第九章組合分類器分類方法基于經(jīng)典統(tǒng)計(jì)理論的分類法參數(shù)法從訓(xùn)練集中直接得出分類結(jié)果引言該方法是在已知先驗(yàn)類別概率和類條件概率，用貝葉斯公式求出判別函數(shù)。優(yōu)點(diǎn)：最優(yōu)分類（理論）缺點(diǎn)：實(shí)際應(yīng)用中很難實(shí)現(xiàn)直接求取分類判別函數(shù)（分類面）事先能確定判別函數(shù)或分類面的形式，再通過訓(xùn)練樣本確定其中的參數(shù)。如SVM，線性判別分析等非參數(shù)如近鄰法等1.基于經(jīng)典統(tǒng)計(jì)理論的分類法2.參數(shù)法3.從訓(xùn)練集直接得出分類結(jié)果評(píng)估分類法的準(zhǔn)確率保留法（holdout）k-倍交叉驗(yàn)證（k-foldcrossvalidation）提高分類法的準(zhǔn)確率

“arcing”(adaptivereweightingandcombining):重新使用或選擇數(shù)據(jù)，以期達(dá)到改善分類器性能的目的。baggingboosting分類法的準(zhǔn)確性holdout劃分為兩個(gè)獨(dú)立的數(shù)據(jù)集：訓(xùn)練集，測(cè)試集變形：隨機(jī)子選擇評(píng)估分類法的準(zhǔn)確率（1）數(shù)據(jù)訓(xùn)練集測(cè)試集導(dǎo)出分類法評(píng)估準(zhǔn)確性k-倍交叉驗(yàn)證將數(shù)據(jù)集分為k個(gè)子集；用k-1個(gè)子集作訓(xùn)練集，1個(gè)子集作測(cè)試集，然后k次交叉驗(yàn)證求平均。評(píng)估分類法的準(zhǔn)確率（2）數(shù)據(jù)S1S2Sk···訓(xùn)練集測(cè)試集BaggingBoosting組合分類器的核心思想是：對(duì)于多個(gè)單獨(dú)分類器的結(jié)果進(jìn)行組合。提高分類法的準(zhǔn)確率訓(xùn)練數(shù)據(jù)C1C2Ct組合得票測(cè)試數(shù)據(jù)類預(yù)測(cè)···組合分類器的核心思想是對(duì)于多個(gè)單獨(dú)的分類器的結(jié)果進(jìn)行加權(quán)整合，以獲得一個(gè)更好的性能！個(gè)體與組合的關(guān)系泛化誤差計(jì)算復(fù)雜度其他評(píng)價(jià)標(biāo)準(zhǔn)分類器組合評(píng)價(jià)假設(shè)E(s)表示在數(shù)據(jù)集s上的組合分類結(jié)果，那么E(s)的泛化誤差則是根據(jù)帶類標(biāo)的樣本空間分布對(duì)任意數(shù)量選定樣本的誤分類概率。估計(jì)泛化誤差實(shí)驗(yàn)方法保留法交叉驗(yàn)證估計(jì)自舉法泛化誤差計(jì)算復(fù)雜度一般是通過比較每一分類器在執(zhí)行過程中耗費(fèi)的CPU總數(shù)，可以將其分為如下三種度量：計(jì)算復(fù)雜度產(chǎn)生一個(gè)新的分類器的計(jì)算復(fù)雜度更新一個(gè)分類器的計(jì)算復(fù)雜度將一個(gè)新樣本進(jìn)行分類的計(jì)算復(fù)雜度總體復(fù)雜度可以看作是這三種度量方式的總和，特別是當(dāng)數(shù)據(jù)集數(shù)量較大時(shí)，更應(yīng)當(dāng)考慮到產(chǎn)生某一新的分類器的損耗。魯棒性穩(wěn)定性可解釋性大規(guī)模數(shù)據(jù)的可測(cè)量性

其他評(píng)價(jià)標(biāo)準(zhǔn)Bagging集成算法基本思想給定一個(gè)學(xué)習(xí)算法和一個(gè)訓(xùn)練集（n個(gè)樣本），讓該學(xué)習(xí)算法訓(xùn)練多輪，每輪的訓(xùn)練集由從初始的訓(xùn)練集中隨機(jī)取出n個(gè)樣本組成（放回取樣），初始訓(xùn)練樣本在某輪訓(xùn)練集中可以出現(xiàn)多次或根本不出現(xiàn)。訓(xùn)練之后得到一個(gè)預(yù)測(cè)函數(shù)序列，最終的預(yù)測(cè)函數(shù)對(duì)分類問題采用投票方式，對(duì)回歸問題采用簡單平均。最后結(jié)果準(zhǔn)確率將得到提高。Bagging集成算法算法

Fort=1,2,…,TDo

從數(shù)據(jù)集S中取樣（放回選樣） 訓(xùn)練得到模型Ht

對(duì)未知樣本X分類時(shí),每個(gè)模型Ht都得出一個(gè)分類，得票最高的即為未知樣本X的分類也可通過得票的平均值用于連續(xù)值的預(yù)測(cè)Bagging集成算法架構(gòu)…C1

