范曉峰 ，閆鳳 ，劉洋

（1.內(nèi)蒙古商貿(mào)職業(yè)學(xué)院，內(nèi)蒙古 呼和浩特 010070；2.內(nèi)蒙古農(nóng)業(yè)大學(xué)職業(yè)技術(shù)學(xué)院，內(nèi)蒙古 包頭 014109；3.呼和浩特職業(yè)學(xué)院，內(nèi)蒙古 呼和浩特 010050）

大數(shù)據(jù)云環(huán)境下TDS和BUG混合k-匿名化方法

范曉峰1，閆鳳2，劉洋3

（1.內(nèi)蒙古商貿(mào)職業(yè)學(xué)院，內(nèi)蒙古 呼和浩特 010070；2.內(nèi)蒙古農(nóng)業(yè)大學(xué)職業(yè)技術(shù)學(xué)院，內(nèi)蒙古 包頭 014109；3.呼和浩特職業(yè)學(xué)院，內(nèi)蒙古 呼和浩特 010050）

針對一般子樹匿名化方法處理大數(shù)據(jù)效率低和伸縮性較差的問題，提出了一種可伸縮的自下向上的泛化（BUG）方法，并在此基礎(chǔ)上，結(jié)合已有的自上向下的特化（TDS），形成一種混合方法。在提出的方法中，k-匿名作為隱私模型，TDS和BUG都是基于映射化簡開發(fā)組成，并通過云的強(qiáng)大計(jì)算能力來獲得較高的伸縮性。提出的映射化簡BUG只需在幾次泛化循環(huán)之后就可插入一個新的泛化候選，不會影響另一個泛化的信息損失?？紤]到工作負(fù)載平衡點(diǎn)K與匿名參數(shù)k的復(fù)雜關(guān)系，將映射化簡的BUG和TDS結(jié)合形成混合方法。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法的有效性，與TDS和BUG相比，混合方法的效率和可伸縮性大為提高。

云計(jì)算；子樹匿名化；大數(shù)據(jù)；泛化；特化；映射化簡

1 引言

目前，云計(jì)算和大數(shù)據(jù)[1]具有顛覆性的趨勢，對IT信息產(chǎn)業(yè)和研究領(lǐng)域都產(chǎn)生了重要影響[1,2]。云計(jì)算可以通過使用大量電腦彈性地提供大規(guī)模的計(jì)算和存儲能力，使用戶能夠在沒有大量基礎(chǔ)設(shè)施的情況下合理地配置大數(shù)據(jù)應(yīng)用。為了開發(fā)公共云平臺提供的優(yōu)勢，越來越多的大數(shù)據(jù)應(yīng)用移入云端，因此，如何保護(hù)這些數(shù)據(jù)集的隱私成為一個重要的挑戰(zhàn)，在云上分析和分享數(shù)據(jù)集之前，迫切需要處理數(shù)據(jù)隱私的問題。

對數(shù)據(jù)的隱私保護(hù)已經(jīng)獲得了廣泛的研究，并取得了一定的進(jìn)展。k-匿名[3]和I-多樣性[4]分別是測量隱私敏感信息、對抗記錄鏈接攻擊和屬性鏈接攻擊程度的兩種基本隱私模型。而一些匿名化操作可用于匿名化數(shù)據(jù)集，如抑制[5]、泛化[6]和分解[7]等，本文采用泛化來匿名化數(shù)據(jù)集。關(guān)于泛化，一般有4種：全域泛化[5]使一個屬性的所有域值泛化到分類樹的同一級上；子樹泛化[8]需要所有的子域值，但分類樹中所有的中間節(jié)點(diǎn)都沒有被泛化；多維泛化[9]在泛化域值時考慮了多個屬性；細(xì)胞泛化[10]是局部重新編碼并將相同的實(shí)例泛化到域值的不同級別中。

前3種泛化都需要全部重新編碼，而細(xì)胞泛化不需要。本文主要討論子樹泛化方法，不同于多維或細(xì)胞泛化方法，子樹泛化可以產(chǎn)生一致的匿名數(shù)據(jù)，該數(shù)據(jù)可以直接用于現(xiàn)存的數(shù)據(jù)挖掘和數(shù)據(jù)分析工具。一般有兩種方法可以實(shí)現(xiàn)子樹匿名化，即自上而下的特化（top-down specialization，TDS）和自下而上的泛化（bottom-up generalization，BUG）。迄今為止，研究者們?yōu)門DS和BUG提出了一系列的方法。

[11]提出了一種分布式的TDS方法，然而該方法主要關(guān)注其他評估的隱私保護(hù)而不是伸縮性問題。該方法仍采用信息獲得作為搜索標(biāo)準(zhǔn)，導(dǎo)致其數(shù)據(jù)效用低。

