Mahout in Action Chapter 4 についてのメモ。
4.2 ユーザベースの推薦の詳細
4.2.1 アルゴリズム
- ユーザにアイテムを推薦する処理は下記のとおり。ユーザは u で表されている
1 for every item i that u has no preferencefor yet 2 for every other user v that has a preference for i 3 compute a similarity s between u and v 4 incorporat e preference of v for i, weighted by s, into a running average 5 return the top items, ranked by weighted average
外側のループはユーザがまだ嗜好度を持っていない、推薦対象になりうるアイテムすべてに対するもの
内側のループはこの推薦対象になりうるアイテムについて嗜好度を持っているユーザに対するもので、その嗜好度を参照している
最後にそれらの値の平均値を計算し、重み平均とする
それぞれの嗜好値はそのユーザがターゲットのユーザとどれぐらい類似しているかの平均値から重み付けされる
ユーザが類似しているほど、重みが嗜好度に加えられる
すべてのアイテムについて検証するのはひどく遅い。
実際は最も類似しているユーザを計算した後、そのユーザに知られているアイテムのみについて検討される
1 for every other user w 2 compute a similaritys between u and w 3 retain the top users, ranked by similarity , as a neighborho od n 4 for every item i that some user in n has ap preference for, but that u has no preference for yet 5 for every other user v in n that has a preference for i 6 compute a similarity s between u and v 7 incorporat e preference of v for i, weighted by s, into a running averate
一番の違いは最も類似しているユーザが何に興味を持っているかを探す前に、類似しているユーザを探している点
これは基本的なユーザベースの推薦アルゴリズムで、Mahoutにも実装されている
4.2.2 GenericUse rBasedReco mmenderによるアルゴリズムの実装
- Mahoutは推薦エンジンを構築するためのコンポーネントの集合で、以下のようなコンポーネントから構成されている
1 データモデル, DataModelによって実装される 2 ユーザ同士の類似度, UserSimilarityによって実装される 3 近隣者の定義, UserNeighb orhoodによって実装される 4 推薦エンジン, Recommende rによって実装される(ここではGenericUse rBasedReco mmender)
4.2.3 GroupLensによる探索
- GroupLensのデータを処理するためにはGroupLensD
ataModelを使えばよい
1 DataModel model = 2 new GroupLensDataModel(new File("ratings.da t")); 3 UserSimila rity similarity = 4 new PearsonCor relationSi milarity(model); 5 UserNeighb orhood neighborho od = 6 new NearestNUs erNeighbor hood(100, similarity , model); 7 Recommende r recommende r = 8 new GenericUse rBasedReco mmender(model, neighborho od, similarity ); 9 LoadEvalua tor.runLoad(recommende r);
- このコードを動かすと、OutOfMemor
yErrorが発生するので、メモリを増やす必要がある
4.2.5 サイズ固定のneighborho od
- 類似度が高い順にN個のデータが使われる
4.2.6 閾値ベースのneighborho od
- 類似度の閾値を決めてそれ以上の類似度を持つユーザを取り出すことが可能
4.3 類似度の測定方法の詳細
- ユーザベースの推薦で他に重要なのはUserSimila
rity実装。ユーザベースの推薦の大部分はこのコンポーネントに依存している
4.3.1 ピアソン相関ベースの類似度
ピアソン相関は -1 から 1 までの数値で、2組の配列の傾向を測定するもので、線形の関係になる
この傾向が高い場合は相関係数は1に近づく
すべての値において関連が小さい場合は、相関係数は0に近づく
関連がまったく逆の場合、一方の組の値が高くなるときに他方の値が小さくなるようなケースでは、相関係数は-1に近づく
類似度の計算は双方のユーザがそのアイテムに対して嗜好度を持っている場合のみ可能
4.3.2 ピアソン相関の問題点
ユーザ間で一致するアイテムの数を評価に加えないことが、推薦エンジンとしては欠点
ユーザ間で一致するアイテムがひとつしかない場合、相関は計算されない
全ての嗜好度が同一のユーザについては相関が計算されない
4.3.3 重み付けを使う
PearsonCor
relationSi milarityは重みを追加して、ピアソン相関の問題点を軽減する PearsonCor
relationSi milarityのコンストラクタの第二引数にWeighting. WEIGHTEDを渡すことができ、これによってデータ数が多い場合には1.0方向へ、少ない場合には-1.0方向へ補正される
ユークリッド距離による類似度の定義
- 前述のサンプルコードのUserSimila
rity実装部分を変更してEuclideanD istanceSim ilarityを使用する
1 new EuclideanDistanceSim ilarity(model)
この実装はユーザ間の距離を基にしている
ユーザがより類似している場合にこの値は小さくなる
この実装が実際に戻す値は 1 / (1 + distance)
コサイン測定による類似性の適用
空間にポイントされ可視化された嗜好度データによる類似度計測方法
ユーザ間の類似度が低い場合、それぞれの嗜好度を表す線の距離は広がり、角度も大きくなる
この角度のコサインが類似度を導く
コサイン値は常に -1 から 1 の間で、小さい角度の場合は 1 に近づき、180度近い大きい角度の場合は -1 に近づく
これは良いことで、小さい角度の場合は類似度が高いということで 1 に近く、大きい角度の場合は -1 に近づくということだからである
コサイン測定による類似度の測定はよく強調フィルタリングによる調査と関連付けられる
この類似度測定法を使用するにはPearsonCor
relationSi milarityを使うだけでよい
スピアマン相関での相対的階級による類似度定義
スピアマン相関はわれわれの目的にとってはピアソン相関の興味深い変種
オリジナルの相関嗜好度データの相関ではなく、嗜好度データの相対ランクに基づいて相関を計算する
このプロセスはいくつかの情報を失うが、嗜好度データの本質である順位付けは維持され、正確な嗜好度合いについての情報は失われる
SpearmanCo
rrelationS imilarityはこの考えを実装する 前出のサンプルコードのUserSimila
rityの実装でSpearmanCo rrelationa lSimilarit yを使うことで試すことができる この実装は計算のために簡単ではない処理を行いランクを保存しなければならないため、かなり遅い
しかしながら小さいデータセットに対しては向いているかもしれない
CachingUse
rSimilarit yは他のUserSimira lity実装をラップするUserSimila rity実装で、その実行結果をキャッシュする 計算処理はラップしているUserSimila
rity実装に委譲し、その結果を内部的に保持しておく
1 UserSimilarity similarity = new CashingUse rSimilarit y( 2 new SpearmanCo rrelationS imilarity(model), model)
evaluate()のtrainingPe
rcentage引数を0.95から0.99に増やすことで、テストデータの量を5%から1%に減らすことで計算量を減らすことができる これによって計算にかかる時間を数十分にすることができる
谷本係数により類似度の中の嗜好度データを無視する
おもしろいことに、嗜好度をすべて無視するUserSimila
rity実装がある TanimotoCo
efficientS imilarityはその実装のひとつで、谷本係数を基にしている。この値はジャカール係数としても知られている この値は嗜好性のあるアイテムの集合のうち、共通する部分の比率になる
二人のユーザのアイテムが完全に一致するとき、結果は1.0になり、共通部分がないとき、0.0になる。結果がマイナスになることはないが問題ない
結果を次の簡単な計算によって -1 から 1 の範囲に拡張することが出来る
similarity= 2・similarity - 1 この計測方法は両方のユーザが嗜好度を持っているアイテムだけでなく、一方が嗜好度をもっているアイテムにも依存することに注意
この類似度計測方法を使う場合は、基になるデータにはブール値(Boolean)の嗜好度データのみを含める
対数尤度によるよりスマートな類似度の計算
対数尤度による類似度は、谷本係数のように二人のユーザに共通するアイテムの数を基にしているが、その他に多くの重複がある可能性がどれくら低いか、アイテムの総数、それぞれのユーザが嗜好性を持っているアイテムの数も含んでいる
二人のユーザ間での偶然による重複がどれくらい起こり得ないかを評価しようとするもの。すなわち、類似しないユーザ間で同じ映画に対する評価をもつことはあるが、類似しているユーザが全くありそうもない共通点を見せることがあるということ。
いくつかの統計的検定で、この類似度計測手法は二人のユーザ間でどれぐらい強く類似することがありそうもないかを断定しようと試みる。
結果の類似度の値は二人のユーザ間で偶然ではない重複がおこるとみなされる値
汎用化は難しいが、対数尤度による類似度は谷本係数による類似度より性能が優れている
嗜好度の推測
ときどき少なすぎるデータが問題になることがある。いくつかのケースにおいて、例えば、ピアソン相関はユーザ間で重複しているアイテムが一つの場合には類似度を計算することができない
データが欠損している部分にデフォルト値が挿入されるとどうか。この戦略はPreference
Inferrerインタフェースにより可能になっており、現在はAveragingP referenceI nferrerという実装がある この実装はそれぞれのユーザの平均嗜好度を計算し、この平均値をまだユーザと関連のないアイテムの嗜好度として挿入する
UserSimila
rityのsetPrefere nceInferre r()メソッドを呼ぶことで使用可能 原則として実際のデータを元に純粋に情報を作るには何も加えないが、これは計算を急激に遅くする
Mahoutはアイテム間の類似度という概念も提供する。ユーザ間だけでなくアイテム間の類似度についても同様の計算が適用される
アイテムベースの推薦
- アイテムベースの推薦は、ユーザとユーザの代わりに、アイテムとアイテムがどれだけ類似しているかによって行われる。Mahoutでは、UserSimila
rityの代わりにItemSimila rityを基にすることを意味する
アルゴリズム
1 for every item i that u has no preferencefor yet 2 for every item j that u has a preference for 3 compute a similarity s between i and j 4 add preference of u for j, weighted by s, to a running average 5 return the top items, ranked by weighted average
アイテムベースの推薦を選択した方がよい理由の一つとしては、アイテムの数がユーザの数と比べて少ないとき、パフォーマンスの優位性はかなり大きくなるということ
また、一般的にアイテムはユーザよりも変更される点が少ない
事前に類似度を計算しておくことは、実行時の推薦スピードを速くする
Mahoutでは、GenericIte
mSimilarit yクラスが事前の計算とItemSimila rityクラスからの結果を格納するのに使われる。これは今までに出てきたいずれの実装にも適用することが可能
アイテムベースの推薦の詳細
- GenericUse
rBasedReco mmenderではなくGenericIte mBasedReco mmenderを使うコードは下記のとおり
1 public Recommender buildRecom mender(DataModel model) 2 throws TasteExcep tion { 3 ItemSimila rity similarity = new PearsonCor relationSi milarity(model); 4 return new GenericIte mBasedReco mmender(model, similarity ); 5 }
PearsonCor
relationSi milarityはItemSimila rityインタフェースを実装しているのでここでも使用しており、これはUserSimila rityインタフェースについても同様 GenericIte
mBasedReco mmenderはシンプルで、DataModelとItemSimila rityのみ必要。ItemNeighb orhoodは不要。 すべてのUserSimila
rityがItemSimila rityも実装しているわけではない アイテムベースの推薦は一般的にアイテム数がユーザ数より少ないときはユーザベースの推薦より速い
スロープワンアルゴリズムによる推薦
- 新しいアイテムとその他のユーザの嗜好性のあるアイテムの嗜好度の差の平均を基に嗜好度を評価する
アルゴリズム
スロープワンという名前は推薦アルゴリズムが一つのアイテムとその他のアイテムの嗜好度の間にいくつかの直線関係があるという仮説から来ており、Yというアイテムの嗜好度を、Y=mx+bという式で表されるXの嗜好度を基にするのは妥当である
ここでスロープワンによる推薦は単純化するためのm=1:という仮説を追加する。この場合、b=y-xのみ残り、これはすべてのアイテムのペアの間での嗜好度の差
これはアルゴリズムは下記の様に、すべてのアイテム間の嗜好度の差を計算する大量の事前計算フェーズから成ること意味する
1 for every item i 2 for every other item j 3 for every user u expressingpreference for both i and j 4 add the difference in preference of u for i and j to an average
- そして、推薦アルゴリズムは下記のとおり
1 for every item i the user u express no preferencefor 2 for every item j that user u expresses a preference for 3 find the average preference difference between j and i 4 add this diff to preference of u value for j 5 add this to a running average 6 return the top items, ranked by these averages
アイテムベースの推薦のように、そのパフォーマンスはデータモデル内のユーザ数には依存せず、事前に計算されるすべてのアイテムのペアの間の嗜好度の平均との差のみに依存する
すべてのアイテム間の嗜好度の差を格納するために必要なメモリはアイテム数の二乗で増えていく。アイテム数が2倍になればメモリは4倍必要
スロープワンの実践
- 類似度の計測方法は不要で必要なのは下記のみ
1 new SlopeOneRecommender(model)
ピアソン相関のように、スロープワンアルゴリズムのもっともシンプルな形は脆弱性を持っている。アイテム間の差はそれがどのぐらい信頼できるか、どれくらいの量のデータに基づいているかということに関係なく重みとして与えられるということ
SlopeOneRe
commenderは2種類の重み付けを提供する。アイテム数と標準偏差に基づいた重み付けである スロープワンはすべてのユーザの現在の嗜好度に差を加えて評価されたものの平均で評価を形成する
アイテム数による重み付けはより多くのデータに基づく時に重みをさらに重くする
同じように、標準偏差による重み付けは、嗜好度の標準偏差の差に基づき重み付けを行う。標準偏差が小さい場合には重み付けは重くなる
もし二つの映画の間の嗜好度の差が多くのユーザについて矛盾がないのであれば、それは信頼できると思われるためより多くの重みを与えられる
もしそれがユーザ間の場合とかなり異なってしまうのであれば、それは強調されるべきではない
この効果を無効にするには下記のようにする
1 DiffStorage diffStorag e = new MemoryDiff Storage( 2 model, Weighting.UNWEIGHTED , Long.MAX_VALUE)); 3 return new SlopeOneRe commender( 4 model, 5 Weighting.UNWEIGHTED , 6 Weighting.UNWEIGHTED , 7 diffStorag e);
DiffStorag eとメモリの検討
スロープワンはメモリ消費の代償を伴う
MySQLJDBCD
iffStorage などの実装は、データベースからの差異データの計算や更新を可能にする これはMySQLJDBCD
ataModelのようなJDBCに基づくDataModel実装の中で使われる必要がある
1 AbstractJDBCDataMode l model = new MySQLJDBCD ataModel(); 2 DiffStorag e diffStorag e = new MySQLJDBCD iffStorage (model); 3 Recommende r recommende r = new SlopeOneRe commender( 4 model, Weighting.WEIGHTED, Weighting.WEIGHTED, diffStorag e);
事前計算の分離
- Hadoopによる差異の計算がサポートされている
新しい実験的な推薦手法
特異値分解による推薦
SVDRecomme
nderは特異値分解に基づいている これは線形代数では重要な技術
SVDは独立したアイテムへのユーザの嗜好度の世界を、より汎用的であまり多くない数の特徴(例えばジャンルなど)の世界に要約する
この処理はいくつかの情報を失うが、推薦結果を改善することが可能なことがある。入力データを有効な方法で整形する
SVDRecomme
nderの使い方はシンプルで下記のとおり
1 new SVDRecommender(model, new ALSWRFacto rizer(model, 10, 0.05, 10))
SVDRecomme
nderはFactorizer を使用し、ここではALSWRFacto rizer実装を使用している 最初の数値の引数はSVDが対象とする特質の数で、正解は存在しない
二つ目の引数はラムダでこれはfactorizer
の正規化機能を制御する 最後の引数はトレーニングステップ数
この実装の大きな問題点はSVDの計算がメモリ上で行われるということ
これはデータセットのすべてをメモリ上に格納する必要があるが、それはアピールするポイントではなく、それは出力の質を大きく低下させることなく入力データを減らすことができるためである
直線補間によるアイテムベースの推薦
直線補間は幾分異なるアイテムベースの推薦方法で、KnnItemBas
edRecommen derとして実装されている Knnはk nearest neighborsの略で、NearestNUs
erNeighbor hoodとしても具体化されている 直線補間アルゴリズムはuser neighborho
odのコンセプトを用いているが、方法は異なる このアルゴリズムはいくつかの線形代数の手法によりすべてのアイテムのペアの最適な重みのセットを計算し、ここに直線補間が用いられる
KnnItemBas
edRecommen derの使い方は下記のとおり
1 ItemSimilarity similarity = new LogLikelih oodSimilar ity(model); 2 Optimizer optimizer = new NonNegativ eQuadratic Optimizer(); 3 return new KnnItemBas edRecommen der(model, similarity , optimizer, 10);
このコードではもっとも近い10アイテムを計算するのに対数尤度による類似度の測定手法を用いている
この実装はとても機能的だが、現在の形ではほどよいサイズのデータセットにおいても遅い
集団ベースの推薦
推薦はそれぞれの集団に行われ、推薦されたアイテムは最大のユーザ数に対してもっとも興味のあるものである
この手法の良い点としては実行時の推薦処理が速いことで、それはほとんどが事前に計算されるためである
この方法では個人ではなくグループに対しての推薦が計算されるため、個人性は少なくなる
この手法は嗜好度データが少ない新しいユーザに対して推薦を行う場合により効果的である
集団化には長時間かかり、この案を実装したTreeCluste
ringRecomm enderを用いた下記の例を実行する場合にもそれがわかる
1 UserSimilarity similarity = new LogLikelih oodSimilar ity(model); 2 ClusterSim ilarity clusterSim ilarity = 3 new FarthestNe ighborClus terSimilar ity(similarity ); 4 return new TreeCluste ringRecomm ender(model, clustersim ilarity, 10);
2つのSimilarity
実装を用いており、ひとつは二人のもっとも類似しているユーザのペアの類似度として集団の類似度を定義し、もうひとつはもっとも類似していないユーザの類似度として集団の類似度を定義する いずれのケースでも集団の端の一つの外れ値が集団の意味合いをゆがめるリスクがある
メンバー間の距離が平均的な二つの集団でも、一方の端に近づくとNearestNei
ghborClust erSimilari tyにより実装されたmost-simil ar-userルールにより極めて近いとみなされる 上記のコードでFarthestNe
ighborClus terSimilar ityにより実装されたleast-simi lar-userルールも同じように、他方の集団から遠く離れた外れ値を含んでいる場合、近い集団でも距離があるとみなされてしまう 三つ目のアプローチは集団の距離を中心値の距離により定義する方法で、どちらにたいしても使用可能であるがまだMahoutでは実装されていない
他の推薦手法との比較
コンテンツベースの技術をMahoutに導入する
アイテムベースの推薦の類似度はItemSimila
rity実装にカプセル化されているが、アイテムの属性に基づいた実装にできない理由はない 例えば映画の類似度をジャンルやディレクター、出演者、発売年などの関数として定義するかも知れず、この実装を従来のアイテムベースの中で使用することはコンテンツベースの推薦の例
コンテンツベースの推薦をより深く見る
協調フィルタリングではユーザとアイテム間の関連の嗜好度に基づいて計算される
関連を発見することとアイテムの属性を発見することで、よりユーザとアイテムの関連の意味合いに基づいた推薦エンジンを構築することが可能になる
Mahoutの推薦はまだこれらの技術を取り入れていないが、将来のバージョンで扱われる流れである
モデルベースの推薦との比較
この技術は既存の嗜好度データに基づきいくつかのユーザの嗜好度モデルを構築し、新しい嗜好度データを推測しようとするもの
これらは通常ユーザの嗜好度からのみ導き出されるので、この技術は一般的には協調フィルタリングのカテゴリに含まれる
このアルゴリズムは全てのユーザの嗜好度からアイテムが好まれる確率を判定しようとし、結果的に推薦のランク付けを行う
データから「ユーザがアイテムXとYを好むとき、アイテムZも好まれる」というようなルールを学習し、そのルールの信頼性を判断することで、最も新しく嗜好性のあるアイテムを推薦することが出来る
集団はどのユーザがグループを形成し、それゆえに嗜好性の方向もおなじであるというモデルを表す。Mahoutはこの狭義のモデルベースの推薦をサポートしているが、その範囲は執筆時点では開発中である