Как хешировать векторы в сегменты в локально-чувствительном хешировании (с использованием расстояния jaccard)?

Question

Я внедряю приложение поиска соседей, которое найдет похожие документы. До сих пор я прочитал значительную часть материалов, связанных с LSH (теория, лежащая в основе LSH, является своего рода путаницей, и я пока не могу понять ее на 100%).

Мой код способен вычислять матрицу сигнатур, используя функции minhash (я близок к концу). Я также применяю стратегию полос на матрице подписей. Однако я не могу понять, как хэшировать векторы сигнатур (столбцов) в группе в сегменты.

Мой последний вопрос может быть самым важным, но я должен задать introduction вопросы:

q1: Будет ли хеш-функция отображать только одни и те же векторы в одно и то же ведро? (Предполагая, что у нас достаточно ведер)

q2: должна ли хеш-функция отображать одинаковые векторы в одно и то же ведро? Если да, какова степень / определение этого сходства, так как я не вычисляю сравнение, а делаю хеширование.

q3: в зависимости от приведенных выше вопросов, какой алгоритм хеш-таблицы мне следует использовать?

q4: я думаю, что мое самое слабое место в том, что я понятия не имею, как сгенерировать хеш-функцию, которая принимает векторы как входные данные и выбирает сегмент как выходной. Я могу реализовать один в зависимости от q1 и q2... Любые предложения по генерации хеш-функций для LSH bucketing?

Answer 1

q1: Вы не должны хэшировать весь вектор, но его части. Допустим, у вас есть векторы длиной 100, представляющие каждый элемент, вы можете хешировать 5 срезов длиной 20.

q2: Это основная идея всего этого: вы измеряете сходство, сравнивая части вещей на равенство. Если вы рассматриваете предложения в тексте как векторы, маловероятно, чтобы 2 предложения были одинаковыми (с одинаковым хеш-выводом). Однако, если вы разделите их на части и хешируете части по отдельности, хэши для некоторых совпадающих отдельных слов в одинаковых позициях будут возвращать одинаковый результат хеширования, следовательно, вы можете получить представление о сходстве предложений.

Количество и длина срезов являются важными параметрами, которые влияют на точность результата вашего сходства. Слишком много срезов дало бы много ложных срабатываний, в то время как слишком мало срезов могло бы выявить только самые высокие степени сходства.

Вы можете найти более подробную информацию об этом в книге "Разработка массивных наборов данных", найденной здесь: http://infolab.stanford.edu/~ullman/mmds.html

q3: вам нужна структура данных, которая для каждого уровня среза может хранить результаты хэша для каждого вектора-среза вместе с тем, какой вектор его создал. Затем, когда вы хотите найти похожих соседей по вектору X, вы можете проверить свою структуру данных для каждого среза и посмотреть, был ли полученный хеш-вывод также выведен другим вектором.

Q4: Я не уверен, что вы имеете в виду здесь. Если вы хешируете объект, вы обычно получаете в качестве выходных данных цепочку битов, целое число или число с плавающей запятой, в зависимости от языка. Это ведро. Если вы получаете один и тот же вывод с одной и той же хэш-функцией для другого объекта, это означает, что они хэшируются в одном и том же сегменте.

Answer 2

Один простой способ создать хеш-функцию для LSH заключается в следующем:

Для данного min-hash signature i для каждой полосы b, вычислить сумму строк в полосе, назвать ее S_ib, Создать ведро для S_ib, Для полного набора в корзину будут добавлены записи, в которых сумма соответствует S_ib, в противном случае генерируется новая корзина.

из коллекции импорта defaultdict

....
LSHdictlist = [defaultdict(list) for b in range(bands)]
....
tempsum = np.int(np.sum(M[i,b*rowsinband:(b+1)*rowsinband]))
        LSHdictlist[b][tempsum].append(i)

Вы можете использовать продукт вместо суммы.