我有一个二维数组:
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
。
我已经通过比较每个元素和其他元素解决了这个问题,但是当你的列表有22 k个点长时,这个过程需要15分钟左右,我们希望最终能在大约3000万个点的列表上运行这个过程。
我读过关于K-d树的书,理解了它的基本概念,但在理解如何编写脚本时遇到了麻烦。
2条答案
按热度按时间bvuwiixz1#
感谢John Vinyard提出scipy,经过一些很好的研究和测试,下面是这个问题的解决方案:
先决条件:安装Numpy和SciPy
1.导入SciPy和Numpy模块
1.制作一个5维数组的副本,* 仅 * 包括X和Y值。
1.创建
cKDTree
的示例,如下所示:1.在
cKDTree
中查询6个单元内的最近邻,如下所示:对于
YourArray
中的每一项,TheResult
将是两点之间的距离和YourArray
中的点的位置的索引的元组。snvhrwxg2#
使用
sklearn.neighbors
上面的代码在一个简单的示例数据集中查找最近邻,该数据集包含位于单位圆上的10个点。下面解释了该数据集的最近邻算法结果。
结果说明:
结果矩阵
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。因此第一列总是零:型
绘制点:
输入矢量
coords_vect
的坐标: