Используя Numpy для нахождения среднего расстояния в ряде точек
У меня есть массив точек в неизвестном размерном пространстве, таких как:
data=numpy.array(
[[ 115, 241, 314],
[ 153, 413, 144],
[ 535, 2986, 41445]])
и я хотел бы найти среднее евклидово расстояние между всеми точками.
Обратите внимание на то, что у меня есть более чем 20 000 точек, таким образом, я хотел бы сделать это максимально эффективно.
Спасибо.
6 ответов
Я не думаю, что есть сверхбыстрый способ сделать это, но это должно сработать:
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.)
Если у вас есть доступ к scipy, вы можете попробовать следующее:
Теперь, когда вы сформулировали свою цель поиска выбросов, вам, вероятно, лучше вычислить среднее значение выборки и, вместе с тем, дисперсию выборки, поскольку обе эти операции дадут вам операцию O (nd). При этом вы должны иметь возможность находить выбросы (например, исключая точки дальше от среднего, чем некоторая часть стандартного отклонения), и этот процесс фильтрации должен быть возможен за время O (nd) для всего O ( nd).
Возможно, вас заинтересует повторение неравенства Чебышева .
Это когда-либо стоило оптимизировать без рабочего решения? Кроме того, вычисление матрицы расстояний по всему набору данных редко должно быть быстрым, потому что вы делаете это только один раз - когда вам нужно знать расстояние между двумя точками, вы просто смотрите его, оно уже рассчитано.
Итак, если вам не с чего начать, вот одно. Если вы хотите сделать это в Numpy без необходимости писать какой-либо встроенный fortran или C, это не должно быть проблемой, хотя, возможно, вы захотите включить эту небольшую векторную виртуальную машину под названием « numexpr » (доступно на PyPI, тривиально для intall), что в этом случае дало 5-кратный прирост производительности по сравнению с одним Numpy.
Ниже я вычислил матрицу расстояний для 10 000 точек в 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")
Невозможно обойти вопрос о количестве оценок:
![Sum[n-i, {i, 0, n}] = http://www.equationsheet.com/latexrender/pictures/27744c0bd81116aa31c138ab38a2aa87.gif](http://www.equationsheet.com/latexrender/pictures/27744c0bd81116aa31c138ab38a2aa87.gif){kind=link}
Но вы можете не тратиться на все эти квадратные корни, если можете обойтись приближенным результатом. Это зависит от ваших потребностей.
Если вы собираетесь вычислять среднее значение, я бы посоветовал вам не пытаться поместить все значения в массив перед вычислением. Просто вычислите сумму (и сумму квадратов, если вам нужно стандартное отклонение) и отбрасывайте каждое значение по мере его вычисления.
Поскольку 
и 
, я не знаю, означает ли это, что вы должны где-то умножить на два.
Если вам нужно быстрое и неточное решение, вы, вероятно, могли бы адаптировать алгоритм Fast Multipole Method.
Точки, разделенные небольшим расстоянием, имеют меньший вклад в итоговое среднее расстояние, поэтому имеет смысл сгруппировать точки в кластеры и сравнить расстояния между кластерами.