决策树

机器学习 决策树

---

决策树模型

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点node和有向边directed edge组成。节点有两种类型：内部结点internal node和叶结点leaf node。内部结点表示一个特征或属性，叶节点表示一个类。

决策树的学习：

假设给定训练数据集

$$D = \{(x_1, y_1), (x_2, y_2),...,(x_N,y_N)\}$$
其中$x_i={({x_i}^1, {x_i}^2,...{x_i}^n)}^T$为输入实例，$n$为特征个数，$y_i \in \{1, 2, ... K\}$为类标记，$i = 1,2,...N$为样本容量。

特征选择

信息增益

熵entropy表示随机变量不确定性的度量，设$X$是一个取有限个值得离散随机变量，其概率分布为

$$P(X=x_i) = p_i, i=1,2,...,n$$
则随机变量$X$的信息熵定义为：
$$H(X) = - \sum_{i=1}^{n}p_i\log{p_i}$$

设有随机变量$(X, Y)$，其联合概率分布为

$$P(X=x_i, Y=y_j) = p_{ij}, i=1,2,...,n; j=1,2,...,n$$
条件熵$H(Y|X)$表示已知$X$的情况下$Y$的不确定性
$$H(Y|X) = \sum_{i=1}^{n}{p_iH(Y|X=x_i)}, p_i=P(X=x_i), i=1,2,...,n$$

信息增益表示得知$X$的信息而使得$Y$的信息的不确定性减少的程度

$$g(D,A) = H(D) - H(D|A)$$
信息增益越大，说明$A$对$D$的分类能力很强。

符号定义：
数据集$D$，$|D|$为样本容量，
$K$为类个数，$k=1,2,...,K$
$C_K$表示类别为$K$的样本个数，则有$\sum_{k=1}^{K}|C_k|=|D|$
设特征$A$有$n$个不同的取值$\{a_1,a_2,...,a_n\}$，根据$A$的取值将$D$划分为$n$个子集$D_1,D_2,...,D_n$
$|D_i|$为样本个数，$\sum_{i=1}^{n}|D_i| = |D|$
设子集$D_i$中属于类$C_k$的样本的集合为$D_{ik}$，即$D_{ik} = D_i \cap C_k$，$|D_{ik}|$为$D_{ik}$为样本个数。

信息增益
输入：训练数据集$D$和特征$A$
输出：特征$A$对训练数据集$D$的信息增益$g(D,A)$
1) 计算数据集$D$的经验熵$H(D)$

$$H(D) = - \sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$$
2) 计算特征$A$对数据集$D$的经验条件熵$H(D|A)$
$$H(D|A) = \sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)$$
3) 计算信息增益
$$g(D,A) = H(D) - H(D|A)$$

信息增益比

由于信息增益并不能绝对的横向比较，因为对于取值比较多的特征，信息增益会比取值少的特征更大。所以使用信息增益比的概念。

$$H_A(D) = -\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}, n为特征A取值的个数$$
$$g_R(D, A) = \frac{g(D,A)}{H_A(D)}$$

决策树的生成

ID3算法

输入： 训练数据集$D$, 特征集$A$，阈值$\varepsilon$。
输出：决策树$T$
1）若$D$中所有实例属于同一类$C_k$，则$T$为单结点树，并将类$C_k$作为该结点的类标记，返回$T$;
2）若$A=\varnothing$,则$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$;
3）否则，计算$A$中各个特征对$D$的信息增益，选择信息增益最大的特征$A_g$；
4）如果$A_g$的信息增益小于阈值$\varepsilon$，则设$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$；
5）否则，对$A_g$的每一可能值$a_i$，依$A_g=a_i$将$D$分割为若干非空子集$D$，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$；
6）对第$i$个子结点，以$D_i$为训练集，以$A-{A_g}$为特征集，递归地调用1-5步，得到子树$T_i$，返回$T_i$。

c4.5生成算法

选择特征时，使用信息增益比 替换 信息增益；

决策树的剪枝

决策树的生成容易过拟合，那么需要进行剪枝。
损失函数的定义
设树$T$的叶结点个数为$|T|$，$t$为树$T$的叶节点，该叶结点有$N_t$个样本点，其中$k$类的样本点有$N_{tk}， k=1,2,...,K$个，$H_t(T)$为叶节点$t$上的经验熵，$\alpha \geq 0$为参数，则决策树学习的损失函数可以定义为

$$C_{\alpha}(T) = \sum_{t=1}^{|T|}N_tH_t(T) + \alpha|T|$$
$\alpha$可以调整树的复杂度，较小的$\alpha$偏向于选择较复杂的模型。决策树生成只考虑通过提供信息增益（信息增益比）对数据实现更好的拟合，而决策树剪枝通过优化损失函数减低模型复杂度。

