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

張雙越，蔡劍平，田 豐，吳振強+

1.陜西師范大學 計算機科學學院，西安 710119

2.福州大學 數學與計算機科學學院，福州 350116

1 引言

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

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

本文將路網結構抽象為有向圖，有向圖中的邊連接兩個相鄰的路口，同時將軌跡數據相應地處理為形如圖1（b）所示的有序序列，對這些軌跡數據進行統計即可得到路網中各個路段的軌跡流量。以北京某街區為例，圖1（a）為該街區道路示意圖，圖1（b）為該示意圖上的車輛軌跡數據樣例。經統計得到的軌跡流量圖如圖2（a）所示。圖2（a）中節點和邊分別對應圖1（a）中的各個路口和街道，邊上的權值代表了相應路段的軌跡流量。接下來，在差分隱私機制下，向圖2（a）中的邊權值添加符合拉普拉斯分布的噪聲以保護用戶隱私。添加噪聲后的流量圖如圖2（b）所示。不難發現，由于拉普拉斯噪聲的引入導致了某些路口出入流量不一致的問題。如B路口所示（非起止路口），添加噪音擾動前車輛駛入該路口的次數等于駛出該路口的次數，如圖2（a）都為3；添加噪音擾動后，該路口的駛入車次為4，駛出車次為3。這顯然與實際情況不符。深入研究發現，不一致問題不僅導致發布結果不符合實際，同時也增大了發布誤差。為此，本文提出了一種一致性調節方案來解決上述問題。

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

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

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

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

（1）將實際城市路網抽象成有向圖模型，并向圖中引入一個輔助的虛擬節點。利用該虛擬節點形式化表現了流量圖中的不一致性問題。

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

（3）在（2）的基礎上提出一致性調節算法。該算法在嚴格的理論分析和公式推導下有效地解決了一致性問題，并提升了發布精度。

（4）在真實路網上對本文所提算法進行實驗驗證，結果表明一致性調節算法減小了約13%的發布誤差且具有處理大規模數據的能力。

2 相關工作

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

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

3 預備知識

3.1 基本概念

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

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

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

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

現實中的任何軌跡經過預處理后均是Ω中的一個元素。本文所用的軌跡數據集D是Ω的子集。根據軌跡數據集D和路網即可構建軌跡流量圖。軌跡流量圖定義如下。

定義3（軌跡流量圖）根據軌跡數據集D計算出路網中每條邊的權值，由此構成的有向加權圖即為軌跡流量圖。邊u→v的權值表示軌跡數據集D中經過邊u→v的軌跡數量。軌跡流量圖中各個邊的權值構成的流量矩陣記為。W即為本文發布的軌跡流量圖。以下簡稱流量圖。

3.2 差分隱私

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

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

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

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

4 軌跡流量圖發布

流量圖的發布過程包括兩步：（1）生成差分隱私流量圖，即統計路網中各路段的流量值并添加獨立同分布的拉普拉斯噪音；（2）一致性調節，即對（1）中的流量圖進行出入流量一致性調節。下面分別描述這兩個過程。

4.1 差分隱私流量圖

軌跡流量圖中節點的流入流量表示從各個方向駛向該節點的車次，而流出流量表示所有駛離該節點的車次。通過觀察分析不難發現，當節點不是任何軌跡的起止點時，該節點的出入流量相等。為此，本文引入一個虛擬節點pv，并讓該虛擬節點作為所有軌跡的起止點，使軌跡變為首尾相連的環，且虛擬節點與路網中每個節點都相連。虛擬節點的引入使得流量圖中所有節點（包括虛擬節點）的出入流量都相等且不會影響真實流量圖中各邊的統計值。沒有特殊說明，下文中的路網鄰接矩陣M和流量矩陣W中均包含了虛擬節點。

4.1.1 差分隱私流量圖算法

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

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

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

算法1軌跡流量圖發布

輸入：軌跡數據集D，鄰接矩陣M，隱私預算ε。

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

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

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

對其進行推導可得：

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

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

由于算法1對軌跡流量圖中的每條邊獨立加噪，因此破壞了路網中節點出入流量相等的特性。針對這個問題，下面將通過二次規劃求解，對算法1進行一致性調節。

4.2 一致性調節算法

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

分別記一致性調節前后的流量矩陣為和，其元素分別表示為ij和ij。經分析發現，由得到的過程可轉化為求解凸優化表達式（6）：

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

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

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

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

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

將式（11）對X求導，得到：

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

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

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

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

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

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

根據上述推導，最終得到一致性調節算法。

算法2一致性調節算法

輸入：添加噪聲保護的流量圖，路網矩陣M。

輸出：一致性調節后的流量圖。

為保證算法效率，上述算法中的矩陣均采用系數矩陣存儲并采用相關算法進行解釋，具體過程文本不做進一步討論。算法2的實現過程中采用了稀疏矩陣的數據結構及相關算法。關于稀疏矩陣的算法已經有諸多研究以及API的支持。本文在第5章提供了該算法的實現源碼下載網址，供讀者參考。

5 實驗分析

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

Table 2 Details of road network and trajectory表2 路網及軌跡信息

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

Fig.3 Relative error圖3 相對誤差

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

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

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

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

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

Fig.7 Run time圖7 算法耗時

6 結束語

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