基于BIGRU的軌跡數(shù)據(jù)發(fā)布隱私保護方案

申艷梅,張玉陽,申自浩,王 輝,劉沛騫

(1.河南理工大學(xué) 軟件學(xué)院, 河南 焦作 454000;2.河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 河南 焦作 454000)

0 引 言

近年來,隨著通信技術(shù)和定位技術(shù)的發(fā)展,越來越多的設(shè)備具有位置數(shù)據(jù)搜集的能力?；谖恢梅?wù)(location-based services, LBS)[1]已經(jīng)廣泛應(yīng)用于各個領(lǐng)域,服務(wù)人民的生活。LBS技術(shù)可以分為兩類:單點LBS與連續(xù)LBS。其中,單點LBS是指用戶可以間斷地獲取位置信息,而連續(xù)LBS則需要用戶周期地獲取位置信息。盡管人們從LBS中獲益良多,但使用LBS時被搜集的數(shù)據(jù)可能包含個人隱私,若不經(jīng)處理直接進(jìn)行發(fā)布,很可能引起隱私的泄露[2]。

目前位置隱私保護技術(shù)中,K-匿名是常用的方法之一。基于K-匿名及其延伸技術(shù)實現(xiàn)了對數(shù)據(jù)的泛化處理,使得每個用戶的記錄與多條錯誤信息相匹配,攻擊者很難分辨出真正的用戶,從而保證個人的隱私。Gupta等[3]在考慮最小等待時間的情況下,將用戶的信息進(jìn)行保護,提出了最佳移動感知緩存數(shù)據(jù)預(yù)取和替換策略,引入匿名器,通過使用K-匿名預(yù)取設(shè)施,使得移動用戶輸入形成一個掩蔽區(qū)域,提高了隱私保護程度。朱素霞等[4]認(rèn)為位置會影響隱私預(yù)算與軌跡形狀,進(jìn)而影響數(shù)據(jù)的可用性,因此,利用相關(guān)熵和K-means技術(shù),既保證了軌跡數(shù)據(jù)的隱私性,又增強了軌跡數(shù)據(jù)可用性。

差分隱私技術(shù)[5]因其具有精確的數(shù)學(xué)表達(dá)方式和個性化的隱私保護而備受關(guān)注。Guo等[6]為解決LBS中位置隱私的暴露問題,設(shè)計了一種構(gòu)造匿名集的最佳輔助用戶選擇,并將差分隱私應(yīng)用于匿名集的構(gòu)建過程,添加自適應(yīng)拉普拉斯噪聲以滿足用戶的隱私要求,從而有效地保護了用戶的隱私。田豐等[7]為滿足不同用戶的隱私保護需求,給出了一種基于個性化差分隱私的軌跡發(fā)布機制,提高數(shù)據(jù)可用性,更好地兼顧隱私和數(shù)據(jù)的可用性。

隨著機器學(xué)習(xí)相關(guān)技術(shù)的發(fā)展,現(xiàn)如今越來越多的學(xué)者嘗試將深度學(xué)習(xí)技術(shù)與差分隱私結(jié)合。晏燕等[8]提出基于深度學(xué)習(xí)的位置大數(shù)據(jù)劃分結(jié)構(gòu)預(yù)測方法和差分隱私發(fā)布方法。該方法構(gòu)建基于時空序列的深度學(xué)習(xí)預(yù)測模型,通過提取歷史位置大數(shù)據(jù)統(tǒng)計劃分結(jié)構(gòu)矩陣的時間和空間相關(guān)特性,實現(xiàn)對劃分結(jié)構(gòu)矩陣的有效預(yù)測,從而解決傳統(tǒng)位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布結(jié)構(gòu)不合理、劃分發(fā)布方法效率低下的問題。Chen等[9]提出新的軌跡發(fā)布算法RNN-DP,將循環(huán)神經(jīng)網(wǎng)絡(luò)與差分隱私技術(shù)相結(jié)合應(yīng)用于軌跡發(fā)布,提高了數(shù)據(jù)可用性。

