机器学习中的提升方法.pptx

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