基于改进谱聚类算法的航路辨识

李爽　史国友　高邈　陈晓　吴京霖

摘要：

為解决船舶自动识别系统（automatic identification system， AIS）数据挖掘不够充分，对航路辨识分析不够全面等问题，提出一种基于改进谱聚类算法的数据挖掘方式。利用Sliding Window算法对船舶轨迹AIS数据进行压缩，减少数据冗余提高聚类效率。改进亲和距离函数，提出新的亲和矩阵的标准，提高聚类的稳定性，进一步对数据去噪，减少噪声敏感。通过优化初始中心对k均值算法进行改进，优化全局搜索能力，缓解初始值的选取对聚类效果的影响。以天津港AIS数据为样本进行算法验证。结果表明，该聚类算法能准确提取和划分某水域船舶主要航迹段，算法消耗系统资源少，计算速度快。改进后的算法可为航路辨识、分道通航制定等提供理论支持。

关键词：

航路辨识; 谱聚类; 船舶自动识别系统（AIS）; 大数据; k均值算法

中图分类号：U675.7

文献标志码：A

收稿日期： 2019-01-05

修回日期： 2019-04-12

基金项目：

国家自然科学基金（51709165）;辽宁省自然科学基金（20170540090）

作者简介：

李爽（1995—），女，山东菏泽人，硕士研究生，研究方向为交通运输工程，（E-mail）641094939@qq.com;

史国友（1968—），男，安徽桐城人，教授，博导，博士，研究方向为船舶智能避碰，（E-mail）sgydmu@dlmu.edu.cn

Route identification based on improved spectral clustering algorithm

LI Shuanga，b， SHI Guoyoua，b， GAO Miaoa，b， CHEN Xiaoa，b， WU Jinglina，b

（

a. Navigation College; b. Key Laboratory of Navigation Safety Guarantee of Liaoning Province，

Dalian Maritime University， Dalian 116026， Liaoning， China）

Abstract：

In order to solve the problem that automatic identification system （AIS） data mining is not enough and the analysis of route identification is not comprehensive enough， a data mining method based on the improved spectral clustering algorithm is proposed. The Sliding Window algorithm is used to compress AIS data of ship trajectory so as to reduce data redundancy and improve the clustering efficiency. The affinity distance function is improved， a new affinity matrix standard is proposed to improve the stability of clustering， and the data denoising is carried out to reduce the noise sensitivity. The k-means algorithm is improved by optimizing the initial center so as to optimize the global search ability and alleviate the impact of the initial value selection on the clustering effect. The AIS data of Tianjin Port is taken as a sample to verify the algorithm. The results show that， the clustering algorithm can accurately extract and divide the main track segments of ships in a certain water area， and the algorithm consumes less system resources and has faster calculation speed. The improved algorithm can provide theoretical support for route identification， traffic separation， and so on.

Key words：

route identification; spectral clustering; automatic identification system （AIS）; big data; k-means algorithm

0 引 言

云计算、无人化、智能化等新技术、新概念的发展，为工作人员处理海量船舶自动识别系统（automatic identification system，AIS）数据中包含的各种信息提供了可能。《国际海上人命安全公约》（SOLAS公约）规定，所有300总吨及以上的国际航行船舶，非国际航行的500总吨及以上的货船和不论大小的客船应按要求配备AIS。随着各国AIS基站网络的建立和星载AIS群的出现，AIS数据的收集也得到了解决，AIS已成为实时的全球海上交通信息来源[1]。AIS数据为多元多维数据，包含各种船舶信息，AIS轨迹数据可描述船舶的空间位置和其他时空属性。

