« チャーハンの素を使わずにチャーハンを作る | メイン | 少し真面目に実装 »

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

トラックバック

コメント