基于XGBoost 的特征選擇算法

李占山，劉兆賡

（1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長春 130012；2.吉林大學(xué)軟件學(xué)院，吉林 長春 130012；3.吉林大學(xué)符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，吉林 長春 130012）

1 引言

特征選擇（feature selection）也稱屬性選擇（attribute selection），是從原始特征中選擇一些有效特征來降低數(shù)據(jù)集維度的過程[1]，是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中關(guān)鍵的預(yù)處理步驟。對(duì)于特征選擇的設(shè)計(jì)，國內(nèi)外學(xué)者已進(jìn)行了大量的研究。常見的特征選擇方法大致有3 類：過濾式（filter）、嵌入式（embedding）和包裹式（wrapper）[2]。過濾式方法在訓(xùn)練學(xué)習(xí)器之前會(huì)對(duì)數(shù)據(jù)集進(jìn)行篩選，特征選擇過程與后續(xù)學(xué)習(xí)器無關(guān)；嵌入式方法將特征選擇過程與學(xué)習(xí)器訓(xùn)練過程融為一體，在學(xué)習(xí)器訓(xùn)練過程中自動(dòng)地進(jìn)行特征選擇[3]；包裹式方法直接將最終要使用的學(xué)習(xí)器的性能作為特征子集的評(píng)價(jià)標(biāo)準(zhǔn)，通常被證明搜尋特征子集的分類準(zhǔn)確性優(yōu)于前二者[4]。

搜索最優(yōu)特征子集是特征選擇過程中最關(guān)鍵、最具有挑戰(zhàn)性的一環(huán)。對(duì)于不同的搜索策略，特征選擇方法又可以分為窮舉法、啟發(fā)式法、基于信息理論的方法、基于演化計(jì)算的方法等。Almuallim等[5]基于窮舉法提出的FOCUS 算法是在整個(gè)搜索空間中進(jìn)行搜尋，直到找出一個(gè)最小的特征子集將訓(xùn)練數(shù)據(jù)分成單純的類。但是FOCUS 的時(shí)間復(fù)雜度是O(2n)，當(dāng)特征數(shù)量非常大時(shí)，評(píng)價(jià)所有特征子集的時(shí)間開銷幾乎是不可接受的[6]，因此，在實(shí)際任務(wù)中很少使用窮舉法。特征選擇的啟發(fā)式方法主要包括爬山法、分支限界法、定向搜索法和最佳優(yōu)先搜索法[7-8]。相較于窮舉法而言，啟發(fā)式方法更加高效，在解決實(shí)際問題的過程中，人們往往將啟發(fā)式方法集成到包裹式方法中，以便權(quán)衡運(yùn)算效率和特征子集的質(zhì)量，獲得一個(gè)好的平衡點(diǎn)，繼而得到近似最優(yōu)解。基于信息理論的方法主要是應(yīng)用不同的信息策略來過濾特征，其中具有代表性的有基于聯(lián)合互信息（JMI,joint mutual information）的特征選擇方法和基于互信息最大化（MIM,mutual information maximization）的特征選擇方法?；谘莼?jì)算的方法是近年來應(yīng)用較廣的一類方法，相比于其他方法，這類方法具有更強(qiáng)的全局搜索能力[9]，最近的研究表明基于森林優(yōu)化的特征選擇方法[10]和基于收益成本的螢火蟲方法[11]均具有良好的性能?；谘莼?jì)算的方法雖然性能較好，但也有不足的地方：首先只有迭代次數(shù)足夠大時(shí)才可能找到比較好的結(jié)果，其次如何設(shè)置參數(shù)也是一個(gè)問題。本文基于XGBoost 提出了一種新型的包裹式特征選擇算法XGBSFS（XGBoost sequential floating selection）。XGBoost 是Chen 等[12]在前人關(guān)于梯度提升算法的大量研究工作基礎(chǔ)上提出的一個(gè)基于提升樹的機(jī)器學(xué)習(xí)系統(tǒng)，它包含一個(gè)迭代殘差樹的集合，每一棵樹都在學(xué)習(xí)前N-1 棵樹的殘差，將每棵樹預(yù)測(cè)的新樣本輸出值相加就是樣本最終的預(yù)測(cè)值[13]。但不同于常用的梯度提升決策樹（GBDT,gradient boosting decision tree）在優(yōu)化時(shí)僅用一階導(dǎo)數(shù)信息，XGBoost對(duì)代價(jià)函數(shù)進(jìn)行了二階泰勒展開，同時(shí)用到了一階導(dǎo)數(shù)和二階導(dǎo)數(shù)，使XGBoost 具有良好的結(jié)果。所提算法的主要特點(diǎn)如下。

