论文部分内容阅读
差分隐私(Differential Privacy, DP)是一种新型的隐私保护模型,而直方图是差分隐私保护下数据发布的一种重要形式。在差分隐私直方图发布方法中,传统方法是采用数据转换或数据压缩技术,对原始直方图进行重新构造,同时通过添加适量噪音,对直方图桶的真实频数进行扰动,从而达到隐私保护的目的。在这一过程中,如何平衡重构误差和噪音误差是研究的关键。研究者们针对该问题提出很多重构策略来平衡重构误差和噪音误差,然而,现存的方法都没有考虑原始直方图桶的频数中存在对重构误差产生影响的离群点问题。本文主要针对上述问题对离群点进行研究,分析离群点和交替分布度对直方图重构结果的影响,并根据分析结果提出差分隐私保护下携带离群点的直方图发布方法。本文主要内容如下:(1)系统地定义离群点和交替分布度的概念,并详细分析离群点和交替分布度对重构误差的影响。(2)针对离群点导致重构误差增大的问题,提出降低交替分布度算法(Decreasing the Alternative Distribution Degree Algorithm,De-ADD)。该算法采用比较注入噪声的相邻桶频数大小的思想,对原始直方图桶的频数序列进行满足差分隐私要求的近似排序预处理,达到减小交替分布度的目的,从而减小离群点对直方图重构结果的影响。(3)提出一种基于合并桶策略的新的直方图重构算法Merge-Bins。该算法首先采用贪心的思想对直方图进行重构,每次通过指数机制选择直方图中频数最相似的两个相邻桶进行合并,重复上述过程,直到误差最小。最后,向直方图每个桶的频数中添加拉普拉斯噪声来满足差分隐私要求。(4)采用真实数据集进行对比实验。首先,根据本文提出的De-ADD算法对原始直方图结构进行预处理。然后,将未进行预处理和进行预处理的直方图通过现有的重构方法进行重构并将实验结果进行对比,以验证De-ADD算法的有效性。最后,将De-ADD算法与Merge-Bins算法组成的差分隐私保护下携带离群点的直方图发布方法(Histograms with Outliers Publishing Method under Differential Privacy, Outlier-HistoPub)与现存的差分隐私直方图发布方法进行对比实验,以验证Outlier-HistoPub方法的准确性和有效性。