决策树基础

对应 “西瓜书” 4.1-4.4 内容，加一些 sklearn api 的内容。

背景简介

内容翻译自：Decision Trees - sklearn

优势

• 易于理解和解释。易于可视化。

• 几乎不需要数据预处理。其他算法通常需要正则化等处理，需要创建哑变量、填充空值。但是请注意，sklearn 实现的这个模块并不支持缺失值。

• 使用决策树（例如预测）代价，仅随训练用的数据增加，呈对数级的增长。

• 可以同时处理数字（连续）和类别（非连续）数据。

• 能够应对多输出的问题。

• 使用白盒模型。如果在模型中可以观察到某个给定的情形，他可以被布尔（二元是否）逻辑解释；黑盒模型（例如神经网络）则要困难得多。

• 可以用统计模型对模型进行验证，因此也可以方便的对模型（在未知数据集上的）可靠程度做出评价。

• 即使内部假设受数据产生的真实模型干扰，依然表现很好。

缺陷

• 决策树可能生成过于复杂的模型，导致泛化能力较弱。这种现象叫做“过拟合（overfitting）”。诸如剪枝（暂不支持）等一些手段，限定了每个叶节点的最小样本数量和树的最大深度，可以极大的避免这个问题。
• 可能不稳定。因为数据的较小波动可能导致生成的树完全不同。在集成（ensemble）中使用决策树可以减轻这个影响。
• 训练得到最优的决策树这个问题被认为是NP完全（NP-complete）的。这就导致了实际应用中，决策树的训练算法通常是基于启发式（heuristic）算法的，如贪心算法，其中每个节点都做局部最优决策。这样的算法不能保证生成全局最优的决策树。这个缺陷也可以通过在集成中训练一批树来解决，集成中样本和特征会被随机选择和替换。
• 例如 XOR、奇偶校验（parity）或多路复用器（multiplexer） 这样的一些逻辑，不能很好的通过决策树表达。
• 如果一些分类数据过多，决策树生成器可能生成有偏的树。所以一般我们建议训练决策树之前，先将数据集平衡好。

• 启发式 - Wikipedia)
• 多路复用器 - Wikipedia
• 奇偶校验 - Wikipedia)

基础内容

老套路，一边讲定义一边讲推导一边讲问题。

信息熵

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标，是统计学上的抽象概念。

假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k, (k=1, 2…，|\mathcal { Y }|)$，则 $D$ 的信息熵定义为：
$\begin{aligned} Ent(D) = - \sum ^ {|\mathcal { Y }|} _ {k=1} p_k log_2 p_k \end{aligned}$
$Ent(D)$ 的值越小，则 $D$ 的纯度（purity）越高。

• 推导：信息熵是什么 - 知乎

• 约定：若 $p=0$，则 $p log_2 p = 0$。
  所以 $Ent(D)$ 最小值为 $0$（此时 $p_k=1$，即所有样本属于同一类），最大值为 $log_2 |\mathcal { Y }|$。

• 单调性，即发生概率越高的事件，其所携带的信息熵越低。极端案例就是“太阳从东方升起”，因为为确定事件，所以不携带任何信息量。从信息论的角度，认为这句话没有消除任何不确定性。

• 非负性，即信息熵不能为负。这个很好理解，因为负的信息，即你得知了某个信息后，却增加了不确定性是不合逻辑的。

• 累加性，即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和。

  $H(A,B)=H(A)+H(B)-I(A,B)$ ，其中 $I(A,B)$ 是互信息（mutual information），代表一个随机变量包含另一个随机变量信息量的度量。

信息增益

假定离散属性 $a$ 有 $V$ 个可能的取值 ${a^1,a^2…，a^V}$：

1. 若使用 $a$ 来对样本集 $D$ 进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$。

2. 根据上式计算出 $D^v$ 的信息熵。

3. 再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $|D^v|/|D|$，即样本数越多的分支结点的影响越大。

