Document

プライバシ協調フィルタリング
における
利用者評価行列の次元削減
○木澤寛厚，菊池浩明(東海大)
背景
ネットショップ
商品が多すぎ
見つからな
いorz
情報推薦システム
amazon
他の利用者の嗜好に
基づき，利用者の嗜
好を予想
利用者の嗜好に合う
商品を提示する
http://www.amazon.co.jp/
従来方式と提案方式の違い
従来方式
サーバ
B’
MAC
S
漏洩
提案方式
MAC
暗号化
漏洩しない
A
A
B
C
MAC
？
Windows
A
B
C
B’
MAC
A
B
？
B
C
Windows
C
提案方式
精度 MAE
１．秘匿CF方式
コスト GB
PCF
◎
0.72
×
1024
CCF
○
0.75
○
28
SCF
△
0.99
○
36
LL
×
1.0
◎
---
２．アイテム
クラスタリング
３．ユーザ
サンプリング
４．最尤法
協調フィルタリング(CF方式)
A
B
C
D
iPhone
フィレオ
フィッシュ
カレー
5
5
1
5
＊
1
5
2
3
3
2
＊=Aの平均＋
類似度S 平均
0.97
0.35
1.0
3.5
3
3
3.5
Bとの類似度・Bの評価+Cとの類似度・Cの評価
類似度の総和
0.97(1-3)+0.35(5-3)
=3.5 +
=
0.97+0.35
2.6
提案方式：秘匿CF方式
準同型性暗号でCF方式を計算する
– 評価値の正規化
• コサイン尺度を和と積で実現するために
評価値を距離で割る
– 欠損値をマスクするフラグ
• 予測値のアイテムを評価していないユーザは
推薦に利用しない
– 評価値の積の予備計算
秘匿CF方式 -予備計算
Bとの類似度・Bの評価 = S(A,B)・(b2-b)
=(a1b1+a2b2+a3b3)(b2-b)
=(a1b1b2+a2b2b2+a3b3b2)-(a1b1b+a2b2b+a3b3b)
E  E (b1b2 )  E (b2b2 ) 
a1
B
E (b1b1 )
E (b1b2 ) E (b2b2 )
E (b1b3 ) E (b2b3 ) E (b3b3 )
暗号文
m(m+1)/2個
a2
被推薦者
A
1024GB
アプローチ
１３５
CCF方式
A
評価行列の次元削減
B
C
１２３４５
D
A
E
B
C
１２３４５
SCF方式
D
A
E
C
E
CCF方式
第3次的な情報から
アイテムをクラスタリング
そのクラスタ中でのみ
秘匿CF方式を適用
SCF方式
何人かサンプリングする
コミュニティに分割する
評価値を決め秘匿CF方
式を適用
アイテム集合I
クラス
クラス
１
２
iPhone
フィレオ
A
5
＊
B
5
1
C
1
5
D
5
ユーザ集合U
α
コミュニティ
β
コミュニティ
iPhone
フィレオ
カレー
α
4
4
2
β
3
2
3
A
5
＊
2
評価実験
公開データベース(Group Lens)を使用し
MAE・通信コスト・計算コストを調べる
– 100個の評価値を未評価とみなし推薦値を求めMAE
を調べる
– CCF方式はクラスタ数，SCF方式はコミュニティ数を
変動させMAE・通信コスト・計算コストを調べる
– 暗号文のサイズを256byteとして通信コストを導出する
– べき乗計算を1764(ms)として計算コストを導出する
ユーザ数 943人
アイテム数 1682個
総評価数
100,000個
CCF方式 MAE
クラスタ数1～19
0.86
500
0.82
computation cost[s]
MAE
communication
cost[GB]
0.84
0.8
0.78
0.76
0.74
0.72
0.7
0
2
4
6
8
10 12 14
number of clusters
16
18
0
20
CCF方式通信コスト・計算コスト
1200
2967秒
1024GB
3000
communication_cost
computation_cost
2500
800
2000
600
1500
400
1000
156秒
3GB
200
0
0
2
4
6
8
10 12 14
number of clusters
16
18
500
0
20
computation cost[s]
communication cost[GB]
1000
結論
プライバシを秘匿した秘匿CF方式を提案
通信コストを減少させるための3つの改良案
を提案
– CCF方式
– SCF方式
– (LL方式)
課題
各方式を実用可能なコストまで下げる
ご清聴ありがとうございました
関連技術 - 準同型性暗号
暗号化したまま計算できる
–E
–E
E (a) E (b)  E (a  b)
E (a)  E (ab)
b
割り算は行えない
関連技術 –
協調フィルタリング方式(CF法)
評価値
高10 9 8 7 6 5 4 3 2 1低
user1
user2
itemA itemB itemC itemD itemE
8
5
4
9
7
8
5
4
X
7
X=9？
itemF
5
5
協調フィルタリング(評価値計算)
ユーザ集合 U={u1,u2,…,um}
アイテム集合 I={i1,i2,…,in}
pi ,k

