基于MapReduce的改進CHI文本特征選擇機制

石 磊,巴 陽,陶永才,衛(wèi) 琳

1(鄭州大學(xué) 信息工程學(xué)院,鄭州 450001) 2(鄭州大學(xué) 軟件技術(shù)學(xué)院,鄭州 450002) E-mail:ieyctao@zzu.edu.cn

1 引 言

文本分類是數(shù)據(jù)挖掘和機器學(xué)習(xí)領(lǐng)域的研究熱點之一,特征選擇作為文本分類的核心主要目的是降維[1].特征選擇的好壞將會直接影響文本分類的準確率.CHI統(tǒng)計法(chi-square test)又稱卡方統(tǒng)計法,是數(shù)理統(tǒng)計中檢驗兩個變量獨立性的方法.CHI 統(tǒng)計法是最常用的文本特征選擇方法之一[2].

MapReduce[3]是Google公司處理大規(guī)模數(shù)據(jù)而提出的基于分布式并行計算的編程模型,MapReduce的核心策略是分而治之,將大的任務(wù)分解成若干個小任務(wù)進行處理[4].通過對數(shù)據(jù)的拆分與組合不僅有效地提高了數(shù)據(jù)并行處理能力也極大地改善了系統(tǒng)性能.

傳統(tǒng)CHI統(tǒng)計法只關(guān)注文檔頻率,一些文檔頻率低但特征詞頻率高的特征詞將不會被選為特征項;同時,放大了在指定類別中出現(xiàn)很少但在其他類別中出現(xiàn)較多的特征詞在該類中的權(quán)重.

為解決上述問題,本文提出一種基于MapReduce的CHI文本特征選擇機制,主要貢獻如下:

1)對傳統(tǒng)CHI統(tǒng)計法公式進行改進,引入類內(nèi)頻數(shù)解決忽略高頻特征詞的問題,同時引入類間方差解決放大外圍特征詞權(quán)重的問題,從而提高CHI統(tǒng)計法的特征選擇準確度,從根本上提高文本分類的精度;

2)提出基于MapReduce的CHI文本特征選擇模型,將文本處理分為獨立可并行的兩個階段:文本訓(xùn)練階段和文本分類階段,充分利用MapReduce模型處理海量數(shù)據(jù)的優(yōu)勢,優(yōu)化文本訓(xùn)練和分類的模式,從而提升文本分類的效率.

2 相關(guān)工作

傳統(tǒng)CHI統(tǒng)計法優(yōu)點是實現(xiàn)簡單,算法復(fù)雜度低,但是也存在明顯不足,眾多研究者對其做出改進.文獻[5]在實際文本數(shù)據(jù)和CHI特征選擇算法的基礎(chǔ)上,提出了一種特征選擇算法.對于分布不均勻的特征數(shù)據(jù)集,該算法適當?shù)靥岣吡思性谏贁?shù)文檔中的詞的權(quán)重;文獻[6]提出了一種基于 CHI 統(tǒng)計和信息熵的改進型 TFIDF 特征加權(quán)方法,提高了特征項權(quán)重計算的準確性;文獻[7]提出一種基于概率的CHI特征選擇方法,結(jié)合特征詞概率和文檔概率來衡量文檔頻度,在不均衡數(shù)據(jù)集上有良好表現(xiàn).上述研究在多個方面不同程度地彌補了傳統(tǒng)CHI統(tǒng)計法的不足,提高了特征詞的質(zhì)量與文本分類的精度.但是,忽略了大量文本文件對文本分類執(zhí)行速率的影響.

文獻[8]利用MapReduce強大的并行處理能力對分類器進行訓(xùn)練和預(yù)測,設(shè)計并實現(xiàn)了并行分類訓(xùn)練和預(yù)測算法,提高了大型數(shù)據(jù)多類問題的準確性和效率;文獻[9]則提出了基于MapReduce的并行K-means文本聚類算法,采用優(yōu)良的初始質(zhì)心選擇策略來提高K-means聚類效果,然后設(shè)計出適用于MapReduce平臺的文本并行聚類模型.從上述研究可以發(fā)現(xiàn)MapReduce技術(shù)的成熟應(yīng)用為各種文本分類方法在大規(guī)模數(shù)據(jù)的處理上開辟新的道路.本文提出的基于MapReduce的CHI文本特征選擇機制,在改進傳統(tǒng)CHI方法的同時采用MapReduce框架對文本分類進行并行處理,不僅有效地提高了文本分類的精度,同時也還提升了文本分類的效率.