聚类算法是数据挖掘中描述数据状态的重要算法。传统聚类方法主要有基于划分的算法、基于密度的算法和基于层次的算法。基于划分的算法，如k均值算法、k中心点算法和EM算法等，适用于数据量较小的凸集。张玉芳等[2]基于取样的划分思想，提出一种改进的k均值算法，在一定程度上避免了聚类结果陷入局部解的现象，减少了原始k均值算法因采用误差平方和准则函数而将大的聚类簇分割开的情况;TAHIRI等[3]提出将一次计算距离矩阵用在每个迭代步骤中寻找新的中间体的新的k中心点算法;何彬彬等[4]提出基于EM和Delaunay三角网的船舶轨迹划分，排除了空间聚类的随机性。基于密度的算法主要有DBSCAN和OPTICS等。DBSCAN算法[5]可以根据密度划分聚类，构建任意聚类簇，但是参数设置依赖大量实验且需自主定义。OPTICS算法是ANKERST等[6]为解决DBSCAN算法参数设置问题而提出的自动交互式聚类算法，但该类算法占用内存空间大，运行效率低，无法解决非凸问题。EDLA等[7]提出选取网格的新方法，但是网格算法主要依赖网格划分单元的质量，对聚类效果影响较大。基于层次的算法有BIRCH[8]、CURE[9]等，适用于任何聚类形状和聚类层次，但是计算时间较长，算法终止条件很难确定。

谱聚类的思想来源于谱图划分理论，通过设计数据点集、建立无向加权图、进行图论划分构造特征矩阵和特征向量，从而进行低维矩阵的聚类，使同一类子图之间划分相关性最大，不同类子图之间划分相关性最小，是一种依靠相关性的亲和聚类方式[10]。传统的谱聚类算法主要用于VLSI设计、计算机视觉、图像分割、文本挖掘和生物信息挖掘等领域[11]，目前已经发展出SM算法、NJW算法等经典的谱聚类算法，但是这些算法大多只能用于解决特例问题，不存在解决各种实际问题的通用算法。

关于谱聚类算法：ZOU等[12]将约束条件引入相似矩阵求解中，但是未考虑在低维子空间内k均值算法受k值和初始值的影响;NG等[13]提出NJW算法;ZHOU等[14]提出基于约束的谱聚类算法，该算法考虑无监督学习时聚类目标产生的目标函数不适用于实际问题的情况;曹妍妍等[15]提出了一种改进Hausdroff距离和谱聚类的车辆轨迹模式学习方法，得到符合实际情况的聚类结果，但是未应用在复杂路口的轨迹聚类。在航海领域，国内外学者主要基于AIS数据进行谱聚类分析：马文耀等[16]改进了谱聚类中的相似距离，采用单向距离进行轨迹相似度度量，得到船舶运动模式，降低噪声容忍度。然而，上述谱聚类算法未考虑低维空间聚类处理时k均值算法对初始值敏感、易陷入局部最优等情况。

本文采用基于改进谱聚类算法的数据挖掘方式，利用Sliding Window算法对船舶轨迹AIS数据进行压缩，减少数据冗余，提高聚类效率;通过改进亲和距离函数，减少噪声敏感;通过优化初始中心对k均值算法进行改进，优化全局搜索能力，缓解初始值的选取对聚类效果的影响，从而提高聚类技术在航路辨识方面的能力。

1 谱聚类算法模型

本文对NG等[13]提出的多路谱聚类下的NJW算法进行改进，主要步骤如下：

步骤1 构造亲和距离函数，建立亲和矩阵，使数据由点集到图论进行转化，建立无向加权图。

步骤2 基于准则或邻近准则稀疏化无向加权图。

步骤3 建立度函数，构造拉普拉斯矩阵，获得规则的矩阵形式的數据关系。

步骤4 求解拉普拉斯矩阵前k个特征向量，其特征值λi从大到小排列，建立k阶矩阵，k=arg max|λi+1-λi|。

步骤5 对矩阵行向量做k均值算法聚类处理，得到划分聚类结果。

通过对AIS数据进行样本间相似处理，得到样本间的亲和距离以进行相似度衡量，从而得到相似度函数，即亲和距离函数：

s（xi，xj）=exp-D2δxiδxj

（1）

式中：D为马氏距离;

