基于行為特征相似度的船舶軌跡聚類(lèi)方法*

張春瑋 馬 杰 牛元淼 劉 琪

(武漢理工大學(xué)航運(yùn)學(xué)院1) 武漢 430063) (湖北省內(nèi)河航運(yùn)技術(shù)重點(diǎn)實(shí)驗(yàn)室2) 武漢 430063) (國(guó)家水運(yùn)安全工程技術(shù)研究中心3) 武漢 430063)

0 引 言

船舶軌跡是表現(xiàn)船舶運(yùn)動(dòng)的最直觀形式，海量的軌跡數(shù)據(jù)中蘊(yùn)藏了豐富的交通特征規(guī)律和船舶運(yùn)動(dòng)模式等信息.對(duì)船舶軌跡數(shù)據(jù)進(jìn)行聚類(lèi)分析，可為船舶交通流特征提取、航路安全規(guī)劃和推薦、船舶異常行為檢測(cè)等技術(shù)研發(fā)和應(yīng)用提供基礎(chǔ)手段和關(guān)鍵方法，為航運(yùn)規(guī)劃、海事監(jiān)管等工作開(kāi)展提供決策支持和科學(xué)依據(jù)[1].

船舶AIS系統(tǒng)已成為當(dāng)前船舶交通監(jiān)控和管理的重要工具，利用AIS數(shù)據(jù)可提取船舶航行的多個(gè)維度信息，即可得到船舶軌跡連續(xù)移動(dòng)位置點(diǎn)，又可獲取不同位置點(diǎn)上的速度、航向等船舶運(yùn)動(dòng)狀態(tài)參量.因此，AIS數(shù)據(jù)非常適于船舶軌跡聚類(lèi)分析[2]、船舶行為模式挖掘等相關(guān)研究[3].

目前，利用AIS數(shù)據(jù)進(jìn)行船舶軌跡聚類(lèi)研究主要有兩種模式：基于軌跡點(diǎn)的聚類(lèi)和基于軌跡段的聚類(lèi).軌跡點(diǎn)聚類(lèi)以目標(biāo)對(duì)象運(yùn)動(dòng)的位置散點(diǎn)(如經(jīng)緯度坐標(biāo)值)為聚類(lèi)樣本進(jìn)行簇群劃分，進(jìn)而研究目標(biāo)軌跡特征或運(yùn)動(dòng)模式.Liu等[4]結(jié)合國(guó)際海事組織IMO相關(guān)規(guī)定對(duì)船舶AIS航跡點(diǎn)進(jìn)行聚類(lèi)，提取船舶的主航跡.Yan等[5]對(duì)航跡點(diǎn)分類(lèi)，劃分為在航和拋錨兩種行為狀態(tài)，并對(duì)主航路路徑選取和錨地選址等問(wèn)題進(jìn)行了討論.基于軌跡點(diǎn)的聚類(lèi)忽略了同一船舶軌跡上相鄰點(diǎn)間的時(shí)空關(guān)聯(lián)特性，對(duì)船舶整體運(yùn)動(dòng)特征的刻畫(huà)能力有限.基于軌跡段的聚類(lèi)將連續(xù)位置點(diǎn)形成的軌跡整體或軌跡片段作為聚類(lèi)對(duì)象，建立軌跡整體或片段之間的相似性度量，進(jìn)而采用各種聚類(lèi)方法實(shí)現(xiàn)簇群劃分，聚類(lèi)結(jié)果能較好地描述不同形式和類(lèi)別的軌跡運(yùn)動(dòng)模式.相比于軌跡點(diǎn)聚類(lèi)，軌跡段聚類(lèi)更適合研究船舶行為模式.Lee[6]等最先提出基于軌跡片段的聚類(lèi)方法，通過(guò)對(duì)軌跡片段外形、夾角等進(jìn)行線性化處理來(lái)定義相似度，設(shè)計(jì)了一種層次化軌跡聚類(lèi)算法.魏照坤等[7-8]采用類(lèi)似手段實(shí)現(xiàn)了對(duì)船舶AIS軌跡線性化分片和聚類(lèi).基于分片的軌跡聚類(lèi)存在分片標(biāo)準(zhǔn)難以確定、分片不當(dāng)影響聚類(lèi)效果，以及計(jì)算過(guò)程復(fù)雜等問(wèn)題[9].特別是針對(duì)船舶運(yùn)動(dòng)具有慣性大、航向，以及航速變化慢等特點(diǎn)，將一定區(qū)域內(nèi)的船舶軌跡看成整體進(jìn)行聚類(lèi)可以更有效的區(qū)分船舶軌跡模式.Li等[10]以船舶AIS軌跡整體為聚類(lèi)對(duì)象，建立軌跡之間的空間位置距離矩陣進(jìn)而實(shí)現(xiàn)不同空間分布和方向上的軌跡簇劃分.然而，其相似度計(jì)算僅考慮了軌跡的經(jīng)緯度位置采樣值，沒(méi)有考慮各位置點(diǎn)上的航向、航速等船舶運(yùn)動(dòng)狀態(tài)信息.船舶位置、航向及航速是體現(xiàn)船舶行為規(guī)律的重要指標(biāo)，共同構(gòu)成了船舶行為特征量.如何利用這些行為特征量，建立船舶軌跡相似度并進(jìn)行聚類(lèi)分析是本文的重點(diǎn).

