一种基于DBSCAN的船舶会遇实时识别方法
甄荣 RIVEIRO Maria 金永兴
摘要：
針对海上交通监控中船舶数量众多，且对具有潜在碰撞危险的船舶识别效率不高的问题，提出一种基于DBSCAN（带噪声的基于密度的空间聚类）的船舶会遇实时识别方法。根据海上交通风险监控的研究需求，分析船舶会遇局面的定义。运用墨卡托算法计算船舶之间的距离，采用DBSCAN算法进行船舶会遇聚类识别。基于浙江舟山群岛西南海域航行船舶的AIS数据，对设置不同船舶会遇距离的试验结果进行比较分析，结果表明：当船舶会遇距离为1 n mile时，可以将56艘船划分为7个会遇船舶类，占船舶总数的32.1%，每个会遇船舶类包括2～3艘船。将该方法运用到实际海上交通监控中，可对每个会遇船舶类中的船舶航行动态进行重点关注，降低海上交通监控人员的工作负担，提高海上交通监控的效率。
关键词：
海上交通监控; DBSCAN; 船舶会遇; 航行风险
中图分类号： U698.8
文献标志码： A
收稿日期： 2017-05-09
修回日期： 2017-07-27
基金项目： 国家自然科学基金（51709165）;国家留学基金管理委员会联合培养博士生项目（201608310093）;上海市科学技术委员会地方院校能力建设项目（15590501600）;上海海事大学研究生创新基金（2016ycx077）;上海海事大学优秀博士学位论文培育项目（2017bxlp003）
作者简介：
甄荣（1990—），男，内蒙古乌兰察布人，博士生，研究方向为海上智能交通，（E-mail）zrandsea@163.com;
RIVEIRO Maria （1978—），女，瑞典人，副教授，博导，研究方向为可视化分析及其在海上交通监控中的应用，（E-mail）maria.riveiro@his.se;
金永兴（1958—），男，上海人，教授，博导，研究方向为船舶运行品质评估，（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覆盖的港口或沿海水域，船舶数量多，通航密度大，船舶航行环境复杂。对此类水域内船舶航行风险进行准确、有效识别是VTS中心值班人员面临的难题。船舶会遇分析是研究海上交通状况的一种重要手段[1]，国内外学者对此进行了很多研究。潘家财等[2]设计了船舶会遇的时空数据挖掘算法，根据历史AIS数据，对水域内船舶会遇空间、会遇时间和会遇船舶类等进行了分析。任亚磊[3]根据船舶领域模型，对船舶会遇从总体会遇情况、会遇船舶参数、会遇船舶时空分布、会遇态势等4个方面进行了定量分析。肖潇等[4]对单船在航行过程中的会遇信息，如会遇空间、会遇数量、会遇态势和最近会遇距离（distance to closest point of approach， DCPA）进行了计算，并将计算结果在电子海图上进行了可视化展示。RONG等[5]结合人工势场法和船舶领域模型对历史船舶会遇样本进行了提取和模拟研究。ZHANG等[6-7]基于船舶领域和最小碰撞距离从历史AIS数据中提取船舶会遇样本，对会遇样本进行了危险度排序。
现有研究从不同角度对船舶会遇进行了定义，并设计了相应的算法，侧重于从历史AIS数据中提取船舶会遇数量、会遇时间、会遇空间、会遇态势、DCPA等特征，研究结果可为海上通航环境危险度时空分布研究、海上交通规划和航行规则制定提供依据。本文从沿海港口水域船舶航行风险的实时识别出发，提出一种基于DBSCAN（density-based spatial clustering of applications with noise）的船舶会遇实时识别方法。通过DBSCAN算法，设定不同的会遇距离，快速实时地实现会遇船舶和非会遇船舶的识别和提取，缩小船舶会遇样本的选取范围。
1 船舶会遇的定义
船舶会遇通常表现为船舶在海上航行过程中从不同的方向会聚而发生的相遇情况[8]。根据研究目的和要求的不同，船舶会遇标准和定义并不统一，通常可以总结为以下两种情况：
（1）宏观海上通航环境危险度评估。由于船舶会遇是船舶发生碰撞事故的必要条件，而某一海域在一段时间内发生交通事故的数量是有限的，所以通常采用船舶的会遇情况来宏观地评估这一海域的通航环境危险度。根据宏观海上通航环境危险度评估的要求，船舶会遇标准通常是航行船舶间的距离在一定范围内构成会遇局面，无须考虑是否构成碰撞危险或紧迫局面。在开阔水域或者沿海水域，会遇距离可取较大值，而在港口受限水域会遇距离应适当取较小值。
（2）微观碰撞危险度评估。在船舶自动避碰领域，船舶会遇标准是两船相遇后为避免碰撞危险而需要采取避碰行动的局面[3]。根据两船的会遇态势和碰撞危险度的大小，进行相应的避碰决策和复航时机决策[5，9]。
本文考虑在VTS覆盖水域船舶宏观碰撞危险实时识别的要求，即对于任一在此類水域航行的船舶，如果在其周围一定的距离范围内存在他船，则与之组成会遇船舶类，否则他船被视为非会遇船舶。因而，会遇船舶的识别可视为基于船舶在航行水域内密度的聚类问题。DBSCAN算法是一种带噪声的基于密度的空间聚类方法，能够将具有高密度的区域划分为簇，并在具有噪声的数据中发现任意形状的簇[10]，在城市交通拥堵识别[11，12]、餐饮集群识别[13]、航空网络优化[14]、铁路运输异物检测[15]等方面有着较好的应用。本文用DBSCAN算法对海上航行船舶进行实时聚类处理，从而提取会遇船舶类。
2 船舶会遇的密度聚类识别方法
2.1 DBSCAN算法
聚类是数据挖掘中的一个重要方法，它根据数据之间的相似性或距离，无监督地将数据划分为不同的类别，保证类内数据之间的距离尽可能小，类间数据之间的距离尽可能大。根据DBSCAN算法的相关概念，DBSCAN算法的流程[10，16]如下：
输入：一个包含n个对象的数据集D，领域半径ε，领域密度阈值M。
输出：具有类别标签的数据集。
（1）随机选择一个unvisited对象p，
标记p为visited，
若p的ε-领域内至少有M个对象，
则创建一个新簇C， 并把p加入到C。
令N为p的ε-领域中的对象集合。
（2）对于N中的每一个p′：若p′是unvisited，则标记p′为visited;若p′的ε-领域内至少有M个对象，则把这些对象添加到N;若p′还不是任何簇的成员，则把p′加入到C。
（3）重复步骤（2），直到没有标记为unvisited的对象。
（4）输出C，
否则标记p为噪声。
（5）重复步骤（1）～（4），直到没有标记为unvisited的对象。
2.2 船舶会遇识别
2.2.1 船舶间距离的计算
在运用DBSCAN算法识别船舶会遇的过程中，需要根据船舶间的距离确定簇以及会遇船舶类。本文以AIS信息中航行船舶实时经纬度作为聚类数据对象，但考虑到由地球这个不规则椭圆体造成的在墨卡托海图上存在纬度渐长现象，即纬度1′长度随着纬度升高而逐渐增长，从而使纬度间隔相等的纬线之间的距离不相等，为保证跨越纬度差较大海域的船舶之间距离的一致，船舶间距离的计算采用墨卡托算法。
假设有两艘船VO和VT， 在AIS动态信息中包含VO和VT的实时经度（λ）、纬度（φ）、对地速度和对地航向，两艘船之间距离的计算过程如下：
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φ分别为经度差和纬度差;MP为纬度渐长率;DMP为不同纬度间的纬度渐长率差;B为方位角;D为两船间的距离，n mile;e为地球椭圆体的偏心率;指数e/2中的e是自然对数的底。
2.2.2 船舶会遇识别参数确定
在运用DBSCAN算法识别船舶会遇的过程中，需要确定领域半径ε和领域密度阈值M。ε对应船舶间的会遇距离。由于只要任意两个船舶间距离小于等于ε即构成会遇，所以M的值为2。
关于船舶会遇距离的设定，潘家财等[2]设定的厦门湾的会遇距离是300 m （约0.16 n mile），会遇距离较小，这主要是考虑到厦门湾属于狭窄的受限水域。肖潇等[4]在开阔的台湾海峡设定的会遇距离为3.8 n mile。谭志荣等[17]在基于Near Miss局面的成山头水域交通冲突研究中采用DCPA 500 m作为空间阈值。通过对比发现，在已有研究中船舶会遇距离的设定并没有统一的标准，通常在船舶交通密集的水域，会遇距离取较小值，在开阔水域，会遇距离取较大值。
3 舟山群岛西南海域船舶会遇识别
浙江舟山群岛西南海域包括螺头航道、金塘航道、虾峙门航道、双峙门航道、册子水道等，它们是船舶进出宁波舟山港区的主要航道。随着宁波舟山港吞吐量的增加，该海域船舶交通密集态势复杂，再加上海域内岛屿众多，因此对该海域内船舶航行风险进行监控一直是相关海事局VTS中心的工作重点。本文选取“船队在线”网站提供的浙江舟山群岛西南海域2016年12月1日9：00的船舶AIS信息工作为试验数据，原始船舶AIS信息见图1，收到的AIS信息来自56艘在航船舶。
图1 舟山群岛西南海域船舶AIS信息
3.1 不同会遇距离的船舶会遇识别
根据海上交通工程中水域特點划分方法，图1所示的舟山群岛西南海域靠近大陆且被岛屿围绕，故可被归类为受限水域[1]，会遇距离可取较小值。当运用DBSCAN算法对会遇船舶样本进行实时识别和提取时，如果会遇距离过大则会造成将所有船舶识别为一个会遇船舶类，如果会遇距离过小则可能无法形成会遇船舶类。根据VTS中心的值班人员和在该海域有航行经验的船舶驾驶员的建议，确定船舶会遇距离的范围为1～3 n mile。当会遇距离小于1 n mile时，所有船舶都是非会遇船舶，失去了监控的意义。
设定会遇距离分别为3 n mile， 2 n mile和1 n mile，得到的船舶会遇识别结果分别见图2～4，图中会遇类船舶用点号表示，非会遇类船舶用三角号表示。
图2 会遇距离为 3 n mile时的船舶会遇识别
图3 会遇距离为 2 n mile时的船舶会遇识别
图4 会遇距离为 1 n mile时的船舶会遇识别
从图2可以看出，当会遇距离为3 n mile时，该海域有3个会遇船舶类。第1个会遇船舶类包含4艘船，第2个会遇船舶类包括37艘船，第3个会遇船舶类包含5艘船。其余10艘船在其各自的3 n mile范围内没有其他船出现，为非会遇船舶。可见在该水域，设置3 n mile的会遇距离导致会遇船舶类较少，每类包含的船舶数量较多，不能有效地得到具体的船舶会遇及航行风险信息。
从图3可以看出，当会遇距离为2 n mile时，该海域有10个会遇船舶类。每个会遇船舶类包含的船舶数量见表1。由表1可知，第2个会遇船舶类包含10艘船，第4个会遇船舶类包含7艘船，第7个会遇船舶类包含6艘船，其他各会遇船舶类包含2～3艘船。与会遇距离为3 n mile时的识别结果相比，会遇船舶类较多，会遇识别较明确。然而，第2，4，7个会遇船舶类包含较多的船，这些船之间的航行风险识别还是较为模糊的。
从图4可以看出，当会遇距离为1 n mile时，该海域有7个会遇船舶类，每个会遇船舶类包含2～3艘船（见表2），因而在监控时可以清晰地看到具体的、有潜在碰撞风险的船舶对，识别效果明确。
表1 会遇距离为2 n mile时每个会遇船舶类
包含的船舶数量
表2 会遇距离为1 n mile时每个会遇船舶类
包含的船舶数量
3.2 结果比较分析
将3个不同会遇距离下得到的会遇船舶类数量、会遇船舶数量和非会遇船舶数量进行比较分析，统计结果见表3。
表3 不同会遇距离下的统计结果
从表3可知，随着会遇距离从3 n mile减少到1 n mile，产生的会遇船舶类数量先增大后减少，会遇船舶数量所占比例减小（从82.1%减小到32.1%），相应的非会遇船舶数量所占比例增加（从17.9%增加到67.9%）。因此，通过DBSCAN算法，可将海域内航行的船舶实时划分为多个相互间距离小于等于会遇距离的船舶类，过滤掉非会遇船舶，将少量的会遇船舶类标识出来，提供给VTS中心值班人员，提高海上交通监控的效率。
4 结 论
提出一种用于海上交通监控的基于密度聚类的船舶会遇实时识别方法。以航行船舶发射的AIS信息为数据来源，运用DBSCAN算法对船舶会遇进行聚类识别。根据海域情况设定合适的船舶会遇距离，得到相应的会遇识别结果。以浙江舟山群岛西南海域为例，分别设定3 n mile，2 n mile和1 n mile为会遇距离进行试验，结果表明当会遇距离为1 n mile时可以过滤掉大部分非会遇船舶，得到7个会遇船舶类，对实际水域内高风险船舶的监控适用性较好。
实际上，在沿海港口水域还有未装设AIS的小型船舶，以及部分装设了AIS但没有开启的船舶，这对船舶会遇实时识别的可靠性存在影响。在此情况下，VTS中心可以考虑采用雷达信号作为数据源，用以保证船舶会遇实时识别的有效性。在实际应用中，可以根据海域特点、船舶驾驶员航行习惯以及海事部门监控要求选取合适的会遇距离。本文初步实现了设定会遇距离下的船舶会遇识别，在后续研究中将考虑在航船舶的静态、动态特性对船舶会遇距离的影响，针对不同的船舶设定不同的船舶会遇距离进行更加精确的船舶会遇识别。
参考文献：
[1]吴兆麟， 朱军. 海上交通工程[M]. 2版. 大连： 大连海事大学出版社， 2004： 135-136.
[2]潘家财， 姜青山， 邵哲平. 船舶会遇的时空数据挖掘算法及应用[J]. 中国航海， 2010， 33（4）： 57-60.
[3]任亚磊. 基于数据的船舶会遇特征研究[D]. 武汉： 武汉理工大学， 2013.
[4]肖潇， 赵强， 邵哲平， 等.基于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]. 哈尔滨工程大学学报， 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]鲁小丫， 宋志豪， 徐柱， 等.利用实时路况数据聚类方法检测城市交通拥堵点[J].地球信息科学学报， 2012， 14（6）： 775-780.
[12]刘畅， 李治军， 姜守旭. 基于DBSCAN 算法的城市交通拥堵区域发现[J]. 智能计算机与应用， 2015（3）： 69-71.
[13]杨帆， 徐建刚， 周亮. 基于DBSCAN 空间聚类的广州市区餐饮集群识别及空间特征分析[J]. 经济地理， 2016， 36（10）： 110-116.
[14]王世锦， 曹希， 郦晴云， 等. 航路网络生成及优化[J]. 航空计算技术， 2016， 46（4）： 4-8.
[15]郭保青， 朱力强， 史红梅. 基于快速DBSCAN 聚类的铁路异物侵限检测算法[J]. 仪器仪表学报， 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的成山头水域交通冲突风险可视化[J]. 中国航海， 2016， 39（4）： 43-46， 107.
摘要：
針对海上交通监控中船舶数量众多，且对具有潜在碰撞危险的船舶识别效率不高的问题，提出一种基于DBSCAN（带噪声的基于密度的空间聚类）的船舶会遇实时识别方法。根据海上交通风险监控的研究需求，分析船舶会遇局面的定义。运用墨卡托算法计算船舶之间的距离，采用DBSCAN算法进行船舶会遇聚类识别。基于浙江舟山群岛西南海域航行船舶的AIS数据，对设置不同船舶会遇距离的试验结果进行比较分析，结果表明：当船舶会遇距离为1 n mile时，可以将56艘船划分为7个会遇船舶类，占船舶总数的32.1%，每个会遇船舶类包括2～3艘船。将该方法运用到实际海上交通监控中，可对每个会遇船舶类中的船舶航行动态进行重点关注，降低海上交通监控人员的工作负担，提高海上交通监控的效率。
关键词：
海上交通监控; DBSCAN; 船舶会遇; 航行风险
中图分类号： U698.8
文献标志码： A
收稿日期： 2017-05-09
修回日期： 2017-07-27
基金项目： 国家自然科学基金（51709165）;国家留学基金管理委员会联合培养博士生项目（201608310093）;上海市科学技术委员会地方院校能力建设项目（15590501600）;上海海事大学研究生创新基金（2016ycx077）;上海海事大学优秀博士学位论文培育项目（2017bxlp003）
作者简介：
甄荣（1990—），男，内蒙古乌兰察布人，博士生，研究方向为海上智能交通，（E-mail）zrandsea@163.com;
RIVEIRO Maria （1978—），女，瑞典人，副教授，博导，研究方向为可视化分析及其在海上交通监控中的应用，（E-mail）maria.riveiro@his.se;
金永兴（1958—），男，上海人，教授，博导，研究方向为船舶运行品质评估，（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覆盖的港口或沿海水域，船舶数量多，通航密度大，船舶航行环境复杂。对此类水域内船舶航行风险进行准确、有效识别是VTS中心值班人员面临的难题。船舶会遇分析是研究海上交通状况的一种重要手段[1]，国内外学者对此进行了很多研究。潘家财等[2]设计了船舶会遇的时空数据挖掘算法，根据历史AIS数据，对水域内船舶会遇空间、会遇时间和会遇船舶类等进行了分析。任亚磊[3]根据船舶领域模型，对船舶会遇从总体会遇情况、会遇船舶参数、会遇船舶时空分布、会遇态势等4个方面进行了定量分析。肖潇等[4]对单船在航行过程中的会遇信息，如会遇空间、会遇数量、会遇态势和最近会遇距离（distance to closest point of approach， DCPA）进行了计算，并将计算结果在电子海图上进行了可视化展示。RONG等[5]结合人工势场法和船舶领域模型对历史船舶会遇样本进行了提取和模拟研究。ZHANG等[6-7]基于船舶领域和最小碰撞距离从历史AIS数据中提取船舶会遇样本，对会遇样本进行了危险度排序。
现有研究从不同角度对船舶会遇进行了定义，并设计了相应的算法，侧重于从历史AIS数据中提取船舶会遇数量、会遇时间、会遇空间、会遇态势、DCPA等特征，研究结果可为海上通航环境危险度时空分布研究、海上交通规划和航行规则制定提供依据。本文从沿海港口水域船舶航行风险的实时识别出发，提出一种基于DBSCAN（density-based spatial clustering of applications with noise）的船舶会遇实时识别方法。通过DBSCAN算法，设定不同的会遇距离，快速实时地实现会遇船舶和非会遇船舶的识别和提取，缩小船舶会遇样本的选取范围。
1 船舶会遇的定义
船舶会遇通常表现为船舶在海上航行过程中从不同的方向会聚而发生的相遇情况[8]。根据研究目的和要求的不同，船舶会遇标准和定义并不统一，通常可以总结为以下两种情况：
（1）宏观海上通航环境危险度评估。由于船舶会遇是船舶发生碰撞事故的必要条件，而某一海域在一段时间内发生交通事故的数量是有限的，所以通常采用船舶的会遇情况来宏观地评估这一海域的通航环境危险度。根据宏观海上通航环境危险度评估的要求，船舶会遇标准通常是航行船舶间的距离在一定范围内构成会遇局面，无须考虑是否构成碰撞危险或紧迫局面。在开阔水域或者沿海水域，会遇距离可取较大值，而在港口受限水域会遇距离应适当取较小值。
（2）微观碰撞危险度评估。在船舶自动避碰领域，船舶会遇标准是两船相遇后为避免碰撞危险而需要采取避碰行动的局面[3]。根据两船的会遇态势和碰撞危险度的大小，进行相应的避碰决策和复航时机决策[5，9]。
本文考虑在VTS覆盖水域船舶宏观碰撞危险实时识别的要求，即对于任一在此類水域航行的船舶，如果在其周围一定的距离范围内存在他船，则与之组成会遇船舶类，否则他船被视为非会遇船舶。因而，会遇船舶的识别可视为基于船舶在航行水域内密度的聚类问题。DBSCAN算法是一种带噪声的基于密度的空间聚类方法，能够将具有高密度的区域划分为簇，并在具有噪声的数据中发现任意形状的簇[10]，在城市交通拥堵识别[11，12]、餐饮集群识别[13]、航空网络优化[14]、铁路运输异物检测[15]等方面有着较好的应用。本文用DBSCAN算法对海上航行船舶进行实时聚类处理，从而提取会遇船舶类。
2 船舶会遇的密度聚类识别方法
2.1 DBSCAN算法
聚类是数据挖掘中的一个重要方法，它根据数据之间的相似性或距离，无监督地将数据划分为不同的类别，保证类内数据之间的距离尽可能小，类间数据之间的距离尽可能大。根据DBSCAN算法的相关概念，DBSCAN算法的流程[10，16]如下：
输入：一个包含n个对象的数据集D，领域半径ε，领域密度阈值M。
输出：具有类别标签的数据集。
（1）随机选择一个unvisited对象p，
标记p为visited，
若p的ε-领域内至少有M个对象，
则创建一个新簇C， 并把p加入到C。
令N为p的ε-领域中的对象集合。
（2）对于N中的每一个p′：若p′是unvisited，则标记p′为visited;若p′的ε-领域内至少有M个对象，则把这些对象添加到N;若p′还不是任何簇的成员，则把p′加入到C。
（3）重复步骤（2），直到没有标记为unvisited的对象。
（4）输出C，
否则标记p为噪声。
（5）重复步骤（1）～（4），直到没有标记为unvisited的对象。
2.2 船舶会遇识别
2.2.1 船舶间距离的计算
在运用DBSCAN算法识别船舶会遇的过程中，需要根据船舶间的距离确定簇以及会遇船舶类。本文以AIS信息中航行船舶实时经纬度作为聚类数据对象，但考虑到由地球这个不规则椭圆体造成的在墨卡托海图上存在纬度渐长现象，即纬度1′长度随着纬度升高而逐渐增长，从而使纬度间隔相等的纬线之间的距离不相等，为保证跨越纬度差较大海域的船舶之间距离的一致，船舶间距离的计算采用墨卡托算法。
假设有两艘船VO和VT， 在AIS动态信息中包含VO和VT的实时经度（λ）、纬度（φ）、对地速度和对地航向，两艘船之间距离的计算过程如下：
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φ分别为经度差和纬度差;MP为纬度渐长率;DMP为不同纬度间的纬度渐长率差;B为方位角;D为两船间的距离，n mile;e为地球椭圆体的偏心率;指数e/2中的e是自然对数的底。
2.2.2 船舶会遇识别参数确定
在运用DBSCAN算法识别船舶会遇的过程中，需要确定领域半径ε和领域密度阈值M。ε对应船舶间的会遇距离。由于只要任意两个船舶间距离小于等于ε即构成会遇，所以M的值为2。
关于船舶会遇距离的设定，潘家财等[2]设定的厦门湾的会遇距离是300 m （约0.16 n mile），会遇距离较小，这主要是考虑到厦门湾属于狭窄的受限水域。肖潇等[4]在开阔的台湾海峡设定的会遇距离为3.8 n mile。谭志荣等[17]在基于Near Miss局面的成山头水域交通冲突研究中采用DCPA 500 m作为空间阈值。通过对比发现，在已有研究中船舶会遇距离的设定并没有统一的标准，通常在船舶交通密集的水域，会遇距离取较小值，在开阔水域，会遇距离取较大值。
3 舟山群岛西南海域船舶会遇识别
浙江舟山群岛西南海域包括螺头航道、金塘航道、虾峙门航道、双峙门航道、册子水道等，它们是船舶进出宁波舟山港区的主要航道。随着宁波舟山港吞吐量的增加，该海域船舶交通密集态势复杂，再加上海域内岛屿众多，因此对该海域内船舶航行风险进行监控一直是相关海事局VTS中心的工作重点。本文选取“船队在线”网站提供的浙江舟山群岛西南海域2016年12月1日9：00的船舶AIS信息工作为试验数据，原始船舶AIS信息见图1，收到的AIS信息来自56艘在航船舶。
图1 舟山群岛西南海域船舶AIS信息
3.1 不同会遇距离的船舶会遇识别
根据海上交通工程中水域特點划分方法，图1所示的舟山群岛西南海域靠近大陆且被岛屿围绕，故可被归类为受限水域[1]，会遇距离可取较小值。当运用DBSCAN算法对会遇船舶样本进行实时识别和提取时，如果会遇距离过大则会造成将所有船舶识别为一个会遇船舶类，如果会遇距离过小则可能无法形成会遇船舶类。根据VTS中心的值班人员和在该海域有航行经验的船舶驾驶员的建议，确定船舶会遇距离的范围为1～3 n mile。当会遇距离小于1 n mile时，所有船舶都是非会遇船舶，失去了监控的意义。
设定会遇距离分别为3 n mile， 2 n mile和1 n mile，得到的船舶会遇识别结果分别见图2～4，图中会遇类船舶用点号表示，非会遇类船舶用三角号表示。
图2 会遇距离为 3 n mile时的船舶会遇识别
图3 会遇距离为 2 n mile时的船舶会遇识别
图4 会遇距离为 1 n mile时的船舶会遇识别
从图2可以看出，当会遇距离为3 n mile时，该海域有3个会遇船舶类。第1个会遇船舶类包含4艘船，第2个会遇船舶类包括37艘船，第3个会遇船舶类包含5艘船。其余10艘船在其各自的3 n mile范围内没有其他船出现，为非会遇船舶。可见在该水域，设置3 n mile的会遇距离导致会遇船舶类较少，每类包含的船舶数量较多，不能有效地得到具体的船舶会遇及航行风险信息。
从图3可以看出，当会遇距离为2 n mile时，该海域有10个会遇船舶类。每个会遇船舶类包含的船舶数量见表1。由表1可知，第2个会遇船舶类包含10艘船，第4个会遇船舶类包含7艘船，第7个会遇船舶类包含6艘船，其他各会遇船舶类包含2～3艘船。与会遇距离为3 n mile时的识别结果相比，会遇船舶类较多，会遇识别较明确。然而，第2，4，7个会遇船舶类包含较多的船，这些船之间的航行风险识别还是较为模糊的。
从图4可以看出，当会遇距离为1 n mile时，该海域有7个会遇船舶类，每个会遇船舶类包含2～3艘船（见表2），因而在监控时可以清晰地看到具体的、有潜在碰撞风险的船舶对，识别效果明确。
表1 会遇距离为2 n mile时每个会遇船舶类
包含的船舶数量
表2 会遇距离为1 n mile时每个会遇船舶类
包含的船舶数量
3.2 结果比较分析
将3个不同会遇距离下得到的会遇船舶类数量、会遇船舶数量和非会遇船舶数量进行比较分析，统计结果见表3。
表3 不同会遇距离下的统计结果
从表3可知，随着会遇距离从3 n mile减少到1 n mile，产生的会遇船舶类数量先增大后减少，会遇船舶数量所占比例减小（从82.1%减小到32.1%），相应的非会遇船舶数量所占比例增加（从17.9%增加到67.9%）。因此，通过DBSCAN算法，可将海域内航行的船舶实时划分为多个相互间距离小于等于会遇距离的船舶类，过滤掉非会遇船舶，将少量的会遇船舶类标识出来，提供给VTS中心值班人员，提高海上交通监控的效率。
4 结 论
提出一种用于海上交通监控的基于密度聚类的船舶会遇实时识别方法。以航行船舶发射的AIS信息为数据来源，运用DBSCAN算法对船舶会遇进行聚类识别。根据海域情况设定合适的船舶会遇距离，得到相应的会遇识别结果。以浙江舟山群岛西南海域为例，分别设定3 n mile，2 n mile和1 n mile为会遇距离进行试验，结果表明当会遇距离为1 n mile时可以过滤掉大部分非会遇船舶，得到7个会遇船舶类，对实际水域内高风险船舶的监控适用性较好。
实际上，在沿海港口水域还有未装设AIS的小型船舶，以及部分装设了AIS但没有开启的船舶，这对船舶会遇实时识别的可靠性存在影响。在此情况下，VTS中心可以考虑采用雷达信号作为数据源，用以保证船舶会遇实时识别的有效性。在实际应用中，可以根据海域特点、船舶驾驶员航行习惯以及海事部门监控要求选取合适的会遇距离。本文初步实现了设定会遇距离下的船舶会遇识别，在后续研究中将考虑在航船舶的静态、动态特性对船舶会遇距离的影响，针对不同的船舶设定不同的船舶会遇距离进行更加精确的船舶会遇识别。
参考文献：
[1]吴兆麟， 朱军. 海上交通工程[M]. 2版. 大连： 大连海事大学出版社， 2004： 135-136.
[2]潘家财， 姜青山， 邵哲平. 船舶会遇的时空数据挖掘算法及应用[J]. 中国航海， 2010， 33（4）： 57-60.
[3]任亚磊. 基于数据的船舶会遇特征研究[D]. 武汉： 武汉理工大学， 2013.
[4]肖潇， 赵强， 邵哲平， 等.基于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]. 哈尔滨工程大学学报， 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]鲁小丫， 宋志豪， 徐柱， 等.利用实时路况数据聚类方法检测城市交通拥堵点[J].地球信息科学学报， 2012， 14（6）： 775-780.
[12]刘畅， 李治军， 姜守旭. 基于DBSCAN 算法的城市交通拥堵区域发现[J]. 智能计算机与应用， 2015（3）： 69-71.
[13]杨帆， 徐建刚， 周亮. 基于DBSCAN 空间聚类的广州市区餐饮集群识别及空间特征分析[J]. 经济地理， 2016， 36（10）： 110-116.
[14]王世锦， 曹希， 郦晴云， 等. 航路网络生成及优化[J]. 航空计算技术， 2016， 46（4）： 4-8.
[15]郭保青， 朱力强， 史红梅. 基于快速DBSCAN 聚类的铁路异物侵限检测算法[J]. 仪器仪表学报， 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的成山头水域交通冲突风险可视化[J]. 中国航海， 2016， 39（4）： 43-46， 107.
