0

决策树——CART

前言

决策树(1)中,介绍了决策树,熵,信息增益,信息增益比以及决策树的生成和剪枝算法。本文介绍CART(Classification and Regression Tree),这是一种既可以用户回归,可以用于分类的算法,看起来挺神奇的。文章分为以下几部分

  • CART介绍
  • CART生成
    • 回归树
    • 分类树
  • CART剪枝

CART介绍

分类与回归树(classification and regression tree, CART)模型由Breiman等人与1984年提出,该算法同样由特征选择,树的生成和剪枝组成,既可以用于分类,也可以用于回归。

CART是在给定输入随机变量$X$条件下输出随机变量$Y$的条件概率分布的学习方法。CART决策树有以下特点。

  1. CART决策树是二叉树
  2. 内部结点特征的取值为“是”和“否”,左分支是取值为“是”的分支,右分支是取值为“否”的分支

CART算法有以下两步组成:

  1. 决策树的生成:基于训练数据集生成决策树,生成的决策树要尽量大;
  2. 决策树的剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时用损失函数最小作为剪枝的标准。

CART生成

CART决策树的生成就是利用递归地构建二叉决策树的过程。对回归树用平方误差最小化的准则,对分类树用基尼指数(Gini index)最小化准则,进行特征选择,生成二叉树。

回归树

假设$X$与$Y$分别为输入和输出变量,并且$Y$是连续变量,给定训练数据集
\[
D={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}
\]
前面介绍了CART可以用于分类也可以用于回归,与线性回归利用一次拟合模型利用全部的样本数据不同的是,CART回归树每次划分把数据划分为2个不同的特征空间,然后在每个特征空间空间上寻找特征进行划分数据,最后得到$M$个单元$R_1,R_2, …, R_M$,并且在每个单元$R_M$上有一个固定的输出值$c_M$,于是回归树模型可以表示为

\[
f(x)=\sum_{m=1}^{M}c_mI(x\epsilon{R_m})
\]
当输入空间的划分确定时,可以用平方误差$\sum_{x_i\epsilon{R_m}}^{}(y_i-f(x))^2$来表示回归树对与训练数据的预测误差,因此,用平方误差最小的准则求解每个单元上的最优输出值。而在训练模型的时候,一般采用单元$R_m$上的$c_m$的最优值$\hat{c}_m$是$R_m$上的所有输入实例$x_i$对应的输出$y_i$的均值,即

\[
\hat{c}_m=avg(y_i|x_i\epsilon{R_m})
\]
那么问题来了,我们知道了对应一个新的观测$x_i$,利用得到的CART回归树可以得到以某个区域$R_m$的$\hat{c}_m$为输出的结果。那么我们怎么去得到这些区域呢?下面重点介绍一下这个启发式方法

对于训练数据$D$,假设其有3个特征,分别是$A_1,A_2,A_3$,而每个特征值都是连续值,而非离散值,如果是离散值,则应该将其连续化。好了,我们的目的是对训练数据$D$,找到一个特征$A_x$及其对应的某个值${A_x}_i$,他们分别是切分变量及其切分点,并将数据分成两部分(前面已经说了CART决策树是二叉树),分别是

\[
R_1(A_j, A_{ji})=\{x|A_j\leq{s}\}
\]

\[
R_2(A_j, A_{ji})=\{x|A_j> r{s}\}
\]

因此,我们的目标就是寻找最优的切分变量$A_j$及其对应的切分点$A_{ji}$,也就是求解以下公式

\[
\min_{A_j,A_{ji}}^{}[\min_{c_1}^{}\sum_{x_i\epsilon{R_1(A_j,A_{ji})}}^{}(y_i-c_1)^2+\min_{c_2}^{}\sum_{x_i\epsilon{R_2(A_j,A_{ji})}}^{}(y_i-c_2)^2]
\]
就可以找到最优切分变量及其切分点,然后求得每个$\hat{c}_1$和$\hat{c}_2$,公式为

\[
\hat{c}_1=avg(y_i|x_i\epsilon{R_1(A_j, A_{ji}})\qquad{\hat{c}_2=avg(y_i|x_i\epsilon{R_2(A_j, A_{ji}})}
\]
因此,从上式可知,我们的目的是遍历数据集$D$中的所有变量(特征),找到最优的切分变量$A_j$及其对应的切分值$A_{ji}$,构成一个切分对$(A_j,A_{ji})$,依据此对将数据集划分为两个区域。然后递归对被划分的数据重复以上划分过程,直到满足停止条件为止。因此就生成了一棵回归树,这样的回归树通常称为最小二乘回归树(Least squares regression tree)。
这里说明一下回归树递归建树的停止条件——所有的特征已经被划分完毕或者得到的误差不能满足给定阈值。

总结一下,我们最终目的是为了得到回归树模型,而为了得到回归树模型,需要对特征空间进行划分,那么就需要得到合适的特征及其对应的值进行划分,而为了得到该特征及其对应的值,就必须利用上面提高的误差公式。

分类树

与回归树不同的树不同是,分类树使用基尼指数选择最优特征。特征选择对于决策树建树非常重要。在选择了最优特征之后再选择最优划分点进行数据集的划分。

基尼指数

分类问题中,假设由$K$个类,样本点属于第$k$类的概率为$p_k$,则概率分布的基尼指数定义为

\[
Gini(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}p_k^2
\]
对于给定的数据集$D$,其基尼指数为

\[
Gini(D)=1-\sum_{k=1}^{K}(\frac{\left|C_k\right|}{\left|D\right|})^2
\]
其中$C_k$是$D$中属于第$k$类的样本子集,$K$是类的个数。

如果样本集合$D$根据特征$A$是否取某个可能值$a$被分割成$D_1$和$D_2$两部分,即

\[
D_1=\{(x,y)\epsilon{D}|A(x)=a\},D_2=D-D_1
\]
则在特征$A$的条件下,集合$D$的基尼指数定义为

\[
Gini(D,A)=\frac{\left|D_1\right|}{\left|D\right|}Gini(D_1)+\frac{\left|D_2\right|}{\left|D\right|}Gini(D_2)
\]
基尼指数表示的数据集$D$的不确定性的程度,基尼指数越大,样本的不确定性也就越大,这一点与熵相似。

在生成分类树的过程中,选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点,然后依次最优特征与最优切分点把建立两个子结点,然后递归建树。最后,算法终止的条件是节点中的样本个数新奥与预定的阈值,或样本集的基尼指数小雨预定阈值(样本基本属于同一类),或者没有更多的特征。

CART剪枝

剪枝的目的已经在决策树(1)已经说明。CART剪枝算法由两步组成(1)首先从生成算法产生的决策树$T_0$底端开始不断剪枝,直到$T_0$的根结点,形成一个子树序列$\{T_0,T_1,…,T_n\}$;(2)然后通过交叉验证法在独立的验证数据集上对子树序列进行测试,从中选择最优子树。

goingmyway

我是一只野生程序猿,我关注机器学习,神经网络,深度学习,增强学习,人工智能,Python,C/C++,Linux

发表评论

电子邮件地址不会被公开。 必填项已用*标注