Improvement of differential privacy protection algorithm based on OPTICS clustering

doi:10.11772/j.issn.1001-9081.2017071944

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (1): 73-78.DOI: 10.11772/j.issn.1001-9081.2017071944

Previous Articles Next Articles

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).

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

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

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

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

Abstract

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

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

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

CLC Number:

TP309.2

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.

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

References

[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.)

Improvement of differential privacy protection algorithm based on OPTICS clustering

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	WANG Jiarui, TAN Guoping, ZHOU Siyuan. Clustered wireless federated learning algorithm in high-speed internet of vehicles scenes [J]. Journal of Computer Applications, 2021, 41(6): 1546-1550.
[2]	HU Runyan, LI Cuiran. Clustering algorithm of energy harvesting wireless sensor network based on fuzzy control [J]. Journal of Computer Applications, 2020, 40(9): 2691-2697.
[3]	HUANG Yongxin, TANG Xuefei. Discovery of functional dependencies in university data based on affinity propagation clustering and TANE algorithms [J]. Journal of Computer Applications, 2020, 40(1): 90-95.
[4]	MAO Yimin, LIU Yinping, LIANG Tian, MAO Dinghui. Functional module mining in uncertain protein-protein interaction network based on fuzzy spectral clustering [J]. Journal of Computer Applications, 2019, 39(4): 1032-1040.
[5]	DING Cheng, WANG Qiuping, WANG Xiaofeng. Krill herd algorithm based on generalized opposition-based learning and its application in data clustering [J]. Journal of Computer Applications, 2019, 39(2): 336-342.
[6]	LIU Xiaoming, SHEN Mingyu, HOU Zhengfeng. Firefly fuzzy clustering algorithm based on Levy flight [J]. Journal of Computer Applications, 2019, 39(11): 3257-3262.
[7]	YE Shuang, YANG Xiaomin, YAN Bin'yu. Image super-resolution algorithm based on adaptive anchored neighborhood regression [J]. Journal of Computer Applications, 2019, 39(10): 3040-3045.
[8]	QIU Baozhi, CHENG Luan. Parameter-free clustering algorithm based on Laplace centrality and density peaks [J]. Journal of Computer Applications, 2018, 38(9): 2511-2514.
[9]	SHAO Lun, ZHOU Xinzhi, ZHAO Chengping, ZHANG Xu. Improved K-means clustering algorithm based on multi-dimensional grid space [J]. Journal of Computer Applications, 2018, 38(10): 2850-2855.
[10]	HOU Haiyao, QIAN Yurong, YING Changtian, ZHANG Han, LU Xueyuan, ZHAO Yi. Spatio-temporal query algorithm based on Hilbert-R tree hierarchical index [J]. Journal of Computer Applications, 2018, 38(10): 2869-2874.
[11]	LI Yan, LIU Hong, ZHENG Xiangwei. Application of binary clustering algorithm to crowd evacuation simulation based on social force [J]. Journal of Computer Applications, 2017, 37(5): 1491-1495.
[12]	QIU Baozhi, TANG Yamin. Efficient clustering algorithm for fast recognition of density backbone [J]. Journal of Computer Applications, 2017, 37(12): 3482-3486.
[13]	ZHANG Ning, ZHONG Shan. Mechanism of personal privacy protection based on blockchain [J]. Journal of Computer Applications, 2017, 37(10): 2787-2793.
[14]	WANG Zhiwen, JIANG Lianyuan, WANG Yuhang, WANG Rifeng, ZHANG Canlong, HUANG Zhenjin, WANG Pengtao. Behavior representation of multi-athletes for football game video based on scale adaptive local spatial and temporal characteristics [J]. Journal of Computer Applications, 2016, 36(8): 2134-2138.
[15]	LIU Baojian, ZHANG Xiaoyi, LI Qing. Evolutionary game theory based clustering algorithm for multi-target localization in wireless sensor network [J]. Journal of Computer Applications, 2016, 36(8): 2157-2162.