Differential privacy high-dimensional data publishing method via clustering analysis

doi:10.11772/j.issn.1001-9081.2020111786

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (9): 2578-2585.DOI: 10.11772/j.issn.1001-9081.2020111786

Special Issue: 数据科学与技术

• Data science and technology • Previous Articles Next Articles

Differential privacy high-dimensional data publishing method via clustering analysis

CHEN Hengheng^1,2, NI Zhiwei^1,2, ZHU Xuhui^1,2, JIN Yuanyuan^1,2, CHEN Qian^1,2

1. School of Management, Hefei University of Technology, Hefei Anhui 230009, China;
2. Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education(Hefei University of Technology), Hefei Anhui 230009, China

Received:2020-11-16 Revised:2021-01-11 Online:2021-09-10 Published:2021-05-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (91546108, 61806068), the Anhui Provincial Science and Technology Major Project (201903a05020020), the Anhui Provincial Natural Science Foundation (1908085QG298).

基于聚类分析的差分隐私高维数据发布方法

陈恒恒^1,2, 倪志伟^1,2, 朱旭辉^1,2, 金媛媛^1,2, 陈千^1,2

1. 合肥工业大学管理学院, 合肥 230009;
2. 过程优化与智能决策教育部重点实验室(合肥工业大学), 合肥 230009

通讯作者: 倪志伟
作者简介:陈恒恒(1998-),女,湖南邵阳人,硕士研究生,主要研究方向:信息安全、数据管理;倪志伟(1963-),男,安徽合肥人,教授,博士,主要研究方向:人工智能、机器学习、数据管理;朱旭辉(1991-),男,安徽阜阳人,讲师,博士,主要研究方向:智能计算、机器学习;金媛媛(1998-),女,安徽芜湖人,硕士研究生,主要研究方向:信息安全、数据管理;陈千(1991-),男,安徽合肥人,博士研究生,主要研究方向:信息安全、数据管理。
基金资助:
国家自然科学基金资助项目（91546108，61806068）；安徽省科技重大专项（201903a05020020）；安徽省自然科学基金资助项目（1908085QG298）。

Abstract

Abstract: Aiming at the problem that the existing differential privacy high-dimensional data publishing methods are difficult to take into account both the complex attribute correlation between data and computational cost, a differential privacy high-dimensional data publishing method based on clustering analysis technology, namely PrivBC, was proposed. Firstly, the attribute clustering method was designed based on the K-means++, the maximum information coefficient was introduced to quantify the correlation between the attributes, and the data attributes with high correlation were clustered. Secondly, for each data subset obtained by the clustering, the correlation matrix was calculated to reduce the candidate space of attribute pairs, and the Bayesian network satisfying differential privacy was constructed. Finally, each attribute was sampled according to the Bayesian networks, and a new private dataset was synthesized for publishing. Compared with PrivBayes method, PrivBC method had the misclassification rate and running time reduced by 12.6% and 30.2% averagely and respectively. Experimental results show that the proposed method can significantly improve the computational efficiency with ensuring the data availability, and provides a new idea for the private publishing of high-dimensional big data.

Key words: differential privacy, high-dimensional data, attribute clustering, Bayesian network, data publishing

摘要： 针对已有差分隐私高维数据发布方法无法有效兼顾数据间复杂属性的关联关系和计算成本的问题，提出一种基于聚类分析技术的差分隐私高维数据发布方法PrivBC。首先，基于K-means++设计属性聚类方法，引入最大信息系数量化属性间的关联关系，并对具有高度关联关系的数据属性进行聚类。其次，对聚类产生的各个数据子集进行如下操作：计算关系矩阵以缩减属性对的候选空间，并构建满足差分隐私的贝叶斯网络。最后，根据贝叶斯网络采样每个属性，并合成新的隐私数据集进行发布。与PrivBayes方法相比，PrivBC方法的误分类率和运行时间分别平均降低了12.6%和30.2%。实验结果表明，所提方法在有效保证数据可用性的基础上，可以显著提高计算效率，为高维数据的隐私发布提供了新思路。

关键词: 差分隐私, 高维数据, 属性聚类, 贝叶斯网络, 数据发布

CLC Number:

TP309.2

CHEN Hengheng, NI Zhiwei, ZHU Xuhui, JIN Yuanyuan, CHEN Qian. Differential privacy high-dimensional data publishing method via clustering analysis[J]. Journal of Computer Applications, 2021, 41(9): 2578-2585.

陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.

References

