作者：Poll的筆記
博客：http://www.cnblogs.com/maybe2030/p/4585705.html

1、什么是隨機(jī)森林

作為新興起的、高度靈活的一種機(jī)器學(xué)習(xí)算法，隨機(jī)森林（Random Forest，簡(jiǎn)稱RF）擁有廣泛的應(yīng)用前景，從市場(chǎng)營銷到醫(yī)療保健保險(xiǎn)，既可以用來做市場(chǎng)營銷模擬的建模，統(tǒng)計(jì)客戶來源，保留和流失，也可用來預(yù)測(cè)疾病的風(fēng)險(xiǎn)和病患者的易感性。最初，我是在參加校外競(jìng)賽時(shí)接觸到隨機(jī)森林算法的。最近幾年的國內(nèi)外大賽，包括2013年百度校園電影推薦系統(tǒng)大賽、2014年阿里巴巴天池大數(shù)據(jù)競(jìng)賽以及Kaggle數(shù)據(jù)科學(xué)競(jìng)賽，參賽者對(duì)隨機(jī)森林的使用占有相當(dāng)高的比例。此外，據(jù)我的個(gè)人了解來看，一大部分成功進(jìn)入答辯的隊(duì)伍也都選擇了Random Forest 或者 GBDT 算法。所以可以看出，Random Forest在準(zhǔn)確率方面還是相當(dāng)有優(yōu)勢(shì)的。
　　那說了這么多，那隨機(jī)森林到底是怎樣的一種算法呢？
　　如果讀者接觸過決策樹（Decision Tree）的話，那么會(huì)很容易理解什么是隨機(jī)森林。隨機(jī)森林就是通過集成學(xué)習(xí)的思想將多棵樹集成的一種算法，它的基本單元是決策樹，而它的本質(zhì)屬于機(jī)器學(xué)習(xí)的一大分支——集成學(xué)習(xí)（Ensemble Learning）方法。隨機(jī)森林的名稱中有兩個(gè)關(guān)鍵詞，一個(gè)是“隨機(jī)”，一個(gè)就是“森林”?！吧帧蔽覀兒芎美斫?，一棵叫做樹，那么成百上千棵就可以叫做森林了，這樣的比喻還是很貼切的，其實(shí)這也是隨機(jī)森林的主要思想--集成思想的體現(xiàn)?！半S機(jī)”的含義我們會(huì)在下邊部分講到。
　　其實(shí)從直觀角度來解釋，每棵決策樹都是一個(gè)分類器（假設(shè)現(xiàn)在針對(duì)的是分類問題），那么對(duì)于一個(gè)輸入樣本，N棵樹會(huì)有N個(gè)分類結(jié)果。而隨機(jī)森林集成了所有的分類投票結(jié)果，將投票次數(shù)最多的類別指定為最終的輸出，這就是一種最簡(jiǎn)單的 Bagging 思想。

2、隨機(jī)森林的特點(diǎn)

我們前邊提到，隨機(jī)森林是一種很靈活實(shí)用的方法，它有如下幾個(gè)特點(diǎn)：

• 在當(dāng)前所有算法中，具有極好的準(zhǔn)確率/It is unexcelled in accuracy among current algorithms；
• 能夠有效地運(yùn)行在大數(shù)據(jù)集上/It runs efficiently on large data bases；
• 能夠處理具有高維特征的輸入樣本，而且不需要降維/It can handle thousands of input variables without variable deletion；
• 能夠評(píng)估各個(gè)特征在分類問題上的重要性/It gives estimates of what variables are important in the classification；
• 在生成過程中，能夠獲取到內(nèi)部生成誤差的一種無偏估計(jì)/It generates an internal unbiased estimate of the generalization error as the forest building progresses；
• 對(duì)于缺省值問題也能夠獲得很好得結(jié)果/It has an effective method for estimating missing data and maintains accuracy when a large proportion of the data are missing
• ... ...

