基于軌跡段DBSCAN的船舶軌跡聚類算法

江玉玲, 熊振南, 唐基宏

(集美大學(xué) a. 誠(chéng)毅學(xué)院； b. 航海學(xué)院, 廈門 361021)

隨著海上經(jīng)濟(jì)的發(fā)展，海洋運(yùn)輸已成為國(guó)內(nèi)外貨物運(yùn)輸?shù)淖钪匾绞街唬絹碓蕉嗟拇巴度氲胶Ｑ筮\(yùn)輸當(dāng)中，沿海以及港口附近的船舶密度越來越大，船舶交通狀況越來越復(fù)雜，這給船舶交管部門的管理帶來很大的麻煩。船舶自動(dòng)識(shí)別系統(tǒng)(Automatic Identification System， AIS)是獲取船舶運(yùn)動(dòng)信息數(shù)據(jù)的重要手段。特別是國(guó)際海事組織(International Maritime Organization， IMO)通過的國(guó)際海上人命安全公約(International Convention for Safety of Life at Sea,SOLAS)修正案要求：所有300 t以上的國(guó)際航行船舶、500 t以內(nèi)的非國(guó)際航行船舶以及所有客船，都必須強(qiáng)制安裝AIS設(shè)備[1]，這使船舶監(jiān)管部門可獲取船舶數(shù)據(jù)。從AIS提取的船舶大數(shù)據(jù)中分析船舶的運(yùn)動(dòng)軌跡，對(duì)其進(jìn)行聚類研究，從而得出船舶運(yùn)動(dòng)的規(guī)律以及進(jìn)一步發(fā)現(xiàn)、分析船舶的異常行為，為海事安全監(jiān)管和決策提供支持服務(wù)。

對(duì)運(yùn)動(dòng)物標(biāo)的軌跡聚類，即將軌跡劃分成不同的、具有相似運(yùn)動(dòng)規(guī)律的對(duì)象組成的子集。目前，國(guó)內(nèi)外學(xué)者對(duì)軌跡聚類進(jìn)行一系列的研究。吐爾遜等[2]采用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法對(duì)模擬農(nóng)業(yè)機(jī)械作業(yè)軌跡進(jìn)行分析，對(duì)農(nóng)機(jī)作業(yè)狀態(tài)進(jìn)行聚類分類研究，分析農(nóng)機(jī)作業(yè)班次的有效作業(yè)軌跡、空行轉(zhuǎn)移軌跡和停歇軌跡，得出農(nóng)機(jī)利用率。周培培等[3]先基于速度的最小描述長(zhǎng)度準(zhǔn)則把軌跡簡(jiǎn)化成有序線段，再利用DBSCAN算法把線段分成不同的類，從而檢測(cè)時(shí)空異常軌跡。陳錦陽等[4]利用特征點(diǎn)概念將軌跡分成軌跡子段，提出一種改進(jìn)的軌跡子段距離度量方法，計(jì)算軌跡子段之間的相似度，用CTIHD聚類算法進(jìn)行軌跡聚類。曹妍妍等[5]提出利用改進(jìn)的Hausdorff距離進(jìn)行軌跡相似度度量，然后采用譜聚類方法對(duì)距離矩陣進(jìn)行聚類，從而得出符合實(shí)際的聚類結(jié)果。綜上，這些專家學(xué)者在對(duì)軌跡聚類上都取得一定的成效，但是軌跡聚類應(yīng)用于船舶AIS數(shù)據(jù)上的研究較少。本文針對(duì)Hausdorff距離可能存在的不足進(jìn)行分析，結(jié)合船舶AIS數(shù)據(jù)的特點(diǎn)，提出一種利用船位轉(zhuǎn)向角和航速變化量作為信息度量對(duì)船舶軌跡進(jìn)行分段，把Hausdorff距離與離散Frechet距離結(jié)合作為軌跡相似度度量，基于軌跡段DBSCAN算法對(duì)運(yùn)動(dòng)軌跡進(jìn)行分類，進(jìn)一步獲取船舶運(yùn)動(dòng)的典型軌跡，從而為研究船舶的異常行為打下基礎(chǔ)。

1 船舶軌跡聚類的總體流程

基于船舶AIS數(shù)據(jù)實(shí)現(xiàn)軌跡聚類的總體流程見圖1。

圖1 基于AIS數(shù)據(jù)的軌跡聚類流程

