協調フィルタリング型レコメンドエンジン開発のため仕様について考える

協調フィルタリング型レコメンドしたいけど、オープンソースでいいライブラリないし、ASPサービスは基本5万円/月以上。もう自分で作るしか無い

協調フィルタリング型レコメンドとは

一番有名な実装例はAmazonの『この商品を買った人はこんな商品も買っています』機能だと思います。以前簡易版の実装を紹介しました。簡易版記事の続きが本記事となります。

wikipediaの協調フィルタリングから引用

協調フィルタリング（きょうちょうフィルタリング、Collaborative Filtering、CF）は、多くのユーザの嗜好情報を蓄積し、あるユーザと嗜好の類似した他のユーザの情報を用いて自動的に推論を行う方法論である。趣味の似た人からの意見を参考にするという口コミの原理に例えられることが多い。

火花と同時受賞した筋トレ作家羽田先生のスクラップアンド・ビルドが1番目にレコメンドされるあたり、流石Amazon様です..直木賞を受賞した流も良い小説ですね。

協調フィルタリングは枯れた技術

Webを漁ると2005年の段階で日本語の記事が存在しています。またレコメンドサービスを提供する会社は乱立しており検索すると何社も見つかるので（どこも高いけど）、作れる理論は出回っているのでしょう。

協調フィルタリングはJaccard係数で相関をとって実現することが一般的みたいです。商品Xと商品AのJaccard係数の計算式は次の通りです。

では100万個の商品が存在するとなると、商品Xからレコメンドされる商品を計算するには100万回Jaccard係数の計算を行う必要があります。計算量爆発してますね。この計算方法は現実的ではありません。

協調フィルタリングは枯れた技術です。上記課題にぶちあたった先人はいくつかの解決方法を提示しています。Amazonは2003年に逆引き索引を作成することで解決する論文を発表しています。

逆引き索引の検証コード

Jaccard係数の計算サンプルはWeb上に散見されますが、逆引き索引を作って解決するサンプルが見当たりません。発見した中では唯一具体的に書いてあったレコメンドにおける類似度計算その傾向と対策 #DSIRNLP 第4回 2013.9.1の資料を参考にして逆引き索引を作ってみましょう。

# -*- coding: utf-8 -*-
from __future__ import absolute_import, unicode_literals

# 商品ID:10の購入者
from collections import defaultdict

ITEM_10_BUY_USERS = ['A', 'C', 'E', 'G']

# 購入者の商品購入履歴(逆引き索引)
INDEX_BASE = 'INDEX_BUY_HISTORY_USER_{}'
INDEX = {
    'INDEX_BUY_HISTORY_USER_A': [10, 20, 50, 60, 90],
    'INDEX_BUY_HISTORY_USER_B': [20, 20, 50, 60, 70],
    'INDEX_BUY_HISTORY_USER_C': [10, 30, 50, 60, 90],
    'INDEX_BUY_HISTORY_USER_D': [30, 40, 50, 60],
    'INDEX_BUY_HISTORY_USER_E': [10],
    'INDEX_BUY_HISTORY_USER_F': [70, 80, 90],
    'INDEX_BUY_HISTORY_USER_G': [10, 70, 90],
}

# 逆引き索引を使って類似度を計算
result = defaultdict(int)
for user_id in ITEM_10_BUY_USERS:
    # INDEXからユーザ毎の購買履歴を取得
    buy_history = INDEX.get(INDEX_BASE.format(user_id))
    # 購買したアイテム数を集計する
    for item_id in buy_history:
        result[item_id] += 1

l = []
for key in result:
    l.append((key, result[key]))

# 結果の類似度を表示
l.sort(key=lambda x: x[1], reverse=True)
print l

>>> [(10, 4), (90, 3), (50, 2), (60, 2), (70, 1), (20, 1), (30, 1)]

商品10と類似度が高い商品は、商品90, 商品50, 商品:60の順で相関が高いことが判りました。こちらの方法ですと全商品との類似度を計算するJaccard係数より計算量が少ないですし、参照するユーザ数の量を制御することで計算量を制御することも可能になりそうです。

レコメンドエンジンの肝は更新速度

