一种基于改进的DBSCAN的面向海量船舶位置数据码头挖掘算法＊

丁兆颖，姚 迪，吴 琳，毕经平，赵瑞莲

（1.北京化工大学信息学院，北京100029；2.中国科学院计算技术研究所，北京100190）

1 引言

船舶目标跟踪方法有很多种，比如国际海事卫星C系统、北斗卫星、Argos卫星、AIS（Automatic Identification System）等。不同方法各有优劣，比如国际海事卫星C 系统是全天候、全球范围、稳定可靠的，但是终端价格和通信费稍高；北斗卫星技术速度快，但目前只是区域性，且终端尚不够稳定；AIS方法成本低廉，无需通信费，可以分布式建设。随着《SOLAS公约》第五章新规则对船舶自动识别系统（AIS）［1］强制性装备的要求，所有300总吨及以上从事国际航行船舶、不从事国际航行的500总吨及以上的货船和不论大小的客船，应按要求配备自动识别系统AIS。AIS在全球范围内广泛使用。各类岸基AIS设备以及卫星AIS设备每天接收到的船只动态、静态AIS实时报文数量数以亿计，为船舶轨迹研究提供了丰富的数据源。这些丰富的海量船舶数据中，隐藏着大量对水运事业管理、规划、安全等具有非常重大的意义的内容。

在水运行业中，港口作为运输枢纽，是各类交通工具转换中心。码头、锚地的作用是供船舶进出、停泊，是港口水域的重要组成部分。各类码头对城市经济的发展、区域经济的发展都起着非常重要的作用。近年来新建码头层出不穷，而中国海图的更新间隔按照区域的热度更新间隔长达3个月、6个月、12个月不等的时间，存在严重的滞后性，并且海图中缺乏码头的空间信息。本文提出的码头挖掘的研究工作可以有效、及时地更新码头空间数据。码头的空间信息可以进一步应用到船舶进出港通知，不仅如此，码头的挖掘成果，也可以作为船舶数据其他研究领域的数据支撑，比如码头间航道挖掘、船舶行为异常监测等。

DBSCAN（Density－Based Spatial Clustering of Applications with Noise）算法是一种具有噪声的基于密度的聚类分析算法，它可以将数据集分成若干组，并有效地处理噪声点，过滤低密度区域。其基本思想是在含有噪声的数据空间中，通过不断扩展有足够高密度的区域来进行聚类，发现任意形状的高密度多簇点集。但是，由于应用DBSCAN算法时有eps和MinPts两个参数需要人工提前确定，且算法对这两个参数非常敏感，这一缺点普遍存在于实际的计算当中。

本文提出一种针对海量数据优化参数的DBSCAN 算法，可以根据不同的实际应用场景、数据集特征，选取合适的算法参数。将其应用在码头挖掘场景中，根据实际的停泊点数据规模和分布特征，自动优化停泊点聚类参数，聚类出停泊点密集的停泊区，去除停泊点稀疏区域的停泊点。再通过融合岸基结构物等空间数据，对停泊区域中的锚区和临时停泊区域等进行排除，获取码头的空间信息，解决了码头空间数据实时更新问题。

本文第2节介绍了位置数据和DBSCAN 算法的相关研究工作；第3 节介绍自动优化DBSCAN算法参数的方法，及将改进的DBSCAN 算法应用于码头挖掘思路；第4节实验及结果分析；第5节总结全文并展望下一步研究工作。

2 相关工作

聚类在数据挖掘领域的研究比较多。聚类算法主要分为四种策略：（1）划分聚类方法，如kmeans［2］，需指定聚类个数，不适用于发掘未知信息；（2）分层聚类方法，如BIRCH［3］，计算量大，算法复杂度高，耗时较长，不适合应用于海量数据；（3）基于密度的聚类方法，如DBSCAN［4］和OPTICS［5］，复杂度低，基于数据密度分布特征，对数据集聚类，比较适合本文所提的码头挖掘研究；（4）基于栅格的聚类方法，如STING［6］，处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性。

目前，DBSCAN 聚类算法应用在实际场景中的研究国内外已有很多，比如交通事故多发区域的挖掘等。通过不断地搜索临近点来使核心对象周围的密度逐渐增加，寻找到一个区域内所查找点或对象密度大的地方。算法中所要研究的点可以描述为交通事故多发的地点。由于应用DBSCAN 算法时有eps和MinPts两个参数需要人工提前确定，且算法对参数敏感，研究者在原始算法的基础上提出了很多改进，来提高算法的效率。Han J等［7］通过计算数据集的信息熵，给出一个最优参数的范围。Karami A 等［8］提出了一种高效的混合聚类方法，命名为bde－dbscan，结合了二进制差分进化算法和DBSCAN 算法。这些方法都能很好地解决DBSCAN 算法的参数敏感问题，但是复杂度较高，且需要人工观察，不适用在大数据量级的数据处理中。

