楊高明，方賢進(jìn)，陸 奎，王 靜

（1.安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南232001；2.中國民航大學(xué)中國民航信息技術(shù)科研基地，天津300300）

1 引言

信息技術(shù)的發(fā)展使企業(yè)更容易收集到大量的個(gè)人隱私數(shù)據(jù)。為更好地服務(wù)社會(huì)，需要發(fā)布這些數(shù)據(jù)或者由第三方數(shù)據(jù)處理公司處理這些數(shù)據(jù)。如果原始數(shù)據(jù)不經(jīng)處理就直接發(fā)布，將不可避免地導(dǎo)致用戶隱私泄露［1，2］，因此，近幾年隱私保護(hù)的數(shù)據(jù)發(fā)布受到越來越多的研究者關(guān)注。如果數(shù)據(jù)發(fā)布者僅僅移除用戶的標(biāo)識(shí)信息，如身份證號(hào)碼、姓名等，這并不能有效地阻止用戶的隱私泄露。攻擊者可以使用準(zhǔn)標(biāo)識(shí)符屬性（QI），如生日、性別、郵政編碼等識(shí)別出用戶的具體信息。

為保護(hù)用戶的隱私信息，Sweeney L 等［3］提出了k－匿名的隱私保護(hù)數(shù)據(jù)發(fā)布模型，該匿名化模型要求每個(gè)匿名化組內(nèi)包含至少k個(gè)元組，且該匿名化組的所有準(zhǔn)標(biāo)識(shí)符屬性有相同的屬性值。由于k－匿名模型只能抵御記錄連接（Record Linkage）攻擊，而不能抵御同質(zhì)攻擊（Homogeneity Attack），因此，Machanavajjhala A 等［4］提出l－多樣性模型解決這個(gè)問題。除了k－匿名和l－多樣性，還有許多其他的隱私保護(hù)模型，如t－逼近［5］、（α，k）－匿名［6］、差分隱私保護(hù)［7］等。所有這些隱私保護(hù)模型假設(shè)攻擊者具有不同的背景知識(shí)，然而僅僅有部分工作關(guān)注數(shù)據(jù)集中存在數(shù)據(jù)關(guān)聯(lián)而導(dǎo)致的隱私泄露［8］。例如，Martin D J等［8］研究元組之間存在關(guān)聯(lián)而導(dǎo)致的隱私泄露。他們?cè)谘芯恐邪l(fā)現(xiàn)，如果元組之間存在關(guān)聯(lián)，一定會(huì)導(dǎo)致發(fā)布的數(shù)據(jù)隱私泄露。Kifer D 等［9］的研究顯示攻擊者可以使用交互的方法引入關(guān)聯(lián)，從而使數(shù)據(jù)集面臨攻擊時(shí)異常脆弱。在隱私保護(hù)的數(shù)據(jù)發(fā)布領(lǐng)域，文獻(xiàn)［10］考慮存在函數(shù)依賴時(shí)如何保護(hù)用戶隱私，但是他們的方法僅僅考慮如何把敏感屬性劃分為組，而沒有涉及到如何把準(zhǔn)標(biāo)識(shí)符屬性匿名化。為有效地保護(hù)用戶隱私，本文研究數(shù)據(jù)集中存在函數(shù)依賴時(shí)隱私保護(hù)的數(shù)據(jù)發(fā)布問題，同時(shí)結(jié)合了數(shù)據(jù)擾動(dòng)和劃分的方法。

2 背景知識(shí)

本部分首先引入函數(shù)依賴的概念，給出基于函數(shù)依賴的攻擊模型以及數(shù)據(jù)擾動(dòng)的基本方法，然后給出基于函數(shù)依賴的（l，α）－多樣性隱私保護(hù)模型。

2.1 函數(shù)依賴

函數(shù)依賴FDs（Functional Dependencies）在數(shù)據(jù)庫領(lǐng)域被廣泛研究，它是設(shè)計(jì)關(guān)聯(lián)數(shù)據(jù)庫的最基本概念和基礎(chǔ)。假設(shè)X和Y是關(guān)聯(lián)數(shù)據(jù)庫中的屬性集合，X和Y之間的函數(shù)依賴關(guān)系表示為X→Y，它指定了數(shù)據(jù)集之間的一致性要求。如果關(guān)系R的兩個(gè)元組擁有同樣的X屬性值，則存在函數(shù)依賴時(shí)，它們一定有相同的Y屬性值。當(dāng)這個(gè)要求滿足的時(shí)候，我們就說關(guān)系R中存在函數(shù)依賴關(guān)系。對(duì)于函數(shù)依賴X→Y來說，屬性集X稱為確定性屬性，屬性集Y稱為依賴屬性，相應(yīng)地，它們的值分別稱為確定性屬性值和依賴性屬性值。

