吳榮士，葉欣欣，許林濤，裴成飛

(安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001)

在大數(shù)據(jù)時(shí)代，保護(hù)個(gè)人隱私信息至關(guān)重要。通常，生成適合發(fā)布的匿名數(shù)據(jù)集需要在披露風(fēng)險(xiǎn)和信息損失之間找到權(quán)衡。k匿名[1-2]是一種較成熟的隱私模型，可以防止身份泄露，但是不能防止屬性泄露?；趉匿名衍生出許多擴(kuò)展模型，如(α,k)-anonymity[3]、l-diversity[4]、(k,l)-diversity[5]、t-closeness[6]等?？紤]到嚴(yán)格的隱私保證，本文重點(diǎn)關(guān)注t-closeness模型。Wang Rong等[7]提出了一種基于Equi-sized FCM聚類方法的多敏感屬性t-closeness算法，該算法在等價(jià)類生成的過程中沒有添加t-closeness限制，不能保證生成的等價(jià)類滿足t-closeness, 從而使得最后生成的等價(jià)類可能包含過多數(shù)量的記錄，降低了數(shù)據(jù)效用。 基于此問題，本文基于k-means++聚類，在等價(jià)類生成的過程中添加t-closeness限制，使得生成的等價(jià)類盡可能滿足t-closeness，從而能夠在保護(hù)隱私的前提下提高數(shù)據(jù)效用。

1 基本概念

假設(shè)數(shù)據(jù)集D={QI1,QI2,…,QIn,SA1,SA2,…,SAm}有N條記錄，每條記錄ri(1≤i≤N)包括n個(gè)準(zhǔn)標(biāo)識(shí)屬性QI1、QI2、…、QIn和m個(gè)敏感屬性SA1、SA2、…、SAm，準(zhǔn)標(biāo)識(shí)屬性的域?yàn)镈om(QIi)(1≤i≤n),敏感屬性的域?yàn)镈om(QIi)(1≤i≤n)，ri[A]表示記錄ri(1≤i≤N)在屬性A上的取值。

1.1 k匿名

如果攻擊者能夠確定匿名數(shù)據(jù)集中的某條記錄所對應(yīng)的用戶身份時(shí)，就可以重新識(shí)別這條記錄。在這種情況下，攻擊者可以將重新識(shí)別的記錄中的敏感屬性值與用戶的身份相關(guān)聯(lián)，從而獲取用戶的隱私。k匿名就是為了限制攻擊者重新識(shí)別用戶身份的能力。

定義1 (k匿名)[1]：對于數(shù)據(jù)集D中的準(zhǔn)標(biāo)識(shí)屬性，其屬性值的每個(gè)組合在共享該組合的數(shù)據(jù)集D中存在至少k條記錄，則稱數(shù)據(jù)集D滿足整數(shù)為k(k≥2)的k匿名。

在k匿名數(shù)據(jù)集中，每個(gè)用戶的身份可被鏈接到至少k條記錄。因此，基于準(zhǔn)標(biāo)識(shí)屬性，攻擊者至多有1/k的概率能夠正確的識(shí)別出用戶的身份。

1.2 t-closeness

k匿名性可以防止身份泄露，但是不能夠防止屬性泄露。當(dāng)?shù)葍r(jià)類中的敏感屬性值的可變性太低時(shí)，容易發(fā)生屬性泄露。針對這一問題，目前已經(jīng)提出了一些k匿名的擴(kuò)展方法用于限制屬性泄露，t-closeness就是其中之一。t-closeness具有嚴(yán)格的隱私保證，它要求每個(gè)等價(jià)類內(nèi)的敏感屬性的分布與其在整個(gè)數(shù)據(jù)集中的分布相似。例如：某醫(yī)療機(jī)構(gòu)的原始數(shù)據(jù)集如表1所示，基于表1的滿足0.33-closeness的匿名化數(shù)據(jù)如表2所示。本文主要基于t-closeness進(jìn)行討論。

定義2(t-closeness)[6]：對于數(shù)據(jù)集D中的某個(gè)等價(jià)類，其敏感屬性在類內(nèi)的分布與在整個(gè)數(shù)據(jù)集上的分布距離不超過閾值t, 則稱該等價(jià)類滿足t-closeness，如果數(shù)據(jù)集中的所有等價(jià)類均滿足t-closeness，則稱D滿足t-closeness。

