机器学习课件-0

集成学习（

）计算机科学与技术学院理论出发点和Boosting算法AdaBoost算法Bagging算法选择性集成总结课程内容No

Free

Lunch

TheoremSuppose

we

make

no

prior

assumptions

aboutthe

nature

of

the

classification

task.

Can

weexpect

any

classification

method

to

be

superioror

inferior

overall?No

Free

Lunch

Theorem:

Answer

to

abovequestion:

NOIf

goal

is

to

obtain

good

generalizationperformance,

there

is

no

context-independentor

usage-independent

reasons

to

favor

oneNo

Free

Lunch

TheoremIf

one

algorithm

seems

to

outperform

another

ina

particular

situation,

it

is

a

consequenceof

its

fitto

a

particular

pattern

recognition

problem.For

a

new

classification

problem,

what

mattersmost:

prior

information,

data

distribution,

size

oftraining

set,

cost

fn.No

Free

Lunch

TheoremIt

is

the

assumptions

about

the

learningalgorithm

that

are

importantEven

popular

algorithms

will

perform

poorlyon

some

problems,

where

the

learningalgorithm

and

data

distribution

do

not

matchwellIn

practice,

experience

with

a

broad

range

oftechniques

is

the

best

insurance

for

solvingarbitrary

new

classification

problemsBias

and

VarianceNo

“best

classifier”

in

generalNecessity

for

exploring

a

variety

of

methodsHow

to

evaluate

if

the

learning

algorithm

“matches”

theclassification

problemBias:

measures

the

quality

of

thematchHigh-bias

implies

poor

matchVariance:

measures

the

specificity

of

the

matchHigh-variance

implies

a

weak

matchBias

and

variance

arenot

independent

of

each

otherBias

and

VarianceGiven

true

function

F(x)Estimated

function

g(x;

D)

from

a

training

set

DDependence

of

function

g

on

training

set

D.Each

training

setgives

an

estimate

of

error

in

the

fitTaking

average

over

all

training

sets

of

size

n,

MSE

isAverage

error

that

g(x;D)makes

in

fitting

F(x)Difference

between

expectedDifference

between

observedvalue

and

expected

valueLow

bias:

o age,

we

willaccura y

estimate

F

from

DLow

variance:

Estimate

of

F

doesnot

change

much

with

different

DMotivation泛化能力是机器学习关注的一个根本问题泛化能力(generalization ability)表征了学习系统对新事件的适用性泛化能力越强越好提高泛化能力是机器学习的追求决策，便是部分的日常生活中，所谓的利用了这种想法。譬如选总统，每个人都以自己的考虑，投下自己的一票，但最后由多数人选出的总统，似乎应该好于由一个人指定的总统。28【集成学习：

】在机器学习中，直接建立一个高性能的分类器是很

的。但是，如果能找到一系列性能较差的分类器，并把它们集成起来的话，也许就能得到更好的分类器。集成学习，就是一种把输入送入多个学习器，再通过某种办法把学习的结果集成起来的办法。这每一个学习器，也就相应的被称为“弱学习器”。集成学习最早也叫做“Committee

VotingMethod”，也就是因为它和投票的过程相似。29【集成学习：】Classifier

ensembleΣαihi(x)hn(x)h2(x)h1(x)InputvectorClassifier

1Classifier

2……Classifier

NCombine

ClassifiersOutputx【集成学习：图示】问题问题集成学习集成学习(Ensemble

Learning)是一种机器学习范式，它使用多个学习器来解决同一个问题…

...…

...由于集成学习可以有效地提高学习系统的泛化能力，因此它成为国际机器学习界的研究热点“当前机器学习四大研究方向之首”[T.G.

Dietterich,AIMag97]Example:

Weather

ForecastReality1XXX2XXX3XXX4XX5XXCombine期望结果1(精度33.3%)2(精度33.3%)3(精度33.3%)集成(精度33.3%)投票期望结果1(精度33.3%)2(精度33.3%)3(精度33.3%)集成(精度0%)投票必须有差异 精度不能太低E

E

A

