具备隐私信息保护能力的学习器研究

doi:10.11959/j.issn.2096-109x.2016.00062

摘要/Abstract

摘要：

随着数据挖掘技术在现实生活的日益发展，对信息数据的共享提出了更高的要求，隐私泄露问题变得日趋严重。设计具有隐私信息保护能力的学习器成为数据挖掘中的一个重要的问题。在已有研究成果的基础上，简要回顾了隐私保护学习器的发展现状，对隐私保护关键技术及学习器模型进行了分析概述，针对近年来国内外关于隐私保护学习器的研究成果进行了归纳总结。

关键词: 隐私保护, 数据挖掘, 学习器

Abstract:

With the increasing development of data mining,more and more data mining methods need to be carried out on the privacy data,which leads to the serious problem of privacy disclosure.Therefore,Study of privacy-preserving learning machines is becoming a key data mining topic.Current privacy-preserving learning machines were surveyed and analyzed,including their basic ideas and their learning models.

Key words: privacy preservation, data mining, learning machine

中图分类号:

TP181

蒋惯樟,王士同. 具备隐私信息保护能力的学习器研究[J]. 网络与信息安全学报, 2016, 2(6): 22-31.

Yi-zhang JIANG,Shi-tong WANG. Research on privacy-preserving learning machines[J]. Chinese Journal of Network and Information Security, 2016, 2(6): 22-31.

图/表 7

表1

表2

表3

表4

图1

图2

图3

参考文献 63

[1]	刘忠宝，王士同 . 面向大规模数据的隐私保护学习机[J]. 电子科技大学学报, 2013,42(2):272-276.
	LUI Z B , WANG S T . Privacy preserving learning machine for large scale datasets[J]. Journal of University of Electronic Science and Technology of China, 2013,42(2):272-276.
