06機(jī)器學(xué)習(xí)-決策樹(shù)

2023年06月機(jī)器學(xué)習(xí)-決策樹(shù)

“分而治之”

本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝CART決策樹(shù)本章小結(jié)本章目錄決策過(guò)程與決策樹(shù)決策的可解釋性與離散屬性的利用決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝CART決策樹(shù)本章小結(jié)1.決策過(guò)程與決策樹(shù)希望能通過(guò)個(gè)人信息（包括“職業(yè)”“年齡”“收入”“學(xué)歷”）建立一個(gè)預(yù)測(cè)貸款是否有風(fēng)險(xiǎn)的模型。我們能不能靈活地利用多種屬性去做決策和判斷？1.決策過(guò)程與決策樹(shù)每個(gè)結(jié)點(diǎn)都代表著具有相同屬性的訓(xùn)練集合。如，“職業(yè)”結(jié)點(diǎn)、“學(xué)歷”結(jié)點(diǎn)等；決策過(guò)程可以用一種叫樹(shù)（tree）的結(jié)構(gòu)來(lái)描述，樹(shù)是由“結(jié)點(diǎn)”和“有向邊”構(gòu)成的不存在環(huán)的結(jié)構(gòu);決策的過(guò)程從根結(jié)點(diǎn)開(kāi)始評(píng)價(jià)預(yù)測(cè)樣本的屬性，并按照其屬性值選擇輸出分支遞歸地到達(dá)相應(yīng)的葉結(jié)點(diǎn)，最后將葉結(jié)點(diǎn)的類別標(biāo)簽作為預(yù)測(cè)結(jié)果三點(diǎn)直覺(jué)：1.決策過(guò)程與決策樹(shù)根節(jié)點(diǎn)(rootnode)非葉子節(jié)點(diǎn)

(non-leafnode)(代表測(cè)試條件，對(duì)數(shù)據(jù)屬性的測(cè)試)分支

(branches)

(代表測(cè)試結(jié)果)葉節(jié)點(diǎn)(leafnode)(代表分類后所獲得的分類標(biāo)記)決策樹(shù)（decisiontree）就是從根結(jié)點(diǎn)開(kāi)始，對(duì)預(yù)測(cè)樣本的某一屬性進(jìn)行測(cè)試，并根據(jù)測(cè)試結(jié)果將樣本遞歸地分配到相應(yīng)的子結(jié)點(diǎn)進(jìn)行更精細(xì)地評(píng)估直到葉子結(jié)點(diǎn)從而實(shí)現(xiàn)分類或回歸任務(wù)。1.決策樹(shù)原理決策樹(shù)：從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)得出一個(gè)樹(shù)狀結(jié)構(gòu)的模型。決策樹(shù)屬于判別模型。決策樹(shù)是一種樹(shù)狀結(jié)構(gòu)，通過(guò)做出一系列決策（選擇）來(lái)對(duì)數(shù)據(jù)進(jìn)行劃分，這類似于針對(duì)一系列問(wèn)題進(jìn)行選擇。決策樹(shù)的決策過(guò)程就是從根節(jié)點(diǎn)開(kāi)始，測(cè)試待分類項(xiàng)中對(duì)應(yīng)的特征屬性，并按照其值選擇輸出分支，直到葉子節(jié)點(diǎn)，將葉子節(jié)點(diǎn)的存放的類別作為決策結(jié)果。非葉子節(jié)點(diǎn)

