基于DBTCAN算法的船舶轨迹聚类与航路识别

杨家轩，刘元

(大连海事大学 a.航海学院；b.辽宁省航海安全保障重点实验室，辽宁 大连 116026)

0 引 言

在经济全球化背景下，海运在国际贸易中的作用越来越重要。现在超过90%的国际贸易是通过海运完成的，沿海和港口附近的船舶密度日益增大，船舶运输条件日益复杂，对水域通航管理能力的要求也日益提高。船舶自动识别系统(automatic identification system, AIS)是获取船舶航行数据、分析海上船舶行为特征和交通流信息的重要数据来源。对AIS数据进行聚类分析，可以为海上船舶行为和交通流特征的提取、航线规划、海上船舶异常行为检测等技术的开发和应用提供基本的手段和关键的方法，为海事监管机构的决策提供支持和科学依据。

船舶轨迹聚类的目的是找到那些具有相同运动模式的轨迹，通过分析船舶运动模式和轨迹特征信息来确定轨迹之间的相似度，然后将相似度较高的轨迹归为一类。目前，轨迹聚类的研究主要分两类：对整条轨迹进行聚类;先对轨迹分段再对轨迹段进行聚类。LEE等将轨迹划分成多个子轨迹段，采用最小描述长度(the minimum description length, MDL)来计算各轨迹段之间的相似度，最后结合轨迹聚类框架从真实的轨迹数据中提取公共子轨迹段。陈锦阳等先根据轨迹特征点将整条轨迹进行分割得到子轨迹段，然后利用基于改进Hausdorff距离的轨迹聚类算法对子轨迹段进行聚类。江玉玲等利用船位转向角和航速变化量作为信息度量对船舶轨迹进行分段，采用离散Frechet 距离作为轨迹相似度度量对子轨迹段进行聚类得到船舶运动典型轨迹。轨迹段聚类在分段的过程中会舍弃轨迹段内部的特征点，可能丢失轨迹的局部关键运动特征，而且大多数分段方法只考虑单一指标，主观性太强，无法找到最优的分段方法。LI等以船舶轨迹整体为聚类对象，建立轨迹之间的空间距离矩阵，实现不同空间分布和方向的轨迹聚类。牟军敏等采用自适应谱聚类算法对长江口完整船舶轨迹进行分析，成功提取出该水域的6条主要航线。刘岳豪等利用骨架提取技术，先将船舶轨迹数据转化为图像数据再进行聚类分析，成功分析出船舶较频繁行进的路线。然而，由于AIS数据量巨大，而且每条船舶轨迹长度不同，直接对完整船舶轨迹进行聚类的效率不高，且检测精度低。因此，如何度量不同长度船舶轨迹之间的相似度并结合聚类算法对船舶轨迹进行分析是本文研究的重点。

为解决船舶轨迹聚类算法在实际应用中遇到的问题，本文把具有噪声的基于密度的空间聚类(density-based spatial clustering of applications with noise, DBSCAN)算法从点聚类推广到线聚类，提出一种可以适用于完整船舶轨迹的聚类算法——具有噪声的基于密度的轨迹聚类(density-based trajectory clustering of applications with noise, DBTCAN)算法。该算法利用Hausdorff距离作为船舶轨迹之间的相似度度量，无须对轨迹进行分段处理，可以对不同长度的船舶轨迹进行聚类分析。

1 DBTCAN算法

1.1 相似度度量

空间距离不仅可以用来描述物体的位置分布，而且可以用来表示物体之间的相似度。距离小意味着差异小，相似度高。以空间距离为基础的相似度度量方法有很多，如欧氏距离、曼哈顿距离、闵可夫斯基距离、切比雪夫距离和Hausdorff距离等，其中Hausdorff距离常用于计算曲线之间的相似度。Hausdorff距离是一种定义两组点集之间距离的方法，可用于描述两组点集之间的相似度。两组点集之间的 Hausdorff距离越大，相似度越低。给定2条由若干有序轨迹点构成的轨迹={}，={}，则集合与集合的Hausdorff距离为

(,)=max((,),(,))

(1)

(2)

(3)

相对于传统的距离度量，运用Hausdorff距离公式无须对轨迹集进行插值处理，可以直接计算轨迹之间的相似度，避免了给轨迹数据添加噪声，减少了噪声对原始数据的影响。另一方面，由于播发时间间隔不一致，不同船舶产生和记录的AIS数据长度不同。Hausdorff距离可以很好地适用于计算船舶轨迹之间的相似度，因此本文采用Hausdorff距离作为船舶轨迹之间的相似度度量。

1.2 DBTCAN算法原理

