融合微聚集隐私保护的协同过滤算法研究

鲜英+于炯+杨兴耀+薛朋强

摘 要： 现有的k?匿名隐私保护是一种安全有效的隐私保护算法，针对其对背景知识攻击和同质性攻击防范的不足，提出一种基于敏感属性多样性的微聚集隐私保护的协同过滤算法。算法在满足k?匿名的前提下，融入敏感属性的多样性，在微聚集算法中通过设置同一等价类中敏感属性的差异值，来避免敏感属性值过于接近而造成隐私泄露，从而达到保护隐私数据的目的，同时保证推荐的准确性。实验结果表明，该算法既能保证为用户提供高效的个性化推荐，又能够产生安全的信息表。

关键词： 推荐系统； 微聚集； 协同过滤； k?匿名化； 隐私泄露； 隐私保护

中图分类号： TN919.1?34； TP391 文献标识码： A 文章编号： 1004?373X（2018）06?0005?06

Abstract： As a safe and effective privacy protection algorithm， the existing k?anonymous privacy protection still has some insufficiency caused by background knowledge attack and homogeneity attack. Therefore， a sensitive attribute diversity based microaggregation collaborative filtering algorithm for privacy protection is proposed. On the premise of meeting the k?anonymity requirement， the sensitive attribute diversity is fused into the algorithm. The difference values of sensitive attributes in the same equivalence class are set in the microaggregation algorithm to avoid too close sensitive attribute values which can cause privacy disclosure， so as to achieve the purpose of protecting the privacy data and ensure the accuracy of recommendation. The experimental results show that the algorithm can not only guarantee to provide users with efficient personalized recommendation， but also generate safe information tables.

Keywords： recommendation system； microaggregation； collaborative filtering； k?anonymity； privacy disclosure； privacy protection

0 引 言

随着电子商务的发展，用户很难从网站上提供的海量物品（产品）或者服务中做出最佳的选择。在这些需求的推动下推荐系统应运而生，推荐系统也可以认为是信息过滤系统的一个子集。如今，推荐系统在商业网站中占有重要的位置，比如在在国内有豆瓣、天猫商城、京东商城和当当网等。在这些系统中为了计算商品和个人兴趣之间的匹配程度，服务商需要收集大量的用户信息用于提供服务，比如：评分记录，交易历史记录，签到位置信息等。数据的各处使用导致了推荐系统具有双面性：一方面，获取用户越多的信息就可获得更准确且更合适的推荐；另一方面，收集大量的用户信息数据对用户信息滥用后可能会暴露用户的个人隐私，产生一些隐私安全方面的问题。服务提供商搜集大量的和用户个体相关的数据即微数据[1]，比如：医疗机构中的患者数据，商业场所的客户购买数据、互联网购物数据信息、银行认证的个人身份数据信息等。这些数据中包含着各种个体信息，若在没有考虑到用户隐私保护的前提下，泄露这些信息后被个人或者机构的不合理利用可能会暴露个人隐私，造成大量的经济或精神损失。所以对这些个人信息的隐私保护已经成为互联网隐私安全的重中之重。在推荐系统中常用的k?匿名隐私保护算法没有考虑敏感属性的多样性问题，针对一些同质性和背景知识性攻击不能很好抵御。本文融合敏感属性多样性的微聚集推荐算法，在进行协调过滤推荐的过程中，对数据集的处理避免在同一个等价类中因敏感属性值过于接近从而造成隐私泄露。本文旨在将敏感属性多样性的微聚集算法应用于协同过滤推荐系统中，满足k?匿名隐私保护的条件，在一定程度上达到隐私保护的目的，并通过在真实数据集上进行验证。实验最终证明本文提出的推荐算法在保证良好推荐的前提下可以有效地保护用户隐私。

1 相关工作

1.1 相关知识

概念1（敏感属性的多样性）[1]。为了弥补等价类中敏感属性过于相似而提出，将等价类中敏感属性值的差异限制在一定范围内，从而在某种程度上避免隐私泄露。若设置值的差异范围越大，将会得到越好的保护，当然也会造成一定程度的信息损失。

概念2（SDC）[2]。最早提出信息发布过程中的隐私保护研究的课题，其采用微聚集、样本化、随机化、添加噪音等隐私保护的方法研究避免隐私泄漏的前提下保留更多的有用信息[3]，对数据集的可用性以及保密性进行均衡，微聚集是SDC系列算法之一，用于去抵制重定向识别用户。

