人工智能之机器学习CART算法解析

人工智能之机器学习主要有三大类：1）分类；2）回归；3）聚类。今天我们重点探讨一下CART算法。

我们知道十大机器学习中决策树算法占有两席位置，即C4．5算法和CART算法，可见CART算法的重要性。下面重点介绍CART算法。

不同于ID3与C4．5，CART为一种二分决策树，是满二叉树。CART算法由Breiman等人在 1984 年提出，它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显著。

CART算法既可用于分类也可用于回归。CART算法被称为数据挖掘领域内里程碑式的算法。

CART（Classification andRegression Tree） 分类回归树是一种决策树构建算法。CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

CART算法既可以处理离散型问题，也可以处理连续型问题。这种算法在处理连续型问题时，主要通过使用二元切分来处理连续型变量，即特征值大于某个给定的值就走左子树，或者就走右子树。

CART算法组成如下：

1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；自上而下从根开始建立节点，在每个节点处要选择一个最好（不同算法使用不同指标来定义＂最好＂）的属性来分裂，使得子节点中的训练数据集尽量的纯。

2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。这里用代价复杂度剪枝CCP（Cost－Complexity Pruning）。

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

1）回归树生成

回归树采用均方误差作为损失函数，树生成时会递归的按最优特征与最优特征下的最优取值对空间进行划分，直到满足停止条件为止，停止条件可以人为设定，比如当切分后的损失减小值小于给定的阈值 ε，则停止切分，生成叶节点。对于生成的回归树，每个叶节点的类别为落到该叶节点数据的标签的均值。

回归树为一棵二叉树，每次都是按特征下的某个取值进行划分，每一个内部节点都是做一个对应特征的判断，直至走到叶节点得到其类别，构建这棵树的难点在于如何选取最优的切分特征与切分特征对应的切分变量。

回归树与模型树既可以处理连续特征也可以处理离散特征。

回归树生成算法如下：

输入：训练数据集 D＝｛（x1，y1），（x2，y2），…，（xN，yN）｝

输出：回归树 T

1）求解选择切分特征 j 与切分特征取值 s ，j 将训练集 D 划分为两部分，R1 与R2 ，依照（j，s）切分后如下：

R1（j，s）＝｛xi｜xji≤s｝ R2（j，s）＝｛xi｜xji＞s｝

c1＝1N1∑xi∈R1yi c2＝1N2∑xi∈R2yi

2）遍历所有可能的解（j，s），找到最优的 （j＊，s＊） ，最优的解使得对应损失最小，按照最优特征（j＊，s＊）来切分即可。

Min ｛ ∑ （yi–c1）＾2 ＋∑ （yi–c2）＾2 ｝

j，s xi∈R1 xi∈R2

3）递归调用 1）和2），直到满足停止条件。

4）返回决策树 T。

回归树主要采用了分治策略，对于无法用唯一的全局线性回归来优化的目标进行分而治之，进而取得比较准确的结果，但分段取均值并不是一个明智的选择，可以考虑将叶节点设置为一个线性函数，这便是所谓的分段线性模型树。实验表明：模型树效果比回归树的效果要好一些。模型树只需在回归树的基础上稍加修改即可，对于分到叶节点的数据，采用线性回归的最小均方损失来计算该节点的损失。

2）分类树生成

分类树是CART中用来分类的，不同于 ID3 与 C4．5，CART分类树采用基尼指数来选择最优的切分特征，而且每次都是二分。

基尼指数是一个类似与熵的概念，对于一个有 K 种状态对应的概率为 p1，p2，…，pK的随机变量 X ，其基尼指数Gini定义如下：

Gini（X）＝∑pk（1？pk）＝1？∑kp2k

k k

在已知特征 A条件下集合 D 的基尼指数：

Gini（D，A）＝（｜D1｜／｜D｜）＊Gini（D1）＋（｜D2｜／｜D｜）＊Gini（D2）

Gini（D，A）取值越大，样本的不确定性也越大，这一点与熵类似，所以选择特征 A 的标准是 Gini（D，A） 的取值越小越好。