基于最大信息系數(shù)的關(guān)聯(lián)性特征選擇算法:MICCFS

羅幼喜, 謝昆明, 胡超竹, 李翰芳

(湖北工業(yè)大學(xué)理學(xué)院, 武漢 430068)

在日益增長(zhǎng)的高維復(fù)雜數(shù)據(jù)分析中,數(shù)據(jù)降維是去除數(shù)據(jù)中多余信息、使數(shù)據(jù)“干凈化”的有效手段,降維主要有特征選擇和特征抽取兩類,特征抽取是在原始特征上再創(chuàng)造新的特征,特征選擇是選擇原始特征的子集,去除的是冗余特征和不相關(guān)特征[1].對(duì)目標(biāo)變量有用的特征往往只有少數(shù)幾個(gè),特征選擇能減少計(jì)算時(shí)間并且增加模型的可解釋性[2].特征選擇可分為三種類型:過濾式,包裹式和嵌入式[3].包裹式通常以最終使用學(xué)習(xí)器的性能作為特征子集的評(píng)價(jià)準(zhǔn)則[4],通常表現(xiàn)較好但計(jì)算量較大,如SVMRFE[5](support vector machine recursive feature elimination);嵌入式是在算法學(xué)習(xí)過程中就選擇出最優(yōu)特征,計(jì)算量較大,如LASSO(least absolute shrinkage and selection operator)算法[6];而過濾式是獨(dú)立于分類器的,通常計(jì)算量較低,速度較快[7],先選擇特征后再進(jìn)行訓(xùn)練,尤其在高維數(shù)據(jù)中具有可操作性,過濾式特征選擇常見有互信息最大化(mutual information maximization,MIM)[8]、Relief F[9]、卡方法(Chi-Square)[10]等.

基于關(guān)聯(lián)性特征選擇算法(correlation-based feature selection,CFS)[7]是基于一種評(píng)價(jià)準(zhǔn)則進(jìn)行搜索最優(yōu)子集的算法,由于其同時(shí)考慮到特征與目標(biāo)變量的相關(guān)性以及特征與特征之間的冗余性,所以被廣泛應(yīng)用于各領(lǐng)域,如李浩文等[11]將算法應(yīng)用于短期風(fēng)電功率預(yù)測(cè)的關(guān)鍵影響特征選擇問題中,邱純等[12]則利用其篩選大規(guī)模膠質(zhì)瘤相關(guān)基因.CFS算法思想是一個(gè)好的特征子集應(yīng)該與輸出類別高度相關(guān)而與其他特征不相關(guān)[7,13],評(píng)價(jià)準(zhǔn)則是基于選出的特征與類之間平均相關(guān)性最大化、特征之間平均相關(guān)性最小化的思想來評(píng)估特征子集的價(jià)值,以此進(jìn)行搜索特征子集,對(duì)于回歸和分類任務(wù),度量?jī)蓚€(gè)變量之間的關(guān)系分別是線性相關(guān)系數(shù)和對(duì)稱不確定度量SU.而線性相關(guān)系數(shù)只能度量?jī)蓚€(gè)變量間存在的線性關(guān)系,無法檢測(cè)其他非線性關(guān)系;SU是一種歸一化的互信息,SU的分母過大[14],同時(shí)互信息在計(jì)算連續(xù)變量相關(guān)性時(shí)不易計(jì)算,通常需要離散化,而互信息的計(jì)算結(jié)果受不同離散化的方式的影響較大[15].如何改進(jìn)CFS中相關(guān)性度量方法,使其既能度量變量間的線性關(guān)系和任意非線性關(guān)系,且同時(shí)適用于離散型變量和連續(xù)型變量是該算法研究中的一項(xiàng)重要課題.Reshef等[16]在2011年提出的最大信息系數(shù)(maximal information coefficient,MIC)為解決該問題提供了一條重要途徑. MIC是一種度量屬性間相關(guān)性的方法,不僅能度量變量間的線性關(guān)系,也能度量其非線性關(guān)系以及非函數(shù)關(guān)系,適用離散和連續(xù)數(shù)據(jù).Reshef等還證明了MIC具有較強(qiáng)泛化性和公平性,適用于變量間任意形式的函數(shù),對(duì)于不同形式函數(shù)的相同水平噪聲能得到同樣的結(jié)果.該度量方法一經(jīng)提出就引起眾多學(xué)者關(guān)注,被廣泛應(yīng)用于醫(yī)學(xué)[17]、電力[18]、環(huán)境[19]、軍事[20]等領(lǐng)域.

