張延祥，潘海俠

(北京航空航天大學(xué) 軟件學(xué)院，北京 100191)

?

一種基于區(qū)分能力的多類不平衡文本分類特征選擇方法

張延祥，潘海俠

(北京航空航天大學(xué) 軟件學(xué)院，北京 100191)

文本分類中的不平衡數(shù)據(jù)問題在現(xiàn)實(shí)應(yīng)用中比較普遍。傳統(tǒng)的特征選擇方法在不平衡問題上傾向于多數(shù)類而忽略稀有類。針對這種傾向性該文提出了一種主導(dǎo)性分析量化方法，并基于對該方法的優(yōu)化提出了一種基于類別區(qū)分能力的特征選擇方法，即DA(Discriminative Ability)方法，該方法使用文檔概率的最小絕對值差作為評分標(biāo)準(zhǔn)，一定程度上保證了特征選擇在稀有類與多數(shù)類上的公平性。實(shí)驗(yàn)表明，DA優(yōu)于CHI、IG、DFICF，尤其在F1宏平均指標(biāo)上，DA在不平衡問題上能夠取得更好的降維效果。

文本分類；不平衡問題；特征選擇；主導(dǎo)性分析；區(qū)分能力

1 引言

互聯(lián)網(wǎng)的快速發(fā)展使得信息呈現(xiàn)爆發(fā)式增長的態(tài)勢，如何有效管理這些數(shù)據(jù)成為當(dāng)前的熱點(diǎn)問題。文本分類作為海量數(shù)據(jù)管理的關(guān)鍵技術(shù)，在信息檢索、數(shù)據(jù)挖掘、輿情監(jiān)測等方面均有著廣泛應(yīng)用。

近年來，基于機(jī)器學(xué)習(xí)的分類方法被應(yīng)用到文本分類中，取得了很好的效果。但在實(shí)際應(yīng)用中，數(shù)據(jù)集分布偏斜仍是一個(gè)亟待解決的問題[1]，尤其在具有高維特點(diǎn)的文本分類問題上。

數(shù)據(jù)集分布不平衡問題一般是指樣本在類別間可能存在數(shù)量級的差別，在這種情況下，樣本無法準(zhǔn)確地反映整個(gè)空間的類別分布，特征降維方法與分類算法都傾向于被大類主導(dǎo)而忽略小類，是導(dǎo)致分類效果不理想的重要因素。有很多種策略可以對不平衡問題進(jìn)行改進(jìn)，如重采樣技術(shù)、新的分類策略、更好的效果評估方法等[1]。本文從特征選擇的角度出發(fā)，針對不平衡問題下的特征選擇方法存在的缺陷進(jìn)行改進(jìn)。

特征選擇是文本分類的重要步驟，直接影響到模型的構(gòu)建與分類的性能，因而通過改進(jìn)特征選擇方法來解決不平衡問題是可行的。特征選擇方法應(yīng)用于分類問題上有很多優(yōu)勢，比如分類模型的快速構(gòu)建、減小過擬合的概率、降低內(nèi)存與硬盤的占用、提高處理速度等；劣勢在于可能會過濾掉一些重要的特征，降低分類效果[2]。

本文對不平衡數(shù)據(jù)集下特征選擇方法的特點(diǎn)進(jìn)行了研究，分析了如下兩個(gè)問題。

a) 不平衡數(shù)據(jù)集下特征選擇方法傾向于被大類主導(dǎo)而忽略小類，如何定義與量化“主導(dǎo)”？

b) 如果存在著一種可以較好地解決不平衡問題的特征選擇方法，那么該方法會有什么樣的特點(diǎn)？

針對以上問題進(jìn)行研究后，本文提出了一種基于區(qū)分能力的特征選擇方法，一定程度上符合本文對問題b的解答，實(shí)驗(yàn)表明，該方法在不平衡問題上達(dá)到了比傳統(tǒng)特征選擇方法更好的分類效果。

本文的其余內(nèi)容安排如下，第2節(jié)對特征降維尤其是特征選擇方法的研究成果進(jìn)行了介紹；第3節(jié)對不平衡問題的研究現(xiàn)狀進(jìn)行了總結(jié)；第4節(jié)對不平衡數(shù)據(jù)集下的特征選擇的特點(diǎn)進(jìn)行了探討，對主導(dǎo)性進(jìn)行了定義與量化分析；第5節(jié)提出了基于區(qū)分能力的特征選擇方法；第6節(jié)對第4、5節(jié)提出的假設(shè)與方法進(jìn)行實(shí)驗(yàn)驗(yàn)證；第7節(jié)為結(jié)論與展望。

