《基于聚类匿名化的差分隐私保护数据发布方法-刘晓迁.pdf》由会员分享，可在线阅读，更多相关《基于聚类匿名化的差分隐私保护数据发布方法-刘晓迁.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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的适用性更强，能够发现任意形状的聚类，因此在数据分组通用性上，具
18、有很大优势。本文提出了一种密度聚类机制(DCM，dens时based cluste血g mechallism)，利用DBSCAN算法对数据集进行聚类操作，按照密度分布将数据划分到不同的等价组，每组数据记录的数量至少为七。在实现数据匿名化的同时，将查询函数的敏感性分化到每组数据的七条记录上，以降低查询函数的敏感性。在聚类划分中，假定所有的属性都是准标识符，那么通过聚类划分得到的数据集就满足肛aIlorl)幔ny机制的要求。算法l DcM(D，r，七)输入：D为原始数据集，为非敏感聚类邻域半径，七为最小聚类尺寸输出：D为经聚类算法划分之后的数据集1)使用伽(D，七)对数据集D进行聚类，得到聚类结果
19、数据集口；2)将口中无法划分到聚类中的噪音异常点使用总体均值进行替换；3)对于划分出的每个簇，使用簇质心替换簇内各条数据；4)返回经替换之后的数据集历。定理1定义原始数据集为D，定义查询函数f，返回数据集中的第f条记录。那么对于聚类机r，、制与查询函数而言，(，：D叫)竺掣成立。七证明 将聚类机制D伽作用于数值型数据集得到D，最小簇尺寸为七。显然，当查询函数f作用于数据集时，由于临近数据集之间的差异被分化到七条数据记录上。那么，当，：D叫操作作用于数据集时，将返回第f条数据记录所在簇的质心(对于数值型数据而言，质心用均值来表示)，其敏感，、性至多为竺掣。对于数据集中未被划分到某个簇的尼噪音异常
20、点来说，通过整体均值进行替换就意味着平均分化的范围为整个数据集，因此查询函数敏感性会远小于已经划分到聚类中的点。综上，聚类函，、数作用后，在可用性上实现了(，：D叫)掣。尼因此，通过聚类操作对数据集进行分组，实现20161003万方数据通信学报 第37卷了将单条记录匿名隐藏于一组数据当中的目的。同时通过均值替换，实现了查询函数的敏感性分化，从而减小了查询函数的敏感性。32差分隐私保护数据发布方法为增强数据隐私性，需要对数据原始信息添加噪声扰动，以达到差分隐私保护模型的要求。本文提出了一种噪声扰动的隐私保护数据发布机制(DCMD只deIls时-b雒ed clllsteIjng mech锄ism、
21、)l，itll di岱矗舶：cial砸vacy)，对经密度聚类划分得到的数据添加拉普拉斯噪声，使其满足差分隐私模型的需求。算法2 Dd坦)尸(D，)输入：历为聚类划分之后的数据集，为隐私保护预算输出：D。为添加噪声后满足g差分隐私模型的数据集1)查询函数f作用于数据集西，返回历中第f条数据记录f(D)，其中，f_1，2，IDI；21对查询到的每一条数据记录添加拉普拉斯噪声札(Z(历)，并将加噪后的数据记录加入D；3)返回满足一差分隐私的数据集D。定理2经噪声扰动后，数据集满足差分隐私。证明 加噪操作的原理是对查询出的每一个数据记录添加拉普拉斯噪声。依据隐私保护模型的并行性规则【l 6|，对于不
22、相交数据记录施以隐私保护预算为的随机算法，那么整个数据集满足s差分隐私。在本文的算法中，针对的是互不相交的簇，因此满足差分隐私保护的并行性规则。综上所述，本文提出的基于聚类匿名化的差分隐私保护数据发布方法满足差分隐私模型的要求。4实验评估41实验环境及数据集描述本算法使用基于Pytllon语言的scil(it1e锄框架进行实现，实验环境为Wmdows 81，内存4 GB。实验中的数据来源于uCI Knowle电e Discove巧舡chive Database(h郇：archiveicsuciedllml)。在本文的研究中，对数值型数据进行差分隐私保护的数据发布，实验数据集为MAGIC GaI
23、I皿aTelescope Data Set，数据集描述如表1所示。表l 数据集属性信息描述42数据可用性度量421后值选择聚类函数作用后，在可用性上实现了(zDcM)垒掣。在实验过程中，从整体数据可用性角度衡量，聚类最小尺寸七的选择，需要满足(掣)(等锁，因此，理论上，当七值的选择在大于等于IDI时，数据的可用性会高于单独应用拉普拉斯机制。422实验结果度量对于可用性的度量，本文通过计算信息损失来实现，即计算聚类匿名化及加噪操作后的扰动数据与原始数据之间的平方误差和。这种度量的公式为跚=(如f(口；，(巧)2 (3)diED diEdi本文讨论数值型数据的隐私保护问题，因此使用欧几里得距离作为
24、距离的衡量尺度。鼹E衡量的是信息损失量，因此船越大，扰动操作后的数据可用性越差。设置差分隐私保护预算为最常用的数值，即=001、01、1和10，加噪操作后通过式(4)对信息损失量进行相对评分。SC(坎E=竺兰旦迪生 H)SSE肿其中，赈脚表示本文算法下的信息损失量，孓呱，表示直接使用拉普拉斯机制下的信息损失量。评分的过程是对信息损失量数据进行归一化的过程，脚相对于越小，表示发布数据可用性的提升越可观。423实验结果讨论以=001时直接添加拉普拉斯噪声引发的信息损失量为基准，不断调整聚类尺寸七的大小，以进行数据可用性对比实验，实验中可用性相对评分结果如图1所示。在图1中，水平线表示不断变化隐私保
25、护预算时，直接添加拉普拉斯噪声时的数据可用性相对评分，=001时直接添加拉普拉斯噪声生成基准可用性相对评分为1。因为其评分并不会随|i值变化，因此表现为水平。应用本文提出的DCMDP机制作用数据集，随着七值增大，可用性在逐渐的提高。总体而言，在|i=1012 z32附万方数据第5期 刘晓迁等：基于聚类匿名化的差分隐私保护数据发布方法 129近，使用DCMDP机制发布的数据可用性超过原始拉普拉斯机制。图1不同隐私保护预算下变换I值时拉普拉斯机制与DCMDP方法可用性评分对比5结束语本文提出了一种基于密度聚类的数据匿名化机制，以提高数据可用性。同时，结合拉普拉斯机制对隐私保护程度进行提升，使该方法
26、满足差分隐私保护模型的要求。对于隐私保护水平，本文给出了较为详细的数学证明过程。实验结果显示，所提算法作用后的数据可用性得到了很大提升。但是聚类过程本身也会造成信息量损失，因此，当七值较小时，聚类造成的数据损失得不到补偿，也会使数据的可用性低于直接添加拉普拉斯噪声。所以，实验中，七值的选择十分关键。本文给出了一种高可用性的差分隐私保护数据发布方法，然而考虑的场景仅仅是数值型数据，并没有对类别型数据和混合型数据的隐私保护数据发布进行研究。类别型数据和混合型数据的差分隐私保护需要考虑随机概率选举及加噪操作混合的问题，处理上较为复杂，本文中未有涉及。因此，后续的工作将是设计更为通用的聚类匿名化差分隐
27、私保护数据发布方法，以满足不同类型数据的差分隐私保护需求。参考文献：2】ADAM N R，WoRIHMANN J CSecuritycontr0I melho(1s for statis-tical databas：a comp撒廿Ve studyJ】AcM computing surveys(CSUR)，1989，21(4)：515556LAL气NYS扣粕onymity：a model for pmtcctiIlg privy【J】IrIter-枷onal Jo啪al 0n Uncercaillty Fuzziness Knowledgeb乏ISed Systems，2002，lO(5)：5
28、57-5703】 DwORK CDi彘rernial priVy【M】Encyclopedia of cryl)to鲫hy锄d Scc州够Sp血ger US，2011：33834041 VERYKIOS V S，BERlrINO E，FOVINO I N，et a1Sta主eof-tl碡一art iIlprivacy pD哪rvirlg da诅miniIlg叨ACM Si驴od Reco吐2004，33(1)：5057【5】 DwORK C，NIsSM KPrivacy-pfeserving dat锄ining on Verticallypartitioned出扭b船es【c】Adv锄ces
29、in cqptolo时-CRyPTo 2004Califom试USA：Sprhlger Berlm Heidelbc唱，c2004：528-544【6】FRIEDIAN A，SCHUSTER AData mining witll di丘h哪ial priVacy【C】仃1le 16tll ACM SIGKDD IIltemational Confefence on K_IlowledgcDiscovery锄d Data MiningW嬲hillgton Dc，USA：ACM，c2010：4935027】 cHAUDHIliI K MONrELEoNI C，SAl溉wrE A DDi侬犯埘all
30、yprivatc e唧试cal risk miniInization【_】The Jo吼al of Machi鹏LeamiIlg黜search，2011，12：1069-1109【8】 0L即认s R M，zAIANE O RP咖acy presenring cl璐tc血g bydata的丑sfo册鲥0n川Jo啪aI of IIlfo珊ation锄d Da主a M趾ageme咄2010，l(1)：37【9】崇志宏，倪巍伟，刘腾腾，等一种面向聚类的隐私保护数据发布方法【J计算机研究与发展，20lO，47(12)：20832089CHONGzH，N1w W，LIUT Tet a1A州vy-p嘲盯V
31、ingda诅pub1ishillg algo硎hnl for cluste咖g applic撕onmJoIlrIlal of ComputcrResearch卸d DeVelopme峨2010，47(12)：2083-2089【lO】李杨，郝志峰，温雯，等差分隐私保护七-me锄s聚类方法研究叨计算机科学，2013，40(3)：287290u Y，姒OzF，wEN wet a1Res咖曲0n衄陆e而al两Vacyp嘲erviIlg知mns clllste啦g叨Comp咖Sci咖e，2013，40(3)：287290【ll】KUMAR K ARANGAN c PPrivacy p陀serviIlg
32、 DBSCAN algo珊蚰fbr clusteringC】AdV锄ced Data Mining柚d Applicatio船H州，iIl，Chinac2007：5768【12】AM砌EKYAN A， ESllLLcAsTRO V PriV粒y p心servingDBscAN for Ve而cally panitioned data【C】仇ntelligence and Sec州tyInf0册aticsSan Diego，CA，USA：Sp血ger BerliIl Heidelbefg，c2006：141153【13】xu w：HUANG L，Lu0 Yet a1Protocols for p
33、riVacypre驼rvingDBscAN cl璐te血g叨Int J secu 2007，1(1)：4556【14】HAEBERLEN A，PIERcE B c，NAR AYAN ADi丘brcntial priVacyl】nder触【c】肌JSENIx S谢哆Symposi啪S柚F瑚cisco，CA，USA：c2011【l 5】DWORK C，MCS胍W F，NISS蹦K，et a1Calibmting noise tosensmv时in研Vate da诅锄alysis【M】111eory of cDrpto卿hySpmger Berlin Heidelbe毽2006：265284【16】
34、Mcs皿褂d F DPriVacy iIl崛目瞰cd qmries：柚exte璐ible platfoImfor privacypserv吣da诅肌alysis【C】佃le 2009 AcM sIGMoD Intemational Confence on Management of DataProVidence，RhodeIsl锄d：ACMc2009：l 930作者简介：刘晓迁(1989)，女，河北保定人，南京理工大学博士生，主要研究方向为数据挖掘、机器学习与隐私保护等。李千目(1979)，男，江苏南京人，博士，南京理工大学教授、博士生导师，主要研究方向为信息安全、传感网技术、智能决策与数据挖掘等。20161005万方数据