基于行駛特征的軌跡壓縮技術(shù)*

江俊文，張　凱，王曉玲，金澈清

華東師范大學 數(shù)據(jù)科學與工程研究院，上海 200062

基于行駛特征的軌跡壓縮技術(shù)*

江俊文，張凱，王曉玲+，金澈清

華東師范大學 數(shù)據(jù)科學與工程研究院，上海 200062

軌跡壓縮；行駛特征；自信息量；馬爾可夫序列

1　引言

近年來，隨著移動設(shè)備的普及和定位服務(wù)的發(fā)展，在很多應(yīng)用中產(chǎn)生了大量的軌跡數(shù)據(jù)。例如，車載GPS設(shè)備連續(xù)采樣車輛在不同時間的位置；在微博、街旁、Foursquare等移動社交網(wǎng)絡(luò)上，用戶的簽到序列可以看作是該用戶的旅游軌跡；公交卡、地鐵卡的刷卡記錄顯示了人們何時何地上車或下車，組成人們的出行軌跡。

基于位置的服務(wù)（location-based services，LBS）需要處理大量的軌跡數(shù)據(jù)，比如路線規(guī)劃、時間預(yù)測等。但是海量軌跡數(shù)據(jù)為基于位置的服務(wù)帶來了許多新的挑戰(zhàn)：（1）數(shù)據(jù)規(guī)模快速膨脹，導致數(shù)據(jù)存儲面臨著巨大壓力；（2）基于海量軌跡數(shù)據(jù)的查詢和數(shù)據(jù)分析性能降低；（3）數(shù)據(jù)的收集和傳輸會帶來誤差和冗余，從而影響服務(wù)器的響應(yīng)速度。

以車輛行駛軌跡為例，上海、北京等地的出租車上裝載的GPS設(shè)備，每隔幾分鐘、幾十秒甚至幾秒鐘就會采樣出租車的行駛狀態(tài)，并傳送給服務(wù)器。司機的行駛路線、行駛習慣直接反應(yīng)了城市的交通狀況，并且為人們的出行提供依據(jù)。

諸多車輛所產(chǎn)生的軌跡數(shù)據(jù)對存儲和查詢都帶來了巨大的挑戰(zhàn)。以前的軌跡壓縮算法[1-13]主要關(guān)注軌跡的空間和時間，卻很少關(guān)注車輛的速度和方向信息。盡管已有的方法能夠有效地減小數(shù)據(jù)量，但是也會損失速度和方向的信息。例如查詢車輛在某一段路程中的速度變化模式，利用已有的壓縮方法壓縮后的軌跡是無法支持的。鑒于此，本文提出了一種新的壓縮方法Mixture Compression（MC），通過訓練樣本得到車輛的行駛特征，然后根據(jù)這些特征為每個軌跡點賦予信息量的值，從而篩選軌跡點。

本文的主要貢獻如下：

（1）挖掘軌跡的行駛特征，分析速度變化、方向變化和路網(wǎng)距離的分布規(guī)律，使用高斯分布來擬合特征的分布。

（2）把軌跡建模為馬爾可夫序列，根據(jù)高斯分布來估計軌跡點出現(xiàn)的概率，從而計算出各軌跡點的信息量。

（3）提出軌跡壓縮算法Mixture Compression，并在真實數(shù)據(jù)集上進行驗證，表明了新算法的有效性。

本文組織結(jié)構(gòu)如下：第2章回顧了已有的軌跡數(shù)據(jù)壓縮工作；第3章定義了待解決的問題；第4章具體描述了新的軌跡壓縮算法；第5章展示了基于真實數(shù)據(jù)集的實驗效果；第6章總結(jié)全文，并展望了未來的工作方向。

2　相關(guān)工作

首先回顧已有的軌跡壓縮技術(shù)，然后再介紹信息論的相關(guān)概念。

2.1軌跡壓縮

現(xiàn)有的軌跡壓縮工作主要有兩方面：一是線段簡化方法；二是基于路網(wǎng)的壓縮方法。

2.1.1線段簡化技術(shù)

線段簡化的主要思想是通過設(shè)定一個誤差閾值，來削減軌跡中GPS點的數(shù)目。這類技術(shù)都是基于歐氏空間的，誤差用歐氏空間距離來度量。線段簡化方法又分為兩類，離線壓縮和在線壓縮。

（1）離線壓縮。離線壓縮是指線下壓縮歷史軌跡數(shù)據(jù)。Douglas-Peucker（DP）[1]算法使用若干條線段來近似原始軌跡，并且保證產(chǎn)生最小的誤差。誤差度量是垂直歐氏距離。整個算法的時間復(fù)雜度為O(N2)，N為原始軌跡中點的數(shù)目。文獻[2]借助外部存儲結(jié)構(gòu)把算法的時間性能提高到O(N×lbN)。DP算法只考慮了空間距離，沒有考慮時間因素，因此在文獻[3]中提出時間比率距離，計算原始軌跡和近似軌跡中擁有相同時間戳的兩個點的歐氏距離，并把它應(yīng)用在TD-TR（top-down time-ratio）算法中，獲得了更精確的近似軌跡。算法的時間復(fù)雜度仍然為O(N2)。

