孫衛(wèi)真，林秋慧，向 勇，趙秋香

1(首都師范大學(xué) 信息工程學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，北京 100048) 2(清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系 網(wǎng)絡(luò)所，北京 100084) 3(山東省 濟(jì)寧市第一中學(xué) 高中數(shù)學(xué)組，山東 濟(jì)寧 272000)

1 引 言

由于GPS設(shè)備的逐漸普及，基于位置服務(wù)[1]的廣泛應(yīng)用等，位置信息的獲取變得愈加便捷.毫無疑問，這些數(shù)據(jù)的匯集將是海量的、個(gè)體連續(xù)的.個(gè)體連續(xù)的位置信息數(shù)據(jù)按照采樣時(shí)刻連接而成后，可以得到該運(yùn)動(dòng)對(duì)象的時(shí)空軌跡.海量的時(shí)空軌跡背后隱藏的信息帶動(dòng)了軌跡挖掘的發(fā)展，目前的應(yīng)用范圍涵蓋了包括交通監(jiān)管、人類行為、動(dòng)物遷徙、自然風(fēng)暴預(yù)測(cè)等等[2].因此，分析并聚類實(shí)時(shí)的海量時(shí)空軌跡數(shù)據(jù)，獲取典型的軌跡模式是非常有必要的.

然而，存儲(chǔ)開銷大、計(jì)算強(qiáng)度高、聚類幾何特征保留不完整等問題，是海量時(shí)空軌跡數(shù)據(jù)的聚類目前所面臨的主要挑戰(zhàn)[3,4].目前國(guó)內(nèi)外在軌跡聚類方面的研究中，主要有以下幾個(gè)方向[6]：基于數(shù)據(jù)的稀疏度、基于空間劃分、基于興趣點(diǎn)以及基于軌跡的幾何特征等.其中，基于數(shù)據(jù)的稀疏度的方法，屬于數(shù)據(jù)挖掘的通用方法[7]，但時(shí)間與空間復(fù)雜度都很高，不適用于海量時(shí)空軌跡的聚類；而基于空間劃分的方法，計(jì)算量相對(duì)較小，一般會(huì)結(jié)合LCSS方法并在明確的應(yīng)用場(chǎng)景下使用[6，8]；基于興趣點(diǎn)劃分的方法準(zhǔn)確度較差，且在興趣點(diǎn)較多的地區(qū)，軌跡的校準(zhǔn)與劃分將存在一定困難[9].而基于軌跡幾何特征方法的文獻(xiàn)則相對(duì)較少，其中，文獻(xiàn)[10]提出了一種基于結(jié)構(gòu)相似度的軌跡聚類算法，與軌跡的幾何特征有一定的的相關(guān)性，但其對(duì)原始軌跡的要求較高.Lee等人[2]在2007年提出了一種新的基于幾何形狀的聚類擬合軌跡的方法，其方法解決了復(fù)雜軌跡之間的比較問題，但是對(duì)軌跡進(jìn)行了近似描述，從而造成了軌跡的局部幾何特征丟失.

此外，實(shí)時(shí)海量的時(shí)空軌跡數(shù)據(jù)的聚類分析，還需考慮聚類的存儲(chǔ)與計(jì)算壓力的問題[11]，目前已有的解決時(shí)效性問題的主要方法集中在對(duì)聚類前的軌跡數(shù)據(jù)進(jìn)行簡(jiǎn)化[12，13].現(xiàn)有的軌跡數(shù)據(jù)的簡(jiǎn)化算法主要分為兩種[12]：一是局部軌跡數(shù)據(jù)簡(jiǎn)化，二是整體軌跡數(shù)據(jù)簡(jiǎn)化.局部軌跡數(shù)據(jù)的簡(jiǎn)化主要針對(duì)待處理點(diǎn)，綜合分析并處理與鄰域點(diǎn)間的簡(jiǎn)化關(guān)系，如距離閾值的過濾方法等[14].而整體的軌跡簡(jiǎn)化大致包括如下四種經(jīng)典的算法[3]：自頂向下(Top-Down，TD)[15]、自下而上、滑動(dòng)窗口、開放窗口(Opening Window，OW).其中，OW算法的窗口大小是動(dòng)態(tài)調(diào)整的，該算法適用于實(shí)時(shí)的流式軌跡數(shù)據(jù).然而經(jīng)典的OW算法在特殊軌跡的處理上并不理想，其一，其簡(jiǎn)化后的軌跡保留的拐角信息點(diǎn)過少[12]，導(dǎo)致減少了一些更準(zhǔn)確的軌跡行進(jìn)可能；其二，軌跡點(diǎn)過于密集時(shí)，其動(dòng)態(tài)滑動(dòng)窗口過長(zhǎng)，從而明顯增加計(jì)算量.余超等在文章[16]中提出的角度可變的滑動(dòng)窗口算法，能夠在轉(zhuǎn)角較大的情況下保留部分拐角軌跡點(diǎn).而TD算法對(duì)于處理有規(guī)律且比較直的密集軌跡點(diǎn)時(shí)，效率非常高，可以彌補(bǔ)OW算法的不足.其經(jīng)典方法有道格拉斯普克(Douglas-Peucher，DP)[4，13]算法，比較常見的有針對(duì)既定路線或網(wǎng)格的軌跡簡(jiǎn)化[5，17].

以上的文獻(xiàn)分析可以看出，實(shí)時(shí)海量時(shí)空軌跡聚類的首要問題是由于幾何特征丟失導(dǎo)致的聚類不準(zhǔn)確性[10].聚類的準(zhǔn)確性取決于相似性度量方法，現(xiàn)有的軌跡間相似性度量方法主要集中在軌跡間距離上.如圖1所示，軌跡1、2與軌跡1、3的歐氏距離和是相同的，即相似度一致，然而軌跡1與軌跡2的幾何形狀特征明顯不一致，這無法達(dá)到相似性度量的準(zhǔn)確性預(yù)期.此外，簡(jiǎn)化應(yīng)當(dāng)能夠保留必要的軌跡數(shù)據(jù)特征，而現(xiàn)有的軌跡數(shù)據(jù)簡(jiǎn)化方法不能直接應(yīng)用到這一場(chǎng)景中.因此，有必要設(shè)計(jì)一種海量時(shí)空軌跡聚類的算法，用以保留必要的軌跡幾何特征，并兼顧時(shí)效性和準(zhǔn)確性的問題.

