"Collective Intelligence"のサンプルをrubyに移植してみた

Programming Collective Intelligence: Building Smart Web 2.0 Applications

「集合知」を解説するこの本にはいろんな実例とサンプルが出てくる。サンプルは python なので ruby に書き換えてみた。書き換えたのは第二章の "Making Recommendations" の一部です。なんらかのアイテム（本とか映画とか）とその評価（Amazonレビューの★とか）を複数の人間が行った場合に，その情報を元に「似た傾向の評価者」を探し，似た傾向の評価者のリストから自分が未評価のアイテム（つまり未読の本とか未見の映画とか）を取得することで，お勧めを作っている。
ちょっと長いんだけど，まず recommendation.rb。

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

# 二者のアイテム間の距離による算出
def sim_distance(prefs, person1, person2)
  # 共通アイテムをくくりだす
  shared_items_a = shared_items_a(prefs, person1, person2)
  # 共通アイテムが無ければ0
  return 0 if shared_items_a.size == 0
  # 各アイテムの差の自乗の総和を計算する
  sum_of_squares = shared_items_a.inject(0) {|result, item| result + (prefs[person1][item]-prefs[person2][item])**2 }
  return 1/(1+sum_of_squares)
end

# 二者のアイテムが同一直線に乗るかどうかで算出
def sim_pearson(prefs, person1, person2)
  # 共通アイテムをくくりだす
  shared_items_a = shared_items_a(prefs, person1, person2)
  # 共通アイテムが無ければ0
  n = shared_items_a.size
  return 0 if n == 0
  # 共通アイテムにあるすべての評価を加算
  sum1 = shared_items_a.inject(0) {|result,si| result + prefs[person1][si]}
  sum2 = shared_items_a.inject(0) {|result,si| result + prefs[person2][si]}
  # 共通アイテムにあるすべての評価の自乗を加算
  sum1_sq = shared_items_a.inject(0) {|result,si| result + prefs[person1][si]**2}
  sum2_sq = shared_items_a.inject(0) {|result,si| result + prefs[person2][si]**2}
  # productsの総計
  sum_products = shared_items_a.inject(0) {|result,si| result + prefs[person1][si]*prefs[person2][si]}

  # ピアソン値を計算
  num = sum_products - (sum1*sum2/n)
  den = Math.sqrt((sum1_sq - sum1**2/n)*(sum2_sq - sum2**2/n))
  return 0 if den == 0
  return num / den
end

# 傾向の似ている順に評価者を取得
# 取得数，近似判定関数は指定可能とする
def top_matches(prefs, person, n=5, similarity=:sim_pearson)
  scores = Array.new
  prefs.each do |key,value|
    # 自分じゃない評価者を計算
    if key != person then
      scores << [__send__(similarity,prefs,person,key),key]
    end
  end
  scores.sort.reverse[0,n]
end

# ある評価者用のお勧めアイテムを計算する
def get_recommendations(prefs, person, similarity=:sim_pearson)
  totals_h = Hash.new(0)
  sim_sums_h = Hash.new(0)

  prefs.each do |other,val|
    next if other==person
    sim = __send__(similarity,prefs,person,other)
    next if sim <= 0
    prefs[other].each do |item, val|
      if !prefs[person].keys.include?(item) || prefs[person][item] == 0 then
        # 似てる度数*スコア
        totals_h[item] += prefs[other][item]*sim
        # 似てる度数の総和
        sim_sums_h[item] += sim
      end
    end
  end

  # 正規化したリストの作成
  rankings = Array.new
  totals_h.each do |item,total|
    rankings << [total/sim_sums_h[item], item]
  end
  rankings.sort.reverse
end

# {'name1'=>{item1=>score1,item2=>score2..}...} というハッシュを
# {'item1'=>{name1=>score1,name2=>score2..}...} というハッシュに変換する
def transform_prefs(prefs)
  result = Hash.new
  prefs.each do |person,score_h|
    score_h.each do |item,score|
      result[item] ||= Hash.new
      result[item][person] = score
    end
  end
  result
end

# 共通アイテムの取得
def shared_items(prefs, person1, person2)
  # 共通アイテムをくくりだす
  shared_items_h = Hash.new
  prefs[person1].each do |k,v|
    shared_items_h[k] = 1 if prefs[person2].include?(k)
  end
  shared_items_h
end

# 共通アイテムの取得その2
# shared_itemsと異なり，共通のキーの配列を返す
def shared_items_a(prefs, person1, person2)
  prefs[person1].keys & prefs[person2].keys
end

if $0 == __FILE__ then
  p critics
  p sim_distance(critics, 'Lisa Rose', 'Gene Seymour')
  p sim_pearson(critics, 'Lisa Rose', 'Gene Seymour')
  p top_matches(critics, 'Toby')
  p get_recommendations(critics, 'Toby')
  movies = transform_prefs(critics)
  p movies
  p top_matches(movies, 'Superman Returns')
end

使い方はこんな感じ。まず critics はテスト用の評価データ。{name=>{item1=>score1,..},name2=>{item2=>score2,..}...} という形式になっている。sim_distance と sim_pearson は，それぞれ異なるアルゴリズムで二者の近似の度合いを計算する。

irb(main):002:0> sim_distance(critics, 'Lisa Rose', 'Gene Seymour')
=> 0.148148148148148

値は1になれば最大（もっとも近似している）。top_matches は，ある評価者に一番似ている他の評価者を計算する関数。

irb(main):003:0> top_matches(critics, 'Toby')
=> [[0.99124070716193, "Lisa Rose"], [0.924473451641905, "Mick LaSalle"], [0.893405147441565, "Claudia Puig"], [0.66284898035987, "Jack Matthews"], [0.381246425831512, "Gene Seymour"]
]

Toby に一番似ているのは Lisa Rose であることが分かる。get_recommendations は，その評価者に一番似ている人の評価リストから，まだ未見のものを探してくれる。つまり「お勧め」機能。

irb(main):004:0> get_recommendations(critics, 'Toby')
=> [[3.3477895267131, "The Night Listener"], [2.83254991826416, "Lady in the Water"], [2.53098070376556, "Just My Luck"]
]

"The Night Listener" がお勧めであることが分かります。