改進的密度峰值聚類算法的差分隱私保護方案

葛麗娜, 陳園園, 王 捷,2, 王 哲

(1.廣西民族大學 人工智能學院,廣西 南寧 530006;2.廣西民族大學 網(wǎng)絡通信工程重點實驗室,廣西 南寧 530006;3.廣西民族大學 廣西混雜計算與集成電路分析設(shè)計重點實驗室,廣西 南寧 530006)

聚類分析是數(shù)據(jù)挖掘中的關(guān)鍵技術(shù)之一,其主要思想是將數(shù)據(jù)集劃分為不同的簇,使得同一簇內(nèi)的數(shù)據(jù)相似度較高、不同簇間的數(shù)據(jù)相似度較低[1]。聚類分析的廣泛應用[2-4]給數(shù)據(jù)擁有者帶來了巨大的利益。但是,若這些數(shù)據(jù)被攻擊者截獲,并惡意利用,將對數(shù)據(jù)的提供者產(chǎn)生不利影響,甚至危及人身財產(chǎn)安全。因此,如何在聚類分析中保護用戶的隱私安全成為了聚類分析的一個熱門方向[5]。

差分隱私是2006年由Dwork[6]針對傳統(tǒng)的隱私保護模型無法應對新型攻擊方式而提出的一種具有嚴格的可證明性的隱私保護模型。該模型通過對原始數(shù)據(jù)或者數(shù)據(jù)的發(fā)布結(jié)果添加符合要求的隨機噪聲,使得攻擊者即使已知除了目標用戶的數(shù)據(jù)以外的其他所有數(shù)據(jù),也無法獲取目標用戶的數(shù)據(jù),達到保護用戶的隱私數(shù)據(jù)的目的。

李楊等[7]為了提高DPK-means算法的可用性,降低算法中由于添加了隨機噪聲而對初始聚類中心點的選取造成的影響,先將數(shù)據(jù)集均分為m個子數(shù)據(jù)集,再對各子集添加噪聲后的聚類中心點進行計算,并將這些點作為初始聚類中心點,提出了IDPK-means算法,但是算法中m的值需要人為選取。

密度峰值聚類 (clustering by fast search and find density peaks, DPC)算法[8]是2014年提出的一種基于密度的聚類算法,該算法僅需輸入1位參數(shù)、不存在迭代,且能夠自動發(fā)現(xiàn)類簇中心,實現(xiàn)任意形狀數(shù)據(jù)的高效聚類,因此廣泛應用于各個領(lǐng)域。但是,DPC算法也存在一些不足,如輸入?yún)?shù)截斷距離的值按照經(jīng)驗選取、聚類中心點需要人為選取以及非聚類中心點分配采取一步策略等,并且算法存在聚類時易導致敏感數(shù)據(jù)泄露的問題。

針對改進的DPC算法的非聚類中心點分配以及算法泄露隱私的問題,本文引入可達概念,對非聚類中心點的分配策略進行改進,并在算法計算數(shù)據(jù)點局部密度的步驟中添加符合要求的Laplace隨機噪聲,使得算法滿足差分隱私保護。

1 相關(guān)知識

1.1 密度峰值聚類算法

密度峰值聚類(DPC)算法基于以下2個假設(shè):①聚類中心被低密度鄰居數(shù)據(jù)點包圍;②聚類中心與另一個密度更高的數(shù)據(jù)點之間的距離足夠遠。DPC算法的主要步驟包括:密度距離計算、聚類中心選取、剩余數(shù)據(jù)點分配。

Step 1 密度距離計算。DPC算法根據(jù)式(1)計算出數(shù)據(jù)點xi的局部密度ρi,當數(shù)據(jù)集規(guī)模較小時由式(2)計算ρi。由式(3)計算其到更高密度數(shù)據(jù)點的距離δi。

(1)

(2)

(3)

式中:dc為截斷距離;dij為數(shù)據(jù)點xi到數(shù)據(jù)點xj之間的歐氏距離。dc的取值:dc的值使得數(shù)據(jù)點的平均近鄰個數(shù)為整個數(shù)據(jù)集數(shù)據(jù)點總數(shù)的1%～2%[9]。

