基于F-score的特征選擇算法在多分類問題中的應(yīng)用

秦喜文, 王 芮, 于愛軍， 董小剛*, 張斯琪

(1.長(zhǎng)春工業(yè)大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 吉林 長(zhǎng)春 130012;2.北京首鋼國(guó)際工程技術(shù)有限公司， 北京 100043)

0 引 言

為了提高機(jī)器學(xué)習(xí)在分類問題上的準(zhǔn)確性和效率，一些研究者已經(jīng)開始將特征選擇算法與機(jī)器學(xué)習(xí)算法相結(jié)合。通過選擇重要的相關(guān)特征來降低計(jì)算成本，使得計(jì)算過程更加準(zhǔn)確和易于理解。

特征選擇可以通過過濾器、包裝器或嵌入方法進(jìn)行。過濾器方法為每個(gè)特征分配一個(gè)重要值以構(gòu)建一個(gè)排名，得分最高的特征是與數(shù)據(jù)類最密切相關(guān)的。這種方法可以使用與算法無關(guān)的技術(shù)，如F-score[1]，以及基于信息度量的數(shù)據(jù)驅(qū)動(dòng)變量選擇方法，如聯(lián)合互信息和正則化互信息等[2-3]。包裝器方法根據(jù)搜索算法確定的給定特征子集中分類器的性能來選擇特征。選擇分類器后，若干特征子集將用作分類器的輸入數(shù)據(jù)，然后選擇精度最高的特征子集。嵌入式方法將特征選擇融合在模型訓(xùn)練的過程中，比如決策樹在分枝的過程中，就是使用嵌入式特征選擇方法，其內(nèi)在還是根據(jù)某個(gè)度量指標(biāo)對(duì)特征進(jìn)行排序。 同時(shí)，隨機(jī)森林中的特征重要性排序也是嵌入式方法的一種。

機(jī)器學(xué)習(xí)已有近70年的發(fā)展歷史，隨著信息技術(shù)的不斷發(fā)展完善，機(jī)器學(xué)習(xí)也被廣泛應(yīng)用于各個(gè)領(lǐng)域。計(jì)算機(jī)利用機(jī)器學(xué)習(xí)算法，通過模擬人類的行為不斷提高機(jī)器的工作效率。自1949年，Hebb開啟機(jī)器學(xué)習(xí)的第一步后，機(jī)器學(xué)習(xí)經(jīng)歷數(shù)十年的發(fā)展不斷進(jìn)步。1984年，Breiman L L[4]提出了一個(gè)著名CART算法，也就是通常所說的決策樹(回歸樹)算法，該方法通過使用簡(jiǎn)單的規(guī)則可以在現(xiàn)實(shí)生活中找到更多的應(yīng)用。支持向量機(jī)(SVM)方法最初由Vapnik V等[5]提出用于二值分類，其基本思想是尋找兩個(gè)并行支持向量之間具有最大裕度的最優(yōu)分離超平面。2001年,Brianman L[6]提出隨機(jī)森林模型，隨機(jī)森林在大量應(yīng)用中證明了其在理論和實(shí)驗(yàn)上對(duì)過擬合的抵抗性。2013年,Anaissi A等[7]提出迭代隨機(jī)森林，能夠識(shí)別出特征的高階交互作用,同時(shí)能夠保證迭代隨機(jī)森林有很好的預(yù)測(cè)能力[8]。

文中利用Márcio Dias de Lima等[9]提出的新的基于F-score的特征選擇方法，將其與多個(gè)機(jī)器學(xué)習(xí)算法相結(jié)合用于多分類問題中，使用分類誤差為評(píng)價(jià)指標(biāo)驗(yàn)證它的魯棒性。

1 機(jī)器學(xué)習(xí)方法

1.1 決策樹算法