尺度参数δ表示相似性与距离之间的增减关系。在对尺度参数的选取中，应充分考虑：当尺度参数过小时，噪声的影响过大;当尺度参数过大时，亲和矩阵变量振荡较大，难以进行有效选取。因此，对尺度参数的选取应十分谨慎。本文采用信息熵确定尺度参数。

对聚类对象，构造亲和矩阵

[WTHX]S[WTBX]=（sij）n×n，

s[WTBX]ij=0，i=j

s（xi，xj），i≠j（2）

在聚类中，对k的选取引入本征间隙的概念。本征间隙是相邻特征值的差值（|λt+1-λt|，t=1，2，…，k），第一个极大本征间隙的存在即表示聚类数目的存在。这是因为根据矩阵摄动理论，本征间隙与子空间的稳定性成比例关系，间隙越大稳定性越高。因此，计算聚类数目k值的问题转化为找寻拉普拉斯矩阵最大本征间隙的问题。通过该方法，可以避免对k值的选择，得到较为合适的k值。当k值过小时，聚类簇较少，聚类划分粗糙，不易识别人工难以识别的航路，不易区分密度可达情况;当k值过大时，聚类划分中噪声比例增大，影响对可研究航路的辨识。

2 改进的谱聚类算法

本文运用上述谱聚类算法模型，通过改进马氏距离对船舶数据距离进行采集，得出亲和距离模型和亲和矩阵表达方式，得出度矩阵和拉普拉斯矩阵，计算得出运动模式k的值，最后运用改进k均值聚类初始中心的算法得到最终聚类结果。改进谱聚类航路辨识流程见图1。

2.1 数据处理的改进

为解决庞大的AIS数据难以有效集成、收集和存储等问题，使用数据压缩处理办法，在合理的有效阈值范围内减少计算量，进行矩阵降维处理。处理后得到的数据更为精简，且有效数据得以保留。

Sliding Window算法是经典数据压缩算法之一，其主要思想是采用逐步压缩的形式，始终对3个点

进行压缩。设定P1为特征点，当P2与P1、P3点连线的欧氏距离小于阈值时，舍弃中间点，加入P4，以此类推。高邈等[17]应用改进的Sliding Window算法，考虑风流压差角，确定距离阈值、角度阈值，建立了有效的船舶轨迹数据价值评价模型，在对大数据进行压缩时可有效利用推荐阈值进行选择，保留船舶轨迹细节，达到AIS数据处理片段化的目的。

本文采用改进的Sliding Window算法对数据进

行压缩。该算法可降低压缩风险、提高压缩效率，在数据持续更新状态下一直保持压缩状态。该算法充分考虑船舶航行中船舶姿态等因素对船舶轨迹的影响，失真率较低，且时间复杂度为O（n+1）（n为数据点数量），算法运行有较大优势。

选取2015年12月天津港水域（38°09′30″～39°08′56″N，117°23′40″～120°03′06E）的AIS数据进行压缩，压缩前为20 971 520个，压缩后为1 048 576个。压缩前后船舶轨迹对比见图2。

a）压缩前

b）压缩后

2.2 亲和距离的改进

对于谱聚类算法来说，亲和距离的计算是关键一步，是构造亲和矩阵的基础。当前基于船舶轨迹的聚类方法主要有欧氏距离、Hausdorff距离、结构化距离等，其中：欧氏距离适用于计算距离下限，但是缺少量纲转化，仅适用于矩阵密集、密度均匀的数据和同等船长的船舶中，大数据使用效果不佳;Hausdorff距离处理过程中虽然不添加轨迹噪声，但对已存在的噪声缺乏敏感性;结构化距离处理过程中易忽视船舶轨迹自身黏性粘连，易陷入局部最优，忽略轨迹聚类簇中集中聚类等惯性问题。马氏距离

是欧几里得空间内非均匀分布的归一化距离，不用考虑各特征参数的量纲，可以将整个空间内的特征分布情况作为判断依据，表征特征数据间的耦合关系，排除样本间相关性的影响。因此，本文采用改进的马氏距离建立亲和矩阵。

设

式中：上标H表示对矩阵的共轭转置。

