基于聚類結(jié)構(gòu)編碼的差分隱私異構(gòu)數(shù)據(jù)發(fā)布

高海燕 高晉陽 鄭志華

1(晉中職業(yè)技術(shù)學(xué)院電子信息學(xué)院 山西 晉中 030600) 2(中北大學(xué)儀器與電子學(xué)院 山西 太原 030051)

0 引 言

大數(shù)據(jù)時(shí)代下,信息已經(jīng)成為了一種極為重要的戰(zhàn)略資源,尤其在醫(yī)療、科研、軍事等領(lǐng)域[1-2]。如何在發(fā)布數(shù)據(jù)的同時(shí)有效地保護(hù)隱私信息,同時(shí)盡可能多地保留受干擾數(shù)據(jù)的效用以進(jìn)行后續(xù)數(shù)據(jù)分析成為了研究的重點(diǎn)[3]。

異構(gòu)數(shù)據(jù)通常由關(guān)系數(shù)據(jù)和集值數(shù)據(jù)組成,因此異構(gòu)數(shù)據(jù)的隱私保護(hù)一般分為關(guān)系數(shù)據(jù)匿名化與集值數(shù)據(jù)匿名化[4]。對于關(guān)系數(shù)據(jù)匿名化問題,文獻(xiàn)[5]隱藏識別屬性和敏感屬性之間的相關(guān)性,并生成k-匿名相似性數(shù)據(jù)以顯示身份和屬性。Mohammed等[6]通過在泛化過程中添加不確定性,可以有效發(fā)布差分隱私數(shù)據(jù)。對于集值數(shù)據(jù)匿名化問題,文獻(xiàn)[7]提出一種數(shù)據(jù)分區(qū)技術(shù),用于斷開標(biāo)識屬性之間的關(guān)聯(lián),并在最終查詢結(jié)果中添加噪聲。文獻(xiàn)[8]提出KP匿名模型,通過區(qū)分集值屬性中的敏感項(xiàng)和非敏感項(xiàng),滿足多樣性相關(guān)性來防止屬性泄漏。雖然上述方法取得了一定的效果,但是許多方法均是單獨(dú)處理關(guān)系數(shù)據(jù)或集值數(shù)據(jù),對于異構(gòu)數(shù)據(jù)來說是否有效還需進(jìn)一步研究。

針對異構(gòu)數(shù)據(jù)匿名化,也有一系列研究,文獻(xiàn)[9]提出一個(gè)差分隱私回歸分析模型,將目標(biāo)函數(shù)轉(zhuǎn)化為多項(xiàng)式形式,并對多項(xiàng)式表示的系數(shù)加入噪聲。文獻(xiàn)[10]將差分隱私與決策樹相結(jié)合,提供分類器的隱私保護(hù),還使用小批量梯度下降算法來保護(hù)訓(xùn)練數(shù)據(jù)的隱私。雖然這些工作針對某些特定數(shù)據(jù)考慮了異構(gòu)數(shù)據(jù)的聚類性能,但是缺乏泛化性能,即上述匿名化過程不考慮一般性的聚類分析任務(wù),因此用戶在使用時(shí)缺乏靈活性與實(shí)用性。

針對上述問題,提出了一種用于聚類分析的異構(gòu)數(shù)據(jù)差分隱私發(fā)布方案。利用聚類標(biāo)簽對聚類結(jié)構(gòu)進(jìn)行編碼,并結(jié)合泛化技術(shù)和輸出擾動(dòng)來掩蓋原始數(shù)據(jù)。通過實(shí)驗(yàn)驗(yàn)證了該方法能夠有效解決異構(gòu)數(shù)據(jù)發(fā)布問題。

1 差分隱私

參數(shù)ε被稱為隱私預(yù)算,它是通過隨機(jī)機(jī)制M來控制隱私保證的程度。ε越小意味著隱私保護(hù)程度越高。ε默認(rèn)為一個(gè)正數(shù)并且它的數(shù)值通常比較小,例如:0.1、0.5和0.8。

