算数とJavaScriptでレコメンド

今年の遠足は、おやつはダメだけど果物はたくさん持って来てもいいよ、と先生が言いました。変な学校だね。遠足の日、さとしくんはリンゴとミカンを、りかちゃんはリンゴとイチゴとドラゴンフルーツを持ってきました。

(1) 果物は全部で何種類ありますか。

=> リンゴ、ミカン、イチゴ、ドラゴンフルーツだから 4 種類

(2) 二人とも持って来た果物は何種類ありますか。

=> リンゴだけだから 1 種類

(3) (2)の答えを(1)の答えで割ってください。

=> 0.25

これをJaccard係数といいます。類似度の計算で使うので、大人になるまで忘れないでください。

目標

邦画の予告をひたすら観られる、というどこに需要があるのかわからないWebサイトがありまして、そこにおすすめの映画を表示するのが目標です。統計やレコメンドの知識はまったくなかったので、色々と調べながらやりました。

レコメンドの実現方法を考える

レコメンドについては、神嶌敏弘さんの資料を参考にさせてもらいました。すごくわかりやすかったので、PDFとまったく同じ内容で書籍化されていても喜んで買うと思います。

推薦システムのアルゴリズム

利用するデータの種類

明示的フィードバック

アイテムに対する評価などの、ユーザーの明示的な行動から得られるデータ。
1〜5の評価をつけたり、👍や👎を押したり尺度はさまざま。

We have several billion item ratings from members. And we receive millions of new ratings a day.

Netflix Recommendations: Beyond the 5 stars

かなり古い記事だけどNetflixの強さに震える。

データがそんなにたくさんあったら文句がないのだけど、評価したりレビューを書いたりしてくれるのは、有名なサービスの一部のユーザーだけだと思うので、零細サイトでは厳しそう。

暗黙的フィードバック

ページの閲覧やアイテムの購入などの、明示的ではない行動データ。
DVDを購入したら好きに違いないとか、曲を50回リピートしているからハマっているとか、スキップした広告は嫌いだろうとかそういうの。

ユーザーの行動に潜む心理（好き/嫌いなど）を推測して分析に利用する。Webの場合はページの表示回数や滞在時間なども対象になりそう。明示的なものに比べると確度は落ちるが、データは大量に取得できる。使うとしたらこっちかな。

レコメンドの手法

多種多様な推薦システムのためのアルゴリズムが存在するが，一体，どのアルゴリズムを使えばよいのであろうか？ 機械学習の基本的な定理であるノーフリーランチ定理によれば万能アルゴリズムは存在しない．よって，アルゴリズムは，推薦システムを利用する目的や，推薦を実行する環境の制約に応じて選択する必要がある．

推薦システムのアルゴリズム

スタッフのおすすめ

いきなりレコメンドから離れますが、よく見かけるのでとりあえず。家具や雑貨のセレクトショップみたいな、スタッフのセンスが信頼されているショップの場合、下手なパーソナライズよりもスタッフのおすすめの方が売れそう。根拠はないけど。

本屋とかレンタルビデオ店におすすめのコーナーがあると、思わず立ち止まってしまうし、手作りのポップとかを見ると優しい気持ちになれる。品数が少なかったら、もうこれだけでいいんじゃなかろうか。

協調フィルタリング

Collaborative Filtering

レコメンドといえばコレ、というぐらいメジャーなものらしい。
行動履歴が似ている人達を探して、あなたもきっとコレ好きだよ、というのをレコメンドする方法。

	たまこまーけっと	響け!ユーフォニアム	リズと青い鳥
Aさん	◯	◯	×
Bさん	×	×	×
Cさん	◯	◯	◯

例えば、ユーザーが視聴済のアニメを記録できるサービスで、表のようなデータがあったとします。AさんとCさんは趣味が似ているので、Aさんには未視聴のリズと青い鳥をレコメンドすれば、なんだかいけそうな気がしますね。

リズと青い鳥は、ただいま公開中なのでぜひ映画館で。どこまでも尊い映画です。響け!ユーフォニアムのスピンオフなので、先にアニメを観ていた方がわかりやすいですが、たぶん初見でもいけます。

例ではアニメを薦めているだけですが、各アイテムに対する評価のデータがある場合は、きっとあなたはこのアニメを観たら3.6ぐらいの評価をするんじゃない？知らんけど。みたいな使い方もできるらしい。

アイテムに対して制作会社などの情報がなくても、ユーザーの行動データだけで的確なレコメンドを行えるかもしれないところがすごい。アイテムの内容に依存しないので、スニーカーでも熱帯魚でも、ユーザーの行動や評価がとれるものであれば適用できそうです。

一見して万能に見える協調フィルタリングではありますが、データのない新規ユーザーへは適用できません。レコメンドするアイテムについても、新発売のアイテムには対応できないので、そこのところは他の方法で補う必要があります。これをコールドスタート問題というらしいです。どうでもいいけど、パワプロのスロースターターを思い出した。

