基于OPTICS聚类的差分隐私保护算法的改进

doi:10.11772/j.issn.1001-9081.2017071944

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 73-78.DOI: 10.11772/j.issn.1001-9081.2017071944

• 2017年全国开放式分布与并行计算学术年会(DPCS 2017)论文 • 上一篇下一篇

基于OPTICS聚类的差分隐私保护算法的改进

王红^1,2, 葛丽娜^1,2, 王苏青³, 王丽颖^1,2, 张翼鹏^1,2, 梁竣程⁴

1. 广西民族大学信息科学与工程学院, 南宁 530006;
2. 广西民族大学东盟研究中心(广西科学实验中心), 南宁 530006;
3. 深圳市亿威尔信息技术股份有限公司, 广东深圳 518000;
4. 广西广播电视信息网络股份有限公司, 南宁 530006

收稿日期:2017-08-07 修回日期:2017-09-10 出版日期:2018-01-10 发布日期:2018-01-22
通讯作者: 葛丽娜
作者简介:王红(1990-),女,河南开封人,硕士,主要研究方向:信息安全;葛丽娜(1969-),女(毛南族),广西环江人,教授,博士,主要研究方向:信息安全;王苏青(1980-),女,广东深圳人,主要研究方向:网络安全;王丽颖(1991-),女,吉林长春人,硕士,主要研究方向:信息安全;张翼鹏(1991-),男(壮族),广西南宁人,硕士,主要研究方向:信息安全;梁竣程(1982-),男,广西南宁人,主要研究方向:信息安全。
基金资助:
国家自然科学基金资助项目（61462009）；广西民族大学科研基金资助项目（2014MDYB029）；广西民族大学中国-东盟研究中心（广西科学实验中心）2014年度开放课题项目（TD201404）；广西民族大学研究生科研创新资助项目（gxun-chxps201671）。

Improvement of differential privacy protection algorithm based on OPTICS clustering

WANG Hong^1,2, GE Lina^1,2, WANG Suqing³, WANG Liying^1,2, ZHANG Yipeng^1,2, LIANG Juncheng⁴

1. College of Information Science and Engineering, Guangxi University for Nationalities, Nanning Guangxi 530006, China;
2. China-ASEAN Research Center(Guangxi Science Experiment Center), Guangxi University for Nationalities, Nanning Guangxi 530006, China;
3. Shenzhen Billion Weir Information Technology Limited Liability Company, Shenzhen Guangdong 518000, China;
4. Guangxi Radio and Television Information Network Limited Liability Company, Nanning Guangxi 530006, China

Received:2017-08-07 Revised:2017-09-10 Online:2018-01-10 Published:2018-01-22
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61462009), the Scientific Research Foundation of Guangxi University for Nationalities (2014MDYB029), the China-ASEAN Research Center of Guangxi University for Nationalities (Guangxi Science Experimental Center) 2014 Open Project (TD201404), the Graduate Research and Innovation Project of Guangxi University for Nationalities (gxun-chxps201671).

摘要/Abstract

摘要： 采用聚类算法预先处理个人隐私信息实现差分隐私保护，能够减少直接发布直方图数据带来的噪声累积现象，同时减小了直方图因合并方式不同带来的重构误差。针对DP-DBSCAN差分隐私算法存在对数据参数输入敏感问题，将基于密度聚类的OPTICS算法应用于差分隐私保护中，并提出改进的DP-OPTICS差分隐私保护算法，对稀疏型数据集进行压缩处理，对比采用同方差噪声和异方差噪声两种添加噪声方式，考虑攻击者能够攻破隐私信息的概率，确定隐私参数ε的上界，有效平衡了敏感信息的隐私性和数据的可用性之间的关系。将DP-OPTICS算法和基于OPTICS聚类的差分隐私保护算法、DP-DBSCAN算法进行对比，DP-OPTICS算法在时间消耗上介于其余二者之间，但是在取得相同参数的情况下，聚类的稳定性在三者中最好，因此改进后OP-OPTICS差分隐私保护算法总体上是可行的。

关键词: 聚类算法, 个人隐私, 重构误差, 差分隐私保护, OPTICS算法

Abstract: Clustering algorithm is used to preprocess personal privacy information in order to achieve differential privacy protection, which can reduce the reconstruction error caused by directly distributing histogram data, and the reconstruction error caused by different combining methods of histogram. Aiming at the problem of sensitivity to input data parameters in DP-DBSCAN (Differential Privacy-Density-Based Spatial Clustering of Applications with Noise) differential privacy algorithm, the OPTICS (Ordering Points To Identify Clustering Structure) algorithm based on density clustering was applied to differential privacy protection. And an improved differential privacy protection algorithm, called DP-OPTICS (Differential Privacy-Ordering Points To Identify Clustering Structure) was introduced, the sparse dataset was compressed, the same variance noise and different variance noise were used as two noise-adding ways by comparison, considering the probability of privacy information's being broken by the attacker, the upper bound of privacy parameter ε was determined, which effectively balanced the relationship between the privacy of sensitive information and the usability of data. The DP-OPTICS algorithm was compared with the differential privacy protection algorithm based on OPTICS clustering and DP-DBSCAN algorithm. The DP-OPTICS algorithm is between the other two in time consumption. However, in the case of having the same parameters, the stability of the DP-OPTICS algorithm is the best among them, so the improved OP-OPTICS differential privacy protection algorithm is generally feasible.

