人工智能之机器学习CART算法解析

  人工智能之机器学习主要有三大类:1)分类;2)回归;3)聚类。今天我们重点探讨一下CART算法。

  我们知道十大机器学习中决策树算法占有两席位置,即C4.5算法和CART算法,可见CART算法的重要性。下面重点介绍CART算法。

  不同于ID3与C4.5,CART为一种二分决策树,是满二叉树。CART算法由Breiman等人在1984年提出,它采用与传统统计学完全不同的方式构建预测准则,它是以二叉树的形式给出,易于理解、使用和解释。由CART模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确,且数据越复杂、变量越多,算法的优越性就越显著。

  CART算法既可用于分类也可用于回归。CART算法被称为数据挖掘领域内里程碑式的算法。

  CART算法概念:

  CART(Classification andRegression Tree)分类回归树是一种决策树构建算法。CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树,内部结点特征的取值为“是”和“否”,左分支是取值为“是”的分支,右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征,将输入空间即特征空间划分为有限个单元,并在这些单元上确定预测的概率分布,也就是在输入给定的条件下输出的条件概率分布。

  CART算法既可以处理离散型问题,也可以处理连续型问题。这种算法在处理连续型问题时,主要通过使用二元切分来处理连续型变量,即特征值大于某个给定的值就走左子树,或者就走右子树。

  CART算法组成:

  CART算法组成如下:

  1)决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大;自上而下从根开始建立节点,在每个节点处要选择一个最好(不同算法使用不同指标来定义"最好")的属性来分裂,使得子节点中的训练数据集尽量的纯。

  2)决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时损失函数最小作为剪枝的标准。这里用代价复杂度剪枝CCP(Cost-Complexity Pruning)。

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

  CART决策树生成:

  1)回归树生成

  回归树采用均方误差作为损失函数,树生成时会递归的按最优特征与最优特征下的最优取值对空间进行划分,直到满足停止条件为止,停止条件可以人为设定,比如当切分后的损失减小值小于给定的阈值ε,则停止切分,生成叶节点。对于生成的回归树,每个叶节点的类别为落到该叶节点数据的标签的均值。

  回归树为一棵二叉树,每次都是按特征下的某个取值进行划分,每一个内部节点都是做一个对应特征的判断,直至走到叶节点得到其类别,构建这棵树的难点在于如何选取最优的切分特征与切分特征对应的切分变量。

  回归树与模型树既可以处理连续特征也可以处理离散特征。

  回归树生成算法如下:

  输入:训练数据集D={(x1,y1),(x2,y2),…,(xN,yN)}

  输出:回归树T

  1)求解选择切分特征j与切分特征取值s,j将训练集D划分为两部分,R1与R2,依照(j,s)切分后如下:

  R1(j,s)={xi|xji≤s}R2(j,s)={xi|xji>s}

  c1=1N1∑xi∈R1yi c2=1N2∑xi∈R2yi

  2)遍历所有可能的解(j,s),找到最优的(j*,s*),最优的解使得对应损失最小,按照最优特征(j*,s*)来切分即可。

  Min{∑(yi–c1)^2+∑(yi–c2)^2}

  j,s xi∈R1 xi∈R2

  3)递归调用1)和2),直到满足停止条件。

  4)返回决策树T。

  回归树主要采用了分治策略,对于无法用唯一的全局线性回归来优化的目标进行分而治之,进而取得比较准确的结果,但分段取均值并不是一个明智的选择,可以考虑将叶节点设置为一个线性函数,这便是所谓的分段线性模型树。实验表明:模型树效果比回归树的效果要好一些。模型树只需在回归树的基础上稍加修改即可,对于分到叶节点的数据,采用线性回归的最小均方损失来计算该节点的损失。  

  2)分类树生成

  分类树是CART中用来分类的,不同于ID3与C4.5,CART分类树采用基尼指数来选择最优的切分特征,而且每次都是二分。

  基尼指数是一个类似与熵的概念,对于一个有K种状态对应的概率为p1,p2,…,pK的随机变量X,其基尼指数Gini定义如下:

  Gini(X)=∑pk(1?pk)=1?∑kp2k

  k k

  在已知特征A条件下集合D的基尼指数:

  Gini(D,A)=(|D1|/|D|)*Gini(D1)+(|D2|/|D|)*Gini(D2)

  Gini(D,A)取值越大,样本的不确定性也越大,这一点与熵类似,所以选择特征A的标准是Gini(D,A)的取值越小越好。

原文链接:https://www.bdm361.com

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小鹏的专栏

为什么很多做人脸的Paper会最后加入一个Local Connected Conv?

Deep face:论文。 a. 人脸检测,使用6个基点 b. 二维剪切,将人脸部分裁剪出来 c. 67个基点,然后Delaunay三角化,在轮廓处添加三角形来...

3445
来自专栏人工智能LeadAI

pytorch入门教程 | 第三章:构造一个小型CNN

学过深度卷积网络的应该都非常熟悉这张demo图(LeNet): ? 此图是LeNet的结构图,把32*32的手写英文字符图片作为输入,训练出一个对于手写字符的分...

3617
来自专栏AI研习社

一篇文章教你用 11 行 Python 代码实现神经网络

编者按:本文作者陶言祺,原文载于作者个人博客,雷锋网 AI 研习社已获授权。 声明:本文是根据英文教程 A Neural Network in 11 lines...

37316
来自专栏机器之心

教程 | 重新发现语义分割,一文简述全卷积网络

语义分割是一种学习如何识别图像中对象范围的机器学习技术。语义分割赋予机器学习系统与人类相似的理解图像内容的能力。它促使机器学习算法定位对象的精准边界,无论是街景...

1602
来自专栏生信小驿站

R 集成算法③ 随机森林

按这种算法得到的随机森林中的每一棵都是很弱的,但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法:每一棵决策树就是一个精通于某一个窄领域的专家,这样在随...

1634
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

基于模糊集理论的一种图像二值化算法的原理、实现效果及代码

  这是篇很古老的论文中的算法,发表与1994年,是清华大学黄良凯(Liang-kai Huang) 所写,因此国外一些论文里和代码里称之为Huang's fu...

29111
来自专栏机器学习算法原理与实践

word2vec原理(一) CBOW与Skip-Gram模型基础

    word2vec是google在2013年推出的一个NLP工具,它的特点是将所有的词向量化,这样词与词之间就可以定量的去度量他们之间的关系,挖掘词之间的...

1792
来自专栏机器学习之旅

R开发:常用R语言包介绍

r与python差异比较大的一个地方就是,python的机器学习算法集中程度比较高,比如sklearn,就集成了很多的算法,而R语言更多时候需要一个包一个包去了...

1095
来自专栏磐创AI技术团队的专栏

使用Keras进行深度学习:(一)Keras 入门

导语 Keras是Python中以CNTK、Tensorflow或者Theano为计算后台的一个深度学习建模环境。相对于其他深度学习的框架,如Tensorflo...

3786
来自专栏人工智能LeadAI

线性回归与最小二乘法 | 机器学习笔记

这篇笔记会将几本的线性回归概念和最小二乘法。 在机器学习中,一个重要而且常见的问题就是学习和预测特征变量(自变量)与响应的响应变量(应变量)之间的函数关系 ...

3417

扫码关注云+社区

领取腾讯云代金券