统计学习方法笔记第一篇。硕士毕业前整理过阅读李航博士的统计学习方法时的笔记。当时记在了几张A4纸上，现在趁着搭建博客的契机再次进行整理，免得那几张孤零零的纸以后寻不着了。今天首先整理的是决策树的ID3和C4.5生成算法，及其剪枝算法
概述
决策树是经典的分类和回归算法。具有泛化性能好，可解释性好，分类速度快等优点。本篇博文旨在介绍两种经典的决策树生成算法以及剪枝算法，为后面对复杂树模型的学习打下基础。
定义
经验熵
假设训练集$D$共有$K$个类别定义为$C_k,k=1,2..,K$，则训练集$D$的经验熵计算公式如下： \begin{equation} H(D) = - \sum_{k=1}^{K}\frac{|C_k|}{|D|}\log_{2}\frac{|C_k|}{|D|} \end{equation} 其中$|C_k|$为属于$C_k$类的训练集样本个数，$\frac{|C_k|}{|D|}$则为$C_k$类的概率。
可以看到当各个类概率相等时，训练集经验熵取得最大。我们想得到一个经验熵较小的训练集，需要怎么做呢？应当是对训练集进行划分，使得各个子训练集里的某类概率特别大，也就是子训练集里的样本基本属于一个类，纯度高。
经验条件熵
当使用特征$A$划分训练集时，此时$A$对于训练集$D$的经验条件熵如下： \begin{equation} H(D|A) = -\sum_{i=1}^{n}\frac{D_i}{D}\sum_{k=1}^{K}\frac{D_{ik}}{D_i}\log{}\frac{D_{ik}}{D_i} \end{equation} 根据特征$A$的取值将训练集$D$划分为$n$个子训练集，$|D_{ik}|$为第$i$个子训练集中属于类别$C_k$的样本数
信息增益
特征$A$对于训练集$D$的信息增益可以定义如下： \begin{equation} g(D,A) = H(D) = H(D|A) \end{equation} 其中$H(D)$为训练集$D$的经验熵，$H(D|A)$为特征$A$给定的情况下训练集$D$的经验条件熵
特征$A$对训练集$D$的信息增益可以理解为使用特征$A$使得训练集$D$变“纯”的程度
ID3算法
ID3算法利用信息增益进行特征选择，递归地构建决策树；直到所有特征的信息增益都很小或没有特征可以选择为止。ID3相当于用极大似然法进行概率模型的选择。
生成步骤
输入：训练数据集$D$，特征集$A$，信息增益阈值$\epsilon$
- 若$D$属于同一个类$C_k$，则$T$为单结点树，$C_k$为结点类别，返回$T$;
- 若$A=\varnothing$，将$D$中实例醉倒的$C_k$作为结点类别，返回$T$；
- 否则，计算$A$中各特征对$D$的信息增益，选择最大的$A_g$；
- 若$A_g < \epsilon$，结果同2；
- 否则，对$A_g$的每一可能值$a_i$，依$A_g=a_i$将$D$分割为若干非空$D_i$，将$D_i$中最多的类别作为标记构建子结点，返回$T$；
- 对第$i$个子结点，以$D_i$为训练集，$A-A_g$为特征集，递归调用1~5返回$T_i$。
C4.5算法
由于信息增益偏向于选择特征集中实例较多的特征，C4.5使用信息增益比来改进特征选择
信息增益比
特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义如下： \begin{equation} g_R(D,A) = \frac{g(D,A)}{H_A(D)} \end{equation} 其中$g(D,A)$为信息增益，$H_A(D)$为训练集$D$关于特征$A$的值的熵，$H_A(D) = -\sum_{i=1}^{n}\frac{|D_i|}{|D|}\log_{2}\frac{|D_i|}{|D|}$
生成步骤
C4.5算法的决策树生成步骤和ID3算法一致，不同之处为特征选择由信息增益改为信息增益比
决策树剪枝
任由决策树分裂到底很可能导致过拟合问题，解决过拟合的方法是对决策树进行剪枝，简化决策树。
损失函数
剪枝算法通过设计损失函数并极小化该损失函数实现。假设树的叶子结点个数为$|T|$，$t$为树$T$的叶结点，该叶结点上有$N_t$个样本，其中属于$k$类别的样本点有$N_{tk}，k=1,2..,K$个,$H_t(T)$为叶子结点$t$的经验熵，$\alpha$为控制剪枝程度的超参数。 则决策树学习的损失函数可以定义如下： \begin{equation} C_a(T) = \sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T| \end{equation} 其中$H_t(T)=-\sum_{k}\frac{N_{tk}}{N_t}\log{}\frac{N_{tk}}{N_t}$
记$C(T)=\sum_{t=1}^{|T|}N_tH_t(T)$，则 \begin{equation} C_a(T) = C(T) + \alpha|T| \end{equation} 其中$C(T)$代表决策树的拟合程度，$|T|$代表模型的复杂度
上述损失函数的极小化等价于正则化的极大似然估计，因此剪枝实际是使用正则化的最大似然估计进行模型选择
剪枝步骤
- 计算每一结点的熵；
- 递归地从叶结点向上回缩，若叶结点为$T_B$，回缩到其父结点后为$T_A$；损失函数分别为$C_a(T_B)$和$C_a(T_A)$，若$C_a(T_A) \le C_a(T_B)$则进行剪枝；
- 回到2直到得到损失函数最小的子树。