一種改進(jìn)的MapReduce互信息文本特征選擇機(jī)制

陶永才,趙國樺,石 磊,衛(wèi) 琳

1(鄭州大學(xué) 信息工程學(xué)院,鄭州 450001) 2(鄭州大學(xué) 軟件技術(shù)學(xué)院,鄭州 450002)

1 引 言

大數(shù)據(jù)時(shí)代引發(fā)的“數(shù)據(jù)挖掘風(fēng)暴”已經(jīng)進(jìn)入超速發(fā)展時(shí)期,文本分類是數(shù)據(jù)挖掘的重要環(huán)節(jié),而特征選擇又是文本分類的核心步驟.

特征選擇是根據(jù)文本中劃分好的特征詞條的重要程度,過濾掉那些不相關(guān)的或者冗余的特征詞條,保留那些對(duì)文本分類有意義的特征詞條[1].互信息(Mutual Information,MI)是信息論中的重要概念,人們把互信息廣泛運(yùn)用于文本分類,互信息成為了文本分類中最常用的特征選擇方法,在文本分類的特征選擇度量指標(biāo)中,互信息值表示特征項(xiàng)的值與文本類別的統(tǒng)計(jì)相關(guān)性以及特征詞之間的統(tǒng)計(jì)相關(guān)性.

MapReduce是Google公司提出的一種基于大規(guī)模數(shù)據(jù)集并行計(jì)算的編程模式,主要用于對(duì)海量數(shù)據(jù)的收集和處理,與傳統(tǒng)的計(jì)算模式相比,極大提升了性能,提高了效率.在當(dāng)今數(shù)據(jù)挖掘、新聞推薦、機(jī)器學(xué)習(xí)、互聯(lián)網(wǎng)服務(wù)等領(lǐng)域上廣泛使用[2].

針對(duì)傳統(tǒng)互信息算法,只考慮特征項(xiàng)出現(xiàn)在某類別文檔的頻數(shù),但是沒有考慮特征項(xiàng)總共出現(xiàn)了多少次,也沒有考慮特征項(xiàng)在文本中平均出現(xiàn)次數(shù),本文提出一種改進(jìn)的MapReduce互信息文本特征選擇機(jī)制,一方面對(duì)傳統(tǒng)互信息計(jì)算公式進(jìn)行改進(jìn),引入特征項(xiàng)的頻數(shù)和特征項(xiàng)的平均出現(xiàn)次數(shù),并借助熵的概念,對(duì)互信息公式進(jìn)行修正,提高互信息方法特征項(xiàng)選擇準(zhǔn)確度,從而提高分類精度.另一方面提出基于MapReduce的互信息文本特征選擇模型,將文本處理分為可并行的兩個(gè)階段:文本訓(xùn)練階段和文本分類階段,利用MapReduce模型對(duì)大規(guī)模數(shù)據(jù)處理的優(yōu)勢,優(yōu)化文本集訓(xùn)練以及分類,進(jìn)而提升系統(tǒng)的工作效率.

2 相關(guān)工作

傳統(tǒng)互信息算法效率較低,眾多研究針對(duì)于傳統(tǒng)互信息算法進(jìn)行改進(jìn),文獻(xiàn)[12]針對(duì)算法中負(fù)相關(guān)現(xiàn)象問題改進(jìn)了傳統(tǒng)互信息算法;文獻(xiàn)[13]提出了一種新的基于互信息的特征評(píng)價(jià)函數(shù)TFMIIE,有效避免偏向低頻特征詞;文獻(xiàn)[15]提出了一種基于互信息的無監(jiān)督的特征選擇方法(UFS-MI),在UFS-MI中,使用綜合考慮相關(guān)度和冗余度的特征選擇標(biāo)準(zhǔn)UmRMR(無監(jiān)督最小冗余最大相關(guān))來評(píng)價(jià)特征的重要性.

以上研究在一定程度上彌補(bǔ)了傳統(tǒng)互信息方法的不足,明顯地提升了處理效率.隨著MapReduce技術(shù)的出現(xiàn)和發(fā)展,借助MapReduce技術(shù)的優(yōu)勢,各種文本分類技術(shù)都有了階段性的進(jìn)步,實(shí)現(xiàn)了高效處理海量數(shù)據(jù)的能力.文獻(xiàn)[10,14]提出了云計(jì)算環(huán)境下樸素貝葉斯文本分類算法,將貝葉斯分類和MapReduce技術(shù)結(jié)合;文獻(xiàn)[16]提出一種基于MapReduce的分布式聚類方法,該方法對(duì)傳統(tǒng)K-means算法進(jìn)行了改進(jìn),采用基于信息損失量的相似性度量,相對(duì)于傳統(tǒng)的聚類算法,性能上有顯著提升.

