y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

Hellinger 距離による記事間の類似度計算

LDA の用途の一つとして、文書間の類似度の計算があります。今回はこれを試してみたいと思います。

前回の記事で参考にした Blei 先生の教科書によると、文書間の類似度は Hellinger 距離を使って計算できるようです。以下のようなコードを書いて試してみます。先頭行の記事を基準として、その記事と 2 行目以降の各記事との Hellinger 距離をまとめて計算します。

#!/bin/awk -f
(NR == 1) {
  for (i = 1; i <= NF; i++) base[i - 1] = $i;
}
(NR > 1) {
  distance = 0;
  for (i = 1; i <= NF; i++) distance += ($i^(1/2) - base[i - 1]^(1/2))^2;
  print distance;
}

これを calc_hellinger_distance.awk として保存しておき、類似記事を抽出してみます。基準にする記事として、前々回に出現した「青森県道34号五所川原浪岡線」を選びました。記事が似ているほど Hellinger 距離の値は小さくなるので、計算結果を昇順にソートして出力します。

$ grep -n '青森県道34号五所川原浪岡線' jawiki-latest-abstract-5000.txt | cut -f1 -d:
711
$ ./calc_topic_probability.awk -v alpha=0.1 jawiki-latest-abstract-5000.result >probs.tmp
$ (head -n 711 probs.tmp | tail -n 1; cat probs.tmp) \
  | ./calc_hellinger_distance.awk                    \
  | paste - jawiki-latest-abstract-5000.txt          \
  | sort -nsk1,1                                     \
  | head -n 10
0       青森県道34号五所川原浪岡線(あおもりけんどう34ごうごしょがわらなみおかせん)は、青森県五所川原市大字原子から青森市浪岡大字下十川に至る主要地方道である。五所川原市大字原子で国道101号から分岐し、五所川原市大字高野を経て、青森市浪岡大字下十川で国道7号に接続する。
0.140329        埼玉県道223号狭山ヶ丘停車場線(さいたまけんどう223ごう さやまがおかていしゃばせん)は、埼玉県所沢市の狭山ヶ丘駅から、所沢市三ヶ島農協交差点で埼玉県道179号所沢青梅線に接続する一般県道である。
0.171573        直木町(なおきちょう Naoki-Chō)は、鹿児島県鹿児島市の町名。旧日置郡伊集院郷直木村、日置郡上伊集院村大字直木、日置郡松元町大字直木。郵便番号は899-2705。人口は912人、世帯数は385世帯(20102月末現在)統計情報 - 鹿児島市ホームページ。。
0.182667        播但連絡道路(ばんたんれんらくどうろ)は、兵庫県姫路市の姫路JCTから朝来市の和田山ICに至る延長約65.1kmの地域高規格道路(自動車専用道路)。一般国道312号かつ、兵庫県道路公社が管理・運営している一般有料道路である。一般には播但道という略称で呼ばれる。
0.188003        宮崎県道214号上祝子綱の瀬線(みやざきけんどう214ごう かみほうりつなのせせん)は延岡市北川町川内名上祝子から延岡市北方町日平に至る予定の一般県道。ただし延岡市北川町川内名上祝子(起点)から延岡市北方町上鹿川までの区間は未開通である。
0.188976        貝取(かいどり/Kaidori)は、東京都多摩市の地名。地番整理施行地区(貝取一丁目~五丁目)と未施行地区(貝取)があるが、本項目では両方取り上げる。郵便番号は貝取一丁目~五丁目、貝取共に206-0012。当地域の人口は10,082人(2009111日現在、住民基本台帳人口調査による。多摩市調べ)。
0.217182        元赤坂(もとあかさか)は、東京都港区の地名。現行行政地名は元赤坂一丁目及び元赤坂二丁目。201231日現在の人口は56520123月(町丁目別人口・世帯数(赤坂地区総合支所管内))。郵便番号は107-00510.220052        桜島二俣町(さくらじまふたまたちょう Sakurajima Futamata-Chō)は、鹿児島県鹿児島市の町名。旧大隅国大隅郡桜島郷二俣村、鹿児島郡西桜島村大字二俣、鹿児島郡桜島町二俣。郵便番号は891-1412。人口は190人、世帯数は79世帯(20102月末現在)統計情報 - 鹿児島市ホームページ。。
0.240145        東京都道43号立川東大和線(とうきょうとどう43ごう たちかわひがしやまとせん)は、東京都立川市羽衣町2丁目から東大和市芋窪に至る主要地方道である。大部分が多摩南北道路4号線(立川東大和線)に属する。
0.241302        愛知県道40号名古屋蟹江弥富線(あいちけんどう40ごう なごやかにえやとみせん)は、愛知県名古屋市中川区から海部郡蟹江町を経由し、弥富市に至る主要地方道である。ほぼ全線に渡って東名阪自動車道に並行している。

このように、似ている記事がうまく抽出されました。先頭行は基準の記事そのものなので、Hellinger 距離が 0 になっています。