面向差分隱私保護的自適應譜聚類優化新算法

金亦喬 章永祺 王 博 王鑫軻 李昭祥*

1(上海師范大學數理學院 上海 200234)

2(上海師范大學信息與機電工程學院 上海 200234)

0 引 言

近年來,大數據是互聯網時代應運而生的信息技術產物,其背后所蘊含的商業價值正是網絡安全問題日趨嚴峻的主要因素,這使得防止用戶隱私信息泄露的隱私保護技術應運而生。聚類分析是數據挖掘和機器學習領域常用手段,但在聚類過程中依然存在著不可忽視的隱私泄露等安全隱患,如何在聚類過程中維持數據隱私安全和聚類可用性的平衡愈發成為近年來的研究熱點之一。

由Samarati等[1]提出的傳統隱私保護技術k-anonymity模型,要求數據表中的每一條記錄至少與其他k-1條記錄在準標識符QID上完全一致來達到隱私保護的目的,但當查詢結果中所有返回值擁有同一個敏感屬性值時,攻擊者就可以輕易獲得隱私信息[2],尤其是當今大數據平臺的數據開放性,合成攻擊和背景知識攻擊的安全問題日漸不容小覷。基于此,l-diversity[3]、t-closeness[4]等隱私保護技術應運而生,但仍然不能完全解決該問題。

Dwork[5]2006年第一次提出了差分隱私保護模型的概念。其原理與傳統隱私保護算法大相徑庭,從統計分析的角度提供理論上的量化邊界來約束敏感信息的泄露[6],通過為數據添加Laplace噪聲干擾的方式,將確定的輸出結果以概率的方式呈現出來從而達到保護隱私的目的,使得攻擊者無法通過觀察查詢結果來獲取準確的用戶信息,由此引發了國內外十幾年來的差分隱私保護熱潮。Dwork等[7]基于Blum等[8]關于差分隱私保護和k-means結合的思想,進一步得出DPk-means算法中查詢函數和查詢序列敏感度的計算方法。李楊等[9]以傳統DPk-means算法初始簇中心點選取的隨機性為出發點提出了IDP k-means算法,在聚類可用性上取得了更好的效果;吳偉民等[10]在基于密度的聚類方法中提出了DP-DBScan聚類算法,解決了對不同規模和不同維度的數據集的有效處理;鄭孝遙等[11]根據傳統的聚類算法可能存在的隱私風險,以保護數據彼此間的相似度為出發點,在相似性矩陣中加上滿足Lapace分布的隨機噪聲,切實可行地提出了一種基于差分隱私保護的譜聚類算法(簡稱DP-SC),改善了傳統差分隱私保護處理高維稀疏數據的局限性和不理想聚類效果,但對最優聚類簇數、初始點選擇的盲目性、離群點高度敏感和聚類效率、聚類可用性不理想等弊端沒有開展進一步處理。

目前,面向差分隱私保護的譜聚類算法研究并不多。因此,本文針對傳統差分隱私保護的譜聚類算法(DP-SC)存在的不足,提出一種基于差分隱私保護的自適應譜聚類優化新算法(IDP-SC)。仿真實驗結果表明,與DP-SC算法相比較,IDP-SC算法在添加多處優化處理的情況下能保持差分隱私的安全性并有效改善聚類效率和提高聚類可用性。

1 相關工作

1.1 差分隱私保護

定義1[12]假設兩個相鄰數據集H與H′,它們至多只有一個元組有差異,Range(A)表示一個隨機算法A的取值范圍,Pr(E)表示事件E的披露風險。若隨機算法A能夠提供ε-差分隱私保護,則對于數據集的所有輸出結果S,均滿足:

Pr[A(H)∈S]≤exp(ε)×Pr[A(H′)∈S]

(1)

式中:披露風險取決于隨機算法A;ε表示隱私保護參數(隱私預算),ε越小,隱私保護水平越高,但數據可用性越低,當ε=0時,隨機函數A對H和H′輸出結果的概率分布是完全一致的。

定義2[12]對于查詢函數G:H→Rh的敏感度定義如下:

(2)

定義3[13]假設尺度參數b=ΔG/ε,則Laplace噪聲函數為:

Laplace(b)=exp(-|x|/b)

(3)

概率密度函數為:

f(x|b)=exp(-x/b)/(2b)

(4)

累積分布函數為:

F(x)=0.5×[1+sgn(x)×(1-exp(-|x|/b))]

(5)

定義4[13](ε-差分隱私保護)假設數據集為H,查詢函數為G,查詢函數返回的結果是G(H),尺度參數b=ΔG/ε,在G(H)上添加合適Laplace隨機噪聲以實現保護隱私的目的,則函數T的響應值為:

T(H)=G(H)+Laplace(b)

(6)

滿足ε-差分隱私保護。

