機(jī)器學(xué)習(xí)算法與實(shí)踐 課件 第7、8章 決策樹(shù)、集成學(xué)習(xí)

第七章決策樹(shù)決策樹(shù)（DecisionTree）是一種基本的分類與回歸方法，是最早的機(jī)器學(xué)習(xí)算法之一。1979年，J.RossQuinlan提出了ID3算法原型，并于1983年和1986年對(duì)ID3算法進(jìn)行了總結(jié)和簡(jiǎn)化，正式確立了決策樹(shù)理論。此間的1984年，LeoBreiman,JeromeFriedman,RichardOlshen與CharlesStone共同提出了分類與回歸樹(shù)（ClassificationandRegressionTrees），即CART算法。1993年，Quinlan在ID3算法的基礎(chǔ)上又提出了著名的C4.5算法。相對(duì)于其他算法，決策樹(shù)算法的基本原理更加符合人的思維方式，可以產(chǎn)生可視化的分類或回歸規(guī)則，生成的模型也具有可解釋性，因此其應(yīng)用十分廣泛。本章主要介紹上述3種決策樹(shù)算法的原理、流程及實(shí)現(xiàn)。17.1決策樹(shù)概述決策樹(shù)是一種呈樹(shù)形結(jié)構(gòu)的層次模型，可以是二又樹(shù)也可以是多叉樹(shù)。在分類問(wèn)題中，樹(shù)的每個(gè)非葉節(jié)點(diǎn)表示對(duì)一個(gè)特征的判斷，每個(gè)分支代表該特征在某個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別。使用決策樹(shù)進(jìn)行決策的過(guò)程就是從根節(jié)點(diǎn)開(kāi)始，逐個(gè)判斷待分類項(xiàng)中相應(yīng)的特征，并按照其值選擇輸出分支，直到到達(dá)葉節(jié)點(diǎn)，將葉節(jié)點(diǎn)存放的類別作為決策的結(jié)果。每一個(gè)樣本只會(huì)被一條路徑覆蓋（樣本的特征與路徑上的特征一致或樣本滿足規(guī)則的條件）。27.1決策樹(shù)概述如果想知道在不同天氣情況下人們是否會(huì)去室外打球，就可以建立圖7-1中的決策樹(shù)。圖中的菱形框表示對(duì)一個(gè)特征的判斷，菱形框下方線段上的文字表示每個(gè)判斷的所有可能的取值。圖中最上方的矩形框?yàn)椤案?jié)點(diǎn)”，中間矩形框?yàn)椤爸虚g節(jié)點(diǎn)”，最下方矩形框?yàn)椤叭~節(jié)點(diǎn)”。圖7-1決策樹(shù)算法原理舉例3稱箭頭的起點(diǎn)是終點(diǎn)的“父節(jié)點(diǎn)”，終點(diǎn)是起點(diǎn)的“子節(jié)點(diǎn)”。當(dāng)子節(jié)點(diǎn)只有兩個(gè)時(shí)，通常把他們稱為“左子節(jié)點(diǎn)”和“右子節(jié)點(diǎn)”。7.1決策樹(shù)概述決策樹(shù)構(gòu)造過(guò)程：1）從根節(jié)點(diǎn)開(kāi)始，將數(shù)據(jù)集依照某個(gè)特征的取值劃分為互不相交的幾個(gè)子集；2）如果某個(gè)子集中的樣本都屬于同一個(gè)類別或某一個(gè)類別所占的百分比大于設(shè)定的閾值，則將其設(shè)置為葉節(jié)點(diǎn)，并將多數(shù)樣本的類別作為該葉節(jié)點(diǎn)的類別。否則將該子集設(shè)置為中間節(jié)點(diǎn)，并依照某個(gè)特征的取值繼續(xù)劃分；3）重復(fù)步驟2）直至所有分支的末尾一行均為葉節(jié)點(diǎn)。

