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

作為新興起的、高度靈活的一種機(jī)器學(xué)習(xí)算法，隨機(jī)森林（Random Forest，簡稱RF）擁有廣泛的應(yīng)用前景，從市場營銷到醫(yī)療保健保險(xiǎn)，既可以用來做市場營銷模擬的建模，統(tǒng)計(jì)客戶來源，保留和流失，也可用來預(yù)測疾病的風(fēng)險(xiǎn)和病患者的易感性。最初，我是在參加校外競賽時(shí)接觸到隨機(jī)森林算法的。最近幾年的國內(nèi)外大賽，包括2013年百度校園電影推薦系統(tǒng)大賽、2014年阿里巴巴天池大數(shù)據(jù)競賽以及Kaggle數(shù)據(jù)科學(xué)競賽，參賽者對隨機(jī)森林的使用占有相當(dāng)高的比例。此外，據(jù)我的個(gè)人了解來看，一大部分成功進(jìn)入答辯的隊(duì)伍也都選擇了Random Forest 或者 GBDT 算法。所以可以看出，Random Forest在準(zhǔn)確率方面還是相當(dāng)有優(yōu)勢的。

那說了這么多，那隨機(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)在針對的是分類問題），那么對于一個(gè)輸入樣本，N棵樹會(huì)有N個(gè)分類結(jié)果。而隨機(jī)森林集成了所有的分類投票結(jié)果，將投票次數(shù)最多的類別指定為最終的輸出，這就是一種最簡單的 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；

• 能夠評估各個(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；

• 對于缺省值問題也能夠獲得很好得結(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ǔ)知識

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

1）信息、熵以及信息增益的概念

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

引用香農(nóng)的話來說，信息是用來消除隨機(jī)不確定性的東西。當(dāng)然這句話雖然經(jīng)典，但是還是很難去搞明白這種東西到底是個(gè)什么樣，可能在不同的地方來說，指的東西又不一樣。對于機(jī)器學(xué)習(xí)中的決策樹而言，如果帶分類的事物集合可以劃分為多個(gè)類別當(dāng)中，則某個(gè)類（xi）的信息可以定義如下:

I(x)用來表示隨機(jī)變量的信息，p(xi)指是當(dāng)xi發(fā)生時(shí)的概率。

熵是用來度量不確定性的，當(dāng)熵越大，X=xi的不確定性越大，反之越小。對于機(jī)器學(xué)習(xí)中的分類問題而言，熵越大即這個(gè)類別的不確定性更大，反之越小。

信息增益在決策樹算法中是用來選擇特征的指標(biāo)，信息增益越大，則這個(gè)特征的選擇性越好。

這方面的內(nèi)容不再細(xì)述，感興趣的同學(xué)可以看信息&熵&信息增益這篇博文。

2）決策樹

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

3）集成學(xué)習(xí)

集成學(xué)習(xí)通過建立幾個(gè)模型組合的來解決單一預(yù)測問題。它的工作原理是生成多個(gè)分類器/模型，各自獨(dú)立地學(xué)習(xí)和作出預(yù)測。這些預(yù)測最后結(jié)合成單預(yù)測，因此優(yōu)于任何一個(gè)單分類的做出預(yù)測。

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

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

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

1）如果訓(xùn)練集大小為N，對于每棵樹而言，隨機(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)練樣本都是不同的，都是沒有交集的，這樣每棵樹都是"有偏的"，都是絕對"片面的"（當(dāng)然這樣說可能不對），也就是說每棵樹訓(xùn)練出來都是有很大的差異的；而隨機(jī)森林最后分類取決于多棵樹（弱分類器）的投票表決，這種表決應(yīng)該是"求同"，因此使用完全不同的訓(xùn)練集來訓(xùn)練每棵樹這樣對最終分類結(jié)果是沒有幫助的，這樣無異于是"盲人摸象"。

2）如果每個(gè)樣本的特征維度為M，指定一個(gè)常數(shù)m<

3）每棵樹都盡最大程度的生長，并且沒有剪枝過程。

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

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

• 森林中任意兩棵樹的相關(guān)性：相關(guān)性越大，錯(cuò)誤率越大；

• 森林中每棵樹的分類能力：每棵樹的分類能力越強(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)就是，沒有必要對它進(jìn)行交叉驗(yàn)證或者用一個(gè)獨(dú)立的測試集來獲得誤差的一個(gè)無偏估計(jì)。它可以在內(nèi)部進(jìn)行評估，也就是說在生成的過程中就可以對誤差建立一個(gè)無偏估計(jì)。

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

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

（note：以樣本為單位）

1）對每個(gè)樣本，計(jì)算它作為oob樣本的樹對它的分類情況（約1/3的樹）；

2）然后以簡單多數(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è)簡單例子

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

收入層次 :

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樹對應(yīng)一個(gè)不同的特征）。

CART 1 : Variable Age

CART 2 : VariableGender

CART 3 : Variable Education

CART 4 : VariableResidence

CART 5 : VariableIndustry

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

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

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

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

回到頂部

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

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

1. from sklearn.datasets import load_iris

2. from sklearn.ensemble import RandomForestClassifier

3. import pandas as pd

4. import numpy as np

5. iris = load_iris()

6. df = pd.DataFrame(iris.data, columns=iris.feature_names)

7. df['is_train'] = np.random.uniform(0, 1, len(df)) <= .75

8. df['species'] = pd.Factor(iris.target, iris.target_names)

9. df.head()

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

11. features = df.columns[:4]

12. clf = RandomForestClassifier(n_jobs=2)

13. y, _ = pd.factorize(train['species'])

14. clf.fit(train[features], y)

15. preds = iris.target_names[clf.predict(test[features])]

16. pd.crosstab(test['species'], preds, rownames=['actual'], colnames=['preds'])

分類結(jié)果：

與其他機(jī)器學(xué)習(xí)分類算法進(jìn)行對比：

1. import numpy as np

2. import matplotlib.pyplot as plt

3. from matplotlib.colors import ListedColormap

4. from sklearn.cross_validation import train_test_split

5. from sklearn.preprocessing import StandardScaler

6. from sklearn.datasets import make_moons, make_circles, make_classification

7. from sklearn.neighbors import KNeighborsClassifier

8. from sklearn.svm import SVC

9. from sklearn.tree import DecisionTreeClassifier

10. from sklearn.ensemble import RandomForestClassifier, AdaBoostClassifier

11. from sklearn.naive_bayes import GaussianNB

12. from sklearn.lda import LDA

13. from sklearn.qda import QDA

14. h = .02 # step size in the mesh

15. names = ["Nearest Neighbors", "Linear SVM", "RBF SVM", "Decision Tree",

16. "Random Forest", "AdaBoost", "Naive Bayes", "LDA", "QDA"]

17. classifiers = [

18. KNeighborsClassifier(3),

19. SVC(kernel="linear", C=0.025),

20. SVC(gamma=2, C=1),

21. DecisionTreeClassifier(max_depth=5),

22. RandomForestClassifier(max_depth=5, n_estimators=10, max_features=1),

23. AdaBoostClassifier(),

24. GaussianNB(),

25. LDA(),

26. QDA()]

27. X, y = make_classification(n_features=2, n_redundant=0, n_informative=2,

28. random_state=1, n_clusters_per_class=1)

29. rng = np.random.RandomState(2)

30. X += 2 * rng.uniform(size=X.shape)

31. linearly_separable = (X, y)

32. datasets = [make_moons(noise=0.3, random_state=0),

33. make_circles(noise=0.2, factor=0.5, random_state=1),

34. linearly_separable

35. ]

36. figure = plt.figure(figsize=(27, 9))

37. i = 1

38. # iterate over datasets

39. for ds in datasets:

40. # preprocess dataset, split into training and test part

41. X, y = ds

42. X = StandardScaler().fit_transform(X)

43. X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=.4)

