一種基于雙速度特征的軌跡劃分方法

祝 賀，于子興

(南京郵電大學 計算機學院，江蘇 南京 210023)

0 引 言

隨著便攜式傳感設備被廣泛應用在人們的日常生活中，由此產生了攜帶重要位置信息的軌跡數據，例如人類生活的行為軌跡數據、自然環境記錄數據等，刻畫了目標對象在時空環境下的個體行為。

軌跡壓縮即使用更少存儲空間的數據信息來代表原始的軌跡時空信息。現有的軌跡壓縮方法一般根據軌跡點的位置信息(經、緯度和偏離角度)來篩選和保留具有顯著特征的軌跡點，然而這些方法都沒有考慮從節點的移動特征角度出發來對軌跡進行劃分，劃分結果有一定的局限性。

因此，筆者考慮節點的雙速度特征(速度和加速度)，并將這些特征結合起來，從而實現對軌跡的有效劃分。

提出的劃分軌跡的方法主要有如下2個創新點：

(1)基于速度和加速度特征對軌跡進行劃分，該方法能夠篩選和保留具有顯著特征的軌跡點，同時確保劃分后的軌跡與原來軌跡的形狀相似。

(2)基于節點雙速度特征檢測來提取停留點的算法，該算法相對其他停留點選擇算法不僅能夠更準確地提取出停留點，而且具有更低的時間復雜度。

1 相關工作

軌跡劃分技術類似于較早提出的軌跡壓縮技術，但又有所不同，軌跡劃分根據軌跡中的關鍵特征進行劃分，而軌跡壓縮則是根據某個距離度量進行壓縮。目前已有較多工作，比如文獻[4]分別介紹了離線壓縮方法和在線壓縮方法兩種軌跡壓縮策略。離線軌跡壓縮的典型算法有DP算法，DP算法是將原始軌跡用滿足特定的垂直歐氏距離的多個軌跡段來近似表示。與離線壓縮相比，在線壓縮在傳輸時能立即對每個軌跡進行壓縮，例如滑動窗口算法和開放窗口算法。開放窗口算法是一種基于DP算法的啟發式方法，該算法的思想是設定空間誤差應滿足的閾值，然后通過使用越來越多的點來逼近每個軌跡段直到達到空間誤差小于約束值的目標。

除了上述兩類方法，文獻[8]還提出一個有界象限系統BQS的軌跡壓縮方法。該方法的優點是能夠獲得不同的壓縮誤差界限，快速地得到壓縮結果，它以起點為中心建立一個虛擬坐標系，在每個象限中，以由盒跟線形成的凸包限定待評估的點。Liu等人還提出了一次誤差界限的軌跡壓縮算法OPERB，該算法通過基于擬合函數的局部距離檢查方法來維持有向線段近似緩沖點。Lee等人提出了一種基于最小描述長度的軌跡劃分方法MDL。此外，文獻[11-12]借助于路網結構，把軌跡數據點的序列映射到路網路段上，用兩個點構成的邊來表示同一條道路上的軌跡點。

2 軌跡劃分算法

2.1 基本概念

首先給出以下幾個定義：

定義1 坐標點

p

：一個帶時間戳的坐標點定義為

p

=(Lat,Lngt,

T

),其中Lat為緯度，Lngt為經度,

T

為時間戳。定義2 軌跡Tra：一條軌跡Tra定義為按時序組成的一組坐標點序，Tra=

p

→

p

→…→

p

，其中

p

.T

<

p

+1

.T

。定義3 停留點SP：一個停留點定義為SP=(Lat,Lngt,

T

,

T

),表示節點SP在時間

T

到達，然后在時間

T

離開。

2.2 根據速度變化提取特征點

當節點由一種出行方式切換到另外一種出行方式時，它的移動速度會發生很大變化，像其出行方式由步行切換到乘公共汽車，移動速度會增大，由乘坐地鐵換成騎自行車，其移動速度會減小。

考慮到出行方式的變化會引起速度的改變，為了檢測切換不同出行方式的切換點，將移動速度差定義為Δ

v

,+1=|

v

,+1-

v

+1,+2|,其中

