基于Hadoop的Dirichlet樸素貝葉斯文本分類算法

孟海東　肖銀龍　宋宇辰

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

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

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

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

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

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

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

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

2 算法的MapReduce并行化

2.1 文本預(yù)處理Job

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

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

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

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

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

2.2 文本向量化Job

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

（1） 讀取TD文件。

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

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

（4） 統(tǒng)計每個文檔中每個特征詞的詞頻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)計在所有文檔中每個特征詞出現(xiàn)的文檔頻率DF，生成DFCount文件。

（6） 計算出每個特征詞的權(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） 為類別建立索引，每個類別有對應(yīng)的ID，生成LabelIndex文件。

（2） 讀取TFIDFVectors文件，疊加相同類別的文檔的向量Vector_TFIDF，可計算出相同類別的特征詞的權(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，可計算出每個特征詞在所有類中的權(quán)重之和FW，生成FWCount文件；疊加每個類別的所有特征詞的向量Vector_LFW，可計算出每個類中所有特征詞的權(quán)重之和LW，生成LWCount文件。

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

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

2.4 測試分類器Job

測試分類器Job的工作流程為：

（1） 讀取NaiveBayesModel文件，建立NaiveBayesModel對象。

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

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

3 仿真實驗

3.1 實驗環(huán)境

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

3.2 實驗結(jié)果

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

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

取數(shù)據(jù)集的60%作為訓(xùn)練集，其余的40%作為測試集，選擇5個節(jié)點進(jìn)行實驗。參數(shù)[μ]的取值是任意的非負(fù)整數(shù)，當(dāng)取0時相當(dāng)于不采用平滑方法。為了獲得參數(shù)[μ]的最佳取值，對[μ]的取值從0開始逐漸遞增，間隔1 000，進(jì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算法的性能對比

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

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

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

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

實驗結(jié)果如表5所示。

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

3.2.4 不同節(jié)點數(shù)對運行時間的影響

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

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

4 結(jié) 語

本文提出了一種基于Hadoop的Dirichlet樸素貝葉斯文本分類算法，通過引入統(tǒng)計語言建模技術(shù)中的數(shù)據(jù)平滑方法，降低了數(shù)據(jù)稀疏問題對分類性能的影響，同時，由于采用并行計算，提高了對海量數(shù)據(jù)的處理能力，并具有良好的擴展性。實驗結(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].計算機研究與發(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] 搜狗實驗室.互聯(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é)報（自然科學(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.