8.2 基于C4.5算法的决策树

C4.5是J.Ross Quinlan基于ID3算法改进后得到的另一个分类决策树算法。C4.5算法继承了ID3算法的优点，且改进后的算法产生的分类规则易于理解，准确率高。同时，该算法也存在一些缺点，如算法效率低，只适合于能驻留于内存的数据集。

改进：

1、用信息增益率来选择属性，客服了ID3算法选择属性时偏向选择取值多的属性的不足。

2、在决策树构造过程中进行剪枝，不考虑某些具有很少元素结点。

3、能够完成对连续属性的离散化处理。

4、能够对不完整数据进行处理。

信息增益率：

V表示属性集合A中的一个属性的全部取值；

1、计算出样本集合D的信息熵。

2、对属性集A中的每个属性分别计算信息熵。

3、根据步骤2中计算出的数据，计算选择第一个根结点所依赖的信息增益值Gain(V)。

4、计算分裂信息度量H(V)。

5、利用公式IGR(V)=Gain(V)H(V)计算信息增益率。