YaChudo

MinHash

Переглядів: 0. Оновлено 14.11.2026.

У комп'ютерних науках і інтелектуальному аналізі даних MinHash (також відомий як схема локально-чутливого хешування на основі перестановок із мінімальною незалежністю) — це метод швидкого оцінювання подібності двох множин. Метод опублікував Андрій Бродер на конференції 1997 року.[1] Спочатку його використовували в пошуковій системі AltaVista для виявлення дублікатів вебсторінок і вилучення їх із результатів пошуку.[2] Також MinHash застосовують у масштабних задачах кластеризації, зокрема для групування документів за подібністю множин слів, які в них містяться.[1]

Подібність за Жаккаром і мінімальні хеш-значення

Коефіцієнт подібності Жаккара — поширений показник подібності двох множин. Нехай U — деяка множина, а A і B — її підмножини. Тоді індекс Жаккара визначається як відношення кількості елементів їхнього перетину до кількості елементів їхнього об'єднання:

J(A,B)=|A∩B||A∪B|.

Це значення дорівнює 0, якщо множини не мають спільних елементів, і 1, якщо вони рівні. В інших випадках воно перебуває строго між 0 і 1. Що ближче індекс Жаккара до 1, то більш подібними є множини, тобто то більшу частку їхніх елементів вони мають спільною. Мета MinHash — швидко оцінити J(A,B), не обчислюючи безпосередньо перетин і об'єднання множин.

Нехай h — хеш-функція, яка відображає елементи U у різні цілі числа, а perm — випадкова перестановка елементів множини U. Для будь-якої підмножини S множини U визначимо hmin(S) як мінімальний елемент S відповідно до композиції функцій h ∘ perm. Іншими словами, це елемент x множини S, для якого значення h(perm(x)) є найменшим. Якщо використана хеш-функція вважається такою, що має псевдовипадкові властивості, випадкову перестановку можна не застосовувати.

Застосуємо hmin до множин A і B. За умови відсутності колізій хеш-значень їхні результати будуть однаковими (hmin(A) = hmin(B)) тоді й лише тоді, коли серед усіх елементів A∪B елемент із найменшим хеш-значенням належить перетину A∩B. Імовірність цієї події точно дорівнює індексу Жаккара. Отже:

Pr⁡[hmin(A)=hmin(B)]=J(A,B).

Тобто за умови вибору perm з рівномірного розподілу ймовірність рівності hmin(A) та hmin(B) дорівнює подібності J(A,B).

Інакше кажучи, нехай r — випадкова величина, яка дорівнює 1, якщо hmin(A) = hmin(B), і 0 в іншому випадку. Тоді r є незміщеною оцінкою J(A,B). Однак сама по собі r має надто велику дисперсію, щоб бути корисною оцінкою подібності Жаккара, оскільки вона завжди дорівнює лише 0 або 1. Ідея MinHash полягає в зменшенні цієї дисперсії шляхом усереднення кількох випадкових величин, побудованих аналогічним способом.

Алгоритм

Варіант із багатьма хеш-функціями

Найпростіша версія MinHash використовує k різних хеш-функцій, де k — фіксований цілий параметр. Кожна множина S представляється набором із k значень hmin(S), обчислених за допомогою цих хеш-функцій.

Щоб оцінити J(A,B) за допомогою цього варіанта, нехай y — кількість хеш-функцій, для яких виконується рівність hmin(A) = hmin(B). Тоді як оцінку використовують відношення y/k.

Ця оцінка є середнім арифметичним k різних випадкових величин, кожна з яких дорівнює 1, коли мінімальні хеш-значення двох множин збігаються, і 0 в іншому випадку. Кожна з цих величин є незміщеною оцінкою J(A,B), а отже, їхнє середнє також є незміщеною оцінкою. Згідно зі стандартними оцінками для сум випадкових величин, які набувають значень 0 або 1, очікувана похибка має порядок O(1/√k).[3]

Таким чином, для будь-якого сталого ε > 0 існує стала k = O(1/ε2), за якої очікувана похибка оцінки не перевищує ε. Наприклад, для оцінювання J(A,B) з очікуваною похибкою не більш як 0,05 потрібно 400 хеш-функцій.

Варіант з однією хеш-функцією

Обчислення кількох хеш-функцій може бути обчислювально витратним. Пов'язаний варіант MinHash дає змогу уникнути цих витрат, використовуючи лише одну хеш-функцію. Замість одного мінімального значення для кожної функції вона вибирає кілька елементів із кожної множини.

Нехай h — хеш-функція, а k — фіксоване ціле число. Якщо множина S містить щонайменше k значень із області визначення h, визначимо h(k)(S) як підмножину з k елементів S, які мають найменші значення хеш-функції h. Цю підмножину використовують як *сигнатуру* множини 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.[1]