圖1 歐式距離相似度不準(zhǔn)確性Fig.1 Inaccuracy of Euclidean distance similarity

針對(duì)海量時(shí)空軌跡的聚類，本文將貫徹時(shí)效性和準(zhǔn)確性兩大原則進(jìn)行闡述分析.首先，為減小計(jì)算量和存儲(chǔ)開銷，本文引入了一種綜合的軌跡簡(jiǎn)化策略，不僅充分考慮了軌跡的時(shí)間和空間要素，更加入了軌跡的形狀特征因素.著眼于簡(jiǎn)化后的時(shí)空軌跡數(shù)據(jù)的幾何特征，在前期的工作[18]中，我們結(jié)合計(jì)算幾何的方法對(duì)軌跡進(jìn)行擴(kuò)展，選擇了計(jì)算復(fù)雜度較低的軌跡梯形帶，定義了軌跡間的相似性度量方法.該方法可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算軌跡范圍，并判斷在不同時(shí)間跨度上的軌跡間相似性，在此基礎(chǔ)上，本文提出了海量時(shí)空軌跡的梯形帶相似聚類算法.該方法利用線性線段落在軌跡形成的梯形范圍內(nèi)長(zhǎng)度和本身長(zhǎng)度的比值定義相似，在充分考慮軌跡幾何特征的條件下，能夠較為快速地獲取時(shí)空軌跡的有效聚類結(jié)果.最后，經(jīng)海量真實(shí)時(shí)空軌跡數(shù)據(jù)測(cè)試集(北京市2010年04月06日出租車數(shù)據(jù))測(cè)試，本文方法能快速并合理保留細(xì)節(jié)特征地進(jìn)行軌跡數(shù)據(jù)簡(jiǎn)化，準(zhǔn)確有效地聚類同類軌跡并獲取合理的軌跡模式.

2 軌跡相似性度量

相似性度量作為軌跡聚類的標(biāo)準(zhǔn)，給出的定義越契合實(shí)際，軌跡聚類的效果也越好.此前的工作中，為減小計(jì)算量，采用梯形帶的方式簡(jiǎn)化了時(shí)空軌跡帶[18].眾所周知，聚類后的軌跡簇一般是分區(qū)域的，那些區(qū)域可大可小，形狀不一.分在一個(gè)簇中的軌跡定義為相似的，相對(duì)于簇而言，這些軌跡是細(xì)小的.將軌跡簇類比于時(shí)空軌跡的梯形帶，那么相似于該梯形帶的軌跡也是細(xì)小的.因此，如圖2所示，假設(shè)存在一個(gè)軌跡梯形帶，令其他的軌跡均與軌跡帶的中心軌跡進(jìn)行相似度匹配，即可得到有效的軌跡聚類，其直觀的度量標(biāo)準(zhǔn)為落在軌跡帶中軌跡長(zhǎng)度與軌跡原長(zhǎng)度的比值.

圖2 軌跡的梯形帶擴(kuò)展及相似性示意Fig.2 Trapezoidal belt of trajectory and similarity diagram

經(jīng)過以上論證，為更準(zhǔn)確的描述軌跡間相似性，本文將在已有研究的基礎(chǔ)上，增加軌跡的幾何特征因素，提出如下的軌跡相似性度量模型.

2.1 時(shí)空軌跡的定義

運(yùn)動(dòng)對(duì)象的時(shí)空軌跡是由一系列采樣點(diǎn)，按照采樣時(shí)刻的順序連接而成的.傳統(tǒng)的軌跡描述方法[19]主要利用二維空間坐標(biāo)，其缺點(diǎn)是，軌跡分類局限性較大，且無法非常準(zhǔn)確地描述一條軌跡.為提高軌跡聚類的有效性，參考文獻(xiàn)[20]的做法，利用運(yùn)動(dòng)物體的特定編號(hào)、空間坐標(biāo)、速度、方向等信息共同描述一條軌跡.

定義1.時(shí)空軌跡：一條時(shí)空軌跡可以表示為

Tr={(id,pi)|pi=(xi,yi,ti,vi,di)，i=1,2,…，n}

(1)

其中，id表示軌跡Tr的特定編號(hào)，也即唯一標(biāo)識(shí)，pi表示軌跡的第個(gè)采樣點(diǎn)，n表示軌跡的采樣點(diǎn)個(gè)數(shù)，(xi,yi)表示第i個(gè)采樣點(diǎn)的二維空間坐標(biāo)，(ti,vi,di)分別表示軌跡Tr在第i個(gè)采樣點(diǎn)位置的時(shí)間信息、速度信息和方向信息.

定義2.原始軌跡：原始數(shù)據(jù)經(jīng)過實(shí)時(shí)預(yù)處理后，按軌跡編號(hào)形成了一條條連續(xù)的軌跡.

(2)

定義3.軌跡模式：代表一組軌跡，初始聚類時(shí)，取原始軌跡中的一條經(jīng)準(zhǔn)確簡(jiǎn)化而成.在類中軌跡達(dá)到一定量時(shí)，擬合這類軌跡并簡(jiǎn)化，得到新的更合理的軌跡模式.

(3)

其中simiID為與該軌跡模式相似的原始軌跡的相似度similarity與oriID對(duì)的集合，初始為?.

2.2 時(shí)空軌跡梯形帶

定義4.時(shí)空軌跡梯形帶：表示如下

(4)

2.3 軌跡相交判斷

避免完全不可能相交的兩軌跡段進(jìn)行軌跡相似計(jì)算，能夠有效減少計(jì)算量，通過判定構(gòu)成軌跡段的基于坐標(biāo)系的最小矩形是否相交，能夠粗略地判定軌跡段是否相交.

定義5.相交粗判：設(shè)有兩點(diǎn)(xn,yn)、(xn+!,yn+1)，則兩點(diǎn)構(gòu)成的基于坐標(biāo)系的最小矩形為R，可以表示成R((xmin,ymin),(xmax,ymax))，其中(xmin,ymin)是R左下角點(diǎn)，(xmax,ymax)是的右上角點(diǎn).

