基于深度學(xué)習(xí)的位置大數(shù)據(jù)統(tǒng)計發(fā)布與隱私保護方法

晏燕，叢一鳴，Adnan Mahmood，盛權(quán)政

（1.蘭州理工大學(xué)計算機與通信學(xué)院，甘肅 蘭州 730050；2.麥考瑞大學(xué)科學(xué)與工程學(xué)院，新南威爾士 2109）

0 引言

車聯(lián)網(wǎng)、智能交通系統(tǒng)、移動眾包、基于位置的服務(wù)（LBS,location-based service）系統(tǒng)、社交網(wǎng)絡(luò)等熱門應(yīng)用的廣泛興起促使包含位置信息的數(shù)據(jù)與日激增，其規(guī)模和復(fù)雜性已經(jīng)達到大數(shù)據(jù)的層次。位置大數(shù)據(jù)的統(tǒng)計發(fā)布可以為用戶提供準(zhǔn)確及時的交通和路況信息，幫助人們規(guī)劃合理的出行時間和路線，獲得高精度的LBS，同時有助于減少交通擁堵和不必要的資源浪費[1-2]。但是，對位置信息的不當(dāng)發(fā)布和反向分析推理容易導(dǎo)致用戶具體位置、運動軌跡、生活習(xí)慣、健康狀況、興趣愛好、經(jīng)濟條件等個人隱私的泄露，甚至可能危及用戶財產(chǎn)和生命安全[3-5]。因此，解決位置大數(shù)據(jù)發(fā)布使用過程中的隱私保護問題，已經(jīng)成為制約位置大數(shù)據(jù)應(yīng)用發(fā)展最為迫切的任務(wù)。

按照一定時間間隔發(fā)布的位置大數(shù)據(jù)統(tǒng)計信息可供用戶查詢一定范圍之內(nèi)的其他用戶數(shù)量、可搭乘的交通工具數(shù)量、車流狀況等。這種位置大數(shù)據(jù)的統(tǒng)計劃分發(fā)布過程依據(jù)特定的索引結(jié)構(gòu)對二維空間進行劃分和索引，并對索引區(qū)域內(nèi)的位置點數(shù)量進行統(tǒng)計發(fā)布，減少了用戶真實位置信息的泄露風(fēng)險。通過對索引區(qū)域內(nèi)真實位置點的統(tǒng)計值添加差分隱私噪聲，還可以進一步提高發(fā)布位置統(tǒng)計數(shù)據(jù)的隱私保護效果。傳統(tǒng)的位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布方法主要采用自頂向下的空間劃分過程，構(gòu)建網(wǎng)格或樹型索引結(jié)構(gòu)，并對各子區(qū)域迭代執(zhí)行類似的劃分策略，容易發(fā)生“過劃分”或“欠劃分”現(xiàn)象。劃分結(jié)構(gòu)的不合理增大了差分隱私統(tǒng)計發(fā)布的噪聲誤差和均勻假設(shè)誤差，導(dǎo)致發(fā)布位置統(tǒng)計數(shù)據(jù)的查詢精度降低。此外，迭代劃分過程需要對位置信息集合進行多次掃描和劃分停止條件判斷，影響了數(shù)據(jù)發(fā)布方法的運行效率。

事實上，位置大數(shù)據(jù)的統(tǒng)計劃分發(fā)布符合典型的時空序列特征。雖然個體用戶的位置信息具有明顯的隨機性和動態(tài)變化特點，但是結(jié)合區(qū)域的統(tǒng)計結(jié)果來看，相鄰發(fā)布時間間隔的位置大數(shù)據(jù)統(tǒng)計信息具有高度相關(guān)性，位置點密集的統(tǒng)計區(qū)域也存在一定的空間分布模式[6-7]。例如，在交通高峰期間，城市中的某些地區(qū)總是會發(fā)生交通擁堵現(xiàn)象并持續(xù)一段時間。近年來，基于深度學(xué)習(xí)的時空序列預(yù)測方法已經(jīng)在交通流量和交通密度區(qū)域預(yù)測方面取得不少研究成果。因此，本文將深度學(xué)習(xí)引入位置大數(shù)據(jù)的發(fā)布過程，將歷史位置大數(shù)據(jù)轉(zhuǎn)換為深度學(xué)習(xí)模型可以分析和處理的劃分結(jié)構(gòu)時空序列，選用合理的深度學(xué)習(xí)模型挖掘和提取劃分結(jié)構(gòu)時空序列的特征，并實現(xiàn)位置大數(shù)據(jù)統(tǒng)計劃分結(jié)構(gòu)的有效預(yù)測。這對降低劃分過程的冗余操作、提高數(shù)據(jù)發(fā)布方法的運行效率具有現(xiàn)實意義。本文的主要貢獻如下。

1)提出二維空間位置大數(shù)據(jù)的網(wǎng)格劃分和自底向上合并吸收算法，使最初與位置點分布無關(guān)的均勻網(wǎng)格劃分結(jié)構(gòu)轉(zhuǎn)化為反映位置點分布密度的合理劃分結(jié)構(gòu)。

2)構(gòu)建時空序列深度學(xué)習(xí)預(yù)測模型，通過提取歷史位置大數(shù)據(jù)統(tǒng)計劃分結(jié)構(gòu)時空序列的潛在特征，實現(xiàn)對位置大數(shù)據(jù)統(tǒng)計劃分結(jié)構(gòu)的有效預(yù)測。

3)設(shè)計與預(yù)測劃分結(jié)構(gòu)相匹配的差分隱私預(yù)算分配和調(diào)整方案，并在不同數(shù)據(jù)規(guī)模的實際位置大數(shù)據(jù)集合上驗證了所提方法在發(fā)布數(shù)據(jù)可用性和運行效率方面的優(yōu)勢。

