差分隱私直方圖發(fā)布方法的研究.pdf

1、差分隱私(Differential Privacy，DP)是一種新型的隱私保護模型，而直方圖是差分隱私保護下數(shù)據(jù)發(fā)布的一種重要形式。在差分隱私直方圖發(fā)布方法中，傳統(tǒng)方法是采用數(shù)據(jù)轉(zhuǎn)換或數(shù)據(jù)壓縮技術，對原始直方圖進行重新構造，同時通過添加適量噪音，對直方圖桶的真實頻數(shù)進行擾動，從而達到隱私保護的目的。在這一過程中，如何平衡重構誤差和噪音誤差是研究的關鍵。研究者們針對該問題提出很多重構策略來平衡重構誤差和噪音誤差，然而，現(xiàn)存的方法都沒有考慮

2、原始直方圖桶的頻數(shù)中存在對重構誤差產(chǎn)生影響的離群點問題。
　　本文主要針對上述問題對離群點進行研究，分析離群點和交替分布度對直方圖重構結果的影響，并根據(jù)分析結果提出差分隱私保護下攜帶離群點的直方圖發(fā)布方法。本文主要內(nèi)容如下:
　　(1)系統(tǒng)地定義離群點和交替分布度的概念，并詳細分析離群點和交替分布度對重構誤差的影響。
　　(2)針對離群點導致重構誤差增大的問題，提出降低交替分布度算法(Decreasing theAlt

3、ernative Distribution Degree Algorithm，De-ADD)。該算法采用比較注入噪聲的相鄰桶頻數(shù)大小的思想，對原始直方圖桶的頻數(shù)序列進行滿足差分隱私要求的近似排序預處理，達到減小交替分布度的目的，從而減小離群點對直方圖重構結果的影響。
　　(3)提出一種基于合并桶策略的新的直方圖重構算法Merge-Bins。該算法首先采用貪心的思想對直方圖進行重構，每次通過指數(shù)機制選擇直方圖中頻數(shù)最相似的兩個相鄰桶

4、進行合并，重復上述過程，直到誤差最小。最后，向直方圖每個桶的頻數(shù)中添加拉普拉斯噪聲來滿足差分隱私要求。
　　(4)采用真實數(shù)據(jù)集進行對比實驗。首先，根據(jù)本文提出的De-ADD算法對原始直方圖結構進行預處理。然后，將未進行預處理和進行預處理的直方圖通過現(xiàn)有的重構方法進行重構并將實驗結果進行對比，以驗證De-ADD算法的有效性。最后，將De-ADD算法與Merge-Bins算法組成的差分隱私保護下攜帶離群點的直方圖發(fā)布方法(Histo