基于贝叶斯网络的差分隐私高维数据发布技术研究

doi:10.19678/j.issn.1000-3428.0067967

摘要/Abstract

摘要： 在实现隐私保护的同时提高数据可用性是高维结构化数据发布研究中的挑战性问题,经典算法PrivBayes针对该问题提供了一种解决方案。为进一步减少计算开销、提高数据可用性,提出基于贝叶斯网络的差分隐私数据发布算法ELPrivBayes。分析贝叶斯网络结构学习阶段的理论计算开销,构建存储属性之间互信息的相关矩阵,避免结构学习算法迭代过程中互信息的冗余计算,降低了时间复杂度。基于平均互信息优化了节点进入贝叶斯网络的顺序,提高结构学习迭代过程中指数机制贡献的互信息期望值,进而提高生成数据集与原始数据集的统计近似度,并实证分析网络结构质量对首节点选择的低敏感性。在4个典型数据集上的实验结果表明,与经典算法PrivBayes及其改进方案相比较,结构学习阶段的计算开销降低了97%~99%,基于指数机制捕获的互信息提高了14%~67%,生成数据集与原始数据集的平均变差距离降低了32%~40%,构建的支持向量机(SVM)分类器的准确率提高了4%~5%,并且当ε≤0.8时,采用ELPrivBayes算法生成数据的可用性提升更为显著。

关键词: 数据发布, 贝叶斯网络, 差分隐私, 隐私保护, 相关矩阵, 平均互信息

Abstract: Improving data availability while implementing privacy protection is challenging in high-dimensional structured data publishing; however, the classic PrivBayes algorithm can solve this issue. To further reduce computational costs and improve data availability, a differential privacy data-publishing algorithm based on Bayesian networks, ELPrivBayes, is proposed. It analyzes the theoretical computational cost of the Bayesian network structure in the learning stage, constructs a correlation matrix for storing Mutual Information(MI) between attributes, avoids redundant calculations of MI in the iterative process of structural learning algorithms, and reduces time complexity. Based on the Average MI(AMI), the order in which nodes enter the Bayesian network is optimized, and the expected mutual information contribution of the exponential mechanism in the iterative process of structural learning increases, thereby improving the statistical approximation between the generated and original datasets. The low sensitivity of the network structure quality to the selection of the first node is analyzed empirically. Experimental results on four typical datasets show that, compared with the classical PrivBayes algorithm and its improved solutions, the computational cost in the structural learning stage is reduced by 97%-99%, the MI captured based on the exponential mechanism is improved by 14%-67%, the average variation distance between the generated and original datasets is reduced by 32%-40%, and the accuracy of the constructed Support Vector Machine(SVM) classifier is improved by 4%-5%. Moreover, when ε≤0.8, the availability improvement of data generated using the ELPrivBayes algorithm is more significant.

Key words: data publishing, Bayesian network, differential privacy, privacy protection, correlation matrix, Average Mutual Information(AMI)

中图分类号:

TP319

卢晓天, 朴春慧, 杨兴雨, 白英杰. 基于贝叶斯网络的差分隐私高维数据发布技术研究[J]. 计算机工程, 2024, 50(5): 167-181.

LU Xiaotian, PIAO Chunhui, YANG Xingyu, BAI Yingjie. Research on Differential Privacy High Dimensional Data Publishing Technology Based on Bayesian Networks[J]. Computer Engineering, 2024, 50(5): 167-181.

https://www.ecice06.com/CN/Y2024/V50/I5/167

参考文献

