孟海東　肖銀龍　宋宇辰

摘 要： 針對(duì)當(dāng)前大數(shù)據(jù)環(huán)境下樸素貝葉斯文本分類算法在處理文本分類任務(wù)時(shí)存在的數(shù)據(jù)稀疏以及效率低的問題，提出了一種基于Hadoop的Dirichlet樸素貝葉斯文本分類算法。該算法引入統(tǒng)計(jì)語言建模技術(shù)中的Dirichlet數(shù)據(jù)平滑方法，采用MapReduce編程模型，在Hadoop云計(jì)算平臺(tái)上實(shí)現(xiàn)了算法的并行化。通過實(shí)驗(yàn)對(duì)比分析了該算法與傳統(tǒng)樸素貝葉斯文本分類算法對(duì)大規(guī)模文本數(shù)據(jù)的分類效果。結(jié)果表明，該算法顯著提高了傳統(tǒng)樸素貝葉斯文本分類算法的準(zhǔn)確率、召回率，且具有高效性和易擴(kuò)展性。

關(guān)鍵詞： 文本分類； 云計(jì)算； MapReduce； 樸素貝葉斯文本； 數(shù)據(jù)平滑

中圖分類號(hào)： TN911?34； TP311 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

文本分類技術(shù)是信息檢索與數(shù)據(jù)挖掘領(lǐng)域的核心技術(shù)，主要的算法包括樸素貝葉斯、K最近鄰、神經(jīng)網(wǎng)絡(luò)和支持向量機(jī)等[1]。其中樸素貝葉斯算法在進(jìn)行文本分類時(shí)，假定特征獨(dú)立于類別，簡化了訓(xùn)練和分類過程的計(jì)算，具有運(yùn)行快速、易于實(shí)現(xiàn)的特點(diǎn)，因此成為文本分類中廣為使用的一種方法，吸引了眾多學(xué)者的關(guān)注。文獻(xiàn)[2]提出了一種基于期望最大化（EM）的樸素貝葉斯文本分類算法，提高了對(duì)未標(biāo)注語料的利用率。文獻(xiàn)[3]提出了一種基于局部加權(quán)的樸素貝葉斯文本分類算法，弱化了特征項(xiàng)間獨(dú)立性假設(shè)。文獻(xiàn)[4]將支持樸素貝葉斯文本分類算法同支持向量機(jī)算法相結(jié)合，提高了分類的準(zhǔn)確率。文獻(xiàn)[5]提出了一種基于輔助特征詞的樸素貝葉斯文本分類算法，提高了類條件概率的精確度。文獻(xiàn)[6]提出了一種對(duì)特征詞權(quán)重進(jìn)行高階投票的方法，改善了當(dāng)訓(xùn)練語料不足時(shí)分類器的性能。但是，以上研究存在一定的局限性。一方面，在單機(jī)上運(yùn)行的傳統(tǒng)樸素貝葉斯文本分類算法，由于其自身擴(kuò)展性和計(jì)算能力的限制，在當(dāng)前大數(shù)據(jù)[7]環(huán)境下，難以保證數(shù)據(jù)處理的高效性；另一方面，在文本分類過程中，語言中的大部分詞都屬于低頻詞，難以有一個(gè)足夠大的訓(xùn)練語料能夠包含所有的詞語，因而會(huì)造成數(shù)據(jù)稀疏問題。對(duì)于該問題，很少有學(xué)者進(jìn)行研究。

因此，針對(duì)數(shù)據(jù)稀疏問題，本文借鑒統(tǒng)計(jì)語言建模技術(shù)[8]中的數(shù)據(jù)平滑方法，提出一種Dirichlet樸素貝葉斯文本分類算法，同時(shí)采用MapReduce編程模型[9]，在 Hadoop[10]云計(jì)算平臺(tái)上實(shí)現(xiàn)該算法的并行化。

1 算法的原理及改進(jìn)

1.1 樸素貝葉斯文本分類算法

樸素貝葉斯文本分類算法NB（Naive Bayes）是一種基于概率統(tǒng)計(jì)的學(xué)習(xí)方法。常用的模型包括多變量貝努利模型和多項(xiàng)式模型，二者的計(jì)算粒度不一樣，伯努利模型以文件為粒度，多項(xiàng)式模型以單詞為粒度。本文采用多項(xiàng)式模型[11]。假設(shè)文檔d可由其所包含的特征詞表示，即[d=（w1，w2，…，wv）]，wk為特征詞，[k=1，2，…，v]，v是特征詞的集合，[v]為特征詞的個(gè)數(shù)。同時(shí)，目標(biāo)類別集合數(shù)目確定，[c={c1，c2，…，cm}]，ci是類標(biāo)簽，[i=1，2，][…，m]。由貝葉斯公式可計(jì)算文檔d屬于類別ci的概率為：

2 算法的MapReduce并行化

