K-匿名隐私保护相关技术的研究

【摘要】在数据领域，k-匿名技术是一种简单有效的隐私数据保护技术。因此国内外专家学者们对匿名化技术开展了广泛深入的研究工作以寻求防止或减少隐私泄露的有效方法。本文根据已有的一些研究结论，阐述了匿名化技术的一般概念、匿名化原则、匿名化方法和匿名化度量等方面，并且介绍了两种经典的匿名化算法。

【关键词】数据；匿名化技术；k-匿名

1.引言

计算机处理能力、存储技术及网络技术的快速发展，信息技术在组织中发挥的作用日益增加，一方面，使得信息共享较之以前来得更为容易和方便，以数据库为基础的应用系统成为经济、金融、医疗等领域的信息基础设施，大大地提高了组织的信息化程度；但是另一方面，这也使得数据库系统面对更多的安全威胁，随之产生的隐私信息泄露现象屡见不鲜，越来越多的因故意或疏忽造成的数据泄露的例子，使人们对数据库中的隐私保护问题日益重视。信息化过程中如何在实现有效的信息共享的同时，有效地保护私有敏感信息不被泄漏，已成为信息安全领域一个活跃的研究方向。Cox在1980年最先提出使用匿名的方法实现隐私保护，1986年Dalenius在针对人口普查记录集的隐私保护应用了匿名技术。自从匿名化概念提出以来，很多国内外的学者对匿名化技术开展了广泛的研究。例如L.Sweeney提出了一种用来保护私有信息的k-匿名模型[1]。Ji-Won Byun，Ashish Kamra，Elisa Bertino，and Ninghui Li在2007年提出了基于聚类的高效k-匿名话算法[2]。在这篇文章中提出，k-匿名问题不需要有簇的数量的限制，但是每个簇中至少含有k条记录，所以，提出可以把k-匿名问题当作聚类问题，被称为k-member clustering problem。现在生活中，人们都很注重隐私保护，尤其像是在医院和银行这种场合，大多数人可能并不愿意让别人知道自己的具体情况，所以怎样既可以做到不泄漏个人的隐私，又可以利用医院和银行中的个人信息做科学研究，这种问题正是我们研究匿名信息的重要意义所在。

下面文章将在第2部分介绍数据和匿名的相关概念及定义，第3部分介绍常见的匿名算法，第4部分小结。

2.相关概念，相关定义

2.1 匿名技术[3]

匿名技术：是身份隐藏中最直接的技术。它作为隐私保护的数据挖掘技术不对数据挖掘结果进行保护，也不将原始数据进行隐藏伪装，而是公布带隐私的所有数据，但是他人拿到隐私数据却不能推导出该数据拥有者的身份。

2.2 匿名技术相关定义[4]

定义1：属性

令：B(A1，…，An)是一个有限数量元组的一个表，B的有限元属性元组是{A1，…，An}。

假设表B(A1，…，An)，{Ai，…，Aj}{A1，…，An}，有一个元组t∈B，用t[Ai，…，Aj]来表示t中Ai，…，Aj的值vi，…，vj的有序序列。用B[Ai，…，Aj]来表示投影，维持B中属性Ai，…Aj的元组复制。

定义2：类标识符

假设一个实体集U，一个特定的实体表T(A1，…，An)，fc:UT以及fg:TU'，其中UU’.T的一个类标识符记为QT，是一组属性{Ai，…，Aj}{A1，…，An}其中:pi∈U所以fg(fc(pi)[QT])=pi.成立。

定义3：k-匿名

RT(A1，...，An)是一个表QIRT是与RT有关联的类标识符，并且仅当在RT[QIRT]中出现的每一个有序的值至少要在RT[QIRT]中出现k次的话，就说RT满足k-匿名。

推论：

假设RT(A1，...，An)为一个表，QIRT=(A1，...，An)是与RT相关联的类标识符，Ai，...，AjA1，…，An，RT满足k-匿名，那么在RT[Ax]中出现的每一个值的有序序列至少要在RT[QIRT]中出现k次，x=i，...，j。

2.3 信息度量相关定义

2.3.1 k-匿名问题转换成聚类问题[2]

定义1：k-member clustering problem

k-member clustering problem需要从给出的n条记录中寻找一组簇，每个簇中至少含有k(k

1)

2)

3)

4)

|e|表示簇e的大小，表示在第i个数据项，Δ(x，y)表示数据x和y的距离。

2.3.2 距离函数

