吳 俊,柯飂挺,任 佳

(浙江理工大學(xué) 機(jī)械與自動(dòng)控制學(xué)院,杭州 310018)

隨著現(xiàn)代科技的飛速發(fā)展,大量數(shù)據(jù)從各個(gè)領(lǐng)域中呈爆炸式不斷產(chǎn)出.同時(shí)因?yàn)檫@些數(shù)據(jù)中含有大量不相關(guān)、冗余信息,在進(jìn)行數(shù)據(jù)挖掘時(shí),預(yù)處理技術(shù)中的特征選擇便變得極為重要和極具挑戰(zhàn)性[1].

目前特征選擇已經(jīng)在文本分類[2]、模式識(shí)別[3-5]、癌癥分類[6]和故障診斷[7]等領(lǐng)域內(nèi)成功應(yīng)用.特征選擇可定義為從數(shù)據(jù)集中去除不相關(guān)和冗余的特征,從而增強(qiáng)后續(xù)學(xué)習(xí)算法性能的過程[8].特征選擇方法可根據(jù)兩個(gè)標(biāo)準(zhǔn)來分類:搜索策略和評(píng)估標(biāo)準(zhǔn)[8].特征子集可以通過兩種模型獲取:過濾式[9]模型和封裝式[10]模型.過濾式模型在搜索過程中僅考慮數(shù)據(jù)集本身,而封裝式模型需在搜索過程中結(jié)合學(xué)習(xí)算法.因此過濾式模型花費(fèi)時(shí)間成本較小,但準(zhǔn)確率不穩(wěn)定.反觀封裝式模型,由于需要結(jié)合學(xué)習(xí)算法,所以準(zhǔn)確率相對(duì)更高,同時(shí)也更耗時(shí).此外搜索最優(yōu)子集的方式也是特征選擇中的一個(gè)關(guān)鍵問題,具體可分為遍歷、隨機(jī)搜索和啟發(fā)式搜索.其中遍歷雖然一定可以獲取最優(yōu)子集但是不適用于大型數(shù)據(jù)集[11].隨機(jī)搜索則因?yàn)闆]有數(shù)學(xué)理論引導(dǎo)搜索方向?qū)е滤阉餍阅懿环€(wěn)定[12].而啟發(fā)式算法使用啟發(fā)式信息指導(dǎo)搜索.雖然不能保證找到最優(yōu)解,但可以再合理的時(shí)間內(nèi)獲取可接受的解[13].近年已經(jīng)有許多研究對(duì)不同特征選擇算法進(jìn)行了對(duì)比,如在文獻(xiàn)[14]中,使用了3種不同的分類器評(píng)估了8種標(biāo)準(zhǔn)的特征選擇方法.文獻(xiàn)[10]使用了K 最近鄰算法作為分類器,系統(tǒng)地研究了鯨魚優(yōu)化算法(Whale Optimization Algorithm,WOA)并將基于WOA的封裝式特征選擇算法和三種標(biāo)準(zhǔn)的啟發(fā)式特征選擇算法進(jìn)行比較證明了WOA的強(qiáng)大性能.文獻(xiàn)[15]中將融合啟發(fā)式算法和3種標(biāo)準(zhǔn)的封裝式特征選擇算法進(jìn)行了對(duì)比以證明融合啟發(fā)式算法的潛力.

綜上,本文基于過濾式模型和封裝式模型各自的特點(diǎn),將這兩種模型結(jié)合,構(gòu)建一種基于最大互信息系數(shù)和皮爾遜相關(guān)系數(shù)的、使用遺傳算法進(jìn)行超參數(shù)自動(dòng)優(yōu)化的兩階段特征選擇融合算法(A feature selection fusion method based on Maximal Information Coefficient and Pearson correlation coefficient with parameters automatic optimized by Genetic Algorithms,MICP-GA),通過結(jié)合使用最大互信息系數(shù)、皮爾遜相關(guān)系數(shù)的過濾式模型和以分類準(zhǔn)確率為目標(biāo)的封裝式模型來克服過濾式模型準(zhǔn)確率較低,傳統(tǒng)相關(guān)系數(shù)處理非線性關(guān)系能力較弱以及封裝式模型的時(shí)間成本過高的問題.第一階段根據(jù)最大互信息系數(shù)獲取各特征和標(biāo)簽之間的相關(guān)度評(píng)分,該評(píng)分綜合考慮線性和非線性相關(guān)度,再設(shè)置相關(guān)度閾值以剔除不相關(guān)特征.第二階段,通過皮爾遜相關(guān)系數(shù)獲取特征子集特征之間的線性冗余度評(píng)分,同樣設(shè)置冗余度閾值來刪除冗余特征.最后,將特征子集的分類準(zhǔn)確率作為評(píng)價(jià)標(biāo)準(zhǔn),使用遺傳算法自動(dòng)優(yōu)化前兩步中的超參數(shù),達(dá)到綜合減少特征數(shù)目和維持甚至提高特征子集分類精度的效果,并自動(dòng)獲取最優(yōu)特征子集.

