决策树【python实现】

作者: To_QT | 来源:发表于2019-07-09 11:47 被阅读0次

决策树思维导图.jpg

0.周董歌词中的决策树

为什麼别人在那看漫画我却在学画画对著钢琴说话
别人在玩游戏我却靠在墙壁背我的ABC
拿王牌谈个恋爱而我不想被你教坏
还是听妈妈的话吧晚点再恋爱吧
长大後我开始明白为什麼我跑的比别人快飞的比别人高

周董妈告诉我们，想跑的比别人快飞的比别人高，就要学画画，练钢琴，背ABC，不要打游戏，早恋。这是成材的规则。决策树，就是这种规则的集合。

1.真正的决策树

在决策树中，一棵决策树包含一个根节点，若干个内部节点和若干个叶节点。

image.png

在《西瓜书》中提到，有三种情况会导致算法返回：

当前结点包含的样本全属于同一类别，无需划分。
当前属性集为空，或所有样本在所有属性上的取值相同，无法划分：把当前结点标记为叶节点，并将其类别设定为该结点所含样本最多的类别。

属性集为空的情况：假设有六个特征，六个特征全部用完发现，数据集中还是存在不同类别数据的情况。

当前特征值全都相同，在类别中有不同取值。

当前结点包含的样本集合为空，不能划分：将类别设定为父节点所含样本最多的类别。

出现这个情况的原因是：在生成决策树的过程中，数据按照特征不断的划分，很有可能在使用这个特征某一个值之前，已经可以判断包含该特征值的类别了。所以会出现空的情况。

2.划分选择

那么，在决策树中，怎么选择特征进行划分？以西瓜数据集为例。

西瓜数据集2.0镇楼

2.1信息增益

信息熵

用于度量样本集合的纯度，代表一个系统中蕴含信息量的多少，熵越小，信息量越少，纯度越高，不确定性就越小。单位为：比特或者纳特。
假定当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k,k=1,2,...,|Y|$ ，则 $D$ 的信息熵，计算公式为（在《统计学习方法》中，也用 $H(D)$ 表示 $Ent(D)$ ）：

信息熵极值公式推导^[1]

当样本 $D$ 中 $|y|$ 类样本均匀分布时，信息熵最大，
$Ent(D)=-\sum_{k=1}^{|Y|} \frac{1}{|y|}log_2\frac{1}{|y|}=log_2|y|$

《统计学习方法》P60
当样本 $D$ 中的 $|y|$ 只有一个值的时候，信息熵最小
$Ent(D)=-\sum_{k=1}^{|Y|} \frac{1}{|y|}log_2\frac{1}{|y|}=-1log_21-0log_20-...-0log_20 = 0$

$Ent(D)=-\sum_{k=1}^{|Y|}p_klog_2p_k \tag{2.1}$

西瓜数据集中，“好瓜”标签下只有“是”与“否”，因此 $|Y|=2$ ，是好瓜的有8个，不是好瓜的有9个，所以信息熵为

条件熵

两个随机变量 $X$ 、 $Y$ 可以形成联合熵 $H(X,Y)$ ，条件熵为：表示 $(X,Y)$ 发生所包含的熵，去掉 $X$ 单独发生的熵<=>在 $X$ 条件发生的条件下， $Y$ 发生所产生的熵。
理解：
$\begin{align} H(Y|X) &= H(X,Y)-H(X)\\ &= -\sum_{X,Y}p(X,Y)log_2p(X,Y)--\sum_{X}p(X)log_2p(X)\\ &= -\sum_{X,Y}p(X,Y)log_2p(X,Y)+\sum_{X}(\sum_{Y}p(X,Y))log_2p(X)\\ &= -\sum_{X,Y}p(X,Y)log_2 \frac{p(X,Y)}{p(X)}\\ &= -\sum_{X,Y}p(X,Y)log_2 p(Y|X)\tag {2.2} \end{align}$

则，在色泽条件下|Y|的条件增益为： $\frac{6}{17}*1+\frac{6}{17}*0.918+\frac{5}{17}*0.722=0.889$

信息增益

大白话：要想知道随机变量 $Y$ 的信息增益，就要“用 $Y$ 本身的信息熵” 减掉 “在已知 $X$ 情况下，随机变量 $Y$ 的信息熵”

含义：得知特征 $X$ 的信息而使得类 $Y$ 的信息不确定性减少的程度。
$g(Y, X)=H(Y)-H(Y|X) \tag{2.3}$

色泽的信息增益计算过程

2.2 信息增益率

