基于GRU 自编码器的船舶航线提取

任成杰，陈怀新，谢卫

（1.电子科技大学 资源与环境学院,四川 成都 611731;2.中国电子科技集团公司第十研究所,四川 成都 610036）

随着船舶自动识别系统(automatic identification system,AIS) 在船上的广泛应用，船舶轨迹数据的获取越来越容易，如何从这些海量的数据中挖掘出有价值的信息，对于研究船舶交通行为模式、分析船舶交通流特征具有重要的意义[1]。

在众多轨迹分析任务中，航线提取可以从凌乱繁杂的轨迹中得到船舶运动的主要线路，是船舶轨迹异常检测、位置预测等研究的基础。目前，有关航线的研究主要存在于航线设计[2-5]和航线规划[6-10]方面，有关航线提取方面的研究较少。船舶航线指特定海域内大量船舶航行轨迹反映出的航线簇的特征线[11]，Halpern 等[12]利用格网统计法，通过统计网格内船舶出现的频次来反映船舶的分布，进一步判断主要航线。Lin 等[13]对不同的轨迹进行比较，将相似的轨迹合并得到船舶航线。Wang 等[14]利用核密度方法对南海的主要航线进行了提取。具体而言，提取船舶航线可分为轨迹聚类和提取聚类典型轨迹两个问题。

轨迹聚类旨在发现具有相似运动模式的轨迹簇，揭示运动目标的潜在特征[15]。传统轨迹聚类方法在定义了轨迹相似度的基础上，利用基于距离和基于密度的算法对轨迹进行聚类。Lee 等[16]首次将每条轨迹划分为轨迹段，并利用基于密度的聚类算法对轨迹段进行聚类。Pallotta 等[17-19]利用增量DBSCAN 算法对AIS 船舶轨迹中的特征点进行聚类，并在次基础上提取了船舶交通运动模式。Vries 等[20]将船舶轨迹看作时间序列，采用动态时间规整(dynamic time warping，DTW)和编辑距离(edit distance，ED)来计算轨迹的相似度，并且结合轨迹压缩的方法，利用核k均值算法对船舶AIS 轨迹聚类。Wang 等[21]提出一种基于Hausdorff 距离和HDBSCAN 的船舶轨迹聚类方法，这种方法可以自适应地将船舶轨迹的形状特征进行聚类，并具有良好的可扩展性。

聚类典型轨迹是指能代表每一类轨迹整体的长度、方向、位置和形状的轨迹。Coelho 等[22]利用定义的投票函数从轨迹簇中选择典型轨迹。Lee 等[16]将轨迹段视为向量并通过计算平均向量来得到代表轨迹。王加胜等[11]采用基于三角网的两线中心线提取算法，将聚类中心线计算转化为两条中心线进行计算，通过迭代的方法得到最终的聚类中心线。

基于传统轨迹聚类的方法虽然可以对一定时间和区域内的船舶轨迹进行聚类，但在定义不同长度轨迹间的距离度量时较为困难。而在提取典型轨迹时，传统方法定义较复杂，且需要一定的后续处理才能得到最终的典型轨迹。针对以上问题，本文提出采用GRU 自编码器（GRU-AE）进行AIS 数据的深度信息编码，可将不同长度的轨迹编码表示为统一格式的深度特征，结合DBSCAN算法，再利用聚类簇中心解码反演进行船舶航线提取，从海量AIS 数据中挖掘船舶轨迹规律。

1 基于GRU-AE 的航线提取方法

船舶航线是指能代表众多船舶轨迹在空间上的整体特征（长度、方向、位置和形状）的特征线。利用AIS 数据挖掘的船舶航线提取流程如图1 所示。

图1 利用AIS 数据的船舶航线提取流程Fig.1 Ship route extraction process using AIS data

提取流程可分为两个主要过程。其一是利用GRU 自编码器提取船舶轨迹中的深度特征，该过程包含AIS 原始数据的预处理，以及GRU 自编码器的构建与训练。首先根据速度与时间阈值从原始AIS 数据中分离出合理的船舶轨迹，其次将船舶轨迹通过编码器生成其深度特征，再通过解码器生成解码轨迹，根据解码轨迹与原始船舶轨迹间的差异来调整GRU 自编码的参数，使得解码轨迹尽可能地接近原始船舶轨迹，由于此时可以从深度特征中完全还原出原始船舶轨迹，故认为此时提取的深度特征是合理的。其二是深度特征的聚类和船舶航线的生成，该过程利用DBSCAN算法对船舶轨迹的深度特征进行聚类，并将聚类后的类簇中心通过训练后的解码器解码反生成船舶航线。

1.1 门控循环单元

