一种基于聚类算法和模式挖掘的船舶行为模式挖掘方法

摘要

一种基于聚类算法和模式挖掘的船舶行为模式挖掘方法涉及船舶的模式挖掘领域。本发明主要通过获取船舶的轨迹数据库中存储的轨迹进行数据清洗和轨迹压缩两个过程的计算，将处理好的轨迹数据进行聚类产生簇，将簇作为频繁项集进行频繁序列的挖掘。本发明对其中的关键点聚类进行优化，能够有效的利用聚类算法进行多类船舶数据的挖掘，从而能够适应船舶大规模数据密度不均匀的特性，提高了行为模式挖掘的质量和准确性。

说明书

技术领域

本发明针对船舶轨迹的特性，利用改进型聚类算法和模式挖掘算法设计了一种船舶行为模式挖掘方法，实现了船舶在航行过程中行为轨迹的挖掘；涉及模式挖掘领域，尤其涉及船舶的模式挖掘领域。

背景技术

随着近年来大数据、云服务、人工智能等新兴技术的发展，我国对海洋建设也在信息化、数据化。与此同时，定位系统、通信设备、传感器网络等基础技术的精度也在提升，应用也随之广泛。大规模数据也因各项技术的发展能够有精确的采集和良好的存储，船舶繁杂的大规模数据引起了政府、国防单位以及相关企业的广泛关注，希望通过不同的技术方法进行数据的充分利用。基于聚类算法和模式挖掘的船舶行为模式挖掘可以利用船舶的轨迹数据，通过聚类和挖掘手段形成目标历史行为模板，从而可以为船舶数据的应用和处理提供重要的辅助和参考作用。

轨迹数据是移动对象在时空中移动点的集合，其中包括对象的经纬度、高度、速度、时间等信息，是移动目标行为活动中的快照。同时，随着航海信息技术的不断发展，船舶自动识别系统(Automatic Identification System，AIS)被强制安装在船舶上，随之而来产生海量的AIS信息数据，该信息数据中蕴含了丰富的船舶信息。从原始轨迹到行为模式应用之间，可以将设备采集的原始轨迹数据通过数据清洗和数据预处理等手段将噪声、冗余、停留点等进行过滤和处理后，将数据用于模式挖掘，形成相对更加准确、可靠的移动目标历史行为轨迹模板，展示目标个体或群体见的活动规律。通过多种技术手段对轨迹数据的分析可以挖掘出活动对象个体及群体间的活动规律，进而能够为轨迹预测、交通规划及海空目标监测提供支持。

聚类分析是数据挖掘的有效手段，已广泛应用于模式识别，数据分析，图像处理等领域。频繁模式挖掘是轨迹数据模式挖掘的方向之一。

在聚类方法的分析中，考虑到船舶轨迹点难以精准重复，并且船舶数据密度分布不规则，同时，基于密度的聚类方法复杂度低，依据数据密度分布特征，可以对无规则形状的数据集聚类。因此，确定基于密度聚类的算法比较适合船舶数据区域分散无形状规则、数据大规模的特性。DBSCAN算法是基于密度的空间聚类算法中的典型代表，可以将高密度点区域划分为簇，并有效地滤除低密度点区域，可以在含有噪声的数据集中实现任意形状的聚类。但DBSCAN算法对Eps和MinPts参数十分敏感，取值不当会导致聚类效果变差甚至不正确。

本发明提出通过对船舶原始数据集的预处理，通过改进型DBSCAN算法对船舶数据集进行聚类，并将聚类产生的簇作为供模式挖掘的数据频繁项，使用模式挖掘算法对数据频繁项进行挖掘，从而挖掘出船舶的行为模板序列。

发明内容

本发明提出一种基于改进型聚类算法和模式挖掘算法的船舶行为模式挖掘方法，主要通过获取船舶的轨迹数据库中存储的轨迹进行数据清洗和轨迹压缩两个过程的计算，将处理好的轨迹数据进行聚类产生簇，将簇作为频繁项集进行频繁序列的挖掘。

