机器学习笔记：决策树

作者: 陆仔的自在生活 | 来源:发表于2023-07-04 18:32 被阅读0次

决策树是机器学习中应用很广泛的算法，它不仅可以处理分类和回归问题，还可以产出特征重要性、连续变量分箱等副产物。决策树有着可解释性强、原理简单、效率高的特点。在决策树算法的发展过程中，演变出了不同的派系，因此决策树不是一个单一的算法，而是一系列算法的统称。本文将着重介绍CART决策树的建模流程，并将CART与ID3、C4.5模型做简要对比。

什么是决策树

简单来说，决策树就是通过构建一系列分类规则，将数据归集为某一类别。下图就是一个简单的决策树例子：

L8_001_iris.jpg

树模型的基本结构

决策树可以看作是一个由点和线构成的图结构（有向无环图）。若一条边由A点引向B点，则这条边对于A点来说是出边，对于B点来说是入边，A节点是B节点的父节点。

根节点（root node）：没有入边，但有零条或者多条出边的点；
内部点（internal node）：只有一条入边且有两条或多条出边的点；
叶节点（leaf node）：只有入边没有出边的点。

决策树的分类和流派

决策树算法大致可以分类为：

ID3 (Iterative Dichotomiser 3)、C4.5、C5.0；
CART (Classification and Regression Trees)；
CHAID (Chi-square Automatic Interaction Detection)；

ID3是最为经典的决策树算法，C4.5是在ID3的基础上改进的算法，使得树模型可以处理连续变量（ID3只能处理离散变量），成为目前最通用的决策树模型一般框架，C5.0在C4.5的基础上优化了运行效率与预测流程，但由于C5.0多集成在收费软件中（如：SAS），因此并未像C4.5一样被广泛应用。

CART树，即分类回归树，可以用一套流程同时处理离散变量和连续变量，也可以同时处理分类问题和回归问题。CART的构造过程与C4.5相似，但比C4.5拓展了对于回归问题的处理，这也是CART越来越流行的原因之一。在机器学习库Sklearn中，集成的就是CART作为决策树评估器。因此，本文后续将重点阐述CART的建模流程。

CHAID树是基于卡方检验（Chi-square）的结果来构建的，是一种典型的统计学算法。由于CHAID树不是目前主流的决策树模型，因此我们不在这里多做赘述。

CART树分类问题的建模流程

下面我们将介绍CART分类树的建模流程。我们将采用数据集A作为例子。

【数据集A】

id	income	credit rating	class
1	1	1	0
2	2	2	0
3	2	1	0
4	1	2	1
5	1	1	0
6	1	2	1
7	1	2	1
8	2	1	0

1）分类规则的提取

我们知道决策树是根据一系列的分类指标来将数据集划分为子类的，那么如何提取分类指标成为了首要问题。

对各特征进行排序（降序升序都可以）；
取不同值的中间点作为切点（无论是连续型变量，还是离散型变量，N个取值可以提取出N-1个分类规则）；
CART树为二叉树，即每条分类规则可以将数据集分为两个子数据集。

在数据集A中，我们可以分别对特征 income 和特征 credit rating 进行排序并提取分类规则，其结果如下：

特征 income 排序为：

id	income
2	2
3	2
8	2
1	1
4	1
5	1
6	1
7	1

由于income只有两个取值：1 和 2，因此只有一个切点1.5，分类规则为 income <= 1.5。

特征 credit rating 排序为：

id	credit rating
2	2
4	2
6	2
7	2
1	1
3	1
5	1
8	1

分类规则为 credit rating <= 1.5。

数据集A中的两个特征均为离散变量，若特征为连续变量，如：每条数据的income值都不同，仍然可以采取上述方法，8条数据可以生成7个切点，可以构造出7条分类规则。

2）分类规则的评估

我们通过分类之后子数据集标签的不纯度来评估各分类规则的效果。

