基于单向距离的谱聚类船舶运动模式辨识

马文耀，吴兆麟，杨家轩，李伟峰

(1. 大连海事大学 航海学院，辽宁 大连 116026；2. 广东海洋大学 航海学院，广东 湛江 524000)



基于单向距离的谱聚类船舶运动模式辨识

马文耀1，2，吴兆麟1，杨家轩1，李伟峰1

(1. 大连海事大学 航海学院，辽宁 大连 116026；2. 广东海洋大学 航海学院，广东 湛江 524000)

利用海事大数据辨识船舶运动模式，能够发现高级别情景意识，提高海事监管技术的效率。提出了一种基于单向距离的谱聚类船舶运动模式辨识方法，充分利用单向距离抗干扰特点，构建了基于单向距离的轨迹相似性度量，得到了轨迹相似度矩阵；以无监督学习方式采用谱聚类算法学习轨迹的空间分布，获取船舶的正常运动模式；以琼州海峡实测AIS数据为样本，研究了进入海口秀英港的船舶运动模式，并分别统计了各模式内及模式之间的距离，获取的4种船舶运动模式与实际相符。实验结果表明：该方法聚类精度高，可以适用于沿海港口、狭水道和船舶交通复杂的区域的船舶运动模式辨识。

交通运输工程；运动模式；单向距离；谱聚类；相似性度量

0 引 言

随着海事云服务和大数据时代的来临，以及全球岸基AIS(Automatic Identification System, AIS)网络的建立，形成了海量船舶运动的数据库。利用海量数据来识别船舶运动模式[1]和挖掘高层次的情境感知，将有助于理解交通模式的季节性差异。聚类的航线能反映出不同船舶类型的船舶日常模式和航行时间等信息的差异，这些知识能提高目标船舶跟踪和海事监管效率。

影响船舶运动模式识别的两个重要方面是高效的模型和时空轨迹聚类算法。目前国内外许多学者多针对道路交通的运动目标进行研究，提出了各种从目标轨迹中获取运动模式的算法。冯宏祥等[2]利用基于AIS的元胞自动机船舶交通流模型模拟再现船舶交通流，获得船舶运动模式。胡宏宇等[3]利用改进的Hausdorff距离和谱聚类算法学习车辆轨迹的空间分布，提取运动目标的典型运动模式。闻佳等[4]设计了一种考虑到运动车辆轨迹方向性和运动性等特征的加权矢量Hausdorff距离公式，获取车辆运动模式，该方法需计算轨迹的运动特性，计算较为复杂。Lin Bin等[5]采用单向距离对运动目标的轨迹相似性进行计算，对轨迹分类，取得良好效果。N.Johnson等[6]和N.Sumpter等[7]采用自组织特征映射神经网络的方法对轨迹空间模式学习进行建模。W.Hu等[8]采用模糊自组织神经网络对目标轨迹的运动模式进行学习。基于神经网络的方法在构建网络方面较为复杂，学习速度较慢，且在学习过程中需要大量的数据学习参数。

无监督聚类算法也广泛应用，S.Atev等[9]和F.I.Bashir等[10]利用K均值聚类对轨迹空间模式进行学习；W.Hu等[8]利用模糊均值聚类的方法获取目标运动模式。但这几种方法需要对轨迹的长度进行标准化，损失了轨迹的部分原始状态信息。D.Biliotti等[11]采用层次聚类对轨迹进行分类，而层次聚类方法中某一层次的分解(合并)误差会导致整体模式学习效果的下降。另外，N.Junejo等[12]采用图分割将轨迹集合划分为多个子集以获取运动行为模式；L.Wang等[13]采用谱聚类方法学习目标轨迹运动模式。

道路交通中运动模式辨识方法一般先选择适当的距离来度量轨迹相似性，再利用分类或聚类算法，对运动轨迹进行划分，从而获得车辆运动模式。与道路交通相比，海上交通有其独特性。在开阔海域船舶与公路网络中移动车辆不同，其在空间上移动几乎无约束，船舶运动轨迹分布较广。而在港口、狭水道和交通复杂区域，船舶通航密度大，轨迹从而相对密集，同时船舶交通还受到陆域、航道、水深和交通管制等因素限制，使其呈现出与道路交通相似的规则性运动模式。因此，笔者参照道路交通中的运动模式辨识方法提出基于单向距离的谱聚类船舶运动模式辨识算法，即先采用单向距离度量船舶轨迹之间的相似性，再利用谱聚类算法[13]获取船舶轨迹的时空分布，从而提取船舶运动模式。