針對循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network,RNN)無法處理長距離數(shù)據(jù)以及大多數(shù)隱私保護方案無法抵御背景知識攻擊的問題,本文利用差分隱私(differential privacy,DP)與循環(huán)神經(jīng)網(wǎng)絡(luò)技術(shù),提出一種面向軌跡數(shù)據(jù)發(fā)布的雙向門控循環(huán)神經(jīng)網(wǎng)絡(luò)差分隱私(bidirectional gated recurrent unit-differential privacy,BIGRU-DP)保護方案,以達(dá)到在抵御背景知識攻擊的同時提高數(shù)據(jù)的可用性的目的。該方案能夠更好地對長距離軌跡數(shù)據(jù)進(jìn)行處理,降低梯度爆炸與梯度消失造成的影響,更好地適應(yīng)不同類型的軌跡數(shù)據(jù)。

1 相關(guān)定義

定義1ε-DP[10]。給定隨機算法M:D→Rn以及任意相鄰數(shù)據(jù)集D和D′,其輸入為一個數(shù)據(jù)集,輸出為n維實數(shù)向量。若隨機算法M對D和D′進(jìn)行操作,得到的任意輸出均使得結(jié)果S?Range(M),且滿足

Pr[M(D)∈S]≤eε×Pr[M(D′)∈S]

(1)

則稱算法M滿足ε-DP。其中,ε為隱私預(yù)算,ε越接近于0,則算法M作用于D和D′輸出的概率分布越相似,隱私保護效果越好。

定義2全局敏感度。設(shè)有查詢函數(shù)f:D→R,以及任意的鄰近數(shù)據(jù)集D和D′,函數(shù)f的敏感度定義為

Δf=maxD,D′‖f(D)-f(D′)‖1

(2)

差分隱私通過對數(shù)據(jù)加上噪聲的方式來保證對數(shù)據(jù)隱私的保護。其中,全局敏感度Δf是一個十分重要的參數(shù)。通過控制全局敏感度,從而控制添加噪聲的大小,實現(xiàn)滿足差分隱私的隱私保護。

定義3軌跡數(shù)據(jù)集。軌跡是若干位置點依據(jù)其時間戳組成的位置序列。其中,位置Pi=(xi,yi,ti)為地圖上離散點,xi和yi分別為位置點Pi的經(jīng)度和維度,ti為記錄該位置點的時間戳。軌跡可以表示為T=P1→P2→P3→…→Pn,其中,n為該軌跡的長度。由若干的軌跡組成的集合,稱為軌跡數(shù)據(jù)集,表示為D=(T1,T2,T3,…,Tq),q為該軌跡數(shù)據(jù)集中軌跡數(shù)量。

定義4Laplace機制[11]。給定數(shù)據(jù)集D和隱私預(yù)算ε,查詢函數(shù)q的全局敏感度為Δf,當(dāng)查詢函數(shù)q的輸出滿足

M(O)=q(O)+Lap(Δf/ε)

(3)

則稱算法M滿足ε-DP,且服從尺度參數(shù)為Δf/ε的Laplace分布。

拉普拉斯機制通過向查詢函數(shù)加入符合拉普拉斯分布的噪聲,使加噪后滿足差分隱私,從而保護用戶隱私。記位置參數(shù)μ為0,尺度參數(shù)為b。則所添加噪聲的概率密度函數(shù)為

(4)

定義5指數(shù)機制。給定輸入為數(shù)據(jù)集D以及輸出為實體對象r∈Range,有可用性函數(shù)u:(D,r)→R,若算法M滿足

(5)

則算法M滿足ε-DP。其中,Δu為效用函數(shù)u:(D,r)全局敏感度,可通過(6)式計算得到。效用函數(shù)值越高,r被選擇輸出的概率越大。

Δu=maxr∈,D～D′|u(D,r)-u(D′,r)|

(6)

性質(zhì)2并行組合原理。設(shè)有算法F1,F2,…,Fn,Fi(1<=i<=n)均滿足εi-DP,那么對于不相交的輸入數(shù)據(jù)集D1,D2,…,Dn,由這些算法構(gòu)成的組合算法F(F1(D1),F2(D2),…,Fn(Dn))滿足max(εi)-DP。

2 BIGRU-DP方案

2.1 系統(tǒng)架構(gòu)

