當前位置：
首頁 > 知識 > GBDT分類的原理及Python實現

GBDT分類的原理及Python實現

知識 09-18


程序員大咖

點擊右側關注，免費進階高級！





作者：李小文

Github: https://gith

ub.com/tushu

shu


提到GBDT分類相信大家應該都不會覺得陌生，本文就GBDT分類的基本原理進行講解，並手把手、肩並肩地帶您實現這一演算法。


完整實現代碼請參考本人的github：

https:

//github.com/tushushu/imylu/blob/master/imylu/ensemble/gbdt_base.py

https:

//github.com/tushushu/imylu/blob/master/imylu/ensemble/gbdt_classifier.py


https:

//github.com/tushushu/imylu/blob/master/examples/gbdt_classifier_example.py



一. 原理篇


我們用人話而不是大段的數學公式來講講GBDT分類是怎麼一回事。


1.1 溫故知新


GBDT分類只是在GBDT回歸上做了一點點改造，而GBDT分類又是建立在回歸樹的基礎上的。 之前寫過一篇GBDT回歸的文章，鏈接如下：


GBDT回歸的原理及Python實現



之前寫過一篇回歸樹的文章，鏈接如下：


回歸樹的原理及Python實現



1.2 Sigmoid函數


如果對邏輯回歸或者神經網路有所了解的話，那麼對Sigmoid函數應該不會感到陌生，它的函數表達式是：



不難得出：




所以，Sigmoid函數的值域是(0, 1)，導數為y * (1 - y)


1.3 改造GBDT回歸


根據《GBDT回歸》可知，假設要做m輪預測，預測函數為Fm，初始常量或每一輪的回歸樹為fm，輸入變數為X，有：



由於是回歸問題，函數F的值域在(-∞, +∞)，而二分類問題要求預測的函數值在(0, 1)，所以我們可以用Sigmoid函數將最終的預測值的值域控制在(0, 1)之間，其函數表達式如下：




1.4 預測見面


以預測相親是否見面來舉例，見面用1表示，不見面用0表示。從《回歸樹》那篇文章中我們可以知道，如果需要通過一個常量來預測同事的年齡，平均值是最佳選擇之一。那麼預測二分類問題，這個常量該如何計算呢？我們簡單證明一下：




結論，如果要用一個常量來預測y，用log(sum(y)/sum(1-y))是一個最佳的選擇。



1.5 見面的殘差


我們不妨假設三個相親對象是否見面分別為[1, 0, 1]，那麼預測是否見面的初始值z = log((1+0+1)/(0+1+0)) = 0.693，所以我們用0.693這個常量來預測同事的年齡，即Sigmoid([0.693, 0.693, 0.693]) = [0.667, 0.667, 0.667]。每個相親對象是否見面的殘差 = 是否見面 - 預測值 = [1, 0, 1] - [0.667, 0.667, 0.667]，所以殘差為[0.333, -0.667, 0.333]


1.6 預測見面的殘差


為了讓模型更加準確，其中一個思路是讓殘差變小。如何減少殘差呢？我們不妨對殘差建立一顆回歸樹，然後預測出準確的殘差。假設這棵樹預測的殘差是[1, -0.5, 1]，將上一輪的預測值和這一輪的預測值求和，之後再求Sigmoid值，每個相親對象是否見面 = Sigmoid([0.693, 0.693, 0.693] + [1, -0.5, 1]) = [0.845, 0.548, 0.845]，顯然與真實值[1, 0, 1]更加接近了， 每個相親對象是否見面的殘差此時變為[0.155, -0.548, 0.155]，預測的準確性得到了提升。


1.7 GBDT


重新整理一下思路，假設我們的預測一共迭代3輪 是否見面：[1, 0, 1]


第1輪預測：Sigmoid(0.693, 0.693, 0.693) = [0.667, 0.667, 0.667]


第1輪殘差：[0.333, -0.667, 0.333]