(5)

2.4 軌跡相交長(zhǎng)度

1978年，Cyrus&Beck[21]提出了一種判斷直線與凸多邊形相交測(cè)試的算法—Cyrus&Beck裁剪算法(以下簡(jiǎn)稱CB算法)，其算法的復(fù)雜度為O(n).如圖3所示，除重合外，線段與多邊形相交主要有以下4種情況.

圖3 CB算法求解相交長(zhǎng)度Fig.3 CB algorithm for intersection length

本文采用了增加重合情況的算法，用以計(jì)算軌跡段與梯形帶的相似長(zhǎng)度.

LenCB(Apexi,pjpj+1)

(6)

2.5 軌跡的相似性計(jì)算

為衡量時(shí)空軌跡的幾何相似性，在判定軌跡段與軌跡帶的相交情況后，利用軌跡段落在軌跡帶中的長(zhǎng)度與軌跡段自身原長(zhǎng)的比值，可以描述為軌跡的幾何相似性.

定義7.基于梯形帶的軌跡相似性：原始軌跡Tro與軌跡模式Trm產(chǎn)生的梯形帶Tp進(jìn)行匹配，有軌跡段RIi-j=1.說明兩者可能相交，并可能產(chǎn)生軌跡段相似長(zhǎng)度.則軌跡Tro與Trm的擴(kuò)展梯形帶Tp的基于梯形帶的軌跡相似度(Trapezoidal Belt Based Similarity, TBST)可以表示為：

(7)

3 軌跡間的相似聚類算法

為實(shí)時(shí)處理海量真實(shí)的時(shí)空軌跡數(shù)據(jù)，通過對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，完成了清潔可用數(shù)據(jù)的獲取.為了保證實(shí)時(shí)海量時(shí)空軌跡聚類的時(shí)效性和準(zhǔn)確性，針對(duì)軌跡數(shù)據(jù)存在大量密集點(diǎn)和直線軌跡點(diǎn)等特征，提出了海量時(shí)空軌跡的梯形帶相似聚類算法(Feature Preserved-Trapezoidal Belt,FP-TB)，它包含2個(gè)階段.其一是綜合的特征保留簡(jiǎn)化算法，它在保證能夠保留軌跡幾何特征的條件下，盡可能地進(jìn)行數(shù)據(jù)存儲(chǔ)量的壓縮，并以不增加時(shí)間開銷為目的.其二是時(shí)空軌跡的梯形帶相似聚類算法，它在更優(yōu)的時(shí)間內(nèi)獲取更具價(jià)值的軌跡模式.下面將進(jìn)行更為具體的描述.

3.1 必要的軌跡簡(jiǎn)化策略

基于海量實(shí)時(shí)時(shí)空軌跡的時(shí)效性和準(zhǔn)確性的需求，本文在前述內(nèi)容的基礎(chǔ)上，為較快壓縮數(shù)據(jù)量、保留細(xì)節(jié)特征時(shí)盡量減少銳角并快速處理較長(zhǎng)的密集軌跡點(diǎn)，在軌跡數(shù)據(jù)簡(jiǎn)化方面，制定整體軌跡數(shù)據(jù)簡(jiǎn)化為主，局部軌跡數(shù)據(jù)簡(jiǎn)化為輔的綜合軌跡壓縮算法，以達(dá)到快速并合理保留軌跡特征地進(jìn)行軌跡數(shù)據(jù)壓縮.

其中，局部鄰域點(diǎn)簡(jiǎn)化(Neighborhood Points Compression，NPC)的核心思想在于，綜合分析待處理點(diǎn)與鄰域點(diǎn)，較快壓縮數(shù)據(jù)量.而整體軌跡數(shù)據(jù)簡(jiǎn)化的算法又包含有兩種，一種是帶銳角限制的開窗算法(Angle Limited Opening Window，ALOW)，用于整體的動(dòng)態(tài)簡(jiǎn)化并保留一些較為特殊的軌跡局部特征；另一種是針對(duì)擁有大量較為筆直的軌跡點(diǎn)，利用DP算法直接進(jìn)行軌跡簡(jiǎn)化.實(shí)時(shí)動(dòng)態(tài)簡(jiǎn)化以NPC算法為第一道關(guān)卡，ALOW算法為主要的簡(jiǎn)化方法，在點(diǎn)閾值達(dá)到一定程度時(shí)再觸發(fā)DP算法，三者相輔相成.以下是詳細(xì)的算法描述.

算法1.綜合的特征保留簡(jiǎn)化算法(Feature Preserved Simplification，F(xiàn)P).

輸入：原始軌跡Tro，局部簡(jiǎn)化閾值SUBSIMPTHR，整體簡(jiǎn)化閾值SIMPTHR，長(zhǎng)直軌跡點(diǎn)閾值PTTHR

輸出：簡(jiǎn)化后的軌跡Trosimp

算法步驟：

1)initialize(SUBSIMPTHR，SIMPTHR，PTTHR)；//初始簡(jiǎn)化閾值

2)copyInfo(Tro，Trosimp)//復(fù)制軌跡基本信息到簡(jiǎn)化軌跡中

3)addp1toTrosimp//將軌跡起始點(diǎn)放入簡(jiǎn)化軌跡中

4)for(next= 1；next≤n；next++){

5)for(i= 1；i≤n-next；i++){ //NPC算法

6)if(Dist(pnext,pnext+i)>SUBSIMPTHR){

7) delete {pnext+1,pnext+i-1} fromTro；

8)break；

9) }

10) }

11) countDP = 0；//用于觸發(fā)DP算法的flag

12)for(j= 1；j≤n-next-i；j++){//ALOW算法

13) LPDist=

Dist(Line(pnext,pnext+i+j),pnext+i+K),K∈[0,j)；

14)if(LPDist

15) countDP++；

16)else{

17) Kmax=MAX(LPDist)；//當(dāng)有距離超過SIMPTHR時(shí)，選擇距離最大的浮動(dòng)點(diǎn)

18)Qobt=FIRSTAngle(∠pbeforepnextpnext+i+Q>90°)

‖MAXAngle(∠pbeforepnextpnext+i+Q>90°),

