基于MATLAB的C4.5决策树分类算法与后剪枝优化

资 源 简 介

本项目旨在在MATLAB环境下完整复现并优化经典的C4.5决策树算法。C4.5算法作为ID3算法的改进版，克服了原算法倾向于选择取值较多属性的缺陷。本项目的主要功能包括：1. 数据预处理功能，能够自动读取CSV或MAT格式的数据集，识别特征类型（连续型或离散型），并包含针对缺失数据的填充或忽略处理机制；2. 核心构建功能，利用信息增益率（Information Gain Ratio）作为属性选择标准，递归地构建决策树节点，同时针对连续属性实现基于二分法的最佳分裂点计算；3. 剪枝优化功能，在树构建完成后执行后剪枝（Post-Pruning）操作（如悲观剪枝），以降低模型复杂度，防止过拟合，提升模型在未知数据上的泛化能力；4. 分类预测功能，能够将训练好的决策树模型应用于测试数据集，输出预测的类别标签；5. 结果评估与可视化功能，通过计算混淆矩阵、准确率、精确率和召回率来量化模型性能，并利用MATLAB绘图工具将最终生成的决策树结构以图形化方式展示，清晰呈现决策规则路径。

详 情 说 明

基于MATLAB的C4.5决策树分类算法设计与实现

项目介绍

本项目是在MATLAB环境下对经典的C4.5决策树分类算法的完整复现与优化。C4.5算法作为ID3算法的重要改进版本，通过引入信息增益率（Information Gain Ratio）解决了属性选择的偏差问题，并增加了对连续属性和缺失值的处理能力。本项目代码集成了数据模拟、预处理、模型构建、悲观剪枝优化以及结果评估的全流程，旨在展示C4.5算法的核心逻辑与实现细节。

功能特性

• 混合类型数据处理：支持同时处理连续型特征（如物理测量值）和离散型特征（如颜色标签）。
• 缺失值自动填充：内置鲁棒的预处理机制，能够识别数据中的NaN值，并根据特征类型自动选择均值或众数进行填充。
• 连续属性二分处理：针对连续特征，算法自动排序并计算相邻值的中间点，寻找最佳分裂阈值，实现二叉分裂。
• 信息增益率选择：采用信息增益率作为分裂标准，避免了ID3算法倾向于选择取值较多属性的问题。
• 悲观剪枝策略：实现了后剪枝（Post-Pruning）逻辑，引入惩罚因子以评估叶节点与子树的误差，防止模型过拟合。
• 全流程评估：包含从数据生成、训练测试分割、未剪枝模型评估到剪枝后模型评估的完整逻辑。

系统要求

• MATLAB R2016b 或更高版本
• Statistics and Machine Learning Toolbox（用于cvpartition等辅助功能）

使用方法

直接运行主函数 main 即可执行整个流程。程序将自动完成以下步骤：

1. 初始化随机种子以确保结果可复现。
2. 生成包含200个样本、4个特征（3个连续，1个离散）的模拟数据集，并人为引入缺失值。
3. 对数据进行预处理及7:3的训练集与测试集划分。
4. 构建未剪枝的C4.5决策树模型并评估。
5. 执行悲观剪枝操作优化树结构。
6. 评估剪枝后的模型并绘制树结构图。

核心算法与实现细节

本项目在一个脚本中实现了C4.5算法的所有关键组件，具体实现逻辑如下：

1. 数据生成与预处理

程序首先生成模拟数据，包含3列连续特征和1列离散特征。为了模拟真实环境，代码随机将部分数据置为NaN。

• 处理逻辑：通过 handleMissingValues 函数遍历数据集。对于离散特征（由索引指定），计算非空数据的众数进行填充；对于连续特征，计算非空数据的均值进行填充。同时记录填充值，确保测试集使用训练集的统计量进行预处理（applyMissingValues），防止数据泄露。

2. C4.5 决策树构建 (C45BuildTree)

这是算法的核心递归函数。

• 停止条件：当样本全属同一类别、特征集为空或无法产生正向增益时，生成叶节点。
• 递归分裂：

* 调用 chooseBestAttribute 计算所有特征的信息增益率。 * 若被选中的是连续特征，采用二分法（Binary Split），寻找最佳分割点，将数据分为“<=”和“>”两部分递归构建。 * 若被选中的是离散特征，采用多叉分裂，根据该特征的所有唯一取值生成对应的子节点。

3. 属性选择与信息增益率 (chooseBestAttribute)

该函数负责评估每个特征的重要性。

• 熵计算：通过 calcEntropy 函数利用直方图统计计算样本集合的香农熵。
• 连续特征处理 (calcGainContinuous)：对特征值进行排序，计算相邻唯一值的中间点作为候选分裂点。算法遍历所有候选点，计算划分后的条件熵和分裂信息（Split Info），进而得出信息增益率。
• 离散特征处理 (calcGainDiscrete)：直接计算各类别分支的加权熵和分裂信息。
• 增益率公式：GainRatio = Gain / SplitInfo。程序包含防止SplitInfo为0的处理机制。

4. 悲观剪枝 (pruneTreePessimistic)

实现了基于C4.5规则的悲观剪枝（Pessimistic Pruning），采用自底向上的递归策略。

• 误差估算：

* 子树误差：计算当前节点作为子树时，其所有叶节点的分类错误数总和，并加上惩罚项（0.5 * 叶子节点数）。 * 叶化误差：估算若将当前节点强制变为叶节点（取多数类），其产生的分类错误数，同样加上惩罚项（0.5）。

• 剪枝决策：如果“叶化后的悲观误差”小于或等于“保留子树的悲观误差”，则执行剪枝操作，将该子树替换为单个叶节点。这种方法不依赖验证集，利用训练数据自身的统计特性来控制模型复杂度。

5. 模型评估与可视化

虽然主流程中调用了预测和可视化函数，但代码的核心逻辑集中在树的构建与优化上。主流程清晰地对比了“未剪枝”与“已剪枝”模型在测试集上的表现，用于验证剪枝操作对泛化能力的提升。

--- *注意：本文档基于提供的 main.m 源代码内容生成。代码中包含了详细的算法实现，包括针对连续值的二分查找优化和缺失值填补策略。*