"> "> 机器学习-决策树 | Yufei Luo's Blog

Yufei Luo's Blog

But I was so much older then, I am younger than that now.

Yufei Luo's Blog

机器学习-决策树

发表于 更新于 分类于 ， 阅读次数：
本文字数： 8.5k 阅读时长 ≈ 8 分钟

概述

定义

决策树模型是一种基本的分类与回归模型，它呈树形结构，可以认为是一系列if-then规则的集合。一棵决策树由结点和有向边组成，结点分成两种：内部结点和叶结点，内部结点表示一个特征或者属性，在分类问题中叶结点表示一个类，而在回归问题中叶结点是一系列数值的集合。用决策树进行分类或者回归时，从根结点开始，对实例的某个特征进行测试，根据测试结果，将实例分配到某个子结点，递归地重复上述过程直至到达叶结点，这个实例的预测值便由叶结点决定。

在分类问题中，决策树还可以表示给定特征条件下类的条件概率分布，这一条件概率分布定义在特征空间的一个划分上。决策树将特征空间划分为互不相交的单元或者区域，并在每个单元定义一个类的概率分布。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。

下图为一个决策树的示意图：

决策树

决策树的学习

以分类问题为例，决策树学习的本质是从训练数据集中归纳出一组分类规则。决策树的分类规则有很多种，我们需要的是一个能够尽量对训练数据进行正确分类的决策树，同时希望它具有很好的泛化能力。如果从概率的角度看，决策树学习是由训练数据集来估计条件概率模型，基于特征空间划分的条件概率模型有无穷多个，因此我们最终选择的模型应该可以对训练数据有很好的拟合，同时也要对未知数据有很好的预测。这一目标可以用损失函数来衡量，因此也就是说决策树学习的策略是损失函数最小化。

当损失函数确定之后，学习问题相当于是在损失函数意义下选择最优的决策树。从所有可能的决策树中选择最优决策树是一个NP完全问题，所以决策树的学习算法通常是采用启发式的方法去近似求解，得到次优的模型。

在决策树学习的开始阶段，所有训练数据全部放在根结点。此时需要选取一个最优特征，按照这一特征将训练数据分割成子集，使得各个子集在当前条件下有一个最好的分类。如果这些子集已经能够被基本正确分类，那么这些子集将被构造成为一个叶结点；如果还有子集无法被正确分类，则需要对这些子集选择新的最优特征，继续对其进行分割。如此递归地进行下去，直到每个子集都被分到叶结点上，这样便生成了一棵决策树。

分类树

特征选择

根据上面的叙述，在决策树的学习过程中，划分数据时的特征选取策略对决策树模型的建立起着决定性的作用。根据特征选取策略的不同，决策树学习算法分为ID3、C4.5和CART三种，下面对其分别进行说明。

值得一提的是，决策树对特征工程的要求不高。决策树可以直接处理数值型与类别型的变量，而且可以直接对缺失值进行处理。

对于数值型的变量，通常对其进行离散化，比如将其分为几个不同的区间，或者是直接使用二分法。

而对于缺失值来说，我们可以将缺失值作为一个特殊的类别来作为划分准则；或是为每个样本都赋予一个权重，然后将缺失值样本划分到每个分支，但是为其赋予一个与其他样本不同的权重。

此外，如果我们基于某个特征进行划分，那么最终得到的划分边界可以认为是一个分段函数，其中每一段都与某个坐标轴平行。为了获得斜的划分边界，有时会对不同的特征进行线性组合，从而增强树的拟合能力，但是这样会相应地使得可解释性变差。

ID3

ID3学习算法使用信息增益作为划分准则，使用信息增益最大的特征进行划分。为了说明信息增益的概念，我们首先需要介绍信息熵的概念。信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合\(D\)中第\(k\)类样本所占的比例为\(p_k,k=1,2,\dots,|\mathcal{Y}|\)，则\(D\)的信息熵定义为： \[ \text{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|}p_k\log_2p_k \] \(\text{Ent}(D)\)的值越小，则\(D\)的纯度越高。

假定离散特征\(a\)（例如西瓜的色泽）有\(V\)个可能的取值\(\{a^1,a^2,\dots,a^V\}\)（例如西瓜色泽有青绿、乌黑、浅白等），如果使用\(a\)来对样本集\(D\)进行划分，则会产生\(V\)个分支结点，其中第\(v\)个分支结点包含了\(D\)中所有在特征\(a\)上取值为\(a^v\)的样本，记作\(D^v\)（例如西瓜色泽为青绿的所有样本）。我们可以计算出\(D^v\)的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支节点赋予权重\(\frac{|D^v|}{|D|}\)，即样本数越多的分支结点的影响越大。据此我们可以计算出使用特征\(a\)对样本集\(D\)进行划分所获得的信息增益： \[ \text{Gain}(D,a)=\text{Ent}(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}\text{Ent}(D^v) \] 一般而言，信息增益越大，则意味着使用特征\(a\)来进行划分所获得的“纯度提升”越大。因此，ID3学习算法选取信息增益最大的特征作为划分准则，即属性\(a_*=\text{argmax}_{a\in A}\text{Gain}(D,a)\)。