Q∈[Kmax,0]

//注意向前浮動(dòng)

19) addpnext+i+QobttoTrosimp；//浮動(dòng)點(diǎn)放入簡(jiǎn)化軌跡

20)next=next+i+Qobt，countDP=0；

21) }

22)if(countDP ≥PTTHR){

23) //超過軌跡點(diǎn)閾值PTTHR，觸發(fā)DP算法.

24) addpnext+i+jtoTrosimp；

25) dpLine(pnext，pnext+i+j)；

26) countDP=0，next=next+i+j；

27) }

28) }

29)}

30)returnTrosimp；

算法1是一個(gè)特征保留的軌跡簡(jiǎn)化算法，它首先選擇從待簡(jiǎn)化的原始軌跡Tro中，取第一個(gè)點(diǎn)作為簡(jiǎn)化軌跡Trosimp的起始點(diǎn)，其后續(xù)進(jìn)入的每一個(gè)點(diǎn)，均先與前一個(gè)簡(jiǎn)化后的點(diǎn)進(jìn)行NPC算法，再按照如下的ALOW算法簡(jiǎn)化軌跡段.

前一條簡(jiǎn)化后的軌跡段末端點(diǎn)作為起始點(diǎn)，從該點(diǎn)開始處理后面連續(xù)的n(n>=3)個(gè)點(diǎn)，第n個(gè)點(diǎn)設(shè)為浮動(dòng)點(diǎn)：過起始點(diǎn)和浮動(dòng)點(diǎn)做一條直線，分別計(jì)算中間n-2個(gè)點(diǎn)到直線的距離LPDist，若所有距離均小于距離閾值，則下一個(gè)數(shù)據(jù)點(diǎn)設(shè)為浮動(dòng)點(diǎn)，計(jì)數(shù)；否則，選取與直線距離最大的點(diǎn)作為浮動(dòng)點(diǎn)，進(jìn)行“浮動(dòng)點(diǎn)前移”：從該浮動(dòng)點(diǎn)向前到起始點(diǎn)的下一點(diǎn)，依次作為浮動(dòng)點(diǎn)計(jì)算三個(gè)點(diǎn)之間的夾角，利用函數(shù)FIRSTAngle選取浮動(dòng)點(diǎn)，該浮動(dòng)點(diǎn)是第一個(gè)和起始點(diǎn)間的軌跡段與前一條軌跡段成鈍角的點(diǎn)，將該浮動(dòng)點(diǎn)加入到簡(jiǎn)化軌跡Trosimp中，并成為下一個(gè)起始點(diǎn)；若所有兩軌跡段間的夾角都不大于90°，則利用函數(shù)MAXAngle選取與前一條軌跡段成最大角的浮動(dòng)點(diǎn)加入到簡(jiǎn)化軌跡Trosimp中，作為下一次循環(huán)的起始點(diǎn).

當(dāng)在ALOW算法簡(jiǎn)化過程中的計(jì)數(shù)超過閾值時(shí)，觸發(fā)DP算法函數(shù)dpLine，將所有當(dāng)前未處理的點(diǎn)取出，并將首尾兩點(diǎn)存入簡(jiǎn)化軌跡Trosimp中，連接這兩點(diǎn)，計(jì)算中間所有點(diǎn)到該線的距離，若超過閾值，則將距離最大的點(diǎn)存入Trosimp中；連接首尾兩點(diǎn)，得到兩條直線，重復(fù)前述步驟，直到所有點(diǎn)到直線的距離均不超過閾值為止.

該算法得到的簡(jiǎn)化軌跡，通過NPC算法減小了OW算法的繁復(fù)計(jì)算壓力，利用DP算法的優(yōu)勢(shì)緩解了OW算法在處理長(zhǎng)直軌跡點(diǎn)時(shí)的計(jì)算壓力，銳角特性的加入，則使得最終得到的簡(jiǎn)化軌跡保留了一定的細(xì)節(jié)特征，能有效地應(yīng)用于實(shí)際場(chǎng)景中，同時(shí)為后續(xù)的聚類分析減小了較大的工作量.

3.2 海量時(shí)空軌跡的梯形帶相似聚類

本文的相似性度量標(biāo)準(zhǔn)，基于軌跡的幾何特征，在擴(kuò)展簡(jiǎn)化后的軌跡模式Trm為梯形帶后，采用原始軌跡Tro落在軌跡模式Trm中的軌跡相似長(zhǎng)度和，與原始軌跡Tro的長(zhǎng)度比值來進(jìn)行定義.這種方法，彌補(bǔ)了歐氏距離對(duì)軌跡幾何特征的忽略，解決了采用多邊形重合面積比定義相似性的不穩(wěn)定問題.基于此，軌跡便能夠得到較好的聚類，并能夠得到更能代表聚類軌跡特征的軌跡模式.具體算法如下：

算法2.海量時(shí)空軌跡的梯形帶相似聚類算法(Trapezoidal Belt Based Clustering，TB).

輸入：原始軌跡集合I={Troi,i=1,2,…,k}，其中原始軌跡為實(shí)時(shí)增加的；軌跡模式集合Q={Trmi,i=1,2,…,s}，初始為空集?，隨聚類的進(jìn)行而增長(zhǎng)；相關(guān)參數(shù)：軌跡帶寬度WIDTH，相似度閾值SIMILARTHR

輸出：軌跡模式類集合Q

算法步驟：

1)initialize(WIDTH，SIMILARTHR)；//初始梯形帶寬度、相似度閾值

2)Q=?；//初始化軌跡模式類集合Q為空集

3)for(eachTrokin theI){ //遍歷集合的原始軌跡

4)if(Q==?){

5) createNewTrm(Tro，Trm)；//生成第一條軌跡模式Trm

6) addTrmtoQ；//將Trm加入到軌跡模式類集合Q中

7) }

8)else{

9) similarflag=false；

10)for(eachTrmsin theQ){ //遍歷集合Q的軌跡模式

11) creatApex(Trms，WIDTH)；//依據(jù)軌跡帶寬度生成軌跡模式梯形帶

13)if(TBBS>SIMILARTHR){

14) add(TBBS，ido)tosimiID；//維護(hù)當(dāng)前Trm的simiID

