《Machine Learning in Action》—— Taoye給你講講決策樹(shù)到底是支什么“鬼”

前面我們已經(jīng)詳細(xì)講解了線(xiàn)性SVM以及SMO的初步優(yōu)化過(guò)程，具體可看：

《Machine Learning in Action》—— 剖析支持向量機(jī)店乐，優(yōu)化SMO
《Machine Learning in Action》—— 剖析支持向量機(jī)逆巍，單手狂撕線(xiàn)性SVM

關(guān)于SVM非線(xiàn)性相關(guān)的內(nèi)容，我們留著下個(gè)星期來(lái)撕

這篇文章我們先來(lái)看看決策樹(shù)的內(nèi)容，決策樹(shù)相對(duì)于SVM來(lái)講要簡(jiǎn)單不少，也沒(méi)有多么復(fù)雜的公式。我理解的決策樹(shù)房待，簡(jiǎn)單來(lái)說(shuō)就是通過(guò)已有的數(shù)據(jù)集訓(xùn)練出一個(gè)樹(shù)形結(jié)構(gòu)的模型，以便我們能夠依據(jù)該模型對(duì)不知分類(lèi)結(jié)果的數(shù)據(jù)進(jìn)行預(yù)測(cè)驼抹。簡(jiǎn)單的決策樹(shù)就有點(diǎn)類(lèi)似于我們?cè)趯W(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)候的二叉排序樹(shù)桑孩。當(dāng)然了，決策樹(shù)除了能夠進(jìn)行分類(lèi)之外框冀，還能進(jìn)行回歸流椒，這里主要討論的是分類(lèi)問(wèn)題。

關(guān)于決策樹(shù)相關(guān)的內(nèi)容左驾，可能會(huì)肝兩篇文章來(lái)介紹镣隶。第一篇主要是講解決策樹(shù)先關(guān)的基本知識(shí)，及其決策訓(xùn)練的過(guò)程诡右，也就是我們的這篇文章安岂，重在理論及推導(dǎo)，也重在理解帆吻。而第二篇文章寫(xiě)的主要內(nèi)容是決策樹(shù)的代碼實(shí)戰(zhàn)域那，而代碼實(shí)戰(zhàn)是在熟悉理論基礎(chǔ)的前提之下來(lái)進(jìn)行的，所以對(duì)于決策樹(shù)相關(guān)的理論知識(shí)還是有必要了解的猜煮〈卧保可能的話(huà)，還會(huì)有第三篇王带，主要是關(guān)羽防止決策樹(shù)過(guò)擬合的剪枝操作的內(nèi)容淑蔚。

一、什么是決策樹(shù)

關(guān)于決策樹(shù)的定義愕撰，李航——《統(tǒng)計(jì)學(xué)習(xí)方法》（第二版）這本書(shū)中是這樣描述的：

分類(lèi)決策樹(shù)模型是一種描述對(duì)實(shí)例進(jìn)行分類(lèi)的樹(shù)形結(jié)構(gòu)刹衫，決策樹(shù)由節(jié)點(diǎn)（node）和有向邊（directed edge）組成醋寝。節(jié)點(diǎn)有兩種類(lèi)型：內(nèi)部節(jié)點(diǎn)（iternal node）和葉節(jié)點(diǎn)（leaf node）。內(nèi)部節(jié)點(diǎn)表示一個(gè)特征或?qū)傩源伲~節(jié)點(diǎn)表示一個(gè)類(lèi)音羞。

上述提到的內(nèi)部節(jié)點(diǎn)可以理解成樣本的屬性特征，而葉節(jié)點(diǎn)可以理解成樣本的標(biāo)簽仓犬，而有向邊可以理解成不同的屬性特征結(jié)果嗅绰。一般我們?cè)诶L制決策樹(shù)的時(shí)候，內(nèi)部節(jié)點(diǎn)用方框或長(zhǎng)方形表示搀继，而葉節(jié)點(diǎn)用圓形或橢圓表示窘面。（注意：這個(gè)并不是絕對(duì)的，在不同資料中可能有不同的表示方法叽躯，比如《統(tǒng)計(jì)學(xué)習(xí)方法》一書(shū)中用圓表示內(nèi)部節(jié)點(diǎn)民镜，用方形表示葉子節(jié)點(diǎn)，而在《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》一書(shū)中表示方式正好相反）

枯燥的文字說(shuō)明總是會(huì)降低讀者的閱讀欲望险毁，下面我們不妨通過(guò)一個(gè)實(shí)際的例子來(lái)說(shuō)明下，從而加強(qiáng)讀者對(duì)決策樹(shù)的理解们童。

比如說(shuō)畔况，形容女生美與丑的時(shí)候一般會(huì)存在多個(gè)指標(biāo)，這個(gè)例子感覺(jué)有點(diǎn)危險(xiǎn)慧库，還是換個(gè)吧跷跪。

例子來(lái)源：李航——《統(tǒng)計(jì)學(xué)習(xí)方法》（第二版）

