决策树详解：从信息熵、信息增益到剪枝实战

1. 决策树是什么：先从“猜人游戏”说起

如果你玩过那种“二十个问题”的猜人游戏，规则很简单：一个人心里想一个角色，另外的人不断提问，对方只回答“是”或“否”，通过一轮轮的筛选把范围缩小，最后锁定到具体答案。比如先问“是男的吗”，再问“戴眼镜吗”，再问“是程序员吗”……每问一句，候选集合就砍掉一大块。这个游戏玩到极致，其实就是一棵决策树在做的事。机器学习里的决策树，说白了就是把这个游戏规则数学化、自动化，让模型从数据里自己学出一套最优的提问顺序。

决策树在机器学习里属于监督学习，既能做分类也能做回归，模型长成一颗倒着长的树：最上面是根节点，中间是内部节点，每个节点代表一个特征的判断条件，每个分支对应一个判断结果，最底层的叶子节点给出最终预测。它的核心优势就两条：一是可解释性强，模型本身就是if-then规则的集合，你完全能跟不懂算法的人讲清楚“为什么模型这么预测”；二是不需要太多数据预处理，不像神经网络那样对特征缩放敏感，离散和连续特征都能处理。

这篇文章是机器学习系列里的第五篇，我打算把决策树完整地过一遍。先讲清楚信息熵、信息增益、基尼系数这些底层概念，再动手用Python从零实现一棵可用的决策树，然后重点聊聊剪枝——这个环节直接决定模型能不能泛化。最后把我实际踩过的坑和调参经验列出来，给正在学或者准备面试的朋友一个相对完整的参考。

2. 核心算法拆解：三种划分指标到底在算什么

2.1 信息熵：量化“混乱程度”

要理解决策树怎么选特征，绕不开香农的信息论。信息熵衡量的是一个系统的混乱程度，公式长这样：

H(X) = -Σ p_i * log2(p_i)

其中p_i是第i个类别在样本中出现的概率。熵越大，说明数据越混乱，不确定性越高。举个最直观的例子，一个集合里如果全是同一类样本，比如10个全是“好瓜”，那p=1，H = -1log2(1) = 0，说明完全确定，没有任何混乱。如果5个好瓜、5个坏瓜，p=0.5，H = -0.5log2(0.5) - 0.5*log2(0.5) = 1，熵达到最大，这时候最拿不准。

决策树的构建逻辑，就是不断选择某个特征，把数据划分成几个子集，让划分后的总熵尽可能小。换句话说，我们希望每次划分之后，每个子集内部的样本尽可能“纯”，最好是同一个类别。这个从“较混乱”到“较有序”的变化量，就是信息增益。

2.2 ID3与信息增益：最朴素的划分方式

ID3算法是决策树最经典的版本，它用信息增益来选择划分特征。信息增益的计算方式：

Gain(D, A) = H(D) - Σ (|D_v| / |D|) * H(D_v)

其中D是当前样本集合，A是候选特征，v是特征A的取值，D_v是特征A取值为v的那部分子集。信息增益越大，说明用特征A划分后，纯度提升得越明显，这个特征就越应该优先作为划分节点。

我记得教科书上经典的西瓜数据集，第一个根节点选的就是“纹理”，因为按纹理划分后信息增益最大。我当时手动推了一遍：色泽、根蒂、敲声、纹理……逐个算下来，纹理的信息增益确实最高。这个过程看似机械，但手动推一次能帮助你真正理解“特征选择”这四个字的含义，比直接调sklearn的代码有用得多。

ID3有明显的毛病：它偏好取值特别多的特征。比如把“编号”也作为一个特征，每个编号只对应一个样本，算出来的条件熵是0，信息增益直接拉满。这明显不合理，相当于把训练集背下来了，完全失去泛化能力。

2.3 C4.5与信息增益率：给“多值特征”降降温

C4.5算法针对ID3的缺陷，提出了信息增益率的概念。它引入了“固有值”这一项，特征的取值越多，固有值越大，从而对信息增益进行惩罚：

Gain_ratio(D, A) = Gain(D, A) / IV(A) IV(A) = -Σ (|D_v| / |D|) * log2(|D_v| / |D|)

信息增益率不是单纯追求“划分后更纯”，而是兼顾了“这个特征本身好不好划分”。注意，C4.5不是直接把信息增益率最大的特征选出来，而是先从信息增益高于平均水平的特征里，再挑增益率最高的那个。这个细节容易被忽略，面试时被问到“C4.5和ID3什么区别”，如果你能答出这一层，会比只说“C4.5用了增益率”更有说服力。

