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

褚雪君, 龍士工, 劉 海

1(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 貴陽(yáng) 550025)

2(貴州大學(xué) 貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室, 貴陽(yáng) 550025)

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

3 基礎(chǔ)知識(shí)

3.1 本地化差分隱私(LDP)

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

其中, 概率P[·]表 示隱私泄露風(fēng)險(xiǎn), ε表示隱私預(yù)算, 代表了隱私保護(hù)水平, 其值越小表示不可區(qū)分性越大, 隱私保護(hù)等級(jí)越高.

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

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

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

為了得到無(wú)偏估計(jì), 可以采用極大似然的方法進(jìn)行估計(jì):

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

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

4.1 設(shè)計(jì)思路

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

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

4.2 本地差分隱私保護(hù)

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

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

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

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

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

4.3 隱私分析

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

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

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

證明過(guò)程與定理1類似, 詳見(jiàn)文獻(xiàn)[8]. 因?yàn)橄嗤霓D(zhuǎn)換是由所有用戶獨(dú)立完成的, 所以上述本地化差分隱私保護(hù)適用于所有分布式用戶.

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

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

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

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

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

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

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

4.6 LREMH算法

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

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

算法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. 計(jì)算yj[b]=[?yj[b]-N(p+0.5fq-0.5fp)]/(1-f)(q-p)4. 計(jì)算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. 計(jì)算 /*使用回歸分析計(jì)算初始值*/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. 計(jì)算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. 計(jì)算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. 計(jì)算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個(gè)步驟:

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)環(huán)境

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

實(shí)驗(yàn)中所使用的軟硬件參數(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ù). 算法的效率是通過(guò)計(jì)算估計(jì)時(shí)間和估計(jì)的精度來(lái)衡量的. 每組實(shí)驗(yàn)運(yùn)行10次, 并報(bào)告平均運(yùn)行時(shí)間. 為了測(cè)量精度, 本文使用了兩個(gè)數(shù)據(jù)集上的平均變異距離(AVD)來(lái)量化估計(jì)的聯(lián)合分布P(ω) 和原始聯(lián)合分布Q(ω)之間的接近程度.

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

5.2 安全性分析

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

5.3 估計(jì)效率對(duì)比

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

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

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

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

5.4 估計(jì)精度對(duì)比

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

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

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

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

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

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

6 總結(jié)與展望

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