决策树算法原理(CART分类树)

时间:2022-01-24 22:36:52

决策树算法原理(ID3,C4.5)

CART回归树

决策树的剪枝

  

  在决策树算法原理(ID3,C4.5)中,提到C4.5的不足,比如模型是用较为复杂的熵来度量,使用了相对较为复杂的多叉树,只能处理分类不能处理回归。对这些问题,CART(Classification And Regression Tree)做了改进,可以处理分类,也可以处理回归。

1. CART分类树算法的最优特征选择方法

  ID3中使用了信息增益选择特征,增益大优先选择。C4.5中,采用信息增益比选择特征,减少因特征值多导致信息增益大的问题。CART分类树算法使用基尼系数来代替信息增益比,基尼系数代表了模型的不纯度,基尼系数越小,不纯度越低,特征越好。这和信息增益(比)相反。

  假设K个类别,第k个类别的概率为pk,概率分布的基尼系数表达式:

决策树算法原理(CART分类树)

  如果是二分类问题,第一个样本输出概率为p,概率分布的基尼系数表达式为:

决策树算法原理(CART分类树)

  对于样本D,个数为|D|,假设K个类别,第k个类别的数量为|Ck|,则样本D的基尼系数表达式:

决策树算法原理(CART分类树)

  对于样本D,个数为|D|,根据特征A的某个值a,把D分成|D1|和|D2|,则在特征A的条件下,样本D的基尼系数表达式为:

决策树算法原理(CART分类树)

  比较基尼系数和熵模型的表达式,二次运算比对数简单很多。尤其是二分类问题,更加简单。

   和熵模型的度量方式比,基尼系数对应的误差有多大呢?对于二类分类,基尼系数和熵之半的曲线如下:

决策树算法原理(CART分类树)

  基尼系数和熵之半的曲线非常接近,仅在45度角附近误差稍大。因此,基尼系数可以做为熵模型的一个近似替代。

  CART分类树算法每次仅对某个特征的值进行二分,而不是多分,这样CART分类树算法建立起来的是二叉树,而不是多叉树。

2. CART分类树算法对连续特征和离散特征的处理

  CART分类树算法对连续值的处理,思想和C4.5相同,都是将连续的特征离散化。唯一区别在选择划分点时,C4.5是信息增益比,CART是基尼系数。

  具体思路:m个样本的连续特征A有m个,从小到大排列a1,a2,......,am,则CART取相邻两样本值的平均数做划分点,一共取m-1个,其中第i个划分点Ti表示为:Ti = (ai + ai+1)/2。分别计算以这m-1个点作为二元分类点时的基尼系数。选择基尼系数最小的点为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为at,则小于at的值为类别1,大于at的值为类别2,这样就做到了连续特征的离散化。

  注意的是,与ID3、C4.5处理离散属性不同的是,如果当前节点为连续属性,则该属性在后面还可以参与子节点的产生选择过程。

  CART分类树算法对离散值的处理,采用的思路:不停的二分离散特征。

  在ID3、C4.5,特征A被选取建立决策树节点,如果它有3个类别A1,A2,A3,我们会在决策树上建立一个三叉点,这样决策树是多叉树。

  CART采用的是不停的二分。会考虑把特征A分成{A1}和{A2,A3}、{A2}和{A1,A3}、{A3}和{A1,A2}三种情况,找到基尼系数最小的组合,比如{A2}和{A1,A3},然后建立二叉树节点,一个节点是A2对应的样本,另一个节点是{A1,A3}对应的样本。由于这次没有把特征A的取值完全分开,后面还有机会对子节点继续选择特征A划分A1和A3。这和ID3、C4.5不同,在ID3或C4.5的一颗子树中,离散特征只会参与一次节点的建立。

