從所有可能的決策樹中選擇選取最優(yōu)決策樹是 NP 完全問題
一顆生成好的決策樹，假設其葉子節(jié)點個數(shù)為T已球，該決策樹是由所有葉子節(jié)點對應的值組成的向量巍沙，以及一個把特征向量映射到葉子節(jié)點索引（Index）的函數(shù)
組成的。因此紊浩，策樹可以定義為
。
-
信息增益疗锐、信息增益比坊谁、基尼系數(shù)
熵：
條件熵：
信息熵是衡量樣本純度最常用的一種指標，熵值越小滑臊，樣本集的純度越高口芍。ID3算法用信息增益準則劃分樣本集，會對可取值數(shù)目較多的屬性有所偏好（可取集多简珠，劃分的分支結點多阶界，每個結點的純度更高），所以 C4.5改用信息增益率來選擇最優(yōu)劃分屬性聋庵。
基尼系數(shù)：
特征 A 下基尼系數(shù)：
基尼系數(shù)反映了從數(shù)據(jù)集中隨機抽取兩個樣本膘融，其類別標記不一致的概率。
簡單介紹一下決策樹模型（其實是一種貪心算法）
信息增益祭玉、ID3氧映、 C4.5、CART：回歸樹模型表示脱货、基尼系數(shù)岛都。ID3律姨、C4.5、CART 分類分別是每次取最大的信息增益臼疫、信息增益比以及最小的基尼系數(shù)進行貪心算法择份。
- 從深度為0的樹開始，對每個葉節(jié)點枚舉所有的可用特征
- 針對每個特征烫堤，把屬于該節(jié)點的訓練樣本根據(jù)該特征值升序排列荣赶，通過線性掃描的方式來決定該特征的最佳分裂點，并記錄該特征的最大收益（采用最佳分裂點時的收益）
- 選擇收益最大的特征作為分裂特征鸽斟，用該特征的最佳分裂點作為分裂位置拔创，把該節(jié)點生長出左右兩個新的葉節(jié)點，并為每個新節(jié)點關聯(lián)對應的樣本集
- 回到第1步富蓄，遞歸執(zhí)行到滿足特定條件為止
- 連續(xù)值處理
對于連續(xù)屬性 a剩燥，假定 a 在 D 上出現(xiàn)了 n 個不同的取值，將這些值從小到大排序立倍，基于劃分點可以t 可以將D 分為兩個子集灭红，一個是在屬性 a 上取值不大于 t，一個是在屬性 a 上取值大于 t帐萎，劃分點的選取是 n 個取值相鄰點的中點比伏，即 ，有了這些劃分點疆导，就可以像離散值一樣處理找到最優(yōu)的劃分點
- 決策樹間的差別
ID3只能處理離散型變量，C4.5和 CART 都可以處理連續(xù)型變量葛躏。
ID3和 C4.5只能用于分類任務澈段，而 CART 不僅用于分類，還可以應用于回歸
ID3和 C4.5可以再每個結點上產(chǎn)生多叉分支舰攒，且每個特征在層級之間不會復用败富，CART 每個結點只會產(chǎn)生兩個分支，因此最后會形成一個二叉樹
ID3和 C4.5通過剪枝來權衡樹的準確性和泛化能力摩窃，CART 直接利用全部數(shù)據(jù)發(fā)現(xiàn)所有可能得樹結構進行對比
- 回歸樹
一個回歸樹對應著輸入空間（即特征空間）的一個劃分以及在劃分的單元上的輸出值兽叮。假設已將輸入空間劃分為M個單元R1,R2,…,RM，并且在每個單元Rm上有一個固定的輸出值cm猾愿，于是回歸樹模型可表示為：
用平方誤差最小值準則求解每個單元上的最優(yōu)輸出值鹦聪，易知：
尋找最優(yōu)切分變量和最優(yōu)切分點：
預剪枝
在決策樹生成過程中，對每個結點在劃分前進行估計蒂秘，如果當前的結點的劃分不能帶來決策樹泛化性能的提升泽本，則停止劃分并將當前節(jié)點標記為葉結點。
后剪枝
先從訓練集生成一個完整的決策樹姻僧，然后自底向上地對非葉結點進行考查规丽，如果將該節(jié)點對應的子樹替換為葉節(jié)點能帶來決策樹泛化性能的提升蒲牧，則將該子樹替換為葉節(jié)點
- 講一下決策樹的剪枝
ID3和 C4.5的剪枝通過構造損失函數(shù)（經(jīng)驗熵），遞歸地從樹的葉結點向上回縮赌莺，直到找到損失函數(shù)最小的子樹
cart 的損失函數(shù)（如基尼系數(shù)）冰抢，α小時，最優(yōu)子樹大艘狭，α大時挎扰，最優(yōu)子樹小，α從小增大缓升，可以得到一系列最優(yōu)子樹鼓鲁，序列中的子樹是嵌套的。
具體得到子樹序列的過程：對整體樹地任意內部結點 t港谊，一個是以 t 為單結點樹的損失函數(shù)骇吭，一個是以 t 為根節(jié)點的子樹地損失函數(shù)，當時兩個損失函數(shù)相等歧寺，因此其表示剪枝后整體損失函數(shù)減少的程度燥狰。在
中剪去 g(t)最小的
，將最小的 g(t)設為
斜筐，然后不斷增加 α的值龙致，得到子樹序列
然后在子樹序列中通過交叉驗證選取最優(yōu)子樹
- 決策樹的損失函數(shù)
，其中經(jīng)驗熵為
顷链，通常將右邊第一項記作
目代，C(T)表示模型對訓練數(shù)據(jù)的預測誤差（？嗤练？）榛了，即模型與訓練數(shù)據(jù)的擬合程度
- 決策樹的優(yōu)缺點
優(yōu)點：非線性模型、不需要歸一化煞抬、不需要處理缺失值霜大、白盒模型，易理解
缺點：容易過擬合革答、方差大战坤、樣本不一致模型信息增益偏向于數(shù)值特征多的特征、忽略了屬性的相關性
