统计学习方法（笔记）-决策树
决策树是一种基本的分类与回归方法。模型可读性强，分类速度快，可以认为是 if-then 规则的集合。
决策树模型与学习
分类决策树模型是一种描述对实例进行分类的树形结构。内部节点表示特征或者属性，叶节点表示一个类。分类时，从根节点开始，对实例某一特征进行测试，根据测试结果分配到子节点，递归进行，直到到达叶节点，即为实例所属的类，如图：
可以将决策树看做一个 if-then 规则的集合，并且其路径具有互斥且完备性质。如上图，最终的类别为 Yes 和 No 两类，假设存在数据$x={青少年,是学生}$，首先判断第一个特征，年龄，为青少年，跳转到最左边节点，判断是否是学生，则类别为 Yes。
决策树还能表示给定特征条件下类的条件概率分布。
决策树学习本质上是从训练数据集中归纳出一组分类规则。能对训练数据集进行正确分类的决策树可能有多个，也可能没有。需要选择一个与训练数据集矛盾小，有很好泛化能力的决策树。从另一个角度，把决策树学习看做训练数据集估计条件概率模型，基于特种空间划分的类的条件概率模型有无穷多个，我们选择的模型应该对训练数据有很好的拟合，对未知数据有很好的预测。
决策树的学习损失函数通常是正则化的极大似然函数。从所有可能的决策树中选取最有决策树是 NP 完全问题，所以通常学习算法采用启发式方法，求得次最优的决策树。对于过拟合现象，采用自下而上的剪枝操作，将树变得更简单。决策树的生成只考虑局部最优，剪枝则考虑全局最优。学习常用算法有 ID3、C4.5和 CART。
特征选择
特征选择的准则通常是信息增益或者信息增益比。
熵是表示随机变量的不确定性的度量。设 X 是一个取有限个值的离散随机变量，其概率分布为：
$$P(X=x_i)=p_i, \quad i=1,2,…,n$$
随机变量 X 的熵定义为：
$$H(X)=-\sum \limits_{i=1}^n p_i \log p_i$$
上式中，若$p_i=0$，定义$0\log 0=0$。对数底可以为2或者 e，这时熵的单位分别为比特或纳特。由定义，熵只依赖于 X 的分布，与 X 的取值无关，所以也可以记为：
$$H(p)=-\sum \limits_{i=1}^n p_i \log p_i$$
熵越大，随机变量的不确定性越大，所以：$0 \le H(p) \le \log n$。
对于随机变量 (X,Y)，其联合概率分布：
$$P(X=x_i,Y=y_j)=P_{ij},\quad i=1,2,…,n;j=1,2,…,m$$
条件熵表示在已知随机变量 X 的条件下，变量 Y 的不确定性，定义为 X 给定条件下 Y 的条件概率分布的熵对 X 的数学期望：
$$H(Y|X)=\sum \limits_{i=1}^n p_iH(Y|X=X_i)$$
这里$p_i=P(X=x_i), i=1,2,…,n$。
信息增益表示得知特征 X 的信息而是类 Y 的信息的不确定性减少的程度，也称为互信息。
特征 A 对训练数据集 D 的信息增益 g(D,A) 定义为集合 D 的经验熵 H(D) 与特征 A 给定条件下 D 的检验条件熵之差，即：
$$g(D,A)=H(D)-H(D|A)$$
因此，决策树特征选择的方法可以为：对训练集 D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
但是，以信息增益作为划分的特征，可能存在偏向于选择取值较多的特征的问题，因此可以改为使用信息增益比：
$$g_R(D,A)=\frac {g(D,A)}{H_A(D)}$$
其中，$H_A(D)=-\sum \limits_{i=1}^n \frac {|D_i|}{|D|}\log_2 \frac {|D_i|}{|D|}$
#决策树的生成
ID3 算法
ID3 核心是在决策树的各个节点上应用信息增益准则选择特征，递归地构建决策树。从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点。ID3相当于用极大似然法进行概率模型的选择。但是 ID3 算法只有树的生成，所以容易产生过拟合。
C4.5 算法
C4.5 与 ID3 类似，但是生成过程，使用的是信息增益比来选择特征。
决策树的剪枝
决策树生成过程，可能会导致过拟合。可以使用剪枝对已生成的树进行简化。具体的，剪枝从已生成的树上裁掉一些子树或者叶节点，并将其根节点或父节点作为新的叶节点，从而简化分类树模型。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。
设树 T 的叶节点个数为 |T|，t 是树 T 的叶节点，该叶节点有$N_t$个样本点，其中 k 类样本有$N_{tk}$个，$H_{t}(T)$为叶节点 t 上的经验熵，$\alpha \ge 0$为参数，则决策树学习的损失函数为：
$$C_{\alpha}(T)=\sum \limits_{t=1}^{|T|}N_tH_t(T)+\alpha{T}$$
其中经验熵：
$$H_t(T)=-\sum_k \frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$$
将损失函数记为：
$$C_{\alpha}(T)=C(T)+\alpha |T|$$
其中第一项表示对训练数据的预测误差，|T|表示复杂度，参数$\alpha \ge 0$控制两者间的影响。
剪枝时，计算每个节点的经验熵，然后递归地从树的叶节点往上回缩。如果一组叶节点回缩到其父节点之前与之后的整体树分别为$T_B$和$T_A$，如果$C_\alpha (T_A) \le C_\alpha(T_B)$则进行剪枝，将父节点变为新的叶节点。
剪枝算法可以由动态规划算法实现。
CART 算法
CART，全称 classification and regression tree，即分类与回归树，既可以用于分类也能用于回归。CART 是在给定输入随机变量 X 条件下输出随机变量 Y 的条件概率分布的学习方法，其假设决策树是二叉树。
CART 生成
决策树的生成就是递归地构建儿茶决策树的过程。对回归树用平方误差最小准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。
回归树的生成
假设将输入划分为 M 个单元$R_1,R_2,…,R_M$，并且在每个单元$R_m$上有一个固定输出值$c_m$，于是回归树模型可以表示为：
$$f(x)=\sum_{m=1}^Mc_mI(x \in R_M)$$
当输入空间划分确定时，可以用平方误差$\sum_\limits{x_i \in R_M}(y_i-f(x_i))^2$来表示回归树对于数据的预测误差，用平方误差最小准则求解每个单元上的最有输出值。采用启发式的方法划分输入空间。
生成算法为：
选择最优切分变量 j 和切分点 s，求解：
$$\min \limits_{j,s}[\min \limits_{c_1} \sum_{x_i\in R_1(j,s)}(y_i-c_1)^2 + \min \limits_{c_2} \sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$$
遍历变量 j，对固定的切分变量 j 扫描切分点 s，选择使上式达到最小值的对 (j,s)。
对选用的对 (j,s) 换分区域并决定相应的输出值：
$$R_1(j,s)={x|x^{(j)} \le s}, \quad R_2(j,s)={x|x^{(j)} \gt s}$$
$$\hat{c_m}=\frac{1}{N_m}\sum_{x_i \in R_m(j,s)}y_i,\quad x\in R_m,\quad m=1,2$$
继续对子区域调用1、2步骤，直到满足停止条件。
将输入空间划分为 M 个区域，生成决策树：
$$f(x)=\sum_{m=1}^{M}\hat{c_m}I(x\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)$$
如果样本 D 根据特征 A 是否取某一可能值$\alpha$被分割成$D_1$和$D_2$两部分，则在特征 A 的条件下，集合 D 的基尼指数为：
$$Gini(D,A)=\frac{|D_1|}{D}Gini(D_1)+\frac{|D_2|}{D}Gini(D_2)$$
基尼指数Gini(D,A)表示经 A=a 分割后集合 D 的不确定性。基尼指数值越大，样本集合的不确定性也就越大。
CART 生成算法为：1. 计算现有特征对数据集 D 的基尼指数，对每一个特征 A，对可能的每个取值$\alpha$的测试为“是”或者“否”将 D 分割成两部分，计算$A=\alpha$ 时的基尼指数；2. 选择基尼指数最小的特征及其对应的且分店作为最优特征和最优切分点，将 D 分配到两个子节点，并递归调用1，2。停止计算的条件是节点中样本个数小雨预定阈值，或者样本集的基尼指数小雨预定阈值，或者没有更多特征。
CART 剪枝
对于生成的决策树$T_0$，进行 CART 剪枝：
设 $k=0,T=T_0$
设 $\alpha=+\infty$
自下而上对各内部节点 t 计算$C(T_t),|T_t|$以及
$$g(t)=\frac{C(t)-C(T_t)}{|T_t| - 1}$$
$$\alpha=\min(\alpha,g(t))$$
这里，$T_t$表示以 t 为根节点的字数，$C(T_t)$是对训练数据的预测误差，$|T_t|$是$T_t$的叶节点数量
自上而下的访问内部节点 t，如果有$g(t)=\alpha$，进行剪枝，并对叶节点 t 以多数表决法决定其类，得到树 T
设$k=k+1,\alpha_k=\alpha,T_k=T$
如果 T 不是由根节点单独构成的树，则回到步骤4
采用交叉验证法在子树序列$T_0,T_1,…,T_n$中选取最优子树$T_\alpha$