實(shí)際上，隨機(jī)森林的特點(diǎn)不只有這六點(diǎn)，它就相當(dāng)于機(jī)器學(xué)習(xí)領(lǐng)域的Leatherman（多面手），你幾乎可以把任何東西扔進(jìn)去，它基本上都是可供使用的。在估計(jì)推斷映射方面特別好用，以致都不需要像SVM那樣做很多參數(shù)的調(diào)試。具體的隨機(jī)森林介紹可以參見隨機(jī)森林主頁：Random Forest。

3、隨機(jī)森林的相關(guān)基礎(chǔ)知識(shí)

隨機(jī)森林看起來是很好理解，但是要完全搞明白它的工作原理，需要很多機(jī)器學(xué)習(xí)方面相關(guān)的基礎(chǔ)知識(shí)。在本文中，我們簡(jiǎn)單談一下，而不逐一進(jìn)行贅述，如果有同學(xué)不太了解相關(guān)的知識(shí)，可以參閱其他博友的一些相關(guān)博文或者文獻(xiàn)。

3.1 信息、熵以及信息增益的概念

這三個(gè)基本概念是決策樹的根本，是決策樹利用特征來分類時(shí)，確定特征選取順序的依據(jù)。理解了它們，決策樹你也就了解了大概。

熵是約翰.馮.諾依曼建議使用的命名（當(dāng)然是英文），最初原因是因?yàn)榇蠹叶疾恢浪鞘裁匆馑迹谛畔⒄摵透怕收撝徐厥菍?duì)隨機(jī)變量不確定性的度量,與上邊聯(lián)系起來，熵便是信息的期望值，可以記作：

熵是用來度量不確定性的，當(dāng)熵越大，X=xi的不確定性越大，反之越小。對(duì)于機(jī)器學(xué)習(xí)中的分類問題而言，熵越大即這個(gè)類別的不確定性更大，反之越小。
信息增益在決策樹算法中是用來選擇特征的指標(biāo)，信息增益越大，則這個(gè)特征的選擇性越好，在概率中定義為：待分類的集合的熵和選定某個(gè)特征的條件熵之差，公式如下：

信息增益

條件熵

3.2 決策樹

決策樹是一種樹形結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉節(jié)點(diǎn)代表一種類別。常見的決策樹算法有C4.5、ID3和CART。

3.3 集成學(xué)習(xí)

集成學(xué)習(xí)通過建立幾個(gè)模型組合的來解決單一預(yù)測(cè)問題。它的工作原理是生成多個(gè)分類器/模型，各自獨(dú)立地學(xué)習(xí)和作出預(yù)測(cè)。這些預(yù)測(cè)最后結(jié)合成單預(yù)測(cè)，因此優(yōu)于任何一個(gè)單分類的做出預(yù)測(cè)。
　　隨機(jī)森林是集成學(xué)習(xí)的一個(gè)子類，它依靠于決策樹的投票選擇來決定最后的分類結(jié)果。你可以在這找到用python實(shí)現(xiàn)集成學(xué)習(xí)的文檔：Scikit 學(xué)習(xí)文檔。

4、隨機(jī)森林的生成

前面提到，隨機(jī)森林中有許多的分類樹。我們要將一個(gè)輸入樣本進(jìn)行分類，我們需要將輸入樣本輸入到每棵樹中進(jìn)行分類。打個(gè)形象的比喻：森林中召開會(huì)議，討論某個(gè)動(dòng)物到底是老鼠還是松鼠，每棵樹都要獨(dú)立地發(fā)表自己對(duì)這個(gè)問題的看法，也就是每棵樹都要投票。該動(dòng)物到底是老鼠還是松鼠，要依據(jù)投票情況來確定，獲得票數(shù)最多的類別就是森林的分類結(jié)果。森林中的每棵樹都是獨(dú)立的，99.9%不相關(guān)的樹做出的預(yù)測(cè)結(jié)果涵蓋所有的情況，這些預(yù)測(cè)結(jié)果將會(huì)彼此抵消。少數(shù)優(yōu)秀的樹的預(yù)測(cè)結(jié)果將會(huì)超脫于蕓蕓“噪音”，做出一個(gè)好的預(yù)測(cè)。將若干個(gè)弱分類器的分類結(jié)果進(jìn)行投票選擇，從而組成一個(gè)強(qiáng)分類器，這就是隨機(jī)森林bagging的思想（關(guān)于bagging的一個(gè)有必要提及的問題：bagging的代價(jià)是不用單棵決策樹來做預(yù)測(cè)，具體哪個(gè)變量起到重要作用變得未知，所以bagging改進(jìn)了預(yù)測(cè)準(zhǔn)確率但損失了解釋性。）。下圖可以形象地描述這個(gè)情況：

