搜索
机器学习之提升方法重庆大学软件学院余俊良关键字•提升方法•强分类器弱分类器•分类器组合•AdaBoost•提升树(ignored)•随机森林提升方法的起源•boost方法系列的起源来自于PACLearnability。指出：在概率近似正确的学习的框架中，一个概念如果存在一个多项式的学习方法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习方法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。这套理论是由Valiant提出来的，也因此他获得了2010年的图灵奖。•PAC定义了学习算法的强弱弱学习算法---识别错误率小于1/2(即准确率仅比随机猜测略高的学习算法)强学习算法---识别准确率很高并能在多项式时间内完成的学习算法提升方法的起源•同时,Valiant和Kearns首次提出了PAC学习模型中弱学习算法和强学习算法的等价性问题,即任意给定仅比随机猜测略好的弱学习算法,是否可以将其提升为强学习算法?如果二者等价,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法,而不必寻找很难获得的强学习算法。也就是这种猜测，让无数牛人去设计算法来验证PAC理论的正确性。•Schapire在1996年证明了强可学习与弱可学习是等价的，并提出一个有效的算法真正实现了这个夙愿，它的名字叫AdaBoost。AdaBoost把多个不同的决策树用一种非随机的方式组合起来，表现出惊人的性能！第一，把决策树的准确率大大提高，可以与SVM媲美。第二，速度快，且基本不用调参数。第三，几乎不Overfitting。•这样一来，问题便成为，在学习中，如果已经发现了弱可学习算法，那么能否将它提升为强学习算法。提升方法的基本思路•提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。实际上，就是“三个臭皮匠顶个诸葛亮”的道理。•对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是通过改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。提升方法的基本思路•对提升方法来说，有两个问题需要回答：一是在每一轮如何改变训练数据的权值或概率分布；二是如何将弱分类器组合成一个强分类器。•关于第一个问题，AdaBoost的做法是，提高那些前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注，于是，分类问题被一系列的弱分类器“分而治之”。•关于第二个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法，具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起小的作用。AdaBoost算法•给定一个训练数据集T={(x1,y1),(x2,y2)…(xN,yN)}，其中实例𝑥∈𝜒，而实例空间χ∈𝑅，yi属于标记集合{-1,+1}，Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器，然后将这些弱分类器组合成一个强分类器。•Adaboost的算法流程如下：▫1.首先，初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权重：1/N。▫2.对于m=1,2,...,Ma.使用具有权值分布Dm的训练数据集学习，得到基本二元分类器：b.计算Gm(x)在训练数据集上的分类误差率c.计算Gm(x)的系数，am表示Gm(x)在最终分类器中的重要程度：d.更新训练数据集的权值分布▫3.构建基本分类器的线性组合▫从而得到最终分类器，如下：AdaBoost的例子•给定下列训练样本，请用AdaBoost算法学习一个强分类器。AdaBoost图解也许你看了上面的介绍或许还是对AdaBoost算法云里雾里的，没关系，看了以下图解之后就会对这个算法整体上很清晰了。下面我们举一个简单的例子来看看AdaBoost的实现过程：图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。AdaBoost图解第一步：根据分类的正确率，得到一个新的样本分布D2，一个子分类器h1其中划圈的样本表示被分错的。在右边的途中，比较大的“+”表示对该样本的权值做了调整。AdaBoost图解第二步：根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2AdaBoost图解第三步：得到一个子分类器h3AdaBoost图解整合所有子分类器：从结果中看，及时简单的分类器，组合起来也能获得很好的分类效果。AdaBoost的训练误差分析AdaBoost的优点简单来说，AdaBoost有很多优点:1)AdaBoost是一种有很高精度的分类器2)可以使用各种方法构建子分类器，AdaBoost算法提供的是框架3)当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单4)简单，不用做特征筛选5)不用担心Overfitting。其他的组合方法Bagging(Breiman,1996)在训练的每一轮中，均从原始样本集S中有放回地随机抽取训练样本集T（T的样本个数同S），这样一个初始样本在某轮训练中可能出现多次或根本不出现（S中每个样本未被抽取的概率为(1-1/|S|)|S|≈0.368，当|S|很大时）。最终的分类规则为简单多数投票法或简单平均法AdaBoost和Bagging的比较AdaBoost的训练集选取与前面各轮的学习结果相关；而Bagging训练集的选取是随机的，各轮训练集之间相互独立。AdaBoost的每个分量分类器有权重，而Bagging的没有权重。AdaBoost的每个分量分类器只能循序生成，而Bagging可以并行生成。随机森林随机森林随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。随机森林随机森林是一个树型分类器{h(x,k),k=1,…}的集合。其中元分类器h(x,k)是用CART算法构建的没有剪枝的分类回归树；x是输入向量；k是独立同分布的随机向量，决定了单颗树的生长过程；森林的输出采用简单多数投票法（针对分类）或单颗树输出结果的简单平均（针对回归）得到。随机森林算法•随机选取训练样本集：使用Bagging方法形成每颗树的训练集•随机选取分裂属性集：假设共有M个属性，指定一个属性数F≤M，在每个内部结点，从M个属性中随机抽取F个属性作分裂属性集，以这F个属性上最好的分裂方式对结点进行分裂（在整个森林的生长过程中，F的值一般维持不变）•每颗树任其生长，不进行剪枝随机森林算法在建立每一棵决策树的过程中，有两点需要注意-采样与完全分裂。首先是两个随机采样的过程，randomforest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(mM)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤-剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。随机森林算法按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。影响随机森林分类性能的主要因素•森林中单颗树的分类强度（Strength）：每颗树的分类强度越大，则随机森林的分类性能越好。•森林中树之间的相关度（Correlation）：树之间的相关度越大，则随机森林的分类性能越差。随机森林的优点两个随机性的引入，使得随机森林不容易陷入过拟合两个随机性的引入，使得随机森林具有很好的抗噪声能力在数据集上表现良好在当前的很多数据集上，相对其他算法有着很大的优势它能够处理很高维度（feature很多）的数据，并且不用做特征选择，在训练完后，它能够给出哪些feature比较重要在创建随机森林的时候，对generalizationerror使用的是无偏估计训练速度快在训练过程中，能够检测到feature间的互相影响容易做成并行化方法实现比较简单参考资料《统计学习方法》李航://《随机森林方法研究综述》方匡南等附录定理证明附录