t-closeness中常用于求分布之間距離的方法是陸地移動(dòng)距離(EMD)[8],EMD(P,Q) 通過移動(dòng)概率質(zhì)量來度量將一個(gè)分布P轉(zhuǎn)換成另一個(gè)分布Q的成本。EMD計(jì)算為把箱子P移動(dòng)到箱子Q所需的最小移動(dòng)成本，它取決于移動(dòng)的質(zhì)量以及移動(dòng)的距離。對于數(shù)值屬性，兩個(gè)箱子之間的距離與它們之間箱子的數(shù)量有關(guān)。設(shè)數(shù)值屬性取值為{a1,a2,…,am}，且i

(1)

表1 某醫(yī)療機(jī)構(gòu)原始數(shù)據(jù)

表2 基于表1滿足0.33-closeness的匿名化數(shù)據(jù)

1.3 信息損失度量

本文使用兩種方法來度量匿名化前后數(shù)據(jù)的損失，一種是概化損失度量(generalized loss metric)[9-11]，記QI= {QI1,QI2,…QIn}為數(shù)據(jù)集D的標(biāo)識(shí)符屬性集。對于數(shù)值屬性，設(shè)QIi在D中的域?yàn)閇L,H],a為QIi中的一個(gè)屬性值，a概化后的值范圍為[La,Ha],則屬性值a信息損失被定義為

(2)

那么D中的一條記錄rD匿名化后的信息損失為

(3)

數(shù)據(jù)集D匿名化后的信息損失為

(4)

平方誤差總和(SSE)是另一種常用的信息損失量度方法，適合度量通過k匿名微聚集創(chuàng)建等價(jià)類的效用。本文中，SSE定義為匿名化前后屬性值損失的平方和：

(5)

式中：N為D中記錄的條數(shù)；n為準(zhǔn)標(biāo)識(shí)符屬性的個(gè)數(shù)。

2 多敏感屬性的t-closeness隱私保護(hù)算法

2.1 多敏感屬性t-closeness

現(xiàn)有的關(guān)于t-closeness的工作大多數(shù)僅考慮單敏感屬性，而現(xiàn)實(shí)生活中敏感屬性往往有多個(gè)。Wang等提出了一個(gè)關(guān)于多敏感屬性的t-closeness定義，該定義分別考慮每個(gè)敏感屬性的分布，然后取最大接近度，本文仍采用這種定義方式。

定義3 (多敏感屬性t-closeness)[7]：記EC={QI1,QI2,…,QIn,SA1,SA2,…,SAm}為多敏感屬性數(shù)據(jù)集D中的一個(gè)等價(jià)類, 敏感屬性SAi(i=1,2,…,m)在EC中的分布與在D中的分布距離為ti(i=1,2,…,m)，如果max(t1,t2,…,tm) ≤t，則該等價(jià)類滿足t-closeness,如果D中的所有等價(jià)類均滿足t-closeness,則認(rèn)為D滿足t-closeness。

2.2 基于k-means++聚類的多敏感屬性t-closeness算法

生成滿足t-closeness的數(shù)據(jù)集本質(zhì)上是一個(gè)優(yōu)化問題，即必須找到滿足t-closeness的最優(yōu)概化。我們提出了一個(gè)基于k-means++聚類的多敏感屬性t-closeness算法，該算法由4個(gè)部分組成。第1個(gè)過程是聚類，如算法1中的行(1)所示，使用k-means++算法生成一個(gè)基于多敏感屬性的k個(gè)分組，本文僅考慮數(shù)值屬性，因此采用歐式距離來計(jì)算兩條記錄之間的距離，即對于D中的任意兩條記錄r1(QI11,QI12,…,QI1n,SA11,SA12,…,SA1m)和r2(QI21,QI22,…,QI2n,SA21,SA22,…,SA2m)，r1與r2之間基于QI屬性和SA屬性的距離分別為

(6)

(7)

第2個(gè)過程是一個(gè)生成等價(jià)類的過程，根據(jù)第1個(gè)過程產(chǎn)生的基于多敏感屬性的k個(gè)分組, 循環(huán)地從每個(gè)分組中抽取一條記錄組成大小為k的等價(jià)類，然后判斷該等價(jià)類是否滿足t-closeness，如果不滿足，則從剩余的記錄中選取一條距離等價(jià)類最近的記錄替換掉等價(jià)類中的某條記錄以使得等價(jià)類最接近t-closeness，重復(fù)上述步驟，直到所有等價(jià)類均被選出來，如算法1中行(2)-行(27)所示。

