基于LightGBM的特征選擇算法

李占山, 姚 鑫, 劉兆賡, 張家晨

(吉林大學 計算機科學與技術學院, 吉林 長春 130012)

特征選擇是數(shù)據挖掘、機器學習等領域中的重要方向,其主要通過減少冗余與不相關特征、使用合適的搜索策略來尋找最優(yōu)特征子集,力求在減小特征維度的情況下減少運行時間、提高模型精度.特征選擇的目標是在滿足給定某種泛化誤差的條件下挑選最小特征子集;或選擇指定個數(shù)的特征子集,并使其在原始樣本上產生最小的泛化誤差[1].依據方法自身與構建模型的關系,特征選擇主要分為過濾式方法和包裹式方法[2].

過濾式方法對數(shù)據特征按照一定標準進行排序并選擇表現(xiàn)較好的特征,由于這些標準獨立于學習過程且單獨評價每個特征的重要度,不考慮對結果的影響,因而過濾式方法通常具有較高的計算效率，卻很難得到具有較高分類準確率的特征子集[3-4].

為克服過濾式的缺點,包裹式方法一般會引入學習器來評估所選的特征子集,并根據評估結果來選擇特征子集,進而找到最優(yōu)特征子集.該方法引入與學習器的交互后雖然增加了計算量,但通過不斷交互通常能得到滿足給定泛化誤差的優(yōu)秀特征子集[3-4].

過濾式方法運行效率較高,但由于其選擇特征的過程并沒有考慮到后續(xù)學習,因而得到的特征子集的分類精度一般低于包裹式,經常不能滿足后續(xù)任務的需求;包裹式方法雖然能夠得到具有較高分類精度的特征子集,但引入的交互過程降低了計算效率,增加了算法復雜度,故包裹式對要求短時間內求解的任務適應性較差.

在現(xiàn)有研究工作中,過濾式研究著力于采用某種度量標準在較低時間復雜度內得到特征子集,包裹式的研究力求通過不斷的交互得到更高分類精度的特征子集.以上兩類研究缺乏對特征子集計算效率和分類精度的協(xié)調與平衡.

為克服這兩類方法的缺陷,本文采用LightGBM中兩種特征重要度指標作為數(shù)據特征間的度量依據,并在此基礎上提出一種包裹式的特征選擇算法LGBFS(LightGBM feature selection),并將提出算法與對比算法在通用的21個UCI標準數(shù)據集上對分類精度、維度縮減率和CPU時間三種指標進行了對比,隨后又進行了顯著性分析與時間復雜度分析.

1 LightGBM系統(tǒng)

LightGBM[5]是由微軟提供的一個迭代提升樹系統(tǒng),它是梯度提升決策樹(GBDT,gradient boosting decision tree)經過改進后的一種變體.經典GBDT一般只采用損失函數(shù)的一階負梯度,而它卻同時使用損失函數(shù)的一二階負梯度計算當前樹的殘差,并以此結果去擬合下一輪的新樹.此外,它還采用了基于Histogram的決策樹算法使得GBDT算法的執(zhí)行可以節(jié)省一半時間,而且其采用最大深度限制的葉子生長策略使得算法的整體執(zhí)行更加具有效率.

1.1 利用直方圖算法構建決策樹模型

相比原始數(shù)據的浮點形式,直方圖數(shù)據占用內存更少、數(shù)據分隔復雜度更低,因而LightGBM處理數(shù)據采用直方圖算法(Histogram算法).

直方圖算法的思想為:將數(shù)據中每列特征值都轉化為一個直方圖,轉化方法是對每個直方圖都按照數(shù)據所在整數(shù)區(qū)間生成k個bin,隨后將連續(xù)的浮點特征值按照所在的整數(shù)區(qū)間放入對應的bin中,以此對每個特征的所有特征值進行轉換,即得到原始數(shù)據的直方圖表示形式.