(non-leafnode)(代表測(cè)試條件，對(duì)數(shù)據(jù)屬性的測(cè)試)本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則決策樹(shù)分裂與特征選擇“純度”與信息熵ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝CART決策樹(shù)本章小結(jié)2.建立決策樹(shù)的基本原則用什么屬性來(lái)分裂一個(gè)結(jié)點(diǎn)？：例如，A經(jīng)理用“職業(yè)”作為根結(jié)點(diǎn)而B(niǎo)經(jīng)理用“年齡”作為根結(jié)點(diǎn)。用哪種屬性分裂結(jié)點(diǎn)更為合理？如何讓一些結(jié)點(diǎn)變?yōu)槿~結(jié)點(diǎn)？：極端的情況下，每個(gè)葉結(jié)點(diǎn)只含有一個(gè)樣本。顯然，這是一個(gè)很壞的方法。經(jīng)理A和經(jīng)理B兩個(gè)完全不同的決策過(guò)程暗示了以下2個(gè)問(wèn)題。2.建立決策樹(shù)的基本原則(a)作為根結(jié)點(diǎn)的劃分(b)作為根結(jié)點(diǎn)的劃分為了回答上述2個(gè)的問(wèn)題，如圖（a）和圖（b）所示，我們給出一個(gè)用不同屬性構(gòu)造決策樹(shù)的過(guò)程。（a）的決策樹(shù)只分裂1次而圖（b）的決策樹(shù)需要分裂2次。因此，圖（a）的決策樹(shù)比圖（b）的決策樹(shù)更簡(jiǎn)單而有效。因此，我們猜想應(yīng)該把分裂后各子結(jié)點(diǎn)盡可能地“純”作為屬性選擇依據(jù)?！凹儭币馕吨Y(jié)點(diǎn)內(nèi)的樣本點(diǎn)盡可能屬于同一類別。決策樹(shù)的基本構(gòu)造算法2.建立決策樹(shù)的基本原則算法支持模型樹(shù)結(jié)構(gòu)特征選擇連續(xù)值處理缺失值處理剪枝特征屬性多次使用ID3分類多叉樹(shù)信息增益不支持不支持不支持不支持C4.5分類多叉樹(shù)信息增益率支持支持支持不支持CART分類回歸二叉樹(shù)基尼指數(shù)均方差支持支持支持支持1.決策樹(shù)原理決策樹(shù)的三種基本類型建立決策樹(shù)的關(guān)鍵，即在當(dāng)前狀態(tài)下選擇哪個(gè)屬性作為分類依據(jù)。根據(jù)不同的目標(biāo)函數(shù)，建立決策樹(shù)主要有一下三種算法：ID3(IterativeDichotomiser)、C4.5、CART(ClassificationAndRegressionTree)。本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則決策樹(shù)分裂與特征選擇“純度”與信息熵ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝CART決策樹(shù)本章小結(jié)2.建立決策樹(shù)的基本原則[猜想]與“純度”相反的概念是“混亂度”。熵（entropy）是描述系統(tǒng)混亂度的數(shù)學(xué)概念。熵最早用于度量熱力學(xué)系統(tǒng)中分子運(yùn)動(dòng)的無(wú)序程度。在1948年，香農(nóng)引入了信息熵（informationentropy）將其定義為隨機(jī)變量不確定性的度量，即，一個(gè)隨機(jī)變量越是確定，它的信息熵就越低；反之，它的信息熵就越高。[問(wèn)題]我們?nèi)绾味x一組樣本的“純度”？

2.建立決策樹(shù)的基本原則[猜想]與“純度”相反的概念是“混亂度”。熵（entropy）是描述系統(tǒng)混亂度的數(shù)學(xué)概念。熵最早用于度量熱力學(xué)系統(tǒng)中分子運(yùn)動(dòng)的無(wú)序程度。在1948年，香農(nóng)引入了信息熵（informationentropy）將其定義為隨機(jī)變量不確定性的度量，即，一個(gè)隨機(jī)變量越是確定，它的信息熵就越低；反之，它的信息熵就越高。[問(wèn)題]我們?nèi)绾味x一組樣本的“純度”？

因此信息熵只依賴于隨機(jī)變量

2.建立決策樹(shù)的基本原則

假設(shè)，隨機(jī)變量

的概率分布服從伯努利分布，下圖給出隨機(jī)變量

的信息熵隨著概率從0變化到1的規(guī)律。

2.建立決策樹(shù)的基本原則決策樹(shù)需要找出讓數(shù)據(jù)集“純度”提升最快的屬性。因此，我們需要計(jì)算已知某種屬性下數(shù)據(jù)集“純度”的方法——一種與條件概率相對(duì)應(yīng)的熵，即條件熵（conditionalentropy）。

2.建立決策樹(shù)的基本原則[問(wèn)題]

怎么用信息熵和條件熵來(lái)定義數(shù)據(jù)集分裂后“純度”的提升值？我們使用分裂前后訓(xùn)練集信息熵的差異大小來(lái)衡量屬性的優(yōu)劣。假設(shè)，訓(xùn)練集的熵記為，給定屬性

下訓(xùn)練集

的條件熵記為信息增益

表示用屬性

對(duì)訓(xùn)練集分裂前后信息熵的差值：