2.1 文本預(yù)處理Job

文本預(yù)處理Job的工作流程：

（1） 解析輸入語料的相對(duì)路徑Path，將其存放的目錄名作為類名Label。

（2） 采用中文分詞工具對(duì)文檔內(nèi)容進(jìn)行處理。

（3） 處理成貝葉斯模型要求的輸入格式：每行一篇文檔，每篇文檔的格式為，鍵Key為Path，值Value為一篇文檔分詞后的特征詞Feature組成的集合，生成TD（tokenized documents）文件。

文本預(yù)處理Job的輸出文件File及其鍵值對(duì)的表述如表1所示。

2.2 文本向量化Job

文本向量化Job的工作流程如下：

（1） 讀取TD文件。

（2） 統(tǒng)計(jì)所有特征詞的數(shù)目，生成WC（word count）文件。

（3） 讀取上一步生成的WC文件，為每個(gè)特征詞分配惟一的ID，生成Dictionary文件。

（4） 統(tǒng)計(jì)每個(gè)文檔中每個(gè)特征詞的詞頻TF，得到向量Vector_TF，形式如下：（Feature_1_ID：Feature_1_TF，F(xiàn)eature_2_ID：Feature_2_TF，…，F(xiàn)eature_n_ID： Feature_n_TF），生成TFVectors文件。

（5） 統(tǒng)計(jì)在所有文檔中每個(gè)特征詞出現(xiàn)的文檔頻率DF，生成DFCount文件。

（6） 計(jì)算出每個(gè)特征詞的權(quán)重TFIDF，得到向量Vector_TFIDF，形式如下：（Feature_1_ID：Feature_1_TFIDF，F(xiàn)eature_2_ID：Feature_2_TFIDF，…，F(xiàn)eature _

n_ID： Feature_n_TFIDF），生成TFIDFVectors文件。

2.3 訓(xùn)練分類器Job

訓(xùn)練分類器Job的工作流程為：

（1） 為類別建立索引，每個(gè)類別有對(duì)應(yīng)的ID，生成LabelIndex文件。

（2） 讀取TFIDFVectors文件，疊加相同類別的文檔的向量Vector_TFIDF，可計(jì)算出相同類別的特征詞的權(quán)重之和LFW，得到向量Vector_LFW，形式如下：（Feature_1_ID：Feature_1_LFW，F(xiàn)eature_2_ID：Feature_2_LFW，…，F(xiàn)eature_n_ID：Feature_n_LFW），生成LFWVectors文件。

（3） 讀取上一步得到的LFWVectors文件，疊加所有類別的向量Vector_LFW，可計(jì)算出每個(gè)特征詞在所有類中的權(quán)重之和FW，生成FWCount文件；疊加每個(gè)類別的所有特征詞的向量Vector_LFW，可計(jì)算出每個(gè)類中所有特征詞的權(quán)重之和LW，生成LWCount文件。

（4） 讀取之前得到的LFWVectors文件、FWCount文件、LWCount文件，新建一個(gè)二維矩陣，行由所有類別構(gòu)成，列由所有特征詞構(gòu)成，用LFW填充這個(gè)矩陣，然后在此矩陣的最后一行增加一行，填充FW，在此矩陣的走后一列添加一列，填充LW，即可構(gòu)造一個(gè)貝葉斯分類模型，生成NaiveBayesModel文件。

訓(xùn)練分類器Job的輸出文件File及其鍵值對(duì)的表述如表3所示。

2.4 測(cè)試分類器Job

測(cè)試分類器Job的工作流程為：

（1） 讀取NaiveBayesModel文件，建立NaiveBayesModel對(duì)象。

（2） 在NaiveBayesModel中取出相關(guān)參數(shù)，根據(jù)式（12），計(jì)算特征詞的類條件概率，根據(jù)式（3），計(jì)算類先驗(yàn)概率，根據(jù)式（6）計(jì)算文檔對(duì)于所有類的后驗(yàn)概率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文件，取最大的后驗(yàn)概率對(duì)應(yīng)的類別作為該輸入文檔的類別cMAP。

測(cè)試分類器Job的輸出文件File及其鍵值對(duì)的表述如表4所示。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

仿真實(shí)驗(yàn)平臺(tái)是由5個(gè)節(jié)點(diǎn)組成的Hadoop集群，其中1臺(tái)為主節(jié)點(diǎn)，其余為從節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)的具體配置如下：4×1.80 GHz CPU，16 GB內(nèi)存，300 GB硬盤，操作系統(tǒng)為CentOS 6.5，Hadoop版本選用1.2.1。實(shí)驗(yàn)數(shù)據(jù)來源于搜狗實(shí)驗(yàn)室提供的文本分類語料庫SogouC[14]。數(shù)據(jù)集包含10個(gè)類別，每個(gè)類別有8 000篇文檔，數(shù)據(jù)集大小約為277 MB。中文分詞工具采用mmseg4j中文分詞器。