目前国内外很少有对船舶停泊点的分析研究，特别是基于停泊点的码头挖掘研究。Le Guillarme N 等［9］提出了一个船舶位置数据挖掘框架，从数据中提取航道和停泊点，对停泊点进行聚类，聚类出密集区域定义为港口、捕鱼点等船只的目的地，没有进一步地划分，也没有解决聚类算法对参数敏感的问题。

3 码头挖掘算法

3.1 码头挖掘算法思路

船舶位置数据，即船舶某个时间点所在位置的经纬度。停泊点数据即是船舶在某个点附近停留时间超过一定阈值的点。面向海量船舶位置数据的码头挖掘算法主要分为两步。第一步是从船舶位置原始数据中提取出停泊点数据。一般船舶停泊的地方主要集中在码头、锚区或临时停泊区，在这些区域船舶停泊点密度较大。除此之外还有很多分散停泊在这些区域外的船只，对于停泊区挖掘来说，这些数据属于噪声数据。第二步针对使用数据集，确定适应停泊点数据聚类的参数。DBSCAN 算法是基于密度聚类的聚类算法，可以有效去掉停泊点噪声数据，将船舶位置数据分成多组任意形状的停泊区。然而，针对不同的数据，聚类算法的参数也不尽相同。本文提出一种优化DBSCAN 算法参数的方法，自动对比聚类后类中心密度变化，自动选取合适的参数，以提高停泊区挖掘的准确度。确定聚类参数后，对停泊点数据进行聚类。单纯的聚类结果还不能确定码头，需要通过融合外部数据，如岸基结构物等，确定码头的位置和区域。码头挖掘流程如图1所示。

Figure 1 Flow chart of dock mining图1 码头挖掘流程图

本节的第2部分介绍海事船舶数据的预处理工作，从船舶自动识别系统采集的原始海事船舶数据，提取出本文需要的船舶停泊点数据。第3部分介绍DBSCAN 算法思想及优化参数的方法。第4部分介绍聚类方法结果和融合外部数据的方法。

3.2 停泊点提取

基于带有时间戳的船舶位置数据分析船舶海洋行为，需要对数据进行划分。其中基于分层数据融合的数据划分方法是最适用于处理海量数据的方法，且该算法的计算复杂度是O（n）。划分方法将数据划分为两层，AIS原始数据经过L1层处理得到子航段。子航段数据经过L2 层融合得到航段及停泊点［8］。原始数据处理流程如图2所示。

L1层处理：分析单艘船时间序列上的数据。时间连续的AIS数据首尾相连，构成一个向量，根据如下两个条件判断是否划分子航段：

其中，O为起始点，Pi表示AIS原始数据中第i个点，T1、T2为两个阈值，分别表示起始向量与第i个向量夹角阈值，第i个向量与第i－1 个向量夹角阈值。超过阈值时开始下一个子航段划分。

L2层处理：基于规则挖掘出单艘船的子航段。根据船舶行为特点确定停泊点，停泊点的定义是船舶子航段端点处停留时间超过一定阈值的点。

Figure 2 Flow chart of raw data processing图2 原始数据处理流程图

3.3 停泊点聚类算法

3.3.1 DBSCAN 算法

定义1eps邻域：给定半径eps（ε），以特定点为圆心，以eps为半径的圆内的点集称为该停泊点的邻域。

定义2 核心点：邻域内的停泊点数大于或等于MinPts，则该点成为核心停泊点。

定义3 直接密度可达：给定停泊点集合D，如果点p在q的邻域内，且q是核心停泊点，则称点p到q直接密度可达。

定义4 密度可达：给定停泊点集合D，如果存在停泊点子集p1，p2，p3，…，pn，pi（1≤i≤n）∈D，pi＋1是从pi关于ε和MinPts直接密度可达，则停泊点p是从q关于ε和MinPts密度可达。

定义5 密度相连：如果存在停泊点k∈D，使点p和q是关于ε和MinPts密度可达，那么p到q是关于ε和MinPts密度相连。

算法1 基于DBSCAN 算法的码头挖掘算法

输入：一组停泊点（经纬度）集合D＝｛p1，p2，p3，…，pn｝（n是停泊点集合的数量）、邻域半径ε和最小邻域点数MinPts；

输出：labels整数集合，标记每个点的类名。

functionDBSCAN（D，ε，MinPts）

clusterId＝0；

标记所有点为未分类点；

其中找出核心点的最大密度相连集合函数如下：

3.3.2 DBSCAN 参数优化