1 船舶轨迹的相似性

1.1 船舶轨迹数据的预处理

船舶的轨迹主要由船载自动识别系统设备获得。AIS设备以不同发送时间间隔(范围从3 min～2 s不等)发送本船的船位、船速、航向、船名、船长、船宽、国际海事组织(IMO)编号和海上移动业务识别码(MMSI)等信息。有时由于船舶发送AIS消息超出岸台AIS接收范围导致该船舶轨迹不全、或存在船舶AIS设备故障导致轨迹中出现部分错误或轨迹缺失等问题。这些因素，都会影响到船舶轨迹的分类、识别及后期的行为分析等。因此，在进行轨迹聚类前，必须对船舶的轨迹进行预处理。

1.2 船舶轨迹的相似性度量

运动轨迹划分的基础在于合理度量轨迹之间的相似性。目前轨迹的相似性度量方法有基于欧氏距离ED(Euclidean Distance)的方法、基于最长公共子序列的方法、基于动态时间弯曲距离的方法和基于Hausdorff距离的方法。欧式距离仅用于计算等长船舶间轨迹的相似性；最长公共子序列、Hausdorff距离和单向距离能用于不同长度船舶轨迹的相似性计算；而单向距离还能克服Hausdorff距离对噪声不敏感的缺陷。因此，笔者采用单向距离来度量轨迹空间的相似程度。

1.3 单向距离度量轨迹相似性

点p到轨迹T的距离定义为：

d(p,T)=minq∈TdED(p,q)

(1)

式中：q是轨迹T中的点；dED(p,q)表示点p到点q的欧氏距离。

轨迹T1到T2的单向距离定义为：

(2)

式中：NT1为轨迹T1中点的个数，该距离是有向距离(即dowd(T1,T2)和dowd(T2,T1)通常情况下是不等的)，轨迹T1到T2的距离使用dowd(T1,T2)和dowd(T2,T1)的平均距离表示。

(3)

从式(2)可以看出，单向距离实际上是一条轨迹上各个点到另一条轨迹中点的最小距离的平均值，所以对轨迹点中的噪声具有较强抗干扰能力。轨迹T1，T2之间的相似度函数定义为：

s(T1,T2)=e-[d(T1,T2)/(2σ2)]

(4)

式中：σ为尺度参数，表示相似性随着距离增大而衰减的程度，可采用信息熵计算得到。轨迹间距离越大，其相似性就越低。

2 基于谱聚类的船舶轨迹学习

基于所定义的轨迹之间的相似度表达，笔者采用谱聚类算法将轨迹按照空间相似度进行划分，获取目标轨迹的空间分布。谱聚类算法建立在谱图理论基础上，具有全局收敛的优点，能对任意形状的样本空间进行聚类且收敛于全局最优解。该算法把前面定义得到的相似度矩阵映射到亲合矩阵，并计算亲和矩阵的特征值和特征向量，得到运动模式的数目，使用K-means算法聚类出船舶运动模式。基于谱聚类的船舶轨迹学习算描述如下。

Step1：对于包含n条有效运动轨迹的集合T={T1，T2，…，Tn}，用单向距离对轨迹间空间相似性进行描述，构建n×n的相似度矩阵：

(5)

Step2：由相似度矩阵S和度矩阵D计算Laplacian矩阵L，并对其进行特征分解。

Step3：将特征分解得到的特征值由小到大排序，则运动模式的个数k取为：

k=argimax|λ(i+1)-λi|

Step4：计算k个最小特征值所对应的特征向量，x1，x2，…，xk，构建矩阵X=[x1，x2，…，xk]；将X的每一行进行归一化，得到特征向量空间矩阵Y：

(6)

Step5：轨迹Ti对应Y中第i个行向量。将Y中每一行看作k维空间中的一个向量，使用K-means算法进行聚类，将轨迹划分为k类。

上述算法能对轨迹的空间分布进行有效学习，从而将轨迹集合中的轨迹样本划分为相应的轨迹簇，即船舶运动模式。为了简洁地描述运动模式，使用轨迹簇的中心轨迹表征运动模式。对于第k个轨迹簇中任意一条轨迹Ti计算其与该簇中其他轨迹的平均距离：

(7)

(8)

