Эффективная память среднее попарное расстояние - PullRequest
Новая
       12

Эффективная память среднее попарное расстояние

0 голосов
/ 02 мая 2019

Мне известна функция scipy.spatial.distance.pdist и способ вычисления среднего значения из полученной матрицы / ndarray. 

>>> x = np.random.rand(10000, 2)
>>> y = pdist(x, metric='euclidean')
>>> y.mean()
0.5214255824176626

В приведенном выше примере y становится довольно большим (почти в 2500 раз больше входного массива): 

>>> y.shape
(49995000,)
>>> from sys import getsizeof
>>> getsizeof(x)
160112
>>> getsizeof(y)
399960096
>>> getsizeof(y) / getsizeof(x)
2498.0019986009793

Но так как меня интересует только среднее попарное расстояние, матрицу расстояний не нужно хранить в памяти.Вместо этого среднее значение каждой строки (или столбца) может быть вычислено отдельно.Окончательное среднее значение может быть затем вычислено из средних значений строки.

Уже существует функция, которая использует это свойство, или существует простой способ расширить / объединить существующие функции для этого?

Ответы [ 2 ]

1 голос
/ 02 мая 2019

Если вы используете квадратную версию расстояния, это эквивалентно использованию дисперсии с n-1: 

from scipy.spatial.distance import pdist, squareform
import numpy as np
x = np.random.rand(10000, 2)
y = np.array([[1,1], [0,0], [2,0]])
print(pdist(x, 'sqeuclidean').mean())
print(np.var(x, 0, ddof=1).sum()*2)
>>0.331474285845873
0.33147428584587346
0 голосов
/ 02 мая 2019

Вам придется взвешивать каждую строку по количеству наблюдений, составляющих среднее значение.Например, pdist матрицы 3 x 2 - это сплющенный верхний треугольник (смещение 1) квадратной формы матрицы расстояний 3 x 3. 

arr = np.arange(6).reshape(3,2)
arr
array([[0, 1],
       [2, 3],
       [4, 5]])
pdist(arr)
array([2.82842712, 5.65685425, 2.82842712])
from sklearn.metrics import pairwise_distances
square = pairwise_distances(arr)
square
array([[0.        , 2.82842712, 5.65685425],
       [2.82842712, 0.        , 2.82842712],
       [5.65685425, 2.82842712, 0.        ]])
square[triu_indices(square.shape[0], 1)]
array([2.82842712, 5.65685425, 2.82842712])

Существует pairwise_distances_chunckedфункция, которая может использоваться для итерации по матрице расстояний строка за строкой, но вам нужно будет отслеживать индекс строки, чтобы убедиться, что вы берете только среднее значение в верхнем / нижнем треугольнике матрицы (матрица расстояний симметрична).Это не сложно, но я полагаю, вы внесете значительное замедление. 

tot = ((arr.shape[0]**2) - arr.shape[0]) / 2
weighted_means = 0
for i in gen:
    if r < arr.shape[0]:
        sm = i[0, r:].mean()
        wgt = (i.shape[1] - r) / tot
        weighted_means += sm * wgt
       r += 1
...