基于DBSCAN的港口泊位自動識別算法設計

劉鑫鑫， 韓 懿

(中遠海運科技股份有限公司，上海 200135)

0 引 言

近年來，船舶自動識別系統(tǒng)(Automatic Identification System，AIS)在船上得到廣泛應用，裝有AIS的船舶通常配合全球定位系統(tǒng)(Global Positioning System，GPS)，將船位、船速、改變航向率和航向等船舶動態(tài)數(shù)據(jù)與船名、呼號、船型、吃水和危險貨物等船舶靜態(tài)信息相結合，實時向外廣播，為航運企業(yè)和海事機構等進行船舶安全管理提供基礎數(shù)據(jù)。當前，在信息技術不斷發(fā)展的大背景下，AIS數(shù)據(jù)已從服務航行安全保障走向服務航運企業(yè)的經(jīng)營管理和行業(yè)決策，成為航運大數(shù)據(jù)挖掘的基礎信息，幫助企業(yè)對船舶管理、成本核算、風險控制和運力分配等進行優(yōu)化。

在已有研究中：張智凱等[1]在總結多泊位油品碼頭平面布置要點時指出了泊位空間平面布置的重要性；汪士寒等[2]基于排隊論，對鼠浪湖鐵礦石碼頭泊位的布局進行了優(yōu)化研究，指出鼠浪湖泊位優(yōu)化方案是基于泊位位置和具體信息得到的。這些研究都是在單個港口的靜態(tài)泊位數(shù)據(jù)的基礎上開展的。為進一步研究泊位對港口作業(yè)的影響，找出泊位的具體位置尤為重要。葉仁道等[3]提出采用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)密度聚類算法研究船舶停泊點，雖然采用DBSCAN聚類了船舶在海上的停泊點，但只是進行了初步的聚類，沒有對聚類結果進行處理，獲取的只是海上一些零散的點，且聚類的是海上的停泊點而非泊位，不具備成為普遍實用性數(shù)據(jù)產(chǎn)品的可行性。2018年，中遠海運科技股份有限公司開始基于大數(shù)據(jù)技術和數(shù)據(jù)服務技術研發(fā)航運數(shù)據(jù)中臺，目標是應用海量的AIS數(shù)據(jù)、港口基礎數(shù)據(jù)和水文氣象數(shù)據(jù)實現(xiàn)對船舶航行全生命周期內行為的動態(tài)識別，并進一步將該平臺拓展應用到港口動態(tài)監(jiān)控、航線識別與動態(tài)監(jiān)控、船隊運營情況和大宗商品運力監(jiān)控等領域中。本文主要對港口泊位的位置進行研究，實現(xiàn)泊位從靜態(tài)信息到動態(tài)信息的自動化識別，用于對泊位作業(yè)狀態(tài)進行實時監(jiān)控,對歷史數(shù)據(jù)進行分析,并實現(xiàn)數(shù)據(jù)可視化，為船舶、港口的作業(yè)計劃優(yōu)化和風險管理提供參考。

1 數(shù)據(jù)采集

本文基于船舶AIS歷史數(shù)據(jù)、船舶動態(tài)信息和船舶靜態(tài)信息，采用DBSCAN密度聚類算法對全球4 079個港口的泊位進行自動識別，得到泊位的位置、方向、岸線長度和類型等信息，用于實時跟蹤船舶在港作業(yè)動態(tài)，分析泊位歷史作業(yè)情況。圖1為某船舶某個完整航次的動態(tài)信息和氣象條件。

圖1 某船舶某個完整航次的動態(tài)信息和氣象條件

本文研究的基礎數(shù)據(jù)主要為AIS歷史數(shù)據(jù)、船舶在港動態(tài)信息和船舶靜態(tài)信息。AIS主要將航運動態(tài)定義為航行、錨泊、靠泊和擱淺等4種，分別用0、1、5和6表示，航運數(shù)據(jù)中臺基于AIS動態(tài)數(shù)據(jù)實現(xiàn)對船舶行為的識別，即對所有船舶靠泊行為的識別(如圖1所示)。以錦州港為例，從船舶歷史動態(tài)數(shù)據(jù)中提取的歷史靠泊數(shù)據(jù)見圖2。從船舶歷史動態(tài)數(shù)據(jù)中提取的數(shù)據(jù)字段說明見表1。

圖2 從船舶歷史動態(tài)數(shù)據(jù)中提取的歷史靠泊數(shù)據(jù)

表1 從船舶歷史動態(tài)數(shù)據(jù)中提取的數(shù)據(jù)字段說明

2 算法比較及選擇

