面向多元組關(guān)系-集值數(shù)據(jù)的脫敏方法

顧兆軍，蔡 暢,+，劉春波，鐘安鳴

(1.中國(guó)民航大學(xué) 信息安全測(cè)評(píng)中心，天津 300300； 2.中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

0 引 言

保證待發(fā)布數(shù)據(jù)安全的前提下，盡可能提高數(shù)據(jù)的可用性是當(dāng)前數(shù)據(jù)脫敏研究的重點(diǎn)。匿名化技術(shù)是發(fā)布數(shù)據(jù)常用的脫敏技術(shù)[1-3]?；A(chǔ)匿名模型有K-匿名[4,5]、L-多樣性[6]和T-接近[7]。在此基礎(chǔ)上，衍生出不少相關(guān)模型，例如約束等價(jià)類(lèi)中的敏感值的出現(xiàn)頻率的(α,k)-匿名模型[8]，和對(duì)個(gè)數(shù)進(jìn)行約束的(K,L)-多樣性匿名模型[9]等。

為滿足匿名模型要求，學(xué)者們提出了很多匿名算法。傳統(tǒng)的匿名算法僅考慮單元組數(shù)據(jù)的匿名，如基于局部泛化的Partition[10]、貪心匿名算法[11]等，但現(xiàn)實(shí)中的數(shù)據(jù)集大多是多元組數(shù)據(jù)，應(yīng)用此類(lèi)方法，由于準(zhǔn)標(biāo)識(shí)符泛化不統(tǒng)一，會(huì)導(dǎo)致信息泄露以及信息缺損。且很多匿名算法僅針對(duì)集值數(shù)據(jù)匿名，如基于格雷碼的局部泛化算法[12]，或僅對(duì)關(guān)系數(shù)據(jù)匿名，如基于有損分解的匿名算法[13]、基于聚類(lèi)的LAC[14]等，無(wú)法直接應(yīng)用到關(guān)系-集值數(shù)據(jù)中。關(guān)于關(guān)系-集值數(shù)據(jù)匿名，文獻(xiàn)[15]對(duì)其進(jìn)行了研究，但對(duì)等價(jià)類(lèi)約束過(guò)于嚴(yán)格，導(dǎo)致信息損失較高，脫敏后數(shù)據(jù)不具有可用性。對(duì)此，Gong等[16]提出了1M-Generalization算法，融合兩種基礎(chǔ)匿名方法，對(duì)關(guān)系數(shù)據(jù)采用多維泛化Mondrain，泛化粒度縮小，使得脫敏后數(shù)據(jù)具有可用性，但隨數(shù)據(jù)維度增加，導(dǎo)致信息缺損增加且算法效率較低。因此，本文基于(K,L)-多樣性模型，提出了一種適用于多元組關(guān)系-集值數(shù)據(jù)的脫敏方法PAHI。將多元組數(shù)據(jù)轉(zhuǎn)換成單元組數(shù)據(jù)，根據(jù)模型約束，按順序來(lái)實(shí)現(xiàn)關(guān)系-集值數(shù)據(jù)的匿名。保證脫敏后數(shù)據(jù)的安全性，同時(shí)降低信息損失和時(shí)間開(kāi)銷(xiāo)。

1 相關(guān)概念

1.1 數(shù)據(jù)分類(lèi)

一般根據(jù)數(shù)據(jù)屬性將待發(fā)布的數(shù)據(jù)分為4類(lèi)，標(biāo)識(shí)符屬性、準(zhǔn)標(biāo)識(shí)符屬性、敏感屬性和其它屬性[1]。

(1)標(biāo)識(shí)符屬性(EID)[1]：一般指能夠唯一確定一個(gè)用戶的屬性，例如個(gè)人的身份證號(hào)，航空公司的常客卡號(hào)等屬性。

(2)準(zhǔn)標(biāo)識(shí)符屬性(QID)[1]：通常指一組屬性，可以通過(guò)結(jié)合外部表來(lái)唯一識(shí)別用戶的屬性集合。例如{性別，年齡，郵編}，{年齡，客戶標(biāo)志，郵編}等屬性集合。

(3)敏感屬性(SA)[1]：通常指包含個(gè)人隱私信息的一類(lèi)屬性，例如婚姻狀況、疾病狀況、航班號(hào)等屬性。

(4)其它屬性(NSA)[1]：不需要脫敏的屬性。

一般情況下，脫敏待發(fā)布的數(shù)據(jù)，需要?jiǎng)h除標(biāo)識(shí)符屬性，并對(duì)準(zhǔn)標(biāo)識(shí)符和敏感屬性進(jìn)行脫敏處理。