經過直方圖算法計算后,原始的每個特征都轉換為直方圖,而原始的特征值也以整數(shù)的形式存儲在每個直方圖的所有bin中,因而LightGBM只需遍歷每個直方圖,并將每一直方圖作為分割點計算分割收益,即可尋得最優(yōu)分割直方圖作為分割節(jié)點.在計算中,LightGBM使用了整數(shù)(每個離散值在直方圖中的累計統(tǒng)計量,也就是某一直方圖中某個bin的高度)代替原始數(shù)據的浮點值,這樣有兩個好處:一是起到了正則化的效果來防止樹模型的過擬合,二是可以通過父節(jié)點與子節(jié)點中的一個做差來得到另一個子節(jié)點,從而節(jié)省了一半的計算量.

對于分割點的增益Gain,可定義如下:

(1)

式(1)說明對每一分割點而言,其增益表示為分割后的左、右葉節(jié)點的總權重減去分割前原節(jié)點的權重.

1.2 構建迭代樹

LightGBM算法中的梯度提升決策樹由給定的訓練數(shù)據集多輪迭代得到,并在每一次迭代的時候都會使用梯度信息重新擬合一棵新樹來加入前續(xù)迭代樹,而這在函數(shù)空間上可以視作一種不斷更迭的線性組合過程,形式化描述如下:

(2)

式中:χ是迭代樹的函數(shù)空間;fq(xi)表示第i個樣例在第q棵樹中的預測值.

樹的每一層分裂節(jié)點采用的都是最佳分割點,構建樹模型時實際采用貪心方法.LightGBM通過綜合所有葉子節(jié)點的權重作為構建樹的參照,繼而確定分割點并計算一階梯度和二階梯度.

1.3 特征重要度指標

根據Guyon等的研究[6],迭代樹的啟發(fā)信息可以作為特征的重要衡量標準,因此,基于樹結構的度量將直接影響候選特征子集的質量,也最終決定了原始機器學習算法的實驗效果.

對于任意給定的樹形結構,LightGBM定義了每個特征在迭代樹中被分割的總次數(shù)T_Split及特征在所有決策樹中被用來分割后帶來的增益總和T_Gain作為衡量特征重要性的度量標準,它們的具體定義如下:

(3)

(4)

其中,K為K輪迭代產生的K棵決策樹.

2 LGBFS算法

本文主要采用LightGBM構建迭代樹的過程來計算樣本的特征重要性度量，提出了一種包裹式的特征選擇算法LGBFS.

LGBFS采用一種適應LightGBM做啟發(fā)式的序列浮動前向搜索方法[7]進行特征選擇,并把分類準確率最高的特征集合作為特征選擇的結果.特征選擇問題從本質而言,可分為評估原始特征與搜索特征子集的兩階段算法.因此本文將LGBFS算法拆分為評估原始特征階段與搜索特征子集階段.

2.1 LGBFS評估原始特征

在評價階段開始前,要將其構造為迭代樹模型從而利用樹形結構對特征進行評價,迭代樹是由K輪迭代生成的K棵決策樹分步迭加而成,每棵決策樹生成方式相同,故本處僅給出構建單棵決策樹的偽代碼.

首先,采用直方圖算法將原始轉化為直方圖.在轉換過程中,一個葉子節(jié)點的Histogram可以直接由父節(jié)點和兄弟節(jié)點的Histogram做差得到,稱為差加速,體現(xiàn)在算法2中.隨后,確定分割點時利用一階梯度gi和二階梯度hi進行計算,每次都選取具有最大Gain的特征進行分割并在每層分裂時都貪心選取最佳分割點.

而對于給定的訓練集X,上述步驟具體細節(jié)如算法1和算法2偽代碼所示,其中算法2是算法1的支撐代碼.

觀察上述模型,可以得到結論:一個特征可能被多次分割;特征被分割次數(shù)越多,整棵樹的增益也越多.這兩個結論說明:某些特征應在子集選擇階段被優(yōu)先考慮.

