kaiyun官方注册
您所在的位置: 首页> 嵌入式技术> 设计应用> 基于抽样路径的K-匿名隐私保护算法
基于抽样路径的K-匿名隐私保护算法
2016年电子技术应用第12期
吴 响,臧 昊,俞 啸
徐州医科大学 医学信息学院,江苏 徐州221116
摘要:K-匿名是信息隐私保护的一种常用技术,而使用K-匿名技术不可避免会造成发布数据的信息损失,因此,如何提高K-匿名化后数据集的可用性一直以来都是K-匿名隐私保护的研究重点。对此提出了一种基于抽样路径的局域泛化算法——SPOLG算法。该算法基于泛化格寻找信息损失较小的泛化路径,为减少寻径时间,引入等概率抽样的思想,选用等概率抽样中的系统抽样方法进行取样,利用样本代替数据集在泛化格上寻找目标泛化路径,最后在该路径上对数据集进行泛化。同时,本算法使用局域泛化技术,能够降低信息损失量,提高发布数据集的可用性。实验结果证明,本算法匿名化的数据集信息损失度低,数据可用性高。
中图分类号:TP391
文献标识码:A
DOI: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.
K-anonymous privacy protection algorithm based on the sampling path
Wu Xiang,Zang Hao,Yu Xiao
School of Medical Informatics,Xuzhou Medical University,Xuzhou 221116,China
Abstract:K-anonymity is a common technique of information privacy protection. But K-anonymity must cause the information loss and how to improve the usability of anonymizing tables is the emphasis of K-anonymity. To solve the problem, this paper puts forward a kind of anonymous privacy protection algorithm based on generalized path —SPOLG algorithm. It introduces sampling with equal probabilities to find the generalized path whose information loss is little and raise the efficiency of data processing. Experimental results show that the algorithm could satisfy the anonymous requirement, at the same time, it is more efficient than Incognito algorithm to reduce the information loss of data released.
Key words :privacy preservation;path;information loss;sample;K-anonymity

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(A1,A2,…,An),表中每条元组指明一个特定实体的相关信息,如年龄、工作、种族、性别、工作时长、工资(敏感属性)等。

jsj3-b1.gif

jsj3-b1-x.gif

jsj3-b2.gif

1.2 SPOLG算法相关定义

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

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

例如:图1中,若用这个节点泛化样本比泛化样本信息损失小,则选取为路径的第2个节点,以此类推。如这条路线是一条可能的抽样泛化路径。

jsj3-t1.gif

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

jsj3-gs1.gif

2 算法实现

2.1 算法实现

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

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

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

(1)抽取样本

jsj3-2.1-x1.gif

(2)寻找抽样泛化路径

函数:path(QI,T′)

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

Begin

①通过QI形成泛化格G;

②将泛化格G的第0层节点n0作为路径P的起点P0

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

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

⑤返回路径P;

End

(3)匿名化数据表

jsj3-2.1-x2.gif

移除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]的计算方法。

元组的信息损失量:

jsj3-gs2-3.gif

3.2.1 数据抽样分析

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

jsj3-t2-3.gif

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无明显波动。综合以上所述:本文算法在信息损失方面具有明显的优势,发布的数据信息失真较少,可用性高。

jsj3-t4-5.gif

jsj3-b3.gif

jsj3-b4.gif

3.2.3 时间效率分析

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

jsj3-t6-7.gif

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.

此内容为AET网站原创,未经授权禁止转载。
Baidu
map