Войти
В информатике и интеллектуальном анализе данных, MinHash (или минимальные независимые перестановки схема хеширования с учетом местоположения ) - это метод быстрой оценки схожести двух наборов. Схема была изобретена Андреем Бродером (1997) и первоначально использовалась в поисковой системе AltaVista для обнаружения повторяющихся веб-страниц и исключения их из результатов поиска. Он также применялся в крупномасштабных задачах кластеризации, таких как кластеризация документов по схожести их наборов слов.
Коэффициент сходства по Жаккару - часто используемый индикатор схожести двух наборов. Пусть U - множество, а A и B - подмножества U, тогда индекс Жаккара определяется как отношение количества элементов их пересечения и количества элементов их объединения :
Это значение равно 0, когда два набора не пересекаются, 1, когда они равны, и строго между 0 и 1 в противном случае. Два набора более похожи (то есть имеют относительно больше общих членов), когда их индекс Жаккара ближе к 1. Цель MinHash - быстро оценить J (A, B), без явного вычисления пересечения и объединения.
Пусть h будет хэш-функцией, которая отображает элементы U в различные целые числа, пусть perm будет случайной перестановкой элементов множества U, а для любое множество S определяет h min (S) как минимальный член S относительно h ∘ perm, то есть член x из S с минимальным значением h (perm (x)). (В случаях, когда предполагается, что используемая хеш-функция имеет псевдослучайные свойства, случайная перестановка не будет использоваться.)
Теперь, применяя h min как к A, так и к B, и предполагая отсутствие хеш-коллизий, мы видим, что значения равны (h min (A) = h min (B)) тогда и только тогда, когда среди всех элементов 
То есть вероятность того, что h min (A) = h min (B) истинно, равна подобию J (A, Б), предполагая нанесение химической завивки из равномерного распределения. Другими словами, если r является случайной величиной, которая равна единице, когда h min (A) = h min (B), и нулю в противном случае, тогда r равно несмещенная оценка J (A, B). r имеет слишком высокую дисперсию, чтобы быть полезной оценкой сходства Жаккара, потому что 
В простейшей версии схемы minhash используются k различных хэш-функций, где k - фиксированный целочисленный параметр, и представляет каждый набор S значениями k h min (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 / ε) такая, что ожидаемая ошибка оценки не превосходит ε. Например, для оценки J (A, B) с ожидаемой ошибкой, меньшей или равной 0,05, потребуется 400 хешей.
Вычисление нескольких хэш-функций может быть дорогостоящим в вычислительном отношении, но связанная версия схемы 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.
Разнообразные методы введения весов в вычисление MinHash было развито. Самый простой расширяет его до целых весов. Расширьте нашу хеш-функцию h, чтобы она могла принимать как член набора, так и целое число, а затем сгенерируйте несколько хешей для каждого элемента в соответствии с его весом. Если элемент i встречается n раз, сгенерировать хэши 
Дополнительные расширения, которые позволяют достичь этой вероятности столкновения на реальных весах с лучшим временем выполнения, одно для плотных данных, а другое для разреженных данных.
Другое семейство расширений использует экспоненциально распределенные хэши. Равномерно случайный хэш от 0 до 1 может быть преобразован в экспоненциальное распределение с помощью инверсии CDF. Этот метод использует множество прекрасных свойств минимума набора экспоненциальных переменных.
Это дает в качестве вероятности столкновения вероятность Жаккара индекс
Для реализации схемы MinHash, как описано выше, требуется хэш-функция h для определения случайной перестановки на n элементах, где n - общее количество различных элементов в объединении всех сравниваемых наборов. Но ведь их нет! различных перестановок, потребовалось бы Ω (n log n) бит только для указания действительно случайной перестановки, недопустимо большого числа даже для умеренных значений n. Из-за этого факта, по аналогии с теорией универсального хеширования, была проделана значительная работа по поиску семейства перестановок, которое "не зависит от минимума", что означает, что для любого подмножества домена любой элемент с одинаковой вероятностью будет минимальным. Было установлено, что минимально независимое семейство перестановок должно включать не менее
различных перестановок, и поэтому для указания одной перестановки требуется Ω (n) битов, что все еще недопустимо велико.
Потому что Из-за этой непрактичности были введены два варианта понятия минимальной независимости: ограниченные минимально независимые семейства перестановок и приблизительные минимально независимые семейства. Ограниченная минимальная независимость - это свойство минимальной независимости, ограниченное некоторыми наборами мощности не более k. Приблизительная минимальная независимость имеет не более фиксированной вероятности ε отклонения от полной независимости.
Исходные приложения для MinHash включали кластеризацию и устранение почти дубликатов среди веб-документов, представленных в виде наборов слов, встречающихся в этих документах. Подобные методы также использовались для кластеризации и почти полного исключения дубликатов для других типов данных, таких как изображения: в случае данных изображения изображение может быть представлено как набор меньших фрагментов изображения, вырезанных из него, или как наборы большего количества описания сложных изображений.
В интеллектуальном анализе данных, Cohen et al. (2001) использовать MinHash как инструмент для изучения правил ассоциации. Учитывая базу данных, в которой каждая запись имеет несколько атрибутов (рассматриваемая как 0–1 матрица со строкой для каждой записи в базе данных и столбцом для каждого атрибута), они используют приближения на основе MinHash к индексу Жаккарда для определения пар кандидатов. атрибутов, которые часто встречаются одновременно, а затем вычисляют точное значение индекса только для этих пар, чтобы определить те, частота совпадения которых ниже заданного строгого порога.
Алгоритм MinHash был адаптирован для биоинформатики, где проблема сравнения последовательностей геномов имеет те же теоретические основания, что и сравнение документов в сети. Инструменты на основе MinHash позволяют быстро сравнивать данные секвенирования всего генома с эталонными геномами (около 3 минут для сравнения одного генома с 90000 эталонными геномами в RefSeq ) и подходят для видообразования и, возможно, ограниченной степени микробной подтип. Существуют также приложения для метагеномики и использования алгоритмов, полученных из MinHash, для выравнивания генома и сборки генома.
Схема MinHash может рассматриваться как пример хеширования с учетом местоположения, набор методов использования хэш-функций для преобразования больших наборов объектов в меньшие хеш-значения таким образом, чтобы, когда два объекта находятся на небольшом расстоянии друг от друга, их хеш-значения, вероятно, будут одинаковыми. В этом случае подпись набора может рассматриваться как его хеш-значение. Для расстояния Хэмминга между наборами и косинусного расстояния между векторами существуют другие методы хеширования, чувствительные к локальности; Хеширование с учетом местоположения имеет важные приложения в алгоритмах поиска ближайшего соседа. Для больших распределенных систем, и в частности MapReduce, существуют модифицированные версии MinHash, которые помогают вычислять сходства без зависимости от размерности точки.
A В 2006 г. компанией Google была проведена крупномасштабная оценка для сравнения производительности алгоритмов Minhash и SimHash. В 2007 году Google сообщил об использовании Simhash для обнаружения дубликатов при сканировании Интернета, а также об использовании Minhash и LSH для персонализации Google News.
