稀疏numpy数组的局部敏感散列-Java 学习之路

我有一个大的稀疏numpy / scipy矩阵，其中每一行对应于高维空间中的一个点 . 我想要进行以下类型的查询：

给定点 P （矩阵中的一行）和距离 epsilon ，从 P 找到距离最多 epsilon 的所有点 .

我使用的距离度量是Jaccard相似度，因此应该可以使用MinHash等Locality Sensitive Hashing技巧 .

是否有一个MinHash的实现稀疏numpy数组（我似乎找不到）或有一个简单的方法来做到这一点？

我之所以不仅仅是为Github提取非稀疏数组的内容，原因是scipy中的稀疏数据结构可能会导致时间复杂度的爆炸 .

1 回答

如果你有非常大的稀疏数据集，这些数据集太大而不能以非稀疏格式保存在内存中，我会尝试这个基于Scipy的CSR稀疏矩阵假设的LSH实现：

https://github.com/brandonrobertz/SparseLSH

如果你不能将表放在内存中，它还会对像LevelDB这样的基于磁盘的键值存储进行哈希支持 . 来自文档：

from sparselsh import LSH
from scipy.sparse import csr_matrix

X = csr_matrix( [
    [ 3, 0, 0, 0, 0, 0, -1],
    [ 0, 1, 0, 0, 0, 0,  1],
    [ 1, 1, 1, 1, 1, 1,  1] ])

# One class number for each input point
y = [ 0, 3, 10]

X_sim = csr_matrix( [ [ 1, 1, 1, 1, 1, 1, 0]])

lsh = LSH( 4,
           X.shape[1],
           num_hashtables=1,
           storage_config={"dict":None})

for ix in xrange(X.shape[0]):
    x = X.getrow(ix)
    c = y[ix]
    lsh.index( x, extra_data=c)

# find points similar to X_sim
lsh.query(X_sim, num_results=1)

如果你肯定只想使用MinHash，你可以试试https://github.com/go2starr/lshhdc，但我没有亲自测试那个与稀疏矩阵的兼容性 .

回复于 2024-05-05T03:03:30+08:00

稀疏numpy数组的局部敏感散列

1 回答

相关问题