一、決策樹介紹

決策樹是一種樹形結構的監督學習算法，其核心思想是通過一系列條件判斷對數據進行分類，就像人類在做決策時的邏輯判斷過程。

1.1 決策樹的結構特征

• 內部節點：表示一個特征上的判斷（如"年齡是否大于30"）
• 分支：表示判斷結果的輸出（如"是"或"否"）
• 葉子節點：表示最終的分類結果（如"同意貸款"或"拒絕貸款"）

1.2 決策樹的構建三步驟

1. 特征選擇：從眾多特征中挑選分類能力最強的特征
2. 樹的生成：基于選擇的特征遞歸構建決策樹
3. 剪枝優化：防止過擬合，提升模型泛化能力

1.3 決策樹構建例子

你有一個朋友正在考慮是否要去參加一個社交活動，他/她/他們可能會這樣思考：
朋友問你：這個活動值得去嗎？
于是你開始了解情況：
問：這個活動是線上還是線下？
答：線下，在市中心的一個咖啡館。
問：天氣怎么樣？
答：那天天氣不錯。
問：有沒有感興趣的人會去？
答：有，你喜歡的那位也會去。
問：交通方便嗎？
答：地鐵直達，很方便。
……
于是你的大腦里就構建了這樣一棵“決策樹”：

繪圖代碼：

import graphviz# 創建有向圖，并設置中文字體
# 1. 導入Graphviz庫：
#    graphviz是Python與Graphviz軟件交互的接口，負責生成可視化圖形（需提前安裝Graphviz軟件）
import graphviz  # 2. 創建有向圖對象，并配置中文顯示：
#    - comment：給圖加注釋（僅文檔用途，不影響渲染）
#    - format：指定輸出文件格式（如png、pdf等）
#    - node_attr/edge_attr/graph_attr：設置節點、邊、全局的字體為"SimHei"（微軟雅黑），解決中文亂碼問題
dot = graphviz.Digraph(comment='社交活動決策樹',       # 圖的描述信息（可選）format='png',                  # 輸出文件格式node_attr={'fontname': 'SimHei'},  # 節點文字用微軟雅黑（支持中文）edge_attr={'fontname': 'SimHei'},  # 邊的標簽文字用微軟雅黑graph_attr={'fontname': 'SimHei'}  # 全局文字（如標題）用微軟雅黑
)# 3. 添加節點（node）：
#    格式：dot.node(節點唯一標識, 顯示的文字)
#    節點ID（如'A'）是內部標記，顯示文字是圖形中實際展示的內容
dot.node('A', '活動類型')         # 根節點：決策起點（活動類型）
dot.node('B', '線上')             # 分支1：活動類型為線上
dot.node('C', '線下')             # 分支2：活動類型為線下
dot.node('D', '天氣是否好？')     # 線下活動的子判斷：天氣條件
dot.node('E', '否')               # 天氣分支：不好
dot.node('F', '是')               # 天氣分支：好
dot.node('G', '有沒有感興趣的人？') # 天氣好時的子判斷：興趣條件
dot.node('H', '否')               # 興趣分支：沒有
dot.node('I', '有')               # 興趣分支：有
dot.node('J', '去參加')           # 最終決策：參加
dot.node('K', '考慮其他安排')     # 最終決策：不參加# 4. 添加邊（edge）：
#    格式：dot.edge(起點ID, 終點ID, label=邊的說明文字)
#    label可選，用于解釋分支條件
dot.edge('A', 'B')                # 活動類型 → 線上（無額外條件，直接分支）
dot.edge('A', 'C')                # 活動類型 → 線下（無額外條件，直接分支）
dot.edge('C', 'D')                # 線下活動 → 判斷天氣
dot.edge('D', 'E', label='否')    # 天氣判斷 → 否（邊標注“否”）
dot.edge('D', 'F', label='是')    # 天氣判斷 → 是（邊標注“是”）
dot.edge('F', 'G')                # 天氣好 → 判斷是否有感興趣的人
dot.edge('G', 'H', label='否')    # 興趣判斷 → 否（邊標注“否”）
dot.edge('G', 'I', label='是')    # 興趣判斷 → 是（邊標注“是”）
dot.edge('I', 'J')                # 有感興趣的人 → 去參加（最終決策）
dot.edge('H', 'K')                # 沒有感興趣的人 → 考慮其他安排（最終決策）# 5. 渲染并查看圖形：
#    - 第一個參數：輸出文件名（生成的文件會是 decision_tree_social_event.png）
#    - view=True：生成后自動用系統默認程序打開圖片
#    注意：運行前需確保：
#      ① 系統安裝了Graphviz軟件（https://graphviz.org/download/）
#      ② Graphviz的bin目錄已加入系統環境變量（如 C:\Program Files\Graphviz\bin）
dot.render('decision_tree_social_event', view=True)

二、ID3決策樹：基于信息增益的決策模型

2.1 信息增益的公式與符號解析

信息增益公式：
$$g(D,A)=H(D)?H(D|A)$$

• $g(D,A)$：特征$A$對數據集$D$的信息增益
• $H(D)$：數據集$D$的經驗熵，衡量數據的不確定性
  $$H(D)=?\sum _{k=1}^K\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|D|}$$
  其中，$K$為類別數，$|C_k|$為第$k$類的樣本數，$|D|$為總樣本數。
• $H(D|A)$：特征$A$給定條件下$D$的經驗條件熵
  $$H(D|A)=\sum _{i=1}^n\frac{|D_i|}{|D|}H(D_i)=?\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{|D_i|}{\log }_2\frac{|D_{ik}|}{|D_i|}$$
  其中，$n$為特征$A$的取值個數，$|D_i|$為特征$A$取第$i$個值的樣本數，$|D_{ik}|$為$D_i$中屬于第$k$類的樣本數。

2.2 信息增益的意義

信息增益衡量的是某個特征對數據分類不確定性的減少程度。直觀來說，它反映了在已知某個特征的取值后，我們對樣本分類結果的不確定性降低了多少。
例如，在判斷一個人是否適合貸款時，如果“是否有房”這一特征能顯著幫助我們確定貸款審批結果，那么這個特征的信息增益就較大。換句話說，信息增益越大，該特征在分類任務中的判別能力越強。

2.3 ID3決策樹案例演示：貸款申請分類

以貸款申請數據為例，計算各特征的信息增益并構建ID3決策樹。

數據集：

年齡	有工作	有房子	信貸情況	類別
青年	否	否	一般	拒絕
青年	否	否	好	拒絕
青年	是	否	好	同意
青年	是	是	一般	同意
青年	否	否	一般	拒絕
中年	否	否	一般	拒絕
中年	否	否	好	拒絕
中年	是	是	好	同意
中年	否	是	非常好	同意
中年	否	是	非常好	同意
老年	否	是	非常好	同意
老年	否	是	好	同意
老年	是	否	好	同意
老年	是	否	非常好	同意
老年	否	否	一般	拒絕

