一种改进的基于差分隐私的k-means聚类算法

初广辉 王晓利

摘 要：聚类分析是数据挖掘和机器学习的一个重要分支，应用范围广，但在聚类分析过程中大量敏感信息的泄露对用户构成威胁。因此，在聚类分析过程中实现隐私保护至关重要。传统基于差分隐私（DP）的k-means聚类算法由于存在盲目选择初始中心点、对异常点敏感度较高等问题，导致在保护数据隐私时，出现聚类可用性较低的情况。针对该问题提出一种改进的基于差分隐私保护的（IDP）k-means聚类算法以提高聚类可用性，并进行理论分析和对比实验。理论分析表明，该算法满足ε-差分隐私;仿真实验结果表明，在同一隐私预算下，k-means算法改进后在聚类可用性上优于其它差分隐私k-means聚类算法，在同一数据集与同一隐私参数下，改进k-means算法在数据可用性方面比传统算法提高了将近5个百分点。

关键词：差分隐私 ;k-means聚类; 隐私保护

DOI：10. 11907/rjdk. 191756 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2019）008-0071-04

An Improved k-means Clustering Algorithm Based on Differential Privacy

CHU Guang-hui， WANG Xiao-li

（College of Computer Science and Engineering， Shandong University of Science and Technology， Qingdao 266590， China）

Abstract： Clustering analysis is a outstanding branch in data mining and machine learning， which has a wide range of applications， but it is scary to users against an ocean of sensitive information leakage in the process of clustering analysis. Therefore， how to achieve clustering analysis privacy protection is crucial. Generally， the traditional k-means clustering algorithm based on differential privacy（DP） has the problem of high sensitivity to abnormal points due to the existence of initial center blind choice， resulting in data privacy protection and low the cluster availability. In order to solve above problems， this paper proposes an improved DPk-means clustering algorithm to improve the availability. Meanwhile， we have carried on the theoretical analysis and experiments. Theoretical analysis indicates that the improved k-means algorithm is superior to other clustering algorithms under the same privacy budget. Under the same privacy parameters of the same data set， in terms of data availability， the algorithm is nearly five percentage points higher than the traditional algorithm.

Key Words： differential privacy; k-means clustering; privacy protection

作者簡介：初广辉（1994-），男，山东科技大学计算机科学与工程学院硕士研究生，研究方向为数据挖掘、隐私保护;王晓利（1994-），男，山东科技大学计算机科学与工程学院硕士研究生，研究方向为数据挖掘、图像处理。

0 引言

随着互联网及信息技术的飞速发展，数据挖掘技术在一些深入的研究和应用中取得了长足进步。聚类分析作为数据挖掘中无监督学习算法的一个重要分支，在数据挖掘领域发挥着重要作用，但是在进行聚类分析过程中可能会导致用户信息泄露。公众对安全性日益重视，隐私保护已成为重要的焦点问题，如何在聚类分析的同时实现个人隐私保护是当前研究热点。

传统隐私保护技术大多基于k-匿名保护模型，但是该保护模型需要特殊的攻击假设，如背景知识攻击[1]和合成攻击[2]，但是这些隐私保护算法的安全性在一定程度上存在问题。2006年，Dwork等[3-4]提出一种极其严格的新型隐私保护模型——差分隐私保护方法。该方法与传统隐私保护算法不同，它不需要关心攻击者的背景知识假设，可通过添加噪声的方式实现隐私保护; 李杨等[5]提出DPk-means算法，通过改变初始中心点盲目选择问题进行算法改进，提出改进的DPk-means聚类方法;傅彦铭等[6]也提出类似的DPk-means++聚类算法。以上算法只是对初始中心选择的盲目性进行改进，但对k-means聚类算法对异常值比较敏感的问题没有作相关处理，因此本文提出一种改进的基于差分隐私的（IDP）k-means聚类算法，该算法根据最远距离规则选取中心点，然后通过区域密度避免异常值的干扰，在保护数据隐私的同时保证数据可用性。

3 实验结果与分析

3.1 实验环境与数据集

为了检测本文算法有效性，必须从以下两个方面考虑问题，第一方面是隐私保护程度，其可通过设置[ε]值进行调节;另一方面是聚类算法的高可用性，其可通过F-measure的值获得。

本文使用Python3.6语言，在Pycharm应用平台上，在具有4 GB RAM的Pentium（R）Dual-Core CPU 3.3 GHz上进行一系列实验。操作系统为Windows 7。为了证明本文算法的有效性，使用DPk-menas、DPk-means++作为对比算法在3个数据集上运行，然后对结果进行评估，本文数据集可以在http：//archive.ics.uci.edu/ml/datasets.html上获取，具体信息如表1所示。

表1 数据集信息

首先对数据进行预处理和规范化，数据规范化主要有3个方法：数据归一化处理、数据标准化处理、数据中心化处理，本文采用归一化方法[19]进行数据规范化，将3个数据集的所有数据均映射到（0，1）之间的小数中。

[x=x-minAmaxA-minA]       （6）

其中[x]表示数据集中的任意点，[maxA和minA]分别代表属性A列中的最大值与最小值，最后结果[x∈（0，1）]。

3.2 评价指标

F-measure[20]是对查准率与查全率的综合评价指标，也是衡量聚类效果的标准，可对两个聚类效果相似性进行评价。 F-measure值取值范围是[0，1]，取值越大，说明两个算法相似性越大，即差分隐私保护算法添加的噪声对聚类可用性影响较小。