鑒于MIC良好的相關(guān)性度量特性,本文擬針對(duì)CFS算法的不足,提出一種基于MIC的CFS特征選擇算法:MICCFS.將回歸和分類中度量變量間相關(guān)性方式改進(jìn)成MIC,依據(jù)評(píng)價(jià)準(zhǔn)則來進(jìn)行特征搜索選擇,并通過實(shí)際數(shù)據(jù)比較和分析算法的有效性.

1 基于關(guān)聯(lián)性的特征選擇算法

基于關(guān)聯(lián)性的特征選擇算法(CFS)[7]是一種同時(shí)考慮特征間冗余性和特征與響應(yīng)變量間的關(guān)聯(lián)性的算法,是基于特征搜索空間的算法.其基本思想是一個(gè)好的特征子集應(yīng)該與響應(yīng)變量高度相關(guān)而與其它特征不相關(guān).首先,定義評(píng)估函數(shù)如下:

(1)

利用式(1)作為評(píng)價(jià)函數(shù),CFS采用早停準(zhǔn)則搜索特征空間[13],最終選擇的特征子集Fk為

(2)

2 基于MIC改進(jìn)的CFS算法:MICCFS

2.1 最大信息系數(shù)

最大信息系數(shù)(MIC)是基于互信息來計(jì)算變量間相關(guān)程度,具體計(jì)算過程如下.

設(shè)有隨機(jī)變量X和Y,對(duì)于由其樣本{(xi,yi),i=1,2,…,N}組成的有序?qū)螪,在二維平面上分別沿x軸方向分割成a段,沿y軸方向分割成b段,得到a×b的網(wǎng)格G,令D|G表示集合D中的點(diǎn)落在網(wǎng)格G上的概率分布,并記I(D|G,a,b)為該分隔情形下對(duì)應(yīng)的X和Y互信息估計(jì)值.對(duì)于不同的劃分網(wǎng)格G,可以估計(jì)出不同的互信息I(D|G,a,b)值,記I*(D,a,b)為所有不同劃分G下的互信息最大值,即:

(3)

則最大信息系數(shù)計(jì)算公式為

(4)

其中,N為樣本數(shù),B(N)是樣本的函數(shù),表示網(wǎng)格總的小單元數(shù)a×b滿足小于B(N),根據(jù)文獻(xiàn)[16],一般取B(N)=N0.6.Reshef等[16]證明了MIC值范圍為[0,1],當(dāng)兩變量間的MIC值越大,相關(guān)性越強(qiáng),反之MIC值越小,則兩變量相關(guān)性越小.且MIC具有很強(qiáng)的泛化能力,適用變量間任意形式的函數(shù),同時(shí)還具有公平性,即對(duì)不同形式的函數(shù)在相同水平噪聲下都能得到同樣的結(jié)果.

鑒于MIC以上優(yōu)良的性質(zhì),本文利用MIC來度量特征與特征間的關(guān)系以及特征與類別間的關(guān)系,從而既能度量離散變量間相關(guān)性,也能度量連續(xù)變量間相關(guān)性,以此對(duì)CFS算法中的變量間關(guān)系度量方式進(jìn)行改進(jìn).

2.2 MICCFS算法

(5)

依據(jù)式(5)進(jìn)行搜索特征子集,算法MICCFS簡(jiǎn)單描述如下.

輸入:D={F1,F2,…,Fp,C}//含有p個(gè)特征,一個(gè)響應(yīng)變量的數(shù)據(jù)集

輸出:Fsub//最終得到的特征子集

步驟一:初始化最終特征子集Fsub為空集.

步驟二:計(jì)算每個(gè)特征與類別間的最大信息系數(shù)MIC(Fi,C)(i=1,2,…,p),每?jī)蓚€(gè)特征之間的最大信息系數(shù)MIC(Fi,Fj)(i,j=1,2,…,p).

步驟三:重復(fù)以下步驟,直至遍歷完所有特征或者滿足CFS早停準(zhǔn)則時(shí)停止搜索,

步驟四:返回最終特征子集Fsub.

此算法由兩部分組成:

①計(jì)算特征與類別間以及特征與特征間的最大信息系數(shù);

2.3 時(shí)間復(fù)雜度比較

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

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

本文實(shí)驗(yàn)中回歸和分類數(shù)據(jù)集均來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)倉(cāng)庫(kù),如表1、表2所示,其中回歸數(shù)據(jù)集中Friedman.1.data是R語(yǔ)言tgp包中的數(shù)據(jù).實(shí)驗(yàn)軟件為Python 3.7、R 3.5.2語(yǔ)言編程,系統(tǒng)運(yùn)行環(huán)境為:Intel(R) Core(TM) i5-3337U 處理器、1.8 GHz CPU, 8GB RAM, Win10 操作系統(tǒng).

