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)
- TF_δ(t,d) = tf(t,d)+δ if tf(t,d)>0, otherwise 0