概念3（L?关联覆盖）。ID为每个个体的显式标识符，例如身份证号等，S表示敏感属性的值。每一个（ID，S）被称为一个关联，在同一个ID下的所有（ID，S）关联关系的集合，称为一个关联覆盖。如果被关联覆盖的数量为L，就称为L?关联覆盖。endprint

1.2 相关研究

协同过滤隐私保护[4]中常用的方法有密码算法、扰乱数据、模糊方法。第一种加密方法适用于多方交互中隐私数据的保护，如Jeckmans，Peter和Hartel（JPH）协议[5]分为线上协议和线下协议，分别对数据进行加密再做推荐，但仍然存在一些威胁，如来自于不可信RS服务器，不可信Friend和Strangers等方面的威胁。在加密方法中Qiang Tang和Jun Wang等人提出随机选取策略加密[5]，通过随机选取Strangers，并给Friend赋予不同的权值，减少上述威胁。综上所述，加密方法没有扰乱原始数据，有很高的性能，但是巨大的计算量和复杂的安全协议导致它很难广泛使用。第二种数据扰乱（Perturbation）方法[4]，在提交到推荐系统之前通过系统化的增加一些噪音来扰乱敏感数据，达到一定的隐私保护程度。第三种模糊数据（Obfuscation）方法[4]，是在提交到推荐系统之前用户的评分用其他的一些数据来代替，比如平均值，质心的值等来代替，隐私保护算法中泛化和隐匿技术来模糊数据较为常用，其中最早、最经典为k?匿名算法。但是以上的扰乱和模糊数据都存在缺点。扰乱数据中加入噪音的多少很难把握，模糊数据中代替的百分比不好控制。差分隐私[4]的提出可以在一定程度上避免以上问题，在针对有关于KNN（K?Nearest Neighborhood）攻击问题上也得到较好处理。

统计泄密控制（Statistical Disclosure Control， SDC）[2]最早提出信息发布过程中的隐私保护研究的课题，其采用微聚集、樣本化、随机化、添加噪音等隐私保护的方法实现在保护隐私的同时尽量保留数据的可用性和统计特性，微聚集是SDC系列算法之一，可以用于在一定程度上抵制重新定向和识别用户。匿名方法是一种安全有效的隐私保护方法，本文提出一种基于微聚集协同过滤用户隐私的保护算法。该算法是一种高效的微聚集隐私保护算法，既保持了高效性，又增加了等价类中敏感属性值取值差异的约束，在融入了敏感属性值中多样性的情况下，可抵制同质性和背景知识攻击。因此该算法所产生的匿名表的安全性更强，既满足了k?匿名隐私保护而且比一般隐私保护方法更有效。

2 敏感属性多样性微聚集隐私保护算法设计

微聚集算法[1]是由启发式算法将数据集划分为若干个等价类，要求每个等价类包括不少于k个不同元组，并且不同等价类中数据尽可能的相异，同一等价类内数据尽可能的相似，利用等价类质心来代替等价类中元组最终来实现k?匿名隐私保护的算法。如图1算法流程图所示。具体算法流程如下：若数据集存在未评分的数据，首先需要对数据集的数据进行预处理操作，填充数据集；然后，将数据集中的每一列数据标准化，得到标准化矩阵；再使用（k，e）?MDAV算法得到聚类关系；在前三步骤结束之后会形成一个新的数据集，该数据集满足k?匿名，即可达到隐私保护的目的；最后针对匿名后的数据即可在推荐系统中做数据预测，为用户做个性化的推荐。

2.1 数据集预处理

为了计算欧几里得距离，若原数据集有空值，则需要填满数据集。要保证数据集任意属性值中没有丢失值，一般可使用以下方法[6]：

1） 使用行、列数据的加权平均值来填充；

2） 使用行、列数据的众数平均值来填充；

3） 使用行、列数据的中位数平均值来填充[6]。

当前实验中使用方法1）加权平均值填充方法，输入的数据集中可能包含未评分的属性，经过填充预处理后的数据集矩阵为满矩阵。

2.2 标准化数据集

一旦数据集矩阵填满，则需要计算数据集中每一列的标准Z分数，其目的是标准化数据集[7]，使用以下计算方式：

[标准Z分数=xi-μσ]

式中：xi是第i个物品x的值；μ是x的平均值；σ是x的标准偏差。用这种方法转换后的数据符合标准正态分布，均值为0，标准差为1，即物品的均值和标准差分别是0和1。

2.3 （k，e）?MDAV聚类算法

算法输入参数说明：匿名化参数个数k和敏感属性差异参数e，可改变它们的大小使得最终达到一个较理想的状态，S为含有n个评分数据集，具体算法描述如下：

输入：S，k，e