r 
i
jU k
s(ui , u j )( rj ,k  rj )

jU k
s(ui , u j )
・Uk = i ∈ U|ri,k = φ(未評価のアイテムの評価)
・s(ui,uj) = uiとujの類似度(コサイン尺度)
・ ri = uiの評価した評価値の平均
コサイン尺度(類似度)
・ユーザaとユーザbの類似度を求める
ユーザaの各アイテムに対する評価値A={a1,a2,…an}
ユーザbの各アイテムに対する評価値B={b1,b2,…bn}
s ( a, b) 
a1b1    anbn
a  a
2
1
2
n
b  b
2
1
これらを準同型性暗号で行う
2
n
秘匿CF方式 (分母) ２－２
A
ユーザB
暗号文
iPhone
フィレオ
カレー
Flag iPhone
5
1
3
iPhone
フィレオ
A
5
？
2
Flag フィレオ
5
1
3
B
5
1
3
Flag カレー
5
1
3
C
1
5
3
ユーザC
D
5
iPhone
フィレオ
カレー
Flag iPhone
1
5
3
Flag フィレオ
1
5
3
Flag カレー
1
5
3
iPhone
フィレオ
カレー
Flag iPhone
5
0
2
Flag フィレオ
0
0
0
Flag カレー
5
0
2
カレー
2
「フィレオ」の予測値を
得るためには
「Flag フィレオ」の値を使って
分母を計算する
ユーザD
秘匿CF方式(コサイン尺度)
iPhone
s( A, B) 
暗号化して
行う場合
フィレオ
カレー
A
a1
a
a2
a
a3
a
B
b1
b
b2
b
b3
b
a1 b1 a2 b2 a3 b3 a1b1  a2b2  a3b3
     
a b a b a b
ab
a1
a
a2
a
 b1   b2 
 b3 




E ( s ( A, B))  E   E   E  
b b
b
a3
a
 a1b1  a2b2  a3b3 

 E 

a
b


