劉丹青，高 瑜，吳振強(qiáng)

(1.青海師范大學(xué) 計(jì)算機(jī)學(xué)院，青海 西寧 810016；2.陜西定邊實(shí)驗(yàn)中學(xué) 計(jì)算機(jī)基礎(chǔ)教學(xué)部，陜西 榆林 718600；3.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710062)

1 引言

現(xiàn)如今，無處不在的信息技術(shù)使各個領(lǐng)域都產(chǎn)生了海量的數(shù)據(jù)，如何從中“提煉”出有效的知識或信息，為人們的生產(chǎn)和生活提供決策，是大數(shù)據(jù)時代一項(xiàng)重要的工作.然而Malik[1]指出，擁有越多的數(shù)據(jù)就越能夠發(fā)現(xiàn)其中的錯誤和不精準(zhǔn)數(shù)據(jù).為此，需要專業(yè)的數(shù)據(jù)挖掘技術(shù)使人們能夠從海量數(shù)據(jù)中找到對實(shí)踐具有指導(dǎo)作用的知識.

隨著網(wǎng)絡(luò)科學(xué)的發(fā)展，數(shù)據(jù)挖掘技術(shù)中的聚類分析應(yīng)用越來越廣泛，在研究者們共同努力下也有了更大的技術(shù)進(jìn)展和應(yīng)用市場.它的功能主要是通過觀察若干個簇的特征，以洞察數(shù)據(jù)模式的分布.但Geng[2]指出，在聚類分析中用戶的敏感信息有可能被第三方利用數(shù)據(jù)挖掘引發(fā)隱私安全問題，且部分用戶還有可能為了保護(hù)自己隱私不被竊取，在數(shù)據(jù)提交之初就刻意隱瞞自己的真實(shí)信息.因此聚類分析中的用戶隱私泄露等問題極大地限制了數(shù)據(jù)挖掘技術(shù)的深度應(yīng)用.

為了處理數(shù)據(jù)隱私保護(hù)和數(shù)據(jù)挖掘分析之間的關(guān)系，Aggrawal在1999年初次提出隱私保護(hù)下的數(shù)據(jù)挖掘技術(shù)，在隱私保護(hù)前提下設(shè)計(jì)對敏感信息保護(hù)的算法，防止敏感屬性遭到隱私攻擊，至此學(xué)界掀起了一股這一領(lǐng)域的研究熱潮[3].作為分析數(shù)據(jù)問題、尋找數(shù)據(jù)之間內(nèi)在結(jié)構(gòu)或分布模式的數(shù)據(jù)挖掘工具——聚類分析，如何保證在聚類過程中不被攻擊者獲取用戶的隱私也逐漸成為學(xué)者們致力研究的一個學(xué)術(shù)方向[4].

2006年，Dwork等[5]提出了一種基于嚴(yán)格數(shù)學(xué)定義的模型——差分隱私保護(hù)模型，這種模型通過在真實(shí)數(shù)據(jù)基礎(chǔ)上添加隨機(jī)噪聲，就可使攻擊者無法發(fā)現(xiàn)原始數(shù)據(jù)的分布模式及真實(shí)值，實(shí)現(xiàn)對真實(shí)數(shù)據(jù)的隱私保護(hù)，這一優(yōu)勢引起研究者們的持續(xù)關(guān)注.基于這一隱私保護(hù)模型框架，Dwork[6]在對隱私數(shù)據(jù)進(jìn)行分析時提出了DPk-means優(yōu)化算法，通過修改隱私預(yù)算分配方式以提高聚類效果，但未對初始中心點(diǎn)的選擇進(jìn)行優(yōu)化.國內(nèi)學(xué)者李楊等[7]繼而在該算法基礎(chǔ)上提出了能對初始中心點(diǎn)選擇優(yōu)化的IDPk-means算法，以提高算法的實(shí)用性.胡闖等[8]研究了一種新的聚類算法——DPk-means-up算法，該算法以k-means++的結(jié)果作為輸入值，改善了中心點(diǎn)的選擇問題.傅彥銘等[9]則針對k-means++算法在隨機(jī)選取初始化中心點(diǎn)和迭代求質(zhì)心過程中隱私泄露的問題，提出了DPk-means++算法，確保不同隱私預(yù)算下聚類的可用性及準(zhǔn)確性.

