差分隐私保护下的高维数据集发布

朱 徐 亚

(安徽理工大学 计算机科学与工程学院， 安徽 淮南 232001)

近年来，个人隐私泄露问题开始引发人们的担忧，数据隐私保护成为计算机学科的热门领域。其中，高维合成数据集的隐私保护数据发布问题是一个巨大的挑战。一般的高维数据集发布算法会出现计算复杂度过高的问题，若直接使用扰动策略对数据集加噪，会因为注入过多的噪声导致数据的可用性降低。目前最流行的解决方案是采用差分隐私机制[1]。Mohammed等[2]提出了一种针对决策树分析的差分隐私合成数据发布算法DiffGen。Chen等[3]提出了一种基于新型稀疏向量技术合成数据集的方法，结合差分隐私分析所有属性之间的成对关系生成无向的依赖关系图，并由此得到联合树模型。然而该新型向量技术中的隐私分析过程是错误的[4]，无法实现预期的隐私保障。Li等[5]提出了一个利用高斯Copula函数的差分隐私数据合成器DPSynthesizer。Zhang等[6]提出了一种基于贝叶斯网络的高维合成数据集生成算法PrivBayes，目前流行的GAN模型的结构化数据生成算法仍处于起步阶段，存在诸多缺陷[7-8]。

为了解决PrivBayes在贝叶斯网络建模阶段使用互信息作为属性相关性衡量标准所带来的数据信噪比低的问题，本文提出基于差分隐私采样机制的DPSM-Bayes算法，通过采样机制调整数据量的大小，能够使数据集获得最优可用性，提出一种改进的Laplace机制替换原本的差分隐私Laplace机制，可以有效地降低在较低的概率分布上添加正的Laplace噪声所引起的系统偏差，在隐私保护程度不变的情况下，进一步提高数据集的可用性。

1 基本概念

假设数据持有方A将数据发布给数据使用方B，数据使用方B希望从数据中学到尽可能多的知识，与此同时，A不希望B学到任何的个体信息。假设数据持有方A持有的数据集为高维列表数据集，数据集D由d个属性或随机变量组成，即X={X1,X2,…,Xd}，数据集包含n条元组且符合独立同分布。算法实现的目标是采用非交互式查询框架，直接发布一个满足差分隐私保护的脱敏的合成数据集。

1.1 差分隐私

2006年，Dwork等[9]提出差分隐私的概念，要求所发布数据集的任何信息必须要经过一个随机化算法的处理，保障数据集中的任何一条记录的个体信息不被泄露。差分隐私拥有严格的统计学定义，能够对隐私保护水平进行量化评估。

定义1ε-差分隐私[9]：假设有随机化算法G，O为G的任意可能输出，若对于任意两个至多相差一条元组的相邻数据集D1和D2，满足：

Pr[G(D1)=O]≤eε·Pr[G(D2)=O]

(1)

则称算法G满足ε-差分隐私保护。其中:参数ε为隐私保护预算；Pr[·]表示事件发生的概率。

定义2 全局敏感度[9]：设有函数f:D→Rd，输入为一数据集，输出为一个d维实数向量，对于任意的相邻数据集D1和D2，

(2)

称为函数f的全局敏感度。

定义3 Laplace机制[9]：设有函数f:D→Rd，函数的敏感度为Δf，若Y～Lap(Δf/ε)为加入的随机噪声，则算法G(D)=f(D)+Y满足ε-差分隐私保护。

定义5 序列组合性[11]：设有一个随机化算法序列G1,G2,…,Gm，算法Gi符合εi-差分隐私保护，则算法序列Gi(D)满足(∑iεi)-差分隐私保护。

定义6 并行组合性[12]：设有一组随机化算法G1,G2,…,Gm，算法Gi符合εi-差分隐私保护，对于任意不相交的数据集D1,D2,…,Dm，则由这些算法组成的组合算法G(G1(D1),G2(D2),…Gm(Dm))满足(maxεi)-差分隐私保护。

1.2 贝叶斯网络

贝叶斯网络[13]又被称为信念网络，是一种概率图型模型，是一个有向无环图如图1所示。对于数据集D，D中的每个属性被表示为一个节点，数据集中属性间的相互关系被表示为有向边的形式。

图1 贝叶斯网络