Step 2 聚類中心選取。聚類中心選取包括2種方法:①決策圖法是算法根據(jù)局部密度和距離生成的以局部密度為橫軸、距離為縱軸的決策圖,再根據(jù)決策圖人工選取最佳聚類中心的方法;②公式法[8]是根據(jù)式(4)生成決策度量γi,再將決策度量進行降序排序,選取前k個值對應的數(shù)據(jù)點作為聚類中心的方法。

γi=ρi×δi。

(4)

Step 3 剩余數(shù)據(jù)點分配。將剩余的非聚類中心點與距離該點最近并且擁有更高局部密度值的數(shù)據(jù)點歸為一類。

改進的密度峰值聚類 (adaptive clustering by fast search and find of density peaks, AdDPC)算法針對DPC算法選取聚類中心點需要人為參與的問題,將加權(quán)思想引入決策度量計算中,避免了人為參與選取聚類中心點。AdDPC算法的聚類步驟如下。

Step 1 計算出數(shù)據(jù)點間的歐氏距離矩陣。

Step 2 分別根據(jù)式(2)和式(3)計算出數(shù)據(jù)點xi的局部密度ρi和距離δi的值,并對ρ和δ做歸一化處理,生成決策圖。

Step 3 根據(jù)式(4)計算出決策度量γ的值,歸一化處理得到γ*,將γ*降序排序。

Step 4 根據(jù)式(5)計算出γ*的斜率變化率kiti,生成聚類中心點判別圖:

kiti=(i-η)ki,i=1,2,…,50。

(5)

式中:η為加權(quán)因子。

(6)

Step 6 將剩余數(shù)據(jù)點分配到擁有更高局部密度且距離其最近的點所在的類簇中。

1.2 差分隱私

差分隱私[6]是一種擁有嚴格數(shù)學定義以及可證明性的信息保護技術(shù),該模型的提出基于一種假設(shè):數(shù)據(jù)攻擊者具有最大背景知識,即攻擊者知道除了需要保護的敏感信息以外的所有信息。

定義1ε-差分隱私[6]。設(shè)隨機算法M,對于任意2個鄰近數(shù)據(jù)集D和D′,若滿足式(7),則稱算法M滿足ε-差分隱私。

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

(7)

式中:Pr[·]表示事件發(fā)生的概率;S∈Range(M),Range(M)表示隨機算法M的所有輸出的集合;ε為隱私預算,表示隱私保護程度,其值與隱私保護程度成反比。

定義2全局敏感度[10]。設(shè)有查詢函數(shù)f:D→Rd,對于任意一對鄰近數(shù)據(jù)集D和D′,函數(shù)f的全局敏感度Δf為

(8)

式中:‖·‖1為1-范數(shù)距離。全局敏感度Δf表示函數(shù)f(·)在鄰近數(shù)據(jù)集上查詢結(jié)果的差異程度,差分隱私中所添加噪聲的大小受全局敏感度的影響。

定義3Laplace機制[6]。設(shè)有隨機函數(shù)f(·),f(D)為其對數(shù)據(jù)集D查詢返回的輸出結(jié)果,則Laplace機制定義為

(9)

Laplace分布的概率密度函數(shù)的表達式為

(10)

2 改進的密度峰值聚類算法的差分隱私保護方案

由AdDPC算法的步驟可以看出,該算法隱私泄露的關(guān)鍵是局部密度ρ。若攻擊者擁有除了目標數(shù)據(jù)點以外的所有數(shù)據(jù)點信息,則攻擊者可以通過局部密度ρ的定義公式,計算出目標數(shù)據(jù)點與其他數(shù)據(jù)點的距離,進而推出目標數(shù)據(jù)點的相關(guān)信息。若攻擊者刪除數(shù)據(jù)集中目標數(shù)據(jù)點,則其余數(shù)據(jù)點的局部密度ρ會相應減小,得到其余數(shù)據(jù)點在刪除目標數(shù)據(jù)點前后的局部密度差,獲取目標數(shù)據(jù)點與其余數(shù)據(jù)點間的距離,從而推斷出目標數(shù)據(jù)點的真實信息。

