【随機森林】随機森林的 原理/ 樣例實作/ 參數調優 分析及 Python代碼實作

決策樹

1.決策樹與随機森林都屬于機器學習中監督學習的範疇，主要用于分類問題。 

決策樹算法有這幾種：ID3、C4.5、CART，基于決策樹的算法有bagging、随機森林、GBDT等。 

決策樹是一種利用樹形結構進行決策的算法，對于樣本資料根據已知條件或叫特征進行分叉，最終建立一棵樹，樹的葉子結節辨別最終決策。新來的資料便可以根據這棵樹進行判斷。随機森林是一種通過多棵決策樹進行優化決策的算法。

2.案例： 

圖 1 是一棵結構簡單的決策樹，用于預測貸款使用者是否具有償還貸款的能力。貸款使用者主要具備三個屬性：是否擁有房産，是否結婚，平均月收入。每一個内部結節都表示一個屬性條件判斷，葉子結節表示貸款使用者是否具有償還能力。 

這裡說的屬性，也就是算法中的特征，對應于資料表就是字段。 

這裡說的可以償還/不能償還，就是一種分類問題。

3.決策樹特征選取： 

從上圖我們可以看到，第一個節點使用“擁有房産”作為條件，也就是特征。那麼我們為什麼第一個條件選擇“擁有房産”呢，選擇的條件和依據是什麼呢？下面介紹基尼系數： 

基尼指數是另一種資料的不純度的度量方法，其公式為： 

該公式可以用數學公式證明： 

x+y=1 

f=1-(x^2+y^2) 

f(x)=1-x^2-(1-x)^2=-2x^2+2x 

曲線為： 

根據上圖可以看到，當x越靠近0或者1時，系數越小，代表資料純度越高。有就是中間的某類資料占的比重比較大，也符合我們的認識。 

其中 c 表示資料集中類别的數量，Pi 表示類别 i 樣本數量占所有樣本的比例。 從該公式可以看出，當資料集中資料混合的程度越高，基尼指數也就越高。當資料集 D 隻有一種資料類型，那麼基尼指數的值為最低 0。 

如果選取的屬性為 A，那麼分裂後的資料集 D 的基尼指數的計算公式為： 

其中 k 表示樣本 D 被分為 k 個部分，資料集 D 分裂成為 k 個 Dj 資料集。 

對于特征選取，需要選擇最小的分裂後的基尼指數。也可以用基尼指數增益值作為決策樹選擇特征的依據。公式如下： 

在決策樹選擇特征時，應選擇基尼指數增益值最大的特征，作為該結節分裂條件。 

另一個，和基尼系數類似，可采用資訊熵，熵的概念實體上都學過，越無序，熵越大，不做多解釋： 

假設在樣本資料集 D 中，混有 c 種類别的資料。建構決策樹時，根據給定的樣本資料集選擇某個特征值作為樹的結節。在資料集中，可以計算出該資料中的資訊熵： 

上圖為分析資訊增益的計算公式，可以看出和基尼系數大體類似。 

如果選取的屬性為 A，那麼分裂後的資料集 D 的基尼指數的計算公式為： 

其中 k 表示樣本 D 被分為 k 個部分，資料集 D 分裂成為 k 個 Dj 資料集。 

對于特征選取，需要選擇最小的分裂後的基尼指數。也可以用基尼指數增益值作為決策樹選擇特征的依據。公式如下： 

在決策樹選擇特征時，應選擇基尼指數增益值最大的特征，作為該結節分裂條件。

4.剪枝： 

分為預剪枝和後剪枝。 

預剪枝提前結束決策樹的省長，後剪枝效果更好，但是後剪枝會浪費在叔的生長過程中的計算。

5.集中決策樹的差別： 

1） ID3 

是最早提出的一種決策樹方法，使用上述資訊增益的方式建立。 

缺點：隻能處理離散型屬性，并且對傾向于選擇取值較多的屬性； 

2） C4.5 

使用增益率對資訊增益進行擴充，以解決偏向取值較多的屬性的問題。另外它可以處理連續型屬性。 

3） CART 

CART中用于選擇變量的不純性度量是Gini指數； 

