一种改进的系统间隐私保持协同过滤推荐算法

吴 涛，黄莉静

1.河北联合大学 现代技术教育中心，河北 唐山 063009

2.河北科技大学 信息科学与工程学院，石家庄 050018

一种改进的系统间隐私保持协同过滤推荐算法

吴 涛1，黄莉静2

1.河北联合大学 现代技术教育中心，河北 唐山 063009

2.河北科技大学 信息科学与工程学院，石家庄 050018

WU Tao,HUANG Lijing.Improved privacy-preserving collaborative filtering recommendation algorithm between systems.Computer Engineering and Applications,2013,49（15）：80-83.

1 引言

由于站点信息的稀疏性，不同的用户之间和系统之间的信息共享成为一种必然的趋势，即为用户提供一种系统间的无缝连接，将分散在不同系统内的用户信息整合并重复利用[1]。随着系统间协同合作的广泛应用，用户的隐私保持问题越来越被关注。虽然隐私偏好设定平台P3P（Platform for Privacy Preference，P3P）及复合能力/偏好设置文件CC/PP（Composite Capabilities/Preferences Profile）提高了用户对个人隐私的控制权，但由于现存的站点大多不支持他们所定义规范和协议，用户隐私难以保障。因此，如何保护隐私数据和防止敏感信息泄露成为系统间协作所面临的重大挑战。

为了解决系统间个性化服务中的隐私泄露问题，B M.Sarwar[2]提出基于流行排列的跨系统个性化方法，即通过用户与系统的参与以及大量的机器学习，将隐私保护机制加入到传统的概率性潜在语义分析PLSA（Probabilistic Latent Semantic Analysis）中。2008年，黄创光[3]提出一种基于同态加密的隐私保护方法，系统根据加密后的矢量积计算用户间的相关相似性，并利用相关相似性实现跨系统隐私保持协同过滤。2009年，C.Clifton[4-5]又利用基于商品服务商模型的安全矢量积[6]技术解决了系统间协作计算问题。但由于第三方的不可信性，使得此方法存在一定的安全隐患。

针对以上存在的用户信息安全问题，本文基于RSA（Rivest，Shamir&Adleman）公钥密码系统和解决互不信任的参与方之间隐私的安全多方计算理论（Secure Multi-party Computation，SMC）[7]为基础，提出一个安全计算模型SCM，并将此安全计算模型SCM应用到系统间的协同过滤推荐算法中。实验证明该算法可以有效防止第三方的恶意串通，保障用户隐私不被泄露，同单系统协同过滤相比，跨系统协同过滤提高了推荐精度，特别是对于用户评分数据非常稀疏的小站点。

2 问题提出

协同过滤技术即收集用户评分数据集中的“最近邻居”，根据“最近邻居”的评分进而预测目标用户的评分。

“最近邻居”即根据相关相似性高的用户的集合，其中相关相似性度量计算公式如下：

由式（1）可得目标用户u的最近邻居集即相似度最大的集合NBSu，将最近邻居集NBSu带入到式（2）可得用户u对项目i的预测评分pu，i，预测评分计算公式如下：

由式（2）可计算得到pu，i的值，用户根据pu，i的值，进行选择，将预测评分最高的N个项目推荐给用户。其中，sim(u，ν)表示用户u和用户ν的相似性。

根据协同过滤发生的位置不同，采取相应的措施。首先，当协同过滤发生在单个系统内部时，则默认用户同意信息共享；其次，当协同过滤的过程发生在不同的系统之间时，由于各种因素造成用户隐私在系统间泄露，使得用户和个性化服务站点不愿意提供用户信息共享的服务或模型[8]。

如假设有N个系统分别为s0，s1，…，sN-1，系统si表示如下：

其中，(ri)i，j表示系统i中的用户i对第j个项目的评分。

为使数据隐私最大限度地得到保持，使用协同过滤技术，对给定的目标用户进行评分预测。对于不同的用户分属于不同的系统时，为了保证信息安全，根据式（1）计算用户的相似度时，首先来判断隐私是否泄露。例如：设系统si和s，通过式（1）计算用户i和用户k的相似度，则()kij和 (rkj)的值必然要在系统si和sk之间共享，而通过(rij)的大小可推测用户i对项目j的评分大于还是小于平均值，进而推测出用户对项目j是喜欢还是厌恶，因而造成隐私泄露。由此可见(rij)和(rkj)值对于跨系统度量用户相似性非常重要。因此保证不把(rij)和(rkj)的值泄露给进行协作计算的系统，就可以消除信息拥有者在共享信息时的顾虑，保证共享信息的质量。

