一天一个机器学习小知识——决策树

小知识——决策树"/>

一天一个机器学习小知识——决策树

文章目录

• 前言
• 一、算法推导
• • 1.模型
  • 2.策略
  • 3.算法
  • • 3.1 ID3（信息增益最大）
    • 3.2 C4.5 （信息增益率最大）
    • 3.3 CRAT（基尼系数最小）
    • 3.4 剪枝
• 二、应用场景
• 三、代码实现
• • 1.导入相关库
  • 2.读取样例数据
  • 3.划分训练集和测试集
  • 4.建立模型
• 四、优缺点
• • 1.优点
  • 2.缺点

前言

本文主要介绍一个常见的分类算法——决策树。决策树虽然简单，但是它的结果非常直观，容易理解和解释，并且它是很多集成模型的基学习器，在机器学习中具有重要的地位。

一、算法推导

李航老师的《统计学习方法》中提到，统计学习方法都是由模型、策略和算法构成的，因此本文在算法推导也主要从这三部分进行展开讨论。

1.模型

决策树模型并不像之前介绍的模型那样存在一个显式的表达式，它的最终模型呈现一个树形结构，本质上是使用特征对实例进行分类的过程。整个模型可以分为三步：选择最优划分特征、生成决策树和剪枝。
最终决策树模型如图所示：

图片来源于周志华老师的《机器学习》

2.策略

上面提到决策树模型没有显式表达式，那么它是否有显式的损失函数呢？其实是有的，它的损失函数如下所示：
C α ( T ) = ∑ t = 1 ∣ T ∣ N t H t ( T ) + α ∣ T ∣ C_{\alpha}(T)=\sum_{t=1}^{|T|} N_{t} H_{t}(T)+\alpha|T| Cα​(T)=t=1∑∣T∣​Nt​Ht​(T)+α∣T∣其中 ∣ T ∣ |T| ∣T∣是决策树的叶子节点数， t t t是决策树的叶子节点，该节点有 N t N_t Nt​个样本点，其中 k k k类样本点有 N t k N_{tk} Ntk​个， k = 1 , 2 , . . . , K k=1,2,...,K k=1,2,...,K， H t ( T ) H_{t}(T) Ht​(T)为叶子节点t上的经验熵， α > = 0 \alpha >=0 α>=0为正则化参数。
经验熵为：
H t ( T ) = − ∑ k N t k N t log ⁡ N t k N t H_{t}(T)=-\sum_{k} \frac{N_{t k}}{N_{t}} \log \frac{N_{t k}}{N_{t}} Ht​(T)=−k∑​Nt​Ntk​​logNt​Ntk​​怎么理解这个损失函数呢？或者说为什么这个函数就能够用来衡量决策树的好坏?
首先看正则项 α ∣ T ∣ \alpha |T| α∣T∣，这个比较容易理解，它主要是用来控制决策树的复杂度，一般来说叶子节点数越多，模型越复杂，模型也就越不好。
比较费解的是 ∑ t = 1 ∣ T ∣ N t H t ( T ) \sum_{t=1}^{|T|} N_{t} H_{t}(T) ∑t=1∣T∣​Nt​Ht​(T)，直观上理解就是T个节点的损失相加，然后 N t N_t Nt​代表每个节点的权重，问题是 H t H_t Ht​为什么就能代表每个节点的损失呢？
其实我们在讨论决策树的时候经常会讨论到“纯度”这个词，纯度越高的树就是越好的（因为能够完全分类，这个不理解可以参考后面选择最优特征这一部分）。回到 H t ( T ) H_{t}(T) Ht​(T)，如果叶子节点t纯度非常高，只有一种类别的样本i，那么此时 N i k = N t N_{ik}=N_t Nik​=Nt​,而 N j k = 0 , j ≠ i N_{jk}=0, j≠i Njk​=0,j​=i，代入到 H t ( T ) H_{t}(T) Ht​(T)中就会得到 H t ( T ) = − [ 1 ∗ l o g 1 + 0 ∗ l o g 0 + . . . . + 0 ∗ l o g 9 ] = 0 H_{t}(T)=-[1*log1 + 0*log0 + ....+ 0*log9]=0 Ht​(T)=−[1∗log1+0∗log0+....+0∗log9]=0，也就是说此时损失为0。
决策树的损失函数主要是用于决策树最后的剪枝部分，对于决策树的生成部分，我们在算法部分重点讲解。

3.算法

虽然上一小节介绍了损失函数，但是我们发现它好像跟决策树的生成过程联系不大，因为决策树的生成主要是取决于特征的选择，所以这一部分我们重点介绍决策树中是如果选择最优划分特征的。
我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。
所以我们每次应该选择那个使得决策树纯度提升最大的特征。既然如此，我们首先要对纯度进行定义，一般使用信息熵来衡量纯度。
Ent ⁡ ( D ) = − ∑ k = 1 ∣ Y ∣ p k log ⁡ 2 p k \operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log _{2} p_{k} Ent(D)=−k=1∑∣Y∣​pk​log2​pk​其中 p k p_k pk​表示第k类样本所占的比例， E n t ( D ) Ent(D) Ent(D)值越小，则D的纯度越高（具体解释可参考上一小节关于 H t ( T ) H_{t}(T) Ht​(T)的介绍）。

3.1 ID3（信息增益最大）