公式說(shuō)明對(duì)于待劃分的訓(xùn)練集，熵刻畫(huà)了數(shù)據(jù)集的“不純凈度”而條件熵刻畫(huà)了用屬性將訓(xùn)練集分裂后的“不純凈度”。因此，信息增益表示使用屬性對(duì)數(shù)據(jù)集劃分后不確定性降低的程度。2.建立決策樹(shù)的基本原則對(duì)于給定訓(xùn)練集，熵是固定不變的。如果，我們需要讓信息增益公式最大，信息增益公式會(huì)轉(zhuǎn)化為：根據(jù)公式，條件熵越小說(shuō)明使用屬性劃分后結(jié)點(diǎn)的“純度”越高。問(wèn)題是：給定數(shù)據(jù)集和屬性，我們?cè)趺从?jì)算信息增益？2.建立決策樹(shù)的基本原則假設(shè)，假設(shè)離散型屬性A有M個(gè)離散值，

訓(xùn)練集包含K個(gè)類別，表示屬于第k類的樣本子集,。我們根據(jù)屬性A的取值將訓(xùn)練集D分裂為M個(gè)樣本子集。樣本子集

中屬于第k類的子集記為

。根據(jù)上述定義，信息增益公式計(jì)算如下3步。計(jì)算數(shù)據(jù)集的熵:計(jì)算特征A對(duì)數(shù)據(jù)集D的條件熵：計(jì)算信息增益：

信息熵

信息熵

右邊數(shù)據(jù)中：

數(shù)量是否信息熵15960.971年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否按年齡劃分信息熵

年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否

年齡數(shù)量是否信息熵青年5230.9710中年5320.9710老年5410.7219

年齡有工作有房子信用

條件熵

條件熵

年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否

信息增益

信息增益

年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝CART決策樹(shù)本章小結(jié)3.ID3算法ID3算法最早是由羅斯昆（J.RossQuinlan）于1975年提出的一種決策樹(shù)構(gòu)建算法，算法的核心是“信息熵”，期望信息越小，信息熵越大，樣本純度越低。。ID3算法是以信息論為基礎(chǔ)，以信息增益為衡量標(biāo)準(zhǔn)，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)的歸納分類。ID3算法計(jì)算每個(gè)屬性的信息增益，并選取具有最高增益的屬性作為給定的測(cè)試屬性。ID3算法3.ID3算法ID3算法3.ID3算法缺點(diǎn)ID3沒(méi)有剪枝策略，容易過(guò)擬合；信息增益準(zhǔn)則對(duì)可取值數(shù)目較多的特征有所偏好，類似“編號(hào)”的特征其信息增益接近于1；只能用于處理離散分布的特征；沒(méi)有考慮缺失值。本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)歸一化信息增益比二叉樹(shù)vs多叉樹(shù)屬性缺失問(wèn)題統(tǒng)一離散屬性與連續(xù)屬性決策樹(shù)的剪枝CART決策樹(shù)本章小結(jié)4.C4.5算法在分裂決策樹(shù)的結(jié)點(diǎn)時(shí)，ID3算法優(yōu)先選擇信息增益最大的屬性。對(duì)于連續(xù)型變量每個(gè)樣本的取值都不一樣，所以其條件熵為0（意味著信息增益最大），這不合理！ID3算法會(huì)優(yōu)先選擇取值數(shù)量多的屬性分裂。ID3面臨著3個(gè)問(wèn)題：如何避免決策樹(shù)優(yōu)先選擇取值數(shù)量多的屬性？如何利用連續(xù)值屬性進(jìn)行決策樹(shù)的構(gòu)造？如何處理屬性缺失的問(wèn)題？[猜想]對(duì)于ID3算法沒(méi)有解決的第1個(gè)問(wèn)題，我們可以用“歸一化因子”來(lái)歸一化屬性取值過(guò)多的問(wèn)題。一種自然的想法是利用屬性A取值的數(shù)量作為分母：顯然，我們希望屬性A取值的數(shù)量越多時(shí)，歸一化的信息增益比越??；而屬性A的取值的數(shù)量越少時(shí)，歸一化的信息增益比越大。上式很完美地解決了屬性取值數(shù)量帶來(lái)的問(wèn)題。4.C4.5算法C4.5算法用信息熵為“歸一化因子”。即，信息增益比

在信息增益

