一种基于差分隐私保护的协同过滤推荐方法

何 明 常盟盟 吴小飞

(北京工业大学计算机学院 北京 100124)



一种基于差分隐私保护的协同过滤推荐方法

何 明 常盟盟 吴小飞

(北京工业大学计算机学院 北京 100124)

(heming@bjut.edu.cn)

由于推荐系统需要利用大量用户数据进行协同过滤，会给用户的个人隐私带来相当大的风险，如何保护隐私数据成为推荐系统当前面临的重大挑战.差分隐私作为一种新出现的隐私保护框架，能够防止攻击者拥有任意背景知识下的攻击并提供有力的保护.针对推荐系统中的隐私保护问题，提出一种满足差分隐私保护的协同过滤推荐算法.首先，构建用户和项目的潜在特征矩阵，有效降低数据稀疏性；然后，采用目标扰动方法对矩阵中添加满足差分隐私约束的噪声得到噪矩阵分解模型；通过随机梯度下降算法最小化相关联的正则化平方误差函数来获取模型中的参数；最后，应用差分隐私矩阵分解模型进行评分预测，并在MovieLens和Netflix数据集上对算法的有效性进行评价.实验结果证明:所提出方法的有效性能够在有限的精度损失范围内进行推荐并保护用户隐私.

差分隐私；隐私保护；协同过滤；推荐系统；矩阵分解

随着信息技术特别是互联网、物联网和云计算等技术的迅猛发展，网络空间中所蕴含的信息量呈指数级增长.人们在获取丰富多彩的信息内容的同时，沉浸于信息海洋而难以及时、准确地获得满足其自身需要的信息，“信息过载”现象愈发严重，给人们带来很大的信息负担.尽管传统搜索引擎如(Google、百度等)可以在一定程度上解决用户的信息检索需求，但仍然不能满足不同背景、不同目的、不同时期的个性化信息需求，从而不能真正有效地解决“信息过载”问题.推荐系统(recommender systems)[1-2]作为一种有效的信息过滤手段是当前解决信息过载问题及实现个性化信息服务有效方法之一.通过挖掘用户与项目之间(user-item)的二元关系，帮助用户从海量数据中便捷发现其可能感兴趣的项目(如Web信息、服务、在线商品等)，并生成个性化推荐以满足个性化需求.目前，推荐系统在电子商务(如Amazon、eBay、Netflix、阿里巴巴、豆瓣网、当当网等)、信息检索(如iGoogle、MyYhoo、GroupLens、百度等)以及移动应用、电子旅游、互联网广告等众多应用领域取得较大进展[3].在众多的推荐方法中，协同过滤是目前应用最多的算法，其核心思想是利用近似用户或者用户喜欢的项目的近似来过滤大量信息，从而为用户筛选出其可能感兴趣的项目.已被广泛应用于推荐系统中并取得了显著的效果，同时受到了大量研究者的高度关注.协同过滤推荐算法大致可以分为2类：基于近邻的协同过滤(neighborhood-based)[4-5]和基于模型的协同过滤(model-based)[6-7].

目前，推荐系统面临着严峻的隐私保护与安全问题.推荐系统需要收集大量的用户信息、用户行为等，数据越丰富，推荐精确度可能越高.然而，这些信息可能泄露用户的个人隐私，用户出于隐私与信息安全考虑，可能不愿意让这些数据被推荐系统记录和存储.由于推荐系统需要利用大量用户数据进行协同过滤(collaborative filtering)，所以数据的隐私保护已经成为推荐系统研究领域一个迫切需要解决的问题，也越来越受到人们的关注和重视.2010年，Netflix Prize比赛因为用户要求的隐私问题而不能继续举办.隐私保护推荐系统研究的问题是如何在保证数据集隐私安全的前提下获取推荐质量最优的模型.其研究通常面向推荐系统领域的具体推荐算法，通过对已有算法的调整和对推荐结果的效用评价来寻求数据安全性和推荐精确度的平衡.

差分隐私(differential privacy，DP)是Dwork[8]在2006年提出的一种新的隐私保护模型，该模型能够解决传统隐私保护模型的2个缺陷：1)无需考虑攻击者所拥有的任何可能的背景知识；2)对隐私保护水平给出了严格的定义和量化评估方法.

差分隐私在推荐系统中已得到普遍应用和广泛关注.McSherry等人[9]将差分隐私保护方法引入到协同过滤推荐系统，在分析项目之间的关系时，他们先建立项目相似度协方差矩阵，并向矩阵中加入噪声实施干扰，然后再提交给推荐系统实施推荐；Machanavajjhala等人[10]在基于社交网络数据的推荐系统中使用了差分隐私保护方法；Zhu等人[11]针对K最近邻算法所面临的隐私泄露问题提出了一种基于差分隐私保护的邻居协同过滤算法；另外，针对基于标签的推荐系统，Zhu等人[12]提出了一种对用户轮廓(user profile)进行修改并发布的差分隐私保护算法，能够在一定的精度损失范围内进行标签推荐并保护用户隐私.

虽然人们已经提出了一些差分隐私保护下的推荐算法，但已有的方法并没有考虑到隐语义模型,存在2方面的局限：1)在面对高维数据稀疏性问题时，导致可扩展性差；2)现有推荐算法隐私保护水平的提高是以牺牲推荐精确度为代价，导致算法推荐质量下降.

针对上述问题，本文将探讨隐私保护与协同过滤相结合的推荐方法.使得推荐算法能够达到推荐精确度与隐私保护的平衡.

本文主要贡献有3点：

