MinHash - MinHash - Wikipedia

v počítačová věda a dolování dat, MinHash (nebo min. nezávislé permutace hash citlivý na lokalitu schéma) je technika pro rychlý odhad jak podobný dvě sady jsou. Schéma vynalezl Andrei Broder  (1997 ),[1] a původně použit v AltaVista vyhledávač pro detekci duplicitních webových stránek a jejich eliminaci z výsledků vyhledávání.[2] Rovněž byl použit ve velkém měřítku shlukování problémy, jako např shlukování dokumentů podobností jejich sad slov.[1]

Jaccardova podobnost a minimální hodnoty hash

The Koeficient podobnosti Jaccard je běžně používaný indikátor podobnosti mezi dvěma sadami. Nechat U být sadou a A a B být podmnožinami U, pak je Jaccardův index definován jako poměr počtu prvků jejich průsečík a počet prvků jejich svaz:

Tato hodnota je 0, pokud jsou obě sady disjunktní, 1, když jsou stejné, a jinak přísně mezi 0 a 1. Dvě sady jsou si více podobné (tj. Mají relativně více společných členů), když je jejich index Jaccard blíže k 1. Cílem MinHash je odhadnout J(A,B) rychle, bez výslovného výpočtu křižovatky a sjednocení.

Nechat h být hashovací funkce který mapuje členy U na různá celá čísla, nechť perm být náhodný permutace prvků sady Ua pro jakoukoli sadu S definovat hmin(S) být minimálním členem S s ohledem na h ∘ perm—Toto je člen X z S s minimální hodnotou h(perm(X)). (V případech, kdy se předpokládá, že použitá hashovací funkce má pseudonáhodné vlastnosti, náhodná permutace by se nepoužila.)

Nyní se přihlašuji hmin oběma A a B, a za předpokladu, že nedojde k žádné srážce hash, vidíme, že hodnoty jsou stejné (hmin(A) = hmin(B)) právě tehdy, pokud mezi všemi prvky , prvek s minimální hodnotou hash leží v průsečíku . Pravděpodobnost, že to bude pravda, je přesně index Jaccard, proto:

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

Toto je pravděpodobnost že hmin(A) = hmin(B) je pravda se rovná podobnosti J(A,B), za předpokladu kreslení perm z jednotného rozdělení. Jinými slovy, pokud r je náhodná proměnná to je jeden, když hmin(A) = hmin(B) a jinak tedy nula r je nezaujatý odhad z J(A,B). r má příliš vysokou a rozptyl být užitečným odhadcem samotné podobnosti Jaccard, protože je vždy nula nebo jedna. Myšlenkou schématu MinHash je snížit tuto odchylku průměrováním společně několika proměnných vytvořených stejným způsobem.

Algoritmus

Varianta s mnoha hashovacími funkcemi

Nejjednodušší verze minhash schématu používá k různé hashovací funkce, kde k je pevný celočíselný parametr a představuje každou sadu S podle k hodnoty hmin(S) pro tyto k funkce.

Odhadovat J(A,B) pomocí této verze schématu, let y být počet hashovacích funkcí, pro které hmin(A) = hmin(B)a použít y/k jako odhad. Tento odhad je průměrem k různé 0-1 náhodné proměnné, z nichž každá je jedna, když hmin(A) = hmin(B) a jinak nula, a každý z nich je nezaujatý odhadce J(A,B). Proto je jejich průměr také nezaujatým odhadcem a směrodatnou odchylkou pro součty 0-1 náhodných proměnných je jeho očekávaná chyba O (1 /√k).[3]

Proto pro každou konstantu ε> 0 existuje konstanta k = O (1 / ε2) taková, aby očekávaná chyba odhadu byla maximálněε. Například 400 hašování by bylo zapotřebí k odhadu J(A,B) s očekávanou chybou menší nebo rovnou 0,05.

Varianta s jedinou hashovací funkcí

Může být výpočetně nákladné vypočítat více hashovacích funkcí, ale související verze schématu MinHash se tomuto trestu vyhne tím, že použije pouze jednu hashovací funkci a použije ji k výběru více hodnot z každé sady namísto výběru pouze jediné minimální hodnoty na hashovací funkci. Nechat h být hashovací funkcí a nechat k být pevné celé číslo. Li S je libovolná sada k nebo více hodnot v doméně h,definovat h(k)(S) být podmnožinou k Členové S které mají nejmenší hodnoty h. Tato podmnožina h(k)(S) se používá jako podpis pro sadu Sa podobnost libovolných dvou sad se odhaduje porovnáním jejich podpisů.

