机器学习算法--集成学习

1. 个体和集成

     集成学习通过构建并结合多个“个体学习器”来完成学习任务。个体学习器通常由一个现有的学习算法从训练数据产生，若集成中只包含同种类型的个体学习器，称为同质集成；若包含不同类型的个体学习器，为异质集成。同质集成中的个体学习器也成为“基学习器”。

    如何产生并结合“好而不同”的个体学习器，恰是集成学习研究的核心。

    根据个体学习器的生成方式，目前的集成学习方法大致分为两大类：

（1）个体学习器间存在强依赖关系，必须串行生成的序列化方法，代表为Boosting

（2）个体学习器间不存在强依赖关系，可同时生成的并行化方法，代表为Bagging和“随机森林”

2. Boosting

    Boosting是一族可将弱学习器提升为强学习器的算法，这族算法的工作机制类似：（1）先从初始训练集训练出一个基学习器；（2）再根据学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注；（3）基于调整后的样本分布来训练下一个基学习器。如此重复进行，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合。

    Boosting族算法最著名的代表是AdaBoost，其算法特点如下：

（1）每次迭代改变的是样本的分布，而不是重复采样；

（2）样本分布的改变取决于样本是否被正确分类，总是分类正确的样本权值低，总是分类错误的样本权值高（通常是边界附近的样本）；

（3）最终的结果是弱分类器（基分类器）的加权组合，权值表示该若分类器的性能。

  下面我们举一个简单的例子来看看AdaBoost的实现过程：

    图中，“+” 和 “-” 分别表示两种类别，在这个过程中，使用水平或者垂直的直线作为分类器，来进行分类。

    第一步：根据分类的正确率，得到一个新的样本分布 D2，一个子分类器 h1，其中画圈的样本表示被分错的，在右边的图中，比较大的“+”表示对该样本做了加权。

    图中的 ε1=0.3，表示的是错误率；α1=0.42，表示该分类器的权重，α1=1/2*ln(1- ε1/ ε1)

    第二步：根据分类正确率，得到一个新的样本分布 D3，一个子分类器 h2

    第三步：得到一个子分类器h3

    整合所有的子分类器：

    因此，可以得到整合的结果，从结果中看，即使简单的分类器，组合起来也能获得很好的分类效果。

    AdaBoost算法的两个特性：（1）训练错误率的上界，随着迭代次数的增加，会逐渐下降；（2）即使训练次数很多，也不会出现过拟合现象

    AdaBoost的算法流程如下：

    步骤1. 首先，初始化数据的权值分布，每一个训练样本最开始时都被赋予相同的权值：1/N

    步骤2. 进行多轮迭代，用m=1,2,...M表示迭代的第多少轮

    （a）使用具有权值分布Dm的训练数据集学习，得到基本分类器（选取让误差率最低的阈值来设计基本分类器）：

    （b）计算Gm(x)在训练数据集上的分类误差率

      由上述式子可知，Gm(x)在训练数据集上的分类误差率em就是被Gm(x)误分类样本的权值之和。

    （c）计算Gm(x)的系数，am表示Gm(x)在最终分类器中的重要程度（目的：得到基本分类器在最终分类器中所占的比重）：

      由上述式子可知，em<=1/2时，am>=0，且am随着em的减小而增大，意味着分类误差率越小的基本分类器在最终分类器中的作用越大。

    （d）更新训练数据集的权值分布（目的：得到样本的新的权值分布），用于下一轮迭代

      使得被基本分类器Gm(x)误分类样本的权值增大，而被正确分类样本的权值减小。就这样，通过这样的方式，AdaBoost方法能“重点关注”或“聚焦”于那些较难分的样本上。其中yi={+1,-1}，Zm是规范化因子，使得Dm+1成为一个概率分布。

    步骤3. 组合各个弱分类器

    从而得到最终分类器，如下：

   注：从偏差-方差分解的角度来看，Boosting主要关注降低偏差，因此Boosting能基于泛化能力相当弱的学习器构建出很强的集成

