滿足LDP的多維數(shù)據(jù)聯(lián)合分布估計①

褚雪君, 龍士工, 劉 海

1(貴州大學 計算機科學與技術(shù)學院, 貴陽 550025)

2(貴州大學 貴州省公共大數(shù)據(jù)重點實驗室, 貴陽 550025)

1 引言

隨著移動互聯(lián)網(wǎng)與大數(shù)據(jù)的發(fā)展, 數(shù)據(jù)規(guī)模也以前所未有的速度不斷增長, 數(shù)據(jù)屬性之間的相互關(guān)系變得復雜多樣, 多維數(shù)據(jù)已是一種常見的數(shù)據(jù)發(fā)布類型[1]. 在實際應(yīng)用中, 大量的多維數(shù)據(jù)被存儲在多個分布式組織中, 進行集成后, 這些多維數(shù)據(jù)將成為做出更好決策和提供高質(zhì)量服務(wù)的寶貴資源.由于數(shù)據(jù)挖掘和分析技術(shù)的提升, 發(fā)布多維數(shù)據(jù)會帶來很高的信息價值, 但多維數(shù)據(jù)中常包含許多隱私信息, 為了保護這些隱私信息在數(shù)據(jù)發(fā)布的過程中不被泄露, 通常會使用差分隱私保護技術(shù). 傳統(tǒng)的差分隱私技術(shù)將原始數(shù)據(jù)集中到一個中心服務(wù)器, 然后發(fā)布滿足差分隱私的信息, 通常稱其為中心化差分隱私保護(CDP). 因此中心化差分隱私技術(shù)始終基于一個可信的第三方數(shù)據(jù)收集者并保證不會竊取或泄露用戶的敏感信息的前提. 然而想要找到一個真正可信的第三方數(shù)據(jù)收集者是非常困難的. 鑒此, 在缺少可信的第三方數(shù)據(jù)收集者的情況下, 本地化差分隱私(LDP)[2–4]應(yīng)運而生, 目前已在業(yè)界得到應(yīng)用. 但多數(shù)的本地化差分隱私技術(shù)不適用于多維數(shù)據(jù), 若直接將其應(yīng)用于多維數(shù)據(jù)會造成通信開銷較大, 可用性差等問題.

目前, 本地化差分隱私技術(shù)已經(jīng)成為繼中心化差分隱私技術(shù)之后一種強健的隱私保護模型. 首先, 用戶對原始數(shù)據(jù)進行滿足 ε-本地化差分隱私的擾動, 然后將其傳輸給第三方數(shù)據(jù)收集者, 數(shù)據(jù)收集者收到擾動后的數(shù)據(jù)再進行一系列的查詢和求精處理, 以得到有效的統(tǒng)計結(jié)果. 對本地化差分隱私的研究和應(yīng)用, 主要考慮以下兩個方面問題: (1) 如何設(shè)計滿足ε -本地化差分隱私的擾動算法; (2) 數(shù)據(jù)收集者如何對收集到的數(shù)據(jù)集進行求精處理, 以提高統(tǒng)計結(jié)果的可用性. 本文中,求精處理即通過基本推理和機器學習的方法來捕捉收集到數(shù)據(jù)集的聯(lián)合概率分布[5–7]的過程.

為解決數(shù)據(jù)收集階段的隱私泄露, 本地化差分隱私保護通信開銷較大以及數(shù)據(jù)收集者求精處理的問題,本文提出了RR-LDP算法和LREMH算法, 主要工作如下:

(1) 提出了一個適用于多維數(shù)據(jù)的本地差分隱私保護算法(RR-LDP). 該算法相比直接將RAPPOR[8]應(yīng)用于多維數(shù)據(jù)上極大地降低了通信開銷.

(2) 結(jié)合期望最大化(EM)算法和LASSO回歸模型, 提出了一種高效的多維數(shù)據(jù)聯(lián)合分布估計混合算法(LREMH). 在真實數(shù)據(jù)集上進行性能評估, 實驗結(jié)果表明LREMH算法在精度和效率之間取得了平衡.

2 相關(guān)工作