的基礎(chǔ)之上除以屬性A的熵：歸一化信息增益比公式希望選擇信息增益最大的屬性同時(shí)還希望該屬性的離散值為均勻分布。最大化意味著屬性最好只有2種取值而且這2種取值的樣本是均勻分布。因此，C4.5算法更傾向于產(chǎn)生二分叉形狀的決策樹(shù)，即二叉決策樹(shù)。4.C4.5算法本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)歸一化信息增益比二叉樹(shù)vs多叉樹(shù)屬性缺失問(wèn)題統(tǒng)一離散屬性與連續(xù)屬性決策樹(shù)的剪枝CART決策樹(shù)本章小結(jié)4.C4.5算法[問(wèn)題]對(duì)于屬性缺失的問(wèn)題，C4.5算法需要解決2個(gè)子問(wèn)題：（1）如何在屬性缺失的情況下選擇最優(yōu)分裂屬性？（2）如果某個(gè)樣本在分裂屬性上有缺失值，我們?nèi)绾螌?duì)這些樣本點(diǎn)進(jìn)行劃分？[猜想]我們?nèi)サ簟奥殬I(yè)”屬性中的某些樣本的值來(lái)研究該問(wèn)題。對(duì)于第1個(gè)子問(wèn)題，C4.5算法不采用填補(bǔ)缺失值的策略。因?yàn)?，我們無(wú)法去猜測(cè)缺失部分的真值。我們發(fā)現(xiàn)缺失值樣本的數(shù)量一般比較少。一個(gè)自然的想法是利用非缺失屬性值的樣本來(lái)計(jì)算歸一化信息增益比然后再對(duì)歸一化信息增益比乘以一個(gè)“打折因子”?！按蛘垡蜃印斌w現(xiàn)了缺失值帶來(lái)的不確定性。4.C4.5算法給定數(shù)據(jù)集D，假設(shè)屬性A有缺失值，令

表示訓(xùn)練集D中屬性A無(wú)缺失值的樣本子集。那么“折算”后屬性a的信息增益

為：

其中,為折算因子，

為樣本子集

計(jì)算出的信息增益。折算因子

可以簡(jiǎn)單地用無(wú)缺失值樣本的數(shù)量與總樣本數(shù)量的比例來(lái)確定：

備注：信息增益信息增益率信息增益率

年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否

