基于Map Reduce关联规则算法的研究与改进

　　第 3 章 基于 MapReduce 关联规则算法的研究与改进

　　在第 1 章绪论中，对比了国内外在教育数据中研究的现状，发现很少有对学生成绩数据进行研究的；通过查阅大量的文献，发现有一些研究者采用传统的关联规则算法-Apriori 挖掘教育数据，而通过仔细的研究学生成绩数据的特点，发现没有更好的算法比关联规则算法更适合学生成绩数据的分析。而在大数据技术兴起的这几年里，也有一部分研究学者将传统的 Apriori 算法结合大数据技术进行了改进。但是，大部分文献都是对 Apriori 算法中的发现频繁项集这一部分内容作了改进，却没有实现强关联规则；在本文所采用的 Hadoop 平台上有一个名为 Mahout 的子项目，提供了机器学习中很多经典的算法的实现，其中就包括Apriori 算法，但是 Mahout 也只是能计算频繁项集也没有实现关联规则。而单凭频繁项集的结果并不能很好的说明课程之间存在的某些相关性，因此本文提出了一种基于 MapReduce 的 Apriori 关联规则改进算法，通过改进后的算法才能更深入的挖掘海量的教育数据。

　　本章对传统的 Apriori 算法和改进后的算法进行了阐述，并且通过改变数据集大小、改变支持度阈值和改变置信度阈值三种方式验证了改进后算法的执行效率和性能优越性。

　　3.1 Apriori 算法简介。

　　目前，有很多方法应用于教育数据的挖掘[48],这些方法都是基于以下几个类别：预测、聚类、关联模型和知识发现等。关联规则挖掘的目标是要找到 IF-THEN形式的规则[49],如果发现了一些设定的变量值，其它一些变量也会具有一个特定值。有这样一个真实案例：美国 Wal-Mart 超市通过对超市购物篮数据进行分析，即对顾客购物篮中的商品进行分析，从而发现顾客的购物习惯。他们发现啤酒和尿布出现在同一个购物篮里的机会很多，于是商家就将啤酒和尿布放在相邻的货架上摆放，这个举措使尿布和啤酒的销量双双增加，为商家带来了大量的利润，并一直被众商家所津津乐道。关联规则分析的是在一个数据集中找出项与项之间的关系，也被称为购物篮分析。Apriori[50]

　　算法是由R .Agrawal和 R .Srikant在1994年提出的，最早应用于 Wal-Mart,主要的应用就是从商业记录中发现数据的关联关系，用于商家决策。

　　Apriori 有几个比较重要的概念：

　　①支持度。

　　A->B 例如有两个事务 A 和 B,那么支持度 support=P（AB），表示事件 A 和 B同时发生的概率。

　　②置信度。

　　置信度 confidence=P（B|A）=P（AB）/P（A），表示发生事件 A 的基础上发生事件B 的概率。

　　例如 support=20%,confidence=60%,就表示 A 和 B 同时出现的概率是 0.2,并且在 A 出现的基础上 B 出现的概率是 0.6.强关联规则需要满足最小支持度和最小置信度。

　　③k 项集。

　　k 个项组成的项集④频繁项集。

　　满足最小支持度的项集，频繁 k-项集一般记为 LkApriori 有两个重要的性质：

　　其一：频繁项集的所有非空子集也一定是频繁的；其二：非频繁项集的超集一定是非频繁的。

　　求解频繁项集的基本思想分为两步：

　　Step1: 连接为了搜索 k 项集，将 k-1 项集自连接产生候选的 k 项集，称为候选集；为了有效的实现连接，首先对每一项进行排序，其次，若满足连接的条件（连接的条件，前 k-2 项相同，k-1 项不同），则进行连接。

　　Step2:剪枝k 项集的每一个 k-1 项子集都存在 k-1 项集，并且支持度满足最小支持度阈值Apriori 算法求解频繁项集描述。

　　从图中可以看到：

　　L1-->C2时，若支持度的阈值很低，L1会很大，则 L1-->C2产生的组合太多。而每一次的剪枝都要在数据集中过滤一下，也就是要反复扫描数据集，如C2-->L2.

　　求解关联规则的基本思想为：

　　根据频繁项集生成强关联规则，首先要找到频繁项集的所有非空真子集，然后根据 minConf（最小置信度）来得到强关联规则。

　　求解关联规则的过程描述。

　　3.2 Apriori 算法的缺陷。

　　采用 Apriori 算法对于简单的数据库来说具有较好的数据挖掘能力，但它也具有一定的局限性：（1）在生成侯选项目集时产生了较多的组合，有一些项目并不在这些组合里却参与了产生组合的过程；（2）当计算每一个项集的支持度时，都会反复扫描数据库，如果数据量很大时，扫描数据库所花费的开销将会成为算法的瓶颈。所以当数据量增加到一定程度时，传统的算法受到计算机内存的限制将不能执行，图 3.3 为当数据量为 11M（与机器的物理内存有关，本机的内存较小）时算法所报出的异常：

