協調フィルタリングについてまとめてみた。
A Survey of Collaborative Filtering Techniques(Xiaoyuan Su and Taghi M. Khoshgoftaar, 2009,Advances in Artificial Intelligence)
仕事で協調フィルタリングについて調べる必要が出てきたのだが、あまりよい日本語の文献を見つけられなかったため（後にしましま先生の文献を見つけた）やむなく英語の論文を検索したところ、
上記のよいサーベイ論文を見つけた。というわけでこのサーベイ論文に書かれていることに自分なりに調べたことを加えて、自分用にまとめておく。
また、一部の人達の間ではとても有名なしましま先生の論文（ドラフト版）があるので、英語が苦手な人はそちらをご覧になるとよいと思われる。
協調フィルタリングは、一言で言えばユーザとアイテムのマトリックスを用いた顧客への商品のレコメンデーションです。このマトリックスより、ユーザの相関を分析し、類似したユーザはお互いが購入している商品買うという仮定に基づきレコメンデーションする仕組みといえます。Wikipediaの英語版にはこの直感的な雰囲気を説明した以下の図があります。
Wikipedia（http://en.wikipedia.org/wiki/Collaborative_filtering）より
１．ユーザとアイテム（商品）の関係がネットワークで表現されています。
２．先ほどの関係が行列で表現されています。
３．一番下のユーザ（アクティブユーザ）のパソコンに対する評価を知りたいとします。
４．アクティブユーザと類似するユーザ（緑のユーザ）を選び出します。
５．類似するユーザの評価よりアクティブユーザはパソコンを評価しないと予測します。
１．協調フィルタリングの歴史
この箇所は論文にはそれほど記述がありませんが、自分なりに調べたものです。私が学生だった頃はNetFlixのコンテストが行われ、日本でも必要のない多くのサイトで協調フィルタリングが導入されていたような記憶があります。当時は「Web2.0」とか「ロングテール」なんて今ではめっきり聞かない単語が流行ったり、「集合知プログラミング」が出版されて周りの学生の間でも簡単に実装可能なWebビジネスのアルゴリズムにほくほくしていました。
1992年：Tapestryというコメンデーションシステムの論文において協調フィルタリングという言葉が初めて登場
1994年：GroupLens、ネットニュースのレコメンデーションシステムの論文が出版
1997年：Amazonが協調フィルタリングを導入
2007年：NetFlixPrize、優勝賞金$1,000,000のオープンレコメンデーションコンペの開催
２.協調フィルタリングの特性とその抱える問題
協調フィルタリングはその実ビジネスとの関連性の強さと特徴的なデータ構造より、以下のようなこの分野に特徴的な問題点を持っています。
２．１．データのスパース性
２．２．スケーラビリティ
２．３．類似性
２．４．灰色の羊
２．５．シリングアタック
２．１．データのスパース性・・・通常のビジネスで用いる協調フィルタリングでは巨大なアイテムセットを用いるためユーザ・アイテム行列は極端に疎であり、精度の面で問題になります。データがスパースであるために以下のような問題が引き起こされます。このスパース性について実感するにはAmazonの人気商品ランキングを見て、自分が買ったことのある商品を数えてみるとよいでしょう。殆どの人は大半の商品を買ったこと無いはずです。
１．コールドスタート問題・・・新しいアイテムやユーザが追加された時に類似のアイテムを見つけるのが難しい問題。
２．少カバー率問題・・・ユーザの評価が少ないアイテムは類似するアイテム等のレコメンデーションの提示が不可能になること。
３．同類推移問題・・・スパースなデータベースの場合、類似のユーザであっても、全く同じアイテムを共に評価しないと類似であると判別されない問題。
これらの問題に対処するために以下のような方法が用いられます。
２．２．スケーラビリティ・・・多くの場合、アイテム数やユーザ数は驚異的なスピードで増大するために、古典的な協調フィルタリングアルゴリズムを使用するのには問題があります。O(n)のアルゴリズムであっても、計算量が大きすぎます（えっ）。いくつかの解決法が存在しますが、レコメンデーションの精度と計算量は常にトレードオフの関係にあります。
２．３．シノニム性・・・シノニム性は同じあるいはとても似ているアイテムが異なるアイテムとなっている傾向のことを指します。シノニムの存在はレコメンデーションの性能を下げます。LSIなどを用いてシノニムを発見することができますが、適合率においては高い性能を示すものの、再現率は低いようです。
２．４．灰色の羊・・・複数の人々と一致するするような曖昧なユーザで、協調フィルタリングの恩恵にあずかれない人を指します。Claypoolはコンテンツベースフィルタリングと協調フィルタリングのハイブリッドアプローチでこの問題を解決する方法を提案しました。
２．５．シリングアタック・・・自己への利益誘導目的の不正なアイテムに対する評価を指します。要はステマです。アイテムベースの協調フィルタリングはユーザベースの協調フィルタリングよりシリングアタックの影響を受けにくいそうです。
協調フィルタリングの分類
協調フィルタリングは大きく、以下の３つの分類に分けることができます。
３．メモリベースの協調フィルタリング・・・ユーザとアイテムの相関関係より、類似したユーザ同士の評価を基にレコメンデーションのルールを作成します。
４．モデルベースの協調フィルタリング・・・統計的なアルゴリズムを用いてユーザの購買行動をモデル化し、モデルに基づいてレコメンデーションのルールを作成します。
５．ハイブリッド協調フィルタリング・・・コンテンツベースのフィルタリングと協調フィルタリングを混合させてレコメンデーションのルールを作成します。
下の表は論文より、上記の協調フィルタリング技術をまとめた表を翻訳したものです(Su&Khoshgoftaar, 2009)。
３．メモリベースの協調フィルタリング
メモリベースの協調フィルタリングはユーザとアイテムのデータベースを用いて、これを行列として表現しユーザ（アイテム）の類似性により、レコメンドする商品をピックアップする方法です。
以下の２つはさらに詳細な分類です。
ユーザベースの協調フィルタリング・・・「同じ商品を買っている類似ユーザ同士の評価は似ている」と仮定してユーザの類似性にもとづき推薦する商品を決定します。
アイテムベースの協調フィルタリング・・・アイテムの類似性を中心に計算する手法。Amazonで用いられている手法もこれであり（Wikipediaより）、スケーラビリティの問題に対処するために開発された。
おそらく協調フィルタリングといえば、一般にはモデルベースではなく、こちらを指すことが多いように思われます。
３．１．類似性の計算
３．２．予測とレコメンデーションの計算
３．２．１．重み付き予測による評価予測
３．３．２．Top-Nレコメンデーション
アノテーションについて
先ほどのWikipediaの図で表示されていたように、協調フィルタリングではユーザアイテム間の行列を用います。以下のようにユーザがアイテムに対して５段階評価をしている行列を例に考えます。
この時、全ユーザの集合をU、その要素をu,vとします。
全アイテムの集合をI、その要素をi,jとします。
この時、あるユーザuのアイテムiに対する評価を
ユーザuの評価の平均を
とします。
３．１．類似性の計算
先ほどのWikipediaの図で言うところの３の作業に値します。ユーザ（アイテム）の距離、類似度を定義する計算を各アイテム別（ユーザ）別に行う処理を指します。協調フィルタリングにおいては致命的な計算になります。
（他の論文読んでいるとどうも、距離の指標はアイテム−ユーザ行列のスパース性や、評価がユーザによる5段階評価か商品の購買やWebページの閲覧と言ったバイナリの値をとるかといったことに依存するみたいです。）
類似性には下のようないくつかの指標が用いられます。
１．ピアソン相関係数・・・二つの変数の互いに（線形の）関係性の強さを表す度合い（最も代表的な類似性）
２．強制ピアソン相関係数・・・ピアソン相関係数の計算において平均ではなく中央値を用いる指標
３．スピアマン順位相関係数・・・ピアソン相関係数の順位版
４．ケンドールのτ相関係数・・・スピアマンの順位相関係数を相対的な順位に直したもの
５．コサイン類似性・・・ベクトルの内積（ドキュメントの単語頻度による距離に用いられる）
６．調整済みコサイン類似性・・・ユーザーにより、異なる評価スケールを行っていることより、コサイン類似性において平均を引いて標準化したもの、実はピアソン相関係数と同じ。
これらの指標を用いて、アイテム間もしくはユーザ間の類似性を定義します。
ピアソン相関係数の場合は、ユーザuとvの類似性は以下のようになります。
この類似性を用いて、以下のステップでレコメンデーションを作成します。
３．２．１．予測（レコメンデーション）計算
ユーザにレコメンドするアイテムを得るために、類似性に基づいてアクティブユーザのアイテムに対する評価を集計し、予測します。以下のような２つの指標がが存在します。
１．類似ユーザ評価の重み付き和・・・ユーザベースの協調フィルタリングでは、特定のユーザの予測を行う際に、同じ嗜好を持っているユーザはより大きな重みを付けてこの評価を行います。
２．重み付き和・・・アイテムベースの協調フィルタリングで用いられます。
アクティブユーザaに対する、類似ユーザ評価の重み付き和としてのアイテムiの評価の予測式は以下のようになります。
これでアクティブユーザに対する商品への評価の予測ができます。
３．２．２．Top-Nレコメンデーション・・・上記の予測だけでもレコメンデーションはできますが、代表的なレコメンデーションの手法であるTop-Nレコメンデーションは類似しているユーザやアイテムを絞って、そこからN個の商品を実際にユーザに推薦する方法の１つです。
３．１．ユーザベースのTopNレコメンデーション・・・商品ベクトル空間上でのユーザの類似性を測定します。あるユーザiさんに商品をレコメンドする際は、そのうち上位のk人を抽出して、その中でユーザiさんがまだ買っていない商品のうち最も購入頻度の高い上位N件をレコメンドします。この手法は計算量的に限界があります。
３．２．アイテムベースのTop-Nレコメンデーション・・・アイテムベースのTop-Nレコメンデーションはアイテムベースのレコメンデーションは計算のスケーラビリティ、早さにおいてユーザベースのものよりメリットがあります。このアルゴリズムでは事前にアイテムの類似性に基づいて全てのアイテムに対して、レコメンデーションの候補となる上位k個の類似アイテムを計算しておきます。そこからユーザuがすでに購入している商品を取り除き、その集合の中のアイテムをiとすると、uの購入しているアイテムjに対する評価とiとjの類似性で重み付けをした重み付き和を計算して、uへのjの評価を予測します。
４．モデルベースの協調フィルタリング
モデルベースの協調フィルタリングについては理解があやふやなので、羅列するだけにとどめておきます。
４．１：ベイズネット協調フィルタリング・・・ベイジアンネットワークを用いた協調フィルタリング
４．１．１：単純ベイズ協調フィルタリング・・・ナイーブベイズを用いた協調フィルタリング
４．１．２：NB-ELRとTAN-ELR・・・単純ベイズより、欠損の多いデータに強いアルゴリズムのようであるが、詳細は不明。性能は、ナイーブベイズやピアソン相関によるメモリベースのモデルよりも強力である。
４．２：クラスタリング協調フィルタリング・・・クラスター分析を協調フィルタリングに用いる手法。多くの場合、クラスタリングはさらなる協調フィルタリングのプロセスの中間ステップとして実行される。例えば、クラスタ間でのメモリベースの協調フィルタリングを行う等。多く場合、クラスタリングは計算量でメリットがあるが精度は低い。
４．３：回帰による協調フィルタリング・・・回帰モデルを構築を行い、特定ユーザの特定のアイテムへの評価を予測する方法。
４．４：MDP（マルコフ決定プロセル）モデルによる協調フィルタリング・・・シミュレーションのような手法・・・らしい。
４．５：潜在意味協調フィルタリング・・・潜在意味解析を用いた手法・・・らしい。
５．ハイブリッド協調フィルタリング
ハイブリッド協調フィルタリングとは、異なる２つの協調フィルタリングの仕組みを混ぜることです。
典型的には、コンテンツベースのレコメンデーションとメモリベースの協調フィルタリングを混合します。
コンテンツベースのレコメンデーションとは、テキストによる文脈情報やユーザの設定やプロフィール等の情報を用いてそこから見つけた規則性によるレコメンデーションの仕組みのことです、
例えば、コンテンツブーステッド協調フィルタリングはナイーブベイズ手法を用いて、ユーザの属性情報（年齢、性別等）とメモリベースで用いてきたユーザアイテムマトリックスを用いて欠損値を補い、擬似評価マトリックスを作成します。
その後にピアソン相関係数に基づき協調フィルタリングを行い欠損値の予測を上書きして、元々存在していた評価は上書きせずに予測を行います。この手法はコールドスタート問題を回避するのにも有効なようです。
他にも、その他利用可能なすべてのレコメンデーション手法を重み付きで混合する手法や、メモリベースの協調フィルタリングとモデルベースの協調フィルタリングを混合する手法等が存在します。
これらの方法の混合により、高い精度を維持しながら、先の２で記載した協調フィルタリング特有の問題に対処するようです。
６．協調フィルタリングの評価
協調フィルタリングの評価には一般的な機会学習の予測評価と同じ指標が用いられます。平均誤差や、再生と再認率、k交差法によるROC曲線、これについては省略します。
最後に
Tescoなんかは結構前からレコメンデーションのDMとかをやっているみたいなので、チラシやDMが大好きな日本の小売でもレコメンデーションを使ったDMが流行る日も近いと思われる。
TokyoR#30ではこれらの解説に加えてRで協調フィルタリングを実行するrecomenderlabの実行例を加えてもう少し具体的な計算手法に突っ込んで解説を行う予定です。
詳細な計算についてはまたBlogに残しておきたい。