1 基礎(chǔ)理論

1.1 信息熵與最大互信息系數(shù)

定義1.信息熵[16]克服了對(duì)信息隨機(jī)變量不確定性的度量,設(shè)X為離散隨機(jī)變量,那么X的信息熵H(X)為:

定義2.條件熵表示為當(dāng)隨機(jī)變量Y單獨(dú)發(fā)生時(shí),隨機(jī)變量X發(fā)生的條件概率分布,可通過式(2)表示:

定義3.互信息用于檢測(cè)兩隨機(jī)變量中所含的信息量和互相關(guān)聯(lián)程度.互信息可通過式(1)和式(2)用熵表示:

最后依據(jù)式(2)和式(3)可得:

Reshef 等人[17]提出的最大互信息系數(shù)(Maximal Information Coefficient,MIC)無需對(duì)數(shù)據(jù)分布進(jìn)行任何假設(shè)便可評(píng)估變量間的函數(shù)關(guān)系和統(tǒng)計(jì)關(guān)系.該算法具有普適性和均勻性兩大特點(diǎn),普適性指當(dāng)數(shù)據(jù)規(guī)模足夠大時(shí),MIC算法能有效捕捉到大規(guī)模有意義的關(guān)系,而并不會(huì)僅局限于某種函數(shù)關(guān)系;均勻性則指對(duì)于不同類型函數(shù)關(guān)系,當(dāng)給予相同噪聲時(shí),MIC算法給出相同或相近的結(jié)果變化.最大互信息系數(shù)Imax(X;Y)可通過互信息和熵計(jì)算得出:

1.2 皮爾遜相關(guān)系數(shù)

皮爾遜相關(guān)系數(shù)(Pearson Correlation Coefficient,PCCs)由Karl Person 提出,因其計(jì)算簡(jiǎn)單、運(yùn)算速度快而被廣泛用于度量在數(shù)據(jù)預(yù)測(cè)、故障診斷和參數(shù)估計(jì)等領(lǐng)域中兩變量間的線性相關(guān)程度,其取值范圍是[?1,1].兩變量間相關(guān)系數(shù)的絕對(duì)值越大,表明兩者的相關(guān)度越高,當(dāng)取值為0時(shí)表示兩個(gè)變量不相關(guān).具體相關(guān)系數(shù)數(shù)值大小和相關(guān)判斷結(jié)果的對(duì)應(yīng)關(guān)系見表1.

通常皮爾遜相關(guān)系數(shù)用希臘字母ρ表示.其具體定義為兩個(gè)變量之間的協(xié)方差和標(biāo)準(zhǔn)差的商,其中cov表示協(xié)方差,E為數(shù)學(xué)期望:

表1 相關(guān)性判斷準(zhǔn)則

1.3 遺傳算法

遺傳算法的靈感來自生物的遺傳過程,該算法的解被稱為染色體或個(gè)體.二進(jìn)制遺傳算法的每個(gè)染色體包含二進(jìn)制值為0或1的基因,這些基因決定了每個(gè)個(gè)體的屬性.一系列的染色體組成了一個(gè)種群.每個(gè)染色體的性能通過適應(yīng)度函數(shù)來評(píng)估,適應(yīng)度值較高的染色體被選作父代,并通過交叉步驟結(jié)合產(chǎn)生新的后代.再對(duì)新的種群進(jìn)行變異處理來增加個(gè)體的隨機(jī)性,降低陷入局部最優(yōu)的可能[18].

2 MICP-GA 基礎(chǔ)理論

