《模式识别》课件 第九章 组合分类器

第九章组合分类器分类方法基于经典统计理论的分类法参数法从训练集中直接得出分类结果引言该方法是在已知先验类别概率和类条件概率，用贝叶斯公式求出判别函数。优点：最优分类（理论）缺点：实际应用中很难实现直接求取分类判别函数（分类面）事先能确定判别函数或分类面的形式，再通过训练样本确定其中的参数。如SVM，线性判别分析等非参数如近邻法等1.基于经典统计理论的分类法2.参数法3.从训练集直接得出分类结果评估分类法的准确率保留法（holdout）k-倍交叉验证（k-foldcrossvalidation）提高分类法的准确率

“arcing”(adaptivereweightingandcombining):重新使用或选择数据，以期达到改善分类器性能的目的。baggingboosting分类法的准确性holdout划分为两个独立的数据集：训练集，测试集变形：随机子选择评估分类法的准确率（1）数据训练集测试集导出分类法评估准确性k-倍交叉验证将数据集分为k个子集；用k-1个子集作训练集，1个子集作测试集，然后k次交叉验证求平均。评估分类法的准确率（2）数据S1S2Sk···训练集测试集BaggingBoosting组合分类器的核心思想是：对于多个单独分类器的结果进行组合。提高分类法的准确率训练数据C1C2Ct组合得票测试数据类预测···组合分类器的核心思想是对于多个单独的分类器的结果进行加权整合，以获得一个更好的性能！个体与组合的关系泛化误差计算复杂度其他评价标准分类器组合评价假设E(s)表示在数据集s上的组合分类结果，那么E(s)的泛化误差则是根据带类标的样本空间分布对任意数量选定样本的误分类概率。估计泛化误差实验方法保留法交叉验证估计自举法泛化误差计算复杂度一般是通过比较每一分类器在执行过程中耗费的CPU总数，可以将其分为如下三种度量：计算复杂度产生一个新的分类器的计算复杂度更新一个分类器的计算复杂度将一个新样本进行分类的计算复杂度总体复杂度可以看作是这三种度量方式的总和，特别是当数据集数量较大时，更应当考虑到产生某一新的分类器的损耗。鲁棒性稳定性可解释性大规模数据的可测量性

其他评价标准Bagging集成算法基本思想给定一个学习算法和一个训练集（n个样本），让该学习算法训练多轮，每轮的训练集由从初始的训练集中随机取出n个样本组成（放回取样），初始训练样本在某轮训练集中可以出现多次或根本不出现。训练之后得到一个预测函数序列，最终的预测函数对分类问题采用投票方式，对回归问题采用简单平均。最后结果准确率将得到提高。Bagging集成算法算法

Fort=1,2,…,TDo

从数据集S中取样（放回选样） 训练得到模型Ht

对未知样本X分类时,每个模型Ht都得出一个分类，得票最高的即为未知样本X的分类也可通过得票的平均值用于连续值的预测Bagging集成算法架构…C1

C2

CT

traintraintrain…c1(x)c2(x)cT(x)C*

c*(x)=maxcnttct(x)S1

S2

ST

X

预处理例题分析例：现有10个人的两门课程考试数据如表9.1所示：(1070)，(2070)，(3010)，(4060)，(6080)，(6050)，(7090)，(8070)，(9080)，(10060)。每一门课程（分别用X1，X2表示）要求大于60分为合格，未达到60分的视为不合格，其中“X”表示至少有一门课程未通过，而“O”表示两门课程均通过。

根据10个样本数据绘制数据分布图

学号01020304050607080910成绩(10,70)(20,70)(30,10)(40,60)(60,80)(60,50)(70,90)(80,70)(90,80)(100,60)是否全通过否否否否是否是是是是10个考试成绩样本数据及其类标使用线性分类器对样本进行划分，首先从10个样本成绩中随机抽取5个样本，一共抽取三轮，抽取结果如下：第一轮：02、03、05、05、10号样本，第二轮：04、04、06、09、10号样本，第三轮：03、04、08、08、09号样本，因此构造出三个线性分类器分别为：

学号01020304050607080910成绩(10，70)(20，70)(30，10)(40，60)(60，80)(60，50)(70，90)(80，70)(90，80)(100，60)h1-1-1-1-1111111h2-1-1-1-1-1-1-1111h311-1-11-1111-1投票结果-1-1-1-11-11111使用不同的分类器对样本数据进行划分根据这三个线性分类器进行投票表决Bagging集成算法分析Bagging要求“不稳定”的分类方法；

比如：决策树，神经网络算法不稳定：数据集的小的变动能够使得分类结果的显著的变动弱学习算法的稳定性是Bagging能否提高预测准确率的关键因素：Bagging对不稳定的学习算法能提高预测的准确度，而对稳定的学习算法效果不明显，有时甚至使预测的准确度降低。（Breiman1996)

