基于XGBoost 的特征選擇算法

李占山，劉兆賡

（1.吉林大學計算機科學與技術學院，吉林 長春 130012；2.吉林大學軟件學院，吉林 長春 130012；3.吉林大學符號計算與知識工程教育部重點實驗室，吉林 長春 130012）

1 引言

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

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

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

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

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

目前在數(shù)據(jù)挖掘和機器學習競賽中，獲勝的隊伍大多使用XGBoost 系統(tǒng)，解決了諸如網絡內容分類、廣告競價排名、顧客行為預測等實際問題，這表明該系統(tǒng)適用范圍廣泛。基于以上分析，本文以XGBoost 為基本工具，完成如下工作。

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

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

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

4)結合理論與實驗對XGBSFS 的有效性做了全面分析與驗證。

2 XGBoost 概述

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

2.1 樹模型

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

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

2.2 樹模型的組合

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

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

2.3 重要性度量指標

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

對于上述3 種重要性度量指標，有

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

3 XGBSFS 算法

3.1 算法描述

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

1)對于缺失值的處理

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

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

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

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

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

3.2 構建樹模型計算重要性度量

本文提出的XGBSFS 在構建樹的過程中，同時對重要性度量進行計算，具體構建步驟如下。

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

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

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

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

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

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

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

3.3 ISFFS 搜索策略

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

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

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

經過若干次迭代后，最終將得到特征數(shù)目最少、分類準確性最高的目標特征集合作為特征選擇結果。

3.4 XGBSFS 偽代碼

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

算法1XGBSFS

輸入原始特征集合A

輸出目標特征集合O

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

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

從集合I1中獲取特征xb，使目標集合O加入xb后，準確性評價函數(shù)J提高

3.5 復雜度分析

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

4 實驗分析

4.1 實驗數(shù)據(jù)與方法

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

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

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

表2 對比SFFS 策略的詳細說明

表3 對比算法的詳細信息

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

4.2 實驗結果分析

在實驗結果的統(tǒng)計上，本文使用了分類準確率和維度縮減率這2 個常用于檢驗特征選擇算法性能的指標[10,24]，其中分類準確率的定義如式(9)所示，維度縮減率的定義如式(10)所示。

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

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

表4 改進前后的SFFS 策略對分類準確率的影響結果

表5 改進前后的SFFS 策略對維度縮減率的影響結果

表6 XGBSFS 及其對比算法在Wine 上的結果

表7 XGBSFS 及其對比算法在Vehicle 上的結果

表8 XGBSFS 及其對比算法在Segmentation 上的結果

表9 XGBSFS 及其對比算法在Ionosphere 上的結果

表11 XGBSFS 及其對比算法在LSVT 上的結果

表12 XGBSFS 及其對比算法在CNAE-9 上的結果

表13 XGBSFS 及其對比算法在Arcene 上的結果

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

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

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

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

5 結束語

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