上一篇介紹了決策樹之分類樹構造的幾種方法，本文主要介紹使用CART算法構建迴歸樹及剪枝算法實現。主要包括以下內容：
1、CART迴歸樹的介紹
2、二元切分的實現
3、總方差法劃分特徵
4、迴歸樹的構建
5、迴歸樹的測試與應用
6、剪枝算法
一、CART迴歸樹的介紹
迴歸樹與分類樹比較類似，不同的是分類樹最後的決策的結果是離散型的值，迴歸樹決策的結果是輸出一個實數。
二、二元切分的實現
CART算法做迴歸樹時，只做二元切分，最後生成的樹是一棵二叉樹。切分代碼如下:
1 def bin_split_data_set(data_set, feature, value): 2 """對數據集進行二元切分""" 3 # np.nonzero(data_set[:,feature] > value)[0] 返回feture值 大於 value 的行號 4 mat0 = data_set[np.nonzero(data_set[:, feature] == value)[0], :] 5 mat1 = data_set[np.nonzero(data_set[:, feature] != value)[0], :] 6 return mat0, mat1
由於使用的數據集特徵是枚舉類型的，所以這裏條件是 【等於】 np.nonzero(data_set[:, feature] == value，假如爲連續數值型的，可以使用【小於】或【大於】
三、總方差法劃分特徵
上一節講到分類樹有三種常用劃分特徵的方法，分別是信息增益，增益率，和基尼指數。CART迴歸樹這裏使用最小總方差法選取劃分特徵。
1 def reg_leaf(data_set): 2 """生成葉子結點""" 3 # 計算平均值 4 result = tools.filter_reg_values(data_set) 5 value = np.mean(result) 6 return value 7 8 9 def reg_err(data_set): 10 """總方差""" 11 # np.val 計算標準差 12 result = tools.filter_reg_values(data_set) 13 return np.var(result) * np.shape(data_set)[0] 14 15 def choose_best_split(data_set, ops=(1, 4)): 16 """ 17 選取最好的劃分特徵值 18 data_set:數據集 19 ops(x,y):x--誤差減少最小值 y--分類後樣本最少個數 20 """ 21 tols = ops[0] 22 toln = ops[1] 23 24 # 所有分類相同（mat.flatten() 將矩陣數據壓平） 25 if len(set(np.array(data_set[:, -1].flatten()[0])[0])) == 1: 26 return None, reg_leaf(data_set) 27 28 m, n = np.shape(data_set) 29 s = reg_err(data_set) 30 31 # np.inf 無限大的數 32 best_s = np.inf 33 best_index = 0 34 best_value = 0 35 36 # 遍歷每一個特徵 37 for feat_index in range(n - 1): 38 # 遍歷當前特徵的所有值 39 for value in set(flatten(np.array(data_set)[:, feat_index])): 40 mat0, mat1 = bin_split_data_set(data_set, feat_index, value) 41 # 分類後樣本個數較少，則退出本次循環 42 if np.shape(mat0)[0] < toln or np.shape(mat1)[0] < toln: 43 continue 44 # 計算新的誤差 45 new_s = reg_err(mat0) + reg_err(mat1) 46 47 # 更新最小誤差 48 if new_s < best_s: 49 best_index = feat_index 50 best_value = value 51 best_s = new_s 52 53 # 如果誤差減小不大，則退出 54 if s - best_s < tols: 55 return None, reg_leaf(data_set) 56 57 # 如果切片分出的數據集很小，就退出 58 mat0, mat1 = bin_split_data_set(data_set, best_index, best_value) 59 if mat0.shape[0] < toln or mat1.shape[0] < toln: 60 return None, reg_leaf(data_set) 61 62 return best_index, best_value
四、迴歸樹的構建
遞歸創建樹形結構：
1 def create_tree(data_set, ops=(1, 4)): 2 """創建迴歸樹""" 3 feat, val = choose_best_split(data_set, ops) 4 if feat is None: 5 return val 6 ret_tree = dict() 7 ret_tree['feature'] = feat 8 ret_tree['value'] = val 9 10 # 左右子樹 11 left_data, right_data = bin_split_data_set(data_set, feat, val) 12 ret_tree['left'] = create_tree(left_data, ops) 13 ret_tree['right'] = create_tree(right_data, ops) 14 15 return ret_tree
五、迴歸樹的測試與應用
選取UCI上面的用於迴歸的數據集，分爲訓練集 和 測試集。
生成的迴歸決策樹圖形如下:
六、決策樹的修剪：
決策樹在構造之後，可能會出現過度擬合的現象，決策樹的複雜度過大，預測效果並不理想，所以需要對決策樹進行剪枝。剪枝就是將決策樹的枝葉適當減去，使決策樹更加精簡，預測效果更加準確。根據剪枝所出現的時間點不同，分爲預剪枝和後剪枝。預剪枝是在決策樹的生成過程中進行的；後剪枝是在決策樹生成之後進行的。
預剪枝：
在構造決策樹的同時進行剪枝。爲了避免過擬合，可以設定一個閾值，如決策樹的高度等，使構造的決策樹不能大於此閾值，由於事先定好閾值，這種方法實際中的效果並不好。決策樹構造完成後進行剪枝。剪枝的過程是對擁有同樣父節點的一組節點進行檢查，判斷如果將其合併，熵的增加量是否小於某一閾值。如果確實小，則這一組節點可以合併一個節點，其中包含了所有可能的結果。
後剪枝：
後剪枝的剪枝過程是刪除一些子樹，然後用其葉子節點代替，這個葉子節點所標識的類別通過大多數原則確定。所謂大多數原則，是指剪枝過程中, 將一些子樹刪除而用葉節點代替,這個葉節點所標識的類別用這棵子樹中大多數訓練樣本所屬的類別來標識。
後剪枝算法
後剪枝算法有很多種，這裏簡要介紹兩種：
Reduced-Error Pruning (REP,錯誤率降低剪枝）
用訓練樣本構造的決策樹可能過度擬合，所以再用測試數據集去修正。對於完全決策樹中的每一個非葉子節點的子樹，我們嘗試着把它替換成一個葉子節點，該葉子節點的類別我們用子樹所覆蓋訓練樣本中存在最多的那個類來代替，這樣就產生了一個簡化決策樹，然後比較這兩個決策樹在測試數據集中的表現，如果簡化決策樹在測試數據集中的錯誤比較少，那麼該子樹就可以替換成葉子節點，如果。
Pessimistic Error Pruning (PEP，悲觀剪枝）
PEP剪枝算法是在C4.5決策樹算法中提出的， 把一顆子樹（具有多個葉子節點）用一個葉子節點來替代的話，比起REP剪枝法，它不需要一個單獨的測試數據集。
REP剪枝算法的代碼：
1 def is_tree(obj): 2 """判斷是否是樹""" 3 return isinstance(obj, dict) 4 5 6 def get_mean(tree): 7 """返回樹的平均值""" 8 if is_tree(tree['right']): 9 tree['right'] = get_mean(tree['right']) 10 if is_tree(tree['left']): 11 tree['left'] = get_mean(tree['left']) 12 13 value = (tree['left'] + tree['right']) / 2.0 14 return float('%.2f' % value) 15 16 17 def prune(tree, test_data): 18 """對樹進行剪枝""" 19 # 測試數據爲空 20 if np.shape(test_data)[0] == 0: 21 return get_mean(tree) 22 23 # 切分測試數據 24 if is_tree(tree['left']) or is_tree(tree['right']): 25 l_set, r_set = tools.bin_split_data_set(test_data, tree['feature'], tree['value']) 26 27 # 遞歸對左右子樹進行剪枝 28 if is_tree(tree['left']): 29 tree['left'] = prune(tree['left'], l_set) 30 if is_tree(tree['right']): 31 tree['right'] = prune(tree['right'], r_set) 32 33 # 左右都爲葉子結點 34 if not is_tree(tree['left']) and not is_tree(tree['right']): 35 l_set, r_set = tools.bin_split_data_set(test_data, tree['feature'], tree['value']) 36 37 # 未合併的誤差 38 error_no_merge = sum(tools.filter_reg_values(l_set) - tree['left'], 2) + sum( 39 np.power(tools.filter_reg_values(r_set) - float(tree['right']), 2)) 40 # 合併左右結點之後的誤差 41 tree_mean = (tree['left'] + tree['right']) / 2.0 42 error_merge = sum(np.power(tools.filter_reg_values(test_data) - tree_mean, 2)) 43 44 # 如果合併後誤差減小，則進行合併 45 if error_merge < error_no_merge: 46 print('merging') 47 return float('%.2f' % tree_mean) 48 else: 49 return tree 50 else: 51 return tree
剪枝後生成的決策樹如下：
對比剪枝前和剪枝後的決策樹，剪枝後的決策樹更加精簡，相應的準確率也更高。
本文的完整代碼見https://gitee.com/beiyan/machine_learning/tree/master/decision_tree
本文只是簡單實現CART迴歸樹及剪枝算法，隨着決策樹的研究，也出現很多改進的或者新的劃分算法和剪枝算法，後面慢慢學習。