44. x_min, x_max = X[:, 0].min() - .5, X[:, 0].max() + .5

45. y_min, y_max = X[:, 1].min() - .5, X[:, 1].max() + .5

46. xx, yy = np.meshgrid(np.arange(x_min, x_max, h),

47. np.arange(y_min, y_max, h))

48. # just plot the dataset first

49. cm = plt.cm.RdBu

50. cm_bright = ListedColormap(['#FF0000', '#0000FF'])

51. ax = plt.subplot(len(datasets), len(classifiers) + 1, i)

52. # Plot the training points

53. ax.scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap=cm_bright)

54. # and testing points

55. ax.scatter(X_test[:, 0], X_test[:, 1], c=y_test, cmap=cm_bright, alpha=0.6)

56. ax.set_xlim(xx.min(), xx.max())

57. ax.set_ylim(yy.min(), yy.max())

58. ax.set_xticks(())

59. ax.set_yticks(())

60. i += 1

61. # iterate over classifiers

62. for name, clf in zip(names, classifiers):

63. ax = plt.subplot(len(datasets), len(classifiers) + 1, i)

64. clf.fit(X_train, y_train)

65. score = clf.score(X_test, y_test)

66. # Plot the decision boundary. For that, we will assign a color to each

67. # point in the mesh [x_min, m_max]x[y_min, y_max].

68. if hasattr(clf, "decision_function"):

69. Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])

70. else:

71. Z = clf.predict_proba(np.c_[xx.ravel(), yy.ravel()])[:, 1]

72. # Put the result into a color plot

73. Z = Z.reshape(xx.shape)

74. ax.contourf(xx, yy, Z, cmap=cm, alpha=.8)

75. # Plot also the training points

76. ax.scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap=cm_bright)

77. # and testing points

78. ax.scatter(X_test[:, 0], X_test[:, 1], c=y_test, cmap=cm_bright,

79. alpha=0.6)

80. ax.set_xlim(xx.min(), xx.max())

81. ax.set_ylim(yy.min(), yy.max())

82. ax.set_xticks(())

83. ax.set_yticks(())

84. ax.set_title(name)

85. ax.text(xx.max() - .3, yy.min() + .3, ('%.2f' % score).lstrip('0'),

86. size=15, horizontalalignment='right')

87. i += 1

88. figure.subplots_adjust(left=.02, right=.98)

89. plt.show()

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

1）從準(zhǔn)確率上可以看出，隨機(jī)森林在這三個(gè)測試集上都要優(yōu)于單棵決策樹，90%>85%，82%>80%，95%=95%；

2）從特征空間上直觀地可以看出，隨機(jī)森林比決策樹擁有更強(qiáng)的分割能力（非線性擬合能力）。

更多有關(guān)隨機(jī)森林的代碼：

1）Fortran版本

2）OpenCV版本

3）Matlab版本

4）R版本

審核編輯 ：李倩