决策树三种经典算法：ID3、C4.5、CART原理与Python实现

简介：决策树三种经典算法实现压缩包，面向机器学习入门者与算法学习者，聚焦ID3、C4.5、CART三种决策树算法的原理与实现。其中ID3基于信息增益，C4.5采用信息增益比并支持连续属性与缺失值处理，CART以基尼不纯度分裂且兼顾分类与回归，三者覆盖了决策树发展中的主要技术路线。压缩包共9个文件，以6个py源代码为主，辅以2个pyc编译文件和1个csv数据集（鸢尾花数据），整体仅14KB，轻量易用。目前已有389人浏览学习，适合初学者对照代码逐步推演建树过程。资源内按ID3、C4.5、CART分目录组织，提供cart2.py、c45.py、id3.py等核心脚本，并包含树绘制工具treePlotter.py，可直观呈现分裂结果；随附的iris.csv可直接用于实验，实现从数据导入、模型训练到预测的完整流程，便于读者比较三种算法的差异，并根据数据特点选择合适的分裂策略。

1. 决策树三种经典算法：这包代码到底帮你搞定什么问题

如果你的收藏夹里躺着“决策树 python 实现”这类链接，或者手上正攥着一份头歌平台的决策树作业，那你大概率见过这个标题。决策树三种经典算法实现，指的就是 ID3、C4.5、CART 这三棵“祖师爷级”的树，它们把“要不要出去玩”“鸢尾花属于哪个类别”“收入能不能过万”这类分类问题，拆成一层层“如果特征大于某值就去左边，否则去右边”的 if-else 规则。这份资源的价值不在于代码本身多玄乎，而在于它一次性把三棵树的划分逻辑——信息增益、增益率、Gini 系数——摆在同一个文件里，让你对照着跑一遍，立刻明白书上那几页公式到底在图什么。

这篇笔记适合两类人：一类是被决策树作业逼着交代码的在校生，另一类是刚入机器学习、想把“调包侠”面具摘下来的从业者。我不打算给你复述源码包里的每一行，而是按“先立住理论、再复现最小实现、最后用 sklearn 验证”的顺序，把从数据集到一棵能用的树的完整路径走一遍。看完你能回答三个问题：三种算法差在哪、手写一份要踩哪些坑、以及什么场景下直接调 sklearn 而不是自己造轮子。

2. ID3、C4.5、CART：信息增益、增益率与 Gini 系数的取舍逻辑

2.1 从“熵”说起：为什么划分特征要看信息增益

决策树建树的过程，本质上是一个“不断提问”的过程。每一次提问（也就是选择一个特征作为划分节点），都要回答一个核心问题：这个特征把当前数据分成几拨之后，混乱程度降低了多少？这里的“混乱程度”就是信息熵，公式是Ent(D) = -Σ pk * log2(pk)，pk 是第 k 类样本在集合 D 中的占比。熵越大说明类别越杂，熵为 0 说明大家全是同一类，完美。

ID3 算法就是拿“信息增益”来挑特征的。信息增益 = 父节点的熵 - 按某个特征划分后各子节点熵的加权和。哪个特征让熵降得最多，就选它当当前节点。这个逻辑直觉上没问题，但有个著名缺陷：它偏爱取值特别多的特征。比如你有一个“学号”列，每个样本都不同，按它划分，每个子节点只剩一个样本，熵直接变 0，信息增益拉满——可这棵树等于在背答案，对新数据毫无泛化能力。

所以你会发现，纯手写 ID3 时，对“特征取值个数”这个维度几乎必须做惩罚。否则你跑出来的树可能长得又深又变态，训练集准确率接近 100%，验证集直接拉胯。C4.5 就是冲着这个“毛病”来的：它不直接用信息增益，而是用信息增益率，相当于在信息增益上除以一个“特征自身熵”的惩罚项，专治离散特征取值过多导致的偏好问题。CART 则换了个思路，根本不碰熵，用 Gini 系数（基尼指数）来度量纯度，Gini 越小纯度越高，同时天然支持了连续特征的二分处理，这也是为什么工业级实现里 CART 是绝对主流。

