基于改進DBSCAN 算法的船舶軌跡聚類與可視化應用

邱文軒，許志遠，翟澤宇，曲勝，張曉鵬，許航

（大連海洋大學，遼寧 大連 116023）

航運業作為龐大的基礎性產業，不斷產生海量數據存儲在船舶識別系統（Automatic Identification System,AIS）中，涵蓋船舶時空信息[1]，為船舶軌跡預測提供豐富的數據源。

劉濤[2]等人提出運用DBSCAN 算法對船舶軌跡進行聚類，分析航域交通流的擁擠區域，通過交通流評判交通擁擠區域；潘家財[3]等利用船舶信息的空間分布來發掘通航環境狀況，得出航速變化率空間分布；Pan[4]等人對DBSCAN 算法進行改進，提出基于密度的對不同線路進行分類，在宏觀視圖上沒有進行可視呈現。Ide K[5]利用AIS 數據計算船舶的港口吞吐量和全球海洋運輸網絡的拓撲結構。綜上，專家學者在軌跡聚類領域做了很多工作，本文根據天津港水域解壓清洗處理后的AIS 數據，改進DBSCAN 算法細化聚類簇后進行時空信息可視化呈現。

1 數據預處理

1.1 屬性選擇

AIS 收集的數據有用信息需要通過數據清洗來獲取數據字段合理范圍[6]，如表1 所示。

表1 船舶軌跡數據字段合理范圍

1.2 數據清洗

假設同一軌跡段上的點pi-1,pi,pi+1為相鄰點，pi對應的航行特征值(位置、航向、航速)為xi，基于pi,pi+1的航行狀態預測pi+1處對應的航行特征值為x’i+1，即x’i+1=xi+f（xi，xi-1）。如果，表明數據發生漂移需要剔除[7]。

式1 為數據漂移算子，（x，y）代表船舶位置特征，v 代表航速特征，c 代表航向特征，w1、w2、w3對應位置、航速向異常閥值[8]。

2 改進DBSCAN 算法

2.1 DBSCAN 算法

DBSCAN 算法原理如圖1 所示。

圖1 DBSCAN 算法原理

2.2 算法改進

改進DBSCAN 算法，通過查詢核心節點以及未標記的點，從而減少查詢次數。在p 包含的對象數不小于MinPts 時，建立新簇C1，然后將點加入N，檢查N 中每個點q,避免重復查詢從而提升算法聚類執行效率。輸入：數據集D，鄰域半徑Eps，最小鄰域點數MinPts；輸出：基于密度的簇的集合。

1：標記所有對象未unvisited;

2：Do；

3：隨機選擇unvisited 對象p；

4：If p 包含的對象數不小于MinPts；

5：創建新簇C1，把p 添加到候選集N；

6：For N 中每個點q；

7：If 點q 與對象p 不重疊不存在核心節點；

8：用新簇C2 標記；

9：Else if 點q 與對象p 重疊且存在核心節點；

10：將對象q 鄰域內unvisited 的點歸入C1；

11：Else if 對象q 與其他標記的節點鄰域重疊；

12：將其中點加入候選集N；

13：End for；

14：Else 標記為噪聲。

3 船舶典型軌跡相似性度量

融合距離MD(The Merge Distance)[9]表示融合后兩條軌跡之間的最短距離，原理如圖2 所示。

圖2 最短子軌跡

通過假定a 和b 兩條軌跡是二維空間內的一系列序列（a1,...,an）,（b1,..,bm）構成，使用d（ai，bj）表示兩點之間在二維平面上的歐式距離，通過序列和a 和b 的最短超軌跡s（a，b）是長度最短的軌跡，a 和b 是s（a，b）的子序列，其長度用L（a，b）表示。通過公式2 從軌跡a 和b 的長度L（a），L（b）獲得融合距離MD（a，b）。

4 實驗與分析

選取渤海灣西端的天津港作為實驗航道，如圖3 所示，公共泊位岸線長14.5 千米是良好的實驗航道。

圖3 天津港段實驗航道衛星圖

在運行64 位Windows10,InterICoreIi7-10700 CPU@和8G 內存的計算機硬件上操作。DBSCAN 算法依賴eps 和MinPts 參數，實驗需要迭代選擇最優參數區間。當數據密度不均勻時，原始聚類軌跡如圖4 所示，效果較差信息呈現較片面且聚類過程耗時較長。

圖4 天津港段船舶AIS 軌跡原始聚類軌跡

當eps=0.0030、MinPts=5 時可以產生良好的聚類效果。改進后的聚類結果如圖5 所示，聚類簇通過細化聚類特征明顯入港軌跡聚類質量較高。

圖5 天津港段船舶AIS 軌跡改進聚類軌跡

通過對DBSCAN 經典算法和改進后的算法進行對比如表2 所示，通過減少運行鄰域樣本點查詢的次數和時間，從而提高效率減少計算時間消耗。

表2 兩種算法對比結果

實驗中對AIS 數據進行聚類，得出了渤海灣西端的天津港主要航道的四條典型軌跡，如圖6 所示，船舶航行的典型軌跡遵循航道的設置，數據聚類分析結果可信，具備參考價值。

圖6 船舶入港典型軌跡