常見的聚類算法主要有基于密度的聚類方法(代表算法為DBSCAN算法)、基于層次的聚類方法(代表算法為BIRCH算法)和基于劃分的聚類方法(代表算法為K-Means算法)等3類。此外還有一些基于這3類算法的衍生算法。本文主要對K-Means算法和DBSCAN算法進行對比分析。

2.1 K-Means算法

在應用K-Means算法時,需先確定樣本類的個數(shù)n，從樣本中隨機挑選n點作為類心，迭代更新類心,直到類心不再改變，流程如下：

1)在樣本中隨機選取K個點，作為每一類的中心點。

2)計算余下n-K個樣本點到每個聚類中心的距離(距離有很多種，這里采用歐式距離)。對于每個樣本點，將其歸到與其距離最近的聚類中心所屬的類中。

3)重新計算每個聚類中心的位置，步驟2)中得到的結果是n個點都有自己所屬的類，對每一類內的所有點取平均值(這里假設是二維空間，即對x坐標和y坐標分別取平均值)，計算出新的聚類中心。

4)重復步驟2)和步驟3)的操作，直到所有的聚類中心不再改變。

2.2 DBSCAN密度聚類算法

DBSCAN密度聚類算法是基于密度的聚類算法，在應用該算法時,不需要預先確定簇的個數(shù)，只需設置半徑eps和半徑內最少點的個數(shù)min_samples即可。該算法將數(shù)據(jù)點分為3類，其中：核心點是在半徑eps內點的數(shù)量超過min_samples的點；邊界點是在半徑eps內點的數(shù)量小于min_samples，但落在核心點的鄰域內的點；噪聲點是核心點和邊界點以外的點。主要概念定義如下。

1)直接密度可達：給定一個對象集合D，若對象p在對象q的eps鄰域內，而對象q是一個核心對象，則稱對象p從對象q出發(fā)時是直接密度可達的。

2)密度可達：若存在一個對象鏈p1,…,pi,…,pn，滿足pi=p和pn=q,pi是從pi-1出發(fā)時關于eps和min_samples直接密度可達的，則對象q是從對象p出發(fā)時關于eps和min_samples密度可達的。

3)密度相連:若存在對象O∈D，使對象p和q都是從O出發(fā)時關于eps和min_samples密度可達的，則對象p到q是關于eps和min_samples密度相連的。

DBSCAN算法原理[4]如下：

1)DBSCAN通過檢查數(shù)據(jù)集中每點的eps鄰域搜索簇，若點p的eps鄰域內包含的點多于min_samples個，則創(chuàng)建一個以p為核心對象的簇；

2)DBSCAN迭代地聚集從這些核心對象出發(fā)時直接密度可達的對象，這個過程可能涉及一些密度可達簇的合并；

3)當沒有新的點添加到任何簇時，該過程結束。

2.3 算法選擇

研究初期選定的算法是K-Means算法，采用該算法的關鍵在于確定類的數(shù)量，通過搜索引擎搜索港口泊位的真實信息。在應用該算法過程中存在幾個無法避免的問題。

1)泊位數(shù)(即類的個數(shù))不能準確獲取。很多港口的泊位情況并沒有在網(wǎng)絡上實時更新，通過搜索引擎搜索，搜索到的泊位數(shù)量并不準確。

2)由于漂移等問題，AIS原始數(shù)據(jù)中會有很多噪聲點或錯誤的船舶狀態(tài)信息，在此情況下按真實泊位數(shù)量聚類，會導致一些分開的泊位聚在同一個類中，或同一個泊位聚在不同的類中。

以錦州港為例，首先搜索到該港有24個泊位(更新時間為2019年9月)，采用K-Means算法進行聚類，結果見圖3。圖3中：不同的顏色代表不同的泊位；方框部分沒有分開，方框內應該是同一泊位，但被分到了2個泊位中；右下角很多零散的泊位被分到了一起作為1個泊位，這樣的效果非常不理想。

圖3 采用K-Means算法聚類的效果

為避免K-Means算法存在的上述問題，嘗試采用DBSCAN算法。該算法的優(yōu)勢在于不需要提前設置類的個數(shù)，只需設置搜索半徑和半徑內點的最少個數(shù)，對不規(guī)則圖形有較好的聚類效果。圖4為采用DBSCAN算法聚類的效果。從圖4中可看出，方框內的泊位被較好地聚類了出來，右下角的零散泊位也得到了很好的分類。

圖4 采用DBSCAN算法聚類的效果

