1，什么是決策樹？

決策樹是一種機(jī)器學(xué)習(xí)算法，我們可以使用決策樹來處理分類問題。決策樹的決策（分類）過程可以用一個(gè)倒著的樹形結(jié)構(gòu)來形象的表達(dá)出來，因此得名決策樹。

決策樹是一個(gè)包含根節(jié)點(diǎn)、若干內(nèi)部節(jié)點(diǎn)和若干葉子節(jié)點(diǎn)的樹形結(jié)構(gòu)。決策樹的根節(jié)點(diǎn)包含樣本全集，內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)特征屬性，葉子節(jié)點(diǎn)表示決策的結(jié)果。

使用決策樹進(jìn)行判斷時(shí)，從根節(jié)點(diǎn)開始，測(cè)試待分類數(shù)據(jù)的特征屬性值，應(yīng)該走哪條分支，循環(huán)這樣判斷，直到葉子節(jié)點(diǎn)為止。最終到達(dá)的這個(gè)葉子節(jié)點(diǎn)，就是決策樹的最終決策結(jié)果。

決策樹模型的學(xué)習(xí)過程一般有三個(gè)階段：

• 特征選擇：選擇哪些屬性作為樹的節(jié)點(diǎn)。
• 生成決策樹：生成樹形結(jié)構(gòu)。
• 決策樹剪枝：是決策樹的一種優(yōu)化手段，比如剪去一些不必要的屬性節(jié)點(diǎn)。一般有“預(yù)剪枝”和“后剪枝”兩種。
  • 剪枝的目的是防止過擬合現(xiàn)象，提高泛化能力。
  • 預(yù)剪枝是在決策樹的生成過程中就進(jìn)行剪枝，缺點(diǎn)是有可能造成欠擬合。
  • 后剪枝是在決策樹生成之后再進(jìn)行剪枝，缺點(diǎn)是計(jì)算量較大。

我們來看一個(gè)例子。

比如我們根據(jù)天氣是否晴朗和是否刮風(fēng)來決定是否去踢球？當(dāng)天氣晴朗并且不刮風(fēng)的時(shí)候，我們才去踢球。

此時(shí)，就可以將這個(gè)決策過程用一個(gè)樹形結(jié)構(gòu)來表示，如下：

這就是一顆最簡(jiǎn)單的決策樹，我們可以用它來判斷是否要去踢球。最上方是樹的根節(jié)點(diǎn)，最下方是樹的葉子節(jié)點(diǎn)。方框里是判斷條件，圓形中是決策的結(jié)果。

當(dāng)然，實(shí)際的使用過程中，判斷條件并不會(huì)這么簡(jiǎn)單，也不會(huì)讓我們自己手動(dòng)畫圖。實(shí)際應(yīng)用中，我們會(huì)讓程序自動(dòng)的，從一堆樣本數(shù)據(jù)集中構(gòu)造出這顆決策樹，這個(gè)程序自動(dòng)構(gòu)建決策樹的過程就是機(jī)器學(xué)習(xí)的過程。

最終構(gòu)造出來的這棵決策樹就是機(jī)器學(xué)習(xí)的結(jié)果，叫做模型。最后，我們可以向模型中輸入一些屬性條件，讓模型給出我們判斷結(jié)果。

2，如何構(gòu)建決策樹？

比如我們有如下數(shù)據(jù)集：

可以看到這個(gè)表格中有4 行（第一行表頭不算），4 列數(shù)據(jù)。

一般在機(jī)器學(xué)習(xí)中，最后一列稱為目標(biāo)(target)，前邊的列都稱為特征(features)。

我們要根據(jù)這個(gè)數(shù)據(jù)集，來構(gòu)建一顆決策樹，那如何構(gòu)建呢？

首先，需要確定使用哪個(gè)屬性作為第一個(gè)判斷條件，是先判斷天氣晴朗，還是先判斷是否刮風(fēng)？也就是，讓天氣晴朗作為樹的根節(jié)點(diǎn)，還是讓是否刮風(fēng)作為樹的根節(jié)點(diǎn)？

解決這個(gè)問題需要用到信息熵和信息純度的概念，我們先來看什么是信息熵。

3，什么是信息熵？

1948 年，克勞德·香濃在他的論文“通信的數(shù)學(xué)原理”中提到了信息熵（一般用H 表示），度量信息熵的單位是比特。

就是說，信息量的多少是可以量化的。一條信息量的多少與信息的不確定性有關(guān)，可以認(rèn)為，信息量就等于不確定性的多少（信息的不確定度）。

信息熵的計(jì)算公式如下：

該公式的含義是：

• 待分類的事物可以分在多個(gè)分類中，這里的n 就是分類的數(shù)目。
• H(X) 表示熵，數(shù)學(xué)含義是，所有類別包含的信息期望值。
• -㏒p(Xì)表示符號(hào)的信息值，p(Xì) 是選擇該分類的概率。
• 公式中的log 一般以2 為底。

總之，就是要知道，信息量的多少是可以用數(shù)學(xué)公式計(jì)算出來的，用信息論中的專業(yè)術(shù)語就叫做信息熵。信息熵越大，信息量也就越大。

