應(yīng)用BWP指標(biāo)的差分隱私保護k-means算法

張亞玲，屈玲玉

西安理工大學(xué) 計算機科學(xué)與工程學(xué)院，西安 710048

隨著大數(shù)據(jù)和信息技術(shù)的快速發(fā)展，數(shù)據(jù)挖掘成為當(dāng)前大數(shù)據(jù)環(huán)境下獲取信息的重要方法[1]。聚類分析是一種經(jīng)典的數(shù)據(jù)挖掘方法，允許從大量的數(shù)據(jù)中挖掘隱含的、有價值的知識和規(guī)則。許多企業(yè)收集了各領(lǐng)域的大量數(shù)據(jù)，利用聚類分析等技術(shù)對這些數(shù)據(jù)進行處理，以便開展科學(xué)研究、推送廣告等，通過聚類可以提高其服務(wù)質(zhì)量。然而，聚類分析通常包含用戶數(shù)據(jù)，如果這些數(shù)據(jù)被不法分子加以利用，將會對個人隱私產(chǎn)生嚴(yán)重的威脅。因此，如何在聚類分析過程中保護用戶的個人隱私已逐漸成為數(shù)據(jù)挖掘和信息安全領(lǐng)域中的熱點問題。

針對以上問題，早期研究提出了基于等價類的kanonymity[2]及其一系列擴展模型。但這些模型沒有一個嚴(yán)格的數(shù)學(xué)公式可以證明其隱私保護水平，并且需要不斷改進來抵御新的攻擊，如背景知識攻擊[3]和合成攻擊[4]?；诖吮尘?，2006年，Dwork提出了差分隱私（differential privacy，DP）[5]的概念。在此定義下，對數(shù)據(jù)集的處理結(jié)果對于具體某個記錄的變化是不敏感的，單個記錄在數(shù)據(jù)集中或者不在數(shù)據(jù)集中，對計算結(jié)果的影響微乎其微，因此攻擊者無法通過觀察計算結(jié)果而獲取準(zhǔn)確的個體信息[6]。同時，差分隱私建立在嚴(yán)格的數(shù)學(xué)定義之上，并對隱私披露風(fēng)險給出了定量化的表示和證明。隨后，Dwork等人持續(xù)完善和補充了差分隱私理論[7-11]。何賢芒等人[12]提出了一個差分隱私保護攻擊模型，并基于這個模型，提出了一個差分隱私保護技術(shù)的攻擊算法和參數(shù)ε的選取計算公式。

作為最常用的聚類算法之一，k-means由于簡單、高效等特點被廣泛應(yīng)用于各個領(lǐng)域，然而在算法執(zhí)行過程中，對中心的更新過程會泄露數(shù)據(jù)集的信息，許多研究者進行了差分隱私k-means算法的研究。

Blum等人[13]提出了一種差分隱私k-means算法（DPK-means），在獲取聚類結(jié)果的同時保護數(shù)據(jù)隱私，并在SuLQ平臺上實現(xiàn)，但該算法全局敏感度較大，且沒有給出迭代過程中如何分配隱私預(yù)算。Dwork[11]在Blum的基礎(chǔ)上，從隱私預(yù)算分配的角度對其進行了完善，提出了兩種隱私預(yù)算分配的方法。Nissim等人[14]提出了PK-means算法，給出了計算查詢函數(shù)敏感度的方法，使k-means聚類中心滿足差分隱私保護，但它的約束條件較多，實用性不強。李楊等人[15]針對隱私預(yù)算ε降低到一定值時聚類可用性變差的問題，提出了IDPKmeans算法，優(yōu)化了初始聚類中心的選擇，卻忽視了離群點對最終聚類結(jié)果的負面影響。Yu等人[16]考慮了離群點的消極影響，在IDPK-means的基礎(chǔ)上提出了OEDPKmeans算法，利用異常值檢測算法，根據(jù)數(shù)據(jù)點的密度分布選擇合適的初始中心，但是該算法時間復(fù)雜度較大，在某些數(shù)據(jù)分布下收斂速度較慢。Ren等人[17]為了提高DPK-means算法的聚類效率，提出了DPLK-means算法，該算法通過對原始數(shù)據(jù)集劃分的每個子集執(zhí)行差分隱私k-means算法來改進初始中心點的選擇，但是聚類結(jié)果受數(shù)據(jù)分布影響較大，當(dāng)數(shù)據(jù)集較小時，算法不能很好地工作。胡闖等人[18]在DPK-means算法的基礎(chǔ)上，引入k-means++算法改進初始中心點的選擇，但是該算法對于不規(guī)則的數(shù)據(jù)集會產(chǎn)生較差的聚類效果。樊一康等人[19]提出的TripleP K-means算法通過計算數(shù)據(jù)集中各點的最近鄰超球半徑以消除離群點的消極影響，但當(dāng)隱私預(yù)算較小時，聚類效果不理想。Fan等人[20]針對傳統(tǒng)的隱私預(yù)算分配存在迭代次數(shù)越多隨機噪聲越大的問題，提出了一種基于等差數(shù)列隱私預(yù)算分配的APDPK-means算法，在迭代過程中由大到小分配隱私預(yù)算，以保證其在迭代早期可以快速收斂。

