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

“分而治之”

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

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

(branches)

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

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

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

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

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

假設，隨機變量

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

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

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

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

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

下訓練集

的條件熵記為信息增益

表示用屬性

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

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

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

中屬于第k類的子集記為

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

信息熵

信息熵

右邊數據中：

數量是否信息熵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老年否否一般否

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

在信息增益

的基礎之上除以屬性A的熵：歸一化信息增益比公式希望選擇信息增益最大的屬性同時還希望該屬性的離散值為均勻分布。最大化意味著屬性最好只有2種取值而且這2種取值的樣本是均勻分布。因此，C4.5算法更傾向于產生二分叉形狀的決策樹，即二叉決策樹。4.C4.5算法本章目錄決策過程與決策樹建立決策樹的基本原則ID3決策樹C4.5決策樹歸一化信息增益比二叉樹vs多叉樹屬性缺失問題統一離散屬性與連續屬性決策樹的剪枝CART決策樹本章小結4.C4.5算法[問題]對于屬性缺失的問題，C4.5算法需要解決2個子問題：（1）如何在屬性缺失的情況下選擇最優分裂屬性？（2）如果某個樣本在分裂屬性上有缺失值，我們如何對這些樣本點進行劃分？[猜想]我們去掉“職業”屬性中的某些樣本的值來研究該問題。對于第1個子問題，C4.5算法不采用填補缺失值的策略。因為，我們無法去猜測缺失部分的真值。我們發現缺失值樣本的數量一般比較少。一個自然的想法是利用非缺失屬性值的樣本來計算歸一化信息增益比然后再對歸一化信息增益比乘以一個“打折因子”。“打折因子”體現了缺失值帶來的不確定性。4.C4.5算法給定數據集D，假設屬性A有缺失值，令

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

為：

其中,為折算因子，

為樣本子集

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

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

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

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

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

其中，

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

。可表示為：

其中，

表示子樹的分類誤差，

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

在

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

其中，

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

，類別數為K，第k類樣本子集記為

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

。我們用屬性

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

…………第1次劃分

第2次劃分

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

第2次劃分

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

CART算法-分類基尼指數

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

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

和

、

和

、

和

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

和

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

。回歸樹f(x)可表示為：我們又該如何去劃分子結點和設定該子結點上的回歸值

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