CART

CART代表分类和回归树，英文是 Classification and Regression Trees

像英文一样，它构建了两棵树：一棵是分类树，另一个是回归树。和C4.5一样，它是一个决策树学习方法

ID3和C4.5算法可以生成二叉树或多叉树，而CART只支持二叉树。同时CART决策树比较特殊，既可以作分类树，又可以作回归树

什么是分类树，什么是回归树呢？

不同职业的人，他们的年龄不同，学习时间也不同。如果构造了一棵决策树，想要基于数据判断这个人的职业身份，这个就属于分类树

如果是给定了数据，想要预测这个人的年龄，那就属于回归树

分类树可以处理离散数据，也就是数据种类有限的数据，它输出的是样本的类别

而回归树可以对连续型的数值进行预测，也就是数据在某个区间内都有取值的可能，它输出的是一个数值

CART分类树的工作流程

决策树的核心就是寻找纯净的划分，因此引入了纯度的概念，在属性选择上，我们通过统计“不纯度”来做判断的

ID3是基于信息增益做判断，C4.5在ID3的基础上做了改进，提出了信息增益率的概念

实际上CART分类树与C4.5算法类似，只是属性选择的指标采用的是基尼系数

你可能在经济学中听过说基尼系数，它是用来衡量一个国家收入差距的常用指标

当基尼系数大于0.4的时候，说明财富差异悬殊。基尼系数在0.2-0.4之间说明分配合理，财富差距不大

基尼系数本身反应了样本的不确定度。当基尼系数越小的时候，说明样本之间的差异性小，不确定程度低

分类的过程本身是一个不确定度降低的过程，即纯度的提升过程。所以CART算法在构造分类树的时候，会选择基尼系数最小的属性作为属性的划分

假设t为节点，那么该节点的GINI系数的计算公式为：

这里p(Ck|t)表示节点t属于类别Ck的概率，节点t的基尼系数为1减去各类别Ck概率平方和

通过下面这个例子，我们计算一下两个集合的基尼系数分别为多少：

集合1：6个都去打篮球；集合2：3个去打篮球，3个不去打篮球

针对集合1，所有人都去打篮球，所以p(Ck|t)=1，因此GINI(t)=1-1=0

针对集合2，有一半人去打篮球，而另一半不去打篮球，所以，p(C1|t)=0.5，p(C2|t)=0.5，GINI(t)=1-(0.50.5+0.50.5)=0.5

通过两个基尼系数可以看出，集合1的基尼系数最小，也证明样本最稳定，而集合2的样本不稳定性更大

在CART算法中，基于基尼系数对特征属性进行二元分裂，假设属性A将节点D划分成了D1和D2，如下图所示：

节点D的基尼系数等于子节点D1和D2的归一化基尼系数之和，用公式表示为：

归一化基尼系数代表的是每个子节点的基尼系数乘以该节点占整体父亲节点D中的比例

上面我们已经计算了集合D1和集合D2的GINI系数，分别为0和0.5

所以在属性A的划分下，节点D的基尼系数为：

GINI(D,A)=(6/12)*GINI(D1)+(6/12)*GINI(D2)=0.25

节点D被属性A划分后的基尼系数越大，样本集合的不确定性越大，也就是不纯度越高

如何使用CART算法来创建分类树

在Python的sklearn中，如果我们想要创建CART分类树，可以直接使用DecisionTreeClassifier这个类

基于iris数据集，构造CART分类树的代码如下：

# encoding=utf-8
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris

# 准备数据集
iris = load_iris()
'''
获取特征集和分类标识
特征集：多个特征组成的二维数组，比如：身高、体重
[
    [175,70],
    [163,55],
    ...
]
分类标识：特征集对应的一维数组，比如：性别（1-男，2-女）
[1,2...]
'''
features = iris.data
labels = iris.target

# 随机抽取33%的数据作为测试集，其余为训练集
train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33,
                                                                            random_state=0)