Key words: clustering algorithm, personal privacy, reconstruction error, differential privacy protection, Ordering Points To Identify Clustering Structure (OPTICS) algorithm

中图分类号:

TP309.2

王红, 葛丽娜, 王苏青, 王丽颖, 张翼鹏, 梁竣程. 基于OPTICS聚类的差分隐私保护算法的改进[J]. 计算机应用, 2018, 38(1): 73-78.

WANG Hong, GE Lina, WANG Suqing, WANG Liying, ZHANG Yipeng, LIANG Juncheng. Improvement of differential privacy protection algorithm based on OPTICS clustering[J]. Journal of Computer Applications, 2018, 38(1): 73-78.

参考文献

[1] DWORK C. Differential privacy[C]//ICALP 2006:Proceedings of the 2006 International Colloquium on Automata, Languages, and Programming. Berlin:Springer, 2006:1-12.
[2] 吴伟民,黄焕坤.基于差分隐私保护的DP-DBScan聚类算法研究[J].计算机工程与科学,2015,37(4):830-834.(WU W M, HUANG H K. Study on DP-DBSCAN clustering algorithm based on differential privacy protection[J]. Computer Engineering and Science, 2015, 37(4):830-834.)
[3] NG R T, HAN J. Efficient and effective clustering methods for spatial data mining[C]//Proceedings of the 1994 International Conference on Very Large Data Bases. San Francisco:Morgan Kaufmann, 1994:144-155.
[4] ANKERST M, BREUNIG M M, KRIEGEL H P, et al. OPTICS:ordering points to identify the clustering structure[J]. ACM SIGMOD Record, 1999, 28(2):49-60.
[5] BLUM A, DWORK C, MCSHERRY F, et al. Practical privacy:the SuLQ framework[C]//Proceedings of the Twenty-Fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. New York:ACM, 2005:128-138.
[6] NISSIM K, RASKHODNIKOVA S, SMITH A. Smooth sensitivity and sampling in private data analysis[C]//Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. New York:ACM, 2007:75-84.
[7] DWORK C. A firm foundation for private data analysis[J]. Communications of the ACM, 2011, 54(1):86-95.
[8] 李杨,郝志峰,温雯,等.差分隐私保护k-means聚类方法研究[J].计算机科学,2013,40(3):287-290.(LI Y, HAO Z F, WEN W, et al. Study on clustering method of differential privacy protection k-means[J]. Computer Science, 2013, 40(3):287-290.)
[9] DWORK C, MCSHERRY F, NISSIM K. Calibrating noise to sensitivity in private data analysis[J]. Proceedings of the VLDB Endowment, 2012, 7(8):637-648.
[10] MCSHERRY F, TALWAR K. Mechanism design via differential privacy[C]//FOCS '07:Proceedings of the 2007 IEEE Symposium on Foundations of Computer Science. Piscataway, NJ:IEEE, 2007:94-103.
[11] HAY M, RASTOGI V, MIKLAU G, et al. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the 36th VLDB Endowment, 2010, 3(1/2):1021-1032.
[12] PENG S, YANG Y, ZHANG Z, et al. DP-tree:indexing multi-dimensional data under differential privacy (abstract only)[C]//SIGMOD '12:Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2012:864.
[13] MCSHERRY F D. Privacy integrated queries:an extensible platform for privacy-preserving data analysis[J]. Communications of the ACM, 2010, 53(9):89-97.
[14] 何贤芒,王晓阳,陈华辉,等.差分隐私保护参数ε的选取研究[J].通信学报,2015,36(12):124-130.(HE X M, WANG X Y, CHEN H H, et al. Study on the selection of differential privacy parameters ε[J]. Journal on Communications, 2015, 36(12):124-130.)
[15] LEE J, CLIFTON C. How much is enough? choosing ε for differential privacy[C]//ISC 2011:Proceedings of the 2011 International Conference on Information Security. Berlin:Springer, 2011:325-340.
[16] HARDT M, TALWAR K. On the geometry of differential privacy[C]//Proceedings of the 2010 ACM Symposium on Theory of Computing. New York:ACM, 2010:705-714.
[17] XIAO X, BENDER G, HAY M, et al. iReduct:differential privacy with reduced relative errors[C]//SIGMOD 2011:Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2011:229-240.
[18] LI Y, ZHANG Z, WINSLETT M, et al. Compressive mechanism:utilizing sparse representation in differential privacy[C]//Proceedings of the 10th Annual ACM Workshop on Privacy in the Electronic Society. New York:ACM, 2011:177-182.
[19] XIAO X, WANG G, GEHRKE J. Differential privacy via wavelet transforms[C]//Proceedings of the 2010 IEEE 26th International Conference on Data Engineering. Piscataway, NJ:IEEE, 2010:225-236.
[20] CHEN R, ACS G, CASTELLUCCIA C. Differentially private sequential data publication via variable-length n-grams[C]//Proceedings of the 2012 ACM Conference on Computer and Communications Security. New York:ACM, 2012:638-649.
[21] 曾依灵,许洪波,白硕.改进的OPTICS算法及其在文本聚类中的应用[J].中文信息学报,2008,22(1):51-55.(ZENG Y L, XU H B, BAI S. Improved OPTICS algorithm and its application in text clustering[J]. Journal of Chinese Information Processing, 2008, 22(1):51-55.)
[22] MCSHERRY F D. Privacy integrated queries:an extensible platform for privacy-preserving data analysis[J]. Communications of the ACM, 2010, 53(9):89-97.
[23] ROY I, SETTY S T V, KILZER A, et al. Airavat:security and privacy for MapReduce[C]//NSDI 2010:Proceedings of the 2010 USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA:USENIX Association, 2010:297-312.
[24] ERLINGSSON U, PIHUR V, KOROLOVA A. RAPPOR:randomized aggregatable privacy-preserving ordinal response[C]//Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM, 2014:1054-1067.
[25] 程呈.基于差分隐私的兴趣点推荐系统的设计与分析[D].成都:电子科技大学,2015.(CHENG C. Design and analysis of point of interest recommendation system based on differential privacy[D]. Chengdu:University of Electronic Science and Technology of China, 2015.)
[26] 王越.基于差分隐私的社交网络隐私保护方法研究[D]. 哈尔滨:哈尔滨工业大学,2016.(WANG Y. Study on privacy protection method of social network based on differential privacy[D]. Harbin:Harbin Institute of Technology, 2016.)

