0 引　言

导航系统为船舶路径规划的自动化发展提供了有效辅助，船舶能够使用性能卓越的导航系统完成航行控制^[1-2]。而目前航行距离的逐渐增加，航向和航行环境的不可判断性凸显，地理信息定位数据也呈爆发式增长。在海量信息数据环境中，想要准确、快速挖掘所需的导航数据，存在一定难度。甄荣等^[3]在挖掘船舶导航信息中的航迹数据时，使用高斯混合模型，此模型以高斯混合聚类的方式，完成航迹信息挖掘。但当属性差异不显著的航迹数据混杂在一起时，信息挖掘精度便会下降。任成杰等^[4]在挖掘船舶导航信息中的航迹数据时，使用GRU自编码器先提取航迹数据特征，再以聚类的方式完成航迹数据聚类挖掘。但此方法在提取大规模航迹数据特征时，需要经过多次训练，才可以保证编码器的特征提取精度，因此存在挖掘耗时长的问题。

针对以上问题，本文设计一种基于滑动窗口的船舶导航信息关联挖掘系统。

1 船舶导航信息关联挖掘系统 1.1 系统架构与硬件结构

所设计的基于滑动窗口的船舶导航信息关联挖掘系统整体架构如图1所示。

此次设计的船舶导航信息关联挖掘系统属于Client/Server结构，当用户在客户端的挖掘界面输入导航信息挖掘请求后，客户端将请求信息发送至服务端，服务端由船舶导航信息挖掘模块组成，通过信息访问接口API，在船舶导航信息数据源中采用滑动窗口划分的方式提取候选数据流，再构建船舶导航信息挖掘的关联规则，挖掘满足用户请求条件的导航信息，返回挖掘界面。

船舶导航信息关联挖掘系统硬件结构如图2所示。

由图2可知，系统硬件结构主要包括S3C2440处理器、人机交互屏、CAN总线、串口等。CAN总线和导航设备自身的标准串行接口相连，便可作为系统客户端和服务端的连接载体。人机交互屏可为用户提供挖掘请求输入、挖掘结果显示服务，具备人机交互功能。系统硬件平台主控制器为ARM920T内核，在此控制器管理下，系统的LCD显示器可以支持STN格式、TFT格式数据的显示。控制器具备3通道的串行接口，4通道高速数据JTAG接口，具备大规模船舶导航信息处理能力。

1.2 基于滑动窗口的导航信息关联挖掘

图3为船舶导航信息关联挖掘算法示意图。

由图3可知，采用滑动窗口进行导航信息关联挖掘时，将船舶导航信息流输入本文系统后，系统通过滑动窗口先挖掘出获选信息流。获取候选信息流后，再采用Apriori算法挖掘导航信息数据流中的频繁项集，完成船舶导航信息关联挖掘。

1.2.1 基于滑动窗口的候选信息流挖掘

设置船舶导航信息流一个时间间隔为 $\varpi$ 的滑动窗口，表示为 ${R_\varpi }\left[ {t - \varpi :t} \right]$ ， $t$ 表示时间，此滑动窗口中的导航信息点表示为 ${R_\varpi }\left( {a_t^{\left( \varpi \right)}} \right) = \left\{ {{a_{t - \varpi }},{a_{t - \varpi + 1}}, \cdots ,{a_{t - 1}},{a_t}} \right\}$ ， $a_t^{\left( \varpi \right)}$ 表示时间间隔为 $\varpi$ 的滑动窗口中的导航信息。

设置需要挖掘的船舶导航信息类型 $P$ 是时间段 $t$ 中的数据 ${a_t}$ ，则基于滑动窗口的候选信息流挖掘步骤为：

1）提取某段船舶导航信息记录的时间序列，从时间 $t$ 开始，设置滑动窗口信息点为 ${R_\varpi }\left( {a_t^{\left( \varpi \right)}} \right)$ 。

2）计算导航信息点 ${R_\varpi }\left( {a_t^{\left( \varpi \right)}} \right)$ 与待挖掘的导航信息的距离均值：

${\rm{avg}}\left( {a_t^{\left( \varpi \right)}} \right) = {\rm{avg}}\left( {{\rm{d}}\left( {a_{t - \varpi }^{\left( \varpi \right)}} \right),...,{\rm{d}}\left( {a_{t - 2}^{\left( \varpi \right)}} \right),{\rm{d}}\left( {a_{t - 1}^{\left( \varpi \right)}} \right)} \right) 。$

(1)

式中： ${\rm{d}}(.)$ 为距离计算函数； ${\rm{ avg}}(.)$ 为平均计算函数。

3）若时间段 $t$ 与时间段 $t - 1$ 导航信息之间的距离均值绝对值是 ${l_t} = \left| {{\rm{d}}\left( {{a_t}} \right) - {\rm{d}}\left( {{a_{t - 1}}} \right)} \right|$ ，则

${\rm{avg}}\left( {l_t^{\left( \varpi \right)}} \right) = {\rm{avg}}\left( {{l_{t - \varpi }},...,{l_t},{l_{t - 1}}} \right) 。$

(2)

此时处于距离均值周围的船舶导航信息为：

$n_t^{\left( \varpi \right)} = avg\left( {a_t^{\left( \varpi \right)}} \right) + \frac{\varpi }{2}avg\left( {l_t^{\left( \varpi \right)}} \right)。$

(3)

4）设置信息的距离阈值为 $\chi$ ，若满足 $\left| {{a_t} - n_t^{\left( \varpi \right)}} \right| < \chi$ ，则将此时间段的导航信息作为候选信息，反之则剔除。

5）多次执行上述操作，最后输出候选导航信息流 $A$ 。