如果目标變量是标稱的，并且是具有兩個以上的類别，則CART可能考慮将目标類别合并成兩個超類别（雙化）； 

如果目标變量是連續的，則CART算法找出一組基于樹的回歸方程來預測目标變量。

随機森林

1.随機森林原理： 

随機森林由Leo Breiman（2001）提出的一種分類算法，它通過自助法（bootstrap）重采樣技術，從原始訓練樣本集N中有放回地重複随機抽取n個樣本生成新的訓練樣本集合訓練決策樹，然後按以上步驟生成m棵決策樹組成随機森林，新資料的分類結果按分類樹投票多少形成的分數而定。其實質是對決策樹算法的一種改進，将多個決策樹合并在一起，每棵樹的建立依賴于獨立抽取的樣本。 

單棵樹的分類能力可能很小，但在随機産生大量的決策樹後，一個測試樣本可以通過每一棵樹的分類結果經統計後選擇最可能的分類。 

随機森林大緻過程如下： 

1）從樣本集中有放回随機采樣選出n個樣本； 

2）從所有特征中随機選擇k個特征，對選出的樣本利用這些特征建立決策樹（一般是CART，也可是别的或混合）； 

3）重複以上兩步m次，即生成m棵決策樹，形成随機森林； 

4）對于新資料，經過每棵樹決策，最後投票确認分到哪一類。 

2.随機森林特點： 

随機森林有很多優點： 

1） 每棵樹都選擇部分樣本及部分特征，一定程度避免過拟合； 

2） 每棵樹随機選擇樣本并随機選擇特征，使得具有很好的抗噪能力，性能穩定； 

3） 能處理很高次元的資料，并且不用做特征選擇； 

4） 适合并行計算； 

5） 實作比較簡單； 

缺點： 

1） 參數較複雜； 

2） 模型訓練和預測都比較慢。 

3.使用： 

随機森林算法在大部分資料處理軟體中都有實作，使用時可以直接調用，隻需指定所需參數。 

随機森林模型訓練前要設定的參數較多，按PAI平台的實作有如下幾個： 

o 算法類型：（可選）可供選擇的算法類型有id3算法、cart算法、c4.5算法以及預設情況下的将上述三種算法均分的混合算法 

o 樹的數目：森林中樹的個數, 範圍(0, 1000] 

o 随機屬性個數：（可選）單顆樹在生成時，每次選擇最優特征，随機的特征個數。可供選擇的類型有logN，N/3，sqrtN，N四種類型，其中N為屬性總數 

o 樹最大深度：（可選）單顆樹的最大深度，範圍[1, ∞)，-1表示完全生長。 

o 葉子節點最少記錄數：（可選）葉節點資料的最小個數。最小個數為2 

o 葉子節點最少記錄百分比：（可選）葉節點資料個數占父節點的最小比例，範圍[0,100]，-1表示無限制。預設-1 

o 每棵樹最大記錄數：（可選）森林中單顆樹輸入的随機資料的個數。範圍為(1000, 1000000] 

4.模型評估： 

算法模型建立後需要進行評估，以判斷模型的優劣。一般使用訓練集 (training set) 建立模型，使用測試集 (test set) 來評估模型。對于分類算法評估名額有分類準确度、召回率、虛警率和精确度等。而這些名額都是基于混淆矩陣 (confusion matrix) 進行計算的。 

混淆矩陣用來評價監督式學習模型的精确性，矩陣的每一列代表一個類的執行個體預測，而每一行表示一個實際的類的執行個體。以二分類問題為例，如下表所示： 

其中 

P (Positive Sample)：正例的樣本數量。 

N (Negative Sample)：負例的樣本數量。 

TP (True Positive)：正确預測到的正例的數量。 

FP (False Positive)：把負例預測成正例的數量。 

FN (False Negative)：把正例預測成負例的數量。 

TN (True Negative)：正确預測到的負例的數量。 

根據混淆矩陣可以得到評價分類模型的名額有以下幾種。 

分類準确度，就是正負樣本分别被正确分類的機率，計算公式為： 

召回率，就是正樣本被識别出的機率，計算公式為： 

虛警率，就是負樣本被錯誤分為正樣本的機率，計算公式為： 

精确度，就是分類結果為正樣本的情況真實性程度，計算公式為： 

