基于OLA的K匿名算法的改進(jìn)

胡翔天，宮秀軍，陳海亮(天津大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津300072)

隨著網(wǎng)絡(luò)信息技術(shù)的發(fā)展，信息資源的共享大大提高了信息資源的利用價(jià)值。大量信息的共享在給統(tǒng)計(jì)研究帶來(lái)方便的同時(shí)也對(duì)個(gè)人隱私帶來(lái)了威脅。因此，在發(fā)布數(shù)據(jù)時(shí)要盡量保護(hù)數(shù)據(jù)中的隱私。

數(shù)據(jù)匿名化是發(fā)布數(shù)據(jù)時(shí)保護(hù)個(gè)人隱私的一種有效手段。數(shù)據(jù)匿名化常用的處理手段源于統(tǒng)計(jì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)處理方法，主要是通過(guò)以發(fā)布數(shù)據(jù)中的屬性值的信息損失為代價(jià)，換取通過(guò)這些屬性值再標(biāo)識(shí)某些個(gè)體的準(zhǔn)確性，同時(shí)盡可能保證發(fā)布數(shù)據(jù)的可用性，在發(fā)布數(shù)據(jù)的準(zhǔn)確性和隱私保護(hù)之間達(dá)到一種平衡，與傳統(tǒng)的保證發(fā)布數(shù)據(jù)整體趨勢(shì)而犧牲單個(gè)數(shù)據(jù)記錄準(zhǔn)確性的隱私保護(hù)方法相比，為發(fā)布數(shù)據(jù)提供了更好的可用性。通常做法是數(shù)據(jù)收集者通過(guò)隱藏或改變數(shù)據(jù)中的部分信息，使得攻擊者無(wú)法通過(guò)發(fā)布出去的數(shù)據(jù)唯一地推導(dǎo)出敏感信息所屬的個(gè)體，從而實(shí)現(xiàn)對(duì)個(gè)體隱私的保護(hù)。K-匿名算法是一種重要的數(shù)據(jù)匿名化方法。K-匿名算法中的一種比較高效的算法叫做最優(yōu)格匿名算法OLA（Optimal Lattice Anomy-zation)，此算法使用一種叫做格（Lattice)的結(jié)構(gòu)，通過(guò)遍歷該結(jié)構(gòu)中的節(jié)點(diǎn)從而最后得到最優(yōu)的節(jié)點(diǎn)。然而OLA遍歷節(jié)點(diǎn)的順序并不能夠最大程度上減少需要計(jì)算的Lattice的個(gè)數(shù)。本文在OLA算法的基礎(chǔ)上提出了一種度優(yōu)先的節(jié)點(diǎn)遍歷方式，即通過(guò)節(jié)點(diǎn)的度積大小來(lái)遍歷節(jié)點(diǎn)，從而顯著減少最優(yōu)結(jié)果的計(jì)算時(shí)間。

1 K-匿名

K-匿名是一個(gè)典型的微數(shù)據(jù)發(fā)布模型。微數(shù)據(jù)定義為一條表達(dá)和描述個(gè)體信息的數(shù)據(jù)記錄，為個(gè)體信息的載體。這些信息包括個(gè)體的標(biāo)識(shí)信息（如姓名、身份證號(hào)等）、敏感信息（如病史等）以及一些非敏感信息（如性別）。每個(gè)信息都是以個(gè)體屬性和相應(yīng)的屬性值匹配的方式作為微數(shù)據(jù)（記錄）的某個(gè)分量[1]。K-匿名就是通過(guò)匿名化原始數(shù)據(jù)中的某些屬性值以導(dǎo)出滿足一定匿名要求的匿名數(shù)據(jù)集并用于發(fā)布，為保證數(shù)據(jù)的有效性，這些被泛化的屬性一般是非敏感屬性，對(duì)于敏感屬性一般不進(jìn)行匿名化，因?yàn)榘l(fā)布數(shù)據(jù)中的敏感屬性通常是所研究的主要內(nèi)容，如醫(yī)院患者就診記錄中的疾病信息，泛化該屬性將導(dǎo)致發(fā)布數(shù)據(jù)失去意義。同時(shí)K-匿名保證敏感屬性值不對(duì)應(yīng)到具體的個(gè)體。通常K-匿名要求對(duì)應(yīng)于任意一條投影到這些屬性上的值行，該k條記錄組成一個(gè)等價(jià)組，從而使個(gè)體隱藏在k條數(shù)據(jù)之中，而無(wú)法確定k條數(shù)據(jù)中具體哪一條記錄是該個(gè)體對(duì)應(yīng)的記錄，從而達(dá)到對(duì)自由訪問(wèn)數(shù)據(jù)型數(shù)據(jù)隱私保護(hù)的目的。對(duì)于敏感屬性這些對(duì)統(tǒng)計(jì)數(shù)據(jù)庫(kù)統(tǒng)計(jì)結(jié)果相對(duì)重要的屬性則保證數(shù)據(jù)的精確性，以屬性值的部分損失換取隱私屬性值的被保護(hù)。

