论文部分内容阅读
直方图是数字数据分布的精确图形表示,广泛用于数据发布、数据挖掘和分析。然而,如果我们直接使用原始数据来发布直方图,这似乎存在隐私漏洞。差分隐私(DP)作为一种数学定义,是在数据库中发布汇总数据统计查询的理想解决方案,能够抵御任意背景知识的攻击者并提供了强大的隐私保护保障。本文研究了基于差分隐私的精确直方图发布算法。本文的主要目的是通过确保发布算法满足差分隐私的同时,提高发布直方图的精度。本文首先分析了V-优化直方图变体算法——噪声优先算法(NoiseFirst)和结构优先算法(StructureFirst)。然后通过复原算法并实验,对其进行了深入研究,并指出了这些算法中存在的问题和不足。为了解决这些问题,本文提出了如下优化及解决方法。其次,本文提出了一种优化结构下的算法(Optimization Structure Algorithm,OSA)。该算法首先通过近似最优的解决方案将隐私预算分成两部分,然后执行迭代的动态规划(Dynamic Programming)算法来获得最优的分组结构,因此新生成的直方图拥有最小的分组误差。然后,通过使用优化的指数机制来保护最优结构的隐私,并计算每个分组的均值。最后,为每个分组的均值添加拉普拉斯噪声并发布最优的直方图。在真实的数据集上,OSA与现有的算法Boost进行实验比对,通过实验结果表明,OSA超越了Boost算法,并达到了更好的效用。再次,本文设计了一种新的直方图发布机制(Optimal Mechanism,OM),可以在满足差分隐私的同时发布更准确的直方图。首先,本文采用随机快速排序算法(Randomized quicksort Algorithm,RA)对注入拉普拉斯噪声的直方图进行排序,以便降低误差。RA法能够有效抵抗已知排序算法并利用特定数据进行恶意攻击的敌手。这也是本文使用该算法的原因。此外,在分组问题上,本文提出并设计了基于动态规划思想的最小误差权重的解决方案(Dynamic Programming based on Error Weights,DPEW),以进一步提高所发布的直方图的准确性。最后,本文使用两个真实数据集提供详细的实验评估分析,其数据范围从数千到数百万条记录不等。这些数据集来自互联网上的各种领域(例如,巴西的IPUMS人口普查,希拉里克林顿和唐纳德特朗普的推文)。本文的结果给出了算法实验数据比对,并证实了本论文设计实现的机制优于其他同类方法,验证了算法将产生更小的误差,并大大提高了直方图上范围查询的准确性。