基于不平衡數(shù)據(jù)的特征選擇算法研究

王俊紅，趙彬佳

（1.山西大學(xué)計算機與信息技術(shù)學(xué)院，太原 030006；2.山西大學(xué)計算智能與中文信息處理教育部重點實驗室，太原 030006）

0 概述

特征選擇是數(shù)據(jù)降維的一種重要方法［1］，最早出現(xiàn)在上世紀60 年代，它的本質(zhì)是從最開始的M個特征中選取某種標(biāo)準(zhǔn)下表現(xiàn)最好的N個特征組成特征子集［2］，以便訓(xùn)練出更加精確的模型，得出更滿意的分類效果，取得更清楚的分析結(jié)論［3］。特征選擇具有減少儲存需求、減少訓(xùn)練時間、提高學(xué)習(xí)的準(zhǔn)確率等優(yōu)點，在機器學(xué)習(xí)等諸多領(lǐng)域具有不可替代的作用［4］。

不平衡數(shù)據(jù)是指數(shù)據(jù)集中的某個或某些類的樣本量遠遠高于其他類，而某些類樣本量較少，通常把樣本量較多的類稱為多數(shù)類，樣本量較少的類稱為少數(shù)類。不平衡分類問題廣泛存在于多個領(lǐng)域，例如文本分類、醫(yī)學(xué)診斷、信用卡欺詐檢測、垃圾郵件判斷等［5］。而在這些應(yīng)用中，人們對研究少數(shù)類更感興趣，少數(shù)類中的樣本往往更有價值。

隨著社會的發(fā)展和進步，越來越多的數(shù)據(jù)是高維且不平衡的，這給數(shù)據(jù)挖掘工作帶來前所未有的挑戰(zhàn)。在分類任務(wù)中，這些高維數(shù)據(jù)中存在大量無關(guān)特征和冗余特征，不僅需要大量的運行時間，還會影響分類效果。當(dāng)這些高維數(shù)據(jù)中存在類別不平衡現(xiàn)象時，傳統(tǒng)的分類算法在少數(shù)類上的分類效果總是不盡人意［6］。因此，對于不平衡數(shù)據(jù)集分類，特別當(dāng)數(shù)據(jù)同時也是高維時，特征選擇有時比分類算法更重要［7］。

FAST（Feature Assessment by Sliding Thresholds）算法［8］根據(jù)AUC 值（ROC 曲線下面積）評估特征，而AUC 值是一個較好的預(yù)測性能的指標(biāo)，尤其是對于不平衡數(shù)據(jù)分類問題，但該方法沒有考慮特征之間的協(xié)同作用。具有協(xié)同作用的特征是指各自對目標(biāo)集不相關(guān)，但兩者相結(jié)合卻對目標(biāo)集高度相關(guān)的特征，若不考慮則可能刪除這些有協(xié)同作用的特征，導(dǎo)致分類性能下降。本文對FAST 算法進行改進，提出一種基于特征協(xié)同的FSBS 特征選擇算法。運用UCI 數(shù)據(jù)集進行實驗，將原始數(shù)據(jù)進行直接分類，并與特征選擇后進行分類的FAST 算法作為對比，以驗證FSBS 方法的分類性能。

1 相關(guān)研究

特征選擇算法一般需要確定搜索起點和方向、搜索策略、特征評估函數(shù)和停止準(zhǔn)則4 個要素。在特征選擇中，搜索策略和特征評估函數(shù)是比較重要的2 個步驟，因此將特征選擇算法分為兩大類。

按照搜索策略可以將特征選擇方法分為全局最優(yōu)搜索、序列搜索和隨機搜索3 種［9］。全局最優(yōu)搜索有窮舉法和分支定界法［10］。序列搜索根據(jù)搜索方向的不同可分為前向搜索、后向搜索和雙向搜索3 類。隨機搜索策略具有較強的不確定性，遺傳算法（GA）［11］、模擬退火算法（SA）［12］和蟻群算法（ACO）［13］是常用的隨機搜索方法。

特征評估函數(shù)對特征選擇至關(guān)重要，特征子集的好壞取決于評估函數(shù)，現(xiàn)有的特征評估函數(shù)大致分為信息度量、距離度量、依賴性度量、一致性度量和分類性能5 類［14］。

