基于聚類(lèi)分析的個(gè)性化異構(gòu)數(shù)據(jù)發(fā)布

聶 靜，常 濤，劉 維，呂小紅，王 晨，楊知方

(1.國(guó)網(wǎng)重慶市電力公司，重慶 400014；2.輸配電裝備及系統(tǒng)安全與新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(重慶大學(xué))，重慶 400014)

在如今的大數(shù)據(jù)時(shí)代，數(shù)據(jù)的價(jià)值已經(jīng)越來(lái)越被人們所重視[1-2]。對(duì)于公共數(shù)據(jù)發(fā)布中存在的隱私保護(hù)問(wèn)題也越來(lái)越受到關(guān)注，如何實(shí)現(xiàn)安全有效的數(shù)據(jù)發(fā)布成為了一個(gè)研究熱點(diǎn)[3]。

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

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

針對(duì)上述問(wèn)題，現(xiàn)提出一種基于聚類(lèi)分析的個(gè)性化異構(gòu)數(shù)據(jù)發(fā)布方法。利用聚類(lèi)標(biāo)簽對(duì)聚類(lèi)結(jié)構(gòu)進(jìn)行編碼，并結(jié)合泛化技術(shù)和輸出擾動(dòng)來(lái)掩蓋原始數(shù)據(jù)。以期有效解決異構(gòu)數(shù)據(jù)發(fā)布問(wèn)題。

1 差分隱私

(1)

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

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

(2)

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

差分隱私有兩個(gè)重要的屬性。它們?cè)谂袛嘁环N機(jī)制是否滿(mǎn)足差分隱私中起著重要的作用。

順序組合表明當(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 問(wèn)題描述

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

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

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

基于上述假設(shè)，有如下定義：

定義6(聚類(lèi)分析差分隱私異構(gòu)數(shù)據(jù))：給定一個(gè)數(shù)據(jù)集D={r1,r2,…,rn}和隱私預(yù)算ε，對(duì)異構(gòu)數(shù)據(jù)進(jìn)行聚類(lèi)分析的匿名化問(wèn)題是使是使數(shù)據(jù)集D使不同類(lèi)型的屬性上匿名化。例如，滿(mǎn)足ε-差分隱私并且盡可能與D的聚類(lèi)結(jié)構(gòu)保持相似的匿名數(shù)據(jù)集D′={r′1,r′2,…}。

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

3.1 差分隱私的泛化算法

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

為異構(gòu)數(shù)據(jù)提出了一種稱(chēng)為DPHeter的差分隱私的泛化算法，該算法基于自上而下的專(zhuān)業(yè)化技術(shù)[15]。專(zhuān)業(yè)化從最一般的狀態(tài)開(kāi)始，然后通過(guò)將某些值替換為更具體的值來(lái)迭代下降，直到達(dá)到預(yù)定義的專(zhuān)業(yè)化數(shù)量。專(zhuān)業(yè)化過(guò)程就是根據(jù)相應(yīng)的分類(lèi)樹(shù)，由表示將父值p→Children(p)替換為其直接連接的子值Children(p)。交替使用術(shù)語(yǔ)“子節(jié)點(diǎn)”和“子值”。在下文中，還將可以替換為其直接關(guān)聯(lián)的子值的父值稱(chēng)為“cut”。

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

圖1 分類(lèi)樹(shù)示意圖Fig.1 Schematic diagram of classification tree

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

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

(3)

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

(4)

在每一次的專(zhuān)業(yè)化過(guò)程中，首先通過(guò)式(4)完成每個(gè)割集候選的效用分?jǐn)?shù)，然后根據(jù)指數(shù)機(jī)制有效地選擇一個(gè)割以向下劃分。Children(ANY_SEX)={M,F}。根據(jù)式(4)中ANY_SEX效用分?jǐn)?shù)計(jì)算為

與上述計(jì)算類(lèi)似，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ù)定義的分類(lèi)樹(shù)，所以分類(lèi)屬性的劃分策略是固定的。因此分類(lèi)屬性的分區(qū)函數(shù)的全局敏感性為1。根據(jù)當(dāng)前選擇的分類(lèi)切割和相應(yīng)的分類(lèi)樹(shù)，記錄分區(qū)的步驟應(yīng)滿(mǎn)足差分隱私。

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

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

