決策樹
優點：模型具有可讀性，分類速度快。
學習時，利用訓練資料，根據損失函數最小化的原則建立決策樹模型。
預測時，對新的資料，利用決策樹模型進行分類。
決策樹學習通常包括3個步驟：特征選擇、決策樹的生成和決策樹的修剪。
1 決策樹模型與學習
決策樹模型
**決策樹（decision tree）**分類決策樹是一種描述對執行個體進行分類的樹形結構。決策樹由結點（node）和有向邊（directed edge）組成。結點有兩種類型：内部結點（internal node）和葉結點（leaf node）。内部結電表示一個特征或屬性，葉結點表示一個類。
用決策樹分類的過程：從根結點開始，對執行個體的某一特征進行測試，根據測試結果，将執行個體配置設定到其子結點；這時，每一個子結點對應着該特征的一個取值。如此遞歸地對執行個體進行測試并配置設定，直至達到葉結點。最後将執行個體分到葉結點的類中。
決策樹與if-then規則
可将決策樹看成一個if-then規則的集合。
由決策樹的根結點到葉結點的每一條路徑建構一條規則；路徑上内部結點的特征對應着規則的條件，而葉結點的類對應着規則的結論。決策樹的路徑或其對應的if-then規則集合具有一個重要的性質：互斥并且完備。即，每一個執行個體都被一條路徑或一條規則所覆寫，而且隻被一條路徑或一條規則所覆寫。這裡的覆寫是指執行個體的特征與路徑上的特征一緻或執行個體滿足規則的條件。
決策樹與條件機率分布
決策樹可表示給定特征條件下類的條件機率分布。
将特征空間劃分為互不相交的cell（或region），并在每個cell定義一個類的機率分布，就構成了一個條件機率分布。決策樹的一條路徑對應于劃分中的一個cell。決策樹所表示的條件機率分布由各個cell給定條件下類的條件機率分布組成。
決策樹學習
決策樹學習本質上是從訓練資料集中歸納出一組分類規則。
決策樹學習的政策是以損失函數為目标函數的最小化。
決策樹學習的算法通常是一個遞歸地選擇最優特征，并根據該特征對訓練資料進行分割，使得對各個子資料集有一個最好的分類的過程。這一過程對應着對特征空間的劃分，也對應着決策樹的建構。
決策樹的建構過程：開始，建構根結點，将所有訓練資料都放在根結點。選擇一個最優特征，按照這一特征将訓練資料集分割成子集，使得各個子集有一個在目前條件下最好的分類。如果這些子集已經能夠被基本正确分類，那麼建構葉結點，并将這些子集劃分到對應的葉結點中去；如果還有子集不能被基本正确分類，那麼就對這些子集選擇新的最優特征，繼續對其進行分割，建構相應的結點。如此遞歸進行下去，直至所有訓練資料子集被基本正确分類，或者沒有合适的特診為止。最後每個子集都被分到葉結點上，即都有了明确的類，這就生成了一棵決策樹。
以上方法生成的決策樹可能對訓練資料有很好的分類能力，但對未知的測試資料未必能夠很好地分類，可能發生過拟合現象。此時需要對已生成的樹自上而下進行剪枝，将樹變得簡單，進而使其具有更好的泛化能力。具體地，就是去掉過于細分的葉結點，使其回退到父結點，甚至更高的結點，最後将父結點或更高的結點改為新的葉結點。
如果特征數量過多，也可以在決策樹開始學習的時候，對特征進行分類，隻留下對訓練資料有足夠分類能力的特征。
2 特征選擇
特征選擇在于選取對訓練資料具有分類能力的特征，以提高決策樹的學習效率。如果利用一個特征進行分類的結果與随機分類的結果沒有很大差别，則稱這個特診是沒有分類能力的，經驗上扔掉這樣的特征對決策樹學習的精度影響不大。通常特征選擇的準則是資訊增益或資訊增益比。
資訊增益
熵（entropy）時表示随機變量不确定性的度量。
熵越大，随機變量的不确定性越大。
資訊增益（information gain）表示得知特征X的資訊而使得類Y的資訊的不确定性減少的程度。
定義（資訊增益）特征A對訓練資料集D的資訊增益g(D,A)，定義為集合D的經驗熵H(D)與特征A在給定條件下D的經驗條件熵H(D|A)之差，即，g(D,A) = H(D) - H(D|A)。
這個熵與條件熵的差稱為互資訊。決策樹學習中的資訊增益等價于訓練資料集中類與特征的互資訊。
決策樹學習應用資訊增益準則選擇特征。資訊增益大的特征具有更強的分類能力。
根據資訊增益準則的特征選擇方法是：對訓練資料集（或子集）D，計算其每個特征的資訊增益，并比較他們的大小，選擇資訊增益最大的特征。
定義（資訊增益比）
3 決策樹的生成
ID3 算法
核心是在決策樹各個結點上應用資訊增益準則選擇特征，遞歸地建構決策樹。具體方法：從根結點（root node）開始，對結點計算所有可能的特征的資訊增益，選擇資訊增益最大的特診作為結點的特征，由該特征的不同取值建立子結點；再對子結點遞歸地調用以上方法，侯建決策樹；直到所有特征的資訊增益均很小或沒有特征可以選擇為止。最後得到一個決策樹。ID3相當于用極大似然法進行機率模型的選擇。
缺點：ID3算法隻有樹的生成，是以該算法生成的樹容易産生過拟合。
C4.5的生成算法
與ID3相似，對其進行了改進。C4,。5在生成的過程中，用資訊增益比來選擇特征。
4 決策樹的剪枝
為什麼剪枝：決策樹生成算法遞歸地産生決策樹，直到不能繼續下去為止。這樣産生的樹往往對訓練資料的分類很準确，但對未知的測試資料的分類卻沒有那麼準确，即出現過拟合現象。過拟合的原因在于學習時過多地考慮如何提高對訓練資料的正确分類，進而建構出過于複雜的決策樹。解決這個問題的辦法是考慮決策樹的複雜度，對已生成的決策樹進行簡化。
什麼是剪枝：在決策樹中将已生成的樹進行簡化的過程稱為剪枝（pruning）。具體地，剪枝從已生成的樹上裁掉一些子樹或葉結點，并将其根結點或父結點作為新的葉結點，進而簡化分類樹模型。
一般做法：通過極小化決策樹整體的損失函數或代價函數來實作。
剪枝，就是當α确定時，選擇損失函數最小的模型，即損失
函數最小的子樹。當α值确定時，子樹越大，往往與訓練資料的拟合越好，但是模型的複雜度就越高；相反，子樹越小，模型的複雜度就越低，但是往往與訓練資料的拟合不好。損失函數正好表示了對兩者的平衡。
決策樹生成隻考慮了通過提高資訊增益對訓練資料進行更好的拟合，而決策樹剪枝通過優化損失函數還考慮了減小模型複雜度。決策樹生成學習局部的模型，而決策樹剪枝學習整體的模型。
5 CART算法
分類與回歸樹（classification and regression tree， CART）
由以下兩步組成：
（1）決策樹生成：基于訓練資料集生成決策樹，生成的決策樹要盡量大；
（2）決策樹剪枝：用驗證資料集對已生成的樹進行剪枝并選擇最優子樹，這時用損失函數最小作為剪枝的标準。
CART生成
回歸樹的生成
分類樹的生成
分類樹用基尼指數選擇最優特征，同時決定該特征的最優二值切分點。
基尼指數Gini(D)表示集合D的不确定性，基尼指數Gini(D,A)表示經A=a分割後集合D的不确定性。基尼指數值越大，樣本集合的不确定性也就越大。
CART剪枝
從決策樹底端剪去一些子樹。
CART剪枝算法由兩步組成：首先從生成算法産生的決策樹T_0,開始不斷，剪枝，直到T_0的根結點，形成一個子樹序列{T_0,T_1,…,T_n}；
然後通過交叉驗證法在獨立的驗證資料集上對子樹序列進行測試，進而選擇最優子樹。
《統計學習方法》 李航