https://www.ibm.com/developerworks/cn/analytics/library/machine-learning-hands-on5-cart-tree/index.html?ca=drs-

CART 樹簡介

在上一篇文章中，主要介紹了 ID3 和 C4.5 決策樹。它們利用信息增益和信息增益比劃分數據集。但是這兩種決策樹是有缺陷的，即按某特征劃分后，該特征將不會在后面的劃分中出現。這就導致了劃分過于迅速，從而影響分類結果。在這篇文章中將要介紹的 CART（Classification And Regression Tree）樹，即分類回歸樹利用二分策略，有效地避免了劃分過于迅速這一問題。而且二分策略可以直接處理連續型屬性值。

CART 樹（分類回歸樹）分為分類樹和回歸樹。顧名思義，分類樹用于處理分類問題；回歸樹用來處理回歸問題。我們知道分類和回歸是機器學習領域兩個重要的方向。分類問題輸出特征向量對應的分類結果，回歸問題輸出特征向量對應的預測值。

分類樹和 ID3、C4.5 決策樹相似，都用來處理分類問題。不同之處是劃分方法。分類樹利用基尼指數進行二分。如圖 1 所示就是一個分類樹。

圖 1. 分類樹示例

回歸樹用來處理回歸問題。回歸將已知數據進行擬合，對于目標變量未知的數據可以預測目標變量的值。如圖 2 所示就是一個回歸樹，其中 s 是切分點，x 是特征，y 是目標變量。可以看出圖 2 利用切分點 s 將特征空間進行劃分，y 是在劃分單元上的輸出值。回歸樹的關鍵是如何選擇切分點、如何利用切分點劃分數據集、如何預測 y 的取值。

圖 2. 回歸樹示例

CART 樹原理

分類樹

二分

分類樹利用二分劃分數據。將特征值等于切分點值的數據劃分為左子樹，將特征值不等于切分點值的數據劃分為右子樹。

基尼指數：同信息增益、信息增益比作用類似，不過基尼指數相對更快

假設有 N 個類，樣本屬于第 n 類的概率為 Pn,則基尼指數為：

若數據集按特征 A 取值是否等于切分點值劃分為 D1 和 D2 兩部分，則在特征 A 下，集合 D 的基尼指數為：

回歸樹

二分

回歸樹也利用二分劃分數據。與分類樹不同的是，回歸樹將特征值大于切分點值的數據劃分為左子樹，將特征值小于等于切分點值的數據劃分為右子樹。

平方誤差

不同于分類樹，回歸樹用平方誤差選擇切分點。若數據集按特征取值是否大于切分點值劃分為兩部分，則在特征 A 下，集合 D 的平方誤差為：

用 CART 樹進行分類和回歸

本節主要用示例數據詳細說明如何用 CART 樹進行分類和回歸。

分類樹

表 1. 示例數據集

圓的紅的分類

1	1	1
1	0	0
0	1	0
0	0	0
1	0	0

選擇最優特征

按特征"圓的" = 1 劃分數據集，則 Gini 為：

3/5 * Gini(D1) + 2/5 * Gini(D0)

= 3/5 * [1/3 * 2/3 + 2/3 * 1/3] + 2/5 * [0]

= 0.266

按特征"紅的" = 1 劃分數據集，則 Gini 為：

2/5 * Gini(D1) + 3/5 * Gini(D0)

= 2/5 * [1/2 * 1/2 + 1/2 * 1/2] + 3/5 * [0]

= 0.2

綜上所述，由于按特征"紅的"比特征"圓的"劃分的基尼指數小，所以特征"紅的" = 1 為切分點。

按最優特征劃分數據集

按特征"紅的"劃分數據集后，有兩種情況，第一種為如果是紅的:0,則分類:0; 第二種為如果是紅的:1, 則有如下數據子集 {圓的:1,分類：1; 圓的:0, 分類:0}

接下來需要對數據子集{圓的:1,分類：1; 圓的:0, 分類:0}繼續劃分。由于剩下一個特征，故按特征"圓的"劃分數據集。劃分后，如果是圓的:1，則分類:1；如果是圓的:0, 則分類:0。

返回的決策樹為：

{'紅的': {0: '類別 0', 1: {'圓的': {0: '類別 0', 1: '類別 1'}}}}

回歸樹

