基于不平衡數據的特征選擇算法研究

王俊紅，趙彬佳

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

0 概述

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

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

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

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

1 相關研究

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

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

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

Relief［15］算法是一種特征權重算法，特征和類別的相關性決定特征權重大小，特征權重越大，該特征的分類能力越強，特征權重小的特征將會被刪除，此方法只能用于二分類問題。為了使Relief 算法支持多分類問題，KONONENKO 等［16］對其進行改進，提出一種ReliefF 算法。信息增益（Information Gain，IG）［17］常用來進行特征選擇，通過計算每個特征對分類提供的信息量判斷特征的重要性程度。卡方統計［18］是在文本分類中經常出現的一種特征選擇方法，能有效提高文本分類的性能?；バ畔⒁步洺Ｓ米魈卣鬟x擇，文獻［19］提出一種新的基于迭代的定性互信息的特征選擇算法，利用隨機森林算法求出每個特征的效用得分，并將其與每個特征的互信息及其分類變量相結合。隨機森林能夠處理高維數據，并且有著較好的魯棒性，常被用來做特征選擇。

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

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

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

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

2 基于特征協同的FSBS 特征選擇算法

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

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

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

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

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

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

式（2）可改變如下：

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

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

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

FSBS 算法流程如圖1 所示。

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

FSBS 算法的偽代碼如下：

算法1FSBS 方法

3 實驗結果與分析

3.1 實驗數據

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

表1 實驗數據集Table 1 Experimental Datasets

本文實驗以少數類的分類準確度、多數類的分類準確度、總的分類準確度以及分類時間作為評價指標。以原始數據進行分類和FAST 算法特征選擇后進行分類作為對比。

3.2 實驗參數

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

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

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

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

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

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

3.3 實驗結果

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

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

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

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

表4 分類準確率1Table 4 Classification accuracy 1 %

表5 分類準確率2Table 5 Classification accuracy 2

表6 分類準確率3Table 6 Classification accuracy 3 %

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

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

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

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

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

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

4 結束語

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