ユーザーのデータが大量にある場合は、とりあえず協調フィルタリングにしておけばそれっぽい結果になりそう。

内容ベースフィルタリング

Content-Based Filtering

アイテムの情報から、特徴が似ているものをレコメンドする方法。映画の場合なら、題名/監督/俳優/ジャンルなどだろうか。具体的には、アウトレイジを観た人には、同じ監督のソナチネを薦めておけばいっか、みたいな感じで。

協調フィルタリングとは違い、ユーザーの行動データが少ないアイテムもレコメンドの対象にできるけれど、アイテムの特徴を与えてあげる必要があるので、対象の知識が必要になります。

結局、どうやってレコメンドするか？

on average, a member is most likely to watch what most others are watching. However, popularity is the opposite of personalization: it will produce the same ordering of items for every member.

Netflix Recommendations: Beyond the 5 stars

人気とパーソナライゼーションは対極にあるという。難しい。

レコメンド結果を表示したいサイトは、知る人ぞ知る、というより誰も知らないに等しいぐらいのユーザー数なので、協調フィルタリングはあまり機能しそうにありません。

内容ベースフィルタリングで行くとしても、監督や俳優が同じ作品を出すだけでは味気ないので、監督や俳優は違うけど実は雰囲気が近いみたいな映画もレコメンドできるのが理想です。

たまたま、それぞれの映画に対して「サスペンス」や「恋愛」などの大まかなタグ以外にも、「裏社会」「暴力」「バカヤロー」のような細かいタグ付けも行っているので、その傾向が似ているものをレコメンドできたら、雰囲気が近いものが揃うかもしれません。

類似度の計算

データがどれぐらい似ているかを、類似度というらしいのですが、その計算方法が色々あってベクトルの話がたくさん出てきたので少し身構えました。けれど冷静に考えたら、共通のタグがどれぐらいあるかをわかればいいだけなので、もっとシンプルにできそう。調べていたらJaccard係数という、まさにコレなものが見つかりました。

Jaccard係数

ふたつの集合(A, B)において、少なくともどちらかにあるものの個数(和集合)を、両方にあるものの個数(積集合)で割ったもの。

jaccard(A, B) = \frac{|A \bigcap B|}{ |A\bigcup B|}

// 計算のイメージ

A = ['木村', 'カエラ', 'りえ']
B = ['木村', '文乃']

A ∩ B => ['木村'] // 1個
A ∪ B => ['木村', 'カエラ', 'りえ', '文乃'] // 4個

jaccard = 1/4 = 0.25

集合や係数などというと大袈裟な印象を受けますが、割り算ができて算数セットが手元にあれば説明できそうな内容なので、小学校の算数で足ります。

Pythonで実装

def jaccard(a, b):
    return len(a & b) / len(a | b)

a = set(['木村', 'カエラ', 'りえ'])
b = set(['木村', '文乃'])

print(jaccard(a, b)) # 0.25
print(jaccard(a, a)) # 1.0
print(jaccard(b, b)) # 1.0

はじめてのPythonだったので、とりあえずAnacondaの環境を整えて、チュートリアルをやりました。Python歴2時間なので、正しいコードなのかはわかりませんが、期待通りに動いたのでよしとします。

JavaScriptとPHPぐらいしか使ったことがなかったので、集合型というものがあることに感動。しかし気がついた。これだけであれば、AnacondaどころかPythonすらも不要ではないか。

もしPythonを使わないのであれば、WebサイトのバックエンドにNode.jsを使っていたので、レコメンドもNode.jsでやりたい。

Node.jsで実装

const _ = require('lodash')

const jaccard = (a, b) => _.intersection(a, b).length / _.union(a, b).length

const a = ['木村', 'カエラ', 'りえ']
const b = ['木村', '文乃']

console.log(jaccard(a, b)) // 0.5
console.log(jaccard(a, a)) // 1
console.log(jaccard(b, b)) // 1

lodashに感謝。
複雑な計算を高速にやりたいわけではないので、今回はNode.jsでやることにします。

レコメンドの実装

すべての映画でJaccard係数を算出

前置きがかなり長くなりましたが実装していきます。それぞれの映画のタグをもとにJaccard係数を算出し、値が大きいもの上位数件をおすすめとしてデータベースに保存します。すべてのコードを貼ると長くなるので色々と省略していますが、実際はタグのデータ以外にも監督と主演俳優も考慮してJaccard係数を算出しています。

実行時間を計測したところ、300アイテムで1秒程度でした。

const _ = require('lodash')

const jaccard = (a, b) => _.intersection(a, b).length / _.union(a, b).length

// データベースから取得する代わり
const all = () => [
  { id: 1, tag: ['サスペンス', 'ダーク', '中学校'] },
  { id: 2, tag: ['サスペンス', 'コミカル'] }
]