表1 回歸數(shù)據(jù)集描述

表2 分類數(shù)據(jù)集描述

數(shù)據(jù)預(yù)處理:在計(jì)算變量間的MIC時(shí),將字符型變量進(jìn)行編碼轉(zhuǎn)化為數(shù)值型,再進(jìn)行計(jì)算,同時(shí),對(duì)于字符型變量,進(jìn)行One-Hot編碼處理,數(shù)據(jù)進(jìn)入模型前進(jìn)行標(biāo)準(zhǔn)化處理;連續(xù)型變量的缺失值用均值代替,離散型變量缺失值用眾數(shù)代替;將預(yù)處理后的數(shù)據(jù)作為初始實(shí)驗(yàn)數(shù)據(jù)集.

3.2 分類器參數(shù)設(shè)置

實(shí)驗(yàn)采用最常見的四種分類器,支持向量機(jī)(SVM)[21]、決策樹(DT)[22]、樸素貝葉斯(NB)[23]、k近鄰(KNN)[24],這些都是比較常用并且廣泛應(yīng)用于各種領(lǐng)域的分類器,超參數(shù)設(shè)置如下.

k近鄰分類器在計(jì)算樣本距離時(shí),為了消除數(shù)據(jù)尺度不同對(duì)結(jié)果的影響,計(jì)算前需要對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理,同時(shí)為簡(jiǎn)便起見,本文中k統(tǒng)一取3.

決策樹采用CART決策樹,采用Python中第三方庫(kù)sklearn,回歸時(shí)的函數(shù)參數(shù)設(shè)置:criterion=′mse′, splitter=′best′;分類時(shí)函數(shù)參數(shù):criterion=′gini′, splitter=′best′,max＿depth=5, min＿samples＿split=20,其余參數(shù)均采用默認(rèn)設(shè)置.

高斯樸素貝葉斯分類器,后驗(yàn)分布參數(shù)

不需要調(diào)節(jié),即假設(shè)特征的條件概率分布滿足高斯分布.

3.3 評(píng)價(jià)比較準(zhǔn)則

對(duì)于回歸任務(wù),比較最終選取的特征數(shù)量p和均方根誤差

其中,N是樣本數(shù),ypred是預(yù)測(cè)值,ytrue是真實(shí)值,并記SVM、3NN、DT三種模型下得到的最小均方根誤差為mRMSE.由于希望得到較少的特征數(shù)量和較小的均方根誤差,因此對(duì)于特征數(shù)量和均方誤差給出一個(gè)綜合指標(biāo)REI:

其中,fRS是回歸任務(wù)選擇出的特征數(shù)量,fRA是數(shù)據(jù)集原有特征數(shù)量,REI越小越好.

類似的,對(duì)于分類任務(wù),對(duì)比選擇出的特征數(shù)量p和分類準(zhǔn)確度Acc,記SVM、3NN、DT、NB四種模型下得到的最大分類精度為mAcc.由于希望得到較少的特征數(shù)量和較大的分類準(zhǔn)確度,對(duì)于衡量模型復(fù)雜度和精度給出一個(gè)綜合指標(biāo)CEI:

其中,fCS是分類任務(wù)選擇出的特征數(shù)量,CEI越大越好.所有分類數(shù)據(jù)的精度采用10次5折交叉驗(yàn)證.

綜上,對(duì)于回歸問題,重點(diǎn)比較選取的特征數(shù)量、RMSE、mRMSE和REI;而對(duì)于分類問題,比較特征數(shù)量,分類精度,最大分類精度mAcc和CEI.

3.4 結(jié)果與討論

3.4.1 回歸結(jié)果 得到的回歸結(jié)果均方根誤差和選擇出的特征數(shù)量如表3所示,表中字體加粗表示MICCFS的RMSE小于CFS的RMSE.

表3 回歸結(jié)果下的特征數(shù)量和均方根誤差

