Amazon の Item-to-Item CF の論文を読んだメモ

今となってはかなり古い部類に入る論文ですが、レコメンデーションの基礎を改めて勉強し直すために読んだので、そのメモを残しておきます。¹

Amazon.com Recommendations: Item-to-Item Collaborative Filtering

この論文が議論の対象としているのは、（Amazon.com のような）数千万ユーザ・数百万点の商品（アイテム）という大規模なデータセットに対し、リアルタイム（遅くとも 500ms 以下）、オンライン ² で、かつ高品質な推薦を行うという問題です。Amazon はこの問題をアイテムベースの協調フィルタリングで解決しています。

ユーザベースの協調フィルタリング

協調フィルタリングの詳細については こちらの資料 に譲るとして、端的にいうと「協調フィルタリング」というのは、アクティブユーザ（推薦対象のユーザ）に類似する他のユーザを、商品購入履歴や評点情報の近さから探し出し、そのユーザが購入している商品をアクティブユーザに推薦する、というものです。

古典的な GroupLens のユーザベース協調フィルタリングでは、時間計算量の制約から、オンラインでの推薦を提供できるのは中規模（数十万ユーザ、数万点の商品程度？）のデータセットまでとなっているようです。このユーザベースの協調フィルタリングの時間計算量は、ユーザ数を m、商品数を n とすると、最悪のケースで O(mn) となります。ただし、実際のデータセットにおいては、ユーザと商品の関係が疎であることが多いので、その場合には O(m + n) の時間計算量に近くなるそうです。どちらにせよ、Amazon ほどの大規模なデータセットにおいては、O(m + n) の時間計算量でさえもオンライン・リアルタイムでの推薦を難しくする要因となり得ます。

このユーザベースの協調フィルタリングを大規模データセットに適用する場合は、時間計算量を小さくする工夫が必要になります。この論文では以下のように、データの規模を減らすことで時間計算量を小さくする手法が挙げられています。

• ユーザをランダムサンプリングして、全体のユーザ数を減らす
• 購入量の少ないユーザを省く（類似度計算結果の精度が低く、推薦にあまり役立たないため）
• とてもよく購入されている/ほとんど購入されていないアイテムを省く

ほかにも、商品の集合をそのカテゴリごとに分類し、その分類された商品の集合内で推薦処理を行う方法も挙げられています。しかしながら、いずれの手法を採用するにしても、推薦の品質・精度が低下してしまう問題がつきまとってしまいます。

クラスタモデルの手法

ユーザベースの協調フィルタリングでは、リクエストの都度、ユーザ間の類似度を計算して、アクティブユーザに類似するユーザを探していました。一方でクラスタモデルでは、ユーザ集合を類似するユーザ同士であらかじめクラスタリングしておきます。このクラスタリング処理は、推薦処理とは切り離してオフラインで計算することができます。推薦処理では、このユーザのクラスタを利用し、アクティブユーザがどのクラスタに属するかを判定したのちに、そのクラスタに属する他のユーザの情報を利用して推薦が行われます。

このクラスタモデル、計算時間の観点では優れた手法ではありますが、推薦品質については決して高くはないようです。推薦品質を向上させるためにはクラスタの数を増やす必要があり、クラスタ数を増やしてしまうと、オンラインでの計算量が増えてしまう、という問題を抱えています。

Amazon.com のアイテムベース (Item-to-Item) の協調フィルタリング ³

以上のように、大規模なデータセットに対して高品質・高精度で、かつパフォーマンスのよい推薦を実現するのは難しい問題と言えます。Amazon はこの問題に対し、アイテムベースの協調フィルタリングを利用することで解決を図っています。

Amazon のアイテムベース協調フィルタリングの一番の特徴は「アイテム間の類似度行列をオフラインで計算して、推薦に備えておく」ことです。アイテム間の類似度行列の計算は、最悪のケースで O(n^2 * m)、疎なデータセットでも O(nm) の時間計算量となりますが、オフラインで計算するのであればこの計算量は許容できる範囲になるのではないでしょうか。また、よく購入されている商品を購入したユーザをサンプリングしてアイテム間の類似度行列を計算することで、品質・精度の低下を小さくしつつ、時間計算量を削減できるようです。

推薦処理では、このアイテム間の類似度行列を利用します。その推薦処理の時間計算量は、ユーザ数や商品総数に依存せず、アクティブユーザの購入商品数、評点情報数にのみ依存します。そのため、大規模データセットであっても、オンラインでの推薦処理で充分な性能が出せるようになる、とのことです。

また、このアイテムベースの協調フィルタリングは、アクティブユーザの購入済みの商品が 2,3 個程度と僅かな状況であっても、質の良い推薦が実現できます（ユーザーベースの協調フィルタリングでは、類似するユーザーを探すためにそれなりの数の購入商品数を必要とするので、2,3 個程度の商品数では十分な推薦が実現できません）。

まとめ

大規模データセットに対して推薦をする場合、高いパフォーマンスと推薦品質・精度の両立は簡単ではありません。Amazon.com は、アイテムベースの協調フィルタリングを採用することで推薦品質・精度の問題を解決し、またその協調フィルタリングで利用するアイテム間類似度行列をオフライン計算することでパフォーマンスの問題を解決しています。

感想など

普段扱っているデータの規模が大きくても数十万ユーザ、数万アイテム数だというのに、この程度でヒイヒイ言っている自分が情けなくなりますね… 規模の大きいデータにもっと慣れねば！

---

1：個人的な解釈が多分に含まれているので、この記事を参考にすることがもしあれば、一度原文と照らし合わせてみることをお勧めします。

2：推薦すべき商品を事前に計算して準備しておくのではなく、リクエストが来たところで初めて推薦する商品を算出する方式。論文の記述から察するに、ショッピングカート内の商品から推薦する場合などにも利用されているらしい。

3：アクティブユーザに類似するユーザを探すのではなく、あるアイテムに類似する別のアイテムを探すタイプの協調フィルタリングを、ここでは「アイテムベースの協調フィルタリング」と呼んでいます。