基于差分隱私保護的DPk-medoids聚類算法

高 瑜，田 豐，吳振強

(1.現代教學技術教育部重點實驗室，陜西 西安 710062; 2.陜西師范大學 計算機科學學院，陜西 西安 710062)

基于差分隱私保護的DPk-medoids聚類算法

高 瑜1,2，田 豐2，吳振強1,2

(1.現代教學技術教育部重點實驗室，陜西 西安 710062; 2.陜西師范大學 計算機科學學院，陜西 西安 710062)

聚類分析是數據挖掘中的一個重要研究領域，由于聚類分析能夠發現數據的內在結構并對數據進行更深入的分析或預處理，因此被用于圖像處理、模式識別等諸多領域中。若用戶數據被一些持有大數據集的組織(如醫療機構)利用挖掘工具獲取個人隱私，將可能導致用戶敏感信息面臨泄露的威脅。為此，結合差分隱私的特性，提出了一種基于差分隱私保護的DPk-medoids聚類算法。該算法在每次發布真實中心點之前使用拉普拉斯機制對中心點加噪，再發布加噪之后的中心點，在一定程度上保證了個人隱私的安全性，以及聚類的有效性。真實數據集上的仿真實驗結果表明，提出的聚類算法可以適應規模、維數不同的數據集，當隱私預算達到一定值時，DPk-medoids聚類算法與原始聚類算法的有效性比率范圍可達0.9～1之間。

數據挖掘；隱私保護；差分隱私；k-中心性聚類

1 概 述

數據挖掘中的聚類分析已經廣泛地應用于許多領域，如在Web搜索中由于Web頁面數量巨大，通常是把關鍵詞搜索返回的大量結果通過聚類算法進行分組，以簡潔的方式呈現給用戶。而數據挖掘的對象是存在擁有大量數據的多個組織(如社交網絡、醫療機構、人口普查等)，這樣的組織通常都會存儲大量的用戶敏感信息，在進行數據挖掘時就會引發用戶隱私泄露的問題。該問題可以分為兩方面：一方面，有些信息是在無意識下收集的，比如在汽車保險行業中，通過聚類算法會發現索賠率較高的客戶群，如果這些信息泄露，就會使得保險業增加索賠率較高用戶的保險金額；另一方面，各種數據挖掘方法與工具的不斷完善，為一些用戶提供便捷的手段來獲取他人信息，比如人肉搜索等。

因此需要在隱私保護的前提下進行數據挖掘操作，不僅需要保護數據中的敏感屬性，而且還要將隱私保護方法對挖掘結果的影響程度控制在一定范圍之內[1]。

隱私保護的數據挖掘方法主要考慮數據的分布方式、數據的修改、隱私保護的對象和隱私保護技術幾個方面[2]。傳統隱私保護技術大多基于k-匿名保護模型，這種方法需要特殊的攻擊假設，對k-匿名保護模型而言，后期總會出現一些新型的攻擊方式。比如鏈接攻擊，攻擊者若能拿到兩份數據表，且兩份數據表具有相同的一條屬性，那么攻擊者就可以通過連接數據表推測出用戶的敏感信息。2000年，Yehuda Lindell等[3]提出了隱私保護下的數據挖掘問題，利用ID3算法及其擴展處理干擾后的噪音數據，使其盡可能保持了分類的結果。

2002年，L. Sweeney等[4]提出基于傳統隱私保護k-匿名模式下的數據挖掘算法，利用其中一條記錄與其他k-1條記錄的不可區分性實現隱私保護。2006年，Dework等提出了一種新型的隱私保護模型—差分隱私保護[5-7]方法。該方法不需要關心攻擊者的背景知識假設和具有嚴格的數學定義及隱私證明等優點廣受研究者的歡迎，通過對分析結果添加噪音，從而進行擾動，達到隱私保護的效果。差分隱私下的數據挖掘也得到了部分研究者的重視，通過對數據挖掘中已有算法進行調整和對數據挖掘結果的性能評估，找出數據安全性和模型可用性的平衡[8]。