1.2 差分隱私保護的譜聚類算法

譜聚類算法的原理是基于圖論的思想方法[10],將數據集中的所有數據視作空間中的數據點,點與點之間的連線就構成了邊,用相似度(權重)來衡量兩點之間的距離,對數據點構成的圖進行切圖,再根據數據的Laplace矩陣的特征向量進行聚類。因此,在譜聚類算法中實現數據隱私安全的保護關鍵就在于樣本數據集中各數據之間的相似性關系[11]。滿足ε-差分隱私保護的譜聚類算法(DP-SC)的主要步驟如下:

輸入:數據集data1。

輸出:標簽label。

Step1定義聚類種類k,根據給定的label計算出k的值。

Step2初始化k_near=10和σ=0.9,根據KNN和高斯核函數的距離公式計算各個數據間的權重值nij。

Step3為鄰接矩陣N添加噪聲得到加噪鄰接矩陣N′。

Step4根據加噪后的鄰接矩陣N′得到度矩陣K,求出Laplace矩陣L=K1/2NK1/2。

Step5求Laplace矩陣L的前k個最大的特征值和對應的特征向量。

Step6標準化特征向量,將樣本數據點映射到基于一個或多個確定的降維空間中去。

Step7利用k-means聚類方法,得到聚類后的label值。

與傳統的k-means聚類算法相比,基于圖論的譜聚類算法能夠將高維凸形的任意形狀的稀疏數據進行聚類,而且不容易陷入局部最優解,適用性更強[14]。由此,譜聚類算法結合差分隱私保護的思想,在相似性矩陣中加上滿足Laplace分布的隨機噪聲,在一定的信息損失度范圍內實現了有效的聚類結果[15]。但它無法保證降維幅度和聚類簇數的選取是最優的,而且對于初始點選擇的盲目性、離群點的高敏感度和聚類可用性有待改善等弊端缺乏更進一步的處理。基于此,為有效解決上述問題,在保證數據隱私的同時改善聚類效率并顯著提高聚類可用性的要求下,本文提出一種面向差分隱私保護的自適應譜聚類優化新算法。

2 差分隱私保護的譜聚類算法改進

設H=[hij]是一個n×h的數據集,其中每一個數據點(每一行元組)的維度是h維,矩陣W=[wij]是稀疏鄰接矩陣,矩陣D=[dij]是度矩陣,矩陣L是該數據集經過W和D計算得到的n×nLaplace矩陣,映射矩陣M是前Ke個特征值所對應的特征向量組合后得到的n×Ke矩陣。

2.1 互鄰高斯核函數

高斯核函數能夠利用高維向量之間的內積得出兩個高維向量之間的距離,有效減少計算的復雜程度。為了得到稀疏鄰接矩陣W,提出互鄰高斯核函數的概念如下,實現高斯核函數和KNN算法的有機結合。

定義5(互鄰高斯核函數)假設vi和vj是兩個數據點,如果vi在vj的k_near領域中并且vj也在vi的k_near領域中,則權重wij=wji為vi與vj之間的距離,否則權重取值為0,其中wij為高斯核函數的計算值,k_near為KNN算法的參數[16-17]。

2.2 自適應聚類簇數

IDP-SC可以分解為如下2個階段:

(1) 降維階段:通過處理矩陣L的數據特征,將原始的高維數據點映射到一個低維的映射空間,即得到映射矩陣M,具體見算法1。

算法1求解降維最優簇數Ke

輸入:矩陣L。

輸出:降維最優簇數Ke和映射矩陣M。

Step1歸一化矩陣L,計算特征值及對應的特征向量。

Step2從小到大排列這n個特征值E(1),E(2),…,E(n)。

Step3初始化特征值閾值εe=average(ΔE(i)),其中i=0,1,…,n-1。

Step4按照次序比較ΔE(i),首次滿足ΔE(i)>εe時,得到降維最優簇數Ke。

Step5依次排序前Ke個特征值所對應的特征向量,得到映射矩陣M。

(2) 聚類階段:在低維的特征空間中,對映射矩陣M的特征向量進行聚類[14],具體見算法2。

算法2求解聚類最優簇數Ks

輸入:映射矩陣M。

輸出:聚類最優簇數Ks。

Step1建立以聚類簇數為X和誤差平方和為Y的直角坐標系。

Step2根據映射矩陣M,計算每一個X=S點對應的SSES以及相鄰兩點之間的斜率絕對值|Slope|。

Step3初始化斜率閾值εs=SSE1/Kmax。

Step4從大到小比較|Slope|,首次滿足|Slope|<εs時,得到聚類最優簇數Ks。

