基于特征貢獻(xiàn)度與線性搜索的特征選擇方法

郭文斌，丘康平，蔡惠坤

（1.廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣州510006；2.廣州廣日電梯工業(yè)有限公司，廣州511447；3.中移互聯(lián)網(wǎng)有限公司，廣州510640）

0 引言

隨著大數(shù)據(jù)時(shí)代來臨，互聯(lián)網(wǎng)、工業(yè)和制造等行業(yè)積累了大量的數(shù)據(jù)，基于數(shù)據(jù)驅(qū)動(dòng)業(yè)務(wù)的研究成為國(guó)內(nèi)外研究的熱點(diǎn)方向。各種形式的數(shù)據(jù)處理技術(shù)的出現(xiàn)，使得數(shù)據(jù)挖掘和數(shù)據(jù)分析等效率更高，利用能被用于數(shù)據(jù)分析或者機(jī)器學(xué)習(xí)建模的數(shù)據(jù)往往特征空間龐大而且復(fù)雜，面對(duì)高維且特征空間巨大的數(shù)據(jù)，去除特征冗余，降低數(shù)據(jù)維度，提高建模計(jì)算空間，節(jié)省計(jì)算性能將成為數(shù)據(jù)處理相關(guān)的難題之一。在回歸問題中，高維數(shù)據(jù)特征與目標(biāo)特征之間往往呈現(xiàn)非線性的關(guān)系，數(shù)據(jù)特征空間中隱含的對(duì)目標(biāo)結(jié)果不相關(guān)或者冗余的數(shù)據(jù)特征會(huì)影響數(shù)據(jù)建模的性能以及準(zhǔn)確性，快速且有效的特征選擇方法有助于簡(jiǎn)化學(xué)習(xí)模型學(xué)習(xí)空間。本文將某特種設(shè)備相關(guān)的高維預(yù)處理數(shù)據(jù)作為研究對(duì)象，使用基于特征參數(shù)的貢獻(xiàn)度分析，結(jié)合參數(shù)的貢獻(xiàn)度排序與分布，進(jìn)行線性搜索，實(shí)現(xiàn)搜索路徑上的最優(yōu)解，并消除冗余特征，提高建模性能。

1 研究現(xiàn)狀分析

特征選擇問題最早于20世紀(jì)60年代被提出，最初用于研究統(tǒng)計(jì)學(xué)和信號(hào)處理領(lǐng)域，后逐步將特征選擇延伸至機(jī)器學(xué)習(xí)、模式識(shí)別等領(lǐng)域[1]。按照特征選擇和機(jī)器學(xué)習(xí)器的結(jié)合方式不同，可以將特征選擇方式分為四種，分別為過濾式[2]、封裝式[3]、嵌入式[4]和集成式，按照特征選擇的搜索策略，可以分為全局最優(yōu)搜索、隨機(jī)搜索和啟發(fā)式搜索等算法[5-6]。

基于特征排序是一種重要的特征選擇方法，特征排序的評(píng)價(jià)標(biāo)準(zhǔn)有多種，可以分為L(zhǎng)aplacian得分、Constraint得分、Fisher得分、Person相關(guān)系數(shù)等。傳統(tǒng)特征搜索算法，采用窮舉算法隨著特征維度升高，特征子集的數(shù)目呈指數(shù)級(jí)增長(zhǎng)，幾乎不可能實(shí)現(xiàn)。基于特征排序，李光華等人提出了一種融合蟻群算法和隨機(jī)森林的特征選擇方法[7]，武煒杰等人提出了三種隨機(jī)森林多特征置換算法進(jìn)行特征選擇，但是此算法研究都針對(duì)分類領(lǐng)域的特征選擇[8]。在特征選擇相關(guān)的研究中，已經(jīng)吸引了許多的研究學(xué)者在從事相關(guān)的研究工作，并綜合了諸多算法與實(shí)現(xiàn)流程，發(fā)展近幾十載，國(guó)內(nèi)外相關(guān)文獻(xiàn)已經(jīng)有了近幾千篇之多，但是諸多研究學(xué)者仍然不遺余力地進(jìn)行相關(guān)地研究，其目標(biāo)之一便是使用簡(jiǎn)單高效的方式實(shí)現(xiàn)特征選擇的最優(yōu)子集以便精簡(jiǎn)算法模型。

本文基于線性搜索的方法，與全局搜索策略不同，線性搜索具有更小的搜索空間；與隨機(jī)搜索不同，隨機(jī)搜索自定義搜索閾值可能使得特征子集仍然存在冗余。

2 相關(guān)理論

2.1 特征選擇框架

