Во многих ссылках мне говорили, что KDTree - это быстрый способ найти ближайших соседей для больших данных. Моя текущая проблема состоит в том, чтобы найти ближайшие точки в X для заданных данных A. Для уточнения, в настоящее время X имеет 1 000 000 числовых данных, а A состоит из 10 000. Я хочу найти ближайшую точку в X для каждой из точек в A. Следовательно, результатом должно быть 10000 индексов, указывающих точки данных в X.
Когда я использовал cdist (из scipy.spatial) сЦикл for, чтобы найти ближайшую точку для каждого из данных в A, занял около получаса (1972 секунды), тогда как cKDTree.query занял около 50 минут (2839 секунд) при использовании n_jobs = 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
- Мне любопытно, нормально ли это, и
- вкакие обстоятельства следует использовать cKDTree, если cdist на самом деле быстрее, когда дело доходит до поиска ближайших соседей путем вычисления расстояния в любом случае? Должно ли KDTree быть лучше, если бы я использовал намного больший набор данных A?
- Можно ли найти индексы только при запросе ближайшей точки (k = 1) без расчета расстояния? Я предполагаю, что вычисление расстояния сильно его замедляет (конечно, на данный момент это всего лишь предположение)