决策树

一种基本的分类与回归方法。主要包括三步：特征选择、决策树的生成、决策树的修剪

分类问题是对抑制标签的学习，而聚类才是自行总结特征。

模型

通过树形结构来描述分类的结果，其中内部节点表示特征，叶子节点代表一个类。

从两个角度来看决策树：

每一条根节点到叶子节点的路径表示了一个if-then的逻辑结构，所有的路径构成的集合完备的表示了每一个实例被分类的过程。
从条件概率的角度来看，所有路径过程的集合实现了对于特征空间的划分。决策树刻画了不同实例属于不同类别的条件概率分布。最终由联合概率分布的大小决定不同实例的类别。

学习过程

我们的目标是得到一个可以较好地对于训练数据进行分类描述地决策树，同时还有具备一定的泛化能力。往往通过正则化的损失函数来描述这一目标

递归的选择最优的特征对于特征空间进行分割，直至没有可再选择的特征或者分类已经足够满意。然后对于已有的树进行剪枝，提高其泛化能力

特征选择

用于分类的特征一定要是能对于训练数据进行有效分类的特征。如何评价一个分类是否有效，可以引入信息增益进行描述

信息增益

首先引入熵的概念。在物理中，熵描述了系统的混乱程度，而在概率论与信息论中，熵作为对于随机变量不确定性的度量。

对于随机变量 $X$ ，若

P(X = x_i) = p_i

则定义

H(X) = -\sum_{i = 1}^np_i\log p_i

特别的，当 $p_i = 0$ 时， $p_i\log p_i = 0$ 由于熵完全由随机变量的分布来决定，熵也可以写作是对于分布的函数。也可以写作

H(p) = -\sum_{i = 1}^np_i\log p_i

熵越大，随机变量的不确定性就越大， $0 \leq H(p) \leq \log n$

条件熵 $H(Y|X) = \sum p_iH(Y|X = x_i)$ 表示在Y在X约束下的不确定程度。

有估计（如最大似然估计）得到的熵称为经验熵。

而信息增益就是用来描述特征X使类Y不确定性减少的程度。显然信息增益越大，一个特征的分类效果越好

信息增益，特征D对于训练集A的信息增益定义为

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

可以解释为引入A特征是否对于特征集的不确定性有有效的降低，评价了分类的有效性，信息增益大的特征具有更强的分类能力

根据信息增益进行特征选择就是选择信息增益最大的特征

信息增益的算法：

对于训练集D，K个类将训练集划分为 $C_k$ 。对于特征A，有n个取值，将训练集划分为n个子集，可以得到：

H(D) = -\sum_{k = 1}^K\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}\\ H(D|A) = \sum_{i = 1}^n\frac{|D_i|}{|D|}H(D_i)

信息增益比：使用信息增益可能会导致倾向取值较多的特征，可以进行一个归一化

g_R(D|A) = \frac{d(D, A)}{H_A(D)}

决策树的生成

ID3算法

从根节点开始，对所有的节点计算可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，对于子节点不断递归这一过程直到所有的特征都被选择完为止。

算法过程：

若D中所有实例属于同一类，直接返回该类的标签
若特征集A为空，直接返回D中实例数最大的类的标签
否则计算各特征的信息增益，选择信息增益最大的特征
若小于阈值，则也就构建一个单节点树
否则对于该特征的所有可能值对于训练集分割，将子集中的实例数最大的类别作为标签构建子节点
对于所有子节点递归这一过程

C4.5

使用信息增益比来进行决策树的生成

剪枝

直接训练出来的决策树模型对于训练数据的分类十分准确，但是对测试数据的分类未必会很好，即出现过拟合现象。过拟合现象出现的原因是模型过度的考虑如何适应训练数据而构建出过于复杂的决策树，我们可以考虑对于决策树剪枝来避免这一情况。

可以通过最小化损失函数的方式来实现。损失函数的定义：

C_{\alpha}(T) = \sum_{t = 1}^{|T|}N_tH_t(T) + \alpha|T|

