情報システム解析学科 谷ゼミ 田中健太 森口麻里 吉野友美

Presentation on theme: "情報システム解析学科 谷ゼミ 田中健太 森口麻里 吉野友美"— Presentation transcript:

1 情報システム解析学科 谷ゼミ 5405019 田中健太 5405078 森口麻里 5405081 吉野友美
Trial program for movie rating prediction using Collaborative Filtering 協調フィルタリングを用いた 映画評価予測プログラムの試作 情報システム解析学科 谷ゼミ 　田中健太 　森口麻里 　吉野友美

2 目次 1. はじめに 2. 研究概要 2.1 User Base & Item Base（予測にジャンルの好みを用いる） 3. 実験方法
　　2.2 Slope one 　　2.3 ジャンル嗜好（オリジナル） 3. 実験方法 4. 結果・考察 5. 今後の課題

3 目次 1. はじめに 2. 研究概要 2.1 User Base & Item Base（予測にジャンルの好みを用いる） 3. 実験方法
　　2.2 Slope one 　　2.3 ジャンル嗜好（オリジナル） 3. 実験方法 4. 結果・考察 5. 今後の課題

4 研究 Computational Advertising 趣味・嗜好・行動の中から そのユーザーに合った広告を表示する
1. はじめに 研究 Computational Advertising 趣味・嗜好・行動の中から そのユーザーに合った広告を表示する

5 1. はじめに ・実際にどんなところに使われているか

6 1. はじめに

7 ・ユーザーに合った 広告を表示できる →広告メディアとして有力 ・ビジネス的にも 技術的にも興味深い分野
1. はじめに ・ユーザーに合った 　広告を表示できる 　→広告メディアとして有力 ・ビジネス的にも 　技術的にも興味深い分野 広告媒体 1 TV 2 インターネット 3 新聞 4 ラジオ Yahoo!JAPAN 掲示板より

8 1. はじめに レコメンドシステム ユーザーの趣味嗜好、購入履歴から そのユーザーがまだ購入、レンタルしたことがなく、
そのユーザーが満足するであろう商品を推薦、 提案しようというもの。

9 1. はじめに -米オンラインビデオレンタルの最大手 -賞金 $1,000,000 -レコメンドシステムの精度を10%改善する
NetFlix 　-米オンラインビデオレンタルの最大手 　-レコメンドシステムを使用 NetFlix Prize 　-2006/10/2 ～ 2011/10/2 　-賞金 $1,000,000 　-レコメンドシステムの精度を10%改善する 　　アルゴリズムを公募

10 データセット 1. はじめに ユーザー 映画 評価 NetFlix 480,000 20,000 100,000,000 MovieLens
レコメンドシステムの技術 - コンテンツベース - ルールベース - 協調フィルタリング 過去のユーザーの評価や行動履歴などを利用して 推薦対象のユーザーの嗜好を推測するものである。 データセット ユーザー 映画 評価 NetFlix 480,000 20,000 100,000,000 MovieLens 943 1,682 100,000

11 目次 1. はじめに 2. 研究概要 2.1 User Base & Item Base（予測にジャンルの好みを用いる） 3. 実験方法
　　2.2 Slope one 　　2.3 ジャンル嗜好（オリジナル） 3. 実験方法 4. 結果・考察 5. 今後の課題

12 2.1 User Base & Item Base 重要になっている考え 推薦対象のユーザーと趣味嗜好が似ているユーザーが
好むアイテムを推薦対象のユーザーも好むであろう 趣味嗜好が似ていないユーザーが好まないアイテムを 対象ユーザーが好むであろう

13 2.1 User Base & Item Base アイテム V W X Y Z A 2 5 B 1 C D 4 ユーザー

14 2.1 User Base & Item Base アイテム V W X Y Z A 2 5 B 1 C D 4 ユーザー

15 2.1 User Base & Item Base アイテム V W X Y Z A 2 5 B(似) 1 C(違) D(？) 4 ユーザー

16 2.1 User Base & Item Base アイテム V W X Y Z A 2 5 B 1 C D 4 ユーザー

