王俊紅，趙彬佳

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

0 概述

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

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

FSBS 算法流程如圖1 所示。

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

FSBS 算法的偽代碼如下：

算法1FSBS 方法

3 實(shí)驗(yàn)結(jié)果與分析

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental Datasets

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

3.2 實(shí)驗(yàn)參數(shù)

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

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

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果

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

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

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

在14 個(gè)數(shù)據(jù)集中，F(xiàn)SBS 算法有3 種不同的效果：第1 種提升了分類準(zhǔn)確率（見表4）；第2 種使用更少的特征，卻保持了最高的分類準(zhǔn)確率（見表5）；第3 種提升了正類的準(zhǔn)確率，負(fù)類準(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 個(gè)數(shù)據(jù)集使用FSBS 算法后，在不同程度上提高了分類準(zhǔn)確率。其中1 個(gè)數(shù)據(jù)集在3 個(gè)分類器上的分類準(zhǔn)確率均有提高。5 個(gè)數(shù)據(jù)集在決策樹上的分類準(zhǔn)確率都得到了提高。

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

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

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

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

表8 含特征選擇時(shí)間的分類時(shí)間對(duì)比Table 8 Classificationtime comparison of including feature selectiontime s

4 結(jié)束語

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