一種基于DBSCAN的船舶會遇實時識別方法

甄榮 RIVEIRO Maria 金永興

摘要：

針對海上交通監(jiān)控中船舶數(shù)量眾多，且對具有潛在碰撞危險的船舶識別效率不高的問題，提出一種基于DBSCAN（帶噪聲的基于密度的空間聚類）的船舶會遇實時識別方法。根據(jù)海上交通風(fēng)險監(jiān)控的研究需求，分析船舶會遇局面的定義。運(yùn)用墨卡托算法計算船舶之間的距離，采用DBSCAN算法進(jìn)行船舶會遇聚類識別。基于浙江舟山群島西南海域航行船舶的AIS數(shù)據(jù)，對設(shè)置不同船舶會遇距離的試驗結(jié)果進(jìn)行比較分析，結(jié)果表明：當(dāng)船舶會遇距離為1 n mile時，可以將56艘船劃分為7個會遇船舶類，占船舶總數(shù)的32.1%，每個會遇船舶類包括2～3艘船。將該方法運(yùn)用到實際海上交通監(jiān)控中，可對每個會遇船舶類中的船舶航行動態(tài)進(jìn)行重點(diǎn)關(guān)注，降低海上交通監(jiān)控人員的工作負(fù)擔(dān)，提高海上交通監(jiān)控的效率。

關(guān)鍵詞：

海上交通監(jiān)控; DBSCAN; 船舶會遇; 航行風(fēng)險

中圖分類號： U698.8

文獻(xiàn)標(biāo)志碼： A

收稿日期： 2017-05-09

修回日期： 2017-07-27

基金項目： 國家自然科學(xué)基金（51709165）;國家留學(xué)基金管理委員會聯(lián)合培養(yǎng)博士生項目（201608310093）;上海市科學(xué)技術(shù)委員會地方院校能力建設(shè)項目（15590501600）;上海海事大學(xué)研究生創(chuàng)新基金（2016ycx077）;上海海事大學(xué)優(yōu)秀博士學(xué)位論文培育項目（2017bxlp003）

作者簡介：

甄榮（1990—），男，內(nèi)蒙古烏蘭察布人，博士生，研究方向為海上智能交通，（E-mail）zrandsea@163.com;

RIVEIRO Maria （1978—），女，瑞典人，副教授，博導(dǎo)，研究方向為可視化分析及其在海上交通監(jiān)控中的應(yīng)用，（E-mail）maria.riveiro@his.se;

金永興（1958—），男，上海人，教授，博導(dǎo)，研究方向為船舶運(yùn)行品質(zhì)評估，（E-mail）yxjin@shmtu.edu.cn

A real-time identification method to ship encounter based on

DBSCAN

ZHEN Rong1，2， RIVEIRO Maria2， JIN Yongxing1

（1. Merchant Marine College， Shanghai Maritime University， Shanghai 201306， China;

2. Informatics Research Centre， University of Skovde， Vstra Gtaland 54128， Sweden）

Abstract：

Aiming at the problem that there are a large number of ships in maritime traffic monitoring and the recognition efficiency for ships with potential collision risk is low， a real-time identification method to ship encounter based on DBSCAN（density-based spatial clustering of applications with noise） is proposed. The definition of ship encounter situation is analyzed according to the research demand of maritime traffic risk monitoring. The distance between ships is calculated using the Mercator algorithm， and the DBSCAN algorithm is applied to the cluster identification of ship encounter. Based on AIS data of ships sailing on southwest sea area of Zhoushan Islands in Zhejiang Province of China， the test results are compared for different ship-encounter radii. The results show that， when the ship encounter radius is 1 n mile， 56 ships can be divided into 7 clusters of ship encounter which compose 32.1% of the total number of ships， and each cluster includes 2 or 3 ships. The method is applied to practical maritime traffic monitoring to pay more attention to the dynamic motion of ships in encounter clusters， which can reduce the workload of maritime traffic monitoring personnel and improve the efficiency of maritime traffic monitoring.

Key words：

maritime traffic monitoring; DBSCAN; ship encounter; sailing risk

0 引 言

