一、決策樹簡介
決策樹是一種既能做分類，又能做回歸的算法。
基本形狀為：
了解上圖中的重要概念（根節點，分支，内部節點，葉子節點）
二、資訊熵的概念（entropy）
假設有兩個籃子A和B：
A裝了 [雞蛋、蘋果、香蕉、橘子、芒果、牛奶]
B裝了 [雞蛋、雞蛋、雞蛋、雞蛋、雞蛋、牛奶]
從上面兩個籃子中随機取一個出來，A有6中結果，B有2種結果
A的不确定性大，B的不确定性小，A的熵 > B的熵 H(A) >H(B)
了解：若一個資料集合内，越混亂，那麼熵就越大
資訊熵的公式（規定0log(0)=0 ）
了解熵的公式
嘗試計算上面例子中的H(A)與H(B)
H(A) = {- 1 6 \frac{1}{6} 61 * log 2 ( 1 / 6 ) \log_2 (1/6) log2(1/6)}*6 = 2.58
H(B) = - 5 6 \frac{5}{6} 65 * log 2 ( 5 / 6 ) \log_2 (5/6) log2(5/6) - 1 6 \frac{1}{6} 61 * log 2 ( 1 / 6 ) \log_2 (1/6) log2(1/6) = 0.65
這裡對數中，為什麼要以2為底數？
遵循資訊論的普遍傳統，使用2作為對數的底
另外，基尼系數，與熵的概念類似，計算方法為：
Gini ( P ) (P) (P) = ∑ i = 1 k \sum_{i=1}^{k} ∑i=1k P k P_k Pk ( 1 − P k ) (1-P_k) (1−Pk)
三、構造決策樹（結合簡單案例）
案例來源：https://blog.csdn.net/wsp_1138886114/article/details/80955528
基本思想：希望節點的熵迅速降低
案例：特征分别為：性别、車型、襯衣尺碼，分類結果為 C0或C1
ID3算法——資訊增益（information gain）
-
先計算一下，不考慮3個特征的資訊熵：C0出現10次，C1出現10次
H = - P C 0 P_{C0} PC0* log 2 ( P C 0 ) \log_2 (P_{C0}) log2(PC0) - P C 1 P_{C1} PC1* log 2 ( P C 1 ) \log_2 (P_{C1}) log2(PC1)
H = 2*(-0.5* log 2 ( 0.5 ) \log_2 (0.5) log2(0.5))
H = 1
- 計算一下，如果根節點是性别，那麼資訊熵為：
機器學習筆記_決策樹一、決策樹簡介二、資訊熵的概念（entropy）三、構造決策樹（結合簡單案例）四、決策樹的過拟合問題以及剪枝政策
gain(性别）= 0.029
同理可得
gain(車型）= 0.62
gain(性别）= 0.029
是以，這裡根節點，應選擇車型
C4.5算法——資訊增益率
如果将上述顧客ID也作為一個特征值，那麼顧客ID的資訊增益 肯定是最大的
因為一個ID 對應一個結果
這時，就引入資訊增益率算法
資訊增益率 = 資訊增益/自身的熵值
CART算法——基尼系數
與資訊增益算法類似
四、決策樹的過拟合問題以及剪枝政策
決策樹的過拟合（Overfitting）：
決策樹訓練得過于複雜，高度高，節點多。訓練集資料表現很高，誤差非常小，但是測試資料的表現不好。
預剪枝
在建構決策樹的過程中，提前停止學習
- 可以指定決策樹的深度
- 可以指定決策樹的節點的最小樣本數（min_sample），如果節點的樣本數小于指定值，那麼也停止裁剪
後剪枝
決策樹建構好之後，開始裁剪
定義損失函數：
C α C_\alpha Cα(T) = C(T) + α \alpha α| T l e a f T_{leaf} Tleaf|
舉例：
假設一個非葉子節點，分裂成了3個葉子節點
試算
分裂之後的 C α C_\alpha Cα(T) = 3個葉子節點的基尼系數 + α \alpha α*3
與 分裂之前的 C α C_\alpha Cα(T) = 自身的基尼系數 α \alpha α*1 進行比較