聚類分析中基于劃分的另一種典型算法——k-medoids算法應(yīng)用比較廣泛，主要用來解決離群值問題，因而隱私保護(hù)下的k-medoids算法研究也更富有挑戰(zhàn)性[10-11].Sanjit Kumar Dash[12]提出了一種在移動云架構(gòu)中使用同態(tài)加密技術(shù)保護(hù)數(shù)據(jù)的方法——差分隱私下的k-medoids分析法，用在與他人共享敏感隱私信息時，保護(hù)隱私免被侵犯.國內(nèi)研究中，馬銀方等[13]考慮到海量數(shù)據(jù)在動態(tài)聚類過程中的隱私保護(hù)問題，提出了差分隱私下的動態(tài)聚類算法KDCk-medoids.文獻(xiàn)[14]也提出了一種差分隱私下的DPk-medoids算法，該算法在基于歐式距離測度數(shù)據(jù)相似性的迭代中對聚類中心點(diǎn)添加Laplace噪聲后再發(fā)布，以防止聚類結(jié)果的隱私信息泄露.2016年，英國考文垂大學(xué)的研究學(xué)者提出了一種差分隱私的拓展模型——誤差隱私保護(hù)模型，這兩種模型都屬于應(yīng)用數(shù)據(jù)擾動技術(shù)中添加隨機(jī)數(shù)的方法來進(jìn)行隱私保護(hù)的方法[15].基于這一隱私保護(hù)模型，文獻(xiàn)[16]提出了一種EPPk-medoids算法，通過隨機(jī)化查詢結(jié)果，可以使攻擊者無法透過擾動值推斷出聚類后用戶的隱私信息[16].

上述研究工作中，研究者均視研究所基于的數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的每個維度對于數(shù)據(jù)的重要性或者影響程度都相同，但事實(shí)上，從數(shù)據(jù)分析的角度而言，數(shù)據(jù)點(diǎn)的屬性集中有的屬性重要、占主導(dǎo)地位，有的屬性次要、僅起輔助說明作用，這使得對數(shù)據(jù)點(diǎn)的聚類和加噪應(yīng)根據(jù)數(shù)據(jù)點(diǎn)每一維屬性對于該數(shù)據(jù)的重要性或者影響程度而論，不應(yīng)統(tǒng)一而論.基于此，論文提出了基于距離貢獻(xiàn)率聚類(即加權(quán)聚類)的Wk-medoids算法，并在該聚類算法基礎(chǔ)上提出了基于距離貢獻(xiàn)率加噪(即加權(quán)加噪)的面向差分隱私保護(hù)框架的WDPk-medoids算法及面向誤差隱私保護(hù)框架的WEPPk-medoids算法，研究了相應(yīng)算法的特性，并與前人未加權(quán)的工作做了對比分析，以驗(yàn)證算法在聚類和加噪過程中引入數(shù)據(jù)屬性權(quán)重的必要性及重要性；同時還應(yīng)用聚類效用評價指標(biāo)對這三種基于距離貢獻(xiàn)率的隱私保護(hù)聚類算法的性能進(jìn)行了對比分析，為隱私保護(hù)框架下聚類挖掘算法如何權(quán)衡數(shù)據(jù)聚類有效性以及隱私保護(hù)安全性之間的相互關(guān)系提供了參照建議.

2 基于距離貢獻(xiàn)率的Wk-medoids算法

2.1 閔氏距離

聚類分析中基于劃分的k-medoids算法是一種常用的聚類算法，其基本問題描述如下：設(shè)數(shù)據(jù)集D={x1，x2，…，xn}，且xi∈Rd，k表示將數(shù)據(jù)集合D劃分為類簇的個數(shù)，Cj表示第j個類簇，nj表示第j個類簇的大小.

