王森杰 何正伟

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

0 引 言

船舶自动识别系统(auto identification system，AIS)[1]是一种实现船船、船岸通信的安全助航设备，船舶通过搭载AIS终端实时将自身船舶运动信息进行广播，通过岸基终端可以快速采集移动船舶的AIS数据.AIS数据不仅记录船舶的空间信息、时间信息，同时集成了对地航向、船首向和对地速度等船舶运动数据，蕴含丰富的语义和行为模式.对船舶轨迹数据进行聚类分析，可为船舶交通流特征提取、航路安全规划、船舶异常检测等技术研发和应用提供基础手段和关键方法，为航运规划、海事监管等工作开展提供决策支持和科学依据[2].在轨迹数据激增和大数据技术发展的背景下，如何从轨迹数据中挖掘积累的物体运动模式，已经成为轨迹数据分析领域的研究热点之一.马文耀等[3]提出了一种基于单向距离的轨迹相似度计算方法，该方法将单向距离定义为一条船舶轨迹上各个点到另一轨迹各个点的最小距离的平均值，利用谱聚类算法对轨迹的空间分布进行学习，获取船舶的正常运动模式.Zhen等[4]人整合k-medoids聚类和朴素贝叶斯分类器，实现了船舶行为的分类和异常行为检测.Zhao等[5]人基于原始朴素DP算法和DBSCAN算法实现船舶轨迹模式的快速分类辨识.江玉玲等[6]采取Frechet距离对船舶轨迹相似度进行建模，基于DBSCAN聚类方法对典型轨迹得到了的符合实际的聚类结果.张春玮等[7]综合船舶位置、航速、航向等信息，对不同属性数据进行加权求和得到轨迹特征，利用DBASCAN算法实现了航道内船舶异常行为的分类辨识.彭祥文等[8]设计了一种基于轨迹分区预处理的并行化子轨迹聚类算法，通过数据分区并行实现了聚类加速.综上，这些专家学者对于船舶轨迹聚类研究都取得了相应的结论，但是以上方法依然在两个方面存在限制.一方面，单一特征的轨迹相似度模型没有充分利用AIS数据多维船舶属性特点，对复杂船舶轨迹的辨识能力不足；另一方面，多特征的轨迹相似度模型采取归一化参数对不同特征进行加权求和计算轨迹相似度，导致权重参数设置难，当耦合参数超过三个时，在某些特征参数分布下不同特征的差异相互叠加可能会导致一些隐蔽轨迹簇无法辨识.因此如何充分利用AIS多维船舶属性数据，建立鲁棒的轨迹相似度模型，提高聚类算法对隐蔽轨迹簇的辨识和聚类效率是当前船舶轨迹聚类研究的重点.

针对AIS数据集成空间、时间和其他多维属性的特点，文中提出了一种分层建模的船舶轨迹快速聚类算法.通过分层建模，以非全耦合的方式对不同特征参数进行有效利用，解决传统融合特征建模中参数权重设置困难，某些隐蔽轨迹簇无法辨识的问题.该算法将轨迹点的经纬度、对地航速、加速度、船艏向、对地航向共五种特征参数根据特征特点划分为空间、速度和方向三大特征类型，在不同层次建立对应特征轨迹相似度模型，通过三次自上而下的层次递进聚类，逐步放大聚类的分辨率，完成对船舶隐蔽轨迹簇的挖掘.同时针对传统轨迹聚类计算量大、聚类时间长等缺点，本文提出一种DP改进算法对船舶AIS轨迹特征点进行提取，实现数据压缩和聚类加速.

1 多特征层次轨迹聚类

1.1 相似度分层建模

轨迹聚类的本质是按照轨迹数据的相似性进行对象的划分，而聚类划分的结果严重取决于轨迹相似度模型的构建方式.因此，如何评价轨迹数据间距离或相似度是聚类处理的关键问题之一.船舶AIS轨迹数据是一种多维数据，它包括船舶位置、对地航速、对地航向、船艏向、转向率等船舶运动状态信息.针对AIS数据多维属性特点，本文将多种船舶状态数据划分为三组，在层次聚类中的上、中、下层中依次建立轨迹相似度模型，不同层次的轨迹相似度计算过程如下.

设两条不等长轨迹时间序列P=(p1,p2,…,pM)和Q=(q1,q2,…,qN)，每个轨迹点包含六种船舶状态参数.

(1)

(2)

式中：x为经度；y为纬度；s为对地航速；a为加速度；c为对地航向；h为船首向；i和j为轨迹序列第i和第j个轨迹点.在多特征层次聚类过程中，上层利用船舶位置信息进行聚类，其中任意轨迹点pi和qj的空间差异r1(pi,qj)为

(3)

中层利用船舶速度、加速度信息聚类，其中任意轨迹点pi和qj的速度差异r2(pi,qj)为

