船舶自动识别系统(automatic identification system, AIS)通过GPS/北斗获得船舶自身的位置、航速和航向等动态信息，并经由AIS外接的VHF广播对外发送，发送间隔严格与船舶航速相关，一般为2~30 s^[1]。AIS的信息交互功能有助于船舶避碰和海事监管^[2]，成为船舶交通流分析和事故研究的主要数据来源^[3-5]。然而，AIS动态信息常出现丢失，导致经由AIS接收到的船舶轨迹信息出现断续甚至轨迹点连续缺失^[6-9]，容易导致船舶驾驶员误判交通态势产生，妨害海事部门监管船舶，更会给以AIS动态信息为基础的船舶交通流分析带来偏差和困扰。因此，需要修复AIS数据中缺失的船舶时空轨迹。

AIS数据是离散的时空轨迹序列，在实际应用中需要同步插值处理以获得连续轨迹^[10-11]。内河船舶时空轨迹同步插值方法中，分段三次样条插值法最为精确，但是误差会随着船舶轨迹缺失距离的增加而增大^[12]。SUTULO^[13]提出考虑船桨动力、舵效力、风、水流等多重因素的多自由度船舶力学模型，理论上可用来修复船舶运动轨迹和姿态，然而由于AIS数据仅包含船舶位置、速度和航向信息，不能为模型提供足够的参数输入。HAMMOND等^[14]及LIU等^[15]分别提出了基于概率推理和张量分析的船舶轨迹预测方法，但该方法只适用于空旷的远洋船舶。SANG^[16]参考内河船舶操纵性能和船舶运动规律，提出了直线、圆弧和曲线轨迹组合的船舶轨迹修复方法，但该方法没有考虑到船舶速度变化对轨迹的影响，当船舶AIS轨迹数据出现连续缺失时，该方法由于需要判断船舶运动状态导致计算量急剧攀升。受通航规则和航道尺度限制，通过特定水域的内河船舶，其行为常常相似^[17-18]，因此，可以采用机器学习方法从相似轨迹数据样本学习船舶行为模式，进而预测和修复缺失的船舶轨迹。最小二乘支持向量机(least squares support vector machine, LS-SVM)作为常用的回归预测模型，采用最小二乘线性系统作为损失函数，简化了计算复杂度，适合应用于海量AIS数据的修复。

基于以上分析，本文提出一种基于LS-SVM的内河船舶缺失轨迹修复方法。同步处理AIS轨迹数据后，采用二阶段相似轨迹快速搜寻和轨迹相似度评估算法找出最相似轨迹；然后利用粒子群优化(particle swarm optimization, PSO)算法和相似轨迹优化LS-SVM模型参数，预测缺失船舶轨迹，并通过实地实验评估本文所提出方法的有效性。

1 时空轨迹同步

基于LS-SVM的内河船舶时空轨迹修复方法需要AIS轨迹序列具有稳定的时间周期。内河船舶所发出的AIS动态信息时间间隔不稳定，需采用插值法将船舶AIS轨迹数据同步为时间间隔固定的时间序列。内河中大部分船载AIS的数据发送标准间隔为30 s，因此以30 s作为数据同步的固定周期。

采用三次样条插值法作为轨迹同步算法。三次样条插值法是常用的时空轨迹同步算法，当船舶时空轨迹缺失导致数据量少、间隔不规整时，三次样条插值法具有良好的修复和同步效果^[19-20]。船舶轨迹序列是二维时间序列，需要分解为经度方向和纬度方向两个时间序列分别处理。三次样条插值有三种边界条件，以端点的导数作为边界条件。假设AIS时空轨迹序列中有m个轨迹点，设t_i(i=1, 2, …, m)为轨迹点的时间，x_i为经度，y_i为纬度，速度为v_i，航向角为θ_i，v_xi=v_icosθ_i为经度方向的速度，v_yi=v_isinθ_i为纬度方向的速度。以序列时间起点为零点，对应的经纬度坐标作为坐标原点，采用经纬度距离转换公式将经纬度转换为距离。Δx_i表示第i个点与第一个点之间经度方向的距离，Δy_i表示第i个点与第一个点之间纬度方向的距离。对于经度和纬度方向关于船舶行驶距离的时间序列，端点的导数即为v_xi和v_yi，代入样条函数之后即可求得系数矩阵。得到系数矩阵后，即可通过分段样条函数解得区间内任意时间t对应的经度方向距离信息。分别求得经度方向和纬度方向的距离样条函数后，根据输入的时间可以求得该时间点对应的船舶行驶距离，然后将行驶距离转换为经纬度坐标。

2 相似轨迹查找与修复 2.1 相似轨迹查找

