差分隱私下滿足一致性的軌跡流量發(fā)布方法*

張雙越，蔡劍平，田 豐，吳振強(qiáng)+

1.陜西師范大學(xué) 計算機(jī)科學(xué)學(xué)院，西安 710119

2.福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福州 350116

1 引言

隨著移動互聯(lián)網(wǎng)和GPS定位技術(shù)的發(fā)展，移動對象不斷上傳的位置信息形成了軌跡大數(shù)據(jù)。根據(jù)軌跡數(shù)據(jù)所含的豐富時空信息可以挖掘分析出許多人類行為模式和交通演化規(guī)律[1]。在路網(wǎng)交通背景下，對車輛軌跡數(shù)據(jù)中各個統(tǒng)計指標(biāo)的發(fā)布可為道路管理及應(yīng)急規(guī)劃提供有力支持。例如，發(fā)布軌跡流量指標(biāo)的統(tǒng)計信息可反映出每條路段的擁堵程度以及流量特征，這對于用戶出行，交通指揮，乃至路網(wǎng)結(jié)構(gòu)調(diào)整及整個路網(wǎng)的承載能力和可靠性的提高都有重要的現(xiàn)實(shí)意義和應(yīng)用價值[2-3]。

然而，軌跡數(shù)據(jù)中隱含了用戶的出行習(xí)慣、行為模式等隱私信息[4-5]。因此，直接發(fā)布軌跡流量值可能造成用戶隱私泄露。例如，假設(shè)攻擊者掌握了某個特定時段內(nèi)除目標(biāo)用戶之外其他用戶的軌跡信息，則他再結(jié)合所發(fā)布的軌跡流量數(shù)據(jù)即可追蹤出目標(biāo)用戶在該時段內(nèi)的軌跡。為了保護(hù)用戶隱私，常用的軌跡發(fā)布隱私保護(hù)方法主要有假數(shù)據(jù)法[6-7]、泛化法[8-12]、抑制法[13-15]。這些方法通常通過變換或剔除軌跡中的敏感信息來保護(hù)軌跡數(shù)據(jù)的發(fā)布。但是，這些方法對攻擊者擁有的背景知識敏感，容易受到背景知識攻擊。當(dāng)攻擊者掌握了較多的背景信息時，用戶的隱私就難以保障且缺乏嚴(yán)格的數(shù)學(xué)證明。2008年Dwork針對統(tǒng)計數(shù)據(jù)庫的隱私泄露問題提出了差分隱私模型[16]。該模型保證了攻擊者在任何知識背景下都無法準(zhǔn)確地從所發(fā)布的數(shù)據(jù)中獲得隱私信息且具有嚴(yán)格的概率分布不可區(qū)分性證明，引起了廣大研究者的興趣。2011年起，差分隱私模型被應(yīng)用到軌跡發(fā)布隱私保護(hù)中，并取得了一系列成果[17-24]。但是，已有的工作專注于發(fā)布經(jīng)過差分隱私保護(hù)的整個軌跡數(shù)據(jù)集，對路網(wǎng)環(huán)境下的軌跡流量發(fā)布缺乏考慮。本文在路網(wǎng)約束下結(jié)合差分隱私在保護(hù)統(tǒng)計信息領(lǐng)域的優(yōu)勢提出軌跡流量發(fā)布算法，并對該算法進(jìn)行一致性優(yōu)化，提高了發(fā)布結(jié)果的可用性和發(fā)布效率。

