赵梁滨， 史国友， 杨家轩

(1.大连海事大学 航海学院， 辽宁 大连 116026;2.辽宁省航海安全保障重点实验室， 辽宁 大连 116026)

随着国家大数据战略的稳步推进及船舶自动识别系统(Automatic Identification System，AIS)的普及，海事领域的数据产业蓬勃发展。传统的海事监管模式受人为因素的制约导致低效。顺应着对 “更好地感知交通态势”及“更及时地识别异常船舶”的迫切需求，随着“智能航海”及“海上智能监管”等新概念的提出，“互联网+”及“云计算”等理念与海事领域的结合越来越紧密。

每艘搭载AIS设备的船舶能向外播发包括船舶轨迹在内的AIS数据，由于AIS数据量庞大，其中蕴藏着海上复杂交通环境中的潜在规律，能保持稳定且快速增长，为水上交通数据挖掘理论提供基础。

轨迹数据的分析方法包括聚类、数理统计、贝叶斯网络及神经网络等。其中，聚类算法(Density-Based Spatial Clustering of Applications with Noise,DBSCAN[1])作为一种经典的空间聚类算法，已遍及各类交通情景的研究。LEE等[2]基于DBSCAN算法提出一种轨迹聚类的框架“TRACLUS”,该框架先将轨迹分裂成子轨迹片段，再用最小描述长度距离衡量片段间的相似度，最后采用DBSCAN算法对所有片段进行聚类来获得轨迹分布特征。该方法被后续的相关研究所广泛借鉴[3]。

以船舶作为研究对象时，在水上交通环景中由于移动对象在空间上更加自由无约束，轨迹分布更加零散、复杂，所以DBSCAN算法的应用效果不佳。LIU等[4]提出一种考虑国际海事组织(International Maritime Organization,IMO)规则和非空间属性的方法，作为聚类后的辅助手段以提取类簇的特征。此外，PALLOTTA等[5]提出名为“TREAD”(Traffic Route Extraction and Anomaly Detection)的方法，考虑船舶轨迹数据点集中的间歇性、持续性等因素。基于DBSCAN算法的船舶轨迹分析研究还包括文献[6]等，但是其均未考虑算法自身的参数设置问题。DBSCAN算法对全局性参数十分敏感,因此,根据经验所设置的单一参数难以在轨迹密度不均的水上交通环境下完成各局部合理的聚类，且其物理意义抽象，很难找到与实际水域情况的关联性。

为了克服DBSCAN算法在水上交通环境中的应用难题，本文基于其原理，通过统计分析数据的核心距离[7]来确定参数，提出针对船舶轨迹的层次聚类方法，并结合实例验证该方法的有效性。

1 自适应层次聚类方法

1.1 DBSCAN算法原理

DBSCAN算法是一种基于密度的聚类算法，它能发现任意形状的类簇，自动确定簇的数量，可适用于噪声环境。拓展到线的DBSCAN算法原理定义为

1)ε-邻域集Nε：Nε(Li)为Li在线段集D内所有与Li距离小于领域范围ε的线段集合为

Nε(Li)={Lj∈D|ddist(Li,Lj)≤ε}

(1)

2)核心线段：给定领域范围参数ε和领域最少线段参数MinLns，若Nε(Li)中的线段数量≥MinLns，则认为Li为核心线段。

3)直接密度可达：给定参数ε，MinLns，若存在核心线段Li，Lj包含在Nε(Li)中，则认为Lj从Li直接密度可达。

4)密度可达：给定参数ε，MinLns，若存在从Li到Lk直接密度可达，从Lk到Lj也直接密度可达，则认为从Li到Lj密度可达。

5)密度相连：给定参数ε，MinLns，若存在Lk，Lj和Li同时从Lk密度可达，则认为Li和Lj密度相连。

DBSCAN算法的思想就是找出所有密度相连的线段，并各自为簇(见图1)。算法唯一需要人为参与的部分就是参数设置，因此，参数的确定是DBSCAN算法减少误差的关键。

图1 DBSCAN算法伪代码

1.2 DBSCAN算法参数的自适应确定

核心距离是指在给定参数MinLns下，使样本数据能够成为核心线段的最小距离Dist(MinLns)。

聚类的目的是将较密集的样本尽可能地聚合成簇。在理想的簇中，样本数量应得到保证，且分布密度应最大。从单个数据样本为中心的局部DBSCAN聚类效果来看，若ε取该样本数据的核心距离，恰好能最准确地完成满足密度要求的聚类。因此，可通过所有样本的核心距离分布情况，找到分布密度最大值来确定合适的全局参数ε。

采用Inverse Gaussian拟合分布密度曲线的方法[8]来确定在给定MinLns情况下的领域范围参数ε，它的概率密度和极值为

(2)

式(2)中:λ和μ可通过最大似然估计法获得。

(3)

参数MinLns的值域为从1到样本总数，根据上述方法可确定所有MinLns所对应的参数ε。接着根据DBSCAN拟聚类的效果，来确定合适的参数MinLns。

用噪声数量来表征数据集的聚类效果。以琼州海峡某时间段的船舶轨迹数据集为例，所有参数取值情况下的噪声数量统计见图2。

图2中随参数MinLns的增大，聚类后的噪声数量逐渐减少，且变化趋势呈现出向下凸的图形。

