徐 春 李广原

（广西师范学院计算机与信息工程学院，广西 南宁 530023）

几种隐私数据挖掘算法研究进展

徐 春 李广原

（广西师范学院计算机与信息工程学院，广西 南宁 530023）

隐私数据挖掘是数据挖掘的一个重要研究方向，它旨在研究在数据挖掘过程中如何保护私有的和敏感的数据不被泄露。文章阐述几种常用的隐私数据挖掘算法，分析它们的技术特点，文末对几种隐私数据挖掘技术进行总结与展望。

隐私数据挖掘；匿名算法；扰动算法；安全多方计算

1 引言

当今世界，随着信息技术的进步与发展，网络的广泛普及与应用，各种机构产生大量的数据。随着数据的剧烈增长，各种数据分析工具应运而生，数据挖掘是一种先进的数据分析工具，数据挖掘是从海量的数据中挖掘潜在的有意义的模式的过程。数据挖掘的主要任务包括关联挖掘、聚类分析、分类、序列模式挖掘、预测和离群点挖掘等。而挖掘的结果则可以用于商业决策。然而，隐私在数据挖掘中已日益成为一个重要的问题。对敏感信息的保护对于许多机构，特别是商业机构来说是一个非常重要的问题，这些机构在和外界进行商业活动时，都不愿意透露自己的商业秘密。为此，要在数据挖掘中保护隐私数据，隐私数据挖掘就是一种要在数据挖掘中保护隐私或敏感的数据的挖掘范型，它是数据挖掘的一个重要研究方向。鉴于隐私数据挖掘内容比较广泛，本文仅对几种目前常用的隐私数据挖掘算法进行阐述，分析每种算法的技术特点，并对隐私数据挖掘技术进行展望。

2 隐私数据挖掘算法

2.1 匿名算法

尽管数据挖掘是潜在有用的，但很多数据拥有者不愿意提供自己的数据给别人以对数据进行挖掘，因为他们担心其中的敏感信息会被暴露。匿名是一种能够在信息传输过程中对于需要保护的数据不容易为外界所识别的技术。一种常用的方法是 k-匿名算法[1]。在 k-匿名表中，如果数据集中每一项记录至少和同一数据集中的k-1项记录不能加以区分，那么数据集就称为k-匿名的。虽然k-匿名能够保护作为个体出现的信息，但当遇到均匀和具有背景知识攻击时，它不能够有效保护个体属性不被泄露。为此，人们提出了新的算法，文献[2]提出一种 l-多样性模型，等价类被称为 l-多样性是指在敏感属性中至少具有l个以上表示良好的值。由于敏感属性缺少多样性，因而k-匿名允许强的攻击，所以相对于k-匿名来说，l-多样性具有优势。然而，l-多样性也存在一些缺陷[3]：要获取l-多样性可能较难而且可能是不必要的，此外，它不足以阻止属性泄露。于是，人们又提出了扩展的模型t-closeness[4]，即如果在一个等价类中，一个类的一个敏感属性的分布与整个表中属性分布之间的距离不超过一个阈值 t时，那么这个等价类是t-closeness。如果在一个数据表中，所有等价类都是 t-closeness，则称这个表是 t-closeness[5]。在对匿名算法进行研究当中，人们提出了不少有效的算法，比如，文献[6]提出一种技术试图解决在数据挖掘中受到常见的一些攻击，这些攻击是针对基于匿名的数据挖掘和数据发布进行的。而这种技术使用了k-匿名和l-多样化方法。为解决k-匿名和 l-多样化存在的问题，文献[5]提出一个新的隐私概念，在一个表中分布敏感属性的值以避免属性泄露问题。文献[7]提出一种关联规则隐藏的算法，它是通过隐藏那些支持特定敏感规则的事务来实现的。文献[8]也提出了隐藏关联规则挖掘算法，它是隐藏规则而不是改变实体，基本方法是通过系统管理员指定一些敏感规则，在对关联规则挖掘时，这些敏感规则将不会被发现，而非敏感规则都会被发现。关联规则隐藏算法主要采用启发式方法，基于边界的方法和精确算法[9]。文献[10]研究健康隐私数据的挖掘问题，它利用了k-匿名和l-多样性技术来保护多敏感属性，以前研究表明，k-匿名可以扩展到多敏感属性但 1-多样性不行，采用两者结合的技术是可行的。文献[11]试图解决在面临诸如记录链接攻击和属性链接攻击时的隐私数据保护问题。文献[12]提出一种方法，让数据使用者能够对匿名数据进行一些特性描述，作为一些分类问题的一种特定的需求，并提出一种启发式算法能把用户指定的需求融合在普通的算法中去。