上述聚類算法各有優(yōu)劣，可根據(jù)不同的應用場景選擇合適的聚類算法。本文主要對AIS靠泊數(shù)據(jù)進行聚類，首先排除圖團體檢測，圖團體檢測使用場景為數(shù)據(jù)可被表示為網(wǎng)絡或圖。由于在聚類之前無法獲取泊位的具體個數(shù)，從網(wǎng)絡上獲取的泊位數(shù)據(jù)不完整且準確度不夠高，因此不能采用K-Means算法和高斯混合模型。

DBSCAN聚類算法、凝聚層次聚類算法和均值漂移聚類算法都不需要先確定類的數(shù)量。凝聚層次聚類算法的復雜度較高，不適合計算數(shù)量巨大的數(shù)據(jù)，同時對奇異值比較敏感，在AIS數(shù)據(jù)質量較低的情況下不適合采用該算法。相對于均值漂移算法，DBSCAN聚類算法對異常數(shù)據(jù)不敏感，且能發(fā)現(xiàn)任意形狀的簇，非常符合課題需要，可較好地擬合出泊位的形狀和大小。

3 算法設計和實現(xiàn)

3.1 算法工作流程

DBSCAN聚類算法的工作流程(見圖5)如下：

圖5 DBSCAN聚類算法工作流程

1)提取某港口的靠泊數(shù)據(jù)，包括船舶的水上移動通信業(yè)務標識碼(Maritime Mobile Service Identify，MMSI)、靠泊時間、艏向和經(jīng)緯度坐標。

2)對數(shù)據(jù)進行分類。

(1)按集裝箱船、液散船、干散貨船、客船和其他船型等類別,將不同類型的船分開；

(2)分離出可能要修理的船，停靠時間大于200 h的船屬于修理船。

3)對泊位進行聚類，采用DBSCAN算法對不同類型船舶的靠泊位置坐標進行計算。

4)獲取泊位特征。

(1)計算每個簇的中心點。

(2)計算簇的長度。

(3)計算簇的方向。

① 若有艏向，則取艏向的眾數(shù)作為泊位方向；

② 若沒有艏向，則以簇內距離最遠的2個點連線的方向作為泊位方向。

5)根據(jù)泊位內靠泊船舶的類型，按“泊位類型+序號”的形式對泊位進行命名。

6)將計算結果輸出到數(shù)據(jù)庫中。

7)前端調用數(shù)據(jù)庫,并將其可視化到地理信息系統(tǒng)(Geographic Information System，GIS)地圖上。

3.2 關鍵步驟實現(xiàn)

本文研究的關鍵步驟為確定DBSCAN聚類參數(shù)、泊位位置、岸線長度和泊位類型。

3.2.1 確定DBSCAN聚類參數(shù)

DBSCAN聚類參數(shù)有eps和min_samples 2個。

1)對于參數(shù)eps，由于輸入的坐標是地理上的經(jīng)緯度坐標，需將傳統(tǒng)距離通過單位變換轉換到地理坐標系中。經(jīng)緯度單位與國際長度單位之間的變換關系為：赤道上經(jīng)度1°為111 km；經(jīng)線上緯度1°為111 km；其他緯線上經(jīng)度1°為111 km×cosA(A為緯度)。

首先確定eps，若eps的值過大，會導致噪聲點被歸入到類內，類的數(shù)量會比較少；若eps的值過小，會導致類的數(shù)量過多。根據(jù)實際情況，eps的取值范圍為20～200 m，對應到地理坐標系上約為0.000 2°～0.002 0°。

2)對于參數(shù)min_samples，若其值過大，會導致離群點變多，類變多，同一個泊位被劃分到2個不同的類中;若min_samples的值過小，會導致簇中包含過多的離群點。

3.2.2 確定泊位位置和岸線長度

首先確定各泊位的中心點，各泊位中數(shù)據(jù)點的外形為長條形，可根據(jù)類內經(jīng)緯度極值的平均值獲取類的中心點，有

(1)

(2)

式(1)和式(2)中：λcenter和φcenter分別為類的中心點的經(jīng)度和緯度；λmax和λmin分別為類內經(jīng)度的極大值和極小值；φmax和φmin分別為類內緯度的極大值和極小值。

其次確定泊位的長度和方向，其中泊位長度L的計算式為

(3)

最后根據(jù)泊位的方向確定泊位的2個端點。泊位方向優(yōu)先考慮采用船舶?？繒r的方向，即艏向?？坎磿r艏向的眾數(shù)定義為泊位方向。采用三角函數(shù)計算，以泊位長度為斜邊長，假設中心點為泊位方向角的頂點，計算端點與中心點的相對位置差。

(4)

(5)

根據(jù)經(jīng)緯度坐標差計算2個端點P1和P2的值,有

P1=(λcenter+λral,φcenter+φral)

(6)

P2=(λcenter-λral,φcenter-φral)

