0 引言

    K-匿名模型被提出之后^[1-2]，國內(nèi)外學(xué)者對此進(jìn)行了大量研究,，提出了眾多K-匿名算法,。這些算法大致可以分為兩類：全域泛化算法^[3-5]和局域泛化算法^[6-10]。全域泛化算法要求待發(fā)布的數(shù)據(jù)表中準(zhǔn)標(biāo)識符屬性^[11-14]泛化到同一層級,，往往會造成較大信息損失,。局域泛化較為靈活，允許待發(fā)布數(shù)據(jù)表的屬性泛化到不同的級別,，使得匿名表具有較小的信息損失,。然而，在大數(shù)據(jù)的背景下,，局域泛化算法也面臨著挑戰(zhàn),，主要包括2個問題：(1)隨著大數(shù)據(jù)時代的數(shù)據(jù)體量越來越巨大，單個計(jì)算機(jī)難以在可接受的時間內(nèi)對數(shù)據(jù)進(jìn)行有效的局域泛化,。因此,，如何利用并行分布式計(jì)算資源進(jìn)行快速泛化^[15-16]是亟待解決的關(guān)鍵問題。(2)大多數(shù)局域泛化算法都是以犧牲時間效率來換取低信息損失量,，無法做到兩者兼顧^[17],。

    為了克服大數(shù)據(jù)背景下局域泛化的不足，本文提出在抽樣路徑局域泛化算法的基礎(chǔ)上，對其耗時較大的部分引入MapReduce技術(shù),。MapReduce是一種大型數(shù)據(jù)處理框架,，為大數(shù)據(jù)應(yīng)用提供了強(qiáng)大的計(jì)算能力^[18-19]，成功解決了在較大數(shù)據(jù)情況下局域泛化算法時間效率低的問題,，同時降低了匿名化后的數(shù)據(jù)表信息損失量,。

1 算法

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

    抽樣路徑泛化算法是一種信息損失量較小的局域泛化K-匿名算法，其思想是引入等概率抽樣的方法,，使用抽樣樣本在泛化格(generalization lattice)^[4,，20]上快速尋找一條信息損失量較小的泛化路徑，在已得到的抽樣泛化路徑上依次對源數(shù)據(jù)集中未滿足K-匿名的等價類進(jìn)行泛化,，最終得到一個高精度的K-匿名表,。

    定義1 等價類。數(shù)據(jù)表T(A₁,，A₂,，…，A_n),，在準(zhǔn)標(biāo)識符集A₁,，A₂，…,，A_j上的一個等價類是指準(zhǔn)標(biāo)識符屬性取值均相同的元組集合,。例如：表1中，ID為1,、2的兩個元組組成的集合就是一個等價類,。

    定義2 K-匿名。給定數(shù)據(jù)表T(A₁,，A₂,，…，A_n),，QI是T的準(zhǔn)標(biāo)識符集,。經(jīng)過匿名化處理后，數(shù)據(jù)表T每條元組在準(zhǔn)標(biāo)識符集屬性上至少有K-1條與其不可區(qū)分的元組,，則T滿足K-匿名,，表1為滿足2-匿名。

    定義3 抽樣泛化路徑,。以泛化格的根節(jié)點(diǎn)為起點(diǎn),，計(jì)算其子節(jié)點(diǎn)對樣本泛化后的信息損失量，將其信息損失量最小子節(jié)點(diǎn)插入路徑,，自底向上,，直至泛化格葉子節(jié)點(diǎn)。例如：圖1中是由工人類別和性別組成的一個泛化格實(shí)例，若用<W1,，S0>這個節(jié)點(diǎn)泛化樣本比<W0,，S1>泛化樣本信息損失小，則選取<W1,，S0>為路徑的第2個節(jié)點(diǎn),，以此類推，找到一條如<W0,，S0>→

