張延祥,潘海俠
(北京航空航天大學(xué) 軟件學(xué)院,北京 100191)
?
一種基于區(qū)分能力的多類不平衡文本分類特征選擇方法
張延祥,潘海俠
(北京航空航天大學(xué) 軟件學(xué)院,北京 100191)
文本分類中的不平衡數(shù)據(jù)問題在現(xiàn)實應(yīng)用中比較普遍。傳統(tǒng)的特征選擇方法在不平衡問題上傾向于多數(shù)類而忽略稀有類。針對這種傾向性該文提出了一種主導(dǎo)性分析量化方法,并基于對該方法的優(yōu)化提出了一種基于類別區(qū)分能力的特征選擇方法,即DA(Discriminative Ability)方法,該方法使用文檔概率的最小絕對值差作為評分標準,一定程度上保證了特征選擇在稀有類與多數(shù)類上的公平性。實驗表明,DA優(yōu)于CHI、IG、DFICF,尤其在F1宏平均指標上,DA在不平衡問題上能夠取得更好的降維效果。
文本分類;不平衡問題;特征選擇;主導(dǎo)性分析;區(qū)分能力
互聯(lián)網(wǎng)的快速發(fā)展使得信息呈現(xiàn)爆發(fā)式增長的態(tài)勢,如何有效管理這些數(shù)據(jù)成為當(dāng)前的熱點問題。文本分類作為海量數(shù)據(jù)管理的關(guān)鍵技術(shù),在信息檢索、數(shù)據(jù)挖掘、輿情監(jiān)測等方面均有著廣泛應(yīng)用。
近年來,基于機器學(xué)習(xí)的分類方法被應(yīng)用到文本分類中,取得了很好的效果。但在實際應(yīng)用中,數(shù)據(jù)集分布偏斜仍是一個亟待解決的問題[1],尤其在具有高維特點的文本分類問題上。
數(shù)據(jù)集分布不平衡問題一般是指樣本在類別間可能存在數(shù)量級的差別,在這種情況下,樣本無法準確地反映整個空間的類別分布,特征降維方法與分類算法都傾向于被大類主導(dǎo)而忽略小類,是導(dǎo)致分類效果不理想的重要因素。有很多種策略可以對不平衡問題進行改進,如重采樣技術(shù)、新的分類策略、更好的效果評估方法等[1]。本文從特征選擇的角度出發(fā),針對不平衡問題下的特征選擇方法存在的缺陷進行改進。
特征選擇是文本分類的重要步驟,直接影響到模型的構(gòu)建與分類的性能,因而通過改進特征選擇方法來解決不平衡問題是可行的。特征選擇方法應(yīng)用于分類問題上有很多優(yōu)勢,比如分類模型的快速構(gòu)建、減小過擬合的概率、降低內(nèi)存與硬盤的占用、提高處理速度等;劣勢在于可能會過濾掉一些重要的特征,降低分類效果[2]。
本文對不平衡數(shù)據(jù)集下特征選擇方法的特點進行了研究,分析了如下兩個問題。
a) 不平衡數(shù)據(jù)集下特征選擇方法傾向于被大類主導(dǎo)而忽略小類,如何定義與量化“主導(dǎo)”?
b) 如果存在著一種可以較好地解決不平衡問題的特征選擇方法,那么該方法會有什么樣的特點?
針對以上問題進行研究后,本文提出了一種基于區(qū)分能力的特征選擇方法,一定程度上符合本文對問題b的解答,實驗表明,該方法在不平衡問題上達到了比傳統(tǒng)特征選擇方法更好的分類效果。
本文的其余內(nèi)容安排如下,第2節(jié)對特征降維尤其是特征選擇方法的研究成果進行了介紹;第3節(jié)對不平衡問題的研究現(xiàn)狀進行了總結(jié);第4節(jié)對不平衡數(shù)據(jù)集下的特征選擇的特點進行了探討,對主導(dǎo)性進行了定義與量化分析;第5節(jié)提出了基于區(qū)分能力的特征選擇方法;第6節(jié)對第4、5節(jié)提出的假設(shè)與方法進行實驗驗證;第7節(jié)為結(jié)論與展望。
2.1 特征降維方法分類
根據(jù)選擇特征集合方式的不同,特征降維方法可以分為兩類,特征選擇和特征抽取。特征選擇一般是依據(jù)某個準則,從原始特征集合中選取最能反映類別統(tǒng)計特性的特征,即從集合中選擇一個子集;特征抽取則是基于特征之間的語義相關(guān)性、類別特征集對類內(nèi)文本聚合程度、類間離散程度的影響力等方面考量而對文本特征集的一種壓縮[3]。
常見的特征選擇方法包括文檔頻度(DF)、互信息(MI)、信息增益(IG)、統(tǒng)計量(CHI)、期望交叉熵、文本證據(jù)權(quán)、幾率比等。而常見的特征抽取方法則包括主成分分析、隱含語義索引、非負矩陣分解等。
本文所提出的方法是一種特征選擇方法。
2.2 特征選擇方法
本節(jié)介紹針對主要特征選擇方法的研究成果,各個主要特征選擇方法的計算公式參考文獻[4],本節(jié)不再贅述。
自從機器學(xué)習(xí)技術(shù)被成功應(yīng)用于文本分類以來,針對特征選擇方法的研究與改進越來越多且日趨成熟。對特征選擇方法的研究主要集中在以下三個方面。
第一,針對各種現(xiàn)有的成熟方法進行性能對比,文獻[4]總結(jié)了IG、MI、CHI、DF、TS五種特征選擇方法的分類性能,發(fā)現(xiàn)IG和CHI是較優(yōu)的特征選擇方法,在容許少量性能損失的情況下,DF則有較好的擴展性與計算性能。文獻[5]則對100余種特征選擇算法的變體進行了比較,得到了CHI效果最好但在低頻詞上不可信等結(jié)論。文獻[6]將主要的特征選擇方法在中文語料上重新實驗,得到了與文獻[5]相似的結(jié)論,即將CHI與IG等與DF組合形成更好地特征選擇方法。
其次,不同于組合傳統(tǒng)方法,有些研究將其他原則引入到傳統(tǒng)方法中作為改進,也達到了較好的效果。文獻[7]將概念特征引入,提出了基于概念屏蔽層的特征選擇方法,通過概念統(tǒng)計和語義層次分析的方法,能夠更好地利用VSM模型,提高分類效率;文獻[8]將最小冗余原則引入,一定程度上避免特征獨立假設(shè)的不足,提高了分類的效果。
再者,也有些研究直接提出新的特征評價函數(shù),并在實驗中證明了其實用性。如文獻[9]提出了一種新的基于類間集中度、類內(nèi)分散度和類內(nèi)平均頻度(CDF)的特征選擇方法, 文獻[10]則提出了一種用概率分布刻畫的基于區(qū)分類別能力的特征選擇方法的表達形式。
以上研究在文本分類實驗中都被證明是有效的,它們雖然都沒有考慮到數(shù)據(jù)集傾斜的情況下的特征選擇問題,但改進思想?yún)s可以引入到不平衡數(shù)據(jù)問題上。
不平衡問題由來已久,在其他領(lǐng)域有很多應(yīng)對方法,包括過采樣、欠采樣、樣例加權(quán)、分類器閾值調(diào)整等方法。文獻[11]在二類不平衡文本上將標準的SVM與過采樣、欠采樣等方法進行了對比,具體參加對比的改進方法為隨機采樣、基于聚類的欠采樣、SMOTE過采樣、樣例權(quán)重、基于F1宏平均的閾值調(diào)整;但實驗表明這些改進方法均不如標準的SVM算法的分類結(jié)果,證明了SVM在兩類不平衡問題上的優(yōu)越性。這并不意味著這些通用技術(shù)在不平衡文本分類中完全無用,文獻[12]使用基于聚類的欠采樣方法訓(xùn)練多個SVM分類器在高維不平衡數(shù)據(jù)集上達到了比標準SVM更好的效果,一定程度上也可以借鑒到文本分類中。
文獻[11]的實驗中沒有考慮特征選擇方法的影響。但在文獻[2]中則考慮了在高維不平衡問題上將特征選擇與采樣方法、樣例加權(quán)、性能指標整合來解決問題,評估了這些技術(shù)對特征選擇的影響,其缺點在于其實驗是針對特征選擇方法的相關(guān)性而不是針對不平衡文本分類來設(shè)計的,不能證明特征選擇方法在這些技術(shù)的影響下效果變好。將解決不平衡問題的通用方法如過采樣、樣例加權(quán)等與特征選擇函數(shù)融合確實是解決不平衡文本分類問題的一個可研究方向,但鑒于這些通用技術(shù)在SVM中并沒有優(yōu)越性且與特征函數(shù)之間的相關(guān)性較為復(fù)雜,本文先從在不平衡文本分類問題中改進特征選擇入手,將特征函數(shù)與通用技術(shù)的融合作為后續(xù)研究方向。
在實際應(yīng)用中,即便是均衡文本,特征選擇方法也可能會遇到一個陷阱,即過多的提取某些類中具有強預(yù)測性的特征,而忽略分類需要的特征[13],即特征選擇方法被大類主導(dǎo)。這里需要注意的是,強預(yù)測性特征往往有助于分類,但強預(yù)測性特征只是可以將某些特定類別區(qū)分出來,為了使全局的分類性能更好,分類需要的性能還要包括一些預(yù)測性并不強但卻能提高強預(yù)測性特征覆蓋不到的類別的分類性能的特征。為了解決被大類主導(dǎo)的問題,文獻[13]提出輪轉(zhuǎn)法在各個類別間選擇特征,文獻[14]提出將正例和反例按照一定比例融合的方法來達到好的效果。輪轉(zhuǎn)法與比例融合法在平衡數(shù)據(jù)集下可以達到較好的效果,但當(dāng)數(shù)據(jù)集不平衡時卻值得懷疑,直觀上看,不平衡問題中的各個類別所需的分類特征數(shù)目是不相同的,文檔數(shù)目多的類別會擁有更多的有效分類特征,輪轉(zhuǎn)法達到的特征在類別間的完全均衡會使得多數(shù)類的性能降低,而比例融合法在多類不平衡問題下的比例的設(shè)定比較復(fù)雜,且當(dāng)訓(xùn)練集與測試集分布不一致時基于訓(xùn)練集中的類別分布設(shè)定的比例未必在測試集中有效。
文獻[15]則對不平衡問題上的特征選擇的改進進行了總結(jié),得出了通過提高稀有類別的準確率來解決不平衡問題的思路,并提出了使用倒轉(zhuǎn)類別頻率對特征選擇函數(shù)如IG等進行加權(quán),在不平衡問題上提升了F1宏平均值。本文提出的特征選擇方法客觀上也是通過提高稀有類別的準確率來解決不平衡問題,因而在實驗中采用文獻[15]中的DFICF方法作為與之前研究成果進行比較的基準線。
綜上所述,基于特征選擇方法改進不平衡文本分類問題主要有以下三個方向。
a) 與不平衡問題的通用解決方法如過采樣、樣例加權(quán)等融合;
b) 使用傳統(tǒng)的特征選擇方法在各個類別上分別選取特征,按照比例融合;
c) 在特征選擇函數(shù)中通過提高稀有類別中特征的權(quán)重來提高稀有類別的特征的比例,從而提高稀有類別的準確率。
本文提出的特征選擇方法正是基于第三個方向的思想,通過特征選擇方法使各個類別間的特征數(shù)目更加平衡,提高稀有類的性能從而提高整體性能。但前兩個方向仍然不失為改進不平衡文本分類問題的研究方向。
文獻[13]中提出了特征選擇方法容易選取某些類的強預(yù)測型特征,而忽略分類需要的特征。在不平衡數(shù)據(jù)集中,由于稀有類的文檔數(shù)目少,其特征空間更為稀疏,一方面稀有類的強預(yù)測型特征會比多數(shù)類要少,一方面稀有類的強預(yù)測型特征的預(yù)測強度一般也會比多數(shù)類要小,使得傳統(tǒng)的特征選擇方法在不平衡問題下會被多數(shù)類所主導(dǎo),造成選取的特征子集中能夠區(qū)分稀有類的特征很少,從而導(dǎo)致稀有類在分類過程中準確率低。
在上面的分析中,隱含了一個弱假設(shè),即只有當(dāng)某個類的強預(yù)測型特征被選擇,該類才可能被正確的分類。該假設(shè)在兩類分類中并不成立,因為兩類中非此即彼,極端情況下即使全都選擇了正類的強預(yù)測型特征,在負類中的樣例仍然會因為不符合正類的判別條件而被歸為負類。但在多類分類中則不如此,尤其是存在多個稀有類的情況時。這也是兩類不平衡分類與多類不平衡分類的不同之處,也可能是svm在兩類不平衡問題上表現(xiàn)優(yōu)異的原因。
通過上面的分析,可得到如下推論。
推論1 在保證多數(shù)類性能的前提下,越不被多數(shù)類主導(dǎo)的特征選擇方法,在不平衡文本問題上就越能提高稀有類的準確率,從而提高整體性能。
該推論一般情況下對于單一的特征選擇函數(shù)成立,當(dāng)使用輪轉(zhuǎn)法或按比例融合法時不能保證成立,因為本文也假設(shè)了在不平衡數(shù)據(jù)集下多數(shù)類與稀有類所需的分類特征數(shù)目存在差異,完全的均衡不能保證多數(shù)類的性能,整體性能會變差。
使用平均方差對特征選擇后的特征子集的主導(dǎo)性進行量化分析,平均方差越大,說明該特征選擇方法越被某些類別主導(dǎo),反之亦然。
下面對主導(dǎo)性平均方差的計算進行定義。
首先,對特征與類別是否存在強預(yù)測型關(guān)系進行判斷,特征的強預(yù)測型是指該特征在某個類或某些類中出現(xiàn)頻繁而在其他類中較少出現(xiàn),可以使用特征在某個類中的出現(xiàn)的文檔概率或者詞頻概率來衡量該特征在某個類中的頻繁性,本文使用文檔概率來衡量,即:
(1)
其中,Count(Ci,tj)表示特征tj在類別Ci中出現(xiàn)的文檔數(shù)目,|Ci|為類別C的文檔數(shù)目。
然后,定義特征tj與類別Ci存在強預(yù)測性關(guān)系的判定條件:
Predict(Ci,tj)=
(2)
式(2)中,k=10,這表示當(dāng)特征tj與類別Ci的文檔概率與特征tj與所有類別的文檔概率中的最大值在同一數(shù)量級時,認為特征tj與類別Ci存在強預(yù)測型關(guān)系。
由式(2)可以得到某類中擁有強預(yù)測型特征的個數(shù)公式:
(3)
式(3)中,n為特征總數(shù)。由式(3)可以繼續(xù)得到平均方差的計算公式,如下:
(4)
使用主導(dǎo)性平均方差對主導(dǎo)性進行量化分析后,根據(jù)推論1,可得推論2。
推論2 在保證多數(shù)類性能的前提下,使得主導(dǎo)性平均方差越低的特征選擇方法,在不平衡文本分類問題上越能提高稀有類的性能,從而提高總體性能。
至此,對引言中的兩個問題進行了回答。即主導(dǎo)性的定義與量化問題,不平衡問題下的較好特征選擇方法的特點問題。在第5節(jié)中,以推論2的論點為指導(dǎo),提出了一種新的特征選擇方法;第6節(jié)的實驗結(jié)果則證明了推論2的正確性以及本文特征選擇方法的有效性。
根據(jù)第4節(jié)的討論,本文構(gòu)造了一種特征選擇函數(shù),它能夠降低主導(dǎo)性平均方差,從而能較為平衡地在稀有類和多數(shù)類之間選取特征,在不降低或較少降低多數(shù)類分類性能的前提下,提高稀有類的分類性能。該方法基于區(qū)分能力(Discriminative Ability),所以稱該方法為DA特征選擇法。
DA方法基于兩點考慮來降低主導(dǎo)性平均方差。首先,使用文檔概率來表示特征與類別的相關(guān)程度,使得特征選擇避免受到先驗分布的影響,特征在稀有類和多數(shù)類的相關(guān)程度得到相對公平的度量,不會偏向于選擇文檔數(shù)目多的類別的特征。其次,使用最小距離來衡量特征對于某類的區(qū)分能力的貢獻,使得對區(qū)分類別有貢獻的特征更容易被選中,弱化了大類強預(yù)測型特征的影響。
基于上述考慮,DA方法使用式(1)中所示的文檔概率來表示特征與文本類別的相關(guān)度,在文獻[9]中,文檔概率被稱為類內(nèi)分散度。然后利用特征在類別之間的相關(guān)程度的差異,計算出特征在各個類別間的區(qū)分能力。直觀上來看,一個特征詞在某個類別上出現(xiàn)的越多,在其他類別中出現(xiàn)的越少,該特征就越能把某類從其他類別中區(qū)分出來。
某特征詞在某個類別上的區(qū)分能力是指該特征在該類上的相關(guān)度與該特征在其他類上的相關(guān)度的差的最小值,該值越大,該特征區(qū)分該類與其他類的能力越大。計算公式如式(5)所示。
(5)
其中,DAjk表示特征tk在類別Cj上的區(qū)分能力,min(|P(Cj,tk)-P(Ci,tk)|),i≠j表示DAjk是文檔概率P(Cj,tk)與最接近P(Cj,tk)的相關(guān)度的差的絕對值,即相關(guān)度的最小絕對值差。
特征tk針對所有類別的區(qū)別能力的計算方法有兩種,一種是對該特征在各個類別上的區(qū)分能力求和,衡量特征針對數(shù)據(jù)集的平均區(qū)分能力,如式(6)所示;另一種是取該特征在各個類別上的區(qū)分能力的最大值,衡量特征針對數(shù)據(jù)集的最大區(qū)分能力,如式(7)所示。
(6)
(7)
由DA方法的定義可知,DA方法的基本思想是選擇對分類貢獻最大的特征。其與文獻[10]不同之處在于,DA方法使用特征在類別之間的差異而不是特征出現(xiàn)與否造成的類別分布的變化來衡量區(qū)分能力的。DA方法使用統(tǒng)一評分標準對每個特征進行評分,按照評分高低進行特征選擇,并不是如DFICF提高稀有類特征評分權(quán)重那樣顯著傾向于選擇稀有類特征。多數(shù)類與少數(shù)類的候選特征空間大小存在固有差別,因而經(jīng)DA方法得到的特征子集中的多數(shù)類特征仍然多于少數(shù)類特征,從而保證了多數(shù)類的性能。
6.1 實驗數(shù)據(jù)集
本實驗使用復(fù)旦大學(xué)的中文文本分類語料庫tc-corpus,復(fù)旦大學(xué)語料庫語料有20個類別,其中訓(xùn)練集和測試集中的每個類別的文檔數(shù)目比例都為1∶1。訓(xùn)練集共9 804篇,測試集共9 833篇。訓(xùn)練集與測試集的類別分布如表 1所示。
本文以100篇文檔以下的類別為稀有類,400篇文檔以上的類別為多數(shù)類。則由表1可知,數(shù)據(jù)集中共有11個稀有類,九個多數(shù)類。
表1 訓(xùn)練集與測試集的文檔數(shù)目分布
6.2 實驗設(shè)計及評測指標
本文的實驗?zāi)繕擞袃蓚€,其一是通過對比各種特征選擇方法在不平衡文本分類問題上的分類性能,驗證本文提出的DA特征選擇方法的優(yōu)越性。其二是通過使用主導(dǎo)性平均方差對各種特征選擇方法得到的特征子集進行分析,驗證本文第4節(jié)推論2的正確性,同時也得到了在不平衡數(shù)據(jù)集上表現(xiàn)優(yōu)越的特征選擇方法的特點。
對于目標一,本文實驗將DA特征選擇方法與傳統(tǒng)特征選擇方法CHI、IG進行對比,CHI即取CHI評分在所有類別上的最大值,另外使用之前針對不平衡數(shù)據(jù)集設(shè)計的特征選擇算法DFICF[15]作為與之前研究成果對比的基線。DFICF特征選擇方法的計算公式為:
(8)
其中,IG(t)是特征t使用信息增益方法得到的評分值,M為類別數(shù)目,mt為特征t出現(xiàn)的類別數(shù)目。
實驗過程中,采用中國科學(xué)院ICTCLAS[16]分詞系統(tǒng)進行中文分詞,向量化時采用TF-IDF方法對向量進行加權(quán),分類器則使用目前性能較好且應(yīng)用廣泛的支持向量機(SVM)和樸素貝葉斯兩種分類算法;其中,SVM分類器基于liblinear[17]程序包,該程序包是SVM使用線性核時的優(yōu)化版本,樸素貝葉斯算法則使用效果較好的多項式事件模型[18]。
為了使實驗結(jié)果具有可信性。實驗首先在兩類不平衡問題上進行,包括兩類較不平衡問題與兩類極不平衡問題。然后在多類不平衡問題上進行特征選擇方法的對比,在多類不平衡問題上的實驗使用全部數(shù)據(jù)集。
對于分類預(yù)測結(jié)果,本文使用F1值的宏平均和微平均作為效果的評價指標。F1值是準確率與召回率的調(diào)和平均值,是一種綜合的測量指標。微平均是指對于每一個實例的性能指標的平均值,它將整個文檔集合看作一個整體。對于同一個數(shù)據(jù)集來說,它的準確率、召回率和F1值的微平均值是相等的。宏平均是指對于每一個類別的性能指標的平均值,它是將類別等同看待,這樣就避免了結(jié)果評測被大類支配的問題。
對于目標二,本文在各特征選擇方法在多類不平衡問題對比實驗的基礎(chǔ)上,對各個特征選擇方法產(chǎn)生的特征子集的主導(dǎo)性平均方差與分類性能的相關(guān)性進行分析。
6.3 特征選擇對比的實驗結(jié)果
6.3.1 較不平衡兩類分類對比實驗
在較不平衡兩類分類實驗中,使用數(shù)據(jù)集中的C34經(jīng)濟類與C37軍事類兩類進行實驗,其中,訓(xùn)練集中C37有74篇文檔,C34中有1 600篇文檔,從C34中隨機選取約1 500篇文檔,使得不平衡比為20∶1,測試集與訓(xùn)練集保持相同分布且文檔數(shù)目比例為1∶1。
由圖1與圖2可以看出,在兩類較不平衡問題中,F(xiàn)1宏平均與微平均的趨勢較為一致。當(dāng)特征數(shù)小于3 000時,DA方法處于劣勢,但當(dāng)特征數(shù)大于3 000時,不論是F1宏平均還是F1微平均,本文提出的方法優(yōu)于其他方法。就峰值而論,也是DA方法高于其他方法。
圖1 兩類較不平衡分類問題中F1宏平均隨特征數(shù)目變化趨勢圖
圖2 兩類較不平衡問題分類中F1微平均隨特征數(shù)目變化趨勢圖
需要注意的是,在兩類問題下,式(6)與式(7)就退化成了同一種方法。
為了節(jié)省篇幅,在兩類不平衡問題下不展示樸素貝葉斯算法的結(jié)果。由下文的多類不平衡問題下的實驗結(jié)果可知,無論樸素貝葉斯算法與支持向量機算法,得到的結(jié)果是相似的。
6.3.2 極不平衡兩類分類對比實驗
在該實驗中,少數(shù)類仍然使用C37軍事類。多數(shù)類使用C19計算機類、C34經(jīng)濟類、C31環(huán)境類、C39運動類、C32農(nóng)業(yè)類、C38政治類的組合。多數(shù)類從這六類的集合中隨機選取約7 400篇文檔,不平衡比例為100∶1,測試集與訓(xùn)練集分布一致且文檔比例為1∶1。
由圖3和圖4可以看出,在兩類極不平衡問題中,本文提出的特征選擇方法在F1宏平均上的優(yōu)勢進一步擴大,在F1微平均上的優(yōu)勢有減小的趨勢。表明了本文的特征選擇方法是在保證大類分類性能的情況下提高少數(shù)類的分類性能來提高總體性能的。
圖3 兩類極不平衡問題中F1宏平均隨特征數(shù)目的變化趨勢
6.3.3 多類不平衡分類對比實驗
多類不平衡分類實驗中,使用復(fù)旦大學(xué)語料的全部類別進行實驗,語料信息如6.1中所述。
在圖5與圖6中,DA-sum對應(yīng)式(6)的計算策略,DA-max對應(yīng)式(7)的計算策略。
圖5 多類不平衡問題中F1宏平均隨特征數(shù)目的變化趨勢(SVM)
圖6 多類不平衡問題中F1微平均隨特征數(shù)目的變化趨勢(SVM)
由圖5與圖6可知,在svm分類器下,五種特征選擇方法的微平均值相差不大,但DA-sum與DA-max仍然保持了微弱的優(yōu)勢。相比而言,在宏平均值的比較中,DA-max與DA-sum保持了較大的優(yōu)勢,DA-sum方法在500-5 000的任一特征數(shù)目下都優(yōu)于其余四種方法,DA-sum在特征數(shù)為4 000-5 000時與IG方法重合,但卻在特征數(shù)為2 000時達到了本次實驗宏平均值的峰值。
圖7和圖8則分別展示了使用樸素貝葉斯分類器時IG、CHI、DA-sum、DA-max、DFICF五種特征選擇方法隨特征數(shù)目的不同F(xiàn)1微平均與宏平均指標的變化。
圖7 多類不平衡分類問題中F1宏平均隨特征數(shù)目的變化趨勢(NB)
圖8 多類不平衡分類問題中F1微平均隨特征數(shù)目的變化趨勢(NB)
由圖7和圖8可知,使用樸素貝葉斯分類器時,在宏平均上仍然是DA-max與DA-sum保持優(yōu)勢,但顯然,DA-max優(yōu)勢較為明顯,DA-sum優(yōu)勢較小。在微平均中,DA-sum則處于弱勢,與IG、DFICF相近;但DA-max仍然保持優(yōu)勢,與CHI相近。這表明,同樣的特征選擇方法,使用不同的分類器也能得到不同的結(jié)果,說明特征選擇方法與分類器之間存在著一定的相關(guān)關(guān)系。
6.3.4 實驗結(jié)果分析總結(jié)
通過在二類較不平衡問題、二類極不平衡問題、多類不平衡問題上的實驗,可以得出如下結(jié)論。
1. 在二類分類問題中,當(dāng)特征數(shù)目較大時,DA方法擁有較大的優(yōu)勢;在多類分類中則不論特征數(shù)目均有明顯優(yōu)勢。
2. 在樸素貝葉斯下的多類分類實驗中,DA-max優(yōu)勢依舊,但DA-sum在宏平均中優(yōu)勢較小,在微平均中遜于IG與DFICF。表明特征選擇方法與分類算法之間具有一定的相關(guān)性。
3. 在二類較不平衡問題中,CHI與DFICF的峰值高于IG,但在其他兩個實驗中,均有IG>IGICF>CHI。表明IG方法在不平衡問題上相比其他特征選擇函數(shù)仍有優(yōu)勢;
4. 在二類較不平衡問題的實驗中,DFICF相對IG略有優(yōu)勢,在其他實驗中,則表現(xiàn)與CHI相仿,表明單純地提高出現(xiàn)文檔數(shù)目少的特征的權(quán)重在多類不平衡問題下不能達到較好的改進效果。
綜上所述,可以得到五種特征選擇函數(shù)在不平衡問題上的最終排名,即:
DA-max > DA-sum > IG > DFICF > CHI
6.4 特征選擇的主導(dǎo)性平均方差對比
本節(jié)針對多類不平衡問題分類實驗中的特征選擇方法,按照第4節(jié)的主導(dǎo)性平均方差分析方法進行了統(tǒng)計分析。特征數(shù)為3 000與5 000時的各特征選擇方法的分類性能與方差對比數(shù)據(jù)如表2與表3所示。其中,各項指標的最優(yōu)值與次優(yōu)值用不同顏色標出。
由表2與表3可以看到,宏平均值與平均方差的相關(guān)性比較強烈,主導(dǎo)性平均方差越低,宏平均值呈現(xiàn)越高的趨勢。對于特征數(shù)為3 000時的SVM宏平均與特征數(shù)為5 000時的NB宏平均,這一趨勢擬合的較好。對于特征數(shù)為3 000時的NB宏平均與特征數(shù)為5 000時的SVM宏平均,雖然存在著異常,但總的趨勢仍然一致。
由表2和表3還可得到,DA方法擁有較低的主導(dǎo)性平均方差與較高的宏平均值與微平均值,表明基于減小主導(dǎo)性平均方差來改進特征選擇方法的思路是可行的。
表2 特征數(shù)為3 000時各特征方法分類性能與主導(dǎo)性平均方差數(shù)據(jù)對照表
DA-sumDA-maxIGCHIIGICFSVM微平均/%90.4790.5389.9789.6389.85SVM宏平均/%71.9671.7466.6964.3364.43NB微平均/%79.3181.9278.8481.4279.82NB宏平均/%61.7966.6359.0960.2059.14平均方差4.0604.3414.9315.5416.030
表3 特征數(shù)為5 000時各特征方法分類性能與主導(dǎo)性平均方差數(shù)據(jù)對照表
DA-maxDA-sumIGCHIIGICFSVM微平均/%90.3590.9790.8689.9390.28SVM宏平均/%68.9171.6768.6266.3867.63NB微平均/%82.2880.7680.9482.5481.20NB宏平均/%67.0763.9662.6663.0662.38平均方差4.6174.8735.7946.1706.666
在特征選擇后的子集上進行的主導(dǎo)性分析的結(jié)果證明了本文推論2的正確性,即在不平衡問題上越不被大類主導(dǎo)的特征選擇方法越能達到好的效果,表明主導(dǎo)性平均方差可以作為不平衡問題上指導(dǎo)特征選擇方法選取特征的一種原則。同時,也證明了本文提出的DA特征選擇方法在不平衡問題上是通過較為平衡的在稀有類和多數(shù)類之間選擇特征,以提高稀有類的性能且保證多數(shù)類的性能來提高整體性能。
文本分類中的不平衡問題是一個在實際應(yīng)用中很常見的問題,本文借鑒了前人在改進特征選擇方法時的保證大類性能提高稀有類性能的思想,總結(jié)出了不被大類主導(dǎo)的特征選擇方法在不平衡問題上有更好效果的推論,并提出了主導(dǎo)性平均方差作為主導(dǎo)性的量化分析方法。在推論與量化方法的指導(dǎo)下,本文提出了DA特征選擇方法。該方法在與傳統(tǒng)特征選擇方法IG、CHI與針對不平衡改進的DFICF特征選擇方法進行的對比實驗中,在宏平均上表現(xiàn)出了較大的優(yōu)勢,同時保證了微平均值,一定程度上可以解決不平衡分類問題。在五種特征選擇方法的主導(dǎo)性分析實驗中,也進一步證明了本文推論的正確性。這也對不平衡問題上的特征選擇方法的衡量提供了一種標準。
但是,本文提出的主導(dǎo)性分析方法在不同分類算法上的對應(yīng)趨勢存在一定的異常情況,表明本文的只有某類的強預(yù)測型特征被選中該類才可能被正確分類的弱假設(shè)可能存在著一定的缺陷,如何對主導(dǎo)性進行更加準確的分析是一個可研究方向。另外,特征選擇函數(shù)與分類算法的交互也是影響主導(dǎo)性分析的一個重要的因子。
本文提出的主導(dǎo)性分析方法的一個限制在于不能使用輪轉(zhuǎn)法等策略進行特征在類別間的絕對或相對平衡,該限制基于本文提出的不平衡問題中各類別所需的用于分類的特征數(shù)目存在差異的假設(shè),如何對基于該假設(shè)改進特征選擇函數(shù)與主導(dǎo)性分析方法是本文的后續(xù)研究方向。
[1] 蘇金樹, 張博鋒, 徐昕. 基于機器學(xué)習(xí)的文本分類技術(shù)研究進展[J]. 軟件學(xué)報, 2006, 17(9): 1848-1859.
[2] Van Hulse J, Khoshgoftaar T M, Napolitano A, et al. Feature selection with high-dimensional imbalanced data[C]//Proceedings of IEEE International Conference. 2009: 507-514.
[3] 劉海峰, 王元元, 張學(xué)仁, 等. 文本分類中基于位置和類別信息的一種特征降維方法[J]. 計算機應(yīng)用研究, 2008, 25(8): 2292-2294.
[4] Yang Y, Pedersen J O. A comparative study on feature selection in text categorization[C]//Proceedings of the ICML. 1997, 97: 412-420.
[5] Rogati M, Yang Y. High-performing feature selection for text classification[C]//Proceedings of the eleventh international conference on Information and knowledge management. ACM, 2002: 659-661.
[6] 代六玲, 黃河燕, 陳肇雄. 中文文本分類中特征抽取方法的比較研究[J]. 中文信息學(xué)報, 2004, 18(1): 26-32.
[7] 廖莎莎, 江銘虎. 中文文本分類中基于概念屏蔽層的特征提取方法[J]. 中文信息學(xué)報, 2006, 20(3): 22-28.
[8] 張希娟, 王會珍, 朱靖波. 面向文本分類的基于最小冗余原則的特征選取[J]. 中文信息學(xué)報, 2007, 21(5): 56-60.
[9] 熊忠陽, 蔣健, 張玉芳. 新的CDF文本分類特征提取方法[J]. 計算機應(yīng)用, 2009, 9(7): 1755-1757.
[10] 徐燕, 李錦濤, 王斌, 等. 基于區(qū)分類別能力的高性能特征選擇方法[J]. 軟件學(xué)報, 2008, 19(1): 82-89.
[11] Sun A, Lim E P, Liu Y. On strategies for imbalanced text classification using SVM: A comparative study[J]. Decision Support Systems, 2009, 48(1): 191-201.
[12] Yin L, Ge Y, Xiao K, et al. Feature selection for high-dimensional imbalanced data[J]. Neurocomputing, 2013,105:3-11.
[13] Forman G. A pitfall and solution in multi-class feature selection for text classification[C]//Proceedings of the twenty-first international conference on Machine learning. ACM, 2004: 38.
[14] Zheng Z, Wu X, Srihari R. Feature selection for text categorization on imbalanced data[J]. ACM SIGKDD Explorations Newsletter, 2004, 6(1): 80-89.
[15] 徐燕, 李錦濤, 王斌, 等. 不均衡數(shù)據(jù)集上文本分類的特征選擇研究[J]. 計算機研究與發(fā)展,2007,44(22):58-62.
[16] Zhang H P, Yu H K, Xiong D Y, et al. HHMM-based Chinese lexical analyzer ICTCLAS[C]//Proceedings of the second SIGHAN workshop on Chinese language processing-Volume 17. Association for Computational Linguistics, 2003: 184-187.
[17] Fan R E, Chang K W, Hsieh C J, et al. LIBLINEAR: A library for large linear classification[J]. The Journal of Machine Learning Research, 2008, 9: 1871-1874.
[18] McCallum A, Nigam K. A comparison of event models for naive bayes text classification[C]//Proceedings of the AAAI-98 workshop on learning for text categorization. 1998, 752: 41-48.
A Feature Selection Method Based on Discriminative Ability for Multiclass Text Categorization on Imbalanced Data
ZHANG Yanxiang, PAN Haixia
(School of Software,BeiHang University, Beijing 100191, China)
Imbalanced data in text categorization is pervasive in reality. Conventional feature selection(FS) methods prefer to choose features in large classes rather than rare classes. This paper proposes a quantitative method to measure the dominance. Then, this paper dscribes a new FS method, namely DA method, based on category discriminative ability takes the minimum absolute difference of documental probability between classes as a criterion to partly ensure the fairness of FS method on large classes and rare classes. Experimental results show the DA method outperforms CHI, IG and DFICF especially on macro-average F1 measure.
text categorization; imbalanced problem; feature selection; dominance analysis; discriminative ability
張延祥(1989—),碩士研究生,主要研究領(lǐng)域為機器學(xué)習(xí)、文本挖掘。E-mail:zhangyx@buaa.edu.cn潘海俠(1972—),博士研究生,副教授,碩士生導(dǎo)師,主要研究領(lǐng)域為云服務(wù)、服務(wù)科學(xué)與管理、軟件工程、人工智能等。E-mail:haixiapan@buaa.edu.cn
1003-0077(2015)04-0111-09
2013-09-05 定稿日期: 2014-01-10
TP391
A