基于聚类的高效(K,L)-匿名隐私保护

柴瑞敏,冯慧慧

(辽宁工程技术大学电子与信息工程学院,辽宁葫芦岛125105)

基于聚类的高效(K,L)-匿名隐私保护

柴瑞敏,冯慧慧

(辽宁工程技术大学电子与信息工程学院,辽宁葫芦岛125105)

为防止发布数据中敏感信息泄露,提出一种基于聚类的匿名保护算法。分析易被忽略的准标识符对敏感属性的影响,利用改进的K-means聚类算法对数据进行敏感属性聚类,使类内数据更相似。考虑等价类内敏感属性的多样性,对待发布表使用(K,L)-匿名算法进行聚类。实验结果表明,与传统K-匿名算法相比,该算法在实现隐私保护的同时,数据信息损失较少,执行时间较短。

(K,L)-匿名;敏感属性;隐私保护;信息损失;聚类;K-means算法

1 概述

随着计算机网络和数据库等相关技术的快速发展,医疗、银行账户、电子邮件等各种系统广泛的渗透于生活应用中,应用系统数据库中的个体数据,被过度地用于数据挖掘和数据发布,这就导致个人的隐私信息极易被暴露,用户的隐私安全得不到保障,工作生活受到影响,严重的甚至危及生命。因此,个人的隐私保护成为丞待解决的问题,许多隐私保护方法也被提出。常用方法是在数据发布前,先对数据预处理,把能够显示身份特征的属性(如姓名、身份证号等)去掉,该方法虽然有一定功效,但隐私信息泄露仍然存在。文献[1]研究表明,把美国的选民登记表和去掉身份特征标识的医疗信息表利用邮编、性别、年龄等属性进行链接,至少87%的美国公民的个人信息都可以被检测出来,造成隐私严重泄露。针对数据匿名发布中的隐私泄露问题,本文提出一种基于聚类的匿名保护算法,考虑背景知识攻击和一致性攻击的影响,减少数据匿名后的信息损失。

2 相关工作

为实验数据隐私保护,1998年,K-匿名(K-anonymity)技术被Samarati和L.Sweeney在PODS上率先提出,引起很大关注。K-匿名技术表现为,将每个个体的敏感属性隐藏在规模为K的群体中,方法简单实用,被广泛应用及研究。2002年L.Sweeney又在此基础上提出了K-匿名保护模型[2],将理论高度进一步提升。同时,他又在文献[3]中继续提出针对这一技术的泛化和隐匿方法,此方法在实际应用中,确实对隐私信息起到很大保护作用。2004年Meyerson和Williams指出,即便对表中一些元素隐匿,要保证匿名结果为最佳的K-匿名问题也已经被证明是NP完全问题。

防止隐私泄露常用方法为添加噪声、数据交换和数据隐匿[4],通过对要发布的数据表添加未知元素、把数据隐藏在更宽泛的取值空间内等方法,实现数据的隐私保护目的。从理论上来说,这些方法能起到一定作用,使隐私泄露信息减少,但通常也会发生发布数据失真等现象,使数据发布没有意义。

现有的K-匿名算法大多通过泛化和隐匿技术来实现k-匿名化,易忽略信息泄露问题。文献[5]对K-匿名后的数据进行分析研究,考虑背景知识的影响来分析信息泄露问题,而不同用户对背景知识的掌握常常是参差不齐的,且由此要进行的数据泛化也会产生影响,结果可能会与期望结果大相径庭。因此,为防止基于背景知识的攻击,本文使用基于聚类的高效(K,L)-匿名算法,考虑准标识符属性对敏感属性的影响,先将敏感属性聚类,然后利用K-匿名算法,分析每组数据的敏感属性不同值的个数L与K值之间的关系,有效保护匿名后的秘密属性,防止其隐私信息泄漏。

聚类是依据对象自身的相似性,将一个对象的集合分割成一系列有意义的子集的过程。聚类完成后特征为:每个簇内高度的同质性,每对簇间高度的异质性。典型聚类问题如K-means和K-Center[6]。

3 基本概念

定义1(标识符属性) 在发布的数据中,能直接链接标识一条特定的记录(个体),称之为标识符属性,如姓名、身份证号、银行卡号。

定义2(准标识符QI) 数据表的属性中,除标识符属性外,能够与外部属性相连接的属性集合,称为准标识符[7]。

定义3(K-匿名)T(A1,A2,…,An)是一个表, QI是表T的准标识符,当且仅当在QI对应的每个等价类中,出现的属性个数最少为K(K≥2)时,就说表T满足K-匿名。

