出，他引进信息论中的信息增益作为单一属性特征判别能力的度量，将建立决
策树的方法嵌在一个迭代的外壳之中。ID3 算法以信息熵作为目标评价函数，
采用自顶向下不可返回的策略，根据 Gain/Gain Ratio 来对被测属性进行选择，
搜索全部空间的一部分，力图使所做的测试数据最少，确保建立最简单的决策
树，基本公式如下：
ID3 算法提出时就是带有缺点的算法，在计算过程中偏向于选择取值较多
的属性，而在很多情况下取值较多的属性并不是最重要的属性，即按照使熵最
小的原则被 ID3 算法列为应该首先判断的属性在现实情况中却并不一定非常重
要。同时，ID3 算法不能处理具有连续值的属性，也不能处理具有缺失数据的
属性，在减少树的平均深度的过程中忽略了叶子数目的研究，其启发式函数并
不是最优的。用信息增益作为选择属性的标准存在一个假设，即训练子集中的
正、反例的比例应与实际问题中正、反例的比例一致，一般情况下很难保证这
两者的比例一致，这样计算训练集的信息增益就会存在偏差。
由于 ID3 算法在实际应用中存在一些问题，Ross Quinlan 在此基础上提出了
C4.5 算法，严格上说，C4.5 算法是 ID3 算法的一种改进。C4.5 算法继承了 ID3
算法的优点，用信息增益率来选择属性，克服用信息增益选择属性时偏向选择
取值多的属性的不足；在树构造过程中进行剪枝；加强了对于不完整数据的处
理能力；能够完成对连续属性的离散化处理。改进之后，C4.5 算法产生的分类
规则易于理解，准确率较高。然而，C4.5 算法只适合于能够驻留于内存的数据
集，当训练集大的无法在内存容纳时无法进行分类。在构造树的过程中，需要
评论15