集合知プログラミング 2章 - 類似度計算の比較

id:plasticscafe が「集合知プログラミング」をPythonからScalaに翻訳しながら写経していくというので，
~~尻馬に乗って自分もやった気になってみよう~~ ちょっとお手伝いがてら自分もやってみました．

まとめ Scalaで集合知プログラミング

集合知プログラミング

作者: Toby Segaran,當山仁健,鴨澤眞夫
出版社/メーカー: オライリージャパン
発売日: 2008/07/25
メディア: 大型本
購入: 91人クリック: 2,220回
この商品を含むブログ (267件) を見る

本題

「集合知プログラミング」2章のエクササイズに

Tanimoto係数について調査、検討してみる

というのがあるそうなので，コサイン類似度と比較してみました*1．
以下，勘に頼る部分が大きいので詳しい人からコメントほしいっ！

数式で比較

比較するデータの組を下のようにn個ずつのベクトル（配列）として考えていきます．
$X = [x_1, x_2, ...., x_n]$ , $Y = [y_1, y_2, ..., y_n]$

Tanimoto係数は実数版とバイナリ*2版があるそうです*3．

実数版Tanimoto係数

$T_c = \frac{\sum{x_k y_k}}{\sum{x^{2}_{k}} + \sum{y^{2}_{k}} - \sum{x_k y_k}}$

分子 => 「X，Yの内積（要素同士のかけ算の和）」
分母 => 「X，Yの要素の2乗和を足して，そこからX，Yの内積を引いたもの」

バイナリ版Tanimoto係数

$T_b = \frac{|X \cap Y|}{ |X| + |Y| - |X \cap Y|}$

こちらは集合の要素の数で計算します．
例えば，
$|X| = 5 \Rightarrow [0,1,0,1,1,0,1,0,1]$

どちらも最小で0，完全一致のとき最大1の範囲をとる係数です．
で，バイナリ版を0と1の要素の配列と考えると実数版でまとめられます．
# 分母は論理積の和，分母の各ベクトルの和は要素が1の二乗の和

コサイン類似度

$\frac{\sum{x_k y_k}}{ \sqrt{\sum{x^{2}_{k}}} \sqrt{\sum{y^{2}_{k}}} }$

コサイン角で類似度を表現したものなので，

分子 => 「X，Yの内積」
分母 => 「XとYのベクトルの大きさの積」

という構成です．
要素の値を正に限ると，最小で0，最大で1の範囲をとることがわかります．
# 0度〜90度のコサイン

比べてみると...

分子が同じ式なので，分母の大きさを比べれば性能がわかりますね．
それぞれの項が正なので，相加相乗平均を考えてみます．

相加相乗平均

$\frac{a + b}{2} \geq \sqrt{a}\sqrt{b}$

この不等式のa, bを次のように考えてみると，
$a \Rightarrow \sum{x^{2}_{k}}$ , $b \Rightarrow \sum{y^{2}_{k}}$

Tanimoto係数の分母「X，Yの要素の2乗和」がコサイン類似度の分母の2倍以上の大きさだと考えられます．
また，Tanimoto係数の分母にある「X，Yの内積」は，XとYが一致したときに最大値をとる*4ので，

Tanimoto係数の分母 $\geq$ コサイン類似度の分母

となりそう*5．
よって，類似度の値は
Tanimoto係数 $\leq$ コサイン類似度
と考えられそうです．

確かめてみる

Ruby で類似度の式を実装して比べてみます*6．
サンプルのデータはScalaで集合知プログラミングその6 から拝借してRubyのhashに書き換えました．

{映画タイトル => { ユーザ　=> 評価値}, ....}

というデータ構成です．~~各映画タイトルへの評価はみな同じユーザが行っています．~~
あとでよく見たらユーザの構成がバラバラでした．
今回検証したプログラムを使うと二乗和部分が不正確で問題ありですが
2つの類似度を比較することには影響はないです．

サンプルデータ

movies = {
  'Lady in the Water' => {
    'Lisa Rose' => 2.5,
    'Jack Matthews' => 3.0,
    'Michael Phillips' => 2.5,
    'Gene Seymour' => 3.0,
    'Mick LaSalle' => 3.0
  },
  'Snakes on a Plane' => {
    'Jack Matthews' => 4.0,
    'Mick LaSalle' => 4.0,
    'Claudia Puig' => 3.5,
    'Lisa Rose' => 3.5,
    'Toby' => 4.5,
    'Gene Seymour' => 3.5,
    'Michael Phillips' => 3.0
  }, 
  'Just My Luck' => {
    'Claudia Puig' => 3.0,
    'Lisa Rose' => 3.0,
    'Gene Seymour' => 1.5,
    'Mick LaSalle' => 2.0
  }, 
  'Superman Returns' => {
    'Jack Matthews' => 5.0,
    'Mick LaSalle' => 3.0,
    'Claudia Puig' => 4.0,
    'Lisa Rose' => 3.5,
    'Toby' => 4.0,
    'Gene Seymour' => 5.0,
    'Michael Phillips' => 3.5
  }, 
  'The Night Listener' => {
    'Jack Matthews' => 3.0,
    'Mick LaSalle' => 3.0,
    'Claudia Puig' => 4.5,
    'Lisa Rose' => 3.0,
    'Gene Seymour' => 3.0,
    'Michael Phillips' => 4.0
  }, 
  'You Me and Dupree' => {
    'Jack Matthews' => 3.5,
    'Mick LaSalle' => 2.0,
    'Claudia Puig' => 2.5,
    'Lisa Rose' => 2.5,
    'Toby' => 1.0,
    'Gene Seymour' => 3.5
  }
}

サンプルデータがHashなので，計算はHashクラスに実装してみます*7．

