MinHashing vs SimHashing

Question

Предположим, у меня есть пять наборов, которые я бы хотел сгруппировать. Я понимаю, что техника 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) Прав ли я, полагая, что кластеры в обоих методах на самом деле являются "предкластерами" в том смысле, что они представляют собой просто наборы "пар-кандидатов"?

(4) Если (3) верно, означает ли это, что мне все еще нужно сделать O(n^2) искать внутри каждого "предварительного кластера", чтобы разделить их дальше на "реальные" кластеры? (что может быть разумно, если у меня много небольших и достаточно сбалансированных предкластеров, но не так сильно)

Answer 1

SimHash и MinHash - оба алгоритма хеширования, которые могут отображать набор в список значений, который соответствует сигнатуре набора.

В случае SimHash список значений - это просто список битов (значения могут быть 0 или 1). В случае MinHash значение в списке представляет минимальное хеш-значение всех установленных элементов относительно данной хеш-функции, которое обычно является 32-битным или 64-битным значением.

Основным отличием обоих алгоритмов является вероятность коллизий хешей. В случае SimHash оно равно косинусному сходству, а в случае MinHash оно равно сходству Джакарда. В зависимости от того, как вы определяете сходство между наборами, тот или иной алгоритм может быть более подходящим.

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