对于一个初学者来说，别被这张表吓住。你只需要记住一句话：ID3 是入门的敲门砖，C4.5 是在它身上打补丁，CART 是真正能上生产环境干活的那一个。实际做项目时，sklearn 里的DecisionTreeClassifier默认用的就是 CART，但绝大多数教程讲原理时还是先从 ID3 的熵开始，因为信息增益的数学直觉最容易建立。

2.2 为什么你用不到“纯手写”：从三算法演化看适用边界

很多人在网上搜“决策树 python 实现”的动机，是课程要求不让你直接调 sklearn，或者头歌平台上有需要填空的实验题。这种情况下你确实需要手写，但手写的目的不是生产，而是理解。我一般建议大家按这样的层次去判断自己到底该写多少代码：

如果目标是应付作业，把 ID3 的建树逻辑跑通就够了，无需做剪枝，甚至无需实现连续特征处理。如果目标是搞懂机器学习，那么建议把 CART 的回归和分类都写一遍——因为 Gini 二分、阈值搜索、代价复杂度剪枝这三件事几乎覆盖了后面随机森林里 80% 的概念。如果目标是做一个能跑数据的工具，直接from sklearn.tree import DecisionTreeClassifier，然后调参max_depth、min_samples_split。

这个判断很重要，因为它决定了你接下来要花多少时间。我自己见过太多新手把整整一周耗在写一个“完美”的手写决策树，结果写到剪枝阶段直接崩溃——因为 CART 的代价复杂度剪枝涉及一串复杂的 α 序列计算，课本上就写了三行公式，但真要用代码实现，你需要把每个内部节点的子误差率都算出来，再找出最小的那个逐层剪。除非你是要吃透原理，否则这投入产出比很差。

2.3 三个必懂参数：max_depth、min_samples_split、min_samples_leaf

不管手写还是调包，这三组参数是所有决策树的“命门”。先看max_depth，它限制树的最大深度。树不设深度限制时，会一路长到每个叶子只剩一个样本，训练集准确率 100%，但测试集一塌糊涂——这就是典型的过拟合。实操里我会把max_depth从 3 往上试，结合交叉验证决定深度，而不是一上来就设 10。

min_samples_split表示一个内部节点至少要有多少个样本才允许继续分裂。它相当于一个“刹车”，样本太少就不许再切了，防止模型学出噪声。经验值是分类任务从 2 开始（sklearn 默认），但数据量大的时候我习惯调到 10-20，降方差效果非常明显。min_samples_leaf则限制叶子节点的最少样本数，它会让树更保守、更适合小数据集或者噪声多的真实业务数据。

这三个参数本质上是“剪枝策略”的廉价替身。C4.5 和 CART 原版都有正式的剪枝算法，但 sklearn 里如果你不想写复杂剪枝逻辑，直接用这几对参数限制树的生长，就够对付 90% 的任务了。后面在第 6 章我会演示怎么用可视化手段验证这些参数到底把树剪成了什么样。

3. 用 Python 手写 ID3：从熵函数到建树主流程的完整落地方案

3.1 先说清楚这份代码能跑成什么样

现在进入能抄作业的环节。我不会把三棵树全部手写一遍给你看——那样篇幅太长，而且 ID3 和 C4.5 的建树框架几乎一样，只是“选特征”那一行的公式不同。我给你的方案是：写一个带“划分准则可插拔”的决策树类，默认用信息增益（ID3），同时留出接口可以切换成增益率（C4.5）和 Gini（CART）。这个设计既符合“三种经典算法实现”的标题语境，也方便你逐个切换对比。

先看数据准备。这里用 sklearn 自带的鸢尾花数据集，只取前两个特征（花萼长度、花萼宽度）——不是不可以取四个特征，而是只取两个特征时树比较浅，打印出来能直观看到每一条规则。实际项目里特征可以更多，代码逻辑不用改，变的是树的形状和深度。

import numpy as np from sklearn.datasets import load_iris data = load_iris() X = data.data[:, :2] # 只要前两个特征，便于可视化 y = data.target # 三分类目标 # 手动把连续特征离散化，方便演示 ID3 的多叉划分 X_discrete = np.zeros_like(X) for col in range(X.shape[1]): # 按中位数分成 0/1 两档，真实项目可以切更多档 median_val = np.median(X[:, col]) X_discrete[:, col] = (X[:, col] > median_val).astype(int) print(X_discrete.shape, set(y)) # 输出示例: (150, 2) {0, 1, 2}