Erlingsson等人[8]提出RAPPOR應(yīng)用隨機響應(yīng)技術(shù)和布隆過濾器來實現(xiàn)本地化差分隱私, 并應(yīng)用在谷歌瀏覽器上. 蘋果的差分隱私團隊提出使用one-hot編碼技術(shù)對敏感數(shù)據(jù)進行編碼, 并部署CMS算法分析Safari中最流行的表情符號和媒體播放偏好. 文獻[9]通過結(jié)合LDP與集中式數(shù)據(jù)模式, 提出具有高可用性的混合模型BLENDER. 文獻[10]針對移動設(shè)備收集隱私數(shù)據(jù)問題, 構(gòu)建了Harmony系統(tǒng), 該系統(tǒng)支持滿足LDP的統(tǒng)計分析與機器學習功能. 隨機響應(yīng)技術(shù)及其變體在收集分布式用戶統(tǒng)計數(shù)據(jù)的安全性方面具有優(yōu)勢, 已成為LDP研究的熱點. 但目前多數(shù)的LDP機制并不適用于多維且多值的數(shù)據(jù).

Giulia等人[11]提出基于EM的學習算法從噪聲樣本空間中估計聯(lián)合概率分布. 然而它們的方案適用于二維數(shù)據(jù), 當維數(shù)較高時, 數(shù)據(jù)的稀疏性會導致很大的效用損失, EM算法的復雜度也會呈指數(shù)級上升. Ren等人[12]打破了文獻[11] EM算法的局限, 將其拓展用于處理多維數(shù)據(jù). Li等人[13]提出使用Copula函數(shù)來模擬多維數(shù)據(jù)的聯(lián)合分布, 但Copula函數(shù)不能處理小域的屬性. Cormode等人[14]將Hadamard變換應(yīng)用于發(fā)布本地邊緣表, 其優(yōu)勢是節(jié)省了通信開銷, 但只適用于二進制數(shù)據(jù). Zhang等人[15]借鑒PriView[16]的思想提出CLMA方法, 該方法可以在不計算滿邊際的情況下釋放任意方向的邊緣表, 并且可以處理非二進制屬性.然而, 除了隱私保護帶來的噪聲誤差外還引入了采樣誤差.

3 基礎(chǔ)知識

3.1 本地化差分隱私(LDP)

定義1. ε - 本 地化差分隱私. 對于一個有N條記錄的數(shù)據(jù)集D, 給定隨機算法Q滿足ε -本地化差分隱私保護,Range(Q) 為隨機算法Q的取值范圍, 那么算法Q在任意兩條記錄X1和X2(X1,X2∈D)上得到相同的輸出結(jié)果X*的概率滿足:

其中, 概率P[·]表 示隱私泄露風險, ε表示隱私預算, 代表了隱私保護水平, 其值越小表示不可區(qū)分性越大, 隱私保護等級越高.

性質(zhì)1. 序列組合性[17]. 給定數(shù)據(jù)集D和n個隱私算法{Q1,···,Qn} 且算法Qi(1≤i≤n) 滿足εi-本地化差分隱私, 那么{Q1,···,Qn}在D上 的序列組合滿足ε -本地化差分隱私, 其中,

3.2 隨機響應(yīng)技術(shù)

隨機響應(yīng)技術(shù)(randomized response) 是本地化差分隱私保護的主流擾動機制, 旨在調(diào)查過程中使用隨機化裝置, 使被調(diào)查者以一個預定的概率p進行誠實的回答, ( 1-p)的概率隨意進行回答. 除被調(diào)查者以外的任何人均不知道被調(diào)查者的回答是否真實, 最后根據(jù)概率論的知識計算出敏感問題特征在人群中的真實分布情況的一種調(diào)查方法. 假設(shè)對n個用戶的問答進行統(tǒng)計, 得到患病人數(shù)的統(tǒng)計值. 其中真實患病的比例記為π, 假定回答“Yes”的人數(shù)為n1, 回答“No”的人數(shù)記為n2.根據(jù)誠實回答的概率θ 可得:

為了得到無偏估計, 可以采用極大似然的方法進行估計:

則患病的人數(shù)可估計為:

4 滿足LDP的多維數(shù)據(jù)聯(lián)合概率分布估計

4.1 設(shè)計思路

首先, 根據(jù)屬性域的大小和每個取值在屬性域中的位置將所有變量映射為位串, 得到的位串代表了唯一的原始記錄. 然后, 通過隨機響應(yīng)技術(shù)進行第一次擾動, 得到的結(jié)果稱作永久隨機響應(yīng), 并將其保存在用戶本地, 在第三方數(shù)據(jù)收集者請求數(shù)據(jù)時, 對永久隨機響應(yīng)的結(jié)果再做一次擾動, 得到的結(jié)果稱作瞬時隨機響應(yīng), 將瞬時隨機響應(yīng)的結(jié)果發(fā)送給第三方數(shù)據(jù)收集者.最后, 數(shù)據(jù)收集者聚合收集到的得到隨機噪聲樣本空間, 利用機器學習技術(shù), 可以從中估計聯(lián)合概率分布,進行求精處理.