47.1決策樹(shù)概述構(gòu)造決策樹(shù)的關(guān)鍵是如何進(jìn)行最優(yōu)特征劃分，即確定非葉節(jié)點(diǎn)對(duì)應(yīng)的特征及其判斷閾值。最優(yōu)特征劃分的方法有很多，每種決策樹(shù)之所以不同，一般都是因?yàn)樽顑?yōu)特征選擇的標(biāo)準(zhǔn)上有所差異，不同的標(biāo)準(zhǔn)導(dǎo)致生成不同類型的決策樹(shù)。本章介紹其中三個(gè)相對(duì)而言比較基本且使用廣泛的算法：ID3、C4.5和CART。三種算法是以遞進(jìn)的關(guān)系產(chǎn)生的。1）ID3算法是最基礎(chǔ)的決策樹(shù)算法，可以解決離散型數(shù)據(jù)的分類問(wèn)題。2）C4.5算法在ID3算法的基礎(chǔ)上進(jìn)一步發(fā)展，可以解決混合型數(shù)據(jù)的分類問(wèn)題。3）CART算法則更進(jìn)一步，在分類問(wèn)題的基礎(chǔ)上，還可以解決回歸問(wèn)題。雖說(shuō)上述算法的功能越來(lái)越強(qiáng)大，但其核心思想都是一致的，即算法通過(guò)不斷劃分?jǐn)?shù)據(jù)集來(lái)生成決策樹(shù)，其中每一步都選擇最優(yōu)的劃分特征。5一般而言，隨著劃分過(guò)程不斷進(jìn)行，希望決策樹(shù)的每個(gè)分枝中所包含的樣本盡可能屬于同一類別，即節(jié)點(diǎn)的“純度”越來(lái)越高。因此，對(duì)于一個(gè)包含多個(gè)特征的數(shù)據(jù)集，應(yīng)盡量選擇對(duì)劃分后子集的純度提升最多的特征。信息熵可以用來(lái)度量一個(gè)系統(tǒng)的有（無(wú)）序程度。如果將其應(yīng)用在數(shù)據(jù)集上，那么一個(gè)集合中包含樣本的類別越多，則說(shuō)明數(shù)據(jù)越“混亂”，信息墑越大；否則說(shuō)明數(shù)據(jù)越“純凈”，信息墑越小。而我們要做的就是保證每一次劃分都讓劃分后的信息墑降低的最多，也就是信息墑的增益最大。ID3決策樹(shù)算法就是以信息增益作為決策樹(shù)分支的劃分依據(jù)，每次選擇信息增益最大的特征進(jìn)行劃分。ID3算法只能處理離散數(shù)據(jù)，即可以處理像性別特征、布爾值特征等離散型特征，但沒(méi)法處理特征值在某個(gè)區(qū)間內(nèi)可以任意取值的特征，如身高特征、年齡特征等。7.2

ID3算法6

7.2.1信息熵和信息增益7

7.2.1信息熵和信息增益8

7.2.1信息熵和信息增益9

7.2.2

ID3算法流程10（8）對(duì)每個(gè)子集從步驟（1）開(kāi)始繼續(xù)執(zhí)行。其中步驟（6）的“停止條件”（也可稱為“預(yù)剪枝”）有多種定義方法，較為常用的是如下兩種：1）若選擇作為劃分特征時(shí)的信息增益小于某個(gè)閾值，則停止；2）事先把數(shù)據(jù)集分為訓(xùn)練集與測(cè)試集，若由訓(xùn)練集得到的節(jié)點(diǎn)并不能降低測(cè)試集上的錯(cuò)誤率，則停止。這兩種停止條件通用于C4.5算法和CART算法。同時(shí)，決策樹(shù)會(huì)在許多地方應(yīng)用到遞歸的思想，上述算法中的步驟（7）正是經(jīng)典的遞歸。7.2.2

ID3算法流程11例7-1：表7-1給出了一個(gè)哺乳動(dòng)物數(shù)據(jù)集包含14個(gè)樣本，樣本有“飲食習(xí)性”、“胎生動(dòng)物”、“水生動(dòng)物”、“會(huì)飛”四個(gè)特征，“哺乳動(dòng)物”為樣本的類別標(biāo)記，有“是”與“否”兩種取值。