上述研究中,各種改進(jìn)傳統(tǒng)互信息的策略殊途同歸,在一定程度上都能提升互信息方法的性能.雖然有不少基于Mapreduce的文本分類技術(shù),但對(duì)于互信息和MapReduce技術(shù)的結(jié)合,還沒有得到過多關(guān)注和研究.本文創(chuàng)新性地將互信息理念和Mapreduce技術(shù)結(jié)合,同時(shí)優(yōu)化傳統(tǒng)互信息方法,不但能提升系統(tǒng)的效率,也將從根本上提高文本分類的精度.

3 研究背景

3.1 文本分類與特征選擇

文本分類(Text Categorization)以預(yù)先給定的分類類別為標(biāo)準(zhǔn),根據(jù)文本的主要內(nèi)容,將文本劃分到某一個(gè)或者多個(gè)分類類別中.借助于文本分類系統(tǒng),用戶可以更方便快捷地查找需要的信息[3].近年來,文本自動(dòng)分類技術(shù)已經(jīng)逐漸與搜索引擎、信息推送、信息過濾等信息處理技術(shù)相結(jié)合,有效地提高了信息服務(wù)的質(zhì)量.一般的文本分類過程如圖1所示.文本分類的核心之一就是特征選擇.典型的特征選擇算法有基于互信息(MI)、基于信息增益(IG)、文檔頻數(shù)(DF)計(jì)算等.特征選擇的目的是對(duì)高維文本進(jìn)行降維處理,降低文本分類的復(fù)雜度.特征選擇的優(yōu)勢在于直接從特征項(xiàng)中選擇,避免生成新特征而消耗大量時(shí)間和空間上的資源.

圖1 標(biāo)準(zhǔn)文本分類過程Fig.1 Standard text categorization process

3.2 MapReduce

MapReduce是一個(gè)大數(shù)據(jù)集的分布式處理平臺(tái),具有高可用性、高可擴(kuò)展性和高容錯(cuò)性能.MapReduce模型集成多個(gè)計(jì)算機(jī)節(jié)點(diǎn)對(duì)海量數(shù)據(jù)并行處理[4].

MapReduce主要包括Map階段(映射)和Reduce階段(歸約)[5,7,8],工作過程如圖2所示.用戶預(yù)先給定一個(gè)Map函數(shù)和Reduce函數(shù),原始數(shù)據(jù)經(jīng)過預(yù)處理被分割成多個(gè)數(shù)據(jù)塊并以鍵值對(duì)形式保存在不同節(jié)點(diǎn)里,經(jīng)過Map階段的Map函數(shù)處理后,生成中間值,然后經(jīng)過Reduce階段的Reduce函數(shù)把具有相同Key值的中間值合并在一起,最后輸出.

圖2 MapReduce工作流程Fig.2 Workflow of MapReduce

3.3 互信息

互信息是信息論的重要概念,用來描述兩個(gè)事件集合之間的關(guān)聯(lián)性[6].兩個(gè)事件X和Y的互信息定義為:

I(X,Y)=H(X)+H(Y)-H(X,Y)

(1)

其中,H(X)和H(Y)是邊緣熵,H(X,Y)是聯(lián)合熵,定義為:

H(X,Y)=-∑p(x,y)log(p(x,y))

(2)

在特征選擇中運(yùn)用互信息的思想,即特征項(xiàng)t和類別ci的互信息MI(t,Ci)指本特征項(xiàng)和類別ci的關(guān)聯(lián)程度,如式(3)所示.

(3)

其中,p(t,ci)指特征項(xiàng)t和類別ci同時(shí)出現(xiàn)的概率(即特征項(xiàng)出現(xiàn)在類別ci中),p(t)指特征項(xiàng)t在整個(gè)訓(xùn)練文本集合中出現(xiàn)的概率,p(ci)指類別Ci的文檔占整個(gè)訓(xùn)練文本集合的比率.由于分類類別一般會(huì)有很多,記分類類別的個(gè)數(shù)為m,用平均關(guān)聯(lián)程度表示最后計(jì)算的互信息值,則特征項(xiàng)t與各個(gè)類別的平均關(guān)聯(lián)程度MI(t,Ci)可表示為式(4).

(4)