C4.5

在使用信息增益准则进行划分时，可能会对取值数目较多的特征有所偏好，为了减少这种偏好所带来的不利影响，C4.5决策树算法使用信息增益率来选择最优划分特征，增益率的定义如下： \[ \text{Gain_ratio}(D,a)=\frac{Gain(D,a)}{IV(a)} \] 其中， \[ IV(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|}\log_2 \frac{|D^v|}{|D|} \] 称为特征\(a\)的“固有值”（Intrinsic Value）。特征\(a\)的可能取值数目越多，则\(IV(a)\)的值通常会越大。

与信息增益相反，信息增益率通常对可取值数目较少的特征有所偏好。因此C4.5算法并不是直接选择增益率最大的候选划分特征，而是先从候选划分特征中找出信息增益高于平均水平的特征，然后从中选取增益率最高的。

CART

CART决策树既可以做分类任务，也可以做回归任务。此处只说明CART做分类任务时的特征选择准则，回归任务将在下文进行说明。CART决策树使用基尼系数来选择划分特征，数据集\(D\)的纯度可以用基尼值来度量： \[ \text{Gini}(D)=\sum_{k=1}^{|\mathcal{Y}|}\sum_{k'\ne k}p_kp_{k'}=1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2 \] 基尼系数越小，表明数据集\(D\)的纯度越高。

我们将特征\(a\)的基尼系数定义为： \[ \text{Gini_index}(D,a)=\sum_{v=1}^{V}\frac{|D^v|}{|D|}\text{Gini}(D^v) \] 因此，我们在候选特征集合\(A\)中，选择那个使得划分之后基尼系数最小的特征作为最优划分特征，即选择\(a_{*}=\text{argmin}_{a\in A}\text{Gini_index}(D,a)\)。

说明：虽然上述的特征选择准则中考虑的是一个特征所有的可能取值，在构造决策树的时候形成一个多叉树。但是通常来讲，这不是一个好办法，与之对应的是使用二叉树（即以是否为某个特征的某个取值作为划分依据）。因为使用特征所有取值进行划分的时候，会将数据过快地分开，从而使得决策树的下一层没有充足的数据再做划分。而使用二叉树可以使得数据的分割速度没有那么快，可以更加充分地使用数据，故实际使用中更倾向于这种方式。

剪枝

通常来说，基于上述准则构造出的决策树容易发生过拟合现象。为了缓解这一现象，通常对决策树采取预剪枝或者后剪枝的办法。

基于验证集的剪枝

决策树的预剪枝需要用到验证集。具体的做法是，先通过训练集生成一个结点划分的结果，然后使用验证集去计算结点划分前后各自的预测性能。通过对比，便可决定是否对一个结点进行划分。预剪枝使得学习过程中一些分支没有展开，这样提高了学习效率，而且降低了过拟合的风险；但是另一方面，一些分支的当前划分虽然使得性能下降，但是后续的划分可能会带来更好的性能，因此预剪枝增大的欠拟合的风险。

后剪枝的过程与预剪枝相反，是在使用训练集构造出一棵决策树之后，再使用验证集去判断是否要剪掉某些分支。这种方法的欠拟合风险较小，但是训练时间开销会很大。

基于损失函数的剪枝

此外，决策树的后剪枝也可以通过极小化决策树整体的损失函数来实现。设决策树\(T\)的叶结点个数为\(|T|\)；\(t\)为树\(T\)的叶结点，该叶结点上有\(N_t\)个样本点，其中类别为\(k(k=1,2,\dots,K)\)的样本点有\(N_{tk}\)个；\(\alpha \ge 0\)为超参数。则决策树的损失函数为： \[ L(T)=-\sum_{t=1}^{|T|}N_t H_t(T)+\alpha |T| \] 其中，\(H_t(T)=-\sum_{k}\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}\)为叶结点\(t\)上的经验熵。

在损失函数中，第一项表示模型对训练数据的预测误差，即模型与训练数据的拟合程度；第二项表示正则化项，用于控制模型的复杂程度，当\(\alpha\)较大时倾向于选择简单的树模型，而\(\alpha\)较小时倾向于选择较复杂的树模型。

