基于网格化压缩挖掘船舶航道位置信息

， ，

(南京船舶雷达研究所，南京 211106)

0 引言

由于海上目标的异常多表现为航迹位置的异常，所以为了能够检测出这种位置异常，需要对正常船舶航道的位置信息进行提取。而船舶自动识别系统(Automatic Identification System，AIS)[1]的广泛应用生成了海量的航迹数据，这为基于AIS数据挖掘正常船舶航道位置信息提供了条件。

就现阶段而言，国内外对航路模型的构建过程多基于单一目标的小样本进行。比如国内的宁建强等[2]提出一种细粒度网格的方法，通过对航迹从不同粒度上进行处理从而提取航路模型；国外的Pallotta等[3]通过采用改良后的的DBSCAN (density-based spatial clustering of applications with noise)聚类算法构建相应的船舶航路模型；而Guillarme等[4]则采用轨迹分割的方法完成航路聚类构建；至于Osekowska等[5-7]则通过将势场的概念应用于船舶航路的构建和提取中。

这些航路模型构建的方法在海量数据背景下，都会存在样本描述整体出现偏差的问题，更有甚者发生错误与遗漏[8]。所以为了从海量AIS数据中提取出船舶的主航道位置信息，为海上目标的异常检测提供位置上的先验知识，本文提出了一种基于网格化压缩提取船舶航道位置信息的算法。首先为了提高海量数据的挖掘效率问题，该算法根据AIS航迹特点提出采用网格化压缩的方法将航迹数据进行压缩，从而在保证不丢失航迹位置信息的基础上降低数据量，从而提高了处理效率；之后由于压缩后的航迹数据缺少航向信息，所以该算法采用了九宫格矢量化的方法重新构建方向属性，既重构了方向属性，又消除了原始AIS数据中的船首向抖动的问题；最后在重构的八个方向上分别采用变阈值设置方法实现最终的密度聚类，挖掘出不同方向上航道的位置信息。

1 航道位置信息挖掘算法模型

本文基于网格化压缩挖掘船舶航道位置信息算法的总体模型架构如图1中的船舶航道位置挖掘算法流程图所示：

图1 船舶航道位置挖掘算法流程

根据流程图可以看出，本文主要从四部分进行处理和研究的：1)数据预处理；2)网格化处理；3)九宫格矢量化；4)航道位置信息模型的挖掘与展示。

其中数据预处理过程主要是从数据去噪和航迹切割角度进行。具体过程如下所述。

因为经由数据库中提取出的AIS原始数据存在大量噪声数据，例如MMSI噪声，航迹位置噪声及航向信息噪声等。为了能够剔除噪声数据，本文通过从MMSI(Maritime Mobile Service Identity)号，航以及航迹经度、纬度等角度对其进行筛选去噪，即数据去噪。

因为同一个MMSI号对应的航迹实际上存在有多个空窗期(见定义1)，所以为了能够满足后续在网格化压缩过程中对船舶航迹数据连续性的要求，需要将同一个MMSI号对应的AIS数据依照空窗期进行分割，将其切割成若干连续的航迹，即航迹切割。

定义1：空窗期。

由于主观或客观环境的干扰导致目标离开监控窗口，监测仪器在一段相当长的时间内丢失对这个目标的跟踪，而且在再次跟踪到该目标时，无法忽略中间缺失过程产生的误差，这段缺失过程就是该目标的一个空窗期。

2 网格化压缩方法

实际中，因为船舶的航速较低，一般大约在30几节以下，对于超过30节的船舶很少，而相较之下AIS信号产生的频率却很高，一般在十几秒到几十秒之间，最快的2到3秒就发射一次，这就导致在相当长的一段时间之中，AIS系统生成了大量的航迹点，而实际上船舶的位置和航向等航行状态却并未发生太大的实质性的变化，所以这就使得船舶的航迹数据里包含了大量的冗余状态信息。为了去除这些冗余的数据，本节提出了一种网格化压缩的方法，通过对每条连续的航迹数据进行压缩处理，从而实现了冗余数据的去除，同时也有效提高了后续处理过程的计算效率。

网格化压缩方法主要是通过以下四个步骤进行处理的：

