简介面向机器学习初学者的决策树分类完整实现包涵盖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.60.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 个全放贷的分支基尼 06 个样本的分支基尼约 0.278加权后约 0.167基尼下降 0.333。基尼指数和熵的排序结果绝大多数时候一致但基尼不用算对数运算快对分类概率的刻画也更直接。这也是 sklearn 默认 criteriongini 的原因。第二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_countsTrue) 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_depthNone, depth0): # 停止条件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 建议至少给一个 510 的值否则数据不纯时树可能长得很深训练集上百分百合对但毫无泛化能力。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_depth3) 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 优化实现默认 criteriongini。它也提供 criterionentropy但这个 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_yTrue) X_train, X_test, y_train, y_test train_test_split( X, y, test_size0.3, random_state42, stratifyy ) clf DecisionTreeClassifier(random_state42) # 默认不剪枝 clf.fit(X_train, y_train) print(训练集准确率:, clf.score(X_train, y_train)) # 接近 1.0 print(测试集准确率:, clf.score(X_test, y_test)) # 明显更低参数说明random_state 固定随机种子保证结果可复现stratifyy 做分层划分让训练和测试集的类别比例一致。不剪枝的树通常在训练集上拿到 1.0 左右测试集掉 510 个点这就是过拟合的直观证据。这个对比请务必跑一次记住这个差距的幅度后面全靠它判断剪枝是否到位。4.2 必调参数组max_depth、min_samples_leaf 与 ccp_alpha 的分工剪枝参数是决策树落地的核心。sklearn 提供两组手段预剪枝在训练时直接限制树的生长后剪枝靠 ccp_alpha 在训练完再修剪。两者不冲突实际项目我一般先用预剪枝压到合理规模再用 ccp_alpha 精调。下面这几个参数是必调的参数作用常见初始值max_depth树的最大深度限制分支层数37min_samples_split内部节点继续分裂所需的最少样本数1020min_samples_leaf叶节点保留的最少样本数510max_features每次分裂考虑的特征数可对抗高基数特征None 或 sqrt(n)ccp_alpha代价复杂度剪枝强度0 表示不剪从剪枝路径曲线选取第一组参数组合如下clf_pruned DecisionTreeClassifier( max_depth4, min_samples_leaf5, random_state42 ) clf_pruned.fit(X_train, y_train) print(剪枝后训练集准确率:, clf_pruned.score(X_train, y_train)) print(剪枝后测试集准确率:, clf_pruned.score(X_test, y_test))逻辑说明max_depth4 把树限制在四层以内每片叶子至少有 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, filledTrue, feature_namesfeature_names, class_names[恶性, 良性], fontsize8, max_depth3 ) plt.show()参数说明filledTrue 按类别上色读图时颜色越纯说明该节点分类越确定max_depth3 限制绘制深度树太深时图会挤成一团先画出前几层结构用于汇报和排查。特征重要性放在同一批代码里输出它告诉你这棵树在靠哪些特征做决策import pandas as pd importance pd.Series( clf_pruned.feature_importances_, indexfeature_names ).sort_values(ascendingFalse) 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_indicatorTrue 可以在填充的同时把缺失掩码也喂给模型。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_weightbalanced让少数类在分裂指标计算中获得更高权重。看指标时不要只看 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_state42) 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_state42, ccp_alphaalpha) 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 看图。希望帮到你。本文还有配套的精品资源点击获取