Nhạy cảm theo địa phương Hashing mảng thưa thớt thưa thớt

Question

Tôi có một ma trận numpy/scipy thưa thớt lớn, trong đó mỗi hàng tương ứng với một điểm trong không gian chiều cao. Tôi muốn làm cho truy vấn của các loại sau đây:

Cho một điểm P (một hàng trong ma trận) và một khoảng cách epsilon, tìm tất cả các điểm với khoảng cách tối đa là epsilon từ P.

Chỉ số khoảng cách tôi đang sử dụng là tương tự như Jaccard, vì vậy, bạn có thể sử dụng các thủ thuật Nhạy cảm về mặt địa phương như MinHash.

Có triển khai MinHash cho mảng thưa thớt thưa thớt ở đâu đó không (dường như tôi không thể tìm thấy) hoặc có cách dễ dàng để thực hiện việc này không?

Lý do tôi không chỉ kéo thứ gì đó được xây dựng cho mảng không thưa thớt của Github là các cấu trúc dữ liệu thưa thớt trong scipy có thể gây nổ trong thời gian phức tạp.

Answer 1

Nếu bạn có bộ dữ liệu thưa thớt rất lớn mà là quá lớn sẽ được tổ chức trong bộ nhớ trong một định dạng không thưa thớt, tôi muốn thử thực hiện LSH này được xây dựng xung quanh các giả định về CSR thưa thớt Ma trận scipy của:

https://github.com/brandonrobertz/SparseLSH

Nó cũng hỗ trợ băm cho các kho khóa-giá trị dựa trên đĩa như LevelDB nếu bạn không thể phù hợp với các bảng trong bộ nhớ. Từ các tài liệu:

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) 

Nếu bạn chắc chắn chỉ muốn sử dụng MinHash, bạn có thể thử ra https://github.com/go2starr/lshhdc, nhưng tôi đã không đích thân kiểm tra rằng một ra cho khả năng tương thích với các ma trận thưa thớt.