鄭 劍，冷碧玉

(江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000)

0 引 言

隨著大數(shù)據(jù)時代的降臨，各類數(shù)據(jù)呈現(xiàn)出爆炸式地增長，為揭示數(shù)據(jù)中的內(nèi)在規(guī)律和性質(zhì)，聚類分析被廣泛應(yīng)用；但在收集分析數(shù)據(jù)獲得數(shù)據(jù)價值的同時，還需保證數(shù)據(jù)的隱私安全，使數(shù)據(jù)不被有心人士利用造成難以彌補的損失。因此對于未標(biāo)記數(shù)據(jù)信息的價值挖掘及隱私保護成為近年來的熱門研究問題。因為k均值聚類算法原理簡單、聚類速度快，故對k均值聚類算法的隱私保護研究熱度只增不減，但基于已研究的k均值隱私保護算法都未考慮全面，如幾十萬條數(shù)據(jù)甚至幾百萬條數(shù)據(jù)進行聚類時，k均值算法聚類過程中k值和聚類初始中心點敏感、離群點[1]處理及分布式數(shù)據(jù)集聚類時如何保護數(shù)據(jù)隱私等[2-4]問題。文獻[5]針對k均值聚類算法對初始中心點敏感及中心點更新會泄露隱私的問題，提出DPk-means++方法，對k均值的改進算法k-means++利用拉普拉斯機制[6]解決了k均值聚類算法隨機選取k個中心點不能保證聚類精確度及數(shù)據(jù)隱私泄露的問題，但未考慮數(shù)據(jù)集中離群點問題；文獻[7]提出在k均值算法中應(yīng)用局部差分隱私以適應(yīng)不同用戶的隱私需求，但未考慮整體隱私預(yù)算；綜合考慮k均值聚類算法對初始中心點的敏感及聚類過程中隱私泄露的問題，對存在離群點的大規(guī)模數(shù)據(jù)集聚類問題，借鑒文獻[8]中的k-means‖聚類算法，結(jié)合差分隱私保護模型，提出適用于存在離群點的大規(guī)模數(shù)據(jù)集聚類分析的隱私保護方法DPk-means‖(differential privacy of k-means‖)，在選取聚類初始中心點時引入且實現(xiàn)差分隱私保護機制，有效地保護了特定數(shù)據(jù)隱私，且由實驗結(jié)果表明，DPk-means‖聚類算法在注入少量隨機噪聲的情況下，保證了對存在離群點情況的魯棒性，能夠保證聚類結(jié)果準(zhǔn)確性的同時將數(shù)據(jù)泄露的風(fēng)險控制在安全范圍內(nèi)。

1 相關(guān)知識

1.1 差分隱私

差分隱私(differential privacy)[9,10]建立在假定攻擊者擁有最大背景知識的前提下，注入特定分布的隨機噪聲，定量地分析使用查詢算法導(dǎo)致敏感數(shù)據(jù)被披露的風(fēng)險，差分隱私使得目標(biāo)數(shù)據(jù)記錄是否在數(shù)據(jù)集中并不影響查詢結(jié)果，即目標(biāo)在或不在數(shù)據(jù)庫中，算法查詢得到相同數(shù)值的概率非常接近，使得攻擊者分析不出目標(biāo)數(shù)據(jù)的詳細(xì)信息，因此在保證數(shù)據(jù)可用性的情況下，同時又保證了數(shù)據(jù)的隱私安全。

定義1 (ε,δ)-差分隱私[10]。給定一個隨機查詢算法M，對于任意鄰近數(shù)據(jù)集D和D’，若M在數(shù)據(jù)集D和D’查詢下得到的結(jié)果s(s∈Range(M)) 滿足式(1)，則稱隨機查詢算法M滿足(ε,δ)-差分隱私

Pr[M(D)∈s]≤eε×Pr[M(D’)∈s]+δ

(1)

其中，Pr[·]表示應(yīng)用隨機查詢算法M數(shù)據(jù)可能被泄露的風(fēng)險；ε表示隨機查詢算法M所能夠提供的隱私保護水平，當(dāng)ε=0時，敏感數(shù)據(jù)的隱私水平達到最高，但此時數(shù)據(jù)的可用性最低，故ε的最佳取值可使得輸出結(jié)果的隱私保護程度與數(shù)據(jù)的可用性達到平衡；δ表示允許每個目標(biāo)數(shù)據(jù)都會存在δ大小的概率隱私會泄露，δ的取值通常是很小的常數(shù)，當(dāng)δ=0時，則稱隨機查詢算法M滿足ε-差分隱私。