Relief［15］算法是一種特征權(quán)重算法，特征和類別的相關(guān)性決定特征權(quán)重大小，特征權(quán)重越大，該特征的分類能力越強，特征權(quán)重小的特征將會被刪除，此方法只能用于二分類問題。為了使Relief 算法支持多分類問題，KONONENKO 等［16］對其進行改進，提出一種ReliefF 算法。信息增益（Information Gain，IG）［17］常用來進行特征選擇，通過計算每個特征對分類提供的信息量判斷特征的重要性程度?？ǚ浇y(tǒng)計［18］是在文本分類中經(jīng)常出現(xiàn)的一種特征選擇方法，能有效提高文本分類的性能。互信息也經(jīng)常用作特征選擇，文獻［19］提出一種新的基于迭代的定性互信息的特征選擇算法，利用隨機森林算法求出每個特征的效用得分，并將其與每個特征的互信息及其分類變量相結(jié)合。隨機森林能夠處理高維數(shù)據(jù)，并且有著較好的魯棒性，常被用來做特征選擇。

針對不平衡數(shù)據(jù)的分類問題，目前主要從數(shù)據(jù)層面和算法層面來解決。數(shù)據(jù)層面可以使用過采樣方法增加少數(shù)類樣本，也可以使用欠采樣方法減少多數(shù)類樣本，還可以使用混合采樣方法平衡數(shù)據(jù)集。SMOTE［20］是一種經(jīng)典的過采樣方法，通過合成樣本增加正類樣本數(shù)量。文獻［21］提出一種利用樸素貝葉斯分類器的欠采樣方法，以隨機初始選擇為基礎(chǔ)，從可用的訓(xùn)練集中選擇信息最豐富的實例。過采樣方法和欠采樣方法都存在缺陷，過采樣方法容易造成數(shù)據(jù)過擬合，而欠采樣方法容易丟失有用信息。

在算法層面，傳統(tǒng)的分類器假定類別之間的誤分類代價是相同的，但是在不平衡數(shù)據(jù)中，少數(shù)類的誤分類代價往往高于多數(shù)類。因此，很多針對不平衡數(shù)據(jù)的分類過程都伴隨代價敏感學(xué)習(xí)，當(dāng)少數(shù)類被錯分時，賦予更高的懲罰代價，使分類器對少數(shù)類的關(guān)注增加。文獻［22］利用HCSL 算法建立代價敏感的決策樹分類器。文獻［23］將模式發(fā)現(xiàn)與代價敏感方法相結(jié)合來解決類別不平衡問題。

將特征選擇應(yīng)用到不平衡數(shù)據(jù)，在近年來已經(jīng)引起了研究者的關(guān)注。CHEN 等［8］提出一種基于AUC 評價標(biāo)準(zhǔn)的特征選擇方法。文獻［24］將遞歸特征消除和主成分分析運用到隨機森林中，并結(jié)合SMOTE 方法處理不平衡數(shù)據(jù)。SUN 等［25］提出一種基于分支與邊界的混合特征選擇（BBHFS）與不平衡定向多分類器集成（IOMCE）相結(jié)合的不平衡信用風(fēng)險評估方法，在減少特征數(shù)量的同時保留更多的有用信息。BIAN 等［26］將代價敏感學(xué)習(xí)應(yīng)用到特征選擇中，提出一種代價敏感特征選擇方法，通過給正類賦予更高的懲罰代價值使得算法對正類關(guān)注增加。SYMON 等［27］使用對稱不確定性衡量特征與標(biāo)簽之間的依賴性，同時還使用harmony 搜索以選擇最佳的特征組合，是一種適用于高維不平衡數(shù)據(jù)集的特征選擇方法。

FAST 算法［8］根據(jù)AUC 值來評估特征，該方法通過在多個閾值上對樣本進行分類并計算每個閾值處的真正例率和假正例率，從而構(gòu)建ROC 曲線并計算該曲線下的面積。AUC 大的特征往往具有更好的預(yù)測能力，因此將AUC 用作特征等級。

2 基于特征協(xié)同的FSBS 特征選擇算法

