决策树是什么原理

图标

豆瓜

豆瓜网

豆瓜官网专栏

豆瓜 图标 2022-01-14 18:05:31

决策树(decision tree)是一类常见的机器学习方法,目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树。

决策树的生成是一个递归的过程。在决策树的基本算法中,有三种情况会导致递归返回:(1)当前节点包含的样本全属于同一类别,无需划分;(2)当前属性集为空,或是所有样本在所有属性上取值相同,无法划分;(3)当前节点包含的样本集为空,不能划分。

划分选择

决策树学习的关键在于,在每个分裂节点处如何选择最优划分属性。一般而言,随着划分过程不断进行,我们希望决策树的分支节点所包含的样本尽可能属于同一类别,即节点的“纯度”越来越高。

ID3决策树

信息增益

“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。

其中pi是S属于类别i的比例,需要注意的是底数仍然为2,原因熵是以二进制位的个数来度量编码长度,同时注意,如果目标属性具有c个可能值,那么熵最大可能为log2(c)。

已经有了熵作为衡量训练样例集合纯度的标准,现在可以定义属性分类训练数据的效力的度量标准。这个标准被称为“信息增益(information gain)”。简单的说,一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低(或者说,样本按照某属性划分时造成熵减少的期望,个人结合前面理解,总结为用来衡量给定的属性区分训练样例的能力)。更精确地讲,一个属性A相对样例集合S的信息增益Gain(S,A)被定义为:

 

C4.5决策树

增益率

实际上,信息增益准则对可取值数目较多的属性有所偏好,为减少这种偏好可能带来的不利影响,C4.5决策树算法不直接使用信息增益,而是使用“增益率”(gain ratio)来选择最优划分属性。信息增益率的计算相关公式:

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

剪枝处理

剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段。在决策树学习中,为了尽可能正确分类训练样本,节点划分过程不断重复,有时会造成决策树分支过多,这时就可能因训练样本学得“太好”了,以至于把训练样本自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此,可通过主动去掉一些分支来降低过拟合的风险。

决策树剪枝的基本策略有“预剪枝”和“后剪枝”。预剪枝是指在决策树生成的过程中,对每个节点在划分前先进行估计,若当前节点的划分不能带来决策树泛化性能的提升,则停止划分并将当前节点标记为叶节点;后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶节点进行考察,若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升,则将该子树替换为叶节点。

那如何判断决策树泛化性能是否提升呢?可以使用留出法,即预留一部书数据用作“验证集”以进行性能评估。

预剪枝

预剪枝使得决策树的很多分支都没有“展开”,这不仅降低了过拟合的风险,还显著减少了决策树的训练时间开销和测试时间开销。但另一方面,有些分支的当前划分虽不能提升泛化性能,甚至可能导致泛化性能暂时下降,但在其基础上进行的后续划分却有可能导致性能显著提高;预剪枝基于“贪心”本质禁止了这些分支展开,给预剪枝决策树带来了欠拟合的风险。

后剪枝

后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下,后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的,并且要自底向上地对树中的所有非叶节点进行逐一考察,因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

 

CART

CART(分类与回归树,classification and regression tree)是一个二叉决策树,亦即决策树的每个内部节点(决策节点)最多有两个分支。

CART算法由以下两步组成:

(1)决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大;

(2)决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时用损失函数最小作为剪枝的标准。

CART生成

决策树的生成就是递归地构建二叉决策树的过程,对回归树用平方误差最小化准则,对分类树用基尼指数(Gini index)最小化准则,进行特征选择,生成二叉树。

回归树的生成

选择怎样对输入空间进行划分,这里采用启发式的方法,选择第j个变量和它取的值s,作为切分变量和切分点,并定义两个区域:

然后寻找最优切分变量j和最优切分点s,具体地,求解:

对固定输入变量j可以找到最优切分点s:

遍历所有输入变量,找到最优的切分变量j,构成一个对(j,s)。依此将输入空间划分为两个区域。接着,对每个区域重复上述划分过程,直到满足停止条件为止,这样就生成一棵回归树。这样的回归树叫做最小二乘回归树。

分类树的生成

分类树用基尼指数选择最优特征,同时决定该特征的最优二值切分点。

CART剪枝


本文由豆瓜网专栏作家 豆瓜 投稿发布,并经过豆瓜网编辑审核。

转载此文章须经作者同意,并附上出处(豆瓜网)及本页链接。

若稿件文字、图片、视频等内容侵犯了您的权益,请联系本站进行 投诉处理

图标 图标

豆瓜

豆瓜网

豆瓜官网专栏

  • logistic回归说明

    logistic回归说明

    图标
    豆瓜 图标 · 2022-01-14 · 85浏览
  • sscanf

    图标
    豆瓜 图标 · 2022-01-14 · 47浏览
  • burp suite使用方法以及安装方法说明

    图标
    豆瓜 图标 · 2022-01-14 · 97浏览
  • 全部评论

    豆瓜

    豆瓜网

    豆瓜官网专栏

  • logistic回归说明
  • sscanf
  • burp suite使用方法以及安装方法说明
  • uml类图解析说明
  • metrics是什么工具类库
  • 我来说两句