1 相關(guān)工作

Dwork 等[8-9]提出的差分隱私模型通過向發(fā)布數(shù)據(jù)的統(tǒng)計結(jié)果添加隨機噪聲來實現(xiàn)隱私保護。因為具備嚴(yán)格的數(shù)學(xué)特性，該模型被認為是一種非常可靠的保護機制，并在數(shù)據(jù)發(fā)布隱私保護領(lǐng)域獲得了廣泛的應(yīng)用。位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布的主要目標(biāo)是在保證用戶位置隱私安全的前提下，盡可能提供準(zhǔn)確且高效的位置統(tǒng)計發(fā)布數(shù)據(jù)。但是，差分隱私噪聲的添加和二維空間區(qū)域的均勻性假設(shè)問題，使位置大數(shù)據(jù)的統(tǒng)計劃分發(fā)布結(jié)果與真實統(tǒng)計值之間存在一定誤差。因此，二維空間劃分結(jié)構(gòu)的合理性是直接關(guān)系到位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布數(shù)據(jù)可用性的關(guān)鍵因素。

Qardaji 等[10]提出的均勻網(wǎng)格（UG,uniform grid）劃分方法將二維空間均勻分割成眾多網(wǎng)格，對網(wǎng)格區(qū)域內(nèi)的位置點數(shù)量進行統(tǒng)計和加噪實現(xiàn)差分隱私保護，劃分結(jié)構(gòu)簡單高效但是統(tǒng)計發(fā)布數(shù)據(jù)可用性不高。Xiong 等[11]使用等高線圖來描述空間眾包服務(wù)中的位置點分布，首先將全體空間區(qū)域劃分為大量不相交的單元，然后將密度值相近的單元連接起來形成更大的區(qū)域。Wang 等[12]在UG 劃分方法基礎(chǔ)上利用線性回歸方法得到網(wǎng)格劃分粒度的最優(yōu)解，采用基于桶排序的單元合并策略將所有相似網(wǎng)格進行合并，降低了統(tǒng)計發(fā)布結(jié)果中的噪聲誤差。文獻[10]提出的自適應(yīng)網(wǎng)格（AG,adaptive grid）劃分方法在均勻網(wǎng)格劃分的基礎(chǔ)上對每個區(qū)域執(zhí)行自適應(yīng)網(wǎng)格劃分，較好地反映了數(shù)據(jù)分布特性對劃分結(jié)構(gòu)的影響。張嘯劍等[13]提出基于伯努利隨機抽樣技術(shù)的三層自適應(yīng)網(wǎng)格劃分發(fā)布方法，利用指數(shù)機制和高通濾波技術(shù)在劃分結(jié)構(gòu)的第二層過濾掉小于閾值的網(wǎng)格單元，對于大于閾值的網(wǎng)格單元繼續(xù)進行劃分，而對于小于閾值且相鄰的網(wǎng)格單元則合并形成粗粒度的網(wǎng)格單元。Fanaeepour 等[14]利用歐拉特性和差分隱私來解決范圍查詢對空間區(qū)域數(shù)據(jù)的敏感性增加問題，使用用戶區(qū)域大小和最小絕對偏差的約束推理來校準(zhǔn)差分隱私保護的噪聲。Wei 等[15]提出的位置隱私保護方案使用三層自適應(yīng)網(wǎng)格劃分發(fā)布方法和基于差分隱私的自適應(yīng)完全金字塔網(wǎng)格算法，將移動眾包服務(wù)中的確切位置拆分成含噪聲的多級網(wǎng)格，從而實現(xiàn)位置隱私保護。Rodríguez 等[16]提出的空間分解算法借助粒子空間分布的統(tǒng)計信息提取最佳空間分解，使每個單元包括空間均勻分布的粒子。

樹型結(jié)構(gòu)具有更好的層次包含特性，可以提供更加便捷的空間范圍查詢服務(wù)。Cormode 等[17]使用與數(shù)據(jù)分布特性無關(guān)的完全四叉樹對二維空間進行劃分，并設(shè)計了幾何隱私預(yù)算分配方法和后置調(diào)整方法，在一定程度上提升了范圍計數(shù)查詢的精度。吳英杰等[18]在完全四叉樹劃分的基礎(chǔ)上根據(jù)設(shè)定的均勻性條件對劃分結(jié)果進行自底向上的調(diào)整合并，從而降低均勻假設(shè)誤差。Zhang 等[19]提出的PrivTree 劃分發(fā)布方法引入一個可控的偏差來決定是否進行四叉樹分割，消除了對預(yù)先定義四叉樹劃分深度的限制。Zhang 等[20]提出的PrivBayes 方法利用貝葉斯網(wǎng)絡(luò)構(gòu)建一組近似分布的低維子立方體，以發(fā)布合成數(shù)據(jù)集。針對空間眾包服務(wù)中的位置隱私問題，Yang 等[21]根據(jù)工作人員的最大密度差將整個工作區(qū)域劃分成4 個大小不同的子單元并遞歸調(diào)用這一過程，直至獲得合理的空間結(jié)構(gòu)。

