C4.5算法

C4.5算法原理

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

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

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

展开全文
相关主题
Top
微信扫码咨询专知VIP会员