17 2.1 User Base & Item Base 基本的な考え あるアイテムについて 推薦対象のユーザーの予測評価値を
他の類似したユーザーたちによる評価の加重平均を用いて計算 一般に使われる類似度計算アルゴリズム ・ピアソンの相関係数 ・ベクトル類似度 ・etc

18 2.1 User Base & Item Base 問題点 データセットの密度が疎の場合 →精度が悪くなる スケーラビリティの問題
→データが大きくなると計算が困難 コールドスタート問題 →過去のデータがない人には推薦不可能

19 2.1 User Base & Item Base ユーザーベースのアプローチ [Paul Resnick他,1994,CSCW]
(1).推薦対象のユーザーと他のユーザー間の類似度を計算 (2).類似度とユーザーの評価でアイテムの予測評価値を計算 アイテムベースのアプローチ [Badrul Sarwar他,2001,WWW10] (1).各アイテム間の類似度を計算 (2).推薦対象のユーザーが評価したアイテムとの類似度とその評価で 予測評価値を計算 参考資料 : 集合知プログラミング [Toby Segarn著,2008]他

20 2.1 User Base & Item Base アイテムの集合 ユーザーの集合 推薦対象ユーザー 表記法の定義
I = {i1,i2,...,im} アイテムの集合 U = {u1,u2,...,un} ユーザーの集合 ua 推薦対象ユーザー Ru(i) ユーザーuのアイテムiに対する評価 ユーザーuの平均評価 𝑅 𝑢

21 2.1 User Base & Item Base ～ユーザーベースの協調フィルタリング
予測対象アイテムについて (1) ua と他のユーザーuとの類似度を計算 (2) 1.ua と各ユーザーuの類似度×uの評価値の総和を計算 2.総和を上で用いた類似度の絶対値の和で割る

22 2.1 User Base & Item Base ～ユーザーベースの協調フィルタリング
(1) ua と他のユーザーu との類似度を計算する。 今回はピアソンの相関係数を使用 sim 𝑢,𝑢′ = 𝑡∈𝐼 𝑢 ∧𝐼 𝑢′ 𝑅 𝑢 𝑖 − 𝑅 𝑢 ⋅ 𝑅 𝑢′ 𝑖 − 𝑅 𝑢′ 𝑡∈𝐼 𝑢 ∧𝐼 𝑢′ 𝑅 𝑢 𝑖 − 𝑅 𝑢 𝑡∈𝐼 𝑢 ∧𝐼 𝑢′ 𝑅 𝑢′ 𝑖 − 𝑅 𝑢′ 2

23 2.1 User Base & Item Base ～ユーザーベースの協調フィルタリング
相関係数の値について 相関係数の値の範囲は-1～1 -1に近い：趣味嗜好が似ていない 1に近い：趣味嗜好が似ている

24 2.1 User Base & Item Base ～ユーザーベースの協調フィルタリング
相関係数を求めるには2人の共通したアイテムを用いる a b c d e f g h i j k ua 1 4 5 2 u 3 計算した値は信用できるのか？ →共通したアイテムが5未満の場合：相関係数を0 実験ではさらに相関係数が正の値のみを評価予測に使用する 2種類を使用

25 2.1 User Base & Item Base ～ユーザーベースの協調フィルタリング
(2) 1.ua と各ユーザーuの類似度×uの評価値の総和を計算 2.総和を上で用いた類似度の絶対値の和で割る 𝑅 𝑢 𝑎 𝑖 = 𝑢∈𝑈 𝑖 sim 𝑢 𝑎 ,𝑢 ⋅ 𝑅 𝑢 𝑖 𝑢∈𝑈 𝑖 ∣ sim 𝑢 𝑎 ,𝑢 ∣

26 2.1 User Base & Item Base ～アイテムベースの協調フィルタリング
予測対象アイテムについて (1) 各アイテムi 間の類似度を計算する (2) 1.ua の評価済みアイテムとの類似度 ×ua の評価済みアイテムの評価値の総和を計算 2.総和を上で用いた類似度の絶対値の和で割る