附加噪聲的量不僅取決于隱私預(yù)算ε還取決于隨機(jī)機(jī)制的全局敏感度。全局敏感度反映了兩個(gè)相鄰數(shù)據(jù)集上函數(shù)輸出的最大差分。

定義3[12](拉普拉斯機(jī)制) 給定一個(gè)數(shù)據(jù)集D,隱私預(yù)算ε和一個(gè)隨機(jī)函數(shù)f:D→R,其全局敏感度是Δf,算法M(D)=f(D)+Lap(Δf/ε)滿足ε-差分隱私。

差分隱私有兩個(gè)重要的屬性。它們在判斷一種機(jī)制是否滿足差分隱私中起著重要的作用。

順序組合表明當(dāng)許多差分隱私被應(yīng)用于相同的數(shù)據(jù)集時(shí)隱私預(yù)算和噪聲會(huì)線性增加。

屬性2(平行組合)M={M1,M2,…,Mm}是一組隱私機(jī)制。如果每個(gè)Mi在不相交的數(shù)據(jù)集子集上提供ε-差分隱私,則Mi將提供(max{ε1,ε2,…,εm})-差分隱私。平行組合表明當(dāng)應(yīng)用于不同數(shù)據(jù)集子集中的一組差分隱私,其隱私保護(hù)程度取決于εi的最大值。

2 問題描述

假設(shè)數(shù)據(jù)所有者希望通過將特定于個(gè)人的數(shù)據(jù)發(fā)布給數(shù)據(jù)接受方來進(jìn)行聚類分析。這些原始數(shù)據(jù)可以被定義為一組記錄D={r1,r2,…,rn}},每個(gè)記錄ri(1≤i≤n)代表一種具有d屬性A={A1,A2,…,Ad}的個(gè)人信息。假定每一種屬性Aj(1≤j≤d)可以是分類的,數(shù)值的或集合值的,并且為每個(gè)分類或集合值的屬性給出了分類樹。在發(fā)布之前,應(yīng)刪除明確的標(biāo)識符,例如名稱和駕駛執(zhí)照編號。

聚類分析的任務(wù)是將對象分成若干組,使相似的對象在組中,不同的對象在不同的組中,聚類的結(jié)果可以用聚類結(jié)構(gòu)來表示。

定義5(聚類結(jié)構(gòu))[14]設(shè)g是聚類的個(gè)數(shù),數(shù)據(jù)集D={r1,r2,…,rn}的聚類結(jié)構(gòu)被定義為一個(gè)矩陣Un×g,矩陣的每個(gè)元素ei,j∈{1,0}(1≤i≤n,1≤j≤g)代表了記錄ri到第j個(gè)聚類的聚類分配,也就是說,當(dāng)ei,j等于1時(shí)記錄ri屬于第j個(gè)簇,而當(dāng)ei,j等于0時(shí)ri不屬于第j個(gè)簇。

基于上述假設(shè),有如下定義:

3 異構(gòu)數(shù)據(jù)發(fā)布方法

3.1 差分隱私的泛化算法

首先,數(shù)據(jù)所有者在原始數(shù)據(jù)集D上使用一種聚類算法來確定初始的聚類結(jié)構(gòu),同一聚類中的記錄有相同的聚類標(biāo)簽。與數(shù)據(jù)集D相比,標(biāo)記的數(shù)據(jù)集D*具有d+1個(gè)屬性A*={A1,A2,…,Ad,Class},其中Class表示類標(biāo)簽;即除了D中的原始屬性d,D*中的每條記錄ri也有一個(gè)類標(biāo)簽。因此,保存D的聚類結(jié)構(gòu)意味著在匿名化過程中保留識別這些類標(biāo)簽的能力,然后通過在D*上執(zhí)行所提出的差分隱私算法來獲取匿名數(shù)據(jù)集D′。如果D′不夠令人滿意,則數(shù)據(jù)所有者可以返回到第一步并且調(diào)整算法因子,即分類樹、聚類算法的選擇和聚類的數(shù)量。重復(fù)上述步驟直到得到效能滿意的D′。第四步,數(shù)據(jù)所有者將數(shù)據(jù)集D′釋放給數(shù)據(jù)接收者。

