支持多屬性泛化的個性化(α,l,k)匿名模型

蘇林萍，董子嫻，李 為，吳克河，崔文超

(華北電力大學 控制與計算機工程學院，北京 102200)

0 引 言

在信息高度共享的今天，每天都有大量的數(shù)據(jù)被收錄和發(fā)布。對信息的挖掘和分析，可以有效促進科學事業(yè)的發(fā)展，從而為人們營造更加便捷暢通的生活環(huán)境。但與此同時，不得不面臨隱私數(shù)據(jù)的泄露問題。因此需要重點保護個體的隱私數(shù)據(jù)。

在數(shù)據(jù)匿名化的思想下，隱私數(shù)據(jù)保護模型的基本做法是：在滿足信息安全發(fā)布的要求下，隱匿特定個體和敏感信息之間的聯(lián)系，并提高數(shù)據(jù)的可用性[1]。但是傳統(tǒng)的匿名方式并未考慮不同個體對敏感數(shù)據(jù)的個性化隱匿需求[2]。不同的隱私信息其敏感等級必然不同，同一敏感信息對不同個體的敏感程度也會不同[3]。

Xiao等在文獻[4]中第一次提出了個性化匿名的思想，之后出現(xiàn)了很多增強型的改進算法。其中，文獻[5-6]為數(shù)據(jù)集中的每一個元組都設置了不同的隱匿需求，盡管極大程度地滿足了不同個體的個性化需求， 但是工作量巨大， 也造成了不必要的數(shù)據(jù)冗余。 文獻[7]提出個性化(α,l)-多樣化k-匿名模型，歸納個性化隱匿方式包括兩種機制，一種是面向個人的，一種是面向敏感值的。因為一般來說，僅僅面向個人的隱私保護模型容易由于個體的喜好造成信息的不必要損失和隱私泄露，而單純面向敏感值的方式往往會欠缺特定個體的特定需求[8]。但是這種方法因為層層的限制條件而造成了屬性值的過度泛化。文獻[9]則提出了個性化(p,α,k)-匿名模型，改善了匿名后數(shù)據(jù)損失較大和高敏信息泄露的缺陷，將敏感值劃分不同的敏感級別，并且各等級應用不相同的匿名方式，但是其對個性化的需求體現(xiàn)不足[10]。

針對上述文獻中所提方法存在的不足，該文基于個性化(α,l)-多樣化k-匿名模型和個性化(p,α,k)-匿名模型，提出針對屬性過度泛化的改進的個性化匿名模型：應用文獻[11]中敏感度評分的概念給不同的敏感值定義不同的等級，再根據(jù)少量特定個體對自己敏感屬性的評級為每條記錄確定最終的敏感值等級，按照敏感屬性泛化樹將高敏值直接泛化到下一級，然后使此時等價組里中低級敏感值滿足l和α約束。

1 匿名模型

數(shù)據(jù)匿名化，指對要發(fā)布數(shù)據(jù)集的各屬性進行合理的脫敏操作，要求數(shù)據(jù)在對應運維、實施或者數(shù)據(jù)挖掘等場景下不影響使用的同時，不能反識別出對應的個體。

可將原始集中屬性劃分為以下四種[12]：標識符屬性(ID)，是可以唯一標識到特定個體的屬性，例如表1的“Name”。這部分屬性在匿名處理中一般會被直接移除；準標識符屬性(QI)，是可通過和外部數(shù)據(jù)鏈接或背景知識的手段唯一確定出特定個體的屬性[13]。例如表1中的“Gender”、“Age”和“Zip code”屬性；敏感屬性(S)，是指個體的敏感信息，指攻擊者最想明確和關聯(lián)的屬性[14]，如表1中的屬性“Disease”；非敏感屬性(N)，也就是其他屬性，在脫敏時這部分屬性不做處理。

表1 原始數(shù)據(jù)

定義1：等價組。給定數(shù)據(jù)集T={A1,A2,…,An}，n為T中屬性的個數(shù)。則其中的準標識符屬性集QI={q1,q2,…,qi}里，i為準標識符屬性個數(shù)，值一致的記錄則屬于同一等價組。

定義2：k-匿名。給定數(shù)據(jù)集T和等價組Q，若對于?Q?T，Q中的記錄條數(shù)都至少為k(k≥2)，則T滿足k-匿名。

