軌跡壓縮的典型方法評(píng)價(jià)

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

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

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

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

1 典型軌跡壓縮方法

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

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

2 軌跡壓縮方法的評(píng)價(jià)指標(biāo)

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

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

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

(1)

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

(2)

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

方向誤差是將壓縮軌跡的方向直接使用兩點(diǎn)之間的方向(以正北方向?yàn)檎较?，以順時(shí)針?lè)较蜻M(jìn)行度量)對(duì)壓縮后的軌跡進(jìn)行重建，即計(jì)算出冗余點(diǎn)在壓縮后的軌跡上的時(shí)間同步點(diǎn)，然后一一對(duì)應(yīng)的計(jì)算點(diǎn)之間的方向差值，以絕對(duì)值累加，最后除以總點(diǎn)數(shù)。該指標(biāo)同樣用于評(píng)估軌跡數(shù)據(jù)壓縮前后幾何形態(tài)的變化，不過(guò)側(cè)重在軌跡壓縮前后的方向上。

(3)

速度誤差是對(duì)壓縮后的軌跡進(jìn)行重建，即計(jì)算出冗余點(diǎn)在壓縮后的軌跡上的時(shí)間同步點(diǎn)，然后一一對(duì)應(yīng)計(jì)算點(diǎn)之間的速度差值，以絕對(duì)值累加，最后除以原始軌跡點(diǎn)的總點(diǎn)數(shù)。該指標(biāo)也是用來(lái)評(píng)估軌跡壓縮前后運(yùn)動(dòng)特征損失的重要指標(biāo)之一。

(4)

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

CR=Ncom/Nori

(5)

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

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

3 評(píng)價(jià)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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