定義6(降維最優簇數Ke)在降維階段中,從小到大排列矩陣L的n個特征值E(1),E(2),…,E(n),第一次出現第Ke個次序特征值與第Ke+1個次序特征值的差距ΔE(i)=E(i+1)-E(i)大于特征值閾值εs(Epsilon Eigenvalue)的情況,即兩相鄰次序特征值差的絕對值首次滿足ΔE(i)>εe時,降維最優簇數的取值Ke。

事實上,(低維映射空間)映射矩陣M的列向量就是這前Ke個特征值所對應的特征向量。

定義7(聚類最優簇數Ks)在聚類階段中,根據映射矩陣M中的降維數據,建立以聚類簇數為X軸和誤差平方和為Y軸的直角坐標系,記錄下X軸相鄰兩點之間的斜率Slopes。第一次出現Slopes的絕對值小于斜率閾值εs(Epsilon Slope)的情況,即相鄰兩點斜率的絕對值首次滿足時|Slopes|<εs,聚類最優簇數的取值為Ks。

其中,Ke、Ks為正整數且2≤Ke,Ks≤Kmax,為保準IDP-SC的降維幅度和聚類有效性,一般取Kmax=8。

定義8(Sum of Squared Errors,SSE)其是K-means聚類算法中最常用的評價指標。它是所有數據點到其所屬簇質心的距離平方和。SSE越小,表示聚類結果越好。計算公式如下:

(7)

式中:K為聚類數;mi為第i個聚類中心;j是第i類簇的第i個數據點。

定義9對于面向差分隱私保護的譜聚類算法的自適應最優聚類簇數AOC的定義如下:

AOC=min{Ke,Ks}

(8)

式中:Ke是降維階段的降維最優簇數;Ks是聚類階段的聚類最優簇數。

2.3 中間信息向量

TOPSIS(Technique for Order Preference by Similarity to an Ideal Solution)法是一種有效的多指標評價方法,能夠充分利用原始數據的內在特征,其結果可以精確反映數據之間的差距,是一種逼近于理想解的排序法[18]。本文利用TOPSIS法的思想計算中間信息向量的目的是為了有效處理譜聚類算法中聚類階段第一個初始簇中心選擇的盲目性,即選取各數據特征的信息最為折中且最有價值的VII以得到更優的第一個初始簇中心來優化算法。

(9)

(10)

式中:wij為鄰接矩陣W中第i行第j列的權重值。

定義11(中間信息向量VII)將數據集H中n個h維的向量根據數據特征的不同分別進行排名,根據這個數據特征的排名綜合評分,分數處于排名中間項的那個向量就叫做中間信息向量。

由于VII是數據集H中各個數據特征綜合排名的中間項,因此它具有良好的中間性(Intermediateness),在代表全體向量各個維度上的信息是最有價值的唯一向量;它也具有低敏感度(Low-Sensitivity),即對任一數據特征的離群點敏感度較低。

2.4 差分隱私保護的自適應譜聚類優化新算法

算法3IDP-SC算法

輸入:數據集H。

輸出:IDP-SC蔟類CIDP={C1,C2,…,CAOC}。

Step1根據數據集H,運用互鄰高斯核函數的概念得到稀疏鄰接矩陣W。

Step2為稀疏鄰接矩陣添加Laplace隨機噪聲得到加噪鄰接矩陣W′,并計算求得度矩陣D。

Step3求出標準化Laplace矩陣L=D1/2W′D1/2。

Step4根據Laplace矩陣L,采用算法1和算法2依次求得降維最優簇數Ke、映射矩陣M和聚類最優簇數Ks,結合式(8)得到IDP-SC的自適應最優聚類簇數AOC。

Step8后續迭代采用傳統k-means++算法,直至算法收斂或蔟中心不再變動,輸出最優蔟類CIDP={C1,C2,…,CAOC}。

3 實驗與結果分析

3.1 實驗環境與數據集

本文涉及的算法均使用Visual Studio 2019集成開發環境的Python 3.8語言仿真實現。實驗環境為Windows 10 x64,CPU 2.30 GHz,內存16.0 GB。算法所涉及的數據集均來自于:UCI Knowledge Discovery Archive database。

各數據集信息如表1所示。

表1 UCI數據集信息

首先對數據集DS1和DS2進行歸一化處理[19],使其所有數據點的各個屬性值都映射至區間[0,1]之間,消除量綱并提升模型精度。

(11)

式中:maxX和minX分別代表數據集中屬性X的最大值和最小值;x表示數據集中的數據點;x′表示經過歸一化處理之后的數據點。

3.2 實驗評價指標

差分隱私數據挖掘類算法取決于差分隱私保護下的保護強度和數據挖掘聚類算法下的聚類效果。隱私保護程度可以通過隱私預算ε來評估,其值越小,添加的Laplace隨機噪聲越大,隱私保護水平越高,但聚類可用性越低;聚類效果可以從兩方面進行評價,即聚類算法的聚類效率和聚類可用性。

3.2.1聚類效率