本发明提供了一种船舶行为模式的挖掘方法，并对其中的关键点聚类进行优化，能够有效的利用聚类算法进行多类船舶数据的挖掘，从而能够适应船舶大规模数据密度不均匀的特性，提高了行为模式挖掘的质量和准确性。

本发明采用了如下的技术方案及实现步骤：

一种基于聚类算法和模式挖掘的船舶行为模式挖掘方法，

针对原始的轨迹数据存在冗余和噪声，会给后续分析造成很大的不便，因此需要对原始轨迹数据进行预处理从而得到能供后续分析的轨迹数据。在预处理后的轨迹数据上，进行轨迹聚类，定义频繁项集，并进行频繁模式的挖掘。

其特征在于包括以下步骤：

(1)针对原始轨迹目标轨迹时空跨度大、转向幅度平缓的数据特点提出数据清洗、压缩方法：

①由于采集到的原始数据可能会存在异常点，所以对数据集进行清洗是必要的。主要规则为：

轨迹段的起始点和终点时间间隔大于一天(24小时)，则进行轨迹段划分；

定义速度最大值v

其中，lon

②轨迹数据一般是按秒采集，所以轨迹数据的量都是很大的，但是在进行数据分析时，轨迹数据量太大会影响运算效率，而且很多轨迹点是没有必要分析的。为了方便计算都需要对轨迹数据进行压缩，道格拉斯-普克(Douglas-Peucker，DP)算法是常用的轨迹压缩算法，使用Douglas-Peucker算法进行压缩，需要设置点到轨迹直线的偏移量阈值threshold。在实验中选用选择8个目标共102584个轨迹点进行实验，对不同阈值下压缩比、压缩时间及压缩后轨迹误差进行对比，得出轨迹的压缩比和压缩误差随着压缩阈值的增大而增大；轨迹随着轨迹阈值的增大，轨迹的压缩时间进行相应减小。为了达到一个计算时间和计算误差的平衡，将轨迹压缩阈值threshold设为0.8km将会在较短的计算时间内得到相对准确的压缩效果。

主要流程为：

将轨迹段上所有的点按时间顺序排列。

1)在轨迹段首尾两点A，B之间连接一条直线AB，该直线为轨迹段的弦

2)得到轨迹段上离该直线段距离最大的点C，计算其与AB的距离d；

3)比较该距离与预先给定的阈值threshold的大小，如果小于threshold，则该直线段作为轨迹段的近似，该段轨迹处理完毕。

4)如果距离大于等于阈值threshold，则用C将轨迹段分为两子轨迹段AC和BC，并分别对两段取弦进行1～3的处理。

当所有子轨迹段都处理完毕时，依次连接各个分割点形成的折线，即可以作为轨迹段的近似。

(2)设计改进型DBSCAN聚类方法：

①参数Eps邻域：一个对象p的Eps邻域是指以对象p为中心，以Eps为半径的区域内，即：

N

式中，D为数据集；Dist(p,q)为对象p和对象q之间的距离；N

利用核密度估计获取除第一个簇以外的邻域值Eps

针对船舶轨迹数据集D，数据集中存在独立同分布的n个样本点x

其中，

带宽是一个自由参数，对所得到的估计值有很大的影响。那么对于h的选择，使用积分均方误差(Mean Intergrated Squared Error)可以判断估计所得的概率密度函数

其中，E()表示括号内变量的数学期望。

在弱假设下

其中，o()表示括号内变量的高阶无穷小；AMISE为渐进积分均方误差，而AMISE有

为了使MISE(h)最小，转化为求极点问题

因此最优带宽

在上述关于带宽h表达式中，存在概率密度函数f(x)的二阶导数f″(x)表示密度估计函数各点的凹凸程度，取高斯密度核函数为核函数进行核密度估计，h的最佳选择(即使积分均方误差最小化的带宽)为