在VTS覆蓋的港口或沿海水域，船舶數(shù)量多，通航密度大，船舶航行環(huán)境復(fù)雜。對此類水域內(nèi)船舶航行風(fēng)險進(jìn)行準(zhǔn)確、有效識別是VTS中心值班人員面臨的難題。船舶會遇分析是研究海上交通狀況的一種重要手段[1]，國內(nèi)外學(xué)者對此進(jìn)行了很多研究。潘家財?shù)萚2]設(shè)計了船舶會遇的時空數(shù)據(jù)挖掘算法，根據(jù)歷史AIS數(shù)據(jù)，對水域內(nèi)船舶會遇空間、會遇時間和會遇船舶類等進(jìn)行了分析。任亞磊[3]根據(jù)船舶領(lǐng)域模型，對船舶會遇從總體會遇情況、會遇船舶參數(shù)、會遇船舶時空分布、會遇態(tài)勢等4個方面進(jìn)行了定量分析。肖瀟等[4]對單船在航行過程中的會遇信息，如會遇空間、會遇數(shù)量、會遇態(tài)勢和最近會遇距離（distance to closest point of approach， DCPA）進(jìn)行了計算，并將計算結(jié)果在電子海圖上進(jìn)行了可視化展示。RONG等[5]結(jié)合人工勢場法和船舶領(lǐng)域模型對歷史船舶會遇樣本進(jìn)行了提取和模擬研究。ZHANG等[6-7]基于船舶領(lǐng)域和最小碰撞距離從歷史AIS數(shù)據(jù)中提取船舶會遇樣本，對會遇樣本進(jìn)行了危險度排序。

現(xiàn)有研究從不同角度對船舶會遇進(jìn)行了定義，并設(shè)計了相應(yīng)的算法，側(cè)重于從歷史AIS數(shù)據(jù)中提取船舶會遇數(shù)量、會遇時間、會遇空間、會遇態(tài)勢、DCPA等特征，研究結(jié)果可為海上通航環(huán)境危險度時空分布研究、海上交通規(guī)劃和航行規(guī)則制定提供依據(jù)。本文從沿海港口水域船舶航行風(fēng)險的實時識別出發(fā)，提出一種基于DBSCAN（density-based spatial clustering of applications with noise）的船舶會遇實時識別方法。通過DBSCAN算法，設(shè)定不同的會遇距離，快速實時地實現(xiàn)會遇船舶和非會遇船舶的識別和提取，縮小船舶會遇樣本的選取范圍。

1 船舶會遇的定義

船舶會遇通常表現(xiàn)為船舶在海上航行過程中從不同的方向會聚而發(fā)生的相遇情況[8]。根據(jù)研究目的和要求的不同，船舶會遇標(biāo)準(zhǔn)和定義并不統(tǒng)一，通常可以總結(jié)為以下兩種情況：

（1）宏觀海上通航環(huán)境危險度評估。由于船舶會遇是船舶發(fā)生碰撞事故的必要條件，而某一海域在一段時間內(nèi)發(fā)生交通事故的數(shù)量是有限的，所以通常采用船舶的會遇情況來宏觀地評估這一海域的通航環(huán)境危險度。根據(jù)宏觀海上通航環(huán)境危險度評估的要求，船舶會遇標(biāo)準(zhǔn)通常是航行船舶間的距離在一定范圍內(nèi)構(gòu)成會遇局面，無須考慮是否構(gòu)成碰撞危險或緊迫局面。在開闊水域或者沿海水域，會遇距離可取較大值，而在港口受限水域會遇距離應(yīng)適當(dāng)取較小值。

（2）微觀碰撞危險度評估。在船舶自動避碰領(lǐng)域，船舶會遇標(biāo)準(zhǔn)是兩船相遇后為避免碰撞危險而需要采取避碰行動的局面[3]。根據(jù)兩船的會遇態(tài)勢和碰撞危險度的大小，進(jìn)行相應(yīng)的避碰決策和復(fù)航時機(jī)決策[5，9]。

本文考慮在VTS覆蓋水域船舶宏觀碰撞危險實時識別的要求，即對于任一在此類水域航行的船舶，如果在其周圍一定的距離范圍內(nèi)存在他船，則與之組成會遇船舶類，否則他船被視為非會遇船舶。因而，會遇船舶的識別可視為基于船舶在航行水域內(nèi)密度的聚類問題。DBSCAN算法是一種帶噪聲的基于密度的空間聚類方法，能夠?qū)⒕哂懈呙芏鹊膮^(qū)域劃分為簇，并在具有噪聲的數(shù)據(jù)中發(fā)現(xiàn)任意形狀的簇[10]，在城市交通擁堵識別[11，12]、餐飲集群識別[13]、航空網(wǎng)絡(luò)優(yōu)化[14]、鐵路運(yùn)輸異物檢測[15]等方面有著較好的應(yīng)用。本文用DBSCAN算法對海上航行船舶進(jìn)行實時聚類處理，從而提取會遇船舶類。

2 船舶會遇的密度聚類識別方法

2.1 DBSCAN算法