參考文獻(xiàn)[12]利用映射化簡通過TDS來實(shí)現(xiàn)大數(shù)據(jù)匿名化需要的密集型運(yùn)算。但是，自上而下的特化在k-匿名參數(shù)很小的情況下比自下而上的泛化的執(zhí)行速度還要慢。

為了研究隱私保護(hù)中的匿名化算法伸縮性和效率，參考文獻(xiàn)[13]引入多屬性支持的k-匿名方法，利用可伸縮的決策樹和采樣技術(shù)來獲得較高的伸縮性和效率。然而，該方法可以用于多維泛化方案，不能為子樹泛化。

參考文獻(xiàn)[14]提出了一種基于BUG的方法，利用索引數(shù)據(jù)結(jié)構(gòu)來提高效率，從而不能在云環(huán)境中達(dá)到較高的伸縮性和并行化。因此，如何開發(fā)帶有映射化簡的BUG算法，從而提升伸縮性和效率是一個有前途的方法，但缺少對指定的k-匿名參數(shù)的準(zhǔn)確獲得。

目前，現(xiàn)有的TDS和BUG方法分別是為了子樹泛化方案而開發(fā)。兩者都缺少對使用者指定的k-匿名參數(shù)的了解。事實(shí)上，k-匿名參數(shù)的值可以影響其性能。如果參數(shù)k較大，TDS更合適，而BUG的性能會較差；當(dāng) k較小時，情況相反。同時考慮到映射簡化廣泛應(yīng)用于各種數(shù)據(jù)處理應(yīng)用程序來增加伸縮性和效率[15]。本文針對大數(shù)據(jù)中的子樹匿名化提出了一種聯(lián)合了TDS和BUG的高度可伸縮的混合方法。當(dāng)給定一個數(shù)據(jù)集時，該方法可以通過對比使用者規(guī)定的k-匿名參數(shù)和來自數(shù)據(jù)集的閾值自動決定哪個組成進(jìn)行匿名化。本文的主要貢獻(xiàn)有3條：

· 通過自動選擇TDS和BUG，提升子樹數(shù)據(jù)匿名化

的伸縮性和效率；

·為BUG設(shè)計(jì)了一組創(chuàng)新的映射化簡任務(wù)，以一種

高度伸縮性的形式推導(dǎo)計(jì)算；

· 提出了在一次循環(huán)中執(zhí)行多個泛化操作，推進(jìn)BUG

的并行處理能力和伸縮性。

2 子樹泛化方案

本節(jié)簡要介紹子樹泛化，表1所示為一些基本符號和標(biāo)記，一個分類樹TTi的葉節(jié)點(diǎn)值是D中記錄的原本屬性值，使用QI作為準(zhǔn)標(biāo)識符。為不失一般性，本文采用k-匿名化[3]作為隱私模型，對于任意qid∈QID，QID(qid)必須為0或至少為k，以便一個準(zhǔn)標(biāo)識符不會與至少k-1個準(zhǔn)標(biāo)識符區(qū)分開。

在子樹泛化方案中，可以采用兩個操作，即BUG泛化和TDS特化。泛化操作就是在分類樹中用中親值取代域值，而特化操作是用所有的子值取代域值。泛化在形式上的表示為 gen:Child(q)→q，而特化表示為spec:q→Child(q)，其中，q∈DOMi為一個域值，集合Child(q)包含了q的所有子域值。利用匿名級的概念[3]來捕獲匿名化的程度，AL匿名化程度用域值集的矢量表示，即AL=，其中，Cuti(1≤i≤m)是 TTi的式樣。

為了選出匿名化過程中最好的操作，通過搜索標(biāo)準(zhǔn)測量候選的泛化或特化，使用信息/隱私權(quán)衡作為本文方法的搜索標(biāo)準(zhǔn)，即分別為TDS的信息增益/隱私損失（IGPL）和BUG的信息損失/隱私增益（ILPG）。

考慮到泛化gen:Child(q)→q，泛化的ILPG計(jì)算如下：

其中，IL(gen)是執(zhí)行 gen后的信息損失，PG(gen)代表隱私增益，兩者都是通過來源于數(shù)據(jù)集的統(tǒng)計(jì)信息計(jì)算得到，Rx表示可以泛化成x屬性值的原始記錄集，|Rx|是Rx中數(shù)據(jù)記錄的數(shù)量，I(Rx)是Rx的熵。IL(gen)定義如下：

表1 基本符號標(biāo)識和定義

