梁 明，陳文靜，段 平，李 佳

(1. 安徽大學資源與環(huán)境工程學院，安徽 合肥 230601； 2. 云南師范大學旅游與地理科學學院，云南 昆明 650500)

軌跡數(shù)據(jù)是典型的時空大數(shù)據(jù)，其在多個領(lǐng)域都有著極其突出而重要的研究和應用價值[1-2]。作為時序數(shù)據(jù)的特例，軌跡數(shù)據(jù)具有鮮明的時序特征，同時還具有突出的空間特征。因此，軌跡數(shù)據(jù)的處理和挖掘方法不能完全照搬時序數(shù)據(jù)的經(jīng)驗，而應當考慮其特殊性。當前限制軌跡數(shù)據(jù)處理和挖掘的重要因素之一是軌跡數(shù)據(jù)海量的數(shù)據(jù)規(guī)模[3-4]。軌跡數(shù)據(jù)的海量數(shù)據(jù)規(guī)模帶來的問題是多方面的，主要表現(xiàn)在：①數(shù)據(jù)存儲壓力大，海量的數(shù)據(jù)規(guī)模和非結(jié)構(gòu)化的數(shù)據(jù)組織為軌跡數(shù)據(jù)的實時數(shù)據(jù)存儲和快速索引帶來了巨大的挑戰(zhàn)；②數(shù)據(jù)的分析壓力大，典型的數(shù)據(jù)挖掘方法在面對海量軌跡數(shù)據(jù)時通常無法直接使用，為軌跡數(shù)據(jù)的分析和挖掘帶來了挑戰(zhàn)；③軌跡數(shù)據(jù)的可視化壓力大，可視化是軌跡數(shù)據(jù)理解和分析的重要手段，而海量的數(shù)據(jù)規(guī)模讓傳統(tǒng)的可視化手段無用武之地，特別是面向Web端和移動端的實時可視化時更顯得傳統(tǒng)手段的不足。

針對軌跡這類特殊時空數(shù)據(jù)的壓縮方法的研究已經(jīng)成為軌跡大數(shù)據(jù)研究領(lǐng)域的重要研究內(nèi)容。軌跡壓縮的實質(zhì)是實現(xiàn)軌跡的數(shù)據(jù)規(guī)模和數(shù)據(jù)質(zhì)量的統(tǒng)一，即數(shù)據(jù)的“量”與“質(zhì)”的統(tǒng)一。正是由于軌跡數(shù)據(jù)不同于常規(guī)的時序數(shù)據(jù)，它有著豐富多維的時空特征，因而在軌跡數(shù)據(jù)壓縮的過程中，如何在減少數(shù)據(jù)量的同時盡可能保障軌跡數(shù)據(jù)的多維時空特征的損失最小，是不同軌跡壓縮方法都應該考慮的問題[4-5]?，F(xiàn)有軌跡壓縮方法的研究雖多，但是缺乏對軌跡數(shù)據(jù)在各個維度的時空特征損失的評價研究。因此，本文綜合選取了MBR面積誤差、距離誤差、方向誤差等多個指標[6]，分別從幾何形態(tài)和運動特征等多個角度對典型的軌跡壓縮算法進行評價，從而為軌跡壓縮的研究和實際應用提供更精確的量化參考。

1 典型軌跡壓縮方法

軌跡壓縮方法可以分為不同的類型，根據(jù)軌跡壓縮過程中是否參考地理背景，可以將軌跡壓縮分為兩種類型：一種是僅僅基于軌跡幾何線劃特征的壓縮方法；另一種是基于路網(wǎng)或語義的軌跡壓縮[7-8]。此外，由于軌跡壓縮過程中最重要的是要尋找最典型最有代表性的特征點，因而基于選取特征點方法的不同，又可以將軌跡壓縮方法分為基于全局特征的軌跡壓縮方法和基于局部特征的壓縮方法。基于全局的壓縮方法，如經(jīng)典的Douglas-Peucker(簡稱DP)算法，它是基于特征點到全局的首末節(jié)點連線的歐氏距離進行特征度量的方法[9]；依時間比例的自頂向下算法(top-down time ratio，TD_TR)同樣是基于全局特征的，但是不同于DP算法直接采用歐氏距離作為壓縮閾值，TD_TR算法采用時間同步歐氏距離作為壓縮閾值[10]。此類全局壓縮算法優(yōu)點在于在考察軌跡點的特征時是從全局出發(fā)進行度量的，能夠保留軌跡數(shù)據(jù)的整體形態(tài)。然而，由于此類全局算法通常是遞歸的，因此壓縮速度較慢。此外，DP和TD_TR算法無法有效壓縮封閉的或者起止點相鄰過于接近的軌跡。

