A Differential Private Data Publishing Algorithm via Principal Component Analysis Based on Maximum Information Coefficient

doi:10.3969/j.issn.1671-1122.2020.02.006

Abstract

Abstract:

The privacy and availability of data are important issues of privacy protection. Principal component analysis (PCA) differential privacy can effectively protect the privacy of high-dimensional data and maintain the high availability of data by integrating the dimensionality reduction and noise addition of the principal component of high-dimensional data. The existing principal component analysis differential privacy protection algorithm relies on Pearson correlation coefficient, which can only capture the linear relationship of high-dimensional data in the privacy protection process, and does not consider to optimize the allocation of difference budget on the data set after dimension reduction, resulting in insufficient applicability of the algorithm and low data utility. To this end, a differential private data publishing algorithm (MIC-PCA-DPPD) is proposed via principal component analysis based on maximum information coefficient. The experimental results show that the proposed privacy protection algorithm is suitable for dimensionality maintenance of linear relationships, nonlinear relationships, multi-function relationships, etc. Its principal component dimensionality reduction can achieve efficient raw data information bearing. Compared with the classic differential privacy algorithm and PCA-based PPDP algorithm, the noise added to the data is smaller and the data availability can be effectively maintained, under the same constraint of privacy protection intensity.

Key words: differential privacy, principal components analysis, dimension reduction, data publication

CLC Number:

TP309

PENG Changgen, ZHAO Yuanyuan, FAN Meimei. A Differential Private Data Publishing Algorithm via Principal Component Analysis Based on Maximum Information Coefficient[J]. Netinfo Security, 2020, 20(2): 37-48.

Figures/Tables 8

References 25

[1]	DWORK C.Differential Privacy[C]//Springer. The 33rd International Colloquium on Automata, Languages, and Programming, July 9-16, 2006, Venice, Italy. Berlin: Spinger, 2006: 1-12.
[2]	DWORK C, LEI J.Differential Privacy and Robust Statistics[C]//SIGACT. 41st ACM Symposium on Theory of Computing(STOC 2009), May 31-June 2, 2009, Bethesda, Maryland. New York: ACM, 2009: 371-380.
[3]	HARDT M, ROTH A.Beating Randomized Response on Incoherent Matrices[C]//SIGACT. 44th ACM Symposium on Theory of Computing(STOC 2012), May 19-22, 2012, New York, USA. New York: ACM, 2012: 1255-1268.
[4]	DWORK C, ROTH A.The Algorithmic Foundations of Differential Privacy[J]. Foundations and Trends in Theoretical Computer Science, 2013, 9(3-4): 211-407.
[5]	BLUM A, DWORK C, MCSHERRY F, et al.Practical Privacy: The SULQ Framework[C]//SIGACT. 24th ACM Sigmod-Sigact-Sigart Symposium on Principles of Database Systems(PODS 2005), June 13-15, 2005, Baltimore, Maryland. New York: ACM, 2005: 128-138.
[6]	JIANG Xiacqiang, JI Zhanglong, WANG Shuang, et al.Differential-Private Data Publishing Through Component Analysis[J]. Transactions on Data Privacy, 2013, 6(1): 19-34.
[7]	DWORK C, TALWAR K, THAKURTA A, et al.Analyze Gauss: Optimal Bounds for Privacy-Preserving Principal Component Analysis[C]//SIGACT. 46th ACM Symposium on Theory of Computing(STOC 2014), May 31-June 3, 2014, New York, USA. New York: ACM, 2014: 11-20.
[8]	CHAUDHURI K, SARWATE A D, SINHA K.A Near-Optimal Algorithm for Differentially-Private Principal Components[J]. Journal of Machine Learning Research, 2013, 14(9): 2905-2943.
[9]	KAPRALOV M, TALWAR K.On Differentially Private Low Rank Approximation[C]//SIGACT. 24th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA 2013), January 6-8, 2013, New Orleans, Los Angeles, USA. New York: ACM, 2013: 1395-1414.
[10]	HARDT M, ROTH A.Beyond Worst-Case Analysis in Private Singular Vector Computation[C]//SIGACT. 45th ACM Symposium on the Theory of Computing, June 1-4, 2013, Palo Alto, California, USA. New York: ACM, 2013: 331-340.
[11]	JIANG Wuxuan, XIE Cong, ZHANG Zhihua.Wishart Mechanism for Differentially Private Principal Components Analysis[J]. Computer Science, 2015, 18(VI): 458-473.
[12]	HARDT M, PRICE E.The Noisy Power Method: A Meta Algorithm with Applications[C]//NIPS. Annual Conference on Neural Information Processing Systems 2014, December 8-13, 2014, Montreal, Quebec, Canada. Boston: MIT Press, 2014: 2861-2869.
[13]	HALKON, MARTINSSON P G, TROPP J A. Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions[J]. SIAM Review, 2011, 53(2): 217-288.
[14]	KALAI A, VEMPALA S.Efficient Algorithms for Online Decision Problems[J]. Journal of Computer and System Sciences, 2005, 71(3): 291-307.
[15]	ZHANG Yuxuan, WEI Jianghong, LI Ji, et al.Graph Degree Histogram Publication Method with Node-Differential Privacy[J]. Journal of Computer Research and Development, 2019, 6(3): 508-520.
	张宇轩,魏江宏,李霁,等.点差分隐私下图数据的度直方图发布方法[J]. 计算机研究与发展,2019,6(3):508-520.
[16]	MCSHERRY F.Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis[C]//SIGACT. 2009 ACM SIGMOD International Conference on Management of Data, June 29-July 2, 2009, Providence, Rhode Island, USA. New York: ACM, 2009: 19-30.
[17]	DWORK C.Differential Privacy: A Survey of Results[C]//Springer. 5th International Conference Theory and Applications of Models of Computation, April 25-29, Xi’an, China. Berlin: Spinger, 2008: 1-19.
[18]	DWORK C, MCSHERRY F, NISSIM K, et al.Calibrating Data to Sensitivity in Private Data Analysis[C]// Springer. the 3rd Theory of Cryptography Conference, March 4-7, 2006, New York, USA. Berlin: Springer, 2006: 265-284.
[19]	MCSHERRY F, TALWAR K.Mechanism Design via Differential Privacy[C]//IEEE. 48th Annual IEEE Symposium on Foundations of Computer Science, October 21-23, 2007, Providence, Rhode Island, USA. New York: IEEE, 2007: 94-103.
[20]	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.
[21]	WOLD S.Principal Component Analysis[J]. Chemometrics & Intelligent Laboratory Systems, 1987, 2(1): 37-52.
[22]	TIPPING M E, BISHOP C M.Probabilistic Principal Component Analysis[J]. Journal of the Royal Statistical Society Series B(Statistical Methodology), 1999, 61(3): 611-622.
[23]	MOHAMMED N, CHEN R, FUNG B C M, et al. Differentially Private Data Release for Data Mining[C]//SIGACT. 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 21-24, 2011, San Diego, California, USA. New York: ACM, 2011: 493-501.
[24]	KAISER, H F.The Application of Electronic Computers to Factor Analysis[J]. Educational and Psychological Measurement, 1960, 20(1): 141-151.
[25]	Residential Building Data Set Data Set[EB/OL]. 2018-2-19.