2 特征降維

2.1 特征降維方法分類

根據(jù)選擇特征集合方式的不同，特征降維方法可以分為兩類，特征選擇和特征抽取。特征選擇一般是依據(jù)某個(gè)準(zhǔn)則，從原始特征集合中選取最能反映類別統(tǒng)計(jì)特性的特征，即從集合中選擇一個(gè)子集；特征抽取則是基于特征之間的語義相關(guān)性、類別特征集對類內(nèi)文本聚合程度、類間離散程度的影響力等方面考量而對文本特征集的一種壓縮[3]。

常見的特征選擇方法包括文檔頻度(DF)、互信息(MI)、信息增益(IG)、統(tǒng)計(jì)量(CHI)、期望交叉熵、文本證據(jù)權(quán)、幾率比等。而常見的特征抽取方法則包括主成分分析、隱含語義索引、非負(fù)矩陣分解等。

本文所提出的方法是一種特征選擇方法。

2.2 特征選擇方法

本節(jié)介紹針對主要特征選擇方法的研究成果，各個(gè)主要特征選擇方法的計(jì)算公式參考文獻(xiàn)[4]，本節(jié)不再贅述。

自從機(jī)器學(xué)習(xí)技術(shù)被成功應(yīng)用于文本分類以來，針對特征選擇方法的研究與改進(jìn)越來越多且日趨成熟。對特征選擇方法的研究主要集中在以下三個(gè)方面。

第一，針對各種現(xiàn)有的成熟方法進(jìn)行性能對比，文獻(xiàn)[4]總結(jié)了IG、MI、CHI、DF、TS五種特征選擇方法的分類性能，發(fā)現(xiàn)IG和CHI是較優(yōu)的特征選擇方法，在容許少量性能損失的情況下，DF則有較好的擴(kuò)展性與計(jì)算性能。文獻(xiàn)[5]則對100余種特征選擇算法的變體進(jìn)行了比較，得到了CHI效果最好但在低頻詞上不可信等結(jié)論。文獻(xiàn)[6]將主要的特征選擇方法在中文語料上重新實(shí)驗(yàn)，得到了與文獻(xiàn)[5]相似的結(jié)論，即將CHI與IG等與DF組合形成更好地特征選擇方法。

其次，不同于組合傳統(tǒng)方法，有些研究將其他原則引入到傳統(tǒng)方法中作為改進(jìn)，也達(dá)到了較好的效果。文獻(xiàn)[7]將概念特征引入，提出了基于概念屏蔽層的特征選擇方法，通過概念統(tǒng)計(jì)和語義層次分析的方法，能夠更好地利用VSM模型，提高分類效率；文獻(xiàn)[8]將最小冗余原則引入，一定程度上避免特征獨(dú)立假設(shè)的不足，提高了分類的效果。

再者，也有些研究直接提出新的特征評價(jià)函數(shù)，并在實(shí)驗(yàn)中證明了其實(shí)用性。如文獻(xiàn)[9]提出了一種新的基于類間集中度、類內(nèi)分散度和類內(nèi)平均頻度(CDF)的特征選擇方法， 文獻(xiàn)[10]則提出了一種用概率分布刻畫的基于區(qū)分類別能力的特征選擇方法的表達(dá)形式。

以上研究在文本分類實(shí)驗(yàn)中都被證明是有效的，它們雖然都沒有考慮到數(shù)據(jù)集傾斜的情況下的特征選擇問題，但改進(jìn)思想?yún)s可以引入到不平衡數(shù)據(jù)問題上。

3 不平衡問題的研究現(xiàn)狀

不平衡問題由來已久，在其他領(lǐng)域有很多應(yīng)對方法，包括過采樣、欠采樣、樣例加權(quán)、分類器閾值調(diào)整等方法。文獻(xiàn)[11]在二類不平衡文本上將標(biāo)準(zhǔn)的SVM與過采樣、欠采樣等方法進(jìn)行了對比，具體參加對比的改進(jìn)方法為隨機(jī)采樣、基于聚類的欠采樣、SMOTE過采樣、樣例權(quán)重、基于F1宏平均的閾值調(diào)整；但實(shí)驗(yàn)表明這些改進(jìn)方法均不如標(biāo)準(zhǔn)的SVM算法的分類結(jié)果，證明了SVM在兩類不平衡問題上的優(yōu)越性。這并不意味著這些通用技術(shù)在不平衡文本分類中完全無用，文獻(xiàn)[12]使用基于聚類的欠采樣方法訓(xùn)練多個(gè)SVM分類器在高維不平衡數(shù)據(jù)集上達(dá)到了比標(biāo)準(zhǔn)SVM更好的效果，一定程度上也可以借鑒到文本分類中。

