k47.cz
výběr foto Praha povídky kultura
TECH ▞▞ kolo | twitter RSS

Kosinová podobnost

24. 9. 2012 (aktualizováno 24. 10. 2019) — 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í.

Nej­lepší na tom celém je, že ko­si­nová po­dob­nost sku­tečně fun­guje. Má sice určité ne­do­statky (k nim se do­stanu poz­ději), ale fun­guje.

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ší.

type WordFreq = Map[String, Int]

def dot(a: WordFreq, b: WordFreq): Double =
  a.map { case (k, v) => if (b.contains(k)) v * b(k) else 0 }.sum

def magnitude(ws: WordFreq): Double =
  math.sqrt(ws.values.map(x => (x * x).toDouble).sum)

def cossim(a: WordFreq, b: WordFreq): Double =
  dot(a, b) / (magnitude(a) * magnitude(b))

def metric(cossim: Double): Double =
  1 - 2 * math.acos(cossim) / math.Pi


val threadsData = io.Source.fromFile("r9k-cossim.data").getLines.take(500)

val threads: Vector[(Int, WordFreq)] = threadsData.map { line =>
  val Array(id, txt) = line.split("\t", 2)

  val words = txt.toLowerCase.replaceAll("\\[ntr\\]", " ").split("\\W+").filter { w => w.length >= 3 && !(w matches "\\d+") }
  val frequency = words.groupBy(identity).mapValues(_.size)

  (id.toInt, frequency)
} toVector


val similarities =
  for (Seq((aId, aWords), (bId, bWords)) <- threads.combinations(2))
    yield (aId, bId, metric(cossim(aWords, bWords)))

similarities.filter { case (_, _, sim) => sim > 0.85 } foreach println

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