2 AIS數(shù)據(jù)預(yù)處理

獲取的AIS數(shù)據(jù)解碼后存入數(shù)據(jù)庫，首先要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理和清洗，這樣才能得到有效的AIS數(shù)據(jù)。預(yù)處理的主要工作是清除信息表中呼號(hào)為0的數(shù)據(jù)；清除不同船舶但水上移動(dòng)通信業(yè)務(wù)標(biāo)識(shí)(Maritime Mobile Service Identification, MMSI)相同的數(shù)據(jù)；清除明顯錯(cuò)誤的數(shù)據(jù)，比如船位、速度或航向超過合理值的AIS數(shù)據(jù)。

3 軌跡聚類的實(shí)現(xiàn)分段

3.1 軌跡聚類方法研究

目前，國(guó)內(nèi)外對(duì)船舶軌跡的聚類研究主要有兩種方法。[6]

1) 把船舶的軌跡當(dāng)作整體進(jìn)行研究，這種方法可發(fā)現(xiàn)軌跡中的關(guān)鍵點(diǎn)，缺點(diǎn)是研究軌跡的開銷大，而且會(huì)因?yàn)閬G掉一些具有相似運(yùn)動(dòng)特征的軌跡子段[7-8]而失去一些重要信息，而這些重要信息對(duì)研究船舶軌跡至關(guān)重要。

2) 將船舶軌跡進(jìn)行分段，分別對(duì)分段后的軌跡子段進(jìn)行聚類研究，將相似的軌跡子段歸類為簇,在此基礎(chǔ)上再甄別異常的軌跡子段,從而有效地發(fā)現(xiàn)船舶的異常行為,為后期研究異常船舶軌跡打下基礎(chǔ)。這種方法的缺點(diǎn)是無法保證船舶軌跡的完整性，但能具體研究軌跡子段的特征，以保證軌跡運(yùn)動(dòng)的重要信息不丟失，而且綜合各軌跡子段后也能得到相對(duì)完整的整條軌跡[9-10]。

本文采用軌跡分段法進(jìn)行軌跡聚類研究。

3.2 軌跡分段

對(duì)船舶軌跡進(jìn)行分段處理，有保證原始軌跡信息的完整性和盡量保證數(shù)據(jù)的簡(jiǎn)潔性兩個(gè)要求，即要求得到的子軌跡數(shù)量盡可能少，從而減少開銷。

船舶運(yùn)動(dòng)軌跡示例見圖2。船舶沿著P1—P8的實(shí)線運(yùn)動(dòng)。如果把P1點(diǎn)到P8點(diǎn)的所有點(diǎn)都采集下來當(dāng)作船舶軌跡的關(guān)鍵點(diǎn)，保證了船舶原始軌跡的完整性，但是采樣點(diǎn)多，計(jì)算復(fù)雜；如果只采集P1點(diǎn)、P5點(diǎn)、P8點(diǎn)3個(gè)點(diǎn)作為關(guān)鍵點(diǎn)，確實(shí)保證了采集點(diǎn)數(shù)量的簡(jiǎn)潔，但沿著P1—P5—P8的細(xì)虛線的船舶軌跡與原始軌跡對(duì)比，卻丟失了原始軌跡的特征，不能保證運(yùn)動(dòng)軌跡的完整性：因而我們選擇P1點(diǎn)、P3點(diǎn)、P5點(diǎn)、P7點(diǎn)作為采集的關(guān)鍵點(diǎn)，這樣它們形成的軌跡P1—P3—P5—P7既能還原原始軌跡的特征，又具有一定的簡(jiǎn)潔性。

本文主要采用采集分段軌跡的特征點(diǎn)，船位轉(zhuǎn)向角信息度量和船位航速信息度量?jī)煞N方法。

3.2.1 船位轉(zhuǎn)向角信息度量

船位轉(zhuǎn)向角信息度量是通過設(shè)置特定船位的船舶轉(zhuǎn)向角的閾值來實(shí)現(xiàn)的。船舶軌跡轉(zhuǎn)向角指相鄰幾個(gè)船位所連接的兩個(gè)船舶子軌跡段的航跡向之差。在給定距離D0范圍內(nèi)，P3—P4軌跡段和P4—P5軌跡段是船舶軌跡的兩個(gè)子軌跡段見圖3。這兩個(gè)軌跡段之間的航跡向之差，也就是轉(zhuǎn)向角為θ，將θ與設(shè)定的轉(zhuǎn)向角閾值θmax進(jìn)行對(duì)比，如果θ≥θmax則將P4點(diǎn)選為關(guān)鍵點(diǎn)，如果θ<θmax則繼續(xù)采樣，如此循環(huán)，直到遍歷所有的點(diǎn)。

