Scalable Collaborative Filtering Using Cluster-based Smoothing

Presentation on theme: "Scalable Collaborative Filtering Using Cluster-based Smoothing"— Presentation transcript:

1 Scalable Collaborative Filtering Using Cluster-based Smoothing
集団に基づくスムージングを使った拡張性のある協調フィルタリング まとめ？編

2 2.背景(予備知識) 協調フィルタリング ・メモリーベース メモリーベースのアプローチは最もポピュラーな予測技術の1つ。 基本的な考え あるアイテムについてのアクティブユーザーの予測される評価を 他の類似したユーザーの多数決、 またはK近傍法(KNN)による評価の加重平均として計算すること。 一般に、メモリーベースでは ピアソン相関係数アルゴリズム(PCC)[16] ベクトル空間類似度アルゴリズム(VSS)[4] を利用する。

3 2.背景(予備知識) 協調フィルタリング ・モデルベース モデルベースの人気のあるアルゴリズム ・協調フィルタリングのためのクラスタリング[13][21] ・アスペクトモデル[12] クラスタリング技術は類似した好みを持つと思われる ユーザー達のグループを特定することによって機能する。 一度クラスタが作成されると、 個人に対する予測はそのクラスタ内の他のユーザー達の 評価の平均をとることによってもたらされる。 いくつかのクラスタリング技術は、 いくつかのクラスタへの部分的な関係で各々のユーザーを表現する。 予測はそれから、そのクラスタらに対する平均である。 そして関係の程度によって重み付けがされる。 アスペクトモデルは確率的潜在空間モデルである。 そしてそれは個々の選択を選択要因の凸結合と考える。 潜在的なクラス変数は、ユーザーとアイテムの各々の情報のペアと関係付けられる。 アスペクトモデルは潜在的クラス変数が与えられると、 ユーザーとアイテムが互いに独立であると仮定する。

4 2.背景(予備知識) 協調フィルタリング ・ハイブリッドモデル Pennockたち[15]はメモリーベースとモデルベースの複合型のアプローチを提案した。 いくつかのアイテムに対するユーザーの好みが与えられれば これらは全ての取り得る評価全体を一様分布として未評価を割り当てることによって 同じ「個性診断」に属するユーザーである確率を計算する。 以前の実験による研究はその手法がPCC手法、VSS手法とベイジアンネットワークアプローチを含む、協調フィルタリングのための他のいくつかのアプローチより 性能が優れていることを示した。 しかし、未評価のアイテムを評価するとき、トレーニングデータベースの情報の集合全体も、ユーザー間の多様性も考慮しない。 ・他の関連研究 ・次元削減手法 ・コンテントブースとCFアプローチ ・Sarwarらのアイテムベースのアプローチ

5 3クラスタベース協調フィルタリングフレームワーク
・表記法の定義 アイテムの集合T={t1,t2,...,tm} データベース内のユーザーの集合U={u1,u2,...,un} アクティブユーザーua トレーニングデータベース内でみつかる全ての評価{(u(1),i(1),r(1)),...,(u(k),i(k),r(k))} ((u(i),t(i),r(i)))はアイテムt(i)がユーザーu(i)によってr(i)と評価されることを意味する。 ユーザーuごとに、Ru(t)はユーザーuによるアイテムtの評価 Ruはユーザーuの平均評価を意味している。 評価の度合いは1からrmaxに及ぶ。

6 ・クラスタリングベースのスムージングアルゴリズム
アルゴリズム：クラスタ-スムーズCF ・前処理：ユーザークラスタCを作成(K-meansアルゴリズムを使用する。) ・アクティブユーザーuaと評価されたアイテムi、アイテムt、最も近い近傍の数である整数Kが与えられたら 1.uaに最も類似したグループらからs人のユーザーを選びグループGに入れる。 2.uの評価がRu(t)とRcu(t)の組み合わせであるGでuごとに類似度sim(ua,u)を計算する。 3.最も近い近傍としてtopK人の最も類似したユーザーを選ぶ。 4.K人の近傍のふるまいによってuaのための特定のアイテムtの評価を予測する。

7 3.1クラスタリングアルゴリズム ・K-meansアルゴリズムを用いる 数字kはクラスタの数を指定する入力。 最初のステップで最初のk人のユーザーをk個のユニークなクラスタの重心として利用する。 残りの各々のユーザーたちは、それから最も近い重心と比較される。 次のステップでクラスタの重心は前のステップで作られたクラスタの重心に基づいて再計算される、そしてクラスタの帰属関係は再評価される。 ユーザーたちがN個のグループにクラスタわけされると仮定すると、ユーザーたちUのクラスタリング結果は、{Cu1,Cu2,...,Cuk}と表現される。