2.2 扰动算法

数据扰动算法最先是由 Agrawal提出来的一种通用的隐私保护数据挖掘技术。每一个数据项被随机地加入了噪声数据，这些噪声数据满足高斯分布。数据扰动包括一系列技术，如对原始数据进行数据添加、对数据进行相乘、矩阵相乘、k-匿名、微聚集、分类数据扰动、数据交换、重复抽样等[13]。数据扰动面临的挑战是在数据保护和数据可用之间进行平衡，以取得一个理想的挖掘效果。

数据扰动主要是在数据发布之前给个体的数据值加入扰动数据从而达到隐私保护的目的。目前，在隐私保护数据挖掘中，主要采用两种数据扰动的方法，一种是给原始数据添加上一些数据，另一种是对数据进行相乘。文献[14]研究了通过缩短非负矩阵因数分解和稀疏约束相结合的数据扰动技术。文献[15]提出一个基于单奇异值分解的隐私保护算法，通过实验证明该算法在保护隐私数据的前提下保证挖掘达到一定的性能。文献[16]在对数据进行预处理阶段，先采用单奇异值分解和稀疏单奇异值分解的方法对数据的特征进行抽取以减少数据的维度，然后提出各种隐私的度量方法用来衡量原始数据集和经过扰动后的数据之间的差别以及隐私保护的程度。文献[17]采用结合各种数据扰动的策略来设计四种隐私保护的策略，这四种策略是属性分解、单奇异值分解、非负矩阵因数分解、离散小波变换。其基本思想是在原始数据集中使用不同的方法对其子集进行数据扰动。实验表明，采用不同的方法进行隐私保护较之单一的方法能够获得更好的隐私挖掘效果。文献[18]提出一个应用决策树学习的隐私保护方法而不失去应有的挖掘精度，该方法使用的是一个抽样的数据，这些抽样数据和原始数据相比，是丢失了部分的信息。算法先把抽样数据转换成一组不真实的数据集，而原始抽样数据不能从这些不真实的数据集中重组生成，同时，可以直接从这些不真实的数据集中建立起精确的决策树。一旦第一个样例被收集了，这种方法就可以应用到数据存储当中，而该方法与其他隐私保护方法是兼容的。文献[19]提出一个可扩展的2阶段由上而下的针对匿名的大规模数据集的专门方法，该方法使用了云模型的MapReduce框架，在每一个阶段，精确地设计一组创新的MapReduce工作，用来以一种高可扩展的方式来完成专门的计算。实验证明，该方法无论在执行的效率上和可扩展性方面都要优于目前的方法。文献[20]处理在数据挖掘中有差别的保护问题，提出一种可直接或间接的差别化保护方法，讨论了如何以一种直接或间接的有差别的决策规则转换成合理的分类规则进行清洗训练数据集和外包数据集，同时提出一种新的度量来评价所提出方法的可用性，并对这些方法进行比较研究。

文献[21]对常用数据相乘的数据扰动技术进行对比研究，这些技术是传统的扰动技术、基于欧氏距离的数据扰动技术和基于投影的扰动技术。它们各有优缺点，传统的扰动技术[22-24]，它们的优点是：可以隐藏原始数据，并能用概括性的统计技术来进行评价。而缺点是：这类技术独立地对每一个数据进行变形失真，所以不能使用基于欧氏距离和内积计算的方法来对扰动的数据进行计算处理，这种失真的数据不能应用到很多的数据挖掘应用。基于欧氏距离的扰动技术[25-27]，它们的优点是：可以应用到各种数据挖掘任务当中。而缺点是：原始数据容易受到攻击。而基于投影的扰动技术[28-30]的优点是：随机投影扰动方法可以把数据投影到低维任意的空间并且可以剧烈地改变数据的原始形式，同时保护了与距离相关的特性。缺点是：挖掘精度会有所损失。数据添加和数据相乘相结合的扰动技术的优点是数据拥有者能够和挖掘者共同分享数据，能够获得精确的聚类结果而不用关心分割了数据稳私。

2.3 安全多方计算

Internet和分布式计算为多方互相协作解决一个问题提供了平台，安全多方计算就是确保在这样的一个环境下以一种安全的方式联合攻关。概括地说，安全多方计算是解决一组互不信任的参与方之间保护隐私的协同计算问题，安全多方计算要确保各自输入的独立性，其他方不知道对方输入的隐私数据，但能够保证输出结果的正确性。安全多方计算的目的在于确保多方能够以一个安全的方式来完成一个分布式计算任务。安全多方计算最基本的特点是[31]：