贝叶斯网络为概率分布提供了一种简洁的表示方式，可以使用贝叶斯网络来描述概率分布中随机变量之间的相互依赖关系，从而描述一个概率分布。假设有一个离散随机变量集合X={X1,X2,…,Xd}，贝叶斯网络可以将它们的联合概率分布表示为

(3)

也称贝叶斯网络的链式法则[14]，贝叶斯网络结构学习领域就是专门研究这个问题的[15]。

2 差分隐私保护下的高维数据集发布算法

针对PrivBayes算法的缺点，本文提出一种新颖的差分隐私保护下的高维数据集发布算法DPSM-Bayes，实现流程图如图2所示。

图2 差分隐私保护下的高维数据集发布算法流程图

2.1 基于采样机制构建满足差分隐私保护的贝叶斯网络

为了降低计算复杂度，GreedyBayes算法将贝叶斯网络的度k限制在一个较小的值，大大减少了时间开销，使用互信息作为属性间相关程度的评分函数，利用差分隐私指数机制，选择出满足差分隐私保护的最优父节点集，进而构造出满足差分隐私保护的贝叶斯网络。

相比较于互信息I的值域，互信息的敏感度是一个不小的值，当评分函数的敏感度较大时，很有可能添加的噪声量覆盖了原本的数据量，导致构建的贝叶斯网络结构与数据集概率分布的拟合程度较差。因此，本文利用差分隐私采样机制[16]满足差分隐私保护的贝叶斯网络构建算法SMBayes。

定义7 采样机制[16]：设有满足ε-差分隐私的随机化算法G，则对于这样的一个算法Gα：首先以概率α对输入数据集中每条元组独立采样，接着对采样得到的数据集应用算法G。则算法Gα为输入数据集提供了ln(1+α(eε-1))-差分隐私保护。

本文提出基于差分隐私采样机制的子算法SMBayes算法，输入为原始数据集D、贝叶斯网络的度k、隐私预算ε1，输出为贝叶斯网络N。该算法的具体描述步骤：

(1)计算采样率α；

(2)以概率α对D中的元组采样，得到输入数据集D′；

(3)εα=ln(eε1-1+α)-lnα；

(4)初始化N=∅，V=∅；

(5)随机选取X中的一个属性作为贝叶斯网络的首节点X1，将(X1,∅)添加到N，将X1添加到V；

(6)fori=2 tod;

(7)初始化Ω=∅；

(9)对输入数据集D′，使用差分隐私指数机制，以互信息为评分函数，隐私预算为εα/(d-1)，从Ω中选出一个AP对(Xi,Π(Xi))；

(10)将选出的AP对(Xi,Π(Xi))添加到N，将Xi添加到V；

(11)end for;

(12)returnN。

通过分析不同数据集大小情况下，敏感度ΔI与采样机制的隐私预算εα之间的关系，得到采样输入数据集D′最佳尺寸的计算公式：

(4)

其中：1

2.2 基于改进的Laplace机制对边缘分布加噪

本文提出改进的Laplace机制IMLap-Noisy算法。该算法的输入为原始数据集D、贝叶斯网络N、隐私预算ε2，输出为d个满足差分隐私保护的边缘条件概率分布。IMLap-Noisy算法具体描述步骤：

(1)初始化P*=∅；

(2)fori=1 tod；

(3)由AP对(Xi,Π(Xi))和D实体化联合概率分布Pr(Xi,Π(Xi))；

(5)根据Pr*(Xi,Π(Xi))计算阈值t；

(6)forpinPr*(Xi,Π(Xi));

(7)ifp

(8)end for;

(9)归一化Pr*(Xi,Π(Xi))；

(10)由Pr*(Xi,Π(Xi))得到Pr*(Xi|Π(Xi))并将其添加到P*；

(11)end for;

(12)returnP*;

阈值t计算是IMLaplace机制的核心，t的计算公式为

(5)

其中:t=i/1 000，i∈*且0

从边缘分布采样生成合成数据集的过程相对于前两个过程较为简单，利用贝叶斯网络的特点，采用逻辑采样方法[17]。每次通过一个低维条件概率分布采样出对应的一个属性值，作为其他属性的父节点取值进而确定下一个属性的值。由于贝叶斯网络是一个有向无环图，当我们对最后一个属性进行采样时，在此之前的所有属性都已经采样结束，即得到了一条完整的记录。逻辑采样可以生成任意数量的记录，考虑到某些应用需要合成数据集与原始数据集的记录数量相似，同时有利于在实验评估阶段对两个数据集进行对比分析，仍然选用n作为合成数据集的大小。