文獻(xiàn)[11]的實(shí)驗(yàn)中沒有考慮特征選擇方法的影響。但在文獻(xiàn)[2]中則考慮了在高維不平衡問題上將特征選擇與采樣方法、樣例加權(quán)、性能指標(biāo)整合來解決問題，評估了這些技術(shù)對特征選擇的影響，其缺點(diǎn)在于其實(shí)驗(yàn)是針對特征選擇方法的相關(guān)性而不是針對不平衡文本分類來設(shè)計(jì)的，不能證明特征選擇方法在這些技術(shù)的影響下效果變好。將解決不平衡問題的通用方法如過采樣、樣例加權(quán)等與特征選擇函數(shù)融合確實(shí)是解決不平衡文本分類問題的一個(gè)可研究方向，但鑒于這些通用技術(shù)在SVM中并沒有優(yōu)越性且與特征函數(shù)之間的相關(guān)性較為復(fù)雜，本文先從在不平衡文本分類問題中改進(jìn)特征選擇入手，將特征函數(shù)與通用技術(shù)的融合作為后續(xù)研究方向。

在實(shí)際應(yīng)用中，即便是均衡文本，特征選擇方法也可能會遇到一個(gè)陷阱，即過多的提取某些類中具有強(qiáng)預(yù)測性的特征，而忽略分類需要的特征[13]，即特征選擇方法被大類主導(dǎo)。這里需要注意的是，強(qiáng)預(yù)測性特征往往有助于分類，但強(qiáng)預(yù)測性特征只是可以將某些特定類別區(qū)分出來，為了使全局的分類性能更好，分類需要的性能還要包括一些預(yù)測性并不強(qiáng)但卻能提高強(qiáng)預(yù)測性特征覆蓋不到的類別的分類性能的特征。為了解決被大類主導(dǎo)的問題，文獻(xiàn)[13]提出輪轉(zhuǎn)法在各個(gè)類別間選擇特征，文獻(xiàn)[14]提出將正例和反例按照一定比例融合的方法來達(dá)到好的效果。輪轉(zhuǎn)法與比例融合法在平衡數(shù)據(jù)集下可以達(dá)到較好的效果，但當(dāng)數(shù)據(jù)集不平衡時(shí)卻值得懷疑，直觀上看，不平衡問題中的各個(gè)類別所需的分類特征數(shù)目是不相同的，文檔數(shù)目多的類別會擁有更多的有效分類特征，輪轉(zhuǎn)法達(dá)到的特征在類別間的完全均衡會使得多數(shù)類的性能降低，而比例融合法在多類不平衡問題下的比例的設(shè)定比較復(fù)雜，且當(dāng)訓(xùn)練集與測試集分布不一致時(shí)基于訓(xùn)練集中的類別分布設(shè)定的比例未必在測試集中有效。

文獻(xiàn)[15]則對不平衡問題上的特征選擇的改進(jìn)進(jìn)行了總結(jié)，得出了通過提高稀有類別的準(zhǔn)確率來解決不平衡問題的思路，并提出了使用倒轉(zhuǎn)類別頻率對特征選擇函數(shù)如IG等進(jìn)行加權(quán)，在不平衡問題上提升了F1宏平均值。本文提出的特征選擇方法客觀上也是通過提高稀有類別的準(zhǔn)確率來解決不平衡問題，因而在實(shí)驗(yàn)中采用文獻(xiàn)[15]中的DFICF方法作為與之前研究成果進(jìn)行比較的基準(zhǔn)線。

綜上所述，基于特征選擇方法改進(jìn)不平衡文本分類問題主要有以下三個(gè)方向。

a) 與不平衡問題的通用解決方法如過采樣、樣例加權(quán)等融合；

b) 使用傳統(tǒng)的特征選擇方法在各個(gè)類別上分別選取特征，按照比例融合；

c) 在特征選擇函數(shù)中通過提高稀有類別中特征的權(quán)重來提高稀有類別的特征的比例，從而提高稀有類別的準(zhǔn)確率。

本文提出的特征選擇方法正是基于第三個(gè)方向的思想，通過特征選擇方法使各個(gè)類別間的特征數(shù)目更加平衡，提高稀有類的性能從而提高整體性能。但前兩個(gè)方向仍然不失為改進(jìn)不平衡文本分類問題的研究方向。

4 不平衡數(shù)據(jù)集下的特征選擇的特點(diǎn)分析