比如說(shuō)，我們沒(méi)Money用了齐板，想要去銀行貸款吵瞻，這個(gè)時(shí)候銀行就會(huì)根據(jù)你自己的個(gè)人附帶特征來(lái)決定是否給你放款。假設(shè)這里的屬性特征有四個(gè)甘磨，分別是年紀(jì)橡羞、是否工作、是否有房子济舆、信用情況卿泽，這些屬性特征就相當(dāng)于是內(nèi)部節(jié)點(diǎn)，標(biāo)簽（結(jié)果）是否放款相當(dāng)于葉子節(jié)點(diǎn)滋觉，而不同屬性特征的結(jié)果表示有向邊签夭，像年紀(jì)中有青年、中年椎侠、老年第租，信用情況有好、一般我纪、非常好等表示不同的有向邊慎宾。

對(duì)此丐吓，我們可以根據(jù)自己的感覺(jué)來(lái)手動(dòng)繪制一個(gè)簡(jiǎn)單的決策樹(shù)模型：

我們知道，上述決策樹(shù)僅僅是我們自己手動(dòng)來(lái)實(shí)現(xiàn)的璧诵，不一定能夠運(yùn)用于解決實(shí)際問(wèn)題汰蜘。而決策樹(shù)的任務(wù)，則是根據(jù)已有的數(shù)據(jù)樣本集訓(xùn)練得到這么一顆樹(shù)形結(jié)構(gòu)模型之宿，以此來(lái)對(duì)未知分類(lèi)的數(shù)據(jù)進(jìn)行類(lèi)別預(yù)測(cè)族操。對(duì)此，我們要向得到這么一顆盡可能理想的決策樹(shù)比被，則不得不考慮以下幾個(gè)問(wèn)題：

決策樹(shù)的指標(biāo)（屬性特征）選擇的順序應(yīng)該是怎樣的的色难？哪個(gè)特征應(yīng)當(dāng)被優(yōu)先考慮呢？
如果構(gòu)建出的決策樹(shù)出現(xiàn)了過(guò)擬合問(wèn)題等缀，也就說(shuō)我們的訓(xùn)練的時(shí)候還不錯(cuò)枷莉，但是一測(cè)試就GG，這個(gè)時(shí)候我們應(yīng)當(dāng)怎么解決呢尺迂？

本篇文章笤妙，主要內(nèi)容是屬性特征的優(yōu)先選取問(wèn)題。

二噪裕、屬性特征的選擇

對(duì)于屬性特征的選擇蹲盘，我們應(yīng)當(dāng)優(yōu)先選取對(duì)訓(xùn)練數(shù)據(jù)集具有明顯分類(lèi)能力的特征，這樣可以提高我們決策樹(shù)的學(xué)習(xí)效率膳音。假如說(shuō)一個(gè)屬性特征的分類(lèi)結(jié)果與隨機(jī)分類(lèi)基本沒(méi)什么差別召衔，則我們可以說(shuō)這個(gè)屬性特征基本是沒(méi)有分類(lèi)能力的。

比如說(shuō)祭陷，我們這里有12個(gè)關(guān)于女生美與丑的數(shù)據(jù)樣本苍凛，其中六個(gè)是丑女，另外六個(gè)是美女兵志，六個(gè)丑女身高有三個(gè)是165cm醇蝴、三個(gè)是185cm，而另外六個(gè)美女身高同樣如此毒姨，這樣的話(huà)哑蔫，我們僅僅通過(guò)身高來(lái)對(duì)女生美貌的判斷基本是沒(méi)有分類(lèi)能力的。（僅僅是個(gè)例子弧呐，不代表任何觀點(diǎn)）

所以闸迷，我們理想情況下決策樹(shù)的生成理應(yīng)是這樣的：隨著決策過(guò)程的不斷進(jìn)行，我們希望決策樹(shù)的分支節(jié)點(diǎn)所包含的樣本盡可能的屬于同一類(lèi)別（標(biāo)簽相同）俘枫，也就是節(jié)點(diǎn)的“純度”越來(lái)越高腥沽。

所以，決策樹(shù)的關(guān)鍵技術(shù)在于屬性特征的選擇鸠蚪。對(duì)于屬性特征的選擇今阳，我們通常有三個(gè)準(zhǔn)則：信息增益师溅、信息增益比（增益率）和基尼指數(shù)。

2.1 信息增益

上面提到了樣本濃度盾舌，比如說(shuō)我這里有10個(gè)女生墓臭，10個(gè)都是美女，那就說(shuō)此時(shí)的樣本濃度高妖谴，假如美女和丑女五五分窿锉，那這個(gè)時(shí)候的濃度就比較低了。這里的“濃度”表達(dá)的就是這個(gè)意思膝舅，它主要針對(duì)的是標(biāo)簽（結(jié)果）嗡载。

而表示樣本“濃度”的指標(biāo)，最常用的就是“信息熵”了仍稀。假定當(dāng)前樣本集合 $D$ 中第 $k$ 類(lèi)（總共 $n$ 類(lèi)）樣本所占的比例為 $p_k$ 洼滚，則此時(shí)樣本 $D$ 的信息熵為：

$Ent(D) = -\sum_{k=1}^np_klog_2(p_k) \tag{2-1}$

