K-means‖隱私保護聚類算法

鄭 劍，冷碧玉

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

0 引 言

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

1 相關知識

1.1 差分隱私

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

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

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

(1)

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

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

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

(2)

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

1.2 差分隱私組合性質

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

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

1.3 k均值聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

(3)

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

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

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

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

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

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

(4)

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

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

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

圖2 DPk-means‖算法流程

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

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

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

(5)

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

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

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

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

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

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

證明：DPk-means‖算法將數據點與中心點間的距離作為數據相似度的評判標準，故確定聚類初始中心點過程的敏感度為

(6)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(7)

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

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

(8)

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

3 實驗分析及數據

實驗對滿足差分隱私定義的DPk-means‖算法從兩個方面進行分析評估：①動態調整ε1和ε2驗證算法的有效性及隱私預算最優的情況；②對比隱私預算ε1和ε2驗證算法在數據聚類過程中數據的可用性與隱私性能夠實現平衡狀態。

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

表1 實驗數據集信息

3.1 實驗評價指標

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

(9)

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

(10)

(11)

(12)

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

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

3.2 實驗分析及比較

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

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

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

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

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

圖5 Occupancy detection dataset聚類AMI指標評估

圖6 PEMS-SF數據集聚類AMI指標評估

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

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

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

圖7 Occupancy detection dataset上的AMI運行

圖8 PEMS-SF數據集上的AMI運行

4 結束語

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