Přesněji řečeno A a B být libovolné dvě sady X = h(k)(h(k)(A) ∪ h(k)(B)) = h(k)(A ∪ B) je sada k prvky A ∪ B, a pokud h je náhodná funkce, pak libovolná podmnožina k stejně pravděpodobné, že budou vybrány prvky; to je X je jednoduchý náhodný vzorek z A ∪ B. Podmnožina Y = X ∩ h(k)(A) ∩ h(k)(B) je sada členů X které patří do křižovatky A ∩ B. Proto |Y|/k je nezaujatý odhadce J(A,B). Rozdíl mezi tímto odhadcem a odhadcem vytvořeným několika hashovacími funkcemi je ten X má vždy přesně k členů, zatímco více hashovacích funkcí může vést k menšímu počtu vzorkovaných prvků kvůli možnosti, že dvě různé hashovací funkce mohou mít stejná minima. Kdy však k je malý vzhledem k velikosti sad, je tento rozdíl zanedbatelný.

Standardně Černoffovy hranice pro vzorkování bez náhrady očekával tento odhadovač chybu O (1 /√k), odpovídající výkonu schématu s více hash funkcemi.

Časová analýza

Odhadce |Y|/k lze vypočítat v čase Ó(k) ze dvou podpisů daných sad, v obou variantách schématu. Proto kdy ε a k jsou konstanty, čas pro výpočet odhadované podobnosti z podpisů je také konstantní. Podpis každé sady lze vypočítat lineární čas na velikosti sady, takže když je třeba odhadnout mnoho párových podobností, může tato metoda vést k podstatným úsporám v době běhu ve srovnání s úplným porovnáním členů každé sady. Konkrétně pro nastavenou velikost n mnoho hash variant trvá Ó(n k) čas. Varianta s jedním hashem je obecně rychlejší a vyžaduje Ó(n) čas na udržení fronty předpokládaných minimálních hodnot hash n >> k.[1]

Zahrnující závaží

Byla vyvinuta řada technik pro zavádění vah do výpočtu MinHashes. Nejjednodušší ji rozšiřuje na celočíselné váhy.[4]Rozšiřte naši hashovací funkci h přijmout jak člena množiny, tak celé číslo, pak vygenerovat pro každou položku více hodnot hash podle její váhy. Pokud položka i dojde n generovat hash . Spusťte původní algoritmus na této rozšířené sadě hash. Tímto způsobem získáte vážený index Jaccard jako pravděpodobnost kolize.

Byly vyvinuty další rozšíření, které dosahují této pravděpodobnosti kolize na reálných vahách s lepším časem běhu, jedno pro hustá data,[5] a další pro řídká data.[6]

Další rodina rozšíření používá exponenciálně distribuované hashe. Rovnoměrně náhodný hash mezi 0 a 1 lze převést tak, aby sledoval exponenciální rozdělení pomocí Inverze CDF. Tato metoda využívá mnoho krásných vlastností minimum sady exponenciálních proměnných.

Tím se získá pravděpodobnost srážky index pravděpodobnosti Jaccard[7]

Minimální nezávislé permutace

Aby bylo možné implementovat schéma MinHash, jak je popsáno výše, je potřeba hash funkce h definovat a náhodná permutace na n prvky, kde n je celkový počet odlišných prvků ve spojení všech sad, které mají být porovnány. Ale protože existují n! různé permutace, to by vyžadovalo Ω (n log n) bity jen k určení skutečně náhodné permutace, neuvěřitelně velkého počtu i pro mírné hodnoty n. Z tohoto důvodu, analogicky k teorii univerzální hash, bylo vynaloženo značné úsilí na nalezení rodiny permutací, které jsou "minimálně nezávislé", což znamená, že pro jakoukoli podmnožinu domény bude jakýkoli prvek stejně pravděpodobný jako minimum. Bylo zjištěno, že minimálně nezávislá rodina permutací musí zahrnovat alespoň

různé permutace, a proto to potřebuje Ω (n) bity k určení jediné permutace, stále nepřijatelně velké.[2]

Z důvodu této nepraktičnosti byly zavedeny dva různé pojmy minimální nezávislosti: omezené nezávislé nezávislé permutační rodiny a přibližné minimální nezávislé rodiny. Omezená minimální nezávislost je minimální nezávislá vlastnost omezená na určité sady mohutnost nanejvýš k.[8]Přibližná minimální nezávislost má nanejvýš pevnou pravděpodobnost ε od úplné nezávislosti.[9]

Aplikace

Původní aplikace pro MinHash zahrnovaly shlukování a eliminaci téměř duplikátů mezi webovými dokumenty, představovanými jako sady slov vyskytujících se v těchto dokumentech.[1][2][10] Podobné techniky byly také použity pro shlukování a eliminaci téměř duplikátů pro jiné typy dat, jako jsou obrázky: v případě obrazových dat může být obrázek reprezentován jako sada menších podřízených obrazů, které jsou z ní oříznuty, nebo jako sady více komplexní popis funkcí obrazu.[11]