評估方法有保留法、随機二次抽樣、交叉驗證和自助法等。 

保留法 (holdout) 是評估分類模型性能的最基本的一種方法。将被标記的原始資料集分成訓練集和檢驗集兩份，訓練集用于訓練分類模型，檢驗集用于評估分類模型性能。但此方法不适用樣本較小的情況，模型可能高度依賴訓練集和檢驗集的構成。 

随機二次抽樣 (random subsampling) 是指多次重複使用保留方法來改進分類器評估方法。同樣此方法也不适用訓練集數量不足的情況，而且也可能造成有些資料未被用于訓練集。 

交叉驗證 (cross-validation) 是指把資料分成數量相同的 k 份，每次使用資料進行分類時，選擇其中一份作為檢驗集，剩下的 k-1 份為訓練集，重複 k 次，正好使得每一份資料都被用于一次檢驗集 k-1 次訓練集。該方法的優點是盡可能多的資料作為訓練集資料，每一次訓練集資料和檢驗集資料都是互相獨立的，并且完全覆寫了整個資料集。也存在一個缺點，就是分類模型運作了 K 次，計算開銷較大。 

自助法 (bootstrap) 是指在其方法中，訓練集資料采用的是有放回的抽樣，即已經選取為訓練集的資料又被放回原來的資料集中，使得該資料有機會能被再一次抽取。用于樣本數不多的情況下，效果很好。

其它類似算法

1.Bagging 

Bagging算法與随機森林類似，差別是每棵樹都使用所有特征，而不是隻選擇部分特征。該算法過程如下： 

1）從樣本集中随機采樣選出n個樣本； 

2）在所有屬性上，對這n個樣本建立分類器（CART or SVM or …）； 

3）重複以上兩步m次，即生成m個分類器（CART or SVM or …）； 

4）将資料放在這m個分類器上跑，最後投票确認分到哪一類。

2.GBDT 

GBDT（Gradient Boosting Decision Tree）是一種疊代的決策樹算法，該算法由多棵決策樹組成，所有樹的結論累加起來做最終結果。被認為是泛化能力較強的一種算法。 

GBDT是一個應用很廣泛的算法，可以用來做分類、回歸。GBDT還有其他名字，比如MART（Multiple Additive Regression Tree），GBRT（Gradient Boosting Regression Tree），Tree Net等。 

GBDT與C4.5等分類樹不同，它是回歸樹。差別在于，回歸樹的每個結點（不一定是葉子結點）都會得到一個預測值，以年齡為例，該預測值等于屬于這個結點的所有人年齡的平均值。分支時窮舉每個特征找到最好的一個進行分支，但衡量最好的标準不再是資訊增益，而是最小化均方差，如 （每個人的年齡 – 預測年齡）^2的總和 / N。也就是被預測出錯的人數越多，錯的越離譜，均方差就越大，通過最小化均方差能夠找到最可靠的分支依據。分支直到每個葉子結點上人的年齡都唯一或者達到預設的終止條件（如葉子個數上限）。若最終葉子結點上人的年齡不唯一，則以結點上所有人的平均年齡做為該葉子結點的預測年齡。 

梯度疊代（Gradient Boosting），即通過疊代多棵樹來共同決策。GBDT的核心就在于，每棵樹學的是之前所有樹結論和的殘差，這個殘差就是一個加預測值後能等到真實值的累加量。比如A的真實年齡是18歲，但第一棵樹的預測年齡是12 歲，差了6歲，即殘差為6歲。那麼在第二棵樹裡我們把A的年齡設為6歲去學習，如果第二棵樹真的能把A分到6歲的葉子結點，那累加兩棵樹的結論就是A的真實年齡；如果第二棵樹的結論是5歲，則A仍然存在1歲的殘差，第三棵樹裡A的年齡就變成1歲，繼續學習。 

GBDT具體實作請自行查閱。

樣例代碼及參數調優

資料集： 

我們的資料集是來自一個著名的資料挖掘競賽網站，是一個關于泰坦尼克号，遊客生存情況的調查。可以從這裡下載下傳：https://www.kaggle.com/c/titanic/data 