2.4 CART与基尼系数：目前最常用的选择

现在的工业界和sklearn默认实现，用的都是CART树。CART不计算信息熵，而是用基尼系数衡量纯度：

Gini(D) = 1 - Σ p_i^2

基尼系数越小，纯度越高。划分时，对每个特征计算基尼指数：

Gini_index(D, A) = Σ (|D_v| / |D|) * Gini(D_v)

选基尼指数最小的特征作为划分点。和熵相比，基尼系数没有log运算，计算更快，而且在分类效果上差异并不大，所以工程上普遍用它。

三种算法我整理了一张表，方便对比：

2.5 为什么现在主流是CART

我在实际使用中基本都用CART，很少自己写ID3或C4.5。原因是多方面的：

一是CART生成的是二叉树，结构更简洁，决策边界是轴对齐的矩形切分，可视化出来干净直观。ID3和C4.5可能生成多叉树，一个特征有几个取值就分几叉，看起来分支很多很乱，实际效果也没更好。

二是CART既能分类又能回归，底层框架统一。sklearn里的DecisionTreeClassifier和DecisionTreeRegressor用的都是CART，学习成本低。

三是计算效率高。基尼系数避免了对数运算，在特征多、数据量大的时候速度优势明显。不过我仍然建议初学者把ID3手推一遍，因为它最直观地揭示了决策树的核心逻辑——信息增益就是在衡量“不确定性减少多少”。理解了这一层，后面看随机森林、XGBoost都会轻松不少。

3. 从零实现一棵决策树：Python手写核心代码

3.1 准备数据与工具

理论说再多，不如自己动手写一版。这里我用一个简单但经典的场景：根据天气、温度、湿度、风力四个特征，判断今天适不适合出门运动。数据是纯手造的，很小，但足够把决策树的每个环节跑通。

import numpy as np import pandas as pd from math import log2 data = [ ['sunny', 'hot', 'high', 'weak', 'no'], ['sunny', 'hot', 'high', 'strong', 'no'], ['overcast', 'hot', 'high', 'weak', 'yes'], ['rainy', 'mild', 'high', 'weak', 'yes'], ['rainy', 'cool', 'normal', 'weak', 'yes'], ['rainy', 'cool', 'normal', 'strong', 'no'], ['overcast', 'cool', 'normal', 'strong', 'yes'], ['sunny', 'mild', 'high', 'weak', 'no'], ['sunny', 'cool', 'normal', 'weak', 'yes'], ['rainy', 'mild', 'normal', 'weak', 'yes'], ['sunny', 'mild', 'normal', 'strong', 'yes'], ['overcast', 'mild', 'high', 'strong', 'yes'], ['overcast', 'hot', 'normal', 'weak', 'yes'], ['rainy', 'mild', 'high', 'strong', 'no'], ] columns = ['outlook', 'temperature', 'humidity', 'wind', 'play'] df = pd.DataFrame(data, columns=columns)

这段数据里，outlook有三个取值：sunny、overcast、rainy；temperature有hot、mild、cool三档；humidity有high、normal；wind有weak、strong。标签列是play，yes代表适合运动，no代表不适合。

3.2 核心代码实现

先写两个基础函数，一个是计算信息熵，一个是按特征切分数据集：

def entropy(labels): total = len(labels) if total == 0: return 0 counts = {} for label in labels: counts[label] = counts.get(label, 0) + 1 ent = 0.0 for count in counts.values(): p = count / total ent -= p * log2(p) return ent def split_data(df, feature, value): return df[df[feature] == value]

然后是计算信息增益的核心函数：

def info_gain(df, feature, target='play'): labels = df[target].tolist() base_entropy = entropy(labels) total = len(df) new_entropy = 0.0 values = df[feature].unique() for value in values: subset = df[df[feature] == value] subset_labels = subset[target].tolist() new_entropy += len(subset) / total * entropy(subset_labels) return base_entropy - new_entropy

选最优特征的函数：

def best_feature(df, features, target='play'): gains = {} for feature in features: gains[feature] = info_gain(df, feature, target) sorted_gains = sorted(gains.items(), key=lambda x: x[1], reverse=True) return sorted_gains[0]

接下来是递归构建树的函数，这块是核心中的核心。它的逻辑是：如果当前集合里所有样本标签一样，就返回这个标签作为叶子节点；如果特征用完但标签还不一致，就返回多数投票结果；否则，选择最优特征，根据特征的每个取值递归生成子树：