第2輪預測：Sigmoid(0.693, 0.693, 0.693 + [1, -0.5, 1]) (第1顆回歸樹)) = Sigmoid([1.693, 0.193, 1.693]) = [0.845, 0.548, 0.845]


第2輪殘差：[0.155, -0.548, 0.155]


第3輪預測：Sigmoid(0.693, 0.693, 0.693 + 1, -0.5, 1 + 2, -1, 2) = Sigmoid([3.693, -0.807, 3.693]) = [0.976, 0.309, 0.976]


第3輪殘差：[0.024, -0.309, 0.024]


看上去殘差越來越小，而這種預測方式就是GBDT演算法。


1.8 公式推導


看到這裡，相信您對GBDT已經有了直觀的認識。這麼做有什麼科學依據么，為什麼殘差可以越來越小呢？前方小段數學公式低能預警。




因此，我們需要通過用第m-1輪的預測值和殘差來得到函數fm，進而優化函數fm。而回歸樹的原理就是通過最佳劃分區域的均值來進行預測，與GBDT回歸不同，要把這個均值改為1.7式11。所以fm可以選用回歸樹作為基礎模型，將初始值，m-1顆回歸樹的預測值相加再求Sigmoid值便可以預測y。


二. 實現篇


本人用全宇宙最簡單的編程語言——Python實現了GBDT分類演算法，沒有依賴任何第三方庫，便於學習和使用。簡單說明一下實現過程，更詳細的注釋請參考本人github上的代碼。


2.1 導入回歸樹類


回歸樹是我之前已經寫好的一個類，在之前的文章詳細介紹過，代碼請參考：

https:

/

/github.com/tushushu/imylu/blob/master/imylu/tree/regression

_tree.py
from ..tree.regression_tree import RegressionTree

2.2 創建GradientBoostingBase類


初始化，存儲回歸樹、學習率、初始預測值和變換函數。

class

 

GradientBoostingBase(object)

:


    

def

 

__init__(self)

:


        self.trees = 

None


        self.lr = 

None


        self.init_val = 

None


        self.fn = 

lambda

 x: sigmoid(x)

2.3 計算初始預測值


初始預測值，見1.7式10。

def

 

_get_init_val(

self

, y)

:
    n = len(y)
    y_sum = sum(y)
    

return

 log((y_sum) / (n - y_sum))

2.4 匹配葉結點


計算訓練樣本屬於回歸樹的哪個葉子結點。

def _match_node(self, row, tree):
    nd = tree.root
    

while

 nd.

left

 

and

 nd.

right

:
        

if

 row[nd.feature] < nd.

split

:
            nd = nd.

left


        

else

:
            nd = nd.

right


    return nd

2.5 獲取葉節點


獲取一顆回歸樹的所有葉子結點。

def

 

_get_leaves(self, tree)

:


    nodes = []
    que = [tree.root]
    

while

 que:
        node = que.pop(

0

)
        

if

 node.left 

is

 

None

 

or

 node.right 

is

 

None

:
            nodes.append(node)
            

continue


        left_node = node.left
        right_node = node.right
        que.append(left_node)
        que.append(right_node)
    

return

 nodes

2.6 劃分區域


將回歸樹的葉子結點，其對應的所有訓練樣本存入字典。

def

 

_divide_regions(

self

, tree, nodes, X)

:
    regions = {

node:

 [] 

for

 node 

in

 nodes}
    

for

 i, row 

in

 enumerate(X):
        node = 

self

._match_node(row, tree)
        regions[node].append(i)
    

return

 regions

2.7 計算預測值


見1.7式11。

def

 

_get_score(

self

, idxs, y_hat, residuals)

:
    numerator = denominator = 

0


    

for

 idx 

in

 

idxs:


        numerator += residuals[idx]
        denominator += y_hat[idx] * (

1

 - y_hat[idx])
    

return

 numerator / denominator

2.8 更新預測值


更新回歸樹各個葉節點的預測值。