(5)

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

u(21)=H21(D)-

0.144 5。

在計(jì)算完所有的u(·)后，式(5)用于計(jì)算每個(gè)值被選作實(shí)際拆分值的概率。首先，為dnum數(shù)值屬性初始化分割值，其中dnum是數(shù)值屬性的數(shù)量。然后，針對(duì)每一輪專(zhuān)業(yè)化，概率性地選擇切割。如果切割是設(shè)置值的，則應(yīng)驗(yàn)證其非空子節(jié)點(diǎn)，以確定它們是否真的是“非空”；如果切割為數(shù)字，則為其選擇分割值。請(qǐng)注意，這兩種情況是互斥的。每個(gè)葉分區(qū)節(jié)點(diǎn)中的確切記錄數(shù)不能直接發(fā)布，因?yàn)閷?duì)于不同的數(shù)據(jù)，該數(shù)目可能不同。可以通過(guò)在每個(gè)節(jié)點(diǎn)中的記錄數(shù)量上增加噪聲來(lái)掩蓋這種差分。

3.2 隱私分析

定理1DPHeter滿(mǎn)足ε-差分隱私。

定理2DPHeter時(shí)間復(fù)雜度為O(h·nlog2n)。

證明：DPHeter為數(shù)值屬性選擇一個(gè)時(shí)間復(fù)雜度為O(nlog2n)地分割值，其中n是輸入的大小數(shù)據(jù)集。dnum數(shù)值屬性確定拆分值，其時(shí)間復(fù)雜度為O(dnum·nlog2n)。通過(guò)遍歷具有d屬性，其時(shí)間復(fù)雜度為O(d·nlog2n)的輸入數(shù)據(jù)集，然后DPHeter無(wú)需遍歷所有數(shù)據(jù)記錄，而是根據(jù)為∪cut中候選數(shù)據(jù)保留的某些信息來(lái)計(jì)算效用分?jǐn)?shù)；因此相應(yīng)的時(shí)間復(fù)雜度僅要求是O(n)。根據(jù)定義4，從指數(shù)機(jī)制選擇切割時(shí)，它的成本與離散切割的數(shù)量成正比。因此，基于概率選擇算法的成本為O(|∪cuti|)，其中|∪cuti|是∪cuti的大小，數(shù)值屬性選擇的時(shí)間復(fù)雜度為O(nlog2n)的分隔值。通常|∪cuti|比n小的多。因此，循環(huán)迭代效能滿(mǎn)意算法成本為O(h·nlog2n)。其他計(jì)算均可以在恒定的時(shí)間O(1)內(nèi)被完成。因此，DPHeter的總運(yùn)行時(shí)間為O(h·nlog2n)。

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

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

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

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

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

(6)

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

(7)

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

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

(8)

(9)

F(Ti,Pj)=2×

(10)

它測(cè)量聚類(lèi)Pj預(yù)測(cè)的準(zhǔn)確性，該預(yù)測(cè)基于Precison和Recall描述了真實(shí)的聚類(lèi)Ti。真實(shí)聚類(lèi)Ti的成功預(yù)測(cè)是通過(guò)Ti的“最佳”預(yù)測(cè)聚類(lèi)Pj來(lái)衡量的，即Pj的最大化F(Ti,Pj)。因此，加權(quán)最大F-Measure的總和用于評(píng)估聚類(lèi)結(jié)構(gòu)P的質(zhì)量，并且P的整體F-Measure計(jì)算為

(11)

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

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

MatchPoint[Matrix(C1),Matrix(C2)]=

(12)

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

4.2 結(jié)果分析

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

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

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

圖2 3均值A(chǔ)dult數(shù)據(jù)的效用Fig.2 3 utility of mean Adult data

圖3 5均值A(chǔ)dult數(shù)據(jù)的效用Fig.3 5 utility of mean Adult data

圖4 對(duì)等分3均值A(chǔ)dult數(shù)據(jù)的效用Fig.4 The utility of Adult data with equal 3-means

圖5 對(duì)等分5均值A(chǔ)dult數(shù)據(jù)的效用Fig.5 The utility of Adult data with equal 5-means

圖6 3均值匿名MIMIC的數(shù)據(jù)效用Fig.6 3 utility of mean MIMIC data

