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

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

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

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

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

1 數(shù)據(jù)預處理

1.1 屬性選擇

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

表1 船舶軌跡數(shù)據(jù)字段合理范圍

1.2 數(shù)據(jù)清洗

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

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

2 改進DBSCAN 算法

2.1 DBSCAN 算法

DBSCAN 算法原理如圖1 所示。

圖1 DBSCAN 算法原理

2.2 算法改進

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

1：標記所有對象未unvisited;

2：Do；

3：隨機選擇unvisited 對象p；

4：If p 包含的對象數(shù)不小于MinPts；

5：創(chuàng)建新簇C1，把p 添加到候選集N；

6：For N 中每個點q；

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

8：用新簇C2 標記；

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

10：將對象q 鄰域內(nèi)unvisited 的點歸入C1；

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

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

13：End for；

14：Else 標記為噪聲。

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

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

圖2 最短子軌跡

通過假定a 和b 兩條軌跡是二維空間內(nèi)的一系列序列（a1,...,an）,（b1,..,bm）構(gòu)成，使用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 天津港段實驗航道衛(wèi)星圖

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

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

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

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

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

表2 兩種算法對比結(jié)果

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

圖6 船舶入港典型軌跡