一种基于Hadoop的海量Web数据挖掘系统研究与实现

一种基于Hadoop的海量Web数据挖掘系统研究与实现ResearchandImplementationofaMassiveDataMiningSystemBasedonHadoop金松昌,杨树强SongchangJin,[e-mail]（国防科技大学计算机学院，湖南长沙410073）（SchoolofComputerScience,NationalUniversityofDefenseTechnology,Changsha410073,China）摘要:针对目前Web数据规模的快速增长，传统的基于单机的数据挖掘模式不能胜任当前Web海量数据存储与处理。随着“云计算”技术的兴起，将传统的数据挖掘方法与“云计算“平台融合以提高数据挖掘的效率成为一种研究方向。本文将传统的遗传算法与Hadoop的MapReduce进行融合，针对Hadoop的分布式文件存储系统HDFS中的海量Web数据进行挖掘。为进一步验证该平台的高效性，在该平台上利用融合后的算法挖掘Web日志中用户的偏爱访问路径。实验结果表明，在Hadoop中运用分布式算法处理大量的Web数据，可以明显提高Web数据挖掘的效率。Abstract：Withtherapidgrowthofwebdata,thecurrentdataminingsystembasedonsinglenodeisnotequaltothetaskofstoringandprocessingmassivewebdata.Withthedevelopmentofcloudcomputingtechnology,integratingthetraditionaldataminingmethodsandcloudcomputingtoimprovetheefficiencyofdataminingistobeoneoftheresearchdirection.WeintegratethetraditionalgeneticalgorithmandtheMapReduceparallelprocessingframeworkofHadooptominethemassivewebdatastoredintheHDFS(HadoopDistributedFileSystem).Tofurtherverifytheeffectivenessandefficiencyoftheplatform,weusetheimprovedalgorithmtomineusers’preferredaccesspathinweblogontheplatform.Experimentalresultsshowthat,usingdistributedalgorithmtoprocesslargenumberofweblogfilesinthecluster,cansignificantlyimprovetheefficiencyofWebdatamining.关键词：Hadoop；map/reduce；数据挖掘；遗传算法Keywords:Hadoop;map/reduce;datamining;GeneticAlgorithm中图分类号：TP393文献标识码：A1.引言目前，随着数据规模的迅速扩张，单一节点的计算能力已经不能胜任大规模数据的分析处理。近几年来，随着“云计算”技术的兴起，人们将海量数据存储与处理的目光转向了这个新兴的行业。“云计算”是一种基于互联网的计算，在其中共享的资源、软件和信息等以一种按需的方式提供给计算机和设备[1]。“云计算”技术借助网络中强大的计算资源，将消耗大量计算资源的复杂计算通过网络分散到多节点上进行计算，是当前一种行之有效的解决方案[2]。互联网作为全球最大的数据集合，基于Web的数据挖掘一直是国内外学者研究的热点。但是目前对数据挖掘的研究主要集中在改进挖掘系统的有效性方面，而忽视了对海量数据的处理速度。随着网络技术的迅猛发展，互联网中的数据正以指数级规模飞速增长，IDC(InternetDataCenter,互联网数据中心)估计2011年的互联网中的数据规模将达到1.8ZB（1ZB=1024EB,1EB=1024PB,1PB=1024TB）。这使得基于单一节点的挖掘平台不能完成目前海量Web数据的存储与分析处理任务。因此，可以需要借助云计算强大的存储和计算能力解决此类问题[3-4]。Hadoop“云计算”平台最大的优势是它实现了“计算靠近存储”思想，传统的“移动数据以靠近计算”模式在数据规模达到海量时的系统开销太大，而“移动计算以靠近存储”可以省去了海量数据的网络传输这一大开销，就能大幅消减处理时间。本文提出了一种基于Hadoop云计算平台的海量web数据挖掘系统的设计，通过将传统的遗传算法与Hadoop平台的Map/Reduce并行计算框架进行融合，验证该系统的可用性。2.Hadoop云计算平台Hadoop是Apache下提供的一个为便于编写和运行处理大规模数据的应用的软件平台。Hadoop的核心设计思想是：MapReduce和HDFS，MapReduce是Google提出的一个软件架构，用于大规模数据集（大于1TB）的并行运算。概念Map（映射）和Reduce（化简），和它们的主要思想，都是从函数式编程语言借来的，还有从矢量编程语言借来的特性；HDFS是HadoopDistributedFileSystem的缩写，即：Hadoop分布式文件系统，它为分布式计算存储提供底层支持[5]。HDFS是分布式计算的存储基石，Hadoop的分布式文件系统和其他分布式文件系统有很多类似的特质。分布式文件系统基本的几个特点：1）对于整个集群有单一的命名空间。2）数据一致性。适合一次写入多次读取的模型，客户端在文件没有被成功创建之前无法看到文件存在。3）文件会被分割成多个文件块，每个文件块被分配存储到数据节点上，而且根据配置会由复制文件块来保证数据的安全性。Map/Reduce是一个用于进行大数据量计算的编程模型，同时也是一种高效的任务调度模型，它将一个任务分成很多更细粒度的子任务，这些子任务能够在空闲的处理节点之间调度，使处理速度越快的节点处理越多的任务，从而避免处理速度慢的节点延长整个任务的完成时间。执行一个Map/Reduce操作需要8个步骤：作业提交，任务指派，任务数据读取，执行Map任务，本地写中间文件，远程读中间文件，执行Reduce任务，输出结果。图1MapReduce数据处理流程1）作业提交：用户提交基于MapReduce编程规范编写的作业；2）任务指派：作业控制节点（JobTracker）根据作业的情况，计算出需要的Map任务数M和Reduce任务数R，并根据数据分布情况和对应节点的负载，将Map任务分给存储该任务对应的数据且负载最轻的任务执行节点（TaskTracker）。同时根据作业结果的要求，分配相应TaskTracker执行Reduce任务；3）任务数据读取：被分配到Map子任务的TaskTracker节点读入已经分割好的数据作为输入，经过处理后生成key/value对；4）Map任务执行：TaskTracker调用从JobTracker获取到的用户编写的Map函数，并将中间结果缓存在内存中；5）本地写中间结果：内存中的中间结果达到一定阈值后，会写入到TaskTracker本地的磁盘中，这些中间数据通过分区函数分成R个分区，并将它们的本地磁盘的位置信息发送给JobTracker，然后JobTracker将位置信息发送给执行Reduce子任务的TaskTracker；6）远程读中间文件：执行Reduce的TaskTracker从JobTracker获取子任务之后，根据中间结果的位置信息通过socket拉取数据，并利用中间结果的key值进行排序，并将具有相同key的对进行合并；7）执行Reduce任务：执行Reduce任务的TaskTracker遍历所有排序后的中间数据，并传递给用户的Reduce函数，执行Reduce过程；8）输出结果：当所有的Map任务和Reduce任务都完成时，JobTracker控制将R个Reduce结果写到HDFS之上。基于Map/Reduce编程模型编写分布式并行程序非常简单，只需要实现Map和Reduce函数及如何将问题进行分割，区分操作是Map操作还是Reduce操作，而并行编程中的其他复杂问题，如分布式存储、工作调度、负载平衡、容错处理、网络通信，都由Map/Reduce框架负责处理。3.基于Hadoop的Web数据分析系统设计[6]基于Hadoop的Web数据分析系统框架如下所示：图2基于Hadoop的Web数据分析系统框架整个系统由多台普通节点和两台服务器组成，其中两台服务器分别充当HDFS文件系统中的名字服务器和MapReduce计算平台中的作业调度器（JobTracker），其余节点既充当HDFS文件系统中的数据节点（DataNode），又充当MapReduce计算平台中的任务执行器（TaskTracker）。正是这种设计，才使得“移动计算以靠近存储”，将大规模Web数据的处理变成“本地计算（localcomputing）”，这将大大提升海量数据处理的速度，达到高效率。4.基于MapReduce的遗传算法面向海量Web数据的数据挖掘方法或者算法必须是能进行并行处理的。在实际大型企业Web站点中，URL数常常达到几万甚至几十万，这将造成构造出的Web访问矩阵过大，传统基于单机处理海量数据的能力成为发展的一个瓶颈。为了解决此问题，对常用数据挖掘算法C4.5、SPRINT、关联规则、K-means等进行改进，提出了许多基于传统挖掘算法的并行算法。其中，基于数据划分的方法是普遍采用一种并行处理的方法：首先将数据集合划分为适当的子块，然后在各个子块上用传统的挖掘算法(如Aprior算法)进行处理，最后将各个子块上的结果进行合并。通过上文的表述，MapReduce已经实现了对数据的划分，但前提是数据上下文是松耦合的。遗传算法是一种求解问题的高度并行的全局随机化搜索算法，在求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛到最优解或满意解，具有较好的全局最优解求解能力。同时，由于遗传算法只需在初始群体的基础上进行遗传进化操作，不需要对数据库进行多次扫描，大大减少了数据的传输量，因此将遗传算法用于基于Hadoop集群框架的用户浏览偏爱路径挖掘，在提高算法执行效率的同时还能减少数据的传输量[7-8]。融合了基于MapReduce的数据分割和遗传算法的新算法结合了数据分割技术的分布式处理和遗传算法的全局搜索最优解的优点。新算法的表述如下：步骤1数据分割处理。针对Web数据的特点，对Web数据进行分割，比如对Web日志文件按用户和访问日期进行分割，并传输到不同的子节点上，同时获取用户定义的支持度S。步骤2初始化群体。各子节点在Hadoop平台下利用Map和Reduce操作将数据集转化为满足用户定义支持度的偏爱子路径的1-项集形式，作为遗传算法的初始种群。步骤3适应度值计算。通过一条访问路径的频度衡量其是否是用户偏爱的访问路径，因此，适应度函数定义如下：{其中，S’为路径的访问频度。保留Fitness大于1的个体进入下一代。步骤4若当前进化代中所有个体的适应度值Fitness等于1，表明群体经过遗传进化后得不到改善，转至步骤7，否则，继续。步骤5对该代进行选择、交叉操作。在遗传进化过程中，首先采取精英保留策略，保留遗传过程中的精英个体，让它们不参与交叉操作直接进入下一代。本文将第i个个体的选择概率定义为：其中，为第i个个体的路径访问频度；为群体中所有个体路径访问频度的平均值。在保留的个体中，根据选择概率选取个体进行交叉操作，当代数为50的倍数时，进行迁移操作，相邻2个子群体间联姻，并将联姻后代中的最佳个体复制到相关的源种群中。步骤6将整个子代群体替代父代群体，形成新一代，然后转至步骤2。步骤7当经过一定遗传代数后