2.2 基于函數(shù)依賴的敵對(duì)攻擊

為預(yù)防 同 質(zhì) 攻 擊，Machanavajjhala A 等［4］提出了強(qiáng)健的l－多樣性模型，這個(gè)模型要求每個(gè)準(zhǔn)標(biāo)識(shí)符組（QI－group）至少有l(wèi)個(gè)不同的敏感屬性值。其他的很多模型基本上都是在l－多樣性的基礎(chǔ)上演化而來，這些具有相同理論基礎(chǔ)的l－多樣性簇，在面臨數(shù)據(jù)集存在函數(shù)依賴的時(shí)候，并不能有效地阻止隱私泄露。下面我們將論述數(shù)據(jù)集中存在函數(shù)依賴時(shí)，如何導(dǎo)致l－多樣性失效。

Table 1 Original data table表1 原始數(shù)據(jù)表

Table 2 Anonymized data table表2 匿名化數(shù)據(jù)表

如果不同的QI組共享某些準(zhǔn)標(biāo)識(shí)符屬性值或者敏感屬性值，隱私就會(huì)泄露。例如：準(zhǔn)標(biāo)識(shí)符組G1和G2包含敏感屬性值x∈X，此處X是函數(shù)依賴F：X→Y的確定性值，如表1 中電話號(hào)碼86518665。假設(shè)y∈Y，如表1 中的郵政編碼232921，是原始數(shù)據(jù)集中x∈X相應(yīng)的依賴屬性。如果y∈Y在組G1中被概化為，在組G2中被概化為。如表1中的郵政編碼被概化為232＊＊＊和232＊＊，如表2 所示，而在組G1和G2中x∈X并沒有被概化。那么攻擊者可以很容易的推導(dǎo)出和一定有相同的原始數(shù)據(jù)值，因此他們求解和的交集，可以很容易得到更為確定的值。下面就y∈Y的不同情況予以討論。

（1）如果y∈Y是數(shù)值屬性，和是兩個(gè)區(qū)間，假設(shè)y′1的區(qū)間是［l1，u1］，的區(qū)間是［l2，u2］。如果這兩個(gè)區(qū)間相交，則min（u1，u2）］，否則

（2）如果y∈Y是分類（Categorical）屬性，我們用TaxoTree 表示屬性Y的分類樹（Taxonomy Tree）。假設(shè)N1和N2是y1和y2在分類樹TaxoTree上所對(duì)應(yīng)的節(jié)點(diǎn)。那么N1和N2就是y的概化節(jié)點(diǎn)，它們一定處于葉節(jié)點(diǎn)y和根節(jié)點(diǎn)Null的路徑上。因此，將返回分類樹上節(jié)點(diǎn)N1和N2中較小的一個(gè)。

需要注意的是y′1和y′2是由相同的屬性值y概化而來的，因此概化分類樹上一定存在由葉節(jié)點(diǎn)y到根節(jié)點(diǎn)Null的路徑，所以一定會(huì)返回一個(gè)非空的結(jié)果。而攻擊者就可以使用更具體的來代替和。由于每個(gè)準(zhǔn)標(biāo)識(shí)符組具有相同的屬性值，我們可以使用G［A］表示準(zhǔn)標(biāo)識(shí)符組G的概化值。

定義1（基于函數(shù)依賴的準(zhǔn)標(biāo)識(shí)符組交、差運(yùn)算） 設(shè)給定數(shù)據(jù)集DS中存在函數(shù)依賴F：X→Y，匿名化準(zhǔn)標(biāo)識(shí)符組分別為G1和G2，若IG＝｛t｜t1∈G1∧t2∈G2s.t.t1［X］＝t2［X］｝，則G1∩G2為元組IG的集合，即每一個(gè)元組t∈IG，存在至少一個(gè)元組t′∈IG，且滿足：

（1）對(duì)每個(gè)元組x∈X，t′［X］＝t［X］；

（2）對(duì)每個(gè)y∈Y：

進(jìn)一步來說，對(duì)于存在函數(shù)依賴關(guān)系的準(zhǔn)標(biāo)識(shí)符組G1和G2的差，有G1－G2＝G1－G12，其中G12是組G1與組G2的交集。

定義2（（l，α）－多樣性） 給定數(shù)據(jù)集DS以及它的匿名化版本DS′，如果對(duì)任意元組t∈DS′，它所在的準(zhǔn)標(biāo)識(shí)符組G包含至少l個(gè)不同的敏感值，且每個(gè)敏感值所占的比率為α，此處α∈［αmin，αmax］，αmin是隱私保護(hù)度的最小值，αmax是隱私保護(hù)度的最大值，這時(shí)我們稱數(shù)據(jù)集DS′滿足（l，α）－多樣性。

