機器學習課件-0

集成學習（

）計算機科學與技術學院理論出發(fā)點和Boosting算法AdaBoost算法Bagging算法選擇性集成總結課程內(nèi)容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)表征了學習系統(tǒng)對新事件的適用性泛化能力越強越好提高泛化能力是機器學習的追求決策，便是部分的日常生活中，所謂的利用了這種想法。譬如選總統(tǒng)，每個人都以自己的考慮，投下自己的一票，但最后由多數(shù)人選出的總統(tǒng)，似乎應該好于由一個人指定的總統(tǒng)。28【集成學習：

】在機器學習中，直接建立一個高性能的分類器是很

的。但是，如果能找到一系列性能較差的分類器，并把它們集成起來的話，也許就能得到更好的分類器。集成學習，就是一種把輸入送入多個學習器，再通過某種辦法把學習的結果集成起來的辦法。這每一個學習器，也就相應的被稱為“弱學習器”。集成學習最早也叫做“Committee

VotingMethod”，也就是因為它和投票的過程相似。29【集成學習：】Classifier

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

1Classifier

2……Classifier

NCombine

ClassifiersOutputx【集成學習：圖示】問題問題集成學習集成學習(Ensemble

Learning)是一種機器學習范式，它使用多個學習器來解決同一個問題…

...…

...由于集成學習可以有效地提高學習系統(tǒng)的泛化能力，因此它成為國際機器學習界的研究熱點“當前機器學習四大研究方向之首”[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]學習器越精確、差異越大，集成越好【如何構建好的集成】【集成學習：如何構造？】辦法就是改變訓練集。通常的學習算法，根據(jù)訓練集的不同，會給出不同的學習器。這時就可以通過改變訓練集來構造不同的學習器。然后再把它們集成起來?！編嗟牟蓸?

】通過給訓練數(shù)據(jù)賦以不同的權，實際上使得每個學習器關注訓練集中的某一部分，這也符合

最初

投票的想法。直觀上，每個學習器關注訓練集中的某一部分，很多個訓練集應該可以覆蓋訓練集中的大部分，只要巧妙的選擇平均的權，就可以得到更好的學習效果。【用多個學習器覆蓋樣本空間】【分類設計的重采樣技術】分類器設計的重采樣技術也被稱為“自適應的權值重置和組合（arcing,adaptive

reweightingand

combining）；這類方法的主要思想是利用同一個訓練樣本集合構造多個分類器，然后以某種方式將這些分類器組一個分類器；主要方法包括：bagging算法和boosting算法【集成學習：如何構造？】

一般選定

平均的方法來構造集成學習的最終學習器。但是里面的每一個Classifier

i怎樣做呢？有一些研究，是針對每個學習器都不同構的情況，比如識別一個人，一個學習器考慮臉，另一個考慮步態(tài)，另一個考慮

。這種研究通常稱為Information

Fusion，不在

今天

的范疇。

今天

的，是用同樣的學習算法來構造不同的弱學習器的方法。3839【集成學習：如何構造？】辦法就是改變訓練集。通常的學習算法，根據(jù)訓練集的不同，會給出不同的學習器。這時就可以通過改變訓練集來構造不同的學習器。然后再把它們集成起來。40【隨機采樣】在原來的訓練集上隨機采樣，可以得到新的訓練集。41可以給訓練集里的每個元素不采樣時，同的權。權值可以通過上一次訓練的結果來確定?！編嗟牟蓸印?2通過給訓練數(shù)據(jù)賦以不同的權，實際上使得每個學習器關注訓練集中的某一部分，這也符合最初投票的想法。直觀上，每個學習器關注訓練集中的某一部分，很多個訓練集應該可以覆蓋訓練集中的大部分，只要巧妙的選擇平均的權，就可以得到更好的學習效果。【帶權的采樣:】43【集成學習：評述】集成學習實際上代表了一種與傳統(tǒng)不同的思維理念。傳統(tǒng)的機器學

般都自認為是單模型的，對于模型的分析總是在整體上完成。Rosenblatt：PerceptronRumelhart:

BPVapnik:

SVM但是，所有這些模型其實都可以看作是一種平均的多模型。44【集成學習：評述】所以，當然應該考慮研究一般的多模型。實際上，從90年始，對集成學習的研究取得了一系列突破進展。在算法上，集成學習的典型代表AdaBoost算法，已經(jīng)成為與SVM并立的方法。而且，集成學習比SVM更為一般，可能可以有更廣闊的前景。45【泛化能力】泛化：generalization泛化能力越強，處理新數(shù)據(jù)的能力越好泛化能力是機器學習關注的基本問題之一提高泛化能力是 的追求46集成學習（Ensemble