8 われわれはピアソン相関係数関数を類似度計算関数として利用する。
ユーザーuとユーザーu'との類似度は次のように定義される。 この式は共分散をそれぞれの標準偏差で割ったものに等しい。

9

10 3.2データスムージング データの疎は協調フィルタリングのための基本的な問題である。 データセット内の未評価を埋めるために、スムージング手法としてクラスタの明示的な利用を行う。 クラスタリングの結果に基づいて、スムージング計画(方法)を未知の評価データに適用する。 まず、特別な評価値を次のように定義する。 ここでRu(t)^はあるアイテムtに対するユーザーuの評価のためにスムージングされた値を意味する。 ユーザーuが与えられたら、Cu∈{Cu1,Cu2,...Cuk}はユーザーが属するクラスタに属しているとする。

11 個人の多様性を考慮することによってRu(t)^を計算するために以下の式を使用することを提案する。
ここでΔRCu(t)はアイテムtに対するクラスタCu内の全てのユーザーに対する平均偏差である。 そして以下で定義される： ここでCu(t)∈CuはクラスタCu内でアイテムtを評価したユーザーのユーザーセットである。 |Cu(t)|はくラスタCuないでアイテムtを評価したユーザーの人数である。

12 3.3近傍事前選択 協調フィルタリングの重要なステップはアクティブユーザーの近傍を検索することだ。 従来の方法はデータベース全体を検索するので、 新しいユーザーやアイテムがデータベースに追加されるとき、 この方法は明らかにスケーラビリティの低下に苦しむ。 クラスタの概念を用いることによって、よりよく実行できる。 あるクラスタ内のユーザーのグループの特徴はそのクラスタの重心によって表現される。 この重心はそのクラスタ内の全てのユーザーに対する平均評価として表現される。 クラスタ内のユーザーの類似した集合を計算するためにユーザーらのグループCとアクティブユーザー間の類似度は以下の関数に基づいて計算される： 各々のグループとアクティブユーザー間の類似度を計算した後、 最も類似したグループら内のユーザーたちを候補者として利用する。 その過程から、 いくらかの無関係の情報を削除するのと同様に、類似度計算のスピードアップの手助けになる。

13 3.4近傍選択 事前選択の後、スムージングされた評価に関して、 候補者集合のユーザーとアクティブユーザー間の類似度を再計算する必要がある。 クラスタ情報によるスムージングの後、ユーザーの評価値は、 2つの部分(元の評価とグループ評価)からなる。 本論文では、候補者集合内のユーザーとアクティブユーザー間の類似度を計算するとき、 異なる重みはユーザーの元の評価とグループ評価の間で考慮される。 すなわち、Wutをアイテムtにユーザーuのための信頼重みとしてセットする。 ここでλは元の評価とグループ評価間の重さを調整するためのパラメーターである。 λの値は0から1まで変化する。

14 それからわれわれは、下記の類似度関数に基づいてtopK人の最も類似したユーザーたちを選ぶ。
λに異なった値を割り当てることによって、 総合的な類似度の異なる評価値の重みを調整することができる λ=0のときPCCアルゴリズム(類似度計算と予測のために評価された情報を使うだけの) λ=1のときクラスタベースの協調フィルタリングアルゴリズム (類似度計算と予測のためにクラスタリングの平均評価を使う）

15 3.5予測 予測する際、K人の最も類似したユーザーたちの部分集合は、 アクティブユーザーに対する彼らの類似度に基づいて選ばれる、 そして彼らの評価の重み付けされた集合は下記のように アクティブユーザーのための予測を生成するのに用いられる。 予測は、近傍の平均値からの偏差の重み付け平均として計算される。 ここでsimua,uはアクティブユーザーuaとトレーニングユーザーu間の類似度、 そしてKは近傍内のユーザーの数である。

16 表で示すように、われわれのフレームワークは近傍事前選択とスムージングの組み合わせにより、非常に柔軟性が高い。
PCC・・・ピアソン相関係数アルゴリズム CBCF・・・クラスタベースの協調フィルタリング CBPCC・・・スムージングのためにクラスタを使用するような クラスタベースのピアソン相関係数アルゴリズム SPCC・・・スケーラブルなピアソン相関係数アルゴリズム 近傍事前選択のためにクラスタを用いる SCBPCC・・・近傍事前選択とスムージングのためにクラスタを用いるような アルゴリズム

17 4実験 スケーラビリティと推薦の質に関して協調フィルタリングのための新しいスキームの 有効性を調査するために実験を行った 結果 提案したフレームワークはスケーラビリティ問題を解決することと同様に 予測の精度を改善することができました、と。