27 2.1 User Base & Item Base ～アイテムベースの協調フィルタリング
ユーザーベースの協調フィルタリングと同様に ピアソンの相関係数を使用 sim 𝑖,𝑖′ = 𝑢∈𝑈 𝑖 ∧𝑈 𝑖′ 𝑅 𝑢 𝑖 − 𝑅 𝑢 ⋅ 𝑅 𝑢 𝑖′ − 𝑅 𝑢 𝑢∈𝑈 𝑖 ∧𝑈 𝑖′ 𝑅 𝑢 𝑖 − 𝑅 𝑢 𝑢∈𝑈 𝑖 ∧𝑈 𝑖′ 𝑅 𝑢 𝑖′ − 𝑅 𝑢 2

28 2.1 User Base & Item Base ～アイテムベースの協調フィルタリング
(2) 1.ua の評価済みアイテムとの類似度 ×ua の評価済みアイテムの評価値の総和を計算 2.総和を上で用いた類似度の絶対値の和で割る 𝑅 𝑢 𝑎 𝑖 = 𝑖′∈𝐼 𝑢 𝑎 sim 𝑖,𝑖′ ⋅ 𝑅 𝑢 𝑎 𝑖′ 𝑖′∈𝐼 𝑢 𝑎 ∣ sim 𝑖,𝑖′ ∣

29 2.1 User Base & Item Base ～アイテムベースの協調フィルタリング
キーとなる考え 推薦対象ユーザーが好むジャンルのアイテムは評価が高くなる 好まないジャンルのアイテムは評価が低くなる 表記法の追加 G = {g1,g2,...,go} ジャンルの集合 G(i) アイテムiが 属するジャンルの集合 GRu(i) アイテムiが属するジャンルに対するユーザーuの平均評価

30 ユーザーの平均評価×1.25以上 like ユーザーの平均評価×0.75以下 dislike それ以外 unknown
2.1 User Base & Item Base ～評価予測にユーザーのジャンルの好みを追加する like、dislikeの定義 GRu(i)の値が ユーザーの平均評価×1.25以上 like ユーザーの平均評価×0.75以下 dislike それ以外 unknown

31 2.1 User Base & Item Base ～評価予測にユーザーのジャンルの好みを追加する
先ほどのlike、dislike、unknownを用いるために 予測値の計算の置き換え 𝑅 𝑢 𝑎 𝑖 = 𝑢∈𝑈 𝑖 sim 𝑢 𝑎 ,𝑢 ⋅ 𝑅 𝑢 𝑖 𝑢∈𝑈 𝑖 ∣ sim 𝑢 𝑎 ,𝑢 ∣ +𝜆 𝑅 𝑢 𝑎 𝑖 = 𝑖′∈𝐼 𝑢 𝑎 sim 𝑖,𝑖′ ⋅ 𝑅 𝑢 𝑎 𝑖′ 𝑖′∈𝐼 𝑢 𝑎 ∣ sim 𝑖,𝑖′ ∣ +𝜆

32 λについてlike、dislike、unknownによって値を変更
2.1 User Base & Item Base ～評価予測にユーザーのジャンルの好みを追加する λについてlike、dislike、unknownによって値を変更 μ = 0.1(10%) or 0.05(5%)

33 目次 1. はじめに 2. 研究概要 2.1 User Base & Item Base（予測にジャンルの好みを用いる） 3. 実験方法
　　1.1 動機 　　1.2 協調フィルタリングとは 2. 研究概要 　　2.1 User Base & Item Base（予測にジャンルの好みを用いる） 　　2.2 Slope one 　　2.3 ジャンル嗜好（オリジナル） 3. 実験方法 4. 結果・考察 5. 今後の課題

34 Slope Oneアルゴリズム [D Lemire他, 2005, SIAM]
個々のユーザーのアイテム評価値間差分を算出し、 全ユーザーについて算出された アイテム評価値間差分の平均値を算出し、 この算出結果を元にレコメンド結果を出す。 ユーザ間の相関値を算出する必要がない。

35 X Y 太郎 2 3 花子 ? 2.2 Slope One 太郎のアイテム評価の差は 1 ⇒花子さんは Y を 4 と評価 ・簡単な例
太郎のアイテム評価の差は　1　 ⇒花子さんは Y を　4　と評価　 アイテム X Y 太郎 2 3 花子 ? ユーザー

