サイト内広告戦略最適化 - 上智大学 情報理工学部 情報理工学科

サイト内広告戦略最適化
上智大学理工学部情報理工学科4年
チーム いの上2011
井上 綾香
2012/3/26
井上 綾香
1
目次
■データ概要
■提案手法
-商品推薦スコア算出法
-SimRankによる類似度算出
-商品に対する評価値算出
■実データを用いて検証
-計算時間の観点からの工夫
-決定すべきものを推定
-全員を対象に解析
-単純な手法との比較
■商品推薦スコア利用例
■ここまでのまとめ・感想・課題
2012/3/26
井上 綾香
2
データ概要
■ゴルフ・ポータルサイトにおける会員の
「ログ」「購買」「会員情報」データ
(2010年7月1日～2011年6月末までの1年分)
– ログデータ
UserID,セッションID,アクセス日…
– 会員データ
UserID,性別,生年, ハンディキャップ…
– 受注データ
UserID,受注日,商品ID…
2012/3/26
井上 綾香
3
GDOショップサイト
「私がGDOさんだったら，どうやって
利益の向上を目指すだろうか？」
会員登録
↓
「井上綾香」としてログイン
↓
ショップページ開く・・・
↓
顧客ごとの差別化なし
⇒私に合った商品が
オススメされていない
→もっと私が興味を引く商品の広告を出すべき！
→各々の会員に合ったオススメ商品を見つけたい！
2012/3/26
井上 綾香
4
今回の私のメインテーマは「広告戦略最適化」
そのために・・・
顧客一人一人に合った商品を
データから推測する！
（⇒結果をサイト内広告に活かしたい)
ではどのように？
2012/3/26
井上 綾香
5
提案手法
■顧客１人１人それぞれに合わせた
商品推薦スコア(商品のオススメ度)を算出する．
①顧客同士の類似度を求める．
(類似度としてSimRankを用いる．)
②算出した類似度を用いて，商品推薦スコアを
求める．
(計算法は商品推薦スコア算出法を用いる．)
2012/3/26
井上 綾香
6
商品推薦スコア算出法
■いわゆる協調フィルタリング
⇒顧客ごと商品ごとの嗜好と顧客間の類似度を基に，
ある特定の顧客と商品の相性を類推
オレンジ
あなたには
○○色が
オススメ
青がいい
ピンクよ
紫がいい
時代は緑
やっぱ赤
2012/3/26
井上 綾香
7
私
果物屋さんにて・・・
嗜好がとても似ている
安藤
A
嗜好が似ている
嗜好が似ていない
伊藤
上野
評価
評価
評価
バナナ
6.0
バナナ
2.0
バナナ
1.0
リンゴ
5.0
リンゴ
5.0
リンゴ
2.0
オレンジ
評価なし
オレンジ
2.0
オレンジ
3.0
評価の合計
バナナ
6.0 + 2.0 + 1.0
リンゴ
5.0 + 5.0 + 2.0
2.0 + 3.0
オレンジ
参考[1] Toby segaran(當山仁健・鴨澤眞夫訳):
『集合知プログラミング』.
オライリー，東京，2008.
2012/3/26
井上 綾香
8
私
果物屋さんにて・・・
嗜好がとても似ている
安藤
＝0.9
A
嗜好が似ている
＝0.5
伊藤
評価
嗜好が似ていない
＝0.1
上野
評価
評価
バナナ
6.0×0.9
バナナ
2.0×0.5
バナナ
1.0×0.1
リンゴ
5.0×0.9
リンゴ
5.0×0.5
リンゴ
2.0×0.1
オレンジ
評価なし
オレンジ
2.0×0.5
オレンジ
3.0×0.1
評価の合計
バナナ
(6.0×0.9 + 2.0×0.5 + 1.0×0.1)÷1.5
リンゴ
(5.0×0.9 + 5.0×0.5 + 2.0×0.1)÷1.5
参考[1] Toby segaran(當山仁健・鴨澤眞夫訳): 『集合知プログラミング』. オライリー，東京，2008.
オレンジ
2012/3/26
(
井上 綾香
2.0×0.5 + 3.0×0.1)÷0.6
9
私
果物屋さんにて・・・
嗜好がとても似ている
安藤
＝0.9
A
嗜好が似ている
＝0.5
伊藤
評価
嗜好が似ていない
＝0.1
上野
評価
評価
バナナ
2.0×0.5
バナナ
1.0×0.1
6.0×0.9
まず，顧客同士の類似度を求める．
リンゴ
5.0×0.5
リンゴ
2.0×0.1
リンゴ
5.0×0.9
⇒相関係数？ オレンジ 2.0×0.5
オレンジ 3.0×0.1
オレンジ 4.0×0.9
⇒ユークリッド距離？
評価の合計
…多品種少量購入では難しい!!
4.33
バナナ
⇒SimRankを利用
4.80
リンゴ
バナナ
参考[1] Toby segaran(當山仁健・鴨澤眞夫訳): 『集合知プログラミング』. オライリー，東京，2008.
3.27
オレンジ
2012/3/26
井上 綾香
1
10
10
0
SimRank
■SimRank：グラフ理論ベースのSimilarity measure
「直接隣接していないノード同士も，その他のノード
との関係性から類似していると見なせる」
という概念
安藤
タルト
伊藤
牛肉
上野
パフェ
2012/3/26
二部グラフを基に
類似度を算出
参考[2] Glen Jeh and Jennifer Widom:
SimRank: A Measure of Structual-Context
Similarity. ACM KDD2002, pp. 538-543.
井上 綾香
1
11
11
1
SimRank
タルト
安藤
類似度
( 安 , 伊 )
類似度
( 安 , 上 )
類似度
( 伊 , 上 )
牛肉
伊藤
上野
パフェ
左集合
2012/3/26
類似度
( タ , 牛 )
類似度
( タ , パ )
類似度
( 牛 , パ )
右集合
井上 綾香
1
12
12
2
SimRank
安藤
タルト
伊藤
牛肉
パフェ
上野
左集合
右集合
定義式
☆S ( A, B ) : AとBのSimRank
𝐶1
𝑆 𝑨, 𝑩 =
�
|𝑁(𝐴)||𝑁(𝐵)|
� 𝑆(𝑖, 𝑗)
𝑖∈𝑁(𝐴) 𝑗∈𝑁(𝐵)
𝐶1
𝑆 𝑨, 𝑩 =
�
|𝑁(𝐴)||𝑁(𝐵)|
� 𝑆(𝑖, 𝑗)
𝑖∈𝑁(𝐴) 𝑗∈𝑁(𝐵)
C1 , C2 : (0,1] : 減衰定数
N ( A) : Aの隣接頂点
■再帰的な定義式である
実践的な計算法：べき乗法⇒比較的少ない繰り返し計算
2012/3/26
井上 綾香
1
13
13
3
提案するSimRank：枝重み追加
既存の定義では…
安藤
2本
タルト
安藤
タルト
2本
伊藤
上野
牛肉
伊藤
パフェ
上野
牛肉
パフェ
⇒タルトも牛肉も全体に与える影響力は同じになってしまう……
2012/3/26
井上 綾香
1
14
14
4
提案するSimRank：枝重み追加
枝重みの値：「ノードの与える影響の強さ」
1
2 1
安藤
伊藤
上野
1
1
2
安藤
タルト
牛肉
≒
伊藤
上野
パフェ
タルト
牛肉
パフェ
⇒ノードが2個に増加したのと同じような感覚で全体に影響
⇒枝重みの導入により，ノードの影響力を考慮することが可能に
2012/3/26
井上 綾香
1
15
15
5
SimRank新定義：枝重み追加
安藤
2
2
1
伊藤
1
1
式を・・・
牛肉
左集合
𝑆 𝐴, 𝐵 =
𝑆 𝐴, 𝐵 =
𝑆 𝑨, 𝑩 =
右集合
𝐶1
∑𝑖∈𝑁(𝐴) ∑𝑗∈𝑁(𝐵) 𝑒𝑖𝑖 ∙ 𝑒𝑗𝑗
𝐶2
∑𝑖∈𝑁(𝐴) ∑𝑗∈𝑁(𝐵) 𝑒𝑖𝑖 ∙ 𝑒𝑗𝑗
枝重みが全て1 ＝ 従来のSimRank
2012/3/26
𝑆 𝑨, 𝑩 =
パフェ
1
上野
枝重みを追加
タルト
𝐶1
�
|𝑁(𝐴)||𝑁(𝐵)|
𝑖∈𝑁(𝐴) 𝑗∈𝑁(𝐵)
𝐶1
�
|𝑁(𝐴)||𝑁(𝐵)|
� 𝑆(𝑖, 𝑗)
𝑖∈𝑁(𝐴) 𝑗∈𝑁(𝐵)
↓
�
� 𝑆(𝑖, 𝑗) ∙ (𝑒𝑖𝑖 ∙ 𝑒𝑗𝑗 )
�
� 𝑆(𝑖, 𝑗) ∙ (𝑒𝑖𝑖 ∙ 𝑒𝑗𝑗 )
𝑖∈𝑁(𝐴) 𝑗∈𝑁(𝐵)
𝑖∈𝑁(𝐴) 𝑗∈𝑁(𝐵)
※𝑒𝑖𝑖 : 枝{i,A}の重み
井上 綾香
� 𝑆(𝑖, 𝑗)
に拡張！！
1
16
16
6
私
果物屋さんにて・・・
嗜好がとても似ている
安藤
＝0.9
A
嗜好が似ている
＝0.5
伊藤
済
評価
嗜好が似ていない
＝0.1
上野
評価
評価
バナナ
6.0×0.9
バナナ
2.0×0.5
バナナ
1.0×0.1
リンゴ
5.0×0.9
リンゴ
5.0×0.5
リンゴ
2.0×0.1
オレンジ
4.0×0.9
オレンジ
2.0×0.5
オレンジ
3.0×0.1
評価の合計
4.33
バナナ
各顧客の各商品に対する評価値を求める．
4.80
リンゴ
参考[1] Toby segaran(當山仁健・鴨澤眞夫訳): 『集合知プログラミング』. オライリー，東京，2008.
3.27
オレンジ
2012/3/26
井上 綾香
1
17
17
7
y:評価値
顧客の1商品に対する評価値算出
同じ物購入
⇑ こだわり?
y = x2
購入した
個数に比例
y=x
同じ物購入
⇑ 惰性…?
y = x1/2
x: 購入個数(個)
2012/3/26
井上 綾香
1
18
18
8
実データによる検証
※計算プログラムは全て自ら実装
使用言語：Python
マシン：iMac（CPU: 3.4GHz Intel Corei7,Mermory:16GByte,OS:MacOS 10.7.3）
つまりちょっといい程度のパソコン
2012/3/26
井上 綾香
1
19
19
9
決定すべきもの(1)(2):ノードと枝重み
？
(1)顧客
？
【例】
「購入履歴」
「性別」
…
(2)顧客の特徴
…
何回アクセス
した顧客？
？
特に！【顧客の特徴】ノードをいかに上手く決めるかで，
顧客同士の類似度が適切な値になるかどうかが決まる！！
2012/3/26
井上 綾香
2
20
20
0
決定すべきもの(3):減衰定数C1,C2
𝑆 𝐴, 𝐵 =
𝑆 𝐴, 𝐵 =
𝑪𝟏
∑𝑖∈𝑁(𝐴) ∑𝑗∈𝑁(𝐵) 𝑒𝑖𝑖 ∙ 𝑒𝑗𝑗
𝑪𝟐
∑𝑖∈𝑁(𝐴) ∑𝑗∈𝑁(𝐵) 𝑒𝑖𝑖 ∙ 𝑒𝑗𝑗
�
� 𝑆(𝑖, 𝑗) ∙ (𝑒𝑖𝑖 ∙ 𝑒𝑗𝑗 )
�
� 𝑆(𝑖, 𝑗) ∙ (𝑒𝑖𝑖 ∙ 𝑒𝑗𝑗 )
𝑖∈𝑁(𝐴) 𝑗∈𝑁(𝐵)
𝑖∈𝑁(𝐴) 𝑗∈𝑁(𝐵)
※𝑒𝑖𝑖 : 枝{i,A}の重み
C1,C2に0.8もしくは1.0を代入
(どちらのノード集合に重みをもたせる？)
2012/3/26
井上 綾香
2
21
21
1
y:評価値
決定すべきもの(4):評価値算出式
同じ物購入
⇑ こだわり?
y = x2
購入した
個数に比例
y=x
同じ物購入
⇑ 惰性…?
y = x1/2
3つの内どれにする……？？
2012/3/26
井上 綾香
x: 購入個数(個)
2
22
22
2
決定するものの採用基準
■SimRank計算のために決めなければいけないもの
(1)ノード(左集合)
(2)ノード(右集合)
(3)減衰定数
■商品評価算出のために決めなければいけないもの
(4)多項式（こだわり，惰性，それとも・・・）
⇛推薦スコアと実績の一致度の高い組合せを採用
(一致度：推薦スコアと購入個数の相関係数)
2012/3/26
井上 綾香
2
23
23
3
一致度の測定
①推薦スコア ⇦ 前半６ヶ月分のデータ
②商品購入実績 ⇦ 後半６ヶ月分のデータ
商品：(中分類×メーカ)の組合せ
⇒相関係数を調べる
2012/3/26
井上 綾香
2
24
24
4
計算の結果最も良かった組合せ
0時
割合×10
…
①顧客
ノード
23時
0
自身のハンデ：0.4
自身のハンデ±1：0.2
自身のハンデ±2：0.1
…
1回以上
サイトに
アクセス
した会員
55
購入数×2
クラブ×
フィラ
…
1
ウェア×
ナイキ
1
井上 綾香
中分類
×
メーカ
②会員特徴
ノード
年代
70以上
男
2012/3/26
ハンデ
10代
…
③減衰定数C1, C2
⇒0.8，1.0
④評価値算出式
⇒y = x
アクセス
時間帯
女
性別
2
25
25
5
計算時間に関わる工夫
■SimRankの計算時間 (理論： O(ノード数2) ，現実：5時間)
⇛ランダム抽出で代用？ 多
人数
少
⇛何人抽出するか？
多
計算時間
少
高
精度
⇛丁度よい人数で実験を行うべき
■GDOさんになったつもりで考える
①推薦値計算
⇛一瞬でできるので，都度計算
②SimRank計算
⇛一日に一回夜中にやる？
③決定すべきもの
⇛１年に１回程度？
⇛良い組合せ推定は上記の繰り返し
（もっと時間がかかる）
⇛ランダム抽出採用
2012/3/26
井上 綾香
低
ユーザに対するリコメンド計算
3日 4日
2日
1日
365日
2
26
26
6
全員分のデータで推薦スコア計算
推薦度30位の中に
購入商品が全て入っている！
とある会員の推薦スコアと販売実績
商品購入個数
【結果】
■計算時間 ⇒ 約4.8時間
■相関係数 ⇒ 0.2163
商品推薦スコア
2012/3/26
井上 綾香
2
27
27
7
商品推薦スコア利用例
商品ストックにも利用！！
一番おすすめ
の商品広告
三番目
二番目におすすめ
の商品広告
適した商品の広告記載が可能！！
2012/3/26
井上 綾香
2
28
28
8
メーカー別の検証，中分類別の検証
■計算時間
⇒約3.5時間
■相関係数
⇒0.2563
■計算時間
⇒約3.5時間
■相関係数
⇒0.4333
商品購入個数
中分類別
商品購入個数
メーカ別
グラフ入れる
商品推薦スコア
商品推薦スコア
2012/3/26
井上 綾香
2
29
29
9
メーカ＆中分類別スコア利用例
二番目に
広告費が
以下がショップサイト画面だとすると…
￥
高い
一番高い ￥
1位メーカ
2位メーカ
3位メーカ
4位メーカ
1位中分類
2位中分類
3位中分類
4位中分類
⇒スコア順に面積比で広告を掲載
2012/3/26
井上 綾香
3
30
30
0
単純な手法と提案手法の比較
単純な手法
提案手法
■会員同士の類似度計算
⇒会員間相関係数
(データ：各商品の購入数)
■商品の評価値
⇒商品購入個数
■会員同士の類似度計算
⇒SimRank
(データ：各商品の購入数)
■商品の評価値
⇒商品購入個数
前半半年で商品を購入した会員1028名に対して推薦
⇒商品推薦度と後半半年の購入商品の相関
計算時間：約35時間
計算時間：約1時間
スコアと実績の相関：
スコアと実績の相関：
0.0940
2012/3/26
井上 綾香
0.2275
3
31
31
1
単純な手法と提案手法の比較
単純な手法
提案手法
■会員同士の類似度計算
⇒相関係数
(データ：あらゆる要素)
■商品の評価値
⇒商品購入個数
■会員同士の類似度計算
⇒SimRank
(データ：あらゆる要素)
■商品の評価値
⇒商品購入個数
前半半年でサイトに1回以上アクセスした200名に対して推薦×5回
⇒商品推薦度と後半半年の購入商品の相関(5回分の平均値)
計算時間：約20分
計算時間：約1分
スコアと実績の相関：
スコアと実績の相関：
0.0101
0.2132
2012/3/26
井上 綾香
3
32
32
2
まとめ・感想・課題
【まとめ】
□SimRank を用いた類似度推測とそれを利用した商品推薦法を提案・実装・検証
⇒特に，推測に要する時間と推薦精度のトレードオフを考慮した推薦法を
提案・実装・検証
【解析結果を見た感想】
□より長期間のデータ⇒より良い結果？
・春夏秋冬で購入するものが異なる
・1年に数回セールがある
ご清聴ありがとう
ございました．
【今後の課題】
■SimRankを用いた類似度の計算においては枝重みとノードの取り方が重要
⇒自動的に(人間の恣意を入れず)枝重みを調整
⇒可能な限り多くのノードを用意し，自動的に集約
■解析時間のボトルネックとなっているSimRank計算の高速化
⇒アルゴリズム，プログラミング両面からの改良
2012/3/26
井上 綾香
3
33
33
3
付録
2012/3/26
井上 綾香
3
34
34
4
会員特徴ノード候補選出
■簡単な集計からわかること
・商品：特定の商品を何個も購入している会員がいる．
・ハンディキャップ：保持者は商品の購入率が高い．
・年代：様々な年代の会員がいる．
・性別：購入率やPV数などに差がある．
・住所：東京都在住の会員が多い．
・リファラ：検索サイトからアクセスした会員の
購入率は高い．
・アクセス曜日：日，月曜日に商品購入する会員が多い．
・アクセス時間：会員ごとにアクセス時間に特徴がある．
→これを参考に特徴ノードを選出
2012/3/26
井上 綾香
3
35
35
5
会員特徴ノード候補選出と枝重み調整
アイテムノード(枝重み)
詳細
①購入商品[メーカ×中分類](個数)
{(ナイキ,ウェア),
(ブリジストン，用品・小物),
(ヤマハ，クラブ),…}
{1,2,3,4,7,10,20,30,40,50,60,70,80,90,100,
200,300,400以上}
(人数が大体同じように平均をとった値)
②セッション総PV数(1)
③アクセス曜日(アクセス回数)
{日，月，火，水，木，金，土}
④アクセス時間帯(アクセス回数)
{0,1,2,…,22,23時}
⑤リファラ(アクセス回数)
{gdo,google,メール,リファラなし,…}
⑥住所(1)
{東京，埼玉，神奈川，…}
⑦年齢(1)
{10代,20代,30代,40代,50代,60代,70代以上}
⑧ハンデ(1)
{0,1,2,3,…,54,55}
⑨性別(1)
{男性,女性}
⇛全ての組合せで推薦スコアと購買実績の相関係数で検証
更に，枝重みに工夫を施して行って良好な組合せを採用
2012/3/26
井上 綾香
3
36
36
6
SimRankの計算時間(理論値)
計算すべきSimRankの値の個数
Ο( n 2 )個　+ Ο( m 2 )個
ベキ乗法の1反復にかかる時間
2
2
Ο ( n・
d 2 ) + Ο ( m・
d2 )
( d : 平均次数)
べき乗法のK回の反復にかかる時間
n個
2012/3/26
m個
Ο( Kn 2 d 2 + Km 2 d 2 )
井上 綾香
3
37
37
7
SimRank計算時間(実験値)
計算時間(秒)
使用言語：Python
マシン：iMac（CPU: 3.4GHz Intel Corei7,Mermory:16GByte,OS:MacOS 10.7.3）
つまりちょっといい程度のパソコン
顧客ノード数(人)
2012/3/26
井上 綾香
3
38
38
8
相関係数の平均と分散
※5回実験を行い，平均と分散をとった
顧客ノード数(人)
相関係数平均
相関係数分散
100
0.069
0.0071
200
0.142
0.0004
300
0.109
0.0009
400
0.130
0.0006
500
0.132
0.0008
⇒200人の顧客をランダムに選び，実験を行うことに決定
このような人数で5回ほど実験を繰り返し，商品推薦スコアと購入商品の相関
を見た．100人と200人の標準変化変量値は5％水準で有意でなく，相関係数の
値が有意に異なっているといえない．100人と500人でも同様．しかし，100人
と200人では相関係数の平均が大きく差があるということから，200人の顧客を
ランダムに選んで実験を行う，乱択アルゴリズムを採用することにした．
2012/3/26
井上 綾香
3
39
39
9
計算時間(SimRankべき乗法による反復回数)
縦軸対数グラフ
SimRank値誤差
選出顧客人数(人)
SimRank値誤差
折れ線グラフ
反復回数(回)
選出顧客人数(人)
反復回数(回)
⇒繰り返し計算は20回が妥当と判断
SimRank計算ではべき乗法を用いた．反復回数も実験により決定した．実験
結果からSimRankの値の反復ごとの差分（の最大値）が少数第三桁代になる
20回を繰り返し回数とした．
2012/3/26
井上 綾香
4
40
40
0