MySQLでTF-IDFの計算、あと2つのベクトルの内積の計算 (2006-12-19)

本文を形態素分解し、必要な品詞をtfテーブルとdfテーブルに入れる。分析対象となる文書群すべてについてこの処理を行い、各形態素のTF-IDF値を求めて文書をベクトル化する。他の文書ベクトルと内積を比較し、小さい順に「似ている記事」を求めたい (クラスタリングとかは別途)。

HarmanによるTF値の正規化とSparok JonesによるDF値の正規化をする場合のTF-IDF値の計算式は以下のようになる (参考文献):

tfidf(i,j) = log2(freq(i,j) + 1) / log2(NoT) * (log2(N / Dfreq(i)) + 1)

HarmanによるTFの正規化

tf(i,j) = log2(freq(i,j) + 1) / log2(NoT)

tf(i,j): 文書jにおける単語iのTF値
freq(i,j): 文書jにおける単語iの登場回数
NoT: 文書j中のタームの種類数(num of terms)

Sparck JonesによるDFの正規化

idf(i) = log2(N / Dfreq(i)) + 1

idf(i): 単語iのDF値
N: 文書集合中の文書総数
Dfreq(i): 単語iが登場する文書数

MySQL での表現

TF値の分子

SELECT log2(times + 1) FROM tf WHERE item='j' AND tag='i';

TF値の分母

SELECT log2(count(tag)) FROM tf WHERE item='j' GROUP BY item;

IDF値のlogの分子

SELECT count(id) FROM article;

IDF値のlogの分母

SELECT times FROM df WHERE tag = 'i';

全部くっつけると:

SELECT item, tag, log2(tf.times + 1) / log2(total) * (log2(n / df.times) + 1) AS tfidf
  FROM tf
    LEFT JOIN df USING(tag)
    LEFT JOIN (SELECT item, count(tag) total FROM tf GROUP BY item) AS a USING(item)
    CROSS JOIN (SELECT count(id) AS n FROM items) AS b
  WHERE item="j";

実際はユーザ変数を使った方がSQLが短くなっていいと思う。

SELECT @total := count(tag) FROM tf WHERE item = "j";
SELECT @n := count(id) FROM items;
SELECT item, tag, log2(tf.times + 1) / log2(@total) * (log2(@n / df.times) + 1) AS tfidf
  FROM tf LEFT JOIN df USING(tag)
  WHERE item="j";

これで記事の各形態素のTFIDF値が求められたので、tfidfテーブルに保管しておく。

内積を求めて近い記事を出す

とりあえず各記事の上位100単語くらいを使うことにする。

INSERT INTO tfidf
  SELECT item, tag, log2(tf.times + 1) / log2(@total) * (log2(@n / df.times) + 1) AS tfidf
    FROM tf LEFT JOIN df USING(tag)
    WHERE item="j"
    ORDER BY tfidf DESC
    LIMIT 100;

ある文書wがn次元のベクトルで表せる (w = {w₁ w₂ ... w_n})とき、文書wとxの内積は

Σ(w_i * v_i) / √(Σ(w_i²) * Σ(v_i²))

SQLで書くと

CREATE TEMPORARY TABLE inp
  SELECT self.tag, self.tfidf self, target.tfidf target
    FROM tfidf self
      LEFT JOIN (SELECT tag,tfidf FROM tfidf WHERE item='v') target USING(tag)
    WHERE self.item = 'w';
SELECT sum(self * target) / sqrt(sum(pow(self,2))*sum(pow(target,2))) inp FROM inp

実際にやってみる

実際にニュー速各板のスレでやってみた。だいたい同じニュースの続きのスレだと0.6以上の高い値に、似たようなネタの異なるニュースの場合は0.3～0.4くらいになった。以下はそれらの例。カッコ内が内積

高い値 …… 同じニュースの次スレ、前スレ

【経済】「格差是正のため、正社員の待遇を非正規社員水準に合わせる」…経済財政諮問会議・八代氏★５

【経済】「格差是正のため、正社員の待遇を非正規社員水準に合わせる」…経済財政諮問会議・八代氏★４ (0.76865722990833)
【経済】「格差是正のため、正社員の待遇を非正規社員水準に合わせる」…経済財政諮問会議・八代氏★３ (0.72848890331971)
【経済】「格差是正のため正社員待遇を非正規社員水準へ」…経済財政諮問会議メンバー・八代尚宏氏★２ (0.61619675121174)
【経済】「格差是正のため正社員待遇を非正規社員水準へ」…経済財政諮問会議メンバー・八代尚宏氏 (0.63664490692797)

【芸能】森本レオが石原真理子の処女を奪ったことを認める「それでもやっぱりマリコがんばれ」

【芸能】石原真理子「17歳で森本レオに処女奪われた」…週刊誌に暴露、「宣伝か」の声も★２ (0.82246383998552)
【芸能】石原真理子「17歳で森本レオに処女奪われた」…週刊誌に暴露、「宣伝か」の声も[12/18] (0.79417204039799)

◆自治議論★64◆

愛の説教部屋166(地獄キャンペーン実施中)（　ﾟдﾟ) (0.67651278868912)
◆自治議論★63◆ (0.81182145799799)
◆自治議論★62◆ (0.79929338782244)

中くらいの値 …… 似たようなネタだが異なるニュースのスレ

【MLB】多田野、アスレチックスと再契約春季キャンプでメジャー復帰目指す★３

【社会】ＮＨＫ職員（男）、電車で大学生（１８０cm・１２０kgの男子）に痴漢→逮捕…東京★３ (0.4629403483907)
【社会】ＮＨＫ職員（男）、電車で大学生（男子）に痴漢→逮捕…東京★２ (0.41509734340642)

【大阪】コリアNGOセンター事務局長「公立校で民族教育は不要との意見が出かねない…外国籍の子供に愛国心強調しないで」［12/18］

【論説】「"日教組が、教育荒廃の元凶"というのは言いがかりだ」…東京新聞★２ (0.35593573724151)
【日韓】［特派員コラム］韓国は日本を追い越すことができる?潜在力も意欲も韓国が上[12/18] (0.3069814685099)
【論説】「愛国心、"格差"はぐらかす為か？学生らは愛国心強要に"日本社会の悪化"を感じている」…毎日新聞★３ (0.39403589906126)

【フィギュアスケート】高橋・安藤・浅田・村主ら日本勢に謎の症状･･･体調不良者が続出★３

【北海道】カキ「風評被害」に悲鳴、取扱額４０％減　ノロウイルス食中毒、今季の感染例ゼロなのに★２ (0.41831300355656)

今回やってみて、同じニュースのスレッドは★１だろうが★８だろうが同じようなことを延々と話しているのではないかと感じた。何スレも立つような息の長いニュースについて、スレッドごとの単語の登場の仕方とか共起の仕方を見ていくと、ニュー速民のニュースへの態度を表せたりするかも。面白いのはフィギュアスケート選手の体調不良の記事とカキの風評被害の記事が関連付けられたこと。フィギュアスケートの記事中に「カキ」への言及がなくても、ニュー速民による噂話の可視化によって、実は関係あるかもしれない2つの記事が結びついた。なんか集合知かも～。