1) 针对高维数据稀疏性问题，采用矩阵分解方法将用户-项目评分矩阵分解成低维潜在特征矩阵的乘积，有效处理高维稀疏数据以提高推荐精确度.

2) 基于隐语义模型，提出了一种满足ε-差分隐私的矩阵分解机制，通过随机扰动目标函数实现差分隐私，并采用随机梯度下降算进行优化求解.

3) 不仅对模型进行了理论分析和推导，并在MovieLens和Netflix两种不同规模的数据集上与已有的方法进行实验比较和分析，展示出该方法在兼顾隐私保护的同时，还具备了较高的推荐精确度.

1 相关工作

差分隐私和数据挖掘研究等领域的结合，使得差分隐私得到了广泛应用与发展.继Dwork提出了差分隐私保护模型之后，Friedman等人[13]提出了一种兼顾算法精确性和隐私性的差分隐私保护决策树建算法DiffP-C4.5；Chaudhuri等人[14]将差分隐私应用到了SVM和Logistic SVM[15]回归上，实现了经验风险最小化的差分隐私保护；针对特定数据类型，Cormode等人[16]通过简化步骤、降低敏感度的方式解决了数据的稀疏性问题，在差分隐私保护过程中，降低了噪声数据的添加量；Sarathy等人[17]指出将差分隐私保护方法应用于数值类型数据之上，存在一定的局限性；Li等人[18]首次将差分隐私与k-Anonymity算法相结合，解决了在微数据隐私保护下的数据发布问题.

在应用领域，Zhou等人[19]提出了一种应用于超大型数据库的差分隐私压缩算法，通过使用高斯随机变量矩阵以随机线性或映射变换的方式压缩数据库，在实现差分隐私保护的同时保持了原有数据的统计学习应用特性；Vu等人[20]将差分隐私保护与传统的统计假设检验建模相结合，从而获得统计效率和隐私保护级别之间的平衡；Gehrke等人[21]将改进了的差分隐私保护算法应用于社交网络的隐私保护建模；Hua等人[22]提出了数据发布在不同交互式环境下的差分隐私保护算法，并对这些方法进行分析和比较.

在基于差分隐私保护的数据挖掘研究中，比较典型的有SuLQ和PINQ接口框架，SuLQ框架将单属性布尔查询定义为查询原语，设计提供了隐私保护的k-means，ID3分类器等复杂算法.PINQ框架基于LINQ实现了敏感数据的差分隐私保护，并提供了一系列便于二次开发的应用接口[23].

此外，Xiao等人[24]将Haar小波变化与差分隐私保护相结合，在添加噪声前先对数据实施小波变换，提高了区间查询的准确度；Hay等人[25]将噪声以分组为单位进行添加，在满足精度的同时，最大限度地降低了噪声添加量；Chen等人[26]提出了差分隐私的数据发布机制.

作为一种严格的和可证明的隐私定义，差分隐私近年来受到了极大关注并被广泛研究.当然，差分隐私保护还是一个相对年轻的研究领域，在理论和应用上都还存在一些难点以及新的方向需要进一步深入研究[23].

2 理论基础

2.1 隐语义分解模型

基于近邻的协同过滤算法是在预测中直接使用已有数据预测，主要包括基于物品[4]和基于用户2类[27].基于模型的协同过滤算法主要通过用户对产品的评分信息训练出相应的模型，利用此模型预测未知的数据.基于模型的算法其中一大类就是采用矩阵分解方法的隐语义模型构建的，通过降维计算用户矩阵和项目矩阵的内积来预测评分，相比于近邻的算法,这种算法的准确性和稳定性都有所提升[28]，故本文采用隐语义模型来进行协同过滤.

隐语义模型(latent factor model)[29]就是联系用户兴趣与物品挖掘之间的隐含关系来构建模型的方法.典型的隐语义模型从奇异值分解(singular value decomposition，SVD)的角度将评分矩阵R分解为用户U和项目V的2个低维语义矩阵相乘的形式,通过直接最小化训练集中的均方根误差(root mean square error，RMSE)来学习矩阵,最终预测得到用户对项目的评分：

(1)

(2)

2.2 差分隐私

差分隐私是基于数据失真的隐私保护技术.通过向查询或者分析结果中添加噪声使数据失真，确保在某一数据集中插入或者删除某一条记录的操作不会影响任何查询的输出结果，从而达到隐私保护的目的.差分隐私的形式化定义如下：

定义1.ε-差分隐私[8].给定2个数据集D和D′，D和D′至多相差1条记录.给定1个隐私算法A，Range(A)为A的取值范围，若算法A在数据集D和D′上的任意输出结果O(O∈Range(A))满足下列不等式，则A满足ε-差分隐私：

Pr[K(D)∈S]≤e(ε)×Pr[K(D′)∈S]，

(3)

其中，概率Pr[·]由算法A的随机性所控制，表示隐私被披露的风险；隐私预算参数ε表示隐私保护程度，ε值越小表示隐私保护程度越高，但可用性相对越低.

噪声机制是实现差分隐私的主要技术.Laplace机制[30](Laplace mechanism)和指数机制[31](exp-onential mechanism)是2种最基础的差分隐私保护实现机制.其中Laplace机制适用于对数值型结果的保护，指数机制则适用于非数值型结果.基于不同噪声机制且满足差分隐私的算法所需噪声大小均依赖于函数的全局敏感度.

定义2. 全局敏感度[30].对于任意一个函数f:D→d，函数f的全局敏感度定义为

(4)

其中，D和D′之间至多相差1条记录，d表示函数f的查询维度，表示所映射的实数空间.

