基于行为特征相似度的船舶轨迹聚类方法*

张春玮 马 杰 牛元淼 刘 琪

(武汉理工大学航运学院1) 武汉 430063) (湖北省内河航运技术重点实验室2) 武汉 430063) (国家水运安全工程技术研究中心3) 武汉 430063)

0 引 言

船舶轨迹是表现船舶运动的最直观形式，海量的轨迹数据中蕴藏了丰富的交通特征规律和船舶运动模式等信息.对船舶轨迹数据进行聚类分析，可为船舶交通流特征提取、航路安全规划和推荐、船舶异常行为检测等技术研发和应用提供基础手段和关键方法，为航运规划、海事监管等工作开展提供决策支持和科学依据[1].

船舶AIS系统已成为当前船舶交通监控和管理的重要工具，利用AIS数据可提取船舶航行的多个维度信息，即可得到船舶轨迹连续移动位置点，又可获取不同位置点上的速度、航向等船舶运动状态参量.因此，AIS数据非常适于船舶轨迹聚类分析[2]、船舶行为模式挖掘等相关研究[3].

目前，利用AIS数据进行船舶轨迹聚类研究主要有两种模式：基于轨迹点的聚类和基于轨迹段的聚类.轨迹点聚类以目标对象运动的位置散点(如经纬度坐标值)为聚类样本进行簇群划分，进而研究目标轨迹特征或运动模式.Liu等[4]结合国际海事组织IMO相关规定对船舶AIS航迹点进行聚类，提取船舶的主航迹.Yan等[5]对航迹点分类，划分为在航和抛锚两种行为状态，并对主航路路径选取和锚地选址等问题进行了讨论.基于轨迹点的聚类忽略了同一船舶轨迹上相邻点间的时空关联特性，对船舶整体运动特征的刻画能力有限.基于轨迹段的聚类将连续位置点形成的轨迹整体或轨迹片段作为聚类对象，建立轨迹整体或片段之间的相似性度量，进而采用各种聚类方法实现簇群划分，聚类结果能较好地描述不同形式和类别的轨迹运动模式.相比于轨迹点聚类，轨迹段聚类更适合研究船舶行为模式.Lee[6]等最先提出基于轨迹片段的聚类方法，通过对轨迹片段外形、夹角等进行线性化处理来定义相似度，设计了一种层次化轨迹聚类算法.魏照坤等[7-8]采用类似手段实现了对船舶AIS轨迹线性化分片和聚类.基于分片的轨迹聚类存在分片标准难以确定、分片不当影响聚类效果，以及计算过程复杂等问题[9].特别是针对船舶运动具有惯性大、航向，以及航速变化慢等特点，将一定区域内的船舶轨迹看成整体进行聚类可以更有效的区分船舶轨迹模式.Li等[10]以船舶AIS轨迹整体为聚类对象，建立轨迹之间的空间位置距离矩阵进而实现不同空间分布和方向上的轨迹簇划分.然而，其相似度计算仅考虑了轨迹的经纬度位置采样值，没有考虑各位置点上的航向、航速等船舶运动状态信息.船舶位置、航向及航速是体现船舶行为规律的重要指标，共同构成了船舶行为特征量.如何利用这些行为特征量，建立船舶轨迹相似度并进行聚类分析是本文的重点.

1 船舶行为特征相似度建模

2004年IMO规定：国际航线总吨位超过300 t，非国际航线中超过500 t的货船及所有客船都需要安装AIS发送设备.AIS信息记录了船舶唯一标识(MMSI)、船长和船宽等的静态信息,以及船舶瞬时位置、航速、航向等动态信息[11].本文以AIS数据作为研究对象，首先对选定研究区域的AIS数据进行预处理，依照MMSI号提取各个船舶对应的轨迹点数据并按时间排序，对残缺严重和噪声点过多的轨迹进行滤除.

为了比较两艘船舶连续行为的相似度，从船舶AIS轨迹数据中提取经度Lat、纬度Lng、航向Cog及航速Sog等采样值，构成船舶行为特征向量，则一条船舶轨迹可以用点序列表示为traj{x1,x2,...,xN}，其中N为该轨迹的长度，即该轨迹由N个采样点组成，每一个采样点由4维度的行为特征向量表示，xi=Lati,Lngi,Cogi,Sogi,i=1,2,…,N.通常情况下，不同船舶即使在同一航路上行驶，其经过的轨迹点也不可能完全一致，并且各个船舶的AIS数据采样时间也不同步.因此，船舶的轨迹序列长度一般是不等长的，这给轨迹之间的相似度计算带来困难，传统针对等长序列采用欧式距离计算相似度的方式就无法适用.针对这一问题，拟采用动态时间规整算法(dynamic time warping，DTW)[12]来计算船舶轨迹序列之间的相似度.该方法通过对序列进行压缩、拉伸变换和配对，有效解决了非等长序列之间相似度计算的问题.基于DTW的船舶轨迹序列相似度具体计算过程如下.