<W1,，S0>→…→<W2，S1>抽樣泛化路徑,。在此路徑上對源數(shù)據(jù)表進(jìn)行局域泛化,，得到高精度的K-匿名表。

    抽樣泛化路徑算法處理的數(shù)據(jù)集信息損失量低,，尋找路徑的時間效率高,。但本文對其進(jìn)行了深入研究后發(fā)現(xiàn)，當(dāng)數(shù)據(jù)集較大時,，該算法時間效率仍然較差，如表2所示,。

    由表2可以看出,，當(dāng)k=100、數(shù)據(jù)集中元組數(shù)量分別為30 000,、60 000,、90 000時，求等價類的時間占總時長的60%以上,，且有增加的趨勢,。由此可以得出：對求等價類進(jìn)行分布式運(yùn)算，可以提高該算法的時間效率,。因此本文將MapReduce技術(shù)引入到該算法計(jì)算等價類,，具體過程如算法1所示。

    算法1：GetFrequencySet_MR(T,，args)

    輸入： 所需計(jì)算等價類集合的數(shù)據(jù)集T,、輸入輸出路徑配置args。

    輸出： 等價類集合,。

    初始化： (1)將數(shù)據(jù)集合T按行寫入Hadoop的分布式文件集群,；

    (2)進(jìn)行Hadoop集群環(huán)境配置及MapReduce任務(wù)配置。

    Map： 讀取文件中單行元組并作為鍵K,，輸出鍵值對<K,，1>；

    Reduce： (1)讀取Map過程的輸出結(jié)果<K，list<2,，3,，3，…>>,；

    (2)值相加和為V,，輸出鍵值對<K，V>,，結(jié)果寫入輸出文件夾中,。

    算法1描述了等價類在MapReduce中的分布式計(jì)算過程，其中Map函數(shù)將數(shù)據(jù)集中準(zhǔn)標(biāo)識符屬性相同的值劃分為一個等價類,，Reduce函數(shù)統(tǒng)計(jì)Map輸出的各等價類中元組的個數(shù),。

1.2 算法分析

    基于上述算法設(shè)計(jì)，把上面Map函數(shù)和Reduce函數(shù)加入到抽樣路徑泛化算法中,，優(yōu)化后的算法具體步驟如下：

    輸入：輸入表T,、準(zhǔn)標(biāo)識符集合QI、等價類約束k以及抽樣率α,。

    輸出：滿足K-匿名的數(shù)據(jù)集T″,。

    (1)尋找抽樣泛化路徑

    函數(shù)： path(QI，T′)

     /* QI為準(zhǔn)標(biāo)識符屬性集,，T′表示抽樣數(shù)據(jù)集*/

    Begin

        ①通過QI形成泛化格G,；

        ②將泛化格G的第0層節(jié)點(diǎn)n₀作為路徑P的起點(diǎn)P₀；

        ③通過泛化格找到n₁直接泛化的節(jié)點(diǎn),，計(jì)算這些節(jié)點(diǎn)泛化T′所得到的信息損失量,，選出泛化數(shù)據(jù)集T′信息損失量最小的節(jié)點(diǎn)n₂作為路徑P的第二個節(jié)點(diǎn)P₁；

        ④重復(fù)步驟②直至到達(dá)泛化格G的頂點(diǎn)n_i作為路徑的終點(diǎn)P_i得到路徑P,；

        ⑤返回路徑P,；

    End

    (2)匿名化數(shù)據(jù)表

    本文算法：

    Begin

    ① 從數(shù)據(jù)集T中以抽樣率α獲取抽樣數(shù)據(jù)集T′；

    ② P=path(QI,，T),；/*P表示所得抽樣路徑*/

    ③ T″=φ； /*T″存放泛化后的數(shù)據(jù)集*/

    ④ node=φ,，把路徑P中第i個節(jié)點(diǎn)賦值給node,，進(jìn)入以下循環(huán)：

        D=φ；

        G={基于node對數(shù)據(jù)表T進(jìn)行泛化后的數(shù)據(jù)集},；

        F=GetFrequencySet(G,，arg s)；/*F是等價類集*/

        D={根據(jù)集合F獲得泛化后滿足K-匿名的元組},；

        計(jì)算D的信息損失量,；

        T″∪D,；

    移除T中滿足K-匿名的元組；

    該優(yōu)化算法①,、②步快速尋找信息損失量較小的泛化路徑,。第④步是算法的主體部分，首先將已找到的泛化路徑P中的節(jié)點(diǎn)依次插入到node中,，使用node的泛化策略對數(shù)據(jù)集T進(jìn)行泛化,，泛化后的數(shù)據(jù)集G使用MapReduce進(jìn)行求解等價類F，然后取出F中已滿足K-匿名的等價類計(jì)算信息損失量,，對不滿足K-匿名的等價類繼續(xù)進(jìn)行泛化,，直到求出滿足K-匿名的數(shù)據(jù)表T″。由此可知,，本文算法是把求解等價類過程進(jìn)行分布式求解,，對于處理數(shù)據(jù)量大的數(shù)據(jù)集，本算法可以有效提高抽樣泛化路徑算法的時間效率,。

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

