基于密度權(quán)重的優(yōu)化差分隱私K-medoids 聚類算法

王圣節(jié)，巫朝霞

（新疆財經(jīng)大學 統(tǒng)計與數(shù)據(jù)科學學院，烏魯木齊 830012）

0 引言

大數(shù)據(jù)技術(shù)和人工智能飛速發(fā)展，海量數(shù)據(jù)的收集、存儲、發(fā)布和分析越來越容易［1］。聚類分析作為數(shù)據(jù)挖掘的主要任務(wù)之一，已在許多領(lǐng)域內(nèi)得到了廣泛的應(yīng)用，如：社交領(lǐng)域、外賣平臺、電商網(wǎng)購。然而這些領(lǐng)域內(nèi)的數(shù)據(jù)大都包含用戶的隱私信息，容易遭受不法分子的攻擊進而造成隱私泄露。因此，在聚類分析過程中，如何有效保護用戶數(shù)據(jù)隱私，是當下研究熱點，具有現(xiàn)實意義。

針對隱私泄露問題，早期學者提出k-anonymity及其一系列擴展模型，通過對準標識符的泛化處理來實現(xiàn)數(shù)據(jù)的隱藏，但該類模型容易受到一致性攻擊和背景知識攻擊，需要針對新型攻擊不斷完善模型［2］。2006 年，微軟研究院的Dwork［3］提出了差分隱私技術(shù)（Difference Privacy，DP），不關(guān)心攻擊者擁有的背景知識。差分隱私建立在嚴格的數(shù)學證明基礎(chǔ)之上，通過在原始的查詢結(jié)果（數(shù)值或離散型數(shù)值）中添加干擾數(shù)據(jù)（即噪聲），再返回給第三方；加入干擾后，可以在不影響統(tǒng)計分析的前提下，無法定位到具體數(shù)據(jù)，從而防止個人隱私數(shù)據(jù)泄露，進而提供了強大的隱私保護。

Avrim 等人［4］最早將差分隱私保護與聚類技術(shù)相結(jié)合，設(shè)計了一種差分隱私K-means（DPKmeans）算法，布置于SulQ 框架平臺，通過發(fā)布添加合理噪聲的相似值來更新查詢值；李揚、郝志峰［5］等提出了滿足ε-差分隱私保護的IDPK-means 算法，數(shù)據(jù)集平均劃分成p個子集，計算子集加擾后的中心點作為初始中心點，以此提升最終聚類效果；吳偉民［6］等提出了一種基于差分隱私保護的DPDBScan 聚類算法，在添加少量噪聲的情況下，保證了隱私安全與聚類效果；傅彥銘［7］等提出一種基于拉普拉斯機制的差分隱私保護k-means++聚類算法（DPk-means++聚類算法），確保算法在不同維度數(shù)據(jù)集的情況下的聚類可用性和準確性。針對傳統(tǒng)聚類算法存在的隱私泄露的風險，鄭孝遙、陳冬梅［8］等提出一種基于差分隱私保護的譜聚類算法，以實現(xiàn)社交網(wǎng)絡(luò)聚類效果和隱私的平衡；高瑜［9］等則針對數(shù)據(jù)集中噪聲點和離群點地對聚類的影響，將差分隱私與K-medoids 算法相結(jié)合，提出了一種滿足ε-差分隱私保護的聚類算法（DPk-medoids），該算法使用拉普拉斯機制在每次發(fā)布真實的中心點之前向中心點添加噪聲，然后發(fā)布具有隱私保護性質(zhì)的中心點，在一定程度上保證了個人隱私的安全性和聚類的有效性。

1 預(yù)備知識

1.1 差分隱私（Difference Privacy，DP）

差分隱私（Difference Privacy，DP）具有嚴格的數(shù)學定義，是一種通過任何模型、算法添加合理噪聲的數(shù)據(jù)失真隱私保護技術(shù)，對可能被惡意攻擊造成隱私泄露的關(guān)鍵部分添加干擾噪聲，例如模型、算法的輸入輸出、梯度參數(shù)、權(quán)重參數(shù)、目標函數(shù)等，以保證模型、算法的隱私。

定義1（差分隱私［3］）假設(shè)存在任意一個隨機算法M，對于相鄰數(shù)據(jù)集D和D＇，Pr［ES］表示事件ES的隱私披露風險，Range（M）表示隨機算法M的取值范圍，Pm為輸出結(jié)果的所有可能值的集合，Sm為Pm的任意子集，如果算法M 滿足式（1）：

則稱算法M 滿足ε-差分隱私。其中數(shù)據(jù)集D和D＇為至多相差一條數(shù)據(jù)的相鄰數(shù)據(jù)集。ε為隱私預(yù)算，ε越小，則算法M 在D和D＇輸出分布越接近；反之，輸出分布相差越大。

