基于Spark的船舶航行轨迹聚类方法

彭祥文, 高 曙, 初秀民, 何 阳, 陆 丛

(武汉理工大学 a.计算机科学与技术学院；b.国家水运安全工程技术研究中心, 武汉 430063)

2017-04-25

国家自然科学基金(51479155);城市灾害地图可视化方法研究(JD20150301)

彭祥文(1992—)，男，江西上饶人，硕士生，研究方向为云计算应用。E-mail:616456468@qq.com

高 曙(1967—)，女，安徽芜湖人，教授，研究方向为数据挖掘及应用、智能交通。E-mail:gshu418@163.com

1000-4653(2017)03-0049-05

基于Spark的船舶航行轨迹聚类方法

彭祥文a, 高 曙a, 初秀民b, 何 阳a, 陆 丛a

(武汉理工大学 a.计算机科学与技术学院；b.国家水运安全工程技术研究中心, 武汉 430063)

依托船舶自动识别系统(Automatic Identification System,AIS)数据，利用云计算并结合聚类算法，对船舶历史数据进行轨迹聚类分析，构建船舶航行正常轨迹模型，为实时检测船舶异常轨迹奠定基础，进而为提高水上交通监管智能化水平提供新方法。针对目前轨迹聚类算法效率低等问题，基于Spark内存计算技术及数据分区思想，提出一种改进的并行子轨迹聚类算法SPDBSCANST(Parallel DBSCAN of Sub Trajectory Based on Spark)。以长江航道武汉段船舶航行数据为例进行试验验证，并通过可视化方式呈现。结果表明，改进后的算法的聚类效率和效果都有明显提升。

水路运输;船舶自动识别系统；Spark；轨迹聚类；正常轨迹建模

近年来，随着国内水运业迅速发展，长江干线的交通压力日益增大,迫切需要提高水上交通监管的智能化水平。因此，依托船舶自动识别系统(Automatic Identification System,AIS)数据，基于Spark云平台，采用数据挖掘技术，对船舶航行轨迹进行聚类分析，构建正常轨迹模型，为发现和研究船舶运动特征及行为模式提供新思路。

现有的轨迹聚类算法[1]主要分为以下2大类:

1) 将整条轨迹作为研究对象进行聚类。该类方法能比较直观地评价轨迹间的相似性，受输入参数的影响较小，但对复杂的轨迹容易忽略局部异常信息，且对高维轨迹数据的聚类效果欠佳。

2) 对复杂轨迹进行划分，将子轨迹作为聚类目标。该方法能很好地识别轨迹的局部特征，有效处理高维轨迹数据，结合基于密度的DBSCAN聚类算法发现任意形状的轨迹簇，但随着数据规模的增大，DBSCAN算法会因消耗大量的I/O而造成聚类效率低下。

对此，结合数据分区思想和Spark云平台高效并行的优势，提出一种改进的基于轨迹分区预处理的并行化子轨迹聚类算法SPDBSCANST(Parallel DBSCAN of Sub Trajectory Based on Spark)。

1 子轨迹划分及相似性度量方法

1.1基于AIS数据的船舶轨迹提取

受AIS设备自身及外界条件的限制[2]，通过AIS设备获得的轨迹数据需经过一系列预处理才可采用。将解码后的AIS数据上传到HDFS，使用Spark的filter算子选取一定范围及一段时间内的AIS数据，依据船舶水上移动通信业务标识码(Maritime Mobile Service Identity,MMSI),按时间顺序提取出船舶轨迹。使用该方法提取出的轨迹通常会出现以下情况：

1) 区域内存在多个往返。采用的解决方法是将MMSI相同的船舶轨迹分为多个轨迹，主要依据的是轨迹点之间的时间间隔。船舶在航行时，其AIS数据更新间隔一般不会超过10 min;而对于折返情况，其时间间隔通常远大于10 min。因此,可将往返轨迹划分为多个轨迹。

2) 轨迹点位置偏移。计算轨迹点与其前后轨迹点之间的时间间隔及距离间隔,若该轨迹点与其前后点之间的时间间隔较小、距离间隔较大，而其前后点之间的时间间隔较小、距离间隔在正常范围内，则可将该轨迹点作为位置偏移点去除。

