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

雷華軍,蔣 強

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

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

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

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

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

1 問題描述

為結構完整性,給出特征選擇的形式化描述.假定D={(s1,y1),(s2,y2),···,(sm,ym)}為原始數據集,S=(s1,s2,···,sm)T為樣本矩陣,行和列分別代表不同的樣本和特征,Y=(y1,y2,···,ym)T為各樣本對應的真實類別.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分別為樣本、特征和類別的個數.

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

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

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

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

2 量子進化算法

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

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

3 特征選擇方法

3.1 種群初始化

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

3.3 種群進化策略

3.4 整個算法流程

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

圖2 特征選擇方法的流程

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

4 實驗與結果分析

4.1 實驗方案

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

表1 實驗數據集

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

4.2 重要參數的選擇

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

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

圖3 重要參數的結果對比

4.3 子集評價方法對比

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

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

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

圖4 子集評價方法在breast 數據集上的對比結果

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

4.4 進化策略的有效性驗證

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

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

表3 BQEA 和IQEA 的運行結果

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

圖5 BQEA 和IQEA 在breast 數據集上的對比結果

4.5 特征選擇方法的對比

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

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

表4 IQEA 與其它方法的對比結果

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

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

5 結論與展望

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

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

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