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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(7):3405−3428 [doi: 10.13328/j.cnki.jos.007287] [CSTR: 32375.14.jos.007287] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
基于自适应剪枝的满足本地差分隐私的真值发现算法

张朋飞 1 , 朱伊波 1 , 程 祥 2,3 , 张治坤 4 , 刘西蒙 5 , 孙 笠 6 , 方贤进 1 , 张 吉 7

1
(安徽理工大学 计算机科学与工程学院, 安徽 淮南 232001)
2
(北京邮电大学 计算机学院 (国家示范性软件学院), 北京 100876)
(网络与交换技术国家重点实验室 (北京邮电大学), 北京 100876)
3
4
(浙江大学 计算机科学与技术学院, 浙江 杭州 310058)
5
(福州大学 计算机与大数据学院, 福建 福州 350108)
6
(华北电力大学 控制与计算机工程学院, 北京 102206)
7
(School of Mathematics, Physics and Computing, University of Southern Queensland, Toowoomba 4350, Australia)
通信作者: 方贤进, E-mail: xjfang@aust.edu.cn
摘 要: 为了对移动群智感知中工人上传的不同质量的感知数据做必要的聚合处理, 真值发现技术应运而生, 其是
为后续应用提供精确数据支持的基础. 为了应对可能的隐私泄露问题, 现有研究往往结合本地差分隐私技术来进
行保护, 然而这些研究往往忽略了感知数据中的异常值对本地差分隐私下真值发现精度的影响. 这些异常值往往
具有极大的取值范围, 导致注入数据中的噪音量较大. 而且在现实世界中, 工人出于对隐私泄露的担心, 移动群智
感知服务器无法在无隐私保护的情况下预先处理数据. 为解决以上问题, 提出基于自适应剪枝的满足本地差分隐
私的真值发现算法 NATURE. 该算法的核心思想是考虑数据中蕴含的噪音类型来自适应剪枝掉不需要的工人的所
有值或者某些任务值. 在 NATURE 中, 为便于剪枝, 在形式化约束优化问题的基础上, 设计基于优化问题的噪音感
知的权重和重要性估计方法; 为进行剪枝, 在证明最优剪枝问题是 NP-hard 的基础上, 设计具有多项式时间复杂度
的效用感知的自适应剪枝方法. 进一步从理论上分析 NATURE 的隐私、效用和复杂度. 在两个真实数据集和一个
合成数据集上的实验结果表明, 相较于对比算法, NATURE 在求得噪音“真值”的精度上至少提高 20%.
关键词: 移动群智感知; 真值发现; 隐私保护; 本地差分隐私; 自适应剪枝
中图法分类号: TP309

中文引用格式: 张朋飞, 朱伊波, 程祥, 张治坤, 刘西蒙, 孙笠, 方贤进, 张吉. 基于自适应剪枝的满足本地差分隐私的真值发现算
法. 软件学报, 2025, 36(7): 3405–3428. http://www.jos.org.cn/1000-9825/7287.htm
英文引用格式: Zhang PF, Zhu YB, Cheng X, Zhang ZK, Liu XM, Sun L, FAng XJ, Zhang J. Locally Differentially Private Truth
Discovery Algorithm via Adaptive Pruning. Ruan Jian Xue Bao/Journal of Software, 2025, 36(7): 3405–3428 (in Chinese). http://www.
jos.org.cn/1000-9825/7287.htm
Locally Differentially Private Truth Discovery Algorithm via Adaptive Pruning

1
1
1
6
5
4
2,3
ZHANG Peng-Fei , ZHU Yi-Bo , CHENG Xiang , ZHANG Zhi-Kun , LIU Xi-Meng , SUN Li , FANG Xian-Jin ,
ZHANG Ji 7
1
(School of Computer Science and Engineering, Anhui University of Science and Technology, Huainan 232001, China)
2
(School of Computer Science (National Pilot Software Engineering School), Beijing University of Posts and Telecommunications, Beijing
100876, China)

* 基金项目: 安徽理工大学高层次引进人才科研启动基金 (2023yjrc92); 国家自然科学基金面上项目 (62372051); 国家自然科学基金青年
项目 (62202164); 安徽省科技重大专项 (18030901025); 高校学科 (专业) 拔尖人才学术资助项目 (gxbjZD2021050)
收稿时间: 2023-11-29; 修改时间: 2024-04-11, 2024-08-07; 采用时间: 2024-08-30; jos 在线出版时间: 2025-01-16
CNKI 网络首发时间: 2025-01-17