本文將路網(wǎng)結(jié)構(gòu)抽象為有向圖，有向圖中的邊連接兩個相鄰的路口，同時將軌跡數(shù)據(jù)相應(yīng)地處理為形如圖1（b）所示的有序序列，對這些軌跡數(shù)據(jù)進(jìn)行統(tǒng)計即可得到路網(wǎng)中各個路段的軌跡流量。以北京某街區(qū)為例，圖1（a）為該街區(qū)道路示意圖，圖1（b）為該示意圖上的車輛軌跡數(shù)據(jù)樣例。經(jīng)統(tǒng)計得到的軌跡流量圖如圖2（a）所示。圖2（a）中節(jié)點(diǎn)和邊分別對應(yīng)圖1（a）中的各個路口和街道，邊上的權(quán)值代表了相應(yīng)路段的軌跡流量。接下來，在差分隱私機(jī)制下，向圖2（a）中的邊權(quán)值添加符合拉普拉斯分布的噪聲以保護(hù)用戶隱私。添加噪聲后的流量圖如圖2（b）所示。不難發(fā)現(xiàn)，由于拉普拉斯噪聲的引入導(dǎo)致了某些路口出入流量不一致的問題。如B路口所示（非起止路口），添加噪音擾動前車輛駛?cè)朐撀房诘拇螖?shù)等于駛出該路口的次數(shù)，如圖2（a）都為3；添加噪音擾動后，該路口的駛?cè)胲嚧螢?，駛出車次為3。這顯然與實(shí)際情況不符。深入研究發(fā)現(xiàn)，不一致問題不僅導(dǎo)致發(fā)布結(jié)果不符合實(shí)際，同時也增大了發(fā)布誤差。為此，本文提出了一種一致性調(diào)節(jié)方案來解決上述問題。

Fig.1 Vehicle trajectory from a city block圖1 某城市街區(qū)及該街區(qū)的車輛軌跡

Fig.2 Traffic flow before and after protection圖2 保護(hù)前后的軌跡流量圖

對于差分隱私領(lǐng)域的不一致性問題已有學(xué)者進(jìn)行了研究[25]。例如，Hay等人[26]對直方圖發(fā)布中的不一致性問題提出了后置處理方案。然而由于研究目標(biāo)不同，該方案無法直接應(yīng)用于解決本文中的不一致問題。因此，本文在參考Hay等人[26]思路的基礎(chǔ)上提出了一種新的后置調(diào)節(jié)算法。經(jīng)過大量的理論分析以及實(shí)驗表明，本文所提后置處理算法不僅能有效地解決上述不一致問題，還在合理的時間內(nèi)對發(fā)布結(jié)果的精度有了明顯提升。

綜上所述，本文完成了以下工作：

（1）將實(shí)際城市路網(wǎng)抽象成有向圖模型，并向圖中引入一個輔助的虛擬節(jié)點(diǎn)。利用該虛擬節(jié)點(diǎn)形式化表現(xiàn)了流量圖中的不一致性問題。

（2）結(jié)合拉普拉斯機(jī)制提出差分隱私流量圖生成算法。

（3）在（2）的基礎(chǔ)上提出一致性調(diào)節(jié)算法。該算法在嚴(yán)格的理論分析和公式推導(dǎo)下有效地解決了一致性問題，并提升了發(fā)布精度。

（4）在真實(shí)路網(wǎng)上對本文所提算法進(jìn)行實(shí)驗驗證，結(jié)果表明一致性調(diào)節(jié)算法減小了約13%的發(fā)布誤差且具有處理大規(guī)模數(shù)據(jù)的能力。

2 相關(guān)工作

為了解決軌跡數(shù)據(jù)發(fā)布過程中的隱私泄露問題，文獻(xiàn)[17]首次引入了差分隱私機(jī)制。該文獻(xiàn)利用原始軌跡數(shù)據(jù)的特性構(gòu)建噪音前綴樹，并向前綴樹節(jié)點(diǎn)的計數(shù)值中添加拉普拉斯噪聲保證用戶的軌跡隱私。然而隨著前綴樹規(guī)模的增大，樹中的節(jié)點(diǎn)將呈指數(shù)增長，導(dǎo)致落入每個分支的軌跡數(shù)量急劇減少，嚴(yán)重降低了數(shù)據(jù)可用性。隨后文獻(xiàn)[18]通過n-gram模型實(shí)現(xiàn)了可變長度的軌跡數(shù)據(jù)集發(fā)布，在一定程度上改善了文獻(xiàn)[17]的不足。但是，文獻(xiàn)[17-18]都基于一個共同的假設(shè)，即原始數(shù)據(jù)中存在大量的共同前綴，這在現(xiàn)實(shí)中很難滿足。文獻(xiàn)[20]利用指數(shù)機(jī)制對軌跡數(shù)據(jù)進(jìn)行聚類操作，去除了軌跡數(shù)據(jù)中存在共同前綴的假設(shè)條件。文獻(xiàn)[23]提出一種有界噪音泛化算法，減小了信息損失和平均軌跡合并時間。然而，以上文獻(xiàn)都是發(fā)布經(jīng)過差分隱私保護(hù)的整個軌跡數(shù)據(jù)集。文獻(xiàn)[24]提出l-軌跡差分隱私保護(hù)模型，實(shí)時發(fā)布無限軌跡流上不同位置的用戶統(tǒng)計值。然而卻鮮有文獻(xiàn)考慮路網(wǎng)約束下的軌跡統(tǒng)計值發(fā)布。文獻(xiàn)[27]指出當(dāng)發(fā)布大量用戶位置的聚合信息時，差分隱私能提供較好的隱私保障。因此本文就以保護(hù)路網(wǎng)中的軌跡流量統(tǒng)計值作為切入點(diǎn)展開研究工作。

