基于量子進化算法的包裝式特征選擇方法①

雷華軍,蔣 強

(樂山師范學(xué)院 電子與材料工程學(xué)院,樂山 614000)

隨著信息技術(shù)的飛速發(fā)展,高維數(shù)據(jù)的監(jiān)督分類問題在生產(chǎn)、生活和科研活動中大量涌現(xiàn).理論上講,增加特征的個數(shù)可以提供更多的分辨能力,但研究表明:數(shù)據(jù)維數(shù)的線性增加將使得問題的假設(shè)空間成指數(shù)增長,特征每增加一維,為確保學(xué)習(xí)算法的性能不變,樣本量亦需成倍增加.另一方面,在樣本量一定的情況下,由于無關(guān)或冗余特征的存在,過多的特征不僅降低學(xué)習(xí)算法的效率,還可能導(dǎo)致過擬合,致使模型的泛化能力下降[1].特征選擇是解決前述問題的有效手段之一,它根據(jù)某種評價標準,從原始特征集中挑選一些最有效的特征以達到降低特征空間維數(shù)的目的,并取得與原始特征集相似甚至更好的分類性能.特征選擇已成功應(yīng)用在文本分類[2]、癌癥識別[3]、設(shè)備故障檢測[4]、貸款風(fēng)險預(yù)測[5]等領(lǐng)域.

縱觀現(xiàn)有特征選擇方法,均包含特征子集生成和子集評價兩個構(gòu)成要素[6].前者采用一定的策略搜索特征空間中的全部或部分子集,常用的方法有窮舉搜索、啟發(fā)式搜索和隨機搜索.后者使用某一標準評價搜索到的子集,依據(jù)該標準是否獨立于后續(xù)的學(xué)習(xí)算法,可將特征選擇方法分為過濾式(filter)、包裝式(wrapper)和嵌入式(embedded)三類.相比過濾式,包裝式選擇的子集通常擁有更優(yōu)的分類性能,因其直接使用特征子集的分類精度作為評價標準[7].

近年來,國內(nèi)外學(xué)者對基于隨機搜索策略的包裝式特征選擇開展了廣泛的研究,大量新穎的群智能優(yōu)化算法被用于特征選擇[8],其中較為典型的方法有粒子群優(yōu)化[9]、蜻蜓算法[10]、灰狼優(yōu)化[11]、鯨魚優(yōu)化[12]、引力搜索算法[13]等.這些方法大多從搜索策略的角度對原算法進行了有益的改進,而有關(guān)子集評價的研究則較少.

量子進化算法(quantum-inspired evolutionary algorithm,QEA)是一種基于量子計算原理的概率進化算法,具有種群規(guī)模小、收斂速度快和全局尋優(yōu)能力強等優(yōu)點[14].目前,僅檢索到一篇與本文主題密切相關(guān)的文獻[15],該文將QEA 作為特征子集的搜索策略,并使用Fisher 比評價其性能,因而它屬于一種過濾式的特征選擇方法.綜上所述,將QEA 與包裝式特征選擇結(jié)合的相關(guān)研究尚處于空白,本文將從子集評價和搜索策略兩個方面開展工作,力圖提出一種具有競爭力的包裝式特征選擇方法.

1 問題描述

為結(jié)構(gòu)完整性,給出特征選擇的形式化描述.假定D={(s1,y1),(s2,y2),···,(sm,ym)}為原始數(shù)據(jù)集,S=(s1,s2,···,sm)T為樣本矩陣,行和列分別代表不同的樣本和特征,Y=(y1,y2,···,ym)T為各樣本對應(yīng)的真實類別.si=(si1,si2,···,sin)是n維特征空間 χ的一個向量,即si∈χ ,χ=span{f1,f2,···,fn},其中fj表示第j個特征,元素sij(1 ≤i≤m,1 ≤j≤n)為樣本si在特征fj上的取值.類別yi∈C,C={c1,c2,···,ck}為類別集合.m、n和k分別為樣本、特征和類別的個數(shù).

