VMath

Для конечных непустых множеств $ \mathbb A $ и $ \mathbb B $ коэффициент их сходства (индекс) Жаккара¹⁾ определяется как $$ J(\mathbb A,\mathbb B)=\frac{ \operatorname{Card}(\mathbb A \cap \mathbb B ) }{ \operatorname{Card}(\mathbb A \cup \mathbb B )}= \frac{ \operatorname{Card}(\mathbb A \cap \mathbb B ) }{ \operatorname{Card}(\mathbb A) + \operatorname{Card}(\mathbb B) - \operatorname{Card} (\mathbb A \cap \mathbb B )} \, , $$ здесь $ \operatorname{Card}( \cdot ) $ — мощность множества. По определению $ J(\mathbb A,\mathbb B) \in [0,1] $. Очевидно, $ J(\mathbb A, \mathbb B)=0 $ если $\mathbb A \cap \mathbb B =\emptyset $ и $ J(\mathbb A,\mathbb B)=1 $ если $ \mathbb A= \mathbb B$.

Расстоянием Жаккара между множествами $ \mathbb A $ и $ \mathbb B $ называется $$ d_J(\mathbb A,\mathbb B)=1- J(\mathbb A,\mathbb B) = \frac{ \operatorname{Card} (\mathbb A \cup \mathbb B )- \operatorname{Card}( \mathbb A \cap \mathbb B )}{ \operatorname{Card}(\mathbb A \cup \mathbb B )} \, . $$

Задача. Для больших множеств $ \mathbb A $ и $ \mathbb B $ оценить $ J(\mathbb A, \mathbb B) $ косвенным образом, т.е. без вычисления точных значений мощностей объединения и пересечения.

Решение задачи посредством алгоритма MinHash (или min-wise локально-чувствительной схемы хеширования с независимыми перестановками). Пусть $ h $ псевдослучайная хеш-функция, определенная на элементах множества $ \mathbb U $ и отображающая это множество во множество целых чисел: $$ h: \mathbb U \to \mathbb Z \, . $$ Пусть эта функция не имеет коллизий на $ \mathbb U $: $ h(x_1)\ne h(x_2) $ при $ \forall \{x_1,x_2\} \subset \mathbb U, x_1 \ne x_2$. Для непустого подмножества $ \mathbb S \subset \mathbb U $ обозначим $$ h_{min} (\mathbb S) $$ элемент множества $ \mathbb S $ с минимальным значением $ h(x) $. Если $$ h_{min} (\mathbb A) = h_{min} (\mathbb B) \ , $$ то, очевидно, $ \mathbb A $ и $ \mathbb B $ имеют общий элемент. Если же $ h_{min} (\mathbb A) \ne h_{min} (\mathbb B) $, то возможно, что $ \mathbb A \cap \mathbb B $ непусто. Тем не менее, утверждается, что справедлив следующий результат.

Теорема. Имеет место равенство

$$ \operatorname{Pr} [ h_{min} (\mathbb A) = h_{min} (\mathbb B) ] = J(\mathbb A, \mathbb B) \, . $$

Исходя из этой теоремы, предлагается сравнивать сходство множеств на основе их отпечатков²⁾, т.е. значений $ h_{min} $. На практике же, для больших множеств $ \mathbb A $ и $ \mathbb B $ вычислять отпечатки некоторого количества их, сравнительно небольших, подмножеств. Фиксируем $ k \in \mathbb N $, пусть $ \operatorname{Card} (\mathbb S) \ge k $. Обозначим $ h_{(k)}(\mathbb S) $ подмножество из $ k $ элементов из $ \mathbb S $ с минимальными значениями $ h $. Это множество используется как отпечаток множества $ \mathbb S $, и сходство двух множеств оценивается сравнением их отпечатков. Так, для множеств $ \mathbb A $ и $ \mathbb B $ составляем два множества $$ \mathbb X:=h_{(k)}(h_{(k)}(\mathbb A)\cup h_{(k)}(\mathbb B)) \quad \mbox{и} \quad \mathbb Y:= \mathbb X \cap h_{(k)}(\mathbb A) \cap h_{(k)}(\mathbb B) \, . $$ Для случайной функции $ h $ множество $ \mathbb X $ — случайная выборка из $ k $ элементов из $ \mathbb A\cup \mathbb B $, а $\mathbb Y $ — подмножество множества $\mathbb X $, содержащее элементы из $\mathbb A \cap \mathbb B $. Таким образом, $$ \operatorname{Card}(\mathbb Y) / k $$ — несмещенная оценка для $ J(\mathbb A,\mathbb B) $.