圖2 船舶運(yùn)動(dòng)軌跡示例

圖3 船舶軌跡轉(zhuǎn)向角

3.2.2 船位航速信息度量

軌跡設(shè)定一個(gè)給定的距離(dmin,dmax)，若在P3點(diǎn)的鄰域距離(dmin,dmax)內(nèi)，任意點(diǎn)與P3點(diǎn)的速度差的絕對(duì)值≥設(shè)定的速度閾值vmax，則不管P3點(diǎn)的轉(zhuǎn)向角多大，都選定P3點(diǎn)為關(guān)鍵點(diǎn)，該點(diǎn)被稱為變速點(diǎn)。

通過轉(zhuǎn)向角與航速變化率來確定船舶軌跡的關(guān)鍵點(diǎn)，連接兩個(gè)相鄰的關(guān)鍵點(diǎn)，他們之間的連線就構(gòu)成了船舶的軌跡子段。

3.3 軌跡相似度度量

度量軌跡間的相似性是實(shí)現(xiàn)軌跡聚類的基礎(chǔ)，AIS數(shù)據(jù)中包含著豐富的船舶運(yùn)動(dòng)信息，如船位、航向、航速等，在軌跡相似性度量中要充分考慮這些信息。本文的軌跡子段包含船位轉(zhuǎn)向角信息和船位航速信息，這能夠提高聚類的準(zhǔn)確度和分析效果。由船位轉(zhuǎn)向角信息和船位航速信息確定的特征點(diǎn)組成船舶的分段軌跡。船舶的分段軌跡由一系列的特征點(diǎn)根據(jù)時(shí)間的先后順序組成，其表達(dá)式為

TRi={Pi1,Pi2,…,Pij, …,Pin}

(1)

基于距離的相似度度量法有很多[7]，包括歐氏距離、Minkowski距離、余弦距離和Hausdorff距離等。最常用到的序列相似性度量的方法是Hausdorff距離：兩條軌跡的距離越大，則軌跡間的相似度越低；反之，相似度就高。Hausdorff距離通常用來度量離散點(diǎn)集間的毗鄰度，而船舶的運(yùn)動(dòng)軌跡被認(rèn)為是矢量空間中有序的序列點(diǎn)集，考慮到兩個(gè)序列即使有很小的Hausdorff距離，也并不能表示他們的相似度高，而且如果船舶運(yùn)動(dòng)軌跡點(diǎn)丟失，或者存在一個(gè)小的異常軌跡點(diǎn)，就會(huì)引起非常大的距離變化。針對(duì)這些問題，本文采用離散Frechet距離作為判別曲線間相似性的度量。

離散Frechet距離起源于人-狗距離模型，以函數(shù)的形式定義人-狗行進(jìn)的兩條曲線間的最小距離，將人與狗所行走的曲線抽象分別抽象為兩個(gè)有序點(diǎn)串，從序列整體全局到局部細(xì)節(jié)逐級(jí)進(jìn)行度量分析，避免Hausdorff距離分析只從點(diǎn)數(shù)據(jù)集合距離上判斷各子目標(biāo)相近程度的缺陷，整體態(tài)勢(shì)上越接近，相似性越高[11]。

根據(jù)參考文獻(xiàn)[12]，兩者之間的離散Frechet距離表示為

(2)

式(2)中：假定{p1,p2,…,pn}為曲線P上的采樣點(diǎn)，{q1,q2, …,qm}為曲線Q上的采樣點(diǎn)；C={C1,C2, …,CK}為兩曲線P、Q采樣點(diǎn)連接的耦合距離集合；CR=(pi,qj)為歐氏距離，r=1,2, …,k,i∈{1,2, …,n},j∈{1,2, …,m}。

3.4 軌跡段聚類

