优秀硕士论文--基于匿名机制的数据发布中隐私泄露控制技术

1、 基于匿名机制的数据发布中隐私泄露控制技术第一章 引言1.1研究背景数据发布环境中存在的隐私泄露问题使得数据发布隐私泄露控制技术的研究成为学术界和工业界关注的一个焦点。数据发布中的原始数据由记录构成，每个记录均与一个个体相对应，数据的属性分为标识符、准标识符、敏感属性三类。数据发布时直接删除标识符以保护个体隐私。但是可能存在攻击者通过准标识符与外部公开的数据源进行链接攻击(Linking Attack) 1，导致个体隐私的泄露。研究表明，这种链接攻击可以识别大量美国公民的身份1。例如，假设一个网站上发布了一个医疗信息表，为保护个体隐私，将原始数据中能识别个体身份的标识符（姓名）删除之后得到数据

2、发布表，如表1-1所示。表1-1属性组(年龄，性别，邮编 )为准标识符，敏感属性为疾病。若攻击者可以从另一个网站上浏览如表1-2选民登记表的信息，获知表中法兰克的年龄属性值为45，性别属性值为男，邮编 属性值为734532。攻击者很容易从表1-1推出法兰克患有心脏病，造成了法兰克的隐私泄露。为了阻止数据发布中的链接攻击，一个有效的手段是对原始数据进行匿名化处理，从而控制个体隐私信息的泄露。表1-1医疗信息表年龄性别邮编疾病t141女734562失眠t240女734552心脏病t341男734532失眠t444男734555心脏病t544男734555失眠t645男734532心脏病t741男7

3、34561禽流感t842男734533禽流感t943女734553禽流感表1-2选民登记表姓名年龄性别邮编爱丽丝41女734562贝蒂40女734552约翰41男734532比尔44男734555艾迪44男734555法兰克45男734532凯恩41男734561杰克42男734533珍妮43女7345531.2国内外研究进展分析数据发布要求匿名数据既具有安全性又具有可用性，然而两者是相互矛盾的。因此，数据匿名化研究的重点是设计高效的匿名保护模型和匿名算法，以使得匿名数据在保证安全性的同时，最大限度地提供可用性。目前，国内外匿名化技术的研究已经取得了许多的成果。1.2.1匿名保护模型1.2.1

4、.1 k-匿名模型(k-anonymity)定义1.11 k-匿名 假设TA1,A2,An为一个数据集，QIT为与之相关的准标识符。当且仅当数据集T中每个记录的准标识符属性值在数据集中至少出现k次，则该数据集满足k-匿名。定义1.21 等价类 一个等价类即数据集TA1,A2,An中一组具有相同准标识符属性值的记录。 针对数据发布中的链接攻击，文献1,2提出了k-匿名技术。文献3提出实现k-匿名的泛化和隐匿方法，泛化是指在数据集中用抽象的属性值来代替原来具体的属性值，隐匿是指隐匿是指直接删除数据集中某些属性值或记录。k-匿名通过泛化和隐匿使得等价类中每个记录具有相同的准标识符属性值，攻击者无法将

5、个体与某个记录对应起来，从而保护个体身份的泄露。例如，表1-3是表1-1的一个满足3-匿名模型的匿名化表，其中，匿名参数=，准标识符为属性组(年龄，性别，邮编 )，敏感属性为疾病。表1-3中生成了3个等价类t1，t2，t7，t4，t5，t6，t3，t8，t9。若在网站上用表1-3代替表1.的医疗信息表，那么攻击者即使知道表1-2选民登记表中某个记录的信息，也无法推断出该记录与表1-3中某一特定记录相关联。例如假设攻击者从1-2选民登记表中获知法兰克的信息，与表1-3链接时，虽然知道法兰克在t4，t5，t6等价类中，却无法将法兰克与其中的某个记录相对应起来，从而避免法兰克隐私的泄露。表1-3 -

6、匿名化表1年龄性别邮编疾病t140-41*7345*失眠t240-41*7345*心脏病t740-41*7345*禽流感t444-45男7345*心脏病t544-45男7345*失眠t644-45男7345*心脏病t341-43*7345*失眠t841-43*7345*禽流感t941-43*7345*禽流感但是， k-匿名模型存在同质性攻击和背景知识攻击的问题4。k -匿名模型由于忽略了敏感属性值的多样性，可能造成个体敏感属性的隐私泄露，即同质性攻击。例如，假设表1-4是表1-1的另一个满足3-匿名模型的匿名化表，表1-4中生成了3个等价类t1，t2，t3，t4，t5，t6，t7，t8，t9。

