《统计学习方法》——第5章 决策树

前言

本文只要记录一些书中的一些小知识点，挑一些本人认为重要的地方进行总结。

各位道友！道长(zhǎng) 道长(chǎng)

一、决策树

• 一种基本的分类与回归方法
• 优点：可读性，分类速度快
• 三个步骤：特征选择、决策树的生成、决策树的剪枝
• 常用算法：ID3,C4.5,CART

二、决策树模型

1.决策树由节点和有向边组成。
2.内部节点表示一个特征或属性
3.叶节点表示一个类

三、决策树的学习

递归的选择最优特征，根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。
  1、构建根节点，将所有数据放在根节点中。
  2、选择最优特征，根据这一特征将训练数据集分割成子集
  3、若可以正确分类，则构建叶节点，将子集放入叶节点
  4、如果自己不能被基本正确的分类，那么对自己继续选新的最优特征，对其进行分割，构建新节点
  5、递归进行，最后生成一颗树
决策树的学习算法包括特征选择、决策树的生成、决策树的剪枝

四、特征选择

特征选择是决定用哪个特征来划分特征空间
准则是信息增益和信息增益比

4.1信息增益

熵：随机变量不确定性的度量
概率分布：
$$P(X=x_i)=p_i$$
X的熵：
$$H(X)=-\sum p_i\log p_i$$
条件熵：X给定的的条件下Y的条件熵
$$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i)$$

由数据估计得到时，对应的熵和条件熵为经验熵和经验条件熵

信息增益：经验熵和条件熵之差
$$g(D|A)=H(D)-H(D|A）$$

4.2信息增益算法

输入：数据集D和特征A
输出：信息增益$g(D|A)$

1、计算H(D)
$$H(D)=-\sum _{k=1}^K\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|D|}$$

• $|C_k|$为这个$C_k$类的样本数

2.计算经验条件熵
$$H(D|A)=\sum _{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{D_i}{\log }_2\frac{|D_{ik}|}{|D_i|}$$
3.计算信息增益
$$g(D,A)=H(D)-H(D|A)$$

选信息增益最大的作为最优特征

4.3信息增益比

• 使用信息增益作为划分数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比对这个问题可以进行矫正

信息增益g与训练数据集D关于特征A的值的熵之比
$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$

• 其中 $H_A(D)$为D关于特征A的的熵

五、决策树的生成

5.1 ID3算法

输入：数据集D和特征集A阈值$\epsilon$
输出：决策树T
（1）若D中所有实例属于同一类$C_k$,则T为单节点树，并将类$C_k$作为节点的类标记，返回T
（2）若$A=\varnothing$,则T为单节点树，并将实例数最大的类$C_k$作为节点的类标记，返回T
（3）否则，按照上面讲的信息增益算法计算A中个特征对D的信息增益，选择信息增益最大的特征$A_g$
（4）若$A_g$的信息增益小于阈值$\epsilon$，则置T为单节点树，并将实例数最大的类$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 } A-\{Ag\} A−{Ag}为特征集，递归的调用(1)-(5),得到子树$T_i$,返回$T_i$

5.2 C4.5生成算法

在ID3基础上，使用信息增益比来选择特征，其余不变

六、决策树的剪枝

若按照以上讲的生成算法产生决策树，这样容易造成过拟合的现象。这是因为过多的考虑对已知数据的正确分类，从而构建了十分复杂的决策树。
为了解决这个问题，需要对决策树进行简化，即剪枝。

6.1 决策树学习的损失函数

决策树学习的损失函数可以定义为：

• |T|为叶节点个数，t是叶节点
• $N_t$为叶节点t的样本数
• $N_{tk}$表示$N_t$中k类的样本数量
• $H_t(T)$为叶节点t的经验熵
• $\alpha$为参数，大于等于0

经验熵$H_t(T)$为

把损失函数$C_{\alpha }(T)$第一项记作C(T)

这时候有

• C(T)表示模型对于训练数据的训练误差，即模型与训练数据的拟合程度
• |T|表示模型复杂度
• $\alpha$控制两者之间的影响。
  • 较大的$\alpha$选择简单的模型（树），较小的选择复杂的模型。

剪枝，就是当$\alpha$确定，选择巡视函数最小的模型（子树）。

6.2 剪枝算法

输入：生成算法生成的整个树T；参数$\alpha$
输出：剪枝后的T
（1）计算学个节点的经验熵
（2）递归的从树的叶节点向上回退。
  设一组叶节点回退到父节点之前和之后的整体树分别是$T_B$和$T_A$，对应的损失函数为$C_{\alpha }(T_B)$与 $C_{\alpha }(T_A)$,如果