v

,+1代表節點在軌跡段

p

p

+1上的平均速度，如果Δ

v

,+1大于給定的速度閾值，那么

p

+1將被認為是特征點，在這里為了衡量速度的波動，以速度的標準差作為速度變化閾值。速度變化閾值

v

表示為：

(1)

2.3 根據加速度變化提取特征點

通常節點在遇到某些特殊事件時，其加速度變化較大，例如路口轉彎、等紅綠燈、公共汽車或者地鐵停靠站臺。

為了檢測加速度改變的軌跡點，將軌跡上點

p

+1的加速度定義為:

其中，

t

是軌跡點

p

的時間戳，加速度差定義為Δ

a

,+1=|

a

+1-

a

|，如果Δ

a

,+1大于給定的加速度閾值，那么

p

+1將被認為是特征點。以加速度的標準差作為加速度變化閾值。加速度變化閾值

a

表示為：

(2)

2.4 根據速度和加速度提取停留點

節點經常訪問或長期停留的地點可以看作停留點。文獻[16-18]中提出了綜合空間距離遠近和時間間隔多少提取停留點的方法：首先測量起始軌跡點與后繼軌跡點之間的距離是否大于設定的距離閾值，然后判斷起始軌跡點與最后一個滿足條件的軌跡點之間的時間跨度。如果時間跨度大于時間閾值，則以這些軌跡點的平均位置作為停留點。

為了解決選擇錯誤的起始軌跡點，以及無法從存在往返路徑的軌跡中確定停留點的問題，文獻[19]提出了基于節點移動速度的停留點提取方法SPEMS。

此外，需要注意簡單地設置前后搜索到的兩點的中間節點作為停留點，而移除兩點之間的其他軌跡點，可能會引起軌跡形態發生劇烈變化。如圖1所示，其中

v

≤

v

，

v

表示速度變化閾值，因為

p

和

p

在以

p

為圓心，

r

為半徑的搜索圓之外，則以

p

為中心并通過向后和向前搜索分別找到

p

和

p

，

r

表示搜索半徑閾值。若判斷Δ

t

(

p

,

p

)≥

δ

，則

p

為停留點。同時，注意到節點在靠近停留點前會存在減速行為，在節點將要離開該位置時，節點會明顯提高其移動速度，即會存在加速度先減小后增大的變化過程。所以需要在搜索圓中能確定加速度減小或者加速度增大的軌跡點，選擇介于這兩點的中間軌跡點作為停留點，否則選擇介于前后搜索確定的軌跡點之間的平均位置作為停留點，該方法能有效解決所選停留點引起原始軌跡形態發生劇烈變化的問題。據此，在SPEMS算法的基礎上引入加速度指標，提出了一種基于雙速度特征(速度和加速度)的停留點提取方法SPEDV(stop points extraction method based on the moving speeds and accelerated velocity of nodes)。

圖1 原始軌跡形態發生劇烈變化

SPEDV根據以下步驟提取停留點：

步驟1：遍歷每組相鄰的GPS軌跡點

p

、

p

+1和

p

+2，計算出加速度

a

+1和速度

v

,+1。步驟2：如果

v

,+1≤

λ

(

λ

表示速度閾值)，則執行以

p

+1為中心的向后搜索來提取

p

，使得不等式dist(

p

+1,

p

)≤

r

和dist(

p

+1,

p

)>

r

成立，其中

r

表示搜索半徑閾值，

k

=

m

+2,

m

+3,…,lst。步驟3：執行以

p

+1為中心的向前搜索來提取

p

，使得不等式dist(

p

+1,

p

)≤

r

和dist(

p

+1,

p

)>

r

成立，其中

r

表示搜索半徑閾值，

k

=

i

,

i

-1,…,fst。步驟4：如果時間間隔Δ

t

(

p

,

p

)≥

δ

(

δ

表示時間閾值)，令

F

=fst，判斷

a

≥

β

,

β

是加速度閾值是否成立，若成立，則flag=1；否則判斷

a

≥

β

是否成立，若成立則令flag1=1，

F

=fst+1，終止迭代，否則繼續判斷

