あけましておめでとうございます。すでに年が変わってからだいぶ経った気もしますが、リハビリも兼ねて今日は集合知プログラミングの第二章を題材に協調フィルタリング (レコメンデーション) について書いてみます。
協調フィルタリングを大雑把に説明すると、多くの人数の集団を検索し、ある対象の好みによく似た小集団を発見する方法です。大きく分けて、ある人に似た他の人を探し出すにはユーザーベース、あるアイテムを選んだ人による重み付けスコアを算出することによるアイテムベースなどといった方法があります。
元データ
ある会社 A 社の社内食堂でランチをした人にここ 10 日間ほどの感想を 5.0 を満点として採点してもらいました。
それぞれのメニューに対する評点は次の通りでした。なお一度も食べなかったメニューは -- となっています。
| 名前 | カレー | ラーメン | チャーハン | 寿司 | 牛丼 | うどん |
|---|---|---|---|---|---|---|
| 山田さん | 2.5 | 3.5 | 3.0 | 3.5 | 2.5 | 3.0 |
| 田中さん | 3.0 | 3.5 | 1.5 | 5.0 | 3.0 | 3.5 |
| 佐藤さん | 2.5 | 3.0 | -- | 3.5 | -- | 4.0 |
| 中村さん | -- | 3.5 | 3.0 | 4.0 | 2.5 | 4.5 |
| 川村さん | 3.0 | 4.0 | 2.0 | 3.0 | 2.0 | 3.0 |
| 鈴木さん | 3.0 | 4.0 | -- | 5.0 | 3.5 | 3.0 |
| 下林さん | -- | 4.5 | -- | 4.0 | 1.0 | -- |
みな味の好みがバラバラで、同じメニューでも人によって採点が高かったり低かったりしているようです。
似ている人を探す
何らかの対象に対して人々の評価が集まったとき、その傾向が似ている程度を決定する基準が必要になります。これを 類似性スコア (Similarity score) と言います。類似性スコアの算出にはさまざまな方法がありますが、上記の集合知プログラミングではユークリッド距離とピアソン相関係数が取り上げられています。いずれも 2 つの確率変数の間の関連度合いを表す尺度であり -1 から 1 の範囲を取ります。
ユークリッド距離
ここでは 平方ユークリッド距離 (Squared Euclidean distance) を使います。これはそれぞれの軸の上での差を求め、その二乗を累計するものです。つまり数式では
d^2(p-q) = (p_1 - q_1)^2 + (p_2 - q_2)^2 + ... + (p_n - q_n)^2
となります。これを Ruby のコードで表すと
def sim_distance(prefs, person1, person2)
shared_items_a = shared_items_a(prefs, person1, person2)
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 shared_items_a(prefs, person1, person2)
prefs[person1].keys & prefs[person2].keys
end
たとえば山田さんと田中がどれくらい似ているかを計算すると 0.14814814814814814 点となります。
ピアソン相関係数
ピアソンの相関係数 (Pearson correlation coefficient) は、データが正規化されていないような状況でユークリッド距離よりも良い結果を得られることが多いとされています。
なぜなら、ある評価者 A が辛口の評価を、評価者 B が甘口の評価をする傾向があったとします。しかしそれぞれのアイテムに対する評価の差に相関があった場合、これが高い相関係数を示すという特徴があるためです。
(例)
A さん「ラーメンはまずまずで 3 点だがカレーとチャーハンはイマイチだから 1.5 点だな……。」
B さん「ラーメンはうまくて 5 点だがカレーとチャーハンはふつうで 3.5 点だな……。」
↑評価の傾向が似ている (それぞれのアイテムの差が同じ) ため高い相関を示す。
定義式は次の通りです。
\rho_P = \frac{\mathrm{E}_{X,Y}[(X-\mu_X)(Y-\mu_Y)]}{\sqrt{\mathrm{E}_X[(X-\mu_X)^2]}\sqrt{E_Y[(Y-\mu_Y)^2]}} \\
ただし \\
\mu_X=E_X[X], \mu_Y=E_Y[Y]
Ruby では
def sim_pearson(prefs, person1, person2)
shared_items_a = shared_items_a(prefs, person1, person2)
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
}
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
となります。
たとえば山田さんと田中がどれくらい似ているかを計算すると 0.39605901719066977 点となります。
類似度を算出する
下林さんに食の好みが似ている人は誰でしょうか。調べてみましょう。
# データをハッシュで持たせておく
def top_matches(prefs, person, n=5, similarity=:sim_pearson)
scores = Array.new
prefs.each do |key,value| # ハッシュを each して
if key != person
# 類似度算出アルゴリズムのメソッドに人名とアイテム、スコアを送信する
scores << [__send__(similarity,prefs,person,key),key]
end
end
scores.sort.reverse[0,n] # スコアの降順にソートして返却
end
p top_matches(critics_ja, '下林')
下林さんに似ている人は
- 1 位 山田さん 0.9912407071619299 点
- 2 位 川村さん 0.9244734516419049 点
- 3 位 鈴木さん 0.66284898035987 点
となりました。
おすすめのメニューを探す
では次に下林さんにおすすめのメニューは何でしょうか。
これを見つけるために、下林さんに似た人を探しその中から下林さんが食べていないメニューを探し出すのは少々面倒です。
この問題を解決するには食べた人に順位付けをした重み付けスコアを算出することでアイテムにスコアを付ける方法が有効です。
# person 以外の全ユーザーの評点の重み付き平均を使い person への推薦を算出する
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 # 0 以下のスコアは無視する
prefs[other].each do |item, val|
# まだ食べてないメニューの得点のみを算出する
if !prefs[person].keys.include?(item) || prefs[person][item] == 0
# 類似度 * スコアを合計する
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
p get_recommendations(critics_ja, '下林')
これにより下林さんにおすすめのメニューは
- 1 位 うどん 3.3477895267131017 点
- 2 位 カレー 2.8325499182641614 点
- 3 位 チャーハン 2.530980703765565 点
となりました。
似ているアイテムを探す
最後にメニュー同士で似ているものを探してみましょう。それでは寿司に似ているメニューは何でしょうか。
これは元データの逆行列を求めれば良いわけですから簡単です。
# 逆行列を求めるメソッド
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
menu = transform_prefs(critics_ja)
p top_matches(menu, '寿司')
これにより寿司に似ているメニューは
- 1 位 牛丼 0.6579516949597695 点
- 2 位 カレー 0.4879500364742689 点
- 3 位 ラーメン 0.11180339887498941 点
となりました。
まとめ
今回の記事のソースコードはこちらです。
集合知プログラミングをもとに協調フィルタリングの実装によって推薦をおこなう例を説明しました。