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

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

5.1.1 決策樹模型

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

決策樹模型

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

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

5.1.3 決策樹與條件概率分布

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

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

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

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

當(dāng)損失函數(shù)確定以后士袄，學(xué)習(xí)問(wèn)題變?yōu)樵趽p失函數(shù)意義下選擇最優(yōu)決策樹的問(wèn)題悲关。因?yàn)閺乃锌赡艿臎Q策樹中選取最優(yōu)決策樹是NP完全問(wèn)題，所以現(xiàn)實(shí)中的決策樹學(xué)習(xí)通常采用啟發(fā)式方法娄柳。這樣得到的決策樹是次最優(yōu)(sub-optimal)的寓辱。

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

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

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

可以看出堪伍，決策樹學(xué)習(xí)算法包含特征選擇、決策樹生成與決策樹剪枝的過(guò)程觅闽。決策樹的剪枝對(duì)應(yīng)于模型的全局選擇帝雇，而決策樹的生成對(duì)應(yīng)于模型的局部選擇。
決策樹學(xué)習(xí)的常用算法有ID3蛉拙、C4.5和CART尸闸。

5.2 特征選擇

5.2.1 特征選擇問(wèn)題

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

5.2.2 信息增益

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

條件熵：

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

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

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

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

5.2.3 信息增益比

信息增益值的大小是相對(duì)于訓(xùn)練數(shù)據(jù)集而言的售碳，并沒有絕對(duì)意義。
當(dāng)訓(xùn)練數(shù)據(jù)集的經(jīng)驗(yàn)熵大的時(shí)候绞呈，信息增益值會(huì)偏大贸人，反之，信息增益值會(huì)偏小佃声。
使用信息增益比可以對(duì)這一問(wèn)題進(jìn)行校正艺智。
信息增益比的定義：

5.3 決策樹的生成

5.3.1 ID3算法

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

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

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

5.3.2 C4.5的生成算法

C4.5 算法與ID3算法相似，C4.5算法對(duì)ID3算法進(jìn)行了改進(jìn)评甜，在生成過(guò)程中灰粮，用信息增益比來(lái)選擇特征。

5.4 決策樹的剪枝

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

決策樹的剪枝往往通過(guò)極小化決策樹整體的損失函數(shù)或代價(jià)函數(shù)來(lái)實(shí)現(xiàn)蓖乘。

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

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

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

可以看出，決策樹生成只考慮了通過(guò)提高信息增益對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行更好的你和刊咳，而決策樹剪枝通過(guò)優(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é)點(diǎn)特征的取值為“是”和“否”顿颅，左分支是取值“是”的分支缸濒，右分支是取值為“否”的分支。
這樣的決策樹等價(jià)于遞歸地二分每個(gè)特征粱腻，將輸入空間（特征空間）劃分為有限個(gè)單元庇配，并在這些單元上確定預(yù)測(cè)的概率分布。

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

5.5.1 CART生成

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

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

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

5.5.2 CART剪枝

CART剪枝算法從“完全生長(zhǎng)”的決策樹的底端剪去一些子樹，使決策樹變星貌拧（模型變簡(jiǎn)單）裹纳，從而能夠?qū)ξ粗獢?shù)據(jù)有更準(zhǔn)確的預(yù)測(cè)。CART剪枝算法由兩部組成：首先從生成算法產(chǎn)生的決策樹底端開始不斷剪枝归斤，直到的根結(jié)點(diǎn)痊夭，形成一個(gè)子樹序列; 然后通過(guò)交叉驗(yàn)證法在獨(dú)立的驗(yàn)證數(shù)據(jù)集上對(duì)子樹序列進(jìn)行測(cè)試，從中選擇最優(yōu)子樹脏里。

1. 剪枝，形成一個(gè)子樹序列

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

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

本章概要

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

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

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

   
   
   
   

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

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

4. 決策樹的生成

   
   

5. 決策樹的剪枝