Scipy: эпсилон окрестности по редкому сходству с порогом

Question

Мне интересно, предлагает ли scipy возможность реализовать примитивный, но дружественный к памяти подход к поиску окрестностей в эпсилоне:

Вычислить попарно подобие для моих данных, но установить все сходства меньше порога epsilon, чтобыноль на лету, а затем вывод результата непосредственно в виде разреженной матрицы.

Например, scipy.spatial.distance.pdist() действительно быстрый, но ограничение памяти достигается раньше по сравнению с моим ограничением по времени, по крайней мере, если я беру squareform().

Я знаю, что есть O (n * log (n)) решения в этом случае, но на данный момент было бы достаточно, если бы результат мог быть редким.Также очевидно, что мне придется использовать сходство, а не расстояние, но это не должно быть такой большой проблемой, если это так.

Answer 1

Пока вы можете изменить свою меру сходства с точки зрения метрики расстояния (скажем, 1 минус сходство), тогда наиболее эффективным решением будет использование BallTree от sklearn.

В противном случае вы можете построить собственную матрицу scipy.sparse.csr_matrix, сравнивая каждую точку с другими точками $ i -1 $ и выбрасывая все значения, меньшие порога.

Не знаяВаша конкретная метрика сходства, этот код должен примерно сделать свое дело:

import scipy.sparse as spsparse
from sklearn.metrics.pairwise import cosine_similarity
import numpy as np


def sparse_similarity(X, epsilon=0.99, Y=None, similarity_metric=cosine_similarity):
    '''
    X : ndarray
        An m by n array of m original observations in an n-dimensional space.
    '''
    Nx, Dx = X.shape
    if Y is None:
        Y=X
    Ny, Dy = Y.shape

    assert Dx==Dy


    data = []
    indices = []
    indptr = [0]
    for ix in range(Nx):
        xsim = similarity_metric([X[ix]], Y)
        _ , kept_points = np.nonzero(xsim>=epsilon)
        data.extend(xsim[0,kept_points])
        indices.extend(kept_points)
        indptr.append(indptr[-1] + len(kept_points))

    return spsparse.csr_matrix((data, indices, indptr), shape=(Nx,Ny))


X = np.random.random(size=(1000,10))
sparse_similarity(X, epsilon=0.95)