為異構(gòu)數(shù)據(jù)提出了一種稱為DPHeter的差分隱私的泛化算法,該算法基于自上而下的專業(yè)化技術(shù)[15]。專業(yè)化從最一般的狀態(tài)開始,然后通過將某些值替換為更具體的值來迭代下降,直到達(dá)到預(yù)定義的專業(yè)化數(shù)量。專業(yè)化過程就是根據(jù)相應(yīng)的分類樹,由表示將父值p→Children(p)替換為其直接連接的子值Children(p)。例如,圖1中Children([19,75])={[19,45],[45,75]}Children(ANY_SEX)={M,F},和Children(**)={1*,2*}

圖1 分類樹示意圖

交替使用術(shù)語“子節(jié)點(diǎn)”和“子值”。在下文中,還將可以替換為其直接關(guān)聯(lián)的子值的父值稱為“cut”。

圖1為數(shù)據(jù)專業(yè)化過程。首先,將每個(gè)值都概括為圖1所示對應(yīng)的分類樹上的最上面的值,并且初始值∪Cut為{[19,75],ANY_SEX,**}。假設(shè)將ANY_SEX剪切以向下切割,然后由于ANY_SEX→M,F和當(dāng)前∪Cut被更新為{[19,75],M,F,**}。

確保專業(yè)化過程滿足ε-差分隱私的關(guān)鍵是確定匿名化的每一步都是差分隱私的。其關(guān)鍵步驟包括切割選擇和劃分記錄。

選擇用指數(shù)機(jī)制來選擇割集是因?yàn)樵摍C(jī)制是為離散備選方案設(shè)計(jì)的。根據(jù)定義4可知,這個(gè)過程是需要效用函數(shù)的。另外采用屬性與類標(biāo)簽之間的信息增益作為效用函數(shù)。這是因?yàn)榍懈钌系拿總€(gè)專業(yè)化的過程中都傾向于通過生成特定的屬性值來增加信息,并且信息增益能夠基于這些值使類標(biāo)簽“更可預(yù)測化”。計(jì)算數(shù)據(jù)集D中屬性值x的熵的方法為:

一般化為其子值的屬性值p的效用函數(shù)定義為:

在每一次的專業(yè)化過程中,首先通過式(4)完成每個(gè)割集候選的效用分?jǐn)?shù),然后根據(jù)指數(shù)機(jī)制有效地選擇一個(gè)割以向下劃分。使用上述分類樹中的數(shù)據(jù),根據(jù)式(4)中ANY_SEX效用分?jǐn)?shù)計(jì)算為:

與上述計(jì)算類似,u([19,75])=0.281 2,u(**)=0.095 4,根據(jù)指數(shù)機(jī)制,[19,75]、ANY_SEX、**被選擇為切割的可能性分別是56.12%、24.85%和19.04%。

選擇剪切后,原始記錄分為不同的組。因?yàn)樗鼈兙哂蓄A(yù)定義的分類樹,所以分類屬性的劃分策略是固定的。因此分類屬性的分區(qū)函數(shù)的全局敏感性為1。根據(jù)當(dāng)前選擇的分類切割和相應(yīng)的分類樹,記錄分區(qū)的步驟應(yīng)滿足差分隱私。

