差分隐私中噪声添加与精度分析研究_王骁识.pdf

文章编号：-（）-差分隐私中噪声添加与精度分析研究王骁识，康海燕*（北京信息科技大学 信息管理学院，北京 ）摘要：国内对于差分隐私定义以及所使用的基本机制缺乏严格清晰的证明与推导过程，对学者入门造成了困难因此针对这方面空白，通过分析、证明与应用举例的方式，对差分隐私中的拉普拉斯机制与指数机制进行了详细分析，并给出完整的数学推导过程和应用举例指出了拉普拉斯机制精度公式和指数机制精度公式存在缩放过大的问题，并且在拉普拉斯机制和指数机制精度公式的证明之后给出了放缩过大的理由通过实验得出结论，拉普拉斯机制精度公式和指数机制精度公式是精度范围过大的公式关键词：隐私保护；差分隐私；拉普拉斯机制；指数机制中图分类号：文献标志码：R e s e a r c ho nn o i s e a d d i t i o na n dp r e c i s i o na n a l y s i s i nd i f f e r e n t i a l p r i v a c y -，-（，）A b s t r a c t：，-，-，-，-K e yw o r d s：；信息技术的飞速发展使得各类数据的发布、采集、存储和分析变得方便快捷，而这些数据的收集和发布直接给个人隐私造成了威胁一方面，如果数据拥有者直接发布隐含的敏感信息，而不采用适当数据保护技术，将可能造成个人的隐私泄露另一方面，对发布后的数据进行分析也给数据的隐私带来了威胁隐私保护技术可以解决数据发布和数据分析带来的隐私威胁问题如何发布和分析而又不泄收稿日期：-基金项目：国家社科基金年度项目（），教育部人文社科项目（）通讯作者：康海燕（-），男，河北灵寿人，博士，教授 ：露隐私信息是隐私保护技术研究的主要目的传统的隐私保护模型主要是-及其扩展模型，然而这些模型主要存在两方面缺点其一，这些模型都属于基于分组的隐私保护模型，它们并不能提供足够的安全保障，许多新型的攻击方式都对基于分组的隐私保护模型形成了新的挑战，例如合成式攻击、背景知识攻击等，这些模型总是因新型攻击的出现而需要不断完善，出现这一现象的根本原因在于基于分组的模型的安全性与敌手掌握的背景知识多少有关第二个缺陷是这些早期的隐私保护模型无法提供一种有效且严格的方法来证明其隐私保护水平，因此当模型参数改变时，无法对隐私第 卷第期 年月兰州理工大学学报 保护水平进行定量分析而差分隐私能弥补这两方面的缺点，原因有二：其一，差分隐私可以抵御最大背景知识攻击，因此面对任何攻击模型都可以进行防范；其二，差分隐私有强大的数学背景作支撑，其隐私保护程度可以通过计算公式被量化差分隐私的应用范围广泛，传统的集中式差分隐私技术主要针对集中式统计发布数据的隐私保护；本地化差分隐私技术致力于客户端数据的隐私保护；在位置隐私保护上，差分隐私的应用又被扩展到二维平面上国内很少有文章对差分隐私最基本的原理和差分隐私常用机制进行详细讲解以及过程推导，因此本文的主要工作就是对传统集中式差分隐私中常用的两种机制 拉普拉斯机制和指数机制进行详细讲解，并呈现出数学的推导与证明 相关研究本节将分为国内与国外两大部分介绍差分隐私的相关研究其中，国内细分为机器学习与差分隐私、位置隐私、差分隐私的直方图发布和数据挖掘应用差分隐私四个部分进行介绍国外部分主要介绍近年差分隐私的实际应用以及近期的研究热点 差分隐私与深度学习的结合差分隐私概念自从 年被提出以来，国内已经对差分隐私做了很多有意义的研究工作关于隐私预算，何贤芒等通过理论证明和时间分析，给出了一个差分隐私保护参数的选取公式关于机器学习与差分隐私，穆海蓉等提出一种基于随机森林的差分隐私保护算法，在每一棵决策树的构建过程中采用指数机制选择分裂点和分裂属性，并根据拉普拉斯机制添加噪声陈思等提出了一种基于神经网络的多集群分布式差分隐私数据发布方法，可以缓解单服务器处理数据的压力；利用神经网络预测隐私预算参数可以提高预测精度与效率方晨等提出了一种基于生成对抗网络（-，）的差分隐私数据发布方法，通过在 模型训练的梯度上添加噪声来实现差分隐私关于位置隐私，叶阿勇等提出了一种融合预测扰动的轨迹差分隐私保护机制，利用马尔可夫链和指数扰动方法预测满足差分隐私和时空安全的扰动位置，并且设计了基于滑动窗口的隐私预算分配机制王斌等提出了通过在当前位置区域中添加噪声数据来满足差分隐私，并且通过基于用户位置偏移减少噪声添加数量的算法改进来保证数据可用性朱维军等提出一种基于统计差分隐私的轨迹隐私保护方法，根据车辆轨迹的特征计算轨迹中位置节点敏感度；并根据位置敏感度，统计阈值和敏感度阈值添加适量 噪音；使用平均相对误差评价轨迹数据的可用性大小吴云乘等根据地理空间的拓扑关系，提出了 算法计算地图上各区域的隐私级别，并定义了一种结合隐私级别与差分隐私预算的隐私模型然后，基于马尔可夫概率转移矩阵，分析了发布位置对当前真实位置和之前真实位置的影响，提出了一种差分隐私位置发布机制 ，以保护用户的位置和轨迹隐私霍峥等 首先提出了两种攻击模型，稀疏位置攻击模型和最大运行速度攻击模型；之后提出了两种隐私保护模型，在自由空间中采用基于噪音四分树的轨迹数据发布方法，在路网空间中采用基于噪音-树的轨迹数据发布方法；最后，由于差分隐私独立添加噪声可能导致数据不一致问题，提出了一种基于最大运行速度的一致性处理算法关于差分隐私的直方图发布，杨旭东等 设计了一种面向直方图数据发布的均衡差分隐私保护方法首先，结合作用域的马尔可夫模型定义了直方图关联隐私；然后，基于隐私泄露损失因素，提出一种多指标决策的隐私泄露损失评估方法；最后，借鉴 博弈与 博弈思想，设计一种均衡差分隐私保护直方图发布方法张啸剑等 提出了一种基于滑动窗分割的流式直方图发布方法，该方法采用种拉普拉斯噪音添加机制以实现差分隐私保护，分别是滑动窗机制、时间点机制以及自适应抽样机制关于数据挖掘应用差分隐私，彭慧丽等 提出了一种基于序列格的差分隐私下时间序列模式挖掘方法 （），该方法首先利用最长路径的策略对原始数据库进行截断处理，在此基础上，采用表连接操作生成满足差分隐私的序列格王金艳等 提出了一种满足差分隐私的数据流关键模式挖掘算法，该算法为关键模式中的时间戳设计了一种两阶段机制，该机制旨在平衡两方面内容，一是数据隐私和数据效用，二是挖掘时间和维护开销张啸剑等 提出了一种满足差分隐私的 -频繁模式挖掘算法，该算法利用指数机制从候选频繁模式集合中挑选出 -个携带真实支持度计数的模式，采用拉普拉斯机制扰动所选模式的真实支持度计数，并且采用后置处理技术对噪音处理后的 -个模式支持度计数进行求精处理对国内部分差分第期王骁识等：差分隐私中噪声添加与精度分析研究 隐私相关文献的整理如表所列表 国内部分差分隐私相关文献T a b D o m e s t i c l i t e r a t u r e o nd i f f e r e n t i a l p r i v a c y差分隐私分类相关文献机器学习与差分隐私决策树，指数机制文献神经网络，拉普拉斯机制文献生成对抗网络（），高斯机制文献位置隐私马尔可夫链，指数机制文献自定义机制，满足差分隐私文献拉普拉斯机制文献马尔可夫概率转移矩阵，-隐私模型（自定义）文献四分树，-树，拉普拉斯机制文献 差分隐私的直方图发布马尔可夫模型，拉普拉斯机制文献 滑动窗分割，拉普拉斯噪声文献 数据挖掘应用差分隐私序列格，拉普拉斯机制文献 关键模式挖掘算法，拉普拉斯机制文献 -频繁模式挖掘，拉普拉斯机制文献 差分隐私近年来最具代表性的工作大多出自国外首先差分隐私技术已经在工业界开始应用，苹果公司将其应用在 手机系统 上以保护用户的设备数据 谷歌公司同样使用该技术从 浏览器采集用户的行为统计数据，谷歌也在其开发的深度学习框架 中应用差分隐私技术保护训练数据的隐私 团队 于 年提出应用差分隐私的想法可以解决机器学习的 -问题，将差分隐私应用到了机器学习领域 等 提出了一种分布式选择性随机梯度下降算法（，简称 ），多方参与者可以在不共享自身真实数据的前提下，共同通过并行训练，学习出目标模型在 工作的基础上，等 基于组合定理（）提出了一种（）机制和 （-）算法 机制允许对隐私消耗进行自动跟踪分析，可以得到对隐私消耗精确的估计，其性能目前已经优于高级组合定理（）算法已经应用于 ，部署在 库中 等 设计了一种保护数据隐私的通用型框架 （），该框架不但可以保证严格的差分隐私保护，也提供一定的直观隐私（）保障 等 在 年提出了高斯机制，该机制保持了差分隐私严格可证明的特性，并且相比拉普拉斯机制和指数机制具备一定的隐私宽松度作为一种宽松的差分隐私机制，高斯机制更容易实现与应用 等 将高斯机制应用到了深度学习中对国外部分差分隐私相关文献与应用的整理如表所列表 国外部分差分隐私相关文献与应用T a b F o r e i g np a r t i a ld i f f e r e n t i a lp r i v a c y-r e l a t e dl i t e r a t u r ea n da p p l i c a t i o n分类主体内容应用苹果公司保护 用户的设备数据安全谷歌公司 对 浏览器采集用户的行为统计数据进行隐私保护 将差分隐私应用在 中文献文献 解决机器学习的 -（过拟合）问题文献 分布式选择性随机梯度下降算法文献 机制和 算法，机制用于追踪隐私预算消耗，用于差分隐私保护文献 保护数据隐私的通用型框架 文献 高斯机制文献 高斯机制应用到深度学习 差分隐私差分隐私技术保证每一个在数据集中的个体，其个人隐私不会因为加入某个数据集之后而变得更容易泄露差分隐私的思想来自于一个心理学的实验，该实验提出了随机响应的思想，对数据的查询结果采用依概率随机回答的方式，其中用到的概率思想正是差分隐私的核心思想同时，差分隐私是一个具有很强数学背景的隐私保护模型，该保护模型不关心攻击者所具有的背景知识，即使攻击者已经掌握除某一条记录之外的所有其他记录的信息，该未被掌握记录的隐私也无法被披露，这种随机响应的思想确保了隐私性；而输出结果的精确性与可用性，则通过保证输出正确结果的概率最大，以及控制噪音的大小来保证在差分隐私的实践中，为了使算法输出满足差分隐私，需要有不同的实现方法，这些方法称为“噪音机制”，在传统的集中式差分隐私技术中，拉普拉斯机制与指数机制是最常用的两种机制，拉普拉斯机制针对数值型数据，指数机制针对非数值型数据差分隐私的形式化定义如下 定义 给定数据集D和D，二者相互之间至多相差一条记录，即DD 给定一个隐私算法 （M）为M的输出范围，若算法M在数据集D和D 上任意输出结果O（O （M）满足下式，则算法M满足-差分隐私：M（D）O M（D）O（）兰州理工大学学报 第 卷其中：概率 *由算法M的随机性控制，反映了隐私被披露的风险；隐私预算参数表示隐私保护程度，越小隐私保护程度越高 差分隐私噪音机制 噪音机制噪音机制是具体实现差分隐私的一种技术手段，噪声机制使用控制所添加的噪声大小，也叫隐私预算，越大，代表隐私预算越大，隐私保护性越差，输出结果的精度越高传统的集中式差分隐私技术中常用的两种噪音机制分别是拉普拉斯机制与指数机制，拉普拉斯机制主要针对数值型的数据进行输出结果的扰动，指数机制则可以对非数值型的查询进行输出结果的扰动本地化差分隐私保护技术是基于传统集中式差分隐私技术所提出的隐私保护方案，本地化差分隐私技术可以用于终端数据的用户级隐私保护，其主流扰动技术是随机响应技术本文主要讨论的是传统的集中式差分隐私技术中常用的两种噪音机制 拉普拉斯机制与指数机制 拉普拉斯机制定义（L-敏感度）查询函数f的L-敏感度：NXRk，如下式所示：f x，yN|X|xy f（x）f（y）（）其中：x，y代表两个至多只差一条记录的数据集，称x，y是相邻数据集；Nx代表了数据集中数据的维度；R代表输出的查询结果；k代表输出结果的维度，比如从一个人口普查数据集中查询指定的 个名字的人数，那么输出就会是这指定的 个名字，以及每个名字对应的人数，这个例子中k ；f表示两个查询结果的距离度量，拉普拉斯机制使用的是范数度量，如果查询算法的输出结果是多维度的，则对应向量范数的计算方法定义（拉普拉斯分布）拉普拉斯分布表达式如下式所示：（x|b）bxb（）（）差分隐私中，因为精确性的要求，期望的噪声值为，因此取拉普拉斯分布中的 定义（拉普拉斯机制）给定一个查询函数f：NXRk，拉普拉斯机制定义如下式所示：（x，f（），）f（x）Y，Yk（）（）其中：Yi代表给每一个输出维度添加的噪音，每一个Yi独立同分布于 （f）证明拉普拉斯机制满足（，）差分隐私设xNX并且yNX满足xy，即x，y是相邻数据集，令f（）是一个查询函数f：NXRk，px和py代表扰动机制ML（x，f，）的两个概率密度函数下面计算两个概率密度函数在任一点zRk的比值：px（z）py（z）ki|f（x）izi|f f（y）izif（-）ki（|f（y）izi|f（x）izi|）f（-）ki|f（x）if（y）i|f（-）f（x）f（y）f（-）（i，k）（-）-中，因为每一个维度的zi都是一个确定的输出值，所以每个p（zi）之间是“与”的关系，因此是累乘；z是扰动后的输出值，f（x）z表示噪音值，因此求输出z的概率相当于求加入的噪声值的概率例如：查询数据库中用户患有感冒的人数，正确输出值是（即f（x），现在求扰动后输出的概率（z），那么用拉普拉斯噪音扰动后输出的概率多大？也就是 （x），即y 就可满足条件（根据式（），M（x）f（x）y），即要计算输出的概率，等价于计算y的概率，由于拉普拉斯分布中的对称性，（x）（x），因此相当于计算 （xf（x）z）的概率 -是底数相同情况下，指数相减的结果 -的不等号是一个三角不等式 -用到了向量范数，即：f（x）f（y）f（x）if（y）if（x）kf（y）kf（x）f（y）-f（x）f（y）f x，yN|X|xy f（x）f（y）定理 当Y b（），有：p Ytb（）t（）证明p（|Y|tb）p（t bYt b）t bt bbxbx bt bxbxt bxbx（）t第期王骁识等：差分隐私中噪声添加与精度分析研究 定义（拉普拉斯精度）设查询函数f：NXRk，z为扰动后的值，则有：pf（x）z k（）f（）证明已知：pf（x）ztb（）t令t k（），bfpf（x）z k（）f（）kk pf（x）z k（）f（）拉普拉斯机制精度公式的放缩是乘以k，换言之是放缩了维度，那么不难看出，维度k越大，拉普拉斯机制精度公式放缩越大，精度越不精确下面通过举例来说明拉普拉斯机制的精度如何使用例 假设有一份人口普查的数据集，先确定 个姓氏，要从数据集中统计这 个姓氏都有多少人，那么输出维度k 显然，去掉一个人的数据，只会使一项输出减，因此f，取 ，根据公式：pf（x）z k（）f得：pf（x）z （）（）pf（x）z p ikYi 本例中，所添加的最大噪音超过 的概率小于 ，即 的噪音都比 小，这对于一个十四亿人口量级的人口普查数据集来说是非常小的误差由此可以见到，加入的噪音对精度影响很小同时，可以利用数学公式来控制噪声大小 拉普拉斯机制与精度的应用下面通过实验来理解上述定义与定理在实际中的应用本实验有两个主要目的，进行三个对比实验目的一：比较加入噪声的大小对数据精度和数据分布的影响；目的二：通过实验结果进一步验证拉普拉斯机制精度公式，即公式（）的准确性实验环境：-，操作系统，数据集使用 年世界人口数据集（：q q -），数 据 集 为 格式数据，数据集中包括的属性有国家名称、国家代号、人口统计的年份、该年份该国家的人口实验过程：限制只查询并输出 年人口小于 的国家或地区的人口数，并以直方图形式呈现结果（图），为了便于对各项数据进行观察，图中横坐标的国家名称使用英文大写字母代替实验中f，拉普拉斯机制默认，通过控制的值控制所加的噪音大小，图和图为，即式（）中b 的实验结果如图和图所示，人数小于 的地区与国家一共有 个，当 时，应用公式（），针对目的一，对于上万的人口来说，如图所示，时噪音量非常小，扰动前后几乎对数据精度与分布没有影响针对目的二，取 ，算出最大噪声不超过 的概率为 ，如图所示，个噪声值都在精度范围内，符合公式结果的预期，验证了公式（）的准确性图为 ，即式（）中b 的噪音添图 原始数据分布（）F i g D i s t r i b u t i o no f o r i g i n a l d a t a（）图 噪音分布（）F i g N o i s ed i s t r i b u t i o n（）兰州理工大学学报 第 卷图 噪音分布（）F i g N o i s ed i s t r i b u t i o n（）加结果针对目的一，时，添加的噪音量已经对数据精度产生一定的影响，但不影响总体分布针对目的二，取 ，应用式（）计算出最大噪声不超过 的概率为 ，如图所示，个噪声值全部在精度范围内，符合公式结果的预期图为 ，即式（）中b 的实验结果针对目的一，时，添加的噪音量不仅对数据精度产生了一定的影响，而且影响到了数据的分布规律针对目的二，取 ，应用式（）算出最大噪声不超过 的概率为 ，如图所示，个噪声值全部在精度范围内，符合公式结果的预期图 噪音分布（）F i g N o i s ed i s t r i b u t i o n（）为进一步说明式（）是一个范围过大的公式，下面以一组对比试验进行证明分别取不同数据维度的噪声k 和k 进行对比，为控制变量，实验中个不同维度下均取，如果当维度k取值很大时，仍然有大量的噪音值在式（）所计算的范围之内，则说明式（）范围过大理由如下，取 说明 的噪声被公式（）控制在值 k（）f的范围内，假设式（）非常精确，则当k 时应有 个噪声值比 k（）f的值大，而当k 时应有 个噪声值比 k（）f的值大因此，若实验结果只有极少量噪声甚至没有噪声值比 k（）f的值大时，则说明式（）范围过大如图所示，每个不同维度的最大噪声分别为 和 ，而通过式（）计算出的噪音范围分别约为 和 当k 和k 时，不但没有 、个噪声超出公式（）计算的范围，而且所有噪声都被控制在式（）所计算的范围内，因此可以看出式（）放缩过大图 噪音分布F i g N o i s ed i s t r i b u t i o n 指数机制定义（打分函数）顾名思义，打分函数就是对每一个可能的输出项进行打分，经过打分后，每一个输出项会得到一个权值，正确的输出项得分最高，权值也最高；打分越高的项，输出概率越高定义（指数机制敏感度）指数机制的敏感度由打分函数控制，其形式化定义为 u rR x，y：xy u（x，r）u（y，r）（）第期王骁识等：差分隐私中噪声添加与精度分析研究 其中：R代表所有可能的输出项；xy代表相邻数据集注意，打分函数的敏感度只与打分函数所对应的数据库参数有关定义（指数机制定义）指数机制ME（x，u，R）选择并输出元素rR，其概率与u（x，r）u成正比指数机制的输出是通过归一化后去确定每一项的输出概率其形式化定义 为pMEx，u，R（）ru（x，r）ur Ru（x，r）u（）其中：u（x，r）u代表了每一个可能输出项经由打分函数后获得的权值；r Ru（x，r）u代表了所有可能输出项获得的权值的总和；每个可能输出项的概率就是这两个权值的比值以下是指数机制应用的实例，如表所列表 指数机制的应用实例T a b A p p l i c a t i o ne x a m p l e o f e x p o n e n t i a lm e c h a n i s m项目得票数u 概率 足球 排球 篮球 网球 本例中，设置查询函数为查询哪个项目得票数最多，打分函数设计为得票数，即足球 分、排球 分、篮球分、网球分，打分函数的敏感度与所对应的参数相关，因此当删除数据集中的一项后，假设是足球少了一票，那么按照所设计的打分函数，足球变为 分，其他项得分不变，因此u，为隐私预算，越大隐私预算越大，输出正确值的概率越高本例中计算 ，足球的输出概率过程如下：计算足球的权值u（x，r）u 计算所有权值的和 则p MEx，u，R（）足球（）此处只计算一项作为示例，表中其余结果计算方法相同下面是指数机制满足（，）差分隐私的证明：p ME（x，u，R）rp ME（y，u，R）ru（x，r）ur Ru（x，r）u u（y，r）ur Ru（y，r）uu（x，r）uu（y，r）ur Ru（y，r）ur Ru（x，r）u （u（x，r）u（y，r）ur Ru（y，r）ur Ru（x，r）u r R（u（x，r）u）ur Ru（x，r）ur Ru（x，r）ur Ru（x，r）u证明最关键之处，在第四步（即不等号的后半部分），这里默认uu（y，r）u（x，r），即u（y，r）u（x，r），如果这里的u（y，r）u（x，r），最后证明出来的结果是p ME（x，u，R）rp ME（y，u，R）r，而是隐私预算，默认，即，因此若u（y，r）u（x，r），则证明出来没意义定义（指数机制精度）定义数据集x，令 u（x）rRu（x，r），u（x）代表了得分最高项 的 分 数，令R rR：u（x，r）u（x），表示得分最高的项数，R ，比如表的例子中，只有足球打分最高，则R 指数机制精度的定义如下式所示：p u ME（x，u，R）（）u（x）u|R|R （）t（）t（）证明指数机制精度只需证明下式即可：p u ME（x，u，R）（）c|R|R （c u（x）u（c u（x）u|R|R （）证明p u ME（x，u，R）（）cr：u（x，r）cu（x，r）ur Ru（x，r）u（-）|R|c uR u（x）u（-）|R|R （c u（x）u（-）式（）描述的是得分小于等于c的项输出的概兰州理工大学学报 第 卷率有多大因此 -就是按照这个意义将式子展开，先算出来每一项的概率，再把每一个得分小于等于c的项加起来 -用到了放缩，将最外面的累加放大成R，R代表所有可能输出项的项数，因此得分小于等于c的项数一定小于等于R；将分子放大，原本分子的u（x，r）c，现在全部放大成c；将分母缩小，原本分母是所有可能的输出项累加，缩小成只是得分最高项累加 -是整理第二步得出的结果指数机制精度公式的放缩是将分母缩小，分子放大只有当正确项的权值很高，错误项权值的和较小时，指数机制精度公式的精度才会较为准确，通过下面的实例也可以看出指数机制精度公式的问题指数机制本身可以通过计算各项权重后，通过各项权重的百分比得出每一项输出的概率，因此指数机制的精度公式实用性方面也存在疑问下面通过一个例子展示指数机制的精度如何使用例 假设数据集中统计了两种疾病和 的计数为，的计数为c，执行查询函数，查询哪种疾病患者最多，显然可以使用指数机制进行扰动，设置打分函数为统计人数，因此u，的分数是，的分数是c，那么请问输出错误结果（即输出）的概率被控制在什么范围内？可以通过以下计算得到：p u ME（x，u，R）（）|R|R （c u（x）u（c）c通过式（），可以更方便地得到错误答案的输出概率，以便通过调整隐私预算进行控制；也可以试试计算最高分小于c的概率是多少，很明显，这个概率的最精确值一定是，因为最高分就是c，所以输出项的得分小于等于c的概率一定是，用指数机制精度公式计算的结果如下：p u ME（x，u，R）（）c|R|R （c u（x）u（cc）由计算结果可以看出，指数机制的精度公式同样算出来的是一个更大范围的数其实从式（）的推导就可以看出来，在式（）的推导过程中，第二步的放缩是将分子上的值全部放大，同时分母上的值缩小，直觉上就是一个很大的放缩 指数机制与精度的应用通过实验来了解上述定义与定理在实际中的应用，本实验有两个主要目的，目的一：通过两个对比实验，比较当加入不同大小的噪音时，对指数机制下输出正确结果概率大小的影响；目的二：通过实验进一步验证指数机制的精度公式，即式（）实验环境：，操作系统，数据集使用 人口数据集（：-）数据集中记录有每个人的学历，一共有 种不同的学历项在实验中，查询在 种学历中，哪种类型的学历人数最多，将横坐标每种学历用大写英文字母代表以人数多少作为打分函数，显然在这个实验中u，但由于指数函数的指数增长性，将打分函数直接设定为人数时需要设置很小，否则程序计算会发生溢出因此在实际应用中，如何设计一个好的打分函数，使隐私预算更加合理，也是一个很重要的研究点取 ，实验结果如图 所示可以看出，可能输出项有 项，即R ，最高得分输出项有一项，是 -（表中的学历），即R 打分函数设置为人数，因此最高分 u（x）针对目的一，通过定义，验证计算经过打分函数后各项的权值，这里只算一项作为示例：图 各学历人数（）F i g N u m b e r o f p e o p l eb y e d u c a t i o n l e v e l（）图 各项经打分函数后的权值（）F i g W e i g h t s a f t e r s c o r i n g f u n c t i o n s（）第期王骁识等：差分隐私中噪声添加与精度分析研究 图 各项输出概率（）F i g O u t p u t p r o b a b i l i t y（）图 查询 次的输出结果（）F i g O u t p u t r e s u l t s o f q u e r i e s（）-的值 u（x，-）u 如图所示，符合实验结果最高项的输出概率很高，扰动程度较小针对目的二，验证指数机制精度式（）应用式（）计算输出错误可能项的概率至多为多少，即pu（x，r），计算过程如下：p u ME（x，u，R）（）|R|R （c u（x）u （）如图，输出错误可能项的最精确概率值约为 ，而 ，因此符合结果同时，不难看出在例中分析指数机制的精度公式放缩过大是有道理的取 ，实验结果如图 所示这步实验的目的主要为进一步体现目的一，当隐私预算非常小，即噪声很大时会严重影响正确答案的输出概率，比如本次实验中正确答案为“-”（表中的学历），但当噪声很大时，查询 次，如图 所示，只有次输出正确答案验证指数机制精度式（），这里计算输出错误可图 各项经打分函数后的权值（）F i g W e i g h t s a f t e r s c o r i n g f u n c t i o n s（）图 各项输出概率（）F i g O u t p u t p r o b a b i l i t y（）图 查询 次的输出结果（）F i g O u t p u t r e s u l t s o f q u e r i e s（）能项的概率至多为多少：p u ME（x，u，R）（）|R|R （c u（x）u （）结果是输出错误答案的概率不超过 ，显然这是一个没有参考价值的答案，因此指数机制精度公式的放缩问题和实用价值确实存在问题 结语本文主要对差分隐私的定义、拉普拉斯机制及其精度、指数机制及其精度进行了分析，并呈现出了有关定义与定理的推导与证明过程，可以帮助学者更快更深入地理解和使用差分隐私本文通过例子和实验的证明，指出了拉普拉斯机制精度公式和指数机制精度公式存在放缩过大的问题，如何给出更精确的精度公式也是在以后的学习与研究中需要进一步探究的问题同时，本文没有对高斯机制、宽松定义的差分隐私、差分隐私组合定理以及组合定理的边界等内容作出解释与证明，这是以后进一步学习与研究的地方兰州理工大学学报 第 卷参考文献：熊平，朱天清，王晓峰差分隐私保护及其应用 计算机学报，（）：-何贤芒，王晓阳，陈华辉，等差分隐私保护参数的选取研究通信学报，（）：-穆海蓉，丁丽萍，宋宇宁，等 ：一种面向随机森林的差分隐私保护算法 通信学报，（）：-陈思，付安民，柯海峰，等 ：基于神经网络的多集群分布式差分隐私数据发布方法 电子学报，（）：-方晨，郭渊博，王娜，等基于生成对抗网络的差分隐私数据发布方法 电子学报，（）：-叶阿勇，孟玲玉，赵子文，等基于预测和滑动窗口的轨迹差分隐私保护机制 通信学报，（）：-王斌，张磊，张国印敏感渐进不可区分的位置隐私保护计算机研究与发展，（）：-朱维军，游庆光，杨卫东，等基于统计差分的轨迹隐私保护计算机研究与发展，（）：-吴云乘，陈红，赵素云，等一种基于时空相关性的差分隐私轨迹保护机制 计算机学报，（）：-霍峥，孟小峰一种满足差分隐私的轨迹数据发布方法计算机学报，（）：-杨旭东，高岭，王海，等一种面向直方图发布的均衡差分隐私保护方法 计算机学报，（）：-张啸剑，孟小峰基于差分隐私的流式直方图发布方法 软件学报，（）：-彭慧丽，金凯忠，付聪聪，等基于序列格的隐私时序模式挖掘方法 电子学报，（）：-王金艳，刘陈，傅星珵，等差分隐私的数据流关键模式挖掘方法 软件学报，（）：-张啸剑，王淼，孟小峰差分隐私保护下一种精确挖掘 -频繁模式方法 计算机研究与发展，（）：-叶青青，孟小峰，朱敏杰，等本地化差分隐私研究综述 软件学报，（）：-，：-，（）：-，-：，e ta l ：-，（）：-，-（）：，：-，e ta l -：，：-，e t a l -：，：-，（）：-，e t a l -：q -，（）：-张啸剑，孟小峰面向数据发布和分析的差分隐私保护 计算机学报，（）：-，-，：，：-，e ta l ，（）：-，-：，：-第期王骁识等：差分隐私中噪声添加与精度分析研究