简介：这份压缩包是西瓜书《机器学习》第四章决策树的Python配套实现，面向刚读完理论、想通过编程加深理解的机器学习初学者，以及需要完成4.3、4.4、4.6习题、希望拿到可运行参考代码的本科生。资源覆盖基于信息熵的划分选择、基于基尼指数的CART构建，能对西瓜数据集2.0生成预剪枝、后剪枝与未剪枝决策树，并加入4个UCI数据集的实验对比，方便完成统计显著性检验。压缩包共9个文件，包含4个Python脚本与5个CSV数据集，整体仅16KB；脚本覆盖决策树生成、剪枝、树形绘图与对比逻辑，CSV涵盖西瓜数据集2.0/3.0及多个UCI标准数据集，目录结构一目了然。这份代码可直接替换数据文件后运行，也可结合教材逐段阅读，适合课程实验、作业复现与期末报告参考。目前已有10322人学习，是入门决策树实现时很实用的练习资源。

1. 为什么都在啃西瓜书第四章：决策树是第一个“能讲人话”的模型

接触一个新机器学习任务，很多人第一次产生「我好像真的懂了某个算法」的时刻，是在搞懂决策树的时候。神经网络权重说不清，逻辑回归系数要解释半天，只有决策树能把「如果色泽青绿、根蒂蜷缩，就是好瓜」这种规则直接讲给人听，业务方也敢指着某个分支问你「为什么这里不能分到另一边」。西瓜书第四章从信息熵、信息增益一路推到剪枝，是整本书里最适合一边读原理、一边用 Python 把代码写出来验证的章节。这篇笔记按我做机器学习实战的习惯，带你把这一章的 ID3、C4.5、CART 三套准则分别实现，再落到 sklearn 的决策树分类器上做参数调优。手写一遍的意义不在于重复造轮子，而在于让「熵」从公式变成能在终端里打印出来的数字，之后看任何树模型都不慌。新手能照段落把代码跑通，熟手可以直接跳到剪枝和连续值那几段核对边界。

2. 从信息熵到划分选择：三个准则的公式、直觉与适用场景

2.1 信息增益与ID3：为什么“纯度”能用熵来度量

判断一次划分好不好，先得回答「一个集合有多纯」。如果某个集合里全是同一类样本，那已经不需要再分；如果两类各占一半，不确定度最高，必须继续问问题。熵就是量化这种不确定度的工具，西瓜书里信息熵的定义是：

Ent(D) = -Σ_{k=1}^{|Y|} p_k * log2(p_k)

其中 p_k 是第 k 类样本占比。熵越大，集合越乱；熵为 0 时所有样本属于同一类。用 Python 写出来只要几行：

import numpy as np def entropy(labels): # labels 是一维数组，元素是类别字符串或整数编码 _, counts = np.unique(labels, return_counts=True) probs = counts / counts.sum() return -np.sum(probs * np.log2(probs)) # 手算对照：9个好瓜、8个坏瓜的根节点熵 root = np.array(['好瓜'] * 9 + ['坏瓜'] * 8) print(entropy(root)) # 约 0.998

代码逻辑：np.unique同时返回去重后的类别标签和计数，probs = counts / counts.sum()得到 p_k，最后用np.log2算二进制熵。对底数取 2 是为了让熵的单位是比特，实际上取 e 或 10 只会让熵值成比例缩放，不影响最终选哪个属性。套公式验证一下：根节点好瓜 9 个、坏瓜 8 个，p1=9/17≈0.529，p2=8/17≈0.471，熵 ≈ 0.998，和代码输出一致。

有了熵，信息增益就顺理成章了。划分前集合的熵，减去按属性 a 划分后各子集熵的加权平均：

Gain(D, a) = Ent(D) - Σ_v (|D_v| / |D|) * Ent(D_v)

