0 引言

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

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

1 算法

1.1 算法設計

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

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

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

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

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

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

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

    算法1：GetFrequencySet_MR(T，args)

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

    輸出： 等價類集合。

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

    (2)進行Hadoop集群環境配置及MapReduce任務配置。

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

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

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

    算法1描述了等價類在MapReduce中的分布式計算過程，其中Map函數將數據集中準標識符屬性相同的值劃分為一個等價類，Reduce函數統計Map輸出的各等價類中元組的個數。

1.2 算法分析

    基于上述算法設計，把上面Map函數和Reduce函數加入到抽樣路徑泛化算法中，優化后的算法具體步驟如下：

    輸入：輸入表T、準標識符集合QI、等價類約束k以及抽樣率α。

    輸出：滿足K-匿名的數據集T″。

    (1)尋找抽樣泛化路徑

    函數： path(QI，T′)

     /* QI為準標識符屬性集，T′表示抽樣數據集*/

    Begin

        ①通過QI形成泛化格G；

        ②將泛化格G的第0層節點n₀作為路徑P的起點P₀；

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

        ④重復步驟②直至到達泛化格G的頂點n_i作為路徑的終點P_i得到路徑P；

        ⑤返回路徑P；

    End

    (2)匿名化數據表

    本文算法：

    Begin

    ① 從數據集T中以抽樣率α獲取抽樣數據集T′；

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

    ③ T″=φ； /*T″存放泛化后的數據集*/

    ④ node=φ，把路徑P中第i個節點賦值給node，進入以下循環：

        D=φ；

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

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

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

        計算D的信息損失量；

        T″∪D；

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

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

2 實驗分析

2.1 實驗平臺（數據集、泛化規則、抽樣比例制定）

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

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

2.2 實驗分析

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

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

    表的信息損失量：

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

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

2.3 實驗效果分析

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

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

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

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

3 結束語

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

參考文獻

[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，Fuzziness 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，Fuzziness 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].電子學報，2014(7)：1327-1337.

[8] 于娟，韓建民，郭騰芳，等.基于聚類的高效k-匿名化算法[J].計算機研究與發展，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的海量數據存儲平臺設計與開發[J].計算機研究與發展，2012，49(z1)：12-18.

[16] 詹浩，段卓毅，陳迎春，等.基于遺傳算法和分布式計算的翼型優化設計研究[J].西北工業大學學報，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].電子學報，2011，39(11)：2635-2642.

[19] MOHAMMED E A，FAR 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].哈爾濱：哈爾濱工業大學，2012.

作者信息：

劉  杰1，沈微微1，戈  軍1，2，王學軍1

（1.宿遷學院 信息工程學院，江蘇 宿遷223800；2.江蘇大學 計算機科學與通信工程學院，江蘇 鎮江212013）