7.2

ID3算法表7-1

哺乳動(dòng)物分類數(shù)據(jù)集12

7.2

ID3算法13

7.2

ID3算法14

7.3

C4.5算法ID3算法存在一個(gè)問(wèn)題，就是偏向于多值特征。例如，如果一個(gè)特征是樣本的唯一標(biāo)識(shí)，則ID3會(huì)選擇它作為最優(yōu)劃分特征。這樣雖然使得劃分充分純凈，但這種劃分對(duì)分類幾乎毫無(wú)用處，而且小數(shù)目子集在分類效果上是不如大數(shù)目子集好的（如過(guò)擬合、抗噪差等問(wèn)題）。所以，為了解決這個(gè)問(wèn)題，可以對(duì)會(huì)產(chǎn)生大量“小數(shù)目”子集的劃分進(jìn)行懲罰，即劃分后產(chǎn)生的子集越小，它的信息熵要懲罰性的增大。這樣雖然ID3算法中會(huì)因?yàn)楹芏鄤澐趾蟮男?shù)量子集而產(chǎn)生較低的信息熵，但做懲罰值處理后，熵值就會(huì)平衡性的增大。這就是C4.5算法的改進(jìn)方向，它不再使用信息增益而是改用信息增益率來(lái)對(duì)最優(yōu)劃分特征進(jìn)行選擇，克服了使用信息增益選擇特征時(shí)偏向于多值特征的不足。此外，C4.5算法還可以處理連續(xù)型特征。15

7.3.1信息增益率

16

7.3.1信息增益率由此看出，劃分的子集越多、子集中樣本數(shù)量越少，懲罰值越大，相除后的信息增益率也就越小，依此做到了一定的平衡。由于“懲罰”了產(chǎn)生小樣本數(shù)量子集的劃分，其由于樣本數(shù)量少帶來(lái)信息增益抗噪性差的問(wèn)題也得到一定程度的解決，這就是C4.5算法的最大好處。另外C4.5和ID3算法還有一個(gè)特點(diǎn)，這兩個(gè)算法的根本都要計(jì)算信息增益，而信息增益的一個(gè)大前提就是要先進(jìn)行劃分，然后才能計(jì)算。所以，每計(jì)算一次增益也就代表進(jìn)行了一次劃分，而劃分特征接下來(lái)就不能再用了，所以ID3和C4.5算法在分類時(shí)會(huì)不斷消耗特征。17

7.3.2連續(xù)型特征處理

18

7.3.2連續(xù)型特征處理

19

7.3.2連續(xù)型特征處理

20

7.3.3C4.5算法流程

21

7.3.3C4.5算法流程

22

7.4分類與回歸樹(shù)分類與回歸樹(shù)（ClassificationAndRegressionTree，CART）算法是目前決策樹(shù)算法中最為成熟的一類算法，它既可用于分類，也可用于回歸。其一大特色就是假設(shè)最終生成的決策樹(shù)為二叉樹(shù)，即它在處理離散型和連續(xù)型特征時(shí)都會(huì)通過(guò)二分標(biāo)準(zhǔn)來(lái)劃分?jǐn)?shù)據(jù)。在處理分類問(wèn)題時(shí)，CART算法一般會(huì)使用基尼系數(shù)作為劃分優(yōu)劣的度量，算法的其他流程與C4.5算法類似。在處理回歸問(wèn)題時(shí)，CART算法使用平方誤差最小化準(zhǔn)則（SquaredResidualsMinimization）。將數(shù)據(jù)集劃分后，利用線性回歸建模，如果每次劃分后的子集仍然難以擬合則繼續(xù)劃分。這樣創(chuàng)建出來(lái)的決策樹(shù)，每個(gè)葉節(jié)點(diǎn)都是一個(gè)線性回歸模型。這些線性回歸模型反映了數(shù)據(jù)集中蘊(yùn)含的模式，也稱為模型樹(shù)。因此，CART不僅支持整體預(yù)測(cè)，也支持局部模式的預(yù)測(cè)，并有能力從整體中找到模式或根據(jù)模式組合成一個(gè)整體。整體與模式之間的相互結(jié)合，對(duì)于預(yù)測(cè)分析非常有價(jià)值。237.4.1基尼系數(shù)