a

≥

β

是否成立，直到滿足fst+

n

>

m

+1。步驟5：令

B

=lst，判斷

a

≤-

β

是否成立，若成立flag2=1，否則判斷

a

≤-

β

是否成立，若成立則令flag2=1和

B

=lst-1，否則繼續判斷

a

≤-

β

是否成立，直到滿足lst-

n

<

m

+1。步驟6：如果flag1=1或者flag2=1，則移除

p

和

p

之間所有的點，取中間點

p

(+)2作為停留點。否則，以介于

p

和

p

之間的所有軌跡點的平均位置作為停留點，并移除

p

和

p

之間所有的點。

對于圖1中選取的停留點導致原始軌跡形態發生劇烈變化的情況，利用SPEDV算法則有效規避了這種風險，其停留點提取結果如圖2所示。

圖2 SPEDV提取停留點

SPEDV的偽代碼在算法1中進行了描述:

算法1:停留點檢測算法(SPEDV)。

輸入:軌跡數據集Tra=

p

,

p

,…,

p

,速度閾值

λ

，時間閾值

δ

，半徑

r

，加速度閾值

β

輸出:停留點集合SP

1:

m

=1,flag1=0,flag2=02:while

m

<

n

-2 do3: 計算加速度

a

+1、速度

v

,+14: if

v

,+1≤

λ

then5: fst=Backward_Search(Tra[]，

m

,

r

)6: lst=Forward_Search(Tra[],

m

,

r

)

7: end if

8:Δ

t

=

p

.t

-

p

.t

9: if Δ

t

≥

δ

then10:

F

=first,

B

=last11: while fst<

m

+1 do12: if

a

≤-

β

13: flag1=1

14:

F

=fst,break

15: end if

16: fst=fst+1

17: end while

18: while lst>

m

+1 do19: if

a

≥

β

20: flag1=1

21:

B

=lst,break

22: end if

23: lst=lst-1

24: end while

25: mid=(

F

+

B

)

/

2.

26: if flag1‖flag2==1

27: Add Tra[mid] to SP

28: else

29:

p

和

p

之間的所有軌跡點的平均位置賦給Tra[mid]

30: Add Tra[mid] to SP

31: end if

32: Remove points from

p

to

p

except

p

33: else

34:

m

=

m

+1

35: end if

36:end while

2.5 基于雙速度特征的軌跡劃分算法

在基于雙速度特征的軌跡劃分方法TPDV(trajectory partition method based on double velocities)中，根據速度和加速度變化提取特征點，使用SPEDV算法提取出停留點，根據這些提取出來的特征點對軌跡進行劃分。TPDV的偽代碼在算法2中進行了描述：

算法2：TPDV算法。

輸入:軌跡數據集Tra=

p

,

p

,…,

p

,速度閾值

λ

，加速度閾值

β

，時間閾值

δ

，半徑

r

輸出:特征點集合FP

1:

m

=1,

k

=0,FP=?2: FP←(FP∪

p

),FP←(FP∪

p

)3:

v

←計算速度標準差4:

a

←計算加速度標準差5: while

m

≤

n

-2 do6: if |

v

,+1-

v

+1,+2|≥

v

then7: FP←(FP∪

p

+1)

8: else

9: if |

a

+1-

a

|≥

a

then10: FP←(FP∪

p

+1)

11: end if

12:

m

=

m

+1

13: end while

14: SP=TPDV(TR,

r

,

λ

,

β

,

δ

)

15:FP←(FP∪SP)

16:按時間從小到大將FP的點排序

2.6 度量指標

利用三個指標來衡量軌跡劃分算法的性能：(a)簡化率，即劃分后的軌跡點數目與原軌跡點數的比例；(b)運行時間，指劃分軌跡需要的運行時間；(c)文獻[19]提出的評估軌跡劃分誤差測量方法。

3 仿真實驗與結果分析

本節將對TPDV算法進行仿真分析，評估TPDV在Geolife數據集上的性能。所有仿真都在配備有Windows 10、2.40 GHz CPU和16 GB內存的PC上進行。

3.1 數據集