本文所使用的相關(guān)符號定義如表1所示.

4.2 本地差分隱私保護

在本文的本地化差分隱私保護機制設(shè)計如算法1所示, 其中包含3個關(guān)鍵的步驟.

算法1. RR-LDP算法xij,j=1,2,···,d Aj f|?j|輸入: 用戶數(shù)據(jù)記{ }, 屬性集 , 隨機翻轉(zhuǎn)概率, 位串長度Ti輸出: 隨機翻轉(zhuǎn)后的位串1≤j≤d 1. for xij |?j| sij 2. 根據(jù)取值將 映射為一個長為 的位串f sij ?sij 3. 根據(jù) 隨機翻轉(zhuǎn) 中的每一位, 得到擾動后的位串4. end for ?sij Tij 5. 對 進行瞬時隨機擾動, 得到∑dj=1|?j| Ti 6. 將翻轉(zhuǎn)后的每個位串連接起來得到一個 位的向量 并返回

上述過程為永久隨機響應(yīng). 永久隨機響應(yīng)可以保證用戶端相互通信時的隱私安全問題, 抵御縱向攻擊.由于每條記錄中所有屬性的取值是獨立的, 故所得到的二進制位串可唯一代表一條記錄.

由于服務(wù)器每次請求數(shù)據(jù)時都要做一次瞬時隨機響應(yīng), 所以服務(wù)此每次請求相同的數(shù)據(jù)得到的結(jié)果都是不同的, 此時就可以保證服務(wù)器不能通過多次請求數(shù)據(jù)進行推斷攻擊.

在本文的RR-LDP方案采用一元編碼的方式進行二進制轉(zhuǎn)換, 相比于RAPPOR[8]所使用布隆過濾器進行二進制轉(zhuǎn)化的方法, 本文映射后的位串長度更小且由于布隆過濾器使用哈希函數(shù)進行映射會出現(xiàn)哈希沖突造成映射后的位串沖突, 而RR-LDP則不會.

4.3 隱私分析

定理1. 在用戶端進行的永久隨機響應(yīng)過程滿足ε1-本地化差分隱私, 其隱私保護等級為:

證明: 令S表示用戶初始的位串,S′表示經(jīng)過本地隨機翻轉(zhuǎn)的位串.S1和S2分別代表兩個不同用戶的記錄, 令它們的條件概率比值記作RR,RR=P(S′=S*|S=S1)/P(S′=S*|S=S2), 它與隱私保護等級ε1相關(guān). 由式(6)可以得到位串的每一位翻轉(zhuǎn)的概率為f/2, 不翻轉(zhuǎn)的概率為1 -f/2, 由文獻[8]可得到RRmax=((2-f)/f)2,此時的隱私保護等級 ε1=2ln((2-f)/f) , 其中f為隨機翻轉(zhuǎn)概率. 根據(jù)差分隱私序列組合性質(zhì)[17],d維數(shù)據(jù)記錄的本地翻轉(zhuǎn)滿足 ε1- 本地化差分隱私, 其ε1=2dln((2-f)/f) , 其中d為原始數(shù)據(jù)集D中屬性的個數(shù).

定理2. 在用戶端進行的瞬時隨機響應(yīng)過程滿足ε2-本地化差分隱私, 其隱私保護等級為:

證明過程與定理1類似, 詳見文獻[8]. 因為相同的轉(zhuǎn)換是由所有用戶獨立完成的, 所以上述本地化差分隱私保護適用于所有分布式用戶.

4.4 基于期望最大化算法(EM)的聯(lián)合分布估計算法

EM算法是在存在缺失或不完整數(shù)據(jù)的情況下獲得最大似然估計的常用方法. 它特別適合于RAPPOR[8]這種只收集它們的噪聲表示且真實值未知的應(yīng)用中.文獻[12]中的EM算法主要分為以下3步:

P(ω1ω2···ωk)=1/(∏kj=1|?d|)

第1步: 初始化, , 設(shè)置均勻分布分布作為初始的先驗概率;

