基于云计算的Web数据挖掘(免积分)

第38卷第1OA期2011年l0月计算机科学ComputerScienceVo1．38No．10A0ct2011基于云计算的Web数据挖掘程苗(中国科学技术大学管理学院合肥230026)摘要因特网是一个巨大的、分布广泛的信息服务中心，其上产生的海量数据通常是地理上分布、异构、动态的，复杂性也越来越高，若用已有的集中式数据挖掘方法则不能满足应用的要求。为了解决这些问题，提出了一种基于云计算的web数据挖掘方法：将海量数据和挖掘任务分解到多台服务器上并行处理。采用Hadoop开源平台，建立一个基于Apriori算法的并行关联规则挖掘算法来验证了该系统的高效性。还提出“计算向存储迁移”的设计思想，将计算在数据存储节点就地执行，从而避免了大量数据在网络上的传递，不会占用大量带宽。关键词云计算，数据挖掘，Map／Reduce，关联规则WebDataMiningBasedonCloud-computingCHENGMiao(SchoolofManagement，UniversityofScienceandTechnologyofChina，Hefei230026，China)AbstractInternetisahugeandwidelydistributedinformationservicecenter，thevastamountsofdatageneratedontheInternetareusuallygeographicallydistributed，heterogeneous，dynamicandbecomemorecomplex，itcarlnotmeettherequirementsifweusetheexistingcentralizeddataminingmethods．Tosolvetheseproblems，proposedacloudcompu—ting-basedWebdataningmethod，themassivedataandminingtaskswillbedecomposedonmultiplecomputersparallelyprocessed．WeuseopenplatformHadooptOestablishaparallelassociationrulesminingalgorithmbasedonApriori，andittestsandveriftestheefficiencyofsystem．Thispaperproposedadesignthinkingthat“migratethecalcu—lationtothestore”，thecalculationwillbeimplementedonthelocalstoragenodes，thusitcanavoidthelargeamountofdatatransmissiononthenetwork，andwi11nottakealotofbandwidtb．KeywordsCloud-computing，Datamining，Map／Reduce，Associationrules1概述随着Internet技术的迅猛发展，互联网上的数据呈指数形式飞速增长，如何在这个全球最大的数据集合中发现有用信息成为数据挖掘研究的热点。Web数据挖掘是建立在对web上海量数据分析的基础上，利用数据挖掘算法有效地收集、选择和存储所感兴趣的信息以及在日益增多的信息中发现新的概念和它们之间的关系，实现信息处理的自动化。这对企业获取有用可靠的外界信息，商业运作过程中收集、分析数据从而做出正确决策有着十分重要的意义。Web数据挖掘主要是以网络日志为研究对象，利用数据挖掘技术发现用户行为的潜在规律。目前，基于网络日志的用户行为模式研究已在网络安全、电子商务、远程教育等多个领域得到了广泛的应用，是当前的热点研究之一。网络日志文件中的数据主要包括URL请求、页面间链接的拓扑结构、注册用户特征等。采用关联规则分析，可获取用户页面访问行为间的关系；采用聚类分析，可将特征相似的用户或页面归并分组；采用分类分析，可对用户行为特征进行归类识别；采用频繁序列模式分析，可获取用户访问习惯。这些常用数据挖掘方法获取的用户行为模式，解决了页面自动导航、页面重要性评价以及改进网站设计、提高网站运营效益等问题。由于因特网本身所具有的分布广泛、用户众多等特性，也使得其上所产生的数据是海量的、地理上分布的、异构的、动态的，这给现有的数据挖掘系统带来了难题：处理这些数据的复杂度很高，系统的计算能力很难达到要求。目前，Web日志挖掘还有待研究的问题主要有两个：一是如何整合与处理分布式的Web日志；二是如何开发出高性能、可伸缩的分布并行的挖掘算法，保证挖掘的效率。为了解决高性能计算问题，国内外学者提出了基于集群、基于Agem等的各种分布式并行数据挖掘平台，提高了数据挖掘系统的处理能力，但实现却相对复杂且只能针对特殊应用。之后，MCannatard。]等人基于GlobusToolkit设计了一种分布式并行知识发现平台，该平台利用GlobusToolkit所提供的网格计算能力，解决了传统数据挖掘计算能力不足的问题。近几年的研究[8]集中在基于GlobusToolkit平台并行数据挖掘算法的实现与改进方面。但网格计算缺少商业化实现，且GlobusTolkit是基于中间件技术，需要通过编程或安装设置来搭建底层架构，增加了系统实现的难度[5]。本文受博士点基金项目(2OO8O358O024)，创新研究群体科学基金(70821001)资助。程苗(1986一)，女，硕士生，主要研究方向为云计算、数据挖掘。·146·Web数据挖掘处理的是海量数据，而且以指数级增长，同时所设计到的挖掘算法相当复杂，有的算法需要多次扫描数据库，当数据量增加时会增加扫描的代价；有的算法需要存储各序列的相关信息，当信息量很大时，会带来存储上的问题。因此，将云计算融入Web数据挖掘中将具有非常重要的现实意义，可以解决Internet上广域分布的海量数据挖掘问题。2Map／Reduce编程模式Map／Reduce是一个用以进行大数据量计算的编程模型，同时也是一种高效的任务调度模型，它将一个任务分成很多更细粒度的子任务，这些子任务能够在空闲的处理节点之间调度，使得处理速度越快的节点处理越多的任务，从而避免处理速度慢的节点延长整个任务的完成时间。它将大型分布式计算表达为一个对数据键／值对集合进行串行化分布式操作，包括Map(映射)和Reduce(化简)两个阶段。Map是一个分的过程，用于将输人数据结合拆分为大量的数据片段，并将每一个数据片段分配给一个计算机处理，达到分布式运算的效果，而Reduce则把分开的数据合到了一起，最后将汇总结果输出。Map／Reduce的执行由两种不同类型的节点负责，Master和Worker。Worker负责数据处理，Master负责任务调度及不同节点之间的数据共享。执行一个Map／Reduce操作需要5个步骤：输入文件、将文件分割并分配给多个WO1~-ker并行执行、本地写中间文件、合并中间文件、输出最终结果。具体流程如下[】：①Map／Reduce库将输入文件分成16到64MB的M份，并在集群的不同机器上执行程序的备份。②Master节点的程序负责找出空闲的worker节点并为它们分配子任务(M个Map子任务和R个Reduce子任务)。③被分配到Map子任务的Worker节点读入已经分割好的文件作为输入，经过处理后生成key／value对，并调用用户编写的Map函数，Map函数的中间结果缓存在内存种并周期性地写入本地磁盘。④这些中间数据通过分区函数分成R个区，并且将它们在本地磁盘的位置信息发送给Master，然后再由Master将位置信息发送给执行Reduce子任务的节点。⑤执行Reduce子任务的节点从Master获取子任务后，根据位置信息调用map工作节点所在的本地磁盘上的中间数据，并利用中间数据的key值进行排序，将具有相同键的对合并。⑥执行Reduce子任务的节点遍历所有排序后的中间数据，并传递给用户定义的reduce函数。Reduce函数的结果将被输出到一个最终的输出文件。⑦当所有的map子任务和reduce子任务完成时，Master节点将R份Reduce结果返回给用户程序，用户程序将这些数据合并得到最终结果。3基于云计算的Web数据挖掘系统设计与实现3．1概述基于云计算的Web数据挖掘系统是在Internet上广域分布的海量数据和计算资源的环境中发现数据模式和获取新的知识和规律。基于云计算的web数据挖掘同传统web数据挖掘的基本过程一致，分为数据预处理、数据挖掘、模式评价3个阶段，只是在数据的处理方式上有所不同，其区别有：借助Hadoop的MapReduce思想，1)在收集数据时，一改传统将所有数据、文件统一存储在数据仓库中的做法，将Web上广域分布的海量数据经过过滤、清洗、转换和合并，并转化为半结构化的XML文件后，保存到分布式文件系统中。同一文件都会复制副本并将其保存在不同的存储节点上，这样不仅可以解决传统Web数据挖掘中普遍存在的存储容量扩展和I／o操作问题，还可以有效地避免因机器故障而带来的数据丢失问题。2)在执行某一具体挖掘任务时，由任务主节点(Master)负责整个的控制工作，创建子节点的从属任务，然后交由web上空闲的计算资源(ServieeNode)去处理，Service-Node将状态和完成的信息向Master汇报。最后再由Master负责将所有结果进行合并。3．2计算与存储整合在Internet中，网络带宽是相对稀缺的资源。Map／Re—duce的Map在各节点进行操作，处理过程中一般没有数据的传输工作，只是在Reduce过程中需要向Master传送计算结果，对于Web数据挖掘这种数据密集型的计算任务，这种方法节省了大量的数据传输时间。由于网络传输速度远小于CPU计算速度，因此有人提出了以计算来换通信的编程策略。可以通过让输入数据保存在构成集群机器的本地磁盘上的方式来减少网络带宽的开销。我们可以将数据文件分成64M大小的块，在不同的机器上保存块的拷贝。由Master保存这些块的位置信息，并在保存相应输人数据块的设备上执行Map任务。这种方法使得大部分输入数据都是在本地机器读取的，并不占用网络带宽。3．3数据文件的备份在设计云计算系统时，不但要考虑计算与存储的整合，还必须在节点失效时考虑计算和存储的迁移。一般的云计算系统(Hadoop)实现存储的迁移，但对计算和存储同时迁移则做得不好，实现计算迁移的基础是数据块必须采用副本策略，这样计算迁移时才能重新找到所要处理的数据。一般来看信息通过网络进行迁移是比较慢的，而计算的迁移可以由系统很快完成，在有副本策略的系统中，只需要找到副本所在地，将计算迁移过去就完成了存储和计算的迁移工作，所以效率非常高。3．4系统架构在本文设计的基于云计算的web数据挖掘系统(见图1)中，节点分为3类。一类是主控节点(Master)，在云中，Mas—ter只有一个，负责调度与协调计算节点之间的工作进程；一类节点是算法存储节点，负责存储数据挖掘所需的算法；还有一类节点是服务节点(ServiceNode)，负责存储分好块的XML文件以及执行由Master分配的任务，并把计算结果返回给Master。相应地，基于云计算的Web数据挖掘系统分为3层：数据存储层、挖掘算法层和业务处理层。·]47·I客户端一一一一一一一一一一一—燕客佳壹LL传输元数据，包括调用的算法以压=i匿愿螳毯量所在位置lMasterl一一一申请需数所据_J一l—所逗在避位熬握置一一一一一一一一一=：1算法库llNameNode将_______调用的算法传输至原始数据所在的子节点子节点的元数据如子节点IP地址是否空闱等ServicsNodellServiceNodellServiceNode结是返回到主控节点进行汇总图1基于云计算的Web数据挖掘系统架构3．4．1数据存储层该层应具