決策樹(CART)算法通過簡(jiǎn)單的圖像表達(dá)，就像樹一樣，所以被稱為決策樹。一個(gè)決策樹在構(gòu)建時(shí)，通過將數(shù)據(jù)劃分為具有相似值的子集來構(gòu)建出一個(gè)完整的樹。決策樹上每一個(gè)非葉節(jié)點(diǎn)都是一個(gè)特征屬性的測(cè)試，經(jīng)過每個(gè)特征屬性的測(cè)試，會(huì)產(chǎn)生多個(gè)分支，而每個(gè)分支就是對(duì)于特征屬性測(cè)試中某個(gè)值域的輸出子集。決策樹上每個(gè)葉子節(jié)點(diǎn)就是表達(dá)輸出結(jié)果的連續(xù)或者離散的數(shù)據(jù)。

1.2 支持向量機(jī)

支持向量機(jī)(SVM)方法最初由Vapnik V等[5]提出用于二值分類，與其他機(jī)器學(xué)習(xí)方法相比，它是一種很有前途的機(jī)器學(xué)習(xí)技術(shù)。SVM在統(tǒng)計(jì)學(xué)理論中有其基礎(chǔ)，該方法是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則(SRM)。支持向量機(jī)解決了一個(gè)二次規(guī)劃問題，確保一旦得到最優(yōu)解，它就是唯一(全局)解。

1.3 隨機(jī)森林

隨機(jī)森林(RF)算法將大量決策樹聚集在一起，并將它們一起用于預(yù)測(cè)最終結(jié)果。隨機(jī)森林中每棵樹都按照規(guī)則自由生長(zhǎng)，并且不需要對(duì)決策樹進(jìn)行剪枝。隨機(jī)森林作為Bagging的改進(jìn)方法，擁有極強(qiáng)的泛化能力。

1.4 迭代隨機(jī)森林

迭代隨機(jī)森林(iRF)的基本思想是在隨機(jī)森林基礎(chǔ)上,通過對(duì)選定的特征進(jìn)行“迭代重新賦權(quán)”，得到一個(gè)帶有特征權(quán)重的隨機(jī)森林，然后利用泛化的隨機(jī)交叉樹作用于帶有特征權(quán)重的隨機(jī)森林上，進(jìn)而識(shí)別出特征的高階交互作用，同時(shí)保證迭代隨機(jī)森林也有很好的預(yù)測(cè)能力。

2 特征選擇

2.1 隨機(jī)森林計(jì)算變量重要性

R軟件中的importance()函數(shù)可以被用于隨機(jī)森林算法中，用于度量變量的重要性。Mean Decrease Accuracy(平均減少度)表示在沒有該對(duì)應(yīng)特征的條件下分類準(zhǔn)確度下降的程度，即數(shù)值越大，說明該特征在分類效果中起到的作用越大;反之?dāng)?shù)值越小，表示該特征在分類效果中起到的作用越小。

2.2 條件互信息

基于互信息的特征選擇算法是通過使用互信息尋找與類高度相關(guān)而特征之間低冗余的特征。其中，條件互信息(CMI)測(cè)量給定第三個(gè)變量時(shí),兩個(gè)變量之間的條件依賴性[10]。

設(shè)

X=(x1,x2,…,xn),

Y=(y1,y2,…,yn),

Z=(z1,z2,…,zn)

是三組離散隨機(jī)變量。條件互信息(CMI)測(cè)量給定第三個(gè)變量時(shí)，兩個(gè)變量之間的條件依賴性。給定Z的變量X和Y的CMI定義為

I(X;Y|Z)=

(1)

式中：I(X;Y|Z)----變量X和Y給定變量Z共享的信息量。

2.3 基于F-score的特征選擇算法

F-score作為一種簡(jiǎn)單的方法，由Chen Y W等[1]于2006年提出，該方法用來衡量?jī)深悢?shù)據(jù)的區(qū)別。給定特征向量xi,i=1,2,…,k，如果正負(fù)實(shí)例的數(shù)目分別為n+和n-，則第i個(gè)特征的F分?jǐn)?shù)定義為

F(i)=

(2)

分子----正負(fù)集合之間的差異；

分母----兩個(gè)集合。

F值越大，該特征越有可能具有區(qū)別性。