文獻(xiàn)[13]中提出了特征選擇方法容易選取某些類的強(qiáng)預(yù)測型特征，而忽略分類需要的特征。在不平衡數(shù)據(jù)集中，由于稀有類的文檔數(shù)目少，其特征空間更為稀疏，一方面稀有類的強(qiáng)預(yù)測型特征會比多數(shù)類要少，一方面稀有類的強(qiáng)預(yù)測型特征的預(yù)測強(qiáng)度一般也會比多數(shù)類要小，使得傳統(tǒng)的特征選擇方法在不平衡問題下會被多數(shù)類所主導(dǎo)，造成選取的特征子集中能夠區(qū)分稀有類的特征很少，從而導(dǎo)致稀有類在分類過程中準(zhǔn)確率低。

在上面的分析中，隱含了一個(gè)弱假設(shè)，即只有當(dāng)某個(gè)類的強(qiáng)預(yù)測型特征被選擇，該類才可能被正確的分類。該假設(shè)在兩類分類中并不成立，因?yàn)閮深愔蟹谴思幢?，極端情況下即使全都選擇了正類的強(qiáng)預(yù)測型特征，在負(fù)類中的樣例仍然會因?yàn)椴环险惖呐袆e條件而被歸為負(fù)類。但在多類分類中則不如此，尤其是存在多個(gè)稀有類的情況時(shí)。這也是兩類不平衡分類與多類不平衡分類的不同之處，也可能是svm在兩類不平衡問題上表現(xiàn)優(yōu)異的原因。

通過上面的分析，可得到如下推論。

推論1 在保證多數(shù)類性能的前提下，越不被多數(shù)類主導(dǎo)的特征選擇方法，在不平衡文本問題上就越能提高稀有類的準(zhǔn)確率，從而提高整體性能。

該推論一般情況下對于單一的特征選擇函數(shù)成立，當(dāng)使用輪轉(zhuǎn)法或按比例融合法時(shí)不能保證成立，因?yàn)楸疚囊布僭O(shè)了在不平衡數(shù)據(jù)集下多數(shù)類與稀有類所需的分類特征數(shù)目存在差異，完全的均衡不能保證多數(shù)類的性能，整體性能會變差。

使用平均方差對特征選擇后的特征子集的主導(dǎo)性進(jìn)行量化分析，平均方差越大，說明該特征選擇方法越被某些類別主導(dǎo)，反之亦然。

下面對主導(dǎo)性平均方差的計(jì)算進(jìn)行定義。

首先，對特征與類別是否存在強(qiáng)預(yù)測型關(guān)系進(jìn)行判斷，特征的強(qiáng)預(yù)測型是指該特征在某個(gè)類或某些類中出現(xiàn)頻繁而在其他類中較少出現(xiàn)，可以使用特征在某個(gè)類中的出現(xiàn)的文檔概率或者詞頻概率來衡量該特征在某個(gè)類中的頻繁性，本文使用文檔概率來衡量，即：

(1)

其中，Count(Ci,tj)表示特征tj在類別Ci中出現(xiàn)的文檔數(shù)目，|Ci|為類別C的文檔數(shù)目。

然后，定義特征tj與類別Ci存在強(qiáng)預(yù)測性關(guān)系的判定條件：

Predict(Ci,tj)=

(2)

式(2)中，k=10，這表示當(dāng)特征tj與類別Ci的文檔概率與特征tj與所有類別的文檔概率中的最大值在同一數(shù)量級時(shí)，認(rèn)為特征tj與類別Ci存在強(qiáng)預(yù)測型關(guān)系。

由式(2)可以得到某類中擁有強(qiáng)預(yù)測型特征的個(gè)數(shù)公式：

(3)

式(3)中，n為特征總數(shù)。由式(3)可以繼續(xù)得到平均方差的計(jì)算公式，如下：

(4)

使用主導(dǎo)性平均方差對主導(dǎo)性進(jìn)行量化分析后，根據(jù)推論1，可得推論2。

推論2 在保證多數(shù)類性能的前提下，使得主導(dǎo)性平均方差越低的特征選擇方法，在不平衡文本分類問題上越能提高稀有類的性能，從而提高總體性能。

至此，對引言中的兩個(gè)問題進(jìn)行了回答。即主導(dǎo)性的定義與量化問題，不平衡問題下的較好特征選擇方法的特點(diǎn)問題。在第5節(jié)中，以推論2的論點(diǎn)為指導(dǎo)，提出了一種新的特征選擇方法；第6節(jié)的實(shí)驗(yàn)結(jié)果則證明了推論2的正確性以及本文特征選擇方法的有效性。