Ad(gen)表示執(zhí)行 gen后的匿名，而 Ab(gen)是執(zhí)行 gen之前的匿名，gen的隱私增益計(jì)算如下：

映射化簡是一種可延伸的容錯數(shù)據(jù)處理結(jié)構(gòu)，具有簡易性、伸縮性和容錯性3種主要特征。映射化簡任務(wù)包含兩個原函數(shù)：map和reduce，通過鍵值對(key,value)的數(shù)據(jù)結(jié)構(gòu)定義。map函數(shù)可以表示為map:(k1,v1)→(k2,v2)，map采用(k1,v1)作為輸入，輸出另一中間鍵值(k2,v2)。這些中間的鍵會作為reduce的輸入而消耗。reduce函數(shù)在形式上可以表示為reduce:(k2,list(v2))→(k3,v3)，即 reduce采用了中間值 k2及其對應(yīng)值list(v2)作為輸入并輸出另一對(k3,v3)。通常(k3,v3)列是映射化簡獲得的結(jié)果。map和reduce函數(shù)都是用戶根據(jù)其特定應(yīng)用程序決定。

3 提出的混合泛化

本節(jié)主要描述映射化簡的自下而上泛化（MRBUG），實(shí)際的映射化簡程序包含了map和reduce函數(shù)，用一個驅(qū)動程序來協(xié)調(diào)映射化簡任務(wù)，然后提出了一種混合泛化方法。

3.1 自下而上泛化的映射化簡驅(qū)動程序

匿名化的自下而上泛化是一種循環(huán)過程，最低匿名級包括分類樹最低級別中的內(nèi)域節(jié)點(diǎn)。每一次循環(huán)包括4個主要步驟，即檢測當(dāng)前數(shù)據(jù)集是否滿足匿名要求、計(jì)算ILPG、尋找最佳的泛化以及根據(jù)選擇的最佳泛化方法泛化數(shù)據(jù)集。

本文為ILPG計(jì)算設(shè)計(jì)映射化簡任務(wù)，由于匿名級的概念是一個數(shù)據(jù)集匿名化狀態(tài)，因此不需要將數(shù)據(jù)集具體泛化到每次循環(huán)。算法1為自下而上的泛化映射化簡（BUGMR）驅(qū)動程序。

算法1 MRBUG驅(qū)動程序

輸入 數(shù)據(jù)集D，匿名級AL0，匿名參數(shù)k

輸出 最終匿名化數(shù)據(jù)集D*

（1）通過任務(wù)ILPG計(jì)算為每個關(guān)于AL0的泛化初始化搜索標(biāo)準(zhǔn)；

（2）當(dāng)?gen,Ab(gen)＜k；（3）從所有的可用泛化候選中確定可用泛化集AGSet；（4）?gen∈AGSet，將gen標(biāo)識為不活躍從而在當(dāng)下匿名級上執(zhí)行g(shù)en；

（5）如果?gen∈AGSet，?gen∈SGSet(gen)，那么 gen已經(jīng)標(biāo)識為不活躍；

（6）向NGSet中插入一個新的泛化gen New:Child(q)→q，其中，Child(q)={qi|gen:Child(qi)→qi,gen∈SGSet(gen)}

（7）移除SGSet(gen)中的所有泛化；

（8）結(jié)束條件；

（9）ALi+1←ALi；通過 ILPG計(jì)算為 ALi+1中的所有活躍泛化候選更新ILPG值；

（10）結(jié)束如果；

（11）根據(jù)ALi通過任務(wù)數(shù)據(jù)泛化將D泛化到D*

算法1的細(xì)節(jié)如下：首先，預(yù)設(shè)所有泛化的ILPG值（第1行）；第2行檢測當(dāng)下匿名化數(shù)據(jù)集是否滿足k-匿名化的需要；第3行識別表示為AGSet的可用泛化集?；旧希珹GSet包括最高ILPG值，只根據(jù)上述BUG方法的第3步最佳泛化genBest。但是本文在一次循環(huán)中執(zhí)行多次泛化，從而提高并行化和效率的程度，這將在第3.2節(jié)中詳細(xì)描述。第4行通過將其標(biāo)識為不活躍來執(zhí)行AGSet中的泛化過程。將一個泛化過程標(biāo)識為不活躍意味著在接下來的循環(huán)中將不再考慮該泛化過程，理論上在數(shù)據(jù)集上實(shí)現(xiàn)匿名化。當(dāng)SGSet(gen)中的泛化都標(biāo)識為不活躍時，將會在匿名級中插入一個新的更高級別的泛化取代不活躍的泛化（第 5～7行）。由于檢測 AGSet中的多泛化，因此很有可能產(chǎn)生多個新的泛化。第9行更新了每個活躍泛化的隱私增益，這是因?yàn)锳GSet中執(zhí)行的泛化可能會改變數(shù)據(jù)集的匿名。而且，如果已經(jīng)插入了新的泛化，那么就需要計(jì)算信息損失，即NGSet≠ 。第11行根據(jù)最終的匿名級，匿名化數(shù)據(jù)集。