k-medoids算法一般采用歐氏距離作為目標(biāo)函數(shù)來劃分?jǐn)?shù)據(jù)集，為了研究隱私保護(hù)框架下聚類算法的普適性特征，論文基于閔氏距離開展研究，如定義1所示.閔氏距離(亦稱閔可夫斯基距離)，是歐氏空間的一種測度，當(dāng)冪指數(shù)p分別取1，2及∞時，該距離公式分別相當(dāng)于曼哈頓距離、歐氏距離及切比雪夫距離.

定義1[17]閔氏距離

(1)

其中：xij表示第i個數(shù)據(jù)的第j個屬性值，xkj表示第k個數(shù)據(jù)的第j個屬性值，d(xi，xk)表示數(shù)據(jù)點(diǎn)xi(i=1，2，…，n)到中心點(diǎn)xk(i=1，2，…，n)的距離值.

通常在計(jì)算數(shù)據(jù)點(diǎn)相似性的算法中，默認(rèn)為數(shù)據(jù)點(diǎn)每一維的屬性對于點(diǎn)與點(diǎn)之間距離的貢獻(xiàn)率是一樣的.為了更準(zhǔn)確地度量數(shù)據(jù)之間的相似性，應(yīng)依據(jù)屬性集中屬性的重要程度，或?qū)ζ渌麑傩缘挠绊懗潭取⒒驅(qū)τ?jì)算樣本點(diǎn)距離中心點(diǎn)遠(yuǎn)近的貢獻(xiàn)率，通過對各屬性之間進(jìn)行橫向比較而確定其相應(yīng)的權(quán)值.于是，數(shù)據(jù)集所有樣本點(diǎn)第k個屬性的權(quán)重均相同，相當(dāng)于整個數(shù)據(jù)集只有一個1×m維的權(quán)重向量，該權(quán)重標(biāo)準(zhǔn)強(qiáng)化了重要屬性對距離中心點(diǎn)的貢獻(xiàn)率、減弱了次要屬性對計(jì)算距離中心點(diǎn)遠(yuǎn)近的影響[17].基于此，論文采用基于距離貢獻(xiàn)率的閔氏距離來開展隱私保護(hù)框架下k-medoids算法的研究，如定義2所示.我們將這個加權(quán)聚類算法稱為Wk-medoids算法.

定義2[18]基于距離貢獻(xiàn)率的閔氏距離為：

(2)

需要說明的是，論文關(guān)于權(quán)值ω的計(jì)算方法沒有做統(tǒng)一的定義，根據(jù)實(shí)際決策問題可采用主觀賦權(quán)法，即決策者(專家)依據(jù)對各屬性的重視程度和自身的知識經(jīng)驗(yàn)來確定各屬性的權(quán)重，也可采用客觀賦權(quán)法或組合賦權(quán)法來確定各屬性的權(quán)重，只要滿足各屬性的權(quán)重之和為1即可.在本文的仿真實(shí)驗(yàn)中，權(quán)值ω是通過隨機(jī)數(shù)賦值的.

Wk-medoids算法中，中心點(diǎn)的更新可以采用數(shù)據(jù)點(diǎn)距代表對象的聚類誤差平方和最小為迭代策略，該平方和定義如下所示：

定義3[19]聚類誤差平方和

(3)

其中：xj b表示第j類的第b個對象，oj是簇Cj的代表對象.

2.2 聚類效用評價指標(biāo)

為了分析聚類結(jié)果的有效性及可用性，在聚類分析過程中需要采用一些客觀的評價方法，本小節(jié)主要介紹論文所采用的幾個聚類效用評價指標(biāo)[20].

定義4[21]戴維森堡丁指數(shù)DB.戴維森堡丁指數(shù)DB是通過數(shù)據(jù)集中任意兩個簇的簇內(nèi)平均距離之和Si+Sj與兩個簇簇中心距離Sij的比值中最大值之和的平均值，來計(jì)算簇之間的相似度：

