云计算及若干数据挖掘算法的MapReduce化研究

摘要

云计算是2008年以来国际IT业热炒的概念,近两年来已开始在中国落地生根,是业界不可回避和逆转的一大趋势。我们可以把云计算看作是分布处理、并行处理以及网格计算的发展,其中并发、分布是云计算的关键,海量数据处理和海量计算是云计算的重头戏。但是云计算本身只是一种思维模式,要真正发挥它的魔力,除了硬件以外,更重要的是还得有软件的云计算平台支撑以及可以在平台上高效运行的并行化程序。
　　 海量数据处理和海量计算是数据挖掘领域的一个常见问题,许多传统数据挖掘算法往往只能适用小规模输入数据,当输入数据增大时,它们往往会因计算量的增大而速度减慢甚至无法运行,这无疑是许多传统挖掘算法的瓶颈。云计算则恰好擅长处理大规模数据和大规模计算,如果我们能够将传统数据挖掘算法并行化,并将之部署到云计算平台上运行,数据挖掘领域中的上述瓶颈问题就能迎刃而解。而能否有效借助云计算平台解决上述问题,关键在于能否合理地将相应的数据挖掘算法并行化。
　　 所以本论文首先主要从分布式文件系统和分布式编程模式两大方向分析了Google、Sector/Sphere和Hadoop三大云计算平台框架;然后从用户角度出发,综合考虑文本内容、人类遗忘性和话题流行度等因素,提出了一种基于网络日志的中文热点话题提取算法,并将其MapReduce化后部署到Hadoop云计算平台上运行,取得了良好的加速比效果,成功地提高了算法的运行速度和扩大了算法输入数据的规模;最后通过分析传统协同过滤算法、局部线性回归算法和朴素贝叶斯算法的详细流程、瓶颈问题和可并行化点,采取并行和串行相结合的方式,提出了将这几大算法MapReduce化的方法,不但证明了这些算法的可MapReduce化,而且在输入大批量数据的Hadoop集群实验中,取得了不错的加速比效果,比较成功地解决了这些算法计算量过大和计算时间过长的难题。本论文的研究为数据挖掘领域相关算法提供了可行的MapReduce化方案,实验结果证明了上述方案的切实有效性。

目录

文摘

英文文摘

第一章 引言

1.1 课题背景

1.2 研究目的和意义

1.3 国内外研究现状

1.4 论文研究内容及章节安排

1.5 本章小结

第二章 云计算平台介绍与浅析

2.1 Google云计算平台介绍与分析

2.1.1 Google文件系统GFS

2.1.2 Google的Bigtable

2.1.3 MapReduce编程模型

2.2 开源云计算平台Hadoop介绍与分析

2.2.1 Hadoop分布式文件系统概述

2.2.2 Hadoop分布式文件系统(HDFS)详解

2.2.3 MapReduce并行编程模型在Hadoop中的实现

2.2.4 Hadoop Map/Reduce的容错机制分析

2.3 Sector架构分析与介绍

2.3.1 Sector概述

2.3.2 Sector文件系统管理

2.4 Security server

2.4.1 Sphere计算云

2.4.2 调度机制

2.5 平台应用背景的对比

2.5.1 GFS、MapReduce和Bigtable应用场景

2.5.2 Hadoop应用场景

2.5.3 Sector/Sphere应用场景

2.6 Google云平台、Sector/Sphere及Hadoop平台的对比

2.7 本章小结

第三章 基于网络日志的中文热点话题提取算法研究

3.1 话题提取算法介绍与分析

3.2 基于网络日志的热点话题提取算法分析

3.3 基于网络日志的热点话题提取方法

3.3.1 网络日志分析

3.3.2 主题提取

3.3.3 热点话题提取

3.3.4 热点话题描述

3.4 单机实验和分析

3.4.1 单机实验结果及分析

3.4.2 中文热点提取算法展望

3.5 中文热点提取算法的MapReduce化

3.5.1 网页统计MapReduce化

3.5.2 网页爬取、网页解析及主题提取MapReduce化

3.5.3 候选话题提取MapReduce化

3.5.4 热点话题描述MapReduce化

3.6 Hadoop云计算集群上实验结果与分析

3.6.1 Hadoop实验集群的搭建

3.7 Hadoop集群上的实验结果与分析

3.7.1 Hadoop集群与单机实验结果与分析

3.7.2 Hadoop集群线性比测试与分析

3.8 本章小结

第四章 基于用户的协同过滤算法在Hadoop平台的实现

4.1 协同过滤算法简介

4.2 协同过滤系统详解

4.2.1 假设与目标

4.2.2 协同过滤算法具体过程

4.2.3 传统协同过滤算法面临的问题及应对策略

4.3 传统协同过滤算法的MapReduce化

4.3.1 数据划分

4.3.2 Map阶段

4.3.3 Reduce阶段

4.4 协同过滤算法实验过程及结果分析

4.4.1 实验总结与展望

4.5 本章小结

第五章 局部加权线性回归算法在Hadoop平台的实现

5.1 局部加权线性回归算法简介

5.2 局部加权线性回归算法详解

5.2.1 局部加权线性回归算法主要步骤

5.3 局部加权线性回归算法的MapReduce化

5.3.1 Datanode数据量的划分

5.3.2 Map阶段

5.3.3 Reduce阶段

5.4 实验过程及测试结果分析

5.5 本章小结

第六章 朴素贝叶斯分类算法在Hadoop平台的实现

6.1 朴素贝叶斯算法简介

6.2 朴素贝叶斯算法详解

6.2.1 贝叶斯定理

6.2.2 算法实现的疑难与解答

6.2.3 朴素贝叶斯算法实现过程

6.3 朴素贝叶斯算法的MapReduce化

6.3.1 数据预处理M印Reduce化

6.3.2 模型训练MapReduce化

6.3.3 分类MapReduce化

6.4 实验过程及测试结果分析

6.5 本章小结

第七章 总结和展望

致谢

参考文献

攻硕期间取得的研究成果