Avrim Blum等[9]基于SuLQ框架設計了一個差分隱私k-means聚類算法，只需發布每次更新平均值的近似值就不會泄露隱私，整個過程是滿足差分隱私條件。2011年，Dework針對文獻[9]提出了改進算法[10]，主要是隱私預算的分配發生變化。李楊等[1]對Dework提出的IDP-kmeans理論進行驗證，仿真實驗表明，改進后的IDP-kmeans算法比DP-kmeans算法的聚類效果更優，并且實現了對大數據集加入少量隱私預算，達到高隱私保護的目的。Su Dong等[11]提出了實現k-means聚類的非交互式方法的EUGkM算法以及DPLloyd的改進算法。吳偉民等[12]提出了基于差分隱私的DBScan聚類算法，該算法在添加少量的隨機噪音下，能夠得到隱私保護并且保持聚類的有效性。

基于差分隱私保護的k-means聚類方法中，沒有考慮到離群點對聚類的影響。為此，提出了基于差分隱私保護的k-medoids聚類算法，以解決離群點帶來的敏感性問題。該算法通過加入拉普拉斯噪音，實現了對敏感數據的隱私保護。

為驗證該算法的有效性和可行性，對該算法進行了可行性證明和仿真實驗。安全分析和模擬實驗結果均表明，該算法在引入差分隱私保護后可實現數據的可用性和安全性，且不同規模的數據集具有不同的有效性。

2 DPk-medoids算法描述與算法分析

2.1差分隱私的相關定義

即使攻擊者知道某一個數據集除一條記錄之外的其他所有信息，差分隱私保護模型也能保證攻擊者不會通過剩余的這一條記錄從輸出結果中獲得額外信息。所關注的焦點是在聚類過程中如何使得距離公布時的隱私不被泄露。當提交聚類模式查詢時，返回的是經過差分隱私處理后的結果。

定義1[13](差分隱私)：給定相差一條記錄的相鄰兩個數據集D1和D2，Range(A)是隱私挖掘算法A的取值范圍，如果算法A的任意可能輸出結果S(S∈Range(A))滿足式(1)，算法A滿足ε-差分隱私。

Pr[A(D1)∈S]≤exp(ε)×Pr[A(D2)∈S]

(1)

其中，相鄰兩個數據集D1和D2是指|D1ΔD2|=1，|D1ΔD2|表示D1ΔD2中記錄的數量。

差分隱私保護主要是通過添加噪音機制技術來實現，適用于數值類型數據是拉普拉斯機制，噪音添加過多，數據真實性降低，噪音添加過小，隱私保護水平降低，所以添加噪音量的大小對數據可用性及隱私保護程度有不同的影響。敏感度是決定噪音大小的關鍵參數，當ε保持不變的情況下，敏感度越大，添加的噪音量越大。

定義2[6](敏感度)：設有函數f:D→Rd(R表示映射的實數空間；d表示查詢維度)，對于任意的相鄰數據集D1和D2，全局敏感度為：

(2)

文獻[6]提出的拉普拉斯機制滿足差分隱私，該機制是利用雙指數分布產生的噪音，實現了隱私保護，而噪音是從位置參數為0，尺度參數為b的拉普拉斯概率密度函數Pr[η=x]=(1/2b)e-|x|/b中計算得到。

定義3[14](拉普拉斯機制)：給定數據集D，設有函數f:D→Rd，敏感度為Δf，設A是基于拉普拉斯機制的隱私挖掘算法，那么算法A(D)=f(D)+〈Lap1(Δf/ε),…,Lapd(Δf/ε)〉提供差分隱私保護。

設A是基于拉普拉斯機制的聚類算法，S為算法A輸出的噪音結果，則S近似服從方差為Δf/ε、期望為0的拉普拉斯分布：

(3)

其中，f(D)表示真實聚類算法的計數查詢。

2.2評價指標

定義4：聚類有效性評價指標DB。

(4)

2.3DPk-medoids算法

以汽車保險行業為例，通過聚類算法會發現索賠率較高的客戶群，如果這些信息泄露，就會使得保險業增加索賠率較高用戶的保險金額。聚類分析的主要研究任務是基于距離的聚類，因此在計算離每個中心點最近的點會泄露隱私，通過添加隨機噪音發布一個近似中心點的值，攻擊者就無法利用已有的背景知識推斷出索賠率較高的客戶群的隱私。

