Как наиболее эффективно рассчитать (евклидово) расстояние ближайшего соседа в списке точек (x, y, z)?

Question

Каков наиболее эффективный способ вычисления (евклидова) расстояния ближайшего соседа для каждой точки в массиве?

У меня есть список из 100k (X, Y, Z) точек, и я хотел бывычислить список расстояний ближайших соседей. Индекс расстояния будет соответствовать индексу точки.

Я смотрел на PYOD и sklearn соседей, но те, кажется, требуют "обучения". Я думаю, что моя проблема проще, чем это. Для каждой точки: найти ближайшего соседа, вычислить расстояние.

Пример данных:

points = [
     (0             0   1322.1695
      0.006711111   0   1322.1696
      0.026844444   0   1322.1697
      0.0604        0   1322.1649
      0.107377778   0   1322.1651
      0.167777778   0   1322.1634
      0.2416        0   1322.1629
      0.328844444   0   1322.1631
      0.429511111   0   1322.1627...)]

вычислить k = 1 расстояние ближайшего соседа

формат результата:

results = [nearest neighbor distance]

пример результатов:

results = [
0.005939372
0.005939372
0.017815632
0.030118587
0.041569616
0.053475883
0.065324964
0.077200014
0.089077602)
]

ОБНОВЛЕНИЕ:

Я реализовал два из предложенных подходов.

1. Используйте scipy.spatial.cdistдля вычисления матриц полных расстояний
2. Используйте ближайшие X соседей в радиусе R, чтобы найти подмножество соседних расстояний для каждой точки и вернуть наименьшее.

В результате метод 2 быстреечем метод 1, но потребовалось намного больше усилий для реализации (имеет смысл).

Кажется, что ограничивающим фактором для метода 1 является объем памяти, необходимый для выполнения полного вычисления, особенно когда мой набор данных приближается к 10 ^ 5(x, y, z) баллы. Для моего набора данных, состоящего из 23 тыс. Точек, для захвата минимальных расстояний требуется ~ 100 секунд.

Для метода 2 скорость масштабируется как n_radius ^ 2. То есть «квадрат радиуса соседа», что в действительности означает, что алгоритм масштабируется ~ линейно с количеством включенных соседей. При использовании радиуса ~ 5 (более чем достаточно для данного приложения) потребовалось 5 секунд для набора из 23 тыс. Точек, чтобы получить список минут в том же порядке, что и сам point_list. Матрица различий между «точным решением» и методом 2. в основном равна нулю.

Спасибо за помощь всем!

Answer 1

Самый быстрый вариант, доступный для вас, может быть scipy.spatial.distance.cdist, который находит попарные расстояния между всеми точками на своем входе. Хотя поиск всех этих расстояний может быть не самым быстрым алгоритмом для поиска ближайших соседей, cdist реализован в C, поэтому он, вероятно, работает быстрее, чем все, что вы пытаетесь в Python.

import scipy as sp
import scipy.spatial
from scipy.spatial.distance import cdist

points = sp.array(...)
distances = sp.spatial.distance.cdist(points)

# An element is not its own nearest neighbor
sp.fill_diagonal(distances, sp.inf)

# Find the index of each element's nearest neighbor
mins = distances.argmin(0)

# Extract the nearest neighbors from the data by row indexing
nearest_neighbors = points[mins, :]

#  Put the arrays in the specified shape
results = np.stack((points, nearest_neighbors), 1)

Вы можететеоретически сделать это быстрее (в основном за счет объединения всех шагов в один алгоритм), но если вы не пишете на C, вы не сможете конкурировать с SciPy / NumPy.

(cdistвыполняется за Θ (n ² ) времени (если размер каждой точки фиксирован), и за любую другую часть алгоритма за O (n), поэтому даже если вы пытались оптимизировать код вPython, вы не заметите изменения для небольших объемов данных, и улучшения будут затенены cdist для получения дополнительных данных.)

Answer 2