利用DecisionTree算法構建決策樹模型后,可得到上文所描述的某一特征的重要性度量Split和Gain.而利用LightGBM構建整體的迭代提升樹后,可用式(3),(4)算出所有特征的T_Split和T_Gain,就得到了所需的經過樹形結構評價后的原始特征集及重要度集合.

算法 1 DecisionTreeInput: X: training data, C: number of leaf, l: loss function Output:Split, GainT1(X)← X //Put all data on rootfor min(2,C) (Gain,pm,fm,vm)←FindBestSplit(X,Tm-1,l) Tm←Tm-1(X).split(pm,fm,vm) /? Perform split ?/ Split←Split+1end for算法2 FindBestSplitInput: X: training data, Tm-1(X): current model H: histogram data, g: first order gradient, h: second order gradientOutput:pm: leaf on split point, fm: feature of certain dimension, vm: value of maximum gain of fm,Gainfor all Leaf p in Tm-1(X) do for all f in X.Features do H ← new Histogram() for i in usedRows do /?Go through all the data row?/ H[f.bins[i]].g← H[f.bins[i]].g+gi H[f.bins[i]].h← H[f.bins[i]].h+hi end for for iin len(H) do /? Go through all the bins?/ SL←SL+H[i].g hL←hL+H[i].h SR←SP- SL /?Difference acceleration?/ hR←hP-hL Gain←S2L/hL+S2R/hR-S2P/hP if Gain >(pm,fm,vm) then (pm,fm,vm)←(p, f, H[i].value) end if end for end forend for

2.2LGBFS搜索特征子集

在子集搜索階段,首先按照得到的重要度特征索引重新對原始數(shù)據集進行排序,隨后采用一種基于LightGBM重要性度量的序列浮動前向搜索方法LRSFFS對特征子集進行浮動搜索,即每次加入L個特征使得特征子集性能更加優(yōu)異;此外,在每次循環(huán)時也嘗試去除R個特征使得特征子集的性能更加穩(wěn)定優(yōu)異.

LRSFFS搜索策略的優(yōu)勢在于能夠交叉浮動的選擇特征,從而較好避免特征子集陷入局部最優(yōu),而浮動思想也能夠盡可能地兼顧特征之間的相關性,具體偽代碼給出如下.

算法3 LRSFFSInput:S1: feature subset from sorting according to T_Split in descending order, S2 feature subset from sorting according to T_Gain in ascending orderOutput:Y: objective feature setY←?while S1≠? do i, j← 0 while S1≠? do x+← S1.top ifJ(Y+x+)>J(Y)then Y←Y+x+ i← i+1 end if if i==Lthen break end if end while while j≠Rdo x-←S2.top ifJ(Y-x-)>J(Y) then Y←Y-x- j←j+1 end if end whileend while

實驗結果表明,LRSFFS策略能在一定程度上減少這些特征子集搜索問題的局限性,故取得了優(yōu)于其他方法的更好結果,其時間復雜度將在第4章討論.

3 實驗及分析討論

3.1 數(shù)據集與對比算法

本文從UCI[8]數(shù)據庫中選擇了21個數(shù)據集對算法進行測試.表1中列出了這些數(shù)據集的名稱、特征數(shù)和實例數(shù).

表1 數(shù)據集詳細信息

為說明LGBFS算法性能的優(yōu)越性,選擇9種近年來具有代表性的算法(表2)進行對比.

表2 對比算法的詳細信息

3.2 實驗參數(shù)設置及實驗環(huán)境

給出本文所提算法LGBFS與9種對比算法的參數(shù)設置(表3).全部算法均采用30次獨立重復實驗,數(shù)據集劃分方法統(tǒng)一為80%作為訓練集,20%作為測試集.用于驗證特征子集分類性能的分類器為KNN(K近鄰,K=5)分類器, 因為KNN本身實現(xiàn)簡便、穩(wěn)定、參數(shù)少,在特征選擇領域得到了廣泛認可,許多工作[10-11,13-14]僅把KNN作為唯一的基分類器.

