包 磊 彭庆喜

（武汉东湖学院计算机科学学院 武汉 430079）

1 引言

随着地理信息的不断泛化，船舶轨迹数据的获取与计算能力不断发展。其中船舶自动识别系统（Auto Identification System，AIS）网络所收集的大量船舶航迹信息众源数据，是船舶轨迹数据的重要组成部分。同时，雷达、观通以及卫星系统主动获取的大量情报态势数据和Argo、海王星等诸多海洋观测计划所采集的海量海洋环境数据，构成一个数据量庞大、内容丰富，且数据量急剧增长的数据集。运动模式挖掘是目前领域中一个发展迅速的前沿研究课题，通过轨迹模式挖掘算法可以发现轨迹大数据中有价值的模式从而分析船舶的运动趋势和运动规律，以感知态势、获取更经济安全的导航信息。

2 相关研究现状

时空共现模式挖掘［1］是运动模式挖掘的一个典型问题，是指2 种（或2 种以上）对象实例在空间和时间上处于邻近。利用船舶轨迹数据进行时空共现模式挖掘具有巨大的应用价值。例如，走私交易船舶在航行中会出现长时间处于共现行为模式；舰艇海上执行任务期间常以编队出航，不同的编队组织形式意味着执行不同的作战任务，这种编队组织形式可以基于时空共现模式进行挖掘分析；海盗在实施非法行动之前的航行行为常会进行长时间近距离的跟踪观察，同样可以使用时空共现模式挖掘方法进行实时发现，进而为军事领域作战计划和战术动作发现，交通领域道路和网络计划，以及国土防卫中的标志性事件关联分析［2］提供有效的分析计算手段。

目前与时空共现模式相关的大多数研究结果都在空间共现模式基础上进行时间维扩展得到，所采用的方法基础以Apriori 算法为主，如celik 定义了一种混合时空共现模式度量方法，提出一种混合时空共生模式算法，并对该算法进行了正确性和完备性分析［2］，以及一种时空部分共现模式的挖掘算法［3］，用于发现动物迁徙中的固定模式和运动常用的战术行动［4～5］。文献［6］分析了从时空数据中挖掘不同移动对象间频繁共现子序列的问题，提出一种二阶段挖掘算法，先用hash函数将原始轨迹转换成具有相近特征的子序列，然后利用Apriori算法挖掘其中的频繁片段。文献［7］结合了时间维和空间维的度量问题，提出一种时空共现模式发现算法COSTCOP，在模式挖掘过程中综合考虑了时间维度量和空间维度量问题。

然而，海量的海上位置数据为时空共现模式的挖掘提出了新的要求，而目前海上位置数据信息量早已达到了TB 级别，且呈持续增长的趋势。仅仅以AIS 数据为例，全球每天通过卫星和基站收集的AIS 数据约为4G，一年产生的AIS 数据量可达1.4TB。现有的研究成果多基于少量数据样本，无法应对巨大的数据量。且传统挖掘算法的串行计算方式和空间特征不敏感的特点限制了共现模式挖掘的速度。针对这些问题，本文基于空间Hadoop分析平台架构，提出了海上位置大数据下的时空共现模式挖掘算法，通过采用两级空间索引划分原始数据集，在给出的扩展MapReduce架构上实现了船舶轨迹数据中的时空共现模式挖掘。基于AIS 实际数据集的实验结果显示，能够有效处理大规模船舶轨迹数据，并保持良好的效率和正确性。

3 船舶时空共现模型

船舶时空共现模式指船舶在位置和时间标识上满足某种邻近关系。这种邻近关系的判定通过实例时空邻近参与度来描述。

1）邻近关系

邻近关系包括空间邻近关系和时间邻近关系。空间邻近关系采用欧式距离来衡量。时间邻近关系采用船舶位置数据实例的时间戳的差值来衡量。

在图1 中，实线相连的实例间满足空间邻近关系。既满足空间邻近关系又满足时间邻近关系的时空共现实例有A1B1，C1D1，C3D3，C4D4，C5D5。

图1 船舶时空共现模式示例图

2）支持度

支持度是指数据集中对象邻近实例的出现数量。当邻近实例出现的数量多于设定的某个阈值时，判定为时空共现模式。

3）置信度

CPR为时空共现模式实例参与率，其计算公式为

其中Ck=｛f0，…，fk-1｝为k 元候选时空共现模式，fi∈E，E 为时空对象全集。计算图1 数据集的时空共现模式实例参与率CPR，计算结果见表1。

表1 时空共现模式实例参与率

船舶对象之间的各种组合构成候选时空共现模式。若仍满足置信度条件，则为时空共现模式。

其中θ 为置信度阈值。若设定θ=0.5，则表1中候选时空共现模式｛C，D｝为二元时空共现模式。

4 基于Hadoop架构的共现挖掘算法设计

基于Hadoop 的时空共现模式挖掘算法的核心问题为数据分区和挖掘算法并行化。

4.1 数据分区