Урахування ваг елементів

Розроблено кілька методів урахування ваг елементів під час обчислення MinHash. Найпростіший із них поширює алгоритм на цілі ваги.[4]

Для цього хеш-функцію h розширюють так, щоб вона приймала як аргументи елемент множини та ціле число. Потім для кожного елемента генерують кілька хеш-значень відповідно до його ваги. Якщо елемент i зустрічається n разів, генерують хеш-значення:

h(i,1),h(i,2),…,h(i,n).

Після цього початковий алгоритм застосовують до розширеної множини хеш-значень. У результаті ймовірність колізії дорівнює зваженому індексу Жаккара:

J𝒲(x,y)=∑imin⁡(xi,yi)∑imax⁡(xi,yi).

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

Інше сімейство розширень використовує хеш-значення з експоненційним розподілом. Рівномірно випадкове хеш-значення між 0 і 1 можна перетворити на величину з експоненційним розподілом за допомогою обернення функції розподілу (CDF). Цей метод використовує властивості мінімуму набору експоненційно розподілених випадкових величин.

H(x)=argmini−log⁡(h(i))xi.

У цьому випадку ймовірність колізії відповідає індексу подібності Жаккара для ймовірнісних розподілів:[7]

J𝒫(x,y)=∑xi≠0yi≠01∑jmax⁡(xjxi,yjyi).

Перестановки з мінімальною незалежністю

Для реалізації описаної вище схеми MinHash хеш-функція h має визначати випадкову перестановку n елементів, де n — загальна кількість різних елементів в об'єднанні всіх порівнюваних множин. Однак існує n! різних перестановок, тому для задання справді випадкової перестановки потрібно щонайменше Ω(n log n) бітів. Навіть для помірних значень n це надто велика кількість.

З цієї причини, за аналогією з теорією універсального хешування, значні зусилля було спрямовано на пошук сімейств перестановок із властивістю мінімальної незалежності (min-wise independence). Це означає, що для будь-якої підмножини області визначення кожен її елемент має однакову ймовірність стати мінімальним.

Було доведено, що сімейство перестановок із мінімальною незалежністю повинно містити щонайменше

lcm⁡(1,2,⋯,n)≥en−o(n)

різних перестановок. Отже, для задання однієї перестановки все одно потрібно щонайменше Ω(n) бітів, що залишається практично неприйнятним обсягом.[2]

Практичні хеш-функції з мінімальною незалежністю

Через описану вище непрактичність було запропоновано два різновиди поняття мінімальної незалежності: сімейства перестановок з обмеженою мінімальною незалежністю та сімейства з наближеною мінімальною незалежністю.

Обмежена мінімальна незалежність означає, що властивість мінімальної незалежності виконується лише для певних множин, потужність яких не перевищує k.[8]

Наближена мінімальна незалежність допускає, що ймовірність відхилення від повної незалежності не перевищує заданого сталого значення ε.[9]

У 1999 році Пйотр Індик довів,[10] що будь-яке сімейство хеш-функцій із k-кратною незалежністю також є сімейством із наближеною мінімальною незалежністю, якщо k достатньо велике.

Зокрема, існують сталі c,c′>0, такі що за умови

k≥clog⁡1ϵ

виконується:

Prh∈ℋ[h(x)<min⁡h(X)]=1|X|+1(1±ϵ),

для всіх множин, для яких |X|≤ϵnc′, і всіх x∉X.

Тут запис (1±ϵ) означає, що ймовірність може бути не більшою за множник 1+ϵ від заданого значення і не меншою за множник 1−ϵ від нього.

Ця гарантія, зокрема, достатня для забезпечення межі індексу Жаккара, необхідної алгоритму MinHash. Тобто для множин A і B виконується:

Prh∈ℋ[min⁡h(A)=min⁡h(B)]=|A∩B||A∪B|±ϵ.

Оскільки хеш-функції з k-кратною незалежністю можна задати лише за допомогою k log n бітів, цей підхід є значно практичнішим за використання повністю мінімально незалежних перестановок.

Іншим практичним сімейством хеш-функцій, яке забезпечує наближену мінімальну незалежність, є табуляційне хешування.

Застосування

Початковими сферами застосування MinHash були кластеризація документів і вилучення майже однакових вебдокументів із результатів пошуку. Документи в цьому випадку представляли у вигляді множин слів, які в них зустрічаються.[1][2][11]

Подібні методи також використовують для кластеризації та виявлення майже однакових об'єктів інших типів, наприклад зображень. Зображення можна представити як множину менших фрагментів, вирізаних із нього, або як набір складніших описів ознак зображення.[12]