全局壓縮算法適用于靜態(tài)或歷史的軌跡數(shù)據(jù)壓縮。對于實時在線的軌跡壓縮需求，基于局部特征的壓縮方法更為合適。最簡單的局部壓縮算法，只需要考慮當前點和相鄰兩個節(jié)點之間的特征關(guān)系，如垂距法和夾角法等，但是由于比較的對象過少，此類壓縮算法無法甄別出局部變化小而累積起來變化大的時空彎曲[11]。因此，相對而言基于窗口的壓縮算法能夠更好地統(tǒng)籌局部特征和整體特征。典型的窗口壓縮算法有滑動窗口算法(slide window，SW)和開放窗口算法(opening window)[12]，其中開放窗口算法又因選取終點的策略不同而分為一般開放窗口算法(normal opening window，NOPW)和向前開放窗口算法(before opening window，BOPW)。窗口算法是通過在窗口不斷更新窗口完成軌跡壓縮，而STTrace和SQUISH算法則是通過提供一個緩沖區(qū)，通過控制緩沖區(qū)的大小來控制給定壓縮率的情況下實現(xiàn)軌跡壓縮的[9,13]。因此，除了STTrace和SQUISH壓縮算法以外，其他的軌跡壓縮算法都可以基于給定的空間閾值進行壓縮(距離或角度等)。

2 軌跡壓縮方法的評價指標

對軌跡數(shù)據(jù)進行壓縮會帶來軌跡多維時空特征在不同維度上的損失。雖然部分研究對軌跡壓縮在某些維度的時空特征損失進行了探討，但是一方面這些研究分析的特征維度少，另一方面相關(guān)研究缺乏系統(tǒng)的對比研究。因此，本文從軌跡數(shù)據(jù)的幾何特征、運動特征和壓縮效率等3個角度，分別選取MBR面積誤差、方向誤差、距離誤差、速度誤差、壓縮率及壓縮速度等6個指標對軌跡壓縮方法進行系統(tǒng)的對比分析。

同時，為了綜合分析軌跡數(shù)據(jù)壓縮算法在多個壓縮尺度上誤差損失的一致性，本文選取了多個尺度進行分析。由于各類算法在具體實現(xiàn)上有所差異，尺度選擇又可以分為兩種不同的類型：一種是通過距離閾值來度量的空間尺度，另一種是以壓縮率為閾值度量的效率尺度。其中本文對DP、TD_TR、SW、BOPW、NOPW等采用基于距離閾值的多尺度評價方法，以距離閾值作為空間尺度變化進行評估，而對SQUISH、STTrace則以壓縮率作為尺度閾值進行評估。

軌跡壓縮對軌跡數(shù)據(jù)質(zhì)量的影響首先體現(xiàn)在軌跡幾何形態(tài)上。MBR作為軌跡幾何的最小外包矩形，對于度量軌跡形態(tài)變化具有重要的意義。MBR面積誤差，即為原始軌跡MBR的面積(通過比較相鄰特征點之間的軌跡點，找到軌跡對應的4個極值點)與壓縮后軌跡的MBR之間面積的差值。該指標用于分析軌跡數(shù)據(jù)壓縮前后幾何形態(tài)上的變化程度。通常認為，面積誤差越大，則軌跡在壓縮前后的幾何形態(tài)損失越大。

(1)

在幾何形態(tài)誤差度量中，另一種典型方法是度量壓縮前后軌跡特征點的距離誤差[14-15]。距離誤差，即首先在壓縮后的軌跡上重建被省略的冗余點位置，然后計算壓縮前后對應兩點之間的距離誤差的總和，并將其總和值除以原始軌跡的總點數(shù)。作為典型的軌跡壓縮評價方法，距離誤差能夠較好地表達軌跡形態(tài)在壓縮前后的變化。

(2)

軌跡數(shù)據(jù)中隱含了軌跡的運動特征，運動特征是軌跡數(shù)據(jù)不同于常規(guī)時序數(shù)據(jù)的顯著特征。由于運動特征對于軌跡挖掘具有舉足輕重的意義，因此，如何確保軌跡壓縮時對運動特征的損失最小，是軌跡壓縮方法評價的重要內(nèi)容。方向和速度作為軌跡數(shù)據(jù)關(guān)鍵的運動特征，尤為值得重視。