表 2. 示例數據集

面積/平米價格/萬

20	40.1
21	40.3
35	70.4
36	70.2

選擇最優特征

1.按特征"面積" = 20 劃分數據集，

y1 均值為 40.1，

y2 均值為(40.3 + 70.4 + 70.2) / 3 = 60.3,

則平方誤差為：

0 + （40.3 – 60.3）2?+ （70.4 – 60.3）2?+（70.2 – 60.3）2

= 600.02

2.按特征"面積" = 21 劃分數據集，則平方誤差為：

y1 均值為(40.1 + 40.3)/ 2 = 40.2，

y2 均值為(70.4 + 70.2) / 2 = 70.3,

則平方誤差為：

（40.1 –40.2）2?+ （40.3 –40.2）2?+ （70.4 –70.3）2?+（70.2 –70.3）2

= 0.04

3.按特征"面積" = 35 劃分數據集，則平方誤差為：

y1 均值為(40.1 + 40.3 + 70.4) / 3 = 50.27，

y2 均值為 70.2,

則平方誤差為：

（40.1 –50.27）2?+ （40.3 –50.27）2?+（70.4 –50.27）2?+ 0

= 608.05

綜上所述，由于按特征"面積" = 21 比特征"面積" = 20、"面積" = 35 劃分的平方誤差小，所以特征"面積" = 21 為切分點。

按最優特征劃分數據集

以特征"面積" = 21 為切分點，將數據切分為{面積 = 20,價格 = 40.1; 面積 = 21, 價格 = 40.3}， {面積 = 35,價格 = 70.4; 面積 = 36, 價格 = 70.2}兩個子集。

其中子集{面積 = 20,價格 = 40.1; 面積 = 21, 價格 = 40.3}的目標變量非常接近，故不繼續劃分，得葉節點值(40.1 + 40.3) / 2 = 40.2； 同理得子集{面積 = 35,價格 = 70.4; 面積 = 36, 價格 = 70.2}的葉節點值為 (70.4 + 70.2) / 2 = 70.3。

實現步驟: 自己動手實現 CART 樹

本節將介紹分類樹和回歸樹的代碼實現細節。兩者都是二分類劃分數據。分類樹利用基尼指數選擇最優特征和最優特征對應的劃分屬性值。回歸樹利用平方誤差選擇最優特征和最優特征對應的劃分屬性值。

分類樹

讀者應該還記得上篇介紹的 ID3 和 C4.5 決策樹，它們利用信息增益和信息增益比劃分數據，且創建出來的樹可以有任意多的分支數，分支數取決于特征值的多少。本節介紹的分類樹與前兩種決策樹不同之處在于，它是二分類，即創建出來的樹最多只有兩個分支，而且是利用基尼指數劃分數據。分類回歸樹分為兩種樹，分類樹和回歸樹。本節先介紹分類樹，回歸樹會在下一小節繼續介紹。

清單 1. 計算基尼指數

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

def calcGini(dataSet): ????totalNum = shape(dataSet)[0] ????labelNum = {} ????gini = 0 ????for data in dataSet: ????????label = data[-1] ????????if label in labelNum: ????????????labelNum[label] += 1 ????????else: ????????????labelNum[label] = 1 ????for key in labelNum: ????????p = labelNum[key] / totalNum ????????gini += p * (1 - p) ????return gini

清單 1 介紹了基尼指數的實現代碼。基尼指數的計算過程詳見本文第二節內容。

清單 2. 選擇最優特征

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

def chooseBestFeatVal2Split(dataSet): ????#如果沒有可劃分的特征或所有目標變量相等，停止 ????if(len(dataSet[0]) == 1): return None, None ????if(len(set([d[-1] for d in dataSet])) == 1): return None, None ????bestFeature = 0 ????bestValue = 0 ????lowestGini = 100000 ????totalGini = calcGini(dataSet) ????totalNum = shape(dataSet)[0] ????for feature in range(shape(dataSet)[1] - 1): ????????allValues = [d[feature] for d in dataSet] ????????values = set(allValues) ????????for value in values: ????????????leftChild, rightChild = splitByFeatVal(feature, value, dataSet) ????????????if(shape(leftChild)[0] == 0 or shape(rightChild)[0] == 0): continue ????????????leftNum = shape(leftChild)[0] ????????????rightNum = shape(rightChild)[0] ????????????curGini = leftNum / totalNum * calcGini(leftChild) + \ ??????????????????????rightNum / totalNum * calcGini(rightChild) ????????????if(curGini < lowestGini): ????????????????bestFeature = feature ????????????????bestValue = value ????????????????lowestGini = curGini ????#如果 gini 減少很小，停止 ????if(totalGini - lowestGini < 0.00001): return None, None ????return bestFeature, bestValue

