如何在Python中從頭開始實現決策樹算法 · Machine Learning Mastery 博客文章翻譯

# 如何在Python中從頭開始實現決策樹算法 > 原文： [https://machinelearningmastery.com/implement-decision-tree-algorithm-scratch-python/](https://machinelearningmastery.com/implement-decision-tree-algorithm-scratch-python/) 決策樹是一種強大的預測方法，非常受歡迎。它們很受歡迎，因為最終模型很容易被從業者和領域專家所理解。最終決策樹可以準確解釋為什么進行特定預測，使其對操作使用非常有吸引力。決策樹還為更先進的集合方法提供了基礎，例如裝袋，隨機森林和梯度增強。在本教程中，您將了解如何使用Python從頭開始實現[分類和回歸樹算法](http://machinelearningmastery.com/classification-and-regression-trees-for-machine-learning/)。完成本教程后，您將了解： * 如何計算和評估數據中的候選分裂點。 * 如何安排拆分為決策樹結構。 * 如何將分類和回歸樹算法應用于實際問題。讓我們開始吧。 * **2017年1月更新**：將cross_validation_split（）中的fold_size計算更改為始終為整數。修復了Python 3的問題。 * **2017年2月更新**：修復了build_tree中的錯誤。 * **2017年8月更新**：修正了基尼計算中的一個錯誤，根據組大小添加了組基尼評分缺失的權重（感謝邁克爾！）。 * **更新Aug / 2018** ：經過測試和更新，可與Python 3.6配合使用。 ![How To Implement The Decision Tree Algorithm From Scratch In Python](img/6ae5db916a10295dfba3cc0aaba924b8.jpg) 如何在Python中從頭開始實施決策樹算法 [Martin Cathrae](https://www.flickr.com/photos/suckamc/4325870801/) 的照片，保留一些權利。 ## 說明本節簡要介紹了本教程中使用的分類和回歸樹算法以及Banknote數據集。 ### 分類和回歸樹分類和回歸樹或簡稱CART是Leo Breiman引用的首字母縮略詞，用于指代可用于分類或回歸預測建模問題的決策樹算法。我們將在本教程中專注于使用CART進行分類。 CART模型的表示是二叉樹。這是來自算法和數據結構的相同二叉樹，沒什么太花哨的（每個節點可以有零個，一個或兩個子節點）。假設變量是數字，節點表示單個輸入變量（X）和該變量上的分割點。樹的葉節點（也稱為終端節點）包含用于進行預測的輸出變量（y）。一旦創建，就可以使用拆分在每個分支之后使用新的數據行來導航樹，直到進行最終預測。創建二元決策樹實際上是劃分輸入空間的過程。貪婪的方法用于劃分稱為遞歸二進制分裂的空間。這是一個數值程序，其中所有值都排成一行，并使用成本函數嘗試和測試不同的分裂點。選擇具有最佳成本（最低成本，因為我們最小化成本）的分割。基于成本函數，以貪婪的方式評估和選擇所有輸入變量和所有可能的分裂點。 * **回歸**：為選擇分割點而最小化的成本函數是落在矩形內的所有訓練樣本的總和平方誤差。 * **分類**：使用基尼成本函數，其表示節點的純度，其中節點純度是指分配給每個節點的訓練數據的混合程度。拆分繼續，直到節點包含最少數量的訓練示例或達到最大樹深度。 ### 鈔票數據集鈔票數據集涉及根據從照片中采取的若干措施來預測給定鈔票是否是真實的。數據集包含1,372行，包含5個數字變量。這是兩個類的分類問題（二元分類）。下面提供了數據集中五個變量的列表。 1. 小波變換圖像的方差（連續）。 2. 小波變換圖像的偏度（連續）。 3. 小波峰度變換圖像（連續）。 4. 圖像熵（連續）。 5. class（整數）。下面是數據集的前5行的示例 ```py 3.6216,8.6661,-2.8073,-0.44699,0 4.5459,8.1674,-2.4586,-1.4621,0 3.866,-2.6383,1.9242,0.10645,0 3.4566,9.5228,-4.0112,-3.5944,0 0.32924,-4.4552,4.5718,-0.9888,0 4.3684,9.6718,-3.9606,-3.1625,0 ``` 使用零規則算法預測最常見的類值，問題的基線準確率約為50％。您可以從 [UCI機器學習庫](http://archive.ics.uci.edu/ml/datasets/banknote+authentication)了解更多信息并下載數據集。下載數據集并將其放在當前工作目錄中，文件名為 **data_banknote_authentication.csv** 。 ## 教程本教程分為5個部分： 1. 基尼指數。 2. 創建拆分。 3. 建樹。 4. 做一個預測。 5. 鈔票案例研究。這些步驟將為您提供從頭開始實施CART算法所需的基礎，并將其應用于您自己的預測建模問題。 ### 基尼系數 Gini索引是用于評估數據集中拆分的成本函數的名稱。數據集中的拆分涉及一個輸入屬性和該屬性的一個值。它可用于將訓練模式劃分為兩組行。基尼分數通過分割創建的兩個組中的類的混合程度，可以了解分割的好壞程度。完美分離導致基尼評分為0，而最差情況分裂導致每組50/50分類導致基尼評分為0.5（對于2類問題）。通過示例可以最好地演示計算基尼系數。我們有兩組數據，每組有2行。第一組中的行都屬于類0，第二組中的行屬于類1，因此它是完美的分割。我們首先需要計算每組中班級的比例。 ```py proportion = count(class_value) / count(rows) ``` 這個例子的比例是： ```py group_1_class_0 = 2 / 2 = 1 group_1_class_1 = 0 / 2 = 0 group_2_class_0 = 0 / 2 = 0 group_2_class_1 = 2 / 2 = 1 ``` 然后為每個子節點計算Gini，如下所示： ```py gini_index = sum(proportion * (1.0 - proportion)) gini_index = 1.0 - sum(proportion * proportion) ``` 然后，必須根據組的大小，相對于父組中的所有樣本，對每組的基尼系數進行加權。當前正在分組的所有樣本。我們可以將此權重添加到組的Gini計算中，如下所示： ```py gini_index = (1.0 - sum(proportion * proportion)) * (group_size/total_samples) ``` 在此示例中，每組的基尼評分計算如下： ```py Gini(group_1) = (1 - (1*1 + 0*0)) * 2/4 Gini(group_1) = 0.0 * 0.5 Gini(group_1) = 0.0 Gini(group_2) = (1 - (0*0 + 1*1)) * 2/4 Gini(group_2) = 0.0 * 0.5 Gini(group_2) = 0.0 ``` 然后在分割點處的每個子節點上添加分數，以給出可以與其他候選分割點進行比較的分割點的最終基尼分數。然后，此分裂點的基尼計算為0.0 + 0.0或完美基尼得分為0.0。下面是一個名為 **gini_index（）**的函數，它計算組列表的Gini索引和已知類值的列表。你可以看到那里有一些安全檢查，以避免空組的除以零。 ```py # Calculate the Gini index for a split dataset def gini_index(groups, classes): # count all samples at split point n_instances = float(sum([len(group) for group in groups])) # sum weighted Gini index for each group gini = 0.0 for group in groups: size = float(len(group)) # avoid divide by zero if size == 0: continue score = 0.0 # score the group based on the score for each class for class_val in classes: p = [row[-1] for row in group].count(class_val) / size score += p * p # weight the group score by its relative size gini += (1.0 - score) * (size / n_instances) return gini ``` 我們可以使用上面的工作示例測試此函數。我們還可以測試每組中50/50分裂的最壞情況。下面列出了完整的示例。 ```py # Calculate the Gini index for a split dataset def gini_index(groups, classes): # count all samples at split point n_instances = float(sum([len(group) for group in groups])) # sum weighted Gini index for each group gini = 0.0 for group in groups: size = float(len(group)) # avoid divide by zero if size == 0: continue score = 0.0 # score the group based on the score for each class for class_val in classes: p = [row[-1] for row in group].count(class_val) / size score += p * p # weight the group score by its relative size gini += (1.0 - score) * (size / n_instances) return gini # test Gini values print(gini_index([[[1, 1], [1, 0]], [[1, 1], [1, 0]]], [0, 1])) print(gini_index([[[1, 0], [1, 0]], [[1, 1], [1, 1]]], [0, 1])) ``` 運行該示例打印兩個Gini分數，首先是最差情況的分數為0.5，然后是最佳情況的分數為0.0。 ```py 0.5 0.0 ``` 現在我們知道如何評估拆分的結果，讓我們看一下創建拆分。 ### 2.創建拆分拆分由數據集中的屬性和值組成。我們可以將其概括為要拆分的屬性的索引以及在該屬性上拆分行的值。這只是索引數據行的有用簡寫。創建拆分涉及三個部分，第一部分我們已經看過計算基尼評分。剩下的兩部分是： 1. 拆分數據集。 2. 評估所有拆分。我們來看看每一個。 #### 2.1。拆分數據集拆分數據集意味著在給定屬性索引和該屬性的拆分值的情況下將數據集分成兩個行列表。一旦我們擁有這兩個組，我們就可以使用上面的Gini評分來評估拆分的成本。拆分數據集涉及迭代每一行，檢查屬性值是低于還是高于拆分值，并分別將其分配給左側或右側組。下面是一個名為 **test_split（）**的函數，它實現了這個過程。 ```py # Split a dataset based on an attribute and an attribute value def test_split(index, value, dataset): left, right = list(), list() for row in dataset: if row[index] < value: left.append(row) else: right.append(row) return left, right ``` 不是很多。請注意，右側組包含索引值大于或等于拆分值的所有行。 #### 2.2。評估所有拆分通過上面的Gini函數和測試分割函數，我們現在擁有評估分割所需的一切。給定一個數據集，我們必須檢查每個屬性的每個值作為候選分割，評估分割的成本并找到我們可以做出的最佳分割。找到最佳拆分后，我們可以將其用作決策樹中的節點。這是一個詳盡而貪婪的算法。我們將使用字典來表示決策樹中的節點，因為我們可以按名稱存儲數據。當選擇最佳分割并將其用作樹的新節點時，我們將存儲所選屬性的索引，要分割的屬性的值以及由所選分割點分割的兩組數據。每組數據都是其自己的小數據集，只有那些通過拆分過程分配給左或右組的行。您可以想象我們如何在構建決策樹時遞歸地再次拆分每個組。下面是一個名為 **get_split（）**的函數，它實現了這個過程。您可以看到它迭代每個屬性（類值除外），然后遍歷該屬性的每個值，分割和評估拆分。記錄最佳分割，然后在所有檢查完成后返回。 ```py # Select the best split point for a dataset def get_split(dataset): class_values = list(set(row[-1] for row in dataset)) b_index, b_value, b_score, b_groups = 999, 999, 999, None for index in range(len(dataset[0])-1): for row in dataset: groups = test_split(index, row[index], dataset) gini = gini_index(groups, class_values) if gini < b_score: b_index, b_value, b_score, b_groups = index, row[index], gini, groups return {'index':b_index, 'value':b_value, 'groups':b_groups} ``` 我們可以設計一個小數據集來測試這個函數和我們的整個數據集拆分過程。 ```py X1 X2 Y 2.771244718 1.784783929 0 1.728571309 1.169761413 0 3.678319846 2.81281357 0 3.961043357 2.61995032 0 2.999208922 2.209014212 0 7.497545867 3.162953546 1 9.00220326 3.339047188 1 7.444542326 0.476683375 1 10.12493903 3.234550982 1 6.642287351 3.319983761 1 ``` 我們可以為每個類使用單獨的顏色繪制此數據集。您可以看到，手動選擇X1的值（圖中的x軸）來分割此數據集并不困難。 ![CART Contrived Dataset](img/dd963418a62770e69fbbf7d35b673dda.jpg) CART Contrived Dataset 下面的例子將所有這些放在一起。 ```py # Split a dataset based on an attribute and an attribute value def test_split(index, value, dataset): left, right = list(), list() for row in dataset: if row[index] < value: left.append(row) else: right.append(row) return left, right # Calculate the Gini index for a split dataset def gini_index(groups, classes): # count all samples at split point n_instances = float(sum([len(group) for group in groups])) # sum weighted Gini index for each group gini = 0.0 for group in groups: size = float(len(group)) # avoid divide by zero if size == 0: continue score = 0.0 # score the group based on the score for each class for class_val in classes: p = [row[-1] for row in group].count(class_val) / size score += p * p # weight the group score by its relative size gini += (1.0 - score) * (size / n_instances) return gini # Select the best split point for a dataset def get_split(dataset): class_values = list(set(row[-1] for row in dataset)) b_index, b_value, b_score, b_groups = 999, 999, 999, None for index in range(len(dataset[0])-1): for row in dataset: groups = test_split(index, row[index], dataset) gini = gini_index(groups, class_values) print('X%d < %.3f Gini=%.3f' % ((index+1), row[index], gini)) if gini < b_score: b_index, b_value, b_score, b_groups = index, row[index], gini, groups return {'index':b_index, 'value':b_value, 'groups':b_groups} dataset = [[2.771244718,1.784783929,0], [1.728571309,1.169761413,0], [3.678319846,2.81281357,0], [3.961043357,2.61995032,0], [2.999208922,2.209014212,0], [7.497545867,3.162953546,1], [9.00220326,3.339047188,1], [7.444542326,0.476683375,1], [10.12493903,3.234550982,1], [6.642287351,3.319983761,1]] split = get_split(dataset) print('Split: [X%d < %.3f]' % ((split['index']+1), split['value'])) ``` **get_split（）**功能被修改為打印出每個分割點，并且在評估時它是基尼指數。運行該示例打印所有Gini分數，然后在X1的數據集中打印最佳分割的分數＆lt; 6.642，基尼指數為0.0或完美分裂。 ```py X1 < 2.771 Gini=0.444 X1 < 1.729 Gini=0.500 X1 < 3.678 Gini=0.286 X1 < 3.961 Gini=0.167 X1 < 2.999 Gini=0.375 X1 < 7.498 Gini=0.286 X1 < 9.002 Gini=0.375 X1 < 7.445 Gini=0.167 X1 < 10.125 Gini=0.444 X1 < 6.642 Gini=0.000 X2 < 1.785 Gini=0.500 X2 < 1.170 Gini=0.444 X2 < 2.813 Gini=0.320 X2 < 2.620 Gini=0.417 X2 < 2.209 Gini=0.476 X2 < 3.163 Gini=0.167 X2 < 3.339 Gini=0.444 X2 < 0.477 Gini=0.500 X2 < 3.235 Gini=0.286 X2 < 3.320 Gini=0.375 Split: [X1 < 6.642] ``` 現在我們知道如何在數據集或行列表中找到最佳分割點，讓我們看看如何使用它來構建決策樹。 ### 3.建造一棵樹創建樹的根節點很簡單。我們使用整個數據集調用上面的 **get_split（）**函數。向樹中添加更多節點更有趣。構建樹可以分為3個主要部分： 1. 終端節點。 2. 遞歸拆分。 3. 建造一棵樹。 #### 3.1。終端節點我們需要決定何時停止種樹。我們可以使用節點在訓練數據集中負責的行數和行數來實現。 * **最大樹深**。這是樹的根節點的最大節點數。一旦滿足樹的最大深度，我們必須停止拆分添加新節點。更深的樹木更復雜，更有可能過度擬合訓練數據。 * **最小節點記錄**。這是給定節點負責的最小訓練模式數。一旦達到或低于此最小值，我們必須停止拆分和添加新節點。預計訓練模式太少的節點過于具體，可能會過度訓練訓練數據。這兩種方法將是用戶指定的樹構建過程參數。還有一個條件。可以選擇所有行屬于一個組的拆分。在這種情況下，我們將無法繼續拆分和添加子節點，因為我們將無法在一側或另一側拆分記錄。現在我們有一些關于何時停止種植樹木的想法。當我們在給定點停止增長時，該節點被稱為終端節點并用于進行最終預測。這是通過獲取分配給該節點的行組并選擇組中最常見的類值來完成的。這將用于進行預測。下面是一個名為 **to_terminal（）**的函數，它將為一組行選擇一個類值。它返回行列表中最常見的輸出值。 ```py # Create a terminal node value def to_terminal(group): outcomes = [row[-1] for row in group] return max(set(outcomes), key=outcomes.count) ``` #### 3.2。遞歸拆分我們知道如何以及何時創建終端節點，現在我們可以構建我們的樹。構建決策樹涉及在為每個節點創建的組上反復調用上面開發的 **get_split（）**函數。添加到現有節點的新節點稱為子節點。節點可以具有零個子節點（終端節點），一個子節點（一側直接進行預測）或兩個子節點。我們將在給定節點的字典表示中將子節點稱為左和右。創建節點后，我們可以通過再次調用相同的函數，對拆分中的每組數據遞歸創建子節點。下面是一個實現此遞歸過程的函數。它將節點作為參數以及節點中的最大深度，最小模式數和節點的當前深度。您可以想象這可能首先如何在根節點中傳遞，并且深度為1.此函數最好用以下步驟解釋： 1. 首先，提取節點分割的兩組數據以供使用并從節點中刪除。當我們處理這些組時，節點不再需要訪問這些數據。 2. 接下來，我們檢查左側或右側行組是否為空，如果是，我們使用我們擁有的記錄創建終端節點。 3. 然后我們檢查是否已達到最大深度，如果是，我們創建一個終端節點。 4. 然后我們處理左子節點，如果行組太小則創建終端節點，否則以深度優先方式創建和添加左節點，直到在該分支上到達樹的底部。 5. 然后以相同的方式處理右側，因為我們將構造的樹恢復到根。 ```py # Create child splits for a node or make terminal def split(node, max_depth, min_size, depth): left, right = node['groups'] del(node['groups']) # check for a no split if not left or not right: node['left'] = node['right'] = to_terminal(left + right) return # check for max depth if depth >= max_depth: node['left'], node['right'] = to_terminal(left), to_terminal(right) return # process left child if len(left) <= min_size: node['left'] = to_terminal(left) else: node['left'] = get_split(left) split(node['left'], max_depth, min_size, depth+1) # process right child if len(right) <= min_size: node['right'] = to_terminal(right) else: node['right'] = get_split(right) split(node['right'], max_depth, min_size, depth+1) ``` #### 3.3。建造一棵樹我們現在可以將所有部分組合在一起。構建樹包括創建根節點并調用 **split（）**函數，然后遞歸調用自身以構建整個樹。下面是實現此過程的小 **build_tree（）**函數。 ```py # Build a decision tree def build_tree(train, max_depth, min_size): root = get_split(train) split(root, max_depth, min_size, 1) return root ``` 我們可以使用上面設計的小數據集測試整個過程。以下是完整的示例。還包括一個小的 **print_tree（）**函數，它遞歸地打印出決策樹的節點，每個節點一行。雖然沒有真正的決策樹圖那么引人注目，但它給出了樹結構和決策的概念。 ```py # Split a dataset based on an attribute and an attribute value def test_split(index, value, dataset): left, right = list(), list() for row in dataset: if row[index] < value: left.append(row) else: right.append(row) return left, right # Calculate the Gini index for a split dataset def gini_index(groups, classes): # count all samples at split point n_instances = float(sum([len(group) for group in groups])) # sum weighted Gini index for each group gini = 0.0 for group in groups: size = float(len(group)) # avoid divide by zero if size == 0: continue score = 0.0 # score the group based on the score for each class for class_val in classes: p = [row[-1] for row in group].count(class_val) / size score += p * p # weight the group score by its relative size gini += (1.0 - score) * (size / n_instances) return gini # Select the best split point for a dataset def get_split(dataset): class_values = list(set(row[-1] for row in dataset)) b_index, b_value, b_score, b_groups = 999, 999, 999, None for index in range(len(dataset[0])-1): for row in dataset: groups = test_split(index, row[index], dataset) gini = gini_index(groups, class_values) if gini < b_score: b_index, b_value, b_score, b_groups = index, row[index], gini, groups return {'index':b_index, 'value':b_value, 'groups':b_groups} # Create a terminal node value def to_terminal(group): outcomes = [row[-1] for row in group] return max(set(outcomes), key=outcomes.count) # Create child splits for a node or make terminal def split(node, max_depth, min_size, depth): left, right = node['groups'] del(node['groups']) # check for a no split if not left or not right: node['left'] = node['right'] = to_terminal(left + right) return # check for max depth if depth >= max_depth: node['left'], node['right'] = to_terminal(left), to_terminal(right) return # process left child if len(left) <= min_size: node['left'] = to_terminal(left) else: node['left'] = get_split(left) split(node['left'], max_depth, min_size, depth+1) # process right child if len(right) <= min_size: node['right'] = to_terminal(right) else: node['right'] = get_split(right) split(node['right'], max_depth, min_size, depth+1) # Build a decision tree def build_tree(train, max_depth, min_size): root = get_split(train) split(root, max_depth, min_size, 1) return root # Print a decision tree def print_tree(node, depth=0): if isinstance(node, dict): print('%s[X%d < %.3f]' % ((depth*' ', (node['index']+1), node['value']))) print_tree(node['left'], depth+1) print_tree(node['right'], depth+1) else: print('%s[%s]' % ((depth*' ', node))) dataset = [[2.771244718,1.784783929,0], [1.728571309,1.169761413,0], [3.678319846,2.81281357,0], [3.961043357,2.61995032,0], [2.999208922,2.209014212,0], [7.497545867,3.162953546,1], [9.00220326,3.339047188,1], [7.444542326,0.476683375,1], [10.12493903,3.234550982,1], [6.642287351,3.319983761,1]] tree = build_tree(dataset, 1, 1) print_tree(tree) ``` 我們可以在運行此示例時更改最大深度參數，并查看對打印樹的影響。最大深度為1（調用 **build_tree（）**函數時的第二個參數），我們可以看到樹使用了我們在上一節中發現的完美分割。這是一個具有一個節點的樹，也稱為決策樹樁。 ```py [X1 < 6.642] [0] [1] ``` 將最大深度增加到2，即使不需要，我們也會強制樹進行拆分。然后，根節點的左右子節點再次使用 **X1** 屬性來拆分已經完美的類混合。 ```py [X1 < 6.642] [X1 < 2.771] [0] [0] [X1 < 7.498] [1] [1] ``` 最后，反過來說，我們可以強制一個更高級別的分裂，最大深度為3。 ```py [X1 < 6.642] [X1 < 2.771] [0] [X1 < 2.771] [0] [0] [X1 < 7.498] [X1 < 7.445] [1] [1] [X1 < 7.498] [1] [1] ``` 這些測試表明，很有可能優化實現以避免不必要的拆分。這是一個擴展。現在我們可以創建一個決策樹，讓我們看看如何使用它來對新數據進行預測。 ### 4.進行預測使用決策樹進行預測涉及使用專門提供的數據行導航樹。同樣，我們可以使用遞歸函數實現此功能，其中使用左子節點或右子節點再次調用相同的預測例程，具體取決于拆分如何影響提供的數據。我們必須檢查子節點是否是要作為預測返回的終端值，或者它是否是包含要考慮的另一級樹的字典節點。下面是實現此過程的 **predict（）**函數。您可以看到給定節點中的索引和值您可以看到給定節點中的索引和值如何用于評估提供的數據行是否位于拆分的左側或右側。 ```py # Make a prediction with a decision tree def predict(node, row): if row[node['index']] < node['value']: if isinstance(node['left'], dict): return predict(node['left'], row) else: return node['left'] else: if isinstance(node['right'], dict): return predict(node['right'], row) else: return node['right'] ``` 我們可以使用我們設計的數據集來測試這個功能。下面是一個使用硬編碼決策樹的示例，該決策樹具有最佳分割數據的單個節點（決策樹樁）。該示例對數據集中的每一行進行預測。 ```py # Make a prediction with a decision tree def predict(node, row): if row[node['index']] < node['value']: if isinstance(node['left'], dict): return predict(node['left'], row) else: return node['left'] else: if isinstance(node['right'], dict): return predict(node['right'], row) else: return node['right'] dataset = [[2.771244718,1.784783929,0], [1.728571309,1.169761413,0], [3.678319846,2.81281357,0], [3.961043357,2.61995032,0], [2.999208922,2.209014212,0], [7.497545867,3.162953546,1], [9.00220326,3.339047188,1], [7.444542326,0.476683375,1], [10.12493903,3.234550982,1], [6.642287351,3.319983761,1]] # predict with a stump stump = {'index': 0, 'right': 1, 'value': 6.642287351, 'left': 0} for row in dataset: prediction = predict(stump, row) print('Expected=%d, Got=%d' % (row[-1], prediction)) ``` 運行該示例將按預期為每行打印正確的預測。 ```py Expected=0, Got=0 Expected=0, Got=0 Expected=0, Got=0 Expected=0, Got=0 Expected=0, Got=0 Expected=1, Got=1 Expected=1, Got=1 Expected=1, Got=1 Expected=1, Got=1 Expected=1, Got=1 ``` 我們現在知道如何創建決策樹并使用它來進行預測。現在，讓我們將它應用于真實的數據集。 ### 5.鈔票案例研究本節將CART算法應用于Bank Note數據集。第一步是加載數據集并將加載的數據轉換為可用于計算分割點的數字。為此，我們將使用輔助函數 **load_csv（）**來加載文件，使用 **str_column_to_float（）**將字符串數轉換為浮點數。我們將使用5倍折疊交叉驗證來評估算法。這意味著每個折疊中將使用1372/5 = 274.4或僅超過270個記錄。我們將使用輔助函數 **evaluate_algorithm（）**來評估具有交叉驗證的算法和 **accuracy_metric（）**來計算預測的準確性。開發了一個名為 **decision_tree（）**的新函數來管理CART算法的應用，首先從訓練數據集創建樹，然后使用樹對測試數據集進行預測。下面列出了完整的示例。 ```py # CART on the Bank Note dataset from random import seed from random import randrange from csv import reader # Load a CSV file def load_csv(filename): file = open(filename, "rb") lines = reader(file) dataset = list(lines) return dataset # Convert string column to float def str_column_to_float(dataset, column): for row in dataset: row[column] = float(row[column].strip()) # Split a dataset into k folds def cross_validation_split(dataset, n_folds): dataset_split = list() dataset_copy = list(dataset) fold_size = int(len(dataset) / n_folds) for i in range(n_folds): fold = list() while len(fold) < fold_size: index = randrange(len(dataset_copy)) fold.append(dataset_copy.pop(index)) dataset_split.append(fold) return dataset_split # Calculate accuracy percentage def accuracy_metric(actual, predicted): correct = 0 for i in range(len(actual)): if actual[i] == predicted[i]: correct += 1 return correct / float(len(actual)) * 100.0 # Evaluate an algorithm using a cross validation split def evaluate_algorithm(dataset, algorithm, n_folds, *args): folds = cross_validation_split(dataset, n_folds) scores = list() for fold in folds: train_set = list(folds) train_set.remove(fold) train_set = sum(train_set, []) test_set = list() for row in fold: row_copy = list(row) test_set.append(row_copy) row_copy[-1] = None predicted = algorithm(train_set, test_set, *args) actual = [row[-1] for row in fold] accuracy = accuracy_metric(actual, predicted) scores.append(accuracy) return scores # Split a dataset based on an attribute and an attribute value def test_split(index, value, dataset): left, right = list(), list() for row in dataset: if row[index] < value: left.append(row) else: right.append(row) return left, right # Calculate the Gini index for a split dataset def gini_index(groups, classes): # count all samples at split point n_instances = float(sum([len(group) for group in groups])) # sum weighted Gini index for each group gini = 0.0 for group in groups: size = float(len(group)) # avoid divide by zero if size == 0: continue score = 0.0 # score the group based on the score for each class for class_val in classes: p = [row[-1] for row in group].count(class_val) / size score += p * p # weight the group score by its relative size gini += (1.0 - score) * (size / n_instances) return gini # Select the best split point for a dataset def get_split(dataset): class_values = list(set(row[-1] for row in dataset)) b_index, b_value, b_score, b_groups = 999, 999, 999, None for index in range(len(dataset[0])-1): for row in dataset: groups = test_split(index, row[index], dataset) gini = gini_index(groups, class_values) if gini < b_score: b_index, b_value, b_score, b_groups = index, row[index], gini, groups return {'index':b_index, 'value':b_value, 'groups':b_groups} # Create a terminal node value def to_terminal(group): outcomes = [row[-1] for row in group] return max(set(outcomes), key=outcomes.count) # Create child splits for a node or make terminal def split(node, max_depth, min_size, depth): left, right = node['groups'] del(node['groups']) # check for a no split if not left or not right: node['left'] = node['right'] = to_terminal(left + right) return # check for max depth if depth >= max_depth: node['left'], node['right'] = to_terminal(left), to_terminal(right) return # process left child if len(left) <= min_size: node['left'] = to_terminal(left) else: node['left'] = get_split(left) split(node['left'], max_depth, min_size, depth+1) # process right child if len(right) <= min_size: node['right'] = to_terminal(right) else: node['right'] = get_split(right) split(node['right'], max_depth, min_size, depth+1) # Build a decision tree def build_tree(train, max_depth, min_size): root = get_split(train) split(root, max_depth, min_size, 1) return root # Make a prediction with a decision tree def predict(node, row): if row[node['index']] < node['value']: if isinstance(node['left'], dict): return predict(node['left'], row) else: return node['left'] else: if isinstance(node['right'], dict): return predict(node['right'], row) else: return node['right'] # Classification and Regression Tree Algorithm def decision_tree(train, test, max_depth, min_size): tree = build_tree(train, max_depth, min_size) predictions = list() for row in test: prediction = predict(tree, row) predictions.append(prediction) return(predictions) # Test CART on Bank Note dataset seed(1) # load and prepare data filename = 'data_banknote_authentication.csv' dataset = load_csv(filename) # convert string attributes to integers for i in range(len(dataset[0])): str_column_to_float(dataset, i) # evaluate algorithm n_folds = 5 max_depth = 5 min_size = 10 scores = evaluate_algorithm(dataset, decision_tree, n_folds, max_depth, min_size) print('Scores: %s' % scores) print('Mean Accuracy: %.3f%%' % (sum(scores)/float(len(scores)))) ``` 該示例使用5層的最大樹深度和每個節點的最小行數為10.這些CART參數通過一些實驗選擇，但絕不是最佳的。運行該示例打印每個折疊的平均分類準確度以及所有折疊的平均表現。您可以看到CART和所選配置的平均分類精度達到了約97％，這明顯優于達到50％精度的零規則算法。 ```py Scores: [96.35036496350365, 97.08029197080292, 97.44525547445255, 98.17518248175182, 97.44525547445255] Mean Accuracy: 97.299% ``` ## 擴展本節列出了您可能希望探索的本教程的擴展。 * **算法調整**。未調整CART在Bank Note數據集中的應用。嘗試使用不同的參數值，看看是否可以獲得更好的表現。 * **交叉熵**。用于評估分裂的另一個成本函數是交叉熵（logloss）。您可以實施和試驗此替代成本函數。 * **樹修剪**。減少訓練數據集過度擬合的一項重要技術是修剪樹木。調查并實施樹修剪方法。 * **分類數據集**。該示例設計用于具有數字或序數輸入屬性的輸入數據，嘗試分類輸入數據和可能使用相等而不是排名的拆分。 * **回歸**。使用不同的成本函數和方法調整樹以進行回歸以創建終端節點。 * **更多數據集**。將算法應用于UCI機器學習庫中的更多數據集。 **你有沒有探索過這些擴展？** 在下面的評論中分享您的經驗。 ## 評論在本教程中，您了解了如何使用Python從頭開始實現決策樹算法。具體來說，你學到了： * 如何選擇和評估訓練數據集中的分割點。 * 如何從多個拆分中遞歸構建決策樹。 * 如何將CART算法應用于現實世界的分類預測建模問題。 **你有什么問題嗎？** 在下面的評論中提出您的問題，我會盡力回答。