通过式(7)可以得到包含nk条轨迹的第k个轨迹簇的中心轨迹Tm，Tm与该簇中其他轨迹的平均距离最小，也可表征某交通场景下运动目标的第k个运动模式。

3 实验分析

为验证笔者提出方法的有效性，使用实测AIS数据辨识船舶运动模式，并与实际交通进行比较。数据样本为琼州海峡2013年某月份的AIS数据记录，研究的水域范围为20°01′N～20°18′N，109°55′E～110°32′E。研究水域及船舶运动轨迹分布如图1。

图1 琼州海峡船舶运动轨迹分布Fig.1 Ship motion trajectory distribution of Qiongzhou strait

对AIS数据进行数据清洗，消除错误和缺失的轨迹数据，并选取进入海口港的船舶轨迹，得出有效船舶运动轨迹364条。使用笔者提出的算法进行空间聚类后，得到4种船舶运动模式，如图2。每类轨迹运行的所在区域恰好与琼州海峡内通航分道和进港航道区域一一对应。如果船舶进入海口秀英港(不考虑异常行为)，在该海域会有4种典型运动模式，即海安港至秀英港模式，与图2(a)表示的轨迹簇对应；海安新港至秀英港模式，与图2(b)表示的轨迹簇对应；海峡东入口至秀英港模式，与图2(c)表示的轨迹簇对应；海峡西入口至海口港模式，与图2(d)表示的轨迹簇对应。

图2 船舶运动模式Fig.2 Motion patterns of vessels

聚类实验结果与实际情况符合，表明了该方法进行船舶轨迹聚类的可行和准确性，4种船舶运动模式轨迹聚类情况统计如表1～表4。表中，d1～d4分别表示类内距离平均值、类内距离最大值、类间距离平均值和类间距离最小值，距离单位为n mile。

表1 进入秀英港船舶模式

表2 类内距离的平均值(d1)和最大值(d2)

表3 类间距离的平均值(d3)

表4 类间距离的最小值(d4)

从表2中看出4种模式中类内平均距离(d1)全都小于0.3 n mile，表明各模式中轨迹之间相互接近，且距离较小；P3和P4模式的最大的类内距离(d2)分别为0.38和0.34 n mile，均小于通航分道宽度(1.3 n mile)的1/2。P3和P4模式分别表示海峡东入口至秀英港和西入口至秀英港模式，属于该模式的船舶运动轨迹都处于通航分道内，且轨迹间最大距离小于通航分道宽度的1/2，表明通过琼州海峡的船舶都几乎航行在通航分道的中间，且分布较为集中。

表3和表4中得出模式P1与模式P2的类间平均距离(d3)小于1.36 n mile，且最小类间距离仅为0.76 n mile，表明这两类运动模式极为类似。从图2中容易看出海安港到秀英港的模式(P1)与海安新港到秀英港的模式(P2)相似，大多数船舶轨迹互相接近，但出发港位置不同。其它轨迹簇之间的类间距离大于4 n mile，很容易区分出运动模式。

4 结 语

笔者提出了一种基于单向距离的谱聚类船舶运动模式辨识方法，使用单向距离度量船舶轨迹之间的相似性，构建得到了船舶轨迹间相似性矩阵，并映射到谱聚类中的亲合矩阵，以无监督学习方式利用谱聚类算法识别出船舶运动模式。使用琼州海峡得实测AIS数据，以海口秀英港为研究对象，对进入该港的船舶运动模式进行辨识，聚类出了4种运动模式，并统计了各模式内及模式之间的距离，聚类结果与实际相符，实验结果表明该方法聚类精度高，可以适用于沿海港口、狭水道和船舶交通复杂的区域的船舶运动模式辨识。

[1] 朱飞祥,张英俊,高宗江.基于数据挖掘的船舶行为研究[J].中国航海,2012,35(2):50-54. Zhu Feixiang,Zhang Yingjun,Gao Zongjiang.Research on ship behaviors based on data mining [J].Journal of Navigation of China,2012,35(2):50-54.

[2] 冯宏祥,孔凡邨,肖英杰,等.基于AIS的元胞自动机模型的船舶交通流特征参数分析[J].武汉理工大学学报:交通科学与工程版,2014,38(2):324-328. Feng Hongxiang,Kong Fancun,Xiao Yingjie,et al.Parameters characteristics analysis of ship traffic flow with cellular automata model on AIS-based [J].Journal of Wuhan University of Technology:Transportation Science & Engineering,2014,38(2):324-328.

