基于Catboost的特征選擇算法

王 麗，王 濤，肖 巍，潘 超

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林 長(zhǎng)春 130012)

0 引 言

特征選擇是機(jī)器學(xué)習(xí)中的一個(gè)重要步驟，并廣泛應(yīng)用于各領(lǐng)域，在訓(xùn)練模型過程中，不相關(guān)的特征會(huì)干擾模型學(xué)習(xí)的正確性，而冗余的特征不會(huì)提供任何有用的信息，反而增加模型的復(fù)雜性。特征選擇的任務(wù)是從高維原始特征空間中選出一組有效的特征子集[1]。特征選擇方法通過搜索相關(guān)特征并移除不相關(guān)特征來尋找最優(yōu)特征子集，提高模型的處理性能，減少處理數(shù)據(jù)維度[2]。

特征選擇方法分為對(duì)特征重要性進(jìn)行排序和選擇特征子集兩種[3]。前者是根據(jù)一些測(cè)量標(biāo)準(zhǔn)對(duì)特征進(jìn)行排序，并相應(yīng)地選擇排在頂部的特征；后者使用評(píng)價(jià)指標(biāo)對(duì)特征子集進(jìn)行評(píng)價(jià)，并篩選關(guān)鍵特征。兩種方法都可以使用基于過濾式或包裹式方法進(jìn)行選擇[4]。在過濾式特征選擇中，使用一定的評(píng)價(jià)指標(biāo)評(píng)估每個(gè)特征的質(zhì)量，不考慮它對(duì)結(jié)果產(chǎn)生的影響。包裹式的特征選擇則根據(jù)一個(gè)或一組分類器的結(jié)果來衡量每個(gè)特征的影響，與過濾式方法相比，包裹式方法的計(jì)算密度更高，在預(yù)測(cè)結(jié)果方面更準(zhǔn)確。但過濾式方法計(jì)算更快，結(jié)果準(zhǔn)確性稍遜色于包裹式方法[5]。

一部分學(xué)者將特征選擇劃分出嵌入式方法，嵌入式方法將特征選擇過程與學(xué)習(xí)器訓(xùn)練過程融為一體，兩者在同一個(gè)優(yōu)化過程中完成，即在學(xué)習(xí)器訓(xùn)練過程中自動(dòng)地進(jìn)行特征選擇[6]。

盡管在計(jì)算開銷上嵌入式方法要比包裹式方法小，但在速度上仍然要比過濾式方法慢很多，并且特征選擇的效果很大程度上依賴所選擇的學(xué)習(xí)器[7]。

集成學(xué)習(xí)是解決機(jī)器學(xué)習(xí)問題的重要方法之一，集成學(xué)習(xí)的主要策略是將弱學(xué)習(xí)器集成為一個(gè)強(qiáng)學(xué)習(xí)器，在輸入一組標(biāo)記樣本到弱學(xué)習(xí)器后，通過生成的模型為新的未標(biāo)記樣本做出預(yù)測(cè)。其中，弱分類器可以是任何類型的機(jī)器學(xué)習(xí)算法，例如決策樹、線性回歸模型等[8]。集成學(xué)習(xí)在組合多個(gè)學(xué)習(xí)器過程中，單個(gè)學(xué)習(xí)器的誤差可能會(huì)被其它學(xué)習(xí)器補(bǔ)償，因此，模型整體的預(yù)測(cè)性能將優(yōu)于單個(gè)學(xué)習(xí)器的預(yù)測(cè)性能。集成學(xué)習(xí)能夠更好地解決特征選擇問題，如Hakan等[9]提出的分類器集成方法應(yīng)用于特征選擇;Martin等[10]提出的使用應(yīng)用過濾器集成解決多目標(biāo)參數(shù)調(diào)整和特征選擇問題;Omar等[11]提出的基于關(guān)聯(lián)度、冗余度和依賴度準(zhǔn)則的集成模糊特征選擇;Ebrahimpour等[12]集成了分級(jí)算法和相似性度量?jī)煞N過濾式方法對(duì)微陣列數(shù)據(jù)集進(jìn)行特征選擇。