定義2 拉普拉斯機制。給定一個數(shù)據(jù)集D，假定有一個函數(shù)f∶D→Rd， 函數(shù)f的敏感度為Δf，如果隨機算法M滿足式(2)，則稱算法M滿足ε-差分隱私

M(D)=f(D)+Lap(b)

(2)

其中，Lap(b)服從位置參數(shù)為0，尺度參數(shù)為b，且b=Δf/ε。

1.2 差分隱私組合性質(zhì)

如果需要保證復(fù)雜過程中數(shù)據(jù)的隱私不被泄露，一般都需要多次應(yīng)用到差分隱私的組合性質(zhì)。借由差分隱私的組合性質(zhì)界定復(fù)雜過程中各個階段的差分隱私預(yù)算，利用差分隱私的組合性質(zhì)計算出為保護數(shù)據(jù)隱私每個細(xì)分過程中分配的隱私預(yù)算。

性質(zhì)2 并行組合性。假設(shè)現(xiàn)有n個算法M1,M2,…,Mn， 其中每個算法的隱私預(yù)算分別為ε1,ε2,…,εn， 對于不相交數(shù)據(jù)集D1,D2,…,Dn， 則組合算法M(M1(D1), M2(D2),…,Mn(Dn)) 滿足(maxεi)-差分隱私。

1.3 k均值聚類算法

k均值聚類算法采用數(shù)據(jù)點與中心點間的距離作為相似度評價的指標(biāo)，認(rèn)為數(shù)據(jù)點與中心點間的距離越小，則相似度越高，即數(shù)據(jù)的屬性特征越接近，不同的聚類個數(shù)或聚類初始中心點會造成k均值聚類算法的聚類結(jié)果不同，因此k均值聚類算法對于聚類初始中心點的選擇和聚類個數(shù)較為敏感；除此之外，若選擇離群點作為聚類的初始中心點，會對聚類結(jié)果存在一定的影響，所以k均值聚類算法對離群點的存在也較為敏感；故k均值聚類算法主要存在3個敏感問題：

(1)聚類開始前事先人為給定的聚類個數(shù)k；

(2)聚類隨機確定聚類初始中心點；

(3)數(shù)據(jù)集中的離群點。

事先給定聚類個數(shù)是針對已知所給數(shù)據(jù)集的數(shù)據(jù)可分為簇的個數(shù)而言的，確定的聚類個數(shù)能夠使聚類精確度較高；對于未知簇的數(shù)據(jù)集來說，使用手肘法和輪廓系數(shù)綜合分析能夠得到未知簇數(shù)據(jù)集的較優(yōu)聚類中心點的個數(shù)可解決敏感問題(1)；本文主要對隨機確定的聚類初始中心點及離群點敏感問題的解決，保證聚類數(shù)據(jù)集的可用性的同時保護聚類數(shù)據(jù)的隱私，具體細(xì)節(jié)在第2大節(jié)中詳細(xì)說明。

1.4 k-means‖與k均值聚類算法初始中心點選擇對比

k-means‖是對于k均值聚類算法的改進算法，解決了k均值算法對初始中心點敏感的問題。k-means‖聚類算法確定聚類初始中心點的步驟如下所示：

(1)先從數(shù)據(jù)集中隨機選取一個點作為第一個聚類初始中心點c1;

(2)在數(shù)據(jù)集中選擇剩下的k-1個聚類初始中心點。

1)使用歐式距離公式計算數(shù)據(jù)集中的每個數(shù)據(jù)點到c1的距離，取最短距離記為distmin以及所有數(shù)據(jù)點距中心點的距離和sum=∑idisti。

2)以log(distmin) 作為初始代價，循環(huán)計算每個數(shù)據(jù)點與中心點的距離。

3)按式(3)計算下個聚類初始中心點的選擇概率(l為樣本因子，每次選擇的數(shù)據(jù)點個數(shù)，dist(x)為每個數(shù)據(jù)點距樣本中心點的距離)

(3)

