简介面向机器学习初学者与数据挖掘入门者的决策树分类实验资源包聚焦ID3、C4.5与CART三种核心算法的原理与实现适合正在学习分类模型、准备课程设计或想快速上手决策树实践的读者。包内提供完整的Python源码与可视化图表通过对比信息增益、增益率、基尼指数等划分准则直观展示三种算法在属性选择上的差异。资源共31个文件包含Python脚本、决策树可视化结果图片、实验报告及样例数据表等压缩包仅1.36MB轻量易用便于快速下载并复现实验。目前已有3572人学习或下载内容结构清晰既有可运行的tree.py、treePlotter.py等代码也有树形图与分类结果截图读者既可参照代码动手实践也可结合实验报告深入理解决策树的生成过程与剪枝思想是理论与实践结合较好的入门资料。1. 机器学习决策树实验一份能直接复现 ID3、C4.5、CART 的完整代码包机器学习决策树是很多人第一次真正「手写」算法的起点调 sklearn 两行代码就出结果但信息增益、增益率、基尼指数这三个名字背后的差异只有在你亲手实现时才暴露出来。这个资源包做的就是这件事——一个 Decision_tree-python 代码包用纯 Python 实现了 ID3、C4.5、CART 三种决策树算法附带可运行的 tree.py、绘图工具 treePlotter.py、训练集与测试集数据以及一份能直接当模板的决策树实验报告。它把周志华《机器学习》第四章里三种选属性准则全部落到了代码上。它最适合两类人要做机器学习课程实验、需要交代码加报告的学生以及想搞清楚决策树内部机制、不愿意只停留在 sklearn 调包层面的入门从业者。2. 资源包结构与数据准备先跑通 tree.py 再看算法很多人下载这类压缩包的第一反应是双击 tree.py 看能不能跑。我的建议是反过来先花五分钟把文件清单摸清楚因为这份资源里既有代码、数据集也有实验报告和结果截图它们各自服务不同环节。文件结构你看一眼就明白它就是一个标准机器学习课程实验的完整骨架。2.1 文件清单代码、数据、实验报告各司其职打开 Decision_tree-python-master 目录你会看到下面这些文件我把它们按用途分成三组分组文件作用核心代码tree.py三种决策树算法的完整实现含数据读取、建树、分类核心代码treePlotter.py用 matplotlib 把决策树画成可视化结构图数据dataset.txt训练集文本格式每行一个样本数据testset.txt测试集用于验证模型泛化能力数据数据表.xlsx原始数据表Excel 格式方便人工查看和筛选报告决策树实验报告.mdMarkdown 格式实验报告附了多张结果图过程产物x.dotgraphviz 的 DOT 中间格式可用 dot 命令转成图片过程产物ID3.png、C4.5.jpg、CART.jpg 等各算法生成树的截图和中间结果图缓存pycachePython 3.7 运行产生的字节码缓存可忽略这里有个容易忽略的细节pycache里的 pyc 文件名带 cpython-37说明这份资源是在 Python 3.7 环境下跑通的。如果你用的是 3.8 以上版本第一次运行会重新生成缓存不用管它。真正要关注的是 tree.py 和 treePlotter.py 这两个文件它们决定了整个实验能不能复现。数据表.xlsx 和 dataset.txt 的关系也要说清楚原始数据在 Excel 里方便人工查看和统计但 Python 读取最顺手的还是纯文本。所以实验前一般会先把 xlsx 里的内容整理成 txt特征列放前面标签列放最后每行一个样本列之间用逗号分隔。这种格式是决策树实验的事实标准因为建树代码每次都要按行切分、按列取值。2.2 数据格式与读取把 Excel 和 txt 喂给决策树先说数据长什么样。以西瓜书风格的表格为例特征是「色泽、根蒂、敲声」这一类离散属性标签是好瓜还是坏瓜。dataset.txt 的第一行通常是特征名列表从第二行开始是样本最后一列是类别。我一般会先写一个通用读取函数把文本数据一次性载入内存def loadDataSet(path): with open(path, r, encodingutf-8) as f: lines f.read().strip().split(\n) if not lines: return [], [] featureNames lines[0].strip().split(,) data [] for line in lines[1:]: line line.strip() if not line: continue data.append(line.split(,)) return data, featureNames # 使用示例 data, features loadDataSet(dataset.txt) print(样本数, len(data), 特征数, len(features) - 1) print(首行样本, data[0])这个函数做三件事读文件、按行切分、按逗号切分。注意编码参数我写了 utf-8如果数据文件里带中文且保存成了 GBK你得把 encoding 改成 gb18030 才不会乱码。data 是一个二维列表每个子列表里前 len(features) - 1 项是特征值最后一项是标签。features 列表的长度比特征列数多 1因为最后一个是标签列名。如果数据源是 xlsx手动转 txt 容易出错我习惯直接用 pandas 一次性搞定import pandas as pd df pd.read_excel(数据表.xlsx) df.to_csv(dataset.txt, indexFalse, headerTrue, sep,)这句代码不需要额外解释太多核心就两点headerTrue 会把第一行当特征名写进 txtsep, 保证列分隔符是逗号。如果你的数据集中有缺失值导出前先用 df.fillna(missing) 把空值统一替换成一个特殊字符串否则建树时 pandas 导出的是空位切分后列数会对不上。2.3 主流程走读tree.py 的入口和算法切换tree.py 的入口逻辑在所有决策树实现里几乎是同一套模板读取数据、备份特征名列表、调用建树函数、输出树结构。资源包里 tree.py 的命名是经典的西瓜书风格主程序长这样if __name__ __main__: data, features loadDataSet(dataset.txt) featuresCopy features[:] # 备份建树过程会修改 features mode C4.5 # 可选 ID3 / C4.5 / CART if mode ID3: decisionTree createTree(data, featuresCopy, chooseBestFeatureID3) elif mode C4.5: decisionTree createTree(data, featuresCopy, chooseBestFeatureC45) elif mode CART: decisionTree createTree(data, featuresCopy, chooseBestFeatureCART) else: raise ValueError(mode 只支持 ID3 / C4.5 / CART) print(decisionTree)这里我习惯把算法选择暴露成一个 mode 变量而不是分别写三次主流程。注意 createTree 的第三个参数是「特征选择函数」这是这份资源在工程上最优雅的设计ID3、C4.5、CART 的区别只在选特征这一步建树递归逻辑完全共用。所以后面章节我会把三个特征选择函数分别讲透createTree 只需要理解它是怎么递归的即可。3. 三种算法的核心原理与实现信息增益、增益率与基尼指数这一章是整份资源的技术核心。很多博客把 ID3、C4.5、CART 的区别列成一张表就完事了但真到写代码的时候你会发现三个算法的差异远不止公式不同——它们在特征选择、连续值处理、树结构上都有细微差别。我会对照 tree.py 里三个函数逐个拆。3.1 共同基础递归出口与停止条件不管用哪种特征选择准则createTree 的递归逻辑是一样的。每次递归做三件事检查是否可以停止分裂、选择一个最优特征、按特征取值把数据集切分成子集继续递归。停止条件在决策树里至关重要直接决定树的深度和过拟合程度def createTree(data, features, chooseBestFeature): classList [row[-1] for row in data] # 条件1所有样本属于同一类别直接返回该类别作为叶节点 if classList.count(classList[0]) len(classList): return classList[0] # 条件2没有剩余特征可用返回样本数最多的类别 if len(features) 0: return majorityVote(classList) bestFeatureIndex chooseBestFeature(data) bestFeatureName features[bestFeatureIndex] tree {bestFeatureName: {}} del features[bestFeatureIndex] featureValues [row[bestFeatureIndex] for row in data] uniqueValues set(featureValues) for value in uniqueValues: subData [row[:bestFeatureIndex] row[bestFeatureIndex 1:] for row in data if row[bestFeatureIndex] value] subFeatures features[:] tree[bestFeatureName][value] createTree(subData, subFeatures, chooseBestFeature) return tree两个停止条件看注释就能明白。我第一次写的时候漏了 condition 2结果特征用完之后递归死循环训练集里恰好每条样本特征组合都一样的测试数据才没触发属于运气好。majorityVote 就是统计 classList 里出现次数最多的标签遇到冲突类别时兜底用的代码不复杂但必须有。这个递归过程对三种算法完全透明——它只关心传入的 chooseBestFeature 是哪个函数。这也是为什么资源里三套实现能共用一套建树框架选特征这件事被抽象成了接口。3.2 ID3信息增益最大者优先ID3 的准则一句话讲完选择信息增益最大的特征进行划分。信息增益是「分裂前的熵」减去「分裂后的加权平均熵」。熵衡量的是类别混乱程度熵越大说明数据越混沌。先写计算熵的函数from math import log def calcShannonEnt(data): n len(data) if n 0: return 0.0 labelCounts {} for row in data: label row[-1] labelCounts[label] labelCounts.get(label, 0) 1 entropy 0.0 for cnt in labelCounts.values(): p cnt / n entropy - p * log(p, 2) return entropycalcShannonEnt 只关心最后一列标签。p 是每个类别出现的概率熵等于所有类别 -p·log2(p) 的累加。二分类情况下两类各占一半时熵为 1.0纯样本熵为 0。接下来是 16 行核心代码def chooseBestFeatureID3(data): baseEntropy calcShannonEnt(data) numFeatures len(data[0]) - 1 bestInfoGain 0.0 bestFeature -1 for i in range(numFeatures): featureValues set(row[i] for row in data) newEntropy 0.0 for value in featureValues: subData [row for row in data if row[i] value] prob len(subData) / len(data) newEntropy prob * calcShannonEnt(subData) infoGain baseEntropy - newEntropy if infoGain bestInfoGain: bestInfoGain infoGain bestFeature i return bestFeature逻辑说明对新特征的每个取值把样本切成子集算子集熵再按子集样本占比加权求和得到分裂后的期望熵。用分裂前熵减分裂后熵就是信息增益。bestInfoGain 初始为 0意味着如果所有特征增益都是 0函数返回 -1 表示没有可用的划分特征createTree 会在上游兜底。注意这里我用了 set 去重特征值如果某个特征是连续型数值这个 set 会巨大无比后面避坑章会专门讲。ID3 的毛病在面试八股里被反复考它偏好取值很多的属性。极端情况是给每个样本编一个唯一 ID 作为特征ID3 会毫不犹豫选它因为每个取值都对应一个子集子集内部纯度极高。实际实验数据集里如果有这种「杀器特征」树会退化成一棵查询表这类问题是用 C4.5 修复的。3.3 C4.5用增益率修正多值属性偏好C4.5 的核心改动是引入增益率。它是信息增益除以固有值Intrinsic Value固有值描述的是「按这个特征的取值分布能带来多少信息」取值越多固有值越大。这样信息增益再高如果特征取值特别多增益率也会被拉低。在数据结构里C4.5 的选特征函数比 ID3 多一步它不是直接选增益率最高的特征而是先筛掉信息增益低于平均水平的特征再在剩下的特征里挑增益率最高的。这一步官方术语叫启发式规则。这里给出一个完整实现它会同时计算增益和固有值def calcGainAndIV(data, featureIndex): baseEntropy calcShannonEnt(data) featureValues set(row[featureIndex] for row in data) newEntropy 0.0 iv 0.0 for value in featureValues: subData [row for row in data if row[featureIndex] value] prob len(subData) / len(data) newEntropy prob * calcShannonEnt(subData) iv - prob * log(prob, 2) infoGain baseEntropy - newEntropy return infoGain, iv def chooseBestFeatureC45(data): numFeatures len(data[0]) - 1 gains [] ivs [] baseEntropy calcShannonEnt(data) for i in range(numFeatures): gain, iv calcGainAndIV(data, i) gains.append(gain) ivs.append(iv) avgGain sum(gains) / len(gains) bestGainRatio 0.0 bestFeature -1 for i in range(numFeatures): if gains[i] avgGain: continue if ivs[i] 0: continue ratio gains[i] / ivs[i] if ratio bestGainRatio: bestGainRatio ratio bestFeature i return bestFeature注意两个细节。第一ivs[i] 0 时直接跳过因为一个特征的取值如果只有一个固有值为 0 会导致除零错误。第二先算平均增益再过滤这保证了最终选出的特征至少信息增益不是最差的那批。实际用的时候你会发现 C4.5 选出来的树往往比 ID3 更矮更稳代价是每次选特征都要算两遍熵训练略慢。数据集中如果存在连续特征C4.5 应该做二分法离散化排序后取相邻值中点挨个试选信息增益最大的切分点。这个我在避坑章再展开因为处理不好会直接翻车。3.4 CART基尼指数与二叉树划分CART 走的完全是另一条路它用基尼指数而不依赖熵。基尼指数衡量的是「从数据里随机抽两个样本类别不一致的概率」所以值越小纯度越高。计算函数比熵简单def calcGini(data): n len(data) if n 0: return 0.0 labelCounts {} for row in data: label row[-1] labelCounts[label] labelCounts.get(label, 0) 1 gini 1.0 for cnt in labelCounts.values(): p cnt / n gini - p * p return gini但 CART 的特征选择比 ID3/C4.5 繁琐因为 CART 强制生成二叉树。对离散特征它不是按所有取值分裂而是遍历每种「取值子集」的组合把特征空间一分为二。对连续特征则保持排序后二分。下面给出简化版选择函数它对每个特征遍历候选划分点计算划分后的加权基尼指数def chooseBestFeatureCART(data): numFeatures len(data[0]) - 1 bestGini float(inf) bestFeature -1 bestSplitValue None for i in range(numFeatures): featureValues sorted(set(row[i] for row in data)) for j in range(len(featureValues) - 1): splitValue (featureValues[j] featureValues[j 1]) / 2 leftData [row for row in data if row[i] splitValue] rightData [row for row in data if row[i] splitValue] giniLeft len(leftData) / len(data) * calcGini(leftData) giniRight len(rightData) / len(data) * calcGini(rightData) giniSum giniLeft giniRight if giniSum bestGini: bestGini giniSum bestFeature i bestSplitValue splitValue return bestFeature, bestSplitValue逻辑说明这里 splitValue 取相邻两个值的平均是连续特征二分的标准做法。对离散特征同样走「小于等于 / 大于」这条路但分裂后两边都会是混合取值语义上不太优雅。真正工程化的 CART 实现里离散特征一般会枚举所有二划分组合资源里的简化版其实够实验用了。注意 CART 返回的是 bestFeature 和 bestSplitValue 两个值createTree 需要对应修改切分逻辑。CART 树结构也更简单每个内部节点只分两支。这就是为什么 scikit-learn 的 DecisionTreeClassifier 默认实现就是 CART——因为二叉树对剪枝、连续特征处理都比多叉树省心。3.5 三个特征选择函数在 tree.py 里的衔接回到 tree.py 的设计createTree 第三个参数接收 chooseBestFeature 函数但 CART 的函数签名比 ID3、C4.5 多一个返回值。我的实战处理方式是用一个字典把模式映射到函数并且调整切分逻辑splitRules { ID3: lambda data: (chooseBestFeatureID3(data), None), C4.5: lambda data: (chooseBestFeatureC45(data), None), CART: lambda data: chooseBestFeatureCART(data), }lambda 把 ID3 和 C4.5 的返回值补成二元组CART 原样返回。这样 createTree 内部统一按 (featureIndex, splitValue) 去切分。splitValue 为 None 时按离散值多叉分裂数值存在时按比较二分。这个适配层的价值很大一口把三种算法塞进了同一套递归框架改模式只改一个变量。这份资源在代码组织上真正值得学习的点就在这里——算法的区别是策略层面的结构层面的东西不要重复写。你之后写随机森林里每棵弱学习器也会用这套思路复用 createTree。4. 决策树实验的五个常见坑从过拟合到绘图乱码的排查记录我拆这份资源的时候顺手把容易踩的坑全过了一遍。这些坑不是代码 bug而是「代码能跑但结果不对」或者「结果对但图出不来」的隐性雷区每一条都是真实翻车记录。4.1 坑一树无限生长导致训练集 100% 准确率、测试集惨不忍睹现象createTree 递归到底训练集上分类完全正确把 testset.txt 喂进去准确率不到 60%。树被打印出来看深度到了十几层很多叶子节点只有一个样本。原因实验数据带有噪声或特征不足以完美区分样本时树一味生长会把噪声也学进去。决策树逼近的是真实分布的分段常数近似它对连续曲线天生拟合得粗糙深度越大越是在硬记训练集这就是过拟合。解决给 createTree 加预剪枝参数。最常见的做法是传 maxDepth 和 minSamples递归进入前判断def createTree(data, features, chooseBestFeature, maxDepth5, depth0, minSamples5): classList [row[-1] for row in data] if len(classList) minSamples or depth maxDepth: return majorityVote(classList) # 其余逻辑不变递归时 depth 1我的建议是先跑一次不加限制的树打印出树结构数一下有效深度再把 maxDepth 设成这个值的三分之二minSamples 设成总样本数的 10% 左右起步观察测试集准确率变化。别一上来就 max_depth3欠拟合也难受。4.2 坑二连续特征直接丢进 ID3 导致熵计算失真甚至卡死现象数据集里有一列是「密度」「含糖率」这种数值型数据ID3 跑起来慢得离谱生成的树深度巨大而且每个节点都按具体数值切分完全不可读。原因ID3 对所有特征取值算熵连续特征每个样本值基本都不重复set 之后得到几十个取值每个取值只覆盖一个样本分裂后每个子集熵都是 0信息增益直接拉满。树退化成了问「密度 / 0.697 吗」这种不可泛化的判断。解决实验数据千万别让 ID3 直接碰连续列。要么在数据预处理阶段把数值列离散化成区间比如密度 0.5 算高否则算低要么直接换 C4.5 或 CART。资源包的核心代码本身不负责自动离散化这个决策得你在 loadDataSet 之后手动做我的习惯是单独写一个离散化函数def discretizeColumn(data, colIndex, thresholds): for row in data: val float(row[colIndex]) row[colIndex] low if val thresholds else highthresholds 可以按中位数、均值或者你业务上的实际分界来定。注意这步必须在建树前完成且 apply 到测试集时用同一个阈值否则测试集分布漂移准确率会骗人。4.3 坑三treePlotter 画决策树节点中文全是方块现象matplotlib 弹出的窗口里根节点文本是「▒▒▒ ▒▒ ▒▒」数值和字母正常中文字体全部变成方块或问号。原因matplotlib 默认字体是 DejaVu Sans不含中文字形。这在 Windows 和 Mac 上都会出现只是表现略有不同。解决在 treePlotter.py 的 import 之后加四行import matplotlib.pyplot as plt plt.rcParams[font.sans-serif] [SimHei] plt.rcParams[axes.unicode_minus] FalseSimHei 是 Windows 自带黑体Mac 上可以改成 Arial Unicode MS。axes.unicode_minus 这行防的是坐标轴负号显示成方块画树图不一定会用到但统一写上省事。如果代码里用的是 from matplotlib import pyplot 这种写法rcParams 的路径不变。改完后关掉旧绘图窗口重新运行中文立即恢复。4.4 坑四x.dot 转图片报 InvocationException 或 dot 命令不存在现象想按实验报告里的命令把 x.dot 转成 PNG用 pydot 或 graphviz 的 Python 接口报错错误信息里有 GraphVizs executables not found 字样或者在命令行敲 dot 提示 command not found。原因资源包里的 x.dot 是 graphviz 生成的过程文件但生成它和渲染它都需要安装 graphviz 本体。pydot 只是 Python 接口它负责调用你的系统里有没有装的 dot 可执行文件装完 pip 装 pydot 是没用的。解决先装系统依赖再装 Python 包顺序不能反。Windows 上把 graphviz 的 bin 目录手动加进系统 PATH装完重启终端再运行pip install graphviz dot -Tpng x.dot -o tree.png跑通后你会得到一张完整的决策树结构图。如果 x.dot 是 treePlotter 导出的中间状态这一步只是为了可视化确认不参与算法本身所以即使转化失败也不影响实验结论但报告里少一张图会扣分所以这个坑值得提前排掉。4.5 坑五数据集没固定随机种子每次跑的准确率都不一样现象同一份 dataset.txt连续跑三次实验测试集准确率分别是 82.1%、78.4%、80.3%每次的树结构还有一些小差异。如果你的代码是按随机比例划分训练集和测试集那基本就是这个原因。原因train_test_split 这类操作内部用了随机数生成器没设 seed 每次划分都不一样。手写实验资源里很多同学的代码是直接从网上复制的大家都没意识去固定随机状态。解决一切涉及随机划分的代码在划分前固定种子import random random.seed(42)或者如果是用 sklearn 的 train_test_split直接在调用时加 random_state42。这个数字本身没有魔法含义只是保证可复现。从那以后我每次拿到别人的实验代码第一件事就是搜 random 和 seed 是否固定——不固定种子的实验结果没有任何可比性你甚至没法判断调参是变好了还是随机噪声。5. 用测试集和 treePlotter 验证模型画树、预测、调参三件事资源包里最大的隐藏价值是 testset.txt。很多实验代码只写了建树和打印没有完整的预测验证闭环导致你交报告时只能说「树建出来了」说不清模型到底准不准。这章我给你一套三连操作直接补全验证链路。5.1 手写 predict 对 testset.txt 逐条分类决策树的预测本质就是沿着树往下走。树结构是嵌套字典叶子是字符串标签内部节点是特征名。predict 函数可以这样写def predict(tree, sample): if not isinstance(tree, dict): return tree featureName list(tree.keys())[0] value sample[featureName] subTree tree[featureName].get(value, None) if subTree is None: return unknown return predict(subTree, sample)注意这里 sample 是一个字典键是特征名值是样本特征。如果你的 sample 是列表建树时就得同时保留 featureNames 映射关系。我在实验里一般先把 testset 的每一行转成字典再调用 predict。下面是准确率的完整计算def evaluate(tree, testFile, featureNames): correct 0 total 0 with open(testFile, r, encodingutf-8) as f: for line in f.readlines()[1:]: line line.strip() if not line: continue parts line.split(,) sample dict(zip(featureNames, parts)) pred predict(tree, sample) if pred parts[-1]: correct 1 total 1 return correct / total if total 0 else 0.0 accuracy evaluate(decisionTree, testset.txt, features) print(测试集准确率%.2f%% % (accuracy * 100))这段逻辑不复杂但建议你亲手写一遍。预测时如果某个特征取值在训练集的树里不存在返回值是 unknown——这说明测试集和训练集分布不一致或者某个离散特征出现了训练时没见过的类别最常见的处理是把 unknown 当作错误并打印该样本方便你回头查数据。5.2 把 x.dot 转成可视化树并解读分裂依据实验报告里最核心的证据就是树的结构图。treePlotter.py 的作用在这里但它依赖 graphviz 环境。转图命令上节已经给了关键是怎么读懂图每棵树的根节点是第一步划分依据越靠近根的属性重要性越高。ID3 的根节点往往落在取值少的特征上C4.5 的根更偏向信息增益率高的CART 因为强制二叉根节点的划分点会直接在两个分支上体现。我一般会把三种算法的树并列对照观察三个根节点是否不同。如果完全一致有理由怀疑代码分支是不是写串了——比如 C4.5 实际调用了 ID3 的函数。对照测试集准确率你会发现 C4.5 和 CART 的表现通常接近ID3 在连续特征多时明显偏弱。这个对照结果写进报告里比贴十行公式有说服力得多。5.3 两个调参习惯预剪枝和样本阈值最后的操作建议给到调参层面。手写树和 sklearn 不同没那么多超参数最有效的是两个树的最大深度 maxDepth 和叶子最少样本数 minSamples。预剪枝代码在避坑章给过了实际调的时候遵循「小步快跑」原则——先跑 maxDepth3、minSamples10看准确率再逐步加深或减小阈值观察准确率变化曲线。你会发现准确率不是单调上升的越过某个峰值后开始下降那个峰值就是当前数据下的最优深度。这个峰值出现的位置跟数据本身强相关没有固定经验值。单棵树的深度上限也就是随机森林里每棵弱学习器的深度上限在 sklearn 里对应 max_depth 参数。你手写这一遍其实就是在理解那个参数为什么存在树过浅欠拟合过深过拟合永远没有一劳永逸的默认值。这三件事做完你手里的实验报告就从「我调了包」变成了「我实现了算法并验证了效果」。我从那以后每次做决策树实验都强制走一遍这个流程——先画图确认树结构合理再用 testset 跑准确率最后调参观察变化曲线缺一步都不交报告。希望帮到你。本文还有配套的精品资源点击获取