5 基于區(qū)分能力的特征選擇方法

根據(jù)第4節(jié)的討論，本文構(gòu)造了一種特征選擇函數(shù)，它能夠降低主導(dǎo)性平均方差，從而能較為平衡地在稀有類和多數(shù)類之間選取特征，在不降低或較少降低多數(shù)類分類性能的前提下，提高稀有類的分類性能。該方法基于區(qū)分能力(Discriminative Ability)，所以稱該方法為DA特征選擇法。

DA方法基于兩點(diǎn)考慮來降低主導(dǎo)性平均方差。首先，使用文檔概率來表示特征與類別的相關(guān)程度，使得特征選擇避免受到先驗(yàn)分布的影響，特征在稀有類和多數(shù)類的相關(guān)程度得到相對公平的度量，不會偏向于選擇文檔數(shù)目多的類別的特征。其次，使用最小距離來衡量特征對于某類的區(qū)分能力的貢獻(xiàn)，使得對區(qū)分類別有貢獻(xiàn)的特征更容易被選中，弱化了大類強(qiáng)預(yù)測型特征的影響。

基于上述考慮，DA方法使用式(1)中所示的文檔概率來表示特征與文本類別的相關(guān)度，在文獻(xiàn)[9]中，文檔概率被稱為類內(nèi)分散度。然后利用特征在類別之間的相關(guān)程度的差異，計(jì)算出特征在各個(gè)類別間的區(qū)分能力。直觀上來看，一個(gè)特征詞在某個(gè)類別上出現(xiàn)的越多，在其他類別中出現(xiàn)的越少，該特征就越能把某類從其他類別中區(qū)分出來。

某特征詞在某個(gè)類別上的區(qū)分能力是指該特征在該類上的相關(guān)度與該特征在其他類上的相關(guān)度的差的最小值，該值越大，該特征區(qū)分該類與其他類的能力越大。計(jì)算公式如式(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ū)別能力的計(jì)算方法有兩種，一種是對該特征在各個(gè)類別上的區(qū)分能力求和，衡量特征針對數(shù)據(jù)集的平均區(qū)分能力，如式(6)所示；另一種是取該特征在各個(gè)類別上的區(qū)分能力的最大值，衡量特征針對數(shù)據(jù)集的最大區(qū)分能力，如式(7)所示。

(6)

(7)

由DA方法的定義可知，DA方法的基本思想是選擇對分類貢獻(xiàn)最大的特征。其與文獻(xiàn)[10]不同之處在于，DA方法使用特征在類別之間的差異而不是特征出現(xiàn)與否造成的類別分布的變化來衡量區(qū)分能力的。DA方法使用統(tǒng)一評分標(biāo)準(zhǔn)對每個(gè)特征進(jìn)行評分，按照評分高低進(jìn)行特征選擇，并不是如DFICF提高稀有類特征評分權(quán)重那樣顯著傾向于選擇稀有類特征。多數(shù)類與少數(shù)類的候選特征空間大小存在固有差別，因而經(jīng)DA方法得到的特征子集中的多數(shù)類特征仍然多于少數(shù)類特征，從而保證了多數(shù)類的性能。

6 實(shí)驗(yàn)設(shè)計(jì)與分析

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

本實(shí)驗(yàn)使用復(fù)旦大學(xué)的中文文本分類語料庫tc-corpus，復(fù)旦大學(xué)語料庫語料有20個(gè)類別，其中訓(xùn)練集和測試集中的每個(gè)類別的文檔數(shù)目比例都為1∶1。訓(xùn)練集共9 804篇，測試集共9 833篇。訓(xùn)練集與測試集的類別分布如表 1所示。

本文以100篇文檔以下的類別為稀有類，400篇文檔以上的類別為多數(shù)類。則由表1可知，數(shù)據(jù)集中共有11個(gè)稀有類，九個(gè)多數(shù)類。

表1 訓(xùn)練集與測試集的文檔數(shù)目分布

6.2 實(shí)驗(yàn)設(shè)計(jì)及評測指標(biāo)

本文的實(shí)驗(yàn)?zāi)繕?biāo)有兩個(gè)，其一是通過對比各種特征選擇方法在不平衡文本分類問題上的分類性能，驗(yàn)證本文提出的DA特征選擇方法的優(yōu)越性。其二是通過使用主導(dǎo)性平均方差對各種特征選擇方法得到的特征子集進(jìn)行分析，驗(yàn)證本文第4節(jié)推論2的正確性，同時(shí)也得到了在不平衡數(shù)據(jù)集上表現(xiàn)優(yōu)越的特征選擇方法的特點(diǎn)。

