В python есть что-то похожее на scipy.spatial.distance.cdist, но для смещений (быстрых)? - PullRequest
Новая
       45

В python есть что-то похожее на scipy.spatial.distance.cdist, но для смещений (быстрых)?

1 голос
/ 06 марта 2020

Я работал над исследовательским кодом в течение нескольких недель и пытался ускорить его, используя cdist вместо многоуровневого для l oop для вычисления расстояний между каждой точкой в ​​матрице.

Что я хочу: 

    from scipy.spatial.distance import cdist
    import numpy as np

    a=np.array([[1],[2],[3]])
    cdist(a,a, lambda u,v: u-v)

[[ 0. -1. -2.]
 [ 1.  0. -1.]
 [ 2.  1.  0.]]

Однако моя проблема в том, что в контексте моего исследования a довольно велико, и использование собственной лямбда-функции в cdist значительно медленнее ( ~ 2 порядка), чем cdist (a, a) - но это дает только положительные значения. т.е. в действительности я должен вычислить это 15 000 раз, когда a имеет 1000 элементов, поэтому эти 2oom имеют большое значение.

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

[[0. 1. 2.]
 [1. 0. 1.]
 [2. 1. 0.]]

Я надеюсь, что вы, ребята, могли бы предложить, как я могу сделать что-то для создания желаемого выхода со знаком из cdist, но быстрее, чем с помощью лямбда-функции.

Спасибо!

1 Ответ

0 голосов
/ 06 марта 2020

В зависимости от вашего метрического расстояния c и типа данных, которые вы имеете, у вас есть различные варианты:

Для вашего конкретного c случая, когда данные 1D и |u-v| == ( (u-v)^2 )^(1/2) вы можете просто использовать свои знания о том, что верхний и нижний треугольник матрицы расстояний равны в абсолютном выражении и отличаются только по знаку, поэтому вы можете избежать пользовательской функции расстояния: 

d = cdist(a, a)

triu_bool = np.triu(np.ones((n_samples, n_samples), dtype=bool))
triu_bool[range(n_samples), range(n_samples)] = False
d[triu_bool] *= -1
# [[ 0. -1. -2.]
#  [ 1.  0. -1.]
#  [ 2.  1.  0.]]

более общий и, на мой взгляд, лучше подход просто использовать numpys вещание ( см. также этот вопрос / ответ ). Вот пример для u-v: 

# Generate data
n_dim = 3
n_samples = int(1.5e4)
arr = np.concatenate([np.arange(n_samples)[:, np.newaxis]] * n_dim, axis=-1)
# array([[    0,     0,     0],
#        [    1,     1,     1],
#        [    2,     2,     2],
#        ...,
#        [14997, 14997, 14997],
#        [14998, 14998, 14998],
#        [14999, 14999, 14999]])

# u - v
d = arr[:, np.newaxis, :] - arr[np.newaxis, :, :]
# (n_samples, n_samples, n_dim)

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

...