基于时空密度的船载AIS数据聚类分析方法研究

李永攀，刘正江，郑中义

(1. 大连海事大学 航海学院，辽宁 大连 116026；2. 舟山海事局 船舶交通管理中心，浙江 舟山 316000)

0 引 言

船舶自动识别系统(automatic identification system，AIS)是一种船载设备，向岸基及周边船舶发送自身的静态、动态和航次数据。AIS的强制配备和广泛应用，不仅提高了船舶航行安全和效率，且为开展相关数据挖掘、寻找海上交通规律、协助海上交通规划与管理提供了宝贵素材。

近年来船载AIS数据挖掘方法和应用迅速发展。学者们主要基于AIS数据点[1]或轨迹线[2]的经纬度、航向和航速等属性，利用一定数学模型和信息技术开展相关数据挖掘。通过挖掘AIS数据可识别海上锚泊区、作业区和拥挤区等特殊区域[1]、识别主要船舶航路[3]、分析船舶领域和运动模式[4]、研究船舶密度和速度分布[5]、评估船舶会遇或碰撞风险[6]、推算到港概率或航迹趋势[7]、开展异常检测、设计或审查定线制、评估碳排放等。

在海上交通特征方面：潘家财等分析AIS蕴含的航向、航速变化率，提出船舶会遇的时空数据挖掘算法[6-8]；唐存宝等研究了基于AIS的船舶航迹分布算法[9]；肖潇等提出基于AIS信息的船舶轨迹线聚类模型[2]；宁建强等提出一种基于海量船舶轨迹数据的细粒度网格海上交通密度计算方法[10]；刘涛等将船舶领域的概念引入DBSCAN(density-based spatial clustering of applications with noise)算法并开展水上交通拥挤区域的聚类分析与识别[11]；丁兆颖等提出一种基于改进DBSCAN的面向海量船舶位置数据码头挖掘算法[12]；魏照坤等引入AIS数据运动轨迹特征，利用DBSCAN算法开展船舶运动模式识别与应用[13]；G. PALLOTTA等基于船载AIS数据点提出无监督的航路辨识和异常检测模型[1]；LIU Bo等引入航向、航速的概念拓展DBSCAN算法，验证船舶是否遵守航路规定及查找异常情形[14]。

以上文献较少综合考虑时间和空间两方面对船载AIS数据进行时空聚类分析。然而船载AIS数据包含位置、时间和其他属性，属于典型时空数据，隐含着时空耦合特征和模式。笔者旨在开展AIS数据时空聚类分析、挖掘隐含的海上交通时空特征。

1 相关工作

时空数据是对现实世界中时空特征和过程的抽象概括。随着传感技术、计算机和大数据技术的发展，时空聚类成为海量时空数据分析的一个重要手段和前沿研究方向[15]。时空聚类是一个无需先验知识的非监督分类过程，依据一定相似性准则将时空实体划分成一系列子类，同一类内实体间的相似度尽可能大于不同类实体间的相似度[15]。

目前常见时空聚类分析算法大多从DBSCAN发展而来。DBSCAN算法不提前设置簇数量，在含有噪声的数据空间中，通过不断扩展有足够高密度的区域来进行聚类，可发现任意形状的高密度簇集，并有效地处理噪声点，过滤低密度区域[16]。该算法提出较早，聚类效果、时间复杂度和算法复杂度的综合评价较高，在空间位置分析领域得到了广泛的应用，已经成为很多学者进一步完善的主要方法[17]。G-DBSCAN(general-DBSCAN)算法除了空间属性外，还引入权重值考虑了其他非空间属性，认为DBSCAN只是一种特殊情况[18]。ST-DBSCAN(spatio-temporal-DBSCAN)算法在DBSCAN算法的基础上，引入时间维和非空间属性，通过指定空间半径、时间窗口与密度阈值，计算、识别出核心对象和噪声对象，从而构建任意形状的时空邻近簇[19]。4D+SNN(a spatio-temporal density-based clustering approach with 4D similarity)算法在共享近邻方法基础上，综合考虑空间(2D)、时间(1D)和语义属性(1D)，是DBSCAN算法的新发展[20]。

ST-DBSCAN和4D+SNN算法属于综合时间、空间维度和其他属性的时空聚类分析，笔者借鉴上述算法理念，考虑船载AIS数据报告特征并加以时间切片化处理，在DBSCAN算法基础上提出船载AIS数据时空聚类算法。