DBSCAN算法是一种基于密度的聚类算法，可以应用于有噪声的环境，利用它可以找到任意形状的簇，并自动确定簇的数量。然而，DBSCAN算法多用于点聚类，不能直接对船舶轨迹进行分析。AIS数据中船舶位置信息是一系列由经纬度坐标构成的点集，Hausdorff距离可以直接用来度量船舶轨迹之间的相似度，无须对AIS数据进行插值处理。因此，本文将DBSCAN算法由传统的点聚类推广为线聚类，并采用Hausdorff距离作为相似度度量，提出一种可以适用于不同长度船舶轨迹聚类的DBTCAN算法。

DBTCAN算法思路如下。选中给定轨迹集中任意一条轨迹，通过计算找到与该轨迹相似度小于等于相似度阈值的所有轨迹：若轨迹数量小于邻域密度阈值，则该轨迹被标记为噪声轨迹；若轨迹数量大于等于，则该轨迹为核心轨迹。接着判断在这条轨迹邻域内的轨迹是否为核心轨迹，如果是，则这些轨迹属于一个簇。再对轨迹集内其他未被选中的轨迹进行判断，直到所有轨迹判断完毕完成聚类为止。DBTCAN算法的相关定义如下：

定义轨迹的邻域为

()={∈|(,)≤}

(4)

式中：为给定的轨迹集，∈,∈。()由所有与的相似度不超过的轨迹构成。

对于∈，如果的邻域满足

|()|≥

(5)

则为核心轨迹。式中，|()|为的邻域内包含的轨迹数量，为轨迹邻域密度阈值。

在轨迹集内，如果满足

∈()

(6)

|()|≥

(7)

则到是直接密度可达的。

太阳能供电系统通过30W太阳能单晶硅面板采能、12V/20Ah蓄电池储电[7]。选择EPOW-PS10太阳能控制器,该控制器是基于智能芯片控制的太阳充放电管理系统，具有防反充、三级过载、短路、反接、过充电、过放电等完善的系统保护功能，保证蓄电池工作在最佳的状态。蓄电池是12V输出，系统只需5V供电，所以还用了一个低纹波的LM2596超小型DC-DC 12V转5V降压模块，该模块最大连续输出电流3A，模块还具有输出短路、过热保护功能，这样就提高了系统的安全性能。

在轨迹集内，如果存在,,…,,…,，使得所有的到+1关于和都是直接密度可达的，则称到是密度可达的。

存在一条任意轨迹，∈，若到、到关于和是密度可达的，则称与关于和是密度相连的。

DBTCAN算法流程见图1。

图1 DBTCAN算法流程

1.3 DBTCAN算法参数的自适应确定

基于密度的聚类算法本质上是在数据集中发现高密度的数据集，即该数据集中数据点之间的平均距离较小，而高密度数据集之间存在着低密度区域。DBTCAN算法采用参数和来确定划分高密度轨迹集的阈值，不同的参数组合对最后的聚类效果有较大影响。要想实现参数的自适应确定，关键在于确定合适的候选阈值参数集合，参数的取值范围和参数间距决定了聚类的精度和运算量。基于以上考虑，本文利用轨迹集自身的空间分布特性，基于平均最近邻(-average nearest neighbor, KANN)算法和数学期望法生成DBTCAN算法的最优输入参数，步骤如下：

采用KANN算法生成候选集合。KANN算法的基本思想是通过计算轨迹集中每条轨迹与其第条最近邻轨迹之间的最近邻距离，并对所有轨迹的最近邻距离求平均值，得到轨迹集的平均最近邻距离。对所有的值进行计算，得到平均最近邻距离向量。具体步骤如下：

步骤① 计算轨迹集的距离矩阵，即

×={(,)|1≤≤,1≤≤}

(8)

式中：为轨迹集所包含的轨迹数量。

步骤② 对距离矩阵×中的每行元素按升序进行排序后，则该矩阵第一列元素(其所组成的距离向量记为)表示轨迹到自身的距离(全为0)，第列元素构成所有轨迹的最近邻距离向量。

(9)

采用数学期望法生成候选集合。依次求出每个候选对应的邻域内轨迹数量，并计算所有轨迹的邻域内轨迹数量的数学期望值，作为轨迹集的邻域密度阈值，表示为

(10)

式中：为第条轨迹邻域内的轨迹数量。

确定最优聚类簇数。依次选取候选和由式(10)计算得到的，将其输入DBTCAN算法对轨迹集进行聚类分析，可以得到不同值下的聚类簇数。当聚类簇数连续3次或3次以上相同时，则认为聚类结果趋于稳定，记该聚类簇数为最优聚类簇数。

2 实验设计与结果分析