有了樹我們就可以分類了，但是森林中的每棵樹是怎么生成的呢？

每棵樹的按照如下規(guī)則生成：

• 1）如果訓(xùn)練集大小為N，對(duì)于每棵樹而言，隨機(jī)且有放回地從訓(xùn)練集中的抽取N個(gè)訓(xùn)練樣本（這種采樣方式稱為bootstrap sample方法），作為該樹的訓(xùn)練集；

從這里我們可以知道：每棵樹的訓(xùn)練集都是不同的，而且里面包含重復(fù)的訓(xùn)練樣本（理解這點(diǎn)很重要）。

為什么要隨機(jī)抽樣訓(xùn)練集？（add @2016.05.28）

如果不進(jìn)行隨機(jī)抽樣，每棵樹的訓(xùn)練集都一樣，那么最終訓(xùn)練出的樹分類結(jié)果也是完全一樣的，這樣的話完全沒有bagging的必要；

為什么要有放回地抽樣？（add @2016.05.28）

我理解的是這樣的：如果不是有放回的抽樣，那么每棵樹的訓(xùn)練樣本都是不同的，都是沒有交集的，這樣每棵樹都是"有偏的"，都是絕對(duì)"片面的"（當(dāng)然這樣說可能不對(duì)），也就是說每棵樹訓(xùn)練出來都是有很大的差異的；而隨機(jī)森林最后分類取決于多棵樹（弱分類器）的投票表決，這種表決應(yīng)該是"求同"，因此使用完全不同的訓(xùn)練集來訓(xùn)練每棵樹這樣對(duì)最終分類結(jié)果是沒有幫助的，這樣無異于是"盲人摸象"。

• 2）如果每個(gè)樣本的特征維度為M，指定一個(gè)常數(shù)m<<M，隨機(jī)地從M個(gè)特征中選取m個(gè)特征子集，每次樹進(jìn)行分裂時(shí)，從這m個(gè)特征中選擇最優(yōu)的；

根據(jù)Leo Breiman的建議，假設(shè)總的特征數(shù)量為M，這個(gè)比例可以是sqrt(M),1/2sqrt(M),2sqrt(M)

• 3）每棵樹都盡最大程度的生長(zhǎng)，并且沒有剪枝過程。

一開始我們提到的隨機(jī)森林中的“隨機(jī)”就是指的這里的兩個(gè)隨機(jī)性。兩個(gè)隨機(jī)性的引入對(duì)隨機(jī)森林的分類性能至關(guān)重要。由于它們的引入，使得隨機(jī)森林不容易陷入過擬合，并且具有很好得抗噪能力（比如：對(duì)缺省值不敏感）。

隨機(jī)森林分類效果（錯(cuò)誤率）與兩個(gè)因素有關(guān)：

1. 森林中任意兩棵樹的相關(guān)性：相關(guān)性越大，錯(cuò)誤率越大；
2. 森林中每棵樹的分類能力：每棵樹的分類能力越強(qiáng)，整個(gè)森林的錯(cuò)誤率越低。

減小特征選擇個(gè)數(shù)m，樹的相關(guān)性和分類能力也會(huì)相應(yīng)的降低；增大m，兩者也會(huì)隨之增大。所以關(guān)鍵問題是如何選擇最優(yōu)的m（或者是范圍），這也是隨機(jī)森林唯一的一個(gè)參數(shù)。

5、袋外錯(cuò)誤率（oob error）

上面我們提到，構(gòu)建隨機(jī)森林的關(guān)鍵問題就是如何選擇最優(yōu)的m，要解決這個(gè)問題主要依據(jù)計(jì)算袋外錯(cuò)誤率oob error（out-of-bag error）。

