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

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

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

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

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

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

1 預(yù)備知識(shí)

1.1 特征選擇問題

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

(1)

(2)

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

1.2 XGBoost算法

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

XGBoost算法可表示為

(3)

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

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

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

2 BSXGBFS算法設(shè)計(jì)

2.1 雙向搜索策略

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

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

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

2.2 BSXGBFS算法描述

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

(7)

(8)

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

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

先根據(jù)式(4)～(6)分別計(jì)算3種特征重要性, 并得到對(duì)應(yīng)的特征重要性評(píng)價(jià)集合A1,A2,A3, 然后從這3個(gè)集合中選擇2個(gè), 作為執(zhí)行雙向搜索策略的特征評(píng)價(jià)集合. 在實(shí)際操作中, 會(huì)有6種可能的排列結(jié)果, 因此可利用多核CPU的優(yōu)勢(shì)一次性并行完成計(jì)算, 縮短計(jì)算時(shí)間, 并使結(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 時(shí)間復(fù)雜度分析

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

3 實(shí)驗(yàn)設(shè)計(jì)與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

CA=CN/AS,

(9)

DR=(AF-SF)/AF,

(10)

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

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

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

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

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

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

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

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

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

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

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

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

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

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