（2）在線壓縮。離線壓縮能夠獲得更好的近似軌跡，因為它把整條軌跡都考慮在內(nèi)，但是這類方法的時間復(fù)雜度都較高。因此許多新的技術(shù)考慮到在線壓縮方法。文獻[4]提出了Sliding Window和Open Window兩種在線壓縮方法。這類方法主要思想是初始化一個大小為1的窗口，并逐步增加窗口的大小，把后續(xù)的GPS點包含在內(nèi)，并用一條直線段來近似窗口內(nèi)的軌跡，如果誤差大于預(yù)先設(shè)定的誤差閾值，那么把引起最大誤差的點或者該點的前一個點加入近似軌跡，并以這個點作為下一個窗口的起點。在文獻[5]中，Thresholds算法借助速度和方向，構(gòu)建了一個扇環(huán)形的安全區(qū)域，如果接下來的一個點落在安全區(qū)域內(nèi)，就省略這個點，否則就把該點加入近似軌跡。文獻[14]提出SQUISH（spatial quality simplification heuristic）方法，借助優(yōu)先隊列，逐步加入軌跡點，當隊列溢出時，刪除誤差最小的點。SQUISH-E[15]優(yōu)化了SQUISH算法的誤差無上界的缺陷，能在給定的誤差閾值內(nèi)，達到最優(yōu)的壓縮率。

2.1.2基于路網(wǎng)結(jié)構(gòu)的技術(shù)

線段簡化方法是基于歐氏空間的，而車輛的運動要受到路網(wǎng)結(jié)構(gòu)的約束，因此線段簡化方法在車輛軌跡壓縮上有很大的局限性。而基于路網(wǎng)結(jié)構(gòu)的壓縮方法能避免這些問題。文獻[6]提出了Nonmaterial方法，記錄了經(jīng)過交叉口的時間和順序，來取代原始的GPS點。文獻[7]使用邊來描述軌跡，如果司機從A點到B點行駛的是它們之間的最短路徑，那么只需要保存頭尾兩條邊即可。盡管這種方法可以用更少的邊來代替大量GPS點，但是卻丟失了時間、速度和方向的信息，因此壓縮后的數(shù)據(jù)僅能支持有限的查詢。文獻[8-9]的目標是找到最優(yōu)的壓縮路徑，并結(jié)合最小描述長度（minimum description length，MDL）的方法，把壓縮問題轉(zhuǎn)化為目標函數(shù)的最優(yōu)化問題。這種方法無法解決帶環(huán)的軌跡，并且如果路網(wǎng)結(jié)構(gòu)很復(fù)雜的話，算法的時間復(fù)雜度會很高。文獻[10]發(fā)現(xiàn)每條路段上的車流量是不均勻的，有些路段車輛經(jīng)過很頻繁，而有些路段卻很少有車輛經(jīng)過。因此可以利用這個信息把整條軌跡分解為幾段子軌跡，并根據(jù)路段出現(xiàn)的頻率進行哈夫曼編碼，每條軌跡就轉(zhuǎn)化為編碼的序列，從而顯著減少空間。但是這種方法在使用之前有解壓縮的步驟。文獻[11]和[12]提出了語義壓縮，把一條軌跡轉(zhuǎn)化為若干個帶語義的事件和地點。這種方法會花費更多的壓縮時間，并且需要解壓才能支持上層應(yīng)用。文獻[16]從路網(wǎng)結(jié)構(gòu)和軌跡中提取了6個特征，根據(jù)這些特征把軌跡切分為子軌跡段，然后用這些特征來描述每段內(nèi)的行駛狀態(tài)。這種提取出的摘要軌跡不僅很好地記錄了軌跡的運行蹤跡，也便于人們理解。

2.2信息論相關(guān)概念

信息論常用來研究信息的傳輸、提取和壓縮的問題。本文把軌跡和軌跡點的重要性用信息論中的信息量進行衡量。

車輛在行駛過程中，相鄰的軌跡點有影響關(guān)系，也就是說一個軌跡點的狀態(tài)是受它前面的軌跡點影響的。統(tǒng)計發(fā)現(xiàn)，軌跡點只與它前一個軌跡點的狀態(tài)有關(guān)，而與更前面的軌跡點無明顯關(guān)系，表明軌跡符合馬爾可夫序列的特征，從而可以被建模成馬爾可夫序列。本文利用馬爾可夫序列的特性來解決軌跡壓縮的問題。

