個性化(p，α，k)-匿名隱私保護算法

蒲 東 方 睿

(成都信息工程大學 四川 成都 610225)

0 引 言

我們在享受信息技術發展給我們帶來便捷的同時，也暴露了大量與個體相關的數據， 而這些數據被政府、商業機構等存儲、發布[1]。這些數據往往隱含大量的個人信息，因此，很容易造成個人隱私信息泄露[2-3]。例如， 公開的醫療記錄，可能對某位病人的隱私構成威脅。因此，如何高效地保護個人隱私數據不被泄露， 同時減少數據的損失成為了當下研究的熱點問題之一。

目前，保護個人隱私信息主要有三種技術方式[4]：數據加密技術、數據失真技術和數據匿名化技術。其中數據加密技術利用加密函數將原數據轉換為加密數據，提高了數據安全性，但是也極大地破壞了數據的可用性；數據失真技術是通過添加噪聲的方式給數據并保持數據特性，該方法雖然保持了數據的原有的特性，但是不能保證數據安全性，還降低了可用信息數據的占比；數據匿名化技術采用不同匿名策略對數據進行壓縮或者抽象，并保證隱私不被泄露的同時，又使得數據可用性最大化。因此，通常采用數據匿名化的技術實現個人隱私保護[5]。

1998年Samarati等首次提出了匿名化的概念，國內外專家對其展開了廣泛深入的研究，找到防止或者減少隱私泄露同時使最大化數據可用性的方法。2002年Sweeney等匿名化概念首次提出了一種匿名的k-匿名模型[6]，對發布數據劃分成多個等價類且使每個等價類中至少有k個元組在準標識符屬性上相同，使攻擊者不能判別隱私信息所屬的個體。雖然k-匿名模型方法能有效減少準標識符屬性泄露風險，但是沒有保護機制減少敏感屬性泄露的風險，不能達到有效的保護隱私的目的[7-8]。2007年,針對敏感屬性泄露問題Machanavajjhala等[9]在k-匿名的基礎上提出了l多樣性-匿名模型，要求等價類中敏感屬性的敏感屬性值至少有l個“良性”值；Li等[10]提出了t-接近模型，要求等價類中敏感屬性值的分布和原數據表的分布間距不大于閾值t。之后文獻[11]基于k匿名模型提出了(α，k)-匿名模型，在滿足看匿名模型的前提，同時要求敏感屬性值出現頻率小于等于α。文獻[12]在防止同質攻擊思想提出了p-sensitive k-匿名模型，對等價類中每個敏感屬性值出現的種類數進行限制：每個等價類中每個敏感屬性值至少出現p個不同敏感屬性值。這些模型提供了表級別的保護粒度，都能在一定程度上防止或者減少隱私泄露風險，但是沒有考慮個人需求，造成了一些不必要的信息損失。

在日常生活中，對于不同的個體敏感度，相同的敏感屬性敏感度也不一定不相同，因此，在進行個性化隱私保護就必須依據個體差異下對敏感屬性值的敏感度進行個性化保護[13]。文獻[14]采用個人隱私自治原則，局部敏感屬性編碼思想對敏感屬性進行個性化泛化提出了個性化k-匿名算法。文獻[15]基于l多樣性-匿名模型提出了個性化(α,l)-多樣性匿名模型，要求匿名后的數據滿足l多樣性-匿名模型的同時，多樣性表的敏感屬性值的頻率不大于α。文獻[16]提出了基于(α，k)-匿名模型建立了個性化(α，k)-匿名隱私保護模型，通過對準標識符屬性進行k匿名隱私保護方法劃分等價類，且將敏感屬性值敏感度劃分成不同的敏感組，然后對不同級別敏感度的敏感組設置不同的閾值α，從而達到個性化隱私保護的目的。文獻[17]在對多敏感屬性進行保護的情形下，提出了對多敏感值進行保護的個性化隱私保護算法。文獻[18]提出了用聚類的方式實現個性化的一種基于變長聚類的個性化匿名保護方法。文獻[5]基于p-sensitive k匿名模型建立了個性化(p，k)-匿名模型，通過對敏感屬性的敏感度進行分級劃分成不同等級的敏感屬性值，然后對不同等級的敏感屬性值泛化為不同層次的低精度的敏感屬性泛化值，達到對敏感屬性值個性化匿名隱私保護的目的。由此可見，個性化保護越來越受到關注和重視。

