多敏感属性K-匿名模型的实现∗

王静 闫仁武 刘亚梅

（江苏科技大学计算机科学与工程学院镇江212003）

多敏感属性K-匿名模型的实现∗

王静 闫仁武 刘亚梅

（江苏科技大学计算机科学与工程学院镇江212003）

L-MDAV算法结合L-多样性模型和MDAV微聚集算法来实现K-匿名模型，但是L-MDAV算法只考虑了单一敏感属性下的约束，而在实际发布的数据中不可能只有一个敏感属性，论文在该算法的基础上提出了基于多敏感属性的MDAV算法，文中仅以两种敏感属性为例，因此算法命名为（L1，L2）-MDAV算法。论文在根据用户不同敏感属性的不同保护需求下为用户个性化定义敏感属性的敏感度。实验结果表明，论文提出的算法相比于L-MDAV算法能够更好地保护隐私数据安全。

多敏感属性；K-匿名；L-多样性；微聚集算法

Class NumberTP3-05

1 引言

在享受信息技术快速发展所带来的便捷的同时，我们暴露了大量与个体相关的数据。这些数据被各个部门或者研究机构收集并且发布，这一趋势所带来的危害是更多的个人隐私数据得不到保护，造成大量的隐私泄露。

为了保护数据发布过程中隐私数据的安全，研究者们提出了数据匿名发布技术，先后出现了K-匿名模型［1］、L-多样性模型［2］、T-接近模型［3］等匿名隐私保护模型。

上述几种模型通常采用泛化［4］技术来实现，然而通过泛化技术得到的数据质量无法得到保证，往往失真度较高，且算法的时间复杂度较大。因此，微聚集算法应用于隐私保护模型得到大量研究［5］。

考虑到实际应用中发布的数据不可能只有一个敏感属性，因此本文在实现单敏感属性L-多样性的L-MDAV算法［6］的基础上提出了基于多敏感属性［7］的L-多样性的MDAV算法。本文的算法适合多敏感属性，但是为了更好地描述，文中以两个敏感属性为例，因此算法命名为（L1，L2）-MDAV算法。

2 相关概念

定义1（准标识符）给定一个表T，当通过一组属性集合与外部表链接可以获得识别个体的元组信息，则称该属性集合为表T的准标识符。

定义2（K-匿名）给定表T中的一个元组，如果表中有至少K-1个元组与该元组存在相同的准标识符，则称该元组满足K-匿名。

定义3（K-划分）给定一个表T，将该表基于准标识符划分成g个类，其中每个类的元组个数要大于等于K，称满足这类划分的表为K-划分。

定义4（聚集）将给定的表基于该表的准标识符进行K-划分为g个类，用每个类的质心来代替给定数据表每个类的所有元素称为聚集。

定义5（L-多样性）对于给定的表T，若该表的等价类中至少含有L个“表现良好“［8］的敏感属性，则称该等价类满足L-多样性模型。

表1 原始数据表

表1所示为原始的发布数据，name是显式标识符，｛age，sex，zipcode｝是准标识符，disease是敏感属性。表2是表1的2-多样性表。

表2 多样化后的数据表

3 度量空间

对于给定的表T，其属性又分为连续型和分类型属性，本文重点以连续型属性为例来实现K-匿名模型。

3.1 数据标准化

考虑到不同的连续型属性会有不同的单位以及不同的取值范围，比如年龄通常取值是两位数，而邮编如45000，这样两个取值范围差距较大的不同属性值往往会对结果造成较大的差异，导致不能准确地衡量两个元组之间的实际距离。本文首先对数据进行预处理，去除异常值，然后用式（1）对预处理后的数据进行标准化来提高实验结果的可靠性。本文选择用极差法［9］将全部属性值映射到［0，1］区间，公式如下：

其中X为新数据，x为原数据，Xmin是属性X取值的最小值，Xmax是属性X取值的最大值。

3.2 距离度量