[2]	AGRAWAL R , SRIKANT R . Privacy-preserving data mining[J]. ACM Sigmod Record, 2000,29 (2):439-450.
[3]	AGGARWAL C C , PHILIP S Y . A condensation approach to pri-vacy preserving data mining[M]// Advances in Database Technology. Berlin Heidelberg: Springer, 2004:183-199.
[4]	MOSKOWITZ L , CHANG I S . A decision theoretical based system for information downgrading[C]// The 5th Joint Conference on In-formation Sciences.c 2000.
[5]	CHANG L W , MOSKOWITZ I S . An integrated framework for database privacy protection[C]// The 14th Working Conference on Database Security:Data and Application Security,Development and Directions.c 2000:161-172.
[6]	GREENBERG B G , KUEBLER R R J , ABERNATHY J R , et al. Application of the randomized response technique in obtaining quantitative data[J]. Journal of the American Statistical Association, 1971,66 (334):243-250.
[7]	GOMATAM S , KARR A F , SANIL A P . Data swapping as a deci-sion problem[J]. Journal of Official Statistics, 2005,21 (4):635-655.
[8]	RIZVI S J , HARITSA J R . Maintaining data privacy in association rule mining[C]// The 28th VLDB Conference.c 2002:682-693.
[9]	KARGUPTA H , DATTA S , WANG Q , et al. On the privacy pre-serving properties of random data perturbation techniques[C]// IEEE International Conference on Data Mining,IEEE.c 2003:99-106.
[10]	SAYGIN Y , VERYKIOS V S , ELMAGARMID A K . Privacy pre-serving association rule mining[C]// ACM Siggraph Symposium on Geometry Processing.c 2002:97-115.
[11]	CHEN K , LIU L . Privacy preserving data classification with rota-tion perturbation[C]// The 5th IEEE International Conference on Data Mining (ICDM'OS).c 2005:589-592.
[12]	EVFIMIEVSKI A , SRIKANT R , AGRAWAL R , et al. Privacy preserving mining of association rules[J]. Information Systems, 2004,29 (4):343-364.
[13]	WARNER S L . Randomized response:a survey technique for eliminating evasive answer bias[J]. Journal of the American Statistical Association, 1965,60 (309):63-69.
[14]	DU W , ZHAN Z . Using randomized response techniques for pri-vacy-preserving data mining[C]// The 9th ACM Sigkdd Interna-tional Conference on Knowledge Discovery and Data Mining.c 2003:505-510.
[15]	DU W , ZHAN Z . Building decision tree classifier on private data[C]// IEEE International Conference on Privacy,Security and Data Mining.c 2002:1-8.
[16]	PINKAS B . Cryptographic techniques for privacy-preserving data mining[J]. ACM Sigkdd Explorations Newsletter, 2002,4 (2):12-19.
[17]	YAO C C . How to generate and exchange secrets[C]// Annual Symposium on Foundations of Computer Science.c 1986:162-167.
[18]	CHAUM D , CREPEAU C , DAMGARD I . Multiparty uncondition-ally secure protocols[M]. Berlin Heidelberg: Springer, 1988:462-462.
[19]	GOETHALS B , LAUR S , LIPMAA H , et al. On private scalar product computation for privacy-preserving data mining[C]// Inter-national Conference in Information Security ＆ Cryptology.c 2004:104-120.
[20]	VAIDYA J , CLIFTON C . Privacy-preserving k-means clustering over vertically partitioned data[C]// The 9th ACM Sigkdd Interna-tional Conference on Knowledge Discovery and Data Mining.c 2003:206-215.
[21]	YAO A C . Protocols for secure computations[C]// Annual Sympo-sium on Foundations of Computer Science.c 1982:160-164.
[22]	LINDELL Y , PINKAS B . Secure multiparty computation for pri-vacy-preserving data mining[J]. ournal of Privacy and Confidenti-ality, 2009,1 (1):59-98.
[23]	FEIGENBAUM J , ISHAI Y , MALKIN T , et al. Secure multiparty computation of approximations[J]. Lecture Notes in Computer Science, 2002,2 (3):927-938.
[24]	CLIFTON C , KANTARCIOGLU M , VAIDYA J , et al. Tools for privacy preserving distributed data mining[J]. ACM SIGKDD Ex-plorations Newsletter, 2002,4 (2):28-34.
[25]	LIU Y H , WEI Z J . Private-preserving naive bayesian classifica-tion[J]. Journal of Information Engineering University, 2003,4 (1):86-89.
[26]	SWEENEY L . K-anonymity:a model for protecting privacy[J]. International Journal of Uncertainty,Fuzziness and Knowl-edge-based Systems, 2012,10 (5):557-570.
[27]	SWEENEY L . Achieving k-anonymity privacy protection using generalization and suppression[J]. International Journal of Uncer-tainty,Fuzziness and Knowledge-based Systems, 2012,10 (5):571-588.
[28]	MIKLAU G , SUCIU D . A formal analysis of information disclosure in data exchange[C]// ACM Sigmod International Conference on Management of Data.c 2004:575-586.
[29]	YAO C , WANG X S , JAJODIA S . Checking for k-anonymity viola-tion by views[C]// The 31th International Conference on Very Large Data Bases.c 2005:910-921.
[30]	XIAO X , TAO Y . Dynamic anonymization:accurate statistical analysis with privacy preservation[C]// The ACM Sigmod Interna-tional Conference on Management of Data.c 2008:107-120.
[31]	MACHANAVAJJHALA A , KIFER D , ABOWD J , et al. Privacy:theory meets practice on the map[C]// IEEE 29th International Conference on Data Engineering (ICDE).c 2008:277-286.
[32]	DALVI N , SUCIU D . Answering queries from statistics and prob-abilistic views[C]// The 31th International Conference on Very large Data Bases.c 2005:805-816.
[33]	WONG R C , LI J , FU A W , et al. (a,k)-anonymity:an enhanced k-anonymity model for privacy preserving data publishing[C]// The 12th ACM Sigkdd International Conference on Knowledge Dis-covery and Data Mining.c 2006:754-759.
[34]	LI J , WONG R , FU A , et al. Achieving k-anonymity by clustering in attribute hierarchical structures[M]// Data Warehousing and Knowledge Discovery. Berlin Heidelberg: Springer, 2006:405-416.
[35]	AGGARWAL G , FEDER T , KENTHAPADI K , et al. Approxima-tion algorithms for k-anonymity[C]// The 8th Latin American Con-ference on Theoretical Informatics.c 2010:81-93.
[36]	LEFEVRE K , DEWITT D J , RAMAKRISHNAN R . Incognito:efficient full-domain k-anonymity[C]// ACM Sigmod International Conference on Management of Data.c 2005:49-60.
[37]	孙立 . 基于隐私保护技术的支持向量机研究[D]．北京：中国农业大学, 2014.
	SUN L . Research on privacy-preserving support vector machine[D]. Beijing:China Agricultural University, 2014.
