Mahout in Action Chapter 4 についてのメモ。
4.2 ユーザベースの推薦の詳細
4.2.1 アルゴリズム
- ユーザにアイテムを推薦する処理は下記のとおり。ユーザは u で表されている
sh>>
for every item i that u has no preference for yet
for every other user v that has a preference for i
compute a similarity s between u and v
incorporate preference of v for i, weighted by s, into a running average
return the top items, ranked by weighted average
<<--
外側のループはユーザがまだ嗜好度を持っていない、推薦対象になりうるアイテムすべてに対するもの
内側のループはこの推薦対象になりうるアイテムについて嗜好度を持っているユーザに対するもので、その嗜好度を参照している
最後にそれらの値の平均値を計算し、重み平均とする
それぞれの嗜好値はそのユーザがターゲットのユーザとどれぐらい類似しているかの平均値から重み付けされる
ユーザが類似しているほど、重みが嗜好度に加えられる
すべてのアイテムについて検証するのはひどく遅い。
実際は最も類似しているユーザを計算した後、そのユーザに知られているアイテムのみについて検討される
sh>>
for every other user w
compute a similarity s between u and w
retain the top users, ranked by similarity, as a neighborhood n
for every item i that some user in n has ap preference for, but that u has no preference for yet
for every other user v in n that has a preference for i
compute a similarity s between u and v
incorporate preference of v for i, weighted by s, into a running averate
<<--
一番の違いは最も類似しているユーザが何に興味を持っているかを探す前に、類似しているユーザを探している点
これは基本的なユーザベースの推薦アルゴリズムで、Mahoutにも実装されている
4.2.2 GenericUserBasedRecommenderによるアルゴリズムの実装
- Mahoutは推薦エンジンを構築するためのコンポーネントの集合で、以下のようなコンポーネントから構成されている
sh>>
データモデル, DataModelによって実装される
ユーザ同士の類似度, UserSimilarityによって実装される
近隣者の定義, UserNeighborhoodによって実装される
推薦エンジン, Recommenderによって実装される（ここではGenericUserBasedRecommender）
<<--
4.2.3 GroupLensによる探索
- GroupLensのデータを処理するためにはGroupLensDataModelを使えばよい
java>>
DataModel model =
new GroupLensDataModel(new File("ratings.dat"));
UserSimilarity similarity =
new PearsonCorrelationSimilarity(model);
UserNeighborhood neighborhood =
new NearestNUserNeighborhood(100, similarity, model);
Recommender recommender =
new GenericUserBasedRecommender(model, neighborhood, similarity);
LoadEvaluator.runLoad(recommender);
<<--
- このコードを動かすと、OutOfMemoryErrorが発生するので、メモリを増やす必要がある
4.2.5 サイズ固定のneighborhood
- 類似度が高い順にN個のデータが使われる
4.2.6 閾値ベースのneighborhood
- 類似度の閾値を決めてそれ以上の類似度を持つユーザを取り出すことが可能
4.3 類似度の測定方法の詳細
- ユーザベースの推薦で他に重要なのはUserSimilarity実装。ユーザベースの推薦の大部分はこのコンポーネントに依存している
4.3.1 ピアソン相関ベースの類似度
ピアソン相関は -1 から 1 までの数値で、2組の配列の傾向を測定するもので、線形の関係になる
この傾向が高い場合は相関係数は1に近づく
すべての値において関連が小さい場合は、相関係数は0に近づく
関連がまったく逆の場合、一方の組の値が高くなるときに他方の値が小さくなるようなケースでは、相関係数は-1に近づく
類似度の計算は双方のユーザがそのアイテムに対して嗜好度を持っている場合のみ可能
4.3.2 ピアソン相関の問題点
ユーザ間で一致するアイテムの数を評価に加えないことが、推薦エンジンとしては欠点
ユーザ間で一致するアイテムがひとつしかない場合、相関は計算されない
全ての嗜好度が同一のユーザについては相関が計算されない
4.3.3 重み付けを使う
PearsonCorrelationSimilarityは重みを追加して、ピアソン相関の問題点を軽減する
PearsonCorrelationSimilarityのコンストラクタの第二引数にWeighting.WEIGHTEDを渡すことができ、これによってデータ数が多い場合には1.0方向へ、少ない場合には-1.0方向へ補正される
ユークリッド距離による類似度の定義
- 前述のサンプルコードのUserSimilarity実装部分を変更してEuclideanDistanceSimilarityを使用する
java>>
new EuclideanDistanceSimilarity(model)
<<--
この実装はユーザ間の距離を基にしている
ユーザがより類似している場合にこの値は小さくなる
この実装が実際に戻す値は 1 / (1 + distance)
コサイン測定による類似性の適用
空間にポイントされ可視化された嗜好度データによる類似度計測方法
ユーザ間の類似度が低い場合、それぞれの嗜好度を表す線の距離は広がり、角度も大きくなる
この角度のコサインが類似度を導く
コサイン値は常に -1 から 1 の間で、小さい角度の場合は 1 に近づき、180度近い大きい角度の場合は -1 に近づく
これは良いことで、小さい角度の場合は類似度が高いということで 1 に近く、大きい角度の場合は -1 に近づくということだからである
コサイン測定による類似度の測定はよく強調フィルタリングによる調査と関連付けられる
この類似度測定法を使用するにはPearsonCorrelationSimilarityを使うだけでよい
スピアマン相関での相対的階級による類似度定義
スピアマン相関はわれわれの目的にとってはピアソン相関の興味深い変種
オリジナルの相関嗜好度データの相関ではなく、嗜好度データの相対ランクに基づいて相関を計算する
このプロセスはいくつかの情報を失うが、嗜好度データの本質である順位付けは維持され、正確な嗜好度合いについての情報は失われる
SpearmanCorrelationSimilarityはこの考えを実装する
前出のサンプルコードのUserSimilarityの実装でSpearmanCorrelationalSimilarityを使うことで試すことができる
この実装は計算のために簡単ではない処理を行いランクを保存しなければならないため、かなり遅い
しかしながら小さいデータセットに対しては向いているかもしれない
CachingUserSimilarityは他のUserSimirality実装をラップするUserSimilarity実装で、その実行結果をキャッシュする
計算処理はラップしているUserSimilarity実装に委譲し、その結果を内部的に保持しておく
java>>
UserSimilarity similarity = new CashingUserSimilarity(
new SpearmanCorrelationSimilarity(model), model)
<<--
evaluate()のtrainingPercentage引数を0.95から0.99に増やすことで、テストデータの量を5%から1%に減らすことで計算量を減らすことができる
これによって計算にかかる時間を数十分にすることができる
谷本係数により類似度の中の嗜好度データを無視する
おもしろいことに、嗜好度をすべて無視するUserSimilarity実装がある
TanimotoCoefficientSimilarityはその実装のひとつで、谷本係数を基にしている。この値はジャカール係数としても知られている
この値は嗜好性のあるアイテムの集合のうち、共通する部分の比率になる
二人のユーザのアイテムが完全に一致するとき、結果は1.0になり、共通部分がないとき、0.0になる。結果がマイナスになることはないが問題ない
結果を次の簡単な計算によって -1 から 1 の範囲に拡張することが出来る
similarity = 2・similarity - 1この計測方法は両方のユーザが嗜好度を持っているアイテムだけでなく、一方が嗜好度をもっているアイテムにも依存することに注意
この類似度計測方法を使う場合は、基になるデータにはブール値（Boolean）の嗜好度データのみを含める
対数尤度によるよりスマートな類似度の計算
対数尤度による類似度は、谷本係数のように二人のユーザに共通するアイテムの数を基にしているが、その他に多くの重複がある可能性がどれくら低いか、アイテムの総数、それぞれのユーザが嗜好性を持っているアイテムの数も含んでいる
二人のユーザ間での偶然による重複がどれくらい起こり得ないかを評価しようとするもの。すなわち、類似しないユーザ間で同じ映画に対する評価をもつことはあるが、類似しているユーザが全くありそうもない共通点を見せることがあるということ。
いくつかの統計的検定で、この類似度計測手法は二人のユーザ間でどれぐらい強く類似することがありそうもないかを断定しようと試みる。
結果の類似度の値は二人のユーザ間で偶然ではない重複がおこるとみなされる値
汎用化は難しいが、対数尤度による類似度は谷本係数による類似度より性能が優れている
嗜好度の推測
ときどき少なすぎるデータが問題になることがある。いくつかのケースにおいて、例えば、ピアソン相関はユーザ間で重複しているアイテムが一つの場合には類似度を計算することができない
データが欠損している部分にデフォルト値が挿入されるとどうか。この戦略はPreferenceInferrerインタフェースにより可能になっており、現在はAveragingPreferenceInferrerという実装がある
この実装はそれぞれのユーザの平均嗜好度を計算し、この平均値をまだユーザと関連のないアイテムの嗜好度として挿入する
UserSimilarityのsetPreferenceInferrer()メソッドを呼ぶことで使用可能
原則として実際のデータを元に純粋に情報を作るには何も加えないが、これは計算を急激に遅くする
Mahoutはアイテム間の類似度という概念も提供する。ユーザ間だけでなくアイテム間の類似度についても同様の計算が適用される
アイテムベースの推薦
- アイテムベースの推薦は、ユーザとユーザの代わりに、アイテムとアイテムがどれだけ類似しているかによって行われる。Mahoutでは、UserSimilarityの代わりにItemSimilarityを基にすることを意味する
アルゴリズム
sh>>
for every item i that u has no preference for yet
for every item j that u has a preference for
compute a similarity s between i and j
add preference of u for j, weighted by s, to a running average
return the top items, ranked by weighted average
<<--
アイテムベースの推薦を選択した方がよい理由の一つとしては、アイテムの数がユーザの数と比べて少ないとき、パフォーマンスの優位性はかなり大きくなるということ
また、一般的にアイテムはユーザよりも変更される点が少ない
事前に類似度を計算しておくことは、実行時の推薦スピードを速くする
Mahoutでは、GenericItemSimilarityクラスが事前の計算とItemSimilarityクラスからの結果を格納するのに使われる。これは今までに出てきたいずれの実装にも適用することが可能
アイテムベースの推薦の詳細
- GenericUserBasedRecommenderではなくGenericItemBasedRecommenderを使うコードは下記のとおり
java>>
public Recommender buildRecommender(DataModel model)
throws TasteException {
ItemSimilarity similarity = new PearsonCorrelationSimilarity(model);
return new GenericItemBasedRecommender(model, similarity);
}
<<--
PearsonCorrelationSimilarityはItemSimilarityインタフェースを実装しているのでここでも使用しており、これはUserSimilarityインタフェースについても同様
GenericItemBasedRecommenderはシンプルで、DataModelとItemSimilarityのみ必要。ItemNeighborhoodは不要。
すべてのUserSimilarityがItemSimilarityも実装しているわけではない
アイテムベースの推薦は一般的にアイテム数がユーザ数より少ないときはユーザベースの推薦より速い
スロープワンアルゴリズムによる推薦
- 新しいアイテムとその他のユーザの嗜好性のあるアイテムの嗜好度の差の平均を基に嗜好度を評価する
アルゴリズム
スロープワンという名前は推薦アルゴリズムが一つのアイテムとその他のアイテムの嗜好度の間にいくつかの直線関係があるという仮説から来ており、Yというアイテムの嗜好度を、Y=mx+bという式で表されるXの嗜好度を基にするのは妥当である
ここでスロープワンによる推薦は単純化するためのm=1:という仮説を追加する。この場合、b=y-xのみ残り、これはすべてのアイテムのペアの間での嗜好度の差
これはアルゴリズムは下記の様に、すべてのアイテム間の嗜好度の差を計算する大量の事前計算フェーズから成ること意味する
sh>>
for every item i
for every other item j
for every user u expressing preference for both i and j
add the difference in preference of u for i and j to an average
<<--
- そして、推薦アルゴリズムは下記のとおり
sh>>
for every item i the user u express no preference for
for every item j that user u expresses a preference for
find the average preference difference between j and i
add this diff to preference of u value for j
add this to a running average
return the top items, ranked by these averages
<<--
アイテムベースの推薦のように、そのパフォーマンスはデータモデル内のユーザ数には依存せず、事前に計算されるすべてのアイテムのペアの間の嗜好度の平均との差のみに依存する
すべてのアイテム間の嗜好度の差を格納するために必要なメモリはアイテム数の二乗で増えていく。アイテム数が2倍になればメモリは4倍必要
スロープワンの実践
- 類似度の計測方法は不要で必要なのは下記のみ
java>>
new SlopeOneRecommender(model)
<<--
ピアソン相関のように、スロープワンアルゴリズムのもっともシンプルな形は脆弱性を持っている。アイテム間の差はそれがどのぐらい信頼できるか、どれくらいの量のデータに基づいているかということに関係なく重みとして与えられるということ
SlopeOneRecommenderは2種類の重み付けを提供する。アイテム数と標準偏差に基づいた重み付けである
スロープワンはすべてのユーザの現在の嗜好度に差を加えて評価されたものの平均で評価を形成する
アイテム数による重み付けはより多くのデータに基づく時に重みをさらに重くする
同じように、標準偏差による重み付けは、嗜好度の標準偏差の差に基づき重み付けを行う。標準偏差が小さい場合には重み付けは重くなる
もし二つの映画の間の嗜好度の差が多くのユーザについて矛盾がないのであれば、それは信頼できると思われるためより多くの重みを与えられる
もしそれがユーザ間の場合とかなり異なってしまうのであれば、それは強調されるべきではない
この効果を無効にするには下記のようにする
java>>
DiffStorage diffStorage = new MemoryDiffStorage(
model, Weighting.UNWEIGHTED, Long.MAX_VALUE));
return new SlopeOneRecommender(
model,
Weighting.UNWEIGHTED,
Weighting.UNWEIGHTED,
diffStorage);
<<--
DiffStorageとメモリの検討
スロープワンはメモリ消費の代償を伴う
MySQLJDBCDiffStorageなどの実装は、データベースからの差異データの計算や更新を可能にする
これはMySQLJDBCDataModelのようなJDBCに基づくDataModel実装の中で使われる必要がある
java>>
AbstractJDBCDataModel model = new MySQLJDBCDataModel();
DiffStorage diffStorage = new MySQLJDBCDiffStorage(model);
Recommender recommender = new SlopeOneRecommender(
model, Weighting.WEIGHTED, Weighting.WEIGHTED, diffStorage);
<<--
事前計算の分離
- Hadoopによる差異の計算がサポートされている
新しい実験的な推薦手法
特異値分解による推薦
SVDRecommenderは特異値分解に基づいている
これは線形代数では重要な技術
SVDは独立したアイテムへのユーザの嗜好度の世界を、より汎用的であまり多くない数の特徴（例えばジャンルなど）の世界に要約する
この処理はいくつかの情報を失うが、推薦結果を改善することが可能なことがある。入力データを有効な方法で整形する
SVDRecommenderの使い方はシンプルで下記のとおり
java>>
new SVDRecommender(model, new ALSWRFactorizer(model, 10, 0.05, 10))
<<--
SVDRecommenderはFactorizerを使用し、ここではALSWRFactorizer実装を使用している
最初の数値の引数はSVDが対象とする特質の数で、正解は存在しない
二つ目の引数はラムダでこれはfactorizerの正規化機能を制御する
最後の引数はトレーニングステップ数
この実装の大きな問題点はSVDの計算がメモリ上で行われるということ
これはデータセットのすべてをメモリ上に格納する必要があるが、それはアピールするポイントではなく、それは出力の質を大きく低下させることなく入力データを減らすことができるためである
直線補間によるアイテムベースの推薦
直線補間は幾分異なるアイテムベースの推薦方法で、KnnItemBasedRecommenderとして実装されている
Knnはk nearest neighborsの略で、NearestNUserNeighborhoodとしても具体化されている
直線補間アルゴリズムはuser neighborhoodのコンセプトを用いているが、方法は異なる
このアルゴリズムはいくつかの線形代数の手法によりすべてのアイテムのペアの最適な重みのセットを計算し、ここに直線補間が用いられる
KnnItemBasedRecommenderの使い方は下記のとおり
java>>
ItemSimilarity similarity = new LogLikelihoodSimilarity(model);
Optimizer optimizer = new NonNegativeQuadraticOptimizer();
return new KnnItemBasedRecommender(model, similarity, optimizer, 10);
<<--
このコードではもっとも近い10アイテムを計算するのに対数尤度による類似度の測定手法を用いている
この実装はとても機能的だが、現在の形ではほどよいサイズのデータセットにおいても遅い
集団ベースの推薦
推薦はそれぞれの集団に行われ、推薦されたアイテムは最大のユーザ数に対してもっとも興味のあるものである
この手法の良い点としては実行時の推薦処理が速いことで、それはほとんどが事前に計算されるためである
この方法では個人ではなくグループに対しての推薦が計算されるため、個人性は少なくなる
この手法は嗜好度データが少ない新しいユーザに対して推薦を行う場合により効果的である
集団化には長時間かかり、この案を実装したTreeClusteringRecommenderを用いた下記の例を実行する場合にもそれがわかる
java>>
UserSimilarity similarity = new LogLikelihoodSimilarity(model);
ClusterSimilarity clusterSimilarity =
new FarthestNeighborClusterSimilarity(similarity);
return new TreeClusteringRecommender(model, clustersimilarity, 10);
<<--
2つのSimilarity実装を用いており、ひとつは二人のもっとも類似しているユーザのペアの類似度として集団の類似度を定義し、もうひとつはもっとも類似していないユーザの類似度として集団の類似度を定義する
いずれのケースでも集団の端の一つの外れ値が集団の意味合いをゆがめるリスクがある
メンバー間の距離が平均的な二つの集団でも、一方の端に近づくとNearestNeighborClusterSimilarityにより実装されたmost-similar-userルールにより極めて近いとみなされる
上記のコードでFarthestNeighborClusterSimilarityにより実装されたleast-similar-userルールも同じように、他方の集団から遠く離れた外れ値を含んでいる場合、近い集団でも距離があるとみなされてしまう
三つ目のアプローチは集団の距離を中心値の距離により定義する方法で、どちらにたいしても使用可能であるがまだMahoutでは実装されていない
他の推薦手法との比較
コンテンツベースの技術をMahoutに導入する
アイテムベースの推薦の類似度はItemSimilarity実装にカプセル化されているが、アイテムの属性に基づいた実装にできない理由はない
例えば映画の類似度をジャンルやディレクター、出演者、発売年などの関数として定義するかも知れず、この実装を従来のアイテムベースの中で使用することはコンテンツベースの推薦の例
コンテンツベースの推薦をより深く見る
協調フィルタリングではユーザとアイテム間の関連の嗜好度に基づいて計算される
関連を発見することとアイテムの属性を発見することで、よりユーザとアイテムの関連の意味合いに基づいた推薦エンジンを構築することが可能になる
Mahoutの推薦はまだこれらの技術を取り入れていないが、将来のバージョンで扱われる流れである
モデルベースの推薦との比較
この技術は既存の嗜好度データに基づきいくつかのユーザの嗜好度モデルを構築し、新しい嗜好度データを推測しようとするもの
これらは通常ユーザの嗜好度からのみ導き出されるので、この技術は一般的には協調フィルタリングのカテゴリに含まれる
このアルゴリズムは全てのユーザの嗜好度からアイテムが好まれる確率を判定しようとし、結果的に推薦のランク付けを行う
データから「ユーザがアイテムXとYを好むとき、アイテムZも好まれる」というようなルールを学習し、そのルールの信頼性を判断することで、最も新しく嗜好性のあるアイテムを推薦することが出来る
集団はどのユーザがグループを形成し、それゆえに嗜好性の方向もおなじであるというモデルを表す。Mahoutはこの狭義のモデルベースの推薦をサポートしているが、その範囲は執筆時点では開発中である
