k47.cz    — každý den dokud se vám to nezačne líbit
foto Praha výběr povídky kultura | twitter FB


Kosinová podobnost

24. 9. 2012 — k47 (CC by-sa)

Kosinová podobnost (cosine similarity) je míra podobnosti dvou vektorů, která se získá výpočtem kosinu úhlu těchto vektorů.

Toho se dá využít pro zjištění podobnosti dvou dokumentů. V takovém případě budou vektory reprezentovat četnost jednotlivých slov (popřípadě n-gramů, tagů nebo jakékoli jiné feature).


Řečí matematiky: skalární součin vektorů vydělený součinem jejich velikostí.1

Na první pohled se může zdát, že takto jednoduchý postup dokáže odhalit jenom téměř identické dokumenty s několika málo změnami nebo přeházenými odstavci, ale není tomu tak. Můžeme předpokládat, že ve dvou různých dokumentech, které pojednávají o stejném tématu, budou použita přibližně stejná slov v přibližně stejném rozložení.

A nejlepší na tom, že kosinová podobnost skutečně funguje. Má sice nějaké nedostatky (ke kterým se dostanu později), ale funguje.


Abych si to otestoval, použil jsem data z projektu Chanminer (ono se vyplatí mít při ruce 100GB strukturovaných dat), konkrétně část /r9k/, která obsahuje 355265 postů ve 12250 vláknech z doby od 23. října do 16. listopadu 2011 - tedy všechno, co je momentálně archivováno na http://chan.k47.cz/r9k/.

Data ze kterých jsem vycházel si můžete stáhnout tady. Každý řádek začíná id daného vlákna od kterého je tabulátorem oddělený text všech postů v daném vlákně.

Následuje ukázková naivní implementace kosinové podobnosti ve Scale, která data načte a spočítá podobnost. Kód je velice pomalý, ale aspoň je přehledný. Optimalizovaná verze (která reprezentuje řídké vektory v Yale formátu/CSR) je asi 20x rychlejší.

Nedostatky:

Jasným nedostatkem algoritmu je prostý fakt, že nebere v potaz synonyma (a v případě češtiny skloňování/časování) a váhu jednotlivých slov.

Pak také produkuje jenom málo falešných pozitiv, ale zato má sklony k falešným negativům. Když vyhodnotí dva dokumenty jako stejné, je malá šance, že se tématicky rozcházejí (mnohoznačná slova nejsou podle mě tak velký problém), ale často se stane, že vůbec nepozná dokumenty, které se o stejném tématu baví trochu jinak (synonyma).


Další krok je jednoznačně tf*idf.


Další čtení:

Pozn:

  1. pokud A i B jsou bitmapy, pak se dá kosinová podobnost implementovat efektivně jako:
     bitcount(A and B)
---------------------------
√bitcount(A) * √bitcount(B)

píše k47 & hosté, ascii@k47.cz