Минхеш

В информатике и анализе данных интеллектуальном MinHash (или минимальная схема хеширования с независимыми перестановками, чувствительной к локальности ) — это метод быстрой оценки того, насколько похожи два набора. Схему придумал Андрей Бродер ( 1997 г. ), и первоначально использовался в поисковой системе AltaVista для обнаружения дубликатов веб-страниц и исключения их из результатов поиска. Он также применялся в крупномасштабных задачах кластеризации , таких как кластеризация документов по сходству их наборов слов.

Сходство Жаккара и минимальные значения хеш-функции

Коэффициент сходства Жаккара является широко используемым индикатором сходства между двумя наборами. Пусть U — множество, а A и B — подмножества U , тогда индекс Жаккара определяется как отношение числа элементов их пересечения и числа элементов их объединения :

$J(A,B)={{|A\cap B|} \over {|A\cup B|}}.$

Это значение равно 0, когда два набора не пересекаются , 1, когда они равны, и строго между 0 и 1 в противном случае. Два набора более похожи (т.е. имеют относительно больше общих элементов), когда их индекс Жаккара близок к 1. Цель MinHash — быстро оценить J ( A , B ) без явного вычисления пересечения и объединения.

Пусть h — хеш-функция , которая отображает элементы U в различные целые числа, пусть perm — случайная перестановка элементов множества U , и для любого подмножества S из U определите h _min ( S ) как минимальный член S относительно h ∘ perm — то есть члена x из S с минимальным значением h ( perm ( x )) . (В тех случаях, когда предполагается, что используемая хеш-функция имеет псевдослучайные свойства, случайная перестановка не будет использоваться.)

Теперь, применяя h _min к A и B и предполагая отсутствие коллизий хэшей, мы видим, что значения равны ( h _min ( A ) = h _min ( B ) ) тогда и только тогда, когда среди всех элементов $A\cup B$, элемент с минимальным значением хеш-функции лежит на пересечении $A\cap B$. Вероятность того, что это правда, равна в точности индексу Жаккара, поэтому:

Pr[ час _мин ( A ) знак равно час _мин ( B ) ] знак равно J ( A , B ),

То есть вероятность того, что h _min ( A ) = h _min ( B ) истинна, равна подобию J ( A , B ) , предполагая получение пермского значения из равномерного распределения. Другими словами, если r — случайная величина , которая равна единице, когда min ₍ A ) = h _min ( B ) , и нулю в противном случае, то r является несмещенной оценкой J h ( A , B ) . r имеет слишком большую дисперсию , чтобы быть полезным средством оценки сходства Жаккара само по себе, потому что $r$ всегда равен нулю или единице. Идея схемы MinHash состоит в том, чтобы уменьшить эту дисперсию путем усреднения нескольких переменных, построенных одинаковым образом.

Алгоритм

Вариант со множеством хэш-функций

Самая простая версия схемы минхэша использует k различных хеш-функций, где — фиксированный целочисленный параметр, и представляет каждый набор S k h значений ( min _k S ) для этих k функций.

Чтобы оценить J ( A , B ) с использованием этой версии схемы, пусть y будет количеством хеш-функций, для которых h _min ( A ) = h _min ( B ) , и используйте y / k в качестве оценки. Эта оценка представляет собой среднее значение k различных случайных величин 0–1, каждая из которых равна единице, когда h _min ( A ) = h _min ( B ), и нулю в противном случае, и каждая из которых является несмещенной оценкой J ( A , B ). . Следовательно, их среднее значение также является несмещенной оценкой, и по стандартному отклонению для сумм случайных величин 0–1 его ожидаемая ошибка составляет O(1/ √ k ) .

Следовательно, для любой константы ε > 0 существует константа k = O(1/ε ² ) такой, что ожидаемая ошибка оценки не превосходит ε . потребуется 400 хэшей Например, для оценки J ( A , B ) с ожидаемой ошибкой, меньшей или равной 0,05, .

Вариант с одной хеш-функцией

Вычисление нескольких хеш-функций может оказаться затратным в вычислительном отношении, но соответствующая версия схемы MinHash позволяет избежать этого штрафа, используя только одну хэш-функцию и использует ее для выбора нескольких значений из каждого набора, а не для выбора только одного минимального значения для каждой хеш-функции. Пусть h — хеш-функция, а k — фиксированное целое число. Если S — любой набор из k или более значений в области h ,определите h _{( k )} ( S ) как подмножество k членов S , которые имеют наименьшие значения h . Это подмножество h _{( k )} ( S ) используется в качестве сигнатуры множества S , а сходство любых двух наборов оценивается путем сравнения их сигнатур.