$$C_{\alpha }(T_B)\ge C_{\alpha }(T_A)$$
则进行剪枝，将父节点变成叶节点
（3）返回（2）直到不能继续为止，得到损失函数最小的子树$T_{\alpha }$

七、CART算法

分类与回归树(classification and regression tree)

• CART既可以分类又可以回归
• 假设决策树是二叉树，内部节点的取值是“是”或“否”，且左“是”右“否”
• 两步组成：（1）决策树生成，尽量大（2）决策树剪枝，损失函数最小

7.1 CART生成

对于回归树用平方误差最小化准则
对于分类树用基尼指数最小化准则

1.回归树生成

假设把输入空间划分为M个单元，
每个单元$R_m$上的输出为$c_m$,故回归树模型可以表示为
$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$

当输入空间划分确定时，可以用平方误差来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。
易知${\hat{c}}_m$是所有输入实例$x_i$对于输出$y_i$的均值。
$${\hat{c}}_m=ave(y_i|x_i\in R_m)$$

然后对输入空间进行划分。具体的选择第j个变量$x^{(j)}$和他的取值s，作为切分变量j和切分点s。并且定义两个区域

具体的，
$$\underset{j,s}{\min }[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i-c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i-c_2{)}^2]$$

对于固定输入变量j可以找到最优切分点s

遍历所有输入变量，找到一个最优的切分变量j，构成（j，s）。将输入空间划分为连个区域。
接着对每个区域重复上述过程，直到满足条件。
这样的回归树称为最小二乘回归树

2.最小二乘回归树生成算法

3.分类树的生成

• 基尼指数
  分类问题中，假设有K个类，样本点属于第k类的概率为$p_k$,则基尼指数为
  $$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$
  对于给定样本集合D，基尼指数为
  $$Gini(D)=1-\sum _{k=1}^K(\frac{|C_k|}{|D|}{)}^2$$
  在特征A的条件下，基尼指数为
  $$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$

  • （$C_k$是D中属于第k类样本子集，K是类的个数）
  • 基尼指数表示集合D的不确定性，
  • $Gini(D,A)$表示经过A=a分割后D的不确定性
  • 基尼指数越大，不确定性越大（类似于熵）

4.CART生成算法

输入：训练集D；停止计算条件
输出：CART决策树
从根节点开始，递归的对每个节点进行以下操作
（1）设节点的训练集是D，计算现有特征的对数据集的基尼指数。根据样本点对特征A=a的测试为是或否，将D分为$D_1$和$D_2$，计算$Gini(D,A)$的基尼指数
（2）在所有可能的特征A机器他们的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征和最优切分点。根据最优特征和最优切分点生成两个子节点，将数据集进行分配
（3）对两个子节点递归调用(1)(2),直到满足条件
（4）生成CART树

• 停止计算条件是节点中的样本个数小于预定阈值。或者样本集的基尼指数小于预定阈值。或者没有更多特征。

7.2 CART剪枝

两步：

1. 从生成的决策树$T_0$底端开始剪枝，直到根节点，形成一个子树序列{$T_0,...,T_n$}
2. 用交叉验证法在独立的验证数据集上对子树序列进行测试，选择最优子树

1.剪枝，形成一个子树序列

剪枝过程中，计算子树的损失函数

对于固定的$\alpha$，一定存在使损失函数$C_{\alpha }(T)$最小的子树$T_{\alpha }$。

• Breiman等人证明：用递归的方法对树剪枝，将$\alpha$从小增大，产生一些列区间，$[{\alpha }_i,{\alpha }_{i_1})$,得到对应的子树序列{$T_0,...,T_n$}，序列中子树是嵌套的

$C(T)$为训练数据的预测误差（如基尼指数）。
对$T_0$的每一内部节点t，计算
$$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$$

• 他表示剪枝后整体损失函数减少的程度。在T0中减去g(t)，将得到的子树记作T1，同时将最小的g(t)设为${\alpha }_1$。$T_1$为区间$[{\alpha }_1,{\alpha }_2)$的最优子树。

2.在子树序列中，通过交叉验证选取最优子树$T_{\alpha }$

利用独立的验证数据集，测试子树序列中各个子树的平方误差或基尼指数。
平方误差或基尼指数最小的决策树被认为是最优决策树。
在子树序列中，每个子树都对应一个${\alpha }_i$，所以最优$T_i$确定，${\alpha }_i$也确定。
即得到了最优决策树$T_{\alpha }$

3.CART剪枝算法

总结

今天的内容是统计学习方法的第5章节，加油呀！