1 船舶行為特征相似度建模

2004年IMO規(guī)定：國(guó)際航線總噸位超過(guò)300 t，非國(guó)際航線中超過(guò)500 t的貨船及所有客船都需要安裝AIS發(fā)送設(shè)備.AIS信息記錄了船舶唯一標(biāo)識(shí)(MMSI)、船長(zhǎng)和船寬等的靜態(tài)信息,以及船舶瞬時(shí)位置、航速、航向等動(dòng)態(tài)信息[11].本文以AIS數(shù)據(jù)作為研究對(duì)象，首先對(duì)選定研究區(qū)域的AIS數(shù)據(jù)進(jìn)行預(yù)處理，依照MMSI號(hào)提取各個(gè)船舶對(duì)應(yīng)的軌跡點(diǎn)數(shù)據(jù)并按時(shí)間排序，對(duì)殘缺嚴(yán)重和噪聲點(diǎn)過(guò)多的軌跡進(jìn)行濾除.

為了比較兩艘船舶連續(xù)行為的相似度，從船舶AIS軌跡數(shù)據(jù)中提取經(jīng)度Lat、緯度Lng、航向Cog及航速Sog等采樣值，構(gòu)成船舶行為特征向量，則一條船舶軌跡可以用點(diǎn)序列表示為traj{x1,x2,...,xN}，其中N為該軌跡的長(zhǎng)度，即該軌跡由N個(gè)采樣點(diǎn)組成，每一個(gè)采樣點(diǎn)由4維度的行為特征向量表示，xi=Lati,Lngi,Cogi,Sogi,i=1,2,…,N.通常情況下，不同船舶即使在同一航路上行駛，其經(jīng)過(guò)的軌跡點(diǎn)也不可能完全一致，并且各個(gè)船舶的AIS數(shù)據(jù)采樣時(shí)間也不同步.因此，船舶的軌跡序列長(zhǎng)度一般是不等長(zhǎng)的，這給軌跡之間的相似度計(jì)算帶來(lái)困難，傳統(tǒng)針對(duì)等長(zhǎng)序列采用歐式距離計(jì)算相似度的方式就無(wú)法適用.針對(duì)這一問(wèn)題，擬采用動(dòng)態(tài)時(shí)間規(guī)整算法(dynamic time warping，DTW)[12]來(lái)計(jì)算船舶軌跡序列之間的相似度.該方法通過(guò)對(duì)序列進(jìn)行壓縮、拉伸變換和配對(duì)，有效解決了非等長(zhǎng)序列之間相似度計(jì)算的問(wèn)題.基于DTW的船舶軌跡序列相似度具體計(jì)算過(guò)程如下.