由對AdDPC算法的隱私泄露問題分析可知,當數(shù)據(jù)擁有者發(fā)布算法聚類的局部密度ρ時,可能會導致隱私數(shù)據(jù)的泄露。而本文算法在局部密度的計算過程中添加Laplace隨機噪聲,使得該算法滿足差分隱私保護的要求,進而達到保護隱私信息的目的。

AdDPC算法的聚類原理是尋找具有較大局部密度,同時將距離其他更高局部密度點較遠的數(shù)據(jù)點作為聚類中心,再將其余數(shù)據(jù)點劃分到局部密度比該點大且相距較近的點所在的類簇中。當數(shù)據(jù)集分布較為均勻,或者數(shù)據(jù)集中某一類簇存在幾個局部密度較大且距離其他局部密度更高的點較遠的點,AdDPC算法即使選取了正確的聚類中心點,也可能會出現(xiàn)部分非聚類中心點歸類錯誤的問題。在AdDPC算法中,非聚類中心點的分配是采用一步分配策略,容易引起“多米諾效應”,即密度大的數(shù)據(jù)點若分配錯誤會導致密度較小的數(shù)據(jù)點歸類錯誤的問題,從而影響算法的聚類性能,如圖1所示。圖1(a)為Flame數(shù)據(jù)集的標準分類圖,圖1(b)為AdDPC算法對Flame數(shù)據(jù)集的錯誤聚類結(jié)果圖。

圖1 Flame數(shù)據(jù)集聚類

對于AdDPC算法的非聚類中心點分配問題,本文引入DP-rcCFSFDP算法[11]中的可達定義,將其應用于非聚類中心點的歸類,從而提高AdDPC算法的聚類效果,基于此,提出一種基于局部密度加噪的密度峰值聚類差分隱私保護算法(differential privacy preserving algorithm of clustering by fast search and find density peaks based on local density adding noise, DP-DPCL)。DP-rcCFSFDP算法的相關(guān)定義如下。

定義4鄰域點。給定數(shù)據(jù)點pi,在以pi為圓心、E為半徑的鄰域中的所有數(shù)據(jù)點稱為pi的鄰域點。

定義5可達。給定一串數(shù)據(jù)點s1,s2,…,sn,若每個數(shù)據(jù)點si+1為數(shù)據(jù)點si的鄰域點時,則稱數(shù)據(jù)點sn到數(shù)據(jù)點si可達。

DP-DPCL算法具體步驟如下。

Step 1 對輸入數(shù)據(jù)集預處理,初始化數(shù)據(jù)點間的歐氏距離,根據(jù)式(2)計算出數(shù)據(jù)點的局部密度。

Step 2 選取合適的隱私預算ε,根據(jù)局部密度ρ的敏感度,生成符合Laplace分布的噪聲,并將隨機噪聲添加至局部密度ρ中,記為l_ρ。

Step 3 將l_ρ降序排序,并按照式(3)計算距離δ,根據(jù)l_ρ和δ生成決策圖。

Step 4 根據(jù)式(4)計算決策度量γ,歸一化后得到γ*,將γ*降序排序。

Step 5 根據(jù)式(5)計算γ*的斜率變化率kiti,生成聚類中心點判別圖。

Step 7 將剩余數(shù)據(jù)點分配到與其距離更近且擁有更高局部密度的數(shù)據(jù)點所在類簇,生成初始聚類結(jié)果。

Step 8 對初始聚類結(jié)果進行遍歷,若存在數(shù)據(jù)點對可達且不在一個類簇中,則將局部密度值小的數(shù)據(jù)點歸類為局部密度值大的數(shù)據(jù)點所在類,得到最終的聚類結(jié)果。

在DP-DPCL算法中,局部密度每次所添加的噪聲是隨機生成的,而由于加噪導致輸出的局部密度值不同,這樣使得攻擊者難以依靠獲得的局部密度差值推導出目標數(shù)據(jù)點的真實信息。由于數(shù)據(jù)點到密度更高點的距離δ的值也會受到局部密度值變化的影響,從而進一步降低了隱私泄露的風險。

