Ruby: 最近傍法による推奨アルゴリズムを実装する（翻訳）
Webのユーザーに関連度の高いコンテンツを自動的におすすめする機能は、Webの多くの機能を成功に導くうえで欠かせません。そのために多種多様な手法が利用されており、最大規模のWebサイトや企業では、非常に高度な技術を取り入れて推奨機能を最適化しています。本記事では、基本原理に基づいた効果的な推奨システムをRubyで構築する方法について解説します。
🔗 はじめに
以前の記事では、距離測定を導入してRubyで実装する方法を紹介しました。そのときに、それらの距離測定アルゴリズムは最近傍モデルや推奨システムの生成に活用できると述べました。本記事では、そうしたアイデアをさらに発展させて、そうしたメトリクスに基づいた推奨システムの開発を目指します。
本記事で実装するアルゴリズムは、Toby Segaranが『Collective Intelligence』で示したPython版にインスパイアされています。
これらのアルゴリズムを適用してRubyで定式化し、ホグワーツ魔法魔術学校の学生たちの適当な成績データセットに適用します。このデータを用いて、学生が受講していないクラスの予測成績を生成してみます。データセットは適当ですが、示しているアルゴリズムは健全であり、本物のデータセットに適用してもよい正当性を備えています。
それではやってみましょう！
🔗 ホグワーツのデータを導入する
ここで使うデータセットは、CLASS_SCORESというRubyの静的なハッシュ内で定義されています。完全なデータについてはGitHubで参照できますが、ここではフォーマットの説明用に一部を抜粋したものを転載します。
CLASS_SCORES = {
"Harry Potter" => {
"Alchemy" => nil,
"Arithmancy" => nil,
"Astronomy" => 6,
"Care of Magical Creatures" => 8,
"Charms" => 5,
"Defence Against the Dark Arts" => 10,
"Divination" => 4,
"Herbology" => 7,
"Muggle Studies" => nil,
"Potions" => 2,
"Study of Ancient Runes" => nil,
"Transfiguration" => 7,
},
"Hermione Granger" => {
"Alchemy" => 9,
"Arithmancy" => 10,
"Astronomy" => 9,
"Care of Magical Creatures" => 9,
"Charms" => 10,
"Defence Against the Dark Arts" => 9,
"Divination" => 1,
"Herbology" => 10,
"Muggle Studies" => 10,
"Potions" => 3,
"Study of Ancient Runes" => 9,
"Transfiguration" => 10,
}, …
アルゴリズムではCLASS_SCORESというRubyのハッシュを使いますが、データをテーブル形式で表現したもので考えると便利です。
| Harry Potter |
Hermione Granger |
Ron Weasley |
Neville Longbottom |
Draco Malfoy |
Vincent Crabbe |
Greggory Goyle |
Ginny Weasley |
Cho Chang |
Cedric Diggory |
|
|---|---|---|---|---|---|---|---|---|---|---|
| 錬金術 （Alchemy） |
- | 9 | - | 4 | - | 1 | 2 | 8 | - | 6 |
| 数占い学 （Arithmancy） |
- | 10 | - | - | 7 | 2 | 2 | - | 8 | - |
| 天文学 （Astronomy） |
6 | 9 | 6 | - | - | - | - | - | 9 | 8 |
| 魔法生物飼育学 （Magical Creatures ） |
8 | 9 | 7 | 5 | 4 | 2 | 3 | 8 | - | 8 |
| 呪文学 （Charms） |
5 | 10 | 7 | 4 | 7 | - | - | 9 | 7 | 7 |
| 対闇魔術防衛 （Dark Arts） |
10 | 9 | 8 | 4 | 3 | 1 | 2 | 9 | 7 | 6 |
| 占い学 （Divination） |
4 | 1 | 7 | 5 | - | - | - | - | - | - |
| 薬草学 （Herbology） |
7 | 10 | 8 | 10 | 8 | 3 | 2 | 9 | 8 | 6 |
| マグル学 （Muggle Studies） |
- | 10 | - | - | - | - | - | 9 | - | - |
| 魔法薬学 （Potions） |
2 | 3 | 3 | 1 | 10 | 9 | 8 | 3 | 6 | 3 |
| 古代ルーン文字学 （Ancient Runes） |
- | 9 | - | - | 7 | 3 | - | - | 9 | - |
| 変身術 （Transfiguration） |
7 | 10 | 7 | 6 | 7 | 2 | 3 | 8 | 9 | 3 |
各列はユーザー（学生）の成績を表し、各行は特定の授業の成績を表す。
この形式では、各列がユーザー（学生）の成績を表し、各行が特定の授業の成績を表します。すなわち、1人の学生の成績は1個のベクトル（配列）で表現可能と考えてよいことになります（例: Ginny Weasleyの成績は[8, nil, nil, 8, 9, 9, nil, 9, 9, 3, nil, 8]というベクトルで表現できる）。
ここで言及しておきたい点が2つあります。
- ベクトル内の順序は明らかに重要です。
Ginnyの配列の3は、魔法薬学の授業に関連しているので、添字9の位置に置かれています。すなわち、値の添字には意味があるのです。
2人の学生のベクトルが同じ添字を使っている限り、両者は直接比較できます。 -
学生が受講していない授業については、ベクトル内に
nilが存在します。
さて、Ginnyは魔法薬学の成績が3であることをとても気に病んでいて、もっとよい成績を取れそうな科目に乗り換えることを検討しているとします。現時点でGinnyが受講していない科目は「数占い学」「天文学」「占い学」「古代ルーン文字学」の4つです。どの科目に変更するのがベストかをアドバイスできるでしょうか？
🔗 似たような学生を見つける
Ginnyが最初に試しそうな方法は、自分と関心の対象が似ている他の学生を見つけて、別の授業を自分にすすめてくるかどうかを尋ねてみることでしょう。前回の記事で解説した距離測定を活用すれば、Ginnyのベクトルと他の学生たちの個別のベクトルを比較し、Ginnyに「最も近い」学生を特定して、その学生からおすすめの授業を聞き出せます。
このプロセスを実行するために、Recommenderクラスを導入します。このクラスでパラメータ化されるclass_scoresデータ構造やdistance_measureを計算で利用します。
require_relative './metrics'
class Recommender
attr_reader :class_scores, :distance_measure
def initialize(class_scores = {}, distance_measure = Metrics.method(:euclidean_distance))
@class_scores = class_scores
@distance_measure = distance_measure
end
class_scores属性は、前のセクションで導入した成績のHashに過ぎません。distance_measureは、（呼び出し可能な）メソッドであり、長さが同じ2つのベクトルを受け取って、両者の距離を返します。
前回の記事で取り上げた実装の多くが再利用可能ですが、現在のクラスでは、他の測定アルゴリズムが指定されていない場合はデフォルトでeuclidean_distanceを使うようになっています。
以下では便宜上euclidean_distanceの実装を再録します。
def self.euclidean_distance(a,b)
return unless a.any? && (a.size == b.size) # この距離を算出するには長さが同じ2つのベクトルが必要
diff_squared = (0..a.size-1).reduce(0) do |sum, i|
sum + (a[i] - b[i])**2
end
Math.sqrt(diff_squared)
end
Recommenderクラスがこのような形で設定されたので、Ginnyに「最も似ている」他の学生を見つける方法を検討できる状態になりました。
Recommenderクラスから抜粋した以下のコードスニペットは、top_k_matchesの実装方法を示しています。このメソッドは、「1人の学生名（対象）」と「数値k（取り出したいマッチ）」を受け取り、考慮されている距離測定に沿って、対象の学生に最も近いと判断される他の学生数k人を返します。
実装は以下のとおりです。
…
def top_k_matches(person, k = class_scores.size)
class_scores.keys.inject({}) do |scores, other_person|
next scores if other_person == person
scores[other_person] = similarity(person, other_person)
scores
end.compact.sort_by do |_key, value|
-1*value
end[0..k-1].to_h
end
private
# 類似度スコアは閉区間[0, 1]になる
# スコア1は項目が同一であることを示す
# スコア0は距離が無限であることを表す
def similarity(person, other_person)
1.0/(1.0 + distance(person, other_person))
end
def distance(person, other)
# 両方の学生に成績が存在する授業の次元を渡さなければならない
person_vec, other_vec = class_scores[person].values.each_with_index.map do |score, i|
next unless score && class_scores[other].values[i]
[score, class_scores[other].values[i]]
end.compact.transpose
# 重複する成績がない場合は任意の大きな値を返す
# これにより無限の距離を効果的に模倣する
return 10_000 if [person_vec, other_vec].any?(&:empty?)
distance_measure.call(person_vec, other_vec)
end
end
このtop_k_matchesメソッドそのものはかなり素直です。class_scoresに含まれる学生ごとにループを回して、その学生と対象の学生との間の類似度を算出します（このとき対象の学生を対象の学生自身と比較しないよう注意します）。得られた類似度は順序付けされ、最も類似度の高いkを返します。
def top_k_matches(person, k = class_scores.size)
class_scores.keys.inject({}) do |scores, other_person|
next scores if other_person == person # 自分自身と比較しないようにする
scores[other_person] = similarity(person, other_person)
scores
end.compact.sort_by do |_key, value|
-1*value # 成績の類似度の降順で並べ替える
end[0..k-1].to_h # 最大のkを抽出してハッシュとして出力
end
おそらくもっと興味深い点は、2人の学生のベクトルを取得した後、成績の類似度を決定するためにどんな操作を実行する必要があるかでしょう。前回の記事で導入した距離測定では、一般的に長さの同じ数値配列が2つ必要でしたが、その観点では、配列にnil値が存在すると距離を算出できなくなってしまうことになります。
このnil値は何を表しているのでしょうか？
学生が受講していない授業があると、学生のベクトルの特定の添字がnil値になります。つまり、学生の一方が特定の科目で成績を持ち、他方の学生がその科目を受講していない（つまりnilになる）場合、その科目では学生同士の類似度や距離についてほとんど何もわかりません。
そういうわけで、ベクトルの一方もしくは両方にnil値が含まれる場合は、その要素の処理を省略することにしましょう。これが、以下のdistanceメソッドの冒頭部分で行われている処理です。
def distance(person, other)
# 両方の学生に成績が存在する授業の次元を渡さなければならない
person_vec, other_vec = class_scores[person].values.each_with_index.map do |score, i|
next unless score && class_scores[other].values[i]
[score, class_scores[other].values[i]]
end.compact.transpose
# 重複する成績がない場合は任意の大きな値を返す
# これにより無限の距離を効果的に模倣する
return 10_000 if [person_vec, other_vec].any?(&:empty?)
distance_measure.call(person_vec, other_vec)
end
入力ベクトルpersonとotherは、さらに短いベクトルperson_vecとother_vecに変換されます。後者では、いずれかにnilエントリが含まれている場合の添字を捨てています。次に、既に確立済みの距離関数にこの短い2つの配列を渡せば、この新しい相互サブスペース内での2人の学生の距離を決定できます。
考慮しておくべきもうひとつの複雑な点は、2人の学生が共通して受講している授業が存在しない場合です。この場合、person_vecとother_vecは空配列になるので、両者の距離を決定しようがありません。そこで、共通する授業がない場合は、学生同士が大きくかけ離れているとみなせるので、任意の大きな距離（無限大の距離の近似）を返します。
ここまでは2人の学生の距離を決定してきましたが、実際に欲しいのは成績の類似度です。以下のメソッドを利用することで、distanceを類似度に変換できます。
def similarity(person, other_person)
1.0/(1.0 + distance(person, other_person))
end
- 2人の学生が同一の場合は
distanceがゼロになるので、similarityは1になります。 - 逆に、
distanceの値が非常に大きい場合は、similarityはゼロに近づく傾向があります。
つまり、類似度は0〜1の範囲になります。
既に説明したコードを援用することで、Ginnyと最も似ている上位3名の学生を算出できるようになります。
require_relative './hogwarts_class_scores'
require_relative './recommender'
recommender = Recommender.new(CLASS_SCORES)
puts recommender.top_k_matches("Ginny Weasley", 3)
# {"Ron Weasley"=>0.2612038749637414, "Hermione Granger"=>0.25, "Cho Chang"=>0.18660549686337075}
なるほど！どうやらGinnyの兄であるRonに尋ねるのが最適のようですね。GinnyがRonにアドバイスを求めれば、RonはGinnyに占い学をすすめることになるでしょう。しかしあなたならRonのアドバイスを信用しますか？
🔗 授業を推薦する
前セクションの方法は、Ginnyがどの授業に乗り換えるかを決めることについては、かなり有効かもしれません。しかしGinnyが尋ねる学生が1人しかいないので、Ginnyが選んだ学生（この場合はRon）の好みが非常に偏っていたとしたら、Ronによる推薦はあまり適していない可能性もあります。
しかも、Ron自身は数占い学も古代ルーン文字学も履修していないので、Ronが経験していないことについては十分な情報に基づいた推奨は行えないことになります。
こうした欠点を克服するには新しい手法が必要です。
1人の学生に授業を推薦してもらうのではなく、ある科目を履修した多くの学生（もしくは学生全員）からの推薦を受けて、その科目の平均スコアを算出する方法が使えるでしょう。
ただしそのときに、学生がGinnyに似ていれば似ているほど、その分その学生からの推薦の重み付けを大きくすることも筋が通っているでしょう。そこで、各学生の貢献度をGinnyへの類似度に応じて重み付けすることにします。
この計算をRubyで実装したものを以下に示します。
def get_recommendations(person)
class_scores[person].inject({}) do |memo, (class_name, score)|
next memo if score # 成績が登録されていない授業だけを推奨したい
total_similarity = 0
memo[class_name] = class_scores.keys.inject(0) do |avg, other_person|
next avg unless class_scores[other_person][class_name] # ここで関心があるのは、この授業を履修して成績が出ている学生のみ
similarity = similarity(person, other_person) # 学生同士の類似度が重み付けの係数となる
total_similarity += similarity # 最後に割るときのために類似度の合計を保持する
avg += class_scores[other_person][class_name] * similarity # 重み付きの貢献度を集計する
end
memo[class_name] = memo[class_name] / total_similarity # 重みの合計で割る
memo
end
end
ここでは対象の学生について授業の成績をループで回していますが、対象となるのは学生の成績が存在しない授業だけです。それらの授業ごとに、その授業で成績が登録された他のすべての学生をループし、その授業の成績の加重平均を算出します（この加重係数は、対象の学生との類似度です）。以上でおしまいです。
それでは、この加重平均を利用して、Ginnyにどんな推奨が生成されるかを見てみましょう。
require_relative './hogwarts_class_scores'
require_relative './recommender'
require_relative './metrics'
recommender = Recommender.new(CLASS_SCORES, Metrics.method(:euclidean_distance))
puts recommender.get_recommendations(student)
# {"Arithmancy"=>7.492996951956632, "Astronomy"=>7.566161526023427, "Divination"=>4.168756010451042, "Study of Ancient Runes"=>8.094049420209119}
このモデルに基づくと、Ginnyは「古代ルーン文字学」で8.09という成績を達成すると見積もられるので、この科目に乗り換えることが推奨されます。
おそらくユークリッド距離は、この高次元空間では距離測定として最適とまではいかないでしょう（以下の記事を参照）。
参考: Why Should Euclidean Distance Not Be the Default Distance Measure? | by Harjot Kaur | Towards AI
しかし心配は無用です。このアルゴリズムは、他の距離測定法でも同様にうまくいくはずです。たとえばmanhattan_distanceで同じ計算を行った場合を考えてみましょう。
require_relative './hogwarts_class_scores'
require_relative './recommender'
require_relative './metrics'
recommender = Recommender.new(CLASS_SCORES, Metrics.method(:euclidean_distance))
puts recommender.get_recommendations(student)
# {"Arithmancy"=>7.492996951956632, "Astronomy"=>7.566161526023427, "Divination"=>4.168756010451042, "Study of Ancient Runes"=>8.094049420209119}
そういうわけで、成績の予測値はわずかに違いはあるものの、結論は変わらないことがわかります。つまり、Ginnyがよい成績を得るベストの選択肢は、古代ルーン文字学に切り替えることです。
🔗 まとめ
以上が、Rubyで実装したシンプルな推奨システムです。
これらのアルゴリズムは、任意のユーザーや項目のデータセットから推奨を生成するのに利用できます。この場合の推奨システムは「類似」ユーザーというアイデアに基づいており、この手法は「ユーザーベースフィルタリング（user-based filtering）」と呼ばれています。
このデータセットを反転すれば、項目（この場合は授業名）から個別の学生の成績をベクトルで表現できることは容易に想像がつくことでしょう。つまり、学生の類似度の代わりに授業の類似度を探索すれば、授業の類似度から推奨を生成できるわけです。このような手法は「項目ベースフィルタリング（item-based filtering）」と呼ばれており、場合によってはこちらが適していることもあります。
私たちが提示したモデルには、まだ多くの欠点があります。中でも重要なのは、データベース上にある対象ユーザーとその他の全ユーザーとの間の距離を算出する必要があることです。ユーザー数が増加すると、この計算量が非現実的になる可能性があります。また、成績がまったく（またはほとんど）出ていない新しいユーザーが存在していると、意味のある推奨を行えなくなってしまいます。
最後に、ここで用いたデータセットは比較的密です（どの学生も、自分が受講可能な授業の大半を受講します）。こういう密なデータセットなら、意味のあるユーザー距離を算出可能です。
しかし、たとえば「映画のおすすめ」のように、各ユーザーが巨大なデータセットのごく一部の項目だけを評価する場合を考えてみましょう。このようなまばらなデータセットでは、ユーザーベクトル間の距離という考え方が少々怪しくなってきます。
こうしたさまざまな問題に対処する推奨モデルは他にも多数ありますが、そうしたアルゴリズムの深掘りは今後の記事に譲ります。
皆さんが本記事を楽しんで役立てていただければ幸いです。最新の記事をすぐお読みになりたい方は、フォームにて購読をお申し付けください。
🔗 参考文献
- 『Collective Intelligence』（Toby Sagaran）Amazonで購入可
- 前回記事Ruby: 機械学習などで使われる距離測定アルゴリズムをRubyで実装する（翻訳）
- GitHubリポジトリ: 本記事で扱ったアルゴリズムの実装を参照できます
- ブログ記事: ranking Hogwarts classes
- ブログ記事: Why Should Euclidean Distance Not Be the Default Distance Measure?
概要
元サイトの許諾を得て翻訳・公開いたします。
日本語タイトルは内容に即したものにしました。
参考: 最近傍法 - Wikipedia