　　可见当我们把数据集增大到 11M 时 , 算法就会抛出异常 :

　　java.lang.OutOfMemoryError:Java heap space,出现这种异常明显是 JVM 内存不够的原因，而 JVM 内存又不可能大于实际的最大物理内存，所以说传统的 Apriori 算法完全不能处理海量数据集，因此就需要利用大数据技术的优势对 Apriori 算法进行改进，让传统的 Apriori 算法移植到大数据平台来处理，因此本文设计一种适合 Hadoop 平台的 Apriori 算法-基于 MapReduce的 Apriori 关联规则算法的改进，在下一个小节进行介绍。

　　3.3 基于 MapReduce 的 Apriori 算法的研究与改进。

　　在处理海量数据集上，Apriori 算法在寻找频繁项集这一过程中会大大降低系统的执行效率。本文设计的基于 MapReduce 的Apriori 改进算法，是将 MapReduce的 Map 和 Reduce 函数引入 Apriori 算法中，MapReduce 可以并行处理海量数据极大的提高了寻找频繁项集效率。而且通过并行化可以使 Apriori 算法处理大量的数据而不受单机运算能力的限制。

　　改进算法的主体思想如下：

　　①首先在 Map 阶段生成频繁 k 项集，这里用到了连接操作，通过 k-1 项集自连接产生候选 k 项集，然后以项集作为 key,支持度作为 value;②Reduce 阶段的任务是将相同 key 的 value 进行合并，同时要进行剪枝操作，即筛选出大于 minSup（最小支持度）的项集；③根据得到的频繁项集生成关联规则，这里最重要的一步就是根据频繁项集找到其所有的非空真子集，并且还要满足 minConf（最小置信度）。

　　下面将分别介绍每部分的具体实现过程:
发现频繁项集
ItemSetMap():
输入：数据集 D
输出：项目集
for each t ∈ D do //生成事务集
for each item ∈ t do //提取每个事务集的项目集
Content.write(item,1) //计数
end
end
ItemSetReduce():
输入：<item,1>，最小支持度阈值 minSup
输出：频繁项集 freqItemSets
Int sum=0;
for each v in values do //遍历项目集
sum += value.get() //统计个数
if (sum >= minSup)
context.write(key, sum) //输出满足最小支持度阈值的项集
end
end
生成关联规则
输入：频繁项集 freqItemSets，最小置信度阈值 minConf
输出：k-项频繁集存入路径 k_0utputpath
for each itemset in freqItemSets //遍历项目集
for all i-itemSet //获得每个项目集的非空真子集
conf = 1.0 * itemSet.getSupport() / occurrence.get(itemSet.getItems())
//计算置信度
if (conf >= minConf)
context.write(itemset, Conf) //输出满足最小置信度阈值的项集
end
end
end
 

　　3.4 改进算法的可行性分析。

　　①在 3.2 小节中介绍过当数据集增大到 11M 时，传统的 Apriori 算法根本不能运行，为了能运行大数据集，我们搭建了 Hadoop 计算机集群（2 个节点），首先简单介绍一下集群环境，具体搭建过程将在下一章介绍。

　　②而经过试验验证本文改进的算法确可以运行大数据集，图 3.5 为当数据为11M 时 Hadoop 集群的运行过程，可见 map 和 reduce 阶段 100%运行成功了：

　　③为了进一步验证算法的可行性，为例验证 MapReduce Apriori 算法的可行性，通过运用一个简单的事务集对算法进行实例分析，本文所使用的实验环境将在第四章介绍，图 3.6 为事务集信息：从实验中我们可以看出改进的 MapReduceApriori 算法是可行的。

　　④为了验证改进后的 MapReduce Apriori 算法的优越性及其稳定性，分别采用1M 到 10M 的数据应用到两种算法中，图 3.9 为改变数据集大小后两种算法的响应时间的对比；进而又分别通过改变两种算法的最小支持度和最小置信度来验证算法的稳定性，图 3.10 为改变支持度时两种算法的响应时间的对比，图 3.11 为改变置信度时两种算法的响应时间的对比。

　　从实验中我们可以看出改进的 MapReduce Apriori 算法是可行的并且性能稳定的。

　　3.5 本章小结。

　　本章分别介绍了传统的 Apriori 算法以及 MapReduce Apriori 算法的原理，然后通过实验验证了算法的可行性和性能优越性。只有将传统的 Apriori 算法进行MapReduce 并行化处理才能移植到 Hadoop 平台上，而为了更深入的挖掘学生数据中的关联关系，改进后的算法不仅实现了挖掘频繁项集这一步骤也实现了强关联规则。