1.2子轨迹划分

船舶在内河航行时，受内河形状、宽度和深度等自身条件及桥梁、风等周围环境的影响，其航行轨迹和航速都会发生变化。通过设置船舶转向角阈值及速度变化率阈值，对船舶轨迹进行划分，其中船舶转向角是指相邻子轨迹段的航迹向之差(见图1)。

图1 船舶转向角

图1中:a和b为船舶轨迹中相邻的2条子轨迹段，其航迹向的夹角(即转向角)为θ1。

速度变化率α的计算式为

(1)

式(1)中:υ2和υ1为相邻轨迹点航速;Δt为相邻时间间隔。

子轨迹划分主要步骤：

1) 计算相邻子轨迹段航迹向差值及相邻轨迹点速度变化率。

2) 将所求值与预先设定的阈值相比较。

3) 若航迹向差值或速度变化率大于阈值，则使用该轨迹点对轨迹进行划分；否则返回步骤1)，继续采样。

1.3子轨迹相似性度量

船舶AIS数据中蕴含有丰富的信息[3]，在度量子轨迹的相似性时，应充分考虑各类信息对子轨迹相似性的影响，从而提高聚类质量。这里主要从船舶位置、航向和航速等3个方面进行距离计算[1,4]，并通过归一化加权求和得到子轨迹多特征距离，以此度量子轨迹之间的相似性。

1.3.1子轨迹间位置与航向距离计算

船舶轨迹划分后可表示为子轨迹的集合。在进行轨迹划分时考虑轨迹段航迹向的变化，因此将划分后的子轨迹近似作为线段进行处理。

图2为子轨迹间距离度量，其中:Li=siei和Lj=sjej分别为2条子轨迹;si和sj分别为子轨迹Li及Lj的起点;ei和ej分别为子轨迹Li及Lj的终点;ps和pe分别为sj及ej在Li(或Li延长线)上的投影。

图2 子轨迹间距离度量

d//(Li,Lj),d⊥(Li,Lj)和dθ(Li,Lj)分别为子轨迹Lj到Li的水平距离、垂直距离及航向距离，具体计算式为

d//(Li,Lj)=min(l//1,l//2)

(2)

(3)

(4)

同理，可求得子轨迹Li到Lj的水平距离d//(Lj,Li)及垂直距离d⊥(Lj,Li)。根据Hausdroff距离定义，取二者中的较大值作为轨迹间的距离。即将子轨迹Li与Lj之间的水平距离d//,垂直距离d⊥及航向距离dθ定义为

1.3.2子轨迹间航速距离计算

船舶在内河航行时，受内河航道条件的限制，航行轨迹都比较固定，因此船舶航速是轨迹聚类的一个非常重要的要素。在现有的轨迹聚类算法中，通常只考虑平均航速，对航速信息的利用较少，从最大航速、最小航速、中位数航速及平均航速等4个方面综合考虑航速距离的度量。其计算方法为

(8)

式(8)中:Smax(Li,Lj)=|Vmax(Li)-Vmax(Lj)|为2个子轨迹中轨迹点最大航速的差异值;Savg,Smin和Smed分别为平均航速、最小航速及中位数航速的差异值。

1.3.3综合距离

