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

vql8enpb  于 12个月前  发布在  其他
关注(0)|答案(1)|浏览(109)

假设我有一个2D numpy数组,大小大约为4000 x 10。假设我把每一行都看作是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更快?

vmdwslir

vmdwslir1#

我认为你的理解不太正确。构造与查找的相对速度取决于算法。The documentation是这样描述你对K-D树的选择的:
KD树的构造非常快:因为仅沿数据轴沿着执行分割,所以不需要计算D维距离。一旦构造完成,查询点的最近邻居**[查找]**只需O[log(N)]距离计算即可确定。虽然KD树方法对于低维(D < 20)邻居搜索非常快,但是当D变得非常大时,它变得低效

相关问题