决策树C4.5连续属性分割阈值算法改进及其应用

姚亚夫，邢留涛

(中南大学 机电工程学院，湖南 长沙，410083)

分类问题是数据挖掘领域中研究和应用最为广泛的技术之一。近年来，分类问题在许多行业和领域都有广泛的应用[1]，如何更精确、更有效地分类一直是广大科研工作者的目标。决策树以其预测准确率高、稳定性好、直观易懂等特点[2-4]，得到广泛的应用。目前，构造决策树的算法比较多[5-6]，用不同的算法可以构造出不同的决策树，其性能也不尽相同，决策树的构造通常包含 2个重要步骤[7]：生成决策树和决策树的剪枝。每个步骤都有不同的方法，相应地就有各种不同的决策树生成和剪枝算法，最早的决策树算法是由 Hunt等[8]于 1966年提出的 CLS(concept learning system)。ID3算法[9]和C4.5算法[10]是目前最具影响的决策树算法,已广泛应用于数据分类领域。C4.5算法是在ID3算法的基础上改进过来的，不仅可以处理离散型描述属性，还可以处理连续性属性。C4.5算法采用信息增益率作为选择分枝属性的标准，弥补了 ID3算法在使用信息增益选择分枝属性时偏向于取值较多的属性的缺陷，但C4.5算法也有一些缺陷[11]。本文作者研究C4.5算法中的连续性属性离散化技术，并提出了改进算法—局部择优法。将改进C4.5算法应用于行人和车辆模式识别，并对改进C4.5分类器与K-均值分类器以及传统C4.5分类器的分类性能进行比较。

1 C4.5算法

作为ID3算法的改进算法，C4.5算法克服了ID3算法的两大缺点：(1) ID3算法使用信息增益作为评价标准来选择根节点和各内部节点中的分枝属性，信息增益的缺点是倾向于选择取值较多的属性，在某些情况下这类属性可能不会提供太多有价值的信息，而C4.5算法采用信息增益率作为评价标准，克服了ID3算法的这点不足；……