7、如果攻击者从1-2选民登记表中获知杰克的信息，与表1-4链接起来时，虽然无法确定杰克与表1-4中具体的某个记录相对应，但通过准标识符属性值可以知道杰克在表1-4的t7，t8，t9等价类中，由于该等价类的敏感属性值均为禽流感，攻击者容易知道杰克患有禽流感，杰克的隐私被泄露。同时，k -匿名还可能遭遇攻击者利用预先知道的背景知识来进行攻击。此外，k -匿名模型由于通过泛化准标识符属性达到匿名的目的也导致大量原始信息的损失，降低了匿名数据的可用性。表1-4 -匿名化表2年龄性别邮编疾病t140-41*7345*失眠t240-41*7345*心脏病t340-41*7345*失眠t444-45男7345

8、*心脏病t544-45男7345*失眠t644-45男7345*心脏病t741-43*7345*禽流感t841-43*7345*禽流感t941-43*7345*禽流感1.2.1.2 l-多样性模型(l-diversity)文献4提出了l-多样性模型(l-diversity)以弥补k-匿名模型的不足。定义1.34 l-多样性原则一个等价类如果对于敏感属性S至少包含l个不同的敏感属性值，那么该等价类是l-多样性的。如果数据集T中的每个等价类是l-多样性的，则称该数据集满足l-多样性。该模型除了要求满足k-匿名之外，还要求每个等价类的敏感属性值具有多样性以防止敏感属性的隐私泄露。例如，表1-5是表1

9、-1的一个满足3-多样性模型的匿名化表，其中，l，Q(年龄，性别，邮编 )。表1-5中生成了3个等价类t1，t2，t7，t4，t5，t9，t3，t6，t8。每个等价类中的记录在(年龄，性别，邮编 )上具有相同的属性值，并且在敏感属性疾病上具有3个不同值。因而，表1-5中的数据能够防止链接攻击所导致的敏感属性隐私泄露。虽然l-多样性模型可以提供比k-匿名模型更强的隐私保护，但是，l-多样性模型依然存在不足之处，l-多样性模型同样采用泛化和隐匿技术对原始数据进行匿名处理，因而也存在信息损失的情况。表1-5 3-多样性表年龄性别邮编疾病t140-41*7345*失眠t240-41*7345*心脏病t

10、740-41*7345*禽流感 t443-44*73455*心脏病t543-44*73455*失眠t943-44*73455*禽流感t341-45男73453*失眠t641-45男73453*心脏病t841-45男73453*禽流感1.2.1.3 Anatomy匿名模型文献5提出了独特的匿名方法Anatomy，该方法首先将数据集按l-多样性匿名模型划分，将划分结果分成准标识符属性表和敏感属性表发布，两张数据表之间通过Group-ID关联。Anatomy匿名模型对等价类的准标识符属性不作泛化和隐匿处理，直接将准标识符属性数据发布，因而保留了大量原始数据的信息，大大提高了匿名数据的可用性。同时，A

11、natomy将数据分成两张表发布，使得攻击者无法将个体的准标识符属性和敏感属性一一对应起来，提高了数据的安全性。由于Anatomy匿名模型是在l-多样性模型的基础上提出的，l-多样性模型上存在的一些不足，在Anatomy匿名模型中也依然存在。例如，表1-6是表1-1的一个满足Anatomy模型的匿名化结果，假设攻击者知道某个个体在Group-ID为1的等价类中。虽然攻击者可以从准标识符属性表获知该个体的年龄，性别，邮编具体值，但他无法从敏感属性表中准确获得敏感属性疾病的值，由于Group-ID为1的疾病值的个数为3，因此攻击者只能以1/3的几率进行猜测。数据发布中，研究出提供更强保护能力的匿名

12、模型依然是匿名保护中的主要工作，因此，研究者们在k-匿名模型和l-多样性模型的基础上，又提出了一些新的匿名模型6-8。表1-6 Anatomy表(a) 准标识符属性表Group-ID年龄性别邮编141女734562140女734552142男734561244男734555244男734555243女734553341男734532345男734532342男734533(b) 敏感属性表Group-ID疾病统计1失眠11心脏病11禽流感 12心脏病12失眠12禽流感13失眠13心脏病13禽流感11.2.2 匿名算法采用匿名技术由原始数据生成最优匿名数据是一个NP难问题9,10，因此，设计出高

13、效的近似最优算法是匿名保护中的重要工作。目前数据发布中采用的匿名技术主要有：泛化和隐匿、聚类以及交换等技术。采用泛化和隐匿技术的匿名算法主要有： Datafly算法11、MinGen最小泛化算法3、Incognito算法12、GA（Genetic Algorithm）算法13、自底向上的泛化方法14、自顶向下的泛化方法15、基于多维空间划分的k-匿名方法16。国内研究者也在文献17-20中对泛化和隐匿技术进行了研究。泛化和隐匿技术将等价类中不同的准标识符属性值泛化为相同值以达到隐私保护的目的，造成了原始数据大量信息的损失。同时，基于泛化和隐匿技术的匿名算法采用基于泛化层次结构的策略会引起不必要