假设元组i和元组j经过数据标准化处理后表示为Xi=(xi1，xi2，…，xip)，Xj=(xj1，xj2，…，xjp)元组为p维向量，则元组Xi和元组Xj之间的距离用欧几里得距离公式表示为

3.3 微聚集算法的评价标准

3.3.1 数据的信息损失

本文采用EM4ADOM模型［10］来计算数据信息损失量。本文主要描述连续型数据，分类型数据的距离和信息损失度量见文献［11］。

类的同质性测度SSE如式（3）所示：

其中g为类的个数，ni为第i类的元组个数，

数据表同质性测度SST如式（4）所示：

给定一个数据表，该表的同质性测度SST是不会变的，但是对于不同的算法或者不同的参数值所划分的表SSE是不同的。因此信息损失量IL用式（5）计算

3.3.2 数据泄密风险

本文用基于距离的记录链接（DLD）模型［12］来衡量匿名表中数据泄密风险。

定义6（链接成功）从匿名表中任意选择一个元组r，计算出原始表中所有的元组到r的距离，把最近的元组记为r（1），第二近的元组记为r（2），如果r是由若r（1）（或者r（2））匿名化得到的，则称r链接成功。

设匿名表共有M条记录，其中有N条链接成功的记录，则DLD模型的泄密风险值用式（6）计算：

4 基于多敏感属性的（L1，L2）-MDAV算法

4.1 多敏感属性匿名模型的发布方法

基于多敏感属性的（L1，L2）-MDAV算法，本文说明仅以两个敏感属性为例，多个敏感属性方法以此类推。首先为两个敏感属性定义敏感度，不同的用户所要保护的敏感属性的级别是不同的，因此，用户可以根据自身需求定义不同敏感属性的敏感度，再根据不同的L值对敏感数据实行不同的级别约束，以满足用户的个性化需求。表3以两个敏感属性disease和occupation为例，将disease定义更高的敏感度。

表3 敏感属性的敏感度以及l值

表4 原始数据表

表4中｛age，zipcode｝为准标识符，disease和oc-cupation为敏感属性。表5是表4的（3，2）-多样性表。

表5 多样化后的数据表

4.2 （L1，L2）-MDAV算法

输入：待发布数据表T，两个不同敏感属性的多样性参数L1，L2

输出：满足多敏感属性（L1，L2）-多样性约束的匿名表T′

步骤：

1）T′=T；

2）计算数据表T中所有记录的中心xˉ；

3）找出数据表中离中心xˉ最远的记录r；

4）在表T′以r为中心，找出离r最近的K-1条记录与r组成一个类，并且要求类中第一敏感属性和第二敏感属性分别满足L1-多样性和L2-多样性；

5）从表T中删除这些记录；

6）若表T中剩下记录第一敏感值的多样性大于2L1且第二敏感属性值的多样性大于2L2，则执行步骤2）；

7）若表T中剩下的记录第一敏感属性值多样性在［L1，2L1-1］或者第二敏感属性值多样性在［L2，2L2-1］中，则剩下的记录归为一类；

8）否则，将表T中剩下的记录分别计算到所有类中心的距离，选择距离最小的类进行插入；

9）输出满足多敏感属性（L1，L2）-多样性约束的匿名表T′。

5 实验结果与分析

本文实验平台为Core2.2GHz/4GB，Windows7，涉及的代码使用Matlab实现。采用census微数据［13］集作为测试数据，实现了MDAV，L-MDAV以及本文提出的（L1，L2）-MDAV三种算法在该数据集下的信息损失量与数据泄密风险的比较。

5.1 信息损失量比较

5.1.1 L值不变，随K值的变化情况

图1各算法信息损失量随k变化情况

信息损失量采用式（5）计算，由图1可以看出K值变大，三种算法的信息损失均会变大，这是因为类越大，类的同质性会越大，因此信息损失量会变大。固定K值，三种算法的信息损失量由小到大依次是MDAV、L-MDAV、（L1，L2）-MDAV，这是因为三种算法的约束性是越来越强，类的平均大小会有所增加，因此数据的信息损失也会增加。