在很多情況下，數(shù)據(jù)集中都存在函數(shù)依賴關(guān)系。如果在匿名化時(shí)僅考慮使用概化值取代具體值，而不考慮數(shù)據(jù)集中存在的函數(shù)依賴，通常會(huì)導(dǎo)致隱私泄露。定義3正式定義基于函數(shù)依賴的隱私攻擊模型。

定義3（基于函數(shù)依賴的隱私攻擊） 給定數(shù)據(jù)集DS，DS′是與之對(duì)應(yīng)的滿足（l，α）－多樣性的匿名化版本。如果存在兩個(gè)準(zhǔn)標(biāo)識(shí)符屬性組G1，G2∈DS′，至少下面兩個(gè)條件：G1∩G2、G1－G2是非空集且不滿足（l，α）－多樣性，則函數(shù)依賴F：X→Y（X?QI，Y?QI∪S）可以很容易受到基于函數(shù)依賴的隱私攻擊。否則，我們稱數(shù)據(jù)集DS′在函數(shù)依賴F：X→Y（X?QI，Y?QI∪S）存在的情況下是安全的。

3 匿名化數(shù)據(jù)發(fā)布的基本模型

本節(jié)首先給出隱私保護(hù)算法中用到的數(shù)據(jù)擾動(dòng)方法，接著給出匿名化的具體方法。

3.1 數(shù)據(jù)擾動(dòng)

對(duì)于實(shí)現(xiàn)匿名化的技術(shù)而言，由于采用隱匿的方法需要改變所有元組的屬性到最大化模糊狀態(tài)，因此信息損失大，此處采用概化和擾動(dòng)結(jié)合的方法以降低信息損失。當(dāng)構(gòu)造匿名化組時(shí)，若某些準(zhǔn)標(biāo)識(shí)符屬性會(huì)導(dǎo)致過大的信息損失，這時(shí)采用擾動(dòng)的方法將是一個(gè)明智的選擇。采用概化和擾動(dòng)結(jié)合的方法分為兩個(gè)階段：首先要對(duì)數(shù)據(jù)集進(jìn)行計(jì)數(shù)，計(jì)算每個(gè)屬性值出現(xiàn)的比率；其次是產(chǎn)生一個(gè)隨機(jī)數(shù)，根據(jù)隨機(jī)數(shù)采用輪盤賭的方法選擇一個(gè)屬性以取代原先的屬性。由于文章篇幅所限，我們不再詳述擾動(dòng)的具體方法，有興趣的研究者可以參考文獻(xiàn)［11］。

3.2 匿名化方法

目前最流行的匿名化方法是概化/隱匿。度量匿名化導(dǎo)致的信息損失是設(shè)計(jì)匿名算法很重要的一個(gè)方面。比較常見的度量信息損失的方法是概化高度、聚集查詢精度以及差別度量。為度量信息損失，本文綜合考慮數(shù)值屬性和分類屬性，而對(duì)于分類屬性，假設(shè)每個(gè)分類屬性已經(jīng)存在分類系統(tǒng)樹。與前人工作類似，由概化/隱匿所導(dǎo)致的信息損失如下：

（1）對(duì)隱匿方法來說，元組t的信息損失為：InfoLost＝1；

（2）對(duì)概化方法來說，信息損失需要考慮兩種情況：①對(duì)數(shù)值屬性NA，設(shè)NAv是屬性NA的值，被概化為［L，U］，設(shè)Min和Max是屬性NA的屬性域的最小值和最大值，則NA的信息損失為：ILNA＝（U－L）/（Max－Min）。②對(duì)分類屬性CA，設(shè)TCA是分類系統(tǒng)樹，VCA是分類系統(tǒng)樹上的原始值，是其對(duì)應(yīng)的概化值，設(shè)N是分類系統(tǒng) 樹TCA的對(duì) 應(yīng) 的 節(jié) 點(diǎn) 葉 子 數(shù)。則VCA的 信 息損失為InfoLosCA＝（MN－1）/（M－1），此處M是分類系統(tǒng)樹TCA的全部葉節(jié)點(diǎn)數(shù)，MN是分類系統(tǒng)樹TCA上以N為節(jié)點(diǎn)的子樹葉節(jié)點(diǎn)數(shù)。

給定信息損失的定義以后，則元組t由于概化/隱匿所導(dǎo)致的信息損失為：InfoLost＝，此處m是元組t的準(zhǔn)標(biāo)識(shí)符屬性數(shù)。整個(gè)數(shù)據(jù)集的信息損失為：InfoLosDS＝（∑t∈DSInfoLost）/｜DS｜。例如：若age屬性的域范圍為［0，100］，如果概化age屬性值75到［70，80］，則其信息損失為：（80－70）/（100－0）＝0.1。