本文基于個性化(p，k)-匿名模型和個性化(α，k)-匿名模型，提出針對匿名后的數據損失度較大，和存在同質攻擊的泄露隱私風險的改進的個性化隱私保護算法。根據個體間敏感程度的差異將敏感屬性值進行劃分成高、中、低不同的敏感級別。根據敏感屬性的不同等級采用不同的匿名保護的方法：通過建立敏感屬性泛化樹，將高敏感度的屬性值進行降級泛化，達到降低高敏感屬性泄露的風險，然后針對中敏感屬性和低敏感屬性通過閾值α限制等價類中每個敏感屬性值的出現的頻率。以此降低匿名后數據的損失和隱私泄露風險，使數據可用性的最大化。

1 匿名模型

數據集中的屬性根據功能可以劃分為三種類別[1]，第一類是標識符屬性I，可以根據其屬性的值唯一確定標識某一個個體的屬性，例如居民身份證號屬性、姓名屬性等。因此，如果要進行數據發布時，就必須用某種隱藏方式保證其隱私，通常我們都會采用直接刪除其屬性的方式；第二類是可以通過鏈接其他數據表識別個體的屬性或屬性集合的準標識符屬性QI，例如性別屬性、郵編屬性、年齡屬性等；最后一類是可以帶表個體隱私的屬性我們稱為敏感屬性S，例如健康狀況屬性、收入情況屬性等，不同的個體對隱私定義也不一樣，因此，敏感屬性的選擇可能也不同。

例如，表1所示為病歷的原數據表，表中屬性Name的屬性值是可以唯一標識個體，因此，NAME為標識符屬性，發布數據時應該刪除其屬性避免隱私泄露；Sex、Age、Zipcode是準標識符屬性，對表操作時應該匿名化操作；Disease是敏感屬性。

表1 原始數據表

定義1(k匿名[19])假設數據表T{A1,A2,…,An}，QI是T中可以通過鏈接的其他數據表識別個體的準標識符屬性，T在QI上的投影為T[QI]，如果每組值在QI投影T[QI]至少重復出現k次，則稱T滿足k匿名。

定義2(等價類[19])假設數據表T{A1,A2,…,An}，數據表子集取元組中準標識符屬性值相同的集合，則稱該集合為一個等價類。

因此，如果數據表滿足k匿名，則任意一個等價類中準標識符屬性上相等的元組數至少為k。

表2為2-匿名數據表，將表1中的標識符隱藏，將準標識符屬性通過泛化操作輸出精度較低的值。

表2 2-匿名數據表

定義3((α，k)-匿名模型[16])數據表T{A1,A2,…,An}，匿名后數據表T′，如果T′滿足k匿名，每個等價類元組數至少為k，在準標識符屬性上取值一致，且在敏感屬性的取值相同取值重復出現的頻率不大于α，則稱匿名后的數據表T′滿足(α，k)-匿名模型。

表3為(0.5，2)-匿名數據表，將表1中的標識符隱藏，將準標識符屬性通過泛化操作輸出精度較低的值。敏感屬性使其滿足每個等價類中同一敏感屬性的頻率大于0.5。

表3 (0.5，2)-匿名數據表

定義4((p，k)-匿名模型[5])數據表T{A1,A2,…,An}，匿名后數據表T′，如果T′滿足k匿名，每個等價類元組數至少為k，在準標識符屬性上取值一致，且在敏感屬性上不同取值個數不小于p，則稱匿名后的數據表T′滿足(p，k)-匿名模型。

表4為(2，2)-匿名數據表，將表1中的標識符隱藏，將準標識符屬性通過泛化操作輸出精度較低的值，將敏感屬性泛化，并使其滿足每個等價類中不同敏感屬性值至少有2個。

表4 (2，2)-匿名數據表