MICP-GA算法兼顧過濾式和封裝式特征選擇算法的優(yōu)點(diǎn),同時(shí)利用遺傳算法對(duì)前述步驟中的超參數(shù)進(jìn)行自動(dòng)優(yōu)化來獲取最優(yōu)特征子集.該算法的實(shí)現(xiàn)流程如圖1所示.

2.1 運(yùn)用最大互信息系數(shù)獲取各特征和標(biāo)簽的相關(guān)度

本階段利用最大互信息系數(shù)進(jìn)行初次特征選擇.第一階段特征選擇的具體步驟如算法1所示.

該方法使用最大互信息系數(shù)準(zhǔn)確找出和類別線性相關(guān)、非線性相關(guān)的特征,剔除不相關(guān)的特征,但篩選出的特征之間仍可能存在線性冗余.為解決該問題,繼續(xù)進(jìn)行第二步特征選擇.

2.2 基于皮爾遜相關(guān)系數(shù)的特征去冗余

對(duì)第一步選取的特征子集D2,使用皮爾遜相關(guān)系數(shù),減少特征之間的冗余性,同時(shí)也減少了D2的特征數(shù)量,幫助后續(xù)學(xué)習(xí)算法更快地獲取結(jié)果.第二階段特征選擇的步驟如算法2所示.

由前述可知,第一階段中的超參數(shù)a和第二階段中的閾值b這兩個(gè)參數(shù)值對(duì)分類結(jié)果有著重要的影響.接下來,以UCI標(biāo)準(zhǔn)數(shù)據(jù)集中的Vehicle數(shù)據(jù)集為例進(jìn)行說明:該數(shù)據(jù)集初始特征共計(jì)18 維,如在第一階段特征選擇時(shí)設(shè)定a為18,則保留全部特征.現(xiàn)對(duì)所選的Vehicle、Ionosphere、Wine和Sonar數(shù)據(jù)集中的特征的皮爾遜相關(guān)系數(shù)進(jìn)行可視化處理,如圖2～圖5所示.熱力圖中,兩兩特征之間的皮爾遜相關(guān)系數(shù)的取值范圍是[0,1],對(duì)應(yīng)著圖中不同的顏色.此外,由于熱力圖沿著正對(duì)角線(如圖2～圖5中從左上貫穿至右下的藍(lán)線所示)對(duì)稱,所以僅觀察熱力圖的左下部分即可.由圖可知,其中若干區(qū)域(如圖2～圖5中藍(lán)色圈注所示)中特征之間的皮爾遜相關(guān)系數(shù)較大,說明該區(qū)域內(nèi)的特征之間存在線性冗余.可采用基于皮爾遜相關(guān)系數(shù)的特征選擇算法有效解決該問題.

圖1 整體算法流程圖

算法1.基于最大互信息系數(shù)的特征選擇算法輸入:數(shù)據(jù)集D1.步驟1.設(shè)定超參數(shù)a.Imax(x(i);y)步驟2.根據(jù)式(5)計(jì)算每個(gè)特征x(i)與類別y 的最大互信息系數(shù).{x(1),x(2),···,x(N)}步驟3.將特征按照最大互信息系數(shù)的大小,從大到小排列,獲取排序后的特征集.D2={x(1),x(2),···,x(a)}步驟4.從排序后的特征集中選擇前a 個(gè)特征,構(gòu)成特征子集.輸出:特征子集D2.

算法2.基于皮爾遜相關(guān)系數(shù)的特征選擇算法輸入:特征子集D2.步驟1.設(shè)定皮爾遜相關(guān)系數(shù)冗余閾值b.步驟2.根據(jù)式(6)計(jì)算D2 中所有特征之間的皮爾遜相關(guān)系數(shù).步驟3.將皮爾遜相關(guān)系數(shù)大于閾值b 的兩個(gè)特征中最大互信息值較小的特征刪除.步驟4.反復(fù)執(zhí)行步驟3 直至特征子集中所有特征的皮爾遜相關(guān)系數(shù)值都大于b,該特征子集記作D3.輸出:最終特征子集D3.

圖2 Vehicle數(shù)據(jù)的皮爾遜相關(guān)系數(shù)熱點(diǎn)圖

圖3 Ionosphere數(shù)據(jù)的皮爾遜相關(guān)系數(shù)熱點(diǎn)圖

圖4 Sonar數(shù)據(jù)的皮爾遜相關(guān)系數(shù)熱點(diǎn)圖