4 分組策略和匿名化算法

本節(jié)首先給出實(shí)現(xiàn)（l，α）－多樣性算法所需的基于函數(shù)依賴的分組策略，然后給出詳細(xì)的（l，α）－多樣性算法。

4.1 基于函數(shù)依賴的概化原則

實(shí)現(xiàn)（l，α）－多樣性的關(guān)鍵是把數(shù)據(jù)集合理地分組，使每一個(gè)組都滿足（l，α）－多樣性約束，另外，分組時(shí)還需要考慮數(shù)據(jù)集中存在的函數(shù)依賴關(guān)系。一般情況下，若數(shù)據(jù)集DS中存在函數(shù)依賴X→Y，X?QI，Y?QI，這時(shí)匿名化數(shù)據(jù)集時(shí)不需要考慮函數(shù)依賴，因?yàn)檫@時(shí)函數(shù)依賴是安全的。然而，若X→Y，X?QI，Y?S，在匿名化時(shí)就必須考慮函數(shù)依賴關(guān)系，即匿名化時(shí)必須切斷屬性X和Y之間的關(guān)聯(lián)。給定準(zhǔn)標(biāo)識(shí)符以后，它們構(gòu)成的分組只有兩種情況，即不相交或者重疊。為說明匿名的準(zhǔn)標(biāo)識(shí)符之間的關(guān)系，下面針對(duì)相交、不交、包含進(jìn)行討論。

4.1.1 不相交關(guān)系

準(zhǔn)標(biāo)識(shí)符組不相交意味著所有的匿名化準(zhǔn)標(biāo)識(shí)符組沒有重疊的元組。也就是說，如果數(shù)值屬性x∈A被概化為A1，A2，…，Am，則?Ai，Aj，Ai∩Aj＝?，1≤i，j≤m；對(duì)于分類屬性x∈A被概化為A1，A2，…，Am，則?Ai，Aj，不存在一條路徑包含Ai和Aj，1≤i，j≤m，此處m是分組的個(gè)數(shù)。在這種條件下，對(duì)?Ai∩Aj＝?，不會(huì)有隱私泄露。如果任意的匿名化組Ai、Aj不相交，存在函數(shù)依賴X→Y，x∈X?QI，y∈Y?QI，有Ai→Aj，此處Ai、Aj分別是x和y的概化域。

4.1.2 包含關(guān)系

準(zhǔn)標(biāo)識(shí)符屬性的包含關(guān)系意味著一個(gè)匿名化組的元組被另外一個(gè)匿名化組所包含。如屬性A1被概化為A11，A12，…，A1m，則存在著包含關(guān)系A(chǔ)11?A12?A13?…?A1m。在這種情況下，我們可以僅考慮A11，因?yàn)锳11是最具體的值。對(duì)于包含n個(gè)屬性匿名化元組，包含關(guān)系要求一個(gè)匿名化組包含另外一個(gè)匿名化組的所有元組。

4.1.3 相交關(guān)系

當(dāng)把準(zhǔn)標(biāo)識(shí)符屬性概化為Ai、Aj等，若存在Ai∩Aj≠?，我們就必須考慮X和S之間的關(guān)系，此處X?QI。因此，針對(duì)相交設(shè)計(jì)了處理策略，要求不同匿名化組共享l個(gè)不同的敏感值。另外，在考慮相交關(guān)系時(shí)，本文不允許出現(xiàn)多于兩個(gè)匿名化組相交，若出現(xiàn)多于兩個(gè)匿名化組相交，則它們的交集與兩個(gè)匿名化組的交集必須滿足最大重疊準(zhǔn)標(biāo)識(shí)符組。

4.2 匿名化算法

給定數(shù)據(jù)集DS，存在函數(shù)依賴F：X→Y，首先構(gòu)造桶，使每個(gè)桶包含相同的敏感屬性值。其次是構(gòu)造匿名化組，在構(gòu)造匿名化組時(shí)結(jié)合概化和數(shù)據(jù)擾動(dòng)，以降低信息損失，提高數(shù)據(jù)效用。

4.2.1 桶的構(gòu)造