5.1.2 K值不变，随L值的变化情况

图2固定K值与约束L2的值，通过一个敏感属性的多样性参数的变化来比较L-MDAV和（L1，L2）-MDAV两种算法的信息损失。可以看出，L值变大，信息损失量也会变大，并且（L1，L2）-MDAV算法的信息损失量较L-MDAV大，因为（L1，L2）-MDAV的约束更强。

图2各算法信息损失量随L变化情况

5.2 泄密风险评估

5.2.1 L值不变，随K值的变化情况

泄密风险采用式（6）计算，图3表明，随着K值的增大，三种算法的泄密风险均变小，且本文提出的（L1，L2）-MDAV算法泄密风险最小，因为该算法是对多敏感属性进行约束，约束性较前两个算法都强，从而使得链接成功的元组数会变少，因此泄密风险减小。可以看出，（L1，L2）-MDAV算法不仅能满足用户对不同敏感属性的个性化保护需求，还能减小发布数据的泄密风险。

图3各算法泄密风险随K变化情况

5.2.2 K值不变，随L值变化情况

图4固定K值和约束L2的值，该图表明两个算法随着L值的增大泄密风险变小，并且（L1，L2）-MDAV算法的泄密风险较L-MDAV算法更小，这是因为增加了第二敏感属性的约束，使得算法约束性更强，从而减小了数据泄密的风险。

图4各算法泄密风险随l变化情况

6 结语

（L1，L2）-MDAV算法在L-MDAV算法的基础上增加了多敏感约束条件。从安全性上看，（L1，L2）-MDAV算法的约束条件更强，因此能达到更好的数据保密效果；从信息损失量上看，（L1，L2）-MDAV算法由于约束性较强，使得数据失真度较高，但是从算法的实验结果来看，该算法与其他两个算法的信息损失量差别不大；从实际出发，在数据发布的过程中，数据不可能只有一个敏感属性，本文提出多敏感属性个性化微聚集算法具有一定的实用价值。总之，本文提出的算法能更好地实现用户的个性化需求，并能保证数据更小的泄密风险，获得更安全的匿名表。

本文选择的微聚集算法是定长微聚集算法MDAV算法，而变长微聚集算法如TFRP［14］、MST［15］等具有聚类质量高的优点，因此论文的下一步工作是研究基于满足多敏感属性多样性的变长微聚集算法，以期得到更高质量的匿名表。

［1］Sweeney L.k-ANONYMITY：A MODEL FOR PROTECT⁃ING PRIVACY 1［J］.International J-ournal of Uncertain⁃ty，Fuzziness and Knowledge-Based Systems，2008，10（5）：557-570.

［2］Machanavajjhala A，Gehrke J，Kifer D，et al.L-diversi⁃ty：privacy beyond k-anonymity［J］.A-cm Transactions on Knowledge Discovery from Data，2006，1（1）：24-24.

［3］张健沛，谢静，杨静，等.基于敏感属性值语义桶分组的t-closeness隐私模型［J］.计算机研究与发展，2014，51（1）：126-137. ZHANG Jianpei，XIE Jing，YANG Jing.A t-c-loseness Privacy Model Based on Sensitive A-ttribute Values Se⁃mantics Bucketization［J］.Journal of Computer Research and Development，2014，51（1）：126-137.

［4］刘乐伟.面向多敏感属性的隐私保护方法研究［D］.北京：北京工业大学，2013. LIU Lewei.Research of privacy preserving methods for multiple seneitive attributes［D］.Beijing：Beijing Universi⁃ty of Technology，2013.

［5］程亮，蒋凡.基于微聚集的a-多样性k-匿名大数据隐私保护［J］.信息网络安全，2015（3）：19-22. CHENG Liang，JIANG Fan.a-diversity and k-anonymity Big Data Pri-vacy Preservation Based on Micro-aggrega⁃tion［J］.Netinfo Security，2015（3）：19-22.

