基于特征建模的航行规律挖掘方法.pdf

舰 船 电 子 工 程2023 年第 8 期1引言当前，我国已具备全球大范围海域的目标监视能力1。海量的目标监视数据具有丰富的研究价值，以目标监视数据中的航迹信息为数据源，利用聚类技术对目标航行规律进行挖掘，对于提升海域的态势感知能力具有重要意义。海上交通量迅猛增长，从大量的海上交通轨迹数据中挖掘规律对于智能化的处理水平提出了新的要求。通过航迹聚类，提取出海域中船舶的主要航路信息，用于规范船舶的航行，为海事监管以及船舶交通管理系统提供支持2。船只航迹的聚类研究，是通过度量航迹间的相似度，对相似的航迹进行聚类，提取出目标的运动模式规律3。针对这一问题，研究者提出了许多解决方案。陈锦阳等4以轨迹子段为单位进行相似性匹配，通过改进hausdorff度量，消除了轨迹子段之间的公共偏差。Xinlong Pan等5提出了一种多维hausdorff度量方式，有效地提升了hausdorff在多维空间上的度量能力。张春玮等6采用动态时间收稿日期：2023年2月1日，修回日期：2023年3月12日基金项目：山东省自然科学基金青年基金项目（编号：ZR2021QF103）资助。作者简介：闫婕妤，女，副高级工程师，研究方向：海上态势感知，大数据应用。夏沭涛，男，硕士，讲师，研究方向：信息融合。董凯，男，博士，副教授，研究方向：信息融合。王子玲，女，博士，副教授，研究方向：信息融合。基于特征建模的航行规律挖掘方法闫婕妤1夏沭涛2董凯2王子玲2（1.91001部队北京100841）（2.海军航空大学信息融合研究所烟台264000）摘要对航迹大数据进行分析，利用聚类技术可以挖掘出船只的航行规律。当前航迹聚类研究集中在度量准则和聚类算法的改进上，精细化的设计与多参数的引入往往受限于场景的限制，降低了算法的普适性。论文从度量对象的转化入手，力图能够采用经典的度量准则与聚类算法实现模式挖掘。通过分析船只不同航行规律的特点，提出了一套特征建模方案，将航迹样本转化为特征空间的特征点，从而将原始的航迹矩阵度量，转化为对特征点的度量，即可采用经典的度量与聚类算法进行聚类，经过仿真数据的实验分析，验证了方法的有效性。关键词航行规律挖掘；船只；航迹特征；聚类中图分类号O141.4DOI：10.3969/j.issn.1672-9730.2023.08.011Navigation Law Mining Method Based on Feature ModelingYAN Jieyu1XIA Shutao2DONG Kai2WANG Ziling2（1.No.91001 Troops of PLA，Beijing100841）（2.Institute of Information Fusion，Naval Aviation University，Yantai264000）AbstractBy analyzing the big data of track，the clustering technology can be used to dig out the navigation law.Current research on track clustering focuses on the improvement of measurement criteria and clustering algorithm.Refined design and the introduction of multiple parameters are often limited by the constraints of the scene，which reduces the universality of the algorithm.This paper starts with the transformation of measurement objects and tries to realize pattern mining by using classical measurementcriteria and clustering algorithm.By analyzing the characteristics of different behavior modes of ships，a set of feature modelingscheme is proposed，which converts the track samples into feature points in the feature space，and then converts the original trackmatrix measure into the measure of feature points.The classical measure and clustering algorithm can be used for clustering.The experimental analysis of simulation data verifies the effectiveness of the method.Key Wordsnavigation law mining，ship，trajectories feature，clusteringClass NumberO141.4总第 350 期2023 年第 8 期舰 船 电 子 工 程Ship Electronic EngineeringVol.43 No.853总第350期规整算法来计算航迹之间的相似度，实现了非等长航迹相似度的计算。牟军敏等7基于 hausdorff距离设计了一种具有尺度参数的相似性度量参数，构建相似度矩阵并利用谱聚类算法完成航迹聚类。当前的研究都是在对原始航迹进行相似度度量，航迹空间中的样本点属于多维矩阵，直接对多维矩阵进行度量本身具有很大的复杂性，这为度量准则的设计增加了困难。度量方式的精细化设计在提高度量精确性的同时，降低了度量的普适性。同时多参数的引进也难以满足实际工程应用。完成航迹聚类的关键两步是度量和聚类。度量对象的空间维度直接影响度量方式的设计难度，而度量方式的精确性直接影响到聚类效果。现有研究很少关注度量对象的转化，度量对象通常为原始的多维航迹序列矩阵。针对现有技术的局限性，本文提出了一种船只航行规律挖掘方法。从度量对象所在空间入手，通过分析不同航行规律的运动特点，首先将航迹转化到特征空间进行表示，将原始航迹空间的多维航迹矩阵转化为特征空间中的点，使同一运动模式的航迹在特征空间中表现出强的内聚性，不同模式的航迹表现强的分离性。从而可以通过经典的欧式距离对航迹进行相似度度量，然后采用分级聚类完成模式挖掘。算法更加具有普适性，更能满足工程实际需求。2航迹特征建模2.1航迹表示一条航迹可以表示为Traji=Pi1Pi2Pi3PijPin（1）式中Traji表示第i条航迹，Pij为()xijyij，代表航迹Traji中的第j个点迹，xij为横坐标，yij为纵坐标，n代表航迹Traji中包含的航迹点个数。2.2特征建模对航迹进行聚类是将航行规律相似的航迹聚为同簇，相异的航迹聚为不同簇，因此在对航迹的特征进行建模时，应寻找簇内航迹相似并且簇间航迹相异的特征。航迹的相似性表现在两个方面，一是几何形状的相似性，二是绝对位置的相似性。考虑图1中的航迹示例，共包含三簇航迹A、B、C，每簇包含两条航迹。同簇航迹间的几何形状相似，而异簇航迹间的几何形状具有明显差异。另一方面，B簇和C簇航迹的几何形状也相似，但是由于绝对位置具有明显差异而异簇。通过以上分析，建模特征需要反映航迹几何形状和绝对位置两方面特点。原始航迹点包括()xijyij两维数据，首先计算出每个航迹段的航向值：cij=yi(j+1)-yijxi(j+1)-xijj1n-1（2）利用航迹的位置坐标来反映航迹的位置特征，利用航向来反映航迹的几何形状特征。为准确刻画特征差异，对航迹的横坐标和纵坐标分别取五类统计量，分别为最小值、最大值、均值、上四分位数、下四分位数，作为第1到第10个特征量：f1:f5=minj1nxijmaxj1nxij-xiQ14(xi)Q34(xi)（3）f6:f10=minj1nyijmaxj1nyij-yiQ14(yi)Q34(yi)（4）式中，Q14表示上四分位数，Q34表示下四分位数。对航向值也如此操作，创建第11到第15个特征量：f11:f15=minj1ncijmaxj1ncij-ciQ14(ci)Q34(ci)（5）为了反映在不同位置处的航向，尝试将位置信息与航向信息联系起来，计算每个航迹点处的位置坐标与航向之积：xijyijcijj1n-1，同样对此积取上述五类统计量，创建第16到第20个特征量：f16:f20=minj1nxijyijcijmaxj1nxijyijcij-xiyiciQ14(xiyici)Q34(xiyici)（6）为反映航向的变化特性，计算航向的间隔值：Dcij=ci(j+1)-cijj1n-2（7）对间隔值取均值作为第21个特征量：f21=-Dci（8）特征建模完毕后，利用PCA主成分分析法分析各特征量的重要程度，去除重要程度低的特征量。将保留的特征量组成特征向量，利用t分布-随机近邻 嵌 入（t-distributed stochastic neighbour embedding，t-SNE）算法8将特征向量降至二维，得到航迹特征向量的二维表示。至此，完成航迹矩阵向特征空间的转化，原始航迹矩阵转化为特征空间的点，对于原始航迹的相似度度量转化为特征空间点的度量，即可采用经典的欧式距离进行度量。3聚类算法聚类算法较为流行的有分层聚类算法9、闫婕妤等：基于特征建模的航行规律挖掘方法54舰 船 电 子 工 程2023 年第 8 期k-means10、k-medoids11、具有噪声的基于密度的轨 迹 聚 类（Density-Based Trajectory Clustering ofApplications with Noise，DBTCAN）算法12、谱聚类算法13等。基于参数设置简单易控制、工程易实现的原则，本文首先选取了分层聚类算法对航迹进行聚类，目的为了检验建模特征对于聚类研究的有效性。利用python环境中的scipy.cluster.hierarchy模块即可实现分层聚类，由于本文通过特征建模将航迹矩阵转化为了特征点，即可通过欧式距离进行相似性度量，因此在模块参数中设置度量方式为欧式距离，减轻了度量准则设置的复杂性，算法更具普适性。Traj1Traj2Traj3Traj4Traj5Traj6CBA图1航迹示例4实验分析4.1仿真数据集-1.0-0.50.00.51.0XY1.51.00.50.0-0.5-1.0（a）数据集1Y1.00.50.0-0.5-1.0-1.5-2.0-1.5-1.0-0.50.00.51.01.5X（b）数据集2图2数据集采用Piciarelli14公开的仿真数据集进行实验，图2为两个数据集，每个数据集包含5个簇，每个簇包含50条航迹，每条航迹包含16个航迹点。5个簇代表5种航行规律。4.2特征筛选与可视化分析通过对聚类任务以及航迹特点的分析，设计了共21个特征量，而不同特征量的贡献程度不一定相同，可能存在冗余特征量，因此需要对特征量进行筛选。利用PCA主成分分析法分析各特征量的重要程度，结果如图3所示，去除排名靠后的4个特征量，分别是第17、7、20、18个特征量，共保留17个特征量。利用 t 分布-随机近邻嵌入（t-distributed stochastic neighbour embedding，t-SNE）算法8将特征向量降至二维，得到特征向量的二维表示。绘制散点图图4。图4中，每种颜色表示同一簇的航迹样本，可以看到，同簇航迹表现出强内聚性，不同簇航迹表现出强分离性，初步验证了建模特征的有效性。f3f11f5f12f14f16f1f4f15f8f2f10f13f19f9f21f6f17f7f20f180.070.060.050.040.030.020.010图3特征量贡献度4.3聚类实验对航迹提取特征后，将原始的航迹矩阵转化为了特征空间中的特征点，采用经典的欧式距离为度量准则，利用分层聚类算法对航迹进行聚类。可以通过设置最大聚类簇数实现不同层级的聚类，图5为两个数据集在簇数等级为5时的聚类效果，每种颜色表示一簇，可见建模特征可以准确体现不同簇航迹间的差异，可以利用欧式距离进行度量实现聚类。在图6中，簇数等级设置为3，依然可以满足聚类需求，实现分层聚类效果，簇数等级可根据实际需求进行设定，簇数等级为本实验参数，参数意义更加接近工程需求层面。4.4对比实验本节将所提方法与流行的基于Hausdorff度量的密度聚类进行对比，选取的指标为轮廓系数与运行时间。轮廓系数是刻画同簇内聚性和异簇分离性的重要指标，计算公式为55总第350期S=1Ni=1Nbi-aimaxaibi式中，ai和bi的计算公式分别为ai=1Nij=1jiNitrajitrajjbi=mintrajitrajjjNi+1Nai表示样本i与同簇其它样本距离的平均值，bi表示样本i与异簇样本距离的最小值。轮廓系数的取值范围为-11，越接近于1表示同簇内聚性和异簇分离性越优。-10-5051015第一维86420-2-4-6第二轴（a）数据集1特征可视化1050-5-10第二轴-10-5051015第一维（b）数据集2特征可视化图4数据集特征可视化此外，本节还对比了利用k-means以及k-medoids聚类算法的聚类表现。表1为实验结果，在两个数据集上，本文所提出的特征构建方法以及Hausdorff度量+密度聚类方法的轮廓系数均较为理想，但是本文方法的轮廓系数均超过基于Hausdorff度量的密度聚类，说明本文建模特征在不同的航行规律之间具有更加优异的判别性，能够将不同簇的航迹更好地区分开，并且将同簇的航迹内聚在一起。运行时间也大幅降低，本实验中的运行时间都是从输入原始航迹数据开始到聚类结束的时间，即本文方法的运行时间包括了航迹特征提取降维的过程。由于直接对原始航迹数据进行Hausdorff度量，遍历计算多，导致计算量大，因此运行时间较长。而通过特征建模，在特征空间中直接对特征点进行欧式度量，计算量大幅降低，运行时间减少。更加符合工程需求。此外，利用本文的特征构建方法，分层聚类的运行时间最短；k-means算法以及k-medoids算法受初始中心点选择影响较大，会出现陷入局部最优的情况，k-medoids算法迭代运算次数较多，计算量大，耗时长，综合来看，分层聚类在本任务中较优异。-101X10-1Y10-1Y-2-101X（a）数据集1聚类结果（b）数据集2聚类结果图5聚类结果1-101X10-1Y10-1Y-2-101X（a）数据集1聚类结果（b）数据集2聚类结果图6聚类结果2表1算法性能比较算法本文方法特征构建+kmean聚类特征构建+k-medoids聚类Hausdorff度量+密度聚类数据集1轮廓系数0.85710.85710.85710.7960运行时间14.568s14.66318.76488.927s数据集2轮廓系数0.92910.92910.92910.7274运行时间14.536s14.89717.48591.088s5结语本文针对船只航行规律挖掘，提出了一种基于特征距离聚类方法，并且通过仿真数据以及实测数据进行了验证。在航迹聚类问题中，研究热点多集中在度量准则和聚类算法的改进上，精细化的设计与多参数的引入，增加了算法的复杂度，降低了度量的普适性。本文从度量对象的转化方面入手，通闫婕妤等：基于特征建模的航行规律挖掘方法56舰 船 电 子 工 程2023 年第 8 期过分析船只的航行规律特点，提出了一套特征建模方案，将对原始航迹矩阵的度量转化为特征空间中特征点的欧式度量，通过转化操作，使度量对象的同簇样本更加内聚，异簇样本更加分离，提高了聚类的鲁棒性。采用欧式距离进行度量，更具普适性。参 考 文 献1黄晓栋.天基海洋目标信息感知与融合技术探讨 J.上海信息化，2020（12）：33-36.2肖潇，邵哲平，潘家财，等.基于AIS 信息的船舶轨迹聚类模型及应用 J.中国航海，2015，38（2）：8286.3Liao T W.Clustering of time series dataa survey J.Pattern Recognition，2005，38（11）：1857-1874.4陈锦阳，宋加涛，刘良旭，等.基于改进Hausdorff距离的轨迹聚类算法J.计算机工程，2012，38（17）：157-161.5Pan X，Wang H，You H，et al.Online classification of frequent behaviours based on multidimensional trajectoriesJ.IET Radar Sonar&Navigation，2017，11（7）：1147-1154.6张春玮，马杰，牛元淼，等.基于行为特征相似度的船舶轨迹聚类方法 J.武汉理工大学学报：交通科学与工程版，2019，43（3）：517-521.7牟军敏，陈鹏飞，贺益雄，等.船舶AIS轨迹快速自适应谱聚类算法 J.哈尔滨工程大学学报，2018，39（3）：428-432.8Laurens V D M，Hinton G.Visualizing Data using t-SNEJ.Journal of Machine Learning Research，2008，9（2605）：2579-2605.9Karypis G，Han E H，Kumar V.Chameleon：Hierarchicalclustering using dynamic modeling J.computer，1999，32（8）：68-75.10KANUNGO T，MOUNT D M，NETANYAHU N S，et al.An efficient k-means clustering algorithm：analysis andimplementation J.IEEE Transactions on Pattern Analysis&Machine Intelligence，2002，24（7）：881-892.11 HAE-SANG，PARK，CHI-HYUCK，JUN.A simpleand fast algorithm for K-medoids clustering-ScienceDirectJ.Expert Systems with Applications，2009，36（2）：3336-3341.12Ester M，Kriegel H P，Sander J，et al.A density-basedalgorithm for discovering clusters in large spatial databases with noiseC/Proc.int.conf.knowledg Discovery&Data Mining，1996，96（34）：226-231.13 Maheswari K，Ramakrishnan M.Kernelized SpectralClustering based Conditional MapReduce function withbig data J.International Journal of Computers and Applications，2021，43（7）：601-611.14 Piciarelli C，Micheloni C，Foresti G L.Trajectory-Based Anomalous Event Detection J.IEEE Transactions on Circuits&Systems for Video Technology，2008，18（11）：1544-1554.57