[A.

Krogh

&

J.

Vedelsby,NIPS94]学习器越精确、差异越大，集成越好【如何构建好的集成】【集成学习：如何构造？】办法就是改变训练集。通常的学习算法，根据训练集的不同，会给出不同的学习器。这时就可以通过改变训练集来构造不同的学习器。然后再把它们集成起来。【带权的采样:

】通过给训练数据赋以不同的权，实际上使得每个学习器关注训练集中的某一部分，这也符合

最初

投票的想法。直观上，每个学习器关注训练集中的某一部分，很多个训练集应该可以覆盖训练集中的大部分，只要巧妙的选择平均的权，就可以得到更好的学习效果。【用多个学习器覆盖样本空间】【分类设计的重采样技术】分类器设计的重采样技术也被称为“自适应的权值重置和组合（arcing,adaptive

reweightingand

combining）；这类方法的主要思想是利用同一个训练样本集合构造多个分类器，然后以某种方式将这些分类器组一个分类器；主要方法包括：bagging算法和boosting算法【集成学习：如何构造？】

一般选定

平均的方法来构造集成学习的最终学习器。但是里面的每一个Classifier

i怎样做呢？有一些研究，是针对每个学习器都不同构的情况，比如识别一个人，一个学习器考虑脸，另一个考虑步态，另一个考虑

。这种研究通常称为Information

Fusion，不在

今天

的范畴。

今天

的，是用同样的学习算法来构造不同的弱学习器的方法。3839【集成学习：如何构造？】办法就是改变训练集。通常的学习算法，根据训练集的不同，会给出不同的学习器。这时就可以通过改变训练集来构造不同的学习器。然后再把它们集成起来。40【随机采样】在原来的训练集上随机采样，可以得到新的训练集。41可以给训练集里的每个元素不采样时，同的权。权值可以通过上一次训练的结果来确定。【带权的采样】42通过给训练数据赋以不同的权，实际上使得每个学习器关注训练集中的某一部分，这也符合最初投票的想法。直观上，每个学习器关注训练集中的某一部分，很多个训练集应该可以覆盖训练集中的大部分，只要巧妙的选择平均的权，就可以得到更好的学习效果。【带权的采样:】43【集成学习：评述】集成学习实际上代表了一种与传统不同的思维理念。传统的机器学

般都自认为是单模型的，对于模型的分析总是在整体上完成。Rosenblatt：PerceptronRumelhart:

BPVapnik:

SVM但是，所有这些模型其实都可以看作是一种平均的多模型。44【集成学习：评述】所以，当然应该考虑研究一般的多模型。实际上，从90年始，对集成学习的研究取得了一系列突破进展。在算法上，集成学习的典型代表AdaBoost算法，已经成为与SVM并立的方法。而且，集成学习比SVM更为一般，可能可以有更广阔的前景。45【泛化能力】泛化：generalization泛化能力越强，处理新数据的能力越好泛化能力是机器学习关注的基本问题之一提高泛化能力是 的追求46集成学习（Ensemble

Learning）是一种机器学习范式，它使用多个（通常是同质的）学习器来解决同一个问题问题…...…...问题集成学习中使用的多个学习器称为

学习器当 学习器均为决策树时，称为“决策树集成”当 学习器均为神经网络时，称为“神经网络集成”……

……【集成学习】47由于集成学习技术可以有效地提高学习系统的泛化能力，因此它成为国际机器学习界的研究热点，并被国际T.G.

Dietterich

称为当前机器学习四大研究方向之首[T.G.Dietterich,

AIMag97]问题：对20维超立方体空间中的区域分类左图中纵轴为错误率从上到下的四条线分别表示：平均神经网络错误率最好神经网络错误率两种神经网络集成的错误率令人惊奇的是，集成的错误率比最好的 还低[L.K.

Hansen

&P.

Salamon,

TPAMI90]【集成学习的重要性】48只要能用到机器学习的地方，就能用到集成学习【集成学习的应用】集成学习技术已经在行星探测、 波分析、Web信息过滤、生物特征识别、计算机辅助医疗等众多领域得到了广泛的应用49的在意味着：时需要更大的计算开销，因为要计算的更大的

开销，因为有

的

需要保存的增加将使得

间的差异越来越难以获得【

越多越好吗？】既然多个

的集成比单个

更好，那么是不是 越多越好?50【分类设计的重采样技术】分类器设计的重采样技术也被称为“自适应的权值重置和组合（arcing,adaptive