圖7 5均值匿名MIMIC的數(shù)據(jù)效用Fig.7 5 utility of mean MIMIC data

圖8 對(duì)等分3均值匿名MIMIC的數(shù)據(jù)效用Fig.8 Data utility for 3-means anonymous MMIC

圖9 對(duì)等分5均值匿名MIMIC的數(shù)據(jù)效用Fig.9 Data utility for 5-means anonymous MIMIC

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

為了驗(yàn)證提出的聚類(lèi)算法聚類(lèi)質(zhì)量是否比沒(méi)有這傾向的一般差分隱私的聚類(lèi)質(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ù)。具體來(lái)說(shuō)，將為值屬性集合的每個(gè)值創(chuàng)建一個(gè)二進(jìn)制屬性。例如，如果屬性是值集合的并且具有兩個(gè)值，即x1和x2，則記錄的模式將為“0 1”“1 0”或“1 1”。此類(lèi)轉(zhuǎn)換僅對(duì)ARX執(zhí)行，對(duì)DPHeter不執(zhí)行。之所以為(ε,δ)-差分隱私設(shè)置δ=1×10-5和δ=1×10-11，是因?yàn)閷?duì)于該工具，這兩個(gè)值分別是最大和最小可接受值。將DPHeter的h固定為16。結(jié)果如圖10～圖13所示。這些數(shù)字表明，在每個(gè)隱私預(yù)算上，DPHeter的F-measure值明顯優(yōu)于(ε,δ)-差分隱私。例如，在圖11(a)和圖13(a)中，即使ε=0.1，Adult的F-measure為0.633 1，而MIMIC的F-measure為0.642 8，而當(dāng)δ=1×10-5時(shí)Adult和F-measure的(ε,δ)-差分隱私的F-measure分別僅為0.201 5和0.332 8,但是，MatchPoint值之間的差分較小。這是因?yàn)槟涿昂笪挥诓煌垲?lèi)中的兩個(gè)記錄的情況也對(duì)MatchPoint的值起了積極的意義。

圖10 Adult數(shù)據(jù)不同的5-均值匿名算法Fig.10 Different 5-means anonymity algorithms for Adult data

圖11 Adult數(shù)據(jù)不同的對(duì)等分5-均值匿名算法Fig.11 Different 5-means anonymity algorithms for Adult data

圖12 5均值的MIMIC匿名算法Fig.12 5 mean MIMIC anonymous algorithm

圖13 對(duì)等分5均值的MIMIC匿名算法Fig.13 5 mean MIMIC anonymous algorithm

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

4.2.3 可擴(kuò)展性

在可擴(kuò)展性方面，將DPHeter與ARX中的(ε,δ)-差分隱私進(jìn)行了比較。與第4.2.2節(jié)中的實(shí)驗(yàn)相似，為(ε,δ)-差分隱私設(shè)置δ=1×10-5和δ=1×10-11，為DPHeter設(shè)置h=16。并固定了ε=1并進(jìn)行了5-均值聚類(lèi)。通過(guò)隨機(jī)復(fù)制它們的記錄，生成了多個(gè)版本的Adult和MIMIC。為了比較，圖14顯示了具有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ù)分類(lèi)樹(shù)考慮當(dāng)前父節(jié)點(diǎn)的子節(jié)點(diǎn)的組合。通過(guò)維護(hù)和更新信息，而不是重復(fù)掃描所有數(shù)據(jù)記錄，進(jìn)一步提高了DPHeter的運(yùn)行速度。而在MIMIC上花費(fèi)的時(shí)間比在Adult上花費(fèi)的時(shí)間更長(zhǎng)。這是因?yàn)橹杏谐汕先f(wàn)個(gè)代碼，并且相應(yīng)的分類(lèi)樹(shù)比t中的職業(yè)屬性樹(shù)大得多，這意味著選擇代碼屬性進(jìn)行拆分時(shí)需要更多的計(jì)算時(shí)間。

圖14 兩個(gè)數(shù)據(jù)集的可擴(kuò)展性Fig.14 Scalability of two datasets

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

5 結(jié)論

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

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

(2)引入了差分隱私方法的聚類(lèi)質(zhì)量比為引入差分隱私的匿名化方法更高，說(shuō)明差分隱私有助于聚類(lèi)性能的提高。

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