在机器学习的分类中，集成学习是按照学习方式分类的一种机器学习，所以先从集成学习讲起。
集成学习
概念
好比人做出一个决策时，会从不同方面，不同角度，不同层次去思考（多个自我，多个价值观），这就会有多个决策结果产生，最终我们会选一种决策作为最终决策。
集成学习（Ensemble Learning）：
- 通常一个集成学习器的分类性能会好于单个分类器，将多个分类方法聚集在一起，以提高分类的准确率。
- 集成学习并不算是一种学习器，而是一种学习器结合的方法。
- 集成学习法由训练数据构建一组基学习器，然后通过对每个基学习器的预测进行投票来产生最终预测。
- 集成学习中需要有效地生成多样性大的基学习器，即多样性增强（增强泛化特性，减小一次预测的方差）：即对样本、特征，学习器进行扰动。
特点
集成方法是一种将几种机器学习技术组合成一个预测模型的元算法，以减小方差（bagging），偏差（boosting），或者改进预测（stacking）。
稳定学习器的集成不太有利，因为这样的集成并不会提升泛化特性。例如，决策树集成相对于kNN集成达到了较高的准确率。kNN对训练样本的扰动不敏感，因此也被称为稳定学习器（stable learner）。
集成方式
- 同构集成：大多数集成方法使用一个基学习算法来产生多个同构基学习器，即相同类型的学习器，这就是同构集成（homogeneous ensembles）。
- 异构集成：也有一些方法使用的是异构学习器，即不同类型的学习器，这就是异构集成（heterogeneousensembles）。为了使集成方法能够比任何构成它的单独的方法更准确，基学习器必须尽可能的准确和多样。
学习模式
- 串行：个体学习器之间存在强依赖关系，必须串行生成的序列化方法
- 并行：个体学习器不存在强依赖关系，可以同时生成的并行化方法
举例（图片来自网络）
集成学习又分为两大类
一、bagging
bagging为bootstrap aggregating简写，即套袋法，过程如下，
- 抽取多组训练集：每个样本集都是从原始样本集中有放回的抽取n次，组成训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行m轮，得到m个训练集，训练集之间相互独立。
- 基学习器：每次使用一个训练集得到一个模型，m个训练集共得到m个模型。
- 投票：分类问题：将上步得到的m个模型采用投票的方式得到分类结果；回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）
bagging本质
对一个样本空间，随机有放回的抽样出若干独立的训练样本，以此来增加样本扰动，多轮次抽样训练后形成多个估计，然后平均多个估计，达到降低一个估计的方差，也就是增强学习器的泛化特性。
二、boosting
其主要思想是将弱分类器组装成一个强分类器。在PAC（概率近似正确）学习框架下，则一定可以将弱分类器组装成一个强分类器。
Adaboost
Adaboost是一种基于boost思想的一种自适应的迭代式算法。通过在同一个训练数据集上训练多个弱分类器(weak classifier)，然后把这一组弱分类器集成起来，产生一个强分类器（strong classifier）。
特点
(1) 每次迭代改变的是样本的分布，而不是重复采样
(2) 样本分布的改变取决于样本是否被正确分类：总是分类正确的样本权值低，总是分类错误的样本权值高（通常是边界附近的样本）
(3) 最终的结果是弱分类器的加权组合
Bagging VS Boosting
(1) 样本选择上
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
(2) 样例权重
Bagging：使用均匀取样，每个样例的权重相等
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
(3) 预测函数
Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
(4) 计算方式
Bagging：各个预测函数可以并行生成
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
随机森林
决策树
概念
决策树是用树的结构来构建分类模型，每个节点代表着一个属性（特征），根据这个属性（特征）的划分，进入这个节点的儿子节点，直至叶子节点，每个叶子节点都表征着一定的类别，从而达到分类的目的。
常用的决策树有ID4，C4.5，CART等。在生成树的过程中，需要选择用那个特征进行剖分，一般来说，选取的原则是，分开后能尽可能地提升纯度，可以用信息增益，增益率，以及基尼系数等指标来衡量。
如果是一棵树的话，为了避免过拟合，还要进行剪枝，取消那些可能会导致验证集误差上升的节点。
特点
树模型和线性模型有什么区别呢？
- 树模型拟合出来的函数其实是分区间的阶梯函数。树形模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性（可以抽取规则）。
- 决策树与逻辑回归的分类区别也在于此，逻辑回归是将所有特征变换为概率后，通过大于某一概率阈值的划分为一类，小于某一概率阈值的为另一类；而决策树是对每一个特征做一个划分。
- 逻辑回归只能找到线性分割，而决策树可以找到非线性分割。
- 树形模型是一个一个特征进行处理，线性模型是所有特征给予权重相加得到一个新的值。
例子
判断一种生物是不是鱼类：
纯度
决策树思想，实际上就是寻找最纯净的划分方法，这个最纯净在数学上叫纯度，就是根据特征划分数据集后，标定结果要分得足够开（label=1的和label=0的混到一起就会不纯）。
在前面提到，寻找最好的分割点是通过量化分割后类的纯度来确定的，目前有三种纯度计算方式，分别是
(1) Gini不纯度：从一个数据集中随机选取数据点度量其被错误分类到其他分组里的概率。
(2) 熵（Entropy）：计算划分前后数据集的熵，对比信息增益的大小来确定哪一种特征是最有效的划分。
(3) 错误率（Error）：信息增益率。
根据不纯度的计算方法的不同，决策树划分为以下三类，
- CART：基尼系数。
- ID3：信息增益。
- C4.5：信息增益率。
决策树要达到寻找最纯净划分的目标要干两件事：建树和剪枝。
建树
ID3决策树
- 信息：对于某观察者，确定一个事件的可能情况所需要的物理量。
- 香农熵：对于某观察者，确定一个事件各种可能情况信息的期望。
- 信息增益：在划分数据集之前之后信息发生的变化
- 用信息增益来对比用各个特征划分数据集后的效果
信息：
熵：
注意：对于等待率事件：
ID3决策树建树过程
- 遍历当前所有代划分特征，对每个特征划分一次数据集，计算划分后的所有子树熵，并求和。
- 计算划分前数据集的熵值。
- 分别与划分之前的熵进行对比，求得信息增益
- 选择信息增益最大的特征划分最为最优划分。
例如，在对于例子中的第一次划分中，按照特征1和特征2划分的计算信息增益的过程中，按照特征1划分的计算信息增益的过程如下：
子集1的熵：
子集2的熵：
原始数据集的熵：
所以按照特征1划分后的信息增益即为：
这其实是一种贪心算法，每次都选择最优的信息增益的特征划分。
采用自顶向下的递归的方法，基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处熵值为0（叶节点中的实例都属于一类）。
变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。
一般来讲，信息增益越大，说明如果用属性a来划分样本集合D，那么纯度会提升，因为我们分别对样本的所有属性计算增益情况，选择最大的来作为决策树的一个结点，或者可以说那些信息增益大的属性往往离根结点越近，因为我们会优先用能区分度大的也就是信息增益大的属性来进行划分。当一个属性已经作为划分的依据，在下面就不在参与竞选了，我们刚才说过根结点代表全部样本，而经过根结点下面属性各个取值后样本又可以按照相应属性值进行划分，并且在当前的样本下利用剩下的属性再次计算信息增益来进一步选择划分的结点，ID3决策树就是这样建立起来的。
ID3算法缺陷：
- 抗噪声性差，如果数据样本数量太少或噪声太大，就会产生过拟合的问题。样本少，其树的构成基本上就是为少数样本量身定做的树，如果噪声太大，或样本少且有噪声的话，很多树枝都是噪声拟合出来的。
- 在选择最优特征时，很容易倾向于选择“特征值种类较多”的特征，作为分类特征。我们举个极端点的例子，假设有100个样本集，现在有一个特征其数值种类也是100，如果按该特征分类，就能把这个样本集分成100份，每份一个样本。在用ID3算法做决策树时，肯定会选择这个特征作为第一个最优特征，因为这个特征分出来的样本集每一个纯度都是最高。
- 无法处理特征值为连续型数据的特征。（不过可以考虑把连续型数据转化成离散型数据）
C4.5决策树：先算信息增益，然后再选取增益率最高的
针对上面说的ID3算法的第二个缺点“最优特征选择倾向于特征种类较多的特征”。我们先来看下特征种类较多时，分类会发生什么。
假设都是均分100个样本，特征值有2种的特征会把样本集分成50和50。特征值为4种的特征会把样本集分成25、25，25，25。
可见特征值越多，就会产生越多的“小数目”样本集，而小数目样本集在分类效果上是不如大样本集好的（如过拟合、抗噪差等问题），所以对于某特征分类后会产生“小数目”样本集的分类后的熵，我们需要有一个惩罚值，即：分类后产生的样本集越小，它的熵值也要惩罚性的增大。
这样虽然ID3算法中会因为很多分类后的小数量样本集而产生低值的期望熵，但做惩罚值处理后，熵值就会平衡性的增大。
信息增益率：
在C4.5中惩罚小数量样本集的做法是，在根据某特征分类，并计算出分类前后的熵差后，再计算该特征的惩罚值，用该分类特征的熵差除以惩罚值得出“信息增益率”，使信息增益率越大的特征，就是最优特征。即：
其中惩罚值实际上就是“信息熵”，只不过这里的信息指的不是计算信息增益时“样本集中分类结果的平均不确定性”，而是“总样本集中分类后子样本集数目的平均不确定性”，即：
其中：
D：分类前的总样本数量。
i：按某特征分类后样本子集序号。
Di：按某特征分类后的第i个子集的数量。
由此看出，样本数量越少，惩罚值越大，相除后的信息增益率也就越小，依此做到了一定的平衡，由于“惩罚”了小样本数量集，其由于数量少带来信息增益抗噪性差的问题也得到一定程度的解决。
这就是C4.5算法最大的好处，解决了ID3算法第二个缺陷，缓解了ID3算法的第一个缺陷。不过ID3算法的第三个不能处理连续型特征数据的问题。C4.5算法本身也不能直接处理连续数据。
另外，C4.5和ID3算法还有一个特点，这俩算法的根本其实都要计算信息增益，而信息增益的一个大前提就是要先进行分类，然后才能计算增益，所以，每计算一次增益也就代表进行了一次分类，分类用了的特征接下来就不能再用了，所以ID3和C4.5算法在分类时会不断消耗特征。
CART决策树：
简单来讲就是，有一个类似于熵的指标叫Gini指数，其代表了分类结果的不确定性，所以自然是越小越好。
每次分类前计算分类前后的Gini指数，求差得出“Gini指数增益”，能使Gini指数增益最大的特征就是最优特征。
需要注意的是，CART算法分类时，即使特征有大于两个特征值，也还是会把样本集分成两类，最后形成的是标准二叉树。
Gini指数：
首先计算分类前样本集的Gini指数，Gini指数想表达的东西和信息熵类似，都是想表达样本集分类结果的不确定性，Gini指数或熵越大，表示样本集分类结果不确定性也越大。
三种方法对比：
(1) ID3和C4.5在每个结点上可以产生多个分支，而CART每个结点只会产生两个分支
(2) C4.5通过引入信息增益比，弥补了ID3在特征取值比较多时，由于过拟合造成泛化能力变弱的缺陷
(3) ID3只能处理离散型变量，而C4.5和CART可以处理连续型变量
(4) ID3和C4.5只能用于分类任务，而CART可以用于分类和回归任务
剪枝
决策树的构建是一个递归的过程，理想情况下所有的记录都能被精确分类，即生成决策树叶节点都有确定的类型，但现实这种条件往往很难满足，这使得决策树在构建时可能很难停止。即使构建完成，也常常会使得最终的节点数过多，从而导致过度拟合（overfitting），因此在实际应用中需要设定停止条件，当达到停止条件时，直接停止决策树的构建。但这仍然不能完全解决过度拟合问题，过度拟合的典型表现是决策树对训练数据错误率很低，而对测试数据其错误率却非常高。过度拟合常见原因有：
- 训练数据中存在噪声；
- 数据不具有代表性。
过度拟合的典型表现是决策树的节点过多，因此实际中常常需要对构建好的决策树进行枝叶裁剪（Prune Tree），但它不能解决根本问题，随机森林算法的出现能够较好地解决过度拟合问题。
树的剪枝分为预剪枝和后剪枝。
- 预剪枝：通过启发式方法，在生成决策树过程中对划分进行预测，若当前结点的划分不能对决策树泛化性能提升，则停止划分，并将其标记为叶节点
- 后剪枝：对已有的决策树，自底向上的对非叶结点进行考察，若该结点对应的子树替换为叶结点能提升决策树的泛化能力，则将改子树替换为叶结点
随机森林
RandomForest，2001年由Breiman提出。
尽管决策树有剪枝等等方法，随机森林算法的出现能够较好地解决过度拟合问题，解决决策树泛化能力弱的缺点。
由多个决策树构成的森林，算法分类结果由这些决策树投票得到，决策树在生成的过程当中分别在行方向和列方向上添加随机过程，行方向上构建决策树时采用放回抽样得到训练数据，列方向上采用无放回随机抽样得到特征子集（如果把训练数据看成矩阵，就像实际中常见的那样，那么就是一个行和列都进行采样的过程），并据此得到其最优切分点，这便是随机森林算法的基本原理。
随机森林实际上是一种特殊的bagging方法，它将决策树用作bagging中的模型。首先，用bootstrap方法生成m个训练集，然后，对于每个训练集，构造一颗决策树，在节点找特征进行分裂的时候，并不是对所有特征找到能使得指标（如信息增益）最大的，而是在特征中随机抽取一部分特征，在抽到的特征中间找到最优解，应用于节点，进行分裂。随机森林的方法由于有了bagging，也就是集成的思想在，实际上相当于对于样本和特征都进行了采样，所以可以避免过拟合。
RandomForest在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。最终随机森林的偏差可能会轻微增大，但是由于平均了几个不相关的树的结果，降低了方差，导致最终模型的整体性能更好。
传统决策树在选择划分属性时是在当前结点的属性集合中选择一个最优属性；而在RF中，对基决策树的每个结点，是从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性进行划分。
随机森林在bagging的基础上更进一步：
- 样本的随机：从样本集中用Bootstrap随机选取n个样本
- 特征的随机：从所有属性中随机选取K个属性，选择最佳分割属性作为节点建立CART决策树（泛化的理解，这里面也可以是其他类型的分类器，比如SVM、Logistics）
- 重复以上两步m次，即建立了m棵CART决策树
- 这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类（投票机制有一票否决制、少数服从多数、加权多数）