Catboost是Dorogush等[13]最近提出的一種新的集成學(xué)習(xí)算法，具有獨(dú)特的對(duì)稱樹結(jié)構(gòu)，通過計(jì)算葉子節(jié)點(diǎn)的值來構(gòu)造決策樹，在此過程中，Catboost對(duì)特征進(jìn)行了量化的度量。

利用基于Catboost樹模型的特點(diǎn)，以其對(duì)特征的重要性排序作為啟發(fā)式策略，與搜索策略相結(jié)合，提出一種新型的特征選擇方法CABFS。以Catboost為基本工具，完成以下工作：

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

2)提出了基于2種重要性度量的搜索策略;

3)提出了一個(gè)新特征選擇方法CABFS;

4)通過實(shí)驗(yàn)對(duì)CABFS的性能做了全面分析與驗(yàn)證。

1 背景知識(shí)

1.1 特征選擇

特征選擇問題旨在從原始特征集合中選擇能提供更多有效信息的特征，同時(shí)去除掉不相關(guān)特征以及冗余特征。

因此，可以使用二進(jìn)制來表示特征問題中的解決方案。在這種條件下，解決方案中的每個(gè)維度采用 1(選定)或 0(未選中)來表示在原始特征集合中選擇或不選擇相應(yīng)的特征。特征選擇過程可以表示為

(1)

式中：γR(D)----分類器的分類誤差率;

|R|----選擇的特征數(shù)量;

|N|----原始特征選擇集合中的特征數(shù)量;

α----分類誤差率的權(quán)重，α∈[0,1]；

β----特征子集中選出特征比例的權(quán)重,β=(1-α)。

1.2 Catboost

Catboost是一種新型的梯度提升算法，它是以決策樹作為基本學(xué)習(xí)器的集成算法，不同于其它梯度提升算法，Catboost采用對(duì)稱樹的結(jié)構(gòu)，在樹的整個(gè)層次上使用相同的分割標(biāo)準(zhǔn)，這樣的樹是平衡的，并且加快了訓(xùn)練時(shí)間。Catboost的建樹過程中，每棵樹都是基于上一棵樹的殘差建立的。

Catboost可表示為

(2)

式中：FT----由多個(gè)弱學(xué)習(xí)器集成的強(qiáng)學(xué)習(xí)器;

ft----一棵決策樹，下一棵樹在現(xiàn)有樹的基礎(chǔ)上順序構(gòu)造而成。

損失函數(shù)為

(3)

式中:l(f(xi),yi)----樣本點(diǎn)(xi,yi)的損失;

wi----第i個(gè)目標(biāo)的權(quán)重;

J(f)----正則化項(xiàng)。

Catboost使用前一棵樹的預(yù)測(cè)結(jié)果來訓(xùn)練下一棵樹，這個(gè)迭代過程使最終的預(yù)測(cè)結(jié)果更為準(zhǔn)確，模型更具有魯棒性。同時(shí)，Catboost提供了獨(dú)特的特征重要性計(jì)算方式，為Catboost能夠被用來做特征選擇問題的啟發(fā)式策略提供了重要依據(jù)。

2 CABFS算法描述

2.1 特征評(píng)價(jià)策略

重要性度量指標(biāo)是評(píng)估每個(gè)特征在所屬特征集中重要程度的一種衡量指標(biāo)。Catboost提供了多種重要性度量指標(biāo)。其中，預(yù)測(cè)值改變量(Prediction Values Change，PVC)顯示特征值更改時(shí)預(yù)測(cè)值的平均變化程度，特征越重要,則預(yù)測(cè)值平均值的變化率越大。損失函數(shù)變化(Loss Function Change，LFC)描述當(dāng)模型中有此特征與沒有此特征時(shí)損失函數(shù)的變化，其變化量越大，則該特征越重要。故對(duì)確定結(jié)構(gòu)的樹模型有：