按照中心點選取概率確定下個聚類初始中心點，滿足式(3)概率條件的數(shù)據(jù)點有可能不止一個，若存在多個數(shù)據(jù)點，則通過對每個數(shù)據(jù)點賦權(quán)值來確定下個聚類初始中心點。

(3)經(jīng)過(2)選擇出多個數(shù)據(jù)點，根據(jù)將每個數(shù)據(jù)點作為中心點時，簇中數(shù)據(jù)點的個數(shù)作為權(quán)值；根據(jù)權(quán)值大小選擇下一個聚類初始中心點，直到k個初始中心點被選擇出來。

k-means‖聚類算法解決了k均值聚類算法對聚類初始中心點敏感的問題，保證了對數(shù)據(jù)聚類的精確度。

2 基于差分隱私保護的DPk-means‖算法簡析

針對1.3節(jié)k均值聚類算法隨機選擇聚類初始中心點及數(shù)據(jù)集中存在離群點敏感的問題，同時在計算距離每個數(shù)據(jù)點最近的中心點時會泄露隱私的問題[11](過程如圖1所示)，提出解決辦法，標(biāo)記離群點使離群點參與數(shù)據(jù)聚類過程，但是不參與聚類初始中心點的選擇，在k個聚類初始中心點均被選出來之后，再根據(jù)k均值聚類算法進行迭代更新聚類中心點，直到聚類中心點收斂或是不再滿足迭代條件時終止。同時利用滿足差分隱私保護的機制注入適量特定分布的隨機噪聲，使數(shù)據(jù)一定程度的失真，保護聚類數(shù)據(jù)的隱私。

對于圖1中所存在的隱私泄露問題，假設(shè)攻擊者擁有最大背景知識的前提下，對于鄰近數(shù)據(jù)集D={x’,x1,x2,…,xn} 和D’={x1,x2,…,xn}， 攻擊者已經(jīng)知道了鄰近數(shù)據(jù)集D和D’的中心點分別為C和C’，故攻擊者可以根據(jù)式(4)推斷出x’的信息，從而造成數(shù)據(jù)x’的隱私泄露

(4)

圖1 聚類確定中心點過程的隱私泄露說明

針對k均值聚類算法所存在的隱私泄露問題以及算法對于選擇聚類初始中心點敏感的問題，本文提出了保證聚類精確度以及保護聚類數(shù)據(jù)隱私的算法DPk-means‖，利用k均值的改進算法k-means‖聚類算法解決k均值對于聚類初始中心點敏感的問題，結(jié)合文獻[6]中提出的差分隱私對算法中所涉及的隱私泄露的部分注入適量的特定分布的隨機噪聲，以便保證聚類數(shù)據(jù)的隱私，選擇合適的隱私預(yù)算，對聚類數(shù)據(jù)的可用性和隱私性達到平衡狀態(tài)。

其中DPk-means‖的算法流程如圖2所示。

圖2 DPk-means‖算法流程

其中DPk-means‖算法解決了k均值對于初始中心點敏感的問題，標(biāo)記離群點，見于2.2節(jié)；除此之外，為保護數(shù)據(jù)的隱私性，利用差分隱私保護機制，犧牲數(shù)據(jù)的一定可用性，使得該算法在數(shù)據(jù)的可用性和隱私性上達到平衡狀態(tài)，既能夠保證數(shù)據(jù)的一定可用性，也能夠保護聚類數(shù)據(jù)的隱私。

2.1 DPk-means‖算法中離群點處理

當(dāng)大規(guī)模數(shù)據(jù)集中存在離群點時，因為離群點與其它數(shù)據(jù)點間相差較大，會影響數(shù)據(jù)聚類的精確度，直觀上考慮如果數(shù)據(jù)集中的離群點不參與聚類中心點的選擇時，其數(shù)據(jù)的聚類精確度就會提升。所以為保證數(shù)據(jù)聚類精確度，對數(shù)據(jù)集中的離群點進行標(biāo)記，被標(biāo)記的數(shù)據(jù)點不參與聚類初始中心點的選擇，但參與數(shù)據(jù)的聚類過程，利用式(5)進行離群點的標(biāo)記

(5)

2.2 DPk-means‖算法聚類初始中心點選擇