定理1. Laplace机制[30].对于任意一个函数f:D→d，若算法A的输出结果满足等式：

A(D)=f(D)+〈lap1(Δfε),

lap2(Δfε),…,lapd(Δfε)〉，

(5)

则A满足ε-差分隐私，其中lapi(Δfε)(1≤i≤d)是相互独立的Laplace变量，其对应的概率密度函数为p(x|b)=(12b)e(-|x|b).噪声大小与Δf成正比，与ε成反比.即全局敏感度越大，所添加噪声越大.

定理2. 指数机制[31].设随机算法A输入为数据集D，输出为一实体对象r∈Range，q(D,r)为敏感度.若算法A以正比于e(εq(D,r)2Δq)的概率从Range中选择并输出r，那么算法A满足ε-差分隐私保护.

3 差分隐私矩阵分解机制

本文面向集中式推荐场景,如图1所示，假定推荐系统是可信的，即推荐系统已经收集了用户的评分且不会泄露用户的隐私信息.矩阵U是保密的，但攻击者可以通过学习矩阵V中数据来推测用户的隐私信息，因此必须对矩阵V的发布进行干扰.为了使矩阵V的发布满足差分隐私保护的要求，向矩阵V中加入噪声实施随机干扰，并以评分预测误差最小化为目标函数，最终确保矩阵V的发布满足ε-差分隐私.

Fig. 1 Centralized recommendation scenario图1 集中式推荐场景

3.1 差分隐私矩阵分解

值得注意的是，推荐系统中的用户-项目评分矩阵不仅是高维数据集，而且存在数据的稀疏性问题.在高维情形下出现的数据样本稀疏导致距离计算困难等维数灾难.通常情况下，用户-项目评分矩阵的稀疏度可能达到99%[32].我们能够利用的表示用户兴趣的信息实际上是非常稀疏甚至是有限的，这使得很难为较少项目评分的用户找到兴趣相似的用户.

数据的稀疏性问题导致了推荐系统在相似度计算、评分预测等方面会直接或间接影响推荐精度.甚至对传统的协同过滤算法起到了很大的负面影响.例如，由于矩阵维度过大，数据稀疏性可能会导致2个用户之间的相似度为0，甚至由于评分数据太少导致了负相关性.早期的研究依赖于填充的方法，即填充用户-项目评分矩阵的缺失值使该矩阵变得稠密.例如，利用用户或项目的平均评分.然而，这种方法存在一定的局限性：由于填充方法极大地增大了数据量，所以代价非常大；除此之外，不准确性的填充也会使得数据变得倾斜.

缓解维数灾难的一个重要途径是降维.在很多情况下，用户-项目评分数据集中的一部分携带了数据集中的大部分信息，其他信息则要么是噪声，要么就是毫不相关的信息.从数值代数角度来看，矩阵分解可以将规模较大的复杂问题转化为小规模的简单子问题来求解；从应用统计学领域来看，通过矩阵分解得到原数据矩阵的低秩逼近，从而可以发现数据的内在结构特征，而其余特征则都是噪声或冗余特征，这些噪声数据会直接或间接影响到推荐精度.矩阵的低秩逼近可以有效降低数据的维数和去噪，缓解数据稀疏性问题，节省存储和计算资源.相对于传统的直接计算用户或者物品相似度的方法，在提高推荐准确性的同时，减小了推荐计算量.

矩阵分解(matrix factorization，MF)技术根据观察到的用户-项目评分直接建模，通过把用户-项目评分矩阵分解成2个或者多个低维矩阵的乘积实现维数的规约，将高维稀疏的用户-项目评分矩阵分解成2个低维的用户潜在特征矩阵U和项目潜在特征矩阵V，通过重构低维潜在特征矩阵预测用户对项目的评分.矩阵分解模型提供了一个内存有效的压缩模型，该模型训练起来相对容易，加上基于梯度的下降算法的矩阵分解模型实现起来相对容易，使得该模型具有较高的预测准确性和稳定性.

设Rn×m为n个用户和m个项目的用户-项目评分矩阵，矩阵分解方法可以把Rn×m分解成2个实数矩阵Un×k和Vn×k，使得：

R≈UVT，

(6)

Fig. 2 Matrix factorization basis图2 矩阵分解基本原理

用户-项目评分矩阵中的真实评分与用户矩阵U和项目矩阵V的关系：

(7)

(8)

并且采用随机梯度下降算法最小化它们之间的误差dui，即:

(9)

得到局部最小值.此时，使得R与UV之间的预测误差极小，数据的预测值与降维前评分矩阵中的实际值基本保持一致，即具有较高的评分预测精度.这样我们将评分矩阵从一个高维空间压缩到低维空间，并且空间的压缩使得数据的可用性损失最小.

一般的矩阵分解方法采用2个向量U和V内积的形式来表示用户对该物品的评分，存在一定的局限性，评分矩阵的稀疏度太大或者迭代次数过多，拟合噪声数据，分解很容易产生过度拟合.本文采用带偏置的矩阵分解方法，将独立于用户或产品的因素作为偏置部分.偏置部分有助于提高评分预测准确度.本文通过将偏置部分与数据噪声相结合来实现差分隐私保护.结合偏置部分，则第i个用户对第j个物品的评分预测可表示为

(10)

其中,〈ui,vj〉表示用户i和项目j的潜在特征向量的内积，b0表示所有项目评分的全局平均数，用户偏置bi表示该用户的打分习惯，物品偏置bj表示物品得到的打分情况.为了得到更加准确的预测值，需要对预测值和实际值之间的损失度进行优化评估，并通过正则化学习参数来避免过拟合现象，本文建立的目标优化函数：