多數(shù)特征選擇算法通常只有單一的決策邊界［28］，當(dāng)改變這個決策邊界時，可能產(chǎn)生更多的真正例和更少的真反例，也可能產(chǎn)生更少的真正例和更多的真反例。在不平衡數(shù)據(jù)中，這種情況的發(fā)生會嚴重影響分類效果。因此，需要不斷滑動閾值來確定哪個特征集更好，這樣才能夠更好地對不平衡數(shù)據(jù)集進行分類。ROC 曲線對樣例進行排序，按此順序逐個把樣本作為正例進行預(yù)測（即滑動閾值），每次預(yù)測后計算假正例率和真正例率，分別以它們作為橫縱坐標(biāo)作圖得到ROC 曲線。研究發(fā)現(xiàn)，那些在不平衡數(shù)據(jù)集上表現(xiàn)較好的分類器，是因為在特征選擇時使用了主要關(guān)注少數(shù)類的度量標(biāo)準(zhǔn)［8］。因此，基于不平衡數(shù)據(jù)的特征選擇算法需要使用適合不平衡數(shù)據(jù)的度量標(biāo)準(zhǔn)。利用ROC 曲線進行評估的一個巨大優(yōu)勢是：即便正負樣本數(shù)量發(fā)生變化，ROC 曲線形狀基本保持不變。因此，ROC 曲線能夠更加客觀也衡量學(xué)習(xí)器本身的好壞，適合于不平衡數(shù)據(jù)集。如果需要對學(xué)習(xí)器進行量化分析，比較合適的標(biāo)準(zhǔn)是ROC 曲線下的面積，即AUC。

FAST 方法通過計算每一個特征的AUC 值，選取AUC 值大于預(yù)設(shè)閾值的特征組成特征子集，非常適合不平衡數(shù)據(jù)集上的特征選擇。此方法只是對單個特征進行評估，因此有一個不足之處，即沒有考慮特征與特征之間的相互影響。如果數(shù)據(jù)集中存在協(xié)同的特征，則該方法容易將這些特征忽略，導(dǎo)致分類性能下降。為解決該問題，提高分類準(zhǔn)確率，本文在原算法的基礎(chǔ)上考慮特征之間的協(xié)同作用，提出了FSBS 方法。

協(xié)同的特征是指各自對目標(biāo)集不相關(guān)或弱相關(guān)，但兩者相結(jié)合卻對目標(biāo)集高度相關(guān)的特征。本文以相互增益評價協(xié)同作用大小，在介紹相互增益前，先引入信息熵和信息增益的概念。

信息熵是SHANNON 在1948 年提出的，用來評估樣本集合純度的一個參數(shù)。給出一個樣本集合，該集合中的樣本可能屬于多個不同的類別，也可能只屬于一個類別，那么如果屬于多個不同的類別，則該樣本是不純的，如果只屬于一個類別，則該樣本是純潔的。信息熵是計算一個樣本集合中的數(shù)據(jù)是否純潔，信息熵越小，表明這個數(shù)據(jù)集越純潔。信息熵的最小值為0，此時數(shù)據(jù)集D中只含有一個類別。

信息增益是指信息熵的有效減少量。一個特征的信息增益越大，說明該特征的分類性能越強。假設(shè)特征為X={x1,x2,…,xn}，標(biāo)簽為Y={y1,y2,…,ym}，它們的聯(lián)合概率分布為p(xi,yj)，xi代表特征中的某個取值，yj代表標(biāo)簽中的某個取值，其 中，i=1,2,…,n，j=1,2,…,m。則信息增益I(X；Y)的計算公式如下：

JAKULIN 等［29-30］提出了相互增益的概念。相互增益可以衡量協(xié)同作用的大小，可以為正、零，還可以為負。假設(shè)X和Y是特征，Z是標(biāo)簽，則相互增益的計算公式如下：

式（2）可改變?nèi)缦拢?/p>

從上式可以看出，當(dāng)2 個特征在一起時的信息增益大于它們單獨存在時的信息增益，相互增益為正值。相互增益為正值，說明特征之間存在協(xié)同作用，相互增益越大，協(xié)同作用越強。

FSBS 方法首先計算所有特征兩兩之間的相互增益，然后求每個特征與其他特征相互增益的算術(shù)平均值A(chǔ)ve（即為某個特征的平均相互增益），再用每個特征的AUC 值和平均相互增益Ave 按式（4）計算得到C_AUC。式（4）將AUC 值和平均相互增益融合形成一個新的標(biāo)準(zhǔn)評價每個特征。