(4)

下层利用船舶对地航向、船首向信息聚类，其轨迹点pi和qj的航向差异r3(pi,qj)为

(5)

(6)

r3(pi,qj)=Δc+Δh

(7)

本文采取DTW算法[9]计算两条轨迹间的相似度.对于两条不等长轨迹序列P和Q，轨迹间相似度为各个轨迹点的累积最小差异.利用动态规划思想，从两条轨迹一端(p1,q1)遍历到另一端(pM,qN)的累计最小差异为

W(pM,qN)=r(pi,qj)+

min{W(pM-1,qN),W(pM,qN-1),W(pM-1,qN-1)}

(8)

式中：r(·)在不同层次聚类过层中分别表示特征相似度函数r1(·)、r2(·)、r3(·).

1.2 分层聚类

本文提出了一种自顶而下的层次聚类算法，见图1.其中船舶AIS数据多维属性被分层利用：基于经纬度聚类实现轨迹的空间分布分析；基于速度、加速度聚类实现船舶的加、减速行为辨识；基于船艏向、对地航向聚类实现船舶避让、掉头等行为识别.在多次递进聚类过程中，簇间差异被逐步放大，而不是一次性聚类，从而实现隐蔽轨迹簇辨识.同时分层建模有效解决了传统融合特征建模中参数权重设置困难的问题.

图1 多特征分层聚类示意图

采用DBSCAN算法作为层次聚类算法的核算法.DBSCAN算法需要预先设置的领域半径ε和簇内元素最小数目minPts.该算法通过遍历轨迹集合，计算两两轨迹之间的相似度，将相似度低于ε的轨迹划分到一个新集合内，如果该集合元素数目大于minPts则被定义为一个新类，否则划为噪声类.DBSCAN算法对噪声数据不敏感，无须事先设定簇个数，非常适合船舶AIS轨迹数据噪声点多，轨迹模式不确定性高等情况下的聚类[10-11].其多特征分层聚类步骤如下.

步骤1将空间位置信息作为上层特征，聚类得到大类轨迹簇.

步骤2将船舶对地航速、加速度作为中间层特征对得到的每一个大类轨迹簇进行进一步聚类得到中类轨迹簇.

步骤3将对地航向、船首向作为下层特征，同时对下层聚类条件进行约束，仅对中层聚类结果中轨迹数目最多的轨迹簇进行进一步下层聚类，其他簇不进行下层聚类，直接作为最后结果.

2 聚类加速

2.1 快速轨迹聚类框架

图2 轨迹特征点提取

2.2 压缩算法

DP算法是一种基于轨迹形状的轨迹压缩算法，在压缩轨迹的同时能够保存轨迹的形状特征[15].但是DP算法仅仅考虑了轨迹点的空间位置，而没有考虑船舶对地速度、船首向、对地航向等信息，导致对于直线加速、减速、减速转向等特殊轨迹段进行压缩时会发生关键特征轨迹点提取丢失.本文综合船舶位置、对地速度、对地航向、船首向信息对DP算法进行改进，提出了一种轨迹特征点提取算法.该算法在压缩轨迹点数量的同时，可以保留船舶不同驾驶行为特征信息.轨迹点提取算法流程见图3.

图3 船舶轨迹特征点提取流程

3 实验及分析

3.1 试验数据

虾峙门口外深水航槽是一条供大吃水受限船舶进出虾峙门的人工航槽.由于该区域没有采取定线制，导致进出虾峙门国际航道的船舶和南下北上的穿越船舶在此区域形成复杂的交通环境.本文提取2018年1月份100条船舶轨迹，共12 118条AIS数据作为试验数据对分层建模聚类算法进行验证.

对原轨迹集合100条轨迹，先利用上层特征船舶位置信息进行上层聚类，见图4.其领域半径ε设置为0.15，簇内元素最小数目minPts设置为15.由图4可知：上层特征将100条船舶轨迹辨识为3类，“class 1”标记轨迹被辨识为下行出港船舶，“class 3”标记的轨迹被辨识为上行进港船舶，“class 2”标记轨迹被辨识为噪声数据，即横穿等异常行为轨迹数据.

图4 上层特征聚类结果

对于上层聚类结果，继续利用中层特征进行进一步聚类.中层聚类的领域半径ε设置为300，簇内元素最小数目minPts设置为5.图5a)为大类下行出港船舶进一步聚类结果，中层聚类将其进一步聚为两类，其中“class 2”标记的轨迹均为减速的高速行驶船舶 “class 1”标记的轨迹均为低速行驶的加速船舶.图5b)为大类异常行为轨迹的中层聚类结果.中层聚类将其进一步聚为两类，其中“class 2”标记的轨迹均为中高速船舶，“class 1”标记的噪声轨迹均为低速游荡船舶.图5c)为大类上行进港船舶进一步聚类结果.中层聚类将其进一步聚为两类，其中“class 1”标记的轨迹均为减速行为，“class 2”标记的轨迹存在匀速行为.根据虾峙门口外深水航槽通航安全规定，进港船舶应采取减速行为.因此“class 2”标记的轨迹应该被识别船舶非法行为.

