基于MapReduce 的樸素貝葉斯算法文本分類方法

張晨躍，劉黎志，鄧開巍，劉 杰

智能機器人湖北省重點實驗室（武漢工程大學(xué)），湖北 武漢 430205

近年來，隨著網(wǎng)絡(luò)的迅速發(fā)展和大數(shù)據(jù)時代的到來［1-3］，文本數(shù)目也不斷增多。面對巨大的數(shù)據(jù)量，需要使用恰當(dāng)?shù)姆椒▽ξ谋具M行分類。樸素貝葉斯算法以其可靠的數(shù)學(xué)基礎(chǔ)成為最主要的分類算法之一。由于其依據(jù)各個條件相互獨立，而各特征詞之間往往具有一定聯(lián)系，所以特征項加權(quán)［4-5］已成為重要的研究內(nèi)容。詞頻-逆文本頻率指數(shù)（term frequency-inverse document frequency，TF-IDF）［6-7］是文本分類中常用的特征權(quán)重算法，突出特征詞在類內(nèi)和類間的分布也有助于提升算法性能。本文選取多項式樸素貝葉斯算法（naive bayes，NB），在Hadoop［8］集群上并行處理文本數(shù)據(jù)，實現(xiàn)對文本的分類，通過實驗驗證了在該集群上設(shè)計的并行化樸素貝葉斯分類方法能夠展現(xiàn)出良好的性能。

1 相關(guān)研究

1.1 樸素貝葉斯分類算法

樸素貝葉斯算法［9-10］假設(shè)各特征之間是相互獨立的，是一種有效的分類方法。常用的模型為多項式模型和伯努利模型，本文采用多項式模型，假如待分類的文本特征項為X( x1,x2,…,xn)，類別集合為C( c1,c2,…,cm)。該算法以詞條在ca類與cb類之間相互獨立為前提，計算出詞條屬于每類文檔的概率P( cm|X )，以概率最大所在類別作為預(yù)測文檔所屬的類別cm。多項式樸素貝葉斯計算公式如下所示：

其中，P(cj)為新文本屬于cj類的概率；P( xk|cj)為cj類中包含詞條xk的概率。

其中，Sj為類cj下的詞語數(shù)目，S 為所有類下的詞語數(shù)目。

為了防止特征詞xk在類別cj中可能出現(xiàn)零次，導(dǎo)致零概率問題，一般采取以下解決方式：

1.2 卡方特征選擇

由于在預(yù)處理階段所篩選的詞語維度較高，需要專門進行特征選擇，得出區(qū)分度高而維度較小的特征詞［11］集合。本文用χ2統(tǒng)計［12］的方法進行特征選擇。該方法假設(shè)兩個樣本之間互不關(guān)聯(lián)，卡方值大小決定了兩者偏離程度的大小?？ǚ街翟酱?，代表特征越明顯。該方法計算公式如下：

其中，N 為文檔數(shù)量，k 代表特征項，c 代表類別。B為非類別c 中包含特征項k 的文本總數(shù)，C 為c 類中不包含特征項k 的文本總數(shù)，A 為c 類中包含特征項k 的文本總數(shù)，D 為非類別c 中不包含特征項k的文本總數(shù)。

1.3 TF-IDF 權(quán)重

TF-IDF［13-14］表示詞頻-逆文檔頻率，TF 表示詞頻，IDF 表示逆文檔頻率。在一篇文章中，假如一個詞語的TF 高，它在別的文檔中又很少出現(xiàn)，那么該詞語能較好地代表這一類文章。其表達式為：

其中，Wdt代表特征項t 在文檔d 中所占權(quán)重，fdt代表特征項t 在文檔d 中的詞頻，N 代表所有文檔數(shù)目，nt代表有多少文檔含有特征項t。但在實際計算的過程中，假如特征項出現(xiàn)的文檔數(shù)為0，分母為0，因此，可以把分母加1，即

1.4 MapReduce 編程框架

MapReduce［15］的核心思想是由許多分節(jié)點去處理大規(guī)模數(shù)據(jù)，這些分節(jié)點由一個主節(jié)點統(tǒng)一來管理。將各分節(jié)點的處理結(jié)果進行整理，就可以得到最終的結(jié)果。Map 和Reduce 是該框架的兩個主要部分。其在< key,value >形式的鍵值對上工作。由于NB 算法假設(shè)各特征項之間是相互獨立的，因此該算法是可以通過并行實現(xiàn)的。

2 樸素貝葉斯算法并行化

