这篇文章会叙述之前没有解决的纯数学问题，同样会涉及到概率论的一些基础概念和思想，可能会有一定的难度
“集成学习”小结
- 集成学习是将个体模型进行集成的方法，大致可分为 Bagging 和 Boosting 两类
- 随机森林是 Bagging 算法的一种常见拓展、性能优异；它不仅对样本的选取引入随机性、还对个体模型（决策树）的特征选取步骤引入随机性
- AdaBoost 是 Boosting 族算法的代表，通过以下三步进行提升：
- 根据样本权重训练弱分类器
- 根据该弱分类器的加权错误率为其分配“话语权”
- 根据该弱分类器的表现更新样本权重
- 集成模型具有相当不错的正则化能力、但该正则化能力并不是必然存在的
- AdaBoost 可以用前向分步算法和加法模型来解释
决策树综述
上个系列讲的朴素贝叶斯模型的理论基础大部分是数理统计和概率论相关的东西，可能从直观上不太好理解。这一章我们会讲解一种可以说是从直观上最好理解的模型——决策树。决策树是听上去比较厉害且又相对简单的模型，虽然它用到的数学知识确实不怎么多、但是在实现它的过程中可能可以获得对编程本身更深的理解，尤其是对递归的利用这一块可能会有更深的体会
以下是目录：
数据的信息
本文首先简要地说明一下决策树生成算法背后的数学基础和思想、然后再叙述具体的算法。往大了说、决策树的生成可以算是信息论的一个应用，但它其实只用到了信息论中一小部分的思想。不过，先对信息论有个概括性的认知还是有必要的、因为这样我们就可以有个更宽的视野
决策树的生成算法
虽然我们之前已经用了许多文字来描述决策树、但可能还是显得过于抽象。为了能有直观的认知，在此援引维基百科上一张很好的图来进行说明：
这张图基本蕴含了决策树中所有的关键结构，下面我们分开来分析它们
信息量计算的实现
（本文会用到的所有代码都在这里）
由于决策树的生成算法中会用到各种定义下的信息量的计算，所以我们应该先把这些计算信息量相关的算法实现出来。注意到这些算法同样是在不断地进行计数工作，所以我们同样需要尽量尝试利用好上一章讲述过的 bincount 方法。由于我们是在决策树模型中调用这些算法的，所以数据预处理应该交由决策树来做、这里就只需要专注于算法本身。值得一提的是，这一套算法不仅能够应用在决策树中，在遇到任何其它需要计算信息量的场合时都能够进行应用
节点结构的实现
（本文会用到的所有代码都在这里）
在实现完计算各种信息量的函数之后，我们就可以着手实现决策树本身了。由前文的讨论可知、组成决策树主体的是一个个的 Node，所以我们接下来首先要实现的就是 Node 这个结构。而且由于我们所关心的 ID3、C4.5 和 CART 分类树的 Node 在大多数情况下表现一致、只有少数几个地方有所不同，因此我们可以写一个统一的 Node 结构的基类CvDNode来囊括我们所有关心的决策树生成算法，该基类需要实现如下功能：
- 根据离散型特征划分数据（ID3、C4.5、CART）
- 根据连续型特征划分数据（C4.5、CART）
- 根据当前的数据判定所属的类别
虽然说起来显得轻巧，但这之中的抽象还是比较繁琐的
树结构的实现
（本文会用到的所有代码都在这里）
由前文的诸多讨论可知，Tree 结构需要做到如下几点：
- 定义好需要在各个 Node 上调用的“全局变量”
- 做好数据预处理的工作、保证传给 Node 的数据是合乎要求的
- 对各个 Node 进行合适的封装，做到：
- 生成决策树时能够正确地调用它们的生成算法
- 进行后剪枝时能够正确地调用它们的局部剪枝函数
- 定义预测函数和评估函数以供用户调用
既然 Node 我们可以抽象出一个基类CvDNode，我们自然也能相应地对 Tree 结构抽象出一个基类CvDBase
决策树的剪枝算法
在知道怎么得到一颗决策树后、我们当然就会想知道：这样建立起来的决策树的表现究竟如何？从直观上来说，只要决策树足够深、划分标准足够细，它在训练集上的表现就能接近完美；但同时也容易想象，由于它可能把训练集的一些“特性”当做所有数据的“共性”来看待，它在未知的测试数据上的表现可能就会比较一般、亦即会出现过拟合的问题。我们知道，模型出现过拟合问题一般是因为模型太过复杂，所以决策树解决过拟合的方法是采取适当的“剪枝”、我们在上一篇文章中也已经大量接触了这一概念。剪枝通常分为两类：“预剪枝（Pre-Pruning）”和“后剪枝（Post-Pruning）”，其中“预剪枝”的概念在生成算法中已有定义，彼时我们采取的说法是“停止条件”；而一般提起剪枝时指的都是“后剪枝”，它是指在决策树生成完毕后再对其进行修剪、把多余的节点剪掉。换句话说，后剪枝是从全局出发、通过某种标准对一些 Node 进行局部剪枝，这样就能减少决策树中 Node 的数目、从而有效地降低模型复杂度