247.4.1基尼系數(shù)

257.4.2回歸樹(shù)

267.4.2回歸樹(shù)

277.4.2回歸樹(shù)

287.5剪枝策略從直觀上來(lái)說(shuō)，只要決策樹(shù)足夠深，劃分標(biāo)準(zhǔn)足夠細(xì)，它在訓(xùn)練集上的表現(xiàn)就能接近完美：但同時(shí)也容易想象，由于它可能把訓(xùn)練集的一些“特性”當(dāng)作所有數(shù)據(jù)的“特性”來(lái)看待，它在未知的測(cè)試數(shù)據(jù)上的表現(xiàn)可能就會(huì)比較一般，亦即會(huì)出現(xiàn)過(guò)擬合的問(wèn)題。模型出現(xiàn)過(guò)擬合問(wèn)題一般是因?yàn)槟Ｐ吞^(guò)復(fù)雜，所以決策樹(shù)解決過(guò)擬合的方法是采取適當(dāng)?shù)摹凹糁Α薄?97.5剪枝策略剪枝通常分為兩類：“預(yù)剪枝”和“后剪枝”，其中“預(yù)剪枝”的概念在前文中已有使用，彼時(shí)采取的說(shuō)法是“停止條件”，如樹(shù)的深度超出閾值、當(dāng)前節(jié)點(diǎn)的樣本數(shù)量小于閾值、信息增益小于閾值等等。但是選取適當(dāng)?shù)拈撝当容^困難，過(guò)高會(huì)導(dǎo)致過(guò)擬合，而過(guò)低會(huì)導(dǎo)致欠擬合，因此需要人工反復(fù)地訓(xùn)練樣本才能得到很好的效果。預(yù)剪枝也有優(yōu)勢(shì)，由于它不必生成整棵決策樹(shù)，且算法簡(jiǎn)單、效率高，適合大規(guī)模問(wèn)題的粗略估計(jì)。而“后剪枝”是指在完全生成的決策樹(shù)上，剪掉樹(shù)中不具備一般代表性的子樹(shù)，使用葉節(jié)點(diǎn)取而代之，進(jìn)而形成一棵規(guī)模較小的新樹(shù)。換句話說(shuō)，后剪枝是從全局出發(fā)，通過(guò)某種標(biāo)準(zhǔn)對(duì)一些節(jié)點(diǎn)進(jìn)行局部剪枝，這樣就能減少?zèng)Q策樹(shù)中節(jié)點(diǎn)的數(shù)目，從而有效地降低模型復(fù)雜度。307.5剪枝策略問(wèn)題的關(guān)鍵在于如何定出局部剪枝的標(biāo)準(zhǔn)。通常來(lái)說(shuō)有兩種做法：1）應(yīng)用交叉驗(yàn)證的思想，若局部剪枝能夠使得模型在測(cè)試集上的錯(cuò)誤率降低，則進(jìn)行局部剪枝（預(yù)剪枝中也可應(yīng)用類似的思想）；2）應(yīng)用正則化的思想，綜合考慮不確定性和模型復(fù)雜度來(lái)定出一個(gè)新的損失函數(shù)（此前的損失函數(shù)只考慮了誤差），用該損失函數(shù)作為一個(gè)節(jié)點(diǎn)是否進(jìn)行局部剪枝的標(biāo)準(zhǔn)。第二種做法又涉及另一個(gè)關(guān)鍵問(wèn)題：如何定量分析決策樹(shù)中一個(gè)節(jié)點(diǎn)的復(fù)雜度？一個(gè)直觀且合理的方法是：直接使用該節(jié)點(diǎn)下屬葉節(jié)點(diǎn)的個(gè)數(shù)作為復(fù)雜度，這種方法稱為代價(jià)復(fù)雜度剪枝法（CostComplexityPruning）。317.5剪枝策略