算法1 基于k-means++聚類的多敏感屬性t-closeness算法

輸入：

D:原始數(shù)據(jù)集，k:k匿名水平，t:t-closeness水平

輸出：

滿足k匿名和t-closeness的數(shù)據(jù)集C′

(1)利用公式(7)對D進(jìn)行k-means++聚類，得到k個(gè)分組C={C1,C2,…,Ck}

(2)初始化C′ = ?；

(3)whileC≠ ? andC中的記錄條數(shù)大于等于2k

(4)初始化等價(jià)類EC=?

(5)r=C1中隨機(jī)選取一條記錄;EC=EC∪ {r};C1=C1(]r}

(6)while |EC|

(7)分別從2～k個(gè)分組中選取一條與r最近的記錄，如果2～k個(gè)分組均為空，則從第1個(gè)分組中選取

只要保證路面的平整、清潔，同步碎石封層技術(shù)才能夠正常進(jìn)行。因?yàn)橥剿槭鈱蛹夹g(shù)要想對道路養(yǎng)護(hù)的效果好，就必須在平整的里面上進(jìn)行操作，只要這樣才能保證與地面充分接觸，養(yǎng)護(hù)效果好。如若地面不平整或地面灰塵多，清潔度差，瀝青與顆粒性碎石和地面的粘合程度收到影響，使得同步碎石封層技術(shù)的效果就大大降低，質(zhì)量大打折扣，并且不利于施工完成后期對該整修路段的監(jiān)修和養(yǎng)護(hù)工作的開展。因此，道路平整且整潔是該技術(shù)正常進(jìn)行的基礎(chǔ)。

(8)end while

(9)D′ =C中所有剩余記錄的集合

(10)r1=EC的質(zhì)心(基于QI屬性)

(11)whileEMD(EC,D) >tandD′ ≠ ? do

(12)y=D′ 中與r1最近的記錄

(13)y0=EC中使得EMD(EC∪{y} {y0},D)

(14)ifEMD(EC∪{y} {y0},D)

(15)EC=EC∪{y} {y0}

(16)C=C/y//將y從C中對應(yīng)的分組中刪除

(17)C=C∪y0// 將y0加入C中對應(yīng)的分組中

(18)r1=EC的簇心(基于QI屬性)

(19)end if

(20)D′=D′ {y}

(21)end while

(22)C′=C′∪EC

(23)end while

(24) ifC≠ ? then

(25)EC=C中剩余的記錄條數(shù)

(26)C′ =C′∪EC

(27) end if

(28)whileEMD(C′,D) >tdo

(29)C=C′中使得EMD(C,D)最大的等價(jià)類

(30)C0=C′中離C最近的等價(jià)類

(31)將C與C0合并

(32)end while

(33)foreachECinC′:

(34)用QI屬性在EC中的取值范圍來概化該屬性值

(35)returnC′

第3個(gè)過程是一個(gè)歸并過程，判斷第2個(gè)過程中產(chǎn)生的等價(jià)類簇與原始數(shù)據(jù)集在敏感屬性上的分布是否滿足t-closeness。如果不滿足，則在等價(jià)類簇中尋找與原始數(shù)據(jù)集敏感屬性分布距離最大的等價(jià)類，并將其與距其質(zhì)心最近的等價(jià)類合并，循環(huán)迭代類簇中的所有等價(jià)類，直到所有等價(jià)類均滿足t-closeness，如算法1中行(28)-行(32)所示。第4個(gè)過程是概化，對于第3個(gè)過程產(chǎn)生的等價(jià)類簇中的每個(gè)等價(jià)類，用屬性在該等價(jià)類中的取值范圍來概化具體的屬性值，最終生成一個(gè)符合k匿名t-closeness的匿名化數(shù)據(jù)集，如算法1中行(33)-行(34)所示。

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