v dolování dat, Cohen a kol. (2001) použít MinHash jako nástroj pro učení asociačního pravidla. Vzhledem k databázi, ve které má každý záznam více atributů (zobrazeno jako 0–1 matice s řádkem na položku databáze a sloupcem na atribut) používají k identifikaci kandidátských párů atributů, které se často vyskytují, aproximace založené na MinHash k indexu Jaccard, a poté vypočítají přesnou hodnotu indexu pouze pro tyto páry, aby určily ty, jejichž frekvence společného výskytu je pod danou přísnou prahovou hodnotou.[12]

Algoritmus MinHash byl upraven pro bioinformatiku, kde má problém srovnávání sekvencí genomu podobný teoretický základ jako srovnávání dokumentů na webu. Nástroje založené na MinHash[13][14] umožňují rychlé srovnání dat sekvenování celého genomu s referenčními genomy (přibližně 3 minuty k porovnání jednoho genomu s 90000 referenčními genomy v RefSeq ), a jsou vhodné pro speciaci a možná omezený stupeň mikrobiální subtypizace. Existují také aplikace pro metagenomiku [13] a použití algoritmů odvozených od MinHash pro zarovnání a shromáždění genomu.[15]

Jiná použití

Schéma MinHash lze považovat za instanci hash citlivý na lokalitu, sbírka technik pro použití hashovacích funkcí k mapování velkých sad objektů na menší hodnoty hash takovým způsobem, že když mají dva objekty malou vzdálenost od sebe, jejich hodnoty hash budou pravděpodobně stejné. V tomto případě lze podpis sady považovat za její hodnotu hash. Existují i ​​jiné techniky hašování citlivé na lokalitu Hammingova vzdálenost mezi sadami a kosinová vzdálenost mezi vektory; hash citlivý na lokalitu má důležité aplikace ve Windows hledání nejbližšího souseda algoritmy.[16] Pro velké distribuované systémy, zejména MapReduce, existují upravené verze MinHash, které pomáhají vypočítat podobnosti bez závislosti na kótě bodu.[17]

Hodnocení a referenční hodnoty

Velké hodnocení provedlo Google v roce 2006 [18] porovnat výkon Minhash a SimHash[19] algoritmy. V roce 2007 Google uvedl, že používá Simhash pro detekci duplikátů pro procházení webu[20] a pomocí Minhash a LSH pro zprávy Google personalizace.[21]

Viz také

