前言

在上一篇文章中我们已经详细介绍了决策树模型，并且提到了ID3算法及其局限性，那么在本篇文章中，我们将会介绍基于ID3算法进行改良的C4.5算法以及决策树拟合度的优化问题。

1 C4.5 算法

C4.5 算法与 ID3 算法相似，C4.5 算法对 ID3 算法进行了改进，C4.5 在生成的过程中，用信息增益比准则来选择特征。

1.1 修改局部最优化条件

• 以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。
• 使用信息增益比（information gain ratio）可以对这一问题进行校正。

信息增益比定义为其信息增益与训练数据集关于某一特征的值的熵之比：$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$其中$$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}$$称为属性 a 的 "固有值“（intrinsic value）。

属性 a 的可能取值越多（即 V 越大），则 IV(a) 的值通常会越大。

IV 值会随着叶节点上样本量的变小而逐渐变大，也就是说一个特征属性中如果标签分类太多，每个叶子上的 IV 值就会非常大。

值得注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一种启发式：先从候选划分属性中找出信息增益高于平均水平的属性， 再从中选择增益率最高的。

我们可利用 Gain_ratio 代替 Gain 重新计算数据集中第 0 列的 Gain_ratio ，由于根据 accompany 字段切分后，2 个分支分别有 3 个和 2 个的样例数据，因此其 IV 指标计算过程如下：$$\begin{gathered} IV{(}^{\prime }accompan{y}^{\prime })=-\frac{3}{5}lo{g}_2\frac{3}{5}-\frac{2}{5}lo{g}_2\frac{2}{5}=0.971 \\ Gain\_ratio{(}^{\prime }accompan{y}^{\prime })=\frac{Gain{(}^{\prime }accompan{y}^{\prime })}{IV{(}^{\prime }accompan{y}^{\prime })}=\frac{0.42}{0.971}=0.432 \end{gathered}$$然后可进一步计算其他各字段的 Gain_ratio ，并选取 Gain_ratio 最大的字段进行切分。

1.2 连续变量处理手段

在 C4.5 中，同样还增加了针对连续变量的处理手段。如果输入特征字段是连续型变量，则算法首先会对这一列数进行从小到大的排序，然后选取相邻的两个数的中间数作为切分数据集的备选点，若一个连续变量有 N 个值，则在 C4.5 的处理过程中将产生 N-1 个备选切分点，并且每个切分点都代表着一种二叉树的切分方案，例如：

这里需要注意的是，此时针对连续变量的处理并非是将其转化为一个拥有 N-1 个分类水平的分类变量，而是将其转化成了 N-1 个二分方案，而在进行下一次的切分过程中，这 N-1 个方案都要单独带入考虑，其中每一个切分方案和一个离散变量的地位均相同（一个离散变量就是一个单独的多路切分方案）。 例如有如下数据集，数据集中只有两个字段，第一行代表年龄，是特征变量，第二行代表性别，是目标字段，则对年龄这一连续变量的切分方案如图所示：

从上述论述能够看出，在对于包含连续变量的数据集进行树模型构建的过程中要消耗更多的运算资源。但与此同时，我们也会发现，当连续变量的某中间点参与到决策树的二分过程中，往往代表该点对于最终分类结果有较大影响，这也为我们连续变量的分箱压缩提供了指导性意见。 例如上述案例，若要对Age 列进行压缩，则可考虑使用 36.5 对其进行分箱，则分箱结果对于性别这一目标字段仍然具有较好的分类效果，这也是决策树的最常见用途之一，也是最重要的模型指导分箱的方法。

下面附上使用C4.5算法建立决策树的Python代码：

import numpy as np
import pandas as pd

# 定义信息熵
def calEnt(dataSet):
    n = dataSet.shape[0]                                     # 数据集总行数
    iset = dataSet.iloc[:,-1].value_counts()                 # 统计标签的所有类别
    p = iset/n                                               # 统计每一类标签所占比  
    ent = (-p*np.log2(p)).sum()                              # 计算信息熵
    return ent