(11)

其中，常量λ控制了正则化程度，以预防过拟合观测数据.

对目标函数进行极小化的优化求解通常有2种方法：交替最小二乘法(alternative least square，ALS)和随机梯度下降法(stochastic gradient descent，SGD).交替最小二乘法是通过平方损失函数建立模型优化目标函数的一种思路，此时求解最优模型过程便具体化为最优化目标函数的过程；随机梯度下降法作为最优化目标函数的一种优化算法，求解的是使得目标函数能达到最优或者近似最优的参数集.本文采用随机梯度下降算法来进行优化，基本思想是使得变量沿着目标函数负梯度的方向移动，直至移动到极小值点.矩阵分解的目标函数是凸函数，因此，通过梯度下降算法我们能够得到目标函数的极小值.在梯度下降算法的隐含矩阵更新公式中，通过不断迭代来更新矩阵U和V中的元素：

ui←ui+α(eui·vj-λui)，

(12)

(vj←vj+α(eui·ui-λvj)，

(13)

bu←bu+α(eui-λbu)，

(14)

bi←bi+α(eui-λbi)，

(15)

其中，eui为预测评分与实际评分之间的误差值；ui为矩阵U中的向量；vj为矩阵V中的向量；λ为正则化参数；α表示学习速率，它是一个超参数，表示训练样本误差的学习程度，需要调参确定.迭代终止主要包括3个条件：

1) 设定阈值，当目标函数值小于阈值停止迭代.

2) 当前后2次函数值变化绝对值小于某一阈值时，停止迭代.

3) 固定迭代次数.

本文采用条件2作为迭代终止条件.

3.2 差分隐私预算的选取

差分隐私预算参数ε衡量了DPMF算法的隐私保护水平，参数ε越小提供的隐私保护能力越大，这是因为ε与噪声的添加幅度成反比.噪声矩阵和差分隐私预算参数ε的关系:

(16)

因此，当ε的取值较小时，DPMF算法输出的发布矩阵Vp中添加的噪声越大，相反，当ε的取值较大时，矩阵V和发布矩阵Vp相差越小，隐私保护力度越差.为了选取合适的参数ε，Lee和Clifton[33]提出了一种攻击模型，给出选取参数ε上界的计算为

(17)

可以看出，参数ε的选取依赖于4个参数：ρ,Δq,Δv,n.其中ρ为攻击者成功概率，Δq为查询函数的敏感度，Δv为潜在输入集的函数敏感度[33]，n是潜在特征向量的维度.在一般实验中，对于ε的取值主要通过列举不同的预算值，然后对比这些不同取值算法的查询平均差错率来评估ε的最佳取值.文献[34]提出了ε的取值与攻击者成功的概率二者之间的关系.当攻击者的成功概率ρ满足：

(18)

可以得到参数ε的取值满足：

(19)

其中，Δq为查询函数的敏感度，L为查询的容错区间长度，ρ攻击者成功的概率.可见参数ε的上界与数据集大小无关，仅仅与查询函数(Δq，L)和攻击者的成功概率有关[34].

3.3 隐私性分析

∀j∈{1,2,…,m}，迭代地进行目标函数的极小化，直到收敛.由于负梯度方向是使目标函数下降最快的方向，在迭代的每一步对vj求偏导数并令其为0，可得：

(20)

因此:

(21)

证毕.

3.4 差分隐私保护

添加噪声是实现差分隐私保护的主要技术，常用的噪声机制包括拉普拉斯机制[30]和指数机制[31].本文采用目标函数扰动方法实现差分隐私保护，其基本思想是将噪声加在目标函数中，通过随机扰动目标函数而不是学习算法的输出来满足差分隐私，在降低噪声量的同时，有助于提高推荐精确度.本文采用目标优化函数：

(22)

其中，ηj是干扰目标函数的噪声矩阵.

算法1.RatingMatrixProcessing(R，b0，λ，α).

输入:原始用户-项目评分矩阵R、所有项目评分的全局平均数b0、正则化参数λ、学习速率α、潜在特征向量维度d；

输出:用户潜在特征矩阵U.

Step1. 计算目标函数误差

① foriin rangeU：

② forjin rangeV：

③ if 用户参与了评分

end if

⑤ end for

⑥ end for

Step2. 训练得到最优化U

① while(abs(连续2次目标值之差)>epsilon)

② foriin rangeU：

③ forjin rangeV：

④ 计算预测用户评分；

⑤eui=rij-〈ui,vj〉-bi-bj-b0；*计算预测评分与实际评分误差eui*

⑥ forkin ranged：

⑦ui←ui+α(eui·vj-λui)；

⑧vj←vj+α(eui·ui-λvj)；

⑨ end for

⑩bu←bu+α(eui-λbu)；

算法2.GenerateNoiseMatrix(ε).

输入:隐私预算参数ε、潜在特征向量维度d；

输出:添加噪声后的矩阵η.

① foriin ranged：

③ end for

④ returnη.

其中，Hj是一个随机向量，满足指数分布Hj～Exponential(1).将Hj加入每一个用户向量Ui中.Ci是一个独立随机向量，并且满足Ci～N(0,1k).生成噪声矩阵η后，采用vj添加到目标函数中，在每次迭代过程中实现扰动操作.其中，η满足定理1，噪声矩阵任意向量ξi∈N之间相互独立，且其概率密度函数为，因此矩阵η满足ε-差分隐私.

算法3.ItemProfileMatrix(R,b0,U,λ,α,η).

