差别隐私保护及其ppt课件.pptx
- 文档编号:18814541
- 上传时间:2023-12-05
- 格式:PPTX
- 页数:46
- 大小:549.19KB
差别隐私保护及其ppt课件.pptx
《差别隐私保护及其ppt课件.pptx》由会员分享,可在线阅读,更多相关《差别隐私保护及其ppt课件.pptx(46页珍藏版)》请在冰点文库上搜索。
差别隐私保护及其应用,来自两篇KDD会议文章KDD2011DifferentiallyPrivateDataReleaseforDataMiningKDD2010DataMiningwithDifferentialPrivacy,敏感信息保护问题提出与描述,第1页/,敏感信息,私有性敏感性易暴露例如:
姓名、身份号、年龄等信息,第2页/,敏感保护新问题,基于背景知识的隐私攻击实例,87%的美国人身份可以通过5位压缩码(5-digitzipcode)、性别和出生日期组成的属性集合唯一地被辨识。
这个属性集合被称为准标识(Quasi-IDentier,QID)。
敌手可能通过一些公开的来源获得这些属性集合信息,比如公众投票表(avoterlist)。
通过简单地连接外部数据源中的QID属性集合,一个人的私有信息可能会被暴露。
第3页/,目前的解决方法,匿名化算法k-匿名的隐私保护模型(k-anonymityprivacymodel)36,37-多样化(-diversity)28(a,k)匿名((,k)-anonymity)41t-密闭(t-closeness)26(c,k)-安全((c,k)-safety)29,交互式与非交互式隐私保护,第4页/,数据发布中的技术,泛化技术36,37基于泛化技术的匿名算法2,13,23,24,36已经被提出来,第5页/,新颖的隐私保护模型,差别隐私(DifferentialPrivacy)7差别隐私是一个新颖的隐私定义,可以提供强的隐私保护。
基于划分的隐私保护模型的输出数据需要保持k个记录是难以分辨的,或者敏感信息值都在每一个等价组中被很好地描述。
然而,差别隐私的保护可以保证敌手对于个体的知识一无所知,无论个人的记录在不在数据当中出现。
简言之,从一个个体的角度来看,输出的处理就像是对一个不包含个体个人记录的数据集进行计算一样。
第6页/,差别隐私保护,定义3.1-差别隐私(-differentialprivacy).一个随机算法是差别隐私的当对于所有的数据集和来说,他们的对称的差别(symmetricdifference)最多包含一个记录,对于所有的可能的匿名化数据集来说有,其中,概率值是在算法的随机性前提下的。
参数0是公开的而且是由数据拥有者指定的。
取值越小提供的隐私保护越强。
第7页/,差别隐私保护,差别隐私保护的标准机制是通过向一个函数的真实输出中添加随机的噪音的方法完成的。
噪音通过函数的敏感度来调整。
函数的敏感度是从两个只有一个记录不同的数据集中得到的输出的最大差别。
第8页/,差别隐私保护-拉普拉斯机制,Dwork等人在文献9中提出了拉普拉斯机制作用是确定添加噪音数据的大小,第9页/,差别隐私保护-指数机制,McSherryandTalwar在文献32中提出了指数机制作用是对效用函数计算的候选评分进行选择越高的计分的输出与被选择输出指数倍地趋近上述所说的定义与机制都已被证明,满足-差别隐私,第10页/,问题提出与描述,假设一个数据拥有者打算发布一个数据集给公众用于数据分析,-所属这个类别属性的值,-包含了d个属性的集合,类别属性是用来分类的,预测器属性要么是数值型的要么是类别型属性。
第11页/,问题提出与描述,对于一个数据集和隐私参数,文中算法的目标是生成一个匿名数据集,使得
(1)满足-differentialprivacy,同时
(2)尽可能多的保留用于分类分析的信息。
第12页/,算法描述,基于泛化技术的差别隐私匿名化算法(Differentially-privateanonymizationalgorithmbasedonGeneralization,DiffGen),第13页/,算法描述,第14页/,Line1起初,在中的所有值都泛化成类别树中最高层的值Line2中包含了每一个属性的值Line7每一次DiffGen算法的迭代过程都要基于概率地选择一个在中的候选来进行下一次的细化过程Line8算法细化选择的候选v,更新Line10更新受影响的候选的评分以为下次细化过程所用Line12把在拉布拉斯分布中选取噪音数据添加到按上述细化过程分类的组当中的统计计数中,第15页/,实例,细化过程,划分,顶层,第16页/,关键步骤详析,候选选取划分值选择噪音数据添加,第17页/,候选选取,选取候选哪个进行细化通过两个方法计算候选评分值信息增益最大匹配,第18页/,候选选取-信息增益,有趣的物理学名词信息论应用-熵(entropy)信息熵是指对信息具体的量化度量问题。
信息论之父C.E.Shannon第一次用数学语言阐明了概率与信息冗余度的关系。
第19页/,自信息,离散信源X的概率空间为:
I(ai)有两种含义:
(1)当ai发生前,表示ai发生的不确定性
(2)当ai发生后,表示ai所提供的信息量,称事件ai发生含有的信息量为ai的自信息量,第20页/,例8个串联的灯泡x1,x2,x8,损坏的可能性是等概的,现假设其中有一个灯泡已损坏,问每进行一次测量可获得多少信息量?
总共需要多少次测量才能获知和确定哪个灯泡已损坏。
第21页/,8个灯泡等概率损坏,先验概率P(x1)=1/8,即,第二次测量获得的信息量=IP(x2)-IP(x3)=1(bit)第三次测量获得的信息量=IP(x3)=1(bit)至少获得3bit信息量就可知道哪个灯泡已坏了。
第一次测量获得的信息量=IP(x1)-IP(x2)=1(bit)经过二次测量,剩2个灯泡,等概率损坏,P(x3)=1/2,一次测量后,剩4个灯泡,等概损坏,P(x2)=1/4,第22页/,信息熵,一个信源发出不同的消息所含有的信息量也不同,故自信息I(ai)是随机变量,不能用它来作为整个信源的信息测度定义自信息的数学期望为平均自信息量Hr(X),称为信息熵:
第23页/,熵(entropy),经典热力学中熵的概念,最先由克劳修斯提出。
它的定义即“热温商”,作为热力学过程不可逆程度的一种量度。
熵是分子随机热运动状态的几率大小的量度,也就是分子热运动的混乱程度或无序度。
若所讨论的对象不限于分子热运动,也可借用熵的概念描述并非分子热运动的其它任何物质运动方式、任何事物、任何系统的混乱度或无序度。
就有另一种熵的概念,它是热力学和统计力学中熵概念的推广,称广义熵。
第24页/,熵的计算例:
有一布袋内放l00个球,其中80个球是红色的,20个球是白色的。
随便摸出一个球,猜测是什么颜色,那么其概率空间为:
如被告知摸出的是红球,则获得的信息量是:
I(a1)logp(a1)log0.8=0.32(比特)如被告知摸出的是白球,所获得的信息量为:
I(a2)logp(a2)log0.2=2.32(比特)平均摸取一次所能获得的信息量为:
H(X)=p(a1)I(a1)+p(a2)I(a2)=0.72(比特/符号),第25页/,熵的含义,熵是从集合的统计特性来考虑的,从平均意义上来表征信源的总体特征。
在信源输出后,信息熵H(X)表示每个消息提供的平均信息量;在信源输出前,信息熵H(X)表示信源的平均不确定性;信息熵H(X)表征了变量X的随机性。
第26页/,例如,有两信源X、Y,其概率空间分别计算其熵,得:
H(X)=0.08(bit/符号)H(Y)=1(bit/符号)H(Y)H(X),因此信源Y比信源X的平均不确定性要大。
第27页/,例设甲地的天气预报为:
晴(占48)、阴(占28)、大雨(占18)、小雨(占18)。
又设乙地的天气预报为:
晴(占78),小雨(占18)。
1)试求两地天气预报各自提供的平均信息量。
2)若甲地天气预报为两极端情况,一种是晴出现概率为1而其余为0。
另一种是晴、阴、小雨、大雨出现的概率都相等为14。
3)试求这两极端情况所提供的平均信息量。
4)又试求乙地出现这两极端情况所提供的平均信息量。
第28页/,两个信源,第29页/,解:
甲地天气预报构成的信源空间为:
则其提供的平均信息量即信源的信息熵:
第30页/,乙地天气预报的信源空间为:
结论:
甲地天气预报提供的平均信息量大于乙地,因为乙地比甲地的平均不确定性小。
第31页/,甲地极端情况,极端情况1:
晴天概率1,结论:
等概率分布时信源的不确定性最大,所以信息熵(平均信息量)最大。
极端情况2:
各种天气等概率分布,第32页/,乙地极端情况,极端情况1:
晴天概率1,结论:
在极端情况2下,甲地比乙地提供更多的信息量。
因为,甲地可能出现的消息数比乙地可能出现的消息数多。
极端情况2:
各种天气等概率分布,第33页/,候选选取-信息增益,信息增益(informationgain)是指期望信息或者信息熵的有效减少量(通常用“字节”衡量),根据它能够确定在什么样的层次上选择什么样的变量来分类。
(InformationGain)来衡量一个属性区分以上数据样本的能力。
信息增益量越大,这个属性作为一棵树的根节点就能使这棵树更简洁,比如说一棵树可以这么读成,如果风力弱,就去玩;风力强,再按天气、温度等分情况讨论,此时用风力作为这棵树的根节点就很有价值。
如果说,风力弱,再又天气晴朗,就去玩;如果风力强,再又怎么怎么分情况讨论,这棵树相比就不够简洁了。
第34页/,候选选取-信息增益,第35页/,候选选取-最大匹配,第36页/,划分值,数值型属性值从哪里划分?
把属性值分为按照上面两种效用函数,计算每个分隔的评分,最高的划之分类型属性值按照分类树选择划分位置,第37页/,噪音数据添加,第38页/,算法复杂度分析,算法DiffGen的算法复杂度为,第39页/,实验结果分析,数据质量(隐私保护质量和分类精度)算法比较(DiGen,DiP-C4.5,和TDS),第40页/,实验环境,文中实验采用了开源的数据集Adult10,这个数据集是一个真实生活的人口普查数据集,常用作验证匿名化算法2,13,18,28,38,33。
Adult中包含了45,222个普查记录,6个数值型属性,8个分类型属性。
文献13中有对属性的详细描述。
实验的硬件平台是IntelCorei72.7GHzPCwith12GBRAM。
第41页/,实验结果,第42页/,7C.Dwork.Dierentialprivacy.InICALP,2006.36P.Samarati.Protectingrespondentsidentitiesinmicrodatarelease.IEEETKDE,2001.37L.Sweeney.k-anonymity:
Amodelforprotectingprivacy.InInternationalJournalonUncertainty,FuzzinessandKnowledge-basedSystems,2002.28A.Machanavajjhala,D.Kifer,J.Gehrke,andM.Venkitasubramaniam.-dierentialprivacybeyondk-anonymity.ACMTKDD,2007.41R.C.W.Wong,J.Li.,A.W.C.Fu,andK.Wang.(,k)-anonymity:
Anenhancedk-anonymitymodelforprivacypreservingdatapublishing.InSIGKDD,2006.26N.Li,T.Li,andS.Venkatasubramanian.t-closeness:
Privacybeyondk-anonymityand-diversity.InICDE,2007.29D.Martin,D.Kifer,A.Machanavajjhala,J.Gehrke,andJ.Halpern.Worst-casebackgroundknowledgeinprivacy-preservingdatapublishing.InICDE,2007.2R.J.BayardoandR.Agrawal.Dataprivacythroughoptimalk-anonymization.InICDE,2005.13B.C.M.Fung,K.Wang,andP.S.Yu.Anonymizingclassicationdataforprivacypreservation.IEEETKDE,19(5):
711725,May2007.23K.LeFevre,D.J.DeWitt,andR.Ramakrishnan.Mondrianmultidimensionalk-anonymity.InICDE,2006.24K.LeFevre,D.J.DeWitt,andR.Ramakrishnan.Workload-awareanonymizationtechniquesforlarge-scaledatasets.ACMTODS,33(3),2008.39R.C.W.Wong,A.W.C.Fu,K.Wang,andJ.Pei.Minimalityattackinprivacypreservingdatapublishing.InVLDB,2007.45L.Zhang,S.Jajodia,andA.Brodsky.Informationdisclosureunderrealisticassumptions:
Privacyversusoptimality.InCCS,2007.5G.Cormode,D.Srivastava,N.Li,andT.Li.Minimizingminimalityandmaximizingutility:
Analyzingmethodbasedattacksonanonymizeddata.InVLDB,2010.19X.Jin,N.Zhang,andG.Das.Algorithm-safeprivacy-preservingdatapublishing.InEDBT,2010.43X.Xiao,Y.Tao,andN.Koudas.Transparentanonymization:
Thwartingadversarieswhoknowthealgorithm.ACMTODS,35
(2),2010.14S.R.Ganta,S.Kasiviswanathan,andA.Smith.Compositionattacksandauxiliaryinformationindataprivacy.InSIGKDD,2008.21D.Kifer.Attacksonprivacyanddenettistheorem.InSIGMOD,2009.40R.C.W.Wong,A.W.C.Fu,K.Wang,Y.Xu,andP.S.Yu.Cantheutilityofanonymizeddatabeusedforprivacybreaches?
ACMTKDD,toappear.6I.DinurandK.Nissim.Revealinginformationwhilepreservingprivacy.InPODS,2003.9C.Dwork,F.McSherry,K.Nissim,andA.Smith.Calibratingnoisetosensitivityinprivatedataanalysis.InTCC,2006.35A.RothandT.Roughgarden.Interactiveprivacyviathemedianmechanism.InSTOC,2010.11A.FriedmanandA.Schuster.Dataminingwithdierentialprivacy.InSIGKDD,2010.1B.Barak,K.Chaudhuri,C.Dwork,S.Kale,F.McSherry,andK.Talwar.Privacy,accuracy,andconsistencytoo:
Aholisticsolutiontocontingencytablerelease.InPODS,2007.44X.Xiao,G.Wang,andJ.Gehrke.Dierentialprivacyviawavelettransforms.InICDE,2010.16M.Hay,V.Rastogi,G.Miklau,andD.Suciu.Boostingtheaccuracyofdierentiallyprivatehistogramsthroughconsistency.InVLDB,2010.27A.Machanavajjhala,J.Gehrke,andM.Gotz.Datapublishingagainstrealisticadversaries.InVLDB,2009.42X.XiaoandY.Tao.Personalizedprivacypreservation.InSIGMOD,2006.12B.C.M.Fung,K.Wang,R.Chen,andP.S.Yu.Privacy-preservingdatapublishing:
Asurveyofrecentdevelopments.ACMComputingSurveys,42(4):
153,June2010.38K.Wang,B.C.M.Fung,andP.S.Yu.Handicappingattackerscondence:
Analternativetok-anonymization.KAIS,11(3):
345368,April2007.3R.Bhaskar,S.Laxman,A.Smith,andA.Thakurta.Discoveringfrequentpatternsinsensitivedata.InSIGKDD,2010.4A.Blum,K.Ligett,andA.Roth.Alearningtheoryapproachtonon-interactivedatabaseprivacy.InSTOC,2008.20S.P.Kasiviswanathan,M.Rudelson,A.Smith,andJ.Ullman.Thepriceofprivatelyreleasingcontingencytablesandthespectraofrandommatriceswithcorrelatedrows.InSTOC,2010.8C.Dwork.Armfoundationforprivatedataanalysis.Commun.ACM,54
(1):
8695,2011.15M.HardtandK.Talwar.Onthegeometryofdierentialprivacy.InSTOC,2010.32F.McSherryandK.Talwar.Mechanismdesignviadierentialprivacy.InFOCS,2007.,第43页/,感谢您的欣赏!
第44页/,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 差别 隐私 保护 及其 ppt 课件