多算法结合的船舶交通流框架提取

本文格式为Word版，下载可任意编辑——多算法结合的船舶交通流框架提取v，则说明在点Pi附近，点Pi邻域内的密度最大，点Pi为该区域的密度点，保存点Pi;若u≤v，则说明在点Pi附近，点Qm邻域内的密度最大，点Qm为该区域的密度点，则包含点Pi在内的Qm邻域内的所有数据点都将被聚类到点Qm，保存点Qm。然后依次遍历所有数据点，即完成一次聚类。

以上一次聚类得到的密度点为基础，增大阈值，再进行聚类;随着迭代次数的增加，被聚类的数据点越来越多，密度点渐渐成为全局密度的局部最大点;当取到最终阈值时，密度聚类完成。密度聚类示意图见图2。用密度点吸收的点数表示其权重，点数越多，权重就越大，该点附近的点密度就越大。为直观显示密度点权重大小，权重越大的密度点在图中显示的尺寸越大。

1.2Douglas-Peucker压缩算法

1973年，Douglas等提出一種简化二维曲线的算法，其核心思想是从构成曲线的点集中提取出能反映曲线总体和局部形态主要特征的另一个点集。该算法步骤如下：将一段航迹线上首

点P1与尾点P2之间的连线称为基线，依次计算这段航迹线上各点到基线的距离，并找出最大距离D对应的点P3。设定阈值δ，若D≤δ，则表示该段航迹线向两舷偏离的距离小于D，即该段航迹线没有明显转折，则用基线代替原航迹线，只保存P1、P2两点即可;若D>δ，则将最大距离D对应的点P3作为分裂点（转向点），并分别与初始点P1、P2连接，得到两组新的首点、尾点和基线。依次递归选取分裂点和分段航迹线，直到整条航迹线上不再出现新的分裂点[5]。

图3为Douglas-Peucker压缩示意图。

设点P1、P2和P3的坐标分别为（x1，y1）、（x2，y2）和（x3，y3），则有D=（y2-y1）x3+（x1-x2）y3+x2y1-x1y2（y2-y1）2+（x2-x1）2

1.3航迹交会算法

船舶航迹密集交会处寻常是海上交通状况对比繁杂的地方，在这一区域，各船航向、航速往往不同，通航状况繁杂，因此交会点也是船舶交通流的重要特征点之一。

航迹交会算法原理：取某条航迹线上相

邻两点Mi和Mi+1，取另一条航迹线上相邻两点Nj和Nj+1，连接Mi、Mi+1得线段MiMi+1，连接Nj、Nj+1得线段NjNj+1，分别设这两条线段的斜率为k1、k2。若k1、k2都不存在，则两直线竖直平行;若k1=k2=0，则两直线水平平行。两直线平行，不存在交点。若k1≠0或k2≠0，则在二维平面内两直线必相交，此时先求得两直线交点E，再判断该交点是否在线段MiMi+1和NjNj+1上，若在，则点E即为所求的交会点。对于每条航迹线上相邻两点之间的线段，均按上述方法判断其与其余所有航迹线有无交点，逐个遍历所有航迹线，即可得到该组AIS数据的所有交会点。图4为交会点提取示意图。

设点Mi、Mi+1、Nj、Nj+1和E的坐标分别为（x6，y6）、（x7，y7）、（x8，y8）、（x9，y9）和（x10，y10），则相关公式如下：

k1=y7-y6x7-x6，k2=y9-y8x9-x8

x10=（x7-x6）（x8y9-x9y8）-（x9-x8）（x6y7-x7y6）（y6-y7）（x9-x8）-（y8-y9）（x7-x6）y10=（y8-y9）（x6y7-x7y6）-（y6-y7）（x8y9-x9y8）（y6-y7）（x9-x8）-（y8-y9）（x7-x6）k1≠0，k2≠0

x10=（（x8-x9）y6+x9y8-x8y9）/（y8-y9）

y10=y6k1=0，k2≠0

x10=（（x6-x7）y8+x7y6-x6y7）/（y8-y9）

y10=y8k1≠0，k2=0

x10=x8，y10=y6k1=0，k2不存在

x10=x8y10=（（y7-y6）x8+x7y6-x6y7）/（y7-y6）

k1≠0，k2不存在

x10=x6，y10=y8k1不存在，k2=0

x10=x6y10=（（y9-y8）x6+x9y8-x8y9）/（x9-x8）

k1不存在，k2≠0

1.4加权融合算法