(v2-avr)2·leafright,

(4)

(5)

式中：leafleft,leafright----分別表示左葉子和右葉子的權(quán)重；

v1，v2----分別表示左葉子和右葉子的目標(biāo)函數(shù)值。

LFCi=l(exi)-l(features),

(6)

式中：l(exi)----不包含特征i時(shí)模型的損失函數(shù)值;

l(features)----使用全部特征時(shí)模型的損失函數(shù)值。

2.2 特征選擇過程

CABFS特征選擇過程包含兩個(gè)步驟：構(gòu)造Catboost中的樹模型和特征子集搜索策略。在構(gòu)建樹結(jié)構(gòu)前，為了防止過擬合，每棵樹的權(quán)重會(huì)隨著選擇不同的分割或不同的樹而變化。在訓(xùn)練過程中，CABFS會(huì)連續(xù)構(gòu)造一組樹，每棵樹會(huì)基于前一棵樹的基礎(chǔ)上，減少損失進(jìn)行構(gòu)建。構(gòu)建一棵樹分為兩個(gè)階段：選擇樹結(jié)構(gòu)，得到多種樹結(jié)構(gòu)后,計(jì)算葉子節(jié)點(diǎn)的值。為了選擇最佳的樹結(jié)構(gòu)，算法貪婪按順序選擇特征作為分割，并用這些分割構(gòu)建一棵新樹。重復(fù)以上過程，構(gòu)建集成模型，依據(jù)2.1中的重要性度量指標(biāo)對(duì)特征進(jìn)行評(píng)分，生成新的特征重要性評(píng)價(jià)排名集合。

CABFS特征選擇過程采用加權(quán)前向搜索策略進(jìn)行實(shí)現(xiàn)，即在傳統(tǒng)前向搜索的基礎(chǔ)上進(jìn)行改進(jìn)，對(duì)特征的兩個(gè)度量指標(biāo)PVC與LFC賦予相應(yīng)的權(quán)重進(jìn)行搜索，兩個(gè)指標(biāo)分別代表特征變化時(shí)預(yù)測(cè)值的改變量以及有無第i個(gè)特征時(shí)損失函數(shù)的變化量。在不同應(yīng)用場(chǎng)景下，面對(duì)不同的特征選擇需求時(shí)，可以賦予兩個(gè)指標(biāo)不同的權(quán)重來進(jìn)行側(cè)重的衡量。文中實(shí)驗(yàn)?zāi)康氖桥c其他已有的特征選擇算法進(jìn)行比較，不涉及特殊應(yīng)用場(chǎng)景，故將兩個(gè)指標(biāo)都賦予了相同的權(quán)重便于比較。

具體搜索過程操作如下：設(shè)置一個(gè)起始元素為空的特征集合S，根據(jù)PVC與LFC加權(quán)后得到的綜合評(píng)價(jià)指標(biāo)對(duì)候選特征子集進(jìn)行搜索，將搜索到的特征依次添加到集合S中，目標(biāo)是當(dāng)加入該特征后提高目標(biāo)集合的適應(yīng)度值。

2.3 偽代碼

CABFS偽代碼

輸入：原始特征集合 O

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

步驟：

1:T ← ?; depth ← 0

2:建立根節(jié)點(diǎn)

3:while depth < 樹的最大深度 do

4: for each s ∈ O do

5: 計(jì)算最佳特征分割點(diǎn)并為最佳分割點(diǎn)建立孩子節(jié)點(diǎn)

6: end for

7: depth ← depth + 1

8:end while

9:根據(jù)式(2)將生成的樹集成為統(tǒng)一的模型C

10:依據(jù)式(4)和(6)從C中生成重要性指標(biāo)PVC和LFC

11:將PVC和LFC中相同特征對(duì)應(yīng)的評(píng)價(jià)結(jié)果進(jìn)行加權(quán)求和并排序，生成新的特征重要性評(píng)價(jià)排名集合I

12:定義最初的特征子集評(píng)價(jià)結(jié)果F(T) ← 0

