大数据背景下Hadoop技术在关联规则挖掘中的应用

李泽龙

贵州师范大学 国际教育学院，贵州 贵阳 550000

0 引言

随着信息技术的快速传播，大多数数据都是数字化的，对于数据的处理和有价值信息的挖掘成为了一个值得探索的技术，数据挖掘技术应运而生。对具有价值的数据信息的分析与识别，都是通过对大量、动态且能够持续的数据运用新的系统、工具和模型进行充分的挖掘和分析得到的[1]。在进入大数据时代后，大量数据的涌现使得如何处理大规模数据的问题仍然存在。大数据意味着数据无法被大多数当前的信息系统或方法处理和处理，因为大数据时代的数据不仅会变得太大而无法加载到一台机器中，还意味着大多数传统的数据挖掘方法或为集中式数据分析过程而开发的数据分析可能无法直接应用于大数据。

1 大数据发展现状

信息技术的进步促进了数据的大容量、高速度和连续存储数据的能力，这导致了几个计算方面的挑战。由于大数据在体积、速度、多样性、可变性、准确性、波动性以及最近产生的价值等方面的特性，大数据计算是未来计算的新趋势。大量的原始数据围绕着我们，这些数据无法由人类或手动应用程序直接处理。互联网、工程和科学应用和网络、商业服务等技术，由于开发了强大的存储和连接工具，数据呈指数级增长。面对这种海量数据的增长，有价值的信息不容易获得也无法自动提取。数据科学和数据挖掘在当前信息时代变得越来越流行。

如今，我们管理处理的当前数据量已经超过了传统系统的处理能力，这也适用于数据挖掘。新技术和服务（如云计算）的出现以及硬件价格的降低正在导致互联网上的信息率不断提高。大数据已成为信息和企业信息科学、商业活动、政策、公共管理以及决策者的重要研究领域。它还带来了新的研究范式和未来专注于大数据的业务。信息技术的进步促进了大量、高速度的数据，以及连续存储数据的能力，从而带来了一些计算挑战。

2 关联规则与频繁项集挖掘的意义

数据技术诞生初期被称为数据知识库中的知识发现，基于本质出发，数据挖掘技术的基础就是信息技术中所涵盖的数据库[2]。数据挖掘是从大型数据中提取隐藏且可能有用的信息，这是从数据中发现知识的基本过程。在大数据如日中天的时代，快速、可扩展的数据优化技术势在必行。关联规则最初是在超市销售中提出的，业主希望从交易记录中找到有用的信息，以帮助决策者制定销售计划，经理可以使用这些信息来调整商店布局，安排交叉销售等[3]。传统的关联规则挖掘算法主要是用于挖掘正关联规则。正关联规则挖掘查找彼此正相关的项目，即如果一个项目上升，相关项目也会上升。虽然正关联规则挖掘的经典应用是市场篮子分析，但正规则挖掘的应用已经扩展到广泛的领域，如生物数据集、网络日志数据、欺诈检测、人口普查数据等。负关联规则可以定义为负相关的项目，即，如果一个项目上升，另一个项目下降。负关联规则挖掘也有许多应用，包括建立有效的决策支持系统，在犯罪数据分析，在医疗保健领域等。

关联规则挖掘(ARM)是一种发现集中数据之间的关联的数据挖掘技术。为了消除那些无用的关联规则，关联规则挖掘分为两个步骤：（1）生成所有的频繁项集；（2）由频繁项集产生关联规则。在这两步中，第二步是在第一步获得的频繁项集基础上产生关联规则，挖掘性能取决于第一步[4]。频繁项集挖掘(FIM)，又称频繁模式挖掘，它尝试从给定的数据库或是数据集中去挖掘一些有趣的模式，例如关联规则、相关性等[5]。特别是，关联规则描述了经常一起购买的物品，这在零售业和电子商务中很有价值。因此FIM被广泛应用于客户推荐系统中。此外，关联在网络搜索或日志分析中具有重要的价值，使FIM成为这些领域的重要方法。三个著名的FIM基本算法是Apriori，FP-Growth和Eclat。为了加快频繁项集的生成，研究人员对这些算法进行了许多改进。由于这些算法具有序贯计算的特性，在应用于大数据集的处理上还存在问题。

3 频繁项集挖掘基本算法分析及其存在的问题

3.1 Apriori算法

Apriori算法用来数据中的共同模式，标识的频繁模式用于生成关联规则。首先，通过扫描原始数据集，计算每个候选数据项集发生的次数，然后基于预先给定的最小支持阈值生成频繁1项集的集合，该集合记录为L1；然后，基于L1和数据集中的数据，产生频繁2项集L2；用同样的方法，直到生成频繁n项集Ln，并且已经不再能生成满足最小支持阈值的n+1项集为止;；最后根据频繁项集和原始项集导出关联规则[6]。在处理大型数据集时，在每次迭代中重复扫描输入数据集会成为一项繁琐的任务。此外，如果阈值设置得很低，Apriori将需要高内存才能生成许多候选项集。它只使用在前一次传递中发现较大的项集，而不考虑数据库中的事务，从而生成要在一次传递中计算的候选项集。当遇到大量的频繁模式、长模式或较低的最小支持值时，Apriori在存储和处理大型候选项集以及扫描它们的工作中有相当大的计算量。这在大数据时代是该算法的一大挑战。

