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

王圣節(jié)，巫朝霞

（新疆財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)與數(shù)據(jù)科學(xué)學(xué)院，烏魯木齊 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ù)大都包含用戶的隱私信息，容易遭受不法分子的攻擊進(jìn)而造成隱私泄露。因此，在聚類分析過程中，如何有效保護(hù)用戶數(shù)據(jù)隱私，是當(dāng)下研究熱點(diǎn)，具有現(xiàn)實(shí)意義。

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

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

1 預(yù)備知識

1.1 差分隱私（Difference Privacy，DP）

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

定義1（差分隱私［3］）假設(shè)存在任意一個(gè)隨機(jī)算法M，對于相鄰數(shù)據(jù)集D和D＇，Pr［ES］表示事件ES的隱私披露風(fēng)險(xiǎn)，Range（M）表示隨機(jī)算法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表示映射的實(shí)空間，d表示函數(shù)f的查詢維數(shù)，輸入是一個(gè)數(shù)據(jù)集，輸出是d維查詢結(jié)果。對于任意相鄰數(shù)據(jù)集，則查詢函數(shù)的全局敏感度，式（2）：

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

1.2 差分隱私K-medoids 算法

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

Step 1隨機(jī)選擇p個(gè)點(diǎn)作為初始聚類中心點(diǎn)，并在每個(gè)中心點(diǎn)上加入拉普拉斯噪聲；

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

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

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

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

2.1 相關(guān)概念

假設(shè)存在數(shù)據(jù)集D ＝｛x1，x2，…，xn｝，是包含n個(gè)樣本對象的數(shù)據(jù)集合，每個(gè)樣本對象存在d維屬性特征；數(shù)據(jù)集被劃分為k個(gè)簇類，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個(gè)數(shù)據(jù)對象的第p維屬性。

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

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

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

當(dāng)x ＜0 時(shí)，S（x）＝1，x≥0 時(shí)，S（x）＝0。

樣本點(diǎn)密度圖如圖1 所示。

圖1 樣本點(diǎn)密度Fig.1 Sample point density

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

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

樣本點(diǎn)類簇距離的計(jì)算原則如圖2 所示。

圖2 樣本點(diǎn)類簇距離計(jì)算原則Fig.2 Calculation principle of cluster distance of sample points

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

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

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

2.2 算法思想

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

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

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

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

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

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

算法流程如下：

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

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

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

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

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

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

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

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

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

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

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

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

2.4 安全性分析

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

其中，N是聚類簇?cái)?shù)。

3.3 實(shí)驗(yàn)結(jié)果分析

考慮到不同數(shù)據(jù)集維度不同，數(shù)據(jù)大小指標(biāo)不一樣，對數(shù)據(jù)集做0-1 歸一化處理。分別在3 個(gè)數(shù)據(jù)集上運(yùn)行DPK-medoids 算法以及本文提出的DWDPK-medoids 算法。由于添加服從拉普拉斯分布噪聲的隨機(jī)性，對每個(gè)算法進(jìn)行10 次實(shí)驗(yàn)，取其平均值。DB值越小，證明聚類有效性越高。仿真實(shí)驗(yàn)結(jié)果如圖3～圖5 所示，橫坐標(biāo)代表隱私預(yù)算ε，縱坐標(biāo)代表聚類效果評價(jià)指標(biāo)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í)達(dá)到數(shù)據(jù)可用性和隱私保護(hù)平衡的狀態(tài)。圖4 和圖5 是Blood 數(shù)據(jù)集和WiFi 數(shù)據(jù)集的對比圖，數(shù)據(jù)集越大，DB指數(shù)越大，最終的聚類效果越低。圖5 的DWDPK-medoids 算法在ε ＝1 時(shí)，整體聚類效果趨于穩(wěn)定，而DPK-medoids 算法在隱私預(yù)算ε ＝2 時(shí)，DB指數(shù)開始下降，隨著ε的增大，逐漸與DWDPK-medoids 算法DB指數(shù)相趨近，表明DWDPK-medoids 算法能夠消耗較小的隱私預(yù)算達(dá)到數(shù)據(jù)可用性與隱私保護(hù)的平衡。

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

4 結(jié)束語

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