根據(jù)屬性值的類(lèi)型，參考文獻(xiàn)[15],本文將數(shù)據(jù)分為關(guān)系數(shù)據(jù)和集值數(shù)據(jù)。一般情況下，關(guān)系數(shù)據(jù)是指包含關(guān)系型屬性的一類(lèi)數(shù)據(jù)，其中，關(guān)系型屬性是指可以構(gòu)成數(shù)據(jù)集中的準(zhǔn)標(biāo)識(shí)符的屬性。集值數(shù)據(jù)是指包含可以取多個(gè)值的屬性的一類(lèi)數(shù)據(jù)，屬性可以舉例描述，例如疾病情況屬性，取值集合{心臟病，糖尿病，癌癥}。通常情況下，很多敏感數(shù)據(jù)都是集值數(shù)據(jù)。在需要發(fā)布的數(shù)據(jù)集中，大部分的數(shù)據(jù)集都是關(guān)系-集值數(shù)據(jù)集。本文中，為了簡(jiǎn)化描述，將關(guān)系數(shù)據(jù)作為準(zhǔn)標(biāo)識(shí)符，集值數(shù)據(jù)作為敏感屬性。同時(shí)，參考文獻(xiàn)[16]，假設(shè)數(shù)據(jù)集中只有一個(gè)敏感屬性。

定義1 多元組數(shù)據(jù)(multiple tuples data)：在一個(gè)數(shù)據(jù)集中，一條記錄是一個(gè)元組，將待發(fā)布的數(shù)據(jù)集中同一個(gè)用戶含多條記錄的數(shù)據(jù)集稱為多元組數(shù)據(jù)集，記為DM。

DM={QI1,QI2,…,QIm,S}， 其中， {QI1,QI2,…,QIm} 為準(zhǔn)標(biāo)識(shí)符 (m≥2)，S為敏感屬性， |DM|=n， 表示數(shù)據(jù)集中記錄的總數(shù)。具體樣例見(jiàn)表1，表1中給出了一個(gè)民航旅客多元組關(guān)系-集值數(shù)據(jù)集，航班號(hào)用編碼代替，其中，屬性姓名為標(biāo)識(shí)符屬性，屬性年齡、旅客標(biāo)志與郵編為準(zhǔn)標(biāo)識(shí)符屬性，屬性航班號(hào)為敏感屬性。在數(shù)據(jù)集中，Sam擁有3條航班記錄，Amyli擁有兩條航班記錄。

為了實(shí)現(xiàn)對(duì)多元組關(guān)系-集值數(shù)據(jù)的脫敏，防止信息泄露，本文采取二次數(shù)據(jù)劃分策略，分步實(shí)行兩種分組方法。根據(jù)關(guān)系數(shù)據(jù)和集值數(shù)據(jù)，將數(shù)據(jù)分為等價(jià)類(lèi)和集值指紋桶。

定義2 等價(jià)類(lèi)(Equivalence Class)[4]：對(duì)于多元組數(shù)據(jù)集DM,等價(jià)類(lèi)是指在準(zhǔn)標(biāo)識(shí)符 {QI1,QI2,…,QIm} 上取值相同的記錄的集合，記為EC。

EC1∪EC2∪…∪ECt=DM,ECi∩ECj=?， 其中t為DM中等價(jià)類(lèi)的個(gè)數(shù), 0

定義3 集值指紋(Set-valued fingerprint)：對(duì)于多元組數(shù)據(jù)集DM，同一個(gè)用戶具有多條記錄，同一個(gè)用戶的所有敏感屬性值構(gòu)成的集合稱為集值指紋,記為SV。例如對(duì)于民航旅客數(shù)據(jù)集，A旅客的集值指紋為{航班1，航班2，航班3}。

定義4 集值指紋桶(SV_Bucket)：對(duì)于多元組數(shù)據(jù)集DM，集值指紋取值相同的記錄構(gòu)成的集合稱為集值指紋桶，記為SV_Bucket。

SV_Bucket1∪SV_Bucket2∪…∪SV_Bucketp=DM，SV_Bucketi∩SV_Bucketj=?, 其中p為DM中集值指紋桶的個(gè)數(shù)， 0

1.2 匿名模型

匿名模型對(duì)脫敏后的數(shù)據(jù)質(zhì)量具有重要的意義。本節(jié)將介紹K-匿名模型[4]、L-多樣性模型[6]以及(K,L)-多樣性模型[9]。

定義5K-匿名[4]：設(shè)數(shù)據(jù)集D*為多元組數(shù)據(jù)集DM脫敏后的匿名數(shù)據(jù)集，EC是D*中的任意一個(gè)等價(jià)類(lèi)，若是EC中有不少于K條記錄，則稱等價(jià)類(lèi)EC是滿足K-匿名的，若數(shù)據(jù)集D*中所有的等價(jià)類(lèi)都滿足K-匿名，則稱數(shù)據(jù)集D*是滿足K-匿名。

表2是表1原始民航旅客多元組關(guān)系-集值數(shù)據(jù)集滿足2-匿名的發(fā)布表。采用傳統(tǒng)的K-匿名模型脫敏后的數(shù)據(jù)，可以防止身份信息的泄露。但是由于沒(méi)有對(duì)敏感屬性值進(jìn)行處理，脫敏后的數(shù)據(jù)無(wú)法抵抗同質(zhì)攻擊和背景知識(shí)攻擊[3]。L-多樣性模型對(duì)K-匿名模型的缺點(diǎn)進(jìn)行了改進(jìn)。