3.2 FP-Growth算法

FP-Growth是一种关联规则挖掘算法，它从数据库中发现整个FP集。首先，获得所有频繁的单例项集，并根据其支持对递减顺序中的频繁项目进行排序。然后使用频繁的单例项目集构建FP-Tree，在FP-Tree上执行挖掘，并创建子数据库，此过程以迭代方式执行。因此，从输入数据集中频繁挖掘项集的任务将转变为挖掘FP-Tree，从而维护项目集的关联信息。前缀树用于将数据库存储在FP-Tree紧凑模型中。FPGrowth算法使用分而治之技术，该技术可最大程度地减小FP树的大小。它将较长的FP拆分为较小的模式，并将常用项的后缀链接在一起。因此，搜索频繁模式所需的时间最小化。该算法使用模式增长方法，降低了生成和测试候选项所需的成本。然而，像并行算法一样FP-growth的一个主要缺点在于构建内存中的FP-Tree来适应大规模的数据库是不可行的。

3.3 Eclat算法

Eclat算法不是以迭代方式访问输入数据集，而是采用垂直数据格式来支持通过交叉点的项集。它仅扫描输入数据集一次，并在生成候选项集时有效地使用apriori属性。如果为每个项集设置的事务ID太大，则Eclat可能需要大量内存和计算时间来与长集相交。一种称为diffset技术用于通过仅跟踪相交集之间的差异来降低长相交的成本。当数据集包含许多密集和冗长的模式时，diffset过程可显著提高性能。但是，当数据较小时，对内存的需求仍然存在，并且在交集之后查找结果集也具有挑战性。

4 Hadoop分布式数据分析技术

4.1 Hadoop分布式框架

Hadoop是一个大规模的分布式框架，可以安装在商用Linux集群上，用于并行处理大数据，允许大规模的分布式数据分析。除了可能的更改以满足每个节点的最低推荐RAM，磁盘空间等要求之外，不需要任何硬件修改。Hadoop有一个主/从架构。每个集群上有一个主节点和多个从节点。从节点通常被称为DataNodes，主节点被称为NameNode。NameNode分配块ID，DataNode存储实际文件。Hadoop支持使用计算机集群对数据集进行收集、存储、检索和管理。Hadoop是用于并行处理的高性能密集型、可扩展且灵活的开发框架。Hadoop框架通过检测和处理应用层本身的故障来提供可靠的服务可用性。Hadoop是一个基于无共享体系结构的容错系统。它将计算移动到执行期间具有数据的节点，而不是将数据移动到节点。数据存储和计算由Hadoop的两个核心组件处理，分别为MapReduce和Hadoop分布式文件系统（HDFS）。

4.2 MapReduce数据处理框架

Hadoop的分布式计算环境使用MapReduce编程范式来支持大量数据的并行处理。MapReduce是一个容错、简单、可扩展的数据处理框架，允许用户处理这些海量的数据，它是一个高效的大规模数据处理框架。MapReduce有两个主要组件：Mapper和Reducer。映射器采用输入键值对（k1，v1）并计算中间键值对（k2，v2）中间键值对在映射器和化简器之间随机排列和交换。Reduce函数采用中间键值对并产生最后输出（k3，v3）。有一个可选的合路器功能，可以在映射器和化简器功能之间使用。合路器主要用于降低将中间输出从映射器传输到化简器的通信成本。

Hadoop采用MapReduce执行引擎，工作流程分六步进行：①用户将作业提交到队列，集群按顺序运行它们；②主节点将Map任务和减少任务分发给不同的工作线程；③映射任务读取数据拆分，并对读入的数据运行映射函数；④映射任务将中间结果写入本地磁盘；⑤Reduce Tasks远程读取中间结果，并对读入的中间结果运行Reduce函数；⑥这些减少任务将最终结果写入输出文件。映射输出是一系列以键值对形式存储在该节点上的记录。在Map阶段中的所有数据都传输到相应的计算机之前，将阻止第二个Reduce阶段进行。Reduce阶段生成另一组键值对，作为最终输出。这是一个简单的编程模型，仅限于使用键值对，但这个框架将容纳数量惊人的任务和算法。此外，虽然Hadoop目前主要用于非常大的数据集的批量分析，但没有什么可以排除使用Hadoop进行计算密集型分析。

4.3 Hadoop分布式文件系统