C4.5的缺點(diǎn)缺點(diǎn)剪枝策略可以再優(yōu)化；C4.5用的是多叉樹(shù)，用二叉樹(shù)效率更高；C4.5只能用于分類；C4.5使用的熵模型擁有大量耗時(shí)的對(duì)數(shù)運(yùn)算，連續(xù)值還有排序運(yùn)算；C4.5在構(gòu)造樹(shù)的過(guò)程中，對(duì)數(shù)值屬性值需要按照其大小進(jìn)行排序，從中選擇一個(gè)分割點(diǎn)，所以只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)，程序無(wú)法運(yùn)行。本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝預(yù)剪枝悲觀剪枝代價(jià)敏感剪枝CART決策樹(shù)本章小結(jié)決策樹(shù)的剪枝過(guò)擬合的原因：為了盡可能正確分類訓(xùn)練樣本，節(jié)點(diǎn)的劃分過(guò)程會(huì)不斷重復(fù)直到不能再分，用少數(shù)樣本的特性進(jìn)行判斷。把訓(xùn)練樣本的一些特點(diǎn)當(dāng)做所有數(shù)據(jù)都具有的一般性質(zhì)，從而導(dǎo)致過(guò)擬合。剪枝的基本策略有“預(yù)剪枝”（prepruning）和“后剪枝”（post-pruning）通過(guò)剪枝處理去掉一些分支來(lái)降低過(guò)擬合的風(fēng)險(xiǎn)。5決策樹(shù)剪枝[猜想]在構(gòu)造決策樹(shù)的過(guò)程中，我們提前終止某些分支的生長(zhǎng)。即，對(duì)每個(gè)結(jié)點(diǎn)在分裂前先進(jìn)行評(píng)估，若當(dāng)前結(jié)點(diǎn)的分裂不能帶來(lái)決策樹(shù)性能的提升，我們將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)。有3種參數(shù)來(lái)停止決策樹(shù)的生長(zhǎng)：（1）樹(shù)的深度max_depth：當(dāng)決策樹(shù)的深度達(dá)到預(yù)設(shè)值之后，我們停止決策樹(shù)的生長(zhǎng)；（2）葉結(jié)點(diǎn)內(nèi)樣本數(shù)量min_sample_split：當(dāng)葉結(jié)點(diǎn)內(nèi)樣本的數(shù)量小于預(yù)設(shè)值時(shí)，我們停止決策樹(shù)的生長(zhǎng)；（3）信息增益閾值min_inpurity_decrease：計(jì)算每次結(jié)點(diǎn)分裂后后決策樹(shù)的信息增益，如果信息增益小于預(yù)設(shè)值時(shí)，我們停止決策樹(shù)的生長(zhǎng)。預(yù)剪枝策略使得決策樹(shù)有很多分支沒(méi)有被“展開(kāi)”，這不僅降低了決策樹(shù)過(guò)擬合的風(fēng)險(xiǎn)還顯著地提高了決策樹(shù)的訓(xùn)練與測(cè)試速度。但是，選取一個(gè)合適的剪枝閾值是非常困難的。較高的閾值可能導(dǎo)致過(guò)分簡(jiǎn)化的決策樹(shù)而較低的閾值可能使決策樹(shù)無(wú)法被優(yōu)化。5決策樹(shù)剪枝預(yù)剪枝[實(shí)驗(yàn)]用Scikit-learn提供的決策樹(shù)函數(shù)對(duì)月牙形數(shù)據(jù)集建立決策樹(shù)模型。請(qǐng)利用預(yù)剪枝策略對(duì)決策樹(shù)進(jìn)行剪枝并觀察剪枝對(duì)決策樹(shù)性能的影響。剪枝條件為“決策樹(shù)最大深度為3”的決策面和決策樹(shù)結(jié)構(gòu)5決策樹(shù)剪枝預(yù)剪枝[實(shí)驗(yàn)]用Scikit-learn提供的決策樹(shù)函數(shù)對(duì)月牙形數(shù)據(jù)集建立決策樹(shù)模型。請(qǐng)利用預(yù)剪枝策略對(duì)決策樹(shù)進(jìn)行剪枝并觀察剪枝對(duì)決策樹(shù)性能的影響。剪枝條件為“決策樹(shù)最大深度為100”的決策面和決策樹(shù)結(jié)構(gòu)5決策樹(shù)剪枝預(yù)剪枝[實(shí)驗(yàn)]用Scikit-learn提供的決策樹(shù)函數(shù)對(duì)月牙形數(shù)據(jù)集建立決策樹(shù)模型。請(qǐng)利用預(yù)剪枝策略對(duì)決策樹(shù)進(jìn)行剪枝并觀察剪枝對(duì)決策樹(shù)性能的影響。剪枝條件為“決策樹(shù)最大深度為0.05”的決策面和決策樹(shù)結(jié)構(gòu)本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝預(yù)剪枝悲觀剪枝代價(jià)敏感剪枝CART決策樹(shù)本章小結(jié)C4.5的剪枝先生成一棵完整的決策樹(shù)，然后再?gòu)娜~結(jié)點(diǎn)向上對(duì)每個(gè)非葉結(jié)點(diǎn)進(jìn)行考察。該結(jié)點(diǎn)對(duì)應(yīng)的子樹(shù)在剪枝后能帶來(lái)決策樹(shù)性能的提升（至少是不降低）則對(duì)該子樹(shù)進(jìn)行剪枝。問(wèn)題是我們用什么原則對(duì)非葉結(jié)點(diǎn)的性能進(jìn)行評(píng)估？一個(gè)自然的想法是利用驗(yàn)證集對(duì)子結(jié)點(diǎn)的分類性能進(jìn)行評(píng)估。但是，自底向上地對(duì)所有非葉子結(jié)點(diǎn)進(jìn)行組合判斷將非常耗時(shí)。（X）不需要驗(yàn)證集我們就能對(duì)子樹(shù)進(jìn)行性能評(píng)估。即，我們僅利用訓(xùn)練集的數(shù)據(jù)對(duì)子結(jié)點(diǎn)進(jìn)行剪枝，如果決策樹(shù)的精度在剪枝前后沒(méi)有變化則該子結(jié)點(diǎn)需要進(jìn)行剪枝。C4.5的剪枝子樹(shù)在剪枝后變?yōu)槿~結(jié)點(diǎn)t，如果，剪枝前后誤判樣本數(shù)的期望不超過(guò)預(yù)定義的閾值Th，我們則認(rèn)為沒(méi)有必要進(jìn)行該子結(jié)點(diǎn)的分裂。即：

其中，