其中：AUC 的取值范圍為0.5～1.0；Ave 的值可能為正數(shù)，也可能為負數(shù)。在算法的最后設(shè)置閾值q，選取C_AUC 超過閾值的特征組成特征子集。

FSBS 算法流程如圖1 所示。

圖1 FSBS 算法流程Fig.1 FSBS algorithm procedure

FSBS 算法的偽代碼如下：

算法1FSBS 方法

3 實驗結(jié)果與分析

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

為評估FSBS 算法的性能，以證實FSBS 方法能有效地用于實踐，本文從UCI 數(shù)據(jù)庫中選擇了14 個數(shù)據(jù)集來進行實驗對比分析。這14 個數(shù)據(jù)集的特征個數(shù)最少為4，最大為1 470，數(shù)據(jù)的不平衡比大小不同。數(shù)據(jù)集如表1 所示。

表1 實驗數(shù)據(jù)集Table 1 Experimental Datasets

本文實驗以少數(shù)類的分類準(zhǔn)確度、多數(shù)類的分類準(zhǔn)確度、總的分類準(zhǔn)確度以及分類時間作為評價指標(biāo)。以原始數(shù)據(jù)進行分類和FAST 算法特征選擇后進行分類作為對比。

3.2 實驗參數(shù)

本文在實驗中運用式（4）計算C_AUC。為確定式（4）中Ave 擴大多少倍，實驗中使用上文的14 個數(shù)據(jù)集，以決策樹為分類器進行實驗，分別將Ave 擴大1 倍、10 倍、100 倍以及1 000 倍，以G-mean 值 作為評價指標(biāo)。不同情況下各數(shù)據(jù)集的G-mean 值對比如圖2 所示。

圖2 不同情況下C_AUC 值對比Fig.2 Comparison of C_AUC values in different cases

實驗結(jié)果表明，在Ave 擴大100 倍時效果最佳，有12 個數(shù)據(jù)集G-mean 值最高，因此式（4）中確定為擴大100 倍。

閾值q的選取會影響特征數(shù)量，實驗中將閾值q分別設(shè)置為所有特征的C_AUC 中最大值與最小值之和的0.3 倍、0.4 倍、0.5 倍、0.6 倍、0.7 倍。當(dāng)最大值與最小值之和為正數(shù)時，隨著倍數(shù)的提高，閾值q增大，特征數(shù)量呈下降趨勢。反之，當(dāng)最大值與最小值之和為負數(shù)時，隨著倍數(shù)的提高，閾值q減小，特征數(shù)量呈增加趨勢。不同閾值下特征數(shù)量如表2所示。

表2 不同閾值下的特征數(shù)量比較Table 2 Comparison of features number different thresholds

分析表2 可知：在閾值q為0.3 倍和0.7 倍時，會導(dǎo)致在部分數(shù)據(jù)集上特征相對較多，而另一部分數(shù)據(jù)集上特征相對較少；在閾值為0.4 倍和0.6 倍時，此種情況減輕；在閾值為0.5 倍時，情況最好。因此，本在文實驗中，F(xiàn)SBS 方法在生成特征子集時的閾值q最終設(shè)置為M個特征的C_AUC 值中最大值和最小值的算術(shù)平均數(shù)（即0.5 倍）。

3.3 實驗結(jié)果

為更好地比較2 個算法選擇的特征子集的優(yōu)劣，驗證算法的性能，分別使用SVM、決策樹、隨機森林3 種分類器進行分類。在本文實驗中訓(xùn)練集為總樣本數(shù)的90%，測試集為總樣本數(shù)的10%。

表3 所示為原始數(shù)據(jù)的特征個數(shù)、FAST 方法選擇后的特征個數(shù)以及FSBS 方法選擇后的特征個數(shù)。分析表3 可以發(fā)現(xiàn)，F(xiàn)SBS 方法對原始數(shù)據(jù)進行特征選擇后特征的數(shù)量都比原始數(shù)據(jù)少，顯然這和閾值q的設(shè)置有關(guān)。與FAST 相比，兩者對原始數(shù)據(jù)進行特征選擇后特征數(shù)量沒有必然聯(lián)系，即使這2 種特征選擇方法處理后特征數(shù)量一樣，特征也不一定相同。

