參數(shù)自動優(yōu)化的特征選擇融合算法①

吳 俊,柯飂挺,任 佳

(浙江理工大學 機械與自動控制學院,杭州 310018)

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

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

綜上,本文基于過濾式模型和封裝式模型各自的特點,將這兩種模型結(jié)合,構(gòu)建一種基于最大互信息系數(shù)和皮爾遜相關(guān)系數(shù)的、使用遺傳算法進行超參數(shù)自動優(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ù)的過濾式模型和以分類準確率為目標的封裝式模型來克服過濾式模型準確率較低,傳統(tǒng)相關(guān)系數(shù)處理非線性關(guān)系能力較弱以及封裝式模型的時間成本過高的問題.第一階段根據(jù)最大互信息系數(shù)獲取各特征和標簽之間的相關(guān)度評分,該評分綜合考慮線性和非線性相關(guān)度,再設置相關(guān)度閾值以剔除不相關(guān)特征.第二階段,通過皮爾遜相關(guān)系數(shù)獲取特征子集特征之間的線性冗余度評分,同樣設置冗余度閾值來刪除冗余特征.最后,將特征子集的分類準確率作為評價標準,使用遺傳算法自動優(yōu)化前兩步中的超參數(shù),達到綜合減少特征數(shù)目和維持甚至提高特征子集分類精度的效果,并自動獲取最優(yōu)特征子集.

1 基礎理論

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

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

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

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

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

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

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

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

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

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

1.3 遺傳算法

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

2 MICP-GA 基礎理論

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

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

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

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

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

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

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

圖1 整體算法流程圖

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

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

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

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

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

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

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

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

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

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

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

3 實驗分析

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

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

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

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

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

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

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

4 結(jié)論與展望

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