决策树

2019-01-28 本文已影响2人千与千与

决策树

决策树模型与学习
特征选择
决策树的生成
决策树的剪枝
CART 算法

决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。

决策树模型与学习

决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。
决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
决策树学习本质上是从训练数据集中归纳出一组分类规则。
决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。
开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。
我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。
如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。
决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

特征选择

如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。
在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设 $X$ 是一个取有限个值的离散随机变量，其概率分布为
$p(X=x_i)=p_i, \ \ \ \ \ i=1,2,...,n$
则随机变量 $X$ 的熵定义为
$H(X) = -\sum_{i=1}^np_i\log p_i$
$H(X)$ 也常用 $H(p)$ 表示，式中的对数以2为底或以e为底，这时熵的单位分别称作比特（bit）或纳特（nat）。熵越大，随机变量的不确定性就越大。
条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。随机变量 $X$ 给定的条件下随机变量 $Y$ 的条件熵（conditional entropy） $H(Y|X)$ ，定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望
$P(X=x_i,Y=y_j) = p_{ij}, \ \ \ \ \ i=1,2,...,n; \ \ \ \ \ j=1,2,...,m \\ H(Y|X) = \sum_{i=1}^np_iH(Y\mid X=x_i)$
其中 $p_i=P(X=x_i), \ \ \ \ \ i=1,2,...,n$ 。
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。
信息增益（information gain）表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。
特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ ，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差
$g(D,A) = H(D) - H(D\mid A)$
一般地，熵 $H(Y)$ 与条件熵 $H(Y|X)$ 之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益大的特征具有更强的分类能力。
信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类问题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。
信息增益比 $g_R(D,A)$ 定义为特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ 与训练数据集 $D$ 经验熵 $H(D)$ 之比：
$g_R(D,A) = \frac{g(D,A)}{H(D)}$

决策树的生成

ID3 算法
输入：训练数据集 $D$ ，特征集 $A$ ，阈值 $\xi$ ；
输出：决策树 $T$
1>> 若 $D$ 中所有实例属于同一类 $C_k$ ，则 $T$ 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 $T$ ；
2>> 若 $A＝\emptyset$ ，则 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
3>> 否则，计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_g$ ；
4>> 如果 $A_g$ 的信息增益小于阈值 $\xi$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
5>> 否则，对 $A_g$ 的每一可能值 $a_i$ ，依 $A_g＝a_i$ 将 $D$ 分割为若干非空子集 $D_i$ ，将 $D_i$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $T$ ，返回 $T$ ；
6>> 对第 $i$ 个子结点，以 $D_i$ 为训练集，以 $A{A_g}$ 为特征集，递归地调用 1>>~5>>，得到子树 $T_i$ ，返回 $T_i$ 。
C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征。

决策树的剪枝

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。
在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。
设树 $T$ 的叶结点个数为 $\mid T \mid$ ， $t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个， $k=1,2,...,K$ ， $H_t(T)$ 为叶结点 $t$ 上的经验熵， $\alpha \ge 0$ 为参数，则决策树学习的损失函数可定义为
$C_\alpha(T) = \sum_{t=1}^{\mid T \mid} N_tH_t(T) + \alpha \mid T \mid$
其中经验熵为
$H_t(T) = -\sum_k\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$
我们将
$C(T) = \sum_{t=1}^{\mid T \mid} N_tH_t(T) = -\sum_{t=1}^{\mid T \mid} \sum_{k=1}^KN_{tk} \log \frac{N_{tk}}{N_t}$
这时有
$C_\alpha(T) = C(T) + \alpha \mid T \mid$
式中， $C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度， $\mid T \mid$ 表示模型复杂度，参数 $\alpha \ge 0$ 控制两者之间的影响。
树的剪枝算法
输入：生成算法产生这个树 $T$ ，参数 $\alpha$
输出：修剪后的子树 $T_a$
1>> 计算每个结点的经验熵。
2>> 递归地从树的叶结点向上回缩。设一组叶结点回缩到其父结点之前与之后的整体树分别为 $T_B$ 与 $T_A$ ，其对应的损失函数值分别是 $C_a(T_B)$ 与 $C_a(T_A)$ ，如果 $C_a(T_A) \le C_a(T_B)$ ，则进行剪枝，即将父结点变为新的叶结点。
3>> 返回 2>>，直到不能继续为止，得到损失函数最小的子树 $T_a$ 。