與分類屬性相比,集值屬性專門化的區(qū)別在于子節(jié)點(diǎn)組合的存在。假設(shè)選擇一個(gè)設(shè)定值p,在它對應(yīng)的分類樹上有t個(gè)子節(jié)點(diǎn)。在p上的一般化將產(chǎn)生總共(2t-1)個(gè)子集。為了提高DPHeter的效率,應(yīng)盡早地剪掉子集。由于差分性隱私需要不確定性,因此通過驗(yàn)證其噪聲大小是否大于閾值,將其視為“非空”。也就是說,如果子分區(qū)的噪聲大小大于閾值,則保留該子分區(qū)。否則,將其視為“空”,應(yīng)該修剪。閾值可以由數(shù)據(jù)所有者控制。

如文獻(xiàn)[15]中所述,無須為數(shù)字屬性提供分類樹。如果選擇了數(shù)字分割以向下分割,則在搜索分割的分割值時(shí)將動(dòng)態(tài)生成或擴(kuò)展其相應(yīng)的分類樹。不應(yīng)為分割隨機(jī)選擇分割值,因?yàn)閺牟话撝档臄?shù)據(jù)集中選擇相同值的可能性為0。這意味著對數(shù)值屬性的分割值的選擇是概率性的。再次使用指數(shù)機(jī)制,計(jì)算數(shù)字切割中每個(gè)屬性值的效用得分,并使用指數(shù)機(jī)制選擇屬性值作為數(shù)字切割的分割值。選擇屬性值c作為數(shù)字割點(diǎn)p的分割值的概率定義為:

式中:ε是隱私預(yù)算,Δu是式(4)的全局敏感度,u(c)(或u(xi))是c(或xi)的效用分?jǐn)?shù),I(p)是剪切p的屬性值的集合。如果選擇[19,75)cut進(jìn)行分割,我們將計(jì)算每個(gè)屬性值在19到75范圍內(nèi)的效用得分,并且概率地選擇一個(gè)值作為[19,75)cut的分割值?？紤]21類屬性。然后,根據(jù)式(4),u(21)計(jì)算如下:

在計(jì)算完所有的u(·)后,式(5)用于計(jì)算每個(gè)值被選作實(shí)際拆分值的概率。

首先,為dnum數(shù)值屬性初始化分割值,其中dnum是數(shù)值屬性的數(shù)量。然后,針對每一輪專業(yè)化,概率性地選擇切割。如果切割是設(shè)置值的,則應(yīng)驗(yàn)證其非空子節(jié)點(diǎn),以確定它們是否真的是“非空”;如果切割為數(shù)字,則為其選擇分割值。請注意,這兩種情況是互斥的。每個(gè)葉分區(qū)節(jié)點(diǎn)中的確切記錄數(shù)不能直接發(fā)布,因?yàn)閷τ诓煌臄?shù)據(jù),該數(shù)目可能不同?？梢酝ㄟ^在每個(gè)節(jié)點(diǎn)中的記錄數(shù)量上增加噪聲來掩蓋這種差分。

3.2 隱私分析

定理1DPHeter滿足ε-差分隱私。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置與數(shù)據(jù)集

所有的實(shí)驗(yàn)都是在一臺3.4 GHz的CPU為英特爾酷睿i7,內(nèi)存大小為16 GB,操作系統(tǒng)為Windows 10(64位)的個(gè)人電腦上進(jìn)行的。下面所給出的每個(gè)結(jié)果都是運(yùn)行了5次以上的平均值。

實(shí)驗(yàn)使用了兩個(gè)公開的數(shù)據(jù)集,即Adult和MIMIC-III。Adult數(shù)據(jù)集包含人口普查記錄,文獻(xiàn)表明,該數(shù)據(jù)集已廣泛用于測試匿名方法。在實(shí)驗(yàn)中,刪除了類標(biāo)簽,并將此數(shù)據(jù)集用于聚類分析。為了綜合一個(gè)異構(gòu)數(shù)據(jù)集,假設(shè)一個(gè)人可以有多個(gè)職業(yè),然后將具有相同屬性值的記錄組合到一條記錄中,從而使職業(yè)屬性為集值。為了綜合處理,放棄了三個(gè)數(shù)值屬性(即fnlwg、資本收益和資本損失),因?yàn)樗鼈兛赡墚a(chǎn)生更少的異構(gòu)記錄。因此,保留了28 308條記錄,這些記錄具有7個(gè)分類屬性、6個(gè)數(shù)字屬性和1個(gè)集值屬性。為簡化問題,將合成數(shù)據(jù)集稱為Adult。