reweightingand

combining）；这类方法的主要思想是利用同一个训练样本集合构造多个分类器，然后以某种方式将这些分类器组一个分类器；主要方法包括：bagging算法和boosting算法理论出发点和Boosting算法AdaBoost算法bagging算法选择性集成总结课程内容研究背景1988年,Kearns等在研究PAC学习模型时提出了一个有趣的问题:“弱可学习是否等价

可学习?”即Boosting问题。如果这一问题有肯定的回答,意味着只要找到比随机猜测略好的弱学习算法,以将其提升为强学习算法,而不必直接去寻找通常情况下很难获得的强学习算法,这对学习算法的设计有着重要的意义。可以通过一弱学习定理：只要找到比随机猜测略好的学习算法，那么定的方式，构造出强学习算法。意义：不用直接寻找通常情况下很难获得的强学习算法，迂回

，通过找弱学习算法来集成。Boosting背景来源于:PAC-Learning

ModelValiant 1984

-11提出问题:强学习算法:准确率很高的学习算法弱学习算法:准确率不高,仅比随机猜测略好是否可以将弱学习算法提升为强学习算法Boosting背景最初的boosting算法Schapire

1989AdaBoost算法Freund

and

Schapire

1995Boosting—concepts(3)Boosting弱学习机（weak

learner):对一定分布的训练样本给出假设（仅仅强于随机猜测）根据有云猜测可能会下雨强学习机（strong

learner):根据得到的弱学习机和相应的权重给出假设（最大程度上符合实际情况：almost

perfect

expert)根据CNN,ABC,CBS以往的 表现及实际天气情况作出综合准确的天气弱学习机强学习机Boosting流程(loop1)强学习机弱学习机原始训练集后的训练集后的假设X>1?1:-1弱假设Boosting流程(loop2)强学习机弱学习机原始训练集后的训练集后的假设Y>3?1:-1弱假设2020/11/16高级人工智能58Boosting流程(loop3)强学习机弱学习机原始训练集后的训练集后的假设Z>7?1:-1弱假设Boosting过程:在一定的权重条件下训练数据，得出分类法Ct根据Ct的错误率调整权重Set

ofweightedinstancesClassifier

Cttrain

classifieradjust

weights流程描述Step1:原始训练集输入，带有原始分布Step2:给出训练集中各样本的权重Step3:

将改变分布后的训练集输入已知的弱学习机，弱学习机对每个样本给出假设Step4:

对此次的弱学习机给出权重Step5:

转到Step2,

直到循环到达一定次数或者某度量标准符合要求Step6:

将弱学习机按其相应的权重 组合形成强学习机思想样本的权重没有先验知识的情况下，初始的分布应为等概分布，也就是训练集如果有N个样本，每个样本的分布概率为1/N每次循环一后提高错误样本的分布概率，分错样本在训练集中所占权重增大，使得下一次循环的弱学习机能够集中力量对这些错误样本进行判断。弱学习机的权重准确率越高的弱学习机权重越高循环控制：损失函数达到最小在强学习机的组合中增加一个的弱学习机，使准确率提高，损失函数值减小。简单问题演示（Boosting训练过程）++--+--

+-++-++--++--++--loop1Weak

learner1(y=0.5)loop2

Weak

learner2(x=0.7)loop3Weak

learner3(y=0.4)loop4

Weak

learner4(x=0.6)training

set等概分布strong

learnerw1*(y>0.5?1:-1)

+

w2*(x<0.7?1:-1)

+

w3*(y<0.4?1:-1)

+

w4*(x>0.6?1:-1)算法—问题描述训练集{(x1,y1),(x2,y2),…,(xN,yN)}xi

Rm,

yi

{-1,+1}Dt为第t次循环时的训练样本分布（每个样本在训练集中所占的概率，Dt总和应该为1）ht:X{-1,+1}

为第t次循环时的Weak

learner，对每个样本给出相应的假设，应该满足强于随机猜测：为t次循环得到的Strong

learner12[

y

h

(x)]

Pt(

x,

y)Dtwt为ht的权重t•i1Ht

(i

)

sign