改进的马氏距离可重新定义为

2.3 改进k均值算法模型建立

传统谱聚类算法主要

利用k均值算法进行最后的低维子空间的聚类处理，虽然更便于得到结果，但是k均值算法对初始聚类划分簇选取敏感，初始值不同可能导致聚类效果不同，容易陷入局部最优，导致维度灾难。本文采取一种改进初始聚类中心[21]的k均值算法来解决对初始值敏感和局部最优问题。

初始聚类中心的选取对聚类的结果影响很大，若初始中心的选取存在问题，则会导致聚类结果不准确。本文提出基于核心点的密度初始中心的选取方法，采用点集密度的思想，借鉴DBSCAN基于密度的算法思想，设定核心密度半径（即邻域半径）r和核心极域集（即最小密度点数）f，選取核心点内的中心点作为聚类初始中心的位置，补充其算法中局部最优和对初始值敏感的问题。具体概念如下：

核心点密度ρ：以点集内任意一点为中心，以r为半径作球体模拟，球体内包含的所有点集称为核心点密度ρ，r为核心密度半径。球体内的点越多，核心点密度就越大，反之就越小。

核心极域集f：以半径为r的高维球体组成核心域，J（p，q）为p与q两个对象间的距离，这里采用欧氏距离表示。设f=intm/25， int函数为取整函数，m为数据集的数量，此处取f=20。

核心密度半径r：设定V为数据集的容积，n为维度数量，ε为阈值，Γ为伽马函数，则

核心点：R区域内的点集d，对于得到的r和f，当d>f时，定义d为核心点集，反之，定义d为非核心点集。

综上所述，改进k均值聚类算法模型建立流程如下：

1）根据特征向量构造特征矩阵

的每行看作待改进的k均值空间内的一点。

2）根据核心极阈集f计算核心密度半径r。

3）根据r计算遍历每个点，计算点集之间的距离，得出相似度矩阵

4）遍历第一个点到所有点的距离，找到在半径r范围内的点，根据|[WTHX]d[WTBX]|的大小，区分核心点与非核心点，得到核心点集。

5）遍历所有核心点，取核心点中心点作为改进后的k均值的聚类中心，当聚类中心阈值小于设定值时聚类结束。

6）完成k均值最终聚类。

3 实验与验证

本文基于Python语言与Spyder的集成开发环境平台，编写基于AIS数据的常规航路特征提取程序并进行实验。

相较于传统聚类算法，谱聚类算法对初始输入数据不敏感，具有识别非凸数据的能力，且理解简单，时间复杂度较低。目前在航海领域使用较多的聚类算法是DBSCAN算法，但是该算法的聚类效果重度依赖输入的参数，聚类结果波动幅度较大，对初始数据比较敏感，未考虑轨迹特征的整体形状，且内存占用较大，运行较慢;k均值算法是聚类算法中的一种简单、快速的算法，在大型数据集处理中，可保持优质的数据伸缩效率，但是该算法易导致局部最优，不适用于非凸集，对噪声较为敏感，在谱聚类中一般用于已做高维处理的低维矩阵聚类的处理。本文将改进谱聚类算法与DBSCAN算法对比，从聚类簇数、时间和聚类精度上进行分析，对比结果见图3。

a）DBSCAN算法

b）改进谱聚类算法

根据图3，采用DBSCAN算法得到的聚类簇为456条，而采用本文提出的经过Sliding Window压缩改进后的谱聚类算法得到的聚类簇为312条。因为水中船舶的航行与陆地上车辆的行驶不同，船舶航行的水域没有明确的航道，所以单纯考虑密度可达。采用DBSCAN算法得到的可聚类簇数多于本文算法，但是其中有很多无效类簇;本文算法可在改进数据处理时舍弃大量无效数据，减少无关类簇对聚类结果的影响。在算法消耗时间方面，采用本文算法的计算时间为32 min，而采用DBSCAN算法的计算时间长达117 min。

在算法复杂度方面，谱聚类在构建相似度时需要的时间复

