Matlab从零实现C4.5决策树：增益率计算与剪枝全流程

简介：本资源是一份面向计算机、电子信息工程及数学等专业本科生的机器学习课程实践材料，聚焦决策树C4.5算法原理与Matlab实现，适用于课程设计、期末大作业或毕业设计参考。压缩包共14个文件，含7个.mat数据文件（如train_features.mat、test_targets.mat等，承载训练/测试样本与标签）、6个.m函数脚本（包括主程序main.m、核心算法C4_5.m、分类误差计算classification_error.m等），以及1份详尽的Word教程文档，全面覆盖数据预处理、信息增益率计算、树构建与剪枝、分类预测全流程。资源仅45KB，轻量紧凑，结构清晰，便于初学者理解算法逻辑并动手调试。已有2689人学习下载，配套教程与可运行源码结合，显著降低C4.5从理论到实践的门槛，特别适合具备基础Matlab编程能力、需自主完成算法复现与结果分析的学习者。

1. 用 Matlab 手撕 C4.5 决策树：不是调用fitctree，而是从熵、增益率、剪枝逻辑开始写透每行代码

你打开一个.rar文件，里面是c45_main.m、build_tree.m、calc_info_gain_ratio.m和wine.csv——这不是调用一行fitctree就完事的封装函数，而是一套完整可调试、可打断点、可替换数据、可对比 ID3 的 C4.5 实现。它解决的不是“怎么画一棵树”，而是“为什么分裂节点必须用增益率而非信息增益”“连续属性如何二值化切分”“缺失值怎么参与划分”“后剪枝时验证集误差怎么算”。适合三类人：机器学习课设要交原创代码的学生、想搞清ClassificationTree底层逻辑的算法工程师、以及正在用 Matlab 做嵌入式模型部署（如 Simulink + HDL Coder）需明确控制分支条件的开发者。本篇不依赖 Statistics and Machine Learning Toolbox 的黑盒函数，所有熵计算、属性选择、树结构递归构建、预剪枝阈值设定、后剪枝回溯逻辑，全部用原生 Matlab 数组和结构体实现，且每步附可验证的中间输出。

2. C4.5 核心机制拆解：为什么增益率能防过拟合，以及 Matlab 如何高效计算它

C4.5 不是 ID3 的简单升级，它针对 ID3 的致命缺陷——对取值多的属性（如“身份证号”“时间戳”）天然偏好——引入了**增益率（Gain Ratio）**作为分裂标准。Matlab 没有内置gainratio函数，必须手动推导并避免浮点陷阱。我们先看数学本质，再落地到向量化代码。

2.1 增益率公式与 Matlab 向量化实现逻辑

ID3 使用信息增益 $Gain(S,A) = Info(S) - Info_A(S)$，但当属性 $A$ 取值过多时，$Info_A(S)$ 极小，导致 $Gain$ 虚高。C4.5 改用增益率：
$$ GainRatio(S,A) = \frac{Gain(S,A)}{SplitInfo(S,A)},\quad SplitInfo(S,A) = -\sum_{v \in Values(A)} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|} $$
关键点在于：$SplitInfo$ 是属性 $A$ 自身的熵，取值越分散，$SplitInfo$ 越大，从而压低增益率。Matlab 中不能直接用log2(0)，必须加 epsilon 防错；且Values(A)需用unique()提取，但要注意浮点连续属性需先离散化。

2.1.1 连续属性二值化切分：中位数 vs. 最优切分点

C4.5 对连续属性（如alcohol列）不直接枚举所有值，而是排序后取相邻值中点作为候选切分点，再选使增益率最大的那个。Matlab 实现如下：

function [best_split, best_gain_ratio] = find_best_continuous_split(X_col, y, epsilon) % X_col: n×1 连续特征列, y: n×1 标签列 [sorted_X, idx] = sort(X_col); sorted_y = y(idx); % 生成候选切分点：相邻值中点 candidates = (sorted_X(1:end-1) + sorted_X(2:end)) / 2; n_cand = length(candidates); gain_ratios = zeros(n_cand, 1); for i = 1:n_cand % 按 candidate 划分左右子集 left_mask = X_col <= candidates(i); right_mask = ~left_mask; if sum(left_mask) == 0 || sum(right_mask) == 0 gain_ratios(i) = -Inf; continue; end % 计算 Info(S), Info_A(S), SplitInfo(S,A) info_S = calc_entropy(y); info_A = (sum(left_mask)/numel(y)) * calc_entropy(y(left_mask)) ... + (sum(right_mask)/numel(y)) * calc_entropy(y(right_mask)); gain = info_S - info_A; % SplitInfo: 属性 A 的内在信息 p_left = sum(left_mask) / numel(y); p_right = 1 - p_left; split_info = -(p_left * log2(max(p_left, epsilon)) + p_right * log2(max(p_right, epsilon))); % 增益率，防除零 gain_ratios(i) = (split_info > epsilon) ? gain / split_info : -Inf; end [~, best_idx] = max(gain_ratios); best_split = candidates(best_idx); best_gain_ratio = gain_ratios(best_idx); end

