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）