集群环境下企业应用系统的关联规则算法研究

赵向兵,张景安

(山西大同大学计算机与网络工程学院，山西大同037009)

随着移动互联网、物联网、云计算等技术的飞速发展，信息爆炸时代已经来临，海量数据已变成一种资源，深受企业的重视，对大数据的存储，分析，管理，应用，决定着企业的未来发展。大数据在各个领域的快速发展，也推动着企业不断地发展新业务和创造新的发展模式，随之而来的数据仓库、数据安全、数据分析、数据挖掘等围绕大数据的商业价值的利用逐渐成为行业人士争相追捧的利润焦点。大数据的整理和分析使企业产品更符合消费者需求，帮企业锁定目标客户，帮企业提供更好的推广方案，提高有效转化率，帮企业危机预警等。同时，大数据技术应用对于企业也面临着前所未有的挑战，Hadoop[1]为核心的大数据生态系统，解决了数据的存储和相关计算问题，是一个优秀的分布式计算系统，利用通用硬件构建一个强大、稳定、高效的分布式集群计算系统，满足了互联网公司基础架构的需求，为企业大数据技术应用提供了巨大的支持。

大数据技术的应用是企业信息化建设的重要方面，我校作为我省唯一一所“厅市共建”院校[2]，对地方企业的信息化建设情况做了调研，并对得到的数据进行了数据分析，特别是对企业的交易数据进行了关联规则分析，得到了很好的效果，为地方企业的发展做出了贡献。

关联规则[2]挖掘是大数据挖掘研究领域的一个主要研究内容，发现数据背后隐藏的数据项集之间的关联关系和依赖关系，使其中的一个事物通过其他事物得以预测和发现。关联规则挖掘应用广泛，经典的案例是购物篮分析，发现交易数据库中不同商品之间的联系，通过“加工”实现数据的“增值”，找出顾客购买行为模式，提高企业的效益。

1 关联规则的发展情况

关联规则挖掘算法的一个关键问题是从事务集合中得出所有满足用户给定的最小支持度的频繁项目集，关联规则挖掘算法基本模型如图1[3]：

图1 关联规则挖掘基本模型

经典的关联规则挖掘算法分为两类：Apriori[4]算法和FP-Growth[5]算法。Apriori算法算法思路简单，以递归统计为基础，生成频繁集易于实现，但该算法多次扫描事物数据库，在确定是否是候选集之前依然需要对它生成子项集，再进行连接比较和剪枝步骤，造成I/O开销巨大，算法效率大幅度减低。频繁模式增长（FP-growth）算法把一个大数据库有效地压缩成比原始数据库小的多的高密度结构，避免了重复扫描数据库的开销；该算法基于FP-tree的挖掘采用模式增长的递归策略和分区策略，无候选项目集，提高了挖掘效率，使用压缩后的数据库分成条件数据库，各个条件数据库关联一个频繁项，条件数据库远远小于原始数据库。

频繁模式增长（FP-growth）对关联规则发现提高了挖掘效率，接着 Ye Gao[6]、Huiling Penguins[7]、张继福[8-9]等对该算法进行了有效的改进，但根本的问题没有解决，包括：FP-tree树生成过程时对条件模式基进行遍历，导致频繁访问本地数据库或服务器；随着数据量的急剧增加，构造树占用内存过大，影响到系统的正常运行。针对关联规则算法发展中存在的问题，采用分布式并行计算模式[10]提高关联规则挖掘算法的效率是一个不错的解决方法。

2 基于MapReduce的关联规则并行挖掘

2.1 频繁模式挖掘

已知数据库记为DB，设I={i1,i2,i3,…,in}，I是n个不同数据项目的集合，T是DB中的事务，且T⊆1,用TID唯一标识标记每个事物。对于任意的项集X⊆1若X⊆T，则事务T对项集X是支持的。数据库DB中包含X事务的个数就是项集X在DB中的支持度计数，数据库DB包含X的事务占整个DB事务总数的百分比叫做DB中项集X的支持度。如果项集X的支持度大于等于用户给出的最小支持度的阙值，称项集X为数据库DB中的频繁项集，频繁模式挖掘的本质就是通过对数据库的DB的处理分析，得出满足所给最小支持度阙值的所有频繁项集。