特征選擇的任務(wù)是從特征數(shù)據(jù)集中選擇最有利于數(shù)據(jù)建模的子特征數(shù)據(jù)集，按照傳統(tǒng)數(shù)據(jù)特征框架，該框架包含四個(gè)基本過程，如圖1所示，主要為生產(chǎn)特征子集、評(píng)價(jià)特征子集、停止條件和驗(yàn)證結(jié)果[9]。

圖1 傳統(tǒng)的特征選擇框架

2.2 特征排序計(jì)算方法

2.2.1 XGBoost算法

XGBoost（eXtreme Gradient Boosting）[10]是極端梯度提升樹算法的簡(jiǎn)稱，是基于GBDT算法上的改進(jìn)，是基于弱學(xué)習(xí)器加權(quán)疊加形成強(qiáng)學(xué)習(xí)器的集成學(xué)習(xí)算法。XGBoost是結(jié)合了決策樹、集成學(xué)習(xí)、廣義加法模型、牛頓法等多種基礎(chǔ)知識(shí)的算法，并在損失函數(shù)、正則化、切分查找算法、稀疏感知算法、并行化算法設(shè)計(jì)等多方面進(jìn)行了改進(jìn)，比較適合解決抽象數(shù)據(jù)分析方面的問題，在Kaggle比賽中也受到諸多青睞。

（1）定義目標(biāo)函數(shù)：

其中，n為訓(xùn)練樣本，l為但樣本損失,為預(yù)測(cè)值，yi為真實(shí)值，φ為模型參數(shù)，γ和λ為人工設(shè)定系數(shù)，w為葉子節(jié)點(diǎn)向量，T為葉子節(jié)點(diǎn)數(shù)，fk為映射函數(shù)。

（2）訓(xùn)練目標(biāo)函數(shù)：yi、是常數(shù)，+ft(Xi)是損失函數(shù)的自變量。

（3）將目標(biāo)函數(shù)按泰勒二階展開：

其中，gi為損失函數(shù)的一階導(dǎo)數(shù)：

hi為損失函數(shù)的二階導(dǎo)數(shù)：

（4）去掉與ft(Xi)無關(guān)常數(shù)項(xiàng)：

（5）求出最優(yōu)解：

（6）算法偽代碼，如圖2所示。

圖2 XGBoost算法流程

2.2.2特征貢獻(xiàn)度度量

貢獻(xiàn)度即重要度，是衡量數(shù)據(jù)特征中每個(gè)特征對(duì)于目標(biāo)特征的影響程度的評(píng)價(jià)指標(biāo)。在XGBoost算法中，有三種全局特征的貢獻(xiàn)度歸因方法。三種貢獻(xiàn)度算法是基于決策樹的每次分割采用貪婪方式進(jìn)行，即選擇信息增益最大的特征用于樹的分裂點(diǎn)。信息增益的計(jì)算方式如下：

（1）Weight。表示權(quán)重形式，指在所有樹中，一個(gè)特征在分裂節(jié)點(diǎn)時(shí)被使用的次數(shù)。若一個(gè)特征作為分裂特征的次數(shù)越多，表明這個(gè)特征對(duì)于目標(biāo)特征越重要。

（2）Cover。表示平均增益形式，指在所有樹中，一個(gè)特征作為分裂節(jié)點(diǎn)存在時(shí)，帶來的增益的平均值。

（3）Gain。表示平均覆蓋度，指在所有樹中，一個(gè)特征作為分裂節(jié)點(diǎn)存在時(shí)，覆蓋的樣本數(shù)據(jù)量的平均值。

2.3 線性搜索算法

線性搜索算法是在搜索空間下按照順序搜索的方式尋找目標(biāo)的最優(yōu)值的算法，其搜索的次數(shù)一般為搜索空間的大小，當(dāng)找到最優(yōu)值或者達(dá)到搜索空間的尾端搜索步驟停止。

3 特征貢獻(xiàn)度分析與特征選擇

3.1 基于線性搜索的特征選擇

結(jié)合特征貢獻(xiàn)度的線性搜索算法的實(shí)現(xiàn)步驟如圖3所示。

圖3 算法流程圖

（1）選用gain指數(shù)作為指標(biāo)，按照XGBoost算法對(duì)數(shù)據(jù)進(jìn)行特征貢獻(xiàn)度分析，并對(duì)高維的數(shù)據(jù)按照得分進(jìn)行特征排序。

（2）初始化搜索次數(shù)K=0，選用特征排序的得分最低點(diǎn)作為搜索起點(diǎn)。

（3）選用搜索空間位置的前向作為特征子集，并計(jì)算該子集的模型評(píng)價(jià)指標(biāo)值。

（4）比較輸出最優(yōu)子集。

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

