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

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

度和非隐私下的通信复杂度完全一致, 并没有增加多余的通信开销.
(2) 计算复杂度
从算法概述可以看出, 算法新增的主要时间消耗在于调用 NWIE 和 UAP 上. 对于 NWIE 来说, 其迭代求解工
人权重、任务真值和任务重要性, 总的计算复杂度为 3O(MN).
对于 UAP, 根据第 3.3 节, 其计算开销为 O(M + N + M + N). 相对于非隐私的真值发现来说增加了 O(M +
2
2
2
N + MN + M + N). 不过, 实际中尤其发起者的招募预算限制, 工人或任务的数量往往较小, 同时由于数据的稀疏
2
性, 工人所做任务的总记录数较少. 此外可以发现算法的主要计算在服务端进行, 本文可以合理地假设服务器有足
够的计算能力, 而且也能利用分布式计算来进一步降低时间开销.

4.2 算法讨论
在 NATURE 中, 本文尽可能地提升了参与最终真值发现的数据的效用, 同时 NWIE 方法不仅可以估算工人
的质量, 还可以为最终的真值发现提供初始化, 从而提升噪音“真值”的精度和真值发现算法的效率, 具体实验结果
如第 5.4 节所示.
(1) LDP 下剪枝的合理性: 直观上来看, 剪枝后能使得留下的数据质量更高. 从引理 1 也可以看出当工人质量
尽量相等时总误差最小, 因此在 LDP 下剪枝掉低质量的数据, 从而降低整体数据中蕴含的误差, 提升 LDP 下得到
“真值”的精度.
(2) 剪枝顺序的确定: 本文先进行工人数据剪枝, 再进行任务剪枝, 其原因在于进行任务剪枝时候需要预先确
定工人数量. 虽然, 先进行任务剪枝也需要确定工人数量, 但显然如果某个工人本身属于低质量工人, 其对“真值”
精度的负面影响要大于某个任务的值. 因此必须先进行工人剪枝.

5 实验评估

5.1 数据集
本文采用两个公开可用的数据集: Population 和 Forecast [6,7] .
(1) Population 数据集: 简称为 Pop, 该数据集收集自 2 415 个网站内关于 1 148 个城市的人口统计信息, 以美国
人口局的数据作为“真值”. 由于本文关注在隐私和效用的权衡, 不失一般性, 本文随机选择 2 000 个网站关于 10 个
城市的统计数据, 共计 16 816 条数据.
(2) Forecast 数据集: 简称为 For, 该数据集收集自 3 353 个气象观测点关于华中某地区的天气数据, 以中央气
象台公布的数据为“真值”. 本文具体选择温度、湿度. 风速和风向这 4 个连续属性进行实验. 共计 12 427 条数据.
(3) 合成数据集: 简称为 Syn, 生成 1 000 个工人对 50 个任务的数据, 值的范围为 [1, 20], 设置真值为 10.5. 不
2 σ i 决定工人的质量, 本文定义 种类型的工人, 其方差分别为
失一般性, 对每个工人注入 N(10.5,σ ) 的噪音, 其中 4
i
1、5、10 和 50. 其比例分别为 20%、50%、20% 以及 10%.

5.2 评价标准与实验环境
为了充分评估所提算法和各个子方法的精度和收敛速度等, 本文采用 MAE Change、KL-Divergence 和目标函
数值 J 来进行评估.
本文采用通用的 MAE Change 来判断最终得到的噪音“真值”的效用, 如下所示:

N
N ∑
∑
∗′ ∗
x − x t − x − x t
t t
t=1 t=1
MAE Change = (42)
|T|
其中, |T| 是任务数, x ∗′ 是第 t 个任务的隐私保护后的真值, x 是非隐私保护下得到的真值, x t 是第 t 个任务真值的
∗
t
t
标准值. MAE Change 表示隐私保护前后 MAE (mean absolute error) 的变化量, 其值越小表示隐私保护对效用的影
响越小.