uの映画

Trial program for movie rating prediction
using Collaborative Filtering
協調フィルタリングを用いた
映画評価予測プログラムの試作
情報システム解析学科 谷ゼミ
5405019　田中健太
5405078　森口麻里
5405081　吉野友美
目次
2/63
1. はじめに
2. 研究概要
2.1 User Base & Item Base（予測にジャンルの好みを用いる）
2.2 Slope one
2.3 ジャンル嗜好（オリジナル）
3. 実験方法
4. 結果・考察
5. 今後の課題
目次
3/63
1. はじめに
2. 研究概要
2.1 User Base & Item Base（予測にジャンルの好みを用いる）
2.2 Slope one
2.3 ジャンル嗜好（オリジナル）
3. 実験方法
4. 結果・考察
5. 今後の課題
4/63
1. はじめに
研究
Computational Advertising
趣味・嗜好・行動の中から
そのユーザーに合った広告を表示する
1. はじめに
・実際にどんなところに使われているか
5/63
1. はじめに
6/63
7/63
1. はじめに
広告媒体
・ユーザーに合った
広告を表示できる
→広告メディアとして有力
・ビジネス的にも
技術的にも興味深い分野
1
TV
2
インターネット
3
新聞
4
ラジオ
Yahoo!JAPAN 掲示板より
1. はじめに
レコメンドシステム
ユーザーの趣味嗜好、購入履歴から
そのユーザーがまだ購入、レンタルしたことがなく、
そのユーザーが満足するであろう商品を推薦、
提案しようというもの。
8/63
1. はじめに
NetFlix
-米オンラインビデオレンタルの最大手
-レコメンドシステムを使用
NetFlix Prize
-2006/10/2 ～ 2011/10/2
-賞金 $1,000,000
-レコメンドシステムの精度を10%改善する
アルゴリズムを公募
9/63
10/63
1. はじめに
レコメンドシステムの技術
- コンテンツベース
- ルールベース
-
協調フィルタリング
過去のユーザーの評価や行動履歴などを利用して
推薦対象のユーザーの嗜好を推測するものである。
データセット
NetFlix
MovieLens
ユーザー
480,000
943
映画
評価
20,000 100,000,000
1,682
100,000
目次
11/63
1. はじめに
2. 研究概要
2.1 User Base & Item Base（予測にジャンルの好みを用いる）
2.2 Slope one
2.3 ジャンル嗜好（オリジナル）
3. 実験方法
4. 結果・考察
5. 今後の課題
2.1 User Base & Item Base
重要になっている考え
推薦対象のユーザーと趣味嗜好が似ているユーザーが
好むアイテムを推薦対象のユーザーも好むであろう
趣味嗜好が似ていないユーザーが好まないアイテムを
対象ユーザーが好むであろう
12/63
13/63
2.1 User Base & Item Base
アイテム
V
W
A
ユ
ー
ザ
ー
B
5
C
2
D
2
X
Y
Z
2
5
2
1
5
1
4
5
14/63
2.1 User Base & Item Base
アイテム
V
W
A
ユ
ー
ザ
ー
B
5
C
2
D
2
X
Y
Z
2
5
2
1
5
1
4
5
15/63
2.1 User Base & Item Base
アイテム
V
W
A
ユ
ー
ザ
ー
B(似)
5
C(違)
2
D(？)
2
X
Y
Z
2
5
2
1
5
1
4
5
16/63
2.1 User Base & Item Base
アイテム
V
W
A
ユ
ー
ザ
ー
B
5
C
2
D
2
X
Y
Z
2
5
2
1
5
1
4
5
2.1 User Base & Item Base
基本的な考え
あるアイテムについて
推薦対象のユーザーの予測評価値を
他の類似したユーザーたちによる評価の加重平均を用いて計算
一般に使われる類似度計算アルゴリズム
・ピアソンの相関係数
・ベクトル類似度
・etc
17/63
2.1 User Base & Item Base
問題点
データセットの密度が疎の場合
→精度が悪くなる
スケーラビリティの問題
→データが大きくなると計算が困難
コールドスタート問題
→過去のデータがない人には推薦不可能
18/63
2.1 User Base & Item Base
19/63
ユーザーベースのアプローチ [Paul Resnick他,1994,CSCW]
(1).推薦対象のユーザーと他のユーザー間の類似度を計算
(2).類似度とユーザーの評価でアイテムの予測評価値を計算
アイテムベースのアプローチ [Badrul Sarwar他,2001,WWW10]
(1).各アイテム間の類似度を計算
(2).推薦対象のユーザーが評価したアイテムとの類似度とその評価で
予測評価値を計算
参考資料 : 集合知プログラミング [Toby Segarn著,2008]他
20/63
2.1 User Base & Item Base
表記法の定義
I = {i1,i2,...,im}
アイテムの集合
U = {u1,u2,...,un}
ユーザーの集合
ua
推薦対象ユーザー
Ru(i)
ユーザーuのアイテムi
に対する評価
Ru
ユーザーuの平均評価
21/63
2.1 User Base & Item Base ～ユーザーベースの協調フィルタリング
予測対象アイテムについて
(1) ua と他のユーザーuとの類似度を計算
(2) 1.ua と各ユーザーuの類似度×uの評価値の総和を計算
2.総和を上で用いた類似度の絶対値の和で割る
22/63
2.1 User Base & Item Base ～ユーザーベースの協調フィルタリング
(1) ua と他のユーザーu との類似度を計算する。
今回はピアソンの相関係数を使用
∑
simu , u ' =
t ∈I u∧I u ' 

