キーワード抽出アルゴリズム - KeyGraph

KeyGraphというキーワード抽出アルゴリズムの説明を書いてみる。ただ自分の知識をまとめたいだけだけど。結構仕組みはシンプルなので、理解しやすいはず。

概念

まず、細かい用語などは置いておき、雰囲気だけを…。

KeyGraphでは文章を『主題』と『土台』に分けて考える。『主題』は『土台』と共に出現する可能性が高い。これは『主題』を説明するうえで『土台』を利用することが多いからだ。

つまり『主題』を抽出する前に『土台』を抽出し、これらと同時に出現する語を『主題』とするわけだ。

用語

共起度: 語Xと語Yが共に出現する回数（ここでは一貫して『同一の文に現われるときに共起したと判断する』）。

詳細

図が無いので、分かりずらい点もあるかと思うが、勘弁。

土台となる語の集合は単純に出現頻度が上位定数個のものとする。ただし、不要語（Stop Word）*1はあらかじめ省く必要がある。次に、出来上がった土台語集合の各語の共起度を調べる。この共起度が任意の閾値以上になるものを辺、各土台語をノードとするグラフGを作成する。すると、このグラフは重みつき無指向グラフになり、辺で結ばれた語は共起度が高いことを示す。

次に、土台語グラフの中で極大連結部分グラフのみを残して辺を刈り込む。この部分の説明は参考1に簡潔に書かれているので引用させてもらう。

グラフG中の対になるノードwi,wjを結ぶ枝に対して、この枝を切り放しても他の枝に遷移することでwiからwjへ到達できる場合は枝をそのまま残し、到達できない場合はこの枝を切断する。
情報検索アルゴリズムP.46-47より

これで土台の準備は完了だ。この段階で土台グラフは極大部分グラフに分割されて、小さいグラフの集合となる。このそれぞれのグラフをPGとする。各PGは{a, b, c, d}のように複数の語の集合になっているが、集合が一語によるものでもグラフPGとして扱う。

ここで主題の抽出にとりかかる。主題語の候補は文章中に現われる全ての語から不要語を取り除いたものであるので、土台語も含まれる。主題語の候補をwとする。主題となる語は土台によって強く支えられる語なので、土台に支えられる力を定義する必要がある。この支えられる力をPGとwとの共起度とする。つまり、同一の文内にwとPG内のいづれか（当然 w 以外）が存在する回数だ。この結果のうち上位定数個の語を先ほどの土台グラフに追加する（共起度を重みとする辺も追加）。

以上の過程を語数分繰り返しできたグラフ内のノードのうち共起度の合計が上位のものを主題を示す語（キーワード）とする。

以上がKeyGraphの説明だ。式・記号のたぐいがほとんど無いので逆分かりづらいかもしれない。機会があれば書き直してみるつもり。

参考1：情報検索アルゴリズム著：北研二・津田和彦・獅々堀正幹

*1:不要語とは「あの」や「それ」といった検索語として不適切なものである。英語ではtheやaなどがこれにあたる。