差别隐私保护及其

null差别隐私保护及其应用差别隐私保护及其应用null来自两篇KDD会议文章 KDD2011 Differentially Private Data Release for Data Mining KDD2010 Data Mining with Differential Privacynull敏感信息保护 问题提出与描述敏感信息敏感信息私有性 敏感性 易暴露 例如：姓名、身份号、年龄等信息敏感保护新问题敏感保护新问题基于背景知识的隐私攻击 实例，87%的美国人身份可以通过5位压缩码（5-digit zip code）、性别和出生日期组成的属性集合唯一地被辨识。这个属性集合被称为准标识（Quasi-IDentifier ，QID）。敌手可能通过一些公开的来源获得这些属性集合信息，比如公众投票 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf （a voter list）。通过简单地连接外部数据源中的QID属性集合，一个人的私有信息可能会被暴露。目前的解决方法目前的解决方法匿名化算法 k-匿名的隐私保护模型（k-anonymity privacy model）[36, 37] ι-多样化（ι-diversity ）[28] （a，k）匿名（(α,k)-anonymity）[41] t-密闭（t-closeness）[26] （c，k）-安全（(c,k)-safety）[29]交互式与非交互式隐私保护数据发布中的技术数据发布中的技术泛化技术[36,37] 基于泛化技术的匿名算法[2,13,23,24,36]已经被提出来 新颖的隐私保护模型新颖的隐私保护模型差别隐私（Differential Privacy）[7] 差别隐私是一个新颖的隐私定义，可以提供强的隐私保护。 基于划分的隐私保护模型的输出数据需要保持k个记录是难以分辨的，或者敏感信息值都在每一个等价组中被很好地描述。 然而，差别隐私的保护可以保证敌手对于个体的知识一无所知，无论个人的记录在不在数据当中出现。 简言之，从一个个体的角度来看，输出的处理就像是对一个不包含个体个人记录的数据集进行计算一样。差别隐私保护差别隐私保护定义 3.1 ε-差别隐私(ε-differential privacy) . 一个随机算法是差别隐私的当对于所有的数据集和来说，他们的对称的差别（symmetric difference）最多包含一个记录，对于所有的可能的匿名化数据集来说有其中，概率值是在算法的随机性前提下的。 参数ε > 0是公开的而且是由数据拥有者指定的。ε 取值越小提供的隐私保护越强。 差别隐私保护差别隐私保护差别隐私保护的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 机制是通过向一个函数的真实输出中添加随机的噪音的方法完成的。 噪音通过函数的敏感度来调整。函数的敏感度是从两个只有一个记录不同的数据集中得到的输出的最大差别。 差别隐私保护-拉普拉斯机制 差别隐私保护-拉普拉斯机制 Dwork等人在文献[9]中提出了拉普拉斯机制 作用是确定添加噪音数据的大小差别隐私保护-指数机制差别隐私保护-指数机制McSherry and Talwar在文献[32]中提出了指数机制 作用是对效用函数计算的候选评分进行选择 越高的计分的输出与被选择输出指数倍地趋近 上述所说的定义与机制都已被证明，满足 ε-差别隐私 问题提出与描述问题提出与描述假设一个数据拥有者打算发布一个数据集给公众用于数据分析-所属这个类别属性的值-包含了d个属性的集合 类别属性是用来分类的，预测器属性要么是数值型的要么是类别型属性。 问题提出与描述问题提出与描述对于一个数据集 和隐私参数 ，文中算法的目标是生成一个匿名数据集 ，使得（1） 满足 - differential privacy，同时（2）尽可能多的保留用于分类分析的信息。算法描述算法描述基于泛化技术的差别隐私匿名化算法（Differentially-private anonymization algorithm based on Generalization ，DiffGen） 算法描述算法描述nullLine 1 起初， 在中的所有值都泛化成类别树中最高层的值 Line 2 中包含了每一个属性的值 Line 7 每一次DiffGen算法的迭代过程都要基于概率地选择一个在 中的候选 来进行下一次的细化过程 Line 8 算法细化选择的候选v，更新 Line 10 更新受影响的候选的评分以为下次细化过程所用 Line 12 把在拉布拉斯分布中选取噪音数据添加到按上述细化过程分类的组当中的统计计数中 实例实例细化过程划分顶层关键步骤详析关键步骤详析候选选取 划分值选择 噪音数据添加候选选取候选选取选取候选哪个 进行细化 通过两个方法计算候选评分值 信息增益 最大匹配候选选取-信息增益候选选取-信息增益有趣的物理学名词信息论应用-熵（entropy） 信息熵是指 对信息具体的量化度量问题。信息论之父 C. E. Shannon 第一次用数学语言阐明了概率与信息冗余度的关系。自信息自信息离散信源X的概率空间为：I(ai)有两种含义： （1）当ai发生前，表示ai发生的不确定性 （2）当ai发生后，表示ai所提供的信息量称事件ai发生含有的信息量为 ai 的自信息量[例] 8个串联的灯泡x1，x2，…，x8，损坏的可能性是等概的，现假设其中有一个灯泡已损坏，问每进行一次测量可获得多少信息量？总共需要多少次测量才能获知和确定哪个灯泡已损坏。 [例] 8个串联的灯泡x1，x2，…，x8，损坏的可能性是等概的，现假设其中有一个灯泡已损坏，问每进行一次测量可获得多少信息量？总共需要多少次测量才能获知和确定哪个灯泡已损坏。 8个灯泡等概率损坏，先验概率P (x1)=1/8 ，即8个灯泡等概率损坏，先验概率P (x1)=1/8 ，即第二次测量获得的信息量 = I [P (x2)] - I [P (x3)]=1(bit) 第三次测量获得的信息量 = I [P (x3)] =1(bit) 至少获得3bit信息量就可知道哪个灯泡已坏了。第一次测量获得的信息量=I [P (x1)] - I [P (x2)]=1(bit) 经过二次测量，剩2个灯泡，等概率损坏，P (x3)=1/2一次测量后，剩4个灯泡，等概损坏，P (x2)=1/4信息熵信息熵一个信源发出不同的消息所含有的信息量也不同，故自信息I(ai)是随机变量，不能用它来作为整个信源的信息测度 定义自信息的数学期望为平均自信息量Hr(X)，称为信息熵：熵（entropy）熵（entropy）经典热力学中熵的概念，最先由克劳修斯提出。它的定义即“热温商”，作为热力学过程不可逆程度的一种量度。熵是分子随机热运动状态的几率大小的量度，也就是分子热运动的混乱程度或无序度。 若所讨论的对象不限于分子热运动，也可借用熵的概念描述并非分子热运动的其它任何物质运动方式、任何事物、任何系统的混乱度或无序度。就有另一种熵的概念，它是热力学和统计力学中熵概念的推广，称广义熵。熵的计算例： 有一布袋内放l00个球，其中80个球是红色的，20个球是白色的。随便摸出一个球，猜测是什么颜色，那么其概率空间为： 熵的计算例： 有一布袋内放l00个球，其中80个球是红色的，20个球是白色的。随便摸出一个球，猜测是什么颜色，那么其概率空间为： 如被告知摸出的是红球，则获得的信息量是： I (a1) ＝－log p(a1) ＝－log0.8= 0.32 （比特） 如被告知摸出的是白球，所获得的信息量为： I (a2) ＝ －log p(a2) ＝ －log0.2 = 2.32 （比特） 平均摸取一次所能获得的信息量为 ： H(X)= p(a1) I (a1) + p(a2) I (a2) =0.72（比特/符号）熵的含义熵的含义熵是从集合的统计特性来考虑的，从平均意义上来表征信源的总体特征。 在信源输出后，信息熵H(X)表示每个消息提供的平均信息量； 在信源输出前，信息熵H(X)表示信源的平均不确定性； 信息熵H(X) 表征了变量X的随机性。null例如，有两信源X、Y，其概率空间分别 计算其熵，得：H(X)=0.08（ bit /符号） H(Y)=1（bit / 符号） H(Y)＞H(X)，因此信源Y比信源X的平均不确定性要大。 [例] 设甲地的天气预报为：晴(占4／8)、阴(占2／8)、大雨(占1／8)、小雨(占1／8)。又设乙地的天气预报为：晴 (占7／8)，小雨(占1／8)。 1）试求两地天气预报各自提供的平均信息量。 2）若甲地天气预报为两极端情况，一种是晴出现概率为1而其余为0。另一种是晴、阴、小雨、大雨出现的概率都相等为1／4。 3）试求这两极端情况所提供的平均信息量。 4）又试求乙地出现这两极端情况所提供的平均信息量。[例] 设甲地的天气预报为：晴(占4／8)、阴(占2／8)、大雨(占1／8)、小雨(占1／8)。又设乙地的天气预报为：晴 (占7／8)，小雨(占1／8)。 1）试求两地天气预报各自提供的平均信息量。 2）若甲地天气预报为两极端情况，一种是晴出现概率为1而其余为0。另一种是晴、阴、小雨、大雨出现的概率都相等为1／4。 3）试求这两极端情况所提供的平均信息量。 4）又试求乙地出现这两极端情况所提供的平均信息量。null两个信源解：甲地天气预报构成的信源空间为:解：甲地天气预报构成的信源空间为:则其提供的平均信息量即信源的信息熵：null乙地天气预报的信源空间为:结论：甲地天气预报提供的平均信息量大于乙地，因为乙地比甲地的平均不确定性小。甲地极端情况甲地极端情况极端情况1：晴天概率＝1 结论：等概率分布时信源的不确定性最大，所以信息熵（平均信息量）最大。极端情况2：各种天气等概率分布乙地极端情况乙地极端情况极端情况1：晴天概率＝1 结论：在极端情况2下，甲地比乙地提供更多的信息量。 因为，甲地可能出现的消息数比乙地可能出现的消息数多。极端情况2：各种天气等概率分布候选选取-信息增益候选选取-信息增益信息增益（information gain）是指期望信息或者信息熵的有效减少量（通常用“字节”衡量），根据它能够确定在什么样的层次上选择什么样的变量来分类。 （Information Gain）来衡量一个属性区分以上数据样本的能力。信息增益量越大，这个属性作为一棵树的根节点就能使这棵树更简洁，比如说一棵树可以这么读成，如果风力弱，就去玩；风力强，再按天气、温度等分情况讨论，此时用风力作为这棵树的根节点就很有价值。如果说，风力弱，再又天气晴朗，就去玩；如果风力强，再又怎么怎么分情况讨论，这棵树相比就不够简洁了。 候选选取-信息增益候选选取-信息增益候选选取-最大匹配候选选取-最大匹配划分值划分值数值型属性值从哪里划分？ 把属性值分为 按照上面两种效用函数，计算每个分隔的评分，最高的划之 分类型属性值按照分类树选择划分位置 噪音数据添加噪音数据添加算法复杂度分析算法复杂度分析算法DiffGen 的算法复杂度为 实验结果分析实验结果分析数据质量（隐私保护质量和分类精度） 算法比较（DiffGen, DiffP-C4.5, 和 TDS）实验环境实验环境文中实验采用了开源的数据集Adult[10]，这个数据集是一个真实生活的人口普查数据集，常用作验证匿名化算法[2，13，18，28，38，33]。Adult中包含了45,222个普查记录，6个数值型属性，8个分类型属性。文献[13]中有对属性的详细描述。实验的硬件平台是Intel Core i7 2.7GHz PC with 12GB RAM。 实验结果实验结果null[7] 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. Machanavajjhala, 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. Venkatasubramanian. 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 optimal 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):711–725, 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 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 realistic 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. In 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 privacy and de finetti’s 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, 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, 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. Boosting 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. Chen, and P. S. Yu. Privacy-preserving data publishing: A survey of recent developments. ACM Computing Surveys, 42(4):1–53, June 2010. [38] K. Wang, B. C. M. Fung, and P. S. Yu. Handicapping attacker’s confidence: An alternative to k-anonymization. KAIS, 11(3):345–368, April 2007. [3] R. Bhaskar, S. Laxman, 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 releasing 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):86–95, 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.