[38]	张战成 . 基于统计学习的协作分类与隐私保护方法及应用研究[D]. 无锡：江南大学, 2011.
	ZHANG Z C . PCollaborative classification based on statistical learning and its application to privacy-preserving[D]. Wuxi:Ji-angnan University, 2011.
[39]	周水庚，李电，陶宇飞，等．面向数据库应用的隐私保护研究综述[J]. 计算机学报, 2009,32(5):847-861.
	ZHOU S G , LI F , TAO Y F , et al. Privacy preservation in database applications:a survey[J]. Chinese Journal of Computers, 2009,32(5):847-861.
[40]	PEI J , XU J , WANG Z , et al. Maintaining k-anonymity against incremental updates[C]// International Conference on Scientific and Statistical Database Management.IEEE Computer Society.c 2007:5.
[41]	AGGARWAL C C . On k-anonymity and the curse of dimensional-ity[C]// International Conference on Very Large Data Bases.c 2005:901-909.
[42]	DU Y , XIA T , TAO Y , et al. On multidimensional k-anonymity with local recoding generalization[C]// IEEE International Conference on Data Engineering.c 2007:1422-1424.
[43]	MEYERSON A , WILLIAMS R . On the complexity of optimal k-anonymity[C]// The 23th ACM Sigmod-sigact-sigart Symposium on Principles of Database Systems.c 2004:223-228.
[44]	EMAM K E , DANKAR F K . Protecting privacy using k-anonymity[J]. Journal of the American Medical Informatics Association, 2008,15 (5):627-637.
[45]	MACHANAVAJJHALA A , KIFER D , GEHRKE J , et al. L-diversity:privacy beyond k-anonymity[J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2007,1 (1):3.
[46]	ZHOU B , PEI J . The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood at-tacks[J]. Knowledge and Information Systems, 2011,28 (1):47-77.
[47]	LI N , LI T , VENKATASUBRAMANIAN S . T-closeness:privacy beyond k-anonymity and l-diversity[C]// The 23th International Conference on Data Engineering (ICDE).c 2007:106-115.
[48]	刘晓红 . 隐私保护支持向量机算法研究[D]. 山东：山东科技大学, 2011.
	LIU X H . Study on the algorithms of privacy preserving support vector machine[D]. Shandong:Shandong University of Science and Technology, 2011.
[49]	李光 . 分类挖掘中的隐私保护问题研究[D]. 哈尔滨：哈尔滨工业大学, 2011.
	LI G . Research on the privacy protection in classification mining[D]. Harbin:Harbin Institute of Technology, 2011.
[50]	王健 . 基于隐私保护的数据挖掘若干关键技术研究[D]. 上海：东华大学, 2011.
	WANG J . Study of several key issues on data mining based on pri-vacy-preserving technology[D]. Shanghai:Donghua University, 2011.
[51]	邓乃扬，田英杰 . 支持向量机：理论、算法与拓展[M]. 北京: 科学出版社, 2009.
	DENG N Y , TIAN Y J . New method in data mining:support vector machine[M]. Beijing: China Science Press, 2004:5-16.
[52]	YU H , VAIDYA J , JIANG X Q . Privacy-preserving SVM classifi-cation on vertically partitioned data[J]. Journal of Jiamusi Uni-versity(Natural Science Edition), 2011(3):647-656.
[53]	LEE Y J , MANGASARIAN O L . RSVM:reduced support vector machines[C]// The 1st SIAM International Conference on Data Mining.c 2001:57-64.
[54]	LIN K M , LIN C J . A study on reduced support vector machines[J]. IEEE Transactions on Neural Network, 2003,45 (2):199-204.
[55]	YU H , JIANG X Q , VAIDYA J . Privacy-preserving SVM using nonlinear kernels horizontally partitioned data[C]// The ACM Sym-posium on Applied Computing.c 2006:603-610.
[56]	MANGASARIAN O L , WILD E W . Privacy-preserving classi-fication of horizontally partitioned data via random kernels[C]// The International Conference on Data Mining.c 2008:473-479.
[57]	张战成，王士同，钟富礼 . 具有隐私保护功能的协作式分类机制[J]. 计算机研究与发展, 2011,48(6):1018-1028.
	ZHANG Z C , WANG S T , CHUNG F L . Collaborative classifica-tion mechanism for privacy-preserving[J]. Journal of Computer Research and Development, 2011,48(6):1018-1028.
[58]	胡文军 . 关于模式识别中大样本分类技术的几个关键问题研究[D]. 无锡：江南大学, 2012
	HU W J . The study of several key issues on large data sets classifi-cation techniques in pattern recognition[D]. Wuxi:Jiangnan Univer-sity, 2012.
[59]	胡文军，王士同 . 隐私保护的 SVM 快速分类方法[J]. 电子学报, 2012,40(2):280-286
	HU W J , WANG S T . Fast classification approach of support vector machine with privacy preservation[J]. Acta Electronica Sinica, 2012,40(2):280-286.
[60]	VAIDYA J , YU H , JIANG X . Privacy-preserving SVM classifica-tion[J]. Knowledge and Information Systems, 2008,14 (2):161-178.
[61]	张学工 . 关于统计学习理论与支持向量机[J]. 自动化学报, 2000,26(1):32-42.
	ZHANG X G . Introduction to statistical learning theory and support vector machines[J]. Acta Automatica Sinica, 2000,26(1):32-42.
[62]	刘向东，陈兆乾 . 一种快速支持向量机分类算法的研究[J]. 计算机研究与发展, 2004,41(8):1327-1332.
	LIU X D , CHEN Z Q . A fast classification algorithm of support vector machines[J]. Journal of Computer Research and Develop-ment, 2004,41(8):1327-1332.
[63]	汤琳，何丰 . 隐私保护的数据挖掘方法的研究[J]. 计算机技术与发展, 2011,21(4):156-159.
	TANG L , HE F . Research on privacy-preserving data mining method[J]. Computer Technology and Development, 2011,21(4):156-159.

隐私保护技术	隐私保护度	计算开销	数据缺失	数据依赖性	通信开销
基于数据失真的技术	中	低	高	高	低
基于密码学的技术	高	高	低	低	高
基于限制发布的技术	高	中	中	低	低

隐私保护技术	优点	缺点	代表技术	主要应用
基于数据失真的技术	计算开销小；实现简单	数据失真；严重依赖数据，不同数据需设计不同的算法	随机扰动随机应答数据交换阻塞凝聚	各种数据挖掘：关联规则挖掘；关联规则隐藏；决策树分类器构建等
				分布式下的各种数据挖掘和发布操作：
基于密码学的技术	数据真实、无缺失；高隐私保护度	计算开销、通信开销大；部署复杂、实际应用难度较高	SMC	分布式关联规则挖掘；分布式数据匿名发布；分布式聚类；
				分布式安全计算等
基于限制发布的技术	适用范围广；通用性高；保证真实性；实现简单	一定程度的数据缺失；一定程度的隐私泄露；最优化的数据匿名开销较大	k-匿名l-diversityt-closeness	发布匿名化数据基于：关联规则挖掘；决策树分类器构建等；聚类等

姓名	年龄	性别	邮编	HIV+
Alex	42	男	2140	Yes
John	27	男	3180	Yes
Lily	36	女	2160	No
Tom	23	男	2220	Yes
Alan	47	女	3150	No
Ben	19	男	2180	No
…	…	…	…	…

年龄	性别	邮编	HIV+
[40～50]	男	2k～3k	Yes
[25～30]	男	3k～4k	Yes
[35～40]	女	2k～3k	No
[20～30]	男	2k～3k	Yes
[45～50]	女	3k～4k	No
[15～20]	男	2k～3k	No
…	…	…	…