计算（x，y，z）点列表中最近邻的（欧几里德）距离最有效的方法是什么？

Question

计算数组中每个点的最近邻距离（欧几里德距离）最有效的方法是什么？在

我有一个100k（X，Y，Z）点的列表，我想计算最近邻距离的列表。距离的指数与点的指数相对应。在

我调查过PYOD和sklearn的邻居，但这些似乎需要“教学”。我想我的问题比那简单。对于每个点：找到最近的邻居，计算距离。在

示例数据：

points = [
     (0             0   1322.1695
      0.006711111   0   1322.1696
      0.026844444   0   1322.1697
      0.0604        0   1322.1649
      0.107377778   0   1322.1651
      0.167777778   0   1322.1634
      0.2416        0   1322.1629
      0.328844444   0   1322.1631
      0.429511111   0   1322.1627...)]

计算k=1最近邻距离

结果格式：

^{pr2}$

示例结果：

^{3}$

更新：

我已经实现了建议的两种方法。在

1. 使用scipy.space.cdist计算全距离矩阵
2. 使用半径R中的最近X邻居来查找每个点的邻居距离子集并返回最小值。在

结果是，方法2比方法1快，但在实现上花费了更多的精力（有意义）。在

似乎方法1的限制因素是运行完整计算所需的内存，尤其是当我的数据集接近10^5（x，y，z）点时。对于我的23k点数据集，捕获最小距离需要大约100秒。在

对于方法2，速度缩放为n_半径^2。也就是“邻域半径平方”，这意味着该算法与包含的邻域数成线性关系。使用半径~5（超过给定应用程序的足够），对于23k个点的集合，需要5秒的时间来提供一个分钟列表，其顺序与point_列表本身的顺序相同。“精确解”与方法2之间的差矩阵基本上为零。在

谢谢大家的帮助！在

Answer 1

这个怎么样？在

from scipy.spatial import distance

A = (0.003467119 ,0.01422762 ,0.0101960126)
B = (0.007279433  ,0.01651597  ,0.0045558849)
C = (0.005392258  ,0.02149997  ,0.0177409387)
D = (0.017898802  ,0.02790659  ,0.0006487222)
E = (0.013564214  ,0.01835688  ,0.0008102952)
F = (0.013375397  ,0.02210725 ,0.0286032185)

points = [A, B, C, D, E, F]
results = []
for point in points:
    distances = [{'point':point, 'neighbor':p, 'd':distance.euclidean(point, p)} for p in points if p != point]
    results.append(min(distances, key=lambda k:k['d']))

结果将是一个对象列表，如下所示：

^{pr2}$

其中point是参考点，neighbor是点的最近邻居。在

Answer 2

类似于Caleb的答案，但是如果您得到的距离大于某个先前的最小距离，您可以停止迭代循环（抱歉-没有代码）。在

我以前常编视频游戏。计算两点之间的实际距离需要太多的CPU。我们所做的是将“屏幕”划分成更大的笛卡尔平方，并且如果Delta-X或Delta-Y“太远”则避免实际的距离计算-这只是减法，所以也许类似这样的东西来限定需要实际欧几里德距离度量计算的地方（根据需要扩展到n维）？在

编辑-扩展“太远”候选对选择注释。 为了简洁起见，我将假设一个二维的场景。 取兴趣点（X0，Y0）并围绕该点“画”一个nxn正方形，原点是（X0，Y0）。在

浏览初始点列表，并在该方格内形成候选点列表。在此过程中，如果DeltaX[ABS（Xi-X0）]在正方形之外，则无需计算DeltaY。在

如果没有候选点，则使正方形变大并迭代。在

如果只有一个候选点，并且它在正方形表示的圆的半径内，那就是你的最小值。在

如果有“太多”候选项，将正方形缩小，，但只需重新检查此迭代中的候选项列表，而不是所有点。

如果没有“太多”候选对象，则计算该列表的距离。执行此操作时，首先计算第一个候选人的DeltaY^2+DeltaY ^2。如果对于后续候选对象，DetlaX^2大于到目前为止的minumin，则不需要计算DeltaY^2。在

如果最小值在正方形内接圆的半径内，则该计算得出的最小值为最小值。在

如果没有，则需要返回上一个候选列表，该列表包含半径为该最小值的圆内的点。例如，如果以一个2x2正方形中的一个候选对象结束，该正方形恰好位于顶点X=1，Y=1上，则距离/半径将为SQRT（2）。所以回到前面的一个候选列表，这个列表的正方形变灰或等于2xSQRT（2）。在

如果有必要，生成一个新的候选列表，该列表只包含带有+/-SQRT（2）正方形的点。 按上述方法计算这些候选点的距离-忽略目前为止超过最小计算值的任何点。在

只有一个候选者时，才需要求增量^2和的平方根。在

如何调整初始正方形的大小，或者它是否应该是一个矩形，以及如何增加或减少正方形/矩形的大小都会受到数据分布应用知识的影响。在

如果您使用的语言支持递归算法，我会考虑使用递归算法。在

Answer 3

您可以使用的最快选项可能是^{}，它可以查找其输入中所有点之间的成对距离。虽然查找所有这些距离可能不是查找最近邻居的最快算法，但是cdist是用C实现的，因此它可能比Python中的任何方法都运行得更快。在

import scipy as sp
import scipy.spatial
from scipy.spatial.distance import cdist

points = sp.array(...)
distances = sp.spatial.distance.cdist(points)

# An element is not its own nearest neighbor
sp.fill_diagonal(distances, sp.inf)

# Find the index of each element's nearest neighbor
mins = distances.argmin(0)

# Extract the nearest neighbors from the data by row indexing
nearest_neighbors = points[mins, :]

#  Put the arrays in the specified shape
results = np.stack((points, nearest_neighbors), 1)

理论上你可以让它运行得更快（主要是通过将所有的步骤合并到一个算法中），但是除非你用C编写，否则你将无法与SciPy/NumPy竞争。在

（cdist在Θ（n²）时间内运行（如果每个点的大小是固定的），并且算法的每个其他部分都在O（n）时间内运行，因此即使您尝试在Python中优化代码，您也不会注意到少量数据的变化，并且对于更多的数据，cdist的改进也会黯然失色。）