設(shè)長(zhǎng)度分別為P和Q的兩條軌跡序列：traja={a1,a2,…,aP}和trajb={b1,b2,…,bQ}，P≠Q(mào).對(duì)軌跡序列a和b進(jìn)行配對(duì)，構(gòu)建P×Q維的路徑矩陣，矩陣元素d(ai,bj)通過(guò)計(jì)算軌跡點(diǎn)上行為特征向量ai(i=1,2,…,P)和bj(j=1,2,…,Q)之間的相似度距離得到.假設(shè)路徑矩陣中存在一條路徑，同時(shí)滿(mǎn)足：①該路徑能遍歷軌跡a、b上的所有點(diǎn)；②路徑按一定方向連續(xù)移動(dòng)生成；③該路徑上經(jīng)過(guò)的元素累計(jì)相似度最小，則該路徑稱(chēng)作最相似規(guī)整路徑(Warping Path)，記作W：

W={w1,w2,…,wK}max(P,Q)≤K≤P+Q-1

(1)

式中：路徑元素wk(ai,bj)為軌跡序列a和b的配對(duì)關(guān)系；規(guī)整路徑W必須從軌跡點(diǎn)a1和b1開(kāi)始，終止于aP和bQ；對(duì)于路徑上前后兩點(diǎn)wk-1(ai′,bj′)和wk(ai,bj)需滿(mǎn)足0≤i-i′≤1，0≤j-j′≤1；計(jì)算路徑W上累計(jì)相似度D(ai,bj)，從路徑矩陣的初始點(diǎn)(a1,b1)開(kāi)始匹配序列a和b，每到一個(gè)點(diǎn)，之前所有點(diǎn)計(jì)算的相似度距離值都會(huì)累加，到達(dá)終點(diǎn)(aP,bQ)后，這個(gè)累積距離就是序列a和b的相似度.采用動(dòng)態(tài)規(guī)劃的思想，該累積計(jì)算過(guò)程為

D(ai,bj)=d(ai,bj)+ min{D(ai-1,bj),D(ai,bj-1),D(ai-1,bj-1)}

(2)

即累積距離D(ai,bj)為路徑矩陣中當(dāng)前元素格點(diǎn)距離d(ai,bj)與可以到達(dá)該點(diǎn)的最小的鄰近元素的累積距離之和.

如前所述，式(2)中的距離d(ai,bj)即路徑矩陣元素，代表不同軌跡點(diǎn)所對(duì)應(yīng)行為特征向量之間的相似度.考慮船舶行為在空間上具有關(guān)聯(lián)特性，如船舶在某些特定的位置點(diǎn)上可能具有相似的速度和轉(zhuǎn)向，因此，綜合考慮船舶位置、速度及航向等行為要素的相互關(guān)系，通過(guò)歸一化加權(quán)求和的方式度量軌跡之間的行為相似性.

以南北和東西方向?yàn)檩S建立船舶運(yùn)動(dòng)參考坐標(biāo)系，見(jiàn)圖1.

考慮船舶軌跡a和b上的兩個(gè)采樣點(diǎn)ai和bj，各自對(duì)應(yīng)的行為特征向量分別表示為

d(ai,bj)=w1V⊥+w2V∥+w3d⊥+w4d∥

(3)

式中：歸一化權(quán)重需滿(mǎn)足條件：wi≥0,i=1,2,3,4 且 ∑wi=1.權(quán)重的分配可以根據(jù)不同水域船舶航線分布特點(diǎn)進(jìn)行確定.

2 基于行為相似度的軌跡聚類(lèi)

通過(guò)船舶行為特征相似度建模，船舶軌跡兩兩之間的相似性計(jì)算不僅考慮了軌跡空間分布與形態(tài)上的差異，同時(shí)也考慮了不同軌跡所蘊(yùn)含的船舶運(yùn)動(dòng)特征，為船舶軌跡聚類(lèi)提供了更為全面的信息.擬采用DBSCAN(density-based spatial clustering of applications with noise)算法對(duì)船舶軌跡實(shí)現(xiàn)聚類(lèi).該算法是一種基于密度的無(wú)監(jiān)督聚類(lèi)算法，其優(yōu)勢(shì)是對(duì)噪聲數(shù)據(jù)不敏感，能夠發(fā)現(xiàn)任意形狀和大小的簇，并且無(wú)須事先設(shè)定簇個(gè)數(shù)，非常適合船舶AIS軌跡數(shù)據(jù)噪聲點(diǎn)多，軌跡模式不確定性高等情況下的聚類(lèi).