差分隱私中常見的優(yōu)化方法主要分為基于數(shù)據(jù)壓縮轉(zhuǎn)換的前置優(yōu)化算法以及基于規(guī)劃策略的后置優(yōu)化算法[26]。Hay等人[26]利用區(qū)間樹的一致性問題對直方圖統(tǒng)計發(fā)布進(jìn)行優(yōu)化就是一種典型的后置優(yōu)化算法，該算法利用最優(yōu)估計理論不僅解決了區(qū)間樹的不一致性問題，同時還有效地提升了發(fā)布數(shù)據(jù)的可用性。在該理論的啟發(fā)下，本文提出了一種新的優(yōu)化模型，有效解決了軌跡流量發(fā)布過程中的不一致問題并提升了發(fā)布數(shù)據(jù)的有效性。

3 預(yù)備知識

3.1 基本概念

本文在論述過程中涉及到較多的數(shù)學(xué)符號，因此在介紹相關(guān)概念之前，先對這些符號進(jìn)行說明，以方便讀者理解。如表1所示。

定義1（路網(wǎng)拓?fù)鋱D）將城市道路網(wǎng)抽象成一個有向圖G=(V,E),其中V表示道路網(wǎng)中所有交叉路口的集合，E表示道路網(wǎng)中所有相鄰交叉路口之間路段的集合。其相應(yīng)的鄰接矩陣記為M∈{0,1}|V|×|V|。其中，|V|表示集合V的大小，mu,v=1表示路口u和v之間存在邊，否則不存在邊。無特殊說明，以下將路網(wǎng)拓?fù)浜喎Q為路網(wǎng)。

定義2（軌跡空間）軌跡是移動用戶產(chǎn)生的一系列位置vi按照時間排序構(gòu)成的集合，記為L。本文對軌跡L進(jìn)行預(yù)處理，使得L由所有它所經(jīng)過的交叉路口表示，即?vi,vj∈V，且每兩個相鄰節(jié)點(diǎn)所構(gòu)成的邊都屬于邊集E。由此可對軌跡空間Ω做如下定義：

其中，N表示軌跡L的長度。

現(xiàn)實(shí)中的任何軌跡經(jīng)過預(yù)處理后均是Ω中的一個元素。本文所用的軌跡數(shù)據(jù)集D是Ω的子集。根據(jù)軌跡數(shù)據(jù)集D和路網(wǎng)即可構(gòu)建軌跡流量圖。軌跡流量圖定義如下。

定義3（軌跡流量圖）根據(jù)軌跡數(shù)據(jù)集D計算出路網(wǎng)中每條邊的權(quán)值，由此構(gòu)成的有向加權(quán)圖即為軌跡流量圖。邊u→v的權(quán)值表示軌跡數(shù)據(jù)集D中經(jīng)過邊u→v的軌跡數(shù)量。軌跡流量圖中各個邊的權(quán)值構(gòu)成的流量矩陣記為。W即為本文發(fā)布的軌跡流量圖。以下簡稱流量圖。

3.2 差分隱私

定義4（差分隱私）假設(shè)存在一個隨機(jī)算法A,SA表示該算法所有可能的輸出構(gòu)成的集合。則對于兩個相鄰的數(shù)據(jù)集D，D′(|DΔD′|≤ 1)以及SA，若算法A滿足：

定義5（全局敏感度）對于任意函數(shù)f:D→Rd，全局敏感度表示向數(shù)據(jù)集中添加或刪除一條記錄，對函數(shù)f產(chǎn)生的最大影響。全局敏感度Δf可由以下公式計算：

其中，D和D′滿足|DΔD′|≤ 1。

