Learning Objectives
- 算出一群資料的 Gini 不純度，說明它代表什麼
- 用 numpy 寫出找最佳分割的程式，並說明一棵樹怎麼遞迴長出來
- 讀懂 scikit-learn 印出的決策樹，並說明決策樹為什麼不受特徵尺度影響
- 從不同深度的訓練與測試準確率，判斷欠擬合與過擬合
問一連串是非題
上一課的 k 近鄰靠距離判斷，這一課換一條路。想像你要猜一位同學會不會及格，可能會這樣問：
小考平均 ≤ 59 嗎？
├─ 是 → 缺席次數 ≤ 2 嗎？ …
└─ 否 → 大概會及格
這就是決策樹（decision tree）：每個節點問一個「某個特徵是否小於等於某個門檻」的問題，資料依答案往左或往右走，走到最底下的葉節點就得到預測。
它的優點是人讀得懂：你可以把整棵樹印出來，一路說明為什麼得到這個預測。
要長出一棵樹，只要回答一個問題：這一群資料，問哪一題最好？ 好的問題會把資料分成兩群，每一群裡的類別盡量單純。「單純的程度」要先有個數字才能比較，最常用的是 Gini 不純度：
Gini = 1 − (每個類別比例的平方加總)
全部是同一類時 Gini 是 0；兩類各半時是 0.5，這是兩個類別時的最大值。一次分割的好壞，就看分割後兩邊的 Gini（依筆數加權平均）比分割前減少了多少。
逐步看：算 Gini，找出最好的門檻
六位同學的讀書時數與是否及格。程式把每個候選門檻都試一次：左邊放小於等於門檻的，右邊放其他的，算 Gini 減少多少。候選門檻是相鄰兩個不同值的中點。
從一次分割長成一棵樹
找到最好的分割之後，資料分成左右兩群。接著對每一群重複同樣的事，直到：
- 這一群只剩一種類別（Gini 是 0），或
- 到達我們限制的深度（
max_depth）。
這是遞迴（recursion）。每一步都只挑眼前最好的分割，不會回頭修改，所以長出來的不保證是全部可能的樹裡最好的一棵，但速度快，結果通常也夠好。
葉節點的預測就是這一群裡最多的類別。接下來的程式把這些步驟串起來，每一步都看得到。
逐步看：用 numpy 長一棵樹
四筆資料、兩個特徵，深度限制 2。注意右上角的呼叫堆疊：grow 會呼叫自己，每一層看到的 X、y 越來越少。
改用 scikit-learn
實際工作不會自己寫，scikit-learn 的 DecisionTreeClassifier 做的是同一件事：預設 criterion="gini"，max_depth=None（一直長到葉節點單純，或筆數少於 min_samples_split=2 為止）。
export_text 可以把樹印成文字。決策樹只比大小，不算距離，所以特徵乘以 1000 只會讓門檻跟著乘以 1000，切法不變，也就不需要標準化。這是它和第 8 課 k 近鄰很大的不同。
逐步看：scikit-learn 的決策樹
用 students.csv（程式產生的模擬資料，不是任何學校的真實資料）預測是否及格，限制深度 2，把樹印出來讀一讀。
切了之後預測沒變，為什麼還要切？
上面那棵樹右半邊的兩個葉節點都預測 class: 1，看起來像白切了一刀。
Gini 看的是比例，不是最後的預測。把一群資料切成一群比較混雜、一群幾乎單純，兩邊都還是多數及格，預測不變，但 Gini 確實下降，而且再往下切時可能就會分出不及格的那一群。所以 Gini 減少量和「準確率有沒有提高」不是同一件事。
逐步看：深度怎麼影響準確率
同一份資料，深度從 1 試到 12。看輸出的四欄：深度、葉節點數、訓練準確率、測試準確率；最後畫成折線圖。
控制樹的複雜度
沒有限制的決策樹可以把訓練資料背到 100%（只要沒有特徵完全相同、標籤卻不同的資料），它會為了一兩筆資料多開一個分支，這就是過擬合。常用的限制：
| 參數 | 意思 | 預設 |
|---|---|---|
max_depth |
樹最多幾層 | None（不限制） |
min_samples_split |
一個節點至少幾筆才可以再切 | 2 |
min_samples_leaf |
每個葉節點至少幾筆 | 1 |
上面深度 6 的測試準確率是 0.798，比較高，但測試資料只有 94 筆，差一兩筆就差 1～2%，而且用測試資料挑深度本身就會讓這個數字偏樂觀。正確的挑法是交叉驗證（第 14 課）。
決策樹還有一個弱點：不穩定。 訓練資料稍微變動，第一刀可能就切在別的地方，整棵樹跟著不同。下一課的隨機森林正是利用這一點。
實作：算一次分割的 Gini 減少量
完成 gini(y) 與 split_gain(x, y, t)：split_gain 回傳用門檻 t 切特徵 x 之後，Gini 減少多少。
小測驗：決策樹
下面程式會印出什麼？
import numpy as np
y = np.array([0, 0, 0, 1])
p = np.bincount(y) / len(y)
print(round(1 - (p ** 2).sum(), 3))
六筆資料的類別是 [0, 0, 0, 1, 1, 1]，某個門檻剛好把前三筆與後三筆分開。Gini 減少多少？
把一個特徵的單位從公尺改成公分（數字乘以 100），決策樹會怎樣？
DecisionTreeClassifier() 不設任何參數，訓練準確率通常接近 1.0。這代表什麼？
一次分割之後，左右兩個葉節點都預測「及格」。這次分割的效果是？
重點整理
- 決策樹用一連串「特徵 ≤ 門檻」的問題分類，葉節點預測該群最多的類別，可以印出來讀。
- Gini ＝ 1 − 比例平方的加總；每一步挑「Gini 減少最多」的分割，然後對左右兩群遞迴。
- 決策樹只比大小，不受特徵尺度影響，不需要標準化；邊界由水平線與垂直線組成。
- 越深越容易過擬合：訓練準確率可以到 1.0，測試不一定跟著上升；用
max_depth、min_samples_leaf控制，並用交叉驗證挑（第 14 課）。 - 一棵樹很不穩定。下一課把很多棵樹組合起來：隨機森林與梯度提升。