基于自适应阈值的船舶轨迹异常点检测算法

韩昭蓉，许光銮，黄廷磊，任文娟

(1.中国科学院大学电子电气与通信工程学院,北京 100049; 2.中国科学院电子学研究所,北京 100190; 3.中国科学院空间信息处理与应用系统技术重点实验室,北京 100190)

0 引 言

随着定位技术、空间通信技术和计算能力的快速发展，人们积累了海量的时空轨迹数据，如船舶轨迹数据、人类活动轨迹、动物迁徙轨迹和气候气流数据等。大规模的轨迹数据蕴含了移动对象丰富的时空和行为信息，分析挖掘轨迹数据中有价值的信息在学术科学领域、商业应用领域和政府管理领域都具有重大现实意义[1]。其中，船舶轨迹数据是船舶行为规律挖掘、海事监管和船舶交通流预测的重要数据源。

在现实生活中，轨迹数据从来都不是完全准确的。由于定位技术的局限和外界干扰因素的影响(如设备故障、人为操作误差)，轨迹数据中存在大量的异常点[2]。轨迹中的异常点为严重偏离轨迹的不合理的采样点。这些异常点的存在严重降低了轨迹数据的质量，同时引起后续轨迹知识发现结果的不准确，例如轨迹压缩[3]、轨迹聚类[4]、路径规划[5]、异常模式检测[6]和航迹关联分析[7-8]。因此，对轨迹异常点的检测是十分必要的。

目前应用最广泛的轨迹异常点检测算法为恒定阈值法，尤其是速度阈值法[9]。当与前一个点计算得到的当前定位点的即时速度超出设定阈值时，采样点被标记为异常点并被剔除。这种方法主要存在以下问题：1)对于大部分的轨迹数据，用户难以找到一个准确的阈值；2)移动目标的运动状态在不同情况下不可能是完全相同的，采用恒定的阈值有明显的不足；3)只考虑前一个点的信息来检测异常点，有可能导致正常点被误判为异常值。

针对上述方法存在的问题，本文提出一种基于自适应阈值的轨迹异常点检测算法(Trajectory Outlier Detection Algorithm based on adaptive Threshold, TODAT)。算法考虑相邻一段时间内船舶的运动状态和数据中噪声的影响，分别采用局部阈值窗和均值滤波窗来计算阈值和速度。通过分析实际的实验数据，本文还引入了经济航速阈值和连续异常点放回机制。TODAT能够根据船舶整条轨迹和轨迹段上的运动信息自动得到自适应的合理的阈值。实验结果表明TODAT算法可以实时检测船舶轨迹数据中的异常点。

1 相关工作

Hawkins在1980年对异常点提出的正式定义为：异常点是指在数据集中显著偏离其它绝大部分数据的那些数据对象，以至于引起人们怀疑它们是由完全不同的机制产生的[10]。异常点检测算法在国内外都得到了广泛的研究，主要分为以下4类[11]。

1)基于统计的方法。假设正常的数据是由一个统计模型产生，而不遵守该模型的数据是异常点。该方法的有效性高度依赖于数据的分布假设是否成立。

2)基于距离的方法。Knorr等人[12]提出了经典的DB(p, D)算法，如果数据集中至少有p部分数据对象与对象o的距离大于D，则o是一个基于距离的关于参数p和D的异常点。该方法需要恰当的距离度量，不能检测出具有不同密度分布数据中的局部异常点。

3)基于密度的方法。该方法假设异常点周围的密度显著不同于其邻域周围的密度。Breunig等人[13]已经提出了局部异常因子(LOF)算法，根据邻域中全部点的局部可达密度计算出每一个点的LOF值，高LOF值的点为异常点。该算法可以检测出全局异常点和局部异常点。

4)基于分类的方法。训练一个可以区分正常数据和异常点的分类模型，用预先训练好的模型来判断新的观测点是否异常。该方法依赖于已标注的训练数据集。