4. 于是可计算出用属性 $a$ 对样本集 $D$ 进行划分所获得的 “信息增益”（information gain）：

   $\begin{aligned} Gain(D,a) = Ent(D) - \sum ^ {V} _ {v=1} \frac {|D^v|} {|D|} Ent(D^v) > 0 \end{aligned}$

一般而言，信息增益越大，则意味着使用属性 $a$ 来进行划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择。

著名的 ID3 决策树学习算法就是以信息增益为准则来选择划分属性。

（计算举例在《西瓜书》P76）

增益率

实际上，信息增益准则对可取值数目较多的属性有所偏好。

例如，给每个样本指定一个唯一编号，并把其视作一个离散属性。那么可以计算出其信息增益相当大，远大于其他候选属性，因为对于其每个分支节点（每个编号），其纯度已达最大。这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。

为减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法不直接使用信息增益，而是使用“增益率”（gain ratio）来选择最优划分属性。增益率定义为：

$\begin{aligned} Gain_ratio(D,a) &= \frac {Gain(D,a)} {IV(a)}, \\ IV(a) &=-\sum^V_{v=1} \frac {|D^v|}{|D|} log_2 \frac {|D^v|}{|D|} \end{aligned}$

其中，$IV(a)$ 称为属性 $a$ 的“固有值”（intrinsic value）。属性 $a$ 的可能取值数目越多（即 $V$ 越大），则 $IV(a)$ 的值通常会越大。

需注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。（增益率仅用来剔除分类效率太低的属性，保护信息增益）

基尼系数

类似的，CART 决策树使用“基尼指数”（Gini index）来选择划分属性。

数据集D的纯度可用基尼值来度量：

$\begin{aligned} Gini(D) &= \sum^{|\mathcal { Y }|}_{k=1} \sum_{k’ \not=k} p_k p_{k’} \\ &=1- \sum^{|\mathcal { Y }|}_{k=1} p_k^2 \end{aligned}$

直观来说，$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$ 越小，则数据集 $D$ 的纯度越高。

属性 $a$ 的基尼指数定义为：

$\begin{aligned} Gini_index(D,a) = \sum^V_{v=1} \frac {|D^v|}{|D|}Gini(D^v). \end{aligned}$

于是，我们在候选属性集合 $A$ 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 $\begin{aligned} a_* = \mathop{\arg\min}_{a \in A} Gini_index(D,a). \end{aligned}$

伪代码描述

剪枝处理

剪枝（pruning）是决策树学习算法对付 “过拟合” 的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得“太好”了，以致于把训练集自身的一-些特点当作所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

决策树剪枝的基本策略有“预剪枝”（prepruning）和“后剪枝”（post-pruning）。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

如何判断决策树泛化性能是否提升呢？这可使用2.2节介绍的性能评估方法。本节假定采用留出法，即预留一部分数据用作“验证集”以进行性能评估。

预剪枝

预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。

但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

本节演算请见《西瓜书》P81。

后剪枝

后剪枝先从训练集生成一棵完整决策树。

对比图4.7和图4.6可看出，后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

连续与缺失值

连续值处理

到目前为止我们仅讨论了基于离散属性来生成决策树。现实学习任务中常会遇到连续属性，有必要讨论如何在决策树学习中使用连续属性。

由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结点进行划分。此时，连续属性离散化技术可派上用场。最简单的策略是采用二分法（bi-partition）对连续属性进行处理，这正是 C4.5 决策树算法中采用的机制。

给定样本集 $D$ 和连续属性 $a$ ，假定 $a$ 在 $D$ 上出现了 $n$ 个不同的取值，将这些值从小到大进行排序，记为 $\{a^1, a^2….a^n\}$ 。基于划分点 $t$ 可将 $D$ 分为子集 $D_t^-$ 和 $D_t^+$，其中 $D_t^-$ 包含那些在属性 $a$ 上取值不大于 $t$ 的样本，而 $D_t^+$ 则反之。显然，对相邻的属性取值 $a^i$ 与 $a^{i+1}$ 来说，$t$ 在区间 $[a^i，a^{i+1})$ 中取任意值所产生的划分结果相同。因此，对连续属性 $a$，我们可考察包含 $n-1$ 个元素的候选划分点集合