В інтелектуальному аналізі даних Cohen, Datar, Fujiwara, Gionis та інші (2001) використовували MinHash для навчання асоціативних правил.[13] Для цього вони розглядали базу даних, у якій кожен запис має кілька атрибутів. Таку базу можна подати у вигляді бінарної матриці (0–1), де кожен рядок відповідає запису бази даних, а кожен стовпець — атрибуту. Використовуючи наближені значення індексу Жаккара, отримані за допомогою MinHash, дослідники визначали пари атрибутів, які часто трапляються разом. Після цього точне значення індексу обчислювали лише для відібраних пар, щоб визначити ті з них, частота спільної появи яких перевищувала заданий поріг.

Алгоритм MinHash було адаптовано для біоінформатики, де задача порівняння геномних послідовностей має теоретичну основу, подібну до порівняння вебдокументів. Інструменти на основі MinHash[14][15] дають змогу швидко порівнювати дані секвенування цілого геному з референтними геномами. Наприклад, порівняння одного геному з 90 000 референтних геномів у базі RefSeq може тривати близько трьох хвилин. Такі інструменти придатні для визначення видів і, можливо, для обмеженого рівня підтипування мікроорганізмів.

MinHash також застосовують у метагеноміці[14] та в алгоритмах вирівнювання й складання геномів.[16] Алгоритми на основі MinHash також дають змогу ефективно обчислювати точні значення середньої нуклеотидної ідентичності (ANI).[17]

Інші застосування

Схему MinHash можна розглядати як окремий випадок локально-чутливого хешування — сукупності методів, які використовують хеш-функції для відображення великих наборів об'єктів у менші хеш-значення таким чином, щоб об'єкти з малою відстанню між ними з високою ймовірністю отримували однакові хеш-значення. У випадку MinHash сигнатуру множини можна розглядати як її хеш-значення.

Існують й інші методи локально-чутливого хешування, призначені для відстані Геммінга між множинами та косинусної відстані між векторами. Локально-чутливе хешування має важливе значення для алгоритмів пошуку найближчих сусідів.[18]

Для великих розподілених систем, зокрема MapReduce, розроблено модифіковані версії MinHash, які дають змогу обчислювати подібність без залежності від розмірності точок даних.[19]

Оцінювання та порівняльні випробування

У 2006 році Google провела масштабне дослідження, у якому порівнювала продуктивність алгоритмів MinHash і SimHash для виявлення майже однакових вебсторінок.[20][21]

У 2007 році Google повідомила про використання SimHash для виявлення дублікатів під час сканування вебсторінок.[22] Того ж року було опубліковано відомості про використання MinHash і локально-чутливого хешування для персоналізації Google Новин.[23]

Див. також