轨迹数据是基于时间和空间的位置序列，传统的检测方法不能直接用于检测轨迹数据中的异常点。针对轨迹数据，Chen等人[5]、Alvares等人[14]和Zheng等人[15]采用恒定阈值法来检测异常值，剔除即时速度超出设置阈值的轨迹点后再进行各自的轨迹数据挖掘任务。Zhang等人[16]提出了TODMF算法，算法在基于距离的检测方法上改进，组合速度、加速度和转角等多个因素来检测轨迹异常点。Chen等人[17]提出了一种基于模型的GPS轨迹清理算法来检测低成本GPS轨迹上的异常值，采用3次平滑样条和时间序列方法对轨迹的趋势进行自适应建模。上述方法主要针对GPS轨迹上的应用，但是不适用于由多种定位手段得到的船舶轨迹数据。不同于GPS高达米级的定位精度，船舶多种来源的轨迹数据的精度均较低，且定位精度和轨迹采样率差异较大。本文将针对多种探测手段获取的船舶轨迹数据，研究基于自适应阈值的异常点检测方法。

2 算 法

本文提出的TODAT算法针对船舶航迹数据。船舶的航迹由一系列时空数据点(即经度、纬度和时间)组成，通常由多种定位手段获得。由于不同数据源定位误差的差异、环境干扰和人为操作失误，船舶轨迹数据中存在大量不符合目标运动规律的异常点。船舶的原始航迹如图1所示，数据中有许多严重偏离航迹的异常点。轨迹异常点检测是数据处理应用前最重要的一步。

TODAT算法的核心思想是：在短时间内船舶的运动状态相似，即速度、加速度不会发生突变。算法依次计算当前时刻的阈值和当前点的即时速度，速度超出阈值则判定为异常点。根据具体的数据情况，算法设定了一系列的参数规则：1)由局部阈值窗或经济航速阈值规则得到对应的自适应阈值；2)采取均值滤波窗来降低噪声对检测结果的影响；3)采用连续异常点放回机制降低误检率。

(a) 轨迹1 (b) 轨迹2图1 船舶的原始轨迹

2.1 局部阈值窗

考虑到待检测点的运动状态与相邻一段航迹的运动状态有很大关系，算法引入局部阈值滑动窗口。局部阈值窗内放置当前点之前的一连串已经判定的正确点。通过对轨迹数据的观察分析，本文设定了窗口时长和点数的限制条件(见3.1节表1)。当限制条件满足时，本文选择由窗口内点计算得到的局部阈值，否则，选用由整段轨迹信息计算得到的全局阈值。对于目标以平稳速度行驶一段航迹后速度突然增大很多的异常点，采用局部阈值窗可以有效检测出。

(1)

(2)

2.2 均值滤波窗

轨迹数据中每个点都是存在着噪声的。为了减少噪声对异常点检测的影响，本文采用均值滤波滑动窗口。均值滤波窗内同样放置了已检测的一系列的好点，但是根据数据情况本文选取了不同的点数和时长设置(见3.1节表1)。

均值滤波是典型的线性滤波算法，通常用于去除图像和信号中的噪声[19]。本文计算均值滤波窗内全部点的经度、纬度和时间的平均值作为一个滤波新点Pf。滤波窗的限制条件符合时选择滤波新点，否则选择前一个点为参照点Pr来计算当前点的即时速度。当前点Pi的速度计算公式为：

vi=dist(Pi,Pr)/(ti-tr)

(3)

其中，dist(Pi,Pr)表示点Pi和Pr之间的距离，ti、tr分别表示2点的时间。滤波窗可以有效提高参照点的精度，保留速度微小波动的点，从而降低误检率。

当前点Pi被判定为异常点当速度vi超出了速度阈值vth即vi>vth成立。算法中，局部阈值窗决定了阈值的选取，均值滤波窗则用来选择参照点和即时速度的计算。检测算法示意图如图2所示，目标点Pi为检测出的异常点。

图2 算法示意图

2.3 算法流程

船舶行驶中，经常会出现长时间没有采集到轨迹点的情况，前后2点间隔时长非常大。本文假设船舶此时是以经济航速[20]行进的，即每海里燃油消耗量可以达到最少值。算法在2点间隔时长超出设定时间时，采用经济航速阈值。与2.1节中阈值公式设计相同，经济航速阈值计算公式如下：

(4)

