简介：面向机器学习初学者的决策树分类完整实现包，涵盖ID3、C4.5、CART三种经典算法，并配有Python代码、实验报告与可视化图表，重点解决划分属性选择准则的对比问题。包内共31个文件，主要包含tree.py与treePlotter.py两个核心脚本、测试数据集txt与xlsx表格、决策树实验报告md，以及大量png/jpg格式的结果截图，压缩包整体约1.36MB，文件命名清晰，便于按算法对照查找。三种算法的区别在资源描述中已明确：ID3以信息增益最大为准则，C4.5先筛选高于平均信息增益的属性再取增益率最高者，CART则依据基尼指数选基尼值最小的属性作为划分点，配合dot结构描述文件和可视化图片可直观对照。已有3574人学习下载，适合需要从零理解决策树原理并动手验证的读者，通过运行脚本和实验报告可较快掌握三种算法的实现细节与适用场景。
1. 决策树分类不难，难在弄清 ID3、C4.5、CART 三兄弟的分叉逻辑
决策树分类可能是机器学习里最好跟同事讲清楚的算法——"收入高且有房，就放贷"，本质就是一组 if-else 规则，画出来是一棵从根到叶的树。但真到落地，几乎所有新手都会在同一个地方翻车：ID3、C4.5、CART 三兄弟，名字都熟，真要选一个处理连续特征、缺失值、类别不平衡时，却不知道差别在哪，最后只能靠 sklearn 默认参数硬扛，树长到几十层还不收敛。这篇文章按这三条技术线的演进顺序拆开讲，每条都配可复现的代码和可抄的参数。不管是期末突击还是项目上线，读完你能知道选哪个、参数怎么定、树长歪了往哪排查、什么时候该放弃单棵决策树去换随机森林。
2. 三种算法的分叉逻辑：信息增益、信息增益率与基尼指数的取舍
2.1 ID3 用信息增益选特征，"编号"这类高基数特征就是它的软肋
ID3 的核心只有一个词：信息增益。它借用了信息论里熵的概念。熵衡量一个数据集的混乱程度，所有样本属于同一类时熵为 0，两类各占一半时熵最大，公式是 Ent(D) = -Σ pk·log2(pk)。对分类问题，父节点的熵记作 Ent(D)，按特征 A 的每个取值把样本划成若干子集后，子熵的加权和就是条件熵。信息增益就是父熵减去条件熵：
Gain(D, A) = Ent(D) - Σ(|Dv| / |D|) × Ent(Dv)
举一个可心算的例子。假设 10 个样本里 5 个放贷、5 个拒贷，父节点熵为 1.0。特征 A 把样本切成两堆：第一堆 4 个样本全放贷（熵 0），第二堆 6 个样本里 1 放贷 5 拒贷（熵约 0.65）。那么 Gain = 1.0 - (0.4×0 + 0.6×0.65) ≈ 0.61。特征 B 如果切完之后两堆都还是接近 1:1 的比例，增益就趋近于 0。ID3 在每一层都算所有特征的增益，挑最大的那个往下分。
问题在于信息增益天然偏向取值多的特征。你把"用户编号"当成特征放进数据，每个样本都是唯一值，切完之后每个叶子只有一个样本、熵为 0，增益直接拉满，ID3 第一层就把编号选成了根节点，树的泛化能力约等于零。这是 ID3 在今天几乎不再单独落地的首要原因，也是期末题最爱考的坑。我在实际项目里见过有人把"订单号"放进特征集，跑出来的树第一层就是订单号，测试集准确率比随机猜还差。
2.2 C4.5 用信息增益率与连续特征二分，补上 ID3 的两个命门
C4.5 是 Quinlan 在 1993 年对 ID3 的修正，主要改了两个大问题。
第一个改动是引入增益率。增益率 = 信息增益 / 固有值（split info），固有值描述了特征取值的分散程度：SplitInfo(D, A) = -Σ(|Dv|/|D|)·log2(|Dv|/|D|)，取值越多固有值越大。刚才那个"编号"特征，10 个分支每支 1 个样本，固有值就是 log2(10) ≈ 3.32，增益率被压到约 0.3；而普通特征大约 0.6～0.7，高基数特征自然被压下去。注意一个细节：C4.5 不是直接挑增益率最大的特征，而是先从增益高于平均水平的特征里，再挑增益率最大的那个。原因是某些特征增益率虚高但信息增益本身很低，这种特征切出的分支没有实际区分能力。这个"先过滤再排序"的操作很多讲稿没提，但它是 C4.5 能稳住泛化能力的关键。
第二个改动是支持连续特征。C4.5 先把连续特征的所有取值排序，每两个相邻值的中点作为一个候选切分点，比如收入取值是 [3, 5, 7]，就在 4 和 6 处试切，然后按信息增益选最优阈值。这让连续特征不用预先分箱。它还顺带解决了缺失值：样本在某特征上缺失时，按该特征各取值在当前节点样本中的分布加权，把样本拆到多个分支继续走。这两个能力是 ID3 完全没有的。
2.3 CART 用基尼指数建二叉树，用代价复杂度剪枝收尾
CART 是 Breiman 在 1984 年提出的，和 ID3、C4.5 有两点本质差异。
第一，它用基尼指数而不是信息增益。基尼指数衡量从数据集中随机抽两个样本、类别不一致的概率：Gini(D) = 1 - Σ pk²。还是刚才 5 放贷 5 拒贷的例子，父节点基尼 0.5；按特征 A 划分后，4 个全放贷的分支基尼 0，6 个样本的分支基尼约 0.278，加权后约 0.167，基尼下降 0.333。基尼指数和熵的排序结果绝大多数时候一致，但基尼不用算对数，运算快，对分类概率的刻画也更直接。这也是 sklearn 默认 criterion='gini' 的原因。
第二，CART 强制二叉树。每个节点只做一次二分：连续特征切在某个阈值上，离散特征只判断"A 是否等于某个值"。相比 ID3、C4.5 的多叉结构，二叉树在同样的表达能力下更少出现"某个分支样本极少"的情况，后续剪枝也更好做。CART 自带一套完整的后剪枝机制——代价复杂度剪枝，定义 Rα(T) = R(T) + α×叶子数，用验证集误差最小作为标准，找出最合适的子树。这个概念对应 sklearn 里的 ccp_alpha 参数，在第 6 章专门讲怎么用。
把三条技术线放到一起看，演变逻辑很清晰：ID3 立住了"用熵选特征"的框架，C4.5 修它偏好多取值特征和不能处理连续特征的毛病，CART 则用二叉树和基尼指数把决策树做成了能跑工业级数据的分类器。这也是为什么现在打开 sklearn，默认拿到的是 CART。
3. 从零实现 ID3 决策树分类器：最小可运行代码与停止条件
3.1 熵与信息增益的实现：核心公式先落地
为了让你在看到 sklearn 之前心里不虚，我先把 ID3 的核心逻辑用 Python 实现一遍。这个实现约 50 行，能跑通一个小数据集。信息增益计算、递归建树、停止条件、预测时遇到未见取值的 fallback 都是完整的。唯一的前提是数据已经做过离散化，因为 ID3 本身不支持连续特征。
import numpy as np def entropy(y): """计算类别分布 y 的熵，y 是 0/1 或任意整数标签""" _, counts = np.unique(y, return_counts=True) p = counts / counts.sum() return -np.sum(p * np.log2(p)) def info_gain(X, y, f): """计算特征 f 的信息增益 = 父节点熵 - 子节点加权熵""" parent = entropy(y) weighted_child = 0.0 for v in np.unique(X[:, f]): mask = X[:, f] == v weighted_child += mask.mean() * entropy(y[mask]) return parent - weighted_child逻辑说明：entropy 函数用 np.unique 统计类别计数并转成概率，再按信息熵公式求和。info_gain 遍历特征 f 的所有离散取值，按取值切出 mask 子集，用 mask.mean() 当权重，累加子熵后拿父熵去减。参数说明：X 是二维 numpy 数组，y 是一维标签，f 是特征列下标。这两段代码已经可以直接被后续建树逻辑调用。
3.2 递归建树与三个停止条件：别让树长得比内存还快
建树函数是核心，递归出口必须有三个，少一个都会长出深度几十层、每个叶子只有一个样本的"满树"。
def build_id3(X, y, features, max_depth=None, depth=0): # 停止条件1：节点内样本已纯 if len(set(y)) == 1: return {'leaf': True, 'label': y[0]} # 停止条件2：特征用完或深度封顶 if not features or (max_depth is not None and depth >= max_depth): return {'leaf': True, 'label': np.bincount(y).argmax()} gains = [info_gain(X, y, f) for f in features] best = int(np.argmax(gains)) # 信息增益最大的特征下标 if gains[best] <= 0: # 停止条件3：增益为0，没有再分信息 return {'leaf': True, 'label': np.bincount(y).argmax()} node = { 'feature': features[best], 'leaf': False, 'fallback': np.bincount(y).argmax(), # 预测时遇到未见取值的兜底 'children': {} } rest = [f for f in features if f != features[best]] for v in np.unique(X[:, features[best]]): mask = X[:, features[best]] == v node['children'][v] = build_id3(X[mask], y[mask], rest, max_depth, depth + 1) return node def predict(tree, x): """对单条样本 x 预测，遇到未见取值时回退到当前节点多数类""" if tree['leaf']: return tree['label'] child = tree['children'].get(x[tree['feature']]) return predict(child, x) if child is not None else tree['fallback']逻辑说明：递归函数接收样本、标签、可用特征列表和当前深度。节点内只有一个类别时直接返回叶子；可用特征耗尽或达到 max_depth 时返回当前多数类；若最佳特征的信息增益是 0，说明按这个特征划分得不到任何区分度，也强制返回叶子。node 字典里存了 fallback，也就是当前节点的多数类，用于预测时兜底：如果预测的样本踩到训练集里没见过的取值组合，就返回这个多数类而不是抛异常。
参数说明：features 是特征下标列表，传给 build_id3 时用 list(range(X.shape[1]))。max_depth 建议至少给一个 5～10 的值，否则数据不纯时树可能长得很深，训练集上百分百合对但毫无泛化能力。np.bincount(y).argmax() 在多分类下也能正确返回众数。
3.3 跑通最小数据集并验证树结构
用一个 8 样本的放贷数据验证。前两列分别是收入（0 低、1 高）和有房（0 无、1 有），y 是是否放贷（0 拒、1 放）。
X = np.array([ [0, 0], [1, 0], [0, 1], [1, 1], [0, 0], [1, 0], [0, 1], [1, 1], ]) y = np.array([0, 1, 1, 1, 0, 1, 1, 1]) tree = build_id3(X, y, list(range(X.shape[1])), max_depth=3) print(predict(tree, np.array([0, 0]))) # 期望拒贷 0 print(predict(tree, np.array([1, 0]))) # 期望放贷 1 print(predict(tree, np.array([2, 0]))) # 收入=2 训练集没见过，走 fallback输出是 0、1、1。前两个符合数据规律；第三个样本把收入设为 2，这一步走到的子节点里没有 2 这个分支，于是调用 fallback 返回该子节点的多数类 1。虽然这个预测本身没有太多依据，但至少不崩溃，这就是 fallback 的意义。反推这棵树的形状：根节点收入，低收入分支下按有房再切，无房拒贷、有房放贷；高收入分支直接放贷。
这个实现可以直接跑，但请注意它没有做剪枝、没有支持连续特征、也没有处理缺失值。它的价值是让你看到 ID3 的骨架——熵、增益、递归、兜底。如果把它换到真实项目里，数据量稍大就会过拟合。
3.4 把代码改成 C4.5 或 CART 最少要动哪几行
改成 C4.5 的核心动作是把 info_gain 换成增益率，再在 split 时按中位候选点试切连续特征。增益率按 2.2 节的公式，先在函数里加一个 split_info 计算，再返回 gain / split_info。注意要先把增益低于平均的特征过滤掉，代码上就是计算 gains 后加一个均值过滤，再对剩余特征取 argmax。缺失值的处理需要改成"按概率拆分到多棵子树"，这个改动量比较大，C4.5 的教学实现一般不写。
改成 CART 的核心动作是换分裂指标和改二叉树结构。分裂指标把 info_gain 换成基尼下降，代码三四行就够。结构上 CART 不再对离散特征的每个取值建分支，而是遍历"是否等于 v"做二分；连续特征则是排序后枚举相邻中点做二分。这两处会在节点的 children 键上体现——从按取值 v 索引，变成按条件 True/False 索引。一句话总结：ID3 的骨架不动，换分裂函数和分支方式，就是另外两种算法。
4. 用 scikit-learn 落地 CART：数据准备、剪枝参数与可视化
4.1 训练前必须知道的边界：sklearn 里没有标准 ID3 和 C4.5
进入 sklearn 之前先把边界讲清楚：DecisionTreeClassifier 是 CART 的 Cython 优化实现，默认 criterion='gini'。它也提供 criterion='entropy'，但这个 entropy 是二叉划分下的信息增益，不是标准 ID3 的多叉划分，更不是 C4.5 的增益率和缺失值机制。所以你在 sklearn 里实际上只有 CART 可选。做项目用 CART 完全够，但如果期末题明确要求 ID3 或 C4.5 的流程，请回到第 3 章的自写实现，别拿 sklearn 冒充。
用乳腺癌数据集走一个最小训练流程，这个数据集 30 个特征、569 个样本，规模小但足够看出过拟合现象。
from sklearn.datasets import load_breast_cancer from sklearn.model_selection import train_test_split from sklearn.tree import DecisionTreeClassifier X, y = load_breast_cancer(return_X_y=True) X_train, X_test, y_train, y_test = train_test_split( X, y, test_size=0.3, random_state=42, stratify=y ) clf = DecisionTreeClassifier(random_state=42) # 默认不剪枝 clf.fit(X_train, y_train) print("训练集准确率:", clf.score(X_train, y_train)) # 接近 1.0 print("测试集准确率:", clf.score(X_test, y_test)) # 明显更低参数说明：random_state 固定随机种子，保证结果可复现；stratify=y 做分层划分，让训练和测试集的类别比例一致。不剪枝的树通常在训练集上拿到 1.0 左右，测试集掉 5～10 个点，这就是过拟合的直观证据。这个对比请务必跑一次，记住这个差距的幅度，后面全靠它判断剪枝是否到位。
4.2 必调参数组：max_depth、min_samples_leaf 与 ccp_alpha 的分工
剪枝参数是决策树落地的核心。sklearn 提供两组手段，预剪枝在训练时直接限制树的生长，后剪枝靠 ccp_alpha 在训练完再修剪。两者不冲突，实际项目我一般先用预剪枝压到合理规模，再用 ccp_alpha 精调。下面这几个参数是必调的：
| 参数 | 作用 | 常见初始值 |
|---|---|---|
| max_depth | 树的最大深度，限制分支层数 | 3～7 |
| min_samples_split | 内部节点继续分裂所需的最少样本数 | 10～20 |
| min_samples_leaf | 叶节点保留的最少样本数 | 5～10 |
| max_features | 每次分裂考虑的特征数，可对抗高基数特征 | None 或 sqrt(n) |
| ccp_alpha | 代价复杂度剪枝强度，0 表示不剪 | 从剪枝路径曲线选取 |
第一组参数组合如下：
clf_pruned = DecisionTreeClassifier( max_depth=4, min_samples_leaf=5, random_state=42 ) clf_pruned.fit(X_train, y_train) print("剪枝后训练集准确率:", clf_pruned.score(X_train, y_train)) print("剪枝后测试集准确率:", clf_pruned.score(X_test, y_test))逻辑说明：max_depth=4 把树限制在四层以内，每片叶子至少有 5 个样本，这两条规则直接把树的规模压到可解释的范围内。训练集准确率会比不剪枝低几个点，但测试集通常会回升，这正是你想要的。min_samples_split 我一般和 min_samples_leaf 配合用，前者控制分裂门槛，后者控制叶子的置信度；深层次的树里，叶子样本数少于 10 的分支基本都是过拟合噪声。
提示：这几个参数对数据规模敏感。几百条样本用小值，几万条样本要成倍放大，min_samples_leaf 在数据量大时可以直接设成 50 起步。
4.3 可视化与特征重要性：让树开口说人话
决策树最大的卖点是可以画出来跟人解释。sklearn 自带的 plot_tree 可以替代 graphviz，少装一套系统依赖。
import matplotlib.pyplot as plt from sklearn.tree import plot_tree feature_names = load_breast_cancer().feature_names plt.figure(figsize=(18, 9)) plot_tree( clf_pruned, filled=True, feature_names=feature_names, class_names=['恶性', '良性'], fontsize=8, max_depth=3 ) plt.show()参数说明：filled=True 按类别上色，读图时颜色越纯说明该节点分类越确定；max_depth=3 限制绘制深度，树太深时图会挤成一团，先画出前几层结构用于汇报和排查。
特征重要性放在同一批代码里输出，它告诉你这棵树在靠哪些特征做决策：
import pandas as pd importance = pd.Series( clf_pruned.feature_importances_, index=feature_names ).sort_values(ascending=False) print(importance.head(10))注意 feature_importances_ 的数值是基尼下降量的归一化结果，它不等于特征的因果贡献，只能当排序线索。两个强相关特征会互相分摊重要性，导致排名失真，这在特征筛选时要格外小心。输出前几名特征后，可以检查它们是否与业务直觉一致，不一致通常说明数据里有泄漏或噪声，这也是我从拿到一棵树开始第一件要做的事。
5. 决策树分类器避坑指南：五个让模型翻车的场景与排查思路
5.1 训练集满分测试集稀烂：默认不剪枝是头号元凶
现象：默认参数训练，训练集准确率 1.0，测试集掉到 0.85 甚至更低，树深度二三十层。原因：sklearn 默认不剪枝，树会长到把每个训练样本都单独包进一个叶子为止，训练集当然满分，但泛化能力几乎没有。解决：先看树的深度，用 clf.get_depth() 和 clf.get_n_leaves() 确认规模，然后从第 4.2 节的参数组开始收。我的顺序是先限 max_depth，再提 min_samples_leaf，最后用 ccp_alpha 精调。剪枝没有后悔药，所以动手前先把训练集和测试集的分层划分固定好，别在调参过程中反复换随机种子。
5.2 连续特征切分点被离群值带偏：噪声数据让阈值失真
现象：某个连续特征的切分点打在 98 分位附近，比如"年龄 > 87 才放贷"，明显不符合业务逻辑。原因：CART 对连续特征枚举所有相邻中点做切分，离群点会把最优切分点往极端值方向拉，尤其是样本量少的时候，单个离群值就能制造一个"看起来区分度很高"的分支。解决：训练前先看特征分布，用 pd.Series.describe() 检查分位数。特征里有明显长尾时，我一般做分位数截断，把 1% 和 99% 之外的数值压到边界；或者直接把连续特征按业务含义分箱，减少切分点候选集。决策树虽然不做距离计算，但对噪声数据同样敏感，只是表现在切分点上而不是梯度上。
5.3 数据里有 NaN 直接报错：sklearn 决策树不吃缺失值
现象：fit 时抛 ValueError，提示输入包含 NaN。原因：sklearn 的 DecisionTreeClassifier 不支持缺失值，和 C4.5 的带权重缺失值处理完全是两回事，这是很多从教科书切到 sklearn 的人踩的第一脚坑。解决：用 SimpleImputer 先把缺失值填上，策略选 most_frequent 对类别特征友好，median 对连续特征更稳。如果缺失比例超过 30%，与其靠填充，不如把"是否缺失"本身做成一个二值特征，让树自己学缺失模式的判别力。在特征工程阶段用 add_indicator=True 可以在填充的同时把缺失掩码也喂给模型。
5.4 高基数离散特征霸占根节点：增益偏差不只是 ID3 的事
现象：维度表里的用户 ID、设备号、城市编码这类特征，出现在树的前两层，测试集分数一塌糊涂。原因：信息增益偏好多取值特征，这是 ID3 的著名缺陷；换成基尼指数后，高基数离散特征依然倾向于被选中，因为按它切分很容易产生样本很少但很纯的子节点。解决：最简单粗暴的是直接删掉这类特征；如果它们的业务价值高，可以对低频取值做归并，把出现次数少于阈值（比如 100 次）的取值合并成"other"。还有一个思路是限制 max_features 为一个小于特征总数的值，让每次分裂只在随机子集里挑特征，降低高基数特征被反复选中的概率，这条路再往前走一步就是随机森林。
5.5 类别不平衡导致预测倾向多数类：class_weight 与分层采样
现象：正负样本比 1:9，模型测试集整体准确率 0.9，看起来不错，但少数类的召回率几乎为 0。原因：决策树的叶子多数类决策直接用 np.argmax 算众数，少数类样本少，很容易被多数类淹没。解决：在 train_test_split 时用 stratify 保证划分前后的类别比例一致；训练时设 class_weight='balanced'，让少数类在分裂指标计算中获得更高权重。看指标时不要只看 accuracy，用 classification_report 查少数类的 precision 和 recall。如果调完还是不行，放弃单棵决策树，换随机森林配合 class_weight 或者过采样，树的集成对不平衡的容忍度会高一个台阶。
6. 用代价复杂度剪枝选 ccp_alpha：把剪枝从玄学变成可复现的流程
第 5 章里我用 max_depth、min_samples_leaf 做预剪枝，这是决策树最常用的手段。但这两个参数本质靠人工试：深度 3 还是 5，叶子 5 还是 20，都得来回试。CART 的代价复杂度剪枝（ccp_alpha）是唯一的后剪枝路径，它把"剪多少"变成了一个可以画曲线验证的数值。sklearn 里用 cost_complexity_pruning_path 就能拿到完整的剪枝路径。
from sklearn.tree import DecisionTreeClassifier clf_unpruned = DecisionTreeClassifier(random_state=42) clf_unpruned.fit(X_train, y_train) path = clf_unpruned.cost_complexity_pruning_path(X_train, y_train) ccp_alphas = path.ccp_alphas train_scores, test_scores = [], [] for alpha in ccp_alphas: clf = DecisionTreeClassifier(random_state=42, ccp_alpha=alpha) clf.fit(X_train, y_train) train_scores.append(clf.score(X_train, y_train)) test_scores.append(clf.score(X_test, y_test)) # 画出 alpha 与准确率曲线，取测试分数峰值对应的 alphaccp_alpha 从 0 开始逐步增大，alpha 越大剪得越狠。画出的曲线里测试分数会先升后降，峰值对应的 alpha 就是最佳剪枝强度，这让剪枝从"拍脑袋定深度"变成了"看图取峰值"。两个注意点：alpha 的路径和训练数据划分、随机种子绑定，换一次数据划分要重新跑一遍路径；最优 alpha 附近往往有一段平台，我会在峰值附近选偏大的一侧，宁可多剪一点，换更小的树和更好的可解释性。
我的习惯是：先跑一次不剪枝的树做上限参考，再用剪枝路径曲线挑 alpha，最后确认剪完的树的深度和叶子数。如果剪到十几层测试分数还在涨，说明特征里带了太多噪声，回头做特征筛选；如果剪到三四层分数就崩，说明特征区分度本来就不够，该换模型了。把这个流程固化下来之后，决策树的落地就剩一句话：数据干净、树别太深、alpha 看图。希望帮到你。
本文还有配套的精品资源，点击获取