表3 實驗參數(shù)設置

LGBFS采用的參數(shù)L,R分為3組,其具體含義為:當數(shù)據集的特征維度小于50時采用第一組參數(shù),特征維度在50至200時采用第二組參數(shù),特征維度大于200時采用第三組參數(shù).此外,所有基于演化學習的特征選擇算法粒子數(shù)設為10,迭代次數(shù)設置為100.

算法的實現(xiàn)環(huán)境為Python語言在PyCharm下的3.7.6版本,使用公開包LightGBM和scikit-learn.計算機配置為:CPU I7-7300K,內存8 GB,硬盤1 TB.

3.3 實驗結果分析與檢驗

為表述實驗結果,使用分類準確率(classification accuracy, CA)、維度縮減率(dimensionality reduction, DR)和CPU時間(CPU time)三種指標用于檢驗特征選擇算法的性能,CA與DR的具體定義如下.

CA=N_CC/N_AS ,

(5)

DR=1-(N_SF/N_AF) .

(6)

式中：N_CC(number of correct classification)為正確的分類數(shù);N_AS(number of all samples)為數(shù)據集的實例數(shù);N_SF(number of selected feature)為選擇的特征數(shù);N_AF(number of all features)為特征總數(shù).

表4,表5給出21個數(shù)據集上LGBFS與9種算法在分類準確率和維度縮減率上的對比結果.最后一行的W,S,L代表所提算法與對比算法勝、平、負的統(tǒng)計量.表6給出CPU運行時間的對比結果.表4～表6中下劃線代表最優(yōu)結果.

表4 LGBFS與9種算法在平均分類準確率上的對比

表5 LGBFS與9種算法在平均維度縮減率上的對比

表6 LGBFS與9種算法在平均CPU時間上的對比

首先,觀察表4的分類準確率結果,LGBFS在16個數(shù)據集的分類準確率均達到最高,而在未達到最高的5個數(shù)據集上相較最優(yōu)結果也未存在明顯差距.因此,可以認定LGBFS在多數(shù)數(shù)據集上效果達到最優(yōu)或次優(yōu).再觀察未能到達最優(yōu)的5個數(shù)據集,可以發(fā)現(xiàn)這5個數(shù)據集均為20維以下的低維數(shù)據集,而LGBFS在構建樹模型時需要構建較深的樹形結構才能平衡掉貪心選取最優(yōu)節(jié)點所帶來的局部最優(yōu)性,因而LGBFS算法更適合處理中高維度,實驗結果也對此進行了驗證.

再對表5的維度縮減率進行觀察,LGBFS在被選中的21個數(shù)據集中的18個數(shù)據集上達到最優(yōu),2個數(shù)據集上達到近似最優(yōu).簡而言之,可以認為LGBFS在近似全部數(shù)據集上有著更高效的維度縮減率.進一步觀察,發(fā)現(xiàn)在維度超過100的高維數(shù)據集上,LGBFS相對其他算法總能在滿足較高的維度縮減率的前提下獲得同樣較高的分類準確率,這也再次說明利用LightGBM評估特征的合理性和有效性,充分印證了LGBFS能夠通過特征之間的內在關聯(lián)找到更相關的特征并進行維度縮減,而并非僅以分類準確率的提高作為算法運行的第一要義.