F-score的一個(gè)缺點(diǎn)是不能揭示特征之間的相互關(guān)系。因此，Márcio Dias de Lima等[9]在此基礎(chǔ)上提出了一種新的變量選擇方法，分別求因變量標(biāo)簽的平方距離之和除以對(duì)應(yīng)實(shí)例的樣本方差，揭示了特征在不同標(biāo)簽數(shù)據(jù)集下的重要性。

同樣給定特征向量xi,i=1,2,…,k，如果正負(fù)實(shí)例的數(shù)目分別為n+和n-，則以下方程定義第i個(gè)特征的正負(fù)樣本排序,

(3)

等式的分子是正負(fù)樣本第i個(gè)特征均值與總體樣本第i個(gè)特征均值之間的平方距離，而分母分別表示正負(fù)樣本的樣本方差。

特征排序(FR)由下式獲得，其中分?jǐn)?shù)越高，特征越重要,

(4)

文中將該方法拓展應(yīng)用于多分類問題中。給定一個(gè)特征向量xi,i=1,2,…,k，因變量xj,j∈i,j≠i，假設(shè)因變量的所有標(biāo)簽用m∈R表示,則由以下方程定義第i個(gè)特征的標(biāo)簽樣本排序,

(5)

注意，上述式子的分子是第i個(gè)特征中屬于m類的均值和第i個(gè)特征總體均值之間的平方距離，分母分別匹配因變量標(biāo)簽的樣本方差。

特征總體排序由下式獲得，其中分?jǐn)?shù)越高，特征越重要,

(6)

3 實(shí)證分析

3.1 數(shù)據(jù)來源

文中以UCI數(shù)據(jù)庫中的5個(gè)公開數(shù)據(jù)為例來驗(yàn)證方法的可行性，為提高分類精度，在進(jìn)行實(shí)驗(yàn)之前對(duì)部分?jǐn)?shù)據(jù)預(yù)處理，包括對(duì)Whitewine-quality數(shù)據(jù)集第3類～第5類數(shù)據(jù)劃分為bad類，第6類數(shù)據(jù)劃分為mid類，第7類～第9類數(shù)據(jù)劃分為bad類,以及對(duì)Waveform中某些無意義的變量進(jìn)行刪除，最終剩余21個(gè)變量用于實(shí)驗(yàn)。數(shù)據(jù)集的具體描述見表1。

表1 數(shù)據(jù)集基本信息

3.2 交叉驗(yàn)證

在建模過程中,為了避免追求高準(zhǔn)確率而產(chǎn)生過擬合的情況，通常將原始數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集，從而使得模型在樣本外的數(shù)據(jù)上預(yù)測(cè)準(zhǔn)確率也有不錯(cuò)的精度。但是，劃分出的訓(xùn)練集、測(cè)試集的不同會(huì)使得模型準(zhǔn)確率產(chǎn)生明顯的變化。因此,為了保證輸出結(jié)果的可靠性，使用k(k=10)折交叉驗(yàn)證來評(píng)估算法性能。文中為保證數(shù)據(jù)的平衡性，對(duì)每個(gè)特征的數(shù)據(jù)采取k折隨機(jī)分割，每個(gè)特征選取一個(gè)子集組成具有n個(gè)隨機(jī)特征子集的訓(xùn)練集。這樣既保證了數(shù)據(jù)的平衡性，又保證了模型訓(xùn)練效果的準(zhǔn)確性。

文中所使用的十折交叉驗(yàn)證數(shù)據(jù)分割方法如圖1所示(每次選擇的測(cè)試集數(shù)據(jù)由深色部分標(biāo)出)。

圖1 交叉驗(yàn)證流程

通過十次交叉驗(yàn)證所得結(jié)果的平均值報(bào)告了所提出變量選擇方法與一些機(jī)器學(xué)習(xí)算法相結(jié)合的測(cè)試精度。

用于獲得最佳精度的參數(shù)見表2(文中使用的特征選擇方法簡(jiǎn)寫為Fs)。

表2 模型參數(shù)配置及分類結(jié)果