C2

CT

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

c*(x)=maxcnttct(x)S1

S2

ST

X

預(yù)處理例題分析例：現(xiàn)有10個(gè)人的兩門課程考試數(shù)據(jù)如表9.1所示：(1070)，(2070)，(3010)，(4060)，(6080)，(6050)，(7090)，(8070)，(9080)，(10060)。每一門課程（分別用X1，X2表示）要求大于60分為合格，未達(dá)到60分的視為不合格，其中“X”表示至少有一門課程未通過，而“O”表示兩門課程均通過。

根據(jù)10個(gè)樣本數(shù)據(jù)繪制數(shù)據(jù)分布圖

學(xué)號(hào)01020304050607080910成績(10,70)(20,70)(30,10)(40,60)(60,80)(60,50)(70,90)(80,70)(90,80)(100,60)是否全通過否否否否是否是是是是10個(gè)考試成績樣本數(shù)據(jù)及其類標(biāo)使用線性分類器對(duì)樣本進(jìn)行劃分，首先從10個(gè)樣本成績中隨機(jī)抽取5個(gè)樣本，一共抽取三輪，抽取結(jié)果如下：第一輪：02、03、05、05、10號(hào)樣本，第二輪：04、04、06、09、10號(hào)樣本，第三輪：03、04、08、08、09號(hào)樣本，因此構(gòu)造出三個(gè)線性分類器分別為：

學(xué)號(hào)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投票結(jié)果-1-1-1-11-11111使用不同的分類器對(duì)樣本數(shù)據(jù)進(jìn)行劃分根據(jù)這三個(gè)線性分類器進(jìn)行投票表決Bagging集成算法分析Bagging要求“不穩(wěn)定”的分類方法；

比如：決策樹，神經(jīng)網(wǎng)絡(luò)算法不穩(wěn)定：數(shù)據(jù)集的小的變動(dòng)能夠使得分類結(jié)果的顯著的變動(dòng)弱學(xué)習(xí)算法的穩(wěn)定性是Bagging能否提高預(yù)測(cè)準(zhǔn)確率的關(guān)鍵因素：Bagging對(duì)不穩(wěn)定的學(xué)習(xí)算法能提高預(yù)測(cè)的準(zhǔn)確度，而對(duì)穩(wěn)定的學(xué)習(xí)算法效果不明顯，有時(shí)甚至使預(yù)測(cè)的準(zhǔn)確度降低。（Breiman1996)

隨機(jī)森林（1）隨機(jī)森林（RandomForest，RF）是Bagging的一種擴(kuò)展算法，它以決策樹作為基本的弱分類器，與Bagging不同的是，它并非從所有特征中選擇最優(yōu)特征作為分界，而是在一個(gè)特征子集中選擇最優(yōu)，即引入了隨機(jī)特征選擇，并因此提升了其方法的泛化性能。隨機(jī)森林（2）算法：輸入：訓(xùn)練集D={(x1,y1),(x2,y2),...,(xn,yn)}決策樹H：重采樣的樣本分布Db樣本集訓(xùn)練特征數(shù)目為M，訓(xùn)練輪數(shù)T

訓(xùn)練過程:

fort=1，2，……，T

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

ht=H(m,Db)

endfor

endfor輸出：Boosting背景提出問題：強(qiáng)學(xué)習(xí)算法：準(zhǔn)確率很高的學(xué)習(xí)算法弱學(xué)習(xí)算法：準(zhǔn)確率不高，僅比隨機(jī)猜測(cè)略好是否可以將弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法目標(biāo)：提高任何給定的學(xué)習(xí)算法的分類準(zhǔn)確率Boosting背景最初的Boosting算法

Schapire1989提出AdaBoost（adaptiveboosting）算法

FreundandSchapire1995提出基本思想：每個(gè)樣本都賦予一個(gè)權(quán)重T次迭代，每次迭代后，對(duì)分類錯(cuò)誤的樣本加大權(quán)重，使得下一次的迭代更加關(guān)注這些樣本。Boosting過程：在一定的權(quán)重條件下訓(xùn)練數(shù)據(jù)，得出分類法Ct根據(jù)Ct的錯(cuò)誤率調(diào)整權(quán)重SetofweightedinstancesClassifierCt

trainclassifier

adjustweightsBoosting……h(huán)1(x)h2(x)hT(x)C*

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

trainS1trainC2

S2CT