由此可知，當數(shù)據(jù)集滿足k-匿名時，攻擊者確定特定個體和元組數(shù)據(jù)之間關聯(lián)關系的概率不超過1/k，有效防止了鏈接攻擊，不過因為并未破壞特定個體與敏感信息間的關系，所以還是會有背景知識攻擊以及同質攻擊的可能[15]。例如，表2就是對原始表表1的2-匿名化實例，當知道Tom的性別、年齡和郵編信息時，因為表中記錄6和7的疾病屬性都是Cancer，所以由此可以確定Tom的所患疾病，很顯然，這是Tom不想公開的屬性信息。

表2 2-匿名表

基于k-匿名模型中存在的風險，需要破壞特定個體與敏感信息之間的關聯(lián)關系，這就需要引入l-多樣性模型。

定義3：l-多樣性。給定數(shù)據(jù)集T和等價組Q，若對于?Q?T，其敏感屬性值的種類數(shù)都不小于l(l≥2)，則該數(shù)據(jù)集滿足l-多樣性模型。

表3即對表2中的敏感屬性按2-多樣性模型泛化后的示例，此時，對于每一個等價類，其敏感屬性的種類個數(shù)都至少為2。但是該模型無法避免相似性攻擊和偏斜攻擊，以表3為例，當只能確定Amy為最后兩條記錄時，由于其疾病種類都是很嚴重的屬性值，所以還是可以得知Amy得了絕癥，這可能是Amy極度不想公開的隱私信息。

表3 2-多樣性表

定義4：個性化(α,l)-多樣化k-匿名模型。給定數(shù)據(jù)集T={A1,A2,…,An}，將敏感值按敏感度的不同劃分不同的等級Sid，此時若有特定個體對自己記錄的敏感值等級指定了等級Ppl，且Ppl>Sid，則按照Ppl的等級替換Sid。匿名后數(shù)據(jù)集T*，若T*符合k匿名，且各等價組里不同敏感值的個數(shù)不低于l，每個等價組里相同敏感等級的敏感值出現(xiàn)的頻率不大于α，就可以稱T*符合個性化(α,l)-多樣化k-匿名模型。

定義5：個性化(p,α,k)-匿名模型。給定數(shù)據(jù)集T={A1,A2,…,An}，將敏感值按敏感程度不同分為高中低三級，將高等級敏感值直接泛化。匿名后數(shù)據(jù)集T*，若此時T*符合k匿名，且此時各等價組里不同敏感值的個數(shù)不低于p，每個等價組中相同敏感值出現(xiàn)的頻率不大于α，就可以稱T*符合個性化(p,α,k)-匿名模型。

2 個性化(α,l,k)匿名模型相關概念

為了給特定個體提供有效的個性化服務，同時要降低信息損失量來提高數(shù)據(jù)的可用性，該文結合個性化(α,l)-多樣化k-匿名和個性化(p,α,k)-匿名兩種模型，提出了一種個性化(α,l,k)匿名模型。在個性化(α,l)-多樣化k-匿名模型中，雖然同時考慮了面向個人和面向敏感值兩種個性化隱匿機制，但是通過實驗也可以看出，由于過度泛化造成了大量的信息損失，極大地影響了數(shù)據(jù)的分析和挖掘。個性化(p,α,k)-匿名模型則提出針對敏感度較高值泛化的思想，將高等級敏感值直接泛化，在讓其余中低敏感等級的值滿足p,α約束時，也是優(yōu)先泛化較高敏感級的屬性，由此不僅有效降低了數(shù)據(jù)集的敏感度，還降低了信息損失量，但是個性化的思想體現(xiàn)不足。由此，該文提出一種個性化(α,l,k)匿名模型。

2.1 敏感屬性的敏感度劃分與頻率約束α

下面將引入文獻[11]里敏感度評分的思想，以其結果作為敏感值的敏感等級，這樣較個性化(α,l)-多樣化k-匿名模型更加體現(xiàn)個性化需求。

定義6：敏感度評分。統(tǒng)計個體對每個敏感值敏感程度的評分結果，并以統(tǒng)計結果的有效區(qū)間劃分等級，作為敏感值敏感等級的預設參數(shù)。用這種方式設定的參數(shù)能更加滿足大眾用戶對敏感度的要求。

