摘要: 本部分对决策树几种算法的原理及算法过程进行简要介绍, 然后编写程序实现决策树算法, 再根据 Python 自带机器学习包实现决策树算法, 最后从决策树引申至集成学习相关内容.
1. 决策树
决策树作为一种常见的有监督学习算法, 在机器学习领域通常有着不错的表现, 决策树在生活中决策去做某件事时, 会根据自己的经验考虑到多种因素, 那么在程序逻辑中使用 if~else 的堆叠, 决定最终结果的过程其实就算是决策树的一种体现, 如下图(举个不太恰当的例子). 学术一点来说, 决策树就是根据以往发生的事的概率, 来评估风险, 作出决策, 通常根据以往事件发生的情况来构建的一种树形图.
构建决策树依据的是由概率所表示的数据的 "混乱程度", 或者说是 "确定性", 依据信息的不确定性将现有数据进行划分, 即若某一种划分使得数据的不确定性变小, 则这种划分就是有意义的, 比如如下一组数据:
作业是否完成 | 天气 | 是否去打篮球 |
是 | 晴朗 | 是 |
否 | 晴朗 | 是 |
是 | 下雨 | 否 |
否 | 下雨 | 否 |
从数据来看, 去不去打篮球的关键因素在于天气状况, 作业完成情况对是否去打蓝球的影响不是很大, 因此选用天气情况划分数据使最终数据的确定性更强(已经区分开了).
而数据的不确定性概念属于信息论的知识, 这里简要介绍一下:
通常度量数据的不确定性有两个指标: 信息熵和基尼系数
(1)信息熵
熵原本是用来描述物质的混乱程度, 借用到信息系统里则表示信息的不确定性, 其可以用如下式表示:
信息熵越大表示信息的不确定性越强, 想要把它搞清楚所需要的信息也就越多, H(y)越小意味着 y 就越规律, 确定性越强. 当 log 的底数为 2 时称之为比特, 底数为 e 时称之为纳特. 其函数图像如下:
(2)基尼系数
基尼系数是表示数据的纯度, 其表达式为:
基尼系数表示样本集合中一个随机选中的样本被分错的概率. 基尼指数越小表示集合中被选中的样本被分错的概率越小, 也就说集合的纯度越高, 反之, 集合越不纯. 即基尼系数越大表示数据的纯度越小, 不确定性越强, 基尼系数越小表示数据纯度越高, 确定性越强.
(3)条件熵
有了信息熵之后, 虽然能够反映出数据的确定性强弱, 那么选取哪个特征能够减小样本数据的不确定性呢? 这里就要用到条件熵的概念, 条件熵是特征 X 关于 y 的信息量的大小, 条件熵用 H(y|X)表示, 条件熵的计算公式为:
条件熵意味着在已知特征 X 的情况下 Y 的不确定性, 其值越小, 数据不确定性越小, 意味着特征 X 对于数据的划分更加有用.
(4)信息增益
信息增益可以理解为特征 X 为信息的不确定性的减少所带来的价值, X 越能为数据的不确定的减小价值贡献越大, 则信息增益就越大, X 就越能作为划分依据, 因此, 信息增益可以用下式计算:
X 使得 H(y|x)越小, 表明不确定性越小, 越能作为划分特征, 因此选取特征时, 信息增益越大越好.
关于信息熵, 条件熵, 信息增益, 互信息可以用下图进行表示:
H(y|x)为条件熵, 表示在变量 x 的条件下, y 的不确定性;
H(x,y)是互信息, 表示 x,y 的信息量之和;
G(y,x)=H(y)-H(y|x), 表示信息增益, 其值与互信息 H(x,y)相同.
上面就是有关信息论的一些基本概念. 有了上述一些基本概念后, 就可以依据上述的信息增益和基尼系数进行决策树的构造了, 决策树的构造类别也有很多种, 常见的有 ID3,C4.5 和 Cart 决策树, 下边分别介绍三种决策树的构造过程.
ID3 决策树
ID3 决策树就是就是利用信息增益进行特征选择和数据的划分的, 其构造过程为从根节点开始每次选择信息增益最大的特征作为划分标准, 直到满足条件即停止. 信息增益的计算过程如下:
比较各个特征值下的信息增益, 选取信息增益最大的那个特征作为划分依据进行树的分裂即可, 下面结合具体数据简单描述上述过程. 借用《Python 机器学习实战》书中的数据, 数据如下:
数据中共有 4 个特征, 分别为{颜色, 大小, 人员属性, 动作}, 类别 Y 为结果{爆炸, 不爆炸}, 那么初次划分节点从 4 个特征中选取一个作为划分标准, 计算每个特征的信息增益:
首先是 Y 的信息熵 H(y):
然后计算四个特征的条件熵:
因此选取大小或者动作作为节点的划分标准, 这里不妨选择气球大小作为划分数据标准, 将数据切割为两部分:
去掉气球大小的属性, 剩余数据集为:
小气球 大气球
然后再根据另外三个特征分别对两个节点 NodeA 和 NodeB 再次进行分割, 以此类推, 直到某个子节点属于同一类别即停止分裂, 那么最终获得的树的结构如图所示:
以上便为 ID3 决策树的算法过程, 然而 ID3 算法存在一定的缺陷, 其在选取信息增益最大作为划分标准时往往偏向于选择取值较多的那个特征去作为划分依据, 比如有一个样本集, 样本数量为 15, 其中一个特征有 15 个不同的值, 那么在计算条件熵时条件熵为 0, 信息增益最大, 那在进行节点分裂时, 会分出 15 个分支, 形成一棵矮胖的决策树, 这显示是不合理的, 这也是正是 ID3 为什么不能用于划分连续型特征的原因, 因此在 ID3 的基础上提出了改进的算法, 此为 C4.5 算法.
C4.5 决策树
C4.5 是在 ID3 决策树的基础上, 避免因特征取值较多而偏向于选取该特征作为分裂标准的不合理性, 因此, C4.5 将信息增益比作为树分裂的依据, 信息增益比的计算公式如下:
在信息增益的基础上除上特征 X 的信息熵, 当特征 X 的取值较多时, 那么 H(X)的值就会增大, 从而使得信息增益比减小, 具体计算过程就不再赘述.
同时 C4.5 可以用于处理连续型特征, 其做法是将某个特征取值按照大小进行排序: a1,a2,...,am, 然后将相邻两个数取平均值, 将特征划分成 m-1 个值. 对于这 m-1 个点, 分别计算以该点作为二元分类点时的信息增益比, 选择信息增益比最大的点作为该连续特征的二元离散分类点, 注意, 与离散特征不同的是, 如果当前节点为连续属性, 则该属性后面还可以参与分裂(有待考究, 有见到过离散变量出现重用的情况). 然而, 这种做法同样也会产生一些缺点, 进行二叉分支时, 可能会分出一个比较小的 Node 出来, 而另一个 Node 则会非常庞大, 在后续进一步分裂时这个特征还可以再分裂, 那么会不断地向下生成一个较深的树, 最终造成过拟合现象.
CART 决策树
CART 决策树的分裂规则是采用基尼系数的大小作为特征选择和树分裂标准的, 采用该指标能够简化熵模型中的对数运算, 同时又保留了熵的含义. 前面提到基尼系数越大数据越不纯, 相反, 基尼系数越小数据就越纯, 对于特征的选择就越好, 基尼系数的计算公式如下:
对于特征 X, 假设 X 有 2 个不同的值, 根据 X 将样本划分成两块 D1 和 D2, 那么有:
这里需要说明的是, CART 决策树是强制二叉树, 即无论特征 X 有多少个值, 在进行分裂时只会分裂出两个节点, 这与 ID3 和 C4.5 有所不同, 在 ID3 和 C4.5 中, 若特征 X 有 3 个取值, 选择该特征进行划分时会划分出三个节点, 而在 CART 中相当于 ovr 的思想. 比如特征 X 取值 {A1,A2,A3}, 那么在进行特征分裂时, 会选择{A1},{A2,A3} 和{A2},{A1,A3}和 {A3},{A1,A2} 的组合分别计算基尼系数, 若计算出 {A2},{A1,A3} 组合的基尼系数最小, 则将会分裂出两个节点, 此时由于特征 A 并没有完全分开, 在后面进行分裂时, 该特征将会进一步重用.
同时 CART 算法不但能够用于分类, 还可以对连续型数据做回归, 称之为 CART 回归树. 在分类树中采用的是基尼系数进行度量, 而在回归树中, 采用常用的和方差的度量方式, 即对于特征 X, 若划分点为 xp,xp 将数据划分成两块 D1 和 D2, 那么要使两块数据的和方差最小, 即:
其中 cjp 为两块样本数据输出的平均值.
回归树的预测最终根据叶子节点的平均值或者中位数作为预测结果. 下面给出 CART 算法决策树的构建流程:
"""
输入是训练集 D, 基尼系数的阈值, 样本个数阈值.
输出是决策树 T
对于当前节点的数据集 D, 如果样本个数小于预设阈值或没有特征, 则返回决策子树, 停止递归;
计算数据集的基尼系数, 若基尼系数小于预设值, 则返回决策子树, 停止递归;
计算当前节点现有的各个特征的每个特征值对数据集 D 的基尼系数, 选取基尼系数最小的特征值 x 及其特征 X, 根据这个特征值和特征, 将数据集 D 划分为两部分 D1 和 D2, 分裂出两个节点 Node1 和 Node2, 分别为左右节点;
对 Node1 和 Node2 分别递归上述过程, 生成决策树
"""
决策树的剪枝
前面在 C4.5 中提到对于连续型数据进行划分时会逐渐向下发展成很深的树, 造成过拟合, 同理, 对于其他的树的构建, 理论上只要树的深度足够深, 就能够完全拟合训练数据, 但这也造成了模型在测试数据上的泛化能力, 造成过拟合现象. 因此在构建决策树时或构建完成后需要进行剪枝操作, 防止过拟合. 剪枝可以分为预剪枝和后剪枝.
预剪枝实际上就是在树的分裂过程中预设的节点停止分裂的条件, 在实际应用中通常不多见.
后剪枝是指在树生成后, 剪掉树的的多余的节点, 降低模型的复杂度. 通常做法分为两步:(1)加入正则化, 即综合考虑不确定性和模型的复杂度, 加上一个损失, 作为新的分别标准重新度量, 进行剪枝操作. 这里主要说明第二种方式.(2)利用交叉验证, 产生所有可能剪枝后的决策树, 验证剪枝后的决策树的泛化能力, 选出最好的一颗;
首先先来看剪枝时的度量损失, 对于任意在节点 t 的一颗子树 T, 损失函数表示为:
其中α表示正则化参数, 与线性回归的一样, C(Tt)表示原度量标准, 分类树中为基尼系数, 回归树中为和方差,|Tt | 为子树 T 的叶子结点个数.α=0 表示未剪枝,α→∞时, 表示仅保留根节点.
如果此时将其剪掉, 仅保留根节点, 那么损失变为:
当α=0 或很小时, 则有, 当α增大到一定程度时会出现:
此时α满足下式:
此时表示 Tt 和 T 具有相同的损失函数, 但是 T 的节点更少, 因此可以对 Tt 进行剪枝操作, 剪掉其他的叶节点, Tt 成为了一个叶子结点.
通过求取设置不同的α, 从不剪枝到剪至只剩 1 个根节点, 记为 {T0,T1,T2,...,Tn}, 通过交叉验证的方法选出最好的决策树作为最终的结果.
下面给出决策树剪枝的算法过程:
"""
输入建立好的完整 CART 决策树 T0
输出最优的决策树 Tα
初始化 k=0,T=T0, 最优子树合集为 T={T0},α=∞;
从叶子节点开始从下向上计算各内部节点 t 的训练误差损失函数 Cα(Tt), 叶子节点的个数 | Tt|, 以及正则化的阈值α:
αk=αmin; 自上而下访问子树 t 的内部节点, 若满足:
则进行剪枝, 并决定叶节点 t 的, 若是分类树, 类别属于概率最高的类别, 若是回归树, 则是所有样本输出的均值, 这样得到了αk 对应的最优子树 Tk, 将放入子树 Tk 集合 T 中;
k=k+1,
T=Tk, 如果 T 不是由根节点单独组成的树, 则递归执行上述步骤, 否则就得到了最优子树集合 T;
利用交叉验证在 T 中选出最优的子树 Tα.
"""
至此, 决策树的算法基本原理这里已经简单介绍完了, 其中涉及较多原理部分可能需要进一步深挖, 目前的层面就先到这里了, 后面回头看的时候再深入理解, 进一步补充, 接下来将根据算法原理对决策树进行逻辑编写, 然后借助一些数据集去建立模型和实现, 最后一部分介绍一下决策树与集成学习的关系, 并对集成学习的原理进行简要介绍.
参考:
《Python 机器学习实战》
决策树算法原理博客 https://www.cnblogs.com/pinard/p/6053344.html
来源: https://www.cnblogs.com/501731wyb/p/15134268.html