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

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

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

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

1 相關研究

1.1 樸素貝葉斯分類算法

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

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

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

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

1.2 卡方特征選擇

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

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

1.3 TF-IDF 權重

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

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

1.4 MapReduce 編程框架

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

2 樸素貝葉斯算法并行化

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

2.1 特征選擇

特征選擇Job 的工作流程：

1）輸入totalnews 和wordcount 文件，讀取分布式文件系統中的內容；

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

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

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

2.2 權重計算

權重計算Job 的工作流程：

1）輸入totalnews 和CHI 文件，讀取分布式文件系統中的內容；

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

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

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

2.3 訓練分類模型

訓練分類模型Job 的工作流程：

1）輸入TF-IDF 文件，讀取分布式文件系統中的內容；

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

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

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

2.4 測試分類模型

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

1）輸入測試數據totalTestNews 文件和權重值weight文件，讀取分布式文件系統中的內容；

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

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

4）Reduce 階段，獲得上一步輸出內容，輸出最大值對應的類別。

3 實驗部分

3.1 環境配置

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

3.2 實驗結果及分析

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

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

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

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

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

其中，Ncj表示實際類別cj中應有的文本數。

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

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

圖1 傳統和并行樸素貝葉斯的比較：（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）可知，分類召回率不但有所提高，類間的差距也在不斷縮小，逐漸趨于平穩。其中，體育類召回率提高了7.56%。由圖1（d）可知，并行化的樸素貝葉斯算法整體上提高了F1值，體育類的F1值提高了11.98%。由此可知，該方法較對照組傳統樸素貝葉斯方法精確率，召回率，F1值分別至少提高了7.66%、7.56% 和11.98%。從總體上看分類效果較好。

4 結 論

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