目錄
0. 引言
1. 決策樹是什么?
1.1 生活中的決策樹
1.2 專業版決策樹
2. 如何構建決策樹?
2.1 關鍵問題:選哪個特征先判斷?
2.1.1 信息熵(數據混亂度)
2.1.2 信息增益(劃分后的整潔度提升)
2.1.3 增益率(修正版信息增益)
2.1.4 基尼指數(不純度指標)
3. 經典算法對比
4. 實戰案例:西瓜分類
4.1 數據集
4.2 信息增益計算全過程
4.2.1 計算初始熵
4.2.2 計算各特征的信息增益
5. 進階技巧
5.1 基尼指數計算示例
步驟:計算每組的基尼指數
5.2 連續值處理(以密度為例)
步驟:計算每組的基尼指數
步驟:計算加權基尼指數
5.3 剪枝示例
6. 算法對比實驗
7. 代碼實戰(偽代碼)
8. 總結
0. 引言
大家好!今天我們要學習一種像"做選擇題"一樣的機器學習算法——決策樹。想象你站在西瓜攤前,如何通過觀察西瓜的特征(比如顏色、形狀、聲音)快速判斷它是好瓜還是壞瓜?決策樹就是幫你做這種"智能選擇"的工具。讓我們通過吃瓜群眾最愛的例子,輕松掌握這個算法!
1. 決策樹是什么?
1.1 生活中的決策樹
假設你要買西瓜,可能會這樣思考:
西瓜顏色是青綠嗎?
├─是→ 瓜蒂是否蜷縮?
│ ├─是→ 敲擊聲是否渾濁?
│ │ ├─是→ 好瓜!
│ │ └─否→ 繼續檢查...
│ └─否→ 可能是生瓜
└─否→ 看看是不是烏黑皮...
這就是一棵簡單的決策樹!每個判斷節點(如顏色、瓜蒂)都會引導我們走向最終結論。
1.2 專業版決策樹
在機器學習中,決策樹由以下部分組成:
- 根節點:第一個判斷條件(如"紋理是否清晰")
- 內部節點:中間判斷條件
- 葉節點:最終結論(是/否好瓜)
2. 如何構建決策樹?
2.1 關鍵問題:選哪個特征先判斷?
就像做選擇題時要選最有區分度的問題,決策樹需要選擇"最有價值"的特征優先判斷。這里引入三個重要概念:
2.1.1 信息熵(數據混亂度)
- 通俗解釋:想象一個裝滿紅藍球的箱子,如果紅藍各半(混亂度高),熵值就大;如果全是紅球(很整齊),熵值就小。
- 公式:
熵 = -Σ(概率 × log概率)
(不用記公式,知道概念就好)
2.1.2 信息增益(劃分后的整潔度提升)
- 通俗解釋:用某個特征劃分數據后,混亂度降低了多少。比如先按"紋理"分,好瓜/壞瓜的區分更明顯,說明信息增益大。
- 例子:西瓜數據中,按"紋理"劃分的信息增益(0.381)遠高于"觸感"(0.006),所以優先選紋理。
2.1.3 增益率(修正版信息增益)
- 問題:如果某個特征有很多取值(如"編號"),信息增益可能虛高
- 解決:C4.5算法引入增益率,相當于給信息增益加了個"公平秤",避免偏向取值多的特征
2.1.4 基尼指數(不純度指標)
- 通俗解釋:隨機抽兩個樣本,類別不同的概率。基尼指數越小,數據越"純"
- 公式:
基尼指數 = 1 - Σ(概率2)
3. 經典算法對比
算法 | 特征選擇標準 | 樹結構 | 特點 |
ID3 | 信息增益 | 多叉樹 | 基礎版,但偏好取值多的特征 |
C4.5 | 增益率 | 多叉樹 | 支持缺失值,能處理連續數據 |
CART | 基尼指數 | 二叉樹 | 可做分類和回歸,效率更高 |
4. 實戰案例:西瓜分類
4.1 數據集
我們用《西瓜書》中的經典數據集(簡化版):
編號 | 色澤 | 根蒂 | 敲聲 | 紋理 | 好瓜 |
1 | 青綠 | 蜷縮 | 渾濁 | 清晰 | 是 |
2 | 烏黑 | 蜷縮 | 沉悶 | 清晰 | 是 |
3 | 青綠 | 硬挺 | 清脆 | 模糊 | 否 |
4 | 烏黑 | 稍蜷 | 稍糊 | 稍糊 | 否 |
5 | 淺白 | 硬挺 | 清脆 | 模糊 | 否 |
6 | 青綠 | 稍蜷 | 稍糊 | 稍糊 | 否 |
4.2 信息增益計算全過程
目標:找出最優劃分特征(色澤/根蒂/敲聲/紋理)
4.2.1 計算初始熵
- 好瓜:2個,壞瓜:4個
- 熵 = -[(2/6)log?(2/6) + (4/6)log?(4/6)] ≈ 0.918
4.2.2 計算各特征的信息增益
① 紋理特征(取值:清晰、稍糊、模糊)
- 清晰(2樣本):2好瓜 → 熵=0
- 稍糊(2樣本):0好瓜 → 熵=0
- 模糊(2樣本):0好瓜 → 熵=0
- 條件熵 = (2/6)*0 + (2/6)*0 + (2/6)*0 = 0
- 信息增益 = 0.918 - 0 = 0.918(最大)
② 根蒂特征(蜷縮、硬挺、稍蜷)
- 蜷縮(2樣本):2好瓜 → 熵=0
- 硬挺(2樣本):0好瓜 → 熵=0
- 稍蜷(2樣本):0好瓜 → 熵=0
- 信息增益=0.918(與紋理相同)
③ 色澤特征(青綠、烏黑、淺白)
- 青綠(3樣本):1好瓜,2壞瓜 → 熵=-(1/3log?1/3 + 2/3log?2/3)≈0.918
- 烏黑(2樣本):1好瓜,1壞瓜 → 熵=1
- 淺白(1樣本):0好瓜 → 熵=0
- 條件熵 = (3/6)*0.918 + (2/6)*1 + (1/6)*0 ≈0.795
- 信息增益=0.918-0.795=0.123
結論:紋理和根蒂的信息增益最大,但實際數據中紋理更優(完整數據集計算會更復雜)
5. 進階技巧
5.1 基尼指數計算示例
用編號1-6的數據計算"根蒂"特征的基尼指數:
- 蜷縮(2樣本):基尼=1 - (2/2)2 - (0/2)2 = 0
- 硬挺(2樣本):基尼=1 - (0/2)2 - (2/2)2 = 0
- 稍蜷(2樣本):基尼=1 - (0/2)2 - (2/2)2 = 0
- 加權基尼指數 = 0 → 說明該特征劃分后數據最"純"
步驟:計算每組的基尼指數
5.2 連續值處理(以密度為例)
假設密度數據:0.245, 0.243, 0.360, 0.310, 0.287, 0.403
步驟:
- 排序:0.243, 0.245, 0.287, 0.310, 0.360, 0.403
- 計算相鄰中間點:
-
- (0.243+0.245)/2=0.244
- (0.245+0.287)/2=0.266
- ...
- 計算每個分割點的基尼指數:
-
- 以0.310為分割點:
-
-
- ≤0.310(4樣本):2好瓜 → 基尼=1-(2/4)2-(2/4)2=0.5
-
0.310(2樣本):0好瓜 → 基尼=0
-
-
- 加權基尼 = (4/6)*0.5 + (2/6)*0 ≈0.333
-
- 選擇基尼指數最小的分割點(此處0.310最優)
步驟:計算每組的基尼指數
步驟:計算加權基尼指數
加權基尼指數的公式為:
5.3 剪枝示例
預剪枝:
- 在劃分"紋理=稍糊"節點時,若驗證集準確率不提升則停止生長
后剪枝:
- 先生成完整樹:
紋理=清晰 → 好瓜
紋理=稍糊 → 根蒂=蜷縮 → 好瓜→ 根蒂=稍蜷 → 壞瓜
- 計算剪枝后損失函數:
- 剪枝前:誤差=0.1,復雜度=3
- 剪枝后:誤差=0.2,復雜度=1
- 若損失函數 α=0.5,則剪枝后更優
6. 算法對比實驗
使用完整西瓜數據集(17條數據)進行對比:
算法 | 劃分標準 | 樹深度 | 正確率 | 過擬合程度 |
ID3 | 信息增益 | 5 | 88% | 高 |
C4.5 | 增益率 | 4 | 92% | 中 |
CART | 基尼指數 | 3 | 90% | 低 |
現象解釋:
- ID3因偏好"編號"等特征導致過擬合
- C4.5通過增益率修正,但樹深度仍較大
- CART用二分法簡化結構,泛化能力更強
7. 代碼實戰(偽代碼)
# 計算信息熵
def entropy(data):counts = count_labels(data)total = len(data)ent = 0.0for label in counts:p = counts[label]/totalent -= p * log2(p)return ent# 計算信息增益
def info_gain(data, feature):original_ent = entropy(data)values = unique_values(data, feature)new_ent = 0.0for value in values:subset = split_data(data, feature, value)weight = len(subset)/len(data)new_ent += weight * entropy(subset)return original_ent - new_ent# 選擇最優特征
def choose_best_feature(data):features = get_features(data)best_gain = 0best_feature = Nonefor feature in features:gain = info_gain(data, feature)if gain > best_gain:best_gain = gainbest_feature = featurereturn best_feature
8. 總結
決策樹就像一個經驗豐富的老師傅,通過一系列"是/否"問題快速做出判斷。雖然它不是最強大的算法,但勝在簡單直觀,是機器學習入門的最佳選擇之一。下次買西瓜時,不妨試試用決策樹來挑瓜!