拉普拉斯機(jī)制[28]是常用的實(shí)現(xiàn)差分隱私的技術(shù)。它通過向查詢結(jié)果添加符合拉普拉斯分布的噪音值來實(shí)現(xiàn)差分隱私。對于函數(shù)f:D→Rd，拉普拉斯機(jī)制實(shí)現(xiàn)差分隱私保護(hù)的過程可表示如下：

4 軌跡流量圖發(fā)布

流量圖的發(fā)布過程包括兩步：（1）生成差分隱私流量圖，即統(tǒng)計路網(wǎng)中各路段的流量值并添加獨(dú)立同分布的拉普拉斯噪音；（2）一致性調(diào)節(jié)，即對（1）中的流量圖進(jìn)行出入流量一致性調(diào)節(jié)。下面分別描述這兩個過程。

4.1 差分隱私流量圖

軌跡流量圖中節(jié)點(diǎn)的流入流量表示從各個方向駛向該節(jié)點(diǎn)的車次，而流出流量表示所有駛離該節(jié)點(diǎn)的車次。通過觀察分析不難發(fā)現(xiàn)，當(dāng)節(jié)點(diǎn)不是任何軌跡的起止點(diǎn)時，該節(jié)點(diǎn)的出入流量相等。為此，本文引入一個虛擬節(jié)點(diǎn)pv，并讓該虛擬節(jié)點(diǎn)作為所有軌跡的起止點(diǎn)，使軌跡變?yōu)槭孜蚕噙B的環(huán)，且虛擬節(jié)點(diǎn)與路網(wǎng)中每個節(jié)點(diǎn)都相連。虛擬節(jié)點(diǎn)的引入使得流量圖中所有節(jié)點(diǎn)（包括虛擬節(jié)點(diǎn)）的出入流量都相等且不會影響真實(shí)流量圖中各邊的統(tǒng)計值。沒有特殊說明，下文中的路網(wǎng)鄰接矩陣M和流量矩陣W中均包含了虛擬節(jié)點(diǎn)。

4.1.1 差分隱私流量圖算法

3．宋·天臺金卞《游金庭觀》：“尋真窮養(yǎng)浩，崇妙路迢迢。洞掩峰千疊，塵分水一條。白云生石壁，飛閣插崖腰。隱隱存仙跡，渾疑在碧霄?！盵7]2426

使用差分隱私進(jìn)行隱私保護(hù)前首先需要明確相鄰數(shù)據(jù)集和全局敏感度。本文規(guī)定如果兩個軌跡數(shù)據(jù)集D和D′僅相差一個位置點(diǎn)，則稱兩者為相鄰數(shù)據(jù)集。因此，軌跡數(shù)據(jù)集D的相鄰數(shù)據(jù)集D′（仍為Ω的子集）可通過刪除或替換D中某條軌跡的一個位置點(diǎn)得到。刪除方式引起的流量改變值為3，替換方式引起的流量改變值為4。由定義3可知，發(fā)布一個流量圖的全局敏感度為4，即Δf=4。

差分隱私流量圖算法描述見算法1。該算法的輸入為軌跡數(shù)據(jù)集D，路網(wǎng)鄰接矩陣M以及差分隱私預(yù)算ε；輸出為真實(shí)的軌跡流量鄰接矩陣W以及滿足差分隱私的流量矩陣。算法1中首先初始化輸出變量，2～5行對軌跡數(shù)據(jù)集進(jìn)行處理，使每條軌跡的首尾與虛擬節(jié)點(diǎn)pv相連，然后統(tǒng)計路網(wǎng)中每個路段的流量值；6、7行向流量圖中存在邊的流量值添加噪音擾動，這是由于流量圖中不存在的邊不可能有軌跡經(jīng)過，對其添加噪聲保護(hù)沒有意義；最后將流量矩陣返回。接下來對算法1的隱私性和誤差進(jìn)行分析。

算法1軌跡流量圖發(fā)布

輸入：軌跡數(shù)據(jù)集D，鄰接矩陣M，隱私預(yù)算ε。

輸出：加噪前后的流量矩陣W、。

4.1.2 差分隱私流量圖算法分析

