基于评分函数的差分隐私数据发布方法

《Future Internet》：Differential Privacy Data Publication Based on Scoring Function Ke Yuan, Quan Zhang, Yinghao Lin, Yuye Wang and Chunfu Jia

　　

现有基于贝叶斯网络（Bayesian Network）的差分隐私算法主要采用均匀隐私预算分配。然而，由于属性节点承载的信息量具有异质性，传统隐私预算分配策略可能导致对重要属性添加的噪声不足，而对不太重要的属性添加过多噪声。为优化隐私预算利用，研究人员提出了SA-PrivBayes，一种由评分函数驱动的分配方法。为提升贝叶斯网络精度，研究人员在网络构建过程中引入阈值机制，在应用指数机制（Exponential Mechanism）进行选择之前，先对低评分属性对进行预筛选。随后，在参数学习阶段，基于节点特异性评分函数，对低维属性集合动态分配隐私预算。在相同隐私预算下，该算法相较于PrivBayes算法展现出更强的数据保护能力。实验结果表明，与传统基于贝叶斯网络的差分隐私方法相比，在相同隐私预算下，该算法在维持更高数据效用的同时，更能满足高维数据的隐私保护需求。

该文发表于《Future Internet》，围绕高维数据发布中的差分隐私保护与数据效用平衡问题，提出了一种基于评分函数的改进型贝叶斯网络方法SA-PrivBayes。研究背景在于，随着数据驱动技术快速发展，包含个人信息、交易记录与行为数据的大规模高维数据被广泛收集、分析与发布，隐私泄露风险显著增加。传统匿名化方法如k-匿名（k-anonymity）、l-多样性（l-diversity）、t-接近性（t-closeness）以及（α, k）-匿名等，难以抵御背景知识攻击；差分隐私（Differential Privacy, DP）因具有严格数学保证而成为更有前景的隐私保护框架。然而，面向高维数据时，经典差分隐私方法面临两个突出难题：其一，属性维度增长会引发噪声放大，导致隐私保护与数据效用之间矛盾加剧；其二，现有方法缺乏对不同属性信息重要性的细粒度区分，特别是在基于贝叶斯网络的数据发布中，均匀分配隐私预算会造成关键属性保护不足、非关键属性噪声冗余，最终削弱合成数据质量与实用性。因此，开展一种兼顾网络结构质量、预算分配合理性与高维适应性的差分隐私发布方法具有明确必要性。

针对上述问题，研究人员设计了SA-PrivBayes算法，对传统PrivBayes框架进行了两方面关键改进。首先，在贝叶斯网络结构学习阶段，以平均互信息（Average Mutual Information, AMI）替代随机初始节点选择策略，使高相关属性优先进入网络，提升网络结构合理性；同时引入阈值筛选机制，在指数机制选择属性—父节点（Attribute-Parent, AP）对之前，先过滤低评分候选对，以降低噪声干扰下选入弱相关属性对的概率。其次，在条件分布扰动阶段，利用评分函数反映节点重要性，将属性节点划分为不同重要性簇，并按比例参数q动态分配隐私预算，使高隐私风险节点获得更强保护、低风险节点保留更多数据效用。研究结论表明，该方法在相同隐私预算条件下，相较PrivBayes、ELPrivBayes及ACDP-Tree等方法，能够获得更高质量的贝叶斯网络、更优的分类效用以及更低的二维边缘分布平均变差距离，从而在高维数据发布任务中实现更优的隐私—效用权衡。

从意义上看，该研究不仅针对高维差分隐私数据发布中的均匀预算分配缺陷提出了可操作的改进方案，而且通过引入评分函数驱动的动态预算调控机制，增强了贝叶斯网络模型对属性异质性的适配能力。论文同时指出，在无需单纯依赖压缩全局隐私预算ε的前提下，仅通过调节比例参数q即可增强隐私保护强度，这为面向不同场景的个性化隐私控制提供了新的方法路径。总体而言，该研究对高维敏感数据的隐私发布、合成数据生成以及差分隐私模型的工程部署均具有现实参考价值。

就主要技术方法而言，研究人员首先基于互信息函数构建相关矩阵（MIM），并计算各属性平均互信息（AMI），据此确定贝叶斯网络初始节点及节点加入顺序；其次，在结构学习中引入带拉普拉斯噪声（Laplace Noise）的阈值筛选机制与指数机制联合选择AP对，以减少低互信息候选项被错误选中的概率；再次，在参数学习中依据节点评分函数将属性划分为3个簇，并通过比例参数q实现动态隐私预算分配，再采用拉普拉斯机制扰动联合分布并推导条件分布；最后在Adult、BR2000与NLTCS三个公开高维离散数据集上，使用SVM分类准确率、二维边缘平均变差距离、互信息总和及配对t检验进行综合评估。

下面按照论文主体中的结果结构进行总结。

