前言

決策樹是一種常用的機器學習模型，用於分類和迴歸任務，它通過模擬“樹”的結構來對數據進行決策。本節我們詳細討論的是決策樹中的分類任務

開始探索

scikit-learn

假設以下運維場景

• CPU
  • 低：<40%
  • 中：40%~70%
  • 高：>70%
• 內存
  • 低：<60%
  • 中：60%~85%
  • 高：>85%
• 磁盤I/O
  • 低：<40%
  • 中：40%~70%
  • 高：>70%
• 日誌報錯數（條）
  • 少：<20
  • 中：20~50
  • 多：>50

將其轉換成代碼：

import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import classification_report


level_map = {'低': 0, '中': 1, '高': 2, '少': 0, '中': 1, '高': 2, '多':2, '穩定': 1, '不穩定': 0}
data = [
    ['低', '低', '低', '少', '穩定'],
    ['中', '中', '低', '少', '穩定'],
    ['低', '中', '高', '少', '穩定'],
    ['低', '低', '低', '多', '不穩定'],
    ['低', '低', '高', '多', '不穩定'],
    ['高', '高', '低', '少', '不穩定'],
    ['中', '高', '低', '中', '穩定'],
    ['高', '低', '低', '多', '不穩定'],
    ['中', '高', '高', '少', '不穩定'],
    ['中', '中', '中', '中', '不穩定'],
    ['高', '高', '低', '少', '穩定'],
]

data_mapped = [[level_map[v] for v in row] for row in data]

df = pd.DataFrame(data_mapped, columns=['CPU', '內存', '磁盤IO', '日誌報錯數', '系統是否穩定'])

X = df[['CPU', '內存', '磁盤IO', '日誌報錯數']]
y = df['系統是否穩定']

clf = DecisionTreeClassifier(criterion='entropy', random_state=0)
clf.fit(X, y)
y_pred = clf.predict(X)

print("分類報告：\n", classification_report(y, y_pred, target_names=['不穩定', '穩定']))

腳本！啓動

繪圖更能直接觀察決策樹

from sklearn import tree
import matplotlib.pyplot as plt

plt.figure(figsize=(14, 8))
tree.plot_tree(clf,
               feature_names=['CPU', 'memory', 'storage I/O', 'error count'],
               class_names=['not stable', 'stable'],
               filled=True)
plt.show()

分析繪圖

• 每個矩形框代表一個決策節點（葉子節點），比如第一個框，error count<1.5表示用該特徵來分類，1.5是基於輸入的數據計算出來的，模型認為1.5是特徵分割點
• entropy：當前節點的不確定性（越低越純）
• samples：這個節點上的樣本數
• value=[不穩定數, 穩定數]：類別分佈
• class：當前節點最終被分類的類別

深入理解決策樹

熵（entropy）

在圖中有一個重要的指標，entropy。它是衡量數據純度（不確定性）的指標，熵越低，表示類別越“純”（不確定性越低）；熵越高，代表數據越混雜

• D 是某個數據集（或某個節點上的樣本）
• k 是類別數量（如“穩定”“不穩定”就是2類）
• \(p_i\) 是第i類在該數據集中的比例

比如某節點：

樣本數samples=5，類別value=[1,4]

熵越小，那就代表了該節點不確定性越低，如果該節點的上為0，那就不會繼續分裂下去產生子節點；而不確定性越高的節點，就會繼續分裂產生葉子節點

信息增益

是決策樹中用於選擇劃分特徵的核心指標。它本質上衡量的是：“使用某個特徵進行劃分後，數據的不確定性減少了多少”

信息增益=原始熵−加權熵

比如以下節點，想要計算出信息增益

原始熵我們已經有了，那就是0.994，需要計算加權熵

通過特徵error count <= 1.5劃分所帶來的信息增益為0.183，也就是減少了 18.3% 的“混亂”程度

• 那該特徵就是信息增益最大的特徵了？
• 特徵選的0.5、1.5的值是怎麼來的？

特徵選取的0.5、1.5從何而來

特徵從“低”、“中”、“高”等文字描述轉換成，0 1 2等數字，比如CPU可能的取值是[0,1,2]，那就可以嘗試劃分出閾值中位點

(0+1)/2=0.5
(1+2)/2=1.5

所以在選取劃分點的時候就會參考中位點進行劃分

選取信息增益最大的特徵

先選擇error count以1.5為劃分點