327.5剪枝策略

33圖7-1決策樹(shù)算法原理舉例

7.5.1單一因子策略

34

7.5.1單一因子策略

357.5.2最優(yōu)因子策略

367.5.2最優(yōu)因子策略

377.5.2最優(yōu)因子策略

38

7.6

本章小結(jié)本章主要介紹了決策樹(shù)算法中的ID3算法、C4.5算法以及CART算法，講解了其算法原理、算法流程以及在Python中的具體實(shí)現(xiàn)代碼，最后介紹了決策樹(shù)算法中使用的剪枝策略。CART算法與ID3算法和C4.5算法都由最優(yōu)劃分特征選擇、樹(shù)的生成、剪枝等流程構(gòu)成。但I(xiàn)D3算法和C4.5算法用于分類，CART既可用于分類又可用于回歸。ID3算法和C4.5算法生成的決策樹(shù)可以是多叉的，每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)由該節(jié)點(diǎn)特征的取值種類而定，而CART算法為假設(shè)決策樹(shù)為二叉樹(shù)，其等價(jià)于遞歸地二分每一個(gè)特征。39第八章集成學(xué)習(xí)在監(jiān)督學(xué)習(xí)中，傳統(tǒng)方式是按照選定的學(xué)習(xí)算法，針對(duì)某個(gè)給定的訓(xùn)練數(shù)據(jù)集訓(xùn)練得到一個(gè)特定的學(xué)習(xí)器模型，然后再用它預(yù)測(cè)未知的樣本。集成學(xué)習(xí)可以組合多個(gè)弱模型以期得到一個(gè)更好更全面的強(qiáng)模型，集成學(xué)習(xí)潛在的思想是即便某一個(gè)弱學(xué)習(xí)器得到了錯(cuò)誤的預(yù)測(cè)，其他的弱學(xué)習(xí)器也可以將錯(cuò)誤糾正回來(lái)。因此，集成學(xué)習(xí)（EnsembleLearning）是指利用多個(gè)獨(dú)立的弱學(xué)習(xí)器來(lái)進(jìn)行學(xué)習(xí)，組合某輸入樣例在各個(gè)弱學(xué)習(xí)器上的輸出，并由它們按照某種策略共同決定輸出。408.1集成學(xué)習(xí)概述集成學(xué)習(xí)是一種功能十分強(qiáng)大的機(jī)器學(xué)習(xí)方法，其基本思想是先通過(guò)一定的規(guī)則生成固定數(shù)量的弱學(xué)習(xí)器（或稱為基學(xué)習(xí)器、個(gè)體學(xué)習(xí)器），再采用某種集成策略將這些弱學(xué)習(xí)器的預(yù)測(cè)結(jié)果組合起來(lái)，從而形成最終的結(jié)論。弱學(xué)習(xí)器（WeakLearner）是錯(cuò)誤概率小于1/2的學(xué)習(xí)器，也就是說(shuō)在兩類問(wèn)題上僅比隨機(jī)猜測(cè)好，而強(qiáng)學(xué)習(xí)器（StrongLearner）則具有任意小的錯(cuò)誤概率。集成學(xué)習(xí)不是一個(gè)單獨(dú)的機(jī)器學(xué)習(xí)算法，而是一個(gè)將多重或多個(gè)弱學(xué)習(xí)器組合成一個(gè)強(qiáng)學(xué)習(xí)器，從而有效地提升分類效果。一般而言，集成學(xué)習(xí)中的基學(xué)習(xí)器可以是同質(zhì)的“弱學(xué)習(xí)器”，也可以是異質(zhì)的“弱學(xué)習(xí)器”。目前，同質(zhì)弱學(xué)習(xí)器的應(yīng)用最為廣泛，同質(zhì)弱學(xué)習(xí)器中使用最多的模型是CART決策樹(shù)和神經(jīng)網(wǎng)絡(luò)。同質(zhì)弱學(xué)習(xí)器按照其間是否存在依賴關(guān)系又可以分為兩類。418.1集成學(xué)習(xí)概述串行集成方法：參與訓(xùn)練的弱學(xué)習(xí)器按照順序執(zhí)行。串行方法的原理是利用弱學(xué)習(xí)器之間的依賴關(guān)系，通過(guò)對(duì)之前訓(xùn)練中錯(cuò)誤標(biāo)記的樣本賦值較高的權(quán)重，可以提高整體的預(yù)測(cè)效果，其代表算法是提升法（Boosting）。并行集成方法：參與訓(xùn)練的弱學(xué)習(xí)器并行執(zhí)行。并行方法的原理是利用弱學(xué)習(xí)器之間的獨(dú)立性，由于弱學(xué)習(xí)器之間不存在強(qiáng)依賴關(guān)系，通過(guò)平均可以顯著降低錯(cuò)誤，其代表算法是投票法（Voting）和裝袋法（Bagging）。428.1集成學(xué)習(xí)概述根據(jù)集成學(xué)習(xí)的用途不同，結(jié)論合成的方法也各不相同。當(dāng)集成學(xué)習(xí)用于分類時(shí)，集成的輸出通常由各弱學(xué)習(xí)器的輸出投票產(chǎn)生。通常采用絕對(duì)多數(shù)投票法（某分類成為最終結(jié)果，當(dāng)且僅當(dāng)有超過(guò)半數(shù)的弱學(xué)習(xí)器輸出結(jié)果為該分類）或相對(duì)多數(shù)投票法（某分類成為最終結(jié)果，當(dāng)且僅當(dāng)輸出結(jié)果為該分類的弱學(xué)習(xí)器的數(shù)目最多）。理論分析和大量實(shí)驗(yàn)表明，后者優(yōu)于前者。當(dāng)集成學(xué)習(xí)用于回歸時(shí)，集成的輸出通常由各學(xué)習(xí)器的輸出通過(guò)簡(jiǎn)單平均或加權(quán)平均產(chǎn)生，采用加權(quán)平均可以得到比簡(jiǎn)單平均更好的泛化能力。

