基于抽样路径的K-匿名隐私保护算法

吴 响，臧 昊，俞 啸

（徐州医科大学 医学信息学院，江苏 徐州221116）

K-匿名是信息隐私保护的一种常用技术，而使用K-匿名技术不可避免会造成发布数据的信息损失，因此，如何提高K-匿名化后数据集的可用性一直以来都是K-匿名隐私保护的研究重点。对此提出了一种基于抽样路径的局域泛化算法——SPOLG算法。该算法基于泛化格寻找信息损失较小的泛化路径，为减少寻径时间，引入等概率抽样的思想，选用等概率抽样中的系统抽样方法进行取样，利用样本代替数据集在泛化格上寻找目标泛化路径，最后在该路径上对数据集进行泛化。同时，本算法使用局域泛化技术，能够降低信息损失量，提高发布数据集的可用性。实验结果证明，本算法匿名化的数据集信息损失度低，数据可用性高。

隐私保护；路径；信息损失；抽样；K-匿名

TP391文献标识码： ADOI：10.16157/j.issn.0258-7998.2016.12.030

吴响，臧昊，俞啸. 基于抽样路径的K-匿名隐私保护算法[J].电子技术应用，2016，42(12)：115-118.

英文引用格式：Wu Xiang，Zang Hao，Yu Xiao. K-anonymous privacy protection algorithm based on the sampling path[J].Application of Electronic Technique，2016，42(12)：115-118.

0 引言

K-匿名^[1]是一种简单而有效的隐私保护模型，实施K-匿名要考虑两个方面：（1）确保数据发布过程中隐私不泄露；（2）发布的匿名数据具有实用性。

基于以上两个要求，众多学者提出了许多匿名算法。但大体上可以分为全域泛化算法^[2]和局域泛化算法^[3]。相比之下，局域泛化算法不仅可以实现K-匿名，而且一定程度上降低了匿名表的信息损失，使得泛化后的数据集更具有可用性。

然而，在局域泛化中想要寻找最优K-匿名已经被证明是NP难问题^[4]，如何优化K-匿名算法、尽可能提高数据的可用性成为亟待解决的问题。因此，本文提出了一种基于抽样路径的局域K-匿名算法——SPOLG(Sampling Path Optimization Local Generalization)算法。

SPOLG算法将等概率抽样的思想引入其中，选取足够的样本代替总体寻找泛化路径，在已经寻找到的路径基础上对数据集进行局域泛化。等概率抽样选择的样本能够代表数据集总体的分布情况，通过样本寻径快速找到信息损失较小的泛化路径，极大地提高了算法效率。同时，该算法采用的局域泛化技术保证了发布的数据集具有较高的可用性。

1 基本符号和定义

1.1 K-匿名相关定义

在实现SPOLG算法的过程中，以表1为例对基于抽样泛化路径的K-匿名算法进行相关定义。假设数据发布者所持有的数据表为T(A₁，A₂，…，A_n)，表中每条元组指明一个特定实体的相关信息，如年龄、工作、种族、性别、工作时长、工资（敏感属性）等。

1.2 SPOLG算法相关定义

定义2 系统抽样：将数据集中的元组按照ID排序，随机选取一条元组作为起点，每隔一定的间隔抽取一个元组，直至样本数量满足事先给定的抽样率。

定义3 抽样泛化路径：以泛化格的根节点为起点，计算其子节点对样本泛化后的信息损失量，将信息损失量最小子节点插入路径，自底向上，直至泛化格叶子节点。

例如：图1中，若用<W1，R0>这个节点泛化样本比<W0，R1>泛化样本信息损失小，则选取<W1，R0>为路径的第2个节点，以此类推。如<W0，R0>→<W1，R0>→<W1，R1>→<W2，R1>这条路线是一条可能的抽样泛化路径。

定义4 抽样寻径时间占比：由抽样数据产生抽样泛化路径所花费的时间S_P在整个算法流程中的百分比。假设整个算法花费的时间为S_A，则其计算公式为：

2 算法实现

2.1 算法实现

本文提出的一个基于抽样路径的局域泛化算法——SPOLG算法，引进了等概率抽样的思想，以系统抽样样本代替数据集寻找泛化路径，具体算法如下：

输入：输入表T，准标识符集合QI，等价类约束k以及抽样率α。

输出：满足K-匿名的数据集T″。

(1)抽取样本

(2)寻找抽样泛化路径

函数：path(QI，T′)

/*QI为准标识符集，T′表示抽样数据集*/

Begin

①通过QI形成泛化格G；

②将泛化格G的第0层节点n₀作为路径P的起点P₀；

③通过泛化格找到n₁直接泛化的节点，计算这些节点泛化T′所得到的信息损失量，选出泛化数据集T′信息损失量最小的节点n₂作为路径P的第二个节点P1；

④重复步骤②直至到达泛化格G的顶点ni作为路径的终点Pi得到路径P；

⑤返回路径P；

End

(3)匿名化数据表

移除T中满足K-匿名的元组；

结束循环；

⑤返回数据表；

End

由以上步骤可知，该算法主要包括系统抽样、寻找路径、 匿名化数据集3个主要环节，利用系统抽样选取样本，在已选择的样本中寻找信息损失较低的泛化路径，由已选路径对数据集进行局域泛化。从路径起点开始，自底向上对不满足K-匿名的元组进行泛化，直到所有元组满足K-匿名。