3 实验评估

实验选用的数据集的具体描述如表1所示，选用平均变分距离和Wasserstein距离作为概率分布间的距离度量，选用SVM分类准确度作为合成数据集可用性的度量标准。

表1 实验选用的数据集

3.1 IMLaplace机制的性能

为了评估IMLaplace机制的性能，将IMLaplace机制与原始Laplace机制进行对比，采用平均变分距离和Wasserstein距离作为加噪前后的概率分布的距离度量，评估两种机制加入的噪声对概率分布的影响；将由概率分布采样出的数据集构造的支持向量机(SVM)分类器模型的分类准确度作为数据可用性的度量，一定程度上可以反映两种加噪机制对数据集质量的影响程度。实验中选用的数据集为Cancer、Sachs和Alarm，实验结果均为20次实验的平均值。实验结果如表2和表3所示。在平均变分距离和Wasserstein距离2种度量下，IMLaplace机制都取得了比原始的Laplace机制更好的效果。

表2 平均变分距离 单位：%

表3 Wasserstein距离 单位：%

在评估2种加噪机制对数据集质量和可用性的影响，每个数据集分别选出两个属性作为两组实验的类别属性，其他属性作为特征属性，构造SVM分类器模型，将原始数据集的20%作为测试集，验证2种机制下的分类准确度。隐私预算ε设置为0.01～1.6，结果如图3～图5所示。NoLaplace表示不对概率分布进行Laplace加噪处理，在图中作为基准分类准确度。

(a) Cancer Y=Smoker (b) Cancer Y=Cancer

(a) Sachs Y=Mek (b) Sachs Y=Raf

(a) Alarm Y=LVEDVolume (b) Alarm Y=TPR

随着隐私预算ε的增加，不同数据集上属性的分类准确度均逐渐增大因为隐私预算增加时，对数据的隐私保护程度降低，对数据添加的噪声扰动较少，数据集的质量和可用性提高。当隐私预算ε的值较小时，能够看到IMLaplace机制得到的数据集的分类准确度明显高于Laplace机制，并且随着隐私预算ε的增加，两者之间的差距呈现逐渐缩小的变化趋势，直到接近基准分类准确度，因为在隐私预算ε的值较小的情况下，Laplace机制添加的噪声值较大的概率最高，对较低的概率值添加正噪声的概率也最高，IMLaplace机制能够很好地解决该问题。

3.2 DPSM-Bayes算法的性能

为了验证和评估DPSM-Bayes算法的性能优越性，选用PrivBayes算法作为对照组，分别让两种算法输出的合成数据集执行分类任务，选用SVM分类器作为分类模型，通过分类准确度验证两种算法生成的数据集的质量和可用性，如图6和图7所示。

随着隐私预算ε的增加，在NLTCS和ACS两个数据集上的分类准确度均逐渐增加，表明隐私保护程度和数据的可用性是矛盾的，隐私保护程度越高，数据集的可用性就越低。因此，在实际应用中要在隐私保护程度和数据可用性之间寻求一个平衡点。另外，相对于NLTCS数据集，ACS数据集上2种算法的分类准确度与基准分类准确度的距离明显更大。在图6和图7中，DPSM-Bayes算法生成数据集的分类准确度均高于PrivBayes算法的分类准确度，表明DPSM-Bayes算法生成的数据集的质量和可用性明显优于PrivBayes算法。

(a) NLTCS Y=Outside (b) NLTCS Y=Bathroom

(a) ACS Y=Mortgage (b) ACS Y=School

4 结 语

为了解决隐私保护高维数据集发布中存在的计算复杂度高和数据可用性低的问题，针对PrivBayes算法的缺陷，提出了DPSM-Bayes算法，优化了互信息敏感度过高带来的信噪比低的问题，利用差分隐私采样机制选取更合适的数据集尺寸，从而缓解该问题。本文还提出了更适合于高维数据分布加噪的IMLaplace机制，能够有效地缓解由于在较低的概率值上加入正噪声所带来的误差。在相同的隐私保护程度下，DPSM-Bayes算法在数据生成质量和可用性上明显优于PrivBayes算法，实现了隐私保护高维数据集发布在隐私性和可用性之间的平衡。