(

wi

ht

(i

))算法—样本权重思想：提高分错样本的权重•反映了strong

learner对样本的假设是否正确采用什么样的函数形式？yi

Ht(i

)i

t

iright

0

wrongy

H

(

)

0exp

yi

Ht(i

)算法—弱学习机权重思想：错误率越低，该学习机的权重应该越大为学习机的错误概率采用什么样的函数形式？和指数函数遥相呼应：tt

P

[

y

h

(x)](

x,

y)D•t

t

1

t

wt

ln12Boosting算法的发展历史Boosting算法(提升算法)是一种把若干个弱分类器整合为一个强分类器的方法。Boosting算法存在的几个问题：如何调整训练集，使得在训练集上训练的弱分类器得以进行。如何将训练得到的各个弱分类器

形成强分类器。需要预先知道弱学习算法学习正确率的下限。即弱分类器的误差。理论出发点和Boosting算法AdaBoost算法Bagging算法随机森林选择性集成总结课程内容AdaBoost算法的引入AdaBoost算法简介AdaBoost算法流程图AdaBoost实例：二元分类缺点和不足总结汇报提纲针对以上几个问题，AdaBoost算法进行了调整：使用

后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上。将弱分类器 ，使用

的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。不需预估弱学习器的正确下限。AdaBoost算法的引入AdaBoost(AdaptiveBoost)算法是一种把若干个弱分类器整合为一个强分类器的自适应提升算法。自适应体现一轮分类器分错的样本会被增强，用来训练下一个分类器AdaBoost算法简介AdaBoost算法流程图循环迭代多次：寻找当前分布下的最优弱分类器计算弱分类器带权分类误差更新样本分布聚合多次训练的弱分类器

t=PrxDt,yI[ht(x)

y];Input:数据集D={(x1,y1),(x2,y2),……,xm,ym)};循环次数：T；基学习算法；for

t

1，……，T

:ht=

(D,Dt);//从D中利用分布Dt训练学习器ht2

t=

Ln(

tif

t>0.5,

then

break;1

1

t

);exp(

t)exp(

t)Dt+1(i)=Dt

(i)

//计算学习器ht的带权分类误差//如果此学习器误差大于0.5，算法失败//计算此学习器的权重endTmif

ht(xi)=yi

if

ht(xi)

yi//更新样本分布Zt

Dt

1(i);

Dt

1(i)

Dt

1(i)

/

Zt；i1//归一化样本分布Output：H(x)=sign（t

ht

(x)）t

1AdaBoost的一种伪代码描述)2t=