方向誤差是將壓縮軌跡的方向直接使用兩點之間的方向(以正北方向為正方向，以順時針方向進行度量)對壓縮后的軌跡進行重建，即計算出冗余點在壓縮后的軌跡上的時間同步點，然后一一對應的計算點之間的方向差值，以絕對值累加，最后除以總點數(shù)。該指標同樣用于評估軌跡數(shù)據(jù)壓縮前后幾何形態(tài)的變化，不過側(cè)重在軌跡壓縮前后的方向上。

(3)

速度誤差是對壓縮后的軌跡進行重建，即計算出冗余點在壓縮后的軌跡上的時間同步點，然后一一對應計算點之間的速度差值，以絕對值累加，最后除以原始軌跡點的總點數(shù)。該指標也是用來評估軌跡壓縮前后運動特征損失的重要指標之一。

(4)

壓縮率即使用壓縮后點的個數(shù)除以原始軌跡點的個數(shù)。壓縮率越小則說明壓縮后保留的軌跡點越少。對于SQUISH、STTrace兩種軌跡壓縮方法，由于它們是基于緩沖區(qū)的壓縮方法，不宜選用距離作為尺度度量。因此，本文選取給定壓縮率的方式來度量不同壓縮率下SQUISH和STTrace兩種壓縮方法對軌跡數(shù)據(jù)時空特征的影響。

CR=Ncom/Nori

(5)

式中，Ncom為壓縮后的軌跡點數(shù)；Nori為原始軌跡的軌跡點數(shù)。

壓縮速度即使用壓縮所用的時間除以原始軌跡的總點數(shù)。用壓縮速度來分析度量不同軌跡壓縮算法的壓縮效率。以壓縮速度為指標系統(tǒng)分析軌跡壓縮效率在多個不同壓縮尺度上的性能差異，從而為軌跡壓縮算法的選擇和壓縮閾值確定提供參考。

3 評價結(jié)果與分析

本文選用微軟亞洲研究院的GeoLife數(shù)據(jù)集作壓縮試驗的數(shù)據(jù)(https:∥www.microsoft.com/en-us/download/details.aspx?id=52367)。該數(shù)據(jù)集收集了北京地區(qū)178位志愿者2007—2011年的時空軌跡采樣數(shù)據(jù)。GeoLife數(shù)據(jù)集共包含17 621條記錄，記錄了超過1.25×106km的軌跡距離。由于數(shù)據(jù)的典型性和豐富性，GeoLife數(shù)據(jù)集已經(jīng)被廣泛應用于軌跡數(shù)據(jù)研究的眾多領(lǐng)域。由于GeoLife數(shù)據(jù)在采樣過程中存在一定的誤差和噪聲，本文先用時間和空間約束對原始GeoLife數(shù)據(jù)集進行預處理。在針對本文目標的試驗中，本文研究選擇了多人的多條軌跡進行定量的度量分析。此處只列舉了用戶000的軌跡壓縮和軌跡誤差定量分析結(jié)果。

由上述壓縮算法對多維運動特征影響的定量分析可見，在以距離為尺度閾值的壓縮算法中，DP算法和TD_TR算法是對完整的軌跡進行壓縮，考慮的是整體情況；而SW、BOPW、NOPW則是對局部的軌跡進行特征分析，并開展軌跡壓縮。通過對MBR面積誤差進行分析時可以看出(如圖1、圖2所示)，由于TD_TR算法使用距離閾值考慮了時間因素的時間同步歐氏距離，同時TD_TR又是全局算法，從而能夠盡可能地保持壓縮后軌跡的最佳形態(tài)，因此TD_TR壓縮算法的MBR誤差最小。對比分析NOPW和DP算法可以發(fā)現(xiàn)，NOPW算法雖是局部算法，但是并沒有規(guī)定具體的窗口范圍，而是由軌跡的形態(tài)決定窗口大小，相對地DP算法雖是全局算法，但在軌跡段的處理上并不細致，因此NOPW算法在形態(tài)保持方面略勝于DP算法。BOPW由于選取的不是窗口中距離代價最大的點，所以在保持上形態(tài)不及BOPW算法和DP算法。SW算法是局部算法，而且窗口的大小人為設置，一旦設置就不能改變，因此保留的點可能并不是信息量較多的點。

圖1 以距離為尺度閾值的MBR面積誤差

圖2 以壓縮率為尺度閾值的MBR面積誤差

對方向誤差的評價，是通過比較壓縮后的軌跡的平均方向與壓縮前軌跡的平均方向之間的誤差進行的。當某個壓縮算法保留的特征點越多、保留的特征點越重要，則其壓縮前后的方向誤差就越小。因此TD_TR算法的角度誤差最小，剩余的算法誤差與比較MBR誤差時相似(如圖3、圖4所示)。而總體趨勢上，隨著壓縮算法的空間尺度越大，各個算法都呈現(xiàn)出方向誤差單調(diào)增加的趨勢。