其中，Vemin、Vemax分别为速度阈值下界和上界，Mve为经济航速倍数。经济航速阈值可以使算法检测出2点间隔时间非常大情况下的异常点，降低漏检率。

通过观察数据发现，数据中不会出现连续多个异常点的情况。本文采取连续异常点放回规则，如果连续异常点个数超过设定值且首尾时间在设定范围内，则重新判定这些点为正常点。该规则可以避免将速度微小波动的点错判为异常点，减少算法中各参数的调整，提高阈值的自适应性。

本文对轨迹点的加速度属性作了同样的处理，点Pi的加速度计算公式为：

ai=(vi-vi-1)/(ti-ti-1)

(5)

与公式(1)、公式(2)类似，由整条轨迹和局部窗口轨迹的点分别得到全局加速度阈值agth和局部加速度阈值alth，当采样点的速度和加速度都超过对应阈值时，采样点被检测为异常点。

算法的流程如图3所示。

图3 TODAT算法流程图

3 实验结果分析

3.1 实验设置

本文采用一个真实的船舶轨迹数据集来验证算法的有效性。该数据集记录了100艘船舶一个月的实时航迹，包含有超过2000条轨迹和百万个轨迹点。本文实验的运行环境为Intel Core i7-6700 3.4 GHz、内存为8 GB的PC，算法由Python实现。

表1 算法中参数值的设置

参数名称值速度阈值下界15节速度阈值上界40节全局速度倍数5局部速度倍数7加速度阈值下界0.5 m/s2加速度阈值上界15 m/s2全局加速度倍数5局部加速度倍数7经济航速间隔时长90 min经济航速倍数3参数名称值阈值窗的最小点数7阈值窗的最大点数31阈值窗的最小时长20 s阈值窗的最大时长5 min均值滤波窗的点数11均值滤波窗的时长11 min连续异常点个数7连续异常点时长80 min经济航速阈值下界10节经济航速阈值上界30节

TODAT算法中各个参数和其预设的值如表1所示。其中，速度、加速度和经济航速阈值上下界的设定是为了保证速度全局阈值、加速度全局阈值和经济航速阈值的有效性，避免由轨迹点直接计算得到的阈值过大或过小引发漏检或错检。参照3准则[18]，阈值应设为均值加上一定倍数的标准差，本文通过对船舶运动数据的统计与分析，确定了全局速度、局部速度、全局加速度、局部加速度和经济航速的标准差倍数。为了更加贴近实际情况，本文进一步考虑了目标在一段时间内的运动信息，设置了局部阈值窗的最小点数、最大点数、最小时长和最大时长的限制条件，在此条件下计算对应的局部阈值。均值滤波窗点数和时长的设置是为了判定滤波窗是否起作用，当点数时长条件符合时，算法采用滤波新点来计算即时速度。当2个点的时间间隔过长，采用局部阈值是不合理的，因此本文设置了经济航速间隔时长，在2点间隔超过经济航速间隔时长时，算法将采用经济航速阈值。最后，本文设置了连续异常点个数和时长，以此判断是否采用连续点放回机制。

所有这些参数的设置取值都是为了尽可能采样到较多的影响当前点检测的有价值信息，获得自适应的阈值，从而使得检测结果更准确。根据船舶固有的最高速度为15～32节(7.72～16.46 m/s)[21]和数据集上的速度分析，本文在数据集上测试调整了各个参数的取值，最终选取了检测效果最符合船舶运动状态的一组参数值。

3.2 实验结果

3.2.1 可视化效果分析

本文算法在船舶数据集上检测出3种类型的异常点，包括孤立异常点、连续异常点和明显判识异常点，其可视化结果如图4所示，异常点用三角形标记出。图4(a)为检测出的孤立异常点，算法通过局部阈值可以有效检测出平稳轨迹中的速度波动的异常点。图4(b)中，算法识别出了连续的5个异常点，这5个点明显偏离了船的航迹，速度与其余点的速度值相差较大。由图4(c)可见，左侧一段航迹与右侧船航迹显著不同，2段轨迹其实是2艘船的，但在数据收集过程中被判识成一个运动对象，异常由判识错误引起。

(a) 孤立异常点

(b) 连续异常点

