幾種隱私數據挖掘算法研究進展

徐 春 李廣原

（廣西師范學院計算機與信息工程學院，廣西 南寧 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－），男（壯族），廣西上林人，廣西師范學院計算機與信息工程學院副教授，博士，研究方向為數據挖掘、智能信息處理。