參數表示如表1所示。

表1 參數表示

詳細描述如下：

算法1：DPk-medoids算法。

輸入：k,D={x1,x2,…,xn},xi∈Rd,1≤i≤n；

輸出：k個簇S1,S2,…,Sk。

1.flag=True;count=0;Min=Maxdis //Maxdis為距離的上界

3.While flag

4.Fori=1∶n

5.Forj=1∶k

8.m=j;

9.End if

10.End for

11.Sm=Sm∪xi//將xi分配給距離最近的中心點，并形成k個簇

12.End for

13.Forj=1∶m

14.Fori=1∶n

17.End if

21.Else

22.count++;

23.End if

24.End for

25.If count≥(n-k)·k//E為非負的個數

26.flag=false;

27.End if

28.End for

29.End while

設D1、D2是相差一條記錄的兩個數據集，在分配到簇時，可以看作是有k個桶的直方圖查詢，因此在d維空間[0,1]d上添加或者刪除某個樣本點，每個維度的最大變化是1，那么整個查詢敏感度為d。令S1和S2分別為算法DPk-medoids在相鄰數據集D1、D2上的輸出結果，S是任意一種聚類劃分，根據式(1)～(3)可得：

exp(ε)

(5)

其中，c(x)表示加噪后的聚類查詢結果；r(D1,x)和r(D2,x)分別表示在數據集D1和D2的真實聚類查詢。

由式(5)可知，DPk-medoids滿足ε-差分隱私。

3 實 驗

通過具體的數據實驗對DPk-medoids算法的可用性進行分析和說明。實驗環境為Inter(R)Xeon(R) CPU E5 1650V3@3.5 GHz，32 GB內存，Windows7 64位操作系統，實驗使用Matlab2013實現DPk-medoids。算法中用到的數據全部來源于UCI Knowledge Discovery Archive database，具體信息如表2所示。

表2 數據信息

研究的主要目的是保證挖掘過程不會泄露隱私，DPk-medoids聚類算法中隱私預算ε越小，加入的噪音越大，保護程度越好。

3.1實驗結果圖

實驗對數據集進行歸一化預處理，使得各個屬性值控制在[0,1]范圍內。對數據集分別運用k-medoids和DPk-medoids，并做出兩種算法的DB比率曲線圖。其中，對于每個ε值，由于添加噪音的隨機性，所以在不同數據集上調用DPk-medoids算法30次后取DB值的平均值。如果DB比率越接近1，那么兩種算法聚類后的有效性就越接近，結果如圖1～3所示。

圖1 DS1的DB指標圖

圖2 DS2的DB指標圖

3.2結果分析

從實驗結果可知，DPk-medoids算法在一定程度上保證了個人隱私不會被泄露，同時也保證了聚類的有效性，它不會因為添加拉普拉斯噪音而受到巨大影響。圖1中當ε為5時，添加噪音的聚類的有效性開始穩定，并且從縱坐標的含義可知，得到差分隱私保護后的聚類與原始聚類的有效性基本相同。

由圖1～3可知，數據集越大，需要的ε越小，說明大數據集需要在較高的隱私保護級別下取得更好的效用性。因為添加敏感度為d的拉普拉斯機制時，決定噪音的參數是數據集的維數，所以加入噪音量的多少與數據集的大小沒有關系。對比圖2、3可知，在相同的隱私保護下，高維數據集的有效性低于低維數據集的有效性；對比圖1、3可知，小數據集聚類可用性低于大數據集。

圖3 DS3的DB指標圖

4 結束語

隱私保護數據挖掘旨在保證數據的安全性和有效性。差分隱私能夠提供很強的隱私證明來達到隱私保護的效果。為此，結合拉普拉斯機制，提出了一種滿足ε-差分隱私保護的聚類算法DPk-medoids。理論證明，加入拉普拉斯過程能夠滿足差分隱私。而仿真實驗結果表明，在引入差分隱私保護后可實現可用性和安全性的平衡，且不同規模的數據集有不同的有效性。此外，因噪音添加的大小直接影響聚類結果和隱私保護程度，所以在實現隱私保護的同時又能實現與原始聚類相同的有效性，將是未來的研究方向之一。