上面的一張圖，是我從官網上下載下傳的，總的來說，裡面的每一行資料，差不多有11個字段，包括遊客的年齡、名字、性别、買的幾等倉的票等等資訊，最後是他的生存情況，在這場事故中，他是死了還是幸存。 

不想解釋了，直接讀入資料吧

import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier
train = pd.read_csv("E:/train.csv", dtype={"Age": np.float64},)
train.head(10)
           

稍微分析一下，我們就可以篩選出對一個遊客的生存與否有關的變量：Pclass, Sex, Age, SibSp，Parch，Fare, Embarked. 一般來說，遊客的名字，買的船票号碼對其的生存情況應該影響很小。

len(train_data)
out:891
           

我們共有891條資料，将近900條，我們使用600條作為訓練資料，剩下的291條作為測試資料，通過對随機森林的參數不斷調優，找出在測試結果上，預測最為精确的随機森林模型。 

在具體的實驗之前，我們看一下使用随機森林模型，需要注意哪幾個變量： 

在 sklearn中，随機森林的函數模型是：

RandomForestClassifier(bootstrap=True, class_weight=None, criterion='gini',
            max_depth=None, max_features='auto', max_leaf_nodes=None,
            min_samples_leaf=1, min_samples_split=2,
            min_weight_fraction_leaf=0.0, n_estimators=10, n_jobs=1,
            oob_score=False, random_state=None, verbose=0,
            warm_start=False)
           

參數分析 

A. max_features： 

随機森林允許單個決策樹使用特征的最大數量。 Python為最大特征數提供了多個可選項。 下面是其中的幾個： 

Auto/None ：簡單地選取所有特征，每顆樹都可以利用他們。這種情況下，每顆樹都沒有任何的限制。 

sqrt ：此選項是每顆子樹可以利用總特征數的平方根個。 例如，如果變量（特征）的總數是100，是以每顆子樹隻能取其中的10個。“log2”是另一種相似類型的選項。 

0.2：此選項允許每個随機森林的子樹可以利用變量（特征）數的20％。如果想考察的特征x％的作用， 我們可以使用“0.X”的格式。 

max_features如何影響性能和速度？ 

增加max_features一般能提高模型的性能，因為在每個節點上，我們有更多的選擇可以考慮。 然而，這未必完全是對的，因為它降低了單個樹的多樣性，而這正是随機森林獨特的優點。 但是，可以肯定，你通過增加max_features會降低算法的速度。 是以，你需要适當的平衡和選擇最佳max_features。 

B. n_estimators： 

在利用最大投票數或平均值來預測之前，你想要建立子樹的數量。 較多的子樹可以讓模型有更好的性能，但同時讓你的代碼變慢。 你應該選擇盡可能高的值，隻要你的處理器能夠承受的住，因為這使你的預測更好更穩定。 

C. min_sample_leaf： 

如果您以前編寫過一個決策樹，你能體會到最小樣本葉片大小的重要性。 葉是決策樹的末端節點。 較小的葉子使模型更容易捕捉訓練資料中的噪聲。 一般來說，我更偏向于将最小葉子節點數目設定為大于50。在你自己的情況中，你應該盡量嘗試多種葉子大小種類，以找到最優的那個。

下面我們對上面提到的三個參數，進行調優，首先參數A，由于在我們的這個資料中，資料段總共隻有七八個，是以我們就簡單的選取所有的特征，是以我們隻需要對剩下的兩個變量進行調優。 

在sklearn自帶的随機森林算法中，輸入的值必須是整數或者浮點數，是以我們需要對資料進行預處理，将字元串轉化成整數或者浮點數：

def harmonize_data(titanic):
    # 填充空資料 和 把string資料轉成integer表示
    # 對于年齡字段發生缺失，我們用所有年齡的均值替代
    titanic["Age"] = titanic["Age"].fillna(titanic["Age"].median())
    # 性别男： 用0替代
    titanic.loc[titanic["Sex"] == "male", "Sex"] = 0
    # 性别女： 用1替代
    titanic.loc[titanic["Sex"] == "female", "Sex"] = 1

    titanic["Embarked"] = titanic["Embarked"].fillna("S")

    titanic.loc[titanic["Embarked"] == "S", "Embarked"] = 0
    titanic.loc[titanic["Embarked"] == "C", "Embarked"] = 1
    titanic.loc[titanic["Embarked"] == "Q", "Embarked"] = 2

    titanic["Fare"] = titanic["Fare"].fillna(titanic["Fare"].median())

    return titanic