假設(shè)在馬爾可夫序列中，信號x的出現(xiàn)依賴信號y，因此在y的基礎(chǔ)上x發(fā)生的條件概率為Pr(x|y)，此時信號x的條件自信息量為I(x|y)，定義公式如下：

式（1）表示在信號x包含的信息量與x發(fā)生的概率成反比。也就是說，在y的基礎(chǔ)上，x發(fā)生的概率越小，包含的信息量越高。相反，如果x發(fā)生的概率越大，則包含的信息量越低。

條件自信息量用來描述離散隨機變量的信息度量，也可以套用在軌跡點上。下文會具體闡述如何描述軌跡點的信息量。

3　問題定義

其中，T表示任意一條軌跡；|T|表示軌跡的長度；I(pi)表示軌跡點pi的信息量。

綜上所述，本文的問題定義如下：給定一條軌跡T，找到一條壓縮后的軌跡T′，使得T′滿足用戶給定的閾值，盡可能保留原始軌跡的特征，并具有最大的軌跡信息量。

壓縮后的軌跡的信息量由式（3）計算。

本章定義了待解決的問題和相關(guān)概念。

定義1（軌跡點）車輛在某時刻的行駛狀態(tài)：

其中，time表示采樣時間；latitude、longitude表示車輛所在的緯度和經(jīng)度；speed表示車輛的速度；direction表示車輛的行駛方向。

定義2（軌跡T）表示車輛的運動蹤跡，用一條軌跡點的序列來表示：

其中，object ID表示車輛的標識號；trajectory ID是軌跡的標識號；pi表示一個軌跡點。

定義3（軌跡點信息量）表示軌跡點的重要性度量。每個軌跡點即是馬爾可夫序列中的一個信號，假設(shè)一個軌跡點為 pi，pi受 pi-1的影響，在 pi-1的基礎(chǔ)上，pi的概率為Pr(pi|pi-1)。根據(jù)信息論中的信息量概念，定義pi的信息量如下：

規(guī)則1一個軌跡點在已知條件下出現(xiàn)的概率越低，則該軌跡點的信息量就越大，該軌跡點更值得保留。

第4章會詳細闡述如何運用規(guī)則1計算行駛特征的信息量。

定義4（軌跡信息量）軌跡中所有軌跡點的信息量的總和。計算公式如下：

4　基于行駛特征的壓縮方法

本章介紹一種新的軌跡壓縮方法，從歷史軌跡數(shù)據(jù)中挖掘司機的行駛特征，分析特征的分布情況。在此基礎(chǔ)上，量化每個軌跡點在各個特征上的信息量和總信息量，選出符合預(yù)先設(shè)定的閾值的點集合，組成體現(xiàn)軌跡特征的壓縮軌跡。

在車輛軌跡中，用戶感興趣的是車輛的速度、方向和位置信息。GPS設(shè)備的采樣頻率不定，若3 s采樣一次，那么一條軌跡包含緊密的軌跡點，因此數(shù)據(jù)量很大并且包含大量的冗余數(shù)據(jù)。對軌跡數(shù)據(jù)進行壓縮時，應(yīng)盡可能保留體現(xiàn)原始軌跡特征的點，并盡可能減少所帶來的誤差。因此本文對車輛行駛特征，包括速度、方向和位置進行分析，通過這3個維度共同決定軌跡點是否值得保存。

4.1行駛特征的分布

車輛行駛特征是基于2013年10月的某市出租車數(shù)據(jù)挖掘的。從數(shù)據(jù)集中隨機采集500條、1 000條和2 000條軌跡，分別來自不同的司機和不同的時間段，如圖1~圖3所示。

4.1.1速度特征

車輛的速度及其變化對研究城市交通狀況很有價值，因此壓縮后的軌跡需要保存具有代表性的速度信息的點。

本文將軌跡建模為馬爾可夫序列，每個軌跡點只與它前一個軌跡點有關(guān)，研究相鄰兩個點速度的變化情況。圖1展示了500條、1 000條和2 000條軌跡的分布，可以看出它們都呈現(xiàn)為高斯分布，因而可以用高斯分布來模擬速度變化分布。

4.1.2方向特征

車輛的方向和速度共同決定車輛的位置，并且方向的改變對車輛的運動狀態(tài)具有重要的表征作用。而單獨的方向并不能表現(xiàn)車輛行駛的變化，因此壓縮后的軌跡要包含具有代表性的方向信息的軌跡點。

與速度類似，本文研究相鄰點方向的變化情況。圖2展示了500條、1 000條和2 000條軌跡的結(jié)果分布，可以看出方向變化也表現(xiàn)出類似高斯分布的特性，并且在0的偏右位置達到峰值。因此也可用高斯分布去模擬方向變化的分布。

Fig.1　Velocity difference statistical figures of 500,1 000 and 2 000 trajectories圖1　軌跡數(shù)分別為500、1 000、2 000時速度差值的統(tǒng)計圖

