鄭孝遙,陳冬梅,劉雨晴,尤 浩,汪祥舜,孫麗萍

(1.安徽師范大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 蕪湖 241002; 2.網(wǎng)絡(luò)與信息安全安徽省重點(diǎn)實(shí)驗(yàn)室(安徽師范大學(xué)),安徽 蕪湖 241002)(*通信作者電子郵箱zxiaoyao_2000@163.com)

0 引言

近年來,隨著互聯(lián)網(wǎng)與信息技術(shù)的蓬勃發(fā)展,海量數(shù)據(jù)的產(chǎn)生可以為研究者們提供許多有效的信息資源,對這些海量數(shù)據(jù)進(jìn)行挖掘分析可以得到非常有價值的信息,其中聚類分析是有效手段之一，但是在聚類的過程中也存在著隱私泄露的風(fēng)險(xiǎn)。

目前,國內(nèi)外研究者圍繞隱私安全保護(hù)問題做了大量的工作,從已有的隱私保護(hù)技術(shù)來看:k-匿名及其擴(kuò)展的保護(hù)模型技術(shù)已被廣泛使用。該方法通過存儲至少k條記錄來隱藏一條數(shù)據(jù)記錄從而達(dá)到隱私保護(hù)的目的,但是在攻擊者掌握特定背景知識的情況下，它就存在不能抵抗一致性攻擊的可能。為了克服這一缺點(diǎn)，研究者們不斷嘗試加以改進(jìn)而出現(xiàn)了l-多樣性[1]、t-鄰近[2]、(a,k)-匿名[3]、泛化和隨機(jī)化[4]等隱私保護(hù)技術(shù)。

如今關(guān)于聚類分析在隱私保護(hù)方面的應(yīng)用越來越多,而且聚類作為數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的主要技術(shù)之一被廣大學(xué)者所研究,聚類分析中常用的隱私保護(hù)技術(shù)有數(shù)值擾動、數(shù)值旋轉(zhuǎn)、數(shù)值匿名等方法。Oliverira等[5]在2004年提出一種基于新的空間數(shù)據(jù)轉(zhuǎn)換方法RT(Rotation-based Transformation),該方法的基礎(chǔ)是基于幾何的旋轉(zhuǎn)變化來隱藏信息,并能保證旋轉(zhuǎn)前后的屬性依舊具有有效性；其缺點(diǎn)在于只能對低維度的數(shù)據(jù)進(jìn)行變換,維度較高時會損耗數(shù)據(jù)的真實(shí)信息,計(jì)算量也較大,并且難以避免一致性攻擊造成的隱私泄露。Mukherjee等[6]在2006年針對文獻(xiàn)[5]算法不易推廣到其他應(yīng)用場景中的問題而提出了一種新的采用傅里葉變換的數(shù)據(jù)擾動方法,其優(yōu)點(diǎn)是在實(shí)現(xiàn)敏感信息隱藏的同時能夠保持?jǐn)?shù)據(jù)值的有效性，并保證歐幾里得集中式和分布式場景中的距離精度很高。目前的研究在聚類的基礎(chǔ)上加上差分隱私技術(shù)的研究還不夠成熟,最早提出這一想法的是2005年Blum等[7]給出的利用差分隱私和k-means相結(jié)合的算法,使用管理員的身份將噪聲引入到查詢響應(yīng)中來維護(hù)單個數(shù)據(jù)庫條目的隱私。隨后Dwork等[8]在2010年對基于差分隱私的k-means算法進(jìn)行了更進(jìn)一步的分析和改進(jìn),提出了一種可以計(jì)算查詢函數(shù)和查詢序列敏感度的算法。國內(nèi)的李楊等[9]提出了ε-差分隱私保護(hù)下的IDPk-means方法,該方法可以應(yīng)對攻擊者具有任意背景知識的攻擊,并且很好地改善了數(shù)據(jù)聚類后的可用性問題,但是此方法不能解決分布式環(huán)境下的隱私泄露安全問題。因此,在2016年李洪成等[10]提出了在分布式環(huán)境下滿足ε-差分隱私的k-means算法,解決了傳統(tǒng)隱私保護(hù)模型無法在分布式環(huán)境中應(yīng)對任意背景知識攻擊的問題。吳偉民等[11]基于文獻(xiàn)[9]提出了滿足ε-差分隱私保護(hù)的DP-DBScan算法,是應(yīng)對傳統(tǒng)的DBScan聚類算法存在的隱私泄露問題而研究出來的,該算法的實(shí)驗(yàn)結(jié)果表明與傳統(tǒng)的DBScan聚類算法相比,加入拉普拉斯噪聲的DP-DBScan算法能保持?jǐn)?shù)據(jù)的有效性并實(shí)現(xiàn)隱私保護(hù)。劉曉遷等[12]基于聚類的匿名化技術(shù)，并利用差分隱私保護(hù)模型對發(fā)布數(shù)據(jù)進(jìn)行保護(hù),該方法通過聚類實(shí)現(xiàn)匿名化,對匿名分化的數(shù)據(jù)添加隨機(jī)噪聲來擾動數(shù)據(jù)的真實(shí)值以實(shí)現(xiàn)隱私保護(hù),并提高數(shù)據(jù)的可用性。目前,針對聚類方法結(jié)合差分隱私的研究還比較少,本文主要針對譜聚類算法，開展基于差分隱私保護(hù)的譜聚類算法研究。