桶的構(gòu)造即是把數(shù)據(jù)集劃分為小的桶，使每個(gè)桶包含一類敏感屬性值。對(duì)于給定的數(shù)據(jù)集DS，其包含不同的敏感屬性值集合為Sen｛S1，S2，…，Sn｝，則針對(duì)敏感屬性值集Sen的劃分模式為：（1）?i≠j，Si∩Sj＝?；（2）因此，在把數(shù)據(jù)集劃分為桶之后，每個(gè)元組屬于一個(gè)桶，每個(gè)桶里面具有相同的敏感屬性值。如果存在n個(gè)不同的敏感屬性值，則存在n個(gè)桶。圖1是根據(jù)敏感屬性值劃分桶的示意圖。

4.2.2 匿名化組構(gòu)造

僅僅簡單地應(yīng)用概化會(huì)導(dǎo)致大量的信息損失。為實(shí)現(xiàn)隱私保護(hù)，滿足（l，α）－多樣性，減少信息損失，需要根據(jù)每個(gè)桶的敏感屬性值以及它們之間的相似度構(gòu)造具有k個(gè)元組的準(zhǔn)標(biāo)識(shí)符組，此處k≥l，使每個(gè)組均滿足（l，α）－多樣性，直到所有的元組都屬于一個(gè)組為止。對(duì)于剩余的不能構(gòu)成準(zhǔn)標(biāo)識(shí)符組的敏感屬性值s所在的元組，有三種選擇：（1）把它刪除掉；（2）把它添加到已經(jīng)存在的匿名化組；（3）與其他剩余的每個(gè)屬性值構(gòu)成一個(gè)新的匿名化組。

Figure 1 Example of the bucket圖1 依據(jù)敏感屬性構(gòu)造分桶

對(duì)于第二種選擇，選擇這樣的準(zhǔn)標(biāo)識(shí)符組，它包含的敏感屬性最大頻度值要大于敏感值s的頻度。對(duì)于第三種情況，選擇其他與s的頻度比較接近的l－1個(gè)剩余的敏感屬性，構(gòu)成一個(gè)新的匿名化組。另外，為滿足（l，α）－多樣性，還需要考慮數(shù)據(jù)集中存在的函數(shù)依賴關(guān)系。

對(duì)于函數(shù)依賴X→Y，X?QI，Y?QI，對(duì)于這種情況，X和Y是數(shù)值屬性或者分類屬性，概化它們?yōu)閷傩蚤撝祷蛘叻诸愊到y(tǒng)樹節(jié)點(diǎn)。由于確定性屬性的發(fā)布不影響敏感屬性，因此是否概化敏感屬性就不需要考慮。

（2）對(duì)于函數(shù)依賴X→Y，Y→Z，X?QI，Y?QI，S?Sen，這種情況類似于X→Y，X?QI，Y?Sen，因此，在此處我們就不再討論。

對(duì)于劃分到一個(gè)匿名化組內(nèi)的元組，若概化時(shí)導(dǎo)致信息損失過大，必須根據(jù)前面討論的擾動(dòng)方法，對(duì)其進(jìn)行擾動(dòng)處理。在前述的基礎(chǔ)上，下面給出使用分組方法實(shí)現(xiàn)基于函數(shù)依賴的（l，α）－多樣性 算 法LDFD（the （L，α）－Diversity algorithm with Function Dependence）。

算法1 基于函數(shù)依賴的（l，α）－多樣性算法

輸入：數(shù)據(jù)集DS，多樣性約束條件l，隱私保護(hù)程度αmin和αmax，此處αmin和αmax分別是隱私保護(hù)的最小概率和最大概率；

輸出：滿足（l，α）－多樣性的數(shù)據(jù)集DS′。

步驟1 統(tǒng)計(jì)數(shù)據(jù)集的DS個(gè)數(shù)和不同敏感屬性值的個(gè)數(shù)。

步驟2 設(shè)定αmin和αmax的閾值，計(jì)算每個(gè)匿名化組的范圍（kmin，kmax），此處kmax＝l/αmin，kmin＝l/αmax。

湖北省縣市區(qū)地理國情普查圖涉及到比例尺范圍為1:15000-1:14000，比例尺跨度大，使用傳統(tǒng)的縮編手段先將1:10000數(shù)據(jù)，縮編為1:50000，然后在1:50000的基礎(chǔ)上再縮編為更小比例尺數(shù)據(jù)，耗時(shí)耗力，WJ-III地圖工作站能夠?qū)崿F(xiàn)從1:10000到1:140000逐級(jí)或跨尺度綜合與成圖，解決了從傳統(tǒng)單一比例尺制圖到多比例尺融合制圖，從單一比例尺靜態(tài)地圖顯示到多比例尺平滑動(dòng)態(tài)連續(xù)顯示技術(shù)難題，從而使多尺度空間數(shù)據(jù)能夠在PC機(jī)、掌上電腦、網(wǎng)絡(luò)上無級(jí)顯示。