從表3可看到,首先對(duì)于選擇的特征,MICCFS算法在CH、CCS、diab、Fried這4個(gè)數(shù)據(jù)集上選擇出的特征數(shù)量小于或等于CFS算法,其余的數(shù)據(jù)集上CFS算法選擇出來的特征數(shù)量均小于MICCFS選擇出的特征數(shù)量,在11個(gè)數(shù)據(jù)集上,CFS最大的特征減少度為92.30%(數(shù)據(jù)集Bos),MICCFS最大的特征減少度為76.92%(數(shù)據(jù)集Bos),CFS特征數(shù)量上比MICCFS少,兩者都對(duì)原始數(shù)據(jù)中特征進(jìn)行了篩選,簡(jiǎn)化了數(shù)據(jù)結(jié)構(gòu);然后對(duì)于預(yù)測(cè)均方根誤差,MICCFS在11個(gè)數(shù)據(jù)集上在3種分類器上分別有7、8、6個(gè)數(shù)據(jù)集的RMSE比CFS小,最大的差距為10.18(CH數(shù)據(jù)集,3NN分類器),其余數(shù)據(jù)集上,CFS比MICCFS的RMSE小,最大差距僅為2.15(CCS數(shù)據(jù)集,3NN分類器),在均方根誤差上MICCFS比CFS較優(yōu);取不同的數(shù)據(jù)集在三種模型下的最小均方根誤差,如圖1所示．

圖1 不同數(shù)據(jù)集在三種情況下的mRMSE

從圖1看到,總體11個(gè)數(shù)據(jù)集,MICCFS算法在7個(gè)數(shù)據(jù)集上的mRMSE比CFS算法小,但原始特征下的得到的分別有6個(gè)數(shù)據(jù)集的mRMSE比CFS算法得到的mRMSE小,原始特征下有8個(gè)數(shù)據(jù)集的mRMSE比MICCFS算法得到的mRMSE小,其中最大差距為20.08(FF數(shù)據(jù)集),最小的差距僅為0.02(Fried數(shù)據(jù)集).

綜合考慮特征數(shù)量和最小均方根誤差,本文運(yùn)用綜合指標(biāo)REI(見定義2)來進(jìn)行比較,結(jié)果見圖2,圖中no＿REI、CFS＿REI、MICCFS＿REI分別表示原特征、CFS算法、MICCFS算法下的REI值.

從圖2可看到,11個(gè)數(shù)據(jù)集中,MICCFS算法有6個(gè)數(shù)據(jù)集比原特征下的REI小,同時(shí)MICCFS算法有6個(gè)數(shù)據(jù)集上的REI比CFS算法下的REI小.總體來說,MICCFS算法較CFS更優(yōu).

3.4.2 分類結(jié)果 分類結(jié)果如表4、表5所示,表中粗字體表示MICCFS的分類精度比CFS高.

表4 SVM和NN下的分類精度結(jié)果

表5 DT和NB下的分類精度結(jié)果

從表4、表5可看到,在4種分類器、11個(gè)數(shù)據(jù)集下,MICCFS算法得到的特征數(shù)量均小于或等于CFS算法得到的特征數(shù)量,其中MICCFS的最小特征減少度為61.76%(Derm數(shù)據(jù)集),CFS的最小特征減少度為38.46%(Wine數(shù)據(jù)集);兩者最大的特征減少度均有99%(HV數(shù)據(jù)集),特征數(shù)量上MICCFS比CFS少,兩者均篩選出了特征子集,去除了冗余信息.同時(shí)11個(gè)數(shù)據(jù)集中MICCFS在4種分類器下分別有3、4、7、3個(gè)數(shù)據(jù)集的分類精度比CFS高,最大差距為7.38個(gè)百分點(diǎn)(Con數(shù)據(jù)集,NB分類器),其余數(shù)據(jù)集上CFS得到的分類精度高于MICCFS得到的分類精度,最大差距為30.38個(gè)百分點(diǎn).同樣,取出不同分類器下的最大分類精度如圖3所示．

從圖3可看到,MICCFS算法在4個(gè)數(shù)據(jù)集上的mAcc比CFS大,最大差距為11.2個(gè)百分點(diǎn)(Aaw數(shù)據(jù)集),其余數(shù)據(jù)集上的CFS算法得到的mAcc比MICCFS大,最大差距為6.09個(gè)百分點(diǎn)(LM數(shù)據(jù)集).同時(shí)原始特征下得到的6個(gè)數(shù)據(jù)集的mAcc比CFS算法得到的mAcc大,原始特征下有7個(gè)數(shù)據(jù)集的mAcc比MICCFS算法得到的mAcc大,最大差距為7.10個(gè)百分點(diǎn)(LM數(shù)據(jù)集),最小差距為0.11個(gè)百分點(diǎn)(Derm數(shù)據(jù)集).與回歸中類似,綜合考慮特征數(shù)量和最大分類精度,運(yùn)用綜合指標(biāo)CEI(見定義4)來進(jìn)行比較,結(jié)果見圖4,圖中no＿CEI、CFS＿CEI、MICCFS＿CEI分別表示原特征、CFS算法、MICCFS算法下的CEI值.