train_data = harmonize_data(train)
           

上面的代碼是對原始資料進行清洗，填補缺失資料， 把string類型資料轉化成int資料 

下面的工作，我們開始劃分訓練資料和測試資料，總的資料有891個，我們用600個訓練資料集，剩下的291個作為測試資料集。

# 列出對生存結果有影響的字段
predictors = ["Pclass", "Sex", "Age", "SibSp", "Parch", "Fare", "Embarked"]
# 存放不同參數取值，以及對應的精度，每一個元素都是一個三元組(a, b, c)
results = []
# 最小葉子結點的參數取值
sample_leaf_options = list(range(1, 500, 3))
# 決策樹個數參數取值
n_estimators_options = list(range(1, 1000, 5))
groud_truth = train_data['Survived'][601:]

for leaf_size in sample_leaf_options:
    for n_estimators_size in n_estimators_options:
        alg = RandomForestClassifier(min_samples_leaf=leaf_size, n_estimators=n_estimators_size, random_state=50)
        alg.fit(train_data[predictors][:600], train_data['Survived'][:600])
        predict = alg.predict(train_data[predictors][601:])
        # 用一個三元組，分别記錄目前的 min_samples_leaf，n_estimators， 和在測試資料集上的精度
        results.append((leaf_size, n_estimators_size, (groud_truth == predict).mean()))
        # 真實結果和預測結果進行比較，計算準确率
        print((groud_truth == predict).mean())

# 列印精度最大的那一個三元組
print(max(results, key=lambda x: x[2]))
           

總的來說，調參對随機森林來說，不會發生很大的波動，相比神經網絡來說，随機森林即使使用預設的參數，也可以達到良好的結果。在我們的例子中，通過粗略的調參，可以在測試集上達到84%的預測準确率，我覺得效果應該出乎我的意料吧。 

附上全部代碼：（運作時間比較久）

__author__ = 'Administrator'
import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier

train = pd.read_csv("E:/train.csv", dtype={"Age": np.float64},)


def harmonize_data(titanic):
    # 填充空資料 和 把string資料轉成integer表示

    titanic["Age"] = titanic["Age"].fillna(titanic["Age"].median())

    titanic.loc[titanic["Sex"] == "male", "Sex"] = 0
    titanic.loc[titanic["Sex"] == "female", "Sex"] = 1

    titanic["Embarked"] = titanic["Embarked"].fillna("S")

    titanic.loc[titanic["Embarked"] == "S", "Embarked"] = 0
    titanic.loc[titanic["Embarked"] == "C", "Embarked"] = 1
    titanic.loc[titanic["Embarked"] == "Q", "Embarked"] = 2

    titanic["Fare"] = titanic["Fare"].fillna(titanic["Fare"].median())

    return titanic

train_data = harmonize_data(train)

predictors = ["Pclass", "Sex", "Age", "SibSp", "Parch", "Fare", "Embarked"]
results = []
sample_leaf_options = list(range(1, 500, 3))
n_estimators_options = list(range(1, 1000, 5))
groud_truth = train_data['Survived'][601:]

for leaf_size in sample_leaf_options:
    for n_estimators_size in n_estimators_options:
        alg = RandomForestClassifier(min_samples_leaf=leaf_size, n_estimators=n_estimators_size, random_state=50)
        alg.fit(train_data[predictors][:600], train_data['Survived'][:600])
        predict = alg.predict(train_data[predictors][601:])
        # 用一個三元組，分别記錄目前的 min_samples_leaf，n_estimators， 和在測試資料集上的精度
        results.append((leaf_size, n_estimators_size, (groud_truth == predict).mean()))
        # 真實結果和預測結果進行比較，計算準确率
        print((groud_truth == predict).mean())

# 列印精度最大的那一個三元組
print(max(results, key=lambda x: x[2]))
           

在講随機森林前，我先講一下什麼是內建學習。內建學習通過建構并結合多個分類器來完成學習任務。內建學習通過将多個學習器進行結合，常可獲得比單一學習器更好的泛化性能。