逻辑说明：连续特征做中位数离散化是 ID3 的常见妥协方案——因为 ID3 本身不支持连续值。set(y)用来确认是三分类任务。后面 C4.5 和 CART 的实现里，我会把这份离散化数据直接复用，让三棵树的对比建立在同一份输入上。

3.2 熵与信息增益的计算函数

接下来写本轮的核心工具函数：计算熵、按特征划分数据集、计算信息增益。这三个函数是 ID3 的心脏，也是你后面排查“树为什么长歪”的第一现场。

from collections import Counter import math def entropy(labels): """计算信息熵: Ent(D) = -sum(pk * log2(pk))""" total = len(labels) if total == 0: return 0 counts = Counter(labels) ent = 0.0 for cnt in counts.values(): p = cnt / total ent -= p * math.log2(p) return ent def split_dataset(X, y, feature_idx, feature_value): """按特征取值划分子数据集: 返回当前分支下的样本""" mask = X[:, feature_idx] == feature_value return X[mask], y[mask] def info_gain(X, y, feature_idx): """计算按某个特征划分后的信息增益""" base_ent = entropy(y) values = set(X[:, feature_idx]) weighted_ent = 0.0 for v in values: _, y_sub = split_dataset(X, y, feature_idx, v) weighted_ent += (len(y_sub) / len(y)) * entropy(y_sub) return base_ent - weighted_ent

参数说明：feature_idx是你要考察的特征列下标（0 或 1），feature_value是该特征的一个取值。entropy函数里Counter(labels)是为了统计每个类别的样本数，p是该类样本占比。然后info_gain先算父节点的熵，再遍历当前特征的所有取值，按比例累加子节点的熵，差值就是信息增益。

这个实现有一个初学者常踩的坑：split_dataset返回值带着X_mask的行索引，但没用np.where收集索引，而是直接拿布尔掩码切片。好处是代码短、可读性强；坏处是如果你在后面做递归时不小心在原数组上修改了数据，掩码的位置就错乱了。所以我的习惯是：所有子数据集都用切片后的新数组，绝不原地修改X和y。

3.3 建树主流程：递归结束条件与特征选择

有了上面的工具函数，建树本身就是一个递归套路。选择当前信息增益最大的特征作为节点，然后按该特征的每个取值把数据分成多份，对每份递归调用自身。递归必须有三条结束条件，缺一条就会死循环或者长出神经病树：

def build_tree(X, y, feature_names, depth=0, max_depth=3): """递归建树: 返回一个嵌套字典表示的树结构""" # 条件1: 当前子集类别全部一致, 无需再分 if len(set(y)) == 1: return {'leaf': True, 'class': int(y[0])} # 条件2: 深度达到限制, 强行停止 if depth >= max_depth: # 取当前子集中出现最多的类别作为叶子结果 majority_class = Counter(y).most_common(1)[0][0] return {'leaf': True, 'class': int(majority_class)} # 条件3: 特征全部用完了或样本为空, 也按多数类兜底 if X.shape[1] == 0 or len(y) == 0: majority_class = Counter(y).most_common(1)[0][0] if len(y) > 0 else -1 return {'leaf': True, 'class': int(majority_class)} # 选信息增益最大的特征 gains = [(idx, info_gain(X, y, idx)) for idx in range(X.shape[1])] best_idx = max(gains, key=lambda t: t[1])[0] best_feature = feature_names[best_idx] # 按该特征取值分叉 subtree = {'leaf': False, 'feature': best_feature, 'depth': depth, 'branches': {}} for v in set(X[:, best_idx]): X_sub, y_sub = split_dataset(X, y, best_idx, v) if len(y_sub) == 0: # 该取值下没有样本, 用父节点的多数类兜底 majority_class = Counter(y).most_common(1)[0][0] subtree['branches'][str(v)] = {'leaf': True, 'class': int(majority_class)} else: subtree['branches'][str(v)] = build_tree(X_sub, y_sub, feature_names, depth + 1, max_depth) return subtree