每个聚类问题的核心是用距离函数处理各个数据点的不同和使成本函数在聚类问题中最小。

数据通常有数值型数据和类别型数据，对于数值型数值，描述两个数据之间的差异就是两个数据的价值差异。这种处理方法同样适用于处理k-匿名问题中的数值型数据。

定义2：数值型数据距离函数

用D表示有限的数值域，数据v1，v2（v1，v2∈D）之间的距离可以定义为：

其中v1，v2为两数值型数据，|D|为有限数值域D的区间大小。

类别型数值可以用类别树表示，假设类别树的每个叶子节点代表在域中的所有不同的值。

定义3：类别型数据距离函数

用D表示类别型数据的域，TD表示根据D所定义的类别树，数据v1，v2（v1，v2∈D）之间的距离可以定义为：

H(T)表示树T的高度，∧(x，y)表示树中结点x和y的最小共同祖先结点。

定义4：两个数据的距离

令QT={N1，…，Nm，C1，…，Cn}为表T的准标识符属性，Ni（i=1…m）为数值属性，Cj(j=1…n)为类别属性，所以两个数据r1，r2，(r1，r2∈T)之间的距离可以定义为：

ri[A]表示记录ri中属性A的值，δN和δC是在定义2和定义3中定义过的距离函数。

2.3.3 成本函数

聚类问题的最终目的是k-匿名问题的数据，通过定义成本函数表示因为泛化过程导致的信息失真（信息丢失），所以成本函数越小越好。簇中的记录被泛化是根据每个簇中相同的原准标识符。假设数值型数据被泛化成一个区间[最小，最大][5]，类别型数据簇中的数据都是有明显区别的集合[6]。根据以上的想法，定义了代表信息丢失的准标识（IL）。

定义5：信息丢失

设e={r1，…，rk}是一个簇(等价类)，准标识属性包含数值型数据和类别型数据QT={N1，…，Nm，C1，…，Cn}，TCi是属性Ci的分类树。MINNi、MAXNi分别为类e中属性Ni的最小、最大值。∪Ci是类e中属性Ci的值集合。所以信息丢失可以定义为：

，

|e|表示簇e中的数据量，|N|表示数值型数据域的大小，H(T)表示树T的高度，∧(∪Cj)表示树中结点∪Cj中所以值的最小共同祖先结点。

根据上面的定义，可以把匿名表的总信息丢失定义如下。

定义6：总信息丢失

设ε为匿名表AT中所有等价类集合，所以总信息丢失量可以定义为：

Total-IL(AT)=

信息损失度量公式中的数值属性度量方法只反映了每一类中属性值的覆盖广度，并没有反映出原始准标识符属性和泛化后的属性值之间的差异关系。

3.常见的匿名技术和算法

3.1 常见的匿名技术

基于属性层次的泛化匿名技术，如全域泛化[4][7]，局部泛化[8]，单层泛化[4][7][9]和多层泛化[8][10]；基于聚类的匿名技术[2][11]；基于划分的方法[5]；基于幂集搜索的方法[6]。

3.2 常见的匿名算法

k-匿名自提出以来，得到了学术界的普遍关注，国内外很多学者都从不同层面研究和发展了该技术。其中以K.LeFevre和Raghu Ramakrishnan等人提出的Mondrian[5]和Incognito[7]为比较经典的k-匿名算法。

3.2.1 Mondrian算法

文献[5]提出了多维k-匿名的概念，根据kd-tree的分割方法提出了Mondrian算法，该方法允许同一时刻在多维类身份属性上进行泛化处理。多维k-匿名从全局泛化(global recoding)和局部泛化(local recoding)的角度归纳出两种多维划分模型——严格多维划分和宽松多维划分。这两种模型用d维空间来表示准标识符属性X1，X2，…，Xd，将每条元组根据各属性值映射为多维空间的一个点，因此一张表就是一个点集。

与单维划分对各属性的域分别作划分不同，多维划分模型将所有属性域作为一个整体进行分割。严格多维划分在各属性域的笛卡尔积DX1×…×DXd上定义一个划分，也就是把多维空间分割为多个互不重叠的区域，并将数据点映射为它们所在的那个子空间。宽松多维划分则是在DX1×…×DXd上定义互不相同的多维区域，可以有重叠，并将每个数据点映射为它所在区域中的一个。

3.2.2 Incognito算法