14、的信息损失。为了解决泛化和隐匿技术存在的不足，在数据的匿名化中引入聚类技术。基于聚类的匿名化方法的主要思想是：首先将数据划分为多个聚类，然后分别泛化每个聚类的准标识符属性以达到匿名化。文献21提出模糊c-均值算法。文献22提出基于k-modes的算法。文献23,24提出了基于k-means聚类算法的k-匿名方法。文献25提出MDAV k-匿名算法。在MDAV算法的基础上，文献26提出了V-MDAV(Variable-MDAV)算法。文献27,28 提出了带权重的聚类方法。文献29-32 提出了基于聚类的k-匿名算法。基于聚类的匿名算法不依赖于泛化层次结构，因此生成的匿名数据集具有更高可用性。数

15、据交换是将数据集中某些属性的值进行互换以防止隐私泄露 33-35。文献5提出了一种不基于泛化和隐匿技术的交换方法Anatomy。文献36-38也提出了基于交换的隐私数据发布算法。采用交换技术的匿名化算法通过交换增加了隐私数据的不确定性，从而保护隐私数据的安全。并且交换技术直接发布准标识符属性，保留了原始数据的大量信息，极大地提高了匿名数据聚集查询的准确性。1.2.3匿名质量评估匿名化原始数据必然会引起信息损失，需要找到适合的评估机制来计算匿名后的信息损失以衡量匿名算法和匿名数据集的优劣。以下是匿名质量评估中常用的信息损失评估机制：定义1.131, 32 等价类信息损失IL(e)。假设等价类er

16、1,rk由准标识符由数值属性(N1,Nm)和分类属性(C1,Cn)构成，则等价类信息损失IL(e)为：公式中|e|是e中记录个数，|Ni|表示数值属性的范围， 和分别是e中关于属性Ni的最大最小值。|Cj| 表示分类属性的不同属性值个数，表示e中关于属性Cj的不同属性值个数。定义1.232 总体信息损失Total_IL。若e1,em是匿名数据集T中所有等价类的集合，那么T的总体信息损失为：。总体信息损失能够反映匿名数据集相对原始数据集所产生的信息损失。此外，文献39中定义的可区分度量机制也可用来衡量匿名化质量。定义1.339 可区分度量DM (Discernability Metric)定义为

17、，其中|E|表示等价类E中的记录个数，DM的值即为数据集中每一个等价类大小的平方的和。可区分度量的意义在于：等价类越大可区分度就越小，意味着一个记录在大的等价类中难以区分。定义1.45 聚集查询平均相对错误率。一个查询的相对错误率为|act est|/act， act是对原始数据进行查询获得的实际结果，est是对匿名数据进行查询获得的推测结果。每个查询相对错误率的和的平均值即为聚集查询平均相对错误率。1.3论文的组织本文共分为四章，各章节内容组织如下：第一章为引言，阐述研究数据发布中匿名化与敏感信息保护技术的意义，分析与评述国内外有关数据发布中匿名模型、匿名化与敏感信息保护技术方面的研究进展，

18、给出本文章节的组织结构。在第二章中，将着重讨论基于聚类的敏感属性l-多样性匿名化算法的设计与实现。首先，分析提出基于聚类的敏感属性l-多样性匿名化算法的动机，然后根据不同的聚类种子记录的选择方式以及聚类前生成不同的聚类记录候选集，提出了2个满足l-多样性模型的聚类算法，并通过对真实数据的实验来评估这两个算法的性能。第三章将讨论基于l-多样性的多敏感属性匿名化技术问题。首先分析多个敏感属性的数据发布存在的隐私泄露风险，从而提出了一个满足l-多样性模型的多敏感属性匿名化算法，并通过实验验证这个算法的有效性。第四章总结本文的工作成果，并对下一步的研究方向做出展望。第二章 基于聚类的匿名化算法2.1问

19、题分析本章讨论基于聚类的匿名化。以往的匿名化研究工作中，大多采用泛化和隐匿技术实现数据的匿名化。但是基于泛化和隐匿的匿名化算法由于受到泛化层次结构的限制，导致一些不必要的信息损失。为了降低信息损失,一些学者将聚类方法应用到数据的匿名化上。事实表明，基于聚类的方法能够生成高质量的匿名数据集。但是，基于聚类的匿名化算法中，大多是基于k-匿名模型的，没有考虑敏感属性值的多样性，存在着隐私泄露的风险。因此，本章研究提出2个满足l-多样性模型的聚类算法LCA-FC(l-diversity clustering algorithm, select furthest seed and compare wit

20、h centroid)和LCA-RC (l-diversity clustering algorithm, randomly select seed and compare with centroid)，以避免敏感属性的隐私泄露。2.2基于聚类的敏感属性l-多样性匿名化算法.在基于聚类的匿名化算法中，聚类种子记录的选择和寻找信息损失最小记录的方式是非常重要的，将会影响到聚类的质量。选择聚类种子记录时，可以随机选择数据集的一个记录，也可以选择最远的记录作为聚类种子记录。寻找信息损失最小记录时，可以计算整个聚类和每个候选记录的信息损失来找到信息损失最小记录，也可以计算聚类代表记录和每个候选记录的信