2 個性化(p，α，k)-匿名隱私保護模型

由于k匿名模型對除了標識符屬性的取值進行了匿名化，雖然可以有效地防止攻擊者通過鏈接攻擊的方式泄露隱私，但存在等價類中敏感屬性取值一致的情況，攻擊者可以通過同質攻擊的方式竊取個人隱私，造成隱私泄露，因此要對敏感屬性進行保護防止泄露隱私問題。由于不同的個體的敏感屬性不同且不同的敏感個體敏感度的不同，因此需要對敏感屬性進行個性化隱私保護[13]。個性化(α，k)-匿名模型是基于(α，k)-匿名模型，對不同等級的敏感屬性設置不同的閾值α，雖然考慮了根據敏感度進行分級保護，但是存在高敏感屬性泄露的風險，例如對表1進行個性化(0.5，2)-匿名，發布的數據依然存在高敏感屬性值HIV，存在背景知識攻擊泄露的風險。個性化(p，k)-匿名模型基于(p，k)-匿名模型，根據不同等級的敏感屬性采用不同的泛化策略：將高敏感度的屬性值泛化到對應樹的根節點的值；將中敏感度的屬性值泛化到對應的父節點的值。其次，采用值的限定方法，使得泛化后的等價類中至少存在p個不同的屬性值。這種策略雖然提供了一種對不同敏感度的敏感屬性值的個性化隱私保護方法，但是也造成了巨大的數據損失，且如果數據分布相似度很高，則會有很大幾率泄露隱私。例如原始表中的敏感屬性取值HIV，經過個性化(p，k)-匿名后屬性取值為疾病，假設HIV泛化后取值為內科疾病，保護了個人隱私。因此在對敏感屬性的個性化保護的同時保證數據的可用性也同樣重要，本文主要使針對高敏感屬性值進行泛化，然后針對中敏感屬性和低敏感屬性通過閾值α限制等價類中每個敏感屬性值的出現的頻率，使泛化后等價類中敏感屬性值分布均勻，以此降低匿名后數據的損失和隱私泄露風險。

2.1 敏感屬性的敏感度劃分

本文根據用戶對敏感屬性值的敏感度劃分敏感級別，針對個體敏感性的敏感度實施分級保護。

定義5(敏感屬等級)，若在數據集為T，其中某個敏感屬性的值集合為{S1,S2,…,Sd}，對敏感屬性的敏感度評定。規定當敏感度為[0，30]時為低敏感度，(30，60]為中敏感度，(60，90]為高敏感度。

表5為用戶的定義敏感度。

表5 敏感屬敏感度評定表

定義6(泛化屬性值敏感度)假設某個泛化屬性值Y,以其為根的子樹其子節點集合為{S1,S2,…,Sm},則泛化屬性值的敏感度為：

(1)

2.2 敏感屬性泛化樹

根據敏感屬性的取值對其屬性構建屬性泛化樹G，將每個原始的敏感屬性的取值均存放在樹的葉子結點中，根據式(1)計算屬性泛化樹上每個泛化節點值的敏感度。對不同的敏感級別的敏感屬性值進行不同方式的泛化，規定將高敏感級別的敏感屬性值泛化到中敏感級別的敏感屬性值，其他敏感屬性的泛化按照等價類中不同敏感屬性的個數和每個敏感屬性進行相應的泛化。如圖1所示，敏感屬性為疾病，取值為{Asthma，Pneumonia，Flu，Cancer，HIV，Measles}。若根據評分認為Asthma(哮喘)是高敏感屬性泛化到下一級敏感屬性值呼吸病，若不能泛化到下一級敏感度則泛化到根節點疾病為止。

圖1 敏感屬性泛化樹

2.3 精度度量

本文主要采用泛化技術來實現匿名操作，因此一定存在信息的損失。本文參考文獻[5]的對分類型屬性進行層次泛化的精度測量和數值型屬性進行區間泛化的精度測量，并給出以下相關定義。

定義7(分類型屬性損失度)假設某一屬性值P通過泛化樹泛化到節點Q，若Q節點子樹的個數記為MQ，則屬性值P泛化到節點Q信息損失度為：