3. CART分类树算法具体流程

  CART分类树建立算法流程,之所以加上建立,是因为CART分类树算法有剪枝。

  算法输入训练集D,基尼系数的阈值,样本个数阈值。

  输出的是决策树T。

  算法从根节点开始,用训练集递归建立CART分类树。

  (1)、对于当前节点的数据集为D,如果样本个数小于阈值或没有特征,则返回决策子树,当前节点停止递归。

  (2)、计算样本集D的基尼系数,如果基尼系数小于阈值,则返回决策树子树,当前节点停止递归。

  (3)、计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数,对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和C4.5算法里描述的相同。

  (4)、在计算出来的各个特征的各个特征值对数据集D的基尼系数中,选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值,把数据集划分成两部分D1和D2,同时建立当前节点的左右节点,做节点的数据集D为D1,右节点的数据集D为D2。

  (5)、对左右的子节点递归的调用1-4步,生成决策树。

  对生成的决策树做预测的时候,假如测试集里的样本A落到了某个叶子节点,而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。

4. CART回归树建立算法

  CART回归树

  CART回归树和CART分类树的建立类似,这里只说不同。

  (1)、分类树与回归树的区别在样本的输出,如果样本输出是离散值,这是分类树;样本输出是连续值,这是回归树。分类树的输出是样本的类别,回归树的输出是一个实数。

  (2)、连续值的处理方法不同。

  (3)、决策树建立后做预测的方式不同。

  分类模型:采用基尼系数的大小度量特征各个划分点的优劣。

  回归模型:采用和方差度量,度量目标是对于划分特征A,对应划分点s两边的数据集D1和D2,求出使D1和D2各自集合的均方差最小,同时D1和D2的均方差之和最小。表达式为:

决策树算法原理(CART分类树)

其中,c1为D1的样本输出均值,c2为D2的样本输出均值。

  对于决策树建立后做预测的方式,CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。回归树输出不是类别,采用叶子节点的均值或者中位数来预测输出结果。

5、CART树算法的剪枝

  CART树的生成:基于训练数据集,递归构建二叉决策树。CART树的剪枝:用验证数据集对生成的树进行剪枝并选择最优子树,损失函数最小作为剪枝的标准。

  CART分类树的剪枝策略在度量损失的时候用基尼系数;CART回归树的剪枝策略在度量损失的时候用均方差。

  决策树很容易对训练集过拟合,导致泛化能力差,所以要对CART树进行剪枝,即类似线性回归的正则化。CART采用后剪枝法,即先生成决策树,然后产生所有剪枝后的CART树,然后使用交叉验证检验剪枝的效果,选择泛化能力最好的剪枝策略。

  剪枝损失函数表达式:决策树算法原理(CART分类树)

  α为正则化参数(和线性回归的正则化一样),C(Tt)为训练数据的预测误差,|Tt|是子树T叶子节点数量。

  当α = 0时,即没有正则化,原始生成的CART树即为最优子树。当α = ∞时,正则化强度最大,此时由原始的生成CART树的根节点组成的单节点树为最优子树。当然,这是两种极端情况,一般来说,α越大,剪枝剪的越厉害,生成的最优子树相比原生决策树就越偏小。对于固定的α,一定存在使得损失函数Cα(Tt)最小的唯一子树。

  剪枝的思路:

  对于位于节点t的任意一颗子树Tt,如果没有剪枝,损失函数是:

决策树算法原理(CART分类树)

  如果将其剪掉,仅保留根节点,损失函数是:

决策树算法原理(CART分类树)

  当α = 0或α很小,决策树算法原理(CART分类树),当α增大到一定程度时

决策树算法原理(CART分类树)

  当α继续增大时不等式反向,即满足下式:

