石 磊,巴 陽,陶永才,衛(wèi) 琳
1(鄭州大學(xué) 信息工程學(xué)院,鄭州 450001) 2(鄭州大學(xué) 軟件技術(shù)學(xué)院,鄭州 450002) E-mail:ieyctao@zzu.edu.cn
文本分類是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)之一,特征選擇作為文本分類的核心主要目的是降維[1].特征選擇的好壞將會(huì)直接影響文本分類的準(zhǔn)確率.CHI統(tǒng)計(jì)法(chi-square test)又稱卡方統(tǒng)計(jì)法,是數(shù)理統(tǒng)計(jì)中檢驗(yàn)兩個(gè)變量獨(dú)立性的方法.CHI 統(tǒng)計(jì)法是最常用的文本特征選擇方法之一[2].
MapReduce[3]是Google公司處理大規(guī)模數(shù)據(jù)而提出的基于分布式并行計(jì)算的編程模型,MapReduce的核心策略是分而治之,將大的任務(wù)分解成若干個(gè)小任務(wù)進(jìn)行處理[4].通過對(duì)數(shù)據(jù)的拆分與組合不僅有效地提高了數(shù)據(jù)并行處理能力也極大地改善了系統(tǒng)性能.
傳統(tǒng)CHI統(tǒng)計(jì)法只關(guān)注文檔頻率,一些文檔頻率低但特征詞頻率高的特征詞將不會(huì)被選為特征項(xiàng);同時(shí),放大了在指定類別中出現(xiàn)很少但在其他類別中出現(xiàn)較多的特征詞在該類中的權(quán)重.
為解決上述問題,本文提出一種基于MapReduce的CHI文本特征選擇機(jī)制,主要貢獻(xiàn)如下:
1)對(duì)傳統(tǒng)CHI統(tǒng)計(jì)法公式進(jìn)行改進(jìn),引入類內(nèi)頻數(shù)解決忽略高頻特征詞的問題,同時(shí)引入類間方差解決放大外圍特征詞權(quán)重的問題,從而提高CHI統(tǒng)計(jì)法的特征選擇準(zhǔn)確度,從根本上提高文本分類的精度;
2)提出基于MapReduce的CHI文本特征選擇模型,將文本處理分為獨(dú)立可并行的兩個(gè)階段:文本訓(xùn)練階段和文本分類階段,充分利用MapReduce模型處理海量數(shù)據(jù)的優(yōu)勢(shì),優(yōu)化文本訓(xùn)練和分類的模式,從而提升文本分類的效率.
傳統(tǒng)CHI統(tǒng)計(jì)法優(yōu)點(diǎn)是實(shí)現(xiàn)簡單,算法復(fù)雜度低,但是也存在明顯不足,眾多研究者對(duì)其做出改進(jìn).文獻(xiàn)[5]在實(shí)際文本數(shù)據(jù)和CHI特征選擇算法的基礎(chǔ)上,提出了一種特征選擇算法.對(duì)于分布不均勻的特征數(shù)據(jù)集,該算法適當(dāng)?shù)靥岣吡思性谏贁?shù)文檔中的詞的權(quán)重;文獻(xiàn)[6]提出了一種基于 CHI 統(tǒng)計(jì)和信息熵的改進(jìn)型 TFIDF 特征加權(quán)方法,提高了特征項(xiàng)權(quán)重計(jì)算的準(zhǔn)確性;文獻(xiàn)[7]提出一種基于概率的CHI特征選擇方法,結(jié)合特征詞概率和文檔概率來衡量文檔頻度,在不均衡數(shù)據(jù)集上有良好表現(xiàn).上述研究在多個(gè)方面不同程度地彌補(bǔ)了傳統(tǒng)CHI統(tǒng)計(jì)法的不足,提高了特征詞的質(zhì)量與文本分類的精度.但是,忽略了大量文本文件對(duì)文本分類執(zhí)行速率的影響.
文獻(xiàn)[8]利用MapReduce強(qiáng)大的并行處理能力對(duì)分類器進(jìn)行訓(xùn)練和預(yù)測(cè),設(shè)計(jì)并實(shí)現(xiàn)了并行分類訓(xùn)練和預(yù)測(cè)算法,提高了大型數(shù)據(jù)多類問題的準(zhǔn)確性和效率;文獻(xiàn)[9]則提出了基于MapReduce的并行K-means文本聚類算法,采用優(yōu)良的初始質(zhì)心選擇策略來提高K-means聚類效果,然后設(shè)計(jì)出適用于MapReduce平臺(tái)的文本并行聚類模型.從上述研究可以發(fā)現(xiàn)MapReduce技術(shù)的成熟應(yīng)用為各種文本分類方法在大規(guī)模數(shù)據(jù)的處理上開辟新的道路.本文提出的基于MapReduce的CHI文本特征選擇機(jī)制,在改進(jìn)傳統(tǒng)CHI方法的同時(shí)采用MapReduce框架對(duì)文本分類進(jìn)行并行處理,不僅有效地提高了文本分類的精度,同時(shí)也還提升了文本分類的效率.
CHI統(tǒng)計(jì)方法是分類效果較好的文本特征選擇方法之一[6].CHI統(tǒng)計(jì)方法通過觀察實(shí)際值與理論值的偏差來確定理論的正確與否[10].在實(shí)際應(yīng)用中,經(jīng)常先假設(shè)指定的兩個(gè)變量相互獨(dú)立,然后比較觀測(cè)值和理論值的偏差程度,若偏差在預(yù)先給定的偏差閾值之內(nèi),則可認(rèn)為造成的誤差是由于測(cè)量不精確或小概率事件發(fā)生,此時(shí)判定原假設(shè)成立,即兩個(gè)變量相互獨(dú)立;若偏差超過預(yù)先給定的偏差閾值,則可認(rèn)為兩個(gè)變量存在相關(guān)性,此時(shí)判定原假設(shè)不成立,即兩個(gè)變量相互關(guān)聯(lián).若用DI表示偏差程度,E表示理論值,xi表示x所有可能的觀測(cè)值(x1,…,xn),則通過計(jì)算得到的DI與偏差閾值對(duì)比,從而判斷原假設(shè)是否成立.計(jì)算公式如式(1)所示.
(1)
將CHI運(yùn)用到特征選擇方法中會(huì)有一定差異,因?yàn)樵趯?shí)際情況中無法給定一個(gè)合適的偏差閾值與DI進(jìn)行對(duì)比.假設(shè)特征詞ti與類別Cj不相關(guān),那么特征選擇的過程變成為每個(gè)特征詞ti計(jì)算與類別Cj的DI值,而后降序排列,取規(guī)定的前k個(gè).假設(shè)有N篇文檔,其中M篇是有關(guān)類別Cj的,若考察特征詞ti與類別Cj之間的相關(guān)性,則有如下定義:
1)A表示包含詞ti且屬于類別Cj的文檔數(shù);
2)B表示包含詞ti但不屬于類別Cj的文檔數(shù);
3)C表示不包含詞ti但屬于類別Cj的文檔數(shù);
4)D表示不包含詞ti也不屬于類別Cj的文檔數(shù).
為了更直觀地解釋字母的含義,引入情形分析表,如表1所示.
因此,對(duì)于給定的特征詞ti與類別Cj之間的相關(guān)性的CHI特征選擇計(jì)算如式(2)所示.
(2)
表1 情形分析表Table 1 Contingency table
傳統(tǒng)CHI方法雖然效果出色,但仍存在明顯的不足,由公式(2)可發(fā)現(xiàn):
1)傳統(tǒng)CHI方法傾向選擇文檔頻數(shù)高的特征詞,即只關(guān)注文檔頻數(shù),而忽略了特征詞頻數(shù),導(dǎo)致那些只在某類文檔中出現(xiàn)頻率高的特征詞被忽略掉,反而選擇了在多數(shù)類別的多數(shù)文檔中偶爾出現(xiàn)的特征詞.
2)放大了在指定類別中出現(xiàn)頻率較低,而在其他類中出現(xiàn)頻率較高的特征詞對(duì)該類DI值的影響,在公式(2)中體現(xiàn)為A、D值很小,B、C值很大,此時(shí)有(AD-BC)2很大,則這樣的特征詞也會(huì)被挑選出來,實(shí)際上,卻并不需要這一類特征詞.
本文在原有CHI方法的基礎(chǔ)上進(jìn)行改進(jìn),通過引入類內(nèi)頻數(shù)和類間方差兩個(gè)參數(shù),有效地解決了傳統(tǒng)CHI方法忽略高頻特征詞和放大外圍特征詞權(quán)重的問題.
類內(nèi)頻數(shù)是指特征詞在某類別所有文檔中頻數(shù)的最大值,由于傳統(tǒng)CHI方法只專注于文檔頻率,導(dǎo)致那些文檔頻率低,但類內(nèi)頻率高的特征詞被過濾掉.本文用Itfij表示特征詞ti對(duì)于類別Cj的類內(nèi)頻數(shù),計(jì)算公式如式(3)所示.
(3)
其中,tfiju為特征詞ti在類別Cj下的文檔du中出現(xiàn)的次數(shù),M為類別Cj的文檔數(shù)(同表1中的M).由式(3)可知,tfiju越大,說明特征詞ti在類別Cj下的文檔du中出現(xiàn)的頻數(shù)越大,則將此特征詞作為這個(gè)類別的候選特征詞的可能性越大.
類內(nèi)頻數(shù)可以有效解決忽略高頻特征詞的問題,而引入類間方差則可以消除傳統(tǒng)CHI方法放大外圍特征詞權(quán)重的影響.外圍特征詞是指:在指定類別中出現(xiàn)次數(shù)很少,而在其他類別中出現(xiàn)次數(shù)很多的一類特征詞.顯然這類特征詞的分類能力較弱.類間方差用來衡量特征詞ti在類別Cj中出現(xiàn)的頻數(shù)與特征詞ti在所有類別文檔中出現(xiàn)的頻數(shù)均值的偏差程度.記作D(ti),計(jì)算公式如式(4)所示.
D(ti)=[dfj(ti)-Vdfj(ti)][dfj(ti)-Vdfj(ti)]2
(4)
其中,dfj( ti)表示特征詞ti在類別Cj中出現(xiàn)的頻數(shù),Vdfj( ti)表示特征詞ti在所有類別文檔中出現(xiàn)的頻數(shù)均值,計(jì)算公式如式(5)所示,式中m表示類別數(shù).
(5)
在式(4)中,若dfj( ti)-Vdfj( ti)>0,且D(ti)值很大時(shí),說明特征詞ti在類別Cj中出現(xiàn)頻數(shù)比特征詞ti在所有類別文檔中出現(xiàn)的頻數(shù)均值大,且大得很多,這樣的特征詞有更好的分類能力,是期望得到的目標(biāo)特征詞;若dfj( ti)-Vdfj(ti)<0,但D(ti)的絕對(duì)值很大時(shí),說明特征詞ti在類別Cj中出現(xiàn)頻數(shù)比特征詞ti在所有類別文檔中出現(xiàn)的頻數(shù)均值小,且小很多,這樣的特征詞的分類能力較差,是需要被淘汰掉的特征詞.
(6)
基于MapReduce的CHI文本特征選擇機(jī)制流程圖如圖1所示.
圖1 機(jī)制流程圖Fig.1 Mechanical flow chart
從圖1中可以看出基于MapReduce的CHI文本特征選擇模型分為兩部分:文本訓(xùn)練階段和文本分類階段.
4.2.1 文本訓(xùn)練階段
圖2是基于MapReduce的CHI文本訓(xùn)練模型.對(duì)于給出的訓(xùn)練文本集,首先進(jìn)行預(yù)處理,包括分詞斷句、去停用詞等,其中,經(jīng)過預(yù)處理后的文本集合為一階訓(xùn)練集,然后將一階訓(xùn)練集輸入到第(1)個(gè)MapReduce過程中.
圖2 基于MapReduce的CHI文本訓(xùn)練模型Fig.2 CHI text training model based on MapReduce
第(1)個(gè)MapReduce過程的作用是計(jì)算特征詞的類內(nèi)頻數(shù),一階訓(xùn)練集按塊劃分入不同的節(jié)點(diǎn)執(zhí)行Map函數(shù),公式(3)為Map函數(shù)的核心,得到基于<特征詞,<類別,tfiju>>的鍵值對(duì)
將第(1)個(gè)MapReduce過程的結(jié)果記為二階訓(xùn)練集,然后輸入到第(2)個(gè)MapReduce過程.第(2)個(gè)MapReduce過程的作用是得到每個(gè)類別的特征向量.二階訓(xùn)練集同樣按塊劃分為不同的節(jié)點(diǎn)執(zhí)行Map函數(shù),Map函數(shù)計(jì)算各個(gè)參數(shù),根據(jù)公式(4)計(jì)算出類間方差,進(jìn)而得到卡方值,公式(6)為Map函數(shù)的核心,得到基于<特征詞,<類別,卡方值>>的鍵值對(duì)
算法1.文本訓(xùn)練算法
輸入:一階訓(xùn)練集;類別C;文檔d;特征詞t;
輸出:各個(gè)類別特征向量;
1 Map1
2 {
3 //計(jì)算一階訓(xùn)練集中特征詞的類內(nèi)頻數(shù)
4foreach du∈Cjdo
7 輸出中間鍵值對(duì)
8endfor
9endfor
10 }
11 Reduce1
12 {
13 輸入中間鍵值對(duì)
14foreach termIDdo
16 輸出鍵值對(duì)
17endfor
18 }
19 Map2
20 {
21 //獲取類別的特征向量
22 輸入鍵值對(duì)
23foreach termIDdo
25 計(jì)算卡方值CHIValue;
26 輸出中間鍵值對(duì)
27endfor
28 }
29 Reduce2
30 {
31 輸入中間鍵值對(duì)
32foreach classIDdo
33 CHIValue倒序排列,并取前k個(gè);
34 輸出類別特征向量;
35endfor
36 }
4.2.2 文本分類階段
圖3是基于MapReduce的CHI文本分類模型.分類模型的輸入數(shù)據(jù)集是經(jīng)過預(yù)處理后的測(cè)試文本集,記作一階測(cè)試集,然后用維向量表示一階測(cè)試集,輸入到第(3)個(gè)MapReduce過程.文本分類算法如算法2所示.
圖3 基于MapReduce的CHI文本分類模型Fig.3 CHI text classification model based on MapReduce
算法2.文本分類算法
輸入:一階測(cè)試集;文檔d,特征詞t;
輸出:類別文檔集;
1 Map3{
2foreach ti∈ dudo
4 輸出中間鍵值對(duì)<
5endfor
6 }
7 Reduce3{
8foreach docIDdo
10 輸出文檔特征向量;
11endfor
12 }
13 Map4{
14 輸入二階測(cè)試集;
15foreach dudo
17 輸出中間鍵值對(duì)
18endfor
19 }
20 Reduce4{
21foreach classIDdo
23 輸出類別文檔集;
24endfor
25 }
第(3)個(gè)MapReduce過程的作用是計(jì)算特征詞ti在測(cè)試文檔du中出現(xiàn)的次數(shù),然后生成文檔特征向量集.需要說明的是本部分過程只關(guān)注某特征詞在某篇文檔中出現(xiàn)的次數(shù),而不關(guān)心文檔類別,但這里可以用tfiu表示特征詞ti在測(cè)試文檔du中出現(xiàn)的次數(shù).一階測(cè)試集按塊劃分入不同的節(jié)點(diǎn)執(zhí)行Map函數(shù),Map函數(shù)的作用是計(jì)算特征詞的tfiu,得到基于<特征詞,文檔,tfiu>的鍵值對(duì)<
將第(3)個(gè)MapReduce過程的結(jié)果歸檔集合,并記為二階測(cè)試集,和文本訓(xùn)練階段生成的訓(xùn)練庫一并輸入到第(4)個(gè)MapReduce過程.第(4)個(gè)MapReduce過程的作用是用KNN分類器[11]分類二階測(cè)試集.經(jīng)過KNN分類后得到基于<類別,文檔>的鍵值對(duì)
本文采用復(fù)旦大學(xué)自然語言處理小組整理收集的文本分類語料庫*語料庫查載于自然語言處理與信息檢索共享平臺(tái)[EB/OL].2017-1-15,http://www.nlpir.org/?action-viewnews-itemid-103.作為訓(xùn)練集和測(cè)試集,從中選取六種類別的部分文檔作為訓(xùn)練集文檔和測(cè)試集文檔.選取情況如表2所示.
表2 測(cè)試集和訓(xùn)練集文檔選取情況Table 2 Testing set and training set document selection
本文實(shí)驗(yàn)設(shè)置情況如下:
1)可行性驗(yàn)證實(shí)驗(yàn).用來檢驗(yàn)本文MapReduce機(jī)制對(duì)改進(jìn)CHI方法是否有不良影響.實(shí)驗(yàn)對(duì)象設(shè)置為:本文提出的改進(jìn)CHI方法分別運(yùn)行在普通PC機(jī)上和Hadoop單節(jié)點(diǎn)上.
2)性能對(duì)比實(shí)驗(yàn).用來檢驗(yàn)本文提出的改進(jìn)CHI方法的性能.對(duì)比實(shí)驗(yàn)對(duì)象設(shè)置為:傳統(tǒng)CHI統(tǒng)計(jì)法、論文[12]提出的改進(jìn)CHI方法(用CHI-F表示)、本文提出的改進(jìn)CHI方法.
3)效率測(cè)試實(shí)驗(yàn).用來測(cè)試本文提出的改進(jìn)CHI方法在Hadoop平臺(tái)上的效率.
實(shí)驗(yàn)設(shè)備具體配置如下:CPU為Intel Xeon E5620 2.66 GHz,8G內(nèi)存,2TB硬盤,操作系統(tǒng)為Ubuntu 14.04,Hadoop版本1.2.1,Java版本1.7.0.實(shí)驗(yàn)中特征向量的維度為1000,分類方法KNN中的K取值為20.
1)查準(zhǔn)率用來反映文本分類的健全性,即分類結(jié)果的準(zhǔn)確性[13],用P表示查準(zhǔn)率,其計(jì)算公式如式(7)所示.
(7)
2)召回率用來反映正確分類的能力,用R表示召回率,其計(jì)算公式如式(8)所示.
(8)
3)F1值是綜合以上兩種評(píng)價(jià)標(biāo)準(zhǔn)對(duì)文本分類進(jìn)行整體評(píng)價(jià),其計(jì)算公式如式(9)所示.
(9)
4)加速比用來衡量程序并行化的性能[14],用Ts表示加速比,其計(jì)算公式如式(10)所示.
(10)
可行性驗(yàn)證實(shí)驗(yàn)結(jié)果如表3所示.
表3 PC單機(jī)和MapReduce下文本的向量維度Table 3 Vector dimension in PC and mapreduce
分別將改進(jìn)的CHI方法運(yùn)行在Hadoop單節(jié)點(diǎn)平臺(tái)和一臺(tái)普通PC機(jī)上.通過表3中的實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn),兩種環(huán)境下最終生成的文本向量維數(shù)差異很小.綜上所述,MapReduce
技術(shù)的引入并未對(duì)CHI方法在文本向量維度產(chǎn)生不良影響.
性能對(duì)比實(shí)驗(yàn)結(jié)果如表4所示.
從表4中得到的三種CHI方法查準(zhǔn)率和召回率,根據(jù)式(9)可以計(jì)算出各個(gè)方法的F1值,F1值對(duì)比結(jié)果如圖4所示.
表4 實(shí)驗(yàn)結(jié)果及對(duì)比Table 4 Experimental results and comparison
由實(shí)驗(yàn)數(shù)據(jù)可以看出:傳統(tǒng)CHI方法在本實(shí)驗(yàn)數(shù)據(jù)集上的F1值最高也只達(dá)到62.56%,對(duì)于樣本較少的“醫(yī)學(xué)”、“歷史”小類預(yù)料,其F1值更低;CHI-F方法在本套數(shù)據(jù)集上的測(cè)試結(jié)果已有明顯改善,F1值較高時(shí)能達(dá)到79.38%,對(duì)于樣本較少的“醫(yī)學(xué)”、“歷史”,其F1值也有顯著提升;本文提出的CHI方法,F1值比其他兩種方法的F1值明顯提升,最高值幾乎能達(dá)到90%.結(jié)合表4發(fā)現(xiàn)傳統(tǒng)CHI方法中小類預(yù)料集F1值偏小是因?yàn)椤搬t(yī)學(xué)”和“歷史”的訓(xùn)練集相對(duì)于整個(gè)訓(xùn)練集的比重較小,在沒有過濾算法處理的情況下,將會(huì)選中訓(xùn)練集中大量外圍特征詞,導(dǎo)致分類效果不佳;CHI-F方法在一定程度上改善了小類預(yù)料集F1值偏低的現(xiàn)象;本文提出的CHI方法通過類內(nèi)頻數(shù)和類間方差的共軛修正,在小類預(yù)料集查準(zhǔn)率、召回率、F1值上,均比CHI-F方法有進(jìn)一步的提高.
圖5 系統(tǒng)加速比Fig.5 System speedup
效率測(cè)試實(shí)驗(yàn)用來檢驗(yàn)Hadoop集群中DataNode節(jié)點(diǎn)數(shù)目的增加是否對(duì)模型的性能產(chǎn)生影響.實(shí)驗(yàn)觀察基于MapReduce的CHI文本特征選擇機(jī)制的實(shí)驗(yàn)運(yùn)行時(shí)間和加速比.其中,多節(jié)點(diǎn)Hadoop集群分別由3、6、9、12、15個(gè)DataNode節(jié)點(diǎn)組成.實(shí)驗(yàn)結(jié)果如表5所示.
表5中的實(shí)驗(yàn)運(yùn)行時(shí)間是經(jīng)過多組實(shí)驗(yàn)得出的平均值,根據(jù)式(10)計(jì)算出系統(tǒng)加速比,實(shí)驗(yàn)結(jié)果如圖5所示.
表5 實(shí)驗(yàn)運(yùn)行時(shí)間Table 5 Experimental running time
由圖5可知,在初始階段當(dāng)Hadoop節(jié)點(diǎn)數(shù)較少時(shí),本文提出的基于MapReduce的CHI文本特征選擇機(jī)制加速比提升不明顯,當(dāng)Hadoop節(jié)點(diǎn)數(shù)增加至9臺(tái),加速比已有顯著提升,綜合來看,本文提出的優(yōu)化機(jī)制的加速比隨著DataNode節(jié)點(diǎn)的增加有顯著增長.
傳統(tǒng)的CHI方法雖然廣泛使用于文本分類中,但是算法忽略高頻特征詞和放大外圍特征詞權(quán)重的問題使得算法在實(shí)際的應(yīng)用中分類精確度偏低.本文針對(duì)上述問題,在改進(jìn)傳統(tǒng)CHI方法的同時(shí)結(jié)合MapReduce技術(shù),提出一種基于MapReduce的CHI文本特征選擇機(jī)制.實(shí)驗(yàn)結(jié)果表明,本機(jī)制不僅能有效提高文本分類精度,也提升了文本分類的效率.
本文提出的基于MapReduce的CHI文本特征選擇機(jī)制對(duì)小類預(yù)料集的分類精度雖然提高很多,但還有上升空間,未來考慮針對(duì)小類預(yù)料集以及含大量噪聲詞的預(yù)料集進(jìn)行專門研究;同時(shí),MapReduce技術(shù)是當(dāng)前大數(shù)據(jù)應(yīng)用的核心,能否將本文MapReduce模型適配到其它算法中也是未來研究的另一個(gè)方向.