21、息损失来找到信息损失最小记录。而选择聚类代表记录时，可以选择聚类质心，也可以随机选择聚类的一个记录作为聚类代表记录。选择不同的方式，将会产生不同的聚类效果。大多数已有的基于聚类的k-匿名算法没有满足敏感属性值l-多样性的要求，存在着隐私泄露的风险。因此，根据不同的聚类种子记录的选择方式以及聚类时生成不同的聚类记录候选集，本文提出了基于聚类的敏感属性l-多样性匿名化算法LCA-FC和LCA-RC。它们的主要思想是：给定一个n个记录的数据集T和l-多样性参数l，首先计算数据集T不同敏感属性值个数，如果该值大于等于l，选择一个记录作为种子开始建立一个聚类，然后每次从聚类记录候选集中选择一个与聚类信息

22、损失最小的记录加入该聚类，直到聚类中记录个数为l时结束，从而生成一个聚类（即等价类）。然后，满足条件的情况下选择一个记录作为新的种子记录，重复相同的过程建立下一个聚类。最后，对于剩余的记录，分别计算它们与已经生成的每个聚类之间的信息损失，然后加入到信息损失最小的聚类中。LCA-FC算法在数据集中选择距离上次种子记录最远的记录作为聚类种子记录，LCA-RC算法则在数据集中随机选择一个记录作为聚类种子记录，两者均通过计算聚类质心和聚类记录候选集的每个记录的信息损失来找到信息损失最小记录，但聚类记录候选集不同。本文算法在计算聚类质心时，各个数值型属性值采用聚类的各个数值型属性平均值，而各个分类属性值

23、则采用聚类的各个分类属性中出现频率最高的值。算法处理的数据包括数值属性和分类属性，信息损失机制必须既适用于数值型数据又适用于分类型数据的信息损失计算。因此聚类所产生的信息损失采用1.2.3小节定义的信息损失机制来衡量。下面分别描述基于聚类的敏感属性l-多样性匿名化算法LCA-FC和LCA-RC：算法2.1 LCA-FC算法 输入：原始数据集T和l-多样性模型参数l；输出：符合l-多样性模型要求的匿名数据集tableBeginStep1: 计算数据集T不同敏感属性值个数；if (T中不同敏感属性值个数<l) then不能满足l-多样性，return T;end if;匿名数据集table=

24、；r=从T中随机选取一个记录;Step2: while (T中不同敏感属性值个数>=l) do聚类C=r;聚类质心centroid=r;数据集T=Tr;聚类记录候选集LT=从数据集T中选择与种子记录敏感属性不相同的记录；while (|C|<l) domin=;for (i=1, 候选集LT记录个数) dorecord=LT中第i个记录；if (record的敏感属性值与聚类C中记录的敏感属性值相同) continue;il= record 到聚类C质心的信息损失IL recordcentroid;if(il<min) thenmin=il;minrecord=record;

25、end if;end for;聚类C=聚类C信息损失最小记录minrecord;候选集LT= LT信息损失最小记录 minrecord ;数据集T=T信息损失最小记录 minrecord ;重新计算聚类质心centroid;end while匿名数据集table=table生成的聚类C;重新计算T中不同敏感属性值个数；r=计算距离记录r最远的记录;end whileStep3: while (|T|0) dor=从T中随机取记录r;T=Tr;for (i=1, 匿名数据集table中的聚类个数) doC=第i个聚类；if (C的记录个数>=2*l-1) then continue;il=

26、记录r与聚类C质心信息损失IL rcentroid;if (il<min) thenmin=il;minc=i;end if;end for;信息损失最小聚类minc = r信息损失最小聚类minc;end whileStep4: 将匿名数据集table中的每个聚类的所有记录在准标识符上的属性值用该聚类代表记录准标识符上的属性值代替，完成匿名化，得到最后输出的匿名数据集table。End算法2.2 LCA-RC算法 输入：原始数据集T和l-多样性模型参数l；输出：符合l-多样性模型要求的匿名数据集tableBeginStep1: 计算数据集T不同敏感属性值个数，种子记录候选集LS=从数据