(7)

然而，有很多艏向數(shù)據(jù)缺失，使得艏向不能單純作為泊位方向。由于通過觀察發(fā)現(xiàn)船舶都是靠著泊位?？康?，數(shù)據(jù)可視化形狀為長條形，因此可根據(jù)類的形狀確定泊位的方向。先取類內的2個極值點，即經(jīng)度最大和最小的2個點，取二者的緯度值，分為2種情況(圖6和圖7)。

圖6 無艏向情況1

圖7 無艏向情況2

1)最大經(jīng)度點的緯度值小于最小經(jīng)度點的緯度值為情況1，此時泊位2個端點為

P1=(λmin,φmin)

(8)

P2=(λmax,φmax)

(9)

2)最大經(jīng)度點的緯度值大于最小緯度值點的緯度值為情況2，此時泊位2個端點為

P1=(λmin,φmax)

(10)

P2=(λmax,φmin)

(11)

3.2.3 確定泊位類型

確定泊位的位置、方向和長度之后就可將泊位可視化在地圖上，但在實際中不同泊位的船舶靠泊狀態(tài)和作業(yè)狀態(tài)是不同的，因此要區(qū)分不同泊位的類型。本文根據(jù)每個分類中船舶的主要類型確定泊位的類型。

將所有處于跟蹤動態(tài)的船舶分為集團船和非集團船2種，由于非集團船相關資料的準確性未得到驗證，故優(yōu)先使用集團船確定泊位類型。若類內集團船只有1種類型，則可直接確定泊位的類型。若類內集團船有2種類型，其中80%以上為1種船型，另外有一些是液散船，可考慮少部分船為加油船，泊位類型依舊按占比80%以上的船型判斷。若類內集團船有多種船型，則設置泊位為通用型，其中液散船由于其特殊性，只能在特定的泊位?？坎?，將其細分為液化石油氣(Liquefied Petroleum Gas,LPG)船、液化天然氣(Liquefied Natural Gas，LNG)船和原油船。當類內都是液散船時，若其中有LNG船、LPG船和原油船，則優(yōu)先將泊位類型確定為LPG船泊位、LNG船泊位和原油船泊位。類似的，當類內有鐵礦石船時，優(yōu)先將泊位確定為鐵礦石船泊位。此外還有一種重要的泊位類型，即修理泊位，該類型泊位需單獨確定，對靠泊時長超過200 h的船進行聚類，聚類出來的泊位即為修理泊位，修理泊位由于其特殊性，后期需單獨確認其可靠性。

4 結果和結論

采用DBSCAN聚類算法計算各港口的泊位信息，輸出的內容為每個泊位的關聯(lián)港口代碼、類型、中文名稱和位置線的點坐標(見圖8)。

圖8 聚類并處理后的結果

目前該航運數(shù)據(jù)中臺已基于DBSCAN聚類算法挖掘出全球4 079個港口34 954個泊位，并結合GIS地圖進行了展示，以錦州港為例，聚類結果地圖展示見圖9，美國IHS公司數(shù)據(jù)源泊位與采用DBSCAN聚類算法聚類結果綜合展示見圖10。圖10中共有27個泊位,其中有1個液散泊位未被IHS收錄,IHS數(shù)據(jù)源泊位中有1個泊位采用該算法未找到。出現(xiàn)該問題的主要原因在于,該泊位樣本點較少,隨著數(shù)據(jù)的增加,通過該算法,可根據(jù)實際情況找到該泊位。相對于IHS數(shù)據(jù)源,該算法更靈活,可根據(jù)數(shù)據(jù)的增加找到新增泊位。綜合所有港口，采用該算法的泊位位置識別準確率可達到90%，部分泊位會出現(xiàn)類型錯誤和多個泊位被識別為1個的情況，這些問題將在后續(xù)優(yōu)化中予以解決。

圖9 聚類結果地圖展示圖

圖10 IHS數(shù)據(jù)源泊位與聚類結果綜合展示

5 結 語

本文采用DBSCAN密度聚類算法識別出了港口泊位的位置、方向、長度和類型等信息。根據(jù)全球港口的泊位信息，可使船舶動態(tài)跟蹤更加準確，有利于船公司對船舶進行數(shù)字化管理，有利于港航數(shù)字化協(xié)同。

下一步的主要工作是對泊位信息進行動態(tài)修正和動態(tài)監(jiān)控,并對歷史數(shù)據(jù)進行分析。例如，隨著數(shù)據(jù)維度的繼續(xù)增加，可對泊位信息進行更準確的描述，將泊位名稱、岸線長度變化、前沿吃水變化和適合作業(yè)的船型等擴充到泊位信息中。