输入:原始评分矩阵R、评分记录的全局平均数b0、用户特征矩阵U、正则化参数λ、学习速率α、噪声矩阵η、潜在特征向量维度d；

输出:物品特征矩阵V、用户偏置bu、物品偏置bi.

Step1. 目标函数加扰

① foriin rangeU：

② forjin rangeV：

③ if 用户参与了评分

⑤ end if

⑥ end for

⑦ end for

Step2. 训练优化

① while(abs(连续2次目标值之差)>epsilon)

② foriin rangeU：

③ forjin rangeV：

④ 计算预测用户评分；

⑤eui=rij-〈ui,vj〉-bi-bj-b0；*计算误差eui*

⑥ forkin ranged：

⑦vj←vj+α(eui·ui-λvj)；

⑧ end for

⑨bu←bu+α(eui-λbu)；

⑩bi←bi+α(eui-λbi)；

4 实验结果与分析

在本节中，将通过具体的实验来对本文提出的方法进行分析、验证和说明.实验环境为Intel Core 2 Duo CPU 2.94 GHz,4 GB内存、Windows7 64 b操作系统，实验使用Python实现相关推荐算法.

4.1 评价指标

评价推荐系统推荐质量的度量标准主要有统计精度度量方法(prediction error)、决策支持精度度量方法(IR metrics)和排名度量方法(ranking metrics).本文实验采用统计精度度量方法中均方根误差RMSE作为评价指标来衡量评分预测推荐精确度：

(23)

4.2 数据集

为了评价算法的性能，本文实验采用2个不同规模的数据集：

1) 本文采用GroupLens研究组提供的MovieLens(www.grouplens.org)数据集ML-100k对算法进行评估，该数据集包含了943个用户对1 682部电影的100 000个评分记录，每个用户至少对20部电影评过分，评分范围为1～5之间的整数，代表喜好程度从低到高.该数据集的评分稀疏度为93.7%.实验中，我们将数据集平均分成5组，采用交叉验证的方法进行实验，训练集与测试的大小比例为4∶1.

2) Netflix数据集是一个评分比较稀疏的数据集(评分稀疏度为98.8%)，该数据集包括480 189个用户对17 770部电影的103 297 638条评分数据，评分为1～5之间的整数.实验中，我们随机选取2 000个用户对4 000部电影的214 690条评分数据作为本文的实验基础数据集，评分稀疏度为97.3%.数据集的具体描述如表1所示：

Table 1 Experimental Dataset Characteristics表1 实验数据集特征描述

4.3 对比算法

根据推荐应用场景的特点，我们将本文提出的基于差分隐私保护的矩阵分解方法(differentially private matrix factorization， DPMF)与4种推荐算法进行实验对比来验证其有效性：

1) 基于用户的推荐方法(user-basedKNN)；

2) 基于项目的推荐方法(item-basedKNN)；

3) SVD++；

4) 交替最小二乘法ALS.

推荐算法1，2是基于近邻的协同过滤推荐算法，该算法简单有效且能够提供准确及个性化的推荐.基于近邻的方法可以分为基于用户的和基于项目的推荐.基于用户的推荐方法是依赖于和自己兴趣相同的用户来预测一个评分，而基于项目的推荐方法是通过评分相近的项目来预测.SVD是一种常用的矩阵分解算法，能够有效获取低维特征空间上的语义概念.SVD++是基于SVD的一种改进算法，该方法在SVD的基础上整合了一种隐式反馈，能够提供比SVD方法更好的精确度.ALS算法的核心思想与本文采用的SGD方法类似，通过分别交替固定用户和项目特征向量来计算其中另一个.当其中的一个特征向量是常量时，最优化问题变成二次的，就可以进行优化求解.

4.4 实验比较与分析

我们在MovieLens数据集和Netflix数据集上进行了不同条件组的实验分析，将潜在特征维度的范围设置为20～100，差分隐私预算ε分别取0.05，0.1，0.15，0.2.实验的基本参数配置如表2所示.

Table 2 Experimental Parameters表2 实验参数列表

实验1. 数据稀疏性条件下推荐算法预测准确度

本组实验的目的是考察不同推荐算法在数据稀疏时的推荐结果精度.为了比较本文提出的DPMF对推荐系统性能的影响，该实验通过将DPMF与4.3节中提到的4种算法在MovieLens数据集上进行了实验结果的对比，证明DPMF推荐算法的有效性.如图3所示，在数据稀疏的情况下，基于用户user-basedKNN和基于物品item-basedKNN推荐算法的RMSE值分别为1.048和1.008.而基于矩阵分解的SGD，ALS，SVD++方法RMSE值分别为0.955，0.955，0.950，这3种方法的RMSE值较user-basedKNN和item-basedKNN推荐算法平均下降7.29%.

Fig. 3 Comparison of different recommendation algorithms图3 不同推荐算法的比较

由此可见，在数据稀疏的情况下，基于矩阵分解方法的预测准确度要优于基于用户和项目的协同过滤算法.这主要是因为矩阵分解方法提供了一个有效的压缩模型，保留了原始数据的潜在特征，而传统的协同过滤算法虽然维持了原始数据的完整性，但推荐算法受到数据稀疏性、噪声数据和无代表性的特征数据等负面影响，导致了推荐精度低于矩阵分解方法.同时，我们注意到DPMF的RMSE值在0.963左右，这与其他4种没有采用隐私保护机制的推荐算法的评分预测准确度相比仅损失了约0.027.由此可见，加入适量干扰噪声后，DPMF能够在一定的预测准确度损失范围内进行有效推荐并保护用户隐私.

