[[206785]]

決策樹

引言

決策樹，是機(jī)器學(xué)習(xí)中一種非常常見的分類方法，也可以說是所有算法中最直觀也最好理解的算法。先舉個(gè)最簡單的例子：

A：你去不去吃飯?

B：你去我就去。

“你去我就去”，這是典型的決策樹思想。

再舉個(gè)例子：

有人找我借錢(當(dāng)然不太可能。。。)，借還是不借?我會(huì)結(jié)合根據(jù)我自己有沒有錢、我自己用不用錢、對(duì)方信用好不好這三個(gè)特征來決定我的答案。

我們把轉(zhuǎn)到更普遍一點(diǎn)的視角，對(duì)于一些有特征的數(shù)據(jù)，如果我們能夠有這么一顆決策樹，我們也就能非常容易地預(yù)測樣本的結(jié)論。所以問題就轉(zhuǎn)換成怎么求一顆合適的決策樹，也就是怎么對(duì)這些特征進(jìn)行排序。

在對(duì)特征排序前先設(shè)想一下，對(duì)某一個(gè)特征進(jìn)行決策時(shí)，我們肯定希望分類后樣本的純度越高越好，也就是說分支結(jié)點(diǎn)的樣本盡可能屬于同一類別。

所以在選擇根節(jié)點(diǎn)的時(shí)候，我們應(yīng)該選擇能夠使得“分支結(jié)點(diǎn)純度最高”的那個(gè)特征。在處理完根節(jié)點(diǎn)后，對(duì)于其分支節(jié)點(diǎn)，繼續(xù)套用根節(jié)點(diǎn)的思想不斷遞歸，這樣就能形成一顆樹。這其實(shí)也是貪心算法的基本思想。那怎么量化“純度最高”呢?熵就當(dāng)仁不讓了，它是我們最常用的度量純度的指標(biāo)。其數(shù)學(xué)表達(dá)式如下：

其中N表示結(jié)論有多少種可能取值，p表示在取第k個(gè)值的時(shí)候發(fā)生的概率，對(duì)于樣本而言就是發(fā)生的頻率/總個(gè)數(shù)。

熵越小，說明樣本越純。

以一個(gè)兩點(diǎn)分布樣本X(x=0或1)的熵的函數(shù)圖像來說明吧，橫坐標(biāo)表示樣本值為1的概率，縱坐標(biāo)表示熵。

可以看到到當(dāng)p(x=1)=0時(shí)，也就是說所有的樣本都為0，此時(shí)熵為0.

當(dāng)p(x=1)=1時(shí)，也就是說所有的樣本都為1，熵也為0.

當(dāng)p(x=1)=0.5時(shí)，也就是樣本中0，1各占一半，此時(shí)熵能取得最大值。

擴(kuò)展一下，樣本X可能取值為n種(x1。。。。xn)?？梢宰C明，當(dāng)p(xi)都等于1/n 時(shí)，也就是樣本絕對(duì)均勻，熵能達(dá)到最大。當(dāng)p(xi)有一個(gè)為1，其他都為0時(shí)，也就是樣本取值都是xi，熵最小。

決策樹算法

ID3

假設(shè)在樣本集X中，對(duì)于一個(gè)特征a，它可能有(a1，a2。。。an)這些取值，如果用特征a對(duì)樣本集X進(jìn)行劃分(把它當(dāng)根節(jié)點(diǎn))，肯定會(huì)有n個(gè)分支結(jié)點(diǎn)。剛才提了，我們希望劃分后，分支結(jié)點(diǎn)的樣本越純?cè)胶?，也就是分支結(jié)點(diǎn)的“總熵”越小越好。

因?yàn)槊總€(gè)分支結(jié)點(diǎn)的個(gè)數(shù)不一樣，因此我們計(jì)算“總熵”時(shí)應(yīng)該做一個(gè)加權(quán)，假設(shè)第i個(gè)結(jié)點(diǎn)樣本個(gè)數(shù)為W(ai)，其在所有樣本中的權(quán)值為W(ai) / W(X)。所以我們可以得到一個(gè)總熵：

這個(gè)公式代表含義一句話：加權(quán)后各個(gè)結(jié)點(diǎn)的熵的總和。這個(gè)值應(yīng)該越小，純度越高。