步驟1：計算數據集D的經驗熵H(D)
數據集中共有15條樣本，其中"同意"類5條，"拒絕"類10條：
$$H(D)=?\frac{5}{15}{\log }_2\frac{5}{15}?\frac{10}{15}{\log }_2\frac{10}{15}=0.9183$$

步驟2：計算各特征的條件熵和信息增益
以"年齡"特征為例，其取值為{青年, 中年, 老年}：

• 青年樣本：5條（ID1-5），其中拒絕4條，同意1條
  $$H(青年)=?\frac{4}{5}{\log }_2\frac{4}{5}?\frac{1}{5}{\log }_2\frac{1}{5}=0.7219$$
• 中年樣本：5條（ID6-10），其中拒絕2條，同意3條
  $$H(中年)=?\frac{2}{5}{\log }_2\frac{2}{5}?\frac{3}{5}{\log }_2\frac{3}{5}=0.9709$$
• 老年樣本：5條（ID11-15），其中拒絕1條，同意4條
  $$H(老年)=?\frac{1}{5}{\log }_2\frac{1}{5}?\frac{4}{5}{\log }_2\frac{4}{5}=0.7219$$
• 條件熵：
  $$H(D|年齡)=\frac{5}{15}\times 0.7219+\frac{5}{15}\times 0.9709+\frac{5}{15}\times 0.7219=0.8049$$
• 信息增益：
  $$g(D,年齡)=0.9183?0.8049=0.1134$$

同理計算其他特征的信息增益：

• $g(D,有工作)=0.3236$
• $g(D,有房子)=0.4208$
• $g(D,信貸情況)=0.3623$

步驟3：選擇信息增益最大的特征分裂
"有房子"的信息增益最大（0.4208），作為根節點分裂，得到左右子樹：

• 有房子：7條樣本（ID4,8,9,10,11,12,14），其中6條同意，1條拒絕
• 無房子：8條樣本（ID1,2,3,5,6,7,13,15），其中2條同意，6條拒絕

步驟4：遞歸構建子樹
對每個子樹重復上述過程，最終生成完整的ID3決策樹。

這是一棵用于 貸款申請分類 的決策樹（基于ID3算法，通過信息熵選擇分裂特征），核心判斷邏輯如下：

根節點：判斷“是否有房子”

• 條件：按特征取值分裂（右分支為 有房子 > 0.5，左分支為 有房子 ≤ 0.5）。
• 信息增益：0.42（衡量該特征對分類的貢獻度）。
• 樣本數：15（全量樣本）。
• 類別分布：拒絕6人，同意9人（分布：拒絕=6，同意=9）。

分支邏輯

• 右分支（有房子 > 0.5）

  • 樣本：6人（所有“有房”申請人）。
  • 類別分布：同意6人，拒絕0人。
  • 決策：直接判定為 同意（葉子節點）。

• 左分支（有房子 ≤ 0.5）

  • 進入下一層判斷 “是否有工作”：

第二層節點：判斷“是否有工作”

• 條件：按特征取值分裂（右分支為 有工作 > 0.5，左分支為 有工作 ≤ 0.5）。
• 信息增益：0.918（該特征對剩余樣本的分類貢獻度）。
• 樣本數：9人（所有“無房”申請人）。
• 類別分布：拒絕6人，同意3人（分布：拒絕=6，同意=3）。

最終葉子節點

• 左子節點（有工作 ≤ 0.5）

  • 樣本：6人（無房且無工作的申請人）。
  • 類別分布：同意0人，拒絕6人。
  • 決策：拒絕（葉子節點）。

• 右子節點（有工作 > 0.5）

  • 樣本：3人（無房但有工作的申請人）。
  • 類別分布：同意3人，拒絕0人。
  • 決策：同意（葉子節點）。

決策樹通過 “有房→有工作” 的兩步判斷，輸出貸款決策：

• 有房 → 直接同意；
• 無房但有工作 → 同意；
• 無房且無工作 → 拒絕。

（注：LabelEncoder 按字母序編碼類別，此處“同意”為0，“拒絕”為1，節點分布以 拒絕=X，同意=Y 格式展示。）

繪圖代碼：