聚類是數(shù)據(jù)挖掘中的一個重要方法，它根據(jù)數(shù)據(jù)之間的相似性或距離，無監(jiān)督地將數(shù)據(jù)劃分為不同的類別，保證類內(nèi)數(shù)據(jù)之間的距離盡可能小，類間數(shù)據(jù)之間的距離盡可能大。根據(jù)DBSCAN算法的相關(guān)概念，DBSCAN算法的流程[10，16]如下：

輸入：一個包含n個對象的數(shù)據(jù)集D，領(lǐng)域半徑ε，領(lǐng)域密度閾值M。

輸出：具有類別標(biāo)簽的數(shù)據(jù)集。

（1）隨機(jī)選擇一個unvisited對象p，

標(biāo)記p為visited，

若p的ε-領(lǐng)域內(nèi)至少有M個對象，

則創(chuàng)建一個新簇C， 并把p加入到C。

令N為p的ε-領(lǐng)域中的對象集合。

（2）對于N中的每一個p′：若p′是unvisited，則標(biāo)記p′為visited;若p′的ε-領(lǐng)域內(nèi)至少有M個對象，則把這些對象添加到N;若p′還不是任何簇的成員，則把p′加入到C。

（3）重復(fù)步驟（2），直到?jīng)]有標(biāo)記為unvisited的對象。

（4）輸出C，

否則標(biāo)記p為噪聲。

（5）重復(fù)步驟（1）～（4），直到?jīng)]有標(biāo)記為unvisited的對象。

2.2 船舶會遇識別

2.2.1 船舶間距離的計算

在運(yùn)用DBSCAN算法識別船舶會遇的過程中，需要根據(jù)船舶間的距離確定簇以及會遇船舶類。本文以AIS信息中航行船舶實時經(jīng)緯度作為聚類數(shù)據(jù)對象，但考慮到由地球這個不規(guī)則橢圓體造成的在墨卡托海圖上存在緯度漸長現(xiàn)象，即緯度1′長度隨著緯度升高而逐漸增長，從而使緯度間隔相等的緯線之間的距離不相等，為保證跨越緯度差較大海域的船舶之間距離的一致，船舶間距離的計算采用墨卡托算法。

假設(shè)有兩艘船VO和VT， 在AIS動態(tài)信息中包含VO和VT的實時經(jīng)度（λ）、緯度（φ）、對地速度和對地航向，兩艘船之間距離的計算過程如下：

Dλ=λT-λO （1）

Dφ=φT-φO（2）

MP=7 915.7lgtanπ4+φ21-esin φ1+esin φe/2 （3）

DMP=MP，T-MP，O （4）

B=arctan（Dλ/DMP） （5）

D=Dφ/cos B （6）

式中：Dλ和Dφ分別為經(jīng)度差和緯度差;MP為緯度漸長率;DMP為不同緯度間的緯度漸長率差;B為方位角;D為兩船間的距離，n mile;e為地球橢圓體的偏心率;指數(shù)e/2中的e是自然對數(shù)的底。

2.2.2 船舶會遇識別參數(shù)確定

在運(yùn)用DBSCAN算法識別船舶會遇的過程中，需要確定領(lǐng)域半徑ε和領(lǐng)域密度閾值M。ε對應(yīng)船舶間的會遇距離。由于只要任意兩個船舶間距離小于等于ε即構(gòu)成會遇，所以M的值為2。

關(guān)于船舶會遇距離的設(shè)定，潘家財?shù)萚2]設(shè)定的廈門灣的會遇距離是300 m （約0.16 n mile），會遇距離較小，這主要是考慮到廈門灣屬于狹窄的受限水域。肖瀟等[4]在開闊的臺灣海峽設(shè)定的會遇距離為3.8 n mile。譚志榮等[17]在基于Near Miss局面的成山頭水域交通沖突研究中采用DCPA 500 m作為空間閾值。通過對比發(fā)現(xiàn)，在已有研究中船舶會遇距離的設(shè)定并沒有統(tǒng)一的標(biāo)準(zhǔn)，通常在船舶交通密集的水域，會遇距離取較小值，在開闊水域，會遇距離取較大值。

3 舟山群島西南海域船舶會遇識別

浙江舟山群島西南海域包括螺頭航道、金塘航道、蝦峙門航道、雙峙門航道、冊子水道等，它們是船舶進(jìn)出寧波舟山港區(qū)的主要航道。隨著寧波舟山港吞吐量的增加，該海域船舶交通密集態(tài)勢復(fù)雜，再加上海域內(nèi)島嶼眾多，因此對該海域內(nèi)船舶航行風(fēng)險進(jìn)行監(jiān)控一直是相關(guān)海事局VTS中心的工作重點(diǎn)。本文選取“船隊在線”網(wǎng)站提供的浙江舟山群島西南海域2016年12月1日9：00的船舶AIS信息工作為試驗數(shù)據(jù)，原始船舶AIS信息見圖1，收到的AIS信息來自56艘在航船舶。