[1] ASMAA H R, YASIN N B M. Privacy preserving data publishing[J]. International Journal of Physical Sciences, 2015, 10(7):239-247.
[2] 杨高明, 杨静, 张健沛. 聚类的(α,k)-匿名数据发布[J]. 电子学报, 2011, 39(8):1941-1946. YANG G M, YANG J, ZHANG J P. Achieving (α,k)-anonymity via clustering in data publishing[J]. Acta Electronica Sinica, 2011, 39(8):1941-1946. (in Chinese)
[3] SWEENEY L. k-anonymity:a model for protecting privacy[EB/OL].[2023-05-25]. https://www.wisdom.weizmann.ac.il/~/naor/COURSE/PRIVACY/shlomo_jozeph_k-anonymity.pdf.
[4] MACHANAVAJJHALA A, KIFER D, GEHRKE J, et al. L-diversity:privacy beyond k-anonymity[J]. ACM Transactions on Knowledge Discovery from Data, 2006,1(1):1-3.
[5] LI N H, LI T C, VENKATASUBRAMANIANS S. t-closeness:privacy beyond k-anonymity and l-diversity[C]//Proceedings of the 23rd International Conference on Data Engineering. Washington D. C., USA:IEEE Press, 2007:106-115.
[6] WONG R C W, LI J Y, FU A W C, et al. (α,k)-anonymity:an enhanced k-anonymity model for privacy preserving data publishing[C]//Proceedings of the 12th International Conference on Knowledge Discovery and Data Mining. New York, USA:ACM Press, 2006:754-759.
[7] DWORK C. Differential privacy[C]//Proceedings of International Colloquium on Automata, Languages, and Programming. Berlin, Germany:Springer, 2006:1-12.
[8] DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[EB/OL].[2023-05-25]. https://link.springer.com/content/pdf/10.1007/11681878_14.pdf.
[9] DWORK C. Differential privacy:a survey of results[C]//Proceedings of the 5th International Conference on Theory and Applications of Models of Computation. Berlin, Germany:Springer, 2008:1-19.
[10] CHAUDHURI K, SARWATE A D, SINHA K. A near-optimal algorithm for differentially-private principal components[J]. The Journal of Machine Learning Research, 2013, 14(1):2905-2943.
[11] KAPRALOV M, TALWAR K. On differentially private low rank approximation[C]//Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete algorithms. New York, USA:ACM Press, 2013:1395-1414.
[12] YANG J, LI Y. Differentially private feature selection[C]//Proceedings of International Joint Conference on Neural Networks. Washington D. C., USA:IEEE Press, 2014:4182-4189.
[13] 高原秀男. 数据发布中的隐私保护关键技术研究[D]. 北京:北京邮电大学, 2018. GAO Y X N. Research on the key technologies of privacy preserving data publishing[D]. Beijing:Beijing University of Posts and Telecommunications, 2018. (in Chinese)
[14] 刘中锋. 基于局部学习的差分隐私集成特征选择算法[J]. 计算机技术与发展, 2018, 28(10):79-82. LIU Z F. An ensemble feature selection algorithm with differential privacy based on local learning[J]. Computer technology and development, 2018, 28(10):79-82. (in Chinese)
[15] KASIVISWANATHAN S P, JIN H X. Efficient private empirical risk minimization for high-dimensional learning[C]//Proceedings of the 33rd International Conference on Machine Learning. New York, USA:ACM Press, 2016:488-497.
[16] 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
[17] QARDAJI W,YANG W N, LI N H. PriView:practical differentially private release of marginal contingency tables[C]//Proceedings of the International Conference on Management of Data. New York, USA:ACM Press, 2014:1435-1446.
[18] ZHANG J, CORMODE G, PROCOPIUC C M, et al. PrivBayes:private data release via Bayesian networks[J]. ACM Transactions on Database Systems, 2017, 42(4):1-41.
[19] ZHANG W, ZHAO J W, WEI F Q, et al. Differentially private high-dimensional data publication via Markov network[J]. EAI Endorsed Transactions on Security and Safety, 2019, 6(19):159626.
[20] 陈旋, 刘健, 冯新淇, 等. 基于朴素贝叶斯的差分隐私合成数据集发布算法[J]. 计算机科学, 2015, 42(1):236-238. CHEN X, LIU J, FENG X Q, et al. Differential private synthesis dataset releasing algorithm based on navie Bayes[J]. Computer Science, 2015, 42(1):236-238. (in Chinese)
[21] CHEN R, XIAO Q, ZHANG Y, et al. Differentially private high-dimensional data publication via sampling-based inference[C]//Proceedings of the 21th International Conference on Knowledge Discovery and Data Mining. New York, USA:ACM Press, 2015:129-138.
[22] LI X X, LUO C F, LIU P, et al. Information entropy differential privacy:a differential privacy protection data method based on rough set theory[C]//Proceedings of International Conference on Dependable, Autonomic and Secure Computing, International Conference on Pervasive Intelligence and Computing, International Conference on Cloud and Big Data Computing, International Conference on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech). Washington D. C., USA:IEEE Press, 2019:918-923.
[23] 王良, 王伟平, 孟丹. 基于加权贝叶斯网络的隐私数据发布方法[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. (in Chinese)
[24] 郝志峰, 王日宇, 蔡瑞初, 等. 基于贝叶斯网络与语义树的隐私数据发布方法[J]. 计算机工程, 2019, 45(4):124-129. HAO Z F, WANG R Y, CAI R C, et al. Privacy data publishing method based on Bayesian network and semantic tree[J]. Computer Engineering, 2019, 45(4):124-129. (in Chinese)
[25] 任雪斌, 徐静怡, 杨新宇, 等.基于Bayes网络的高维感知数据本地隐私保护发布[J]. 中国科学:信息科学, 2019, 49(12):1586-1605. REN X B, XU J Y, YANG X Y, et al. Bayes network-based high-dimensional crowdsourced data publication with local differential privacy[J]. Scientia Sinica(Informations), 2019, 49(12):1586-1605. (in Chinese)
[26] 肖彪, 闫宏强, 罗海宁, 等. 基于差分隐私的贝叶斯网络隐私保护算法的改进研究[J]. 信息网络安全, 2020, 20(11):75-86. XIAO B, YAN H Q, LUO H N, et al. Research on improvement of Bayesizan network privacy protection algorithm based on differential privacy[J]. Information Network Security, 2020, 20(11):75-86. (in Chinese)
[27] 马苏杭, 龙士工, 刘海, 等.面向高维数据发布的个性化差分隐私算法[J].计算机系统应用, 2021, 30(4):131-138. MA S H, LONG S G, LIU H, et al. Personalized differential privacy algorithm for high-dimensional data publishing[J]. Computer Systems & Applications, 2021, 30(4):131-138. (in Chinese)
[28] 陈思阳. 改进贝叶斯网络的个性化隐私数据发布方法[J]. 软件导刊, 2021, 20(9):213-216. CHEN S Y. Personalized privacy data publishing method based on improved Bayesian network[J]. Software Guide, 2021, 20(9):213-216. (in Chinese)
[29] 洪金鑫, 吴英杰, 蔡剑平, 等. 基于属性分割的高维二值数据差分隐私发布[J]. 计算机研究与发展, 2022, 59(1):182-196. HONG J X, WU Y J, CAI J P, et al. Differentially private high-dimensional binary data publication via attribute segmentation[J]. Journal of Computer Research and Development, 2022, 59(1):182-196. (in Chinese)
[30] MCSHERRY F, TALWAR K. Mechanism design via differential privacy[C]//Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. Washington D. C., USA:IEEE Press, 2007:94-103.
[31] PEARL J. Probabilistic reasoning in intelligent systems:networks of plausible inference[J]. Decision Support Systems, 1992, 8(1):73-75.
[32] TSYBAKOV A B. Introduction to nonparametric estimation[M]. Berlin, Germany:Springer, 2009.
[33] CHICKERING D M, MEEK C, HECKERMAN D. Large-sample learning of Bayesian networks is NP-Hard[J]. Journal of Machine Learning Research, 2004, 5:1287-1330.
[34] CHOW C K, LIU C N. Approximating discrete probability distributions with dependence trees[J]. IEEE Transactions on Information Theory, 1968, 14(3):462-467.

选择文件类型/文献管理软件名称

选择包含的内容