一種距離誤差可控的DPTS-SP-Prac改進算法

董天放　孟慶彬　舒　奎

1(大連東軟信息學院　遼寧 大連 116023)2(大連工業大學信息科學與工程學院　遼寧 大連 116034)

0　引　言

伴隨著經濟的發展和科技的進步，各種具備定位功能的設備和智能移動終端觸手可及，這些設備每天會產生大量的軌跡數據。這些軌跡數據中隱藏了很多有價值的知識模式，個人的出行軌跡可以反映出一個人的職業特征，通過對城市群體的軌跡進行分析，可以發現城市的熱點區域和對城市的功能區域進行識別[1]。但隨著用戶規模不斷增大，軌跡數據的數量幾乎呈指數趨勢進行增長。據2012年的一篇文獻中的數據表明，以北京市的67 000 輛出租車為例，如果這些出租車以2～3 s頻率向數據中心發送GPS定位數據，僅這些出租車每天就能產生高達60 TB的軌跡數據[2]。海量的軌跡數據給基于位置服務的應用帶來了很多挑戰：(1)這些數據會占據大量的存儲空間；(2)對于在線的應用，傳輸這些數據會消耗大量的網絡流量；(3)當在瀏覽器上展示這些數據時，會給瀏覽器帶來很大的負擔，每繪制1 000個軌跡點就需要約1 s的時間[3]；(4)當軌跡數據的量較大時，會使得軌跡數據的查詢和分析變得困難。因此，在使用軌跡數據前對數據進行壓縮處理就顯得尤為必要。

軌跡壓縮的主要思想是減少軌跡中定位點的數量，同時確保最小化的信息丟失。傳統的軌跡壓縮算，如Douglas-Peucker算法[4]、基于Douglas-Peucker改進的TD-TR算法[5]、最優化的軌跡壓縮算法[6-9]、近似最優化的軌跡壓縮算法[10-11]、基于開放窗口的OPW-TR算法[6]、SQUISH算法[12]以及 SQUISH-E[13]算法僅關注于捕捉軌跡的位置信息，因此在使用這些算法進行軌跡壓縮時易造成軌跡方向信息的丟失。然而，軌跡的方向信息對于描述軌跡的語義起著至關重要的作用，移動對象運動方向的改變暗示了用戶的行為(例如，停留、拍照等)[14]。此外，很多基于位置服務的應用都使了用軌跡的方向信息，例如：地圖匹配[15]、軌跡聚類[16]、軌跡分類[17]以及孤立點檢測[18]。DPTS-SP-Prac算法[19]是一種基于方向保持的軌跡壓縮算法，能夠有效地控制軌跡的方向誤差。由于該算法考慮到了軌跡的方向信息，故相比于傳統的基于位置的軌跡壓縮算法，該算法具有更加廣泛的應用范圍，支持的應用更多。

DPTS-SP-Prac算法雖然能夠有效地捕捉軌跡的方向信息，但該算法的理論最大距離誤差是與壓縮后的軌跡段是相關的，是不可控的。對于某些軌跡進行壓縮后，產生的最大距離誤差可能很大，可能是用戶不能接受的。為了解決這個問題，提高算法的可用性，本文提出了一種距離誤差可控的DPTS-SP-Prac改進算法，這種改進提高了DPTS-SP-Prac的可用性，減小了壓縮誤差，提高了精度，使得軌跡壓縮變得更加準確。

1　軌跡壓縮的相關定義

定義1軌跡：一條長度為n的軌跡T是一系列以時間為順序的定位點的集合，即T={P1,P2,…,Pn-1,Pn}。T中的每一個定位點Pi均由一個三元組組成，其中(xi，yi)為移動對象在ti時刻的位置坐標。

定義2軌跡壓縮：給定一條軌跡T={P1,P2,…,Pn-1,Pn}，軌跡壓縮就是要尋找一系列以時間為順序的定位點的集合T′(T的子集)，即T′={Pc1,Pc2,…,Pc(m-1),Pcm}，其中1=c1