[1] 李 楊,郝志峰,溫 雯,等.差分隱私保護k-means聚類方法研究[J].計算機科學,2013,40(3):287-290.

[2] 雷紅艷,鄒漢斌.限制隱私泄露的隱私保護聚類算法[J].計算機工程與設計,2010,31(7):1444-1446.

[3] Lindell Y,Pinkas B.Privacy preserving data mining[C]//International cryptology conference on advances in cryptology.[s.l.]:[s.n.],2000:36-54.

[4] Sweeney L.K-anonymity:a model for protecting privacy[J].International Journal on Uncertainty,Fuzziness and Knowledge-based Systems,2002,10(5):557-570.

[5] Dwork C. Differential privacy[C]//Proceedings of the 33rd international colloquium on automata,languages and programming.Venice,Italy:[s.n.],2006:1-12.

[6] Dwork C.Differential privacy:a survey of results[C]//International conference on theory & applications of models of computation.[s.l.]:[s.n.],2008:1-19.

[7] Dework C, Lei J. Differential privacy and robust statistics[C]//ACM symposium on theory of computing.[s.l.]:ACM,2009:371-380.

[8] 熊 平,朱天清,王曉峰.差分隱私保護及其應用[J].計算機學報,2014,37(1):101-122.

[9] Blum A,Dework C,Mcsherry F,et al. Practical privacy:the SuLQ framework[C]//Twenty-fourth ACM Sigact-Sigmod-Sigart symposium on principles of database systems.[s.l.]:ACM,2005:128-138.

[10] Dework C.A firm foundation for private data analysis[J].Communications of the ACM,2011,54(1):86-95.

[11] Su D,Cao J,Li N,et al.Differentially private K-Means clustering[C]//Conference on data and application security and privacy.[s.l.]:ACM,2015.

[12] 吳偉民,黃煥坤.基于差分隱私保護的DP-DBScan聚類算法研究[J].計算機工程與科學,2015,37(4):830-834.

[13] 張嘯劍,王 淼,孟小峰.差分隱私保護下一種精確挖掘top-k頻繁模式方法[J].計算機研究與發展,2014,51(1):104-114.

[14] Dwork C,McSherry F,Nissim K,et al.Calibrating noise to sensitivity in private data analysis[C]//Theory of cryptography conference.[s.l.]:[s.n.],2006:265-284.

[15] Davies D L,Bouldin D W.A cluster separation measure[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1979,1(2):224-227.

ADPk-medoidsClusteringAlgorithmwithDifferentialPrivacyProtection

GAO Yu1,2，TIAN Feng2，WU Zhen-qiang1,2

(1.Key Laboratory of Modern Teaching Technology of Ministry of Education,Xi’an 710062,China; 2.School of Computer Science,Shaanxi Normal University,Xi’an 710062,China)

Cluster analysis is one of the significant research fields in the data mining.Due to its paramount advantages in identification of the internal data structure and pretreatment/analysis of the data,it can be used in fields of the image processing and pattern recognition and so on.Users’ sensitive information could face leaking threats if mining tools are used to obtain the personal privacy by some organizations which own large datasets,such as medical companies.Therefore,taken into the characteristic of differential privacy account,a DPk-medoids algorithm based on differential privacy protection is proposed.It releases the noised center points before using Laplace mechanism to add noise,and in certain degree,personal privacy security and the effectiveness of clustering can be ensured.Experimental results with the ture datasets show that it can be applied to datasets with different scales and dimensions and moreover the range of effective ratio can reach to 0.9～1 compared with original clustering algorithm when the privacy budget reaches a certain value.

data mining;privacy preserving;differential privacy;k-medoids clustering

TP309.2

A

1673-629X(2017)10-0117-04

2016-10-01

2017-02-15 < class="emphasis_bold">網絡出版時間

時間：2017-07-11

國家自然科學基金資助項目(61602290，61173190)；中央高校基本科研業務費(GK201501008，GK261001236)

高 瑜(1990-)，女，碩士研究生，研究方向為差分隱私保護；吳振強，教授，博士生導師，研究方向為隱私保護、分子通信。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1454.036.html

10.3969/j.issn.1673-629X.2017.10.025