對于目標(biāo)一，本文實(shí)驗(yàn)將DA特征選擇方法與傳統(tǒng)特征選擇方法CHI、IG進(jìn)行對比，CHI即取CHI評分在所有類別上的最大值，另外使用之前針對不平衡數(shù)據(jù)集設(shè)計(jì)的特征選擇算法DFICF[15]作為與之前研究成果對比的基線。DFICF特征選擇方法的計(jì)算公式為：

(8)

其中，IG(t)是特征t使用信息增益方法得到的評分值，M為類別數(shù)目，mt為特征t出現(xiàn)的類別數(shù)目。

實(shí)驗(yàn)過程中，采用中國科學(xué)院ICTCLAS[16]分詞系統(tǒng)進(jìn)行中文分詞，向量化時(shí)采用TF-IDF方法對向量進(jìn)行加權(quán)，分類器則使用目前性能較好且應(yīng)用廣泛的支持向量機(jī)(SVM)和樸素貝葉斯兩種分類算法；其中，SVM分類器基于liblinear[17]程序包，該程序包是SVM使用線性核時(shí)的優(yōu)化版本，樸素貝葉斯算法則使用效果較好的多項(xiàng)式事件模型[18]。

為了使實(shí)驗(yàn)結(jié)果具有可信性。實(shí)驗(yàn)首先在兩類不平衡問題上進(jìn)行，包括兩類較不平衡問題與兩類極不平衡問題。然后在多類不平衡問題上進(jìn)行特征選擇方法的對比，在多類不平衡問題上的實(shí)驗(yàn)使用全部數(shù)據(jù)集。

對于分類預(yù)測結(jié)果，本文使用F1值的宏平均和微平均作為效果的評價(jià)指標(biāo)。F1值是準(zhǔn)確率與召回率的調(diào)和平均值，是一種綜合的測量指標(biāo)。微平均是指對于每一個(gè)實(shí)例的性能指標(biāo)的平均值，它將整個(gè)文檔集合看作一個(gè)整體。對于同一個(gè)數(shù)據(jù)集來說，它的準(zhǔn)確率、召回率和F1值的微平均值是相等的。宏平均是指對于每一個(gè)類別的性能指標(biāo)的平均值，它是將類別等同看待，這樣就避免了結(jié)果評測被大類支配的問題。

對于目標(biāo)二，本文在各特征選擇方法在多類不平衡問題對比實(shí)驗(yàn)的基礎(chǔ)上，對各個(gè)特征選擇方法產(chǎn)生的特征子集的主導(dǎo)性平均方差與分類性能的相關(guān)性進(jìn)行分析。

6.3 特征選擇對比的實(shí)驗(yàn)結(jié)果

6.3.1 較不平衡兩類分類對比實(shí)驗(yàn)

在較不平衡兩類分類實(shí)驗(yàn)中，使用數(shù)據(jù)集中的C34經(jīng)濟(jì)類與C37軍事類兩類進(jìn)行實(shí)驗(yàn)，其中，訓(xùn)練集中C37有74篇文檔，C34中有1 600篇文檔，從C34中隨機(jī)選取約1 500篇文檔，使得不平衡比為20∶1，測試集與訓(xùn)練集保持相同分布且文檔數(shù)目比例為1∶1。

由圖1與圖2可以看出，在兩類較不平衡問題中，F(xiàn)1宏平均與微平均的趨勢較為一致。當(dāng)特征數(shù)小于3 000時(shí)，DA方法處于劣勢，但當(dāng)特征數(shù)大于3 000時(shí)，不論是F1宏平均還是F1微平均，本文提出的方法優(yōu)于其他方法。就峰值而論，也是DA方法高于其他方法。

圖1 兩類較不平衡分類問題中F1宏平均隨特征數(shù)目變化趨勢圖

圖2 兩類較不平衡問題分類中F1微平均隨特征數(shù)目變化趨勢圖

需要注意的是，在兩類問題下，式(6)與式(7)就退化成了同一種方法。

為了節(jié)省篇幅，在兩類不平衡問題下不展示樸素貝葉斯算法的結(jié)果。由下文的多類不平衡問題下的實(shí)驗(yàn)結(jié)果可知，無論樸素貝葉斯算法與支持向量機(jī)算法，得到的結(jié)果是相似的。

6.3.2 極不平衡兩類分類對比實(shí)驗(yàn)