（1）输入的隐私性：没有任何一方能够从它规定的输出中获取更多的信息，能够从其他方输入中得到信息只能从输出中推导出。

（2）正确性：每一方都得到的结果应该保证其是正确的。

（3）输入的独立性：破坏方选择自己的输入是必须独立于诚实方的输入来进行的。

（4）保证输出的正确交付：破坏方不能阻止诚实方获取它们的输出。

（5）公平性：当且仅当诚实方获取它们的输出，破坏方也应该获得到它们的输出。

文献[32]是一篇有关安全多方计算的综述文章，主要阐述安全多方计算的基本范型和概念，并且论述构建一个高效的协议时所面临的困难以及有效性问题。文献[33]研究各种有效的基本安全建造模块，比如快速安全矩阵乘法、安全点积、安全矩阵求逆。文献[34]提出一种安全多方多数据排序协议，这种协议和任何特定的加密算法没有关联，这种协议在半诚实模型中是正确的和安全的。也提出一种基于安全多方求和协议和安全多方多数据排序协议来解决隐私序列模式挖掘问题，并对此问题的解决进行简单的分析。文献[35]给出一个在零丢失概率情况下的计算安全求和的协议。文献[36]给出了在半诚实的对抗模型以及强大的非破坏的恶意模型下的协议。虽然协议是受安全求和的启发，但它们没有受到象安全求和遇到的一些问题所困扰。在分布式隐私挖掘中，为了给网络结点分配标识符，必须利用有效的算法以使标识符是匿名的。在文献[37]中，安全求和允许各方合力对各个输入进行求和同时避免暴露各自的输入，算法提供允许在安全求和之上共享简单的信息，但不能共享复杂的信息。文献[38]论述了一个安全求和函数，这个函数在数据挖掘中得到广泛应用并且能够解释安全多方计算的复杂性。文献[39]提出一些有效的算法来为网络结点分配标识符（ID号），标识符是匿名的，这是采用非集中授权的分布式计算随机产生的，主要的算法是基于为匿名共享数据而导致为有效共享复杂数据的方法。文献[40]则给出一个有效算法，这个算法是共享建立在安全求和基础上的简单整数。算法采用递归的方式来产生匿名ID的分配。

3 结束语

本文对几种重要的隐私数据挖掘技术进行综述，匿名算法是一种重要的隐私数据挖掘技术，它能够有效地隐藏原始数据以避免敏感信息泄露。数据匿名技术还有一些值得研究的课题，比如多个敏感属性的匿名，非均匀数据的匿名等。数据扰动是另一种重要的隐私保护数据挖掘技术，对原始数据进行数据添加和对数据进行相乘是两种主要的数据扰动技术，在安全多方计算中采用的协议是一个重要的问题，加密协议对于安全计算可以获得一个较好的效果。今后，研究有效的安全技术和有效的协议仍是安全多方计算的重要研究方向，而这些研究与哪些信息泄露是被允许的而哪些不能被接受是有关联的。

隐私保护是一个复杂的社会问题，有效的隐私保护不仅仅与技术有关，它还涉及到政策、法规的制订，还可能涉及到人的心理学等。而计算机及相关信息技术对于隐私保护只能够在技术层面上起到一定的保护措施，但要真正获得一个完好的隐私保护效果，还需要政府和各行业的通力合作。

[1] P.Samarati and L.Sweeney. Protecting Privacy When Disclosing Information: k-Anonymity and Its Enforce-ment through Generalization and Suppression[M].Technical Report SRICSL-98-04,1998.

[2] A.Machanavajjhala,J. Gehrke,et al..l-Diversity:Pri-vacy beyond k-Anonymity[M].Proceeding of ICDE,April 2006.

[3] Ashwin Machanavajihala,Johannes Gehrke Daniel Kifer, Muthuramakrishnan Venkitasubramaniam.ℓ-Diversity: Privacy Beyond K-Anonymity[M].Department of Computer Science, Cornell University.

[4] R. C. Wong, J. Li, A. W. Fu, et a1. (α,k)-Anonymity: An Enhaned k-Anonymity Model for Privacy-Preserving Data Publishing[J].In:Proceedings of the 12th ACM SIGKDD, ACM Press, New York,2006:754-759.

[5] Ninghui Li Tiancheng Li,Suresh Venkatasubramanian, -Closeness: Privacy Beyond k-Anonymity and l-diversity[J]. ICDE, 2007:106-115.