第1、9行需要的ILPG估算包括訪問原始數(shù)據(jù)集和計(jì)算數(shù)據(jù)集的統(tǒng)計(jì)信息。第11行也需要處理所有數(shù)據(jù)集。本文利用映射化簡來執(zhí)行這些情況下的密集型運(yùn)算。本文設(shè)計(jì)了映射化簡任務(wù)：為完成第1、9行所需的計(jì)算，進(jìn)行ILPG估算任務(wù)，為獲得第11行中的具體匿名化，進(jìn)行數(shù)據(jù)泛化任務(wù)。

3.2 執(zhí)行泛化的并行性

一些觀察值也可以有助于設(shè)計(jì)出有效的ILPG的映射化簡任務(wù)。自下而上的泛化在幾次泛化循環(huán)之后插入一個新的泛化候選。另一個是根據(jù)式（2）泛化，不會影響另一個泛化的信息損失。根據(jù)這個觀察值，本文可以在一次循環(huán)中考慮多個泛化候選，從而提高本文提出方法的并行性。然而，執(zhí)行一次泛化可能會改變數(shù)據(jù)集的匿名，并影響每個泛化候選的隱私增益。為了確定一次循環(huán)可以同時考慮哪些候選，本文給出下列定義。

定義1 （匿名標(biāo)識符）如果|QIG(qid)|=minqid′∈QID|QIG(qid)′|，那么準(zhǔn)標(biāo)識符 qid就是一個匿名準(zhǔn)標(biāo)識符，其中，|·|表示 QI-組的大小。

具有一個匿名準(zhǔn)標(biāo)識符的QI-組的大小取決于定義1中的數(shù)據(jù)集匿名化。值得注意的是，在一個匿名級中可能具有多個匿名準(zhǔn)標(biāo)識符。AQISet表示匿名準(zhǔn)標(biāo)識符的集合。本文定義關(guān)鍵詞泛化如下。

定義 2 （關(guān)鍵的泛化)如果?q′∈Child(q),q′∈∪qid∈AQISet{qi|qi=Proji(qid),1≤i≤m}那么泛化 gen:Child(q)→q是關(guān)鍵的，其中，Proji(qid)是qid的第i個坐標(biāo)。

CGSet表示關(guān)鍵泛化的集合，即 CGSet=∪qid∈AQISet{qi|qi=Proji(qid),1≤i≤m}。 非關(guān)鍵泛化的集合表示為 NCGSet，且，根據(jù)上述定義得出：

如果一個泛化gen∈CGSet，執(zhí)行該泛化可能會改變數(shù)據(jù)集的匿名，即Ap(gen)-Ab(gen)可能會大于0。相反，如果gen∈NCGSet，Ap(gen)-Ab(gen)=0，則 PG(gen)=0。

假設(shè)所有泛化候選都根據(jù)ILPG值進(jìn)行分類，則本文可以在第一個關(guān)鍵泛化之前同時執(zhí)行所有候選而不影響匿名化的結(jié)果。為了確定在相同的循環(huán)中可以泛化哪些關(guān)鍵泛化，給出下列定義。

定義3 （競賽泛化）假設(shè)所有泛化候選根據(jù)ILPG值進(jìn)行分類。第一個關(guān)鍵泛化及其之后的持續(xù)關(guān)鍵泛化都是競賽泛化。這些一起構(gòu)成了競賽泛化的集合，表示為RGSet。

第一個關(guān)鍵泛化可以在相同的循環(huán)中明確執(zhí)行，而RGSet中的其他泛化不能，值得注意的是，執(zhí)行關(guān)鍵泛化可能會影響候選的ILPG值，因此需要強(qiáng)制更新ILPG值。為了確定RGSet中一次循環(huán)的可用關(guān)鍵泛化，算法2中給出了一個子程序。ACGSet表示合成的可用關(guān)鍵泛化集，即ACGSet中的泛化以及第一個關(guān)鍵泛化之前的泛化可以在一次循環(huán)中執(zhí)行。在該算法中，使用一個優(yōu)先序列來保持關(guān)于ILPG的泛化分類。

算法2 確認(rèn)可用泛化

輸入 RGSet，AQISet

輸出 ACGSet