例如散點圖1所示，該圖為對敏感屬性疾病的調查結果，橫坐標依次代表Flu、Indigestion、Heart disease、Asthma、Phthisis、Hepatitis、HIV和Cancer這八種疾病，將評分滿分設置為80分，每個個體根據(jù)自己對疾病的重視程度對各個疾病進行打分，得分越高表示重視程度越高。去掉離群點，可以看到數(shù)據(jù)依次集中在區(qū)間[0,20)、[0,20)、[20,40)、[20,40)、[40,60)、[40,60)、[60,80)、[60,80)中，所以疾病的敏感屬性可劃分為4個等級，分別為1、2、3和4，并將這個值作為敏感屬性的預設參數(shù)C。劃分結果如表4所示。

圖1 敏感度評分結果

表4 敏感屬性預設參數(shù)

定義7：頻率約束α。給定數(shù)據(jù)集T、等價組Q，指定的敏感屬性S中各個敏感值的出現(xiàn)頻率α(0≤α≤1)。若在任意等價組Q中，任意屬性值都滿足|(Q,S)|/|Q|≤α，那么數(shù)據(jù)集T滿足出現(xiàn)頻率約束α。其中，|(Q,S)|指等價組Q中敏感屬性為S的記錄個數(shù)，|Q|是等價組Q的大小。

2.2 敏感屬性泛化樹

構建敏感屬性泛化樹，如圖2所示。各個原始敏感值作為泛化樹的葉節(jié)點，樹的高度至少是敏感屬性的總等級數(shù)，要求被泛化的每個父節(jié)點均滿足各敏感值的行業(yè)規(guī)范。

圖2 敏感屬性泛化樹

2.3 個性化隱私保護規(guī)則

在通過應用敏感度評分的方法，達到了面向敏感值的個性化需求基礎上，本模型還支持面向個人的個性化需求，允許用戶給自己記錄的敏感值認定敏感等級。需要注意的是，自定義的敏感等級值p不得超過泛化樹的高度H。僅當p>C時，需用p值替換C的值。

如表5所示，在ID為3的記錄中p=2≥C=1，所以會對該記錄執(zhí)行進一步脫敏操作，用對應等級父節(jié)點“呼吸道感染”屬性值代替“Flu”。其中，用戶指定的敏感等級p列中，“-”代表用戶未指定等級。

表5 隱私保護級別

2.4 信息損失度量

不管是準標識符屬性還是隱私屬性的泛化操作都會帶來信息的損失[16]。信息的損失反映了信息的可用性，但在一定程度上也反映了敏感信息的保護程度。

定義8：信息損失量。給定數(shù)據(jù)集T，規(guī)定T里屬性A的閾值是size(A)，那么A被泛化成A*的信息損失量為：

(1)

其中，|A*|為屬性A被泛化后的值。|size(A)|是A的可能取值，若該屬性是連續(xù)性數(shù)據(jù)，取區(qū)間長度，若是分類型數(shù)據(jù)，取值域的基數(shù)。

所以T中記錄ti(1≤i≤n)的信息損失量如下，其中Wi是A的信息損失量權重：

(2)

則T中所有屬性的信息損失量為：

(3)

3 算法設計

該文提出了個性化(α,l,k)匿名算法，本算法結合了個性化匿名的兩種機制，在極大程度滿足個性化的前提下，有效降低了數(shù)據(jù)損失量。

算法步驟如下：

(1)引用文獻[17]中提出的多屬性泛化的方法得到符合k匿名的數(shù)據(jù)集；

(2)比較自定義的敏感等級p和敏感屬性的預設參數(shù)C，若p>C，則修改對應記錄的等級，用F代表敏感屬性的最終級別，再將敏感值泛化到相應的級別；

(3)將每個等價組中的記錄按敏感值的敏感等級由高到低進行排序，將F最高的屬性信息直接泛化到下一級；

(4)統(tǒng)計各等價類里不一致的敏感值個數(shù)，若小于l則將F相對較高的值進行泛化，并使其滿足出現(xiàn)頻率α的約束，直到滿足個數(shù)值大于等于l；

(5)計算各等價類中各敏感值出現(xiàn)的頻率，若大于α則將敏感度相對較高的屬性進行泛化，直到滿足頻率值小于等于α。

如表6所示，是對表2中隱私屬性Disease的進一步泛化，使其滿足個性化(0.5,2,2)匿名模型的要求。最后一列是敏感屬性的最終敏感等級，在滿足個性化隱私保護規(guī)則的同時，滿足對α、l和k值的要求。其中共三個等價組，分別為記錄1～2、3～4和5～7，各等價組均包括兩條及以上記錄，等價組里不同種類的敏感值最少為兩種，且符合出現(xiàn)頻率α為0.5。