步驟3 按照敏感屬性值的不同，將元組分別放入桶Bi（i＝1，2，…，m），此處m是敏感屬性值的個(gè)數(shù)。

步驟4 計(jì)算每一個(gè)QI組Ci（i＝1，2，…，m）的質(zhì)心，此處m是敏感屬性值的個(gè)數(shù)。

步驟5 選擇一個(gè)包含元組數(shù)最大的桶Bj，再由桶Bj中任意選擇一個(gè)元組t1匿名化組構(gòu)造G1，計(jì)算元組到每個(gè)桶質(zhì)心的距離。

步驟6 選擇到元組t1最近的桶Bi，計(jì)算匿名化組G1到桶Bi的距離；選擇一個(gè)到桶Bi最近的元組，并把這個(gè)元組放入桶G1，計(jì)算G1的質(zhì)心。

步驟7 如果組G1內(nèi)的元組數(shù)少于l，則需要按照步驟6把l個(gè)不同的元組放入組G1。

步驟8 如果｜DS｜＞l，轉(zhuǎn)步驟5。

步驟9 把剩余的l個(gè)元組放入距離它們最近的匿名化組Gi。

步驟10 按照4.2.1節(jié)的內(nèi)容調(diào)整匿名化組。

步驟11 計(jì)算每個(gè)匿名化組的信息損失、總信息損失、以及每個(gè)組的質(zhì)心。

步驟12 標(biāo)記最大信息損失的組，把它組內(nèi)的元組放到其他的組內(nèi)，若其他的組達(dá)到組分裂條件，則分裂這個(gè)組，然后計(jì)算總的信息損失，若總信息損失小于未標(biāo)記前的信息損失，則正式解散標(biāo)記的最大信息損失組，把其內(nèi)的元組放到其他匿名化組。

步驟13 檢查每個(gè)匿名化組，如果每個(gè)匿名化組內(nèi)的不同敏感屬性個(gè)數(shù)的比率小于αmin或者大于αmax，按照3.1節(jié)所述生成準(zhǔn)標(biāo)識(shí)符屬性。

步驟14 發(fā)布滿足（l，α）－多樣性的匿名化數(shù)據(jù)集DS′。

4.2.3 算法的復(fù)雜度分析

根據(jù)敏感屬性構(gòu)造桶的時(shí)間復(fù)雜度為O（n），此處n是不同敏感屬性值的個(gè)數(shù)。構(gòu)造匿名化組G1的復(fù)雜度為（m－1＋n/m）×l，此處m是敏感屬性值的個(gè)數(shù)。構(gòu)造匿名化組G2的復(fù)雜度為（m－1＋（n－1）/m）×l，以此類推，構(gòu)造匿名化組G［n/l］的復(fù)雜度為（m－1＋（n－n＋l）/m）×l。因此，總的復(fù)雜度為O（nlogn），此處我們假設(shè)n＞＞m，n＞＞l。在最壞情況下，若數(shù)據(jù)分布是嚴(yán)重傾斜的，構(gòu)造匿名化組G的復(fù)雜度為O（n2）。

4.3 討論

為實(shí)現(xiàn)隱私保護(hù)，概化/隱匿方法使用粗粒度的值代替細(xì)粒度的值，這無疑會(huì)降低數(shù)據(jù)效用。在極端情況下，可以導(dǎo)致數(shù)據(jù)完全失去效用。因此，本文不僅使用概化/隱匿方法，還使用擾動(dòng)的方法。采用數(shù)據(jù)擾動(dòng)的方法使原始的數(shù)據(jù)分布不發(fā)生改變，但是對(duì)于具體的值，有可能會(huì)導(dǎo)致查詢精度降低。

5 仿真和實(shí)驗(yàn)

測試實(shí)驗(yàn)使用的數(shù)據(jù)來源于Adult 數(shù)據(jù)集［12］，總共有45 222個(gè)數(shù)據(jù)記錄可用，這個(gè)數(shù)據(jù)集是隱私保護(hù)領(lǐng)域常用的數(shù)據(jù)集。此處使用其中的9個(gè)屬性，8個(gè)屬性作為準(zhǔn)標(biāo)識(shí)符屬性，1個(gè)屬性作為敏感屬性。另外，假設(shè)函數(shù)依賴為salary－class→occupation 和age→marital－status，occupation作為敏感屬性。所用算法的執(zhí)行環(huán)境是VC＋＋，Intel Core i－3，2.2GHz，2GB RAM，Windows 7操作系統(tǒng)。

（l，α）－多樣性匿名化算法以文獻(xiàn)［10］中的自頂向下的劃分分組的方法作為比較對(duì)象，為方便起見，下文把比較對(duì)象稱之為TDGA。在具體的算法中通過改變參數(shù)l、α、QI等驗(yàn)證算法的效率和有效性。

