0 引言

    K-匿名模型被提出之后^[1-2]，國內(nèi)外學(xué)者對此進行了大量研究，提出了眾多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ù)體量越來越巨大，單個計算機難以在可接受的時間內(nèi)對數(shù)據(jù)進行有效的局域泛化。因此，如何利用并行分布式計算資源進行快速泛化^[15-16]是亟待解決的關(guān)鍵問題。(2)大多數(shù)局域泛化算法都是以犧牲時間效率來換取低信息損失量，無法做到兩者兼顧^[17]。

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

1 算法

1.1 算法設(shè)計

    抽樣路徑泛化算法是一種信息損失量較小的局域泛化K-匿名算法，其思想是引入等概率抽樣的方法，使用抽樣樣本在泛化格(generalization lattice)^[4，20]上快速尋找一條信息損失量較小的泛化路徑，在已得到的抽樣泛化路徑上依次對源數(shù)據(jù)集中未滿足K-匿名的等價類進行泛化，最終得到一個高精度的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é)點為起點，計算其子節(jié)點對樣本泛化后的信息損失量，將其信息損失量最小子節(jié)點插入路徑，自底向上，直至泛化格葉子節(jié)點。例如：圖1中是由工人類別和性別組成的一個泛化格實例，若用<W1，S0>這個節(jié)點泛化樣本比<W0，S1>泛化樣本信息損失小，則選取<W1，S0>為路徑的第2個節(jié)點，以此類推，找到一條如<W0，S0>→

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

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

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

    算法1：GetFrequencySet_MR(T，args)

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

    輸出： 等價類集合。

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

    (2)進行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中的分布式計算過程，其中Map函數(shù)將數(shù)據(jù)集中準(zhǔn)標(biāo)識符屬性相同的值劃分為一個等價類，Reduce函數(shù)統(tǒng)計Map輸出的各等價類中元組的個數(shù)。

1.2 算法分析

    基于上述算法設(shè)計，把上面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é)點n₀作為路徑P的起點P₀；

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

        ④重復(fù)步驟②直至到達(dá)泛化格G的頂點n_i作為路徑的終點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é)點賦值給node，進入以下循環(huán)：

        D=φ；

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

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

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

        計算D的信息損失量；

        T″∪D；

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

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

2 實驗分析

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

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

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

2.2 實驗分析

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

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

    表的信息損失量：

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

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

2.3 實驗效果分析

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

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

3 結(jié)束語

    本文主要針對大數(shù)據(jù)背景下，如何提高K-匿名算法的時間效率及降低發(fā)布數(shù)據(jù)信息損失量的問題進行了研究。將MapReduce技術(shù)運用到抽樣泛化算法中，很大程度上提高了較大數(shù)據(jù)集匿名化處理的時間效率，同時抽樣泛化路徑算法能夠有效降低發(fā)布數(shù)據(jù)的信息損失量。通過實驗仿真數(shù)據(jù)驗證了本文數(shù)據(jù)匿名化方法的有效性，取得了較為理想的實驗結(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].計算機研究與發(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è)計與開發(fā)[J].計算機研究與發(fā)展，2012，49(z1)：12-18.

[16] 詹浩，段卓毅，陳迎春，等.基于遺傳算法和分布式計算的翼型優(yōu)化設(shè)計研究[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-匿名的隱私保護方法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2012.

作者信息：

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

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