通過(guò)上述公式，我們可以知道10個(gè)美女（一個(gè)類(lèi)別）的信息熵為

$Ent(D)=-1 * log_21=0$

美女丑女五五分（兩類(lèi)）的信息熵為：

$Ent(D) = -\frac{1}{2}log_2\frac{1}{2}-\frac{1}{2}log_2\frac{1}{2}=1$

通過(guò)上面信息熵的簡(jiǎn)單計(jì)算技潘，我們可以知道遥巴，信息熵的值越小，則純度越高享幽。

既然我們已經(jīng)了解了信息增益的計(jì)算公式及其所表達(dá)的意義挪哄，那么對(duì)于一個(gè)數(shù)據(jù)樣本集，我們應(yīng)當(dāng)如何用代碼來(lái)進(jìn)行計(jì)算呢琉闪？下面我們來(lái)試試吧。

本次使用到的數(shù)據(jù)樣本來(lái)自李航——《統(tǒng)計(jì)學(xué)習(xí)方法》（第二版）砸彬，數(shù)據(jù)是關(guān)于貸款申請(qǐng)的颠毙，具體如下：

image

那么現(xiàn)在我們來(lái)通過(guò)代碼形式計(jì)算下這個(gè)數(shù)據(jù)樣本集的信息熵吧：

首先創(chuàng)建一個(gè)establish_data方法來(lái)建立一個(gè)二維數(shù)組用于存儲(chǔ)上述數(shù)據(jù)樣本集的相關(guān)信息（關(guān)于屬性特征所對(duì)于的值0,1,2之類(lèi)的，大家可以參考上述表格對(duì)號(hào)入座砂碉，這里就不做過(guò)多解釋了）：

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：創(chuàng)建訓(xùn)數(shù)據(jù)集
"""
def establish_data():
    data = [[0, 0, 0, 0, 'N'],         # 樣本數(shù)據(jù)集相關(guān)信息蛀蜜，前面幾項(xiàng)代表屬性特征，最后一項(xiàng)表示是否放款
            [0, 0, 0, 1, 'N'],
            [0, 1, 0, 1, 'Y'],
            [0, 1, 1, 0, 'Y'],
            [0, 0, 0, 0, 'N'],
            [1, 0, 0, 0, 'N'],
            [1, 0, 0, 1, 'N'],
            [1, 1, 1, 1, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [2, 0, 1, 2, 'Y'],
            [2, 0, 1, 1, 'Y'],
            [2, 1, 0, 1, 'Y'],
            [2, 1, 0, 2, 'Y'],
            [2, 0, 0, 0, 'N']]
    return np.array(data)

隨后增蹭，我們創(chuàng)建一個(gè)calc_information_entropy方法用于計(jì)算信息熵滴某，計(jì)算過(guò)程的代碼可結(jié)合上述的公式來(lái)看。另外滋迈，需要說(shuō)一點(diǎn)的是霎奢，為了方便對(duì)放款結(jié)果進(jìn)行分類(lèi)，我們使用pandas包進(jìn)行處理饼灿，關(guān)于pandas的使用幕侠，大伙可以參考文檔，Taoye后期也會(huì)整理一份碍彭。當(dāng)然了晤硕，不用pandas模塊也能實(shí)現(xiàn)這個(gè)功能悼潭，有興趣的讀者可自行嘗試，也不難舞箍。calc_information_entropy具體代碼如下：

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：計(jì)算信息熵
"""
def calc_information_entropy(data):
    data_number, _ = data.shape
    information_entropy = 0
    for item in pd.DataFrame(data).groupby(_ - 1):
        print(item[1])
        proportion = item[1].shape[0] / data_number
        information_entropy += - proportion * np.log2(proportion)
    return information_entropy

我們運(yùn)行上述代碼舰褪，來(lái)看看具體的信息熵結(jié)果：

相比大家都了解了信息熵的概念，并能夠手動(dòng)計(jì)算樣本集的信息熵了疏橄，現(xiàn)在我們?cè)賮?lái)把信息增益搬出來(lái)吧占拍。

假設(shè)一個(gè)屬性特征 $a$ 有 $V$ 個(gè)可能的取值 $\{a^1, a^2,.., a^V\}$ ，若使用 $a$ 來(lái)對(duì)樣本集 $D$ 進(jìn)行劃分软族，這樣的話(huà)就會(huì)產(chǎn)生 $V$ 個(gè)分支節(jié)點(diǎn)刷喜，其中第 $v$ 個(gè) 分支節(jié)點(diǎn)包含了 $D$ 中所有在屬性 $a$ 上取值為 $a^V$ 的樣本，記為 $D^V$ 立砸。于是可計(jì)算出用屬性特征 $a$ 對(duì)樣本集 $D$ 進(jìn)行劃分所獲得的“信息增益”（information gain）為：

$Gain(D, a)=Ent(D)-\sum_{v=1}^V\frac{D^v}{D}Ent(D^v) \tag{2-2}$

以上是周志華——《機(jī)器學(xué)習(xí)》一書(shū)中對(duì)信息增益的相關(guān)說(shuō)明掖疮。

