近似を検索するアルゴリズムを変える

ruby collective intelligence

先日のエントリに載せたコードは，似たものを探すアルゴリズムを切り換えることができる。top_matches も get_recommendations もパラメータの最後にアルゴリズムに使うメソッド名をシンボルとして渡せる。デフォルトでは sim_pearson が使われるが，ブックマークなどでは sim_distance の方が向いていることに気づいた。
sim_distanceは評価点の「距離」を計算する。複数の評価対象アイテム（例えば映画a，映画b，映画c…）があるとする。このうち任意の2つのアイテムを取り出してみる。これを仮に映画mと映画nとする。X軸に映画mの評価点，Y軸に映画nの評価点をとり，評価者Aさんの評価（例えば3点と4点）をプロットする。続いてBさん，Cさん…と全ての評価者の評価をプロットしていく。もし評価が近似しているならば，プロットされた点は近くにあるはずだ。全ての点について他の点との距離を計算して，一番近いものを探すことができる。この場合は2つのアイテムで考えたが，n個のアイテムに関してはn次元に拡張すればよいだけで，座標の差の自乗の総和のルートをとると計算できる。
この方式の欠点はバイアスを考慮できないこと。つまり傾向はすごくよく似ているが"全体に"評価の辛い評価者と，評価の甘い評価者では座標が離れるので，似ていないことになってしまう。そこで使うのが「ピアソンの相関係数」である（つーか，本読んで知った）。簡単にいえば，X軸に評価者Aのスコア，Y軸に評価者Bのスコアをとり，各映画ごとにスコアをプロットする（例えば映画aについてAが5，Bが3を付けれていれば(5,3)にプロットする）。こうしてできた点の集合がどれだけ一本の直線上に集まるかどうかを調べるのが，この計算式になる。
先日は sim_pearson を使っていたが，ブックマークはしてる/してないの二値評価なのでバイアスが混じる可能性は無い。そこで sim_distance で計算してみた。

--- top_matches ---
0.03 : w650
0.03 : neko-note
0.03 : kixx_me_tender
0.03 : leechan
0.02 : hiroyadoraemon
--- get_recommendations ---
0.237793441151896 : http://code.nanigac.com/
0.229834925835669 : http://d.hatena.ne.jp/amachang/20071010/1192012056
0.139690916622098 : http://www.imgsrc.co.jp/~kuriyama/prototype/prototype.js.html
0.0983419384518453 : http://www.ideaxidea.com/archives/2007/10/windows_pc.html
0.0983419384518453 : http://fnya.cocolog-nifty.com/blog/2006/08/ajax_76d4.html
0.0768585771327981 : http://e0166.blog89.fc2.com/blog-entry-307.html
0.0764881743514352 : http://www.future-planning.net/x/modules/news/article.php?storyid=2733
0.0764881743514352 : http://lifehacking.jp/2007/10/time-saving-tips/
0.0655612923012302 : http://yusukebe.com/archives/07/10/15/174049.html
0.0655612923012302 : http://www.a-windows.com/
--- get_recommendations(xformed) ---
http://code.nanigac.com/
0.390 : http://netaxtane.blog111.fc2.com/blog-entry-297.html
0.336 : http://www.asahi.com/life/update/1011/TKY200710110446.html
0.336 : http://wiredvision.jp/news/200710/2007101023.html
0.336 : http://mainichi.jp/select/wadai/news/20071013k0000m040154000c.html
0.336 : http://itpro.nikkeibp.co.jp/article/COLUMN/20070820/279907/

あ，やっぱり top_matches の評価点はたいして高くないですね。「似たユーザー」なんて簡単に見つからないってことか。