# 機器學習的分類和回歸樹 > 原文： [https://machinelearningmastery.com/classification-and-regression-trees-for-machine-learning/](https://machinelearningmastery.com/classification-and-regression-trees-for-machine-learning/) 決策樹是用于預測建模機器學習的重要算法類型。 經典的決策樹算法已經存在了幾十年，現代變體如隨機森林是最有效的技術之一。 在這篇文章中，您將發現一種簡陋的決策樹算法，它以更現代的名稱CART代表分類和回歸樹。閱讀這篇文章后，你會知道： * 用于描述機器學習的CART算法的許多名稱。 * 實際存儲在磁盤上的已學習CART模型使用的表示形式。 * 如何從訓練數據中學習CART模型。 * 如何使用學習的CART模型對看不見的數據進行預測。 * 您可以使用其他資源來了解有關CART和相關算法的更多信息。 如果你已經采用了算法和數據結構課程，那么可能很難阻止你實現這個簡單而強大的算法。從那里開始，您距離自己實施的隨機森林只有一小步之遙。 讓我們開始吧。 * **2017年8月更新**：修正了一個拼寫錯誤，表明Gini是一個類的實例數，應該是實例的比例。除了計算子節點的純度之外，還更新了顯示用于評估拆分的Gini權重。  用于機器學習的分類和回歸樹 照片由 [Wonderlane](https://www.flickr.com/photos/wonderlane/2062184804/) 拍攝，保留一些權利。 ## 決策樹 分類和回歸樹或簡稱CART是 [Leo Breiman](https://en.wikipedia.org/wiki/Leo_Breiman) 引用的術語，指的是可用于分類或回歸預測建模問題的[決策樹](https://en.wikipedia.org/wiki/Decision_tree_learning)算法。 傳統上，這種算法被稱為“決策樹”，但在某些平臺上，如R，它們被更現代的術語CART所引用。 CART算法為諸如袋裝決策樹，隨機森林和提升決策樹等重要算法提供了基礎。 ## 獲取免費算法思維導圖  方便的機器學習算法思維導圖的樣本。 我已經創建了一個由類型組織的60多種算法的方便思維導圖。 下載，打印并使用它。 ## CART模型表示 CART模型的表示是二叉樹。 這是來自算法和數據結構的二叉樹，沒什么太花哨的。每個根節點表示單個輸入變量（x）和該變量上的分割點（假設變量是數字）。 樹的葉節點包含用于進行預測的輸出變量（y）。 給定一個數據集，其中兩個輸入（x）的高度以厘米為單位，重量以千克為單位，性別輸出為男性或女性，下面是二元決策樹的粗略示例（完全虛構僅用于演示目的）。  決策樹示例 樹可以作為圖形或一組規則存儲到文件中。例如，下面是上面的決策樹作為一組規則。 ```py If Height > 180 cm Then Male If Height <= 180 cm AND Weight > 80 kg Then Male If Height <= 180 cm AND Weight <= 80 kg Then Female Make Predictions With CART Models ``` 利用上述CART模型的二叉樹表示，進行預測相對簡單。 給定新輸入，通過評估在樹的根節點處開始的特定輸入來遍歷樹。 學習的二叉樹實際上是輸入空間的分區。您可以將每個輸入變量視為p維空間上的維度。決策樹將其分為矩形（當p = 2個輸入變量時）或某種具有更多輸入的超矩形。 新數據通過樹過濾并落在其中一個矩形中，該矩形的輸出值是模型預測的結果。這讓您對CART模型能夠做出的決策類型有所了解，例如：四四方方的決定邊界。 例如，如果輸入[height = 160 cm，weight = 65 kg]，我們將按如下方式遍歷上面的樹： ```py Height > 180 cm: No Weight > 80 kg: No Therefore: Female ``` ## 從數據中學習CART模型 創建CART模型涉及在這些變量上選擇輸入變量和分割點，直到構造出合適的樹。 使用貪婪算法選擇要使用的輸入變量和特定的分割或切割點以最小化成本函數。樹構造使用預定義的停止標準結束，例如分配給樹的每個葉節點的最小數量的訓練實例。 ### 貪婪的分裂 創建二元決策樹實際上是劃分輸入空間的過程。貪婪的方法用于劃分稱為[遞歸二進制分裂](https://en.wikipedia.org/wiki/Binary_splitting)的空間。 這是一個數值程序，其中所有值都排成一行，并使用成本函數嘗試和測試不同的分裂點。選擇具有最佳成本（最低成本，因為我們最小化成本）的分割。 以貪婪的方式評估和選擇所有輸入變量和所有可能的分裂點（例如，每次選擇最佳分裂點）。 對于回歸預測建模問題，最小化以選擇分割點的成本函數是落在矩形內的所有訓練樣本的總平方誤差： sum（y - 預測）^ 2 其中y是訓練樣本的輸出，預測是矩形的預測輸出。 對于分類，使用Gini索引函數，其指示葉節點的“純”程度（分配給每個節點的訓練數據的混合程度如何）。 G =總和（pk *（1 - pk）） 其中G是所有類的基尼指數，pk是在感興趣的矩形中具有類k的訓練實例的比例。具有相同類型（完全類純度）的所有類的節點將具有G = 0，其中對于二元分類問題（最差純度）具有50-50類別的G將具有G = 0.5。 對于二元分類問題，可以將其重寫為： G = 2 * p1 * p2 或 G = 1 - （p1 ^ 2 + p2 ^ 2） 每個節點的Gini索引計算由父節點中的實例總數加權。因此，二元分類問題中所選分裂點的基尼分數計算如下： G =（（1 - （g1_1 ^ 2 + g1_2 ^ 2））*（ng1 / n））+（（1 - （g2_1 ^ 2 + g2_2 ^ 2））*（ng2 / n）） 其中G是分裂點的基尼指數，g1_1是第1組中第1類實例的比例，第2類為g1_2，第2組為第2類，第2組為g2_2，第2組為第2，ng1和ng2為總數第1組和第2組中的實例和n是我們嘗試從父節點分組的實例總數。 ### 停止標準 上面描述的遞歸二進制分裂過程需要知道何時停止分裂，因為它沿著具有訓練數據的樹向下工作。 最常見的停止過程是對分配給每個葉節點的訓練實例的數量使用最小計數。如果計數小于某個最小值，則不接受拆分，并將該節點作為最終葉節點。 訓練成員的數量被調整到數據集，例如，它定義了樹將對訓練數據的具體程度。太具體（例如計數為1）并且樹將過度擬合訓練數據并且可能在測試集上具有差的表現。 ### 修剪樹 停止標準很重要，因為它會嚴重影響樹的表現。學習樹后可以使用[修剪](https://en.wikipedia.org/wiki/Pruning_(decision_trees))來進一步提升表現。 決策樹的復雜性定義為樹中的分裂數。更簡單的樹木是首選。它們易于理解（您可以將它們打印出來并向主題專家展示），并且它們不太可能過度填充您的數據。 最快和最簡單的修剪方法是遍歷樹中的每個葉節點，并使用保持測試集評估刪除它的效果。僅當葉節點導致整個測試集上的總成本函數下降時，才會刪除葉節點。如果無法進一步改進，則停止刪除節點。 可以使用更復雜的修剪方法，例如成本復雜性修剪（也稱為最弱鏈接修剪），其中使用學習參數（α）來權衡是否可以基于子樹的大小來移除節點。  決策樹的遞歸二進制拆分 照片由 [Paul L Dineen](https://www.flickr.com/photos/pauldineen/8527296947/) 拍攝，保留一些權利。 ## CART的數據準備 除了很好地表示問題之外，CART不需要任何特殊的數據準備。 ## 進一步閱讀 本節列出了一些資源，如果您希望深入了解CART，可以參考這些資源。 * [分類和回歸樹](http://www.amazon.com/dp/0412048418?tag=inspiredalgor-20) 下面是一些很好的機器學習文本，它們從機器學習的角度描述了CART算法。 * [統計學習簡介：在R](http://www.amazon.com/dp/1461471370?tag=inspiredalgor-20) 中的應用，第8章 * [Applied Predictive Modeling](http://www.amazon.com/dp/1461468485?tag=inspiredalgor-20) ，第8章和第14章 * [數據挖掘：實用機器學習工具和技術](http://www.amazon.com/dp/0123748569?tag=inspiredalgor-20)，第6章。 ## 摘要 在這篇文章中，您發現了用于機器學習的分類和回歸樹（CART）。你了解到： * 經典名稱決策樹和更現代的名稱CART算法。 * 用于CART的表示是二叉樹。 * 通過在給定新輸入記錄的情況下遍歷二叉樹，使用CART進行預測。 * 使用訓練數據上的貪婪算法來學習樹以選擇樹中的分裂。 * 停止標準定義了多少樹學習和修剪可用于改進學習樹。 您對CART或這篇文章有任何疑問嗎？ 在評論中提問，我會盡力回答。