3 研究背景

CHI統(tǒng)計方法是分類效果較好的文本特征選擇方法之一[6].CHI統(tǒng)計方法通過觀察實際值與理論值的偏差來確定理論的正確與否[10].在實際應(yīng)用中,經(jīng)常先假設(shè)指定的兩個變量相互獨立,然后比較觀測值和理論值的偏差程度,若偏差在預(yù)先給定的偏差閾值之內(nèi),則可認為造成的誤差是由于測量不精確或小概率事件發(fā)生,此時判定原假設(shè)成立,即兩個變量相互獨立;若偏差超過預(yù)先給定的偏差閾值,則可認為兩個變量存在相關(guān)性,此時判定原假設(shè)不成立,即兩個變量相互關(guān)聯(lián).若用DI表示偏差程度,E表示理論值,xi表示x所有可能的觀測值(x1,…,xn),則通過計算得到的DI與偏差閾值對比,從而判斷原假設(shè)是否成立.計算公式如式(1)所示.

(1)

將CHI運用到特征選擇方法中會有一定差異,因為在實際情況中無法給定一個合適的偏差閾值與DI進行對比.假設(shè)特征詞ti與類別Cj不相關(guān),那么特征選擇的過程變成為每個特征詞ti計算與類別Cj的DI值,而后降序排列,取規(guī)定的前k個.假設(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所示.

因此,對于給定的特征詞ti與類別Cj之間的相關(guān)性的CHI特征選擇計算如式(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)頻率較高的特征詞對該類DI值的影響,在公式(2)中體現(xiàn)為A、D值很小,B、C值很大,此時有(AD-BC)2很大,則這樣的特征詞也會被挑選出來,實際上,卻并不需要這一類特征詞.

4 基于MapReduce的CHI文本特征選擇

4.1 改進的CHI方法

本文在原有CHI方法的基礎(chǔ)上進行改進,通過引入類內(nèi)頻數(shù)和類間方差兩個參數(shù),有效地解決了傳統(tǒng)CHI方法忽略高頻特征詞和放大外圍特征詞權(quán)重的問題.

類內(nèi)頻數(shù)是指特征詞在某類別所有文檔中頻數(shù)的最大值,由于傳統(tǒng)CHI方法只專注于文檔頻率,導(dǎo)致那些文檔頻率低,但類內(nèi)頻率高的特征詞被過濾掉.本文用Itfij表示特征詞ti對于類別Cj的類內(nèi)頻數(shù),計算公式如式(3)所示.

(3)

其中,tfiju為特征詞ti在類別Cj下的文檔du中出現(xiàn)的次數(shù),M為類別Cj的文檔數(shù)(同表1中的M).由式(3)可知,tfiju越大,說明特征詞ti在類別Cj下的文檔du中出現(xiàn)的頻數(shù)越大,則將此特征詞作為這個類別的候選特征詞的可能性越大.

類內(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),計算公式如式(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ù)均值,計算公式如式(5)所示,式中m表示類別數(shù).

(5)

在式(4)中,若dfj( ti)-Vdfj( ti)>0,且D(ti)值很大時,說明特征詞ti在類別Cj中出現(xiàn)頻數(shù)比特征詞ti在所有類別文檔中出現(xiàn)的頻數(shù)均值大,且大得很多,這樣的特征詞有更好的分類能力,是期望得到的目標特征詞;若dfj( ti)-Vdfj(ti)<0,但D(ti)的絕對值很大時,說明特征詞ti在類別Cj中出現(xiàn)頻數(shù)比特征詞ti在所有類別文檔中出現(xiàn)的頻數(shù)均值小,且小很多,這樣的特征詞的分類能力較差,是需要被淘汰掉的特征詞.

(6)

4.2 基于MapReduce的CHI文本特征選擇機制

基于MapReduce的CHI文本特征選擇機制流程圖如圖1所示.

圖1 機制流程圖Fig.1 Mechanical flow chart

從圖1中可以看出基于MapReduce的CHI文本特征選擇模型分為兩部分:文本訓(xùn)練階段和文本分類階段.

4.2.1 文本訓(xùn)練階段

圖2是基于MapReduce的CHI文本訓(xùn)練模型.對于給出的訓(xùn)練文本集,首先進行預(yù)處理,包括分詞斷句、去停用詞等,其中,經(jīng)過預(yù)處理后的文本集合為一階訓(xùn)練集,然后將一階訓(xùn)練集輸入到第(1)個MapReduce過程中.

圖2 基于MapReduce的CHI文本訓(xùn)練模型Fig.2 CHI text training model based on MapReduce

第(1)個MapReduce過程的作用是計算特征詞的類內(nèi)頻數(shù),一階訓(xùn)練集按塊劃分入不同的節(jié)點執(zhí)行Map函數(shù),公式(3)為Map函數(shù)的核心,得到基于<特征詞,<類別,tfiju>>的鍵值對>,然后經(jīng)過中間過程流入緩存、再分類等過程,最后經(jīng)過Reduce函數(shù),以termID為分類依據(jù),找到tfiju的最大值Itfij,最終得到了基于<特征詞,<類別,類內(nèi)頻數(shù)>>的鍵值對>.

將第(1)個MapReduce過程的結(jié)果記為二階訓(xùn)練集,然后輸入到第(2)個MapReduce過程.第(2)個MapReduce過程的作用是得到每個類別的特征向量.二階訓(xùn)練集同樣按塊劃分為不同的節(jié)點執(zhí)行Map函數(shù),Map函數(shù)計算各個參數(shù),根據(jù)公式(4)計算出類間方差,進而得到卡方值,公式(6)為Map函數(shù)的核心,得到基于<特征詞,<類別,卡方值>>的鍵值對>,同樣地,經(jīng)過中間過程處理后,以classID為分類依據(jù),并降序排列篩選得到的CHIValue,取預(yù)先規(guī)定的前k個值,組成類別Cj的特征向量,最終并入訓(xùn)練庫.文本訓(xùn)練算法如算法1所示.

算法1.文本訓(xùn)練算法

輸入:一階訓(xùn)練集;類別C;文檔d;特征詞t;

輸出:各個類別特征向量;

1 Map1

2 {

3 //計算一階訓(xùn)練集中特征詞的類內(nèi)頻數(shù)

4foreach du∈Cjdo

7 輸出中間鍵值對>;

8endfor

9endfor

10 }

11 Reduce1

12 {

13 輸入中間鍵值對>;

14foreach termIDdo

16 輸出鍵值對>;

17endfor

18 }

19 Map2

20 {

21 //獲取類別的特征向量

22 輸入鍵值對>;

23foreach termIDdo

25 計算卡方值CHIValue;

26 輸出中間鍵值對>;

27endfor

28 }

29 Reduce2

30 {

31 輸入中間鍵值對>;

32foreach classIDdo

33 CHIValue倒序排列,并取前k個;

34 輸出類別特征向量;

35endfor

36 }

4.2.2 文本分類階段

圖3是基于MapReduce的CHI文本分類模型.分類模型的輸入數(shù)據(jù)集是經(jīng)過預(yù)處理后的測試文本集,記作一階測試集,然后用維向量表示一階測試集,輸入到第(3)個MapReduce過程.文本分類算法如算法2所示.

圖3 基于MapReduce的CHI文本分類模型Fig.3 CHI text classification model based on MapReduce

算法2.文本分類算法

輸入:一階測試集;文檔d,特征詞t;

輸出:類別文檔集;

1 Map3{

2foreach ti∈ dudo

4 輸出中間鍵值對<,tfiu>;

5endfor

6 }

7 Reduce3{

8foreach docIDdo

10 輸出文檔特征向量;

11endfor

12 }

13 Map4{

14 輸入二階測試集;

15foreach dudo

17 輸出中間鍵值對;

18endfor

19 }

20 Reduce4{

21foreach classIDdo

23 輸出類別文檔集;

24endfor

25 }

第(3)個MapReduce過程的作用是計算特征詞ti在測試文檔du中出現(xiàn)的次數(shù),然后生成文檔特征向量集.需要說明的是本部分過程只關(guān)注某特征詞在某篇文檔中出現(xiàn)的次數(shù),而不關(guān)心文檔類別,但這里可以用tfiu表示特征詞ti在測試文檔du中出現(xiàn)的次數(shù).一階測試集按塊劃分入不同的節(jié)點執(zhí)行Map函數(shù),Map函數(shù)的作用是計算特征詞的tfiu,得到基于<特征詞,文檔,tfiu>的鍵值對<,tfiu>,然后經(jīng)過中間過程流入緩存、再分類等過程,最后經(jīng)過Reduce函數(shù)處理,以為分類依據(jù),將同docID的特征詞按tfiu值降序排列,取預(yù)先規(guī)定的前k個值,組成文檔的du特征向量.歸檔集合后送入下一個MapReduce過程.

將第(3)個MapReduce過程的結(jié)果歸檔集合,并記為二階測試集,和文本訓(xùn)練階段生成的訓(xùn)練庫一并輸入到第(4)個MapReduce過程.第(4)個MapReduce過程的作用是用KNN分類器[11]分類二階測試集.經(jīng)過KNN分類后得到基于<類別,文檔>的鍵值對,同樣是經(jīng)過中間過程處理后,最后執(zhí)行Reduce函數(shù),以類別為分類依據(jù),將同classID的文檔歸類,即得到最終的分類結(jié)果.

5 性能評估

5.1 實驗數(shù)據(jù)

本文采用復(fù)旦大學(xué)自然語言處理小組整理收集的文本分類語料庫*語料庫查載于自然語言處理與信息檢索共享平臺[EB/OL].2017-1-15,http://www.nlpir.org/?action-viewnews-itemid-103.作為訓(xùn)練集和測試集,從中選取六種類別的部分文檔作為訓(xùn)練集文檔和測試集文檔.選取情況如表2所示.

表2 測試集和訓(xùn)練集文檔選取情況Table 2 Testing set and training set document selection

5.2 實驗設(shè)置

本文實驗設(shè)置情況如下:

1)可行性驗證實驗.用來檢驗本文MapReduce機制對改進CHI方法是否有不良影響.實驗對象設(shè)置為:本文提出的改進CHI方法分別運行在普通PC機上和Hadoop單節(jié)點上.