Примітки

  1. ↑ а б в г Broder, Andrei Z. (1998), On the resemblance and containment of documents, Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171) (PDF), IEEE, с. 21—29, doi:10.1109/SEQUEN.1997.666900, ISBN 978-0-8186-8132-5, S2CID 11748509, архів оригіналу (PDF) за 31 січня 2015, процитовано 18 січня 2014.
  2. ↑ а б в Broder, Andrei Z.; Charikar, Moses; Frieze, Alan M.; Mitzenmacher, Michael (1998), Min-wise independent permutations, Proc. 30th ACM Symposium on Theory of Computing (STOC '98), New York, NY, USA: Association for Computing Machinery, с. 327—336, doi:10.1145/276698.276781, ISBN 978-0-89791-962-3, S2CID 465847.
  3. ↑ Vassilvitskii, Sergey (2011), COMS 6998-12: Dealing with Massive Data (lecture notes, Columbia university) (PDF), архів оригіналу (PDF) за 24 жовтня 2018.
  4. ↑ Chum, Ondrej; Philbin, James; Zisserman, Andrew (2008), Near Duplicate Image Detection: min-Hash and tf-idf Weighting. (PDF), BMVC, 810: 812—815.
  5. ↑ Shrivastava, Anshumali (2016), Exact weighted minwise hashing in constant time, arXiv:1602.08393 [cs.DS]
  6. ↑ Ioffe, Sergey (2010). Improved Consistent Sampling, Weighted Minhash and L1 Sketching. 2010 IEEE International Conference on Data Mining (PDF). с. 246—255. doi:10.1109/ICDM.2010.80. ISBN 978-1-4244-9131-5. S2CID 9970906..
  7. ↑ Moulton, Ryan; Jiang, Yunjiang (2018), Maximally Consistent Sampling and the Jaccard Index of Probability Distributions, 2018 IEEE International Conference on Data Mining (ICDM), с. 347—356, arXiv:1809.04052, doi:10.1109/ICDM.2018.00050, ISBN 978-1-5386-9159-5, S2CID 49746072.
  8. ↑ Matoušek, Jiří; Stojaković, Miloš (2003), On restricted min-wise independence of permutations, Random Structures and Algorithms, 23 (4): 397—408, doi:10.1002/rsa.10101, S2CID 1483449.
  9. ↑ Saks, M.; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000), Low discrepancy sets yield approximate min-wise independent permutation families, Information Processing Letters, 73 (1—2): 29—32, doi:10.1016/S0020-0190(99)00163-5.
  10. ↑ Indyk, Piotr. "A small approximately min-wise independent family of hash functions." Journal of Algorithms 38.1 (2001): 84–90.
  11. ↑ Manasse, Mark (2012). On the Efficient Determination of Most Near Neighbors: Horseshoes, Hand Grenades, Web Search, and Other Situations when Close is Close Enough. Morgan & Claypool. с. 72. ISBN 978-1-60845-088-6..
  12. ↑ Chum, Ondřej; Philbin, James; Isard, Michael; Zisserman, Andrew (2007), Scalable near identical image and shot detection, Proceedings of the 6th ACM International Conference on Image and Video Retrieval (CIVR'07), с. 549—556, doi:10.1145/1282280.1282359, ISBN 978-1-59593-733-9, S2CID 3330908; Chum, Ondřej; Philbin, James; Zisserman, Andrew (2008), Near duplicate image detection: min-hash and tf-idf weighting, Proceedings of the British Machine Vision Conference (PDF), т. 3, с. 4.
  13. ↑ Cohen, E.; Datar, M.; Fujiwara, S.; Gionis, A.; Indyk, P.; Motwani, R.; Ullman, J. D.; Yang, C. (2001), Finding interesting associations without support pruning, IEEE Transactions on Knowledge and Data Engineering, 13 (1): 64—78, Bibcode:2001IDSO...13...64C, doi:10.1109/69.908981.
  14. ↑ а б Ondov, Brian D.; Treangen, Todd J.; Melsted, Páll; Mallonee, Adam B.; Bergman, Nicholas H.; Koren, Sergey; Phillippy, Adam M. (20 червня 2016). Mash: fast genome and metagenome distance estimation using MinHash. Genome Biology. 17 (1): 132. doi:10.1186/s13059-016-0997-x. ISSN 1474-760X. PMC 4915045. PMID 27323842.
  15. ↑ Welcome to sourmash! — sourmash 1.0 documentation. sourmash.readthedocs.io (англ.). Процитовано 13 листопада 2017..
  16. ↑ Berlin, Konstantin; Koren, Sergey; Chin, Chen-Shan; Drake, James P; Landolin, Jane M; Phillippy, Adam M (25 травня 2015). Assembling large genomes with single-molecule sequencing and locality-sensitive hashing. Nature Biotechnology (англ.). 33 (6): 623—630. Bibcode:2015NatBi..33..623B. doi:10.1038/nbt.3238. ISSN 1546-1696. PMID 26006009. S2CID 17246729..
  17. ↑ Jain, Chirag; Rodriguez-R, Luis M.; Phillippy, Adam M.; Konstantinidis, Konstantinos T.; Aluru, Srinivas (Грудень 2018). High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundaries. Nature Communications. 9 (1): 5114. Bibcode:2018NatCo...9.5114J. doi:10.1038/s41467-018-07641-9. PMC 6269478. PMID 30504855..
  18. ↑ Andoni, Alexandr; Indyk, Piotr (2008), Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Communications of the ACM, 51 (1): 117—122, doi:10.1145/1327452.1327494, S2CID 6468963.
  19. ↑ Zadeh, Reza; Goel, Ashish (2012), Dimension Independent Similarity Computation, arXiv:1206.2082 [cs.DS].
  20. ↑ Henzinger, Monika (2006), Finding near-duplicate web pages: a large-scale evaluation of algorithms, Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, с. 284, doi:10.1145/1148170.1148222, ISBN 978-1-59593-369-0, S2CID 207160068.
  21. ↑ Charikar, Moses S. (2002), Similarity estimation techniques from rounding algorithms, Proceedings of the 34th Annual ACM Symposium on Theory of Computing, с. 380—388, doi:10.1145/509907.509965, ISBN 978-1-58113-495-7, S2CID 4229473.
  22. ↑ Gurmeet Singh, Manku; Jain, Arvind; Das Sarma, Anish (2007), Detecting near-duplicates for web crawling, Proceedings of the 16th International Conference on World Wide Web (PDF), с. 141, doi:10.1145/1242572.1242592, ISBN 978-1-59593-654-7, S2CID 1414324.
  23. ↑ Das, Abhinandan S.; Datar, Mayur; Garg, Ashutosh; Rajaram, Shyam та ін. (2007), Google news personalization: scalable online collaborative filtering, Proceedings of the 16th International Conference on World Wide Web, с. 271, doi:10.1145/1242572.1242610, ISBN 978-1-59593-654-7, S2CID 207163129.

Джерело: стаття у Вікіпедії та історія редагувань (автори).