论文部分内容阅读
信息时代迅速发展的今天,越来越多的数据被人们所共享使用,与此同时对于被发布数据的隐私保护也越来越受到人们的重视,因此,在发布数据的时候,我们既要保护这些数据中的隐私,同时也要尽量保证这些数据的完整性以供人们使用。一种叫做K-匿名的方法被提出来,这种方法通过对原始数据进行泛化或者抑制使其形成容量至少为K的簇,从而使得每条元组与至少其他K-1条记录不能够相区别。K-匿名方法简单易懂,并且易于实现,能够在保护病人隐私的同时,有效减少信息的损失量。K-匿名算法中的一种比较高效的算法叫做最优格匿名算法(Optimal Lattice Anonymization简称OLA),此算法使用一种叫做格(Lattice)的结构,通过遍历此结构中的节点从而最后得到最优结果,然而OLA算法的遍历节点顺序并不能够最大程度上减少需要计算的Lattice节点的数量,这增加了算法的运行时间,同时由于源数据中孤立数据的存在,使得一次全局K-匿名算法处理后的数据并不能够在信息损失量上达到很好的效果。本文的工作是对OLA算法从以上两个方面做了改进,从而使得算法达到更好的效果,以下三点工作的前两点是针对减少算法运行时间来对算法进行改进的,最后一点是针对减少信息损失量来对算法进行改进的。1.针对OLA算法中Lattice节点遍历顺序的问题,我们提出了根据节点的度的乘积来对需要进行计算的节点进行排序的方法,实验表明这种方法能够在一定程度上减少计算K-匿名节点的数量从而减少算法运行时间。2.针对需要计算的Lattice节点的数量,我们运用K匿名的子集性质对OLA算法进行改进,改进后的方法能够在判断每个非匿名节点之后标记(去除)更多的非匿名节点,从而减少计算K-匿名节点的数量。3. OLA算法在信息损失量上并不能够达到令人满意的效果,原因是被处理数据中存在着孤立数据,我们采取二次K-匿名的方法对数据进行分块,从而将孤立数据和非孤立数据分离,然后在非孤立数据上再次运行K-匿名算法,最后将两块数据的信息损失量相加。结果表明,这种方法的信息损失量能够大量减少。