たとえば100万件の商品と利用ユーザ100万人の販売サイトを運営しています。2015/3/11に発売した『火花』が発売日から大ヒットして1日で5万部売れました。商品数が多いと週1でプチ祭りが発生するので、いかに早く100万件の商品のレコメンドを更新するかが売上げに直結しそうです。

しかし計算量は膨大です。いかに早く更新できるかが勝負の世界。レコメンドエンジンに求められる機能として並列計算可能な仕組みであることが求められるのではないでしょうか。プロデューサに更新間隔を1/4に出来ないのと言われたとき、いま4台で更新してるので4倍の16台で計算すれば1/4になります。1台月5万円なので月額5 x 12 = 60万円のコスト増です。と返答できればステキですね。（プロデューサは去っていきエンジニアは定時で帰れるはずです。）

バックエンドはRedisが良いと思う

レコメンドエンジンのバックエンドはRedisが良いのではないでしょうか。枯れていて、それなりにread早くて、AWSで提供されてて、シングルスレッドで動作するから適切に使えばデータがAtomicであることが保証され、RDSよりI/Oが早いです。またRuby、PHP、Node.js、Perlからもライブラリが存在するため利用が容易です。Atomicであることが保証されるということはスレッドセーフであるということ。つまり並列計算のバックエンドとして利用できる条件を満たしていると考えられます。
※理想の実装はdata_handlerでバックエンドが選択可能な方式だと思う。

仕様

1. pip install可能であること
2. タグ機能を有し、タグ毎にレコメンド可能であること
3. レコメンドする商品の更新が並列で実行可能であること
4. Ruby、PHPから利用可能であること
5. 商品を削除可能であること
6. ユーザの購入履歴を編集可能であること
7. ユーザを削除可能であること

性能目標

100万個の商品、100万人のユーザ、ユーザ毎に平均50個購入している状態で
1. 全レコメンド更新がMacBookPro1台で4時間以内に完了すること
2. レコメンドする商品の更新が1商品あたりMacBookPro1台で10秒以内に完了すること

こんな感じで呼び出せたらいいなー

[sample]新システムに導入時

# 全商品を登録
for goods in goods.get_all():
  Recomender.register(goods.id, tag=goods.tag)

# 全購入履歴を登録
for user in user.get_all():
  Recomender.like(user.id, user.history.goods_ids)

# sample1. 全商品のレコメンド更新(シングルスレッド)
Recomender.update_all()

# sample2. 全商品のレコメンド更新(マルチスレッドスレッド)
Recomender.update_all(proc=4)

# sample3. 全商品のレコメンド更新(並列クラスタ4台x4並列)
# 並列クラスタ.1 全商品のうち前半1/4を計算
Recomender.update_all(proc=4, scope=[1, 4])

# 並列クラスタ.2 全商品のうち中前半1/4を計算
Recomender.update_all(proc=4, scope=[2, 4])

# 並列クラスタ.3 全商品のうち中後半1/4を計算
Recomender.update_all(proc=4, scope=[3, 4])

# 並列クラスタ.4 全商品のうち後半1/4を計算
Recomender.update_all(proc=4, scope=[4, 4])

sample_code

# 商品新規追加
new_goods_id = 2100
tag = "book"
Recomender.register(new_goods_id, tag=tag)

# この商品を買った人はこんな商品も買っています。5件取得
goods_id = 102
print Recomender.get(goods_id, count=5)
>>> [802, 13, 45, 505, 376]

# 特定商品のレコメンド更新
Recomender.update(goods_id)

# 全商品のレコメンド更新
Recomender.update_all()

# Aさんがgoods_idsを購入
user_id = "dd841cad-b7cf-473b-9006-77823ad5e006"
goods_ids = [102, 102, 103, 104]
Recomender.like(user_id, goods_ids)

recommendation_data_update

# 商品のタグを変更
new_tag = "computer"
Recomender.change_tag(goods_id, new_tag)

# 商品の削除
Recomender.remove(goods_id)

# ユーザの削除
Recomender.remove_user(user_id)

あとは作るだけ...つくる...だ....け....つ.........け.....

参考

1. 協調フィルタリング 増井俊之
2. レコメンドにおける類似度計算その傾向と対策 #DSIRNLP 第4回 2013.9.1
3. Amazon.com Recommendations Item-to-Item Collaborative Filtering

完成しました

協調フィルタリング型RealTimeレコメンドエンジンを公開
よろしくお願い致します。