為準(zhǔn)確描述K-匿名的概念，一般將發(fā)布數(shù)據(jù)表中的個(gè)體記錄的屬性分為標(biāo)識(shí)符、準(zhǔn)標(biāo)識(shí)符、敏感屬性三類。

標(biāo)識(shí)符：標(biāo)識(shí)符屬性是指能夠直接標(biāo)識(shí)出個(gè)體身份的屬性，如姓名、身份證號(hào)碼、社會(huì)保險(xiǎn)號(hào)碼等，通過(guò)這些屬性值能夠直接確定具體的個(gè)體。

準(zhǔn)標(biāo)識(shí)符QI(Quasi-Indentifiers)：也叫做類標(biāo)識(shí)符屬性，同時(shí)存在于發(fā)布數(shù)據(jù)表和外部數(shù)據(jù)源表中，利用此兩種數(shù)據(jù)表進(jìn)行連接的推演來(lái)表示個(gè)人隱私信息的一組屬性[2]。不同的發(fā)布數(shù)據(jù)表可以根據(jù)不同的情況劃分為不同的準(zhǔn)標(biāo)識(shí)符屬性，通常準(zhǔn)標(biāo)識(shí)符由專家選擇，而非用戶隨便選取。一般情況下可以以年齡、教育程度、性別、地區(qū)等作為準(zhǔn)標(biāo)識(shí)符。

敏感屬性SA(Sensitive-Attributes)：個(gè)人隱私屬性。發(fā)布數(shù)據(jù)中，個(gè)體不希望其他用戶知道的信息屬性。例如個(gè)人的工資水平、患者就診記錄中的所患疾病。

等價(jià)組：在準(zhǔn)標(biāo)識(shí)符上的投影完全相同的記錄組成的組。等價(jià)組中所有的記錄在準(zhǔn)標(biāo)識(shí)符上的屬性值完全相同，其他的屬性值可以不同。

K-匿名準(zhǔn)確描述：給定數(shù)據(jù)表 T[A1，A2，…，An]，QI是與T相關(guān)聯(lián)的準(zhǔn)標(biāo)識(shí)符，當(dāng)且僅當(dāng)在T[QI]中出現(xiàn)的每個(gè)值序列至少在 T[QI]中出現(xiàn) K次，則 T滿足 K-匿名。T[QI]表示T表元組在QI上的投影。

圖1 年齡的泛化層次

2 最優(yōu)格匿名算法OLA

OLA算法是一種全局最優(yōu)的K-匿名算法[3]，它是在Incognito[4]和Datafly[5]的基礎(chǔ)上進(jìn)行改進(jìn)而得到的一種方法。OLA算法的主要步驟如下：

2.1 泛化格（Lattice）的建立

選取準(zhǔn)標(biāo)識(shí)符，并按照一定的標(biāo)準(zhǔn)進(jìn)行泛化，可以得到各個(gè)屬性的泛化層次，如圖1所示為選取年齡為準(zhǔn)標(biāo)識(shí)符，根據(jù)年齡建立的泛化層次，圖2為根據(jù)所屬地區(qū)建立的泛化層次。

