« チャーハンの素を使わずにチャーハンを作る | メイン | 少し真面目に実装 »
2008年11月04日
コサイン尺度（コサイン類似度）の計算
文書間の類似度を求める方法の一つとして、コサイン尺度が挙げられます。コサイン尺度とは、2つのベクトルのなす角度であり、文書をベクトル化することにより、文書間の類似度を求めることが出来ます。
sub cosine_similarity {
my ($vector_1, $vector_2) = @_;
my $inner_product = 0.0;
map {
if ($vector_2->{$_}) {
$inner_product += $vector_1->{$_} * $vector_2->{$_};
}
} keys %{$vector_1};
my $norm_1 = 0.0;
map {
$norm_1 += $_ ** 2
} values %{$vector_1};
$norm_1 = sqrt($norm_1);
my $norm_2 = 0.0;
map {
$norm_2 += $_ ** 2
} values %{$vector_2};
$norm_2 = sqrt($norm_2);
return ($norm_1 && $norm_2) ? $inner_product / ($norm_1 * $norm_2) : 0.0;
}
Perl で書いてみるとこんな感じかな。ハッシュのリファレンスでベクトルを表現し、引数として受け取ります。返値は計算したコサイン尺度となります。ベクトルの各要素の値が0以上であるならば、コサイン尺度は 0 から 1 の値を取り、1に近いほど類似性が高いことを示します。
my $vector_1 = {
'日本' => 1,
'今日' => 3,
'高校' => 2,
'国語' => 1,
};
my $vector_2 = {
'日本' => 2,
'明日' => 1,
'大学' => 1,
'数学' => 1,
};
print cosine_similarity($vector_1, $vector_2);
実際の利用例はこんな感じ。文書のベクトルには、出現した単語数を利用すると良いと思います。
卒業研究では、ウェブページ内の重要箇所特定（本文抽出）に取り組んでいるのですが、コサイン尺度は、重要箇所候補の重要度を求めるために利用します。一先ず、参照論文 Automatic Identification of Informative Sections of Web Pages の ContentExtractor を実装しているのですが、実験結果に書かれている実行速度が出ない…。重要箇所候補数を載せておいて欲しかったかな（区切りとなるタグもあやふやですし）。プロファイラ Devel::DProf, Devel::SmallProf で調べてみると、この類似度計算がボトルネックになっていることが判っています（呼び出し回数が多いというのもある）。ハッシュ操作の keys, values で詰まる感じ。他の類似度計算手法も調査中。
【関連情報】
・Cosine similarity - Wikipedia
http://en.wikipedia.org/wiki/Cosine_similarity
【関連商品】
・情報検索アルゴリズム （北 研二, 津田 和彦, 獅々堀 正幹）
2008年11月04日 22:32 | Programming