假定現(xiàn)有數(shù)據(jù)集合D={x1,x2,…,xm}∈Rd， 其中d為數(shù)據(jù)維度，指定聚類個數(shù)為k、抽樣因子l，利用式(5)標(biāo)記離群點，選擇距離其它數(shù)據(jù)點較近的數(shù)據(jù)點作為第一個聚類初始中心點c1。記D1(x)={dist1,dist2,…,distn} 為c1跟剩下的數(shù)據(jù)點間的距離，其累加概率分布為

在計算每個數(shù)據(jù)點到中心點的最短距離的過程中會存在圖1的隱私泄露的問題，所以利用差分隱私機制注入適量隨機噪聲即dist′i=disti+noise， 故得到

利用式(3)進行選擇下一個聚類初始中心點，若滿足條件有多個數(shù)據(jù)點，則賦權(quán)值選擇下一個聚類初始中心點，直到k個聚類初始中心點被選擇出來。

DPk-means‖算法是由算法1標(biāo)記離群點選擇聚類初始中心點；利用算法2迭代更新中心點進行數(shù)據(jù)聚類說明如何保護聚類數(shù)據(jù)的隱私安全以及保證數(shù)據(jù)聚類的精確度。

定理1 算法1滿足ε1-差分隱私。

證明：DPk-means‖算法將數(shù)據(jù)點與中心點間的距離作為數(shù)據(jù)相似度的評判標(biāo)準(zhǔn)，故確定聚類初始中心點過程的敏感度為

(6)

其中，d為聚類數(shù)據(jù)集的維度，為了保護聚類數(shù)據(jù)隱私，在確定聚類初始中心點的時候，即在算法1中第(12)行和第(13)行中進行滿足拉普拉斯機制的隨機噪聲添加，由差分隱私的序列組合性質(zhì)可得算法1滿足ε1-差分隱私。

算法1: InitCenter

Input: D={x1,x2,…,xm}-raw dataset;

k-the number of clusters;

l-oversampling factor;

r-the parameter of the outliers;

ε1-privacy budget.

Output:C={c1,c2,…,ck}-cluster initial center point;

D’-clustered dataset.

(1) Normalized D, initialCand the distance setd

(2) dividedε1intoε1/2 andε1/2

(3)fori← 0 to len(D)do

(4) calculate outliers(xi) according to formula (5)

(5)endfor

(6)outlier_set← sort(outliers(xi)) from small to large

(7) mark the first len(D)×routlier_setas outliers

(8)c1← the point of max(outlier_set)

(9)φ← the shortest distance ofxifromc1

(10)forO(log(φ)) timesdo

(11)d={disti|i=1,2,…,N} ← the distance between each pointxiandc1

(12) sum (dist1+dist2+…+distN) + Lap(2Δf/ε1)

(13)d← {disti+Lap(2NΔf/ε1)|i=1,2,3,…,N}

(15)C←ci∪c

(16)endfor

(17)forci∈Cdo

(18)wi←quantity of points in D closer tocithan any other point inC

(19) recluster the weighted points inCintokclusters

(20)endfor

(21)returnC, D’

算法1介紹了DPk-means‖算法如何處理離群點及初始中心點選擇。算法1中的第(3)行～第(7)行就是對離群點的處理，標(biāo)記離群點，使離群點不參與聚類初始中心點的選擇；算法1中第(8)行對k-means‖聚類算法隨機確定的第一個初始中心點進行了改進，避免了算法首次若選擇離群點作為聚類初始中心點時使聚類效果不佳的情況；在選擇剩下的k-1個聚類初始中心點的過程中保護聚類數(shù)據(jù)的隱私安全，算法1的時間復(fù)雜度為O(log(φ))； 選擇滿足概率條件的一個或多個數(shù)據(jù)點賦權(quán)值，根據(jù)權(quán)值大小選擇合適的聚類初始中心點；算法1中第(13)行在計算數(shù)據(jù)點與中心點間的距離進行數(shù)據(jù)間相似度判斷時注入服從拉普拉斯分布的隨機噪聲，使得選擇聚類初始中心點的過程中滿足差分隱私定義，使聚類數(shù)據(jù)隱私泄露的風(fēng)險控制在安全范圍內(nèi)。

2.3 DPk-means‖算法簇中心點迭代更新