2.1 實(shí)驗(yàn)平臺（數(shù)據(jù)集,、泛化規(guī)則、抽樣比例制定）

    本文實(shí)驗(yàn)硬件平臺為一臺Cisco UCS C240 M3的虛擬化ESXi服務(wù)器上搭建Hadoop平臺的完全分布式集群,，包括1個Master節(jié)點(diǎn)和3個Slave節(jié)點(diǎn),，其硬件配置均為CPU E5-2660/2.2 GHz，內(nèi)存為4 GB,。實(shí)驗(yàn)軟件環(huán)境為：Centos 6.5,，Java 1.8.0，Hadoop版本為Hadoop-2.6.0,，遠(yuǎn)程數(shù)據(jù)庫為SQL Sever2008,。

    實(shí)驗(yàn)使用了UCI Machine Learning Repository中的Census-income數(shù)據(jù)集,，初始數(shù)據(jù)集共有199 523條記錄,，去除其中缺省值，剩余95 130條記錄,。每條記錄包含40個屬性,，選擇其中的7個屬性作為準(zhǔn)標(biāo)識符。

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

    為證明本文算法在時間效率方面的優(yōu)越性,，實(shí)驗(yàn)部分設(shè)計(jì)了與抽樣泛化路徑算法以及Incognito算法的時間對比,。同時，本文還設(shè)計(jì)了與抽樣泛化路徑算法匿名表和Incognito算法匿名表的信息損失量對比實(shí)驗(yàn),，進(jìn)一步論述了本文對抽樣泛化路徑算法引入MapReduce技術(shù)得到的優(yōu)化算法是一種時間效率高,、匿名化數(shù)據(jù)表信息損失量低的算法。其中信息損失量采用文獻(xiàn)[21]的計(jì)算方法：

    元組信息損失量（Information Loss,，IL）：

    表的信息損失量：

    定義4 抽樣尋徑時間占比(Simple Generalize Percentage,，SGP),。由抽樣數(shù)據(jù)產(chǎn)生抽樣泛化路徑所花費(fèi)的時間S_p在整個算法流程中的百分比。抽樣尋徑時間占比越大,，說明利用樣本尋找泛化路徑的時間在整個算法運(yùn)行時間中所占的比重越大,，尋徑耗時越長。假設(shè)整個算法花費(fèi)的時間為S_p,，則其計(jì)算公式為：  

    圖2,、圖3對比了不同大小的數(shù)據(jù)集在k=100、|QI|=7的環(huán)境下,，抽樣率對信息損失和抽樣尋徑時間占比的影響,，由圖可知，當(dāng)抽樣率增大時,，信息損失量沒有明顯變化,，但是抽樣路徑時間占比增加幅度較為顯著。說明當(dāng)抽樣樣本量足夠大時,，增大抽樣率對降低匿名表的信息損失量無顯著影響,，故本文以下實(shí)現(xiàn)均基于1%的抽樣率進(jìn)行，且所得實(shí)驗(yàn)數(shù)據(jù)均在實(shí)驗(yàn)運(yùn)行5次的基礎(chǔ)上取平均值,。