第一步：首先对待研究的区域W按照经纬度的值划分成大小为step的网格，如图2的网格化过程图所示(图中A'是A的放大)，这里的step就是网格的最小粒度大小，该值的大小选择决定着网格化压缩的效果；

第二步：然后将落在网格中的所有航迹点的经纬度坐标都改成网格的中心点的经纬度坐标，而对于落在网格边界线上的点统一移到左侧或上侧的格子中，即将图2中所有落到A'格子中的点都压缩到点1位置。

第三步：之后将每一条连续的航迹按照时间属性(UDT_TM)进行排序，并对经纬度采用一阶差分的算法进行计算；

第四步：最后将经纬度差分为零的点去掉。至此实现了网格化压缩。

3 九宫格矢量化及航道位置挖掘

而压缩后的航迹数据失去了航向信息，所以本节提出了一种九宫格矢量化的方法为压缩后的航迹重构方向属性。而为了能并行化的挖掘出不同航向上船舶航道的位置信息模型，需要从不同航向上分别进行航道位置挖掘，但由于矢量化后的不同航向上的航迹数据的分布存在差异，所以本节采用变阈值的方法分别设置密度阈值从而实现在不同航向上航道位置的提取。

3.1 九宫格矢量化

经过上一节中的网格化压缩之后，船舶的航迹数据只剩下位置信息，而缺失航向信息，所以为了能够使网格化之后的航迹数据准确反映航向信息，同时去除原始航迹中航向抖动的问题，本节提出了一种九宫格矢量化的方法重构航迹的航向属性。

定义2：矢量化规则。

假设航迹的初始航迹点的经纬度坐标为P0 (LON0，LAT0)，其下一航迹点的经纬度坐标为P1 (LON1，LAT1)，则根据代数矢量的定义法则可以得出P0点的矢量为(LON1-LON0，LAT1-LAT0)。

假设1：九宫格编码假设。

如图3所示，首先对九宫格进行编码形成编码格，然后假设9号格为初始航迹点的位置P0，则下一航迹点的位置P1定会落到剩余的八个格中的任意一个格中，则此时P0的方向编码即为P1点落到的格子对应的编码号。

图3 九宫格编码图 图4 假设轨迹图

如图4是一个假设的航迹，根据矢量化规则与九宫格编码假设可以得出轨迹点a的轨迹方向编码为7，轨迹点b的轨迹方向编码为5，轨迹点c的轨迹方向编码为2。这样这条轨迹方向的整体编码形式就是7-5-2。如此这般即可将所有的压缩后的航迹点重构出其航向属性。

但是该矢量化方法需要满足假设1的条件，否则编码不成立。所以为了确定压缩后的航迹数据是否满足假设1，需要对网格化压缩后的航迹数据进行统计分析，具体过程可见第四章节实验中的概率密度统计分析。

3.2 变阈值设置挖掘航道

本文实现航道位置信息挖掘的过程基于的是网格密度聚类思想，网格密度聚类需要设置密度阈值TD。而为了从不同航向角度分别实现航路位置模型的提取，同时考虑到九宫格矢量化的8个方向的航迹数存在差异的问题，如果设置固定的密度阈值TD，会导致一些方向的航迹数据被其他方向的航迹数据冲淡，而误判为噪声网格，为此本节提出采用一种变阈值设置的方法(见定义3)对不同航向的航迹数据分别设置密度阈值TD。

定义3：轨迹格点阈值。

设网格密度值为D(D1，D2，…，Dn)，则如公式1所示，其中μ为网格密度值的均值，σ为网格密度值的标准差，TD为密度阈值，m为一个系数(m>0)。

μ=(D1+D2+...+Dn)/n

TD=μ+m·σ

(1)

之后通过阈值判决，将超过阈值TD的网格判为正常航道网格，将低于阈值TD的网格设置为噪声网格，并将其直接去除，最后通过可视化的方法对航道网格进行展示和选择。

4 实验过程及结果分析

4.1 实验环境及数据

本实验的硬件平台为Window7 x64位系统，内存为24.0 GB，处理器为Intel(R) Core(TM) i7-4770K CPU @ 3.50 GH，软件平台为R-3.4.3版本。本实验使用的是XX雷达基站采集的厦门港口海域的近一个月的AIS数据，其数据总量达到28.8 GB。

4.2 实验结果分析

4.2.1 网格化压缩效果分析

根据文献[2]介绍，图2中的Step大小是网格划分的关键。Step太大，容易丢失船舶轨迹中的一些转向信息；Step太小，压缩不充分。所以根据两个先验知识：1)在船舶的正常航行中，正常转弯过程都是在4到5倍的船长为半径的区域内进行；2)地球的经纬度每0.01度对应实际的地理距离约是1.1公里左右(见公式2)。而由于正常船舶最长400多米，所以本文采用0.02°×0.02°网格进行划分，这样既可以充分压缩，又不会丢失转向信息。