本文主要針對聚類算法存在隱私泄露的問題,利用譜聚類算法將社交關(guān)系圖網(wǎng)絡(luò)化,使得具有社交關(guān)系的聚類在一起,為了防止這種社交關(guān)系泄露,在通過相似性函數(shù)計(jì)算權(quán)重時加上差分隱私的拉普拉斯隨機(jī)噪聲來進(jìn)行擾動達(dá)到隱私保護(hù)的作用。

1 相關(guān)工作

1.1 譜聚類算法

目前,譜聚類算法在國內(nèi)得到廣泛的應(yīng)用和研究,最常應(yīng)用的領(lǐng)域有機(jī)器學(xué)習(xí)、大數(shù)據(jù)挖掘、圖像分割、文本挖掘等[13]。該算法的流程簡單,并且與傳統(tǒng)的k-means和最大期望(Expectation Maximization, EM)算法相比適用性更強(qiáng),在任何的數(shù)據(jù)樣本空間中都會聚類出最好的聚類效果。譜聚類的主要思想是基于圖譜理論的分割技術(shù),該算法將樣本數(shù)據(jù)看成無向帶權(quán)圖中的一個個頂點(diǎn),然后利用相似性函數(shù)計(jì)算出各頂點(diǎn)之間的值,權(quán)重值代表各個頂點(diǎn)間的相似度,然后采用圖譜的分割準(zhǔn)則將數(shù)據(jù)分割聚類。

一般譜聚類算法的相似性函數(shù)采用余弦函數(shù)和高斯函數(shù),具體定義如下:

(1)

(2)

圖分割算法準(zhǔn)則主要有以下幾個準(zhǔn)則：

1)圖分割最小分割法準(zhǔn)則:

(3)

2)規(guī)范化分割準(zhǔn)則:

(4)

3)最小最大分割準(zhǔn)則:

(5)

4)比例分割準(zhǔn)則:

(6)

譜聚類算法的主要算法流程如算法1所示。

算法1 譜聚類算法。

輸入n個數(shù)據(jù)點(diǎn)集,聚類數(shù)目k。

輸出 得到k個簇劃分。

a)通過高斯核函數(shù)的距離公式計(jì)算相似性矩陣;

b)利用相似矩陣構(gòu)建鄰接矩陣N和度矩陣G;

c)由第b)步得到的鄰接矩陣和度矩陣求出拉普拉斯矩陣L=G1/2NG1/2；

d)得到拉普拉斯矩陣后選取前k個最大特征值對應(yīng)的特征向量;

e)將特征向量標(biāo)準(zhǔn)化,然后將樣本數(shù)據(jù)點(diǎn)映射到基于一個或多個確定的降維空間中去;

f)基于新的數(shù)據(jù)點(diǎn)空間,將特征矩陣的每一行看成一個樣本點(diǎn)利用k-means將它聚為k類。

1.2 差分隱私