Ln(

t1

1

t“弱分类器权重-带权分类误差”函数图像误差越低，分类器权重越高误差大于0.5，权重为负，实际已退出关键步骤：计算学习器权重关键步骤：更新样本分布Dt

1(i)

Dt

(i)

exp(t

)

ht得到新的弱分类器后，需要对样本分布进行更新：分类错误，提高该样本的权值。分类正确，降低该样本的权值。mZt

Dt

1(i)i1Dt

1(i)

t（归一化）AdaBoost实例：二元分类序号12345678910X0123456789Y111-1-1-1111-1注：这里假设Xi为二元分类，即对于X->Y,有Y={-1,+1}Q:已知如下学习样本及其对应的分类，构造分类器，对样本X进行准确分类(也就是要求一个分类函数F(x)，其对样本X能进行准确的分类)X0123456789Y111-1-1-1111-1D10.10.10.10.10.10.10.10.10.10.1这里

要训练得到一个弱分类器。严格来讲，应在给定的权重样本和分类方法上穷举分类器，选择带权误差最小的弱分类器作为本轮训练得到的分类器。选择的分类方法为：y=1

(X<分界值)y=-1(X>分界值)1

x2.51

x2.5G1(x)

分界值0.51.52.53.54.55.56.57.58.5带权误差0.50.40.30.40.50.60.50.40.3不同值作为分界时分类器带权误差在此分类方法下，选择2.5或8.5作为分界值，得到的带权分类误差最小。这里选择2.5。故本轮

训练得到的分类器为：X0123456789Y111-1-1-1111-1D10.10.10.10.10.10.10.10.10.10.1

11

x2.51

x2.5G1(x)

1=0.5ln(1

1

)=0.4236分类函数取：有：

1=0.1+0.1+0.1=0.3更新Di;F1(x)=1*G1(x)=0.4236*G1(x)Q:为什么G1(x)要取这种形式呢？分错了x7，x8,x9X0123456789Y111-1-1-1111-1D20.0710.0710.0710.0710.0710.0710.1660.1660.1660.0714444447774选择的分类方法为：y=1

(X<分界值)y=-1(X>分界值)1

x8.51

x8.5G2(x)

分界值0.51.22.53.54.55.56.57.58.5带权误差0.64290.57150.50010.57150.64290.71430.54760.38090.2142不同值作为分界时分类器带权误差在当前选取的分类方法下，选择8.5作为分界值，得到的带权分类误差最小。故本轮

训练得到的分类器为：

21

x8.51

x8.5G2(x)

2

=0.5ln(1

2

)=0.6499;分类函数取：有：

2=0.0714+0.0714+0.0714=0.2142;更新Di;F2(x)=1*G1(x)+

2*G2(x)=0.4236*G1(x)+0.6499*G2(x)X0123456789YD210.071410.071410.0714-10.0714-10.0714-10.071410.166710.166710.1667-10.0714Q:为什么G2(x)要取这种形式呢？分错了x4、x5、x6X0123456789Y111-1-1-1111-1D30.0450.0450.0450.1660.1660.1660.1060.1060.1060.0454447771114选择的分类方法为：y=-1(X<分界值)y=1(X>分界值)-1

x5.5+1

x5.5G3(x)

分界值0.51.52.53.54.55.56.57.58.5带权误差0.59090.63630.68170.51500.34830.18160.28770.34840.4545不同值作为分界时分类器带权误差在当前选取的分类方法下，选择5.5作为分界值，得到的带权分类误差最小。故本轮

训练得到的分类器为：)=0.7528;