3.1，計(jì)算信息熵

那么我們就來計(jì)算一下上面表格數(shù)據(jù)的信息熵。我們只關(guān)注“結(jié)果”那一列：

根據(jù)表格，我們可以知道，所有的分類共有2 種，也就是“去” 和“不去”，“去”出現(xiàn)了1 次，“不去”出現(xiàn)了3 次。

分別計(jì)算“去” 和“不去” 出現(xiàn)的概率：

• P(去) = 1 / 4 = 0.25
• P(不去) = 3 / 4 = 0.75

然后，根據(jù)熵的計(jì)算公式來計(jì)算“去”和“不去” 的信息熵，其中l(wèi)og 以2 為底：

• H(去) = 0.25 * log 0.25 = -0.5
• H(不去) = 0.74 * log 0.75 = -0.31127812445913283

所以，整個(gè)表格含有的信息量就是：

• H(表格) = -(H(去) + H(不去)) = 0.81127812445913283

3.2，用代碼實(shí)現(xiàn)信息熵的計(jì)算

將計(jì)算信息熵的過程用Python 代碼實(shí)現(xiàn)，如下：

import math

# 本函數(shù)用于計(jì)算一組數(shù)據(jù)的信息熵
# data_set 是一個(gè)列表，代表一組數(shù)據(jù)
# data_set 的元素data 也是一個(gè)列表
def calc_ent(data_set):
    labels = {} # 用于統(tǒng)計(jì)每個(gè)label 的數(shù)量
    
    for data in data_set:
        label = data[-1]    # 只用最后一個(gè)元素做計(jì)算
        if label not in labels:
            labels[label] = 0

        labels[label] += 1 

    ent = 0 # 熵
    n = len(data_set)   # 數(shù)據(jù)條數(shù)

    # 計(jì)算信息熵
    for label in labels:
        prob = float(labels[label]) / n # label 的概率
        ent -= prob * math.log(prob, 2) # 根據(jù)信息熵公式計(jì)算

    return ent

下面用該函數(shù)來計(jì)算表格的信息熵：

# 將表格轉(zhuǎn)化為 python 列表
# "yes" 表示"去"
# "no" 表示"不去"
data_set = [['yes'], ['no'], ['no'], ['no']] 
ent = calc_ent(data_set)
print(ent)  # 0.811278124459

可見，用代碼計(jì)算出來的結(jié)果是 0.811278124459，跟我們手算的結(jié)果 0.81127812445913283 是一樣的（保留的小數(shù)位數(shù)不同）。

4，什么是信息純度？

信息的純度與信息熵成反比：

• 信息熵越大，信息量越大，信息越雜亂，純度越低。
• 信息熵越小，信息量越小，信息越規(guī)整，純度越高。

經(jīng)典的“不純度”算法有三種，分別是：

• 信息增益，即 ID3 算法，Information Divergence，該算法由 Ross Quinlan 于1975 年提出，可用于生成二叉樹或多叉樹。
  • ID3 算法會(huì)選擇信息增益最大的屬性來作為屬性的劃分。
• 信息增益率，即 C4.5 算法，是 Ross Quinlan 在ID3 算法的基礎(chǔ)上改進(jìn)而來，可用于生成二叉樹或多叉樹。
• 基尼不純度，即 CART 算法，Classification and Regression Trees，中文為分類回歸樹。
  • 只支持二叉樹，即可用于分類數(shù)，又可用于回歸樹。分類樹用基尼系數(shù)做判斷，回歸樹用偏差做判斷。
  • 基尼系數(shù)本身反應(yīng)了樣本的不確定度。
    • 當(dāng)基尼系數(shù)越小的時(shí)候，樣本之間的差異性越小，不確定程度越低。
    • CART 算法會(huì)選擇基尼系數(shù)最小的屬性作為屬性的劃分。

信息增益是其中最簡(jiǎn)單的一種算法，后兩者都是由它衍生而來。本篇文章中，我們只詳細(xì)介紹信息增益。

基尼系數(shù)是經(jīng)濟(jì)學(xué)中用來衡量一個(gè)國(guó)家收入差距的常用指標(biāo)。當(dāng)基尼系數(shù)大于 0.4 的時(shí)候，說明財(cái)富差異較大?；嵯禂?shù)在 0.2-0.4 之間說明分配合理，財(cái)富差距不大。

5，ID3 算法

ID3 算法也就是信息增益，在根據(jù)某個(gè)屬性劃分?jǐn)?shù)據(jù)集的前后，信息量發(fā)生的變化。

信息增益的計(jì)算公式如下：

該公式的含義：

• 簡(jiǎn)寫就是：G = H(父節(jié)點(diǎn)) - H(所有子節(jié)點(diǎn))
• 也就是：父節(jié)點(diǎn)的信息熵減去所有子節(jié)點(diǎn)的信息熵。
• 所有子節(jié)點(diǎn)的信息熵會(huì)按照子節(jié)點(diǎn)在父節(jié)點(diǎn)中的出現(xiàn)的概率來計(jì)算，這叫做歸一化信息熵。