隨機(jī)森林有一個(gè)重要的優(yōu)點(diǎn)就是，沒有必要對(duì)它進(jìn)行交叉驗(yàn)證或者用一個(gè)獨(dú)立的測(cè)試集來獲得誤差的一個(gè)無偏估計(jì)。它可以在內(nèi)部進(jìn)行評(píng)估，也就是說在生成的過程中就可以對(duì)誤差建立一個(gè)無偏估計(jì)。

我們知道，在構(gòu)建每棵樹時(shí)，我們對(duì)訓(xùn)練集使用了不同的bootstrap sample（隨機(jī)且有放回地抽?。Ｋ詫?duì)于每棵樹而言（假設(shè)對(duì)于第k棵樹），大約有1/3的訓(xùn)練實(shí)例沒有參與第k棵樹的生成，它們稱為第k棵樹的oob樣本。

而這樣的采樣特點(diǎn)就允許我們進(jìn)行oob估計(jì)，它的計(jì)算方式如下：(note：以樣本為單位）

1）對(duì)每個(gè)樣本，計(jì)算它作為oob樣本的樹對(duì)它的分類情況（約1/3的樹）；
2）然后以簡(jiǎn)單多數(shù)投票作為該樣本的分類結(jié)果；
3）最后用誤分個(gè)數(shù)占樣本總數(shù)的比率作為隨機(jī)森林的oob誤分率。

（文獻(xiàn)原文：Put each case left out in the construction of the kth tree down the kth tree to get a classification. In this way, a test set classification is obtained for each case in about one-third of the trees. At the end of the run, take j to be the class that got most of the votes every time case n was oob. The proportion of times that j is not equal to the true class of n averaged over all cases is the oob error estimate. This has proven to be unbiased in many tests.）

oob誤分率是隨機(jī)森林泛化誤差的一個(gè)無偏估計(jì)，它的結(jié)果近似于需要大量計(jì)算的k折交叉驗(yàn)證。

6、隨機(jī)森林工作原理解釋的一個(gè)簡(jiǎn)單例子

描述：根據(jù)已有的訓(xùn)練集已經(jīng)生成了對(duì)應(yīng)的隨機(jī)森林，隨機(jī)森林如何利用某一個(gè)人的年齡（Age）、性別（Gender）、教育情況（Highest Educational Qualification）、工作領(lǐng)域（Industry）以及住宅地（Residence）共5個(gè)字段來預(yù)測(cè)他的收入層次。

收入層次 :

Band 1 : Below $40,000
Band 2: $40,000 – 150,000
Band 3: More than $150,000

隨機(jī)森林中每一棵樹都可以看做是一棵CART（分類回歸樹），這里假設(shè)森林中有5棵CART樹，總特征個(gè)數(shù)N=5，我們?nèi)=1（這里假設(shè)每個(gè)CART樹對(duì)應(yīng)一個(gè)不同的特征）。

CART 1 : Variable Age

CART 2 : Variable Gender

CART 3 : Variable Education

CART 4 : Variable Residence

CART 5 : Variable Industry

我們要預(yù)測(cè)的某個(gè)人的信息如下：

1. Age : 35 years ; 2. Gender : Male ; 3. Highest Educational Qualification : Diploma holder; 4. Industry : Manufacturing; 5. Residence : Metro.

根據(jù)這五棵CART樹的分類結(jié)果，我們可以針對(duì)這個(gè)人的信息建立收入層次的分布情況：

pp.png

最后，我們得出結(jié)論，這個(gè)人的收入層次70%是一等，大約24%為二等，6%為三等，所以最終認(rèn)定該人屬于一等收入層次（小于$40,000）。

7、特征工程

7.1 特征重要性

在隨機(jī)森林中某個(gè)特征X的重要性的計(jì)算方法如下：