# 導入必要的庫
import pandas as pd  # 用于數據處理和構建 DataFrame
from collections import Counter  # 用于統計樣本數量
from math import log2  # 用于計算對數
from graphviz import Digraph  # 用于可視化決策樹
from sklearn.preprocessing import LabelEncoder  # 用于將字符串特征編碼為數字# =============================================
# 1. 數據準備
# =============================================
# 構建訓練數據集，包含 5 個特征和 1 個目標變量
data = {# 每個樣本的唯一編號，容易造成過擬合# "ID": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],# 年齡：青年、中年、老年"年齡": ["青年", "青年", "青年", "青年", "青年", "中年", "中年", "中年", "中年", "中年","老年", "老年", "老年", "老年", "老年"],# 是否有工作：是、否"有工作": ["否", "否", "是", "是", "否", "否", "否", "是", "否", "否","否", "否", "是", "是", "否"],# 是否有房子：是、否"有房子": ["否", "否", "否", "是", "否", "否", "否", "是", "是", "是","是", "是", "否", "否", "否"],# 信貸情況：一般、好、非常好"信貸情況": ["一般", "好", "好", "一般", "一般", "一般", "好", "好", "非常好", "非常好","非常好", "好", "好", "非常好", "一般"],# 類別：是否貸款成功（同意/拒絕）"類別": ["拒絕", "拒絕", "同意", "同意", "拒絕", "拒絕", "拒絕", "同意", "同意", "同意","同意", "同意", "同意", "同意", "拒絕"]
}# 將數據轉換為 pandas 的 DataFrame 格式
df = pd.DataFrame(data)# 提取特征列名列表（所有列除了最后一列）
features = list(df.columns[:-1])  # 特征：ID、年齡、有工作、有房子、信貸情況# 目標變量列名（最后一列）
target = df.columns[-1]  # 類別列名# =============================================
# 2. 信息熵與信息增益計算
# =============================================def entropy(y):"""計算信息熵 H(Y)y: 當前樣本的目標變量值（如：['拒絕', '同意', ...]）返回：當前樣本的信息熵"""counts = Counter(y)  # 統計每個類別的數量total = len(y)  # 總樣本數if total == 0:return 0  # 防止除以 0# 計算 -Σ(p * log2(p))return -sum((count / total) * log2(count / total) for count in counts.values())def conditional_entropy(X_col, y):"""計算條件熵 H(Y|X)X_col: 某個特征列的值（如：['青年', '中年', ...]）y: 對應的目標變量值返回：給定該特征下目標變量的條件熵"""values = set(X_col)  # 獲取該特征的所有唯一值total = len(y)  # 總樣本數ent = 0for v in values:mask = (X_col == v)  # 找到該特征值對應的樣本y_sub = y[mask]  # 取出這些樣本的目標變量ent += len(y_sub) / total * entropy(y_sub)  # 加權求和return entdef info_gain(dataset, feature):"""計算某個特征的信息增益 IG(Y, X)dataset: 整個數據集feature: 當前特征名稱（如："年齡"）返回：該特征的信息增益"""X_col = dataset[feature]  # 取出該特征列y = dataset[target]  # 取出目標變量列return entropy(y) - conditional_entropy(X_col, y)  # 信息增益 = 總熵 - 條件熵# =============================================
# 3. 手動實現 ID3 決策樹
# =============================================def id3_tree(dataset, features):"""使用 ID3 算法遞歸構建決策樹dataset: 當前數據集features: 當前可用特征列表返回：當前節點的決策樹結構字典"""target_values = dataset[target].unique()  # 獲取當前目標變量的唯一值# 終止條件1：當前樣本全部屬于同一類if len(target_values) == 1:return {'label': target_values[0]}  # 返回葉子節點標簽# 終止條件2：沒有可用特征if not features:most_common = dataset[target].mode().iloc[0]  # 返回多數類作為預測結果return {'label': most_common}# 選擇信息增益最大的特征gains = {f: info_gain(dataset, f) for f in features}  # 計算每個特征的信息增益best_feature = max(gains, key=gains.get)  # 選出最大增益的特征# 構建當前節點信息class_counts = dict(Counter(dataset[target]))  # 統計目標變量分布node_info = {'feature': best_feature,'gain': gains[best_feature],  # 信息增益'class_dist': class_counts,  # 類別分布'n_samples': len(dataset),  # 樣本數量'children': {}  # 子節點}# 遞歸劃分每個特征值remaining_features = [f for f in features if f != best_feature]  # 剩余可用特征for raw_value in dataset[best_feature].unique():  # 遍歷當前特征的每個唯一值sub_data = dataset[dataset[best_feature] == raw_value]  # 劃分子數據集node_info['children'][raw_value] = id3_tree(sub_data, remaining_features)  # 遞歸生成子樹return node_info# =============================================
# 4. 構建特征編碼器（用于生成 CART 風格的分割條件）
# =============================================
# 保存每個特征的編碼器，便于后續可視化時使用
feature_encoders = {}for feat in features:le = LabelEncoder()  # 創建編碼器le.fit(df[feat])  # 擬合該特征的編碼規則feature_encoders[feat] = le  # 保存編碼器# =============================================
# 5. 決策樹可視化（CART 風格，支持中文）
# =============================================
def visualize_tree_cart_style(tree, feature_encoders, graph=None, parent_id=None, edge_label=""):"""使用 Graphviz 可視化決策樹（CART 風格）tree: 當前樹節點結構feature_encoders: 編碼器字典graph: 當前圖對象parent_id: 父節點 IDedge_label: 邊上的標簽返回：Graphviz 圖對象"""from uuid import uuid4  # 用于生成唯一節點 IDif graph is None:# 初始化一個空圖，設置字體支持中文graph = Digraph('DecisionTree',format='png',node_attr={'fontname': 'SimHei'},  # 支持中文節點edge_attr={'fontname': 'SimHei'},  # 支持中文邊標簽graph_attr={'fontname': 'SimHei', 'rankdir': 'TB'}  # 樹方向從上往下)node_id = str(uuid4())  # 生成當前節點的唯一標識符if 'label' in tree:# 如果是葉子節點，顯示類別標簽label = f"類別: {tree['label']}"shape = "box"  # 葉子節點用矩形else:# 如果是內部節點，顯示特征、增益等信息feat_name = tree['feature']metric = round(tree.get('gain', 0), 3)  # 獲取信息增益n = tree['n_samples']  # 樣本數dist = ", ".join([f"{k}={v}" for k, v in tree['class_dist'].items()])  # 分布# 構造節點標簽label = (f"{feat_name}\\n"f"信息增益={metric}\\n"f"樣本數={n}\\n"f"分布：{dist}")shape = "ellipse"  # 內部節點用橢圓graph.node(node_id, label=label, shape=shape)  # 添加當前節點到圖中if parent_id:# 如果有父節點，則畫邊graph.edge(parent_id, node_id, label=edge_label)if 'children' in tree:# 如果有子節點，遞歸繪制feat_name = tree['feature']encoder = feature_encoders[feat_name]  # 獲取該特征的編碼器unique_values = df[feat_name].unique()  # 獲取原始特征值sorted_values = sorted(encoder.transform(unique_values))  # 編碼后的排序值for raw_value, child in tree['children'].items():encoded_value = encoder.transform([raw_value])[0]  # 把原始值轉為編碼值display_label = get_edge_label(feat_name, encoded_value, sorted_values)  # 生成邊標簽# 遞歸繪制子樹visualize_tree_cart_style(child, feature_encoders, graph, node_id, display_label)return graphdef get_edge_label(feat_name, encoded_value, sorted_values):"""生成邊標簽，例如：年齡 <= 0.5、年齡 > 0.5feat_name: 特征名encoded_value: 編碼后的特征值sorted_values: 排序后的編碼值列表返回：邊標簽字符串"""index = sorted_values.index(encoded_value)if index == 0:threshold = (sorted_values[index] + sorted_values[index + 1]) / 2return f"{feat_name} <= {threshold:.1f}"elif index == len(sorted_values) - 1:threshold = (sorted_values[index - 1] + sorted_values[index]) / 2return f"{feat_name} > {threshold:.1f}"else:low = (sorted_values[index - 1] + sorted_values[index]) / 2high = (sorted_values[index] + sorted_values[index + 1]) / 2return f"{low:.1f} < {feat_name} <= {high:.1f}"# =============================================
# 6. 主程序：構建并可視化 ID3 決策樹
# =============================================# 構建模型
tree_id3 = id3_tree(df, features)  # 構建 ID3 決策樹# 設置可視化圖例格式
dot_id3 = visualize_tree_cart_style(tree_id3, feature_encoders)  # 可視化 ID3 樹# 保存為 PNG 文件，并自動打開查看
dot_id3.render("id3_decision_tree_with_id", view=True)

2.4 ID3決策樹缺陷

ID3決策樹的核心優勢是計算簡單、可解釋性強，但存在明顯缺陷：傾向于選擇取值較多的特征（如"ID"特征可能有最大信息增益），導致過擬合風險。

ID3決策樹的缺陷演示：被“ID”特征誤導的過擬合

1. 構造含干擾特征的數據集
   在原有貸款數據中加入 “ID” 特征（唯一標識，與貸款結果無實際關聯），數據如下：