其中 $t$ 是树T的叶节点。损失函数就是加入了正则项，避免模型过于复杂

剪枝算法：

计算每个结点的经验熵
递归的从树的叶节点向上回缩
比较回缩后的损失函数与回缩前，若损失函数减小，则在此节点处进行剪枝

CART算法

分类与回归树也是一种决策树学习方法，同样有特征选择、树的生成、剪枝构成。CART假设决策树是一个二叉树，所有的节点都是取“是”或“否”，是递归的对于所有的特征进行二分。对于输入的随机变量X，给出Y的条件概率分布的学习结果。

CART生成

回归树生成

一种回归方法，输出是数值。

X,Y分别是输入和输出，其中Y是连续性随机变量，对于训练集

D = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}

一颗回归树意味着对于输入空间的划分，每一个划分的区域对应一个固定的输出值，回归树的数学模型可以表示为

f(x) = \sum_{m = 1}^M c_mI(x \in R_m)

$R_m$ 表示一个区域， $c_m$ 表示该区域的取值

使用2范数来表示回归树对于训练集的误差，通过最小二乘法，可以知道 $c_m$ 取区域内均值时误差最小

输入空间的划分有不同的方法，可以直接选择第 $j$ 个变量作为划分，或者相邻两个变量的中点，然后对于两个区域误差和做最优化得到最佳的切分点，数学表示为：

\min_{j,s}\left[\sum_{x_i \in R_1(j, s)}(y_i - \hat{c}_1)^2 + \sum_{x_i \in R_2(j, s)}(y_i - \hat{c}_2)^2\right]

这样划分得到的回归树称为最小二乘回归树。

分类树生成

基尼系数：

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

Gini(p) = \sum_{k = 1}^Kp_k(1-p_k) = 1 - \sum_{k = 1}^Kp_k^2

若样本集合D根据特征A是否取可能值 $a$ 被分割为两部分，则在特征A的条件下，集合D的基尼指数为：

Gini(D, A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)

基尼指数也表示了集合D的不确定性，基尼指数越大，则样本集合的不确定性就越大。

基尼指数和熵对于样本的不确定性描述往往是一致的，但是二者侧重不同，基尼指数考虑的是样本被误分类的概率，相比于熵更适合分类树的快速生成，并且计算也更加简便，不用进行对数运算。

CART生成算法：

对于训练集D，的所有特征及可能取值计算对应的基尼指数
选择基尼系数最小的特征及其对应取值，作为最优特征与最优切分点，生成两个子节点，将训练集分割到两个子节点中去
对子节点递归进行以上过程，直到满足停止条件

停止条件就是节点中样本过少或基尼系数小于某一个阈值

CART剪枝

在生成决策树后，得到最原始的决策树 $T_0$ ，对于任意的子树 $T$ ，计算其损失函数：

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

$C(T)$ 为对于训练数据的预测误差，如基尼指数、信息增益。

对于不同的 $\alpha$ ，有使损失函数最小的子树。经过证明，有一系列嵌套的子树称为最优子树序列 $\{T_0, T_1, \cdots, T_n\}$

对于任意节点 $t$ ， $C_{\alpha}(t)$ 就是该单节点树的损失函数。

当 $\alpha$ 很小时， $C_{\alpha}(T_t) < C_{\alpha}(t)$ ，此时说明不剪枝更好，随着 $\alpha$ 的增长， $C_{\alpha}(T_t) = C_{\alpha}(t)$ ，直到大小反转。

因此当 $\alpha = \dfrac{C(t) - C(T_t)}{|T_t| - 1}$ 时，就可以直接剪枝了。

对于每个节点，计算 $\dfrac{C(t) - C(T_t)}{|T_t| - 1}$ ，递归的取值最小的节点，并将这个值设置为 $\alpha_i$ 。最终得到对于参数空间分割为 $n+1$ 段，对应最优子树序列。

对于不同的测试集，采用交叉验证的方法计算不同最优子树的基尼指数或平方误差，选择最小的一个字数就完成了对于决策树的剪枝。