決策樹是一種基本的分類與回歸方法
決策樹模型呈樹形結(jié)構(gòu)，在分類問題中，表示基于特征對實例進(jìn)行分類的過程，可以被認(rèn)為是if-then規(guī)則的集合，也可以認(rèn)為是定義在特征空間與類空間上的條件概率分布。
主要優(yōu)點是：模型具有可讀性，分類速度快。

5.1 決策樹模型與學(xué)習(xí)

5.1.1 決策樹模型

分類決策樹模型是一種描述對實例進(jìn)行分類的樹形結(jié)構(gòu)，決策樹由結(jié)點(node)和有向邊(directed edge)組成。結(jié)點有兩種類型：內(nèi)部節(jié)點(internal node) 和葉節(jié)點(leaf node)。內(nèi)部結(jié)點表示一個特征或?qū)傩?，葉節(jié)點表示一個類。

決策樹模型

5.1.2 決策樹與if-then規(guī)則

可以將決策樹看成一個if-then規(guī)則的集合。
決策樹的路徑或其對應(yīng)的if-then規(guī)則集合具有一個重要的性質(zhì)：互斥且完備。

5.1.3 決策樹與條件概率分布

決策樹還表示給定特征條件下類的條件概率分布。這一條件概率分布定義在特征空間的一個劃分(partition)上。

5.1.4 決策樹學(xué)習(xí)

決策樹學(xué)習(xí)本質(zhì)上是從訓(xùn)練數(shù)據(jù)集中歸納出一組分類規(guī)則，與訓(xùn)練數(shù)據(jù)集不相矛盾的決策樹可能有多個，也可能一個也沒有。我們需要的是一個與訓(xùn)練數(shù)據(jù)矛盾較小的決策樹，同時具有很好的泛化能力。

決策樹學(xué)習(xí)用損失函數(shù)表示這一目標(biāo)，通常為正則化的極大似然函數(shù)。

當(dāng)損失函數(shù)確定以后，學(xué)習(xí)問題變?yōu)樵趽p失函數(shù)意義下選擇最優(yōu)決策樹的問題。因為從所有可能的決策樹中選取最優(yōu)決策樹是NP完全問題，所以現(xiàn)實中的決策樹學(xué)習(xí)通常采用啟發(fā)式方法。這樣得到的決策樹是次最優(yōu)(sub-optimal)的。

決策樹學(xué)習(xí)的算法通常是一個遞歸地選擇最優(yōu)特征，并根據(jù)該特征對訓(xùn)練數(shù)據(jù)進(jìn)行分割，使得對各個子數(shù)據(jù)集有一個最好的分類的過程。

為了防止過擬合，需要對已生成的樹自下而上進(jìn)行剪枝，將樹變得更簡單，從而使它具有更好的泛化能力。（即去掉過于細(xì)分的葉節(jié)點，使其回退到父節(jié)點）。

如果特征數(shù)量多，也可以在開始學(xué)習(xí)時對特征進(jìn)行選擇。

可以看出，決策樹學(xué)習(xí)算法包含特征選擇、決策樹生成與決策樹剪枝的過程。決策樹的剪枝對應(yīng)于模型的全局選擇，而決策樹的生成對應(yīng)于模型的局部選擇。
決策樹學(xué)習(xí)的常用算法有ID3、C4.5和CART。

5.2 特征選擇

5.2.1 特征選擇問題

特征選擇在于選取對訓(xùn)練數(shù)據(jù)具有分類能力的特征。
通常特征選擇的準(zhǔn)則是信息增益或信息增益比。

5.2.2 信息增益

首先給出熵與條件熵的定義。
在信息論與概率統(tǒng)計中，熵(entropy)是表示隨機(jī)變量不確定性的度量。設(shè)X是一個取有限個值的離散隨機(jī)變量，其概率分布為

條件熵：

當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計(特別是極大似然估計)得到時，所對應(yīng)的熵與條件熵分別被稱為經(jīng)驗熵(empirical entropy)和經(jīng)驗條件熵(empirical conditional entropy)。

信息增益表示得知特征X的信息而使得類Y的信息的不確定性減少的程度。

信息增益(information gain)的定義：

決策樹中的信息增益等價于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。
根據(jù)信息增益準(zhǔn)則的特征選擇方法是：對訓(xùn)練數(shù)據(jù)集（或子集）D，計算其每個特征的信息增益，并比較它們的大小，選擇信息增益最大的特征。
信息增益的算法：

5.2.3 信息增益比

信息增益值的大小是相對于訓(xùn)練數(shù)據(jù)集而言的，并沒有絕對意義。
當(dāng)訓(xùn)練數(shù)據(jù)集的經(jīng)驗熵大的時候，信息增益值會偏大，反之，信息增益值會偏小。
使用信息增益比可以對這一問題進(jìn)行校正。
信息增益比的定義：

5.3 決策樹的生成

5.3.1 ID3算法

ID3算法的核心是在決策樹的各個節(jié)點上應(yīng)用信息增益準(zhǔn)則選擇特征，遞歸地構(gòu)建決策樹。
具體方法：從根節(jié)點開始，對結(jié)點計算所有可能的特征的信息增益，選擇信息增益最大的特征作為結(jié)點的特征，由該特征的不同取值建立子結(jié)點，再對子結(jié)點遞歸地調(diào)用以上方法，構(gòu)建決策樹；直到所有特征的信息增益均很小或沒有特征可以選擇為止。

ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇。
ID3算法：