1)XGBoost 具有良好的防過擬合特性。

2)XGBoost 擁有較高的計(jì)算效率。

3)XGBoost 的計(jì)算過程中有一定的啟發(fā)性。

目前在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)競(jìng)賽中，獲勝的隊(duì)伍大多使用XGBoost 系統(tǒng)，解決了諸如網(wǎng)絡(luò)內(nèi)容分類、廣告競(jìng)價(jià)排名、顧客行為預(yù)測(cè)等實(shí)際問題，這表明該系統(tǒng)適用范圍廣泛?；谝陨戏治?，本文以XGBoost 為基本工具，完成如下工作。

1)基于XGBoost 構(gòu)建了用于求解特征選擇問題的啟發(fā)式策略。

2)提出了基于2 種重要性度量的序列浮動(dòng)前向選擇策略ISFFS。

3)提出了一個(gè)新型的包裹式特征選擇算法XGBSFS。

4)結(jié)合理論與實(shí)驗(yàn)對(duì)XGBSFS 的有效性做了全面分析與驗(yàn)證。

2 XGBoost 概述

XGBoost 是梯度提升（gradient boosting）思想的一種高效的系統(tǒng)實(shí)現(xiàn)，其基學(xué)習(xí)器既可以是線性分類器，也可以是樹。本文利用其樹模型的特點(diǎn)作為量化每個(gè)特征重要性的依據(jù)進(jìn)行特征選擇。

2.1 樹模型

對(duì)于給定的數(shù)據(jù)集，在樹模型構(gòu)建的過程中，每一層貪心地選取一個(gè)特征分割點(diǎn)作為葉子節(jié)點(diǎn)，使在分割之后整棵樹增益值最大，這意味著特征被分割次數(shù)越多，該特征給整棵樹帶來的效益越大，該特征也越重要；相似地，特征每次被分割時(shí)的平均增益越大，該特征越重要。在分割過程中，每個(gè)葉子節(jié)點(diǎn)的權(quán)值可以表示為w(gi,hi)，gi和hi分別為

式(3)說明了對(duì)于每一個(gè)分割點(diǎn)而言，其增益可表示為分割后的總權(quán)值（葉子節(jié)點(diǎn)左子樹的總權(quán)值與右子樹的總權(quán)值之和）減去分割前的葉子節(jié)點(diǎn)的總權(quán)值。

2.2 樹模型的組合

決策樹模型作為一種非參數(shù)監(jiān)督式學(xué)習(xí)模型，常用于分類與回歸，該模型不需要對(duì)數(shù)據(jù)有任何的先驗(yàn)假設(shè)，就可以快速地根據(jù)數(shù)據(jù)的特征找到?jīng)Q策規(guī)則[14]。而XGBoost 在決策樹的基礎(chǔ)上采用了集成策略，利用梯度提升算法不斷減小前面生成的決策樹的損失，并產(chǎn)生新樹構(gòu)成模型，確保了最終決策的可靠性。XGBoost 在每一次迭代的時(shí)候都會(huì)增加一棵樹，則構(gòu)建K棵樹的線性組合為

其中，F(xiàn)表示包含所有樹的函數(shù)空間，fk(xi)表示第i個(gè)樣本在第k棵樹中被分類到所在葉子節(jié)點(diǎn)的權(quán)重。

2.3 重要性度量指標(biāo)