從測(cè)試分類誤差角度來看，基于F-score的特征排序方法與其他機(jī)器學(xué)習(xí)方法相結(jié)合，在多分類問題中能夠在選擇較少變量的情況下達(dá)到與未進(jìn)行變量選擇或與其他變量選擇方法相差無異，甚至更好。

3.3 結(jié)果分析

從表2可以得到以下分析結(jié)果：

針對(duì)Iris數(shù)據(jù)集，分類精度最好的方法為Importance+iRF和Fs+iRF，分類誤差為0.026 7，其次為Importance+RF和Fs+RF，分類誤差為0.033 3。分類最佳與次佳的誤差相差0.006 6。

針對(duì)Wine數(shù)據(jù)集，分類精度最好的方法為Importance+SVM和Importance+RF，分類誤差為0.016 7，但相比于Importance+RF方法，Importance+SVM只使用了5個(gè)變量便達(dá)到了最佳分類效果。其次為iRF、Importance+RF和Fs+iRF，分類誤差為0.017 0，但相比于其他兩種方法，F(xiàn)s+iRF只使用了7個(gè)變量以及一次迭代，分類最佳與次佳的誤差相差0.000 3。

針對(duì)Glass數(shù)據(jù)集，分類精度最好的方法為CMI+iRF，誤差為0.207 0，其次為iRF、Importance+iRF和Fs+iRF，分類誤差為0.214 0，分類最佳與次佳的誤差相差0.007 0。

針對(duì)Whitewine-quality數(shù)據(jù)集，分類精度最好的方法為基于iRF的四種方法，誤差為0.259 0，其次為RF和CMI+iRF，分類誤差為0.263 0，分類最佳與次佳的誤差相差0.004 0。

針對(duì)Waveform數(shù)據(jù)集，分類精度最好的方法為Fs+SVM，誤差為0.132 4，其次為SVM方法，分類誤差為0.137 4，然而結(jié)合Fs的SVM方法只使用了16個(gè)變量,即達(dá)到了最佳效果。

通過對(duì)比不同特征選擇方法與決策樹結(jié)合的分類效果可以看到，雖然基于F-score的特征排序方法在部分?jǐn)?shù)據(jù)集的表現(xiàn)不如使用隨機(jī)森林計(jì)算變量重要性的方法，但兩種方法的分類誤差差距不是很大。

通過對(duì)比不同特征選擇方法與SVM結(jié)合的分類效果可以看到，雖然基于F-score的特征排序方法在Iris、Wine和Whitewine-quality數(shù)據(jù)集的表現(xiàn)不如使用隨機(jī)森林計(jì)算變量重要性的方法和CMI方法，但針對(duì)這些數(shù)據(jù)集而言，其與最優(yōu)方法之間的差距僅為0.006 7、0.000 7和0.005 7，可以說方法之間的分類誤差差距極小。換個(gè)角度可以觀察到，同樣的數(shù)據(jù)集，基于F-score的方法在Iris和Whitewine-quality數(shù)據(jù)集上所使用的特征數(shù)相對(duì)較少。可以說該方法能夠與其他方法相媲美。

通過對(duì)比不同特征選擇方法與RF結(jié)合的分類效果可以看到，基于F-score的特征排序方法在Iris和Waveform數(shù)據(jù)集上的表現(xiàn)優(yōu)于其他方法，在 Wine、Glass和Whitewine-quality數(shù)據(jù)集上的表現(xiàn)雖然不是最好的，但分類誤差與其他方法相差不大。尤其在Whitewine-quality數(shù)據(jù)集，該方法與最優(yōu)方法之間的差距僅為0.005 7，且使用的特征數(shù)比全變量方法要少。

通過對(duì)比不同特征選擇方法與支持向量機(jī)結(jié)合的分類效果可以看到，基于F-score的特征排序方法在Iris、Wine、Whitewine-quality和Waveform數(shù)據(jù)集的表現(xiàn)最佳，在Glass數(shù)據(jù)集上的表現(xiàn)稍遜色于條件互信息方法，但分類效果相差甚微。反觀Whitewine-quality數(shù)據(jù)集，模型的精度都是在全變量條件下達(dá)到最優(yōu)，可以斷定這兩個(gè)數(shù)據(jù)集之間的特征相關(guān)系數(shù)較小，特征區(qū)分度較大。