[1] 熊平, 朱天清, 王晓峰. 差分隐私保护及其应用[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.)
[2] 张啸剑, 陈莉, 金凯忠, 等. 基于联合树的隐私高维数据发布方法[J]. 计算机研究与发展,2018,55(12):2794-2809.(ZHANG X J, CHEN L, JIN K Z, et al. Private high-dimensional data publication with junction tree[J]. Journal of Computer Research and Development,2018,55(12):2794-2809.)
[3] DAY W Y,LI N H. Differentially private publishing of highdimensional data using sensitivity control[C]//Proceedings of the 10th ACM Symposium on Information, Computer and Communication Security. New York:ACM,2015:451-462.
[4] XU C G,REN J,ZHANG Y X,et al. DPPro:differentially private high-dimensional data release via random projection[J]. IEEE Transactions on Information Forensics and Security, 2017, 12(12):3081-3093.
[5] CHAUDHURI K,SARWATE A D,SINHA K. A near-optimal algorithm for differentially-private principal components[J]. Journal of Machine Learning Research,2013,14:2905-2943.
[6] ZHANG J,CORMODE G,PROCOPIUC C M,et al. PrivBayes:private data release via Bayesian networks[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York:ACM,2014:1423-1434.
[7] CHEN R,XIAO Q,ZHANG Y,et al. Differentially private highdimensional data publication via sample-based inference[C]//Proceedings of the 21st ACM SIGMOD International Conference on Knowledge Discovery and Data Mining. New York:ACM,2015:129-138.
[8] 苏炜航, 程祥. 一种基于隐树模型的满足差分隐私的高维数据发布方法[J]. 小型微型计算机系统,2018,39(4):681-685.(SU W H,CHENG X. Latent tree model based differentially private high-dimension data publishing algorithm[J]. Journal of Chinese Computer Systems,2018,39(4):681-685.)
[9] QARDAJI W, YANG W N, LI N H. PriView:practical differentially private release of marginal contingency tables[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York:ACM,2014:1435-1446.
[10] WANG N, GU Y, XU J, et al. Differentially private highdimensional data publication via grouping and truncating techniques[J]. Frontiers of Computer Science,2019,13(2):382-395.
[11] LI H R, XIONG L, JIANG X Q. Differentially private synthetization of multi-dimensional data using copula functions[EB/OL].[2020-06-01]. https://openproceedings.org/EDBT/2014/paper_74.pdf.
[12] SU D, CAO J N, LI N H. Differentially private projected histograms of multi-attribute data for classification[EB/OL]. (2015-04-22)[2020-06-01]. https://arxiv.org/pdf/1504.05997.pdf.
[13] REN X B,YU C M,YU W R,et al. LoPub:high-dimensional crowdsourcing data publication with local differential privacy[J]. IEEE Transactions on Information Forensics and Security,2018, 13(9):2151-2166.
[14] SU S,TANG P,CHENG X,et al. Differentially private multiparty high-dimensional data publishing[C]//Proceedings of the IEEE 32nd International Conference on Data Engineering. Piscataway:IEEE,2016:205-216.
[15] 任雪斌, 徐静怡, 杨新宇, 等. 基于Bayes网络的高维感知数据本地隐私保护发布[J]. 中国科学:信息科学,2019,49(12):1586-1605.(REN X B,XU J Y,YANG X Y,et al. Bayesian network-based high-dimensional crowdsourced data publication with local differential privacy[J]. SCIENTIA SINICA Informationis,2019,49(12):1586-1605.)
[16] 王良, 王伟平, 孟丹. 基于加权贝叶斯网络的隐私数据发布方法[J]. 计算机研究与发展,2016,53(10):2343-2353.(WANG L,WANG W P,MENG D. Privacy preserving data publishing via weighted Bayesian networks[J]. Journal of Computer Research and Development,2016,53(10):2343-2353.)
[17] 郝志峰, 王日宇, 蔡瑞初, 等. 基于贝叶斯网络与语义树的隐私数据发布方法[J]. 计算机工程,2019,45(4):124-129.(HAO Z F,WANG R Z,CAI R C,et al. Privacy data publishing method based on Bayesian network and semantic tree[J]. Computer Engineering,2019,45(4):124-129.)
[18] 张啸剑, 孟小峰. 面向数据发布和分析的差分隐私保护[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.)
[19] DWORK C. Differential privacy[C]//Proceedings of the 33rd International Colloquium on Automata, Language and Programming,LNCS 4052. Berlin:Springer,2006:1-12.
[20] ZHU T Q,LI G,ZHOU W L,et al. Differentially private data publishing and analysis:a survey[J]. IEEE Transactions on Knowledge and Data Engineering,2017,29(8):1619-1638.
[21] RESHEF D N,RESHEF Y A,FINUCANE H K,et al. Detecting novel associations in large data sets[J]. Science,2011,334(6062):1518-1524.
[22] 戚围, 王浩, 姚宏亮. 动态贝叶斯网络一种自适应的局部抽样粒子滤波方法[J]. 计算机应用研究,2010,27(4):1304-1307. (QI W,WANG H,YAO H L. Adaptive particle filtering for dynamic Bayesian networks inference based on local sample method[J]. Application Research of Computers,2010,27(4):1304-1307.)
[23] 叶青青, 孟小峰, 朱敏杰, 等. 本地化差分隐私研究综述[J]. 软件学报,2018,29(7):1981-2005.(YE Q Q,MENG X F,ZHU M J,et al. Survey on local differential privacy[J]. Journal of Software,2018,29(7):1981-2005.)
[24] AU W H,CHAN K C C,WONG A K C,et al. Attribute clustering for grouping, selection, and classification of gene expression data[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics,2005,2(2):83-101.
[25] DING Y F,ZHAO Y,SHEN X P,et al. Yinyang K-means:a drop-in replacement of the classic K-means with consistent speedup[C]//Proceedings of the 32nd International Conference on Machine Learning. New York:JMLR. org,2015:579-587.
[26] XIA S Y,PENG D W,MENG D Y,et al. A fast adaptive k-means with no bounds[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2020(Early Access):1-1.
[27] ARTHUR D,VASSILVITSKⅡ S. k-means ++:the advantages of careful seeding[C]//Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia,PA:Society for Industrial and Applied Mathematics,2007:1027-1035.
[28] XIA S Y,WANG G Y,CHEN Z Z,et al. Complete random forest based class noise filtering learning for improving the generalizability of classifiers[J]. IEEE Transactions on Knowledge and Data Engineering,2019,31(11):2063-2078.
[29] XIA S Y,LIU Y S,DING X,et al. Granular ball computing classifiers for efficient, scalable and robust learning[J]. Information Sciences,2019,483:136-152.
[30] CHAUDHURI K, MONTELEONI C, SARWATE A D. Differentially private empirical risk minimization[J]. Journal of Machine Learning Research,2011,12:1069-1109.
[31] ZHANG J,XIAO X K,YANG Y,et al. PrivGene:differentially private model fitting using genetic algorithms[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York:ACM,2013:665-676.
[32] SU D,CAO J N,LI N H,et al. PrivPfC:differentially private data publication for classification[J]. The International Journal on Very Large Data Bases,2018, 27(2):201-223.

Differential privacy high-dimensional data publishing method via clustering analysis

基于聚类分析的差分隐私高维数据发布方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LI Zhuo, SONG Zihui, SHEN Xin, CHEN Xin. Local differential privacy protection mechanism for mobile crowd sensing with edge computing [J]. Journal of Computer Applications, 2021, 41(9): 2678-2686.
[2]	WANG Xin, ZHU Haohua, LIU Guangcan. Convolution robust principal component analysis [J]. Journal of Computer Applications, 2021, 41(5): 1314-1318.
[3]	SUN Jianqiang, XU Shaohua. Knowledge reasoning method based on differentiable neural computer and Bayesian network [J]. Journal of Computer Applications, 2021, 41(2): 337-342.
[4]	WANG Lijuan, CHEN Shaomin, YIN Ming, XU Yueying, HAO Zhifeng, CAI Ruichu, WEN Wen. Improved block diagonal subspace clustering algorithm based on neighbor graph [J]. Journal of Computer Applications, 2021, 41(1): 36-42.
[5]	JIN Bo, ZHANG Zhiyong, ZHAO Ting. Location nearest neighbor query method for social network based on differential privacy [J]. Journal of Computer Applications, 2020, 40(8): 2340-2344.
[6]	TU Zixuan, LIU Shubo, XIONG Xingxing, ZHAO Jing, CAI Zhaohui. Differential private average publishing of numerical stream data for wearable devices [J]. Journal of Computer Applications, 2020, 40(6): 1692-1697.
[7]	LUO Huiwen, LONG Shigong. Location perturbation algorithm based on geo-indistinguishability of user’s region of interest [J]. Journal of Computer Applications, 2020, 40(3): 760-764.
[8]	LIU Xiangyu, CHEN Jinmei, XIA Xiufeng, Manish Singh, ZONG Chuanyu, ZHU Rui. Preventing location disclosure attacks through generating dummy trajectories [J]. Journal of Computer Applications, 2020, 40(2): 479-485.
[9]	LI Kunming, WANG Chaoqian, NI Weiwei, BAO Xiaohan. High-precision histogram publishing method based on differential privacy [J]. Journal of Computer Applications, 2020, 40(11): 3242-3248.
[10]	ZHANG Bang, ZHU Jinxin, XU Zhengyi, LIU Pan, WEI Jianming. Bayesian network-based floor localization algorithm [J]. Journal of Computer Applications, 2019, 39(8): 2468-2474.
[11]	MA Fangfang, LIU Shubo, XIONG Xingxing, NIU Xiaoguang. Privacy protection based on local differential privacy for numerical sensitive data of wearable devices [J]. Journal of Computer Applications, 2019, 39(7): 1985-1990.
[12]	ZHANG Shuxuan, KANG Haiyan, YAN Han. Privacy preserving for social network relational data based on Skyline computing [J]. Journal of Computer Applications, 2019, 39(5): 1394-1399.
[13]	HUO Zheng, ZHANG Kun, HE Ping, WU Yanbin. Crowdsourcing location data collection for local differential privacy [J]. Journal of Computer Applications, 2019, 39(3): 763-768.
[14]	WANG Xiaohan, HAN Huihui, ZHANG Zepei, YU Qingying, ZHENG Xiaoyao. Differential privacy budget allocation method for data of tree index [J]. Journal of Computer Applications, 2018, 38(7): 1960-1966.
[15]	YANG Jie, LI Songbin, DENG Haojiang. Steganalysis based on Bayesian network for compressed speech [J]. Journal of Computer Applications, 2018, 38(7): 1967-1973.