在相似轨迹查找中，需要根据丢失轨迹点前后一定数量的待匹配轨迹点判断船舶的运动状态。根据船舶轨迹的时空相关性，本文取15作为待匹配轨迹点数，即对于缺失轨迹数据，取缺失轨迹点前后各15个轨迹点，共30个轨迹点作为待匹配轨迹，如图 1所示^[21]。待匹配轨迹分为两段，缺失轨迹之前的15个轨迹点中，起点和终点分别为P₁、P₂，缺失轨迹之后的15个轨迹点中，起点和终点分别为P₃、P₄。为解决在船舶轨迹大数据样本中搜索效率低下的问题，提出一种粗匹配-细匹配两层匹配框架。

利用轨迹粗匹配从海量的AIS轨迹历史数据库中缩小查询范围，减少细匹配的计算量。根据内河船舶航速，一个时间间隔内船舶航行距离通常不超过200 m。以序列点初始坐标起始点P₁(x₁, y₁)和结束点P₄(x_m, y_m)为中心，200 m为半径搜寻轨迹点，如图 2所示。若搜索出的轨迹中同时存在P₁'和P₄'两个点处于初始点和结束点半径范围之内，则将该条轨迹纳入待匹配轨迹集，同时仅保留P₁'和P₄'之间的轨迹点，多余的轨迹删除。

在粗匹配备选轨迹集T_x=(T₁, T₂, …, T_n)中，各条轨迹初始点和结束点都是与待匹配轨迹对应对齐的。下一步需要对T_x中的每一条轨迹，找出与待匹配轨迹P₂、P₃相对应的轨迹点。同样以200 m作为半径，搜索满足条件的轨迹，如图 3所示。满足后，则将该轨迹加入细匹配轨迹集。

船舶航行速度不同会使得船舶轨迹点集的疏密程度不同，以至于待匹配序列点与模板点无法精确对齐。针对不匹配的两个序列集，采用Hausdorff距离为其相似度度量空间。设两条轨迹相似度表示为Sim(i, j)：

$ {\rm{Sim}}\left( {i, j} \right) = H\left( {i, j} \right) + \left| {{N_i} - {N_j}} \right| $

(1)

式中H(i, j)为轨迹i和轨迹j的Hausdorff距离, N_i表示轨迹i的节点数量。H(i, j)包含缺失处前后两段轨迹，记为i_s和i_e。则式(1)改写为:

$ {\rm{Sim}}\left( {i, j} \right) = [H({i_{\rm{s}}}, j) + H({i_{\rm{e}}}, j)] + \left| {{N_i} - {N_j}} \right| $

(2)

船舶轨迹信息中，位置和速度最能表征船舶运动特征。Housdorff相似度可以表征其在轨迹位置相似度，但若两条轨迹节点数目不一致，即轨迹点疏密程度不一样，则意味着两条轨迹速度有很大差异，因此引入节点差|N_i-N_j|作为相似度衡量公式(式(1))中的补充项。

2.2 相似轨迹回归与轨迹修复

采用LS-SVM修复AIS丢失数据的步骤如图 4所示。采用适用性优异的径向基核(radial basis function，RBF)作为AIS数据修复LS-SVM模型的核函数。基于RBF核函数的LS-SVM模型具有惩罚系数C与核函数宽度变量σ两个参数。这两个参数基本决定了LS-SVM的泛化能力。本文选择其中应用最广的PSO优化算法确定这两个参数。

3 实验分析与验证

在长江中游武汉航段开展验证实验。实验数据来源于长江海事局，共取得2015-06-01—2015-08-31总计3个月3 001万余条原始AIS数据。实验地域范围为东经114.45°~114.56°，北纬30.60°~30.71°，河段长度大约为30 km。

3.1 数据同步

图 5实线所示轨迹为2015-06-02经过长江武汉段的一段原始AIS动态数据(MMSI：413940407)，该段AIS轨迹中，存在数据发送周期不稳定的现象。采用三次样条插值对轨迹的经纬度同步效果如图 5中修复前所示。可见，采用三次样条插值法对船舶轨迹的还原度很高，能够有效地将时间周期不规律的AIS数据变为固定周期的轨迹时间序列。

3.2 相似轨迹查询

在武汉水域AIS轨迹数据库中，选取一条完整轨迹数据进行算法验证。在数据样本中，选择武汉段天兴洲下方处航道中间部分为起始点，一条下行船舶轨迹为目标轨迹，进行轨迹库快速检索。将一条有50个连续轨迹点的完整轨迹从第16个点开始连续删除20个轨迹点，得到缺失的轨迹数据。采用两阶段匹配方法共得到14条待匹配轨迹，所得结果如表 1所示。