分类误差：
$Classification \ Error(t) = 1 - \max_{1\le i \le C}[p(i|t)]$
其中 $i$ 表示第 $i$ 类，数据集总共有 $C$ 类， $t$ 表示整个数据集， $p(i|t)$ 表示第 $i$ 类数据个数占总数据集个数的比例。从公式上不难看出，所谓的分类误差，其实就是数据集中非多数类的数据的占比。分类误差越小，数据集标签纯度越高。
信息熵：
$Entropy(t) = - \sum_{i=1}^{C}p(i|t)\log_{2}p(i|t)$
信息熵越小表示数据集标签纯度越高。ID3、C4.5、C5.0 算法采用信息熵进行分类规则的筛选。
基尼系数：
$Gini(t) = 1 - \sum_{i=1}^{C}p(i|t)^{2}$
基尼系数越小表示数据集标签纯度越高。CART树采用基尼系数进行分类规则的筛选。

当我们需要衡量一个数据集被分为多个子数据集之后，多个子数据集的平均指标，我们可以采用加权平均的方法。例如：对于数据集A，我们可以根据分类指标 income <= 1.5，将其分为 数据集B1和数据集B2两个子数据集：

L8_002.png

数据集B1和数据集B2的加权平均基尼系数 $Gini(B)$ 为：
$Gini(B) = \frac{|B1|}{{|A|}} Gini(B1) + \frac{|B2|}{|A|} Gini(B2)$

数据集A的基尼系数为： $Gini(A) = 1-(5/8)^2-(3/8)^2 = 0.46875$ ；
B1、B2的平均基尼系数： $Gini(B) = (5/8)*Gini(B1)+(3/8)*Gini(B2) = (5/8)*12/25 + (3/8)*0 = 0.3$ 。

3）挑选最佳分类规则

对于每一条备选的分类规则，我们都可以计算出按其分类后的子数据集的平均基尼系数。我们选取分类后（与父数据集相比）基尼系数下降最多的那一条分类规则。

例如，数据集A中，根据 income <= 1.5 分类后，基尼系数下降值为： $Gini(A)-Gini(B) = 0.46875-0.3=0.16875$ ，而根据 credit rating <= 1.5 分类后的基尼系数下降值为： $0.28125$ （此处省略计算过程），那么，我们将选取 credit rating <= 1.5 作为分类规则。

4）决策树的停止生长

每一次决策树子树的生长，可以看作算法的一次迭代过程。而基尼系数（或信息熵、分类误差）可以看作是损失函数，每一次迭代的目标就是尽可能的减少损失函数的值。在机器学习中，通常有两种方式来终止算法的迭代：1）两轮迭代中损失函数差值小于某个值；2）算法已达到设置的最大迭代次数；在决策树中，也可以采用这两种方法来终止决策树的生长：1）当基尼系数的减少值小于某个设定的阈值，则不对数据集进行划分；2）限制决策树模型的最高生长层数。另外，在决策树中，如果备选的分类规则已经耗尽，决策树也会停止生长。

CART树的剪枝

决策树本身是一个很容易过拟合的模型，因此，决策树需要通过剪枝（限制生长）来抑制算法的过拟合。剪枝策略总体可以分为两种：1）在模型生长前就抑制模型生长，称为预剪枝/盆栽法；2）先让模型尽可能生长，再进行剪枝，称为后剪枝/修建法。C4.5和CART都采用后剪枝法，其中C4.5是通过计算叶节点的期望错误率来进行剪枝，而CART是通过类似正则化的方法在计算基尼系数的函数中加入结构复杂度的惩罚因子来进行剪枝的。

在sklearn集成的CART树中，并没有采用上述CART的原生剪枝方法来进行剪枝，而是直接将决定树模型结构复杂度的因素（如：树的层数、每一层分叉的节点数）作为超参数，通过网格搜索的方式，来确定泛化能力最强的树模型结构。

使用Sklearn实现CART分类树

from sklearn.datasets import load_iris
import numpy as np
from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor

X = np.array([[1,1],[2,2],[2,1],[1,2],[1,1],[1,2],[1,2],[2,1]])
y = np.array([0,0,0,1,0,1,1,0])

# 实例化评估器
clf = DecisionTreeClassifier()