圖5 Wine數(shù)據(jù)的皮爾遜相關(guān)系數(shù)熱點(diǎn)圖

2.3 使用遺傳算法實(shí)現(xiàn)超參數(shù)的自動(dòng)優(yōu)化

本文采用遺傳算法自動(dòng)優(yōu)化3.1和3.2節(jié)中的超參數(shù)a和b.遺傳算法優(yōu)化超參數(shù)的步驟描述如算法3所示.

此外染色體個(gè)數(shù)NIND設(shè)為5.最大迭代次數(shù)MAXGEN設(shè)為20.子代和父代個(gè)體不相同的概率GGAP設(shè)為0.9.遺傳算法選擇方式SELECTSTYLE選用輪盤賭選擇法rws.基因變異的概率PM由源代碼中的0.1 修改為由式(7)獲取,令PM隨著迭代次數(shù)t的增加而不斷減小,使得算法在搜索前期擴(kuò)大搜索空間,不容易陷入局部最優(yōu)解,而且在搜索后期也不會(huì)因?yàn)镻M過大導(dǎo)致子集狀態(tài)有較大突變.

綜上所述,本文提出的遺傳算法可對(duì)前兩步驟中的待優(yōu)化超參數(shù)a、b自動(dòng)進(jìn)行優(yōu)化,并以適應(yīng)度函數(shù)Fitness作為目標(biāo)函數(shù),將Fitness取得最小值時(shí)對(duì)應(yīng)的a、b作為最優(yōu)參數(shù).

算法3.使用遺傳算法實(shí)現(xiàn)超參數(shù)的自動(dòng)優(yōu)化步驟1.初始化染色體個(gè)數(shù)NIND和各個(gè)染色體中的超參數(shù)a和b.fitness=AR+BMN步驟2.根據(jù)超參數(shù)a、b 結(jié)合階段一、二的步驟獲取各個(gè)染色體對(duì)應(yīng)的特征子集,通過適應(yīng)度函數(shù)計(jì)算各個(gè)染色體的適應(yīng)度值fitness,并記錄本輪獲取的最小適應(yīng)度值fitness*和對(duì)應(yīng)的參數(shù)a*、b*(其中R表示給定分類器的平均錯(cuò)誤率,M表示所選子集中特征的個(gè)數(shù),N表示初始數(shù)據(jù)集中所有特征的個(gè)數(shù),其中A和B分別是來自文獻(xiàn)[18]與分類準(zhǔn)確率和子集長(zhǎng)度對(duì)應(yīng)的兩個(gè)參數(shù),A∈[1,0],B∈[0,1-A]).步驟3.設(shè)定迭代次數(shù)t的初值和最大迭代次數(shù)MAXGEN.t=t+1 fitnessbest= fitness?步驟4.使用遺傳算法更新超參數(shù)a和b,迭代次數(shù),重復(fù)步驟2,若本輪最優(yōu)適應(yīng)度值fitness*小于歷史最優(yōu)適應(yīng)度值.fitnessbest,則,并覆蓋對(duì)應(yīng)的超參數(shù)a*和b*,其中超參數(shù)a∈[2,N],b∈[Min(PCCs),Max(PCCs)],Min(PCCs)和Max(PCCs)分別表示各個(gè)子集的特征之間的皮爾遜相關(guān)系數(shù)的最小值和最大值.其中a的閾值設(shè)置為[2,N]是為了確保搜索算法的搜索空間完整,最小值取2 而不是取1 則是考慮到代碼參數(shù)個(gè)數(shù)需求.步驟5.若迭代次數(shù)t 等于最大迭代次數(shù)MAXGEN,終止迭代并輸出歷史最優(yōu)適應(yīng)度值fitnessbest和對(duì)應(yīng)超參數(shù)a、b.

3 實(shí)驗(yàn)分析

為檢測(cè)上文提出的MICP-GA算法的可靠性,本文選取了5個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集.表2和表3分別列出了這些測(cè)試數(shù)據(jù)集的具體信息以及直接將各數(shù)據(jù)集初始數(shù)據(jù)用于不同分類器時(shí)的分類準(zhǔn)確率.

表2 測(cè)試數(shù)據(jù)集

