固态硬盘选择第38卷第1期__________________________计算机仿真_____________________________2021年1月文章编号：1006 - 9348(2021)01 -0431 -06
压缩降维矩阵分解算法的差分隐私推荐
杨竞1，向真2，王小骥1
(1.中国电子科技集团公司第三十研究所，四川成都610041;
2. 93114 部队，北京 100195)
摘要：为提供更好的用户体验，提出一种考虑压缩降维矩阵分解的差分隐私随机扰动推荐算法。首先，改进了局部差分隐私 保护（L D P)的下矩阵分解算法，单个用户将自己的数据随机化以满足不同的隐私，并将受干扰的数据发送到推荐器。然后，推荐者计算扰动数据的聚集，框架确保了用户的项目和评级对推荐者都是私有的。同时为解决L D P应用于矩阵因式分解 时存在的数据髙维特性，采用了随机投影降维技术，在没有数据先验知识情况下减少用户数据的维度。通过在Last,f m和 Flixstei•测试集上对推荐系统的推荐精度、推荐效率以及参数变化影响进行了实验分析，证明了上述算法在更强的隐私要求 下比现有的算法具有更好的矩阵分解性能，验证了算法的有效性。
关键词：压缩降维；矩阵分解；差分隐私；梯度下降；推荐
中图分类号:T P391.9 文献标识码：B
Differential Privacy Recommendation for Compresd
Reduced Dimension Matrix Decomposition Algorithms
YANG Jing1，XIANG Zhen2，WANG Xiao - ji1
(1. No.30 I n s t i t u t e o f C ET C,Chengdu S i c h u a n610041, China；
2.PLA93114, B e i j i n g 100195, China)
A B S T R A C T：To p r o v i d e a b e t t e r u s e r e x p e r i e n c e,t h i s p a p e r p r o p o s e s a d i f f e r e n t i a l p r i v a c y random p e r t u r b a t i o n r e c
ommendation a l g o r i t h m w i t h r e d u c e d- d i m e n s i o n m a t r i x d e c o m p o s i t i o n.F i r s t l y,t h e l o w e r m a t r i x d e c o m p o s i t i o n a l g or i t h m o f LDP was im pr ov ed.A s i n g l e u s e r r a n d o m i z e d h i s own d a t a t o s a t i s f y d i f f e r e n t p r i v a c y,and s e n t t h e i n t e r f e r e d
d a t a t o t h
e recommender.Then,t h e recommender c a l c u l a t e d t h e a g g r e g a t i o n o
f p e r t u r b a t i o n d a ta,wh ic h e n s u r e d t h a t
t h e u s e r’
s p r o j e c t and r a t i n g a r e p r i v a t e t o t h e recommender.Then,t h e recommender c a l c u l a t e d t h e a g g r e g a t i o n o f p e r t u r b a t i o n d a ta,wh ic h e n s u r e d t h a t t h e u s e r’s p r o j e c t an d r a t i n g w e r e p r i v a t e t o t h e recommender.A t t h e same t i me,i n o r d e r t o s o l v e t h e h i g h- d i m e n s i o n a l c h a r a c t e r i s t i c s o f d a t a when LDP was a p p l i e d t o m a t r i x f a c t o r i z a t i o n, random p r o j e c t i o n d i m e n s i o n r e d u c t i o n t e c h n o l o g y was a d o p t e d t o r e d u c e t h e d i m e n s i o n o f u s e r d a t a w i t h o u t p r i o r k n o w l e d g e o f d a t a.E x p e r i m e n t s o n L a s t,fm a n d F l i x s t e r t e s t s e t s show t h a t t h e p r o p o s e d a l g o r i t h m h a s b e t t e r m a t r i x
d e c o m p o s i t i o n p e r f o r m a n c e t h a n t h e e x i s t i n g a l g o r i t h m u n d e r s t r o n g e r p r i v a c y r e q u i r e m e n t s,and t h e e f f e c t i v e n e s s o f
t h e p r o p o s e d a l g o r i t h m i s v e r i f i e d.
K E Y W O R D S：
C o m p re ss io n d i m e n s i o n a l i t y r e d u c t i o n；M a t r i x d e c o m p o s i t i o n；
D i f f e r e n t i a l p r i v a c y；G r a d i e n t de s c e n t；
Recommendation
i引言
随着越来越多地用户使用移动设备，利用在线商店进行 商品购买的人数也越来越多。这种数据泛滥通常意味着消
基金项目：国家重点研发计划（20n Y F B0802000)
收稿日期:2019-04-丨8修回日期:2019-〇7-16费者面临许多选择，这使得决策更加困难。推荐系统可帮助 消费者找到感兴趣或者建议的项目U因此，推荐系统在
我们的日常生活中变得越来越普遍，从电影到商品的推荐。推荐系统可收集和挖掘用户数据以获得更好的用户体验[3]。然而，用户数据包括个人信息，常常会引起隐私问题。
差分隐私由于其强大的隐私保障能力，是解决隐私问题 的常用工具。已经有一些工作将差分隐私应用于推荐系统。
—431—
例如，文献[4]应用差分隐私来保护每个用户的项集，但其采 用随机化算法干扰了位于预定类别内的项，导致用户的类别 偏好可能被暴露=文献[5]还提出了局部模型，其中用户的 私人数据被扰动之前提交给推荐者。文献[6]提出一种RAPP o t算法来收集和分析用户数据而不侵犯隐私。RAPPor 建立在随机反应的概念之上，它是由Warner•开发的一种调 査技术，用于收集敏感话题的统计数据。文献[7]开发改进 的RAPPor实用L D P解决方案。其随机化机制使得能够分 析分类数据和数值数据，以及基于随机梯度下降的机器学习 任务。文献[8]提出一种用于差分私有矩阵分解的梯度扰动 算法，以防止不可信推荐者学习任何用户的评级或配置文件。此类文献还有很多，不再赘述。现有的方法均从不同的 角度提出了差分隐私的改进方案，取得了很好的效果，但是 也存在不足，主要体现在两个方面:①其被设计成保护用户 的评价或用户评价的项目，但不能同时保护两者。在许多情 况下，用户的项目集与她的评分一样存在敏感信息，因为推 断用户对哪些项目进行了评分可以泄露其政治观点等隐私 信息。②其关注于保护单个项目或用户的整个项目及其评 级中的评级值。然而，在推荐系统中，存在高度相关的项目 集（例如，同一类型的电影）。掩盖相关项中单个项的存在或 不存在不足以保护用户的敏感信息。此外，用户通常一次上 传一组收视率。从这个意义上说，单一评级或项目的保护在 实
践中并不适合。人们可能会试图扩展现有的方案，以便将 差别隐私应用于每个项目和评价。此外，这些算法中的大多 数假设可信推荐场景，然而，随着推荐服务越来越流行，许多 不信任推荐者出现在网上，可能超出服务滥用用户隐私，特 别是用户存在非对称化时，可能存在个人数据意外泄漏问题。
本文的目标是通过保证每个用户的强隐私性，建立一个 解决现有文献局限性的推荐系统。在协同过滤技术中使用 矩阵分解进行推荐。我们发展了新的用于矩阵分解的差分 隐私梯度下降算法。通过采用Nguyen等人建议的最新LDP 梯度扰动解决方案来保护用户的私有数据，包括项目、评级 和配置文件。验证了矩阵因式分解算法的最终项目配置文 件在用户或不在用户之间没有显著差异，从而保证每个用户 的隐私，并通过采用随机投影降维技术，减小了大量项目引 起的摄动误差，该解决方案将保护用户的项和评级放在一起，保证每个用户隐私，并保持推荐质量。
2问题描述
2.1算法框架
图1显示了我们的系统是如何工作的。在我们的系统 中，梯度下降算法需要在服务器和用户之间进行迭代反馈。从中观察到，当推荐者共享巧时，可以在用户的设备中计算 用户配置文件％，而无需向推荐者提交其数据。另一方面，在收集了所有用户的梯度之后计算项目配置文件因此由推荐者执行其计算。在每个迭代步骤中，推荐器必须向用户 —432—提供更新的然后每个用户在自己的设备中计算她
的配置文件u,，并向推荐器提交梯度的噪声版本。然后，推荐者通 过聚集噪声梯度来更新项目配置文件t^。用户和服务器之 间的这些反馈继续进行，直到达到固定次数的迭代。在每次 迭代中，隐私预算被分配给s/f c，在这里由推荐者给出。在A 次迭代之后，推荐者广播最终项目配置h然后由预测
在用户设备上未评级项目的评级，）=1,2,…,m。最后，根据 设备中的预测评级向用户提出建议。
图1所提差分陳私推荐系统概述
由于各个用户的梯度包括关于评级b和用户配置文件 u,.的信息，所以需要在每次迭代中保护用户的梯度。因此，所提随机扰动算法被设计为在每次迭代中满足
以保护由项、评级和用户简档组成的整个数据。在局部隐私 模型中，评价模型中的M不能先验地知道，除非用户公开他 们评级的项目的数量。因此，本文采用n代替M来改进所提 梯度下降算法。所有参数，即n、A…、A，和f c由推荐者给 出。隐私预算e也由推荐者给出。
2.2矩阵分解
假设n t用户对m项的子集（例如，电影）进行评级。利用x |l，".，m|表示已生成评级的用户/项 对,m是项目的数量。令Af=丨M l是总评级数。利用％表示 由用户i生成的项目 > 的评级。在实际设置中，提供的评级 是稀疏的，因此M比小得多，而n和m都大。对于给定 评级e对|，推荐系统可预测未被用户
全民国家安全教育日是哪一天评定的项目 的评级。矩阵分解用于计算用户配置文件h句矣n，以及项目的配置文件~ E,1〇名m,d是潜在因素数。可 通过最小化已知评级集上正则均方误差获得
/= TT y(r a - US)2 + I U i I P + A»Z
大型网络手游排行榜
I V i i=l j=l
(1)
对于<fCmin(m,n)和正常数A…,A…。未预测到的评价 值％，可由进行预测。解决非凸优化问题的两种常用方 法是（随机）梯度下降法和交替最小二乘法。后一种算法通 过在固定u，和固定^之间旋转迭代地解决最小二乘优化。梯度下降通过以下更新公式迭代地调整配置文件u，和巧r u； = u'r' -y, •\VU i<l>(U"' ,V'') +2A…u；'M⑵
^ = y j'1-y, • |V,，4)(f/'"1.V"1)+2\,vy'
党史的简单概括
\
式中,y, >〇是迭代《的学习率,f/是用户配置文件矩阵，其第 i行是七，V是项目轮廓矩阵，其第y行是v▽…>( t/,1〇和▽分别是+和^的梯度，可计算为
r V^C i/,^)=-^-y vj(r i/. -u[V j)
I I V1j:(HTeM(3)
[v <；)((/,F) X^(r-. - u[v j)
式中，▽…>( K H和v,/M R卩特征是用户配置文件u，应该 改变以减少均方误差。学习率y，是一个常数，通常被设置 为 〇(1/〇。
3基于服务器随机扰动的差分隐私矩阵分解
3.1项目保护和评价
早期的研究中就将拉普拉斯机制应用于梯度，以保护用 户的收视率。在他们的算法中，推荐者要求评分项目）的用 户以私有的方式提交他们的梯度。因此，聚合器可以了解用 户是否具有评级项目y。在本节中，我们提出了一个简单的 解决方案来克服现有工作中的问题。
如果用户i对项目;'进行评价，则令&为1，否则设定h 为〇。对于(o w w，令％.=〇。
S(〜-U‘r〜)2= Y免yv(〜(4)
(ij)e M j= 1
因此公式(3)中f M O梯度形式可改写为
n
V </>([/,K)= -2n~l- ujvj)(5)
i=\
如果用户i不对项目y进行评价，则令h为〇，因此其相 对于项目>的梯度是〇。一种保护“用户对哪些项目进行评 级”的方法是使用随机响应机制来干扰项目向量。具体来 说，根据々生成的以形式如下
,0,P r = p/2
y；= |l,Pr = p/2(6)
y^Pr = \ - p
式中,_/_ =1,2,“％^1。保护项为心=(心）1*,<1；=-2〜（〜-
u^)，通过个人用户在设备中施加干扰这样可得
g; = + Vm(7)式中，是独立随机变量，遵循具有标度〇■的拉普拉斯分 布。如果每个用户提交|(<，<,…，= 丨到服务器，则可以显示各个梯度的平均值，进而可得=，估计值形式为
,yl-p/2
)g'(8)服务器利用噪声梯度的平均值更新项目配置文件1, B H
…； = -y, • |V…；--i+ 2A.«；-1|(9)基于A= maxi<y〜和s q，如果在每次迭代中设定P=2/(l +e*|/4)和则可证明最终的V满足两个数据集和以的差分隐私。为了保护用户的整个项目和评级，必须在每次迭代中设置p=2/(l +eU l/i)/")和c r= ^|。在这种情况下，最终V满足两个数据集D和Z T
在一个用户的整个数据中不同的差分隐私，从而矩阵分解算 法保证用户隐私。
3.2用户隐私的服务器梯度扰动
为了减少V估计中的误差，采用随机化方法。特别地，该方法考虑这样的场景，其中每个用户都有一个要由服务器 收集的多维元组，并且要求用户在提交元组时随机选择一个 维度，并在所选维度上提交其元组值的扰动版本，同时忽略 所有其他维度。由服务器收集的扰动值可以用于估计每个 维度上的所有用户值的平均值，并且估计误差显著小于每个 用户在所有维度上提交其值的情况。算法1给出基于服务 器随机扰动的矩阵分解算法。
算法1：差分隐私梯度下降
输人：预定义迭代数与隐私参数e;
输出：项目配置矩阵P e r u;
1)初始化f/、V以及迭代计数器—=0;
2) while iter^k do
3)初始化Vf e|〇r x";
4) for i= 1t o n do
5)初始化 <e l〇r xd;
6)在|l，2,"*,m丨中对）进行采样；
7)在|1,2，中对/进行采样;
8 )计算 U;(%.- “f%.);
9) -1,1]，将映射到[-1,1]区间；
、/(*.),((e*/4-1) +(6*/4+ 1)\
10) r—((▲2(，t + i)--------)；
11) i/r= 1(、•）;' = e-^~：;
e—1
12) e l s e (x*)j t= - md€~e/k +|；
e—1
13) endif
14)计算;
15) endfor
16)计算 Vf = V f= ife r+ 1;
17)V=V-yt • |V；^2\vV\ ；
18) for i= 1t o n do
19) u,=u.-y(- |VU.+2Au u,|；
20) endfor
21) endwhlie
22) r eturn V
算法1的核心思想是每个用户从mx梯度矩阵中为随 机选择的元素发送扰动梯度。这种随机化技术每次迭代中 可将梯度的估计误差从〇(m)降低到〇(y^r)。
3.3通过降维实现精度提升
虽然算法1增强了隐私并减小为A的线性估计误差，
—433
—
但是误差可能仍然太大，因为在实践中，m是一个巨大的数 字，通常从1〇4到1〇6大小不等。为提高算法1的精度，考虑 采用降维策略。特别是，本文采用随机投影原因是：（i)随机 投影使我们能够在没有数据先验知识情况下减少用户数据 的维度；（i i)随机投影具有受限的等距性质，使得适当高维的随机选择的子空间中的点间距离近似保持。对于
令少是9x n的随机矩阵，其矩阵元素是是均值为〇，方差 为1/9的高斯分布或伯努利分布的独立随机变量。根据 J o h n s o n L i n d e n s t r a u s s可得
(1-5) ||r, - Ku,|p ^
|丨0(/■‘ -Va, ) |p 彡（1+ 5) -Vu, |p (1〇)
对于g = 0(S-2logn)，因为满足等式（伽）"（俲）= (||<P(a + 6)|P-||^a|F-||^|F)/2J I J
|(«Pa)r(<P6) -a Tb\^||a|p + ||6|F)(11)对于任意的a,f i e存在
全^(%-《= _2r>T^Vui
I
+ + 0(8)(12)式中，=出ag(l)，/\=(〜）,，K =(々）= [幻1，…,〜]7。令=(〜）及=抑，^=少A#= (，则上述问题变为6的求解问题，其中\W，目标是最小化
/ = X ||6jp + n~l ^Ufz,.- IzjBui +
rn i=i
(13)
对于给定的，可得更新公式
B'= B-' -y, •\V b^U"',B-1) +2\.B-'\(14)式中,▽>({；,B)= -2^(4-W u,)uf。每个用户发送▽；>=U - l T,&〇u〖到服务器，以实现B的更新计算。因为▽^ =^V‘v+0(S)，对所有用户使用相同的随机矩阵少，服务 器可以容易地基于▽纟使用压缩感知等稀疏恢复算法得到稀 疏矩阵▽‘,，其矩阵元素是-2y p a(〜-U\)。在这种情况下，融合算法可以学习用户的项目和评级。为了避免这样的 问题，提出与算法1类似的方式为从<7-^矩阵中随机选择的元素发送噪声梯度。然后，融合算法收集所有用户的降维梯度并更新B。这些用户和服务器之间的反馈一直持续到友次迭代。一旦融合算法使用用户提交的噪声梯度获得最终 融合算法与用户共享S，然后用户设备计算i，利用测量值z,，用户设备可以通过稀疏恢复算法预测未观测到的(i,y)的评级r…。假设每个用户偏好的项目是稀疏的，因此，可通过求解范数优化问题来预测评级
minimize\\X i||,⑴)
s u b ject t o z{-
在这种情况下，通过压缩感知算法给出估计评价值k，(i,;+)ffM。通过实验，观察到当9小于用户所评级的项目数—434—时，从足恢复评级会产生较大的误差。由于评级的稀疏程度 因用户而异，因此设置最佳<?并不容易。因此，采取交替地 从％ =少▽，恢复梯度V8E利用V B恢复的全梯度W
如下
V；= V；(16)式中，是0的伪逆计算结果。利用梯度
令,'项目配置矩阵P可被推荐者更新和共享。然而，在每次 迭代中共享m x d矩阵V会增加通信成本。因此，在所提系 统中，推荐者与用户共享9x d矩阵，并且每个用户使用 公式（19)利用其设备中的恢复在每个用户的设备中
更新项目配置矩阵V，并用最终的V进行推荐。
算法1：基于降维的差分隐私梯度下降
输人：正整数9，预定义迭代数*与隐私参数以
输出：项目配置矩阵
1)初始化f/、v以及迭代计数器如「= 0;
2) while iter^k do
3)初始化W e
4) for i= 1t o n do
5)初始化 <e l〇r x r f;
6) V；= |-2y^uu(r^- u[v y)|;
7) ^=^VV;
8)在11,2,…，m l中对进行采样；
9)在|1,2,…,⑷中对/进行采样;
10) f$ [ -1,1]，将 U);"映射到[-1,1]区间；
11)
12)
13)
T~ Bernoulli I
(认,（，-1) +(，+ i)、
信任的作文i f T= \then (x* );z= md
2(ee/k + 1)
•h i
e l s e (x* )jt= - md
7；
14) endif
15)计算 V f l_+<;
16) endfor
17)计算▽:= V j /n; “er = "e r + 1;
18) for i= l t o n do
19) uL-yt •|V u. + 2A.U,\；V= V- yt •I V； + 2\vV\ ;
20)endfor
21)endwhlie
22) r eturn V
4实验分析
4.1实验设置
本节实验选取的硬件配置为：英特尔i5 - 6400K 3.2〇}^，内存为801^，系统是《^8旗舰版。为验证本文算
]文献[丨4] ■文献丨15】■本文算法
隐私预算参数峭*.!1.]
图3
实验集（Flixster)上的N D C G 指标变化情况
根据图2〜图3实验结果可知，当实验参数隐私预算e 在区间[0.1，1.0]变化时，指标N D C G 的取值从大到小的趋
势进行变化，主要原因是算法中因为隐私预算e 取值越大， 其在算法实现过程中所需要的拉普拉斯噪音的取值越小，但 是本文算法因为采用了用户隐私的服务器梯度扰动，因此其 所得到的N D C G 指标取值大约是文献[14]算法的3倍，是文 献[15]的2倍。
2)参数m 变化影响实验。本部分实验环节中，设定隐 私预算为固定值，即e =〇.4，对于不同取值的差分隐私推荐 数量m ，选取Jaccard 度量指标对算法的有效性进行验证。 则对比算法在选取实验集上的N D C G 评估指标见图4〜5
所示。
]文献[M l ■文献丨丨51 ■本文算法
推荐项目数〃
图4
实验集（Last, f m )上的N D C G 指标变化情况
推荐项目数A f /Is.n.]
图5
实验集（Flixster)上的N D C G 指标变化情况
□文献[14] ■文献[15] ■本文算法
M i
)
0.2
0.4 0.6
春菜是什么菜0.8
1
隐私预算参数
法的有效性，这里选取文献[14]的L A P 和文献[15]的NOE
两种算法作为对比算法，其中L A P 算法采用的是拉普拉斯噪 声摄动算法。本文算去的实验对象是表1数据。
表1
选取的数据集
数据集
U E l E2Item Last, fm 1889127149219217634Flixster
137372
1269074
7527931
48754
表1中的有关参数，参数U 是实验对象中设定的用户数 量，参数E 1是实验对象中用户之间的关系数量，参数E 2是 实验对象中用户和项目之间的关系数量，参数Item 是实验对 象中的项目的数量。
为了验证三种对比算法的差分隐私推荐结果可用性，选 取的实验评价指标是N D C G 指标，定义形式如下
^ DCG(L(k) tu)
1
n 7、
DCG{L{k) ,u)
sd卡和tf卡的区别\U\
K J
NDCG(k ，u)
式中，参数项N D C G (k ，i i )是实验对象中用户u 对差分隐私 项目k 进行可用性推荐的评估指标，定义形式为
Y
RankiuJi )
l i ^f k ) m a x (1 y l 〇g2index ( Ii ) + 1)'
不齿是什么意思
DCG(L(k)，u)
-(18)
式中，参数项i n d e x ( 1)是差分隐私项目在L ( k )数据集中 的位置索引。同时，为了评估/数据集和两个 数据集的差分隐私推荐相似性，这里选取近邻关系指标
I 厂U ) n
厂⑷
Jaccard(ufv)Adamic/Adar{ uy v)
\r(u) u r(v)zeT (^f \r {v ) i 〇g |r (z ) I
(19)(20)
式中，参数项r (u )是同数据集中用户u 的关系近邻集。
4.2可用性度置评价
采用表1中所示的两种实验数据集，实验过程中通过设 定不同的项目推荐数k 以及隐私预算e ，来获得不同大小的 可用性推荐的评估指标N D C G (k ,U )，其中参数6= 10. 1,0. 4,0.7,1.01 ,k = |10,40,70,100|。参数实验如下：
1)隐私预算e 影响实验：本实验中设定数据集中差分隐 私的推荐数量是k =40，实验过程中选择改变隐私预算e ，分 别采用Jaccard 度量指标对算法的有效性进行验证。则对比 算法在选取实验集上的N D C G 评估指标见图2 ~3所示。
t .u
.s l /c u c z i i K I n 联怨粑聲
图2实验集（Last, f m )上的N D C G 指标变化情况
—435
—