清單 2 介紹了分類樹選擇最優特征的過程。對所有特征及特征下的所有屬性值，計算按其劃分的子數據集的基尼指數，選擇最小的基尼指數對應的特征和屬性值為最優特征及最優特征對應的最優屬性。注意分類樹的結束條件。如果沒有可以劃分的特征或者所有目標變量都相等，則停止繼續劃分數據集；如果基尼指數減小很少，也停止繼續劃分數據集。

清單 3. 按特征劃分數據集

1 2 3 4 5 6 7

def splitByFeatVal(feature, value, dataSet): ????#左子樹的值大于根節點的值 ????dataSet = mat(dataSet) ????leftChild = dataSet[nonzero(dataSet[:,feature] == value)[0], :].tolist() ????#右子樹的值小于等于根節點的值 ????rightChild = dataSet[nonzero(dataSet[:,feature] != value)[0], :].tolist()??????????????????? ????return leftChild, rightChild

清單 3 用來給分類樹劃分數據集。如果 feature 對應的屬性值等于 value 值，則將該條數據劃分到左子樹；如果 feature 對應的屬性值不等于 value 值，則將該條數據劃分到右子樹。

清單 4. 結束條件

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

def checkIsOneCateg(newDataSet): ????flag = False ????categoryList = [data[-1] for data in newDataSet] ????category = set(categoryList) ????if(len(category) == 1): ????????flag = True ????return flag def majorityCateg(newDataSet): ????categCount = {} ????categList = [data[-1] for data in newDataSet] ????for c in categList: ????????if c not in categCount: ????????????categCount[c] = 1 ????????else: ????????????categCount[c] += 1 ????sortedCateg = sorted(categCount.items(), key = lambda x:x[1], reverse = True) ????return sortedCateg[0][0]

清單 4 介紹了分類樹用來結束的條件。checkIsOneCateg 函數用來判斷數據集的目標變量是否為一個分類結果。majorityCateg 函數用來選出目標變量中的大多數值作為輸出變量。

清單 5. 創建分類樹

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

def createClassifTree(dataSet): ????feature, value = chooseBestFeatVal2Split(dataSet) ????#如果無法分割，那么返回葉節點的值。如果業界點鐘所有目標變量相同則為此值，不同則為多數值 ????if feature == None and checkIsOneCateg(dataSet): ????????return dataSet[0][-1] ????if feature == None and not checkIsOneCateg(dataSet): ????????return majorityCateg(dataSet) ????#如果可以繼續分割，那么繼續創建新的子樹 ????classifTree = {} ????classifTree['featIndex'] = feature ????classifTree['value'] = value ????leftChild, rightChild = splitByFeatVal(feature, value, dataSet) ????classifTree['leftChild'] = createClassifTree(leftChild) ????classifTree['rightChild'] = createClassifTree(rightChild)??????????????????? ????return classifTree

清單 5 用來創建分類樹。首先判斷是否可以繼續分割。如果無法分割，則出現葉節點。若所有目標變量值相同，則葉節點值就是此目標變量的值；否則，選出大多數值作為葉節點的值。如果可以繼續分割，則創建子樹 classifTree。這是一個 python 中的字典結構，存儲四個鍵值對。featIndex 存儲特征的下標，value1 存儲特征的值；leftChild 存儲左子樹；rightChild 存儲右子樹。對左右子樹繼續遞歸調用 createClassifTree 函數，直到達到結束條件為止。

回歸樹

回歸樹與分類樹的不同之處體現在選擇最優特征的方法、劃分數據集的方法、葉節點取值的方法上。

清單 6. 計算平方誤差

1 2 3

def calcErr(dataSetMat): ????error = var(dataSetMat[:,-1]) * shape(dataSetMat)[0] ????return error

清單 6 介紹了平方誤差的計算方法。具體方法詳見本文第二節內容。