3 基于SCM的系统间隐私保持协同过滤

由于网络上信息资源逐渐增多，使得单个系统中信息的稀疏性越来越严重，要求多个系统间的协作计算也越来越多。当给定目标用户后，系统向相同领域内的系统发出协作计算请求，并按照安全计算模型SCM将请求系统中的用户评分数据在系统间共享，准确地对某一指定项进行评分预测，为用户提供跨系统的隐私保持个性化服务[9]。

3.1 安全计算模型（Security Computing Model，SCM）

为了实现多个第三方协同合作与系统间的数据传递，同时防止第三方和系统恶意串通，本文以RSA公钥密码系统和SMC理论为基础，提出一个安全计算模型SCM。系统首先利用RSA公钥密码系统将公钥放入公钥库，当第三方要为系统提供数据时首先去公钥库里找到系统的公钥，并利用公钥将数据加密，数据并不直接由第三方传递给系统，而是通过一个中间节点，在第三方和中间节点之间采用茫然传送协议，中间节点将获得的数据传递给系统，实现第三方和系统间的数据传递。SCM如图1所示。

图1 安全计算模型SCM

安全计算模型SCM：

（1）系统利用RSA公钥密码系统产生一对用来加密和解密的密钥，公钥PK和私钥SK，并将加密密钥PK放入公钥库，另一密钥SK保密。

（2）当第三方要和系统传递数据时，首先从公钥库中取得系统发布的公钥PK，并将要发送的明文m使用公钥PK加密得到密文c，并将密文c发送给中间节点。

（3）第三方和中间节点采用茫然传送协议，中间节点从密文组(c1，c2，…，cn)中获得一组数据ci。并将获得的数据ci发送给系统。

（4）系统利用密钥SK将收到的数据ci解密得到明文mi。

3.2 基于SCM的跨系统隐私保持协同过滤推荐算法

传统的安全多方计算借助第三方提供的数据，来保护系统内部用户的数据，前提是第三方不能和任何一方串通，但目前没有可靠的方法保证不可信第三方不和系统串通，因此安全性较差。为了解决以上问题，采用基于安全计算模型SCM的跨系统隐私保持协同过滤，下面给出了两个系统间基于SCM的隐私保持协同过滤推荐算法PPCF-SCM，算法描述如下：

输出：Pui

/*系统Alice和系统Bob，Alice持有私有向量XΑ，Bob持有私有向量YB，输出结果为Pui，n代表Alice和Bob共同拥有的项目个数，m代表Bob中用户个数*/

（1）Alice和Bob分别利用RSΑ公钥密码系统产生一对用来加密和解密的密钥，公钥PKΑ、PKB和私钥SKΑ、SKB，并将加密密钥PKΑ、PKB放入公钥库，另一密钥SKΑ、SKB保密。

（2）n个不可信第三方产生一组数据Ra，ra，Rb，rb，且满足ra+rb=Ra·Rb，并将Ra，ra使用公钥PKΑ加密得密文Ra'，ra'，Rb，rb使用公钥PKB加密得密文Rb'，rb'。

（3）第三方和中间节点采用茫然传送协议，将密文c= (Ra'，ra'，Rb'，rb')发送给中间节点，中间节点从多个第三方发来的数据中获得一组数据。并将Ra'，ra'发送给Alice，Rb'，rb'发送给Bob。

（4）Alice和Bob分别利用密钥SKΑ、SKB解密密文得到明文Ra，ra和Rb，rb。

（5）Alice将X'=XΑ+Ra发送给Bob，Bob将Y'=YB+Rb发送给Alice。