DBSCAN算法主要涉及兩個(gè)參數(shù)：鄰域ε(eps)和高密度區(qū)域形成所需要的最少點(diǎn)數(shù)minPts.軌跡聚類(lèi)算法由軌跡集T中任意一個(gè)未被訪問(wèn)的樣本點(diǎn)開(kāi)始，在T中探索這個(gè)點(diǎn)的ε-鄰域，即Neps(p)={q∈T|D(p,q)≤eps}，如果ε-鄰域里有足夠的點(diǎn)，即|Neps(p)|≥minPts，則建立一個(gè)新的聚類(lèi)，否則這個(gè)點(diǎn)被標(biāo)簽為異常點(diǎn)(該點(diǎn)之后可能被發(fā)現(xiàn)在其它點(diǎn)的ε-鄰域里而加入其聚類(lèi)中).如果一個(gè)點(diǎn)位于一個(gè)聚類(lèi)的密集區(qū)域里，它的ε-鄰域里的點(diǎn)也加入該聚類(lèi)，如果這些新加入聚類(lèi)的點(diǎn)也在密集區(qū)域里，則它們的ε-鄰域里的點(diǎn)也會(huì)被加進(jìn)聚類(lèi)里.此過(guò)程將一直重復(fù)，直至不能再加進(jìn)更多的點(diǎn)為止，這樣，一個(gè)密度連結(jié)的聚類(lèi)被完整地找出來(lái).然后，軌跡集T中一個(gè)未曾被訪問(wèn)的點(diǎn)將繼續(xù)被探索，從而發(fā)現(xiàn)一個(gè)新的聚類(lèi)或異常(無(wú)法被聚類(lèi)的樣本點(diǎn)).將DBSCAN應(yīng)用于船舶軌跡聚類(lèi)，參數(shù)eps反映了不同軌跡聚成一類(lèi)需滿(mǎn)足的最低相似程度，而minPts刻畫(huà)了不同軌跡聚成一類(lèi)需滿(mǎn)足的最少數(shù)量，軌跡之間相似度D(p,q)可由式(2)計(jì)算得到，聚類(lèi)結(jié)果不但可以區(qū)分不同的軌跡模式，聚類(lèi)完成所產(chǎn)生異常點(diǎn)還可用來(lái)篩選異常軌跡.

3 實(shí)驗(yàn)與分析

長(zhǎng)江南北槽水道位于銅沙淺灘與九段沙之間，是進(jìn)出長(zhǎng)江口的關(guān)鍵樞紐，對(duì)該區(qū)域船舶軌跡進(jìn)行研究具有重要意義.以南槽段2017年2月的AIS數(shù)據(jù)作為數(shù)據(jù)集(見(jiàn)圖2)，從南槽西至東方向的直行軌跡和西至北方向的上行軌跡中各選取50條，共10 148條AIS信息進(jìn)行算法驗(yàn)證.

圖2 長(zhǎng)江口南槽段電子海圖

聚類(lèi)實(shí)驗(yàn)分兩組進(jìn)行以對(duì)比算法效果.一組只考慮軌跡之間的空間位置相似度，即在相似度計(jì)算式(2)中的權(quán)重設(shè)置為：w1=w2=0，w3=w4=0.5；另一組相似度計(jì)算不僅考慮軌跡空間距離，同時(shí)還引入速度及航向等行為特征量，即權(quán)重設(shè)置為：wi=0.5(i=1,2,3,4).兩組實(shí)驗(yàn)的鄰域都設(shè)置為0.5，密度閾值minPts設(shè)為5.兩組實(shí)驗(yàn)的軌跡聚類(lèi)結(jié)果見(jiàn)圖3～4.

圖3 基于空間位置相似度軌跡聚類(lèi)

圖4 基于行為特征相似度軌跡聚類(lèi)

由圖3可知，在只考慮空間位置相似度進(jìn)行軌跡聚類(lèi)時(shí)，聚類(lèi)算法可以有效的將兩個(gè)不同方向上的軌跡劃分成不同的簇，即圖中上行軌跡的實(shí)線條和代表直行軌跡的淺色虛線條.同時(shí)，算法還輸出了一條異常軌跡，由圖中深色虛線表示，可以看到該異常軌跡在空間上明顯偏離兩個(gè)方向的軌跡簇，代表一種航線偏離異常.

