cart

决策树之CART算法

⼀、基本概念

使⽤基尼系数作为划分标准。基尼系数越⼩，则不纯度越低，区分的越彻底。

2.假设有k个类别，第k个类别的概率为,则基尼系数表达式为：

Gini(p)=(1-)=1-

3.对于样本D，如果根据特征A的值把样本分为D1,D2两部分，则在特征A条件下，D的基尼系数

Gini(D,A)=Gini(D1)+Gini(D2)

建⽴起来的是⼆叉树，如果特征A有A1,A2，A3三个类别，CART会考虑把A分成{A1},{A2,A3}两组，或者是其他两种情况。由于这次

A并没有完全分开，所以下次还有机会在⼦节点把A2,A3分开.

5.对于连续值的切分.假如有12345那么cart会有4个切分点[1.52.53.54.5]

⼆.实例推导树的建⽴过程

1.假设我有以下源数据

序号天⽓周末促销销量

1坏是是⾼

2坏是是⾼

3坏是是⾼

4坏否是⾼

5坏是是⾼

6坏否是⾼

7坏是否⾼

8好是是⾼

9好是否⾼

10好是是⾼

11好是是⾼

12好是是⾼

13好是是⾼

14坏是是低

15好否是⾼

16好否是⾼

17好否是⾼

18好否是⾼

19好否否⾼

20坏否否低

21坏否是低

22坏否是低

23坏否是低

24坏否否低

25坏是否低

26好否是低

27好否是低

28坏否否低

29坏否否低

30好否否低

31坏是否低

32好否是低

33好否否低

34好否否低

该数据集有三个特征天⽓周末促销

2.为了简化建⽴树的过程,我将忽略基尼系数与样本个数阀值

2.1⾸先计算各个特征值对数据集的基尼系数,公式见----基本概念.3

Gini(D|天⽓)=17/34*(1-(11/17)^2-(6/17)^2)+17/34*(1-(7/17)^2-(10/17)^2)=0.4706

Gini(D|周末)=20/34*(1-(7/20)^2-(13/20)^2)+14/34*(1-(11/14)^2-(3/14)^2)=0.4063

Gini(D|促销)=12/34*(1-(9/12)^2-(3/12)^2)+22/34*(1-(7/22)^2-(15/22)^2)=0.4131

周末的基尼系数最⼩，这也符合我们的⼀般认识

2.2第⼀个分列特征选择周末。此时数据集按照是否周末分成两个。

Gini(周末|天⽓)=0.2679

Gini(周末|促销)=0.2714

Gini(⾮周末|天⽓)=0.3505

Gini(⾮周末|促销)=0.3875

此时，周末应该以天⽓作为划分，⾮周末也是以天⽓作为划分，下⾯放个图

cart分类树

三、CART树对于连续特征的处理

假如特征A为连续型变量，则把特征A按照从⼩到⼤进⾏排序，取相邻两点的平均值为切分点，计算基尼系数。则基尼系数最⼩的点为切分点，⼤

于切分点的为⼀类，⼩于切分点的为另⼀类。举例：特征A的值为1，2，3，4，5，6⽬标变量是⾼、低、⾼、低、⾼、低。则1.5处的基尼

系数为(1/6)*(1-1^2)+(5/6)*(1-(2/5)^2-(3/5)^2)=0.42.5处的基尼系数为(2/6)*(1-(1/2)^2-

(1/2)^2)+(4/6)*(1-(2/4)^2-(2/4)^2)=0.53.5处的基尼系数为(3/6)*(1-(1/3)^2-(2/3)^2)+(3/6)*(1-(1/3)^2-

(2/3)^2)=0.444.5处的基尼系数为(4/6)*(1-(2/4)^2-(2/4)^2)+(2/6)*(1-(1/2)^2-(1/2)^2)=0.5

5.5处的基尼系数为(5/6)*(1-(2/5)^2-(3/5)^2)+(1/6)*(1-1^2)=0.4结论：1.5和5.5处的基尼系数最⼩，

可以把1分为⼀类，2-6分为另⼀类。或者6分为⼀类，1-5另⼀类。

四、关于回归树

1.回归树和分类树的区别在于输出值类型不同。分类树输出的是离散值，回归树输出的是连续值。

2.和分类树使⽤基尼系数不同，回归树使⽤和均⽅差来度量最佳分隔点。假设有123456六个数。假设3.5处把数据分开最合适，那么(1-

2)^2+(2-2)^2+(3-2)^2+(4-5)^2+(5-5)^2+(6-5)^2在所有分割点中取得最⼩值。2，5为各⾃数据段的平均值。

3.回归树采⽤最后叶⼦的平均值或者中值作为输出结果