# 如何在Python中從零開始實現隨機森林 > 原文： [https://machinelearningmastery.com/implement-random-forest-scratch-python/](https://machinelearningmastery.com/implement-random-forest-scratch-python/) 決策樹可能遭受高度變化，這使得它們的結果對于所使用的特定訓練數據而言是脆弱的。 從訓練數據樣本中構建多個模型（稱為裝袋）可以減少這種差異，但樹木具有高度相關性。 隨機森林是套袋的擴展，除了根據訓練數據的多個樣本構建樹木之外，它還限制了可用于構建樹木的特征，迫使樹木變得不同。反過來，這可以提升表現。 在本教程中，您將了解如何在Python中從頭開始實現隨機森林算法。 完成本教程后，您將了解： * 袋裝決策樹與隨機森林算法的區別。 * 如何構造具有更多方差的袋裝決策樹。 * 如何將隨機森林算法應用于預測建模問題。 讓我們開始吧。 * **2017年1月更新**：將cross_validation_split（）中的fold_size計算更改為始終為整數。修復了Python 3的問題。 * **2017年2月更新**：修復了build_tree中的錯誤。 * **2017年8月更新**：修正了基尼計算中的一個錯誤，根據組大小添加了組基尼評分缺失的權重（感謝邁克爾！）。 * **更新Aug / 2018** ：經過測試和更新，可與Python 3.6配合使用。  如何在Python中從頭開始實現隨機森林 照片由 [InspireFate Photography](https://www.flickr.com/photos/inspirefatephotography/7569736320/) ，保留一些權利。 ## 描述 本節簡要介紹隨機森林算法和本教程中使用的Sonar數據集。 ### 隨機森林算法 決策樹涉及在每個步驟中從數據集中貪婪地選擇最佳分割點。 如果沒有修剪，該算法使決策樹易受高方差影響。通過使用訓練數據集的不同樣本（問題的不同視圖）創建多個樹并組合它們的預測，可以利用和減少這種高方差。這種方法簡稱為bootstrap聚合或裝袋。 套袋的限制是使用相同的貪婪算法來創建每個樹，這意味著可能在每個樹中選擇相同或非常相似的分裂點，使得不同的樹非常相似（樹將相關）。反過來，這使他們的預測相似，減輕了最初尋求的差異。 我們可以通過限制貪婪算法在創建樹時在每個分割點處可以評估的特征（行）來強制決策樹不同。這稱為隨機森林算法。 與裝袋一樣，采集訓練數據集的多個樣本，并對每個樣本進行不同的訓練。不同之處在于，在每個點處對數據進行拆分并添加到樹中，只能考慮固定的屬性子集。 對于分類問題，我們將在本教程中看到的問題類型，要考慮拆分的屬性數量限制為輸入要素數量的平方根。 ```py num_features_for_split = sqrt(total_input_features) ``` 這一個小變化的結果是彼此更加不同的樹（不相關）導致更多樣化的預測和組合預測，其通常具有單個樹或單獨裝袋的更好表現。 ### 聲納數據集 我們將在本教程中使用的數據集是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. 計算拆分。 2. 聲納數據集案例研究。 這些步驟提供了實現和應用隨機森林算法到您自己的預測建模問題所需的基礎。 ### 1.計算拆分 在決策樹中，通過查找導致成本最低的屬性和該屬性的值來選擇拆分點。 對于分類問題，此成本函數通常是Gini索引，用于計算分割點創建的數據組的純度。基尼系數為0是完美純度，在兩類分類問題的情況下，類值完全分為兩組。 在決策樹中查找最佳分割點涉及評估每個輸入變量的訓練數據集中每個值的成本。 對于裝袋和隨機森林，此過程在訓練數據集的樣本上執行，由替換完成。對替換進行采樣意味著可以選擇相同的行并將其多次添加到樣本中。 我們可以更新隨機森林的這個程序。如果具有最低成本的拆分，我們可以創建要考慮的輸入屬性的樣本，而不是在搜索中枚舉輸入屬性的所有值。 此輸入屬性樣本可以隨機選擇而無需替換，這意味著在查找成本最低的分割點時，每個輸入屬性只需要考慮一次。 下面是一個函數名 **get_split（）**，它實現了這個過程。它將數據集和固定數量的輸入要素作為輸入參數進行評估，其中數據集可以是實際訓練數據集的樣本。 輔助函數 **test_split（）**用于通過候選分割點分割數據集， **gini_index（）**用于評估創建的行組的給定分割的成本。 我們可以看到通過隨機選擇特征索引并將它們添加到列表（稱為**特征**）來創建特征列表，然后枚舉該特征列表并將訓練數據集中的特定值評估為分割點。 ```py # Select the best split point for a dataset def get_split(dataset, n_features): class_values = list(set(row[-1] for row in dataset)) b_index, b_value, b_score, b_groups = 999, 999, 999, None features = list() while len(features) < n_features: index = randrange(len(dataset[0])-1) if index not in features: features.append(index) for index in features: 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} ``` 現在我們知道如何修改決策樹算法以與隨機森林算法一起使用，我們可以將其與包裝的實現結合起來并將其應用于真實世界的數據集。 ### 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（）[HTG11用于創建單個決策樹，**預測（）**使用決策樹進行預測， **subsample（）**制作訓練數據集的子樣本和 **bagging_predict（ ）**使用決策樹列表進行預測。** 開發了一個新的函數名 **random_forest（）**，它首先從訓練數據集的子樣本創建決策樹列表，然后使用它們進行預測。 如上所述，隨機森林和袋裝決策樹之間的關鍵區別是樹木創建方式的一個小變化，這里是 **get_split（）**函數。 下面列出了完整的示例。 ```py # Random Forest Algorithm on Sonar Dataset from random import seed from random import randrange from csv import reader from math import sqrt # 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, n_features): class_values = list(set(row[-1] for row in dataset)) b_index, b_value, b_score, b_groups = 999, 999, 999, None features = list() while len(features) < n_features: index = randrange(len(dataset[0])-1) if index not in features: features.append(index) for index in features: 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, n_features, 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, n_features) split(node['left'], max_depth, min_size, n_features, depth+1) # process right child if len(right) <= min_size: node['right'] = to_terminal(right) else: node['right'] = get_split(right, n_features) split(node['right'], max_depth, min_size, n_features, depth+1) # Build a decision tree def build_tree(train, max_depth, min_size, n_features): root = get_split(train, n_features) split(root, max_depth, min_size, n_features, 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) # Random Forest Algorithm def random_forest(train, test, max_depth, min_size, sample_size, n_trees, n_features): trees = list() for i in range(n_trees): sample = subsample(train, sample_size) tree = build_tree(sample, max_depth, min_size, n_features) trees.append(tree) predictions = [bagging_predict(trees, row) for row in test] return(predictions) # Test the random forest algorithm seed(2) # load and prepare data filename = 'sonar.all-data.csv' dataset = load_csv(filename) # convert string attributes to integers for i in range(0, 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 = 10 min_size = 1 sample_size = 1.0 n_features = int(sqrt(len(dataset[0])-1)) for n_trees in [1, 5, 10]: scores = evaluate_algorithm(dataset, random_forest, n_folds, max_depth, min_size, sample_size, n_trees, n_features) 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個記錄。 構建深度樹，最大深度為10，每個節點為1的最小訓練行數。訓練數據集的樣本創建的大小與原始數據集相同，這是隨機森林算法的默認期望值。 在每個分割點處考慮的要素數設置為sqrt（num_features）或sqrt（60）= 7.74四舍五入為7個要素。 評估了一組3種不同數量的樹木進行比較，顯示隨著更多樹木的增加，技能越來越高。 運行該示例打印每個折疊的分數和每個配置的平均分數。 ```py Trees: 1 Scores: [56.09756097560976, 63.41463414634146, 60.97560975609756, 58.536585365853654, 73.17073170731707] Mean Accuracy: 62.439% Trees: 5 Scores: [70.73170731707317, 58.536585365853654, 85.36585365853658, 75.60975609756098, 63.41463414634146] Mean Accuracy: 70.732% Trees: 10 Scores: [75.60975609756098, 80.48780487804879, 92.6829268292683, 73.17073170731707, 70.73170731707317] Mean Accuracy: 78.537% ``` ## 擴展 本節列出了您可能有興趣探索的本教程的擴展。 * **算法調整**。發現本教程中使用的配置有一些試驗和錯誤，但沒有進行優化。嘗試使用更多樹，不同數量的功能甚至不同的樹配置來提高表現。 * **更多問題**。將該技術應用于其他分類問題，甚至使用新的成本函數和用于組合樹木預測的新方法使其適應回歸。 **你有沒有試過這些擴展？** 在下面的評論中分享您的經驗。 ## 評論 在本教程中，您了解了如何從頭開始實現隨機森林算法。 具體來說，你學到了： * 隨機森林與袋裝決策樹的區別。 * 如何更新決策樹的創建以適應隨機森林過程。 * 如何將隨機森林算法應用于現實世界的預測建模問題。 **你有什么問題嗎？** 在下面的評論中提出您的問題，我會盡力回答。