根據(jù)算法1確定的聚類初始中心點進行數(shù)據(jù)初步聚類，這時聚類的中心點可能并不是最佳的，故需要根據(jù)劃分好的簇進行迭代更新簇中心點，進行數(shù)據(jù)的重新聚類，直到聚類中心點收斂或是達到迭代條件，利用傳統(tǒng)k均值聚類算法進行聚類中心點更新，并且在該過程中也進行數(shù)據(jù)的隱私保護。

定理2 算法2滿足ε2-差分隱私。

證明：由算法1確定的聚類初始中心點進行數(shù)據(jù)聚類之后，針對聚類好的各個簇，利用k均值聚類算法進行簇中心點的更新移動，算法2中的第(6)行為保護聚類數(shù)據(jù)的隱私安全注入滿足差分隱私定義的隨機噪聲，計算均值作為中心點的過程中的敏感度由式(6)可得Δf=d(d為聚類數(shù)據(jù)集的維度)，同時在更新簇中心點時其敏感度為Δf=1，故算法2中敏感度為d+1，由差分隱私組合性質(zhì)1得出算法2滿足ε2-差分隱私；其詳細(xì)過程由算法2給出：

算法2: UpdateCenter

Input: D’-the output of algorithm 1;

ε2-privacy budget;

C-the output of algorithm 1.

Output:C’ -the set of center point.

(1) InitialC’

(2) dividedε2intoε2/2 andε2/2

(3)foreach cluster in D’do

(4)d← distance fromxitoci

(5)num← the number of the cluster

(7) if AMI(c’i)>AMI(ci)

(8)C←c’i∪C

(9) end if

(10)endfor

(11) update the set of center pointC

(12)returnC

算法2解決了在算法1確定聚類初始中心點將數(shù)據(jù)集劃分為k個簇之后，針對簇中心點更新過程中可能泄露數(shù)據(jù)隱私的問題，其算法時間復(fù)雜度為O(N)；算法2的第(7)行判斷由k均值聚類算法得到的中心點是否比初始中心點的聚類效果更好而決定是否更新簇中心點。

DPk-means‖算法與k均值聚類算法相比，在處理大規(guī)模數(shù)據(jù)聚類任務(wù)時有效地降低了離群點對于聚類精確度的影響，不僅解決了k均值聚類算法對初始中心點敏感的問題，保證了數(shù)據(jù)聚類的精確度，而且還保護了聚類數(shù)據(jù)的隱私安全，提高了算法的適用能力。

2.4 DPk-means‖算法過程中敏感度的確定

在使用算法進行大規(guī)模數(shù)據(jù)聚類時，其中所涉及到注入隨機噪聲，包括用DPk-means‖算法確定聚類的初始中心點，以及確定聚類初始中心點將大規(guī)模數(shù)據(jù)聚類成k個簇后，針對每個簇迭代更新每個簇中心點的過程。

(1)確定k個聚類初始中心點的過程；假定有d維鄰近數(shù)據(jù)集D1和D2；在確定聚類初始中心點的過程中，需要計算每個數(shù)據(jù)點到中心點間的距離，則該過程的敏感度為Δf≤d。

(2)確定k個聚類初始中心點之后，針對由初始中心點確定的每個簇，計算每個簇中數(shù)據(jù)點距中心點間的距離，此時Δf≤d，再迭代更新每個簇中的中心點，確定聚類中心最優(yōu)解，此時Δf=1。

綜上所述，DPk-means‖算法的敏感度為2d+1，在聚類過程中注入Lap((2d+1)/ε)。

定理3 DPk-means‖算法滿足ε-差分隱私。

證明：DPk-means‖算法中泄露數(shù)據(jù)隱私的過程主要為兩個部分：一是為確定聚類初始中心點；在確定中心點的過程中會造成數(shù)據(jù)隱私的泄露；二是在確定k個聚類初始中心點將數(shù)據(jù)集劃分為k個簇之后，迭代更新每個簇中的中心點時會涉及到數(shù)據(jù)隱私的泄露。為了解決整個過程所涉及的隱私泄露的問題，分別給定隱私預(yù)算為ε1和ε2，在對應(yīng)過程利用拉普拉斯噪聲機制注入隨機噪聲；則由差分隱私的定義可知：隨機算法M1對于鄰近數(shù)據(jù)集D和D’的查詢結(jié)果泄露的概率滿足式(7)，數(shù)據(jù)的隱私泄露在安全控制范圍內(nèi)，即