∑
t ∈ I u∧ I u ' 
 R u i− Ru ⋅ Ru ' i− Ru ' 
2
 Ru i −Ru 

∑
t ∈I u∧I u ' 
2
 Ru ' i −Ru ' 
23/63
2.1 User Base & Item Base ～ユーザーベースの協調フィルタリング
相関係数の値について
相関係数の値の範囲は-1～1
-1に近い：趣味嗜好が似ていない
1に近い：趣味嗜好が似ている
24/63
2.1 User Base & Item Base ～ユーザーベースの協調フィルタリング
相関係数を求めるには2人の共通したアイテムを用いる
a
ua
u
b
1
c
d
4
5
2
e
f
5
2
3
g
h
i
2
1
j
k
4
5
計算した値は信用できるのか？
→共通したアイテムが5未満の場合：相関係数を0
実験ではさらに相関係数が正の値のみを評価予測に使用する
2種類を使用
25/63
2.1 User Base & Item Base ～ユーザーベースの協調フィルタリング
(2) 1.ua と各ユーザーuの類似度×uの評価値の総和を計算
2.総和を上で用いた類似度の絶対値の和で割る
∑
Ru i=
a
u∈U i
sim u , u⋅Ru i
a
∑ ∣simu , u∣
u∈U i
a
26/63
2.1 User Base & Item Base ～アイテムベースの協調フィルタリング
予測対象アイテムについて
(1) 各アイテムi 間の類似度を計算する
(2) 1.ua の評価済みアイテムとの類似度
×ua の評価済みアイテムの評価値の総和を計算
2.総和を上で用いた類似度の絶対値の和で割る
27/63
2.1 User Base & Item Base ～アイテムベースの協調フィルタリング
(1) 各アイテムi 間の類似度を計算する
ユーザーベースの協調フィルタリングと同様に
ピアソンの相関係数を使用
∑
simi , i ' =
u∈U i∧U i ' 

∑
u∈U i∧U i ' 
 R u i− Ru ⋅ Ru i ' −Ru 
2
 Ru i −Ru 

∑
u∈U i ∧U i ' 
2
 Ru i ' − Ru 