实验2. 隐私保护对推荐结果的影响

本组实验的目的是考察本文提出的DPMF在对推荐数据进行差分隐私保护的同时对推荐效果的影响.因此，这里我们重点考察了在不同差分预算下的DPMF对推荐结果的影响.

Fig. 4 RMSE comparison of MF and DPMF图4 MF与DPMF的RMSE比较

我们在MovieLens数据集上进行了100次迭代实验，分别设置ε=0.05，0.1，0.15.由图4可以看出，预测准确度随着迭代次数的增加而逐渐提高.经过40次迭代之后RMSE值变化趋于平缓，随机扰动后的预测准确度也有所提高，但下降速率和趋势与MF预测结果趋于一致.

本组实验结果表明:DPMF对预测准确度的影响范围是有限的，一方面既能对推荐数据进行隐私保护;另一方面对最终预测准确度的影响不是很明显.

实验3. 不同的差分隐私保护方法对推荐精度的影响

本组实验的目的是考察在满足差分隐私保护的前提下，本文提出的DPMF和文献[9]提出的差分隐私保护算法对推荐精度的影响.文献[9]提出了首先将评分矩阵进行差分隐私预处理，然后将处理后的数据作为推荐系统的输入数据，在本文中称之为PreDP方法.在MovieLens数据集上进行了2种隐私保护方法实验结果的对比，其中采用相同的差分隐私预算值ε=0.05.在PreDP方法中，我们选择基于项目的item-basedKNN推荐算法.

Fig. 5 RMSE comparison of PreDP and DPMF图5 PreDP与DPMF的RMSE比较

PreDP方法的推荐精确度依赖于k值的选择，由图5可以看出，推荐精度随着最近邻个数的增加而增加.在最近邻个数超过40之后，RMSE趋于稳定值1.092.这是由于评分矩阵稀疏性的原因，影响了推荐算法的推荐精度，PreDP方法没有采用隐语义模型来解决稀疏性问题.在DPMF方法实验中，经过100次迭代之后，RMSE值达到了0.963.

本组实验结果表明:DPMF和PreDP方法在同样满足差分隐私保护的前提下，本文提出的DPMF方法的具有较高的推荐精度.

实验4. 基于矩阵分解的不同差分隐私保护方法对推荐精度的影响

在实验3中，由于PreDP方法并未考虑矩阵分解的模型，因此本组实验的目的是考察在满足差分隐私保护的前提下，本文提出的DPMF和文献[9]提出预处理基础上进行矩阵分解方法，对推荐结果精度的影响.首先，我们采用了文献[9]提出了的差分隐私预处理方法;然后在加扰后的评分矩阵上采用随机梯度下降算法进行矩阵分解，在本文中称之为PreSGD方法.在MovieLens数据集上进行了实验对比，其中差分隐私预算值ε=0.05.

由图6可以看出，DPMF和PreSGD方法的精确度随着迭代次数的增加而逐渐提高，在100次迭代之后，DPMF的RMSE值低于PreSGD方法.预处理PreSGD方法在初始评分矩阵中加入噪声实现差分隐私保护，而本文提出的DPMF将噪声的引入参与到矩阵分解的训练过程中，减少了噪声的整体添加量，在隐私保护的基础上进一步提高了推荐算法的准确性.

Fig. 6 RMSE Comparison of PreSGD and DPMF图6 PreSGD与DPMF的RMSE比较

本组实验结果表明:同样具备差分隐私保护的隐语义模型推荐方法中，DPMF具有较高的推荐精度.

实验5. 潜在特征向量维度对DPMF推荐结果的影响

本组实验的目的是考察本文提出的DPMF在不同潜在特征向量维度下的推荐效果.设定ε=0.1，通过将参数d分别取20，50，100来观察预测误差累计分布函数(cumulative distribution function，CDF)的变化.

由图7可知，预测准确度随着迭代次数的增加而提高.经过40次迭代之后，我们注意到DPMF预测准确度与MF非常接近.因此，DPMF算法对预测准确度影响不大.此外，可以看出随着d的增加，上升速率相对略有减小，这说明随着d值的增加也会对DPMF预测精度产生一定的影响.但随着迭代次数的增加，误差值也逐步减少.在Netflix数据集中，我们观察到当d=50和d=100时的预测精度优于MF，这主要是稀疏性数据对推荐结果产生了影响.

Fig. 7 Prediction error CDF图7 预测误差CDF趋势图

本组实验结果表明:潜在特征向量维度对DPMF预测精度没有非常明显的影响.

实验6. 不同差分预算对推荐精确度的影响

本组实验的目的是考察本文提出的DPMF方法中隐私预算参数对矩阵的保护程度.因此，这里我们重点考察差分隐私预算ε在一定取值范围内的DPMF对推荐结果的影响.

我们设置d=50，ε分别取0.05，0.1，0.15来对比实验.经过40次迭代之后，MF与差分隐私曲线相融合，这表明无论ε的取值大小，只要满足差分隐私保护，迭代结果不会明显影响最终的预测准确度.另外，根据不同的ε值曲线对比，可以得出随着ε的取值越小，DPMF隐私保护水平越高，但可用性相对越低.相反，ε的取值越大DPMF隐私保护水平越低.在图8(a)中，我们可以看到当差分预算值为ε=0.15时，与无差分隐私保护的MF的曲线基本一致;在图8(b)中，预测曲线与图8(a)中走势一致，随着迭代次数的增加，预测准确度接近一致.

Fig. 8 Different privacy budgets CDF图8 不同差分预算CDF趋势图