文献[7]提出了Incognito算法，Incognito是一种广泛应用的k-匿名算法，能够产生给定表的所有可能的k-匿名全域泛化（一种全局重编码技术）。算法首先检查QI属性中的单属性子集是否满足k-匿名，然后迭代地检查QI属性的多维属性子集，每次迭代，用于检查的属性子集宽度增加1。迭代过程包含两个主要的部分：寻找k-匿名泛化点、候选点和边的生成。

每轮迭代从一个由若干候选多属性泛化模式构成的图开始。第i次迭代的泛化模式由若干宽度为i-1的QI属性集生成，记作Ci。图中表示直接泛化关系的连接边的集合记作Ei。算法对图中的候选点进行宽度优先搜索，通过判断原始表在候选点上是否满足k-匿名，筛选出宽度为i的多属性泛化模式，记作Si。

算法从Si生成宽度为i+1的候选点集Ci+1和直接泛化连接边Ei+1。Incognito的第i轮迭代使用一种经过改进的自底向上的宽度优先搜索搜索来判断原始表T在候选泛化模式集Ci上的k-匿名状态。搜索开始于候选泛化图中没有边指向的“根”节点，算法通过自底向上地集成来得到各点上的元组计数。这种宽度优先搜索同时也是基于“泛化性质”的，如果原始表在某点上是k-匿名的，则该点的所有有连接的上层点也能使表满足k-匿名。因此，当搜索算法发现匿名点，就将其直接泛化点做标记，并且后面的计算中不再予以考虑。

4.结束语

随着计算机技术的发展，人们现在可以很容易的就取得自己想要的信息。但是，伴随而来的就是隐私数据泄露的问题，这可能会侵害数据所有者的利益。为了能够使用已的数据信息并且又可以不侵害信息所有者的利益，这是我们所关心的，这也正是我们做此项研究的目的和意义。

参考文献

[1]L.Sweeney,L,k-aonyfnjty:a model for privacy[J].IntemationaI JoumaI on Uncertainty Fuzziness and Knowledge based Systems,2002,10(5):557-570．

[2]J.-W.Byun,A.Kamra,E.Bertino and N.Li,Efficient k-anonymization using clustering techniques,in:Proceedings of Database Systems for Advanced Applications(DASFAA2007),LNCS4443.Berlin:Springer-Verlag,2007:188-200.

[3]马延淮,唐美丽.基于隐私保护的数据挖掘[J].计算机工程,34(9):78-80.

[4]L.Sweeney.Achieving k-anonymity privacy protection using generalization and suppression.International Journal on Uncertainty,Fuzziness and Knowledge-based Systems,10(5),2002:571-588.

[5]K.LeFevre,D.DeWitt and R.Ramakrishnan,Mondrian multidimensional k-anonymity,in:Proceedingsof the International Conference on Data Engineering(ICDE),Atlanta,GA,USA,2006.

[6]R.J.Bayardo and R.Agrawal.Data privacy through optimal k-anonymization.In International Conference on Data Engineering,2005.

[7]K.LeFevre,D.DeWitt and R.Ramakrishnan,Incognito:Efficient full-domain k-anonymity,in:Proceedings of the ACM SIGMOD International Conference on Management of Data(SIGMOD),Baltimore,MD,USA,2005.

[8]B.C.M.Fung,K.Wang and P.S.Yu,Top-down specialization for information and privacy preservation,in:Proceedings of the International Conference on Data Engineering(ICDE),Tokyo,Japan,2005.

[9]P.Samarati,Protecting respondents’privacy in microdata release,IEEE Transactions on Knowledge and Data Engineering 13(2001),1010-1027.

[10]V.S.Iyengar,Transforming data to satisfy privacy constraints,in:Proceedings of the ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining(KDD),Edmonton,AB,Canada,2002.

[11]G.Aggrawal,T.Feder,K.Kenthapadi,S.Khuller,R.Panigrahy,D.Thomas and A.Zhu,Achievinganonymity via clustering,in:Proceedings of the ACM Symposium on Principles of Database Systems(PODS),Chicago,IL,USA,2006.

基金资助：国家自然科学基金面上项目（项目编号：61070131，71172190）；教育部人文社会科学研究项目基金（项目编号：09YJC870001，12YJA630136）；安徽高校省级自然科学研究重大项目资助（项目编号：KJ2010ZD01）；安徽财经大学大学生创新基金（项目编号：45）。

作者简介：

张雪松（1989—），男，现就读于安徽财经大学管理科学与工程学院。

徐勇（1978—），男，博士，安徽财经大学管理科学与工程学院副教授，硕士生导师，目前主要研究数据库技术、数据挖掘、隐私保护。