2 AIS数据约简

船载AIS设备分A、B两类，300 GT以上船舶安装A级AIS，航行时报告间隔2～12 s，锚泊时报告间隔3 min。其他小型船舶及渔船安装B级AIS，移动速度不超过2节时报告间隔3 min，锚泊时报告间隔6 min，其他均小于30 s[21]。

定义1基于AIS数据的船舶运动点集为三维时空域中的有限序列P={p1,p2,p3,,pn}。第i个船舶运动点pi=(time, mmsi, lon, lat)，经度lon、纬度lot和时间time构成三维时空域，属性mmsi为海上移动通信业务标识(maritime mobile service identity)，可推断该船为国际船舶、国内船舶或渔船[22]。

船载AIS设备连续发送数据报告，但报告间隔不同[21]。在相同时间内，不同船舶报告AIS数据对象的数量可能相差十几倍。指定时间内AIS数据点数与船舶数不成一定比例，使盲目指定时间距离开展时空聚类分析没有实际意义。为便于时空聚类分析，仅考虑速度大于2节的在航船载AIS数据点，并对其开展时间切片化约简，即每分钟只选取第一个报告点，去除该分钟内其他报告点。

定义2AIS数据时间切片化指对某船所有AIS数据点根据时间量度进行约简，即按时间先后排序，只保留每分钟内第一个报告点。

算法1AIS数据时间切片化

输入：某区域某时间段内的原始AIS数据集D1={p1,p2,p3,,pn}。

输出：该区域该时间段内每艘船舶每分钟有且仅有第一个报告点的新数据集D2。

步骤：

1)去除速度小于2节、属性值缺失和MMSI不合规范的点。

2)将D1中所有数据pi以mmsi为主要关键字、time为次要关键字排序。

3)将time的秒位设置成0。

4)去掉mmsi、time均相同的数据元素。

对于速度大于2节的在航船舶，不论装载A或B级AIS系统，报告间隔均小于30 s，其AIS数据经算法1处理后每分钟内有且仅有第一个AIS报告点。比如，某船舶以10节速度航行，时间属性值分别为12:31:02、12:31:13、12:31:21、12:31:32的4条连续报告AIS数据经算法1处理后，变为12:31(12:31:00，实际为12:31:02)时间点数据，即只取第1条(12:31:02)，后3条舍去，误差为2 s，10.3 m。根据AIS报告间隔规律和实际数据抽样查证，正常情况下某分钟内第一条数据都在其前30 s内，且大部分都在前20 s内。由于沿海船舶平均速度较低，约10节左右，30 s内仅航行百余米，故将某分钟的第一条数据看作整分时刻的数据所造成的误差在可接受范围之内。

3 AIS数据时空聚类算法

作为DBSACN在时空域的拓展，将密度、邻域、噪声等在时空域进行新的定义。

定义3任意一点的时空密度是以该点为圆心、邻域半径Eps为半径、2倍时间距离Δt为高的圆柱体内所包含的点的数量。如图1，p点的时空密度为7。

图1 船载AIS数据时空维度Fig. 1 Spatio-temporal dimension of shipborne AIS data

定义5若满足条件点q在点p的时空邻域内，且p是时空核心点，则称点p到点q时空直接密度可达。

定义6若有一组有序集Y={p1,p2,,pn}(其中，p1=p，pn=q)，对于任意的k(k

定义7若存在点o∈D使得点p和点q均从点o时空密度可达，则称点p和点q时空密度连接。

定义8若集合C是数据库D的一个非空子集，点p∈C时空密度到达的任一点q∈C，且任意p∈C、q∈C，p和q是时空密度连接的，那么称集合C是一个时空簇。

定义9时空核心点是在指定邻域半径Eps和时间距离Δt的时空邻域中含有大于最小邻域对象数MinPts的点。

定义10时空边界点是在时空域中自身不是时空核心点，但是与某一个或者几个时空核心点密度连接的点。

定义11时空噪声点是不属于任何时空簇的点。

在上述定义的基础上，基于船载AIS数据的时空密度聚类算法的步骤如下：

算法2船载AIS数据时空聚类算法

输入：数据点集D、MinPts、Eps和Δt。

输出：时空聚类簇。

步骤：

1)将数据集D中的所有对象指定为未标记状态。

2)读取一个未标记的对象p，在D中寻找未标记的所有满足dist(p,q)