# 选择最优的列进行切分
def bestSplit2(dataSet):
    baseEnt = calEnt(dataSet)                                # 计算原始熵
    bestGainRatio = 0                                       # 初始化信息增益
    axis = -1                                                # 初始化最佳切分列，标签列
    
    for i in range(dataSet.shape[1]-1):                      # 对特征的每一列进行循环
        levels= dataSet.iloc[:,i].value_counts().index       # 提取出当前列的所有取值
        ents = 0                                             # 初始化子节点的信息熵
        IV = 0                                               # 初始化子节点的属性分裂信息度量
        
        for j in levels:                                     # 对当前列的每一个取值进行循环
            childSet = dataSet[dataSet.iloc[:,i]==j]         # 某一个子节点的dataframe
            ent = calEnt(childSet)                           # 计算某一个子节点的信息熵
            p = childSet.shape[0]/dataSet.shape[0]           # 计算当前取值的概率
            ents += p*ent                                    # 计算当前列的信息熵
            IV += -(p*np.log(p))                             # 计算当前列的分裂信息度量
        print('第列的信息熵为'.format(i,ents))
            
        infoGain = baseEnt-ents                              # 计算当前列的信息增益
        print('第列的信息增益为'.format(i,infoGain))
        
        gainRatio = infoGain / IV                           # 计算当前列的信息增益率
        print('第列的信息增益率为\\n'.format(i,gainRatio))
        
        if (gainRatio > bestGainRatio):
            bestGainRatio = gainRatio                      # 选择最大信息增益率
            axis = i                                         # 最大信息增益率所在列的索引
    print("第列为最优切分列\\n".format(axis))
    return axis

#为决策树进一步划分去做准备
def mySplit(dataSet,axis,value):
    col = dataSet.columns[axis]
    redataSet = dataSet.loc[dataSet[col]==value,:].drop(col,axis=1)
    return redataSet

"""
函数功能：基于最大信息增益率切分数据集，递归构建决策树
参数说明：
dataSet：原始数据集(最右一列是标签)
return：myTree：字典形式的树
"""
def createTree2(dataSet):
    featlist = list(dataSet.columns)                        # 提取出数据集所有的列
    classlist = dataSet.iloc[:,-1].value_counts()           # 获取最后一列类标签
    
    # 判断最多标签数目是否等于数据集行数，或者数据集是否只有一列
    if classlist[0]==dataSet.shape[0] or dataSet.shape[1] == 1:
        return classlist.index[0]                           # 如果是，返回类标签
   
    axis = bestSplit2(dataSet)                              # 确定出当前最佳切分列的索引
    bestfeat = featlist[axis]                               # 获取该索引对应的特征
    myTree = bestfeat:                                  # 采用字典嵌套的方式存储树信息
    del featlist[axis]                                      # 删除当前特征
    valuelist = set(dataSet.iloc[:,axis])                   # 提取最佳切分列所有属性值
    
    for value in valuelist:                                 # 对每一个属性值递归建树
        myTree[bestfeat][value] = createTree(mySplit(dataSet,axis,value))
    
    return myTree

row_data = '是否陪伴' :[0,0,0,1,1],
            '是否玩游戏':[1,1,0,1,1],
            '渣男' :['是','是','不是','不是','不是']
dataSet = pd.DataFrame(row_data) 

createTree2(dataSet)

运行结果如下：

第0列的信息熵为0.5509775004326937
第0列的信息增益为0.4199730940219749
第0列的信息增益率为0.6240205253621535

第1列的信息熵为0.8
第1列的信息增益为0.17095059445466854
第1列的信息增益率为0.3416262320352702

第0列为最优切分列

第0列的信息熵为0.0
第0列的信息增益为0.9182958340544896
第0列的信息增益率为1.4426950408889636

第0列为最优切分列

‘是否陪伴’: 0: ‘是否玩游戏’: 0: ‘不是’, 1: ‘是’, 1: ‘不是’

2 决策树的拟合度优化

在实际操作过程中，我们判断模型是否过拟合往往是从模型训练误差和泛化误差的比较中得出，而采用我们之前介绍的交叉验证可得到较为准确的训练误差和泛化误差，二者结合使用就能判断模型是否存在过拟合现象。虽然我们之前举例时并没有对数据集进行切分，但任何有监督学习算法建模过程中都需要进行训练集和测试集的划分，决策树也不例外，进而我们可用交叉验证计算训练误差和泛化误差，进而判断决策树是否存在过拟合。这是一套通用地判断有监督学习算法是否过拟合的方法，同时通用的方法中还有更高级的方法，我们将在后续进行逐步介绍。但对于决策树而言，有一套决策树独有的防止过拟合的解决方案——剪枝。

2.1 决策树剪枝

所谓剪枝是指在决策树中去除部分叶节点。