ID	年齡	有工作	有房子	信貸情況	類別
1	青年	否	否	一般	拒絕
2	青年	否	否	好	拒絕
3	青年	是	否	好	同意
…	…	…	…	…	…

（共15條，ID=1~15，類別不變）

2. 信息增益計算（核心對比）

   ① 總熵 ( H(D) )
   總樣本15條，同意=9，拒絕=6：
   $$H(D)=?\frac{9}{15}{\log }_2\frac{9}{15}?\frac{6}{15}{\log }_2\frac{6}{15}\approx 0.918$$

   ② “ID”特征的信息增益
   “ID”有15個唯一值（每個ID對應1條樣本），每個子集 $D_i$ 只有1條樣本（純類別，熵為0）：
   $$H(D|\text{ID})=\sum _{i=1}^{15}\frac{1}{15}\times 0=0?g(D,\text{ID})=0.918?0=0.918$$

   ③ 有效特征“有房子”的信息增益
   “有房子”分兩類（無房=8條，有房=7條），條件熵計算得 $H(D|\text{有房子})\approx 0.497$，故：
   $$g(D,\text{有房子})\approx 0.918?0.497=0.421$$

3. 缺陷暴露：被“ID”誤導的過擬合

   • 增益排序：g(D, ID) > g(D, 有房子)，ID3會優先選 “ID” 作為根節點。
   • 邏輯荒謬：“ID”是純標識（與貸款結果無關），但因取值唯一，決策樹會分裂出15個葉子節點（每個ID對應一個結果），導致 模型僅記憶樣本，無法泛化新數據（如ID=16的新樣本，樹無法判斷）。

這就是ID3的核心缺陷：盲目追求“信息增益最大”，傾向選擇取值多的特征（如ID），最終導致過擬合。

三、C4.5決策樹：信息增益率的優化

3.1 信息增益率的公式與符號解析

信息增益率公式：
$$\text{Gain\_Ratio}(D,A)=\frac{g(D,A)}{\text{IV}(A)}$$

• $\text{Gain\_Ratio}(D,A)$：特征$A$的信息增益率
• $g(D,A)$：特征$A$的信息增益
• $\text{IV}(A)$：特征$A$的內在信息（分裂信息）
  $$\text{IV}(A)=?\sum _{i=1}^n\frac{|D_i|}{|D|}{\log }_2\frac{|D_i|}{|D|}$$
  其中，$n$為特征$A$的取值個數，$|D_i|$為特征$A$取第$i$個值的樣本數。

3.2 信息增益率的意義

信息增益率通過引入一個稱為內在信息（Intrinsic Value，IV）的指標對信息增益進行歸一化處理。其目的是解決ID3算法中偏向于選擇取值較多特征的問題。

內在信息 $\text{IV}(A)$ 反映了特征 $A$ 取值分布的均勻程度。分布越均勻，$\text{IV}(A)$ 的值就越大。通過將信息增益除以 $\text{IV}(A)$，信息增益率有效降低了那些取值數量多、但劃分意義不大的特征的優先級。

可以將其理解為：信息增益是一個“原始得分”，而信息增益率是根據題目難度調整后的“加權得分”。對于取值較少但具有明顯分類效果的特征，它會得到更高的認可，從而避免模型錯誤地偏好那些取值繁多但實際判別能力一般的特征。

3.3 C4.5決策樹：信息增益率修正ID3的過擬合缺陷

含ID特征的數據集構造 ：
在原貸款數據中加入ID列（取值1~15，唯一標識，與貸款結果無關），數據集如下：

ID	年齡	有工作	有房子	信貸情況	類別
1	青年	否	否	一般	拒絕
2	青年	否	否	好	拒絕
3	青年	是	否	好	同意
4	青年	是	是	一般	同意
5	青年	否	否	一般	拒絕
6	中年	否	否	一般	拒絕
7	中年	否	否	好	拒絕
8	中年	是	是	好	同意
9	中年	否	是	非常好	同意
10	中年	否	是	非常好	同意
11	老年	否	是	非常好	同意
12	老年	否	是	好	同意
13	老年	是	否	好	同意
14	老年	是	否	非常好	同意
15	老年	否	否	一般	拒絕

步驟1：計算數據集總熵$H(D)$
總樣本15條，同意=9，拒絕=6：
$$H(D)=?\frac{9}{15}{\log }_2\frac{9}{15}?\frac{6}{15}{\log }_2\frac{6}{15}\approx 0.918$$

步驟2：計算“ID”特征的信息增益率

• 信息增益 $g(D,\text{ID})$：
  ID有15個唯一值，每個子集僅1條樣本（純類別，熵為0）：
  $$H(D|\text{ID})=\sum _{i=1}^{15}\frac{1}{15}\times 0=0?g(D,\text{ID})=0.918?0=0.918$$

• 內在信息 $\text{IV(ID)}$：
  $$\text{IV(ID)}=?\sum _{i=1}^{15}\frac{1}{15}{\log }_2\frac{1}{15}\approx 3.907$$

• 信息增益率：
  $$\text{Gain\_Ratio}(D,\text{ID})=\frac{0.918}{3.907}\approx 0.235$$

步驟3：計算“有房子”特征的信息增益率

• 信息增益 $g(D,\text{有房子})$：
  有房=7條（同意6，拒絕1），無房=8條（同意2，拒絕6）：
  $$H(D|\text{有房子})=\frac{7}{15}\left(?\frac{6}{7}{\log }_2\frac{6}{7}?\frac{1}{7}{\log }_2\frac{1}{7}\right)+\frac{8}{15}\left(?\frac{2}{8}{\log }_2\frac{2}{8}?\frac{6}{8}{\log }_2\frac{6}{8}\right)\approx 0.497$$

  $$g(D,\text{有房子})=0.918?0.497=0.421$$

• 內在信息 $\text{IV(有房子)}$：

  $$\text{IV(有房子)}=?\frac{7}{15}{\log }_2\frac{7}{15}?\frac{8}{15}{\log }_2\frac{8}{15}\approx 0.998$$

• 信息增益率：
  $$\text{Gain\_Ratio}(D,\text{有房子})=\frac{0.421}{0.998}\approx 0.422$$

特征選擇對比

特征	信息增益 ( g )	內在信息 $\text{IV}$	信息增益率
ID	0.918	3.907	0.235
有房子	0.421	0.998	0.422

步驟4：遞歸構建子樹

• 分裂子節點：以信息增益率最高的特征（ “有房子” ）為根節點分裂后，得到兩個子節點：左子節點：無房樣本（8 條，同意 2，拒絕 6）右子節點：有房樣本（7 條，同意 6，拒絕 1）遞歸應用
• C4.5 邏輯：對每個子節點數據集，重復步驟 1-3：計算子節點數據集的總熵 $H(D_i)$；計算各特征（年齡、有工作、信貸情況、ID）的信息增益率；選擇信息增益率最大的特征分裂（若存在）。
• 終止條件（滿足任一條件則停止分裂）：子節點所有樣本屬于同一類別（如右子節點 “有房” 樣本中 6 同意 1 拒絕，若繼續分裂可能得到純類別節點）；信息增益率小于預設閾值（避免無意義分裂）；特征已全部使用或樣本數少于最小閾值。
  $$ID3決策樹$$