定義3壓縮率：給定原始軌跡T={P1,P2, …,Pn-1,Pn}及其壓縮后的軌跡T′={Pc1,Pc2,…,Pc(m-1),Pcm}。壓縮率CR的定義如公式所示：

(1)

定義4垂直距離誤差：給定原始軌跡T及其壓縮后的軌跡T′，T中的定位點Pi相對于T′的垂直距離誤差可表示為Pi與Pi的估計點Pi′之間的距離。如果T′中包含Pi，則Pi′ =Pi。否則Pi′為Pi與直線predT′ (Pi)succT′(Pi)的垂點，其中predT′ (Pi) 與succT′(Pi)分別表示T′中離Pi最近的前驅和后繼。

圖1用軌跡T={P1,P2,…,P6}及其壓縮后的軌跡T′={P1,P4,P6}闡述了垂直距離誤差。如圖1所示，軌跡T中定位點P1、P4、P6對應于T′的垂直距離誤差為零。P2的垂直距離誤差為P2到直線P1P4的垂直距離。

圖1　垂直距離誤差

定義5方向誤差：給定原始軌跡T及其壓縮后的軌跡T′，軌跡T中Pi點對應于T′的方向誤差可表示為DirectionChange(h1,h2)，其中h1為Pi點的方向，h2為T′中由定位點PsPe構成的射線方向，Ps=predT′(Pi+1)，Pe=succT′ (Pi)。方向變化函數DirectionChange及方向函數Direction的定義如下。

(2)

(3)

(4)

2　距離誤差可控的DPTS-SP-Prac改進算法

2.1　算法描述

