sklearn最近邻算法的运行时间：构建 vs 查找

Question

sklearn最近邻算法的运行时间：构建 vs 查找

pythonnumpyscikit-learnruntimenearest-neighbor

3

假设我有一个大约为4000乘以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个点的索引，而不需要距离，有没有办法使第二步更快？

- TN530

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Hall · Accepted Answer

我觉得你的理解有些不对。建立和查找的相对速度取决于算法。文档对你选择的K-D树有以下说明（我强调）：

构建KD树非常快：因为分割只沿着数据轴进行，所以不需要计算D维距离。一旦构建完成，查询点的最近邻【查找】只需要进行O[log(N)]次距离计算即可确定。尽管对于低维（D < 20）的邻居搜索，KD树方法非常快，但随着D变得非常大，效率会降低。