def

 

_update_score(

self

, tree, X, y_hat, residuals)

:
    nodes = 

self

._get_leaves(tree)
    regions = 

self

._divide_regions(tree, nodes, X)
    

for

 node, idxs 

in

 regions.items():
        node.score = 

self

._get_score(idxs, y_hat, residuals)
    tree._get_rules()

2.9 計算殘差

def

 

_get_residuals(

self

, y, y_hat)

:
    

return

 [yi - 

self

.fn(y_hat_i) 

for

 yi, y_hat_i 

in

 zip(y, y_hat)]

2.10 訓練模型


訓練模型的時候需要注意以下幾點：




  1. 控制樹的最大深度max_depth；



  2. 控制分裂時最少的樣本量min_samples_split；



  3. 訓練每一棵回歸樹的時候要乘以一個學習率lr，防止模型過擬合；



  4. 對樣本進行抽樣的時候要採用有放回的抽樣方式。

def

 

fit(

self

, X, y, n_estimators, lr, max_depth, min_samples_split, subsample=None)

:
    

self

.init_val = 

self

._get_init_val(y)

    n = len(y)
    y_hat = [

self

.init_val] * n
    residuals = 

self

._get_residuals(y, y_hat)

    

self

.trees = []
    

self

.lr = lr
    

for

 

_

 

in

 range(n_estimators):
        idx = range(n)
        

if

 subsample is 

not

 

None:


            k = int(subsample * n)
            idx = choices(population=idx, k=k)
        X_sub = [X[i] 

for

 i 

in

 idx]
        residuals_sub = [residuals[i] 

for

 i 

in

 idx]
        y_hat_sub = [y_hat[i] 

for

 i 

in

 idx]

        tree = RegressionTree()
        tree.fit(X_sub, residuals_sub, max_depth, min_samples_split)

        

self

._update_score(tree, X_sub, y_hat_sub, residuals_sub)

        y_hat = [y_hat_i + lr * res_hat_i 

for

 y_hat_i,
                    res_hat_i 

in

 zip(y_hat, tree.predict(X))]

        residuals = 

self

._get_residuals(y, y_hat)
        

self

.trees.append(tree)

2.11 預測一個樣本

def

 

_predict(

self

, Xi)

:
    

return

 

self

.fn(

self

.init_val + sum(

self

.lr * tree._predict(Xi) 

for

 tree 

in

 

self

.trees))

2.12 預測多個樣本

def

 

predict(

self

, X)

:
    

return

 [int(

self

._predict(Xi) >= threshold) 

for

 Xi 

in

 X]

三. 效果評估


3.1 main函數


使用著名的乳腺癌數據集，按照7:3的比例拆分為訓練集和測試集，訓練模型，並統計準確度。

@run_time


def

 

main()

:

    print(

"Tesing the accuracy of GBDT classifier..."

)

    X, y = load_breast_cancer()

    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=

20

)

    clf = GradientBoostingClassifier()
    clf.fit(X_train, y_train, n_estimators=

2

,
            lr=

0.8

, max_depth=

3

, min_samples_split=

2

)

    get_acc(clf, X_test, y_test)

3.2 效果展示


最終準確度93.082%，運行時間14.9秒，效果還算不錯~


3.3 工具函數


本人自定義了一些工具函數，可以在github上查看

https:

//github.com/tushushu/imylu/blob/master/imylu/utils.py





  1. run_time - 測試函數運行時間



  2. load_breast_cancer - 載入乳腺癌數據



  3. train_test_split - 拆分訓練集、測試集



  4. get_acc - 計算準確度


總結


GBDT分類的原理：GBDT回歸加Sigmoid


GBDT分類的實現：一言難盡


【點擊成為源碼大神】

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！


請您繼續閱讀更多來自 Python開發 的精彩文章:

※使用Python自動生成報表以郵件發送
※女生哪裡最緊？

TAG:Python開發 |