决策树之C4.5的生成算法

    本文主要参考李航老师的《统计学习方法》一书，如有不妥之处，欢迎指出。

    上篇文章介绍了ID3算法，其实C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。相比于ID3是用信息增益来选择特征，C4.5则是利用信息增益比来选择特征。

    信息增益比：特征A对于训练数据集D的信息增益比定义为其信息增益g(D,A)与训练数据集D的经验熵H(D)之比：

    C4.5的生成算法：

    输入：训练数据集D，特征集A，阈值；

    输出：决策树T

    (1)如果D中所有实例属于同一类Ck，则置T为单结点树，并将Ck作为该节点的类，返回T；

    (2)如果A=∅，则置T为单结点树，并将D中实例数最大的类Ck作为该节点的类，返回T；

    (3)否则，按上式计算A中个特征对D的信息增益比，选择信息增益比最大的特征Ag；

    (4)如果Ag的信息增益比小于阈值，则置T为单结点树，并将D中实例数最大的类Ck作为该节点的类，返回T；

    (5)否则，对Ag的每一可能值ai，依Ag=ai将D分割为子集若干非空Di，将Di中实例数最大的类作为标记，构建子结点，由结点及其子结点构成数T，返回T；

    (6)对结点i，以Di为训练集，以A-{Ag}为特征集，递归地调用(1)~(5)步，返回字数Tj，返回Tj。