36 X Y 一太郎 2 3 二太郎 5 三太郎 1 花子 ? 2.2 Slope One 一太郎の差は 1 二太郎の差は 3
アイテム X Y 一太郎 2 3 二太郎 5 三太郎 1 花子 ? 一太郎の差は　1 二太郎の差は　3 三太郎は 　両方評価していないので無視 ⇒平均偏差　(1+3)/2 = 2 ⇒花子さんは 　　　　Yを　5　と評価 ユーザー

37 Uj,i：jとi を評価しているユーザーの集合 |A|：Aの総数
2.2 Slope One 𝑑𝑒𝑣 𝑗,𝑖 = 𝑢∈ 𝑈 𝑗,𝑖 𝑅 𝑢,𝑗 − 𝑅 𝑢,𝑖 ∣ 𝑈 𝑗,𝑖 ∣ i,j：アイテム(映画)　u：ユーザー Ru,i：u による i の評価 Uj,i：jとi を評価しているユーザーの集合 |A|：Aの総数

38 X Y Z 一太郎 2 3 1 二太郎 5 4 花子 ? 2.2 Slope One ⇒devZ,X = 0.5
アイテム X Y Z 一太郎 2 3 1 二太郎 5 4 花子 ? ユーザー ⇒devZ,X = 0.5 ⇒devZ,Y = (-2-1)/2 = -1.5 ⇒花子のCの評価は　(3+0.5)+(4-1.5)/2 = 3

39 i,j：アイテム(映画) u：ユーザー Ru,i,ui：u による i の評価 Ru：u が評価したアイテムの集合 |A|：Aの総数
2.2 Slope One 𝑃 𝑅 𝑢,𝑗 = 1 ∣ 𝑅 𝑢 ∣ 𝑖∈ 𝑅 𝑢 𝑑𝑒𝑣 𝑗,𝑖 + 𝑢 𝑖 i,j：アイテム(映画)　u：ユーザー Ru,i,ui：u による i の評価 Ru：u が評価したアイテムの集合 |A|：Aの総数

40 2.2 Slope One ～Weighted Slope-One
平均偏差について 1人の評価を元に出した値と 1000人の評価を元に出した値では 重みが違う。 𝑃 𝑤 𝑅 𝑢,𝑗 = 𝑖∈ 𝑅 𝑢 𝑑𝑒𝑣 𝑗,𝑖 + 𝑢 𝑖 ∣ 𝑈 𝑖,𝑗 ∣ 𝑖∈ 𝑅 𝑢 ∣ 𝑈 𝑗,𝑖 ∣

41 2.2 Slope One ～Bi-polar Slope-One
好き嫌いに分けて予想する 判定基準 × （評価は1~5なので）３ ・ ユーザーの評価の平均 dislike ＜ aveu ＜ like 𝑃 𝑏𝑝 𝑅 𝑢,𝑗 = 𝑖∈ 𝑅 𝑢 𝑙𝑖𝑘𝑒 𝑑𝑒𝑣 𝑗,𝑖 𝑙𝑖𝑘𝑒 + 𝑢 𝑖 ∣ 𝑈 𝑖,𝑗 𝑙𝑖𝑘𝑒 ∣ + 𝑖∈ 𝑅 𝑢 𝑑𝑖𝑠𝑙𝑖𝑘𝑒 𝑑𝑒𝑣 𝑗,𝑖 𝑑𝑖𝑠𝑙𝑖𝑘𝑒 + 𝑢 𝑖 ∣ 𝑈 𝑖,𝑗 𝑑𝑖𝑠𝑙𝑖𝑘𝑒 ∣ 𝑖∈ 𝑅 𝑢 𝑙𝑖𝑘𝑒 ∣ 𝑈 𝑖,𝑗 𝑙𝑖𝑘𝑒 ∣ + 𝑖∈ 𝑅 𝑢 𝑑𝑖𝑠𝑙𝑖𝑘𝑒 ∣ 𝑈 𝑖,𝑗 𝑑𝑖𝑠𝑙𝑖𝑘𝑒 ∣