這時(shí)候，我們引入一個(gè)名詞叫信息增益G(X，a)，意思就是a這個(gè)特征給樣本帶來的信息的提升。公式就是：，由于H(X)對(duì)一個(gè)樣本而言，是一個(gè)固定值，因此信息增益G應(yīng)該越大越好。尋找使得信息增益最大的特征作為目標(biāo)結(jié)點(diǎn)，并逐步遞歸構(gòu)建樹，這就是ID3算法的思想，好了以一個(gè)簡單的例子來說明信息增益的計(jì)算：

上面的例子，我計(jì)算一下特征1的信息增益

首先計(jì)算樣本的熵H(X)

再計(jì)算總熵，可以看到特征1有3個(gè)結(jié)點(diǎn)A、B、C，其分別為6個(gè)、6個(gè)、5個(gè)

所以A的權(quán)值為6/(6+6+5), B的權(quán)值為6/(6+6+5), C的為5/(6+6+5)

因?yàn)槲覀兿Ｍ麆澐趾蠼Y(jié)點(diǎn)的純度越高越好，因此還需要再分別計(jì)算結(jié)點(diǎn)A、B、C的熵

特征1=A：3個(gè)是、3個(gè)否，其熵為

特征1=B：2個(gè)是、4個(gè)否，其熵為

特征1=C：4個(gè)是、1個(gè)否，其熵為

這樣分支結(jié)點(diǎn)的總熵就等于：

特征1的信息增益就等于0.998-0.889=0.109

類似地，我們也能算出其他的特征的信息增益，最終取信息增益最大的特征作為根節(jié)點(diǎn)。

以上計(jì)算也可以有經(jīng)驗(yàn)條件熵來推導(dǎo)：G(X,A)=H(X) - H(X|A)，這部分有興趣的同學(xué)可以了解一下。

C4.5

在ID3算法中其實(shí)有個(gè)很明顯的問題。

如果有一個(gè)樣本集，它有一個(gè)叫id或者姓名之類的(唯一的)的特征，那就完蛋了。設(shè)想一下，如果有n個(gè)樣本，id這個(gè)特征肯定會(huì)把這個(gè)樣本也分成n份，也就是有n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)只有一個(gè)值，那每個(gè)結(jié)點(diǎn)的熵就為0。就是說所有分支結(jié)點(diǎn)的總熵為0，那么這個(gè)特征的信息增益一定會(huì)達(dá)到最大值。因此如果此時(shí)用ID3作為決策樹算法，根節(jié)點(diǎn)必然是id這個(gè)特征。但是顯然這是不合理的。。。

當(dāng)然上面說的是極限情況，一般情況下，如果一個(gè)特征對(duì)樣本劃分的過于稀疏，這個(gè)也是不合理的(換句話就是，偏向更多取值的特征)。為了解決這個(gè)問題，C4.5算法采用了信息增益率來作為特征選取標(biāo)準(zhǔn)。

所謂信息增益率，是在信息增益基礎(chǔ)上，除了一項(xiàng)split information,來懲罰值更多的屬性。

而這個(gè)split information其實(shí)就是特征個(gè)數(shù)的熵H(A)。

為什么這樣可以減少呢，以上面id的例子來理解一下。如果id把n個(gè)樣本分成了n份，那id這個(gè)特征的取值的概率都是1/n，文章引言已經(jīng)說了，樣本絕對(duì)均勻的時(shí)候，熵最大。

因此這種情況，以id為特征，雖然信息增益最大，但是懲罰因子split information也最大，以此來拉低其增益率，這就是C4.5的思想。

CART

決策樹的目的最終還是尋找到區(qū)分樣本的純度的量化標(biāo)準(zhǔn)。在CART決策樹中，采用的是基尼指數(shù)來作為其衡量標(biāo)準(zhǔn)?；嵯禂?shù)直觀的理解是，從集合中隨機(jī)抽取兩個(gè)樣本，如果樣本集合越純，取到不同樣本的概率越小。這個(gè)概率反應(yīng)的就是基尼系數(shù)。

因此如果一個(gè)樣本有K個(gè)分類。假設(shè)樣本的某一個(gè)特征a有n個(gè)取值的話，其某一個(gè)結(jié)點(diǎn)取到不同樣本的概率為：

因此k個(gè)分類的概率總和，我們稱之為基尼系數(shù)：

而基尼指數(shù)，則是對(duì)所有結(jié)點(diǎn)的基尼系數(shù)進(jìn)行加權(quán)處理