重要性度量指標(biāo)是評(píng)估每個(gè)特征在所屬特征集中重要程度的一種衡量方式。XGBoost 根據(jù)特征分裂的次數(shù)FScore、特征平均增益值A(chǔ)verageGain和特征平均覆蓋率AverageCover 來作為其構(gòu)建決策樹的依據(jù)，以便準(zhǔn)確地完成分類任務(wù)。

對(duì)于上述3 種重要性度量指標(biāo)，有

其中，X是所求特征分類到葉子節(jié)點(diǎn)的集合；Gain是X中每個(gè)葉子節(jié)點(diǎn)由式(3)得到的在分割時(shí)節(jié)點(diǎn)增益值；Cover 是X中落在每個(gè)節(jié)點(diǎn)的樣本個(gè)數(shù)。

3 XGBSFS 算法

3.1 算法描述

通過以上分析，本文提出了一種基于XGBoost 的包裹式特征選擇方法XGBSFS，利用XGBoost 算法構(gòu)建樹的過程，分別根據(jù)FScore、AverageGain 和AverageCover 計(jì)算特征重要性度量，然后提出一種改進(jìn)的序列浮動(dòng)前向選擇策略（ISFFS,improved sequential floating forward selection）進(jìn)行搜索，最后把分類準(zhǔn)確率最高的特征子集作為特征選擇結(jié)果。XGBSFS 用于特征選擇特點(diǎn)如下。

1)對(duì)于缺失值的處理

利用XGBoost 獨(dú)特的樹模型，使XGBSFS 能夠?qū)?shù)據(jù)集中的一些缺失值進(jìn)行處理。XGBSFS 先將缺失值轉(zhuǎn)換為稀疏矩陣，將缺失值數(shù)據(jù)分到左子樹和右子樹分別計(jì)算損失，并選擇損失較小的子樹；如果訓(xùn)練中沒有數(shù)據(jù)缺失，但預(yù)測(cè)時(shí)出現(xiàn)了數(shù)據(jù)缺失，那么缺失數(shù)據(jù)被默認(rèn)分類到右子樹[12]。如此便有效降低了樹模型對(duì)缺失值的敏感度。

2)對(duì)于零重要度特征的處理

在樹模型構(gòu)建中，零重要度的特征，即特征節(jié)點(diǎn)分裂次數(shù)FScore=0 的特征不會(huì)被用于分割任何節(jié)點(diǎn)，移除它們不會(huì)影響最終的模型表現(xiàn)，因此XGBSFS在得到特征的重要性度量后優(yōu)先過濾零重要度特征。

3)對(duì)于特征的重要性處理順序

利用給定結(jié)構(gòu)的樹模型集合，對(duì)非零重要度特征進(jìn)行排序；考慮到單向搜索的局限性，因此XGBSFS 采用不同的重要性度量雙向進(jìn)行搜索，以獲得更好的效果。

3.2 構(gòu)建樹模型計(jì)算重要性度量

本文提出的XGBSFS 在構(gòu)建樹的過程中，同時(shí)對(duì)重要性度量進(jìn)行計(jì)算，具體構(gòu)建步驟如下。

1)從根節(jié)點(diǎn)開始，對(duì)每一節(jié)點(diǎn)都遍歷所有的特征。

2)對(duì)于特征ai∈A，先按照樣本值進(jìn)行排序，線性掃描ai確定增益最好的分割點(diǎn)

3)從所有選擇好的特征分割點(diǎn)中選取增益最高的特征進(jìn)行分割，并更新樣本到樹節(jié)點(diǎn)的映射關(guān)系。

4)一直分割到最大深度，并計(jì)算構(gòu)建下一棵樹的殘差。

5)將生成的所有樹集成，完成最終樹模型的構(gòu)建。

6)根據(jù)式(5)～式(7)計(jì)算重要性度量。

在XGBoost 的相關(guān)研究中，許多學(xué)者已經(jīng)驗(yàn)證了該樹模型的優(yōu)勢(shì)及其高效的原因[12,15-16]。本文在此基礎(chǔ)之上，結(jié)合所提出的ISFFS 搜索策略，將XGBoost 在特征選擇問題的求解中進(jìn)行了更好的擴(kuò)展應(yīng)用。