在检索结果集中，使用前文所述的匹配方法进行计算。其与待修复轨迹的轨迹相似度计算结果如表 2所示。在所得计算结果中，取最小值8号为匹配结果，整体轨迹及结果如图 6所示。

3.3 轨迹修复实验

匹配完相似轨迹，则可以根据相似轨迹训练回归模型，用于预测丢失轨迹点的位置。为了验证算法的有效性，采用人工去除部分轨迹点的方式获取缺失数据样本，用于评估最终数据修复结果。

使用PSO优化LS-SVM方法对相似样本进行建模，当拟合精度达到要求后，进行缺失数据的预报。由于AIS数据样本量较大，采用实时性好的全局PSO算法进行优化，试验对比分为两组：一组是PSO优化前后的LS-SVM的相似样本建模精度对比；另一组是PSO优化后LS-SVM方法和插值法、传统SVM算法对丢失数据的修复对比。

PSO算法中加速常量C₁、C₂分别为0.5, 1;最大进化代数为15，种群规模为10;参数变化极值V_max(C)为1×10⁶，V_min为1，V_max为1×10⁴，V_min(σ)为1。

根据训练模型预报的拟合程度来评价LS-SVM算法对相似样本的建模精度，选取均方根误差作为拟合程度的目标函数：

$ J = \sqrt {\frac{{\sum\limits_{i = 1}^n {\left( {{{\left( {{C_1}\left( {{x_{{\rm{p}}, i}} - {x_i}} \right)} \right)}^2} + {{\left( {{C_2}\left( {{y_{{\rm{p}}, i}} - {y_i}} \right)} \right)}^2}} \right)} }}{n}} $

(3)

式中:n表示样本数据长度；C₁、C₂分别为经纬度与绝对坐标系下的单位长度转换系数，当前航段，取C₁=96 297.6、C₂=111 194.9；x_{p, i}与x_i分别为预报经度与实际经度值; y_{p, i}与y_i分别为预报纬度与实际纬度值。

分别使用PSO优化前后的LS-SVM算法进行回归，再分别使用回归后的模型进行递推预报，4组相似样本的训练结果如图 7所示。

计算得改进前后的拟合误差如表 3所示。由表 3可以看出，PSO优化之后的LS-SVM算法的拟合精度明显上升，考虑到传感器数据的不确定性等因素，该优化算法可以满足数据修复需求。由上述相似样本所训练的模型可以直接进行待修复轨迹的预报，部分模型参数结果如表 4所示。

图 8是LS-SVM模型和PSO优化后的LS-SVM模型对修复样本经纬度数据的预报结果。由于实际修复时待修复样本数据不可知，使用一组相似样本中的一条轨迹数据作为训练数据，另一条作为假设待修复数据。

按照式(3)计算得拟合误差如表 5。从表 5中可以得出，PSO优化后的LS-SVM修复误差更小。

3.4 实验对比

为对比常用三次样条插值法、BP神经网络算法和LS-SVM算法的优劣，以武汉段随机挑选出的30条轨迹为例验证三种算法在修复缺失AIS轨迹方面的时效性和准确性。当连续丢失20个轨迹点时，三种算法对这30条轨迹修复的平均误差和消耗时间分别如图 9和图 10所示。

可以看出，在轨迹修复精度方面，本文提出的采用PSO优化模型参数后的LS-SVM算法要好于BP神经网络和常用的三次样条插值法，绝大多数情况下的误差都小于30 m，相对于船舶外形尺寸来说具有较高的修复精度。在轨迹修复时效性方面，三次样条插值法由于不需要搜寻相似轨迹和训练模型参数，消耗时间几乎都稳定在0.01 s以内，远小于BP神经网络算法和LS-SVM算法。LS-SVM由于简化了损失函数表达式，在运行效率方面总体上要好于BP神经网络，处于可接受的范围之内。

4 结论

1) 提出的粗-细两层匹配方法，能够快速地从海量历史轨迹数据库中搜寻出符合条件的相似轨迹。改进的Hausdorff距离计算公式，融合了轨迹空间相似度和船舶航行速度相似度，能够更好地找到相似船舶轨迹，为基于LS-SVM回归模型的AIS数据修复方法提供数据基础。

2) 采用相似轨迹作为LS-SVM算法的输入样本，通过训练回归模型，能够在长距离的情形下较准确还原AIS数据。采用LS-SVM算法比BP神经网络算法具有更优的时效性，在轨迹点出现长距离连续丢失的情况下，修复精度高于传统的插值法。

3) 本文的研究有助于改善AIS数据质量，对于海事监管、AIS信号传播规律分析、船舶行为特征分析与挖掘具有积极作用。