多步驟船舶軌跡聚類方法研究與實現?

蔣 通 崔良中 周 鋼 張社國

（1.海軍工程大學電子工程學院 武漢 430033）（2.中國人民解放軍92682部隊 湛江 524000）

1 引言

船舶自動識別系統是船舶航行安全和海上監視的關鍵，在船舶行為模式分析［1］和海上交通規律挖掘［2］的研究與應用中受到了廣泛關注。對AIS船舶軌跡數據開展聚類分析研究，可以跟蹤與預測船舶航行軌跡，檢測與識別船舶異常行為［3］，從而為航運規劃和海事監管等工作開展提供決策支持和科學依據。目前，國內外學者對于船舶軌跡聚類的研究主要從以下三個方面展開。

在研究對象方面，21世紀初Knorr等人以整條航跡為聚類的對象，使用位置、方向和速度等三個維度組成的序列來表示每個位置點，運用傳統距離函數來計算軌跡之間距離并對航跡進行聚類。而Lee等［4］將整條航跡劃分成子航跡，考慮航跡的結構性特征，來計算子航跡段之間的相似性。此后肖瀟等［5］將航跡方向變化較大的點作為整條航跡的分割點，對分割后的子航跡進行聚類。

在相似性度量方面，大多數是基于距離進行計算，諸如歐幾里得距離、hausdorff距離和最長公共子序列距離等。然而，航跡的速度、方向等特征都應當被考慮在內。牟軍敏等［6］基于hausdorff距離，設計自動選取尺度參數的相似度度量函數，構造相似度矩陣；雷鵬［7］將包含多個特征的結構化距離進行歸一化，避免由于各項特征的取值范圍差別較大而造成的實驗誤差。

在算法選擇方面，目前常用的航跡聚類算法主要包括基于密度［8～9］（DBSCAN、OPTICS）、基于統計學（GMM、KDE）和基于網格（CLIQUE、STING）的軌跡聚類算法等。其中，DBSCAN算法因其能夠發現任意形狀的簇類而被廣泛改進和應用。江玉玲等［10］采用離散Frechet距離作為軌跡相似度度量，利用類似DBSCAN算法對軌跡段進行聚類，得出船舶運動典型軌跡；PALLOTTA等［11］采用增量DBSCAN算法對AIS船舶軌跡數據中的轉向點進行聚類，在此基礎上分析船舶的交通流模式。

然而，原始AIS數據是如何一步步變成可以為我們所用的有效信息，相關系統完整的研究較少。為解決這一問題，本文在對AIS數據進行預處理后，提出一種多步驟船舶軌跡聚類方法，主要包括軌跡壓縮、軌跡點匹配與距離相似性度量和軌跡聚類等三部分，并利用真實AIS數據進行實例驗證。

2 數據預處理

原始AIS數據預處理過程如圖1所示。

圖1 AIS數據預處理流程圖

AIS報告種類包括船位報告、基地臺報告和信道管理等13種，長度從168～1192比特數不等。對AIS數據進行預處理首先需要對其各個組成部分進行剖析，將信息進行解碼處理，才能轉化成我們需要的水上移動通信業務標識碼（MMSI）、IMO編號、船長和船寬和船舶類型等靜態信息，以及船舶位置、對地航速、對地航向和航行狀態等動態信息。

AIS數據經過解析后主要存在三個方面的數據質量問題：1）重復（連續兩行數據完全一致）；2）缺失（如某一行數據中某個屬性數據為空）；3）錯誤（某些數據明顯與客觀事實不符，如實際航向超出0～3599、實際航速超出0～1022等）。這些數據都應該去除，否則會對實驗結果產生不可忽視的影響。

每一條AIS數據中記錄著大量信息，在本文對船舶軌跡聚類的研究中，我們只需提取MMSI、時刻、實際航速、經度、緯度和實際航向等六種屬性信息，這樣可以有效提高后續計算效率。

為方便后續研究的開展，一般需要先對數據進行無量綱化處理，這樣表征不同屬性的各數據之間才有可比性。數據規范化的常用方法主要包括z分數規范化、正則化、小數定標規范化和最小-最大規范化。根據AIS航跡數據的特點，本文選用最小-最大規范化。

假設minA和maxA分別為屬性A的最小值和最大值。最小-最大規范化通過計算：

把A的值vi映射到區間［0，1］中的v'i。最小-最大規范化既可以放大某些標準差較小的特征之間的差異，又能夠保留原始數據中由標準差所反映的潛在權重關系，因此被廣泛應用。

對AIS數據進行預處理后的結果及對部分數據進行規范化的結果如圖2所示。

圖2 規范化前后的AIS數據對比

