祝 賀，于子興

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210023)

0 引 言

隨著便攜式傳感設(shè)備被廣泛應(yīng)用在人們的日常生活中，由此產(chǎn)生了攜帶重要位置信息的軌跡數(shù)據(jù)，例如人類生活的行為軌跡數(shù)據(jù)、自然環(huán)境記錄數(shù)據(jù)等，刻畫了目標(biāo)對(duì)象在時(shí)空環(huán)境下的個(gè)體行為。

軌跡壓縮即使用更少存儲(chǔ)空間的數(shù)據(jù)信息來代表原始的軌跡時(shí)空信息?，F(xiàn)有的軌跡壓縮方法一般根據(jù)軌跡點(diǎn)的位置信息(經(jīng)、緯度和偏離角度)來篩選和保留具有顯著特征的軌跡點(diǎn)，然而這些方法都沒有考慮從節(jié)點(diǎn)的移動(dòng)特征角度出發(fā)來對(duì)軌跡進(jìn)行劃分，劃分結(jié)果有一定的局限性。

因此，筆者考慮節(jié)點(diǎn)的雙速度特征(速度和加速度)，并將這些特征結(jié)合起來，從而實(shí)現(xiàn)對(duì)軌跡的有效劃分。

提出的劃分軌跡的方法主要有如下2個(gè)創(chuàng)新點(diǎn)：

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

(2)基于節(jié)點(diǎn)雙速度特征檢測來提取停留點(diǎn)的算法，該算法相對(duì)其他停留點(diǎn)選擇算法不僅能夠更準(zhǔn)確地提取出停留點(diǎn)，而且具有更低的時(shí)間復(fù)雜度。

1 相關(guān)工作

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

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

2 軌跡劃分算法

2.1 基本概念

首先給出以下幾個(gè)定義：

定義1 坐標(biāo)點(diǎn)

p

：一個(gè)帶時(shí)間戳的坐標(biāo)點(diǎn)定義為

p

=(Lat,Lngt,

T

),其中Lat為緯度，Lngt為經(jīng)度,

T

為時(shí)間戳。定義2 軌跡Tra：一條軌跡Tra定義為按時(shí)序組成的一組坐標(biāo)點(diǎn)序，Tra=

p

→

p

→…→

p

，其中

p

.T

<

p

+1

.T

。定義3 停留點(diǎn)SP：一個(gè)停留點(diǎn)定義為SP=(Lat,Lngt,

T

,

T

),表示節(jié)點(diǎn)SP在時(shí)間

T

到達(dá)，然后在時(shí)間

T

離開。

2.2 根據(jù)速度變化提取特征點(diǎn)

當(dāng)節(jié)點(diǎn)由一種出行方式切換到另外一種出行方式時(shí)，它的移動(dòng)速度會(huì)發(fā)生很大變化，像其出行方式由步行切換到乘公共汽車，移動(dòng)速度會(huì)增大，由乘坐地鐵換成騎自行車，其移動(dòng)速度會(huì)減小。

考慮到出行方式的變化會(huì)引起速度的改變，為了檢測切換不同出行方式的切換點(diǎn)，將移動(dòng)速度差定義為Δ

v

,+1=|

v

,+1-

v

+1,+2|,其中

v

,+1代表節(jié)點(diǎn)在軌跡段

p

p

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

v

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

p

+1將被認(rèn)為是特征點(diǎn)，在這里為了衡量速度的波動(dòng)，以速度的標(biāo)準(zhǔn)差作為速度變化閾值。速度變化閾值

v

表示為：

(1)

2.3 根據(jù)加速度變化提取特征點(diǎn)

通常節(jié)點(diǎn)在遇到某些特殊事件時(shí)，其加速度變化較大，例如路口轉(zhuǎn)彎、等紅綠燈、公共汽車或者地鐵?？空九_(tái)。

為了檢測加速度改變的軌跡點(diǎn)，將軌跡上點(diǎn)

p

+1的加速度定義為:

其中，

t

是軌跡點(diǎn)

p

的時(shí)間戳，加速度差定義為Δ

a

,+1=|

a

+1-