一些劃分發(fā)布方法將網(wǎng)格結(jié)構(gòu)與樹型結(jié)構(gòu)有機結(jié)合，形成混合劃分結(jié)構(gòu)。Cormode 等[17]將依賴數(shù)據(jù)分布特性的kd 樹結(jié)構(gòu)和與數(shù)據(jù)分布無關(guān)的四叉樹劃分發(fā)布方法進行結(jié)合，有助于范圍計數(shù)查詢精度的進一步提升。文獻[22]將AG 劃分發(fā)布方法與kd樹結(jié)構(gòu)結(jié)合，將相鄰的近似網(wǎng)格進行合并，以防網(wǎng)格劃分過細而引入較多的噪聲誤差。Yan 等[23]提出的分層混合劃分發(fā)布方法首先根據(jù)位置點的密度進行自適應(yīng)網(wǎng)格劃分，然后根據(jù)設(shè)置的高密度閾值和低密度閾值將網(wǎng)格分成3 種類型，對大于高密度閾值的網(wǎng)格進行自適應(yīng)網(wǎng)格劃分，對小于低密度閾值的網(wǎng)格停止劃分，對處于2 種閾值之間的網(wǎng)格進行啟發(fā)式四叉樹劃分，有效地提高了發(fā)布數(shù)據(jù)的可用性。Cai 等[24]將UG 劃分發(fā)布方法和改進的H-tree劃分發(fā)布方法相結(jié)合。張嘯劍等[25]采用網(wǎng)格結(jié)構(gòu)對空間數(shù)據(jù)區(qū)域進行均勻劃分，通過四叉樹對網(wǎng)格單元進行索引，提高了范圍響應(yīng)查詢的精度。

針對傳統(tǒng)劃分發(fā)布方法難以確定空間分割停止條件、劃分結(jié)構(gòu)無法均衡噪聲誤差和均勻假設(shè)誤差、數(shù)據(jù)掃描和迭代分析復(fù)雜等問題，本文借助深度學(xué)習(xí)模型對劃分結(jié)構(gòu)矩陣組成的時空序列進行時空關(guān)聯(lián)分析，實現(xiàn)對位置大數(shù)據(jù)統(tǒng)計劃分結(jié)構(gòu)的有效預(yù)測和基于差分隱私保護的統(tǒng)計劃分發(fā)布。

2 差分隱私模型

差分隱私模型與位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布具有天然的匹配性。位置大數(shù)據(jù)的連續(xù)動態(tài)變化使添加/刪除某個位置點對整體位置數(shù)據(jù)分布特性的影響非常小，這一特質(zhì)與差分隱私定義的內(nèi)涵十分吻合。

定義1ε-差分隱私[8]。針對兄弟數(shù)據(jù)集T1和T2（T1與T2相比僅存在一條不同的記錄）以及任意輸出S?Range(K)，如果算法K在T1和T2上得到相同輸出結(jié)果的概率滿足

則稱算法K滿足ε-差分隱私。

式(1)中的ε稱為隱私預(yù)算，其數(shù)值越小，算法K提供的隱私保護程度越高。因為攻擊者即便獲得了除特定目標(biāo)記錄之外的其他所有數(shù)據(jù)，依然無法根據(jù)查詢結(jié)果推斷該目標(biāo)所對應(yīng)的記錄是否存在于原始數(shù)據(jù)集合中，從而實現(xiàn)了隱私保護。

定義2敏感度[26]。給定一個查詢映射函數(shù)f，其敏感度Δf定義為該查詢映射函數(shù)在兄弟數(shù)據(jù)集T1和T2上的輸出之間的最大L1 范數(shù)距離

定義3Laplace 機制[26]。針對數(shù)值型數(shù)據(jù)，Laplace 機制通過向查詢映射函數(shù)f的輸出結(jié)果添加少量的獨立噪聲來實現(xiàn)差分隱私保護。用f(T)表示查詢映射函數(shù)f作用于原始數(shù)據(jù)集T得到的結(jié)果，則 Laplace 機制返回的查詢結(jié)果可以表示為K(T)=f(T)+η。其中η是滿足Laplace 分布的連續(xù)型隨機變量，其概率密度函數(shù)為

結(jié)合敏感度定義，添加的獨立噪聲服從幅度為b=Δf/ε的零均值Laplace 分布。

定理1串行組合特性[27]。對于一組隨機算法{K1,K2,…,Kn}，其中Ki(1≤i≤n)滿足對數(shù)據(jù)集T的εi-差分隱私，則該組隨機算法{K1,K2,…,Kn}整體能夠?qū)崿F(xiàn)對數(shù)據(jù)集T的-差分隱私。

定理2并行組合特性[27]。如果數(shù)據(jù)集T可以劃分為多個獨立且互不相交的子集{T1,T2,…,Tn}，一組隨機算法{K1,K2,…,Kn}分別作用于上述數(shù)據(jù)子集，其中Ki(1≤i≤n)滿足對數(shù)據(jù)子集Ti的εi-差分隱私，則該組隨機算法{K1,K2,…,Kn}能夠?qū)崿F(xiàn)對數(shù)據(jù)集T的max{εi}-差分隱私。

3 基于深度學(xué)習(xí)的劃分發(fā)布結(jié)構(gòu)預(yù)測方法

為了將深度學(xué)習(xí)應(yīng)用于二維空間劃分結(jié)構(gòu)的預(yù)測，需要完成以下2 個關(guān)鍵步驟：首先是如何把二維空間分解問題轉(zhuǎn)化為深度學(xué)習(xí)模型可以理解和分析的數(shù)據(jù)；其次是如何構(gòu)造適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)并搭建合理的深度學(xué)習(xí)模型進行預(yù)測。

3.1 劃分結(jié)構(gòu)矩陣的形成

