K-means‖隱私保護(hù)聚類算法

鄭 劍，冷碧玉

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

0 引 言

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

1 相關(guān)知識(shí)

1.1 差分隱私

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

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

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

(1)

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

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

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

(2)

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

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

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

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

1.3 k均值聚類算法

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

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

(2)聚類隨機(jī)確定聚類初始中心點(diǎn)；

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

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

1.4 k-means‖與k均值聚類算法初始中心點(diǎn)選擇對(duì)比

k-means‖是對(duì)于k均值聚類算法的改進(jìn)算法，解決了k均值算法對(duì)初始中心點(diǎn)敏感的問(wèn)題。k-means‖聚類算法確定聚類初始中心點(diǎn)的步驟如下所示：

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

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

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

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

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

(3)

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

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

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

2 基于差分隱私保護(hù)的DPk-means‖算法簡(jiǎn)析

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

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

(4)

圖1 聚類確定中心點(diǎn)過(guò)程的隱私泄露說(shuō)明

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

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

圖2 DPk-means‖算法流程

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

2.1 DPk-means‖算法中離群點(diǎn)處理

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

(5)

2.2 DPk-means‖算法聚類初始中心點(diǎn)選擇

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

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

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

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

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

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

(6)

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

2.3 DPk-means‖算法簇中心點(diǎn)迭代更新

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

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

證明：由算法1確定的聚類初始中心點(diǎn)進(jìn)行數(shù)據(jù)聚類之后，針對(duì)聚類好的各個(gè)簇，利用k均值聚類算法進(jìn)行簇中心點(diǎn)的更新移動(dòng)，算法2中的第(6)行為保護(hù)聚類數(shù)據(jù)的隱私安全注入滿足差分隱私定義的隨機(jī)噪聲，計(jì)算均值作為中心點(diǎn)的過(guò)程中的敏感度由式(6)可得Δf=d(d為聚類數(shù)據(jù)集的維度)，同時(shí)在更新簇中心點(diǎn)時(shí)其敏感度為Δf=1，故算法2中敏感度為d+1，由差分隱私組合性質(zhì)1得出算法2滿足ε2-差分隱私；其詳細(xì)過(guò)程由算法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確定聚類初始中心點(diǎn)將數(shù)據(jù)集劃分為k個(gè)簇之后，針對(duì)簇中心點(diǎn)更新過(guò)程中可能泄露數(shù)據(jù)隱私的問(wèn)題，其算法時(shí)間復(fù)雜度為O(N)；算法2的第(7)行判斷由k均值聚類算法得到的中心點(diǎn)是否比初始中心點(diǎn)的聚類效果更好而決定是否更新簇中心點(diǎn)。

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

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

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

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

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

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

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

證明：DPk-means‖算法中泄露數(shù)據(jù)隱私的過(guò)程主要為兩個(gè)部分：一是為確定聚類初始中心點(diǎn)；在確定中心點(diǎn)的過(guò)程中會(huì)造成數(shù)據(jù)隱私的泄露；二是在確定k個(gè)聚類初始中心點(diǎn)將數(shù)據(jù)集劃分為k個(gè)簇之后，迭代更新每個(gè)簇中的中心點(diǎn)時(shí)會(huì)涉及到數(shù)據(jù)隱私的泄露。為了解決整個(gè)過(guò)程所涉及的隱私泄露的問(wèn)題，分別給定隱私預(yù)算為ε1和ε2，在對(duì)應(yīng)過(guò)程利用拉普拉斯噪聲機(jī)制注入隨機(jī)噪聲；則由差分隱私的定義可知：隨機(jī)算法M1對(duì)于鄰近數(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ù)集中的每個(gè)數(shù)據(jù)點(diǎn)距離聚類初始中心點(diǎn)的最短距離，D和D’中的數(shù)據(jù)至多有一條數(shù)據(jù)不一樣。在初始中心點(diǎn)確定之后，針對(duì)每個(gè)簇迭代更新中心點(diǎn)，直至聚類結(jié)果收斂或是達(dá)到迭代條件；在更新的過(guò)程中注入隨機(jī)噪聲保護(hù)數(shù)據(jù)隱私，即

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

(8)

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

3 實(shí)驗(yàn)分析及數(shù)據(jù)

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

3.1 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

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

(9)

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

(10)

(11)

(12)

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

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

3.2 實(shí)驗(yàn)分析及比較

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

圖3 ε1遞減ε2遞增的聚類中心點(diǎn)分布

實(shí)驗(yàn)1：不同隱私保護(hù)水平對(duì)DPk-means‖算法聚類精確度的影響。

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

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

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

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

實(shí)驗(yàn)2：DPk-means‖算法和DPk-means++算法聚類效果對(duì)比。

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

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

圖7 Occupancy detection dataset上的AMI運(yùn)行

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

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

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