逻辑说明：每次递归进入build_tree后，先检查前面提到的三条结束条件，其中第一条最重要——len(set(y)) == 1，意思是当前子集里所有样本类别都一样，再分就是过度拟合。第二条max_depth是为了防深树，第三条用于应付“特征用完还没分干净”的窘境。在递归分支构建时，如果某个特征取值下没有样本（比如测试集中出现了训练集没见过的取值），就直接用父节点的多数类做叶子，这在代码里也叫“兜底策略”。

一个重要的细节是：gains = [(idx, info_gain(X, y, idx)) for idx in range(X.shape[1])]，每次递归都把所有特征重新算一遍信息增益。这在 ID3 里没问题，但在真实项目里如果特征有几十个，这个暴力枚举会让你等到怀疑人生。这也是为什么我们在第 4 章要让位于 sklearn——它的 CART 实现有优化过的特征选择底子，速度完全不在一个量级。

3.4 写一个预测函数，确认树真的能工作

建完树只能算完成一半，还得能预测。预测就是顺着树往下走：到非叶子节点看特征取值，然后跳转到对应分支，直到遇见leaf: True，返回类别。

def predict_one(tree, sample): """单样本预测: 从根节点一路落到叶子""" if tree.get('leaf'): return tree['class'] feature_idx = list(tree['branches'].keys())[0] # 实际应传特征名映射, 简化演示 # 真实场景这里需要根据 tree['feature'] 定位列下标 return None # 因为在字典树里直接存的是特征名而不是下标, 我们这里补一个辅助查找 def feature_index(feature_name, feature_names): return feature_names.index(feature_name) def predict_one_fixed(tree, sample, feature_names): """修正版预测: 通过 feature_names 定位特征列位置""" if tree.get('leaf'): return tree['class'] fname = tree['feature'] idx = feature_index(fname, feature_names) val = sample[idx] branch = str(int(val)) # 注意这里要和建树时的 str(v) 一致 if branch in tree['branches']: return predict_one_fixed(tree['branches'][branch], sample, feature_names) else: # 该取值未见过, 返回这个节点下多数类的近似值 # 简单做法: 递归进入第一个分支 first_branch = list(tree['branches'].values())[0] return predict_one_fixed(first_branch, sample, feature_names)

这段代码里的str(int(val))是个隐藏的坑：如果特征被离散化成 float，比如 0.0 和 1.0，那么建树时str(v)会产生'0.0'和'1.0'，而预测时如果直接str(val)也一致的话没问题。但如果你在别处把特征类型转成 int（比如astype(int)），建树时是'0'，预测时是'0.0'，那就匹配不上，代码会掉进兜底分支——这种现象我在帮别人排错时见过好几次。解决方案只有一个：规范化离散化流程，建树和预测用同一套预处理管线。

4. 用 sklearn 落地 CART：为什么实战里你该直接调包而不是手写

4.1 手写和调包的差距到底在哪

当你把手写 ID3 跑通，理解了递归和熵之后，一个很自然的疑问是：那我现在做项目，是不是也应该自己写一棵树？我的答案是：不要，除非你是在交作业。原因有三：性能、编码细节和生产功能。性能方面，sklearn 的 CART 实现用的是编译优化的底层代码，支持特征预排序，在真实规模的数据集上比纯 Python 递归快几十倍。编码细节更不用提——手写代码要考虑缺失值传播、类别特征处理、并行训练、代价复杂度剪枝。这些资源包里大概率没有，即便有，代码质量也千差万别。

生产功能方面，sklearn 的DecisionTreeClassifier内置了feature_importances_、predict_proba、apply等方法，配合GridSearchCV可以做系统化调参。你自己写一棵树想要这些能力，等于把 sklearn 源码再重写一遍——纯纯的重复造轮子。这也正是很多人搜到“决策树 python 实现”后，最后反而回去调 sklearn 的原因：手写代码只解决“懂原理”，不解决“干活”。

4.2 直接跑通的最小代码：训练、评估、特征重要性

用 sklearn 训练一棵决策树，数据不用离散化——CART 天然支持连续特征，它会自动遍历所有可能的阈值来找最优切分点。下面是完整的最小代码，可以直接跑。