枯燥的文字說(shuō)明總是會(huì)降低讀者的閱讀欲望，上述符號(hào)也是有點(diǎn)多颗祝，我們不妨拿上面的貸款數(shù)據(jù)來(lái)進(jìn)一步理解下上述信息增益的內(nèi)容：

我們單獨(dú)拿年齡這一個(gè)屬性特征來(lái)計(jì)算其信息增益吧浊闪，其有青年、中年螺戳、老年三個(gè)可能的值搁宾，也就是說(shuō)上述的 $a=年齡$ ， $\{a^1,a^2,...,a^V\}=\{青年,中年,老年\}$ 倔幼，而數(shù)據(jù)樣本集 $D$ 為上述15個(gè)數(shù)據(jù)樣本盖腿，由于年齡有三個(gè)可能的值，所以此時(shí)會(huì)產(chǎn)生三個(gè)分支损同，即 $V=3$ 翩腐。之前我們已經(jīng)計(jì)算得到 $Ent(D)=0.971$ ，現(xiàn)在我們只要計(jì)算出后一項(xiàng) $\sum_{v=1}^V\frac{D^v}{D}Ent(D^v)$ 的值即可得到該屬性特征所對(duì)應(yīng)的信息增益：

通過(guò)數(shù)據(jù)膏燃，我們觀察得到如下信息：

對(duì)于年齡這個(gè)屬性特征來(lái)講茂卦，青年、中年组哩、老年分別有5個(gè)等龙。
5個(gè)青年中有2個(gè)允許貸款，有三個(gè)不允許貸款伶贰；中年中有3個(gè)允許貸款蛛砰，2個(gè)不允許貸款；老年中有4個(gè)允許貸款黍衙，有1個(gè)不允許貸款暴备。

對(duì)此，我們可以計(jì)算：

$\begin{aligned} \sum_{v=1}^V\frac{D^v}{D}Ent(D^v) & = \frac{5}{15}(-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5})\\ & +\frac{5}{15}(-\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}) \\ & +\frac{5}{15}(-\frac{4}{5}log_2\frac{4}{5}-\frac{1}{5}log_2\frac{1}{5}) \\ & = 0.883 \end{aligned}$

對(duì)此们豌，我們的計(jì)算處年齡這個(gè)屬性特征所對(duì)應(yīng)的信息增益值為：

$Gain(D, 年齡) = 0.971-0.883=0.083$

我們可以把后一項(xiàng)的內(nèi)容理解成條件概率涯捻。另外浅妆，信息增益越大，則其所對(duì)應(yīng)的屬性特征的分類(lèi)能力也就越強(qiáng)障癌，也就是我們應(yīng)當(dāng)優(yōu)先選取的特征凌外。

同理，我們可以計(jì)算出工作涛浙、房子康辑、信用屬性特征所對(duì)應(yīng)的信息增益：

$\begin{aligned} & Gain(D, 工作)=0.324 \\ & Gain(D, 房子)=0.420 \\ & Gain(D, 信用)=0.363 \end{aligned}$

我們比較哥哥屬性特征的信息增益值，可以發(fā)現(xiàn)房子這個(gè)屬性特征最大轿亮，所以它應(yīng)該是我們優(yōu)先選擇的屬性特征疮薇。

了解了信息增益的計(jì)算及其意義，下面我們來(lái)通過(guò)代碼計(jì)算一下（代碼含義見(jiàn)注釋?zhuān)?/p>

import numpy as np
import pandas as pd

np.__version__
pd.__version__

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：創(chuàng)建訓(xùn)數(shù)據(jù)集
"""
def establish_data():
    data = [[0, 0, 0, 0, 'N'],         # 樣本數(shù)據(jù)集相關(guān)信息我注，前面幾項(xiàng)代表屬性特征按咒，最后一項(xiàng)表示是否放款
            [0, 0, 0, 1, 'N'],
            [0, 1, 0, 1, 'Y'],
            [0, 1, 1, 0, 'Y'],
            [0, 0, 0, 0, 'N'],
            [1, 0, 0, 0, 'N'],
            [1, 0, 0, 1, 'N'],
            [1, 1, 1, 1, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [2, 0, 1, 2, 'Y'],
            [2, 0, 1, 1, 'Y'],
            [2, 1, 0, 1, 'Y'],
            [2, 1, 0, 2, 'Y'],
            [2, 0, 0, 0, 'N']]
    return np.array(data)

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：計(jì)算信息熵
"""
def calc_information_entropy(data):
    data_number, _ = data.shape
    information_entropy = 0
    for item in pd.DataFrame(data).groupby(_ - 1):
        proportion = item[1].shape[0] / data_number
        information_entropy += - proportion * np.log2(proportion)
    return information_entropy

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：找出對(duì)應(yīng)屬性特征值的樣本，比如找出所有年紀(jì)為青年的樣本數(shù)據(jù)集
"""
def handle_data(data, axis, value):
    result_data = list()
    for item in data:
        if item[axis] == value: result_data.append(item)
    return result_data

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：計(jì)算最大的信息增益但骨，并輸出其所對(duì)應(yīng)的特征索引
"""
def calc_information_gain(data):
    feature_number = data.shape[1] - 1                    # 屬性特征的數(shù)量
    base_entropy = calc_information_entropy(data)                 # 計(jì)算總體數(shù)據(jù)集的信息熵
    max_information_gain, best_feature = 0.0, -1                 # 初始化最大信息增益和對(duì)應(yīng)的特征索引
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy = 0.0
        for set_item in feat_set:                         # 計(jì)算屬性特征劃分后的信息增益
            sub_data = handle_data(data, index, set_item)
            proportion = len(sub_data) / float(data.shape[0])           # 計(jì)算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
        temp_information_gain = base_entropy - new_entropy                     # 計(jì)算信息增益
        print("第%d個(gè)屬性特征所對(duì)應(yīng)的的增益為%.3f" % (index + 1, temp_information_gain))            # 輸出每個(gè)特征的信息增益
        if (temp_information_gain > max_information_gain):
            max_information_gain, best_feature = temp_information_gain, index       # 更新信息增益励七，確定的最大的信息增益對(duì)應(yīng)的索引
    return best_feature