從改進差分隱私保護k-means算法的隱私預(yù)算分配機制以提高聚類結(jié)果的可用性出發(fā)，本文引入BWP（between-within proportion）指標(biāo)，提出一個改進的差分隱私k-means算法BDPK-means（BWP differential privacyk-means）。BDPK-means算法根據(jù)每一次迭代中不同聚類簇具有不同密度分布的特點，分配不同的隱私預(yù)算，避免聚類簇太小或者密度太大而添加過大的隨機噪聲，規(guī)避由于數(shù)據(jù)擾動造成聚類中心點偏移過大的問題，使隱私性和可用性達到一個較好的平衡。實驗表明，本文BDPK-means算法在可用性與穩(wěn)定性上優(yōu)于現(xiàn)有的同類差分隱私k-means算法。

1 預(yù)備知識

1.1 差分隱私

差分隱私是一種基于數(shù)據(jù)失真的隱私保護技術(shù)，通過添加隨機噪聲干擾數(shù)據(jù)來保證數(shù)據(jù)具有一定的隱私性，同時保證原有數(shù)據(jù)的統(tǒng)計特性及可用性，以便進行數(shù)據(jù)分析等操作。

定義1（ε-差分隱私[5]）設(shè)有隨機算法M,P M為M所有可能輸出構(gòu)成的集合。對于任意兩個鄰近數(shù)據(jù)集D和D′以及P M的任何子集S，若算法M滿足：

則稱算法M滿足ε-差分隱私保護。其中，D和D′是相差最多為一條記錄的兩個鄰近數(shù)據(jù)集，參數(shù)ε稱為隱私保護預(yù)算。隱私預(yù)算代表隱私保障的水平，越小的隱私預(yù)算提供越嚴(yán)格的隱私保護水平。

定義2（全局敏感度[7]）設(shè)有查詢函數(shù)f:D→Rd，輸入為一數(shù)據(jù)集，輸出為d維實數(shù)向量。對于任意鄰近數(shù)據(jù)集D和D′：

稱為函數(shù)f的全局敏感度?！?表示1-階范數(shù)距離。

差分隱私有兩種實現(xiàn)機制，Laplace機制與指數(shù)機制，其中Laplace機制適用于處理數(shù)值型數(shù)據(jù)，指數(shù)機制適用于非數(shù)值型結(jié)果。本文采用Laplace機制實現(xiàn)差分隱私保護。

定義3（Laplace機制[8]）給定數(shù)據(jù)集D，設(shè)有函數(shù)f:D→Rd，其中函數(shù)敏感度為Δf，那么隨機算法M(D)=f(D)+Y提供ε-差分隱私保護，Y~Lap(Δf/ε)服從尺度參數(shù)Δf/ε的Laplace分布。

Laplace機制是通過向結(jié)果中加入服從Laplace分布的隨機噪聲來實現(xiàn)差分隱私保護。將位置參數(shù)為0、尺度參數(shù)為b的Laplace分布記為Lap(b)，其概率密度函數(shù)為：

此外，一個復(fù)雜的隱私保護問題通常需要多次應(yīng)用差分隱私保護算法才能得以解決。在這種情況下，隱私預(yù)算兩個組合性質(zhì)對于聚類算法的隱私分配過程具有重要的意義。

性質(zhì)1（序列組合性[21]）設(shè)有算法M1,M2,…,M n，算法的隱私預(yù)算分別為ε1,ε2,…,εn，那么對于同一數(shù)據(jù)集D，算法{M1,M2,…,M n}在D上構(gòu)成的組合算法M(M1(D),M2(D),…,M n(D))提供ε-差分隱私，其中ε=