5.1 時(shí)間性能

為驗(yàn)證時(shí)間性能，首先通過該變QI屬性值的大小，存在函數(shù)依賴時(shí)與TDGA［10］比較評(píng)估時(shí)間性能。圖2是使用Adult數(shù)據(jù)集得到的結(jié)果。實(shí)驗(yàn)中參數(shù)l設(shè)置為3、5、7，參數(shù)α設(shè)置為0.2，其變動(dòng)范圍設(shè)置為［0.15，0.25］。對(duì)于不同的參數(shù)l，其構(gòu)成的匿名化組的大小也會(huì)發(fā)生相應(yīng)的變化，圖2針對(duì)不同的l值，固定設(shè)置了不同的匿名化組值，即k值的大小。

由圖2 可知，LDFD 的運(yùn)行時(shí)間比TDGA 稍微快一些。對(duì)于常量參數(shù)l和α，QI的增加會(huì)導(dǎo)致運(yùn)行時(shí)間的響應(yīng)增加，但是增加范圍有限?？傮w說來，LDFD 運(yùn)行時(shí)間較快，但是與TDGA 處于同一個(gè)數(shù)量級(jí)，在可以接受的范圍之內(nèi)。LDFD 運(yùn)行稍快是由于LDFD 采用自頂向下的方法，按照敏感屬性數(shù)構(gòu)造QI組，且采用全局編碼方式。

由這些評(píng)估結(jié)果可知，LDFD 算法的運(yùn)行時(shí)間足夠快，在實(shí)際的匿名化發(fā)布中完全可以應(yīng)用，事實(shí)上LDFD 模型可以在存在函數(shù)依賴時(shí)有效地阻止相似性攻擊以確保隱私保護(hù)度。

5.2 數(shù)據(jù)效用

此處，使用兩種度量標(biāo)準(zhǔn)測試數(shù)據(jù)效用，分別是信息損失、KL－散度。信息損失在隱私保護(hù)的數(shù)據(jù)發(fā)布是比較常見的一種度量方法，該方法有很多變種，本文采用3.2節(jié)所描述的方法。KL－散度主要用于度量查詢誤差估計(jì)，采用該度量方法主要是檢測匿名化以后查詢精度的改變情況。另外，為簡單起見，算法不執(zhí)行任何元組隱匿，則差異性度量就等于匿名化組內(nèi)元組個(gè)數(shù)的平方和數(shù)。

Figure 2 Running time of Adult dataset圖2 采用Adult數(shù)據(jù)集的運(yùn)行時(shí)間

LDFD 和TDGA 算法信息損失的度量采用Adult數(shù)據(jù)集。算法的運(yùn)行結(jié)果如圖3所示，算法的參數(shù)設(shè)置為l＝4，6，8；α＝0.25，其變化范圍為±0.05，如前面一樣，對(duì)每個(gè)不同的l值均有相應(yīng)的匿名化組k與之對(duì)應(yīng)。當(dāng)固定參數(shù)l和α，增加QI時(shí)，信息損失幾乎以指數(shù)增長。由圖3可以看出，LDFD 算法初始時(shí)產(chǎn)生的信息損失小于TDGA，隨著QI的增長，LDFD 算法優(yōu)勢就開始體現(xiàn)。這是由于更多的QI會(huì)導(dǎo)致更多的屬性參與運(yùn)算，為達(dá)到最優(yōu)化概化就會(huì)搜索更多的空間。隨著QI的增加，信息損失的增長趨勢也不是一成不變，其增長幅度也有一定的變化，這主要是由于每個(gè)屬性的域不同所致的。

Figure 3 Information loss of Adult dataset when l andαare constant，and the QIchanges圖3 固定l和α，變化QI，Adult數(shù)據(jù)集的信息損失

為檢驗(yàn)?zāi)涿瘮?shù)據(jù)集的查詢精度，使用KL－散度來度 量 數(shù) 據(jù) 效 用［13］，并 與TDGA［10］和TPP［14］相比較。圖4 是運(yùn)用Adult數(shù)據(jù)集產(chǎn)生的結(jié)果。在每一個(gè)圖中，期望發(fā)布一個(gè)連接分布QI×S能被很好估計(jì)的數(shù)據(jù)表。此處，設(shè)置敏感屬性S＝occupation。QI分別為多維屬性｛age，gender，race｝、｛age，gender，maritalstatus，race｝和｛age，education，gender，maritalstatus，race｝。每一個(gè)圖顯示一個(gè)基線，它相對(duì)于匿名化組內(nèi)所有QI屬性被隱匿的KL－散度，這時(shí)候結(jié)果表內(nèi)僅僅有一個(gè)敏感屬性。在圖4中可以看出，在l＝2，4，6，8，10，QI＝3，5，7 時(shí)，LDFD 的散度接近于TTP 的散度。同時(shí)差于TDGA 的散度。正如所期望的那樣，值l越大，（l，α）－多樣性的效用越低。在l＝8，10時(shí)，基準(zhǔn)表基本上與基線相同了。

