Scipy:阈值稀疏相似的epsilon邻域

2024-03-28 15:23:43 发布

您现在位置:Python中文网/ 问答频道 /正文

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

为我的数据计算两两相似性,但将所有小于阈值epsilon的相似性设置为零,然后将结果直接输出为稀疏矩阵。你知道吗

例如scipy.spatial.distance.pdist()确实很快,但是与我的时间限制相比,内存限制很早就达到了,至少如果我使用squareform()。你知道吗

我知道在这种情况下有O(n*log(n))个解,但是现在如果结果是稀疏的就足够了。很明显,我不得不用相似性来代替距离,但这不应该是个大问题,不是吗。你知道吗


Tags: 数据方法内存时间情况矩阵阈值scipy
1条回答
网友
1楼 · 发布于 2024-03-28 15:23:43

只要你能用距离度量(比如1减去相似度)来重铸你的相似度度量,那么最有效的解决方案就是使用sklearn的BallTree。你知道吗

否则你可以自己造一个scipy.sparse.csr\u矩阵通过将每个点与其他$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)

相关问题 更多 >