[6] Hamza,Nermin,and Hesham A.Hefny.Attacks on anonymization -based privacy-preserving: a survey for data mining and data publishing.Journal of Information Security,2013(4):101.

[7] Dr.R.Sugumar,Dr.A. Rengarajan, M.Vijayanand. Extending K-Anonymity to Privacy Preserving Data Mining Using Association Rule Hiding Algorithm.International Journal of Advanced Research in Computer Science and Software Engineering[J].Volume 2,Issue 6, June 2012.

[8] Dhanalakshmi.M,Siva Sankari.E.Privacy Preserving Data Mining Techniques-Survey[M].IEEE Information Communication and Embedded Systems (ICICES),2014.

[9] A.Evfimievski,R.Srikant, R. Agrawal and J.Gehrke, Privacy Preserving Mining of Association Rules[J].SIGKDD,2002. 217-228.

[10] Gal,Tamas S., Zhiyuan Chen, and Aryya Gangopadhyay. A privacy protection model for patient data with multiple sensitive attributes[J].International Journal of Information Security and Privacy (IJISP),2008,2(3):28-44.

[11] Mahesh, R., and T. Meyyappan. Anonymization technique through record elimination to preserve privacy of published data[J].Pattern Recognition, Informatics and Mobile Engineering (PRIME),2013 International Conference on. IEEE, 2013.

[12] Hongwei Tian,Weining Zhang.Privacy-Preserving Data Publishing Based On Utility Specification[M].IEEE,2013.

[13] Lokesh Patel,Prof.Ravindra Gupta. A Survey of Perturbation Technique For Privacy-Preserving of Data[M].International Journal of Emerging Technology and Advanced Engineering. Volume 3, Issue 6, June 2013.

[14] Kabir,S.M.A,Youssef, A.M. Elhakeem,.On Data Distortion for Privacy Preserving Data Mining[J].Canadian Conference on Electrical and Computer Engineering,2007.CCECE,2007: 308-311.

[15] S.Xu,J.Zhang,D.Han and J.Wang.Singular value decomposition based data distortion strategy for privacy protection[J]. ACM Journal of Knowledge and Information Systems,2006, 10(3):383-397.

[16] Jahan, Narsimha and Rao.Data perturbation and feature selection in preserving privacy[J].Ninth International Conference on Wireless and Optical Communications Networks (WOCN),2012:1-6.

[17] Bo Peng, Xingyu Geng,Jun Zhang.Combined data distortion strategies for privacy-preserving data mining[J].Proceeding of the IEEE International Conference on Advanced Computer Theory and Engineering (1CACTE),2010.

[18] Pui K. Fong and Jens H. Weber-Jahnke, Senior Member. Privacy Preserving Decision Tree Learning Using Unrealized Data Sets[J].Proceeding of the IEEE Transactions On Knowledge And Data Engineering,2012,24(2):353-364.

[19] Xuyun Zhang,Laurence T.Yang,Senior Member. A Scalable Two-Phase Top-Down Specialization Approach for Data Anonymization using MapReduce on Cloud[C].Proceeding of the IEEE Transactions On Parallel And Distributed Systems, 2013.

[20] Sara Hajian ,Josep Domingo-Ferrer.A Methodology for Direct and Indirect Discrimination Prevention in Data Mining[J].Proceeding of the IEEE Transactions on Knowledge and Data Engineering,2013,25(7):1445-1459.

[21] Bhupendra Kumar Pandya,Umesh kumar Singh,Keerti Dixit. A Comparative Study of Multiplicative Data Perturbation Techniques for Privacy Preserving Data Mining[J]. International Journal of Advanced Research in Computer Engineering & Technology,2015,4(4):4.

[22] B. Pandya,U.K.Singh,K Bunkar and K.Dixit.An Overview of Traditional Multiplicative Data Perturbation[J]. International Journal of Advanced Research in Computer Science and Software Engineering,2012,2(3):424-428.

[23] B.Pandya,U.K.Singh and K.Dixit.Effectiveness of Multiplicative Data Perturbation forPerturbation for Privacy Preserving Data Mining[J].International Journal of Advanced Research in Computer Science,2014,5(6): 112-115.

[24] B.Pandya,U.K.Singh and K.Dixit.Performance of Multiplicative Data Perturbation for Perturbation for Privacy Preserving Data Mining[J].International Journal for Research in Applied Science and Engineering Technology,2014(VII):2.

