稀疏numpy数组的局部敏感哈希

Question

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

给定一个点P（矩阵中的一行）和一个距离epsilon，找到所有距离P不超过epsilon的点。

我使用的距离度量是Jaccard相似度，因此可以使用局部敏感哈希技巧（如MinHash）。

是否有用于稀疏numpy数组的MinHash实现（我似乎找不到任何实现），或者是否有简单的方法可以做到这一点？

我之所以不从Github上获取为非稀疏数组构建的东西，是因为scipy中的稀疏数据结构可能会导致时间复杂度爆炸。

- utdiscant

---

到目前为止，我已经实现了一个使用https://github.com/go2starr/lshhdc的实现。 - utdiscant

Answer 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，但我个人还没有测试过它与稀疏矩阵的兼容性。

- COOLZXxX