MinHash - Википедия - MinHash

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

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

В Коэффициент подобия Жаккара - часто используемый индикатор схожести двух наборов. Позволять U быть набором и А и B быть подмножествами U, то индекс Жаккара определяется как отношение количества элементов их пересечение и количество элементов их союз:

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

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

Теперь, применяя часмин как для А и B, и при условии отсутствия хеш-коллизий мы видим, что значения равны (часмин(А) = часмин(B)) тогда и только тогда, когда среди всех элементов , элемент с минимальным хеш-значением лежит в пересечении . Вероятность того, что это правда, и есть индекс Жаккара, поэтому:

Pr [ часмин(А) = часмин(B) ] = J(А,B),

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

Алгоритм

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

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

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

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

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

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

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

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

Анализ времени

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

Добавление весов

Были разработаны различные методы введения весов в вычисление MinHash. Самый простой расширяет его до целых весов.[4]Расширьте нашу хеш-функцию час чтобы принять как член набора, так и целое число, а затем сгенерировать несколько хешей для каждого элемента в соответствии с его весом. Если элемент я происходит п раз генерировать хеши . Запустите исходный алгоритм на этом расширенном наборе хешей. Это дает взвешенный индекс Жаккара как вероятность столкновения.

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

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

Это дает в качестве вероятности столкновения вероятность индекса Жаккара[7]

Минимальные независимые перестановки

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

разные перестановки, и поэтому это необходимо Ω (п) биты для указания единственной перестановки, все еще недопустимо большой.[2]

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

Приложения

Оригинальные приложения для MinHash включали кластеризацию и устранение почти дубликатов среди веб-документов, представленных в виде наборов слов, встречающихся в этих документах.[1][2][10] Аналогичные методы также использовались для кластеризации и почти полного устранения дубликатов для других типов данных, таких как изображения: в случае данных изображения изображение может быть представлено как набор меньших фрагментов изображения, вырезанных из него, или как наборы большего количества сложные описания характеристик изображения.[11]

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

Алгоритм MinHash был адаптирован для биоинформатики, где проблема сравнения последовательностей геномов имеет те же теоретические основания, что и сравнение документов в сети. Инструменты на основе MinHash[13][14] позволяют быстро сравнивать данные секвенирования всего генома с эталонными геномами (около 3 минут для сравнения одного генома с 90000 эталонными геномами в RefSeq ) и подходят для видообразования и, возможно, с ограниченной степенью микробного подтипирования. Также есть приложения для метагеномики [13] и использование алгоритмов, полученных из MinHash, для выравнивания генома и сборки генома.[15]

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

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

Оценка и контрольные показатели

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

Смотрите также