27、集T中选择敏感属性值相同且数目最多的所有记录，聚类记录候选集LT= 数据集T-种子记录候选集LS-敏感属性值相同且数目最少的所有记录；if (T中不同敏感属性值个数<l) then 不能满足l-多样性，return T;end if;匿名数据集table=；Step2: while (T中不同敏感属性值个数>=l) do r=种子记录候选集LS中随机选取一个记录;聚类C=r;聚类质心centroid=r;数据集T=T-r;while (|C|<l) domin=;for (i=1, 聚类记录候选集LT记录个数) dorecord=LT中第i个记录；if (record的敏感属

28、性值与聚类C中记录的敏感属性值相同) continue;il= record 与聚类C质心的信息损失IL recordcentroid;if (il<min) thenmin=il;minrecord=record;end if;end for;聚类C=聚类C信息损失最小记录minrecord;候选集LT= LT信息损失最小记录 minrecord ;数据集T=T信息损失最小记录 minrecord ;重新计算聚类质心centroid;end while匿名数据集table=table生成的聚类C;重新计算T中不同敏感属性值个数，种子记录候选集LS，聚类记录候选集LT；r=距离记录r最远

29、的记录;end whileStep3: while (|T|0) dor=从T中随机取记录r;T=Tr;for (i=1, 匿名数据集table中的聚类个数) doC=第i个聚类；if (C的记录个数>=2*l-1) then continue;il=记录r与聚类C质心信息损失IL rcentroid;if (il<min) thenmin=il;minc=i;end if;end for;信息损失最小聚类minc = r信息损失最小聚类minc;end whileStep4: 将匿名数据集table中的每个聚类的所有记录在准标识符上的属性值用该聚类代表记录准标识符上的属性值代替，

30、完成匿名化，得到最后输出的匿名数据集table。EndLCA-FC和LCA-RC算法通过设置l-多样性模型参数l，使得生成的每个聚类至少有l个不同的敏感属性值，降低了隐私泄露的风险。重新分配剩余记录时，若聚类记录个数达到2l-1时该聚类则停止参与分配，控制生成聚类的大小介于l和2l-1之间，以满足最优划分。LCA-FC算法每次选择距离上次种子记录最远的记录作为聚类种子记录，获得了较好的划分效果；选择与种子记录敏感属性值不同的所有记录作为候选集，在较大的记录范围中寻找信息损失最小记录，可获得较小的总体信息损失。LCA-RC算法每次从数据集中随机选择一个记录作为聚类种子记录，选择与聚类中各记录敏感

31、属性值不相同且记录数最多的一个敏感属性值上的所有记录作为候选集。该算法可较大减少剩余记录，生成较多的聚类，获得较好的可区分度量。但是，由于LCA-RC算法生成的候选集较小，寻找信息损失最小记录的范围小，因而在获得较好可区分度量的同时会导致比LCA-FC算法多一些的总体信息损失。此外，在生成聚类时，若通过计算整个聚类和每个候选记录的信息损失来找到信息损失最小记录加入聚类，记录的准标识符属性值可能会被泛化到较大的值区域，引起较多的信息损失。因此，LCA-FC和LCA-RC算法总是计算聚类质心和每个候选记录的信息损失来找到信息损失最小记录，这样可以减少信息的损失并提高算法效率。2.3实验结果与分析实

32、验硬件环境为Intel Pentium Dual E2180 2.0GHz CPU、2.0GB RAM，操作系统是Microsoft Windows XP。LK-member、LCA-FC和LCA-RC算法均采用C+语言编程实现，开发环境是Microsoft visual Studio6.0。本文采用UC Irvine机器学习数据集中的真实数据集Adults人口普查数据作为实验数据，这个数据集是匿名化研究领域的标准测试数据集。采用与文献39一样的方法对Adults数据进行预处理，删除存在信息缺失的记录，得到30162个记录的实验数据集。本文中只保留8个属性: Age，Work Class，Ed

33、ucation，Marital Status，Race，Sex，Country，Occupation。其中Age和Education属性为数值型属性，其他属性均为分类属性。用三个评价标准来衡量算法的有效性:(l) 总体信息损失Total-IL (2)可区分度量DM (3)运行时间Running Time。为了进行实验分析比较，本文对文献32提出的基于k-匿名模型的k-member聚类算法进行修改，使之得到满足l-多样性模型的LK-member(l-diversity K-member)聚类算法，LK-member算法采用选择与上次种子记录距离最远的记录作为聚类种子记录，通过计算整个聚类和每个候

34、选记录的信息损失来找到信息损失最小记录的策略。实验将本文提出的LCA-FC和LCA-RC算法与LK-member算法进行总体信息损失、可区分度量和运行时间性能比较。2.3.1 l-多样性变化下实验结果分析实验中，取前7个属性构成准标识符，将属性Occupation作为敏感属性，Occupation不同属性值的个数为14个。实验中数据集Adults的记录数n=30162，LK-member、LCA-FC和LCA-RC算法的l-多样性模型参数l分别取值为2，3，4，5，6。总体信息损失、可区分度量和运行时间三种实验结果分别如图2-1、图2-2和图2-3所示。图2-1 总体信息损失图2-1的实验结果