Figure 4 KL＿divergence utility measurational圖4 KL－散度效用度量

6 結(jié)束語

本文研究了存在函數(shù)依賴時(shí)如何進(jìn)行隱私保護(hù)的數(shù)據(jù)發(fā)布問題，特別是在前人的工作基礎(chǔ)上，根據(jù)數(shù)據(jù)集所包含的函數(shù)依賴關(guān)系，提出了（l，α）－多樣性模型，并設(shè)計(jì)了魯棒的、有效的算法予以實(shí)現(xiàn)，使匿名化數(shù)據(jù)集時(shí)保持較少的信息損失。實(shí)驗(yàn)結(jié)果顯示了我們算法的有效性和效率。然而算法還有需要完善的地方，如αmin和αmax是人為設(shè)定的，缺少理論支持。另外，隱私保護(hù)的數(shù)據(jù)發(fā)布方面還有許多工作需要做，比如大數(shù)據(jù)的隱私保護(hù)問題就是一個(gè)值得研究的課題。因此，我們計(jì)劃將來開展大數(shù)據(jù)方面的隱私研究工作。

［1］ Wu Wei－min，Huang Huan－kun.A DP－DBScan clustering algorithm based on differential privacy preserving［J］.Computer Engineering ＆ Science，2015，37（4）：830－834.（in Chinese）

［2］ Srisungsittisunti B，Natwichai J.An incremental privacypreservation algorithm for the（k，e）－anonymous model［J］.Computers ＆Electrical Engineering，2015，41：126－141.

［3］ Sweeney L.Achievingk－anonymity privacy protection using generalization and suppression［J］.International Journal of Uncertainty Fuzziness and Knowledge－Based Systems，2002，10（5）：571－588.

［4］ Machanavajjhala A，Gehrke J，Kifer D，et al.l－Diversity：Privacy beyondk－anonymity［C］∥Proc of the 22nd International Conference on Data Engineering，2006：24－36.

［5］ Ninghui L，Tiancheng L，Venkatasubramanian S.t－Closeness：Privacy beyondk－anonymity andl－diversity［C］∥Proc of the 23rd International Conference on Data Engineering，2007：106－115.

［6］ Zhang Xiao－lin，Wang Ying，Li Yu－feng.A（α，k）－anonymity method based on social networks［J］.Computer Engineering ＆Science，2012，34（11）：50－54.（in Chinese）

［7］ Holohan N，Leith D J，Mason O.Differential privacy in metric spaces：Numerical，categorical and functional data under the one roof［J］.Information Sciences，2015，305：256－268.

［8］ Martin D J，Kifer D，Machanavajjhala A，et al.Worst－case background knowledge for privacy－preserving data publishing［C］∥Proc of the 23rd International Conference on Data Engineering，2007：126－135.

［9］ Kifer D.Attacks on privacy and deFinetti’s theorem［C］∥Proc of the 2009ACM SIGMOD International Conference on Management of Data，2009：127－138.

［10］ Wang H，Liu R.Privacy－preserving publishing microdata with full functional dependencies［J］.Data ＆ Knowledge Engineering，2011，70（3）：249－268.

［11］ Giannella C R，Liu K，Kargupta H.Breaching Euclidean distance－preserving data perturbation using few known inputs［J］.Data ＆ Knowledge Engineering，2013，83：93－110.

［12］ http：//archive.ics.uci.edu/ml/datasets/Adult.

［13］ Navarro－Arribas G，Torra V，Erola A，et al.Userk－anonymity for privacy preserving data mining of query logs［J］.Information Processing ＆ Management，2012，48（3）：476－487.

［14］ Xiao X，Yi K，Tao Y.The hardness and approximation algorithms forl－diversity［C］∥Proc of the 13th International Conference on Extending Database Technology：Advances in Database Technology，2010：135－146.

附中文參考文獻(xiàn)：

［1］ 吳偉民，黃煥坤.基于差分隱私保護(hù)的DP－DBScan聚類算法研究［J］.計(jì)算機(jī)工程與科學(xué)，2015，37（4）：830－834.

［6］ 張曉琳，王穎，李玉峰.基于社會(huì)網(wǎng)絡(luò)的（α，k）－匿名方法［J］.計(jì)算機(jī)工程與科學(xué)，2012，34（11）：50－54.