軌跡聚類的方法有很多，本文采用基于密度的聚類方法。[13-14]傳統(tǒng)的DBSCAN算法是最典型的密度聚類算法，他的對(duì)象主要是點(diǎn)，通過對(duì)比參考文獻(xiàn)[9]、文獻(xiàn)[10]、文獻(xiàn)[15]、文獻(xiàn)[16]發(fā)現(xiàn)，利用DBSCAN也可對(duì)軌跡段進(jìn)行聚類，其研究方法與基于點(diǎn)的DBSCAN的聚類方法類似。其算法的主要思想是：將所有的軌跡段標(biāo)記為未聚類的，讀取軌跡段，通過ε和minLns判斷該軌跡段是否是核心軌跡段。如果是，則該核心軌跡段的ε鄰域形成一個(gè)新簇C并用該核心軌跡段標(biāo)記。然后這個(gè)簇通過ε鄰域的核心軌跡段不斷向外擴(kuò)展，直到簇不再增長(zhǎng)為止?；贒BSCAN的軌跡段聚類法的相關(guān)定義如下：

定義1Li鄰域的公式化定義為

Nε(Li)={Lj∈D|Ddist(Li,Lj)≤ε}

(3)

式(3)中：ε為軌跡段的密度半徑；minLns為軌跡段的密度閾值；D為給定的軌跡子段數(shù)據(jù)空間；Li、Lj為軌跡子段。Li、Lj∈D,Li的鄰域由所有與其空間距離不超過ε的軌跡子段構(gòu)成。

定義2 對(duì)于Li∈D，如果Li的鄰域滿足

|Nε(Li)|≤minLns

(4)

則Li為核心軌跡段。

定義3 在數(shù)據(jù)空間D內(nèi)，如果滿足

Li∈Nε(Lj)

(5)

|Nε(Lj)|≤minLns

(6)

則Li到Lj是直接密度可達(dá)。

式(5)為軌跡子段Li在軌跡子段Lj的ε鄰域范圍，式(6)為L(zhǎng)j是核心軌跡段。

定義4 在數(shù)據(jù)空間D內(nèi)，如果存在L1,L2,L3, …,Li, …,Ln(Li∈D,1≤i≤n),使得所有的Li+1從Li出發(fā)都是關(guān)于ε和minLns是直接密度可達(dá)的，則稱Ln從L1出發(fā)是密度可達(dá)的。

定義5 存在一任意軌跡段Lk，Li、Lj、Lk∈D， 當(dāng)Li和Lj都滿足從Lk出發(fā)關(guān)于ε和minLns是密度可達(dá)，則稱Li到Lj是關(guān)于ε和minLns是密度相連的。[17]

基于DBSCAN的軌跡段聚類算法流程見圖4。

圖4 基于DBSCAN的軌跡段聚類算法流程圖

通過上述過程，直至遍歷完所有的軌跡段對(duì)象，最終類C確定下來，DBSCAN算法示意見圖5。在計(jì)算軌跡段核心對(duì)象時(shí)，將半徑設(shè)為ε，密度閾值為minLns的外包橢圓作為搜索區(qū)域來獲取，橢圓區(qū)域內(nèi)包含的點(diǎn)為最終的類。

圖5 DBSCAN算法示意

4 試驗(yàn)結(jié)果

本文以天津港獲取的船舶AIS信息為研究對(duì)象對(duì)船舶軌跡進(jìn)行聚類。選取天津港2016年8月1日—2016年8月3日的AIS數(shù)據(jù)，經(jīng)過篩選和數(shù)據(jù)處理，顯示出3 d船舶進(jìn)出天津港軌跡見圖6。3條航道從上到下分別是天津港主航道、大沽沙航道、大港航道，3 d的聚類軌跡分布在這3條航道上，總共198條船舶軌跡，軌跡某些段會(huì)重合，將3 d的船舶運(yùn)動(dòng)軌跡進(jìn)行軌跡分段，獲得951條軌跡子段。再利用軌跡段的DBSCAN算法對(duì)軌跡子段進(jìn)行聚類計(jì)算，基于密度的DBSCAN算法對(duì)ε和minLns參數(shù)值的選定非常敏感[18]，試驗(yàn)需要反復(fù)進(jìn)行。經(jīng)過多番篩選，當(dāng)ε=0.002 n mile，密度閾值minLns=3 時(shí)，聚類結(jié)果比較理想。

圖6 3 d AIS船舶軌跡