$$C4.5決策樹$$

繪圖代碼：

# 導入必要的庫
import pandas as pd  # 用于數據處理和構建 DataFrame
from collections import Counter  # 用于統計樣本數量
from math import log2  # 用于計算對數
from graphviz import Digraph  # 用于可視化決策樹
from sklearn.preprocessing import LabelEncoder  # 用于將字符串特征編碼為數字# =============================================
# 1. 數據準備（含 ID）
# =============================================
# 構建訓練數據集，包含 5 個特征和 1 個目標變量
data = {# 每個樣本的唯一編號，容易造成過擬合"ID": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],# 年齡：青年、中年、老年"年齡": ["青年", "青年", "青年", "青年", "青年", "中年", "中年", "中年", "中年", "中年","老年", "老年", "老年", "老年", "老年"],# 是否有工作：是、否"有工作": ["否", "否", "是", "是", "否", "否", "否", "是", "否", "否","否", "否", "是", "是", "否"],# 是否有房子：是、否"有房子": ["否", "否", "否", "是", "否", "否", "否", "是", "是", "是","是", "是", "否", "否", "否"],# 信貸情況：一般、好、非常好"信貸情況": ["一般", "好", "好", "一般", "一般", "一般", "好", "好", "非常好", "非常好","非常好", "好", "好", "非常好", "一般"],# 類別：是否貸款成功（同意/拒絕）"類別": ["拒絕", "拒絕", "同意", "同意", "拒絕", "拒絕", "拒絕", "同意", "同意", "同意","同意", "同意", "同意", "同意", "拒絕"]
}# 將數據轉換為 pandas 的 DataFrame 格式
df = pd.DataFrame(data)# 提取特征列名列表（所有列除了最后一列）
features = list(df.columns[:-1])  # 特征：ID、年齡、有工作、有房子、信貸情況# 目標變量列名（最后一列）
target = df.columns[-1]  # 類別列名# =============================================
# 2. 信息熵與信息增益計算
# =============================================def entropy(y):"""計算信息熵 H(Y)y: 當前樣本的目標變量值（如：['拒絕', '同意', ...]）返回：當前樣本的信息熵"""counts = Counter(y)  # 統計每個類別的數量total = len(y)  # 總樣本數if total == 0:return 0  # 防止除以 0# 計算 -Σ(p * log2(p))return -sum((count / total) * log2(count / total) for count in counts.values())def conditional_entropy(X_col, y):"""計算條件熵 H(Y|X)X_col: 某個特征列的值（如：['青年', '中年', ...]）y: 對應的目標變量值返回：給定該特征下目標變量的條件熵"""values = set(X_col)  # 獲取該特征的所有唯一值total = len(y)  # 總樣本數ent = 0for v in values:mask = (X_col == v)  # 找到該特征值對應的樣本y_sub = y[mask]  # 取出這些樣本的目標變量ent += len(y_sub) / total * entropy(y_sub)  # 加權求和return entdef info_gain(dataset, feature):"""計算某個特征的信息增益 IG(Y, X)dataset: 整個數據集feature: 當前特征名稱（如："年齡"）返回：該特征的信息增益"""X_col = dataset[feature]  # 取出該特征列y = dataset[target]  # 取出目標變量列return entropy(y) - conditional_entropy(X_col, y)  # 信息增益 = 總熵 - 條件熵def split_info(X_col):"""計算分裂信息（Split Information），用于 C4.5 增益率計算X_col: 某個特征列的值返回：該特征的分裂信息"""counts = Counter(X_col)  # 統計每個特征值出現的次數total = len(X_col)  # 總樣本數# 計算 -Σ(|D_v|/|D| * log2(|D_v|/|D|))return -sum((count / total) * log2(count / total) for count in counts.values())def gain_ratio(dataset, feature):"""計算增益率 GainRatio(Y, X)dataset: 整個數據集feature: 當前特征名稱返回：該特征的增益率"""ig = info_gain(dataset, feature)  # 先計算信息增益si = split_info(dataset[feature])  # 再計算分裂信息return ig / si if si != 0 else float('inf')  # 增益率 = IG / SI# =============================================
# 3. 手動實現 ID3 和 C4.5 決策樹
# =============================================def id3_tree(dataset, features):"""使用 ID3 算法遞歸構建決策樹dataset: 當前數據集features: 當前可用特征列表返回：當前節點的決策樹結構字典"""target_values = dataset[target].unique()  # 獲取當前目標變量的唯一值# 終止條件1：當前樣本全部屬于同一類if len(target_values) == 1:return {'label': target_values[0]}  # 返回葉子節點標簽# 終止條件2：沒有可用特征if not features:most_common = dataset[target].mode().iloc[0]  # 返回多數類作為預測結果return {'label': most_common}# 選擇信息增益最大的特征gains = {f: info_gain(dataset, f) for f in features}  # 計算每個特征的信息增益best_feature = max(gains, key=gains.get)  # 選出最大增益的特征# 構建當前節點信息class_counts = dict(Counter(dataset[target]))  # 統計目標變量分布node_info = {'feature': best_feature,'gain': gains[best_feature],  # 信息增益'class_dist': class_counts,  # 類別分布'n_samples': len(dataset),  # 樣本數量'children': {}  # 子節點}# 遞歸劃分每個特征值remaining_features = [f for f in features if f != best_feature]  # 剩余可用特征for raw_value in dataset[best_feature].unique():  # 遍歷當前特征的每個唯一值sub_data = dataset[dataset[best_feature] == raw_value]  # 劃分子數據集node_info['children'][raw_value] = id3_tree(sub_data, remaining_features)  # 遞歸生成子樹return node_infodef c45_tree(dataset, features):"""使用 C4.5 算法遞歸構建決策樹（基于增益率）dataset: 當前數據集features: 當前可用特征列表返回：當前節點的決策樹結構字典"""target_values = dataset[target].unique()# 終止條件1：當前樣本全部屬于同一類if len(target_values) == 1:return {'label': target_values[0]}# 終止條件2：沒有可用特征if not features:most_common = dataset[target].mode().iloc[0]return {'label': most_common}# 選擇增益率最大的特征gains = {f: gain_ratio(dataset, f) for f in features}best_feature = max(gains, key=gains.get)# 構建當前節點信息class_counts = dict(Counter(dataset[target]))node_info = {'feature': best_feature,'gain_ratio': round(gains[best_feature], 3),'class_dist': class_counts,'n_samples': len(dataset),'children': {}}# 遞歸劃分每個特征值remaining_features = [f for f in features if f != best_feature]for raw_value in dataset[best_feature].unique():sub_data = dataset[dataset[best_feature] == raw_value]node_info['children'][raw_value] = c45_tree(sub_data, remaining_features)return node_info# =============================================
# 4. 構建特征編碼器（用于生成 CART 風格的分割條件）
# =============================================
# 保存每個特征的編碼器，便于后續可視化時使用
feature_encoders = {}for feat in features:le = LabelEncoder()  # 創建編碼器le.fit(df[feat])  # 擬合該特征的編碼規則feature_encoders[feat] = le  # 保存編碼器# =============================================
# 5. 決策樹可視化（CART 風格，支持中文）
# =============================================
def visualize_tree_cart_style(tree, feature_encoders, graph=None, parent_id=None, edge_label=""):"""使用 Graphviz 可視化決策樹（CART 風格）tree: 當前樹節點結構feature_encoders: 編碼器字典graph: 當前圖對象parent_id: 父節點 IDedge_label: 邊上的標簽返回：Graphviz 圖對象"""from uuid import uuid4  # 用于生成唯一節點 IDif graph is None:# 初始化一個空圖，設置字體支持中文graph = Digraph('DecisionTree',format='png',node_attr={'fontname': 'SimHei'},  # 支持中文節點edge_attr={'fontname': 'SimHei'},  # 支持中文邊標簽graph_attr={'fontname': 'SimHei', 'rankdir': 'TB'}  # 樹方向從上往下)node_id = str(uuid4())  # 生成當前節點的唯一標識符if 'label' in tree:# 如果是葉子節點，顯示類別標簽label = f"類別: {tree['label']}"shape = "box"  # 葉子節點用矩形else:# 如果是內部節點，顯示特征、增益等信息feat_name = tree['feature']metric = round(tree.get('gain', tree.get('gain_ratio', 0)), 3)  # 獲取指標值metric_label = "信息增益" if 'gain' in tree else "信息增益率"n = tree['n_samples']  # 樣本數dist = ", ".join([f"{k}={v}" for k, v in tree['class_dist'].items()])  # 分布# 構造節點標簽label = (f"{feat_name}\\n"f"{metric_label}={metric}\\n"f"樣本數={n}\\n"f"分布：{dist}")shape = "ellipse"  # 內部節點用橢圓graph.node(node_id, label=label, shape=shape)  # 添加當前節點到圖中if parent_id:# 如果有父節點，則畫邊graph.edge(parent_id, node_id, label=edge_label)if 'children' in tree:# 如果有子節點，遞歸繪制feat_name = tree['feature']encoder = feature_encoders[feat_name]  # 獲取該特征的編碼器unique_values = df[feat_name].unique()  # 獲取原始特征值sorted_values = sorted(encoder.transform(unique_values))  # 編碼后的排序值for raw_value, child in tree['children'].items():encoded_value = encoder.transform([raw_value])[0]  # 把原始值轉為編碼值display_label = get_edge_label(feat_name, encoded_value, sorted_values)  # 生成邊標簽# 遞歸繪制子樹visualize_tree_cart_style(child, feature_encoders, graph, node_id, display_label)return graphdef get_edge_label(feat_name, encoded_value, sorted_values):"""生成邊標簽，例如：年齡 <= 0.5、年齡 > 0.5feat_name: 特征名encoded_value: 編碼后的特征值sorted_values: 排序后的編碼值列表返回：邊標簽字符串"""index = sorted_values.index(encoded_value)if index == 0:threshold = (sorted_values[index] + sorted_values[index + 1]) / 2return f"{feat_name} <= {threshold:.1f}"elif index == len(sorted_values) - 1:threshold = (sorted_values[index - 1] + sorted_values[index]) / 2return f"{feat_name} > {threshold:.1f}"else:low = (sorted_values[index - 1] + sorted_values[index]) / 2high = (sorted_values[index] + sorted_values[index + 1]) / 2return f"{low:.1f} < {feat_name} <= {high:.1f}"# =============================================
# 6. 主程序：構建并可視化兩種樹
# =============================================# 構建模型
tree_id3 = id3_tree(df, features)  # 構建 ID3 決策樹
tree_c45 = c45_tree(df, features)  # 構建 C4.5 決策樹# 設置可視化圖例格式
dot_id3 = visualize_tree_cart_style(tree_id3, feature_encoders)  # 可視化 ID3 樹
dot_c45 = visualize_tree_cart_style(tree_c45, feature_encoders)  # 可視化 C4.5 樹# 保存為 PNG 文件，并自動打開查看
dot_id3.render("id3_decision_tree_with_id", view=True)
dot_c45.render("c45_decision_tree_with_id", view=True)