• error count<=1.5有9條，穩定與不穩定的比例為[5, 4]
• error count>1.5有2條，並且都是不穩定的

計算一下信息增益：

• 首先計算原始熵：11個樣本中，5個穩定，6個不穩定，\(Entropy=-(\frac{6}{11}⋅log_2\frac{6}{11}+\frac{5}{11}⋅log_2\frac{5}{11}) \approx 0.994\)
  • 再計算error count>=1.5的熵：\(Entropy_1=-(\frac{4}{9}⋅log_2\frac{4}{9}+\frac{5}{9}⋅log_2\frac{5}{9}) \approx 0.991\)
  • 再計算error count>1.5的熵，由於全是不穩定，所以熵是0
• 計算加權熵：\(Entropy_{weighted}=\frac{9}{11}⋅0.991+\frac{2}{11}⋅0 \approx 0.811\)
• 信息增益：0.994-0.811=0.183

選擇error count以0.5為劃分點

• error count<=0.5有6條，穩定與不穩定的比例為[4, 2]

• error count>0.5有5條，穩定與不穩定的比例為[1, 4]

• 首先計算原始熵：上面已經計算過了，0.994

  • 再計算error count<=0.5的熵：\(Entropy_1=-(\frac{4}{6}⋅log_2\frac{4}{6}+\frac{2}{6}⋅log_2\frac{2}{6}) \approx 0.918\)
  • 再計算error count>0.5的熵：\(Entropy_2=-(\frac{1}{5}⋅log_2\frac{1}{5}+\frac{4}{5}⋅log_2\frac{4}{5}) \approx 0.722\)

• 計算加權熵：\(Entropy_{weighted}=\frac{6}{11}⋅0.918+\frac{5}{11}⋅0.722 \approx 0.829\)

• 信息增益：0.994-0.829=0.165

綜上所述，error count為特徵，以1.5為劃分點，是合適的選擇。並且將每個特徵的每個劃分點遍歷一遍，得出error count<=1.5是熵下降最快的劃分點

小結

算法步驟：

• 計算當前數據集的熵
• 對每個特徵求出信息增益
• 選擇信息增益最大的特徵進行節點分類
• 重複以上步驟，直至熵為0，或者特徵用完，或者數到達規定層數

有位彥祖説到，這不就是ID3算法嘛，基於信息熵作為劃分標準。其實説對了一部分，文中使用的代碼

clf = DecisionTreeClassifier(criterion='entropy', random_state=0)

criterion='entropy'使用的是的算法是整合了CART算法+ID3的信息熵分類等多種算法思想融合而來

基尼指數

之前討論了通過熵的方式來劃分節點，本節討論基尼指數來劃分節點

• n：數據集中類別的數量
• \(p_i\)：數據集中第 \(i\) 類的概率

clf = DecisionTreeClassifier(criterion='gini', random_state=0)

使用基尼指數，選擇了error count<=0.5作為劃分特徵，與熵不一樣

基尼增益

選擇error count<=0.5

• error count<=0.5有6條，穩定與不穩定的比例為[4, 2]
• error count>0.5有5條，穩定與不穩定的比例為[1, 4]

計算一下基尼增益：

• 原始基尼指數：\(Gini = 1 - \sum_{i=1}^{n} p_i^2 = 1-((\frac{5}{11})^2-(\frac{6}{11})^2 \approx 0.496)\)
  • 計算error count<=0.5的基尼指數，\(Gini_1=1-((\frac{4}{6})^2+(\frac{2}{6})^2) \approx 0.4445\)
  • 計算error count>0.5的基尼指數，\(Gini_2=1-((\frac{1}{5})^2+(\frac{4}{5})^2) = 0.32\)
• 計算加權平均基尼指數：\(Gini_{weighted}=\frac{6}{11}⋅0.4445 + \frac{5}{11}⋅0.32 \approx 0.3870\)
• 基尼增益：0.4959 - 0.3870=0.1089

選擇error count<=1.5

• error count<=1.5有9條，穩定與不穩定的比例為[5, 4]
• error count>1.5有2條，並且都是不穩定的

計算一下基尼增益：

• 原始基尼指數：上面已經計算過，0.0496
  • 計算error count<=1.5的基尼指數，\(Gini_1=1-((\frac{5}{9})^2+(\frac{4}{9})^2) \approx 0.4939\)
  • 計算error count>1.5的基尼指數，由於全是不穩定，\(Gini_2=1-((\frac{0}{2})^2+(\frac{2}{2})^2) = 0\)
