MapReduce框架下支持差分隐私保护的k-means聚类方法

doi:10.11959/j.issn.1000-436x.2016038

摘要/Abstract

摘要：

针对传统隐私保护方法无法应对任意背景知识下恶意分析的问题，提出了分布式环境下满足差分隐私的k-means算法。该算法利用MapReduce计算框架，由主任务控制k-means迭代执行；指派Mapper分任务独立并行计算各数据片中每条记录与聚类中心的距离并标记其属于的聚类；指派Reducer分任务计算同一聚类中的记录数量num和属性向量之和sum，并利用Laplace机制产生的噪声扰动num和sum，进而实现隐私保护。根据差分隐私的组合特性，从理论角度证明整个算法满足e差分隐私保护。实验结果证明了该方法在提高隐私性和时效性的-情况下，保证了较好的可用性。

关键词: 数据挖掘, k-均值聚类, MapReduce, 差分隐私保护, Laplace机制

Abstract:

Aiming at the problem that traditional privacy preserving methods were unable to deal with malign analysis with arbitrary background knowledge, a k -means algorithm preserving differential privacy in distributed environment was proposed. This algorithm was under the computing framework of MapReduce. The host tasks were obligated to control the iterations of k -means. The Mapper tasks were appointed to compute the distances between all the records and cluster-ing centers and to mark the records with the clusters which the records belong. The Reducer tasks were appointed to compute the numbers of records which belong to the same clusters and the sums of attributes vectors, and to disturb the numbers and the sums with noises made by Laplace mecha ism, in order to achieve differential privacy preserving. Based on the combinatorial features of differential privacy, theoretically prove that this algorithm is able to fulfill -differentiallye private. The experimental results demonstrate that this method can remain available in the process of preserving privacy and improving efficiency.

Key words: data mining, k-means clustering, MapReduce, differential privacy preserving, Laplace mechanism

李洪成,吴晓平,陈燕. MapReduce框架下支持差分隐私保护的k-means聚类方法[J]. 通信学报, 2016, 37(2): 125-131.

Hong-cheng LI,Xiao-ping WU,Yan CHEN. k-means clustering method preserving differential privacy in MapReduce framework[J]. Journal on Communications, 2016, 37(2): 125-131.

图/表 5

参考文献 15

[1]	FLAVIO C , NILESH D , RAVI K . Correlation clustering in MapReduce[C]// The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2014). New York, USA, c2014: 641-650.
[2]	孟小峰, 张啸剑 . 大数据隐私管理[J]. 计算机研究与发展, 2015, 42(2): 265-281. MENG X F , ZHANG X J . Big data privacy management[J]. Journa f Computer Research and Development, 2015, 42(2): 265-281.
[3]	江小平, 李成华, 向文 , 等. k-means聚类算法的MapReduce并行化实现[J]. 华中科技大学学报（自然科学版）, 2011, 39(S1): 120-124. JIANG X P , LI C H , XIANG W , et al. Parallel implementing -meansk clustering algorithm using MapReduce programming mode[J]. nal of Huazhong Univ of Sci ＆ Tech （Natural Science Edition）, 2011, 39(S1): 120-124.
[4]	ROY I , SETTY S T V , KILZER A , et al. Airavat: security and privacy for MapReduce[C]// The 7th USENIX Symposium on Networked Systems Design and Implementation. San Jose, USA, c2010: 297-312.
[5]	肖人毅 . 云计算中数据隐私保护研究进展[J]. 通信学报, 2014, 35(12): 168-177. XIAO R Y . Survey of privacy preserving data queries in cloud compu-ting[J]. Journal on Communications, 2014, 35(12): 168-177.
[6]	SHI E , CHAN T H , RIEFFEL E G , et al. Privacy-preserving aggrega-tion of time-series data[C]// The Network and Distributed System Security Symposium.San Diego. San Diego, USA, c2011.
[7]	DWORK C . A Firm Foundation for Private Data Analysis[J]. Communications of the ACM, 2011, 54(1): 86-95.
[8]	漕？, ?？香, ？岷？ , 等. 差分隐私DPE k-means数据聚合下的多维数据可视化[J]. 小型微型计算机系统, 2013, 34(7): 1637-1640. LI Y , HAO Z F , XIAO Y S , et al. Multidimensional data visualization using aggregation method of differential privacy equip partition k-means[J]. Journal of Chinese Computer Systems, 2013, 34(7): 1637-1640.
[9]	漕？, ?？香, ?? , 等. 差分隐私保护k-means 聚类方法研究[J]. 计算机科学, 2013, 40(3): 287-290. LI Y , HAO Z F , WEN W , et al. Research on differential privacy preserv-ing -means clustering[J]. Computer Science, 2013, 40(3): 287-290.
[10]	何清, 庄福振, 曾立 , 等. PDMiner：基于云计算的并行分布式数据挖掘工具平台[J]. 中国科学：信息科学， 2014, 44(7): 871-885. HE Q , ZHUANG F Z , ZENG L , et al. PDMiner: a cloud computing based parallel and distributed data mining toolkit platform[J]. Chinese Science: Information Science, 2014, 44(7): 871-885.
[11]	MCGREGOR A , MIRONOV I , PITASSI TG , et al. The limits of two-party differential privacy[C]// The 51st IEEE Annual Symposium on Foundations of Computer Science. Las Vegas, USA, c2010: 81-90.
[12]	熊平，朱天清，王晓峰 . 差分隐私保护及其应用[J]. 计算机学报, 2014, 37(1): 101-122. XIONG P , ZHU T Q , WANG X F . A survey on differential privacy and applications[J]. Chinese Journal of Computers, 2014, 37(1): 101-122.
[13]	丁丽萍，卢国庆 . 面向频繁模式挖掘的差分隐私保护研究综述[J]. 通信学报， 2014, 34(10): 200-209. DING L P , LU G Q . Survey of differential privacy in frequent pattern mining[J]. Journal on Communications, 2014, 34(10): 200-209.
[14]	张啸剑，孟小峰 . 面向数据发布和分析的差分隐私保护[J]. 计算机学报， 2014, 37(4): 927-949. ZHANG X J , MENG X F . Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014, 37(4): 927-949.
[15]	MCSHERRY F . Privacy integrated queries: an extensible platform for privacy-preserving data analysis[J]. Communication of the ACM, 2010, 53(9): 89-97.