35、反映了匿名化数据产生的总体信息损失。由于LK-member总是选择与整个聚类信息损失最小的记录来生成聚类，随着l值的增大，生成的聚类所包含记录个数增多，记录的准标识符属性值可能会被泛化到更大的值区域，这将会引起更多的总体信息损失。而LCA-FC和LCA-RC算法总是选择与聚类质心信息损失最小的记录生成聚类，随着l值的增大，总体信息损失增长较平稳。LCA-FC算法由于采用选择距离上次种子记录最远的记录作为聚类种子记录，并且在较大的候选集中寻找信息损失最小记录的策略，因此获得比LCA-RC算法小一些的总体信息损失。图2-2 可区分度量图2-2的实验结果表明，由于可区分度量只与聚类大小有关，LCA-

36、RC算法总是从与聚类中各记录敏感属性值不相同且记录数最多的一个敏感属性值上的所有记录中选择信息损失最小记录加入聚类，较大地减少了剩余记录的产生，生成较多的聚类，聚类也较小，因而DM值较小，从而获得了较好的可区分度。LK-member算法和LCA-FC算法产生剩余记录较多些，因此可区分度相对较差些。图2-3 运行时间图2-3的实验结果表明，LCA-FC和LCA-RC算法的运行时间较少，而LK-member算法的运行时间较多。这是由于LK-member算法需要计算整个聚类和每个候选记录的信息损失，而LCA-FC和LCA-RC算法只需计算聚类质心和每个候选记录的信息损失，并且采用聚类记录候选集。因此

37、，LK-member算法所花费的时间较多。此外，LCA-FC算法生成的候选集相对来说比LCA-RC算法大一些，寻找信息损失最小记录所花的时间也多一些，因此，LCA-FC算法所需的运行时间比LCA-RC算法的运行时间多一些。2.3.2 准标识符维数变化下实验结果分析实验中数据集Adults的记录数n=30162，l=4，LK-member、LCA-FC和LCA-RC算法分别取前Age，Work Class，Education，Marital Status，Race，Sex，Country ，Occupation 属性中前2，3，4，5，6个属性构成准标识符，将属性Occupation作为敏感属性

38、，Occupation不同属性值的个数为14个。总体信息损失、可区分度量和运行时间三种实验结果分别如图2-4、图2-5和图2-6所示。图2-4 总体信息损失图2-4表明LK-member、LCA-FC和LCA-RC算法的总体信息损失均随准标识符维数增加而增加。这是由于随着准标识符维数的增加，数据泛化时需要在等价类更多属性上进行泛化，相应地，总体信息损失也增多。图2-5 可区分度量图2-5的实验结果表明，LK-member和LCA-FC算法可区分度量的值均随准标识符维数增加而增加，而LCA-RC算法可区分度量的值变化较小。随准标识符维数增加，LK-member和LCA-FC算法生成的等价类越大，

39、可区分度越小。而LCA-RC算法产生的剩余记录少，生成等价类数目较多，大小变化不大，因而获得的可区分度变化不大。图2-6 运行时间图2-6的实验结果表明，LK-member、LCA-FC和LCA-RC算法的运行时间均随准标识符维数增加而增加。这是由于随着准标识符维数的增加，生成等价类所进行的计算和比较工作增加，因此所花费的时间也较多。2.3.3 数据集记录个数变化下实验结果分析实验中数据集Adults的记录数n=30162，l=5，LK-member、LCA-FC和LCA-RC算法分别取数据集记录个数分别为5000，10000，150000，20000，25000，30162。将属性Occup

40、ation作为敏感属性，Occupation不同属性值的个数为14个。总体信息损失、可区分度量和运行时间三种实验结果分别如图2-7、图2-8和图2-9所示。图2-7 总体信息损失图2-7反映了 LK-member、LCA-FC和LCA-RC算法的总体信息损均随着数据集记录数增加而增加。由于匿名数据集的总体信息损失是所有等价类信息损失的和，在固定的l值下，随着数据集记录数增加，所生成等价类数目增多，总体信息损失也随之增加。图2-8 可区分度量图2-8反映了 LK-member、LCA-FC和LCA-RC算法可区分度量的值均随着数据集记录数增加而增加。由于可区分度量的值即为数据集中每一个等价类大小

41、的平方的和，随着数据集记录数增加，所生成等价类数目也增多，可区分度量的值也随之加大。图2-9 运行时间图2-9给出了|QI|和l值固定时，数据集大小对LK-member、LCA-FC和LCA-RC算法运行时间的影响。随着数据集记录数增加，生成等价类数目也增多，计算工作量增大，因而 LK-member、LCA-FC和LCA-RC算法运行时间均随着数据集记录数增加而增加。2.4本章小结针对基于k-匿名模型的聚类算法中存在着敏感属性隐私泄露的问题，本章提出了满足l-多样性模型的聚类算法LCA-FC和 LCA-RC。算法所生成的匿名数据集中每个聚类至少有l个不同的敏感属性值，每个聚类的大小介于l和2l