EM算法具有較高的精度, 但對初始值比較敏感,當初始值選擇合適時, 上述方法能達到較好的收斂效果. 然而文獻[12]將聯(lián)合分布初始化為均勻分布, 顯然不是最優(yōu)的, 當屬性個數(shù)k增大時, 由于?1×?2×···×?k中所有組合的樣本空間爆發(fā)性增長, 算法的復雜度也會急劇上升, 阻礙良好的收斂. 同時多維數(shù)據(jù)呈現(xiàn)出的稀疏性也會帶來較大的誤差, 從而導致最終的估計達不到所需的效用.

4.5 基于LASSO回歸的聯(lián)合分布估計算法

LASSO回歸最早由Tibshirani于1996年提出[18],文獻[8]將它和最小二乘法用于收到噪聲樣本后的解碼工作. 如第4.1節(jié)所述, 位串是原始記錄的唯一代表. 隨機翻轉(zhuǎn)后, 本地用戶會產(chǎn)生大量不同程度的噪聲樣本. 此時,可以利用Mβ來估計噪聲樣本空間的聯(lián)合分布, 其中M是預測變量,是響應(yīng)變量, β是回歸系數(shù)向量, 這里的目的是估計M上的分布, 而不是原來的域. 響應(yīng)變量→y可以根據(jù)已知的隨機翻轉(zhuǎn)概率f, 從位串中估計出來. 因此, 唯一的問題就是求出一個準確的回歸系數(shù) β.基于LASSO回歸的聯(lián)合分布估計主要包含以下幾步:

4.6 LREMH算法

基于EM的算法在樣本足夠的情況下, 可以表現(xiàn)出良好的收斂性, 但也會產(chǎn)生很高的復雜度. 其高復雜度是因為它迭代掃描用戶的數(shù)據(jù), 并構(gòu)建一個先驗分布表, 其大小為然而, 在多維情況下, ?j的組合是非常稀疏的, 且有很多零項. 同時, 由于EM對初始值的選擇敏感, 均勻分配的初始值會導致收斂速度較慢. 然而基于LASSO回歸的聯(lián)合分布估計方法可以有效地解決由于多維數(shù)據(jù)的稀疏性導致的過擬合和效率慢的問題, 但與基于EM的算法相比, 精度略有下降.

為了在精度和效率之間取得平衡, 本文提出了LREMH算法, 該算法首先用基于LASSO回歸的方法估計初始值, 這樣得到的初始值會比均勻分布的初始值更加精確, 同時對基于EM算法的收斂性有積極的改進作用, 然后根據(jù)LASSO回歸模型計算出冗余候選項, 并消除他們, 從而提高計算效率, 最后使用EM算法進行迭代計算得到一個較為準確的估計值.