在文本分類中,傳統(tǒng)的互信息特征選擇的基本步驟為:

1)對(duì)目標(biāo)文本進(jìn)行預(yù)處理:分詞,去停用詞;

2)利用傳統(tǒng)的互信息計(jì)算公式,計(jì)算每個(gè)特征項(xiàng)與各個(gè)類別的平均關(guān)聯(lián)程度;

3)在所有特征項(xiàng)中選擇一定量的特征項(xiàng),選擇依據(jù)是根據(jù)特征項(xiàng)與各個(gè)類別的平均關(guān)聯(lián)程度的高低.

3.4 傳統(tǒng)互信息方法的不足

傳統(tǒng)的互信息特征選擇方法中,基于p(t,ci)的存在,只考慮了特征項(xiàng)的文檔頻度,即只考慮特征項(xiàng)t出現(xiàn)在類別ci的文檔數(shù),但是沒有考慮特征項(xiàng)出現(xiàn)了多少次,即特征項(xiàng)的頻數(shù).在式(3)中沒有考慮到特征項(xiàng)的頻數(shù)這個(gè)參數(shù),則會(huì)有以下情況出現(xiàn):

可能存在兩個(gè)特征項(xiàng)t1、t2,特征項(xiàng)t1的頻數(shù)遠(yuǎn)大于特征項(xiàng)t2的頻數(shù),由于沒有特征項(xiàng)的頻數(shù)的約束,在用互信息計(jì)算公式計(jì)算時(shí),導(dǎo)致t1、t2的互信息權(quán)值相等,在排序中隨機(jī)選擇權(quán)值相等的特征項(xiàng)中的一個(gè),很大可能過濾掉頻數(shù)高的特征項(xiàng),將稀有的低頻特征項(xiàng)選作最終特征項(xiàng).

當(dāng)然,如果單純地直接引入特征項(xiàng)的頻數(shù),沒有考慮特征項(xiàng)在文本中平均出現(xiàn)次數(shù),可能會(huì)出現(xiàn)以下情況:在個(gè)別文本中出現(xiàn)次數(shù)多的特征項(xiàng)的互信息值小于在多數(shù)文本中偶爾出現(xiàn)的特征項(xiàng)的互信息值.以至于對(duì)于一個(gè)類別ci,無法選擇特征項(xiàng)t作為它的一個(gè)候選特征項(xiàng),這個(gè)特征項(xiàng)t可能僅僅是在這個(gè)類別中出現(xiàn)的次數(shù)較高.

4 改進(jìn)的MapReduce互信息文本特征選擇機(jī)制

4.1 改進(jìn)的互信息方法

針對(duì)互信息的不足,本文通過引入特征項(xiàng)的頻數(shù)和特征項(xiàng)的平均出現(xiàn)次數(shù),同時(shí),基于信息熵的概念,引入信息熵對(duì)互信息的計(jì)算公式加以修正,從而提高互信息值的有效性和準(zhǔn)確度.

由于在傳統(tǒng)的互信息選擇方法中,只考慮了特征項(xiàng)的文檔頻度,即只考慮特征項(xiàng)t出現(xiàn)在類別ci的文檔數(shù),但是沒有考慮特征項(xiàng)出現(xiàn)了多少次,即特征項(xiàng)的頻數(shù).本文引入特征項(xiàng)的頻數(shù)這個(gè)概念,用來表示特征項(xiàng)在某個(gè)類別中出現(xiàn)的次數(shù)和特征項(xiàng)在整個(gè)文本集合中出現(xiàn)的次數(shù)的比值,記作Q(qt),若類別ci有文檔(d1,…，dk,…，dn),則有:

(5)

其中,qt表示特征項(xiàng)在類別ci的文檔dk中出現(xiàn)的次數(shù),n表示類別ci中的文本總數(shù),m表示訓(xùn)練集中類別總數(shù).由式(5)可知,Q(qt)越大,說明特征項(xiàng)在某個(gè)類別中出現(xiàn)的次數(shù)越多,則這個(gè)特征項(xiàng)選為候選特征項(xiàng)的可能性就越大.

再引入特征項(xiàng)的平均出現(xiàn)次數(shù),來彌補(bǔ)引入特征項(xiàng)的頻數(shù)的不足:沒有考慮特征項(xiàng)在文本中平均出現(xiàn)次數(shù),導(dǎo)致可能會(huì)出現(xiàn)在個(gè)別文本中出現(xiàn)次數(shù)多的特征項(xiàng)的互信息值小于在多數(shù)文本中偶爾出現(xiàn)的特征項(xiàng)的互信息值.記特征項(xiàng)的平均出現(xiàn)次數(shù)為V(qt),若類別ci有文檔(d1,…,dk,…,dn),則有:

(6)

其中,qt表示特征項(xiàng)在類別ci的文檔dk中出現(xiàn)的次數(shù),n表示類別ci中的文本總數(shù).由式(6)可知,V(qt)越大,表明這個(gè)特征項(xiàng)越能當(dāng)這個(gè)類別的候選特征項(xiàng).

考慮特征項(xiàng)的頻數(shù)和特征項(xiàng)的平均出現(xiàn)次數(shù),互信息計(jì)算公式可表示為:

(7)

考慮分類類別有m個(gè),并用平均關(guān)聯(lián)程度表示最后計(jì)算的互信息值,則有:

(8)

熵是統(tǒng)計(jì)熱力學(xué)中表示目標(biāo)系統(tǒng)的混亂程度的物理量[9],為了讓互信息值更有效,準(zhǔn)確度更高,借助于信息熵的概念,特征項(xiàng)t在類別ci中的信息熵為:

(9)

其中,P(ci|t)是含有特征項(xiàng)t的類別ci的文本數(shù)和含有特征項(xiàng)t的文本數(shù)的比值.信息熵IE(C|t)描述了以類別ci為系統(tǒng),特征項(xiàng)t為事件的一個(gè)量,表示文本分類的混亂程度(即不確定性).IE(C|t)越小,系統(tǒng)的混亂程度越小,確定性越大,特征項(xiàng)t對(duì)類別ci分類的影響越大.

在式(8)中引入信息熵作為互信息計(jì)算的修正,用新的記號(hào)MInew(C,t)表示改進(jìn)過的互信息計(jì)算公式,如式(10)所示.

(10)

4.2 基于MapReduce的互信息文本特征選擇

基于MapReduce的互信息文本特征選擇模型分為兩部分:文本訓(xùn)練階段和文本分類階段.

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

圖3是基于MapReduce的文本訓(xùn)練模型.首先選擇合適的訓(xùn)練文本集進(jìn)行預(yù)處理:分詞、去停用詞.通過VSM模型建立維向量來表示預(yù)處理后的特征項(xiàng).經(jīng)過預(yù)處理和向量處理的訓(xùn)練文本集便可以進(jìn)入文本訓(xùn)練過程.

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

文本訓(xùn)練模型包含3個(gè)MapReduce過程,前兩個(gè)過程可以在資源節(jié)點(diǎn)上同時(shí)運(yùn)作,第1個(gè)MapReduce過程用來產(chǎn)生訓(xùn)練文本集的特征項(xiàng),公式(10)是Map階段函數(shù)的核心;第2個(gè)MapReduce過程用來產(chǎn)生訓(xùn)練文本集各個(gè)類別的特征項(xiàng),公式(7)是這過程中Map階段函數(shù)的核心;第3個(gè)MapReduce過程用來產(chǎn)生訓(xùn)練文本集各個(gè)類別的特征向量,利用過程(1)、(2)的結(jié)果,在過程(1)生成的訓(xùn)練文本集的特征項(xiàng)中匹配過程(2)中訓(xùn)練文本集各個(gè)類別的特征項(xiàng),匹配成功(即發(fā)現(xiàn)相同特征項(xiàng))后便可選為最終的訓(xùn)練文本集對(duì)應(yīng)類別的特征項(xiàng)向量,作為訓(xùn)練庫供下一步使用.

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

輸入:訓(xùn)練文本集W1;類別C;文檔d;特征項(xiàng)t

輸出:Textvectorfile

1.Map1:

//計(jì)算特征詞t對(duì)于全部類別(C)的互信息值均值

2.{

3.Foreach du∈W1do

5.MInew(C,t);

6.endfor

7.endfor

8. }

9. Sort( )→Ts={MI1,MI2,…,MIn};

10.Map2:

//計(jì)算特征詞t對(duì)于每個(gè)類別(Ci)的互信息值

11.{

12.Foreach du∈Cido

14. MI(t,Ci);

15.endfor

16.endfor

17. }

18.Foreach Cido

19.Sort( )→Tv={MI1,MI2,…,MIn};

20.endfor

21.Map3:

22. Match the same tjin Map1 and Map2;

23.OutputText vector file;

文本訓(xùn)練算法如算法1所示:

1)對(duì)于進(jìn)入文本訓(xùn)練過程的每一個(gè)訓(xùn)練文本,通過第1個(gè)Mapreduce過程的Map1函數(shù)計(jì)算其與全部類別的互信息均值,得到<特征項(xiàng),互信息值>的鍵值對(duì)< termID,Value >(第1行至第8行).

2)將步驟(1)得到的鍵值對(duì)< termID,Value >經(jīng)過處理后,以Value為分類標(biāo)準(zhǔn)降序排列,得到訓(xùn)練文本集的特征項(xiàng)序列Ts={MI1,MI2,…,MIn}(第9行).

3)通過第2個(gè)Mapreduce過程,計(jì)算特征詞對(duì)于每個(gè)類別的互信息值,得到以<特征項(xiàng),互信息值>的鍵值對(duì)< termID,Value >(第10行至第17行).

4)將步驟(3)得到的鍵值對(duì)< termID,Value >經(jīng)過處理后,同樣的,以Value為分類標(biāo)準(zhǔn)降序排列,得到每個(gè)類別的特征項(xiàng)序列Tv={MI1,MI2,…,MIn}(第18行至第20行).

5)通過第3個(gè)Mapreduce過程,執(zhí)行Map3函數(shù),在Map1和Map2中匹配相同的特征詞,得到訓(xùn)練文本集各個(gè)類別特征向量.(第21行至第22行).

6)輸出Text vector file(第23行).

4.2.2 文本分類階段

圖4所示為基于MapReduce的文本分類模型.

基于MapReduce的文本訓(xùn)練模型已生成文本的訓(xùn)練庫,當(dāng)給出合適的測試文本集時(shí),使用一個(gè)MapReduce過程,以訓(xùn)練庫的文本向量為訓(xùn)練樣例,對(duì)輸入過來的測試用例集(測試文本集)進(jìn)行分類.其中,Map階段就是分類的階段,本文使用KNN算法作為Map階段的核心函數(shù).KNN算法思想如下:對(duì)于給定待分類的文本文檔,經(jīng)過預(yù)處理,用特征向量(t1…tk…tn)表示,在訓(xùn)練庫中找到與它最近的K個(gè)近鄰,則待分類文本屬于這K個(gè)近鄰中大多數(shù)屬于的那一類.之后經(jīng)過Reduce階段將Map階段的結(jié)果按類別輸出.

圖4 基于MapReduce的文本分類模型Fig.4 Text categorization model based on MapReduce

算法2.文本分類算法

輸入:Textvectorfile;測試文本集W2;類別C;

文檔d;特征項(xiàng)t

輸出:Classifieddocuments

1.Map4:

//分類測試文本集W2

2.{

3.Foreach du∈W2do

4. KNN();

5. Get an initial classification file(ICF);

//通過KNN分類后,得到初始分類文件

6. }

7.Reduce4:

8.{

9.Foreach cj∈Wdo

10. Match the same category in the initial classification file;

11. ICFi→FileCz{LR1,LR2,…,LRn};

12.endfor

13. }

14.OutputClassified documents;

文本分類算法如算法2所示:

1)對(duì)于進(jìn)入文本測試過程的每一個(gè)訓(xùn)練文本,通過本階段的Mapreduce過程中Map4函數(shù)以及訓(xùn)練階段得到的Text vector file,進(jìn)行文本分類.其中,Map4函數(shù)的主體為KNN分類算法,執(zhí)行后經(jīng)過處理得到初始分類文件(第1行至第6行).

2)步驟(1)得到的初始分類文件,是<類別,文檔>的鍵值對(duì)< ClassID,DocID >集.在本步驟的Reduce4函數(shù)中,將初始分類文件,以ClassID為分類標(biāo)準(zhǔn)進(jìn)行分類,得到基于不同類別的文本序列FileCz{LR1,LR2,…,LRn}(第7行至第13行).

3)輸出Classified documents(第14行).

在算法1和算法2中,第1個(gè)Mapreduce過程和第2個(gè)Mapreduce過程可在給定的節(jié)點(diǎn)上分布式運(yùn)行,并且對(duì)于每一個(gè)Mapreduce過程中的Map階段和Reduce階段,也可以在給定的多個(gè)節(jié)點(diǎn)上并行執(zhí)行,因此可大幅度消減時(shí)間上的復(fù)雜度,提升系統(tǒng)效率.