输出：k?匿名化的数据集S′

1） 计算出数据集S的中心点[x]，再找到距离[x]最远距离记录S，再得到离S最远距离的记录[r]；

2） 用S作为中心，选出离S最近距离的k个分数记录，若满足敏感属性取值差异大于等于e，就形成一个聚类，否则继续取入数据，直到满足敏感属性取值的差异大于等于e；

3） 用记录r作为中心，选出离r最近距离的k个分数记录，若选取的数据满足敏感属性取值差异大于等于e，则形成一个聚类，否则继续取入数据，直到满足敏感属性取值的差异大于等于e；

4） 如果余下的数据个数大于等于2k且满足敏感属性取值差异大于等于e，则对余下的数据重复运行步骤1）～步骤3）；

5） 如果余下的数据个数在k～2k-1之间，且满足敏感值差异大于等于e，则将这些记录自成一类，否则将剩余记录加入到离它最近的类中，那么这些数据自成为一个类，记为Cf。

2.4 数据预测

数据预测方法分类[5]如下：

1） 平均值预测方法。在用户的分类和物品的分类中，算出用户对某一类物品的平均评分，若有新的用户和物品加入时，就将其分别对应到相应的用户类和物品类，然后将该评分设为已算出好的平均评分。endprint

2） 邻域的预测方法。其中包括基于用户邻域的预测和基于物品邻域的预测两类，使用相似的用户评分或相似的物品评分来预测。

3） 隐语义的预测方法与矩阵分解模型的预测方法，其本质上都是很相似的，也可以认为是一种比较特殊的降维预测方法，若将用户评分和物品对应的评分建立相应的评分矩阵后，预测问题就是补全其中的缺失值。补全的基本要求即为补全后的矩阵的特征值和之前的特征值不能相差太大，其中基础的解法就是奇异值分解（Singular Value Decomposition，SVD）。此方法首先需要简单地将矩阵补全，如可用平均值方法补全，补全后矩阵为满矩阵。数据经过以上处理后会产生一个标准化的模糊数据集，在推荐系统中为了取得更好的推荐效果，需要对数据进行预测，然后推荐给用户[8]。

3 质量评估标准

3.1 隐私保护性能评测标准

为了测量隐私保护的质量，可用信息丢失量（Information Loss，IL）和泄密风险（Disclosure Risk，DR）这两个因素来考虑[9]。信息丢失通常和偏差平方和（the Sum of Squared Errors，SSE）有关，SSE一般用来测量原始数据被模糊的程度。在微聚集中，SSE的计算公式如下：

[SSE=i=1nj=1m（oij-pij）2]

式中：o代表[m×n]个元素的原始数据集矩阵，oij是属于原始数据集o；p代表[m×n]个元素的模糊矩阵，pij是属于模糊数据集p。

DR[1]为假设攻击者，有原数据集o和模糊数据集p。使用模糊数据集p中的数据pij去链接原数据集o中的对应数据oij，若攻击者成功重新识别出原始数据则称为該数据被泄露[10]，DR的测量是从模糊后的数据表中推测出原数据表中的数据的可能性，DR定义为：

[DR=linked_successtotal_numbers]

式中：分子linked_success表示模糊后的数据表中能链接成功的个数；分母total_numbers表示数据集中总共的个数。由以上分析可知，在隐私保护和数据的使用方面要SSE和DR越低越好[2]。

3.2 评分预测分析

在前面部分，分析了有关于（k，e）?MDAV和MDAV的SSE和DR，然而信息丢失并不是完全能被SSE捕获到。在推荐系统中保护过的数据将会用于去预测用户最感兴趣的item，因此对保护后的数据监测其预测的准确性是非常重要的，设定80%的item值为训练值，20%为测试集合[2]。训练集合是保护后的记录，测试集合是原始记录也就是没有被保护的数据集，使用以下方法进行预测：首先，找到最近邻，在测试数据集中给定用户uj，在训练集合中找的最近用户uj；然后，分配预测值，对于用户ui的预测值是对应于uj。

一旦如以上方法对测试集合中的所有用户预测完成后，计算测试集的原始值和通过以上方法得到的分配值之间的误差[10]，在推荐系统中对推荐质量的评测主要有统计精度度量方法以及决策支持精度度量方法两种方法[11]。其中统计精度度量方法中的平均绝对误差（Mean Absolute Error，MAE）是一种较为常用的度量推荐质量高低的方法，以对推荐质量进行直观的度量。