Fig.2　Direction difference statistical figures of 500,1 000 and 2 000 trajectories圖2　軌跡數(shù)分別為500、1 000、2 000時方向差值的統(tǒng)計圖

Fig.3　Network distance statistical figures of 500,1 000 and 2 000 trajectories圖3　軌跡數(shù)分別為500、1 000、2 000時路網(wǎng)距離差值的統(tǒng)計圖

速度和方向代表車輛的行駛狀態(tài)，而根據(jù)之前的闡述，速度變化和方向變化都呈現(xiàn)高斯分布，并且在y軸的附近達到峰值。根據(jù)高斯分布的特征，知道速度和方向在大概率情況下是變化很小的，而在小概率情況下會變化很大。因此可以假設(shè)車輛在運動過程中，速度、方向的變化呈現(xiàn)高斯分布。

4.1.3位置特征

位置信息是軌跡中最重要的數(shù)據(jù)，幾乎所有的查詢都會涉及到位置信息。因此壓縮后的軌跡必須要盡可能保留準確的時空信息。

在挖掘位置特征之前，首先假設(shè)在兩個軌跡點之間，車輛是勻速行駛的，則可把前一個點的瞬時速度當作下一段軌跡的平均速度。車輛所在的位置是由前一個點的速度和方向共同決定的。因此可以通過速度和方向預(yù)測下一個點的位置。盡管預(yù)測點的位置和實際采樣到的點的位置會存在距離，但是可以對這兩者之間的距離進行建模。

假設(shè)在 pi點，已知 pi的速度vi和方向di，根據(jù)速度和方向預(yù)測到的下一個點的位置為p′i+1，實際的下一個點的位置為 pi+1。計算得到預(yù)測點 p′i+1和實際點pi+1之間的路網(wǎng)距離為lpp′。

如果lpp′越小，說明預(yù)測得越準確，刪除實際點對軌跡帶來的誤差就越小。如果lpp′越大，說明預(yù)測得越不準確，刪除這個點帶來的誤差就越大。

圖3顯示了500條、1 000條和2 000條軌跡的分布情況?？梢钥闯觯琹pp′的分布呈現(xiàn)高斯分布的特征，因此使用高斯分布去擬合lpp′的分布。

由以上分析可知，車輛的行駛軌跡有3個重要特征，速度、方向和位置。這些特征能充分刻畫軌跡的輪廓，并描述車輛的運動狀態(tài)。簡單的速度、方向和位置信息并沒有明顯的分布規(guī)律，而軌跡符合馬爾可夫序列的特性，因此軌跡點的速度、方向和位置相對于前一個軌跡點的變化是有規(guī)律的。從數(shù)據(jù)集中發(fā)現(xiàn)，速度變化、方向變化和位置變化呈現(xiàn)高斯分布，通過高斯分布擬合這種規(guī)律，就可以量化軌跡點的速度、方向和位置出現(xiàn)的概率值。計算公式為：

其中，x表示速度變化、方向變化或位置變化。

4.2行駛特征信息量

下面通過例1來說明信息量的計算過程。

例1如圖4所示，假設(shè)有一條軌跡T={p0,p1,p2, p3,p4}，各個軌跡點落在不同的路段上，如黑色實心點所示。其中車輛在p0的速度為v0、方向為d0和經(jīng)緯度為(x0,y0)，p1點是否保留需要通過考察 p1點的概率和信息量來決定。根據(jù)假設(shè)1車輛在p0p1以速度v0勻速運動，結(jié)合兩點之間的時間信息，可以計算得到在這段時間內(nèi)車輛行駛的路程，從而預(yù)測p1的位置在 p1′（紅色空心點）處，p1′的經(jīng)緯度位置為(x1′,y1′)。實際采樣到的 p1的經(jīng)緯度為(x1,y1)。實際點 p1與預(yù)測點p1′之間的路網(wǎng)距離為lp1p1′。軌跡點 p1的速度和方向分別為v1和d1。因此p1相對于軌跡點p0的速度變化為v1-v0，方向變化為d1-d0。

Fig.4　Trajectory example圖4軌跡示例

由于速度變化、方向變化和路網(wǎng)距離均符合高斯分布，由式（4）可以計算得到 p1點在p0的基礎(chǔ)上的速度、方向和位置的概率值。

以Iv表示速度維度的信息量，Id表示方向維度的信息量，Il表示位置維度的信息量。根據(jù)式（2）和（4）可得：

根據(jù)式（5）～（7）計算速度變化、方向變化和位置距離的信息量。事實上如果速度變化、方向變化越小，預(yù)測點和實際點位置的路網(wǎng)距離越小，那么概率值越大，則信息量越低。

軌跡點的總信息量由如下公式計算：