trainSTXD1D2DTBoosting總結(jié)(1)Boosting易受到噪音的影響；AdaBoost可以用來鑒別異常；經(jīng)過多輪后，具有最高權(quán)重的樣本即為異常。應(yīng)用Boosting，不需尋找很難獲得的預(yù)測(cè)精度很高的強(qiáng)學(xué)習(xí)算法，只需找出精度稍好于隨機(jī)預(yù)測(cè)的弱學(xué)習(xí)算法即可。但是同時(shí)也有可能使集成過分偏向于某幾個(gè)特別困難的示例。因此，該方法不太穩(wěn)定，有時(shí)能起到很好的作用，有時(shí)卻沒有效果。Boosting類別中的一種；非常成功的機(jī)器學(xué)習(xí)算法，由YoavFreund和RobertSchapire于1995年提出，他們因此獲得了2003年的哥德爾獎(jiǎng)（G?delPrize）。前一輪訓(xùn)練結(jié)果將用來調(diào)整本輪訓(xùn)練的樣本，從而優(yōu)化本輪訓(xùn)練出的模型，使得整個(gè)的模型更加精確。AdaBoost側(cè)重于調(diào)整本輪樣本的樣本權(quán)重，從而改變樣本的分布。AdaBoost（AdaptiveBoosting）AdaBoost輸入:(X1,Y1),(X2,Y2),…(Xn,Yn)

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

初始化:W1(i)=1/nFort=1,…,T，do:在Wt下訓(xùn)練,得到弱的假設(shè)ht:X->{-1,+1},

錯(cuò)誤率:Εt=ΣWt(i)[ht(Xi)≠Yi]選擇αt=1/2ln((1-Εt)/Εt

),更改權(quán)值: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是一種對(duì)多個(gè)回歸樹進(jìn)行集成的方法，構(gòu)造出的多個(gè)回歸樹通過優(yōu)化使得樹群的預(yù)測(cè)值盡可能接近真實(shí)值且具有泛化能力，它是對(duì)Boosting族算法的改進(jìn)，GrandientBoost改變的是本輪訓(xùn)練的樣本標(biāo)簽，能夠?qū)蝹€(gè)弱分類器進(jìn)行優(yōu)化。回歸樹:回歸樹預(yù)測(cè)模型XGBoost(2)分割點(diǎn)尋找算法

輸入：I，當(dāng)前結(jié)點(diǎn)的樣本集合，d，特征維數(shù)增益Gain取0fork=1tom

for每一個(gè)待分類的數(shù)據(jù)集計(jì)算其一階、二階導(dǎo)數(shù)(score表示當(dāng)前分割值得分)endend輸出：最大分割值得分Bagging和boosting區(qū)別聯(lián)系(1)訓(xùn)練集：Bagging：隨機(jī)選擇，各輪訓(xùn)練集相互獨(dú)立Boosting：各輪訓(xùn)練集并不獨(dú)立，它的選擇去前輪的學(xué)習(xí)結(jié)果有關(guān)預(yù)測(cè)函數(shù)：Bagging：沒有權(quán)重；可以并行生成Boosting：有權(quán)重；只能順序生成

Bagging和boosting區(qū)別聯(lián)系(2)在許多應(yīng)用中，準(zhǔn)確率比運(yùn)算速度更為重要，因?yàn)橛?jì)算機(jī)的性價(jià)比提高很快。bagging和boosting都可以有效地提高分類的準(zhǔn)確性。在大多數(shù)數(shù)據(jù)集中，boosting的準(zhǔn)確性比bagging高。在有些數(shù)據(jù)集中，boosting會(huì)引起退化。--Overfit

集成學(xué)習(xí)中多樣性個(gè)體的構(gòu)造基于不同訓(xùn)練數(shù)據(jù)集的構(gòu)造方式(bagging,boosting)基于不同特征集的構(gòu)造方式(特征選擇；隨機(jī)投影；隨機(jī)子空間）基于不同性質(zhì)的學(xué)習(xí)機(jī)器或分類器的構(gòu)造方式基于相同學(xué)習(xí)機(jī)器的不同學(xué)習(xí)參數(shù)的構(gòu)造方式其他方法，如嵌入隨機(jī)性，處理輸出等。集成學(xué)習(xí)算法中的合并方法

投票法(Voting)；平均法(Averaging)；加權(quán)平均法(Weightedaveraging)；其他方法集成學(xué)習(xí)系統(tǒng)的構(gòu)成非監(jiān)督集成學(xué)習(xí)非監(jiān)督集成(Unsupervisedensemble)也稱聚類集成，被認(rèn)為在許多方面都能超越單個(gè)聚類算法，如：魯棒性，穩(wěn)定性和一致性估計(jì)以及并行性和可量測(cè)性在圖像分割，生物信息等領(lǐng)域已獲得了很好的性能。相對(duì)于分類集成，對(duì)其研究還較少，在應(yīng)用領(lǐng)域的研究有待進(jìn)一步展開。個(gè)體聚類構(gòu)造方面現(xiàn)有方法基于Bagging、Boosting的聚類集成方法。多目標(biāo)數(shù)據(jù)聚類方法，用來處理具有多種不同結(jié)構(gòu)的數(shù)據(jù)劃分問題?！喜⒎椒ǖ难芯坑捎诰垲惤Y(jié)果僅僅是一種符號(hào)，不同聚類結(jié)果間并無對(duì)應(yīng)關(guān)系，例如兩個(gè)聚類結(jié)果與雖然表現(xiàn)形式不同，實(shí)際上卻是在邏輯上完全相同的聚類，這一現(xiàn)實(shí)使得多個(gè)聚類結(jié)果的合并比分類集成中的合并要困難得多。非