TF-IDFで遊んでみた - uncertain world

最近，何が分かってて何が分かってないのかがゴチャゴチャしてきたので，
頭の整理と勉強の為に，
某ニュースサイトの記事をクローリングして集めていたものを使って色々遊んでみました．

今回はTF-IDFの計算をMySQLでやるというお題．
ここで言うTFとIDFの意味は以下のような感じです．

単語 $\begin{align*} w_i \end{align*}$ の文書 $\begin{align*} D_j \end{align*}$ における重みを $\begin{align*} d_{ij} \end{align*}$ とすると，
以下のような指標によって $\begin{align*} d_{ij} \end{align*}$ を特徴付けることができる．

$\begin{align*} d_{ij} = \frac{ l_{ij} g_i }{n_j} \end{align*}$

・TF(局所的重み付け)
単語 $\begin{align*} w_i \end{align*}$ の文書 $\begin{align*} D_j \end{align*}$ における出現頻度を元に計算される重み．

$\begin{align*} l_{ij} \end{align*}$ = 単語 $\begin{align*} w_i \end{align*}$ の文書 $\begin{align*} D_j \end{align*}$ における出現回数 / 文書 $\begin{align*} D_j \end{align*}$ に出現した単語数

ここで注意するのは，"文書 $\begin{align*} D_j \end{align*}$ に出現した単語数"は単語数であり，単語の種類数ではないという事．

例えば，「今日は東京で太郎君と東京タワーに行ってきました．東京まんじゅう美味いな．」という文書 $\begin{align*} D_j \end{align*}$ があった場合，

今日/は/東京/で/太郎/君/と/東京タワー/に/行っ/て/き/まし/た/．/東京/まんじゅう/美味い/な/．

と分解されます．

この場合の，"文書 $\begin{align*} D_j \end{align*}$ に出現した単語数"は

今日，は，東京，で，太郎，君，と，東京タワー，に，行っ，て，き，まし，た，．，東京，まんじゅう，美味い，な，．

20個

"文書 $\begin{align*} D_j \end{align*}$ に出現した単語の種類数"

今日，は，東京，で，太郎，君，と，東京タワー，に，行っ，て，き，まし，た，．，まんじゅう，美味い，な

18個になります．

・IDF(大域的重み付け)
全文書の中で単語 $\begin{align*} w_i \end{align*}$ が出現した文書の数を元に計算される重み．

$\begin{align*} w_i \end{align*}$ = log(文書の総数 / 単語 $\begin{align*} w_i \end{align*}$ を含む文書数)

・文書正規化係数
長い文書に含まれる単語の方が重みが強くなるので，調整する．
コサイン正規化は以下のような式で定義されています(今回は正規化しないで行う)．
$\begin{align*} n_j = \sqrt{\sum_{i = 1}^m(l_{ij}g_i)^2 } \end{align*}$

数学的な定義は上記のような感じです．
これだけで結構おなか一杯ですが，もうちょっと続けます．．

今回は，文書の本文一覧テーブル(documents)，単語一覧テーブル(terms)，各文書中の単語の出現回数を保存するテーブル(document_terms)の三つを作りました．

テーブルの定義は以下の通り

・本文一覧テーブル(documents)
id int
document longtext

id 0
document Intel「P45」チップセットを搭載したGIGABYTE製マザーボード2モデル「GA-EP45-D...

・単語一覧テーブル(terms)
id int
name varchar(100)

id 1
name ASUS

・文書中に出現した単語数保存テーブル(document_terms)
document_id int
term_id int
frequency int # 修験頻度
score float # tf-idfで算出したスコア

document_id 0
term_id 1
frequency 1
score 0.0173551

