《差别隐私保护及其》由会员分享，可在线阅读，更多相关《差别隐私保护及其（45页珍藏版）》请在金锄头文库上搜索。
1、差别隐私保护及其应用1来自两篇KDD会议文章KDD2011 Differentially Private Data Release for Data Mining KDD2010 Data Mining with Differential Privacy2敏感信息保护问题提出与描述3敏感信息私有性敏感性易暴露例如：姓名、身份号、年龄等信息4敏感保护新问题基于背景知识的隐私攻击实例，87%的美国人身份可以通过5位压缩码（5-digit zip code）、性别和出生日期组成的属性集合唯一地被辨识。这个属性集合被称为准标识（Quasi-IDentifier ，QID）。敌手可能通过一些公开的来源获
2、得这些属性集合信息，比如公众投票表（a voter list）。通过简单地连接外部数据源中的QID属性集合，一个人的私有信息可能会被暴露。5目前的解决方法匿名化算法k-匿名的隐私保护模型（k-anonymity privacy model）36, 37 -多样化（-diversity ）28（a，k）匿名（(,k)-anonymity）41 t-密闭（t-closeness）26 （c，k）-安全（(c,k)-safety）29交互式与非交互式隐私保护6数据发布中的技术泛化技术36,37 基于泛化技术的匿名算法2,13,23,24,36已经被提出来 7新颖的隐私保护模型差别隐私（Differe
3、ntial Privacy）7 差别隐私是一个新颖的隐私定义，可以提供强的隐私保护。基于划分的隐私保护模型的输出数据需要保持k个记录是难以分辨的，或者敏感信息值都在每一个等价组中被很好地描述。然而，差别隐私的保护可以保证敌手对于个体的知识一无所知，无论个人的记录在不在数据当中出现。简言之，从一个个体的角度来看，输出的处理就像是对一个不包含个体个人记录的数据集进行计算一样。8差别隐私保护定义 3.1 -差别隐私(-differential privacy) . 一个随机算法是差别隐私的当对于所有的数据集和来说，他们的对称的差别（symmetric difference）最多包含一个记录，对于所有
4、的可能的匿名化数据集来说有其中，概率值是在算法的随机性前提下的。参数 0是公开的而且是由数据拥有者指定的。 取值越小提供的隐私保护越强。 9差别隐私保护差别隐私保护的标准机制是通过向一个函数的真实输出中添加随机的噪音的方法完成的。噪音通过函数的敏感度来调整。函数的敏感度是从两个只有一个记录不同的数据集中得到的输出的最大差别。 10差别隐私保护-拉普拉斯机制 Dwork等人在文献9中提出了拉普拉斯机制 作用是确定添加噪音数据的大小11差别隐私保护-指数机制McSherry and Talwar在文献32中提出了指数机制作用是对效用函数计算的候选评分进行选择越高的计分的输出与被选择输出指数倍地趋近
5、上述所说的定义与机制都已被证明，满足-差别隐私 12问题提出与描述假设一个数据拥有者打算发布一个数据集给公众用于数据分析-所属这个类别属性的值-包含了d个属性的集合 类别属性是用来分类的，预测器属性要么是数值型的要么是类别型属性。 13问题提出与描述对于一个数据集 和隐私参数 ，文中算法的目标是生成一个匿名数据集 ，使得（1） 满足 - differential privacy，同时（2）尽可能多的保留用于分类分析的信息。14算法描述基于泛化技术的差别隐私匿名化算法（Differentially-private anonymization algorithm based on Generali
6、zation ，DiffGen） 15算法描述16Line 1 起初， 在中的所有值都泛化成类别树中最高层的值Line 2 中包含了每一个属性的值 Line 7 每一次DiffGen算法的迭代过程都要基于概率地选择一个在 中的候选 来进行下一次的细化过程Line 8 算法细化选择的候选v，更新Line 10 更新受影响的候选的评分以为下次细化过程所用 Line 12 把在拉布拉斯分布中选取噪音数据添加到按上述细化过程分类的组当中的统计计数中 17实例细化过程划分顶层18关键步骤详析候选选取划分值选择噪音数据添加19候选选取选取候选哪个 进行细化通过两个方法计算候选评分值信息增益最大匹配20候选
7、选取-信息增益有趣的物理学名词信息论应用-熵（entropy）信息熵是指 对信息具体的量化度量问题。信息论之父 C. E. Shannon 第一次用数学语言阐明了概率与信息冗余度的关系。21自信息离散信源离散信源X的概率空间为：的概率空间为：I(ai)有两种有两种含义含义：（1）当当ai发生前，表示发生前，表示ai发生的不确定性发生的不确定性（2）当）当ai发生后，表示发生后，表示ai所提供的信息量所提供的信息量n称事件称事件ai发生含有的信息量为发生含有的信息量为 ai 的的自信息量自信息量22例例 8个串联的灯泡个串联的灯泡x1，x2，x8，损坏的可能性是，损坏的可能性是等概的，现假设其中
8、有一个灯泡已损坏，问每进行一等概的，现假设其中有一个灯泡已损坏，问每进行一次测量可获得多少信息量？总共需要多少次测量才能次测量可获得多少信息量？总共需要多少次测量才能获知和确定哪个灯泡已损坏。获知和确定哪个灯泡已损坏。 238个灯泡等概率损坏，先验概率个灯泡等概率损坏，先验概率P (x1)=1/8 ，即，即第二次测量第二次测量获得的信息量获得的信息量 = I P (x2) - I P (x3)=1(bit)第三次测量第三次测量获得的信息量获得的信息量 = I P (x3) =1(bit)v至少获得至少获得至少获得至少获得3bit3bit信息量就可知道哪个灯泡已坏了。信息量就可知道哪个灯泡已坏了
9、。信息量就可知道哪个灯泡已坏了。信息量就可知道哪个灯泡已坏了。第一次测量第一次测量获得的信息量获得的信息量=I P (x1) - I P (x2)=1(bit)经过二次测量，剩经过二次测量，剩2个灯泡，等概率损坏，个灯泡，等概率损坏，P (x3)=1/2一次测量后，剩一次测量后，剩4个灯泡，等概损坏，个灯泡，等概损坏，P (x2)=1/424信息熵一一个个信信源源发发出出不不同同的的消消息息所所含含有有的的信信息息量量也也不不同同，故故自自信信息息I(I(a ai i) )是是随随机机变变量量，不不能能用用它它来来作作为为整整个个信信源源的信息测度的信息测度定定义义自自信信息息的的数数学学期期
10、望望为为平平均均自自信信息息量量Hr(X)，称称为为信息熵信息熵：25熵（entropy）经典热力学中熵熵的概念，最先由克劳修斯提出。它的定义即“热温商”，作为热力学过程不可逆程度的一种量度。熵是分子随机热运动状态的几率大小的量度，也就是分子热运动的混乱程度或无序度。 若所讨论的对象不限于分子热运动，也可借用熵的概念描述并非分子热运动的其它任何物质运动方式、任何事物、任何系统的混乱度或无序度。就有另一种熵的概念，它是热力学和统计力学中熵概念的推广，称广义熵广义熵。26熵的熵的计算例计算例： 有一布袋内放有一布袋内放l00个球，其中个球，其中80个球是红色的，个球是红色的，20个球是白色的。随便
11、摸出一个球，猜测是什么颜色，个球是白色的。随便摸出一个球，猜测是什么颜色，那么其概率空间为：那么其概率空间为： 如被告知摸出的是红球，则获得的信息量是：如被告知摸出的是红球，则获得的信息量是：如被告知摸出的是红球，则获得的信息量是：如被告知摸出的是红球，则获得的信息量是： I (a1) log p(a1) log0.8= 0.32 （比特）（比特）（比特）（比特）如被告知摸出的是白球，所获得的信息量为：如被告知摸出的是白球，所获得的信息量为：如被告知摸出的是白球，所获得的信息量为：如被告知摸出的是白球，所获得的信息量为：I (a2) log p(a2) log0.2 = 2.32 （比特）（比
12、特）（比特）（比特）平均摸取一次所能获得的信息量为平均摸取一次所能获得的信息量为平均摸取一次所能获得的信息量为平均摸取一次所能获得的信息量为 ： H(X)= p(a1) I (a1) + + p(a2) I (a2) =0.72（比特（比特（比特（比特/ /符号）符号）符号）符号）27熵的含义熵是熵是从集合的统计特性从集合的统计特性来考虑的，从平均意义上来表征来考虑的，从平均意义上来表征信源的总体特征。信源的总体特征。在信源输出后，信息熵在信源输出后，信息熵H(X)表示每个消息提供的平均信表示每个消息提供的平均信息量；息量；在信源输出前，信息熵在信源输出前，信息熵H(X)表示信源的平均不确定性
13、；表示信源的平均不确定性；信息熵信息熵H(X) 表征了变量表征了变量X的随机性。的随机性。28n n例如例如例如例如，有两信源有两信源有两信源有两信源X X、Y Y，其概率空间分别其概率空间分别其概率空间分别其概率空间分别计算其熵，计算其熵，得：得：得：得：H(X)=0.08H(X)=0.08（ bit /bit /符号）符号）符号）符号） H(Y)=1H(Y)=1（bit / bit / 符号）符号）符号）符号）H(Y)H(X)，因此信源因此信源Y比信源比信源X的平均不确定性的平均不确定性要大。要大。 29例例 设甲地的天气预报为：晴设甲地的天气预报为：晴(占占48)、阴、阴(占占28)、大
14、雨大雨(占占18)、小雨、小雨(占占18)。又设乙地的天气预报。又设乙地的天气预报为：晴为：晴 (占占78)，小雨，小雨(占占18)。1）试求两地天气预报各自提供的平均信息量。）试求两地天气预报各自提供的平均信息量。2）若甲地天气预报为两极端情况，一种是晴出现概）若甲地天气预报为两极端情况，一种是晴出现概率为率为1而其余为而其余为0。另一种是晴、阴、小雨、大雨出现。另一种是晴、阴、小雨、大雨出现的概率都相等为的概率都相等为14。3）试求这两极端情况所提供的平均信息量。）试求这两极端情况所提供的平均信息量。4）又试求乙地出现这两极端情况所提供的平均信息）又试求乙地出现这两极端情况所提供的平均信息
15、量。量。30两个信源两个信源31解：甲地天气预报构成的信源空间为解：甲地天气预报构成的信源空间为:则其提供的平均信息量即信源的信息熵：则其提供的平均信息量即信源的信息熵：则其提供的平均信息量即信源的信息熵：则其提供的平均信息量即信源的信息熵：32乙地天气预报的信源空间为乙地天气预报的信源空间为:n n结论结论结论结论：甲地：甲地：甲地：甲地天气预报天气预报提供的平均信息量大于乙地，提供的平均信息量大于乙地，提供的平均信息量大于乙地，提供的平均信息量大于乙地，因为乙地比甲地的平均不确定性小。因为乙地比甲地的平均不确定性小。因为乙地比甲地的平均不确定性小。因为乙地比甲地的平均不确定性小。33甲地极
16、端情况极端情况极端情况1：晴天概率：晴天概率1n 结论结论：等概率分布等概率分布时信源的不确定性最大，时信源的不确定性最大，所以所以信息熵信息熵（平均信息量）平均信息量）最大最大。n极端情况极端情况2：各种天气等概率分布：各种天气等概率分布34乙地极端情况极端情况极端情况1：晴天概率：晴天概率1n 结论结论：在极端情况：在极端情况2下，甲地比乙地提供更多的信下，甲地比乙地提供更多的信息量。息量。 因为，甲地可能出现的消息数比乙地可能出现因为，甲地可能出现的消息数比乙地可能出现的消息数多。的消息数多。n极端情况极端情况2：各种天气等概率分布：各种天气等概率分布35候选选取-信息增益信息增益（in
17、formation gain）是指期望信息或者信息熵的有效减少量（通常用“字节”衡量），根据它能够确定在什么样的层次上选择什么样的变量来分类。（Information Gain）来衡量一个属性区分以上数据样本的能力。信息增益量越大，这个属性作为一棵树的根节点就能使这棵树更简洁，比如说一棵树可以这么读成，如果风力弱，就去玩；风力强，再按天气、温度等分情况讨论，此时用风力作为这棵树的根节点就很有价值。如果说，风力弱，再又天气晴朗，就去玩；如果风力强，再又怎么怎么分情况讨论，这棵树相比就不够简洁了。36候选选取-信息增益37候选选取-最大匹配38划分值数值型属性值从哪里划分？把属性值分为 按照上面两
18、种效用函数，计算每个分隔的评分，最高的划之分类型属性值按照分类树选择划分位置39噪音数据添加40算法复杂度分析算法DiffGen 的算法复杂度为 41实验结果分析数据质量（隐私保护质量和分类精度）算法比较（DiffGen, DiffP-C4.5, 和 TDS）42实验环境文中实验采用了开源的数据集Adult10，这个数据集是一个真实生活的人口普查数据集，常用作验证匿名化算法2，13，18，28，38，33。Adult中包含了45,222个普查记录，6个数值型属性，8个分类型属性。文献13中有对属性的详细描述。实验的硬件平台是Intel Core i7 2.7GHz PC with 12GB R
19、AM。 43实验结果447 C. Dwork. Differential privacy. In ICALP, 2006.36 P. Samarati. Protecting respondents identities inmicrodata release. IEEE TKDE, 2001.37 L. Sweeney. k-anonymity: A model for protecting privacy. In International Journal on Uncertainty,Fuzziness and Knowledge-based Systems, 2002.28 A. Ma
20、chanavajjhala, D. Kifer, J. Gehrke, and M. Venkitasubramaniam. - differential privacy beyond k-anonymity. ACM TKDD, 2007.41 R. C. W. Wong, J. Li., A. W. C. Fu, and K. Wang.(,k)-anonymity: An enhanced k-anonymity model for privacy preserving data publishing. In SIGKDD, 2006.26 N. Li, T. Li, and S. Ve
21、nkatasubramanian. t-closeness:Privacy beyond k-anonymity and -diversity. In ICDE,2007.29 D. Martin, D. Kifer, A. Machanavajjhala, J. Gehrke,and J. Halpern. Worst-case background knowledge in privacy-preserving data publishing. In ICDE, 2007.2 R. J. Bayardo and R. Agrawal. Data privacy through optima
22、l k-anonymization. In ICDE, 2005.13 B. C. M. Fung, K. Wang, and P. S. Yu. Anonymizing classification data for privacy preservation. IEEE TKDE, 19(5):711725, May 2007.23 K. LeFevre, D. J. DeWitt, and R. Ramakrishnan. Mondrian multidimensional k-anonymity. In ICDE,2006.24 K. LeFevre, D. J. DeWitt, and
23、 R. Ramakrishnan.Workload-aware anonymization techniques for large-scale data sets. ACM TODS, 33(3), 2008.39 R. C. W. Wong, A. W. C. Fu, K. Wang, and J. Pei.Minimality attack in privacy preserving data publishing. In VLDB, 2007.45 L. Zhang, S. Jajodia, and A. Brodsky. Information disclosure under re
24、alistic assumptions: Privacy versus optimality. In CCS, 2007.5 G. Cormode, D. Srivastava, N. Li, and T. Li.Minimizing minimality and maximizing utility:Analyzing methodbased attacks on anonymized data.In VLDB, 2010.19 X. Jin, N. Zhang, and G. Das. Algorithm-safe privacy-preserving data publishing. I
25、n EDBT, 2010.43 X. Xiao, Y. Tao, and N. Koudas. Transparent anonymization: Thwarting adversaries who know the algorithm. ACM TODS, 35(2), 2010.14 S. R. Ganta, S. Kasiviswanathan, and A. Smith.Composition attacks and auxiliary information in data privacy. In SIGKDD, 2008.21 D. Kifer. Attacks on priva
26、cy and de finettis theorem.In SIGMOD, 2009.40 R. C. W. Wong, A. W. C. Fu, K. Wang, Y. Xu, andP. S. Yu. Can the utility of anonymized data be used for privacy breaches? ACM TKDD, to appear.6 I. Dinur and K. Nissim. Revealing information while preserving privacy. In PODS, 2003.9 C. Dwork, F. McSherry,
27、 K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, 2006.35 A. Roth and T. Roughgarden. Interactive privacy via the median mechanism. In STOC, 2010.11 A. Friedman and A. Schuster. Data mining with differential privacy. In SIGKDD, 2010.1 B. Barak, K. Chaudhuri
28、, C. Dwork, S. Kale, F. McSherry, and K. Talwar. Privacy, accuracy, and consistency too: A holistic solution to contingency table release. In PODS, 2007.44 X. Xiao, G. Wang, and J. Gehrke. Differential privacy via wavelet transforms. In ICDE, 2010.16 M. Hay, V. Rastogi, G. Miklau, and D. Suciu. Boos
29、ting the accuracy of differentially private histograms through consistency. In VLDB, 2010.27 A. Machanavajjhala, J. Gehrke, and M. Gotz. Data publishing against realistic adversaries. In VLDB, 2009.42 X. Xiao and Y. Tao. Personalized privacy preservation. In SIGMOD, 2006.12 B. C. M. Fung, K. Wang, R
30、. Chen, and P. S. Yu. Privacy-preserving data publishing: A survey of recent developments. ACM Computing Surveys, 42(4):153,June 2010.38 K. Wang, B. C. M. Fung, and P. S. Yu. Handicapping attackers confidence: An alternative to k-anonymization. KAIS, 11(3):345368, April 2007.3 R. Bhaskar, S. Laxman,
31、 A. Smith, and A. Thakurta. Discovering frequent patterns in sensitive data. In SIGKDD, 2010.4 A. Blum, K. Ligett, and A. Roth. A learning theory approach to non-interactive database privacy. In STOC, 2008.20 S. P. Kasiviswanathan, M. Rudelson, A. Smith, and J. Ullman. The price of privately releasi
32、ng contingency tables and the spectra of random matrices with correlated rows. In STOC, 2010.8 C. Dwork. A firm foundation for private data analysis. Commun. ACM, 54(1):8695, 2011.15 M. Hardt and K. Talwar. On the geometry of differential privacy. In STOC, 2010.32 F. McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS, 2007.45