决策树算法原理(CART分类树)

  Tt和T有相同的损失函数,但T节点更少,因此可以对子树Tt进行剪枝,也就是将它的子节点全部剪掉,变为一个叶子结点T。

  

  交叉验证策略:

  如果我们把所有节点是否剪枝的值α都计算出来,然后针对不同α对应的剪枝后的最优子树做交叉验证。这样可以选择最好的α,有了这个α,用对应的最优子树作为最终结果。

  有了上面的思路,CART树的剪枝算法:

  输入是CART树建立算法得到的原始决策树T。

  输出是最优决策树Tα

  算法过程:

  (1)、初始化αmin = ∞,最优子树集合ω = {T}。

  (2)、从叶子结点开始自下而上计算内部节点 t 的训练误差损失函数Cα(Tt)(回归树为均方差,分类树为基尼系数),叶子节点数|Tt|,以及正则化阈值决策树算法原理(CART分类树),更新αmin = α

  (3)、得到所有节点的α值得集合M。

  (4)、从M中选择最大的值αk,自上而下的访问子树 t 的内部节点,如果决策树算法原理(CART分类树)时,进行剪枝。并决定叶子节点 t 的值。如果是分类树,这是概率最高的类别,如果是回归树,这是所有样本输出的均值。这样得到αk对应的最优子树Tk

  (5)、最优子树集合ω = ωυTk,M = M - {αk}。

  (6)、如果M不为空,则回到步骤4。否则就已经得到了所有的可选最优子树集合ω。

  (7)、采用交叉验证在ω选择最优子树Tα

6. CART算法小结 

 算法 支持模型 树结构 特征选择  连续值处理 缺失值处理    剪枝
 ID3    分类  多叉树  信息增益  不支持  不支持  不支持
 C4.5    分类  多叉树  信息增益比  支持  支持  支持
 CART  分类回归  二叉树

基尼系数

均方差

 支持  支持  支持

ωCART算法缺点:

(1)、无论ID3,C4.5,CART都是选择一个最优的特征做分类决策,但大多数,分类决策不是由某一个特征决定,而是一组特征。这样得到的决策树更加准确,这种决策树叫多变量决策树(multi-variate decision tree)。在选择最优特征的时,多变量决策树不是选择某一个最优特征,而是选择一个最优的特征线性组合做决策。代表算法OC1。

(2)、样本一点点改动,树结构剧烈改变。这个通过集成学习里面的随机森林之类的方法解决。

7. 决策树算法小结

  这里不纠结ID3、C4.5、CART,这部分来自scikit-learn英文文档。

优点:

  1. 简单直观,生成的决策树很直观。
  2. 基本不需要预处理,不需要提前归一化和处理缺失值。
  3. 使用决策树预测的代价是O(log2m)。m为样本数。
  4. 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
  5. 可以处理多维度输出的分类问题。
  6. 相比于神经网络之类的黑盒分类模型,决策树在逻辑上可以很好解释。
  7. 可以交叉验证的剪枝来选择模型,从而提高泛化能力。
  8. 对于异常点的容错能力好,健壮性高。

缺点:

  1. 决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
  2. 决策树会因为样本发生一点的改动,导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
  3. 寻找最优的决策树是一个NP难题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习的方法来改善。
  4. 有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决。
  5. 如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