3.3 ISFFS 搜索策略

對(duì)全部特征根據(jù)重要性度量進(jìn)行排序，可以得到原始的候選子集。傳統(tǒng)的搜索策略有3 種：前向搜索（forward search）、后向搜索（backward search）和雙向搜素（bidirectional search）。逐漸增加相關(guān)特征的策略稱為前向搜索[17]：首先取當(dāng)前最優(yōu)的特征作為第一輪的選定集，接下來每一輪輪番添加一個(gè)特征，對(duì)每次生成的集合判斷是否優(yōu)于上一輪，若是，保留本輪的結(jié)果作為新的選定集；若不是，則停止搜索，并將上一輪選定的集合作為特征選擇的結(jié)果[18]。相反，若從完整的候選集合開始，每輪嘗試舍棄一個(gè)無關(guān)特征，像這樣逐漸減少特征的策略稱為后向搜索[19]。而雙向搜索結(jié)合了前向與后向搜索策略，每輪根據(jù)評(píng)價(jià)算法并行地選出最優(yōu)特征和無關(guān)特征：在增加相關(guān)最優(yōu)特征的同時(shí)去掉一個(gè)無關(guān)特征，且新加入的特征在后續(xù)搜索過程中不會(huì)被淘汰[20]。然而，上述策略容易陷入局部最優(yōu)[18,21]。本文通過對(duì)傳統(tǒng)搜索策略的研究，提出了一種改進(jìn)的序列浮動(dòng)前向搜索方法ISFFS。一般的序列浮動(dòng)前向搜索方法只使用一種重要性度量指標(biāo)搜索候選集合，而ISFFS 同時(shí)使用了2 種不同的重要性度量i1和i2進(jìn)行搜索，從而避免被單一重要性度量所約束，在一定程度上減少了問題的局限性。該策略主要包含2 個(gè)步驟，具體如下。

步驟1序列前向添加。建立一個(gè)起始為空的目標(biāo)特征集合，每次從原始的候選子集中，依據(jù)重要性度量i1從大到小搜索一個(gè)最重要的特征添加到目標(biāo)集合中，使在這個(gè)特征加入之后，目標(biāo)集合的分類準(zhǔn)確性提高。

步驟2浮動(dòng)后向篩除。從目標(biāo)集合中根據(jù)重要性度量i2從小到大搜索并剔除一個(gè)特征，使在去除該特征之后，目標(biāo)集合的分類準(zhǔn)確性提高，一直篩到不存在能使準(zhǔn)確性提高的特征，返回步驟1。

經(jīng)過若干次迭代后，最終將得到特征數(shù)目最少、分類準(zhǔn)確性最高的目標(biāo)特征集合作為特征選擇結(jié)果。

3.4 XGBSFS 偽代碼

結(jié)合前文描述，本文給出了XGBSFS 算法，其偽代碼如算法1 所示。

算法1XGBSFS

輸入原始特征集合A

輸出目標(biāo)特征集合O

根據(jù)重要性度量分別對(duì)特征進(jìn)行排序

選取2 個(gè)候選特征子集I1和I2，其中I1是根據(jù)重要性度量i1從大到小排列的集合，I2是根據(jù)重要性度量i2從小到大排列的集合

從集合I1中獲取特征xb，使目標(biāo)集合O加入xb后，準(zhǔn)確性評(píng)價(jià)函數(shù)J提高

3.5 復(fù)雜度分析

