CART算法

CART

CART的全称是classification and regression tree,意为分类回归树。也就是说这类决策树既可以解决分类问题,也能解决回归问题。因此针对分类树和回归树,cart有两种生成方式。这里要注意,树是根据训练集数据依据一定的规则生成,对于测试集数据,只需要将数据从根节点输入,像流水一样,沿着应该走的管道,到达所预测的类别或者回归数值。

针对任何一种机器学习模型,其训练过程都大同小异,目的都是为了使训练集数据尽可能被较好地分类和拟合。cart也不例外,无论是分类树还是回归树,无外乎都需要在生成过程(训练过程)使得某些误差最小,最恰当的安排训练数据。下面分别说明。

Gini指数

  • 一种不等性度量
  • 通常用来度量收入不平衡,可以用来度量任何不均匀分布
  • 是介于0~1之间的数,0-完全相等,1-完全不相等
  • 总体内包含的类别越杂乱,Gini指数就越大(跟熵的概念很相似)

Gini 指数的定义为:

G i n i ( D ) = 1 i = 1 m p i 2 Gini(D)=1-\sum_{i=1}^m p_i^2

其中, p i p_i 是D元祖水果属于 C i C_i 类的概率,并用 C i , D D \frac{|C_{i,D|}}{|D|} 估计,对 m m 个类计算和。由于CART算法是二叉树形式,所以一个多水平(m个水平)的离散变量(自变量)可以把数据集D划分为2m-2种可能.举个例子,在去不去打高尔夫球的例子中,Outlook有三个选项{Sunny,Rainy,Overcast},则其子集可能是{Sunny,Rainy,Overcast},{Sunny,Rainy},{Sunny,Overcast}{Rainy,Overcast},{Rainy},{Sunny},{Overcast},{},其中{Sunny,Rainy,Overcast}和空集{}为无意义的Split,所以6=23-2.
对于一个离散变量来说,需要计算每个分区不纯度的加权和,即对于变量A来说,D的Gini系数为:

G i n i ( D , A ) = D 1 D G i n i ( D 1 ) + D 2 D ( D 2 ) , D 1 = ( x , y ) D A ( x ) = a , D 2 = D D 1 Gini(D,A)=\frac{|D_1|}{D}Gini(D_1)+\frac{D_2}{D}(D_2), D_1={(x,y)\in D | A(x)=a},D_2=D-D_1

用每个特征(这里是A)的每个可能的值(这里是a)进行二分,每分一次就会产生两份样本,然后按照上式求每一次的综合基尼指数,最后选择基尼指数最小的那个分法就好了。

回归树的生成

对应分类树的最小化基尼指数准则,回归树该怎么确定哪个分法才最好呢?经典的最小二乘算法!
对于每一个特征的每一个值,我们依然都尝试一遍,每一次,都算一下5.21式。c1,c2分别是分开的两份样本的各自均值,也就是能使拟合误差最小的预测值。直至满足停止条件。

  • 输入:训练数据集D:
  • 输出:回归树 f ( x ) f(x)
  • 在训练数据集所在的输入空间中,递归的向每个区域划分为两个子区域并决定每个子区域熵的输出值,构建二叉树。
  1. 选择最后切分变量 j j 与切分点 s s ,求解

m i n j , s [ m i n c 1 x i R 1 ( f , s ) ( y i c 1 ) 2 + m i n c 2 x i R 2 ( f , s ) ( y i c 2 ) 2 ] min_{j,s}[min_{c_1}\sum_{x_i\in R_1(f,s)}(y_i-c_1)^2+min_{c_2}\sum_{x_i\in R_2(f,s)}(y_i-c_2)^2]

遍历变量 j j ,对固定的切分变量 j j 扫描切分点 s s ,选择使上式达到最小值得对 ( j , s ) (j,s) .
2. 用选定的对(j,s)划分区域并决定相应的输出值。

R 1 ( j , s ) = x x ( j ) s , R 2 ( j , s ) = x x ( j ) > s , c m = 1 N m x i R m ( j , s ) y i , x R m m = 1 , 2 R_1(j,s)={x|x^{(j)}\le s}, R_2(j,s)={x|x^{(j)}\gt s}, c_m=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i,x\in Rmm=1,2

  1. 继续对两个子区域调用步骤1,2,直到满足停止条件。
  2. 将输入空间划分成M个区域 R 1 , R 2 , . . . , R M R_1,R_2,...,R_M ,直至生成决策树:

f ( x ) = m = 1 M c m I ( x R m ) f(x)=\sum_{m=1}^Mc_mI(x\in R_m)

  • 关于停止条件:对于分类回归树来说,停止条件可以有多种,也可以人为设定。比如对于分类树,可以当所有特征都用尽时停止,也可以当某个树杈包含的所有样本都纯净时停止。对于回归树,可以认为设定当某个树杈包含的样本个数或者方差小于某个阈值时停止。

代码实现

python 库sklearn有对CART的实现,具体使用方式见
http://scikit-learn.org/stable/modules/tree.html#tree-algorithms

参考资料

决策树(主要针对CART)的生成与剪枝

CART决策树(分类回归树)分析及应用建模

展开全文
相关主题
Top
微信扫码咨询专知VIP会员