本節(jié)首先證明差分隱私流量圖算法符合差分隱私的定義，即算法1可以保證用戶的軌跡隱私；然后分析該算法中由于差分隱私噪聲的添加所引起的發(fā)布誤差。用P:D→Rk代表差分隱私流量圖生成算法，輸入為軌跡數(shù)據(jù)集D，輸出為實(shí)數(shù)域上的k維向量，k代表路網(wǎng)中所有的邊數(shù)，其所有可能的輸出結(jié)果為SP。D′與D是任意兩個相鄰的軌跡數(shù)據(jù)集，則對于任意的輸出o(o1,o2,…,ok)∈SP有：

對其進(jìn)行推導(dǎo)可得：

由前文關(guān)于差分隱私的定義可知，軌跡流量圖發(fā)布算法符合差分隱私的定義。

接下來分析算法1中由于差分隱私噪聲的添加引起的發(fā)布誤差。根據(jù)式（5）可知，每添加一次拉普拉斯噪聲將引起 2(Δf)2/ε2=2(4/ε)2的均方誤差。算法1對路網(wǎng)矩陣M的每條邊均添加拉普拉斯噪聲。因此，的總體均方誤差為 2(4ε)2×|E|，其中 |E|表示路網(wǎng)中所有的邊數(shù)。由以上公式可知，算法1所發(fā)布的流量圖誤差大小取決于路網(wǎng)中邊的數(shù)量以及用戶設(shè)定的隱私預(yù)算ε，與軌跡數(shù)量沒有關(guān)系。因此，在同一個路網(wǎng)中算法1所引起的誤差不會隨著軌跡數(shù)據(jù)集的改變而改變。

由于算法1對軌跡流量圖中的每條邊獨(dú)立加噪，因此破壞了路網(wǎng)中節(jié)點(diǎn)出入流量相等的特性。針對這個問題，下面將通過二次規(guī)劃求解，對算法1進(jìn)行一致性調(diào)節(jié)。

4.2 一致性調(diào)節(jié)算法

如圖2（b）所示，添加噪音擾動后的流量圖大部分節(jié)點(diǎn)的出入流量不相等，雖然保護(hù)了用戶的隱私，但是影響了發(fā)布數(shù)據(jù)的可用性。本節(jié)針對該問題提出算法2。對加噪后的流量圖進(jìn)行一致性調(diào)節(jié),使得發(fā)布的流量圖在滿足差分隱私的同時具有較高的可用性。推導(dǎo)過程涉及了大量符號，符號說明見表1。

分別記一致性調(diào)節(jié)前后的流量矩陣為和，其元素分別表示為ij和ij。經(jīng)分析發(fā)現(xiàn)，由得到的過程可轉(zhuǎn)化為求解凸優(yōu)化表達(dá)式（6）：

其中，I|V|+1表示長度為|V|+1（包含虛擬節(jié)點(diǎn)）且所有元素全為1的列向量。懲罰系數(shù)α2(α>>1)的引入是使得路網(wǎng)中不存在的邊上的流量值在一致性調(diào)節(jié)后趨于0。因為當(dāng)邊i→j不存在時，若，則子式的值會非常大，而式（6）為了取得最小值就會迫使。極限情況下，當(dāng)α→+∞時，有。為了式（6）表達(dá)更加緊湊，記懲罰系數(shù)矩陣為C，其元素滿足。此時式（6）表示為：

當(dāng)α→+∞時，。因此，可使用鄰接矩陣M來代替。同時將式（8）中的⊙運(yùn)算部分利用普通乘法公式進(jìn)行代換，得到與之等價的表達(dá)式（9）：

其中，Di表示取M的第i行向量并將其對角化后的常數(shù)矩陣；Ei為第i行以及第i列為1其他全為0的對角陣。此時。因此，式（9）解出的X即為式（6）的解。

接下來，為了求解式（9），使用拉格朗日乘子法將其轉(zhuǎn)化為無約束的對偶問題。表示如下：

式中，u為拉格朗日系數(shù)組成的長度為|V|+1的列向量。對其化簡可得：

將式（11）對X求導(dǎo)，得到：

根據(jù)拉格朗日系數(shù)方法，L(u,X*)取得最大值的解即為式（6）的解。

