机器学习中树模型算法总结之 决策树（下）
写在前面
首先回顾一下上一篇的相关内容，主要是理论的介绍了决策树的模型及几种常见的特征选择准则，具体可参见机器学习中树模型算法总结之 决策树（上）。今天主要接着学习，包括决策树的生成（依赖于第一篇的三种特征选择准则）以及生成之后避免过拟合的剪枝操作。
学习笔记相关资料：
《统计学习方法》——李航
《机器学习》西瓜书——周志华
《Machine Learning Tech》课程——台大林轩田
3.决策树的生成
3.1 基于信息增益准则的ID3算法
ID3算法的具体实现：
（1）从根结点开始，对当前结点计算所有特征的信息增益；
（2）选择信息增益最大的特征作为当前结点特征，然后根据该特征的不同取值构建子结点；
（3）接着对新生成的子结点递归执行以上步骤，直到所有特征的信息增益都很小或者没有特征可选(分类完毕)为止。
ID3相当于用极大似然法进行概率模型的选择。
这里再贴上对上述步骤的详细描述：
3.2 基于信息增益率的C4.5算法
C4.5算法与ID3算法类似，可以看成其改进版，只是将特征选择中的信息增益准则换为信息增益率。
具体算法步骤如下：
4.决策树的剪枝（pruning）
由以上决策树的算法可以看出，生成过程递归地进行直至不能继续为止，这样的结果往往导致训练集合准确率很高，但是在测试集上表现很差，即所谓的过拟合（overfitting）。机器学习中有许多降低过拟合问题的解决方法，在决策树中使用的是剪枝。剪枝的基本策略有“预剪枝”和“后剪枝”。
4.1 预剪枝（pre-pruning）
预剪枝是指在决策树的生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树性能的提升，则停止划分并将当前结点标记为叶结点。
使用预剪枝操作，一方面减低了过拟合的风险并且显著降低了算法的训练及预测时间开销，但是另一方面，由于预剪枝的“贪心”本质禁止某些分支的展开，可以导致其泛化性能不升反降，带来了欠拟合的风险。所以在实际应用中较少使用预剪枝。
4.2 后剪枝（post-pruning）
总体思路：由完全树T0开始，剪枝部分结点得到T1，再次剪枝部分结点得到T2...直到剩下树根的树Tk；在验证数据集上对这k个树分别评价，选择损失函数最小的树Ta。
设|T|为树T叶结点个数，t是树T的叶结点，该叶结点有Nt个样本点，其中k类的样本点有Ntk个，则决策树的损失函数可以定义为：
其中H（T）为经验熵：
将损失函数第一项简化记为C（T）：
最终形式的损失函数：
在上式中，C（T）表示模型对训练数据的预测误差，|T|为模型的复杂度，alpha为平衡两者的参数（大于等于0）。较大的alpha偏向选择较简单的树，较小的alpha偏向选择预测误差更小的树模型。
下面贴上剪枝算法的具体步骤：
关于后剪枝的其他几种算法：
1、REP-错误率降低剪枝
2、PEP-悲观剪枝
3、CCP-代价复杂度剪枝
4、MEP-最小错误剪枝
具体可参见知乎专栏决策树之决策树剪枝5.CART算法
CART——Classification and Regression Tree，分类与回归树，是广泛应用的决策树学习方法。与前类似，CART算法也包括特征选择、树的生成和剪枝几个部分。
5.1 CART生成
CART树包括两种，回归树和分类树。对于回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择。
5.1.1 回归树
5.1.2 分类树
5.2 CART 剪枝
CART剪枝算法从“完全生长”的决策树的地段剪去一些子树，使决策树变小，从而能够对未知数据有更准确的预测。CART剪枝算法步骤：
（1）首先从生成算法产生的决策树T0底端不断剪枝，直到T0的根结点，形成一个子序列{T0，T1，…Tn} ；
（2）通过交叉验证在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
具体步骤：
平方误差或者基尼指数最小的决策树被认为是最优的决策树。
同样为了加深CART的印象，贴一个例子(P71)
小结
至此决策树的基本学习就差不多啦，但是这些仅仅是理论的算法，至于代码实现还是要更进一步地去练习。
如果理论掌握的差不多的小伙伴可以转到周志华老师《机器学习》Chapter 4的课后习题，也是我最近在看的，一起交流哈~
新人学机器学习算法，有错误或者不完备的地方请指正~
以上~
2018.04.18