定义4(等价类) K-匿名化后,在准标识符属性中对应的每组至少k个相同的元组的集合,称为一个等价类。

定义5((K,L)-匿名) 给定一个表T,如果表T满足K-匿名的要求,并且在准标识符QI上的值相同的一组等价类中,敏感属性不同值至少有L个,则说表T满足(K,L)-匿名,其中,K≥2,1＜L≤K,L,K均取整数。

定义6(参考矩阵) 准标识符对敏感属性影响概率的参考矩阵为J,是m×n型矩阵,其中,m是敏感属性个数;n为准标识符个数;qi(1≤i≤n)是准标识符属性;pi(1≤i≤m)是敏感属性。

其中,Jij为第i个准标识符对第j个敏感属性的影响概率。DISab为任一准标识符对第a个敏感属性和对第b个敏感属性的影响距离:

下面从实例说明(K,L)-匿名。表1是某原始数据表,显示的是个人信息及疾病表。表2是满足表1的2-匿名化表,表3为某人口信息表。表1中对数据先进行预处理,标识符属性如姓名、身份证号等已删除,属性集合(年龄,国家,邮编,性别)是准标识符,疾病为敏感属性。由表2可知该表满足K匿名,且满足L多样性(K=2,L=2)。遇到表3链接攻击时,能有效防止信息泄露。如表3中的第2条信息,名字为tiffany的个人信息与表2链接,不能得出它到底得了什么病,个人隐私得到了有效保护,实现了K-匿名。但是,它忽略了背景知识攻击,比如名字为tom的个人信息与表2链接,虽然不能判断出他得的是什么病,但是通过个人知识了解到,日本人患心脏病的概率及其低微,那么几乎可以肯定地推断出他得的是癌症,而这种病是tom不想为人知的,他的个人隐私因此就被泄露了。而且,与表1相比,表2虽然很好地保护了隐私信息,但是有信息损失。本文的主要研究重点就是要在满足(K,L)-匿名[8]的同时,使要发布的表信息损失降到最少。

表1 原始数据表

表2 2-匿名数据表

表3 人口信息表

4 (K,L)-匿名聚类算法

K-匿名在遇到链接攻击时,能够有效防御,防止隐私信息泄露,但是在遇到同质攻击和背景知识攻击时,却无能为力。为了更好保护敏感信息,增加对数据的L-diversity[9]处理,即(K,L)-匿名聚类算法。

对于输入的数据集,为使发布的数据有意义且使信息损失尽量降低,可分为2个步骤进行:

(1)进行数据集背景知识参考矩阵的计算,各个准标识符对各个敏感属性的影响的强弱均可明显的反应出来。据此对敏感属性进行聚类,本文采用改进的K-means算法,使类内数据更相似,类间数据更不同。聚类结果较传统K-means算法,数据精度更高,能为以下数据匿名化作更好的铺垫。

(2)将数据集中的每条记录初始化为等价类,依据第一步的聚类结果将等价类进行聚类,然后,计算最小化信息损失,对等价类进行合并,K-匿名化要满足生成的等价类大小在K与2K之间。同时判断生成的等价类是否满足L-diversity匿名化原则,使算法最终满足(K,L)-匿名化。

4.1 敏感属性聚类

对敏感属性值进行聚类。令M为敏感属性值的个数,L为L-diversity(多样性)中的参数,则聚类个数为G=M/L。在此过程中要求簇内元素具有极大的同质性,每对簇间元素具有极大的异质性。依据此特点,可以提出改进的K-means算法来完成,因为相比传统的K-means算法,改进的K-means算法更高效省时[10]。

传统的K-means算法步骤为:对于给定的聚类簇数,首先对集群初始化,随机选择初始聚类中心,通过分配每个数据到最近的质心,生成新的分区集群。重复以上计算,直到质心不再变化。传统 K-means算法虽然能快速处理数据,且快速简单,但它存在着局限性:K值需要事先指定,对噪声和孤立点敏感等,其中最突出的是对初始聚类中心的随机选择,易使聚类结果不稳定,造成结果陷入局部最优解,甚至得到相差甚远的聚类结果。

K-means聚类算法的目的是使簇内最大程度的相似,每对簇间数据最大程度地不同。聚类结果的好坏与初始聚类中心的选择关系重大。为使聚类效果更好,应选择尽可能离得远的对象作为初始聚类中心,以避免在应用K-means聚类算法时由于初始聚类中心选择的过于邻近,造成选取的初始聚类中心在同一个簇中,或小簇被包涵在大簇中等聚类结果不好的情况。