43投票法（Voting）是集成學(xué)習(xí)里面針對(duì)分類問(wèn)題的一種結(jié)合策略?；舅枷胧沁x擇所有機(jī)器學(xué)習(xí)算法當(dāng)中輸出最多的那個(gè)類。分類的機(jī)器學(xué)習(xí)算法輸出有兩種類型，一種是直接輸出類標(biāo)簽，另外一種是輸出類概率。使用前者進(jìn)行投票叫做硬投票（Majority/HardVoting），使用后者進(jìn)行分類叫做軟投票（SoftVoting）。例如，在硬投票中，如果三個(gè)算法將特定葡萄酒的顏色預(yù)測(cè)為“白色”、“白色”和“紅色”，則集成算法將輸出“白色”；在軟投票中，如果算法A以40%的概率預(yù)測(cè)對(duì)象是一塊巖石，而算法B以80%的概率預(yù)測(cè)它是一塊巖石，那么集成算法將預(yù)測(cè)該對(duì)象是一塊巖石的可能性為(80+40)/2=60%。8.2投票法44

8.2.1投票策略45

8.2.1投票策略46

8.3裝袋法47隨機(jī)森林（RandomForest，RF）就是通過(guò)裝袋法的思想將多個(gè)弱學(xué)習(xí)器組合在一起，其弱學(xué)習(xí)器一般采用CART決策樹(shù)。隨機(jī)森林的“隨機(jī)”體現(xiàn)在兩個(gè)方面：一是樣本的隨機(jī)選取，即通過(guò)有放回采樣構(gòu)造子數(shù)據(jù)集，子數(shù)據(jù)集的樣本數(shù)量和原始數(shù)據(jù)集一致。不同子數(shù)據(jù)集中的樣本可以重復(fù)，同一個(gè)子數(shù)據(jù)集中的樣本也可以重復(fù)。這樣在訓(xùn)練模型時(shí)，每一棵樹(shù)的輸入樣本都不是全部的樣本，使森林中的決策樹(shù)不至于產(chǎn)生局部最優(yōu)解。二是特征的隨機(jī)選取，即隨機(jī)森林中的決策樹(shù)的每一個(gè)分裂過(guò)程并未使用所有特征，而是從所有特征中隨機(jī)選取一定的特征，之后在隨機(jī)選取的特征中選取最優(yōu)劃分特征。最后，將多棵決策樹(shù)的輸出進(jìn)行整合作為最終輸出。隨機(jī)森林既可以用于分類問(wèn)題，也可以用于回歸問(wèn)題，生成過(guò)程中這兩個(gè)隨機(jī)性可以確保不會(huì)出現(xiàn)過(guò)擬合的情況。8.3.1隨機(jī)森林算法48