為比較算法的優(yōu)劣，對(duì)Hausdorff距離結(jié)合離散Frechet距離作為軌跡相似度度量的改進(jìn)的DBSCAN算法與傳統(tǒng)的Hausdorff距離作為相似度度量的DBSCAN算法進(jìn)行比較，結(jié)果見表1。

表1 兩種算法對(duì)比結(jié)果

由表1可知：基于離散Frechet距離作為軌跡相似度度量的改進(jìn)的DBSCAN算法在運(yùn)行時(shí)間上多于傳統(tǒng)的DBSCAN算法，這是因?yàn)楦倪M(jìn)的DBSCAN算法需要利用船位轉(zhuǎn)向角和航速變化量作為信息度量對(duì)船舶軌跡進(jìn)行分段，相似性度量也較復(fù)雜，增加了計(jì)算的復(fù)雜度，但是該算法考慮船位轉(zhuǎn)向角和航速變化量，并且能從多方面計(jì)算軌跡相似度，容易發(fā)現(xiàn)隱蔽的軌跡群，在分類結(jié)果和準(zhǔn)確度方面優(yōu)于傳統(tǒng)的DBSCAN 算法。

試驗(yàn)再獲取4 d、5 d的AIS船舶數(shù)據(jù)，利用改進(jìn)的軌跡分段和軌跡段聚類算法對(duì)數(shù)據(jù)進(jìn)行處理，得出軌跡分段后的軌跡子段數(shù)和聚類算法過程所用的時(shí)間。3 d、4 d、5 d的AIS船舶數(shù)據(jù)進(jìn)行聚類算法的數(shù)據(jù)比較見表2。數(shù)據(jù)比較主要測(cè)試在執(zhí)行聚類算法過程中，隨著數(shù)據(jù)量的增加，其算法的執(zhí)行效率。從試驗(yàn)結(jié)果來看，采用軌跡段DBSCAN算法，能較好地對(duì)船舶軌跡進(jìn)行聚類，但此算法對(duì)ε和minLns參數(shù)值的選定比較敏感。而且由表2可知：隨著數(shù)據(jù)量的增加，聚類過程所用時(shí)間基本成倍增加，所以在后期的研究中，需要關(guān)注在數(shù)據(jù)量增加的時(shí)候，如何改進(jìn)聚類過程，節(jié)約聚類開銷。

表2 3組AIS數(shù)據(jù)比較結(jié)果

為驗(yàn)證試驗(yàn)結(jié)果的可信度，從聚類后的船舶軌跡中求取船舶的典型軌跡。船舶的典型軌跡指的是將聚類后的各簇中的軌跡子段對(duì)應(yīng)的船位、船舶速度、航向求平均值，每簇得到一條典型的軌跡子段，并將各軌跡子段按時(shí)間先后順序相連得出的軌跡。取3 d的AIS船舶數(shù)據(jù)進(jìn)行聚類，然后求其典型軌跡見圖7，分別得出天津港主航道、大沽沙航道、大港航道的3條典型軌跡。圖7中用3條點(diǎn)線表示提取出的典型軌跡，將船舶的典型軌跡與天津港3條航道設(shè)置相對(duì)比可知：船舶典型軌跡基本沿著航道的設(shè)置，由此可推斷，試驗(yàn)結(jié)果可信，有一定的參考價(jià)值。

圖7 船舶運(yùn)動(dòng)典型軌跡

5 結(jié)束語

本文基于船舶AIS數(shù)據(jù)，先對(duì)船舶軌跡進(jìn)行分段，利用改進(jìn)的軌跡段DBSCAN算法對(duì)軌跡子段進(jìn)行聚類，對(duì)比改進(jìn)的DBSCAN算法與傳統(tǒng)算法的聚類結(jié)果，并得出船舶運(yùn)動(dòng)的典型軌跡。從對(duì)比試驗(yàn)結(jié)果看，改進(jìn)的DBSCAN算法在聚類結(jié)果和聚類準(zhǔn)確率上有所提高，并且船舶的典型軌跡能夠按照天津港的航道設(shè)置?？蓪⒋嗽囼?yàn)數(shù)據(jù)作為參考，為進(jìn)一步研究挖掘船舶異常軌跡打下基礎(chǔ)。但從4 d、5 d聚類所需的時(shí)間看，隨著分段軌跡數(shù)的增多，聚類所需時(shí)間成倍增加，怎樣提高聚類效率也是后期研究的方向。