1、基于 HADOOP 的数据挖掘算法并行化研究与实现 摘要 随着 互联网技术的发展和 云计算技术的流行 ， 提供网络服务的互联网公司每 天生成和需要处理的数据呈爆炸式增长 ，海量 数据已经逐渐将我们包围。数据的不断增长给人们带来 了 巨大价值 ， 同时 也给人们带来了巨大的挑战。 如何分析和挖掘这些数据背后隐藏的有价值的信息， 已经成为很多大型企业所关注的焦点。 大规模文档 信息资源的自动化处理 是海量数据处理中较受关注的一个领域，企业通过对 文本数据进行分类 ，不仅可以 对数字资源进行有效的整理，而且 保证数字资源被全面检索和充分利用 ， 满足用户对 信息咨询服务的需求。 但同时 互联网企业产
2、生的文本数据 又具有海量，复杂 等特点，面对现在飞速增长的 文本数据 ，传统采用单机来处理的方式已经逐渐满足不了人们的需求，如何高效率的 对 海量 文本进行分类整理并且 挖掘出有价值的信息，这是本文的一个关注的问题。 Hadoop 是目前最流行的用于处理海量数据的开源分布式框架。Hadoop 主要的组件包括 HDFS 和 MapReduce。 HDFS 是 Hadoop 集群提供的分布式文件系统，而 MapReduce 是一种分布式框架， 通过这两者的结合，可以对海量的 文本 数据进行有效的处理 。本文 研究了Hadoop 进行分布式处理的步骤和原理 ， 在其基础上设计并实现了基于 Hadoo
3、p 的分布式文本分类系统， 通过与单机系统处理结果的对比，论证了 Hadoop 系统 在进行文本分类 时的效率要高于单机 ，并且取得良好的分类效果。 目录 基于 HADOOP 的数据挖掘算法并行化研究与实现 . 1 第一章 绪论 . 3 1.1 课题研究背景 . 3 1.2 研究现状 . 4 1.2.1 Hadoop 研究现状 . 4 1.2.2 文本分类研究现状 . 5 1.3 本文的主要工作 . 5 1.4 论文的组织结构 . 5 第二章 Hadoop 分布式框 架概述 . 6 2.1 什么是 Hadoop. 6 2.2 HDFS 分布式文件系统 . 7 2.2.1 HDFS 设计思想 .
4、 7 2.2.2 名字节点和数据节点 . 7 2.2.3 块的概念 . 9 2.2.4 文件系统命名空间 . 9 第三章 文本分类的原理 . 16 3.1 向量空间模型 . 16 3.2 中文分词 . 17 3.3 特征选择 . 18 3.3.1 卡方检验 . 19 3.3.2 信息增益 . 19 3.4 特征权重计算 . 20 3.4.1 什么是特征权重 . 20 3.4.2 TF/IDF . 20 3.4.2 特征权重与特征选择的区别 . 21 3.5 文本分类算法 . 21 3.5.1 朴素贝叶斯方法 . 21 3.5.2 支持向量机 (SVM) . 22 3.6 文本分类的评价体系 .
5、 28 3.6.1 准确率 (Precision)与召回率 (Recall) . 28 3.6.2 F 值 (F-measure). 28 第四章 基于 Hadoop 平台的文本分类系统的设计 . 29 4.1 环境搭建与实验设计 . 29 4.1.1 系统环境配置 . 29 4.1.2 Hadoop 集群配置 . 32 4.2 文本表示 过程的并行化 . 35 4.2.1 预处理和中文分词并行化 . 35 4.2.2 特征选择并行化 . 36 4.2.3 TF/IDF 计算并行化 . 37 4.3 基于朴素贝叶斯文本分类的并行化 . 37 4.4 基于 SVM 文本分类的 并行化 . 40
6、4.4.1 SVM 并行化 . 40 4.4.3 MapReduce 实现 . 43 4.4.4 基于 Hadoop 的 SVM 实现 . 44 第一章 绪论 1.1 课题研究背景 我们处在一个数据爆炸的时代，随着互联网技术的发展 和 云计算技术的流行， 互联网 正以海量的数据资源和咨询信息丰富着人们的日常生活 ， 网络数据规模正以几何式增长 ！仅仅以互联网技术的发展为例，各种 微博 ， 论坛 ，社交网站等网站如雨后春笋般层出不穷。据统计，目前全球的 Web 站点已经达到数亿个，而且还在 飞速 增长中。 网络上各种电子书籍、门户新闻、信息咨询等服务内容在满足人们网络服务需求的同时，也给对海量的
7、数据处理带来了巨大的挑战。 在海量数据处理问题中，文档自动分类成为处理和组织大量文档数据的关注焦点。在数字图书馆中，对数字文本进行准确高效的分类是保证数字资源被全面检索和充分利用的基础。在门户网站 中，对实时新闻的准确快速分类是满足人们获得良好的咨询服务的关键。文本分类是文本处理领域的重要研究内容之一，其任务就是在预先给定的分类模型下，系统在学习各类的训练文档的基础上，根据文本的内容让计算机自动判断、预测未知 类文档的类别。文本分类技术已经应用于信息检索、信息抽取、数字化图书馆、新闻门户 、网上信息快速定位等多个领域。 文本自动分类是通过分析被分类文档的特征，并与其他各类文档所具有的共同特征进
8、行比较，将被分类文档归于特征最接近的一类并赋予相应类别。 常用的文本分类方法有 K 近邻 ( KNN) 方法、朴素 贝叶斯 (Naive Bayes) 方法、神经网络方法 (Neural Net) 、支持向量机 ( SVM) 方法和决策树方法 (Decision Tree) 等。其中朴素贝叶斯分类方法是一种简单有效的概率分类方法 , 在某些领域表现出很好的性能 。 就目前网络上的海量文本数据而言，传统的文本分类方法具有以下两点局限：一是分类效率低，互联网上动辄几十 TB 的文本数据如果使用传统单机的分类方式需要大量的时间；二是分类准确率不高，没有充分考虑特征权重对分类效果的影响。本文将主要针对
9、基于 Hadoop 的文本分类并行化方法 进行研究，着力提高海量文本数据下的文本分类效率和准确率。 1.2 研究现状 1.2.1 Hadoop 研究现状 Hadoop 是 Apache 基金会的一个开源项目 由 Doug Cutting Apache Lucene的创始人所带领的团队幵发 实现了 Google 的 GFS 和 MapReduce 思想。目前Hadoop 的最新版本是 2012 年 12 月 1 日发布的 Hadoopl.1.1 并还在不断完善发展之中。其为开发者提供了一个分布式系统的基础架构 用户可以在不了解分布式系统的底层细节的情况下来开发分布式应用 充分利用集群 的强大功能
10、 实现高速运算和存储。 由于 Hadoop 优势突出 不论在国内还是国外 基于 Hadoop 的应用已经遍地开花 尤其是在互联网领域。 2008 年 2 月 雅虎宣布搭建出当时世界上最大的基于 Hadoop 的集群系统 Yahoo! Search Webmap 它们在 2000 个节点上执行了超过 1 万个 Hadoop 虚拟机器来处理超过 5PB 的网页内容 分析大约 1 兆个网络连接之间的网页索引资料。著名 SNS 网站 Facebook 用 Hadoop 构建了整个网站的数据仓库 存储日志数据 支持其上的数据分析和机器学习。近几年 国内应用和研究 Hadoop 的企业也越来越多 包括淘宝
11、、百度、中国移动等。百度用 Hadoop处理每周 200TB 的数据 进行搜索日志分析和网页数据挖掘工作同时赞助了 HyperTable 的幵发 ;淘宝的 Hadoop 系统用于存储并处理电子商务的交易相关数据。 为了满足互联网海量数据的处理和挖掘需求，将机器学习应用于大型数据库的数据挖掘和知识发现技术也得到了长足的发展。目前，基于云计算的数据挖掘正处于研究阶段，也会是最近几年的研究热点。 Mahout 是 Apache Software Foundation（ ASF） 旗下的一个开源项目，提供一些可扩展的机器学习领域经典算法的实现，旨在帮助开发人员更加方便快捷地创建智能应用程序。 Apac
12、he Mahout 项目已经发展到了它的第三个年头，目前已经有了三个公共发行版本。Mahout 包含许多实现，包括集群、分类、推荐过滤、频繁子项挖掘。此外，通过使用 Apache Hadoop 库， Mahout 可以有效地扩展到云中。 1.2.2 文本分类研究现状 国外主要的研究单位如 CMU、斯坦福。国内主要的研究单位有东北大学、上海复旦大学、哈尔滨工业大学、中科院计算所、 TRS 等，主要都是将 国外的方法引进来应用到中文信息处理技术上。 到目前为止，文本自动分类在国外大致经历了三个发展阶段：第一阶段（ 1958-1964）主要进行自动分类的可行性研究。第二阶段（ 1965-1974）进
13、行自动分类的试验研究。第三阶段（ 1975-至今）进行实用化阶段，并在邮件分类、电子会议、信息过滤等方面取得较为广泛的应用，其中较为成功的系统有麻省理工学院（ MIT）为白宫开发的邮件分类系统，卡内基集团为路透社开发的 Construe系统等。 我国文本分类的研究工作始于 20 世纪 80 年代，大体经历了可行性探讨、辅助分类 系统、自动分类系统三个阶段。总体来书，中文文本分类还处于在试验研究阶段，正确分类率约为 60%90%，已经逐渐向商业话的软件应用靠拢，并已经尝试开发了一批自动分类系统。例如，清华大学吴军研制的自动分类系统、山西大学刘正瑛等人开发的金融自动分类系统、上海交大的西风文本自动
14、分类系统。如何找到合理的应用并且在实践中逐步改善算法，提高性能成为文本分类算法的当务之急。 1.3 本文的主要工作 1.4 论文的组织结构 论文的结构安排如下： 第一章介绍了本文的研究背景，通过对现在海量数据的 处理和海量文本的分类问题 ，引入 了 Hadoop，然后介绍了 Hadoop 和文本分类技术的国内外研究现状。 第二章主要介绍 Hadoop 及相关的技术，简要介绍什么是 Hadoop 和 HDFS分布式文件系统 ，并介绍了 MapReduce 框架原理以及其作业执行流程。 第三章 详细介绍了文本分类模型训练的主要步骤 文本表示、中文分词、特征选择、特征权重计算、文本分类算法，以及每个
15、部分所用到的算法和原理 。 第四章利用 Hadoop 平台 设计了一个 分布式的文本分类系统 ，介绍了 Hadoop集群搭建的主要步骤以及 如何利用 MapReduce 框架实现文本分类系统各个部分的 并行化工作。 第五章 运行实验并分析实验结果 。通过实验证明在处理海量 文本数据 的时候引入 Hadoop 集群上在效率上要优于单机服务器的处理方式， 即文本分类结果的不足和需要哪些改进 。 第六章总结本次论文所完成的工作，介绍一下自己的心得及对 Hadoop 技术处理海量文本数据方面 未来的展望。 第二章 Hadoop 分布式框架概述 2.1 什么是 Hadoop 简单的说， Hadoop 是
16、 Apache 开源软件基金会开发的运行于大规模普通服务器上的用于海量数据存储、计算、分析的分布式存储和分布式运算框架。 3主要的特点包 括： 1. 成本低廉： Hadoop 可以运行在一般商用机器构成的大型集群上，机器的配置不需要很高。目前多采用 X86 Linux 服务器。 2. 可扩展性： Hadoop 通过扩展集群的节点，可以近乎线性的增加集群的处理能力，以处理更多的数据 ,存储的数据可以达到 PB 级别。 3. 高可用性：集群机器数量越多，出现硬件的故障的概率就越高。 Hadoop 可以轻松面对硬件故障带来的数据丢失及备份问题。 正是由于 Hadoop 具有的这些特点，使得它很快成为
17、了学术界包括工业界的宠儿。硬件方面的成本低廉，即使是在校的大学生也可以轻松部 署自己的 Hadoop集群来完成自己的学术实验，同时可扩展性以及高可用性可以很好的承担公司企业严格的生产任务。 下图是 Hadoop 的体系结构： Hadoop 的核心服务组件包括两部分：分布式文件系统 HDFS 以及分布式运算框架 MapReduce。 2.2 HDFS 分布式文件系统 什么是分布式文件系统？分布式文件系统又有哪些特点？ 简单的说，管理的物理存储资源分布在多台节点上，节点之间通过计算机网络相连，就构成了分布式文件系统。它的服务基于客户机 /服务器模式，文件系统提供多个对外的访问入口 ，提供备份和容错
18、的功能。同时文件系统一般都基于操作系统的本地文件系统。这种模式的系统称为分布式文件系统 多用户多应用的并行读写是分布式文件系统产生的根源。通常，传统文件系统最大的问题是容量和吞吐量的限制。而分布式文件系统在数据的并行读写方面有很大的优势，直观的讲，一块硬盘的读写性能，比不上多块硬盘同时读写的性能。分布式文件系统的特点是扩充存储空间的成本低廉，可提供冗余备份，还可以为分布式计算提供基础。 2 2.2.1 HDFS 设计思想 HDFS 设计的目标主要有以下几点： 具有存储海量数据的能力。适合存储 大量文件，总存储量可以达到 PB,EB级，适合存储大文件，单个文件大小一般在百 MB 级之上。 满足流
19、式数据访问。 Hadoop 建立在这样的一个思想上，数据一次写入，多次读取是最有效率的。数据集的形成通常是从数据源的获得或者复制，接着在此基础上进行各种形式的分析。每次分析要涉及到数据集中的大部分数据。 HDFS 被设计用于批处理而非交互式应用。 HDFS侧重于提供高数据吞吐量，可以容忍数据访问的高延迟 6 运行成本低廉并且可以容忍硬件出错， HDFS 可以运行在价格低廉的普通硬件上，如果其中一台或者几台服务器出现故障时，系 统依旧可用并且数据完整。 错误恢复。由于 Hadoop 集群节点数量很大，发生各种各样的错误而导致节点不可用的概率也很高，所以 HDFS 被设计为可以自动检测这些错误并且
20、进行数据的保护和数据的恢复。 平台的移植性。 HDFS 可以在异构的平台上移植，增加了应用的灵活性。 移动程序代替移动数据。因为程序的规模与数据比起来小很多，在移动上更为方便。程序的计算请求在操作数据本地还会减少网络的拥塞。 2.2.2 名字节点和数据节点 HDFS 的架构如 图 3-1 所示。 图 3-1. HDFS 架构图 HDFS 是一个大规模的分布式文件系统，采用 master/slave 架构。从上图可以看出，一个 HDFS 集群是由一个 NameNode 和一定数目的 DataNode 组成。 NameNode 是一个中心服务器，负责管理文件系统的 namespace 和客户端对文
21、件的访问， DataNode 在集群中有多个节点，负责管理各自节点上本地自带的存储。 NameNode 是 Hadoop 守护进程中最重要的一个，它管理着文件系统的命名空间，维护文件系统树和树内所有的文件和索引，同时还保存着文 件名到数据块的映射和数据块到 DataNode 的映射。在一个 HDFS 集群中只有一个命名空间和一个根目录，一份元数据。元数据保存在 NameNode 的内存当中，以便快速查询。 NameNode 进程运行的机器通常是 Hadoop 集群中配置最高的机器，因为NameNode 在运行中需要消耗大量的内存和 IO 资源。一般来说， 1G 内存大致可以存放 1,000,0
22、00 个块对应的元数据信息。（按缺省每块 64M 计算，大致对应 64T实际数据） NameNode 的重要性也带来了一个负面的影响，那就是 Hadoop 集群的单点故障，它不像其他的守 护进程，宕掉了不影响 Hadoop 集群的平稳运行，如果NameNode 宕机或者硬件出现故障，整个 Hadoop 集群都会受到影响。这里我们再介绍一下 Standby NameNode 的概念。 Standby NameNode（ SNN）是一个用于检测整个 Hadoop 集群状态的辅助守护进程，像 NameNode 一样，在一个集群中， SNN 也会独占一台机器。它一个主要的作用就是 NameNode 的
23、快照功能。平时工作时， SNN 不会接受 HDFS 的任何实时变化，它按照集群配置的时间间隔获取 HDFS 元数据的快照。这样在NameNode 出现故障的时候，用户可以手工进行干预，手工的重新配置集群，将SNN 做为临时的 NameNode，通过一些人工干预和技术手段， SNN 可以有助于减少系统停机的时间和降低数据丢失的风险， SNN 的硬件配置基本与 NameNode的配置相同。 DataNode 节点保存实际的数据，集群中的每台机器分别运行一个 DataNode守护进程， DataNode 节点通过心跳机制与 NameNode 节点进行定时的通信。客户端读取 /写入数据的时候直接与 D
24、ataNode 通信 。 2.2.3 块的概念 在传统的块存储介质中，块是读写的最小数据单位 ,传统文件系统基于存储块进行操作 ,像类似 df,fsck 等工具均是对块进行操作，为了节省文件分配表空间，会对物理存储块进行整合，一般大小为 4096 字节。 HDFS 也使用了块的概念，不过是更大的单元，默认大小设为 64M 字节，也可针对具体的文件配置，由客户端自己指定。每个块有一个自己的全局 ID 作为唯一标识。 HDFS 将一个文件分为一个或数个块来存储，每个块是一个独立的存储单位。以块为单位在集群服务器上分配存储。与传统文件系统不同的是，如果实际数据没有达到块大小，则并不实际占用磁盘空间。
25、例如：一个文件是 200M，则它 会被分为 4 个块 : 64+64+64+8。 在分布式文件系统中使用块会带来一些好处。首先，它会使文件系统可以存储比任何一个硬盘储存容量都大的文件，该文件的分块不需要只储存在一块硬盘上，而是可以储存在集群的任何一块磁盘上。 其次，使用快会简化文件系统的管理。对于故障种类繁多的分布式文件系统来说，储存子系统管理的是块而不是文件，简化了存储的管理。因为块的大小是固定的，计算一个磁盘能够存放多少块就相对容易些。同时也简化了元数据的管理，块可以只存储数据，元数据的信息不一定要和数据存放在一起。 第三，块的概念可以为数据 复制以及容错提供方便。为了应对损坏的块或者是硬
26、件方面的故障，每个块都会在其他的机器上进行复制，如果一个块损坏了，用户可以从其他的位置块的副本上读取信息，而这个过程对于用户来说是一个透明的过程，同时集群还会把损坏的块的信息从它的副本上再重新复制到一个好的块上，保证副本数量回到原来的水平。 2.2.4 文件系统命名空间 HDFS 支持传统的层次化文件组织，在 HDFS 中用户可以创建不同的文件目录，把文件放在不同的目录中，文件系统的命名空间层次类似于大多数文件系统，用户可以创建、修改、删除、移动、重命名文件及目录，目前 HDFS 暂不支持文件的软硬链接及访问权限控制。这些信息的变动都会由 NameNode 记录，同时用户可以指定一个文件在 H
27、DFS 文件系统中复制的份数，也叫做文件的复制因子，同样也由 NameNode 记录。 3.1.1 元数据的持久化 HDFS 对元数据和实际数据采取分别存储的方法，元数据存储在一台指定的服务器上 (NameNode)，而实际数据储存在集群的其他机器的本地文件系统中(DataNode)。元数据包括文件系统目录树信息 ,主要包括文件名、目录名、文件和目录的从属关系、文件和目录的大小，创建及最后访问时间及权限。元数据也会记载文件与块的关系，文件由哪些块组成，块的存放位置，机器名，块 ID 等。 NameNode 里使用两个非常重要的本地文件来保存元数据信息： fsimage（文件系统映像）和 edi
28、ts（编辑日志）。 fsimage 里保存了文件系统目录树信息以及文件和块的对应关系。它是文件系统元数据的持久性检查点。 Fsimage 不会随时更新文件系统的每个写操作，因为写出 fsimage 的速度很慢。每次当 NameNode启动时，就会将磁盘中的 fsimage 文件加载到内存，并将此应用于 edits 中的每个操作，然后将新的元数据保存到本地磁盘驱 动器中 fsimage 文件中。 Fsimage文件没有记录块存储在哪个数据节点， NameNode 把这种映射保留在内存中，当DataNode 加入集群时要求提供这些 DataNode 所包含的块列表，此后定期执行，以确保 NameN
29、ode 的块隐射是最新的。 edits 保存文件系统的更改记录，当客户端对文件进行写操作 (包括新建或移动 )的时候，操作首先记入 edits，成功后才会更改内存中的数据，并不会立刻更改硬盘上的 fsimage。 如前所述， edits 文件会不断变大。当 NameNode 在运行期间不会对系统造成影响，但是当 NameNode 重新启动时，需要花很长时间来运行 edits 日志中的每个操作，在此期间，文件系统会脱机，这样就产生了 HDFS 集群的单点故障。 解决这种问题的方案，就是前文提到的 SNN（ Standby NameNode），其目的是产生一个主 NameNode 的内存中文件系统
30、元数据的检查点。当一个检查点事件发生时首先 NameNode 会产生一个新的 edits 文件，后面的操作都记载在这个新的文件中。这时 SNN 会从主节点获取 fsimage 和 edits，将 fsimage 加载到内存中，执行 edits 中的每个操作，然后创建一个新 的统一的 fsimage 文件，然后将新的 fsimage发送到主节点。主节点用获得的新 fsimage文件替代旧的 fsimage。同时更新一个名为 fstime 的文件，来记录该检查点发生的时间。检查点的时间可以根据具体情况由配置参数决定， SNN 的目录结构与主 NameNode 的目录结构完全相同。经过这样一些配置，
31、一旦 NameNode 发生故障，就可以尽快的从SNN 恢复。 3.1 MapReduce 原理深入解析 MapReduce 来自于 Google 的论文，它是一种编程模型，把一个复杂的问题分解成处理子集的子问题，基本思想是可以拆 分为对子问题分别进行处理 (Map)，然后把子问题处理后的结果进行汇总 (Reduce)。 HadoopMapReduce 是基于 HDFS 的 MapReduce 编程框架，是一个能够在大量的普通配置的计算机上处理和生成超大数据集的编程模型的具体实现。这个框架确保程序以可靠的，容错的方式执行。采用 HadoopMapReduce 架构可以使那些没有并行计算和分布式
32、处理系统开发经验的程序员有效利用分布式系统的丰富资源。 3.2.1 Jobtracker 与 Tasktracker Jobtracker 负责应用程序与 Hadoop 集群间之间 的沟通，当代码提交到集群上， Jobtracker 就会确定执行计划，接受客户端提交作业分配任务到计算节点(Tasktracker)，同时监控作业的运行情况，更新作业状态，进行作业容错处理。如果作业失败， Jobtracker 会自动重启任务，但重新分配的节点有可能会不同。客户端可通过命令行或 Web 页面查看作业状态。 Jobtracker 可以和 NameNode运行在同一个服务器上。 Jobtracker 也是一个单点故障的服务，如果 Jobtracker失效，所有正在运行的作业都会失败。当集群规模较大或是任务繁重的场景，建议单独运行 Jobtracker。 7 根据计算向数据移动的原则， JobTracker 会与 NameNode 通信以定位任务所需数据的位置，从而更有效的分配任务执行节点。更具体的情况是， JobTracker不保证一定在数据所在节点处理数据，取决与任务节点的空闲状态并且尽量在一