2)性能對比實驗.用來檢驗本文提出的改進CHI方法的性能.對比實驗對象設(shè)置為:傳統(tǒng)CHI統(tǒng)計法、論文[12]提出的改進CHI方法(用CHI-F表示)、本文提出的改進CHI方法.

3)效率測試實驗.用來測試本文提出的改進CHI方法在Hadoop平臺上的效率.

實驗設(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.實驗中特征向量的維度為1000,分類方法KNN中的K取值為20.

5.3 評價指標

1)查準率用來反映文本分類的健全性,即分類結(jié)果的準確性[13],用P表示查準率,其計算公式如式(7)所示.

(7)

2)召回率用來反映正確分類的能力,用R表示召回率,其計算公式如式(8)所示.

(8)

3)F1值是綜合以上兩種評價標準對文本分類進行整體評價,其計算公式如式(9)所示.

(9)

4)加速比用來衡量程序并行化的性能[14],用Ts表示加速比,其計算公式如式(10)所示.

(10)

5.4 性能評估

可行性驗證實驗結(jié)果如表3所示.

表3 PC單機和MapReduce下文本的向量維度Table 3 Vector dimension in PC and mapreduce

分別將改進的CHI方法運行在Hadoop單節(jié)點平臺和一臺普通PC機上.通過表3中的實驗數(shù)據(jù)可以發(fā)現(xiàn),兩種環(huán)境下最終生成的文本向量維數(shù)差異很小.綜上所述,MapReduce

