Матрица расстояний для произвольного расстояния - PullRequest
Новая
       29

Матрица расстояний для произвольного расстояния

1 голос
/ 07 ноября 2019

Насколько я понимаю, функция scipy scipy.spatial.distance_matrix возвращает расстояние Минковского для любой пары векторов из предоставленных матриц векторов. Есть ли способ получить тот же результат на другом расстоянии? Что-то, что выглядело бы как distance_matrix(X, Y, distance_function)?

Я предполагаю, что scipy выполняет какую-то оптимизацию под капотом. Поскольку я имею дело с очень большими векторами, я бы предпочел не терять преимущества этой оптимизации, реализовав свою собственную функцию distance_matrix.

1 Ответ

0 голосов
/ 07 ноября 2019

Самостоятельно реализовать его самостоятельно

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

Большинство функций расстояния применяют одну функциюна всех парах и суммировать их, например. (A_ik-B_jk)**n для расстояния Минковского, и в конце применяется некоторая другая функция, например. acc**(1/n).

Функция шаблона

Вам не нужно ничего менять здесь для реализации различных функций расстояния. 

import numpy as np
import numba as nb

def gen_cust_dist_func(kernel_inner,kernel_outer,parallel=True):

    kernel_inner_nb=nb.njit(kernel_inner,fastmath=True)
    kernel_outer_nb=nb.njit(kernel_outer,fastmath=True)

    def cust_dot_T(A,B):
        assert B.shape[1]==A.shape[1]

        out=np.empty((A.shape[0],B.shape[0]),dtype=A.dtype)
        for i in nb.prange(A.shape[0]):
            for j in range(B.shape[0]):
                acc=0
                for k in range(A.shape[1]):
                    acc+=kernel_inner_nb(A[i,k],B[j,k])
                out[i,j]=kernel_outer_nb(acc)
        return out

    if parallel==True:
        return nb.njit(cust_dot_T,fastmath=True,parallel=True)
    else:
        return nb.njit(cust_dot_T,fastmath=True,parallel=False)

Примеры и сроки 

#Implement for example a Minkowski distance and euclidian distance
#Minkowski distance p=20
inner=lambda A,B:(A-B)**20
outer=lambda acc:acc**(1./20)
my_minkowski_dist=gen_cust_dist_func(inner,outer,parallel=True)

#Euclidian distance
inner=lambda A,B:(A-B)**2
outer=lambda acc:np.sqrt(acc)
my_euclidian_dist=gen_cust_dist_func(inner,outer,parallel=True)

from scipy.spatial.distance import cdist

A=np.random.rand(1000,50)
B=np.random.rand(1000,50)

#Minkowski p=20
%timeit res_1=cdist(A,B,'m',p=20)
#1.44 s ± 8.18 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit res_2=my_minkowski_dist(A,B)
#10.8 ms ± 105 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
res_1=cdist(A,B,'m',p=20)
res_2=my_minkowski_dist(A,B)
print(np.allclose(res_1,res_2))
#True

#Euclidian
%timeit res_1=cdist(A,B,'euclidean')
#39.3 ms ± 307 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit res_2=my_euclidian_dist(A,B)
#3.61 ms ± 22.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
res_1=res_1=cdist(A,B,'euclidean')
res_2=my_euclidian_dist(A,B)
print(np.allclose(res_1,res_2))
#True
...