3. Bagging和随机森林

    为什么出现这两种方法？由前面可知，如果想要得到泛化能力比较强的集成，集成中的个体学习器应尽可能相互独立。一种可能的方法是对训练样本进行采样，产生出若干个不同的子集，再从每个子集中训练出一个基学习器。训练数据不同，获得的学习器可能会有较大差异。但是若每个子集完全不同，那么每个基学习器只用到一小部分训练数据，不足以有效学习。所以，为了解决这个问题，我们可以考虑使用相互交叠的采样子集

    <1> Bagging是并行式集成学习方法最著名的代表。

    Bagging基本流程：（1）采样出T个含m个训练样本的采样集，采用自助采样法：给定包含m个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样经过m次随机采样操作，我们得到含有m个样本的采样集，初始样本集有的样本在采样集里面出现多次，有的则从未出现。初始训练集中约有63.2%的样本出现在采样集中。重复操作，得到T个含m个训练样本的采样集；（2）基于每个采样集训练出一个基学习器；（3）将这些基学习器进行结合（分类任务使用简单投票，回归任务使用简单平均法）。

     算法优点： （1）训练一个Bagging集成与直接使用基学习算法训练一个学习器的复杂度相同，说明很高效；

                    （2）Bagging能不经修改的用于多分类、回归等任务（AdaBoost一般用于二分类）；

                    （3）自助采样过程带来的另外一个优点：由于每个基学习器只使用了初始训练机中约63.2%的样本，剩下约36.8%可用作验证集对泛化性能进行“包外估计”。当基学习器为决策树

                       时，可使用包外样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理；当基学习器为神经网络时，可使用包外样本来辅助早期停止以减少过拟

                       合风险。

    注：从偏差-方差角度来看，Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更明显。

    <2> 随机森林（RF）是Bagging的一个扩展变体

    RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体来说，传统决策树在选择划分属性时是在当前结点的属性集合（假定有d个属性）中选择一个最优属性；而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。一般情况下，推荐k=log₂d。

    随机森林起始性能往往相对较差，特别是在集成中只包含一个基学习器时，因为引入了属性扰动。然而，随着个体学习器数目增加，RF会收敛到更低的泛化误差。值得一提的是，RF效率往往优于Bagging，Bagging使用的是“确定型”决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用“随机型”决策树则只需考察一个属性子集。

    简单来说，随机森林就是由多棵CART（Classification And Regression Tree）构成的。

    在建立每一棵决策树的过程中，有两点需要注意–采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个（与Bagging相同）。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 – 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。

注：有关分类效果的评判标准，因为使用的是CART，因此使用的也是CART的评判标准，和C3.0,C4.5都不相同。

对于分类问题（将某个样本划分到某一类），也就是离散变量问题，CART使用Gini值作为评判标准。定义为Gini=1-∑(P(i)*P(i)),P(i)为当前节点上数据集中第i类样本的比例。例如：分为2类，当前节点上有100个样本，属于第一类的样本有70个，属于第二类的样本有30个，则Gini=1-0.7×07-0.3×03=0.42，可以看出，类别分布越平均，Gini值越大，类分布越不均匀，Gini值越小。在寻找最佳的分类特征和阈值时，评判标准为：argmax（Gini-GiniLeft-GiniRight），即寻找最佳的特征f和阈值th，使得当前节点的Gini值减去左子节点的Gini和右子节点的Gini值最大。

对于回归问题，相对更加简单，直接使用argmax(Var-VarLeft-VarRight)作为评判标准，即当前节点训练集的方差Var减去减去左子节点的方差VarLeft和右子节点的方差VarRight值最大。

参考：http://www.cnblogs.com/harvey888/p/5505511.html     AdaBoost算法

        http://baidutech.blog.51cto.com/4114344/743809/        AdaBoost算法

        http://blog.csdn.net/qq_30189255/article/details/51532442     Bagging算法

        http://www.36dsj.com/archives/21036   随机森林算法

        http://www.cnblogs.com/hrlnw/p/3850459.html    随机森林算法

        《机器学习》，周志华著