BIGRU-DP方案系統(tǒng)架構(gòu)如圖1所示,包含軌跡預(yù)測,軌跡泛化,軌跡合并,軌跡發(fā)布4個部分。

圖1 系統(tǒng)架構(gòu)Fig.1 System architecture

該方案實現(xiàn)隱私保護進(jìn)行軌跡數(shù)據(jù)發(fā)布步驟如下。

步驟1軌跡預(yù)測模塊應(yīng)用BIGRU對軌跡進(jìn)行預(yù)測。與一般的神經(jīng)網(wǎng)絡(luò)不同,BIGRU不僅適用于處理時序數(shù)據(jù),相對于單向循環(huán)網(wǎng)絡(luò)能夠達(dá)到更精確的預(yù)測結(jié)果。

步驟2軌跡泛化模塊使用K-means對時間屬性進(jìn)行泛化處理,降低時空相關(guān)性對于數(shù)據(jù)泄露的影響。

步驟3軌跡合并模塊使用聚類技術(shù)與指數(shù)機制生成抽象軌跡數(shù)據(jù)集,并與原始軌跡進(jìn)行比較合并。

步驟4軌跡發(fā)布模塊采用異常處理機制刪除異常軌跡,并對需要發(fā)布的軌跡數(shù)據(jù)集進(jìn)行加噪處理,抵御背景知識攻擊。

2.2 軌跡預(yù)測

鑒于RNN的梯度爆炸和梯度消失的缺陷,循環(huán)神經(jīng)網(wǎng)絡(luò)的發(fā)展催生出了門控循環(huán)網(wǎng)絡(luò)(gated recurrent unit,GRU),它能有效地處理上述問題,并能捕獲長距離依賴。BIGRU改進(jìn)了GRU,其結(jié)構(gòu)包含正反2個GRU層。時間步t處的輸入提供正反雙向隱藏狀態(tài)信息來進(jìn)行參考。在訓(xùn)練模型的過程中提供正向逆向2個隱藏信息,其中,參數(shù)根據(jù)公式(7)—(9)進(jìn)行更新。

H′t=f(W1xt+W3H′t+b′t)

(7)

Ht=f(W2xt+W4Ht-1+bt)

(8)

Ht=H′t⊕Ht

(9)

使用BIGRU來進(jìn)行軌跡的預(yù)測,生成新的軌跡,從而達(dá)到隱藏原始軌跡的效果。在模型訓(xùn)練的過程中,BIGRU同時參考預(yù)測點兩側(cè)的數(shù)據(jù),因此,能夠獲得更加準(zhǔn)確的軌跡數(shù)據(jù)。算法1給出了軌跡預(yù)測生成的過程。

算法1BIGRU-DP_prediction

輸入:原始軌跡數(shù)據(jù)集D;

輸出:預(yù)測后的軌跡數(shù)據(jù)集DBIGRU。

1.forTinD;

2.for eachPinT;

3.xBIGRU=BIGRU(D,x);

4.yBIGRU=BIGRU(D,y);

5.end for;

6.end for;

7.TBIGRU=(XBIGRU_1,YBIGRU_1,t1)→(XBIGRU_2,YBIGRU_2,t2)→…→(XBIGRU_n,YBIGRU_n,tn);

8.DBIGRU=(TBIGRU_1,TBIGRU_2,TBIGRU_3,…,TBIGRU_n);

9.returnDBIGRU。

2.3 軌跡泛化

在得到DBIGRU軌跡數(shù)據(jù)集后,對其時間屬性進(jìn)行泛化處理,避免因軌跡的時空相關(guān)性帶來的隱私泄露。使用K-means聚類方法來實現(xiàn)所需的時間泛化。算法2描述了具體的泛化過程。

算法2BIGRU-DP_Generalization

輸入:預(yù)測后的軌跡數(shù)據(jù)集DBIGRU,位置點集X={X1,X2,X3,…,Xm};

輸出:泛化后的分區(qū)集Pset=(P1,P2,…,Pn)。

1.ifDBIGRU=? ;

2.return null;

3.end if;

4.初始化k個簇心μ1,…,μk;

5.repeat;

6.forjfrom 1 tom;

7.計算各位置點Xj與各聚類中心μi的距離;

8.將該位置點Xj劃進(jìn)與其最近的樣本中心μi所在的簇中;

