最近邻居搜索:Python [英] Nearest Neighbor Search: Python

问题描述

我有一个二维数组:

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 坐标.

The first two elements MyArray[0] and MyArray[1] are the X and Y coordinates of the points.

对于数组中的每个元素，我想找到最快的方法来返回半径为 X 个单位的单个最近邻居.我们假设这是在2D空间中.

For every element in the array, I would like to find the quickest way to return its single nearest neighbor in a radius of X units. We are assuming this is in 2D space.

在本示例中，请说X = 6.

我已经通过将每个元素与每个其他元素进行比较来解决了这个问题，但是当您的列表长度为22k点时，​​这需要15分钟左右的时间.我们希望最终能够在大约3000万点的列表上运行它.

I have solved the problem by comparing every element to every other element, but this takes 15 minutes or so when your list is 22k points long. We hope to eventually run this on lists of about 30million points.

我已经阅读了有关K-d树的知识并了解了其基本概念，但是在理解如何编写它们的脚本时遇到了困难.

I have read about K-d trees and understand the basic concept, but have had trouble understanding how to script them.

推荐答案

感谢John Vinyard提出建议.经过一些良好的研究和测试，以下是此问题的解决方案:

Thanks to John Vinyard for suggesting scipy. After some good research and testing, here is the solution to this question:

先决条件: 安装Numpy和SciPy

Prerequisites: Install Numpy and SciPy

1. 导入SciPy和Numpy模块

1. Import the SciPy and Numpy Modules

制作5维数组的副本，其中包括 just X和Y值.

Make a copy of the 5 dimensional array including just the X and Y values.

创建 :

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

在cKDTree中查询6个单位内的最近邻居，例如:

Query the cKDTree for the Nearest Neighbor within 6 units as such:

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

对于YourArray中的每个项目，TheResult将是两个点之间的距离的元组，以及该点在YourArray中的位置的索引.

for each item in YourArray, TheResult will be a tuple of the distance between the two points, and the index of the location of the point in YourArray.

这篇关于最近邻居搜索:Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！