sklearn 最近邻运行时：构造与查找

Question

假设我有一个大小约为 4000 x 10 的 2D numpy 数组。假设我将每一行视为 10 维空间中的一个点，并且想要计算每个点的 5 个最近邻。我运行了以下代码。

import numpy as np
from sklearn.neighbors import NearestNeighbors
import time
A = np.random.rand(4000, 10)
t1 = time.time()
nbrs = NearestNeighbors(n_neighbors = 5, algorithm = 'kd_tree').fit(A)
t2 = time.time()
distance, indices = nbrs.kneighbors(A)
t3 = time.time()
print('time taken for step1: fitting is:', t2 - t1)
print('time taken for step2: retrieving data is:', t3 - t2)

结果是

time taken for step1: fitting is: 0.009654521942138672
time taken for step2: retrieving data is: 0.3108406066894531

我的第一个问题：为什么获取距离/索引数组比拟合花费的时间长得多。据我理解，拟合是构建模型的过程（计算距离，对计算出的距离进行排序），而获取距离/指数只是从模型中读取数据。这与我的直觉完全相反，第二步花费了更多时间。我的哪一部分理解是错误的？

我的第二个问题是，如果我只想要模型中的索引，即对于每个点，最近的 5 个点的索引，而不是距离，有什么方法可以使步骤 2 更快？

Answer 1

我觉得你的理解不太对。构造与查找的相对速度取决于算法。 文档说明了您对 K-D 树的选择（我的重点）：

KD 树的构建非常快：因为仅沿着数据轴进行分区，所以不需要计算 D 维距离。一旦构造完毕，只需 O[log(N)] 距离计算即可确定查询点的最近邻居 [lookup]。尽管 KD 树方法对于低维 (D < 20) neighbors searches, it becomes inefficient as D grows very large