圖1 舟山群島西南海域船舶AIS信息

3.1 不同會遇距離的船舶會遇識別

根據(jù)海上交通工程中水域特點(diǎn)劃分方法，圖1所示的舟山群島西南海域靠近大陸且被島嶼圍繞，故可被歸類為受限水域[1]，會遇距離可取較小值。當(dāng)運(yùn)用DBSCAN算法對會遇船舶樣本進(jìn)行實時識別和提取時，如果會遇距離過大則會造成將所有船舶識別為一個會遇船舶類，如果會遇距離過小則可能無法形成會遇船舶類。根據(jù)VTS中心的值班人員和在該海域有航行經(jīng)驗的船舶駕駛員的建議，確定船舶會遇距離的范圍為1～3 n mile。當(dāng)會遇距離小于1 n mile時，所有船舶都是非會遇船舶，失去了監(jiān)控的意義。

設(shè)定會遇距離分別為3 n mile， 2 n mile和1 n mile，得到的船舶會遇識別結(jié)果分別見圖2～4，圖中會遇類船舶用點(diǎn)號表示，非會遇類船舶用三角號表示。

圖2 會遇距離為 3 n mile時的船舶會遇識別

圖3 會遇距離為 2 n mile時的船舶會遇識別

圖4 會遇距離為 1 n mile時的船舶會遇識別

從圖2可以看出，當(dāng)會遇距離為3 n mile時，該海域有3個會遇船舶類。第1個會遇船舶類包含4艘船，第2個會遇船舶類包括37艘船，第3個會遇船舶類包含5艘船。其余10艘船在其各自的3 n mile范圍內(nèi)沒有其他船出現(xiàn)，為非會遇船舶?？梢娫谠撍颍O(shè)置3 n mile的會遇距離導(dǎo)致會遇船舶類較少，每類包含的船舶數(shù)量較多，不能有效地得到具體的船舶會遇及航行風(fēng)險信息。

從圖3可以看出，當(dāng)會遇距離為2 n mile時，該海域有10個會遇船舶類。每個會遇船舶類包含的船舶數(shù)量見表1。由表1可知，第2個會遇船舶類包含10艘船，第4個會遇船舶類包含7艘船，第7個會遇船舶類包含6艘船，其他各會遇船舶類包含2～3艘船。與會遇距離為3 n mile時的識別結(jié)果相比，會遇船舶類較多，會遇識別較明確。然而，第2，4，7個會遇船舶類包含較多的船，這些船之間的航行風(fēng)險識別還是較為模糊的。

從圖4可以看出，當(dāng)會遇距離為1 n mile時，該海域有7個會遇船舶類，每個會遇船舶類包含2～3艘船（見表2），因而在監(jiān)控時可以清晰地看到具體的、有潛在碰撞風(fēng)險的船舶對，識別效果明確。

表1 會遇距離為2 n mile時每個會遇船舶類

包含的船舶數(shù)量

表2 會遇距離為1 n mile時每個會遇船舶類

包含的船舶數(shù)量

3.2 結(jié)果比較分析

將3個不同會遇距離下得到的會遇船舶類數(shù)量、會遇船舶數(shù)量和非會遇船舶數(shù)量進(jìn)行比較分析，統(tǒng)計結(jié)果見表3。

表3 不同會遇距離下的統(tǒng)計結(jié)果

從表3可知，隨著會遇距離從3 n mile減少到1 n mile，產(chǎn)生的會遇船舶類數(shù)量先增大后減少，會遇船舶數(shù)量所占比例減小（從82.1%減小到32.1%），相應(yīng)的非會遇船舶數(shù)量所占比例增加（從17.9%增加到67.9%）。因此，通過DBSCAN算法，可將海域內(nèi)航行的船舶實時劃分為多個相互間距離小于等于會遇距離的船舶類，過濾掉非會遇船舶，將少量的會遇船舶類標(biāo)識出來，提供給VTS中心值班人員，提高海上交通監(jiān)控的效率。

4 結(jié) 論

提出一種用于海上交通監(jiān)控的基于密度聚類的船舶會遇實時識別方法。以航行船舶發(fā)射的AIS信息為數(shù)據(jù)來源，運(yùn)用DBSCAN算法對船舶會遇進(jìn)行聚類識別。根據(jù)海域情況設(shè)定合適的船舶會遇距離，得到相應(yīng)的會遇識別結(jié)果。以浙江舟山群島西南海域為例，分別設(shè)定3 n mile，2 n mile和1 n mile為會遇距離進(jìn)行試驗，結(jié)果表明當(dāng)會遇距離為1 n mile時可以過濾掉大部分非會遇船舶，得到7個會遇船舶類，對實際水域內(nèi)高風(fēng)險船舶的監(jiān)控適用性較好。