第二個(gè)數(shù)據(jù)集MIMIC-III是醫(yī)療研究的重要公共資源。它由一些臨床注釋表組成,包括護(hù)理記錄和出院摘要。具體來說,根據(jù)共享的subject_id列將三個(gè)表連接在一起。然后,將相同subject_id的多個(gè)ICD-9代碼合并為一行。檢索了48 612條記錄,并選擇了7個(gè)分類屬性,即性別、婚姻狀況、宗教、種族、入學(xué)類型,保險(xiǎn)方式和入學(xué)來源和一個(gè)集值屬性ICD-9代碼。

選擇K均值和平分K均值僅包含一個(gè)算法參數(shù),即聚類數(shù)K,而不是考慮聚類參數(shù)的不同組合[16-17]。任何聚類算法都需要某種方法來測量對象之間的距離或相似性。因此介紹兩個(gè)異構(gòu)記錄的語義距離度量。如果讓x1、x2表示來自同一域的兩個(gè)屬性值,則x1和x2之間的距離計(jì)算如下:

式中:path(x1,x2)是x1和x2之間最短路徑的長度,H是相應(yīng)分類法樹的高度。歸一化定義的優(yōu)勢在于,分類樹的所有葉節(jié)點(diǎn)可以具有不同的深度。兩個(gè)異構(gòu)記錄之間的距離,即r1和r2,定義為:

PPDP的目標(biāo)是在保護(hù)可觀數(shù)據(jù)實(shí)用性的同時(shí)保護(hù)原始數(shù)據(jù)集的私人信息。通過匿名前后的聚類結(jié)構(gòu)的相似性來確定數(shù)據(jù)實(shí)用性。也就是說,匿名化前后的聚類結(jié)構(gòu)越相似,匿名化數(shù)據(jù)集的效用就越高。在實(shí)驗(yàn)中,應(yīng)用兩個(gè)指標(biāo)F-measure和MatchPoint評估兩個(gè)聚類結(jié)構(gòu)的相似性。

考慮兩個(gè)聚類結(jié)構(gòu)T和P,并將T中的每個(gè)聚類Ti視為“真實(shí)聚類”,并將P中的每個(gè)聚類Pj視為“預(yù)測聚類”。令numij表示同時(shí)包含在Ti和Pj中的記錄數(shù),并且|·|表示聚類中對象的數(shù)量。Ti和Pj的Precison、Recall和F-measure計(jì)算如下:

它測量聚類Pj預(yù)測的準(zhǔn)確性,該預(yù)測基于Precison和Recall描述了真實(shí)的聚類Ti。真實(shí)聚類Ti的成功預(yù)測是通過Ti的“最佳”預(yù)測聚類Pj來衡量的,即Pj的最大化F(Ti,Pj)。因此,加權(quán)最大F-measure的總和用于評估P的質(zhì)量,并且P的整體F-measure計(jì)算為:

式中:|D|是原始數(shù)據(jù)集D中的記錄數(shù)。F-measure(P)的范圍是0到1。F-measure(P)的值越大,比較的兩個(gè)聚類結(jié)構(gòu)越相似。