3.4 結論：C4.5如何解決過擬合

• ID3的缺陷：ID特征因信息增益最大（0.918）被優先選擇，導致樹分裂為15個葉子節點，完全記憶訓練數據（過擬合）。
• C4.5的修正：ID的信息增益雖高，但內在信息$V(ID)$=3.907極大，導致信息增益率（0.235）低于“有房子”（0.422），因此C4.5選擇 “有房子” 作為根節點，避免被ID特征誤導。
• 本質原因：信息增益率通過IV(A)懲罰了取值多但分類意義小的特征（如ID），使模型更關注真正有判別力的特征，降低過擬合風險。

3.5 C4.5的局限性

• 對取值少的特征仍有偏向：若某特征取值少且IV(A)小，可能被過度優先選擇（如兩取值特征，IV=1時信息增益率=信息增益）。
• 計算復雜度高：需額外計算IV(A)，比ID3耗時更多。

通過信息增益率的歸一化，C4.5在保留ID3可解釋性的同時，有效緩解了“取值多特征偏好”問題，是決策樹從理論到工程應用的重要改進。

四、CART決策樹：基于基尼指數的二叉樹模型

CART 決策樹是一種基于基尼指數（或平方誤差）的二叉樹模型，廣泛應用于分類和回歸任務中。它通過最小化基尼指數來選擇最優劃分特征，確保每一步劃分都能帶來最大純度提升。相較于 ID3 或 C4.5 等多叉樹模型，CART 結構簡單、計算效率高、魯棒性強，是工業界常用的一種決策樹實現方式。

4.1 基尼指數的公式與符號解析

基尼指數相關公式：

• 數據集$D$的基尼值：
  $$\text{Gini}(D)=1?\sum _{k=1}^K{\left(\frac{|C_k|}{|D|}\right)}^2$$

• 特征$A$的基尼指數：
  $$\text{Gini\_index}(D,A)=\sum _{i=1}^n\frac{|D_i|}{|D|}\text{Gini}(D_i)$$

• $\text{Gini}(D)$：衡量數據集$D$的不純度，值越小純度越高