13:for i in I do

14: T′← T∪i

15: 計(jì)算新的特征子集評(píng)價(jià)結(jié)果F(T′)

16: if F(T′)> F(T)

17: T←T′

18: F(T) ← F(T′)

19:end for

20:return T

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

3.1 實(shí)驗(yàn)數(shù)據(jù)與對(duì)比算法

使用UCI數(shù)據(jù)集中的一些經(jīng)典數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)，詳細(xì)信息見表1。

表1 UCI數(shù)據(jù)集 個(gè)

實(shí)驗(yàn)采用一些近年來具有代表性的特征選擇算法與CABFS進(jìn)行對(duì)比，見表2。

表2 對(duì)比算法

3.2 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)采用特征分類準(zhǔn)確率CA(Classification Accuracy)以及特征維度縮減率FR(Feature Reduction)對(duì)特征選擇的效果進(jìn)行評(píng)價(jià)，

(7)

(8)

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

CABFS及其對(duì)比算法在Glass、Spambase、Vehicle、Waveform、Wine、Wisconsin、Yeast上的結(jié)果分別見表3～表9。

表3 CABFS及其對(duì)比算法在Glass上的結(jié)果 %

表4 CABFS及其對(duì)比算法在Spambase上的結(jié)果 %

表5 CABFS及其對(duì)比算法在Vehicle上的結(jié)果 %

表6 CABFS及其對(duì)比算法在Waveform上的結(jié)果 %

表7 CABFS及其對(duì)比算法在Wine上的結(jié)果 %

表8 CABFS及其對(duì)比算法在Wisconsin上的結(jié)果 %

表9 CABFS及其對(duì)比算法在Yeast上的結(jié)果 %

通過表3～表9可以看到，CABFS在Glass、Spambase、Waveform、Wisconsin、Yeast這5個(gè)數(shù)據(jù)上的分類準(zhǔn)確率均達(dá)到了最高，說明CABFS在一定程度上能夠很好地確保分類準(zhǔn)確率，而針對(duì)以上數(shù)據(jù)集的維度縮減率而言，CABFS僅在Spambase上達(dá)到了最優(yōu)，另外幾個(gè)數(shù)據(jù)集上的排名均在居中位置，這說明CABFS在追求分類準(zhǔn)確率的同時(shí)，并沒有完全的犧牲維度縮減率，而是一定程度上做到了兼顧，但是還無法保證兩個(gè)衡量標(biāo)準(zhǔn)均達(dá)到最優(yōu)的表現(xiàn)。

綜合7個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析發(fā)現(xiàn)，大多數(shù)數(shù)據(jù)集的準(zhǔn)確率都能在分類準(zhǔn)確率或維度縮減率達(dá)到最優(yōu)，只有Vehicle 數(shù)據(jù)集上的結(jié)果沒有達(dá)到最優(yōu)。之所以有這種情況，是因?yàn)镃ABFS算法應(yīng)用于Vehicle 數(shù)據(jù)集上在建樹時(shí)分割特征的過程中無法獲得最優(yōu)的分割點(diǎn)導(dǎo)致的，但在維度縮減率上能排在第2位置，能夠說明CABFS對(duì)于降低數(shù)據(jù)維度方面相對(duì)其他對(duì)比算法而言，具有較好的效果。

4 結(jié) 語

CABFS將Catboost中構(gòu)建樹模型過程中的分割指標(biāo)作為特征選擇中度量特征重要性的標(biāo)準(zhǔn)，在傳統(tǒng)前向搜索中對(duì)兩種度量賦予了權(quán)值，并通過綜合計(jì)算來進(jìn)行搜索，實(shí)驗(yàn)結(jié)果證明，CABFS采用特征重要性度量作為啟發(fā)式的策略是有效的，但在保證分類準(zhǔn)確率結(jié)果好的情況下，如何進(jìn)一步提高維度縮減率，仍需要更進(jìn)一步的深入研究，并加以改進(jìn)。