基于差分隱私保護的二分k均值聚類算法研究

馬文博, 巫朝霞

(新疆財經大學 統計與數據科學學院， 烏魯木齊 830011)

0 引 言

當下數據科學的發展一日千里，所產生的數據也呈爆炸式增長，結合傳統統計學的理論基礎與現代計算機科學的計算優勢所產生的衍生學科在處理復雜問題的能力上也有了質的飛躍。機器學習、數據挖掘、人工智能等新的理論和技術也應運而生，為大數據的信息挖掘與應用帶來了新的路徑和視野，新理論、新技術的應用極大提升了社會服務的效率、增強了商業運營的能力、促進了相關科學研究的發展，但對大數據的濫用及相關的隱私泄漏問題也日漸顯現。用戶舉手投足間產生的海量信息中往往包含著大量的敏感信息，如；金融信息、醫療信息、行為特點信息等，而對這些敏感信息的濫用將會切實危害到信息提供者的隱私安全，不利于大數據行業的健康發展，大數據的利用與隱私保護已經成為了一對尖銳的問題，保護數據隱私的情況下高效的利用數據是當下研究的重要關注點[1-2]。

隱私保護的發展也決定了數據科學的應用范圍與發展方向。目前隱私保護方法可以分為密碼學方法、信息隱藏方法以及數據處理方法。密碼學方法主要是研究數據的加解密方案，以及不同的密鑰分配管理機制，包括同態加密、對稱加密等[3-4]；信息隱藏方法則通過對原始數據的形態變換，將隱私信息隱寫與公開信息再進行傳輸進而保護原始信息，如數字水印等[5]；數據處理方法是減少隱私數據之間存在的關聯性，通過添加數據擾動、數據匿名化等方法實現隱私保護。防止復雜網絡分析、深度學習等大數據計算的過程中泄露敏感信息。Dwork在數據擾動的思想下于2006年提出了差分隱私保護技術，是可由嚴密數學邏輯證明的數據擾動隱私保護技術[6]。通過對所要處理的數據添加符合隱私預算ε的噪聲，從而實現在假定攻擊者擁有最大知識背景的情況下依然能對數據進行有效保護，使數據在保證其可用性的同時不會泄露敏感信息。

在大數據處理分析中，聚類分析是數據挖掘的核心問題之一[7]。k-means作為基于劃分聚類的經典算法，有著原理直觀、可解釋性強、算法復雜度低、收斂速度快、對于處理大數據具有良好的伸縮性等諸多優勢。但傳統k-means算法對初始點的選取非常敏感，聚類性能易受初始節點的影響，在算法迭代過程中存在隱私泄露的安全隱患[8]。傅彥銘等[9]人提出了一種基于拉普拉斯機制的差分隱私保護k-means++算法，保證了在不同安全級別下算法的可用性；李洪成[10]等人針對傳統隱私保護方法無法應對任意背景知識下惡意分析的問題，提出了分布式環境下滿足差分隱私的k-means算法；馬銀方[11]等人提出了基于差分隱私保護的KDCK-medoids動態聚類算法，解決k-medoids算法不能對動態數據進行聚類的問題；Dwork[12]等人提出了差分隱私保護k-menas算法中隱私預算的分配方法。

本文針對k-means算法可能存在的隱私泄露以及易受初始點選取影響的缺陷，提出了一種基于拉普拉斯噪聲機制的差分隱私保護二分k-means算法(DP Bi-k-means)，在聚類的過程中實現了差分隱私保護機制。實驗結果表明，該算法與傳統差分隱私保護k-means算法相比，可以避免聚類結果受初始點的影響陷入局部最優解，從而優化聚類效果，并為聚類分析提供了嚴格的隱私保護。

1 差分隱私相關理論

1.1 差分隱私定義

差分隱私是基于不同機制對不同類型的數據進行失真的隱私保護方法。通過對原始數據、算法參數、以及輸出結果等關鍵信息添加服從特定分布的噪音，使在全體數據集中任意添加或刪除一條數據并不顯著改變該數據集的信息熵，使攻擊者在擁有最大背景知識時也無法準確判斷某條數據是否在該數據集中，從而保證了所有隱私信息的安全[6]。滿足差分隱私的數據集能夠抵抗對隱私數據的分析，具有信息論意義上的安全性。

定義1ε-差分隱私

假設D和D′是兩個具有相同數據結構且差別為一條數據記錄的相鄰數據集，函數M為隨機函數，其取值范圍表示為Range(M)，存在集合S，且S∈Range(M)，E為查詢函數，Pr(E)表示隱私泄露的風險。