（7）Alice计算(X'YB+rb)-RaY'+ra=XΑYB+ν。

（9）Alice利用公式（2）计算预测评分Pui。

（10）Alice选择预测评分最高的Top_N个项目为目标用户i推荐。

该算法结合了SCM的优点，文中已论证了SCM的安全性，同传统的安全多方计算相比，PPCF-SCM可以有效防止第三方的恶意串通，由于RSA公钥密码系统的参与，势必会造成系统间通讯时间的增加，为了提高算法的性能，RSA密钥对的产生即算法的第一步也可以离线进行。

3.3 算法分析

由第（7）步Alice可得：

第（8）步利用公式（1）计算用户i和j之间的相似度即

（3）算法的时间复杂度和通讯耗费：RSA算法的安全性高，但速度慢只适用于少量的数据加密，而算法PPCF-SCM只需要将数据Ra，ra，Rb，rb进行加密，因此选用RSA算法既可以满足安全性的要求，同时也不会影响系统的性能。对此文章在第4章进行了实验说明。

通讯耗费包括两部分，第三方与系统间的通讯及系统之间的通讯。其中第三方与系统间的通讯耗费为O（1），系统之间的通讯耗费为O（n）。

4 实验结果及其分析

4.1 实验数据

实验数据来自于协同过滤领域的公开数据，即Jester数据集，此数据集是对73 421个用户的100个笑话的4.1×106个数据的评分，参与的评分数据为－10到10之间的连续数据。数据库包括三个Excel表格，其中前两个数据较稠密，其稠密度高达72%，第三个数据较稀疏，其稠密度只有24%。

4.2 度量标准

实验评价标准采用平均绝对偏差（Mean Absolute Error，MAE）预测准确性。设评分项目个数为N，预测评分集合为{p1，p2，…，pN}，实际评分集合为{q1，q2，…，qN}，则平均绝对误差[8]为：

MΑE值越小，表明预测评分和实际评分相差越小，预测的准确性精度越高。

4.3 实验结果及分析

为了验证提出的保护用户隐私的跨系统协同过滤推荐算法的有效性，分别从算法的性能和推荐精度上进行了实验验证。

（1）RSA公钥加密系统的性能分析及验证：RSA算法的基础是数论的欧拉定理，它的安全性依赖于大数的因数分解的困难性。目前最新记录是129位十进制数已处在分解技术的边缘上，因此要选取足够大的数作为公钥。考虑到密钥长度对RSA算法的执行时间的影响，利用java语言实现了一个简单的RSA公钥密码系统，并选取密钥长度分别为512 bit，1 024 bit和2 048 bit，图2给出了RSA生成密钥的时间及RSA加密和RSA解密时间。

图2 RSA算法的密钥长度-执行时间

由图2的实验结果可以看出，RSA加密和解密时间均呈现线性增长趋势，并且密钥生成时间随着密钥长度的增加而呈现指数级增加。为了提高系统的安全性则定时更新RSA公钥的密码对。因为对RSA的攻击主要依赖于大数的因数分解，实验分析证明对于200位10进制数进行因式分解，在亿次机上需要运行55万年，因此选取足够大的素数即可保证攻击者根据公钥求私钥在计算上的不可行性。

（2）相似性度量比较：对于分布式系统间基于矢量积的隐私保持协同过滤算法的性能D.Heckmann[8]已经给出了证明，下面针对跨系统协同过滤和单系统协同的精度进行对比实验。分别从数据比较稀疏的数据表中随机选取100个用户评分向量作为系统A，从数据比较稠密的数据表中随机选取100个用户作为系统B。为了比较数据的稀疏度对协同过滤推荐算法的影响，本文采用数据的稀疏度来衡量数据的稀疏情况，稀疏度即用户评分矩阵中未评分数目所占的比例。系统A的数据稀疏度为0.82，系统B的数据稀疏度为0.18。

实验分别利用系统A和系统B内用户的评分信息，分别采用传统的协同过滤推荐算法及改进后的算法PPCF-SCM计算用户之间的平均绝对误差MΑE进行对比实验，其相似邻居的个数从4递增到20个，实验结果如图3、图4所示。

图3 推荐精度对比（系统A）

图4 推荐精度对比（系统B）

由图3和图4可知，对于系统A和系统B改进后的算法PPCF-SCM比传统的协同过滤推荐算法的平均绝对误差有降低，特别是对于系统A，改进后的算法PPCF-SCM比传统的协同过滤推荐算法有显著的降低。

由实验结果可知，协同过滤的推荐精度随着数据集稀疏度的增加而降低，对于用户数据非常稀疏的站点，通过跨系统协作计算，可以有效地提高协同过滤推荐算法的推荐精度，并且基于安全计算模型的跨系统协作计算可以保护用户的隐私不泄露给协同合作的系统。

5 结论

针对跨系统协同过滤推荐算法中用户隐私泄露问题，提出一个安全计算模型，此模型在RSA公钥密码系统和安全多方计算的理论基础上，实现了在保护用户评分矩阵的前提下进行跨系统协同过滤计算，同时可有效防止第三方和任何一方恶意串通，并给出了证明及实验结果。为了简单，在此只是给出了两个系统间协作计算的实验结果，理论上从两个系统推广到多个系统的应用是简单的，但还没有进行实验验证，下一步的工作主要集中在多个系统之间的推广和应用。

[1]Deng Ailin，Zhu Yangyong，Shi Baile.A collaborative filtering recommendation algorithm based on item rating prediction[J]. Journal of Software，2003，14（9）：1621-1627.

[2]Sarwar B M，Karypis G，Konstan J A，et al.Application of dimensionality reduction in recommender system—a case study[C]//ACM WebKDD 2000 Workshop，2000.

[3]黄创光，印鉴，汪静.不确定近邻的协同过滤推荐算法[J].计算机学报，2010，33（8）：1369-1377.

[4]Vaidya J，Clifton C，Zhu M.Privacy preserving data mining（advances in information security）[M].New York：Springer-Verlag，2005.

[5]Kantarcioglu M，Clifton C.Privacy preserving distributed mining of association rules on horizontally partitioned data[J]. IEEE Τransactions on Knowledge and Data Engineering，2004，16（9）：1026-1037.

[6]Qiu Mei，Luo Shoushan，Liu Wen，et al.A solution of secure multi-party multi-data ranking problem based on RSA encryption scheme[J].ACΤA Electronica Sinica，2009，37（5）：1119-1123.

[7]Agrawal R，Evfimievski A，Srikant R.Information sharing across private databases[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. San Diego，CA：ACM Press，2003：86-97.

[8]Heckmann D，Schwartz Τ，Brandherm B，et al.Decentralized user modeling with UserML and GUMO[C]//Proceedings of 10th International Conference on User Modeling（DASUM），Edinburgh，UK，2005：61-65.

[9]Mehta B，Nejdl W.Intelligent distributed user modeling：from semantics to learning[C]//Proceedings of the International Workshop on Ubiquitous and Decentralized User Modeling，UBIDEUM 2007，USA，2007：18-28.

WU Τao1,HUANG Lijing2

1.Modern Education Τechnology Center,Hebei United University,Τangshan,Hebei 063009,China
2.College of Information Science and Engineering,Hebei University of Science and Τechnology,Shijiazhuang 050018,China

Τo solve the privacy disclosure problem of the recommendation algorithm between systems,this paper addresses a secure computation model based on RSA public key cryptosystem and secure multi-party computation.Applying this model to the collaborative filtering between systems,an efficient privacy-preserving collaborative filtering recommender algorithm is proposed.Τhe algorithm uses secure vector product to calculate the similarity of users,prevents the untrusted third party from colluding.Experimental results show that algorithm not only has stronger ability to protect the user’s privacy disclosing to the system which is cooperated,but also has better quality of recommendation,especially for the small system of sparse data.

collaborative filtering;privacy-preserving;secure multi-party computation;RSA public key cryptosystem;secure computation model

针对系统间协同过滤推荐过程中的隐私泄露问题，以RSA公钥密码系统和安全多方计算SMC理论为基础，提出一个安全计算模型SCM，将安全计算模型SCM应用到系统间协同过滤中，得到一个有效的隐私保持协同过滤推荐算法。算法利用安全矢量积计算用户的相似度，防止了第三方的恶意串通。实验表明，该算法不但可以保护用户的隐私不泄露给协同合作的系统，而且提高了推荐算法的精度，特别是对用户数据稀疏的小站点。

协同过滤；隐私保持；安全多方计算；RSA公钥密码；安全计算模型

A

ΤP391.4

10.3778/j.issn.1002-8331.1204-0730

河北省自然科学基金（No.F2008000115，No.F2012208004）。

吴涛（1979—），男，高级实验师，研究领域为计算机网络，网络安全，无线传感网络；黄莉静（1978—），女，硕士研究生，研究领域为计算机网络。E-mail：wjt326@163.com

2012-05-08

2012-08-28

1002-8331（2013）15-0080-04

CNKI出版日期：2012-09-06 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120906.0855.012.html