考慮D為樹的最大深度，K為樹的個(gè)數(shù)，給定無缺失值的數(shù)據(jù)集，其樣本量為N，特征數(shù)量為M，非零重要性特征的比例為β，令m=Mβ，則對(duì)于精確貪婪算法（exact greedy）[12]下的全局特征預(yù)排序，有排序復(fù)雜度O(MnlogN)；由于后期節(jié)點(diǎn)分裂時(shí)都可以復(fù)用全局預(yù)排序的結(jié)果，不需要消耗額外的時(shí)間來進(jìn)行排序。對(duì)于樹模型構(gòu)建的過程，每一層遍歷分割點(diǎn)的時(shí)間復(fù)雜度為O(MN)，故建立K棵樹的時(shí)間復(fù)雜度為O(MNKD)。對(duì)所得非零重要性特征子集進(jìn)行排序，采用快速排序算法的平均時(shí)間復(fù)雜度為O(mlogm)。在搜索策略SFFS 中，序列前向添加過程從頭遍歷到尾，由于|S|=m，故添加過程時(shí)間復(fù)雜度為O(m)；浮動(dòng)后向篩除過程從尾遍歷到頭，由于|O|≤m，故篩除過程時(shí)間復(fù)雜度為O(m)；ISFFS總的時(shí)間復(fù)雜度為O(m2)×基分類器的時(shí)間復(fù)雜度。當(dāng)基分類器為KNN（k-nearest neighbor）時(shí)，主流的KNN 分類器均是經(jīng)過KD tree 或是ball tree優(yōu)化后的，其復(fù)雜度可近似表示為O(mNlogN)。所以 ISFFS 過程的時(shí)間復(fù)雜度可近似表示為O(m3NlogN)。故XGBSFS 算法總的時(shí)間復(fù)雜度可近似表示為

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

4.1 實(shí)驗(yàn)數(shù)據(jù)與方法

本文從UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫（UCI machine learning repository）[22]中選擇了8 個(gè)數(shù)據(jù)集進(jìn)行測(cè)試，這些數(shù)據(jù)集的特征數(shù)、樣本數(shù)和分類數(shù)如表1 所示。

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

為了驗(yàn)證ISFFS 策略的有效性，分別獨(dú)立使用FScore、AverageGain 和AverageCover 做了序列浮動(dòng)前向搜索，對(duì)比SFFS 策略的詳細(xì)說明如表2 所示。為了便于比較本文所提算法的性能，選擇其他具有代表性的特征選擇算法進(jìn)行對(duì)比，對(duì)比算法的詳細(xì)信息如表3 所示。

表2 對(duì)比SFFS 策略的詳細(xì)說明

表3 對(duì)比算法的詳細(xì)信息

在本文的實(shí)驗(yàn)中，使用了python 3.6 實(shí)現(xiàn)算法，同時(shí)使用了公開的工具包 XGBoost、scikit-feature 和 scikit-learn。所有實(shí)驗(yàn)均在一臺(tái)配置為AMD R7 1700 CPU、16 GB 內(nèi)存、500 GB硬盤的電腦上完成。

4.2 實(shí)驗(yàn)結(jié)果分析

在實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)上，本文使用了分類準(zhǔn)確率和維度縮減率這2 個(gè)常用于檢驗(yàn)特征選擇算法性能的指標(biāo)[10,24]，其中分類準(zhǔn)確率的定義如式(9)所示，維度縮減率的定義如式(10)所示。

其中，NCC 代表正確的分類數(shù)，NAS 代表數(shù)據(jù)集的總實(shí)例，NSF 代表選擇的特征數(shù)，NAF 代表總的特征數(shù)。

在分類器的選擇上，本文使用了KNN 分類器作為基分類器。之所以使用KNN 是因?yàn)槠涫且粋€(gè)通用簡便的分類方法，并且由于KNN 分類器相較于其他分類器來說，并不需要調(diào)整過多的參數(shù)，因此較容易進(jìn)行對(duì)比實(shí)驗(yàn)來驗(yàn)證特征選擇算法的性能。目前提出的很多包裹式特征選擇算法，僅使用了KNN 作為唯一的基分類器[11,25-26]，它們之間唯一區(qū)別在于參數(shù)K的取值。本文中，為了與Rc-BBFA 對(duì)比方便，在參數(shù)K的選取上和Rc-BBFA保持了一致，將K設(shè)置為1。表4和表5是驗(yàn)證ISFFS策略有效性的實(shí)驗(yàn)結(jié)果，表6～表13 給出了XGBSFS與其他特征選擇算法的對(duì)比實(shí)驗(yàn)結(jié)果，其中，加粗字體表示對(duì)應(yīng)的最優(yōu)值。