接下來，求式（12）的最大值。不難發(fā)現(xiàn)該式為無約束的二次規(guī)劃問題，令其二次項系數(shù)矩陣diag((M+MT)I|V|+1-(M+MT))為Q，Q為拉普拉斯矩陣，即不可求逆的半正定矩陣，由于M為連通圖的鄰接矩陣，因而其秩等于鄰接矩陣的點(diǎn)數(shù)減去1。對式（12）求導(dǎo)可得：。根據(jù)Q的秩的性質(zhì)，可采用將u的最后一個元素設(shè)為0求解。記′。同時由于路網(wǎng)鄰接矩陣M中的虛擬節(jié)點(diǎn)pv與其他節(jié)點(diǎn)相連，將Q做如下分塊，代入式（12）可得：

P為式（13）的二次項系數(shù)矩陣，對其分析可知該系數(shù)矩陣為正定矩陣。具體分析如下:

Q為半正定矩陣且，得，可知P′也是拉普拉斯矩陣，具有半正定性。因此，將任意非零列向量x代入下式有：

因此，P為正定矩陣。式（13）可直接求解得：

式（15）中求解u′的過程實(shí)際上就等價于解方程組Pu′=[E|V|o|V|](X′T-X′)I|V|+1。由于鄰接矩陣節(jié)點(diǎn)數(shù)眾多，而且極度稀疏。為使得式（15）具有更高效的求解效率，本文采用了PCG（preconditioned conjugate gradients method）。該算法是現(xiàn)有解決大規(guī)模稀疏方程組最有效的方法之一。由式（15）求得的結(jié)果u′即可得到u，由此求得一致性調(diào)節(jié)后的流量矩陣及最小誤差分別為：

根據(jù)上述推導(dǎo)，最終得到一致性調(diào)節(jié)算法。

算法2一致性調(diào)節(jié)算法

輸入：添加噪聲保護(hù)的流量圖，路網(wǎng)矩陣M。

輸出：一致性調(diào)節(jié)后的流量圖。

為保證算法效率，上述算法中的矩陣均采用系數(shù)矩陣存儲并采用相關(guān)算法進(jìn)行解釋，具體過程文本不做進(jìn)一步討論。算法2的實(shí)現(xiàn)過程中采用了稀疏矩陣的數(shù)據(jù)結(jié)構(gòu)及相關(guān)算法。關(guān)于稀疏矩陣的算法已經(jīng)有諸多研究以及API的支持。本文在第5章提供了該算法的實(shí)現(xiàn)源碼下載網(wǎng)址，供讀者參考。

5 實(shí)驗分析

本章主要從效用和執(zhí)行效率兩方面對本文提出的算法進(jìn)行驗證。實(shí)驗的硬件環(huán)境為：Intel?CoreTMi7-6700 CPU@3.40 GHz，16 GB內(nèi)存；用Matlab實(shí)現(xiàn)。實(shí)驗中所用的路網(wǎng)分別來自德國奧爾登堡（Oldenburg）市，美國的圣華金（San Joaquin）以及舊金山灣區(qū)（San Francisco Bay Area）三個城市，相應(yīng)的三個城市中的軌跡數(shù)據(jù)由Brinkhoff基于路網(wǎng)的軌跡生成器生成。Brinkhoff軌跡生成器和三個城市的路網(wǎng)信息數(shù)據(jù)可以從網(wǎng)站http://iapg.jade-hs.de/personen/brinkhoff/generator/下載。本實(shí)驗中所用到的三個城市的路網(wǎng)信息以及相應(yīng)路網(wǎng)上的軌跡詳細(xì)信息如表2所示。其中，邊的方向不同視為不同的邊，路口數(shù)表示路網(wǎng)中交叉路口的數(shù)量。本章所涉及到的主要實(shí)驗源碼及部分供驗證的數(shù)據(jù)已經(jīng)上傳到http://matweb.applinzi.com/paperCode/，供讀者下載參考。本章實(shí)驗包括三部分：（1）分析一致性調(diào)節(jié)前后算法1的相對誤差；（2）采用標(biāo)準(zhǔn)誤差具體分析一致性調(diào)節(jié)對算法1的優(yōu)化情況，標(biāo)準(zhǔn)誤差采用矩陣Frobenius范數(shù)計算，即；（3）對算法1和算法2的耗時情況進(jìn)行分析。下面分別介紹這三部分。

Table 2 Details of road network and trajectory表2 路網(wǎng)及軌跡信息