如果兩個(gè)保留在同一個(gè)聚類C1中的記錄在C2中一起保存,并且C1中不同聚類的兩個(gè)記錄被分在C2中不同的聚類里則說明兩個(gè)聚類結(jié)構(gòu)C1和C2相同。對于每個(gè)聚類結(jié)構(gòu),都將生成一個(gè)方矩陣Matrix(·)來表示每對記錄之間的關(guān)系。也就是說,如果第i個(gè)記錄和第j個(gè)記錄在同一聚類中,則Matrix(·)中的第(i,j)個(gè)元素等于1;否則等于0。然后,定義MatchPoint來表示Matrix(C1)和Matrix(C2)中出現(xiàn)的相同值的百分比:

如果Matrix(C1)和Matrix(C2)中第(i,j)個(gè)元素的值相同,則mij等于1;否則,mij等于0,并且|D|是原始數(shù)據(jù)集D中的記錄數(shù)。MatchPoint的范圍是0到1。MatchPoint的值越大,比較的兩個(gè)聚類結(jié)構(gòu)越相似。

4.2 結(jié)果分析

4.2.1數(shù)據(jù)實(shí)用性和隱私

在該實(shí)驗(yàn)中,改變了隱私預(yù)算ε,專業(yè)化數(shù)目h和聚類數(shù)k,以觀察F-measure和MatchPoint。

圖2-圖5顯示了Adult的結(jié)果。其中,圖2(a)顯示了當(dāng)ε=0.1且h=4時(shí),最小F-measure為0.540 8。圖3(a)還顯示當(dāng)ε=0.1且h=16最大F-measure為0.784 0。從圖2-圖3可以看出,與F-measure相比,不同于ε和h值的MatchPoint值的跨度較小,大約在0.727 0～0.931 4范圍內(nèi)。有一個(gè)明顯的趨勢表明隨著較高的ε導(dǎo)致較少的干擾和較少的噪聲,F-measure值隨ε的增加而增加。另外,F-measure和MatchPoint也隨著h的增加而增加,因?yàn)楦敿?xì)的信息保留在用于聚類的匿名數(shù)據(jù)集中。但是,從一定的h開始,隨著h的進(jìn)一步增加,F-measure和MatchPoint保持相同或減少。這是因?yàn)閔的值越高,表示分區(qū)樹中的葉子節(jié)點(diǎn)越多,并且葉子節(jié)點(diǎn)的數(shù)量越多,作用于這些葉子中的記錄數(shù)的拉普拉斯機(jī)制產(chǎn)生的噪聲越多節(jié)點(diǎn)。圖4-圖5顯示了MIMIC的F-measure和MatchPoint值的相似趨勢,只有在獲得最佳性能的情況下和h的值不同。這些結(jié)果表明,DPHeter即使對于不同的匿名性要求,也可以在匿名化后保持原始數(shù)據(jù)集的相似聚類結(jié)構(gòu)。

(a) F-measure效用

(a) F-measure效用

(a) F-measure效用

(a) F-measure效用

4.2.2不同匿名化算法上的數(shù)據(jù)實(shí)用程序

為了驗(yàn)證提出的聚類算法聚類質(zhì)量是否比沒有這傾向的一般差分隱私的聚類質(zhì)量更好,在ARX工具中將本文的算法與(ε,δ)-差分隱私進(jìn)行了比較。(ε,δ)-差分隱私是ε-差分隱私的松弛版本,因?yàn)榍罢咴试S以δ為邊界的錯(cuò)誤概率。因?yàn)橹挥嘘P(guān)系數(shù)據(jù)可以輸入到ARX,所以首先將異構(gòu)的Adult和MIMIC轉(zhuǎn)換為關(guān)系數(shù)據(jù)。具體來說,將為值屬性集合的每個(gè)值創(chuàng)建一個(gè)二進(jìn)制屬性。例如,如果屬性是值集合的并且具有2個(gè)值,即x1和x2,則記錄的模式將為“0 1”“1 0”或“1 1”。此類轉(zhuǎn)換僅對ARX執(zhí)行,對DPHeter不執(zhí)行。之所以為(ε,δ)-差分隱私設(shè)置δ=1E-5和δ=1E-11,是因?yàn)閷τ谠摴ぞ?這兩個(gè)值分別是最大和最小可接受值。將DPHeter的h固定為16。