杂度为O（n2），在计算特征值对应特征向量时其时间复杂度为O（m3）+（O（nm）+O（nt））·O（p（m-k）），其中：p是算法每次执行时迭代的次数，参数m的取值为k的几倍大小。对特征矩阵运行k均值算法，时间复杂度为O（lnk2），其中l为k均值算法迭代次数。分析可得，构建相似度环节是时间复杂度最高的环节，求解拉普拉斯矩阵的前k个特征向量也需要相当长的时间和相当多的内存。本文通过使用Sliding Window压缩算法压缩AIS数据，改善了谱聚类算法中相似矩阵处理环节资源占用、运行困难的情况，可在数据规模不断增长的情况下，保持聚类的质量和速度;DBSCAN算法的时间复杂度为O（nlog n）[22]。

在算法精度对比方面，以船舶通过分道通航区域A为例，采用DBSCAN算法只能提取到A、B两种航路特征模式（见图4），采用本文算法可提取到A1、A2、B1、B2四种航路特征模式（见图5）。

由图4可知DBSCAN算法的密度可达性，当只有一个核心对象时DBSCAN算法可成功识别该类

簇，当在其邻域内有多个核心对象时导出最大的密度相连集合，DBSCAN算法就仅识别一类簇，因此DBSCAN算法不可识别船舶在航行中存在交叉航路和叠加航路等情况。谱聚类算法[23]可克服DBSCAN算法的这一弊端，可发现船舶航行过程中产生的多组聚类簇，获得更合理的航路辨识效果。

4 结 论

谱聚类可以克服其他聚类需要设置参数、消耗内存大、运行速率慢、聚类效果差、聚类划分粗糙等弊端;通过改进亲和距离，优化相似度，避免DBSCAN密度可达导致的初始点相同但整体不同仍被分为一类的情况;改进k均值中初始值选取的准确性，使聚类划分更为合理。经过改进后的谱聚类算法，能够发现人工无法发现的异同，计算结果较为合理。该算法可应用在船舶习惯航路的识别，可以为航路辨识、航路规划、分道通航制定和异常行为数据识别提供理论支持。目前，在AIS数据挖掘、航路特征提取方面还面临很多挑战，聚类参数的选取有待改进，对聚类结果的评价仍没有统一的标准，这是今后需要重点研究的问题。

参考文献：

[1]

GAO Miao， SHI Guoyou， LI Shuang. Online prediction of ship behavior with automatic identification system sensor data using bidirectional long short-term memory recurrent neural network[J]. Sensors， 2018， 18（12）. DOI： 10.3390/s18124211.

[2]張玉芳， 毛嘉莉， 熊忠阳. 一种改进的k-means算法[J]. 计算机应用， 2003， 23（8）： 31-33.

[3]TAHIRI N， WILLEMS M， MAKARENKOV V. A new fast method for inferring multiple consensus trees using k-medoids[J]. BMC Evolutionary Biology， 2018， 18（1）： 48. DOI： 10.1186/s12862-018-1163-8.

[4]何彬彬， 方濤， 郭达志. 基于不确定性的空间聚类[J]. 计算机科学， 2004， 31（11）： 196-198. DOI： 10.3969/j.issn.1002-137X.2004.11.053.

[5]TRAN T N， DRAB K， DASZYKOWSKI M. Revised DBSCAN algorithm to cluster data with dense adjacent clusters[J].Chemometrics and Intelligent Laboratory Systems， 2013， 120（15）： 92-96. DOI： 10.1016/j.chemolab.2012.11.006.

[6]ANKERST M， BREUNING M M， KRIEGEL H， et al. OPTICS： ordering points to identify the clustering structure[C]//ACM SIGMOD99 International Conference on Management of Data. ACM SIGMOD Record，1999， 28（2）： 49-60.

[7]EDLA D R， JANA P K. A grid clustering algorithm using cluster boundaries[C]//Information & Communication Technologies. IEEE， 2013： 254-259. DOI： 10.1109/WICT.2012.6409084.