根據(jù)各個(gè)屬性相應(yīng)的泛化方式可以建立泛化格。令Ti(A1，…，Ak)和 Tj(A1，…，Ak)是兩個(gè)不同的表（即兩者為L(zhǎng)attice中不同的節(jié)點(diǎn)，(A1，…，Ak)為數(shù)據(jù)的 k個(gè)屬性，Ai為第i個(gè)屬性的泛化等級(jí)或泛化高度）。這兩個(gè)表為對(duì)同一數(shù)據(jù)的各個(gè)屬性進(jìn)行不同程度泛化的結(jié)果，它們構(gòu)成泛化格中的兩個(gè)節(jié)點(diǎn)，每個(gè)表都是對(duì)數(shù)據(jù)的一種泛化策略。

圖2 地區(qū)的泛化層次

泛化向量：L(ai，…，ak)，其中 ai表示節(jié)點(diǎn)每個(gè)屬性的泛化等級(jí)（或者泛化高度）。

距離矢量：DVij=[d1，…，dk]，計(jì)算公式為：di=(Tjk-Tik)，其中，di為泛化等級(jí)中屬性間路徑長(zhǎng)度。

兩個(gè)或多個(gè)屬性進(jìn)行不同等級(jí)的泛化得到的結(jié)果構(gòu)成屬性泛化序列，這些序列構(gòu)成基于準(zhǔn)標(biāo)識(shí)符的泛化等級(jí)序列，稱為泛化格。圖3為根據(jù)年齡和地區(qū)建立的一種泛化格。(i，j)中i表示年齡的泛化層次，j表示地區(qū)的泛化層次。

圖3 年齡和地區(qū)建立的泛化格

2.2 泛化格的遍歷

建立完成泛化格后，需要對(duì)泛化格進(jìn)行遍歷以找出最優(yōu)的泛化方式，OLA在遍歷時(shí)使用了Datafly的性質(zhì)：(1)在一個(gè)泛化格中，若某一個(gè)節(jié)點(diǎn)v滿足K-匿名，則比v高的節(jié)點(diǎn)也滿足K-匿名；(2)若某個(gè)節(jié)點(diǎn)v不滿足K-匿名，則比v低的節(jié)點(diǎn)均不滿足K-匿名。通過(guò)這個(gè)性質(zhì)遍歷泛化格，可以對(duì)已遍歷的節(jié)點(diǎn)進(jìn)行標(biāo)記，同時(shí)可以推測(cè)與之相關(guān)的節(jié)點(diǎn)是否滿足K-匿名，加快尋求K-匿名節(jié)點(diǎn)的速度。

具體遍歷方式如下：

(1)對(duì)于建立的泛化格，使用二分順序遍歷法，找到所有滿足K-匿名的節(jié)點(diǎn)。二分順序遍歷法是首先取泛化等級(jí)的最高值Lmax和最低值Lmin， 令Lmid=(Lmax+Lmin)/2，對(duì)于泛化等級(jí)為L(zhǎng)mid的節(jié)點(diǎn)依次判斷是否滿足K-匿名，若滿足，則將該節(jié)點(diǎn)的祖先節(jié)點(diǎn)標(biāo)記為K匿名；如不滿足，將該節(jié)點(diǎn)的子孫節(jié)點(diǎn)標(biāo)記為不滿足K匿名。然后以該節(jié)點(diǎn)為最低節(jié)點(diǎn)，遞歸地使用二分順序遍歷的方法，直到標(biāo)記完所有節(jié)點(diǎn)。

(2)對(duì)于找到的滿足K-匿名的節(jié)點(diǎn)，根據(jù)單調(diào)性只保留高度最低的距離向量。例如：對(duì)于兩個(gè)節(jié)點(diǎn)(2，3)、(2，2)都滿足 K-匿名，因?yàn)楣?jié)點(diǎn)（2，2）在節(jié)點(diǎn)（2，3）的下面，所以只保留節(jié)點(diǎn)（2，2）。