技術(shù)的引入并未對CHI方法在文本向量維度產(chǎn)生不良影響.

性能對比實驗結(jié)果如表4所示.

從表4中得到的三種CHI方法查準率和召回率,根據(jù)式(9)可以計算出各個方法的F1值,F1值對比結(jié)果如圖4所示.

表4 實驗結(jié)果及對比Table 4 Experimental results and comparison

由實驗數(shù)據(jù)可以看出:傳統(tǒng)CHI方法在本實驗數(shù)據(jù)集上的F1值最高也只達到62.56%,對于樣本較少的“醫(yī)學(xué)”、“歷史”小類預(yù)料,其F1值更低;CHI-F方法在本套數(shù)據(jù)集上的測試結(jié)果已有明顯改善,F1值較高時能達到79.38%,對于樣本較少的“醫(yī)學(xué)”、“歷史”,其F1值也有顯著提升;本文提出的CHI方法,F1值比其他兩種方法的F1值明顯提升,最高值幾乎能達到90%.結(jié)合表4發(fā)現(xiàn)傳統(tǒng)CHI方法中小類預(yù)料集F1值偏小是因為“醫(yī)學(xué)”和“歷史”的訓(xùn)練集相對于整個訓(xùn)練集的比重較小,在沒有過濾算法處理的情況下,將會選中訓(xùn)練集中大量外圍特征詞,導(dǎo)致分類效果不佳;CHI-F方法在一定程度上改善了小類預(yù)料集F1值偏低的現(xiàn)象;本文提出的CHI方法通過類內(nèi)頻數(shù)和類間方差的共軛修正,在小類預(yù)料集查準率、召回率、F1值上,均比CHI-F方法有進一步的提高.