2.3 實(shí)驗(yàn)效果分析

    由圖4可知,，當(dāng)數(shù)據(jù)集較小時，抽樣泛化路徑算法比本文算法的時間效率略高,；而當(dāng)數(shù)據(jù)集大于50 000時,，本文算法時間效率明顯高于抽樣泛化路徑算法時間效率，隨著數(shù)據(jù)集的不斷增大,，本文算法時間優(yōu)勢更加顯著,。本文算法處理較小數(shù)據(jù)集時，MapReduce的通信開銷所占比重較大,，故此時本文算法的時間效率略差于抽樣泛化路徑算法,；而在處理較大數(shù)據(jù)集時，將MapReduce技術(shù)運(yùn)用到算法的等價類計(jì)算當(dāng)中,，有效地縮短了計(jì)算等價類的時間,。并且當(dāng)數(shù)據(jù)量增大到一定程度時，MapReduce的通信開銷可以忽略不計(jì),，此時本文算法的時間效率要遠(yuǎn)高于抽樣路徑泛化算法,。由此可知，在處理較大數(shù)據(jù)集時,，本文算法有很大優(yōu)勢,。 

    圖5為準(zhǔn)標(biāo)識符屬性個數(shù)|QI|=7(k取50，100,，150,，200,，250)時，本文算法分別與抽樣路徑算法,、Incognito算法在處理數(shù)據(jù)及求解信息損失量方面的時間對比,。圖6為準(zhǔn)標(biāo)識符屬性個數(shù)|QI|=7(k取50，100,，150,，200，250)時,，本文算法,、抽樣路徑算法和Incognito算法處理數(shù)據(jù)集的信息損失量的對比。當(dāng)k值增大時,，由圖5可知3種算法處理數(shù)據(jù)集的時間均呈下降趨勢,，而其中抽樣泛化路徑算法用時最長，本文算法用時最短,。 

    由于本文算法是對抽樣路徑泛化算法的時間優(yōu)化,，其處理數(shù)據(jù)集的信息損失量和抽樣路徑算法相同，故在圖6中表示兩種算法的信息損失量曲線重合,。由圖6可以看出相比于Incognito算法,，本文算法處理數(shù)據(jù)集的信息損失大幅度減少，所得匿名表可用性更高,。綜合圖5,、圖6可知，當(dāng)|QI|一定時,，抽樣泛化路徑算法匿名化數(shù)據(jù)集的信息損失量比Incognito算法更小,，但其所用時間比Incognito算法更長。而本文在引入MapReduce后,，時間效率大幅度提高,，其所用時間遠(yuǎn)小于Incognito算法，而該算法匿名化的數(shù)據(jù)集比Incognito算法匿名的數(shù)據(jù)集精度更高,，可用性更強(qiáng),。

    由圖7,、圖8看出,，當(dāng)值一定，|QI|變化時,，本文算法時間效率更高,，匿名表信息損失量更小，因此該算法可用性更高,。綜合以上所述,，本文對抽樣路徑算法的優(yōu)化符合之前的理論分析,，改進(jìn)后的算法對于大數(shù)據(jù)集的處理有較高的使用價值。

3 結(jié)束語

    本文主要針對大數(shù)據(jù)背景下,，如何提高K-匿名算法的時間效率及降低發(fā)布數(shù)據(jù)信息損失量的問題進(jìn)行了研究,。將MapReduce技術(shù)運(yùn)用到抽樣泛化算法中，很大程度上提高了較大數(shù)據(jù)集匿名化處理的時間效率,，同時抽樣泛化路徑算法能夠有效降低發(fā)布數(shù)據(jù)的信息損失量,。通過實(shí)驗(yàn)仿真數(shù)據(jù)驗(yàn)證了本文數(shù)據(jù)匿名化方法的有效性，取得了較為理想的實(shí)驗(yàn)結(jié)果,。

參考文獻(xiàn)

[1] SAMARATI P,，SWEENEY L.Generalizing data to provide anonymity when disclosing information(abstract)[C].Proc.of the 17th ACM-S1GMOD-SIGACT-SIGART Symp on the Principles of Database Systems.Piscataway，NJ：IEEE,，1998：188-188.

[2] SWEENEY L.K-anonymity：a model for protecting privacy[J].International Journal of Uncertainty,，F(xiàn)uzziness and Knowl-edge-based Systems，2002,，10(5)：557-570.