因为信息增益可能会更偏向于数目较多的属性，因此，用一个数放缩了一下，具体公式如下：
$Gain_ratio(D, a)=\frac{Grain(D, a)}{IV(a)} \tag{2.4}$
其中
$IV(a)=-\sum_{v=1}p(X,Y)log_2 p(X,Y)\tag{2.5}$

IV举例

增益率对特征值较少的特征有一定偏好，因此 C4.5 算法选择特征的方法是先从候选特征中选出信息增益高于平均水平的特征，再从这些特征中选择增益率最高的。

2.3 基尼系数

2.3.1基尼值

反映了数据集中随机抽取两个样本，其类别标记不一致的概率，因此，基尼值越小，数据集的纯度越高。
$\begin{align} Gini(D) &= \sum_{k=1}^{|Y|}\sum_{k \neq k'}p_kp_{k'} \\ &=\sum_{k=1}^{|Y|}p_k(1-p_{k}) \\ &=\sum_{k=1}^{|Y|}p_k- \sum_{k=1}^{|Y|}p_k^2 \\ &=1-\sum_{k=1}^{|Y|}p_k^2 \tag{2.6} \end{align}$

2.3.2基尼系数

基尼系数

3. 剪枝

通过剪枝，可以有效防止决策树模型过拟合的问题。主要有一下两种剪枝方法：

预剪枝
后剪枝

3.1 预剪枝

在决策树生成过程中，对每个节点先进行估计，若当前及诶单的划分不能使决策树的泛化性能提升，则停止划分。

3.2 后剪枝

对一个完整的决策树，从底向上对非叶子节点进行分析，若将该子树替换为叶子结点能够提升决策树的泛化能力，则将该子树替换为叶子节点。

4. python 代码实现地址

4.1 在所有数据集上未剪枝的决策树运行结果

西瓜书中有一处分类错误：

P78页图4.4

西瓜数据2.0计算结果

4.2 在训练集上未剪枝的运行结果

本文的运行结果与西瓜书不一致，原因在于在信息增益相同的情况下：（“脐部凹陷”处，gain(色泽)=gain(根蒂)），选取的划分特征不同。本文在“脐部凹陷”处选择的划分特征为根蒂，西瓜书选择的是“色泽”。

未剪枝的决策树

4.3 在训练集上使用“预剪枝”运行结果

预剪枝的决策树

5.小结

构建决策树过程中出现了以下问题：

在特征值划分部分

python列表深复制和浅复制的问题。
《西瓜书》中在算法描述部分提到的“从A中去掉 $a_*$ ”是指在子树中去掉，并不是整棵树中不再用，所以在最终树的“触感”特征出现了两次
image.png

之前第三种导致算法返回的情况一直没有遇到。原因是，在特征选择时用到的是

feature_values = list(dataset[classify_feature].unique())

而非

feature_values = self.unique_value[classify_feature]

导致无法获取到第三种返回的特征值。

image.png

6. 参考：

《西瓜书》
《统计学习方法》
机器学习实战决策树plotTree函数完全解析

7. 留疑

若特征值是连续变量怎么处理？

缺失值的处理方式
多变量决策树

脚注

已知集合D的信息熵为:
$Ent(D)=-\sum_{k=1}^{|y|}p_klog_2p_k$
可以理解为在 $0 \leq p_k \leq 1$ 和 $\sum_{k=1}^{|y|}$ 的条件下 $-\sum_{k=1}^{|y|}p_klog_2p_k$ 的最大值/最小值的问题。由拉格朗日算子可设
$L(p_1,p_2,...,p_n,\lambda) = -\sum_{k=1}^{|y|}p_klog_2p_k + \lambda(\sum_{k=1}^{|y|}p_klog_2p_k-1)$
对 $p_1,...,p_n,\lambda$ 求导，可得
$\begin{align} \frac{\partial L(p_1,...,p_n,\lambda)}{\partial x_1} &= \frac{\partial}{\partial p_1}\left [ -\sum_{k=1}^{y}p_klog_2 + \lambda \left( \sum_{k=1}^{y}p_k -1 \right) \right ] = 0 \\ &= -log_2p_1 - p_1 · \frac{1}{p_1·In2}+ \lambda = 0 \\ &= -log_2p_1 - \frac{1}{In2}+ \lambda = 0 \\ \Rightarrow \lambda &= log_2p_1 + \frac{1}{In2} \end{align}$
那么，对 $p_2...p_n$ 求导则有
$\begin{align} \lambda = log_2p_1 + \frac{1} {In2} = log_2p_2 + \frac{1}{In2} = ... = log_2p_n + \frac{1}{In2} \end{align}$
又因 $\sum_{k=1}^{|y|}=1$ ，所以有 $p_1=p_2=...=p_n= \frac{1}{n}$ ↩