1.2.2 基于Apriori算法的导航信息关联挖掘

关联规则可以体现数据之间相关性，若多个数据之间存在相关性，关联规则便可体现数据之间的关系。为了对导航信息进行关联挖掘，以获得候选导航信息流为基础，采用Apriori算法进行导航信息的关联挖掘。

设置候选导航信息流 $A$ 中的某信息为项，各个导航信息记录就是1个项集，将其设成 ${\boldsymbol{A}} = \left\{ {{A_1},{A_2},...,{A_m}} \right\}$ ， $m$ 为项集中导航信息记录总数目。关联规则设成 $a \Rightarrow Y$ ， $a \in A$ ， $a \cap Y \ne \emptyset$ 。其中， $a$ 表示导航信息中的某数据， $Y$ 表示用户请求信息类型，在分析关联规则是否满足需求时，需要使用支持度 $support\left( {a \Rightarrow Y} \right)$ 与置信度 $confidence\left( {a \Rightarrow Y} \right)$ ，前者表示某项集在用户需求信息类型中的支持度，后者表示关联规则的可信度，支持度与置信度的计算公式为：

$support\left( {a \Rightarrow Y} \right) = \frac{{count\left( {a \cup Y} \right)}}{m} ，$

(4)

$confidence\left( {a \Rightarrow Y} \right)\frac{{count\left( {a \cup Y} \right)}}{{count\left( a \right)}}。$

(5)

其中： $count\left( {a \cup Y} \right)$ 为船舶导航信息 $a$ 和用户请求信息的匹配数目； $count\left( a \right)$ 为船舶导航信息 $a$ 的信息量。分析 $a$ 与 $Y$ 之间的关联规则支持度与置信度，如果均满足最小阈值，那么 $a$ 就是和 $Y$ 匹配的导航信息。在分析 $a$ 与 $Y$ 之间关联规则支持度与置信度的基础上，采用Apriori算法先把候选导航信息数据流 $A$ 映射为“0”与“1”的元素矩阵，称为布尔矩阵。矩阵行与列分别表示导航信息数据类型、用户请求的导航信息类型。比如滑动窗口分为5个，那么便可构建5×5的布尔矩阵：

${\boldsymbol{C}} = \left( {\begin{array}{*{20}{c}} 0&1&1&0&0 \\ 1&1&0&1&0 \\ 0&0&1&1&1 \\ 0&1&0&0&0 \\ 1&0&1&1&0 \end{array}} \right) 。$

(6)

将布尔矩阵 ${\boldsymbol{C}}$ 每列用户请求的导航信息项，以并集的方式，构建候选频繁 $A$ 项集，整理 ${\boldsymbol{C}}$ 中各列“1”元素的数目，执行剪枝处理，如果 $i$ 列“1”元素数目小于阈值 $\beta$ ，便采取剪枝处理，反之去除此列，构建频繁 $A - 1$ 项集。

将频繁 $A - 1$ 项集执行连接处理，将 ${\boldsymbol{C}}$ 的项列执行逻辑“与”计算，得到候选频繁 $A - 2$ 项集。将候选频繁 $A - 2$ 项集中，每个子元素的“1”和阈值对比，更新候选频繁 $A - 2$ 项集。循环操作，当项集 $A$ 为空集便可停止，输出最后挖掘的频繁项集，此项集即为用户请求的船舶导航信息关联挖掘结果。

2 实验分析

为测试本文系统是否有效，进行系统导航信息挖掘性能分析。

图4和图5为本文系统挖掘界面为用户提供的请求信息示例图、导航信息挖掘结果显示图。

为体现本文系统的挖掘精度，以航迹信息为例，将挖掘的航迹信息量 ${A_j}$ 和实际航迹信息量 ${A_b}$ 之间平均距离 $O$ 作为指标， $O$ 可体现挖掘信息量的完备性，其数值越小，表示信息越完备、越准确。

$O = \frac{1}{M}\sum\limits_{j = 1}^M {{\rm{dis}}\left( {{A_j},{A_b}} \right)} 。$

(7)

其中： ${\rm{dis}}\left( {{A_j},{A_b}} \right)$ 为 ${A_j}$ 与 ${A_b}$ 之间的欧式距离； $M$ 为航迹信息挖掘次数， $j \in M$ 。本文系统提取的航迹路线和实际航迹信息量之间平均距离测试结果如表1所示。

可知，船舶导航信息中航迹信息挖掘效果较好， $O$ 的数值极小，说明本文系统挖掘信息量的完备性显著，准确性显著。原因是本文系统能够将船舶导航信息数据流划分为多个滑动窗口，通过关联规则挖掘的方式，挖掘与用户请求相匹配的导航信息。图6和图7为本文系统使用前后，多种导航信息挖掘耗时对比结果。

对比可知，本文系统对多种导航信息挖掘耗时小于0.4 s，和使用前相比，挖掘耗时明显缩短，说明本文系统的挖掘效率有所提升。原因是本文系统利用滑动窗口划分技术，能够把大规模的船舶导航信息分解为多个窗口，提高数据挖掘有序性，从而保证数据的处理效率。

3 结　语

本文设计基于滑动窗口的船舶导航信息关联挖掘系统，引入滑动窗口技术和关联规则挖掘算法，能够在规模化、复杂化的导航信息流中，将杂乱无章的信息划分为多个挖掘操作窗口，从而以关联规则挖掘的方式，提取匹配用户请求的导航信息数据。实验结果显示，本文系统导航信息挖掘的完备性显著，准确性显著，挖掘耗时小于0.4 s，导航信息挖掘性能得到提升。