2.2 基于MapReduce的频繁模式挖掘算法

首先针对待处理的数据集进行遍历得出频繁1-项集，接着构造FP-Tree，再调用FP-Growth算法进行挖掘，最终得到频繁项集。挖掘过程中使用了两对Map和Reduce函数，实现了将数据事务映射为频繁项计数和频繁项集，最后生成关联规则。具体步骤如下：

1）设集群系统中有N个节点，首先将数据库根据事务条数分成大小相同的N个部分，且将每个部分分配到不同的节点并存储在节点本地磁盘中；

2）扫描每个节点上的数据集，处理每个节点中的数据，计算出所有1项的支持度计数，再根据给定的最小支持度阙值，生成频繁1项集合，并对频繁1项集排序然后上传到HDFS上。此过程通过一对Map和Reduce函数实现；

3）第二对Map和Reduce函数的Map阶段：根据排好序的频繁1项集，将事务数据排好序，然后遍历排好序的事务数据，以频繁项为键，事务数据为值传递给Reduce阶段。

第二对Map和Reduce函数的Reduce阶段：Re⁃duce节点接收到从Map节点过来的数据，遍历这个频繁项对应的事务数据集，将它们构建起该频繁项的条件FP树。从条件FP树进而得到包含本频繁项的频繁项集，如图2；

图2 MapReduce实现过程

4）基于频繁项目集满足最小置信度度量标准，产生关联规则。

3 系统实现

该系统采用Eclipse作为开发工具，从系统的输入（企业交易数据参数）与输出（交易数据分析）之间复杂非线性的关系中抽取两者之间的关联规则，用以解释客户购买模式特点以及提供解决方案。然后将得到的交易数据分析情况反馈到企业产品生产和销售的改进中，进而优化企业的生产和销售环节，实现“加工”实现数据的“增值”，提高企业的竞争力。

该原型系统包含了三大功能，分别是：并行环境的参数设置，频繁项集的生成和最后客户购买模式的关联规则的生成。

并行参数设置中，选择不同的集群环境时，可对相应的参数选项进行设置，系统涉及Hadoop并行计算平台。数据经过预处理后，首先选择要处理的企业交易数据文件，数据导入完成后，输入生成频繁项集的最小支持度，按照介绍的算法思想，生成频繁项集，输入最小置信度度量标准，生成的关联规则。

4 实验结果及分析

运行环境：8个计算节点，都是在内存16G服务器上搭建的虚拟机（内存为512M），主要使用插件有：Ubuntu Linux10.10，JDK 1.6.0_37，Hadoop-1.1.1，Java eclipse，Hadoop-eclipse。

实验数据：采用大同市企业信息化调研数据（规模以上141家，其它2011家）,数据经过预处理，每条数据共40个属性。

4.1 可扩展性

由图3表明，在输入数据集、支持度和置信度一定的情况下，对于所对应的柱状图观察，节点数的增加，加速比是逐渐升高的趋势。从增长的幅度上来看，加速比在6个节点之前，增长缓慢，但是6个节点之后，加速比迅速增加，说明节点增加，计算能力提高，但同时造成了节点之间通信负荷也随着有所提高，节点数目越大，系统通信代价越大，降低了系统并行化挖掘的加速比。

图3 计算节点对算法效率的影响

4.2 可伸缩性

图4表明，在相同节点、支持度和置信度下，数据集比较小时第一次扫描数据库用时较少，构造频繁项的条件FP树较小，系统挖掘效率明显升高。随着数据集的增加，第一次扫描数据库用时逐渐增加，构造频繁项的条件FP树和挖掘阶段时间也逐渐增加，占用内存也增加，故系统处理数据集到达一定程度时，运行时间增加变快。

图4 数据集对算法效率的影响

5 总结

提出的算法，采用分布式并行计算模式，解决了FP-growth算法中，存在频繁访问本地数据库或服务器，构造树占用内存过大等问题。实验结果表明，该算法有较强的可拓展性、收缩性和可行性。下一步的研究工作是在数据集动态改变的环境下，实现全局关联规则的快速挖掘。