• 1：對(duì)于隨機(jī)森林中的每一顆決策樹,使用相應(yīng)的OOB(袋外數(shù)據(jù))數(shù)據(jù)來計(jì)算它的袋外數(shù)據(jù)誤差,記為errOOB1.
• 2: 隨機(jī)地對(duì)袋外數(shù)據(jù)OOB所有樣本的特征X加入噪聲干擾(就可以隨機(jī)的改變樣本在特征X處的值),再次計(jì)算它的袋外數(shù)據(jù)誤差,記為errOOB2.
• 3：假設(shè)隨機(jī)森林中有Ntree棵樹,那么對(duì)于特征X的重要性=∑(errOOB2-errOOB1)/Ntree,之所以可以用這個(gè)表達(dá)式來作為相應(yīng)特征的重要性的度量值是因?yàn)椋喝艚o某個(gè)特征隨機(jī)加入噪聲之后,袋外的準(zhǔn)確率大幅度降低,則說明這個(gè)特征對(duì)于樣本的分類結(jié)果影響很大,也就是說它的重要程度比較高。

7.2 特征選擇

在論文 Variable Selection using Random Forests中詳細(xì)的論述了基于隨機(jī)森林的特征選擇方法,這里我們進(jìn)行一些回顧。
首先特征選擇的目標(biāo)有兩個(gè)：

1：找到與應(yīng)變量高度相關(guān)的特征變量。
2：選擇出數(shù)目較少的特征變量并且能夠充分的預(yù)測(cè)應(yīng)變量的結(jié)果。

其次一般特征選擇的步驟為：
1：初步估計(jì)和排序

a) 對(duì)隨機(jī)森林中的特征變量按照VI（Variable Importance）降序排序。
b) 確定刪除比例,從當(dāng)前的特征變量中剔除相應(yīng)比例不重要的指標(biāo)，從而得到一個(gè)新的特征集。
c) 用新的特征集建立新的隨機(jī)森林,并計(jì)算特征集中每個(gè)特征的VI,并排序。
d) 重復(fù)以上步驟,直到剩下m個(gè)特征。

2：根據(jù)1中得到的每個(gè)特征集和它們建立起來的隨機(jī)森林,計(jì)算對(duì)應(yīng)的袋外誤差率(OOB err),將袋外誤差率最低的特征集作為最后選定的特征集。

8、隨機(jī)森林的Python實(shí)現(xiàn)

利用Python的兩個(gè)模塊，分別為pandas和scikit-learn來實(shí)現(xiàn)隨機(jī)森林。

from sklearn.datasets import load_iris
from sklearn.ensemble import RandomForestClassifier
import pandas as pd
import numpy as np

iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['is_train'] = np.random.uniform(0, 1, len(df)) <= .75
df['species'] = pd.Factor(iris.target, iris.target_names)
df.head()

train, test = df[df['is_train']==True], df[df['is_train']==False]

features = df.columns[:4]
clf = RandomForestClassifier(n_jobs=2)
y, _ = pd.factorize(train['species'])
clf.fit(train[features], y)

preds = iris.target_names[clf.predict(test[features])]
pd.crosstab(test['species'], preds, rownames=['actual'], colnames=['preds'])

分類結(jié)果：

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn.cross_validation import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_moons, make_circles, make_classification
from sklearn.neighbors import KNeighborsClassifier
from sklearn.svm import SVC
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier, AdaBoostClassifier
from sklearn.naive_bayes import GaussianNB
from sklearn.lda import LDA
from sklearn.qda import QDA

h = .02  # step size in the mesh

names = ["Nearest Neighbors", "Linear SVM", "RBF SVM", "Decision Tree",
         "Random Forest", "AdaBoost", "Naive Bayes", "LDA", "QDA"]
classifiers = [
    KNeighborsClassifier(3),
    SVC(kernel="linear", C=0.025),
    SVC(gamma=2, C=1),
    DecisionTreeClassifier(max_depth=5),
    RandomForestClassifier(max_depth=5, n_estimators=10, max_features=1),
    AdaBoostClassifier(),
    GaussianNB(),
    LDA(),
    QDA()]

X, y = make_classification(n_features=2, n_redundant=0, n_informative=2,
                           random_state=1, n_clusters_per_class=1)
rng = np.random.RandomState(2)
X += 2 * rng.uniform(size=X.shape)
linearly_separable = (X, y)