9.end for;

10.forifrom 1 tok;

12.end for;

13.until所有的聚類中心不再變化;

14.記錄泛化后的分區(qū)集Pset=(P1,P2,…,Pn);

15.returnPset。

軌跡泛化如圖2所示。

圖2 軌跡泛化Fig.2 Trajectory generalization

2.4 軌跡合并

考慮到軌跡數(shù)據(jù)存在維數(shù)高,位置范圍較大的問題,本方案通過對每個時間戳內(nèi)的位置進(jìn)行空間劃分來解決。即通過使用K-means聚類將同一個時間戳內(nèi)的位置劃分為k組,k值越大,則每個位置將與其他軌跡上的較少位置進(jìn)行合并,從而軌跡精度損失越小。劃分后如圖3所示。

通過合并每個時間戳的位置點,軌跡也會被合并,因此軌跡的計數(shù)就會增加。通過這種方式,使得即使添加小噪聲也不會對數(shù)據(jù)可用性造成過大影響。

使用指數(shù)機制對在同一時間戳中的分區(qū)進(jìn)行選擇,并用候選分區(qū)的簇心代替該簇中的其他位置點。指數(shù)機制使用效用函數(shù)來對每一個候選分區(qū)進(jìn)行打分賦值,分?jǐn)?shù)較高的分區(qū)將會有更高的概率被輸出。根據(jù)文獻(xiàn)[14]中基于豪斯多夫距離設(shè)計的平均距離算法(mean distance,MeanDist),可以得到效用函數(shù)[13]為

(10)

(10)式中,

(11)

指數(shù)機制基于該效用函數(shù),則每一個分區(qū)Pi的輸出概率為

(12)

通過指數(shù)機制,能夠建立一個劃分區(qū)域內(nèi)部位置點與簇心的映射關(guān)系,從而達(dá)到泛化的效果。

圖3 空間劃分Fig.3 Space division

2.5 軌跡發(fā)布

s個時間段與m個候選分區(qū)會有ms種劃分策略。將所有的真實軌跡替換為泛化軌跡,從而保護用戶的隱私。

然而,使用新生成的泛化軌跡代替原始軌跡的同時,會產(chǎn)生一些不存在的異常軌跡。針對這些異常軌跡,設(shè)計異常處理機制,將原始軌跡與泛化后的軌跡作對比并計數(shù)相對應(yīng)的真實軌跡數(shù)(true count,TC),將tc=0的數(shù)據(jù)進(jìn)行刪除,不但減少了處理空軌跡的資源,同時增加了發(fā)布軌跡的有效性。

若直接將tc=1的軌跡進(jìn)行發(fā)布,很容易遭到背景知識攻擊。因此需要對其添加Laplace噪聲。選擇n條泛化軌跡,首先將具有原始軌跡的泛化軌跡納入選擇,將其數(shù)量記為n1,然后在剩余泛化軌跡中選擇n-n1條軌跡。

然而,為了保證隱私性而添加噪聲,將會導(dǎo)致犧牲部分的數(shù)據(jù)可用性。因此,根據(jù)文獻(xiàn)[14]本文設(shè)計了一種后處理機制以保證數(shù)據(jù)的可用性。具體處理工作為將添加噪聲前的軌跡集映射為圖G,將泛化后的軌跡作為圖G的邊,其交叉點作為節(jié)點,這種映射更加符合現(xiàn)實的軌跡網(wǎng)絡(luò)。為了降低添加噪聲對數(shù)據(jù)可用性的影響,規(guī)定對于任意的兩條邊x,y,若x的軌跡比y更多,則其tc(x)>tc(y)。令Cmean[i,j]表示S的一條子軌跡Sij的平均數(shù)。

(13)

則經(jīng)過約束性處理后的噪聲Lm可以表示為

Lm=minj∈[m,n]maxi∈[1,j]Cmean[i,j]

(14)

排序處理后的序列S為

S=

(15)

經(jīng)過處理后能提高數(shù)據(jù)的可用性。其處理過程如算法3所示。

算法3BIGRU-DP_release

輸入:合并優(yōu)化后的軌跡數(shù)據(jù)集Do,每條軌跡的真實計數(shù){tc1,tc2,…,tcN};