$\begin{aligned}T_a=\{\frac{a^i+a^{i+1}}{2} | 1 \le i \le n-1\}\end{aligned}$

即把区间 $[a^i，a^{i+1})$ 的中位点 $\frac{a^i+a^{i+1}}{2}$ 作为候选划分点。然后，我们就可像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。

例如，可对上述信息增益方程稍加改造，非常容易可以得到：

$\begin{aligned} Gain(D,a) &= \max_{t \in T_a} Gain(D,a,t) \\ &= \max_{t \in T_a} Ent(D) - \sum _ {\lambda \in \{+,-\}} \frac {|D^\lambda_t|} {|D|} Ent(D^\lambda_t) \end{aligned}$

其中 $Gain(D,a,t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益。于是，我们就可选择使 $Gain(D,a,t)$ 最大化的划分点。

需注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。例如由于诊测成本、隐私保护等因素，患者的医疗数据在某些属性上的取值（如HIV测试结果）未知；尤其是在属性数目较多的情况下，往往会有大量样本出现缺失值。

如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息极大的浪费。

我们需解决两个问题：

1. 如何在属性值缺失的情况下进行划分属性选择？
2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

给定训练集 $D$ 和属性 $a$，令 $\tilde D$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集。对问题（1），显然我们仅可根据 $\tilde D$ 来判断属性 $a$ 的优劣。假定属性 $a$ 有 $V$ 个可取值 $\{a^1, a^2….a^V\}$，令 $\tilde D^v$ 表示 $\tilde D$ 中在属性 $a$ 上取值为 $a^v$ 的样本子集， $\tilde D_k$ 表示 $D$ 中属于第 $k$ 类 $(k= 1, 2…|\mathcal { Y }|)$ 的样本子集，则显然有 $\tilde D=\bigcup^{|\mathcal { Y }|}_{k=1} \tilde D_k, \tilde D = \bigcup ^{V}_{v=1} \tilde D^v$ 假定我们为每个样本 $x$ 赋予一个权重 $w_x$，并定义

$\begin{aligned} \rho & = \frac { \sum _ { \boldsymbol { x } \in \tilde { D } } w _ { \boldsymbol { x } } } { \sum _ { \boldsymbol { x } \in D } w _ { \boldsymbol { x } } } \\ \tilde { p } _ { k } & = \frac { \sum _ { \boldsymbol { x } \in \tilde { D } _ { k } } w _ { \boldsymbol { x } } } { \sum _ { \boldsymbol { x } \in \tilde { D } } w _ { \boldsymbol { x } } } \\ \tilde { r } _ { v } & = \frac { \sum _ { \boldsymbol { x } \in \tilde { D } ^ { v } } w _ { \boldsymbol { x } } } { \sum _ { \boldsymbol { x } \in \tilde { D } } w _ { \boldsymbol { x } } } \end{aligned}​$

权重在训练之初一般初始化为1。

直观地看，对属性 $a$，

• $\rho$ 表示无缺失值样本所占的比例，
• $\tilde p_k$ 表示无缺失值样本中第 $k$ 类所占的比例，
• $\tilde r_v$ 则表示无缺失值样本中在属性 $a$ 上取值 $a^v$ 的样本所占的比例。

显然，$\sum _ { k = 1 } ^ { | \mathcal { Y } | } \tilde { p } _ { k } = 1 , \sum _ { v = 1 } ^ { V } \tilde { r } _ { v } = 1$。

于是类似地，我们可将信息增益的计算式推广为：

$\begin{aligned} \operatorname { Gain } ( D , a ) & = \rho \times \operatorname { Gain } ( \tilde { D } , a ) \\ & = \rho \times \left( \operatorname { Ent } ( \tilde { D } ) - \sum _ { v = 1 } ^ { V } \tilde { r } _ { v } \operatorname { Ent } \left( \tilde { D } ^ { v } \right) \right) \end{aligned}$

其中，$\operatorname { Ent } ( \tilde { D } ) = - \sum _ { k = 1 } ^ { | \mathcal { Y } | } \tilde { p } _ { k } \log _ { 2 } \tilde { p } _ { k }$

对问题（2），

• 若样本 $x$ 在划分属性 $a$ 上的取值已知，则将 $x$ 划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_x$。
• 若样本x在划分属性a上的取值未知，则将 $x$ 同时划入所有子结点，且样本权值在与属性值 $a^v$ 对应的子结点中调整为动 $\tilde { r } _ { v } \cdot w _ { \boldsymbol { x } }$；直观地看，这就是让同一个样本以不同的概率（根据已知样本概率）划入到不同的子结点中去。

C4.5算法 使用了上述解决方案。

《西瓜书》P87 描述一个很好的例子。

sklearn - api

from sklearn import tree

# 两个样本，每个两个特征
X = [[0, 0], [1, 1]]
Y = [0, 1]
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, Y)