本实验使用MAE 作为评价标准，其是通过计算预测值和实际值之间的偏差来用于预测它们推荐的准确性。其中MAE越小，得到的推荐质量就越高。设预测值的集合可以表示为[p1，p2，…，pn]，则相应的实际值的集合可表示为[r1，r2，…，rn]，则MAE可以定义为：

[MAE=i=1npi-rin]

式中：[n]是预测元素的个数；[pi]是元素[i]的预测值；[ri]是测试集合中的真实值[3]。

4 实 验

本节主要内容包括使用以上方法得到实验结果，将和之前的（MDAV）算法以及传统的k?匿名隐私保护算法做比较。在本实验中e的取值为0.3，和文献[1]相同，e值越大，信息损失量随之增大。

4.1 数据集及其预处理

数据集选择Jester Joke，其中包括73 496个用户的410万次评分对100个笑话做出不同的评分。评分范围是从-10～10的连续实数。用zscore来标准化数据集，得到一个符合标准正态分布，即均值为0，标准差为1的数据集，再进行本文实验操作。

4.2 结果分析

图2显示了在不同k下的基于MDAV算法的隐私保护协同过滤下的SSE比较结果，可以看出，在k取不同的值时基于（k，e）?MDAV算法下且e的取值为0.3时SSE的变化趋势。还可以看出当引入属性多样性以后（k，e）?MDAV算法的SSE的值比MDAV算法略高，原因是（k，e）?MDAV算法增加了对类的约束，最终产生的类的大小比MDAV产生的类要大，故而SSE也相对来说会变大。但两条曲线总体靠得很近，信息损失量并不大，增加了敏感属性的差异后抗攻击能力更强，相比较而言，k?匿名隐私保护算法SSE普遍偏高，数据被模糊的程度远不及MDAV系列算法。

图3显示了在不同k下的基于MDAV算法的隐私保护协同过滤下的DR和在k取不同的值时且e的取值为0.3时基于（k，e）?MDAV算法的DR的值的比较。可以看出，随着k的增大泄密风险的值在减小，原因是分组个数k增大，数据分组中的失真度也会增大，被成功链接的概率就会变小。k?匿名算法也随着分组数的增多泄密风险逐渐降低，但总体趋势高于以下两种，从图3也可以看出（k，e）?MDAV算法的泄密风险的值比原MDAV算法的DR值要低，由此产生的匿名信息表比原算法产生的表更加安全。endprint

使用以上方法对处理后的数据做预测，通过MAE值比较三种方法的推荐准确性。如图4所示，可以看出k?匿名算法在DR较大时平均绝对误差很大，随着泄密风险的降低其误差将会越来越低，但其MAE一直高于MDAV，（k，e）?MDAV的MAE值低于原MDAV算法。原因在于MAE是通过计算预测值和实际值之间的偏差来用于预测它们推荐的准确性，其中MAE越小，得到的推荐质量就越高。由此可得出（k，e）?MDAV在加入敏感属性多样性后其推荐准确性并没有丢失。

图5显示了在不同DR下的基于MDAV算法的隐私保护协同过滤下的信息丢失程度和在不同DR下时且e的取值为0.3时基于（k，e）?MDAV算法的SSE的值的比较。可以看出（k，e）?MDAV算法的SSE的取值低于原MDAV算法，结果表明（k，e）?MDAV算法可以更有效地模糊数据。在k?匿名算法中SSE的值较高，原始数据被模糊的程度较低， 由此可以得出结论：相比于MDAV算法和k?匿名算法。基于（k，e）?MDAV算法其预测质量和隐私保护的质量较好。

5 结 语

协同过滤是用于上下文中的一种用户推荐系统[12]，尽管协同过滤有许多好处，且有大量的相关方法被提出，但是在这些研究中仍然面临着许多挑战，其中最重要的是合理保护用户隐私相关问题[13]，包括对用户偏好方面的隐私保护和推荐质量高低的权衡。k?匿名隐私保护方法是一种高效的隐私保护方法[14]，但仍然存在一些不足，使得攻击者有机可乘，如同质性攻击和背景知识攻击。因此，本文融入（k，e）?MDAV的协同过滤推荐算法是基于微聚集的且考虑到敏感属性的多样性的隐私保护算法。该算法既能有效地实现个性化的推荐，又可以安全地保护用户隐私信息。使用jester真实数据集，利用不同的指标建立模型，实验结果表明，用该方法比原MDAV算法在模糊数据上更有效，本文所提出的算法既保持原推荐算法的高效性同时在隐私保护方面获得了很大改進。在未来的研究中，需要针对多敏感信息的多样性进行研究，保证有较高的效率和推荐质量。并且，对信息暴露多少和推荐质量高低以及隐私保护程度三者之间比重的权衡也是很重要的研究范围。

