采用编码降维及DTW算法改进的船舶航迹聚类

曹伟，刘亚帅，管志强

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

0 引言

在船舶航迹异常检测研究中，部分异常船舶会伪装在正常航道中航行，从航迹位置信息无法检测该类异常，需要通过对这类异常船舶的异常机动进行检测来检测异常。而检测这种异常机动，需要首先提取正常船舶航迹在时间维度上的各点的航行状态，然后在时间维度上对比检测。这种时间维度上的航行状态特性就是航迹时序特性。

由于传统船舶航道聚类多基于密度聚类算法，例如Pallotta G等人[1]采用DBSCAN (density-based spatial clustering of applications with noise)算法实现航道聚类，这些算法只能挖掘出航道的位置信息，无法提取船舶航迹的时序特性。所以为了提取出船舶航迹的时序特性，本文采用时间序列聚类的方法对航迹进行聚类。时间序列聚类算法的关键点在于时间序列的相似性度量。由于船舶航迹时间序列是不等长的，为了度量该类时间序列，本文采用了Berndt等人[2-3]于1994年提出了DTW算法。

虽然DTW算法可以实现不等长时间序列的度量，但是在海量船舶航迹时间序列上使用DTW算法存在2个问题：①DTW算法主要适用于一元时间序列(univariate time series,UTS)[4]，对于多元时间序列(multivariate time series,MTS)[4]只有属性之间相关性较低时才能有效度量，否则很容易失去属性之间的相关性。而船舶航迹时间序列中的经纬度相关性很高，无法有效应用DTW算法实现相似性度量;②DTW时间复杂度高达O(n2)，虽然近年来不少学者提出了许多改进方法，比如LB_Keogh下界函数[5]，微分动态弯曲距离(derived dynamic time waping,DDTW)[6-7]，加权动态弯曲距离(weighted dynamic time warping,WDTW)以及加权微分动态弯曲距离(weighted derived dynamic time warping,WDDTW)[8-9]，添加窗口的DTW距离[10-11]等，但是这些算法都只从DTW的路径搜索空间进行改进，在点迹数很高的海量时间序列背景下，依然无法满足计算效率的要求。

所以针对二维船舶航迹时间序列应用DTW算法度量容易丢失属性之间相关性的问题，本文采用降维编码的方法在不丢失经纬度相关性的前提下，将二维航迹时间序列转化为一维航迹时间序列。同时，针对传统DTW改进算法在点迹数很高的海量数据背景下计算效率依然无法满足要求的问题，本文分别从最小粒度压缩角度和聚类度量搜索角度对DTW算法进行了改进，实验结果表明该改进实现了对DTW算法计算效率的提升。

1 船舶航道聚类系统架构

本文设计的聚类算法的架构如图1所示。

由于从数据库抽取的原始数据中包含有噪声数据，所以需要对原始数据先进行数据清洗，去除噪声数据；处理后的船舶航迹数据由于存在停泊断点和时间断点，并不是连续的时间序列，为了后续聚类的航道是连续的，本文通过对同一MMSI (maritime mobile service Identity)[12]号下的船舶航迹时间序列进行切割，将其切割成连续的航迹时间序列。之后应用改进的DTW算法对切割后的时间序列进行聚类，最后通过可视化方法进行判决。

2 编码降维及DTW算法改进

由于船舶航迹时间序列中经纬度属性之间相关性很高，如果将属性分开进行DTW度量，会造成属性之间经纬度相关性的丢失，所以本文提出了一种编码降维的方法，在不丢失相关性的前提下，将航迹二维时间序列转化为一维时间序列。之后在进行DTW度量中，由于单条航迹点迹数较高，航迹数量大，传统DTW改进算法依然无法满足计算效率的要求，所以为了提高计算效率，本文根据船舶航迹时间序列特点从最小粒度压缩角度和聚类搜索角度对DTW算法进行了改进，从而提高了计算效率。具体算法改进如下所述。

图1 聚类算法架构图Fig.1 Clustering algorithm architecture diagram

2.1 编码降维