差分隱私保護(hù)模型具有嚴(yán)格的數(shù)學(xué)理論基礎(chǔ),該模型的基本思想是對數(shù)據(jù)添加噪聲來達(dá)到隱私保護(hù)的目的[14]。該保護(hù)方法不需要關(guān)心攻擊者的強(qiáng)大計(jì)算能力和任何的背景知識,即使攻擊者擁有除一條記錄以外的所有數(shù)據(jù)記錄也能保證這條記錄的敏感信息不會被披露,這種機(jī)制能夠?qū)颖緮?shù)據(jù)中個體敏感信息進(jìn)行特定的保護(hù)，而且還不會引起數(shù)據(jù)分布的變化。差分隱私的具體定義如下:

定義1 假設(shè)數(shù)據(jù)集D和D′是相鄰數(shù)據(jù)集,兩個數(shù)據(jù)集完全相同或至多相差一條數(shù)據(jù)記錄,給定一個隨機(jī)算法S,Range(S)是算法S的取值范圍,RM是數(shù)據(jù)集上的輸出結(jié)果, Pr[X]是事件X的披露風(fēng)險(xiǎn),則算法S滿足ε-差分隱私的保護(hù)模型定義:

Pr[S(D)=RM]≤exp(ε) Pr[S(D′)=RM]

(7)

隱私披露風(fēng)險(xiǎn)的值由隨機(jī)算法S控制,通過限制ε的大小來控制隱私保護(hù)的安全度：ε越小引入的隨機(jī)噪聲越大,隱私保護(hù)安全性越高；ε越大引入的隨機(jī)噪聲越小,隱私保護(hù)安全性越低。

定義2 對于函數(shù)F:D→Rd的敏感度定義如下:

(8)

其中:‖*‖1表示一階范數(shù);F是查詢函數(shù)；d是記錄數(shù)據(jù)的屬性維度;D和D′是至多相差一條數(shù)據(jù)記錄的數(shù)據(jù)集;R表示的實(shí)數(shù)空間。

由定義1可以看出隨機(jī)函數(shù)的選擇與攻擊者的背景知識無關(guān),所以任意一條記錄的增加或者刪除都不會影響查詢結(jié)果的輸出。該定義從理論上滿足了差分隱私對隱私披露風(fēng)險(xiǎn)的要求,而具體的實(shí)現(xiàn)還是依靠添加噪聲機(jī)制來實(shí)現(xiàn)。

1.3 兩種噪聲機(jī)制

實(shí)現(xiàn)差分隱私保護(hù)的噪聲添加機(jī)制有兩種:一種是基于數(shù)值型的拉普拉斯噪聲機(jī)制；另一種是針對非數(shù)值型數(shù)據(jù)的指數(shù)機(jī)制[15]。

1.3.1 拉普拉斯噪聲機(jī)制

文獻(xiàn)[16]中提出了對于數(shù)值型的數(shù)據(jù)采用拉普拉斯機(jī)制對數(shù)據(jù)的真實(shí)值進(jìn)行擾動來達(dá)到隱私安全保護(hù)。其定義如下:

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

(9)

其概率密度函數(shù)表達(dá)形式是:

p(x)=exp(-x/b)/(2b)

(10)

其累積分布函數(shù)的表達(dá)形式是:

D(x)=[1+sgn(x)×(1-exp(x/b))]/2

(11)

其概率密度函數(shù)如圖1所示。

圖1 拉普拉斯概率密度函數(shù)Fig. 1 Laplace probability density function

假設(shè)數(shù)據(jù)集為D,查詢函數(shù)是F,查詢結(jié)果是F(D),添加噪聲的函數(shù)為W，其響應(yīng)值定義如下：

W(D)=F(D)+Laplace(ΔF/ε)

(12)

則稱W(D)滿足ε-差分隱私保護(hù)。

1.3.2 指數(shù)機(jī)制

Laplace機(jī)制僅適用于查詢結(jié)果是數(shù)值型的數(shù)據(jù),而在實(shí)際的生活應(yīng)用中許多數(shù)據(jù)的查詢是非數(shù)值型的,因此在文獻(xiàn)[8]中提出了一種非數(shù)值型的算法。該算法定義如下:設(shè)隨機(jī)算法F,查詢結(jié)果集為R,t是R中某一個體,在這種機(jī)制下函數(shù)u(D,t)中t是所有輸出項(xiàng)的選中項(xiàng)。若算法F以exp((εu(D,t))/(2Δu))的概率從查詢結(jié)果集中選擇并輸出的是t,那么稱此算法滿足ε-差分隱私的保護(hù)模型定義。