设长度分别为P和Q的两条轨迹序列：traja={a1,a2,…,aP}和trajb={b1,b2,…,bQ}，P≠Q.对轨迹序列a和b进行配对，构建P×Q维的路径矩阵，矩阵元素d(ai,bj)通过计算轨迹点上行为特征向量ai(i=1,2,…,P)和bj(j=1,2,…,Q)之间的相似度距离得到.假设路径矩阵中存在一条路径，同时满足：①该路径能遍历轨迹a、b上的所有点；②路径按一定方向连续移动生成；③该路径上经过的元素累计相似度最小，则该路径称作最相似规整路径(Warping Path)，记作W：

W={w1,w2,…,wK}max(P,Q)≤K≤P+Q-1

(1)

式中：路径元素wk(ai,bj)为轨迹序列a和b的配对关系；规整路径W必须从轨迹点a1和b1开始，终止于aP和bQ；对于路径上前后两点wk-1(ai′,bj′)和wk(ai,bj)需满足0≤i-i′≤1，0≤j-j′≤1；计算路径W上累计相似度D(ai,bj)，从路径矩阵的初始点(a1,b1)开始匹配序列a和b，每到一个点，之前所有点计算的相似度距离值都会累加，到达终点(aP,bQ)后，这个累积距离就是序列a和b的相似度.采用动态规划的思想，该累积计算过程为

D(ai,bj)=d(ai,bj)+ min{D(ai-1,bj),D(ai,bj-1),D(ai-1,bj-1)}

(2)

即累积距离D(ai,bj)为路径矩阵中当前元素格点距离d(ai,bj)与可以到达该点的最小的邻近元素的累积距离之和.

如前所述，式(2)中的距离d(ai,bj)即路径矩阵元素，代表不同轨迹点所对应行为特征向量之间的相似度.考虑船舶行为在空间上具有关联特性，如船舶在某些特定的位置点上可能具有相似的速度和转向，因此，综合考虑船舶位置、速度及航向等行为要素的相互关系，通过归一化加权求和的方式度量轨迹之间的行为相似性.

以南北和东西方向为轴建立船舶运动参考坐标系，见图1.

考虑船舶轨迹a和b上的两个采样点ai和bj，各自对应的行为特征向量分别表示为

d(ai,bj)=w1V⊥+w2V∥+w3d⊥+w4d∥

(3)

式中：归一化权重需满足条件：wi≥0,i=1,2,3,4 且 ∑wi=1.权重的分配可以根据不同水域船舶航线分布特点进行确定.

2 基于行为相似度的轨迹聚类

通过船舶行为特征相似度建模，船舶轨迹两两之间的相似性计算不仅考虑了轨迹空间分布与形态上的差异，同时也考虑了不同轨迹所蕴含的船舶运动特征，为船舶轨迹聚类提供了更为全面的信息.拟采用DBSCAN(density-based spatial clustering of applications with noise)算法对船舶轨迹实现聚类.该算法是一种基于密度的无监督聚类算法，其优势是对噪声数据不敏感，能够发现任意形状和大小的簇，并且无须事先设定簇个数，非常适合船舶AIS轨迹数据噪声点多，轨迹模式不确定性高等情况下的聚类.

DBSCAN算法主要涉及两个参数：邻域ε(eps)和高密度区域形成所需要的最少点数minPts.轨迹聚类算法由轨迹集T中任意一个未被访问的样本点开始，在T中探索这个点的ε-邻域，即Neps(p)={q∈T|D(p,q)≤eps}，如果ε-邻域里有足够的点，即|Neps(p)|≥minPts，则建立一个新的聚类，否则这个点被标签为异常点(该点之后可能被发现在其它点的ε-邻域里而加入其聚类中).如果一个点位于一个聚类的密集区域里，它的ε-邻域里的点也加入该聚类，如果这些新加入聚类的点也在密集区域里，则它们的ε-邻域里的点也会被加进聚类里.此过程将一直重复，直至不能再加进更多的点为止，这样，一个密度连结的聚类被完整地找出来.然后，轨迹集T中一个未曾被访问的点将继续被探索，从而发现一个新的聚类或异常(无法被聚类的样本点).将DBSCAN应用于船舶轨迹聚类，参数eps反映了不同轨迹聚成一类需满足的最低相似程度，而minPts刻画了不同轨迹聚成一类需满足的最少数量，轨迹之间相似度D(p,q)可由式(2)计算得到，聚类结果不但可以区分不同的轨迹模式，聚类完成所产生异常点还可用来筛选异常轨迹.