本组实验结果表明:差分隐私预算ε与DPMF隐私保护水平成反比，与预测准确度成正比.

实验7. 不同差分隐私预算下的平均误差

本组实验的目的是考察本文提出的DPMF方法中隐私预算参数ε对推荐结果的误差率.因此，这里我们重点考察了在不同隐私预算下的DPMF的平均误差下降速率.

在100次迭代过程中，预测误差下降平均速率与差分隐私预算关系如图9所示.预测误差表示在每次迭代过程中，预测精度的下降平均速率.我们分别得出基于差分隐私预算ε取不同值时对应的平均下降速率.比较明显的是:在MovieLens数据集中，当ε=0.15时，预测错误率达到0.74;而当ε=0.2时，预测误差有所回升.因此，我们可以判断在ε=0.15附近，预测错误率达到了某一极小值(极小值≤0.74).如果我们减小差分隐私保护，即将ε从0.1提升到0.15，经过100次迭代，结果显示推荐精度变得非常接近实际评分.

Fig. 9 The prediction error by average speed图9 预测误差下降平均速率

本组实验结果表明:差分预算ε在DPMF隐私保护中存在一个最优ε值，使得隐私保护程度和推荐的可用性相对平衡.

5 结束语

本文将差分隐私保护方法应用于解决推荐问题的矩阵分解方法之中.面向集中式推荐场景，建立基于矩阵分解的协同过滤推荐模型，提出了一种满足ε-差分隐私的矩阵分解机制，采用目标扰动技术对目标函数进行随机干扰，并通过对引入差分隐私保护后的推荐质量进行分析，得到了若干有指导意义的结论.与现有典型推荐方法相比，本文提出新的带隐私保护的矩阵分解方法既能够在一定推荐精确度损失范围内进行推荐并保护用户隐私信息，它为推荐系统中隐私保护问题的研究提供了新的思路.如何在隐私保护和推荐质量之间寻找一个平衡是一个值得深入研究的课题.下一步的工作是研究如何在不可信推荐系统中实现满足差分隐私保护的推荐方法.

[1]Resnick P, Iakovou N, Sushak M, et al. GroupLens: An open architecture for collaborative filtering of netnews[C]Proc of ACM Conf on Computer Supported Cooperative Work. New York: ACM, 1994: 175-186

[2]Hill W, Stead L, Rosenstein M, et al. Recommending and evaluating choices in a virtual community of use[C]Proc of SIGCHI Conf on Human Factors in Computing Systems. New York: ACM, 1995: 194-201

[3]Wang Licai, Meng Xiangwu, Zhang Yujie. Context-aware recommender systems[J]. Journal of Software, 2012, 23(1): 1-20 (in Chinese)(王立才, 孟祥武, 张玉洁. 上下文感知推荐系统[J]. 软件学报, 2012, 23(1): 1-20)

[4]Sawar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]Proc of the 10th Int Conf on World Wide Web. New York: ACM, 2001: 285-295

[5]Shi Yue, Larson M, Hanjalic A. Exploiting user similarity based on rated-item pools for improved user-based collaborative filtering[C]Proc of the 3rd ACM Conf on Recommender Systems. New York: ACM, 2009: 125-132

[6]Kamishima T, Akaho S. Nantonac collaborative filtering: A model-based approach[C]Proc of the 4th ACM Conf on Recommender Systems. New York: ACM, 2010: 273-276

[7]Zhou Ke, Yang Shuanghong, Zha Hongyuan. Functional matrix factorizations for cold-start recommendation[C]Proc of the 34th ACM Conf on Research and Development in Information Retrieval. New York: ACM, 2011: 315-324

[8]Dwork C. Differential privacy[C]Proc of the 33rd Int Colloquium on Automata, Languages and Programming. Berlin: Springer, 2006: 1-12

[9]McSherry F, Mironov I. Differentially private recommender systems: Build privacy into the net[C]Proc of the 15th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2009: 627-636

[10]Machanavajjhala A, Korolova A, Sarma A D. Personalized social recommendations: Accurate or private[J]. Proceedings of the VLDB Endowment, 2011, 4(7): 440-450

[11]Zhu Tianqing, Li Gang, Ren Yongli, et al. Differential privacy for neighborhood-based collaborative filtering[C]Proc of ACM Int Conf on Advances in Social Networks Analysis and Mining. New York: ACM, 2013: 752-759

[12]Zhu Tianqing, Li Gang, Ren Yongli, et al. Privacy preserving for tagging recommender systems[C]Proc of ACM Int Conf on Web Intelligence. New York: ACM, 2013: 81-88

[13]Friedman A, Schuster A. Data minning with differential privacy[C]Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 493-502

[14]Chaudhuri K, Monteleoni C, Sarwate A D. Differentially private empirical risk minimization[J]. The Journal of Machine learning Research, 2011, 12(2): 1069-1109

[15]Chaudhuri K, Monteleoni C. Pricacy-preserving logistic regression[C]Proc of Annual Conf on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2008: 289-296

[16]Cormode G, Procopiuc M, Srivastava D, et al. Differentally private publication of sparse data[OL]. [2011-03-04]. http:arxiv.orgabs1103.0825

[17]Sarathy R, Muralidhar K. Some additional insights on applying differential privacy for numeric data[C]Proc of Int Conf on Privacy in Statistical Databases. Berlin: Springer, 2010: 210-219

[18]Li Ninghui, Qardaji W, Su Dong. Procably private data anonymization: Or,k-anonymity meets differential privacy, CERIAS TR2010-24[R]. West Lafayette, Indiana: Center for Education and Research Information Assurance and Security, Purdue University,2010