表2 民航旅客多元組關(guān)系-集值數(shù)據(jù)集2-匿名

定義6L-多樣性[6]：設(shè)數(shù)據(jù)集D*為多元組數(shù)據(jù)集DM脫敏后的匿名數(shù)據(jù)集，EC是D*中的任意一個(gè)等價(jià)類(lèi)，若EC中不同集值指紋的個(gè)數(shù)不少于L(L≥2),則稱等價(jià)類(lèi)EC是滿足L-多樣性，若數(shù)據(jù)集D*中所有的等價(jià)類(lèi)均滿足L-多樣性，則稱數(shù)據(jù)集D*是滿足L-多樣性的。

L-多樣性模型通過(guò)對(duì)等價(jià)類(lèi)中集值指紋個(gè)數(shù)的約束，使得脫敏后的數(shù)據(jù)可以抵御同質(zhì)攻擊。但是L-多樣性模型沒(méi)有約束記錄的數(shù)目，導(dǎo)致脫敏后數(shù)據(jù)可能遭受偏斜性攻擊和相似性攻擊，數(shù)據(jù)的安全性無(wú)法保證。

定義7 (K，L)-多樣性[9]：設(shè)數(shù)據(jù)集D*為多元組數(shù)據(jù)集DM脫敏后的匿名數(shù)據(jù)集，SV_Bucket是D*中任意一個(gè)集值指紋桶，EC是D*中的任意一個(gè)等價(jià)類(lèi),若滿足SV_Bucket中記錄的條數(shù)不少于K，且EC中至少有L(L≥2)個(gè)不同的集值指紋，則稱數(shù)據(jù)集D*是滿足(K,L)-多樣性的。

2 多元組關(guān)系-集值數(shù)據(jù)的脫敏方法

匿名算法的基礎(chǔ)是對(duì)數(shù)據(jù)的劃分，現(xiàn)有很多算法對(duì)數(shù)據(jù)執(zhí)行一次劃分。對(duì)于多元組關(guān)系集值數(shù)據(jù)，一次劃分可能無(wú)法滿足數(shù)據(jù)的安全需求?；?K,L)-多樣性模型的約束，在多元組關(guān)系-集值數(shù)據(jù)脫敏方法PAHI中，采取二次數(shù)據(jù)劃分策略，即讓集值指紋桶和等價(jià)類(lèi)并存，對(duì)關(guān)系數(shù)據(jù)和集值數(shù)據(jù)分步進(jìn)行匿名。PAHI算法的主要步驟分為3步，如圖1所示，先根據(jù)準(zhǔn)標(biāo)識(shí)符，對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換處理，以保證后續(xù)準(zhǔn)標(biāo)識(shí)符統(tǒng)一泛化；然后使用信息增益比優(yōu)化partition算法實(shí)現(xiàn)集值數(shù)據(jù)K-匿名；最后引入敏感度值建立集值指紋桶，并采用敏感度距離優(yōu)化剩余元組的處理，實(shí)現(xiàn)關(guān)系-集值數(shù)據(jù)的L-多樣性，得到匿名化的數(shù)據(jù)集D*。

圖1 PAHI算法基本步驟

2.1 數(shù)據(jù)轉(zhuǎn)換

現(xiàn)實(shí)生活中，待發(fā)布的真實(shí)數(shù)據(jù)集大多是多元組數(shù)據(jù)集。例如病人病歷數(shù)據(jù)集、超市的購(gòu)物數(shù)據(jù)集、民航旅客數(shù)據(jù)集等等。很多匿名模型和匿名方法對(duì)于多元組數(shù)據(jù)的處理，通常有兩種方法：一是把同一用戶的多條記錄刪除，轉(zhuǎn)化成單元組數(shù)據(jù)后再進(jìn)行脫敏處理，這種轉(zhuǎn)化方法會(huì)造成數(shù)據(jù)集較高的信息缺損；二是直接把它當(dāng)作單元組數(shù)據(jù)處理。

由于方法一刪除部分?jǐn)?shù)據(jù)，會(huì)導(dǎo)致數(shù)據(jù)集產(chǎn)生較高的信息損失。使用方法二處理數(shù)據(jù)，會(huì)導(dǎo)致信息泄露。以表2中的數(shù)據(jù)為例說(shuō)明方法二的弊端，表2中的數(shù)據(jù)是對(duì)表1中的多元組數(shù)據(jù)進(jìn)行了K-匿名脫敏，脫敏后的數(shù)據(jù)符合K-匿名的約束要求。但是，如果敵人從其它數(shù)據(jù)中獲得了Sam的準(zhǔn)標(biāo)識(shí)符信息，通過(guò)表2，即可獲得Sam的航班號(hào)指紋 {b1,b2,c1}。 并且在第二個(gè)等價(jià)類(lèi)中，敵人可以通過(guò)Sam的信息，推測(cè)第二組中另外一個(gè)人的準(zhǔn)標(biāo)識(shí)符情況，比如根據(jù)Sam的年齡21歲以及年齡的匿名區(qū)間，可以推測(cè)這位旅客的年齡小于20歲。由此造成信息泄露，這主要是準(zhǔn)標(biāo)識(shí)符泛化不一致造成的。

