基于mapreduce框架的频繁项集挖掘算法研究

《基于mapreduce框架的频繁项集挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于MapReduce框架的频繁项集挖掘算法研究-->第1章绪论1.1课题研究的背景和意义随着计算机的普及和互联网的发展，电子商务逐渐兴起，网络上每天都产生TB以上等级的巨量数据[1]，如何从海量的数据中找到有价值的信息是当前的一个热点，对人类社会具有非常重要的社会价值和降级利益，数据挖掘就是实现这一功能的技术。在企业应用方面[2]，可经由数据挖掘[3]中的关联规则挖掘算法[4]来分析用户的浏览行为、兴趣取向和使用频率等，提高网站或商品的使用客户率，进而提高公司得营利。关联规则挖掘作为数据挖掘中最成

2、熟、最活跃的研究内容之一，其目的是找出数据库中不同项之间的相关关系、核心问题是频繁项集的获取[4]。在频繁项集挖掘中具代表性的经典算法─Apriori算法[5,6]。Apriori算法采取循序渐进的方式组合出侯选项集，其思想是利用已知的高频数据项集推导其他高频数据项集。但是单一的主机已经无法负担大量的运算，从而延伸出的丛集式运算、格网运算、云端运算[7]等，以往提出的分布式数据挖掘算法已经无法解决现有海量数据处理问题[8]。云计算是分布式计算、并行运算和网格计算的进一步演进。将传统数据挖掘算法并行化

3、改进后移植到Hadoop云计算平台被相继提出[9]，由于Hadoop具有良好的可靠性、扩展性、通用性、价格低廉、虚拟化、按需服务、巨大的存储和计算能力、动态交互等特色，促使学者甚至各大企业大量投入其研究与应用[10,11]。现在已有很多运用在Hadoop的MapReduce计算框架的Apriori算法被提出[12,13]。其中one-phase算法一次产生所有候选项集再进行筛选的特性有着内存严重占用的问题[14]；而k-phase算法，运用多次MapReduce运算出每一阶的候选项集再进行筛选，虽有

4、效节省内存，但多次的MapReduce运算会严重增加其基本消耗的时间(一次22秒~25秒左右)，而且由于Hadoop环境下多台计算机之间通讯方式采用传统的通讯协议，如，TCP/IP，HTTP，造成通讯延迟问题，严重影响了以上两种算法的运算效率[15]。FAMR算法，其利用了AprioriTID[17]的优点对数据先做前置的处理，目的在于筛选出一阶低频项集，减少候选项集的产生和内存使用量，使速度有显着的提升，但是其算法在Map端仍存在大量低频项集的产生问题[16]。……….1.2数据挖掘的介绍及研究现

5、状数据挖掘是从大量的数据中抽取未知的、可信的、新颖的、有效的及有潜在应用价值的信息或模式的高级处理过程。也就是说可以从一个大型数据库里头所储存的大量数据当中萃取出有趣、有用的知识。近几年云端运算的议题非常的热门，运用Hadoop来处理巨量数据的算法也相继被提出，由于Hadoop具有良好的扩充性、容错性、经济性等特色，促使学者甚至各大企业大量投入其研究与应用。而数据挖掘被作为数据库中知识发现的一个基本步骤，因为云端运算技术的成熟，运用Hadoop来处理巨量数据的算法也相继被提出。数据挖掘是数据库知识发

6、现(Kno,HDFS)和MapReduce为核心[10]。HDFS的高容错性、高伸缩性等优点允许用户将Hadoop部署在低廉的硬件上，形成分布式系统，MapReduce分布式编程模型允许用户在不了解分布式系统底层细节的情况下开发并行应用程序。Hadoop是基于Java程序语言所开发的，在架设方面不限于特定的操作系统，使得Hadoop可以轻易部署在低阶的计算机丛集中，对于中、小型企业或者学术研究单位，可节省实际运用及学习研究的门槛，Hadoop是一个能够让用户轻松架构和使用的分布式计算平台。用户可以轻

7、松地在Hadoop上开发和运行处理海量数据的应用程序，它在Hadoop上开发和处理巨量数据的应用程序更为容易，所以在众多产业和学术研究单位领域中被高度地重视，最主要有以下几个特色[35]，如表2-1所示。在2008年1月，Hadoop已经成为Apache顶级的项目，证明了它的成功，多样，活跃性。到目前为止，除Yahoo!之外，被许多公司像Facebook和《纽约时报》等知名企业使用，其最大贡献者Yahoo!在同年的2月份建构了当时运算规模顶级的Hadoop应用，它们在2000个节点上面执行了超过1万

8、个Hadoop虚拟机器来处理超过5PB的网页内容，这些数据经过压缩后超过300TB，有着非常突出的成绩，相信在不久未来，Hadoop将会被广泛应用到更多领域中，为大量的数据提供更加快速且高质的服务。………2.2Hadoop分布式文件系统Hadoop分布式文件系统(HadoopDistributedFilesystem，HDFS)以流式数据访问模式来存储超大文件，它具有高容错性的特点[36]，可以运行于商用硬件集群上。整体来说，HDFS它主要有以下特点。1．处理超大文件