CART 算法

分类与回归树（classification and regression tree，CART）是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。
CART 算法由以下两步组成：
1>> 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
2>> 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
CART 的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。
假设已将输入空间划分为 $M$ 个单元 $R_1,R_2,...,R_M$ ，并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$ ，于是回归树模型可表示为
$f(x) = \sum_{m=1}^M c_m I(x \in R_m)$
当输入空间划分确定时，可以用平方误差 $\sum_{x_i \in R_m} (y_i - f(x_i))^2$ 来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。
单元 $R_m$ 上的 $c_m$ 的最优值 $\hat{c}_m$ 是 $R_m$ 上的所有输入实例 $x_i$ 对应的输出 $y_i$ 的均值，即
$\hat{c}_m = ave(y_i \mid x_i \in R_m)$
最小二乘回归树生成算法
输入：训练数据集 $D$
输出：回归树 $f(x)$
1>> 遍历变量 $j$ ，对固定的切分变量 $j$ 扫描切分点，求解
$min_{j,s} \ \ \ [\ \ \ min_{c_1} \sum_{x_i \in R_1(j,s)}(y_i - c_1)^2 \ \ \ + \ \ \ min_{c_2} \sum_{x_i \in R_2(j,s)}(y_i - c_2)^2 \ \ \ ]$
得到最优切分变量 $j$ 与切分点 $s$ 。
2>> 用选定的 $(j,s)$ 划分区域并决定响应的输出值
$R_1(j,s) = \{x\mid x^{(j)} \le s \}, \ \ \ \ \ R_2(j,s) = \{x\mid x^{(j)} \gt s \} \\ \hat{c}_m = \frac{1}{N_m} \sum_{x_i \in R_m(j,s)} y_i, \ \ \ \ \ x \in R_m, \ \ \ \ \ m=1,2$
3>> 继续对两个子区域调用步骤 1>> 和 2>>，直至满足停止条件。
4>> 将输入空间划分 $M$ 个区域 $R_1,R_2,...,R_m$ ，生成决策树：
$f(x) = \sum_{m=1}^M \hat{c}_m I( x \in R_m)$
分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$ ，则概率分布的基尼指数定义为
$Gini(p) = \sum_{k=1}^Kp_k(1-p_k) = 1- \sum_{k=1}^Kp_k^2$
对于给定的样本集合 $D$ ，其基尼指数为
$Gini(D) = 1-\sum_{k=1}^K(\frac{\mid C_k \mid}{ \mid D \mid })^2$
这里， $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集， $K$ 是类的个数。
如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分，则在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为
$Gini(D,A)=\frac{\mid D_1 \mid}{\mid D \mid}Gini(D_1) + \frac{ \mid D_2 \mid}{\mid D \mid}Gini(D_2)$
基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼指数 $Gini(D,A)$ 表示经 $A＝a$ 分割后集合 $D$ 的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。直观来说， $Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此， $Gini(D)$ 越小，则数据集 $D$ 的纯度越高。
分类数生成算法
输入：训练数据集 $D$ ，停止计算的条件；
输出：CART 决策树。
1>> 设结点的训练数据集为 $D$ ，计算现有特征对该数据集的基尼指数。此时，对每一个特征 $A$ ，对其可能取的每个值 $a$ ，根据样本点对 $A＝a$ 的测试为“是”或“否”将 $D$ 分割成 $D_1$ 和 $D_2$ 两部分，计算 $A＝a$ 时的基尼指数。
2>> 在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
3>> 对两个子结点递归地调用 1>> 和 2>>，直至满足停止条件。
4>> 生成 CART 决策树。
算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。
对固定的 $\alpha$ ，一定存在使损失函数 $C_\alpha(T)$ 最小的子树，将其表示为 $T_a$ 。 $T_a$ 在损失函数 $C_\alpha(T)$ 最小的意义下是最优的。容易验证这样的最优子树是唯一的。当 $\alpha$ 大的时候，最优子树 $T_a$ 偏小；当 $\alpha$ 小的时候，最优子树 $T_a$ 偏大。极端情况，当 $a＝0$ 时，整体树是最优的。当 $a\rightarrow \infty$ 时，根结点组成的单结点树是最优的。
将 $\alpha$ 从小增大， $0＝\alpha_0<\alpha_1<…<\alpha_n<+\infty$ ，产生一系列的区间 $[\alpha_i,\alpha_{i+1}), \ i＝0,1,…,n$ ；剪枝得到的子树序列对应着区间 $\alpha \in [\alpha_i,\alpha_{i+1}), \ i＝0,1,…,n$ 的最优子树序列 ${T_0，T_1,…,T_n}$ ，序列中的子树是嵌套的。然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
从整体树 $T_0$ 开始剪枝，对 $T_0$ 的任意内部结点 $t$ , 以 $t$ 为单结点树的损失函数是
$C_\alpha(t) = C(t) + \alpha$
以 $t$ 为根节点的子树 $T_t$ 的损失函数是
$C_\alpha(T_t) = C(T_t) + \alpha\mid T_t \mid$
当 $\alpha = 0$ 或者 $\alpha$ 充分小时，有不等式
$C_\alpha(T_t) \lt C_\alpha(t)$
当 $\alpha$ 增大时，在某一 $\alpha$ 有
$C_\alpha(T_t) = C_\alpha(t)$
所以只要 $\alpha = \frac{C(t)-C(T_t)}{\mid T_t \mid -1}$ ， $T_t$ 与 $t$ 有相同的损失函数值，而 $t$ 的结点少，因此 $t$ 比 $T_t$ 更可取，对 $T_t$ 进行剪枝。
因此，对 $T_0$ 中的每个内部结点 $t$ ，计算
$g(t) = \frac{C(t)-C(T_t)}{\mid T_t \mid -1}$
它表示剪枝后整体损失函数减少的程度。在 $T_0$ 中剪去 $g(t)$ 最小的 $T_t$ ，将得到的子树作为 $T_1$ ，同时将最小的 $g(t)$ 设为 $\alpha_1$ 。 $T_1$ 为区间 $[\alpha_1,\alpha_2)$ 的最优子树。
如此剪枝下去，直至得到根结点。在这一过程中，不断地增加 $\alpha$ 的值，产生新的区间。
CART 剪枝算法
输入： CART 算法生成的决策树 $T_0$ ；
输出：最优决策树 $T_\alpha$
1>> 设 $k=0, T=T_0$ 。
2>> 设 $\alpha=+\infty$ 。
3>> 自下而上地对各内部结点 $t$ 计算 $C(T_t)$ ， $\mid T_t \mid$ 以及 $g(t)$ ，并令 $\alpha = min(\alpha, g(t))$ 。
4>> 自上而下地访问内部结点t，如果有 $g(t)＝\alpha$ ，进行剪枝，并对叶结点 $t$ 以多数表决法决定其类，得到树 $T$ 。
5>> 设 $k=k+1, \alpha_k=\alpha, T_k=T$ 。
6>> 如果 $T$ 不是由根结点单独构成的树，则回到步骤 4>>。
7>> 采用交叉验证法在子树序列 $T_0,T_1,…,T_n$ 中选取最优子树 $T_\alpha$

决策树

决策树模型与学习

特征选择

决策树的生成

决策树的剪枝

CART 算法

猜你喜欢

热点阅读