datasets = [make_moons(noise=0.3, random_state=0),
            make_circles(noise=0.2, factor=0.5, random_state=1),
            linearly_separable
            ]

figure = plt.figure(figsize=(27, 9))
i = 1
# iterate over datasets
for ds in datasets:
    # preprocess dataset, split into training and test part
    X, y = ds
    X = StandardScaler().fit_transform(X)
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=.4)

    x_min, x_max = X[:, 0].min() - .5, X[:, 0].max() + .5
    y_min, y_max = X[:, 1].min() - .5, X[:, 1].max() + .5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))

    # just plot the dataset first
    cm = plt.cm.RdBu
    cm_bright = ListedColormap(['#FF0000', '#0000FF'])
    ax = plt.subplot(len(datasets), len(classifiers) + 1, i)
    # Plot the training points
    ax.scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap=cm_bright)
    # and testing points
    ax.scatter(X_test[:, 0], X_test[:, 1], c=y_test, cmap=cm_bright, alpha=0.6)
    ax.set_xlim(xx.min(), xx.max())
    ax.set_ylim(yy.min(), yy.max())
    ax.set_xticks(())
    ax.set_yticks(())
    i += 1

    # iterate over classifiers
    for name, clf in zip(names, classifiers):
        ax = plt.subplot(len(datasets), len(classifiers) + 1, i)
        clf.fit(X_train, y_train)
        score = clf.score(X_test, y_test)

        # Plot the decision boundary. For that, we will assign a color to each
        # point in the mesh [x_min, m_max]x[y_min, y_max].
        if hasattr(clf, "decision_function"):
            Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])
        else:
            Z = clf.predict_proba(np.c_[xx.ravel(), yy.ravel()])[:, 1]

        # Put the result into a color plot
        Z = Z.reshape(xx.shape)
        ax.contourf(xx, yy, Z, cmap=cm, alpha=.8)

        # Plot also the training points
        ax.scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap=cm_bright)
        # and testing points
        ax.scatter(X_test[:, 0], X_test[:, 1], c=y_test, cmap=cm_bright,
                   alpha=0.6)

        ax.set_xlim(xx.min(), xx.max())
        ax.set_ylim(yy.min(), yy.max())
        ax.set_xticks(())
        ax.set_yticks(())
        ax.set_title(name)
        ax.text(xx.max() - .3, yy.min() + .3, ('%.2f' % score).lstrip('0'),
                size=15, horizontalalignment='right')
        i += 1

figure.subplots_adjust(left=.02, right=.98)
plt.show()

分類結(jié)果

這里隨機(jī)生成了三個(gè)樣本集，分割面近似為月形、圓形和線形的。我們可以重點(diǎn)對(duì)比一下決策樹和隨機(jī)森林對(duì)樣本空間的分割：

1）從準(zhǔn)確率上可以看出，隨機(jī)森林在這三個(gè)測(cè)試集上都要優(yōu)于單棵決策樹，90%>85%，82%>80%，95%=95%；
2）從特征空間上直觀地可以看出，隨機(jī)森林比決策樹擁有更強(qiáng)的分割能力（非線性擬合能力）。

更多有關(guān)隨機(jī)森林的代碼：
　　1）Fortran版本
　　2）OpenCV版本
　　3）Matlab版本
　　4）R版本

9、理解

當(dāng)我們訓(xùn)練一個(gè)模型時(shí)，偏差和方差都得照顧到，漏掉一個(gè)都不行。對(duì)于Bagging算法來說，由于我們會(huì)并行地訓(xùn)練很多不同的分類器的目的就是降低這個(gè)方差(variance)

\mathbb{E}(h)

參考內(nèi)容

[1] Random Forest's homepage (by Leo Breiman and Adele Cutler)
[2] Introduction to Random forest - Simplified
[3] Comparing a Random Forest to a CART model (Part 2)
[4] Introduction to Random forest (博主：愛67)
[5] Python實(shí)現(xiàn)隨機(jī)森林
[6] 隨機(jī)森林之oob error估計(jì)
[7] 隨機(jī)森林
[8] Wikipedia-Random Forest
[9] Ensemble methods