表3 不同方法的特征數(shù)量比較Table 3 Comparison of feature numbers of different methods

在14 個數(shù)據(jù)集中，F(xiàn)SBS 算法有3 種不同的效果：第1 種提升了分類準(zhǔn)確率（見表4）；第2 種使用更少的特征，卻保持了最高的分類準(zhǔn)確率（見表5）；第3 種提升了正類的準(zhǔn)確率，負類準(zhǔn)確率只有輕微下降（見表6）。在表4～表6 中：①代表原數(shù)據(jù)；②代表FAST 算法選擇后的數(shù)據(jù)；③代表FSBS 方法選擇后的數(shù)據(jù)。

表4 分類準(zhǔn)確率1Table 4 Classification accuracy 1 %

表5 分類準(zhǔn)確率2Table 5 Classification accuracy 2

表6 分類準(zhǔn)確率3Table 6 Classification accuracy 3 %

從表4 可以看出，5 個數(shù)據(jù)集使用FSBS 算法后，在不同程度上提高了分類準(zhǔn)確率。其中1 個數(shù)據(jù)集在3 個分類器上的分類準(zhǔn)確率均有提高。5 個數(shù)據(jù)集在決策樹上的分類準(zhǔn)確率都得到了提高。

從表5 可以看出，6 個數(shù)據(jù)集使用FSBS 算法在特征數(shù)量盡可能少的情況下，可以保持最高的分類準(zhǔn)確率。當(dāng)數(shù)據(jù)維度較大時，能在特征數(shù)量較少的情況下保持較高的準(zhǔn)確率是至關(guān)重要的，可以縮短運行時間，減少存儲成本。

從表6 可以看出，3 個數(shù)據(jù)集上負類分類準(zhǔn)確率有輕微減少，但在正類上提升效果明顯。在不平衡數(shù)據(jù)分類中，本文對正類更感興趣，正類錯分比負類錯分代價更大，因此可以以犧牲部分負類分類準(zhǔn)確率為代價，提高正類分類準(zhǔn)確率。但在數(shù)據(jù)ecoli 中，雖然負類分類準(zhǔn)確率下降較多，但是測試集少，只分錯3 個樣本。

如表7 所示，在進行分類時重復(fù)10 次，求取平均值得到分類時間（SVM、決策樹、隨機森林3 個分類器的分類總時間）。對比發(fā)現(xiàn)在多數(shù)數(shù)據(jù)集上，F(xiàn)AST 和FSBS 都可以使分類時間變短，原因是經(jīng)過特征選擇后，特征數(shù)量下降，所以分類時間變短。而在個別數(shù)據(jù)集上（ecoli 和yeast）分類時間增加，是由于特征選擇后，特征數(shù)量幾乎保持不變（詳見表3），而且經(jīng)過特征選擇后，數(shù)據(jù)集中特征位置發(fā)生變化，使得分類器耗時更長。在表7 中，分類時間不含特征選擇時間，但考慮到在高維數(shù)據(jù)中特征選擇花費的時間不可忽略，在表8 中，將特征選擇時間包含進去進行比較。表8 顯示在部分數(shù)據(jù)集上，特征選擇后的分類時間依然比原始數(shù)據(jù)進行分類的時間要短，但當(dāng)數(shù)據(jù)集中特征數(shù)量較多或樣本數(shù)量較多時，F(xiàn)SBS 方法處理后的分類時間較高。

表7 不含特征選擇時間的分類時間對比Table 7 Classification time comparison of excluding feature selectiontime s

表8 含特征選擇時間的分類時間對比Table 8 Classificationtime comparison of including feature selectiontime s

4 結(jié)束語

本文通過對FAST 算法進行改進，在FAST 算法的基礎(chǔ)上考慮特征的協(xié)同作用，提出一種新的特征選擇算法。通過計算特征之間的相互增益，分析特征與特征之間的協(xié)同度，從而使協(xié)同作用大的特征更容易被選擇到。實驗結(jié)果表明，該算法能在一定程度上提高分類性能，尤其是少數(shù)類的準(zhǔn)確率。但該方法在計算特征之間的相互增益時會增加運行時間，因此快捷有效地選擇有協(xié)同作用的特征并進行高效應(yīng)用是下一步的研究重點。