v 是属性 a 的取值。ID3 在每个节点挑选信息增益最大的属性来划分，直觉就是：做完这次划分，不确定度下降最多，纯度提升最大。接着算「色泽」这个属性：青绿、乌黑、浅白三组的好瓜分布分别是 3/2、4/2、2/2，加权熵约 0.576，信息增益约 0.422。后面无论手写实现还是调 sklearn，都能拿这两个数核对模型的第一步划分有没有选对属性。

2.2 增益率与C4.5：信息增益偏爱取值多的属性怎么办

信息增益有个明显毛病：属性取值越多越容易被选中。最极端的例子是用「编号」做属性，每个样本独享一个分支，每个分支熵为 0，信息增益直接拉满，但这样的树没有任何泛化能力。C4.5 用增益率修正，在信息增益基础上除以一个「固有值」：

Gain_ratio(D, a) = Gain(D, a) / IV(a)

IV(a) = -Σ_v (|D_v| / |D|) * log2(|D_v| / |D|)

固有值的公式和信息熵长得一样，只是它统计的是属性取值分布的均匀程度。取值越多、分布越均匀，固有值越大，增益率被惩罚得越狠。实现固有值也很快：

def intrinsic_value(partition): # partition 是列表，每个元素是某个属性取值对应的样本下标数组 total = sum(len(p) for p in partition) iv = 0.0 for p in partition: prob = len(p) / total iv -= prob * np.log2(prob) return iv

注意增益率也不是完美的，它可能过度偏好取值很少的属性。西瓜书给的应对方式是：先从候选属性里挑出信息增益高于平均水平的属性，再从这些属性里选增益率最高的。我复现时会把这条启发式直接写在注释里，提醒自己不要对着所有属性argmax(gain_ratio)一把梭，那会和教材结果对不上。

2.3 基尼指数与CART：砍掉对数运算的工程派选择

CART 决策树用基尼指数，基尼值定义为：

Gini(D) = 1 - Σ_{k=1}^{|Y|} p_k^2

它衡量从集合里随机抽两个样本，类别不一致的概率。基尼值越小，集合越纯。相比熵里的对数运算，基尼只需要平方和，计算更快，这也是大数据场景里 sklearn 默认用gini的原因之一。Python 实现：

def gini(labels): _, counts = np.unique(labels, return_counts=True) probs = counts / counts.sum() return 1 - np.sum(probs ** 2) print(gini(root)) # 约 0.4976

对属性 a 的基尼指数，是划分后各子集基尼值的加权平均，CART 选择基尼指数最小的属性。关键区别是：ID3 和 C4.5 允许一个属性分出多个分支，而 CART 强制建二叉树，对取值很多的离散属性要「二分离散」，常见做法是枚举属性取值的子集，把样本分成「属于这个子集」和「不属于」两类，再挑基尼指数最小的那个组合。三个准则放在一起对比更直观：

再补充一个复现时常遇到的小问题：任何底数的 log 只差常数倍，信息增益是差值，比较时不改变顺序；基尼指数没有 log，它受类别数量分布影响的形态和熵不完全一样。手写代码时用 log2 和 log10 在分类效果上等价，但打印出的熵值不同，核对教材数字时务必统一用 log2。我自己的选型建议：复现西瓜书习题时三个准则都实现一遍，体会差别；真正跑机器学习应用流程时直接用 sklearn 的 CART，因为它把离散值、连续值和缺失值处理都打包好了，不需要在模型层重复造轮子。

3. 用 Python 把西瓜书第四章从零写一遍：数据结构与递归划分

3.1 节点与树的数据结构：字典嵌套就够了

写一个Node类当然规范，但复现教材时字典更灵活。我习惯用一个四字段字典表示节点：attr记录当前节点用哪个属性做划分，split记录连续值的阈值（离散属性为 None），children是分支到子节点的映射，label在叶子节点里填多数类。整棵树就是层层嵌套的 dict，print出来能直接看结构，存成 JSON 也方便。