[25] B.Pandya,U.K.Singh and K. Dixit.An Analysis of Euclidean Distance Presrving Perturbation for Privacy Preserving Data Mining[J].International Journal for Research in Applied Science and Engineering Technology,2014(x):2.

[26] B. Pandya,U.K.Singh and K.Dixit.Performance of Euclidean Distance Presrving Perturbation for K-Means Clustering[J]. International Journal of Advanced Scientific and Technical Research,2014,5(4):282-289.

[27] B.Pandya,U.K.Singh and K.Dixit.Performance of Euclidean Distance Presrving Perturbation for K-Nearest Neighbour Classification[J].International Journal of Computer Application,2014,105(2):34-36.

[28] B. Pandya,U.K.Singh and K. Dixit. A Study of Projection Based Multiplicative Data Perturbation for Privacy Preserving Data Mining[J].International Journal of Application or Innovation in Engineering and Management,2014,3 (11):180-182.

[29] B.Pandya,U.K.Singh and K.Dixit.An Analysis of Projection Based Multiplicative Data Perturbation for K-Means Clustering[J].International Journal of Computer Science and Information Technologies,2014,5(6):8067-8069.

[30] B.Pandya,U.K.Singh and K.Dixit.An Evaluation of Projection Based Multiplicative Data Perturbation for K-Nearest Neighbour Classification[J].International Journal of Science and Research,2014,3(12):681-684.

[31] Yehuda Lindell and Benny Pinkas.Secure Multiparty Computation for Privacy-Preserving Data Mining[J].The Journal of Privacy and Confidentiality,2009:62-63.

[32] Yehuda Lindell, and Benny Pinkas. Secure Multiparty Computation for Privacy-Preserving Data Mining[J].The Journal of Privacy and Confidentiality,2009:59-98.

[33] Teo, S.G. Lee,V. Shuguo Han.A Study of Efficiency and Accuracy of Secure Multiparty Protocol in Privacy-Preserving Data Mining[J].26th International Conference on Advanced Information Networking and Applications Workshops (WAINA),2012:85-90.

[34] Liu Wen., Luo Shou-shan, Wang Yong-bin, Jiang Zhen-tao. A Protocol of Secure Multi-party Multi-data Ranking and Its Application in Privacy Preserving Sequential Pattern Mining[J].2011 Fourth International Joint Conference on Computational Sciences and Optimization (CSO),2011: 272-275.

[35] Pathak,F.A.N.Pandey,S.B.S.Distributed changing neighbors k-secure sum protocol for secure multiparty computation[J]. Nirma University International Conference on Engineering (NUiCONE),2013:1-3.

[36] Hasan,O.,Bertino,E.;Brunie,L.Efficient privacy preserving reputation protocols inspired by secure sum, Privacy Security and Trust (PST)[J].2010 Eighth Annual International Conference on,2010:126-133.

[37] Akheel Mohammed,Sajjad Ahmed Md Ayesha Confidentiality And Anonymity Strengthening in Computational Sevices IJRRECS[J].Volume-1Issue-6, 2013:1006-1011.

[38] Swathi,P.Jyothi,and Anil Kumar(2014).Assigning Privacy Ids For Each Data That Have Been Sharing In Wireless Networks[J].International Journal of Communication Network and Security (IJCNS) ISSN,2014(2):3.

[39] Ayswarya R Kurup, Simi Lukose. Security Enhanced Privacy Preserving Data sharing With Random ID Generation[M].IJSRE Volume 2 Issue 8,2014.

[40] Larry A. Dunning,And Ray Kresman.Privacy Preserving Data Sharing With Anonymous ID Assignment[J].IEEE Transactions on Information Forensics and Security,2013(8):2.

Advances in the study of several kinds of privacy preservation algorithms in data mining

Privacy preserving data mining is one of the important directions in data mining, it aim at how to protect the privacy or sensitive information from leaking in the process of data mining, in this paper, a survey of several privacy preservation algorithms in data mining is presented, and we also analyze the characteristics of their technology, conclusions are outlined in the end of this paper,

Privacy preserving data mining; anonymization algorithm; perturbation algorithms; secure multiparty computation

TP311

A

1008-1151(2016)07-0031-04

2016-06-11

广西自然科学基金项目（2014GXNSFAA118388）,广西高校科研项目（YB2014237)。

徐春（1987－），女，安徽合肥人，广西师范学院计算机与信息工程学院硕士研究生，研究方向为数据挖掘；李广原（1969－），男（壮族），广西上林人，广西师范学院计算机与信息工程学院副教授，博士，研究方向为数据挖掘、智能信息处理。