在實際應(yīng)用中，不少交通量統(tǒng)計和LBS 應(yīng)用系統(tǒng)都使用區(qū)域計數(shù)的方式發(fā)布位置大數(shù)據(jù)的統(tǒng)計信息。因此，本文首先根據(jù)位置大數(shù)據(jù)范圍計數(shù)查詢服務(wù)的最小尺度將位置信息覆蓋的二維空間進行均勻網(wǎng)格劃分，并統(tǒng)計每個網(wǎng)格區(qū)域內(nèi)的位置點數(shù)量作為該網(wǎng)格的密度。為了解決均勻網(wǎng)格劃分發(fā)布方法噪聲誤差和均勻假設(shè)誤差較大的問題，根據(jù)局部分布均勻則整體也分布均勻的常理，采用自底向上合并吸收的策略對相鄰的網(wǎng)格進行均勻性判斷和合并操作，使最初與位置點分布無關(guān)的均勻網(wǎng)格劃分結(jié)構(gòu)轉(zhuǎn)化為能夠反映位置點分布密度的合理劃分結(jié)構(gòu)。

定義4區(qū)域合并條件。對于一個包含有m個網(wǎng)格的二維空間區(qū)域R，設(shè)Ci為每個網(wǎng)格的密度(i=1,2,…,m)，為區(qū)域R內(nèi)的網(wǎng)格平均密度。若區(qū)域R中的統(tǒng)計值滿足

則區(qū)域R內(nèi)的所有網(wǎng)格可以合并為一個區(qū)域。

定義4 要求區(qū)域R內(nèi)的所有網(wǎng)格密度與整個區(qū)域的平均密度接近時才能進行網(wǎng)格合并操作，通過減小式(4)中的常數(shù)，可以進一步收緊網(wǎng)格區(qū)域合并的條件。

定義5劃分結(jié)構(gòu)矩陣。對于初始劃分結(jié)構(gòu)為N×N均勻網(wǎng)格的二維空間區(qū)域，可以構(gòu)建如式(5)所示的矩陣以表示該二維空間區(qū)域的最終劃分結(jié)構(gòu)，其中的每一個元素hij(i,j=1,2,…,N)代表對應(yīng)位置的網(wǎng)格區(qū)域所處的劃分層次。hij的初始值設(shè)定為h(N=2h)，每當(dāng)選定區(qū)域R內(nèi)的所有網(wǎng)格滿足合并條件時，對應(yīng)的hij減小1，表示選定區(qū)域R發(fā)生一次區(qū)域合并。

3.2 深度學(xué)習(xí)預(yù)測模型的構(gòu)建

深度學(xué)習(xí)可以在大量復(fù)雜的非結(jié)構(gòu)化數(shù)據(jù)中發(fā)現(xiàn)并自動提取隱藏在數(shù)據(jù)中的特征、類別、結(jié)構(gòu)、概率分布等有價值的信息。在時間序列預(yù)測方面，遞歸神經(jīng)網(wǎng)絡(luò)（RNN,recursive neural network）[28]、長短期記憶（LSTM,long short-term memory）網(wǎng)絡(luò)[29]、卷積神經(jīng)網(wǎng)絡(luò)（CNN,convolutional neural network）[30]等常用深度學(xué)習(xí)模型已經(jīng)取得廣泛的應(yīng)用。RNN 可能隨著時間的增大出現(xiàn)梯度消失或梯度爆炸的問題，并且其結(jié)構(gòu)依賴于激活函數(shù)和網(wǎng)絡(luò)參數(shù)。CNN可以有效地捕捉空間特性。LSTM 通過遺忘門決定丟棄或保留哪些信息，通過輸入門更新細胞狀態(tài)，因此在時間特征提取方面具有良好的效果。全連接長短期記憶（FC-LSTM,fully connected-LSTM）網(wǎng)絡(luò)[31]被證明在處理時間相關(guān)性方面具有強大的功能，但是在處理時空數(shù)據(jù)時，其“輸入-狀態(tài)”和“狀態(tài)-狀態(tài)”的轉(zhuǎn)換使用全連接，空間信息并沒有被編碼，所以在捕捉數(shù)據(jù)空間特性上的能力依然不足。

位置大數(shù)據(jù)的統(tǒng)計劃分發(fā)布數(shù)據(jù)是由數(shù)據(jù)快照按照時間順序串聯(lián)形成的序列，符合典型的時空序列特征。為了實現(xiàn)對下一時刻位置大數(shù)據(jù)劃分發(fā)布結(jié)構(gòu)的準(zhǔn)確預(yù)測，既要考慮時間上的相關(guān)性，又要考慮空間分布的相關(guān)性。卷積長短期記憶（ConvLSTM）模型[32]在“輸入-狀態(tài)”和“狀態(tài)-狀態(tài)”轉(zhuǎn)換過程中都具有卷積結(jié)構(gòu)，該模型的輸入是三維張量，在加入卷積操作之后不僅能夠得到時序關(guān)系，還能夠像卷積層一樣提取空間特征，非常適合時空序列的處理。圖1 為ConvLSTM 模型結(jié)構(gòu)。首先，通過遺忘門ft來決定要從細胞中丟棄的信息；然后，由輸入門it中的tanh 層創(chuàng)建一個備選狀態(tài)，并將其與輸入門it信息進行矩陣對應(yīng)元素相乘，上述兩部分的結(jié)果相加確定了更新后的細胞狀態(tài)Ct；最后，通過tanh處理的更新后的細胞狀態(tài)與sigmoid門的輸出進行矩陣對應(yīng)元素相乘，得到最終的輸出結(jié)果。式(6)～式(10)給出了ConvLSTM 的關(guān)鍵方程，其中，*表示卷積算子，?表示Hadamard 積。

圖1 ConvLSTM 模型結(jié)構(gòu)