L1°=2πR/360°≈111.139km

L0.01°=L1°/100≈1.1km

(2)

实验中，由于数据量太大，R语言对于硬件平台的内存要求较高，在对原始数据进行处理时，无法一次性将所有数据进行展开，所以本文通过将一个月的数据依据时间属性分割成为三个数据集分别进行网格化压缩处理。

表1 数据压缩效果表

如表1所示是原始数据集分割成的三个数据集的三次数据压缩的效果，由此可见网格化压缩的倍数都在200倍左右，所以可见网格化压缩方法的压缩效果显著，可以在很大程度上去除冗余航迹信息，提高后续航迹位置信息提取过程中的计算效率。

为了确定压缩后的数据分布情况，从而确定压缩后的航迹数据是否满足九宫格矢量化假设要求，本实验对差分后数据的经度差分值属性(DLON)和纬度差分值属性(DLAT)进行了概率密度值统计。如图5所示，分别对应的是差分后的经度差分值属性(DLON)和纬度差分值属性(DLAT)，其二者的分布主要集中在0.02°，0°和-0.02°，其中中心最高峰值对应的是0，左侧次高峰对应的是-0.02，右侧次高峰对应的是0.02。这就表明差分后的航迹数据依然是连续的，压缩并没有失真。由此也可以证明，压缩后的航迹数据是满足九宫格编码假设的，因此压缩后的航迹数据是可以通过九宫格矢量化规则进行航向属性的重构。

图5 差分后概率密度统计

4.2.2 聚类效果展示

本实验采用并行化的思想，从重构的八个航向向上分别进行提取船舶航路位置模型，其网格密度阈值的选取是根据公式1进行的。实验中分别选取取m值为0，1，1.5和2进行了研究。实验结果显示，不同航向上航路的密度阈值中的m值的选择影响航路位置模型提取的效果。其中网格密度值较大的航向上，m值选择较大时效果显著，而网格密度值较小是，m值的选择较小时效果较好。

这是由于当网格密度较大时，该航向上航行船舶较多，出现异常的船舶也较多，只有提高m值，才能有效去除航路中的异常航迹；而当网格密度较小时，表示该航向上航行的船舶较少，尤其是受地理地形影响较大的航向区域，其基本上很少有异常航迹，所以只需要取较小的m值就可以完全实现航路位置模型的提取，反而较大的m值易于造成正常航路被误判而去除。

如图6所示是部分方向在适当的m下的航道位置聚类效果图，其中图6.1是m=1.5时，3号航向上的航道位置模型提取的效果图；图6.2是m=1时，5号航向上的航道位置模型提取的效果图。由于采用了网格化压缩，所以航道点迹成为离散状态，即图中显示的航路是有一个一个的航迹点组合而成的航迹区域。这也同时指出，在后续的海上目标的异常检测过程中，也需要对船舶目标的航迹进行网格化压缩，使其成为离散转态后再进行对比判决检测。

图6 提取的航道位置信息效果

5 结束语

为了从海量AIS数据中挖掘出船舶航道的位置信息模型，本文根据船舶航迹存在冗余的特点，提出一种基于网格化压缩挖掘船舶航道位置信息的算法。其中针对计算效率低的问题，该算法提出采用网格化压缩方法有效去除了航迹数据中的冗余数据，提高了海量数据聚类的计算效率。同时该压缩方法也为海量路径数据的压缩提供了一种算法支持。为了解决压缩后的航迹数据缺少航向信息的问题，本文采用的九宫格矢量化方法在网格化的基础上重构了船舶航向属性，为压缩后的航迹增加方向属性，同时也有效去除了原始航迹中航向抖动的问题。最后为了避免不同方向上数据相互干扰，易将核心网格误判成噪声网格的问题，本文在矢量化的八个方向上，分别采用不同的阈值实现航道位置信息模型的提取。

本实验中可视化的结果表明在选择合适的阈值下，该算法可以有效提取船舶的主航道位置信息。但是该算法提取的船舶航道只有一个位置信息，缺少航迹中的时序信息，需要后续从时序角度进一步挖掘提取。