15) similarflag=true；

16) }

17) }

18)if(similarflag ==false){

19) createNewTrm(Tro，Trm)；

20) addTrmtoQ；//將Trm加入到軌跡模式類集合Q中

21) }

22) }

23)}

算法2在初始時(shí)，初始化軌跡模式集合Q為空集，相關(guān)參數(shù)的梯形帶寬度WIDTH和相似度閾值SIMILARTHR.對(duì)所有在原始軌跡集合I中的所有原始軌跡，與所有在軌跡模式集合Q中的每一條軌跡模式進(jìn)行相似度計(jì)算.首先生成簡(jiǎn)化后的軌跡模式梯形帶，采用前述的相似性度量模型，計(jì)算兩軌跡間的相似度TBBS的值.繼而判斷當(dāng)相似度的值大于相似度閾值SIMILARTHR時(shí)，認(rèn)為該原始軌跡Tro與當(dāng)前Trm相似，維護(hù)當(dāng)前Trm的simiID集合，從而達(dá)到聚類效果.最后，若當(dāng)前軌跡模式集合Q中沒有任何一條軌跡模式Trm與該原始軌跡Tro相似的話，依據(jù)該原始軌跡Tro生成一條軌跡模式Trm并參與后續(xù)計(jì)算.

從此處可以看出，軌跡模式所含數(shù)據(jù)點(diǎn)越多，則軌跡模式段越多，軌跡模式所對(duì)應(yīng)的梯形帶中所含梯形越多，這樣，計(jì)算原始軌跡在梯形帶內(nèi)的長(zhǎng)度時(shí)，計(jì)算量就會(huì)越大，所以，軌跡模式是簡(jiǎn)化后的軌跡，而且，簡(jiǎn)化后的軌跡做軌跡模式與原始軌跡計(jì)算的相似度和未簡(jiǎn)化前的軌跡做軌跡模式與原始軌跡計(jì)算相似度，兩者相似度相差不大，而前者的計(jì)算量則較后者大大減小了.

3.3 算法時(shí)間復(fù)雜性分析

在給出具體算法的基礎(chǔ)上，分析算法的時(shí)間復(fù)雜度是很有必要的.通過時(shí)間復(fù)雜度的分析，能夠進(jìn)一步的改進(jìn)和優(yōu)化算法的結(jié)構(gòu)，以達(dá)到更加實(shí)時(shí)高效的目的.

算法1是一個(gè)綜合特征保留的軌跡簡(jiǎn)化算法，為了追求最好的效率，可能需要反復(fù)執(zhí)行，反復(fù)對(duì)軌跡點(diǎn)進(jìn)行簡(jiǎn)化，進(jìn)而減少軌跡點(diǎn)的數(shù)量，對(duì)m條軌跡，其執(zhí)行次數(shù)為O(m).對(duì)每個(gè)被保留的軌跡點(diǎn)而言，需要在其他剩余的軌跡點(diǎn)中，尋找下一個(gè)被保留點(diǎn)，候選的軌跡點(diǎn)共有O(n)個(gè).因此，每次執(zhí)行的算法時(shí)間復(fù)雜度最差為O(n2)，最好的情況為O(log2n)，其中n表示軌跡集合中軌跡的數(shù)量.

算法2是海量時(shí)空軌跡的梯形帶相似聚類算法，針對(duì)算法1產(chǎn)生的軌跡集合形成的原始軌跡，其軌跡的平均長(zhǎng)度為O(n-1)，對(duì)于每個(gè)軌跡點(diǎn)，需要在m條軌跡模式中進(jìn)行相似度擬合，因此，算法2的時(shí)間復(fù)雜度為O(n-1)O(m).

其中，算法2由于原始軌跡的個(gè)數(shù)是實(shí)時(shí)增加的，其執(zhí)行的效率主要取決于在聚類過程中形成的軌跡模式條數(shù)，當(dāng)軌跡模式較少，其執(zhí)行效率較高，反之，執(zhí)行效率降低.目前本算法對(duì)待軌跡模式的增加主要取決于軌跡間相似度的閾值，后續(xù)將會(huì)基于此進(jìn)行有效的改進(jìn).

以上分析可知，本文提出的FP-TB算法，在計(jì)算軌跡相似性時(shí)，增加了特征保留的軌跡點(diǎn)簡(jiǎn)化，減少了大量的軌跡點(diǎn)，其對(duì)較為筆直和密集軌跡點(diǎn)的簡(jiǎn)化大大提高了軌跡的簡(jiǎn)化執(zhí)行效率，利用這些簡(jiǎn)化后的軌跡點(diǎn)進(jìn)行相似度計(jì)算，充分減少了計(jì)算量.增加的軌跡幾何形狀的因素，則使得本算法所得的軌跡聚類結(jié)果更加準(zhǔn)確.

4 測(cè)試與性能分析

在實(shí)驗(yàn)部分，采用真實(shí)數(shù)據(jù)擴(kuò)展的數(shù)據(jù)集對(duì)算法的可用性進(jìn)行分析.其中真實(shí)數(shù)據(jù)集為2010年04月06日的30382520條北京市出租車數(shù)據(jù)，通過過濾得到較為清潔的數(shù)據(jù)，并在此基礎(chǔ)上利用空車與重車標(biāo)志位分割軌跡，共得到可用軌跡35380條.使用該數(shù)據(jù)集的優(yōu)勢(shì)在于，它包含大量的軌跡信息，包括軌跡的速度、角度、時(shí)間、位置信息、軌跡標(biāo)識(shí)、類別信息等，并且這些軌跡信息都是真實(shí)的，其軌跡出現(xiàn)的情況均為真實(shí)應(yīng)用環(huán)境的情形，能夠驗(yàn)證本文所述方法的真實(shí)有效性.

實(shí)驗(yàn)的硬件環(huán)境為：服務(wù)器端Ubuntu 14.04，內(nèi)存2.00GB，數(shù)據(jù)庫(kù)端為Windows 7系統(tǒng)，安裝Oracle DB 11g，算法實(shí)現(xiàn)代碼為C++，并均在服務(wù)器終端進(jìn)行測(cè)試運(yùn)行.

4.1 軌跡簡(jiǎn)化的實(shí)驗(yàn)結(jié)果