DBSCAN 算法依赖聚类最小点数MinPts，聚类内部最长距离eps两个参数。因此，对不同分布的数据需要调整不同的MinPts和eps，以达到好的聚类效果。本文采用聚类个数和类中心密度（Cluster Center Density）作为聚类效果的评价指标，分别确定MinPts及eps，不断迭代直到MinPts和eps稳定。

由于DBSCAN 是基于密度的聚类算法，因此该算法在一定程度上对参数不敏感。即由一个确定的MinPts可能有多个连续的eps与之对应，即一个eps的区间对应，因此寻找最优参数即寻找最优的MinPts区间与eps区间。区别于传统的优化问题，本问题找不到一个可以形式化表示的损失函数。参数优化算法如下：

算法2 DBSCAN 参数确定算法

输 入：数 据 集，MinPts初 始 值p0，eps初 始 值e0，MinPts变化率；

输出：最优参数区间p，e。

当eps值确定时，搜索不同MinPts值，计算不同MinPts产生的聚类个数。首先确定MinPts搜索间隔，记录MinPts对应的聚类个数。聚类个数的变化一定是递减的过程，选取聚类个数达到最大稳定时对应的MinPts值作为最佳MinPts值。实现方法为计算不同MinPts值对应的聚类个数计算横坐标为MinPts值，纵坐标为聚类个数确定的点中，每一个点与下一个点相连直线的斜率。

设第n次搜索得到的点为Pn（MinPtsn，Cn），其中MinPtsn为聚类最小点数，Cn为聚类个数。对每一步记录kPn－1Pn。搜索的终止条件为：

其中，

Δeps为搜索步长，是一个常数；m为稳定条件，即有m步斜率接近于零则判定为稳定，并记录MinPts的值。

3.4 融合岸基结构物筛选码头

根据上述算法，可以将停泊点数据聚成一个个停泊区域，对不同的停泊区域肯定需要参照其地理位置信息对其分类。本文通过融合岸基结构物数据，根据码头的形状位置特征从停泊区域中筛选出码头，并将筛选出的码头与已有码头分布的区域比对，验证算法挖掘出码头的准确性。

海岸线延伸出大陆架的部分称为陆地的岸基结构物，码头一定是贴近岸基结构物建造的。本文用到的岸基结构物由google KML文件标准定义，定义结构如图3所示。

Figure 3 Raw data of the shore structures图3 岸基结构物原始数据

可以看出，岸基结构物是通过一条条线定义的，通过计算聚类区域到线的距离即可判断停泊区域是否是一个码头。

设类核心点为P，首先提取以P为中心、以r为半径区域内的岸基结构物线段数据，设定码头距岸基阈值rt，如果r＜rt即判定该区域为码头区域，否则不是码头区域。

4 实验及分析

4.1 实验场景

本文实验基于2012年4月至2014年4月的滚装船位置数据，实现了改进的DBSCAN 算法和挖掘码头算法，挖掘出国内滚装船码头，通过对比人工识别码头判断算法准确率。同样用本文提出的算法，挖掘出国际滚装船码头。实验表明本文方法具有很高的准确性和很强的可扩展性。本实验使用的语言是Python 2.7版本，在普通的电脑上执行程序，具体实验环境参数和实验数据如表1和表2所示。

Table 1 Experimental environment表1 实验环境

Table 2 Experimental dataset表2 实验数据

表2是从AIS采集到大量船舶静态和动态数据，包括船位、航向、航速、类型等中提取出的滚装船位置数据。其中静态数据表示船舶的条数，国内54艘滚装船，国际有279艘。

4.2 DBSCAN 算法参数选取

码头挖掘算法第二步，首先要针对使用数据集，确定适应停泊点数据聚类的参数。按照本文参数优化方法，首先确定MinPts值。给出DBSCAN算法两个参数最小点数MinPts和聚类内部最长距离eps的初始值10和0.000 3，ΔMinPts为1，m取值为5，即有5步斜率接近于零则判定为稳定，并记录MinPts的值。分别计算特定eps值时，计算不同MinPts产生的聚类个数。如图4所示，横坐标是MinPts值，纵坐标代表聚类的个数。

本文算法的执行结果中，当eps＝0.000 3时，MinPts值取32，当eps＝0.000 6时，MinPts值取31，当eps＝0.000 8时，MinPts值取34，当eps＝0.001 0 时，MinPts值 取32。确 定MinPts值 为32。

确定MinPts值后，需要根据得到的MinPts值确定eps。在聚类核心点中随机选取25个点。计算并记录不同eps值时，每个点所在类中的类中心密度即最大密度相连集合内点总数。如图5所示。

Figure 4 The number of clusters based on different eps changing with MinPts value图4 不同eps聚类个数随MinPts值变化曲线图