在得到4种距离的度量方法之后，首先分别对4种距离进行归一化处理，然后定义相应的权重W={W//,W⊥,Wθ,WS}，权重应满足：

(1) 均>0，即非负性；

(2)W//+W⊥+Wθ+WS=1。

在定义权重时，在不同的内河航道条件及外部环境中所取的权重可以不同，例如：在较宽的航道，子轨迹间允许的垂直距离会增大，可减小W⊥。由于4种距离的量纲不同，因此在计算综合距离之前需对4种距离进行归一化，归一化公式为

(9)

式(9)中:d为处理前距离;dmax和dmin分别为该类距离的最大值及最小值;d′为处理后距离。由此,对4种归一化后的距离进行加权求和即可得到综合距离，即

(10)

2 SPDBSCANST聚类算法

在采用DBSCAN算法对数据进行聚类时，大量的I/O消耗导致时间剧增。[5]Spark分布式云平台引入弹性分布式数据库RDD(Resilient Distributed Dataset)的概念[6]，在计算中将数据分布式缓存在各节点内存中，从而降低大量的磁盘I/O消耗。基于Spark实现并行子轨迹DBSCAN聚类算法，首先对轨迹数据进行分区预处理，分别对各分区子轨迹进行聚类;然后对各邻近区域进行类簇合并，从而得到最终的轨迹聚类结果。由于Spark所有的计算都在内存中对RDD进行计算，中间无需与磁盘进行I/O，因此能极大地提高聚类效率。SPDBSCANST聚类算法总体流程见图3。

图3 SPDBSCANST聚类算法总体流程

SPDBSCANST聚类算法伪代码描述如下：

SPDBSCANST聚类算法

算法名称：SPDBSCANST聚类算法

输入：(1)邻域ε，密度阈值minStr;

(2)轨迹数据，各分区经度范围;

(3)分区距离权重W{W//,W⊥,Wθ,WS}

输出：全局轨迹类簇

BEGIN

1. rdd=sc.textFile(hdfs文件路径) //将轨迹数据存入到rdd

2. rdd.map(d=>(num,d)) //依据分区经度的范围对轨迹数据进行划分，num为划分后分区号

3. rdd.groupByKey() //按分区号聚合轨迹数据

4. rdd.map(BinOrderKey(_)) //对各分区内数据进行二次排序，提取船舶轨迹

5. rdd.map(seprate(_)) //分区子轨迹划分

6. rdd.map(DBSCANST(_)) //子轨迹DBSCAN聚类

7. rdd.map(c=>(cnum,c)).reduceByKey() //合并邻接子轨迹类簇

END

2.1轨迹数据分区处理

轨迹数据的分区可看作是对轨迹的初次子轨迹划分。在进行轨迹数据划分时，由于内河环境复杂，不一定依据经度值(长江在纬度上可看成一条曲线)均匀划分，可根据内河特征进行划分，将轨迹划分为桥梁区域、支流区域和弯道区域等。轨迹分区完成后，采用“1.2”节中的子轨迹划分方法对各区域内的轨迹进行划分。

2.2分区子轨迹聚类

采用DBSCAN聚类算法对各分区子轨迹进行聚类[8]，使用式(10)度量子轨迹的相似性，依据分区特征，利用分区权值代替全局权值，从而提高聚类质量。子轨迹DBSCAN聚类方法与典型的DBSCAN聚类方法类似，不同之处在于距离的度量方法。子轨迹DBSCAN聚类方法使用的距离为子轨迹对象之间的距离，而典型的DBSCAN聚类方法使用的距离为点对象之间的距离。邻域为ε,密度阈值为minStr的子轨迹DBSCAN聚类算法相关定义如下。

1) 核心对象：给定子轨迹Li的ε邻域内的子轨迹数目大于或等于密度阈值minStr，具体定义为

2) 直接密度可达：对于子轨迹集合DTD，若子轨迹Li在Lj的邻域ε内，且子轨迹Lj为核心对象，则称子轨迹Li为Lj直接密度可达。

3) 密度可达：对于子轨迹集合DTD，若存在子轨迹链L1，L2，…，Ln，对于Li∈DTD(1≤i≤n)存在Li+1从Li关于ε和minStr直接密度可达，则称Ln为L1密度可达。

4) 密度相连：若存在子轨迹Lk，使得子轨迹Li和Lj都从Lk密度可达，则称Li和Lj密度相连。

2.3局部类簇合并

在进行区域划分时，可将原本在全局中为同一类簇的子轨迹类簇划分成2个局部类簇(见图4)[9]。

图4 轨迹类簇合并

图4中,黑点代表子轨迹，p和q两条子轨迹同时属于分区L1及分区L2中的类簇，因此可对类簇进行合并。具体合并方法为：

1) 确定划分边界邻接区域，若子轨迹中存在轨迹点在邻接区域内，则将该子轨迹划分到邻接区域内。

2) 遍历邻接区域内所有的子轨迹，若存在子轨迹为核心对象且同时属于2个局部类簇，则合并该局部类簇。

