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

Kosinová podobnost

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

Ko­si­nová po­dob­nost (cosine si­mi­la­rity) je míra po­dob­nosti dvou vek­torů, která se získá vý­po­čtem kosinu úhlu těchto vek­torů.

Toho se dá využít pro zjiš­tění po­dob­nosti dvou do­ku­mentů. V ta­ko­vém pří­padě budou vek­tory re­pre­zen­to­vat čet­nost jed­not­li­vých slov (po­pří­padě n-gramů, tagů nebo ja­ké­koli jiné fe­a­ture).


Řečí ma­te­ma­tiky: ska­lární součin vek­torů vy­dě­lený sou­či­nem jejich ve­li­kostí.1

Na první pohled se může zdát, že takto jed­no­du­chý postup dokáže od­ha­lit jenom téměř iden­tické do­ku­menty s ně­ko­lika málo změ­nami nebo pře­há­ze­nými od­stavci, ale není tomu tak. Můžeme před­po­klá­dat, že ve dvou růz­ných do­ku­men­tech, které po­jed­ná­vají o stej­ném tématu, budou po­u­žita při­bližně stejná slov v při­bližně stej­ném roz­lo­žení.

A nej­lepší na tom, že ko­si­nová po­dob­nost sku­tečně fun­guje. Má sice nějaké ne­do­statky (ke kterým se do­stanu poz­ději), ale fun­guje.


Abych si to otes­to­val, použil jsem data z pro­jektu Cha­n­mi­ner (ono se vy­platí mít při ruce 100GB struk­tu­ro­va­ných dat), kon­krétně část /r9k/, která ob­sa­huje 355265 postů ve 12250 vlák­nech z doby od 23. října do 16. lis­to­padu 2011 – tedy všechno, co je mo­men­tálně ar­chi­vo­váno na http://chan.k47.cz/r9k/.

Data ze kte­rých jsem vy­chá­zel si můžete stáh­nout tady. Každý řádek začíná id daného vlákna od kte­rého je ta­bu­lá­to­rem od­dě­lený text všech postů v daném vlákně.

Ná­sle­duje ukáz­ková naivní im­ple­men­tace ko­si­nové po­dob­nosti ve Scale, která data načte a spo­čítá po­dob­nost. Kód je velice pomalý, ale aspoň je pře­hledný. Op­ti­ma­li­zo­vaná verze (která re­pre­zen­tuje řídké vek­toryYale for­mátu/CSR) je asi 20x rych­lejší.

Ne­do­statky:

Jasným ne­do­stat­kem al­go­ritmu je prostý fakt, že nebere v potaz sy­no­nyma (a v pří­padě češ­tiny sklo­ňo­vání/ča­so­vání) a váhu jed­not­li­vých slov.

Pak také pro­du­kuje jenom málo fa­leš­ných po­zi­tiv, ale zato má sklony k fa­leš­ným ne­ga­ti­vům. Když vy­hod­notí dva do­ku­menty jako stejné, je malá šance, že se té­ma­ticky roz­chá­zejí (mno­hoznačná slova nejsou podle mě tak velký pro­blém), ale často se stane, že vůbec ne­po­zná do­ku­menty, které se o stej­ném tématu baví trochu jinak (sy­no­nyma).


Další krok je jed­no­značně tf*idf.


Další čtení:

Pozn:

  1. pokud A i B jsou bitmapy, pak se dá ko­si­nová po­dob­nost im­ple­men­to­vat efek­tivně jako:
     bitcount(A and B)
---------------------------
√bitcount(A) * √bitcount(B)

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