简介本资源是北京邮电大学自动化专业《机器学习》课程实验的决策树算法Python实现代码面向高校本科生及机器学习初学者聚焦监督学习中分类任务的核心算法实践。压缩包为7z格式仅含1个Python源文件Ex2_DecTree.py大小仅1KB轻量简洁涵盖数据加载、预处理、信息增益计算、决策树构建、模型训练与预测、性能评估及可视化等完整流程代码结构清晰适合作为教学参考与算法复现起点。已有1055人学习下载体现了该实验在高校机器学习实践教学中的典型性与实用性。读者可直接运行代码理解ID3/C4.5类决策树的底层逻辑掌握scikit-learn中DecisionTreeClassifier的参数调优方法并借助graphviz实现树结构可视化快速建立从理论推导到工程落地的闭环认知。1. 北邮自动化专业学生做决策树实验为什么用 Python 实现比调包更能吃透 ID3/C4.5 的分裂逻辑北邮自动化学院《机器学习导论》课程实验里“决策树”从来不是只调sklearn.tree.DecisionTreeClassifier就交差的环节。去年三组同学在“收入预测”实验中用max_depth3跑出准确率 82%但老师一句“请画出你手算的第一次分裂特征和信息增益值”当场有两人卡住——他们没写过一行entropy()或gain_ratio()计算代码模型是黑匣子训练过程是玄学。这正是本篇要解决的核心用纯 Python 从零实现 ID3 和 C4.5 决策树不依赖 sklearn但最终能与 sklearn 对齐结果让北邮自动化本科生真正看清“特征怎么选、阈值怎么定、树怎么长”的每一步计算细节。它不追求工业级鲁棒性而专注课程实验最常考的三个落地点① 手动计算信息熵/增益比② 构建可打印结构的树节点③ 在 UCI Adult收入预测和 Iris鸢尾花分类两个经典数据集上复现课本公式。适合刚学完周志华《机器学习》第4章、正在赶头歌平台“决策树进行鸢尾花分类-sklearn版”实验但想知其所以然的同学。2. 从信息熵到分裂准则为什么 ID3 用信息增益、C4.5 改用增益比手推公式 Python 实现决策树不是“自动分组”而是基于统计量做理性选择。北邮实验报告里常被扣分的地方就是混淆了 ID3 和 C4.5 的分裂依据。我们先厘清本质ID3 只处理离散特征用信息增益Information GainC4.5 支持连续特征和缺失值改用增益比Gain Ratio来抑制偏向取值多的特征。这不是“升级”而是对信息增益固有缺陷的修补——比如把“身份证号”当特征每个样本 ID 都不同信息增益会爆表但毫无泛化意义。2.1 信息熵与信息增益手算一例再写 Python 函数以 UCI Adult 数据集中的education教育程度为例假设当前节点含 100 个样本其中 60 人年收入 ≤50K40 人 50K。当前节点熵$ H(S) -\frac{60}{100}\log_2\frac{60}{100} - \frac{40}{100}\log_2\frac{40}{100} \approx 0.971 $若按education分为“高中以下”30 样本25 人 ≤50K、“本科”50 样本25 人 ≤50K、“硕士以上”20 样本10 人 ≤50K各子集熵$ H(S_1) \approx 0.551 $, $ H(S_2) 1.0 $, $ H(S_3) 1.0 $加权平均熵$ H(S|education) \frac{30}{100} \times 0.551 \frac{50}{100} \times 1.0 \frac{20}{100} \times 1.0 0.865 $信息增益$ IG(S, education) 0.971 - 0.865 0.106 $这个过程必须手动算过一遍才能理解后续代码为何要循环遍历所有特征、所有可能分割点。下面给出可直接粘贴进实验脚本的熵与增益计算函数import numpy as np from collections import Counter def entropy(y): 计算标签 y 的信息熵 if len(y) 0: return 0 counts np.array(list(Counter(y).values())) probs counts / len(y) return -np.sum([p * np.log2(p) for p in probs if p 0]) def information_gain(y, y_left, y_right): 计算按某特征分割后的信息增益 n len(y) n_left, n_right len(y_left), len(y_right) if n_left 0 or n_right 0: return 0 return entropy(y) - (n_left / n) * entropy(y_left) - (n_right / n) * entropy(y_right)提示entropy()中if p 0是关键——避免0 * log2(0)导致nan。北邮实验环境常用 Python 3.8np.log2(0)返回-inf不加判断会导致整个增益计算崩掉。2.2 增益比解决 ID3 的“特征取值过多陷阱”信息增益天然偏好取值多的特征如“日期”字段有 365 个不同值。C4.5 引入分裂信息Split Information作为惩罚项$$ \text{GainRatio}(S, A) \frac{IG(S, A)}{IV(A)} $$其中 $ IV(A) -\sum_{v \in Values(A)} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|} $即特征 A 自身的信息熵。例如若某特征将 100 个样本分成 99 个单一样本组 1 组含 1 样本则 $ IV(A) \approx \log_2 100 \approx 6.64 $极大拉低增益比从而抑制该特征被选中。def split_information(y, groups): 计算特征分裂的信息量 IV(A) n len(y) iv 0 for group in groups: if len(group) 0: continue prob len(group) / n if prob 0: iv - prob * np.log2(prob) return iv def gain_ratio(y, y_left, y_right): 计算增益比 ig information_gain(y, y_left, y_right) iv split_information(y, [y_left, y_right]) return ig / iv if iv 0 else 0注意split_information()输入是各子集标签列表如[y_left, y_right]不是原始特征列。这是学生最容易写错的地方——误把X[:, feature_idx]直接传进去导致维度错乱。正确做法是先用特征值切分样本索引再用索引提取对应y子集。3. 构建可解释的树结构用嵌套字典模拟节点支持 print_tree() 可视化sklearn 的tree.plot_tree()很炫但课程实验要求你“写出树的结构”。北邮自动化实验报告明确要求“提交决策路径文本描述例如 root→age≤35→income50K”。这意味着树不能只是fit()后黑盒输出而必须能递归展开、逐层打印。我们采用轻量级嵌套字典设计每个节点含feature,threshold,value,left,right字段完全避开sklearn.tree._tree.Tree这类底层结构。3.1 树节点定义与递归构建逻辑核心思想每次分裂后将当前数据集递归传入左右子树直到满足停止条件如样本数 5或纯度 ≥ 0.95或深度超限。注意北邮实验默认最大深度设为 5最小样本分割数设为 10这两个参数必须显式控制否则在 Iris 上可能生成 10 层深树无法手绘。class DecisionTreeNode: def __init__(self, featureNone, thresholdNone, valueNone, leftNone, rightNone): self.feature feature # 最优分裂特征索引如 0 表示 sepal length self.threshold threshold # 连续特征的分割阈值离散特征为分割值如 High self.value value # 叶节点的预测类别如 setosa self.left left # 左子树满足 threshold 的样本 self.right right # 右子树满足 threshold 的样本 def build_tree(X, y, max_depth5, min_samples_split10, depth0, criteriongain_ratio): 递归构建决策树 n_samples, n_features_total X.shape n_classes len(np.unique(y)) # 停止条件纯节点、样本过少、达到最大深度 if n_classes 1 or n_samples min_samples_split or depth max_depth: # 叶节点返回众数类别 most_common Counter(y).most_common(1)[0][0] return DecisionTreeNode(valuemost_common) # 寻找最优分裂 best_gain -1 best_feature None best_threshold None best_left_idx None best_right_idx None for feature_idx in range(n_features_total): # 对连续特征尝试所有唯一值作为候选阈值排序后去重 if np.issubdtype(X[:, feature_idx].dtype, np.number): thresholds np.unique(X[:, feature_idx]) for t in thresholds[:-1]: # 避免取最大值导致右子集为空 left_mask X[:, feature_idx] t right_mask ~left_mask if np.sum(left_mask) 0 or np.sum(right_mask) 0: continue y_left, y_right y[left_mask], y[right_mask] if criterion gain_ratio: gain gain_ratio(y, y_left, y_right) else: # information_gain gain information_gain(y, y_left, y_right) if gain best_gain: best_gain gain best_feature feature_idx best_threshold t best_left_idx left_mask best_right_idx right_mask else: # 离散特征按取值分组此处简化为二分实际可扩展为多叉 # 北邮实验数据集如 Adult、Iris 均含连续特征此分支暂略 # 若未找到有效分裂退化为叶节点 if best_feature is None: most_common Counter(y).most_common(1)[0][0] return DecisionTreeNode(valuemost_common) # 递归构建左右子树 left_tree build_tree(X[best_left_idx], y[best_left_idx], max_depth, min_samples_split, depth1, criterion) right_tree build_tree(X[best_right_idx], y[best_right_idx], max_depth, min_samples_split, depth1, criterion) return DecisionTreeNode( featurebest_feature, thresholdbest_threshold, leftleft_tree, rightright_tree )提示thresholds[:-1]是血泪经验——若取max(thresholds)则X[:,f]t恒成立右子集为空递归崩溃。北邮实验数据中sepal width最小值 2.0最大值 4.4若阈值取 4.4所有样本都进左子树右子树无数据build_tree()会因len(y_right)0报IndexError。3.2 可打印的树结构用缩进模拟层级支持复制进 Word 报告课程实验要求“文字描述决策路径”而非图片。我们写一个print_tree()函数输出带缩进的纯文本树格式与周志华《机器学习》图4.2一致def print_tree(node, depth0, feature_namesNone, class_namesNone): 打印树结构支持中文特征名和类别名 indent * depth if node.value is not None: # 叶节点 label class_names[node.value] if class_names else node.value print(f{indent}→ 预测: {label}) return # 内部节点 fname feature_names[node.feature] if feature_names else f特征{node.feature} print(f{indent}├─ {fname} {node.threshold:.3f}) print_tree(node.left, depth1, feature_names, class_names) print(f{indent}└─ {fname} {node.threshold:.3f}) print_tree(node.right, depth1, feature_names, class_names) # 使用示例Iris 数据集 from sklearn.datasets import load_iris iris load_iris() X, y iris.data, iris.target tree build_tree(X, y, max_depth3, min_samples_split5, criteriongain_ratio) print_tree(tree, feature_namesiris.feature_names, class_namesiris.target_names)运行后输出类似├─ petal length (cm) 2.450 → 预测: setosa └─ petal length (cm) 2.450 ├─ petal width (cm) 1.750 → 预测: versicolor └─ petal width (cm) 1.750 → 预测: virginica这正是实验报告要求的“可验证、可手绘、可答辩”的结构。无需 matplotlib不依赖 GUI复制进 Word 即可排版。4. 在 Iris 和 Adult 数据集上跑通预处理差异、特征编码、结果对齐 sklearn北邮自动化课程实验指定两个数据集Iris小而精用于验证原理和 Adult大而杂用于检验工程能力。二者预处理方式天差地别——Iris 是干净数值型Adult 含大量离散字段如workclass,education,marital-status和缺失值?。若不做适配你的纯 Python 决策树会在 Adult 上直接报ValueError: Input contains NaN。4.1 Iris零预处理直接喂入验证公式一致性Iris 特征全为浮点数标签为整数 0/1/2。我们用sklearn的DecisionTreeClassifier作为黄金标准对比自研树的预测结果和结构from sklearn.tree import DecisionTreeClassifier from sklearn.model_selection import train_test_split # 划分数据 X_train, X_test, y_train, y_test train_test_split( iris.data, iris.target, test_size0.3, random_state42, stratifyiris.target ) # sklearn 训练固定参数确保可比 sklearn_tree DecisionTreeClassifier( criterionentropy, # 对应信息增益 max_depth3, min_samples_split5, random_state42 ) sklearn_tree.fit(X_train, y_train) # 自研树训练 my_tree build_tree(X_train, y_train, max_depth3, min_samples_split5, criterioninformation_gain) # 预测对比 def predict_tree(X, tree): 递归预测单个样本 if tree.value is not None: return tree.value if X[tree.feature] tree.threshold: return predict_tree(X, tree.left) else: return predict_tree(X, tree.right) y_pred_my np.array([predict_tree(x, my_tree) for x in X_test]) y_pred_sklearn sklearn_tree.predict(X_test) print(f自研树准确率: {np.mean(y_pred_my y_test):.3f}) print(fsklearn 准确率: {np.mean(y_pred_sklearn y_test):.3f}) # 输出应接近0.933 vs 0.933注意criterionentropy在 sklearn 中等价于 ID3 的信息增益而criteriongini是 CART非本实验范围。北邮实验明确要求“实现 ID3 或 C4.5”故必须用entropy。4.2 Adult处理缺失值、离散特征、类别不平衡Adult 数据集adult.data需手动清洗。头歌平台提供的是已处理版本但北邮实验要求你从原始 UCI 下载并清洗——这是考察工程能力的关键点。缺失值处理Adult 中?出现在workclass,occupation,native-country。不能简单删行会损失 10% 数据应按众数填充# 读取并清洗 import pandas as pd col_names [age,workclass,fnlwgt,education,education-num, marital-status,occupation,relationship,race,sex, capital-gain,capital-loss,hours-per-week,native-country,income] df pd.read_csv(adult.data, namescol_names, skipinitialspaceTrue, na_values?) # 众数填充离散列 for col in [workclass, occupation, native-country]: df[col].fillna(df[col].mode()[0], inplaceTrue)离散特征编码不能直接用字符串喂入X。需用LabelEncoder或pd.get_dummies()。但注意get_dummies()会爆炸式增加维度native-country有 41 类 → 41 列而北邮实验内存限制严格。推荐用LabelEncoderOrdinalEncoder组合保持单列整数编码from sklearn.preprocessing import LabelEncoder, OrdinalEncoder le_income LabelEncoder() y le_income.fit_transform(df[income]) # 50K→0, 50K→1 # 对离散特征列编码 discrete_cols [workclass,education,marital-status,occupation, relationship,race,sex,native-country] X_discrete df[discrete_cols].copy() ordinal_enc OrdinalEncoder(handle_unknownuse_encoded_value, unknown_value-1) X_discrete_encoded ordinal_enc.fit_transform(X_discrete) # 数值特征拼接 numeric_cols [age,fnlwgt,education-num,capital-gain,capital-loss,hours-per-week] X_numeric df[numeric_cols].values X np.hstack([X_numeric, X_discrete_encoded])类别不平衡Adult 中50K占 76%50K占 24%。若不处理树会倾向预测多数类。北邮实验不要求 SMOTE但要求你在build_tree()中修改叶节点判定逻辑不用众数而用加权众数按类别频率调整阈值# 替换原叶节点逻辑 class_counts Counter(y) total len(y) # 计算各类占比 ratios {cls: cnt/total for cls, cnt in class_counts.items()} # 取占比最高的类仍是众数但已隐含权重 most_common max(ratios.items(), keylambda x: x[1])[0]完成上述清洗后你的自研树在 Adult 测试集上应达到82%~84% 准确率sklearn 同参数下约 83.5%误差 0.5%证明实现正确。5. 避坑指南北邮自动化学生在决策树实验中最常踩的 4 个坑这些坑我带过三届北邮自动化本科生每年都有至少 15 人卡在同一处。不是代码写错而是对课程要求和数据特性的误判。5.1 坑1用sklearn的plot_tree当“手写树结构”被老师当场退回现象实验报告里贴了一张plot_tree()生成的图结论写“树结构如上图所示”。原因课程实验明确要求“文字描述分裂路径”图是辅助文字才是主体。plot_tree()输出的是可视化渲染结果无法提取feature/threshold文本链。且头歌平台禁止截图上传只接受.py和.txt。解决必须用print_tree()输出纯文本并在报告中复制该文本再手绘对应流程图。文本链就是答辩时老师追问“第二层分裂依据”的答案来源。5.2 坑2Iris 数据集上准确率 100%但 Adult 上直接报ZeroDivisionError现象Iris 跑通Adult 一运行就ZeroDivisionError: float division by zero。原因entropy()函数未处理len(y)0边界或split_information()中prob0未过滤导致log2(0)。Adult 清洗后仍有极少数空分组如某职业仅 1 人被分到测试集后训练集该职业为空。解决在entropy()和split_information()开头加if len(y) 0: return 0所有涉及log2()的地方if p 0必须存在。这是北邮实验环境Python 3.8 numpy 1.21的硬性要求。5.3 坑3max_depth5下树只有 2 层怀疑代码没递归现象设置max_depth5但print_tree()只显示 2 层第三层全是叶节点。原因min_samples_split10过大。Adult 训练集约 30000 样本但按education分组后“Doctorate”仅 500 人再分一次可能只剩 50 人 10提前终止。解决北邮实验指导书注明“Adult 数据建议min_samples_split2”Iris 用 5 即可。参数必须按数据集动态调整不能全局固定。5.4 坑4predict_tree()返回None测试集预测全错现象y_pred_my全为None准确率为 0。原因predict_tree()递归中X[tree.feature]索引越界。Iris 特征数 4但tree.feature5—— 因为训练时X是pandas.DataFrame列索引含range(4)但build_tree()中X[:, feature_idx]要求数组索引。若传入df.values则正常传入df则X[:, feature_idx]报错但部分环境静默失败tree.feature被赋为None后续X[None]返回None。解决所有输入X必须是np.ndarray用X df[features].values显式转换。在build_tree()开头加断言assert isinstance(X, np.ndarray), X must be numpy array。6. 进阶技巧用tree.export_text()对齐 sklearn一键生成实验报告树结构做完基础实现后你会面临一个现实问题如何向老师证明“我的手写树和 sklearn 逻辑一致”光靠准确率不够因为随机种子不同结果就不同。真正的验证是——让两棵树的分裂特征、阈值、叶节点类别完全一致。sklearn提供了export_text()它输出的文本结构和我们print_tree()高度相似可直接对比。6.1 用export_text()提取 sklearn 树的可比结构from sklearn.tree import export_text # 用相同参数训练 sklearn 树 sklearn_tree DecisionTreeClassifier( criterionentropy, max_depth3, min_samples_split5, random_state42 ) sklearn_tree.fit(X_train, y_train) # 导出文本结构关键指定 feature_names r export_text( sklearn_tree, feature_namesiris.feature_names, class_namesiris.target_names, decimals3, spacing3, show_weightsFalse ) print(r)输出示例|--- petal length (cm) 2.450 | |--- class: setosa |--- petal length (cm) 2.450 | |--- petal width (cm) 1.750 | | |--- class: versicolor | |--- petal width (cm) 1.750 | | |--- class: virginica6.2 自研树导出格式对齐修改print_tree()使其兼容export_text()语法只需微调缩进和符号就能生成可 diff 的文本def export_my_tree(node, depth0, feature_namesNone, class_namesNone, prefix| ): 输出与 sklearn export_text 兼容的文本 if node.value is not None: label class_names[node.value] if class_names else node.value indent prefix * depth return f{indent}|--- class: {label}\n fname feature_names[node.feature] if feature_names else ffeature{node.feature} indent prefix * depth left_str export_my_tree(node.left, depth1, feature_names, class_names, prefix) right_str export_my_tree(node.right, depth1, feature_names, class_names, prefix) return (f{indent}|--- {fname} {node.threshold:.3f}\n f{left_str} f{indent}|--- {fname} {node.threshold:.3f}\n f{right_str}) # 生成对比文本 my_text export_my_tree(my_tree, feature_namesiris.feature_names, class_namesiris.target_names) sklearn_text export_text(sklearn_tree, feature_namesiris.feature_names, class_namesiris.target_names, decimals3) # 写入文件供 diff with open(my_tree.txt, w) as f: f.write(my_text) with open(sklearn_tree.txt, w) as f: f.write(sklearn_text)然后终端执行diff my_tree.txt sklearn_tree.txt。若输出为空说明两棵树结构完全一致——这是北邮实验答辩时最硬核的佐证材料。我曾见学生凭此获得附加分因为老师说“能对齐 sklearn说明你真懂了分裂逻辑不是调包。”6.3 一个真实教训别在build_tree()里用random_state最后分享一个血泪经验所有随机性必须在数据划分阶段引入树构建过程必须确定性。北邮实验要求“结果可复现”而build_tree()若用np.random.choice()选特征顺序每次运行树结构都不同答辩时老师让你现场 rerun结果变了直接不及格。正确做法是特征遍历用for feature_idx in range(n_features)固定顺序分裂阈值用np.unique()排序后遍历所有随机操作只发生在train_test_split()时。这样同一份数据、同一份代码永远输出同一棵树。希望帮到你。本文还有配套的精品资源点击获取