（1）Queue← ，其中，Queue是關(guān)于ILPG的優(yōu)先排隊(duì)；

（2）如果 RGSet= ；

（3）Queue←gmin,gmin∈RGSet且 gmin有著最低的 ILPG;

（4）ACGSet←gmin；

（5）如果 Queue≠ ；

（6）g←Queue 且 RGSet←RGSet/{g}；

（7）Queue←∪qid∈{qid′|qid′containsgandqid′∈AQISet}{qi|qi=Proji(qid),1≤i≤m}/{g}；

（8）AQISet←AQISet/{qid|qid′contains g}；

（9）結(jié)束如果；

（10）結(jié)束如果

在將所有活躍泛化候選進(jìn)行分類并識別了關(guān)鍵泛化之后，可以獲得輸入?yún)?shù)RGSet。根據(jù)算法2中其他輸入?yún)?shù)即AQISet，來確定CGSet。因此，確定AQISet是算法2的關(guān)鍵。第3.3節(jié)給出了如何在映射化簡任務(wù)IPLG估算中確定AQISet。一旦確定AQISet，就可以輕松構(gòu)建可用泛化集 AGSet。

3.3 ILPG估算任務(wù)

IPLG估算任務(wù)負(fù)責(zé)算法1第1行中的ILPG初始化以及第9行中的ILPG更新。ILPG初始化所需要的算法和ILPG更新所需算法十分相似。算法3描述了ILPG估算中的map函數(shù)，而算法4顯示了reduce函數(shù)。在算法3和算法4中，“#”用來確定是否發(fā)出一個密鑰來計(jì)算信息增益或匿名損失?！?”用來區(qū)分一個密鑰是為了計(jì)算Ap(spec)還是Ab(spec)。

算法3 ILPG估算中的map

輸入 數(shù)據(jù)記錄(IDr,r),r∈D；匿名級，NGSet

輸出 中間鍵值對(key,count)

（1）對于 r中的每個屬性值 vi，找出其在當(dāng)下 AL中的泛化 geni。pi為 geni中的中親，且 ci是 vi本身或者 pi′的子集也是 vi′的前身；

（2）如果 geni∈NGSet，那么發(fā)出(＜pi,ci,sv＞,count)；

（3）構(gòu) 建 準(zhǔn) 標(biāo) 識 符 qid=＜q1,q2,…,qm＞ ，其 中 ，

