基于聚类匿名化的差分隐私保护数据发布方法-刘晓迁.pdf
《基于聚类匿名化的差分隐私保护数据发布方法-刘晓迁.pdf》由会员分享,可在线阅读,更多相关《基于聚类匿名化的差分隐私保护数据发布方法-刘晓迁.pdf(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第37卷第5期2016年5月通信学报Joumal on Co咖unications、b137 No5Mav2016doi:lO11959aissn1000-436x2016100基于聚类匿名化的差分隐私保护数据发布方法刘晓迁,李千目(南京理工大学计算机科学与工程学院,江苏南京2l0094)摘要:基于匿名化技术的理论基础,采用DBscAN聚类算法对数据记录进行聚类,实现将个体记录匿名化隐藏于一组记录中。为提高隐私保护程度,对匿名化划分的数据添加拉普拉斯噪声,扰动个体数据真实值,以实现差分隐私保护模型的要求。通过聚类,分化查询函数敏感性,提高数据可用性。对算法隐私性进行证明,并实验说明发布数据的可
2、用性。关键词:差分隐私;隐私保护;聚类:数据发布;匿名化中图分类号:TP392 文献标识码:ADifferentiaUy private data release based on clustering anonym娩ationLIU Xiao-qiaIl,LI Qi锄舢(School ofcomputer Science锄d Engieri唱Nanj地umve体时ofScience锄d Technolo鼢Na坷啦210094,Cllina)Abstract:B够ed On t11e the0Iy of锄onymi动tio玛廿le DBSCAN metllod w鹪applied to diV
3、lde all tlle da【诅records lmodi腩rem gmups to cover individIlalsT0 provide priVacy enh锄cem蚰t,me L印lace noise was added to1e锄onymizedpartitioned地to pertufb也e real value of data recordtllat me requ试mle“lS of di妊erential pracy model were satisfied砌th the cl砸tedng opemtion,地seflsi6vi够of吐屺query fIlIlc廿on h
4、船been partitioned to iIIlproVe data utili够Thep啪fofpriVacy h弱been given锄d experimerl协l resultS have been pmVided to evaluate ttle utilit),ofnle rele硒ed咖Key words:di仃brential privacyprivacy preserv撕on,cluStering,出妇release,柚onymization1 引言互联网、传感技术和大数据的迅猛发展促使数据以指数增量急速暴涨,这些数据为政府部门和研究机构提供了重要的分析资源,促进了相关服务优
5、化和产品升级。数据挖掘与分析技术在发现知识的同时,也带来了个体隐私泄露的问题,容易招致法律争端和道德争议。知识发现是数据挖掘和分析技术的首要任务,然而,在隐私保护问题日趋得到重视的情形下,如何保护数据隐私,构建隐私保护数据发布模型成为研究热点。隐私保护数据发布的任务是通过对数据记录进行扰动,确保隐私信息不被泄露,同时保证发布数据的可用性。换言之,隐私保护数据发布致力于数据发布给使用者和查询者之前的数据清洁工作,通过隐私保护手段对原始数据进行扰动,同时又注重加强数据查询和分析的准确性,力求构建算法以实现数据隐私性和可用性的平衡。在数据分析领域,隐私保护技术大致可以分为数值扰动技术、查询限制技术、
6、匿名分组技术以及数据分布技术等【l】。数值扰动技术通过添加随机噪声对数据原始值进行扰动,从而掩藏真实数值。查询限制技术从2个角度对数据查询者进行限制:1)对查询数收稿日期:20150722;修回日期:20151016基金项目:中央高校基本科研业务专项基金资助项目(No3091605104);国家自然科学基金资助项目(N061272419);江苏省未来网络前瞻性研究基金资助项目(NoBY2013095302);江苏省产学研前瞻性基金资助项目(BY2014089,NoBY2013039,BY2013037);江苏省普通高校研究生创新计划基金资助项目(NoK15 0384)Foundation It
7、ems:Tlle FuIldational Research Fullds for ttle Cen刚UIliversities mo3091605104),The National N狐嘲l ScienceFoundation ofChina fNo61272419),The Future Network Pmspective Stlldy Proiect ofJi锄gsu Province(NoBY2013095-3-02),The Indus仃yUniversi够Research Perspective Project ofJi锄gsu Province(NoBY2014089,NoBY
8、2013039,NoBY2013037),Graduate Stlldents Research IIlIlovation Pl蛐ofJiallgsu Pmvince州oKYLXl5 0384)20161001万方数据通信学报 第37卷量的严格限制;2)对可能实现组合推断的连续性查询进行控制。匿名分组技术以banonym时机制【2J为代表,肛a110nyIlli够机制实际上是一种分组策略,将准标识符相同的数据相组合以实现总体数据记录分组,每组中至少有七条数据,从而将一条数据记录隐藏在七条数据当中。数据分布技术是指通过对数据进行垂直或水平划分,从物理存储角度对数据进行分布化,从而达到数据隐藏的目
9、的。以上的这些隐私保护技术,往往不对攻击者所能获得的数据背景知识做定义,因此在处理复杂多变的攻击模型中,随着攻击者掌握背景知识的增加,往往会生成很多攻击变体,如联合性攻击、一致性攻击等。该类隐私保护算法在通用性上的限制,使数据管理者不得不针对个性化的攻击模式设计出新的隐私保护算法。如肛aIlonym时机制及其扩展模型往往难以应对组合式攻击、一致性攻击等模型。攻击者通过将用户的出生日期、性别、邮编等准标识符数据进行组合,常常能推断并锁定特定个体,进而获取该个体其他重要的隐私信息。Dw“副在2011年提出了差分隐私保护模型,该模型提供了顽健性的隐私证明,该模型不对攻击者的背景知识做限定,假设攻击者
10、拥有全部的背景知识,因此克服了背景知识不断扩大引起的隐私保护模型不再适用的缺点。然而,差分隐私模型往往提供较差的数据可用性。针对以上问题,本文提出了一种适用于数值属性数据的数据发布方法,该方法在满足差分隐私保护模型要求的同时,提升了数据可用性。2相关工作及概念定义21相关工作近年来,在数据隐私保护领域取得了很多研究成果。Vassilios等4】从数据分布、数据修改、挖掘算法改造、数据隐藏等角度对数据隐私保护研究成果进行了综述,Dwork等垆J研究了多属性数据库和垂直划分数据库的隐私保护问题。FriedmaIl等【6】提出了一种兼顾算法精确性和隐私性的差分隐私保护决策树分类算法,K锄alil(a
11、等【7J通过经验风险最小化实现了差分隐私保护的逻辑斯蒂回归分类方法和支持向量机分类方法。作为数据挖掘领域的重要方法和实现数据分组的重要手段,隐私保护聚类算法研究引起了巨大的研究热情。为了避免数据扰动技术过多影响聚类算法中的距离指标,造成聚类结果失真严重的问题,文献8提出了一种几何数据转换方法,该方法提供了隐私保护的聚类分析方法,但是并没有进行十分严格的数学证明。文献9】对后邻域替换的方法实现数据隐藏,但只对数据聚类可用性进行了分析,没有给出隐私性证明。文献10】给出了一种差分隐私保护的肛mealls聚类方法,但是该方法评价的是加噪扰动后数据聚类的准确性,旨在对数据是否正确划分到某个聚类进行评估
12、,并没有从数据发布的角度对总体信息损失做出量化表示。22聚类在隐私保护中的应用从挖掘方法角度分析,聚类算法依据数据记录的簇内相似性和簇间相异性对数据集进行聚类划分,力求使簇内数据相似|生更大,簇间数据相异性更大。隐私保护聚类算法的动机在于保护个体敏感信息的同时,不丧失聚类的准确性。如药品制造公司希望通过对用户的购买行为数据进行聚类分析,其动机是获得准确的聚类划分结果以辅助产品定位或服务优化,同时又要保障客户的个人隐私信息,即不能泄露某个特定客户曾买过治疗艾滋病的药物等。文献【1113对划分共享计算场景的聚类任务设计了隐私保护的DBSCAN聚类算法,该类算法通过加密协议构造处理垂直和水平划分形式
13、下数据集的隐私保护问题。然而,以上算法仅对特定场景的隐私保护问题加以解决,难以抵御变体模型的攻击。在数据发布领域,聚类算法可以作为一种分组算法,依据相似度和相异性指标对数据进行分组预处理,从而实现单条数据到组数据的匿名化隐藏。依据文献3】提出的查询函数敏感性加噪方法,经过分组操作后,函数查询敏感性会由单一个体分化到一组个体,从而实现扰动噪声量到组数据的分化。从组中单一个体数据的角度考虑,添加在其上的噪声量会大大减小,进而信息损失量减少,数据可用性得到提升。23差分隐私差分隐私保护【3J是一种加密机制驱动的、具有很强顽健性的隐私保护模型。该模型假定攻击者掌握了任何关于数据的背景知识,并且对隐私保
14、护的程度提供严格的数学证明。对于能够满足差分隐私保护的随机算法而言,其输出随机变量的概率分布显然是要以数据集的先验特征为前提条件的。从随机变量的概率分布角度进行分析,如果一个随机算法满足差分隐私保护模型的要求,那么其输出结果的概率分布不会因为在数据集中添加或减少一条数据记录而产生很大变化,即某个个体存在与否仅仅会对数据总体的概率分布产生很小的影响,这种影响的程度通过万方数据第5期 刘晓迁等:基于聚类匿名化的差分隐私保护数据发布方法 。127。隐私保护预算【14】进行估计。在差分隐私保护模型中,数据分析者可以获得数据总体的统计属性或模型特征,但对任意特定数据记录的信息则无法获取。因此,这种机制能
15、够对数据集中特定个体的敏感信息进行保护,又不至于引起数据分布的巨大变化。定义1差分隐私模型定义了概率分布层面的隐私量化。假设随机算法M满足差分隐私模型的要求,那么当其满足式(1)的概率约束时,随机算法M提供差分隐私。Prf(D)=Se5PrA,(D)=S】 (1)其中,表示隐私保护预算,D表示原始数据集,D为D的邻近数据集,指在D中添加或删除任意一条数据记录,S表示任意输出结果集合。差分隐私保护机制要求将随机算法M作用在邻近数据集上后,所得到输出结果相同的概率比值上界为e8。通过限制的大小,使随机算法作用于邻近数据集上输出相同结果的概率尽量接近。占越小,隐私性越强,引入的噪声也越大。当为0时,
16、输出结果相同的概率也相同。文献15】提出了针对数值数据进行差分隐私保护的拉普拉斯机制,即通过对数据属性值添加拉普拉斯噪声的形式,实现差分隐私保护。将查询函数表示为为原始数据添加均值为0,尺度参数为竺的拉普拉斯噪声以实现数值型数据的差分隐私保护,加噪操作的形式化表示为,、M(D)=(D)+LapI兰L (2)在上述表示中,厂表示查询函数的敏感性,指的是查询函数厂作用于邻近数据集时产生的最大距离差。3 差分隐私保护的聚类匿名化数据发布方法本文提出的聚类匿名化数据发布方法,首先依据准标识符对数据集进行聚类划分,使数据满足缸a110nyIIli够模型的要求。在匿名化的过程中,所有数据属性都被当作准标识
17、符。然后对匿名分组后的数据添加拉普拉斯噪声,扰动数据记录真实值,从而实现差分隐私保护模型的隐私性要求。相对于常规拉普拉斯机制而言,聚类操作主要用于减小查询函数的敏感性,敏感性减小促使添加噪声量的减小,从而大大增强数据可用性。31 基于密度的聚类匿名化方法DBSCAN(densi够一based spatial cluste血g of印plications谢m noise)算法是一种基于密度的聚类算法,与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇。相对于其他聚类算法而言,DBSCAN的适用性更强,能够发现任意形状的聚类,因此在数据分组通用性上,具
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 匿名 隐私 保护 数据 发布 方法 刘晓迁
限制150内