4.1.1 軌跡簡(jiǎn)化算法的幾何特征保留情況

本文提出的特征保留的軌跡簡(jiǎn)化算法FP，其主要目標(biāo)是在不影響軌跡簡(jiǎn)化速率的基礎(chǔ)下，盡可能多的保留原始軌跡的有效特征.以較小的空間開銷，保留更多的軌跡特征，其軌跡的可用性越高，反之亦然.在該算法中，有三個(gè)閾值需要確定，其中僅有SIMPTHR閾值是與簡(jiǎn)化效果密切相關(guān)的距離閾值.

由于其距離閾值所針對(duì)的點(diǎn)均為地圖上的點(diǎn)，而就中國(guó)的情況而言，緯度范圍從3°51′N至53°33′N，跨度較大，因此不適合在任意緯度指定固定的閾值.為了獲取更為合理的閾值，在指定閾值時(shí)，以千米km為單位，指定閾值為αkm，則不同緯度的緯度閾值由以下公式(8)換算得到：

(8)

下面的實(shí)驗(yàn)結(jié)果展現(xiàn)了在不同α值決定的SIMPTHR閾值下，本文算法FP與OW算法所得的簡(jiǎn)化軌跡的對(duì)比結(jié)果.

圖4-圖6中虛線均代表原始軌跡，共17個(gè)點(diǎn)，左圖的實(shí)線為OW算法簡(jiǎn)化后的軌跡，右圖實(shí)線則是本文算法FP簡(jiǎn)化后的軌跡.如圖5所示，在本文的算法中，在保留了原始軌跡中的第8個(gè)點(diǎn)之后，若利用OW算法則下一個(gè)點(diǎn)為第10個(gè)點(diǎn)(即左圖算法中保留的第6個(gè)點(diǎn))，由于第8個(gè)點(diǎn)和前一個(gè)被保留點(diǎn)所成的線段與第8、10個(gè)點(diǎn)所成的線段夾角為銳角，本文的算法利用“浮動(dòng)點(diǎn)前移”，到第9個(gè)點(diǎn)(即右圖中保留的第7個(gè)點(diǎn))，使得兩者之間的夾角不是銳角.利用OW算法簡(jiǎn)化后的軌跡均含有1個(gè)銳角，而本文算法FP簡(jiǎn)化后的軌跡則不含銳角，且簡(jiǎn)化結(jié)果較為穩(wěn)定.

圖4 值為0.01km時(shí)OW與FP的簡(jiǎn)化效果Fig.4 Simplified results of OW and FP at α=0.01km

圖5 值為0.02km時(shí)OW與FP的簡(jiǎn)化效果Fig.5 Simplified results of OW and FP at α=0.02km

圖6 值為0.03km時(shí)OW與FP的簡(jiǎn)化效果Fig.6 Simplified results of OW and FP at α=0.03km

縱向比較圖4、圖5、圖6可知，隨著α值為0.01km、0.02km、0.03km，OW算法僅在值較小時(shí)才能保留原始軌跡的幾何特征，而本文的算法FP，則能夠在較大范圍內(nèi)均保持簡(jiǎn)化后的原始軌跡不失真.因此，本文算法FP較OW算法在實(shí)際應(yīng)用中更為廣泛.

4.1.2 執(zhí)行時(shí)間比較

本文所使用的真實(shí)的出租車數(shù)據(jù)集中，存在個(gè)體連續(xù)的大量密集點(diǎn)、較長(zhǎng)時(shí)間的直線行駛和部分大型立交橋的轉(zhuǎn)彎行駛軌跡點(diǎn)，因此該簡(jiǎn)化算法主要基于以上的數(shù)據(jù)特征進(jìn)行.描述的是，在使用α=0.02km時(shí)，OW、ALOW以及本文所述的FP簡(jiǎn)化算法，在壓縮率及執(zhí)行時(shí)間方面的表現(xiàn).其中，簡(jiǎn)化的總點(diǎn)數(shù)W為3651685個(gè)點(diǎn)，形成了35380條原始軌跡.

結(jié)合上述實(shí)驗(yàn)一及表1數(shù)據(jù)可以得到，本文的綜合特征保留算法FP的簡(jiǎn)化較OW算法能夠保留更多原始軌跡的特征點(diǎn)，約多了6.75%.由于壓縮率數(shù)值越大，壓縮后的軌跡點(diǎn)所需的存儲(chǔ)空間也越大，而本文算法FP較OW算法的整體壓縮率增加了2.01%，存儲(chǔ)空間開銷隨之增大，但這一比例屬于存儲(chǔ)的可接受范圍.而對(duì)比ALOW算法，本文算法FP保留的軌跡點(diǎn)總數(shù)約少了2.36%，整體壓縮率減少了0.77%.這一差異性是由于NPC及DP算法的簡(jiǎn)化造成的，而在執(zhí)行時(shí)間減少諸多的情況下，這一情況基本可以忽略.

表1 各簡(jiǎn)化算法的壓縮率及執(zhí)行時(shí)間Table 1 Compression rate and execution time of each algorithm

通過觀察表1可以發(fā)現(xiàn)，同等實(shí)驗(yàn)條件下，純粹的ALOW算法由于其時(shí)間復(fù)雜性較OW算法高，其運(yùn)行時(shí)間較OW算法高出約13%.對(duì)于海量的軌跡數(shù)據(jù)而言，時(shí)間上的開銷是較難容忍的，因此需要對(duì)ALOW算法做進(jìn)一步的改進(jìn).同樣地，從上表也可以看出，本文的FP算法較OW算法的運(yùn)行時(shí)間縮短了約25.82%，較純粹的ALOW算法的執(zhí)行時(shí)間縮短了約34.17%.這主要是因?yàn)镹PC和DP算法有效地簡(jiǎn)化和壓縮了這些增長(zhǎng)的密集點(diǎn)和長(zhǎng)直點(diǎn)，減小了ALOW以及OW算法的窗口，迭代次數(shù)隨之減少，執(zhí)行的時(shí)間自然減少.以上數(shù)據(jù)結(jié)果說明，增加了NPC算法和DP算法來進(jìn)行執(zhí)行效率上的改進(jìn)結(jié)果是卓有成效的，達(dá)到了縮短執(zhí)行時(shí)間的目的.因此本文提供的FP算法是有效的，且更為高效的.

