1、 数据挖据技术集成学习方法集成学习方法(ensemble learnig)王磊王磊 （副教授）（副教授）经济信息工程学院经济信息工程学院2 2第六章：第六章：集成学习方法集成学习方法n基本概念基本概念nbaggingnboostingn随机森林n选择性集成方法n在机器学习中，直接建立一个高性能的分类器是很困难的。n但是，如果能找到一系列性能较差性能较差的分类器（弱分类器）的分类器（弱分类器），并把它们集成起来的话，也许就能得到更好的分类器。n日常生活中，“三个臭皮匠，胜过诸葛亮”，便是体现了这种思想。集成学习的基本概念Classifier ensembleihi(x)hn(x)h2(x)h1(
2、x)Input vectorClassifier 1Classifier 2Classifier NCombine ClassifiersOutputx集成学习：图示n我们一般选定加权平均的方法来构造集成学习的最终学习器。n但是里面的每一个 弱分类器（弱分类器（i）怎样构造呢）怎样构造呢？n有一些研究，是针对每个学习器都不同构的情况，比如有一些研究，是针对每个学习器都不同构的情况，比如识别一个人，一个学习器考虑脸，另一个考虑步态，另识别一个人，一个学习器考虑脸，另一个考虑步态，另一个考虑指纹。这种研究通常称为一个考虑指纹。这种研究通常称为Information FusionInformatio
3、n Fusion，不在我们今天讨论的范畴。n狭义的集成学习（ensemble learning），是用同样同样类型的学习算法类型的学习算法来构造不同不同的弱学习器的方法。集成学习：如何构造？n办法就是改变训练集。办法就是改变训练集。n通常的学习算法，根据训练集的不同，会给出不同的学习器。这时就可以通过改变训练集来构造不同的学习器。然后再把它们集成起来。集成学习：如何构造？n在原来的训练集上随机采样，可以得到新的训练集。【随机采样】集成学习（Ensemble Learning）是一种机器学习方法，它使用多个（通常是同质的）学习器来解决同一个问题 问题.问题 集成学习中使用的多个学习器称为个体学习
4、器当个体学习器均为决策树时，称为“决策树集成”当个体学习器均为神经网络时，称为“神经网络集成”集成学习的定义由于集成学习技术可以有效地提高学习系统的泛化能力，因此它成为国际机器学习界的研究热点，并被国际权威 T.G.Dietterich 称为当前机器学习四大研究方向之首T.G.Dietterich,AIMag97问题：对20维超立方体空间中的区域分类左图中纵轴为错误率从上到下的四条线分别表示：平均神经网络错误率最好神经网络错误率两种神经网络集成的错误率令人惊奇的是，集成的错误率比最好的个体还低 L.K.Hansen&P.Salamon,TPAMI90【集成学习的重要性】集成学习技术已经在行星探
5、测、地震波分析、Web信息过滤、生物特征识别、计算机辅助医疗诊断等众多领域得到了广泛的应用只要能用到机器学习的地方，就能用到集成学习【集成学习的应用】期望结果个体1(精度33.3%)个体2(精度33.3%)个体3(精度33.3%)集成(精度33.3%)投票个体必须有差异期望结果个体1(精度33.3%)个体2(精度33.3%)个体3(精度33.3%)集成(精度0%)投票个体精度不能太低EEA个体学习器越精确、差异越大，集成越好A.Krogh&J.Vedelsby,NIPS94既然多个个体的集成比单个个体更好，那么是不是个体越多越好?更多的个体意味着：在预测时需要更大的计算开销，因为要计算更多的个
6、体预测 更大的存储开销，因为有更多的个体需要保存个体的增加将使得个体间的差异越来越难以获得集成策略集成策略n有多种策略可以将q个弱分类器组合成集成分类器。集成策略集成策略1.从大小为n的原始数据集D中独立随机地抽取n个数据(n=n)，形成一个自助数据集；2.重复上述过程，产生出多个独立的自助数据集；3.利用每个自助数据集训练出一个“分量分类器”；4.最终的分类结果由这些“分量分类器”各自的判别结果投票决定。基本思想：对训练集有放回地抽取训练样例，从而为每一个基本分类器都构造出一个跟训练集相当大小但各不相同的训练集，从而训练出不同的基本分类器；该算法是基于对训练集进行处理的集成方法中最简单、最直
7、观的一种。Boosting流程描述流程描述nStep1:原始训练集输入nStep2:计算训练集中各样本的权重nStep3:采用已知算法训练弱学习机，并对每个样本进行判别nStep4:计算对此次的弱学习机的权重nStep5:转到Step2,直到循环到达一定次数或者某度量标准符合要求nStep6:将弱学习机按其相应的权重加权组合形成强学习机核心思想核心思想n样本的权重n没有先验知识的情况下，初始的分布应为等概分布，也就是训练集如果有N个样本，每个样本的分布概率为1/Nn每次循环一后提高错误样本的分布概率，分错样本在训练集中所占权重增大，使得下一次循环的弱学习机能够集中力量对这些错误样本进行判断。n
8、弱学习机的权重n准确率越高的弱学习机权重越高n循环控制：损失函数达到最小n在强学习机的组合中增加一个加权的弱学习机，使准确率提高，损失函数值减小。简单问题演示（简单问题演示（Boosting训练过程）训练过程）算法算法boosting数学描述数学描述n训练集 (x1,y1),(x2,y2),(xN,yN)nxi Rm,yi -1,+1nDt 为第t次循环时的训练样本分布（每个样本在训练集中所占的概率，Dt总和应该为1）nht:X-1,+1 为第t次循环时的Weak learner，对每个样本给出相应的假设，应该满足强于随机猜测：nwt为ht的权重n 为t次循环得到的Strong learner
9、21),()(xhyPtDyxttiitiithwsignH1)()(样本权重样本权重n思想：提高分错样本的权重n 反映了strong learner对样本的假设是否正确n采用什么样的函数形式？)(itiHywrongrightHyiti00)()(expitiHy弱学习机权重弱学习机权重n思想：错误率越低，该学习机的权重应该越大n 为学习机的错误概率n采用什么样的函数形式？和指数函数遥相呼应：)(),(xhyPtDyxtt tttw1ln21AdaBoost算法算法25Adaboost 训练过程训练过程26Adaboost 训练过程训练过程27Adaboost 训练过程训练过程Adaboos
10、t的缺点的缺点随机森林算法随机森林算法n随机森林算法是Leo Breiman于2001年提出的一种新型分类和预测模型，它具有需要调整的参数少，不容易过度拟合，分类速度快，能高效处理大样本数据等特点。nBagging和AdaBoost等方法只是通过改变样本的权重来获得不同的弱分类器。随机森林（RF）则通过同时改变样本和同时改变样本和特征子集来获得不同的弱分类器特征子集来获得不同的弱分类器。随机森林算法随机森林算法n随机森林是采用随机的方式建立一个森林，森林有很多决策树组成，每棵决策树之间没有关联。对于新的测试样本，让森林中的每一棵决策树分布分别进行一下判断，依据多数者投票方法决定样本的类别。完全
11、分裂的方式完全分裂的方式随机特征选取随机特征选取n当特征个数M较多时，随机选择m个用于训练决策树。m越小，树的相关性越小，且训练速度越快。n当特征个数M较少时，可以由M个特征进行随机线性组合来产生M 个扩展特征，然后，在（M+M）上随机选择m个特征，构建决策树。n其中，每一个扩展特征的构造如下：从现有M特征中随机抽取L个，它们的权重系数是-1,+1区间的均匀随机数。然后，由L个已有特征线性组合出扩展特征。随机特征数的确定随机特征数的确定选择性集成算法选择性集成算法n一方面，使用更多的学习器将导致更大的计算和存储开销一方面，使用更多的学习器将导致更大的计算和存储开销，另一方面，当个体学习器数目增
12、加之后，学习器之间的，另一方面，当个体学习器数目增加之后，学习器之间的差异将越来越难以获得。差异将越来越难以获得。n因此，提出问题：为了达到更好的性能，是否必须为了达到更好的性能，是否必须使用更多的个体学习器使用更多的个体学习器？选择性集成的理论分析选择性集成的理论分析选择性集成的理论分析选择性集成的理论分析选择性集成的理论分析选择性集成的理论分析选择性集成的理论分析选择性集成的理论分析问题求解问题求解问题求解问题求解GASEN算法算法论文讲解论文讲解n基于约束投影的支持向量机选择性集成基于约束投影的支持向量机选择性集成，2009研究题目：研究题目：Local Boostingna local boosting algorithm for solving classification problem,Computational Statistics&Data Analysis 52,2008n要求：准备30分钟左右的ppt，讲清楚LS-SVM的原理及特点。