在特征選擇的回歸數(shù)據(jù)子集中，衡量子集在數(shù)據(jù)模型上的表現(xiàn)好壞需要對(duì)子集建模的效果做出評(píng)價(jià)，決定系數(shù)將是很好的衡量指標(biāo)。決定系數(shù)是反映預(yù)測(cè)目標(biāo)的變異中可以通過自變量解釋的所占的比例，它能夠評(píng)判回歸模型對(duì)于該數(shù)據(jù)的解釋能力，其值越大說明自變量對(duì)因變量的解釋程度越高，模型的表達(dá)能力越好，進(jìn)而可以說明在該數(shù)據(jù)特征的子集下建模的效果越好。其公式如下：

定義一組數(shù)據(jù)集中包含y1,…,yn一共包含n個(gè)觀察值，該同等觀察值的參數(shù)下的模型預(yù)測(cè)值為f1,…,fn。

平均觀察值：

總平方和：

回歸平方和：

殘差平方和：

決定系數(shù)：

4 案例分析與討論

實(shí)驗(yàn)數(shù)據(jù)采用來自電梯設(shè)備相關(guān)的報(bào)價(jià)數(shù)據(jù)，其數(shù)據(jù)特征包含維度較低和維度較高的編號(hào)為NUM01、NUM02、NUM03三種設(shè)備型號(hào)的數(shù)據(jù)，該數(shù)據(jù)經(jīng)過數(shù)據(jù)預(yù)處理的基本過程，使得數(shù)據(jù)能夠直接利用在數(shù)據(jù)建模、數(shù)據(jù)分析和決策之中。實(shí)驗(yàn)數(shù)據(jù)描述如表1所示。

表1 測(cè)試數(shù)據(jù)描述

本次實(shí)驗(yàn)環(huán)境為采用統(tǒng)一的計(jì)算硬件環(huán)境和性能配置，并且使用統(tǒng)一的神經(jīng)網(wǎng)絡(luò)模型作為評(píng)價(jià)指標(biāo)的計(jì)算工具，分別對(duì)三組數(shù)據(jù)進(jìn)行測(cè)試與比較。其結(jié)果如圖4-圖6所示。

圖4 NUM01實(shí)驗(yàn)結(jié)果

圖5 NUM02實(shí)驗(yàn)結(jié)果

圖6 NUM03實(shí)驗(yàn)結(jié)果

本次實(shí)驗(yàn)除了使用決定系數(shù)作為評(píng)價(jià)指標(biāo)，還引入了MAE作為參考指標(biāo)，方便對(duì)特征選擇的搜索位置做出更精確定位，由圖4-圖6中，每個(gè)實(shí)驗(yàn)結(jié)果圖中分別展示了兩種顏色區(qū)分的折線圖，紅色折線圖為在本文實(shí)現(xiàn)的算法中隨著搜索路線中的搜索步長(zhǎng)的遞增，決策系數(shù)指標(biāo)值的變化，藍(lán)色折線圖為隨著搜索路線中的搜索補(bǔ)償?shù)倪f增，該搜索子集下的數(shù)據(jù)建模的損失值（Loss）。

在圖4-圖6的三個(gè)實(shí)驗(yàn)結(jié)果中，可以觀察到隨著搜索步數(shù)的不斷增加，決定系數(shù)的值有平穩(wěn)上升的趨勢(shì)，說明冗余去除對(duì)模型的解釋能力有所提升，同時(shí)MAE的值平穩(wěn)下降，說明去除了冗余特征對(duì)總體數(shù)據(jù)的精確度有所提升。在決定系數(shù)上升到某個(gè)位置時(shí)，后續(xù)數(shù)據(jù)呈現(xiàn)震蕩下降和不穩(wěn)定的情況，說明去除了某些重要的特征之后，數(shù)據(jù)的解釋能力忽然變差，模型不穩(wěn)定因素變高。

5 結(jié)語

在數(shù)據(jù)驅(qū)動(dòng)的時(shí)代，算法模型等分析和建模工具能夠輔助科研工作者等做出快速的分析和決策，但是基于數(shù)據(jù)的處理始終是個(gè)棘手的難題，高維數(shù)據(jù)不僅增加了計(jì)算成本，增加了模型的復(fù)雜度，增加了計(jì)算空間，在次基礎(chǔ)上，本文通過線性搜索的方式與特征貢獻(xiàn)度結(jié)合，提出與分析了數(shù)據(jù)特征的選擇方法，實(shí)驗(yàn)表明，可以縮減搜索空間的條件下找到搜索區(qū)域的較優(yōu)子集，該方法對(duì)特征選擇具有一定的參考價(jià)值。但是特征之間的關(guān)聯(lián)度、特征編碼方式的差異，以及特征降維之后該方法是否能夠達(dá)到同樣的效果還尚待挖掘。