树的剪枝算法
输入：生成算法产生的整个树$T$，参数$\alpha$
输出：修剪后的子树$T_{\alpha}$
1）计算每个结点的经验熵；
2）递归地从树的叶结点向上回缩
设一组叶结点会缩到其父结点之前与之后的整体树分别为$T_B$和$T_A$，其对应的损失函数值分别为$C_{\alpha}(T_B)$与$C_{\alpha}(T_A)$，如果

$$C_{\alpha}(T_A) \leq C_{\alpha}(T_B)$$
则进行剪枝，即父结点变为新的叶结点。
3）返回2），直至不能继续为止，得到损失函数最小的子树$T_{\alpha}$

CART算法
分类和回归树classification and regression tree,CART。
CART算法由一下两步组成：
1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，此时以最小损失函数最小作为剪枝的标准。

CART生成
回归树的生成
$X$为输入变量，$Y$为输出变量，并且$Y$是连续变量，给定训练数据集

$$D = \{(x_1,y_1), (x_2, y_2),...(x_N,y_N)\}$$
假设将输入空间划分为$M$个单元$R_1,R_2,...,R_M$，并且在每个单元$R_M$上有一个固定输出值$c_m$。
回归树模型
$$f(x) = \sum_{m=1}^{M}c_mI(x \in R_m)$$

训练误差

$$C = \sum_{x_i \in R_m}{}{(y_i - f(x_i)}^2$$

同时单元$R_m$中的$c_m$的最优值为$\hat{c}_m$

$$\hat{c}_m = ave(y_i|x_i \in R_m)$$

采用启发式的方式对输入空间 选择第$j$个变量$x^j$和它取的值$s$，作为切分变量splitting variable和切分点splitting point，则区域被切分为两个

$$R_1(j, s)=\{x|x^j \leq s\}, R_2(j,s) = \{x|x^j > s\}$$

然后寻找最优切分变量$j$和最优切分点$s$。
即求解

$$\min_{j,s}[\min_{c_1}\sum_{x_i \in {R_1(j,s)}} {(y_i - c_1)}^2 + \min_{c_2}\sum_{x_2 \in R_2(j,s)} {(y_i - c_2)} ^ 2 ]$$

$${\hat{c}}_1 = ave(y_i|x_i \in R_1(j,s)), {\hat{c}}_2 = ave(y_i|x_i \in R_2(j,s))$$

最小二乘回归树
输入：训练数据集$D$；
输出：回归树$f(x)$；
1）选择最优的切分变量$j$和切分点$s$，求解：

$$\min_{j,s}[\min_{c_1}\sum_{x_i \in {R_1(j,s)}} {(y_i - c_1)}^2 + \min_{c_2}\sum_{x_2 \in R_2(j,s)} {(y_i - c_2)} ^ 2 ]$$
2）对选定的对$(j,s)$划分区域并决定相应的输出值：
$$R_1(j, s)=\{x|x^j \leq s\}, R_2(j,s) = \{x|x^j > s\}$$
$$\hat{c}_m = ave(y_i|x_i \in R_m)$$
3）继续对两个子区域调用步骤1,2，直至满足停止条件；
4）将输入空间划分为$M$个区域$R_1,R_2,...R_M$，生成决策树：
$$f(x) = \sum_{m=1}^{M}{\hat{c}_mI(x\in R_m)}$$

基尼系数
在分类问题中，假设有$K$个类，样本点属于第$k$个类的概率为$p_k$，则概率分布的基尼系数为

$$Gini(p) = \sum_{k=1}^{K}p_k(1-p_k) = 1 - \sum_{k=1}^{K}{p_k}^2$$
基尼系数值越大，说明样本集合的不确定越大。
对于二分类问题，$Gini(p)=2p(1-p)$。

import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline
x = np.arange(0, 1, 0.0001)
plt.plot(x, np.where(x <= 0.5, x, 1-x), label="分类误差率")
plt.plot(x, 2 * x * (1 - x), label="基尼系数")
plt.plot(x, - 1/2 * (x * np.log2(x) + (1-x) * np.log2(1-x)), label="熵之半")
plt.legend((u"classification error rate", u"gini rate", u"half entropy"))
plt.show()

CART生成算法
输入：训练数据集$D$，停止计算的条件；
输出：CART决策树
1）设结点的训练数据集为$D$，计算现有特征对该数据集的基尼系数。此时对每一个特征$A$，对其可能取的每个值$a$，根据样本点对$A=a$的测试将集合分为两个集合：$D1$和$D2$，并计算基尼系数；
2）选择基尼系数小的切分点a进行切分；
3）对子结点递归地调用1,2，直到满足停止条件；
4）生成CART决策树。

停止条件可以设置叶子节点中样本个数的阈值，或者基尼系数的阈值

CART算法的剪枝