若隨機算法M對數據集D和數據集D′進行計算，得到的輸出結果M(D)和M(D′)使M(D)∈range(M)，M(D′)∈range(M)成立，且滿足式(1)：

Pr[M(D)∈S]≤eε×Pr[M(D′)∈S]

(1)

則稱算法M滿足隱私參數為ε的差分隱私[6]。在ε確定的情況下，差分隱私的嚴格數學定義保證了算法M在計算時其輸出結果的概率分布是隨機相似的。即使遭到最大背景知識的差分攻擊，也能對數據集中任意一條的數據進行保護。由公式(1)可知隱私參數ε的值越小，M(D)與M(D′)的概率分布越相似，隨機算法M的隱私保護能力越強。

風險泄露曲線如圖1所示，可知在位置參數相同的情況下兩曲線的差為|eε|。即滿足任意隨機算法在相鄰數據集上輸出同一個結果的概率的比值Z∈[e-ε,eε]。

圖1 隱私泄露風險曲線

定義2全局敏感度

敏感度是差分隱私保護中的一個重要參數，全局敏感度是指對數據集中任意一個數據進行修改時對查詢結果造成的最大影響。全局敏感度與查詢函數性質相關，與數據集無關。

設f是將d維數據集D映射為實數空間內一個d維向量的查詢函數，對于任意只相差一條數據的鄰近數據集D和D′，函數f的全局敏感度，式(2)：

(2)

對于全局靈敏度較小的函數，只需要添加少量的噪聲，就可以使在更改一條數據時對查詢結果的影響具有不可分辨性。然而，當全局靈敏度較大時，需要向輸出添加大量的噪聲，以滿足ε差分隱私。為了避免因添加過量噪音導致數據可用性變差，針對不同的問題常常引入不同的噪聲機制。

定義3拉普拉斯機制

差分隱私技術通常通過拉普拉斯機制(Laplace Mechanism)實現對數值型數據的隱私保護。在此機制下可以對原數據或隨機函數的查詢結果添加服從拉普拉斯分布的隨機噪聲，來保證滿足ε的差分隱私。當噪聲函數的概率密度為公式(3)時，則此噪聲函數服從拉普拉斯分布記為x∽Lap(Δf/ε)

(3)

其中，位置參數為u，尺度參數為b(b>0)，式(4)：

(4)

給定數據集D時，設有查詢函數F，全局敏感度為Δf，根據差分隱私定義可得經ε的差分隱私保護的查詢函數M，式(5)：

(5)

由公式(5)可知在敏感度已知的情況下，在ε的差分隱私保護的查詢函數M中，隱私參數ε越小，添加的噪聲越多，隱私保護程度越高。

1.2 差分隱私的特性

隱私保護問題往往是復雜的系統工程。對于多層次的數據結構，多樣的查詢需求，需要多次使用差分隱私保護算法才能保證數據的隱私安全。為了平衡算法的可用性與算法隱私保護能力，需要借助差分隱私保護算法的兩個組合性質合理的設置隱私參數ε。

性質1序列組合性

如果給定一個組合函數S(s1(c),s2(c),s3(c)…sn(c))，對于給定的數據集C進行差分隱私保護，每一個獨立的函數s1,s2,s3…sn都滿足差分隱私，且差分隱私預算分別為ε1,ε2,ε3…εn則對于整體的組合函數都滿足ε差分隱私，式(6)：

(6)

性質2并行組合性

如果給定一個組合函數S(s1(C1),s2(C2),s3(C3)…sn(Cn))，對給定的不相交的數據集C1,C2,C3…Cn進行差分隱私保護，每一個獨立的函數s1,s2,s3…sn都滿足差分隱私，且差分隱私預算分別為ε1,ε2,ε3…εn，則對于整體的組合函數都滿足ε差分隱私，式(7)：

(7)

2 基于拉普拉斯機制保護的二分k-均值聚類算法

二分k均值聚類算法(Bisecting k-means)是傳統k-means聚類算法結合層次聚類算法思想中分裂策略的改進算法。首先使所有對象初始化為一個簇，自上而下遞歸地進行分裂，將原始簇一分為二；再選擇其中一個新的簇進行以上操作。因為聚類的誤差平方和(SSE)能夠衡量聚類性能，該值越小表示數據點越接近于其質心，聚類效果就越好；選擇哪一個簇進行劃分取決于對其劃分是否可以最大程度降低SSE的值；重復該過程直到分出了指定的k個簇。相對于k-means聚類算法，該算法最后優化時采用的質心是多次二分產生的，避免了因隨機產生質心而得到局部最優化結果。

