资源描述：
《基于hadoop的数据挖掘算法并行化研究与实现11》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
基于hadoop的数据挖掘算法并行化研究与实现摘要随着互联网技术的发展和云计算技术的流行，提供网络服务的互联网公司每天生成和需要处理的数据呈爆炸式增长，海量数据已经逐渐将我们包围。数据的不断增长给人们带来了巨大价值，同时也给人们带来了巨大的挑战。如何分析和挖掘这些数据背后隐藏的有价值的信息，已经成为很多大型企业所关注的焦点。大规模文档信息资源的自动化处理是海量数据处理中较受关注的一个领域，企业通过对文本数据进行分类，不仅可以对数字资源进行有效的整理，而且保证数字资源被全面检索和充分利用，满足用户对信息咨询服务的需求。但同时互联网企业产生的文本数据又具有海量，复杂等特点，面对现在飞速增长的文本数据，传统采用单机来处理的方式已经逐渐满足不了人们的需求，如何高效率的对海量文本进行分类整理并且挖掘出有价值的信息，这是本文的一个关注的问题。Hadoop是目前最流行的用于处理海量数据的开源分布式框架。Hadoop主要的组件包括HDFS和MapReduce。HDFS是Hadoop集群提供的分布式文件系统，而MapReduce是一种分布式框架，通过这两者的结合，可以对海量的文本数据进行有效的处理。本文研究了Hadoop进行分布式处理的步骤和原理，在其基础上设计并实现了基于Hadoop的分布式文本分类系统，通过与单机系统处理结果的对比，论证了Hadoop系统在进行文本分类时的效率要高于单机，并且取得良好的分类效果。 目录基于hadoop的数据挖掘算法并行化研究与实现1第一章绪论31.1课题研究背景31.2研究现状41.2.1Hadoop研究现状41.2.2文本分类研究现状51.3本文的主要工作51.4论文的组织结构5第二章Hadoop分布式框架概述62.1什么是Hadoop62.2HDFS分布式文件系统72.2.1HDFS设计思想72.2.2名字节点和数据节点72.2.3块的概念92.2.4文件系统命名空间9第三章文本分类的原理163.1向量空间模型163.2中文分词173.3特征选择183.3.1卡方检验193.3.2信息增益193.4特征权重计算203.4.1什么是特征权重203.4.2TF/IDF203.4.2特征权重与特征选择的区别213.5文本分类算法21 3.5.1朴素贝叶斯方法213.5.2支持向量机(SVM)223.6文本分类的评价体系283.6.1准确率(Precision)与召回率(Recall)283.6.2F值(F-measure)28第四章基于Hadoop平台的文本分类系统的设计294.1环境搭建与实验设计294.1.1系统环境配置294.1.2Hadoop集群配置324.2文本表示过程的并行化354.2.1预处理和中文分词并行化354.2.2特征选择并行化364.2.3TF/IDF计算并行化374.3基于朴素贝叶斯文本分类的并行化374.4基于SVM文本分类的并行化384.4.1SVM并行化384.4.3MapReduce实现414.4.4基于Hadoop的SVM实现42第一章绪论1.1课题研究背景 我们处在一个数据爆炸的时代，随着互联网技术的发展和云计算技术的流行，互联网正以海量的数据资源和咨询信息丰富着人们的日常生活，网络数据规模正以几何式增长！仅仅以互联网技术的发展为例，各种微博，论坛，社交网站等网站如雨后春笋般层出不穷。据统计，目前全球的Web站点已经达到数亿个，而且还在飞速增长中。网络上各种电子书籍、门户新闻、信息咨询等服务内容在满足人们网络服务需求的同时，也给对海量的数据处理带来了巨大的挑战。在海量数据处理问题中，文档自动分类成为处理和组织大量文档数据的关注焦点。在数字图书馆中，对数字文本进行准确高效的分类是保证数字资源被全面检索和充分利用的基础。在门户网站中，对实时新闻的准确快速分类是满足人们获得良好的咨询服务的关键。文本分类是文本处理领域的重要研究内容之一，其任务就是在预先给定的分类模型下，系统在学习各类的训练文档的基础上，根据文本的内容让计算机自动判断、预测未知类文档的类别。文本分类技术已经应用于信息检索、信息抽取、数字化图书馆、新闻门户、网上信息快速定位等多个领域。文本自动分类是通过分析被分类文档的特征，并与其他各类文档所具有的共同特征进行比较，将被分类文档归于特征最接近的一类并赋予相应类别。常用的文本分类方法有K近邻(KNN)方法、朴素贝叶斯(NaiveBayes)方法、神经网络方法(NeuralNet)、支持向量机(SVM)方法和决策树方法(DecisionTree)等。其中朴素贝叶斯分类方法是一种简单有效的概率分类方法,在某些领域表现出很好的性能。就目前网络上的海量文本数据而言，传统的文本分类方法具有以下两点局限：一是分类效率低，互联网上动辄几十TB的文本数据如果使用传统单机的分类方式需要大量的时间；二是分类准确率不高，没有充分考虑特征权重对分类效果的影响。本文将主要针对基于Hadoop的文本分类并行化方法进行研究，着力提高海量文本数据下的文本分类效率和准确率。1.2研究现状1.2.1Hadoop研究现状Hadoop是Apache基金会的一个开源项目由DougCuttingApacheLucene的创始人所带领的团队幵发实现了Google的GFS和MapReduce思想。目前Hadoop的最新版本是2012年12月1日发布的Hadoopl.1.1并还在不断完善发展之中。其为开发者提供了一个分布式系统的基础架构用户可以在不了解分布式系统的底层细节的情况下来开发分布式应用充分利用集群的强大功能实现高速运算和存储。由于Hadoop优势突出不论在国内还是国外基于Hadoop的应用已经遍地开花尤其是在互联网领域。2008年2月雅虎宣布搭建出当时世界上最大的基于Hadoop的集群系统——Yahoo!SearchWebmap它们在2000个节点上执行了超过1万个Hadoop虚拟机器来处理超过5PB的网页内容分析大约1兆个网络连接之间的网页索引资料。著名SNS网站Facebook用Hadoop构建了整个网站的数据仓库存储日志数据支持其上的数据分析和机器学习。近几年 国内应用和研究Hadoop的企业也越来越多包括淘宝、百度、中国移动等。百度用Hadoop处理每周200TB的数据进行搜索日志分析和网页数据挖掘工作同时赞助了HyperTable的幵发;淘宝的Hadoop系统用于存储并处理电子商务的交易相关数据。为了满足互联网海量数据的处理和挖掘需求，将机器学习应用于大型数据库的数据挖掘和知识发现技术也得到了长足的发展。目前，基于云计算的数据挖掘正处于研究阶段，也会是最近几年的研究热点。Mahout是ApacheSoftwareFoundation（ASF）旗下的一个开源项目，提供一些可扩展的机器学习领域经典算法的实现，旨在帮助开发人员更加方便快捷地创建智能应用程序。ApacheMahout项目已经发展到了它的第三个年头，目前已经有了三个公共发行版本。Mahout包含许多实现，包括集群、分类、推荐过滤、频繁子项挖掘。此外，通过使用ApacheHadoop库，Mahout可以有效地扩展到云中。1.2.2文本分类研究现状国外主要的研究单位如CMU、斯坦福。国内主要的研究单位有东北大学、上海复旦大学、哈尔滨工业大学、中科院计算所、TRS等，主要都是将国外的方法引进来应用到中文信息处理技术上。到目前为止，文本自动分类在国外大致经历了三个发展阶段：第一阶段（1958-1964）主要进行自动分类的可行性研究。第二阶段（1965-1974）进行自动分类的试验研究。第三阶段（1975-至今）进行实用化阶段，并在邮件分类、电子会议、信息过滤等方面取得较为广泛的应用，其中较为成功的系统有麻省理工学院（MIT）为白宫开发的邮件分类系统，卡内基集团为路透社开发的Construe系统等。我国文本分类的研究工作始于20世纪80年代，大体经历了可行性探讨、辅助分类系统、自动分类系统三个阶段。总体来书，中文文本分类还处于在试验研究阶段，正确分类率约为60%~90%，已经逐渐向商业话的软件应用靠拢，并已经尝试开发了一批自动分类系统。例如，清华大学吴军研制的自动分类系统、山西大学刘正瑛等人开发的金融自动分类系统、上海交大的西风文本自动分类系统。如何找到合理的应用并且在实践中逐步改善算法，提高性能成为文本分类算法的当务之急。1.3本文的主要工作1.4论文的组织结构论文的结构安排如下：第一章介绍了本文的研究背景，通过对现在海量数据的处理和海量文本的分类问题，引入了Hadoop，然后介绍了Hadoop和文本分类技术的国内外研究现状。第二章主要介绍Hadoop及相关的技术，简要介绍什么是Hadoop和HDFS分布式文件系统，并介绍了MapReduce框架原理以及其作业执行流程。 第三章详细介绍了文本分类模型训练的主要步骤——文本表示、中文分词、特征选择、特征权重计算、文本分类算法，以及每个部分所用到的算法和原理。第四章利用Hadoop平台设计了一个分布式的文本分类系统，介绍了Hadoop集群搭建的主要步骤以及如何利用MapReduce框架实现文本分类系统各个部分的并行化工作。第五章运行实验并分析实验结果。通过实验证明在处理海量文本数据的时候引入Hadoop集群上在效率上要优于单机服务器的处理方式，即文本分类结果的不足和需要哪些改进。第六章总结本次论文所完成的工作，介绍一下自己的心得及对Hadoop技术处理海量文本数据方面未来的展望。第二章Hadoop分布式框架概述2.1什么是Hadoop简单的说，Hadoop是Apache开源软件基金会开发的运行于大规模普通服务器上的用于海量数据存储、计算、分析的分布式存储和分布式运算框架。[3]主要的特点包括：1.成本低廉：Hadoop可以运行在一般商用机器构成的大型集群上，机器的配置不需要很高。目前多采用X86Linux服务器。2.可扩展性：Hadoop通过扩展集群的节点，可以近乎线性的增加集群的处理能力，以处理更多的数据,存储的数据可以达到PB级别。3.高可用性：集群机器数量越多，出现硬件的故障的概率就越高。Hadoop可以轻松面对硬件故障带来的数据丢失及备份问题。正是由于Hadoop具有的这些特点，使得它很快成为了学术界包括工业界的宠儿。硬件方面的成本低廉，即使是在校的大学生也可以轻松部署自己的Hadoop集群来完成自己的学术实验，同时可扩展性以及高可用性可以很好的承担公司企业严格的生产任务。下图是Hadoop的体系结构： Hadoop的核心服务组件包括两部分：分布式文件系统HDFS以及分布式运算框架MapReduce。2.2HDFS分布式文件系统什么是分布式文件系统？分布式文件系统又有哪些特点？简单的说，管理的物理存储资源分布在多台节点上，节点之间通过计算机网络相连，就构成了分布式文件系统。它的服务基于客户机/服务器模式，文件系统提供多个对外的访问入口，提供备份和容错的功能。同时文件系统一般都基于操作系统的本地文件系统。这种模式的系统称为分布式文件系统多用户多应用的并行读写是分布式文件系统产生的根源。通常，传统文件系统最大的问题是容量和吞吐量的限制。而分布式文件系统在数据的并行读写方面有很大的优势，直观的讲，一块硬盘的读写性能，比不上多块硬盘同时读写的性能。分布式文件系统的特点是扩充存储空间的成本低廉，可提供冗余备份，还可以为分布式计算提供基础。[2]2.2.1HDFS设计思想HDFS设计的目标主要有以下几点：l具有存储海量数据的能力。适合存储大量文件，总存储量可以达到PB,EB级，适合存储大文件，单个文件大小一般在百MB级之上。l满足流式数据访问。Hadoop建立在这样的一个思想上，数据一次写入，多次读取是最有效率的。数据集的形成通常是从数据源的获得或者复制，接着在此基础上进行各种形式的分析。每次分析要涉及到数据集中的大部分数据。HDFS被设计用于批处理而非交互式应用。HDFS侧重于提供高数据吞吐量，可以容忍数据访问的高延迟[6]l运行成本低廉并且可以容忍硬件出错，HDFS可以运行在价格低廉的普通硬件上，如果其中一台或者几台服务器出现故障时，系统依旧可用并且数据完整。l错误恢复。由于Hadoop集群节点数量很大，发生各种各样的错误而导致节点不可用的概率也很高，所以HDFS被设计为可以自动检测这些错误并且进行数据的保护和数据的恢复。l平台的移植性。HDFS可以在异构的平台上移植，增加了应用的灵活性。l移动程序代替移动数据。因为程序的规模与数据比起来小很多，在移动上更为方便。程序的计算请求在操作数据本地还会减少网络的拥塞。2.2.2名字节点和数据节点HDFS的架构如图3-1所示。 图3-1.HDFS架构图HDFS是一个大规模的分布式文件系统，采用master/slave架构。从上图可以看出，一个HDFS集群是由一个NameNode和一定数目的DataNode组成。NameNode是一个中心服务器，负责管理文件系统的namespace和客户端对文件的访问，DataNode在集群中有多个节点，负责管理各自节点上本地自带的存储。NameNode是Hadoop守护进程中最重要的一个，它管理着文件系统的命名空间，维护文件系统树和树内所有的文件和索引，同时还保存着文件名到数据块的映射和数据块到DataNode的映射。在一个HDFS集群中只有一个命名空间和一个根目录，一份元数据。元数据保存在NameNode的内存当中，以便快速查询。NameNode进程运行的机器通常是Hadoop集群中配置最高的机器，因为NameNode在运行中需要消耗大量的内存和IO资源。一般来说，1G内存大致可以存放1,000,000个块对应的元数据信息。（按缺省每块64M计算，大致对应64T实际数据）NameNode的重要性也带来了一个负面的影响，那就是Hadoop集群的单点故障，它不像其他的守护进程，宕掉了不影响Hadoop集群的平稳运行，如果NameNode宕机或者硬件出现故障，整个Hadoop集群都会受到影响。这里我们再介绍一下StandbyNameNode的概念。StandbyNameNode（SNN）是一个用于检测整个Hadoop集群状态的辅助守护进程，像NameNode一样，在一个集群中，SNN也会独占一台机器。它一个主要的作用就是NameNode的快照功能。平时工作时，SNN不会接受HDFS的任何实时变化，它按照集群配置的时间间隔获取HDFS元数据的快照。这样在NameNode出现故障的时候，用户可以手工进行干预，手工的重新配置集群，将SNN做为临时的NameNode，通过一些人工干预和技术手段，SNN可以有助于减少系统停机的时间和降低数据丢失的风险，SNN的硬件配置基本与NameNode的配置相同。 DataNode节点保存实际的数据，集群中的每台机器分别运行一个DataNode守护进程，DataNode节点通过心跳机制与NameNode节点进行定时的通信。客户端读取/写入数据的时候直接与DataNode通信。2.2.3块的概念在传统的块存储介质中，块是读写的最小数据单位,传统文件系统基于存储块进行操作,像类似df,fsck等工具均是对块进行操作，为了节省文件分配表空间，会对物理存储块进行整合，一般大小为4096字节。HDFS也使用了块的概念，不过是更大的单元，默认大小设为64M字节，也可针对具体的文件配置，由客户端自己指定。每个块有一个自己的全局ID作为唯一标识。HDFS将一个文件分为一个或数个块来存储，每个块是一个独立的存储单位。以块为单位在集群服务器上分配存储。与传统文件系统不同的是，如果实际数据没有达到块大小，则并不实际占用磁盘空间。例如：一个文件是200M，则它会被分为4个块:64+64+64+8。在分布式文件系统中使用块会带来一些好处。首先，它会使文件系统可以存储比任何一个硬盘储存容量都大的文件，该文件的分块不需要只储存在一块硬盘上，而是可以储存在集群的任何一块磁盘上。其次，使用快会简化文件系统的管理。对于故障种类繁多的分布式文件系统来说，储存子系统管理的是块而不是文件，简化了存储的管理。因为块的大小是固定的，计算一个磁盘能够存放多少块就相对容易些。同时也简化了元数据的管理，块可以只存储数据，元数据的信息不一定要和数据存放在一起。第三，块的概念可以为数据复制以及容错提供方便。为了应对损坏的块或者是硬件方面的故障，每个块都会在其他的机器上进行复制，如果一个块损坏了，用户可以从其他的位置块的副本上读取信息，而这个过程对于用户来说是一个透明的过程，同时集群还会把损坏的块的信息从它的副本上再重新复制到一个好的块上，保证副本数量回到原来的水平。2.2.4文件系统命名空间HDFS支持传统的层次化文件组织，在HDFS中用户可以创建不同的文件目录，把文件放在不同的目录中，文件系统的命名空间层次类似于大多数文件系统，用户可以创建、修改、删除、移动、重命名文件及目录，目前HDFS暂不支持文件的软硬链接及访问权限控制。这些信息的变动都会由NameNode记录，同时用户可以指定一个文件在HDFS文件系统中复制的份数，也叫做文件的复制因子，同样也由NameNode记录。3.1.1元数据的持久化HDFS对元数据和实际数据采取分别存储的方法，元数据存储在一台指定的服务器上(NameNode)，而实际数据储存在集群的其他机器的本地文件系统中(DataNode)。元数据包括文件系统目录树信息,主要包括文件名、目录名、文件和目录的从属关系、文件和目录的大小，创建及最后访问时间及权限。元数据也会记载文件与块的关系，文件由哪些块组成，块的存放位置，机器名，块ID等。 NameNode里使用两个非常重要的本地文件来保存元数据信息：fsimage（文件系统映像）和edits（编辑日志）。fsimage里保存了文件系统目录树信息以及文件和块的对应关系。它是文件系统元数据的持久性检查点。Fsimage不会随时更新文件系统的每个写操作，因为写出fsimage的速度很慢。每次当NameNode启动时，就会将磁盘中的fsimage文件加载到内存，并将此应用于edits中的每个操作，然后将新的元数据保存到本地磁盘驱动器中fsimage文件中。Fsimage文件没有记录块存储在哪个数据节点，NameNode把这种映射保留在内存中，当DataNode加入集群时要求提供这些DataNode所包含的块列表，此后定期执行，以确保NameNode的块隐射是最新的。edits保存文件系统的更改记录，当客户端对文件进行写操作(包括新建或移动)的时候，操作首先记入edits，成功后才会更改内存中的数据，并不会立刻更改硬盘上的fsimage。如前所述，edits文件会不断变大。当NameNode在运行期间不会对系统造成影响，但是当NameNode重新启动时，需要花很长时间来运行edits日志中的每个操作，在此期间，文件系统会脱机，这样就产生了HDFS集群的单点故障。解决这种问题的方案，就是前文提到的SNN（StandbyNameNode），其目的是产生一个主NameNode的内存中文件系统元数据的检查点。当一个检查点事件发生时首先NameNode会产生一个新的edits文件，后面的操作都记载在这个新的文件中。这时SNN会从主节点获取fsimage和edits，将fsimage加载到内存中，执行edits中的每个操作，然后创建一个新的统一的fsimage文件，然后将新的fsimage发送到主节点。主节点用获得的新fsimage文件替代旧的fsimage。同时更新一个名为fstime的文件，来记录该检查点发生的时间。检查点的时间可以根据具体情况由配置参数决定，SNN的目录结构与主NameNode的目录结构完全相同。经过这样一些配置，一旦NameNode发生故障，就可以尽快的从SNN恢复。3.1MapReduce原理深入解析MapReduce来自于Google的论文，它是一种编程模型，把一个复杂的问题分解成处理子集的子问题，基本思想是可以拆分为对子问题分别进行处理(Map)，然后把子问题处理后的结果进行汇总(Reduce)。HadoopMapReduce是基于HDFS的MapReduce编程框架，是一个能够在大量的普通配置的计算机上处理和生成超大数据集的编程模型的具体实现。这个框架确保程序以可靠的，容错的方式执行。采用HadoopMapReduce架构可以使那些没有并行计算和分布式处理系统开发经验的程序员有效利用分布式系统的丰富资源。3.2.1Jobtracker与TasktrackerJobtracker负责应用程序与Hadoop集群间之间的沟通，当代码提交到集群上，Jobtracker就会确定执行计划，接受客户端提交作业分配任务到计算节点(Tasktracker)，同时监控作业的运行情况，更新作业状态，进行作业容错处理。如果作业失败，Jobtracker会自动重启任务，但重新分配的节点有可能会不同。客户端可通过命令行或Web页面查看作业状态。Jobtracker可以和NameNode运行在同一个服务器上。Jobtracker也是一个单点故障的服务，如果Jobtracker失效，所有正在运行的作业都会失败。当集群规模较大或是任务繁重的场景，建议单独运行Jobtracker。[7] 根据计算向数据移动的原则，JobTracker会与NameNode通信以定位任务所需数据的位置，从而更有效的分配任务执行节点。更具体的情况是，JobTracker不保证一定在数据所在节点处理数据，取决与任务节点的空闲状态并且尽量在一个机架。与分布式系统的存储守护进程一样，计算的守护进程也遵循master/slave架构：Jobtracker作为主节点，监控MapReduce作业的整个执行过程，而Tasktracker管理各个任务在每个从节点上的执行情况。每个Tasktracker负责执行Jobtracker分配的单项任务，虽然每个从节点上只有一个Tasktracker，但它可以生成多个JVM（JavaVirtualMachine,Java虚拟机）来并行的执行许多任务。Tasktracker调用具体的Map、Reduce、Shuffle和Sort等操作。当接到Jobtracker分配的任务时，每一个任务会生成一个单独的JVM进程，确保Tasktracker进程不会因为用户代码而崩溃。Tasktracker监视这些生成的进程，捕获输出和退出代码。当这个进程完成后，无论成功与否，都会通知Jobtracker。每个Tasktracker可以配置运行任务的最大数量，也叫Slot，对应一个JVM的Child实例。通常是核数-2(减去Tasktracker本身和DataNode进程)，而Map与Reduce分工的比例大概是2:1。Tasktracker是任务运行节点，通常和DataNode装在一起。Tasktracker通过发送心跳消息给Jobtracker，向Jobtracker汇报可运行任务数量。如果Jobtracker在规定的时间内没有收到Tasktracker传来的心跳信号，它就会认为这个Tasktracker已经崩溃，进而重新分配任务到其他的节点。3.2.1MapReduce工作原理MapReduce工作过程分为两个阶段：Map阶段和reduce阶段。每个阶段都有键/值对作为输入和输出。程序员定义了两个函数：Map函数和reduce函数。我们从一个例子了解一下MapReduce工作的逻辑流程：我们从某气象站得到一些数据，采用Map函数来找出每年的最高气温。该例Map函数只是一个数据准备阶段。通过这种方式建立数据，使得reducer函数能在此基础上进行工作，最后从中找出每年的最高气温。输入的气温数据格式如下：Map函数的功能从输入的数据中提取出年份和气温的键/值对：(1950,0)，(1950,22)，(1950,-11)，(1949,211)，(1949,78)Map函数的输出先由MapReduce框架处理，然后再被发送到reduce函数。这一处理过程根据键来对键/值进行排序和分组。因此，reduce函数会看到如下输入：(1949,[211,78])，(1950,[0,22,-11])。每年的年份后都有一系列气温度数。所有reduce函数现在必须重复这个列表并从中找出最大的度数。最后的输出为：(1949,211)，(1950,22)，也就是全球气温记录中每年的最高气温。上面的数据流如图3-2所示。在图的底部是Unix的管道，模拟整个MapReduce的流程。 图3-1.MapReduce流程示意图从上例我们大致可以看出MapReduce的基本逻辑流程，下面我们再详细介绍一下MapReduce的基本工作原理，如图3-3所示。图3-2.MapReduce基本工作原理图Hadoop把要处理的问题称之为Job，把Job又分成若干个任务（task）来工作，任务又分为Map任务和reduce任务。3.2.2.1.MapandShuffle首先，Hadoop把输入数据划分成等长的小数据，我们称为输入分片(inputsplit)，发送到MapReduce，Hadoop为每个分片(split)创建一个task，由它来运行分析每个分片的一个个记录（record）。Hadoop会尽量让输入数据块所在的DataNode和task所执行的DataNode为同一个，可以提高作业的运行效率，所以inputsplit的大小一般是HDFS的block大小。Hadoop从input split中读取一个个的record，然后依次调用Mapper的Map函数，将结果输出。Map的输出并不是简单的写入硬盘，而是利用缓冲的方式写到内存，因为频繁的磁盘读写会严重影响性能，它会先把数据写到一个内存的缓冲区，并且预先做个简单的排序。每个Map任务都有一个环形内存缓冲区，任务会把输出写到此。默认情况下缓冲区大小为100MB,当buffer中数据的到达一定的大小（默认为80%），一个后台线程将数据开始写入硬盘（此时Map输出继续被写到缓冲区，但如果在此期间缓冲区被填满，Map会阻塞直到写入过程结束）。写入硬盘之前，内存中的数据通过partitioner分成多个partition(分区)。在同一个partition中，后台线程会将数据按照key在内存进行内中排序。每次从内存向硬盘flush数据，都生成一个新的spill文件。当此task结束之前，所有的spill文件被合并为一个整的被partition的而且排好序的文件。reducer可以通过http协议请求Map的输出文件，tracker.http.threads可以设置http服务线程数，默认为40。Map任务把输出写入本地硬盘，而不是HDFS，因为Map的输出作为中间输出，中间输出被reduce处理后产生最终的输出，一旦作业完成，Map的输出就可以删除了。如果该节点运行的Map任务在Map输出给reduce任务处理之前崩溃，那么Hadoop将在另一个节点上重新运行Map任务以再次产生Map输出。3.2.2.1.ReduceandShuffleTasktracker需要为它的分区文件运行Reduce任务，而Reduce任务需要其对应的partition的所有的Map输出，这些Map输出可能是若干个Map执行的结果。Reduce如何知道要从那个Tasktracker取得Map输出呢？Map任务成功完成后，它们会通知其父Tasktracker状态已更新，然后Tasktracker进而通知JobTracker。这些通知在前面介绍的心跳交流机制中传输。因此，对于指定作业，JobTracker知道Map输出和Tasktracker之间的映射关系。Reduce线程定期向JobTracker获取Map输出的位置，直到得到所有输出位置。Reduce任务中的copy过程即当每个Map任务结束的时候就开始拷贝输出，因为不同的Maptask完成时间不同。Reduce任务中有多个copy线程，可以并行拷贝Map输出。当很多Map输出拷贝到Reduce任务后，一个背景线程将其合并为一个大的排好序的文件。当所有的Map输出都拷贝到Reducetask后，进入sort过程，将所有的Map输出合并为大的排好序的文件。最后进入Reduce过程，调用Reducer的Reduce函数，处理排好序的输出的每个key，最后的结果写入HDFS。Reducer有3个主要阶段：copy（shuffle）、sort和Reduce。Shuffle（Shuffle,whichpartitionsandsortstheper-Mapoutput），Reducer的输入就是Mapper已经排好序的输出。在这个阶段，框架通过HTTP为每个Reducer获得所有Mapper输出中与之相关的分块。Sort（Sort,whichmergesortstheshuffleoutputforeachpartitionofallMapoutputs），这个阶段，框架将按照key的值对Reducer的输入进行分组（因为不同Mapper的输出中可能会有相同的key）。Shuffle和Sort两个阶段是同时进行的；Map的输出也是一边被取回一边被合并的。Reduce任务并不具备数据本地读取的优势。一个单一的Reduce任务往往来自于所有Mapper的输出。因此，有序Map的输出必须通过网络传输到Reduce任务运行的节点，在那里进行合并，然后传递到用户定义的Reduce函数中。Reduce的输出通常存储在HDFS中。对于每个Reduce输出的HDFS块，第一个副本存储在本地节点，其他副本存储在其他机架节点中。在Reduce中，相同key的所有记录会到同一个Tasktracker上面运行，而不同的key可以在不同的Tasktracker上运行，我们称之为partition。Partition的规则为：（K1，V1）àInteger,即根据K1，生成一个partitionID,具有相同ID的K1则进入到同一个partition，被同一个Tasktracker上的同一个Reducer进行处理。 3.2.1MapReduce的作业执行流程MapReduce作业执行流程图如图3-4所示。图3-1.MapReduce作业执行流程图Map-Reduce的处理过程主要涉及以下四个实体：•客户端Client：用于提交MapReducejob•JobTracker：用户提交作业的服务器，同时，它还负责各个作业任务的分配，管理所有的任务服务器。•Tasktracker：负责执行具体的任务。•HDFS：Hadoop分布式文件系统，用于在各个进程间共享Job相关的文件MapReduce作业(job)是客户端执行的基本单位：包括输入数据,MapReduce程序和配置信息。3.2.3.1.作业提交JobClient的runJob()方法是用于创建JobClient实例和调用其submitJob()方法的简便方法。提交作业后，runJob()每秒会轮询作业的进度，如果发现作业与上一个记录不同，就会将记录报告到控制台。作业完成后，如果成功则显示作业计数器，失败则将导致作业失败的错误记录到控制台。[2]JobClient的submitJob()方法所实现作业提交的过程：1、向JobTracker请求一个新的jobID（通过调用JobTracker的getNewJobId()）2、检测此job的output配置。比如，如果没有指定输出目录或者它已经存在，作业就不会被提交，并有错误返回给MapReduce程序3、计算此job的inputsplits （即计算作业的输入划分，将作业分成多少块，每块大小是多少等等）。如果输入路径不存在，则划分无法计算，作业就不会被提交，并有错误返回给MapReduce程序。4、复制运行Job所需要的资源到HDFS目录中以jobID命名的jobtracker’sfilesystem中。这些资源包括作业JAR文件、配置文件和计算所得的输入划分。作业JAR的副本较多(由Mapred.submit.replication属性控制，默认为10)，这样一来，在Tasktracker运行作业任务时，集群能为他们提供许多副本进行访问（步骤3）5、通知JobTracker此Job已经可以运行了(步骤4)3.2.3.1.作业初始化当JobTracker收到submitJob调用的时候，将此作业放到一个队列中，交由Job调度器进行调度，并对其初始化。初始化首先创建一个对象来封装job运行的tasks,status以及progress（步骤5）.在创建task之前，job调度器首先从共享文件系统中获得JobClient计算出的inputsplits信息（步骤6）。其为每个inputsplit创建一个maptask。每个task被分配一个ID。3.2.3.2.任务分配Tasktracker周期性的向JobTracker发送心跳。告知JobTracker它是否存活，同时也充当两者之间的消息通道。可以通过心跳告诉JobTracker，它是否已经准备运行新的任务，如果是，JobTracker会为它分配一个任务，并使用心跳方法的返回值于Tasktracker进行通信（步骤7）。在JobTracker为Tasktracker选择一个task之前，JobTracker必须先选择一个Job，有很多调度算法，默认的方法是按照job的优先级。3.2.3.3.任务执行现在Tasktracker已经被分配了一个task，下一步就是要运行此task。首先，将它要执行的本地化作业的JAR文件从HDFS复制到Tasktracker所在的文件系统。同时，将应用程序所需要的全部文件从分布式缓存复制到本地磁盘（步骤8）。然后，任务新建一个本地工作目录，并把JAR文件中的内容解压到这个文件夹下。第三步，新建一个TaskRunner实例来运行任务。TaskRunner创建一个新的JVM（步骤9）来运行task（步骤10）。被创建的childJVM和Tasktracker通信来报告运行进度。3.2.3.4.任务结束当JobTracker获得最后一个task的运行成功的报告后，将job的状态改为成功。当JobClient从JobTracker轮询的时候，发现此job已经成功结束，则向用户打印消息，从runJob函数中返回。3.2.1本章小结 本章对Hadoop系统的架构进行了深入的分析，分别详细介绍了HDFS以及MapReduce。从HDFS的设计思想，名字节点和数据节点，HDFS块的概念，文件系统的命名空间以及元数据的持久化等方面介绍了HDFS的原理及组成。在MapReduce方面，分析了MapReduce的工作原理，介绍了包括Map过程与Reduce过程的实现，中间阶段的shuffle以及sort过程，介绍了MapReduce执行作业，处理作业的具体流程。第三章文本分类的原理3.1向量空间模型文本信息的特征表示模型有多种，常用的有布尔逻辑型、向量空间型、概率型以及混合型等。其中，向量空间模型 (VectorSpaceModel,VSM) 是近几年来应用较多且效果较好的方法之一 [2]。 1969 年， GerardSalton提出了向量空间模型 VSM ，它是文档表示的一个统计模型。该模型的主要思想是：将每一文档都映射为由一组规范化正交词条矢量张成的向量空间中的一个点。对于所有的文档类和未知文档，都可以用此空间中的词条向量(W 1 ,W2 ,…Wn)来表示 ( 其中， n为特征向量的个数； Wi 为 第i个特征的权重 )[3] 。我们首先看一下向量空间模型如何表示一个文本：空间向量模型需要一个“字典”：文本的样本集中特征词集合，这个字典可以在样本集中产生，也可以从外部导入，上图中的字典是[baseball,specs,graphics,...,space,quicktime,computer]。有了字典后便可以表示出某个文本。先定义一个与字典长度相同的向量，向量中的每个位置对应字典中的相应位置的单词，比如字典中的第一个单词baseball，对应向量中的第一个位置。然后遍历这个文本，对应文本中的出现某个单词，在向量中的对应位置，填入“某个值”。实际上填入的“某个值”，就是当前特征词的权重(Term Weight)，目前特征词的权重主要有以下四种：•Bool（presence）表示某个单词是否在某个文档中出现，如果出现则记为1，否定则记为0。 •Termfrequency(TF)表示某个单词在文本中出现的次数(上图中使用的权重)，一个文本中，某个特征词出现的愈多，可能其在样本中的贡献越大。 •Inversedocumentfrequency(IDF)documentfrequency表示特征词在数据集中出现的文档频率。某个词文档频率越低，相应的这些文档，越容易被捕获。• TF-IDFTF-IDF则综合了上面两种特征权重的性质。有关于“教育”的文档中，“高校”、“学生”等词出现的频率很高，而在“体育”类的文档中，“比赛”，“选手”出现的频率比很高。采用TF权重，这些特征词有着较高权重是合理的(Termfrequency)。但是，某些词如“这些”，“是”，“的”，也有着较高的词频，但是重要度显然没有，“高校”、“学生”、“比赛”，“选手”来得重要。但“这些”，“是”，“的”这些词IDF往往比较低，很好的弥补了TF的缺陷。因此TF-IDF权重，在传统的文本分类，信息检索领域有着非常广泛的运用。3.2中文分词中文分词(ChineseWordSegmentation)是指将连续的汉字序列按照一定的规则切割成汉语词汇序列的过程[21]。如想提取出Web内容中的命名实体,分词是内容处理的第一步,故而采取合适的分词技术是提高命名实体提取率的关键。由于中文没有英文那样有明显的空格符作为自然的分界符号,故而中分分词要比英文分词要复杂、困难的多。目前较为流行的分词基本算法主要有基于词典的方法、基于统计的方法和基于理解的方法。(1)基于词典的方法 基于词典的方法又称为机械分词方法或者字符串匹配方法,是依据一定的策略将待分析的汉字序列与一个中文词典中的词条逐个进行匹配,如果切出来的词序列在词典中匹配成功,则表示切分出来一个词。(2)基于统计的方法在中文语义中,词是较为稳定的字与字之间的一种基于特殊含义的组合,故而,相邻字一起出现的概率越大,就越可能构成一个词汇,这样便可以通过计算字与字之间组合的概率来确定对分词的判断，选取概率最大的结果作为分词方案。此种方法的考虑到了不同分词方案间概率大小的比较，比机械地基于词典的方法效果好很多。(3)基于理解的方法基于理解分词,也称为知识分词,是一种通过计算机从大量的语言知识中模拟出人类对句法、语义的理解来识别出最贴近原句语义的方法。但是这种分词的方案算法复杂度高,有效性与可行性尚不能在实际工作中进一步得到验证,故而目前还处于实验室内试验阶段。常用的中文分词的工具有很多，比如像：MMSEG、ICTCLAS、StandfordChineseWordSegmenter等。本文使用StanfordWordSegmenter进行中文分词，它是用JAVA编写的基于CRF模型的中文分词程序，具有良好的分词效果。使用步骤：1.下载stanfordChineseWordSegmenter分词包：http://nlp.stanford.edu/software/stanford-chinese-segmenter-2008-05-21.tar.gz2.解压缩tar.gz档3.为了方便分词程序处理，先将待处理中文文本转换成UTF-8格式的编码：iconv–fgbk–tutf-8text.txt>content.txt4.在Linux下，切换到解压缩之后的目录。执行：segment.batctbcontent.txtUTF-80>out.txt分词结果就会出现在out.txt。如下图所示：3.3特征选择向量空间模型表示的文本特征空间维度非常高,使文本分类的效率和精度非常低下。文本特征选择算法可以降低特征维度,去除冗余特征,保留区分性特征,从而提升分类效果。常见的文本特征选择算法有信息增益(IG)、开方校验(CHI)、互信息(MI)、文档频率(DF)等,其中信息增益和卡方检验方法一般效果较好,文档频率方法次之,互信息的方法一般效果较差[4]。 3.3.1卡方检验卡方检验最基本的思想就是通过观察实际值与理论值的偏差来确定理论的正确与否。具体做的时候常常先假设两个变量确实是独立的，然后观察实际值与理论值的偏差程度，如果偏差足够小，我们就认为误差是很自然的样本误差，是测量手段不够精确导致或者偶然发生的，两者确确实实是独立的，此时就接受原假设；如果偏差大到一定程度，使得这样的误差不太可能是偶然产生或者测量不精确所致，我们就认为两者实际上是相关的，即否定原假设，而接受备择假设。一般使用衡量偏差程度，这时又引来了新的问题，对于500的均值来说，相差5其实是很小的（相差1%），而对20的均值来说，5相当于25%的差异，这是使用方差也无法体现的。因此诶了让均值的大小不影响我们对差异程度的判断，改进上面的式子如下：在文本分类问题的特征选择阶段，我们主要关心一个词t与一个类别c之间是否相互独立，如果独立，就可以说词t对类别c完全没有表征作用，即我们根本无法根据t出现与否来判断一篇文档是否属于c这个分类。我们一般都使用”词t与类别c不相关“来做原假设。选择的过程也变成了为每个词计算它与类别c的开方值，从大到小排个序（此时开方值越大越相关），取前k个作为选出的特征。比如说现在有N篇文档，其中有M篇是关于体育的，我们想考察一个词“篮球”与类别“体育”之间的相关性。我们有四个观察值可以使用：特征选择1．属于“体育”2．不属于“体育”总 计1．包含“篮球”ABA+B2．不包含“篮球”CDC+D总 数A+CB+DN通过计算可以得出t(篮球)与c(体育)类文章的开方值为：接下来我们就可以计算其他词如“排球”，“产品”，“银行”等等与体育类别的开方值，然后根据大小来排序，选择我们需要的最大的数个词汇作为特征项。3.3.2信息增益在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。对分类系统来说，类别C是变量，它可能的取值是C1，C2，……，Cn，而每一个类别出现的概率是P(C1)，P(C2)，……，P(Cn )，因此n就是类别的总数。此分类系统的熵就可以表示为：因此特征T给系统带来的信息增益就可以写成系统原本的熵与固定特征T后的条件熵之差：通过这个公式就可以求出每个特征的信息增益值，即每个特征对系统的重要程度，然后选出前100个特征作为向量空间模型中表示文本的向量。由于卡方检验方法只能获取本地的特征集合，而信息增益可以得到全局的特征集合，所以本文选用信息增益法来进行特征提取。3.3特征权重计算我们在进行文本分类时，用卡方检验或者信息增益的方法得到精简过的特征向量以后，下一步要做的就是确定这些特征的权重，以便于将每一篇文档表示成的向量的形式，好让计算机能够看懂。3.3.1什么是特征权重特征权重是用来衡量某个特征项（即特征选择算法选出的单词）在一篇文章中的区分能力。布尔权重（Booleanweighting）是一种最简单的模型，即对于一个特征词，文本中只要出现过这个词其权重为1，如果没有出现过则权重为0。布尔权重只能反映这些词是否在文本出现过，而不能区分这些词对文本的“表现能力”。也有人用关键词出现的次数来作为一篇文章特征向量的权重，这样虽然能体现这个特征的重要性，但不具有对文本的区分能力，例如“中国”这个词在“文化”类和“军事”类的文章中出现的次数都很多。最常用的特征权重计算方法是TF/IDF。3.4.2TF/IDFTF（TermFrequency）即词频的意思。它衡量的是一个词的“热度”。比如一篇关于“英语培训”的文章，“新东方”出现了80次，“听力”出现了20次，“口语”出现了10次，“高分”出现了50次，“英语”出现了35次，表示成向量的形式就是：(新东方/80,听力/20,口语/10,高分/50,英语/35)。但是对于同样类型的文章，因为篇幅有长有短，因此要对特征值做归一化处理（即用词频除以文章的总词数）。假设第一篇文本有1000个字，正确的TF形式应该表示为：(新东方/0.08,听力/0.02,口语/0.01,高分/0.05,英语/0.035)。只考虑词频TF也还是不够，还需要考虑这个词是否在其它类中也一样很“ 热门”，一些常用字会在各种类别中都频繁出现。“新东方”会在一篇英语培训的文章中经常出现，但是在厨师培训领域也有一个“新东方”，而且很多领域的培训机构也会自称自己是这个领域的“新东方”，因此“新东方”这个词在表示这篇文章时的作用就要大大减低。要考虑词的区分度，还需要计算逆向文本频数IDF（InverseDocumentFrequency）。IDF=log(D/Dw)其中D表示文档总数，Dw表示包含关键字w的文档数。从公式中可以看出，包含关键字w的文档数量越少，IDF越大；如果每篇文章都出现了w（即Dw=D），IDF就等于0。直观地想想也是如此，如果一个词在每个类中都出现了，这个词也就不稀奇了。TF和IDF值的乘积就是TF/IDF。文本分类时常用TF/IDF来表示特征向量的权重，即不仅要考虑一个词在这篇文章中出现的频率还要考虑它在所有其他文本中出现的频率。3.3.1特征权重与特征选择的区别特征向量的选择和特征权重的计算在文本分类中是两个完全不同的概念。TF/IDF仅仅对那些不太具有代表性的特征的权重进行了一些修正，卡方统计和信息增益法等特征选择的目标是把原本上万维的词典进行简化，选择出比较有代表性的特征。也有些人会混淆这两者的区别，然后用TF/IDF去做特征选择，虽其选择出的特征也可以进行分类，但是效果没有卡方统计或者信息增益等特征选择算法好。3.5文本分类算法研究文本自动分类的关键问题是如何构造分类器,分类器需要通过某种算法进行学习获得。文本分类的算法大多来自于模式分类,基本上可以分为三大类:一类是基于统计的方法,如中心向量法、朴素贝叶斯(Naivebayes)、K近邻、回归模型、支持向量机(SVM)、最大熵模型等方法；另一种是基于连接的方法，如人工神经网络；还有一种是基于规则的方法，如决策树、关联规则等。这些方法的主要区别在于规则获取的方式。3.5.1朴素贝叶斯方法朴素贝叶斯方法是一种在已知先验概率与条件概率的情况下得到后验概率的模式识别方法，这种方法可以确定一个给定样本属于一个特定类的概率。朴素素叶斯方法基于一个前提,即在给定的文本类语境下，文本属性是相互独立的。设X为一任意文本，用向量表示为：X=()，它属于文档类C={}中的某一类。根据朴素贝叶斯公式有： 上式表示在给定文档X的条件下，X属于类别的概率(即后验概率)。所以分类的问题就转化为计算的值,使取得最大值的那个类别就是。在比较不同C值的后验概率时，分母P(X)总是常数，忽略掉。先验概率可以通过计算训练集中属于每一个类的训练样本所占的比例，容易估计，对类条件概率的估计，因为朴素贝叶斯假设事物属性之间相互条件独立，。所以要求max()即求max(*)。3.5.2支持向量机(SVM)支持向量机是在统计学习理论的基础上发展起来的一种机器学习方法，它基于结构风险最小化原理，将原始数据集合压缩到支持向量集合，学习得到分类决策函数。其基本思想是：根据结构风险最小化的原理，对一个给定的具有有限数量训练样本的学习任务,如何在高维空间中寻找一个超平面作为两类的分割，以保证最小的错误率。支持向量机在解决小样本、非线性及高维模式识别问题上表现出许多特有的优势，并在很多领域得到成功的应用。在文本分类方面SVM的表现也不错，其分类的准确率和召回率超过了现有的大部分方法。3.5.2.1线性可分考虑如图3.1所示的二维线性可分情况，图中实心点和空心点分别表示两类训练样本，SVM的目的就是要找出最优分类线H，使得分别过两类样本中离分类超平面最近的点且平行于分类线的H1,H2之间的距离最大。 图3.1二类线性可分最优超平面示意图设线性可分的样本集,分类线方程为,我们可以对它进行归一化，则满足：(3.1)此时分类间隔等于，使间隔最大等价于使最小。满足条件(3.1)且使最小的分类面即为最优分类面H，H1、H2上的训练样本点就称作支持向量(SupportVector)。实际上求最优分类超平面的问题归结为如下的约束优化问题：（3.2）这个优化问题引入Lagrange函数等价于：（3.3）其中为Lagrange系数。根据拉格朗日求极值定理，即为求Lagrange函数关于和的极小值。根据极值条件：得到 （3.4）将式（3.4）带入到拉格朗日函数式（3.3）中得到原始问题的对偶问题形式：（3.5）若为最优解，则即最优分类超平面的权向量是训练样本向量的线性组合。可以看出这是一个不等式约束下二次函数极值问题，存在唯一的最优解。且根据条件，这个优化问题的解满足（3.6）可由这个约束条件求出，对于所对应的样本成为支持向量，即若，则（3.7）解得。也称为分类阈值，它由一个支持向量得到的，也可通过两类中任意一对支持向量取中值。通常为了稳健性，可以根据所有的支持向量的总和取平均阈值。如此，求使目标函数最小的w和b问题即转换为了求Lagrange系数的问题，这个问题有更加高效的优化算法——SMO算法。3.5.2.2线性不可分对于一般线性可分情况，可以硬性地使训练集正确地被最优分类面分隔到分类面的两端；而对于线性不可分的情况，采用线性可分的方法无法得到这样的超平面，即某些训练样本不能满足(3.1)的要求，对于这种情况可以在约束条件中加一个松弛因子来“软化”对间隔的要求，即允许不满足约束条件（3.1）的样本点存在，这样(3.1)就变为 （3.8）从“软化”后的约束条件可以看出，如果松弛因子充分大时，样本点总是可以满足这个约束条件的，所以应该设法避免取值过大，可以通过在目标函数加入惩罚系数来对这些松弛变量进行“惩罚”，从而避免约束条件的“畸形”,对应的目标函数的最优化问题则改为:（3.10）其中>0为惩罚系数，起控制错分样本惩罚程度的作用。式(3.10)转化为其对偶得到的形式和式(3.5)几乎完全相同，只是的约束条件变为：。3.5.2.3核函数支持向量机在对线性可分或几乎线性可分问题分类时，直接在原始空间中寻找最优分类超平面作为分类面。然而在实际应用中的大多数问题（例如本文何总的文本分类问题）都是高维的、非线性的，这时需要引入核函数，通过核函数使非线性的训练样本数据映射到高维空间，再在高维空间中使用SVM训练算法找出合适的线性分离超平面将数据按类别分类。核函数的好处是，我们只需知道其内积运算，这样又避免了高维空间的计算复杂度。核函数的本质是一个函数K，对所有的满足，这里是从到内积特征空间F的映射。每当出现在SVM针对非线性可分数据集的训练算法中时，都可以使用来替换计算。这样，所有关于训练点的内积计算都在原来的空间上进行，比映射后的空间维数要低得多，从而减少了因为数据集映射到高维空间带来的维数灾难的影响。常用的核函数有h次多项式核、高斯径向基函数核核线性核：1）h次多项式核：2）高斯径向基函数核：3）线性核： 没有确定哪种核函数能够得到更准确的分类器或者分类函数，在实践中，核的选择一般不会导致结果准确率出现较大的差别。本文中选用最常见的高斯径向基函数核。使用核函数后对应的非线性分类问题的最优化的数学表达式如下：3.5.2.4停机准则用SVM的训练算法（如SMO算法）对目标函数的拉格朗日系数不断迭代训练的过程需要有个迭代的停止条件即停机准则，满足这个条件的即为SVM训练的最优解。常用的停机准则有三个：1）SVM训练算法从任意一个可行点出发，逐步进行迭代计算，在不违背约束条件的条件下使目标函数值逐渐缩小，观察每次迭代过程中目标函数的下降量，如果目标函数的下降量小于一定精度的时候则停止迭代。这种停机准则的缺点是不稳定，在实际应用过程中肯能会因为停机准则的不稳定性导致不一定能够得到最优化问题的最优解。2）使用问题的KKT条件作为第二个停机准则，该条件如下所示：在实际求解问题时，不要求严格满足上面的停机准则，只要在算法迭代的过程中达到某个给定的精度就可以结束迭代。3）使用原始问题的目标函数值与对偶问题的目标函数值之间的增长率等关系作为第三个停机准则：其中，给定一个迭代停止的精度，当他们之间的比率小与这个精度时，使迭代算法停止计算。 需要注意的是，作为停机准则的比较精度大小的选取是很重要的，因为精度是在平衡实际求解结果的准确度和训练所用的时间，精度过大会使准确率比较低，精度过小可能会浪费非常多的时间在提高很小一部分的准确率上。3.5.2.5SVM用于多分类SVM是一种典型的两类分类器，即它只回答属于正类还是负类的问题。而现实中要解决的问题，往往是多类的问题，例如本文中的文本分类问题。所以还需研究如何由两类分类器得到多类分类器。以文本分类为例，将SVM用于多分类的方法有很多，其中一种一劳永逸的方法，就是一次性考虑所有的样本，求解一个多目标函数的优化问题，一次性得到多个分类面，就像下图这样：多个超平面把空间划分为多个区域，每个区域对应一个类别，给一篇文章，看它落在哪个区域就知道了它的分类。但是这种一次性求解的方法计算量太大，无法达到实用的地步。目前比较常用的就是“一类对其余”和“一对一分类”方法：1）“一类对其余”方法就是每次仍然解一个两类分类的问题。比如有5个类别，第一次假定类别1的样本为正样本，其余2，3，4，5的样本都为负样本，这样得到一个两类分类器，它能够指出一篇文章是不是第1类的；第二次把类别2的样本定为正样本，把其余的1，3，4，5类的样本都定为负样本，得到一个分类器，如此下去，我们就可以得到5个这样的两类分类器（总是和类别的数目一致）。然后将需要分类的文本分别用这5个分类器进行分类，哪个分类器分为正类则此类即为文章的类别。这种多分类方法的缺点是训练时要考虑的样本点太多导致训练速度非常慢。2）“一对一分类”方法是在每两类样本之间都设计一个SVM分类决策函数，因此k个类别的样本就需要设计k(k-1)/2个分类面。当对一个未知样本进行分类时，每个分类器都对其进行分类，最后分得正类最多的类别即为该未知样本的类别。这种方法的缺点是当类别很多的时候需要训练的分类面比较多（类别的平方量级）。 SVM训练过程的时间复杂度主要和训练集的样本个数L、支持向量个数Nsv和每个样本的维数d相关，“一类对其余”方法比“一对一分类”方法需要考虑的样本数多很多，所以训练的时间也长很多，而文本分类问题的类别一般都不多，使用“一对一分类”方法也不会需要训练很多的分类面，所以本文中的文本分类任务我们使用“一对一分类”方法。3.6文本分类的评价体系文本分类从根本上说是一个映射过程,所以评估文本分类系统的标志是映射的准确程度和映射所需的计算成本。计算成本主要包括分类所需时间和所占空间,而准确程度主要通过准确率和召回率来考察。3.6.1准确率(Precision)与召回率(Recall)在文本分类领域，通常使用准确率和召回率来评估分类器的性能。准确率和召回率的公式如下：其中，a、b、c各值如下表所示：属于该类的文本数不属于该类的文本数判断为属于该类的文本数ab判断为不属于该类的文本数cd由公式可以看出,召回率就是一个文档应该属于某类,而分类器也确实将其分到该类别的概率;查准率就是对文档被分类器正确分类的概率。召回率考察的是分类器的完备性,而查准率考查的是分类的正确性。3.6.2F值(F-measure)召回率和准确率不是独立的，通常为了获得比较高的召回率通常要牺牲准确率；同样，为了获得比较高的准确率通常要牺牲召回率。因此需要有一种综合考虑召回率和准确率的方法来对分类器进行评价。VanRijsbergen于1979年提出的F值是这样一个方法。计算公式为: 其中0≤≤+是关于召回率和准确率的权重。当=0时,就与准确率一致,而当=+时,口就与召回率一致。即取值越小越强调准确率的重要性,而取值越大越强调召回率的重要性。一般情况下取=1，使它们的重要程度相同,这时就为常用的F1值：第四章基于Hadoop平台的文本分类系统的设计4.1环境搭建与实验设计4.1.1系统环境配置利用实验室的4台计算机搭建一套4个节点的小型Hadoop集群，其中一台NameNode与Jobtracker节点，三台DataNode与Tasktracker节点，具体结构如图4-1所示。 图4.1实验环境示意图a.配置主机名修改每台服务器上的/etc/hosts文件，加入如下内容：192.168.1.1master192.168.1.2slave1192.168.1.3slave2192.168.1.4slave3主机信息: 机器名IP地址作用master192.168.1.1NameNode、JobTrackermaster192.168.1.2DataNode、TaskTrackerslaver1192.168.1.3DataNode、TaskTrackerslaver3192.168.1.4DataNode、TaskTrackerb.安装JDK $sudoapt-getinstallsun-java6-jdk1.2.3这个安装，java执行文件自动添加到/usr/bin/目录。验证shell命令：java-version看是否与你的版本号一致。 c.创建hadoop账户$useraddhadoop$cd/home/Hadoop在所有的机器上都创建相同的用户和目录，最好是以该用户的home路径来做hadoop的安装路径。例如在所有的机器上的安装路径都是：/home/hadoop/hadoop-0.20.203（这个不需要mkdir，在/home/hadoop/下解压hadoop包的时候，会自动生成）。d.安装和配置ssh1）安装sudoapt-getinstallssh这个安装完后，可以直接使用ssh命令了。执行$netstat-nat查看22端口是否开启。测试：sshlocalhost，如果显示需要输入当前用户的密码，说明安装成功（这种默认安装方式完后，默认配置文件是在/etc/ssh/目录下。sshd配置文件是：/etc/ssh/sshd_config）。2）配置在Hadoop启动以后，Namenode是通过SSH（SecureShell）来启动和停止各个datanode上的各种守护进程的，这就需要在节点之间以不需要输入密码的形式执行命令，故我们需要配置SSH运用无密码公钥认证的形式。以本文中的三台机器为例，现在master是主节点，他须要连接slaver1、slaver2和slaver3。首先确定每台机器上都安装了ssh，并且datanode机器上sshd服务已经启动。(说明：hadoop@hadoop~)$ssh-keygen-trsa这个命令将为hadoop上的用户hadoop生成其密钥对，询问其保存路径时直接回车采用默认路径，当提示要为生成的密钥输入passphrase的时候，直接回车，也就是将其设定为空密码。生成的密钥对id_rsa，id_rsa.pub，默认存储在/home/hadoop/.ssh目录下然后将id_rsa.pub的内容复制到每个机器(也包括本机)的/home/dbrg/.ssh/authorized_keys文件的结尾，如果没有authorized_keys这个文件，则以authorized_keys为名直接复制过去。)3)设置namenode的ssh为无需密码的、自动登录切换到hadoop用户(保证用户hadoop可以无需密码登录，因为我们后面安装的hadoop属主是hadoop用户。)$suhadoop$cd/home/hadoop$ssh-keygen-trsa然后一直按回车完成后，在home跟目录下会产生隐藏文件夹.ssh$cd.ssh之后ls查看文件cpid_rsa.pubauthorized_keys测试：$sshlocalhost或者： $sshmaster第一次ssh会有提示信息：Theauthenticityofhost‘master(10.64.56.76)’can’tbeestablished.RSAkeyfingerprintis03:e0:30:cb:6e:13:a8:70:c9:7e:cf:ff:33:2a:67:30.Areyousureyouwanttocontinueconnecting(yes/no)?输入yes，即可把该服务器添加到你的已知主机的列表中，并且无需密码。4)复制authorized_keys到slaver1、slaver2和slaver3上为了保证master可以无需密码自动登录到slaver1、slaver2和slaver3，先在slaver1、slaver2和slaver3上执行：$suhadoop$cd/home/hadoop$ssh-keygen-trsa一路按回车.然后回到master，复制authorized_keys到slaver1、slaver2和slaver3[hadoop@hadoop.ssh]$scpauthorized_keysslaver1:/home/hadoop/.ssh/[hadoop@hadoop.ssh]$scpauthorized_keysslaver2:/home/hadoop/.ssh/[hadoop@hadoop.ssh]$scpauthorized_keysslaver3:/home/hadoop/.ssh/这里会提示输入密码,输入hadoop账号密码就可以了。改动你的authorized_keys文件的许可权限[hadoop@hadoop.ssh]$chmod644authorized_keys 测试：sshslaver1（第一次需要输入yes）。如果不须要输入密码则配置成功，如果还须要请检查上面的配置能不能正确。4.1.2Hadoop集群配置a.安装Hadoop切换为hadoop用户,下载安装包后，直接解压安装即可：1)安装Hadoop集群通常要将安装软件解压到集群内的所有机器上。并且安装路径要一致，如果我们用HADOOP_HOME指代安装的根路径，通常，集群里的所有机器的HADOOP_HOME路径相同。2)如果集群内机器的环境完全一样，可以在一台机器上配置好，然后把配置好的软件即hadoop-0.20.203整个文件夹拷贝到其他机器的相同位置即可。3)可以将Master上的Hadoop通过scp拷贝到每一个slave相同的目录下，同时根据每一个slave的JAVA_HOME的不同修改其hadoop-env.sh。4)为了方便，使用hadoop命令或者start-all.sh等命令，修改Master上/etc/profile新增以下内容：exportHADOOP_HOME=/home/hadoop/hadoop-0.20.203exportPATH=$PATH:$HADOOP_HOME/bin修改完毕后，执行source/etc/profile来使其生效。5)配置conf/hadoop-env.sh文件在conf/hadoop-env.sh中添加：exportJAVA_HOME=/usr/lib/jvm/java-6-sun/（这里为你的jdk的安装位置）。 测试hadoop安装：Bin/hadoopjarhadoop-0.20.2-examples.jarwordcountconf//tmp/outb.集群配置（所有节点相同）1)配置文件：conf/core-site.xmlfs.default.namehdfs://master:49000hadoop.tmp.dir/home/hadoop/hadoop_home/varfs.default.name是NameNode的URI。hdfs://主机名:端口/hadoop.tmp.dir：Hadoop的默认临时路径，如果在新增节点或者其他情况下莫名其妙的DataNode启动不了，就删除此文件中的tmp目录即可。不过如果删除了NameNode机器的此目录，那么就需要重新执行NameNode格式化的命令。 2)配置文件：conf/mapred-site.xmlmapred.job.trackermaster:49001mapred.local.dir/home/hadoop/hadoop_home/var mapred.job.tracker是JobTracker的主机（或者IP）和端口。主机:端口。3)配置文件：conf/hdfs-site.xml dfs.name.dir/home/hadoop/name1,/home/hadoop/name2#hadoop的name目录路径dfs.data.dir/home/hadoop/data1,/home/hadoop/data2dfs.replication2dfs.name.dir是NameNode持久存储名字空间及事务日志的本地文件系统路径。当这个值是一个逗号分割的目录列表时，nametable数据将会被复制到所有目录中做冗余备份。dfs.data.dir是DataNode存放块数据的本地文件系统路径，逗号分割的列表。当这个值是逗号分割的目录列表时，数据将被存储在所有目录下，通常分布在不同设备上。dfs.replication是数据需要备份的数量，默认是3，如果此数大于集群的机器数会出错。注意：此处的name1、name2、data1、data2目录不能预先创建，hadoop格式化时会自动创建，如果预先创建反而会有问题。c.配置masters和slaves主从结点配置conf/masters和conf/slaves来设置主从结点，注意最好使用主机名，并且保证机器之间通过主机名可以互相访问，每个主机名一行。masters中输入：masterslaves中输入：slaver1slaver2slaver3配置结束，把配置好的hadoop文件夹复制到其他集群的机器中，并且保证上面的配置对于其他机器而言正确，例如：如果其他机器的Java安装路径不一样，要修改conf/hadoop-env.sh$scp-r/home/hadoop/hadoop-0.20.203root@slaver1:/home/hadoop/d.hadoop启动1)格式化一个新的分布式文件系统$cdhadoop-0.20.203 $bin/hadoopnamenode–format查看输出保证分布式文件系统格式化成功执行完后可以到master机器上看到/home/hadoop//name1和/home/hadoop//name2两个目录。在主节点master上面启动hadoop，主节点会启动所有从节点的hadoop。2)启动所有节点启动方式1：$bin/start-all.sh（同时启动HDFS和Map/Reduce）执行完后可以到master（master）和slave（master，slaver1）机器上看到/home/hadoop/hadoopfs/data1和/home/hadoop/data2两个目录。启动方式2：启动Hadoop集群需要启动HDFS集群和Map/Reduce集群。$bin/start-dfs.sh（单独启动HDFS集群）in/start-dfs.sh（单独启动HDFS集群）bin/start-dfs.sh脚本会参照NameNode上${HADOOP_CONF_DIR}/slaves文件的内容，在所有列出的slave上启动DataNode守护进程。在分配的JobTracker上，运行下面的命令启动Map/Reduce：$bin/start-mapred.sh（单独启动Map/Reduce）bin/start-mapred.sh脚本会参照JobTracker上${HADOOP_CONF_DIR}/slaves文件的内容，在所有列出的slave上启动TaskTracker守护进程。 e.关闭所有节点从主节点master关闭hadoop，主节点会关闭所有从节点的hadoop。$bin/stop-all.shHadoop守护进程的日志写入到${HADOOP_LOG_DIR}目录(默认是${HADOOP_HOME}/logs)。4.2文本表示过程的并行化将原始文本数据表示为向量空间模型的步骤包括中文分词、特征选择、特征权重计算，本节将实现这些的算法MapReduce并行化，使文本表示的过程在Hadoop下以并行化的方式更快的计算出来。4.2.1预处理和中文分词并行化本实验的数据采用搜狗实验室所提供的文本分类语料库。该语料库为XML格式的文本数据，所以首先需要对其进行XML解析，从中得到每篇文章的文章内容content和文章分类category，并以键值对的形式作为Map函数的输入。MapReduce过程如下图所示： key：categoryvalue：统计词频后的contentReduce统计词频Map中文分词key：categoryvalue：分词后的contentKey：categoryValue：contentMap阶段：对于输入的键值对，将其中的文本内容content通过linux下管道的方式用中文分词包stanford-segmenter下的segment.sh脚本进行中文分词，将分词后的内容作为新的文本content2并以键值对的形式输出作为Reduce函数的输入。Reduce阶段：输入键值对后对content2中相同的单词合并并且统计每个单词在本篇文章中出现的频率以如下形式输出：，例如：<体育，篮球/5足球/3比赛/2……>。4.2.2特征选择并行化第3.3节介绍了特征选择常用的两种算法，本文使用信息增益法选择特征，并通过MapReduce的方式实现其并行化。上面介绍过了信息增益的公式如下：(4.1)所以需要在MapReduce过程中计算每个类的概率、特征t出现时属于类的概率和特征t没有出现时属于类的概率。Map阶段：将中文分词的MapReduce阶段后输出的键值对：作为本阶段map函数的输入，将每个单词word与类别category的键值对用tab连接后输出。Reduce阶段：上阶段map函数的输出经过Hadoop框架的洗牌（shuffle）和合并（conbiner）后作为reduce函数的输入，把输入的键值对以tab分割后统计每个类别的文章数和总文章数，它们之比即为类别的概率，还要统计每个单词出现时的文章数、不出现时的文章数、每个单词出现时属于类别的文章数、不出现时属于类别的文章数。根据上述这些统计结果可以计算出和，带入式4.1即可算出每个单词（即特征）带来的信息增益IG(T)，将所有特征的信息增益按大到小排序取前100个特征作为向量空间模型中表示文本的向量。 4.2.3TF/IDF计算并行化特征选择算法从所有单词中选出了可以表示文本的具有代表性的特征，然后需要统计这些特征的TF/IDF值给这些特征赋上权重。由第3.4.2节可知，计算特征w对文章d的TF/IDF值需要统计特征w在文章d中出现的词频tf(w,d)、出现过特征w的文档数Dw和总的文档数D，这些数据都可以通过MapReduce统计得到。具体过程如下：Map阶段：将4.2.1节输出的键值对作为输入，读取上节选出的特征对输入的value进行过滤，删除不在特征集的word并按特征集中的特征顺序对value排序后输出。Reduce阶段：合并map函数的输出键值对，并统计特征集中每个特征的Dw、总文档数D，计算出每个特征的IDF值。计算特征w对文档d的TF/IDF值：将map函数统计出的tf(w,d)乘上reduce函数统计出的IDF(w)即为特征w对文档d的TF/IDF值tfidf(w,d)，带入并替换map函数输出结果中的tf得到所有文本的带权重的向量空间表示：。4.3基于朴素贝叶斯文本分类的并行化4.3.1MapReduce实现由3.5.1节可知，求max()即求max(*)，所以在MapReduce过程中需要求出每个类对应每个特征的条件概率、每个类的先验概率，其中即为类中包含特征的文章数与类中的文章数之比。Map阶段：将4.2.1节输出的键值对作为输入，读取上节选出的特征对输入的value进行过滤，删除不在特征集的word并按特征集中的特征顺序对value排序后输出。Reduce阶段：合并map函数的输出键值对，并统计类中包含特征的文章数和类中的文章数，然后计算出每个特征对应每个类的条件概率。在分类阶段时将待分类文本以键值对<行号，文本内容>的格式输入到分类器中，对文本内容进行预处理和中文分词、特征过滤等文本表达后转换成向量空间模型的形式，分别计算属于每个类时其各个特征的条件概率的乘机，最后与类的先验概率相乘，得到结果概率最大的即为所属的类别。 4.3.2算法描述算法一般流程：1.数据的收集：下载搜狗实验室的新闻语料库2.数据的准备：按照中文分词、特征选择的流程进行文本表示3.上传数据：将训练样本上传到HDFS中进行训练4.训练算法：计算各个的独立特征的条件概率即各类的先验概率5.测试算法：计算准确率、召回率和F1值代码实现与示例：trainNB0函数计算各个独立特征在不同类别中的条件概率和各类别的先验概率（为了避免条件概率等于0，将所有词出现的次数初始化为1，并且将分母初始化为2，即p0Num=ones(numWords)p1Num=ones(numWords)p0Denom=2.0p1Denom=2.0）；setOfWords2Vec和bagOfWords2VecMN根据字典形成相应的vector（setOfWords2Vec中的vector中只有0和1，对词出现的次数多少不区分，而bagOfWords2VecMN终的vector则进行了区分）；在classifyNB中进行条件概率计算，进行了一些对数转换。defloadDataSet():postingList=[['my','dog','has','flea','problems','help','please'],['maybe','not','take','him','to','dog','park','stupid'],['my','dalmation','is','so','cute','I','love','him'],['stop','posting','stupid','worthless','garbage'],['mr','licks','ate','my','steak','how','to','stop','him'],['quit','buying','worthless','dog','food','stupid']]classVec=[0,1,0,1,0,1]returnpostingList,classVecdefcreateVocabList(dataSet):vocaSet=set([])fordocindataSet:vocaSet=vocaSet|set(doc)returnlist(vocaSet)defsetOfWords2Vec(vocabList,inputSet):returnVec=[]fordocininputSet:tmpVec=[0]*len(vocabList)forwordindoc:ifwordinvocabList:tmpVec[vocabList.index(word)]=1else: print"theword:%sisnotinmyvacobulary!"%wordreturnVec.append(tmpVec)returnreturnVecdefbagOfWords2VecMN(vocabList,inputSet):returnVec=[]fordocininputSet:tmpVec=[0]*len(vocabList)forwordindoc:ifwordinvocabList:ifwordinvocabList:tmpVec[vocabList.index(word)]+=1else:print"theword:%sisnotinmyvacobulary"%wordreturnVec.append(tmpVec)returnreturnVecdeftrainNB0(trainMatrix,trainCategory):numTrainDocs=len(trainMatrix)numWords=len(trainMatrix[0])pAbusive=sum(trainCategory)/float(numTrainDocs)'''p0Num=zeros(numWords)p1Num=zeros(numWords)'''p0Num=ones(numWords)p1Num=ones(numWords)p0Denom=2.0p1Denom=2.0foriinrange(numTrainDocs):iftrainCategory[i]==1:p1Num+=trainMatrix[i]p1Denom+=sum(trainMatrix[i])else:p0Num+=trainMatrix[i]p0Denom+=sum(trainMatrix[i])p1Vect=p1Num/p1Denom p0Vect=p0Num/p0Denomreturnp0Vect,p1Vect,pAbusivedefclassifyNB(vec2Classify,p0Vec,p1Vec,pClass):p1=sum(vec2Classify*p1Vec)+log(pClass)p0=sum(vec2Classify*p0Vec)+log(1.0-pClass)ifp1>p0:return1else:return0deftestingNB():listOPosts,listClasses=loadDataSet()myVocabList=createVocabList(listOPosts)trainMat=setOfWords2Vec(myVocabList,listOPosts)p0V,p1V,pAb=trainNB0(array(trainMat),array(listClasses))result=[]testSet=[['love','my','dalmation'],['stupid','garbage']]testVec=setOfWords2Vec(myVocabList,testSet)fortestintestVec:tmp_r=classifyNB(test,p0V,p1V,pAb)result.append(tmp_r)foriinrange(len(testSet)):printtestSet[i]print"Theclassofitis:"+str(result[i])testingNB()4.4基于SVM文本分类的并行化4.4.1SVM并行化虽然SVM的分类准确率很高，但是它的训练时间也是最长的。为了加快SVM的训练速度，降低其训练时间，本节设计并实现了基于Hadoop的并行SVM，用以加快SVM的训练速度。设计和实现SVM并行化的过程中最需要考虑的问题是数据集如何划分和迭代停止条件。 由于SVM的训练最终结果实际上是找出训练数据集中所有支持向量，我们可以先对大型训练数据集进行分块，把分块后的小数据集分散到hadoop上各个节点进行训练，通过不断迭代计算每个节点的小数据块的最优解来得到SVM训练算法关于整个大训练数据集的全局最优解，迭代计算的停止条件就是达到全局最优解的时候停止计算。对于每个节点的小数据块我们可以使用常用的SMO算法来进行训练，这样通过各个节点的并行化训练方式可以提高SVM的训练速度，同时又不会明显降低SVM的训练准确率。下面是SVM并行化训练中各个节点数据的迭代过程示意图：图4.4.1SVM并行化训练示意图图4.4.1中显示的是训练样本集合被分为8份的情况,其中TD和SV分别表示分块后的训练数据集(TrainingDataset)和对对应训练数据集作SVM训练得到的支持向量。在第一层中，原始训练样本集被分成8份(TD1-8)，然后分别对每个子样本集合做SVM训练，得到该训练集的支持向量SV，然后把这些支持向量对应的样本两两合并，得到4份新样本集(TD9-12)。如此类推，第三次得到2份新样本集(TD13、TD14)，第四层得到本次迭代的最终样本集(TD15)。此时，如果未达到迭代停止条件，说明之前各子节点在训练中将本应是最终支持向量的样本点删除了，需要将这些删除的样本点通过上述的分布式训练方式训练出新的支持向量，并加入到之前的支持向量结果集中进行训练，判断是否达到停止条件。如果已达到收敛条件，则直接输出分类器模型。否则，继续上述迭代过程。下面通过图解的方式说明在二维训练数据集上各个节点删除非边界样本（即非支持向量）和合并支持向量结果集的过程： 图4.3.2原始训练样本集按图4.4.2是原始样本训练集，按图4.4.3的方式划分为两个子数据集：用☐包括的样本点是子训练数据集1，用O包括的样本点是子训练数据集2，分别对各自进行SVM训练。图4.4.3数据集划分划分出不同的子训练集之后,在各个子训练集上进行训练,得到各自的子支持向量： 图4.4.4子训练集上的支持向量其中，用√表示子训练集1上的支持向量，用×表示子训练集2上的支持向量。将以上两个子训练集训练得到的支持向量合并后进行训练得到一次迭代的训练结果：图4.4.5本次迭代的训练结果将每个子训练样本集训练得到的支持向量合并再训练得到新的支持向量，通过这种方式不断的减少非支持向量来提高SVM的训练速度，这里有几点需要注意：1）在划分数据集的过程中如果采用纯随机的划分方式容易导致当前的一次完整迭代计算不一定能全部得到所有的支持向量，随机划分最严重的情况是有些划分的子集中只有一个类别或者很少的类别，这样的子集在训练的过程就会损失掉一些支持向量甚至根本就得不到支持向量的点。所以需要采用合理的方式划分数据集以避免这种极端情况，例如对原始数据进行正类负类交错的方式预处理数据集，这样可以使正类和负类的训练样本均匀的分部在每个子节点上。2）即使每个类别都能平均的划分到每个子节点还是有可能子训练样本集训练所得到的支持向量漏掉了全局的支持向量的情况，所以还要以迭代的方式从删除的非边界样本中训练出新的支持向量加入到结果集中，迭代的停止条件与SVM训练的停机准则一样，每次迭代使目标函数下降的速率小与一定的精度或者所有的样本点都满足KKT条件。3）上面展示的将数据集划分成多个子训练集进行并行SVM训练是使用一个线性可分的二维数据集来作为例子进行说明，对于本文中的文本分类问题是高维的线性不可分问题，SVM训练需要使用选定的核函数(高斯径向基或其他核函数)来对划分的数据集进行迭代训练，上述基于Hadoop的并行SVM的计算模型对于高维线性不可分的数据仍然是可行的。4.4.3MapReduce实现文本分类任务通常是多分类问题，如本实验的数据采用搜狗实验室所提供的文本分类语料库，该语料库包含财经、 技术、教育、军事、娱乐、运动、 文化、汽车8个类别。由第3.5.2.5节可知SVM用于文本分类的多分类问题时常采用“一对一分类”方法，所以本实验需要训练(8*（8-1）)/2=28个二类分类器，相当于细分为了28个子任务，每个子任务分派到不同的节点上并行训练，可以大大提高SVM模型的训练速度。对于每个子任务来说，分配4个节点来并行训练SVM算法，例如训练“教育”和“运动”两类分类器的子任务，首先进行数据预处理：按照4.2节中的数据预处理方式把格式为XML的原始文本按键值对的方式提取出来，并且在Hadoop中进行分词并将得到所有category为education和sports的文本，然后以行为单位使educaton类的数据和sports的数据交错存储，这样在Hadoop以块为单位上传文本数据到HDFS上的时候就可以保证这两个类别的数据都是均匀的分布在每个子节点上。数据预处理完成后将数据输入Hadoop中，利用自定义的MapReduce函数进行SVM迭代训练。在map阶段输入分块后的子训练样本数据集，对子训练样本使用SMO算法进行训练，找出本节点中的支持向量作为下一阶段的输入数据。然后将map阶段训练出的支持向量集两两合并到reduce函数中继续进行SMO训练，直到所有分片节点汇总到一个reducer中，判断所有训练样本是否满足kkt条件，如果不满足则返回第一层中的map阶段，将上次训练中不是支持向量的样本点进行训练，如此反复迭代下去直到所有的训练样本都满足kkt条件时停止迭代，此时得到的支持向量集合即为最终的支持向量集合。MapReduce迭代过程如下图所示：图4.4.6SVM的单次迭代过程4.4.4基于Hadoop的SVM实现首先分析训练样本数据集Hadoop上的分块和存储。Hadoop的HDFS分布式文件系统是基于数据块的存储，所以需要对原始大数据集进行分块，结合前面介绍的数据集划分的方法，首先确定划分数据块的数目，通过如下方式预处理原始数据集使得每个块上的正负类别样木数目大致相等：因为HDFS对文件的分块操作是按数据的大小而不是按行去划分的，所以我们可以在每一行正类的样本点数据之后紧跟一行负类样本点的数据，这样就可以避免各个子节点上数据块的正负类别数目出现比较大的偏差。预处理完数据集后就可以通过“hadoopdfs–putfile”命令将需要训练的数据集上传到HDFS中，下图为预处理数据的流程： 图4.4.7数据集准备通过上面的流程将数据进行预处理后上传到HDFS中进行SVM训练，考虑到在节点数据合并过程中一般是使用两两进行合并，所以为了使同一层之间的训练结果能进行合并，推荐使用2的幂作为划分数据分块的数目。接下来就是在MapReduce上进行SVM训练，读取使用向量空间模型表示的文本数据，使用上节自定义的map操作和reduce操作对每个节点上的子训练样本进行训练，下图为在hadoop上的SVM训练流程:图4.4.8SVM训练过程在单个节点上的SVM训练计算是使用前面介绍的SMO算法来实现对子训练数据集的训练的，通过SMO算法训练出子训练数据集的支持向量(SV)作为下一层输入。4.4.4算法描述基于Hadoop的SvM训练的算法的伪代码主要由4个部分组成,Hadoop提交job的迭代训练!单次迭代的map操作和reduce操作以及单数据集的SVM训 练算法：Hadoop提交Job的算法伪代码如下:InPut：trainingDatasetOutPut：datasetofSVs(thevertexesofsupportvector)Configuration：SettheconfigurationsofHadoopandthenusingtheseconfigurationtoruntheparallelalgorithmofSVMlayersßcompute_layers(num_blocks)；//thenumberofblockswhicharestoredinHDFSWhile(true)dotimesßlWhile(times<=layers)do……DefineJOB：SettheclassesofmapperandreducerSettheinputandoutputdirectoryofcurrentjobSetthenumberofreducers……times+=2;EndwhileDeletetemporarydirectories;//thestop_conditionisusedtopointthestoppingofwhileloopIf(stop_condition)breakEndwhile在Hadoop子节点上的map运算有两种，一种是处于第一层子节点中的map函数对初始数据集上的训练样本进行SMO训练得到各个数据块的支持向量，而其他节点上的map操作主要是接受上一层两个节点训练出的支持向量汇总后交由reduce函数进行SMO训练。map函数的伪代码如下:InPut：oneblockoftrainingdatasetOutPut：resultsofkey/valueafterthetrainingofSVMIf(keystr!=null&&!keystr.equals(“-1”))then//using-1toidentifytheendofdatasetblocklndexßread_file(key,value);//gettheindexofblockfrominputfileElseifkeyStr.equals(“-1”)then//reachtheendofthisblockoftrainingdataIftimes=l&&totalTimes>1then//readthepreviousiterator’sresultofthewholedataset……svmMapDatasßkey/value; //key/valueisreadfromfileofpreviousofresultEndififtimes>l||times==layersthen……transformthedatasettotheclassofreducer;……//writekey/valuesintocontextandtransformthemintoreducerElse……SVsßtrain_svm(svmMapDatas)；//usingthealgorithmofSVMtotrainthesvmMapDatasand//thensaveintoSVs……EndifEndifmap函数输出的数据经过hadoop框架的洗牌（shuffle）和合并（conbine）操作后，两两合并到一个下一个子节点作为其reducer的输入，reduce函数主要任务也是对输入的样本数据进行SMO训练，并选出这一阶段的支持向量输出。reduce函数的伪代码如下：Input：key/valuesfromthemapfunction’sresultOutput：fileswhichareusedtothenextinputorthefinalresultWhileconditiondo//usingtheflagofconditiontopointtheendofdatasetInsert_intoSet(svmMapDatas,key_value);//insertthedataofkey/valueintothesetofsvmMapDatasfortrainingEndwhileif(!Condition)then//alldataisinsertedintosvmMapDatasandthentrainthem……SVsßtrain_svm(svmMapDatas);//usingthealgorithmofSVMtotrainthesvmMapDatasandthenCurrent_valueßcompute_optimalValue(SVs);//computingtheoptimalvalueofcurrentvaluesofSVs,usingthisvalue//andpreviousvaluetoconfirmwhetherthemainloopcontinuesornot,//thiswayisbasedonthefirststopconditionwhichisintroducedin//chapter3……Endif每个map函数和reduce函数中对数据集的训练算法都使用SMO(序列最小最优化)算法，即每次用启发式方法选择数据集中两个破坏KKT条件最严重的样本点、，更新这两个点的拉格朗日参数、，并不断检测是否满足迭代的停止条件，如果满足则停止计算，并将计算得到的 支持向量点以及对应的拉格朗日参数返回。SMO算法伪代码如下：Input：thedatasetoftrainingdataOutput：thedatasetofSV(supportvector)andtheircoefficientWhiletruedo……Seleetßvertex(,);//selectthebestvertexestoupdatetheircoefficient,//usingtheconditionofKKTUpdate_coefficient(,,,);//updatetheircoefficientifstop_condition//thestopconditionissatisfied,usingthefirststopconditionbreak;……Endwhile从图5-9中可以看出，中间每一层的迭代训练都是从下面一层中特定的选择两个位置的训练结果进行结合进行SVM训练的，在基于Hadoop的设计实现中，通过对每层的每个位置进行相应标号来区分上面一层的SVM训练究竟选择下面一层的哪两个数据，从而避免了一层上多个并行SVM训练数据集选择紊乱的问题。对应的hadoop使用partition函数来进行reduee的区分和选择我们可以简单的除以2就可以将对应编号的数据集传输到对应的reduce:计算节点上进行相应的SVM训练。