Reference

  1. ^ A b C d Broder, Andrei Z. (1997), „O podobnosti a zadržování dokumentů“, Komprese a složitost sekvencí: Proceedings, Positano, Amalfitánské pobřeží, Salerno, Itálie, 11. – 13. Června 1997 (PDF), IEEE, str. 21–29, CiteSeerX  10.1.1.24.779, doi:10.1109 / SEKVENCE.1997.666900, ISBN  978-0-8186-8132-5, archivovány z originál (PDF) dne 2015-01-31, vyvoláno 2014-01-18.
  2. ^ A b C Broder, Andrei Z.; Charikar, Mojžíš; Frieze, Alan M.; Mitzenmacher, Michael (1998), „Min-wise independent permutations“, Proc. 30. ACM Symposium on Theory of Computing (STOC '98), New York, NY, USA: Sdružení pro výpočetní techniku, str. 327–336, CiteSeerX  10.1.1.409.9220, doi:10.1145/276698.276781, ISBN  978-0897919623.
  3. ^ Vassilvitskii, Sergey (2011), COMS 6998-12: Nakládání s masivními daty (poznámky z přednášky, Kolumbijská univerzita) (PDF), archivovány z originál (PDF) dne 2018-10-24.
  4. ^ Chum, Ondřej; Philbin, James; Zisserman, Andrew (2008), „Near Duplicate Image Detection: min-Hash and tf-idf Weighting.“ (PDF), BMVC, 810: 812–815
  5. ^ Shrivastava, Anshumali (2016), "Přesné vážené minwise hashování v konstantním čase", arXiv:1602.08393 [cs.DS ]
  6. ^ Ioffe, Sergey (2010), „Vylepšené konzistentní vzorkování, vážený minhash a skicování l1“ (PDF), Data Mining (ICDM), 2010 IEEE 10th International Conference on: 246–255, CiteSeerX  10.1.1.227.9749, doi:10.1109 / ICDM.2010.80, ISBN  978-1-4244-9131-5
  7. ^ Moulton, Ryan; Jiang, Yunjiang (2018), „Maximally Consistent Sampling and the Jaccard Index of Probability Distribuce“, 2018 IEEE International Conference on Data Mining (ICDM), str. 347–356, arXiv:1809.04052, doi:10.1109 / ICDM.2018.00050, ISBN  978-1-5386-9159-5
  8. ^ Matoušek, Jiří; Stojaković, Miloš (2003), „O omezené minimální nezávislosti permutací“, Náhodné struktury a algoritmy, 23 (4): 397–408, CiteSeerX  10.1.1.400.6757, doi:10.1002 / rsa.10101.
  9. ^ Saks, M.; Srinivasan, A .; Zhou, S .; Zuckerman, D. (2000), „Sady s nízkou odchylkou přinášejí přibližné minimální nezávislé permutační rodiny“, Dopisy o zpracování informací, 73 (1–2): 29–32, CiteSeerX  10.1.1.20.8264, doi:10.1016 / S0020-0190 (99) 00163-5.
  10. ^ Manasse, Mark (2012). O efektivním určování nejbližších sousedů: podkovy, ruční granáty, vyhledávání na webu a další situace, kdy je blízko dost blízko. Morgan & Claypool. str. 72. ISBN  9781608450886.
  11. ^ Chum, Ondřej; Philbin, James; Isard, Michael; Zisserman, Andrew (2007), „Škálovatelné na téměř identický obraz a detekce snímků“, Sborník příspěvků ze 6. mezinárodní konference ACM o obrazu a načítání videí (CIVR'07), str. 549–556, doi:10.1145/1282280.1282359, ISBN  9781595937339; Chum, Ondřej; Philbin, James; Zisserman, Andrew (2008), „Detekce téměř duplicitního obrazu: vážení min-hash a tf-idf“, Sborník z konference British Machine Vision (PDF), 3, str. 4.
  12. ^ Cohen, E.; Datar, M .; Fujiwara, S .; Gionis, A .; Indyk, P.; Motwani, R.; Ullman, J. D.; Yang, C. (2001), „Hledání zajímavých asociací bez podpory prořezávání“, Transakce IEEE na znalostní a datové inženýrství, 13 (1): 64–78, CiteSeerX  10.1.1.192.7385, doi:10.1109/69.908981.
  13. ^ A b Ondov, Brian D .; Treangen, Todd J .; Melsted, Páll; Mallonee, Adam B .; Bergman, Nicholas H .; Koren, Sergey; Phillippy, Adam M. (2016-06-20). „Mash: rychlý odhad vzdálenosti genomu a metagenomu pomocí MinHash“. Genome Biology. 17 (1): 132. doi:10.1186 / s13059-016-0997-x. ISSN  1474-760X. PMC  4915045. PMID  27323842.
  14. ^ „Vítejte v sourmash! - dokumentace sourmash 1.0“. sourmash.readthedocs.io. Citováno 2017-11-13.
  15. ^ Berlín, Konstantin; Koren, Sergey; Chin, Chen-Shan; Drake, James P; Landolin, Jane M; Phillippy, Adam M (2015-05-25). „Sestavování velkých genomů s sekvenováním jedné molekuly a hašováním citlivým na lokalitu“. Přírodní biotechnologie. 33 (6): 623–630. doi:10.1038 / nbt.3238. ISSN  1546-1696. PMID  26006009.
  16. ^ Andoni, Alexandr; Indyk, Piotr (2008), „Téměř optimální hashovací algoritmy pro přibližného nejbližšího souseda ve vysokých rozměrech“, Komunikace ACM, 51 (1): 117–122, CiteSeerX  10.1.1.226.6905, doi:10.1145/1327452.1327494.
  17. ^ Zadeh, Reza; Goel, Ashish (2012), „Dimension Independent Similarity Computation“, arXiv:1206.2082 [cs.DS ].
  18. ^ Henzinger, Monika (2006), „Hledání téměř duplicitních webových stránek: rozsáhlé vyhodnocení algoritmů“, Sborník 29. výroční mezinárodní konference ACM SIGIR o výzkumu a vývoji v oblasti získávání informací, str.284, doi:10.1145/1148170.1148222, ISBN  978-1595933690.
  19. ^ Charikar, Moses S. (2002), „Techniky odhadu podobnosti z algoritmů zaokrouhlování“, Proceedings of the 34. Annual ACM Symposium on Theory of Computing, str. 380, doi:10.1145/509907.509965, ISBN  978-1581134957.
  20. ^ Gurmeet Singh, Manku; Jain, Arvind; Das Sarma, Anish (2007), „Detection near-duplicates for web crawling“, Sborník ze 16. mezinárodní konference o World Wide Web (PDF), str. 141, doi:10.1145/1242572.1242592, ISBN  9781595936547.
  21. ^ Das, Abhinandan S .; Datar, Mayur; Garg, Ashutosh; Rajaram, Shyam; et al. (2007), „Personalizace zpráv Google: škálovatelné online filtrování spolupráce“, Sborník ze 16. mezinárodní konference o World Wide Web, str. 271, doi:10.1145/1242572.1242610, ISBN  9781595936547.