性質(zhì)2（并行組合性[21]）設(shè)有算法M1,M2,…,M n，算法的隱私預(yù)算分別為ε1,ε2,…,εn，將D分為不相交的數(shù)據(jù)集D1,D2,…,D n，算法{M1,M2,…,M n}構(gòu)成的組合算法M(M1(D1),M2(D2),…,Mn(D n))提供ε-差分隱私，其中ε=max(εi)。

1.2 差分隱私保護k-means聚類

基于差分隱私保護的k-means聚類算法旨在改變數(shù)據(jù)集中的任意一條記錄時，各聚類簇中心和數(shù)據(jù)數(shù)目產(chǎn)生的相應(yīng)變化不會泄露隱私信息。文獻[19]提出的TripleP K-means算法考慮了k-means算法對離群點較敏感的缺點，對離群點進行修剪，實現(xiàn)了在單機環(huán)境和分布式環(huán)境下對k-means算法添加差分隱私的過程。文獻[19]中有關(guān)離群點的定義如下：

定義4（r-最近鄰超球半徑[19]）對于RT上的數(shù)據(jù)集D={x1,x2,…,x N}，稱任一數(shù)據(jù)點xi與離其最近的r個數(shù)據(jù)點在T維空間中構(gòu)成的超球為x i的r-最近鄰超球，這一概念原型為文獻[16]中的r-最近鄰區(qū)域。點x i與其超球中所有點的平均歐式距離為超球的半徑。

定義5（離群點及判定閾值[19]）離群點[16]是指數(shù)據(jù)集中與其他點顯著不同的數(shù)據(jù)點。對于離群點的判定，設(shè)數(shù)據(jù)集中的稀有類由至多5%的數(shù)據(jù)點組成[22]，估計數(shù)據(jù)集D中離群點數(shù)目不超過N×0.05，其中N為數(shù)據(jù)集規(guī)模大小。記離群點的r-最近鄰超球半徑的判定閾值為T，取其值為數(shù)據(jù)集中r-最近鄰超球半徑最大的N×0.05個點的半徑均值，從而認為r-最近鄰超球半徑超過閾值T的數(shù)據(jù)點為離群點。

文獻[19]算法單機環(huán)境下的主要思想：

步驟1對數(shù)據(jù)集中的所有數(shù)據(jù)進行歸一化處理，并且計算各點的r-最近鄰超球半徑，由此得出離群點判定閾值T。

步驟2從數(shù)據(jù)集中隨機選取一個非離群點μ1′，然后從剩余的數(shù)據(jù)點中選取距離μ1′最近的floor(N/K)個非離群點（floor()為向下取整函數(shù)），與μ1′組成初始簇C1。算法重復(fù)這一過程，直至選出K個簇。

步驟3計算各簇中數(shù)據(jù)點總和與簇中數(shù)據(jù)點的數(shù)目，分別添加Laplace噪聲，求各簇的均值作為初始聚類中心。

步驟4計算數(shù)據(jù)集中非離群點與各聚類中心的距離，并將這些數(shù)據(jù)點分配到距離最近的聚類中心所在簇中。記第k個中心的簇為C k，簇中數(shù)據(jù)點數(shù)目及總和分別為numk和sumk，分別向numk和sumk添加相同大小的隨機噪聲，并計算新的聚類中心點。

步驟5計算本輪和上一輪中K個聚類中心點的距離是否滿足收斂條件，若滿足，則算法終止，輸出聚類結(jié)果，否則重復(fù)步驟2~步驟5。

隱私預(yù)算分配采用二分分配[11]的方法，即第一輪迭代分配ε/2的隱私預(yù)算，之后每次迭代消耗隱私預(yù)算的1/2。

實驗過程中發(fā)現(xiàn)隨著迭代次數(shù)的增加，隱私預(yù)算就會越小。由Laplace差分隱私保護機制的性質(zhì)可知，產(chǎn)生的隨機噪聲就越大，從而導(dǎo)致聚類中心的偏移過大，影響最終的聚類結(jié)果。

2 BDPK-means算法

為了解決隱私預(yù)算ε較小時數(shù)據(jù)可用性較差的問題，本文提出了一種基于BWP指標(biāo)的差分隱私保護kmeans聚類算法。算法的主要思想是使用BWP指標(biāo)評估每次迭代中聚類的效果，考慮每輪迭代中不同簇有不同密度分布、不同大小等特點，為每輪迭代中不同的聚類簇分配不同的隱私預(yù)算，從而添加不同的隨機噪聲，以此來解決中心點嚴(yán)重偏離而造成聚類可用性差的問題。