HDFS是一个分布式文件系统，用于在商用的架式硬件上运行。HDFS的主要目标是在大型集群中使用常见的商用服务器，其中每个服务器都有一组磁盘驱动器。HDFS是Hadoop对分布式文件系统的实现。它旨在保存大量数据，并为分布在网络上的许多客户端提供对此数据的访问。HDFS的文件系统将文件划分为固定的块大小，同时块的大小可以按照需求改变。HDFS由多个用于存储数据的DataNode和一个名为NameNode的主节点组成，用于监控DataNodes并维护所有元数据。HDFS作为提供服务的存储系统，可以分为客户端和服务器。因此，HDFS通常分为三个节点：Client、NameNode和DataNode。每个节点都可以与其他节点进行交互，有助于实现分布式文件系统并支持集群之间的可扩展性。客户端计算机的作用是通过与 NameNode上的可配置TCP端口建立连接，将数据加载到群集中。NameNode执行文件系统命名空间操作，也确定块到DataNodes的映射。DataNodes在NameNode的管理下执行对象创建、删除和复制。

5 Hadoop技术在关联规则挖掘中的应用

5.1 采用Hadoop提高频繁项集挖掘算法的效率

第一个MapReduce任务是确定频繁的1项集。第一个MapReduce作业的输入是事务性数据集。当数据被读入HDFS时，数据被分成块，分布在多个映射器上。映射器每次读取一个事务，输出一个键值对。然后，键值对被传递到reduce阶段。Reducer将获取这些键值对，并将各自键的值相加。Reducer将输出(item， total_count)。Total_count与min_supp进行比较，并且那些等于或高于min_supp阈值的条目被保留为频繁的1项集。然后将频繁的1项集及其各自的支持值写入分布式缓存。

第二个MapReduce任务是生成频繁的2项集。第二个MapReduce作业的输入是来自第一个MapReduce作业和事务数据库的频繁的1项集。频繁的1项集从分布式缓存中读入。与第一个MapReduce作业并行的是，在map阶段生成2项键值对。然后，2项键值对被传递到第二个MapReduce作业的reduce阶段。同样，与第一个MapReduce作业并行，减速机然后获取这些对，并汇总各自键的值。Reducer将输出（item，total_count）。然后将Total_count与min_supp进行比较，那些等于或高于min_supp阈值的将被保留为频繁的2项集。然后将频繁的2项集及其各自的支持值写入分布式缓存。需要多少项集，就会有多少类似的MapReduce任务。

第三个MapReduce任务是一个仅映射的操作。MapReduce作业2的输出（经常是2-itemset）从分布式缓存读入MapReduce作业3。在MapReduce作业3中，通过计算频繁2项集的置信度和提升度来确定正关联规则和负关联规则。如果（A B）的置信度大于最小置信度阈值，且（A B）的上升幅度大于1，则为正关联规则。如果（A and not B）或（not A and B）或（not A and B）的置信度大于最小置信度阈值，且同一规则的提升度也大于1，则为负关联规则。

5.2 采用Hadoop改进频繁项集挖掘算法的优势

Hadoop提供了可扩展性和容错能力。Hadoop的分布式文件系统的大小取决于集群的大小，HDFS确保快速和可扩展地访问数据。HDFS以块的形式分解大数据，并以复制的方式将它们存储在集群的不同节点上。应用程序作为MapReduce作业提交，该作业被分为多个独立的任务，并在集群中的不同数据块上同时执行。通过将数据划分为不同的任务来实现的，这些任务充当映射任务和化简器进程的输入，结果是从映射器接收的数据。较大的数据基本上分布在节点中。如果网络中的任何节点发生故障，系统仍可正常运行。这降低了灾难性系统故障的风险。

Hadoop技术可以提高算法的效率和执行的准确性。分布式文件计算形成由多个计算机节点组成的大型集群。节点由JobTracker和TaskTracker组成。JobTracker通过计划和监视任务来执行作业。TaskTracker为复制的输入数据执行任务。此外，在任务执行失败后，JobTracker将重新调度到另一个TaskTracker。由于TaskTracker已复制数据，因此执行任务的结果会产生错误。如果在某个TaskTracker执行任务时发生错误，则会将其报告给JobTracker。在这种情况下，JobTracker会命令另一个TaskTracker从发生错误的部件执行任务。由于它们都使用相同的数据重复任务，因此调度结果的误差很小，并且准确性保持高且一致。

6 结语

由于信息技术革命带来的挑战和机遇，大数据分析已经成为竞争和创新的新前沿。抓住大数据分析机会和数据挖掘技术可以获得实时稳健决策的洞察，关联规则挖掘用于发现项目或项目集之间的关联。本文通过分析关联规则挖掘基本算法存在的问题，提出了Hadoop技术在关联规则挖掘中的应用策略，Hadoop分布式批处理系统是一个基于无共享体系结构的容错系统，数据存储和计算由分别由分布式文件系统和MapReduce两个核心组件进行处理，在它将计算移动到执行期间具有数据的节点，而不是将数据移动到节点。Hadoop技术在关联规则挖掘中的应用可以提高相关算法的效率和执行的准确性，具有良好的可扩展性和容错能力。