参考文献

[1] 夏赞珠.微数据发布中的隐私保护匿名化算法研究[D].金华：浙江师范大学，2011.

XIA Zanzhu. Research on microdata anonymity algorithms for privacy?preservation data publishing [D]. Jinhua： Zhejiang Normal University， 2011.

[2] CASINO F， DOMINGO?FERRER J， PATSAKIS C， et al. A k?anonymous approach to privacy preserving collaborative filtering [J]. Journal of computer & system sciences， 2015， 81（6）： 1000?1011.

[3] CASINO F， DOMINGO?FERRER J， PATSAKIS C， et al. Privacy preserving collaborative filtering with k?anonymity through microaggregation [C]// Proceedings of the 2013 IEEE 10th International Conference on E?Business Engineering. Washington： IEEE Computer Society， 2013： 490?497.

[4] ZHU T， REN Y， ZHOU W， et al. An effective privacy preserving algorithm for neighborhood?based collaborative filtering [J]. Future generation computer systems， 2014， 36（36）： 142?155.

[5] TANG Q， WANG J. Privacy?preserving context?aware recommender systems： analysis and new solutions [C]// Proceedings of European Symposium on Research in Computer Security. Berlin： Springer， 2015： 101?119.

[6] 夏建勋，吴非，谢长生.应用数据填充缓解稀疏问题实现个性化推荐[J].计算机工程与科学，2013，35（5）：15?19.

XIA Jianxun， WU Fei， XIE Changsheng. Applying data filling to alleviate the sparsity problem for personalized recommendation [J]. Computer engineering and science， 2013， 35（5）： 15?19.

[7] 杨兴耀，于炯，吐尔根·依布拉音，等.融合奇异性和扩散过程的协同过滤模型[J].软件学报，2013，24（8）：1868?1884.

YANG Xingyao， YU Jiong， IBRAHIM Turgun， et al. Collaborative filtering model fusing singularity and diffusion process [J]. Journal of software， 2013， 24（8）： 1868?1884.endprint

[8] LIU B， HENGARTNER U. Privacy?preserving social recommendations in geosocial networks [C]// Proceedings of 2013 Eleventh Annual International Conference on Privacy， Security and Trust. Tarragona： IEEE， 2013： 69?76.

[9] CLEMENTE F J G. A privacy?preserving recommender system for mobile commerce [C]// Proceedings of 2015 IEEE Conference on Communications and Network Security. Florence： IEEE， 2015： 725?726.

[10] 周长利，马春光，杨松涛.路网环境下保护LBS位置隐私的连续KNN查询方法[J].计算机研究与发展，2015，52（11）：2628?2644.

ZHOU Changli， MA Chunguang， YANG Songtao. Location privacy?preserving method for LBS continuous KNN query in road networks [J]. Journal of computer research and development， 2015， 52（11）： 2628?2644.

[11] 王国霞，王丽君，刘贺平.个性化推荐系统隐私保护策略研究进展[J].计算机应用研究，2012，29（6）：2001?2008.

WANG Guoxia， WANG Lijun， LIU Heping. Study progress of privacy protection techniques used in personalized recommendation system [J]. Application research of computers， 2012， 29（6）： 2001?2008.

[12] 张小波，付达杰.网络信息资源个性化推荐中隐私保护的研究[J].软件，2015，36（4）：62?66.

ZHANG Xiaobo， FU Dajie. Research on privacy protection in the personalized recommendation of network information resources [J]. Software， 2015， 36（4）： 62?66.

[13] 孙广中，魏燊，谢幸.大数据时代中的去匿名化技术及应用[J].信息通信技术，2013，7（6）：52?57.

SUN Guangzhong， WEI Shen， XIE Xing. De?anonymization technology and applications in the age of big data [J]. Information and communications technologies， 2013， 7（6）： 52?57.

[14] 张学军，桂小林，伍忠东.位置服务隐私保护研究综述[J].软件学报，2015，26（9）：2373?2395.

ZHANG Xuejun， GUI Xiaolin， WU Zhongdong. Privacy preservation for location?based services： a survey [J]. Journal of software， 2015， 26（9）： 2373?2395.

[15] 叶阿勇，李亚成，马建峰，等.基于服务相似性的k?匿名位置隐私保护方法[J].通信学报，2014，35（11）：162?169.

YE Ayong， LI Yacheng， MA Jianfeng， et al. Location privacy?preserving method of k?anonymous based?on service similarity [J]. Journal on communications， 2014， 35（11）： 162?169.endprint