計算プログラム

class Hash
  # 二乗和
  def sum_square
      self.inject(0.0){|sum, (k,v)| sum + (v ** 2)}
  end

  # 内積
  def inner_product(other)
      self.inject(0.0){|sum, (k,v)| sum +  (v  * other[k].to_f)}
  end

  # 実数Tanimoto係数
  def tanimoto(other)
      inner_product = self.inner_product(other)
      inner_product / (self.sum_square + other.sum_square - inner_product)
  end

  # コサイン類似度
  def cosine_similarity(other)
      self.inner_product(other) / Math.sqrt(self.sum_square * other.sum_square)
  end
end

確認

映画の類似度を総当たりで計算して，コサイン類似度とTanimoto係数の差をとってみました．
（実装に間違いがなければ）やはりコサイン類似度の方が大きい値になっているようです*8．

p movies.inject(Hash::new){|h1, (k1, v1)|
  h1[k1] =  movies.inject(Hash::new){|h2, (k2, v2)|
    h2[k2] =  (v1.cosine_similarity(v2) - v1.tanimoto(v2) >= 0)? true : false
    h2
  }
  h1
}

#=> {
  "Snakes on a Plane"=>{
    "Snakes on a Plane"=>true,
    "Superman Returns"=>true,
    "The Night Listener"=>true,
    "Lady in the Water"=>true,
    "You Me and Dupree"=>true,
    "Just My Luck"=>true
  },
  "Superman Returns"=>{
    "Snakes on a Plane"=>true,
    "Superman Returns"=>true,
    "The Night Listener"=>true,
    "Lady in the Water"=>true,
    "You Me and Dupree"=>true,
    "Just My Luck"=>true
  },
  "The Night Listener"=>{
    "Snakes on a Plane"=>true,
    "Superman Returns"=>true,
    "The Night Listener"=>true,
    "Lady in the Water"=>true,
    "You Me and Dupree"=>true,
    "Just My Luck"=>true
  },
  "Lady in the Water"=>{
    "Snakes on a Plane"=>true,
    "Superman Returns"=>true,
    "The Night Listener"=>true,
    "Lady in the Water"=>true,
    "You Me and Dupree"=>true,
    "Just My Luck"=>true
  },
  "You Me and Dupree"=>{
    "Snakes on a Plane"=>true,
    "Superman Returns"=>true,
    "The Night Listener"=>true,
    "Lady in the Water"=>true,
    "You Me and Dupree"=>true,
    "Just My Luck"=>true
  },
  "Just My Luck"=>{
    "Snakes on a Plane"=>true,
    "Superman Returns"=>true,
    "The Night Listener"=>true,
    "Lady in the Water"=>true,
    "You Me and Dupree"=>true,
    "Just My Luck"=>true
  }
}

単純な計算結果

p movies.map{|k1, v1| movies.map{|k2, v2| v1.tanimoto(v2)}}
#=> [[1.0, 0.746153846153846, 0.954233409610984, 0.585014409221902, 0.671641791044776, 0.389204545454545], [0.746153846153846, 1.0, 0.767058823529412, 0.661710037174721, 0.667883211678832, 0.519685039370079], [0.954233409610984, 0.767058823529412, 1.0, 0.573604060913706, 0.68, 0.346987951807229], [0.585014409221902, 0.661710037174721, 0.573604060913706, 1.0, 0.689119170984456, 0.39344262295082], [0.671641791044776, 0.667883211678832, 0.68, 0.689119170984456, 1.0, 0.577380952380952], [0.389204545454545, 0.519685039370079, 0.346987951807229, 0.39344262295082, 0.577380952380952, 1.0]]
p movies.map{|k1, v1| movies.map{|k2, v2| v1.cosine_similarity(v2)}}
#=> [[1.0, 0.864571736660863, 0.979878059993656, 0.815688728171367, 0.876768308983898, 0.702573340933072], [0.864571736660863, 1.0, 0.892170154676181, 0.832995274019294, 0.830515089501848, 0.788386434103751], [0.979878059993656, 0.892170154676181, 1.0, 0.836486445274097, 0.91530229603964, 0.680229773816739], [0.815688728171367, 0.832995274019294, 0.836486445274097, 1.0, 0.816335074333143, 0.581591547095], [0.876768308983898, 0.830515089501848, 0.91530229603964, 0.816335074333143, 1.0, 0.759855876058712], [0.702573340933072, 0.788386434103751, 0.680229773816739, 0.581591547095, 0.759855876058712, 1.0]]

まとめ

コサイン類似度の方がTanimoto係数より大きい評価値になる．
生データが個数のみで構成される場合，バイナリ版Tanimoto係数が使えそう

おまけの収穫

HashもEnumerableだから... とinjectを試してみたところ，

self.inject(0.0){|sum, (k, v)| sum + (v ** 2)}

のように，括弧で括るとキーと値も参照できることがわかったのが収穫でした．

はてなにTeX記法があるのを知ったのも思わぬ収穫！

*1: エクササイズの内容は => http://d.hatena.ne.jp/plasticscafe/20110121/1295582338

*2:0と1のみで構成されるデータ

*3:参考: http://nlp.nagaokaut.ac.jp/tanimoto%E4%BF%82%E6%95%B0

*4:参考: http://www.infra.kochi-tech.ac.jp/takagi/Survey1/13InnerProduct.pdf

*5:詳しい証明はできませんが、ざっくりと．収束速度で比較すればいいのかなぁ？

*6:自分にとって書きやすい言語なので

*7:データ量が多い場合Array使う方が軽快でしょうね．また，Vectorクラスを使えれば内積などは実装しなくてよい....

*8:今思えばUnitTestを利用できればよかったのかも...