算法2. LREMH算法Aj|?j|f CTi輸入: , , , 索引集 ,P0(ω1ω2···ωk)輸出:j∈C 1. for each do···|?j|2. for each b=1, 2, , do ?yj[b]=∑Ni=1Tij[b]3. 計算yj[b]=[?yj[b]-N(p+0.5fq-0.5fp)]/(1-f)(q-p)4. 計算5. end for 6. end for→y=[y1[1],···,y1[|?1|]|···|yk[1],···,yk[|?k|]]7. 令M=[(?1)×(?2)×···(?k)]8. 令→β=Lasso(M,→y)9. 計算 /*使用回歸分析計算初始值*/P0(ω1ω2···ωk)=→β/N 10. 返回C′={x|x∈C,P0(x)=0}11. 令i=1,···,N 12. for each do j=1,···,k 13. for each do···|?j|14. for each b=1, , do Tij[b]=1 15. if P(Tij|ωj)=∏|?j|b=1q*images/BZ_236_1717_1856_1722_1881.pngimages/BZ_236_1717_1866_1722_1891.pngimages/BZ_236_1717_1876_1722_1901.pngimages/BZ_236_1717_1887_1722_1912.pngimages/BZ_236_1717_1897_1722_1922.pngTij[b]·ωj[b]images/BZ_236_1857_1856_1862_1881.pngimages/BZ_236_1857_1866_1862_1891.pngimages/BZ_236_1857_1876_1862_1901.pngimages/BZ_236_1857_1887_1862_1912.pngimages/BZ_236_1857_1897_1862_1922.pngp*images/BZ_236_1897_1856_1902_1881.pngimages/BZ_236_1897_1866_1902_1891.pngimages/BZ_236_1897_1876_1902_1901.pngimages/BZ_236_1897_1887_1902_1912.pngimages/BZ_236_1897_1897_1902_1922.pngTij[b]-ωj[b]images/BZ_236_2040_1856_2046_1881.pngimages/BZ_236_2040_1866_2046_1891.pngimages/BZ_236_2040_1876_2046_1901.pngimages/BZ_236_2040_1887_2046_1912.pngimages/BZ_236_2040_1897_2046_1922.png16. 計算17. else P(Tij|ωj)=∏|?j|b=1(1-q*)images/BZ_236_1772_1980_1778_2005.pngimages/BZ_236_1772_1991_1778_2016.pngimages/BZ_236_1772_2001_1778_2026.pngimages/BZ_236_1772_2012_1778_2036.pngimages/BZ_236_1772_2022_1778_2047.pngTij[b]-ωj[b]images/BZ_236_1915_1980_1921_2005.pngimages/BZ_236_1915_1991_1921_2016.pngimages/BZ_236_1915_2001_1921_2026.pngimages/BZ_236_1915_2012_1921_2036.pngimages/BZ_236_1915_2022_1921_2047.png(1-p*)images/BZ_236_2011_1980_2017_2005.pngimages/BZ_236_2011_1991_2017_2016.pngimages/BZ_236_2011_2001_2017_2026.pngimages/BZ_236_2011_2012_2017_2036.pngimages/BZ_236_2011_2022_2017_2047.pngTij[b]-ωj[b]images/BZ_236_2154_1980_2160_2005.pngimages/BZ_236_2154_1991_2160_2016.pngimages/BZ_236_2154_2001_2160_2026.pngimages/BZ_236_2154_2012_2160_2036.pngimages/BZ_236_2154_2022_2160_2047.png18. 計算19. end if 20. end for 21. end for ω1ω2···ωk∈C′22. if P(Ti1···Tik|ω1···ωk)=0 23.24. else P(Ti1···Tik|ω1···ωk)=Πj∈CP(Tij|ωj)25. 計算26. end if 27. end for 28. 初始化 t=0 /*迭代次數(shù)*/29. repeat i=1,···,N 30. for each do ωc∈(?1)×(?2)×···(?k)31. for each do Pt(ωc|TiC)=Pt(ωc)·P(TiC|ωc)/ΣωCPt(ωc)·P(TiC|ωc)32.33. end for 34. end for Pt+1(ωc)=∑Ni=1Pt(ωc|TiC)/N 35. 令36. 更新t=t+1 maxPt(ω1ω2···ωk)-maxPt-1(ω1ω2···ωk)≥δ 37. 直到P(Ac)=Pt(ωc)38. 返回

本文提出的LREMH算法主要包含以下3個步驟:

第1步: 計算初始值, 根據(jù)永久隨機響應(yīng)翻轉(zhuǎn)概率f和瞬時隨機響應(yīng)的翻轉(zhuǎn)概率p和q, 使用基于LASSO回歸的聯(lián)合分布方法計算初始值(第1–10行).

第2步: 消除冗余項, 利用基于LASSO回歸的聯(lián)合分布估計方法得到聯(lián)合分布為0的屬性并消除他們(第11, 22–23行).

第3步: 更新迭代, 根據(jù)永久隨機響應(yīng)翻轉(zhuǎn)概率f和瞬時隨機響應(yīng)的翻轉(zhuǎn)概率p和q, 使用基于EM的聯(lián)合分布估計算法通過組合每個屬性來計算得到一個特定的位串組合的所有條件分布, 通過貝葉斯定理計算它們對應(yīng)的后驗概率. 得到后驗概率后, 通過計算后驗概率的平均值來更新先驗概率. 在下一次迭代中利用更新后的先驗概率計算后驗概率. 使用上述方法進行迭代直至收斂(第12–37行).

上述LREMH算法具有兩個優(yōu)勢:

(1) 回歸分析能夠非常有效地選擇稀疏的候選項.因此, EM算法可以只計算這些稀疏候選項上的條件概率, 而不是所有候選項上的條件概率, 從而降低了時間和空間復雜度.

(2) EM算法對初值比較敏感, 尤其是在候選空間稀疏的情況下. 回歸分析可以對聯(lián)合分布產(chǎn)生較好的初始估計. 相對于均勻賦值的初值, 使用回歸分析生成的初值可以進一步加快EM算法的收斂速度.

