06機器學習-決策樹

2023年06月機器學習-決策樹

“分而治之”

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

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

(branches)

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

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

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

因此信息熵只依賴于隨機變量

2.建立決策樹的基本原則

假設(shè)，隨機變量

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

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

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

2.建立決策樹的基本原則[問題]

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

下訓練集

的條件熵記為信息增益

表示用屬性

對訓練集分裂前后信息熵的差值：

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

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

中屬于第k類的子集記為

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

信息熵

信息熵

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

在信息增益

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

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

為：

其中,為折算因子，

為樣本子集

計算出的信息增益。折算因子

可以簡單地用無缺失值樣本的數(shù)量與總樣本數(shù)量的比例來確定：

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

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

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

其中，

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

?？杀硎緸椋?/p>

其中，

表示子樹的分類誤差，

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

在

處進行1階泰勒展開：5.CART算法信息熵因此可以被近似表示為：

其中，

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

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

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

。我們用屬性

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

…………第1次劃分

第2次劃分

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

第2次劃分

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

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

和

、

和

、

和

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

和

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

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

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