Рекомендации

  1. ^ а б c d Бродер, Андрей З. (1997), «О сходстве и содержании документов», Сжатие и сложность последовательностей: материалы, Позитано, Амальфитанское побережье, Салерно, Италия, 11-13 июня 1997 г. (PDF), IEEE, стр. 21–29, CiteSeerX  10.1.1.24.779, Дои:10.1109 / SEQUEN.1997.666900, ISBN  978-0-8186-8132-5, заархивировано из оригинал (PDF) на 2015-01-31, получено 2014-01-18.
  2. ^ а б c Бродер, Андрей З.; Чарикар, Моисей; Frieze, Алан М.; Митценмахер, Майкл (1998), "Независимые перестановки по минимуму", Proc. 30-й симпозиум ACM по теории вычислений (STOC '98), Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники, стр. 327–336, CiteSeerX  10.1.1.409.9220, Дои:10.1145/276698.276781, ISBN  978-0897919623.
  3. ^ Васильвицкий, Сергей (2011), COMS 6998-12: Работа с массивными данными (конспект лекций, Колумбийский университет) (PDF), заархивировано из оригинал (PDF) на 2018-10-24.
  4. ^ Чум, Ондрей; Филбин, Джеймс; Зиссерман, Андрей (2008), «Обнаружение почти повторяющихся изображений: минимальный хэш и tf-idf взвешивание». (PDF), BMVC, 810: 812–815
  5. ^ Шривастава, Аншумали (2016), «Точное взвешенное минимальное хеширование за постоянное время», arXiv:1602.08393 [cs.DS ]
  6. ^ Иоффе, Сергей (2010), «Улучшенная последовательная выборка, взвешенный минхеш и создание эскизов l1» (PDF), Data Mining (ICDM), 10-я Международная конференция IEEE 2010 г.: 246–255, CiteSeerX  10.1.1.227.9749, Дои:10.1109 / ICDM.2010.80, ISBN  978-1-4244-9131-5
  7. ^ Моултон, Райан; Цзян, Юньцзян (2018 г.), «Максимально согласованная выборка и индекс вероятностных распределений Жаккара», Международная конференция IEEE по интеллектуальному анализу данных (ICDM) 2018 г., стр. 347–356, arXiv:1809.04052, Дои:10.1109 / ICDM.2018.00050, ISBN  978-1-5386-9159-5
  8. ^ Матушек, Иржи; Стоякович, Милош (2003), «Об ограниченной минимальной независимости перестановок», Случайные структуры и алгоритмы, 23 (4): 397–408, CiteSeerX  10.1.1.400.6757, Дои:10.1002 / rsa.10101.
  9. ^ Сакс, М.; Srinivasan, A .; Чжоу, S .; Цукерман, Д. (2000), "Множества с низким расхождением дают приблизительные, по минимуму, независимые семейства перестановок", Письма об обработке информации, 73 (1–2): 29–32, CiteSeerX  10.1.1.20.8264, Дои:10.1016 / S0020-0190 (99) 00163-5.
  10. ^ Манассе, Марк (2012). Об эффективном определении ближайших соседей: подковы, ручные гранаты, поиск в Интернете и другие ситуации, когда близко достаточно близко. Морган и Клейпул. п. 72. ISBN  9781608450886.
  11. ^ Чум, Ондржей; Филбин, Джеймс; Айсард, Майкл; Зиссерман, Эндрю (2007), «Масштабируемое почти идентичное изображение и обнаружение выстрелов», Материалы 6-й Международной конференции ACM по поиску изображений и видео (CIVR'07), стр. 549–556, Дои:10.1145/1282280.1282359, ISBN  9781595937339; Чум, Ондржей; Филбин, Джеймс; Зиссерман, Эндрю (2008), «Обнаружение почти повторяющихся изображений: минимальное хеширование и взвешивание tf-idf», Труды Британской конференции по машинному зрению (PDF), 3, п. 4.
  12. ^ Коэн, Э.; Датар, М .; Fujiwara, S .; Gionis, A .; Индик, П.; Мотвани, Р.; Ульман, Дж. Д.; Ян, C. (2001), «В поисках интересных ассоциаций без поддержки подрезать», IEEE Transactions по разработке знаний и данных, 13 (1): 64–78, CiteSeerX  10.1.1.192.7385, Дои:10.1109/69.908981.
  13. ^ а б Ондов, Брайан Д .; Treangen, Todd J .; Мельстед, Палл; Мэллони, Адам Б.; Бергман, Николас Х .; Корень, Сергей; Филлиппи, Адам М. (2016-06-20). «Mash: быстрая оценка расстояния между геномом и метагеномом с использованием MinHash». Геномная биология. 17 (1): 132. Дои:10.1186 / s13059-016-0997-х. ISSN  1474-760X. ЧВК  4915045. PMID  27323842.
  14. ^ «Добро пожаловать в sourmash! - документация sourmash 1.0». sourmash.readthedocs.io. Получено 2017-11-13.
  15. ^ Берлин, Константин; Корень, Сергей; Чин, Чен-Шань; Дрейк, Джеймс П. Ландолин, Джейн М; Филлиппи, Адам М (25 мая 2015 г.). «Сборка больших геномов с помощью секвенирования одной молекулы и хеширования с учетом локализации». Природа Биотехнологии. 33 (6): 623–630. Дои:10.1038 / nbt.3238. ISSN  1546-1696. PMID  26006009.
  16. ^ Андони, Александр; Индик, Петр (2008), «Почти оптимальные алгоритмы хеширования для приближенного ближайшего соседа в больших измерениях», Коммуникации ACM, 51 (1): 117–122, CiteSeerX  10.1.1.226.6905, Дои:10.1145/1327452.1327494.
  17. ^ Заде, Реза; Гоэль, Ашиш (2012), «Вычисление подобия, не зависящее от размерности», arXiv:1206.2082 [cs.DS ].
  18. ^ Хенцингер, Моника (2006), "Поиск почти дублирующихся веб-страниц: широкомасштабная оценка алгоритмов", Материалы 29-й ежегодной международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска, стр.284, Дои:10.1145/1148170.1148222, ISBN  978-1595933690.
  19. ^ Чарикар, Моисей С. (2002), "Методы оценки подобия на основе алгоритмов округления", Материалы 34-го ежегодного симпозиума ACM по теории вычислений, п. 380, Дои:10.1145/509907.509965, ISBN  978-1581134957.
  20. ^ Гурмит Сингх, Манку; Джайн, Арвинд; Дас Сарма, Аниш (2007), «Обнаружение почти дубликатов для сканирования Интернета», Материалы 16-й Международной конференции по всемирной паутине (PDF), п. 141, Дои:10.1145/1242572.1242592, ISBN  9781595936547.
  21. ^ Das, Abhinandan S .; Датар, Маюр; Гарг, Ашутош; Раджарам, Шьям; и другие. (2007), "Персонализация новостей Google: масштабируемая совместная фильтрация в Интернете", Материалы 16-й Международной конференции по всемирной паутине, п. 271, Дои:10.1145/1242572.1242610, ISBN  9781595936547.