基于OPTICS聚类的差分隐私保护算法的改进

Improvement of differential privacy protection algorithm based on OPTICS clustering

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	孙建军, 徐岩. 基于加权改进模糊C均值聚类的欠定混合矩阵估计[J]. 计算机应用, 2020, 40(6): 1769-1773.
[2]	黄永鑫, 唐雪飞. 基于近邻传播聚类和TANE算法的高校数据中函数依赖的发现[J]. 计算机应用, 2020, 40(1): 90-95.
[3]	张书旋, 康海燕, 闫涵. 基于Skyline计算的社交网络关系数据隐私保护[J]. 计算机应用, 2019, 39(5): 1394-1399.
[4]	毛伊敏, 刘银萍, 梁田, 毛丁慧. 基于模糊谱聚类的不确定蛋白质相互作用网络功能模块挖掘[J]. 计算机应用, 2019, 39(4): 1032-1040.
[5]	丁成, 王秋萍, 王晓峰. 基于广义反向学习的磷虾群算法及其在数据聚类中的应用[J]. 计算机应用, 2019, 39(2): 336-342.
[6]	刘晓明, 沈明玉, 侯整风. 基于Levy飞行的萤火虫模糊聚类算法[J]. 计算机应用, 2019, 39(11): 3257-3262.
[7]	叶双, 杨晓敏, 严斌宇. 基于自适应锚定邻域回归的图像超分辨率算法[J]. 计算机应用, 2019, 39(10): 3040-3045.
[8]	邱保志, 程栾. 基于拉普拉斯中心性和密度峰值的无参数聚类算法[J]. 计算机应用, 2018, 38(9): 2511-2514.
[9]	邵伦, 周新志, 赵成萍, 张旭. 基于多维网格空间的改进K-means聚类算法[J]. 计算机应用, 2018, 38(10): 2850-2855.
[10]	侯海耀, 钱育蓉, 英昌甜, 张晗, 卢学远, 赵燚. 基于Hilbert-R树分级索引的时空查询算法[J]. 计算机应用, 2018, 38(10): 2869-2874.
[11]	李焱, 刘弘, 郑向伟. 折半聚类算法在基于社会力的人群疏散仿真中的应用[J]. 计算机应用, 2017, 37(5): 1491-1495.
[12]	邱保志, 唐雅敏. 快速识别密度骨架的聚类算法[J]. 计算机应用, 2017, 37(12): 3482-3486.
[13]	章宁, 钟珊. 基于区块链的个人隐私保护机制[J]. 计算机应用, 2017, 37(10): 2787-2793.
[14]	王智文, 蒋联源, 王宇航, 王日凤, 张灿龙, 黄镇谨, 王鹏涛. 基于尺度自适应局部时空特征的足球比赛视频中的多运动员行为表示[J]. 计算机应用, 2016, 36(8): 2134-2138.
[15]	黄秀杰, 陈靖, 张运超. 基于最小重构误差的优化局部聚合描述符向量图像检索算法[J]. 计算机应用, 2016, 36(6): 1682-1687.