3 多步驟船舶軌跡聚類方法

完成對AIS數據的預處理后，本文提出多步驟船舶軌跡聚類方法［12］，主要由軌跡壓縮、軌跡點匹配與距離相似性度量和軌跡聚類等三部分組成。完整流程如圖3所示。

圖3 多步驟船舶軌跡聚類方法

3.1 軌跡壓縮

每一條軌跡都可以看做是一條不規則曲線，在對軌跡數字化時，要對曲線進行采樣，即在曲線上取有限個點，將其變為折線，并且能夠在一定程度上保持原有的形狀。經典算法步驟如下。

運用經典 Douglas-Peucker（DP）［13］算法壓縮軌跡時，只考慮了軌跡點的經度和緯度，而忽略了航向和航速對壓縮結果的影響，往往會導致不能將“轉折點”或“變速點”保留下來。因此，本文在經典DP算法的基礎上進行改進，通過查閱相關文獻資料以及咨詢航海領域專業人士，保留符合以下條件中至少一條的軌跡點：

也即保留航向或航速變化較大的點。

以經度為橫坐標、緯度為縱坐標，經改進的DP軌跡壓縮算法處理前后的軌跡對比如圖4所示。原始軌跡包括73個軌跡點，壓縮后軌跡包括58個軌跡點，軌跡點減少的同時能夠基本保持原有形狀。

圖4 軌跡壓縮前后對比

3.2 軌跡點匹配和距離相似性度量

在某一區域、某一時間段內的所有AIS航跡數據中，不同航跡包含的軌跡點數量往往不同，而且，僅依據經緯度作為衡量軌跡間距離的指標往往是片面的，因此如何更全面、更準確地對不同軌跡的軌跡點進行匹配以及軌跡間距離相似性如何度量成為目前研究的熱點問題。

每一條航跡都可以看作是由相鄰軌跡點連接而成的子航跡段組成，我們采用動態時間規整算法（DTW）［14］對不同航跡之間的軌跡點進行匹配，保證每條航跡的任一軌跡點在另一條航跡當中都能找到與之匹配的軌跡點，把它們之間的等效認為是以此軌跡點為起點的子航跡段之間的“距離”。算法的思想是使用迭代的方法求出任意兩條航跡的匹配路徑，使得“距離”最小。

假設有兩條軌跡為Traj1和Traj2，T1i表示第一條軌跡的第i個軌跡點，T2j表示第二條軌跡的第j個軌跡點，DTW(i,j)表示Traj1的前i個軌跡點組成的軌跡和Traj2的前j個軌跡點組成的軌跡之間的最小“距離”。那么：

不同軌跡之間的結構化距離中除了幾何距離外，還包括由于航向和航速的差異而導致的“距離”［15］，我們也需要對此進行度量。假設m和n是任意兩條不同軌跡上的點跡，可以用四維向量來描述其特征，以點m為例：

其中，lat表示緯度，lng表示經度，cog表示航向，sog表示航速。以點跡m為例，將sogm在兩個方向軸進行水平和垂直投影分解為Vm//和Vm⊥兩個分量：

對sogn進行同樣分解，則不同軌跡上的點跡之間的速度差異可以表示為

同理，將兩軌跡點之間的幾何距離d(m,n)分解為d//和d⊥兩個分量，由于地球為近似的橢球體，可以用如式（8）進行計算：

其中，C表示兩點與球心連線的夾角，Rc為地球的平均半徑。

那么m、n兩點之間地結構化距離為

上式中，μi表示各“距離”所占權重，需滿足條件：μi≥0,i=1,2,3,4且∑μi=1。

3.3 軌跡聚類

在應用比較廣泛的幾類軌跡聚類算法中，DBSCAN算法是一種有代表性的基于密度的無監督聚類算法。它將簇定義為密度相連的點的最大集合，在無須事先設定簇的個數前提下，能夠發現任意形狀和大小的簇，而AIS數據具有噪聲點多、軌跡不確定的特性，應用DBSCAN算法能夠獲得較好的聚類效果。

應用DBSCAN算法進行軌跡聚類的結果取決于鄰域半徑參數ε和鄰域密度閾值MinPts的確定。本文對DBSCAN算法的改進正是體現在這兩個參數的選取方法上。

聚類的目的是將樣本數據集盡可能地聚合成簇。鄰域密度MinPts一定的情況下，鄰域半徑ε過大會導致簇之間區分度很小，ε過小會導致得到的簇較少，而噪聲點較多；鄰域半徑ε一定的情況下，鄰域密度MinPts過大會導致噪聲點較多，MinPts過小會導致聚成的簇數較多，不能實現聚類的目的。本文采用基于核密度估計和噪聲數據量變化的方法來確定合適的鄰域半徑參數ε和鄰域密度閾值MinPts。