定義2（全局敏感度［10］）對于任何查詢函數(shù)f：D→Rd，R表示映射的實空間，d表示函數(shù)f的查詢維數(shù)，輸入是一個數(shù)據(jù)集，輸出是d維查詢結(jié)果。對于任意相鄰數(shù)據(jù)集，則查詢函數(shù)的全局敏感度，式（2）：

定義3（Laplace 機制［10］）已知任意查詢函數(shù)f：D→Rd，給定數(shù)據(jù)集D，敏感度為Δf，令A(yù)表示隱私聚類算法，若A（D）滿足式（3）：

1.2 差分隱私K-medoids 算法

原有的差分隱私K-medoids 算法在K-medoids聚類過程中對中心點添加少量合適的噪聲，使中心點的披露風險滿足差分隱私定義，以此為最終的聚類結(jié)果提供差分隱私保護?，F(xiàn)有應(yīng)用在用戶數(shù)據(jù)基于差分隱私的K -medoids 聚類算法（DP K -medoids）的具體步驟如下：

Step 1隨機選擇p個點作為初始聚類中心點，并在每個中心點上加入拉普拉斯噪聲；

Step 2計算數(shù)據(jù)集中每個點與中心點之間的距離，并將該點從其最近的中心點分配給簇，形成k個簇；

Step 3在每個集群中，依次選擇一個點來計算用該點替換原始中心點所產(chǎn)生的消耗，并選擇一個消耗少于原始中心點的點作為一個新的中心點，并對該點添加噪聲；

Step 4重復步驟2 和步驟3，直到迭代次數(shù)達到閾值。

2 基于密度權(quán)重的差分隱私保護K-medoids算法

2.1 相關(guān)概念

假設(shè)存在數(shù)據(jù)集D ＝｛x1，x2，…，xn｝，是包含n個樣本對象的數(shù)據(jù)集合，每個樣本對象存在d維屬性特征；數(shù)據(jù)集被劃分為k個簇類，C為簇集合：C ＝｛c1，c2，…，ck｝。

定義4數(shù)據(jù)集D ＝｛x1，x2，…，xn｝ 中，任意兩樣本對象xi和xj之間的距離用歐氏距離d（xi，xj），表示簡記為dij，公式（4）：

其中：i ＝1，2，…，n；j ＝1，2，…，n；p ＝1，2，…，d；xip表示第i個數(shù)據(jù)對象的第p維屬性。

定義5數(shù)據(jù)集D ＝｛x1，x2，…，xn｝ 中，所有樣本對象的平均距離，公式（5）：

其中，n是數(shù)據(jù)集D中樣本點的個數(shù)，dij表示數(shù)據(jù)集中樣本點xi到樣本點xj之間的歐氏距離。

定義6樣本點xi的密度參數(shù)是以數(shù)據(jù)集中任意樣本對象xi為中心，AverDis（D）ρ（i）為半徑的區(qū)域樣本對象的總數(shù)，公式（6）：

當x ＜0 時，S（x）＝1，x≥0 時，S（x）＝0。

樣本點密度圖如圖1 所示。

圖1 樣本點密度Fig.1 Sample point density

定義7設(shè)ui是以樣本對象xi為中心，AverDis（D）為半徑的區(qū)域內(nèi)所有樣本對象集，d（xi，xj）＜AverDis（D），則式（7）：

定義8類簇之間距離si代表樣本點xi與另一局部密度較高的樣本點xj之間的距離。如果樣本點xi的局部密度是最大值，si則定義為max（dij）；否則si被定義為min（dij），公式（8）：

樣本點類簇距離的計算原則如圖2 所示。

圖2 樣本點類簇距離計算原則Fig.2 Calculation principle of cluster distance of sample points

定義9假設(shè)數(shù)據(jù)集D被劃分為k個聚類，聚類Cj（j≤k）的中心點為cj，聚類結(jié)果的誤差平方和是每個聚類的樣本與其聚類中心之間的距離的平方和，即式（9）：

定義10定義選取中心點的密度權(quán)重如式（10）：

通過公式（10）可知，樣本點xi的密度參數(shù)ρi越大，代表點xi周圍的樣本點越密集，則密度權(quán)重wi越大；ui越小表明以樣本對象xi為中心，AverDis（D）為半徑的區(qū)域內(nèi)樣本對象相似程度越高，則密度權(quán)重wi越??；類簇之間距離si越大，即代表兩個類簇之間距離遠，簇中樣本點相似程度低，則密度權(quán)重wi越大。

2.2 算法思想