2.4船舶航行轨迹建模

经过以上聚类过程即可得到船舶子轨迹类簇，在各子轨迹类簇中提取一系列采样点(用SP表示采样点)表征船舶典型轨迹。以下为船舶航行轨迹建模过程。

2.4.1确定各子轨迹类簇的方向(簇向)

取各子轨迹类簇中所有轨迹点航向的平均值作为簇向，具体计算方法为

(13)

2.4.2沿着对应簇向划分网格

沿着对应簇向对子轨迹类簇进行网格划分(见图5)。

图5 类簇网格划分

图5中:矩形框表示子轨迹类簇;箭头方向表示簇向;n为类簇划分后的块数，即该子轨迹类簇采样点个数。n的值通过对类簇内所有完整轨迹(同一MMSI)的轨迹点总数取平均确定，计算式为

(14)

式(14)中:numPi为第i条完整轨迹中轨迹点个数;m为完整轨迹数。

2.4.3构建采样点

图5中，每个网格构建1个采样点SPi，采样点有4个特征属性,分别为平均经度LONavg,平均纬度LATavg,平均航速SPDavg和平均航向COUavg，具体表示为

SPi={LONavg,LATavg,SPDavg,COUavg}

(15)

使用采样点表征船舶典型轨迹，具体表示为

TR={SP1,SP2,…,SPn}

(16)

3 试验及分析

试验在武汉理工大学国家水运安全工程技术研究中心的Spark云服务平台上完成，创建6台虚拟机组成一个集群。处理器配置：8核；内存8G；硬盘300G。软件环境选择CentOS系统；Spark1.6.1；Hadoop2.6.4；IDEA3.4；Scala2.10.8；可视化工具使用Mapv。选取一台虚拟机作为主节点master，其余为工作节点worker。试验分为改进后算法对聚类效率的提升和聚类效果的展示2部分。

3.1Spark云平台下轨迹聚类效率分析

选取长江航道武汉段2016年2月份的AIS数据作为试验数据。为在不同数据量下对算法的效率进行对比，分别选取大约500M(1 000万条预处理后AIS数据，只包含纬度、经度、速度、方向、MMSI及时间)和2G的数据量进行试验，结果见图6。

图6 算法执行时间对比

从图6中可看出:随着集群节点个数的增加，算法执行时间缩短，最后趋于平稳;数据量越大，算法的加速比越高，从而说明改进后的算法对大数据具有很好的适应性。

由此可见，利用Spark云平台能有效提高海量AIS数据的处理效率，数据量越大，效果越明显，从而为高效、大规模地进行船舶航行轨迹分析奠定基础。

3.2聚类效果展示

选取长江航道武汉段2016年2月份大船(船长>80 m)的AIS数据作为试验数据，经度值在[114.23°,114.56°]，纬度值在[30.447°,30.73°]，对数据进行预处理之后，有效AIS数据为1 948 581条;将轨迹数据划分为20个区域，对各分区进行子轨迹划分，划分后子轨迹有96 566条。该部分试验主要分为3部分进行，分别为邻域ε及密度阈值minStr的确定、不同航道条件下综合距离权值的确定和典型轨迹提取。

3.2.1邻域ε及密度阈值minStr的确定

在距离权值(如式(10)所示)相等(都为0.25)的情况下，对轨迹间距离进行统计，结果表明轨迹间距离大多集中在(0～0.01)范围内，故取邻域ε=0.01。由于船舶轨迹受航道限制，故轨迹间相似性都比较高，经过多次试验后，当密度阈值minStr=20时，聚类结果比较理想。图7为船舶轨迹聚类前后对比。

a) 聚类前船舶轨迹

b) 聚类后船舶轨迹

3.2.2综合距离权值的确定

从图7a)中可看出，对所有分区使用相同的距离权值时，一些分区内的聚类结果不尽如人意(图8a)和9a)为放大后的2个分区)，因此需基于航道特征确定各距离权值。综合距离从垂直距离、平行距离、角度距离及速度距离等4方面考虑，依据航道特征将航道划分为限速区域(桥区，港口等)、限宽区域(宽航道/窄航道)及弯道区域。

