Graph of Word、TW-IDFとTFのnormalizationメモ

はじめに

Rousseau et al., Graph-of-word and TW-IDF: New Approach to Ad Hoc IR
http://www.lix.polytechnique.fr/~rousseau/papers/rousseau-cikm2013.pdf
文書dのグラフ的表現とそこから計算されるTW-IDFというTermの重み付けについて、メモ。

Graph of Word

  • 文書を重みなし有向グラフで表現
    • 頂点: 各(unique)term
    • 辺: 固定幅(4ぐらい?)の窓内のtermとの共起
    • 辺の向き: termの出現順序(前から後ろ方向のみ)
      • 多重辺にはしない

TW-IDF

  • TW-IDF(t,d) = tw(t,d) / (1-b+b*|d|/avdl) * log( (N+1) / df(t) )
    • tw(t,d): 文書dのgraph of word表現における頂点tの重み(term weight)
    • b: [0,1]のパラメータ(0.003)
    • N: 文書数
  • tw(t,d)には「入次数」を使うのがよいらしい
    • 他には以下なども考えられたが、計算コストなどの問題から簡単な「次数」を利用
      • closeness(頂点間の最小距離)
      • betweenness(頂点間の最短パスの頂点の出現頻度)
      • eigenvectors(隣接行列のspectral decomposition)
      • PageRank

TF normalization

TFの正規化についても紹介されている。

1から2への変化と100から101への変化を同様に扱うより、前者を大きく扱う方がよかったりする。
以下のようなものがある。

  • concave function(TF_k, TF_l)
    • TF_k(t,d) = (k_1+1)*tf(t,d) / (k_1 + tf(t,d))
    • TF_l(t,d) = 1 + ln(1+ln(tf(t,d)))
  • pivoted document length normalization(TF_p)
    • TF_p(t,d) = tf(t,d) / (1-b+b*|d|/avdl)
  • lower-bounding regularization(TF_δ)
    • TF_δ(t,d) = tf(t,d)+δ if tf(t,d)>0, otherwise 0
      • tf(t,d): ドキュメントdにおけるterm tの頻度
      • k_1: corresponding to the asymptotical maximal gain achievable by multiple occurrences compared to a single occurrence
      • b: [0,1]のパラメータ
      • |d|: 文書の長さ
      • avdl: 全文書における文書の平均の長さ
      • δ: lower bounding gap(1.0)

http://d.hatena.ne.jp/jetbead/20110904/1315147130