0 引　言

近年来，物联网技术发展迅猛，各行业的数据都呈现井喷趋势，大数据已经成为规模庞大的船舶运营管理中不可或缺的一部分。将数据技术应用到船舶管理领域，不仅限于将采集的数据信息化、可视化，更重要的是通过深度挖掘技术，将数据中所蕴含的信息应用于智能化船舶安全管理、船舶资源管理、物流贸易等领域，发挥大数据和人工智能技术在促进经济发展、提高航运贸易量及船舶运能中的积极作用，从而推动整个行业快速前行。

1993年，R.Agrawal等提出了关联规则的概念及其模型，目前最经典的是1994年R.Agrawal等提出的Apriori算法和2000年Han等提出的FP-growth算法^[1]。胡晓轩将改进型Apriori算法应用于船舶安全管理中，通过对生产中的考核指标进行挖掘分析，发现指标间的高度关联关系，分析和事故的相关性，并将其作为预警因子，提前预防安全事故的发生^[2]。孙斌采用改进的多维Apriori算法，挖掘人为失误导致船舶碰撞事故的频繁因素组合，并对该人为失误致因进行分析^[3]，以此来提高船舶航行的安全系数。顾洵瑜等提出利用FP-growth算法，采用分治方式，不产生候选项集^[4]，直接挖掘船舶滞留原因间的潜在关联，分析滞留原因，进行针对性检查，提高安全检查效率。

相对Apriori算法而言，FP-growth算法的效率明显提升，但当数据量快速增长时，该算法构建的频繁模式树（Frequent Pattern tree，FP-tree）在横向和纵向的维度上会越来越大，不仅容易造成FP-tree构建过程中出错，而且也会导致在频繁项集的递归挖掘过程中花费更多时间，造成挖掘效率低下。由于Spark采用了弹性分布式架构的编程接口，ZHANG Feng等提出了基于Spark框架的分布式频繁项集挖掘方法^[5]，该方法能很好地适用于大数据挖掘。章志刚等提出并行挖掘算法FPPM，该算法首先在各分计算节点上挖掘频繁项集，然后将各频繁项集进行合并得到全部的频繁项集，最后对不满足最小支持度要求的频繁项集再次计算支持度^[6]。

为了进一步提高船舶管理中数据挖掘效率，本文提出基于负载平衡的并行FP-growth数据挖掘算法，将原来在一个分区节点对整个FP树的挖掘转换为在多个分区节点上对分组FP树的挖掘，不仅简化了频繁项集的挖掘过程，减少了计算量，而且通过负载均衡技术，使多分区节点并行运算，压缩了挖掘时间。实验表明，该算法能够较好地提高船舶管理中数据挖掘的效率，并具有较好的可扩展性。

1 FP-growth算法描述

FP-growth算法将数据映射到FP-tree上，通过递归的方法，挖掘出全部频繁项集。FP-growth算法的基本过程分为2个步骤^[7]：

步骤1　构建FP树

1）遍历数据集，统计各元素出现的次数，创建头指针表；

2）将小于最小支持度的项从头指针表中剔除；

3）再次对数据集遍历，过滤和重排序每个元素项，并创建根节点为NULL的树fp_t。

步骤2　挖掘频繁项集

1）从头指针表中最下面的频繁元素项开始，根据相同类型元素链表的指针，向上遍历fp_t，得到其相应的条件模式基α；

2）基于步骤1的数据，构建FP树，并将小于最小支持度的元素项剔除掉，从而挖掘出频繁项集；

3）迭代重复步骤1和步骤2，挖掘获取所有的频繁项集β。

2 基于负载平衡的并行FP-growth算法研究 2.1 关联规则相关概念

关联规则是用于表示元素项之间关联关系的一种形式，对于２个互斥的元素项X和Y，可以用X⇒Y来表示X出现将导致Y出现。可用支持度和置信度来实现对关联规则的度量。

