蘇林萍，董子?jì)?，?為，吳克河，崔文超

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

0 引 言

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

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

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

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

1 匿名模型

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

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

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

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

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

由此可知，當(dāng)數(shù)據(jù)集滿(mǎn)足k-匿名時(shí)，攻擊者確定特定個(gè)體和元組數(shù)據(jù)之間關(guān)聯(lián)關(guān)系的概率不超過(guò)1/k，有效防止了鏈接攻擊，不過(guò)因?yàn)椴⑽雌茐奶囟▊€(gè)體與敏感信息間的關(guān)系，所以還是會(huì)有背景知識(shí)攻擊以及同質(zhì)攻擊的可能[15]。例如，表2就是對(duì)原始表表1的2-匿名化實(shí)例，當(dāng)知道Tom的性別、年齡和郵編信息時(shí)，因?yàn)楸碇杏涗?和7的疾病屬性都是Cancer，所以由此可以確定Tom的所患疾病，很顯然，這是Tom不想公開(kāi)的屬性信息。

表2 2-匿名表

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

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

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

表3 2-多樣性表

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

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

2 個(gè)性化(α,l,k)匿名模型相關(guān)概念

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

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

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

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

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

圖1 敏感度評(píng)分結(jié)果

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

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

2.2 敏感屬性泛化樹(shù)

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

圖2 敏感屬性泛化樹(shù)

2.3 個(gè)性化隱私保護(hù)規(guī)則

在通過(guò)應(yīng)用敏感度評(píng)分的方法，達(dá)到了面向敏感值的個(gè)性化需求基礎(chǔ)上，本模型還支持面向個(gè)人的個(gè)性化需求，允許用戶(hù)給自己記錄的敏感值認(rèn)定敏感等級(jí)。需要注意的是，自定義的敏感等級(jí)值p不得超過(guò)泛化樹(shù)的高度H。僅當(dāng)p>C時(shí)，需用p值替換C的值。

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

表5 隱私保護(hù)級(jí)別

2.4 信息損失度量

不管是準(zhǔn)標(biāo)識(shí)符屬性還是隱私屬性的泛化操作都會(huì)帶來(lái)信息的損失[16]。信息的損失反映了信息的可用性，但在一定程度上也反映了敏感信息的保護(hù)程度。

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

(1)

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

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

(2)

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

(3)

3 算法設(shè)計(jì)

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

算法步驟如下：

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

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

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

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

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

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

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

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

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

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

(1)對(duì)T中的所有屬性構(gòu)建泛化樹(shù)；

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

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

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

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

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

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

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

③合并t作為T(mén)*。

(7)返回T*。

4 實(shí)驗(yàn)結(jié)果與分析

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

表7 各屬性基本情況

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

4.1 運(yùn)行時(shí)間分析比較

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

圖3 運(yùn)行時(shí)間與k值的關(guān)系

4.2 信息損失量分析比較

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

圖4 信息損失量與k值的關(guān)系

5 結(jié)束語(yǔ)

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