高 瑜，田 豐，吳振強(qiáng)

(1.現(xiàn)代教學(xué)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710062; 2.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710062)

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

高 瑜1,2，田 豐2，吳振強(qiáng)1,2

(1.現(xiàn)代教學(xué)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710062; 2.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710062)

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

數(shù)據(jù)挖掘；隱私保護(hù)；差分隱私；k-中心性聚類

1 概 述

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

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

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

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

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

基于差分隱私保護(hù)的k-means聚類方法中，沒有考慮到離群點(diǎn)對(duì)聚類的影響。為此，提出了基于差分隱私保護(hù)的k-medoids聚類算法，以解決離群點(diǎn)帶來(lái)的敏感性問(wèn)題。該算法通過(guò)加入拉普拉斯噪音，實(shí)現(xiàn)了對(duì)敏感數(shù)據(jù)的隱私保護(hù)。

為驗(yàn)證該算法的有效性和可行性，對(duì)該算法進(jìn)行了可行性證明和仿真實(shí)驗(yàn)。安全分析和模擬實(shí)驗(yàn)結(jié)果均表明，該算法在引入差分隱私保護(hù)后可實(shí)現(xiàn)數(shù)據(jù)的可用性和安全性，且不同規(guī)模的數(shù)據(jù)集具有不同的有效性。

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

2.1差分隱私的相關(guān)定義

即使攻擊者知道某一個(gè)數(shù)據(jù)集除一條記錄之外的其他所有信息，差分隱私保護(hù)模型也能保證攻擊者不會(huì)通過(guò)剩余的這一條記錄從輸出結(jié)果中獲得額外信息。所關(guān)注的焦點(diǎn)是在聚類過(guò)程中如何使得距離公布時(shí)的隱私不被泄露。當(dāng)提交聚類模式查詢時(shí)，返回的是經(jīng)過(guò)差分隱私處理后的結(jié)果。

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

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

(1)

其中，相鄰兩個(gè)數(shù)據(jù)集D1和D2是指|D1ΔD2|=1，|D1ΔD2|表示D1ΔD2中記錄的數(shù)量。

差分隱私保護(hù)主要是通過(guò)添加噪音機(jī)制技術(shù)來(lái)實(shí)現(xiàn)，適用于數(shù)值類型數(shù)據(jù)是拉普拉斯機(jī)制，噪音添加過(guò)多，數(shù)據(jù)真實(shí)性降低，噪音添加過(guò)小，隱私保護(hù)水平降低，所以添加噪音量的大小對(duì)數(shù)據(jù)可用性及隱私保護(hù)程度有不同的影響。敏感度是決定噪音大小的關(guān)鍵參數(shù)，當(dāng)ε保持不變的情況下，敏感度越大，添加的噪音量越大。

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

(2)

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

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

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

(3)

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

2.2評(píng)價(jià)指標(biāo)

定義4：聚類有效性評(píng)價(jià)指標(biāo)DB。

(4)

2.3DPk-medoids算法

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

參數(shù)表示如表1所示。

表1 參數(shù)表示

詳細(xì)描述如下：

算法1：DPk-medoids算法。

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

輸出：k個(gè)簇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分配給距離最近的中心點(diǎn)，并形成k個(gè)簇

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為非負(fù)的個(gè)數(shù)

26.flag=false;

27.End if

28.End for

29.End while

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

exp(ε)

(5)

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

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

3 實(shí) 驗(yàn)

通過(guò)具體的數(shù)據(jù)實(shí)驗(yàn)對(duì)DPk-medoids算法的可用性進(jìn)行分析和說(shuō)明。實(shí)驗(yàn)環(huán)境為Inter(R)Xeon(R) CPU E5 1650V3@3.5 GHz，32 GB內(nèi)存，Windows7 64位操作系統(tǒng)，實(shí)驗(yàn)使用Matlab2013實(shí)現(xiàn)DPk-medoids。算法中用到的數(shù)據(jù)全部來(lái)源于UCI Knowledge Discovery Archive database，具體信息如表2所示。

表2 數(shù)據(jù)信息

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

3.1實(shí)驗(yàn)結(jié)果圖

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

圖1 DS1的DB指標(biāo)圖

圖2 DS2的DB指標(biāo)圖

3.2結(jié)果分析

從實(shí)驗(yàn)結(jié)果可知，DPk-medoids算法在一定程度上保證了個(gè)人隱私不會(huì)被泄露，同時(shí)也保證了聚類的有效性，它不會(huì)因?yàn)樘砑永绽乖胍舳艿骄薮笥绊憽D1中當(dāng)ε為5時(shí)，添加噪音的聚類的有效性開始穩(wěn)定，并且從縱坐標(biāo)的含義可知，得到差分隱私保護(hù)后的聚類與原始聚類的有效性基本相同。

由圖1～3可知，數(shù)據(jù)集越大，需要的ε越小，說(shuō)明大數(shù)據(jù)集需要在較高的隱私保護(hù)級(jí)別下取得更好的效用性。因?yàn)樘砑用舾卸葹閐的拉普拉斯機(jī)制時(shí)，決定噪音的參數(shù)是數(shù)據(jù)集的維數(shù)，所以加入噪音量的多少與數(shù)據(jù)集的大小沒有關(guān)系。對(duì)比圖2、3可知，在相同的隱私保護(hù)下，高維數(shù)據(jù)集的有效性低于低維數(shù)據(jù)集的有效性；對(duì)比圖1、3可知，小數(shù)據(jù)集聚類可用性低于大數(shù)據(jù)集。

圖3 DS3的DB指標(biāo)圖

4 結(jié)束語(yǔ)

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

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

[2] 雷紅艷,鄒漢斌.限制隱私泄露的隱私保護(hù)聚類算法[J].計(jì)算機(jī)工程與設(shè)計(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] 熊 平,朱天清,王曉峰.差分隱私保護(hù)及其應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào),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] 吳偉民,黃煥坤.基于差分隱私保護(hù)的DP-DBScan聚類算法研究[J].計(jì)算機(jī)工程與科學(xué),2015,37(4):830-834.

[13] 張嘯劍,王 淼,孟小峰.差分隱私保護(hù)下一種精確挖掘top-k頻繁模式方法[J].計(jì)算機(jī)研究與發(fā)展,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">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-07-11

國(guó)家自然科學(xué)基金資助項(xiàng)目(61602290，61173190)；中央高?；究蒲袠I(yè)務(wù)費(fèi)(GK201501008，GK261001236)

高 瑜(1990-)，女，碩士研究生，研究方向?yàn)椴罘蛛[私保護(hù)；吳振強(qiáng)，教授，博士生導(dǎo)師，研究方向?yàn)殡[私保護(hù)、分子通信。

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

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