提示：epsilon = 1e-12必须显式传入，否则log2(0)报Inf或NaN，导致max()失效。calc_entropy函数需用histcounts统计类别频次，再套用 $-\sum p_i \log_2 p_i$，不可用entropy()（那是图像处理工具箱的灰度熵）。

2.2 缺失值处理：C4.5 的加权分配策略

C4.5 不丢弃含缺失值的样本，而是将该样本按比例分配给所有分支。例如某节点有 100 个样本，其中 20 个age缺失，其余 80 个中age≤30占 40 个、age>30占 40 个，则缺失的 20 个样本以 0.5:0.5 权重分到左右子节点。Matlab 实现时，标签向量y需改为n×2矩阵：第一列为真实标签，第二列为权重（初始全 1），后续递归中权重会衰减。

2.2.1 权重更新与信息熵修正

% 在 build_tree.m 中，当遇到缺失值时： if any(isnan(X_col)) % 计算非缺失样本的分布比例 valid_mask = ~isnan(X_col); valid_X = X_col(valid_mask); valid_y = y(valid_mask, :); % y now has weight in column 2 % 获取最优切分（仅用 valid 样本） [best_split, ~] = find_best_continuous_split(valid_X, valid_y(:,1), eps); % 分配缺失样本：按左右子集在 valid 样本中的占比 left_valid = sum(valid_X <= best_split); right_valid = sum(valid_X > best_split); total_valid = left_valid + right_valid; left_weight_ratio = left_valid / total_valid; right_weight_ratio = right_valid / total_valid; % 构建带权重的子数据集 left_y = [valid_y(valid_X <= best_split, :); ... repmat([mode_y, 1*left_weight_ratio], sum(isnan(X_col)), 1)]; right_y = [valid_y(valid_X > best_split, :); ... repmat([mode_y, 1*right_weight_ratio], sum(isnan(X_col)), 1)]; else % 正常切分 end

注意：mode_y是当前节点多数类标签，用于缺失样本的伪标签填充。权重列（第 2 列）直接影响calc_entropy的计算——需改用加权熵：
$$Info(S) = -\sum_{i} \frac{\sum_{x\in S_i} w_x}{\sum_{x\in S} w_x} \log_2 \frac{\sum_{x\in S_i} w_x}{\sum_{x\in S} w_x}$$
因此calc_entropy必须接收权重向量，不能只传标签。

3. 从零构建决策树结构：递归生成、节点存储与预剪枝控制

C4.5 的树不是抽象概念，而是 Matlab 结构体数组或自定义 class。我们采用struct存储每个节点，字段包括feature_idx（分裂属性索引）、split_val（切分值，连续属性为数值，离散为类别名）、children（子节点 struct 数组）、class_label（叶节点预测类）、samples_count（加权样本数）。构建过程必须显式控制深度、最小样本数、增益率阈值。

3.1 树节点结构定义与初始化

function node = init_node() node.feature_idx = []; % 分裂属性列号，如 3 表示第 3 列 node.split_val = []; % 切分值，离散属性为 cellstr，连续为 scalar node.children = {}; % 子节点 struct cell array node.class_label = []; % 叶节点：预测类别 node.samples_count = 0; % 当前节点加权样本总数 node.is_leaf = false; % 是否为叶节点 end

3.2 递归建树主函数：预剪枝三重闸门

build_tree.m是核心，它接收数据矩阵X、标签y（含权重列）、当前深度depth、最大深度max_depth、最小样本数min_samples_split、增益率阈值min_gain_ratio。每次递归前检查三个终止条件：

