一种基于云计算的关联规则改进研究

刘姜

（抚顺职业技术学院 信息工程系，辽宁 抚顺113006）

一种基于云计算的关联规则改进研究

刘姜

（抚顺职业技术学院 信息工程系，辽宁 抚顺113006）

随着数据挖掘技术的成熟，其中关联规则在大规模数据中的应用成为了目前的热点。为了提高在大规模数据下进行数据挖掘的效率，在MapReduce中通过引入归并函数Fusion来提高执行剪枝任务的效率并进行了优化研究，提出了一种基于云理论的关联规则Apriori算法，详细论述了实现的过程以及关键技术。通过实验表明，该方法取得了良好的实验效果，克服了Apriori算法耗时多、识别率低下等问题，是实现在大规模数据进行数据挖掘的实用工具。

MapReduce；数据挖掘：关联规则；Apriori算法

数据挖掘是由半自动化或自动化的计算器工具对资料存储库中的海量资料进行有条理且可重复的探索与分析的过程，对研究人员与知识需求者来说，其主要目的在于发掘出未知的、新颖的、有价值的、可利用的知识与规律。通过这些知识与规律，人们可以预测未来可能发生的结果。

数据挖掘作为一个新型智能资料分析技术，与传统分析技术“假设－收集－检验＂的不同点在于，其使用“发现－匹配＂等算法来获取资料之间的有价值关联。不同种类资?的涌现也导致数据挖掘技术经历了多次变革，由原本的事务集数据挖掘转向文件挖掘、多媒体挖掘、Web页面集挖掘、时序气象资料挖掘及三维结构DNA挖掘等。数据挖掘与以往的数据库查询也有相当程度的不同，其处理目标在于分析海量且复杂的数据库，其服务对象在于高级决策者，其主旨在于为高级决策者的决策提供有形且有力的数据支持。近年来，数据挖掘已成?各?同专业的研究热点之一[1]。Apriori算法是数据挖掘技术中的经典算法，由于传统的Apriori算法需要重复搜索数据库来得到候选集，影响了其运行的效率和计算精度。随着第四次IT产业革命的到来，云计算已成为大规模计算未来发展的方向，由Google提出的MapReduce编程框架是云计算中的核心技术之一，它适用于处理大规模数据集，计算效率非常高[2]。

针对传统 Apriori算法性能差的特点，本文立足MapReduce框架使用云计算技术传统的Apriori算法进行了改进，充分利用云计算的大数据存储和计算的能力来提高Apriori算法的运行效率。

1 传统的Apriori算法

传统的Apriori算法是在海量数据库中挖掘关联规则最基本的算法，由数据库专家是由Agrawal Rakesh等人在1994年所提出的[3]。该算法目的在于快速地寻找海量数据库中的频繁项集，是一种单维单层的布林关联规则，与市场购物篮分析的结果相同。使用Apriori算法进行关联规则挖掘时是利用支持度阈值来减少在寻找频繁项集时，全部项所可能生成的候选项集组合个数，主要分为以下几个步骤：

1)Apriori算法将先扫描一次整个事务集合，由此计算每一个项的支持度（出现频率）。该动作结束后，根据预设的最小支持度阈值（min_sup）限制，便可得到所有频繁项集的集合F1；

2)循环依序选取上一步经迭代所得到的频繁(K-1)项集，进而产生新的候选K项集；

3)Apriori算法须将重新再扫描整个事务集合一次，该动作是为了要重新计算新候选K项集的支持度计数 （出现次数）。接着，通过子集函数subset()来确定包含在每一个事务ti中的CK所有候选K项集；

4)经过计算候选K项集的支持度计数（出现次数）后，Apriori算法将剔除支持度计数少于最小支持度计数阈值（N*min_sup）的候选K项集。该动作是为了要从候选K项集中选取所有的频繁K项集；

5)当计算到FK=Φ时，这意味没有新的频繁项集能够产生。此时，Apriori算法产生频繁项集的部份计算结束；

6)输出频繁K项集集合的结果。

Apriori算法的伪代码如下：

2 优化M apReduce框架

MapReduce是目前非常流行的分布式计算架构主要是通过网络来处理在云端上储存的大量数据[4]。将要执行的MapReduce程序复制到 Master node以 及各个Worker，Master node会决定要给哪台WorkerWorker去执行Map程序或者Reduce程序。通过Map程序将数据切成许多区块，经过Map阶段产生出 Key/Value，将此 Key/Value存储在 Local disc，然后经过Shuffle（将相同属性的key排序在一起）。而Reduce程序将这些Shuffle后的结果进行整合，最再将产生出来。

由于MapReduce只能对单个数据集合进行操作的情况下去执行，对于Apriori算法中需要进行剪枝操作(也就是再次访问读取数据库中的事务记录)，会导致计算效率会下降。这就需要对MapReduce框架进行优化。我们引入了一个归并函数Fusion，用于将候选项集合中不需要二次读取数据库性质的项集进行删除。Fusion函数的流程如图1所示。

图1 Fusion函数流程图Fig.1 Flow chart fusion function

3 云计算下改进的Apriori算法

在改进后的MapReduce计算框架基础上，提出了基于此框架的关联规则Apriori算法，称为动态数据分配Apriori算法(DDAS:Dynamic Data Apriori Scheduler)。算法的主要思想是：将Apriori算法中关于频繁集和项集的计算部署到云计算环境下执行，同时采用改进的MapReduce计算框架，简化了任务执行的复杂度，提高系统响应时间，并且控制剪枝任务的数量避免引起任务抖动[5]。