即軌跡點的總信息量等于它各個特征的信息量的權(quán)重和，其中α+β+γ=1。α、β和γ可以調(diào)節(jié)3個特征量的權(quán)重，權(quán)重越大的特征，表明用戶更在意該特征，壓縮后的數(shù)據(jù)也偏向于該特征，因此這3個值由用戶自定義。在本文的實驗中，為了表示速度、方向和位置特征具有相同的重要性，設(shè)置α、β和γ都為1/3。

用戶設(shè)置的閾值可以幫助篩選合適的軌跡點?？梢岳盟俣茸兓拈撝?、方向變化的閾值和路網(wǎng)距離的閾值來計算信息量的閾值。但是設(shè)定3個閾值帶來的不僅僅是參數(shù)增多，更重要的是如何設(shè)置3個閾值的大小能控制這3個特征具有相同的影響力，而不會導致篩選出的軌跡點只體現(xiàn)了某一個特征。本文設(shè)置一個閾值δ來代替速度變化、方向變化和路網(wǎng)距離的閾值。δ表示在高斯分布中距離期望最遠的兩端的面積。根據(jù)高斯分布的面積公式，可以計算得到自變量的范圍，即速度變化、方向變化和路網(wǎng)距離的閾值。LBS服務(wù)對軌跡數(shù)據(jù)的精確性要求是各不相同的，有的服務(wù)需要非常精確的軌跡數(shù)據(jù)，而有些服務(wù)可以容忍部分信息的丟失，但要求較快的查詢速度。因此，針對不同的應(yīng)用，用戶可以設(shè)定合適的閾值來篩選出最合適的壓縮軌跡。

4.3基于行駛特征的軌跡壓縮算法

本文提出的行駛特征的軌跡壓縮方法Mixture Compression，根據(jù)輸入的參數(shù)可以分為兩種：算法1的輸入是原始軌跡ST和用戶自定義閾值δ；算法2的輸入是原始軌跡ST和用戶設(shè)定壓縮率cr。

算法1 MC(ST,δ)

輸入：軌跡集合ST，閾值δ∈[0,1]。

輸出：壓縮后的軌跡集合ST′。

1.從軌跡集合中隨機選取2 000條軌跡，訓練得到速度、方向和路網(wǎng)距離的高斯分布參數(shù)

2.根據(jù)閾值δ和高斯函數(shù)計算信息量閾值Iδ

3.初始化數(shù)組T′

4.for eachST中軌跡Tdo

5.把T的起點加入到壓縮軌跡T′中