Learning）是一種機器學習范式，它使用多個（通常是同質(zhì)的）學習器來解決同一個問題問題…...…...問題集成學習中使用的多個學習器稱為

學習器當 學習器均為決策樹時，稱為“決策樹集成”當 學習器均為神經(jīng)網(wǎng)絡時，稱為“神經(jīng)網(wǎng)絡集成”……

……【集成學習】47由于集成學習技術可以有效地提高學習系統(tǒng)的泛化能力，因此它成為國際機器學習界的研究熱點，并被國際T.G.

Dietterich

稱為當前機器學習四大研究方向之首[T.G.Dietterich,

AIMag97]問題：對20維超立方體空間中的區(qū)域分類左圖中縱軸為錯誤率從上到下的四條線分別表示：平均神經(jīng)網(wǎng)絡錯誤率最好神經(jīng)網(wǎng)絡錯誤率兩種神經(jīng)網(wǎng)絡集成的錯誤率令人驚奇的是，集成的錯誤率比最好的 還低[L.K.

Hansen

&P.

Salamon,

TPAMI90]【集成學習的重要性】48只要能用到機器學習的地方，就能用到集成學習【集成學習的應用】集成學習技術已經(jīng)在行星探測、 波分析、Web信息過濾、生物特征識別、計算機輔助醫(yī)療等眾多領域得到了廣泛的應用49的在意味著：時需要更大的計算開銷，因為要計算的更大的

開銷，因為有

的

需要保存的增加將使得

間的差異越來越難以獲得【

越多越好嗎？】既然多個

的集成比單個

更好，那么是不是 越多越好?50【分類設計的重采樣技術】分類器設計的重采樣技術也被稱為“自適應的權值重置和組合（arcing,adaptive

reweightingand

combining）；這類方法的主要思想是利用同一個訓練樣本集合構造多個分類器，然后以某種方式將這些分類器組一個分類器；主要方法包括：bagging算法和boosting算法理論出發(fā)點和Boosting算法AdaBoost算法bagging算法選擇性集成總結課程內(nèi)容研究背景1988年,Kearns等在研究PAC學習模型時提出了一個有趣的問題:“弱可學習是否等價

可學習?”即Boosting問題。如果這一問題有肯定的回答,意味著只要找到比隨機猜測略好的弱學習算法,以將其提升為強學習算法,而不必直接去尋找通常情況下很難獲得的強學習算法,這對學習算法的設計有著重要的意義?？梢酝ㄟ^一弱學習定理：只要找到比隨機猜測略好的學習算法，那么定的方式，構造出強學習算法。意義：不用直接尋找通常情況下很難獲得的強學習算法，迂回

，通過找弱學習算法來集成。Boosting背景來源于:PAC-Learning

ModelValiant 1984

-11提出問題:強學習算法:準確率很高的學習算法弱學習算法:準確率不高,僅比隨機猜測略好是否可以將弱學習算法提升為強學習算法Boosting背景最初的boosting算法Schapire

1989AdaBoost算法Freund

and

Schapire

1995Boosting—concepts(3)Boosting弱學習機（weak

learner):對一定分布的訓練樣本給出假設（僅僅強于隨機猜測）根據(jù)有云猜測可能會下雨強學習機（strong

learner):根據(jù)得到的弱學習機和相應的權重給出假設（最大程度上符合實際情況：almost

perfect

expert)根據(jù)CNN,ABC,CBS以往的 表現(xiàn)及實際天氣情況作出綜合準確的天氣弱學習機強學習機Boosting流程(loop1)強學習機弱學習機原始訓練集后的訓練集后的假設X>1?1:-1弱假設Boosting流程(loop2)強學習機弱學習機原始訓練集后的訓練集后的假設Y>3?1:-1弱假設2020/11/16高級人工智能58Boosting流程(loop3)強學習機弱學習機原始訓練集后的訓練集后的假設Z>7?1:-1弱假設Boosting過程:在一定的權重條件下訓練數(shù)據(jù)，得出分類法Ct根據(jù)Ct的錯誤率調(diào)整權重Set

ofweightedinstancesClassifier

Cttrain

classifieradjust

weights流程描述Step1:原始訓練集輸入，帶有原始分布Step2:給出訓練集中各樣本的權重Step3:

將改變分布后的訓練集輸入已知的弱學習機，弱學習機對每個樣本給出假設Step4:

對此次的弱學習機給出權重Step5:

轉(zhuǎn)到Step2,

直到循環(huán)到達一定次數(shù)或者某度量標準符合要求Step6:

將弱學習機按其相應的權重 組合形成強學習機思想樣本的權重沒有先驗知識的情況下，初始的分布應為等概分布，也就是訓練集如果有N個樣本，每個樣本的分布概率為1/N每次循環(huán)一后提高錯誤樣本的分布概率，分錯樣本在訓練集中所占權重增大，使得下一次循環(huán)的弱學習機能夠集中力量對這些錯誤樣本進行判斷。弱學習機的權重準確率越高的弱學習機權重越高循環(huán)控制：損失函數(shù)達到最小在強學習機的組合中增加一個的弱學習機，使準確率提高，損失函數(shù)值減小。簡單問題演示（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次循環(huán)時的訓練樣本分布（每個樣本在訓練集中所占的概率，Dt總和應該為1）ht:X{-1,+1}

為第t次循環(huán)時的Weak

learner，對每個樣本給出相應的假設，應該滿足強于隨機猜測：為t次循環(huán)得到的Strong

learner12[

y

h

(x)]

Pt(

x,

y)Dtwt為ht的權重t?i1Ht

(i

)

sign

(

wi

ht

(i

))算法—樣本權重思想：提高分錯樣本的權重?反映了strong

learner對樣本的假設是否正確采用什么樣的函數(shù)形式？yi

Ht(i

)i

t

iright

0

wrongy

H

(

)

0exp

yi

Ht(i

)算法—弱學習機權重思想：錯誤率越低，該學習機的權重應該越大為學習機的錯誤概率采用什么樣的函數(shù)形式？和指數(shù)函數(shù)遙相呼應：tt

P

[

y

h

(x)](

x,

y)D?t

t

1

t

wt

ln12Boosting算法的發(fā)展歷史Boosting算法(提升算法)是一種把若干個弱分類器整合為一個強分類器的方法。Boosting算法存在的幾個問題：如何調(diào)整訓練集，使得在訓練集上訓練的弱分類器得以進行。如何將訓練得到的各個弱分類器

形成強分類器。需要預先知道弱學習算法學習正確率的下限。即弱分類器的誤差。理論出發(fā)點和Boosting算法AdaBoost算法Bagging算法隨機森林選擇性集成總結課程內(nèi)容AdaBoost算法的引入AdaBoost算法簡介AdaBoost算法流程圖AdaBoost實例：二元分類缺點和不足總結匯報提綱針對以上幾個問題，AdaBoost算法進行了調(diào)整：使用

后選取的訓練數(shù)據(jù)代替隨機選取的訓練樣本，這樣將訓練的焦點集中在比較難分的訓練數(shù)據(jù)樣本上。將弱分類器 ，使用

的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權重，而分類效果差的分類器具有較小的權重。不需預估弱學習器的正確下限。AdaBoost算法的引入AdaBoost(AdaptiveBoost)算法是一種把若干個弱分類器整合為一個強分類器的自適應提升算法。自適應體現(xiàn)一輪分類器分錯的樣本會被增強，用來訓練下一個分類器AdaBoost算法簡介AdaBoost算法流程圖循環(huán)迭代多次：尋找當前分布下的最優(yōu)弱分類器計算弱分類器帶權分類誤差更新樣本分布聚合多次訓練的弱分類器

t=PrxDt,yI[ht(x)

y];Input:數(shù)據(jù)集D={(x1,y1),(x2,y2),……,xm,ym)};循環(huán)次數(shù)：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“弱分類器權重-帶權分類誤差”函數(shù)圖像誤差越低，分類器權重越高誤差大于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進行準確分類(也就是要求一個分類函數(shù)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分類函數(shù)?。河校?/p>

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;分類函數(shù)?。河校?/p>

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分類函數(shù)取：有：

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)要取這種形式呢？通過弱學習算法生產(chǎn)的，具體到本例：通過窮舉算法來獲得分錯了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算法得到的分類器分類效果優(yōu)點和不足優(yōu)點：精度很高只是框架，弱學習算法(弱分類器的構造生成方法)可以多樣不會產(chǎn)生過渡擬合缺點：難以估計訓練次數(shù)效果與弱分類器選擇有關樣本多時效率較低離散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,退出循環(huán)it

,i

tt

,i

twt

,i1et

1,iw

w

w

,

如果樣本被正確分類其他tt

t1

th(x)=arg

maxyYlogt

1...TFloatboost