4.1. SA-PrivBayes Algorithm Bayesian Network Construction
本节提出SA-PrivBayes的结构学习算法。研究人员指出，传统GreedyBayes算法随机选择初始节点，可能选中与其他节点依赖关系较弱的属性，从而降低网络对原始分布的逼近能力。为此，该研究以平均互信息最高的属性作为初始节点，并按AMI降序决定节点进入网络的顺序。进一步地，针对指数机制在小隐私预算下容易选择低互信息AP对的问题，研究人员设置阈值λ，对低于排序阈位的候选属性对进行预过滤，然后仅在保留候选空间内使用指数机制完成选择。由此提高了网络结构的准确性与候选选择效率。算法1给出了完整过程，并明确了阈值筛选与指数机制的预算划分方式。

4.2. Differentially Private Conditional Distribution Generation in the SA-PrivBayes Algorithm
本节讨论如何在贝叶斯网络基础上生成满足差分隐私的条件分布。研究人员认为，若对所有节点均匀分配预算，则重要节点可能保护不足，非重要节点则可能因过量噪声而损失效用。因此，该算法在参数学习阶段不再采用统一预算，而是基于节点评分函数对低维属性集实施差异化扰动。

4.2.1. Dynamic Privacy Budget Allocation
本小节提出动态隐私预算分配策略。研究人员依据节点评分值将全部属性划分为3个簇：低重要性簇C₁、中等重要性簇C₂和高重要性簇C₃。在总预算ε固定情况下，使用比例参数q对不同簇分配预算，再在簇内平均分配给各属性节点。文中进一步说明，q既可跨数据集自适应地反映属性相关性、敏感属性分布和维度规模，也可在同一数据集内适配高、中、低不同隐私需求场景。该设计遵循“高隐私风险节点分配更小ε、从而添加更多噪声”的差分隐私原则，以实现按需保护。

4.2.2. Algorithm Implementation
本小节给出算法2。研究人员先计算属性节点与其父节点集合的联合分布，再依据评分函数得到该节点对应的隐私预算ε_i，并通过拉普拉斯机制加入噪声：高评分节点分配更小预算，从而获得更强保护。之后将负值截断为0并归一化，再由扰动联合分布推导条件分布，最终生成带噪条件概率集合P^*，作为后续合成数据生成的核心基础。

4.3. Privacy Security Analysis
本节证明算法满足差分隐私。研究人员给出定理1：若算法1满足ε₁-差分隐私，算法2满足ε₂-差分隐私，则SA-PrivBayes整体满足ε-差分隐私，其中ε = ε₁ + ε₂。证明过程分为三步：第一，阈值筛选子过程通过拉普拉斯机制满足ε_τ-差分隐私，AP对选择通过指数机制在d ? 1次调用下满足ε_exp-差分隐私，由顺序组合性质可得算法1满足ε₁-差分隐私；第二，算法2对不同属性子集独立加噪，根据并行组合性质满足ε₂-差分隐私；第三，由顺序组合性质得到总体隐私保证。这一部分为方法的形式化安全性提供了理论支撑。

4.4. Algorithm Time Complexity Analysis
本节分析算法复杂度。研究人员指出，主要开销集中于贝叶斯网络构建阶段，尤其是属性互信息计算与AP候选筛选。文中引用已有结果说明，利用互信息矩阵存储节点间互信息后，结构学习复杂度可降至O(nd²)，低于GreedyBayes的复杂度；同时，相比ELPrivBayes，SA-PrivBayes通过缩减指数机制候选空间进一步降低最优项选择成本，因此在大规模数据集上的理论时间效率更优。

5.1. Dataset Overview
实验采用Adult、BR2000和NLTCS三个公开高维数据集。Adult来源于1994年美国人口普查，BR2000来源于2000年巴西人口统计记录，NLTCS来源于美国长期护理调查。研究人员对所有数据集采用统一预处理流程，均作为离散分类数据处理，其中二元分类属性采用0-1编码，多分类无序属性采用独热编码（One-Hot Encoding），多分类有序属性采用标签编码（Label Encoding）。

5.2. Experimental Setup
本节说明实验平台、参数与评估方式。研究人员统一设置贝叶斯网络最大父节点数k = 2，评分函数采用互信息分数，按AMI降序使用贪婪搜索构建网络。总隐私预算ε按ε₁:ε₂ = 3:7划分，其中结构学习阶段又分为阈值筛选预算ε_τ = 0.3ε₁和指数机制预算ε_exp = 0.7ε₁。所有实验在每个ε下独立重复50次，并对ACDP-Tree进行公平参数对齐比较。该设置保证了不同算法比较的可重复性与一致性。

5.3. Computational Cost Evaluation
本节通过理论与实验评估算法计算代价。结果表明，随着k增加，PrivBayes在网络构建中的时间复杂度快速上升，而ELPrivBayes与SA-PrivBayes由于使用互信息矩阵，受k影响较小。进一步地，SA-PrivBayes因减少了指数机制候选空间，时间开销略低于ELPrivBayes。由此说明该方法在保持模型表达能力的同时，具备较好的计算可行性。

