Kosinová podobnost

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

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

Nejlepší na tom celém je, že kosinová podobnost skutečně funguje. Má sice určité nedostatky (k nim se dostanu později), ale funguje.

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 20× rychlejší.

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

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í:

• Od pohledu dobrý, aneb jak najít skoro stejné obrázky mezi dvěma miliony souborů za méně než deset minut
• Článek, který mě k tomu navedl
• Cosine Similarity
• Vector space model
• Clustering related stories

Pozn:

1. pokud A i B jsou bitmapy, pak se dá kosinová podobnost implementovat efektivně jako:

     bitcount(A and B)
---------------------------
√bitcount(A) * √bitcount(B)