# 如何用Python從頭開始實現Bagging > 原文： [https://machinelearningmastery.com/implement-bagging-scratch-python/](https://machinelearningmastery.com/implement-bagging-scratch-python/) 決策樹是一種簡單而強大的預測建模技術，但它們存在高度差異。 這意味著在給定不同的訓練數據的情況下，樹可以得到非常不同 使決策樹更加健壯并實現更好表現的技術稱為引導程序聚合或簡稱包裝。 在本教程中，您將了解如何使用Python從頭開始使用決策樹實現裝袋過程。 完成本教程后，您將了解： * 如何創建數據集的引導樣本。 * 如何使用自舉模型進行預測。 * 如何將裝袋應用于您自己的預測建模問題。 讓我們開始吧。 * **2017年1月更新**：將cross_validation_split（）中的fold_size計算更改為始終為整數。修復了Python 3的問題。 * **2017年2月更新**：修復了build_tree中的錯誤。 * **2017年8月更新**：修正了基尼計算中的一個錯誤，根據組大小添加了組基尼評分缺失的權重（感謝邁克爾！）。 * **更新Aug / 2018** ：經過測試和更新，可與Python 3.6配合使用。  如何用Python實現套裝 照片由 [Michael Cory](https://www.flickr.com/photos/khouri/5457862281/) 拍攝，保留一些權利。 ## 說明 本節簡要介紹Bootstrap Aggregation和將在本教程中使用的Sonar數據集。 ### Bootstrap聚合算法 引導程序是具有替換的數據集的樣本。 這意味著從現有數據集的隨機樣本創建新數據集，其中可以選擇給定行并將其多次添加到樣本中。 當您只有可用的有限數據集時，在估算諸如更廣泛數據集的均值等值時使用它是一種有用的方法。通過創建數據集的樣本并估算這些樣本的均值，您可以獲取這些估計的平均值，并更好地了解潛在問題的真實均值。 這種方法可以與具有高方差的機器學習算法一起使用，例如決策樹。針對每個數據引導樣本以及用于進行預測的那些模型的平均輸出，訓練單獨的模型。這種技術簡稱為bootstrap聚合或裝袋。 方差意味著算法的表現對訓練數據敏感，高方差表明訓練數據的變化越多，算法的表現就越差。 通過訓練許多樹并取其預測的平均值，可以改善諸如未修剪的決策樹之類的高方差機器學習算法的表現。結果通常優于單個決策樹。 除了提高表現之外，裝袋的另一個好處是袋裝決策樹不能過度配合問題。可以繼續添加樹木，直到達到最大表現。 ### 聲納數據集 我們將在本教程中使用的數據集是Sonar數據集。 這是一個描述聲納啁啾返回從不同表面反彈的數據集。 60個輸入變量是不同角度的回報強度。這是一個二元分類問題，需要一個模型來區分巖石和金屬圓柱。共有208個觀測結果。 這是一個眾所周知的數據集。所有變量都是連續的，通常在0到1的范圍內。輸出變量是我的字符串“M”和搖滾的“R”，需要將其轉換為整數1和0。 通過預測數據集（M或礦）中具有最多觀測值的類，零規則算法可以實現53％的準確度。 您可以在 [UCI機器學習庫](https://archive.ics.uci.edu/ml/datasets/Connectionist+Bench+(Sonar,+Mines+vs.+Rocks))中了解有關此數據集的更多信息。 免費下載數據集并將其放在工作目錄中，文件名為 **sonar.all-data.csv** 。 ## 教程 本教程分為兩部分： 1. Bootstrap Resample。 2. 聲納數據集案例研究。 這些步驟提供了實現和將決策樹的引導聚合應用于您自己的預測建模問題所需的基礎。 ### 1\. Bootstrap Resample 讓我們首先深入了解bootstrap方法的工作原理。 我們可以通過從數據集中隨機選擇行并將它們添加到新列表來創建數據集的新樣本。我們可以針對固定數量的行重復此操作，或者直到新數據集的大小與原始數據集的大小的比率匹配為止。 我們可以通過不刪除已選擇的行來允許替換采樣，以便將來可以選擇。 下面是一個名為 **subsample（）**的函數，它實現了這個過程。來自隨機模塊的 **randrange（）**函數用于選擇隨機行索引以在循環的每次迭代中添加到樣本。樣本的默認大小是原始數據集的大小。 ```py # Create a random subsample from the dataset with replacement def subsample(dataset, ratio=1.0): sample = list() n_sample = round(len(dataset) * ratio) while len(sample) < n_sample: index = randrange(len(dataset)) sample.append(dataset[index]) return sample ``` 我們可以使用此函數來估計人為數據集的平均值。 首先，我們可以創建一個包含20行和0到9之間的單列隨機數的數據集，并計算平均值。 然后，我們可以制作原始數據集的引導樣本，計算平均值，并重復此過程，直到我們有一個均值列表。取這些樣本均值的平均值可以給出我們對整個數據集平均值的可靠估計。 下面列出了完整的示例。 每個bootstrap樣本創建為原始20個觀察數據集的10％樣本（或2個觀察值）。然后，我們通過創建原始數據集的1,10,100個引導樣本，計算它們的平均值，然后平均所有這些估計的平均值來進行實驗。 ```py from random import seed from random import random from random import randrange # Create a random subsample from the dataset with replacement def subsample(dataset, ratio=1.0): sample = list() n_sample = round(len(dataset) * ratio) while len(sample) < n_sample: index = randrange(len(dataset)) sample.append(dataset[index]) return sample # Calculate the mean of a list of numbers def mean(numbers): return sum(numbers) / float(len(numbers)) seed(1) # True mean dataset = [[randrange(10)] for i in range(20)] print('True Mean: %.3f' % mean([row[0] for row in dataset])) # Estimated means ratio = 0.10 for size in [1, 10, 100]: sample_means = list() for i in range(size): sample = subsample(dataset, ratio) sample_mean = mean([row[0] for row in sample]) sample_means.append(sample_mean) print('Samples=%d, Estimated Mean: %.3f' % (size, mean(sample_means))) ``` 運行該示例將打印我們要估計的原始平均值。 然后我們可以從各種不同數量的自舉樣本中看到估計的平均值。我們可以看到，通過100個樣本，我們可以很好地估計平均值。 ```py True Mean: 4.450 Samples=1, Estimated Mean: 4.500 Samples=10, Estimated Mean: 3.300 Samples=100, Estimated Mean: 4.480 ``` 我們可以從每個子樣本創建一個模型，而不是計算平均值。 接下來，讓我們看看如何組合多個bootstrap模型的預測。 ### 2.聲納數據集案例研究 在本節中，我們將隨機森林算法應用于Sonar數據集。 該示例假定數據集的CSV副本位于當前工作目錄中，文件名為 **sonar.all-data.csv** 。 首先加載數據集，將字符串值轉換為數字，并將輸出列從字符串轉換為0到1的整數值。這可以通過輔助函數 **load_csv（）**， **str_column_to_float（ ）**和 **str_column_to_int（）**加載和準備數據集。 我們將使用k-fold交叉驗證來估計學習模型在看不見的數據上的表現。這意味著我們將構建和評估k模型并將表現估計為平均模型誤差。分類精度將用于評估每個模型。這些行為在 **cross_validation_split（）**， **accuracy_metric（）**和 **evaluate_algorithm（）**輔助函數中提供。 我們還將使用適用于裝袋的分類和回歸樹（CART）算法的實現，包括輔助函數 **test_split（）**將數據集分成組， **gini_index（）**來評估分裂點， **get_split（）**找到最佳分裂點， **to_terminal（）**， **split（）**和 **build_tree（）**使用創建單個決策樹，**預測（）**用決策樹和上一步驟中描述的**子樣本（）**函數進行預測，以制作訓練數據集的子樣本 開發了一個名為 **bagging_predict（）**的新函數，負責使用每個決策樹進行預測并將預測組合成單個返回值。這是通過從袋裝樹所做的預測列表中選擇最常見的預測來實現的。 最后，開發了一個名為 **bagging（）**的新功能，負責創建訓練數據集的樣本，在每個樣本上訓練決策樹，然后使用袋裝樹列表對測試數據集進行預測。 The complete example is listed below. ```py # Bagging Algorithm on the Sonar dataset from random import seed from random import randrange from csv import reader # Load a CSV file def load_csv(filename): dataset = list() with open(filename, 'r') as file: csv_reader = reader(file) for row in csv_reader: if not row: continue dataset.append(row) return dataset # Convert string column to float def str_column_to_float(dataset, column): for row in dataset: row[column] = float(row[column].strip()) # Convert string column to integer def str_column_to_int(dataset, column): class_values = [row[column] for row in dataset] unique = set(class_values) lookup = dict() for i, value in enumerate(unique): lookup[value] = i for row in dataset: row[column] = lookup[row[column]] return lookup # 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: # for i in range(len(dataset)): # row = dataset[randrange(len(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'] # Create a random subsample from the dataset with replacement def subsample(dataset, ratio): sample = list() n_sample = round(len(dataset) * ratio) while len(sample) < n_sample: index = randrange(len(dataset)) sample.append(dataset[index]) return sample # Make a prediction with a list of bagged trees def bagging_predict(trees, row): predictions = [predict(tree, row) for tree in trees] return max(set(predictions), key=predictions.count) # Bootstrap Aggregation Algorithm def bagging(train, test, max_depth, min_size, sample_size, n_trees): trees = list() for i in range(n_trees): sample = subsample(train, sample_size) tree = build_tree(sample, max_depth, min_size) trees.append(tree) predictions = [bagging_predict(trees, row) for row in test] return(predictions) # Test bagging on the sonar dataset seed(1) # load and prepare data filename = 'sonar.all-data.csv' dataset = load_csv(filename) # convert string attributes to integers for i in range(len(dataset[0])-1): str_column_to_float(dataset, i) # convert class column to integers str_column_to_int(dataset, len(dataset[0])-1) # evaluate algorithm n_folds = 5 max_depth = 6 min_size = 2 sample_size = 0.50 for n_trees in [1, 5, 10, 50]: scores = evaluate_algorithm(dataset, bagging, n_folds, max_depth, min_size, sample_size, n_trees) print('Trees: %d' % n_trees) print('Scores: %s' % scores) print('Mean Accuracy: %.3f%%' % (sum(scores)/float(len(scores)))) ``` k值為5用于交叉驗證，每次迭代時評估每個折疊208/5 = 41.6或僅超過40個記錄。 構建深度樹，最大深度為6，每個節點為2的最小訓練行數。訓練數據集的樣本創建為原始數據集大小的50％。這是為了強制用于訓練每棵樹的數據集子樣本中的某些變體。裝袋的默認設置是使樣本數據集的大小與原始訓練數據集的大小相匹配。 評估了一系列4種不同數量的樹以顯示算法的行為。 打印每個折疊的精度和每個配置的平均精度。隨著樹木數量的增加，我們可以看到表現略有提升的趨勢。 ```py Trees: 1 Scores: [87.8048780487805, 65.85365853658537, 65.85365853658537, 65.85365853658537, 73.17073170731707] Mean Accuracy: 71.707% Trees: 5 Scores: [60.97560975609756, 80.48780487804879, 78.04878048780488, 82.92682926829268, 63.41463414634146] Mean Accuracy: 73.171% Trees: 10 Scores: [60.97560975609756, 73.17073170731707, 82.92682926829268, 80.48780487804879, 68.29268292682927] Mean Accuracy: 73.171% Trees: 50 Scores: [63.41463414634146, 75.60975609756098, 80.48780487804879, 75.60975609756098, 85.36585365853658] Mean Accuracy: 76.098% ``` 這種方法的一個難點是，即使構建了深樹，創建的袋裝樹也非常相似。反過來，這些樹的預測也是相似的，并且我們希望在訓練數據集的不同樣本上訓練的樹之間的高方差減小。 這是因為在構造選擇相同或相似分裂點的樹時使用的貪婪算法。 本教程試圖通過約束用于訓練每棵樹的樣本大小來重新注入此方差。更強大的技術是約束在創建每個分割點時可以評估的特征。這是隨機森林算法中使用的方法。 ## 擴展 * **調整示例**。探索樹木數量甚至單個樹配置的不同配置，以了解您是否可以進一步改善結果。 * **Bag另一種算法**。其他算法可與套袋一起使用。例如，具有低k值的k-最近鄰算法將具有高方差并且是用于裝袋的良好候選者。 * **回歸問題**。套袋可以與回歸樹一起使用。您可以從袋裝樹中返回預測的平均值，而不是從預測集中預測最常見的類值。回歸問題的實驗。 **你有沒有試過這些擴展？** 在下面的評論中分享您的經驗。 ## 評論 在本教程中，您了解了如何使用Python從頭開始實現引導程序聚合。 具體來說，你學到了： * 如何創建子樣本并估計引導數量。 * 如何創建決策樹集合并使用它們進行預測。 * 如何將裝袋應用于現實世界的預測建模問題。 **你有什么問題嗎？** 在下面的評論中提出您的問題，我會盡力回答。