隨后對表6的CPU運行時間進行觀察,可以發(fā)現(xiàn)LGBFS雖然是包裹式的特征選擇算法,卻并未像基于演化學習的特征選擇算法需要復雜的計算量和較長的計算時間,而這是由LGBFS設計理念的完整性和設計結構的精簡性所決定的.LGBFS力求在演化式包裹特征選擇算法和過濾式算法中做出平衡,既希望能夠得到具有優(yōu)秀分類性能的特征子集,又希望能夠用較少的計算時間和較小的計算量完成特征選擇這一階段的任務,從表6中可以看出,LGBFS在全部數(shù)據集上的運行時間都遠優(yōu)于傳統(tǒng)的演化特征選擇算法.粗略計算,LGBFS比每種演化包裹式特征選擇算法快100倍以上,即使與公認計算效率最優(yōu)的過濾式算法相比,LGBFS在大部分數(shù)據集的CPU運行時間指標依然處于平手,甚至在個別數(shù)據集上超過了過濾式的JMI和MIM算法的運行時間.LGBFS出色地在特征選擇的計算量和特征子集的最優(yōu)性間做出了平衡.

最后,為定量討論LGBFS算法相較對比算法的有效性與顯著性,本文采用了非參數(shù)的威爾森秩和檢驗[17](Wilcoxon rank-sum test)來確認9種對比算法與LGBFS是否有統(tǒng)計學上的差異(顯著性水平設置為0.05),威爾森秩和檢驗定義如式(7)所示:

(7)

其中:CA為分類準確率;M為所使用數(shù)據集的數(shù)量;i代表21個數(shù)據集中第i個數(shù)據集;j表示9種對比算法中第j個算法;k代表30次獨立重復實驗的第k次實驗;Wjk代表第j個對比算法相較LGBFS在第k次實驗在全部數(shù)據集上的威爾森秩和檢驗結果.

9種對比算法的檢驗結果于表7給出.其中6種算法相較LGBFS的p值小于或近似等于0.05,這在統(tǒng)計學上表示測試拒絕默認值5%顯著性水平下的中位數(shù)相等的零假設,證明了無論初始解決方案和整個搜索過程中采用的隨機決策如何,LGBFS總能夠找到相較其他6種算法更優(yōu)異的特征子集.

通過威爾森秩和檢驗,既定性地分析了LGBFS的準確性與高效性,又定量地驗證了LGBFS顯著性與有效性.

表7 LGBFS相較9種算法在分類準確率上的威爾森檢驗結果

4 時間復雜度分析

分析算法LGBFS的時間復雜度,對數(shù)據集給定如下假設:給定無缺失值的具有N個樣本、M個特征的數(shù)據集X,設D為樹模型最大樹深、T為決策樹的棵數(shù)且非零重要性特征的比例為β,則m=βM,對于數(shù)據處理階段的直方圖算法,每一特征的N個特征值被分配進k個bin中(k?N),則直方圖算法時間掃描數(shù)據的復雜度為O(kM).

得到每個特征對應的直方圖后,樹節(jié)點的分裂對應直方圖的分裂,在遍歷每層特征的直方圖后就確定了最佳分割點,時間復雜度仍為O(kM),對于建立最大深度為D、數(shù)量為T的迭代樹模型的總計時間復雜度為O(kMDT).采用快速排序對度量后的子集排序時間復雜度為O(mlogm).

最后考慮搜索策略LRSFFS算法,由于L,R均為常數(shù),故向項添加與后向去除的時間復雜度均為O(m),而浮動的過程導致迭代的前向交叉浮動,所以浮動算法時間復雜度為O(m2×KNN),而KNN的時間復雜度可近似表示為O(mNlogN),所以LRSFFS的總時間復雜度為O(m3NlogN).

故LGBFS算法總時間復雜度可近似表示為O(kM+mlogm+kMDT+m3NlogN).

5 結 語

本文提出了基于LightGBM的包裹式特征選擇算法LGBFS,該算法利用樹形信息度量特征集合,提出一種新型的序列浮動前向選擇策略用于特征選擇.經過21個數(shù)據集和9種特征選擇算法的對比實驗,驗證了LGBFS算法的良好性能,對L與R參數(shù)的自適應化將是下一步的研究內容.