Pr[M1(D)∈Range(M1)]≤eε1×Pr[M1(D’)∈Range(M1)]

(7)

其中，鄰近數(shù)據(jù)集D和D’中數(shù)據(jù)代表數(shù)據(jù)集中的每個數(shù)據(jù)點距離聚類初始中心點的最短距離，D和D’中的數(shù)據(jù)至多有一條數(shù)據(jù)不一樣。在初始中心點確定之后，針對每個簇迭代更新中心點，直至聚類結(jié)果收斂或是達到迭代條件；在更新的過程中注入隨機噪聲保護數(shù)據(jù)隱私，即

Pr[M1(c)∈Range(M1)]≤eε2×Pr[M1(c’)∈Range(M1)]

(8)

其中，c和c’為聚類中心點數(shù)據(jù)集。根據(jù)差分隱私組合性質(zhì)1，則DPk-means‖算法的整個過程滿足(ε1+ε2)-差分隱私。且隱私預(yù)算越小，注入的隨機噪聲量越大，則選取的聚類中心點的誤差就會越大，數(shù)據(jù)聚類的精確度就越小。

3 實驗分析及數(shù)據(jù)

實驗對滿足差分隱私定義的DPk-means‖算法從兩個方面進行分析評估：①動態(tài)調(diào)整ε1和ε2驗證算法的有效性及隱私預(yù)算最優(yōu)的情況；②對比隱私預(yù)算ε1和ε2驗證算法在數(shù)據(jù)聚類過程中數(shù)據(jù)的可用性與隱私性能夠?qū)崿F(xiàn)平衡狀態(tài)。

本文實驗部分采用python語言編程實現(xiàn)，實驗環(huán)境為Windows10 2.50 GHz，實驗數(shù)據(jù)來自UCI machine learning repository中的公開數(shù)據(jù)集，其數(shù)據(jù)集的基本信息見表1。

表1 實驗數(shù)據(jù)集信息

3.1 實驗評價指標(biāo)

(1)本文將采用調(diào)整互信息AMI(adjusted mutual information)作為聚類效果評價指標(biāo)，AMI∈[-1,1]， AMI值越大，則代表使用該算法進行聚類的聚類效果越好。AMI的計算公式如式(9)所示

(9)

其中，MI(mutual information)為互信息，用來表示兩個數(shù)據(jù)分布吻合程度，測試基于聚類算法、預(yù)測標(biāo)簽與真實標(biāo)簽的一致性，MI的計算需要知道真實類別標(biāo)簽的分配情況；假設(shè)U和V表示對N個樣本標(biāo)簽的分配情況，標(biāo)簽分配的不確定性用熵值表示，則U和V的熵值計算如式(10)和式(11)所示

(10)

(11)

(12)

(2)通過隱私預(yù)算的大小進行評估聚類分析數(shù)據(jù)隱私保護水平的高低，由差分隱私的定義可知，隱私預(yù)算越小，注入的隨機噪聲量越大，數(shù)據(jù)的隱私保護水平就越高；反之?dāng)?shù)據(jù)的隱私保護水平越低，數(shù)據(jù)可用性的程度就越高。

本文為驗證DPk-means‖算法的可用性，將通過AMI和隱私預(yù)算兩個方面作為評估指標(biāo)來綜合說明算法的適用性，驗證DPk-means‖算法在保證聚類精確度的情況下，同時保護聚類數(shù)據(jù)的隱私安全。

3.2 實驗分析及比較

本實驗旨在考察DPk-means‖算法進行數(shù)據(jù)聚類過程中，在確定k個聚類初始中心點過程分配隱私預(yù)算ε1及確定初始中心點將數(shù)據(jù)集劃分為k個簇后，涉及到各數(shù)據(jù)點與中心點間距離的計算，更新每個簇中心點的過程中，分配隱私預(yù)算ε2。針對算法對對應(yīng)過程提供不同隱私保護程度，用DPk-means‖算法聚類的精確度來證實算法的可用性，實驗驗證如圖3和圖4所示，針對數(shù)據(jù)集Occupancy detection dataset，給定k=2，在隱私預(yù)算ε1遞減ε2遞增情況下數(shù)據(jù)聚類的中心點分布較集中，數(shù)據(jù)聚類精確度高；而ε1遞增ε2遞減情況下聚類中心點較分散，使得數(shù)據(jù)聚類精確度不高。