將NB 的并行化過程分為：特征選擇、權(quán)重計算、模型訓(xùn)練和測試4 個階段。首先用中文分詞工具jieba 對文本內(nèi)容進行分詞預(yù)處理，并通過本文構(gòu)建的中文停用詞表去掉無意義詞語，計算同一類別的詞頻之和，并過濾掉詞頻過高或過低的詞，最終得到totalnews 和wordcount兩個文件。

2.1 特征選擇

特征選擇Job 的工作流程：

1）輸入totalnews 和wordcount 文件，讀取分布式文件系統(tǒng)中的內(nèi)容；

2）Map 階段，順序讀取兩個文件，數(shù)據(jù)分別寫入words_list 和news_list 元組。定義flag，通過for循環(huán)判斷每個詞在每類文本中是否出現(xiàn)，出現(xiàn)flag為1，否則為0，求出N 和每個特征項xk的A，B，C，D，利用公式（5）計算chi，再通過sqrt 對其進行開方，按照鍵值對的形式溢出到HDFS 本地磁盤中保存為一個文件；

3）所有分片輸出的鍵值對會在Shuffle 過程按照s_CHI 大小降序排序、歸并處理，Reduce 階段接收排序和歸并結(jié)果繼續(xù)處理。整理結(jié)果會按照“”的鍵值對形式進行輸出；

4）Reduce 階段，獲得上一步輸出內(nèi)容，每類選取top 前V 作為該類最終特征詞，過濾掉重復(fù)的xk，得到最終的全局特征項X（x1，x2，…，xn），以鍵值對形式保存到CHI 文件并輸出，wordID 為特征詞ID，xk為特征詞。

2.2 權(quán)重計算

權(quán)重計算Job 的工作流程：

1）輸入totalnews 和CHI 文件，讀取分布式文件系統(tǒng)中的內(nèi)容；

2）Map 階段，順序讀取兩個文件，數(shù)據(jù)分別寫入words_list 和news_list 元組。利用公式（7）首先計 算 出xk的TF 和IDF 值，按 照< wordID_xk，newCategory_TF_IDF> 鍵值對的形式溢出到HDFS 本地磁盤中保存為一個文件；

3）Shuffle 過程根據(jù)相同的key 值進行歸并，Reduce 階段接收歸并結(jié)果繼續(xù)處理。整理結(jié)果會按照“< wordID_xk，newCategory_TF_IDF>”的鍵值對形式進行輸出；

4）Reduce 階段，獲得上一步輸出內(nèi)容，計算每個xk在每條文本中的權(quán)重值，以形式保存到TF-IDF 文件并輸出。

2.3 訓(xùn)練分類模型

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

1）輸入TF-IDF 文件，讀取分布式文件系統(tǒng)中的內(nèi)容；

2）Map 階段，讀取文件，計算xk在每個類別的TF-IDF 值，按照鍵值對的形式溢出到HDFS 本地磁盤中保存為一個文件；

3）所有分片輸出的鍵值對會在Shuffle 過程按照wordID_xk歸并處理，Reduce 階段接收歸并結(jié)果繼續(xù)處理。整理結(jié)果會按照“>”的鍵值對形式進行輸出；

4）Reduce 階段，獲得上一步輸出內(nèi)容，直接以的鍵值對形式保存到weight文件并輸出即可。

2.4 測試分類模型

測試分類模型Job 的工作流程：

1）輸入測試數(shù)據(jù)totalTestNews 文件和權(quán)重值weight文件，讀取分布式文件系統(tǒng)中的內(nèi)容；

2）Map 階段，按順序讀取兩個文件，根據(jù)公式（1）預(yù)測新文本概率。按照鍵值對的形式保存；

3）所有分片輸出的鍵值對會在Shuffle 過程按照newID 歸并處理，Reduce 階段接收歸并結(jié)果繼續(xù)處理。整理結(jié)果會按照“>”的鍵值對形式進行輸出；

4）Reduce 階段，獲得上一步輸出內(nèi)容，輸出最大值對應(yīng)的類別。

3 實驗部分

3.1 環(huán)境配置

