基于MapReduce的关联规则挖掘

陈凤娟

(辽宁对外经贸学院，辽宁 大连 116052)

基于MapReduce的关联规则挖掘

陈凤娟

(辽宁对外经贸学院，辽宁 大连 116052)

关联规则挖掘是数据挖掘的一项重要技术，它主要是通过频繁项集挖掘得到关联规则。基于云计算的MapReduce模型的数据挖掘算法可以提高挖掘的效果及性能。

关联规则；频繁项集；MapReduce；数据挖掘

1．引言

计算机和网络技术飞速发展，各个行业中存储了海量的数据，并且这些数据的数量还在增长。这些海量数据蕴含着丰富的知识，如何找出数据中蕴含的知识，为各种决策提供帮助成为了一个迫切需要解决的问题。数据挖掘技术运用了机器学习和模式识别等多个领域的知识，为解决这个实际问题提供了有力的工具。关联规则是数据挖掘的一个主要技术，它能从给定的数据集中，通过关联规则挖掘算法，找出各个属性之间的关联关系，以及多个属性域之间的依赖关系，这种依赖关系对决策和预测有作用。

MapReduce是由谷歌研究员提出的一种分布式编程框架，是一个用于处理海量数据的并行编程模型，可以运行在异构环境下，编程简单，不必关心底层实现细节。对现有的关联规则挖掘算法进行改进，使这些算法能在MapReduce模型中运行，利用并行技术提高算法的性能。

2．关联规则的基本概念

关联规则的挖掘是分两步来实现的，首先按照用户给定的最低阈值，找出数据集中的所有频繁项目集，然后从频繁项目集中构造规则，要求构造的规则的可信度大于等于用户设定的最低值。支持度是对关联规则代表的重要性进行度量的指标，它体现了关联规则的频度。如果某个项集的支持度的值太小，则表明相应的规则很可能只是偶然发生的。

设U={U1，U2，…，Un}为n个不同字符的集合，其中的字符称为项或商品。任意一个集合X⊆U称为一个项集，若|X|=k，则称X为k项集。事务（或交易）T是项的集合，且任意的T⊆U，对应每一个事务有唯一的标识，记作TID。设A= {T1，T2，…，Tn}，称A为U上的交易集或者数据集，简称交易集或者数据集。如果X⊆T，称事务T包含X。对于一个项集X和一个交易集A，X在A中的支持度定义为X在A中的支持计数与A中总的交易个数之比，记作sup(X)。如果X的支持度大于某个给定的最小阈值，则称X是频繁的。

频繁项集挖掘就是要在事务数据库里找出所有大于给定的最小支持度的频繁项集。频繁闭项集是一组事务都包含的项的最大项集。频繁闭项集和频繁项集的信息量相等，但是频繁闭项集比频繁项集的元素少很多，因此挖掘频繁闭项集能够满足用户的需求并且对减少了算法的开销，提升了频繁项集挖掘的效率，同时还减少了冗余信息的输出。

3．MapReduce模型

MapReduce是一个将大型分布式计算转换成为行串行化分布式计算的编程模型，它用Key/Value，即键/值对的形式来表示分布式计算，完成分布式操作。通过计算机集群，在Hadoop/MapReduce框架中，把用户定义的MapReduce任务分布到集群中的各个节点上执行。

能用MapReduce来处理的数据集必须是能分解成多个小数据集的数据集合，并且每个小数据集都可以完全并行地进行处理，否则，这个数据集合是不能用MapReduce来处理的。一个MapReduce分布式计算由两个过程组成，一个是Map过程，一个是Reduce过程，其中，Map过程也叫映射过程，而Reduce过程也叫规约过程。MapReduce框架将输入的数据分成多个能并行运算的数据片段，然后将每一个数据片段分配给一个Map任务，每一个Map任务执行相同的操作，即对分配给它的数据片段的key/value对进行计算，生成一个中间结果，这个过程称为Map过程。Map过程把计算得到的所有具有相同key值的value，经过计算后传递给Reduce函数，而Reduce任务会将从Map得到的二元组key/value集合的片段作为输入，调用用户定义的Reduce函数，将value值合并，得到value的集合，这个过程称为Reduce过程。

无论是Map过程还是Reduce过程，它们的每个任务的执行都支持容错功能，当任一个或多个节点在计算过程中出现错误时，都会自动将出错的任务重新分配到其他节点上，让其他节点完成计算。并行运行多个Map和Reduce任务，为系统提供了很好的负载均衡同时也降低了运行中失败的任务被重新运行的代价。