门控循环单元(gate recurrent unit,GRU)是由Cho 等[23-24]在2014 年提出的一种特殊类型的循环神经网络(recurrent neural networks,RNN)，它旨在解决标准RNN 中出现的梯度消失问题。GRU的功能类似于著名的LSTM 网络，不同之处在于，GRU 中只存在两个门，比LSTM 少一个门，因此GRU 中包含的参数更少，训练速度更快，使用的内存更少。GRU 利用重置门和更新门来解决梯度消失问题，这些门能够长时间保存信息，而不会在一段时间内丢失信息[25]。GRU 单元的图形表示如图2 所示。

图2 门控循环单元(GRU)Fig.2 Gate recuurent unit (GRU)

更新门决定了有多少过去的信息应该被传递到之后的模型中：

式中：xt为t时刻的输入；ht-1保存了t-1时刻的信息；xt、ht-1分别与权重矩阵Wz、Uz相乘并经过激活函数后得到更新门在t时刻的输出zt。

GRU 利用重置门来决定有多少过去的信息需要被遗忘，其输出表达式与更新门类似：

当前记忆内容利用重置门来存储与过去相关的信息：

当前时间最终记忆内容会保留当前单元的信息并传递到下一个单元中：

1.2 GRU 自编码器

本文利用GRU 自编码器来重建预处理后的轨迹序列，并产生每条轨迹的固定长度的深度特征。自编码器模型由两个GRU 网络组成，包括图3 中左边所展示的编码器GRU 部分以及右边所展示的解码器GRU。

图3 自编码器结构Fig.3 Auto-encoder structure

该模型的输入是轨迹序列 TRi={p1,p2,···,pT}，当最后的pT被处理后，编码器的隐藏状态h被用来作为整个轨迹序列的深度特征。

解码器将h作为初始隐藏状态，产生输出q1，并进一步产生 (q2,q3,···,qT)，它的目标是重建输入轨迹序列 TRi。通过最小化重建误差，编码器GRU 和解码器GRU 被放在一起进行训练，其中重建误差由均方误差产生：

固定长度的深度特征h是输入轨迹序列 TRi的合理表示，因为利用解码器可以从h中重建整个输入轨迹序列。将深度特征作为DBSCAN 聚类算法的输入，选择欧氏距离作为距离度量方法，得到聚类结果。

1.3 航线提取

经过DBSCAN 聚类，得到不同的轨迹簇。对于某一个轨迹簇，取其中的核心对象集合为Ci，将对象集合的中心作为航线的深度特征：

2 实验及结果分析

2.1 实验一：利用模拟数据测试算法的合理性

在仿真数据中，基于3 条不同形状的航线，包括直线型航线、曲线型航线及椭圆形航线，通过添加一定的噪声，并且将轨迹的长度取为50～100的随机值，以此生成30 条模拟轨迹，如图4(a)所示，其中红色曲线为预设航线，绿色曲线为合成轨迹。

图4 合成轨迹与生成航线Fig.4 Synthetic trajectories and generated routes

本次实验中将GRU 自编码器的隐藏层大小设置为30，学习率设为0.000 1，迭代次数设为1 000。经过DBSCAN 算法聚类后，得到3 个轨迹聚类簇并生成相应的航线，如图4(b)所示，其中3 种不同颜色的曲线代表3 个不同的轨迹簇，蓝色曲线代表生成航线。对比生成航线与预设航线可以看出，本文算法所提取的航线与实际航线基本一致，且由于合成轨迹的长度并不相同，这说明本文算法适用于实际中不同长度的船舶运动轨迹聚类，免去了传统轨迹聚类中定义不同长度轨迹间距离度量的步骤。

2.2 实验二：采用实际数据验证算法的效能

该实验在真实数据集中测试本文算法，研究区域选择美国波士顿港口附近海域。波士顿港是美国马萨诸塞州波士顿的一座港口，位于波士顿湾之内，是马萨诸塞州规模最大的港口，也是美国东海岸的主要港口之一。研究数据采用海洋能源管理局（BOEM）和美国国家海洋与大气管理局（NOAA）提供的2018 年AIS 数据，如图5 所示。

图5 研究区域及研究数据Fig.5 Research area and data

2.2.1 轨迹预处理

AIS 数据中包含众多与船舶运动相关的信息，包括船舶的水上移动业务标识(maritime mobile service identify,MMSI)、所处的经纬度、航向和航速等信息。考虑具有不同MMSI 标识的船舶目标集合O={o1,o2,···,oL}，对每个目标o，它的历史AIS 数据按时间排序后形成序列So={p1,p2,···,pn} 。对于轨迹序列So，即使它是来自同一艘船的轨迹，也会有不同航次的轨迹的区别，而不同航次的轨迹应被认为是不同的轨迹。为区分不同航次的轨迹，利用时间和速度阈值对轨迹序列进行预处理，得到处理后的轨迹集合TRS={TR1,TR2,···,TRN}，由于后续将对轨迹中包含的空间信息进行处理，故保留各轨迹点的经纬度信息，即TRi={(lon1,lat1),(lon2,lat2),···,(lonm,latm)}。

