LDA による文書集合のクラスタリング
潜在ディリクレ配分法 (Latent Dirichlet Allocation) による文書集合のクラスタリングを試してみました。
LDA の実装は探せば色々と出てくるのですが、今回は plda を利用して実験します。plda のソースコードは下記の URL からダウンロードできます。
実験用のコーパスには wikipedia の「要約」を使います。ダウンロードされるデータは巨大なので、ここから適当に間引いて 5000 記事を利用します。また、極端に短い記事は使いたくないので、内容が 100 文字未満の記事は除外しています。
$ wget http://dumps.wikimedia.org/jawiki/latest/jawiki-latest-abstract.xml $ grep '^<abstract>' jawiki-latest-abstract.xml | sed 's/<[^>]*>//g' >jawiki-latest-abstract.txt $ expr $(awk '{ if (length($0) >= 100) print $0 }' jawiki-latest-abstract.txt | wc -l) / 5000 23 $ awk '{ if (length($0) >= 100) if (++lines % 23 == 0) print $0; }' jawiki-latest-abstract.txt | head -n 5000 >jawiki-latest-abstract-5000.txt $ mecab -Owakati jawiki-latest-abstract-5000.txt >jawiki-latest-abstract-5000-wakati.txt
plda の入力データは term frequency 形式のファイルで与える必要があります。具体例は Downloads ページから取得できる test_data.txt を参照してください。一行が一文書で、各行は「単語 文書内の出現回数」を列挙する形式です。そこで、分かち書きした状態のファイルをこの形式に変換します。慣れている PHP で書いてみました。array_count_values という関数が term frequency の計算そのものなので便利ですね。
<?php while ($line = fgets(STDIN)) { $termFrequencies = array_count_values(explode(" ", trim($line))); print implode(" ", array_map(function ($term, $frequency) { return "$term $frequency"; }, array_keys($termFrequencies), array_values($termFrequencies))) . "\n"; }
出来上がりはこんなファイルになります。
$ head -n 3 jawiki-latest-abstract-5000-tf.txt コンピュータ 1 ゲーム 12 （ 4 ） 4 と 4 は 1 、 6 プレイヤー 1 の 2 行動 1 入力 1 以外 1 全て 1 を 2 コンピューター 1 によって 1 処理 1 さ 1 れる 4 。 5 コンシューマーゲーム 1 テレビ 1 や 1 携帯 1 型 1 アーケード 1 パソコン 1 モバイル 1 など 1 が 1 ある 3 画面 1 ビデオ 2 モニター 1 に 2 出力 1 する 1 ため 1 も 4 呼ば 3 また 2 いわゆる 1 LSI 1 含め 1 て 1 電子 1 場合 1 シンプル 1 こと 1 小山田 1 いく 2 （ 2 おや 1 まだ 1 、 2 1 2 9 1 5 1 6 1 年 1 6月 1 0 1 日 1 - 1 ） 2 は 2 日本 1 の 1 漫画 1 家 1 。 5 長野 1 県 1 小諸 1 市 1 出身 1 ・ 2 在住 1 本名 1 田上 1 勝久 1 た 1 が 1 み 1 かつ 1 ひさ 1 長野工業高等専門学校 1 機械 1 工学科 1 卒業 1 代表 1 作 1 に 1 『 1 す 1 くらっ 1 ぷ 1 ブック 1 』 1 など 1 作品 3 が 6 テレビ 3 アニメ 3 化 2 さ 3 れ 3 た 3 こと 3 ある 3 漫画 2 家 2 一覧 1 （ 1 さくひん 1 か 2 まんが 1 いちらん 1 ） 1 で 1 は 2 、 1 を 2 列記 1 する 2 。 2 原作 1 つき 1 の 3 場合 1 作画 1 担当 1 者 1 記載 1 アポロ 2 計画 2 （ 2 けいかく 1 、 3 Apollo 1 program 1 ） 2 と 1 は 1 アメリカ 1 航空 1 宇宙 2 局 1 NASA 1 による 1 人類 1 初 1 の 3 月 1 へ 1 有人 2 飛行 1 で 1 ある 1 。 2 1 3 9 2 6 2 年 2 から 1 7 1 2 1 にかけて 1 実施 1 さ 1 れ 1 全 1 回 1 月面 1 着陸 1 に 1 成功 1 し 1 た 1
それでは、このコーパスからトピックモデルを学習してみます。plda をビルドして得られる lda がモデル学習プログラムです。今回の実験では、トピック数を 50 個として、ディリクレ分布のパラメータは alpha = 0.1, beta = 0.01 としました。training_data_file が入力ファイル名、model_file が出力ファイル名の指定になります。burn_in_iterations と total_iterations の指定は、最初の 100 反復を捨てて、101 回目から 150 回目までの観測結果の平均を出力するという意味です。なお、トピック数以外の各パラメータは、ソースファイルの lda.cc のコメントに書いてある実行例の数字をそのまま用いているもので、特に検討した値ではありません。alpha については「50 / トピック数」に設定するのがよいという話もあるようですが*1*2、これも今回は気にしていません。
$ lda --num_topics 50 --alpha 0.1 --beta 0.01 \ --training_data_file jawiki-latest-abstract-5000-tf.txt \ --model_file jawiki-latest-abstract-5000.model \ --burn_in_iterations 100 --total_iterations 150
実行が終わると、以下のようなモデルファイルが出力されます。各行は、単語が各トピックから生成された回数を表します。今回は 50 トピックで実行したので、各行に 50 個の数字が並ぶことになります。それぞれの値は 101 回目から 150 回目まで 50 回の観測の平均です。各行の合計はコーパス全体における単語の出現回数に一致します。
$ head -n 3 jawiki-latest-abstract-5000.model コンピュータ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.04 0 0.02 0.02 0 0 0 0 0 0 0 0.1 0 0 0 0 68.12 0 0 0 0 0 0 22.68 0.02 ゲーム 0.02 0 0 0 0 0 0.02 0 0.06 0 0.02 0.02 0 0 0 0 0 0 0 0 0.02 0 0 0.04 0 0 0 0 0 0.02 0 0 0 0 0 0 0.02 0 0 0 0 0.04 0.28 0 0 0 0 0 252.44 0 （ 314.86 330.56 225.52 140.18 244.7 255.44 93.9 127.52 0 0 157.6 100.36 112.12 104.4 159.7 119.4 0 164.72 281.68 158.08 255.7 0.02 820.6 134 153.14 240.88 182.5 50.18 100.76 261.02 59.72 157.26 283.96 246.48 202.84 253.34 163.56 0.02 0 180.4 0 105.84 247.96 61.44 213.3 98.24 228.14 206.5 0.46 0
次に、このモデルのもとで各文書のトピック分布を求めます。これには、plda をビルドして得られる infer を利用します。パラメータの alpha と beta にはモデル学習時と同じ値を指定します。inference_data_file が入力ファイル名、inference_result_file が出力ファイル名の指定になります。model_file には先ほどの学習で得られたモデルファイル名を指定します。burn_in_iterations と total_iterations はモデル学習プログラムと同じ意味です。なお、こちらも各パラメータの値は infer.cc のコメントに書いてあるものを用いています。
$ infer --alpha 0.1 --beta 0.01 \ --inference_data_file jawaiki-latest-abstract-5000-tf.txt \ --inference_result_file jawaiki-latest-abstract-5000.result \ --model_file jawiki-latest-abstract-5000.model \ --burn_in_iterations 10 --total_iterations 15
実行が終わると、以下のようなファイルが出力されます。各行は inference_data_file の同一行に対応しており、その文書から各トピックが生成された回数を表します。
$ head -n 3 jawiki-latest-abstract-5000.result 0 15.2 0.8 0 0 0 0 0 0 0 0 0.2 0 0 0 0 0 0 2 0 7.8 0.6 0 3.4 0 13.2 0 0 0 0 0.8 0 0 0 0 0 0 0.6 0 0 0.2 24.6 0 0.8 0.6 0.8 0 0 21.4 0 2.8 5.8 2.2 0.2 0 0 0 0 0 0 0.6 0 6.4 0.4 0 6.6 1.6 3 0 5 0.2 0 2.2 0 0.2 0 0.2 0 1.2 0 0 0 2.6 0.2 0 0 0 0 0 0 0 0 7 1 0 0.8 7.6 4.2 0 0 0 1.6 0 0 0 0 0 0 0 0 0 0 7.8 13.4 0.2 0 0 0 0 0.2 0 0.2 0 0.8 0 1.4 0.4 0 0 0 0.6 0 0 0.2 0.4 0 0 3.6 0 0 0 0 10.2 0.4 0 0 0 0 23.6 0
ある文書からのトピック生起確率は、各トピックの生成回数にパラメータ alpha を足した数の比として推定できます。これは行指向で簡単に計算できます。
#!/bin/awk -f { total = NF * alpha; for (i = 1; i <= NF; i++) total += $i; for (i = 1; i <= NF; i++) printf("%f%s", ($i + alpha) / total, i == NF ? "\n" : " "); }
これを calc_probability.awk として、たとえば 1 番目のトピックの生起確率が高い順に 10 記事を出力してみます。これは道路や地名に関するトピックでしょうか。
$ awk -f calc_probability.awk -v alpha=0.1 jawiki-latest-abstract-5000.result \ | cut -f1 -d' ' \ | paste - jawiki-latest-abstract-5000.txt \ | sort -nrsk1,1 \ | head -n 10 0.763750 青森県道34号五所川原浪岡線（あおもりけんどう34ごうごしょがわらなみおかせん）は、青森県五所川原市大字原子から青森市浪岡大字下十川に至る主要地方道である。五所川原市大字原子で国道101号から分岐し、五所川原市大字高野を経て、青森市浪岡大字下十川で国道7号に接続する。 0.763750 宮崎県道214号上祝子綱の瀬線（みやざきけんどう214ごう かみほうりつなのせせん）は延岡市北川町川内名上祝子から延岡市北方町日平に至る予定の一般県道。ただし延岡市北川町川内名上祝子（起点）から延岡市北方町上鹿川までの区間は未開通である。 0.706316 桜島二俣町（さくらじまふたまたちょう Sakurajima Futamata-Chō）は、鹿児島県鹿児島市の町名。旧大隅国大隅郡桜島郷二俣村、鹿児島郡西桜島村大字二俣、鹿児島郡桜島町二俣。郵便番号は891-1412。人口は190人、世帯数は79世帯（2010年2月末現在）統計情報 - 鹿児島市ホームページ。。 0.701111 直木町（なおきちょう Naoki-Chō）は、鹿児島県鹿児島市の町名。旧日置郡伊集院郷直木村、日置郡上伊集院村大字直木、日置郡松元町大字直木。郵便番号は899-2705。人口は912人、世帯数は385世帯（2010年2月末現在）統計情報 - 鹿児島市ホームページ。。 0.701000 大分県道537号湯平温泉線（おおいたけんどう537ごう ゆのひらおんせんせん）は、大分県由布市湯布院町大字下湯平から、湯平温泉を経て、大分県玖珠郡九重町大字田野に至る一般県道である。湯平温泉へのアクセス路として、また、大分市方面から大分県道・熊本県道11号別府一の宮線（やまなみハイウェイ）へのバイパスとして利用される。 0.698684 群馬県道291号境木島大間々線（ぐんまけんどう291ごう さかいきじまおおまません）は、群馬県伊勢崎市境木島の群馬県道14号伊勢崎深谷線の「木島三叉路」からみどり市大間々町大間々の群馬県道69号大間々世良田線との三叉路を結ぶ県道である。 0.693846 東京都道43号立川東大和線（とうきょうとどう43ごう たちかわひがしやまとせん）は、東京都立川市羽衣町2丁目から東大和市芋窪に至る主要地方道である。大部分が多摩南北道路4号線（立川東大和線）に属する。 0.689623 佃大橋(つくだおおはし)は､隅田川にかかる橋で､佃大橋通りとも呼ばれる東京都道473号新富晴海線(旧東京都道304号線明石町晴海支線･晴海通り)を通す橋である｡隅田川右岸においては北が東京都中央区湊三丁目､南が中央区明石町｡同左岸では中央区佃一丁目と中央区月島一丁目を分かつ｡地下にて東京地下鉄有楽町線と並行する｡ 0.672152 青森県道19号八戸百石線（あおもりけんどう19ごう はちのへももいしせん）とは、青森県八戸市長苗代（内舟渡交差点＝国道104号・454号交点）とおいらせ町（旧百石町）一川目（国道338号交点）を結ぶ主要地方道。 0.660638 千葉県道53号千葉川上八街線（ちばけんどう53ごう ちばかわかみやちまたせん）は、千葉県千葉市若葉区大草の、国道126号との交点である「大草」交差点を起点とし、八街市八街ほ（五方杭）の国道409号との交点である「千葉川上入口」交差点を終点とする主要地方道である。
他のトピックを選べば、それぞれ特徴を持った記事が得られます。9 番目のトピックで同じことをやってみると、以下のように数学関係の記事が出力されました。
0.719335 数学において、一致の定理(identity theorem)は、局所的に一致する複素解析関数が大域的に一致することを主張する定理である。単連結開領域\mathcal{D}\subset\mathbb{C}で正則な複素関数f(z),g(z)は、領域\mathcal{D}内に集積点を持つ点列の上で一致すれば領域\mathcal{D}全体で一致する。この場合、点とは複素平面上の点である。従って、点列は複素数の数列であると考えてよい。点列が集積点aを持つとは、いかに小さな正の実数\epsilonを選ぼうとも0<|z_k-a|<\epsilonとなる点z_kが点列に含まれることをいう。領域\mathcal{D}内の異なる二点a,b\in\mathcal{D}を結ぶ曲線\gamma\subset\mathcal{D}の上で\forall{z\in\gamma},f(z)=g(z)であれば、z_1=bから始め、曲線に沿ってz_kとaの中間点をz_{k+1}として得る点列\{z_k\}は集積点a\in\mathcal{D}を持ち、f(z_k)=g(z_k)であるから、一致の定理により、領域\mathcal{D}全体で
0.689610 比増殖速度（ひぞうしょくそくど）は、単位時間あたりの細胞量の増加として定義される。単位は、たとえば細胞1グラムあたり1時間あたりのグラム重量(\text{g}\cdot\text{g}^{-1}\cdot\text{h}^{-1})のようになる。
0.642391 数学の、特に測度論の分野におけるボレル測度（ボレルそくど、）とは、次のように定義される測度のことである：X を局所コンパクトなハウスドルフ空間とし、\mathfrak{B}(X) を X の開集合を含む最小のσ-代数とする。このような \mathfrak{B}(X) はボレル集合のσ-代数と呼ばれる。
0.635211 結合次数（けつごうじすう、Bond order）は原子ペア間の結合の数である。例えば窒素分子 N:::N の結合次数は3、アセチレン H:C:::C:HのC-C間の結合次数は3でH-C間のそれは1である。
0.473611 複素変数 z の関数 f(z) が複素平面上の1点 z=c で解析的（analytic）であるとは、c の近傍で z-c の冪級数で表されることを云う。しかし解析関数（かいせきかんすう）という語は場合により多少異なった意味で用いられる。
0.456364 Java Transaction API(JTA)とは、Java EEのAPIの1つであり、XAリソース間の分散トランザクション処理を扱う。JTA は Java Community Processで JSR 907 として開発された仕様である。
0.453175 相関係数（そうかんけいすう、）とは、2 つの確率変数の間の相関（類似性の度合い）を示す統計学的指標である。原則、単位は無く、−1 から 1 の間の実数値をとり、1 に近いときは2 つの確率変数には正の相関があるといい、−1 に近ければ負の相関があるという。0 に近いときはもとの確率変数の相関は弱い。因みに 1 もしくは −1 となる場合は 2 つの確率変数は線形従属の関係にある。
0.451351 thumb|right|220px|固定された回転軸をもつ系に対して、力を作用させた時の物理量の関係。力のモーメント \vec{\tau} と位置ベクトル \vec{r} と力 \vec{F} との関係（上の式）、および運動量のモーメント（角運動量）\vec{L} と位置ベクトル \vec{r} と運動量 \vec{p} との関係（下の式）。
0.445556 支配集合問題（しはいしゅうごうもんだい）は、グラフ理論における有名なNP困難な問題の一つ。与えられたグラフ G(V, E) の頂点集合 V′ (⊆ V) で、V′ に属さない全ての頂点 v について、v の隣接頂点のいずれか一つが V′ に属するような V′ （支配集合）のうち、最小のものを求める問題。
0.441333 数学の分野における両側ラプラス変換（りょうがわラプラスへんかん、）とは、フーリエ変換やメリン変換、通常の片側ラプラス変換などと関係している積分変換の一種である。すべての実数に対して定義される実あるいは複素数値関数を ƒ(t) としたとき、その両側ラプラス変換は積分