輸出:經(jīng)過合并與異常機制處理后的軌跡數(shù)據(jù)集Dr。

1.ifDo=?;

2.return null;

3.end if;

5.for allp,q∈[1,n1];

6.Δf=maxp,q{∣tcp-tcq∣};

7.μ=ComputeAverage(ε);

8.b=Δf/μ;

9.end for;

10.for alli∈[1,n1];

12.nci=tc′+noise(x);

13.end for;

14.NC={nc1,nc2,…,ncN};

16.S′=;

17.forifrom 1 ton1;

19.end for;

21.returnDr。

3 隱私安全證明

結(jié)合差分隱私應(yīng)用到方案的不同模塊以滿足隱私安全需求。在軌跡合并模塊,首先在每個時間戳的位置區(qū)域上執(zhí)行聚類,得到該時間戳的候選分區(qū)集,然后使用指數(shù)機制在候選分區(qū)集中選擇一個區(qū)域。在軌跡發(fā)布模塊中,為了提高隱私保護程度,對tc添加Laplace噪聲。為了便于描述,分別將其稱為軌跡合并(trajectory merging,TM)和軌跡發(fā)布(trajectory release,TR)。

定理1TM滿足ε-DP。

因此,只需將隨機算法M的輸出進(jìn)行歸一化處理,即可得到輸出候選分區(qū)ri的概率密度。歸一化處理為

(16)

根據(jù)差分隱私定義,在相鄰數(shù)據(jù)集中通過隨機化算法M得到相同的輸出值ri的比值為

(17)

將(16)式代入(17)式,進(jìn)行展開運算,則有

(18)

綜上,TM滿足ε-DP。

定理2TR滿足ε-DP。

證明對tc的集合TC={tc1,tc2,…,tcN},Δf為敏感度。

M(D)=f(D)+Y

(19)

(19)式中:f為查詢函數(shù);Y為Laplace噪聲;M(D)為加入噪聲后的混淆返回結(jié)果。

px(z)和py(z)分別為ML(x,f,ε)與ML(y,f,ε)的概率密度函數(shù)。因此,對于某個輸出z,有

(20)

對其進(jìn)行運算推導(dǎo)可以得出

(21)

綜上,TR滿足ε-DP。

定理3BIGRU-DP滿足ε-DP。

證明:由于TM與TR均為BIGRU-DP的子算法,且TM與TR都滿足ε-DP,假設(shè)TM滿足ε1-DP,TR滿足ε2-DP,因此,BIGRU-DP滿足ε-DP,其中,ε=ε1+ε2。

4 實驗評估

實驗仿真采用Pycharm開發(fā)平臺,以Python語言實現(xiàn)。實驗所使用的軌跡數(shù)據(jù)集為微軟的T-Drive軌跡數(shù)據(jù)集。將BIGRU-DP與RNN-DP[9],NGTMA[14]進(jìn)行比較以證明該方案在可用性和性能上的優(yōu)勢。

4.1 可用性評估

本文使用Hausdorff[15]距離作為軌跡數(shù)據(jù)可用性的度量指標(biāo)。Hausdorff距離能夠很好地計算兩組集合之間的相似度。假設(shè)有2組集合A={a1,a2,…,ap},B={b1,b2,…,bq}則這2個點集合之間的Hausdorff距離定義為

H(A,B)=max(h(A,B),h(B,A))

(22)

(22)式中,

h(A,B)=max(a∈A)min(b∈B)‖a-b‖

(23)

h(B,A)=max(b∈B)min(a∈A)‖b-a‖

(24)

(23)—(24)式中,‖·‖是點集A和B點集間的距離范式。Hausdorff距離越小,代表數(shù)據(jù)的可用性越高。

本文使用Hausdorff距離計算原始軌跡數(shù)據(jù)集與進(jìn)行軌跡發(fā)布算法處理后的軌跡數(shù)據(jù)集的相似性度量,并且記錄在分配不同的隱私預(yù)算ε的情況下使用Hausdorff距離軌跡相似度的變化情況。

圖4展示了隱私預(yù)算分別為0.1、0.2和0.5的情況下,隨著每組測試數(shù)據(jù)的增加,BIGRU-DP,RNN-DP和NGTMA三種方案中Hausdorff距離的變化和對比情況。

