这篇文章主要介绍 CART 算法。

CART 算法简介

分类与回归树（CART）模型既可以用来解决分类问题，也可以用来解决回归问题。CART 算法同样由特征选择、树的生成以及剪枝组成。
CART 假设决策树是二叉树，也就是说通过 CART 算法得到的决策树是一棵二叉树。

CART 算法的特征选择

• 对于回归问题，使用平方误差最小化准则来进行特征选择。
• 对于分类问题，使用基尼指数最小化准则来进行特征选择。

CART 算法如何进行划分

对于连续特征来说，假设在样本集 DD 中连续特征 aa 的取值有 nn 个，记为 a1,a2,a3,…,ana1,a2,a3,…,an，那么对于特征 aa 一供有 n−1n−1 个候选划分点，首先我们要将这 n 个取值排序。然后通过以下公式计算出这 n−1n−1 个划分点：
T_a = \Big{t_i = \frac{a^i + a^{i+1}}{2}|1 \leq i \leq n-1 \Big}T_a = \Big{t_i = \frac{a^i + a^{i+1}}{2}|1 \leq i \leq n-1 \Big}
然后按每个候选划分点进行划分，将样本集划分为两部分，一部分样本中的每个实例对应的特征的值都大于或者等于候选划分点，另一部分样本中的每个实例对应特征的值则都小于候选划分点。
对于非连续特征来说，就是遍历特征上的每个取值，按照每个取值进行划分，同样将样本集划分为两部分，一部分样本集中的每个实例对应的特征的值等于该取值，另一部分实例对应的特征的值则不等于该取值。

选择哪个特征进行划分

对于分类问题，选择划分后基尼指数最小的属性作为最优划分属性。数据集 DD 的基尼值 定义如下：
Gini(D)=|γ|∑k=1∑k‘≠kpkpk‘ =1−|γ|∑k=1p2kGini(D)=∑k=1|γ|∑k‘≠kpkpk‘=1−∑k=1|γ|pk2
基尼值反应的是从样本集中随机抽两个样本，这两个样本不属于同一类的概率。因此基尼值越小，数据集的纯度越高。属性 aa 的基尼指数定义如下：
GiniIndex(D,a)=V∑v=1|Dv||D|Gini(Dv)GiniIndex(D,a)=∑v=1V|Dv||D|Gini(Dv)

对于回归问题，由于要预测的是连续值，所以需要一个指标对连续值的混乱程度进行度量，这里用总方差来度量样本集上连续值的混乱程度。

1. 《统计学习方法》 —— 李航
2. 《机器学习》 —— 周志华

文章标题:决策树算法（四）：CART

文章字数:672

本文作者:ylhao

发布时间:2018-05-05, 15:22:42

最后更新:2019-06-07, 11:50:53

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。