通过Douglas-Peucker压缩算法得到的转向点、通过航迹交会算法得到的交会点和原有的船位点分别为船舶交通流的3种特征点，对这3种特征点分别进行密度聚类，得到相应的密度点，然后将这3种特征密度点集中显示。由于转向点和交会点是基于算法从船位點中提取出来的，其数据量远小于船位点的初始数据量，若直接按权重显示，则转向点和交会点的聚类密度相较于船位点的聚类密度几乎可以忽视不计，这违背了本文的初衷;此外，由于最终密度点的权重很大，直接显示可能会使各点难以区分，影响视觉效果。鉴于以上原因，对不同类型特征点进行加权显示。具体来说，就是分别成比例地放大或缩小3种特征点的权重值，放大或缩小比例的设置需要考虑原始船位点的数据量、特征点在交通流框架中的重要程度和最终的可视化效果。例如：10000个船位点经过Douglas-Peucker压缩算法得到200个转向点，其整体权重值相当于缩小为原来的1/50，考虑本文的交通流框架是以船位密度点为主体的，转向点权重的放大倍数可先取50的60%～80%，如30，然后统一调整使可视化效果最正确。这样充分考虑了3种特征点的影响，显示了不同类型特征点之间的位置关系，可更直观地判断船舶交通流的整体航迹特征和宏观态势，达到更好的视觉效果，如图5所示。

对交通流网络中位置相近的3种特征点进行加权融合（见图6），提取出4种新的融合特征点，即“船位+转向+交会点〞、“船位+转向点〞、“船位+交会点〞和“转向+交会点〞。它们能够表现该点附近的多种航迹特征，与原有的3种特征点一起共同作为该交通流框架的重要节点。

设共有ω个被融合点，融合后点的总权重为W;被融合点坐标为（xτ，yτ），权重为wτ，τ=1，2，…，ω。第τ个被融合点的权重占比rτ=wτ/W，各点加权可得融合点的坐标（X，Y）。

X=ωτ=1（xτrτ），Y=ωτ=1（yτrτ）

2实例验证与分析

选定老铁山水道附近水域（38.3217～38.7471°N，120.4319～121.4319°E），从AIS数据中提取2022年3月11日至3月14日过往船舶的动态信息，并对其进行解码，共得到126408个船位点数据。对解码的AIS信息进行预处理，主要包括数据清理和数据转换。数据清理主要是为了将数据挖掘过程中的异常点、错误信息以及无用信息去除;数据转换是为了修正原始数据以更有利于数据挖掘。对不同航行状态船舶的AIS数据进行时间等距差分，统一初始时间和船载信息更新时间间隔，以及等比例转换各船舶信息的时间戳和船位，在时空上保证AIS船位点数据的一致性。经过数据预处理，将212条航迹线上共计126193个船位点数据作为试验对象，将其经纬度坐标转换为墨卡托坐标，以便在海图上显示。整体实现流程见图7。

2.1船位点密度聚类

为使最终聚类得到的船位点坐标更加确切，采用渐渐增大阈值的方法，以上一层的输出数据作为

下一层的输入数据，依次聚类。随着阈值的不断增

大，等差增大阈值的聚类效果会渐渐变差，需渐渐增大阈值差：阈值最初取300，600，…，1800m，每次增加300m;而后取2400，3000m，每次增加600m;最终取4200，5400m，每次增加1200m。聚类过程中，不同阈值下的船位点数和压缩率如表1所示，这里的压缩率是根据上一层数据（而非初始数据）计算得出的。

从表1可以看出，在阈值差相等的状况下，除首次压缩外，其他各次的压缩率随阀值增大渐渐减小，至阈值取1800m和3000m时，对上一层的压缩率已不足20%，因此可增大阈值差以获得更好的聚类效果。截止到最终阈值5400m时，对初始数据的压缩率已经达到99%以上。

由于密度聚类不限于单条航迹线，聚类后同一船位点可能位于多条航迹线上，压缩后的船位点数为各条航迹线上船位点数之和，因此最终1229个船位点会包含大量点的屡屡计量，实际船位点数远小于此。此外，聚类完成后，删除船位点网络中权重小于600的低密度点，最终得到33个船位点。图8为部分不同阈值下船位点密度聚类效果图，图8f为在图8e的基础上删掉权重小于600的船位点所得的最终效果图。

从图8可以看出：聚类后的船位点几乎都在交通流最密集的区域，而且该船位点网络两头宽、中间窄，很好地反映了航迹线的实际分布状况;在老铁山水道及其进出口附近，密度点大且分布较为密集，表示水道附近船位点密度大且较为密集;船位点网络并未延伸到右上水域的一些航迹线上，表示右上水域的船位点密度小，这与航迹线在老铁山水道较为密集而在东北方向较为稀疏的实际状况相符;在老铁山水道的相向交通流中，水道右侧密度点大而密集，水道左侧密度点小而稀疏，这与当时老铁山水道航迹线右侧多、左侧少的实际状况一致。

2.2转向点的提取及聚类

为验证Douglas-Peucker压缩算法的有效性，对212条航迹线上的126193个船位点进行Douglas-Peucker压缩，阈值为120m，压缩后转向点数减为1979（压缩率达98.43%）。压缩后的数据量虽然大幅减少，但很好地保存了原始航迹的特征，可以明了地看出船舶交通流的宏观态势，见图9。

