Более быстрый способ расчета расстояния между каждой точкой и оставшимися n-1 точками

Question

У меня есть n точек, и я должен вычислить евклидово расстояние между каждой точкой и оставшимися n-1 точками. Я использовал следующий способ сделать это в Python:

for eachRow in range(0, numberOfPoints):
        distanceProximityMatrix.append([])

    print('Initialisation Completed')
    for i in range(0, numberOfPoints):
        if(i%100 == 0) : print('.', end = '')
        for j in range(i, numberOfPoints):
            if(i != j):
                tempDist = distanceForMultivariate(recordsList[i], recordsList[j], attributesToBeUsed, isFirstColumnID = isFirstColumnID)
                distanceProximityMatrix[i].append(tempDist) 
                distanceProximityMatrix[j].append(tempDist)
            else :
                distanceProximityMatrix[i].append(0)

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

Примечание. Функция distanceForMultivariate вычисляет евклидово расстояние.

Answer 1

Я предполагаю 2D точки здесь. Тогда евклидово расстояние равно:

sqrt( (x1 - x2)^2 + (y1 - y2)^2 )

У нас есть следующие операции здесь:

• 2 вычитания
• 2 умножения
• 1 дополнение
• 1 кв.

Если вам нужно только сравнить расстояния (например, чтобы найти ближайших соседей), вы можете полностью удалить sqrt, поскольку он сохраняет порядок. Будьте осторожны, чтобы они не стали большими, хотя, если вы захотите суммировать значения позже, они могут стать довольно большими.

Уравнение треугольника НЕ ​​выполняется, поэтому не используйте его там, где это необходимо (поэтому не нужно искать пути или вообще где-нибудь, где вы бы суммировали расстояния!):

if sqrt(a) + sqrt(b) >= sqrt(c), then
a + b <= a + 2sqrt(a*b) + b = (sqrt(a) + sqrt(b)) ^2 >= sqrt(c)^2 = c

sqrt(100) + sqrt(1) >= sqrt(121) но 100 + 1 < 121

При этом, я не думаю, что вы можете уменьшить сложность, если вам действительно нужны все расстояния, потому что тогда вы, несмотря ни на что, вычисляете значения O(n^2).

[Обновление, поскольку приложение теперь ясно]

Хотя я думаю, что мое решение работает для нахождения ближайших соседей, на самом деле есть лучшие алгоритмы, которые решают проблему, чем вычислять некоторое расстояние для всех пар точек. Например, кд-деревья.

Ответы на этот вопрос могут помочь: Как эффективно найти k-ближайших соседей в многомерных данных?

Answer 2

Если это просто намерение найти ближайший k баллы, что вы думаете об этом?
Начните с первого k указывает на некоторый отсортированный массив (в зависимости от расстояния до исходной точки) и вычисляет максимальное расстояние, вызовите это d_max,
За каждую новую точку p, сделайте следующую проверку:

if (x_p - x_start > d_max) or (y_p - y_start > d_max)
then disregard(x)
else:
  d = distance (x, start);
  if d < d_max 
  then:
    insert_into_array(x) // obviously the array must stay sorted
    d_max = distance(array[k],start)

Идея заключается в следующем: если разница между X-координатами или Y-координатами больше, чем максимальное расстояние, то расстояние также будет больше.

Например
Представьте, что ваша начальная точка - (2,2), и вы уже добавили (2,6), (2,3) и (3,2), тогда d_max будет 4. Другие ваши точки - (10,0), (0,20) и (5,6), тогда произойдет следующее:

Add (10,0)? No, because 10 - 2 > 4 (x_p - x_start > d_max)
Add (0,20)? No, because 20 - 2 > 4 (y_p - y_start > d_max)
Add (5,6) ? Maybe: 5 - 2 <= d_max (X-coordinates) => ok
                   6 - 2 <= d_max (Y-coordinates) => ok
                   distance((5,6),(2,2)) = 5, which is larger than 4 => don't add (5,6)

Очевидно, вам нужно создать некий "массив":

• где вы можете добавить точку где-то посередине, чтобы другие сместились соответственно (связанный список).
• если вы добавите точку, и у вас уже есть k записи, последняя запись должна быть удалена.

Поскольку вам нужно только сравнить расстояния, нет необходимости вычислять квадратный корень.

Answer 3

Чрезвычайно быстрый способ вычисления расстояний между точкой и списком точек — это функция einsum из numpy:

          deltas = pointlist - point
    dist_2 = np.einsum('ij,ij->i', deltas, deltas) #squared distance.

для n=1e8 точек на моей машине это занимает всего 1 секунду.

      import numpy as np
import time

n = int( 1e8 )
x_test = np.random.uniform(0,1000, n )
y_test = np.random.uniform(0,1000, n )
xy = np.vstack(( x_test, y_test )).T


t0 = time.perf_counter()     
dist_x0 = argmin_dist( [ x_test[0], y_test[0] ] , xy[1:])
print('Argmin dist took', np.round( time.perf_counter() - t0, 4) , 's')