a

|，如果Δ

a

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

p

+1將被認(rèn)為是特征點(diǎn)。以加速度的標(biāo)準(zhǔn)差作為加速度變化閾值。加速度變化閾值

a

表示為：

(2)

2.4 根據(jù)速度和加速度提取停留點(diǎn)

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

為了解決選擇錯(cuò)誤的起始軌跡點(diǎn)，以及無法從存在往返路徑的軌跡中確定停留點(diǎn)的問題，文獻(xiàn)[19]提出了基于節(jié)點(diǎn)移動(dòng)速度的停留點(diǎn)提取方法SPEMS。

此外，需要注意簡單地設(shè)置前后搜索到的兩點(diǎn)的中間節(jié)點(diǎn)作為停留點(diǎn)，而移除兩點(diǎn)之間的其他軌跡點(diǎn)，可能會(huì)引起軌跡形態(tài)發(fā)生劇烈變化。如圖1所示，其中

v

≤

v

，

v

表示速度變化閾值，因?yàn)?p>p

和

p

在以

p

為圓心，

r

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

p

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

p

和

p

，

r

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

t

(

p

,

p

)≥

δ

，則

p

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

圖1 原始軌跡形態(tài)發(fā)生劇烈變化

SPEDV根據(jù)以下步驟提取停留點(diǎn)：

步驟1：遍歷每組相鄰的GPS軌跡點(diǎn)

p

、

p

+1和

p

+2，計(jì)算出加速度

a

+1和速度

v

,+1。步驟2：如果

v

,+1≤

λ

(

λ

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

p

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

p

，使得不等式dist(

p

+1,

p

)≤

r

和dist(

p

+1,

p

)>

r

成立，其中

r

表示搜索半徑閾值，

k

=

m

+2,

m

+3,…,lst。步驟3：執(zhí)行以

p

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

p

，使得不等式dist(

p

+1,

p

)≤

r

和dist(

p

+1,

p

)>

r

成立，其中

r

表示搜索半徑閾值，

k

=

i

,

i

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

t

(

p

,

p

)≥

δ

(

δ

表示時(shí)間閾值)，令

F

=fst，判斷

a

≥

β

,

β

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

a

≥

β

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

F

=fst+1，終止迭代，否則繼續(xù)判斷

a

≥

β

是否成立，直到滿足fst+

n

>

m

+1。步驟5：令

B

=lst，判斷

a

≤-

β

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

a

≤-

β

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

B

=lst-1，否則繼續(xù)判斷

a

≤-

β

是否成立，直到滿足lst-

n

<

m

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

p

和

p

之間所有的點(diǎn)，取中間點(diǎn)

p

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

p

和

p

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

p

和

p

之間所有的點(diǎn)。

對(duì)于圖1中選取的停留點(diǎn)導(dǎo)致原始軌跡形態(tài)發(fā)生劇烈變化的情況，利用SPEDV算法則有效規(guī)避了這種風(fēng)險(xiǎn)，其停留點(diǎn)提取結(jié)果如圖2所示。

圖2 SPEDV提取停留點(diǎn)

SPEDV的偽代碼在算法1中進(jìn)行了描述:

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

輸入:軌跡數(shù)據(jù)集Tra=

p

,

p

,…,

p

,速度閾值

λ

，時(shí)間閾值

δ

，半徑

r

，加速度閾值

β

輸出:停留點(diǎn)集合SP

1:

m

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

m

<

n

-2 do3: 計(jì)算加速度

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

之間的所有軌跡點(diǎn)的平均位置賦給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)中，根據(jù)速度和加速度變化提取特征點(diǎn)，使用SPEDV算法提取出停留點(diǎn)，根據(jù)這些提取出來的特征點(diǎn)對(duì)軌跡進(jìn)行劃分。TPDV的偽代碼在算法2中進(jìn)行了描述：

算法2：TPDV算法。

輸入:軌跡數(shù)據(jù)集Tra=

p

,

p

,…,

p

,速度閾值

λ

，加速度閾值

β

，時(shí)間閾值

δ

，半徑

r

輸出:特征點(diǎn)集合FP

