Использование Numpy для определения среднего расстояния в наборе точек

Question

У меня есть массив точек в неизвестном размерном пространстве, например:

data=numpy.array(
[[ 115, 241, 314],
[ 153, 413, 144],
[ 535, 2986, 41445]])

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

Обратите внимание, что у меня более 20 000 баллов, поэтому я хотел бы сделать это максимально эффективно.

Спасибо.

Answer 1

Если у вас есть доступ к scipy, вы можете попробовать следующее:

scipy.spatial.distance.cdist(data,data)

Answer 2

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

Так что, если у вас нет места, чтобы начать, вот один. Если вы хотите сделать это в Numpy без необходимости писать какие-либо встроенные фортран или C, это не должно быть проблемой, хотя, возможно, вы захотите включить эту небольшую векторную виртуальную машину под названием " Numberxpr " (доступно на PyPI (тривиально для ввода), который в этом случае дал 5-кратное повышение производительности по сравнению с одним Numpy.

Ниже я вычислил матрицу расстояний для 10000 точек в 2D-пространстве (матрица 10K x 10k, показывающая расстояние между всеми 10k точками). На моем MBP это заняло 59 секунд.

import numpy as NP
import numexpr as NE

# data are points in 2D space (x, y)--obviously, this code can accept data of any dimension
x = NP.random.randint(0, 10, 10000)
y = NP.random.randint(0, 10, 10000)
fnx = lambda q : q - NP.reshape(q, (len(q), 1))
delX = fnx(x)
delY = fnx(y)
dist_mat = NE.evaluate("(delX**2 + delY**2)**0.5")

Answer 3

Теперь, когда вы заявили о своей цели нахождения выбросов, вам, вероятно, лучше вычислить среднее значение выборки и, следовательно, дисперсию выборки, поскольку обе эти операции дадут вам операцию O (nd).При этом вы должны быть в состоянии найти выбросы (например, исключая точки дальше от среднего значения, чем некоторая часть стандартного отклонения), и этот процесс фильтрации должен быть выполнен за O (nd) время для общего количества O (nd).

Вас может заинтересовать повышение квалификации по неравенству Чебышева .

Answer 4

Количество оценок невозможно обойти:

Сумма [n-i, {i, 0, n}] = http://www.equationsheet.com/latexrender/pictures/27744c0bd81116aa31c138ab38a2aa87.gif

Но вы можете сэкономить на счетах всех этих квадратных корней, если сможете обойтись приблизительным результатом . Это зависит от ваших потребностей.

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

С и Я не знаю, означает ли это, что вам нужно где-то умножить на два.

Answer 5

Ну, я не думаю, что есть супер быстрый способ сделать это, но это должно сделать это:

tot = 0.

for i in xrange(data.shape[0]-1):
    tot += ((((data[i+1:]-data[i])**2).sum(1))**.5).sum()

avg = tot/((data.shape[0]-1)*(data.shape[0])/2.)

Answer 6

Если вы хотите быстрое и неточное решение, вы, вероятно, можете адаптировать алгоритм Fast Multipole .

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