[3] 胡宏宇,王庆年,曲昭伟,等.运动目标空间模式辨识与异常交通行为检测[J].吉林大学学报,2011,41(6):1598-1602. Hu Hongyu,Wang Qingnian,Qv Zhaowei,et al.Spatial pattern recognition and abnormal traffic behavior detection of moving object [J].Journal of Jilin University,2011,41(6):1598-1602.

[4] 闻佳,崔维.实时视频中的车辆运动轨迹的提取和聚类[J].计算机工程与应用,2010,46(11):155-157. Wen Jia,Cui Wei.Extraction and clustering of vehicle’s trajectories from live video [J].Computer Engineering and Applications,2010,46(11):155-157.

[5] Lin Bin,Su Jianwen.One way distance:for shape based similarity search of moving object trajectories [J].Journal of Geo-informatics,2008,12(2):117-142.

[6] Johnson N,Hogg D.Learning the distribution of object trajectories for event recognition [J].Image and Vision Computing,1996,14(8):609-615.

[7] Sumpter N,Bulpitt A J.Learning spatial-temporal patterns for predicting object behavior [J].Image and vision Computing,2000,18(9):697-704.

[8] Hu W,Xie D,Tan T,et al.Learning activity patterns using fuzzy self-organizing neural network [J].IEEE Transactions on Systems,machinery and Cybernetics Part B:Cybernetics,2004,34(3):1618-1626.

[9] Atev S,Masoud O,Papanikolopoulos N.Learning traffic patterns at intersections by spectral clustering of motion trajectories [C]//IEEE International Conference on Intelligent Robots and Systems.Beijing:[s.n.],2006.

[10] Bashir F I,Khokhar A A,Schonfeld D.Object trajectory-based activity classification and recognition using hidden Markov models [J].IEEE Transactions on Image Processing,2007,16(7):1912-1919.

[11] Biliotti D,Antonimi G,Thiran J P.Multi-layer hierarchical clustering of pedestrian trajectories for automatic counting of people in video sequences [C]//Proceedings-IEEE Workshop on Motion and Video Computing.Breckenridge,Colorado:[s.n.],2007.

[12] Junejo N,Javed O,Shah M.Multi-feature path modeling for video surveillance [C]//Proceedings of the 17th International Conference on Pattern Recognition.Washington,D.C.,USA:[s.n.],2004.

[13] Wang L,Hu W M,Tan T N.Recent developments in human motion analysis [J].Pattern Recognition,2003,36(3):585-601

Vessel Motion Pattern Recognition Based on One-Way DistanceSpectral Clustering Algorithm

Ma Wenyao1, 2, Wu Zhaolin1, Yang Jiaxuan1, Li Weifeng1

(1. Navigation College, Dalian Maritime University, Dalian 116026, Liaoning, China; 2. Navigation College, Guangdong Ocean University, Zhanjiang 524000, Guangdong, China)

The vessel motion pattern recognition from marine large data can discovery high-level situational awareness, which improves the efficiency of maritime surveillance technology. Therefore, a motion pattern of vessel recognition methods based on one-way distance spectral clustering algorithm was proposed. The anti-interference of the one-way distance measurement was fully used to form the similarity value of trajectory based on one-way distance, and then the similarity matrix of the trajectory was also obtained. The regular motion patterns of vessels were extracted from the trajectories spatial distribution learnt by the spectral clustering algorithm in unsupervised learning way. Finally, the motion patterns for vessels entering into Xiuying port were analyzed by using real AIS data sample in Qiongzhou strait. And distance of inner pattern class and distance between of pattern class were calculated separately. Four obtained typical patterns were in consistence with those of the real traffic. The experiment results demonstrate that the proposed clustering methods is of good performance and well fit for identifying motion patterns of vessel in areas, such as coastal ports, narrow channels and complicated traffic zones.

transportation engineering; motion pattern; one-way distance; spectral clustering; similarity measure

10.3969/j.issn.1674-0696.2015.05.26

2014-05-28；

2014-08-29

国家自然科学基金项目(61073134)；中央高校基本科研业务费项目(3132013015)

马文耀(1980—)，男，湖北潜江人，副教授，博士研究生，主要从事海上交通工程及交通信息工程及控制方面的研究。E-mail: wenyaoma1980@163.com。

U672.5

A

1674-0696(2015)05-130-05