算法向前增加一個弱分類器之后，就需要向后回饋r。r的取值取決于當前分類性能的穩(wěn)定性。這種弱分類器選擇的方法相對于前向搜索來說具有更大的靈活性，因此，增加弱分類器組合的多樣性，相比AdaBoost中的單調(diào)搜索有更優(yōu)的解集合。mT

(x1,

y1

),

(x2

,

y2

),

...

,

(xm

,

ym

)J

(Hm

)為此特征集合的目標函數(shù)值，J

min是目前m個特征構成的集合中目標函數(shù)的最小值。圖像正樣本=1負樣本=-1Step

1:訓練集Step

2:初始化權值t

mmw

(i)

1

,

i

1,...m;

J

min

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

M=01.

每個弱分類器h,在權值下進行訓練，得到 函數(shù)ht.2.

計算誤判率，選取參數(shù)at：3.

更新權值:4.最終的函數(shù)：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

)低于值或循環(huán)次數(shù)大于預定值M時，停止循環(huán)。MH

(x)

sign(

hm

(x))m1總結AdaBoost算法是一種自適應性的提升類算法。通過前一個分類器的分類結果對樣本分布進行更新，用來訓練下一個弱分類器，最后將弱分類器組合得到強的分類器。AdaBoost算法能得到分類精度高的強分類器。AdaBoost算法只是一個框架，容易拓展應用。理論出發(fā)點和Boosting算法AdaBoost算法Bagging算法隨機森林選擇性集成總結課程內(nèi)容03

Bagging算法通過自助采樣始終數(shù)據(jù)集D中約有36.8%的樣本未出現(xiàn)在采樣數(shù)據(jù)集D’中。自助法在數(shù)據(jù)集較小、難以有效劃分訓練/測試集時很有用；此外，自助法能從初始數(shù)據(jù)集中產(chǎn)生多個不同的訓練集，這對集成學習等方法有很大好處。Bagging是并行式集成學習最著名的代表。它直接基于自助采樣法。自助采樣法：給定包含m個樣本的數(shù)據(jù)集D，對它采樣產(chǎn)生數(shù)據(jù)集D’，每次隨機從

D中挑選一個樣本，將其拷貝放入D’，然后再將該樣本放回數(shù)據(jù)集D中，使得該樣本在下次采樣時仍有可能被采到；這個過程重復執(zhí)行m次后，就得到了包含m個樣本的數(shù)據(jù)集D’，這就是自助采樣的結果。顯然，D中有一部分樣本會在D’中多次出現(xiàn)，而另一部分樣本不出現(xiàn)樣本在m次采樣中始終不被采到的概率是(1

1

)m

，取極限得到mm

emlim(1

1

)m

1

0.368bagging算法Bagging算法的主要思想：給定訓練集 和弱學習算法，對該學習算法進行T次調(diào)用，每次調(diào)用時只使用訓練集S中的某個子集作為當前訓練集，每一個訓練例在某輪訓練集中可以多次或根本不出現(xiàn)。經(jīng)過T次調(diào)用后，可得到T個不同的分類器啊，當對于一個測試實例工進行分類時，分別調(diào)用這T個分類器，得到T個分類結果。最后對分類問題把這T個分類結果中出現(xiàn)次數(shù)多的類賦予測試實例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

輪的

函數(shù)ht

.t

=

t

+

1

.End最終輸出：

對未知樣本X分類時，每個模型ht得到一個分類器，得票最高的未知樣本x

的分類輸入：訓練集；3：若t<T，回到1，并令t=t+1，否則轉(zhuǎn)4；函4：將各 集合生成最終數(shù)：D={(x1,

y1),(x2

,

y2

),,(xm

,

ym

)}基學習算法h(x)；訓練輪數(shù)T輸出：集成

模型過程：1：從初始的訓練集中采用boostrap方法抽取出m個訓練例組成子集S’；2：在S’上訓練基學習器

h1,h2

,

,hT

，得到第t輪的 函數(shù)ht(x)；函數(shù)H

(x)

signhi

(x)03

Bagging算法圖2

Bagging算法描述03

Bagging算法Bagging與Boosting的區(qū)別：Bagging的訓練集的選擇是隨機的，各訓練集之間相互獨立；而Boosting的訓練集的選擇不獨立，各輪訓練集的選擇與前面各輪的學習有關；Bagging的各個 函數(shù)沒 重，而Boosting各訓練集

重；Bagging各個函數(shù)可以并行生成，Boosting只能順序生成。（對于像神經(jīng)網(wǎng)絡這種比較耗時的學習方法，