表6 個性化(0.5,2,2)匿名模型

生成個性化(α,l,k)匿名算法：(以上文中疾病這一敏感屬性為例)

輸入：數(shù)據(jù)集T，參數(shù)α、l、k，敏感等級C與p

輸出：滿足發(fā)布條件的數(shù)據(jù)集T*

(1)對T中的所有屬性構建泛化樹；

(2)計算T中記錄的總條數(shù)count，if(count==0)，則執(zhí)行(7)；else，則繼續(xù)執(zhí)行(3)；

(3)引用文獻[11]中提出的多屬性泛化方法得到符合k匿名的數(shù)據(jù)集T1；

(4)用C列值給F列賦初值，對于每一條記錄，if(C

(5)依次在T2中取出k條記錄，并將其存放到ti中；

(6)i從1～n遍歷t={t1,t2,…,tn}：

①若ti.length()不為0，則j從1～m遍歷tj，將tj中的記錄按敏感值的F由高到低進行排序，將F為最高級的敏感值泛化一級并替換原值；

②若ti.length()不為0，則k從1～m遍歷tk，若tk中不同敏感值個數(shù)小于l，則泛化較高F的敏感值，且保證該敏感值滿足α約束，直到tk中的敏感值均滿足l和α約束；

③合并t作為T*。

(7)返回T*。

4 實驗結果與分析

本實驗采用UCI機器學習倉庫中Adult數(shù)據(jù)集，此數(shù)據(jù)集被廣泛應用于脫敏領域的研究實驗。其中有48 842條記錄，可篩選出30 162條有效數(shù)據(jù)作為原始數(shù)據(jù)集T。選取T中的6個屬性為QI，并添加一列Disease為S列，屬性的基本情況如表7所示。其中敏感屬性列的敏感等級C值依舊應用上文的用戶評分結果，隨機選取2/5的數(shù)據(jù)記錄添加用戶自定義的疾病敏感屬性值，并為表7中所有屬性構建泛化樹。

表7 各屬性基本情況

實驗環(huán)境：硬件環(huán)境為Intel Core i7-6700 3.40 GHz CPU，8 GB RAM；操作系統(tǒng)為Windows10；編程語言為Java。為了驗證分析該算法的實用性，將個性化(α,l)-多樣化k-匿名模型和個性化(p,α,k)-匿名模型在運行時間和信息損失量上作比較。固定l和α的值分別為4和0.7，每組實驗反復運行10次，剔除離群數(shù)據(jù)，并取剩余值的平均數(shù)作為最后的取值。

4.1 運行時間分析比較

在相同實驗條件下，比較三種算法在k值大小的變化下，運行時間的變化。由圖3可知，隨k值變大，三種模型的運行時間都會減少，是由于等價組數(shù)量變少了，要處理的次數(shù)就也變少了。由于該文所提算法較個性化(p,α,k)-匿名算法增加了很多個性化的處理，所以運行時間上會稍多。隨著k值的增大，對于多樣性的要求越容易滿足，所以折線的斜率會小一些。

圖3 運行時間與k值的關系

4.2 信息損失量分析比較

采用上文所給信息損失量公式(3)，在相同實驗條件下，比較三種算法在k值大小的變化下，信息損失量的變化。如圖4所示，隨k值變大，三種模型的損失量也在變大，是由于等價組里記錄數(shù)變多造成的。該文所提算法不僅應用了個性化(p,α,k)-匿名算法中對不同敏感等級的敏感值采取不同匿名方式的思想，還引入了文獻[11]中的多屬性泛化方法來使數(shù)據(jù)集滿足k匿名，該方法針對屬性過度泛化進行了深入研究，因此所提模型信息損失量要低。

圖4 信息損失量與k值的關系

5 結束語

提出一種個性化(α,l,k)匿名模型。該模型在應用多屬性泛化算法得到符合k-匿名模型的基礎上，將敏感屬性在面向個人和面向敏感值這兩方面進行匿名操作，且針對不同敏感等級的敏感值執(zhí)行不一樣的操作，同時使其滿足各等價組里敏感值的多樣性和頻率。實驗表明，該模型在有限的運行時間內，達到了較好的個性化隱私保護效果。但是該模型是面向單敏感值的匿名操作，在實際生活中會經(jīng)常面臨多敏感值的情況，所以提出可以應用于任意敏感屬性個數(shù)的個性化匿名模型是后續(xù)研究工作的主要內容。