結(jié)果如圖6所示。這些數(shù)字表明,在每個(gè)隱私預(yù)算上,DPHeter的F-measure值明顯優(yōu)于(ε,δ)-差分隱私。例如,在圖7中,即使ε=0.1,Adult的F-measure為0.633 1,而MIMIC的F-measure為0.642 8,而當(dāng)δ=1E-5時(shí)Adult和F-measure的(ε,δ)-差分隱私的F-measure分別僅為0.201 5和0.332 8但是,MatchPoint值之間的差分較小。這是因?yàn)槟涿昂笪挥诓煌垲愔械膬蓚€(gè)記錄的情況也對MatchPoint的值起了積極的意義。

(a) F-measure效用

(a) F-measure效用

當(dāng)0.1≤ε≤1評估ARX工具中DPHeter相對于(ε,1E-5)的DPHeter改進(jìn)時(shí),還對0.1≤ε≤1成對測試用例進(jìn)行了一系列單尾t檢驗(yàn),證明DPHeter的改善在α=5%時(shí)具有顯著的統(tǒng)計(jì)學(xué)意義。從這些結(jié)果可以推出,提出的方法在聚類質(zhì)量方面勝過了一般的匿名化方法。

4.2.3不同聚類算法上的數(shù)據(jù)實(shí)用程序

在本實(shí)驗(yàn)中,研究了在數(shù)據(jù)接收者應(yīng)用與數(shù)據(jù)所有者使用的聚類算法不同的聚類算法的情況下的數(shù)據(jù)實(shí)用程序。以兩種不同的順序應(yīng)用了5-均值和等分5-均值,分別表示為等分5-均值→5-均值以及5-均值→等分5-均值。

圖8、圖9分別顯示了匿名的Adult和MIMIC的數(shù)據(jù)實(shí)用程序。除了圖8中ε=0.25和h=4的情況外,所有F-Measure值均高于0.5。具體表現(xiàn)在,對于Adult和MIMIC,最大的F-Measure值是0.766 0和0.757 7。MatchPoint的所有值均高于0.720 6,Adult和MIMIC的平均MatchPoint值分別為0.812 7和0.840 1。

(a) 5均值聚類算法

(a) 5均值聚類算法

這些結(jié)果表明DPHeter即使使用不同的聚類算法,也具有良好的數(shù)據(jù)實(shí)用性。在這些不同實(shí)體聚類算法中使用的記錄之間的距離度量應(yīng)保持相同或相似。否則,由不同聚類算法產(chǎn)生的聚類結(jié)構(gòu)可能完全不同。

與4.2.2節(jié)中的實(shí)驗(yàn)結(jié)果相比,不同聚類算法上的數(shù)據(jù)效用可能不是很穩(wěn)定。例如,在圖9(b)中,h=16時(shí)F-Measure的平均值僅為0.571 9,比h=12和h=16時(shí)的平均值小。該算法可能與其他聚類算法產(chǎn)生的結(jié)構(gòu)不同,因?yàn)樗鼈兊乃阉鳁l件不同。

4.2.4可擴(kuò)展性

