C4.5 算法

定义

C4.5 是澳大利亚学者 Ross Quinlan 于 1993 年发布的决策树算法,是其早期 ID3 算法(1986)的系统性改进,在 2006 年 IEEE 数据挖掘国际会议评选的"数据挖掘十大算法"中位列第一。

对 ID3 的改进

ID3 使用信息增益选择分裂特征,天然偏向取值数目多的特征;C4.5 改用增益率(gain ratio),以特征自身的分裂信息作归一化来抑制该偏差。此外,C4.5 支持连续特征(自动寻找最优二分阈值)、能处理缺失值(按比例分配样本),并引入基于悲观误差估计的后剪枝以缓解过拟合,还可将树转化为规则集。

后续

Quinlan 后来推出商业版本 C5.0,速度与内存效率更高并支持 Boosting。

意义

C4.5 与 CART 共同定义了经典决策树的技术形态,是理解树模型演化脉络的关键节点。