3)如果查找出的对象数大于等于MinPts，则标记该对象为时空核心点，建立新的时空簇C，簇号为ClusterID；反之则标记为时空噪声点，并且转步骤2。

4)将p时空邻域内所有对象加入C，将其的簇号赋值为ClusterID。从C中未被标记的对象开始逐一继续搜索，将所有时空密度可达的对象簇号赋值为ClusterID。

5)ClusterID+1，转步骤2，直到D中所有点都被标记为止。

上述算法和DBSCAN拥有相同的时间复杂度O(n2)。

4 实例分析

以浙沪交界水域为研究对象，浙江沿海东航路、中航路、洋山港主航道、小型船舶和渔船习惯航路等在这里交汇，交通流密集，通航状态复杂，2016年7—12月的船舶流量线如图2。在图2中ABCD四边形界限内提取2017年1月5、10、15、20、25日共40万余条船载AIS数据。

图2 研究区域Fig. 2 Research area

4.1 数据预处理

以1月15日75 722条数据为例，经算法1处理后，即对于同一艘船舶每分钟内仅保留第一条AIS数据，得到20 850条AIS数据，见表1。

表1 处理后的AIS数据列表Table 1 AIS data list after preprocessing

4.2 时空聚类分析

以上述20 850条AIS数据为基础，使用JAVA语言编写并借助WEKA软件运行船载AIS数据时空聚类算法。反复调整参数，当Eps=0.9 n mile、Δt=3 min、MinPts=35时，即对于任意一点p，在以p为圆心、Eps=0.9 n mile为半径、分别向上向下延伸高度为Δt=3 min的圆柱体内至少有MinPts=35个点，该圆柱体在三维时空域内不断游走，直至不再包含35个点，所有网进的点形成一个时空邻近簇。所选数据集形成2个时空簇，如图3、表2。

图3 聚类结果示意Fig. 3 Clustering result visualization

时间MMSI经度/(°)纬度/(°)簇20:50412425318122.656 230.511 73cluster020:49412425318122.654 930.510 25cluster017:25412427363122.545 930.515 62cluster117:50412427363122.560 630.503 11noise

聚类结果特征参见表3。从19∶18至21∶14时，该水域有31艘船舶(根据MMSI编码规律分析[22]，含25艘渔船，3艘国际航行船舶，3艘国内货船)的1 725个AIS数据点在图中位置集中出现，满足时空密度条件构成簇0(cluster0)。从17∶15至17∶30时，该水域有9艘船舶(含8艘渔船，1艘国际航行船舶)的121个AIS数据点在图中位置集中出现，满足时空密度条件构成簇1(cluster1)。

由此可看出，当日17∶00、20∶00前后该水域渔船结伴而行、密集活动的情况较突出，东航路、中航路虽然AIS数据点密集，但由于商船之间独立性较强，并未发生AIS数据点在时空邻域内密集出现的情况。

表3 聚类结果特征Table 3 Clustering result characteristics

4.3 聚类对比分析

按照4.1、4.2节所述方法对该月其他4天(为总结规律，不选择连续日期)的AIS数据开展时空聚类分析，参数Eps=0.9 n mile、Δt=3 min、MinPts=30或35，最后形成1或2个簇，如图4。

图4 聚类结果示意Fig. 4 Clustering result visualization

当月5天的数据聚类结果对比如表4。

表4 聚类结果特征对比Table 4 Contrast of clustering result characteristics

5天AIS数据聚类形成多个不同的簇，各簇的点在空间分布上相对分散，但时间分布上呈现一定规律，18∶00～19∶00时左右船舶在时空域上比较密集(占总簇数60%以上)。

5 结 语

通过分析船载AIS数据特征，提出时间切片化约简方法，在DBSCAN算法基础上引入时间和空间元素给出船载AIS数据时空聚类算法，并对浙沪交界复杂水域的船载AIS数据开展时空聚类分析，得出渔船结伴而行、18∶00～19∶00左右船舶密集的常见交通模式。与其他船载AIS数据挖掘算法相比，笔者所提算法能更好地顾及船舶交通流的时空耦合特征，发现隐含的时空模式，为主管机关开展船舶交通管理、优化通航秩序、保障航行安全等提供了一种新途径。

该算法对参数较敏感，参数选择需较多专业背景知识，部分小型船舶存在不开启AIS或AIS数据报告间隔过大的情况，以上问题影响数据分析结果，有待下一步深入研究。