基于上述定義,監(jiān)督分類的任務(wù)是:利用給定的學(xué)習(xí)算法從D中學(xué)習(xí)一個分類模型h:χ →C,它對采樣自 χ的新樣本具有良好的泛化能力.然而,并不是所有特征都對分類有貢獻,為提高模型的訓(xùn)練效率和泛化能力,特征選擇從原始特征集F={f1,f2,···,fn}中找出一個子集X,X?F,它使得評價函數(shù)J(X)盡量大,X包含的特征數(shù)盡量少.J(X)量化了X分類性能的好壞,不失一般性,假定J(X)值越大,X越優(yōu).不難看出,分類性能和特征個數(shù)是該問題最重要的兩個優(yōu)化目標.

基于現(xiàn)有研究,歸納出包裝式特征選擇的一般框架如圖1所示.

圖1 包裝式特征選擇的一般框架

由圖1 可以看出,數(shù)據(jù)集被分為訓(xùn)練集和測試集,特征選擇在訓(xùn)練集上進行,測試集不參與該過程.特征選擇結(jié)束,需驗證最優(yōu)子集在測試集上的分類精度.在特征選擇過程中,子集的分類性能通過K 折平均分類精度來衡量,分類器被視為一個封閉的黑盒.

2 量子進化算法

基本量子進化算法包含種群初始化、隨機觀測、種群進化等3 個主要步驟[14,16].它采用量子比特編碼,一個量子比特可表示為:

其中,|0〉和|1〉表示兩個不同的量子態(tài),α 和 β分別表示狀態(tài) |0〉和| 1〉的概率幅.一個量子比特可能處于| 0〉或|1〉兩個基態(tài),或者兩基態(tài)的任意疊加態(tài),|α|2和 |β|2表示該量子比特處于| 0〉和| 1〉的概率大小.

3 特征選擇方法

3.1 種群初始化

3.2 特征子集評價和性能比較

3.3 種群進化策略

3.4 整個算法流程

綜合第3.2 節(jié)和第3.3 節(jié)的改進措施和圖1,得到整個特征選擇方法的流程如圖2所示.

圖2 特征選擇方法的流程

由圖2 可知,實驗中利用分層采樣將數(shù)據(jù)集分為訓(xùn)練集和測試集.在特征選擇過程中,兩種進化策略分別執(zhí)行T/3 和2T/3 代.

4 實驗與結(jié)果分析

4.1 實驗方案

選取UCI[19]中的15 個數(shù)據(jù)集作為實驗數(shù)據(jù),其中大多已被用于驗證各種特征選擇方法,關(guān)于這些數(shù)據(jù)集的詳細信息如表1所示.注意,前11 個數(shù)據(jù)集以一個整體的形式提供,實驗中利用分層采樣將其分為70%的訓(xùn)練集和30%的測試集;后4 個加“*”號的數(shù)據(jù)集以訓(xùn)練集和測試集的形式提供,實驗中直接使用訓(xùn)練集做特征選擇,測試集用于驗證,不再進行劃分.

表1 實驗數(shù)據(jù)集

包裝式特征選擇方法使用分類器來評價特征子集,后續(xù)實驗均使用K 近鄰(K-nearest neighbor,KNN)學(xué)習(xí)算法,這有利于算法之間公平的比較[9-13];KNN 的距離度量使用歐氏距離,近鄰個數(shù)為5.所有實驗均在同一臺PC 機上進行,配置為:Intel(R)Core(TM)i7-9700 CPU@ 3.00 GHz,8 GB 內(nèi)存,Win10 64 位操作系統(tǒng),編程環(huán)境為Matlab 9.9(R2020b).為了結(jié)果的客觀性,若無特別說明,對于每個數(shù)據(jù)集,算法均獨立運行20 次,以便評估算法的性能,表中所示分類精度和特征個數(shù)是20 次獨立試驗后的平均值.

4.2 重要參數(shù)的選擇

子集評價方法4 和5 分別依賴于參數(shù)ε和delta的取值,它們直接影響顯著性的判定.選取表1 中的前5 個數(shù)據(jù)集進行參數(shù)的討論,假定 ε的可能取值為{0.001,0.005,0.010,0.050,0.100,0.500},delta的可能取值為{0.05,0.10,0.15,0.20}.為選擇一組合適的參數(shù),進化策略采用基本QEA,將其分別與子集評價方法4 和5 相結(jié)合構(gòu)成2 種特征選擇算法.其它的算法參數(shù)為:種群規(guī)模G=10,最大進化代數(shù)T=50,交叉驗證次數(shù)K=10,旋轉(zhuǎn)角幅值θ=0.01 π.不同參數(shù)取值對應(yīng)的平均分類精度和特征個數(shù)如圖3所示.