当eps取0.000 68时，所有点类中心密度达到稳定，即确定eps值为0.000 68，从而最终确定eps值为0.000 68，MinPts值为32。如图5所示。

Figure 5 The class center density of core points varying with the eps value图5 核心点的类中心密度随eps值变化曲线图

4.3 国内滚装船码头挖掘实验

根据上一步实验，挖掘国内滚装船码头算法的两个参数eps和MinPts的值分别确定为0.000 68和32，挖掘国内滚装船码头。 本文利用googleMap展现国内滚装船码头的挖掘结果。挖掘出的码头位置用圆点表示，共挖掘出国内滚装船停泊区40个，筛选出码头29个。图6为使用本文提出的算法挖掘出的码头与真实码头的对比图，三角标志是人工标记的真实码头。

Figure 6 Result of dock mining for Chinese Ro Ro vessels图6 国内滚装船码头挖掘结果

图7是放大的上海外高桥码头区域，深色部分是岸基结构物，可以看到融合岸基结构物后可以清晰地区分出码头与非码头。从图7可以看出，码头都在岸基结构物附近，非码头区域离岸基较远。图中黑色圆点是已公布的滚装船码头位置。人工识别标记的滚装船码头有27个，本文算法挖掘出的码头有29个，正确率达93%。以此可见本文提出的算法能有效、准确地挖掘出码头的位置。此处挖掘出的非码头区域为上海码头附近的锚区。其作用是供船舶停靠等待装卸货物。此类停泊区域在本文中不做深入阐述。

Figure 7 Shanghai Waigaoqiao dock area combined with shore structures图7 上海外高桥码头区域结合岸基结构物

4.4 国际滚装船码头挖掘实验

本文利用国际滚装船位置数据进行测试，与国内滚装船数据同时间段的国际船舶位置数据有51 985条。利用本文挖掘码头算法，共挖掘出244个停泊区。如图8所示。

Figure 8 Dock mining result for international Ro Ro vessels图8 国际滚装船码头挖掘结果

对比地形结构发现，通过本文方法挖掘出的滚装船码头大部分与地形相符，表明本文提出的算法对不同的数据集有较好的可扩展性。

5 结束语

本文提出的优化参数的DBSCAN 算法，根据待聚类数据特征，自动优化确定DBSCAN 算法的两个参数，有效地解决了DBSCAN 算法对参数敏感问题。本文又提出一种基于船舶位置数据挖掘码头的算法，第一步先挖掘出停泊区域，再一步，融合岸基结构物数据，筛选出码头区域。本文选取2012年4月至2014年4 月国内滚装船位置数据进行实验，实验结果表明，本文算法能够针对特定数据集的分布特征及规模，自动确定DBSCAN 算法参数，并聚类出停泊区。再融合岸基结构物数据筛选出码头区域，对比本文挖掘出的码头位置和人工标注的码头位置数据，本文算法正确率达到93%。下一步工作，在完善码头挖掘工作的同时，分析非码头停泊区域的特点，融合多样化的数据，挖掘出更多有用的知识。

［1］ Wang Yong.AIS technology application in the navigation practice analysis［J］.Science Technology and Enterprise，2013（22）：158.（in Chinese）

［2］ Loyd S.Least squares quantization in PCM［J］.IEEE Transactions on Information Theory，1982，28（2）：129－137.

［3］ Zhang T，Ramakrishnan R，Livny M.BIRCH：An efficient data clustering method for very large databases［J］.ACM SIGMOD Record，1996，25（2）：103－114.

［4］ Dai B R，Lin I.Efficient map/reduce－based DBSCAN algorithm with optimized data partition［C］∥Proc of 2012IEEE 5th International Conference on Cloud Computing（CLOUD），2012：59－66.

［5］ Shi X，Chen Y，Tan Z，et al.Numerical simulation of adaptive optics correction system［C］∥Proc of 2011IEEE 3rd International Conference on Communication Software and Networks（ICCSN），2011：293－296.

［6］ Wang W，Yang J，Muntz R R.STING：A statistical information grid approach to spatial data mining［C］∥Proc of the 23rd International Conference on Very Large Data Bases，1997：186－195.

［7］ Lee J G，Han J，Whang K Y.Trajectory Clustering：A partition－and－group framework［C］∥Proc of SIGMOD，2007：593－604.

［8］ Karami A，Johansson R.Choosing DBSCAN parameters automatically using differential evolution［J］.International Journal of Computer Applications，2014，91（7）：1－11.

［9］ Le Guillarme N，Lerouvreur X.Unsupervised extraction of knowledge from S－AIS data for maritime situational awareness［C］∥International Conference on Information Fusion，2013：2025－2032.

附中文参考文献：

［1］ 王勇.AIS技术在航海实践中的应用分析［J］.科技与企业，2013（22）：158.