numpy 最近邻搜索:巨蟒

nwwlzxa7  于 2022-12-18  发布在  其他
关注(0)|答案(2)|浏览(145)

我有一个二维数组:

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0],
                [6588253.79, 1933602.89, 212.66, 0, 0],
                 etc...)

前两个元素MyArray[0]MyArray[1]是点的 XY 坐标。
对于数组中的每一个元素,我都希望找到最快的方法来返回它在 X 个单位半径内的最近邻居,我们假设这是在2D空间中。
假设对于这个例子X = 6
我已经通过比较每个元素和其他元素解决了这个问题,但是当你的列表有22 k个点长时,这个过程需要15分钟左右,我们希望最终能在大约3000万个点的列表上运行这个过程。
我读过关于K-d树的书,理解了它的基本概念,但在理解如何编写脚本时遇到了麻烦。

bvuwiixz

bvuwiixz1#

感谢John Vinyard提出scipy,经过一些很好的研究和测试,下面是这个问题的解决方案:
先决条件:安装Numpy和SciPy
1.导入SciPy和Numpy模块
1.制作一个5维数组的副本,* 仅 * 包括X和Y值。
1.创建cKDTree的示例,如下所示:

YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100)
#Play with the leafsize to get the fastest result for your dataset

1.在cKDTree中查询6个单元内的最近邻,如下所示:

for item in YourArray:
    TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6)

对于YourArray中的每一项,TheResult将是两点之间的距离和YourArray中的点的位置的索引的元组。

snvhrwxg

snvhrwxg2#

使用sklearn.neighbors

from sklearn.neighbors import NearestNeighbors

#example dataset
coords_vect = np.vstack([np.sin(range(10)), np.cos(range(10))]).T 

knn = NearestNeighbors(n_neighbors=3)
knn.fit(coords_vect)
distance_mat, neighbours_mat = knn.kneighbors(coords_vect)

上面的代码在一个简单的示例数据集中查找最近邻,该数据集包含位于单位圆上的10个点。下面解释了该数据集的最近邻算法结果。

结果说明:

neighbours_mat = array([[0, 6, 7],
                        [1, 7, 8],
                        [2, 8, 9],
                        [3, 9, 4],
                        [4, 3, 5],
                        [5, 6, 4],
                        [6, 0, 5],
                        [7, 1, 0],
                        [8, 2, 1],
                        [9, 3, 2]], dtype=int64)

结果矩阵neighbours_mat的值是元素的索引在我们的示例中,阅读结果neighbours_mat的第一行,coords_vect的索引0中的点最接近其自身(索引0)然后到索引6中的点coords_vect,然后到达索引7 -〉中的点,这可以通过下面的“**输入向量coords_vect**的坐标”图进行验证。结果neighbours_mat中的第二个原始数据表示索引1中的点最接近其自身,然后是索引7中的点,然后是索引8中的点,依此类推。
注:结果neighbours_mat中的第一列是我们测量距离的节点,第二列是它的最近邻居,第三列是第二最近邻居。您可以通过增加n_neighbors@NearestNeighbors(n_neighbors=3)初始化来获得更多的邻居。distance_mat是每个节点到它的邻居的距离,注意每个节点到它自己的距离为0。因此第一列总是零:

distance_mat = array([[0.        , 0.28224002, 0.70156646],
                      [0.        , 0.28224002, 0.70156646],
                      [0.        , 0.28224002, 0.70156646],
                      [0.        , 0.28224002, 0.95885108],
                      [0.        , 0.95885108, 0.95885108],
                      [0.        , 0.95885108, 0.95885108],
                      [0.        , 0.28224002, 0.95885108],
                      [0.        , 0.28224002, 0.70156646],
                      [0.        , 0.28224002, 0.70156646],
                      [0.        , 0.28224002, 0.70156646]])


绘制点:

x_vect, y_vect = np.sin(range(10)), np.cos(range(10))
plt.figure()
plt.scatter(x_vect, y_vect)
for x,y, label in zip (x_vect, y_vect, range(number_of_points)):
    plt.text(x,y,label)

输入矢量coords_vect的坐标:

相关问题