随机森林（1）随机森林（RandomForest，RF）是Bagging的一种扩展算法，它以决策树作为基本的弱分类器，与Bagging不同的是，它并非从所有特征中选择最优特征作为分界，而是在一个特征子集中选择最优，即引入了随机特征选择，并因此提升了其方法的泛化性能。随机森林（2）算法：输入：训练集D={(x1,y1),(x2,y2),...,(xn,yn)}决策树H：重采样的样本分布Db样本集训练特征数目为M，训练轮数T

训练过程:

fort=1，2，……，T

form=1，2，……，（为M的子集）

ht=H(m,Db)

endfor

endfor输出：Boosting背景提出问题：强学习算法：准确率很高的学习算法弱学习算法：准确率不高，仅比随机猜测略好是否可以将弱学习算法提升为强学习算法目标：提高任何给定的学习算法的分类准确率Boosting背景最初的Boosting算法

Schapire1989提出AdaBoost（adaptiveboosting）算法

FreundandSchapire1995提出基本思想：每个样本都赋予一个权重T次迭代，每次迭代后，对分类错误的样本加大权重，使得下一次的迭代更加关注这些样本。Boosting过程：在一定的权重条件下训练数据，得出分类法Ct根据Ct的错误率调整权重SetofweightedinstancesClassifierCt

trainclassifier

adjustweightsBoosting……h1(x)h2(x)hT(x)C*

c*(x)=sign(Sath2t(x))C1

trainS1trainC2

S2CT

trainSTXD1D2DTBoosting总结(1)Boosting易受到噪音的影响；AdaBoost可以用来鉴别异常；经过多轮后，具有最高权重的样本即为异常。应用Boosting，不需寻找很难获得的预测精度很高的强学习算法，只需找出精度稍好于随机预测的弱学习算法即可。但是同时也有可能使集成过分偏向于某几个特别困难的示例。因此，该方法不太稳定，有时能起到很好的作用，有时却没有效果。Boosting类别中的一种；非常成功的机器学习算法，由YoavFreund和RobertSchapire于1995年提出，他们因此获得了2003年的哥德尔奖（GödelPrize）。前一轮训练结果将用来调整本轮训练的样本，从而优化本轮训练出的模型，使得整个的模型更加精确。AdaBoost侧重于调整本轮样本的样本权重，从而改变样本的分布。AdaBoost（AdaptiveBoosting）AdaBoost输入:(X1,Y1),(X2,Y2),…(Xn,Yn)

Xi∈X,Yi∈Y={+1,-1}

初始化:W1(i)=1/nFort=1,…,T，do:在Wt下训练,得到弱的假设ht:X->{-1,+1},

错误率:Εt=ΣWt(i)[ht(Xi)≠Yi]选择αt=1/2ln((1-Εt)/Εt

),更改权值:Wt+1(i)=Wt(i)*eαt/Zt，ifht(Xi)≠Yi

Wt+1(i)=Wt(i)*e-αt/Zt

ifht(Xi)=Yi

输出:H(X)=sign(∑αtht(X))XGBoost(1)XGBoost是一种对多个回归树进行集成的方法，构造出的多个回归树通过优化使得树群的预测值尽可能接近真实值且具有泛化能力，它是对Boosting族算法的改进，GrandientBoost改变的是本轮训练的样本标签，能够对单个弱分类器进行优化。回归树:回归树预测模型XGBoost(2)分割点寻找算法

输入：I，当前结点的样本集合，d，特征维数增益Gain取0fork=1tom

for每一个待分类的数据集计算其一阶、二阶导数(score表示当前分割值得分)endend输出：最大分割值得分Bagging和boosting区别联系(1)训练集：Bagging：随机选择，各轮训练集相互独立Boosting：各轮训练集并不独立，它的选择去前轮的学习结果有关预测函数：Bagging：没有权重；可以并行生成Boosting：有权重；只能顺序生成

Bagging和boosting区别联系(2)在许多应用中，准确率比运算速度更为重要，因为计算机的性价比提高很快。bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在有些数据集中，boosting会引起退化。--Overfit

集成学习中多样性个体的构造基于不同训练数据集的构造方式(bagging,boosting)基于不同特征集的构造方式(特征选择；随机投影；随机子空间）基于不同性质的学习机器或分类器的构造方式基于相同学习机器的不同学习参数的构造方式其他方法，如嵌入随机性，处理输出等。集成学习算法中的合并方法

投票法(Voting)；平均法(Averaging)；加权平均法(Weightedaveraging)；其他方法集成学习系统的构成非监督集成学习非监督集成(Unsupervisedensemble)也称聚类集成，被认为在许多方面都能超越单个聚类算法，如：鲁棒性，稳定性和一致性估计以及并行性和可量测性在图像分割，生物信息等领域已获得了很好的性能。相对于分类集成，对其研究还较少，在应用领域的研究有待进一步展开。个体聚类构造方面现有方法基于Bagging、Boosting的聚类集成方法。多目标数据聚类方法，用来处理具有多种不同结构的数据划分问题。……合并方法的研究由于聚类结果仅仅是一种符号，不同聚类结果间并无对应关系，例如两个聚类结果与虽然表现形式不同，实际上却是在逻辑上完全相同的聚类，这一现实使得多个聚类结果的合并比分类集成中的合并要困难得多。非