def build_tree(df, features, target='play'): labels = df[target].tolist() # 如果所有样本都属于同一类，返回该类别 if len(set(labels)) == 1: return labels[0] # 如果没有可用特征了，返回多数投票 if len(features) == 0: majority = df[target].value_counts().idxmax() return majority # 选择最优特征 best = best_feature(df, features, target) tree = {best: {}} values = df[best].unique() for value in values: subset = df[df[best] == value] # 如果某个取值下没有样本，返回多数投票 if len(subset) == 0: majority = df[target].value_counts().idxmax() tree[best][value] = majority else: remaining_features = [f for f in features if f != best] tree[best][value] = build_tree(subset, remaining_features, target) return tree

这段代码打印出来就是一棵嵌套字典的树结构，比如根节点是outlook，outlook下面有三个子分支，每个分支再继续往下分。

3.3 训练与预测效果

用上面的数据直接跑：

features = ['outlook', 'temperature', 'humidity', 'wind'] tree = build_tree(df, features) print(tree)

输出的树结构大概是这样的：

{ 'outlook': { 'sunny': { 'humidity': { 'high': 'no', 'normal': 'yes' } }, 'overcast': 'yes', 'rainy': { 'wind': { 'weak': 'yes', 'strong': 'no' } } } }

这个结果很符合直觉：阴天（overcast）不管其他条件直接去运动；晴天看湿度，湿度正常就去，湿度高不去；下雨天看风力，风弱去，风强不去。树的逻辑可以完整翻译成几条if-then规则，非常直观。

自己写一遍代码，你会发现决策树的构建过程本质上就是一个递归的“找最优特征、切分数据、再递归”的过程。它没什么高深的地方，代码量也不大，但每个环节都很关键。我当时在写这段代码时踩过一个坑：直接用df[df[best] == value]切分数据时，如果某个取值下的子集为空，必须返回多数投票，否则递归会陷入死循环。这个边界情况在书上往往一笔带过，但实际写代码时很容易漏掉。

4. 剪枝：防止过拟合的关键一步

4.1 预剪枝与后剪枝到底在做什么

决策树如果不加限制，会一直长到把所有训练样本都正确分类为止。训练集上准确率可能接近100%，但一到新数据上就露馅。原因很简单：树太深，把训练数据里的噪声和个别异常点全都学进去了。这就好比考试前把练习册的答案都背下来了，碰见稍微变形的题目就不会做了。

剪枝就是给这棵树“做减法”，去掉一些不必要的分支，让模型更简单、更泛化。剪枝分两种：预剪枝和后剪枝。

预剪枝是在建树过程中实时判断，如果当前节点的划分不能带来验证集准确率的提升，就停止划分，把这个节点直接变成叶子节点。优点是效率高，边建边剪，不用等整棵树长完；缺点是可能会漏掉一些“当前看来没用、但后续划分会带来收益”的特征，也就是“欠拟合”风险稍高。因为在决策树的贪婪策略下，某一步没迈出去，可能就永远没机会补回来了。

后剪枝是先把树完整建好，然后自底向上地考察每个内部节点：如果把这个节点替换成叶子节点（用多数投票定类别），验证集准确率不降反升，就进行剪枝。这个做法更保守，不容易漏掉好特征，但计算开销大，要等整棵树长完再回头修剪。

4.2 实操对比：预剪枝 vs 后剪枝

我拿上面的运动数据集做了一次对比实验，将数据集按7:3随机分成训练集和验证集，分别对预剪枝和后剪枝进行了测试。由于手写版本只有14条数据，本身就不易过拟合，对比并不明显。所以我又生成了一个100条样本的模拟数据，让效果更直观。

用的是sklearn自带的接口：

