返回主目录
返回决策树目录
上一章：机器篇——决策树(三)
下一章：机器篇——决策树(五)
本小节，细说 CART 算法，下一小节开始细说 评估指标的相关曲线(ROC、KS、PR)。
二. 算法细说
5. CART 算法
(1). CART 分类树算法的最优特征选择方法
①. 在 ID3 算法中使用了信息增益来选择特征，信息增益大的优先选择。在 C4.5算法中，采用了信息增益率来选择特征以减少信息增益容易选择特征值多的特征问题。但是，无论是 ID3，还是 C4.5，都是基于信息论的熵模型的，这里面会涉及大量的对数运算。
②. CART 分类树算法使用基尼系数来代替信息增益率，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(率)是相反的。
③. 具体的，在分类问题中，假设有 个类别，第 个类别的概率为 ，则基尼系数表达式为：
如果是二分类问题，计算就更加简单了如果属于第一个样本输出的概率为 ，则基尼系数的表达式为：
对于给定的样本 ，假设有 个类别，第 个类别的数量为 ，则样本 的基尼系数表达式为：
特别的，对于样本 ，如果根据特征 的某个值 ，把 分成 和 两类别，则在特征 的条件下， 的基尼系数表达式为：
④. 基尼系数与 Gain 的表达式：
a. 分类树：Gini值
(a). Gini 值的计算公式；
(b). 节点越不纯，Gini 值越大，效果越差；越纯，Gini 值越小，效果越好。以二分类为例，如果节点的所有数据只有一个类别，则：
(c). 如果两类数量相同，则：
(d). Gini 值的计算
b. 回归树：回归方差
(a). 回归方差计算公式：
(b). 如果两类数量相同，则方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据都相同，那么方差就为零。此时可以很肯定的认为该节点的输出值。如果节点的数据相差很大，那么输出的值有很大的可能与实际值相差较大。回归方差越小，效果越好。
(c). 值的计算
⑤. 基尼系数可以做为熵模型的一个近似替代。
而 CART 分类树算法就是使用的基尼系数来选择决策树的特征。同时，为了进一步简化，CART 分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样 CART 分类树算法建立起来的是二叉树，而不是多叉树。这样一可以进一步简化基尼系数，二可以简历一个更加优雅的二叉树。
(2). CART 分类树算法对于连续特征和离散特征处理的改进
①. 对于 CART 分类树连续值的处理问题，其思路和 C4.5 是相同的，都是将连续的特征离散化。唯一的区别在于选择划分点时的度量方式不同，C4.5使用的是信息增益率，而 CART 分类树使用的是基尼系数。
②. 具体思路：
比如 个样本的连续特征 有 个，从小到大排列为：，则 CART 算法取相邻两个样本值的平均数，一共取到 个划分点，其中第 个划分点 表示为：
对于这 个点，分别计算以该点作为二元分类点的基尼系数。选择基尼系数最小的点作为该连续特征的二元分类点。比如取到的基尼系数最小的点为 ，则小于 的值为类别 1，大于 的值为类别 2。这样就座到了连续特征的离散化。
要注意的是，与 ID3 或 C4.5 处理离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参加与子节点的产生选择过程。
③. 对于 CART 分类树离散值的处理问题，采用的思路是不停的二分离散特征。
④. 在 ID3 和 C4.5 中，如果某个特征 被选建立决策树节点，如果它有 三种类别，一般会在决策树一下建立一个三叉的节点。这样导致决策树是多叉树。但是 CART 分类树使用的方法不同，它采用的事不停的二分。还是这个例子，CART 分类树会考虑把 分为 和 ， 和 ， 和 三种情况，然后建立二叉树节点，一个节点是 对应的样本，另一个节点是 对应的节点。同时，由于这次没有把特征 的取值完全分开，后面还有机会在子节点继续选择到特征 来划分 和 。
这和 ID3 和 C4.5 不同，在 ID3 或 C4.5 的一棵树中，离散特征只会参与一次节点的建立。
(3). CART 分类树建立算法的具体流程
算法输入的训练集 ，基尼系数的阈值，样本个数阈值，输出是决策树 。
CART 算法从根节点开始，用训练递归建立 CART 树。
①. 对于当前节点的数据集为 ，如果样本数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。
②. 计算样本集 的基尼系数，如果基尼系数小于阈值，则返回决策子树，当前节点停止递归。
③. 计算当前节点现有的各个特征的各个特征值对数据集 的基尼系数，对于离散值和连续值的处理方法和基尼系数的计算。缺失值的处理方法和 C4.5 算法中描述的相同。
④. 在计算出的各个特征值对数据集 的基尼系数中，选择基尼系数小的特征 和对应的特征 。跟进这个最优特征和最优特征值，把数据划分成两部分 和 ，同时建立当前节点的左右节点，左节点的数据集 为 ，右节点的数据集 为 。
⑤. 对左右的子节点递归的调用 ①~④ 步骤，生成决策树。
对于生成的决策树预测的时候，假如测试集里的样本 落到了某个叶子节点，而节点里有多个训练样本。则对于 的类别预测采用的是这个叶子节点里概率最大的类别。
(4). CART 回归树建立算法
①. CART 回归树和 CART 分类树的建立算法大部分是类似的。
②. 回归树和分类树的区别在于样本的输出，如果样本输出是离散值，那么这是一棵分类树。如果样本输出是连续值，那么这是一棵回归树。
③. CART 回归树和 CART 分类树除了概念的不同，它们的建立和预测的区别主要有以下两点：
a. 连续值的处理方法不同。
b. 决策树建立后做预测的方式不同。
④. 对于连续值的处理，CART 分类树采用的是基尼系数的大小来度量特征的各个划分点的优劣情况。这比较适合分类模型。但是，对于回归模型，则使用常见的方差的度量方式。CART 回归树的度量标准是，对于任意划分特征 ，对应的任意划分点 两边划分成数据集 和 ，求出使用 和 各自集合的均方差最小，同时 和 的均方差之和最小所对应的特征和特征值划分点。表达式为：
：为 数据集的样本输出均值
：为 数据集的样本输出均值
⑤. 对于决策树建立后做预测的方式，CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的事用最终叶子的均值或中位数来预测出结果。
⑥. 除了上面提到的之外，CART 回归树和 CART 分类树的建立算法和预测没有什么区别。
(5). CART 树算法的剪枝
①. CART 回归树和 CART 分类树的剪枝策略除了在度量损失的时候一个使用均方差，一个使用基尼系数，算法基本完全一样。
②. 由于决策时算法很容易对训练集过拟合，而导致泛化能力差，为了解决这个问题，需要对 CART 树进行剪枝，即类似于线性回归的正则化，用来增加决策树的泛化能力。CART 树采用的是后剪枝法，即先生成决策树，然后再产生所有可能的剪枝后的 CART 树，之后，使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。也就是说，CART 树的剪枝算法可以概括为两步：
a. 第一步，是从原始决策树生成各种剪枝效果的决策树。
b. 第二步，是用交叉验证来检验剪枝后的预测能力，选择泛化能力最好的剪枝后的树作为最终的 CART 树。
③. 剪枝的损失函数度量，在剪枝的过程中，对于任意的一棵子树 ，其损失函数为：
：为训练数据的预测误差，分类树用基尼系数度量，回归树是均方差度量。
：是子树 的叶子节点的数量。
：为正则化参数，这和线性回归的正则化一样。
当 时，即没有正则化，原始生成的 CART 树即为最优子树。
当 时，即正则化强度达到最大，此时由原始生成的 CART 树的根节点组成的单节点树为最优子树。
当然，这是两种极端情况。一般来说， 越大，则剪枝剪得越厉害，生成的最优子树比原生决策树就越偏小。对于固定的 ，一定存在使损失函数 最小的唯一子树。
④. 看过剪枝的损失函数度量后，再看看剪枝的思路，对于位于节点 的任意一棵子树 ，如果没有剪枝，它的损失是：
如果将其剪掉，仅仅保留根节点，则损失是：
当 或 很小时，
当 增大到一定的程度时，
当 继续增大时，不等式反向，也就是说，如果满足下式：
和 有相同的损失函数，但是 节点更少，因此可以对子树 进行剪枝，也就是将它的子节点全部剪掉，变成一个叶子节点
⑤. CART 树的交叉验证策略
CART 树可以计算出每个子树是否剪枝的阈值 ，如果把所有的节点是否剪枝的值都计算出来，然后分别对不同的 所对应的剪枝后的最优子树做交叉验证。这样，就可以选择一个最好的 ，有了这个 ，就可以用对应的最优子树作为最终结果。
⑥. 算法过程：
：CART 树建立算法得到的原始决策树。
：最优决策子树
a. 初始化 ，最优子树集合
b. 从叶子节点开始自下而上计算各内部节点 的训练误差损失函数 (回归树为均方差，分类树为基尼系数)。叶子节点数 ，以及正则化阈值：
更新
c. 得到所有节点的 值的集合 。
d. 从 中选择最大的值 ，自上而下的访问子树 的内部节点，如果 时， 进行剪枝。并决定叶子点的 的值。如果是分类树，则是概率最高的类别；如果是回归树，则是所有样本输出的均值。这样得到 对应的最优子树 。
e. 最优子树集合
f. 如果 不为空，则回到步骤 d。否则就已经得到了是所有的可选最优子树集合 。
g. 采用交叉验证在 选择最优子树
⑦. ID3、C4.5、CART 树的结构
⑧. 决策树算法的优缺点
a. 优点
(a). 简单直观，生成的决策树很直观
(b). 基本不需要预处理，不需要提前归一化，处理缺失值。
(c). 使用决策树预测的代价是 。 为样本数
(d). 既可以处理离散值，也可以处理连续值。很多算法只是专注于离散值或连续值。
(e). 可以处理多维度输出的分类问题。
(f). 相比于神经网络之类的分类模型，决策树在逻辑上得到很好的解释。
(g). 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
(h). 对于异常点的容错能力好，健壮性高
b. 缺点
(a). 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进
(b). 决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决
(c). 寻找最优的决策树是一个 NP 难度的问题，一般是通过启发式方法，容易陷入局部最优解。可以通过集成学习之类的方法来改善。
(d). 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
(e). 如果某些特征的样本比例过大，成长决策树容易偏向于这些特征。这样可以通过调节样本权重来改善。
(6). 决策树代码
#!/usr/bin/env python
# _*_ coding:utf-8 _*_
# ============================================
# @Time : 2020/01/02 22:11
# @Author : WanDaoYi
# @FileName : dec_tree_test.py
# ============================================import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
from sklearn.tree import DecisionTreeRegressorimport matplotlib.pyplot as plt
import matplotlib
# 用于解决画图中文乱码
font = {"family": "SimHei"}
matplotlib.rc("font", **font)# 加载 iris 数据
iris_info = load_iris()# 读取 iris 的 data 数据 (x)
iris_data = pd.DataFrame(iris_info.data)
print(iris_data.head())# 获取 data.columns 列属性名称
iris_data.columns = iris_info.feature_names
print(iris_data.columns)# 获取 iris label 数据
label_info = iris_info.target# 将 data 数据与 label 数据拼接 有 x 有 y 的成完整的数据。
iris_data["Species"] = label_infoprint(iris_data.head())# 读取前面的 4 列，即 x，花萼长度和宽度
x = iris_data.iloc[:, : 4]
# 读取最后 1 列，即 y，花的类别
y = iris_data.iloc[:, -1]# 划分训练集和验证集
# train_size:训练数据比例
# random_state:随机种子，保证每次随机数据一致
x_train, x_val, y_train, y_val = train_test_split(x, y, train_size=0.7, random_state=42)# DecisionTreeClassifier 分类
# DecisionTreeRegressor 回归
# criterion='entropy' 表示信息增益；criterion='gini' 表示基尼系数。
# dec_tree = DecisionTreeClassifier(max_depth=6, criterion='entropy')
dec_tree = DecisionTreeClassifier(max_depth=2, criterion='gini')# 训练
dec_tree.fit(x_train, y_train)# 预测
y_pred = dec_tree.predict(x_val)
acc_score = accuracy_score(y_val, y_pred)
print("acc_score: {}".format(acc_score))# 下面是通过循环去训练15棵树，并绘制出每棵树的错误率图表,
# 通过这个方法，可以获得效果较好，深度较浅的树。
# 生成一个数组，存放 1-15 个 depth
max_depth = np.arange(1, 15)
err_list = []
for depth in max_depth:max_dec_tree = DecisionTreeClassifier(criterion="entropy", max_depth=depth)# max_dec_tree = DecisionTreeClassifier(criterion="gini", max_depth=depth)max_dec_tree.fit(x_train, y_train)max_y_pred = max_dec_tree.predict(x_val)result = (max_y_pred == y_val)if depth == 1:print(result)err = 1 - np.mean(result)print(100 * err)err_list.append(err)print("depth: {}, 错误率: {}".format(depth, 100 * err))plt.figure(facecolor='w')
plt.plot(max_depth, err_list, 'ro-', lw=2)
plt.xlabel('决策树深度', fontsize=15)
plt.ylabel('错误率', fontsize=15)
plt.title('决策树深度和过拟合', fontsize=18)
plt.grid(True)
plt.show()
返回主目录
返回决策树目录
上一章：机器篇——决策树(三)
下一章：机器篇——决策树(五)