時空長短期記憶（ST-LSTM）模型[33]在LSTM模型的基礎(chǔ)上加入了時空單元，可以把時間特征和空間特征保存到每個時刻的細胞狀態(tài)，從而獲得其時空關(guān)系。圖2 為ST-LSTM 模型結(jié)構(gòu)，輸入門it確定進入細胞的新序列，遺忘門ft選擇保留多少歷史序列信息于細胞中。當(dāng)前細胞輸入Xt經(jīng)過由權(quán)重矩陣和偏置形成的LSTM 結(jié)構(gòu)后輸出的結(jié)果，與上一層的時空門輸出結(jié)果STt-1相耦合，用于融合序列間的相互影響。每個序列的各個特征通過這種方式進行重構(gòu)，從而實現(xiàn)空間信息之間的依賴。式(11)和式(12)給出了ST-LSTM 模型的時空門STt和細胞狀態(tài)Ct的計算式。

圖2 ST-LSTM 模型結(jié)構(gòu)

本文分別以 LSTM、CNN、ConvLSTM、ST-LSTM 模型為核心，構(gòu)建位置大數(shù)據(jù)劃分結(jié)構(gòu)時空序列的深度學(xué)習(xí)預(yù)測模型。首先使用算法1 將歷史位置大數(shù)據(jù)集合轉(zhuǎn)換為劃分結(jié)構(gòu)矩陣；然后按照時間順序把劃分結(jié)構(gòu)矩陣組織成三維時空序列，并將其作為深度預(yù)測模型的輸入張量，實現(xiàn)劃分結(jié)構(gòu)矩陣的有效預(yù)測。4 種模型的具體參數(shù)如表1～表4所示。

表1 LSTM 預(yù)測模型參數(shù)

表2 CNN 預(yù)測模型參數(shù)

表3 ConvLSTM 預(yù)測模型參數(shù)

表4 ST-LSTM 預(yù)測模型參數(shù)

4 基于差分隱私的位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布

為了實現(xiàn)對位置大數(shù)據(jù)統(tǒng)計發(fā)布信息的隱私保護，需要結(jié)合空間劃分結(jié)構(gòu)進行差分隱私預(yù)算分配，并對各空間區(qū)域的統(tǒng)計結(jié)果添加擾動噪聲。差分隱私預(yù)算分配的相關(guān)研究[34-38]指出，隨著劃分層次的增加，自頂向下逐步增大各層的隱私預(yù)算有助于降低噪聲方差，提高統(tǒng)計發(fā)布位置信息的范圍計數(shù)查詢精度。因此，本文設(shè)計了差分隱私預(yù)算的梯度分配方法，并結(jié)合劃分結(jié)構(gòu)的不平衡特點進行隱私預(yù)算的調(diào)整，實現(xiàn)滿足ε-差分隱私的位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布。

定義6隱私預(yù)算梯度分配。假設(shè)差分隱私總預(yù)算為ε，對于深度為h的層次化空間劃分結(jié)構(gòu)，每一層分配的差分隱私預(yù)算為

其中，ai=i(i-1)/2(i=1,2,…,h+1)是一個公差逐漸增大的序列，ε1是分配給根節(jié)點（即整個位置數(shù)據(jù)集覆蓋的二維空間）的隱私預(yù)算值，εh+1是葉子節(jié)點（即初始網(wǎng)格劃分區(qū)域）的隱私預(yù)算值。

定義7隱私預(yù)算調(diào)整。在深度為h的層次化空間劃分結(jié)構(gòu)中，如果發(fā)生網(wǎng)格合并的區(qū)域處于劃分層次i，則按照式(14)調(diào)整該區(qū)域的差分隱私預(yù)算

以圖3 所示的自底向上合并吸收結(jié)構(gòu)為例，其中灰色節(jié)點表示未發(fā)生網(wǎng)格合并的區(qū)域，可以根據(jù)式(13)分配相應(yīng)的差分隱私預(yù)算；黑色節(jié)點表示發(fā)生了網(wǎng)格合并的區(qū)域，需要按照式(14)進行差分隱私預(yù)算調(diào)整。當(dāng)i=3 時，發(fā)生網(wǎng)格合并的區(qū)域隱私預(yù)算應(yīng)當(dāng)調(diào)整為；當(dāng)i=2 時，，從而保證任意從葉子節(jié)點到達根節(jié)點的路徑都滿足=ε。

圖3 差分隱私預(yù)算調(diào)整示意

算法2 給出了差分隱私位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布方法的具體過程。圖4 描述了本文基于深度學(xué)習(xí)的位置大數(shù)據(jù)統(tǒng)計發(fā)布與隱私保護方法的整體流程。

圖4 位置大數(shù)據(jù)深度學(xué)習(xí)預(yù)測和差分隱私統(tǒng)計劃分發(fā)布流程

推論1算法2 能夠為位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布結(jié)果提供ε-差分隱私保護。

證明位置大數(shù)據(jù)的統(tǒng)計劃分發(fā)布主要向用戶提供范圍計數(shù)查詢服務(wù)。關(guān)于用戶提交的任意查詢范圍Q，存在以下3 種情況。

1)Q所覆蓋的查詢范圍完全包含在劃分發(fā)布結(jié)構(gòu)的單個區(qū)域范圍之內(nèi)。根據(jù)算法1，Q可能被包含在初始網(wǎng)格區(qū)域或者是合并網(wǎng)格形成的區(qū)域內(nèi)。對于前者，差分隱私總預(yù)算ε按照式(13)為每一層劃分節(jié)點分配隱私預(yù)算，從初始網(wǎng)格區(qū)域自底向上到達根節(jié)點的路徑滿足差分隱私。對于后者，假設(shè)該區(qū)域位于劃分發(fā)布結(jié)構(gòu)的第l層(l=2,3,…,h)，根據(jù)本文提出的隱私預(yù)算調(diào)整策略，該區(qū)域的隱私預(yù)算強度為；從該區(qū)域自底向上到達根節(jié)點的路徑滿足差分隱私。因此，情況1)的查詢范圍Q之內(nèi)發(fā)布數(shù)據(jù)受到強度為εQ=ε的差分隱私保護。