from sklearn.tree import DecisionTreeClassifier from sklearn.model_selection import train_test_split X_train, X_val, y_train, y_val = train_test_split( X, y, test_size=0.3, random_state=42 ) # 不剪枝 clf_default = DecisionTreeClassifier(random_state=42) clf_default.fit(X_train, y_train) train_score_default = clf_default.score(X_train, y_train) val_score_default = clf_default.score(X_val, y_val) # 预剪枝：限制最大深度 clf_pre = DecisionTreeClassifier(max_depth=3, random_state=42) clf_pre.fit(X_train, y_train) train_score_pre = clf_pre.score(X_train, y_train) val_score_pre = clf_pre.score(X_val, y_val) # 后剪枝：用代价复杂度剪枝 path = clf_default.cost_complexity_pruning_path(X_train, y_train) ccp_alphas = path.ccp_alphas clf_post = DecisionTreeClassifier(random_state=42, ccp_alpha=0.01) clf_post.fit(X_train, y_train) train_score_post = clf_post.score(X_train, y_train) val_score_post = clf_post.score(X_val, y_val) print(f"不剪枝: 训练集准确率 {train_score_default:.3f}, 验证集准确率 {val_score_default:.3f}") print(f"预剪枝: 训练集准确率 {train_score_pre:.3f}, 验证集准确率 {val_score_pre:.3f}") print(f"后剪枝: 训练集准确率 {train_score_post:.3f}, 验证集准确率 {val_score_post:.3f}")

这里要解释一下sklearn的cost_complexity_pruning_path，它返回一系列ccp_alpha的候选值，每个值对应一个剪枝程度，alpha越大，剪枝越狠。实际使用中可以遍历alpha，找出验证集上效果最好的那个。

结果通常是这样的规律：不剪枝的树，训练集准确率接近1，但验证集可能只有0.7左右；预剪枝max_depth=3后，训练集准确率降到0.85左右，验证集提升到0.8左右；后剪枝后验证集会再稍好一点，因为这棵树是在完整建完之后才进行的剪枝，捕捉到的信息更完整。

注意：实际数据不同，准确率会有浮动，但趋势基本一致——剪枝会牺牲一部分训练集准确率，换来验证集准确率的提升，这就是“用偏差换方差”。

4.3 关于剪枝的独家心得

剪枝不是越狠越好。我见过很多人无脑设置max_depth=2，结果模型欠拟合，什么都学不到。经验法则是：先不设任何限制跑一版，看默认树的深度和验证集分数，然后从max_depth等于默认树深度的一半开始搜索，用网格搜索或随机搜索找到最优点。

还有一个容易被忽略的参数是min_samples_leaf，它代表叶子节点的最少样本数。这个参数比max_depth更平滑，不会像max_depth那样一刀切地限制树的深度，而是动态地决定“叶子节点再细分是否值得”。我通常会把min_samples_leaf设成训练集样本数的1%到5%之间，效果比单纯调max_depth要稳。

后剪枝在sklearn里没有独立的“先建完再修剪”的接口，最接近的就是ccp_alpha，也就是代价复杂度剪枝。它其实是后剪枝思想的一种实现：在损失函数里加上一项与叶子节点数量成正比的惩罚项，然后通过交叉验证选alpha。理解了这个机制，你就可以把ccp_alpha当成一个正则化参数来调，和岭回归里的alpha是一个思路。

5. 连续值、缺失值与回归扩展

5.1 连续特征怎么处理：二分法切分

前面用的都是离散特征。实际数据里出现最多的是连续特征，比如年龄、收入、温度。CART处理连续特征的方式是二分法：对特征A的所有取值从小到大排序，然后在相邻取值的中点尝试切分，看看哪个切分点让基尼指数最小，就把数据分成“小于等于阈值”和“大于阈值”两部分。

举个简单例子，假设样本的“温度”分别是12、16、19、22、25，对应的标签有yes也有no。那候选切分点就是(12+16)/2=14、(16+19)/2=17.5、(19+22)/2=20.5、(22+25)/2=23.5这4个点，分别计算按14、17.5、20.5、23.5切分后的基尼指数，选出最优的那个。

这个机制意味着，决策树对连续特征的切分点是数据驱动的，不需要提前做标准化。它不会假设特征服从正态分布，也不会因为特征取值范围大就产生偏见。这也是决策树一个比较省心的优点。

5.2 缺失值怎么处理：两个层面的问题

缺失值处理是决策树里的一个经典考点，分两个层面展开：

第一个层面是，有缺失值的样本怎么参与特征选择？C4.5的答案是：计算信息增益时，只用那些在特征A上没有缺失的样本计算权重。也就是说，先按无缺失样本的子集计算信息增益，再乘上无缺失样本占比作为修正。

第二个层面是，特征A上有缺失值的样本，划分时该去哪个分支？C4.5的做法是把样本同时分到所有分支，但每个分支上都带上一个权重，权重等于该分支的样本数占无缺失样本总数的比例。sklearn的CART实现略有不同，它默认会把缺失样本分到最常去的那个分支，保证每个样本最终都会落到一个叶子节点上。