• 計算加權平均基尼指數：\(Gini_{weighted}=\frac{9}{11}⋅0.4939 \approx 0.4041\)
• 基尼增益：0.4959 - 0.4041=0.0918

小結

綜上所述，error count為特徵，以0.5為劃分點，是合適的選擇

使用基尼指數，選擇特徵劃分點的時候，與熵的行為完全不一樣，下面列一下基尼指數與熵的對比

剪枝

所謂剪枝，是提高決策樹泛化能力的一種策略，剪枝的核心思想是減少數的複雜度，決策樹通過找到最大的信息增益，不斷迭代的劃分節點分類，不斷的迭代劃分，就會造成樹的複雜度不斷提高

預剪枝

預剪枝：在構建決策樹的過程中就進行限制，提前停止樹的生長

• 設置最大深度，max_depth
• 設置葉子節點最小樣本數，min_samples_leaf
• 設置內部節點最小樣本數，min_samples_split
• 設置信息增益閾值（如增益低於某一閾值就不分裂）

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_predict, StratifiedKFold
from sklearn.metrics import classification_report


X, y = load_iris(return_X_y=True)

cv = StratifiedKFold(n_splits=5, shuffle=True)

model = DecisionTreeClassifier(max_depth=3, min_samples_leaf=3, random_state=0)
y_pred = cross_val_predict(model, X, y, cv=cv)

print("預剪枝 分類報告：\n")
print(classification_report(y, y_pred, zero_division=0))

後剪枝

後剪枝：先讓樹儘可能長大（完全生長），然後再自底向上地修剪枝葉。sklearn中默認採用：成本複雜度剪枝（Cost Complexity Pruning，也叫 α-剪枝）：用代價函數考慮準確率與模型複雜度的權衡

from sklearn.model_selection import cross_val_score
import numpy as np

model = DecisionTreeClassifier(random_state=0)
path = model.cost_complexity_pruning_path(X, y)
ccp_alphas = path.ccp_alphas[:-1]

mean_scores = []

for alpha in ccp_alphas:
    clf = DecisionTreeClassifier(random_state=0, ccp_alpha=alpha)
    scores = cross_val_score(clf, X, y, cv=5, scoring='accuracy')
    mean_scores.append(scores.mean())

best_alpha = ccp_alphas[np.argmax(mean_scores)]
print("最佳 ccp_alpha:", best_alpha)

best_model = DecisionTreeClassifier(random_state=0, ccp_alpha=best_alpha)
best_model.fit(X, y)
y_pred = best_model.predict(X)
print("後剪枝 分類報告:")
print(classification_report(y, y_pred))

• 首先訓練處一顆完整樹
• 從底部開始，找到最小的子樹節點t，將其子樹 \(T_t\) 剪成一個葉子節點

• 計算剪枝後誤差的變化，得到\(\alpha_t\)
  • 其中損失函數可以使用多種方式計算，由於sklearn默認使用的是基尼指數，那就用基尼指數來計算誤差$$\alpha = \frac{R(t)-R(T_t)}{|T_t|-1}$$
    • \(R(t)\)：父節點的基尼指數
    • \(R(T_t)\)：剪枝前加權基尼指數
    • \(|T_t|\)：葉節點數
• 上一步拿到的\(\alpha\)，與ccp_alpha超參數（提前設置）進行對比，如果ccp_alpha>\(\alpha\)，則減掉該子樹
• 重複以上過程

舉一個例子，來看下該節點（CPU<=1.5）是否應該被剪枝

• 父節點的基尼指數：\(R(t)=0.444\)
• 加權平均基尼指數：
  • 父節點的加權基尼指數：\(\frac{3}{6}⋅0.444=0.222\)
  • 左子樹的加權基尼指數：\(\frac{1}{6}⋅0\)
  • 右子樹的加權基尼指數：\(\frac{2}{6}⋅0.5 \approx 0.166\)
  • 子樹的加權基尼指數：\(0.222+0+0.166=0.388\)
• \(\alpha = \frac{0.444-0.166}{3-1}=0.028\)

如果超參數ccp_alpha>0.028，那該節點就將剪枝

聯繫我

• 聯繫我，做深入的交流
  

至此，本文結束
在下才疏學淺，有撒湯漏水的，請各位不吝賜教...