圖3 ε1遞減ε2遞增的聚類中心點分布

實驗1：不同隱私保護水平對DPk-means‖算法聚類精確度的影響。

針對k-means‖聚類算法中影響聚類精確度及數(shù)據(jù)隱私會泄露的問題進行分析，利用DPk-means‖算法可以保證聚類的精確度的同時對聚類數(shù)據(jù)的隱私安全也起到保護的作用。將差分隱私應(yīng)用到聚類算法設(shè)計中，實驗分析對選擇初始中心點和迭代更新中心點提供不同的隱私保護水平對數(shù)據(jù)聚類精確度的影響。

由圖5和圖6可以看出，ε2起始值為0.1(若值太小，注入的隨機噪聲量大)，以步長為0.1逐步增大，簇中心點迭代更新注入噪聲的影響比初始中心點選擇時注入隨機噪聲(ε1=0)要大，并且由圖5和圖6可以看出，當(dāng)ε2∈(0.42, 0.52) 時，初始中心點未注入隨機噪聲保護時算法聚類精確度要更高；但總體來說，對初始中心點與確定初始中心點之后，將數(shù)據(jù)劃分為k個簇，對每個簇迭代更新簇中心點時注入服從拉普拉斯分布的隨機噪聲保護數(shù)據(jù)隱私，聚類精確度都比只關(guān)注簇中心點更新注入噪聲的聚類精確度高，在ε1=ε2=0.5時，從數(shù)據(jù)聚類的精確度以及隱私保護水平角度來看，能達到數(shù)據(jù)可用性和隱私保護平衡的狀態(tài)；所以若要保證數(shù)據(jù)聚類精確度及一定的隱私保護水平，保證聚類初始中心點和迭代更新中心點可行的前提下，ε1和ε2應(yīng)該相等且接近0.5，可保證聚類結(jié)果的精確度且對數(shù)據(jù)提供有效的隱私保護水平。

圖5 Occupancy detection dataset聚類AMI指標(biāo)評估

圖6 PEMS-SF數(shù)據(jù)集聚類AMI指標(biāo)評估

實驗2：DPk-means‖算法和DPk-means++算法聚類效果對比。

本實驗旨在比較DPk-means‖算法的有效性，在兩個實驗數(shù)據(jù)集上使用DPk-means‖算法和文獻[5]中基于k均值改進算法k-means++的隱私保護算法——DPk-means++算法進行數(shù)據(jù)聚類精確度比較，且利用DPk-means++算法進行數(shù)據(jù)的聚類分析時，不涉及到對數(shù)據(jù)集中離群點的處理；

實驗結(jié)果如圖7和圖8所示；由圖7、圖8可以看出使用DPk-means‖算法的聚類精確度高于DPk-means++算法，且用DPk-means‖算法能耗費較小的隱私預(yù)算達到較高的聚類精確度，其數(shù)據(jù)聚類精確度能夠較快收斂；相比之下，使用DPk-means‖算法進行離群點的處理之后再進行數(shù)據(jù)聚類能夠給數(shù)據(jù)提供更高的隱私保護級別，同時數(shù)據(jù)聚類的精確度更高。

圖7 Occupancy detection dataset上的AMI運行

圖8 PEMS-SF數(shù)據(jù)集上的AMI運行

4 結(jié)束語

本文既解決了傳統(tǒng)k均值聚類算法對聚類初始中心點敏感的問題，同時對聚類初始中心點的選擇進行了改進，降低了離群點對聚類精確度的影響，同時將差分隱私應(yīng)用于聚類算法中，在確定聚類初始中心點以及每個簇迭代更新中心點的過程中選擇合適的噪聲注入機制，在不同隱私保護程度下揭示了數(shù)據(jù)內(nèi)在的規(guī)律性質(zhì)。通過實驗動態(tài)設(shè)置不同的隱私預(yù)算，對數(shù)據(jù)提供了不同程度的保護情況下聚類結(jié)果的精確度表明，DPk-means‖算法對于存在異常離群點的大規(guī)模數(shù)據(jù)集聚類任務(wù)，能夠保證一定的聚類精確度及數(shù)據(jù)的可用性。