用聯(lián)想z40-70 筆記本一臺，該筆記本包含一臺英特爾i5-4210U 物理CPU，該CPU 有2 個內(nèi)核，主頻1.70 GHz，內(nèi)存8 GB，硬盤1 TB，物理網(wǎng)卡1個。筆記本安裝win10 專業(yè)版操作系統(tǒng)，使用Vmware Workstation Pro14 軟件創(chuàng)建4 個虛擬機，每個虛擬機包含一個內(nèi)核CPU，內(nèi)存1 GB，硬盤20 GB 和虛擬網(wǎng)卡1 個。搭建Hadoop 分布式集群，使用Anaconda3、Python3.7 和PyCharm 作為開發(fā)環(huán)境。同時，本文通過編寫爬蟲程序，從新浪新聞網(wǎng)站爬取了4 類新聞數(shù)據(jù)作為實驗語料，分別為娛樂、軍事、體育和科技4 個類別，格式為新聞類別、標(biāo)題、URL 和內(nèi)容。每類新聞數(shù)目為4 500 條，共包含1.8 萬條新聞，其中訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)比值為2∶1，即包含1.2萬條訓(xùn)練數(shù)據(jù)和6 000條測試數(shù)據(jù)。

3.2 實驗結(jié)果及分析

第1 組實驗是不同節(jié)點運行時間對比實驗。選擇4 個節(jié)點對本文數(shù)據(jù)集進行訓(xùn)練，記錄并行化處理的總時間。當(dāng)節(jié)點數(shù)為1時，運行時間為658 s；節(jié)點數(shù)為2 時，運行時間為534 s；節(jié)點數(shù)為3 時，運行時間為397 s；節(jié)點數(shù)為4 時，運行時間為274 s。節(jié)點數(shù)目越多，處理時間越少，因此該方法一定程度上可以提高算法的時間效率。

第2 組實驗是傳統(tǒng)樸素貝葉斯分類算法與本文并行化算法的分類時間對比。如圖1（a）所示。圖1（a）表明：在初期訓(xùn)練集較少時，并行算法讀取數(shù)據(jù)需要消耗一定時間，串行樸素貝葉斯算法分類的效率優(yōu)于并行的樸素貝葉斯算法。隨著訓(xùn)練數(shù)據(jù)集的擴大，集群運行優(yōu)勢逐步體現(xiàn)，且數(shù)據(jù)規(guī)模越大優(yōu)勢越明顯。

第3 組實驗是對本文算法分類效果的評估。在單機和集群環(huán)境下，分別選取精確率U、召回率R 和它們的調(diào)和平均值F1進行比較。

分類器在類cj上的精確率定義如下：其中，Ncuj代表正確分到cj類中的文檔數(shù)目，Nuj代表分到cj類中的全部文檔數(shù)目。

分類器在類cj上的召回率定義如下：

其中，Ncj表示實際類別cj中應(yīng)有的文本數(shù)。

分類器在類cj上的F1值定義如下：

將娛樂，軍事，體育，科技類分別記為類別1，2，3，4。傳統(tǒng)的樸素貝葉斯和本文并行化的樸素貝葉斯分類精確率、召回率和F1值對比分別如圖1（b），圖1（c），圖1（d）所示。

圖1 傳統(tǒng)和并行樸素貝葉斯的比較：（a）運行時間，（b）精確率，（c）召回率，（d）F1值Fig.1 Comparison of traditional method and parallelized naive bayes method：（a）runtime，（b）precision，（c）recall，（d）F1 values

由于進行了專門的特征詞選取工作，由圖1（b）可知，4 類新聞的分類精確率都有所提高，軍事類精確率提高了7.66%。由圖1（c）可知，分類召回率不但有所提高，類間的差距也在不斷縮小，逐漸趨于平穩(wěn)。其中，體育類召回率提高了7.56%。由圖1（d）可知，并行化的樸素貝葉斯算法整體上提高了F1值，體育類的F1值提高了11.98%。由此可知，該方法較對照組傳統(tǒng)樸素貝葉斯方法精確率，召回率，F(xiàn)1值分別至少提高了7.66%、7.56% 和11.98%。從總體上看分類效果較好。

4 結(jié) 論

本文利用NB 算法，通過Hadoop 平臺實現(xiàn)了文本分類的并行化。在特征選擇，權(quán)重計算等階段分別使用MapReduce 框架來計算。實驗證明，與串行NB 算法相比，在同樣的數(shù)據(jù)規(guī)模下，本文分類算法在精確率、召回率和F1值上均有所提高，具有更好的分類效果。同時，節(jié)點數(shù)目越多，算法運行時間越少，運算效率顯著提升。因此，Hadoop平臺對大規(guī)模的文本處理具有較大的優(yōu)勢。但由于實驗中語料庫的規(guī)模較小，在今后的研究中，將嘗試與其它大數(shù)據(jù)平臺、優(yōu)化算法相結(jié)合，擴大數(shù)據(jù)規(guī)模，并適當(dāng)增加集群的節(jié)點數(shù)，不但要提升時間效率，還要從根本上提升算法分類的準(zhǔn)確率。