前言：
决策树归纳是从有类标号的训练元组中学习决策模型。常用的决策树算法有ID3，C4.5和CART。它们是采用贪心（即非回溯的）方法，自顶向下递归的分治方法构造。这几个算法选择属性划分的方法各不相同，ID3使用的是信息增益，C4.5使用的是信息增益率，而CART使用的是Gini基尼指数。下面来简单介绍下决策树的理论知识。内容包含决策树的算法构成，熵、信息增益、信息增益率以及Gini指数和树的剪枝的概念及公式。
快速系统的理解一个机器学习算法
- 算法要解决的问题什么?
- 算法的输入输出是什么?
- 算法的实现的机理是什么?
- 算法的优化方法是什么？
- 算法的评价指标是什么？
决策树的算法构成
决策树归纳是从有类标号的训练元组中学习决策模型。常用的决策树算法有ID3，C4.5和CART。它们都是采用贪心（即非回溯的）方法，自顶向下递归的分治方法构造。这几个算法选择属性划分的方法各不相同，ID3使用的是信息增益，C4.5使用的是信息增益率，而CART使用的是Gini基尼指数。下面来简单介绍下决策树的理论知识。内容包含决策树的算法构成，熵、信息增益、信息增益率以及Gini指数和树的剪枝的概念及公式。
决策树是是由特征空间作为结点和类空间作为叶子构建的一棵树。：
特征划分逻辑
以每个特征作为判别标志（根节点），用if…then…作为分裂规则(yes or no)，将特征空间划分成互斥且完备的子空间，通过不断地划分子空间，树不断地生长。具体的划分依据和逻辑见第三章。 
分类规则：
从统计的角度出发，节点对应的最大条件概率作为分类准则。(要明白似然函数和概率的区别)
优化：
决策树的损失函数通常是正则化的极大似然函数，学习的策略是以损失函数为目标函数的最小化。决策树采用启发式算法来近似求解最优化问题，得到的是次最优的结果。
该启发式算法可分为三步：
- 特征选择
- 模型生成
- 决策树的剪枝
决策树生成与剪枝
信息量与熵
不管是分类任务还是回归任务，都是在做这样一件事情传递消息（类别or回归值）；特征就是我们对需要传递的消息的一种编码方式即信息。那么怎么衡量信息?信息论定义如下： \[ 信息量：l(x_i)=-log_2p(x_i) \] 有了信息（特征）以后怎么确定这个信息是否可靠的表达消息？我们定义熵来度量信息是否可靠。 \[ 熵：H(x) = -\sum_{i=1}^np_ilog(p_i)\ \]
\[ 条件熵： H(Y|X) = H(X,Y)-H(X) = \sum_XP(X)H(Y|X) = -\sum_{X,Y}logP(Y|X) \]
熵越大，说明系统越混乱，携带的信息就越少。熵越小，说明系统越有序，携带的信息就越多。信息的作用就是在于消除不确定性。 均匀分布的不确定性最大，即特征均匀分布（所有特征都一样）熵最大，特征完全没有区分性，无法准确传递消息（类别or回归）。条件熵H（Y|X）描述的是在X给定的条件下Y的不确定性，如果条件熵越小，表示不确定性就越小，那么B就越容易确定结果。
ID3算法与信息增益
ID3划分特征（创建节点的规则）使用的就是信息增益Info-Gain排序。一个特征的信息增益越大，表明该对样本的熵减少的能力就更强，该特征使得数据所属类别的不确定性降低。信息增益描述特征对分类(回归)的不确定性的降低程度，可以用来度量两个变量的相关性。比如，在给定一个变量的条件下，另一个变量它的不确定性能够降低多少，如果不确定性降低得越多，那么它的确定性就越大，就越容易区分，两者就越相关。
信息增益在统计学中称为互信息，互信息是条件概率与后验概率的比值，化简之后就可以得到信息增益。所以说互信息其实就是信息增益。计算方法: \[ G(D, A) = H(D) - H(D|A) ，H(D)经验熵，H(D|A)经验条件熵，D表示训练集，A表示特征空间 \] \[ H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}log\frac{|C_k|}{|D|}，其中，|C_k|是属于类C_k的个数，|D|是所有样本的个数 \] \[ H(D|A)=\sum_{i=1}^np_{a_i}H(D|a_i)=\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\frac{|D_{ik}|}{|D_i|}，\\特征A有个不同的划分取值\{a_1, a_2, ..., a_n\}，根据特征A的划分取值将D划分为n个子集D_1, D_2, ..., D_n， |D_i|是D_i的样\\本个数，D_ik是中属于C_k类的样本集合。 \]信息增益ID3算法流程图对非空非单一特征空间A:
C4.5算法与信息增益比
C4.5算法用信息增益比作为特征选择的依据。算法流程与ID3类似。 使用信息增益作为特征选择的标准时，容易偏向于那些取值比较多的特征，容易导致过拟合。而采用信息增益比则有效地抑制了这个缺点：取值多的特征，以它作为根节点的单节点树的熵很大，导致信息增益比减小，在特征选择上会更加合理。 \[
信息增益比: 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取值的个数
\] 我的理解就是信息增益比在信息增益上做了个平滑处理，将特征对应的信息增益与特征空间划分的熵相结合起来，约束了不同取值特征的信息增益处理不均衡的问题，在一定程度生类似于标准化，正向统一特征划分的标准。
CART算法
CART(分类回归树)算法是由以特征为节点的多个二叉树串联形成可以完成回归任务和分类任务。CART算法同样由特征选择，树的生成及剪枝组成 ；其中回归树用最小平方误差准则，分类树用基尼指数(Gini index)最小化 准则，进行特征选择，生成二叉树。
1. 最小二乘回归树生成算法
带着问题看算法： 要搞明白最小二乘法是怎么进行特征选择的？ 采用启发式的方法，选择第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]\\其中，R_1(j,s)=\{x|x^{(j)}≤s\},R_2(j,s)=\{x|x^{(j)}＞s\}，c_1={1\over N_1}\sum_{x_i \in R_1}y_i , \quad c_2={1\over N_2}\sum_{x_i \in R_2}y_i \] 统计学习方法上说 对上述俩个子空间递归调用该步骤,直到满足停止条件。 然后将输入空间划分为M个子区域，生成决策树： \[ f(x) = \sum_{m=1}^Mc_mI(x \in R_m) \]
2. CART分类算法与基尼系数
- 基尼指数
\[ 基尼指数 ：Gini(D) =1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2，其中C_k是D中属于第k类的子集。\\如果样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分，即\\ D_1=\{(x,y) \in D| A(x) =a\},D_2 = D-D_1\\则在特征A的条件下，集合D的基尼指数定义为 :Gini(D,A) = \frac{\vert D_1\vert}{\vert D\vert}Gini(D_1)+\frac{\vert D_2\vert}{\vert D\vert}Gini(D_2) \] 问题： 那为什么用基尼指数选择特征而不用信息增益或者信息增益率？
- 分类CART生成：
输入：训练数据集D，停止计算的条件；
输出：CART决策树；
根据训练数据集，从根节点开始，递归地对每个结点进行以下操作，构建二叉决策树：
（1）设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割成D1和D2两部分，利用基尼指数计算公式计算。
（2）在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
（3）对两个子结点递归地调用（1），（2），直至满足停止条件。
（4）生成CART决策树
算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值，或者没有更多特征。
决策树的剪枝
因为决策树的生成算法容易构建过于复杂的决策树，产生过拟合。而剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型，在这里我们可以联想其实剪枝就是一直正则化手段，简化模型，防止过拟合！下面我们进行详细介绍：
决策树剪枝的基本策略： - 预剪枝(prepruning) 在决策树生成过程中，对每个节点在分割前先进行估计。若当前的分割不能带来决策树泛化性能的提升，则停止分割并将当前节点标记为叶节点 在预剪枝过程中，决策树的很多分支都没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间和预测时间；但有些分支的当前分割虽不能提升泛化性能、甚至能导致泛化性能下降，但在其基础上的后续分割却有可能导致泛化性能的显著提高，容易导致欠拟合 - 后剪枝(postpurning) 先从训练样本集生成一棵最大规模的完整的决策树，然后自底向上地对非叶结点进行考察。若将该提升决策树的泛化性能，则将该子树替换为叶节点节点对应的子树替换为叶节点能 后剪枝决策树比预剪枝决策树保留了更多的分支。后剪枝过程的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中所有的非叶节点进行逐一考察，因此训练时间开销比未剪枝决策树和预剪枝决策树都要大的多
决策树的剪枝
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。 设树T的叶结点个数为\(|T|\)，t是树T的叶结点，该叶结点有\(N_t\)个样本结点，其中k类的样本点有\(N_{tk}\)，k = 1, 2, …, K，\(H_t(T)\)为叶结点t上的经验熵，α≥0为参数，则决策树学习的损失函数可以定义为 :\(C_{\alpha}(T_t) = C(T_t) + \alpha|T_t|\) 其中经验熵:\(H_t(T)=-\sum_{i}^{K}\frac{|N_{ik}|}{N_i}log\frac{|N_{ik}|}{N_i}\) 在损失函数中，将第1项记作:\(C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}\) 则：\(C_\alpha(T)=C(T)+\alpha|T|\)
C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，\(|T|\)表示模型的复杂度，参数\(\alpha\)控制两者之间的影响。较大的\(\alpha\)促使选择较简单的模型（树），较小的\(\alpha\)促使选择较复杂的模型（树）。\(\alpha=0\)意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。 剪枝，就是当α确定时，选择损失函数最小的模型（树）。但α值确定时，子树越大，往往与训练数据的拟合越好，但是模型的复杂度就越高；相反，子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好。损失函数正好表示了对两者的平衡。 可以看出，决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。 损失函数的极小化等价于正则化的极大似然估计。所以，利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。
决策树剪枝算法：
输入：生成算法产生的整个树T，参数\(\alpha\);
输出：修剪后的子树\(T_\alpha\)
（1）计算每个结点的经验熵；
（2）递归地从树的叶结点向上回缩。设一组叶结点回缩到其父结点之前与之后的整体树分别为\(T_B\)和\(T_A\)，其对应的损失函数值分别是\(C_\alpha(B)\)和\(C_\alpha(A)\)，如果\(C_\alpha(B)\le C_\alpha(A)\) 则进行剪枝，即父结点变为新的叶结点。
（3）返回（2），直至不能继续为止，得到损失函数最小的子树\(T_\alpha\)。
CART剪枝
相比一般剪枝算法，CART剪枝算法的优势在于，不用提前确定α值，而是在剪枝后从所有子树中找到最优子树对应的\(\alpha\)值。 对于固定的α值，一定存在让\(C_\alpha(T)\)最小的唯一的子树，记\(T_\alpha\)。
决策树小结
决策树算法对比
| 算法 | 支持模型 | 树结构 | 特征选择 | 连续值处理 | 缺失值处理 | 剪枝 |
|---|---|---|---|---|---|---|
| ID3 | 分类 | 多叉树 | 信息增益 | 不支持 | 不支持 | 不支持 |
| C4.5 | 分类 | 多叉树 | 信息增益比 | 支持 | 支持 | 支持 |
| CART | 分类，回归 | 二叉树 | 基尼系数，均方差 | 支持 | 支持 | 支持 |
决策树算法的优缺点
- 优点：
- 决策树由明确的规则生成，可解释性强。
- 基本不需要预处理，不需要提前归一化，处理缺失值。
- 既可以处理离散值也可以处理连续值。
- 非参数模型，树模型在不同分布数据上表现更稳定。
- 可以交叉验证的剪枝来选择模型，从而提高泛化能力。(验证集(CART)也可以发挥调整模型的作用而不仅仅是评估模型)
- 缺点：
- 决策树算法非常容易过拟合，导致泛化能力不强。
- 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。
