XGBoost啟發(fā)的雙向特征選擇算法

王 麗, 王 濤, 肖 巍, 劉兆賡, 李占山

(1. 長春工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院, 長春 130012； 2. 吉林大學(xué) 人工智能學(xué)院, 長春 130012； 3. 吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 長春 130012)

特征選擇是機器學(xué)習(xí)領(lǐng)域中的一個重要問題, 可通過縮小特征維度提高模型的精度及運行速度, 減少運行時間. 在尋找最優(yōu)特征子集過程中, 通過結(jié)合一些搜索策略去除冗余特征與不相關(guān)特征, 目的是在給定的泛化誤差下選擇維度最小的特征子集, 或者選擇具有K個特征的最佳特征子集, 使其在原始樣本上產(chǎn)生最小的泛化誤差[1].

由于特征的選取方式與評價方式不同, 因此特征選擇方法又分為過濾式方法、 包裹式方法及嵌入式方法[2]. 過濾式方法通常依賴于數(shù)據(jù)的固有屬性, 如方差、 熵、 相關(guān)性等估計特征子集的重要程度, 不依賴于特定的學(xué)習(xí)器, 通常速度較快并具有可伸縮性[3]. 包裹式方法通過一些已有的機器學(xué)習(xí)算法評估所選的特征子集, 評估過程依賴于這些機器學(xué)習(xí)算法并與之不斷交互, 通常產(chǎn)生的結(jié)果較好[4]. 嵌入式方法將特征選擇過程融入學(xué)習(xí)過程中, 通過優(yōu)化預(yù)先設(shè)計好的目標函數(shù)搜索最優(yōu)特征子集, 并在學(xué)習(xí)過程中刪除對分類結(jié)果影響較小的特征, 保留良好特征[5].

由于搜索空間會隨著特征個數(shù)的增加呈指數(shù)級增長, 所以在分類問題中的特征選擇是NP難問題. 對于包含n個特征的問題, 其搜索空間會有(2n-1)種可能的結(jié)果[6-7]. 目前, 對特征選擇方法已有許多研究成果, 在分類問題中, 不同搜索策略產(chǎn)生的最優(yōu)特征子集也不同, 因此也可分為窮舉法、 隨機方法以及基于啟發(fā)式的特征選擇方法等. 窮舉法試圖完全搜索特征空間以找到一個能正確區(qū)分所有類別的最小特征集合. 但當數(shù)據(jù)的特征個數(shù)較多時, 在時間和空間上很難計算和評估所有的特征子集, 因此在包含大量特征的數(shù)據(jù)集中很少用窮舉法. 基于啟發(fā)式的特征選擇算法有定向搜索算法、 分支界限法、 最優(yōu)優(yōu)先搜索算法等[8]. 這些算法能在保持模型精度的同時找到最佳的特征子集[9]. 這類算法的優(yōu)點是具有良好的時間復(fù)雜性, 特別是基于演化計算的方法由于其超強的全局搜索能力在特征選擇問題中受到廣泛關(guān)注[10]. 如文獻[11]提出了通過基于特征的熵信息生成切割點序列表, 尋找最佳切點組合進行特征選擇的改進離散化粒子群優(yōu)化算法； 文獻[12]給出了以特征為頂點、 以特征相關(guān)性為邊構(gòu)造無向圖, 并將無向圖導(dǎo)出為最小生成樹, 通過處理最小生成樹的方法進行特征選擇.

集成學(xué)習(xí)是解決機器學(xué)習(xí)問題的重要方法之一[13], 本文受基于決策樹的集成學(xué)習(xí)中極端梯度提升算法(XGBoost)的啟發(fā), 提出一種新的特征選擇算法BSXGBFS(bidirectional search based on XGBoost for feature selection). 該算法首先考慮將XGBoost算法中用于構(gòu)建集成樹模型的指標選為特征選擇問題中單個特征的重要性度量指標, 然后提出一種新的雙向搜索策略更好地權(quán)衡如何使用多個特征重要性進行特征選擇, 最后給出新算法BSXGBFS理論上的時間復(fù)雜度上界.