核密度估計（KDE）是一種用于估計概率密度函數的非參數方法，x1,x2,…,xn為獨立同分布F的n個樣本點，其概率密度函數為f，則核密度估計可表示為

其中，K(.)為核函數，h為一個平滑參數，稱作帶寬或窗口，Kh(.)為縮放核函數。

高斯核函數是比較常用的核函數，對于噪音數據有著較好的抗干擾能力，其數學形式如下：

其參數決定了函數作用范圍，因此其性能對參數十分敏感。為降低函數對參數的依賴性，本文選用指數函數，其數學形式如下：

將式（13）、（15）兩式聯立，可得到概率密度函數表達式為

鄰域密度閾值MinPts∈[1 ,n]，其中n為樣本總數，根據上述方法可確定MinPts不同取值下對應的鄰域半徑參數ε。

噪聲數據量的變化可以用來衡量聚類的效果。隨著鄰域密度閾值MinPts的增大，噪聲數據量逐漸減少，且速度呈現出由慢到快再到慢的趨勢，部分學者［16］基于此認為使得噪聲數據量變化率最大的MinPts最為合適，然后這并不能保證將樣本數據集盡可能地聚合成簇，因此本文對此進行改進，假設g為鄰域密度閾值MinPts到噪聲數據量的一個映射：

最合適的MinPts應滿足以下要求：

其中，n為樣本總數。從上式中可以看出，MinPts的取值應保證噪聲數據不超過樣本總數的5%，這樣可以取得更好的聚類效果。

4 實驗驗證與分析

4.1 實驗準備

本文基于Python語言編寫程序并進行了實驗。選取2013年1月某連續10h內在長江入海口河段部分水域（119.0°E～119.5°E、32.2°N～32.3°N）測得的115098條AIS數據作為樣本。利用DP算法壓縮軌跡時的閾值dMax取0.01，距離結構化度量中的權重參數μ1、μ2、μ3、μ4均取 0.25，改進的基于DBSCAN算法的軌跡聚類算法中的兩個重要參數ε取52.5，MinPts取20。

4.2 實驗結果與分析

對AIS數據進行預處理后，篩選出至少包含100個軌跡點的194條航跡，運用本文提出的多步驟船舶估計聚類方法進行聚類，并與文獻［15］提出的基于行為特征相似度的船舶軌跡聚類方法進行對比，結果如表2所示。

從表1中可以看出，本文方法在獲取更多簇數的情況下，噪聲數據反而較少，且通過下文的主航道提取可以得出本文方法更加合理的結論。

表1 軌跡聚類結果

利用Python作圖，以經度為橫坐標、以緯度為縱坐標，分別將每一類航跡進行展示，如圖5所示。

從圖5中可以看出，船舶在該水域航行的軌跡主要有三條，以類別二為代表的軌跡主要位于所選區域的西南一側，大致航向為東北-東南，并且轉向過程基本在119.10°E～119.15°E完成；以類別三為代表的軌跡主要位于所選區域的東南一側，大致航向為東北-正東，轉向角度小于“類別一”；而以類別一為代表的軌跡顯著特點是航向的多次改變。

為能更好地表示聚類結果，利用Matlab作圖，取每一類軌跡的均值，得到平均軌跡，也可以理解為船舶在該水域航行的三條主要航道，如圖5所示。

圖5 軌跡聚類結果示意圖

圖6 長江口某水域主航道示意圖

值得注意的是，樣本數據中有四條航跡沒有被聚到任何簇中，可以認為它們是“異常”的，往往代表著船舶比較特殊的行為模式，不同于海上目標一般的行動規律。通過整合和比較可知，每一條軌跡都會出現一段基本與y軸平行的部分，而且4條軌跡的航速最大航速不超過7節（圖7），航行過程中基本保持在3節～5節（圖8）。通過對該水域實際情況的調查，得知可能是從事拖帶、引航、水下作業等活動的特殊船舶的軌跡。

圖7 異常軌跡位置變化

圖8 異常軌跡航速變化

5 結語

本文針對目前AIS船舶軌跡聚類過程不夠系統完整的問題，首先對原始AIS數據進行預處理，提出主要包括軌跡壓縮、子軌跡匹配、相似性度量和軌跡聚類等三部分的多步驟船舶軌跡聚類方法，并以長江入海口河段部分水域的真實數據進行實驗驗證，結果表明該方法不僅可以找出船舶在該水域航行的主要航道，而且能夠發現異常軌跡的存在，在航道規劃和海事監管方面有一定的應用意義，對AIS船舶軌跡聚類的研究有一定的參考價值。