(2)

式中：C表示P的父節點。

例如，如果將圖1中Asthma泛化到了疾病節點，則P=Asthma，Q=疾病，C=呼吸病，泛化過程中子樹個數序列為{M呼吸病=3，M疾病=3}，因此從Asthma泛化到了疾病節點信息損失為Loss(Asthma，疾病)=8/9。

定義8(數值型屬性損失度)假設某一數值型屬性值P通過屬性泛化樹泛化為Q，泛化的區間為[L,R]，則損失度為：

(3)

例如將屬性年齡25泛化到25～30,泛化區間為[25，30]，則泛化后損失為Loss(25，25～30)=4/5。

3 算法設計

本文提出的一種對敏感屬性的個性化保護的匿名隱私保護算法為個性化(p，α，k)-匿名隱私保護算法，算法對不同等級的敏感屬性采用不同的隱私方法策略：對高敏感屬性進行泛化操作，避免高敏感屬性值泄露。針對中敏感等級和低敏感等級的敏感屬性采用個性化閾值α方法進行隱私保護。算法的大體思想是：將高敏感屬性的值泛化為中敏感屬性值，然后限定等價類中等級敏感屬性值和低敏感屬性值出現的頻率不大于α，并保證等價類中不同敏感屬性值的個數不小于p。

算法思想步驟：

1) 根據準標識符屬性值的相似性分成每組k條記錄的若干元組的集合，將每個組泛化成等價類。

2) 將每個等價類中按敏感度由高到低進行排列，并將高敏感屬性值向上泛化成下一級敏感屬性值。

3) 統計每個等價中的不同敏感屬性值的個數是否大于p，若小于p則將相對高的敏感屬性值進行泛化并使得泛化后的值的頻率小于α，直到等價類中不同的敏感屬性值個數大于等于p。

4) 核查每個等價類中每個屬性值的頻率是否小于等于α，若大于α則進行泛化操作，并使得泛化后值的頻率不能大于α。

算法個性化(p，α，k)-匿名隱私保護算法。

輸入待發布的原始數據表T，敏感屬性敏感度評定表ST，匿名參數k，等價類不同敏感屬性值個數最小參數p，每個敏感值在等價類中出現的最大頻率α。

輸出匿名表T′

(1) 將數據表中的所有屬性依次構建屬性泛化樹，并根據敏感度評定表ST對敏感屬性泛化樹上的泛化值根據式(1)計算其泛化后的敏感度；

(2) 統計數據表的記錄數size，若size

(3) 從數據表中取出在準標識符屬性值上相似度最高的k條記錄元組，并將元組存放到t中，然后返回執行(2)；

(4) 將數據表剩余的值根據準標識符屬性的相似度加入到list中的元組中；

(5) 按照i從1～n循環遍歷元組t={t1,t2,…,tn}：

① 若ti為非空集合，屬性集合A{A1,A2,…,Am}，初始化m個size(ti)大小的集合{set1,set2,…,setm}，按照j從1～m遍歷集合：

② 按照j從1～m遍歷，若屬性為敏感屬性將高敏感屬性泛化為下一級敏感屬性值并將每個屬性值ti,j存放到setj中；

③ 按照從1～m遍歷集合set，若Aj為準標識符屬性，則執行④，若Aj為敏感屬性則執行⑤；

④ 根據setj值的分布泛化到當前屬性泛化樹中最小泛化的值Vj并將元組ti的當前屬性的值全部設置為Vj；

⑤ 將當前敏感屬性值ti[:,j]使其滿足其不同敏感值的個數不小于p且每個敏感值的頻率不大于α；

⑥ 返回元組t合并成匿名表T′。

4 實驗結果與分析

4.1 實驗數據及參數

實驗環境：Intel(R) Core(TM) i3-6100 CPU @3.70 GHz，4.00 GB內存， Microsoft Windows10操作系統，編程語言為Python 3.6。實驗選用的是UCI機器學習數據庫中的Adult數據集，刪除其中的缺省值處理得到共計30 162條記錄，本文選取其中6個屬性{Occupation，Age，Workclass，Education，Relationship，sex}，其數據結構見表6。將Occupation作為敏感屬性，其他的作為準標識符屬性，敏感屬性Occupation的屬性值設定的敏感度見表7。

