0 引言

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

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

1 算法

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

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

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

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

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

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

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

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

    算法1：GetFrequencySet_MR(T，args)

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

    輸出： 等價(jià)類集合。

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

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

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

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

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

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

1.2 算法分析

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

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

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

    (1)尋找抽樣泛化路徑

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

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

    Begin

        ①通過(guò)QI形成泛化格G；

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

        ③通過(guò)泛化格找到n₁直接泛化的節(jié)點(diǎn)，計(jì)算這些節(jié)點(diǎn)泛化T′所得到的信息損失量，選出泛化數(shù)據(jù)集T′信息損失量最小的節(jié)點(diǎn)n₂作為路徑P的第二個(gè)節(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個(gè)節(jié)點(diǎn)賦值給node，進(jìn)入以下循環(huán)：

        D=φ；

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

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

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

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

        T″∪D；

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

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

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

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

    本文實(shí)驗(yàn)硬件平臺(tái)為一臺(tái)Cisco UCS C240 M3的虛擬化ESXi服務(wù)器上搭建Hadoop平臺(tái)的完全分布式集群，包括1個(gè)Master節(jié)點(diǎn)和3個(gè)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ù)庫(kù)為SQL Sever2008。

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

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

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

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

    表的信息損失量：

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

    圖2、圖3對(duì)比了不同大小的數(shù)據(jù)集在k=100、|QI|=7的環(huán)境下，抽樣率對(duì)信息損失和抽樣尋徑時(shí)間占比的影響，由圖可知，當(dāng)抽樣率增大時(shí)，信息損失量沒(méi)有明顯變化，但是抽樣路徑時(shí)間占比增加幅度較為顯著。說(shuō)明當(dāng)抽樣樣本量足夠大時(shí)，增大抽樣率對(duì)降低匿名表的信息損失量無(wú)顯著影響，故本文以下實(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ù)集較小時(shí)，抽樣泛化路徑算法比本文算法的時(shí)間效率略高；而當(dāng)數(shù)據(jù)集大于50 000時(shí)，本文算法時(shí)間效率明顯高于抽樣泛化路徑算法時(shí)間效率，隨著數(shù)據(jù)集的不斷增大，本文算法時(shí)間優(yōu)勢(shì)更加顯著。本文算法處理較小數(shù)據(jù)集時(shí)，MapReduce的通信開(kāi)銷所占比重較大，故此時(shí)本文算法的時(shí)間效率略差于抽樣泛化路徑算法；而在處理較大數(shù)據(jù)集時(shí)，將MapReduce技術(shù)運(yùn)用到算法的等價(jià)類計(jì)算當(dāng)中，有效地縮短了計(jì)算等價(jià)類的時(shí)間。并且當(dāng)數(shù)據(jù)量增大到一定程度時(shí)，MapReduce的通信開(kāi)銷可以忽略不計(jì)，此時(shí)本文算法的時(shí)間效率要遠(yuǎn)高于抽樣路徑泛化算法。由此可知，在處理較大數(shù)據(jù)集時(shí)，本文算法有很大優(yōu)勢(shì)。 

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

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

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

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

    本文主要針對(duì)大數(shù)據(jù)背景下，如何提高K-匿名算法的時(shí)間效率及降低發(fā)布數(shù)據(jù)信息損失量的問(wèn)題進(jìn)行了研究。將MapReduce技術(shù)運(yùn)用到抽樣泛化算法中，很大程度上提高了較大數(shù)據(jù)集匿名化處理的時(shí)間效率，同時(shí)抽樣泛化路徑算法能夠有效降低發(fā)布數(shù)據(jù)的信息損失量。通過(guò)實(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é)報(bào)，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ù)存儲(chǔ)平臺(tái)設(shè)計(jì)與開(kāi)發(fā)[J].計(jì)算機(jī)研究與發(fā)展，2012，49(z1)：12-18.

[16] 詹浩，段卓毅，陳迎春，等.基于遺傳算法和分布式計(jì)算的翼型優(yōu)化設(shè)計(jì)研究[J].西北工業(yè)大學(xué)學(xué)報(bào)，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é)報(bào)，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）