Hashování citlivé na lokalitu

Cíl: Najít dokumenty s Jaccardovou podobností alespoň t

Obecnou myšlenkou LSH je najít takový algoritmus, který nám při zadání signatur 2 dokumentů řekne, zda tyto 2 dokumenty tvoří kandidátskou dvojici, nebo ne, tj. jejich podobnost je větší než práh t. Nezapomeňte, že podobnost podpisů bereme jako zástupce Jaccardovy podobnosti mezi původními dokumenty.

Konkrétně pro podpisovou matici min-hash:

• Hashujeme sloupce podpisové matice M pomocí několika hashovacích funkcí
• Pokud se 2 dokumenty hashují do stejného kyblíku alespoň pro jednu z hashovacích funkcí, můžeme tyto 2 dokumenty považovat za kandidátskou dvojici

Teď je otázka, jak vytvořit různé hashovací funkce. Za tímto účelem provedeme rozdělení pásem.

Pásmové rozdělení

Tady je algoritmus:

• Rozdělte signaturní matici na pásma, přičemž každé pásmo má r řádků
• Pro každé pásmo, hashujte jeho část každého sloupce do hashovací tabulky s k kyblíky
• Kandidátní dvojice sloupců jsou ty, které se hashují do stejného kyblíku alespoň pro 1 pásmo
• Nastavte b a r tak, abyste zachytili většinu podobných dvojic, ale málo nepodobných dvojic

Je zde několik úvah. V ideálním případě chceme pro každé pásmo vzít k rovné všem možným kombinacím hodnot, které může sloupec v rámci pásma nabývat. To bude ekvivalentní shodě identit. Tímto způsobem však bude k obrovské číslo, které je výpočetně neproveditelné. Například: Pokud máme v pásmu 5 řádků. Pokud jsou nyní prvky v signatuře 32bitová celá čísla, pak bude k v tomto případě (2³²)⁵ ~ 1,4615016e+48. Zde vidíte, v čem je problém. Obvykle se k bere kolem 1 milionu.

Jde o to, že pokud jsou si 2 dokumenty podobné, pak se objeví jako kandidátská dvojice alespoň v jednom z pásem.

Volba b & r

Pokud vezmeme b velké, tj. větší počet hašovacích funkcí, pak snížíme r, protože b*r je konstanta (počet řádků v podpisové matici). Intuitivně to znamená, že zvyšujeme pravděpodobnost nalezení kandidátního páru. Tento případ je ekvivalentní přijetí malého t (prahu podobnosti)

Řekněme, že vaše podpisová matice má 100 řádků. Uvažujme 2 případy:

b1 = 10 → r = 10

b2 = 20 → r = 5

V 2. případě je větší šance, že se 2 dokumenty objeví ve stejném kbelíku alespoň jednou, protože mají více příležitostí (20 vs. 10) a porovnává se méně prvků signatury (5 vs. 10).

Vyšší b znamená nižší práh podobnosti (vyšší falešná pozitivita) a nižší b znamená vyšší práh podobnosti (vyšší falešná negativita)

Zkusme to pochopit na příkladu.

Nastavení:

• 100k dokumentů uložených jako signatura o délce 100
• Matrice signatur: Vezměme b = 20 → r = 5

Prah podobnosti (t) : 80%

Chceme, aby 2 dokumenty (D1 & D2) s 80% podobností byly zaheslovány ve stejném kbelíku alespoň pro jedno z 20 pásem.

P(D1 & D2 shodné v určitém pásmu) = (0,8)⁵ = 0,328

P(D1 & D2 nejsou podobné ve všech 20 pásmech) = (1-0,328)^20 = 0,00035

To znamená, že v tomto případě máme ~.035% šanci na falešnou negativitu při 80% podobnosti dokumentů.

Také chceme, aby 2 dokumenty (D3 & D4) s 30% podobností nebyly zaheslovány ve stejném kbelíku pro žádné z 20 pásem (práh = 80%).

P(D3 & D4 shodné v určitém pásmu) = (0.3)⁵ = 0.00243

P(D3 & D4 jsou podobné alespoň v jednom z 20 pásem) = 1 – (1-0,00243)^20 = 0,0474

To znamená, že v tomto scénáři máme ~4,74% šanci na falešnou pozitivitu při 30 % podobných dokumentů.

Vidíme tedy, že máme několik falešně pozitivních a několik falešně negativních výsledků. Tento podíl se bude lišit podle volby b a r.

To, co zde chceme, je něco jako níže. Máme-li 2 dokumenty, jejichž podobnost je větší než prahová hodnota, pak pravděpodobnost, že sdílejí stejný kbelík alespoň v jednom z pásem, by měla být 1, jinak 0.

Nejhorší případ bude, pokud budeme mít b = počet řádků v podpisové matici, jak je uvedeno níže.

Obecný případ pro libovolné b a r je uveden níže.

Zvolte b a r tak, abyste získali nejlepší S-křivku i.e minimální míra falešně negativních a falešně pozitivních výsledků

LSH souhrn

• Nastavte M, b, r, abychom získali téměř všechny dvojice dokumentů s podobnými signaturami, ale vyřadili většinu dvojic, které podobné signatury nemají
• Kontrola v hlavní paměti, zda kandidátské dvojice skutečně mají podobné signatury