在进行DTW度量时，由于船舶航迹时间序列是一个经纬度时间序列，其经纬度的相关性很高，如果拆开分别进行DTW度量很容易丢失经纬度的相关性。所以为了能够应用DTW算法对船舶航迹时间序列进行有效的相似性度量，本文提出了一种编码降维的方法将二维的船舶航迹时间序列转换成一维船舶航迹编码时间序列。

具体方法如图2所示，首先将研究区域依据经纬度值按照如图2所示方法进行切割，将原始区域切割为9个区域，对落入各个区域的航迹点分别编码为1～9；之后分别对这9个区域再次应用图2的方法进行切割，则此时对落入每个格子中的航迹点的编码为CU×10+CN，其中CU为航迹点的上一级编码值(例如图3所示，第1次的CU值是9，第2次的CU值是99)，CN的值为1～9，表示每次9个格子中的第几个。编码后的序列如定义1。

图2 相关编码Fig.2 Relevant coding

图3 总体编码过程Fig.3 Overall coding process

定义1：船舶航迹编码时间序列

S={Coding(i)∈R:i=1,2,…,m},

(1)

式中：S为预处理中切割出来的连续的航迹时间序列；Coding为船舶航迹时间序列S中的每个航迹点的编码值，是一个长度为m的一元时间序列。

根据相关编码的原理可以看出，在地理上相近的点，其编码值相差较小，说明编码后的船舶航迹编码序列既实现了降维，又将原始船舶航迹时间序列中经纬度的相关性转化为编码值的大小了。

2.2 最小粒度压缩改进DTW算法

标准DTW算法[13]的核心思想为

D(i,j)=Dist(i,j)+min[D(i-1,j),
D(i,j-1),D(i-1,j-1)]，

(2)

式中：D(i，j)表示长度i和j的2个时间序列X，Y之间的归整路径距离；Dist(i，j)表示X序列第i个点与Y序列第j个点之间的距离。

想求D(i，j)，需要先求出D(i-1，j)，D(i-1，j-1)，D(i，j-1)，依此类推，直到遍历整个序列，所以DTW算法的时间复杂度为O(N2)。

可见DTW算法的计算效率主要与以下2点有关：①时间序列的点迹数量N值；②D的搜索空间的大小。所以本文通过从这2个方面对DTW算法进行了改进(如图4所示)。

针对船舶时间序列点迹N较大的问题，采用最小粒度压缩方法(如图5所示)将网格中的点迹压缩成一点，从而将N点的航迹压缩成M点(N≫M)的航迹，从而实现对DTW算法的改进。

图4 DTW算法改进Fig.4 DTW algorithm improvement

图5 最小粒度压缩Fig.5 Minimum granularity compression

之后采用编码降维后，为了从DTW算法D搜索空间进行改进，本文采用如下方法进行处理：

(1) 进行粗粒度化，将多个细粒度的数据点以平均值形式抽象成为一个点，从而形成一个较粗粒度的序列。具体的方法采用的是PAA(piecewise aggregate approximation)方法[14-15]。

(2) 采用细粒化搜索循环，直到达到最小粒度为止。其中投影是指当前搜索区域下进行DTW运算，而细粒化是指在投影中产生的归整路径进一步细化到较细粒度上，同时为了避免粗粒度造成的路径偏差，在细化后的路径空间外延伸R个格子作为下一次D搜索空间，如图6为细粒化搜索过程。

图6 细粒化搜索过程Fig.6 Fine-grained searching process

2.3 聚类搜索改进DTW算法

传统时间序列聚类算法会将所有序列之间都进行度量，包括类内和类间的，这实际上会增加大量的时间开销。所以本文针对航迹类别间差异较大的特点，采用如图7所示的搜索流程对DTW算法进行改进，提升计算效率。

图7 搜索改进Fig.7 Search improvement

假设第1次选取S1作为种子航迹，依次与其他航迹进行相似性度量，再假设度量结果显示{S2,S3,…,Sn}与S1之间的相似性度量值D1y都小于聚类阈值ThD，则认为{S1,S2,…,Sn}聚集为一类，则将{S1,S2,…,Sn}从原始数据集中删除，之后选取Sn+1作为种子航迹与删除后的数据集中的数据进行相似性度量，依次类推聚类下去。

3 实验结果分析

3.1 实验环境与数据来源