ID3算法只有樹的生成，所以該算法生成的樹容易產(chǎn)生過擬合。

5.3.2 C4.5的生成算法

C4.5 算法與ID3算法相似，C4.5算法對ID3算法進(jìn)行了改進(jìn)，在生成過程中，用信息增益比來選擇特征。

5.4 決策樹的剪枝

在決策樹學(xué)習(xí)中將已生成的樹進(jìn)行簡化的過程稱為剪枝(pruning). 具體地，剪枝從已生成的樹熵裁掉一些子樹或葉節(jié)點，并將其根節(jié)點或父結(jié)點作為新的葉節(jié)點，從而簡化分類樹模型。

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

在損失函數(shù)中，將式(5.11)有段的第一項記作

較大的促使選擇較為簡單的模型，反之選擇較為復(fù)雜的模型

剪枝就是當(dāng)確定時，選擇損失函數(shù)最小的模型，即損失函數(shù)最小的子樹。

可以看出，決策樹生成只考慮了通過提高信息增益對訓(xùn)練數(shù)據(jù)進(jìn)行更好的你和，而決策樹剪枝通過優(yōu)化損失函數(shù)還考慮了減小模型復(fù)雜度。決策樹生成學(xué)習(xí)局部的模型，而決策樹剪枝學(xué)習(xí)整體的模型。

決策樹的剪枝算法：

5.5 CART算法

分類與回歸樹（classif and regression tree，CART）模型由Breiman等人在1984年提出，是應(yīng)用最廣泛的決策樹學(xué)習(xí)方法。
CART同樣由特征選擇、樹的生成及剪枝組成，既可以用于分類也可以用于回歸。
CART是在給定輸入隨機(jī)變量條件下輸出隨機(jī)變量的條件概率分布的學(xué)習(xí)方法。

CART假設(shè)決策樹是二叉樹，內(nèi)部結(jié)點特征的取值為“是”和“否”，左分支是取值“是”的分支，右分支是取值為“否”的分支。
這樣的決策樹等價于遞歸地二分每個特征，將輸入空間（特征空間）劃分為有限個單元，并在這些單元上確定預(yù)測的概率分布。

CART算法由以下兩步組成：
(1) 決策樹生成：基于訓(xùn)練數(shù)據(jù)生成決策樹，生成的決策樹要盡量大；
(2) 決策樹剪枝：用驗證數(shù)據(jù)集對已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹，這時用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。

5.5.1 CART生成

決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。對回歸樹用平方誤差最小化準(zhǔn)則，對分類樹用基尼指數(shù)（Gini index)最小化準(zhǔn)則進(jìn)行特征選擇，生成二叉樹。

1. 回歸樹的生成
   
   
   
   
   
   
   這樣的回歸樹通常稱為最小二乘回歸樹，該算法可被敘述如下：
   
2. 分類樹的生成
   分類樹用基尼指數(shù)選擇最優(yōu)特征，同時決定該特征的最優(yōu)二值切分點。
   首先定義基尼指數(shù)：
   
   
   
   
   基尼指數(shù)表示集合D的不確定性，基尼指數(shù)表示經(jīng)分割后集合D的不確定性。基尼指數(shù)值越大，樣本集合的不確定性也就越大，這一點與熵相似。
   
   二分類中基尼指數(shù)、熵之半和分類誤差率的關(guān)系

CART生成算法可被敘述如下：

5.5.2 CART剪枝

CART剪枝算法從“完全生長”的決策樹的底端剪去一些子樹，使決策樹變?。Ｐ妥兒唵危瑥亩軌?qū)ξ粗獢?shù)據(jù)有更準(zhǔn)確的預(yù)測。CART剪枝算法由兩部組成：首先從生成算法產(chǎn)生的決策樹底端開始不斷剪枝，直到的根結(jié)點，形成一個子樹序列; 然后通過交叉驗證法在獨立的驗證數(shù)據(jù)集上對子樹序列進(jìn)行測試，從中選擇最優(yōu)子樹。

1. 剪枝，形成一個子樹序列

   
   
2. 在剪枝得到的子樹序列中通過交叉驗證選取最優(yōu)子樹
   

現(xiàn)在寫出CART剪枝算法

本章概要

1. 分類決策樹模型是表示基于特征對實例進(jìn)行分類的樹形結(jié)構(gòu)，可以轉(zhuǎn)換成一個if-then規(guī)則的集合，也可以看作是定義在特征空間劃分上的類的條件概率分布。

2. 決策樹學(xué)習(xí)旨在構(gòu)建一個與訓(xùn)練數(shù)據(jù)擬合很好，并且復(fù)雜度小的決策樹。因為該問題是個NP-Complete問題，現(xiàn)實中采用啟發(fā)式方法學(xué)習(xí)次優(yōu)的決策樹。
   決策樹學(xué)習(xí)算法包括3部分：特征選擇、樹的生成和樹的剪枝。常用的算法有ID3、C4.5和CART。

3. 特征選擇的目的在于選取對訓(xùn)練數(shù)據(jù)能夠分類的特征。常用的準(zhǔn)則如下：
   (1) 信息增益(ID3算法采用)

   
   
   
   

   (2) 樣本集合D對特征A的信息增益比(C4.5采用)

   
   
   
   (3) 樣本集合D的基尼指數(shù)(CART采用)
   

4. 決策樹的生成

   
   

5. 決策樹的剪枝