3.2 實(shí)驗(yàn)結(jié)果

其中：TPi表示測(cè)試文檔集中正確分類到類別ci的文檔數(shù)；FPi表示測(cè)試文檔集中錯(cuò)誤分類到類別ci的文檔數(shù)；FNi表示測(cè)試文檔集中屬于類別ci但被錯(cuò)誤分類到別的類別的文檔數(shù)。

3.2.1 DNB算法的參數(shù)選擇

取數(shù)據(jù)集的60%作為訓(xùn)練集，其余的40%作為測(cè)試集，選擇5個(gè)節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)。參數(shù)[μ]的取值是任意的非負(fù)整數(shù)，當(dāng)取0時(shí)相當(dāng)于不采用平滑方法。為了獲得參數(shù)[μ]的最佳取值，對(duì)[μ]的取值從0開始逐漸遞增，間隔1 000，進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖1所示。

從圖1可以看出，當(dāng)參數(shù)[μ]的取值從0遞增到3 000的過程中，準(zhǔn)確率和召回率都在大幅增加，而參數(shù)[μ]的取值在3 000之后的遞增過程中，準(zhǔn)確率和召回率或增或減，幅度都較平緩且趨于穩(wěn)定。因此選擇參數(shù)[μ]的取值為3 000。

3.2.2 DNB算法與NB算法的性能對(duì)比

取數(shù)據(jù)集的60%作為訓(xùn)練集，其余的40%作為測(cè)試集，選擇5個(gè)節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖2、圖3所示。

從圖2、圖3可以看出，除個(gè)別類外，改進(jìn)后的DNB算法的準(zhǔn)確率和召回率都優(yōu)于NB算法，說明了改進(jìn)后的DNB算法提高了分類性能。

3.2.3 不同數(shù)據(jù)集對(duì)加速比的影響

對(duì)數(shù)據(jù)集進(jìn)行有返還抽樣（sampling with replacement），分別構(gòu)造100 MB，200 MB，400 MB，800 MB，1 600 MB五個(gè)不同大小的新數(shù)據(jù)集，然后分別從5個(gè)新數(shù)據(jù)集中取60%作為訓(xùn)練集，其余的40%作為測(cè)試集，依次選擇1個(gè)和5個(gè)節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)。

實(shí)驗(yàn)結(jié)果如表5所示。

從表5可以看出，當(dāng)數(shù)據(jù)集較小時(shí)，加速比[16]并不理想。這是因?yàn)楫?dāng)數(shù)據(jù)集較小時(shí)，處理數(shù)據(jù)的時(shí)間較少，節(jié)點(diǎn)之間通信消耗的時(shí)間相對(duì)較多。但是，隨著數(shù)據(jù)集的不斷增大，處理數(shù)據(jù)的時(shí)間遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)之間通信消耗的時(shí)間，因此加速比有了顯著提升，同時(shí)說明了本文算法適用于大數(shù)據(jù)的處理。

3.2.4 不同節(jié)點(diǎn)數(shù)對(duì)運(yùn)行時(shí)間的影響

從1 600 MB的數(shù)據(jù)集中取60%作為訓(xùn)練集，其余的40%作為測(cè)試集，依次選擇1～5個(gè)節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖4所示。

從圖4可以看出，運(yùn)行時(shí)間隨節(jié)點(diǎn)數(shù)的增加而顯著減小，說明了本文算法具有良好的擴(kuò)展性和高效性。

4 結(jié) 語

本文提出了一種基于Hadoop的Dirichlet樸素貝葉斯文本分類算法，通過引入統(tǒng)計(jì)語言建模技術(shù)中的數(shù)據(jù)平滑方法，降低了數(shù)據(jù)稀疏問題對(duì)分類性能的影響，同時(shí)，由于采用并行計(jì)算，提高了對(duì)海量數(shù)據(jù)的處理能力，并具有良好的擴(kuò)展性。實(shí)驗(yàn)結(jié)果表明，本文算法可以顯著提高傳統(tǒng)樸素貝葉斯文本分類算法的性能和效率，適用于海量文本數(shù)據(jù)的處理。

參考文獻(xiàn)

[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] 丁國棟，白碩，王斌.文本檢索的統(tǒng)計(jì)語言建模方法綜述[J].計(jì)算機(jī)研究與發(fā)展，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] 搜狗實(shí)驗(yàn)室.互聯(lián)網(wǎng)語料庫[EB/OL].[2015?07?06]. http：//www.sougou.com/labs/dl/c.html.

[15] 饒麗麗，劉雄輝，張東站.基于特征相關(guān)的改進(jìn)加權(quán)樸素貝葉斯分類算法[J].廈門大學(xué)學(xué)報(bào)（自然科學(xué)版），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.