if __name__ == "__main__":
    data = establish_data()
    print("屬性特征對(duì)應(yīng)的最大的信息增益對(duì)應(yīng)的索引為：%d" % calc_information_gain(data))

運(yùn)行上述代碼，可見(jiàn)輸出的各個(gè)屬性特征的信息增益奔缠，以及最大信息增益對(duì)應(yīng)的特征索引：

image

可以發(fā)現(xiàn)掠抬，和我們手動(dòng)計(jì)算的如出一轍，所以此時(shí)我們應(yīng)當(dāng)優(yōu)先選取索引為2的屬性特征作為決策標(biāo)準(zhǔn)校哎，也就是房子两波。

2.2 信息增益比（增益率）

我們使用信息增益作為選取特征指標(biāo)的時(shí)候，存在偏向于選擇取值較多的特征的問(wèn)題闷哆。

比如我們將id作為上述數(shù)據(jù)集的一個(gè)分類(lèi)屬性雨女，通過(guò)計(jì)算可以發(fā)現(xiàn)該信息增益最大，但實(shí)際上該id對(duì)類(lèi)別不具有什么分類(lèi)能力阳准，所以這樣得到的決策樹(shù)不具有泛化能力，無(wú)法對(duì)新樣本進(jìn)行有效預(yù)測(cè)馏臭。

為了解決信息增益存在的這個(gè)問(wèn)題野蝇，我們就引入了信息增益比（增益率）的概念，著名的C4.5算法就是用“增益率”來(lái)作為選取最優(yōu)劃分屬性括儒。增益率定義為：

$Gain_ratio(D, a)=\frac{Gain(D, a)}{IV(a)} \tag{2-3}$

$其中绕沈，IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|} \tag{2-4}$

$IV(a)$ 稱(chēng)為 $a$ 的“固有值”（intrinsic value）。通常 $a$ 的取值數(shù)目越多帮寻，則 $IV(a)$ 的值會(huì)越大乍狐。其中的 $a$ 的取值比如說(shuō)：上述的年紀(jì)有青年、中年固逗、老年三種取值浅蚪。

對(duì)于上述的貸款數(shù)據(jù)集來(lái)說(shuō)藕帜，信用情況有一般、好和非常好三種惜傲，比例分為是 $\frac{5}{15}洽故、\frac{6}{15}、\frac{4}{15}$ 盗誊。毒刺时甚，我們可以計(jì)算信用情況的“固有值”：

$\begin{aligned} IV(信用) & =-\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|} \\ & =-\frac{5}{15}log_2\frac{5}{15}-\frac{6}{15}log_2\frac{6}{15}-\frac{4}{15}log_2\frac{4}{15} \\ & = 1.566 \end{aligned}$

所以，對(duì)于信用屬性來(lái)講哈踱，其增益率為：

$\begin{aligned} Gain\_ratio(D, 信用) & =\frac{Gain(D, 信用)}{IV(信用)} \\ & = \frac{0.363}{1.566} \\ & = 0.232 \end{aligned}$

同理荒适，我們可以計(jì)算出其他屬性特征的增益率：

$\begin{aligned} Gain\_ratio(D, 年齡) & =0.052 \\ Gain\_ratio(D, 工作) & =0.352 \\ Gain\_ratio(D, 房子) & =0.433 \\ \end{aligned}$