從圖4可以看出,根據(jù)分配不同的隱私預(yù)算ε實驗結(jié)果可以得知,當(dāng)實驗數(shù)據(jù)量大小固定時,隨著隱私預(yù)算ε的增大,不同算法的Hausdorff距離值均為下降趨勢,數(shù)據(jù)可用性增加。這是因為,根據(jù)差分隱私的性質(zhì),增加隱私預(yù)算ε會導(dǎo)致隱私保護度的下降,從而導(dǎo)致數(shù)據(jù)可用性的提高。

圖4 可用性分析對比Fig.4 Availability analysis and comparison

在分配相同的隱私預(yù)算的情況下,可以觀察到BIGRU-DP具有更好的數(shù)據(jù)可用性,這是因為在預(yù)測算法中,BIGRU在預(yù)測過程中引入了更多的信息,因此具有更高的數(shù)據(jù)可用性。

4.2 效率評估

觀察不同的隱私預(yù)算與每組測試數(shù)據(jù)的大小對于消耗時間的影響。圖5展示了隱私預(yù)算分別為0.1,0.2,0.5的情況下,隨著每組測試數(shù)據(jù)的增加,BIGRU-DP,RNN-DP和NGTMA三種方案中所需時間的變化情況。

圖5 性能效率對比Fig.5 Performance efficiency comparison

該實驗結(jié)果表明,在對時間資源使用的過程中,隱私預(yù)算對于時間的影響不大。隨著每一組實驗數(shù)據(jù)的增加,所用時間也會隨之增長。BIGRU-DP相較于其他2種方案具有時間優(yōu)勢。這是因為BIGRU-DP減少軌跡數(shù)據(jù)集的離群點,從而減少聚類時的迭代次數(shù),進(jìn)而減少了時間的消耗。

4.3 評估總結(jié)

本文主要貢獻(xiàn)如下。

1)考慮到軌跡數(shù)據(jù)的多樣性,利用GRU中門的特性,捕捉到軌跡數(shù)據(jù)中時間步距離較長的依賴關(guān)系,使該方案對于軌跡數(shù)據(jù)的處理更加具有普遍性。

2)為了提高軌跡發(fā)布數(shù)據(jù)的可用性,使用雙向循環(huán)網(wǎng)絡(luò),同時參考預(yù)測點兩側(cè)的數(shù)據(jù),使得到的軌跡更加準(zhǔn)確。

3)使用BIGRU對軌跡數(shù)據(jù)集進(jìn)行預(yù)處理,為k-means聚類減少了離群值,提升了效率。

4)采用微軟公司發(fā)布的T-Drive軌跡數(shù)據(jù)集進(jìn)行仿真實驗。仿真實驗結(jié)果表明,與同類方案相比,BIGRU-DP方案提高了軌跡數(shù)據(jù)可用性。同時與RNN-DP,NGTMA對比,實驗結(jié)果表明BIGRU-DP具有時間效率優(yōu)勢。

5 結(jié)束語

本文提出了一種面向軌跡數(shù)據(jù)發(fā)布的BIGRU保護方案,使用BIGRU進(jìn)行預(yù)測處理軌跡數(shù)據(jù)。由于BIGRU的雙向性,BIGRU-DP對于軌跡數(shù)據(jù)具有更好的處理效果,從而增加了軌跡數(shù)據(jù)的可用性。同時在預(yù)測過程中能夠處理離群值,使得BIGRU-DP在執(zhí)行效率上優(yōu)于RNN-DP與NGTMA,并且能夠在不同樣本數(shù)量下保持穩(wěn)定。BIGRU能夠利用過去和未來的數(shù)據(jù)來估計當(dāng)前值,因此,其更加適合對一些靜態(tài)軌跡數(shù)據(jù)進(jìn)行處理。對于動態(tài)軌跡數(shù)據(jù),該方案只能根據(jù)過去的數(shù)據(jù)進(jìn)行處理,因此精度將會下降。如何在保證數(shù)據(jù)可用性的同時,提高數(shù)據(jù)的處理效率,選擇與更好的聚類技術(shù)結(jié)合將會是下一步工作的重點。