2)Q所覆蓋的查詢范圍包含劃分發(fā)布結(jié)構(gòu)中的p個完整區(qū)域。根據(jù)位置信息的空間分布，劃分發(fā)布結(jié)構(gòu)將位置集合所覆蓋的二維空間分割為獨立且互不相交的若干個區(qū)域。根據(jù)定理2，查詢范圍Q之內(nèi)的發(fā)布數(shù)據(jù)受到強度為εQ=max{εp}的差分隱私保護。p個完整區(qū)域既可能是初始網(wǎng)格區(qū)域，也可能是合并網(wǎng)格形成的區(qū)域，根據(jù)情況1)可知?εp=ε，所以情況2)的查詢范圍Q內(nèi)發(fā)布數(shù)據(jù)受到強度為εQ=max{εp}=ε的差分隱私保護。

3)Q所覆蓋的查詢范圍包含p個完整區(qū)域并與q個區(qū)域相交。類似于情況2)，此時查詢范圍Q之內(nèi)的發(fā)布數(shù)據(jù)受到強度為εQ=max{εi}(i∈p∪q)的差分隱私保護。根據(jù)情況1)可知?εi=ε，所以該情況下查詢范圍Q之內(nèi)發(fā)布數(shù)據(jù)受到強度為εQ=max{εi}=ε的差分隱私保護。

綜合上述情況可知，算法2 能夠為位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布結(jié)果提供ε-差分隱私保護。

5 實驗與分析

為了對本文基于深度學(xué)習(xí)的位置大數(shù)據(jù)統(tǒng)計發(fā)布與隱私保護方法進行綜合評估和分析，從劃分發(fā)布結(jié)構(gòu)的合理性、深度學(xué)習(xí)預(yù)測模型的準(zhǔn)確性、發(fā)布位置大數(shù)據(jù)的可用性、數(shù)據(jù)發(fā)布方法的運行效率等方面，將本文方法與經(jīng)典的UG 方法[10]、AG方法[10]、Quad-opt 方法[17]、Unbalanced Quadtree方法[39]進行比較分析。

實驗數(shù)據(jù)分別選用紐約市共享單車使用記錄數(shù)據(jù)集 BikeShare（2015—2017 年）、Macquarie University 智慧城市項目的車輛統(tǒng)計數(shù)據(jù)集Macquarie Park、紐約出租車管理委員會提供的乘車記錄數(shù)據(jù)集Yellow_tripdata（2009—2016 年）。實驗平臺選用華為云服務(wù)器ECS（pi2.4xlarge.4：Intel SkyLake 6151 3.0 GHz/Intel Cascade Lake 6278 2.6 GHz CPU；GPU：2×NVIDIA T4/2×16 G；64 GB 內(nèi)存；100 G SSD 云硬盤；Windows Server 2016 64 位標(biāo)準(zhǔn)版鏡像），算法使用Python 3.8 編程，采用深度學(xué)習(xí)框架TensorFlow 作為后端引擎，選擇Keras 高層神經(jīng)網(wǎng)絡(luò)API 作為前端搭建深度學(xué)習(xí)預(yù)測模型。

5.1 劃分發(fā)布結(jié)構(gòu)的合理性

為了直觀地了解位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布結(jié)構(gòu)的合理性，對相同位置大數(shù)據(jù)集合的空間分布狀態(tài)和各種方法得到的劃分發(fā)布結(jié)構(gòu)進行橫向比較。圖5 是各種方法針對Yellow_tripdata 數(shù)據(jù)集得到的劃分發(fā)布結(jié)構(gòu)。其中UG 方法的常數(shù)參量c=10，AG 方法的隱私分配比例α=0.5，Quad-opt 方法的劃分深度h=6，Unbalanced Quadtree 方法的均勻性判定閾值θ=0.01。

觀察圖5 中的各種劃分結(jié)果不難發(fā)現(xiàn)，UG 方法得到的劃分結(jié)構(gòu)與位置數(shù)據(jù)集合的分布狀態(tài)無關(guān)，劃分結(jié)構(gòu)中存在大量的空網(wǎng)格（密度值為0 的網(wǎng)格），添加Laplace 噪聲之后容易產(chǎn)生較大的噪聲誤差，影響位置統(tǒng)計信息的可用性。AG 方法的劃分過程是對UG 方法中密度較大的網(wǎng)格區(qū)域進一步劃分細粒度的網(wǎng)格單元，其效果是對位置點密集區(qū)域進行與數(shù)據(jù)分布特性相關(guān)的細致劃分，但是仍然無法避免位置點稀疏區(qū)域存在的噪聲誤差問題。Quad-opt 方法的劃分過程采用與位置數(shù)據(jù)分布狀態(tài)無關(guān)的完全四叉樹結(jié)構(gòu)，當(dāng)劃分層次較少時容易產(chǎn)生較大的均勻假設(shè)誤差，而當(dāng)劃分層次較多時與UG 方法同樣存在較大的噪聲誤差。Unbalanced Quadtree 方法采用基于均勻性判斷的非平衡四叉樹劃分結(jié)構(gòu)，可以根據(jù)位置數(shù)據(jù)的分布狀態(tài)啟發(fā)式的引導(dǎo)劃分過程，其合理性高于前3 種方法。本文方法能夠根據(jù)位置大數(shù)據(jù)的分布特性對二維空間進行細致劃分和自底向上的合并，細致劃分降低了位置點密集區(qū)域的均勻假設(shè)誤差，自底向上合并過程減少了位置點稀疏區(qū)域的“過劃分”現(xiàn)象，避免過多的噪聲誤差。綜合比較上述劃分發(fā)布結(jié)構(gòu)，對于相同的位置大數(shù)據(jù)集合，本文方法產(chǎn)生的統(tǒng)計劃分發(fā)布結(jié)構(gòu)更加合理。