其中，

②参数MinPts密度阈值描述了某一样本的距离为Eps的邻域中样本个数的阈值。

针对数据集D，遍历数据集D，记录每个数据点在Eps邻域中的对象个数M，M值可以作为数据集密度分布的依据。选取数据集D中M值最大的数据点为第一个核心对象D

其中，M(n)为当前核心对象的M值；M(max)记录D

(3)对频繁项集进行序列挖掘。

经过对船舶数据集的聚类，最终生成聚类中心和类簇距离范围所代表轨迹的频繁项，以及由聚类中心组成的轨迹，利用PrefixSpan(Prefix-Projected Pattern Growth，前缀投影的模式挖掘)算法可以将从大量偏序现象中挖掘出经常出现的偏序规律，从而得到船舶的行为模式。

本发明的创造性主要体现在：

(1)本发明在基于聚类算法和模式挖掘的基础上对船舶的行为进行模式挖掘，提出了先清洗、压缩，再聚类，并将聚类结果作为模板挖掘的入口，针对船舶数据冗余、数据量大、转向角平缓以及船舶轨迹难以精准重复的特点，有效的对船舶行为进行挖掘，从而能够得出船舶的航行规律；

(2)本发明对聚类方法进行了改进，相对于之前的聚类算法，改进后的算法能够使得聚类过程更加贴合样本特性，聚类结果质量更高，从而使得最终行为模式挖掘有更精确，船舶数据的利用率也会更高，也能为海洋数据的利用提供更加准确的参考。

附图说明

图1是本发明的整体结构示意图；

图2是本发明聚类方法示意图。

具体实施方式

本发明选取船舶AIS数据为原始数据，利用聚类算法和模式挖掘算法实现船舶行为模式的挖掘，采用了如下的技术方案及实现步骤。

基于聚类算法和模式挖掘的船舶行为模式挖掘方法具体步骤如下：

1.船舶原始数据集清洗及压缩，具有以下步骤：

步骤1：遍历轨迹数据集，根据时间差要求，对轨迹段的起始点和终点时间间隔大于一天(24小时)的轨迹进行分段，并将分段后的轨迹数据集进行保存。

步骤2：对分段后的轨迹数据集，遍历一条轨迹的所有子轨迹段，并根据设定的最大速度v

步骤3：使用道格拉斯-普克算法对已经清洗过的数据集按轨迹段逐一进行压缩，并保存压缩过的轨迹数据集。

2.利用改进型DBSCAN聚类方法对处理过后的轨迹数据集进行压缩

步骤1：设定初始Eps邻域阈值：

根据核密度估计

为选择最优带宽h值，使用最小化平均积分平方误差的方法

AMISE有

根据以上公式，为求得最小h值，则需使得MISE(h)最小，求极点

使用采用高斯核函数进行核密度估计，h的最佳选择为

其中n为数据集中对象个数，将h的值赋值给邻域阈值Eps进行聚类。

步骤2：遍历数据集D，记录每个数据点在Eps邻域中的对象个数M。

步骤3：选取M值最大的数据点为第一个核心对象，用Eps和MinPts参数值，对第一个簇进行DBSCAN聚类，标记已经聚类的数据点，直到该簇聚类结束。

步骤4：:从未被聚类的数据对象中选取M值最大的数据对象作为核心对象，动态获取除第一个簇以外的聚类密度阈值MinPts

利用Eps和MinPts参数进行聚类。

步骤5：重复步骤4，直到剩余对象无法作为核心对象时结束。

步骤6：记录由聚类中心组成的轨迹以及每个聚类中心和簇的范围。

3.对聚类结果进行模式挖掘。

将聚类中心和聚类范围作为频繁项，使用PrefixSpan算法对聚类中心组成的轨迹进行模式挖掘，获得具有时间顺序的频繁序列，该序列则为船舶的行为模板，是船舶航行过程中的运行规律。