圖4為引入行為特征相似度的軌跡聚類(lèi)效果，與圖3的結(jié)果對(duì)比可知，聚類(lèi)后軌跡簇由兩類(lèi)變成三類(lèi)，圖中淺色虛線條所代表直行軌跡簇沒(méi)有明顯變化，而上行軌跡簇被劃分為兩類(lèi)，即圖中箭頭“類(lèi)別二”和“類(lèi)別三”所指向的部分，新產(chǎn)生的軌跡簇“類(lèi)別三”由點(diǎn)線條標(biāo)識(shí).同時(shí)，算法輸出的異常軌跡由原來(lái)的一條變成三條，除了之前西東方向的一條航線偏離異常軌跡，在西北上行方向上多出兩條異常軌跡，圖中仍由深色虛線表示.兩條新增的異常軌跡在空間位置分布上與其他各軌跡簇并無(wú)明顯的偏離或差異，因此在只考慮空間位置相似度進(jìn)行軌跡聚類(lèi)時(shí)，這兩條軌跡未能判別為異常.實(shí)際上，兩條異常軌跡雖然與其他軌跡簇在空間軌跡點(diǎn)分布上存在重疊的情況，但它們都出現(xiàn)大角度橫跨航路的情況.這種情況通常也是海上交通中的一種異常，引入行為相似度的軌跡聚類(lèi)能有效識(shí)別這種異常情況.

進(jìn)一步對(duì)聚類(lèi)結(jié)果“類(lèi)別二”和“類(lèi)別三”進(jìn)行分析.從空間軌跡點(diǎn)分布上看，兩類(lèi)軌跡有較高的相似性很難區(qū)分，因此僅考慮空間位置相似度的聚類(lèi)將兩類(lèi)軌跡判別為同一簇.但仔細(xì)觀察兩類(lèi)軌跡走勢(shì)，可以發(fā)現(xiàn)“類(lèi)別三”主要分布在航線的東側(cè)，且由西東向變?yōu)槲鞅毕驎r(shí)，其轉(zhuǎn)向角度普遍大于“類(lèi)別二”.采用柱狀頻率統(tǒng)計(jì)與高斯擬合方法對(duì)兩類(lèi)軌跡的速度分布作進(jìn)一步統(tǒng)計(jì)分析，圖5給出了統(tǒng)計(jì)結(jié)果.其中，“類(lèi)別二”軌跡簇的航速近似于高斯分布，其速度均值約為9 kn；而“類(lèi)別三”軌跡簇在速度分布上出現(xiàn)雙峰的情況，與“類(lèi)別二”相比在分布形態(tài)上出現(xiàn)了明顯差異.這實(shí)際反映了西北向行駛過(guò)程中“類(lèi)別三”軌跡相比“類(lèi)別二”軌跡轉(zhuǎn)向較大，因轉(zhuǎn)向較大、過(guò)晚導(dǎo)致有偏離航線偏離的趨勢(shì)，“類(lèi)別三”船舶為及時(shí)修正航向在后半段速度由10 kn加速至13 kn，故產(chǎn)生雙峰的特征.因此，在引入航速、航向等行為特征后，聚類(lèi)算法能更為細(xì)致的對(duì)軌跡進(jìn)行分類(lèi)，發(fā)現(xiàn)新的船舶運(yùn)動(dòng)模式.

圖5 船舶速度分布對(duì)比

4 結(jié) 束 語(yǔ)

利用AIS數(shù)據(jù)提取船舶位置、航速及航向等行為特征量，并建立了行為特征相似度計(jì)算模型，基于DBSCAN算法實(shí)現(xiàn)了船舶軌跡聚類(lèi)方法流程，利用長(zhǎng)江口南槽段船舶實(shí)際軌跡數(shù)據(jù)對(duì)算法進(jìn)行了驗(yàn)證和分析.結(jié)果表明，基于行為特征相似度的軌跡聚類(lèi)比僅考慮空間位置相似度的軌跡聚類(lèi)能發(fā)現(xiàn)更多的軌跡模式或軌跡異常，為開(kāi)展船舶交通行為分析和行為監(jiān)管提供了新方法.