为验证DBTCAN算法的有效性，选取渤海水域(36°08′16″～40°27′26″N,117°42′46″～123°50′35″E)2018年1月1—4日121艘船的739 629条轨迹数据作为研究对象进行实验。

2.1 实验过程

对AIS数据进行解码存储、坐标转换、噪声清洗等预处理后，设置合适的阈值，利用Douglas-Peucker算法对船舶轨迹进行压缩，预处理后的船舶轨迹见图2。

图2 预处理后的渤海水域船舶轨迹

图3 聚类簇数与K值的关系

值是一种评价聚类结果的综合指标。设正确率为判断正确的轨迹数量占识别出的轨迹数量的百分比；召回率为判断正确的轨迹数量占实际的总轨迹数量的百分比，则值为

(11)

由图4可知，在=16时，值最大，聚类结果较优，说明利用参数自适应确定方法得到的参数为最优参数。将最优参数输入DBTCAN算法，得到渤海水域船舶轨迹聚类结果，见图5。

图4 聚类结果的F值曲线

图5 渤海水域船舶轨迹聚类结果

2.2 结果分析

实验共得到4个簇。根据实际航路与各簇之间的对应关系，对图5中4种不同颜色的簇进行分析与整合，得到渤海水域4条主要的航路:

航路1(图6a)：成山角→老铁山水道→天津港、曹妃甸港。航路起点为成山角附近水域，经(37°38′30″N,122°38′48″E)转向305°到达老铁山水道水域。在老铁山水道定线制的警戒圈经(38°36′06″N,120°51′18″E)到达(38°48′00″N,118°45′12″E)，进入曹妃甸水域，再按曹妃甸水域船舶定线制航法，航行至天津港。

航路2(图6b)：成山角→老铁山水道→唐山港。航路起点为成山角船舶定线制水域，经(37°38′30″N,122°38′48″E)转向305°到达老铁山水道水域。在(38°37′06″N,120°51′48″E)沿航向305°航行至唐山港附近水域。

航路3(图6c)：成山角→老铁山水道→渤海湾北部。航路起点为成山角水域，经(37°38′30″N,122°38′48″E)转向305°到达老铁山水道水域。经(38°37′06″N,120°51′48″E)沿航向8°航行至(39°32′18″N,121°01′42″E)，再转向31°航行至(40°08′06″N,121°29′12″E)，再转向69°航行至终点(40°13′12″N,121°47′24″E)。反之，依次沿航向249°、211°、188°航行至老铁山水道水域，再沿航向125°到达成山角水域。

航路4(图6d)：成山角→老铁山水道→秦皇岛港。航路起点为成山角船舶定线制水域，经(37°38′30″N,122°38′48″E)转向305°到达老铁山水道定线制水域。经(38°37′06″N,120°51′48″E)转向334°航行至(38°54′30″N,120°41′36″E)，再转向319°航行至(39°40′42″N,119°51′42″E)，最终抵达秦皇岛港水域。反之，由139°转向到154°航行到老铁山水道水域，再沿航向125°航行至成山角水域。

a)航路1

由渤海及黄海北部航法图可知，船舶通过老铁山水道后大致有3个主要航向，分别是向西沿着推荐航线前往天津港和曹妃甸港及其附近水域，向西北沿推荐航线前往秦皇岛港附近水域，向北前往渤海湾北部水域。由此可知，本文提出的DBTCAN算法可以对渤海水域的船舶轨迹进行聚类，能准确提取该水域船舶的主要航线，且聚类结果符合渤海水域实际的交通流现状。

3 结束语

本文针对聚类算法在船舶轨迹聚类应用中的不足，提出能够适用于完整船舶轨迹聚类的DBTCAN算法。该算法利用Hausdorff距离作为船舶轨迹之间的相似度度量，可以对不同长度的船舶轨迹进行聚类。同时针对DBTCAN算法需要人工确定输入参数的问题，提出一种参数自适应确定方法，可以自适应得到DBTCAN算法的最优输入参数，使得聚类过程无须人为干预，聚类结果具有高的准确率。最后，利用渤海水域的船舶轨迹数据对DBTCAN算法进行实例验证。结果表明，该算法能够在大量复杂船舶轨迹中找到相似轨迹并对其进行聚类，且聚类结果与实际交通流情况一致。本文成果可以为相关部门在航道规划、分道通航方面以及开展渤海水域船舶定线制工作提供一定的参考。

在基于DBTCAN算法进行聚类的过程中需要计算每两条轨迹之间的Hausdorff距离，如果数据量太大，则算法运行效率将大大降低，运行时间将成倍增加。后续的研究工作可以从提高算法运行效率和推动聚类结果的实际应用等方面展开。