2.1 k-means聚類算法收斂性證明

給定觀測點集D={x1,x2,…,xn}，k-means算法針對聚類所得到的簇劃分C={C1,C2,…,Cn}最小化平方誤差，式(8)：

(8)

假設簇數k已確定，使用誤差平方和(SSE)作為目標函數，可以變形獲得畸變函數，式(9)：

(9)

其中，x(i)為觀測集中第i個觀測，c是觀測對象屬于的類。

基于最短距離判斷可知，c=argmin‖x-μj‖2,μc為聚類簇的中心點，對畸變函數求偏導?μj(j=1,2,…,k)，式(10)：

(10)

令畸變函數偏導為0，可以求得極值點，式(11)：

(11)

證得收斂。

從k-means的算法可以發現，誤差平方和函數(SSE)是一個嚴格的坐標下降過程。每一次朝一個變量Ci尋找最優解，式(12):

(12)

其中，m是Ci所在簇的元素的個數。

即當前聚類的均值就是當前方向的最優解，這與k-means的每一次迭代過程一樣，保證誤差平方和函數(SSE)每一次迭代時，都會減小，最終收斂。

由于誤差平方和函數(SSE)是一個非凸函數，所以不能保證收斂于全局最優解。

2.2 二分k均值算法隱私泄露風險

二分k-means聚類算法是基于距離的聚類方法，其更新迭代聚類中心點的過程與傳統k-means相同，其中迭代參數sum為分類過程中簇內的點到簇中心點的距離之和，num為分類過程中簇內點的個數，Ck為聚類過程中的簇中心，式(13)：

(13)

由公式(13)可知，二分k均值算法在基于背景知識對聚類中心點的攻擊下會泄露整體數據集從而發生隱私泄露[8]。

2.3 差分隱私保護的二分k均值(DP Bi-k-means)算法設計

針對二分k均值聚類算法在聚類過程中存在數據泄露的問題，ε-差分隱私保護二分k均值聚類算法通過在算法迭代中心點添加噪音，達到對中心點數據的保護，算法的步驟如下：

步驟1預設聚類個數k；

步驟2將整體數據劃分為一個簇，計算質心及總誤差平方和；

步驟3使用k-means算法將這個簇二分為兩個簇；

步驟4計算該簇一分為二之后的總誤差平方和；

步驟5選擇滿足條件的可以分解的簇進行劃分；

步驟6重復步驟3-步驟5操作，直到達到指定的簇數k為止。

迭代過程中分別計算各簇迭代參數sum與num并分別添加拉普拉斯噪音，從而得到新的聚類中心，式(14)：

(14)

通常在步驟5時會選擇可以使總誤差平方和最小的簇進行劃分，本文選用劃分后簇內誤差平方和最大的簇進行劃分。實驗證明：在保證其聚類效果優于傳統k-means算法的情況下，相較于通常的二分k-means算法提高了算法運行效率。

2.4 差分隱私保護的二分k均值(DP Bi-k-means)算法安全性證明

DP Bi-k-means算法通過向迭代過程添加服從拉普拉斯的噪音實現對算法敏感參數的保護，進而保護整體數據集，其中隱私保護強度由全局敏感度Δf、隱私參數ε決定。由定義2可知：在算法迭代中心點時，敏感度參數Δf=1。同一簇內計算距離之和的敏感度Δf≤M，M為數據集的特征個數，所以DP Bi-k-means算法的全局敏感度為M+1。

根據定義1，對隨機算法M更新的迭代中心點進行計算可得式(15)；

Pr[M(D)∈S]≤eε×Pr[M(D′)∈S]

(15)

根據性質1，差分隱私的序列組可得式(16)：

(16)

即DP Bi-k-means算法滿足ε-差分隱私。

3 實驗結果及分析

通過3個方面對差分隱私保護的二分k均值算法(DP Bi-k-means)進行實驗評價：

(1)DP Bi-k-means與DP k-means在隱私參數動態變化的情況下對比聚類效果，分析新算法的算法特征；

(2)分析在相同隱私參數條件下新算法相比傳統算法的抗局部最優解的能力；

(3)通過使用不同的分類策略提高新算法的運行效率。

實驗平臺為windows10操作系統，cpu3.2 GHZ，8 GB內存，采用python語言及相關庫進行模擬實驗。數據集來自UCI機器學習實驗室的IRIS數據集和Wine數據集，見表1。

