MinHashing vs SimHashing

12

Предположим, у меня есть пять наборов, которые я бы хотел сгруппировать. Я понимаю, что техника SimHashing описана здесь:

https://moultano.wordpress.com/2010/01/21/simple-simhashing-3kbzhsxyg4467-6/

может привести к трем кластерам ( {A}, {B,C,D}и {E}), например, если его результаты были:

A -> h01
B -> h02
C -> h02
D -> h02
E -> h03

Точно так же метод MinHashing описан в главе 3 книги MMDS:

http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

может также дать те же три кластера, если его результаты были:

A -> h01 - h02 - h03

B -> h04 - h05 - h06
      |
C -> h04 - h07 - h08
                  |
D -> h09 - h10 - h08

E -> h11 - h12 - h13

(Каждый набор соответствует сигнатуре MH, состоящей из трех «полос», и два набора группируются, если хотя бы одна из их полос подписи совпадает. Чем больше полос, тем больше шансов на совпадение.)

Однако у меня есть несколько вопросов, связанных с этим:

(1) Можно ли понимать SH как однополосную версию MH?

(2) Обязательно ли MH подразумевает использование структуры данных, такой как Union-Find, для построения кластеров?

(3) Прав ли я, полагая, что кластеры в обоих методах на самом деле являются «предкластерами» в том смысле, что они являются просто наборами «пар-кандидатов»?

O(n2)

cjauvin
источник

Ответы:

3

Как правильно указано выше, MinHash и SimHash оба относятся к Locality Sensitive Hashing. Ссылка: https://en.wikipedia.org/wiki/Locality-sensitive_hashing

Основное различие между ними заключается в способе обработки столкновения,

  1. SimHash, использует косинусное сходство
  2. MinHash, использует Jaccard Index.

Ответы на ваши вопросы:

  1. Нет. Они используют разные методы обработки столкновений для проверки сходства. Также есть вариант для одной хэш-функции для минимального хэша, но он работает по-другому. Для получения более подробной информации, проверьте следующую ссылку, https://en.wikipedia.org/wiki/MinHash (вариант с одной хэш-функцией)
  2. Да, https://github.com/chrisjmccormick/MinHash/blob/master/runMinHashExample.py
  3. O(nlogn)
Pramit
источник
SimHash и MinHash не используют эти функции сходства. Я думаю, что лучший способ сказать, что они создают дайджесты, которые приближают эти функции.
Алексей Григорьев
@AlexeyGrigorev Я немного растерялся. Я рассмотрел следующую реализацию для minHash 'computeS SimilarityFromSignatures' @ link . Он использует | HashedArray (A) и HashedArray (B) | / (общее количество записей)
Pramit