设I为m个互斥元素项组成的集合。

定义1　对于关联规则R：X⇒Y，其中X⊂I，Y⊂I。规则R的的支持度（Support）是数据集中X和Y同时出现的记录数与所有记录数之比，即

${\rm{support}}\left( {{{X}} \Rightarrow {{Y}}} \right) = \frac{{{\rm{count}}\left( {{{X}}\mathop \cup \nolimits {{Y}}} \right)}}{{\left| {{D}} \right|}}\text{。}$

(1)

式中： ${\rm{count}}\left( {{{X}}\mathop \cup \nolimits {{Y}}} \right)$ 是X和Y同时出现的记录数，|D|是所有的记录数。

定义2　对于关联规则R：X⇒Y，其中X⊂I，Y⊂I。规则R的置信度（Confidence）是数据集中X和Y同时出现的记录数与只有X出现的记录数之比，即

${\rm{confidence}}\left( {{{X}} \Rightarrow {{Y}}} \right) = \frac{{{\rm{support}}\left( {{{X}}\mathop \cup \nolimits {{Y}}} \right)}}{{{\rm{support}}\left( {{X}} \right)}}\text{。}$

(2)

式中： ${\rm{support}}\left( {{{X}}\mathop \cup \nolimits {{Y}}} \right)$ 是X和Y同时出现的记录数， ${\rm{support}}\left( {{X}} \right)$ 是只有X出现的记录数。

定义3　最小支持度和最小置信度，最小支持度（Minimum Support，minsup）从统计分析的角度表示元素项的最低重要性；最小置信度（Minimum Confidence，minconf）从统计分析的角度表示关联规则的最低可靠性。

关联规则的挖掘实际上就是从所有满足最小支持度的项集中挖掘满足最小置信度的规则的过程，也就是挖掘强关联规则的过程^[8]。

2.2 算法基本思想

本文提出的基于负载平衡的并行FP-growth数据挖掘算法基于以下结论：

1）频繁项集的子集是频繁的。

2）设元素i⊂I，support（i）≥ minsup，k-FItemS（i）为所有包含元素i的k项频繁项集，则k-FItemS（i）的并集为项目集I的频繁项集。

2.3 算法项目树构建

在对海量的船舶管理数据进行关联挖掘时，构建的FP-Tree在横向和纵向维度上会变的非常庞大，挖掘效率也会随之而降低。为解决此问题，本文提出一种基于时间片段和TID的项目树构建方法。对任意满足i⊂I的元素，系统按照一定的规则和顺序分配一个唯一的TID，对任意T⊂I，首先，按照TID（i）对T中的元素进行排序，将T存入数据库的同时，按照系统事先设置的时间片段值，构建项目树，为压缩树存储空间，相同前缀的路径可以共用，通过链接，相同元素被连接成为一个链表。在构建项目树的同时，为项目树构建头表节点，头表中元素按照TID的升序排列，数据结构为ItemName：TID：count：Node-Links，其中，Node-Links指向项目树中与它同名的节点，如图1所示。

2.4 算法实现

BPFP-growth算法主要分为４个核心部分：

1）计算数据库项目集中的1-项频繁项集。

为了挖掘1-项频繁项集，首先根据项目树集的头表htab值建立矩阵模型 ${{{A}}_{\rm{i}}} = \left( {\begin{array}{*{20}{c}}{{{{a}}_{11}}}\\{\begin{array}{*{20}{c}}{{{{a}}_{21}}}\\ \ldots \end{array}}\\{{{{a}}_{{{n}}1}}}\end{array}} \right)$ ，通过式（3）计算1-项集支持度：

${\rm{sup}}({{A}}) = \mathop \sum \nolimits_{{{i}} = 1}^{{n}} \left( {{{{A}}_{\rm{i}}}} \right)\text{。}$

(3)

遍历过滤掉小于最小支持度阈值的元素项，挖掘获取所有的1-项频繁项集α。