圖5 劃分發(fā)布結(jié)構(gòu)比較

5.2 深度學(xué)習(xí)模型預(yù)測準(zhǔn)確性

為了驗證深度學(xué)習(xí)模型對劃分發(fā)布結(jié)構(gòu)預(yù)測的準(zhǔn)確性，首先將實際位置大數(shù)據(jù)集合按照發(fā)布時間間隔進行子集劃分（BikeShare 數(shù)據(jù)集的發(fā)布間隔為 Δt1=60min，Macquarie Park 數(shù)據(jù)集的發(fā)布間隔為 Δt2=15min，Yellow_tripdata 數(shù)據(jù)集的發(fā)布間隔為 Δt3=10min），并按照本文提出的網(wǎng)格劃分與合并方法生成劃分結(jié)構(gòu)矩陣；然后按照時間順序?qū)澐纸Y(jié)構(gòu)矩陣組織成深度學(xué)習(xí)預(yù)測模型的輸入序列，對下一發(fā)布時刻的劃分發(fā)布結(jié)構(gòu)進行預(yù)測；最后與真實數(shù)據(jù)子集上的劃分結(jié)構(gòu)矩陣進行比較。

使用均方誤差（MSE,mean square error）、均方根誤差（RMSE,root mean square error）、平均絕對誤差（MAE,mean absolute error）評估深度學(xué)習(xí)預(yù)測模型的準(zhǔn)確性，定義如式(15)～式(17)所示。其中Fp表示劃分結(jié)構(gòu)矩陣的預(yù)測值，F(xiàn)t表示劃分結(jié)構(gòu)矩陣的真實值。

引入多分類評價指標(biāo)中的宏平均（Macro-average）和微平均（Micro-average），進一步衡量預(yù)測劃分結(jié)構(gòu)矩陣與真實劃分結(jié)構(gòu)矩陣在所有網(wǎng)格區(qū)域劃分結(jié)果上的誤差，其定義如式(18)～式(19)所示。其中TP（true positive）、FP（false positive）、TN（true negative）和FN（false negative）分別表示真正例數(shù)、假正例數(shù)、真反例數(shù)和假反例數(shù)，F(xiàn)1 函數(shù)的定義與多分類評價一致。

實驗過程中各類深度學(xué)習(xí)預(yù)測模型的結(jié)構(gòu)和參數(shù)設(shè)置如表1～表4 所示，各模型的準(zhǔn)確性評價指標(biāo)結(jié)果如表5 所示。在不同規(guī)模的位置大數(shù)據(jù)集合上，基于時空特性的深度學(xué)習(xí)預(yù)測模型均獲得了較低的預(yù)測誤差。特別是在預(yù)測劃分層次與真實劃分層次之間的誤差方面，基于時空特性的深度學(xué)習(xí)預(yù)測模型的宏平均值和微平均值遠高于簡單時間序列模型的預(yù)測精度，說明利用深度學(xué)習(xí)預(yù)測模型得到的統(tǒng)計劃分發(fā)布結(jié)構(gòu)在絕大多數(shù)情況下都獲得了與真實劃分結(jié)構(gòu)一致的結(jié)果，證明了深度學(xué)習(xí)預(yù)測模型的可行性和準(zhǔn)確性。

表5 各模型的準(zhǔn)確性評價指標(biāo)結(jié)果

5.3 發(fā)布位置大數(shù)據(jù)的可用性

為了驗證本文位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布數(shù)據(jù)的可用性，選用5.2 節(jié)中效果最好的ST-LSTM 模型實現(xiàn)位置大數(shù)據(jù)劃分發(fā)布結(jié)構(gòu)預(yù)測，按照算法2 實現(xiàn)差分隱私位置大數(shù)據(jù)統(tǒng)計信息發(fā)布。針對發(fā)布結(jié)果進行不同尺寸的范圍計數(shù)查詢，并將本文方法的相對誤差與UG、AG、Quad-opt、Unbalanced Quadtree 等方法的結(jié)果進行比較。實驗過程中范圍計數(shù)查詢區(qū)域的尺寸設(shè)置如表6 所示，各種方法的參數(shù)設(shè)置與5.1 節(jié)相同，差分隱私模型分別添加隱私預(yù)算為ε=0.1、ε=0.5、ε=1的Laplace 噪聲，每種類型的查詢區(qū)域隨機生成1 000 個。相對誤差的定義如式(20)所示。

表6 實驗過程中范圍計數(shù)查詢區(qū)域的尺寸設(shè)置

其中，q是用戶向位置大數(shù)據(jù)統(tǒng)計發(fā)布平臺提交的查詢范圍，C(q)是在原始位置大數(shù)據(jù)集上相應(yīng)范圍內(nèi)得到的查詢結(jié)果，C*(q)是在發(fā)布位置大數(shù)據(jù)集上相應(yīng)范圍內(nèi)得到的查詢結(jié)果，代表位置大數(shù)據(jù)集的大小。

