基于k-means++的多敏感屬性t-closeness隱私保護

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

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

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

1 基本概念

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

1.1 k匿名

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

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

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

1.2 t-closeness

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

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

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

(1)

表1 某醫(yī)療機構(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的標識符屬性集。對于數(shù)值屬性，設(shè)QIi在D中的域為[L,H],a為QIi中的一個屬性值，a概化后的值范圍為[La,Ha],則屬性值a信息損失被定義為

(2)

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

(3)

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

(4)

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

(5)

式中：N為D中記錄的條數(shù)；n為準標識符屬性的個數(shù)。

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

2.1 多敏感屬性t-closeness

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

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

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

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

(6)

(7)

第2個過程是一個生成等價類的過程，根據(jù)第1個過程產(chǎn)生的基于多敏感屬性的k個分組, 循環(huán)地從每個分組中抽取一條記錄組成大小為k的等價類，然后判斷該等價類是否滿足t-closeness，如果不滿足，則從剩余的記錄中選取一條距離等價類最近的記錄替換掉等價類中的某條記錄以使得等價類最接近t-closeness，重復(fù)上述步驟，直到所有等價類均被選出來，如算法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進行k-means++聚類，得到k個分組C={C1,C2,…,Ck}

(2)初始化C′ = ?；

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

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

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

(6)while |EC|

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

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

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

(31)將C與C0合并

(32)end while

(33)foreachECinC′:

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

(35)returnC′

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

3 實驗評估

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

表3 實驗中采用的屬性

3.1 等價類大小

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

表4 k和t取不同值時等價類的最小尺寸、平均尺寸

3.2 運行時間

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

圖1 k、t取不同值時算法運行時間

3.3 信息損失

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

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

4 結(jié) 語

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