python - Scipy:通过阈值的稀疏相似性计算 epsilon 邻域

Question

我想知道 scipy 是否提供了实现 epsilon 邻域搜索的原始但内存友好方法的选项:

计算数据的成对相似度，但将所有小于阈值epsilon的相似度动态设置为零，然后直接将结果输出为稀疏矩阵。

例如，scipy.spatial.distance.pdist()确实很快，但与我的时间限制相比，内存限制提前达到了，至少如果我采用squareform().

我知道在这种情况下有 O(n*log(n)) 解决方案，但现在如果结果可以稀疏就足够了。显然，我必须使用相似度而不是距离，但这不应该是一个大问题，不是吗？

Answer 1

只要您可以根据距离度量(例如 1 减去相似度)重新计算相似度度量，那么最有效的解决方案就是使用 sklearn 的 BallTree 。

否则，您可以通过将每个点与其他 $ i -1$ 点进行比较并丢弃所有小于阈值的值来构建自己的 scipy.sparse.csr_matrix 矩阵。

在不知道您的具体相似性指标的情况下，这段代码应该大致可以达到目的:

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)