[Ci]表示利用OTPK-means算法进行聚类的结果，[Cj]表示利用DP-OTPK-means算法进行聚类的结果。其中[Xi]表示[Ci]的任意聚簇，[Yj]表示[Cj]的任意聚簇，[nij=Xi∩Xj]，[T]为数据集的样本个数，按式（7）-式（9）计算[F（Cj）]既可得到F-measure的结果。

[Recall（Xi，Yj）=nijXi]      （7）

[Precision（Xi，Yj）=nijYi]   （8）

[F（Xi，Yj）=2×Recall（Xi，Yj）×Precision（Xi，Yj）Recall（Xi，Yj）+Precision（Xi，Yj）]  （8）

[F（Cj）=Xi∈cXiTmaxYj∈CjF（Xi，Yj）]    （9）

3.3 实验结果分析

对3个数据集分别用DPk-means算法、DPk-means++算法、本文算法进行实验，求取F-measure，为了避免实验结果的偶然性，本文分别进行20次实验，求取20次实验结果的平均值作为实验总结果。

从图1-图3可以看出，在同一隐私参数[ε]下，本文算法具有更高的可用性，在同一数据集下，伴随着隐私参数[ε]的不断增大，F-measure也在不断增大，说明当[ε]增大，加入的Laplace噪声随之减少，聚类可用性便增大。

图1 Iris数据集实验结果

图2 Wine数据集实验结果

图3 Gamma数据集实验结果

4 结语

本文首先描述了k-means聚类算法在差分隐私中的应用，然后在DPk-means算法基础上加以改进，解决了DPk-means算法对异常值敏感和初始化中心随机选择的问题。首先本文算法根据最远欧式距离选取初始中心点，由于异常点往往分布在数据点边缘地带，为了避免选取到异常值，本文采用区域密度进行筛选，以此提高聚类可用性，并在仿真试验上与DPk-means算法和DPk-means++算法进行比较，结果显示，本文算法在可用性方面优于以上两种算法。在未来研究中，可使用不同的策略进行异常点检测，对本文算法作进一步优化，以便在更多領域进行探索。

参考文献：

[1] 谷汪峰，饶若楠. 一种基于K-anonymity模型的数据隐私保护算法[J]. 计算机应用与软件，2008（8）：65-67.

[2] 焦佳. 社会网络数据中一种基于k-degree-l-diversity匿名的个性化隐私保护方法[J]. 现代计算机：专业版，2016（29）：45-47+60.

[3] BLUM A，DWORK C，MCSHERRY F，et al. Practical privacy： the SULQ framework[C].  Twenty-fourth ACM Sigmod-sigact-sigart Symposium on Principles of Database Systems， 2005.

[4] DWORK C. Differential privacy[C]. Venice： International Colloquium on Automata， Languages & Programming，2006.

[5] 李杨，郝志峰，温雯，等. 差分隐私保护k-means聚类方法研究[J]. 计算机科学，2013，40（3）：287-290.

[6] 傅彦铭，李振铎. 基于拉普拉斯机制的差分隐私保护k-means++聚类算法研究[J]. 信息网络安全，2019（2）：43-52.

[7] SWEENEY L. k-ANONYMITY[J]. International Journal of Uncertainty，Fuzziness and Knowledge-Based Systems，2008，10（5）：557-570.

[8] 刘海，李兴华，雒彬，等. 基于区块链的分布式K匿名位置隐私保护方案[J]. 计算机学报，2019（5）：942-960.

[9] 曹敏姿，张琳琳，毕雪华，等. 个性化（α，l）-多样性k-匿名隐私保护模型[J]. 计算机科学，2018，45（11）：180-186.

[10] 王涛春，刘盈，金鑫，等. 群智感知中基于k-匿名的位置及数据隐私保护方法研究[J]. 通信学报，2018，39（S1）：170-178.

[11] 杨升森. 基于空间位置的K-匿名隐私保护机制研究[J]. 现代信息科技，2018，2（8）：160-161.

[12] 陈家明，王丽，肖亚飞，等.  k-匿名机制下查询隐私的一种度量方法[J]. 中国科学技术大学学报，2018，48（6）：512-518.

[13] 汪小寒，罗永龙，江叶峰，等. 基于KD树最优投影划分的k匿名算法[J]. 南京大学学报：自然科学，2016，52（6）：1050-1064.

[14] 吴伟民，黄焕坤. 基于差分隐私保护的DP-DBScan聚类算法研究[J]. 计算机工程与科学，2015，37（4）：830-834.

[15] 王红，葛丽娜，王苏青，等. 基于OPTICS聚类的差分隐私保护算法的改进[J]. 计算机应用，2018，38（1）：73-78.

[16] DWORK C. Differential privacy： a survey of results[C]. Berlin： International Conference on Theory and Applications of Models of Computation， 2008.

[17] DWORK C，MCSHERRY F，NISSIM K，et al. Calibrating noise to sensitivity in private data analysis[C]. Proceedings of the 3rd Theory Cryptograph Conference， 2006：265-284.

[18] AGGARWAL C C. Outlier analysis[M]. New York： Springer Publishing， 2013.

[19] VISALAKSHI N K， THANGAVEL K. Impact of normalization in distributed k-means clustering[J]. International Journal of Soft Computing， 4（4）：168-172.

[20] JIANG H， YI S， LI J， et al. Ant clustering algorithm with k-harmonic means clustering[J]. Expert Systems with Applications， 2010，37（12）：8679-8684.

（責任编辑：江 艳）