計(jì)算出來后，我們會(huì)選擇基尼系數(shù)最小的那個(gè)特征作為最優(yōu)劃分特征。

剪枝

剪枝的目的其實(shí)就是防止過擬合，它是決策樹防止過擬合的最主要手段。決策樹中，為了盡可能爭取的分類訓(xùn)練樣本，所以我們的決策樹也會(huì)一直生長。但是呢，有時(shí)候訓(xùn)練樣本可能會(huì)學(xué)的太好，以至于把某些樣本的特有屬性當(dāng)成一般屬性。這時(shí)候就我們就需要主動(dòng)去除一些分支，來降低過擬合的風(fēng)險(xiǎn)。

剪枝一般有兩種方式：預(yù)剪枝和后剪枝。

預(yù)剪枝

一般情況下，只要結(jié)點(diǎn)樣本已經(jīng)100%純了，樹才會(huì)停止生長。但這個(gè)可能會(huì)產(chǎn)生過擬合，因此我們沒有必要讓它100%生長，所以在這之前，設(shè)定一些終止條件來提前終止它。這就叫預(yù)剪枝，這個(gè)過程發(fā)生在決策樹生成之前。

一般我們預(yù)剪枝的手段有：

1、限定樹的深度

2、節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目小于閾值

3、設(shè)定結(jié)點(diǎn)熵的閾值

等等。

后剪枝

顧名思義，這個(gè)剪枝是在決策樹建立過程后。后剪枝算法的算法很多，有些也挺深?yuàn)W，這里提一個(gè)簡單的算法的思想，就不深究啦。

Reduced-Error Pruning (REP)

該剪枝方法考慮將樹上的每個(gè)節(jié)點(diǎn)都作為修剪的候選對(duì)象，但是有一些條件決定是否修剪，通常有這幾步：

1、刪除其所有的子樹，使其成為葉節(jié)點(diǎn)。

2、賦予該節(jié)點(diǎn)最關(guān)聯(lián)的分類

3、用驗(yàn)證數(shù)據(jù)驗(yàn)證其準(zhǔn)確度與處理前比較

如果不比原來差，則真正刪除其子樹。然后反復(fù)從下往上對(duì)結(jié)點(diǎn)處理。這個(gè)處理方式其實(shí)是處理掉那些“有害”的節(jié)點(diǎn)。

隨機(jī)森林

隨機(jī)森林的理論其實(shí)和決策樹本身不應(yīng)該牽扯在一起，決策樹只能作為其思想的一種算法。

為什么要引入隨機(jī)森林呢。我們知道，同一批數(shù)據(jù)，我們只能產(chǎn)生一顆決策樹，這個(gè)變化就比較單一了。還有要用多個(gè)算法的結(jié)合呢?

這就有了集成學(xué)習(xí)的概念。

圖中可以看到，每個(gè)個(gè)體學(xué)習(xí)器(弱學(xué)習(xí)器)都可包含一種算法，算法可以相同也可以不同。如果相同，我們把它叫做同質(zhì)集成，反之則為異質(zhì)。

隨機(jī)森林則是集成學(xué)習(xí)采用基于bagging策略的一個(gè)特例。

從上圖可以看出，bagging的個(gè)體學(xué)習(xí)器的訓(xùn)練集是通過隨機(jī)采樣得到的。通過n次的隨機(jī)采樣，我們就可以得到n個(gè)樣本集。對(duì)于這n個(gè)樣本集，我們可以分別獨(dú)立的訓(xùn)練出n個(gè)個(gè)體學(xué)習(xí)器，再對(duì)這n個(gè)個(gè)體學(xué)習(xí)器通過集合策略來得到最終的輸出，這n個(gè)個(gè)體學(xué)習(xí)器之間是相互獨(dú)立的，可以并行。

注：集成學(xué)習(xí)還有另一種方式叫boosting，這種方式學(xué)習(xí)器之間存在強(qiáng)關(guān)聯(lián)，有興趣的可以了解下。

隨機(jī)森林采用的采樣方法一般是是Bootstap sampling，對(duì)于原始樣本集，我們每次先隨機(jī)采集一個(gè)樣本放入采樣集，然后放回，也就是說下次采樣時(shí)該樣本仍有可能被采集到，經(jīng)過一定數(shù)量的采樣后得到一個(gè)樣本集。由于是隨機(jī)采樣，這樣每次的采樣集是和原始樣本集不同的，和其他采樣集也是不同的，這樣得到的個(gè)體學(xué)習(xí)器也是不同的。