2.2 算法合理性分析

本文算法使用系统抽样，能够保证每个元组被抽取概率相同，通过等概率抽样样本快速寻找到信息损失较低的泛化路径，使得数据集整体泛化后的信息损失较小。同时，局域泛化进一步保证了匿名后的数据集信息损失小，因此本算法是可行的。

3 实验验证及结果分析

3.1 实验环境

本文使用了UCI Machine Learning Repository中的Adults数据集作为实验数据集，Adult数据集是由美国人口普查数据构成，采用数据集中的训练集，并去除缺省值记录，共有30 162条记录，本文选取7个属性作为准标识符属性，包括性别、种族、婚姻状况、教育程度、工作、国籍、年龄，各属性预定义的泛化规则参考文献[5]。实验平台配置为：Core 2.50 GHz/8 GB，Windows 7，所涉代码均由Java实现，并在Eclipse Mars.2 Release(4.5.2)上运行。实验数据都是在实验运行5次所得到的实验数据基础上取得的平均值。

3.2 实验结果分析

实验主要从信息损失度及执行时间方面对本文算法进行衡量。本实验选用Incognito算法作为对比算法，比较了在不同个数的准标识符和不同k值条件下信息损失度和执行时间的变化。其中信息损失度采用文献[6]的计算方法。

元组的信息损失量：

3.2.1 数据抽样分析

寻径时间占比通过式（1）进行计算，信息损失量依据公式（2）、（3）来度量，由图2、图3可知，当|QI|一定时，随着采样率的增加，抽样寻径时间占比均有大幅度上升，然而信息损失量的波动幅度较小，故可使用较小的采样率；同时因抽样率越大越符合数据集的分布，故要使用足够数量的样本代表数据集。综合以上所述，本文以下实验均采用1%的抽样率。

3.2.2 信息损失量分析

图4为准标识符属性个数|QI|=7，k取5/10/15/20/25/50时，SPOLG算法和Incognito算法匿名化数据集信息损失量的比较。由图4知，执行SPOLG算法和Incognito算法产生的信息损失量随k值的增加而增加，这是由于k值变大时，每个等价类所含元组数量增多，数据集泛化程度变大，故IL增大。但随k值的变大，SPOLG算法信息损失IL增加幅度较小。其原因在表3中可以清晰看出，元组前三步泛化比例达50%以上，由此可知数据集中的大部分元组都只经过一次泛化，因此泛化后的数据集信息损失IL小，随着k值的变大IL增加较小。图5表示当k=10时，|QL|取3/4/5/6/7，SPOLG算法与Incognito算法匿名化数据信息损失量的比较。从图5可以看出，Incognito算法产生的信息损失IL呈明显上升趋势，本文算法随着准标识符属性的|QI|增多信息损失IL无明显波动。表4中数据表明，|QI|增大时，前三步泛化比例均达到60%。由此可见，数据集中的大部分元组都只经过一次泛化，因此泛化后的数据集信息损失IL小，随着|QI|的增加IL无明显波动。综合以上所述：本文算法在信息损失方面具有明显的优势，发布的数据信息失真较少，可用性高。

3.2.3 时间效率分析

图6、图8分别表示运行时间、k和|QI|的关系。由图6知，当|QI|一定时，由于k值增大，泛化程度变大，产生的等价类数量变少，每个元组寻找等价类的时间大幅度降低。由图7知，当k值一定时，随着|QI|的增加，约束条件变多，等价类数量增多，每个元组寻找等价类的时间变大，所以本算法运行时间有所增加。综合图6、图7可知，本文算法在时间效率上比Incognito算法略差，但是由于信息损失量的大幅度降低，因此本算法的综合优势明显。

4 总结

本文提出一种基于准标识符属性泛化路径的K-匿名化算法——SPOLG算法，该算法采用等概率抽样的方法快速寻找泛化路径，在已找到泛化路径的基础上进行数据集的局域泛化。实验结果表明，该算法泛化的数据表信息损失较小，可用性高。

参考文献

[1] SWEENEY L.A model for protecting privacy[J].International Journal on Uncertainty Fuzziness and Knowledge-Based Systems，2002，10(5)：557-570.

[2] SWEENY L.Achieving k-anonymity privacy protection using generalization and suppression[J].International Journal of Uncertainty，Fuzziness and Knowledge-Based Systems：IJUFKS，2002，10(5)：571-588.

[3] SWEENY L．Guaranteeing anonymity when sharing medical data：the datafly system[C].Proceedings of the 1997 AMIA Annual Fall Symposium，Journal of the American Medial Informatis，Association，AMIA，1997，4(suppl)：51-55．

[4] MACHANAVAJJHALA A，GEHRKE J，KIFER D.L-diversity：Privacy beyond k-anonymity[C].Proc of the 22nd In Conference on Data Engineering.Piscataway,NJ：IEEE，2006：24-36.

[5] LI J Y，WONG C W，FU W C，et al.Achieving k-anonymity by clustering in attribute hierarchical structures[C].Data Warehousing and Knowledge Discovery.Springer Berlin Heidelberg，2006：405-416.

[6] 任向民.基于K-匿名的隐私保护方法研究[D].哈尔滨：哈尔滨工业大学，2012.