算法能够应对离散的描述属性——参照tinyxml指南[中文版]

第11章 决策树与神经网络 11.1 理解决策树 决策树方法在分类、预测、规则提取等领域有着广泛应用。在 20 世纪 70 年代后期和 80 年代初期，机器学习研究者 J.Ross Quinilan 提出了 ID3[5-2]算法以后，决策树在机器学习、 数据挖掘邻域得到极大的发展。Quinilan 后来又提出了 C4.5，成为新的监督学习算法。1984 年几位统计学家提出了 CART 分类算法。ID3 和 ART 算法大约同时被提出，但都是采用类 似的方法从训练样本中学习决策树。 决策树是一树状结构，它的每一个叶节点对应着一个分类，非叶节点对应着在某个属性 上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。对于非纯的叶节点，多 数类的标号给出到达这个节点的样本所属的类。构造决策树的核心问题是在每一步如何选择 适当的属性对样本做拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策 树是一个自上而下，分而治之的过程。 常用的决策树算法见表 11-1。 表 11-1 决策树算法分类 决策树算法 算法描述 ID3 算法 其核心是在决策树的各级节点上，使用信息增益方法作为属性的选 择标准，来帮助确定生成每个节点时所应采用的合适属性。 C4.5 算法 C4.5 决策树生成算法相对于 ID3 算法的重要改进是使用信息增益率 来选择节点属性。C4.5 算法可以克服 ID3 算法存在的不足：ID3 算 法只适用于离散的描述属性，而 C4.5 算法既能够处理离散的描述属 性，也可以处理连续的描述属性。 CART 算法 CART 决策树是一种十分有效的非参数分类和回归方法，通过构建 树、修剪树、评估树来构建一个二叉树。当终结点是连续变量时， 该树为回归树；当终结点是分类变量，该树为分类树。 本节将详细介绍 ID3 算法，也是最经典的决策树分类算法。 1. ID3 算法简介及基本原理 ID3 算法基于信息熵来选择最佳测试属性。它选择当前样本集中具有最大信息增益值的