（4）對于每個 i∈[1,m]，用 qi在 qid中的中親 pi取代qi，如果 qi=ci，產(chǎn)生結(jié)果準(zhǔn)標(biāo)識符 qid*發(fā)出 (＜qid*,pi,#＞,count)

算法3的細(xì)節(jié)：對于ILPG初始化，NGSet是關(guān)于AL0的所有初始泛化集合，對于ILPG更新，根據(jù)算法1的第6行設(shè)置。算法3的第6行根據(jù)當(dāng)前的匿名級，將一個原始記錄轉(zhuǎn)換為其匿名形式。為了計(jì)算式（2）中信息損失估算|Rd|、|(Rd,sv)|、|Rb|和|(Rb,sv)|，第 2 行向 reduce 函數(shù)發(fā)射鍵值對進(jìn)行信息損失計(jì)算，在執(zhí)行其他泛化或插入一個新的泛化時，泛化的信息損失將不會受到影響，而隱私增益則由于數(shù)據(jù)集匿名化的改變而受到影響。

算法3的第3行的目的在于在執(zhí)行一個泛化前，找出數(shù)據(jù)集的匿名，即Ab(gen)，第4行在執(zhí)行一次泛化之后發(fā)射鍵值對來獲得該匿名，即Ad(gen)。由于Ab(gen)在整體中是唯一的，本文只是反射了當(dāng)下的準(zhǔn)標(biāo)識符qid進(jìn)行統(tǒng)計(jì)。至于Ad(gen)，將發(fā)射qid的潛在匿名準(zhǔn)標(biāo)識符來計(jì)算不同活躍泛化候選的Ad(gen)。在獲得了Ad(gen)和Ab(gen)后，可以根據(jù)式（3）更新每個泛化的隱私增益。

算法4 ILPG估算中的reduce

輸入 中間鍵值對(key,list(count))

輸出 信息增益 (gen,IL(gen))和匿名(gen,Ab(gen),AQISet)，泛化的(gen,Ad(gen))

（1）對于每個 key,sum←∑count；

（2）對于每個 key，if key.sv≠#，更新統(tǒng)計(jì)計(jì)算；

（3）|(Rb,sv)|←sum，|Rb|←sum+|Rb|，|(Rd,sv)|←sum+|(Rd,sv)|，|Rd|←sum+|Rd|；

（4）如果子集c中的所有敏感值都到達(dá)，那么計(jì)算I(Rd)；

（5）如果親本p中的所有子集c都到達(dá)，那么計(jì)算I(Rd)和 IL(gen)，發(fā)射(gen,IL(gen))；

（6）對于每個 key，if key.sv≠#，更新匿名：

（7）如果 key.c=$，且 sum＜Ad(gen)那么更新當(dāng)下匿名：Ad(gen)←sum；

（8）如果 key.c≠$；

（9）如果 sum＜Ab(gen)，更新 gen 的潛在匿名：Ab(gen)←sum 和 AQISet←key.c；

（10）如果 sum=Ab(gen)，那么更新：AQISet←{key.c}∪AQISet；

（11）發(fā)射(gen,Ad(gen))且發(fā)射(gen,Ab(gen),AQISet)

算法4中描述的reduce函數(shù)主要聚合估算信息損失和隱私增益的統(tǒng)計(jì)信息。由于鍵值對在傳輸給reducer workers之前通過映射化簡內(nèi)置機(jī)制進(jìn)行分類，該reduce函數(shù)可以依次計(jì)算泛化的信息損失而不需要大量記憶來保存統(tǒng)計(jì)信息。因此，reduce函數(shù)在計(jì)算信息損失上具有很強(qiáng)的伸縮性。

計(jì)算數(shù)據(jù)集匿名的本質(zhì)特征是找出QI-組的最小值。第二部分，第6行和第11行，目的在于計(jì)算隱私增益以及確定AQISet。在并行執(zhí)行泛化的前后，reducer workers會找出局部最小QI-組大小。通過比較reducer workers的輸出可以獲得驅(qū)動程序的整體大小。在處理和構(gòu)建AQISet中會記錄具有最小組大小的QI-組的準(zhǔn)標(biāo)識符。值得注意的是，AQISet在確定下一個循環(huán)的可用泛化中起到十分重要的作用。綜上所述，ILPG估算reduce函數(shù)在信息損失和隱私增益計(jì)算中都具有較高的伸縮性。在獲得信息損失和隱私增益后就可以根據(jù)式（1）計(jì)算ILPG的值。

3.4 結(jié)合TDS和BUG

本文將自下而上泛化的映射化簡（MRBUG）和自上而下特化的映射化簡（MRTDS）[12]結(jié)合在一起，在使用者指定匿名參數(shù)k后確定使用哪個組成來匿名化數(shù)據(jù)?；旌戏椒梢宰詣咏o出系統(tǒng)參數(shù)k，如果k≥K，那么選擇MRTDS，否則選擇MRBUG。

一旦確定了工作負(fù)載平衡點(diǎn)K，混合方法就可以確定選擇哪個組成。如果k＞K，那么選擇MRTDS，這是因?yàn)镸RBUG會引發(fā)更多計(jì)算；而如果k＜K，則選擇MRBUG。算法5簡略描述如下：

算法5 混合算法

輸入 數(shù)據(jù)集D，k-匿名參數(shù)

輸出 匿名數(shù)據(jù)集

（1）如果 k≥K，那么用 MRTDS匿名化 D；

（2）否則，用MRBUG匿名化 D

找出K的精確值較為困難，這是由于K主要依賴于數(shù)據(jù)集的一些性能，如數(shù)據(jù)分配和偏態(tài)。然而并不需要獲得精確值，這是因?yàn)楫?dāng)k在K附近取值時，MRTDS和MRBUG的性能區(qū)別很小。

4 實(shí)驗(yàn)評估

4.1 實(shí)驗(yàn)設(shè)置

為了評估提出方法的效率，將其與參考文獻(xiàn)[12]中的MRTDS和MRBUG進(jìn)行比較，本文方法用Hyb表示，取混合英文單詞Hybrid的前3個字母，3種方法的執(zhí)行時間分別表示為 THyb、TTDS和 TBUG。當(dāng) k＞K 時，THyb和 TTDS相似；而當(dāng)k＜K時，THyb和TBUG相似，估計(jì)K會引發(fā)額外開支，但是這與映射化簡任務(wù)中進(jìn)行的計(jì)算相比非常微小。

實(shí)驗(yàn)在U-Cloud的云環(huán)境下進(jìn)行，U-Cloud是一種經(jīng)常測試使用的云計(jì)算環(huán)境。圖1顯示了U-Cloud的系統(tǒng)概述，在硬件和Linux操作系統(tǒng)（Ubuntu）上安裝了可以虛擬化的基礎(chǔ)設(shè)施，并提供可以統(tǒng)一計(jì)算和存儲資源的KVM虛擬化軟件[16,17]。為了創(chuàng)建虛擬化數(shù)據(jù)中心，安裝了負(fù)責(zé)虛擬化管理、資源調(diào)度、任務(wù)分配和與用戶的交互的OpenStack開源云環(huán)境。