Аналогично ответу Калеба, но вы можете остановить итеративный цикл, если вы получите расстояние, превышающее некоторое предыдущее минимальное расстояние (извините, кода нет).

Я использовал для программирования видеоигр. Для вычисления фактического расстояния между двумя точками потребуется слишком много ресурсов процессора. Мы делили «экран» на большие декартовы квадраты и избегали вычисления фактического расстояния, если Delta-X или Delta-Y были «слишком далеко» - это просто вычитание, так что, может быть, что-то в этом роде, чтобы определить, где находится настоящий ЕвклианТребуется вычислить метрику расстояния (при необходимости расширить на n-размеры)?

РЕДАКТИРОВАТЬ - расширение «слишком далеко» комментариев выбора пары кандидатов. Для краткости я возьму двумерный пейзаж. Возьмите интересующую точку (X0, Y0) и «нарисуйте» квадрат nxn вокруг этой точки с (X0, Y0) в начале координат.

Пройдите начальный список точек и сформируйте список кандидатовточки, которые находятся в этом квадрате. При этом, если DeltaX [ABS (Xi-X0)] находится за пределами квадрата, вычислять DeltaY не нужно.

Если нет точек-кандидатов, увеличьте квадрат и выполните итерацию.

Если есть ровно одна точка-кандидат, и она находится в радиусе круга, на который наложен квадрат, то это ваш минимум.

Если «слишком много» кандидатов, сделайте квадратменьше, , но вам нужно только пересмотреть список кандидатов из этой итерации, а не все точки.

Если кандидатов не слишком много, вычислите расстояние для этого списка. При этом сначала рассчитайте DeltaX ^ 2 + DeltaY ^ 2 для первого кандидата. Если для последующих кандидатов DetlaX ^ 2 до сих пор больше, чем минимумин, нет необходимости вычислять DeltaY ^ 2.

Минимум из этого расчета является минимумом, если он находится в радиусе круга, вписанногоквадрат.

Если нет, вам нужно вернуться к предыдущему списку кандидатов, в котором есть точки внутри круга, радиус которого равен этому минимуму. Например, если вы закончили с одним кандидатом в квадрат 2x2, который оказался в вершине X = 1, Y = 1, расстояние / радиус будет SQRT (2). Поэтому вернитесь к предыдущему списку кандидатов, который имеет квадрат с жадностью или равный 2xSQRT (2).

Если это оправдано, создайте новый список кандидатов, который включает в себя только точки с квадратом +/- SQRT (2). Вычислите расстояние для этих баллов-кандидатов, как описано выше, исключая любые, которые превышают рассчитанный минимум.

Нет необходимости делать квадратный корень из суммы Дельты ^ 2, пока у вас не будет только одного кандидата.

Как измерить начальный квадрат, или если он должен быть прямоугольником, и как увеличить или уменьшить размер квадрата / прямоугольника, может повлиять знание приложения о распределении данных.

Iрассмотрел бы рекурсивные алгоритмы для некоторых из них, если язык, который вы используете, поддерживает это.

Answer 3

Как насчет этого?

from scipy.spatial import distance

A = (0.003467119 ,0.01422762 ,0.0101960126)
B = (0.007279433  ,0.01651597  ,0.0045558849)
C = (0.005392258  ,0.02149997  ,0.0177409387)
D = (0.017898802  ,0.02790659  ,0.0006487222)
E = (0.013564214  ,0.01835688  ,0.0008102952)
F = (0.013375397  ,0.02210725 ,0.0286032185)

points = [A, B, C, D, E, F]
results = []
for point in points:
    distances = [{'point':point, 'neighbor':p, 'd':distance.euclidean(point, p)} for p in points if p != point]
    results.append(min(distances, key=lambda k:k['d']))

Результатами будет список объектов, например:

results = [
    {'point':(x1, y1, z1), 'neighbor':(x2, y2, z2), 'd':"distance from point to neighbor"},
...]

Где point - это контрольная точка, а neighbor - это точкаближайший сосед.