《统计学习方法》决策树相关内容的学习笔记
1. 决策树简介
定义（决策树）：分类决策树模型是一种描述对实例进行分类的树形结构。
- 决策树由节点和有向边组成。
- 节点由两种类型：内部节点和叶节点。
- 内部节点标识一个特征或者属性，叶节点表示一个类。
用一个通俗的例子来解释：假设我们要对羊肉进行分类，羊肉由口感、熟度、新鲜度三个分类特征，评判结果是灰太狼爱吃与否。
我们由经验已知：
| 序号 | 品质 | 熟度 | 新鲜度 | 评判结果 |
|---|---|---|---|---|
| 1 | 好 | 全熟 | 新鲜 | 爱吃 |
| 2 | 好 | 全熟 | 不新鲜 | 不爱吃 |
| 3 | 好 | 半数 | 新鲜 | 爱吃 |
| 4 | 好 | 半熟 | 不新鲜 | 不爱吃 |
| 5 | 好 | 生 | 新鲜 | 爱吃 |
| 6 | 好 | 生 | 不新鲜 | 不爱吃 |
| 7 | 差 | 全熟 | 新鲜 | 不爱吃 |
| 8 | 差 | 全熟 | 不新鲜 | 不爱吃 |
| 9 | 差 | 半熟 | 新鲜 | 爱吃 |
| 10 | 差 | 半熟 | 不新鲜 | 不爱吃 |
| 11 | 差 | 生 | 新鲜 | 不爱吃 |
| 12 | 差 | 生 | 不新鲜 | 不爱吃 |
将上述规则画成决策树：
则，面对每一个待分类的实例，仅需要从根节点出发，在每一个内部节点处进行相应的判断，并进入对应子树，直至到达叶子节点找到对应标签。
补充说明：当然，我们此处的例子在每个叶子节点都仅有一个实例，因此可以直接确定标签。如果叶子节点有多个标签的话，则使用“多数表决”原则，少数服从多数，取多数实例的标签为分类标签。
我们也可以从概率学角度来理解决策树，就是在给定特征条件下的条件概率分布。例如从根节点经过判断，进入“品质好”的子树，再进行熟度的判断，其实等价于求 P(全熟|品质好)、P(半熟|品质好)、P(生|品质好)。
2. 决策树学习
决策树学习本质上是从训练集中归纳出一组分类规则。
与训练集不相矛盾的决策树可能有多个，也可能没有。我们需要的是一个与训练集矛盾较小的决策树，同时具有较好的泛化能力。
2.1 信息增益
首先先来介绍一个概念：熵。
在信息论与概率统计中，熵是表示随机变量不确定性的度量。假设 $X$ 是一个取有限个值的离散随机变量，其概率分布为 $P(X=x_i)=p_i, \ i=1,2,…,n$，则随机变量 $X$ 的熵定义为 $H(x)=-\sum_{i=1}^n p_i log\ p_i$（通常底数为 2 或 e，此时熵的单位为比特（bit）或者纳特（nat））
由上可以发现，熵只依赖于 $X$ 的分布，而与 $X$ 的取值无关，所以 $H(X)$ 通常也被记为 $H(p)$
熵越大，随机变量的不确定性越大。$H(p)$ 的取值范围为 $[0,\ log\ n]$。（当均匀分布时，熵最大，取等号为 $log\ n$）
信息增益表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。
定义（信息增益）：特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，
即 $g(D,A)=H(D)-H(D|A)$
上面的公式在两类的情况下，可以写为 $g(D,A)=H(D)-[H(D_1|A)+H(D_2|A)]$
将信息增益放到之前的“羊肉”例子中，我们截取了决策树的上半部分并假定了数据分布。将根节点的熵记为 $H(D)$，则“品质好”节点的熵为 $H(D_1|A)$，“品质差”节点的熵为 $H(D_2|A)$。我们进行计算：
- 在根节点下 P(灰太狼喜欢) = 4/10，则 $H(D)=\frac{4}{10} log \frac{4}{10}$
- 在品质好节点下 P(灰太狼喜欢) = P(灰太狼喜欢 | 品质好) = 4/5，则 $H(D_1|A)=\frac{4}{5}log \frac{4}{5}$
- 在品质差节点下 P(灰太狼喜欢) = P(灰太狼喜欢 | 品质差) = 2/5，则 $H(D_2|A)=\frac{2}{5}log \frac{2}{5}$
则 $g(D,A)=H(D)-H(D|A)=g(D,A)=H(D)-[H(D_1|A)+H(D_2|A)]=\frac{4}{10} log \frac{4}{10}-\frac{4}{5}log \frac{4}{5}-\frac{2}{5}log \frac{2}{5}$
2.2 信息增益比
以信息增益为选择划分训练数据集特征的依据时，存在偏向选择取值较多的特征的问题。
举一个通俗的例子：要对人群进行是否提供借贷服务的划分，一般可以有以下特征可用于划分（是否拥有房产、是否拥有工作、年龄等）。但是聪明的决策树会发现，如果将身份证 id 作为分类特征，仅需一层就可以实现 100% 的经验正确率（将身份证号与是否提供借贷服务的结果一一对应）。但这显然是没有任何意义的，而且会产生极高的泛化误差。
因此我们引入了信息增益比对这一问题进行校正。
信息增益比：特征 A 对训练数据集 D 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 D 关于特征 A 的值的熵 $H_A(D)$ 之比，
即：$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$，其中 $H_A(D)=-\sum_{i=1}^n \frac{|D_i|}{|D|}log_2 \frac{|D_i|}{|D|}$，$n$ 是特征 A 取值的个数
其实我们很容易发现信息增益比就是在信息增益的基础上除以分母 $H_A(D)$
2.3 特征选择
从效率而言，我们希望模型（决策树）可以通过一层一层的判断，尽快得到标签。换言之，就是每一层的信息增益都尽可能大（信息的不确定性下降得尽可能快）
也就是说，我们希望优先使用分类效果更加显著的特征用于分类（比如某特征 A 可以将 10 个样本分为两类，样本数量分别为 5个 与 5 个；某特征 B 会将 10 个样本分为为两类，样本数量分别为 1 个和 9 个。显然，特征 B 不是我们希望优先选用的分类特征）
通常，特征选择的准则是信息增益或信息增益比。
3. 构建决策树
3.1 ID3 算法
输入：训练数据集 D，特征集 A 阈值 $\epsilon$；
输出：决策树 T。
若 D 中所有实例同属于一类 $C_k$，则 T 为单节点树，并将类 $C_k$ 作为该节点的类标记，返回 T；
若 $A = \emptyset$，则 T 为单节点树，并将 D 中的实例数最大的类 $C_k$ 作为该结点的类标记，返回 T；
否则计算 A 中各特征对于 D 的信息增益，选择增益最大的特征 $A_g$；
如果 $A_g$ 的信息增益小于阈值 $\epsilon$，则置 T 为单节点数，并将 D 中实例最大的类 $C_k$ 作为该节点的类标记，返回 T；
否则，对 $A_g$ 的每一个可能值 $a_i$，依 $A_g=a_i$ 将 D 分割为若干个非空子集 $D_i$，将 $D_i$ 中实例最大的类作为标记，构建子节点，由节点及其子节点构成树 T，返回 T；
对第 i 个节点，以 $D_i$ 为训练集，以 $A-{A_g}$ 为特征集，递归地调用步骤 1~5，得到子树 $T_i$，返回 $T_i$
这里，对几个步骤进行解释：
- 步骤二中，当 $A = \emptyset$ 时，则意味着不再有可以用于分类的特征，则剩余实例自动并入叶子节点。且叶子节点的标签遵从“多数表决”的原则。
- 步骤三中，选择增益最大的特征 A ，就是计算当前所有剩余分类特征的增益，选择增益最大的特征作为下一个分类特征。目的在于更快速地降低信息不确定性
- 步骤四中，采用阈值的意义在于如果当前剩余特征中最大的信息增益都小于阈值（比如 0.01），则说明已经不具备继续分类的必要
3.2 C4.5 算法
C4.5 算法和 ID3 算法唯一不同之处在于，ID3 算法选择信息增益来选择特征，而 C4.5 算法选择信息增益比。此处不过多赘述。
4. 决策树的剪枝
一般模型产生的过拟合现象，来源于两个原因：（1）训练过久；（2）模型过于复杂。
对此我们一般采用如下对策：（1）尽早停止 early stop；（2）降低模型复杂度。
在决策树模型下，上述两个对策对应为：（1）添加正则项；（2）对决策树进行剪枝。
4.1 决策树整体损失函数
比如给出上图这样一棵决策树，根节点为 T，其中一个叶子节点为 t，叶子节点中有 $N_t$ 个样本点，其中 k 类样本有 $N_{tk}$ 个。
我们可以得到叶节点 t 上的经验熵：$H_t(T)=-\sum_k \frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$
于是可以得到损失函数 $C_\alpha=\sum_{t=1}^{|T|} \frac{N_t}{N} H_t(T)$ （计算整棵树的经验熵期望之和）
由于 N 在整个计算过程中保持不变，因此也可以省去写为：$C_\alpha=\sum_{t=1}^{|T|} N_t H_t(T)$
为了防止模型过拟合，我们一般会在损失函数之后加上一个正则项 $\alpha$，$\sum_{t=1}^{|T|} N_t H_t(T)+\alpha |T|$。其中 $\alpha$ 的取值范围为 $[0,1]$。
一般我们简单写为 $C_\alpha(T)=C(T)+\alpha|T|$，其中 $C(T)=\sum_{t=1}^{|T|} N_t H_t(T)=\sum_{t=1}^{|T|}\sum_{k=1}^K N_{tk} log \frac{N_{tk}}{N_t}$
关于正则项的解释：正则项的添加是为了防止模型过拟合，此处的 $\alpha$ 的含义为模型在多大程度上参考正则项
- 当 $\alpha$ 取 1 时：最大程度参考正则项，使节点尽可能少
- 当 $\alpha$ 取 0 时：不参考正则项，可劲儿 train
4.2 决策树的剪枝算法
剪枝，简而言之就是选择损失函数最小的模型。
决策树的剪枝算法：
输入：生成算法产生的整个树 T，参数 $\alpha$；
输出：修剪后的子树 $T_\alpha$
- 计算每个节点的经验熵
- 递归地从树的叶节点向上回缩：如果回缩后的损失函数小于回缩前，则进行剪枝
- 返回步骤2，直至不能继续为止。得到损失函数函数最小的子树 $T_\alpha$
当然，上述算法可以做一步优化，就是无需每次对整棵决策树的每个节点的经验熵进行求和。比如下面这个例子：
剪枝前后，绿色框框出的部分的经验熵是不会变化的。因此可以仅对剩余部分进行经验熵求和。所以这是一个局部求解最优解从而得到整体最优解。在代码上，可以采用动态规划的办法实现。
4.3 CART 算法
分类和回归树（classification and regression tree，CART）模型是应用广泛的决策树学习方法。CART 同样由特征选择、树的生成以及剪枝组成，既可以用于分类也可以用于回归。
4.3.1 CART 生成
CART 的生成是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。
回归树生成
假设 X，Y 分别为输入和输出变量，并且 Y 为连续变量，给定数据集 $D={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$
我们可以将决策树的构建立即为特征空间的划分，每一个划分出的单元对应一个叶节点，如下图所示。
我们使用平方误差来衡量回归树对于训练数据的预测误差，在每一个节点上是 $(y_i-f(x_i))^2$ ，合并到整棵树的损失函数就是 $\sum_{x_i \in R_m}(y_i - f(x_i))^2$。不难发现，单元 $R_m$ 上的最优解（损失函数最小）为其均值 $\hat c_m = ave(y_i|x_i \in R_m)$。
接下来我们介绍两个概念：切分特征 $j$ 和切分点 $s$
- 切分特征就是在众多特征中当前选取的用于划分的特征
- 切分点就是选取的特征下在何处进行二分类。
假设选取切分特征 $j$，并在切分点 $s$ 处切分，将可以得到两个区域 $R_1(j,s)={x|x^{(j)} \leq s}$ 和 $R_2(j,s)={x|x^{(j)} > s}$。
要使切分点和切分特征最合理，则应该求解 $min_{j,s}[min_{c1} \sum_{x_i \in R_1(j,s)} (y_i-c_1)^2 + min_{c2} \sum_{x_i \in R_2(j,s)}(y_i-c_2)^2]$
也就是遍历所有的 $j$ 和 $s$，寻找最小代价函数。（这样的回归树通常称为最小二乘回归树）
由此生成的决策树的代价函数为 $f(x)=\sum_{m=1}^M \hat c_m I(x \in R_m)$，其中 $\hat c_m = ave(y_i|x_i \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$
则对于二分类问题，假设样本点属于第一个类的概率为 $p$，则概率分布的基尼系数为 $Gini(p)=2p(1-p)$。
（也就是将定义中的 $p_k$ 用 $k$ 带入）
对于给定的样本集合 D，我们采用极大似然的思想，令 $p_k = \frac{|C_k|}{|D|}$，其中 $C_k$ 为属于第 $k$ 类的样本数量。带入二分类问题公式，
得到：$Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2$
在样本集合 D，特征 A 的条件下，假定切分点为 a，将样本分为 $D_1$ 和 $D_2$ 两个部分，则基尼系数为 $Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{D}Gini(D_2)$
基尼系数 $Gini(D)$ 代表集合 D 的不确定性，基尼指数数值越大，代表样本集合的不确定性越大，和熵类似。
因此，分类树的生成就是遍历所有的特征 A，寻找合适的切分点 a，使得基尼系数最小。
4.3.2 CART 剪枝
CART 剪枝的目的是从决策树减去一些子树，使决策树变小，降低模型复杂度。主要分为两个步骤：
剪枝，形成一个子树序列
在 4.1 章节中，我们介绍了决策树的整体损失函数为 $C_{\alpha}(T)=C(T)+\alpha |T|$。（此处正则项 $|T|$ 为节点个数）
我们一般从决策树的底端（叶节点）开始剪枝，因此，也会写出叶节点（单个节点）的损失函数：$C_{\alpha}(t)=C(t)+\alpha$
- 当 $\alpha$ 充分小的时候，正则项 $\alpha |T|$ 几乎不对结果产生影响，损失函数直接取决于 $C(T)$ 和 $C(t)$，则显而易见，$C(T) > C(t)$，因为越到树的底层，分类越清晰，数据的不确定性越低。因而 $C_{\alpha}(T) > C_{\alpha}(t)$，即叶节点的损失函数大于根节点
- 当 $\alpha$ 足够大时，正则项对损失函数的影响将会很大，系数 $\alpha$ 乘上节点个数数值可观，因此根节点的损失函数大于根节点
由上两种情况可得，当 $\alpha$ 从小到大的过程中，叶节点的损失函数从大于根节点开始，不断增加，到小于根节点。则必有某一时刻，叶节点的损失函数等于根节点。因此，我们可以得到等式 $C_{\alpha}(T)=C_{\alpha}(t)=C(T)+\alpha |T|=C(T)+\alpha$
将后两项进行移项得到：$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$
此时，树 $T_t$ 和叶节点 $t$ 拥有相同的损失函数，而 $t$ 的节点更少，因此对 $T_t$ 进行剪枝。
因此，我们要做的是计算整棵树中每一个内部节点的 $\alpha$ 值，减去 $\alpha$ 最小的子树，将得到的子树记为 $T_1$，同时记 $\alpha$ 为 $\alpha_1$。则 $T_1$ 为区间 $[\alpha_1,\alpha_2)$ 中最优子树。如此剪枝下去，直到根节点，即可得到子树序列 。
用一张比较形象的图来解释：
在图中，右侧是 $\alpha$ 的坐标轴，此处举了三个剪枝子树 ${T_1,T_2,T_3}$，分别对应 $[\alpha_1,\alpha_2)$ 和 $[\alpha_2,\alpha_3)$ 和 $[\alpha_3,\infty)$ 上的最优子树。
在剪枝得到的子树序列中通过交叉验证的方法选取最优子树
我们一般采用平方误差或者基尼系数来衡量决策树的优劣（代价函数）。也就是计算子树序列中代价函数最小的子树，在确定最优子树的同时，也就确定了 $\alpha$。
5. 总结
决策树是用于数据分类的常见模型，内部节点为每一次分类判断，不同类别的实例进入不同的子树，直到叶节点得到对应实例的标签。
决策树的代价（损失函数）一般用信息增益或者信息增益比进行衡量。
信息增益是指决策树每深入一层，信息不确定性的减少程度（熵的减少程度）
$g(D,A)=H(D)-H(D|A)$
信息增益比是在信息增益的原理基础下，减少了因特征取值数量引起的过度拟合
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$，其中 $H_A(D)=-\sum_{i=1}^n \frac{|D_i|}{|D|}log_2 \frac{|D_i|}{|D|}$，$n$ 是特征 A 取值的个数
构造决策树就是不断地选取信息增益/信息增益比最大的特征用于当前步骤的分类，从而产生了两种决策树构造算法：ID3 和 C4.5
为了减少模型复杂度，我们将会对决策树进行剪枝，剪枝依据就是对比剪枝前后总体决策树代价函数的大小，从叶子节点向根节点回缩，如果回缩后损失函数小于等于回缩前，就进行剪枝。
决策树的损失函数就是所有节点的经验熵之和，为了防止模型过拟合，一般会在损失函数后加上正则项。
CART 算法是既可用于分类也可用于回归的决策树模型，是二叉决策树。回归树用平方误差最小化准则，分类树用基尼指数最小化准则，每次选取最合适的分类特征与分类点，来构造最小代价的决策树。
同样我们也对二叉决策树进行剪枝：
当某棵子树的代价等于某个叶节点的代价时减去子树，得到此时 $\alpha$ 区间内的最优子树；
以此类推，得到一个剪枝子树集（分别对应不同的 $\alpha$ 区间）
再对剪枝子树集中的每一棵子树进行代价计算，得到一棵代价最小的最优子树及其对应的 $\alpha$ 值