• $\text{Gini\_index}(D,A)$：特征$A$的基尼指數，用于選擇最優分裂特征

• $K$：類別數，$|C_k|$：第$k$類的樣本數，$|D|$：總樣本數

• $n$：特征$A$的取值個數，$|D_i|$：特征$A$取第$i$個值的樣本數

4.2 基尼指數的意義

• 基尼指數衡量的是從數據集中隨機抽取兩個樣本時，它們類別不一致的概率。這個指標越小，說明數據集的純度越高；反之，則表示數據越混雜。

• 在決策樹構建過程中，當我們使用某個特征對數據集進行劃分后，會分別計算每個子集的基尼指數，并通過加權求和得到整體的基尼指數（即 $\text{Gini\_index}(D,A)$ ）。該值越小，意味著劃分后的各子集純度越高，分類效果越好。

• 可以形象地理解為：假設你有一袋球，顏色各異。如果你隨手抓出兩個球，顏色不一樣的可能性越大，說明這袋球越“混亂”（基尼值高）。我們的目標是找到一種分法（特征），讓每次分出來的每一小袋都盡可能接近“同色”，也就是讓每袋的基尼指數盡可能小。

4.3 CART決策樹案例演示：貸款申請的基尼指數計算

沿用前例，計算特征"有房子"的基尼指數（CART為二叉樹，需將多取值特征轉化為二叉分裂）。

步驟1：計算數據集D的基尼值
$$\text{Gini}(D)=1?{\left(\frac{5}{15}\right)}^2?{\left(\frac{10}{15}\right)}^2=0.4444$$

步驟2：計算"有房子"特征的基尼指數

• 有房子：7條樣本，6同意，1拒絕
  $$\text{Gini}(有房子)=1?{\left(\frac{6}{7}\right)}^2?{\left(\frac{1}{7}\right)}^2=0.2449$$
• 無房子：8條樣本，2同意，6拒絕
  $$\text{Gini}(無房子)=1?{\left(\frac{2}{8}\right)}^2?{\left(\frac{6}{8}\right)}^2=0.375$$
• 基尼指數：
  $$\text{Gini\_index}(D,有房子)=\frac{7}{15}\times 0.2449+\frac{8}{15}\times 0.375=0.3176$$

步驟3：計算其他特征的基尼指數
以"年齡"特征為例，需轉化為二叉分裂（如"青年"vs"非青年"）：

• 青年：5樣本，4拒絕，1同意
  $$\text{Gini}(青年)=1?{\left(\frac{4}{5}\right)}^2?{\left(\frac{1}{5}\right)}^2=0.32$$
• 非青年：10樣本，6拒絕，4同意
  $$\text{Gini}(非青年)=1?{\left(\frac{6}{10}\right)}^2?{\left(\frac{4}{10}\right)}^2=0.48$$
• 基尼指數：
  $$\text{Gini\_index}(D,年齡)=\frac{5}{15}\times 0.32+\frac{10}{15}\times 0.48=0.4267$$

步驟4：選擇基尼指數最小的特征
"有房子"的基尼指數0.3176最小，作為分裂特征，生成二叉樹：

• 左子樹：有房子，基尼值0.2449（更純）
• 右子樹：無房子，基尼值0.375（較不純）

步驟5：遞歸構建子樹
在完成當前節點的最佳劃分特征選擇后（如“有房子”），CART 決策樹會基于該特征的不同取值，將數據集劃分為兩個子集，并對每個子集遞歸地重復以下過程：

• 判斷是否滿足終止條件：
  • 若當前子集中所有樣本屬于同一類別（基尼值為 0），則將其設為葉子節點，直接返回類別結果。
  • 若達到預設的最大深度（如 max_depth=3）或樣本數過少（如小于 min_samples_split），也停止繼續分裂。
• 否則，繼續進行最優劃分特征的選擇：
  • 對當前子集重新計算各個特征的基尼指數。
  • 選擇基尼指數最小的特征作為新的劃分依據。
  • 再次劃分數據集并生成新的左右子節點：
  • 每個子節點代表一個劃分后的子集。
  • 對每個子節點遞歸執行上述步驟，直到滿足終止條件為止。
• 最終形成一棵完整的二叉決策樹：

繪圖代碼：

# 導入必要的庫
import pandas as pd  # 用于構建 DataFrame 數據結構
from sklearn.tree import DecisionTreeClassifier, plot_tree  # 構建和可視化決策樹
from sklearn.preprocessing import LabelEncoder  # 對字符串特征進行編碼
import matplotlib.pyplot as plt  # 可視化工具# 設置中文字體顯示（解決中文亂碼問題）
plt.rcParams['font.sans-serif'] = ['SimHei']  # 將默認字體設置為"SimHei（黑體）"，確保中文標簽正常顯示
plt.rcParams['axes.unicode_minus'] = False  # 修復負號顯示為方塊的問題（確保特殊符號渲染正常）# =============================================
# 1. 數據準備（含 ID）
# =============================================
# 構建訓練數據集，包含 5 個特征和 1 個目標變量
data = {# 每個樣本的唯一編號，容易造成過擬合"ID": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],# 年齡：青年、中年、老年"年齡": ["青年", "青年", "青年", "青年", "青年", "中年", "中年", "中年", "中年", "中年","老年", "老年", "老年", "老年", "老年"],# 是否有工作：是、否"有工作": ["否", "否", "是", "是", "否", "否", "否", "是", "否", "否","否", "否", "是", "是", "否"],# 是否有房子：是、否"有房子": ["否", "否", "否", "是", "否", "否", "否", "是", "是", "是","是", "是", "否", "否", "否"],# 信貸情況：一般、好、非常好"信貸情況": ["一般", "好", "好", "一般", "一般", "一般", "好", "好", "非常好", "非常好","非常好", "好", "好", "非常好", "一般"],# 類別：是否貸款成功（同意/拒絕）"類別": ["拒絕", "拒絕", "同意", "同意", "拒絕", "拒絕", "拒絕", "同意", "同意", "同意","同意", "同意", "同意", "同意", "拒絕"]
}# 將數據轉換為 pandas 的 DataFrame 格式
df = pd.DataFrame(data)# 提取特征和目標變量
X = df.drop("類別", axis=1)  # 特征：年齡、有工作、有房子、信貸情況
y = df["類別"]  # 目標變量：類別（是否貸款成功）# =============================================
# 2. 特征編碼（將字符串特征轉為數字）
# =============================================
# 創建 LabelEncoder 并對每個特征列進行編碼
encoders = {}  # 存儲每個特征的編碼器
for col in X.columns:le = LabelEncoder()X[col] = le.fit_transform(X[col])  # 轉換為數字encoders[col] = le  # 保存編碼器供后續反編碼用# 對目標變量進行編碼：'拒絕' -> 0, '同意' -> 1
y = LabelEncoder().fit_transform(y)# =============================================
# 3. 構建 CART 決策樹模型
# =============================================
# 創建 CART 分類器，使用默認的 gini 指數作為劃分標準
clf = DecisionTreeClassifier(criterion='gini', max_depth=3)# 訓練模型
clf.fit(X, y)# =============================================
# 4. 使用 matplotlib 可視化決策樹結構
# =============================================
# 設置繪圖風格
plt.figure(figsize=(10, 6))  # 設置畫布大小# 繪制決策樹結構圖
plot_tree(clf,  # 決策樹模型feature_names=X.columns,  # 特征名稱class_names=["拒絕", "同意"],  # 類別名稱（中文支持）filled=True,  # 使用顏色填充節點fontsize=10,  # 字體大小proportion=False,  # 顯示樣本數量而非比例rounded=True  # 圓角矩形顯示節點
)# 設置圖像標題并調整布局
plt.title("CART 決策樹結構（基于基尼指數）")
plt.tight_layout()  # 自動調整子圖參數，防止重疊# 顯示圖像
plt.show()