42 2.2 Slope One ～提案 最低の重みは0 Weighted Slope Oneにおいて （誰にも評価されていないアイテムがある場合
その予測値は0になる。） 　→ 最低の重みを1にする （誰にも評価されていないアイテムを評価するときには ユーザーの平均を用いることが出来る）

43 目次 1. はじめに 2. 研究概要 2.1 User Base & Item Base（予測にジャンルの好みを用いる） 3. 実験方法
　　1.1 動機 　　1.2 協調フィルタリングとは 2. 研究概要 　　2.1 User Base & Item Base（予測にジャンルの好みを用いる） 　　2.2 Slope one 　　2.3 ジャンル嗜好（オリジナル） 3. 実験方法 4. 結果・考察 5. 今後の課題

44 ユーザーのジャンル嗜好を求めて、同じ嗜好を持つ ユーザーの評価を参考に評価する
2.3 ジャンル嗜好 ユーザーのジャンル嗜好を求めて、同じ嗜好を持つ ユーザーの評価を参考に評価する アクション映画最高！ アニメ大好き！ ですよね！

45 2.3 ジャンル嗜好 基本手順 １．それぞれのユーザーのジャンル平均を求める ２．ジャンル平均を求めた上で、そのジャンルを好むか 好まないか判断する ３．その映画を好むグループと好まないグループに分け て、それぞれで平均をだす ４．未評価の映画に対して、その映画を好むか好まない か判断し、評価する

46 2.3 ジャンル嗜好 藤巻 山崎 戸張 ２ ５ ３ ４ アクション アニメ １ ０ ５ 好む 好まない ５ ２ ４ ２．５ 藤巻 山崎 戸張
A ２ ５ B ３ ４ アクション アニメ A １ ０ B ５ 好む 好まない A ５ ２ B ４ ２．５ 藤巻 山崎 戸張 アクション ４ ３ ３．５ ジャンル ２

47 基本手順との変更点 (1)基本手順での評価結果にジャンル平均との平均を 出す (2)好む、好まないの他に普通という基準と設ける
2.3 ジャンル嗜好 基本手順との変更点 (1)基本手順での評価結果にジャンル平均との平均を 出す (2)好む、好まないの他に普通という基準と設ける

48 (1)基本手順での評価結果にジャンル平均との平均を 出す
2.3 ジャンル嗜好 (1)基本手順での評価結果にジャンル平均との平均を 出す 山崎 藤巻 戸張 Ａ ２ ５ Ｂ ４ アクション アニメ Ａ １ ０ Ｂ ４．５ 好む 好まない Ａ ５ ２ Ｂ ４ 山崎 藤巻 戸張 アクション ４ ３ ３．５ アニメ ２

49 (2)好む、好まないの他に普通という基準と設 ける
2.3 ジャンル嗜好 (2)好む、好まないの他に普通という基準と設 ける 山崎 藤巻 戸張 上村 Ａ ２ ３ ５ Ｂ ４ １ アクション アニメ Ａ １ ０ Ｂ ５ 山崎 藤巻 戸張 上村 アクション ５ ２ ３ アニメ ４ １ 好む 普通 好まない A ５ ３ ２ B ４．５ １

50 目次 1. はじめに 2. 研究概要 2.1 User Base & Item Base（予測にジャンルの好みを用いる） 3. 実験方法
　　1.1 動機 　　1.2 協調フィルタリングとは 2. 研究概要 　　2.1 User Base & Item Base（予測にジャンルの好みを用いる） 　　2.2 Slope one 　　2.3 ジャンル嗜好（オリジナル） 3. 実験方法 4. 結果・考察 5. 今後の課題

51 3. 実験方法 実験環境 データセットについて MovieLens(ミネソタ大学提供) 各ユーザー毎に評価数20は保証されている。
CPU Athlon メモリ 1024MB OS CentOS5.2 データセットについて MovieLens(ミネソタ大学提供) 　　各ユーザー毎に評価数20は保証されている。 ユーザー数 943 映画数 1682 評価数 10万

52 分割学習法 3. 実験方法 各ユーザー毎にランダムに10評価抜いたデータを 予測対象データとし、 残りを予測のためのデータとする。
これを10組作成し実験を行い、精度を出し、 その平均を比較する。