3=0.5ln(

31

x5.51

x5.5G3(x)

1

3分类函数取：有：

3=0.0454+0.0454+0.0454+0.0454=0.1816;更新Di;F3(x)=1*G1(x)+

2*G2(x)+

3*G3(

x)

0.4236*G1(x)+0.6499*G2(x)

0.7528

*

G

3(

x)X0123456789YD310.045410.045410.0454-10.1667-10.1667-10.166710.106110.106110.1061-10.0454Q:为什么G3(x)要取这种形式呢？通过弱学习算法生产的，具体到本例：通过穷举算法来获得分错了x1,x2,x3,x10H(x)=sig=sign[1*G1(x)+

2*G2(x

sign[0.4236*G1(x)+0.6499*G2(x)

0.7528

*1

x2.51

x2.5G1(x)

1

x8.51

x8.5G2(x)

1

x5.51

x5.5G3(x)

X0123456789Y111-1-1-1111-1F3(X)0.32070.32070.3207-0.5265-0.5265-0.52650.97910.97910.9791-0.3207H(x)111-1-1-1111-1AdaBoost算法得到的分类器分类效果优点和不足优点：精度很高只是框架，弱学习算法(弱分类器的构造生成方法)可以多样不会产生过渡拟合缺点：难以估计训练次数效果与弱分类器选择有关样本多时效率较低离散AdaBoost-AdaBoost.M1AdaBoost.M1

和AdaBoost.M2

是用来解决多分类单

问题AdaBoost.M1算法(x1,

y1),(x2

,

y2

),...,

(xn

,

yn

)Step

1:训练集Step

2:初始化权值1,iiw2n

1for

y

0,1,For

t

=

1,

…

,

T1.

归一化权值,2.

对于第j个特征,在给定权值条件下训练若分类器hj

，若分类器的分类错误率为：3.

更新权值:End最终的强分类器：t

,it

,

jwt

,iwnj

1w

j

wi

|

hj

(xi

)

yi

|i如果t

1/2,设T

t

1,退出循环it

,i

tt

,i

twt

,i1et

1,iw

w

w

,

如果样本被正确分类其他tt

t1

th(x)=arg

maxyYlogt

1...TFloatboost

算法向前增加一个弱分类器之后，就需要向后回馈r。r的取值取决于当前分类性能的稳定性。这种弱分类器选择的方法相对于前向搜索来说具有更大的灵活性，因此，增加弱分类器组合的多样性，相比AdaBoost中的单调搜索有更优的解集合。mT

(x1,

y1

),

(x2

,

y2

),

...

,

(xm

,

ym

)J

(Hm

)为此特征集合的目标函数值，J

min是目前m个特征构成的集合中目标函数的最小值。图像正样本=1负样本=-1Step

1:训练集Step

2:初始化权值t

mmw

(i)

1

,

i

1,...m;

J

min

=max-value(t=1,...,Max),

M=01.

每个弱分类器h,在权值下进行训练，得到 函数ht.2.

计算误判率，选取参数at：3.

更新权值:4.最终的函数：i

j

wi

|

hj

(xi

)

yi

|选择有最小错误率t的若分类器ht。MtZi

1Wt

(xi

)

exp(t

yi

ht

(xi

))Wt

1

(xi

)

,Zt是使Wt

1

(xi

)的归一化因子。Step

3:弱分类器训练For

t

=1,

…

,

TM

M

mhHm设h'arg

min,为

最小特征集合，若J(H)(为漏检率与虚警率的和)<Jmin

,则删掉此特征，当J(HM

)低于值或循环次数大于预定值M时，停止循环。MH

(x)

sign(

hm

(x))m1总结AdaBoost算法是一种自适应性的提升类算法。通过前一个分类器的分类结果对样本分布进行更新，用来训练下一个弱分类器，最后将弱分类器组合得到强的分类器。AdaBoost算法能得到分类精度高的强分类器。AdaBoost算法只是一个框架，容易拓展应用。理论出发点和Boosting算法AdaBoost算法Bagging算法随机森林选择性集成总结课程内容03

Bagging算法通过自助采样始终数据集D中约有36.8%的样本未出现在采样数据集D’中。自助法在数据集较小、难以有效划分训练/测试集时很有用；此外，自助法能从初始数据集中产生多个不同的训练集，这对集成学习等方法有很大好处。Bagging是并行式集成学习最著名的代表。它直接基于自助采样法。自助采样法：给定包含m个样本的数据集D，对它采样产生数据集D’，每次随机从

D中挑选一个样本，将其拷贝放入D’，然后再将该样本放回数据集D中，使得该样本在下次采样时仍有可能被采到；这个过程重复执行m次后，就得到了包含m个样本的数据集D’，这就是自助采样的结果。显然，D中有一部分样本会在D’中多次出现，而另一部分样本不出现样本在m次采样中始终不被采到的概率是(1

1

)m

，取极限得到mm

emlim(1

1

)m

1

0.368bagging算法Bagging算法的主要思想：给定训练集 和弱学习算法，对该学习算法进行T次调用，每次调用时只使用训练集S中的某个子集作为当前训练集，每一个训练例在某轮训练集中可以多次或根本不出现。经过T次调用后，可得到T个不同的分类器啊，当对于一个测试实例工进行分类时，分别调用这T个分类器，得到T个分类结果。最后对分类问题把这T个分类结果中出现次数多的类赋予测试实例x。2S

((x1,

y1),(x203

Bagging算法Bagging算法的主要思想：通过自助采样法得到含有m个样本的采样集；进行T轮，可以采样出T个含m个训练样本的训练集；基于每个采样训练集训练出一个基学习器hi(x)；对T个基学习器进行结合得到最终分类器H(x)；对于 输出进行结合时，采用简单投票法，对回归任务使用简单平均法。图1

Bagging算法流程图Bagging算法(x1,

y1),(x2

,y2

),...,(xn

,yn

)Step

1:训练Step

2:初始化权值For

t

=1,

…

,

TS’为从给定训练集S中，随机抽样（有放回）.在S’

上训练弱学习器，得到第t

轮的

函数ht

.t

=

t

+

1

.End最终输出：

对未知样本X分类时，每个模型ht得到一个分类器，得票最高的未知样本x

的分类输入：训练集；3：若t<T，回到1，并令t=t+1，否则转4；函4：将各 集合生成最终数：D={(x1,

y1),(x2

,

y2

),,(xm

,

ym

)}基学习算法h(x)；训练轮数T输出：集成

模型过程：1：从初始的训练集中采用boostrap方法抽取出m个训练例组成子集S’；2：在S’上训练基学习器

h1,h2

,

,hT

，得到第t轮的 函数ht(x)；函数H

(x)

signhi

(x)03

Bagging算法图2

Bagging算法描述03

Bagging算法Bagging与Boosting的区别：Bagging的训练集的选择是随机的，各训练集之间相互独立；而Boosting的训练集的选择不独立，各轮训练集的选择与前面各轮的学习有关；Bagging的各个 函数没 重，而Boosting各训练集

重；Bagging各个函数可以并行生成，Boosting只能顺序生成。（对于像神经网络这种比较耗时的学习方法，

Bagging可通过并行训练节省大量的时间）Bagging

和AdaBoost

区别Bagging的训练集是随机的，各训练集是独的，而

Boosting训练集的选择不是独立的，每一次选择的训练集都依赖于上一次学习的结果。Bagging的每个

函数(即弱假设)没重，而Boosting根据每一次训练的训练误差得到该次函数的权重。Bagging的各个

函数可以并行生成，而Boosting的只能顺序生成。对于像神经网络这样极为耗时的学习方法，Bagging可通过并行训练节省大量时间开销。理论出发点和Boosting算法AdaBoost算法Bagging算法随机森林选择性集成总结课程内容04

随机森林--Random

Forest随机森林（RandomForest，简称RF）是Bagging的一个扩展变体。随机森林由许多的决策树组成，因为这些决策树的形成采用了随机的方法，因此也叫做随机决策树。随机森林中的树之间是没有关联的。当测试数据进入随机森林时，其实就是让每一颗决策树进行分类，最后取所有决策树中分类结果最多的那类为最终的结果。RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入随机属性选择。传统决策树在选择划分属性时是在当前结点的属性集合（假定有d个属性）中选择一个最优属性；在RF中，对决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分；这里的参数k控制了随机性的引入程度：若令k=d，则基决策树的构建与传统决策树相同；若令k=1，则是随机选择一个属性用于划分；一般情况下， 值k=log2d。04

随机森林--Random

Forest决策树复习：决策树实际上是将空间用超平面进行划分的

法，每次分割的时候，都将当前的空间一分为二，比如说下面的决策树（其属性的值都是连续的实数）：图3 决策树图4 空间划分后04

随机森林--Random

Forest随机森林的构造过程：假N个样本，则有放回的随机选择N个样本（每次随机选择一个样本，然后放回继续选择），用选择好的N个样本来训练决策树。当每个样本有d个属性时，在决策树的每个节点需要时，随机从这k个属性中选取出k个属性，满足条件k<<d。然后从这k个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的属性。决策树形成过程中每个节点都要按照步骤2来，一直到不能够再 为止。注意整个决策树形成过程中没有进行剪枝。按照步骤1~3建立大量的决策树，这样就构成了随机森林。随机森林的随机性体现在：每颗数的训练样本是随机的；树中每个节点的分类属性是随机选择的。04

随机森林--Random

Forest随机森林的优点：在数据集上表现良好，两个随机性的引入，使得随机森林不容易陷入过拟合，具有很好的抗噪声能力。它能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。能够并行处理，训练速度快。随机森林的缺点：算法倾向于观测值较多的类别随机森林中水平较多的分类属性的自变量（如土地利用类型>20个类别）比水平较少的分类属性的自变量（气候区类型<10个类别）对模型的影响大。理论出发点和Boosting算法AdaBoost算法Bagging算法随机森林选择性集成总结课程内容的在意味着：时需要更大的计算开销，因为要计算的选择性集成既然多个学习器的集成比单个学习器更好，那么是不是学习器越多越好?更大的

开销，因为有

的 需要保存E

E

A [A.Krogh

&

J.

Vedelsby,

NIPS94]的增加将使得 间的差异越来越难以获得104Many

Could

be

Better

Th

l：在有一组

学习器可用时，从中选择一部分进行集成，可能比用所有学习器进行集成更好[Z.-H.

Zhou

et

al.,

AIJ02]【选择性集成】选择性集成提出了选择性集成(Selective

Ensemble)证明了

“Many

Could

be

Better

Th l”

Theorem在有一组 学习器可用时，从中选择一部分进行集成，可能比用所