简介这份压缩包面向机器学习入门与数据挖掘学习者集中演示决策树三种经典算法——ID3、C4.5、CART在Python中的实现方式并以鸢尾花数据集iris.csv作为测试样例覆盖从数据导入、模型训练到预测评估的完整流程。包内共9个文件以6个py源码文件为主另有2个pyc编译文件与1个csv数据文件便于直接运行或对照学习整体压缩包仅14KB结构紧凑、适合快速上手。已有389人学习下载。通过对比信息增益、信息增益比与基尼不纯度在树构建中的实际应用读者可清晰理解各算法的分裂标准、优缺点及适用场景同时掌握决策树的可视化与绘图方法为后续在scikit-learn等库中调参优化打下基础。1. 拿到决策树经典算法实现压缩包后先把三棵树的“选特征”逻辑想清楚你下载了那个“决策树三种经典算法实现.rar”解压后大概率是 ID3、C4.5、CART 三份 Python 代码外加一个数据集。不少同学的第一步就卡住了直接python main.py报错、中文路径乱码、或者三份代码跑出来的结果对不上。这不是你操作有问题而是这三棵树在“选特征”这件事上用的数学准则完全不同对数据格式的要求也不一样。这篇笔记就把三份代码从头到尾拆开——三个算法到底差在哪、怎么用 Python 逐个实现、参数怎么调以及最常见的五个翻车现场怎么修。适合正在做决策树实验、准备面试手撕树模型、或者想把机器学习入门算法真正落到本地跑通的人。2. ID3、C4.5、CART 都选特征但选法完全不同先把三个准则吃透2.1 信息熵是决策树分裂的“度量尺”先算一遍再谈优化决策树的本质是一连串 if-else 规则关键问题是先对哪个特征做判断答案不是拍脑袋而是找一个数学指标来度量“分裂前后数据纯度变化”。这个指标的基础就是信息熵。信息熵衡量一组数据的混乱程度。如果一个样本集合里全是一个类别熵是 0如果两类各占一半熵是 1以 2 为底。公式是import math from collections import Counter def entropy(y): 计算类别标签的信息熵 参数 y: 一维列表每个元素是样本的类别标签 返回 熵值取值范围 [0, log2(类别数)] total len(y) if total 0: return 0 counts Counter(y) return -sum((c / total) * math.log2(c / total) for c in counts.values())这段代码先统计每个类别的数量再套熵的定义。Counter是 Python 标准库里的计数工具比手动维护字典快得多。注意边界当total为 0 时直接返回 0否则math.log2(0)会报错。配合条件熵才能构成“分裂前后”的对比。所谓条件熵就是按某个特征的取值把数据切开后各个子集熵的加权平均。权重是子集样本数占总样本数的比例。决策树的每一次分裂都是在找一个特征让条件熵最小化。2.2 信息增益ID3与信息增益率C4.5从“减多少”到“减得划不划算”ID3 用的特征选择准则叫信息增益公式简单粗暴信息增益 分裂前的熵 − 分裂后的条件熵直觉是这个特征把数据分成几堆之后混乱度降了多少。降得越多说明这个特征的分辨能力越强。但纯找“降得最多”的特征会出问题分类变量的取值越多数据被切得越碎每个子集就越纯信息增益天然就大。举个极端例子如果给每个样本编一个唯一的 ID 号特征按这个 ID 分裂后每个子集只有一个样本条件熵为 0信息增益直接拉满。但这样的树没有任何泛化能力。C4.5 的改进是把信息增益除以一个“固有值”惩罚项得到信息增益率def intrinsic_value(y, groups): 计算固有值按特征取值分裂后子集比例本身带来的熵 参数 y: 原始标签列表 groups: 按特征取值切分后的子集索引列表 total len(y) return -sum((len(g) / total) * math.log2(len(g) / total) for g in groups)这个值衡量的是“特征本身有多少个分支”。取值多的特征固有值大信息增益被削弱的程度也大。增益率高的特征才是“每股出又少、收益又高”的优质特征。2.3 基尼系数CART不碰对数运算的工程派选择CART 树分类与回归树选特征用的不是熵而是基尼系数。基尼系数同样衡量纯度但完全不需要算对数只需要算每个类别占比的平方def gini(y): 计算基尼系数 返回 基尼值越接近 0 说明越纯 total len(y) if total 0: return 0 counts Counter(y) return 1 - sum((c / total) ** 2 for c in counts.values())二分类场景下基尼系数和信息熵的对比如下当类别占比从 0 到 0.5基尼从 0 涨到 0.5熵从 0 涨到 1两个指标的趋势完全一致但基尼计算只有乘法和加法没有log2在大规模数据上的速度优势非常明显。CART 还有一个硬性特点它强制二叉树特征取值再多也只会切一次切出一个“左子集”和一个“右子集”。这个设计让 CART 天然避免了多叉树那种“切太碎”的问题也是 sklearn 里DecisionTreeClassifier的底层算法。2.4 三种算法选型对比写代码前先决定用哪把尺子算法特征选择准则树结构连续特征剪枝策略实际场景ID3信息增益多叉树不支持无容易过拟合入门学习、手写实现C4.5信息增益率多叉树支持离散化有悲观剪枝教学与经典研究CART基尼系数二叉树支持阈值二分有代价复杂度剪枝工程落地、sklearn 默认选型逻辑很直接你要是只做课程实验ID3 代码最少熵的计算逻辑最好理解如果手头数据有一堆连续特征比如鸢尾花的四个测量值直接用 CART离散化逻辑最少如果你在写论文或者做理论对比C4.5 的增益率要单独实现一版。下面第 3 章的代码就以 CART 风格的二叉树为骨架把三种打分函数都做进去这样你一份代码就能对比三种准则。3. Python 实现三棵决策树从公共地基到端到端跑通3.1 搭公共地基节点类、熵计算与数据切分函数三棵树的代码有大量公共部分先把这些基础件写出来。这里统一用二叉分裂结构连续特征按“阈值二分”处理离散特征也可以转换成“取值是否等于某个值”的二分条件。这样三种准则的分裂逻辑是同一套只需要替换打分函数。class Node: 树节点 feature: 分裂用的特征索引 threshold: 分裂阈值连续特征取数值离散特征取某个取值 value: 叶节点的预测类别 left: 左子树 right: 右子树 def __init__(self, featureNone, thresholdNone, valueNone, leftNone, rightNone): self.feature feature self.threshold threshold self.value value self.left left self.right right def split_data(X, y, f, t): 按特征 f 的阈值 t 把数据切成左右两部分 规则X[i][f] t 进左否则进右 left_idx, right_idx [], [] for i in range(len(X)): if X[i][f] t: left_idx.append(i) else: right_idx.append(i) return left_idx, right_idx这个拆分的核心规则是“左闭右开”小于等于阈值的进左边。对于连续特征来说阈值的备选集合是“排序后相邻两个取值的中间点”比如[1.2, 1.8, 2.5]会生成[1.5, 2.15]两个候选切割点。对于离散特征阈值就是特征本身的取值判断“是否等于”就是通过把等于阈值的放左边其余放右边。3.2 三种特征选择打分函数的完整实现与参数说明接下来是三个算法最关键的分裂准则实现。公共接口是输入特征矩阵X、标签y、特征索引f以及候选阈值t输出该切分方式下的“得分”。ID3 和 C4.5 是得分越高越好CART 是得分越低越好最后统一取最优。def score_gain(X, y, f, t): ID3 信息增益打分 left_idx, right_idx split_data(X, y, f, t) y_left, y_right [y[i] for i in left_idx], [y[i] for i in right_idx] w_left, w_right len(y_left) / len(y), len(y_right) / len(y) cond_entropy w_left * entropy(y_left) w_right * entropy(y_right) return entropy(y) - cond_entropy def score_gain_ratio(X, y, f, t): C4.5 信息增益率打分 left_idx, right_idx split_data(X, y, f, t) y_left, y_right [y[i] for i in left_idx], [y[i] for i in right_idx] w_left, w_right len(y_left) / len(y), len(y_right) / len(y) cond_entropy w_left * entropy(y_left) w_right * entropy(y_right) gain entropy(y) - cond_entropy iv - (w_left * math.log2(w_left) w_right * math.log2(w_right)) if iv 0: return 0 return gain / iv def score_gini(X, y, f, t): CART 基尼系数打分取加权基尼值越低越纯 left_idx, right_idx split_data(X, y, f, t) y_left, y_right [y[i] for i in left_idx], [y[i] for i in right_idx] w_left, w_right len(y_left) / len(y), len(y_right) / len(y) return w_left * gini(y_left) w_right * gini(y_right)这里有几个参数细节值得说清楚。第一iv 0的兜底必须加当特征把数据全切到一边时固有值是 0除数为零在 Python 里直接抛ZeroDivisionError。第二三个函数的输入输出格式完全一致最后一个统一选择特征的函数时只需要把打分函数作为参数传进去。第三基尼系数这里算的是分裂后的加权基尼不是求差值所以后面选特征时要用min而不是max这是最容易写反的地方。统一选择最优特征和阈值的函数def best_split(X, y, criteriongini): 遍历所有特征和候选阈值返回最优 (特征索引, 阈值) criterion: gain 对应 ID3gain_ratio 对应 C4.5gini 对应 CART score_func {gain: score_gain, gain_ratio: score_gain_ratio, gini: score_gini}[criterion] best_f, best_t, best_score None, None, None n_samples, n_features X.shape for f in range(n_features): values sorted(set(X[:, f])) thresholds values if len(values) 10 else [ (values[i] values[i 1]) / 2 for i in range(len(values) - 1) ] for t in thresholds: sc score_func(X, y, f, t) if criterion gini: if best_score is None or sc best_score: best_f, best_t, best_score f, t, sc else: if best_score is None or sc best_score: best_f, best_t, best_score f, t, sc return best_f, best_tsorted(set(X[:, f]))是对特征取值去重排序得到候选分裂点。当特征取值超过 10 个时用相邻值中点作为阈值减少计算量这是训练速度优化的一个常见技巧。3.3 递归建树与剪枝参数max_depth 和 min_samples_leaf 怎么定打分函数有了树的骨架就是一路递归选最优分裂 → 切数据 → 左右子树分别继续。递归必须有三条终止条件少一条都会栈溢出def build_tree(X, y, depth0, max_depth5, min_samples_leaf2, criteriongini): 递归构建决策树 max_depth: 最大深度None 表示不限强烈不建议 min_samples_leaf: 叶节点最少样本数防止子树过碎 criterion: 分裂准则 n_samples len(y) n_classes len(set(y)) # 终止条件 1类别全一致不需要再切 if n_classes 1: return Node(valuey[0]) # 终止条件 2达到最大深度 if max_depth is not None and depth max_depth: return Node(valueCounter(y).most_common(1)[0][0]) # 终止条件 3当前节点样本太少 if n_samples min_samples_leaf * 2: return Node(valueCounter(y).most_common(1)[0][0]) f, t best_split(X, y, criterion) if f is None: return Node(valueCounter(y).most_common(1)[0][0]) left_idx, right_idx split_data(X, y, f, t) left_node build_tree(X[left_idx], y[left_idx], depth 1, max_depth, min_samples_leaf, criterion) right_node build_tree(X[right_idx], y[right_idx], depth 1, max_depth, min_samples_leaf, criterion) return Node(featuref, thresholdt, leftleft_node, rightright_node)三个终止条件是避坑关键。n_classes 1是纯度达标depth max_depth是预剪枝n_samples min_samples_leaf * 2是因为一个节点至少要能分裂成两个不小于min_samples_leaf的子节点。Counter(y).most_common(1)[0][0]取的是当前节点里出现次数最多的类别作为叶节点的预测值。剪枝参数的经验值max_depth在鸢尾花这类小数据集上设 3 到 5 就够设大了训练集准确率会接近 100%测试集反而掉min_samples_leaf设 2 到 5 可以减少噪声样本对叶子节点的影响。如果数据量上万max_depth可以放到 10 到 15但要配合下一章的误差验证步骤一起调。3.4 用鸢尾花数据端到端跑通三棵树一把梭把上面的代码拼起来用 sklearn 自带的鸢尾花数据集验证。注意这里只借用load_iris加载数据树本身完全是自己实现的from sklearn.datasets import load_iris from sklearn.model_selection import train_test_split iris load_iris() X, y iris.data, iris.target X_train, X_test, y_train, y_test train_test_split( X, y, test_size0.3, random_state42, stratifyy ) for criterion in [gain, gain_ratio, gini]: tree build_tree(X_train, y_train, depth0, max_depth4, min_samples_leaf2, criterioncriterion) def predict_one(node, sample): while node.value is None: if sample[node.feature] node.threshold: node node.left else: node node.right return node.value train_acc sum(predict_one(tree, x) y for x, y in zip(X_train, y_train)) / len(y_train) test_acc sum(predict_one(tree, x) y for x, y in zip(X_test, y_test)) / len(y_test) print(f{criterion:8s} train_acc{train_acc:.2f} test_acc{test_acc:.2f})stratifyy必须带上它保证划分后训练集和测试集里三个类别的比例和原始数据一致避免某个类别在测试集里一个样本都没有。random_state42固定随机种子让结果可复现——没有这一步你每次跑出来的准确率都不一样后面调参完全没法对比。predict_one的循环判定条件是node.value is None说明还没到叶节点。每到一个节点拿当前样本的特征值和阈值比较决定走左还是走右。这份代码在鸢尾花上的典型结果是三种准则测试集准确率都在 0.9 左右ID3 略低、CART 略高但差距不大——小数据集上准则的差异体现得没那么明显真正拉开差距的是第 4 章要讲的几个工程坑。4. 决策树手写代码避坑手册五个翻车现场与修法4.1 解压后运行报 UnicodeDecodeError文件编码与路径的锅现象双击运行.py文件报错UnicodeDecodeError: gbk codec cant decode byte或者读取 csv 时乱码。原因Windows 下 Python 默认编码是 GBK而压缩包里的代码和数据文件大多是 UTF-8 编码尤其是从网上下载的 rar 包文件头还经常混入 BOM 标记。解决在代码文件第一行或读取文件时显式指定编码。import pandas as pd # 读取数据时强制走 UTF-8注意参数是 encoding 不是 enconding df pd.read_csv(iris.csv, encodingutf-8)如果你的 csv 是 GBK 编码的反过来把encodingutf-8改成encodinggbk。还有一条血泪经验rar 解压后如果文件名是乱码不要直接改扩展名先用系统自带的解压工具重新解压一次并在解压设置里选“保留文件名编码”。4.2 连续特征当离散特征枚举信息增益虚高现象用 ID3 跑鸢尾花数据训练准确率很高但看一看分裂结果发现第一刀永远切在某个特征的某个极小范围上树的结构非常诡异。原因很多入门版 ID3 代码把所有特征都当成离散的每个取值算一个分支。连续特征的取值可能有几十个分支越多信息增益天然越高这跟 2.2 节说的“ID 号特征”是同一个毛病。解决连续特征必须做二分预处理要么在特征选择前把取值排序并枚举相邻中点要么直接用 3.2 节里thresholds的生成方式。手写代码时最容易遗漏的是离散特征枚举取值连续特征枚举中点两种特征的候选分裂点逻辑是分开的。4.3 树深不设限训练集满分、测试集翻车现象max_depthNone时训练集准确率 1.0测试集准确率只有 0.6 左右而且每次运行结果波动很大。原因不加限制的树把训练集里每个噪声样本都记住了典型过拟合。解决先固定random_state然后从max_depth2开始逐步加深度观察训练集和测试集准确率的变化。max_depth训练准确率测试准确率判断20.890.84欠拟合40.970.90合理81.000.72过拟合None1.000.58严重过拟合判断标准训练准确率超过测试准确率 10 个百分点以上基本就是过拟合信号。这时候你可以把max_depth往后回退两档再结合min_samples_leaf一起压。4.4 类别不均衡把根节点带偏现象二分类任务里正样本占 90%负样本占 10%树分裂几次后所有叶节点预测结果全是正类。原因叶节点的类别取的是“出现次数最多的类”负样本比例太低在多次分裂后被稀释成少数派。解决最简单的方案是在预测函数里按比例加权重把叶节点的多数投票改成加权投票majority_class max(counts.items(), keylambda kv: kv[1] * weight_dict[kv[0]])[0]其中weight_dict按样本总数 / (类别数 * 该类样本数)计算这个公式和 sklearn 的class_weightbalanced是同一个逻辑。如果不改代码另一个可行方案是采样把多数类样本随机抽掉一部分让两类比例接近 1:1。4.5 训练/测试划分不固定同一个数据集跑出两个结果现象室友用同一份 rar 包跑出来的准确率和你的差了 10 个百分点互相怀疑代码有问题。原因概率最大的不是算法差异而是train_test_split没固定随机种子或者干脆直接用全部数据训练再拿全部数据评估。解决把random_state42写死在划分那一行评估时严格只用测试集。这个坑几乎 90% 的新手都踩过但它和决策树本身没关系任何机器学习代码都一样。调参之前先统一划分的数据否则所有对比结果都没有意义。5. 验证决策树是否逼近真实曲线误差差值与 max_depth 扫描法写完了树怎么判断它到底好不好看一次准确率是不够的我用一个最笨但最有效的办法扫描max_depth把训练误差和测试误差的两条曲线画出来对比。for depth in [1, 2, 3, 4, 5, 6, 8, 10]: tree build_tree(X_train, y_train, depth0, max_depthdepth, min_samples_leaf2, criteriongini) train_acc evaluate(tree, X_train, y_train) test_acc evaluate(tree, X_test, y_test) print(fdepth{depth:2d} train{train_acc:.3f} test{test_acc:.3f} gap{train_acc - test_acc:.3f})输出里最值得看的不是准确率本身而是gap这一列。深度小的时候训练和测试准确率都很低两者差距也小说明树还没学到足够的信息欠拟合深度往上加训练准确率一路涨测试准确率涨到某个点开始掉头向下这个转折点对应的深度就是你这批数据的最优复杂度。理论上一棵能逼近真实曲线的树训练误差和测试误差应该同步下降并且保持在一个小的稳定差值内。调完深度再做一次后剪枝验证。用 sklearn 的DecisionTreeClassifier配合ccp_alpha跑一遍代价复杂度剪枝路径看看哪些分支删掉之后测试集准确率不降反升这能反推你手写树里的哪些节点是噪声分段。和随机森林对照也是常见做法同一份数据随机森林的测试准确率往往会比单棵树高 5 个百分点以上这不是说你的树写错了而是单棵树的方差太大集成的本质就是用多棵树的平均来压低方差。如果你的单棵树已经能做到和随机森林差不多的准确率反而要怀疑是不是数据太简单或过拟合了。日常做决策树实验时我的习惯是先固定数据划分再跑一遍深度扫描最后才去调min_samples_leaf和特征选择准则。手写树的意义不在于超越 sklearn而在于你能看到每一次分裂背后的熵变化和样本流动这比直接调库更能建立对模型边界的感知。希望帮到你。本文还有配套的精品资源点击获取