1 預(yù)備知識

1.1 特征選擇問題

特征選擇問題可描述為： 對于給定N個樣本D個維度特征的數(shù)據(jù)集DataSetN×D, 特征選擇任務(wù)就是從D個維度特征中選取d個特征(d≤D), 使得目標函數(shù)J(S)取最大值, 其中SubDataSetN×d是DataSetN×D的一個特征子集, 簡記為S. 優(yōu)化目標J一般為模型的分類準確率、 維度縮減率或二者的結(jié)合. 即特征選擇的目的是通過選取特征數(shù)量盡可能少的特征子集S使得目標函數(shù)J(S)最大化. 求解特征選擇問題時, 通常采用如下二進制編碼方式將第i次選取的d維特征子集擴展到D維：

(1)

(2)

其中|S|表示在特征子集S中選取的特征數(shù)量.

1.2 XGBoost算法

極端梯度提升算法XGBoost是一種基于樹的Boosting算法[14]. XGBoost算法相比于傳統(tǒng)的梯度提升決策樹算法, 創(chuàng)新性地利用了損失函數(shù)的二階導(dǎo)數(shù)信息, 使得XGBoost算法能更快收斂, 保證了較高的求解效率, 同時還增大了可擴展性, 因為只要一個函數(shù)滿足二階可導(dǎo)的條件, 則在適當?shù)那樾蜗略摵瘮?shù)便可作為自定義的代價函數(shù)而被使用. XGBoost算法的另一個優(yōu)點是其借鑒了隨機森林算法中的列抽樣方法, 進一步降低了計算量和過擬合. 目前, XGBoost算法被廣泛應(yīng)用的原因不僅在于其訓(xùn)練后的模型表現(xiàn)好、 速度快, 能進行一些數(shù)據(jù)規(guī)模較大的計算, 而且其既能解決分類問題, 還能很好地處理回歸問題[15].

XGBoost算法可表示為

(3)

其中K表示樹的棵數(shù),F={f(x)=ωq(x)}(q:m→T,ω∈T)表示模型的函數(shù)空間,fK(xi)表示第i個樣本在第K棵樹中的分類結(jié)果. 由XGBoost算法的表達式可見, 該模型是迭代殘差樹的集合, 每次迭代時都會增加一棵樹, 每棵樹通過學(xué)習(xí)前(N-1)棵樹的殘差, 最終構(gòu)成由K棵樹線性組合而成的模型.

對任意結(jié)構(gòu)確定的樹, 有

其中C是所有樹用于產(chǎn)生節(jié)點時使用的特征集合, GainC是每棵樹用C中特征分割后產(chǎn)生的增益值, CoverC是樹用C中的特征分割時落在每個節(jié)點的樣本個數(shù).

2 BSXGBFS算法設(shè)計

2.1 雙向搜索策略

為能在特征選擇問題中算法性能更好, 本文結(jié)合經(jīng)典的前向特征選擇和后向特征選擇方法的優(yōu)勢, 提出新的雙向搜索策略, 步驟如下：

1) 前向添加過程. 首先, 設(shè)空集為初始狀態(tài)的特征選擇目標集合, 并將候選子集中的全部特征根據(jù)式(4)～(6)中的一個重要性衡量標準A1進行評價并排序. 其次, 依次從中選擇重要性高的特征添加到目標集合中, 并對加入新特征后的特征集合進行評價, 保留能提高分類準確性的特征. 經(jīng)過若干次執(zhí)行后, 得到初步的目標特征子集. 這種方法的優(yōu)勢是根據(jù)已經(jīng)評價好的特征重要性度量結(jié)果做啟發(fā)式, 能給出一個特征選擇的方向, 即初步選定一個較好的搜索空間.