首先，采用奧爾登堡和圣華金的數(shù)據(jù)分別分析當(dāng)隱私預(yù)算ε取1時不同軌跡規(guī)模下一致性調(diào)節(jié)前后的相對誤差情況。相對誤差通過公式求得。實(shí)驗結(jié)果如圖3所示。橫坐標(biāo)為軌跡規(guī)模，縱坐標(biāo)為相對誤差。從圖中可以看出，同一路網(wǎng)中，隨著軌跡規(guī)模的增大，相對誤差逐漸減小，這是因為軌跡越多路網(wǎng)上流量值越大，相比之下噪音的影響就微乎其微。另外可發(fā)現(xiàn)，經(jīng)過一致性調(diào)節(jié)后的相對誤差明顯比調(diào)節(jié)前的小。接下來具體分析一致性調(diào)節(jié)算法的優(yōu)化程度。

Fig.3 Relative error圖3 相對誤差

為驗證算法2對流量圖發(fā)布精度的提升情況，分別計算當(dāng)ε取0.5、1.0、2.0、5.0時，三個城市一致性調(diào)節(jié)前后流量的標(biāo)準(zhǔn)誤差，其結(jié)果如圖4～圖6所示。隨著ε的增大，添加的噪音減小，相應(yīng)的整體誤差減??；隨著路網(wǎng)規(guī)模的增加，添加噪音的次數(shù)增加，相應(yīng)的整體誤差增加，與4.1.2節(jié)的誤差分析結(jié)果一致。另外可以看出，通過算法2的優(yōu)化，整體誤差減小了12%～14%，且減小的程度隨ε的改變無明顯變化，這說明算法2在不同的ε下是穩(wěn)定的。

Fig.4 Error of trajectory flow before and after consistency adjustment in Oldenburg圖4 奧爾登堡市一致性調(diào)節(jié)前后軌跡流量誤差

Fig.5 Error of trajectory flow before and after consistency adjustment in San Joaquin圖5 圣華金市一致性調(diào)節(jié)前后軌跡流量誤差

Fig.6 Error of trajectory flow before and after consistency adjustment in San Francisco圖6 舊金山一致性調(diào)節(jié)前后軌跡流量誤差

最后對算法1和算法2的耗時情況進(jìn)行分析，仍以奧爾登堡市、圣華金以及舊金山灣區(qū)三個城市路網(wǎng)數(shù)據(jù)進(jìn)行實(shí)驗，實(shí)驗結(jié)果如圖7。結(jié)合表2可看出根據(jù)不同城市路網(wǎng)節(jié)點(diǎn)數(shù)、邊數(shù)以及相應(yīng)的軌跡規(guī)模的不同，算法1的耗時相差較大。尤其是路網(wǎng)規(guī)模最大的舊金山灣區(qū)，由于處理的軌跡數(shù)量為98 048條且平均軌跡長度為312，因此耗時達(dá)到了340 s左右。而算法2在優(yōu)化上述三個城市的軌跡流量時用時均不到1 s。因此，本文所提出的一致性調(diào)節(jié)方法在提升軌跡流量發(fā)布效果的同時具有較高的發(fā)布效率且具有處理較大規(guī)模路網(wǎng)的能力。

Fig.7 Run time圖7 算法耗時

6 結(jié)束語

對蘊(yùn)含路網(wǎng)信息的軌跡大數(shù)據(jù)進(jìn)行分析，并發(fā)布一段時間內(nèi)路網(wǎng)上車流量的統(tǒng)計值，可為現(xiàn)實(shí)中的很多應(yīng)用提供參考信息。本文介紹了在差分隱私機(jī)制下發(fā)布基于路網(wǎng)的軌跡流量信息過程，并通過求解二次規(guī)劃問題實(shí)現(xiàn)了流量圖的后置處理算法。實(shí)驗證明該一致性調(diào)節(jié)算法不僅提高了發(fā)布數(shù)據(jù)的精度，而且可處理較大規(guī)模的路網(wǎng)數(shù)據(jù)。但是，由于本文算法是針對于靜態(tài)的軌跡流量圖發(fā)布所設(shè)計的，無法滿足現(xiàn)實(shí)中需要實(shí)時發(fā)布的應(yīng)用場景。因此，如何將本文所涉及的算法與軌跡流量圖發(fā)布的實(shí)時性相結(jié)合是下一步的研究方向。