董天放　孟慶彬　舒　奎

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

0　引　言

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

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

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

1　軌跡壓縮的相關(guān)定義

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

定義2軌跡壓縮：給定一條軌跡T={P1,P2,…,Pn-1,Pn}，軌跡壓縮就是要尋找一系列以時(shí)間為順序的定位點(diǎn)的集合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中的定位點(diǎn)Pi相對(duì)于T′的垂直距離誤差可表示為Pi與Pi的估計(jì)點(diǎn)Pi′之間的距離。如果T′中包含Pi，則Pi′ =Pi。否則Pi′為Pi與直線predT′ (Pi)succT′(Pi)的垂點(diǎn)，其中predT′ (Pi) 與succT′(Pi)分別表示T′中離Pi最近的前驅(qū)和后繼。

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

圖1　垂直距離誤差

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

(2)

(3)

(4)

2　距離誤差可控的DPTS-SP-Prac改進(jìn)算法

2.1　算法描述

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

2.2　算法偽代碼

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

距離誤差可控的DPTS?SP?Prac改進(jìn)算法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改進(jìn)算法

3　算法評(píng)估

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

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

(5)

(6)

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

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

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

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

3.2　相同壓縮率條件下對(duì)DPTS-SP-Prac改進(jìn)算法評(píng)估

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

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

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

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

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

4　結(jié)　語

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

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

[2] 袁晶. 大規(guī)模軌跡數(shù)據(jù)的檢索、挖掘和應(yīng)用[D]. 合肥：中國科學(xué)技術(shù)大學(xué)，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.