对压缩后获得的转向点进行密度聚类，同样采用阈值渐渐增大的方法。不同阈值下的转向点数和压缩率见表2。由表2可知，每经过一次聚类，转向点数就减少一次，阈值取4200m和4800m时转向点数已区别不大。

与船位点密度聚类一样，表2中所示的转向点数为各条航迹线上转向点数之和，存在多条航迹线上的转向点被重复计数问题，阈值取4800m时的实际转向点数远远小于930，删除权重小于30的转向点，最终得到的转向点数为24。图10为部分不同阈值下的转向点密度聚类效果图，图10e为在图10d的基础上删掉权重小于30的转向点所得的最终效果图。

从图10可以看出，聚类后的转向点网络与船位点网络有很大不同：在航迹线最为密集的老铁山水道内，转向点很少且密度较小;在水道进出口附近，有大量密度较大的转向点。实际航行中，船舶在水道内大多定向行驶，航迹偏转很小;而在水道进出口附近，船舶进出水道需频繁动舵，因此航迹线转折较多，与试验数据相符。在图10中左上区域航迹线好多，但大多对比平直或整体弯曲度较低，转向点相对较少，最终导致该水域在转向点网络中的转向点少且密度小;图10e中C1、C2两点不在航迹线密集的区域，但其附近航迹线转折颇多，转向点并不少，最终成为转向点网络中相对突出、孤立的两点。

2.3交会点的提取及聚类

根据航迹交会算法，对212条航迹线上的126193个船位点进行编程计算，最终得到5200个交会点，見图11。

从图11可以看出，在老铁山水道及其进出口附近交会点密集。图11中左上区域（进出口邻近的警惕区）和右下区域交会点也好多，与右下区域相比左上区域交会点较少且分布对比零散，与航迹线进水道时汇集、出水道后发散的实际状况一致。对提取的交会点进行密度聚类，阈值渐渐增大，阈值差也渐渐增大（依次取300、600、900、1200m）。不同阈值下的交会点数和压缩率见表3。

与船位点和转向点不同，交会点是散点，并未引入航迹线中，因此表3中压缩后的交会点数和压缩率均为实际值。为得到最有代表性的交会点，最终的压缩率很高。在阈值渐渐增大的过程中，最初采用300m的阈值差，在阈值取1800m与2100m时其整体压缩率很相近，因此加大阈值差至600m。阈值越大，数据量减少率越低。阈值取3000m后改用900m阈值差，阈值取4800m后改用1200m阈值差，阈值差改变的区间内往往存在数据阶跃。

图12为不同阈值下的交会点密度聚类效果图，图12f为在图12e的基础上删掉权重小于50的交会点所得的最终效果图。

2.4加权融合提取船舶交通流框架

经数据清洗后共获得126193个船位点数据，利用密度聚类算法、Douglas-Peucker压缩算法和航迹交

会算法等对该AIS数据进行处理，获取密度聚类后的3种交通流特征点。关于特征点聚类过程中最终阈值的选取，主要考虑以下两个方面。一是聚类效果：随着阈值的不断增大，船位点数的下降幅度会越来越小，阈值取到4800m和6000m时，交通流框架的主要节点已基本形成，继续加大阈值后所聚类的点基本是主框架之外的散点，这些点绝大部分属于之后会被删除的低密度点，其对主框架的影响基本可以忽视不计。例如在对交会点进行聚类时，当阈值取6000m时，删除低密度点后剩余点数为16，该数值一直保持不变，直到阈值取8000m时出现阶跃。阈值的过大和数值的阶跃，会导致原有的交通流框架发生严重变形，不符合最初的设想，因此阈值取到6000m已完全符合试验需要;转向点的状况也与此类似，阈值取到4800m即可。二是实际状况需要：对于特征密度点的聚类，除考虑交通流框架外，还要考虑具体状况。试验数据中两股反向的交通流在老铁山水道聚集进行分道通航，当阈值取到6000m以上时，南下交通流的个别密度点由于权重相对较小，会被聚类到北上一侧，这显然不符合实际航行状况，必需保证通航分道的两侧都有对应的密度点保存，因此阈值取到5400m即可。关于删除较小密度点的权重阈值选择，以最终保存的特征点不过多为原则：若船位点数多且权重大，则权重阈值选用其最大点权重的5%左右;若转向点和交会点的数量和权重都相对较小，则在选取权重阈值时要保存其数据总量的30%～40%。具体地，取船位点的最大聚类阈值为5400m，聚类完成后删除权重600以下的点;对船舶轨迹进行Douglas-Peucker压缩，阈值取600m，得到1979个转向点，再经过密度聚类，取最大聚类阈值为4800m，聚类完成后删除权重30以下的点;船舶轨迹经航迹交会算法提取到5200个交会点，再经过密度聚类，取最大聚类阈值为6000m，聚类完成后删除权重50以下的散点。权重调整后的结果见表4和图13。

在以