专栏首页数据星河人工智能之机器学习CART算法解析

人工智能之机器学习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 条评论
登录 后参与评论

相关文章

  • iPhone X之后,面部识别的未来何在?

       远在1811年,第一次工业革命的发源地英国有这样一群纺织工人,历史上称他们为“勒德分子”,他们认为机器铁定会砸掉自己的饭碗,于是搬起家伙,捣毁工厂的机器,...

    数据星河
  • 苹果远端装置管理服务DEP含有验证缺陷

      安全业者DuoSecurity本周披露,苹果的装置注册计划(DeviceEnrollmentProgram,DEP)含有验证缺陷,将允许骇客以暴力破解法取得...

    数据星河
  • 什么是Hyperledger?Linux如何围绕英特尔的区块链项目构建开放平台?

           访问区块链会议并关注区块链新闻时,不可避免地,您会遇到Linux基金会的Hyperledger。理解像比特币、以太坊这样的加密货币还算相对容易的,...

    数据星河
  • C语言 | 每日基础(49)

    读者:我第一次把一个程序分成多个源文件, 我不知道该把什么放到 .c 文 件, 把什么放到 .h 文件。(“.h” 到底是什么意思?)

    C语言入门到精通
  • 如何评价创作歌手的业务能力?试试让NLP帮你分析一下

    【导读】如何评定一首歌的歌词的创造性?有些歌词是否真的套词或假借他人之手?本文作者就尝试用 NLP 技术分析了一位出名却也具有争议的嘻哈歌手 —— Drake ...

    AI科技大本营
  • 说唱有嘻哈 算法有哈希

    讲完了List之后,我们继续讲集合中的另外两大巨头,Map和Set。在讲解这两个巨头之前,很有必要来了解一下哈希算法,因为Map和Set的无脑实现类就是Hash...

    用户5745563
  • 组复制性能 | 全方位认识 MySQL 8.0 Group Replication

    为了让一个复制组正常使用消息分段功能,所有组成员必须运行MySQL 8.0.16或以上版本,并且组使用的组复制通信协议版本必须支持消息分段。可以使用group_...

    老叶茶馆
  • 3.使用sass、全局样式及进度条

    Sass 世界上最成熟、最稳定、最强大的专业级CSS扩展语言 NProgress 前端轻量级web进度条

    RtyXmd
  • Gradle构建-从Eclipse到Studio介绍篇

    记得之前体验Android Studio 1.x版本的时候,从Eclipse到Studio的第一感受就是严重的“水土不服”。由于手管要切换到Gradle,故又重...

    谢文军
  • Mac下的Jenkins安装

    1)通过命令行安装   brew install jenkins,可能会遇到先更新 brew 的情况  https://brew.sh/index_zh-cn;

    meteoric

扫码关注云+社区

领取腾讯云代金券