圖5 系統(tǒng)加速比Fig.5 System speedup

效率測試實驗用來檢驗Hadoop集群中DataNode節(jié)點數(shù)目的增加是否對模型的性能產(chǎn)生影響.實驗觀察基于MapReduce的CHI文本特征選擇機制的實驗運行時間和加速比.其中,多節(jié)點Hadoop集群分別由3、6、9、12、15個DataNode節(jié)點組成.實驗結(jié)果如表5所示.

表5中的實驗運行時間是經(jīng)過多組實驗得出的平均值,根據(jù)式(10)計算出系統(tǒng)加速比,實驗結(jié)果如圖5所示.

表5 實驗運行時間Table 5 Experimental running time

由圖5可知,在初始階段當Hadoop節(jié)點數(shù)較少時,本文提出的基于MapReduce的CHI文本特征選擇機制加速比提升不明顯,當Hadoop節(jié)點數(shù)增加至9臺,加速比已有顯著提升,綜合來看,本文提出的優(yōu)化機制的加速比隨著DataNode節(jié)點的增加有顯著增長.

6 總結(jié)與展望

傳統(tǒng)的CHI方法雖然廣泛使用于文本分類中,但是算法忽略高頻特征詞和放大外圍特征詞權(quán)重的問題使得算法在實際的應(yīng)用中分類精確度偏低.本文針對上述問題,在改進傳統(tǒng)CHI方法的同時結(jié)合MapReduce技術(shù),提出一種基于MapReduce的CHI文本特征選擇機制.實驗結(jié)果表明,本機制不僅能有效提高文本分類精度,也提升了文本分類的效率.

本文提出的基于MapReduce的CHI文本特征選擇機制對小類預(yù)料集的分類精度雖然提高很多,但還有上升空間,未來考慮針對小類預(yù)料集以及含大量噪聲詞的預(yù)料集進行專門研究;同時,MapReduce技術(shù)是當前大數(shù)據(jù)應(yīng)用的核心,能否將本文MapReduce模型適配到其它算法中也是未來研究的另一個方向.