綜上所述，與支持向量機(jī)、隨機(jī)森林和迭代隨機(jī)森林相結(jié)合的特征選擇方法都優(yōu)于與決策樹相結(jié)合的方法，尤其是基于F-score和基于隨機(jī)森林計(jì)算變量重要性特征選擇方法。特征選擇與迭代隨機(jī)森林方法相結(jié)合時(shí)能夠顯著提高模型精度。同時(shí)基于F-score的特征選擇方法與機(jī)器學(xué)習(xí)方法相結(jié)合能夠達(dá)到較好的分類效果，可以在選擇少數(shù)變量的同時(shí)達(dá)到與傳統(tǒng)方法無異的效果，甚至是更好的分類精度。F-score通過分別計(jì)算每個(gè)特征在各個(gè)類別標(biāo)簽下的分?jǐn)?shù)，然后計(jì)算這些分?jǐn)?shù)之間的平均值，揭示了特征之間的相互關(guān)系。相比之下，條件互信息特征選擇方法在低維小樣本數(shù)據(jù)中的表現(xiàn)就沒有那么出色。

4 結(jié) 語

利用Márcio Dias de Lima等[9]提出的新的基于F-score的特征選擇方法，將其與多個(gè)機(jī)器學(xué)習(xí)算法相結(jié)合用于多分類問題中，使用分類誤差作為評(píng)價(jià)指標(biāo)驗(yàn)證它的魯棒性。該變量選擇算法的每個(gè)特征得分都是相對(duì)于因變量的標(biāo)簽分別計(jì)算的。然后，計(jì)算標(biāo)簽對(duì)應(yīng)分?jǐn)?shù)的平均值，提供最終排名用于機(jī)器學(xué)習(xí)模型中。主要研究?jī)?nèi)容包括以下幾個(gè)方面。

1)將該方法與未進(jìn)行變量選擇的模型(CART、SVM、RF、iRF)使用隨機(jī)森林importance函數(shù)所選特征相結(jié)合的機(jī)器學(xué)習(xí)模型,以及使用條件互信息(CMI)方法選特征相結(jié)合的機(jī)器學(xué)習(xí)模型相比較，驗(yàn)證了該變量選擇方法在多分類問題中的有效性。

2)文中使用十折交叉驗(yàn)證數(shù)據(jù)篩選框架用于模型效果對(duì)比，這樣既保證了數(shù)據(jù)的平衡性，又保證了模型訓(xùn)練效果的準(zhǔn)確性。

3)實(shí)驗(yàn)結(jié)果表明，該方法能夠使用比原始數(shù)據(jù)集更少特征，并產(chǎn)生良好分類結(jié)果，尤其在與迭代隨機(jī)森林方法相結(jié)合的情況下，能夠顯著提高模型分類精度。

F-score方法是一種過濾器方法，能夠?yàn)槊總€(gè)特征分配一個(gè)得分，以構(gòu)建特征排名，這種包括特征排序的方法是特別吸引人的。得分最高的特征是與因變量最密切相關(guān)的特征，反之，得分較低的特征則表示與因變量關(guān)系較小。這種過濾器方法使用與算法無關(guān)的技術(shù)比較簡(jiǎn)單，易于運(yùn)行和理解。

文中仍存在一些不足與值得改進(jìn)的地方，如文中所使用的基于F-score的特征選擇方法是一種單變量特征選擇方法，需要使用窮舉方法測(cè)試每個(gè)所選擇的特征子集的分類效果，雖然難度不高，但十分費(fèi)時(shí)耗力。一種自適應(yīng)的特征子集選擇方法有待被開發(fā)應(yīng)用于基于F-score的特征選擇算法中。其次，文中只選用了四種機(jī)器學(xué)習(xí)方法，更多的方法有待被發(fā)掘與應(yīng)用。針對(duì)不同的數(shù)據(jù)特征，選擇合適的分類方法也是分類問題的關(guān)鍵。