由图8a)可知，该航道内有武汉长江大桥、长江二桥及汉江汇流，因此该区域内船舶的航速会受到限制，增大航速距离权值将加大航速对轨迹聚类的影响；图8b)为修改权重W=(0.2,0.2,0.2,0.4)后的聚类效果，可发现修改权值后聚类效果有明显提升。

b) 修改后

由图9a)可知，该航道为夹水道，航道较窄，在该区域内船舶间垂直距离受到限制，故增大垂直距离权值，从而增大垂直距离对聚类效果的影响;图9b)为修改权值W=(0.15,0.4,0.2,0.25)后聚类效果，可发现聚类效果有较大改善。

a) 修改前

b) 修改后

3.2.3典型轨迹提取

在确定各分区距离权值之后，采用“2.4”节给出的方法构建船舶航行轨迹。图10为船舶典型轨迹提取，其中黑点为提取出的2条典型轨迹(分别为上行和下行)。

图10 船舶典型轨迹提取

4 结束语

基于Spark云平台，对船舶子轨迹聚类方法进行研究，构建船舶航行轨迹，并以长江航道武汉段2016年2月份的AIS数据为试例进行验证。通过在Spark云平台上对船舶子轨迹聚类算法进行并行化设计，可极大地提高轨迹聚类效率，为进一步研究船舶运动特征、行为模式及船舶轨迹实时异常检测等提供技术保障。

[1] 肖潇, 邵哲平, 潘家财,等. 基于AIS信息的船舶轨迹聚类模型及应用[J]. 中国航海, 2015, 38(2):82-86.

[2] 魏照坤. 基于 AIS 的船舶轨迹聚类与应用[D]. 大连： 大连海事大学,2015.

[3] 刘畅. 船舶自动识别系统(AIS)关键技术研究[D].大连:大连海事大学,2013.

[4] LIU B, DE SOUZA E N, MATWIN S, et al. Know-ledge-Based Clustering of Ship Trajectories Using Density-Based Approach[C]// IEEE International Conference on Big Data. IEEE, 2014:603-60.

[5] 赖丽萍, 聂瑞华, 汪疆平,等. 基于MapReduce的改进DBSCAN算法[J]. 计算机科学, 2015(S2):396-399.

[6] 王桂兰, 周国亮, 萨初日拉,等. Spark环境下的并行模糊C均值聚类算法[J]. 计算机应用, 2016, 36(2):342-347.

[7] 朱飞祥, 张英俊, 高宗江. 基于数据挖掘的船舶行为研究[J]. 中国航海, 2012, 35(2):50-54.

[8] DAI B R, LIN I C. Efficient Map/Reduce-Based DBSCAN Algorithm with Optimized Data Partition[C]// IEEE Fifth International Conference on Cloud Computing. IEEE Computer Society, 2012:59-66.

[9] SARAZIN T, AZZAG H, LEBBAH M. SOM Clustering Using Spark-MapReduce[C]// Parallel & Distributed Processing Symposium Workshops. IEEE, 2015.

ClusteringMethodofShip’sNavigationTrajectorySetBasedonSpark

PENGXiangwena,GAOShua,CHUXiuminb,HEYanga,LUConga

(a. School of Computer Science and Technology; b. National Water Transportation Safety Engineering Technology Research Center, Wuhan University of Technology, Wuhan 430063, China)

Constructing normal navigation trajectory model through processing historical AIS(Automatic Identification System) data of ships with the trajectory clustering algorithm is a way of setting up the reference for real-time detection of abnormal ships trajectory. Aimed at the problem of low efficiency of the current trajectory clustering algorithm, an improved parallel sub trajectory clustering algorithm is proposed named as SPDBSCANST (Parallel DBSCAN of Sub Trajectory Based on Spark) featuring Spark memory computing technology and data partition. The algorithm is verified with the ship navigation data of Yangtze River Waterway. The visualization of the trajectories is also achieved. The experiments show that the efficiency of the improved clustering algorithm is increased significantly.

waterway transportation; AIS； Spark； trajectory clustering； normal trajectory modeling

U675.7

A