(4)

根據(jù)公式可知，DB值與聚類結(jié)果相似性的程度呈反比，即DB值越小，簇內(nèi)越同質(zhì)、簇間越異質(zhì).

設(shè)有數(shù)據(jù)集D={x1，x2，…，xn}.假設(shè)數(shù)據(jù)集D可劃分成m個組，表示為E={E1，E2，…，Em}，且D中存在一個包含k個簇的聚類結(jié)構(gòu)，表示為C={C1，C2，…，Ck}，則可通過比較分組E和聚類結(jié)構(gòu)C來對聚類質(zhì)量進(jìn)行評價.

定義5[22]標(biāo)準(zhǔn)化互信息NMI(Normalized Mutual Information)可通過下面一組公式進(jìn)行計(jì)算：

(1)數(shù)據(jù)E和C之間的互信息

(5)

(2)數(shù)據(jù)E與C之間的信息熵

H(E)=-∑Ep(Ei)p(Cj),

(6)

(3)數(shù)據(jù)E與C之間的歸一化互信息

(7)

由式(7)可知，NMI的值越大，則劃分結(jié)果越相似、聚類效果越好.

(8)

2.3 Wk-medoids算法流程圖

聚類算法中的k-medoids算法主要解決離群值問題，應(yīng)用比較廣泛.Wk-medoids算法以目標(biāo)函數(shù)最小化為目的，通過迭代策略把數(shù)據(jù)集合劃分成若干個塊或分組，每個塊或分組稱為一個簇.

算法流程圖如圖1所示.

圖1 Wk-medoids算法流程圖

3 基于距離貢獻(xiàn)率的WDPk-medoids算法

3.1 差分隱私保護(hù)模型

差分隱私保護(hù)采用添加諸如適用于數(shù)值數(shù)據(jù)的Laplace隨機(jī)數(shù)，以對數(shù)據(jù)進(jìn)行加噪處理.噪聲值的大小受敏感度影響，噪聲過大，數(shù)據(jù)可用性降低；噪聲過小，數(shù)據(jù)隱私泄露風(fēng)險增高.

定義7[23]假設(shè)隨機(jī)函數(shù)A所有可能的輸出構(gòu)成集合Range(A)，且Range(A)的任意子集為S(S?Range(A))，對于最多相差一條記錄的兩個數(shù)據(jù)集D1，D2，(|D1ΔD2|≤1))，若滿足下式：

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

(9)

則稱A提供ε-差分隱私，數(shù)據(jù)隱私保護(hù)的效果隨著隱私保護(hù)預(yù)算ε的增大而降低.

定義8[23]設(shè)有函數(shù)f：D→Rd.對于任意相鄰的數(shù)據(jù)集D1和D2，其敏感度定義為：

Δf=maxD1D2‖f(D1)-f(D2)‖.

(10)

定義9[23]基于定義8，如果算法A的輸出結(jié)果滿足：

A(D)=f(D)+〈Lap1(Δf/ε)，…，Lapd(Δf/ε)〉

(11)

則稱算法A可提供滿足Laplace機(jī)制的差分隱私保護(hù).

考慮到數(shù)據(jù)集D中數(shù)據(jù)點(diǎn)每一維的屬性對于數(shù)據(jù)的重要程度不同，且在聚類過程中對于距離中心點(diǎn)的貢獻(xiàn)率也有所不同，因此對數(shù)據(jù)點(diǎn)的加噪也應(yīng)按照屬性相應(yīng)的貢獻(xiàn)率有輕重緩急之分，以減少數(shù)據(jù)整體的失真程度.基于此，我們提出基于距離貢獻(xiàn)率的Laplace加噪機(jī)制，即依據(jù)數(shù)據(jù)每一維屬性的權(quán)重來為相應(yīng)維度添加噪聲，此時算法A的輸出結(jié)果滿足：

A(D)=f(D)+〈ω1*Lap1(Δf/ε)，…，ωd*Lapd(Δf/ε)〉

(12)