在DP-DPCL算法中使用的差分隱私保護技術(shù)中的Laplace機制是由算法的敏感度Δf以及隱私預算ε控制生成的滿足Laplace分布的隨機噪聲。敏感度是指在數(shù)據(jù)集中增加或減少任意一個數(shù)據(jù)點對聚類結(jié)果的最大影響。對于任意一對鄰近數(shù)據(jù)集,對2個數(shù)據(jù)集進行局部密度計算時,根據(jù)局部密度定義公式可知,數(shù)據(jù)點局部密度的最大差值為1,因此,局部密度的敏感度Δf=1。

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

3.1 算法的差分隱私性證明

DP-DPCL算法的差分隱私性證明如下:

假設(shè)數(shù)據(jù)集D和D′為一對鄰近數(shù)據(jù)集,R(D)和R(D′)分別為AdDPC算法未添加噪聲時作用于數(shù)據(jù)集D和D′的聚類結(jié)果,A表示任意一種聚類結(jié)果。S(D)和S(D′)分別表示在AdDPC算法中添加Laplace噪聲后的作用于數(shù)據(jù)集D和D′的輸出結(jié)果,B表示添加噪聲后的任意一種聚類結(jié)果。則由式(7)～(10)可得

DP-DPCL算法的差分隱私性得證。

3.2 實驗結(jié)果分析

本實驗由Python語言編程實現(xiàn),實驗環(huán)境為Windows10的64位操作系統(tǒng)、8 GB內(nèi)存、2.30 GHz處理器。實驗用于測試的數(shù)據(jù)集信息如表1所示。本實驗中使用F-Measure[12]和調(diào)整蘭德指數(shù)ARI[13]作為評價指標。用A=(A1,A2,…,AK)表示數(shù)據(jù)集的真實劃分,B=(B1,B2,…,BK′)表示聚類算法對數(shù)據(jù)集的聚類結(jié)果。

表1 數(shù)據(jù)集信息

F-Measure值是同時考慮了精確率(precision)和召回率(recall)的一種評價指標。精確率用于衡量算法聚類結(jié)果的精確程度,召回率用于衡量聚類結(jié)果的完備程度,F-Measure指標可以較為全面地區(qū)分算法的聚類能力。精確率、召回率和F-Measure分別按照式(11)、(12)、(13)來計算,F-Measure取值為[0,1],值越大聚類效果越優(yōu)。一般的聚類結(jié)果分布情況有4類:Na表示在真實劃分A和聚類結(jié)果B中同屬一個類簇的數(shù)據(jù)對的數(shù)目;Nb表示在真實劃分A中屬于同一類簇,而在聚類結(jié)果B中不屬于同一類簇的數(shù)據(jù)對的數(shù)目;Nc表示在真實劃分A中不屬于同一類簇,而在聚類結(jié)果B中屬于同一類簇的數(shù)據(jù)對的數(shù)目;Nd表示在真實劃分A和聚類結(jié)果B中均不屬于同一類簇的數(shù)據(jù)對的數(shù)目。

(11)

(12)

(13)

若β=1,則式(13)可以化為

(14)

蘭德指數(shù)(RI)是一種考慮在真實劃分和聚類結(jié)果中均劃分為同一類簇或均不是同一類簇,即Na和Nd這2種情況的評價指標。這種指標評價比較片面,因此對蘭德指數(shù)進行改進,提出調(diào)整蘭德指數(shù)(ARI)。ARI用于度量真實劃分A和聚類結(jié)果B之間的相似度,其計算式如式(15)所示,取值為[-1,1],值越接近1,聚類效果越好。

(15)

為對比算法在不同隱私預算下的聚類性能,將DP-DPCL算法與AdDPC_rDP算法、DP-rcCFSFDP算法[16]、IDPK-means算法[7]進行對比,通過算法的F-Measure和ARI指標值評估DP-DPCL算法的聚類性能。實驗中DP-DPCL算法在Iris、WDBC、Aggregation數(shù)據(jù)集上的dc取值分別為2.5、1.5、2.5,鄰域半徑取值分別為2.2%、0.8%、0.5%,加權(quán)因子設(shè)為1.001。AdDPC_rDP算法在Iris、WDBC、Aggregation數(shù)據(jù)集上的dc取值分別為2.5、3.0、2.5。DP-rcCFSFDP算法的dc取值分別為2.5、2.5、4.0,根據(jù)文獻[16],鄰域半徑分別為1.8%、0.7%、0.4%。IDPK-means算法中,根據(jù)文獻[7],敏感度Δf=M+1,M為數(shù)據(jù)集的特征屬性數(shù),最大迭代次數(shù)Niter_max=1 000。

