C4.5算法原理

C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进，用信息增益比来选择特征。
信息增益比的公式如下图所示：

$I_R(Y,X)=\frac{I(Y,X)}{H_X(Y)}$

• 输入: 训练数据集 $D$，特征集 $A$,阈值 $\epsilon$
• 输出: 决策树T

1. 如果 $D$中所有实例属于同一类 $C_k$，则置 $T$为单节点树，并将 $C_k$作为该节点的类，返回 $T$.
2. 如果 $A=\emptyset$,则置T为单节点树，并将D中实例数最大的类 $C_k$作为该节点最大的类，返回 $T$.
3. 否则，按上式计算 $A$中各特征的对 $D$ 的信息增益比，选择信息增益比最大的特征 $A_g$.
4. 如果 $A_g$的信息增益比小于阈值 $\epsilon$，则置T为单结点树，并将 $D$中实例数最大的类 $C_k$作为该结点的类，返回 $T$.
5. 否则，对 $A_g$的每一可能值 $a_i$,依 $A_g=a_i$将 $D$分割为子集若干非空 $D_i$，将 $D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $T$，返回 $T$.
6. 对结点 $i$,以 $D_i$为训练集，以 $A-{A_g}$为特征集，递归地调用1-5步，得到子树 $T_i$,返回 $T_i$.

代码实现

python
Implementation of C4.5 algorithm in python.

Java http://weka.sourceforge.net/doc.dev/weka/classifiers/trees/J48.html

参考资料

机器学习之决策树（Decision Tree）及其 Python 代码实现