圖1 U-Cloud的系統(tǒng)概述

所有方法都在Java和標(biāo)準(zhǔn)Hadoop MapReduce API中實(shí)現(xiàn)。Hadoop集群包含20個具有2個虛擬CPU和4 GB內(nèi)存的m1型媒介。每一輪實(shí)驗(yàn)重復(fù)20次，計(jì)算20次的均值作為測量結(jié)果。

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

本文測量了隨著匿名參數(shù)k改變的執(zhí)行時間THyb、TTDS和TBUG，數(shù)據(jù)集的大小設(shè)置為1 000 MB。該數(shù)據(jù)集包含1.1×107個數(shù)據(jù)記錄，參數(shù) α 為 0.5。

圖 2 所示為 THyb、TTDS和 TBUG隨著 k 在 0～1.1×107之間變化而發(fā)生的變化。為了表示簡潔，k用exp表示，即k=1.1×10exp，所有exp的取值范圍為 0～7。從圖 2可以看出，混合算法的執(zhí)行時間保持在一定水平之下，而MRTDS和MRBUG在k較小和較大時引發(fā)了較高的執(zhí)行時間。此外，THyb曲線的左邊部分十分靠近TBUG，而右邊部分十分靠近TTDS，這是由于混合算法利用MRTDS和MRBUG作為具體計(jì)算的組件。因此，實(shí)驗(yàn)結(jié)果表明，本文的混合算法相較于現(xiàn)有方法，能夠在不考慮k-匿名參數(shù)的情況下較大地提高了子樹匿名化的性能。

圖2 執(zhí)行時間隨著匿名參數(shù)k的改變

5 結(jié)束語

本文研究了云上大數(shù)據(jù)子樹匿名化的伸縮性問題，并提出了一種結(jié)合了自上向下的特化（TDS）和自下而上的泛化（BUG）的混合方法。該混合方法通過比較用戶指定的k-匿名參數(shù)和負(fù)載平衡點(diǎn)自動選擇兩個組件中的一個。通過一系列特意設(shè)計(jì)的MapReduce任務(wù)，實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有方法相比，本文方法極大地提高了子樹數(shù)據(jù)匿名化的伸縮性和效率。

在云環(huán)境中，由于數(shù)據(jù)集體積越來越大，數(shù)據(jù)分析、分享和挖掘中的隱私保護(hù)是一項(xiàng)具有挑戰(zhàn)性的研究課題，本文未來計(jì)劃進(jìn)一步探討伸縮性的隱私保護(hù)感知分析和大規(guī)模數(shù)據(jù)集的調(diào)集。

參考文獻(xiàn)：

[1]戚建國.基于云計(jì)算的大數(shù)據(jù)安全隱私保護(hù)的研究 [D].北京:北京郵電大學(xué),2015.QI J G.Research on security privacy protection of large data based on cloud computing[D].Beijing:Beijing University of Posts and Telecommunications,2015.

[2]康瑛石,鄭子軍.大數(shù)據(jù)整合機(jī)制與信息共享服務(wù)實(shí)現(xiàn)[J].電信科學(xué),2014,30(12):97-102.KANG Y S,ZHENG Z J.Big data integration mechanism and information sharing service realization[J].Telecommunications Science,2014,30(12):97-102.

[3]徐勇,秦小麟,楊一濤,等.一種考慮屬性權(quán)重的隱私保護(hù)數(shù)據(jù)發(fā)布方法[J].計(jì)算機(jī)研究與發(fā)展,2012,49(5):913-924.XU Y,QIN X L,YANG Y T,et al.A QI weighted-aware approach to privacy preserving publishing data set[J].Journal ofComputerResearch and Development,2012,49(5):913-924.

[4]MACHANAVAJJHALA A,GEHRKEJ,KIFER D,etal.L-diversity:privacy beyond k-anonymity[J].ACM Transactions on Knowledge Discovery from Data,2007,1(1):24-32.

[5]李明慶.一種基于抽樣確定泛化區(qū)間的K-匿名算法 [D].哈爾濱:哈爾濱工程大學(xué),2013.LI M Q.A K-anonymity algorithm based on sampling to determine the generalized interval [D].Harbin:Harbin Engineering University,2013.

[6]WANG K,FUNG B C M,YU P S.Handicapping attacker’s confidence:an alternative to k-anonymization[J].Knowledge&Information Systems,2007,11(3):345-368.

