搜索
基于MapReduce和GPU双重并行层次下的关联规则挖掘的探讨计算机学院2011级硕七班张宗禹21121276摘要：数据挖掘是指从巨量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程。而关联规则就是其中一种典型的例子,本论文主要关注关联规则的挖掘。在许多情况下，将所有数据集中在一起进行分析往往是不可行的。分布式数据挖掘系统则可以充分利用分布式计算的能力对相关的数据进行分析与综合，再加上可以节省大量的时间和空间开销，分布式数据挖掘应运而生。同时，随着数据量的指数型增加以及对计算量的需求急切增长，已有的数据挖掘软件很难满足应用的实时性需要，人们对并行数据挖掘技术的需求十分强烈。图形处理器(GPU)的最新发展已经能够以低廉的成本提供高性能的通用计算。本文将在介绍当前分布式数据挖掘的发展现状和趋势，以及当前基于GPU的并行数据挖掘发展现状的同时，从理论上以关联规则挖掘为例探讨一种将这两种正火热的技术结合的方法。关键字：数据挖掘、关联规则、MapReduce、GPGPU、CUDA、HadoopStreaming1．研究背景和现状1.1云计算框架Hadoop和MapReduce计算模型云计算的核心思想，是将大量用网络连接的计算资源统一管理和调度，构成一个计算资源池向用户按需服务。提供资源的网络被称为“云”。Hadoop是一个能够对大量数据进行分布式处理的软件框架。但是Hadoop是以一种可靠、高效、可伸缩的方式进行处理的。Hadoop是可靠的，因为它假设计算元素和存储会失败，因此它维护多个工作数据副本，确保能够针对失败的节点重新分布处理。Hadoop是高效的，因为它以并行的方式工作，通过并行处理加快处理速度。Hadoop还是可伸缩的，能够处理PB级数据。此外，Hadoop依赖于社区服务器，因此它的成本比较低，任何人都可以使用。Hadoop带有用Java语言编写的框架，因此运行在Linux生产平台上是非常理想的。Hadoop上的应用程序也可以使用其他语言编写，比如C++，当然也自然可以用CUDA语言，之后会详细说明。Hadoop最有趣的方面之一是MapandReduce流程，它受到Google开发的启发。MapReduce本身就是用于并行处理大数据集的软件框架。MapReduce的根源是函数性编程中的map和reduce函数。它由两个可能包含有许多实例（许多Map和Reduce）的操作组成。Map函数接受一组数据并将其转换为一个键/值对列表，输入域中的每个元素对应一个键/值对。Reduce函数接受Map函数生成的列表，然后根据它们的键（为每个键生成一个键/值对）缩小键/值对列表。1.2GPGPU以及CUDA编程GPGPU全称GeneralPurposeGPU，即通用计算图形处理器。这个GPU可以分担CPU的处理任务，一般集成在CPU上。近年来，计算机图形处理器（GPU，GraphicsProcessingUnit）正在以大大超过摩尔定律的速度高速发展，极大的提高了计算机图形处理的速度和质量，不但促进了图像处理、虚拟现实、计算机仿真等相关应用领域的快速发展，同时也为人们利用GPU进行图形处理以外的通用计算提供了良好的运行平台。GPU应用领域的拓宽与其硬件发展有着极大关系。GPU自1999年首先由NVIDIA公司提出后，就其发展的速度而言，是CPU更新速度的三倍。从1993年开始，GPU的性能以每年2.8倍的速度增长。目前，图形处理器已经经历了五代发展，平均每半年就有新一代的GPU问世。GPU具有四大优势：分别是众多的处理单元(ALU)，高数据带宽的运算，高效的并行性，超长图形流水线。在3D领域，GPU的用途很简单，就是为拉更好的渲染3D场景，减轻CPU在图形运算方面的负担。时下刚刚出台的GPGPU，是将应用范围扩展到图形之外，无论是科研教育，财务计算，还是在工业领域，GPGPU都得到拉广泛的使用，关于它的科研成果和新应用模式也层出不穷。CUDA(ComputeUnifiedDeviceArchitecture)，是显卡厂商NVidia推出的运算平台。CUDA是一种由NVIDIA推出的通用并行计算架构，该架构使GPU能够解决复杂的计算问题。它包含了CUDA指令集架构（ISA）以及GPU内部的并行计算引擎。开发人员现在可以使用C语言来为CUDA架构编写程序，C语言是应用最广泛的一种高级编程语言。所编写出的程序于是就可以在支持CUDA的处理器上以超高性能运行。将来还会支持其它语言，包括FORTRAN以及C++。1.3并行数据挖掘并行数据挖掘技术不同于其它并行算法的地方在于它需要处理的数据的规模很大。人们知道，对于并行而言，交互之间的消耗（即内存的使用）是比执行时间（计算阶段）重要得多的因素。串行数据挖掘算法对于规模很小的数据也需要大量的运行时间，而且可用于分析的数据增长得很快，这样就需要寻找用于数据挖掘的并行算法，目前对并行数据挖掘算法已有了充分的研究。并行数据挖掘策略通常是有三种：1.朴素并行，也就是人们通常说的网络并行。网络并行，就是通过高速信息网络充分利用网上的计算机资源，实现大规模数据上的并行计算。在这种并行类型中用于计算的时间会减少但是每一个处理器都要扫描所有的数据，这样就阻碍了算法性能的提高。2.典型并行是当前并行数据挖掘策略的典型代表（这里称为典型并行）。在算法的每一步中，一个处理器只处理1/p的数据，而且在步骤的最后需要交换从数据中收集到的信息。3逻辑并行类型的技术是适用于逻辑性较强的并行。对于这种类型的并行数据挖掘策略，初始化阶段可能要重复进行是为了给该类型技术的结构减小数据规模。然而，该结构进一步发生在进一步抽取信息的过程中。许多归纳的逻辑方法（如的处理是ProgoL）就是这种并行类型。2．主要内容2.1传统的关联规则挖掘Apriori算法简介Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。下面通过流程图来表示整个过程。2.2Apriori算法的并行改进Apriori通过对数据库的多趟扫描来发现所有的频繁项集，而对存储海量数据的数据库的多趟扫描将耗费大量时间和内存空间，这将成为Apriori算法的瓶颈。因此，有关并行数据挖掘算法的研究不断升温。由于云计算环境具有分布特点，可支持算法的并行执行，从而提供挖掘效率。1.把数据库分成规模相当的M个数据子集，把数据子集发送到M个站点。2.每个站点扫描它的数据子集，产生一个局部候选K项集，每个候选项集的支持度计数为1。3.利用hash函数把M个站点的候选k项集总相同的项集和它的支持度计数发送到R个站点。4.站点把相同项集的计数累加起来，产生最后的实际支持度，与最小支持度计数比较，确定局部频繁k项集的集合。5.把R个站点的输出合并即产生全局频繁k项集的集合。改进的Apriori算法的优势是查找k频繁项集和k+1频繁项集的过程是完全独立的。他们之间没有联系，这是一个循环的过程。k值从1开始递增，知道找出所有的频繁项集。也可以设定k的值，知识查找k频繁项集，或者从1频繁项集到k频繁项集之间的所有频繁项集。改进的Apriori算法的MapReduce实现：1.MapReduce库将事物数据库进行水平划分，分成M个规模相当的数据子集。2.对M个数据子集进行格式化，产生key,value对，具体格式化为Tid,list，Tid表示事物数据库中的事物标识符，list为事物数据库中的事物对应的列表值。3.Map函数的任务是对输入的数据子集的每个记录Tid,list进行扫描，产生一个局部候选k项集的集合，每个候选k项集的支持度计数为1。Map函数生成并输出中间key,value对，这里定义为itemsets,1对，itemsets表示候选k项集。4.当事物数据库很大，划分后的每个数据子集中事物对应的列表很相近时，Map函数产生的中间key值得重复数据会占很大的比重。例如每个Map函数产生成千上万个这样的记录I,1。所有这些记录将通过网络被发送到指定的Reduce函数。这无疑耗费了宝贵的网络资源，增加了延迟，降低了I/O性能。所以在每台执行map任务的机器上增加一个可选的Combiner函数，Combiner函数首先在本地将Map函数输出进行一次合并输出itemsets,supsup表示itemsets在数据子集中的支持度计数，然后利用分区函数hash（key）modR将Combiner函数产生的中间键值对分成R个不同的分区，将每个分区分配到指定的Reduce函数。5.被分配了Reduce任务的工作站的读取Combiner函数提交的数据itemsets,sup，由于许多不同的候选k项集会映射到相同的Reduce函数，因此对键值itemsets进行排序使得具有相同候选k项集的数据聚合在一起，形成itemsets,list(sup)。工作站点遍历排序后的中间数据，将itemsets,list(sup)传递给Reduce函数，然后Reduce函数把相同候选k项集itemsets的支持度计数累加起来，就得到此候选k项集在整个事物数据库中的实际支持度计数，然后和最小支持度比较，确定局部频繁k项集的集合。6.把比较之后的R各Reduce函数的输出的项集合并就得到最终的频繁K项集的集合。7.k值从数值1开始递增，知道生成的k频繁项集为空，至此，已找出所有的频繁项集。Apriori算法用MapReduce实现的优势是：1.对事物数据库的扫描次数减少。2.查找频繁项集的过程可以并行执行，当查找频繁k项集的流程执行的中间结果都被传送到分配了Reduce任务的工作站点时，Master就可以调度分配Map任务的工作站点开始查找频繁K+1项集，加快并行处理速度，极大地提高执行效率。上述描述的算法可以通过Hadoop的MapReduce框架进行实现。这是在宏观上的MapReduce实现。但是如果能在每个节点上从微观上再做一层并行，就是通过GPGPU再增加该算法的并行性，那么效率将进一步得到提升。2.3Apriori算法的GPU并行实现该算法参考自论文《ParallelDataMiningonGraphicsProcessors》。由于Apriori算法的主要瓶颈出现在各阶段对各项支持度的计数，该算法不仅使用字典树来存储候选集和它们的支持度，而且还是用Bitmap技术来存储记录集来做计数。第一次和第二次支持度筛选直接通过计数来进行，当项数达到三项以上时，计数将通过一个递归过程来实现。该递归过程递归的遍历字典树，以便能够在节省I\O时间，节省重复查找的条件下进行计数。由于本文重在如何将两种层次结合的探讨，所以具体将不再叙述，可以查找相关论文。2.4Apriori算法的双重层次并行正如我们所见，Apriori算法无论是在网络的Mapreduce框架下，和GPU的并行框架上都是可行的，那么不妨把这两个层次结合起来，把效率进一步提升。如果这个用Hadoop实现，那么就不得不介绍Hadoop的Streaming编程技术。它是实现该结合的关键。HadoopStreaming是Hadoop提供的一个编程工具，它允许用户使用任何可执行文件或者脚本文件作为Mapper和Reducer，例如：采用shell脚本语言中的一些命令作为mapper和reducer（cat作为mapper，wc作为reducer）$HADOOP_HOME/b