5.4. Bayesian Network Quality Evaluation
本节以贝叶斯网络中所有AP对贡献的互信息总和作为质量指标，对PrivBayes、ELPrivBayes和SA-PrivBayes进行比较。结果显示，随着隐私预算增加，三种算法的网络精度均提升，但SA-PrivBayes在各预算下总体优于另外两种方法。其原因在于：与ELPrivBayes相比，该方法限制指数机制优先从高互信息候选中选择；与PrivBayes相比，该方法通过AMI优先选择依赖更强的根节点，改善了网络结构。尤其在小隐私预算下，噪声影响较强，SA-PrivBayes能捕获更多互信息，优势更明显。文中还比较了不同阈值λ，最终认为λ = 2/3能够在网络精度与隐私保护之间取得更合理平衡。

5.5. Data Utility Evaluation
本节从分类准确率与平均变差距离两方面评价数据效用。研究人员将原始数据按0.8:0.2划分为训练集与测试集，由不同算法基于训练集生成同规模合成数据，并用合成数据训练SVM多分类器，再用原始测试集评估分类准确率；同时计算合成数据与原始训练数据在所有属性二维边缘分布上的平均变差距离。结果表明，随着隐私预算ε增大，各算法分类准确率普遍提高，平均变差距离普遍下降。对于SA-PrivBayes，当q = 1时，相当于均匀预算分配，此时分类准确率最高；随着q增加，重要节点预算减小、保护增强，分类准确率逐步下降，但隐私保护能力增强。文中指出，当q = 1.1时，算法在数据效用损失不大的情况下能明显提高安全性，是较优设置。进一步比较显示，在q = 1.1、λ = 2/3时，SA-PrivBayes在三个数据集上的分类准确率整体高于PrivBayes、ELPrivBayes和ACDP-Tree，同时具有更低的二维边缘平均变差距离，说明该方法在保持较高隐私强度的同时，更好地保留了原始数据统计结构。

5.6. Data Robustness Analysis
本节在BR2000数据集上，针对ε = 1、q = 1.1、λ = 2/3的参数组合，使用配对t检验评估算法稳健性。结果显示，SA-PrivBayes与PrivBayes比较时，平均分类准确率分别为81.10与78.82，差值为2.28，t(4) = 10.324，p = 0.0005；与ELPrivBayes比较时，平均准确率差值为1.60，t(4) = 8.317，p = 0.0009。两组比较均达到显著水平，表明SA-PrivBayes在该实验设定下对基线方法具有稳定且显著的数据效用优势。

综合讨论部分，论文的核心贡献在于同时改进了贝叶斯网络结构学习与隐私预算分配两个关键环节。结构学习方面，研究通过AMI排序与阈值预筛选降低了随机初始化和低质量候选选择带来的误差；参数学习方面，基于评分函数的动态预算分配缓解了统一预算无法反映属性重要性差异的问题。实验结果支持该设计在高维数据发布场景中获得更优的网络质量、更高的分类效用和更强的隐私保护。论文也明确指出其局限性：第一，面对超高维海量数据时，贝叶斯网络结构学习复杂度仍可能显著上升，动态预算分配效率也会下降；第二，阈值λ与比例常数q仍主要依赖经验设定，缺乏自适应优化机制，限制了跨异质数据集的泛化能力。由此，研究后续将朝向两条路径推进：一是结合降维与分治思想优化结构学习，以降低超高维场景中的计算复杂度；二是构建基于数据特征的自适应参数调节模型，以提升阈值和q的智能优化能力及算法通用性。

研究结论部分可译为：本文针对现有基于贝叶斯网络的差分隐私方法在参数学习过程中对所有属性节点采用统一隐私预算分配、从而导致数据效用欠佳且无法准确反映数据集质量的问题，提出了一种基于评分函数的隐私预算分配方法。该方法依据属性节点的重要性，即其评分函数值，动态分配隐私预算。为增强传统算法中的数据安全性，通常需要减小全局隐私预算；而在本方法中，仅通过增大比例常数q即可实现同等程度的安全增强。此外，在结构学习阶段，互信息函数的高敏感性常导致依据互信息分数选择属性—父节点对。为缓解这一问题，研究人员引入循环机制，对由指数机制选出的AP对互信息总和进行迭代排序；若选中低评分函数的AP对，则重新选择候选项，从而改善贝叶斯网络构建。最终，所提出算法在提升数据隐私性的同时改善了数据效用。与PrivBayes算法相比，在相同隐私预算下，该方法实现了更强的隐私保护和更高的数据效用；同时，与ACDP-Tree算法的比较实验也验证了其在医疗与一般高维数据场景中的优势。