表示期望。[問(wèn)題]雖然在理論上很有道理，但是閾值Th該如何確定？統(tǒng)計(jì)上，置信區(qū)間能檢驗(yàn)?zāi)硞€(gè)隨機(jī)變量的值是否在合理范圍內(nèi)。如果先建立每個(gè)結(jié)點(diǎn)錯(cuò)誤率的概率分布，我們可利用該概率分布的置信區(qū)間確定閾值。閾值Th可以設(shè)置為錯(cuò)誤率的某個(gè)上限（最悲觀的誤差或容忍最大的誤差），那么我們就應(yīng)該剪去這個(gè)分枝。C4.5的剪枝后剪枝之悲觀剪枝假設(shè)，決策樹(shù)的某顆子樹(shù)含有N個(gè)樣本，其中，有E個(gè)被錯(cuò)分的樣本。因此，在剪枝后，該結(jié)點(diǎn)的錯(cuò)誤率為：我們可以假設(shè)每個(gè)結(jié)點(diǎn)內(nèi)樣本的誤判數(shù)服從二項(xiàng)分布,其中，二項(xiàng)式分布的置信區(qū)間為：C4.5的剪枝后剪枝之悲觀剪枝本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝預(yù)剪枝悲觀剪枝代價(jià)敏感剪枝CART決策樹(shù)本章小結(jié)C4.5的剪枝悲觀剪枝方法能避免使用驗(yàn)證集，但是悲觀剪枝方法存在置信區(qū)間的設(shè)置問(wèn)題和二項(xiàng)式分布逼近精度的問(wèn)題。另外，悲觀剪枝也沒(méi)有考慮到?jīng)Q策樹(shù)的復(fù)雜度問(wèn)題。[問(wèn)題]假設(shè)，我們還有足夠多的樣本構(gòu)成驗(yàn)證集，如何在有驗(yàn)證集的情況下進(jìn)行后剪枝？[猜想]我們需要解決2個(gè)層次的問(wèn)題：（1）定義一種既能描述分類準(zhǔn)確性又能描述決策樹(shù)復(fù)雜度的指標(biāo)；（2）該指標(biāo)對(duì)決策樹(shù)的子樹(shù)以貪心地方式進(jìn)行剪枝。C4.5的剪枝假設(shè)，剪枝前子樹(shù)的代價(jià)復(fù)雜度函數(shù)記為

?？杀硎緸椋?/p>

其中，

表示子樹(shù)的分類誤差，

是子樹(shù)的葉結(jié)點(diǎn)數(shù)量（也表示了子樹(shù)的復(fù)雜度）子樹(shù)的分類誤差可簡(jiǎn)化為：其代價(jià)復(fù)雜度函數(shù)的變化量為：C4.5的剪枝后剪枝之復(fù)雜度剪枝假設(shè)，剪枝前后的代價(jià)復(fù)雜度變化為零時(shí)，我們得到代價(jià)復(fù)雜度指標(biāo)的表達(dá)式：公式解決了第1個(gè)問(wèn)題“既能描述分類準(zhǔn)確性又能描述子樹(shù)復(fù)雜度的指標(biāo)”。最優(yōu)子樹(shù)序列的嵌套性定理可知由葉結(jié)點(diǎn)向根結(jié)點(diǎn)遞歸生成子樹(shù)所對(duì)應(yīng)的將逐步增大。最優(yōu)子樹(shù)序列的嵌套性告訴我們可以貪心地根據(jù)的大小進(jìn)行子樹(shù)的剪枝而不需考慮所有結(jié)點(diǎn)組合成的剪枝。C4.5的剪枝后剪枝之復(fù)雜度剪枝本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝CART決策樹(shù)基尼系數(shù)與信息熵分類處理策略回歸處理策略本章小結(jié)5.CART算法CARTClassificationandRegressionTree(CART)是決策樹(shù)的一種。用基尼指數(shù)來(lái)選擇屬性（分類），或用均方差來(lái)選擇屬性（回歸）。顧名思義，CART算法既可以用于創(chuàng)建分類樹(shù)，也可以用于創(chuàng)建回歸樹(shù)，兩者在構(gòu)建的過(guò)程中稍有差異。如果目標(biāo)變量是離散的，稱為分類樹(shù)。如果目標(biāo)變量是連續(xù)的，稱為回歸樹(shù)。5.CART算法[問(wèn)題]C4.5算法所用的信息熵會(huì)涉及大量耗時(shí)的對(duì)數(shù)運(yùn)算。尤其是用連續(xù)值型屬性構(gòu)造決策樹(shù)的速度，如何加速信息增益比的計(jì)算？[猜想]因?yàn)樾畔㈧厥顷P(guān)于概率密度的連續(xù)可微函數(shù)，所以我們利用泰勒展開(kāi)對(duì)信息熵進(jìn)行1階近似。即，用線性函數(shù)逼近信息熵。我們將函數(shù)

在

處進(jìn)行1階泰勒展開(kāi)：5.CART算法信息熵因此可以被近似表示為：

其中，