MapReduce采用“分而治之”的思想，有效地降低每一部分的运算复杂度，提高了运算效率，屏蔽了底层的实现细节，有效降低并行编程难度，提高编程效率。它的不足主要体现在以下方面：首先它善于处理松耦合型的数据，对不容易分解成多个相互独立的子任务的计算任务的处理效率很低；其次，它不能显式地支持迭代计算；最后它是一种离线计算框架，不擅长进行流式计算和实时分析。

4．基于MapReduce的挖掘算法

常用的关联规则挖掘算法有Apriori算法、A-Coles算法、Closet算法和ECLAT算法。这些算法都可以转化成基于MapReduce的挖掘算法。

Apriori算法是一种宽度优先的多趟扫描算法，主要包含连接和剪枝两个步骤。连接操作主要是生成候选集Ck，而剪枝主要是删除候选集中不可能成为频繁项集的元素。该算法首先扫描数据集，计算数据集中所有单个项目的支持度计数，然后再次扫描数据集，第k次扫描时，首先通过对Lk-1中的项目集的连接操作生成k-项集的候选集Ck，再利用Apriori性质进行剪枝，删除Ck中不可能是频繁项集的候选项，最后的频繁项集的集合为∪Lk。

A-Coles算法是一个基于Apriori算法的挖掘频繁闭项集的算法，它的主要思想是通过多次扫描数据集生成所有的频繁闭项集，属于自底向上的宽度优先的搜索。A-Coles算法主要由两步组成，第一步是通过宽度优先的搜索策略发现所有的频繁闭项集的生成器，第二步利用函数计算出每一个生成器对应的频繁闭项集。A-Close通过引入剪裁技术减小搜索范围，但是该算法需要多次扫描数据集，而且会产生大量的候选项集，因此对内存的消耗较大。

Closet算法是一个基于频繁模式树的频繁闭项集挖掘算法，它把原始数据集中的事务间的关联信息压缩到频繁模式树中，通过得到的频繁模式树生成每一个频繁项的条件频繁模式树，每一个条件模式树中存储了包含该频繁项并且支持度大于等于给定支持度的频繁模式。Closet算法只需遍历两次原始数据集，降低了对数据集的访问，不需要生成任何侯选项集，有效地提高了挖掘效率。但是当数据量大的时候，Closet算法生成的频繁模式树的规模过大，导致算法性能下降。

ECLAT算法是采用垂直数据表示的频繁项集挖掘算法，在该算法中，首次提出垂直数据表示的概念，用垂直数据表示可以大大减少扫描数据集的次数，以概念格理论为基础，采用深度优先搜索策略，采用前缀等价关系划分搜索空间。ECLAT算法对数据集只需要扫描一次，使用数据垂直表示形式，通过交叉计数来计算支持度，在实际应用中有较好的效果，是一种性能较好的频繁项集挖掘算法。

可以充分利用云计算提供的分布式并行计算功能，对Apriori算法、A-Coles算法、Closet算法和ECLAT算法加以改进，得到新的适用于云计算的频繁项集挖掘方法。

5．结束语

关联规则有许多挖掘算法，这些算法各自都有自己的优点和不足，为了提高这些算法的效果，可以依托于云计算平台，基于MapReduce模型，改进已有的各种算法，利用并行计算的功能，提升算法的性能。

[1]戎祥，李玲娟．基于MapReduce的频繁项集挖掘方法[J]．西安邮电学院学报，2011，16(4)：37-40．

[2]付沙，周航军．关联规则挖掘Aproiri算法的研究与改进[J]．微电子学与计算机，2013，30(9)：110-114．

[3]赵伟卫，赵航等．基于MapReduce的海量数据挖掘技术研究[J]．计算机工程与应用，2013，49(20)：112-117．

[4]霍然，王宏志等．基于Map-Reduce的大数据实体识别算法[J]．计算机研究与发展，2013，50(16)：170-179．

[5]应毅，刘亚军．MapReduce并行计算技术发展综述[J]．计算机系统应用，2014，23(4)：1-11．

Association Rules Mining Based on MapReduce

Chen Fengjuan
(Liaoning University of International Business and Economics,Dalian 116052,Liaoning)

tract】 Association rules mining is one of the most important techniques of data mining.It mainly gets the association rules by mining frequent itemsets.The data mining algorithms which are based on MapReduce model of cloud computing can improve the effect and performance.

words】 association rules;frequent itemset;MapReduce;data mining

陈凤娟，女，辽宁本溪人，硕士，副教授，研究领域：数据挖掘、粗糙集。