在該實(shí)驗(yàn)中，少數(shù)類仍然使用C37軍事類。多數(shù)類使用C19計(jì)算機(jī)類、C34經(jīng)濟(jì)類、C31環(huán)境類、C39運(yùn)動類、C32農(nóng)業(yè)類、C38政治類的組合。多數(shù)類從這六類的集合中隨機(jī)選取約7 400篇文檔，不平衡比例為100∶1，測試集與訓(xùn)練集分布一致且文檔比例為1∶1。

由圖3和圖4可以看出，在兩類極不平衡問題中，本文提出的特征選擇方法在F1宏平均上的優(yōu)勢進(jìn)一步擴(kuò)大，在F1微平均上的優(yōu)勢有減小的趨勢。表明了本文的特征選擇方法是在保證大類分類性能的情況下提高少數(shù)類的分類性能來提高總體性能的。

圖3 兩類極不平衡問題中F1宏平均隨特征數(shù)目的變化趨勢

6.3.3 多類不平衡分類對比實(shí)驗(yàn)

多類不平衡分類實(shí)驗(yàn)中，使用復(fù)旦大學(xué)語料的全部類別進(jìn)行實(shí)驗(yàn)，語料信息如6.1中所述。

在圖5與圖6中，DA-sum對應(yīng)式(6)的計(jì)算策略，DA-max對應(yīng)式(7)的計(jì)算策略。

圖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時(shí)與IG方法重合，但卻在特征數(shù)為2 000時(shí)達(dá)到了本次實(shí)驗(yàn)宏平均值的峰值。

圖7和圖8則分別展示了使用樸素貝葉斯分類器時(shí)IG、CHI、DA-sum、DA-max、DFICF五種特征選擇方法隨特征數(shù)目的不同F(xiàn)1微平均與宏平均指標(biāo)的變化。

圖7 多類不平衡分類問題中F1宏平均隨特征數(shù)目的變化趨勢(NB)

圖8 多類不平衡分類問題中F1微平均隨特征數(shù)目的變化趨勢(NB)

由圖7和圖8可知，使用樸素貝葉斯分類器時(shí)，在宏平均上仍然是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 實(shí)驗(yàn)結(jié)果分析總結(jié)

通過在二類較不平衡問題、二類極不平衡問題、多類不平衡問題上的實(shí)驗(yàn)，可以得出如下結(jié)論。

1. 在二類分類問題中，當(dāng)特征數(shù)目較大時(shí)，DA方法擁有較大的優(yōu)勢；在多類分類中則不論特征數(shù)目均有明顯優(yōu)勢。

2. 在樸素貝葉斯下的多類分類實(shí)驗(yàn)中，DA-max優(yōu)勢依舊，但DA-sum在宏平均中優(yōu)勢較小，在微平均中遜于IG與DFICF。表明特征選擇方法與分類算法之間具有一定的相關(guān)性。

3. 在二類較不平衡問題中，CHI與DFICF的峰值高于IG，但在其他兩個(gè)實(shí)驗(yàn)中，均有IG>IGICF>CHI。表明IG方法在不平衡問題上相比其他特征選擇函數(shù)仍有優(yōu)勢；

4. 在二類較不平衡問題的實(shí)驗(yàn)中，DFICF相對IG略有優(yōu)勢，在其他實(shí)驗(yàn)中，則表現(xiàn)與CHI相仿，表明單純地提高出現(xiàn)文檔數(shù)目少的特征的權(quán)重在多類不平衡問題下不能達(dá)到較好的改進(jìn)效果。

綜上所述，可以得到五種特征選擇函數(shù)在不平衡問題上的最終排名，即：

DA-max > DA-sum > IG > DFICF > CHI

6.4 特征選擇的主導(dǎo)性平均方差對比

本節(jié)針對多類不平衡問題分類實(shí)驗(yàn)中的特征選擇方法，按照第4節(jié)的主導(dǎo)性平均方差分析方法進(jìn)行了統(tǒng)計(jì)分析。特征數(shù)為3 000與5 000時(shí)的各特征選擇方法的分類性能與方差對比數(shù)據(jù)如表2與表3所示。其中，各項(xiàng)指標(biāo)的最優(yōu)值與次優(yōu)值用不同顏色標(biāo)出。

由表2與表3可以看到，宏平均值與平均方差的相關(guān)性比較強(qiáng)烈，主導(dǎo)性平均方差越低，宏平均值呈現(xiàn)越高的趨勢。對于特征數(shù)為3 000時(shí)的SVM宏平均與特征數(shù)為5 000時(shí)的NB宏平均，這一趨勢擬合的較好。對于特征數(shù)為3 000時(shí)的NB宏平均與特征數(shù)為5 000時(shí)的SVM宏平均，雖然存在著異常，但總的趨勢仍然一致。