從圖4可看到,10個(gè)數(shù)據(jù)集中,MICCFS算法下所有數(shù)據(jù)集的CEI均比CFS算法下的CEI大,總體來看,可得到MICCFS較CFS更優(yōu)的結(jié)論.

此外,本文還將MICCFS算法與其他常用特征選擇算法SVMRFE、Lasso、MIM、Relief F、Chi-Square,使用表2中數(shù)據(jù)進(jìn)行了對(duì)比,其中 SVMRFE 屬于封裝式的常用的方法;Lasso 是嵌入式的,是統(tǒng)計(jì)學(xué)中變量選擇被使用較多且經(jīng)典的變量壓縮算法,其余的是過濾式的,也是常用且流行被使用在各個(gè)領(lǐng)域的方法.CFS和MICCFS算法均是基于特征子集的算法,將MICCFS和基于特征子集的算法Lasso(超參數(shù)alpha=0.3,其余參數(shù)采用Python默認(rèn)設(shè)置)比較,比較選擇的特征數(shù)量、mAcc和CEI;以及基于排序式的特征選擇算法Relief F、 SVMRFE、Chi-Square、MIM,選擇和MICCFS相同數(shù)量的特征時(shí)來比較mAcc,與前面計(jì)算方式類似,在4種分類器下,得到這些算法的結(jié)果如表6,表中加粗字體表示MICCFS的mAcc比其他算法大或者CEI比Lasso算法高.

表6 六種不同方法下的特征、mAcc、CEI結(jié)果

從表6可看到,MICCFS和5種基于權(quán)重排序的特征選擇算法中,10個(gè)數(shù)據(jù)集中有5個(gè)數(shù)據(jù)集MICCFS算法的mAcc均優(yōu)于其他算法,其他算法分別只有1～2個(gè)數(shù)據(jù)集是最優(yōu)的,同時(shí),MICCFS和Lasso對(duì)比,10個(gè)數(shù)據(jù)集中9個(gè)數(shù)據(jù)集的MICCFS選擇出的特征小于或等于Lasso選擇出的特征; 6個(gè)數(shù)據(jù)集的最大分類精度mAcc比Lasso高,最大差距為16.39個(gè)百分點(diǎn)(數(shù)據(jù)集Derm),其余4個(gè)數(shù)據(jù)集Lasso的mAcc比MICCFS高,最大差距僅為5.21個(gè)百分點(diǎn)(數(shù)據(jù)集LM);同時(shí),對(duì)于CEI指標(biāo),有9個(gè)數(shù)據(jù)集的CEI均比Lasso高,綜合數(shù)據(jù)來看,MICCFS較其他常用特征選擇算法有優(yōu)勢(shì).

4 結(jié)論

本文基于最大信息系數(shù)(MIC)對(duì)關(guān)聯(lián)性的特征選擇算法(CFS)進(jìn)行了改進(jìn),提出MICCFS算法,它運(yùn)用MIC衡量變量間的復(fù)雜關(guān)系,統(tǒng)一回歸時(shí)和分類時(shí)變量關(guān)系衡量方式,再依據(jù)評(píng)估函數(shù)來選擇特征子集,是一種更有效的特征選擇方法.對(duì)于CFS算法中的回歸任務(wù)和分類任務(wù),首先,將回歸任務(wù)中衡量變量間關(guān)系的線性相關(guān)系數(shù)替換為MIC系數(shù),使其能衡量的關(guān)系更為復(fù)雜,3種模型在UCI中11個(gè)回歸數(shù)據(jù)集上進(jìn)行驗(yàn)證,比較其特征選擇數(shù)量、mRMSE和綜合指標(biāo)REI,綜合比較,結(jié)果表明MICCFS較CFS有優(yōu)勢(shì);然后將分類任務(wù)中衡量變量間的關(guān)系的對(duì)稱不確定性度量替換為MIC系數(shù),4種模型在UCI中10個(gè)分類數(shù)據(jù)集上進(jìn)行驗(yàn)證,比較其特征數(shù)量、mAcc和CEI,綜合比較,MICCFS較CFS更優(yōu).最后將MICCFS和其它常用特征選擇算法進(jìn)行比較,結(jié)果表明MICCFS也具有一定優(yōu)勢(shì).