COS類似度 - 小宮日記

文章の類似度を計算する場合などにCOS類似度というのが
使われるらしい。

二次元で考えた場合、ベクトルAとベクトルBの類似度は、

COS類似度＝AとBの内積/(norm(A)*norm(B))

normは

my $norm_1 = 0.0;
  map {
    $norm_1 += $_ ** 2
  } values %{$vector_1};
  $norm_1 = sqrt($norm_1);

のように、ベクトルの要素をそれぞれ二乗して積算して、SQRTをとったもの。
二次元の場合は、norm([x,y])=sqrt(x^2+y^2)=距離ですね
（このへんはボナメソのペナルティでもおなじみ。L1norm、L2norm）

内積をノルムで割ってるのは、正規化がかかるためのようです。
ベクトルによって長かったり、短かったりするでしょうから。
ベクトルとベクトルの間の角度が、類似度を表現するわけです。

内積は、高校の数学で習うのかな？

my $inner_product = 0.0;
  map {
    if ($vector_2->{$_}) {
      $inner_product += $vector_1->{$_} * $vector_2->{$_};
    }
  } keys %{$vector_1};

例えば、[1,2]・[3,5]=1*3+2*5
内積を計算できるのはベクトルの次元が同じじゃないとだめ。

2chradioの場合、YahooAPIを用いることで、文章上で重要な単語を10個割り出してmysqlに保存してますので、
この単語のありなしで、記事をベクトルかできているわけです。
実際は、全体での単語の数が未知ですが、
少なくともベクトルは最大でも10次元で考えることになるのか。
どうベクトル化すればいいのかねえ。

キーワードの順位はYahooAPIが返してきたスコアに基づいてるんだよな
YahooAPIの内部では、TFやIDFを計算したり、新語を表現するために名詞を結合したりしてるんでしょうけど。

とりあえず、
本当に単純に類似度を考えるなら、同じ単語を多く含むほど近い文章
とか考えておけばいいんでしょうけど(^^;
Yahoo!APIのスコアが高い上位10個しか残してないから、
normは考えないでも内積だけでいいんではないかと(^^;
要するに、同じ単語があるかないか。その和。
ただ、同じ単語があったばあいに、10個のうちの順位を見てやると
類似度がより正確になりそう。

ダウンロードたけしさんの日記によるとmixiの中の人が作られている
bayonが速いのは、以下が成立するかららしい

ただし、クラスタ中の各要素と中心との類似度をまじめに全て比較するのは計算量も高くなってしまいます。
実際には、この値はクラスタ中のベクトルをすべて足した複合ベクトルの長さと同値になり、
そのため計算量も少なく評価値を求めることができます。

ちょっとこれをやると何故クラスタ分類が速くなるのか
までは理解できませんが(^^;　まだ勉強が足りないっす

bayonやCLUTOが爆速な理由
http://d.hatena.ne.jp/download_takeshi/20100213

コサイン尺度（コサイン類似度）の計算
http://private.ceek.jp/archives/003891.html