2.1 BWP指標(biāo)

BWP指標(biāo)[23]是評價聚類結(jié)果好壞的一種方式。結(jié)合內(nèi)聚度和分離度兩種因素，評價不同算法或者算法不同運行方式對聚類結(jié)果所產(chǎn)生的影響。其計算公式如下：

其中，N為數(shù)據(jù)集規(guī)模大小，j表示類標(biāo)，b(j,i)表示類間距離，w(j,i)表示類內(nèi)距離。類間距離b(j,i)為樣本i到其他每個類中樣本平均值中的最小值，類內(nèi)距離w(j,i)為該樣本到第j類中其他數(shù)據(jù)對象距離的平均值，公式如下：

其中，n k代表第k個簇的樣本點數(shù)量。BWP k值越大聚類效果越好，反之越差。

2.2 BDPK-means算法設(shè)計

假設(shè)數(shù)據(jù)集D={x1,x2,…,x N}，其包含N個具有d維屬性值的數(shù)據(jù)點，算法可以將其劃分為K個簇，聚類中心點記為u k(1≤k≤K)，隱私預(yù)算為ε，第k個簇在第t次迭代的隨機噪聲為

BDPK-means算法的主要步驟如下。

算法1主要分為三個階段。首先計算數(shù)據(jù)集中每個數(shù)據(jù)點的r-最近鄰超球半徑，由此導(dǎo)出數(shù)據(jù)集中離群點的判定閾值T（第1~6行），然后在此基礎(chǔ)上選取初始聚類中心（第7~12行），最后完成差分隱私聚類分析（第13~33行）。其中第20~32行使用BWP指標(biāo)評估聚類每一次迭代中不同簇的密度分布，在隱私預(yù)算二分分配的基礎(chǔ)上為不同的簇分配不同的權(quán)重，有針對地調(diào)整隱私預(yù)算分配，從而對每次迭代中的聚類中心點分別添加不同的噪聲，盡可能降低噪聲對聚類中心偏移的影響，提高聚類結(jié)果的可用性。

2.3 隱私性分析

定理1BDPK-means算法滿足ε-差分隱私保護。

（4）由定義1、式（11）和式（12）可得：

綜上所述，由差分隱私定義可知，BDPK-means算法滿足ε-差分隱私保護。

3 實驗分析

3.1 實驗環(huán)境及數(shù)據(jù)

本文使用Java語言進行模擬仿真實驗，實驗平臺為Intel?CoreTMi3-3240 CPU@3.40 GHz處理器，6 GB內(nèi)存，Windows10 64位操作系統(tǒng)。

本文選取了不同數(shù)量的數(shù)據(jù)集來進行仿真實驗，實驗所選擇的數(shù)據(jù)集均來自UCI機器學(xué)習(xí)庫，具體信息如表1所示。

表1 數(shù)據(jù)信息Table 1 Data information

3.2 實驗評價標(biāo)準(zhǔn)

（1）Purity

Purity（純度）作為一種用來計算聚類劃分結(jié)果正確率的常用指標(biāo)，可以對聚類結(jié)果的優(yōu)劣程度做出正確的判斷。主要思想是計算被正確劃分的樣本數(shù)據(jù)的數(shù)量占整個數(shù)據(jù)集中所有樣本數(shù)據(jù)數(shù)量的百分比。公式如下：

（2）F-measure

F-measure[24]是一種經(jīng)典的衡量聚類結(jié)果有效性的評價指標(biāo)。綜合了信息檢索與挖掘中的準(zhǔn)確率（precision）和召回率（recall）。

F-measure取值為[0，1]，值越大表示兩個數(shù)據(jù)集的聚類結(jié)果越接近，說明聚類結(jié)果可用性更好。

3.3 算法參數(shù)選取

由于計算離群點判定閾值和選取初始中心時，使用了r-最近鄰區(qū)域的概念，參考文獻[19]和文獻[25]中的方法，以F-measure為目標(biāo)函數(shù)對參數(shù)r進行調(diào)參并取最優(yōu)。

3.4 實驗結(jié)果分析

3.4.1 算法可用性分析