28/63
2.1 User Base & Item Base ～アイテムベースの協調フィルタリング
(2) 1.ua の評価済みアイテムとの類似度
×ua の評価済みアイテムの評価値の総和を計算
2.総和を上で用いた類似度の絶対値の和で割る
∑
Ru i=
a
i ' ∈I u a 
sim i , i '⋅Ru i ' 
a
∑ ∣simi , i '∣
i ' ∈I u a 
29/63
2.1 User Base & Item Base ～アイテムベースの協調フィルタリング
キーとなる考え
推薦対象ユーザーが好むジャンルのアイテムは評価が高くなる
好まないジャンルのアイテムは評価が低くなる
表記法の追加
G = {g1,g2,...,go}
ジャンルの集合
G(i)
アイテムiが
属するジャンルの集合
GRu(i)
アイテムiが属するジャンルに
対するユーザーuの平均評価
30/63
2.1 User Base & Item Base ～評価予測にユーザーのジャンルの好みを追加する
like、dislikeの定義
GRu(i)の値が
ユーザーの平均評価
×1.25以上
ユーザーの平均評価
×0.75以下
それ以外
like
dislike
unknown
31/63
2.1 User Base & Item Base ～評価予測にユーザーのジャンルの好みを追加する
先ほどのlike、dislike、unknownを用いるために
予測値の計算の置き換え
∑
Ru i=
u∈U i 
sim u , u⋅R u i
a
∑ ∣simu , u∣
u∈U i 
a
a
∑
Ru i=
a
sim i , i '⋅R u i ' 
i ' ∈ I u a 
a
∑ ∣simi , i '∣
i ' ∈ I u a 
λ
λ
32/63
2.1 User Base & Item Base ～評価予測にユーザーのジャンルの好みを追加する
λについてlike、dislike、unknownによって値を変更
μ = 0.1(10%) or 0.05(5%)
目次
1. はじめに
1.1 動機
1.2 協調フィルタリングとは
2. 研究概要
2.1 User Base & Item Base（予測にジャンルの好みを用いる）
2.2 Slope one
2.3 ジャンル嗜好（オリジナル）
3. 実験方法
4. 結果・考察
5. 今後の課題
33/63
2.2 Slope One
34/63
Slope Oneアルゴリズム　[D Lemire他, 2005, SIAM]
個々のユーザーのアイテム評価値間差分を算出し、
全ユーザーについて算出された
アイテム評価値間差分の平均値を算出し、
この算出結果を元にレコメンド結果を出す。
ユーザ間の相関値を算出する必要がない。
35/63
2.2 Slope One
・簡単な例
アイテム
ユ
ー
ザ
ー
X
Y
太郎
2
3
花子
3
?
太郎のアイテム評価の差は　1　⇒花子さんは Y を　4　と評価　36/63
2.2 Slope One
アイテム
一太郎
ユ
ー
ザ
ー
二太郎
三太郎
花子
X
Y
2
3
一太郎の差は　1
二太郎の差は　3
2
5
三太郎は
両方評価していないので無視
3
1
?
⇒平均偏差　(1+3)/2 = 2
⇒花子さんは
Yを　5　と評価
37/63
2.2 Slope One
dev j , i=
∑
u ∈U j ,i
Ru , j −Ru ,i
∣U j ,i∣
i,j：アイテム(映画)　u：ユーザー
Ru,i：u による i の評価
Uj,i：jとi を評価しているユーザーの集合
|A|：Aの総数
38/63
2.2 Slope One
アイテム
ユ
ー
ザ
ー
X
Y
Z
一太郎
2
3
1
二太郎
2
5
4
花子
3
4
?
⇒devZ,X = 0.5
⇒devZ,Y = (-2-1)/2 = -1.5
⇒花子のCの評価は　(3+0.5)+(4-1.5)/2 = 3
39/63
2.2 Slope One
1
P Ru , j =
dev j ,iu i 
∑
∣Ru∣ i ∈R
u
i,j：アイテム(映画)　u：ユーザー
Ru,i,ui：u による i の評価
Ru：u が評価したアイテムの集合
|A|：Aの総数
2.2 Slope One　～Weighted Slope-One
• 平均偏差について
1人の評価を元に出した値と
1000人の評価を元に出した値では
重みが違う。
∑ dev j ,i ui ∣U i , j∣
w
P  R u , j =
i ∈Ru
∑ ∣U j ,i∣
i ∈Ru
40/63
2.2 Slope One　～Bi-polar Slope-One
41/63
• 好き嫌いに分けて予想する
• 判定基準
× （評価は1~5なので）３
・ ユーザーの評価の平均
dislike ＜ aveu ＜ like
∑
bp
P  Ru , j =
i ∈R
like
u
like
dev like
u