船舶位置数据的空间分布特征存在明显的不均匀性，因此均匀的数据分区方法会出现数据负载不均衡的现象，这会导致并行化计算速度下降，影响算法的整体执行效率。同时，数据分区必须考虑到空间局部性，即空间上相近的对象应当被分割在相同的分区内。

数据分区算法分为三个步骤:1）计算分区数量。分区数量根据输入数据文件的大小，和系统开销确定，主要用于保存重复的空间记录和存储本地索引。2）确定分割边界，在分割阶段，为了简化计算将输入文件进行随机采样。输入文件的随机采样率默认为1%。当输入文件较大时，构建MapReduce任务分布式浏览所有记录并输出1%的采样文件。当得到的采样文件尺寸大于给定阈值时，需要进行二次采样。针对采样文件，进行边界划分，保存每个数据块的最小外接矩形，形成边界划分矩形集。3）实现物理分割。根据已知分割边界实现数据物理分割操作，是原始数据与分割区域的匹配问题。由于原始数据间分割区域匹配是相互独立的，所以可以进行并行化处理。首先将原始数据平均分成n 块，针对每块数据建立一个Map 过程，将执行结果送入Reduce 过程进行化简，从而加快处理速度。

4.2 时空共现挖掘算法

时空共现模式挖掘算法实质上是经典Apriori算法面向船舶位置大数据的适应性改进［8～10］。算法步骤包括数据分区、并行挖掘分区数据［11］、剔除结果中的边界共现实例、执行Apriori挖掘算法［12］。如图2所示。

图2 时空共现模式挖掘过程

图中分割边界确定算法的并行化计算只涉及到各垂直切块的并行排序和水平切割。对于最终切割结果需要获得每个分块的矩形区域范围，并将其结果作为最终结果输出。

分割函数Splitter 的输入为形式为

Splitter函数伪代码输入:

时空共现模式挖掘算法涉及Map 函数和Reduce 函数的设计，用于挖掘时空共现模式的Map_Reduce计算。

Map 函数的功能在于计算时空共现实例对。函数的数据输入形式为

Map函数伪代码输入:

Reduce 函数的功能在于合并相同的时空共现实例对。函数的输入形式为

Reduce函数伪代码输入:

5 算例与结果分析

5.1 实验环境与数据准备

使用4台计算机搭建Hadoop平台，每台计算机作为一个计算节点，其中一台机器作为Master 和JobTracker 控制节点，其余三台机器作为Slave 和TaskTracker 计算节点。计算机操作系统采用Ubuntu Linux 14.04，Hadoop 版 本 为Hadoop1.2.1。计算机基本配置为InterQ8300，内存4G，硬盘500G。

实验数据选自真实的AIS 历史数据。选取2012 年1 月 和7 月 的 全 球AIS 数 据，数 据 量 约400GB，选取的海区为我国琼洲海峡附近。实验之前，对数据采取预处理操作，剔除了错误数据和格式有误数据。

5.2 实验结果

1）2012年1月份数据集

实验参数设置:输入数据量=224GB，分块大小=1MB，邻近距离=500m，支持度=10000，置信度=0.1。实验结果见表2。

表2 时空共现模式挖掘结果

2）2012年7月份数据集

实验参数设置:输入数据量=186GB，分块大小=1MB，邻近距离=500m，支持度=10000，置信度=0.2。实验结果见表3。

表3 时空共现模式挖掘结果

5.3 算法分析

共现模式挖掘算法有4 个可控参数，其分别为分块大小、邻近距离阈值、支持度和置信度。在设定其余变量的前提下，本文分析讨论了各个参数对算法执行效率的影响。所用数据为2012 年1 月份数据，约224GB。

图3 分块大小影响分析

图4 距离阈值影响分析

图5 支持度影响分析

图6 置信度影响分析

如图3～6 所示，结果表明:随着分块大小的增加，算法执行时间呈先减后增的变化趋势，在分块大小为1MB 时取得最小值。邻近距离参数是时空共现模式非常重要的参数，直接影响实验结果的可靠性。邻近距离选择过大，会出现时空共现关系弱化的现象，邻近距离选择过小，会导致部分时空共现模式被忽略的情况。支持度大小的选择关系到时空共现模式挖掘的核心问题。支持度增大一个数量级，邻近实例对数量减小4 个数量级，也反映出支持度参数设定的重要性。而置信度的大小反映出时空共现关系的可靠性，有强时空共现关系的时空共现模式才具有实际意义。随置信度参数增加，共现实例对数量迅速减少。

6 结语

船舶AIS 数据中时空共现模式挖掘通过计算AIS 海量数据中对象间的时空邻近关系，发现邻近关系背后的模式与规律，对于海洋交通以及安全监管等军事、民用领域具有十分重要的实用价值。本文提出了一种基于Hadoop 的船舶时空共现模式挖掘算法，通过采用并行化分区算法划分原始数据集，在扩展的MapReduce架构上实现了船舶轨迹数据中的时空共现模式挖掘，并基于AIS 实际数据集进行了实验和分析。

由于硬件条件限制，本文中只选取的实验数据规模仍然较小，采用更大规模的全域数据进行实验，并结合其他数据来源，对船只异常行为进行综合判断也是一个重要的研究方向。