3.2 WDPk-medoids算法流程圖

WDPk-medoids算法是在差分隱私保護(hù)框架下基于DPk-medoids的算法，應(yīng)用基于距離貢獻(xiàn)率的理念對中心點(diǎn)加噪、對剩余結(jié)點(diǎn)聚類，循環(huán)往復(fù)直至發(fā)布最新噪音中心點(diǎn)和聚類分布，以實(shí)現(xiàn)隱私信息不被泄露的目的.

算法流程圖如圖2所示.

圖2 WDPk-medoids算法流程圖

4 基于距離貢獻(xiàn)率的WEPPk-medoids算法

4.1 誤差隱私保護(hù)模型

誤差隱私保護(hù)模型是對查詢結(jié)果隨機(jī)化，使得第三方估算數(shù)據(jù)點(diǎn)在與不在數(shù)據(jù)集中的誤差方差值總相等，從而無法挖掘用戶的隱私信息.

(13)

這里，參數(shù)ε為xe的隱私泄露程度.式(12)表明，第三方使用函數(shù)f(Dn)預(yù)測xe的未知信息比用函數(shù)f(Dne)預(yù)測xe的未知信息僅僅多ε部分，當(dāng)ε很小時，xe幾乎沒有隱私披露的風(fēng)險；如果ε為0，數(shù)據(jù)的隱私保護(hù)最強(qiáng)，即用戶的信息不會因?yàn)樵贒n中就會被第三方使用查詢函數(shù)查詢得到個人隱私，而是和xe不在Dn中的情況有幾乎相同的查詢結(jié)果；而隨著ε值的增加，xe隱私披露的風(fēng)險也逐步增加.

為了實(shí)現(xiàn)對數(shù)據(jù)點(diǎn)的隱私保護(hù)，需要在滿足上式條件下，對查詢結(jié)果隨機(jī)化.該過程可采用自助抽樣法加噪機(jī)制來進(jìn)行，其過程如圖3所示[16]：對于數(shù)據(jù)集的每一個簇，用均勻隨機(jī)抽樣法生成樣本簇，樣本簇大小與原始簇大小相同，并按下式計(jì)算樣本簇的質(zhì)心(中心點(diǎn)):

圖3 自助抽樣法的過程示意圖

(14)

再獨(dú)立地將前面的隨機(jī)抽樣事件重復(fù)執(zhí)行B次，并取這些質(zhì)心的均值.則每個聚類簇的中心點(diǎn)可按下式進(jìn)行估計(jì)，其中αe為xe在有放回抽樣的結(jié)果中出現(xiàn)的次數(shù)：

(15)

與差分隱私保護(hù)框架中對聚類中心的加噪一樣，在誤差隱私保護(hù)框架下我們同樣提出基于距離貢獻(xiàn)率的自助抽樣加噪機(jī)制，在對樣本簇質(zhì)心的每個分量進(jìn)行估算時參考了相應(yīng)屬性的權(quán)重，此時每個樣本簇的中心點(diǎn)可按下式進(jìn)行估計(jì)：

(16)

4.2 WEPPk-medoids算法流程圖

WEPPk-medoids算法是在誤差隱私保護(hù)框架下基于EPPk-medoids算法，在Wk-medoids聚類分析所得中心點(diǎn)上，應(yīng)用基于距離貢獻(xiàn)率的自助抽樣法估算近似中心點(diǎn)(噪音結(jié)點(diǎn))，再以噪音結(jié)點(diǎn)為聚類中心基于距離貢獻(xiàn)率重新分配剩余結(jié)點(diǎn)，直接發(fā)布加噪后的中心點(diǎn)及聚類分布，由此防止第三方得到真實(shí)聚類分布情況.

算法流程圖如圖4所示：

圖4 WEPPk-medoids算法流程圖

5 算法分析與討論

5.1 WDPk-medoids算法性能分析