計(jì)算增益率的具體代碼可參考如下：

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：計(jì)算增益率
"""
def calc_gain_ratio(data):
    feature_number = data.shape[1] - 1                    # 屬性特征的數(shù)量
    base_entropy = calc_information_entropy(data)                 # 計(jì)算總體數(shù)據(jù)集的信息熵
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy, iv = 0.0, 0.0
        for set_item in feat_set:                         # 計(jì)算屬性特征劃分后的信息增益
            sub_data = handle_data(data, index, set_item)
            proportion = len(sub_data) / float(data.shape[0])           # 計(jì)算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
            iv += -proportion * np.log2(proportion)
        temp_information_gain = base_entropy - new_entropy                     # 計(jì)算信息增益
        gain_ratio = temp_information_gain / iv
        print("第%d個(gè)屬性特征所對(duì)應(yīng)的增益率為%.3f，信息增益為%.3f" % (index + 1, gain_ratio, temp_information_gain))            # 輸出每個(gè)特征的信息增益

運(yùn)行結(jié)果如下：

image

在C4.5算法中开镣，并不是直接單一的使用增益率來(lái)對(duì)屬性特征的選取進(jìn)行決策刀诬，而是先在信息增益中選取高于平均水平的屬性作為候選，然后從候選中選取增益率最高的哑子。

關(guān)于C4.5算法舅列，我們后期會(huì)講到。

2.3 基尼指數(shù)

基尼指數(shù)是另外一種選取屬性的指標(biāo)卧蜓。

前面我們提到了帐要，信息熵是描述數(shù)據(jù)樣本純度一個(gè)標(biāo)準(zhǔn)，而在基尼指數(shù)中的基尼值同樣可以體現(xiàn)數(shù)據(jù)樣本的純度弥奸。數(shù)據(jù)樣本集 $D$ 的基尼值可以用 $Gini(D)$ 來(lái)表示（其中 $k$ 表示有 $k$ 個(gè)標(biāo)簽結(jié)果）：

$Gini(D)=1-\sum_{k=1}^{|y|}p_k^2 \tag{2-5}$

基尼值 $Gini(D)$ 越小榨惠，說(shuō)明數(shù)據(jù)樣本純度越高。而屬性 $a$ 對(duì)應(yīng)的基尼指數(shù) $Gini\_index(D,a)$ 可以定義為：

$Gini\_index(D, a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v) \tag{2-6}$

我們同樣來(lái)分別計(jì)算下上述貸款數(shù)據(jù)集的基尼指數(shù)盛霎。

對(duì)于信用情況這一屬性特征來(lái)講赠橙，其基尼指數(shù)的手動(dòng)計(jì)算過(guò)程如下所示：

$\begin{aligned} Gini\_index(D, 信用) & = \sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v) \\ & = \frac{5}{15}(1-(\frac{4}{5})^2 - (\frac{1}{5})^2)+\frac{6}{15}(1-(\frac{2}{6})^2 - (\frac{4}{6})^2)+\frac{4}{15}(1-(\frac{4}{4})^2 - (\frac{0}{4})^2) \\ & = \end{aligned}$

對(duì)于其他屬性的基尼指數(shù)，讀者可自行根據(jù)上述過(guò)程進(jìn)行計(jì)算（真的很簡(jiǎn)單）愤炸。關(guān)于基尼指數(shù)的計(jì)算代碼期揪，可參考如下：

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：計(jì)算基尼指數(shù)
"""
def calc_gini_index(data):
    feature_number = data.shape[1] - 1                    # 屬性特征的數(shù)量
    base_entropy = calc_information_entropy(data)                 # 計(jì)算總體數(shù)據(jù)集的信息熵
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy, iv, gini_index = 0.0, 0.0, 0.0
        for set_item in feat_set:                         # 計(jì)算屬性特征劃分后的信息增益
            sub_data = handle_data(data, index, set_item)
            temp_df = pd.DataFrame(sub_data)
            yes_proportion = temp_df[temp_df[temp_df.shape[1]-1] == "Y"].shape[0] / len(sub_data)
            gini_value = 1 - (yes_proportion ** 2) - ((1- yes_proportion) ** 2)
            proportion = len(sub_data) / float(data.shape[0])           # 計(jì)算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
            iv += -proportion * np.log2(proportion)
            gini_index += gini_value * proportion     # 計(jì)算基尼指數(shù)
        temp_information_gain = base_entropy - new_entropy                     # 計(jì)算信息增益
        gain_ratio = temp_information_gain / iv
        print("第%d個(gè)屬性特征所對(duì)應(yīng)的信息增益為%.3f,增益率為%.3f， 基尼指數(shù)為%.3f" % (index + 1, temp_information_gain, gain_ratio, gini_index))

運(yùn)行結(jié)果：

image

以上就是基尼指數(shù)的計(jì)算及其相關(guān)代碼规个，一般來(lái)講凤薛，基尼指數(shù)越小就優(yōu)先被劃分。

上述內(nèi)容的完整代碼如下：

import numpy as np
import pandas as pd