const updateRecommendMovies = () => {
  const movies = all() // データベースからすべての映画を取得
  const total = movies.length
  let records = []

  for (let i = 0; i < total; i++) {
    let similarities = []

    for (let j = 0; j < total; j++) {
      if (i !== j) {
        similarities.push({
          movie_id: movies[i].id,
          recommend_movie_id: movies[j].id,
          similarity: jaccard(movies[i].tag, movies[j].tag)
        })
      }
    }

    // Jaccard係数で降順にソートして上位10件を抽出
    const similarMovies = _(similarities)
      .orderBy(['similarity'], ['desc'])
      .slice(0, 10)
      .value()

    records.push(...similarMovies)
  }

  // 実際はもっとデータがありますが、こんな感じになります
  //
  // [
  //   { movie_id: 1, recommend_movie_id: 2, similarity: 0.25 },
  //   { movie_id: 2, recommend_movie_id: 1, similarity: 0.25 }
  // ]
  console.log(records)

  // recordsをDBへ保存
}

参考までに「ちはやふる 結び」に関連する映画はこんな感じになりました。シリーズが最上位に来て、高校が舞台のものや部活ものが並んでいます。登録している映画がまだ少ないので、もっと増やしたい。

類似度	タイトル
1	ちはやふる 上の句
1	ちはやふる 下の句
0.25	ガチ☆ボーイ
0.23	トリガール
0.18	サイモン＆タダタカシ
0.17	大人ドロップ
0.17	くちびるに歌を
0.17	坂道のアポロン
0.15	君の膵臓をたべたい
0.15	君の名は

おすすめの映画を取得するAPIを追加

先ほどデータベースに保存した各映画に対するおすすめを、映画のIDを指定して取得できるエンドポイントを追加します。実際はもっと長いので、コードは雰囲気です。

// Express
router.get('/api/movie/:id/related', (req, res) => {
  const movies = selectRecommendMoviesById(req.params.id)

  res.json(movies);
});

Webサイトへ表示する

ここが最も適当なところですが、ユーザーが最近見た映画のページのIDをローカルストレージに保存しておいて、再訪してくれた際に、トップページに関連する映画を表示します。実際のサイトではReactを使っているので、コードは雰囲気です。

localStorage | MDN

import axios from 'axios'

const save = id => {
  localStorage.setItem('movie_id', id)
}

const recommend = async () => {
  const movieId = localStorage.getItem('movie_id')

  // キーがなかったらnullが返るので
  if (movieId === null) {
    return
  }

  // 指定したIDに関連する映画を取得
  const { data } = await axios.get(`/api/movie/${movieId}/related`)

  // React/Vue/jQueryなどでレンダリングする
  render(data)
}

できあがり

邦画の予告を、朝まで

改善が必要なところ

簡素な実装なので改善点だらけですが、ぱっと思いつくところだけ。

最近見たページだけを対象にしていいのか

本来であれば、ユーザーが過去に閲覧した各ページ、もしくはその組み合わせを考慮しておすすめの映画を選ぶべきです。本来であれば。

タグ付けのさじ加減

類似度を算出するためにもっとも重要な映画のタグ付けをひとりで行っているため、全力で主観に依存しています。この問題を軽減するには、ユーザーにタグ付けをしてもらってそれを精査する仕組みを作ったり、運営スタッフにレビューを行ってもらったりする必要があります。大変だ。

各タグの重み

現状の類似度の計算だと、各タグの重みが考慮されていません。なので、本格的なサスペンスだけどホラー要素がある映画と、がっつりホラーだけどサスペンスの要素がある映画が完全に一致してしまいます。これを避けるためには、各タグに重みをつけて計算してあげる必要がありますが、全部のタグに人力で重みを付け直すと考えたら気が遠くなったので、実装していません。

計算量

全アイテム×全アイテムで類似度を計算しているので、計算量が膨大です。アイテム数が10倍になると時間が100倍になってしまうと考えると恐ろしいですが、幸か不幸かアイテムは手動で登録しているため、一気に増えることはないのでしばらくは大丈夫です。これを解消するには、より効率的に類似度を計算できるアルゴリズムを適用していく必要があります。

レコメンドの打率について

レコメンドの精度は高いに越したことはないけれど、1割ぐらい打てて、たまにホームランが飛び出せばかなり優秀なんじゃないかと思うのですが、一般的なレコメンドシステムはどのくらいの結果が出ているのだろうか。おすすめのエリアにコンバージョンを設定して計測すれば打率は出せそうな気がしますが、気力が残っていなかったのでそこまでは実装していません。

Amazonのレコメンドは的確すぎて財布が追いつかないので、もう少し打率を下げて欲しい。

より精度の高いレコメンドを目指して

Everything is a Recommendation

Netflix Recommendations: Beyond the 5 stars

今回は自分の頭と相談して、簡単な算数のみで実装しましたが、より多くの人に響くレコメンドを実装するには、ベクトルや機械学習と正面から向き合い、色々な手法を組み合わせていく必要があります。レコメンドを商売にしている会社もあるぐらいなので道は険しいですが・・・

今はとりあえず映画を観よう。