(3)如此得到一個(gè)最小的滿足K-匿名的節(jié)點(diǎn)的集合k-minimal，計(jì)算該集合中每個(gè)節(jié)點(diǎn)的信息損失量。在各種文獻(xiàn)中，有許多衡量信息損失的定義，Domingo-Ferrer[6]提到可以通過(guò)比較源數(shù)據(jù)和處理后數(shù)據(jù)的相似度來(lái)得到信息損失，參考文獻(xiàn)[7]也給了類似的定義。本文采用的信息損失量的計(jì)算方式如下：

其中，N表示元組集中的屬性個(gè)數(shù)，DGHi表示第i個(gè)屬性的最高泛化等級(jí)，hi表示屬性i的當(dāng)前泛化等級(jí)。由式(1)可知泛化程度越高，信息損失量越大；泛化程度越低，信息損失量越小。將信息損失量最小的節(jié)點(diǎn)作為最后的結(jié)果，這個(gè)結(jié)果即最優(yōu)結(jié)果。

OLA算法中最消耗時(shí)間的兩個(gè)步驟是：判斷一個(gè)節(jié)點(diǎn)是否為K-匿名節(jié)點(diǎn)和比較k-minimal中所有節(jié)點(diǎn)的信息損失量。因此本文以盡量減少需要進(jìn)行K-匿名判斷的節(jié)點(diǎn)的數(shù)量作為切入點(diǎn)對(duì)其進(jìn)行改進(jìn)。

3 算法的改進(jìn)

OLA采取的二分遍歷法，將會(huì)遍歷較多的節(jié)點(diǎn)，為此本文采取一種度優(yōu)先的方法對(duì)泛化格中的節(jié)點(diǎn)進(jìn)行遍歷。把Lattice中一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)數(shù)和子節(jié)點(diǎn)數(shù)分別叫做該節(jié)點(diǎn)的出度和入度，定義一個(gè)節(jié)點(diǎn)的度積為該節(jié)點(diǎn)出度和入度的乘積。改進(jìn)后的算法的簡(jiǎn)要步驟如下：

(1)數(shù)據(jù)預(yù)處理：建立泛化格（Lattice）的步驟與 OLA建立泛化格的情況相同。

(2)最優(yōu)節(jié)點(diǎn)選擇算法：

①首先計(jì)算Lattice中所有節(jié)點(diǎn)的度積。

②從Lattice中找到度積最大的節(jié)點(diǎn)。

(a)判斷該節(jié)點(diǎn)是否滿足K-匿名。如果該節(jié)點(diǎn)滿足K-匿名，可知該節(jié)點(diǎn)的所有父節(jié)點(diǎn)都為K-匿名節(jié)點(diǎn)。從Lattice中刪除該節(jié)點(diǎn)及其所有祖先節(jié)點(diǎn)；然后查找已保存的k-minimal的集合，看該集合中是否有該節(jié)點(diǎn)的祖先，若有，則從k-minimal集合中將其刪除；若無(wú)，則不操作。最后把該節(jié)點(diǎn)保存到k-minimal中。

(b)如果該節(jié)點(diǎn)不滿足K-匿名，則可知該節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)都不是K-匿名節(jié)點(diǎn)。從Lattice中刪除該節(jié)點(diǎn)及其所有的子孫節(jié)點(diǎn)。

(c)比較所有保存在k-minimal集合中節(jié)點(diǎn)的信息損失量。信息損失量最小的那個(gè)節(jié)點(diǎn)，即為所查找的全局最優(yōu)節(jié)點(diǎn)。

該算法的流程圖如圖4所示。

圖4 改進(jìn)OLA算法流程圖

4 實(shí)驗(yàn)采用的數(shù)據(jù)及結(jié)果

