改進(jìn)的GDBT迭代決策樹分類算法及其應(yīng)用

曹穎超

【摘 要】傳統(tǒng)的決策樹分類方法有ID3和C4.5，由于單棵決策樹的局限性，在訓(xùn)練數(shù)據(jù)過程中由于屬性值的過多容易出現(xiàn)過擬合現(xiàn)象，本文研究使用多顆決策樹和Boosting算法結(jié)合在一起的GDBT分類方法。GDBT算法是基于回歸的思想，對復(fù)雜數(shù)據(jù)有較強(qiáng)的處理能力，且它是由多棵樹組成的，構(gòu)造樹不復(fù)雜，每次用殘差進(jìn)行調(diào)整，保證分類的精確。

【關(guān)鍵詞】分類算法；決策樹；GBDT

0 引言

決策樹分類方法是一種自上而下，在分支節(jié)點(diǎn)進(jìn)行屬性值的比較得到分裂點(diǎn)屬性，根據(jù)不同的屬性值判斷構(gòu)造向下的分支，最終在葉子節(jié)點(diǎn)得到分類結(jié)果。傳統(tǒng)的決策樹分類方法有ID3和C4.5，他們都是以信息熵作為分類依據(jù)，是單顆決策樹。然而，由于單棵決策樹的局限性，在訓(xùn)練數(shù)據(jù)過程中由于屬性值的過多容易出現(xiàn)過擬合（Over-Fitting）現(xiàn)象。為了彌補(bǔ)單棵決策樹的缺陷，本研究使用多顆決策樹和Boosting算法結(jié)合在一起的GDBT分類方法。

1 改進(jìn)的決策樹分類算法

1.1 Boosting方法

Boosting方法其實(shí)是一個(gè)框架，是用來提升算法準(zhǔn)確度的，可以將其他算法放到boosting框架里面，boosting方法通過構(gòu)造一系列的預(yù)測函數(shù)然后將它們合并形成一個(gè)最終的預(yù)測函數(shù)。Boosting方法主要是通過操作樣本集獲得一些子集，然后用弱分類算法去訓(xùn)練樣本子集來生成一系列基分類器。每得到一個(gè)樣本集就用該基分類算法在該樣本集上產(chǎn)生一個(gè)基分類器，這樣迭代N次后，就可以得到N個(gè)基分類器，然后運(yùn)用Boosting框架將這 N個(gè)基分類器賦予不同的權(quán)值融合在一起合，產(chǎn)生一個(gè)最終的結(jié)果分類器，在這 N個(gè)基分類器中，每個(gè)單獨(dú)的基分類器識別度不同，也許有的基分類器識別率很低，但是當(dāng)他們加權(quán)融合在一起生成的最終結(jié)果分類器識別率就很高，這樣就提高了算法的識別率或者準(zhǔn)確度。

1.2 隨機(jī)森林

隨機(jī)森林這個(gè)術(shù)語最早由1995年由貝爾實(shí)驗(yàn)室的Tin Kam Ho所提出的隨機(jī)決策森林（random decision forests）而來的，后來是結(jié)合 Breimans 的“Bootstrap aggregating”想法和 Ho 的“random subspace method”以建造決策樹的集合，就形成了隨機(jī)森林算法。

隨機(jī)森林算法運(yùn)用重采樣技術(shù)，從原始訓(xùn)練樣本集中有放回地重復(fù)隨機(jī)抽取N個(gè)樣本形成樣本子集，然后根據(jù)N個(gè)樣本子集生成N決策樹，當(dāng)輸入測試數(shù)據(jù)時(shí)，在每一顆決策樹上進(jìn)行判斷，得到分類結(jié)果，最后統(tǒng)計(jì)哪一個(gè)分類選擇最多，就預(yù)測這個(gè)測試樣本屬于哪一個(gè)分類。隨機(jī)森林算法能處理很高維度的數(shù)據(jù)，并且不用做特征選擇，有很多顆決策樹，不會對數(shù)據(jù)過度擬合，抗噪聲能力強(qiáng)。缺點(diǎn)就是一個(gè)測試樣本在每一顆樹上都要判斷，計(jì)算過于復(fù)雜，對線性數(shù)據(jù)不敏感，且對算法的準(zhǔn)確度沒有過多的提升。

1.3 GBDT算法

1.3.1 GDBT 思想與原理

不同于隨機(jī)森林，GBDT 是決策樹與 Boosting 方法相結(jié)合的應(yīng)用。GBDT 模 型 全 稱 Gradient Boosted Decision Trees，是一種迭代的決策樹算法，該算法由多棵決策樹組成，通常都是上百棵樹，而且每棵樹規(guī)模都較小。模型預(yù)測的時(shí)候，對于輸入的一個(gè)樣本實(shí)例，首先會賦予一個(gè)初值，然后會遍歷每一棵決策樹，每棵樹都會對預(yù)測值進(jìn)行調(diào)整修正，最終的結(jié)果是將每一棵決策樹的結(jié)果進(jìn)行累加得到的最后得到預(yù)測的結(jié)果，具體算法思想如圖1所示。