表1 數據集信息

3.1 實驗評價指標

為了對DP Bi-k-means算法的聚類效果進行綜合評價，本文以DP k-means作為對比算法，分別從內部評估法中選取輪廓系數(Silhouette Coefficient)、DB指數(Davies-Bouldin score)、CH指數(Calinski-Harabasz Index)、外部評估方法中選取調蘭德指數(Adjusted Rand Index)來對兩種差分隱私聚類算法進行多方面比較。

通過對DP Bi-k-means與DP k-means的誤差平方和(SSE)進行比較，來分析新算法的聚類性能與魯棒性，并對算法改進后選用劃分后簇內誤差平方和最大的簇進行劃分的運行效率進行實驗分析。

3.2 實驗結果

3.2.1 聚類效果分析

實驗中通過控制隱私預算參數ε，進而在不同的隱私保護水平下對算法進行聚類效果的比較實驗。

實驗在指定分類個數k=3的預設下，在隱私參數ε逐步增加的情況下對試驗指標進行測度。由于在k均值聚類算法中超參數只有聚類個數k，所以實驗結果完全受隱私預算參數ε、算法本身以及隨機誤差決定。通過直接度量聚類效果的角度進行實驗分析，統計算法的內部指標輪廓系數、DB指數和CH指數。經實驗得到輪廓系數圖如圖2所示，可知在ε變動的情況下，相比DP k-means算法本文提出的DP Bi-kmeans算法輪廓系數整體更接近于1，分類目標與所劃分類別更加匹配，且波動程度較小聚類效果更穩定；在相同實驗條件下得到兩種聚類算法的CH系數圖如圖3所示，可知DP Bi-k-means算法的CH系數更大，各分類內部越緊密，各分類之間越疏松，聚類能力較DP k-means算法有一定優勢；實驗分析DB指標得到DB指標圖如圖4所示，DP Bi-k-means算法的DB指數相較于與DP k-means算法的DB指數更小，各分類之間距離更大，分類結果更好。

圖2 輪廓系數圖

圖3 CH指標圖

圖4 DB指標圖

在將原始IRIS數據分類結果作為外部參考，將兩種算法的調蘭德指數(ARI)作為外部評估指標，實驗得出的ARI指數圖如圖5所示，可以觀察到在隱私參數逐步增加，隱私保護水平在逐漸減小的過程中DP Bi-k-means算法的ARI指數相比DP k-means的ARI指數始終更大，DP Bi-k-means算法的分類之間聚類的重疊程度更低。

圖5 調整蘭德指數圖

通過對兩種算法進行內部、外部評估，得知DP Bi-k-means相較于DP k-means有著更好的聚類性能。

3.2.2 魯棒性分析

在對IRIS數據集聚類過程中進行兩種算法的魯棒性分析，在數據集聚類簇數k=3時進行實驗，動態變化的隱私參數ε對DP Bi-k-means算法與DP k-means算法的總誤差平方和(SSE)的影響情況如圖6所示，可以觀察到DP Bi-k-means算法相較于DP k-means算法，平均誤差平方和降低61.15，且波動幅度更小，所以DP Bi-k-means算法有著更好的魯棒性。

圖6 誤差平方和波動圖

3.3.2 聚類效率分析

算法運行效率與相同條件下算法運行時間有直接聯系，本文對比了兩種劃分方法在相同條件下的運行時間，運行時間圖如圖7所示 ，DP Bi-k-means 1是選用劃分后簇內誤差平方和最大的簇進行劃分，DP Bi-k-means 2則為使用總誤差平方和最小的簇進行劃分，本文算法選擇劃分后簇內誤差平方和最大的簇進行劃分。由圖7可知DP Bi-k-means 1比DP Bi-k-means 2運行時間更短，證明在保證其聚類效果優于傳統k-means算法并且滿足差分隱私保護的情況下，相較于一般二分k均值算法的劃分方式提高了算法的運行效率。

圖7 運行時間圖

4 結束語

本文針對差分隱私保護的k均值聚類算法易受初始點影響，導致算法整體陷入局部最優解的問題，結合分層聚類的思想提出了一種差分隱私保護二分k均值聚類算法。在動態改變隱私參數的實驗中與傳統算法進行對比，由實驗結果可知，新算法在保證其隱私保護能力的前提下，提高了聚類效果，增強了聚類算法的魯棒性，并通過選取合適的簇劃分規則提高了算法的運行效率，并證明新算法在不同隱私保護水平的情況下都有較好的性能，下一步將繼續研究基于此算法的融合算法。