剪枝（Pruning）主要是用来防止过拟合，对于一般的数据集如果总是追求 ”纯的“ 叶节点，或者观测数较小的叶节点，很容易使得树过于庞杂，尤其是存在可以反复使用的连续变量的时候，此时就需要主动去掉一些分支来降低过拟合的风险。

常见的剪枝策略有 ”预剪枝“（Pre-Pruning）和 ”后剪枝“（Post-Pruning）。

• 预剪枝：在决策树生成的过程中，对每个节点在划分前先进行估计，如果当前的节点划分不能带来决策树泛化性能（预测性能）的提升，则停止划分并且将当前节点标记为叶节点。
• 后剪枝：先训练生成一颗完整的树，自底向上对非叶节点进行考察，如果将该节点对应的子树替换为叶节点能带来决策树泛化能力的提升，则将该子树替换为叶节点。

\\	预剪枝	后剪枝
分支数	很多分支都没有展开	保留了更多分支
拟合风险	降低过拟合风险，但是由于基于“贪心”算法的本质禁止后续分支展开，可能会导致模型欠拟合。	先生存决策树，自下而上逐一考察，欠拟合风险小，泛化能力更强
时间开销	训练开销和测试开销降低	后剪枝是从底往上进行裁剪的，因此其训练时间开销相对较大。

2.2 CART 算法

CART：分类回归树（Classification and Regression Tree）

• 分裂过程是一个二叉递归划分过程
• CART 预测变量 x 的类型既可以是连续型变量也可以是分类型变量
• 数据应以其原始形式处理，不需要离散化
• 用于数值型预测时，并没有使用回归，而是基于到达叶节点的案例的平均值做出预测

2.2.1 分裂准则

二叉递归划分：条件成立向左，反之向右

• 对于连续变量：条件是属性小于等于最优分裂点
• 对于分类变量：条件是属性属于若干类

2.2.2 二叉分裂的优点

相比多路分裂导致数据碎片化的速度慢，允许在一个属性上重复分裂，即可以在一个属性上产生足够多的分裂。两路分裂带来的树预测性能提升足以弥补其相应的树易读性损失。

对于属性不同的被预测变量 y 分裂准则不同：

• 分类树：Gini 准则。与之前的信息增益很类似，Gini 系数度量一个节点的不纯度。
• 回归树：一种常见的分割标准是标准偏差减少（Standard Deviation Reduction, SDR），类似于最小均方误差 LS（least squares，预测错误的平方和）准则。

2.2.3 利用测试集进行剪枝

简单讨论 CART 算法剪枝过程，该过程也是测试集用于修正模型的最佳体现。例如，有如下在训练集中训练得到的树模型，黑色数字表示训练集上的分类情况，红色数字表示模型作用于验证集上的分类情况。

则 CART 算法利用验证集剪枝的过程如下：

• 判断每个叶节点在验证集上的错误率：
• 节点 4 的错误率$e(4)=\frac{1}{3}$
• 节点 5 的错误率$e(5)=1$
• 节点 6 的错误率$e(6)=1$
• 节点 7 的错误率为$e(7)=\frac{4}{9}$

计算子节点总加权平均错误率并和父节点进行比较，加权方法就是乘以该节点样本量占父节点样本总量的百分比（测试集）：

如节点 2 的错误率为$查看详情$

梦开始的地方，从最小二乘法开始学机器学习(代码片段)

梦开始的地方，从最小二乘法开始学机器学习从这篇博客开始，我们将逐步实现不同的机器学习代码，以此来深入学习了解不同的机器学习背后的原理~文章目录梦开始的地方，从最小二乘法开始学机器学习00.参考... 查看详情

梦开始的地方，从最小二乘法开始学机器学习(代码片段)

梦开始的地方，从最小二乘法开始学机器学习从这篇博客开始，我们将逐步实现不同的机器学习代码，以此来深入学习了解不同的机器学习背后的原理~文章目录梦开始的地方，从最小二乘法开始学机器学习00.参考... 查看详情

机器学习的常用方法都有哪些？

参考技术A梯度下降是非常常用的优化算法。作为机器学习的基础知识，这是一个必须要掌握的算法。借助本文，让我们来一起详细了解一下这个算法。前言本文的代码可以到我的Github上获取：https://github.com/paulQuei/gradient_descent本... 查看详情

什么是自动机器学习？它有哪些用处？

