胡翔天，宮秀軍，陳海亮(天津大學 計算機科學與技術學院，天津300072)

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

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

1 K-匿名

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

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

標識符：標識符屬性是指能夠直接標識出個體身份的屬性，如姓名、身份證號碼、社會保險號碼等，通過這些屬性值能夠直接確定具體的個體。

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

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

等價組：在準標識符上的投影完全相同的記錄組成的組。等價組中所有的記錄在準標識符上的屬性值完全相同，其他的屬性值可以不同。

K-匿名準確描述：給定數(shù)據(jù)表 T[A1，A2，…，An]，QI是與T相關聯(lián)的準標識符，當且僅當在T[QI]中出現(xiàn)的每個值序列至少在 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]的基礎上進行改進而得到的一種方法。OLA算法的主要步驟如下：

2.1 泛化格（Lattice）的建立

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

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

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

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

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

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

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

2.2 泛化格的遍歷

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

具體遍歷方式如下：

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

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

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

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

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

3 算法的改進

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

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

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

①首先計算Lattice中所有節(jié)點的度積。

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

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

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

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

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

圖4 改進OLA算法流程圖

4 實驗采用的數(shù)據(jù)及結果

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

表1 實驗使用的數(shù)據(jù)集

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

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

本文介紹了隱私保護中K-匿名的相關概念，簡單敘述了K-匿名的一種較好的算法OLA，并針對OLA在遍歷Lattice格計算節(jié)點過多這一問題進行改進，提出了度積優(yōu)先的遍歷算法。通過OLA和度優(yōu)先算法對相同數(shù)據(jù)的實驗，可以看出度積優(yōu)先的算法相對OLA有明顯提高。取得最優(yōu)結果后，按照該結果的泛化方式處理數(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.