改進的GDBT迭代決策樹分類算法及其應用

曹穎超

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

【關鍵詞】分類算法；決策樹；GBDT

0 引言

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

1 改進的決策樹分類算法

1.1 Boosting方法

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

1.2 隨機森林

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

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

1.3 GBDT算法

1.3.1 GDBT 思想與原理

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

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

T=T1+T2…Tn（1）

1.3.2 GBDT分裂點

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

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

1.3.3 GDBT算法示例

有四個訓練樣本A、B、C、D，他們的年齡分別是14、16、24、26，現在要對他們進行年齡預測。其中A、B是學生，C、D是已經工作的人。使用GBDT算法得到第一棵樹如圖2所示。

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

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

現在給一個特征表測試一下，如表1所示。

2 結論

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

【參考文獻】

[1]孟巖，汪云云.典型半監督分類算法的研究分析[J].計算機技術與發展，2017（09）：1-7.

[2]龍浩.用于不平衡分類問題的自適應加權極限學習機研究[D].深圳大學，2017.

[3]楊志輝.基于機器學習算法在數據分類中的應用研究[D].中北大學，2017.

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

[責任編輯：朱麗娜]endprint