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

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

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

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

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