4.7 滿足本地化差分隱私證明

證明. 在LREMH算法中, 所有的輸入數(shù)據(jù)的都是經(jīng)過RR-LDP算法處理后的數(shù)據(jù), 且LREMH算法的整個流程中沒有任何操作引入其他隱私保護和隨機擾動, RR-LDP算法的永久隨機響應(yīng)和瞬時隨機響應(yīng)根據(jù)定理1和定理2證得分別滿足 ε1-本地化差分隱私和ε2-本地化差分隱私, 根據(jù)本地化差分隱私的性質(zhì)1(序列組合性)可證得, LREMH算法滿足ε -本地化差分隱私, 其中ε =ε1+ε2.

5 實驗與分析

5.1 實驗環(huán)境

實驗中使用了兩個真實數(shù)據(jù)集, NLTCS和Adult.NLTCS數(shù)據(jù)集來自美國護理調(diào)查中心, 包含21 574名殘疾人不同時間段的活動. 成人數(shù)據(jù)集來自1994年美國人口普查, 包含45 222個居民的個人信息, 如性別、工資和教育水平. 在預處理中對一些連續(xù)域進行了離散化處理并刪除了一些缺省值.

實驗中所使用的軟硬件參數(shù)如下:

(1) 操作系統(tǒng): Windows 10;

(2) 硬件參數(shù): IntelCore i5, 2.0 GHz CPU, 4 GB;

(3) 編譯環(huán)境及工具: Python 2.7, PyCharm.

本文分別從數(shù)據(jù)集NLTCS和數(shù)據(jù)集Adult中采樣了20%的數(shù)據(jù)和10%的數(shù)據(jù). 算法的效率是通過計算估計時間和估計的精度來衡量的. 每組實驗運行10次, 并報告平均運行時間. 為了測量精度, 本文使用了兩個數(shù)據(jù)集上的平均變異距離(AVD)來量化估計的聯(lián)合分布P(ω) 和原始聯(lián)合分布Q(ω)之間的接近程度.

為了快速收斂, 將收斂間隙設(shè)置為0.001, 在瞬時響應(yīng)中通常取q=0.75,p=0.5.

5.2 安全性分析

根據(jù)第4.7節(jié)的結(jié)論, LREMH算法是滿足ε -本地化差分隱私, 又根據(jù)本地化差分隱私的兩個性質(zhì)得到ε=ε1+ε2=2dln((2-f)/f)+log[q*(1-p*)/p*(1-q*)],由于本次實驗的p和q是定值, 故ε 的大小只與d(數(shù)據(jù)記錄的數(shù)量)和f(永久隨機響應(yīng)的翻轉(zhuǎn)概率)有關(guān), 而兩個數(shù)據(jù)集的數(shù)據(jù)記錄數(shù)d也是確定的, 所以本次實驗的安全性只與f相關(guān). 從本地化差分隱私的定義可以看出ε 越小,eε就越小, 數(shù)據(jù)記錄之間的差距就越小, 就越難分辨, 安全性就越強, 反之則ε 的值越大, 安全性就越弱,本次實驗的f取(0, 1), 根據(jù)式(10)可以看出隨著f的增大ε 的值會減小, 安全性會增強.

5.3 估計效率對比

(1) NLTCS數(shù)據(jù)集: 如圖1, 對于任一維度k, LASSO回歸始終比EM算法和LREMH算法快, 尤其是當k較大時. 由于LASSO回歸的時間復雜度主要受用戶數(shù)量的影響, 所以當k增大時, LASSO回歸的計算時間增長緩慢, 而EM算法的計算時間增長較快是因為EM算法必須反復掃描每個用戶的位串, 同時, 固定的收斂精度會有更多的迭代從而導致EM算法的時間消耗隨著f的增加而增加. 相比之下, LASSO回歸可以更有效地估計聯(lián)合分布. 因為LASSO回歸的初始估計可以大大減少候選屬性空間和所需的迭代次數(shù), 所以LREMH算法的復雜度要比EM算法小.

圖1 NLTCS數(shù)據(jù)集估計效率對比

(2) Adult數(shù)據(jù)集: 如圖2, EM算法在低維k=2的情況下以可接受的復雜度運行. 當k=5時, EM算法的時間復雜度急劇增加了幾倍. 當k進一步增加時, 在120 s內(nèi)沒有返回任何結(jié)果. 然而, LASSO回歸只需要幾秒的時間.

