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

李洪成; 吴晓平; 陈燕

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- MapReduce框架下支持差分隐私保护的k-means聚类方法
- k-means clustering method preserving differential privacy in MapReduce framework
- 通信学报 2016年37卷第2期页码：125-131
- 作者机构：
  
  1. 海军工程大学信息安全系，湖北武汉 430033
  2. 解放军 61062部队，北京100091
- 作者简介：
  
  [ "李洪成（1991-），男，河南商丘人，海军工程大学博士生，主要研究方向为信息安全、数据挖掘。" ]
  [ "吴晓平（1961-），男，山西新绛人，海军工程大学教授、博士生导师，主要研究方向为信息安全、密码学。" ]
  [ "陈燕（1975-），女，河北石家庄人，解放军61062部队高级工程师，主要研究方向为网络应用、信息系统。" ]
- 基金信息：
  
  国家自然科学基金青年基金资助项目(61100042);总后军内科研基金资助项目(AWS14R013)
- DOI：10.11959/j.issn.1000-436x.2016038
  中图分类号： TP301
- 网络首发：2016-02，
  
  纸质出版：2016-02-15
- 稿件说明：
移动端阅览
李洪成, 吴晓平, 陈燕. 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.
李洪成, 吴晓平, 陈燕. MapReduce框架下支持差分隐私保护的k-means聚类方法[J]. 通信学报, 2016,37(2):125-131. DOI： 10.11959/j.issn.1000-436x.2016038.

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. DOI： 10.11959/j.issn.1000-436x.2016038.

摘要

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

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.

关键词

Keywords

references

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 .

孟小峰 , 张啸剑 . 大数据隐私管理 [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 .

江小平 , 李成华 , 向文 , 等 . 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 .

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 .

肖人毅 . 云计算中数据隐私保护研究进展 [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 .

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 .

DWORK C . A Firm Foundation for Private Data Analysis [J ] . Communications of the ACM , 2011 , 54 ( 1 ): 86 - 95 .

漕？ , ?？香 , ？岷？ , 等 . 差分隐私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 .

漕？ , ?？香 , ?? , 等 . 差分隐私保护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 .

何清 , 庄福振 , 曾立 , 等 . 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 .

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 .

熊平，朱天清，王晓峰 . 差分隐私保护及其应用 [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 .

丁丽萍，卢国庆 . 面向频繁模式挖掘的差分隐私保护研究综述 [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 .

张啸剑，孟小峰 . 面向数据发布和分析的差分隐私保护 [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 .

MCSHERRY F . Privacy integrated queries: an extensible platform for privacy-preserving data analysis [J ] . Communication of the ACM , 2010 , 53 ( 9 ): 89 - 97 .

浏览量

1406

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

MapReduce框架下支持差分隐私保护的随机梯度下降算法

IP地理定位技术综述：理论、方法与应用创新

基于快速密度峰值聚类离群因子的离群点检测算法

ERDOF：基于相对熵权密度离群因子的离群点检测算法

基于BCP的联合委托学习模型及协议