由表2和表3還可得到，DA方法擁有較低的主導(dǎo)性平均方差與較高的宏平均值與微平均值，表明基于減小主導(dǎo)性平均方差來改進(jìn)特征選擇方法的思路是可行的。

表2 特征數(shù)為3 000時(shí)各特征方法分類性能與主導(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時(shí)各特征方法分類性能與主導(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

在特征選擇后的子集上進(jìn)行的主導(dǎo)性分析的結(jié)果證明了本文推論2的正確性，即在不平衡問題上越不被大類主導(dǎo)的特征選擇方法越能達(dá)到好的效果，表明主導(dǎo)性平均方差可以作為不平衡問題上指導(dǎo)特征選擇方法選取特征的一種原則。同時(shí)，也證明了本文提出的DA特征選擇方法在不平衡問題上是通過較為平衡的在稀有類和多數(shù)類之間選擇特征，以提高稀有類的性能且保證多數(shù)類的性能來提高整體性能。

7 結(jié)論與展望

文本分類中的不平衡問題是一個(gè)在實(shí)際應(yīng)用中很常見的問題，本文借鑒了前人在改進(jìn)特征選擇方法時(shí)的保證大類性能提高稀有類性能的思想，總結(jié)出了不被大類主導(dǎo)的特征選擇方法在不平衡問題上有更好效果的推論，并提出了主導(dǎo)性平均方差作為主導(dǎo)性的量化分析方法。在推論與量化方法的指導(dǎo)下，本文提出了DA特征選擇方法。該方法在與傳統(tǒng)特征選擇方法IG、CHI與針對不平衡改進(jìn)的DFICF特征選擇方法進(jìn)行的對比實(shí)驗(yàn)中，在宏平均上表現(xiàn)出了較大的優(yōu)勢，同時(shí)保證了微平均值，一定程度上可以解決不平衡分類問題。在五種特征選擇方法的主導(dǎo)性分析實(shí)驗(yàn)中，也進(jìn)一步證明了本文推論的正確性。這也對不平衡問題上的特征選擇方法的衡量提供了一種標(biāo)準(zhǔn)。

但是，本文提出的主導(dǎo)性分析方法在不同分類算法上的對應(yīng)趨勢存在一定的異常情況，表明本文的只有某類的強(qiáng)預(yù)測型特征被選中該類才可能被正確分類的弱假設(shè)可能存在著一定的缺陷，如何對主導(dǎo)性進(jìn)行更加準(zhǔn)確的分析是一個(gè)可研究方向。另外，特征選擇函數(shù)與分類算法的交互也是影響主導(dǎo)性分析的一個(gè)重要的因子。

本文提出的主導(dǎo)性分析方法的一個(gè)限制在于不能使用輪轉(zhuǎn)法等策略進(jìn)行特征在類別間的絕對或相對平衡，該限制基于本文提出的不平衡問題中各類別所需的用于分類的特征數(shù)目存在差異的假設(shè)，如何對基于該假設(shè)改進(jìn)特征選擇函數(shù)與主導(dǎo)性分析方法是本文的后續(xù)研究方向。

[1] 蘇金樹, 張博鋒, 徐昕. 基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J]. 軟件學(xué)報(bào), 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]. 計(jì)算機(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é)報(bào), 2004, 18(1): 26-32.

[7] 廖莎莎, 江銘虎. 中文文本分類中基于概念屏蔽層的特征提取方法[J]. 中文信息學(xué)報(bào), 2006, 20(3): 22-28.

[8] 張希娟, 王會珍, 朱靖波. 面向文本分類的基于最小冗余原則的特征選取[J]. 中文信息學(xué)報(bào), 2007, 21(5): 56-60.

[9] 熊忠陽, 蔣健, 張玉芳. 新的CDF文本分類特征提取方法[J]. 計(jì)算機(jī)應(yīng)用, 2009, 9(7): 1755-1757.

[10] 徐燕, 李錦濤, 王斌, 等. 基于區(qū)分類別能力的高性能特征選擇方法[J]. 軟件學(xué)報(bào), 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]. 計(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)域?yàn)闄C(jī)器學(xué)習(xí)、文本挖掘。E-mail:zhangyx@buaa.edu.cn潘海俠(1972—),博士研究生,副教授,碩士生導(dǎo)師,主要研究領(lǐng)域?yàn)樵品?wù)、服務(wù)科學(xué)與管理、軟件工程、人工智能等。E-mail:haixiapan@buaa.edu.cn

1003-0077(2015)04-0111-09

2013-09-05 定稿日期： 2014-01-10

TP391

A