圖2 Adult數(shù)據(jù)集估計效率對比

5.4 估計精度對比

(1) NLTCS數(shù)據(jù)集: 如圖3, 當f很小時, EM算法的AVD誤差很小, 但當f增大時, 它會急劇增大, 高達0.28. 相比之下, 即使f= 0.9, LASSO回歸的AVD誤差也保持在0.1左右. 當f較大時, LASSO回歸的AVD誤差與EM算法相當, 甚至更好. 這是因為LASSO回歸在從M和→y估計系數(shù)時對f不敏感. 由于EM算法掃描每條記錄的位串, 所以它對f很敏感, 并且容易得到某些局部最優(yōu)值. 相比之下, LREMH算法在LASSO回歸和EM算法之間實現(xiàn)了更好的權(quán)衡. 例如, 當f值較小時, 它的AVD誤差小于LASSO回歸; 當f值較大時, 它的AVD誤差優(yōu)于EM算法.

圖3 NLTCS數(shù)據(jù)集估計精度對比

(2) Adult數(shù)據(jù)集: 如圖4, 當k= 2時, LASSO回歸的AVD誤差幾乎不隨f變化, 因為回歸分析對f不敏感. 而EM算法的AVD誤差而隨f逐漸增大. 當f很大時, LASSO回歸的趨勢非常接近EM算法. 因為LREMH算法比EM算法運行的快得多且估計精度于EM算法相差不大, 所以它實現(xiàn)了精度和效率之間的平衡. 另外, 當k= 5時, 估計誤差也增大. 而LREMH算法可以在LASSO回歸和EM算法之間進一步平衡, 因為當k更大時, 候選集將會更稀疏, 而LREMH算法可以有效地減少候選集的冗余和迭代次數(shù).

根據(jù)圖1, 圖2可以看出LREMH算法的估計效率隨著屬性維度和f的增加而緩慢下降, 但始終處于EM算法和LASSO回歸算法兩者之間. 當f＞0.7時EM算法的效率急劇下降, 這是因為EM算法對f很敏感, 并且容易得到某些局部最優(yōu)值. 由于LREMH算法使用LASSO回歸快速的估計初始值, LREMH算法對f的敏感度要低于EM算法, 同時使用LASSO回歸估計的初始值要比直接使用均勻分布的初始值更加精確, 很好的解決的EM算法對初始值敏感的問題, 而且有效地減少了迭代的次數(shù), 這使得LREMH算法的估計效率一直比EM算法高. 根據(jù)圖中可以看出, LREMH算法的估計精度隨著屬性維度和f的增加而下降, 但也在大部分情況下處于EM算法和LASSO回歸算法兩者之間, 當屬性的維度增大時, 需要計算的候選集會變得更加稀疏, 所以EM算法的誤差會隨著維度和f的增加而增加, 由于LASSO回歸只進行一次回歸分析的估計, 并沒有像EM算法一樣進行迭代, 所以其估計的精度在大多數(shù)情況下不如EM算法, 但LREMH算法在估計初始值的同時會消除冗余候選項, 解決的初值估計問題, 減少了迭代次數(shù), 降低了得到局部最優(yōu)的概率,所以LREMH算法在效率和精度之間取得了均衡.

并且由于f的值直接影響了隱私保護等級, 當f增加時, 隱私保護的等級就越高, 也就導致了隨著f的增加, 3個算法估計的效率和精度都隨之下降, 從圖3和圖4中可以直觀看出當f＜0.7時, LREMH算法的估計效率和精度在LASSO回歸算法和EM算法中取得了良好的均衡.

圖4 Adult數(shù)據(jù)集估計精度對比

6 總結(jié)與展望

多維數(shù)據(jù)的聯(lián)合概率分布估計對于數(shù)據(jù)發(fā)布具有重要作用, 本文提出的LREMH算法在滿足本地化差分隱私的情況下, 結(jié)合期望最大化算法和回歸分析方法消除冗余候選項, 用回歸分析估計初始聯(lián)合分布, 然后用期望最大化算法進行迭代計算, 直至收斂. 通過實驗驗證LREMH算法在精度和效率之間取得了平衡.下一步工作將會圍繞如何學習到與原始數(shù)據(jù)最為擬合的概率圖模型, 如何進一步提高發(fā)布數(shù)據(jù)的可用性等方面的問題進行研究.