2) 后向篩除過程. 將步驟1)中得到的初步目標特征子集再根據(jù)式(4)～(6)中的另一個特征重要性指標A2或A3評價后的結(jié)果篩除一個最不重要的特征, 進一步提高分類準確性. 經(jīng)過若干次執(zhí)行后, 最終得到一個分類準確率較高且特征數(shù)目較少的特征子集. 這種方法能保證通過另一個特征評價指標進一步綜合衡量出單個特征的實際重要程度, 進而保證刪除冗余特征.

2.2 BSXGBFS算法描述

BSXGBFS算法進行特征選擇主要包含兩個過程： 構(gòu)造迭代樹模型和雙向搜索策略. XGBoost算法中定義的整體損失函數(shù)為

(7)

(8)

為降低樹分割后的損失, 根據(jù)各子節(jié)點的權(quán)值進一步計算不同特征作分割點后帶來的增益Gain, 有

即作分割點的特征產(chǎn)生的增益可表示為： 該特征節(jié)點左右分支的子節(jié)點總權(quán)值之和與用該特征作分割點前總權(quán)值之差.

先根據(jù)式(4)～(6)分別計算3種特征重要性, 并得到對應(yīng)的特征重要性評價集合A1,A2,A3, 然后從這3個集合中選擇2個, 作為執(zhí)行雙向搜索策略的特征評價集合. 在實際操作中, 會有6種可能的排列結(jié)果, 因此可利用多核CPU的優(yōu)勢一次性并行完成計算, 縮短計算時間, 并使結(jié)果趨于最優(yōu).

BSXGBFS算法的偽代碼如下.

算法1BSXGBFS算法.

輸入: Original feature setA;

輸出: Objective feature setO;

O← ?

depth ← 0

Initialization the three measures of feature importance Fcount, AvgGain, AvgCover

while depth

for a inAdo

Calculus the best feature segmentation pointak

Generate left child node and right child node

depth ← depth+1

Update ensemble model

for tree in ensemble model do

for node of tree do

Calculate gain and cover generated by node

Fcount ← Fcount+1

Gain ← Gain+gain

Cover ← Cover+cover

forainAdo

AvgGain ← Gain/Fcount

AvgCover ← Cover/Fcount

GetA1from sortingAin descending order according to Fcount

GetA2from sortingAin descending order according to AvgGain

GetA3from sortingAin descending order according to AvgCover

Select two set fromA1,A2andA3randomly, then rename them asB1andB2

ReverseB2

forbiinB1do

O′←O∪bi

ifJ(O′)>J(O) then

O←O′

forbjinB2do

ifbjinO

O′←O-bj

ifJ(O′)>J(O) then

O←O′

returnO.

2.3 時間復(fù)雜度分析

O(MNlgN+MNKD+mlgm+2mT).

3 實驗設(shè)計與分析

3.1 實驗設(shè)計

實驗選擇目前應(yīng)用最廣泛的UCI(UCI machine learning repository)數(shù)據(jù)庫中的11個覆蓋低維到超高維的標準數(shù)據(jù)集, 各數(shù)據(jù)集信息列于表1. 實驗選擇多策略二元蝴蝶優(yōu)化特征選擇算法(OEbBOA)[16]、 基于森林優(yōu)化算法的特征選擇算法(FSFOA)[17]、 基于蝴蝶優(yōu)化算法的特征選擇算法(bBOA)[18]、 使用聯(lián)合互信息策略的特征選擇算法(JMI)[19]、 使用互信息最大化策略的特征選擇算法(MIM)[19]、 基于二元蝗蟲優(yōu)化算法的特征選擇算法(BGOA_M)[20]作為與本文算法的對比算法. 實驗中全部實驗代碼使用Python 3.6實現(xiàn). 實驗平臺處理器為AMD Ryzen 7 1700, 內(nèi)存容量32 GB, 硬盤容量2 TB.

表1 UCI的數(shù)據(jù)集信息

3.2 實驗分析