# 创建CART分类树（criterion='gini'表示使用基尼指数）
# gini-基尼指数 mse-最小二乘 mae-最小绝对值 entropy-信息熵（ID3）
clf = DecisionTreeClassifier(criterion='gini')
# 拟合构造CART分类树
clf = clf.fit(train_features, train_labels)
# 用CART分类树做预测
test_predict = clf.predict(test_features)
# 预测结果与测试集结果作比对
score = accuracy_score(test_labels, test_predict)
print("CART分类树准确率 %.4lf" % score)

• X[3]<=0.75：这个节点，选择的属性是X[3]，阈值是0.75，当<=0.75的时候，决策进入到左子树，反之进入到右子树
• gini=0.666：基尼指数为0.666
• samples=100：节点的样本数为100，
• value=[34,31,35]：样本分布，其中34个进入了左节点，另外的进入了右节点
• 继续上面的分裂过程，直到叶子节点，纯度越来越高，最终归为同一个类别时，纯度最高，gini=0

CART回归树的工作流程

CART回归树划分数据集的过程和分类树的过程是一样的，只是回归树得到的预测结果是连续值，而且评判“不纯度”的指标不同

在CART分类树中采用的是基尼系数作为标准，那么在CART回归树中，如何评价“不纯度”呢？实际上我们要根据样本的混乱程度，也就是样本的离散程度来评价“不纯度”

样本的离散程度具体的计算方式是，先计算所有样本的均值，然后计算每个样本值到均值的差值

我们假设x为样本的个体，均值为u。为了统计样本的离散程度，我们可以取差值的绝对值，或者方差

其中差值的绝对值为样本值减去样本均值的绝对值：

方差为每个样本值减去样本均值的平方和除以样本个数：

所以这两种节点划分的标准，分别对应着两种目标函数最优化的标准，即用最小绝对偏差（LAD），或者使用最小二乘偏差（LSD）

这两种方式都可以让我们找到节点划分的方法，通常使用最小二乘偏差的情况更常见一些。我们可以通过一个例子来看下如何创建一棵CART回归树来做预测

基于波士顿房价数据集，该数据集给出了影响房价的一些指标，比如犯罪率，房产税等，最后给出了房价

根据这些指标，使用CART回归树对波士顿房价进行预测，代码如下：

# encoding=utf-8
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_boston
from sklearn.metrics import mean_absolute_error, mean_squared_error
from sklearn.tree import DecisionTreeRegressor

# 准备数据集
boston = load_boston()
# 探索数据（列名）['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO' 'B' 'LSTAT']
print(boston.feature_names)
# 获取特征集和房价
features = boston.data
prices = boston.target
# 随机抽取33%的数据作为测试集，其余为训练集
train_features, test_features, train_price, test_price = train_test_split(features, prices, test_size=0.33)
# 创建CART回归树
dtr = DecisionTreeRegressor()
# 拟合构造CART回归树
dtr.fit(train_features, train_price)
# 预测测试集中的房价
predict_price = dtr.predict(test_features)
# 测试集的结果评价
print('回归树二乘偏差均值:', mean_squared_error(test_price, predict_price))
print('回归树绝对值偏差均值:', mean_absolute_error(test_price, predict_price))

树结构 （提取码: 2gnt）

CART决策树的剪枝

CART决策树的剪枝主要采用的是CCP方法，它是一种后剪枝的方法，英文全称叫做cost-complexity prune，中文叫做代价复杂度

这种剪枝方式用到一个指标叫做节点的表面误差率增益值，以此作为剪枝前后误差的定义。用公式表示则是：

其中Tt代表以t为根节点的子树，C(Tt)表示节点t的子树没被裁剪时子树Tt的误差，C(t)表示节点t的子树被剪枝后节点t的误差

|Tt|代表子树Tt的叶子数，剪枝后，T的叶子数减少了|Tt|-1

所以节点的表面误差率增益值等于节点t的子树被剪枝后的误差变化除以剪掉的叶子数量

因为我们希望剪枝前后误差最小，所以我们要寻找的就是最小α值对应的节点，把它剪掉

这时候生成了第一个子树。重复上面的过程，继续剪枝，直到最后只剩下根节点，即为最后一个子树

得到了剪枝后的子树集合后，我们需要用验证集对所有子树的误差计算一遍

可以通过计算每个子树的基尼指数或者平方误差，取误差最小的那个树，得到我们想要的结果