import numpy as np from sklearn.datasets import load_iris from sklearn.model_selection import train_test_split from sklearn.tree import DecisionTreeClassifier from sklearn.metrics import accuracy_score, classification_report data = load_iris() X = data.data y = data.target # 切分训练集和测试集, 固定随机种子保证结果可复现 X_train, X_test, y_train, y_test = train_test_split( X, y, test_size=0.3, random_state=42, stratify=y ) # 建立 CART 决策树, 三个关键参数先按经验设置 clf = DecisionTreeClassifier( criterion='gini', # gini 或 entropy max_depth=3, # 先限制深度防过拟合 min_samples_split=10, # 内部节点最少样本数 min_samples_leaf=5, # 叶子节点最少样本数 random_state=42 ) clf.fit(X_train, y_train) y_pred = clf.predict(X_test) print("测试集准确率:", accuracy_score(y_test, y_pred)) print("\n分类报告:\n", classification_report(y_test, y_pred)) # 特征重要性排序 for name, imp in zip(data.feature_names, clf.feature_importances_): print(f"{name}: {imp:.4f}")

参数说明：criterion='gini'表示用基尼指数建树，换成'entropy''则可以模拟 ID3 的信息增益逻辑（但 sklearn 实际上还是二叉树结构，和经典 ID3 不完全一样）。max_depth=3是我在小型数据集上的常用起点，min_samples_split=10表示一个节点至少有 10 个样本才允许继续分裂，min_samples_leaf=5强制每个叶子至少覆盖 5 个样本。这组参数组合下来，树会很浅、很稳，测试集准确率一般在 90% 以上。

值得注意的是，特征重要性输出能让你一眼看出模型到底靠哪几个特征做判断。在鸢尾花数据集上，通常是花瓣长度和花瓣宽度占大头，花萼那两根特征基本派不上用场。这份信息在业务项目里很值钱——比如做信贷风控决策树，特征重要性排序就是一份可解释性报告。

4.3 参数还可以怎么调：max_features 和 class_weight 的实战价值

很多初学者只会调深度和叶子大小，忽略下面这两个参数，但它们在实战里的作用非常大。max_features控制每次分裂时最多考虑几个特征。随机森林里每个树分裂时都会限制特征子集，但单棵决策树如果也设置max_features=0.5或sqrt，可以有效降低树之间的相关性，后续如果你要往随机森林过渡，提前熟悉这个参数很有用。

class_weight则专门处理类别不平衡。比如二分类任务中正样本只有 5%，负样本 95%，决策树很容易学成“永远猜负样本”，准确率看着 95% 但其实毫无作用。此时设置class_weight='balanced'，sklearn 会自动根据类别频率放大少数类的权重，让树不会彻底倒向多数类。我在做风控模型时吃过这个亏，一上来只看准确率，结果坏账用户全被漏掉了。加了这个参数后，虽然整体准确率降了一点，但召回率从 20% 提到了 60% 以上，业务上才算真正能用。

5. 决策树 Python 实现避坑指南：特征离散化、超参数与过拟合的四个现场

5.1 坑一：手写 ID3 时把连续特征直接丢进去，树变成了“一列一个分支”

现象：你用网上找的代码跑真实数据，发现树的结构奇怪到爆炸——某个特征有三十多个不同取值，每个取值都拉出一个分支，整棵树宽度惊人，打印出来根本没法看。训练准确率极高，但测试准确率惨不忍睹。

原因：经典 ID3 只支持离散特征，但很多入门教程没有前置处理步骤，直接把连续的浮点特征喂给了set(X[:, feature_idx])去枚举取值。于是每个唯一值都成一个分支，模型记住了训练集里每一个具体的数值，彻底过拟合。

解决：在做 ID3 之前，先做离散化。常见做法是按中位数二值化（像我第 3 章演示那样），或者按分位数切成 3-5 档。千万别贪多，档位越多越容易过拟合。如果嫌麻烦，直接换用 C4.5 的思路——连续特征在递归里实时搜索最佳切分阈值，但对新手来说，先学会分箱更稳。

5.2 坑二：sklearn 里设了random_state但树每次结果还是不一样

现象：你在 sklearn 里已经设置了random_state=42，但每次重新训练决策树，得到的准确率和树结构却不完全一致，于是怀疑代码写错了。

原因：random_state只保证“随机数生成器”的起点一致。决策树里的随机性来源主要是：特征分裂时的阈值搜索在多个相同增益的情况下随机选一个、max_features抽取特征子集时用到随机数。如果在train_test_split时没有固定random_state，那么每次进模型的训练集本身就不同，树结构自然不同。

