潘俊辉 王 辉 张 强 王浩畅

（东北石油大学 大庆 163318）

1 引言

随着网上资源的爆炸式增长，在给用户带来便利的同时，也产生了海量的数据，而如何对这些海量数据进行有效的分类，在现实生活中有着非常重要的作用。目前文本分类技术能够准确地对文本进行分类，从而得到有用的分类信息［1］。针对目前互联网上的海量数据，传统的文本分类方法在时间和空间开销上都急剧增长，而分布式平台Hadoop［2］中的MapReduce和HDFS［3］的出现，极大地提高了海量数据的存储和处理效率，并且对文本分类算法处理海量数据和进行文本分类的并行化研究均具有重要的意义。

目前，国内一些学者对Hadoop平台并行实现和进行文本分类做了相应的研究，如向小军等利用Hadoop平台实现了海量数据下的文本分类的并行化处理［4］；江小平，李成华等在云计算环境下，提出了一种改进的朴素贝叶斯的文本分类算法，通过并行化处理的方式，极大地提高了分类的效率［5］；周婷等使用Hadoop平台实现并行化的K近邻聚类算法的改进［6］；国外的C-TChu等人通过使用MapRe⁃duce对支持向量机实现了并行化的处理［7］；Spiros Papaimitriou等学者在MapReduce模型的基础上提出了一种分布式的聚类方法，该方法可高效地处理海量数据［8］。

针对现有的文本特征选择方法所存在的不足，本文提出了类别相关度算法（CCA）。对于海量数据，类别相关度算法在单机环境下表现的没有优势，由于Hadoop平台具有并行化处理的能力，因此首先并行化分析了文本分类的过程，然后对其各个阶段采用并行化编程加以实现，最后通过实验将Hadoop平台下的文本分类的优化算法与传统算法在单机环境下进行了对比分析，实验结果表明并行环境下优化的算法在运行时间上有极大的提高。

2 文本分类及Hadoop平台

2.1 文本分类

文本分类的过程可表示为一个映射过程，该映射过程可用公式f：A→B表示，其中A为待分类的文本集合，而B则是分类体系中的类别集合［10］。该数学公式非常直观地表示出文本分类的过程，就是将待分类的文本集合映射到已有的类别集合中去。

2.2 Hadoop开源平台

Hadoop［11］开源平台主要由HDFS（Hadoop Dis⁃tributed File System，分布式文件系统）和MapRe⁃duce编程框架组成。

2.2.1 HDFS

HDFS是一种分布式的文件系统，主要的工作就是以分布式的形式存储大规模的海量数据。HDFS中包含两类节点，分别称之为名称节点（Na⁃meNode）和数据节点（DataNode）。其中，NameNode主要负责分布式文件系统的命名空间，在其中保存了两个核心的数据结构，即FsImage和EditLog。DataNode则是HDFS的工作节点，主要负责数据的存储和读取，它会根据客户端或者NameNode的调度来进行数据的存储和检索，并向NameNode定期发送自己所存储的块的列表［12～14］。

2.2.2 MapReduce

MapReduce的核心是Map函数和Reduce函数，这两个函数都是以作为输入，按一定的映射规则转换成一个或一批进行输出。通常存储在HDFS中的数据会被分割为相互独立的数据块，然后交给Map对其进行并行处理，而Map的输出接着会成为Reduce的输入，接着执行Reduce计算得到最终结果，并存入到HDFS［12～14］。

3 Hadoop平台下实现文本分类的优化算法

针对现有的文本特征选择方法所存在的不足，提出一种类别相关度特征选择算法，该算法在单机环境下表现的没有优势，但由于Hadoop平台具有并行化处理的能力，因此首先并行化分析了文本分类的过程，然后对其各个阶段采用并行化编程加以实现，包括自定义文本输入的格式、文本分词、TFIDF、特征选择方法CCA、向量空间模型构建和文本分类。文中在最后通过实验将Hadoop平台下的文本分类的优化算法与传统算法在单机环境下进行了对比分析，实验结果表明并行环境下优化的算法在执行时间上有很大的提高。

3.1 自定义文本输入格式

由于文本分类后的文件要放在指定的类别文件夹中，这会导致分类后的文件很小，但文件量增多，而Hadoop平台主要是以流式访问的形式处理大文件，如果以这种方式处理大量的几KB的小文件则存在弊端，不仅导致分词效率降低，而且严重影响Hadoop平台的性能。由此，本文在进行分片时未采用默认的分块大小，而是将所需的参数作为分片大小的最小值和最大值。然后重新继承自定义输入格式类从而确保每个文件只分配给一个分片［15］。

3.2 并行化实现文本分词

