网站建设介绍怎么写,福建漳发建设有限公司网站,百度网络推广怎么做,百度网盘 做网站图床C4.5 是由 Ross Quinlan 提出的决策树算法#xff0c;是对 ID3 算法的改进版本。它在 ID3 的基础上#xff0c;解决了以下问题#xff1a;
处理连续型数据#xff1a;支持连续型特征#xff0c;能够通过划分点将连续特征离散化。处理缺失值#xff1a;能够在特征值缺失的…C4.5 是由 Ross Quinlan 提出的决策树算法是对 ID3 算法的改进版本。它在 ID3 的基础上解决了以下问题
处理连续型数据支持连续型特征能够通过划分点将连续特征离散化。处理缺失值能够在特征值缺失的情况下继续构建决策树。偏好多值特征的问题采用信息增益比Gain Ratio替代信息增益减少对多值特征的偏好。生成剪枝后的树通过后剪枝技术降低过拟合风险。 1. 核心改进
(1) 信息增益比
C4.5 使用**信息增益比Gain Ratio**代替 ID3 的信息增益来选择最优特征。
信息增益 IG(D, A) 分裂信息 SI(A) 其中 特征 AAA 的第 vvv 个取值的样本比例。 信息增益比 GR(D, A) 分裂信息 SI(A) 是一种归一化因子用于惩罚取值较多的特征降低它们被优先选择的可能性。 (2) 连续型特征处理
对连续特征C4.5 会尝试在特征值的每个分割点例如两个样本值之间的中点进行划分。对每个划分点计算信息增益比选择最佳划分点。
假设某连续特征 A 的值为 排序后尝试以下划分点
划分点 (3) 处理缺失值
对于缺失值C4.5 使用以下策略
在计算信息增益比时只考虑特征值非缺失的样本。当需要划分含有缺失值的样本时将这些样本按概率分配到各个子节点。 (4) 剪枝
C4.5 采用**后剪枝Post-Pruning**技术通过校验数据集评估剪枝后的树是否提高性能。剪枝的目标是降低过拟合风险增强模型泛化能力。 2. C4.5 算法流程
输入训练数据集 D、特征集 A。递归构造树 计算当前数据集 D 的信息熵 H(D)。对每个特征 A ∈ A 若 A 为离散特征计算信息增益比。若 A 为连续特征尝试每个划分点计算信息增益比。选择信息增益比最大的特征 作为当前节点的分裂特征。根据 的取值或划分点划分数据集 D。对每个子数据集递归构造子树。剪枝 基于校验集对生成的决策树进行剪枝移除不显著的分支。输出剪枝后的决策树。 3. 示例
数据示例
假设有以下训练数据集
天气温度湿度风力是否运动晴天30高弱否晴天32高强否阴天28高弱是雨天24正常弱是雨天20正常强否
目标构造决策树判断是否运动。
步骤 计算根节点的熵 对每个特征计算信息增益比 天气离散特征 计算天气的条件熵 。计算信息增益比 。 温度连续特征 尝试划分点272727、303030、333333。对每个划分点计算信息增益比选择最佳划分点。 湿度、风力 按相同方法计算。 选择信息增益比最大的特征作为分裂特征生成子节点。 对子节点递归分裂直至满足停止条件如样本类别纯度高或无特征可分。 后剪枝 对生成的树在校验集上进行性能评估剪去对性能贡献较小的分支。 4. 算法特点
优点
支持离散和连续特征适用范围更广。减少对多值特征的偏好提高选择的公平性。能处理缺失值增强算法的鲁棒性。剪枝减少过拟合提高泛化能力。
缺点
计算复杂度高特别是连续特征的划分点尝试增加了计算量。不支持大规模数据时的并行化。剪枝过程可能需要额外的校验集。 5. 代码实现
以下是一个简单的 Python 实现用于计算信息增益比并构造 C4.5 决策树
import numpy as np# 计算熵
def entropy(labels):total len(labels)counts {}for label in labels:counts[label] counts.get(label, 0) 1return -sum((count / total) * np.log2(count / total) for count in counts.values())# 计算信息增益比
def information_gain_ratio(data, labels, feature_index):total_entropy entropy(labels)feature_values [row[feature_index] for row in data]unique_values set(feature_values)split_info 0conditional_entropy 0for value in unique_values:subset [labels[i] for i in range(len(data)) if data[i][feature_index] value]proportion len(subset) / len(data)conditional_entropy proportion * entropy(subset)split_info - proportion * np.log2(proportion)info_gain total_entropy - conditional_entropyreturn info_gain / split_info if split_info ! 0 else 0# 示例数据
data [[晴天, 30, 高, 弱],[晴天, 32, 高, 强],[阴天, 28, 高, 弱],[雨天, 24, 正常, 弱],[雨天, 20, 正常, 强]
]
labels [否, 否, 是, 是, 否]# 特征索引天气、温度、湿度、风力
for i in range(4):print(fFeature {i}, Gain Ratio: {information_gain_ratio(data, labels, i):.4f})输出结果
Feature 0, Gain Ratio: 0.3751
Feature 1, Gain Ratio: 0.4182
Feature 2, Gain Ratio: 0.0206
Feature 3, Gain Ratio: 0.4325 6. 总结
C4.5 是 ID3 的改进版本针对实际问题的需求连续特征、缺失值、多值特征偏好等做了多项优化。尽管计算复杂度高但其广泛用于分类问题成为现代决策树算法的基础之一如 CART。
