k-means clustering method preserving differential privacy in MapReduce framework

Hong-cheng LI; Xiao-ping WU; Yan CHEN

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

您当前的位置：

首页 >

文章列表页 >

k-means clustering method preserving differential privacy in MapReduce framework

academic paper | 更新时间：2024-06-05

- k-means clustering method preserving differential privacy in MapReduce framework
- Journal on Communications Vol. 37, Issue 2, Pages: 125-131(2016)
- 作者机构：
  
  1. 海军工程大学信息安全系，湖北武汉 430033
  2. 解放军 61062部队，北京100091
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China (Project for Youth)(61100042);The Military Scientific Research Project of the General Logistics Department(AWS14R013)
- DOI：10.11959/j.issn.1000-436x.2016038
  CLC： TP301
- Online First：2016-02，
  
  Published：15 February 2016
- 稿件说明：
移动端阅览
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：

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 .

Views

1424

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Stochastic gradient descent algorithm preserving differential privacy in MapReduce framework

Personalized trajectory privacy protection method based on fuzzy sensitivity quantification in MEC

Survey of IP geolocation: theory, methods, and innovative applications

Outlier detection algorithm based on fast density peak clustering outlier factor

ERDOF: outlier detection algorithm based on entropy weight distance and relative density outlier factor

Related Author

Yihan YU

Yu FU

Xiaoping WU

Jiang Zhongyuan

Fang Mengxin

Wang Qizhou

Ma Jianfeng

Li Xinghua

Related Institution

School of Telecommunication, Xi’an Jiaotong University

Purple Mountain Laboratories

School of Cyber Engineering, Xidian University

Zhengzhou Aiwen Tech Co., Ltd.

Department of Computer Science and Engineering, The Hong Kong University of Science and Technology

AI问答

⁰