為減少DP K-medoids 算法在初始中心點選擇的隨機性，影響最終聚類結(jié)果，引入密度權(quán)重這一概念。選取權(quán)重最大的樣本點作為聚類中心，以此來減少隨機選取中心點帶來的不確定性，提高聚類效果。算法步驟如下：

第一步，根據(jù)公式（6）計算數(shù)據(jù)集D中所有樣本點的密度大小，取密度最高的樣本點c1設(shè)置成第一個聚類中心，并將該聚類中心c1添加到中心集合C中，此時中心集合C ＝｛c1｝；然后，將滿足定義7中樣本點到初始簇中心之間的距離小于AverDis（D）條件的所有樣本點添加到當前聚類簇中，并將這些樣本點從數(shù)據(jù)集D中移除；

第二步，根據(jù)公式（6）～公式（8）計算剩余樣本點的密度ρ（i）、簇間平均距離ui和類簇距離si，根據(jù)公式（10）計算剩余樣本點的密度權(quán)重，選擇密度權(quán)重系數(shù)最大的樣本點c2作為第二個聚類中心，將中心點c2添加到中心集合C中，此時中心集合中C＝｛c1，c2｝；同 樣，從 數(shù)據(jù)集中刪除距離小于AverDis（D）的剩余樣本點與該初始聚類中心之間的所有樣本點；

第三步，重復第二步至數(shù)據(jù)集D被清空。此時聚類中心集合C ＝｛c1，c2，…，ck｝，數(shù)據(jù)集被劃分成k個類簇，將得到的聚類數(shù)和聚類中心作為輸入，對數(shù)據(jù)集進行DP K-medoids 運算。

2.3 基于密度權(quán)重的優(yōu)化DP K-medoids 算法流程

DP K-medoids 在傳統(tǒng)K-medoids 算法的基礎(chǔ)上添加了差分隱私保護技術(shù)，但也容易受初始中心點、聚類個數(shù)等因素影響其聚類效果。當輸入數(shù)據(jù)或參數(shù)處理不當時，算法容易陷入局部最優(yōu)解［11］。因此，本文通過對原有算法在初始中心點及聚類個數(shù)的選擇上進行改進，選擇密度權(quán)重較大的樣本點作為初始中心點，再將結(jié)果產(chǎn)生的中心點與簇類數(shù)作為差分隱私的K-medoids 算法的輸入?yún)?shù)，避免初始中心點和k值選擇的隨機性，進而產(chǎn)生具有隱私保護能力的良好聚類結(jié)果。

算法流程如下：

輸入 初始樣本數(shù)據(jù)集D ＝｛x1，x2，…，xn｝

輸出 帶有差分隱私保護的聚類結(jié)果

Step 1輸入原始數(shù)據(jù)集D ＝｛x1，x2，…，xn｝；

Step 2根據(jù)定義7 計算數(shù)據(jù)集中所有樣本點的密度大小，選取密度最大的樣本點c1作為第一個聚類中心，添加到中心集合中，C ＝｛c1｝；

Step 3計算剩余樣本點的密度ρ（i）、簇間距離Si、簇內(nèi)樣本點距離和ui；

Step 4確定第二個聚類中心的條件：根據(jù)定義11 計算得到剩余樣本點的密度權(quán)重最大的樣本點，將其添加到中心集合中，C ＝｛c1，c2｝；

Step 5重復Step3～Step4，直至數(shù)據(jù)集清空，此時C ＝｛c1，c2，…，ck｝；

Step 6將上述步驟得到的聚類中心和聚類數(shù)作為輸入；

Step 7對中心集合C ＝｛c1，c2，…，ck｝ 添加拉普拉斯噪聲，式（11）：

Step 9對于產(chǎn)生的每個初始簇，計算其簇中每個樣本點與簇中其他樣本點的距離和，選擇距離和最小的樣本點，更新為該簇的新中心點，并在新的中心點添加拉普拉斯噪聲；

Step 10重復Step9～Step10，當中心點穩(wěn)定不再發(fā)生改變或是達到預(yù)設(shè)的迭代次數(shù)，終止循環(huán)；

Step 11輸出帶有差分隱私保護的聚類。

2.4 安全性分析

在DWDPK-medoids 算法中，通過添加適量服從拉普拉斯分布的噪聲對中心點進行隱私保護，使最終的聚類結(jié)果滿足差分隱私定義。假設(shè)M（D）和M（D＇）代表經(jīng)過DWDPK-medoids 算法的在數(shù)據(jù)集D和D＇的輸出結(jié)果，D1和D2是兩個只相差一個記錄的相鄰數(shù)據(jù)集，S代表一種隨機的聚類劃分方法，φ（x）為添加噪聲之后的聚類結(jié)果，則有式（12）：

式（12）符合差分隱私的定義。因此，DWDPKmedoids 算法可以提供ε-差分隱私保護。