本節(jié)我們對WDPk-medoids算法，應(yīng)用DB指標(biāo)考察引入數(shù)據(jù)點(diǎn)各維度基于距離的貢獻(xiàn)率對算法聚類和加噪過程產(chǎn)生的影響，以說明在差分隱私保護(hù)框架下WDPk-medoids算法相較于DPk-medoids算法的優(yōu)勢，并基于DB指標(biāo)和NMI指標(biāo)分別對WDPk-medoids算法中的閔氏距離冪指數(shù)進(jìn)行仿真分析，以了解該算法的特性.

論文研究采用UCI Knowledge Discovery Archive database中的公開數(shù)據(jù)集——大腸桿菌數(shù)據(jù)集.該數(shù)據(jù)集是一個生物領(lǐng)域的多分類數(shù)據(jù)集，由336個大腸桿菌蛋白質(zhì)數(shù)據(jù)組成，每個數(shù)據(jù)均使用從蛋白質(zhì)氨基酸序列計(jì)算出的七個輸入變量，外加序列名稱共八個屬性進(jìn)行描述.在仿真實(shí)驗(yàn)時我們刪除第一列屬性(序列名稱)、只取后七列屬性，再對所有數(shù)據(jù)進(jìn)行預(yù)處理，將數(shù)據(jù)歸一化為0到1之間的小數(shù)，基于預(yù)處理過的數(shù)據(jù)集使用MATLAB 2013對算法調(diào)用多次后取相應(yīng)指標(biāo)的平均值.

(1)距離貢獻(xiàn)率對DB比率值的影響

針對在聚類和加噪過程中是否需要引入距離貢獻(xiàn)率這一問題，我們在相同冪指數(shù)(p=2)下，著重考察了距離貢獻(xiàn)率對算法DB比率值(加噪前算法的DB值與加噪后算法DB值的比率)的影響，如圖5所示，其中橙色曲線表示DPk-medoids算法下的DB比率值(加噪前k-medoids算法的DB值與加噪后DPk-medoids算法DB值的比率變化)，而黃色曲線表示W(wǎng)DPk-medoids算法下的DB比率值(加噪前Wk-medoids算法的DB值與加噪后WDPk-medoids算法DB值的比率變化).顯然，當(dāng)數(shù)據(jù)點(diǎn)在聚類和加噪過程中按照屬性的重要程度來測度或隨機(jī)化后，加權(quán)的WDPk-medoids算法的DB比率值整體要高于未加權(quán)的DPk-medoids算法，這是由于加權(quán)后WDPk-medoids算法的DB值變小，使得相同ε下DB比率值增大.根據(jù)DB值與聚類結(jié)果相似性程度呈反比這一理論，這意味著加權(quán)劃分后的聚類在差分隱私保護(hù)框架下其整體聚類效果更優(yōu).

圖5 WDPk-medoids與DPk-medoids算法的DB比率比較圖

(2)不同冪指數(shù)p對DB比率值的影響

當(dāng)數(shù)據(jù)集的聚類數(shù)確定時，通過仿真分析如圖6所示，加權(quán)下冪指數(shù)p越小，WDPk-medoids算法的DB比率值(原始k-medoids算法的DB值與添加噪聲后WDPk-medoids算法DB值的比率)整體越大，當(dāng)p=1時，該比率值整體性能最優(yōu)，穩(wěn)定在0.9～1之間，說明此時在差分隱私保護(hù)框架下，WDPk-medoids算法的聚類效果更接近于原始的k-medoids算法.

圖6 WDPk-medoids算法的DB比率曲線圖

(3)不同冪指數(shù)p對NMI指標(biāo)的影響

聚類中的NMI指標(biāo)反映了對數(shù)據(jù)集所劃分簇之間的異質(zhì)性以及簇內(nèi)部同質(zhì)性的程度，它與聚類有效性呈正比關(guān)系.通過圖7可見，冪指數(shù)p越小，同等隱私保護(hù)程度下(相同ε值)聚類的有效性越好；隨著ε值的增大，即隱私保護(hù)程度降低時，不同冪指數(shù)下的NMI值均有所升高.

圖7 WDPk-medoids算法的NMI指標(biāo)曲線圖