從圖1中可以看出GBDT的訓(xùn)練過程是線性的，它不像隨機(jī)森林算法那樣并行訓(xùn)練多棵樹，第一顆T1訓(xùn)練結(jié)果與真實(shí)值T的殘差作為第二顆決策樹T2的樣本，第n顆決策樹Tn的樣本就是第N-1顆決策樹Tn-1的訓(xùn)練結(jié)果，所以該模型的最終分類結(jié)果就是將每一顆決策樹上的結(jié)點(diǎn)值累加。即得到公式：

T=T1+T2…Tn（1）

1.3.2 GBDT分裂點(diǎn)

如果對于一個(gè)模型有多種特征值如何選擇特征值去分類，在ID3算法中選擇每個(gè)屬性中條件熵最小也就是信息增益最大的屬性作為分裂點(diǎn)，在GBDT算法中選擇屬性的最小均方差或者是使得（左子樹樣本目標(biāo)值和的平方均值+右子樹樣本目標(biāo)值和的平方均值-父結(jié)點(diǎn)所有樣本目標(biāo)值和的平方均值）最大的那個(gè)分裂點(diǎn)作為分類特征。

當(dāng)特征很多的時(shí)候，特征的選取對于決策樹的創(chuàng)建有很大的影響，他決定這顆回歸樹的深度，所以必須通過正確的方式找到最能決定樣本分類的分裂特征，才能創(chuàng)建預(yù)測效果較好的決策樹。

1.3.3 GDBT算法示例

有四個(gè)訓(xùn)練樣本A、B、C、D，他們的年齡分別是14、16、24、26，現(xiàn)在要對他們進(jìn)行年齡預(yù)測。其中A、B是學(xué)生，C、D是已經(jīng)工作的人。使用GBDT算法得到第一棵樹如圖2所示。

首先，輸入樣本的均值，這里均值為20，選擇第一個(gè)特征分類（具體選擇是根據(jù)上文的G來判斷的），可以把4個(gè)樣本分成兩類，一類是購物金額<1K，一類是>1K的。根據(jù)這個(gè)特征可以把樣本分成兩類，如果到這里就停止學(xué)習(xí)了，就要統(tǒng)計(jì)葉子節(jié)點(diǎn)包含了哪些樣本，如果A、B被分到了一組，那么該節(jié)點(diǎn)的值就是分到左子樹所有樣本的平均值，這里為15，也就是這些樣本的預(yù)測值，即A、B的預(yù)測值都為15，右子樹同理計(jì)算；如果學(xué)習(xí)還沒有停止，那么就要計(jì)算分到該類的樣本與預(yù)測值的差，A=-1，B=1，C=-1，D=1，這些得到的殘差作為下一顆決策樹的樣本，下一顆樹的學(xué)習(xí)過程如圖3所示。

第二棵決策樹，把第一棵的殘差樣本（A，-1歲）、（B，1歲）、（C，-1歲）、（D，1歲）輸入。此時(shí)要選取第二個(gè)特征值來分類（具體選擇的特征還是上文求出G的公式）。接下來又可以把樣本分成兩類，一部分是A、C組成了左葉子，另一部分是B、D組成的右葉子，先計(jì)算記一下殘差發(fā)現(xiàn)都是0，GBDT算法的分類過程就是不斷的將殘差接近0，所以直到殘差為0的時(shí)候就可以結(jié)束學(xué)習(xí)了，那么可以得到ABCD的預(yù)測值，即AC的預(yù)測結(jié)果都是-1，BD都是1。

現(xiàn)在給一個(gè)特征表測試一下，如表1所示。

2 結(jié)論

通過分析傳統(tǒng)決策樹和迭代決策樹有何區(qū)別，并舉例說明，可以得到以下結(jié)論：傳統(tǒng)決策樹一般適用于一個(gè)屬性的特征值較少的情況，決策樹構(gòu)造不是很復(fù)雜，對于復(fù)雜的數(shù)據(jù)，傳統(tǒng)決策樹分類效果并不是很好，構(gòu)造的樹會很深，橫向也很廣，有可能最終還會造成無法分類；這時(shí)就要找尋新的算法來代替?zhèn)鹘y(tǒng)決策樹，幸運(yùn)的是GBDT算法是一個(gè)可行的算法，基于回歸的思想對復(fù)雜數(shù)據(jù)有較強(qiáng)的處理能力，而且它是由多棵樹組成的，構(gòu)造樹不復(fù)雜，每次用殘差進(jìn)行調(diào)整，保證分類的精確。

【參考文獻(xiàn)】

[1]孟巖，汪云云.典型半監(jiān)督分類算法的研究分析[J].計(jì)算機(jī)技術(shù)與發(fā)展，2017（09）：1-7.

[2]龍浩.用于不平衡分類問題的自適應(yīng)加權(quán)極限學(xué)習(xí)機(jī)研究[D].深圳大學(xué)，2017.

[3]楊志輝.基于機(jī)器學(xué)習(xí)算法在數(shù)據(jù)分類中的應(yīng)用研究[D].中北大學(xué)，2017.

[4]沈龍鳳，宋萬干，葛方振，等.最優(yōu)路徑森林分類算法綜述[J].計(jì)算機(jī)應(yīng)用研究，2018（01）：1-9.

[責(zé)任編輯：朱麗娜]endprint