01 決策樹定義

之前我們學習了兩種分類方法：
K近鄰(KNN)
樸素貝葉斯(Naive Bayes)

今天我們來學習另一種分類方法——決策樹

在開始學習之前，先提出一個問題：

這三種分類方法的區(qū)別是什么呢？分別適用什么場景呢？

好了，帶著疑問，我們開始學習決策樹~

決策樹是什么？

它是一種基本的分類與回歸的方法，可以認為是if-then規(guī)則的集合，決策樹分類時，將某結(jié)點的實例強行分到條件概率大的那一類中去。

下面我們主要啊解釋分類決策樹，回歸決策樹在CART算法中有提及，篇幅限制，本文暫不做講解。

它的優(yōu)點是，模型具有可讀性，分類速度快。

決策樹定義

我們用決策樹分類時，從根結(jié)點開始，對實例的某一特征進行測試，根據(jù)測試結(jié)果，將實例分配到子結(jié)點，這時每個子結(jié)點對應著分類特征的一個值，如此遞歸地對實例進行測試并分配，直到達到葉結(jié)點，最后將實例分到葉結(jié)點的類中。

02 決策樹學習

在01節(jié)的末尾，我們概述了決策樹的構(gòu)建過程，這一節(jié)我們更進一步講解決策樹的學習過程。

目標：根據(jù)給定的訓練數(shù)據(jù)集，構(gòu)建一個決策樹模型，使它能夠?qū)嵗M行正確的分類。

本質(zhì)：從訓練數(shù)據(jù)集歸納出一組分類規(guī)則，由訓練數(shù)據(jù)集估計條件概論模型，從而對訓練集有很好的擬合，對未知數(shù)據(jù)有很好的預測。

步驟：

1. 特征選擇
2. 決策樹的生成
3. 決策樹的剪枝

學習過程
可以概括為，遞歸地選擇最優(yōu)特征，并根據(jù)該特征對訓練數(shù)據(jù)進行分割，使得對各個子數(shù)據(jù)集有一個最好的分類。

具體步驟如下：

1. 構(gòu)建根結(jié)點，所有訓練數(shù)據(jù)都放在根結(jié)點
2. 選擇一個最優(yōu)特征，按照此特征將訓練數(shù)據(jù)集分割成子集，使各子集有一個在當前條件下最好的分類
3. 若子集已經(jīng)能被正確分類，該結(jié)點變?yōu)槿~結(jié)點；否則繼續(xù)對這些結(jié)點選擇最優(yōu)特征，分類，如此遞歸下去
4. 每個子集都被分到葉結(jié)點上，決策樹生成
5. step1～4可能對訓練數(shù)據(jù)有很好的分類能力，但對未知數(shù)據(jù)的預測能力較弱（過擬合），于是需要對決策樹進行修剪
6. 去掉過于細分的葉結(jié)點，回退到父結(jié)點甚至更高的結(jié)點，然后將父結(jié)點或更高結(jié)點改為新的葉結(jié)點

常用算法：
ID3
C4.5
CART

03 學習步驟詳解

決策樹學習過程分為三個步驟：特征選擇、決策樹生成、決策樹剪枝。

下面我們詳細講解每個步驟的算法和原理，介紹ID3算法和C4.5算法。由于篇幅限制，CART算法在本文暫不做講解。

1. 特征選擇

目的：選取對訓練數(shù)據(jù)具有分類能力的特征，從而提高決策樹學習效率

準則：
信息增益 (information gain)
信息增益比 (information gain ratio)

信息增益是什么？
定義為，集合D的經(jīng)驗熵H(D)與特征A給定的條件下D的經(jīng)驗條件熵H(D|A)之差

g(D,A) = H(D) - H(D|A)

在熱力學中，熵表示物質(zhì)的混亂程度，在這里，我們可以這樣理解信息增益：表示得知特征X的信息而使得類Y的信息的不確定性減少的程度。信息增益越大，特征的分類能力越強。

如何選擇最優(yōu)特征
我們現(xiàn)在知道信息增益越大，特征的分類能力越強。有了信息增益這個工具，我們自然而然可以選擇最優(yōu)特征了——選擇信息增益最大的特征。

再提一句，以信息增益作為劃分選擇數(shù)據(jù)集的特征，可能存在偏向于選擇取值較多的特征的問題。因此產(chǎn)生了信息增益比這個度量，它規(guī)避了信息增益的問題，定義為：信息增益g(D,A)與訓練數(shù)據(jù)集D關(guān)于特征A的值的熵HA(D)之比。

2. 決策樹的生成

算法核心：在決策樹各個結(jié)點上應用信息增益準則(ID3算法)或信息增益比準則(C4.5算法)選擇特征，遞歸地構(gòu)建決策樹。

過程：從根結(jié)點開始，對結(jié)點計算所有可能特征的信息增益(比)，選擇增益(比)最大的特征作為結(jié)點特征，由該特征的不同取值建立子結(jié)點，再對子結(jié)點遞歸地調(diào)用以上方法，構(gòu)建決策樹，直到所有特征的信息增益均很小或沒有特征可以選擇為止。

ID3算法

C4.5算法

3. 決策樹的剪枝

決策樹的生成算法(ID3, C4.5)，因為過多地考慮提高對訓練數(shù)據(jù)的正確分類，容易產(chǎn)生過擬合。

于是人們想出一個辦法解決過擬合的問題：正則化（控制樹的復雜度），及決策樹的剪枝。

剪枝是將已生成的樹進行簡化的過程：從已生成的樹上裁掉一些子樹或葉結(jié)點，并將根結(jié)點或父結(jié)點作為新的葉結(jié)點，從而簡化分類樹模型。

原理：通過極小化決策樹整體的損失函數(shù)或代價函數(shù)來實現(xiàn)。

決策樹的損失函數(shù)
設樹T的葉結(jié)點有|T|個，t是樹T的葉結(jié)點，該葉結(jié)點有Nt個樣本點，其中k類樣本點Ntk個，Ht(T)為葉結(jié)點t上的經(jīng)驗熵，那么有：

其中：

• C(T)——模型對訓練數(shù)據(jù)的預測誤差（即模型與訓練數(shù)據(jù)的擬合程度）
• |T|——模型的復雜度（即葉結(jié)點個數(shù)）
• alpha——>=0，控制模型擬合程度和復雜度
  • 較大的alpha促使選擇較簡單的模型（樹）
  • 較小的alpha促使選擇較復雜的模型（樹）
  • alpha=0表示只考慮模型與訓練數(shù)據(jù)的擬合程度，不考慮過擬合

剪枝算法

4. 生成和剪枝算法的區(qū)別

決策樹生成：只考慮通過提高信息增益(比)對訓練數(shù)據(jù)進行更好地擬合，容易產(chǎn)生過擬合，相當于用極大似然估計進行模型選擇。

決策樹剪枝：還考慮減小模型復雜度|T|，從而減小過擬合，更好地對未知數(shù)據(jù)進行預測，相當于用正則化極大似然估計進行模型選擇。

04 總結(jié)

今天我們學習了除KNN，Naive Bayes分類方法之外的另一種分類方法：決策樹。

決策樹可以用于分類和回歸，我們主要學習了分類樹。

我們給出了決策樹的定義、學習過程以及過程詳解，介紹了ID3、C4.5、剪枝三種算法。

其中，由于篇幅限制，CART算法（分類與回歸樹算法）沒有介紹。

下期我們將學習邏輯回歸，敬請期待~