隨機(jī)森林最主要的問題是有了n個(gè)結(jié)果，怎么設(shè)定結(jié)合策略，主要方式也有這么幾種：

加權(quán)平均法：

平均法常用于回歸。做法就是，先對(duì)每個(gè)學(xué)習(xí)器都有一個(gè)事先設(shè)定的權(quán)值wi，

然后最終的輸出就是：

當(dāng)學(xué)習(xí)器的權(quán)值都為1/n時(shí)，這個(gè)平均法叫簡單平均法。

投票法：

投票法類似我們生活中的投票，如果每個(gè)學(xué)習(xí)器的權(quán)值都是一樣的。

那么有絕對(duì)投票法，也就是票數(shù)過半。相對(duì)投票法，少數(shù)服從多數(shù)。

如果有加權(quán)，依然是少數(shù)服從多數(shù)，只不過這里面的數(shù)是加權(quán)后的。

例子

以一個(gè)簡單的二次函數(shù)的代碼來看看決策樹怎么用吧。

訓(xùn)練數(shù)據(jù)是100個(gè)隨機(jī)的真實(shí)的平方數(shù)據(jù)，不同的深度將會(huì)得到不同的曲線

測試數(shù)據(jù)也是隨機(jī)數(shù)據(jù)，但是不同深度的樹的模型，產(chǎn)生的預(yù)測值也不太一樣。如圖

這幅圖的代碼如下：

我的是python 3.6環(huán)境，需要安裝numpy、matplotlib、sklearn這三個(gè)庫，需要的話直接pip install，大家可以跑跑看看，雖然簡單但挺有趣。

#!/usr/bin/python 
# -*- coding:utf-8 -*- 
 
import numpy as np 
import matplotlib as mpl 
import matplotlib.pyplot as plt 
from sklearn.tree import DecisionTreeRegressor 
 
 
if __name__ == "__main__": 
 
    # 準(zhǔn)備訓(xùn)練數(shù)據(jù) 
    N = 100 
    x = np.random.rand(N) * 6 - 3 
    x.sort() 
    y = x*x 
    x = x.reshape(-1, 1) 
 
    mpl.rcParams['font.sans-serif'] = ['SimHei'] 
    mpl.rcParams['axes.unicode_minus'] = False 
 
    # 決策樹深度及其曲線顏色 
    depth = [2, 4, 6, 8, 10] 
    clr = 'rgbmy' 
 
    # 實(shí)際值 
    plt.figure(facecolor='w') 
    plt.plot(x, y, 'ro', ms=5, mec='k', label='實(shí)際值') 
 
    # 準(zhǔn)備測試數(shù)據(jù) 
    x_test = np.linspace(-3, 3, 50).reshape(-1, 1) 
 
    # 構(gòu)建決策樹 
    dtr = DecisionTreeRegressor() 
    # 循環(huán)不同深度情況下決策樹的模型，并用之測試數(shù)據(jù)的輸出 
    for d, c in zip(depth, clr): 
        # 設(shè)置最大深度（預(yù)剪枝） 
        dtr.set_params(max_depth=d) 
        # 訓(xùn)練決策樹 
        dtr.fit(x, y) 
        # 用訓(xùn)練數(shù)據(jù)得到的模型來驗(yàn)證測試數(shù)據(jù) 
        y_hat = dtr.predict(x_test) 
        # 畫出模型得到的曲線 
        plt.plot(x_test, y_hat, '-', color=c, linewidth=2, markeredgecolor='k', label='Depth=%d' % d) 
    # 一些畫圖的基本參數(shù) 
    plt.legend(loc='upper center', fontsize=12) 
    plt.xlabel('X') 
    plt.ylabel('Y') 
    plt.grid(b=True, ls=':', color='#606060') 
    plt.title('二次函數(shù)決策樹', fontsize=15) 
    plt.tight_layout(2) 
    plt.show() 

原文鏈接：https://www.qcloud.com/community/article/160232

作者：汪毅雄

【本文是51CTO專欄作者“騰訊云技術(shù)社區(qū)”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過51CTO聯(lián)系原作者獲取授權(quán)】

戳這里，看該作者更多好文