又被稱為隨機(jī)變量的基尼系數(shù)。5.CART算法基尼系數(shù)將對(duì)數(shù)運(yùn)算轉(zhuǎn)化為冪運(yùn)算從而大大地降低了信息熵的計(jì)算復(fù)雜度。顯然，基尼系數(shù)公式是對(duì)信息熵的近似。因此，隨機(jī)變量的基尼系數(shù)值越小，隨機(jī)變量的不純度越低。[問(wèn)題]信息增益比用屬性的信息熵做“歸一化因子”來(lái)防止結(jié)點(diǎn)分叉過(guò)多而導(dǎo)致過(guò)擬合問(wèn)題。因此，一個(gè)重要的問(wèn)題：我們是否還用基尼系數(shù)計(jì)算屬性的熵作為“歸一化因子”？[猜想]二叉決策樹(shù)已經(jīng)避免了多叉決策樹(shù)帶來(lái)的過(guò)擬合問(wèn)題。C4.5我們已知二叉決策樹(shù)能獲得更高的信息增益比；此外，二叉決策樹(shù)處理連續(xù)型變量比多叉決策樹(shù)更方便。因此，我們只需解決基尼系數(shù)的計(jì)算。5.CART算法假設(shè)，樣本集記為D，樣本數(shù)量記為

，類別數(shù)為K，第k類樣本子集記為

。樣本集合D的基尼系數(shù)為：假設(shè)，給定訓(xùn)練集D，屬性

。我們用屬性

將樣本集D分割成D1和D2兩部分后，樣本的基尼系數(shù)為：本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝CART決策樹(shù)基尼系數(shù)與信息熵分類處理策略回歸處理策略本章小結(jié)CART算法-分類連續(xù)特征處理…………

…………第1次劃分

第2次劃分

CART算法-分類離散特征處理……………………第1次劃分

第2次劃分

CART的特征會(huì)多次參與節(jié)點(diǎn)的建立，而在ID3或C4.5的一顆子樹(shù)中，離散特征只會(huì)參與一次節(jié)點(diǎn)的建立。房子是否工作是有無(wú)3,7,8,9,10,110,1,2,4,5,6,12,13,144,12,130,1,5,6,14

CART算法-分類基尼指數(shù)

年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否分類時(shí)用基尼指數(shù)來(lái)選擇屬性粗垂直線表示根節(jié)點(diǎn)的決策邊界（深度0）：花瓣長(zhǎng)度=2.45厘米。由于左側(cè)區(qū)域是純凈的（僅Iris-Setosa），因此無(wú)法進(jìn)一步拆分。然而，右側(cè)區(qū)域是不純的，因此深度為1的右側(cè)節(jié)點(diǎn)將其分割成花瓣寬度=1.75厘米（由虛線表示）。由于max_depth設(shè)置為2，因此決策樹(shù)會(huì)在那里停止。但是，如果將max_depth設(shè)置為3，那么兩個(gè)深度為2的節(jié)點(diǎn)將各自添加另一個(gè)決策邊界（由點(diǎn)虛線表示）。150個(gè)鳶尾花樣本進(jìn)行分類，特征為花萼的長(zhǎng)度和寬度決策樹(shù)原理5.CART算法分類回歸樹(shù)的分類樹(shù)算法[問(wèn)題]有了信息熵和條件熵的近似計(jì)算方法，關(guān)鍵問(wèn)題是：分類回歸樹(shù)在處理分類問(wèn)題時(shí)，我們?nèi)绾巫裱畔⒃鲆娴脑瓌t選擇屬性將訓(xùn)練集劃分為2個(gè)子結(jié)點(diǎn)？[猜想]與C4.5算法的處理策略一樣，分類回歸樹(shù)的分類樹(shù)既要考慮離散值型屬性的劃分又要考慮連續(xù)值型屬性的劃分。對(duì)于離散值型屬性而言，當(dāng)屬性A取值數(shù)量大于2時(shí)，我們需要將屬性值的集合分裂成兩組“超級(jí)屬性值”的集合分別作為分類回歸樹(shù)的兩個(gè)分支。因此，當(dāng)屬性A的取值數(shù)量大于2時(shí)，我們只需要對(duì)屬性A取值的所有二分組合計(jì)算基尼系數(shù)，并用基尼系數(shù)最小的組合作為決策樹(shù)的兩個(gè)分枝。5.CART算法分類回歸樹(shù)的分類樹(shù)算法例如，離散值型屬性A被選出以分裂決策樹(shù)的某個(gè)結(jié)點(diǎn)，而屬性A的取值為

。在ID3和C4.5算法中，我們會(huì)建立三叉決策樹(shù)（每個(gè)分叉對(duì)應(yīng)一種取值）。相反，分類回歸樹(shù)對(duì)屬性的取值生成所有的二分組合，即，

和

、

和

、

和

；然后分類回歸樹(shù)再找到基尼系數(shù)最小的組合，比如

和