[7]TERROVITIS M,MAMOULIS N,LIAGOURIS J,et al.Privacy preservation by disassociation [J].Proceedings of the Vldb Endowment,2012,5(10):944-955.

[8]黃春梅,費(fèi)耀平,李敏,等.基于多維泛化路徑的 K-匿名算法[J].計(jì)算機(jī)工程,2009,35(2):154-156.HUANG C M,FEI Y P,LI M,et al.K-anonymity algorithm based on multi-dimensional generalization path [J]. Computer Engineering,2009,35(2):154-156.

[9]FUNG B C M,WANG K,YU P S.Anonymizing classification data for privacy preservation [J].IEEE Transactions on Knowledge&Data Engineering,2007,19(5):711-725.

[10]RAJALAKSHMI V,MALA G S A.Anonymization based on nested clustering for privacy preservation in data mining[J].Indian Journal of Computer Science&Engineering,2013,34(3):856-861.

[11]MOHAMMED N,FUNG B C M,HUNG P C K,et al.Centralized and distributed anonymization for high-dimensional healthcare data[J].ACM Transactions on Knowledge Discovery from Data,2010,4(4):885-900.

[12]ZHANG X,YANG L T,LIU C,et al.A scalable two-phase top-down specialization approach for data anonymization using MapReduce on cloud [J].IEEE Transactions on Parallel&Distributed Systems,2014,25(2):363-373.

[13]呂品,鐘珞,于文兵,等.MA-Datafly：一種支持多屬性泛化的k-匿名方法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(4):138-140.LV P,ZHONG L,YU W B,et al.MA-Datafly:k anonymity approaches forsupporting multi-attribute generalization[J].Computer Engineering and Applications, 2013, 49(4):138-140.

[14]劉盼盼.基于聚類的數(shù)據(jù)匿名發(fā)布技術(shù)研究 [D].西安:西安電子科技大學(xué),2013.LIU P P.Research on technology of data anonymous publishing based on clustering[D].Xi’an:Xidian University,2013.

[15]CUI X,ZHU P,YANG X,et al.Optimized big data K-means clustering using map reduce[J].Journal of Super Computing,2014,70(3):1249-1259.

[16]王笑帝,張?jiān)朴?劉鏑,等.云計(jì)算虛擬化安全技術(shù)研究[J].電信科學(xué),2015,31(6):1-5.WANG X D,ZHANG Y Y,LIU D,et al.Research on security of virtualization on cloud computing[J].Telecommunications Science,2015,31(6):1-5.

[17]KVM[EB/OL].(2011-04-10)[2012-02-10].http://www.linux-kvm.org/page/Main_Page.

Hybrid k-anonymity approach based on TDS and BUG under the environment of big data cloud

FAN Xiaofeng1,YAN Feng2,LIU Yang3
1.Inner Mongolia Business&Trade Vocational College,Hohhot 010070,China 2.Vocational and Technical College of Inner Mongolia Agricultural University,Baotou 014109,China 3.Hohhot Vocational College,Hohhot 010050,China

As the issue of low efficiency and poor scalability in general sub-tree anonymous method of treating big data,a bottom-up generalization(BUG)method with scalability was proposed,and on this basis,combined with the existing top-down specialization(TDS),a hybrid approach was formed.In the proposed method,k-anonymity was being as a privacy model,the compositions of TDS and BUG were developed with mapping simplification,and higher scalability through powerful cloud computing capabilities were achieved.The proposed mapping simplification BUG could insert a new candidate after several cycles of generalization,and would not affect information loss of another generalization.Given the complexity of the relationship between workload balancing point K and anonymous parameter k,mapping simplifications of BUG and TDS were combined to form a hybrid approach.Experimental results demonstrate the effectiveness of the proposed method and compared with TDS and BUG,the efficiency and scalability of hybrid method are greatly improved.

cloud computing,sub-tree anonymous,big data,generalization,specialization,mapping simplification

TP391

A

10.11959/j.issn.1000-0801.2016135

2016-03-03；

2016-04-23

范 曉 峰 （1982-），女 ，內(nèi) 蒙 古 商 貿(mào) 職 業(yè) 學(xué) 院講師，主要研究方向?yàn)榇髷?shù)據(jù)、云計(jì)算。

閆鳳（1982-），女，內(nèi)蒙古農(nóng)業(yè)大學(xué)職業(yè)技術(shù)學(xué)院講師，主要研究方向?yàn)榇髷?shù)據(jù)。

劉洋（1975-），女，呼和浩特職業(yè)學(xué)院講師，主要研究方向?yàn)榇髷?shù)據(jù)。