從圖3(a)可以看出,除了waveform,在其它數(shù)據(jù)集上平均特征個數(shù)隨ε增大而減小,ε的值越小越好;考察分類精度,其值亦呈現(xiàn)相同的趨勢,但前3 種ε值對應(yīng)的分類精度在5 個數(shù)據(jù)集上均無顯著差異,后3 種ε值對應(yīng)的分類精度則顯著下降.綜合考慮,選取 ε的值為0.010.同理分析圖3(b),平均特征個數(shù)隨delta增大而增大,delta的值越小越好;從分類精度的角度,僅有delta=0.10 時對應(yīng)的分類精度在5 個數(shù)據(jù)集上與delta的其余4 種取值的最優(yōu)分類精度均無顯著差異,故選取delta值為0.10.

圖3 重要參數(shù)的結(jié)果對比

4.3 子集評價方法對比

為對比不同的子集評價方法,搜索策略采用基本QEA,將其分別與5 種子集評價方法相結(jié)合構(gòu)成5 種特征選擇算法,算法參數(shù)同第4.2 節(jié).表2 為5 種特征選擇方法的運行結(jié)果,其中Pij表示對方法i(i=1,2,3)和方法j(j=4,5)的20 次分類精度進行威爾科克森秩和檢驗的P 值,顯著性水平為0.05.“+”和“-”分別表示前者的分類精度顯著好于和差于后者,而“=”則表示兩者的分類精度相似,沒有顯著差異,表中最后一行統(tǒng)計了對應(yīng)列“+”“-”和“=”的個數(shù).

表2 5 種子集評價方法的分類精度和特征個數(shù)

由表2 可知,相比子集評價方法1、方法2 和方法3,方法4 至少在13 個數(shù)據(jù)集上取得相似甚至更好的分類精度;而方法5 僅在8 個數(shù)據(jù)集上表現(xiàn)出同樣的性能,在其余7 個數(shù)據(jù)集上分類精度要顯著的差于方法1、方法2 和方法3.從特征個數(shù)的角度,不難看出方法5 總是取得最優(yōu)的結(jié)果,其次是方法4.為更具體的說明,以breast 數(shù)據(jù)集為例,給出其20 次實驗中的分類精度和特征個數(shù)的箱線圖,如圖4所示.

圖4 子集評價方法在breast 數(shù)據(jù)集上的對比結(jié)果

從圖4(a)可以看出,前4 種方法對應(yīng)分類精度的中位值和平均值大致相當,難以直觀判斷哪種方法更優(yōu),但均優(yōu)于方法5 的分類精度;從圖4(b)可以很容易看出方法5 選擇的特征個數(shù)最少,其次是方法4.綜合兩者,方法4 能在確保分類精度無顯著差異的情況下,選擇特征個數(shù)更小的子集,表明針對子集評價方法的改進是有效的,后續(xù)實驗均采用方法4 作為子集評價方法.

4.4 進化策略的有效性驗證

采用子集評價方法4,將其分別與基本QEA 和改進QEA 相結(jié)合構(gòu)成2 種特征選擇方法,算法參數(shù)同第4.2 節(jié).為敘述方便,分別簡記為BQEA 和IQEA,其運行結(jié)果如表3所示,其中P為針對分類精度的威爾科克森秩和檢驗的P 值,“+”和“-”分別表示BQEA 的分類精度顯著的好于和差于IQEA,而“=”則表示兩者的分類精度相似.

由表3 可以看出,在Semeion 和Landsat 數(shù)據(jù)集上,BQEA 的分類精度顯著優(yōu)于IQEA,在Ionosphere 和Hillvalley 數(shù)據(jù)集上的結(jié)論正好相反,在其余數(shù)據(jù)集上兩者的分類精度均相似.從特征個數(shù)來看,IQEA 的結(jié)果總是優(yōu)于BQEA 對應(yīng)的結(jié)果.同樣以Breast 數(shù)據(jù)集為例,其分類精度和特征個數(shù)的箱線圖如圖5所示.