由此可以看出,當(dāng)ε越大,被選出輸出的概率就越大;當(dāng)ε較小時,選中輸出的概率就變小。

2 差分隱私保護(hù)的譜聚類算法分析

2.1 算法描述

與傳統(tǒng)的k-means相比，基于圖分割理論的譜聚類算法的適用性更強(qiáng),不容易陷入局部最優(yōu)解,能夠?qū)ι缃痪W(wǎng)絡(luò)中非凸型的數(shù)據(jù)進(jìn)行聚類。該算法把數(shù)據(jù)點(diǎn)看成一個個頂點(diǎn),然后利用相似矩陣將樣本點(diǎn)鏈接一起,采用子圖最優(yōu)的分割理論來劃分。其中相似矩陣計(jì)算的是兩個樣本點(diǎn)之間的權(quán)重值,而這種權(quán)重可以理解為樣本點(diǎn)的親密度。對于數(shù)據(jù)的發(fā)布者來看,如何在發(fā)布數(shù)據(jù)的同時不泄露它們的親密度關(guān)系是本文的研究重點(diǎn)。因此本文采用差分隱私結(jié)合譜聚類的方法,在相似性矩陣上加上滿足拉普拉斯分布的隨機(jī)噪聲來達(dá)到隱私保護(hù)的目的。

基于差分隱私的譜聚類算法流程如下:假設(shè)p={p1,p2,…,pn}和q={q1,q2,…,qn}是n維空間中的兩個樣本集,譜聚類算法的原理就是利用相似性函數(shù)計(jì)算樣本數(shù)據(jù)集的相似性,值越大相似性越高,聚為一類的可能性就越大。同時這種相似性也可以理解為社交網(wǎng)絡(luò)中的關(guān)系親密度,為了確保這種親密關(guān)系不被泄露,在計(jì)算相似性時加上差分隱私的拉普拉斯噪聲來隱藏潛在的數(shù)據(jù)信息,從而實(shí)現(xiàn)隱私安全的保護(hù)。

算法2 基于差分隱私的譜聚類算法。

輸入 UCI數(shù)據(jù)集data。

輸出 標(biāo)簽label。

1)

定義聚類種類k，根據(jù)給定的label計(jì)算出k的值;

2)

初始化k_near=100和?=0.9;

3)

fori=1 torow

4)

forj=1 torow

5)

ifi≠j

6)

dis_matij←exp(-‖pi-qj‖2/(2σ2));

7)

dis_matii←0;

8)

end if

9)

end for

10)

end for

11)

保留k_near的權(quán)重值A(chǔ)ffinity[i,j]，根據(jù)積累分布函數(shù)(11)生成隨機(jī)噪聲，并添加進(jìn)去;

12)

計(jì)算度矩陣和拉普拉斯矩陣的值du[i,j]、laplas[i,j];

13)

求拉普拉斯矩陣的前k大特征值和對應(yīng)的特征向量;

14)

15)

利用k-means進(jìn)行聚類，得到聚類后的label值;

2.2 算法分析

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文采用來自于UCI Knowledge Discovery Archive database (http://archive.ics.uci.edu/)數(shù)據(jù)集中的liver、 pima、sonar、balance四個數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。各數(shù)據(jù)集信息如表1所示。

表1 UCI數(shù)據(jù)集Tab. 1 UCI datasets

本文首先對四個數(shù)據(jù)集liver、 pima、sonar、balance進(jìn)行預(yù)處理,使其每個屬性值都在區(qū)間[0,1],對四個數(shù)據(jù)集分別進(jìn)行譜聚類算法和差分隱私譜聚類算法實(shí)驗(yàn),因?yàn)閷?shí)驗(yàn)的偶然性,所以進(jìn)行20次實(shí)驗(yàn),對比20次實(shí)驗(yàn)結(jié)果的平均值。然后調(diào)整相似性函數(shù)σ的值，如0.1、0.5、0.9、1、2、4、6、8、10和12來確定最佳的聚類狀態(tài)，并用精確度作為聚類結(jié)果的輸出。從圖2可以看出,聚類效果比較好的σ維持在1～2。

圖2 參數(shù)σ對聚類結(jié)果的影響Fig. 2 Effect of parameter σ on clustering results