1自然語言處理與信息檢索共享平臺(tái)[EB/OL].2017-1-15,http://www.nlpir.org/?action-viewnews-itemid-103.2實(shí)驗(yàn)A、B與實(shí)驗(yàn)D、E的實(shí)驗(yàn)?zāi)康南嗤瑢?shí)驗(yàn)結(jié)果類似，鑒于篇幅問題，本文只列舉實(shí)驗(yàn)A、B的實(shí)驗(yàn)結(jié)果.

5 性能評(píng)價(jià)

5.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用“自然語言處理與信息檢索共享平臺(tái)1”提供的復(fù)旦大學(xué)收集的文本分類語料庫作為訓(xùn)練集和測試集,包含Art、Medical、Education、Computer等20個(gè)類別.從中選取部分類別作為實(shí)驗(yàn)所需的訓(xùn)練文本集和測試文本集,選取情況如表1所示.

表1 抽取語料庫樣本分布
Table 1 Corpus drawn sample distribution

ArtMedicalComputerEducationSportsLaw訓(xùn)練集200200200200200200測試集200200200200200200

5.2 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)在兩個(gè)條件下的三種環(huán)境里進(jìn)行性能測試.第一個(gè)條件是基于傳統(tǒng)的互信息方法,分別在普通的PC單機(jī)、Hadoop集群(單節(jié)點(diǎn))、Hadoop集群(多節(jié)點(diǎn))三種環(huán)境下進(jìn)行試驗(yàn),第二個(gè)條件是基于改進(jìn)的互信息方法,也在相同的三種環(huán)境下進(jìn)行試驗(yàn).實(shí)驗(yàn)設(shè)置如圖5所示.

圖5 實(shí)驗(yàn)設(shè)置Fig.5 Experimental arrangement

三種實(shí)驗(yàn)環(huán)境采用相同的基本配置,配置如下:CPU為3.60Hz,內(nèi)存為8G,硬盤為1T,操作系統(tǒng)為Ubuntu-15.10,Hadoop版本為2.6.0,所用到代碼編譯環(huán)境為JDK-1.8.使用的KNN算法設(shè)置K值為8.針對(duì)互信息特征選擇方法,選取1000維特征做特征向量.多節(jié)點(diǎn)Hadoop集群由配置相同的2、4、8、10臺(tái)、16臺(tái)節(jié)點(diǎn)組成.

5.3 評(píng)價(jià)指標(biāo)

準(zhǔn)確率:系統(tǒng)正確分類出某類別的文本數(shù)和系統(tǒng)分類的文本總數(shù)比值,該指標(biāo)反映系統(tǒng)正確分類能力的高低.

召回率:系統(tǒng)正確分類出某類別的文本數(shù)和系統(tǒng)分類的某類別文本總數(shù),該指標(biāo)反映系統(tǒng)分類能力的高低.

F1值:用于綜合反映整體的指標(biāo),計(jì)算公式如式(11)所示.

(11)

其中,P表示準(zhǔn)確率,R表示召回率.

加速比:系統(tǒng)在改進(jìn)前后處理同一任務(wù)所用時(shí)間的比例,該指標(biāo)反映系統(tǒng)執(zhí)行效率的高低.

5.4 實(shí)驗(yàn)結(jié)果

選取實(shí)驗(yàn)A和實(shí)驗(yàn)B(或?qū)嶒?yàn)D和實(shí)驗(yàn)E2)為一組,對(duì)比實(shí)驗(yàn)結(jié)果,如表2所示.

表2 PC單機(jī)和Mapreduce下文本的向量維度
Table 2 Vector dimension in PC and Mapreduce

序號(hào)類別PC單機(jī)下Maprduce下1Art1281302Medical16143Computer14134Educaton91945Sports3363306Law333341

由表2實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn),基于MapReduce的互信息文本特征選擇和傳統(tǒng)互信息特征選擇得到的文本向量維數(shù)相差無幾.由此可見,引入MapReduce技術(shù)對(duì)互信息特征選擇在基本的文本向量選擇性能方面未造成不良影響.

選取實(shí)驗(yàn)A和實(shí)驗(yàn)D為一組,對(duì)比實(shí)驗(yàn)結(jié)果,如表3所示.

表3 傳統(tǒng)方法和改進(jìn)方法的文本向量維度
Table 3 Text vector dimensions of traditional and improved

序號(hào)類別MIMInew1aArt1283002Medical16753Computer143694Education911475Sport3361346Law333252