在測(cè)試中,使用Python3進(jìn)行編程,并且使用常規(guī)的十折交叉驗(yàn)證用于檢驗(yàn).接下來使用3種特征選擇方法對(duì)上述數(shù)據(jù)集進(jìn)行測(cè)試和比較,3種方法分別是MICP-GA、單獨(dú)用MIC特征選擇以及單獨(dú)使用皮爾遜相關(guān)系數(shù)特征選擇.在測(cè)試過程中,將3種特征選擇方法與三種典型分類器,K 最近鄰分類器(K-Nearest Neighbors,KNN)、隨機(jī)森林分類器(Random Forest,RF)和支持向量機(jī)(Support Vector Machine,SVM)結(jié)合后,對(duì)上述數(shù)據(jù)集進(jìn)行測(cè)試.結(jié)果顯示平均最高準(zhǔn)確率如表4所示,平均特征選取率如表5所示,平均適應(yīng)度函數(shù)如表6所示.對(duì)比表3和表4的分類準(zhǔn)確率,可見本文提出的算法對(duì)原始數(shù)據(jù)的分類準(zhǔn)確率有明顯提升,說明MICP-GA在搜索最優(yōu)特征選擇的組合時(shí)能夠有效跳出局部最優(yōu),確保搜索到的解是近似全局最優(yōu)解,同時(shí)說明MICP-GA 充分考慮特征和類別之間的包括線性和非線性的關(guān)系,解決了傳統(tǒng)相關(guān)系數(shù)處理非線性關(guān)系表現(xiàn)不好的問題,并根據(jù)MIC 評(píng)分來判斷刪除每對(duì)冗余特征中的哪一個(gè),較好地結(jié)合了運(yùn)用MIC和PCCs的特征選擇從而使得分類效果比單獨(dú)使用MIC或PCCs時(shí)更優(yōu).同時(shí),結(jié)合表5中基于不同特征選擇方法的分類器的平均特征選取率,也表明了該算法在降低數(shù)據(jù)維度方面有較優(yōu)的表現(xiàn),能夠有效剔除和類別不相關(guān)的特征以及冗余特征,為后續(xù)學(xué)習(xí)算法節(jié)省大量的運(yùn)算成本,提升了運(yùn)行效率.綜上所述,本文提出的算法充分考慮了特征和類別之間的線性相關(guān)性以及特征之間的冗余性,能夠有效對(duì)數(shù)據(jù)進(jìn)行降維同時(shí)保證數(shù)據(jù)集的分類準(zhǔn)確率保持不變甚至提升分類準(zhǔn)確率.

表3 基于不同分類器的初始數(shù)據(jù)集的平均分類準(zhǔn)確率

表4 基于不同特征選擇方法的分類器的平均最高準(zhǔn)確率

表5 基于不同特征選擇方法的分類器的平均特征選取率

表6 基于不同特征選擇方法的分類器的平均適應(yīng)度值

4 結(jié)論與展望

特征選擇算法的優(yōu)劣對(duì)模型的預(yù)測(cè)準(zhǔn)確率有著重要影響,Filter可以快速高效地去除冗余特征及不相關(guān)特征,但是無法保證獲取的特征子集準(zhǔn)確率達(dá)標(biāo).Wrapper 更傾向于獲取準(zhǔn)確率更高的特征子集,所以其時(shí)間成本一般遠(yuǎn)高于前者.本文針對(duì)以上兩種方法的特點(diǎn),將其進(jìn)行結(jié)合提出了MICP-GA方法,所提算法兼顧了兩者的優(yōu)點(diǎn)并且在UCI標(biāo)準(zhǔn)數(shù)據(jù)集中也有較好的表現(xiàn).但是因?yàn)榻Y(jié)合了遺傳算法以及最大互信息系數(shù),導(dǎo)致時(shí)間復(fù)雜度比傳統(tǒng)特征選擇方法更高,根據(jù)文獻(xiàn)[10]可見傳統(tǒng)的全局搜索算法在性能和運(yùn)算復(fù)雜度上并沒有較大差別,所以沒有將GA 替換成其他全局搜索算法.而如果使用單解的搜索算法如模擬退火(Simulated Annealing,SA)算法替換GA 確實(shí)可以較快獲取解,但鑒于SA 極其容易陷入局部最優(yōu),因此不考慮用SA 搜索最優(yōu)特征子集.所以如何加快搜索速度是后續(xù)進(jìn)一步的研究課題.