這對(duì)組合來(lái)建立二叉決策樹(shù)的兩個(gè)子結(jié)點(diǎn)。對(duì)于連續(xù)值型屬性而言，與C4.5處理連續(xù)值屬性一致，分類回歸樹(shù)將連續(xù)的屬性值離散化。區(qū)別在于，C4.5用信息增益比選擇分裂點(diǎn)時(shí)而分類回歸樹(shù)用基尼系數(shù)用基尼系數(shù)。算法6.6給出了分類回歸樹(shù)中分類樹(shù)算法流程。5.CART算法分類回歸樹(shù)的分類樹(shù)算法5.CART算法分類回歸樹(shù)的回歸樹(shù)算法[問(wèn)題]給定訓(xùn)練數(shù)據(jù)集D，樣本及回歸值和屬性集合，Ｎ為樣本數(shù)量，Ｄ為屬性的數(shù)量。我們?nèi)绾斡脹Q策樹(shù)實(shí)現(xiàn)回歸任務(wù)？分類和回歸的區(qū)別在于如何將類別標(biāo)簽擴(kuò)展到連續(xù)的取值空間。在分類任務(wù)中，決策樹(shù)利用屬性將樣本集分裂為更為“純”的樣本子集。假設(shè)，分類回歸樹(shù)的分類樹(shù)已將輸入訓(xùn)練集劃分為M個(gè)樣本子集。每個(gè)子結(jié)點(diǎn)所包含樣本的數(shù)量不僅越來(lái)越少而且樣本之間也越來(lái)越相似。因此，葉結(jié)點(diǎn)對(duì)樣本類別標(biāo)簽的判斷可以用該葉結(jié)點(diǎn)內(nèi)眾數(shù)的標(biāo)簽。理想的情況下，每個(gè)葉子結(jié)點(diǎn)內(nèi)的樣本都將具有相同的類別標(biāo)簽。本章目錄決策過(guò)程與決策樹(shù)建立決策樹(shù)的基本原則ID3決策樹(shù)C4.5決策樹(shù)決策樹(shù)的剪枝CART決策樹(shù)基尼系數(shù)與信息熵分類處理策略回歸處理策略本章小結(jié)5.CART算法對(duì)于每個(gè)葉子節(jié)點(diǎn)相當(dāng)于一類數(shù)據(jù)的聚類，每個(gè)聚類賦予一個(gè)回歸值。（a）分類問(wèn)題（b）回歸問(wèn)題5.CART算法分類回歸樹(shù)的回歸樹(shù)算法假設(shè)，ｍ個(gè)葉結(jié)點(diǎn)對(duì)應(yīng)的子結(jié)點(diǎn)分別為，相應(yīng)子結(jié)點(diǎn)內(nèi)樣本數(shù)分別為，子結(jié)點(diǎn)有個(gè)對(duì)應(yīng)地輸出值

?；貧w樹(shù)f(x)可表示為：我們又該如何去劃分子結(jié)點(diǎn)和設(shè)定該子結(jié)點(diǎn)上的回歸值

？假設(shè)，子結(jié)點(diǎn)上的回歸值為子結(jié)點(diǎn)內(nèi)所有樣本子集的平均回歸值的均值：5.CART算法分類回歸樹(shù)的回歸樹(shù)算法以下公式解決了子結(jié)點(diǎn)內(nèi)回歸值的設(shè)定后，我們用均方誤差最小化實(shí)現(xiàn)回歸樹(shù)結(jié)點(diǎn)的分裂策略：我們將利用上式實(shí)現(xiàn)將訓(xùn)練集劃分成多個(gè)子結(jié)點(diǎn)，并在每個(gè)子結(jié)點(diǎn)內(nèi)實(shí)現(xiàn)回歸。最小化目標(biāo)函數(shù)就可以選取最優(yōu)分裂屬性A及相應(yīng)的分裂點(diǎn)s（s為屬性A取值范圍內(nèi)的某個(gè)數(shù)值）。5.CART算法分類回歸樹(shù)的回歸樹(shù)算法針對(duì)屬性A，假設(shè)分裂點(diǎn)s將數(shù)據(jù)集D劃分成兩個(gè)子結(jié)點(diǎn)R1和R2。公式只需要求出讓子結(jié)點(diǎn)R1和R2各自均方差之和最小的分裂點(diǎn)。一旦我們實(shí)現(xiàn)了結(jié)點(diǎn)的1次分裂，我們就可遞歸地對(duì)下一個(gè)子結(jié)點(diǎn)進(jìn)行分裂從而構(gòu)造出回歸樹(shù)。假設(shè)，我們