基于云计算的Web结构挖掘算法研究

论文摘要

Web结构挖掘是通过研究网页之间的链接结构来发现网络的组织结构和链接关系中隐藏的知识。随着互联网的发展,对网络中的海量数据分析与挖掘都面临着在计算能力和存储空间方面的瓶颈。云计算作为目前国内外研究的热点,是网格计算、并行计算、分布式计算的发展,利用云计算技术,人们可以方便的通过网络获取强大的计算能力、存储能力以及基础设施。云计算思想可以有效解决分析与处理海量数据时面临的问题,并提供了可靠性高、可扩展的的数据处理存储中心,在降低了终端设备要求的同时提高了处理数据的能力。本文在研究Web结构挖掘经典算法Pagerank和云计算关键技术Mapreduce的基础上,做了如下工作：1.在云计算环境下对Pagerank算法进行研究,将Pagerank算法与Mapreduce编程模型结合。对不同规模的数据集测试基于Mapreduce的Pagerank算法的性能。2.针对并行Pagerank算法运行大数据集时面临的：每次迭代都需要访问HDFS导致I/O消耗增加；每次Mapreduce迭代在混合阶段和排序阶段因为要处理大量key而导致时间消耗多的问题提出了两个改进算法。一个是利用矩阵分块的思想将邻接矩阵分块处理,以减少每次MapReduce迭代在混合阶段和排序阶段的时间消耗。另一个是在通过增加每次迭代Pagerank计算跨度基础上,成倍减少迭代次数,即减少与迭代次数相关的网络通信消耗和访问HDFS的I/O操作消耗。3.利用Hadoop搭建云环境,在实验环境下分析不同的BlockSize参数对于计算性能的影响。最后在云环境下面向不同的Web数据集,对一般pagerank并行算法和两种改进算法的性能进行测试和比较,结果表明改进后算法分别在结果集的空间占用方面和总迭代时间方面具有一定的优越性。

论文目录

• 致谢
• 摘要
• ABSTRACT
• 1 引言
• 1.1 研究背景和意义
• 1.2 国内外研究现状
• 1.3 论文的组织结构
• 2 Web挖掘技术概述
• 2.1 Web挖掘的分类
• 2.1.1 Web内容挖掘
• 2.1.2 Web使用记录挖掘
• 2.1.3 Web结构挖掘
• 2.2 Web结构挖掘
• 2.2.1 Web图概念
• 2.2.2 链接关系表示方法
• 2.3 PageRank算法简介
• 2.3.1 算法思想
• 2.3.2 算法分析
• 2.3.3 收敛性评估
• 2.3.4 Pagerank算法的不足和改进
• 3 云计算与MapReduce编程模型
• 3.1 计算介绍
• 3.1.1 技术背景
• 3.1.2 计算概念
• 3.1.3 计算的实现机制
• 3.2 MapReduce技术介绍
• 3.2.1 概念
• 3.2.2 编程原理
• 3.2.3 实现
• 3.2.4 适用条件
• 3.3 Hadoop分布式开源框架
• 3.3.1 概述
• 3.3.2 Hadoop分布式文件系统HDFS
• 3.4 Hadoop下Mapreduce的执行原理
• 3.4.1 概述
• 3.4.2 输入与输出
• 3.4.3 Hadoop-MapReduce的工作流程
• 3.4.4 Hadoop执行中的性能瓶颈
• 3.4.5 Hadoop-MapReduce的任务调度
• 4 基于Mapreduce的pagerank算法研究
• 4.1 算法的来源
• 4.2 基于Mapreduce的Pagerank算法
• 4.2.1 算法数据准备
• 4.2.2 算法实现
• 4.2.3 算法存在的问题和改进
• 4.3 利用矩阵分块思想的并行Pagerank算法
• 4.3.1 矩阵分块原理
• 4.3.2 Web数据集预处理和划分数据块
• 4.3.3 分块算法执行
• 4.4 低迭代并行pagerank改进算法
• 4.4.1 算法分析
• 4.4.2 算法实现过程
• 4.4.3 算法的比较和扩展
• 5 实验分析
• 5.1 实验数据集
• 5.2 实验平台搭建
• 5.2.1 硬件实验平台
• 5.2.2 Hadoop在集群上配置
• 5.2.3 Hadoop关键配置项
• 5.3 Hadoop下设计Mapreduce的算法
• 5.4 在hadoop集群上运行pagerank算法
• 5.5 实验结果分析
• 5.5.1 MapReduce并行规模对作业执行时间的影响
• 5.5.2 分析Mapreduce下各pagerank算法时空消耗
• 6 结论与展望
• 6.1 本文工作总结
• 6.2 展望
• 参考文献
• 作者简历
• 学位论文数据集