提示：实际项目里，如果缺失值比例超过30%，我不会直接把全部信息交给决策树去处理，而是先做特征工程，判断一下这个特征是否还有保留价值。缺失太多本身可能说明数据采集环节有问题，盲填均值反而会引入偏差。

5.3 回归树：从分类走向数值预测

决策树不只是能分类，CART回归树的逻辑也很清晰：叶子节点不再是类别，而是一个数值——通常是该节点下样本标签的均值。划分标准不再是基尼系数，而是均方误差MSE。

from sklearn.tree import DecisionTreeRegressor X = np.array([[1], [2], [3], [4], [5], [6], [7], [8]]) y = np.array([3.5, 4.2, 5.1, 6.8, 8.0, 9.5, 10.2, 11.0]) reg = DecisionTreeRegressor(max_depth=3, random_state=42) reg.fit(X, y)

回归树在实际业务里用得挺多，比如预测用户生命周期价值、预测某个商品的销量区间。它的缺点是预测值不连续，会形成阶梯状的输出，因为叶子节点输出的是一个常数。如果你需要平滑的预测曲线，可以考虑随机森林或者梯度提升树。

6. 常见问题与调参经验

6.1 常见问题速查表

下面这些是我在写决策树时遇到过的典型问题，整理成了一张速查表：

6.2 调参顺序与个人经验

决策树调参我一般按这个顺序来：

第一步，先固定一个随机种子，把基线跑出来。随机种子影响树的构建，尤其是当特征重要性差不多时，随机选择特征会带来不同的结果。做实验前不固定种子，后面根本没法复现。

第二步，调min_samples_leaf。从10开始往下试，观察验证集分数的变化。这个参数控制叶子节点大小，对泛化性能影响明显，而且搜索空间不大。

第三步，调max_depth。如果树深已经到50以上还没看到过拟合，说明数据量大、特征多，可以考虑用max_depth=10到20的区间搜索。如果数据量小，树深度一般不会太大，不用刻意设限。

第四步，用ccp_alpha做后剪枝。把cost_complexity_pruning_path跑一遍，画出验证集分数随alpha变化的曲线，选最优点。这一步通常能带来0.01到0.03的提升。

第五步，如果仍然不满意，考虑换集成模型。单棵决策树的性能上限是比较清楚的，随机森林和梯度提升树会在决策树的基础上大幅提升准确率和稳定性。

我个人不太建议在单棵决策树上花太多时间追求极致精度。它的最大价值在于可解释性——业务方问起“为什么这个用户被判定为高风险”，你可以直接回答“因为他的收入等级是low，且历史逾期次数大于2，且最近借款间隔小于30天”。这在信贷风控、医疗诊断这类对解释性要求极高的场景里，是黑盒模型替代不了的。如果想进一步提升精度，把决策树作为基础模型去做集成，才是更常见的路径。

我在实际使用中发现一个特别实用的小技巧：把决策树模型导出为文本规则，可以直接用sklearn.tree.export_text，它会生成一段非常清晰的if-then规则文本，放在业务评审文档里很有说服力。如果要做更复杂的可视化，可以用plot_tree把树画出来，然后保存成图片给团队看。树深度控制在4以内时，可视化效果最好，超过5层基本就糊成一团没法看了。

7. 写在最后：一点实际体会

决策树这个模型最迷人的地方，在于它把“人如何做决定”这件事用数学方式表达了出来，而且表达得相当忠实。每次我向刚入门的朋友介绍它，都会用猜人游戏做引子，因为大家都玩过，一解释就懂。等他们真的把代码跑通，把树结构打印出来，看到那棵嵌套字典的树开始“自动”分类时，那种“原来机器学习就这么回事”的顿悟感特别真实。

但我也必须说一句大实话：单棵决策树的精度在绝大多数真实业务场景里都不够看。它是极好的基学习器、极好的可解释性工具、极好的教学素材，但不要指望它单枪匹马打赢复杂任务。我这几年的经验是，决策树最合适的定位是“第一幕的主角”——先用它建立baseline，理解数据的结构和特征的重要性，然后再让XGBoost、LightGBM这些进阶选手接管精细化拟合。

最后分享一个我在项目里反复用到的小做法：不管最终用的是不是决策树，都会先跑一版决策树，把特征重要性打出来，作为特征筛选的初步依据。这个习惯帮我避免过很多次“拿到数据就猛堆特征”的坑。如果你刚开始接触机器学习，不妨也从这个思路切入，先用决策树认识你的数据，再做深度模型。