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

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

1 引 言

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

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

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

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

2 相關(guān)工作

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

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

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

3 研究背景

3.1 文本分類與特征選擇

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

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

3.2 MapReduce

MapReduce是一個大數(shù)據(jù)集的分布式處理平臺,具有高可用性、高可擴展性和高容錯性能.MapReduce模型集成多個計算機節(jié)點對海量數(shù)據(jù)并行處理[4].

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

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

3.3 互信息

互信息是信息論的重要概念,用來描述兩個事件集合之間的關(guān)聯(lián)性[6].兩個事件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)

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

(3)

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

(4)

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

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

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

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

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

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

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

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

4 改進的MapReduce互信息文本特征選擇機制

4.1 改進的互信息方法

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

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

(5)

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

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

(6)

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

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

(7)

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

(8)

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

(9)

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

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

(10)

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

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

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

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

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

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

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

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

輸出:Textvectorfile

1.Map1:

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

2.{

3.Foreach du∈W1do

5.MInew(C,t);

6.endfor

7.endfor

8. }

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

10.Map2:

//計算特征詞t對于每個類別(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)對于進入文本訓(xùn)練過程的每一個訓(xùn)練文本,通過第1個Mapreduce過程的Map1函數(shù)計算其與全部類別的互信息均值,得到<特征項,互信息值>的鍵值對< termID,Value >(第1行至第8行).

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

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

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

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

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

4.2.2 文本分類階段

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

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

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

算法2.文本分類算法

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

文檔d;特征項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)對于進入文本測試過程的每一個訓(xùn)練文本,通過本階段的Mapreduce過程中Map4函數(shù)以及訓(xùn)練階段得到的Text vector file,進行文本分類.其中,Map4函數(shù)的主體為KNN分類算法,執(zhí)行后經(jīng)過處理得到初始分類文件(第1行至第6行).

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

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

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

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

5 性能評價

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

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

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

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

5.2 實驗設(shè)置

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

圖5 實驗設(shè)置Fig.5 Experimental arrangement

三種實驗環(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.針對互信息特征選擇方法,選取1000維特征做特征向量.多節(jié)點Hadoop集群由配置相同的2、4、8、10臺、16臺節(jié)點組成.

5.3 評價指標(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),計算公式如式(11)所示.

(11)

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

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

5.4 實驗結(jié)果

選取實驗A和實驗B(或?qū)嶒濪和實驗E2)為一組,對比實驗結(jié)果,如表2所示.

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

序號類別PC單機下Maprduce下1Art1281302Medical16143Computer14134Educaton91945Sports3363306Law333341

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

選取實驗A和實驗D為一組,對比實驗結(jié)果,如表3所示.

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

序號類別MIMInew1aArt1283002Medical16753Computer143694Education911475Sport3361346Law333252

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

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

序號類別傳統(tǒng)互信息方法(MI)改進互信息方法(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 實驗運行時間
Table 5 Experimental running time

實驗號機器數(shù)運行時間(ms)實驗D126604實驗E126376218824413232實驗F86080105419163775

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

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

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

6 總結(jié)與展望

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

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

[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.

附中文參考文獻：

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

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

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

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

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