最近邻搜索: Python

Question

我有一个二维数组：

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

前两个元素MyArray[0]和MyArray[1]是点的X和Y坐标。

对于数组中的每个元素，我想要找到--在X单位半径内返回其唯一最近邻居的最快方法。我们假设这是在2D空间。

让我们以这个例子为例，X = 6。

我通过比较每个元素和其他元素来解决这个问题，但是当列表长到22k时，这需要15分钟左右的时间。我们希望最终能在大约3000万分的名单上运行。

我读过关于K-d树的文章，并且理解了基本概念，但很难理解如何编写它们的脚本。

Answer 1

感谢约翰·文亚德的建议。经过一些良好的研究和测试，以下是这个问题的解决方案：

先决条件:安装Numpy和SciPy

1. 导入SciPy和Numpy模块
2. 制作一个5维数组的副本，只包括X和Y值。
3. 创建cKDTree的实例如下： YourTreeName = scipy.spatial.cKDTree(YourArray，leafsize=100) #处理页面大小，以获得数据集最快的结果
4. 查询cKDTree中6个单元中最近的邻居，如下所示： 用于YourArray中的项目: TheResult = YourTreeName.query( item，k=1，distance_upper_bound=6) 对于YourArray中的每一项，TheResult将是两个点之间距离的元组，以及YourArray中点位置的索引。

Answer 2

使用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的值是输入向量coords_vect中元素(行)的索引。在我们的示例中，读取结果neighbours_mat的第一行时，coords_vect的索引0中的点最接近自身(索引0)，然后是coords_vect的索引6中的点，然后到索引7 ->中的点--这可以通过下面的“输入向量->图的坐标”来验证。结果neighbours_mat中的第二个raw表明，索引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**:**的坐标

​

​