关于决策树的一些内容。

决策树的工作原理

决策树是一种非参数的有监督学习方法。它能够从一系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则，以解决分类和回归问题。

决策树算法的本质是一种图结构。

image.png
图来自：陈旸

例如根据上图所示，决策树要做的是根据“天气”、“温度”、“湿度”、“刮风” 4 个特征来判断，最后是否要去打篮球。在整个决策过程中，一直对特征进行提问，并判断出最后结果。最初的问题阶段叫做根节点，在得到结论前的每一个问题都是中间节点，而得到的每一个结论都叫做叶子节点。也就是：

  • 根节点：就是树的最顶端，最开始的节点。没有进边，有出边。在上图中，“天气”就是一个根节点。
  • 内部节点：就是树中间节点。有进边也有出边，进边只有一条，出边可以有很多条，比如说“温度”、“湿度”、“刮风”；
  • 叶节点：就是树最底部的节点。有进边，没有出边。每个叶子节点都是一个类别标签。也就是决策结果。

决策树的构造和剪枝

决策树根据节点的选择、以及节点的多少来决定决策结果。所以对于决策树来说，最重要的 2 个问题：

  1. 如何找出最佳根节点和最佳子节点？
  2. 什么时候停止并得到最佳目标状态。也就是什么时候找出叶节点，防止过拟合？

这两个问题，也就是决策树的构造和剪枝。

剪枝是为了防止过拟合情况出现。过拟合的意思就是模型训练过度，不具备泛化能力。实际场景中，造成过拟合的原因之一就是在训练中样本量太小，决策树选择的特征属性过多，就会把样本特点，当成总体数据特点。
image.png
图来自：陈旸
_
上图第 1 种情况属于欠拟合状态，第 3 种情况属于过拟合状态，第 2 种属于模型泛化能力较好的状态。

另外，剪枝也分为预剪枝和后剪枝：
**

  • 预剪枝：在构造决策树过程中提前停止。例如：指定决策树深度最大为 5，那么训练出来决策树的高度就是 5。预剪枝主要是建立某些规则限制决策树的生长。降低了过拟合的风险，降低了建树的时间，但是有可能带来欠拟合问题。
  • 后剪枝：从训练集生成一棵决策树，然后自下向上对非叶子结点进行考察，若该结点对应的子树用叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。使用“留出法”进行评估。即预留一部分数据用作“验证集”（周志华《机器学习》有较为详细的说明）。

决策树的 3 种算法

在构造决策树时，本质是基于信息纯度来构造。信息纯度可以用信息熵来衡量。信息熵是衡量信息的不确定度或者说不纯度。信息不确定度越大，信息熵越大。

信息纯度的理解，就是目标变量的分歧最小。也就是纯度越低，信息熵越高。举例说明：

场景一：4 次去打篮球，2 次不去打篮球；
场景二：3 次去打篮球，3 次不去打篮球。

以上两种场景下，场景一的信息纯度高于场景二。具体高多少，就用信息熵来对比衡量。信息熵公式：

image.png
在决策树算法中，基于信息纯度构造的常用算法有 3 种，分别是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指数（Cart 算法）。

信息增益（ID3 算法）

信息增益指的是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父节点的信息熵减去所有子节点的信息熵。在计算的过程中，我们会计算每个子节点的归一化信息熵，即按照每个子节点在父节点中出现的概率，来计算这些子节点的信息熵。所以信息增益的公式可以表示为：
image.png
简单来说，信息熵越小，信息增益越大，样本纯度越高，选择信息增益最大的特征作为分裂标准。ID3 算法流程：

  1. 自上而下，遍历所有的特征值；
  2. 计算每个节点信息增益，将信息增益最大的节点作为父节点；
  3. 根据分裂属性划分内部节点；
  4. 重复上述流程，直至满足条件结束。

ID3 算法特点：

  1. 有些属性可能对分类任务没有太大作用，但是仍然可能会被选为最优属性；
  2. ID3 算法倾向于选择取值比较多的属性。例如：把“编号”作为一个属性，那么“编号”将会被选为最优属性；
  3. 不适用于连续变量，只能用于分类。

信息增益率（C4.5 算法）