以微軟研究Geolife項目中收集的182個用戶的軌跡數據作為仿真實驗數據集。這些數據包含了一系列軌跡點，每一個點軌跡點包含經緯度、時間戳等信息。

3.2 軌跡劃分方法的比較

表1 仿真參數設置

3.2.1 仿真1─與TPMF算法比較

首先比較了與同基于節點移動特征進行軌跡劃分的TPMF算法，測試了它們在運行時間、簡化率和軌跡劃分誤差三方面的性能。首先對節點1的所有軌跡進行了劃分，仿真結果如圖3～圖5所示。

圖3 單節點運行時間比較

圖4 單節點簡化率比較

從圖3可以看出，TPDV的運行時間要比TPMF短，這是因為TPMF遞歸提取移動方向變化的特征點。如圖4所示，在簡化率方面，TPDV比TPMF算法提取了更多的軌跡點作為特征點。而就劃分誤差而言，在圖5中，TPDV要低于TPMF的誤差曲線。因此，相較于TPMF，TPDV算法具備更低的時間復雜度，同時軌跡劃分誤差率也更小。

圖5 單節點劃分誤差比較

為了獲得更準確的實驗結果，對更大量的軌跡點進行了實驗。為此從數據集中選擇了5個節點(Node 1、3、5、6、9)，仿真結果分別如圖6～圖8所示。

圖6 多節點運行時間比較

圖7 多節點簡化率比較

圖8 多節點劃分誤差比較

圖6中TPDV在每個節點上的運行時間都要比TPMF少，且節點中軌跡點數量越多，時間差越大(在節點7上時間相差約2 s，對于節點5則相差11 s左右)。圖7中給出了節點的平均簡化率，TPDV算法的簡化率在80%至90%之間，要略低于TPMF，原因在于TPDV比TPMF算法提取了更多的軌跡點作為特征點。TPDV根據加速度變化提取的特征點中不僅包含了移動方向變化顯著的軌跡點，還有遭遇紅綠燈、公共汽車或者地鐵停靠站臺等特殊情況的軌跡點。從圖8可以明顯看出，TPDV的平均誤差(5個節點的平均誤差都靠近15%刻度線)始終比TPMF要低，這都歸因于利用SPEDV算法提取停留點，有效解決了誤選停留點導致原始軌跡形態發生劇烈變化的問題。

3.2.2 仿真2─與其他算法比較

此外，還將TPDV算法與其他4種算法(DP、BQS、OPERB、MDL)進行了比較。其中各算法用到的歐氏距離閾值都設置為10 m。仿真結果如圖9～圖11所示。

圖9 運行時間

如圖9所示，OPERB算法的運行時間快于其他算法，TPDV的運行時間要比BQS、MDL和DP算法短，略高于OPERB算法的運行時間，MDL運行時間比其他算法要長的多。

圖10 簡化率

在圖10中，OPERB在節點平均簡化率方面表現最優，達到90%以上，MDL在所有算法中取得最低的簡化率。TPDV和DP的簡化率曲線相互交叉，它們的簡化率都介于80%到85%之間，而BQS的簡化率略高于TPDV和DP。

圖11 劃分誤差

在圖11中，TPDV的平均誤差始終比DP、BQS和OPERB小，MDL獲得了最低的平均誤差，這主要歸因于MDL算法近似地劃分軌跡，保留了大量的軌跡點且盡可能地維持了軌跡形狀。

綜合上述仿真結果，TPDV算法根據軌跡點速度和加速度提取特征點來對子軌跡進行劃分，在簡化率和軌跡劃分誤差之間取得較好的平衡，同時也具備較低的時間復雜度。

4 結束語

軌跡劃分作為軌跡數據挖掘的一個主要步驟，該文提出了一種基于雙速度特征的軌跡劃分方法。該方法的突出優點是全面考慮了節點的移動特征，在去掉大量冗余點的情況下，保持了節點的移動軌跡形狀骨架。未來的研究將關注TPDV方法中參數設置的自適應解決方案，如參數

r

、

δ

和

β

的值。此外，還將研究基于TPDV的軌跡挖掘算法，以獲得節點的運動模式。