ch5-决策树

决策树

决策树是一种对实例进行分类的树形结构，由

• 结点
  • 内结点：分类的特征
  • 叶子结点：具体的类别
• 有向边

决策树是互斥且完备的：可以理解为一个实例只会被一条路径覆盖。

给定数据集：

$$D = \{(x_{1},y_{1}),(x_{2},y_{2}) \cdots (x_{n},y_{n}) \}$$

其中 $x=(x^{1},x^{2} \cdots x^{n})^{T}$ 是特征向量，$n$ 为特征个数。

决策树的学习函数通常是正则化的极大似然函数，其学习策略是以损失函数为目标函数最小化。通常做法是递归地选择最优特征，划分数据集。

特征选择

主要讨论怎么去判定哪个特征能最好地划分数据集。

信息增益

我们一般用熵来衡量一个随机变量的不确定性：熵越大，不确定性越大

$$H(X) = - \sum_{i=1}^{n} p_{i} log{p_{i}}$$

条件熵则是已知随机变量 $X$ 的情况下，随机变量 $Y$ 的不确定性：

$$H(Y|X) = \sum_{i=1}^{n}p_{i} \cdot H(Y|X=x_{i})$$

信息增益就可以理解为我们分类之后对训练集不确定性的降低：

$$g(D,A) = H(D) - H(D|A)$$

那么我们就可以知道，对于不同地特征分类效果也是不同地，我们自然是想要最优地特征，即信息增益最大的特征。

可以用极大似然估计地方式去算，具体推导pass，这里比较简单，只需要算出相应地概率即可。

决策树的生成

ID3 算法

$ID3$ 算法的核心是在决策树各个节点上使用信息增益去选择特征，递归地构建决策树。

算法流程：

输入：训练集 $D$ ，特征集 $A$ ，阈值 $\delta$

输出：

1. 若集合中全部实例属于同一类$C{k}$ ，则 $T$ 为单结点树，类标记是 $C{k}$；
2. 若 $A$ 是空集，则将集合中实例数最多的类 $C_{k}$ 作为该结点的类标记
3. 否则，按照信息增益法则去计算 $A$ 中各特征对集合 $D$ 的信息增益，选择信息增益最大的特征 $A_{i}$
4. 如果 $A{i}$ 的信息增益小于阈值 $\delta$ ，则将集合中实例数最多的类 $C{k}$ 作为该结点的类标记
5. 否则，对于 $A{i}$ 的每一个值 $a{i}$ ，划分数据集 $D$ 为若干非空子集 $D{i}$ ，将 $D{i}$ 中实例数最多的类作为该子集的标记，构建子结点
6. 对于第 $i$ 个结点，使用 $A-A{i}$ 为特征集，对训练集 $D{i}$ 递归地调用前五步。

$ID3$ 算法只是生成了树，达到了局部最优，但是缺少了剪枝的过程，容易过拟合，泛化能力可能不高。

C4.5 生成算法

$C4.5$ 算法针对 $ID3$ 算法做出了改进，使用信息增益比来选择特征。

信息增益比

定义：信息增益 $g(D,A)$ 与训练集 $D$ 关于特征 $A$ 的值得熵 $H_{A}(D)$ 之比

$$g_{R}(D,A) = \frac{g(D,A)}{H_{A}(D)}$$

具体训练过程基本同 $ID3$ 算法。

决策树的剪枝

上述算法生成的决策时在训练集上表现可能极为优秀，但是在其他数据集上就可以分类很不准确，此为过拟合现象。因为此决策树可能过于复杂，我们解决问题的方法是简化决策树，称之为剪枝。

书上说的一个比较简单的算法：

设树的叶子结点个数为 $|T|$ ， $t$ 是树 $T$ 的叶结点，该结点有 $N{t}$ 个样本点，其中 $k$ 类的样本点有 $N{tk}$ 个，$H_{t}(T)$ 定义为叶子结点上的经验熵，$\alpha >= 0$ 是参数，则其损失函数为：

$$C_{\alpha}(T) = \sum_{t=1}^{|T|} { N_{t}H_{t}(T) + \alpha |T| }$$

其中经验熵则是：

$$H_{t}(T) = -\sum_{k} \frac {N_{tk}}{N_{t}} log{ \frac {N_{tk}}{N_{t}} }$$

我们把 $ C(T) = \sum{t=1}^{|T|} { N{t}H_{t}(T) } $ 称之为预测误差，$|T|$ 表示模型复杂度，我们使用参数 $\alpha$ 来控制两者之间的影响：

• 若 $alpha$ 较小，则模型相对复杂
• 若 $alpha$ 较大，则模型相对简单

然后我们只需要计算每个结点的经验熵，并且递归地网上回缩：若损失函数值更小，则进行剪枝，直到不能继续为止。

$CART$ 算法

在给定随机变量 $X$ 的情况下输出随机变量 $Y$ 的条件概率分布的学习方法。

算法生成

决策树的生成是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则。

回归树

pass

分类树

基尼系数：假设有 $K$ 个类，样本点属于第 $k$ 类的概率是 $p_{k}$ ，则概率分布的基尼系数定义为

$$Gini(p) = \sum_{k=1}^{K} p_{k}(1-p_{k}) = 1 - \sum_{k=1}^{K} {p_{k}}^2$$

对于二分类问题而言，样本点属于第一个分类的概率为 $p$ ，则

$$Gini(p) = 2p(1-p)$$

那么对于给定的样本集合 $D$ ，则有：

$$Gini(D) = 1 - \sum_{k=1}^{K} ( \frac {|C_{k}|} {|D|} )^2$$

我们知道根据特征 $A$ 的值可以把 $D$ 分成两个子集，那么在特征 $A$ 的条件下，集合 $D$ 的基尼系数为：

$$Gini(D,A) = \frac {|D_{1}|}{|D|} Gini(D_{1}) + \frac {|D_{2}|}{|D|} Gini(D_{2})$$

这一点的理解和熵十分类似。

具体过程：

1. 给定训练集 $D$ , 对每一个特征 $A{i}$ 的每一个取值 $a{i}$ 计算基尼系数
2. 选择最小的基尼系数对应的特征及取值，从而生成两个子结点，分配训练集的数据
3. 重复前两步，直到满足停止条件

算法的停止条件是自定义的，可以样本个数小于阈值，也可以是基尼系数小于阈值（表示基本是同一类的）…

算法剪枝

因为此决策树是完全生长的，所以需要剪去一些子树。

还是使用损失函数：

$$C_{\alpha}(T) = C(T) + \alpha|T|$$

定义同上文基本一致，不过不确定性的度量函数换了。

我们可以知道，对于固定的 $\alpha$ ,肯定存在是 $C{\alpha}(T)$ 最小的子树，将其表示为 $T{\alpha}$。

pass

课后习题

待完成。