42、之间，满足最优划分并提高数据的安全性。在聚类前生成候选记录集以减少不必要的计算和比较，总是选择与聚类质心信息损失最小的记录生成聚类，以提高算法效率并减少信息的损失。实验结果表明，LCA-FC和LCA-RC算法具有较高执行效率，生成的匿名数据具有较好的可用性。本章的主要研究成果已被中文核心期刊计算机工程与设计录用，即将刊登发表在该期刊上45。第三章 多敏感属性的匿名化算法3.1问题的提出本章讨论多敏感属性数据的匿名化。为了解决数据发布中的隐私泄露问题，k-匿名模型要求等价类的每个记录在准标识符上有相同的属性值，防止了个体身份的泄露。但是，k-匿名模型没有考虑到敏感属性值的多样化，存在着敏感属性隐

43、私泄露的风险。文献4提出l-多样性模型弥补了k-匿名模型的缺陷，要求每个等价类中敏感属性足够多样性以避免敏感属性的隐私泄露，实现单一敏感属性的数据发布。然而，在现实当中，数据集中往往包含不止一个的敏感属性，如果将单一敏感属性的匿名化方法应用于多敏感属性的数据集，将会造成信息的损失和隐私的泄露。例如，假设网上发布了一个如表3-1的医疗信息表，准标识符为属性组(年龄，性别，邮编 )，敏感属性为疾病和工作级别。例如，将单敏感属性的匿名化方法应用于表3-1获得表3-2的3-多样化表，生成了3个等价类t1，t2，t7，t4，t5，t9，t3，t6，t8。每个等价类中的记录在准标识符上具有相同的属性值，并

44、且在敏感属性疾病上具有3个不同属性值。但是表3-2只满足了敏感属性疾病的3-多样性而忽略了另一个敏感属性工作级别，观察等价类t1，t2，t7，在敏感属性疾病上具有3-多样性，但在敏感属性工作级别上却具有相同的敏感属性值。因而，表3-2中的匿名数据存在着隐私泄露的风险。表3-1医疗信息表年龄性别邮编疾病工作级别t141女734531失眠无薪t240女734552心脏病无薪t341男734532失眠私营t444男734555心脏病联邦政府t543男734555失眠州政府t645男734532心脏病地方政府t742男734561胃炎无薪t842女734533禽流感联邦政府t943男734553禽流感

45、从未工作t1040女734531胃炎自雇表3-2 3-多样化表1年龄性别邮编疾病工作级别t140-41*7345*失眠无薪t240-41*7345*心脏病无薪t740-41*7345*胃炎无薪t443-44男73455*心脏病联邦政府t543-44男73455*失眠州政府t943-44男73455*禽流感从未工作t340-45*73453*失眠私营t640-45*73453*心脏病地方政府t840-45*73453*禽流感联邦政府t1040-45*73453*胃炎自雇此外，即使多敏感属性匿名数据集等价类各个敏感属性对于准标识符属性分别满足l-多样性，也不能完全保证多敏感属性的l-多样性。例如表

46、3-3是表3-1的针对敏感属性疾病和工作级别的一个满足3-多样化模型的匿名化处理结果。表3-3中生成了3个等价类t1，t3，t4，t8，t2，t5，t10，t6，t7，t9。每个等价类中的记录在(年龄，性别，邮编 )上具有相同的属性值，并且分别在敏感属性疾病和工作级别上具有3个不同值。但是观察等价类t1，t3，t4，t8，如果攻击者根据杰克的准标识符属性值知道杰克对应的记录在等价类t1，t3，t4，t8中，若攻击者还知道杰克在敏感属性疾病上的值不是“失眠”，那么攻击者就可以推断出杰克在敏感属性工作级别上的值为“联邦政府”。由于等价类t1，t3，t4，t8中敏感属性疾病和工作级别的值之间缺乏多样

47、性，表3-3中的匿名数据依然存在着敏感属性隐私泄露的风险。表3-3 3-多样化表2年龄性别邮编疾病Workclasst141-44*73453*失眠无薪t341-44*73453*失眠州政府t441-44*73453*心脏病联邦政府t841-44*73453*禽流感联邦政府t240-43*7345*心脏病无薪t540-43*7345*失眠州政府t1040-43*7345*胃炎自雇t642-45男7345*心脏病地方政府t742-45男7345*胃炎无薪t942-45男7345*禽流感从未工作文献4给出了一个多属性l-多样性的概念。定义4-14：（多属性l-多样性）假设T表由准标识符属性Q1，Q