np.__version__
pd.__version__

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：創(chuàng)建訓(xùn)數(shù)據(jù)集
"""
def establish_data():
    data = [[0, 0, 0, 0, 'N'],         # 樣本數(shù)據(jù)集相關(guān)信息诞仓，前面幾項(xiàng)代表屬性特征缤苫，最后一項(xiàng)表示是否放款
            [0, 0, 0, 1, 'N'],
            [0, 1, 0, 1, 'Y'],
            [0, 1, 1, 0, 'Y'],
            [0, 0, 0, 0, 'N'],
            [1, 0, 0, 0, 'N'],
            [1, 0, 0, 1, 'N'],
            [1, 1, 1, 1, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [2, 0, 1, 2, 'Y'],
            [2, 0, 1, 1, 'Y'],
            [2, 1, 0, 1, 'Y'],
            [2, 1, 0, 2, 'Y'],
            [2, 0, 0, 0, 'N']]
    return np.array(data)

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：計(jì)算信息熵
"""
def calc_information_entropy(data):
    data_number, _ = data.shape
    information_entropy = 0
    for item in pd.DataFrame(data).groupby(_ - 1):
        proportion = item[1].shape[0] / data_number
        information_entropy += - proportion * np.log2(proportion)
    return information_entropy

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：找出對(duì)應(yīng)屬性特征值的樣本，比如找出所有年紀(jì)為青年的樣本數(shù)據(jù)集
"""
def handle_data(data, axis, value):
    result_data = list()
    for item in data:
        if item[axis] == value: result_data.append(item)
    return result_data

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：計(jì)算最大的信息增益墅拭，并輸出其所對(duì)應(yīng)的特征索引
"""
def calc_information_gain(data):
    feature_number = data.shape[1] - 1                    # 屬性特征的數(shù)量
    base_entropy = calc_information_entropy(data)                 # 計(jì)算總體數(shù)據(jù)集的信息熵
    max_information_gain, best_feature = 0.0, -1                 # 初始化最大信息增益和對(duì)應(yīng)的特征索引
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy = 0.0
        for set_item in feat_set:                         # 計(jì)算屬性特征劃分后的信息增益
            sub_data = handle_data(data, index, set_item)
            proportion = len(sub_data) / float(data.shape[0])           # 計(jì)算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
        temp_information_gain = base_entropy - new_entropy                     # 計(jì)算信息增益
        print("第%d個(gè)屬性特征所對(duì)應(yīng)的的增益為%.3f" % (index + 1, temp_information_gain))            # 輸出每個(gè)特征的信息增益
        if (temp_information_gain > max_information_gain):
            max_information_gain, best_feature = temp_information_gain, index       # 更新信息增益活玲，確定的最大的信息增益對(duì)應(yīng)的索引
    return best_feature

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：計(jì)算增益率
"""
def calc_gain_ratio(data):
    feature_number = data.shape[1] - 1                    # 屬性特征的數(shù)量
    base_entropy = calc_information_entropy(data)                 # 計(jì)算總體數(shù)據(jù)集的信息熵
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy, iv = 0.0, 0.0
        for set_item in feat_set:                         # 計(jì)算屬性特征劃分后的信息增益
            sub_data = handle_data(data, index, set_item)
            proportion = len(sub_data) / float(data.shape[0])           # 計(jì)算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
            iv += -proportion * np.log2(proportion)
        temp_information_gain = base_entropy - new_entropy                     # 計(jì)算信息增益
        gain_ratio = temp_information_gain / iv
        print("第%d個(gè)屬性特征所對(duì)應(yīng)的增益率為%.3f，信息增益為%.3f" % (index + 1, gain_ratio, temp_information_gain))            # 輸出每個(gè)特征的信息增益

"""
    Author: Taoye
    微信公眾號(hào): 玩世不恭的Coder
    Explain：計(jì)算基尼指數(shù)