3 实验与分析

长江南北槽水道位于铜沙浅滩与九段沙之间，是进出长江口的关键枢纽，对该区域船舶轨迹进行研究具有重要意义.以南槽段2017年2月的AIS数据作为数据集(见图2)，从南槽西至东方向的直行轨迹和西至北方向的上行轨迹中各选取50条，共10 148条AIS信息进行算法验证.

图2 长江口南槽段电子海图

聚类实验分两组进行以对比算法效果.一组只考虑轨迹之间的空间位置相似度，即在相似度计算式(2)中的权重设置为：w1=w2=0，w3=w4=0.5；另一组相似度计算不仅考虑轨迹空间距离，同时还引入速度及航向等行为特征量，即权重设置为：wi=0.5(i=1,2,3,4).两组实验的邻域都设置为0.5，密度阈值minPts设为5.两组实验的轨迹聚类结果见图3～4.

图3 基于空间位置相似度轨迹聚类

图4 基于行为特征相似度轨迹聚类

由图3可知，在只考虑空间位置相似度进行轨迹聚类时，聚类算法可以有效的将两个不同方向上的轨迹划分成不同的簇，即图中上行轨迹的实线条和代表直行轨迹的浅色虚线条.同时，算法还输出了一条异常轨迹，由图中深色虚线表示，可以看到该异常轨迹在空间上明显偏离两个方向的轨迹簇，代表一种航线偏离异常.

图4为引入行为特征相似度的轨迹聚类效果，与图3的结果对比可知，聚类后轨迹簇由两类变成三类，图中浅色虚线条所代表直行轨迹簇没有明显变化，而上行轨迹簇被划分为两类，即图中箭头“类别二”和“类别三”所指向的部分，新产生的轨迹簇“类别三”由点线条标识.同时，算法输出的异常轨迹由原来的一条变成三条，除了之前西东方向的一条航线偏离异常轨迹，在西北上行方向上多出两条异常轨迹，图中仍由深色虚线表示.两条新增的异常轨迹在空间位置分布上与其他各轨迹簇并无明显的偏离或差异，因此在只考虑空间位置相似度进行轨迹聚类时，这两条轨迹未能判别为异常.实际上，两条异常轨迹虽然与其他轨迹簇在空间轨迹点分布上存在重叠的情况，但它们都出现大角度横跨航路的情况.这种情况通常也是海上交通中的一种异常，引入行为相似度的轨迹聚类能有效识别这种异常情况.

进一步对聚类结果“类别二”和“类别三”进行分析.从空间轨迹点分布上看，两类轨迹有较高的相似性很难区分，因此仅考虑空间位置相似度的聚类将两类轨迹判别为同一簇.但仔细观察两类轨迹走势，可以发现“类别三”主要分布在航线的东侧，且由西东向变为西北向时，其转向角度普遍大于“类别二”.采用柱状频率统计与高斯拟合方法对两类轨迹的速度分布作进一步统计分析，图5给出了统计结果.其中，“类别二”轨迹簇的航速近似于高斯分布，其速度均值约为9 kn；而“类别三”轨迹簇在速度分布上出现双峰的情况，与“类别二”相比在分布形态上出现了明显差异.这实际反映了西北向行驶过程中“类别三”轨迹相比“类别二”轨迹转向较大，因转向较大、过晚导致有偏离航线偏离的趋势，“类别三”船舶为及时修正航向在后半段速度由10 kn加速至13 kn，故产生双峰的特征.因此，在引入航速、航向等行为特征后，聚类算法能更为细致的对轨迹进行分类，发现新的船舶运动模式.

图5 船舶速度分布对比

4 结 束 语

利用AIS数据提取船舶位置、航速及航向等行为特征量，并建立了行为特征相似度计算模型，基于DBSCAN算法实现了船舶轨迹聚类方法流程，利用长江口南槽段船舶实际轨迹数据对算法进行了验证和分析.结果表明，基于行为特征相似度的轨迹聚类比仅考虑空间位置相似度的轨迹聚类能发现更多的轨迹模式或轨迹异常，为开展船舶交通行为分析和行为监管提供了新方法.