48、m1和敏感属性S1, , Sm2构成。若对于每一个Si （i=1，m2）为敏感属性， Q1，Qm1, S1, , Si-1, Si+1, , Sm2为准标识符属性时表T是l-多样性，那么表T是l-多样性。多属性l-多样性规则也存在一些不足，当敏感属性的维数增加时，需要越来越大的等价类来确保敏感属性的l-多样性，那么泛化等价类准标识符属性时也将导致更多的信息损失。并且，文献4虽然提出了一个多属性l-多样性的概念，但没有作更深入的探讨，也没有给出算法实现多个敏感属性的数据发布。因此，在文献4、5的基础上，本章提出并实现一个满足多敏感属性l-多样性的匿名化算法MSAL (multivariate s

49、ensitive attribute l-diversity)，以提高数据的安全性。3.2 基于l-多样性模型的多敏感属性匿名化算法设计与分析基于l-多样性模型的多敏感属性匿名化算法MSAL的主要思想是：首先确定数据集中n个敏感属性的主次，然后按n个敏感属性主次序的逆次序分别对数据集进行排序，使得n个敏感属性各自属性值相同的记录尽可能排在一起。然后按照第一敏感属性值的不同，将数据集记录分到若干个桶中，使得每个桶中的记录拥有相同的第一敏感属性值。按记录数从大到小对桶进行排序, 得到非空桶BK1, BKbknum，如果非空桶的数目bknuml，每次总是从最大桶BK1中取出一个记录，然后按从大到小的

50、顺序在其余桶中选择寻找l-1个记录生成记录数为l的等价类，要求等价类中每个敏感属性的l个属性值都不同。然后重新对桶排序，重复相同的过程建立下一个等价类。最后，将剩余记录分到生成的等价类中，控制加入剩余记录的等价类的大小介于l和2l-1之间，并且也要求加入剩余记录的类每个敏感属性满足最频繁敏感值出现的次数与该类记录数之比小于等于1/l。采用文献5中的方法，将结果分成多张数据表发布，其中一张表包含等价类ID和各准标识符属性等字段，其余每张表包含等价类ID、一个敏感属性、敏感属性值计数等字段，准标识符属性表与各敏感属性表之间通过等价类ID关联。算法中信息损失采用1.2.3小节定义的信息损失机制来衡量

51、。基于l-多样性模型的多敏感属性匿名化算法MSAL形式描述如下：算法3.1 基于l-多样性模型的多敏感属性匿名化算法MSAL 输入：原始数据集T，敏感属性个数n和l-多样性模型参数l；输出：符合多个敏感属性l-多样性要求的匿名数据集tableBeginStep1: 确定数据集中n个敏感属性及n个敏感属性的主次。分别计算各敏感属性的不同敏感属性值个数；if (T中各敏感属性的不同敏感属性值个数<l) then不能满足l-多样性，return T;end if;按n敏感属性次序的逆次序，从最后一个敏感属性开始，分别对数据集进行排序；按照第一敏感属性值的不同，把数据集T的记录分到桶BK中,桶的

52、数目bknum；按记录数对非空桶进行排序, 得到非空桶BK0, BKbknum-1；最大桶maxbk =BK0;匿名数据集table=；Step2: while (非空桶的数目bknum>=l&&各敏感属性的不同敏感属性值个数>=l) do r=从最大桶maxbk中随机选择一个记录；等价类C=r;最大桶maxbk=最大桶maxbkr;for (i=1; i<bknum;i+) do max=0;for(j=0;j<第i个桶的记录数目;j+)dorec=第i个桶中第j个记录；for(k=0;k<等价类C的记录数;k+)do如果rec记录与等价类C所有

53、记录在n-1个敏感属性的属性值完全不相同, 则 record= rec， record为符合条件的记录，退出循环变量为k,j的循环；否则回到j循环，继续从第i个桶中寻找符合条件的记录；end forend for;如果不存在符合条件的记录record，回到i循环，从下一个桶中寻找符合条件的记录；否则，聚类C=聚类C符合条件的记录maxrecord ;从找到符合条件记录的桶中删除该记录;如果等价类C的记录数等于l，退出i循环；end for;匿名数据集table=table生成的等价类C;重新按记录数对非空桶进行排序, 计算非空桶的数目bknum,得到非空桶BK0, BKbknum；最大桶maxbk =BK0;重新计算各敏感属性的不同敏感属性值个数；end whileStep3: 数据集LS=聚类后剩余的记录；while (|LS|0) dor=从LS中随机取记录r;tnum=匿名数据集table中的等价类个数;for (i=1,tnum) do如果第i个等价类的记录数>2l-1，则该等价类停止参与计算；如果将记录r加入类i仍然满足每个敏感属性最频繁敏感值出现的次数与该等价类记录数之比小于等于1/l，第i个等价类符合条件