对波士顿港口附近的AIS 数据进行预处理，其中时间阈值取为30 min，速度阈值取为0.5 kn，如图6 所示，经过预处理后不同航次的轨迹被明显地区分开来。

图6 预处理前后的轨迹Fig.6 Trajectories before and after preprocessing

2.2.2 轨迹聚类及航线提取

预处理后一共形成918 条轨迹，将轨迹作为输入。将自编码器的隐藏层大小设置为100，学习率为0.000 1，迭代次数设为3 000。经过训练后，918 条不同长度的轨迹被统一编码为长度为100的深度表示，利用DBSCAN 算法对其进行聚类，经过反复实验，将密度半径设为0.8，密度阈值设为5，此时聚类效果最佳，去除不在主要路线上的噪声轨迹后一共得到16 个轨迹簇，如图7 所示。

图7 轨迹聚类后形成的不同轨迹簇Fig.7 Different trajectory clusters after trajectory clustering

分析聚类后的16 个轨迹簇可知，该区域内船舶运动的起点和终点主要包括图7 中A～G共7 个位置，其中A、B为进出目标区域的地点，C～G为不同城市。由于运动方向相反，运动形状相似的轨迹簇被认为是不同的轨迹簇。例如图7 中轨迹簇(1)和(2)，簇(1)由A点出发运动到B点，而簇(2)由B点出发运动到A点。轨迹簇(3)(4)、(5)(6)、(7)(8)、(9)(10)和(11)(12)同样具有运动方向相反的特征。在16 个轨迹簇中，大部分簇内的轨迹具有相同且唯一的起点和终点，而对于簇(10)和(16)，它们存在两个不同的起点，导致该现象的原因可能是AE (auto encoder)结构中的编码器没有很好地区分这两种起点不同的轨迹，使得两种轨迹的深度特征间距离相近，因而在聚类过程中被认为是同一类轨迹。

通过统计各个不同轨迹簇内的船舶类型可知，经过实验区域且不做停留的轨迹簇(1)(2)中主要包括拖船和领航船，而起点和终点均在实验区域内的轨迹簇(3)～(14)主要包括的是客船的轨迹。客船在城市C、D、E、F间航行，其中城市C、D之间的客船流量最大，且往返间具有两条明显不同的航线，见图7 中轨迹簇(3)(4)(5)(6)。

由以上分析可知，聚类后各轨迹簇在轨迹形状、方向和船舶类型等特征上各不相同，这说明利用船舶轨迹的深度表示对轨迹进行聚类具有较好的效果。对聚类后的每个轨迹簇，计算其在深度空间中的中心，并通过解码器生成对应的航线，如图8 所示。

图8 航线提取Fig.8 Route extraction

图8 中航线的宽度代表了通过该航线的船舶流量，其中航线(5)和(6)流量最大，其余航线流量相近。对比图7 与图8 可知，提取的航线在整体上较好地体现了各轨迹簇在空间上的长度、方向、位置和形状等特征，这说明了航线的合理性。

2.2.3 实验结果对比

本文方法与相关论文航线提取方法（Hausdorff[21]、DTW[20]、三角网[11]）进行对比分析，其处理结果如图9 所示。

图9 中基于Hausdorff 距离的聚类无法分辨出相同路径上不同航向的轨迹，需进行一定的后处理；而利用三角网提取的航线均存在以下缺点，即起点或终点不明确、存在航线折返、航线不平滑等。

图9 不同航线提取方法对比Fig.9 Comparison of different route extraction methods

对此，本文还提出航线评价的量化指标，即整体轨迹与航线间的平均距离：

式中：Davg为平均距离，Davg越小说明航线提取越准确DIS (DIS_Hausdorff/DIS_DTW)为轨迹相似性度量方法；Routej为与轨迹 TRi最近的航线。不同方法的对比结果如表1 所示，可以看出本文方法在两种度量方法下的性能均优于传统方法。

表1 航线提取效果对比Table 1 Route-extraction effect comparison

3 结束语

本文提出了一种基于GRU 自编码器的船舶航线提取方法，通过深度学习的GRU 自编码器进行AIS 数据的深度特征信息提取。在实验一中，基于合成数据集测试验证了航线提取算法的有效性以及对不同长度轨迹的适应性；在实验二中，采用波士顿港附近海域2018 年内的AIS 数据，利用时间和速度阈值对不同航次的轨迹进行分割与预处理，采用GRU 自编码器将船舶轨迹编码为固定长度的深度表示，并在深度空间中利用DBSCAN 算法对船舶轨迹进行聚类，共得到16 个轨迹簇，通过航线提取算法得到研究区域内的16 条航线，对比原始数据与所提取的航线，表明了本文方法可以有效地进行海量船舶航行数据挖掘，提取不同模式下船舶的轨迹航线。本文方法对比传统航线提取方法具有精确提取和无需后处理的优点，且同时可以提取出各航线的船舶流量和船舶类型等有价值的信息，为后续目标区域内的船舶路径规划、异常检测和位置预测等研究与应用打下了基础。