1)Map函数从数据库中读取文件记录[6]，并将这些事务记录保存为项集，同时判断是否可以进行连接，不能进行连接的舍弃，从而产生频繁集的一个列表。同时，Map函数将输入的数据切割成固定大小，并记录下频繁集中的所有记录在数据库中出现的频度，最后将产生的候选集结果当做中间结果返回。

2)MapReduce框架中的节点会选择Mapper对读取的表进行遍历，然后将预处理得到中间结果输出给Reducer，并将最终得到的结果进行存储。

3)对于Apriori算法存在剪枝任务须再次读取数据的特性，我们采用自身合并(self-Fusion)操作，引入Fusion函数。Fusion函数基于最小支持度和Apriori性质(任何非频繁项集的子集都不可能是频繁项集的子集)对项集进行压缩，计算出频繁项集集合，删除掉候选项集中不符合Apriori性质的项集。如果此时项集已经为空（即处理完成），则将结果保存到数据库上并输出去给用户；否则，执行2）[7-9]。

4 实验及分析

在局域网内使用4节点的集群环境，每个节点的配置相同，CPU是酷睿2 1.83 GHz，内存2 G；千兆以太网卡。操作系统是Ubuntu Linux 13.10，Java环境为 JDK 1.7，Hadoop版本是0.20.2，HBase版本为0.90.1，配置好MapReduce的分布式计算环境。使用来自于加里福利亚大学提供的一个公用数据集进行测试，这个数据集记录了某血液中心献血者的一些数据，我们选择其中呢 40人的数据作为实验样本。

在Eclipse平台下编写了改进版本的Apriori算法与传统的Apriori算法测试结果进行比较，结果如图2所示。

图2 所用时间趋势Fig.2 Diagram of time trend

通过改进版本的Apriori算法，所使用的时间如图2所示，较传统的特征方法有明显的减少，以40人的样本数为例，改进版本的Apriori算法所用时间为Apriori算法的1/3。

本文将网络环境下的数据识别作为必要手段，统计了处理前后随着样本数变化在识别率方面的差异，如图3所示。实验结果表明使用改进版本的Apriori算法能够有效提升数据的识别率，以40人的样本数为例，传统的Apriori算法识别率为73%，而改进版本的Apriori算法的识别率为91%，在识别率方面提升了18%。

图3 识别率的差异Fig.3 Diagram of recognition rate

5 结束语

文中通过对传统的关联规则Apriori算法进行分析，在现有的云计算框架MapReduce的基础上进行改进，提出了一种新的关联规则改进Apriori算法，通过利用云计算的高速数据处理能力来解决传统关联规则Apriori算法性能较差的缺点。实验表明，该算法简单易实现，所需时间大幅降低，能够有效提高关联规则Apriori算法的运算效率。

[1]韩家炜.数据挖掘[M].北京：机械工业出版社，2009.

[2]陈康，郑纬民.云计算：系统实例与研究现状[J].软件学报，2009，20（5）：1337-1348.CHEN Kang,ZHENG Wei-Min.Cloud Computing:System Instances and Current Research[J].Journal of Software, 2009,20(5):1337-1348.

[3]邵峰晶，于忠清.数据挖掘原理与算法[M].北京：中国水利水电出版社，2003.

[4]郑启龙，房明，汪胜，等.基于MapReduce模型的并行科学计算[J].微电子学与计算机，2009，26（8）：13-17.ZHENG long,FANG Ming,WANG Sheng,et al.Scientific parallel computing based on mapReduce model[J].Microel Ectronics&Computer,2009,26(8):13-17.

[5]Apache基金会.Hadoop[EB/OL].(2009)[2014].http://lucene.apache.org/hadoop/.

[6]王鄂，李 铭.云计算下的海量数据挖掘研究[J].现代计算机(专业版)，2009，10（11）：22-25.WANG E,LI Ming.Research on mass data mining under cloud computing[J].Modern Computer,2009,10(11):22-25.

[7]刘华元，袁琴琴，王保保.并行数据挖掘算法综述[J].电子科技，2006，9(1)：65-73.LIU Hua-yuan,YUAN Qin-qin,WANG Bao-bao.Review of the parallel data mining algorithm[J].Electronic science and technology,2006,9(1):65-73.

[8]李志坚，莫建麟.一种改进的基于概念格的数据挖掘算法[J].重庆师范大学学报：自然科学版，2013（2）：92-95.LI Zhi-jian,MO Jian-lin.An improved concept lattice-based data mining algorithm[J].Journal of Chongqing Normal University:Natural Science,2013（2）：92-95.

[9]朱德利.基于Weka的就业数据分析和模式挖掘--以重庆市信管专业为例 [J].重庆师范大学学报：自然科学版，2014（4）：120-125.ZHU De-li.Employment data analysis and pattern mining based on Weka--take specialty of information management and information system in chongqing for example[J].Journal of Chongqing Normal University:Natural Science,2014（4）：120-125.

An improved association rules based on cloud computing

LIU Jiang
（Department of Information Engineering，Fushun Vocational Technology Institute，Fushun 113006，China）

With the mature of data mining technology,including the application of association rules in large scale data has become the current hot spot.In order to improve the efficiency of data mining,in MapReducethe is introduced Fusion function and optimized,the Apriori algorithm based on Cloud was designed,the process and key technology was discussed in details.Experiments show that this method has obtained the good experimental effect,overcomes the Apriori algorithm is time-consuming and low recognition rate,It is a practical tool that realizing the data mining.

MapReduce;data mining;association rule;Apriori algorithm

TN919.5

A

1674－6236（2015）10-0048-03

2014-10-26 稿件编号：201410191

刘 姜(1980—)，男，辽宁昌图人，讲师。研究方向：计算机网络应用与安全。