考慮一個簡單例子：在二分類任務中，假定三個分類器在三個測試樣本上的表現如下圖，其中√表示分類正确，×表示分類錯誤，內建學習的結果通過投票法産生，即“少數服從多數”。如下圖，在（a）中，每個分類器都隻有66.6%的精度，但內建學習卻達到了100%；在（b）中，三個分類器沒有差别，內建之後性能沒有提高；在(c)中，每個分類器的精度都隻有33.3%，內建學習的結果變得更糟。這個簡單地例子顯示出：要獲得好的內建，個體學習器應“好而不同”，即個體學習器要有一定的“準确性”，即學習器不能太差，并且要有“多樣性”，即學習器間具有差異。

根據個體學習器的生成方式，目前的內建學習方法大緻可分為兩大類，即個體學習器之間存在強依賴關系，必須串行生成的序列化方法，以及個體學習器間不存在強依賴關系，可同時生成的并行化方法；前者的代表是Boosting，後者的代表是Bagging和“随機森林”（Random Forest）

Bagging與随機森林

要得到泛化性能強的內建，內建中的個體學習器應盡可能互相獨立，雖然這在現實任務中很難做到，但我們可以設法使基學習器盡可能具有較大的差異。

在我的實驗中，使用“自助采樣法”：給定包含m個樣本的資料集，我們先随機取出一個樣本放入采樣集中，再把該樣本放回初始資料集，使得下次采樣時該樣本仍有可能被選中，這樣，經過m次随機操作，我們得到含m個樣本的采樣集，初始訓練集中有的樣本在采樣集裡多次出現，有的則從未出現。

按照這種方法，我們可以采樣出T個含m個訓練樣本的采樣集，然後基于每個采樣集訓練處一個基學習器，再将這些基學習器進行結合，這就是Bagging的基本流程。在對預測輸出進行結合時，Bagging通常對分類任務使用簡單投票法，對回歸任務使用簡單平均法。

随機森林是Bagging的一個擴充。随機森林在以決策樹為基學習器建構Bagging內建的基礎上，進一步在決策樹的訓練過程中引入了随機屬性選擇（即引入随機特征選擇）。傳統決策樹在選擇劃分屬性時時在目前節點的屬性集合（假定有d個屬性）中選擇一個最優屬性；而在随機森林中，對基決策樹的每個節點，先從該節點的屬性集合中随機選擇一個包含k個屬性的子集，然後再從這個子集中選擇一個最優屬性用于劃分。這裡的參數k控制了随機性的引入程度：若令k=d,則基決策樹的建構與傳統決策樹相同；若令k=1，則是随機選擇一個屬性進行劃分。

在這篇文章中，我們隻講随機森林的分類部分。随機森林用于分類時，即采用n個決策樹分類，将分類結果用簡單投票法得到最終分類，提高分類準确率。

對于決策樹不太了解的童鞋，可以看我的上一篇部落格：決策樹原理及Python代碼實作

簡單來說，随機森林就是對決策樹的內建，但有兩點不同：

（1）采樣的差異性：從含m個樣本的資料集中有放回的采樣，得到含m個樣本的采樣集，用于訓練。這樣能保證每個決策樹的訓練樣本不完全一樣。

（2）特征選取的差異性：每個決策樹的n個分類特征是在所有特征中随機選擇的（n是一個需要我們自己調整的參數）

随機森林需要調整的參數有：

（1）    決策樹的個數

（2）    特征屬性的個數

（3）    遞歸次數（即決策樹的深度）

下面，講一下如何用代碼實作随機森林。

代碼實作流程：

（1）    導入檔案并将所有特征轉換為float形式

（2）    将資料集分成n份，友善交叉驗證

（3）    構造資料子集（随機采樣），并在指定特征個數（假設m個，手動調參）下選取最優特征

（4）    構造決策樹

（5）    建立随機森林（多個決策樹的結合）

（6）    輸入測試集并進行測試，輸出預測結果

（1）    導入檔案并将所有特征轉換為float形式

#加載資料
def loadCSV(filename):
    dataSet=[]
    with open(filename,'r') as file:
        csvReader=csv.reader(file)
        for line in csvReader:
            dataSet.append(line)
    return dataSet
 
