一、基本概念
1.cart使用基尼系数作为划分标准。基尼系数越小，则不纯度越低，区分的越彻底。
2.假设有k个类别，第k个类别的概率为,则基尼系数表达式为：
Gini(p)=(1-
)=1-
3.对于样本D，如果根据特征A 的值把样本分为D1,D2两部分，则在特征A条件下，D的基尼系数
Gini(D,A)=Gini(D1)+
Gini(D2)
4.CART建立起来的是二叉树，如果特征A有A1,A2，A3三个类别，CART会考虑把A分成{A1},{A2 ,A3}两组，或者是其他两种情况。由于这次A并没有完全分开，所以下次还有机会在子节点把A2,A3分开.
5.对于连续值的切分.假如有1 2 3 4 5 那么cart会有4个切分点 [1.5 2.5 3.5 4.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树对于连续特征的处理
假如特征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.4 2.5处的基尼系数为 (2/6)*(1-(1/2)^2-(1/2)^2)+(4/6)*(1-(2/4)^2-(2/4)^2)=0.5 3.5处的基尼系数为 (3/6)*(1-(1/3)^2-(2/3)^2)+(3/6)*(1-(1/3)^2-(2/3)^2)=0.44 4.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.和分类树使用基尼系数不同，回归树使用和均方差来度量最佳分隔点。假设有1 2 3 4 5 6 六个数。假设3.5处把数据分开最合适，那么(1-2)^2+(2-2)^2+(3-2)^2+(4-5)^2+(5-5)^2+(6-5)^2在所有分割点中取得最小值。2，5为各自数据段的平均值。
3.回归树采用最后叶子的平均值或者中值作为输出结果