實際上，在沿海港口水域還有未裝設(shè)AIS的小型船舶，以及部分裝設(shè)了AIS但沒有開啟的船舶，這對船舶會遇實時識別的可靠性存在影響。在此情況下，VTS中心可以考慮采用雷達(dá)信號作為數(shù)據(jù)源，用以保證船舶會遇實時識別的有效性。在實際應(yīng)用中，可以根據(jù)海域特點(diǎn)、船舶駕駛員航行習(xí)慣以及海事部門監(jiān)控要求選取合適的會遇距離。本文初步實現(xiàn)了設(shè)定會遇距離下的船舶會遇識別，在后續(xù)研究中將考慮在航船舶的靜態(tài)、動態(tài)特性對船舶會遇距離的影響，針對不同的船舶設(shè)定不同的船舶會遇距離進(jìn)行更加精確的船舶會遇識別。

參考文獻(xiàn)：

[1]吳兆麟， 朱軍. 海上交通工程[M]. 2版. 大連： 大連海事大學(xué)出版社， 2004： 135-136.

[2]潘家財， 姜青山， 邵哲平. 船舶會遇的時空數(shù)據(jù)挖掘算法及應(yīng)用[J]. 中國航海， 2010， 33（4）： 57-60.

[3]任亞磊. 基于數(shù)據(jù)的船舶會遇特征研究[D]. 武漢： 武漢理工大學(xué)， 2013.

[4]肖瀟， 趙強(qiáng)， 邵哲平， 等.基于AIS的特定船舶會遇實況分布[J]. 中國航海， 2014， 37（3）： 50-53.

[5]RONG H， TEIXEIRA A， SOARES C G. Evaluation of near-collisions in the Tagus River Estuary using a marine traffic simulation model[J]. Zeszyty Naukowe Akademii Morskiej w Szczecinie， 2015， 43： 68-78.

[6]ZHANG W B， GOERLANDT F， MONTEWKA J， et al. A method for detecting possible near miss ship collisions from AIS data[J]. Ocean Engineering， 2015， 107： 60-69.

[7]ZHANG W B， GOERLANDT F， KUJALA P， et al. An advanced method for detecting possible near miss ship collisions from AIS data[J].Ocean Engineering， 2016， 124： 141-156.

[8]胡甚平. 船舶會遇過程中避碰階段的劃分與量化[J].中國航海， 2001， 24（2）： 83-87.

[9]賀益雄， 黃立文， 牟軍敏， 等. 交叉相遇局面讓路船自動避碰行動方案[J]. 哈爾濱工程大學(xué)學(xué)報， 2015， 36（8）： 1024-1029.

[10]ESTER M， KRIEGEL H P， SANDER J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining （KDD-96）， 1996， 96（34）： 226-231.

[11]魯小丫， 宋志豪， 徐柱， 等.利用實時路況數(shù)據(jù)聚類方法檢測城市交通擁堵點(diǎn)[J].地球信息科學(xué)學(xué)報， 2012， 14（6）： 775-780.

[12]劉暢， 李治軍， 姜守旭. 基于DBSCAN 算法的城市交通擁堵區(qū)域發(fā)現(xiàn)[J]. 智能計算機(jī)與應(yīng)用， 2015（3）： 69-71.

[13]楊帆， 徐建剛， 周亮. 基于DBSCAN 空間聚類的廣州市區(qū)餐飲集群識別及空間特征分析[J]. 經(jīng)濟(jì)地理， 2016， 36（10）： 110-116.

[14]王世錦， 曹希， 酈晴云， 等. 航路網(wǎng)絡(luò)生成及優(yōu)化[J]. 航空計算技術(shù)， 2016， 46（4）： 4-8.

[15]郭保青， 朱力強(qiáng)， 史紅梅. 基于快速DBSCAN 聚類的鐵路異物侵限檢測算法[J]. 儀器儀表學(xué)報， 2012， 33（2）： 241-246.

[16]HAN J， PEI J， KAMBER M. Data mining： concepts and techniques[M]. Elsevier， 2011： 418-419.

[17]譚志榮， 張球林， 王偉， 等. 基于Near Miss的成山頭水域交通沖突風(fēng)險可視化[J]. 中國航海， 2016， 39（4）： 43-46， 107.