差分隐私保护下基于聚类的KNN协同过滤推荐算法

李佳琪 曲梦溪

摘 要：大数据时代的到来所带来的“信息超载”问题愈发严重，对可解决此问题的推荐系统的准确性和可扩展性要求更高，但人们在享受推荐系统便利的同时也承受着其带来的隐私泄露问题。因此，本文将KNN这一经典的协同过滤算法中融入基于密度的DBSCAN聚类算法和差分隐私保护，提出了差分隐私保护下基于聚类的KNN协同过滤推荐算法，对其隐私保护性能实现了优化。差分隐私保护避免了DPSCAN除噪时可能会带来隐私泄露的风险，并且能够保持聚类的有效性。数据预处理阶段，该算法采用DBSCAN对数据中噪声进行判断和挖掘，并将数据集分类成簇，而后利用差分隐私添加随机噪声敏感数据失真。在推荐过程，采用KNN进行评级预测，只有簇内的项目作为距离计算和预测的候选邻居。

关键词：KNN 聚类；差分隐私；协同过滤；DBSCAN

0.引言

伴随着大数据时代的到来，全球数据量呈爆炸式增长，“信息超载”现象越来越严重。为解决这一问题，个性化推荐系统应运而生，它根据用户特征推荐满足用户需求的对象，实现个性化服务，推荐系统被广泛应用于各个领域，现有的推荐系统主要包括关联规则、基于内容的推荐、协同过滤和混合推荐，协同过滤算法是推荐系统中主流且应用较多的算法之一，协同过滤根据其他用户的偏好向目标用户推荐，它首先找出一组与目标用户偏好一致的邻居用户，然后分析该邻居用户，把邻居用户喜欢的项目推荐给目标用户。协同过滤算法可分为两类：基于记忆的协同过滤和基于模型的协同过滤，基于记忆的协同过滤算法分为基于用户的协同过滤和基于项目的协同过滤，KNN（K-最近邻）是基于用户的协调过滤算法。

传统的KNN是使用所有邻居进行商品之间的相似度计算，这不仅导致其时间复杂度较高，且由于只用单个距离度量参与相似度的计算，还会导致推荐精度不理想。除此之外，噪声数据的存在也是影响推荐准确性的一大重要因素，但噪声数据在隐私保护方面起到的作用同样也不容忽视，所以在对协同过滤算法准确性与可扩展性进行优化的同时也要平衡好其隐私保护性能。

聚类可以对数据集大、复杂的数据分类成簇，可划分未知的类。DBSCAN算法是一种基于高密度连通区域的聚类，将足够高密度的区域划分为簇，可在具有噪声的空间数据库中发现任意形状的簇，具有良好的除噪能力。但如果在聚类分析中发布两点之间的确切距离，攻击者就可以从已知的对象半径中推断出两点之间的具体信息，这就会存在泄漏敏感属性的可能。所以引入差分隐私技术就尤其重要。

差分隐私旨在当从统计数据库查询时，最大化数据查询的准确性，同时最大限度减少识别其记录的机会。它通过添加随机噪声发布点密度的近似值，保证攻击者无法从任何相关的背景知识或者关联的信息中推断出个人的敏感信息。差分隐私提出了一个更为严格的攻击模型，在该攻击模型下，假设攻击者已获取除一个记录以外的所有数据记录，也能够保护该记录的信息不会被泄露。据此，本文提出了差分隐私保护下基于聚类的KNN协同过滤推荐算法。

1.相关工作

与k-means相比，DBSCAN具有不需要预知要形成的簇类的数量、可以发现任意形状的簇类、能够识别出噪声点和对数据库中样本顺序不敏感等优点，但是它有着很高的隐私泄露风险。因此，采用DBSCAN聚类算法除噪、分类成簇后，根据差分隐私保护的拉普拉斯机制对数据进行加噪保护，再利用KNN协同过滤算法进行推荐，并且保证整个算法满足拉普拉斯机制。

KNN协同过滤算法、DBSCAN聚类与差分隐私都是较为成熟的算法，下文介绍三种基础算法的概念及原理，而后在三种算法基础上提出了差分隐私保护下基于聚类的KNN协同过滤推荐算法并进行评估分析。

2.相关基础算法

2.1 DBSCAN：一种基于高密度连通区域的高密度聚类

DBSCAN是一个比较有代表性的基于密度的聚类算法，将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，可在噪声的空间数据库中发现任意形状的聚类，因此具有很好的除噪能力。

用靠近q的对象数度量对象q的密度，连接对象q和其 -邻域，形成的稠密区域作为簇，若 -邻域中对象数不大于Minpts，则创建新簇；若大于Minpts，则称对象q为核心对象。如果p在q的 -邻域内，则称p是q直接密度可達的。具体算法过程如表1

表1 DBSCAN算法

2.2 差分隐私

Calandrino等人研究了几种著名的推荐系统的隐私保护，得出差分隐私技术可以克服许多方法的缺点这一结论，

差分隐私保护是基于数据失真的隐私保护技术，即通过随机噪声的添加使敏感数据失真，同时保持某些数据或数据属性不变，处理后的数据仍然保持某些统计特性。在差分隐私保护方法下，在数据集中添加或删除一条记录不会影响查询输出结果，因此，在上述攻击模型中，攻击者无法通过任何已知记录的敏感属性推断出其他未知记录的敏感属性。下面是差分隐私的定义及原理。

定义1（披露风险公式） 对于两个相差至多一个记录的数据集D1 和D2 ，Range（K） 为一个随机函数K的取值范围，Pr[Es] 为事件Es的披露风险，若随机函数F提供ε-差分隐私保护，则对于所有 ，

（1）

其中披露风险取决于随机函数F的值，随机函数F的选择与攻击者所具有的知识无关。