改进的K-means聚类算法具体步骤是:首先计算n个数据对象间的两两距离,找到距离最大的2个点,并分别以它们为质心,然后计算离此2个质心最近距离的数据对象,划分到该簇中,直到达到阈值。再通过计算剩余数据对象与前2个质心间的最大距离,找第3个质心,以此类推,直到每个簇的质心不再变化。改进的K-means聚类算法不需要预先指定K值,不受随机分配初始质心的影响,通过选取距离最远的数据点为质心,不会产生传统K-means聚类算法中初始质心在同一个簇的情况,将数据集划分的更合理,能更好实现聚类效果,即簇内最大程度的相似,每对簇间数据最大程度地不同。

上述步骤对于下一步进行的匿名化会有较大影响,因此,本文提出改进的K-means算法对敏感属性聚类,算法描述如下:

输入背景知识参考矩阵,敏感属性值M,L

输出敏感属性聚类结果

(1)先从数据集中选择2组数据,形成2个簇。根据式(2)计算数据中每一对之间的距离,选择出最远的2组数据(如d1和d2),这2个数据将被视为初始集群中心。计算确定离d1最近的数据点并且将该数据点添加到d1集群,且从数据集中删除该数据,直到该集群内数量达到阈值。d2同理,由此,形成2个簇;

(2)更新2个新形成簇的质心;

(3)第3个簇的选择是,同样由式(2)计算数据集中与前2个簇距离最远的数据,以此数据为中心,生成第3个簇;

(4)直到形成G个簇;

(5)计算集群算术平均值获得集群的质心;

(6)Until质心不再变化。

4.2 (K,L)-匿名聚类算法

为实现K-匿名,就需要对数据进行变换,由此就不可避免地会产生信息损失。对数值型属性和分类型属性,分别按不同的方式进行信息损失计算。设表T中的准标识符为QI(N1,N2,…,Nn,M1,M2,…,Mm),其中,Ni(1≤i≤n)为第i个数值型属性,Mj(1≤j≤m)为第j个分类属性。K-匿名化时,其中一个元组t=(xN1,xN2,…,xNn,xC1,xC2,…,xCm)被变换成t′=([yN1,zN1],[yN2,zN2],…,[yNn,zNn],DC1,DC2,…,DCm),则其信息损失定义如下[11],令R=(r1,r2,…,rk)为一个聚类。

定义7(元组信息损失) 元组信息损失定义为:

(K,L)-匿名算法描述如下:

输入包含N条记录的表T,参数K,L。

输出(K,L)-匿名化的表T′。

(1)将数据集中每条记录初始为等价类;

(2)从步骤(1)中G个簇中,每个簇选一条记录,作为G个等价类的质心;

(3)Repeat;

(4)根据式(3)计算算法1聚类结果中同一簇所有记录转变到对应等价类中的信息损失;

(5)将信息损失最小的记录分配到对应的等价类;

(6)每个等价类内记录个数到K,则停止向该等价类内分配,直到只有最后一个等价类内记录数不是K;

(7)更新G个等价类的质心;

(8)在以上生成的等价类中,查找敏感属性个数小于L的等价类;

(9)计算第G个记录中所有记录转换到该等价类的最小信息损失;

(10)直到前边G-i个等价类满足L多样性;

(11)最后一个等价类中记录数若不足K,按最小信息损失分配到对应等价类中;

(12)再次更新等价类的质心;

(13)Until质心不再变化。

5 实验结果与分析

5.1 实验环境

本文实验的验证采取UCI机器学习数据库中的Adult数据集。该数据集应用广泛,在隐私保护研究中有权威性,其内容包括了部分美国人口普查数据,数据量很大。采用文献[12]中的数据预处理方法,将含有缺失值的不完整数据及有身份特征标识的姓名、身份证号码等信息删除,得到的实验数据集包含45 222条数据记录。将属性{age,work class, education,martial status,race,gender,native country}作为准标识符属性,其中,age和education为数值型属性,occupation为敏感属性,其余5个属性为分类型属性。

5.2 数据质量

将本文算法与传统K-匿名算法在信息损失方面进行比较,结果如图1所示,可以看出,在K值递增的情况下,本文算法信息损失较小,而且随着K值的增大,该优势更明显,数据质量更高。

图1 信息损失度量

5.3 运行时间

