1.CART分类树的特征选择

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

如果，集合D根据特征A是否取某一可能值a被分割成和，在特征A的条件下,集合D的基尼指数定义为:

基尼指数代表了模型的不纯度,基尼指数越小,不纯度越小,特征越好.

 2.CART分类树的生成算法

输入:训练数据集D,停止计算条件;

输出:CART决策树.

根据训练数据集,从根结点开始,递归的对每个结点进行以下操作,构建二叉树:

(1)计算现有特征对该数据集的基尼指数;

(2)在所有可能的特征A以及它们所有可能的切分点a中,选择基尼指数最小的特征,以及其对应的切分点作为最优特征和最优切分点,依此从现结点生成两个子结点,将数据集集体依特征分配到两个子结点中去;

(3)对两个子结点递归的调用(1)(2)，直至满足停止条件;

(4)生成CART决策树

3.CART回归树的建立

在CART分类树中,用基尼指数来选择最优特征和最优切分点,而在回归树当中用的是均方差.选择最优切分变量j与切分点s的方式是,求解:

　　其中是的样本输出均值，是的样本输出均值。CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

4.CART剪枝思想

　　由于决策树算法容易过拟合，导致泛化能力较差，为了解决此问题，便引入了决策树剪枝，即类似于线性回归的正则化，来增强决策树的泛化能力。CART树采用后剪枝，分为两步：一、从生产算法产生的决策树不断剪枝，直到根结点，产生剪枝后的决策树；二、通过交叉验证法在独立的实验数据集上对子树进行测试，选择最优子树。

　　在剪枝过程中，计算子树的损失函数：

其中，T为任意子树，是对训练数据的预测误差(如基尼指数)，为子树的叶结点个数，为参数，并权衡训练数据的拟合程度与模型的复杂度。表示参数为时的整体损失。偏大时，最优子树偏小，偏小时，最优子树偏大，时，整体树是最优的。

　　剪枝时，从整体树开始,对的任意内部结点t,以t为单结点树的损失函数是:

　　以t为根结点的子树的损失函数是:

　　当及充分小时,有不等式:

可以这么理解,剪枝后的损失函数值比剪枝前的损失函数值要小.

　　当增大时,在某一有:

　　当再增大时,不等式反向.那么,只要,与t有相同的损失函数值,而t的结点减少,因此t比更可取,对进行剪枝.

 　　为此,对中每一个内部结点t,计算

它表示剪枝后整体损失函数减少的程度,在中减去最小的,得到的子树作为,同时将最小的设为.为区间的最优子树.如此剪枝下去,直到得到根结点.在这一过程中,不断的增加的值,产生新的区间.

　　最后,利用独立的验证数据集,测试子树序列中各棵子树的平均方误差或者基尼指数,值最小的决策树被认为是最优的决策树.在子树序列中,每棵子树都对应一个参数.所以,当最优子树确定时,对应的也就确定下来了,即得到最优决策树.

5.CART剪枝算法

输入:CART算法生成的决策树;

输出:最优决策树.

(1)设k=0，

(2)设

(3)自下而上地对各内部结点t计算,以及

这里,表示以t为根结点的子树,是对训练数据的预测误差,是的叶结点个数

(4)对的内部结点t进行剪枝,并对叶结点t以多数表决法决定其类,得到树

(5)设

(6)如果不是由根结点及两个叶结点构成的树,返回到(3);否则

(7)采用交叉验证法在子树序列中选择最优子树

统计学习笔记之决策树(二)