[8]TIAN Z， RAMAKRISHNAN R， LIVNY M. BIRCH： a new data clustering algorithm and its applications[J]. Data Mining & Knowledge Discov-ery， 1997， 1（2）： 141-182. DOI： 10.1023/a：1009783824328.

[9]LATHIYA P， RANI R. Improved CURE clustering for big data using Hadoop and Mapreduce[C]//International Conference on Inventive Computation Technologies. Coimbatore. IEEE， 2017： 1-5. DOI： 10.1109/INVENTIVE.2016.7830238.

[10]朱光辉， 黄圣彬， 袁春风. SCoS： 基于Spark的并行谱聚类算法设计与实现[J]. 计算机学报， 2018， 41（4）： 868-885. DOI： 10.11897/SP.J.1016.2018.00868.

[11]王贝贝， 杨明， 燕慧超. 基于改进谱聚类算法在图像分割中的应用[J]. 河北工业科技， 2018， 35（1）： 55-60. DOI： 10.7535/hbgykj.2018yx01010.

[12]ZOU Haishuang， ZHOU Weida， ZHANG Li， et al. A new constrained spectral clustering for SAR image segmentation[C]//Asian-Pacific Conference on Synthetic Aperture Radar. IEEE， 2010： 680-683. DOI： 10.1109/APSAR.2009.5374114.

[13]NG A Y， JORDAN M I， WEISS Y. On spectral clustering： analysis and an algorithm[J]. Advances in Neural Information Processing Systems， 2002， 2（14）： 849-856.

[14]ZHOU Zhiping， JIA Xuan， ZHAO Xiaoxiao. A new constraint spectral clustering algorithm[C]//Control & Decision Conference. IEEE， 2017： 6664-6668. DOI： 10.1109/CCDC.2017.7978376.

[15]曹妍妍， 崔志明， 吳健， 等. 一种改进Hausdorff距离和谱聚类的车辆轨迹模式学习方法[J]. 计算机应用与软件， 2012， 29（5）： 38-40. DOI： 10.3969/j.issn.1000-386X.2012.05.011.

[16]马文耀， 吴兆麟， 杨家轩， 等. 基于单向距离的谱聚类船舶运动模式辨识[J]. 重庆交通大学学报（自然科学版）， 2015， 34（5）： 130-134. DOI： 10.3969/j.issn.1674-0696.2015.05.26.

[17]高邈， 史国友， 李伟峰. 改进的Sliding Window在线船舶AIS轨迹数据压缩算法[J]. 交通运输工程学报， 2018， 18（3）： 218-227.

[18]XIANG Shiming， NIE Feiping， ZHANG Changshui. Learning a Mahalanobis distance metric for data clustering and classification[J]. Pattern Recognition， 2008， 41（12）： 3600-3612. DOI： 10.1016/j.patcog.2008.05.018.

[19]KATSIKIS V N， PAPPAS D， PETRALIAS A. An improved method for the computation of the Moore-Penrose inverse matrix[J]. Applied Mathematics & Computation， 2011， 217（23）： 9828-9834. DOI： 10.1016/j.amc.2011.04.080.

[20]张小波. Moore-Penrose逆的表示及扰动分析[D]. 上海： 上海师范大学， 2016.

[21]杨艳， 许道云. 优化加权核k-means聚类初始中心点的SLIC算法[J]. 计算机科学与探索， 2018， 12（3）： 494-501. DOI： 10.3778/j.issn.1673-9418.1708034.

[22]YUAN Guan， SUN Penghui， ZHAO Jie， et al. A review of moving object trajectory clustering algorithms[J]. Artificial Intelligence Review， 2017， 47（1）： 123-144. DOI： 10.1007/s10462-016-9477-7.

[23]牟军敏， 陈鹏飞， 贺益雄. 船舶AIS轨迹快速自适应谱聚类算法[J]. 哈尔滨工程大学学报， 2018， 39（3）： 428-432. DOI： 10.11990/jheu.201609033.

（编辑 贾裙平）