本文中根據(jù)準(zhǔn)標(biāo)識(shí)符，對(duì)多元組數(shù)據(jù)集進(jìn)行轉(zhuǎn)換。對(duì)于待發(fā)布的數(shù)據(jù)，在刪除標(biāo)識(shí)符屬性前，首先按照數(shù)據(jù)集原有的數(shù)據(jù)集的順序?qū)γ織l記錄進(jìn)行編號(hào)，增加編號(hào)一列，命名為OID，此列只是為了標(biāo)記，不參與匿名處理；然后遍歷數(shù)據(jù)集，將準(zhǔn)標(biāo)識(shí)符相同的記錄的敏感屬性值進(jìn)行合并，合并后保留一條數(shù)據(jù)，刪除其它重復(fù)數(shù)據(jù)；最后轉(zhuǎn)換結(jié)束，將標(biāo)識(shí)符屬性數(shù)據(jù)刪除，再進(jìn)行后續(xù)的脫敏處理。例如，將表1中的數(shù)據(jù)通過(guò)轉(zhuǎn)換，得到表3。此轉(zhuǎn)換方法可以使得數(shù)據(jù)在后續(xù)的匿名處理中保證轉(zhuǎn)標(biāo)識(shí)符的統(tǒng)一泛化。

表3 轉(zhuǎn)換后的數(shù)據(jù)集

2.2 匿名集值數(shù)據(jù)

多元組關(guān)系-集值數(shù)據(jù)集DM,通過(guò)本文的轉(zhuǎn)換方法得到數(shù)據(jù)集DS。轉(zhuǎn)換之后，集值數(shù)據(jù)部分變成了變長(zhǎng)的集值指紋。變長(zhǎng)的集值指紋具有高維性，文獻(xiàn)[17]中驗(yàn)證，高維數(shù)據(jù)具有“維度災(zāi)難”。為了降低數(shù)據(jù)缺損，本文采用基于局部泛化的Partition算法，并對(duì)它進(jìn)行改進(jìn)，來(lái)實(shí)現(xiàn)集值數(shù)據(jù)的K-匿名。

算法采用自頂向下的順序進(jìn)行泛化。核心步驟是節(jié)點(diǎn)的選擇階段，Partition算法以信息增益作為擴(kuò)展節(jié)點(diǎn)的依據(jù)，但是信息增益存在偏向于選擇子節(jié)點(diǎn)較多的節(jié)點(diǎn)的問(wèn)題。本文對(duì)其進(jìn)行改進(jìn)，使用信息增益比對(duì)這一問(wèn)題進(jìn)行校正。對(duì)于集值屬性泛化樹(shù)，信息增益的定義為擴(kuò)展節(jié)點(diǎn)展開(kāi)前后的信息損失之差，即G(a)=ILbefore-ILafter。

故本文選擇使用信息增益比最大的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。改進(jìn)的Partition算法的具體思想是：遞歸分組，直到葉子節(jié)點(diǎn)。每次遞歸中，依據(jù)信息增益比選取擴(kuò)展節(jié)點(diǎn)。然后根據(jù)層次結(jié)構(gòu)原則和擴(kuò)展節(jié)點(diǎn)來(lái)劃分?jǐn)?shù)據(jù)。每次劃分結(jié)束后，對(duì)不滿足約束要求的分組進(jìn)行調(diào)整。最終形成集值指紋桶，其中，每個(gè)桶中具有相同集值指紋的記錄條數(shù)不少于K，輸出匿名中間表DS*。偽代碼如下所示。

算法1： 改進(jìn)的Partition算法

輸入： 數(shù)據(jù)集DS， 層次結(jié)構(gòu)原則ATree，k

輸出：DS*

(1) Anonynimze(partition,k)；

(2) If partition無(wú)法繼續(xù)下鉆

(3) 將分區(qū)增加到global并返回；

(4) else

(5) 根據(jù)信息增益比選取下鉆的節(jié)點(diǎn)ENode;

(6) for(partition中的每條記錄g)do

(7) 根據(jù)ATree， 擴(kuò)展節(jié)點(diǎn)和g， 劃分?jǐn)?shù)據(jù)得到Rpartitions;

(8) end for

(9) 調(diào)整Rpartitions， 處理少于k條記錄的Rpartitions;

(10) for (Rpartitions中的每個(gè)Subpartition) do

(11) Anonynimze(Subpartition,k);

(12) end for

(13) end if