圖6～圖8 用對數(shù)坐標(biāo)展示了各種方法在不同數(shù)據(jù)集上的相對誤差比較結(jié)果。在相同的實驗數(shù)據(jù)集上，各種方法的相對誤差都隨著隱私預(yù)算ε的增大而逐漸減小，其原因是隱私預(yù)算ε的增大使添加的Laplace 噪聲值減小，因而發(fā)布數(shù)據(jù)與真實統(tǒng)計值之間的誤差也減小了。在數(shù)據(jù)分布較稀疏的BikeShare 和Macquarie Park 數(shù)據(jù)集上，UG 和Quad-opt 方法的相對誤差較大，其原因在于UG 和Quad-opt 方法的粗粒度劃分過程與位置點分布密度無關(guān)，導(dǎo)致在較小查詢范圍內(nèi)的區(qū)域噪聲誤差較大，而在較大查詢范圍內(nèi)的均勻假設(shè)誤差較大。AG方法對位置點密集區(qū)域進行了第二層細粒度的網(wǎng)格劃分，因此在查詢范圍較小時相對誤差較小，而當(dāng)查詢范圍尺度較大時相對誤差發(fā)生惡化。Unbalanced Quadtree 方法根據(jù)區(qū)域分布密度進行啟發(fā)式四叉樹劃分，本文方法根據(jù)均勻性進行自底向上的網(wǎng)格合并，得到的劃分結(jié)構(gòu)比UG、AG 和Quad-opt 方法更合理，因此在各類查詢范圍下的相對誤差都優(yōu)于上述算法。在數(shù)據(jù)分布最稠密的Yellow_tripdata 數(shù)據(jù)集上，AG 方法的第二層細粒度網(wǎng)格劃分使在查詢范圍較小的情況下（q1和q2）獲得了較低的相對誤差，而當(dāng)查詢范圍增大時，本文方法的范圍計數(shù)查詢精度最高。

圖6 BikeShare 數(shù)據(jù)集范圍計數(shù)查詢精度比較

圖7 Macquarie Park 數(shù)據(jù)集范圍計數(shù)查詢精度比較

圖8 Yellow_tripdata 數(shù)據(jù)集范圍計數(shù)查詢精度比較

5.4 位置大數(shù)據(jù)發(fā)布方法的運行效率

為了驗證本文提出的差分隱私位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布方法的運行效率，將本文方法的整體運行時間與UG、AG、Quad-opt、Unbalanced Quadtree等方法進行比較分析，各種方法的參數(shù)設(shè)置與5.2 節(jié)相同。由于差分隱私預(yù)算強度對統(tǒng)計劃分發(fā)布方法的運行時間沒有明顯影響，本文以ε=0.5為例對3 個不同規(guī)模的實際位置大數(shù)據(jù)集進行實驗比較。圖9用對數(shù)坐標(biāo)展示了各種位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布方法在實際位置大數(shù)據(jù)集合上的運行時間。

從圖9 可以看出，UG 方法由于不考慮位置數(shù)據(jù)的具體分布狀態(tài)所以運行效率最高，而且?guī)缀醪皇軘?shù)據(jù)集合大小的影響。AG 方法在UG 方法的基礎(chǔ)上多執(zhí)行了一遍細粒度網(wǎng)格劃分，所以整體算法用時長于UG 方法。Quad-opt 方法的劃分過程雖然也不考慮位置數(shù)據(jù)的具體分布狀態(tài)，但是采用深度優(yōu)先遍歷的樹型迭代過程，整體用時明顯高于UG 和AG 方法。Unbalanced Quadtree 方法劃分過程需要結(jié)合位置數(shù)據(jù)的具體分布狀態(tài)，但是因為能夠在位置點稀疏區(qū)域避免不必要的細致劃分，反而節(jié)省了不少時間，整體運行時間介于AG 和Quad-opt 方法之間。本文方法使用深度學(xué)習(xí)預(yù)測模型產(chǎn)生統(tǒng)計劃分發(fā)布結(jié)構(gòu)，深度學(xué)習(xí)預(yù)測模型的構(gòu)建、訓(xùn)練、參數(shù)優(yōu)化等步驟可以借助歷史數(shù)據(jù)提前完成，所以在運行時只需花費極少的時間產(chǎn)生預(yù)測劃分結(jié)構(gòu)，繼而添加差分隱私噪聲形成位置大數(shù)據(jù)的統(tǒng)計劃分發(fā)布結(jié)果，整體的運行時間僅次于UG 方法。

圖9 不同數(shù)據(jù)集的運行時間比較

6 結(jié)束語

大數(shù)據(jù)技術(shù)的深入發(fā)展和移動智能終端的廣泛普及使基于位置的各種服務(wù)與用戶的工作和生活緊密相關(guān)，涉及的位置隱私保護問題也引起了廣泛的關(guān)注。位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布技術(shù)借助空間分解和差分隱私保護模型實現(xiàn)位置數(shù)據(jù)統(tǒng)計信息的發(fā)布，在保證數(shù)據(jù)可用性的基礎(chǔ)上有效避免了用戶位置隱私的泄露風(fēng)險。為了充分利用位置大數(shù)據(jù)的周期性和時空關(guān)聯(lián)性，減少統(tǒng)計劃分過程的冗余操作，本文提出基于深度學(xué)習(xí)的位置大數(shù)據(jù)劃分結(jié)構(gòu)預(yù)測方法和差分隱私發(fā)布方法。通過設(shè)計合理的網(wǎng)格劃分與合并算法將歷史位置大數(shù)據(jù)的劃分結(jié)構(gòu)轉(zhuǎn)換為三維時空序列。構(gòu)建基于時空序列的深度學(xué)習(xí)預(yù)測模型，通過提取歷史位置大數(shù)據(jù)統(tǒng)計劃分結(jié)構(gòu)矩陣的時間和空間相關(guān)特性，實現(xiàn)對劃分結(jié)構(gòu)矩陣的有效預(yù)測。設(shè)計了與預(yù)測劃分結(jié)構(gòu)相匹配的差分隱私預(yù)算分配和調(diào)整方案，實現(xiàn)了位置大數(shù)據(jù)統(tǒng)計劃分發(fā)布結(jié)果的差分隱私保護。通過實際位置大數(shù)據(jù)集合的實驗和分析證明了本文方法的可行性和有效性。