英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
一种改进的基于Power Set和Hadoop的关联规则挖掘算法
摘要
关联规则挖掘在数据挖掘中具有重要的影响。 随着数据集的快速增长，它所需的内存急剧增加且运行效率迅速下降。 云计算提供高效且便宜的解决方案来分析并改善关联规则并行挖掘算法。本文提出了一种基于Power Set和MapReduce编程模型改进的关联挖掘算法，它可以利用Hadoop平台上的机器集群来处理海量数据集。大量实验的结果表明所提出的算法可以在关联规则中实现更高的效率。
关键字：数据挖掘；关联规则挖掘；云计算；MapReduce；Power Set；
I介绍
数据挖掘被称为一种知识发现方法，它可以自动发现隐藏的和有用的来自数据库的信息。 关联规则挖掘可以在交易数据库中找到规则，同时在数据挖掘中扮演着重要的角色。
Apriori算法[1]是最著名的传统关联规则挖掘算法之一，它通过频繁k项目集的自连接迭代地产生k 1项候选集以及重复扫描数据库来计算每个候选人的频率。Apriori算法可以被描述以下为两个步骤：首先，它找到所有的频繁项目集，其中每一个必须超过预设的支持计数，mini_sup。 其次，它使用频繁项目集来生成令人关注的关联规则。 主要的工作重点是在关联规则挖掘中找到频繁项目集。为了得到所有的频繁项目集，它需要重复地扫描数据库。随着数据库规模增加，计算时间和所需内存急剧增加。
为了解决上述问题，并行关联规则算法已经在[2]，[3]中提出，它们是计数分布、候选分布和数据分布。它们各有优势，但也有很多问题，比如网络交互频繁、同步成本代价高、每个节点的负载不均衡等等。 如今，云计算[4]将整个计算过程分成许多小任务，然后将这些任务分配给由大量普通计算机组成的任务调度池，对解决存在的问题传统关联规则挖掘具有许多优点。
本文提出了一种改进的关联规则挖掘算法-AprioriPMR。 它使用Power Set和云计算的MapReduce来改进Apriori算法并并行查找隐藏在海量数据集的关联规则。 实验结果表明该提出的AprioriPMR算法在处理时间和可扩展性上具有优异的性能。
本文的其余部分由以下几部分组成。 第2节介绍一些背景知识。接下来，第3部分提出了架构和改进关联挖掘算法。 然后，第4节分析性能研究的结果。 最后，第5节给出了一个结论。
II 背景
A.关联规则
[1]介绍了挖掘关联规则的关键步骤。令 I = 是一组项目集。令 DB = 为事务数据库，其中每个事务是一组项目集，并且sube;I。给定一组项目Xsube;I，当且仅当Xsube;T时，事务T包含X.然后，关联规则可以表示为形式，其中Xsube;Y，Ysube;I和。
给定一组交易数据库DB，关联规则挖掘的主要过程就是分别找到所有的比用户指定的最小支持度mini_sup和最小可信度mini_conf大的支持度和可信度的项目集。
发现所有关联规则的主要过程可以被认为是两个子问题[5]：
bull;查找所有的项目集，这些项目集的支持度等于或大于最小支持度。这些项目集称为频繁项目集。一个项目集的支持度是包含这个项目集的交易量的总和。
bull;使用频繁项目集生成所需的规则。主要思路如下：如果说，ABCD和AB是频繁项目集，那么我们可以通过计算可信度的比率确定规则？如果，则规则成立。 （因为ABCD是频繁项目集，所以规则肯定会有mini_sup）大量的研究集中在第一个子问题，因为它决定关联规则挖掘的大多数性能。
B. MapReduce和Hadoop
MapReduce[6]是一个并行编程模型，它通常用于生成和处理大型数据集。该
并行处理被描述为两个功能：Map和Reduce。Map函数处理lt;key，valuegt;键值对后生成一组中间lt;key，valuegt;键值对，然后Reduce函数合并并处理这些lt;key，
值gt;键值对，它们具有相同的中间键。在处理数据集时，该Map和Reduce函数都遵循形式为lt;key，valuegt;键值对的数据格式，。然后，Map和Reduce函数具有相关性的数据类型：
Map（k1，v1）→list（k2，v2）
Reduce（k2，list（v2））→list（k3，v3）
Hadoop是一个编程框架,它可以在数千台电脑上构建的大型集群上执行程序，同时，它也是MapReduce[7]，[8]的开源实现。Hadoop作为处理海量数据集并进行深入分析的高效平台，它可以将作业划分为大量的小任务，每个小任务都可以在集群中的任何一台计算机上执行或重新执行。 Hadoop分布式文件系统（HDFS），它将数据集分成许多常规数据块并创建指定数量的这些块的复制品，然后将它们分配给集群上的不同节点，具有极高存储原始数据、中间数据和结果数据[9]的效率。此外，它提供了在集群中非常高的瞬时通信并减少在网络通信、调度和处理中间结果总资源的消耗。
- Power Set
在数学中，任何集合S的幂集写成作为P（S），是S的所有子集的集合，包括空集和S本身。如果S是| S | = n个元素的有限集合，那么S的子集数是。例如，如果S是集合{x，y，z}，那么P（S）是{{}，{x}，{y}，{z}，{x，y}，{x，z}，{y，z}，{x，y，z}}。
III改进的关联规则挖掘算法：AprioriPMR
- 传统Apriori的描述
Apriori的主要思想是：产生候选人项目集，然后扫描数据库以确定这些项目集是否满足最低的支持度。Apriori的第一阶段只计算项目的发生次数以找出频繁1项集。然后，接下来就是阶段k，由两个步骤组成。首先，在第（k-1）次迭代中被找到的频繁k-1项集，它用于生成候选k项集。接下来，程序扫描数据库并计算的候选集的支持度。 Apriori算法可以描述如下：
输入：D（数据库中的事务），最小支持度mini_sup
输出：L（频繁项目集）
方法：
（1）L1 = find_freq_1-itemsets( D ); //查找D中频繁1项集;
（2）for（k = 2;！=empty;; k ）{
（3） = Apriori_gen（）; //获取k项候选集
（4）对于所有的交易tisin;D{//扫描D计数
（5） = subset（，t）; //获取t的子集
（6）对于所有候选集cisin;{
（7）c.count ;
（8）}
（9）}
（10） = {cisin;| c.countmini_sup};
（11）}
（12）返回L = L;
Apriori_gen（Lk-1）和subset（Ck，t）函数在[1]中给出。
- AprioriPMR算法
在Apriori算法的计算过程中，我们可以发现频繁项目集Lk的每个元素都是Power Set 的一个非空元素，这些元素是从交易数据库中产生的。为了减少传统Apriori算法的迭代次数，我们可以计算数据库中的每条交易行为的幂集（Power Set），然后统计每个元素的幂集（Power Set）。基于上述想法，我们给出了一个并行方法来处理关联规则挖掘和具体的想法如下：
（1）计算频繁1项集。
（2）然后，水平把交易数据库划分成n个数据块并把这些数据块发送给m个节点。
（3）每个节点扫描被划分的数据块和每个事务保留存在于频繁1项集中的项目以生成项目集S.接下来，程序产生幂集，其中的每个元素可以看作一个候选项目集c。每个候选项目集的支持度被设置为1，然后就产生了一个lt;c，1gt;键值对。接下来，所有lt;c，1gt;键值对生成一组候选项目集。
（4）被分成r个不同的分区和这些带有支持度计数的分区被发送到r个节点。
（5）的每个元素都可以看作lt;key，valuegt;键值对。所有具有相同key的键值对都被发送到相同的位置节点。所以r节点分别累计相同项目集的支持度计数来产生最终的实际支持度，在与最低支持mini_sup比较后确定分区中的本地频繁项目集。
（6）通过合并r节点的输出生成最终的频繁项目集L。
（7）用L查找关联规则。
给定方法的优点是扫描两次交易数据库它就可以找到全部的频繁项目集，一次用于生成频繁项目集和另一次产生频繁项目集L。
表1 Map和Reduce函数的lt;key,valuegt;键值对
|
Input/Output |
Map |
Reduce |
|
Input: lt;key, valuegt;键值对 |
Key: 行号 Value: 一行的数据 |
Key: 候选集 Value: 1 |
|
Output: lt;key, valuegt;键值对 |
Key: 候选集 Value: 1 |
Key: 频繁候选集 Value: 支持度 |
我们将MapReduce编程模型部署到实施上述提出的方法并描述他们的组合作为一种改进的关联挖掘算法，并将其命名为AprioriPMR。 这些数据集存储在文件并上传到HDFS。 这些文件分为N个数据段和每个段的大小设置为64MB。在这些文件中，每行可以看作是一个交易事务，每个项目由空格键分隔。 Map函数和Reduce函数的lt;key，valuegt;键值对的描述如表1所示。
图1. AprioriPMR算法的数据流
总体思路是我们使用AprioriPMR算法来获得两个MapReduce操作中的频繁项目集。首先，算法将每个事务分解为一个带空格键单词集合，然后，在Map函数中将每个单词的计数设置为1，并在Reduce函数执行后获取频繁1项集。频繁1项集存储在HDFS中。其次，通过使用频繁1项集，在执行Map函数之后，就会产生带有自身总数的候选项目集，接下来，在执行Reduce函数后，生成频繁项目集。
图1显示了AprioriPMR算法的MapReduce框架的数据流和不同的步骤。 AprioriPMR算法定义的伪代码可以描述为如下：
MapReduce 1
Map 函数：
输入：D（D分为n个数据块和HDFS中的第i个数据块被定义为，）。
输出：lt;key，valuegt;键值对，key是一个事务中的任何单词，它的值被设置为1。
（1）foreach（中的事务t）{
//用空格键分隔事务。
（2） = split（t）;
（3）foreach（itemcisin;）{
（4）write（c，1）; // lt;key，valuegt;键值对
（5）}
（6）}
Reduce 函数：
输入：lt;key，valuegt;列表（在Map函数中生成），keyList（由不同的key组成），mini_sup（最小支持度门阀）。
输出：lt;gKey，gValuegt;键值对（频繁1项集）。
（1）foreach（keyList中的gKey）{
（2）lt;gKey，gValuegt; .gValue = 0;
（3）foreach（lt;key，valuegt; p lt;gKey，1gt; list）{
（4）lt;gKey，gValuegt; .gValue = lt;gKey，gValuegt; .gValue p.value;
（5）}
（6）if（lt;gKey，gValuegt;.gValueminisup）{
（7）write（gKey，gValue）; // lt;key，valuegt;键值对
（8）}
（9）}
MapReduce 2
Map 函数：
输入：D（D分为n个数据块和HDFS中的第i个数据块被定义为，），（在MapReduce1中产生）。
输出：lt;key，valuegt;键值对，key是幂集的一个元素，值被设置为1。
（1）foreach（中的事务t）{
//从t中删除L1中不存在的项目集
（2） = t.retainAll（）;
（3）P（S）= powerset_gen（）;
（4）foreach（setsisin;）{
（5）write（s，1）; // lt;key，valuegt;键值对
（6）}
（7）}
Reduce 函数：
输入：lt;key，valuegt;列表（在Map函数中生成），keyList（由不同的key组成），mini_sup（最小支持度门阀）。
输出：lt;gKey，gValuegt;键值对（频繁项目集L）。
（1）foreach（keyList中的gKey）{
（2）lt;gKey，gValuegt; .gValue = 0;
（3）foreach（lt;key，valuegt; p
全文共9010字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[9868]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