[3] SWEENEY L.Achieving K-anonymity privacy protection using generalization and suppression[J].International Journal on Uncertainty,，F(xiàn)uzziness and Knowledge—Based Systems，2002,，10(5)：571-588.

[4] LEFEVRE K,，DEWITT D J，RAMAKRISHNAN R.Incognito：efficient full-domain K-anonymity[C].Proc.of the ACM SIGMOD International Conference on Management of Data,，2005：49-60.

[5] EL EMAM K,，DANKAR F K，ISSA R,，et al.A globally optimal k-anonymity method for the de-identification of health data[J].Journal of the American Medical Informatics Association：JAMIA,，2009，16(5)：670-682.

[6] LEFEVRE K,，DEWITT D J,，RAMAKRISHNAN R.Mondrian multi-mensional K-anonymity[C].Proc.of the 22nd International Conference on Data Engineering，2006.

[7] 楊靜,，王超,，張健沛，等.基于敏感屬性熵的微聚集算法[J].電子學(xué)報,，2014(7)：1327-1337.

[8] 于娟,，韓建民，郭騰芳,，等.基于聚類的高效k-匿名化算法[J].計(jì)算機(jī)研究與發(fā)展,，2009，46(z2)：480-486.

[9] AMIRI F,，YAZDANI N,，SHAKERY A,，et al.Hierarchical anonymization algorithms against background knowledge attack in data releasing[J].Knowledge-Based Systems，2016,，101(c)：71-89.

[10] ZHANG X,，DOU W，PEI J,，et al.Proximity-aware local-recoding anonymization with MapReduce for scalable big data privacy preservation in cloud[J].IEEE Transactions on Computers,，2015，64(8)：2293-2307.

[11] HINSHAW J V.Finding a needle in a haystack[J].LC-GC Europe,，2004,，22(10)：580-585.

[12] SAMARATI P.Protecting respondent′s identity in microdata release[C].IEEE Transactions on Knowledge and Data Engineering.IEEE，2001：13.

[13] GKOULALAS-DIVANIS A,，LOUKIDES G,，SUN J.Publishing data from electronic health records while preserving privacy：A survey of algorithms[J].Journal of Biomedical Informatics，2014,，50(8)：4-19.

[14] LIU Q,，SHEN H，SANG Y.Privacy-preserving data publishing for multiple numerical sensitive attributes[J].Tsinghua Science & Technology,，2015,，20(3)：246-254.

[15] 崔杰，李陶深,，蘭紅星,，等.基于Hadoop的海量數(shù)據(jù)存儲平臺設(shè)計(jì)與開發(fā)[J].計(jì)算機(jī)研究與發(fā)展，2012,，49(z1)：12-18.

[16] 詹浩,，段卓毅，陳迎春,，等.基于遺傳算法和分布式計(jì)算的翼型優(yōu)化設(shè)計(jì)研究[J].西北工業(yè)大學(xué)學(xué)報,，2004，22(6)：778-781.

[17] LIU X Y,，YANG X C,，YU G.A representative classes based privacy preserving data publishing approach with high predsion[J].Computer Science，2005,，32(9A)：368-373.

[18] 李建江,，崔健，王聃,，等.MapReduce并行編程模型研究綜述[J].電子學(xué)報,，2011,，39(11)：2635-2642.

[19] MOHAMMED E A,，F(xiàn)AR B H,，NAUGLER C.Applications of the MapReduce programming framework to clinical big data analysis：current landscape and future trends[J].Biodata Mining，2014,，7(1)：1-23.

[20] KOHLMAYER F,，PRASSER F，KUHN K A.The cost of quality：Implementing generalization and suppression for anonymizing biomedical data with minimal information loss[J].Journal of Biomedical Informatics,，2015,，58(5)：37-48.

[21] 任向民.基于K-匿名的隱私保護(hù)方法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2012.

作者信息：

劉  杰1,，沈微微1,，戈  軍1，2,，王學(xué)軍1

（1.宿遷學(xué)院 信息工程學(xué)院,，江蘇 宿遷223800；2.江蘇大學(xué) 計(jì)算機(jī)科學(xué)與通信工程學(xué)院,，江蘇 鎮(zhèn)江212013）