В частности, пусть A и B — любые два множества.Тогда X = h _{( k )} ( h _{( k )} ( A ) ∪ h _{( k )} ( B )) = h _{( k )} ( A ∪ B ) представляет собой набор из k элементов A ∪ B , и если h является любое подмножество из k случайная функция, то с равной вероятностью будет выбрано элементов; то есть X — случайная выборка A B ∪ . простая Подмножество Y = X ∩ h _{( k )} ( A ) ∩ h _{( k )} ( B ) является множеством членов X , которые принадлежат пересечению A ∩ B . Следовательно, | Y |/ k — несмещенная оценка J ( A , B ) . Разница между этой оценкой и оценкой, созданной с помощью нескольких хэш-функций, заключается в том, что X всегда имеет ровно k членов, тогда как множественные хеш-функции могут привести к меньшему количеству выборочных элементов из-за возможности того, что две разные хэш-функции могут иметь одинаковые минимумы. . Однако когда k мало по сравнению с размерами множеств, эта разница незначительна.

Согласно стандартным границам Чернова для выборки без замены, эта оценка имеет ожидаемую ошибку O(1/ √ k ) , что соответствует производительности схемы с несколькими хэш-функциями.

Временной анализ

Оценщик | Y |/ k можно вычислить за время O( k ) по двум сигнатурам заданных наборов в любом варианте схемы. Следовательно, когда ε и k являются константами, время вычисления предполагаемого сходства по сигнатурам также является постоянным. Сигнатура каждого набора может быть вычислена за линейное время в зависимости от размера набора, поэтому, когда необходимо оценить множество парных сходств, этот метод может привести к существенной экономии времени выполнения по сравнению с полным сравнением членов каждого набора. . В частности, для размера набора n вариант с множеством хэшей занимает время O( n k ) . Вариант с одним хэшем, как правило, быстрее, и ему требуется время O( n ) для поддержания очереди минимальных значений хеш-функции, предполагая n >> k .

Включение весов

Были разработаны различные методы введения весов в вычисление MinHashes. Самый простой расширяет его до целочисленных весов. Расширьте нашу хеш-функцию h, чтобы она могла принимать как член множества, так и целое число, а затем сгенерируйте несколько хэшей для каждого элемента в соответствии с его весом. Если элемент i встречается n раз, сгенерируйте хеши $h(i,1),h(i,2),\ldots ,h(i,n)$. Запустите исходный алгоритм на этом расширенном наборе хешей. В результате получается взвешенный индекс Жаккара как вероятность столкновения.