集值數(shù)據(jù)部分本來(lái)不具有泛化層次結(jié)構(gòu)，需要人為設(shè)定一個(gè)層次結(jié)構(gòu)ATree，即集值屬性泛化樹(shù)。層次結(jié)構(gòu)原則不同，匿名后的結(jié)果不同，此處本文根據(jù)給定的隱私要求確定集值屬性泛化樹(shù)的扇區(qū)f，扇區(qū)f決定了在集值屬性泛化樹(shù)中多少節(jié)點(diǎn)從該層推廣到父節(jié)點(diǎn)層次。數(shù)據(jù)隱私要求高，樹(shù)得層次高，扇區(qū)小，數(shù)據(jù)隱私要求低，樹(shù)層次低，扇區(qū)大。在表4中展示了使用改進(jìn)后的partition算法將表3中的集值數(shù)據(jù)K-匿名后的效果。

表4 集值數(shù)據(jù)K-匿名

2.3 關(guān)系-集值數(shù)據(jù)L-多樣性

通過(guò)改進(jìn)后的partition算法對(duì)集值數(shù)據(jù)的處理，得到了中間數(shù)據(jù)集DS*，滿足了(K,L)-多樣性的一個(gè)約束。接下來(lái)實(shí)現(xiàn)對(duì)等價(jià)類(lèi)的約束。基于Hilb算法，引入敏感度和敏感距離，提出了改進(jìn)的Hilb算法。通過(guò)敏感度和敏感距離，使得在建立分組G時(shí)敏感屬性分布更合理，對(duì)數(shù)據(jù)進(jìn)行更好的保護(hù)。

參考文獻(xiàn)[18]，使用逆文檔頻率的思想來(lái)衡量集值指紋的敏感度。逆文檔頻率是指在數(shù)據(jù)集中出現(xiàn)頻率高的屬性值的敏感程度，要比出現(xiàn)頻率低的屬性值的敏感度低。本文將集值指紋的敏感度定義為

SV_sensitivity(h[i])=log(N/Num(h[i]))

(1)

其中，Num(h[i]) 為數(shù)據(jù)集DS*中集值指紋值為h[i]的記錄的條數(shù)，N為數(shù)據(jù)集DS*中所有記錄的條數(shù)。進(jìn)一步，本文對(duì)不同記錄之間的敏感度距離進(jìn)行定義

SV_distance(Ri,Rj)=|SV_sensitivity(h[i])-SV_sensitivity(h[j])|

(2)

其中，SV_sensitivity(h[i]) 和分別是記錄Ri和Rj的集值指紋的敏感度。

改進(jìn)后的Hilb算法的具體思想是，根據(jù)敏感屬性的敏感度值，按照貪心和回退的原則建立初始分組。然后通過(guò)敏感度距離，優(yōu)化剩余記錄的分配，最后得到匿名表D*。偽代碼如下：

算法2： 改進(jìn)的Hilb算法偽代碼

輸入： 中間數(shù)據(jù)集DS*，l

輸出： 匿名表D*

(1) 計(jì)算DS*每個(gè)集值指紋的敏感度并將記錄的準(zhǔn)標(biāo)識(shí)符映射到一維;

(2) while(DS*中非空桶的數(shù)量>l)

(3) 取出每個(gè)桶內(nèi)OID最小的元組放入集合F中， 按集值指紋的敏感度進(jìn)行排序,將數(shù)據(jù)集規(guī)模|DS*|賦值給計(jì)數(shù)器Num， 將l值賦給計(jì)數(shù)器count;

(4) while(Num>0)

(5) do

(6) 初始化一個(gè)空組Gi， 將集合F中集值指紋敏感度值最小的記錄放到組Gi中;

(7) count++;

(8) 直到滿足等價(jià)類(lèi)要求或者count>m

(9) If沒(méi)有滿足等價(jià)類(lèi)要求

(10) 令count=l;

(11) do

(12) 將集合F中最后一個(gè)記錄放到組Gi中;

(13) 直到滿足等價(jià)類(lèi)要求

(14) end if

(15) Num=Num-count+1;

(16) i++;

(17) end whie

(18) end while

//分配剩余的記錄

(19) for(每個(gè)桶中剩余的記錄)

(20) 將記錄按照敏感度， 將記錄分配到敏感度距離最大的組G中;

(21) end for

(22) 泛化組Gi

PAHI方法最后一步，使用改進(jìn)后的Hilb算法實(shí)現(xiàn)關(guān)系數(shù)據(jù)的L-多樣性，輸出最后結(jié)果，見(jiàn)表5。

表5 關(guān)系數(shù)據(jù)L-多樣性

2.4 K和L閾值的計(jì)算方法

通常的匿名算法中，K和L的值都是人為指定的，在這里本文引入辨別度度量標(biāo)準(zhǔn)(discernability metric，CDM)和信息熵，根據(jù)給定的隱私泄露閾值，分別來(lái)確定K和L的閾值，提高算法的實(shí)用性，更有利于數(shù)據(jù)的保護(hù)以及數(shù)據(jù)質(zhì)量的保證。