SCF方式 MAE
1
0.95
MAE
0.9
0.85
0.8
0.75
0.7
1 6 111621263136414651566166717681869196
nuber
numberofofcommunities
communities d d
SCF方式通信コスト
communication cost [GB]
1000
100
10
1
0
10
20 30 40 50 60 70 80
number of communities d
number of communities d
90 100
協調フィルタリング方式
iPhone
フィレオ
フィッシュ
カレー
A
1
？
2
B
5
1
3
C
1
5
3
D
5
D
C
サーバ
2
推薦依頼
B
？の値を計算
A
値を返す
協調フィルタリング方式(類似度)
iPhone
フィレオ
フィッシュ
カレー
A
5a1
a2
？
2a3
B
5b1
1b2
3b3
C
1c1
5c2
3c3
D
5d1
d2
2d3
s ( A, B) 
サーバ
a1b1  a2b2  a3b3
a12  a22  a32 b12  b22  b32
類似度計算 s(A,B)
(5*5+0*1+2*3)/{√(52+02+22)*√(52+12+32)}=0.97
協調フィルタリング(予測値計算)
iPhone
フィレオ
フィッシュ
カレー
A
5
？
2
B
5
1
3
C
1
5
3
D
5
pa, 2
サーバ
2
s( A, B)(b2  b)  s( A, C )(c2  c)
a
s( A, B)  s( A, C )
pa,2=3.5+{0.97(1-3)+0.35(5-3)}/(0.97+0.35)
これらの計算を
=2.6
準同型性暗号で計算する
提案方式：秘匿CF方式
暗号化
した
評価値
を
送信
iPhone
フィレオ
フィッシュ
カレー
A
5
？
2
B
5
1
3
C
1
5
3
D
5
D
2
C
B
暗号化したまま
？を計算し
復号する
A
推薦依頼
秘匿CF方式 – 手順
pa, 2
A
s( A, B)(b2  b)  s( A, C )(c2  c)
a
s( A, B)  s( A, C )
被推薦者は分子と分母をそれぞれ計算
(暗号化したまま)
分子と分母の値をそれぞれ復号
– 閾値復号する
(鍵はm人のユーザで分散しているとする)
分子と分母の値を割り平均を足す
秘匿CF方式(分母)
pa , 2
s( A, B)(b2  b)  s( A, C )(c2  c)
a
s( A, B)  s( A, C )
iPhone
フィレオ
カレー
A
5
？
2
B
5
1
3
C
1
5
3
D
5
0
2
コサイン尺度
s ( A, B) 
a1b1  a2b2  a3b3
a12  a22  a32 b12  b22  b32
ポイント
１．コサイン尺度には割り算があるのでそのままでは準
同型性暗号の適用は不可能．
２．予測値を得たいアイテムを評価していないユーザの
類似度は加算しない
秘匿CF方式 (分母) １－１
コサイン尺度を準同型性暗号で計算
できるように和と積だけにする
– 各ユーザが評価値をあらかじめノルムで
割っておく(単位ベクトルにする)
iPhone
フィレオ
カレー |u|
A
a1
a2
a3
a12  a22  a32  a
B
b1
b2
b3
b12  b22  b32  b
iPhone
評価値とする
フィレオ
カレー
A
a1
a
a2
a
a3
a
B
b1
b
b2
b
b3
b
B
秘匿CF方式 (分母) １－２
iPhone
s( A, B) 
暗号化して
行う場合
フィレオ
A
カレー
A
a1
a
a2
a
a3
a
B
b1
b
b2
b
b3
b
a1 b1 a2 b2 a3 b3 a1b1  a2b2  a3b3
     
a b a b a b
ab
a1
a
a2
a
 b1   b2 
 b3 




E ( s ( A, B))  E   E   E  
b b
b
a3
a
 a1b1  a2b2  a3b3 

 E 

a
b


B
秘匿CF方式 (分母) ２－１
D
C
0か1のフラグを用意して未評価を判断
iPhone
D
5
フィレオカレー
2
※実際はノルムを割る
フィレオ
0
カレー
2
Flag フィレオ 0
0
0
Flag カレー
0
2
iPhone
Flag iPhone
5
5
一つ一つ暗号化して，全て被推薦者Aに送信する
秘匿CF方式 (分母) ２－２
A
ユーザB
暗号文
iPhone
フィレオ
カレー
Flag iPhone
5
1
3
iPhone
フィレオ
A
5
？
2
Flag フィレオ
5
1
3
B
5
1
3
Flag カレー
5
1
3
C
1
5
3
ユーザC
D
5
iPhone
フィレオ
カレー
Flag iPhone
1
5
3
Flag フィレオ
1
5
3
Flag カレー
1
5
3
iPhone
フィレオ
カレー
Flag iPhone
5
0
2
Flag フィレオ
0
0
0
Flag カレー
5
0
2
カレー
2
「フィレオ」の予測値を
得るためには
「Flag フィレオ」の値を使って
分母を計算する
ユーザD
秘匿CF方式 (分母) ２－３
A
ユーザB
iPhone
フィレオ
カレー
A
5
？
2
B
5
1
3
C
1
5
3
D
5
Flag フィレオ
iPhone
フィレオ
カレー
5
1
3
iPhone
フィレオ
カレー
1
5
3
iPhone
フィレオ
カレー
0
0
0
ユーザC
Flag フィレオ
2
ユーザD
Flag フィレオ
分母=S(A,B)+S(A,C)+S(A,D)=0.97+0.35+0=1.32
フィレオを評価していないユーザDの類似度が0
になるため足されたことにならない

Download Report