從以上分析可以看出，差分隱私保護(hù)框架下算法的隱私保護(hù)預(yù)算ε越小，則添加的噪聲越大、數(shù)據(jù)隱私泄露風(fēng)險越低，但與此同時，WDPk-medoids算法在不同冪指數(shù)下的聚類效果均有所下降(不同顏色的曲線從右向左看均呈下降趨勢).是否有算法能夠同時兼顧k-medoids算法的聚類有效性以及聚類發(fā)布中數(shù)據(jù)的隱私保護(hù)程度呢？下面我們在誤差隱私保護(hù)框架下對基于距離貢獻(xiàn)率的WEPPk-medoids算法進(jìn)行仿真研究.

5.2 WEPPk-medoids算法性能分析

本節(jié)我們對WEPPk-medoids算法，基于NMI指標(biāo)及AP指標(biāo)著重考察引入數(shù)據(jù)點(diǎn)各屬性的權(quán)重對算法聚類和加噪過程產(chǎn)生的影響，以說明在誤差隱私保護(hù)框架下WEPPk-medoids算法相較于EPPk-medoids算法的優(yōu)勢，其中WEPP-know及WEPP-unknow分別表示算法中第三方是否知道預(yù)測數(shù)據(jù)點(diǎn)屬于哪個簇對應(yīng)的情況.

(1)距離貢獻(xiàn)率對NMI指標(biāo)的影響

NMI指標(biāo)是反映聚類有效性的重要指標(biāo)，通過圖8可見，當(dāng)考慮數(shù)據(jù)點(diǎn)各屬性對聚類及加噪過程的影響程度時，對于know及unknow兩種情況，加權(quán)的WEPPk-medoids算法在各隱私保護(hù)預(yù)算ε下，整體聚類效果均大于未加權(quán)的EPPk-medoids算法.

圖8 WEPPk-medoids與EPPk-medoids算法的NMI指標(biāo)比較圖

(2)距離貢獻(xiàn)率對AP指標(biāo)的影響

為了進(jìn)一步說明若要達(dá)到相同的隱私保護(hù)程度，不同算法需要添加擾動量的大小，即添加的擾動量隨隱私泄露程度值的變化情況，我們通過實(shí)驗(yàn)得到了AP(加入擾動量的平均值)隨ε變化的關(guān)系圖，如圖9所示，對于know及unknow兩種情況，加權(quán)的WEPPk-medoids算法在各隱私保護(hù)預(yù)算ε下，平均加入擾動量的程度要小于未加權(quán)的EPPk-medoids算法.這說明WEPPk-medoids這種依屬性權(quán)重加噪數(shù)據(jù)的方法可降低對整個數(shù)據(jù)點(diǎn)添加的噪聲量、減少加噪數(shù)據(jù)的失真程度，達(dá)到更好的聚類效果.

圖9 WEPPk-medoids與EPPk-medoids算法的AP指標(biāo)比較圖

5.3 三種加權(quán)算法的比較分析

本節(jié)我們基于NMI及AP兩聚類效用評價指標(biāo)著重對比分析基于距離貢獻(xiàn)率的無隱私保護(hù)的Wk-medoids算法、差分隱私框架下的WDPk-medoids算法和誤差隱私框架下的WEPPk-medoids算法在聚類有效性及隱私保護(hù)安全性上的優(yōu)劣.

(1)聚類有效性分析

圖10展示了當(dāng)ε變化時不同算法NMI指標(biāo)的變化情況.根據(jù)理論可知，ε值與隱私保護(hù)程度的強(qiáng)弱呈反向關(guān)系，而NMI值與算法聚類結(jié)果的好壞呈正向關(guān)系.

如圖10所示，Wk-medoids算法由于其不提供任何隱私保護(hù)，因而其聚類有效性最優(yōu)；隨著ε值的增加，WDPk-medoids算法的聚類有效性增強(qiáng)，直至ε=1時相當(dāng)于Wk-medoids算法的聚類效果；而對于WEPPk-medoids算法，無論噪聲添加的大小，其始終都能與Wk-medoids算法有相近的聚類效果.