2.4.1K的閾值

根據(jù)(K,L)-多樣性模型的約束條件，匿名后集值指紋桶中記錄的條數(shù)不少于K，即參數(shù)K的決定著匿名后集值指紋桶的大小。K值越大，集值指紋桶越大，泛化的范圍也越大，匿名后集值數(shù)據(jù)的質(zhì)量越差，但是數(shù)據(jù)的安全性高。K值越小，集值指紋桶越小，需要匿名的集值數(shù)據(jù)越少，匿名后數(shù)據(jù)的可用性高，不可避免地是數(shù)據(jù)的安全性低。所以需要權(quán)衡數(shù)據(jù)的安全性和可用性，來(lái)確定K的閾值。

本文參考文獻(xiàn)[18]，引入了辨別度識(shí)別度量標(biāo)準(zhǔn)來(lái)確定K的閾值。辨別度度量標(biāo)準(zhǔn)可反映匿名后數(shù)據(jù)集中集值指紋桶的規(guī)模和分布情況。辨別度度量標(biāo)準(zhǔn)定義為

(3)

2.4.2L的閾值

根據(jù)(K,L)-多樣性模型的約束條件，匿名后數(shù)據(jù)集D*中每個(gè)EC中，至少有L(L≥2)個(gè)不同的集值指紋。L值越小，等價(jià)類(lèi)中集值指紋的個(gè)數(shù)越少，抵抗同質(zhì)攻擊和背景攻擊的能力弱，但是數(shù)據(jù)的質(zhì)量高。L值越大，等價(jià)類(lèi)中集值指紋個(gè)數(shù)越多，數(shù)據(jù)的安全性高，但是數(shù)據(jù)缺損會(huì)增加。同樣，權(quán)衡數(shù)據(jù)的安全性和可用性，來(lái)確定L的閾值。

屬性的信息熵可以反映出屬性值分布的不確定性。敏感屬性的信息熵越大，則在同一等價(jià)類(lèi)中，敏感屬性值的分布越平均，數(shù)據(jù)泄露的難度越大。在數(shù)據(jù)集DS*中，集值指紋S為所有集值指紋中出現(xiàn)頻率最高的指紋，根據(jù)文獻(xiàn)[19]中信息熵與L的關(guān)系，計(jì)算信息熵的公式為

(4)

其中，p(Ei,S) 為在每個(gè)等價(jià)類(lèi)ECi中，集值指紋S出現(xiàn)的頻率, 其中t為DM中等價(jià)類(lèi)的個(gè)數(shù)。通過(guò)推導(dǎo)得到

(5)

2.5 算法安全性分析

本方法對(duì)多元組數(shù)據(jù)轉(zhuǎn)換處理，避免了同一準(zhǔn)標(biāo)識(shí)符匿名不一致的情況，為后續(xù)準(zhǔn)標(biāo)識(shí)符的統(tǒng)一泛化奠定了基礎(chǔ)，減少了信息泄露的風(fēng)險(xiǎn)。并且采用了(K,L)-多樣性模型，攻擊者通過(guò)集值數(shù)據(jù)唯一識(shí)別數(shù)據(jù)集DM中任意用戶的信息的概率不高于1/K，通過(guò)關(guān)系數(shù)據(jù)唯一識(shí)別數(shù)據(jù)集DM中任意用戶的信息的概率不高于1/L。因此，通過(guò)在集值數(shù)據(jù)上的K-匿名約束和關(guān)系數(shù)據(jù)的L-多樣性約束來(lái)保證了數(shù)據(jù)集中用戶數(shù)據(jù)不被泄露，用戶的隱私得到了保護(hù)。所以，本文的方法在3個(gè)基本環(huán)節(jié)上能夠保證脫敏后數(shù)據(jù)的安全性。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境及設(shè)置

本次實(shí)驗(yàn)采用了民航旅客訂座數(shù)據(jù)集PNR(passengers name record)，它反映了旅客的航程，航班座位占用的數(shù)量及旅客信息，共48 288條記錄。在某一時(shí)間范圍內(nèi)，同一個(gè)旅客存在有多條訂座記錄的情況，所以PNR數(shù)據(jù)集為多元組關(guān)系-集值數(shù)據(jù)集。選取數(shù)據(jù)集的6個(gè)屬性{年齡，性別，旅客標(biāo)志，郵編，代理人代碼，航班號(hào)}作為實(shí)驗(yàn)對(duì)象，其中年齡是有序?qū)傩?，其它屬性均為無(wú)序?qū)傩?。?shí)驗(yàn)中，選取{年齡，性別，旅客標(biāo)志，郵編，代理人代碼}作為關(guān)系屬性，{航班號(hào)}作為集值屬性。