信息增益率（C4.5算法）是在 ID3 算法上进行改进的一种算法。主要改进点有：

  • 采用信息增益率。因为 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵。当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5 来说，属性熵也会变大，所以整体的信息增益率并不大。
  • 采用悲观剪枝。ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5 中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。
  • 离散化处理连续属性。C4.5 可以对连续属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢。C4.5 选择具有最高信息增益的划分所对应的阈值。
  • 处理缺失值。针对数据集不完整的情况，C4.5 也可以进行处理。这种算法会在最后使用已有数据样本值 / 总体值*信息增益率。

基尼指数（Cart 算法）

ID3 和 C4.5 算法可以生成二叉树或多叉树，而 CART 只支持二叉树。并且，Cart 算法既可以做决策树分类，也可以用做回归。分类树可以处理离散数据，也就是数据种类有限的数据，它输出的是样本的类别，而回归树可以对连续型的数值进行预测，也就是数据在某个区间内都有取值的可能，它输出的是一个数值。

Cart 算法分类树

ID3 是基于信息增益做判断，C4.5 在 ID3 的基础上做了改进，提出了信息增益率的概念。实际上 CART 分类树与 C4.5 算法类似，只是属性选择的指标采用的是基尼系数。

基尼系数本身反应了样本的不确定度。当基尼系数越小的时候，说明样本之间的差异性小，不确定程度低。分类的过程本身是一个不确定度降低的过程，即纯度的提升过程。所以 CART 算法在构造分类树的时候，会选择基尼系数最小的属性作为属性的划分。GINI 系数的计算公式：
image.png

基尼系数算法举例：

  • 场景一：6 个都去打篮球。所有人都去打篮球，所以 p(Ck|t) = 1，因此 GINI(t) = 1 - 1 = 0
  • 场景二：3 个去打篮球，3 个不去打篮球。有一半人去打篮球，而另一半不去打篮球，所以，p(C1|t) = 0.5，p(C2|t) = 0.5，GINI(t) = 1 -（0.5 * 0.5 + 0.5 * 0.5）= 0.5

通过两个基尼系数你可以看出，场景一基尼系数最小，也证明样本最稳定，而场景二样本不稳定性更大。
**
案例说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 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()

# 获取特征集和分类标识
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分类树
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)
1
CART分类树准确率 0.9600
Cart 算法回归树

CART 回归树划分数据集的过程和分类树的过程一样，只是回归树得到的预测结果是连续值，而且评判“不纯度”的指标不同。在 CART 分类树中采用的是基尼系数作为标准，在 CART 回归树中，采用最小绝对偏差（LAD），或者最小二乘偏差（LSD）作为节点划分的依据，得到的是连续值，即回归预测结果。

样本的离散程度具体的计算方式是，先计算所有样本的均值，然后计算每个样本值到均值的差值。假设 x 为样本的个体，均值为 u。为了统计样本的离散程度，可以取差值的绝对值，或者方差。

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

image.png

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

所以这两种节点划分的标准，分别对应着两种目标函数最优化的标准，即用最小绝对偏差（LAD），或者使用最小二乘偏差（LSD）。这两种方式都可以让我们找到节点划分的方法，通常使用最小二乘偏差的情况更常见一些。

案例说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# encoding=utf-8
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_boston
from sklearn.metrics import r2_score,mean_absolute_error,mean_squared_error
from sklearn.tree import DecisionTreeRegressor

# 准备数据集
boston=load_boston()

# 探索数据
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)) 
1
2
3
['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO' 'B' 'LSTAT']
回归树二乘偏差均值: 23.80784431137724
回归树绝对值偏差均值: 3.040119760479042
Cart 算法决策树的剪枝

CART 决策树的剪枝主要采用的是 CCP 方法，一种后剪枝的方法。这种剪枝方式用到一个指标叫做节点的表面误差率增益值，以此作为剪枝前后误差的定义。用公式表示则是：
image.png
其中 Tt 代表以 t 为根节点的子树，C(Tt) 表示节点 t 的子树没被裁剪时子树 Tt 的误差，C(t) 表示节点 t 的子树被剪枝后节点 t 的误差，|Tt|代子树 Tt 的叶子数，剪枝后，T 的叶子数减少了|Tt|-1。

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

因为我们希望剪枝前后误差最小，所以我们要寻找的就是最小α值对应的节点，把它剪掉。这时候生成了第一个子树。重复上面的过程，继续剪枝，直到最后只剩下根节点，即为最后一个子树。得到了剪枝后的子树集合后，我们需要用验证集对所有子树的误差计算一遍。可以通过计算每个子树的基尼指数或者平方误差，取误差最小的那个树，得到我们想要的结果。