Page 486 - 《软件学报》2025年第7期

张朋飞 等: 基于自适应剪枝的满足本地差分隐私的真值发现算法 3407

较高的迭代次数. 现有研究表明, 即便对这些质量很低的数据赋予消极的权重, 也会对最终结果产生较大的负面
影响 [14,17−21] .
现有满足 LDP 的真值发现方法 [22−27] 忽略了数据中的异常值对本地差分隐私下真值发现精度的影响, 这些异
常值往往具有极大的取值范围, 导致注入数据中的噪音量较大. 而且实际中工人出于对隐私泄露的担心, 移动群智
感知服务器无法在非隐私下预先处理. 一种直观方案是在满足 LDP 下采样一些需要的值或者剪枝掉不需要的值,
并根据加噪上传后的值进行真值发现. 然而, 采样比例越大注入的噪音就越大, 采样比例越小剩下数据中的信息量
就越小, 难以确定一个恰当的采样比例. 而且, 该采样比例的确定很容易受到异常值的干扰. 此外, 从剪枝掉的数据
量来说, 如果剪枝掉的数据量太少, 则无法起到剪枝的效果, 剪枝太多可能导致剩下数据的信息量不够; 从剪枝掉
的工人来说, 这些工人可能是高质量的工人, 这会降低留下数据的质量; 从剪枝掉的任务值来说, 随机剪枝可能导
致某些任务没有值. 这是因为某些任务可能被少量工人做过, 如果这些值都被剪枝掉, 那么就无法得到这些任务对
应的“真值”, 进而导致真值发现的失败.
为此, 本文从剪枝的角度, 提出一种基于自适应剪枝的满足 LDP 的真值发现算法 (locally differentially private
truth discovery via adaptive pruning, NATURE). 该算法的核心思想是考虑数据中蕴含的噪音类型效用感知地自适
应剪枝掉不需要的工人的所有值或者某些任务值, 然后利用剩下的噪音值进行真值发现. 具体地讲, 首先每个工人
采用 Laplace 机制对自身数据加噪并将加噪后数据上传到群智感知服务器, 其次为便于剪枝, 本文在形式化约束
优化问题的基础上求得工人的质量和任务的重要性以及每个任务的初步“真值”; 接着, 为进行剪枝, 本文将剪枝问
题形式化为另一个约束优化问题并证明该问题是 NP-hard 的, 且进一步根据工人的质量、任务的重要性以及算法
的总误差设计了具有多项式时间复杂度的、效用感知的自适应剪枝方法; 最后, 根据剪枝后的噪音数据和任务的
初步“真值”进行非隐私的真值发现以得到每个任务的最终噪音“真值”.
综上, 本文的主要贡献如下.
(1) 基于剪枝思想, 本文提出一种针对异常值的满足 LDP 的真值发现算法 NATURE, 并从理论上分析了算法
的隐私、效用和复杂度. 理论分析表明 NATURE 不仅严格满足 LDP, 而且还能得到高精度的噪音“真值”, 同时相
对于非隐私的真值发现算法来说, 没有增加多余的通信开销, 计算开销也增加较少.
(2) 为便于剪枝, 本文考虑上传数据中蕴含的噪音类型, 形式化了约束优化问题, 并基于拉格朗日乘子法来求
解得到工人的质量和任务的重要性以及任务的初始“真值”.
(3) 为进行剪枝, 本文将剪枝问题形式化为另一个约束优化问题并证明该问题是 NP-hard 的, 进而基于工人的
质量和任务的重要性设计了具有多项式时间复杂度的、效用感知的自适应剪枝算法.
(4) 本文在两个真实的数据集和一个合成数据集上验证了 NATURE 的效用和效率. 相较于对比算法, NATURE
在求得噪音“真值”的精度上至少提高 20%.

1 相关工作

本文相关工作主要落在本地差分隐私 (LDP) 中的数据投毒与防御, 基于密码学的真值发现和满足 LDP 的真
值发现.

1.1 LDP 中的数据投毒与防御
Cao 等人 [28] 和 Cheu 等人 [29] 指出 LDP 协议对数据操纵较为敏感, 攻击者通过注入精心制作的虚假数据以使
得 LDP 协议错误估计项目的频率或者均值, 此种攻击被称为“数据投毒攻击 (data poisoning attack, DPA)”. Li 等人 [30]
为了平衡群智感知系统中的安全风险与隐私威胁, 提出一种新的基于伪装的 DPA 方法, 来欺骗满足差分隐私的真
值发现协议.
为防御 DPA, Zhang 等人 [31] 提出了一种多轮次的针对真值发现的攻击和防御方法. Song 等人 [32] 提出了两种
可验证的 LDP 协议, 优化了现有使用零知识证明协议存在计算和通信成本高的问题. Huang 等人 [33] 针对频率估计
等数据分析任务提出了通用的 LDP 投毒防御机制. 在此基础上, Zheng 等人 [34] 针对较低隐私预算下基于 LDP 的