本實(shí)驗(yàn)將本文所提的PAHI方法與文獻(xiàn)[16]中所提的1M-Generalization算法從信息損失和效率兩方面進(jìn)行比較分析。實(shí)驗(yàn)編程語(yǔ)言為Python 2.7，在 Intel-Core i5-4590 CPU 3.30 GHz 處理器上進(jìn)行，內(nèi)存為8.0 G，使用64位Windows10操作系統(tǒng)。

通過(guò)計(jì)算閾值，設(shè)置K和L的默認(rèn)值分別為10和5。實(shí)驗(yàn)分為4組，3組對(duì)比實(shí)驗(yàn)和一組PAHI方法自身測(cè)試。實(shí)驗(yàn)設(shè)置見(jiàn)表6。

表6 實(shí)驗(yàn)變量設(shè)置

3.2 實(shí)驗(yàn)指標(biāo)

本次實(shí)驗(yàn)從信息損失和執(zhí)行時(shí)間兩方面對(duì)算法進(jìn)行對(duì)比分析。其中算法效率的評(píng)價(jià)指標(biāo)采用算法執(zhí)行時(shí)間。

信息損失的評(píng)價(jià)指標(biāo)，即數(shù)據(jù)可用性的評(píng)價(jià)指標(biāo)。采用匿名化技術(shù)來(lái)脫敏數(shù)據(jù)，會(huì)造成信息損失，信息損失越小，數(shù)據(jù)可用性越高。所以，匿名化的目標(biāo)是找到滿足匿名模型約束的最優(yōu)轉(zhuǎn)換，同時(shí)最小化信息損失，以達(dá)到保證數(shù)據(jù)可用性的目的。因此，需要一個(gè)度量標(biāo)準(zhǔn)來(lái)衡量匿名數(shù)據(jù)的信息損失。早期的信息損失度量函數(shù)有分類(lèi)度量和差別度量，前者對(duì)信息損失的計(jì)算主要基于元組之間的關(guān)系，不適合應(yīng)用到通用程序中；后者主要是度量等價(jià)類(lèi)的基數(shù)，不適合整個(gè)數(shù)集的計(jì)算?，F(xiàn)在，又有學(xué)者提出廣義損失度量[20],歸一化確定懲罰(NCP)[20]和全局確定懲罰(GCP)[21]。根據(jù)本文的算法特點(diǎn)，選用GCP作為信息損失度量標(biāo)準(zhǔn)，對(duì)GCP定義如下：

設(shè)數(shù)據(jù)集D*為多元組數(shù)據(jù)集DM脫敏后得到的匿名數(shù)據(jù)集，其中H是D*的一個(gè)屬性，g是D*中的一條記錄，g[i]是記錄g對(duì)應(yīng)屬性H的一個(gè)值，則g[i]的信息損失為

(6)

|ugi| 是g[i]泛化范圍，若g[i]是數(shù)值型，則 |ugi| 對(duì)應(yīng)的是一個(gè)區(qū)間長(zhǎng)度，若g[i]是離散型，則 |ugi| 對(duì)應(yīng)的是g[i]所在的泛化子樹(shù)對(duì)應(yīng)的葉子節(jié)點(diǎn)的數(shù)量。 |H| 代表屬性H泛化的范圍。

記錄g的信息損失為

(7)

d為D*所有屬性的維數(shù)，wj是第j個(gè)屬性對(duì)應(yīng)的權(quán)重，本文按照每個(gè)屬性的屬性值的數(shù)量分配權(quán)重，屬性值多的屬性權(quán)重大。所以，D*的全局確定懲罰可以定義為

(8)

其中，N為D*中所有記錄的總數(shù)。GCP取值越小表示信息損失越小，即脫敏后數(shù)據(jù)的有用性越高。

3.3 信息損失分析

固定L=5，圖2(a)中給出了隨著K值變化，兩種算法的GCP的變化?？梢园l(fā)現(xiàn)，隨著K值的變大，1M-Generalization算法和PAHI算法的GCP均隨之線性增大。這是由于對(duì)集值指紋K-匿名的時(shí)候，當(dāng)K值變大，要使得更多的集值指紋保持相同的值，不可避免地造成一定的信息損失。但是PAHI算法的GCP整體低于1M-Generalization算法。因?yàn)镻AHI算法在對(duì)集值指紋K-匿名的時(shí)候，對(duì)partition算法優(yōu)化了選取擴(kuò)展節(jié)點(diǎn)的規(guī)則，使得數(shù)據(jù)的缺損保持較低的水平。

圖2 對(duì)比實(shí)驗(yàn)的信息損失度量分析

固定K=10，圖2(b)中展示了兩種算法對(duì)于不同的L值，GCP的相應(yīng)變化。隨著L值的增大，兩個(gè)算法的信息損失也隨著增大。這是因?yàn)椋S著L值增大，相應(yīng)的建立的等價(jià)類(lèi)的規(guī)模也變大，匿名準(zhǔn)標(biāo)識(shí)符會(huì)帶來(lái)一定的信息損失。但是PAHI算法表現(xiàn)得比1M-Generalization算法好。在實(shí)現(xiàn)關(guān)系集值數(shù)據(jù)的L-多樣性時(shí)，PAHI算法根據(jù)敏感度距離對(duì)剩余元組進(jìn)行分配，使其分組更加合理，信息損失相對(duì)較少。