清單 7. 選擇最優特征

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

def chooseBestFeatVal2Split(dataSetMat): ????#如果所有目標變量相等，停止 ????if(len(set(dataSetMat[:,-1].T.tolist()[0])) == 1): return None, None ????bestFeature = 0 ????bestValue = 0 ????lowestErr = 100000 ????totalErr = calcErr(dataSetMat) ????for feature in range(shape(dataSetMat)[1] - 1): ????????allValues = [d[feature] for d in dataSetMat.tolist()] ????????values = set(allValues) ????????for value in values: ????????????leftChild, rightChild = splitByFeatVal(feature, value, dataSetMat) ????????????if(shape(leftChild)[0] == 0 or shape(rightChild)[0] == 0): continue ????????????curErr = calcErr(leftChild) + calcErr(rightChild) ????????????if(curErr < lowestErr): ????????????????bestFeature = feature ????????????????bestValue = value ????????????????lowestErr = curErr ????#如果誤差減少很小，停止 ????if(totalErr - lowestErr < 1): return None, None ????return bestFeature, bestValue

清單 7 用來為回歸樹選擇最優特征。對每個特征的每個屬性值，計算按該屬性值二分后的兩個子數據集的平方誤差和，選擇平方誤差和最小的特征作為最優特征。除了用平方誤差代替基尼指數之外，其他過程和分類樹基本相同。

清單 8. 按特征劃分數據集

1 2 3 4 5 6

def splitByFeatVal(feature, value, dataSetMat): ????#左子樹的值大于根節點的值 ????leftChild = dataSetMat[nonzero(dataSetMat[:,feature] > value)[0], :] ????#右子樹的值小于等于根節點的值 ????rightChild = dataSetMat[nonzero(dataSetMat[:,feature] <= value)[0], :]??????????????????? ????return leftChild, rightChild

清單 8 介紹了回歸樹劃分數據集的方法。與分類樹不同的是，回歸樹將 feature 屬性值大于 value 的數據歸入 leftChild 左子樹，將 feature 屬性值小于等于 value 的數據歸入 rightChild 右子樹。

清單 9. 創建回歸樹

1 2 3 4 5 6 7 8 9 10 11 12

def createRegTree(dataSetMat): ????feature, value = chooseBestFeatVal2Split(dataSetMat) ????#如果無法分割，那么返回葉節點的值，即所有 dataSetMat 的均值 ????if feature == None: return mean(dataSetMat[:,-1]) ????#如果可以繼續分割，那么繼續創建新的子樹 ????regTree = {} ????regTree['featIndex'] = feature ????regTree['value'] = value ????leftChild, rightChild = splitByFeatVal(feature, value, dataSetMat) ????regTree['leftChild'] = createRegTree(leftChild) ????regTree['rightChild'] = createRegTree(rightChild)??????????????????? ????return regTree

清單 9 是創建回歸樹的代碼。與分類樹不同之處在于，如果無法繼續劃分數據集，那么返回子數據集的所有目標變量的均值作為葉節點的值。其他部分和分類樹基本相同。

代碼下載

本文所有 CART 樹實現代碼可在文末下載。

本文數據集簡介

圖 3. 分類樹數據集樣例

數據集有 9 條數據。其中第一列數據代表顏色，取值范圍是 0,1,2。其中 0 代表青色，1 代表紅色，2 代表黃色。第二列數據代表形狀，取值范圍是 0,1,2。其中 0 代表扁的，1 代表圓的，2 代表橢圓的。第三列代表分類，取值范圍是 0,1。其中 0 代表不是蘋果，1 代表是蘋果。

圖 4. 回歸樹數據集樣例

數據集共 25 條數據。第一列數據代表房子的評價得分，此數據集中所有數據的評價得分都是 5.23。第二列數據代表房子的平方數，第三列數據代表房子的價格，以萬為單位。

應用示例: 應用實現的 CART 樹解決實際問題

清單 10. 用分類樹解決實際問題

1 2 3 4

if __name__ == '__main__': ????dataSet, labels = loadDataSet() ????classifTree = createClassifTree(dataSet) ????print(classifTree)

清單 10 列出調用分類樹進行建模的代碼。

運行結果：