本文前期数据预处理过程采用R语言实现，其硬件平台为Window7×64位系统，内存为24.0 GB，处理器为Intel(R) Core(TM) i7-4770KCPU@3.50 GH，软件平台为R-3.4.3版本。使用的是XX雷达基站采集的XX海域的近1个月28.8 GB的AIS数据。聚类及可视化判决是基于Python语言实现，其硬件平台为Window8.1×64位系统，内存为4 GB，处理器为Intel(R) Core(TM) i3-3120M CPU @ 2.50 GH，软件平台为Python-3.6.4版本。

3.2 航迹时间序列聚类实验分析

3.2.1 最小粒度压缩效果分析

最小粒度压缩效果如表1所示。

表1 压缩效果表Table 1 Table of compression effect

本文采用的是0.02°×0.02°的最小粒度网格进行压缩。由于原始数据量太大，本文按照时间将其分割成3个数据集处理。由表1可见，3次压缩效果都是在200倍左右，说明最小粒度压缩方法对每条航迹都平均压缩了200倍，使得DTW计算时间降低了2002倍。

3.2.2 航迹聚类时间分析

如图8所示，是本文在不同阈值(ThD)下的聚类的时间开销折线图。

图8 ThD与聚类时间的关系折线图Fig.8 ThD and clustering time line chart

随着ThD的增加，聚类时间总体上呈现逐渐降低的趋势，这是由于随着阈值的增加，聚类越来越充分，同一类中聚集航迹数增多，聚集形成的类增多，所以根据DTW搜索改进思路，需要进行相似性度量的次数就减少了，从而降低了计算时间开销。

3.2.3 航迹聚类结果分析

如表2所示是实验中不同ThD下的聚类的总数、正常聚类航道及航道真伪比的统计值。

表2 聚类结果记录Table 2 Report of clustering result

可以看出当ThD<1 000时，随着ThD的增加，聚类效果越来越充分，无论从总体的聚类数还是正常的航道数都在增加；当ThD到达1 000时，聚类最充分，此时正常航道数最多，真伪比最大；当ThD>1 000时，由于阈值太大，大量的伪航道开始聚集，此时正常航道间也发生了多个类的融合，所以虽然聚类总数在增加，但是正常航道却在急剧减少，伪航道大量产生。由此可见最佳的ThD值应当在1 000左右，此时聚类最充分，聚类效果最好。

本文提出的基于改进DTW的聚类算法，由于聚类本身就是基于时间序列的，所以实际上聚类形成的航道本身就具有时序性。

如图9所示是Pallotta G等人[1]采用DBSCAN算法实现的聚类效果图，可以看出采用DBSCAN算法聚类结果只有位置信息，没有方向信息，也没有时序信息。图10是本文在ThD=1000时，聚类得到的部分航道效果图，其中图10b)是航道中的2条正常航道效果图，这2条航道经纬度位置相近，只是方向不同(图b_1航道方向为右上至左下，即●表示序列起始位置，▲表示序列终止位置；图b_2航道方向为左下至右上)，而这个方向就是时序性，已知任何一点的航行状态，可以通过这个航道方向知道其前后任何点的航行状态。

图9 DBSCAN算法聚类效果Fig.9 DBSCAN algorithm clustering effect chart

图10 航道效果对比图Fig.10 Channel comparison chart

4 结束语

本文针对船舶航迹异常检测中需要提取航迹时序特性的问题，采用基于编码降维及改进的DTW算法实现了船舶航迹聚类，有效提取出正常航道的时序特性，为后续异常检测研究提高了先验知识，同时该算法也为需要时序特性的路径研究提供了一种算法支持。在该算法中从最小粒度压缩角度和度量搜索角度改进后的DTW算法有效提高了相似性度量过程的计算效率，基本满足了聚类度量要求对计算效率的要求，为大点迹量的海量不等长时间序列的相似性度量提供了一种算法支持；为了满足DTW度量的条件，算法提出的编码降维方法既完整保留了原始数据的地理相关性，又将地理数据实现了降维，其为地理数据的降维提供了一种新的思路。虽然本文提出的聚类算法实现了提取航迹的时间序列特性，但是由于算法本身对于路径的规整度依赖较高，对于不规整路径聚类效果不好，需要进一步改进。