"""
def calc_gini_index(data):
    feature_number = data.shape[1] - 1                    # 屬性特征的數(shù)量
    base_entropy = calc_information_entropy(data)                 # 計(jì)算總體數(shù)據(jù)集的信息熵
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy, iv, gini_index = 0.0, 0.0, 0.0
        for set_item in feat_set:                         # 計(jì)算屬性特征劃分后的信息增益
            sub_data = handle_data(data, index, set_item)
            temp_df = pd.DataFrame(sub_data)
            yes_proportion = temp_df[temp_df[temp_df.shape[1]-1] == "Y"].shape[0] / len(sub_data)
            gini_value = 1 - (yes_proportion ** 2) - ((1- yes_proportion) ** 2)
            proportion = len(sub_data) / float(data.shape[0])           # 計(jì)算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
            iv += -proportion * np.log2(proportion)
            gini_index += gini_value * proportion
        temp_information_gain = base_entropy - new_entropy                     # 計(jì)算信息增益
        gain_ratio = temp_information_gain / iv
        print("第%d個(gè)屬性特征所對(duì)應(yīng)的信息增益為%.3f,增益率為%.3f， 基尼指數(shù)為%.3f" % (index + 1, temp_information_gain, gain_ratio, gini_index))
        
if __name__ == "__main__":
    data = establish_data()
    calc_gini_index(data)

優(yōu)先選取屬性特征的指標(biāo)主要有三個(gè)舒憾，分別是信息增益镀钓、增益率、基尼指數(shù)珍剑。對(duì)上述內(nèi)容做個(gè)簡(jiǎn)單的總結(jié)吧：

屬性特征的信息增益越高掸宛，按道理來(lái)講應(yīng)當(dāng)被優(yōu)先選取，常用于 $ID3$ 算法
屬性特征的增益率越高招拙，按道理來(lái)講應(yīng)當(dāng)被優(yōu)先選取唧瘾，常用與 $C4.5$ 算法
屬性特征的尼基指數(shù)低，按道理來(lái)講應(yīng)當(dāng)被優(yōu)先選取别凤，常用于 $CART$ 算法

本文主要是決策樹(shù)的理論部分內(nèi)容饰序，介紹了什么決策樹(shù)，以及生成決策樹(shù)時(shí)所需要優(yōu)先選取的三種決策標(biāo)準(zhǔn)规哪。有學(xué)習(xí)的過(guò)SVM求豫，或閱讀過(guò)Taoye之前寫(xiě)的幾篇SVM內(nèi)容的文章可以發(fā)現(xiàn)，決策樹(shù)相對(duì)于SVM來(lái)講要簡(jiǎn)單很多诉稍，沒(méi)有太多且復(fù)雜的公式推導(dǎo)蝠嘉。關(guān)于決策樹(shù)的其他內(nèi)容，比如決策樹(shù)的生成杯巨、可視化蚤告、剪枝等，我們放在后面幾篇文章來(lái)寫(xiě)服爷。

我是Taoye杜恰，愛(ài)專(zhuān)研，愛(ài)分享仍源，熱衷于各種技術(shù)心褐，學(xué)習(xí)之余喜歡下象棋、聽(tīng)音樂(lè)笼踩、聊動(dòng)漫逗爹，希望借此一畝三分地記錄自己的成長(zhǎng)過(guò)程以及生活點(diǎn)滴，也希望能結(jié)實(shí)更多志同道合的圈內(nèi)朋友嚎于，更多內(nèi)容歡迎來(lái)訪微信公主號(hào)：玩世不恭的Coder掘而。

參考資料：

[1] 《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》：Peter Harrington 人民郵電出版社
[2] 《統(tǒng)計(jì)學(xué)習(xí)方法》：李航第二版清華大學(xué)出版社
[3] 《機(jī)器學(xué)習(xí)》：周志華清華大學(xué)出版社

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市泥栖，隨后出現(xiàn)的幾起案子簇宽，更是在濱河造成了極大的恐慌，老刑警劉巖吧享，帶你破解...
沈念sama閱讀 211,042評(píng)論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件魏割，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡钢颂，警方通過(guò)查閱死者的電腦和手機(jī)钞它，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 89,996評(píng)論 2贊 384
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)殊鞭，“玉大人遭垛，你說(shuō)我怎么就攤上這事〔俨樱” “怎么了锯仪？”我有些...
開(kāi)封第一講書(shū)人閱讀 156,674評(píng)論 0贊 345
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)牲尺。經(jīng)常有香客問(wèn)我卵酪，道長(zhǎng)，這世上最難降的妖魔是什么谤碳？我笑而不...
開(kāi)封第一講書(shū)人閱讀 56,340評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任溃卡，我火速辦了婚禮，結(jié)果婚禮上蜒简，老公的妹妹穿的比我還像新娘瘸羡。我一直安慰自己，他們只是感情好搓茬，可當(dāng)我...
茶點(diǎn)故事閱讀 65,404評(píng)論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布犹赖。她就那樣靜靜地躺著，像睡著了一般卷仑。火紅的嫁衣襯著肌膚如雪峻村。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 49,749評(píng)論 1贊 289
城市分裂傳說(shuō)
那天锡凝，我揣著相機(jī)與錄音粘昨，去河邊找鬼。笑死，一個(gè)胖子當(dāng)著我的面吹牛张肾，可吹牛的內(nèi)容都是我干的芭析。我是一名探鬼主播，決...
沈念sama閱讀 38,902評(píng)論 3贊 405
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼吞瞪，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼馁启！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起芍秆，我...
開(kāi)封第一講書(shū)人閱讀 37,662評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤惯疙，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后浪听，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體螟碎，經(jīng)...
沈念sama閱讀 44,110評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,451評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年迹栓，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了掉分。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,577評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡克伊，死狀恐怖酥郭，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情愿吹，我是刑警寧澤珊豹，帶...
沈念sama閱讀 34,258評(píng)論 4贊 328
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布滩褥，位于F島的核電站剪撬，受9級(jí)特大地震影響法希，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜坷衍，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,848評(píng)論 3贊 312
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一寝优、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧枫耳，春花似錦乏矾、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,726評(píng)論 0贊 21
一樁弒父案钻心，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至铅协，卻和暖如春捷沸，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背狐史。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,952評(píng)論 1贊 264
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工痒给，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留坯钦，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,271評(píng)論 2贊 360
代替公主和親
正文我出身青樓侈玄，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親吟温。傳聞我的和親對(duì)象是個(gè)殘疾皇子序仙，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,452評(píng)論 2贊 348

《Machine Learning in Action》—— Taoye給你講講決策樹(shù)到底是支什么“鬼”

《Machine Learning in Action》—— Taoye給你講講決策樹(shù)到底是支什么“鬼”

一、什么是決策樹(shù)

二噪裕、屬性特征的選擇

2.1 信息增益

2.2 信息增益比（增益率）

2.3 基尼指數(shù)

推薦閱讀更多精彩內(nèi)容