# 输出预测标签
p = clf.predict([[2., 2.]])
assert p == numpy.array([1])

# 输出预测样本属于各类的可能性（也即训练样本中该类别样本所占比例）
pp = clf.predict_proba([[2., 2.]])
assert pp == numpy.array([[0., 1.]])

鸢尾花数据集这样的多分类数据集也可以搞定：

from sklearn.datasets import load_iris
from sklearn import tree

iris = load_iris()
clf = tree.DecisionTreeClassifier()
clf = clf.fit(iris.data, iris.target)

# 通过 graphvis 导出决策树图片
# 可以通过 `conda install python-graphviz` 安装
import graphviz 
dot_data = tree.export_graphviz(clf, out_file=None, 
                     feature_names=iris.feature_names,  
                     class_names=iris.target_names,  
                     filled=True, rounded=True,  
                     special_characters=True)
graph = graphviz.Source(dot_data) 
graph.render("iris")

完整代码

import numpy as np
import matplotlib.pyplot as plt

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

# 各种参数
n_classes = 3
plot_colors = "ryb"
# 下图绘制步长
plot_step = 0.02

# 加载数据
iris = load_iris()

for pairidx, pair in enumerate([[0, 1], [0, 2], [0, 3],
                                [1, 2], [1, 3], [2, 3]]):
    # 只使用两个相应的特征进行训练
    X = iris.data[:, pair]
    y = iris.target

    # 训练
    clf = DecisionTreeClassifier().fit(X, y)

    # 绘制判别边界（绘图相关）
    plt.subplot(2, 3, pairidx + 1)
    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    # meshgrid 函数从一个坐标向量中返回一个坐标矩阵
    xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),
                         np.arange(y_min, y_max, plot_step))
    plt.tight_layout(h_pad=0.5, w_pad=0.5, pad=2.5)

    # np.c_ 按行连接两个矩阵
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    # 等高线间的区域进行填充
    # 数据集到色彩的映射
    cs = plt.contourf(xx, yy, Z, cmap=plt.cm.RdYlBu)

    plt.xlabel(iris.feature_names[pair[0]])
    plt.ylabel(iris.feature_names[pair[1]])

    # 绘制训练点
    for i, color in zip(range(n_classes), plot_colors):
        idx = np.where(y == i)
        plt.scatter(X[idx, 0], X[idx, 1], c=color, label=iris.target_names[i],
                    cmap=plt.cm.RdYlBu, edgecolor='black', s=15)

plt.suptitle("Decision surface of a decision tree using paired features")
plt.legend(loc='lower right', borderpad=0, handletextpad=0)
plt.axis("tight")
plt.show()

几个参考资料：

• numpy中的meshgrid函数
• plt.contour 与 plt.contourf
• 对 matplotlib.cm.RdYlBu() 的理解