表6 原UCI數據集Adult數據表結構

表7 敏感屬性值敏感度

實驗從信息損失度與執行時間2個方面進行分析比較。主要是比較以下模型：

(1) k-匿名模型：通過泛化樹最小信息代價泛化構造匿名表，對定義的敏感屬性不進行泛化處理。

(2) 個性化(α，k)-匿名模型：通過泛化樹最小信息代價泛化構造匿名表，且對不同等級敏感度設定不同的閾值α，實現對敏感屬性個性化匿名保護。

(3) 個性化(p，k)-匿名模型：通過泛化樹最小信息代價泛化構造匿名表，通過對不同等級敏感度的敏感屬性泛化不到不同的層次。高敏感屬性泛化為根節點，中敏感屬性泛化為父節點，并使等價類中不同敏感值的個數不小于閾值p，從而實現個性化匿名隱私保護。

(4) 個性化(p，α，k)-匿名模型：通過泛化樹最小信息代價泛化構造匿名表，通過對不同等級敏感屬性采用不同的匿名方式：將高敏感屬性值泛化為中敏感屬性值，然后將其他等級的敏感屬性值采用閾值α進行匿名化，并使等價類中不同敏感值的個數不小于閾值p，從而實現個性化匿名隱私保護。

4.2 執行時間分析

設準標識符屬性個數為5、數據集大小為30 162，當k值改變時，比較四個匿名算法的執行時間，如圖2所示。可知，隨著k值的增大，四種算法的執行時間反而減小。這主要因為本文是采用從源數據集中取出準標識符屬性上相似度最高的k條記錄直到數據集為空為止，當k值增大時，等價類的數量減少，因此執行時間會減小。本文的個性化(p，α，k)匿名算法，因為需要滿足的條件根據多樣化，進行比較的次數會增加，因此比其他算法的執行時間要高。

圖2 執行時間

4.3 信息損失度分析

信息損失度用式(2)、式(3)來度量，設準標識符屬性個數為5，數據集大小為30 162，當k值改變時，比較四種匿名算法的平均信息丟失程度，如圖3所示。四種算法的平均信息丟失程度隨著k值的增加而增加，因為k值越大，每個等價類中元組的數量將增加，等價類中元組的泛化將更高，從而導致更多的信息丟失。其中，k匿名算法的平均信息丟失最小的原因是該算法僅對標識符的屬性進行泛化操作，因此信息平均損失度比其他三種匿名算法低；個性化(α，k)-匿名算法對不同的敏感級別的敏感屬性值設置不同閾值實現個性化匿名隱私保護，而個性化(p，α，k)-匿名算法只是對中級敏感屬性值和低級敏感屬性設置不同閾值，其信息損失要比個性化(α，k)-匿名算法低；個性化(p，k)-匿名算法將高敏感度的敏感屬性泛化到樹的根節點，中敏感度的敏感屬性泛化到父節點。而個性化(p，α，k)-匿名算法采用泛化樹和閾值α方法共同實現個性化隱私保護，只對高敏感度的敏感屬性采用泛化樹的方式泛化到父節點，其他敏感級別屬性值采用閾值α方法，因此信息損失度地個性化(p，k)-匿名要低。

圖3 平均損失度

5 結 語

本文提出了個性化(p，α，k)匿名隱私保護算法，根據敏感屬性值的屬性度、屬性泛化樹按照式(1)計算泛化屬性值敏感度；通過敏感級別定義建立對敏感屬性值分級，然后對高敏感度屬性值采用泛化樹進行降級泛化，對中級敏感屬性值和低級敏感屬性值采用不同閾值α限制其在等價類的頻率。通過該算法匿名發布數據，雖然從時間上看，花費了比其他算法多一點的時間代價，但是從隱私和信息損失方面，降低了數據隱私泄露風險和信息損失量。