6.for each軌跡點pi(1

7.計算pi在pi-1基礎(chǔ)上的速度差、方向差和距離差

8.計算pi的條件自信息量I(pi)

9.If（I(pi)>Iδ） then

10.把pi加入T′中

11.End for

12.把T的終點加入到壓縮軌跡T′中

13.把T′加入集合ST′中

14.清空T′

15.End for

16.returnST′

首先從軌跡集合中隨機選取2 000條軌跡作為訓練集（第1行），計算得到速度、方向和位置特征的高斯分布函數(shù)，訓練步驟是離線處理的，并且計算一次后，可以保存下來并持續(xù)使用。值得注意的是，本文實驗采用的是某市出租車軌跡數(shù)據(jù)集，因此這組訓練參數(shù)，只適合該數(shù)據(jù)集。對于其他類型的數(shù)據(jù)集，例如公交車的軌跡數(shù)據(jù)集，需要利用公交車的數(shù)據(jù)集訓練出適合公交車軌跡的參數(shù)。然后，用戶預(yù)先設(shè)定一個閾值（第2行），結(jié)合高斯分布函數(shù)，計算得到速度、方向和位置變化的閾值，并最終計算出軌跡點的信息量閾值Iδ。對于每條軌跡T，先把軌跡的起點加入到壓縮軌跡T′中（第4~5行）。從第二個軌跡點開始（第6~11行），計算它與前一個點的速度變化、方向變化和路網(wǎng)距離，根據(jù)式（5）~（8）計算該點的信息量I(pi)。如果I(pi)大于Iδ，則保留該點。如果I(pi)小于Iδ，則跳過該軌跡點。接著把T的終點加入T′（第12行）。最終把壓縮后的軌跡T′放入軌跡集合ST′（第13行）。

用戶也可以設(shè)定壓縮率來進行壓縮。當給定壓縮率cr時，需要調(diào)用算法MCCR（mixture compression of compression rate）。

算法2 MCCR(ST,cr)

輸入：軌跡集合ST，壓縮率cr∈[0,1]。

輸出：壓縮后的軌跡集合ST′。

1.從軌跡集合中隨機選取2 000條軌跡，訓練得到速度、方向和路網(wǎng)距離的高斯分布參數(shù)

2.初始化數(shù)組T′和temp

3.for eachST中軌跡Tdo

4.把T的起點加入到壓縮軌跡T′中

5.for each軌跡點pi(1

6.計算pi在pi-1基礎(chǔ)上的速度差、方向差和距離差

7.計算pi的條件自信息量I(pi)

8.將二元組加入temp中

9.End for

10.根據(jù)I(pi)對temp遞減排序

11.選取temp中前temp.length*cr個軌跡點加入壓縮后的軌跡T′中

12.把T的終點加入到壓縮軌跡T′中

13.把T′加入集合ST′中

14.清空T′和temp

15.End for

16.returnST′

算法2從第3行開始，對每條軌跡的每個軌跡點，計算軌跡點的自信息量，并加入到數(shù)組temp中（第5~8行）。對temp依據(jù)自信息量進行遞減排序，選取出前temp.length*cr個軌跡點加入T′（第10~12行）。最后把T′加入集合ST′。

5　實驗結(jié)果與分析

本文通過實驗來驗證Mixture Compression算法的有效性?；谛旭偺卣鞯能壽E壓縮思想在本文中第一次提出，Mixture Compression算法在壓縮數(shù)據(jù)量的同時，也保證了壓縮后的軌跡具有原始軌跡的特征。為了體現(xiàn)新算法的有效性，選取了兩個Baseline算法進行對比，DP（Douglas-Peucker）算法[1]和Thresholds算法[5]。DP算法和Thresholds算法都屬于線段簡化技術(shù)，DP只考慮了距離因素，Thresholds考慮了速度和方向的因素，而Mixture Compression考慮了速度、方向和距離因素。

首先介紹了實驗的數(shù)據(jù)集和運行環(huán)境。其次比較了Mixture Compression算法和Baseline方法的壓縮率。最后比較了Mixture Compression算法和Baseline方法的誤差。

5.1實驗設(shè)置

本文采用真實的出租車軌跡數(shù)據(jù)構(gòu)建實驗。數(shù)據(jù)集是2013年10月某市出租車軌跡數(shù)據(jù)，大小約為2 GB。每一行記錄表示車載GPS采樣到的出租車信息，包含經(jīng)緯度、速度、方向、載客狀態(tài)信息。軌跡的采樣間隔不同，為十幾秒至幾分鐘不等。為了降低軌跡數(shù)據(jù)的差錯率，首先進行了Map-Matching預(yù)處理。

本文的實驗代碼用Java編寫，運行在配置2.0 GHz Intel Xeon處理器、16 GB內(nèi)存的64位Windows 8操作系統(tǒng)上。為了進行性能對比，本文實現(xiàn)了DP算法[1]和Thresholds[5]算法。DP算法原來工作于歐氏空間內(nèi)，使用垂直歐氏距離作為距離函數(shù)。本文則使用路網(wǎng)距離作為距離函數(shù)。Thresholds算法考慮速度和方向信息來構(gòu)造安全區(qū)域，以過濾掉落在安全區(qū)域里面的軌跡點。

本文主要從壓縮率和誤差兩方面進行評測。閾值從0.1到1.0逐步增加，比較Mixture Compression 和Baseline算法的壓縮效果。相同閾值情況下，如果壓縮率越小，則說明算法越有效。本文使用速度誤差、方向誤差和距離誤差來衡量壓縮軌跡的誤差。在壓縮率不變時，比較不同算法的誤差。

5.2壓縮率比較

本實驗比較相同閾值下的壓縮率。壓縮率（compression rate，CR）的計算公式如下：

其中，|T′|表示壓縮后的軌跡的長度；|T|表示原始軌跡的長度。顯然，|T′|<|T|。

從圖5可知，隨著閾值的增加，壓縮率也逐漸增加。與兩種Baseline技術(shù)相比較，在相同的閾值條件下，Mixture Compression的壓縮率更小。例如當閾值為0.1時，Mixture Compression比Baseline方法的壓縮率好5~6倍，也就是說壓縮后的數(shù)據(jù)大小是Baseline方法的1/5到1/6。Mixture Compression比Baseline方法的平均壓縮效果要好4倍左右。值得注意的是，在閾值為1.0的條件下，Mixture Compression比Baseline方法要好一些。這是因為出租車在行駛過程中，遇到紅燈或者上下客時會停車，Mixture Compression能壓縮這部分數(shù)據(jù)。

Fig.5　Compression rate圖5 壓縮率比較

5.3誤差比較

本實驗評測不同壓縮算法的誤差情況。鑒于軌跡需要同時考慮空間、時間、速度和方向等信息，因此使用平均時間同步速度誤差（average time synchronized velocity distance，ATSVD）、平均時間同步方向誤差（average time synchronized direction distance，ATSDD）和平均時間同步的路網(wǎng)距離（average time synchronized network distance，ATSND）作為誤差衡量。時間同步的兩點是指壓縮后的軌跡中與原始軌跡中時間匹配的點。ATSVD是指兩條軌跡中所有時間同步的兩點的速度誤差的平均值。ATSDD是指兩條軌跡中所有時間同步的兩點的方向誤差的平均值。ATSND是指兩條軌跡中所有時間同步的兩點之間的路網(wǎng)距離的平均值。計算公式如下所示：

圖6~圖8展示了基于真實數(shù)據(jù)集的實驗結(jié)果。可以發(fā)現(xiàn)隨著壓縮率增大，每種方法的誤差都逐漸減小。這是因為如果壓縮后的數(shù)據(jù)越大，那么它跟原始軌跡相差就越小，所以平均速度誤差、平均方向誤差和平均路網(wǎng)距離也越小。此外，在各種情況下，Mixture Compression的誤差均低于對比算法，表示Mixture Compression方法更優(yōu)。比如壓縮率為30%的時候，Mixture Compression的平均速度誤差為4 km/h，平均方向誤差為35°，平均路網(wǎng)誤差只有80 m，均優(yōu)于DP算法和Thresholds算法，約為它們的1/4到1/2。而當壓縮率達到40%以上，Mixture Compression的誤差是DP或者Thresholds的1/3，甚至是1/10。隨著壓縮率的增大，Mixture Compression在誤差方面的優(yōu)勢更明顯。

Fig.6　Average velocity error圖6　平均速度誤差比較

Fig.7　Average direction error圖7 平均方向誤差比較

Fig.8　Average network distance error圖8　平均距離誤差比較

6　結(jié)束語

本文提出了一種軌跡壓縮技術(shù)，綜合考慮了位置、速度、方向等信息。本文方法采用馬爾可夫模型對軌跡建模，繼而從速度變化、方向變化和路網(wǎng)距離維度上考察其分布。最終借助高斯分布來預(yù)測軌跡下一個點的狀態(tài)，并賦予一個信息量值來表示這個點的重要性。實驗結(jié)果表明本文方法在壓縮率和精度上具有優(yōu)勢，能有效地壓縮軌跡。未來可以研究基于行駛特征的查詢。

References:

[1]Douglas D H,Peucker T K.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].Cartographica:The International Journal for Geographic Information and Geovisualization,1973,10 (2):112-122.

[2]Hershberger J E,Snoeyink J.Speeding up the Douglas-Peucker line-simplification algorithm[D].University of British Columbia,Department of Computer Science,1992.

[3]Meratnia N,de By R A.Spatiotemporal compression techniques for moving point objects[C]//LNCS 2992:Proceedings of the 9th International Conference on Extending Database Technology,Heraklion,Greece,Mar 14-18,2004. Berlin,Heidelberg:Springer,2004:765-782.

[4]Keogh E,Chu S,Hart D,et al.An online algorithm for segmenting time series[C]//Proceedings of the 2001 IEEE International Conference on Data Mining,San Jose,USA,Nov 29-Dec 2,2001.Piscataway,USA:IEEE,2001:289-296.

[5]Potamias M,Patroumpas K,Sellis T.Sampling trajectory streams with spatiotemporal criteria[C]//Proceedings of the 18th International Conference on Scientific and Statistical Database Management,Vienna,Austria,Jul 3-5,2006.Piscataway,USA:IEEE,2006:275-284.

[6]Lerin P M,Yamamoto D,Takahashi N.Encoding travel traces by using road networks and routing algorithms[M]//Intelligent Interactive Multimedia:Systems and Services.Berlin, Heidelberg:Springer,2012:233-243.

[7]Kellaris G,Pelekis N,Theodoridis Y.Trajectory compression under network constraints[M]//Advances in Spatial and Temporal Databases.Berlin,Heidelberg:Springer,2009: 392-398.

[8]Kellaris G,Pelekis N,Theodoridis Y.Map-matched trajectory compression[J].Journal of Systems and Software,2013,86 (6):1566-1579.

[9]Song Renchu,Sun Weiwei,Zheng Baihua,et al.PRESS:a novel framework of trajectory compression in road networks[J].Proceedings of the VLDB Endowment,2014,7 (9):661-672.

[10]Muckell J,Hwang J H,Lawson C T,et al.Algorithms for compressing GPS trajectory data:an empirical evaluation [C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems,San Jose,USA,Nov 2-5,2010.New York,USA:ACM, 2010:402-405.

[11]Schmid F,Richter K F,Laube P.Semantic trajectory compression[M]//Advances in Spatial and Temporal Databases. Berlin,Heidelberg:Springer,2009:411-416.

[12]Richter K F,Schmid F,Laube P.Semantic trajectory compression:representing urban movement in a nutshell[J]. Journal of Spatial Information Science,2012(4):3-30.

[13]Cao Hu,Wolfson O.Nonmaterialized motion information in transport networks[C]//LNCS 3363:Proceedings of the 10th International Conference on Database Theory,Edinburgh,UK,Jan 5-7,2005.Berlin,Heidelberg:Springer,2005: 173-188.

[14]Muckell J,Hwang J H,Patil V,et al.SQUISH:an online approach for GPS trajectory compression[C]//Proceedings of the 2nd International Conference on Computing for Geospatial Research&Applications,Washington,Jul 1-3,2012. New York:ACM,2011.

[15]Muckell J,Olsen P W,Hwang J H,et al.Compression of trajectory data:a comprehensive evaluation and new approach[J].Geoinformatica,2014,18(3):435-460.

[16]Su Han,Zheng Kai,Zeng Kai,et al.Making sense of trajectory data:a partition-and-summarization approach[C]//Proceedings of the 2015 IEEE 31st International Conference on Data Engineering,Seoul,Apr 13-17,2015.Piscataway,USA: IEEE,2015:963-974.

JIANG Junwen was born in 1991.He is an M.S.candidate at East China Normal University.His research interests include databases and data mining.

江俊文（1991—），男，浙江衢州人，華東師范大學碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)庫，數(shù)據(jù)挖掘。

ZHANG Kai was born in 1992.He is an M.S.candidate at East China Normal University.His research interests include databases and data mining.

張凱（1992—），男，上海人，華東師范大學碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)庫，數(shù)據(jù)挖掘。