[19]Zhou Shuheng, Ligett K, Wasserman L. Differential privacy with compression [C]Proc of IEEE Int Symp on Information Theory. Los Alamitos, CA: IEEE Computer Society, 2009: 2718-2722

[20]Vu D, Slavkovic A. Differential privacy for clinical trial data: Preliminary evaluations[C]Proc of the 9th IEEE Int Conf on Data Mining. Los Alamitos, CA: IEEE Computer Society, 2009: 138-143

[21]Gehrke J, Lui E, Pass R. Towards privacy for social networks: A zero-knowledge based definition of privacy[C]Proc of the 8th Conf on Theony of Cryptography. Berlin: Springer, 2011: 432-499

[22]Hua Jingyu, Xia Chang, Zhong Sheng. Differentially private matrix factorization[C]Proc of the 24th Int Joint Conf on Artificial Intelligence. New York: ACM, 2015: 1763-1770

[23]Xiong Ping, Zhu Tianqing, Wang Xiaofeng. Differential privacy protection and application[J]. Chinese Journal of Computers, 2014, 37(1): 113-114 (in Chinese)(熊平, 朱天清, 王晓峰. 差分隐私保护及其应用[J]. 计算机学报, 2014, 37(1): 113-114)

[24]Xiao Xiaokui, Wang Guozhang, Gehrke J. Differential privacy via wavelet transforms[C]Proc of the 26th IEEE Int Conf on Data Engineering. Piscataway. NJ: IEEE, 2010: 225-236

[25]Hay M, Rastogi V, Miklau G, et al. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment, 2010, 3(1): 66-69

[26]Chen R, Mohammed N, Fung Bcm, et al. Publishing setvalued data via differential privacy[J]. Proceedings of the VLDB Endowment, 2011, 4(11): 1087-1098

[27]Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[J]. IEEE Trans on Knowledge and Data Engineering, 2005, 17(6): 734-749

[28]Koren Y. Factorization meets the neighborhood: A multi-faceted collaborative filtering model[C]Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 426-434

[29]Koren Y, Robert B, Chris V. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30-37

[30]Dwork C, Mcsherry F, Smith A. Calibrating noise to sensitivity in private data analysis[C]Proc of the 3rd Theory of Cryptography Conf. Berlin: Springer, 2006: 265-284

[31]Mcsherry F. Mechanism design via differential privacy[C]Proc of the 48th Annual IEEE Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2007: 94-103

[32]Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]Proc of the 10th Int Conf on World Wide Web. New York: ACM, 2001: 285-295

[33]Lee J, Clifton C. How much is enough? Choosingεfor differential privacy[C]Proc of the 14th Int Conf on Information Security. Berlin: Springer, 2011. 325-340

[34]He Xianmang, Wang Xiaoyang, Chen Huahui, et al. Research on the selection of differential privacy protection parameterε[J]. Journal on Communications, 2015, 36(12): 125-129 (in Chinese)(何贤芒, 王晓阳, 陈华辉, 等. 差分隐私保护参数ε的选取研究[J]. 通信学报, 2015, 36(12): 125-129)

He Ming, born in 1975. Associate professor at Beijing University of Technology. His main research interests include recommendation systems, data mining and machine learning.

Chang Mengmeng, born in 1987. Master candidate at Beijing University of Technology. His main research interests include differential privacy and machine learning.

Wu Xiaofei, born in 1991. Master candidate at Beijing University of Technology. His main research interests include personalized recommendation and information retrieval.

A Collaborative Filtering Recommendation Method Based on Differential Privacy

He Ming, Chang Mengmeng, and Wu Xiaofei

(CollegeofComputerScience,BeijingUniversityofTechnology,Beijing100124)

Collaborative filtering with large amount of user data will raise serious risk privacy of individuals. How to protect private data information from disclosure has become one of the greatest challenges to recommender systems. Differential privacy has emerged as a new paradigm for privacy protection with strong privacy guarantees against adversaries with arbitrary background knowledge. Although several studies explored privacy-enhanced neighborhood-based recommendations, little attention has been paid to privacy preserving latent factor models. To address the problem of privacy preserving in recommendation systems, a new collaborative filtering recommendation algorithm based on differential privacy is proposed in this paper, which achieves trade-off between recommendation accuracy and privacy by matrix factorization technique. Firstly, user and item latent feature matrices are constructed for decreasing sparsity. After that, matrix factorization model with noise is generated by adding the differential noisy using objective perturbation method, and then stochastic gradient descent is utilized to minimize regularized squared error function and learn the parameters of model. Finally, we apply a differentially private matrix factorization model to predict the ratings and conduct experiments on the MovieLens and Netflix datasets to evaluate its effectiveness. The experimental results demonstrate that our proposal is efficient and has limited side effects on the precision of recommendation.

differential privacy; privacy protection; collaborative filtering; recommender systems; matrix factorization

2016-03-20；

2016-09-06

国家自然科学基金项目(91646201，91546111，60803086)；国家科技支撑计划项目(2013BAH21B02)；北京市自然科学基金项目(4153058，4113076);北京市教育委员会科技计划重点项目(KZ20160005009)；北京市教育委员会科技计划一般项目(KM201710005023) This work was supported by the National Natural Science Foundation of China (91646201, 91546111, 60803086), the National Key Technology Research and Development Program of China (2013BAH21B02)，the Beijing Natural Science Foundation (4153058，4113076), the Key Project of Beijing Municipal Education Commission (KZ20160005009), and the General Project of Beijing Municipal Education Commission (KM201710005023).

TP391; TP18