Hadoop是基于Java实现的，通过对常用的几种分词工具进行对比分析，本文采用庖丁解牛分词工具进行文本分词。该作业中Mapper的输入是，而 输 出 为，该阶段的主要工作是分词，把分词的信息附加到Key中，Map阶段的伪代码可表示为

而Reducer的输入是，输出为，该阶段的伪代码可表示为如下：

3.3 并行化实现TFIDF

本文采用TFIDF计算特征词的权重，如在海量数据集中计算量大且效率低，本文采用MapReduce并行化实现TFIDF的计算，通过MapReduce实现需要三个作业即可完成。其中第二作业的Map阶段和Reduce阶段的可分别表示为

3.4 并行化实现特征选择算法CCA

为了得到特征词的评估值，本文所提出的特征选择方法CCA需三个变量，由此并行化实现CCA算法时应由三个作业完成。其中第一个作业用于fd（ti，Cj）的计算，第二个作业则采用特征选择算法中的评估函数计算得到每个类别对应的特征值，而最后一个作业则会将排序后的前n个特征词选择出来。本文在采用MapReduce完成CCA时，通过将并行化实现TFIDF中的输出文件作为CCA的输入文件。其中并行化实现CCA中的第二个作业可通过使用CCA特征选择评估函数计算出特征词在每个类中的特征值。该作业的Map和Reduce可分别表示为

3.5 并行化实现向量空间模型VSM构建

并行化实现VSM只需要构建一个称之为Vec⁃torDriver的MapReduce作业即可实现。其中在并行化实现TFIDF阶段得到的输出文件作为Vector⁃Driver的输入文件进行工作。其中Map阶段的工作是分离出词和文件名，接着将分离得到的词与特征词表进行对比，如果该词存在于特征词表中，则重置value的值，用该词与其TFIDF值组成新的val⁃ue值。该阶段的伪代码为

Map的输出作为Reduce的输入进行工作，Re⁃duce的工作则是根据相同的文件名统计出词与TFIDF复合键的列表。该阶段的伪代码为

3.6 并行化实现分类

本文在实现文本分类时采用的是KNN分类算法，其优点在于其计算量主要集中在测试阶段，在测试阶段用于计算文本的相似度由此选出最近的K个类别，最后把次数最多的类别作为测试文本的类别。因此根据KNN的算法思想，本文在并行化实现文本分类时可通过一个MapReduce作业完成。

Map的 输 入 为，输 出则为，该阶段主要是得到训练文本的ClassLabel，计算出相似度，最后选择出最近的K个文本输出。该阶段的伪代码可表示为

Reduce阶段的输入为，输出则为，该阶段主要是统计处得到K个文本分别出现的次数，次数最多将作为测试文本的类别。伪代码为

4 实验及分析

本文实验通过采用4台同构的计算机搭建Ha⁃doop集群，其中使用1台机器作为集群中的主节点，剩下的3台则用来作为从节点。特征选择算法使用的是改进的CCA，分类算法采用KNN方法，本文的实验分别在节点个数为1、2、3、4的情况下进行，实验中分别对分类精度和时间进行了比较。

表1给出了串行和并行环境下五类文本的在分类性能为查准率、召回率及F1度量上的实验对比分析结果。由表1可见，在其他条件均相同的情况下，当采用KNN算法对同一数据集进行分类时，Hadoop并行环境下和单机环境下的各个类别的文本分类性能都是相同的。

表1 分类性能实验对比分析结果

表2分别给出了采用KNN对文本进行分类时单机与Hadoopp环境下执行时间对比分析结果。

由表2可见，单节点时Hadoop下消耗的时间不但没有减少，反而比单机下所需时间还要多，原因是其运行作业时也会耗费时间。而当节点个数逐步增加时，Hadoop上执行所需时间却在逐渐减少，且明显小于单机环境所需时间。实验结果表明，改进后的特征选择算法CCA在并行环境下的进行文本分类时所需时间会随着节点个数的增多逐渐减少，且远远小于单机所需时间。

表2 单机与Hadoopp下执行时间对比分析结果

5 结语

本文首先介绍了文本分类和Hadoop开源云平台相关知识，针对文本分类中特征选择阶段对文本分类性能影响有很大影响的缺点，提出了一种改进的特征选择算法，同时根据Hadoop平台在海量数据存储和处理方面所具有的优点，利用MapReduce的并行编程框架和HDFS分布式存储系统对文本分类的各个阶段实现了并行化编程。最后通过实验将Hadoop平台下的文本分类的优化算法与传统的单机运行环境下的文本分类算法进行了对比分析，实验结果表明，改进后的方法可有效提高文本分类的时间。