#除了判别列，其他列都轉換為float類型
def column_to_float(dataSet):
    featLen=len(dataSet[0])-1
    for data in dataSet:
        for column in range(featLen):
            data[column]=float(data[column].strip())
           

（2）    将資料集分成n份，友善交叉驗證

#将資料集分成N塊，友善交叉驗證
def spiltDataSet(dataSet,n_folds):
    fold_size=int(len(dataSet)/n_folds)
    dataSet_copy=list(dataSet)
    dataSet_spilt=[]
    for i in range(n_folds):
        fold=[]
        while len(fold) < fold_size:   #這裡不能用if，if隻是在第一次判斷時起作用，while執行循環，直到條件不成立
            index=randrange(len(dataSet_copy))
            fold.append(dataSet_copy.pop(index))  #pop() 函數用于移除清單中的一個元素（預設最後一個元素），并且傳回該元素的值。
        dataSet_spilt.append(fold)
    return dataSet_spilt
           

（3）    構造資料子集（随機采樣），并在指定特征個數（假設m個，手動調參）下選取最優特征

#構造資料子集
def get_subsample(dataSet,ratio):
    subdataSet=[]
    lenSubdata=round(len(dataSet)*ratio)
    while len(subdataSet) < lenSubdata:
        index=randrange(len(dataSet)-1)
        subdataSet.append(dataSet[index])
    #print len(subdataSet)
    return subdataSet
 
#選取任意的n個特征，在這n個特征中，選取分割時的最優特征
def get_best_spilt(dataSet,n_features):
    features=[]
    class_values=list(set(row[-1] for row in dataSet))
    b_index,b_value,b_loss,b_left,b_right=999,999,999,None,None
    while len(features) < n_features:
        index=randrange(len(dataSet[0])-1)
        if index not in features:
            features.append(index)
    #print 'features:',features
    for index in features:
        for row in dataSet:
            left,right=data_spilt(dataSet,index,row[index])
            loss=spilt_loss(left,right,class_values)
            if loss < b_loss:
                b_index,b_value,b_loss,b_left,b_right=index,row[index],loss,left,right
    #print b_loss
    #print type(b_index)
    return {'index':b_index,'value':b_value,'left':b_left,'right':b_right}
           

（4）    構造決策樹

#構造決策樹
def build_tree(dataSet,n_features,max_depth,min_size):
    root=get_best_spilt(dataSet,n_features)
    sub_spilt(root,n_features,max_depth,min_size,1) 
    return root
           

（5）    建立随機森林（多個決策樹的結合）

#建立随機森林
def random_forest(train,test,ratio,n_feature,max_depth,min_size,n_trees):
    trees=[]
    for i in range(n_trees):
        subTrain=get_subsample(train,ratio)
        tree=build_tree(subTrain,n_features,max_depth,min_size)
        #print 'tree %d: '%i,tree
        trees.append(tree)
    #predict_values = [predict(trees,row) for row in test]
    predict_values = [bagging_predict(trees, row) for row in test]
    return predict_values
           

（6）    輸入測試集并進行測試，輸出預測結果

#預測測試集結果
def predict(tree,row):
    predictions=[]
    if row[tree['index']] < tree['value']:
        if isinstance(tree['left'],dict):
            return predict(tree['left'],row)
        else:
            return tree['left']
    else:
        if isinstance(tree['right'],dict):
            return predict(tree['right'],row)
        else:
            return tree['right']
   # predictions=set(predictions)
           

對以上代碼的一點總結：

訓練部分：假設我們取dataset中的m個feature來構造決策樹，首先，我們周遊m個feature中的每一個feature，再周遊每一行，通過spilt_loss函數（計算分割代價）來選取最優的特征及特征值，根據是否大于這個特征值進行分類（分成left,right兩類），循環執行上述步驟，直至不可分或者達到遞歸限值（用來防止過拟合），最後得到一個決策樹tree。

測試部分：對測試集的每一行進行判斷，決策樹tree是一個多層字典，每一層為一個二分類，将每一行按照決策樹tree中的分類索引index一步一步向裡層探索，直至不出現字典時探索結束，得到的值即為我們的預測值。