為了測(cè)試使用兩個(gè)算法脫敏后，數(shù)據(jù)的質(zhì)量是否受到數(shù)據(jù)集規(guī)模的影響，實(shí)驗(yàn)固定K=10,L=5,N以5000條記錄為單位進(jìn)行變化。圖2(c)中，改變數(shù)據(jù)集的規(guī)模，對(duì)算法進(jìn)行測(cè)試。N為數(shù)據(jù)集的規(guī)模，隨著N的增大，算法的信息損失會(huì)有所下降，這是因?yàn)椋S著數(shù)據(jù)集的增大，會(huì)更加容易滿足(K，L)-多樣性約束，所以GCP會(huì)隨之降低。并且，PAHI采用的基礎(chǔ)算法Hilb，在信息損失方面會(huì)優(yōu)于1M-Generalization的基礎(chǔ)算法Mondrian，所以，使得PAHI算法的GCP低于1M-Generalization算法。

針對(duì)PAHI算法，測(cè)試不同的K、L值對(duì)GCP的影響。在圖3中可以看出，K值和L值對(duì)GCP都有影響，并呈正相關(guān)。隨著K值變大，GCP不斷地變大。隨著L值變大，GCP也不斷地變大。

圖3 PAHI中K和L對(duì)GCP的影響

從圖2中我們可以看到，PAHI算法的信息損失低于1M-Generalization算法，即PAHI算法脫敏后的數(shù)據(jù)的可用性高。

3.4 效率分析

接下來(lái)，將從算法執(zhí)行時(shí)間方面對(duì)算法進(jìn)行測(cè)試。如圖4(a)所示，兩個(gè)算法隨著K值的增大，運(yùn)行時(shí)間都會(huì)縮短。這是由于隨著K值的變大，形成集值指紋桶的過(guò)程中分割次數(shù)會(huì)減少。兩個(gè)算法的執(zhí)行時(shí)間類(lèi)似。在圖4(b)中，展示了L值對(duì)兩個(gè)算法運(yùn)行時(shí)間的影響。隨著L值的增大，兩個(gè)算法的執(zhí)行時(shí)間變化微弱。但是，1M-Generalization算法保持在25 s左右，PAHI算法保持在20 s左右。因?yàn)樵谀涿P(guān)系數(shù)據(jù)時(shí)，PAHI方法采用的比Mondrain更高效的Hilb算法。在圖4(c)中，PAHI算法的運(yùn)行時(shí)間隨著數(shù)據(jù)集規(guī)模的增大線性增加。因?yàn)殡S著數(shù)據(jù)規(guī)模的增大，在集值指紋事務(wù)桶的規(guī)模和等價(jià)類(lèi)的規(guī)模都會(huì)變大，所以執(zhí)行時(shí)間也會(huì)相應(yīng)的增加。

圖4 對(duì)比實(shí)驗(yàn)的時(shí)間效率分析

所以，從圖4中我們可以看到，PAHI算法的運(yùn)行效率高于1M-Generalization算法。

針對(duì)PAHI算法，測(cè)試不同的K、L值對(duì)算法執(zhí)行時(shí)間的影響。在圖5中,可以看出，K值對(duì)算法執(zhí)行時(shí)間有明顯的影響，而L值對(duì)算法運(yùn)行時(shí)間的影響微弱。

圖5 PAHI中K和L同時(shí)對(duì)時(shí)間開(kāi)銷(xiāo)的影響

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

對(duì)于脫敏待發(fā)布的多元組關(guān)系-集值數(shù)據(jù)存在的脫敏后數(shù)據(jù)的信息缺損高以及可能產(chǎn)生信息泄露的問(wèn)題，本文基于(K,L)-多樣性模型，提出了一種適合多元組關(guān)系-集值數(shù)據(jù)的脫敏方法，來(lái)保證脫敏后數(shù)據(jù)的安全性和可用性。對(duì)比現(xiàn)有的方法，實(shí)驗(yàn)結(jié)果表明，PAHI方法降低了信息缺損，即提高了數(shù)據(jù)的可用性；在時(shí)間開(kāi)銷(xiāo)方面，PAHI方法算法執(zhí)行時(shí)間較低，占有一定的優(yōu)勢(shì)。綜上驗(yàn)證了基于(K,L)-多樣性的多元組關(guān)系-集值數(shù)據(jù)的脫敏方法的可行性。

另外，該方法主要針對(duì)考單個(gè)敏感屬性情況下，多元組關(guān)系-集值數(shù)據(jù)的脫敏問(wèn)題。因此，多個(gè)敏感屬性的脫敏方法將是筆者下一步研究的重點(diǎn)。