Bagging可通過并行訓練節(jié)省大量的時間）Bagging

和AdaBoost

區(qū)別Bagging的訓練集是隨機的，各訓練集是獨的，而

Boosting訓練集的選擇不是獨立的，每一次選擇的訓練集都依賴于上一次學習的結果。Bagging的每個

函數(shù)(即弱假設)沒重，而Boosting根據(jù)每一次訓練的訓練誤差得到該次函數(shù)的權重。Bagging的各個

函數(shù)可以并行生成，而Boosting的只能順序生成。對于像神經(jīng)網(wǎng)絡這樣極為耗時的學習方法，Bagging可通過并行訓練節(jié)省大量時間開銷。理論出發(fā)點和Boosting算法AdaBoost算法Bagging算法隨機森林選擇性集成總結課程內(nèi)容04

隨機森林--Random

Forest隨機森林（RandomForest，簡稱RF）是Bagging的一個擴展變體。隨機森林由許多的決策樹組成，因為這些決策樹的形成采用了隨機的方法，因此也叫做隨機決策樹。隨機森林中的樹之間是沒有關聯(lián)的。當測試數(shù)據(jù)進入隨機森林時，其實就是讓每一顆決策樹進行分類，最后取所有決策樹中分類結果最多的那類為最終的結果。RF在以決策樹為基學習器構建Bagging集成的基礎上，進一步在決策樹的訓練過程中引入隨機屬性選擇。傳統(tǒng)決策樹在選擇劃分屬性時是在當前結點的屬性集合（假定有d個屬性）中選擇一個最優(yōu)屬性；在RF中，對決策樹的每個結點，先從該結點的屬性集合中隨機選擇一個包含k個屬性的子集，然后再從這個子集中選擇一個最優(yōu)屬性用于劃分；這里的參數(shù)k控制了隨機性的引入程度：若令k=d，則基決策樹的構建與傳統(tǒng)決策樹相同；若令k=1，則是隨機選擇一個屬性用于劃分；一般情況下， 值k=log2d。04

隨機森林--Random

Forest決策樹復習：決策樹實際上是將空間用超平面進行劃分的

法，每次分割的時候，都將當前的空間一分為二，比如說下面的決策樹（其屬性的值都是連續(xù)的實數(shù)）：圖3 決策樹圖4 空間劃分后04

隨機森林--Random

Forest隨機森林的構造過程：假N個樣本，則有放回的隨機選擇N個樣本（每次隨機選擇一個樣本，然后放回繼續(xù)選擇），用選擇好的N個樣本來訓練決策樹。當每個樣本有d個屬性時，在決策樹的每個節(jié)點需要時，隨機從這k個屬性中選取出k個屬性，滿足條件k<<d。然后從這k個屬性中采用某種策略（比如說信息增益）來選擇1個屬性作為該節(jié)點的屬性。決策樹形成過程中每個節(jié)點都要按照步驟2來，一直到不能夠再 為止。注意整個決策樹形成過程中沒有進行剪枝。按照步驟1~3建立大量的決策樹，這樣就構成了隨機森林。隨機森林的隨機性體現(xiàn)在：每顆數(shù)的訓練樣本是隨機的；樹中每個節(jié)點的分類屬性是隨機選擇的。04

隨機森林--Random

Forest隨機森林的優(yōu)點：在數(shù)據(jù)集上表現(xiàn)良好，兩個隨機性的引入，使得隨機森林不容易陷入過擬合，具有很好的抗噪聲能力。它能夠處理很高維度（feature很多）的數(shù)據(jù)，并且不用做特征選擇，對數(shù)據(jù)集的適應能力強：既能處理離散型數(shù)據(jù)，也能處理連續(xù)型數(shù)據(jù)，數(shù)據(jù)集無需規(guī)范化。能夠并行處理，訓練速度快。隨機森林的缺點：算法傾向于觀測值較多的類別隨機森林中水平較多的分類屬性的自變量（如土地利用類型>20個類別）比水平較少的分類屬性的自變量（氣候區(qū)類型<10個類別）對模型的影響大。理論出發(fā)點和Boosting算法AdaBoost算法Bagging算法隨機森林選擇性集成總結課程內(nèi)容的在意味著：時需要更大的計算開銷，因為要計算的選擇性集成既然多個學習器的集成比單個學習器更好，那么是不是學習器越多越好?更大的

開銷，因為有

的 需要保存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在有一組 學習器可用時，從中選擇一部分進行集成，可能比用所