参数MinLns在一定程度上反映着数据间能够被聚合成簇的最大距离，故随着MinLns的增大，在达到理想的聚类效果之前，类簇应快速地吸纳周围高密度的数据，导致噪声数量急剧减少，然后类簇周围的数据则变得稀疏，其扩张的速率应急剧下降，噪声减少的速率也随之下降。基于这一原则，合适的MinLns应在噪声数量下降率变化最大的横坐标位置，即图2中O点所在位置。

图3是上述最优参数情况下的聚类结果。由图3可知，琼州海峡南北方向上的主要交通流数据已被识别出来，并划分为红、绿两类，剩余相对稀疏的数据则被归为噪声。从结果可知，轨迹集被全面且合理地识别划分，但是却没有体现局部的交通流特性，例如航向相对的轨迹区分及各航道中的轨迹分布。这是因为在密度不均的数据集中，全局参数无法使各局部都达到最优化的聚类效果。而船舶轨迹是一种典型的密度不均衡数据，因此需采用层次进行聚类的方法。

1.3 层次聚类

层次聚类的原理是在每个层次都确定与该层次数据集密度最匹配的参数，其聚类精度随层级递增，从而达到适应各局部密度环境的聚类效果，以下是层次聚类的具体方法。

根据1.2节所述方法，确定该层次的参数取值，并完成聚类，得到包含类簇集和噪声集在内的子数据集。接着，根据容量阈值分拣子数据集，其中小于容量阈值的数据集将被作为最终子数据集而输出，容量阈值可根据实际情况设定，剩余的数据将被作为下一个层次的数据源。下一个层次则重复上述步骤，直到满足停止条件为止。停止条件包括：

1)该层次聚类后产生的所有子数据集均小于容量阈值。

2)该层次无法再选取出合适的参数。

由于每个层次数据数量及变化规律的不同，其选取参数的具体方法也不同，例如在层次聚类的初期，噪声数量还存在着较多异常波动，此时用图形中距直线y=-x最近的点近似代替该点作为该层次参数的取值，往往能够获得较好的聚类效果。根据经验确定了3种参数选取的具体方法(见表1)。

表1 选取参数的方法

当使用某一种选取方法进行聚类后，没有新类簇产生，且新产生的噪声数量小于容量阈值，则采用下一优先级方法重新进行聚类。当采用第3优先级方法进行聚类时，若两个类簇的数据量分别大于和小于容量阈值，则视为无法再选取出合适参数。综上所述，自适应层次聚类的方法见图4。

d) 聚类结果函数的伪代码

图4 基于DBSCAN的自适应层次聚类算法

2 实例分析

为了验证该聚类方法对于船舶轨迹数据的有效性，本文以琼州海峡水域(110°06′00″E,20°18′00″N,111°24′00″E,20°00′00″N)2006年4月21日至22日内88艘船舶的332 525条AIS轨迹数据作为对象进行了试验。

2.1 试验过程

在数据库中筛出研究范围水域的全部数据，对数据进行解码存储、坐标转换[9]、噪声清洗等预处理。然后，采用Douglas-Peucker算法[10-11]对航迹点进行了压缩，采用分解为垂直、水平、方向、速度的结构化距离[2]进行了轨迹线段间距离的度量。最后，完成基于DBSCAN的自适应层次聚类，部分过程及结果见图5和图6。

2.2 结果分析

试验共得到28个类簇。根据实际航路中各类簇之间的连通性，将秀英港、海安港以及海口新港之间的船舶轨迹分为了4组(见图7)。分析试验结果，可得到以下结论。

图5 部分层次聚类过程

1)该方法能够发现内部具有相似性的轨迹类簇，例如聚类可以识别出从秀英港进入主航道的轨迹、主航道上的出港轨迹、离开主航道后继续北上的轨迹以及向北航行一段距离后向东转向的轨迹等(对应图7a)中C-1、C-3、C-10、C-8)。此外聚类还能够发现并识别出同一水域中不同航法的轨迹类簇，例如C-15、C-20、C-25，它们都是北上准备进入海安港主航道的船舶轨迹，C-24和C-26则都是在海安港主航道上的进港轨迹。

2)类簇结果能够反映水域的交通情况[12]。从图7a)和图7c)中可知，海峡西侧的轨迹类簇数量较多，说明该水域交通流量大。此外相向轨迹的分布存在着部分重合，说明该水域的交通流混乱、不分明，可能存在着较多的对遇局面。从图7b)和图7d)中可知，海峡东侧的轨迹类簇数量较少，说明该水域交通流量小，轨迹分布零散。这些类簇结果都与琼州海峡水域当时的交通情况相符。琼州海峡当时并没有实施定线制来拓宽南北方向的航路，因此交通流量都集中在海峡的偏西侧，而偏东侧水域的客船交通流量小，散乱无序。

3 结束语

本文针对DBSCAN算法在水上交通情景中的参数选取问题，提出一种能够自适应确定算法参数，且适用于船舶轨迹数据的层次聚类方法，并通过琼州海峡水域的实船AIS数据，完成了实例分析。试验结果表明，该方法能够在复杂的船舶轨迹中发现具有相似性的轨迹并将其聚集成簇，且聚类结果与实际情况相符，在航道规划及海事监管等方面具有一定的应用价值。

图7 4个类簇分组

该方法需要获取每个层次中所有轨迹相互之间的距离以及所有参数取值的拟聚类结果，大量的遍历计算使得方法的效率低。此外，用于类簇筛选的容量阈值需要人为设置，若设置不当，会导致局部交通流特征的丧失或对轨迹的过度分类。今后的工作可从优化方法效率及结果的工程应用方面开展。