5

许多参考资料都告诉我，KDTree 是一种快速查找大数据最近邻居的方法。我当前的问题是为给定的数据 A 在 X 中找到最近的点。详细说明，目前，X 有 1,000,000 个数字数据，A 由 10,000 个组成。我想为 A 中的每个点找到 X 中最近的点。因此，结果应该是 10,000 个指示 X 中的数据点的索引。

当我使用 cdist（来自 scipy.spatial）和 for 循环来查找 A 中每个数据的最近点时，大约需要半小时（1972 秒），而使用 n_jobs 时，cKDTree.query 大约需要 50 分钟（2839 秒） = 4。

cdist 的代码如下：

t = time.time() 
nn = np.array([])
jump = 1000
nloop = np.ceil(A.shape[0]/jump).astype(int)
for ii in range(nloop):
   temp = cdist(X, A[ii*jump:(ii+1)*jump])
   nn = np.append(nn, np.argmin(temp, axis = 0))
print('Elapsed time: ', time.time() - t) # this was 1926 seconds (a little bit faster than one by one loop)

cKDTree 的代码如下：

t = time.time()
tree = cKDTree(X)
nn = tree.query(A, 1, n_jobs = 4)[1]
print('Elapsed time: ', time.time() - t) # this is 2839 seconds
  1. 我很好奇这是否正常
  2. 如果 cdist 在通过计算距离来找到最近的邻居时实际上更快，那么在什么情况下应该使用 cKDTree？如果我使用更大的数据集 A，KDTree 会更好吗？
  3. 有没有办法只在查询最近点（k=1）而不计算距离时才找到索引？我的猜测是距离计算会减慢很多（当然这只是一个猜测）
4

0 回答 0