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

江玉玲, 熊振南, 唐基宏

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

隨著海上經濟的發展，海洋運輸已成為國內外貨物運輸的最重要方式之一，越來越多的船舶投入到海洋運輸當中，沿海以及港口附近的船舶密度越來越大，船舶交通狀況越來越復雜，這給船舶交管部門的管理帶來很大的麻煩。船舶自動識別系統(Automatic Identification System， AIS)是獲取船舶運動信息數據的重要手段。特別是國際海事組織(International Maritime Organization， IMO)通過的國際海上人命安全公約(International Convention for Safety of Life at Sea,SOLAS)修正案要求：所有300 t以上的國際航行船舶、500 t以內的非國際航行船舶以及所有客船，都必須強制安裝AIS設備[1]，這使船舶監管部門可獲取船舶數據。從AIS提取的船舶大數據中分析船舶的運動軌跡，對其進行聚類研究，從而得出船舶運動的規律以及進一步發現、分析船舶的異常行為，為海事安全監管和決策提供支持服務。

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

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

基于船舶AIS數據實現軌跡聚類的總體流程見圖1。

圖1 基于AIS數據的軌跡聚類流程

2 AIS數據預處理

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

3 軌跡聚類的實現分段

3.1 軌跡聚類方法研究

目前，國內外對船舶軌跡的聚類研究主要有兩種方法。[6]

1) 把船舶的軌跡當作整體進行研究，這種方法可發現軌跡中的關鍵點，缺點是研究軌跡的開銷大，而且會因為丟掉一些具有相似運動特征的軌跡子段[7-8]而失去一些重要信息，而這些重要信息對研究船舶軌跡至關重要。

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

本文采用軌跡分段法進行軌跡聚類研究。

3.2 軌跡分段

對船舶軌跡進行分段處理，有保證原始軌跡信息的完整性和盡量保證數據的簡潔性兩個要求，即要求得到的子軌跡數量盡可能少，從而減少開銷。

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

本文主要采用采集分段軌跡的特征點，船位轉向角信息度量和船位航速信息度量兩種方法。

3.2.1 船位轉向角信息度量

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

圖2 船舶運動軌跡示例

圖3 船舶軌跡轉向角

3.2.2 船位航速信息度量

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

通過轉向角與航速變化率來確定船舶軌跡的關鍵點，連接兩個相鄰的關鍵點，他們之間的連線就構成了船舶的軌跡子段。

3.3 軌跡相似度度量

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

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

(1)

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

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

根據參考文獻[12]，兩者之間的離散Frechet距離表示為

(2)

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

3.4 軌跡段聚類

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

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

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

(3)

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

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

|Nε(Li)|≤minLns

(4)

則Li為核心軌跡段。

定義3 在數據空間D內，如果滿足

Li∈Nε(Lj)

(5)

|Nε(Lj)|≤minLns

(6)

則Li到Lj是直接密度可達。

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

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

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

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

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

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

圖5 DBSCAN算法示意

4 試驗結果

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

圖6 3 d AIS船舶軌跡

為比較算法的優劣，對Hausdorff距離結合離散Frechet距離作為軌跡相似度度量的改進的DBSCAN算法與傳統的Hausdorff距離作為相似度度量的DBSCAN算法進行比較，結果見表1。

表1 兩種算法對比結果

由表1可知：基于離散Frechet距離作為軌跡相似度度量的改進的DBSCAN算法在運行時間上多于傳統的DBSCAN算法，這是因為改進的DBSCAN算法需要利用船位轉向角和航速變化量作為信息度量對船舶軌跡進行分段，相似性度量也較復雜，增加了計算的復雜度，但是該算法考慮船位轉向角和航速變化量，并且能從多方面計算軌跡相似度，容易發現隱蔽的軌跡群，在分類結果和準確度方面優于傳統的DBSCAN 算法。

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

表2 3組AIS數據比較結果

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

圖7 船舶運動典型軌跡

5 結束語

本文基于船舶AIS數據，先對船舶軌跡進行分段，利用改進的軌跡段DBSCAN算法對軌跡子段進行聚類，對比改進的DBSCAN算法與傳統算法的聚類結果，并得出船舶運動的典型軌跡。從對比試驗結果看，改進的DBSCAN算法在聚類結果和聚類準確率上有所提高，并且船舶的典型軌跡能夠按照天津港的航道設置。可將此試驗數據作為參考，為進一步研究挖掘船舶異常軌跡打下基礎。但從4 d、5 d聚類所需的時間看，隨著分段軌跡數的增多，聚類所需時間成倍增加，怎樣提高聚類效率也是后期研究的方向。