2）扫描项目树，产生并行分组子项，结果存储在单独的数据库文件中。

并行分组是该算法中最核心的一环，根据算法的基本思想，对上述挖掘获取的1-项频繁项集α中的元素项集{a₁，a₂，···，a_n}，循环扫描项目树ptree，通过对数据项进行过滤、剪枝，构建头结点为a_i的分组子项集pns_t。

3）计算负载因子，根据负载因子完成并行分组，结果存储在分布式文件中。

并行挖掘中的分组是非常重要的环节，因为在并行挖掘中，各分区节点中最后一个完成挖掘任务节点的结束时间决定了整个系统最终的结束时间，因此，如何分配任务，使各分区节点的任务相对平衡，分组策略就显得非常关键。

在构建分组子项树时，从根节点到叶子节点的支持度逐步降低，搜索路径逐步减少，且分组中节点数量也不尽相同。本文综合考虑节点数量和路径长度，赋予不同的权重w_i。若同一层搜索路径内的节点数量为b_i，可通过下式计算分组子项的负载因子：

${{f}}\left( {\rm{x}} \right) = \mathop \sum \nolimits_{{{i}} = 1}^{{n}} \left( {{{{w}}_{\rm{i}}} * {{{b}}_{\rm{i}}}} \right)\text{。}$

(4)

循环遍历分组子项集pns_t，构建生成对应的FP树分组子项集fp_pns_t，通过式（4）计算分组子项集fp_pns_t中每个分组子项的负载因子，根据负载因子完成负载平衡分组gr_fp_t。

4）挖掘频繁项集。

在每个计算节点上，并行读取分布式文件，循环遍历挖掘负载平衡分组gr_fp_t中的各子项集，生成分组频繁项集，汇总各计算节点挖掘结果求得全局频繁项集β。

3 实验与结果分析

为了验证本文提出的BPFP-growth算法在船舶管理数据挖掘中的有效性和可扩展性，构建3个节点组成的并行计算平台。随机抽取10 000条数据作为实验数据集，实验测试结果如下：

1）BPFP-growth算法与FP-growth算法性能比较

在最小支持度为10的情况下，分别选取1 000条、2 000条、3 000条、······、10 000条的数据集，将BPFP-growth算法在2个并行分区计算节点和3个并行分区计算节点上的运算性能与传统的FP-growth算法进行对比测试，实验结果如图2所示。

从图2可以看出，不论采用何种挖掘算法，当数据集增大时，挖掘的数据量增大，频繁项集增多，递归挖掘所需要的资源和运算次数增多，导致挖掘的复杂度增大，最终使整个系统的挖掘时间延长。

另外，从图2还可以看出，当并行分区计算节点增多时，数据被平衡分布到更多的计算节点，所以，对于单个计算节点而言，所要处理的数据量减少，相应所花费的挖掘时间也缩短，呈现线性下降趋势。因此该算法具有较好的可扩展性。

2）BPFP-growth算法自身性能分析

当最小支持度为5，10，20的情况下，分别选取1 000条、2 000条、3 000条、······、10 000条的数据集在3个并行分区计算节点上进行对比测试，实验结果如图3所示。

可以看出，当选定的最小支持度增大时，被剔除掉的项目数将增多，这时剩余项目数减少，挖掘的数据集规模降低，使得递归挖掘所需要的资源和运算的次数减少，计算复杂度降低，缩短了整个数据挖掘的时间。

4 结　语

本文提出的BPFP-growth算法基于镜像重构技术对数据集进行切割，然后通过负载因子完成切割数据的并行分组与挖掘。实验结果表明，该算法在面向船舶管理大数据的频繁项集挖掘时，具有较好的可并行性和可伸缩性，可以有效挖掘出高度相关的频繁项集，从而能够利用该频繁项集完成船舶运营中的安全管理、事故原因分析等，大大降低事故发生率，提高资源的配置效率。