图5 中层特征聚类结果

对于中层聚类结果，由于聚类条件约束，下层聚类仅选取中层聚类结果中簇内元素最多的中类进行下层聚类.下层聚类的领域半径ε设置为3 000，簇内元素最小数目minPts设置为5.图6a)为中类加速出港船舶的进一步聚类，下层聚类将其进一步聚为两类，其中标记为“class 1”的轨迹均为直线加速出港船舶，而标记为“class 2”的轨迹被辨识为加速出港南下船舶.图6b)为中类穿越船舶的进一步聚类，下层聚类将其辨识为两类，其中标记为“class 1”的轨迹均为南下横穿船舶，而标记为“class 2”的轨迹被辨识为北上横穿船舶.图6c)为中类减速进港船舶的进一步聚类结果.下层聚类将其进一步聚为两类，其中标记为“class 1”的轨迹均为直线减速进港船舶，而标记为“class 2”的轨迹被辨识为东北向汇入减速进港船舶.

图6 下层特征聚类结果

图7 轨迹特征柱状统计分析图

图8 聚类结果的层次树状关系

经过3层层次聚类后，所有船舶轨迹被聚类为9类轨迹，见图7.对每一类船舶轨迹的平均速度、平均对地航向、平均压差角和平均加速度共4个属性进行柱状图统计分析，9类轨迹被辨识为9种不同船舶行为模式的船舶，并且9类轨迹拥有图8的层次树状关系.其中“class 1”为高速出港船舶，其船舶行为特征表现为初始速度快、存在小幅度减速；“class 2”为低速游荡船舶，其船舶行为特征为平均速度低、频繁转向、频繁减速；“class 3”为匀速进港船舶，其船舶行为特征变现为速度适中、速度稳定；“class 4”为加速南下出港船舶，其船舶行为特征为速度适中、下幅度加速、负压差角；“class 5”为加速直线出港、其船舶行为特征为速度适中、加速度适中、直线行驶.“class 6”为北上横穿船舶，船舶行为特征表现为速度适中、大幅度转向.“class7”为南下横穿船舶，船舶行为特征表现为速度适中、大幅度转向.“class 8”为减速东北向汇入进港船舶、其船舶行为特征表现为速度适中、减速度适中、负压差角.“class 9”为减速直线进港船舶、其船舶行为特征表现为速度适中、减速度适中、正压差角.统计结果表明，分层建模的船舶轨迹聚类算法能够有效将船舶轨迹辨识为9类轨迹模式，并且不同轨迹模式具有各自典型的轨迹特征分布.

3.3 聚类速度测试

以100条轨迹，共12 118个轨迹点作为测试数据，本文对传统DTW-DBSCAN、LCSS-DBSCAN、Frechet-DBSCAN和分层快速聚类算法进行了聚类速度对比实验.实验环境：python3.5，实验设备：i5-8250，内存8g.对于分层快速轨迹聚类算法，设置压缩阈值参数Th1=0.000 15，Th2=2，Th3=10，Th4=10.表1为目前算法和分层快速聚类算法在实验数据上的聚类时间结果.可以发现，DTW-DBSCAN、LCSS-DBSCAN、Frechet-DBSCAN在聚类速度速度上大致相等，约为283 s.而分层快速聚类算法，在4.025压缩倍率下，聚类速度约为传统无压缩算法的16倍.通过对比发现本文提出的聚类加速框架能够明显提升聚类速度，其速度提升倍率约为轨迹压缩倍率ρ的平方，与理论提升效率一致.

表1 聚类速度结果

4 结 束 语

针对目前轨迹聚类算法存在的缺点，本文充分利用船舶AIS数据的多维属性数据，提出了一种分层建模的轨迹聚类算法.通过分层建模，解决了融合特征模型中权重参数取值困难的问题，提高了模型的鲁棒性.通过递进聚类，依次放大类间差异，从而达到对隐蔽轨迹簇的辨识.同时改进DP算法，在轨迹聚类前先对轨迹进行特征点提取，通过数据规整和压缩有效提高了聚类效率.利用虾峙门深水航槽的数据进行了实验和分析，结果表明，分层建模的轨迹聚类算法能够有效辨识复杂船舶交通环境下各种船舶轨迹模式，同时该算法能够在层次聚类过层中有效挖掘不同船舶轨迹模式的树状层次关系，对于加强船舶交通行为分析和船舶交通监管具有重要意义.同时聚类速度对比实验的结果证明该框架能够极大提高聚类速度时间，对于目前快速增长的船舶AIS大数据分析极具现实意义.