信息增益的目的在于，將數(shù)據(jù)集劃分之后帶來的純度提升，也就是信息熵的下降。如果數(shù)據(jù)集在根據(jù)某個(gè)屬性劃分之后，能夠獲得最大的信息增益，那么這個(gè)屬性就是最好的選擇。

所以，我們想要找到根節(jié)點(diǎn)，就需要計(jì)算每個(gè)屬性作為根節(jié)點(diǎn)時(shí)的信息增益，那么獲得信息增益最大的那個(gè)屬性，就是根節(jié)點(diǎn)。

5.1，計(jì)算信息增益

為了方便看，我將上面那個(gè)表格放在這里：

我們已經(jīng)知道了，信息增益等于按照某個(gè)屬性劃分前后的信息熵之差。

這個(gè)表格劃分之前的信息熵我們已經(jīng)知道了，就是我們?cè)谏厦嬗?jì)算的結(jié)果：

• H(表格) = 0.81127812445913283。

接下來，我們計(jì)算按照“天氣晴朗”劃分的信息增益。按照“天氣晴朗”劃分后有兩個(gè)表格。

表格1，“天氣晴朗”的值為“是”：

分類共有2 種，也就是“去” 和“不去”，“去”出現(xiàn)了1 次，“不去”出現(xiàn)了1 次。

所以，“去” 和“不去” 出現(xiàn)的概率均為0.5：

• P(去) = P(不去) = 1 / 2 = 0.5

然后，“去”和“不去” 的信息熵，其中l(wèi)og 以2 為底：

• H(去) = H(不去) = 0.5 * log 0.5 = -0.5

所以，表格1 含有的信息量就是：

• H(表格1) = -(H(去) + H(不去)) = 1

表格2，“天氣晴朗”的值為“否”：

所有的分類只有1 種，是“不去”。所以：

• P(不去) = 1

然后，“不去” 的信息熵，其中l(wèi)og 以2 為底：

• H(不去) = 1 * log 1 = 0

所以，表格2 含有的信息量就是：

• H(表格2) = 0

總數(shù)據(jù)共有4 份：

• 表格1 中有2 份，概率為 2/4 = 0.5
• 表格2 中有2 份，概率為 2/4 = 0.5

所以，最終按照“天氣晴朗”劃分的信息增益為：

• G(天氣晴朗) = H(表格) - (0.5*H(表格1) + 0.5*H(表格2)) = H(表格) - 0.5 = 0.31127812445913283。

5.2，ID3 算法的缺點(diǎn)

當(dāng)我們計(jì)算的信息增益多了，你會(huì)發(fā)現(xiàn)，ID3 算法傾向于選擇取值比較多的屬性作為（根）節(jié)點(diǎn)。

但是有的時(shí)候，某些屬性并不會(huì)影響結(jié)果（或者對(duì)結(jié)果的影響不大），那此時(shí)使用ID3 選擇的屬性就不恰當(dāng)了。

為了改進(jìn)ID3 算法的這種缺點(diǎn)，C4.5 算法應(yīng)運(yùn)而生。

6，C4.5 算法

C4.5 算法對(duì)ID3 算法的改進(jìn)點(diǎn)包括：

• 采用信息增益率，而不是信息增益，避免ID3 算法有傾向于選擇取值多的屬性的缺點(diǎn)。
• 加入了剪枝技術(shù)，防止ID3 算法中過擬合情況的出現(xiàn)。
• 對(duì)連續(xù)的屬性進(jìn)行離散化的處理，使得C4.5 算法可以處理連續(xù)屬性的情況，而ID3 只能處理離散型數(shù)據(jù)。
• 處理缺失值，C4.5 也可以針對(duì)數(shù)據(jù)集不完整的情況進(jìn)行處理。

當(dāng)然C4.5 算法也并不是沒有缺點(diǎn)，由于 C4.5算法需要對(duì)數(shù)據(jù)集進(jìn)行多次掃描，所以算法效率相對(duì)較低。

ID3 和C4.5 都是基于信息熵，所以涉及大量的對(duì)數(shù)運(yùn)算。而 CART 算法基于基尼系數(shù)，不涉及對(duì)數(shù)運(yùn)算。

7，CART 算法

CART 算法全稱為分類回歸樹，基于基尼系數(shù)。

基尼系數(shù)的計(jì)算公式如下：

該公式表示的含義是：

• 整個(gè)數(shù)據(jù)集共有 k 個(gè)類別。
• 第 n 個(gè)類別的概率為 Pn。

基尼系數(shù)的效果與熵模型高度近似，而且避免了對(duì)數(shù)運(yùn)算，因此CART 算法的執(zhí)行效率較高。

本篇文章主要介紹了決策樹的基本原理，決策樹的算法一般有三種，分別是ID3 算法，C4.5 算法，CART 算法，其中重點(diǎn)介紹了ID3 算法的計(jì)算過程。

下篇會(huì)介紹如何用決策樹來解決實(shí)際問題。

（完。）