使用人口普查數(shù)據(jù)集Census作為評估數(shù)據(jù)，該數(shù)據(jù)集通常用于測試隱私保護(hù)方法，其中包含1 080條具有數(shù)字屬性的記錄，共有13個(gè)屬性。將TAXINC和POTHVAL設(shè)為為準(zhǔn)標(biāo)識(shí)符屬性，并將FEDTAX和FICA設(shè)為敏感屬性，屬性的描述如表3所示。算法的運(yùn)行環(huán)境為jdk1.8.0_212，Intel Core i5 2.6GHz，8GB RAM Win10操作系統(tǒng)。

表3 實(shí)驗(yàn)中采用的屬性

3.1 等價(jià)類大小

對k和t取不同的值，從而獲得了一系列的實(shí)驗(yàn)結(jié)果。k的值在5到30之間，t的取值范圍為[0.05,0.30]。為了使信息丟失最小化，所有等價(jià)類的大小越接近k越好。考慮到k-means++聚類算法初始簇心的隨機(jī)性對聚類結(jié)果的影響，每組取值重復(fù)實(shí)驗(yàn)50次，取最好結(jié)果。等價(jià)類的大小隨著k值的增加而變大如表4所示，對于同一個(gè)k值，t值越小，即隱私保護(hù)水平越高，等價(jià)類的平均尺寸就越大，因而信息損失就越大。

表4 k和t取不同值時(shí)等價(jià)類的最小尺寸、平均尺寸

3.2 運(yùn)行時(shí)間

評估的第2部分著重于測量算法在數(shù)據(jù)集上的測試時(shí)間。k、t取不同值時(shí)算法的執(zhí)行時(shí)間如圖1所示，t越大，即隱私保護(hù)程度越低，算法的運(yùn)行時(shí)間越小，對于Census數(shù)據(jù)集，算法的執(zhí)行時(shí)間在t= 0.15前后相差較大，并且在t=0.15之前，執(zhí)行時(shí)間受t的影響較大，t=0.15之后，執(zhí)行時(shí)間趨于平緩；另一方面，k越小，執(zhí)行時(shí)間越長，這是因?yàn)閗越小，每個(gè)等價(jià)類中包含的記錄條數(shù)就越少，生成滿足t-closeness的等價(jià)類需要迭代計(jì)算EMD的次數(shù)越多，因而執(zhí)行時(shí)間越長。

圖1 k、t取不同值時(shí)算法運(yùn)行時(shí)間

3.3 信息損失

評估的第3部分著重于匿名化前后信息的損失，采用上文提到的兩種度量方法，圖2表示的是k、t取不同值時(shí)的概化損失(IL),圖3表示的是k、t取不同值時(shí)的平方誤差總和(SSE)。t越小，信息損失越大，即隱私保護(hù)程度越高；另一方面，在同等隱私保護(hù)程度下，等價(jià)類的大小越大，即k越大，誤差越大，這是因?yàn)閗越大，等價(jià)類中包含的記錄條數(shù)越多，準(zhǔn)標(biāo)識(shí)屬性的概化范圍變大，從而導(dǎo)致誤差變大。這也是基于準(zhǔn)標(biāo)識(shí)屬性聚類和基于敏感屬性聚類的一個(gè)區(qū)別。

圖2 k、t取不同值時(shí)的信息損失IL 圖3 k、t取不同值時(shí)的平方誤差和SSE

4 結(jié) 語

針對大多數(shù)有關(guān)t-closeness研究未考慮到多敏感屬性的問題，提出了一種基于k-means++聚類的多敏感屬性t-closeness算法，使用k-means++聚類算法基于多敏感屬性對原始數(shù)據(jù)集進(jìn)行分組，然后從每個(gè)分組中選取一條或多條記錄組成等價(jià)類，并計(jì)算其接近度，如果不滿足t-closeness,則迭代地從剩余的未分組的記錄中選取記錄更新等價(jià)類，直至其滿足t-closeness或接近度最小。實(shí)驗(yàn)表明本方法具有良好的效果。然而，本文算法仍有不完美的地方，為使得所有的等價(jià)類盡量滿足t-closeness,在生成等價(jià)類的過程中不斷計(jì)算EMD，計(jì)算復(fù)雜性高；另一方面，在計(jì)算EMD時(shí)，單獨(dú)考慮每個(gè)敏感屬性的分布，而沒有考慮到多敏感屬性的聯(lián)合分布，并且沒有考慮到多個(gè)敏感屬性之間的關(guān)系。這些問題將在未來的工作中進(jìn)一步研究。