基于Hadoop的Dirichlet朴素贝叶斯文本分类算法
2016-03-15孟海东肖银龙宋宇辰
孟海东 肖银龙 宋宇辰
摘 要： 针对当前大数据环境下朴素贝叶斯文本分类算法在处理文本分类任务时存在的数据稀疏以及效率低的问题，提出了一种基于Hadoop的Dirichlet朴素贝叶斯文本分类算法。该算法引入统计语言建模技术中的Dirichlet数据平滑方法，采用MapReduce编程模型，在Hadoop云计算平台上实现了算法的并行化。通过实验对比分析了该算法与传统朴素贝叶斯文本分类算法对大规模文本数据的分类效果。结果表明，该算法显著提高了传统朴素贝叶斯文本分类算法的准确率、召回率，且具有高效性和易扩展性。
关键词： 文本分类； 云计算； MapReduce； 朴素贝叶斯文本； 数据平滑
中图分类号： TN911?34； TP311 文献标识码： A 文章编号： 1004?373X（2016）04?0029?05
Abstract： When applied to deal with text classification task under the circumstance of big data， Naive Bayes text classification algorithm is always suffered from the data sparse and inefficiency problem. To solve this problem， a Dirichlet Naive Bayes text classification algorithm based on Hadoop is proposed， in which the Dirichlet data smoothing method in statistical language modeling technology is adopted and MapReduce programming model is used to realize the parallelization of the algorithm in Hadoop cloud computing environment. The contrastive analysis on the classification effect of this algorithm and traditional Naive Bayes text classification algorithm for large?scale text data was made through experiments. The experimental results show this algorithm significantly improves the precision rate and recall rate of the traditional Naive Bayes text classification algorithm， and has high efficiency and easy expansibility.
Keywords： text classification； cloud computing； MapReduce； Naive Bayes text； data smoothing
0 引 言
文本分类技术是信息检索与数据挖掘领域的核心技术，主要的算法包括朴素贝叶斯、K最近邻、神经网络和支持向量机等[1]。其中朴素贝叶斯算法在进行文本分类时，假定特征独立于类别，简化了训练和分类过程的计算，具有运行快速、易于实现的特点，因此成为文本分类中广为使用的一种方法，吸引了众多学者的关注。文献[2]提出了一种基于期望最大化（EM）的朴素贝叶斯文本分类算法，提高了对未标注语料的利用率。文献[3]提出了一种基于局部加权的朴素贝叶斯文本分类算法，弱化了特征项间独立性假设。文献[4]将支持朴素贝叶斯文本分类算法同支持向量机算法相结合，提高了分类的准确率。文献[5]提出了一种基于辅助特征词的朴素贝叶斯文本分类算法，提高了类条件概率的精确度。文献[6]提出了一种对特征词权重进行高阶投票的方法，改善了当训练语料不足时分类器的性能。但是，以上研究存在一定的局限性。一方面，在单机上运行的传统朴素贝叶斯文本分类算法，由于其自身扩展性和计算能力的限制，在当前大数据[7]环境下，难以保证数据处理的高效性；另一方面，在文本分类过程中，语言中的大部分词都属于低频词，难以有一个足够大的训练语料能够包含所有的词语，因而会造成数据稀疏问题。对于该问题，很少有学者进行研究。
因此，针对数据稀疏问题，本文借鉴统计语言建模技术[8]中的数据平滑方法，提出一种Dirichlet朴素贝叶斯文本分类算法，同时采用MapReduce编程模型[9]，在 Hadoop[10]云计算平台上实现该算法的并行化。
1 算法的原理及改进
1.1 朴素贝叶斯文本分类算法
朴素贝叶斯文本分类算法NB（Naive Bayes）是一种基于概率统计的学习方法。常用的模型包括多变量贝努利模型和多项式模型，二者的计算粒度不一样，伯努利模型以文件为粒度，多项式模型以单词为粒度。本文采用多项式模型[11]。假设文档d可由其所包含的特征词表示，即[d=（w1，w2，…，wv）]，wk为特征词，[k=1，2，…，v]，v是特征词的集合，[v]为特征词的个数。同时，目标类别集合数目确定，[c={c1，c2，…，cm}]，ci是类标签，[i=1，2，][…，m]。由贝叶斯公式可计算文档d属于类别ci的概率为：
2 算法的MapReduce并行化
2.1 文本预处理Job
文本预处理Job的工作流程：
（1） 解析输入语料的相对路径Path，将其存放的目录名作为类名Label。
（2） 采用中文分词工具对文档内容进行处理。
（3） 处理成贝叶斯模型要求的输入格式：每行一篇文档，每篇文档的格式为
文本预处理Job的输出文件File及其键值对的表述如表1所示。
2.2 文本向量化Job
文本向量化Job的工作流程如下：
（1） 读取TD文件。
（2） 统计所有特征词的数目，生成WC（word count）文件。
（3） 读取上一步生成的WC文件，为每个特征词分配惟一的ID，生成Dictionary文件。
（4） 统计每个文档中每个特征词的词频TF，得到向量Vector_TF，形式如下：（Feature_1_ID：Feature_1_TF，Feature_2_ID：Feature_2_TF，…，Feature_n_ID： Feature_n_TF），生成TFVectors文件。
（5） 统计在所有文档中每个特征词出现的文档频率DF，生成DFCount文件。
（6） 计算出每个特征词的权重TFIDF，得到向量Vector_TFIDF，形式如下：（Feature_1_ID：Feature_1_TFIDF，Feature_2_ID：Feature_2_TFIDF，…，Feature _
n_ID： Feature_n_TFIDF），生成TFIDFVectors文件。
2.3 训练分类器Job
训练分类器Job的工作流程为：
（1） 为类别建立索引，每个类别有对应的ID，生成LabelIndex文件。
（2） 读取TFIDFVectors文件，叠加相同类别的文档的向量Vector_TFIDF，可计算出相同类别的特征词的权重之和LFW，得到向量Vector_LFW，形式如下：（Feature_1_ID：Feature_1_LFW，Feature_2_ID：Feature_2_LFW，…，Feature_n_ID：Feature_n_LFW），生成LFWVectors文件。
（3） 读取上一步得到的LFWVectors文件，叠加所有类别的向量Vector_LFW，可计算出每个特征词在所有类中的权重之和FW，生成FWCount文件；叠加每个类别的所有特征词的向量Vector_LFW，可计算出每个类中所有特征词的权重之和LW，生成LWCount文件。
（4） 读取之前得到的LFWVectors文件、FWCount文件、LWCount文件，新建一个二维矩阵，行由所有类别构成，列由所有特征词构成，用LFW填充这个矩阵，然后在此矩阵的最后一行增加一行，填充FW，在此矩阵的走后一列添加一列，填充LW，即可构造一个贝叶斯分类模型，生成NaiveBayesModel文件。
训练分类器Job的输出文件File及其键值对的表述如表3所示。
2.4 测试分类器Job
测试分类器Job的工作流程为：
（1） 读取NaiveBayesModel文件，建立NaiveBayesModel对象。
（2） 在NaiveBayesModel中取出相关参数，根据式（12），计算特征词的类条件概率，根据式（3），计算类先验概率，根据式（6）计算文档对于所有类的后验概率PP（posterior probability），得到向量Vector_PP，形式如下：（Label_1_ID：Label_1_PP，Label_2_ID：Label_2_ PP，…，Label_n_ID：Label_n_PP）。生成Result文件。
（3） 读取第（2）步得到的Result文件，取最大的后验概率对应的类别作为该输入文档的类别cMAP。
测试分类器Job的输出文件File及其键值对的表述如表4所示。
3 仿真实验
3.1 实验环境
仿真实验平台是由5个节点组成的Hadoop集群，其中1台为主节点，其余为从节点。每个节点的具体配置如下：4×1.80 GHz CPU，16 GB内存，300 GB硬盘，操作系统为CentOS 6.5，Hadoop版本选用1.2.1。实验数据来源于搜狗实验室提供的文本分类语料库SogouC[14]。数据集包含10个类别，每个类别有8 000篇文档，数据集大小约为277 MB。中文分词工具采用mmseg4j中文分词器。
3.2 实验结果
其中：TPi表示测试文档集中正确分类到类别ci的文档数；FPi表示测试文档集中错误分类到类别ci的文档数；FNi表示测试文档集中属于类别ci但被错误分类到别的类别的文档数。
3.2.1 DNB算法的参数选择
取数据集的60%作为训练集，其余的40%作为测试集，选择5个节点进行实验。参数[μ]的取值是任意的非负整数，当取0时相当于不采用平滑方法。为了获得参数[μ]的最佳取值，对[μ]的取值从0开始逐渐递增，间隔1 000，进行实验。实验结果如图1所示。
从图1可以看出，当参数[μ]的取值从0递增到3 000的过程中，准确率和召回率都在大幅增加，而参数[μ]的取值在3 000之后的递增过程中，准确率和召回率或增或减，幅度都较平缓且趋于稳定。因此选择参数[μ]的取值为3 000。
3.2.2 DNB算法与NB算法的性能对比
取数据集的60%作为训练集，其余的40%作为测试集，选择5个节点进行实验。实验结果如图2、图3所示。
从图2、图3可以看出，除个别类外，改进后的DNB算法的准确率和召回率都优于NB算法，说明了改进后的DNB算法提高了分类性能。
3.2.3 不同数据集对加速比的影响
对数据集进行有返还抽样（sampling with replacement），分别构造100 MB，200 MB，400 MB，800 MB，1 600 MB五个不同大小的新数据集，然后分别从5个新数据集中取60%作为训练集，其余的40%作为测试集，依次选择1个和5个节点进行实验。
实验结果如表5所示。
从表5可以看出，当数据集较小时，加速比[16]并不理想。这是因为当数据集较小时，处理数据的时间较少，节点之间通信消耗的时间相对较多。但是，随着数据集的不断增大，处理数据的时间远远大于节点之间通信消耗的时间，因此加速比有了显著提升，同时说明了本文算法适用于大数据的处理。
3.2.4 不同节点数对运行时间的影响
从1 600 MB的数据集中取60%作为训练集，其余的40%作为测试集，依次选择1～5个节点进行实验。实验结果如图4所示。
从图4可以看出，运行时间随节点数的增加而显著减小，说明了本文算法具有良好的扩展性和高效性。
4 结 语
本文提出了一种基于Hadoop的Dirichlet朴素贝叶斯文本分类算法，通过引入统计语言建模技术中的数据平滑方法，降低了数据稀疏问题对分类性能的影响，同时，由于采用并行计算，提高了对海量数据的处理能力，并具有良好的扩展性。实验结果表明，本文算法可以显著提高传统朴素贝叶斯文本分类算法的性能和效率，适用于海量文本数据的处理。
参考文献
[1] CROFT Bruce， LAFFERTY John. Language modeling for information retrieval [M]. Germany： Springer Science & Business Media， 2010.
[2] HE J， ZHANG Y， LI X， et al. Learning naive Bayes classifiers from positive and unlabelled examples with uncertainty [J]. International journal of systems science， 2012， 43（10）： 1805?1825.
[3] JIANG L， CAI Z， ZHANG H， et al. Naive Bayes text classifiers： a locally weighted learning approach [J]. Journal of experimental & theoretical artificial intelligence， 2013， 25（2）： 273?286.
[4] WANG S， MANNING C D. Baselines and bigrams： simple， good sentiment and topic classification [C]// Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics. Stroudsburg： Association for Computational Linguistics， 2012， 2： 90?94.
[5] ZHANG W， GAO F. An improvement to Naive Bayes for text classification [J]. Procedia engineering， 2011， 15（3）： 2160?2164.
[6] GANIZ M C， GEORGE C， POTTENGER W M. Higher order Naive Bayes： a novel non?IID approach to text classification [J]. IEEE transactions on knowledge and data engineering， 2011， 23（7）： 1022?1034.
[7] DOBRE C， XHAFA F. Parallel programming paradigms and frameworks in big data era [J]. International journal of parallel programming， 2014， 42（5）： 710?738.
[8] 丁国栋，白硕，王斌.文本检索的统计语言建模方法综述[J].计算机研究与发展，2015，43（5）：769?776.
[9] LEE K H， LEE Y J， CHOI H， et al. Parallel data processing with MapReduce： a survey [J]. Sigmod record， 2012， 40（4）： 11?20.
[10] Apache Hadoop. Hadoop [EB/OL]. [2015?05?04]. http：//hadoop.apache.org.
[11] PUURULA A. Combining modifications to multinomial Naive Bayes for text classification [J]. Information retrieval technology， 2012， 7675： 114?125.
[12] YATSKO V， DIXIT S， AGRAWAL A J， et al. TFIDF revisited [J]. Intelligence， 2013， 16（4）： 2?11.
[13] WANG X. Zipf′s law and the frequency of characters or words of Oracles [J]. Arxiv preprint arxiv， 2014， 14（4）： 412?418.
[14] 搜狗实验室.互联网语料库[EB/OL].[2015?07?06]. http：//www.sougou.com/labs/dl/c.html.
[15] 饶丽丽，刘雄辉，张东站.基于特征相关的改进加权朴素贝叶斯分类算法[J].厦门大学学报（自然科学版），2012，51（4）：682?685.
[16] BAUER R， DELLING D， WAGNER D. Experimental study of speed up techniques for timetable information systems [J]. Networks， 2011， 57（1）： 38?52.