U
j ,i
i ∣ i , j∣
∑
dislike
dislike
dev dislike
u

U
j ,i
i ∣ i, j ∣
i∈Ru
∑ ∣U ilike, j∣ ∑ ∣U dislike
i, j ∣
like
i ∈Ru
dislike
i∈ Ru
2.2 Slope One　～提案
42/63
Weighted Slope Oneにおいて
最低の重みは0
（誰にも評価されていないアイテムがある場合
その予測値は0になる。）
→
最低の重みを1にする
（誰にも評価されていないアイテムを評価するときには
ユーザーの平均を用いることが出来る）
目次
43/63
1. はじめに
1.1 動機
1.2 協調フィルタリングとは
2. 研究概要
2.1 User Base & Item Base（予測にジャンルの好みを用いる）
2.2 Slope one
2.3 ジャンル嗜好（オリジナル）
3. 実験方法
4. 結果・考察
5. 今後の課題
44/63
2.3 ジャンル嗜好
ユーザーのジャンル嗜好を求めて、同じ嗜好を持つ
ユーザーの評価を参考に評価する
アクション映画最高！
アニメ大好き！
ですよね！
2.3 ジャンル嗜好
45/63
基本手順
１．それぞれのユーザーのジャンル平均を求める
２．ジャンル平均を求めた上で、そのジャンルを好むか
好まないか判断する
３．その映画を好むグループと好まないグループに分け
て、それぞれで平均をだす
４．未評価の映画に対して、その映画を好むか好まない
か判断し、評価する
46/63
2.3 ジャンル嗜好
藤巻
山崎
戸張
A
５
２
５
A
アクショ
ン
１
B
３
４
２
B
１
藤巻
山崎
戸張
アクショ
ン
４
３
３．５
ジャン
ル
３
４
２
好む
アニメ
０
１
好まない
A
５
２
B
４
２．５
2.3 ジャンル嗜好
47/63
基本手順との変更点
(1)基本手順での評価結果にジャンル平均との平均を
出す
(2)好む、好まないの他に普通という基準と設ける
48/63
2.3 ジャンル嗜好
(1)基本手順での評価結果にジャンル平均との平均を
出す
山崎
藤巻
戸張
アクション アニメ
Ａ
４．５
２
５
Ａ
１
０
Ｂ
４
４
２
Ｂ
１
１
山崎
藤巻
戸張
アクショ
ン
４
３
３．５
Ａ
５
２
アニメ
４
４
２
Ｂ
４
２
好む
好まない
49/63
2.3 ジャンル嗜好
(2)好む、好まないの他に普通という基準と設
ける
山崎
藤巻
戸張
上村
Ａ
５
２
３
５
Ａ
１
０
Ｂ
５
４
１
３
Ｂ
１
１
山崎
藤巻
戸張
上村
アクショ
ン
５
２
３
５
A
５
３
２
アニメ
５
４
１
３
B
４．５
３
１
アクション アニメ
好む
普通
好まない
目次
50/63
1. はじめに
1.1 動機
1.2 協調フィルタリングとは
2. 研究概要
2.1 User Base & Item Base（予測にジャンルの好みを用いる）
2.2 Slope one
2.3 ジャンル嗜好（オリジナル）
3. 実験方法
4. 結果・考察
5. 今後の課題
51/63
3. 実験方法
実験環境
CPU
Athlon64 3200+
メモリ
1024MB
OS
CentOS5.2
データセットについて
MovieLens(ミネソタ大学提供)
ユーザー数
943
映画数
1682
評価数
10万
各ユーザー毎に評価数20は保証されている。
3. 実験方法
分割学習法
各ユーザー毎にランダムに10評価抜いたデータを
予測対象データとし、
残りを予測のためのデータとする。
これを10組作成し実験を行い、精度を出し、
その平均を比較する。
52/63
53/63
3. 実験方法
精度
→ 今回は精度を比較するためにMAEを採用
MAE・・・Mean Absolute Error(平均絶対誤差)
N：予測対象データ数=9430
MAEの値が0に近ければ近いほど
誤差が少なく、精度が良い。
3. 実験方法　～実験に使用したプログラム
54/63
・ユーザーベース
+ジャンルの好みを用いる(0.1 or 0.05)
･アイテムベース
+ジャンルの好みを用いる(0.1 or 0.05)
上の6種類×
相関係数の全体を用いる(type A) or 正の値のみを用いる(type B)
･Slope One
･Weighted Slope One（重みを2通り）
･bi-polar Slope One
･ジャンル嗜好（オリジナル）
計19個(C++)
目次
55/63
1. はじめに
1.1 動機
1.2 協調フィルタリングとは
2. 研究概要
2.1 User Base & Item Base（予測にジャンルの好みを用いる）
2.2 Slope one
2.3 ジャンル嗜好（オリジナル）
3. 実験方法
4. 結果・考察
5. 今後の課題
56/63
4. 結果・考察　～既存アルゴリズム
ユーザーベース(type A)
精度
1.768743
(type B)
0.822609
アイテムベース(type A)
(type B)
1.276004
0.842814
・アイテムベースのほうが優秀
・正の値のみを用いると、精度が上がる
57/63
4. 結果・考察　～既存アルゴリズム
精度
ユーザーベース(type A)
1.768743
(type B)
0.822609
アイテムベース(type A)
1.276004
(type B)
0.842814
Slope One
0.763081
Weighted SO
0.762692
・重みをかけたほうが精度が高い
・bi-polarはより精度が高くなるとされているが、
今回はデータ量が少なかったせいか精度が落ちている
58/63
4. 結果・考察　～オリジナル
精度
ユーザーベース(type A) 0.1
1.770090
(type A) 0.05
1.769306
アイテムベース(type A) 0.1
1.276039
(type A) 0.05
1.275851
ユーザーベース(type B) 0.1
0.822413
(type B) 0.05
0.822261
アイテムベース(type B) 0.1
0.842043
(type B) 0.05
0.842190
既存のものと比較して
値がほとんど変化していない
→unknownの幅を取りすぎたのではないか？
59/63
4. 結果・考察　～オリジナル
精度
Weighted SO
0.762692
Weighted SO(改)
0.761764
・多少だが精度は上がった。
60/63
4. 結果・考察　～オリジナル
精度
ジャンル嗜好
0.861948
ジャンル嗜好２
ジャンル嗜好３
0.860496
1.200622
・基本手順と比較して、ジャンル平均を加えたものは僅かによくな
った。
・好む好まない普通の３タイプにわけたものは逆に悪くなった。
目次
61/63
1. はじめに
1.1 動機
1.2 協調フィルタリングとは
2. 研究概要
2.1 User Base & Item Base（予測にジャンルの好みを用いる）
2.2 Slope one
2.3 ジャンル嗜好（オリジナル）
3. 実験方法
4. 結果・考察
5. 今後の課題
62/63
5. 今後の課題
[1]
別の手法を取り入れる
-クラスタリング
-特異値分解(SVD)
[2]
データベースの利用・マシンスペックの改善
NetFlix
MovieLens
ユーザー
480,000
943
映画
評価
20,000 100,000,000
1,682
100,000
63/63
fin