張晨躍，劉黎志，鄧開(kāi)巍，劉 杰

智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室（武漢工程大學(xué)），湖北 武漢 430205

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

1 相關(guān)研究

1.1 樸素貝葉斯分類(lèi)算法

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

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

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

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

1.2 卡方特征選擇

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

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

1.3 TF-IDF 權(quán)重

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

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

1.4 MapReduce 編程框架

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

2 樸素貝葉斯算法并行化

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

2.1 特征選擇

特征選擇Job 的工作流程：

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

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

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

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

2.2 權(quán)重計(jì)算

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

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

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

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

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

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

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

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

2）Map 階段，讀取文件，計(jì)算xk在每個(gè)類(lèi)別的TF-IDF 值，按照鍵值對(duì)的形式溢出到HDFS 本地磁盤(pán)中保存為一個(gè)文件；

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

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

2.4 測(cè)試分類(lèi)模型

測(cè)試分類(lèi)模型Job 的工作流程：

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

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

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

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

3 實(shí)驗(yàn)部分

3.1 環(huán)境配置

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

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

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

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

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

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

分類(lèi)器在類(lèi)cj上的召回率定義如下：

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

分類(lèi)器在類(lèi)cj上的F1值定義如下：

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

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

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

4 結(jié) 論

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