定义2 （敏感度） 对于函数 ，f 的敏感度定义为：

（2）

其中数据集D1 和D2 相差至多一个记录。敏感度f只是函数的性质之一，与数据集X无关。

定义3（拉普拉斯机制） 设存在一查询函数f、数据集X，查询结果为f（X） ，通过在f（X） 上加入合适选择的随机噪声来保护隐私。函数K的响应值为：f（x）+（Lap（△f/ε））k ，满足ε-差分隐私保护。设噪声函数

呈标准差为 的对称指数分布，其中，b=△f/ε 。则概率密度函数为

，累积分布函数为

3.差分隐私保护下的基于聚类的KNN协同过滤算法

差分隐私保护避免了DBSCAN除噪时可能会带来隐私泄露的风险，并且能够保持聚类的有效性。数据预处理阶段，该算法采用DBSCAN对数据中噪声进行判断和挖掘，并将数据集分类成簇，而后利用差分隐私添加随机噪声敏感数据失真。在推荐过程，采用KNN进行评级预测，只有簇内的项目作为距离计算和预测的候选邻居。

KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类，则该样本也属于这个类，并具有这个类上其余样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN算法在分类时，只与极少量的邻居样本有关。将不同距離的邻居对该样本产生的影响给予不同的权值，权值通常与距离成反比。KNN算法通常有两种相似度计算方法，即标准欧氏距离和余弦距离，标准欧氏距离为欧氏距离的优化。

3.1 KNN协同过滤算法相似度计算方法：

（1）欧式距离计算公式：

标准欧氏距离：将各个维度的数据进行标准化：标准化后的值=（标准化前的值-分量的均值）/分量的标准差，然后计算欧式距离。假设样本集D的均值为m，标准差为S，那么D的“标准化变量”表示为：

则标准欧式距离计算公式：

（2）余弦相似性：将用户评分被看做是n 维空间[0，1]n 上的向量，用户间的相似性通过向量间的余弦夹角度量。设用户i和用户j在n维项目空间上对项目z的评分分别表示为向量 和 ，则用户i和用户j之间的相似性为

3.2 算法的主要思想如下：

（1）数据预处理：

输入：一个n维空间[0，1]n数据集D（D中包含n个对象）、半径参数ε 、邻域密度阈值Minpts。

输出：簇的集合

i.重复表1 DBSCAN（D，ε，Minpts ）算法直到所有的点都已经包含在任一簇或者

被标记为噪声点。

ii.设x={x1，x2，…，xn} 和y={y1，y2，…，yn} 是n维空间[0，1]n 数据集D 两个直接密度可达的对象。

iii.在n维空间[0，1]n 数据集D中，x 与y之间的点密度为

，分别在各维中添加随机噪声使得 ，其中

，重复上述过程直到所有的点都已经包含在任何一个簇中或被标记为噪声。

（2）KNN协同过滤算法：

输入：簇的集合

输出：k个目标用户的相似用户

i.选用合适的数据结构存储训练数据和目标用户

ii.设定参数k=3

iii.维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算目标用户到这k个元组的距离，将训练元组标号和距离存入优先级队列。

iv.遍历训练元组集，计算当前训练元组与目标用户的距离，将所得距离L 与优先级队列中的最大距离Lmax 。

v.进行比较。若 ，则舍弃该元组，遍历下一个元组。若

，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队列。

vi.遍历完毕，计算优先级队列中k个元组的多数类，并将其作为目标用户的类别。

vii.目标用户集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k 值。

4.评估体系

差分隐私保护下基于聚类的KNN协调过滤算法的时间消耗小，而且处理稀疏型数据效果较好，但是不能彻底解决输入敏感性问题。采用两种评估方法：均方根误差：

绝对平均误差： ，其中ri，j 表示用户i对物品j的实际评分， 表示用户i对物品j的预测评分，N是含有的评分数量。MAE和RSME的值越小，表明预测的结果越准确，用户的满意度越高。

5.结束语

本文在KNN协同过滤算法基础上，结合DBSCAN聚类算法，并引入了差分隐私保护，提出了差分隐私保护下基于聚类的KNN协同过滤算法。添加少量随机噪声时，算法仍具有聚类的有效性和KNN的准确性，但算法仍处于理论研究阶段，具体实施与改进仍需继续研究，后期可以在此基础上采用更优化的聚类算法与协同过滤算法。

参考文献：

[1]Armita Afsharinejad.Performance Analysis of a Privacy Constrained KNN Recommendation Using Data Sketches[J].Technical Presentation.2018

[2]Jiawei Han.数据挖掘概念与技术.机械工业出版社，2017

[3]吴伟民.基于差分隐私保护的DP-DBScan聚类算法研究[D].广州：广东工业大学计算机学院，2015

[4]喻新潮.一种聚类与KNN结合的协同过滤算法[D].成都：西南石油大学，2019

[5]李杨.差分隐私保护k-means聚类方法研究[D].广州：广东工业大学自动化学院，2013

[6]毋文敏.基于差分隐私的协同过滤推荐系统的设计与实现[D].徐州：徐州医科大学，2018

[7]胡闯.面向差分隐私保护的聚类算法[D].南京：南京邮电大学，2019

[8]傅彦铭，基于拉普拉斯机制的差分隐私保护k-means++聚类算法研究[D].南宁：广西大学计算机与电子信息学院，2019

[9]李晓瑜，K近邻协同过滤推荐算法的最优近邻参数[D]，安康：安康电子与信息工程学院，2018

作者简介：

李佳琪（1998-），汉族，女，辽宁沈阳人，本科生，研究方向：物联网、数据挖掘。

曲梦溪（1998-），汉族，女，山东济南人，本科生，研究方向：物联网、大数据。