Хеширование с учетом местоположения разреженных массивов numpy

У меня есть большая разреженная матрица numpy/scipy, где каждая строка соответствует точке в многомерном пространстве. Я хочу сделать запросы следующего вида:

Имея точку P (строка в матрице) и расстояние эпсилон, найдите все точки с расстоянием не более эпсилон от P .

Метрика расстояния, которую я использую, — это сходство с Jaccard, поэтому должна быть возможность использовать приемы хеширования с учетом местоположения, такие как MinHash.

Есть ли где-нибудь реализация MinHash для разреженных массивов numpy (кажется, я не могу ее найти) или есть простой способ сделать это?

Причина, по которой я не просто вытаскиваю что-то, созданное для неразреженных массивов, с Github, заключается в том, что разреженные структуры данных в scipy могут вызвать взрыв временной сложности.


python numpy scipy locality-sensitive-hash
person utdiscant    schedule 17.07.2014    source источник
comment
До сих пор я сделал реализацию, которая использует github.com/go2starr/lshhdc.   -  person utdiscant    schedule 17.07.2014

Ответы (1)


arrow_upward
7
arrow_downward

Если у вас есть очень большие разреженные наборы данных, которые слишком велики для хранения в памяти в неразреженном формате, я бы попробовал эту реализацию LSH, построенную на предположении о разреженных матрицах Scipy CSR:

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, но я лично не тестировал его на совместимость с разреженными матрицами.

person COOLZXxX    schedule 26.07.2014