表3 BQEA 和IQEA 的運行結(jié)果

由圖5(a)可以看出,BQEA 和IQEA 的分類精度大致相當,無法直觀判斷哪種方法更優(yōu);從圖5(b)卻可以直觀的看出IQEA 選擇的特征個數(shù)小于BQEA 對應(yīng)的結(jié)果.由實驗的設(shè)置可知,BQEA 和IQEA 的差異僅在于進化策略的不同,表明針對進化策略的改進措施是有效的.

圖5 BQEA 和IQEA 在breast 數(shù)據(jù)集上的對比結(jié)果

4.5 特征選擇方法的對比

選取近年來新提出的包裝式和過濾式特征選擇方法作為對比,包括HPSOSSM[9]、SBDA[10]、ABGWO[11]、HMNWOA[12]、HGSA[13]和FS-IQEA[15],其中前5 種方法屬于包裝式,后1 種方法為過濾式.為比較的公平性,設(shè)置所有算法的種群規(guī)模G=20、進化代數(shù)T=60,交叉驗證次數(shù)K=10,每種方法其余的參數(shù)按照對應(yīng)文獻給定的值設(shè)置.這些方法連同IQEA 的運行結(jié)果如表4所示,其中Pi(i=1,2,3,4,5,6)分別表示6 種對比方法和IQEA 的分類精度做威爾科克森秩和檢驗的P 值,“+”“-”和“=”的含義同前.

由表4 可知,分類精度方面,IQEA 顯著優(yōu)于HPSOSSM 、SBDA、ABGWO、HMNWOA、HGSA和FS-IQEA 的數(shù)據(jù)集占比分別為26.67%、20.00%、26.67%、13.33%、20.00%和66.67%;取得相似分類精度的數(shù)據(jù)集占比分別為53.33%、66.67%、60.00%、73.33%、66.67%和33.33%.綜合兩者,IQEA 與比較方法取得相似甚至更好分類性能的數(shù)據(jù)集占比分別為80.00%、86.67%、86.67%、86.67%、86.67% 和100%.

表4 IQEA 與其它方法的對比結(jié)果

從特征個數(shù)來看,除了Semeion 數(shù)據(jù)集,FS-IQEA選擇的子集總是包含最少的特征,但其對應(yīng)的平均分類精度亦小于包裝式方法對應(yīng)的結(jié)果,從而證實了“相比過濾式,包裝式選擇的子集通常擁有更優(yōu)的分類性能”的一般結(jié)論.若僅考察包裝式方法,不難看出,除了LSVT 和hillvalley 數(shù)據(jù)集 ,IQEA 在其余數(shù)據(jù)集上選擇的特征個數(shù)均最少,占總數(shù)據(jù)集的86.67%.

綜合考慮分類精度和特征個數(shù),相比現(xiàn)有包裝式特征選擇方法,可以看出IQEA 在大多數(shù)情況下能取得相似甚至更好的分類性能,并且選擇的特征個數(shù)更少,降維效果更加明顯.

5 結(jié)論與展望

子集評價和搜索策略是構(gòu)成包裝式特征選擇方法的兩個關(guān)鍵要素,論文從這兩個角度出發(fā),分別提出了改進的子集評價方法和搜索策略,進而設(shè)計了一種

基于量子進化算法的包裝式特征選擇方法.大量的實驗結(jié)果表明,相比現(xiàn)有特征選擇方法,本文方法在大多數(shù)情況下能搜索到更小的特征子集,并能取得相似甚至更好的分類精度,降維效果突出.同時表明,要提高包裝式特征選擇方法的性能,除了現(xiàn)有文獻廣泛關(guān)注的搜索策略,子集評價方法也應(yīng)重點關(guān)注.

需要指出,隨著樣本量和特征個數(shù)的增加,包裝式特征選擇方法的計算量將顯著增加,甚至根本不適用.實驗中所用數(shù)據(jù)集的特征個數(shù)均不超過1 000,因此如何進一步提高算法的性能,使其適用于更高維(特征個數(shù)＞1000)數(shù)據(jù)的場合,例如基因選擇,將是下一步要研究的內(nèi)容.