給定原始軌跡T={P1,P2,…,Pn-1,Pn}和角度閾值θ，DPTS-SP-Prac算法通過三個步驟實現軌跡壓縮：(1) 基于給定的軌跡T和角度閾值限定條件構建一個圖，對于任意兩個定位點(Pi,Pj)(1≤i

2.2　算法偽代碼

為了更簡潔地對算法的偽代碼進行描述，我們首先給出兩個符號Δ(Pi,Pj)和(Pi,Pj)。其中Δ(Pi,Pj)的含義為Pi與Pj之間的定位點與線段PiPj的最大垂直距離。(Pi,Pj)的含義為Pi與Pj之間的定位點與射線之間的最大方向變化。圖2給出了距離誤差可控的DPTS-SP-Prac改進算法的詳細描述。該算法維持了兩個集合，集合H用以存儲BFS檢索過的定位點，集合U用來存儲未被訪問過的定位點。首先H0的值被設置為{P1}，U的值被設置為{P2,P3,…,Pn}，并初始化l=1。算法的迭代通過Hl-1來計算Hl。對于Hl-1中的每個點Pi,U中的每個點Pj，檢查位于PiPj之間的所有定位點是否均滿足垂直距離誤差條件和方向誤差條件，如果滿足條件，則進一步判斷Pj是否為軌跡T的終點，如果Pj=Pn則返回壓縮后的軌跡，算法結束。如果Pj≠Pn，則更新集合U和Hl，繼續進行搜索。

距離誤差可控的DPTS?SP?Prac改進算法INPUT：　T={P1，P2，…，Pn}　　　　//原始軌跡　　μ　　　　//垂直距離閾值　　θ　　　//角度閾值1．H0={P1}；U={P2，P3，…，Pn}；l=1；2．while(true){3．　Hl=？4．　for(eachPiinHl-1andeachPjinUwherei

圖2距離誤差可控的DPTS-SP-Prac改進算法

3　算法評估

為了對改進的算法進行評估，我們使用Scala語言實現了DPTS-SP-Prac算法及其他的一些軌跡壓縮算法，并選取了Geolife數據集[20-22]作為實驗數據。Geolife 數據集的軌跡數據由182個用戶，歷時五年收集而來。其中73個用戶標記了他們軌跡的交通模式(開車、乘公交、騎自行車、乘地鐵、步行等)。Geolife 數據集總共包含了17 621條軌跡，總長度1 292 951 km，累積時間達到50 176 h。這些軌跡數據來自不同的GPS記錄器以及智能手機，軌跡的采樣周期也不盡相同，其中91.5%的軌跡數據為密集采樣(即每隔1～5 s或每隔5～10 m記錄一個定位點)。我們在Geolife數據集中選取了兩條不同交通模式的軌跡作為實驗數據。軌跡1是一條公交車的行駛軌跡，該軌跡包含2 045 個定位點，歷時50分鐘 (從2008-06-18, 12:33:34 到2008-06-18, 13:23:02)。軌跡2是一條高速公路上出租車的行駛軌跡，其中包含2 167個定位點，歷時37 min(從2008-04-04, 07:16:50 到2008-04-04, 07:53:00)。

為了評估軌跡壓縮算法壓縮的精確程度，我們選取了平均垂直距離誤差APDE(Average Perpendicular Distance Error)及平均方向誤差ADE(Average Direction Error)對算法進行評估。給定原始軌跡T={P1,P2,…,Pn}及壓縮后的軌跡T′，平均垂直距離誤差及平均方向誤差的定義如下：

(5)

(6)

3.1　相同角度閾值下DPTS-SP-Prac與DPTS-SP-Prac改進算法的比較

圖3在相同角度閾值下，就平均垂直距離誤差，對DPTS-SP-Prac和DPTS-SP-Prac改進算法進行了對比。從圖中可以看出，隨著角度閾值的增大，未改進的原DPTS-SP-Prac算法的垂直距離誤差急速增大，最大時接近2 km。而平均2 km的誤差，在有些情況下是不可接受的，因此一個可控的距離誤差對于DPTS-SP-Prac顯得尤為重要。而對于本文提出的改進算法而言，由于設置了一個100 m的距離閾值，因此不論多大的角度閾值都不會使得壓縮結果產生一個超出預期的距離誤差。

(a) 軌跡1公交車行駛軌跡

(b) 軌跡2高速公路上汽車的軌跡圖3　平均垂直距離誤差

3.2　相同壓縮率條件下對DPTS-SP-Prac改進算法評估

為了驗證改進后的算法的有效性，我們選取了一些傳統的基于位置的軌跡壓縮算法與所提出的算法進行對比。如圖4所示，在相同壓縮率的條件下，想比于原始的DPTS-SP-Prac，本文提出的改進算法有效地降低了壓縮的平均垂直距離誤差。雖然本文算法的平均垂直距離誤差比傳統的基于位置的軌跡壓縮算法的誤差大，但接下來我們將會看到該算法在軌跡方向信息保持方面的優勢。

(b) 軌跡2高速公路上汽車的軌跡　　　　　　　圖4　平均垂直距離誤差

如圖5所示，在相同壓縮率的條件下，由于傳統的基于位置保持的軌跡壓縮算法只關注于位置信息的保持，因此這些算法會丟失較多的方向信息。而基于方向保持的DPTS-SP-Prac及其改進算法，則能夠較好地保持軌跡的方向信息。對于軌跡1，本文提出的改進算法在壓縮率達到30時的平均方向誤差，比基于位置保持的軌跡壓縮算法在壓縮率為5時的誤差還小。結合圖4和圖5可以看出，本文提出的算法在有效地保持軌跡的方向信息的同時有效地降低了平均垂直距離誤差，提高了算法的可用性。

(a) 軌跡1公交車行駛軌跡

(b) 軌跡2高速公路上汽車的軌跡圖5　平均方向誤差

4　結　語

本文提出一種距離誤差可控的DPTS-SP-Prac改進算法，其解決了DPTS-SP-Prac算法距離誤差不可控的問題，提高了算法的可用性。該算法在原有的算法的基礎上，通過增加對距離誤差的檢查，實現了距離誤差的可控。因此，在使用該算法進行壓縮時，不會出現超出用戶預期、不可預料的距離誤差。真實世界數據集下的實驗結果驗證了這種改進的優越性，相比于原有算法，該改進算法壓縮結果更加精確，具有更小的誤差和更高的可用性。

[1] 李婷，裴韜，袁燁城. 人類活動軌跡的分類、模式和應用研究綜述[J]. 地理科學進展，2014，33(7)：938-948.

[2] 袁晶. 大規模軌跡數據的檢索、挖掘和應用[D]. 合肥：中國科學技術大學，2012.

[3] Chen M, Xu M, Fr?nti P. A fast O(N) multiresolution polygonal approximation algorithm for GPS trajectory simplification[J]. IEEE Transactions on Image Processing, 2012, 21(5):2770-2785.

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

[5] Meratnia N, By R A. Spatiotemporal compression techniques for moving point objects[C]// Springer, 9th international conference on extending database technology. Crete: Springer, 2004.

[6] Bellman R. On the approximation of curves by line segments using dynamic programming[J]. Communications of the Association for Computing Machinery, 1961, 4(6): 284-286.

[7] Perez J C, Vidal E. Optimum polygonal approximation of digitized curves[J]. Pattern Recognition Letters, 1994, 15(8): 743-750.

[8] Salotti M. Improvement of perez and vidal algorithm for the decomposition of digitized curves into line segments[C]// IEEE, 15th Conference on pattern recognition. Barcelona: IEEE, 2000.

[9] Salotti M. An efficient algorithm for the optimal polygonal approximation of digitized curves[J]. Pattern Recognition Letters, 2001, 22(2): 215-221.

[10] Kolesnikov A, Fr?nti P. A fast nearoptimal min-# polygonal approximation of digitized curves[C]// IEEE, 16th International conference on automation. Novosibirsk: IEEE, 2002.

[11] Kolesnikov A, Fr?nti P. Reduced search dynamic programming for approximation of polygonal curves[J]. Pattern Recognition Letters, 2003, 24(14): 2243-2254.

[12] Muckell J, Hwang J, Patil V, et al. SQUISH: an online approach for GPS trajectory compression[C]// ACM, 2nd international conference on computing for geospatial research and applications. Washington D.C.: ACM, 2011.

[13] 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.

[14] Chen Y K, Jiang K, Zheng Y, et al. Trajectory simplification method for location-based social networking services[C]// ACM, 2009 International workshop on location based social networks. Seattle: ACM, 2009.

[15] Brakatsoulas S, Pfoser D, Salas R, et al. On map-matching vehicle tracking data[C]// International Conference on Very Large Data Bases. VLDB Endowment, 2005:853-864.

[16] Lee J G, Han J, Whang K Y. Trajectory clustering:a partition-and-group framework[C]// ACM SIGMOD International Conference on Management of Data. ACM, 2007:593-604.

[17] Lee J G, Han J, Li X, et al. TraClass : trajectory classification using hierarchical region-based and trajectory-based clustering[J]. Proceedings of the Vldb Endowment, 2008, 1(1):1081-1094.

[18] Lee J G, Han J, Li X. Trajectory Outlier Detection: A Partition-and-Detect Framework[C]// IEEE, International Conference on Data Engineering. IEEE Computer Society, 2008:140-149.

[19] Long C, Wong C W, Jagadish H V. Direction-preserving trajectory simplification[J]. Proceedings of the Vldb Endowment, 2013, 6(10):949-960.

[20] Zheng Y, Zhang L, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories[C]// International Conference on World Wide Web. ACM, 2009:791-800.

[21] Zheng Y, Li Q, Chen Y, et al. Understanding mobility based on GPS data[C]// International Conference on Ubiquitous Computing. ACM, 2008:312-321.

[22] Zheng Y, Xie X, Ma W Y. GeoLife: A Collaborative Social Networking Service among User, Location and Trajectory[J]. Bulletin of the Technical Committee on Data Engineering, 2010, 33(2):32-39.