由表3實(shí)驗(yàn)數(shù)據(jù)可以明顯地看出使用傳統(tǒng)互信息方法得到的文本向量維數(shù)很不均勻,Medical和Computer類別的訓(xùn)練文本各有200篇,但是選取的特征詞只有十幾個(gè),這會(huì)對(duì)后期測試文本的分類有很大影響.Sports和Law類別的特征項(xiàng)相對(duì)較多,在后期的文本分類中,準(zhǔn)確率可能會(huì)相對(duì)提高.基于改進(jìn)互信息方法得到的向量維度相對(duì)均衡.結(jié)合表4發(fā)現(xiàn)Sports類別使用傳統(tǒng)互信息方法得到的特征項(xiàng)比使用改進(jìn)互信息方法得到的特征項(xiàng)多,但是準(zhǔn)確率卻不如改進(jìn)互信息方法,特選取Sports類別進(jìn)行分析.傳統(tǒng)互信息方法相對(duì)于Sports類別得到的特征項(xiàng)雖然很多,但其中包含了關(guān)聯(lián)度并不是很高的詞,如:防守、出擊、光速、去年底、整治、輔助、艱苦等等,這類詞會(huì)對(duì)分類結(jié)果產(chǎn)生很大影響.反觀采用改進(jìn)互信息方法選到的特征項(xiàng)雖然少,但是到100維,特征項(xiàng)仍明顯和Sports相關(guān),如:110米欄、體能、三雙等等.使得后期的文本分類能保持較高的準(zhǔn)確率.

表4 實(shí)驗(yàn)結(jié)果及對(duì)比
Table 4 Experimental results and comparison

序號(hào)類別傳統(tǒng)互信息方法(MI)改進(jìn)互信息方法(MInew)準(zhǔn)確率%招回率%F1值%準(zhǔn)確率%招回率%F1值%1Art42．6851．2246．5669．5785．8176．842Medical24．5328．1726．2266．2678．4671．843Computer21．1826．4529．7783．4484．2983．864Education37．5936．5637．0775．1861．5767．705Sports53．6651．2852．4478．6181．0979．836Law62．23366．5564．3282．8678．0480．38

表5 實(shí)驗(yàn)運(yùn)行時(shí)間
Table 5 Experimental running time

實(shí)驗(yàn)號(hào)機(jī)器數(shù)運(yùn)行時(shí)間(ms)實(shí)驗(yàn)D126604實(shí)驗(yàn)E126376218824413232實(shí)驗(yàn)F86080105419163775

為測試基于MapReduce的改進(jìn)互信息文本特征選擇機(jī)制的加速比性能,選取實(shí)驗(yàn)D和實(shí)驗(yàn)E以及實(shí)驗(yàn)F為一組,多次實(shí)驗(yàn),對(duì)比實(shí)驗(yàn)結(jié)果,用來驗(yàn)證Hadoop集群中節(jié)點(diǎn)數(shù)目增加時(shí)對(duì)模型的性能影響.Hadoop集群多節(jié)點(diǎn)分別采用2臺(tái)、4臺(tái)、8臺(tái)、10臺(tái)、16臺(tái)同配置的節(jié)點(diǎn).實(shí)驗(yàn)D、實(shí)驗(yàn)E、實(shí)驗(yàn)F執(zhí)行時(shí)間如表5所示,圖6所示為由表5運(yùn)行時(shí)間數(shù)據(jù)計(jì)算的系統(tǒng)加速比.

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

由表3、表4和表5可知,與傳統(tǒng)的互信息特征選擇方法相比,基于MapReduce的改進(jìn)互信息文本特征選擇機(jī)制不僅提高了分類的準(zhǔn)確度,而且明顯提高了系統(tǒng)的執(zhí)行效率.由圖6可知,當(dāng)增加Hadoop節(jié)點(diǎn)數(shù),基于MapReduce的改進(jìn)互信息文本特征選擇機(jī)可以達(dá)到近似線性的加速比.

6 總結(jié)與展望

傳統(tǒng)的基于互信息的特征文本選擇在文本分類中比較常用,但是因理論公式過于簡單,實(shí)際應(yīng)用中分類準(zhǔn)確率較為偏低.本文在理論上闡述了傳統(tǒng)互信息方法的不足,提出一種改進(jìn)的互信息特征文本選擇方法,同時(shí)結(jié)合MapReduce技術(shù),提出一種基于MapReduce的改進(jìn)互信息文本特征選擇機(jī)制.實(shí)驗(yàn)表明該機(jī)制可以明顯提高文本分類的精度,而且顯著提升執(zhí)行效率.