圖3 以距離為尺度閾值的方向誤差

圖4 以壓縮率為尺度閾值的方向誤差

距離誤差評價與MBR誤差分析相似，也是對形態(tài)保持方面的研究。因此得到的結(jié)果(如圖5、圖6所示)與MBR面積誤差和方向誤差評價的結(jié)論相類似。首先，TD_TR算法具有明顯優(yōu)于其他算法的最小距離誤差，而SW滑動窗口算法具有較大的誤差。其次，在多個壓縮尺度上，隨著空間尺度的增加各壓縮算法造成的軌跡距離誤差的趨勢為單調(diào)遞增。

圖5 以距離為尺度閾值的距離誤差

圖6 以壓縮率為尺度閾值的距離誤差

對速度誤差進行評價，是通過比較壓縮后的軌跡速度與壓縮前的軌跡平均速度之間的誤差開展的。在總體趨勢上其誤差的分布結(jié)果與距離誤差等類似(如圖7、圖8所示)。比較明顯的變化是，在速度誤差上，SW滑動窗口算法不再表現(xiàn)為隨著尺度的增加誤差相較于其他算法差距越大的趨勢(圖7)。其速度誤差總體上呈線性增長。

圖7 以距離為尺度閾值的速度誤差

圖8 以壓縮率為尺度閾值的速度誤差

針對壓縮率的評價，在軌跡點特征度量時采用的點到線段的最短距離是垂直距離，因此軌跡點的垂直距離(ED)是大于時間同步歐氏距離的(SED)。在進行軌跡點的保留時若采用相同的距離閾值，那么使用時間同步歐氏距離算法保留的點會多于使用垂直距離的算法，因此TD_TR算法的壓縮率最大及保留的點數(shù)最多。其余算法的壓縮率相似，但仍有微小的差距，如圖9—圖11所示。

圖9 以距離為尺度閾值的壓縮率誤差

圖10 以距離為尺度閾值的壓縮速度誤差

圖11 以壓縮率為尺度閾值的壓縮速度誤差

STTrace和SQUISH算法的思路大致相同，只是在更新冗余點前后對兩個鄰居點的時間同步歐氏距離的度量上有所差異：STTrace算法利用修改后的軌跡進行重新計算，而SQUISH是將冗余點的時間同步歐氏距離加到鄰居點上。因此STTrace所求的每個點的時間同步歐氏距離是真實值，而SQUISH求得軌跡點的距離值可能因為累加導致的權(quán)重過大。因此在MBR誤差、角度誤差、距離誤差、速度誤差方面STTrace要優(yōu)于SQUISH。

4 結(jié) 論

現(xiàn)有的各類軌跡壓縮算法，無法完全兼顧軌跡數(shù)據(jù)在不同維度時空特征的保持。因此，不同的算法或以速度保持為優(yōu)先、或以方向誤差最小為目標。這些軌跡壓縮算法雖有側(cè)重，卻缺乏各自算法對軌跡壓縮各個維度時空特征損失的系統(tǒng)評價，無法為不同應用場景下軌跡壓縮算法的選擇提供定量的參考。因此，本文選取MBR面積誤差、距離誤差、方向誤差、速度誤差、壓縮率和壓縮速度等軌跡數(shù)據(jù)壓縮前后的多維度時空特征，分別從軌跡的幾何特征、運動特征和壓縮效率3個方向?qū)Φ湫蛙壽E壓縮方法進行評價。通過綜合評價發(fā)現(xiàn)：①在特征度量中引入時間同步距離等顧及時空特征的壓縮算法，如TD_TR算法，總體上能夠較好地保持軌跡的時空特征；②不同壓縮算法對軌跡數(shù)據(jù)時空特征的影響在各個尺度上的表現(xiàn)基本是一致的。雖然不同的數(shù)據(jù)集可能在量化誤差時在具體分值上有差異，但是總體趨勢應該是穩(wěn)定的?？傮w上，研究表明難以有一種軌跡壓縮算法能夠兼顧所有維度時空特征的損失。本文的定量分析為具體應用中對軌跡壓縮算法的選擇提供了參考。然而，本文研究僅僅關(guān)注了軌跡壓縮算法對單一軌跡本身多維特征的影響，而未考慮不同壓縮算法對軌跡之間時空關(guān)系的影響。軌跡間的時空關(guān)系是時空檢索和時空挖掘的基礎(chǔ)。因此，在后續(xù)研究中應當進一步對典型軌跡壓縮算法對軌跡間時空關(guān)系的影響開展定量研究。