將本文提出的BDPK-means算法和文獻[19]中的TripleP K-means算法（簡稱TDPK-means算法）、文獻[20]中的APDPK-means算法在不同數(shù)據(jù)集下進行對比實驗。

由于Laplace噪聲的隨機性，實驗結(jié)果在同一隱私預(yù)算ε下，運行50次取平均值。圖1~圖4（a）和圖1~圖4（b）分別展示了在數(shù)據(jù)集DS1~DS4上運行三種聚類算法得到的Purity值和F-measure值的對比。

由圖1~圖4可知，隨著隱私預(yù)算的增加，三種聚類算法的Purity值和F-measure值也在不斷增加。這是因為隨著隱私預(yù)算的增加，添加的噪聲就會減小，聚類結(jié)果的可用性就會得到提高。本文算法與TDPK-means算法和APDPK-means算法相比，Purity值和F-measure值都有較大的提升，尤其在隱私預(yù)算較小時，聚類性能優(yōu)勢表現(xiàn)更為明顯。

圖1 DS1上運行的結(jié)果Fig.1 Results on DS1

圖4 DS4上運行的結(jié)果Fig.4 Results on DS4

具體來說，當(dāng)隱私預(yù)算為0.05時，對于DS1，Purity值平均提高了0.24，F(xiàn)-measure值平均提高了0.33。DS2中，Purity值平均提高了0.21，F(xiàn)-measure值平均提高了0.40。針對DS3，F(xiàn)-measure值平均提高了0.20。可以注意到，DS3中，本文算法和其他兩種聚類算法的Purity值，在隱私預(yù)算為0.05時，改進幅度不是很大。這是由于當(dāng)隱私預(yù)算為0.05時，添加的Laplace噪聲過大導(dǎo)致的。此時并不能很好地表現(xiàn)出該數(shù)據(jù)集的聚類特性，但是隨著隱私預(yù)算的增加，本文算法還是優(yōu)于其他兩種算法。對于DS4，當(dāng)隱私預(yù)算為0.05時，Purity值平均提高了0.54，F(xiàn)-measure值平均提高了0.47。

圖2 DS2上運行的結(jié)果Fig.2 Results on DS2

圖3 DS3上運行的結(jié)果Fig3 Results on DS3

因此，在相同的隱私保護水平下，BDPK-means算法在不同數(shù)據(jù)集上的性能要優(yōu)于其他兩種聚類算法。

3.4.2 算法穩(wěn)定性分析

本次實驗通過計算算法的平均迭代次數(shù)來衡量算法的穩(wěn)定性。對比算法依然采用文獻[19]和文獻[20]中的算法。三種算法的穩(wěn)定性對比如圖5所示。

圖5 迭代次數(shù)對比Fig.5 Comparison of iteration number

由圖5實驗結(jié)果可以看出，在四個數(shù)據(jù)集中，本文算法的迭代次數(shù)明顯降低，表明本文算法收斂速度較快。隨著隱私預(yù)算的增加，三種聚類算法的迭代次數(shù)都逐漸減少，當(dāng)隱私預(yù)算達到設(shè)定的最大值時，本文算法基本達到收斂狀態(tài)。此外，從圖中還可得知，本文算法迭代次數(shù)波動不大，在穩(wěn)定性上要優(yōu)于其他兩種聚類算法。

4 結(jié)束語

本文針對差分隱私k-means算法中存在隱私預(yù)算較小時聚類結(jié)果可用性差的問題，通過引入聚類評價指標(biāo)BWP評估聚類效果，為具有不同密度分布的聚類簇分配不同的權(quán)重，在一次迭代中，動態(tài)地為不同的簇分配不同的隱私預(yù)算，從而添加不同大小的隨機噪聲，避免了因為差分隱私保護導(dǎo)致數(shù)據(jù)嚴(yán)重失真的問題，使得保護個體隱私的同時保持了較高的數(shù)據(jù)可用性。通過一系列對比實驗，結(jié)果表明，本文算法不僅提高了數(shù)據(jù)的可用性和準(zhǔn)確性，而且減小了迭代次數(shù)，提高了聚類結(jié)果的穩(wěn)定性。但是本方案是在單機環(huán)境下完成的，當(dāng)數(shù)據(jù)量較大時，會耗費大量的時間。因此，在未來的研究中，應(yīng)重點考慮如何將本文算法擴展到分布式環(huán)境以解決大數(shù)據(jù)背景下所面臨的隱私泄露問題。