53 MAEの値が0に近ければ近いほど 誤差が少なく、精度が良い。 3. 実験方法 精度 → 今回は精度を比較するためにMAEを採用
MAE・・・Mean Absolute Error(平均絶対誤差) N：予測対象データ数=9430 MAEの値が0に近ければ近いほど 誤差が少なく、精度が良い。

54 3. 実験方法 ～実験に使用したプログラム 計19個(C++) ・ユーザーベース ･アイテムベース ･Slope One
3. 実験方法　～実験に使用したプログラム ・ユーザーベース 　+ジャンルの好みを用いる(0.1 or 0.05) ･アイテムベース 上の6種類× 相関係数の全体を用いる(type A) or 正の値のみを用いる(type B) ･Slope One ･Weighted Slope One（重みを2通り） ･bi-polar Slope One ･ジャンル嗜好（オリジナル） 計19個(C++)

55 目次 1. はじめに 2. 研究概要 2.1 User Base & Item Base（予測にジャンルの好みを用いる） 3. 実験方法
　　1.1 動機 　　1.2 協調フィルタリングとは 2. 研究概要 　　2.1 User Base & Item Base（予測にジャンルの好みを用いる） 　　2.2 Slope one 　　2.3 ジャンル嗜好（オリジナル） 3. 実験方法 4. 結果・考察 5. 今後の課題

56 ・アイテムベースのほうが優秀 ・正の値のみを用いると、精度が上がる
4. 結果・考察　～既存アルゴリズム 精度 ユーザーベース(type A) (type B) アイテムベース(type A) ・アイテムベースのほうが優秀 ・正の値のみを用いると、精度が上がる

57 ・重みをかけたほうが精度が高い ・bi-polarはより精度が高くなるとされているが、 今回はデータ量が少なかったせいか精度が落ちている
4. 結果・考察　～既存アルゴリズム 精度 ユーザーベース(type A) (type B) アイテムベース(type A) Slope One Weighted SO ・重みをかけたほうが精度が高い ・bi-polarはより精度が高くなるとされているが、 　今回はデータ量が少なかったせいか精度が落ちている

58 既存のものと比較して 値がほとんど変化していない →unknownの幅を取りすぎたのではないか？
4. 結果・考察　～オリジナル 精度 ユーザーベース(type A) 0.1 (type A) 0.05 アイテムベース(type A) 0.1 ユーザーベース(type B) 0.1 (type B) 0.05 アイテムベース(type B) 0.1 既存のものと比較して 値がほとんど変化していない →unknownの幅を取りすぎたのではないか？

59 4. 結果・考察 ～オリジナル ・多少だが精度は上がった。 精度 Weighted SO 0.762692 Weighted SO(改)
4. 結果・考察　～オリジナル 精度 Weighted SO Weighted SO(改) ・多少だが精度は上がった。

60 ・基本手順と比較して、ジャンル平均を加えたものは僅かによく なった。 ・好む好まない普通の３タイプにわけたものは逆に悪くなった。
4. 結果・考察　～オリジナル 精度 ジャンル嗜好 ジャンル嗜好２ ジャンル嗜好３ ・基本手順と比較して、ジャンル平均を加えたものは僅かによく なった。 ・好む好まない普通の３タイプにわけたものは逆に悪くなった。

61 目次 1. はじめに 2. 研究概要 2.1 User Base & Item Base（予測にジャンルの好みを用いる） 3. 実験方法
　　1.1 動機 　　1.2 協調フィルタリングとは 2. 研究概要 　　2.1 User Base & Item Base（予測にジャンルの好みを用いる） 　　2.2 Slope one 　　2.3 ジャンル嗜好（オリジナル） 3. 実験方法 4. 結果・考察 5. 今後の課題

62 [1] 別の手法を取り入れる -クラスタリング -特異値分解(SVD) [2] データベースの利用・マシンスペックの改善
5. 今後の課題 [1] 別の手法を取り入れる -クラスタリング -特異値分解(SVD) [2] データベースの利用・マシンスペックの改善 ユーザー 映画 評価 NetFlix 480,000 20,000 100,000,000 MovieLens 943 1,682 100,000

63 fin