表4 改進(jìn)前后的SFFS 策略對(duì)分類準(zhǔn)確率的影響結(jié)果

表5 改進(jìn)前后的SFFS 策略對(duì)維度縮減率的影響結(jié)果

表6 XGBSFS 及其對(duì)比算法在Wine 上的結(jié)果

表7 XGBSFS 及其對(duì)比算法在Vehicle 上的結(jié)果

表8 XGBSFS 及其對(duì)比算法在Segmentation 上的結(jié)果

表9 XGBSFS 及其對(duì)比算法在Ionosphere 上的結(jié)果

表11 XGBSFS 及其對(duì)比算法在LSVT 上的結(jié)果

表12 XGBSFS 及其對(duì)比算法在CNAE-9 上的結(jié)果

表13 XGBSFS 及其對(duì)比算法在Arcene 上的結(jié)果

從表4 可以發(fā)現(xiàn)，本文提出的同時(shí)使用2 種重要性度量的ISFFS 在全部數(shù)據(jù)集的分類準(zhǔn)確率上均能帶來不同程度的提升。在效果較為明顯的Wine數(shù)據(jù)集上，ISFFS 甚至比僅使用單一重要性度量指標(biāo)的序列浮動(dòng)前向搜索策略中表現(xiàn)最好的SFFS1高出了6%。從表5 可以看出，ISFFS 在Vehicle、Segmentation 和LSVT 這3 個(gè)數(shù)據(jù)集上的表現(xiàn)均位于最優(yōu)，因此在這3 個(gè)數(shù)據(jù)集上本文所提改進(jìn)策略無疑是最佳的。至于在其他數(shù)據(jù)集上，ISFFS 的表現(xiàn)不如表4 明顯，是因?yàn)樗阉鬟^程中的主要目標(biāo)是分類準(zhǔn)確率，所以并不能保證維度縮減率也達(dá)到最優(yōu)?？偠灾?，ISFFS 不僅可以提升分類準(zhǔn)確率，而且在一定程度上能保證算法在CA 取最優(yōu)時(shí)仍使DR 達(dá)到最優(yōu)。唯一比較遺憾的是，在進(jìn)行搜索之前，沒有很好的方法能夠得知由XGBSFS 所計(jì)算出的3 個(gè)重要性指標(biāo)構(gòu)成的6 個(gè)組合中哪個(gè)是最優(yōu)的。不過，總共僅有6 種情況尚屬于可枚舉的范圍，所以在實(shí)際實(shí)驗(yàn)操作中，本文恰好可以利用多核CPU 的計(jì)算特性，采用6 個(gè)內(nèi)核并行運(yùn)算的方式來降低計(jì)算時(shí)間開銷，最后從中選擇出分類準(zhǔn)確率最佳的結(jié)果即為最終結(jié)果。

通過對(duì)比表6～表13 可以看出，XGBSFS 在Vehicle、Ionosphere、Sonar 和Arcene 這4 個(gè)數(shù)據(jù)集上的平均分類準(zhǔn)確率均達(dá)到了最高，在Wine、Segmentation、LSVT 和CNAE-9 這4 個(gè)數(shù)據(jù)集上的平均分類準(zhǔn)確率稍微落后于目前性能較好的基于螢火蟲算法的特征選擇算法，總體來看，在分類準(zhǔn)確率上XGBSFS 和Rc-BBFA 處于伯仲之間。對(duì)比JMI 和MIM 這2 個(gè)常用的基于信息理論的啟發(fā)式特征選擇策略，很容易發(fā)現(xiàn)本文提出的基于XGBoost的啟發(fā)式方法XGBSFS在這些數(shù)據(jù)集上的準(zhǔn)確率性能是占優(yōu)勢(shì)的。觀察DR 值，除了Wine和LSVT 數(shù)據(jù)集之外，XGBSFS 的維度縮減率也均是最優(yōu)的。另外結(jié)合式(8)中提出的復(fù)雜度進(jìn)一步分析發(fā)現(xiàn)，對(duì)于絕大部分的實(shí)驗(yàn)數(shù)據(jù)集，均有M≤[(1-DR)×M]3，由此可以近似得出M≤m3。又因?yàn)樵谕ǔＧ闆r下mlogm＜m3NlogN，根據(jù)時(shí)間復(fù)雜度的性質(zhì)，可以將式(8)簡化成O(MNKD+m3NlogN)。這樣基于簡化后的形式，可以合理做一假設(shè)，當(dāng)XGBSFS 處理M或N較大的數(shù)據(jù)集時(shí)，KD會(huì)趨近于常數(shù)，所以m3NlogN的大小是最終決定算法性能的關(guān)鍵，而這一項(xiàng)的出現(xiàn)，是經(jīng)由基于KNN 分類器的時(shí)間復(fù)雜度提出的，再者絕大多數(shù)分類器的時(shí)間復(fù)雜度都是大于KNN 分類器的，因此可以說本文所提算法仍主要受限于包裹式特征選擇框架。但由于XGBSFS 在DR 值上有優(yōu)良表現(xiàn)，因此這從側(cè)面驗(yàn)證了本文基于XGBoost 提出啟發(fā)式策略的合理性，也很好地印證了本文所采用的啟發(fā)式策略的高效性。