$J_{\mathcal {W}}(x,y)={\frac {\sum _{i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}}$

Были разработаны дополнительные расширения, которые обеспечивают эту вероятность коллизий для реальных весов с лучшим временем выполнения: одно для плотных данных, и еще один для редких данных.

Другое семейство расширений использует экспоненциально распределенные хэши. Равномерно случайный хеш от 0 до 1 может быть преобразован в экспоненциальное распределение путем инверсии CDF . Этот метод использует множество прекрасных свойств минимума набора экспоненциальных переменных .

$H(x)={\underset {i}{\operatorname {arg\,min} }}{\frac {-\log(h(i))}{x_{i}}}$

В качестве вероятности столкновения это дает вероятность индекса Жаккара.

$J_{\mathcal {P}}(x,y)=\sum _{x_{i}\neq 0 \atop y_{i}\neq 0}{\frac {1}{\sum _{j}\max \left({\frac {x_{j}}{x_{i}}},{\frac {y_{j}}{y_{i}}}\right)}}$

Независимые по минимуму перестановки

Чтобы реализовать схему MinHash, как описано выше, нужна хеш-функция h для определения случайной перестановки на n элементах, где n — общее количество различных элементов в объединении всех сравниваемых наборов. Но поскольку есть n ! различных перестановок, потребовалось бы Ω( n log n ) бит только для того, чтобы указать действительно случайную перестановку, а это невероятно большое число даже для умеренных значений n . Из-за этого факта, по аналогии с теорией универсального хеширования , была проведена значительная работа по поиску семейства перестановок, которое является «минимально независимым», что означает, что для любого подмножества области любой элемент с равной вероятностью будет минимум. Установлено, что минимально независимое семейство подстановок должно включать не менее

$\operatorname {lcm} (1,2,\cdots ,n)\geq e^{n-o(n)}$

требуется Ω( n ) бит. различные перестановки, и, следовательно, для указания одной перестановки, все еще невероятно большой,

Практические независимые хеш-функции по минимуму

Из-за вышеуказанной непрактичности были введены два варианта понятия минимальной независимости: ограниченные минимально независимые семейства перестановок и аппроксимированные минимально независимые семейства.Ограниченная минимальная независимость — это свойство минимальной независимости, ограниченное определенными наборами мощности не более k . Приблизительная минимальная независимость имеет не более фиксированной вероятности ε , отличающейся от полной независимости.

В 1999 году Петр Индик проявил себя что любое независимое по k-му семейству хеш-функций также является приблизительно независимым по min-му для $k$ достаточно большой.В частности, существуют константы $c,c'>0$ такое, что если $k\geq c\log {\tfrac {1}{\epsilon }}$, затем

$\Pr _{h\in {\mathcal {H}}}[h(x)<\min h(X)]={\frac {1}{|X|+1}}(1\pm \epsilon ),$

для всех наборов $|X|\leq \epsilon nc'$ и $x\not \in X$.(Обратите внимание, здесь $(1\pm \epsilon )$ означает, что вероятность не более чем фактор $1+\epsilon$ слишком большой и максимум $1-\epsilon$ слишком маленький.)

Эта гарантия, среди прочего, достаточна для получения оценки Жаккара, требуемой алгоритмом MinHash.То есть, если $A$ и $B$ являются множествами, то

$\Pr _{h\in {\mathcal {H}}}[\min h(A)=\min h(B)]={\frac {|A\cap B|}{|A\cup B|}}\pm \epsilon .$

Поскольку независимые хэш-функции по k можно указать, используя только $k\log n$ бит, этот подход гораздо более практичен, чем использование полностью независимых по минимуму перестановок.

Еще одно практичное семейство хэш-функций, которое дает приблизительную независимость по минимуму, — это хеширование табуляций .

Приложения

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

В области анализа данных интеллектуального Коэн и др. (2001) используют MinHash как инструмент для изучения правил ассоциации . Учитывая базу данных, в которой каждая запись имеет несколько атрибутов (рассматриваемых как матрица 0–1 со строкой на запись базы данных и столбцом на атрибут), они используют аппроксимации индекса Жаккара на основе MinHash для идентификации пар-кандидатов атрибутов, которые часто совпадают. происходят, а затем вычислить точное значение индекса только для тех пар, чтобы определить те, частота совместного появления которых ниже заданного строгого порога.

Алгоритм MinHash был адаптирован для биоинформатики, где проблема сравнения последовательностей генома имеет теоретическую основу, аналогичную проблеме сравнения документов в сети. Инструменты на основе MinHash позволяют быстро сравнивать данные полногеномного секвенирования с эталонными геномами (около 3 минут для сравнения одного генома с 90 000 эталонными геномами в RefSeq ) и подходят для видообразования и, возможно, в ограниченной степени микробного подтипирования. Есть также приложения для метагеномики. и использование алгоритмов, основанных на MinHash, для выравнивания и сборки генома. Точные значения средней идентичности нуклеотидов (ANI) можно очень эффективно генерировать с помощью алгоритмов на основе MinHash.

Другое использование

Схему MinHash можно рассматривать как пример хеширования с учетом местоположения — набора методов использования хеш-функций для сопоставления больших наборов объектов с меньшими значениями хеш-функции таким образом, что, когда два объекта находятся на небольшом расстоянии друг от друга , их хеш-значения, скорее всего, будут одинаковыми. В этом случае подпись набора можно рассматривать как его хеш-значение. Существуют и другие методы хеширования, чувствительные к местонахождению, для расстояния Хэмминга между наборами и косинусного расстояния между векторами ; Хэширование с учетом локальности имеет важные применения в алгоритмах поиска ближайших соседей . Для больших распределенных систем, в частности MapReduce , существуют модифицированные версии MinHash, помогающие вычислять сходства без зависимости от размерности точки.

Оценка и критерии

Крупномасштабная оценка была проведена Google в 2006 году. сравнить производительность Minhash и SimHash алгоритмы. В 2007 году Google сообщил об использовании Simhash для обнаружения дубликатов при сканировании веб-страниц. и использование Minhash и LSH для персонализации Новостей Google .

См. также

• Фильтр Блума – структура данных для приблизительного членства в наборе
• Эскиз «Счет-мин» - Вероятностная структура данных в информатике
• ш-черепица