在可擴(kuò)展性方面,將DPHeter與ARX中的(ε,δ)-差分隱私進(jìn)行了比較。與第4.2.2節(jié)中的實(shí)驗(yàn)相似,我們?yōu)?ε,δ)-差分隱私設(shè)置δ=1E-5和δ=1E-11,為DPHeter設(shè)置h=16。我們還固定了ε=1并進(jìn)行了5-均值聚類。通過隨機(jī)復(fù)制他們的記錄,生成了多個(gè)版本的Adult和MIMIC。為了比較,圖10顯示了具有200 000至1 000 000條數(shù)據(jù)記錄的DPHeter和ARX在Adult和MIMIC上的結(jié)果。可以看出,在運(yùn)行時(shí)方面,ARX比DPHeter更有效,因?yàn)锳RX不考慮數(shù)據(jù)分析任務(wù)。在搜索數(shù)值屬性的分割值時(shí),DPHeter將計(jì)算當(dāng)前值范圍內(nèi)所有可能數(shù)值的效用分?jǐn)?shù)。在拆分集值屬性時(shí),DPHeter根據(jù)分類樹考慮當(dāng)前父節(jié)點(diǎn)的子節(jié)點(diǎn)的組合。通過維護(hù)和更新信息,而不是重復(fù)掃描所有數(shù)據(jù)記錄,進(jìn)一步提高了DPHeter的運(yùn)行速度。而在MIMIC上花費(fèi)的時(shí)間比在Adult上花費(fèi)的時(shí)間更長。這是因?yàn)橹杏谐汕先f個(gè)代碼,并且相應(yīng)的分類樹比t中的職業(yè)屬性樹大得多,這意味著選擇代碼屬性進(jìn)行拆分時(shí)需要更多的計(jì)算時(shí)間。

DPHeter的適應(yīng)性。雖然在文中只使用了k-均值和等分k-均值來評估DPHeter的性能,但是其他的聚類算法,例如DBSCAN,可以集成到我們的方法中。提出的方法提供了一個(gè)靈活的框架,在這個(gè)框架中,聚類算法可以被視為“插件”組件。DPHeter利用將聚類結(jié)果對原始數(shù)據(jù)進(jìn)行匿名化處理,而并非一種聚類算法。然而,數(shù)據(jù)匿名化前后用于聚類的距離度量應(yīng)該保持不變,或者至少相似,以獲得更好的數(shù)據(jù)效用。否則,不同聚類策略所生成的聚類結(jié)構(gòu)將會(huì)完全不同。同時(shí),DPHeter的關(guān)注點(diǎn)是在數(shù)據(jù)發(fā)布的前后保持聚類結(jié)構(gòu)的相似性。如果原始數(shù)據(jù)不適用于聚類分析或者某些聚類算法無法產(chǎn)生好的聚類結(jié)果,那么DPHeter就無法幫助數(shù)據(jù)或其匿名版本生成更好的數(shù)據(jù)。

5 結(jié) 語

本文介紹了一種用于聚類分析的異構(gòu)數(shù)據(jù)發(fā)布方法。該方法利用聚類標(biāo)簽對聚類結(jié)構(gòu)進(jìn)行編碼,并結(jié)合泛化技術(shù)和輸出擾動(dòng)來掩蓋原始數(shù)據(jù)。通過分析實(shí)驗(yàn)結(jié)果可得如下結(jié)論:

(1) 提出的方法即使對于不同的匿名性要求,也可以在匿名化后保持原始數(shù)據(jù)集的相似聚類結(jié)構(gòu)。

(2) 引入了差分隱私方法的聚類質(zhì)量比未引入差分隱私的匿名化方法更高,說明差分隱私有助于聚類性能的提高。

(3) 提出的方法提供了一個(gè)適應(yīng)性較強(qiáng)的框架,可以結(jié)合不同的聚類算法,且都能夠具有良好的數(shù)據(jù)實(shí)用。在這些不同實(shí)體聚類算法中使用的記錄之間的距離度量應(yīng)保持相同或相似。否則,由不同聚類算法產(chǎn)生的聚類結(jié)構(gòu)可能完全不同。

本文雖然分析了提出方法的有效性,但是缺乏與其他隱私數(shù)據(jù)發(fā)布方法的對比研究,對于該方法的實(shí)際應(yīng)用也缺乏可行性分析,這些都是實(shí)驗(yàn)室下一步研究的重點(diǎn)。