简介决策树三种经典算法实现压缩包面向机器学习入门者与算法学习者聚焦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 是绝对主流。对比项ID3C4.5CART划分依据信息增益增益率有惩罚项Gini 系数支持连续特征否需要离散化是阈值二分是阈值二分支持回归任务否否是回归树输出结构多叉树多叉树二叉树缺失值处理无有有代理划分剪枝策略无有悲观剪枝有代价复杂度剪枝对于一个初学者来说别被这张表吓住。你只需要记住一句话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和 GiniCART。这个设计既符合“三种经典算法实现”的标题语境也方便你逐个切换对比。先看数据准备。这里用 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 或 1feature_value是该特征的一个取值。entropy函数里Counter(labels)是为了统计每个类别的样本数p是该类样本占比。然后info_gain先算父节点的熵再遍历当前特征的所有取值按比例累加子节点的熵差值就是信息增益。这个实现有一个初学者常踩的坑split_dataset返回值带着X_mask的行索引但没用np.where收集索引而是直接拿布尔掩码切片。好处是代码短、可读性强坏处是如果你在后面做递归时不小心在原数组上修改了数据掩码的位置就错乱了。所以我的习惯是所有子数据集都用切片后的新数组绝不原地修改X和y。3.3 建树主流程递归结束条件与特征选择有了上面的工具函数建树本身就是一个递归套路。选择当前信息增益最大的特征作为节点然后按该特征的每个取值把数据分成多份对每份递归调用自身。递归必须有三条结束条件缺一条就会死循环或者长出神经病树def build_tree(X, y, feature_names, depth0, max_depth3): 递归建树: 返回一个嵌套字典表示的树结构 # 条件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, keylambda 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_size0.3, random_state42, stratifyy ) # 建立 CART 决策树, 三个关键参数先按经验设置 clf DecisionTreeClassifier( criteriongini, # gini 或 entropy max_depth3, # 先限制深度防过拟合 min_samples_split10, # 内部节点最少样本数 min_samples_leaf5, # 叶子节点最少样本数 random_state42 ) 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})参数说明criteriongini表示用基尼指数建树换成entropy则可以模拟 ID3 的信息增益逻辑但 sklearn 实际上还是二叉树结构和经典 ID3 不完全一样。max_depth3是我在小型数据集上的常用起点min_samples_split10表示一个节点至少有 10 个样本才允许继续分裂min_samples_leaf5强制每个叶子至少覆盖 5 个样本。这组参数组合下来树会很浅、很稳测试集准确率一般在 90% 以上。值得注意的是特征重要性输出能让你一眼看出模型到底靠哪几个特征做判断。在鸢尾花数据集上通常是花瓣长度和花瓣宽度占大头花萼那两根特征基本派不上用场。这份信息在业务项目里很值钱——比如做信贷风控决策树特征重要性排序就是一份可解释性报告。4.3 参数还可以怎么调max_features 和 class_weight 的实战价值很多初学者只会调深度和叶子大小忽略下面这两个参数但它们在实战里的作用非常大。max_features控制每次分裂时最多考虑几个特征。随机森林里每个树分裂时都会限制特征子集但单棵决策树如果也设置max_features0.5或sqrt可以有效降低树之间的相关性后续如果你要往随机森林过渡提前熟悉这个参数很有用。class_weight则专门处理类别不平衡。比如二分类任务中正样本只有 5%负样本 95%决策树很容易学成“永远猜负样本”准确率看着 95% 但其实毫无作用。此时设置class_weightbalancedsklearn 会自动根据类别频率放大少数类的权重让树不会彻底倒向多数类。我在做风控模型时吃过这个亏一上来只看准确率结果坏账用户全被漏掉了。加了这个参数后虽然整体准确率降了一点但召回率从 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_state42但每次重新训练决策树得到的准确率和树结构却不完全一致于是怀疑代码写错了。原因random_state只保证“随机数生成器”的起点一致。决策树里的随机性来源主要是特征分裂时的阈值搜索在多个相同增益的情况下随机选一个、max_features抽取特征子集时用到随机数。如果在train_test_split时没有固定random_state那么每次进模型的训练集本身就不同树结构自然不同。解决把固定随机种子这件事贯彻到底。train_test_split里设random_state42模型里也设random_state42再配合GridSearchCV里的cv参数固定交叉验证的切分方式。做到这三处你的结果才能完全复现。这也是我写任何建模代码的第一个习惯所有随机入口全部锁种子否则后面排错连基线都对不上。5.3 坑三数据量大时手写树慢到怀疑人生现象你把手写代码跑在 10 万行的数据集上一个build_tree递归调用几个小时没跑完CPU 直接被拉满。原因手写代码里每个info_gain都要遍历所有样本去计算熵而且每次递归都会重复计算一遍。在纯 Python 循环下这个复杂度是O(特征数 * 样本数 * 深度)特征一多直接爆炸。解决有两个方案。第一个是换 sklearn让 C 语言优化后的实现去干这活。第二个是如果你确实要手写比如为了交作业那就刻意减少计算量每次选特征时先随机抽样一部分样本来算增益或者把特征排序预计算免得每次从头扫。但说实话这已经偏离学习初衷了不如直接调包。5.4 坑四不知道自己的树长什么样盲目调参全靠猜现象训练完模型后只看准确率数字调参也完全靠蒙——今天max_depth5试一下明天改成 8 试一下来回折腾效果却不稳定。原因决策树是一个可解释性极强的模型它的所有行为都体现在树结构上。你不用可视化去看它就等于闭着眼睛调音——全靠运气。解决把树画出来。sklearn 提供了plot_tree函数我教你的做法在这里复用每次调参后都把树结构导出来看一下特别关注这几个地方——根节点选了什么特征、第二层选了什么特征、有没有某个叶子节点的样本数特别小比如只有 1-2 个。如果叶子样本数普遍很小说明min_samples_leaf太低了如果根节点直接选了一个区分度很差但取值很多的特征说明要检查离散化或者改用 Gini。可视化逼你从“看指标”转变为“看结构”这是决策树调试最核心的思路转变。6. 验证一棵树学没学会可视化结构、交叉验证选参和剪枝的进阶路径想判断一棵决策树到底有没有真的学到规律还是只是在背数据最直接的手段就是把它画出来。sklearn 里可以用plot_tree一键导出树的结构图形每一层节点的分裂特征、阈值、样本分布都会直接显示在图上。按照经验第一眼看根节点选的特征对不对第二眼看每个叶子的样本数是否均衡第三眼看整棵树的深度是否符合你的预期——这三眼看下来你基本能判断出当前参数设置是否合理。可视化的用途之一是用来选参数。你不需要全部依赖网格搜索先凭经验跑一个max_depth3的树看结构然后加深到max_depth5看测试集准确率是升是降——如果升了说明还没学够继续加深如果降了说明开始过拟合。结合交叉验证里的GridSearchCV对max_depth、min_samples_split、min_samples_leaf三个参数做网格搜索就能拿到一组比较稳的超参数。注意交叉验证时固定random_state和cv5否则结果不稳定。另一种剪枝路径需要借助cost_complexity_pruning_path——这是代价复杂度剪枝的 sklearn 实践版。它会输出一串 α 值和对应的树规模你选取一个合适的 α 来剪掉多余的枝节效果往往比单纯限制max_depth更平滑因为它会优先剪掉那些对整体误差贡献最小的枝。不过我给新手的建议是先玩透深度限制和叶子限制等你的树在测试集上表现出明显的过拟合特征训练准确率远高于测试准确率时再试着用代价复杂度剪枝找回泛化能力。做决策树这些年我最大的教训就是“先看树再调参”。数据预处理、特征离散化、超参数搜索这些东西每一个都比“换一个算法”重要得多。最后送大家一个习惯每训练完一棵树先 export 成图片或文本结构看一遍再去看准确率。多花的那一分钟能帮你少踩一整晚的盲目调参。希望帮到你。本文还有配套的精品资源点击获取