綜合8 個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析發(fā)現(xiàn)，大多數(shù)數(shù)據(jù)集的準(zhǔn)確率都在90%以上，只有Vehicle 數(shù)據(jù)集上的結(jié)果是75.95%。之所以有這種情況，是因?yàn)閂ehicle 數(shù)據(jù)集用于1NN 分類器進(jìn)行分類時(shí)效果并不是很好，但這并不能證明本文所提特征選擇算法XGBSFS 不適用于這一數(shù)據(jù)集，相反，通過XGBSFS對(duì)Vehicle 進(jìn)行特征選擇之后，會(huì)達(dá)到全部對(duì)比算法中最高的分類準(zhǔn)確率和維度縮減率，這說明了XGBSFS 在該數(shù)據(jù)集上的優(yōu)越性。而像在LSVT 數(shù)據(jù)集上，雖然CA 和DR 值都在90%以上，但XGBSFS 的總體對(duì)比并沒有十分突出，反而不能說明XGBSFS 在該數(shù)據(jù)集上性能優(yōu)秀。

總體而言，XGBSFS 之所以在有些數(shù)據(jù)集上表現(xiàn)良好，有些數(shù)據(jù)集上的結(jié)果不太理想，主要是因?yàn)橥ㄟ^XGBoost 計(jì)算的3 種重要性指標(biāo)符合數(shù)據(jù)內(nèi)在分布規(guī)律時(shí)，結(jié)果就令人滿意，不符合數(shù)據(jù)的內(nèi)在規(guī)律時(shí)，即使通過ISFFS 策略混合了不同的重要性指標(biāo)，也只能在有限的程度上改善結(jié)果；另一個(gè)導(dǎo)致實(shí)驗(yàn)結(jié)果不同的因素是數(shù)據(jù)集中存在的離群數(shù)據(jù)的數(shù)量，離群數(shù)據(jù)越多，對(duì)算法特征重要性計(jì)算的準(zhǔn)確性干擾越大，進(jìn)而影響實(shí)驗(yàn)結(jié)果。

5 結(jié)束語

本文提出了一種基于XGBoost 的包裹式特征選擇算法XGBSFS，該算法利用XGBoost 的重要性量度作為特征子集搜索啟發(fā)依據(jù)，同時(shí)通過采用提出的ISFFS 策略較好地完成了特征選擇任務(wù)。實(shí)驗(yàn)結(jié)果表明，本文提出的特征選擇算法與其他特征選擇算法相比具有一定的競(jìng)爭優(yōu)勢(shì)。在今后的工作中，將進(jìn)一步提高本文所提算法在超高維數(shù)據(jù)集以及龐大實(shí)例數(shù)據(jù)集上的性能，同時(shí)嘗試采用并行計(jì)算或其他策略，努力尋求能讓算法突破包裹式特征選擇框架限制的方法。