WANG Xiaoling was born in 1975.She is a professor and Ph.D.supervisor at East China Normal University,and the member of CCF.Her research interests include Web services and Web data management.

王曉玲（1975—），女，山東煙臺人，華東師范大學教授、博士生導師，CCF會員，主要研究領(lǐng)域為Web服務(wù)，數(shù)據(jù)管理技術(shù)。

JIN Cheqing was born in 1977.He is a professor and Ph.D.supervisor at East China Normal University,and the member of CCF.His research interests include data stream,location-based services and uncertain data management.

金澈清（1977—），男，浙江成縣人，華東師范大學教授、博士生導師，CCF會員，主要研究領(lǐng)域為數(shù)據(jù)流管理，基于位置的服務(wù)，不確定數(shù)據(jù)管理。

Trajectory Compression Based on Moving Features?

JIANG Junwen,ZHANG Kai,WANG Xiaoling+,JIN Cheqing
Institute for Data Science and Engineering,East China Normal University,Shanghai 200062,China
+Corresponding author:E-mail:xlwang@sei.ecnu.edu.cn

JIANG Junwen,ZHANG Kai,WANG Xiaoling,et al.Trajectory compression based on moving features.Journal of Frontiers of Computer Science and Technology,2016,10(9)：1240-1249.

The popularity of mobile terminals and the development of global positioning system(GPS)produce mass of trajectory data.Based on the data,a lot of location-based services(LBS)provide services for people.However,the increment of trajectory data brings many challenges:huge data volume,long query latency,hard to analyze and data redundancy.Hence the trajectory compression plays an important role for better LBS.This paper proposes a trajectory compression method which fully considers the moving features and handles trajectory as Markov sequence.The moving features include speed,direction and position.Gaussian distributionis used to model speed change,direction change and position distance,so that the status of the next point can be predicated well based on aforementioned information.According to the prediction accuracy,every point in trajectory is given a conditional self-information value.A compressed trajectory is generated by picking those points that satisfy the user-predefined value.Finally,this paper verifies the performance of the proposed compression method through a number of experiments on real datasets.

