- 1、本文档共7页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
??
?
??
机器学习CART算法
?
??
?
?
?
?
?
?
?
???
?
?
?
?
?
?
?
导读:人工智能机器学习有关算法内容,今天我们重点探讨一下CART算法。
继上两篇决策树算法之ID3算法和ID3的改进算法-C4.5算法后,本文继续讨论另一种二分决策树算法-CART算法。我们知道十大机器学习中决策树算法占有两席位置,即C4.5算法和CART算法,可见CART算法的重要性。下面重点介绍CART算法。
不同于ID3与C4.5,CART为一种二分决策树,是满二叉树。CART算法由Breiman等人在1984年提出,它采用与传统统计学完全不同的方式构建预测准则,它是以二叉树的形式给出,易于理解、使用和解释。由CART模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确,且数据越复杂、变量越多,算法的优越性就越显著。
CART算法既可用于分类也可用于回归。CART算法被称为数据挖掘领域内里程碑式的算法。
CART算法概念:
CART(ClassificaTIonandRegressionTree)分类回归树是一种决策树构建算法。CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树,内部结点特征的取值为“是”和“否”,左分支是取值为“是”的分支,右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征,将输入空间即特征空间划分为有限个单元,并在这些单元上确定预测的概率分布,也就是在输入给定的条件下输出的条件概率分布。
CART算法既可以处理离散型问题,也可以处理连续型问题。这种算法在处理连续型问题时,主要通过使用二元切分来处理连续型变量,即特征值大于某个给定的值就走左子树,或者就走右子树。
CART算法组成:
1)决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大;自上而下从根开始建立节点,在每个节点处要选择一个最好(不同算法使用不同指标来定义"最好")的属性来分裂,使得子节点中的训练数据集尽量的纯。
2)决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时损失函数最小作为剪枝的标准。这里用代价复杂度剪枝CCP(Cost-ComplexityPruning)。
决策树的生成就是通过递归地构建二叉决策树的过程,对回归树用平方误差最小化准则,对分类树用基尼指数最小化准则,进行特征选择,生成二叉树。
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
您可能关注的文档
最近下载
- 华侨大学工程经济学考研真题试题2011年.pdf VIP
- 国标建筑专业图集 - 08J933-1 体育场地与设施(一).pdf
- 《ATV212HVAC变频器编程手册SCDOC1564-CN_40821》.pdf
- 西师版三年级上册教材分析.ppt
- 九年级英语人教版全册 unit6_sectiona(3a-3c)阅读课教学设计.pdf
- 初中语文必背古诗文61首.pdf
- 建筑材料行业2024年4月建材家居出口月报:美国通胀回落、就业低于预期,降息预期回升.docx
- 2024第六届(2024年)“信用电力”知识竞赛活动总试题库-下(多选、判断题汇总).docx
- 人教版高中生物必修一全册教学课件.pptx
- 《畜禽粪便与秸秆混合堆肥技术规程》 __DB2306_T098-2019.pdf
文档评论(0)