［6］王茜，张刚景.实现单敏感属性多样性的微聚集算法［J］.计算机工程与应用，2015（11）：72-75. WANG Qian，ZHANG Gangjing.Microaggregation algo⁃rithm for single sensitive attribute diversely［J］.Computer Engineering and Applications，2015（11）：72-75.

［7］唐印浒，钟诚.基于变长聚类的多敏感属性概率k-匿名算法［J］.计算机工程与设计，2014（8）：2660-2665. TANG Yinhu，ZHONG Cheng.Probabilistic k-anonymity algo-rithm with multi-sensitive attributes based on variab len-gth clustering［J］.Computer Engineering and Design，2014（8）：2660-2665.

［8］Domingo-Ferrer J，Mateo-Sanz J M，Torra V.Comparing SDC Methods for Microdata on the Basis of Information LossandDisclosure［C］//ProceedingsofETK-NTTS 2001，Luxemburg：Eurostat，2001.

［9］Chang C C，Li Y C，Huang W H.TFRP：An efficient mi⁃croaggregation algorithm for statistical disclosure control［J］.Journal of Systems&Software，2007，80（11）：1866-1878.

［10］陈建明，韩建民.面向微聚集技术的k-匿名数据质量评估模型［J］.计算机应用研究，2010，27（6）：2344-2347. CHEN Jianming，HAN Jianmin.valuation model for q-uality of k-anonymity data oriented to microa-ggre⁃gat-ion［J］.Application Research of Computers，2010，27（6）：2344-2347.

［11］Domingo-Ferrer J，Mateo-Sanz J M.Practical data-ori⁃ented microaggregation for statistical disclosure control［J］.IEEE Transactions on Knowledge&Data Engineer⁃ing，2002，14（1）：189-201.

［12］王茜，甘荣庆.一种高效的微聚集k-匿名算法［J］.世界科技研究与发展，2013，35（1）：38-40. WANG Qian，GANRongqing.An Efficient Micro-aggre⁃gation Algorithm f-or K-Anonymity［J］.World Sci-tech R&D，2013，35（1）：38-40.

［13］Domingo-Ferrer J，Sebé F，Solanas A.A polynomial t-ime approximation to optimal multivariate microag⁃gr-egation［J］.Computers&Mat-hematics with Applica⁃ti-ons，2008，55（4）：714-732.

［14］Laszlo M，Mukherjee S.Minimum Spanning Tree Parti⁃tioning Algorithm for Microaggregat-ion［J］.IEEE Trans⁃actions on Knowledge&Data Engineering，2010，17（7）：902-911.

［15］杨静，王超，张健沛.基于敏感属性熵的微聚集算法［J］.电子学报，2014，42（7）：1327-1337. YANG Jing，WANG Chao，ZHANG Jianpei.Micro-Ag⁃gregation Algorithm Based on Sensitive Attribute Entropy［J］.Acta Electronica Sinica，2014，42（7）：1327-1337.

Implementation of K-anonymous Model with Multi-sensitive Attributes

WANG JingYAN RenwuLIU Yamei
（School of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang212003）

L-MDAV algorithm combined with L-diversity model and MDAV algorithm to implement the K-anonymous mod⁃el，but L-MDAV algorithm only considers the single sensitive attribute，in the actual，released data may not have only one sensitive attribute，so，on the basis of the algorithm the article propose a MDAV algorithm with multi-sensitive attributes.In this paper，with only two sensitive attributes as an example，so the algorithm named（L1，L2）-MDAV algorithm.According to user's protection for dif⁃ferent sensitive attributes have different requirements to define the different values of L.As the experimental results show，the pro⁃posed algorithm can protect the privacy of privacy data perfectly compared with L-MDAV algorithm.

multi-sensitive，attributes，K-anonymous，L-diversity，microaggregation algorithm

TP3-05

10.3969/j.issn.1672-9722.2017.07.029

2017年1月7日，

2017年2月23日

王静，女，硕士研究生，研究方向：信息安全，数据挖掘。闫仁武，男，副教授，硕士生导师。刘亚梅，女，硕士研究生，研究方向：数据挖掘。