圖2為4種算法在Iris數(shù)據(jù)集上聚類的輸出結(jié)果。由圖2(a)可知,隨著隱私預算ε的增加,各算法的F-Measure指標值逐漸增大并趨于穩(wěn)定;當隱私預算ε>1.5時,DP-DPCL算法的F-Measure達到最優(yōu),此時,在Iris數(shù)據(jù)集上DP-DPCL算法聚類性能最佳。由圖2(b)可知,隨著隱私預算的增加,各算法的ARI逐漸增加并趨于穩(wěn)定;當隱私預算ε>1.5時,DP-DPCL算法的ARI達到最優(yōu)。因此,在Iris數(shù)據(jù)集上,總體聚類性能最佳的是DP-DPCL算法。

圖2 Iris數(shù)據(jù)集輸出結(jié)果

圖3為4種算法在WDBC數(shù)據(jù)集上的輸出結(jié)果。由圖3(a)可以看出,DP-DPCL算法的F-Measure均優(yōu)于AdDPC_rDP算法;當隱私預算ε>1.5時,DP-DPCL算法的F-Measure達到最優(yōu),其值均比其余3種算法高。由圖3(b)可知,DP-DPCL算法的ARI均優(yōu)于其余3種算法。

圖3 WDBC數(shù)據(jù)集輸出結(jié)果

圖4為4種算法在Aggregation數(shù)據(jù)集上的輸出結(jié)果。由圖4(a)可知,當隱私預算ε>1.5時,DP-DPCL算法F-Measure均優(yōu)于AdDPC_rDP;當隱私預算ε=2.0時,DP-rcCFSFDP算法的F-Measure達到最優(yōu)值,此時,DP-DPCL算法的F-Measure較DP-rcCFSFDP算法小,其余情況下DP-DPCL算法均比DP-rcCFSFDP表現(xiàn)更佳。與IDPK-means算法的F-Measure比較可知,當隱私預算較小(ε<0.9)時,IDPK-means算法表現(xiàn)均比其余3種算法好,當隱私預算ε>0.9時,IDPK-means算法表現(xiàn)最差。圖4(b)結(jié)果顯示,在Aggregation數(shù)據(jù)集上,DP-DPCL算法的ARI最優(yōu)。

圖4 Aggregation數(shù)據(jù)集輸出結(jié)果

實驗結(jié)果表明,總體上看,DP-DPCL算法的聚類性能與AdDPC_rDP算法、DP-rcCFSFDP算法、IDPK-means算法相比得到了提升,在不同的數(shù)據(jù)集上指標數(shù)值均優(yōu)于其他3種算法。因此,DP-DPCL算法可以在保護敏感數(shù)據(jù)的同時降低所添加的隨機噪聲對聚類可用性的影響。

4 結(jié)論

本文針對AdDPC算法的隱私泄露問題提出了DP-DPCL算法,并對算法的非聚類中心點分配策略進行了優(yōu)化。首先對AdDPC算法存在的隱私泄露問題及非聚類中心點分配策略進行分析,在算法計算數(shù)據(jù)點局部密度的過程中添加Laplace噪聲,并在算法分配非聚類中心點的過程中引入鄰域和可達的概念,優(yōu)化算法非聚類中心點分配的方法。實驗結(jié)果表明,DP-DPCL算法在隱私預算ε>1.5時,聚類性能得到了提高,這是因為隱私預算過小時,添加的噪聲過大,增加了其他算法對聚類中心選取的隨機性,導致剩余數(shù)據(jù)點的分配可能比原始聚類算法的更好;而當預算增大時,DP-DPCL算法對剩余數(shù)據(jù)點的分配方式進行了改進,使得更多的點分配到正確的類簇。但是,DP-DPCL算法對不同的數(shù)據(jù)集聚類時,當最佳截斷距離值不同,如何自適應選取最佳截斷距離值需要進一步研究。