3 實驗結(jié)果與分析

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

通過實驗對DWDPK-medoids 算法的可用性進行分析。實驗環(huán)境為Windows 10 操作系統(tǒng)，Intel（R）Core（TM）i5-6200U CPU ＠ 2.40 GHz，12 GB機帶RAM，采用Python3.6 編程語言，通過Pycharm專業(yè)版編輯器進行仿真實驗。數(shù)據(jù)來源于UCI Knowledge Discovery Archive database 官網(wǎng)的真實數(shù)據(jù)集，見表1。

表1 實驗數(shù)據(jù)集信息Tabl.1 Experimental data set information

3.2 實驗評價指標

本文采用戴維森堡丁指數(shù)（Davies-Bouldin Index，DBI）指數(shù)作為聚類評價有用性指標。通過計算簇與簇之間相似度，再通過計算所有相似度的平均值，衡量整個聚類結(jié)果的優(yōu)劣。如果簇與簇之間的相似度越高（DBI指數(shù)高），說明簇與簇之間的距離越小，此時聚類效果就越差，反之越好。

Rij表示簇Ci與簇Cj的相似度，公式（13）：

其中，Si代表簇Ci內(nèi)所有樣本點到中心點ci的平均距離，Sij表示第i個簇與第j個簇之間的距離（即兩個簇中心之間的距離）。

其中，N是聚類簇數(shù)。

3.3 實驗結(jié)果分析

考慮到不同數(shù)據(jù)集維度不同，數(shù)據(jù)大小指標不一樣，對數(shù)據(jù)集做0-1 歸一化處理。分別在3 個數(shù)據(jù)集上運行DPK-medoids 算法以及本文提出的DWDPK-medoids 算法。由于添加服從拉普拉斯分布噪聲的隨機性，對每個算法進行10 次實驗，取其平均值。DB值越小，證明聚類有效性越高。仿真實驗結(jié)果如圖3～圖5 所示，橫坐標代表隱私預(yù)算ε，縱坐標代表聚類效果評價指標DB指數(shù)。

圖3 Iris 數(shù)據(jù)集上的DB 指數(shù)圖Fig.3 DB exponential graph on Iris dataset

圖4 Blood 數(shù)據(jù)集上的DB 指數(shù)圖Fig.4 DB exponential graph on blood dataset

圖5 Wifi 數(shù)據(jù)集上的DB 指數(shù)圖Fig.5 DB exponential graph on wifi dataset

圖3 和圖4 為小樣本數(shù)據(jù)集下的算法效果，可見在相同隱私預(yù)算情況下，DWDPK-medoids 算法的DB指數(shù)低于DPK-medoids 算法，聚類效果更加好；在隱私預(yù)算ε ＝2 的情況下，聚類效果開始趨于穩(wěn)定，此時達到數(shù)據(jù)可用性和隱私保護平衡的狀態(tài)。圖4 和圖5 是Blood 數(shù)據(jù)集和WiFi 數(shù)據(jù)集的對比圖，數(shù)據(jù)集越大，DB指數(shù)越大，最終的聚類效果越低。圖5 的DWDPK-medoids 算法在ε ＝1 時，整體聚類效果趨于穩(wěn)定，而DPK-medoids 算法在隱私預(yù)算ε ＝2 時，DB指數(shù)開始下降，隨著ε的增大，逐漸與DWDPK-medoids 算法DB指數(shù)相趨近，表明DWDPK-medoids 算法能夠消耗較小的隱私預(yù)算達到數(shù)據(jù)可用性與隱私保護的平衡。

從實驗結(jié)果可知，DWDPK-medoids 算法在一定程度上的聚類效果優(yōu)于原有的DPK-medoids 算法。DB 指數(shù)越低，則最終聚類結(jié)果所分的簇與簇之間距離越大，代表聚類效果越好。

4 結(jié)束語

差分隱私與K-medoids 算法相結(jié)合在保證聚類效果的前提下，能夠有效保護相關(guān)數(shù)據(jù)的安全性。針對DPK-medo-ids 算法在選取初始中心點和聚類個數(shù)的隨機性和盲目性，本文提出一種基于密度權(quán)重的優(yōu)化差分隱私K-medoids 算法（DWDPKmedoids 算法），通過引入密度權(quán)重的相關(guān)概念，確定初始聚類中心點以及聚類個數(shù)，提高聚類效果。仿真實驗結(jié)果表明，DWDPK-medoids 算法在多樣本和多維度的數(shù)據(jù)集上具有更高的聚類效果。在今后的研究中，應(yīng)當針對算法復雜度進行優(yōu)化，在保障數(shù)據(jù)隱私的前提下添加少量噪聲獲得更好的聚類效果。