def create_node(): return { "attr": None, # 划分属性索引或名称 "split": None, # 连续值阈值，离散属性为 None "children": {}, # 键为属性取值或 "left"/"right" "label": None # 叶子节点的类别 }

这种结构最大的优点是调试时可以直接用pprint打印整棵树，不用写自定义类的__repr__；缺点是访问子节点时总要记得处理空 children。后面所有递归函数都约定：非叶子节点必有 children，叶子节点必有 label。这个约定能避免大量if node is None判断。

3.2 划分函数：离散值分组与连续值阈值扫描

先处理离散属性。给定一列属性和标签，按取值切分：

def split_discrete(X_col, y, attr_values): # X_col 是某个属性的取值数组，attr_values 是所有可能取值 partitions = [] for value in attr_values: idx = np.where(X_col == value)[0] if len(idx) > 0: partitions.append(idx) return partitions

连续属性不能按取值直接分组，因为取值几乎都不重复。西瓜书的做法是：排序后取相邻值的均值作为候选阈值，把样本分成<= threshold和> threshold两类。扫描候选阈值时要注意浮点尾巴：

def candidate_thresholds(X_col): sorted_vals = np.sort(np.unique(X_col)) thresholds = [] for i in range(len(sorted_vals) - 1): mid = (sorted_vals[i] + sorted_vals[i + 1]) / 2.0 thresholds.append(float(round(mid, 4))) return thresholds

round(mid, 4)是为了避免 0.30000000000000004 这样的浮点尾巴影响后续比较；实际工程里更推荐用np.float64统一类型。分界符号全程只用<=，左分支踩线，右分支严格大于，这样训练和预测时行为一致。

3.3 递归生成树：三个停止条件一起写

建树函数是递归的，每一层做三件事：检查是否该停；对候选属性算划分质量；选出最好属性并递归建子树。增益函数我拆成离散和连续两个，接口统一返回(增益, 阈值)，否则建树时连续属性会找不到该用哪个阈值切分。

def info_gain_discrete(X_col, y): base_entropy = entropy(y) weighted = 0.0 for value in np.unique(X_col): idx = np.where(X_col == value)[0] weighted += len(idx) * entropy(y[idx]) / len(y) return base_entropy - weighted, None def info_gain_continuous(X_col, y): base_entropy = entropy(y) best_gain, best_threshold = -np.inf, None for t in candidate_thresholds(X_col): left_idx = np.where(X_col <= t)[0] right_idx = np.where(X_col > t)[0] gain = base_entropy - (len(left_idx) * entropy(y[left_idx]) + len(right_idx) * entropy(y[right_idx])) / len(y) if gain > best_gain: best_gain, best_threshold = gain, t return best_gain, best_threshold

离散分支返回的第二个值是 None，连续分支返回最优阈值。最容易出错的地方就在这里：循环里如果上一个属性是连续值，把split带进了下一个离散属性的判断里，最后建树时机麻。因此赋值时一定要写成：

best_split = split if attr in continuous_attrs else None

建树主体：

def build_tree(X, y, attrs, continuous_attrs): # y 必须是整数编码，0/1 或 0/1/2 if len(np.unique(y)) == 1: return {"label": int(y[0])} if len(attrs) == 0: return {"label": int(np.bincount(y).argmax())} best_attr, best_split, best_gain = None, None, -np.inf for attr in attrs: if attr in continuous_attrs: gain, split = info_gain_continuous(X[:, attr], y) else: gain, split = info_gain_discrete(X[:, attr], y) if gain > best_gain: best_gain = gain best_attr = attr best_split = split if attr in continuous_attrs else None if best_gain < 1e-6: return {"label": int(np.bincount(y).argmax())} node = create_node() node["attr"] = best_attr node["split"] = best_split if best_split is not None: left_idx = np.where(X[:, best_attr] <= best_split)[0] right_idx = np.where(X[:, best_attr] > best_split)[0] node["children"]["left"] = build_tree(X[left_idx], y[left_idx], attrs, continuous_attrs) node["children"]["right"] = build_tree(X[right_idx], y[right_idx], attrs, continuous_attrs) else: for value in np.unique(X[:, best_attr]): idx = np.where(X[:, best_attr] == value)[0] node["children"][value] = build_tree(X[idx], y[idx], attrs - {best_attr}, continuous_attrs) return node

这里必须强调西瓜书里最容易和教材对不上的点：连续属性在后续节点可以再被选用，因为阈值划分不会把一个属性彻底用完；而离散属性用掉之后不该再出现在子节点候选里。所以代码里连续分支调用build_tree时传的是attrs，离散分支才传attrs - {best_attr}。另一个参数是best_gain < 1e-6的停止条件，它用来兜底「继续划分已经无法提升纯度」的情况，不加的话，树会靠 attrs 为空来硬停，结果会长出一堆没意义的深度分支。1e-6 是我习惯的浮点容忍度，数学上等价于 0，工程上留一点余量更稳。

建树之后预测函数就是顺着字典结构往下走：离散属性按取值跳 child，连续属性比较<=和>。如果预测时遇到训练时没见过的取值，常见做法是返回当前节点的多数类，不再下钻。这个兜底逻辑等剪枝时一起处理。

4. 剪枝这块硬骨头：预剪枝、后剪枝与排查记录

4.1 预剪枝：边建树边评估，验证集划分是第一道关

预剪枝的思路是建树过程中提前停止：如果当前节点不划分比划分在验证集上表现得更好，就直接把当前节点变成叶子。换句话说，每次划分前都要用验证集做一次「假设检验」。

常见做法是把数据分成三份：训练集、验证集、测试集。训练集建树，验证集决定剪不剪，测试集只用于最终评估。把第 3 章的build_tree加一层判断就是预剪枝骨架：

def pre_prune_build(X_train, y_train, X_val, y_val, attrs): if len(np.unique(y_train)) == 1: return {"label": int(y_train[0])} if len(attrs) == 0: return {"label": int(np.bincount(y_train).argmax())} # 先算出当前节点当作叶子时的验证集精度 leaf_label = int(np.bincount(y_train).argmax()) leaf_acc = evaluate_constant_prediction(y_val, leaf_label) # 再生成完整子树，计算划分后的验证集精度 node = create_node() node["attr"] = choose_best_attr(X_train, y_train, attrs) # 复用第3章打分逻辑 node["children"] = {} for value in np.unique(X_train[:, node["attr"]]): idx = np.where(X_train[:, node["attr"]] == value)[0] node["children"][value] = pre_prune_build( X_train[idx], y_train[idx], X_val, y_val, attrs - {node["attr"]}) split_acc = evaluate_tree(node, X_val, y_val) if split_acc < leaf_acc: return {"label": leaf_label} return node

注意两个细节。第一，验证集精度必须用「多数类填充」的叶子做基线，不能用训练集精度，否则过拟合树几乎总是占优。第二，划分后精度和叶子精度相等时我习惯选择剪枝，也就是split_acc < leaf_acc才保留子树；这个保守偏好能明显降低小数据上的方差。严格版的预剪枝会让验证集样本也随递归进入每一个子节点重新分组，我这里的evaluate_tree是全量验证集走整棵树算精度，是控制篇幅后的简化写法，读者若要复现教材细节，需要把X_val也按分支过滤。

4.2 后剪枝：先生成完整树，再从下往上判断是否回缩

后剪枝不急着在建树时判断，先把整棵树建出来，再自底向上访问内部节点，考察「把这个节点替换成多数类叶子」之后验证集精度是否变差。不差就剪。

def post_prune(node, X_val, y_val): # 叶子节点直接返回 if len(node["children"]) == 0: return node # 深度优先，先处理所有子节点 for key in list(node["children"].keys()): node["children"][key] = post_prune(node["children"][key], X_val, y_val) # 再尝试把当前节点缩成叶子 leaf_label = majority_label(node) # 当前节点样本的多数类 leaf_node = {"label": leaf_label} if evaluate_tree(leaf_node, X_val, y_val) >= evaluate_tree(node, X_val, y_val): return leaf_node return node

这里有个实现陷阱：node是字典，直接node = leaf_node不会改到父节点的 children 引用。我在写这类递归时经常因为这个「重新赋值字典变量」而踩坑，必须改成原地更新才能让剪枝生效：

node.clear() node.update(leaf_node)

后剪枝开销比预剪枝大，因为要先建完整棵树再遍历，但效果通常更好，它是站在全局视角做回缩，不会像预剪枝那样在前几层就短视地切掉后续可能很有用的分支。训练数据只有几十条时，我一般更信后剪枝。

4.3 复现剪枝时的 4 条排查记录

现象一：预剪枝得到的树只有一个根节点，训练集分数低得离谱。原因：验证集划分时没做分层抽样，验证集某一类占比严重偏离训练集，导致「划分后精度」始终低过「不划分精度」。解决：用train_test_split时传stratify=y，保证验证集类别比例和训练集一致。

现象二：剪枝后测试集精度不升反降。原因：拿测试集来指导剪枝，等于把测试集信息泄漏进模型，评估结果虚高，换到新数据就露馅。解决：剪枝比较只用验证集，测试集从开始就锁起来，只允许最后碰一次。

现象三：连续值分支的左右样本总数和父节点对不上。原因：阈值用 Python float 和 np.float64 混用时，精度差异导致边界样本漏切或重复切。解决：阈值统一float(round(mid, 4))，比较符号全程只用同一个<=，不要一半<=一半<。

现象四：后剪枝递归之后整棵树变成了一个叶子，中间过程全部丢失。原因：递归函数里return node但父节点收到的是新对象，没写回 children；或者剪枝条件用了>而不是>=，导致同精度分支被反复保留后又回缩，只留下根。解决：用node.clear(); node.update(leaf_node)原地更新；条件写成>=，允许同精度剪枝。

提示：剪枝比较用的验证集样本量建议不少于 30。样本太少时精度估计的方差太大，剪枝判断基本靠运气。

5. 用 sklearn 复现第四章：决策树分类器实战与参数调优

5.1 数据准备：把西瓜数据集转成 sklearn 能吃的格式

手写代码是为了对齐教材，实际项目里用 sklearn 才是效率最高的。西瓜数据集里很多列是中文文本，DecisionTreeClassifier不接受字符串，必须先做编码。我一般对离散列做标签编码，连续列保持数值：

import pandas as pd from sklearn.preprocessing import LabelEncoder df = pd.read_csv("watermelon.csv") le = LabelEncoder() df["色泽"] = le.fit_transform(df["色泽"]) df["好瓜"] = le.fit_transform(df["好瓜"]) # 变成 0/1 X = df.drop(columns=["编号", "好瓜"]) y = df["好瓜"]

LabelEncoder会把「青绿/乌黑/浅白」变成 0/1/2，这里引入的人为大小关系对决策树没有影响，因为树只做等值比较。编号列必须删掉，否则它会变成信息增益最高的属性，让整棵树退化成查表。这一步是复现第四章时最有仪式感的验证：亲手确认「信息增益偏好取值多属性」真的会发生。

5.2 DecisionTreeClassifier 关键参数与网格搜索

sklearn 的决策树分类器本质是 CART 改良版，支持criterion选gini或entropy，对应第四章的基尼指数和信息增益。max_depth限制最大深度，min_samples_leaf要求叶子节点最少样本数，这两个参数一起用，效果接近「预剪枝 + 后剪枝」的组合。

from sklearn.tree import DecisionTreeClassifier from sklearn.model_selection import GridSearchCV param_grid = { "criterion": ["gini", "entropy"], "max_depth": [2, 3, 4, None], "min_samples_leaf": [1, 2, 3], } grid = GridSearchCV( DecisionTreeClassifier(random_state=0), param_grid, cv=5, scoring="accuracy", ) grid.fit(X, y) print(grid.best_params_)

参数说明：cv=5表示五折交叉验证，每折用训练部分建树、验证部分打分，最后取平均。scoring="accuracy"对西瓜书这种二分类小数据集够用，但类别不平衡时要换成f1或roc_auc。min_samples_leaf从 1 往上加，每加 1 都能明显压低树高度，是缓解过拟合最直接的旋钮。

有一点必须说清楚：sklearn 没有直接复现西瓜书后剪枝的接口。ccp_alpha是最小成本复杂度剪枝，走的是「对总复杂度施加惩罚」的路，和教材里的逐节点验证集回缩不是同一个算法。想严格复现教材的后剪枝，还是要用第 4 章的代码。这个坑经常让新手误以为调了ccp_alpha就等于完成了西瓜书剪枝。

5.3 可视化与特征重要性：让树自己说人话

训练完之后务必把树打印出来，哪怕只是文本格式。export_text比plot_tree更直接：

from sklearn.tree import export_text tree_text = export_text(grid.best_estimator_, feature_names=list(X.columns)) print(tree_text)

输出是缩进形式的规则，每一行对应一个划分条件，叶子节点带类别。我会拿这份文本去和业务核对：任何一个分支条件如果业务方看不懂，说明特征工程没做好，或者模型学到了不该学的东西。

特征重要性也是第四章信息增益的延伸。clf.feature_importances_在 sklearn 里用的是「基尼重要性」——每个特征在所有节点上减少的不纯度总和，再按特征归一化。它在小数据集上波动很大，不要当作精确的因果度量，只能当作「哪些特征参与了主要划分」的线索。如果训练后某个业务上公认重要的特征重要性为 0，优先怀疑数据质量，而不是模型有问题。

注意：决策树对特征共线性不敏感，但特征重要性会被高度相关的特征分摊。两列特征几乎一样时，它们的重要性各自减半，横向对比时很容易误导。

6. 决策树落地前的最后几步：连续值、缺失值和验证习惯

连续值处理在第四章的复现里要格外小心阈值扫描；工程上如果不想手写，完全可以直接交给 sklearn。缺失值也一样，sklearn 的 CART 实现会自动选择最优的缺失值分支方向，不需要预填充；十年前的教材实现一般选择丢弃缺失样本或用众数填充。但真正管用的不是这些选项，而是一个验证习惯：写完手写决策树之后，先在迷你数据集上做「手算对照」。比如用西瓜书中那 17 条样本，手工算根节点熵和信息增益，再跑自己代码里的entropy()和info_gain()，数字能对上再继续。这个习惯帮我少改了很多 bug，尤其是浮点阈值和加权熵分母写错的场景；每次改完剪枝逻辑，我也用这个迷你数据集重跑一遍，确保教材里那张表的结果能复现。

另一个进阶用法是把树导出成规则列表，直接做成业务口诀。遍历树每一条根到叶子的路径，拼成「如果…并且…那么…」的字符串。这个技巧在解释机器学习检测结果时特别有用，别人问你「为什么判成好瓜」，你不需要讲梯度，只需要念一条规则。真正落地的决策树项目，最后交付物往往不是模型文件，而是几页规则。

我自己的习惯是，每次把决策树跑上线前都会问三个问题：训练集和验证集有没有泄漏，连续值阈值记录得是否一致，叶子节点样本数是否够稳。这三个问题对应第三章的浮点坑、第四章的剪枝误判和第五章的参数选择，也是复现第四章时最容易翻车的地方。希望帮到你。

本文还有配套的精品资源，点击获取