4.4 Scikit-learn 中 CART 決策樹的 API

1. 分類樹：DecisionTreeClassifier
   用于離散標簽分類（如是否貸款），基于基尼指數或信息熵生成二叉樹。

• 核心參數：
  criterion 控制分裂標準（gini為默認基尼指數，entropy為信息熵）；
  max_depth 限制樹深度（避免過擬合，如設為3-10）；
  min_samples_split 規定節點分裂的最小樣本數（默認2）；
  min_samples_leaf 設定葉子節點最小樣本數（默認1）。
• 關鍵方法：
  fit(X, y) 訓練模型（X為特征矩陣，y為離散標簽）；
  predict(X) 預測類別；
  predict_proba(X) 輸出類別概率；
  score(X, y) 計算準確率。

2. 回歸樹：DecisionTreeRegressor
   用于連續值預測（如房價），基于均方誤差或平均絕對誤差分裂。

• 核心參數：
  criterion 可選mse（均方誤差，默認）或mae（平均絕對誤差）；
  其他參數（如max_depth、min_samples_split）與分類樹邏輯一致。
• 關鍵方法：
  fit(X, y) 訓練模型（y為連續值）；
  predict(X) 輸出回歸值；
  score(X, y) 計算R2系數（越接近1擬合越好）。

3. 核心共通點

• 分裂策略：splitter='best'（全局最優）或'random'（隨機分裂防過擬合）；
• 特征重要性：訓練后通過feature_importances_屬性獲取；
• 可視化：用sklearn.tree.export_graphviz或plot_tree展示樹結構。

4. 分類與回歸差異
   分類樹用基尼/熵衡量純度，輸出類別概率；回歸樹用MSE/MAE衡量誤差，輸出連續值預測，評估指標為R2而非準確率。

4.5 小結

CART決策樹的核心優勢在于：

1. 始終生成二叉樹，結構更簡單
2. 基尼指數計算效率高于熵運算
3. 同時支持分類和回歸任務（回歸時使用平方誤差最小化）
4. 對噪聲數據和缺失值的處理更魯棒

五、三大決策樹模型對比總結

模型	核心指標	節點分裂方式	特征處理	樹結構	優缺點
ID3	信息增益	多叉分裂	僅支持離散特征	多叉樹	優點：計算簡單；缺點：偏向取值多的特征，易過擬合
C4.5	信息增益率	多叉分裂	支持離散/連續特征	多叉樹	優點：修正ID3的偏向問題；缺點：計算復雜，對取值少的特征仍有偏向
CART	基尼指數	二叉分裂	支持離散/連續特征	二叉樹	優點：計算高效，泛化能力強，支持分類/回歸；缺點：對高維數據表現不佳

決策樹的發展歷程體現了機器學習算法的優化思路——從簡單有效到復雜精準，再到平衡效率與性能。實際應用中，可根據數據特點和任務需求選擇合適的決策樹模型，或采用集成學習（如隨機森林）進一步提升模型效果。

六、其他重要決策樹算法

6.1 CHAID：基于統計檢驗的決策樹

核心思想：使用卡方檢驗（分類目標）或F檢驗（連續目標）評估特征與目標的相關性

公式示例：
$${\chi }^2=\sum \frac{(O_i?E_i{)}^2}{E_i}$$
其中$O_i$為觀察頻數，$E_i$為期望頻數

優勢：

• 支持多叉分裂，直觀展示特征交互作用
• 自動處理缺失值
• 可生成非二叉樹結構

應用場景：市場細分、客戶畫像分析

6.2 QUEST：快速無偏決策樹

核心思想：通過統計檢驗選擇分裂特征，避免CART對連續特征的偏向

算法流程：

1. 使用ANOVA F-test選擇最佳分裂特征
2. 應用二次判別分析確定最優分裂點
3. 遞歸構建二叉樹

優勢：

• 無偏特征選擇
• 計算效率高
• 處理高維數據能力強

應用場景：基因表達數據分析、高維生物信息學

6.3 條件推斷樹：統計驅動的決策樹

核心思想：基于置換檢驗（Permutation Test）選擇分裂變量和分裂點

算法特點：

1. 計算特征與目標的統計相關性
2. 評估分裂顯著性的p值
3. 僅當p值小于閾值時才進行分裂

公式核心：
$$p\text{-value}=P(|T|\ge |t||H_0)$$
其中$T$為檢驗統計量，$t$為觀察值，$H_0$為無關聯假設

優勢：

• 有效控制變量選擇偏差
• 適用于混合類型特征（離散+連續）
• 提供統計顯著性評估

應用場景：臨床試驗數據分析、社會科學研究

6.4 斜決策樹（Oblique Decision Tree）

核心思想：允許使用特征的線性組合進行分裂（如$0.5\times \text{年齡}+0.8\times \text{收入}>50$）

數學表示：
$$\sum _{j=1}^p{w}_j{x}_j>\theta$$
其中$w_j$為特征權重，$\theta$為閾值

優勢：

• 構建更緊湊的樹結構
• 提升模型泛化能力
• 更好處理相關特征

挑戰：

• 分裂點優化復雜度高
• 需結合線性規劃求解
• 訓練時間顯著增加

應用場景：圖像識別、金融風險評估

6.5 流數據決策樹（Hoeffding Tree）

核心思想：基于Hoeffding不等式，在有限內存下處理無限數據流

核心公式：
$$n>\frac{R^2\ln (1/\delta )}{2{?}^2}$$
其中$n$為所需樣本數，$R$為隨機變量范圍，$\delta$為置信度，$?$為誤差界

優勢：

• 單次遍歷數據
• 實時更新模型
• 有限內存需求

應用場景：實時交易監控、物聯網設備數據分析