function node = build_tree(X, y, depth, max_depth, min_samples_split, min_gain_ratio, epsilon) node = init_node(); node.samples_count = sum(y(:,2)); % 加权样本总数 % 闸门1：纯度检查 if numel(unique(y(:,1))) == 1 node.is_leaf = true; node.class_label = y(1,1); return; end % 闸门2：深度检查 if depth >= max_depth node.is_leaf = true; [node.class_label, ~] = mode(y(:,1), 'omitnan'); % 加权 mode 需另行实现 return; end % 闸门3：样本数检查 if node.samples_count < min_samples_split node.is_leaf = true; [node.class_label, ~] = mode(y(:,1), 'omitnan'); return; end % 寻找最优分裂属性 best_feat_idx = -1; best_gain_ratio = -Inf; best_split_val = []; for feat_idx = 1:size(X,2) X_col = X(:,feat_idx); if isnumeric(X_col) && ~all(isnan(X_col)) % 连续属性 [~, gr] = find_best_continuous_split(X_col, y, epsilon); else % 离散属性：枚举每个取值作为分支 gr = calc_discrete_gain_ratio(X_col, y, epsilon); end if gr > best_gain_ratio best_gain_ratio = gr; best_feat_idx = feat_idx; end end % 闸门4：增益率不足，强制设为叶节点 if best_gain_ratio < min_gain_ratio node.is_leaf = true; [node.class_label, ~] = mode(y(:,1), 'omitnan'); return; end % 执行分裂 node.feature_idx = best_feat_idx; X_col = X(:,best_feat_idx); if isnumeric(X_col) && ~all(isnan(X_col)) node.split_val = find_best_continuous_split(X_col, y, epsilon); % 按 split_val 划分左右子集... else % 离散属性：对每个 unique value 构建子节点... end end

提示：min_gain_ratio通常设为0.01~0.1。设太小导致过拟合，太大则树过浅。实测wine数据集（13 属性，178 样本）推荐min_gain_ratio=0.05，max_depth=8，min_samples_split=5。

3.3 离散属性分裂：避免ismember的向量化陷阱

对离散属性（如color列），C4.5 将每个唯一值作为一个分支。但 Matlab 的ismember在大数据量下慢，应改用accumarray或逻辑索引：

function gr = calc_discrete_gain_ratio(X_col, y, epsilon) % X_col: n×1 离散列，可能含 NaN [vals, ~, idx] = unique(X_col, 'stable'); valid_mask = ~isnan(X_col); valid_idx = idx(valid_mask); % 统计每个值的样本权重和 weights_per_val = accumarray(valid_idx, y(valid_mask,2), [numel(vals) 1]); total_weight = sum(y(:,2)); % 计算 SplitInfo p_vals = weights_per_val / total_weight; split_info = -sum(p_vals .* log2(max(p_vals, epsilon))); % 计算 Info_A info_A = 0; for i = 1:numel(vals) mask = (X_col == vals(i)) | isnan(X_col); % 缺失值也计入该分支 if sum(mask) > 0 sub_y = y(mask, :); info_A = info_A + (sum(sub_y(:,2))/total_weight) * calc_entropy(sub_y, epsilon); end end info_S = calc_entropy(y, epsilon); gain = info_S - info_A; gr = (split_info > epsilon) ? gain / split_info : -Inf; end

4. 后剪枝实现：用验证集误差驱动子树替换，Matlab 版 Reduced-Error Pruning

预剪枝靠阈值，后剪枝靠数据。C4.5 默认采用Reduced-Error Pruning：用独立验证集评估每个非叶节点，若将其替换为叶节点（即用该节点多数类预测）能使验证误差下降，则执行替换。这要求树结构支持“临时替换”和“误差回溯”。

4.1 验证集误差计算与节点替换逻辑

假设验证集为X_val,y_val（无权重列），需编写evaluate_tree_error函数，返回错误样本数。关键点在于：替换节点时，其所有后代节点被忽略，仅用该节点class_label预测整棵子树覆盖的验证样本。

function error_count = evaluate_tree_error(node, X_val, y_val, epsilon) if node.is_leaf pred = repmat(node.class_label, size(y_val,1), 1); error_count = sum(pred ~= y_val); return; end % 根据 node.split_val 划分验证集 X_col = X_val(:, node.feature_idx); if isnumeric(X_col) % 连续 left_mask = X_col <= node.split_val; right_mask = ~left_mask; else % 离散 left_mask = ismember(X_col, node.split_val); % node.split_val 为 cellstr right_mask = ~left_mask; end % 递归计算左右子树误差 error_count = 0; if ~isempty(node.children) && numel(node.children) >= 2 if any(left_mask) error_count = error_count + evaluate_tree_error(node.children{1}, X_val(left_mask,:), y_val(left_mask), epsilon); end if any(right_mask) error_count = error_count + evaluate_tree_error(node.children{2}, X_val(right_mask,:), y_val(right_mask), epsilon); end end end

4.2 后剪枝主循环：DFS 遍历 + 替换评估

function pruned_node = post_prune(node, X_val, y_val, alpha, epsilon) if node.is_leaf pruned_node = node; return; end % 先递归剪枝子树 for i = 1:numel(node.children) node.children{i} = post_prune(node.children{i}, X_val, y_val, alpha, epsilon); end % 计算当前子树在验证集上的误差 curr_error = evaluate_tree_error(node, X_val, y_val, epsilon); % 计算若将 node 替换为叶节点的误差（用 node.class_label 预测所有覆盖样本） % 需先获取 node 覆盖的验证样本索引 —— 这里简化：用训练时的样本分布近似 % 实际工程中应保存每个节点的样本索引掩码 % 为简化，我们假设 node.class_label 是训练集多数类，直接预测全部验证集 pred_all = repmat(node.class_label, size(y_val,1), 1); replace_error = sum(pred_all ~= y_val); % 若替换后误差更小，执行剪枝 if replace_error < curr_error node.is_leaf = true; node.children = {}; pruned_node = node; else pruned_node = node; end end