3.2 實(shí)驗(yàn)配置環(huán)境

主要采用Matlab軟件編程來實(shí)現(xiàn)本文算法。實(shí)驗(yàn)的軟硬件環(huán)境如下:

1)硬件環(huán)境配置:Intel i5 處理器,4 GB內(nèi)存。

2)軟件環(huán)境配置:Matlab R2013b編程軟件,操作系統(tǒng)Windows 7 64位旗艦版。

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

根據(jù)前文的實(shí)驗(yàn)設(shè)置，本文完成了四個數(shù)據(jù)集上的對比實(shí)驗(yàn)，圖3～6分別給出了四個數(shù)據(jù)集擾動前后的實(shí)驗(yàn)對比情況。

由圖3可知,對于數(shù)據(jù)集liver,運(yùn)用差分隱私的譜聚類算法和只用譜聚類算法在聚類效果上是差不多的,說明本文算法可以在具有隱私保護(hù)的前提下,保證了數(shù)據(jù)集liver的聚類有效性。

圖3 liver數(shù)據(jù)集擾動前后的精確度結(jié)果比較Fig. 3 Accuracy results comparison of dataset liver

由圖4可知,對于數(shù)據(jù)集pima,精確度平均分布在0.6～0.7,分布較為穩(wěn)定,而擾動前后的對比,雖然總體上是加擾動前聚類效果要好,但是此條件下并不能滿足隱私保護(hù),所以擾動后的算法仍然具有可用性。

圖4 pima數(shù)據(jù)集擾動前后的精確度結(jié)果比較Fig. 4 Accuracy results comparison of dataset pima

由圖5可知,對于數(shù)據(jù)集sonar,其運(yùn)行的總體情況是加入拉普拉斯噪聲要比不加噪聲好,精確度平均分布在0.5～0.6,而干擾后的算法在隱私保護(hù)的前提下可以達(dá)到聚類效果的最好狀態(tài)。

圖5 sonar數(shù)據(jù)集擾動前后的精確度結(jié)果比較Fig. 5 Accuracy results comparison of dataset sonar

由圖6可知,對于數(shù)據(jù)集balance的運(yùn)行結(jié)果總體都比未擾動的效果更好,其精確度的平均值穩(wěn)定在0.4左右,而加入擾動后的值平均在0.5左右,提高了聚類的有效性。同時,經(jīng)過擾動后的權(quán)重因隨機(jī)點(diǎn)的選取,可能會出現(xiàn)樣本點(diǎn)更好的聚類在樣本中心點(diǎn)附近，所以出現(xiàn)擾動后結(jié)果優(yōu)于擾動前。

圖6 balance數(shù)據(jù)集擾動前后的精確度結(jié)果比較Fig. 6 Accuracy results comparison of dataset balance

對比圖3～6,對于不同的四個數(shù)據(jù)集,在與譜聚類算法和差分隱私譜聚類算法對比實(shí)驗(yàn)中,擾動前的精確度總體比擾動后的結(jié)果要高一些。總體來說，本文算法在實(shí)現(xiàn)隱私保護(hù)方面具有較好的成效,同時得到的聚類精確度也較高。

4 結(jié)語

本文針對傳統(tǒng)的聚類算法存在隱私泄露的風(fēng)險(xiǎn),以及幾個經(jīng)典的聚類保護(hù)算法，如k-means、DBScan、k-medoids等,在社交網(wǎng)絡(luò)應(yīng)用中還存在的一些不足,利用譜聚類算法對處理凸型的空間數(shù)據(jù)和高維度的數(shù)據(jù)不容易陷入局部最優(yōu)解的優(yōu)勢,開展具有隱私保護(hù)的譜聚類算法研究。首先計(jì)算樣本數(shù)據(jù)集之間的樣本相似性作為數(shù)據(jù)點(diǎn)之間的權(quán)重值,再利用差分隱私算法對權(quán)重值添加拉普拉斯分布的隨機(jī)噪聲,通過干擾權(quán)重值達(dá)到隱私保護(hù)的目的。實(shí)驗(yàn)結(jié)果表明，干擾后的數(shù)據(jù)不僅可以實(shí)現(xiàn)隱私保護(hù)，還保證了聚類的有效性。