基于OLA的K匿名算法的改進

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

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

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

1 K-匿名

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

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

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

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

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

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

K-匿名準確描述：給定數據表 T[A1，A2，…，An]，QI是與T相關聯的準標識符，當且僅當在T[QI]中出現的每個值序列至少在 T[QI]中出現 K次，則 T滿足 K-匿名。T[QI]表示T表元組在QI上的投影。

圖1 年齡的泛化層次

2 最優格匿名算法OLA

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

2.1 泛化格（Lattice）的建立

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

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

圖2 地區的泛化層次

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

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

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

圖3 年齡和地區建立的泛化格

2.2 泛化格的遍歷

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

具體遍歷方式如下：

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

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

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

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

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

3 算法的改進

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

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

(2)最優節點選擇算法：

①首先計算Lattice中所有節點的度積。

②從Lattice中找到度積最大的節點。

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

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

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

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

圖4 改進OLA算法流程圖

4 實驗采用的數據及結果

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

表1 實驗使用的數據集

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

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

本文介紹了隱私保護中K-匿名的相關概念，簡單敘述了K-匿名的一種較好的算法OLA，并針對OLA在遍歷Lattice格計算節點過多這一問題進行改進，提出了度積優先的遍歷算法。通過OLA和度優先算法對相同數據的實驗，可以看出度積優先的算法相對OLA有明顯提高。取得最優結果后，按照該結果的泛化方式處理數據，可以得到最終發布的數據。

[1]SWEENEY L.K-anonymity：a model for protecting privacy[J].International Journal on Uncertainty，Fuzziness 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，Fuzziness 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.