# 进行训练
clf.fit(X,y)

# 绘制树状图
import matplotlib.pyplot as plt
from sklearn import tree

plt.figure(figsize=(6,2), dpi=150)
tree.plot_tree(clf)

L8_003.png

DecisionTreeClassifier 重要参数

criterion：不纯度衡量指标；
max_depth：最大生长深度；
max_leaf_nodes：最大叶节点数量；
min_samples_split：内部节点再划分所需最小样本数；
min_samples_leaf：叶节点包含最小样本数；
min_impurity_decrease：数据再划分至少需要降低的损失值；sklearn中在计算父节点和子节点的基尼系数（或信息熵）的差值时，会在计算结果的前面乘以一个父节点占根节点数据量比例的系数作为最终impurity_decrease的结果，当节点样本量很少时，impurity_decrease值会比较低，也在一定程度上抑制了过拟合；
ccp_alpha：结构风险权重，在sklearn的0.22版本中才加入的参数，为实现CART原生原理中的剪枝过程所设置的参数； $R_\alpha(T) = R(T) + \alpha|\widetilde{T}|$ ； $R(T)$ 为决策树在训练集上整体不纯度， $|\widetilde{T}|$ 为树的叶节点数量， $R_\alpha(T)$ 为加入风险结构项后的损失函数， $\alpha$ 取值越大，对模型的结构风险惩罚力度就越大，越能抑制过拟合；

另外，值得注意的是关于控制建模过程中随机性的一些参数，主要包含两个，其一是splitter参数，当该参数取值为random时其实是随机挑选分类规则对当前数据集进行划分，其二是max_features，该参数可以任意设置最多带入几个特征进行备选规律挖掘，当参数的设置值小于全部特征数量，则给树模型的训练增加了一定的随机性。随机性的增加一方面可以加快模型训练速度，另一方面也为成为集成学习的基分类器做好准备。

CART树回归问题的建模流程

CART回归树的建模流程与CART分类树类似，只是在挑选分类规则时，使用MSE作为损失函数，并选取能使MSE下降最多的规则。在计算MSE时，使用被划分后的子集的平均值作为预测值。

$MSE = \frac{1}{m} \sum_{i=1}^{m} (y_{i} - \hat{y}_{i})^2$

除了MSE之外，也可以选取MAE作为损失函数：
$MAE = \frac{1}{m} \sum_{i=1}^{m} |y_{i} - \hat{y}_{i}|$
此时预测值 $\hat{y}_{i}$ 为子集的中位数而非平均数。

如果希望模型能单独为极端值（非常大或非常小的值）设立分类规则，则适用MSE；
如果希望模型能忽略极端值，则适用MAE。

ID3、C4.5、CART对比

	ID3	C4.5	CART
离散变量	√	√	√
连续变量	X	√	√
处理分类问题	√	√	√
处理回归问题	X	X	√
分类规则的提取	按特征列提取规则，每次展开1列； </br> 特征有几个分类，就有几个分支	对于离散变量，按照ID3的方式提取规则；</br> 对于连续变量，按照CART的方式提取规则	对于每一个特征，先排序；</br> 再取不同值的中间点作为切点，提取分类规则
剪枝	X	后剪枝；</br> 计算叶节点的期望错误率	后剪枝； </br> 在计算基尼系数的函数中加入结构复杂度的惩罚因子
分类规则的评估	信息熵；</br> 最大化信息增益	信息熵；</br> 最大化增益率	基尼系数；</br> 最大化基尼系数的减小值
sklearn	X	X	√

信息增益（Information Gain）：
$IG = Entropy(A) - Entropy(B)$

信息值（Information Value）:
$IV = - \sum_{i=1}^{K} p(V_{i}) \log_{2}p(V_{i})$

$K$ 表示划分的总分支个数；
$V_{i}$ 表示划分后的某样本；
$p(V_{i})$ 表示该样本数量占父节点数据量的比例；

增益率（Gain Ratio）：
$Gain Ratio = \frac{Information \ Gain}{Information \ Value}$