柚子快报邀请码778899分享：02-22 决策树C4.5算法
目录决策树C4.5算法一、决策树C4.5算法学习目标二、决策树C4.5算法详解2.1 连续特征值离散化2.2 信息增益比2.3 剪枝2.4 特征值加权三、决策树C4.5算法流程3.1 输入3.2 输出3.3 流程四、决策树C4.5算法的优缺点4.1 优点4.2 缺点五、小结
人工智能从入门到放弃完整教程目录：https://www.cnblogs.com/nickchen121/p/11686958.html
决策树C4.5算法
为了解决决策树ID3算法的不足，ID3算法的作者昆兰基于它的不足改进了决策树ID3算法。但是可能会有人有疑问，既然上一个决策树算法叫做ID3算法，为什么改进版本不叫做ID4或者ID5呢？因为当时决策树过于火爆，有人二次创新把ID4、ID5都用掉了，由此作者另辟蹊径把ID3算法的改进版本称为C4算法，后来C4算法又一次升级便有了现在的C4.5算法。
一、决策树C4.5算法学习目标
使用C4.5算法对连续特征值离散化
信息增益比
使用C4.5算法对特征值加权
决策树C4.5算法步骤
决策树C4.5算法优缺点
二、决策树C4.5算法详解
上一次说到决策树ID3算法有4个缺点，而这次作者也是基于这4个缺点改进了算法，也就是现在的C4.5算法。
假设现有一个训练集\(D\)，特征集\(A\)，训练集中有\(m\)个样本，每个样本有\(n\)个特征，我们通过该训练集聊一聊作者对C4.5算法做了哪些改进。
2.1 连续特征值离散化
ID3算法的第一个缺点：没有考虑到连续值的情况。
假设现有一个特征\(F\)的特征值为连续值，从大到小排序为\(f_1,f_2,\ldots,f_m\)，C4.5算法对相邻样本间的特征值\(f_i,f_{i+1}\)取平均数，一共可以得到\(m-1\)个划分点，其中第\(j\)个划分点可以表示为
\[S_j = {\frac {f_i + f_{i+1}} {2}}
\]对于这\(m-1\)个划分点，分别计算以该点作为二元分类点的信息增益比，选择信息增益比最大的点作为该连续特征的二元离散分类点，把改点记作\(f_t\)，则特征值小于\(f_t\)的点记作\(c_1\)；特征值大于\(f_t\)的点记作\(c_2\)，这样就实现了连续特征值的离散化。
2.2 信息增益比
ID3算法的第二个缺点：以信息增益作为划分训练数据集的特征，存在于偏向于选择取值较多的特征的问题。
信息增益作为标准容易偏向于取值较多的特征，因此可以使用信息增益比作为划分节点的标准。信息增益比的概念已经在《熵和信息增益》一文中介绍过，这里只给出公式
\[g_R(D,A) = {\frac{g(D,A)}{H_A(D)}}
\]由于特征越多的特征对应的特征熵\(H_A(D)\)越大，则信息增益比\(g_R(D,A)\)则会变小，因此可以校正信息增益容易偏向于取值较多的特征的问题。
2.3 剪枝
ID3算法的第三个缺点：没有考虑过拟合问题。
决策树一般采用剪枝的方法解决过拟合问题，剪枝的具体思路将在《CART树》一文中细讲。
2.4 特征值加权
ID3算法的第四个缺点：没有考虑特征中含有缺失值的情况。
假设某个特征\(F\)有2个特征值\(f_1,f_2\)，先设定缺失\(F\)特征的样本\(D_i\)的关于特征\(F\)的特征值权重都为1，即\(f_1\)和\(f_2\)。假设\(2\)个特征值对应的无缺失值的样本个数为\(3\)和\(5\)，现在把特征值\(f_1,f_2\)重新划入样本\(D_i\)中，在样本\(D_i\)中\(f_1\)的权重调节为\({\frac{3}{8}}\)，\(f_2\)的权重调节为\({\frac{5}{8}}\)，即样本\(D_i\)的特征\(F\)的特征值为\({\frac{3}{8}}*f_1和{\frac{5}{8}}*f_2\)。
计算样本\(D_i\)的特征\(F\)的信息增益比的时候，及计算\({\frac{3}{8}}*f_1\)和\({\frac{5}{8}}*f_2\)的信息增益比。
三、决策树C4.5算法流程
3.1 输入
假设现有一个训练集\(D\)，特征集\(A\)，阈值\(\epsilon\)。
3.2 输出
C4.5算法决策树。
3.3 流程
初始化信息增益的阈值\(\epsilon\)
如果\(D\)中的所有样本都属于同一类\(C_k\)，则返回单节点树\(T\)，标记类别为\(C_k\)
如果\(A\)为空集，则返回单节点树\(T\)，标记类别为\(D\)中样本数最大的类\(C_k\)
计算\(A\)中各个特征对输出\(D\)的信息增益比，选择信息增益比最大的\(A_g\)
如果\(A_g\)小于阈值\(\epsilon\)，则返回单节点数\(T\)，标记类别为\(D\)中样本数最大的类\(C_k\)
如果\(A_g\)大于阈值\(\epsilon\)，则按照特征\(A_g\)的不同取值\(A_{g_i}\)把\(D\)分割成若干个子集\(D_i\)，每个子集生成一个子节点，子节点对应特征值为\(A_{g_i}\)，递归调用\(2-6\)步，得到子树\(T_i\)并返回
四、决策树C4.5算法的优缺点
4.1 优点
理论清晰，方法简单
学习能力强
4.2 缺点
只能用于分类
C4.5算法由于使用了熵的概念，即决策树的生成需要大量的熵值计算，并且如果特征值为连续值，还需要进行排序运算
使用模型较为复杂的多叉树结构
五、小结
决策树C4.5算法流程上和决策树ID3算法大相径庭，只是在决策树ID3算法上的某一步流程进行了优化，总而言之，它这种处理方式还是治标不治本的，并且还是无法处理回归问题。
接下来我们将要将一个改革意义的决策树，目前scikit-learn算法中以及集成学习中都使用该树作为目标决策树，即决策树CART算法。
柚子快报邀请码778899分享：02-22 决策树C4.5算法
相关链接
发表评论