實(shí)驗(yàn)使用的數(shù)據(jù)如表1所示。這個(gè)數(shù)據(jù)集為公共數(shù)據(jù)集，該數(shù)據(jù)來(lái)自UC Irvine機(jī)器學(xué)習(xí)儲(chǔ)藏室，是美國(guó)人口普查中抽出的數(shù)據(jù)，該數(shù)據(jù)集已經(jīng)被很多類似的研究使用過(guò)[5，8]。實(shí)驗(yàn)時(shí)，從數(shù)據(jù)集中將標(biāo)識(shí)符（姓名、身份證號(hào)等）屬性和隱私屬性去掉，留下準(zhǔn)標(biāo)識(shí)符，對(duì)準(zhǔn)標(biāo)識(shí)符根據(jù)其語(yǔ)義建立泛化層次。數(shù)據(jù)集的準(zhǔn)標(biāo)識(shí)符的選取以及泛化高度如表1中第二列所示。第三列是數(shù)據(jù)的條數(shù)，第四列是建立的Lattice的節(jié)點(diǎn)的數(shù)目。

表1 實(shí)驗(yàn)使用的數(shù)據(jù)集

將OLA和度優(yōu)先均用于這個(gè)數(shù)據(jù)集，然后將運(yùn)行的結(jié)果加以比較。圖5、圖6為實(shí)驗(yàn)結(jié)果。

從兩個(gè)方面評(píng)定算法的執(zhí)行效率，一方面通過(guò)讀取源數(shù)據(jù)判斷節(jié)點(diǎn)的數(shù)量，另一方面是算法的運(yùn)行時(shí)間。圖5為兩種算法需要計(jì)算的節(jié)點(diǎn)數(shù)量的比較，最下面的折線為最小K-匿名節(jié)點(diǎn)的數(shù)量。從中可以看出度優(yōu)先需要計(jì)算節(jié)點(diǎn)數(shù)比OLA要少。圖6為兩個(gè)算法計(jì)算完成時(shí)間的對(duì)比，明顯可以看出度優(yōu)先運(yùn)行的時(shí)間比OLA要少，可見(jiàn)度優(yōu)先計(jì)算K-匿名的算法比OLA要好。

本文介紹了隱私保護(hù)中K-匿名的相關(guān)概念，簡(jiǎn)單敘述了K-匿名的一種較好的算法OLA，并針對(duì)OLA在遍歷Lattice格計(jì)算節(jié)點(diǎn)過(guò)多這一問(wèn)題進(jìn)行改進(jìn)，提出了度積優(yōu)先的遍歷算法。通過(guò)OLA和度優(yōu)先算法對(duì)相同數(shù)據(jù)的實(shí)驗(yàn)，可以看出度積優(yōu)先的算法相對(duì)OLA有明顯提高。取得最優(yōu)結(jié)果后，按照該結(jié)果的泛化方式處理數(shù)據(jù)，可以得到最終發(fā)布的數(shù)據(jù)。

[1]SWEENEY L.K-anonymity：a model for protecting privacy[J].International Journal on Uncertainty，F(xiàn)uzziness and Knowledge-based Systems，2002，10(5)：557-570.

[2]DALENIUS T.Finding a needle in a haystack-or identifying anonymouscensus record[J].Journal of Official Statistics，1986，2(3)：329-336.

[3]EMAM K，DANKAR F，ISSA R J，et al.A globally optimal K-anonymity method for the de-identification of health data[J].J Am Med Inform Assoc，2009，16(5)：670-82.

[4]SWEENEY L.Achieving K-anonymity privacy protection using generalization and suppression[J].International Journal on Uncertainty，F(xiàn)uzziness and Knowledge based Systems，2002，10(5)：18.

[5]LEFEVRE K，DEWITT D J，RAMAKRISHNAN R.Incognito：EfficientFull domain K-anonymity Proc[C].ACM Management of Data，Baltimore，USA：ACM，2005：49-60.

[6]DOMINGO-FERRER J，TORRA V.Risk assessment in statistical microdata protec-tion via advanced record linkage[J].Journal of Statistics and Computing，2003，13(4).

[7]XU J，WANG W，PEI J，et al.Utility-based anonymization using local recoding[C].12th ACM SIGKDD international conference on knowledge discovery and data mining，Philadelphia，USA：ACM，2006：785-790.

[8]BAYARDO B，AGRAWAL R.Data privacy through optimal K-anonymity[C].In Proc.of the 21st Int′l Conference on Data Engineering.IEEE CS，2005：217-228.