解决：把固定随机种子这件事贯彻到底。train_test_split里设random_state=42，模型里也设random_state=42，再配合GridSearchCV里的cv参数固定交叉验证的切分方式。做到这三处，你的结果才能完全复现。这也是我写任何建模代码的第一个习惯：所有随机入口全部锁种子，否则后面排错连基线都对不上。

5.3 坑三：数据量大时手写树慢到怀疑人生

现象：你把手写代码跑在 10 万行的数据集上，一个build_tree递归调用几个小时没跑完，CPU 直接被拉满。

原因：手写代码里每个info_gain都要遍历所有样本去计算熵，而且每次递归都会重复计算一遍。在纯 Python 循环下，这个复杂度是O(特征数 * 样本数 * 深度)，特征一多直接爆炸。

解决：有两个方案。第一个是换 sklearn，让 C 语言优化后的实现去干这活。第二个是如果你确实要手写（比如为了交作业），那就刻意减少计算量：每次选特征时，先随机抽样一部分样本来算增益；或者把特征排序预计算，免得每次从头扫。但说实话，这已经偏离学习初衷了，不如直接调包。

5.4 坑四：不知道自己的树长什么样，盲目调参全靠猜

现象：训练完模型后只看准确率数字，调参也完全靠蒙——今天max_depth=5试一下，明天改成 8 试一下，来回折腾，效果却不稳定。

原因：决策树是一个可解释性极强的模型，它的所有行为都体现在树结构上。你不用可视化去看它，就等于闭着眼睛调音——全靠运气。

解决：把树画出来。sklearn 提供了plot_tree函数，我教你的做法在这里复用：每次调参后都把树结构导出来看一下，特别关注这几个地方——根节点选了什么特征、第二层选了什么特征、有没有某个叶子节点的样本数特别小（比如只有 1-2 个）。如果叶子样本数普遍很小，说明min_samples_leaf太低了；如果根节点直接选了一个区分度很差但取值很多的特征，说明要检查离散化或者改用 Gini。可视化逼你从“看指标”转变为“看结构”，这是决策树调试最核心的思路转变。

6. 验证一棵树学没学会：可视化结构、交叉验证选参和剪枝的进阶路径

想判断一棵决策树到底有没有真的学到规律，还是只是在背数据，最直接的手段就是把它画出来。sklearn 里可以用plot_tree一键导出树的结构图形，每一层节点的分裂特征、阈值、样本分布都会直接显示在图上。按照经验，第一眼看根节点选的特征对不对，第二眼看每个叶子的样本数是否均衡，第三眼看整棵树的深度是否符合你的预期——这三眼看下来，你基本能判断出当前参数设置是否合理。

可视化的用途之一是用来选参数。你不需要全部依赖网格搜索，先凭经验跑一个max_depth=3的树，看结构；然后加深到max_depth=5，看测试集准确率是升是降——如果升了说明还没学够，继续加深；如果降了说明开始过拟合。结合交叉验证里的GridSearchCV对max_depth、min_samples_split、min_samples_leaf三个参数做网格搜索，就能拿到一组比较稳的超参数。注意交叉验证时固定random_state和cv=5，否则结果不稳定。

另一种剪枝路径需要借助cost_complexity_pruning_path——这是代价复杂度剪枝的 sklearn 实践版。它会输出一串 α 值和对应的树规模，你选取一个合适的 α 来剪掉多余的枝节，效果往往比单纯限制max_depth更平滑，因为它会优先剪掉那些对整体误差贡献最小的枝。不过我给新手的建议是：先玩透深度限制和叶子限制，等你的树在测试集上表现出明显的过拟合特征（训练准确率远高于测试准确率）时，再试着用代价复杂度剪枝找回泛化能力。

做决策树这些年，我最大的教训就是“先看树，再调参”。数据预处理、特征离散化、超参数搜索，这些东西每一个都比“换一个算法”重要得多。最后送大家一个习惯：每训练完一棵树，先 export 成图片或文本结构看一遍，再去看准确率。多花的那一分钟，能帮你少踩一整晚的盲目调参。希望帮到你。

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