trajectory compression;moving features;self-information;Markov sequence

移動終端的普及和全球定位系統(tǒng)（global positioning system，GPS）的發(fā)展，產(chǎn)生了海量的軌跡數(shù)據(jù)。許多基于位置的服務(wù)（location-based services，LBS）利用這些軌跡數(shù)據(jù)為用戶提供服務(wù)。但是軌跡數(shù)據(jù)日益增多帶來了許多挑戰(zhàn)：數(shù)據(jù)量巨大，查詢延時增長，數(shù)據(jù)分析困難以及數(shù)據(jù)冗余。軌跡壓縮對于提供更好的服務(wù)是非常有必要的，因此提出了基于行駛特征的軌跡壓縮技術(shù)，考慮了行駛特征，并且把軌跡數(shù)據(jù)建模為馬爾可夫序列。行駛特征包括速度、方向和位置，使用高斯分布對速度變化、方向變化和位置距離進行建模，下一個點的狀態(tài)就能通過之前的信息來進行預(yù)測；根據(jù)預(yù)測的準確度，為每個軌跡點賦予條件自信息量；篩選出滿足用戶設(shè)定準確度閾值的點，組成壓縮后的軌跡。在真實數(shù)據(jù)集上進行了一系列的實驗，證明了算法的性能。

2015-07,Accepted 2015-11.

*The National Natural Science Foundation of China under Grant Nos.61170085,61321064,61370101(國家自然科學基金);the Shanghai Knowledge Service Platform Project under Grant No.ZF1213(上海市知識服務(wù)平臺項目).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-11-24,http://www.cnki.net/kcms/detail/11.5602.TP.20151124.1354.004.html

A

TP311