・TF-IDFのスコアリングの手順
MySQLだとサブクエリに同じテーブル使えなかった(http://stackoverflow.com/questions/45494/sql-delete-cant-specify-target-table-for-update-in-from-clause)ので，
最初に各のスコアを計算してその結果を各々のカラムにupdateする形にした

-- TF-IDF
select
  dt.document_id,
  dt.term_id,
  (
    -- TF
    (
      -- 文書Djにおける単語Wiの出現回数
      (
        select sum(frequency)
        from document_terms dt1
        where dt1.document_id = dt.document_id and dt1.term_id = dt.term_id
      )
      /
      -- 文書Djに出現する単語の総数(種類数ならcount(*)にする)
      (
        select sum(frequency)
        from document_terms dt2
        where dt2.document_id = dt.document_id
      )
    )
    *
    -- IDF
    log(
      -- 文書の数
      (
        select count(distinct document_id)
        from document_terms dt1
      )
      /
      -- 単語Wiを含む文書の数
      (
        select count(distinct document_id)
        from document_terms dt2
        where dt2.term_id = dt.term_id
      )
    )
  ) as tf_idf,
  -- 単語名表示用(ホントは不要)
  (
    select name
    from terms t
    where t.id = dt.term_id
  ) as term_name
  from document_terms dt
  where dt.document_id = 0

これでまず計算して，その結果を

UPDATE document_terms SET score = ? WHERE document_id = ? AND term_id = ?

みたいな感じのSQLをdocument_termsのデータ量分まわす．

これで文書中に出現した各単語のスコアリングをTF-IDFを用いて行えた．
ので，後は遊んでみる．

・各単語の共起情報の取得
単語(行)文書(列)行列Aってのを作った場合，
A×A^Tは単語×単語行列になっていて，
各単語の共起頻度を表す行列になってた気がするけど，
その行列を作るのがアレなので，SQL使ってなんとかしようとしてみる．

・単純な出現回数をスコアとした共起情報

select
  b.term_id,
  sum(b.frequency) as freq,
  (
    select name from terms c where c.id = b.term_id
  ) as name
from document_terms b
where
  b.document_id in (
    select a.document_id from document_terms a where a.term_id = 8404
  )
  and b.term_id != 8404
group by b.term_id
order by freq;

結果：「政治」と共起しやすい奴ら

term_id | freq | term_name |
13278 | 19 | 審判 |
9365 | 21 | 総選挙 |
8315 | 21 | 政策 |
1391 | 23 | たち |
8212 | 25 | 日本共産党 |
8169 | 26 | 党 |
17 | 26 | もの |
1674 | 27 | 必要 |
13280 | 27 | 自公政権 |
8751 | 27 | マニフェスト |
8416 | 28 | 政権 |
2955 | 28 | 一 |
769 | 30 | 問題 |
567 | 31 | 万 |
7824 | 32 | 立場 |
167 | 33 | 人 |
142 | 34 | 年 |
8413 | 41 | 自民党 |
11 | 44 | 日 |
8446 | 49 | 民主党 |
8336 | 50 | 選挙 |
1398 | 54 | 私 |
9170 | 54 | 国民 |
657 | 56 | 日本 |
89 | 74 | 的 |
703 | 141 | の |
106 | 161 | こと |

・出現回数×スコアで重み付け

select
  b.term_id,
  sum(b.frequency * b.score) as freq,
  (
    select name from terms c where c.id = b.term_id
  ) as name
from document_terms b
where
  b.document_id in (
    select a.document_id from document_terms a where a.term_id = 8404
  )
  and b.term_id != 8404
group by b.term_id
order by freq;

結果：「政治」と共起しやすい奴ら

term_id | freq | term_name |
8212 | 1.2222178727388382 | 日本共産党 |
23933 | 1.3558716103434563 | 性行為 |
657 | 1.4579699432943016 | 日本 |
8751 | 1.5716206398792565 | マニフェスト |
89 | 1.6600907219108194 | 的 |
8336 | 1.7056102231144905 | 選挙 |
8446 | 1.7192125204019248 | 民主党 |
8413 | 1.8657475979998708 | 自民党 |
23960 | 1.938939392566681 | わいせつ物 |
4181 | 1.951665947213769 | 物 |
106 | 2.006680705351755 | こと |
7824 | 2.1125706338789314 | 立場 |
703 | 2.1293790051713586 | の |
13280 | 2.1437609866261482 | 自公政権 |
23961 | 2.3461167961359024 | わいせつ |
1398 | 2.8301126593723893 | 私 |
9170 | 3.0106590217910707 | 国民

個人的に，後者の結果が好きでした．
「政治」と「性行為」や「わいせつ」はニュースの格好の記事のネタだからスコアが高くなったんでしょうねぇ．

数学的な所は，情報検索アルゴリズムを参考にしました．

・追記

なんかupdateする際に自己相関サブクエリ使えない〜って思ってたけど，
replace into〜でやれば一個のSQLでどうにかできた(多分)．
計算結果はよく分からん！

REPLACE INTO document_terms ( select dt.document_id, dt.term_id, dt.frequency, -- TF ( -- 文書Djにおける単語Wiの出現回数 ( select sum(dt1.frequency) from document_terms dt1 where dt1.document_id = dt.document_id and dt1.term_id = dt.term_id ) / -- 文書Djに出現する単語の総数(種類数ならcount(*)にする) ( select sum(dt2.frequency) from document_terms dt2 where dt2.document_id = dt.document_id ) ) * -- IDF log( -- 文書の数 ( select count(id) from documents dt3 ) / -- 単語Wiを含む文書の数 ( select count(d.id) from documents d join document_terms dt4 on d.id = dt4.document_id where dt4.term_id = dt.term_id ) ) as tf_idf from document_terms dt )

↑やっぱこれ嘘っぽい？