采用多數(shù)研究中常用的分類準確率(classification accuracy, CA)與維度縮減率(dimensionality reduction, DR)做實驗結(jié)果分析的性能衡量指標[21-22]:

CA=CN/AS,

(9)

DR=(AF-SF)/AF,

(10)

其中CN表示分類正確的樣例數(shù), AS表示全部樣例數(shù), AF表示特征總數(shù), SF表示進行特征選擇后的特征數(shù). 采用KNN(K=1)作為評價分類準確率的基分類器. KNN分類器具有易實現(xiàn)且參數(shù)較少, 能更好地反映特征選擇算法自身性能的特點, 因此使用KNN測試特征選擇算法的性能, 并用于對比實驗[18-22]. 數(shù)據(jù)集的劃分均采用70%的樣例作為訓(xùn)練集, 30%的樣例作為測試集. 實驗結(jié)果列于表2～表12.

表2 BSXGBFS及其對比算法在Wine數(shù)據(jù)集上的測試結(jié)果

表3 BSXGBFS及其對比算法在Vehicle數(shù)據(jù)集上的測試結(jié)果

表4 BSXGBFS及其對比算法在Segmentation 數(shù)據(jù)集上的測試結(jié)果

表5 BSXGBFS及其對比算法在Ionosphere數(shù)據(jù)集上的測試結(jié)果

表6 BSXGBFS及其對比算法在Sonar數(shù)據(jù)集上的測試結(jié)果

表7 BSXGBFS及其對比算法在LSVT數(shù)據(jù)集上的測試結(jié)果

表8 BSXGBFS及其對比算法在CNAE-9 數(shù)據(jù)集上的測試結(jié)果

表9 BSXGBFS及其對比算法在Arcene 數(shù)據(jù)集上的測試結(jié)果

表10 BSXGBFS及其對比算法在10 000維內(nèi)的數(shù)據(jù)集上分類準確率測試結(jié)果

表11 BSXGBFS及其對比算法在10 000維內(nèi)的數(shù)據(jù)集上維度縮減率測試結(jié)果

表12 BSXGBFS及其對比算法在高維數(shù)據(jù)集上的測試結(jié)果

由表2～表12可見, 對于10 000維以內(nèi)的數(shù)據(jù)集, BSXGBFS算法無論是在分類準確率還是維度縮減率上, 都存在較高的競爭力, 甚至在Ionosphere,Sonar,CNAE-9,Arcene這4個數(shù)據(jù)集上, 分類準確率和維度縮減率性能在全部對比算法中都達到了最優(yōu). 因此, BSXGBFS算法不存在如OEbBOA,FSFOA,BGOA_M等基于演化計算的特征選擇算法需要過多犧牲維度縮減率換取分類準確率的問題, 而是在確保分類準確率的前提下兼顧了維度縮減率, 也進一步驗證了采用特征重要性評價作啟發(fā)式的合理性. 由表12可見, 在使用RNA-Seq,Dorothea,News20這3個數(shù)據(jù)集對BSXGBFS算法進行極限測試的過程中, 發(fā)現(xiàn)BSXGBFS算法具有可以進一步計算10 000維以上高維數(shù)據(jù)集的能力, 甚至在10萬維Dorothea數(shù)據(jù)集和100萬維News20數(shù)據(jù)集上都具有可計算性. 實驗結(jié)果表明, BSXGBFS算法的性能與預(yù)期相符, 不僅在中低維數(shù)據(jù)集上的性能良好, 而且在高維數(shù)據(jù)集上也具有可計算性.

綜上所述, 本文受集成學(xué)習(xí)算法XGBoost的啟發(fā), 提出了一種適用范圍更廣, 能處理高維數(shù)據(jù)的特征選擇算法BSXGBFS. 對比實驗結(jié)果表明, BSXGBFS算法不僅在中低維數(shù)據(jù)集上相比于其他算法更具競爭力, 同時在高維甚至超高維數(shù)據(jù)集上也具有良好、 可靠的計算能力.