注意：真实场景中，node.class_label应基于验证集样本重新计算（即该节点覆盖的验证样本中多数类），而非训练集。这需要在建树时保存每个节点的样本索引，或在剪枝前做一次前向传播标记。本例为降低复杂度，采用训练集多数类近似，实际项目中务必补全。

5. 完整运行链路：从wine.csv加载、参数调优到可视化树结构

现在把所有模块串起来。以 UCI Wine 数据集为例（13 个化学指标，3 类葡萄酒），演示如何从原始 CSV 跑通 C4.5 全流程，并用plot函数绘制树结构。

5.1 数据加载与预处理：处理 CSV 中的逗号与空格

Wine 数据集常因 Excel 保存格式含多余空格，需清洗：

% 加载 wine.csv，第一列为标签，后13列为特征 data = readmatrix('wine.csv', 'Delimiter', ','); % 清洗：去除首尾空格，转换为 numeric data = cellfun(@(x) str2double(strtrim(x)), num2cell(data), 'UniformOutput', false); data = cell2mat(data); X = data(:, 2:end); % 特征 y = data(:, 1); % 标签（整数 1/2/3） % 划分训练集（80%）、验证集（20%） n = size(X,1); idx = randperm(n); train_idx = idx(1:round(0.8*n)); val_idx = idx(round(0.8*n)+1:end); X_train = X(train_idx, :); y_train = y(train_idx); X_val = X(val_idx, :); y_val = y(val_idx); % 添加权重列：y_train 从 n×1 变为 n×2 y_train = [y_train, ones(size(y_train))];

5.2 参数调优实验：网格搜索min_gain_ratio与max_depth

为找到最优超参，运行网格搜索：

min_gr_list = [0.01, 0.03, 0.05, 0.08, 0.1]; max_depth_list = [4, 6, 8, 10]; results = table('Size', [0 3], 'VariableTypes', {'double','double','double'}, ... 'VariableNames', {'MinGainRatio','MaxDepth','ValError'}); for gr = min_gr_list for depth = max_depth_list tree = build_tree(X_train, y_train, 0, depth, 5, gr, 1e-12); pruned_tree = post_prune(tree, X_val, y_val, 0.01, 1e-12); err = evaluate_tree_error(pruned_tree, X_val, y_val, 1e-12); results = [results; table(gr, depth, err)]; end end % 找最优组合 [~, best_idx] = min(results.ValError); best_gr = results.MinGainRatio(best_idx); best_depth = results.MaxDepth(best_idx); fprintf('Best: min_gain_ratio=%.3f, max_depth=%d, val_error=%.3f\n', best_gr, best_depth, results.ValError(best_idx));

5.3 可视化树结构：用plot和text手绘决策路径

Matlab 没有treeplot对 C4.5 的原生支持，我们用坐标计算手动绘制：

function plot_tree(node, x, y, dx, dy, level) if isempty(node) || ~isstruct(node) return; end % 绘制当前节点框 rectangle('Position', [x-0.5, y-0.2, 1, 0.4], 'FaceColor', 'w', 'EdgeColor', 'k'); if node.is_leaf text(x, y, sprintf('Class %d', node.class_label), 'HorizontalAlignment', 'center'); else feat_name = sprintf('Feature %d', node.feature_idx); if isnumeric(node.split_val) text(x, y, sprintf('%s ≤ %.2f', feat_name, node.split_val), 'HorizontalAlignment', 'center'); else text(x, y, sprintf('%s ∈ {%s}', feat_name, strjoin(node.split_val, ',')), 'HorizontalAlignment', 'center'); end end % 绘制子节点连线与递归 if ~node.is_leaf && ~isempty(node.children) n_children = numel(node.children); for i = 1:n_children child_x = x + (i-1)*dx - (n_children-1)*dx/2; child_y = y - dy; line([x, child_x], [y-0.2, child_y+0.2], 'Color', 'k'); plot_tree(node.children{i}, child_x, child_y, dx/1.5, dy*0.8, level+1); end end end % 调用 figure; plot_tree(pruned_tree, 0, 0, 4, 2, 0); axis equal off; title('C4.5 Decision Tree (Pruned)');

技巧：dx和dy控制树的横向/纵向间距，level用于动态缩放子树尺寸。实际项目中可导出为 PDF：print('-dpdf', 'c45_tree.pdf')。

本文还有配套的精品资源，点击获取