4.2 軌跡聚類的實(shí)驗(yàn)結(jié)果

4.2.1 梯形帶寬度width對(duì)軌跡間相似的影響

本文提出的海量時(shí)空軌跡的梯形帶相似聚類算法FP-TB中，閾值width是影響軌跡間相似判斷的主要因素.下面是實(shí)驗(yàn)獲取的某一類軌跡模式聚類的實(shí)驗(yàn)結(jié)果，展現(xiàn)了在不同的width取值下，本文算法FP-TB在同一類軌跡中，其平均相似度的變化.

圖7 不同width下同類軌跡的平均相似度Fig.7 Average similarity of similar trajectories under different width

其中灰色底帶表示軌跡模式，黑色線條表示與之相似的原始軌跡，閾值width是影響梯形帶的半帶寬.

圖7(a)顯示的是width=0.04km時(shí)，直線型軌跡的其中一類所有相似軌跡與軌跡模式的相似度平均值，其相似度平均值顯示為0.765518.圖7(b)顯示的是width=0.05km時(shí)，直線型軌跡的其中一類所有相似軌跡與軌跡模式的相似度平均值，其相似度平均值顯示為0.818084.

根據(jù)以上的實(shí)驗(yàn)結(jié)果，橫向比較圖7(a)與圖7(b)不難得出，隨著梯形半帶寬width值的增大，其聚類的軌跡相似度平均值也隨之增大，這說明類中的原始軌跡與軌跡模式的相似度也是增大的.這是符合前文所述相似性度量的結(jié)果，因此本文提供的FP-TB算法的相似性度量模型是行之有效的，且能準(zhǔn)確有效的進(jìn)行各類軌跡的聚類.

4.2.2 軌跡聚類結(jié)果及執(zhí)行時(shí)間的比較分析

本文所用的真實(shí)出租車數(shù)據(jù)集，具有幾何走勢(shì)明顯的特征，對(duì)于這類軌跡，其主要目標(biāo)是盡可能保證軌跡聚類的準(zhǔn)確性，并挖掘出有價(jià)值的軌跡模式信息.本文從35380條原始軌跡中進(jìn)行挖掘，其獲取的軌跡模式較多，下面將舉例給出直線型軌跡模式和環(huán)型軌跡模式的聚類結(jié)果，以驗(yàn)證聚類的有效性，其梯形帶寬度width=0.05km，軌跡的相似度閾值SIMILARTHR=0.65.

圖8 不同類型的軌跡聚類結(jié)果Fig.8 Clustering results of different types of trajectories

圖8顯示的是根據(jù)本文所給的相似性度量模型，對(duì)原始軌跡集合進(jìn)行聚類后所得的不同類型的軌跡模式.圖8(a)顯示的是簡(jiǎn)單的直線型軌跡模式，其基本呈直線走勢(shì)，表明了所有與該直線型軌跡模式相似的原始軌跡的平均相似度為0.716002.參照北京市地圖可以發(fā)現(xiàn)，該軌跡模式表示去往首都機(jī)場(chǎng)的機(jī)場(chǎng)線路徑，說明在一天內(nèi)，出租車去往首都機(jī)場(chǎng)的出行頻次是較高的.圖8(b)顯示的則是環(huán)型軌跡模式，其走勢(shì)為閉合的環(huán)線，圖中表明所有與該環(huán)型軌跡模式相似的原始軌跡的平均相似度為0.770505.該軌跡模式表示由西便門橋、右安門橋、左安門橋、東便門橋所形成的環(huán)線，并去往雙井橋附近.該區(qū)域有較多辦公大樓，屬于出租車司機(jī)的長(zhǎng)期巡客區(qū)域，而雙井附近有較多居民區(qū)，因此這一路線也是出租車經(jīng)常會(huì)走的路線.這些軌跡模式均符合北京市的實(shí)際交通路況，說明本文的相似性度量模型對(duì)于各類軌跡模式均是有效的，而環(huán)型軌跡中保留的部分拐角信息，則是出于幾何特征保留的考慮，由此可見，該聚類結(jié)果具備準(zhǔn)確性.

此外，為定量比較聚類結(jié)果的執(zhí)行時(shí)間，做了如下的幾組實(shí)驗(yàn)來驗(yàn)證.其中軌跡模式A、B分別是軌跡模式A′、B′簡(jiǎn)化后的軌跡，與之聚類的原始軌跡為簡(jiǎn)化后的35380條出租車軌跡.

通過3.3的算法分析可知，本文所述的FP-TB算法其執(zhí)行效率主要取決于軌跡模式的條數(shù)和單條軌跡模式的段數(shù)，其中軌跡模式條數(shù)主要由原始軌跡數(shù)據(jù)集決定.由表2可以看出，相同的軌跡在簡(jiǎn)化前后聚類所得的原始軌跡集合相差不大，其平均相似度的差別亦不大.而簡(jiǎn)化后的軌跡聚類時(shí)間大約都減少了50%，其中軌跡模式A較軌跡模式A′的聚類執(zhí)行時(shí)間減少了52.2732%，軌跡模式B較軌跡模式B′的聚類執(zhí)行時(shí)間減少了59.5798%.

表2 FP-TB算法與僅TB的聚類方法的執(zhí)行時(shí)間比較Table 2 Comparison of the execution time between FP-TB and TB clustering method

綜合在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)測(cè)試可以發(fā)現(xiàn)，本文提出的FP-TB算法可用性較高，并在考慮到軌跡幾何特征后，能夠在不影響執(zhí)行時(shí)間的情況下保留重要的原始軌跡特征.在此基礎(chǔ)上，通過提出的相似性度量模型，計(jì)算原始軌跡落在軌跡模式梯形帶內(nèi)的長(zhǎng)度總和與原始軌跡線段的長(zhǎng)度和之比定義相似性，對(duì)原始軌跡進(jìn)行準(zhǔn)確聚類，這一聚類方法能夠有效地對(duì)包括直線型與環(huán)型交叉等各類軌跡進(jìn)行聚類，且執(zhí)行時(shí)間較不經(jīng)過處理直接進(jìn)行聚類的方法快了近50%.因此，本文提出的FP-TB聚類算法是行之有效的.

