決策樹（Decision tree）是一種常用的監督式學習演算法，適用於分類與回歸問題。決策樹是一個在機器學習中既簡單又直觀的模型。就像我們日常所做的種種決策，每一個選擇都將你帶向不同的道路。決策樹就像這樣，從問題的「根」開始，不斷通過「節點」提出問題或檢查特徵，直到我們達到一個清晰的「葉子」，也就是最終的決策結果。
如下圖，假設我們的分類目標是想要辨別出顧客會不會參加某個行銷活動（0為不參加，1為參加）。我們可以建構一顆決策樹來進行推論。下圖中的決策樹選擇了三種顧客的特徵來作為決策的標準，分別是顧客收入（Income）、最近一次購買為幾天前（Recency）、兩年內購買酒類的金額（MntWines），這些判斷標準都是模型演算後的最佳結果。
第一層 ：決策樹首先判斷變數 Income 是否小於 77627。
第二層 ：判斷 Recency 是否小於 24.5 或是 MntWines 是否小於 814（根據第一層的結果）
- 如果 Income 小於 77627 且 Recency 小於 24.5。則顧客不會參加此次行銷活動。
- 如果 Income 小於 77627 且 Recency 大於 24.5。則顧客不會參加此次行銷活動。
- 如果 Income 大於 77627 且 MntWines 小於 814。則顧客不會參加此次行銷活動。
- 如果 Income 大於 77627 且 MntWines 大於 814。則顧客會參加此次行銷活動。
根據上述的邏輯，我們就生成了簡易的決策樹，可以用在新資料的推斷上面。我們可以由上述的舉例中發現，決策樹有別於許多機器學習或是深度學習的模型，是相對非常容易解釋的模型，這也是其優點之一。接下來的章節，我會介紹決策樹訓練時的重要因素，特別是如何選擇最佳的特徵，以及使用哪些演算法來決定切割標準（例如信息增益或基尼不純度）。
ID3 — Information Gain (Entropy)
ID3 使用了 Information Gain 來決定每個節點上最適合的特徵來進行分裂，並遞迴的逐步生成決策樹。
Entropy(熵)：是用來度量一個隨機變量的不確定性，熵越高，表示系統越不確定，資訊混亂。在機器學習中，特別是在決策樹（Decision Tree）演算法中，Entropy 被用來衡量節點分裂後資料的純度。Entropy 越小則類別分佈越不平均，也就是使用該特徵來分割越能降低資料的混亂程度。Entropy 計算公式：
其中，Pi 是類別 i 的機率，S 是資料集。
Information Gain(資訊增益)：資訊增益衡量的是在根據某個特徵進行分裂後，系統不確定性減少的程度。換句話說，也就是在使用該特徵進行分割後，資料的混亂度降低了多少。Information Gain 越大就代表在使用該特徵來分割能夠使資料混亂程度降低最多。Information Gain 計算公式：
其中， S 是當前資料集， A 是我們考慮的劃分特徵， Sv 是根據特徵 A 的值 v 劃分後的子集。
ID3 演算法步驟
- 計算節點的 Entropy：對於當前資料集 S，計算其熵 H(S)。
- 選擇分裂特徵：對每一個特徵 A，計算在使用這個特徵分裂後的 Information Gain IG(S, A)。選擇資訊增益最大的特徵作為該節點的分裂依據。
- 分裂資料集：使用選定的特徵將資料集劃分成多個子集，並遞迴執行 ID3 算法，繼續選擇最佳的特徵並分裂資料集。
- 終止條件：當資料集中的所有樣本都屬於同一個類別，或是在達成某一個停止條件時，停止生成決策樹。更多的終止條件我會在後面介紹。
C4.5 (Gain Ratio)
上述介紹的 ID3 雖然容易解釋且運行效率高，但是由於 Entropy 的計算公式會在 v 的 outcome 越多時得到越低的值，因此 ID3 會傾向於挑選 v 較多的特徵。這會造成一個問題，舉例來說，我們有一個特徵”身分證字號”，我們都知道，身分證字號是不會重複的，因此 ID3 在進行演算時，”身分證字號” 這個特徵可以得到很低的 Entropy，進而使其容易被挑中。但我們從直覺就可以發現，像是”身分證字號”這類的特徵每個人都不一樣，根本沒有作為非類決策上的意義。
C4.5 演算法就很好的解決了這個問題，C4.5 引入了 增益率（Gain Ratio） 來平衡這一偏好。增益率在計算 Information Gain 的基礎上，對特徵的取值數量進行修正，從而避免過度偏向取值範圍大的特徵。
增益率（Gain Ratio）: 增益率引入了一個稱為 Split Information 的修正因子，用來調整資訊增益對於取值範圍大的特徵的偏好，簡單來說，當 v 提高時 Split Information 也會跟著提高，以緩解 v 過高時對於 Information Gain 所帶來的影響。Gain Ratio 計算公式：
C4.5 的目標是挑選 Gain Ratio 最大的特徵當作是分割的依據。此外，與 ID3 不同，C4.5 可以處理連續型特徵。它會通過測試不同的切割點來找到最佳的分裂點。
CART (Gini impurity)
CART（Classification and Regression Trees）決策樹是一個二元分類樹，這意味著每次分裂時，節點只會被劃分為兩個子節點。這和 ID3、C4.5 等決策樹不同，這兩者可以根據特徵中不同的值挑選多個值進行分裂。
Gini 不純度(Gini impurity)：Gini 不純度衡量資料集中樣本被錯誤分類的概率，數值越低代表純度越高。Gini 不純度的計算公式：
其中，Pi 是類別 i 的樣本比例，S 是資料集。當資料集中的所有樣本屬於同一類別時，Gini 不純度為 0，表示純度最高。
Gini 不純度的最佳分裂點：CART 根據分裂後的兩個子集的加權平均 Gini 不純度，來選擇最佳的分裂點。公式如下：
其中，SL 和 SR 是分裂後的兩個子集。
CART 回歸問題：CART 除了解決分類問題外，同樣也可以處理回歸問題。對於回歸問題，CART 使用均方誤差（MSE）來衡量。透過最小化 MSE，來選擇分裂的特徵。公式如下：
其中，yi 是真實值，hat{yi} 是預測值，N 是樣本數。
比較
What is overfitting?
過度擬合（Overfitting）是指機器學習模型在訓練資料上表現非常好，但無法有效應用於新的、模型未見過的資料上。也就代表模型過度學習了訓練資料中的“細節”和“噪音”，而不是抓住資料的普遍規律，導致泛化能力較差。
在生成 Decision tree 的過程中，模型為了擬合數據，會不斷的生成節點，導致樹變過於複雜，並很有可能會 overfitting。因此，在訓練 Decision Tree 的過程中，剪枝（Pruning）這項技術是十分重要的。
就如同字面上的意思，剪枝就是對樹的枝、葉進行修剪。在訓練決策樹的過程中，剪枝被分為兩種，分別是事前修剪（Prepruning）以及事後修剪（Postpruning）。
事前修剪（Prepruning）
Prepruning 是通過設置超參數來實現的，我們可以設置一個閾值（threshold）。在決策樹生成過程中，如果某次分裂所帶來的性能提升（例如根據某種評估標準，如資訊增益或 Gini 不純度的改善）未超過該閾值，則會停止進行進一步的分裂，以防止生成過於複雜的樹。
事後修剪（Postpruning）
Postpruning 是在決策樹構建後使用的。當我們生成了一顆複雜的決策樹後，我們可以使用超參數（例如 最大深度max_depth 或是 最小樣本分裂數min_samples_split）來進行修剪。我們先前所提到的 C4.5 以及 CART 演算法皆是利用 Postpruning 並配合 cost complexity pruning 的方式來進行剪枝。
Dataset : https://www.kaggle.com/datasets/ahsan81/superstore-marketing-campaign-dataset/data
Decision Tree
我這裡使用在本章一開始舉例的“超市行銷活動”的資料集作為範例，我們的目標是分類出有意願參與活動的顧客，因此，我們可以透過決策樹，來進行一個二元分類。以下是範例程式碼
# Training
model = DecisionTreeClassifier(
criterion='entropy',
random_state=42
)
model.fit(X_train, y_train)# Testing
y_pred = model.predict(X_test)
acc = accuracy_score(y_test, y_pred)
print(f'Accuracy: {acc}')
我使用 entropy 作為 criterion。我們可以透過以下的視覺化來觀察這顆決策樹的生成過程。如下圖，這顆決策樹過於複雜以至於無法解釋，而且有很高的機率已經 overfiting。
Decision Tree with pruning
我們可以使用一些剪枝的方法來避免以上的問題，以下為範例程式碼。
ccp_list = [0.0001, 0.001, 0.01, 0.02, 0.03]
best_acc = 0
best_ccp = 0for ccp in ccp_list:
model = DecisionTreeClassifier(
criterion='entropy',
random_state=42,
ccp_alpha=ccp
)
model.fit(X_train, y_train)
# Testing
y_pred = model.predict(X_test)
acc = accuracy_score(y_test, y_pred)
if acc > best_acc:
best_acc = acc
best_ccp = ccp
print(f'Accuracy (ccp_alpha={ccp}) : {acc}')
print(f'Best Accuracy: {best_acc}')
print(f'Best ccp: {best_ccp}')
我們使用了ccp_alpha 作為超參數來實現剪枝。ccp_alpha 為 Sklearn DecisionTreeClassifier 中的參數，代表 最小成本複雜度剪枝（Minimal Cost-Complexity Pruning） 的複雜度參數。此參數用於控制剪枝過程中的平衡點，以防止過度擬合。當 ccp_alpha 增加時，決策樹中那些帶來的複雜度增長（例如更多節點）超過 ccp_alpha 所帶來的性能提升的子樹會被剪掉。簡而言之，ccp_alpha數值越大，剪枝越多，樹越簡單；反之，數值越小，剪枝越少，樹越複雜。更多關於 DecisionTreeClassifier 的說明可以參考 Sklearn 的官方文件。
https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html
我們可以發現，在進行剪枝後，模型的測試正確率有所提高，因此在我們這個分類任務上，我們確實可以使用剪枝來避免 overfitting 的問題。而且如下圖，經過剪枝的決策樹變得十分容易解釋，我們可以清楚地理解決策樹建構的邏輯以及是以哪些特徵作為篩選標準。
以上就是關於決策樹的模型架構、演算法介紹以及簡單的實作範例。決策樹是一個高效率、易於解釋且易於擴展的模型，因此了解決策樹模型以及背後的演算法是十分鐘要的。我們未來還會介紹許多以樹的概念為基礎的機器學習模型。