一开始的时候，整个样本属于一个节点，此时熵为 E n t ( D ) Ent(D) Ent(D)，如果选择属性 a a a作为划分属性，假设划分后会产生 V V V个分支，那么此时熵为这 V V V个分支的加权和。即划分后的熵为：
∑ v = 1 V ∣ D v ∣ ∣ D ∣ Ent ⁡ ( D v ) \sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right) v=1∑V​∣D∣∣Dv∣​Ent(Dv)那么整个划分过程所带来的信息增益就等于
Gain ⁡ ( D , a ) = Ent ⁡ ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Ent ⁡ ( D v ) \operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right) Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。
所以我们要做的是遍历所有的特征，计算每个特征划分后所带来的信息增益，然后选择信息增益最大那个特征作为我们的最后划分特征，来对节点进行一轮划分。
但是ID3有个缺陷，就是对可取数目较多的属性有所偏好。比如说，把样本的索引也作为一个划分属性，那么它将产生N（样本数量）叶子节点，每个叶子节点只包含一个样本，这些节点的纯度已达到最大，然而这样的决策树不具有泛化能力，无法对新样本进行预测。

3.2 C4.5 （信息增益率最大）

为了避免ID3算法偏好可取值数目较多的属性的缺陷，C4.5使用增益率来选择最优划分属性。增益率定义为：
G a i n _ r a t i o ( D , a ) = Gain ⁡ ( D , a ) IV ⁡ ( a ) Gain\_ratio (D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)} Gain_ratio(D,a)=IV(a)Gain(D,a)​
其中 I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ log ⁡ 2 ∣ D v ∣ ∣ D ∣ \mathrm{IV}(a)=-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \log _{2} \frac{\left|D^{v}\right|}{|D|} IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​其中IV(a)称为属性的固有值，属性a的可能取值数目越多，则IV(a)的值通常越大。但是C4.5又有个缺陷，增益率准则对可取值数目较少的属性有所偏好
因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用一个启发式算法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性。

3.3 CRAT（基尼系数最小）

事实上，最常用的筛选指标应该是基尼系数，它也是CRAT（Classification and Regression Tree）中所采用的指标：
Gini ⁡ ( D ) = ∑ k = 1 ∣ Y ∣ ∑ k ′ ≠ k p k p k ′ = 1 − ∑ k = 1 ∣ Y ∣ p k 2 \begin{aligned} \operatorname{Gini}(D) &=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_{k} p_{k^{\prime}} \\ &=1-\sum_{k=1}^{|\mathcal{Y}|} p_{k}^{2} \end{aligned} Gini(D)​=k=1∑∣Y∣​k′​=k∑​pk​pk′​=1−k=1∑∣Y∣​pk2​​ p k p_{k} pk​为D中第k类样本所占比例，直观上来看，基尼系数表示从数据集D中随机抽取两个样本，其类别标记不一致的概率。基尼系数越小，纯度越高。
属性a的基尼指数定义为：
Gini index  ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Gini ⁡ ( D v ) \text { Gini index }(D, a)=\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Gini}\left(D^{v}\right)  Gini index (D,a)=v=1∑V​∣D∣∣Dv∣​Gini(Dv) 我们要做的就是选择一个划分属性，使得划分后，样本的基尼系数最小
a ∗ = arg ⁡ min ⁡ a ∈ A Gini ⁡ − index ⁡ ( D , a ) a_{*}=\underset{a \in A}{\arg \min } \operatorname{Gini}_{-} \operatorname{index}(D, a) a∗​=a∈Aargmin​Gini−​index(D,a)

3.4 剪枝

如果决策树每个叶子节点只包含一个样本，这时候纯度肯定是最高的，但是这时候决策树过于复杂，容易过拟合，所以我们需要对决策树进行剪枝。
剪枝又可以分为预剪枝和后剪枝。
预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能（比如验证集上的准确率）的提升，则停止划分并将当前结点标记为叶节点。
后剪枝是指先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该结点对应地子树替换成叶节点能够带来决策树泛化性能提升，则将该子树替换成叶子结点，即剪枝。

二、应用场景

（1）非常适合离散特征，对于离散特征，其他很多模型都需要对其进行编码，得到稀疏的编码向量再进行模型拟合，决策树直接对离散特征进行分析。
（2）能够生成清晰的基于特征(feature)选择不同预测结果的树状结构，数据分析师希望更好的理解手上的数据的时候往往可以使用决策树。
（3）作为很多集成学习模型的基学习器

三、代码实现

这里主要使用sklearn这个库来实现机器学习算法。

1.导入相关库

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_breast_cancer
from sklearn.metrics import accuracy_score
import pandas as pd
import numpy as np

2.读取样例数据

data = load_breast_cancer() # 获取样例数据，这里的数据乳腺癌检测,y=0代表没有乳腺癌，y=1代表有
X = pd.DataFrame(data.data,columns=data.feature_names)
y = data.target

3.划分训练集和测试集

X_train, X_test, y_train, y_test =train_test_split(X,y,test_size=0.3,random_state=0)

4.建立模型

model = DecisionTreeClassifier().fit(X_train,y_train)
y_pred = model.predict(X_test)
## 5.评估模型
由于是分类问题，所以我们可以直接使用准确率来评估模型
```python
print('ACC:%.3f'%(accuracy_score(y_test,y_pred)))
ACC:0.924

其实上面用的方法是留出法，我们也可以使用交叉验证法来计算模型误差。这样就把划分训练集和测试集、建立模型以及评估模型这几步合并在一起。

acc = np.mean(cross_val_score(DecisionTreeClassifier(),X,y,cv=10,scoring='accuracy'))
print('ACC:%.3f'%(acc))
ACC:0.905

可以看到两者比较接近。

四、优缺点

1.优点

（1）易于理解和解释
（2）非参数型
（3）模型可以通过树的形式进行可视化展示
（4）可以直接处理非数值型数据，不需要进行哑变量的转化，甚至可以直接处理含缺失值的数据

2.缺点

（1）容易过拟合
（2）对于有大量数值型输入和输出的问题，决策树未必是一个好的选择
（3）模型不够稳健，某一个节点的小小变化可能导致整个树会有很大的不同（即模型容易受到攻击）