5 結(jié)束語

本文在分析了海量時(shí)空軌跡數(shù)據(jù)的空間和時(shí)間特性后，考慮到已有的聚類算法在計(jì)算軌跡相似性時(shí)忽略了軌跡的幾何特征對(duì)聚類結(jié)果的影響，導(dǎo)致獲取的軌跡模式的部分重要細(xì)節(jié)特征失真的問題，針對(duì)出租車數(shù)據(jù)特征進(jìn)行的軌跡挖掘，提出了FP-TB算法.第一階段的FP算法從存儲(chǔ)效率和保留簡(jiǎn)化后的細(xì)節(jié)特征出發(fā)，制定了整體簡(jiǎn)化為主，局部簡(jiǎn)化為輔的軌跡簡(jiǎn)化方案.第二階段的TB算法，增加軌跡幾何特征的影響因素，提出了一種新的相似性度量模型.并以此為主要依據(jù)并通過一定的相似度閾值準(zhǔn)確篩選和挖掘相似的時(shí)空軌跡簇，進(jìn)行海量時(shí)空軌跡的聚類分析.通過真實(shí)軌跡數(shù)據(jù)集上的實(shí)驗(yàn)可以看出，本文算法在保留更多的軌跡原始特征的情況下，能夠準(zhǔn)確有效地聚類同類軌跡以獲取典型的出租車行駛軌跡；而對(duì)不同類的軌跡，其執(zhí)行效率均有不同程度的提升，因此具有更高的實(shí)際意義.

在未來的研究工作中，我們將考慮在聚類過程中軌跡模式的局部增刪與軌跡模式本身的動(dòng)態(tài)調(diào)整，以獲取更切合實(shí)際的軌跡模式，減小計(jì)算開銷.

[1] Gruteser M，Grunwald D.Anonymous usage of location-based services through spatial and temporal cloaking[C].Proceedings of the 1st International Conference on Mobile Systems，Applications and Services，ACM，2003：31-42.

[2] 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.

[3] Keogh E，Chu S，Hart D，et al.An online algorithm for segmenting time series[C].Data Mining，ICDM 2001，Proceedings IEEE International Conference on.IEEE，2001：289-296.

[4] Meratnia N，Rolf A.Spatiotemporal compression techniques for moving point objects[C].International Conference on Extending Database Technology，Springer Berlin Heidelberg，2004：765-782.

[5] Muckell J，Hwang J H，Lawson C T，et al.Algorithms for compressing GPS trajectory data：an empirical evaluation[C].Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems，ACM，2010：402-405.

[6] Su H，Zheng K，Wang H，et al.Calibrating trajectory data for similarity-based analysis[C].Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data，ACM，2013：833-844.

[7] Simoudis E，Livezey B K，Kerber R G.Method for generating predictive models in a computer system：U.S.Patent 5，692，107[P].1997-11-25.

[8] Su H，Zheng K，Huang J，et al.Calibrating trajectory data for spatio-temporal similarity analysis[J].The VLDB Journal，2015，24(1)：93-116.

[9] Fu Z，Hu W，Tan T.Similarity based vehicle trajectory clustering and anomaly detection[C].Image Processing，2005.ICIP，IEEE International Conference on.IEEE，2005，2：II-602.

[10] Yuan Guan，Xia Shi-xiong,Zhang Lei，et al.Trajectory clustering algorithm based on structural similarity[J].Journal on Communications，2011，32(9)：103-110.

[11] Thuraisingham B，Khan L，Clifton C，et al.Dependable real-time data mining[C].Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing,IEEE Computer Society，2005：158-165.

[12] Chen Y，Jiang K，Zheng Y，et al.Trajectory simplification method for location-based social networking services[C].Proceedings of the 2009 International Workshop on Location Based Social Networks，ACM，2009：33-40.

[13] Douglas D H，Peucker T K.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].Cartographica：The International Journal for Geographic Information and Geovisualization，1973，10(2)：112-122.

[14] Tobler W R.Numerical map generalization，and notes on the analysis of geographical distributions[M].Department of Geography，University of Michigan，1966.

[15] Hershberger J E，Snoeyink J.Speeding up the douglas-peucker line-simplification algorithm[M].University of British Columbia，Department of Computer Science，1992.

[16] Yu Chao,Guo Qing，Xie Wen-jun，et al.A method of fast geomagnetic matching based on orientation alterable sliding window[J].Computer Simulation，2015，32(3)：86-89.

[17] Yu J，Chen G，Zhang X，et al.An improved Douglas-peucker algorithm aimed at simplifying natural shoreline into direction-line[C].Geoinformatics(GEOINFORMATICS)，2013 21st International Conference on.IEEE，2013：1-5.

[18] Zhao Qiu-xiang.Trajectory clustering algorithm based on trapezoid belt similarity measure[D].Beijing：Graduate School of Beijing Normal University，2015.

[19] Hwang J R，Kang H Y，Li K J.Spatio-temporal similarity analysis between trajectories on road networks[C].International Conference on Conceptual Modeling，Springer Berlin Heidelberg，2005：280-289.

[20] Hu Hong-yu.Research on methods for traffic event recognition based on video processing[D].Changchun：Jilin University，2010.

[21] Cyrus M，Beck J.Generalized two-and three-dimensional clipping[J].Computers & Graphics，1978，3(1)：23-28.

附中文參考文獻(xiàn)：

[10] 袁 冠，夏士雄，張 磊，等.基于結(jié)構(gòu)相似度的軌跡聚類算法[J].通信學(xué)報(bào)，2011，32(9)：103-110.

[16] 余 超，郭 慶，謝文俊，等.地磁導(dǎo)航基于方向可變滑動(dòng)窗口快速匹配方法[J].計(jì)算機(jī)仿真，2015，32(3)：86-89.

[18] 趙秋香.基于梯形帶相似性度量的軌跡聚類算法[D].北京：北京師范大學(xué)，2015.

[20] 胡宏宇.基于視頻處理的交通事件識(shí)別方法研究[D].長(zhǎng)春：吉林大學(xué)，2010.