8.3.1隨機(jī)森林算法49這里我們還要提到一下極端隨機(jī)樹(shù)（ExtremelyRandomizedTrees）算法，簡(jiǎn)稱ExtraTree。它與隨機(jī)森林算法十分相似，主要區(qū)別是隨機(jī)森林采用對(duì)數(shù)據(jù)集有放回隨機(jī)采樣的方式生成多個(gè)子訓(xùn)練集，而極端隨機(jī)樹(shù)使用整個(gè)數(shù)據(jù)集作為訓(xùn)練集，但是節(jié)點(diǎn)的劃分特征是隨機(jī)選取的。因?yàn)榉至咽峭耆S機(jī)的，所以有時(shí)可以得到比隨機(jī)森林更好的結(jié)果。8.3.2極端隨機(jī)樹(shù)算法50提升法（Boosting）是一種重要的集成學(xué)習(xí)技術(shù)，能夠?qū)㈩A(yù)測(cè)精度僅比隨機(jī)猜度略高的弱學(xué)習(xí)器增強(qiáng)為預(yù)測(cè)精度高的強(qiáng)學(xué)習(xí)器，這在直接構(gòu)造強(qiáng)學(xué)習(xí)器非常困難的情況下，為學(xué)習(xí)算法的設(shè)計(jì)提供了一種有效的新思路和新方法。提升法可以提升任意給定學(xué)習(xí)算法的準(zhǔn)確度，主要思想是通過(guò)一些簡(jiǎn)單的規(guī)則整合得到一個(gè)整體，使得該整體具有的性能比任何一個(gè)部分都高。其思想受啟發(fā)于Valiant提出的PAC（ProbablyApproximatelyCorrect）學(xué)習(xí)模型。8.4提升法51在PAC學(xué)習(xí)模型中，能夠在多項(xiàng)式個(gè)時(shí)間內(nèi)獲得特定要求的正確率即就是一個(gè)好的學(xué)習(xí)過(guò)程。該模型由統(tǒng)計(jì)模式識(shí)別、決策理論得到的一些簡(jiǎn)單理論并結(jié)合計(jì)算復(fù)雜理論的方法而得出的學(xué)習(xí)模型，其中提出了弱學(xué)習(xí)和強(qiáng)學(xué)習(xí)的概念。提升法先從初始訓(xùn)練集訓(xùn)練出一個(gè)弱學(xué)習(xí)器，再根據(jù)弱學(xué)習(xí)器的表現(xiàn)對(duì)訓(xùn)練樣本分布進(jìn)行調(diào)整，使得先前弱學(xué)習(xí)器做錯(cuò)的訓(xùn)練樣本在后續(xù)受到更多關(guān)注，然后基于調(diào)整后的樣本分布來(lái)訓(xùn)練下一個(gè)弱學(xué)習(xí)器。如此重復(fù)進(jìn)行，直至弱學(xué)習(xí)器數(shù)目達(dá)到指定的值k，最終將這k個(gè)弱學(xué)習(xí)器的輸出進(jìn)行加權(quán)結(jié)合。提升法包含一系列算法，如AdaBoost（AdaptiveBoosting，自適應(yīng)提升算法），GradientBoosting（梯度提升算法）等。提升法中的個(gè)體分類器可以是不同類的分類器。8.4提升法52自適應(yīng)提升算法（AdaBoost）中有兩種權(quán)重，一種是樣本的權(quán)重，另一種是弱分類器的權(quán)重。樣本的權(quán)重主要用于弱分類器計(jì)算誤差最小的劃分特征，找到之后用這個(gè)最小誤差計(jì)算出該弱分類器的權(quán)重（發(fā)言權(quán)），分類器權(quán)重越大說(shuō)明該弱分類器在最終決策時(shí)擁有更大的發(fā)言權(quán)。其原理是通過(guò)調(diào)整樣本的權(quán)重和弱分類器的權(quán)重，對(duì)關(guān)鍵分類特征進(jìn)行挑選，逐步訓(xùn)練不同的弱分類器，再用適當(dāng)?shù)拈撝颠x擇最佳弱分類器，最后將每次迭代訓(xùn)練選出的最佳弱分類器構(gòu)建為強(qiáng)分類器。因此，每一個(gè)弱分類器都是在樣本的不同權(quán)重集上訓(xùn)練獲得的。每個(gè)樣本被分類的難易度決定權(quán)重，而分類的難易度是經(jīng)過(guò)前面步驟中的分類器的輸出估計(jì)得到的。8.4.1自適應(yīng)提升算法算法流程53在自適應(yīng)提升算法中，每訓(xùn)練完一個(gè)弱分類器都就會(huì)調(diào)整權(quán)重，上一輪訓(xùn)練中被誤分類的樣本的權(quán)重會(huì)增加。因此在本輪訓(xùn)練中，由于權(quán)重影響，本輪的弱分類器將更有可能把上一輪的誤分類樣本分對(duì)，如果還是沒(méi)有分對(duì)，那么分錯(cuò)的樣本的權(quán)重將繼續(xù)增加，下一個(gè)弱分類器將更加關(guān)注這個(gè)點(diǎn)，盡量將其分對(duì)。也就是說(shuō)，下一個(gè)分類器主要關(guān)注上一個(gè)分類器沒(méi)分對(duì)的樣本，因此每個(gè)弱分類器都有各自最關(guān)注的點(diǎn)，每個(gè)弱分類器都只關(guān)注整個(gè)數(shù)據(jù)集的中一部分?jǐn)?shù)據(jù)。但是這也產(chǎn)生了一個(gè)問(wèn)題，就是第n個(gè)分類器更可能分對(duì)第n-1個(gè)分類器沒(méi)分對(duì)的樣本，卻不能保證以前分類器分對(duì)的樣本還能分對(duì)。所以必然是所有的弱分類器組合在一起才能發(fā)揮出最好的效果。因此，最終投票表決時(shí)，需要根據(jù)弱分類器的權(quán)重來(lái)進(jìn)行加權(quán)投票，權(quán)重大小是根據(jù)弱分類器的分類錯(cuò)誤率計(jì)算得出的，總的規(guī)律就是弱分類器錯(cuò)誤率越低，其權(quán)重就越高。8.4.1自適應(yīng)提升算法算法流程54

8.4.1自適應(yīng)提升算法算法流程55

8.4.1自適應(yīng)提升算法算法流程56

8.4.1自適應(yīng)提升算法算法流程57

8.4.1自適應(yīng)提升算法算法流程58

8.4.1自適應(yīng)提升算法算法流程59

8.4.1自適應(yīng)提升算法算法流程60

8.4.1自適應(yīng)提升算法算法流程61

8.4.1自適應(yīng)提升算法算法流程62

8.4.1自適應(yīng)提升算法算法流程63

8.4.1自適應(yīng)提升算法算法流程64

8.4.1自適應(yīng)提升算法算法流程65梯度提升（GradientBoosting）算法的基本思想是：串行地