{'value': 1, 'featIndex': 0, 'leftChild': 1, 'rightChild': {'value': 1, 'featIndex': 1, 'leftChild': 1, 'rightChild': 0}}

運行結果中的樹用 python 中的字典結構表示。featIndex 表示 feature 的下標，其中 feature 指顏色和形狀。value 指 feature 的取值，取值范圍是 0, 1, 2。leftChid 表示左子樹，左子樹是等于父節點值的子集合數據。rightChild 表示右子樹，右子樹是不等于父節點值的子集合數據。如果左子樹和右子樹是葉節點，則葉節點的值就是最終的分類結果。其中葉節點的取值范圍是 0 和 1。0 代表是蘋果，1 代表不是蘋果。運行結果含義為：如果顏色是紅的，則是蘋果；如果顏色不是紅的，但形狀是圓的，則是蘋果；如果顏色不是紅的，且形狀不是圓的，則不是蘋果。該運行結果與圖 1 所示分類樹相同。

清單 11. 用回歸樹解決實際問題

1 2 3 4

if __name__ == '__main__': ????dataSetMat = loadDataSet() ????regTree = createRegTree(dataSetMat) ????print(regTree)

清單 11 列出了調用回歸樹進行建模的代碼。

運行結果：

{'featIndex': 1, 'value': 10.0, 'rightChild': {'featIndex': 1, 'value': 5.0, 'rightChild': 0.078, 'leftChild': 5.0700000000000003}, 'leftChild': {'featIndex': 1, 'value': 20.0, 'rightChild': {'featIndex': 1, 'value': 15.0, 'rightChild': 10.27, 'leftChild': 15.266}, 'leftChild': 20.268000000000001}}

運行結果中的樹同樣用 python 中的字典結構表示。featIndex 和 value 的含義和分類樹中的相同。在回歸樹中，leftChild 代表的左子樹的值比父節點值大，rightChild 代表的右節點的值小于等于父節點值。運行結果含義是：第一個特征的值小于 5.0 時，目標變量為 0.078；第一個特征的值大于 5.0 且小于 10.0 時，目標變量為 5.07；第一個特征的值大于 15.0 且小于 20.0 時，目標變量為 15.266；第一個特征的值大于 10.0 且小于 15.0 時，目標變量為 10.27；第一個特征的值大于 20.0 時，目標變量為 20.268。該運行結果與圖 2 所示回歸樹相同。

總結

本文首先介紹了分類回歸樹及預剪枝、后剪枝的概念，接著從二分、基尼指數、平方誤差等入手詳細深入地講解了 CART 樹的原理。接著用例子介紹分類樹與回歸樹的算法過程。然后通過代碼樣例，介紹了自己動手實現分類樹與回歸樹的思路。最后，利用數據展示了如何應用 CART 樹解決實際問題。通過上面介紹，讀者已經知道回歸樹用來進行分段回歸，每段輸出的目標變量為該段所有目標變量的均值。這種方法簡單易實現，但是也有局限。如果每段的目標變量并非一個常數，而是一個線性模型，用回歸樹擬合就會造成誤差過大的后果。這時，就需要考慮模型樹。同回歸樹一樣，模型樹也是對特征空間進行劃分，但在每個劃分內部建立線性模型，而非一個常數。關于模型樹的詳細介紹請參考下方所列文獻。由于分類回歸樹對特征空間不斷劃分，這很容易造成過擬合的問題。處理過擬合不僅需要預剪枝，還需要后剪枝。預剪枝是在建立模型階段通過制定終止條件來提早完成劃分。后剪枝則是在模型建立后，利用測試數據計算剪除部分葉節點是否會造成模型誤差減少，如果是，則剪除對應的葉節點。當然，后剪枝時不僅要考慮誤差是否減少，還需考慮正則項，即模型的大小。最后綜合選擇模型誤差較小且模型簡單的分類回歸樹。由于篇幅有限，對后剪枝感興趣的讀者請參考下文所列文獻。

參考資源

本文用到的參考文獻如下：

• 參考李航著《統計學習方法》，了解后剪枝概念。
• 參考 Peter Harrington 著《機器學習實戰》，了解 CART 樹代碼框架及模型樹概念。

轉載于:https://www.cnblogs.com/davidwang456/articles/8927019.html

總結

以上是生活随笔為你收集整理的机器学习系列之手把手教你实现一个分类回归树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。