随着人工智能的技术的崛起，深度学习的概念开始流行起来，那么谈到深度学习就不得不提自动机器学习。可能还有许多人会问：什么是自动机器学习？它有哪些用处？下面就我们一起了解自动机器学习吧ÿ... 查看详情

什么是自动机器学习？它有哪些用处？

随着人工智能的技术的崛起，深度学习的概念开始流行起来，那么谈到深度学习就不得不提自动机器学习。可能还有许多人会问：什么是自动机器学习？它有哪些用处？下面就我们一起了解自动机器学习吧ÿ... 查看详情

什么是自动机器学习？它有哪些用处？

随着人工智能的技术的崛起，深度学习的概念开始流行起来，那么谈到深度学习就不得不提自动机器学习。可能还有许多人会问：什么是自动机器学习？它有哪些用处？下面就我们一起了解自动机器学习吧ÿ... 查看详情

什么是自动机器学习？它有哪些用处？

随着人工智能的技术的崛起，深度学习的概念开始流行起来，那么谈到深度学习就不得不提自动机器学习。可能还有许多人会问：什么是自动机器学习？它有哪些用处？下面就我们一起了解自动机器学习吧ÿ... 查看详情

机器学习中都有哪些重要的优化算法？

梯度下降是非常常用的优化算法。作为机器学习的基础知识，这是一个必须要掌握的算法。借助本文，让我们来一起详细了解一下这个算法。前言本文的代码可以到我的Github上获取：https://github.com/paulQuei/gradient_descent本文的算法... 查看详情

机器学习（05）——主要概念理解(代码片段)

机器学习的专业术语非常多，不需要一开始理解所有的专业术语，这些术语会随着对机器学习的深入，会慢慢理解，水到渠成。不过在学习的过程中，有一些概念必须要了解，有助于后续的学习与理解，需要了解的核心概念有：... 查看详情

机器学习面试总结————

目录1、使用机器学习模型时，一般怎么处理数据集2、什么是训练误差和测试误差3、什么是过拟合与欠拟合?怎么解决4、机器学习当中的回归模型有哪些5、机器学习当中的分类模型有哪些6、回归和分类模型的评价指标都有哪... 查看详情

机器学习中用来防止过拟合的方法有哪些？

...训练集上。所以，必须要解决过拟合问题。为什么在机器学习中比较常见？这是因为机器学习算法为了满足尽可能复杂的任务，其模型的拟合能力一般远远高于问题复杂度，也就是说，机器学习算法有「拟合出正确规则的前提下... 查看详情

机器学习之随机森林

...大家想学人工智能的话，那么就一定不能够忽视有关机器学习的内容。这时候就会有人问，什么是机器学习？所谓机器学习就是一门多领域交叉学科，涉及概率论、统计学、逼近论等多门学科。机器学习是专门研究计算机怎样模... 查看详情

实时机器学习是什么，面临哪些挑战？

  最近能够随数据获取实时调整模型的实时机器学习，正在成为媒体技术领域的新“网红”。曾经连续两年，都被FTI评为传媒业的重要技术趋势之一，与自然语言理解NLU、机器阅读理解MRC、音视频算法等共享金字塔顶端的... 查看详情

机器学习工程师必备，一本专门讲解机器学习工程实践的书

...机器学习精讲》[2]（TheHundred-PageMachineLearningBook）开始学习，然后再转向本书。本书的目标读者是倾向于机器学习工程角色的数据分析师、希望让工作更有条理的机器学习工程师、机器学习工程专业的学生，以及正... 查看详情

6分钟了解所有机器学习模型

所有机器学习模型都可以分为有监督的或无监督的。如果模型是监督模型，则将其再分类为回归模型或分类模型。我们将介绍这些术语的含义以及下面每个类别中对应的模型。监督学习模型监督学习涉及基于示例输入-输出对学... 查看详情

机器学习中，有哪些特征选择的工程方法？

机器学习中，有哪些特征选择的工程方法？数据和特征决定了机器学习的上限，而模型和算法调参只是逼近这个上限而已。0，特征本身是否具有基础的表征能力或者判别性，例如方差筛选法。方差是衡量一个变量的离散程度(即... 查看详情

为机器学习处理图像

...hinelearning【发布时间】：2019-05-0614:50:28【问题描述】：我开始为一个项目做医学图像分析。在这个项目中，我有人类肾脏有结石和无结石的图像。目的是预测给定的新图像是否有石头。我选择了KNN分类器模型进行分类，但我不了... 查看详情