鑒于本文提出的改進(jìn)的MapReduce互信息文本特征選擇機(jī)制沒有針對(duì)特殊文本進(jìn)行特殊處理,例如,現(xiàn)實(shí)中所用到的文本可能包含提綱或者標(biāo)題.未來研究考慮針對(duì)帶有提綱或者標(biāo)題的文本改進(jìn)算法,提取提綱或標(biāo)題的關(guān)鍵字,提高關(guān)鍵字在分類時(shí)的權(quán)重,從而提升此類文本分類的準(zhǔn)確率.此外,文本分類方法和Hadoop平臺(tái)結(jié)合是未來本領(lǐng)域發(fā)展趨勢,所以本文提到的Mapreduce模型能否移植到其他分類方法上、性能是否有所提升,也是下一步研究的重點(diǎn).

[1] Dash M,Liu H.Feature selection for classification[J].Intelligent Data Analysis,1997,1(1):131-156.

[2] Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.

[3] Li Yun,Lu Bao-liang.Feature selection based on loss-margin of nearest neighbor classification[J].Pattern Recognition,2009,42(9):1914-1921.

[4] Mashayekhy L,Nejad M,Grosu D,et al.Energy-aware scheduling of MapReduce jobs[J].IEEE International Congress on Big Data,2014,26(10):32-39.

[5] Han Lei,Sun Xu-zhan,Wu Zhi-chuan,et al.Optimization study on sample based partition on MapReduce[J].Journal of Computer Research and Development,2013,50(Sup.):77-84.

[6] Zhao Zheng,Wang Lei,Liu Huan,et al.On similarity preserving feature selection[J].IEEE Transactions on Knowledge & Data Engineer,2013,25(3):619-632.

[7] Neil Gunther,Paul Puglia,Kristofer Tomasette.Hadoop superlinear scalability[J].Communications of the ACM,2015,58(4):46-55.

[8] Fabrizio Marozzo,Domenico Talia,Paolo Trunfio.P2P-MapReduce:parallel data processing in dynamic cloud environments[J].Journal of Computer and System Sciences,2012,78(5):1382-1402.

[9] Howard Barnum,Jonathan Barrett,Lisa Orloff Clark,et al.Entropy and information causality ingeneral probabilistic theories[J].New Journal of Physics,2010,12,033024.

[10] Feng Guo-zhong,Guo Jian-hua,Jing Bing-yi,et al.Feature subset selection using naive Bayes for text classification[J].Pattern Recognition Letters,2015,65:109-115.

[11] Liu Z,Zhang Q,Zhan M F,et al.Dreams:dynamic resource allocation for mapreduce with data skew[J].Integrated Network Management (IM),IFIP/IEEE International Symposium on,2015:18-26.

[12]Xin Zhu,Zhou Ya-jian.Study and improvement of mutual information for feature selection in text categorization[J].Journal of Computer Applications,2013,(S2):116-118+152.

[13]Cheng Wei-qing,Tang Xuan.A text feature selection method using the improved mutual information and information entropy[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science),2013,(5):63-68.

[14]Jiang Xiao-ping,Li Cheng-hua,Xiang Wen,et al.Naive Bayesian text classification algorithm in cloud computing environment[J].Journal of Computer Application,2011,(9):2551-2554+2566.

[15]Xu Jun-ling,Zhou Yu-ming,Chen Lin,et al.An unsupervised feature selection approach based on mutual information[J].Journal of Computer Research and Development,2012,(2):372-382.

[16]Li Zhao,Li Xiao,Wang Chun-mei,et al.Text clustering method study based on mapreduce[J].Computer Science,2016,(1):246-250+269.

附中文參考文獻(xiàn)：

[12] 辛 竹,周亞建.文本分類中互信息特征選擇方法的研究與算法改進(jìn)[J].計(jì)算機(jī)應(yīng)用,2013,(S2):116-118+152.

[13] 成衛(wèi)青,唐 旋.一種基于改進(jìn)互信息和信息熵的文本特征選擇方法[J].南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,(5):63-68.

[14] 江小平,李成華,向 文,等.云計(jì)算環(huán)境下樸素貝葉斯文本分類算法的實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用,2011,(9):2551-2554+2566.

[15] 徐峻嶺,周毓明,陳 林,等.基于互信息的無監(jiān)督特征選擇[J].控制與決策,2012,(2):372-382.

[16] 李 釗,李 曉,王春梅,等.一種基于MapReduce的文本聚類方法研究[J].計(jì)算機(jī)科學(xué),2016,(1):246-250+269.