(c) 明显判识异常点图4 检测出的异常点类型

图1中2条轨迹原图在检测并去除异常点后的轨迹图如图5所示。为了直观地体现TODAT算法的有效性，图6给出了更多的检测前和剔除异常点后的轨迹对比。从这些图中可以明显观察出，检测后的轨迹更为平滑，符合船舶的运动情况，算法有效检测出了原始轨迹中的偏离航迹的不合理的异常点。船舶的轨迹数据只有在检测完异常点之后，才可以用来做后续的处理和知识挖掘工作。

(a) 轨迹1 (b) 轨迹2图5 图1中剔除异常点后的轨迹

(a) 检测前 (b) 检测后图6 原始轨迹与检测后轨迹对比图

3.2.2 检测结果对比与分析

为验证本文算法的有效性与合理性，本文抽取100条船舶轨迹，24295个航迹点作为实验数据集，并将本文提出的算法与恒定速度阈值法进行对比。通过对数据集中船舶运动状态的统计和分析，本文将恒定速度阈值设为20 m/s，并根据每个轨迹点与前一个已判定的正常点来计算即时速度，速度超过恒定速度阈值则被标记为异常点。

图7给出了TODAT算法与恒定速度阈值法在3段轨迹上检测结果的对比图。图7(a)为本文算法检测结果，正常点用圆点表示，异常点用三角形表示；图7(b)为恒定速度阈值法的检测结果，其中菱形标记为检测出的异常点。从第1幅图中可以看出，恒定阈值法未能将明显的孤立异常点检测出来，该点速度为15.58 m/s，远远超出了其邻近点3～5 m/s的速度值，而TODAT算法能够很好地检测出孤立的异常点。这是因为TODAT算法能够根据移动目标的运动状态得到自适应的阈值。从第2、第3幅图中可以看出，恒定速度阈值法不仅没检测出正确的异常点，反而将较多的正常点错判为异常点，而TODAT能够对异常点进行正确的判别，且没有对正常点的错判。其原因是位置明显波动的异常点速度没有超出根据船舶最大运动能力设定的恒定速度阈值而被错判，而在此之后的轨迹点根据这些错判点计算的即时速度超出了恒定速度阈值，进而引发漏检和错检。而TODAT算法则能根据数据得到自适应的合理的阈值，从而得到更准确的检测结果。

(a) TODAT算法 (b) 恒定速度阈值法图7 轨迹异常点检测结果对比图

实验结果表明，TODAT算法检测出851个异常点(所有异常点均检测出来)；而恒定速度阈值法检测出的异常点共833个，其中还包含了一些错判的正常点。原始轨迹和TODAT算法、恒定速度阈值算法检测后轨迹各个点的速度分布直方图分别如图8所示，图中的横纵坐标轴均为对数刻度，每个点速度按前一个点来计算。

(a) 原始轨迹

(b) TODAT算法

(c) 恒定速度阈值算法图8 速度直方图对比

由图8和统计结果可知，船舶的速度主要集中在1.5～10 m/s范围内，TODAT算法有效检测出了速度超出绝大部分20 m/s的异常点，共有693个点；与此同时，算法也检测出来158个与相邻点运动状态波动较大的异常点。而恒定速度阈值算法只是简单地将速度为20 m/s以上的点判为异常点，这样极易引发漏检和错检。可视化结果和速度直方图对比图均表明，本文TODAT算法可根据不同的数据实时得到自适应的阈值，相比于恒定速度阈值法得到更准确的检测结果，非常适用于舰船轨迹数据中异常点的实时检测。

4 结束语

本文提出一种基于自适应阈值的轨迹异常点检测算法TODAT。算法能够根据船舶整条轨迹和轨迹段上的数据，采用局部阈值窗、均值滤波窗和设定参数规则来得到自适应的阈值，实现对船舶轨迹数据实时的异常点检测。实验结果表明本文算法能够有效检测出明显偏离航迹、速度波动较大的不合理的轨迹点，大幅度提高轨迹数据的质量，为后续数据处理和知识发现提供保障。在下一步工作中，将在该算法的基础上，提取轨迹数据的特征，引入机器学习分类方法，实现船舶数据点是否异常的自动分类。