根据这一损失函数，可以设计出决策树的剪枝算法：

  1. 计算每个结点的经验熵
  2. 递归地从树的叶结点向上回缩。假设一组叶结点回缩到其父结点之前的决策树为\(T\)，回缩之后为\(T'\)，其对应的损失函数值分别为\(L(T)\)和\(L(T')\)。如果\(L(T')\le L(T)\)，则进行剪枝，将其父结点变为新的叶结点
  3. 重复步骤2，直到不能继续剪枝为止

由于在第2步的剪枝过程中只需要考虑两个树损失函数的差，其计算可以在局部进行，因此可以使用动态规划算法来实现决策树的剪枝（相当于剪枝过程中的一些中间结果可能重复出现，使用动态规划时会将这些中间状态保存起来，从而避免了重复计算）。

CART回归树

原理

CART决策树除了可以做分类任务，还可以完成回归任务。一个回归树对应于特征空间的一个划分，以及在每个划分单元上的一个输出值。假设一棵回归树将输入空间划分为\(M\)个单元\(R_1,R_2,\dots,R_m\)，并且在每个单元\(R_m\)上面有一个固定的输出值\(c_m\)，则回归树模型可以表示为： \[ f(\boldsymbol x)=\sum_{m=1}^{M}c_mI(\boldsymbol x\in R_m) \] 当输入空间的划分确定时，可以用平方误差\(\sum_{\boldsymbol{x}_i\in R_m}(y_i-f(\boldsymbol{x}_i))^2\)来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。此时，单元\(R_m\)上输出值\(c_m\)的最优值\(\hat{c}_m\)是\(R_m\)上的所有输入实例\(\boldsymbol{x}_i\)对应的输出\(y_i\)的均值，即\(\hat{c}_m=\text{avg}(y_i|\boldsymbol{x}_i\in R_m)\)。这样得到的决策树被称为最小二乘回归树。当然，在构造回归树的时候也可以使用其它的损失函数，但是其构造方法基本相同。

要生成训练集上最优的对输入空间划分也是一个NP完全问题，因此在划分时通常采用启发式的方法。当我们选择第\(j\)个特征以及它取的值\(s_j\)作为用于切分的特征和切分点时，可以得到两个区域： \[ R_1(j,s_j)=\{\boldsymbol{x}|x_j\le s_j\}~\&~ R_2(j,s_j)=\{\boldsymbol{x}|x_j> s_j\} \] 通过遍历所有的特征，并对每一个特征求解下面的表达式： \[ \min_{j,s_j}[\min_{c_1}\sum_{\boldsymbol{x}_i\in R_1(j,s_j)}(y_i-c_1)^2+\min_{c_2}\sum_{\boldsymbol{x}_i\in R_2(j,s_j)}(y_i-c_2)^2] \\ \] 其中， \[ \hat{c}_1=\text{avg}(y_i|\boldsymbol{x}_i\in R_1(j,s_j))~\&~\hat{c}_2=\text{avg}(y_i|\boldsymbol{x}_i\in R_2(j,s_j)) \] 即可得到最优的切分特征以及在这一特征上的最优切分点。

接下来，便可以根据所选取的最优切分特征与最优切分点将输入空间划分为两个区域，然后在子区域上重复上述的过程，直到满足停止条件，这样便生成了一棵回归树。

剪枝

对于回归树而言，我们同样可以使用如下的损失函数进行剪枝： \[ L_{\alpha}(T)=L(T)+\alpha |T| \] 其中\(L(T)\)代表平方误差。剪枝的具体步骤与分类树类似，此处不再赘述。

此外，也可以使用递归的方式进行剪枝，即初始时设置\(\alpha=0\)，然后自下而上地进行剪枝，这一过程相当于逐渐增大\(\alpha\)，最终得到一系列的子树序列\(\{T_0,T_1,\dots,T_n\}\)。使用验证集可以从序列中选出一个最合适的决策树\(T_k\)，同时得到与之对应的\(\alpha\)值。

优缺点

优点:

  1. 速度快，计算量相对较小， 且容易转化成分类规则；
  2. 挖掘出来的分类规则便于理解；
  3. 不需要任何参数假设；
  4. 适合高维数据，且对于类别型和数值型的数据都能够很好的处理，而且可以直接处理缺失值。

缺点:

  1. 容易过拟合，可以使用剪枝或者随机森林等方式减小过拟合程度；

  2. 忽略属性之间的相关性，如果要考虑相关性则需要构造多变量决策树；

  3. 决策树模型得到的分类边界或是回归表达式不是光滑的曲线。对于分类问题来说，这影响不是很大；但是对于回归问题来说，可能会有较大的影响，为了解决这一问题可以使用多元自适应回归样条（MARS）算法（具体可查阅ESL的9.4节）

代码示例

分类

我们使用Sklearn自带的Iris数据集，来演示如何用sklearn中的KNN分类器DecisionTreeClassifier做分类任务。

Iris数据集的四个特征分别为：sepal length (cm)、sepal width (cm)、petal length (cm)、petal width (cm)，三种不同的类别0、1、2分别对应于Iris-Setosa、Iris-Versicolour和Iris-Virginica这三类。

为了方便做可视化，我们对数据进行精简，只选取2、3两列来训练与预测模型。我们取petal length (cm)和petal width (cm)这两个特征来训练和预测。

1
2
3
4
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import confusion_matrix
1
2
3
X,y=load_iris(return_X_y=True)
X=X[:,2:4]
train_x,test_x,train_y,test_y=train_test_split(X,y,test_size=0.3)

决策树分类器的主要参数包括：

  • criterion：代表结点的划分准则，默认为gini，即使用基尼系数作为划分准则。也可以使用entropy，代表使用信息增益作为划分准则。
  • max_depth：树的最大深度，默认为None，即没有限制。
  • min_samples_split：结点划分的最小样本数量，默认为2。可以传入一个整数，代表最小样本数量；也可以传入一个0-1的浮点数，代表样本数量占所有样本的比例。
  • min_samples_leaf：一个叶结点最少包含多少个样本，默认为1。传入的数据类型同min_samples_split。
  • max_leaf_nodes：决策树最多有多少个叶结点，默认为None，即无限制。可以传入一个整数来调整叶节点的最大个数。
1
2
3
tree_clf=DecisionTreeClassifier()
tree_clf.fit(train_x,train_y)
pred_y=tree_clf.predict(test_x)

首先我们来看一下混淆矩阵的结果，从中可以看到有少量样本被错误地分类。

1
confusion_matrix(test_y,pred_y)
array([[16,  0,  0],
       [ 0,  9,  1],
       [ 0,  1, 18]], dtype=int64)

接下来我们绘制出模型的分类边界：

1
2
3
X_mesh,Y_mesh=np.meshgrid(np.linspace(0,8,200),np.linspace(0,5,100))
XY_mesh=np.concatenate([X_mesh.reshape(-1,1),Y_mesh.reshape(-1,1)],axis=1)
mesh=tree_clf.predict(XY_mesh)
1
2
3
4
5
6
7
8
9
10
fig=plt.figure(figsize=(8,6))
axes=fig.subplots(1,1)
axes.set_xlabel('sepal length (cm)')
axes.set_ylabel('sepal width (cm)')
contour=axes.contourf(X_mesh,Y_mesh,mesh.reshape(X_mesh.shape),cmap='Greys')
fig.colorbar(contour,ax=axes)
axes.scatter(test_x[test_y==0][:,0],test_x[test_y==0][:,1],label='Iris-Setosa')
axes.scatter(test_x[test_y==1][:,0],test_x[test_y==1][:,1],label='Iris-Versicolour')
axes.scatter(test_x[test_y==2][:,0],test_x[test_y==2][:,1],label='Iris-Virginica')
axes.legend()
决策树分类

从决策树的分类边界可以看到，这些边界都是与坐标轴平行的，也就是说普通的决策树只能得到与坐标轴平行的分类边界。如果要得到不与坐标轴平行的分类边界，则需要构造多变量决策树。

回归

我们使用Sklearn自带的Diabetes数据集，来演示如何用sklearn中的决策树做回归任务。这一数据集共有10个特征，且这些特征都已经被标准化至\((-2,2)\)区间内，待预测的值是25-346范围内的整数。由于我们的目的主要是说明模型的用法，因此省略了特征工程的步骤，将这些数据直接用来训练模型。

1
2
3
from sklearn.datasets import load_diabetes
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor
1
2
X,y=load_diabetes(return_X_y=True)
train_x,test_x,train_y,test_y=train_test_split(X,y,test_size=0.3)

DecisionTreeRegressor回归器的主要参数有：

  • criterion：结点分裂准则，可以使用'mse', 'friedman_mse', 'mae'中的其中一个，默认为'mse'
  • splitter：用于分裂结点的策略，可以使用'best'或者'random'，默认为'best'
  • max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes：与决策分类树相同
1
2
3
4
reg=DecisionTreeRegressor()
reg.fit(train_x,train_y)
pred=reg.predict(test_x)
errors=pred-test_y

参考

  1. 机器学习，周志华
  2. 统计学习方法，李航
  3. The Elements of Statistical Learning
  4. https://www.jianshu.com/p/655d8e555494