圖10也表明WDPk-medoids算法要想達(dá)到同樣的聚類有效性，其隱私泄露的風(fēng)險也會相應(yīng)地升高.這是由于WDPk-medoids算法是基于維度來添加Laplace噪聲的，對于高維數(shù)據(jù)集，ε值越小，則數(shù)據(jù)集中添加的噪聲越多、給予數(shù)據(jù)的隱私保護(hù)越強(qiáng)，這雖避免了敏感屬性隱私泄露的風(fēng)險，但隨著噪聲擾動量的逐步添加，超過一定界限時有可能會破壞聚類的結(jié)果，因此WDPk-medoids算法更適用于低維度的數(shù)據(jù)集.

圖10 不同加權(quán)算法的NMI指標(biāo)比較圖

(2)噪聲擾動量分析

針對噪聲擾動量的仿真分析如圖11所示，顯然當(dāng)ε為0.001時，對于know及unknow兩種情況，WEPPk-medoids算法添加的擾動量遠(yuǎn)小于WDPk-medoids算法，且在不同隱私保護(hù)程度下，其添加的擾動量都很小，這表明WEPPk-medoids算法在小規(guī)模數(shù)據(jù)集上的聚類效果較WDPk-medoids算法要好.

圖11 不同加權(quán)算法的AP指標(biāo)比較圖

6 結(jié)束語

數(shù)據(jù)挖掘中聚類分析的目的就是在各種結(jié)果集中識別并提取具有價值的信息，這一過程中的規(guī)則或算法可能會導(dǎo)致數(shù)據(jù)的敏感信息無意中被泄露.因此，自隱私保護(hù)技術(shù)出現(xiàn)后，許多聚類分析工作就紛紛基于隱私保護(hù)而開展.本文主要基于距離貢獻(xiàn)率在隱私保護(hù)框架下對k-medoids聚類算法進(jìn)行相關(guān)研究，所做的仿真工作如下表所示(加粗顯示的為本文所提算法)：

表1 論文仿真分析小結(jié)

通過對聚類效用評價指標(biāo)的仿真分析可見，基于數(shù)據(jù)點(diǎn)不同維度對于距離中心點(diǎn)的貢獻(xiàn)率來對數(shù)據(jù)點(diǎn)聚類、添加噪聲或?qū)Σ樵兘Y(jié)果隨機(jī)化時，與原有未加權(quán)的工作相比，可降低整個數(shù)據(jù)點(diǎn)所添加的噪聲量、減少加噪數(shù)據(jù)的失真程度、提高聚類結(jié)果的有效性.整體而言，隱私保護(hù)下的聚類算法各有優(yōu)劣，其中Wk-medoids算法的聚類效果最優(yōu)、隱私保護(hù)性能最差，WDPk-medoids算法更適合大規(guī)模、低維度數(shù)據(jù)集，WEPPk-medoids算法更適合小規(guī)模數(shù)據(jù)集，以在保證用戶隱私安全的同時兼顧聚類結(jié)果的有效性.

綜上所述，基于距離貢獻(xiàn)率的理念不僅可以應(yīng)用到數(shù)據(jù)聚類過程中，也可以應(yīng)用到隱私保護(hù)的加噪過程中，以使隱私保護(hù)框架下的聚類算法適用于不同的規(guī)模和維度的數(shù)據(jù)集及應(yīng)用場景.如何擇優(yōu)選擇聚類的初始中心點(diǎn)、如何設(shè)計(jì)更合適的聚類目標(biāo)函數(shù)及如何優(yōu)化數(shù)據(jù)集各屬性之間基于距離的貢獻(xiàn)率，這關(guān)系到聚類結(jié)果的好壞，也關(guān)系到加入隱私保護(hù)后聚類算法性能的優(yōu)劣，這將是聚類劃分算法在隱私保護(hù)框架下進(jìn)一步研究的內(nèi)容之一.