决策树算法原理(CART分类树)的更多相关文章

  1. 决策树算法原理(ID3,C4.5)

    决策树算法原理(CART分类树) CART回归树 决策树的剪枝 决策树可以作为分类算法,也可以作为回归算法,同时特别适合集成学习比如随机森林. 1. 决策树ID3算法的信息论基础   1970年昆兰找 ...

  2. 决策树算法原理--good blog

    转载于:http://www.cnblogs.com/pinard/p/6050306.html (楼主总结的很好,就拿来主义了,不顾以后还是多像楼主学习) 决策树算法在机器学习中算是很经典的一个算法 ...

  3. ID3决策树算法原理及C++实现(其中代码转自别人的博客)

    分类是数据挖掘中十分重要的组成部分.分类作为一种无监督学习方式被广泛的使用. 之前关于"数据挖掘中十大经典算法"中,基于ID3核心思想的分类算法C4.5榜上有名.所以不难看出ID3 ...

  4. 机器学习相关知识整理系列之一:决策树算法原理及剪枝(ID3,C4.5,CART)

    决策树是一种基本的分类与回归方法.分类决策树是一种描述对实例进行分类的树形结构,决策树由结点和有向边组成.结点由两种类型,内部结点表示一个特征或属性,叶结点表示一个类. 1. 基础知识 熵 在信息学和 ...

  5. 决策树算法原理及JAVA实现(ID3)

    0 引言 决策树的目的在于构造一颗树像下面这样的树. 图1 图2 1. 如何构造呢? 1.1   参考资料.       本例以图2为例,并参考了以下资料. (1) http://www.cnblog ...

  6. CART回归树

    决策树算法原理(ID3,C4.5) 决策树算法原理(CART分类树) 决策树的剪枝 CART回归树模型表达式: 其中,数据空间被划分为R1~Rm单元,每个单元有一个固定的输出值Cm.这样可以计算模型输 ...

  7. CART分类与回归树与GBDT(Gradient Boost Decision Tree)

    一.CART分类与回归树 资料转载: http://dataunion.org/5771.html        Classification And Regression Tree(CART)是决策 ...

  8. 机器学习实战---决策树CART简介及分类树实现

    https://blog.csdn.net/weixin_43383558/article/details/84303339?utm_medium=distribute.pc_relevant_t0. ...

  9. scikit-learn决策树算法类库使用小结

    之前对决策树的算法原理做了总结,包括决策树算法原理(上)和决策树算法原理(下).今天就从实践的角度来介绍决策树算法,主要是讲解使用scikit-learn来跑决策树算法,结果的可视化以及一些参数调参的 ...

随机推荐

  1. 如何利用报表工具FineReport实现报表列的动态展示

    相信动态列的实现困扰了很多人,大数据量,多字段的加载将会非常耗时,数据又做不到真正的动态灵活.现有的方式都是通过变向的隐藏等方式来实现. 那该如何解决呢?这里分享帆软报表设计器FineReport的实 ...

  2. 一大早居然有骗子还是*,真是莫名其妙的,QQ1913522040,一看就是刚申请不久的

  3. Programming In hardware Programming in software

    COMPUTER ORGANIZATION AND ARCHITECTURE DESIGNING FOR PERFORMANCE NINTH EDITION

  4. IntelliJ IDEA 15开发Java Maven项目

    1.安装好之后开始创建项目

  5. ASP.NET网页动态添加、更新或删除数据行

    ASP.NET网页动态添加.更新或删除数据行 看过此篇<ASP.NET网页动态添加数据行> http://www.cnblogs.com/insus/p/3247935.html的网友,也 ...

  6. linux和windows双系统时间错误解决方法

    转自http://www.2cto.com/os/201204/126212.html windows时间会慢8小时,原因: 两个概念: UTC即Universal Time Coordinated, ...

  7. 文件读写监控&lpar;inotify&comma; systemtap&rpar;

    一.inotify      inotify是内核的一个特性,可以用来监控目录.文件的读写等事件,当监控目标是目录时,inotify除了会监控目录本身,还会监控目录中的文件.inotify的监控功能由 ...

  8. python函数默认参数陷阱

    对于学习python的人都有这样的困惑 def foo(a=[]): a.append(5) return a Python新手希望这个函数总是返回一个只包含一个元素的列表:[5].结果却非常不同,而 ...

  9. Django多个中间件的执行顺序

    Django中的中间件是一个轻量级.底层的插件系统,可以介入Django的请求和响应处理过程,修改Django的输入或输出.中间件的设计为开发者提供了一种无侵入式的开发方式,增强了Django框架的健 ...

  10. 并发编程之 线程协作工具 LockSupport

    前言 在前面的文章中,我们介绍了并发工具中的4个,Samephore,CyclicBarrier,CountDownLatch,Exchanger,但是我们漏了一个,非常的好用的工具,楼主在这里必须加 ...