将本文算法与传统K-匿名算法在运行时间方面进行比较,结果如图2所示,可以看出,在K值递增的情况下,本文算法在运行时间上具有优势。对任意K值,本文算法的运行时间都比传统K-匿名算法短,且优势明显,体现了本文算法的高效性。

图2 运行时间

6 结束语

本文利用改进K-Means算法将待发布数据聚合成K个簇,簇内最大程度相似,每对簇间数据最大程度不同,使准标识符对敏感属性相似的数据聚合在一起。根据聚合结果对整个数据集进行聚类,且使每个等价类满足L-多样性,以此实现(K,L)-匿名。实验从数据质量和运行时间2个方面进行比较,可以看出,当K值增大时,本文算法能获得高质量的结果,实现数据发布中敏感属性的保护。下一步将研究在面对海量数据时如何实现数据的高效保护。

[1] LeFevre K,DeWitt D J,Ramakrishnan R.Mondrian Multi Dimensional K-anonymity[EB/OL].[2014-02-10].http//www.cs.wisc.edu/-lefevre/Research.htm.

[2] Sweeney L.K-anonymity:A Modelfor Protecting Privacy[J].International Journal of Uncertainty, Fuzziness and Knowledge-based Systems,2002,10(5): 557-570.

[3] Sweeney L.Achieving k-anonymity Privacy Protection Using Generalization and Suppression[J].International Journal of Uncertainty,Fuzziness,and Knowledge-based Systems,2002,10(5):571-588.

[4] 吴溥峰,张玉清.数据库安全综述[J].计算机工程, 2006,32(12):85-88.

[5] Machanavajjhala A,Gehrke J,KiferD.l-diversity: Privacy Beyond K-anonymity[EB/OL].[2014-02-10]. http://www.cs.cornel.ledu/_mvnak.

[6] 邱保志,许 敏.无参数聚类边界检测算法的研究[J].计算机工程,2011,37(15):23-26.

[7] 万 涛,刘国华.K-匿名数据中的数据依赖问题研究[J].计算机工程,2012,38(20):38-40.

[8] 罗红薇,刘国华.保护隐私的(L,K)-匿名[J].计算机应用研究,2008,25(2):526-528.

[9] 韩建民,于 娟虞慧群,等.面向数值型敏感属性的分级l-多样性模型[J].计算机研究与发展,2011, 48(1):147-158.

[10] 徐义峰,陈春明 徐云青.一种改进的K-均值聚类算法[J].计算机应用与软件,2008,25(3):275-277.

[11] 傅鹤岗,曾 凯.多维敏感k-匿名隐私保护模型[J].计算机工程,2012,38(3):145-147.

[12] Lefevre K,Dewittd J,Ramakrishnan R.Incognito: Efficient Full-domain k-anonymity[C]//Proceedings of 2005ACM SIGMOD InternationalConferenceon Management of Data.New York,USA:ACM Press, 2005:49-60.

编辑 金胡考

Efficient(K,L)-anonymous Privacy Protection Based on Clustering

CHAI Ruimin,FENG Huihui
(School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125105,China)

In order to prevent sensitive information leakage in the release data,this paper puts forward a kind of anonymous protection algorithm based on clustering.It takes the overlooked influnces of identifier to sensitive attributes into account,clusters the sensitive attribute of data,and makes the modified k-means clustering algorithm apply to this step,to make the data more similar in class.It uses(K,L)-anonymous method for tables which being published, considering of sensitive attribute in the equivalence class,and puts forward the effective methods for privacy protection. Experimental results show that the proposed model has good effect of privacy protection,compared with the traditional K-anonymous methods,it can achieve privacy protection,at the same time,reduce the loss of data information,make the data have a higher accuracy,and the executive time is shorter.

(K,L)-anonymous;sensitive attribute;privacy protection;information loss;clustering;K-means algorithm

1000-3428(2015)01-0139-04

A

TP309

10.3969/j.issn.1000-3428.2015.01.026

柴瑞敏(1969-),女,副教授、硕士,主研方向:信息安全,数据库技术,数据挖掘;冯慧慧,硕士研究生。

2014-03-10

2014-05-09 E-mail:656248970@qq.com

中文引用格式:柴瑞敏,冯慧慧.基于聚类的高效(K,L)-匿名隐私保护[J].计算机工程,2015,41(1):139-142.

英文引用格式:Chai Ruimin,Feng Huihui.Efficient(K,L)-anonymous Privacy Protection Based on Clustering[J]. Computer Engineering,2015,41(1):139-142.