曹穎超

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

1.2 隨機(jī)森林

隨機(jī)森林這個術(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個樣本形成樣本子集，然后根據(jù)N個樣本子集生成N決策樹，當(dāng)輸入測試數(shù)據(jù)時(shí)，在每一顆決策樹上進(jìn)行判斷，得到分類結(jié)果，最后統(tǒng)計(jì)哪一個分類選擇最多，就預(yù)測這個測試樣本屬于哪一個分類。隨機(jī)森林算法能處理很高維度的數(shù)據(jù)，并且不用做特征選擇，有很多顆決策樹，不會對數(shù)據(jù)過度擬合，抗噪聲能力強(qiáng)。缺點(diǎn)就是一個測試樣本在每一顆樹上都要判斷，計(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í)候，對于輸入的一個樣本實(shí)例，首先會賦予一個初值，然后會遍歷每一棵決策樹，每棵樹都會對預(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)

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

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

1.3.3 GDBT算法示例

有四個訓(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，選擇第一個特征分類（具體選擇是根據(jù)上文的G來判斷的），可以把4個樣本分成兩類，一類是購物金額<1K，一類是>1K的。根據(jù)這個特征可以把樣本分成兩類，如果到這里就停止學(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的公式）。接下來又可以把樣本分成兩類，一部分是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)在給一個特征表測試一下，如表1所示。

2 結(jié)論

通過分析傳統(tǒng)決策樹和迭代決策樹有何區(qū)別，并舉例說明，可以得到以下結(jié)論：傳統(tǒng)決策樹一般適用于一個屬性的特征值較少的情況，決策樹構(gòu)造不是很復(fù)雜，對于復(fù)雜的數(shù)據(jù)，傳統(tǒng)決策樹分類效果并不是很好，構(gòu)造的樹會很深，橫向也很廣，有可能最終還會造成無法分類；這時(shí)就要找尋新的算法來代替?zhèn)鹘y(tǒng)決策樹，幸運(yùn)的是GBDT算法是一個可行的算法，基于回歸的思想對復(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