1:

m

=1,

k

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

p

),FP←(FP∪

p

)3:

v

←計(jì)算速度標(biāo)準(zhǔn)差4:

a

←計(jì)算加速度標(biāo)準(zhǔn)差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:按時(shí)間從小到大將FP的點(diǎn)排序

2.6 度量指標(biāo)

利用三個(gè)指標(biāo)來衡量軌跡劃分算法的性能：(a)簡化率，即劃分后的軌跡點(diǎn)數(shù)目與原軌跡點(diǎn)數(shù)的比例；(b)運(yùn)行時(shí)間，指劃分軌跡需要的運(yùn)行時(shí)間；(c)文獻(xiàn)[19]提出的評(píng)估軌跡劃分誤差測量方法。

3 仿真實(shí)驗(yàn)與結(jié)果分析

本節(jié)將對(duì)TPDV算法進(jìn)行仿真分析，評(píng)估TPDV在Geolife數(shù)據(jù)集上的性能。所有仿真都在配備有Windows 10、2.40 GHz CPU和16 GB內(nèi)存的PC上進(jìn)行。

3.1 數(shù)據(jù)集

以微軟研究Geolife項(xiàng)目中收集的182個(gè)用戶的軌跡數(shù)據(jù)作為仿真實(shí)驗(yàn)數(shù)據(jù)集。這些數(shù)據(jù)包含了一系列軌跡點(diǎn)，每一個(gè)點(diǎn)軌跡點(diǎn)包含經(jīng)緯度、時(shí)間戳等信息。

3.2 軌跡劃分方法的比較

表1 仿真參數(shù)設(shè)置

3.2.1 仿真1─與TPMF算法比較

首先比較了與同基于節(jié)點(diǎn)移動(dòng)特征進(jìn)行軌跡劃分的TPMF算法，測試了它們?cè)谶\(yùn)行時(shí)間、簡化率和軌跡劃分誤差三方面的性能。首先對(duì)節(jié)點(diǎn)1的所有軌跡進(jìn)行了劃分，仿真結(jié)果如圖3～圖5所示。

圖3 單節(jié)點(diǎn)運(yùn)行時(shí)間比較

圖4 單節(jié)點(diǎn)簡化率比較

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

圖5 單節(jié)點(diǎn)劃分誤差比較

為了獲得更準(zhǔn)確的實(shí)驗(yàn)結(jié)果，對(duì)更大量的軌跡點(diǎn)進(jìn)行了實(shí)驗(yàn)。為此從數(shù)據(jù)集中選擇了5個(gè)節(jié)點(diǎn)(Node 1、3、5、6、9)，仿真結(jié)果分別如圖6～圖8所示。

圖6 多節(jié)點(diǎn)運(yùn)行時(shí)間比較

圖7 多節(jié)點(diǎn)簡化率比較

圖8 多節(jié)點(diǎn)劃分誤差比較

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

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

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

圖9 運(yùn)行時(shí)間

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

圖10 簡化率

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

圖11 劃分誤差

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

綜合上述仿真結(jié)果，TPDV算法根據(jù)軌跡點(diǎn)速度和加速度提取特征點(diǎn)來對(duì)子軌跡進(jìn)行劃分，在簡化率和軌跡劃分誤差之間取得較好的平衡，同時(shí)也具備較低的時(shí)間復(fù)雜度。

4 結(jié)束語

軌跡劃分作為軌跡數(shù)據(jù)挖掘的一個(gè)主要步驟，該文提出了一種基于雙速度特征的軌跡劃分方法。該方法的突出優(yōu)點(diǎn)是全面考慮了節(jié)點(diǎn)的移動(dòng)特征，在去掉大量冗余點(diǎn)的情況下，保持了節(jié)點(diǎn)的移動(dòng)軌跡形狀骨架。未來的研究將關(guān)注TPDV方法中參數(shù)設(shè)置的自適應(yīng)解決方案，如參數(shù)

r

、

δ

和

β

的值。此外，還將研究基于TPDV的軌跡挖掘算法，以獲得節(jié)點(diǎn)的運(yùn)動(dòng)模式。