| 引用本文: | 张朋飞,朱伊波,程祥,张治坤,刘西蒙,孙笠,方贤进,张吉.基于自适应剪枝的满足本地差分隐私的真值发现算法.软件学报,2025,36(7):3405-3428 |
| |
|
| |
|
|
| 本文已被：浏览 1036次 下载 2042次 |
码上扫一扫！ |
|
|
| 基于自适应剪枝的满足本地差分隐私的真值发现算法 |
|
张朋飞1, 朱伊波1, 程祥2,3, 张治坤4, 刘西蒙5, 孙笠6, 方贤进1, 张吉7
|
|
1.安徽理工大学 计算机科学与工程学院, 安徽 淮南 232001;2.北京邮电大学 计算机学院(国家示范性软件学院), 北京 100876;3.网络与交换技术国家重点实验室(北京邮电大学), 北京 100876;4.浙江大学 计算机科学与技术学院, 浙江 杭州 310058;5.福州大学 计算机与大数据学院, 福建 福州 350108;6.华北电力大学 控制与计算机工程学院, 北京 102206;7.School of Mathematics, Physics and Computing, University of Southern Queensland, Toowoomba 4350, Australia
|
|
| 摘要: |
| 为了对移动群智感知中工人上传的不同质量的感知数据做必要的聚合处理, 真值发现技术应运而生, 其是为后续应用提供精确数据支持的基础. 为了应对可能的隐私泄露问题, 现有研究往往结合本地差分隐私技术来进行保护, 然而这些研究往往忽略了感知数据中的异常值对本地差分隐私下真值发现精度的影响. 这些异常值往往具有极大的取值范围, 导致注入数据中的噪音量较大. 而且在现实世界中, 工人出于对隐私泄露的担心, 移动群智感知服务器无法在无隐私保护的情况下预先处理数据. 为解决以上问题, 提出基于自适应剪枝的满足本地差分隐私的真值发现算法NATURE. 该算法的核心思想是考虑数据中蕴含的噪音类型来自适应剪枝掉不需要的工人的所有值或者某些任务值. 在NATURE中, 为便于剪枝, 在形式化约束优化问题的基础上, 设计基于优化问题的噪音感知的权重和重要性估计方法; 为进行剪枝, 在证明最优剪枝问题是NP-hard的基础上, 设计具有多项式时间复杂度的效用感知的自适应剪枝方法. 进一步从理论上分析NATURE的隐私、效用和复杂度. 在两个真实数据集和一个合成数据集上的实验结果表明, 相较于对比算法, NATURE在求得噪音“真值”的精度上至少提高20%. |
| 关键词: 移动群智感知 真值发现 隐私保护 本地差分隐私 自适应剪枝 |
| DOI：10.13328/j.cnki.jos.007287 |
| 分类号:TP309 |
| 基金项目:安徽理工大学高层次引进人才科研启动基金(2023yjrc92); 国家自然科学基金面上项目(62372051); 国家自然科学基金青年项目(62202164); 安徽省科技重大专项(18030901025); 高校学科(专业)拔尖人才学术资助项目(gxbjZD2021050) |
|
| Locally Differentially Private Truth Discovery Algorithm via Adaptive Pruning |
|
ZHANG Peng-Fei1, ZHU Yi-Bo1, CHENG Xiang2,3, ZHANG Zhi-Kun4, LIU Xi-Meng5, SUN Li6, FANG Xian-Jin1, ZHANG Ji7
|
|
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;3.State Key Laboratory of Networking and Switching Technology (Beijing University of Posts and Telecommunications), Beijing 100876, China;4.College of Computer Science and Technology, Zhejiang University, Hangzhou 310058, China;5.College of Computer and Data Science, Fuzhou University, Fuzhou 350108, China;6.School of Control and Computer Engineering, North China Electric Power University, Beijing 102206, China;7.School of Mathematics, Physics and Computing, University of Southern Queensland, Toowoomba 4350, Australia
|
| Abstract: |
| To conduct necessary aggregation on varying-quality sensed data uploaded by workers in mobile crowdsensing, truth discovery technology has emerged as the cornerstone for providing precise data support for subsequent applications. Existing studies tend to adopt local differential privacy for protection against potential privacy breaches, but often ignore the influence of outliers in the sensed data on the truth discovery accuracy under local differential privacy. These outliers often have a large range of values, resulting in a large amount of noise in the injected data. Additionally, due to workers’ concerns about privacy breaches, mobile crowdsensing servers cannot preprocess data without privacy protection. To this end, this study proposes NATURE, which meets local differential privacy based on adaptive pruning. The core idea of the algorithm is to consider the noise types in the data to adaptively prune all unnecessary workers’ values or certain task values. In NATURE, the noise-aware weight and importance estimation (NWIE) method based on a formalized constraint optimization problem is designed to facilitate data pruning. Based on proving the optimal pruning problem is NP-hard, this study designs the utility-aware adaptive pruning (UAP) method with polynomial time complexity to conduct pruning. Furthermore, a theoretical analysis of NATURE’s privacy, utility, and complexity is carried out. Experimental results on two real-world datasets and one synthetic dataset demonstrate that NATURE achieves an accuracy improvement of at least 20% in obtaining “truth” compared to its comparative algorithms. |
| Key words: mobile crowdsensing (MCS) truth discovery privacy protection local differential privacy adaptive pruning |
|
|
|
|
