文档介绍：CART算法组员:吕月明黄志骞万广玺杨程刘文谢振峰背景CART即分类与回归树算法,是在1984年由四位美国统计学家提出。适用于非度量的语义属性分类。它通过构建二叉树达到预测目的,已经在统计领域和数据挖掘技术中普遍使用。,并且具有两个以上的类别,则CART可能考虑将目标合并成两个超类别。这一过程称为双化。(数值的),则CART算法找出一组基于树的回归方程来预测目标变量。如果目标变量是标称的,则称该树为分类树(classificationtree);如果目标变量是连续数值,则称该树为回归树(regressiontree)Gini指数Gini指数是一种不等性度量,它通常用来度量收入不平衡,但是它可以用来度量任何不均匀分布。Gini指数是一个0~1之间的数,其中0对应于完全相等(其中每个人都具有相同的收入),而1对应于完全不相等(其中一个人具有所有收入,而其他人收入都为零)。Gini指数的一个修订形式用于度量节点的不纯性,并且常常在依赖目标变量是分类变量时使用。它的最小值是0,最大值是(1-1/k),其中k是目标变量的类别数。节点t的Gini指数GINI(t)定义为:GINI(t)=()其中i和j是目标变量的类别。上式可以写作:GINI(t)=1-()其中p(j/t)表示目标类别j在节点t中出现的比例。当节点中的实例在目标类别之间均匀分布时,Gini指数取最大值1-1/k,其中k是目标变量的类别数。Gini指数的最小值为0,当节点上所有数据都属于一个目标类别时取最小值。节点t上的s划分的Gini标准定义为:()其中pL是t中送到左边子女节点的实例所占的比例,pR是t中送到右边子女节点的实例所占的比例。s∈S是所有可能的划分集S中的一个具体划分。选择划分s,最大化GINIsplit(s,t)的值。由于对于节点t上的任意划分s,GINI(t)是常量,我们可以说选择划分s,使得量Gain(s,t)=pL*GINI(tL)+pR*GINI(tR)最小。对于分类变量,如果类别多于两个,则考虑将类别合并为两个超类别的所有可能组合,以求出最佳划分。CART分析的步骤从根节点t=1开始,从所有可能候选s的集合中搜索使得不纯性降低最大的划分s*;然后,使用划分s*将节点1(t=1)划分成两个节点t=2和t==2和t=3上分别重复划分搜索过程。继续生长过程,直到至少满足一个停止树生长的规则为止。变量“天气”和“气温”有三个级别,因此我们需要考虑级别合并,得到使用Gini指数划分数据的增益。在这个例子中,我们仅计算三个可能的合并中的一个。节点0上的计算:变量---天气GINI(天气=晴+雨)=1-[(5/10)2+(5/10)2]=(天气=多云)=1-[(4/4)2+(0/4)2]=0GINI(按天气划分)=[(10/14)*(1/2)+(4/14)*0]=---气温GINI(气温=热+凉爽)=1-[(5/8)2+(3/8)2]=(气温=适中)=1-[(4/6)2+(2/6)2]=(按气温划分)=[(8/14)*+(6/14)*]=---湿度GINI(湿度=高)=1-[(3/7)2+(4/7)2]=24/49GINI(湿度=正常)=1-[(6/7)2+(1/7)2]=12/49GINI(按湿度划分)=[(7/14)*(24/49)+(7/14)*(12/49)]=---有风GINI(有风=false)=1-[(6/8)2+(2/8)2]=(有风=true)=1-[(3/6)2+(3/6)2]=(按有风划分)=[(8/14)*+(6/14)*]=