差分隱私保護模型下的聚類效率可以采用聚類過程中算法收斂或簇中心不再變動時的迭代次數來評價,同時它也是衡量聚類算法初始簇中心選取合理性的有效指標。迭代次數越小表示初始簇中心點的選擇越合理,算法聚類效率越高。

3.2.2聚類可用性

差分隱私保護模型下的聚類可用性可以使用蘭德系數RI指標和修正蘭德系數ARI指標評價。對于數據集H,假設用C表示實際類別信息,K表示最終聚類結果,a表示C和K中屬于同一類別的元素數量,b表示C和K中屬于不同類別的元素數量,則RI指標[20]如式(12)所示。

(12)

但在仿真實驗中,算法實現計算得到的RI值普遍偏高導致區分度不明顯,由此ARI指標[20]被提出,如式(13)所示。

(13)

式中:E(RI)表示RI的數學期望,ARI取值范圍[0,1],ARI值越大表示聚類結果和真實情況越吻合,聚類可用性越好。

3.3 結果分析

對數據集DS1和DS2分別采用DP-SC算法和IDP-SC算法進行對比實驗,在評價聚類效率指標時將隱私預算ε的值逐步從0.1調至2.0,在評價聚類可用性指標時將隱私預算ε的值逐步從0.1調至1.0。為了避免算法隨機性而導致的實驗結果存在偶然性,根據每個隱私預算ε值,對DS1和DS2分別采用DP-SC和IDP-SC算法聚類20次,并將其評價指標結果的平均值作為最終的實驗結果。

在數據集DS1和DS2上運行的聚類效率評價結果分別如圖1和圖2所示。

圖1 數據集DS1的聚類效率評價結果

圖2 數據集DS2的聚類效率評價結果

結合圖1和圖2可以發現,對于數據集DS1和DS2的實驗結果來說,在同一隱私預算ε下,本文提出的IDP-SC算法與傳統的DP-SC算法相比,IDP-SC算法的平均迭代次數明顯小于DP-SC算法且具有穩健性,意味著IDP-SC采用中間信息向量的概念挑選第一個初始簇中心的方法可以有效提高聚類效率,并且隨著隱私預算ε的增加,DP-SC算法的平均迭代次數逐漸減少,聚類效率越來越高,趨近于IDP-SC的平均迭代次數。這說明新算法在保證數據隱私的同時可以有效提高聚類效率。值得一提的是,對于高維數據集,新算法在聚類效率上的改進效果尤其顯著。

在數據集DS1和DS2上運行的聚類可用性評價結果分別如圖3和圖4所示。

圖3 數據集DS1的聚類可用性評價結果

圖4 數據集DS2的聚類可用性評價結果

結合圖3和圖4可以發現,對于數據集DS1和DS2的實驗結果來說,在同一隱私預算ε下,本文提出的IDP-SC算法與傳統的DP-SC算法相比,顯然具有更高的ARI評價結果,這說明新算法在保證數據隱私的同時可以顯著提高聚類可用性。不難看出,對于高低緯數據集,本文算法在聚類可用性上的改進效果都比較顯著。

圖3和圖4分別展示的是在DS1和DS2數據集上,針對不同的隱私預算ε值分別調用DP-SC算法和IDP-SC算法進行聚類20次后得到的ARI的平均值折線圖。可以看出,IDP-SC算法的聚類可用性明顯要高于DP-SC,同時隨著隱私預算的增大,添加的噪聲量減小,使得聚類可用性也越高。不難得出,對于高低緯數據集,本文算法在聚類可用性上的改進效果都比較顯著。

4 結 語

本文針對傳統的差分隱私保護的譜聚類算法(DP-SC),提出基于差分隱私保護的自適應譜聚類優化新算法(IDP-SC),有效解決了降維幅度和聚類簇數的不確定性、初始簇中心選取的隨機性和離群點高敏感度等問題而可能導致出現聚類效果不理想的情況。

首先本文算法結合KNN思想和高斯核函數的概念提出互鄰高斯核函數,有效處理了高維大樣本場合數據集的計算壓力;通過分析高維數據點的數據特征與聚類簇數的關系自適應地得到IDP-SC的最優聚類簇數,再利用TOPSIS思想引入中間信息向量和中間性的概念處理聚類階段第一個初始簇中心選取的隨機性,最后根據多維高斯分布離群點檢驗后的結果采用插補法解決離群點問題。仿真實驗結果表明,IDP-SC在高維大樣本場合數據集下,能夠在保證差分隱私安全性的同時改善聚類效率并顯著提高聚類可用性,切實把握住數據隱私和聚類效果兩者的平衡。在以后的研究中,將繼續深入研究如何有效減少算法的復雜程度,在保證差分隱私技術的安全性下進一步提高運行效率和聚類可用性,特別是如何顯著提高維數據集的聚類可用性。