機(jī)器學(xué)習(xí)九大算法

甯靜1 2019-05-02

展開全文

1. 隨機(jī)森林使用背景

1.1 隨機(jī)森林定義

隨機(jī)森林是一種比較新的機(jī)器學(xué)習(xí)模型。經(jīng)典的機(jī)器學(xué)習(xí)模型是神經(jīng)網(wǎng)絡(luò)，有半個多世紀(jì)的歷史了。神經(jīng)網(wǎng)絡(luò)預(yù)測精確，但是計算量很大。上世紀(jì)八十年代Breiman等人發(fā)明分類樹的算法（Breiman et al. 1984），通過反復(fù)二分?jǐn)?shù)據(jù)進(jìn)行分類或回歸，計算量大大降低。2001年Breiman把分類樹組合成隨機(jī)森林（Breiman 2001a），即在變量（列）的使用和數(shù)據(jù)（行）的使用上進(jìn)行隨機(jī)化，生成很多分類樹，再匯總分類樹的結(jié)果。隨機(jī)森林在運算量沒有顯著提高的前提下提高了預(yù)測精度。隨機(jī)森林對多元公線性不敏感，結(jié)果對缺失數(shù)據(jù)和非平衡的數(shù)據(jù)比較穩(wěn)健，可以很好地預(yù)測多達(dá)幾千個解釋變量的作用（Breiman 2001b），被譽(yù)為當(dāng)前最好的算法之一（Iverson et al. 2008）。

隨機(jī)森林顧名思義，是用隨機(jī)的方式建立一個森林，森林里面有很多的決策樹組成，隨機(jī)森林的每一棵決策樹之間是沒有關(guān)聯(lián)的。在得到森林之后，當(dāng)有一個新的輸入樣本進(jìn)入的時候，就讓森林中的每一棵決策樹分別進(jìn)行一下判斷，看看這個樣本應(yīng)該屬于哪一類（對于分類算法），然后看看哪一類被選擇最多，就預(yù)測這個樣本為那一類。

1.2 隨機(jī)森林優(yōu)點

隨機(jī)森林是一個最近比較火的算法，它有很多的優(yōu)點：

a. 在數(shù)據(jù)集上表現(xiàn)良好，兩個隨機(jī)性的引入，使得隨機(jī)森林不容易陷入過擬合

b. 在當(dāng)前的很多數(shù)據(jù)集上，相對其他算法有著很大的優(yōu)勢，兩個隨機(jī)性的引入，使得隨機(jī)森林具有很好的抗噪聲能力

c. 它能夠處理很高維度（feature很多）的數(shù)據(jù)，并且不用做特征選擇，對數(shù)據(jù)集的適應(yīng)能力強(qiáng)：既能處理離散型數(shù)據(jù)，也能處理連續(xù)型數(shù)據(jù)，數(shù)據(jù)集無需規(guī)范化

d. 可生成一個Proximities=（pij）矩陣，用于度量樣本之間的相似性： pij=aij/N, a_ij表示樣本i和j出現(xiàn)在隨機(jī)森林中同一個葉子結(jié)點的次數(shù)，N隨機(jī)森林中樹的顆數(shù)

e. 在創(chuàng)建隨機(jī)森林的時候，對generlization error使用的是無偏估計

f. 訓(xùn)練速度快，可以得到變量重要性排序（兩種：基于OOB誤分率的增加量和基于分裂時的GINI下降量

g. 在訓(xùn)練過程中，能夠檢測到feature間的互相影響

h. 容易做成并行化方法

i. 實現(xiàn)比較簡單

1.3 隨機(jī)森林應(yīng)用范圍

隨機(jī)森林主要應(yīng)用于回歸和分類。本文主要探討基于隨機(jī)森林的分類問題。隨機(jī)森林和使用決策樹作為基本分類器的（bagging）有些類似。以決策樹為基本模型的bagging在每次bootstrap放回抽樣之后，產(chǎn)生一棵決策樹，抽多少樣本就生成多少棵樹，在生成這些樹的時候沒有進(jìn)行更多的干預(yù)。而隨機(jī)森林也是進(jìn)行bootstrap抽樣，但它與bagging的區(qū)別是：在生成每棵樹的時候，每個節(jié)點變量都僅僅在隨機(jī)選出的少數(shù)變量中產(chǎn)生。因此，不但樣本是隨機(jī)的，連每個節(jié)點變量（Features）的產(chǎn)生都是隨機(jī)的。

許多研究表明，組合分類器比單一分類器的分類效果好，隨機(jī)森林（random forest）是一種利用多個分類樹對數(shù)據(jù)進(jìn)行判別與分類的方法，它在對數(shù)據(jù)進(jìn)行分類的同時，還可以給出各個變量（基因）的重要性評分，評估各個變量在分類中所起的作用。

2. 隨機(jī)森林方法理論介紹

2.1 隨機(jī)森林基本原理

隨機(jī)森林由LeoBreiman（2001）提出，它通過自助法（bootstrap）重采樣技術(shù)，從原始訓(xùn)練樣本集N中有放回地重復(fù)隨機(jī)抽取k個樣本生成新的訓(xùn)練樣本集合，然后根據(jù)自助樣本集生成k個分類樹組成隨機(jī)森林，新數(shù)據(jù)的分類結(jié)果按分類樹投票多少形成的分?jǐn)?shù)而定。其實質(zhì)是對決策樹算法的一種改進(jìn)，將多個決策樹合并在一起，每棵樹的建立依賴于一個獨立抽取的樣品，森林中的每棵樹具有相同的分布，分類誤差取決于每一棵樹的分類能力和它們之間的相關(guān)性。特征選擇采用隨機(jī)的方法去分裂每一個節(jié)點，然后比較不同情況下產(chǎn)生的誤差。能夠檢測到的內(nèi)在估計誤差、分類能力和相關(guān)性決定選擇特征的數(shù)目。單棵樹的分

類能力可能很小，但在隨機(jī)產(chǎn)生大量的決策樹后，一個測試樣品可以通過每一棵樹的分類結(jié)果經(jīng)統(tǒng)計后選擇最可能的分類。

2.2 隨機(jī)森林算法

2.2.1 決策樹

決策樹（decision tree）是一個樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）。其每個非葉節(jié)點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節(jié)點存放一個類別。使用決策樹進(jìn)行決策的過程就是從根節(jié)點開始，測試待分類項中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結(jié)果。

隨機(jī)森林是用隨機(jī)的方式建立一個森林，森林里面有很多的決策樹組成，隨機(jī)森林的每一棵決策樹之間是沒有關(guān)聯(lián)的。在得到森林之后，當(dāng)有一個新的輸入樣本進(jìn)入的時候，就讓森林中的每一棵決策樹分別進(jìn)行一下判斷，看看這個樣本應(yīng)該屬于哪一類，然后看看哪一類被選擇最多，就預(yù)測這個樣本為那一類。

在建立每一棵決策樹的過程中，有兩點需要注意采樣與完全分裂。首先是兩個隨機(jī)采樣的過程，random forest對輸入的數(shù)據(jù)要進(jìn)行行、列的采樣。對于行采樣，采用有放回的方式，也就是在采樣得到的樣本集合中，可能有重復(fù)的樣本。假設(shè)輸入樣本為N個，那么采樣的樣本也為N個。這樣使得在訓(xùn)練的時候，每一棵樹的輸入樣本都不是全部的樣本，使得相對不容易出現(xiàn)over-fitting。然后進(jìn)行列采樣，從M個feature中，選擇m個（m << M）。之后就是對采樣之后的數(shù)據(jù)使用完全分裂的方式建立出決策樹，這樣決策樹的某一個葉子節(jié)點要么是無法繼續(xù)分裂的，要么里面的所有樣本的都是指向的同一個分類。一般很多的決策樹算法都一個重要的步驟——剪枝，但是這里不這樣干，由于之前的兩個隨機(jī)采樣的過程保證了隨機(jī)性，所以就算不剪枝，也不會出現(xiàn)over-fitting。

決策樹中分裂屬性的兩個選擇度量：

1）信息增益

隨機(jī)森林模型任意樣本分類的期望信息：

a) I(s1,s2,……,sm)=

∑Pi log2(pi)(i=1..m)

其中，數(shù)據(jù)集為S，m為S的分類數(shù)目，Pi≈|Si/|S|，Ci為某分類標(biāo)號，Pi為任意樣本屬于Ci的概率，si為分類Ci上的樣本數(shù)

b) I(s1,s2,……,sm)越小，s1,s2,……,sm就越有序（越純），分類效果就越好。

c) 由屬性A劃分為子集的熵：

A為屬性，具有V個不同的取值， S被A 劃分為V 個子集s1,s2,……,sv，sij是子集sj中類Ci的樣本數(shù)。E(A)= ∑(s1j+ ……+smj)/s * I(s1j,……,smj)

d) 信息增益：Gain(A)= I(s1,s2,……,sm)

E(A)

e) 分裂屬性選擇規(guī)則：選擇具有最大信息增益的屬性為分裂屬性

2）基尼指數(shù)

a) 集合T包含N個類別的記錄，那么其Gini指標(biāo)就是p_j 類別j出現(xiàn)的頻率

b) 如果集合T分成m部分 N1 , N2 ,…, Nm 。那么這個分割的Gini就是

c)分裂屬性選擇規(guī)則：選擇具有最小Ginisplit的屬性為分裂屬性（對于每個屬性都要遍歷所有可能的分割方法）。

2.2.3 隨機(jī)森林模型的注意點

設(shè)有N個樣本，每個樣本有M個features，決策樹們其實都是隨機(jī)地接受n個樣本（對行隨機(jī)取樣）的m個feature（對列進(jìn)行隨機(jī)取樣），每顆決策樹的m個feature相同。每顆決策樹其實都是對特定的數(shù)據(jù)進(jìn)行學(xué)習(xí)歸納出分類方法，而隨機(jī)取樣可以保證有重復(fù)樣本被不同決策樹分類，這樣就可以對不同決策樹的分類能力做個評價。

2.2.4隨機(jī)森林實現(xiàn)過程

隨機(jī)森林中的每一棵分類樹為二叉樹，其生成遵循自頂向下的遞歸分裂原則，即從根節(jié)點開始依次對訓(xùn)練集進(jìn)行劃分；在二叉樹中，根節(jié)點包含全部訓(xùn)練數(shù)據(jù)，按照節(jié)點

純度最小原則，分裂為左節(jié)點和右節(jié)點，它們分別包含訓(xùn)練數(shù)據(jù)的一個子集，按照同樣的規(guī)則節(jié)點繼續(xù)分裂，直到滿足分支停止規(guī)則而停止生長。若節(jié)點n上的分類數(shù)據(jù)全部來自于同一類別，則此節(jié)點的

純度I(n)=0，

純度度量方法是Gini準(zhǔn)則，即假設(shè)P(X_j)是節(jié)點n上屬于X_j 類樣本個數(shù)占訓(xùn)練。

具體實現(xiàn)過程如下：

（1）原始訓(xùn)練集為N，應(yīng)用bootstrap法有放回地隨機(jī)抽取k個新的自助樣本集，并由此構(gòu)建k棵分類樹，每次未被抽到的樣本組成了k個袋外數(shù)據(jù)；

（2）設(shè)有m_all個變量，則在每一棵樹的每個節(jié)點處隨機(jī)抽取m_try個變量(m_try n m_all)，然后在m_try中選擇一個最具有分類能力的變量，變量分類的閾值通過檢查每一個分類點確定；

（3）每棵樹最大限度地生長, 不做任何修剪；

（4）將生成的多棵分類樹組成隨機(jī)森林，用隨機(jī)森林分類器對新的數(shù)據(jù)進(jìn)行判別與分類，分類結(jié)果按樹分類器的投票多少而定。

3. 隨機(jī)森林應(yīng)用

由于R中早就出現(xiàn)randomForest包了，本文主要討論R中隨機(jī)森林的應(yīng)用。兩個主要函數(shù)比較重要：randomForest用來構(gòu)建隨機(jī)森林模型，predict()使用訓(xùn)練后的隨機(jī)森林對新數(shù)據(jù)進(jìn)行預(yù)測。

3.1目標(biāo)

通過隨機(jī)森林的算法，根據(jù)一些特征，例如花瓣的長，寬，花萼的長寬。來預(yù)測植株的種類。

3.2 準(zhǔn)備的數(shù)據(jù)集

iris數(shù)據(jù)集，是R語言自帶的數(shù)據(jù)集。

Sepal.Length Sepal.Width Petal.Length Petal.Width Species
1 5.1 3.5 1.4 0.2 setosa
2 4.9 3.0 1.4 0.2 setosa
3 4.7 3.2 1.3 0.2 setosa
4 4.6 3.1 1.5 0.2 setosa
5 5.0 3.6 1.4 0.2 setosa
6 5.4 3.9 1.7 0.4 setosa
7 4.6 3.4 1.4 0.3 setosa
8 5.0 3.4 1.5 0.2 setosa
9 4.4 2.9 1.4 0.2 setosa
10 4.9 3.1 1.5 0.1 setosa
11 5.4 3.7 1.5 0.2 setosa
12 4.8 3.4 1.6 0.2 setosa
13 4.8 3.0 1.4 0.1 setosa
14 4.3 3.0 1.1 0.1 setosa
15 5.8 4.0 1.2 0.2 setosa
16 5.7 4.4 1.5 0.4 setosa
17 5.4 3.9 1.3 0.4 setosa
18 5.1 3.5 1.4 0.3 setosa
19 5.7 3.8 1.7 0.3 setosa
20 5.1 3.8 1.5 0.3 setosa
21 5.4 3.4 1.7 0.2 setosa
22 5.1 3.7 1.5 0.4 setosa
23 4.6 3.6 1.0 0.2 setosa
24 5.1 3.3 1.7 0.5 setosa
25 4.8 3.4 1.9 0.2 setosa
26 5.0 3.0 1.6 0.2 setosa
27 5.0 3.4 1.6 0.4 setosa
28 5.2 3.5 1.5 0.2 setosa
29 5.2 3.4 1.4 0.2 setosa
30 4.7 3.2 1.6 0.2 setosa
31 4.8 3.1 1.6 0.2 setosa
32 5.4 3.4 1.5 0.4 setosa
33 5.2 4.1 1.5 0.1 setosa
34 5.5 4.2 1.4 0.2 setosa
35 4.9 3.1 1.5 0.2 setosa
36 5.0 3.2 1.2 0.2 setosa
37 5.5 3.5 1.3 0.2 setosa
38 4.9 3.6 1.4 0.1 setosa
39 4.4 3.0 1.3 0.2 setosa
40 5.1 3.4 1.5 0.2 setosa
41 5.0 3.5 1.3 0.3 setosa
42 4.5 2.3 1.3 0.3 setosa
43 4.4 3.2 1.3 0.2 setosa
44 5.0 3.5 1.6 0.6 setosa
45 5.1 3.8 1.9 0.4 setosa
46 4.8 3.0 1.4 0.3 setosa
47 5.1 3.8 1.6 0.2 setosa
48 4.6 3.2 1.4 0.2 setosa
49 5.3 3.7 1.5 0.2 setosa
50 5.0 3.3 1.4 0.2 setosa
51 7.0 3.2 4.7 1.4 versicolor
52 6.4 3.2 4.5 1.5 versicolor
53 6.9 3.1 4.9 1.5 versicolor
54 5.5 2.3 4.0 1.3 versicolor
55 6.5 2.8 4.6 1.5 versicolor
56 5.7 2.8 4.5 1.3 versicolor
57 6.3 3.3 4.7 1.6 versicolor
58 4.9 2.4 3.3 1.0 versicolor
59 6.6 2.9 4.6 1.3 versicolor
60 5.2 2.7 3.9 1.4 versicolor
61 5.0 2.0 3.5 1.0 versicolor
62 5.9 3.0 4.2 1.5 versicolor
63 6.0 2.2 4.0 1.0 versicolor
64 6.1 2.9 4.7 1.4 versicolor
65 5.6 2.9 3.6 1.3 versicolor
66 6.7 3.1 4.4 1.4 versicolor
67 5.6 3.0 4.5 1.5 versicolor
68 5.8 2.7 4.1 1.0 versicolor
69 6.2 2.2 4.5 1.5 versicolor
70 5.6 2.5 3.9 1.1 versicolor
71 5.9 3.2 4.8 1.8 versicolor
72 6.1 2.8 4.0 1.3 versicolor
73 6.3 2.5 4.9 1.5 versicolor
74 6.1 2.8 4.7 1.2 versicolor
75 6.4 2.9 4.3 1.3 versicolor
76 6.6 3.0 4.4 1.4 versicolor
77 6.8 2.8 4.8 1.4 versicolor
78 6.7 3.0 5.0 1.7 versicolor
79 6.0 2.9 4.5 1.5 versicolor
80 5.7 2.6 3.5 1.0 versicolor
81 5.5 2.4 3.8 1.1 versicolor
82 5.5 2.4 3.7 1.0 versicolor
83 5.8 2.7 3.9 1.2 versicolor
84 6.0 2.7 5.1 1.6 versicolor
85 5.4 3.0 4.5 1.5 versicolor
86 6.0 3.4 4.5 1.6 versicolor
87 6.7 3.1 4.7 1.5 versicolor
88 6.3 2.3 4.4 1.3 versicolor
89 5.6 3.0 4.1 1.3 versicolor
90 5.5 2.5 4.0 1.3 versicolor
91 5.5 2.6 4.4 1.2 versicolor
92 6.1 3.0 4.6 1.4 versicolor
93 5.8 2.6 4.0 1.2 versicolor
94 5.0 2.3 3.3 1.0 versicolor
95 5.6 2.7 4.2 1.3 versicolor
96 5.7 3.0 4.2 1.2 versicolor
97 5.7 2.9 4.2 1.3 versicolor
98 6.2 2.9 4.3 1.3 versicolor
99 5.1 2.5 3.0 1.1 versicolor
100 5.7 2.8 4.1 1.3 versicolor
101 6.3 3.3 6.0 2.5 virginica
102 5.8 2.7 5.1 1.9 virginica
103 7.1 3.0 5.9 2.1 virginica
104 6.3 2.9 5.6 1.8 virginica
105 6.5 3.0 5.8 2.2 virginica
106 7.6 3.0 6.6 2.1 virginica
107 4.9 2.5 4.5 1.7 virginica
108 7.3 2.9 6.3 1.8 virginica
109 6.7 2.5 5.8 1.8 virginica
110 7.2 3.6 6.1 2.5 virginica
111 6.5 3.2 5.1 2.0 virginica
112 6.4 2.7 5.3 1.9 virginica
113 6.8 3.0 5.5 2.1 virginica
114 5.7 2.5 5.0 2.0 virginica
115 5.8 2.8 5.1 2.4 virginica
116 6.4 3.2 5.3 2.3 virginica
117 6.5 3.0 5.5 1.8 virginica
118 7.7 3.8 6.7 2.2 virginica
119 7.7 2.6 6.9 2.3 virginica
120 6.0 2.2 5.0 1.5 virginica
121 6.9 3.2 5.7 2.3 virginica
122 5.6 2.8 4.9 2.0 virginica
123 7.7 2.8 6.7 2.0 virginica
124 6.3 2.7 4.9 1.8 virginica
125 6.7 3.3 5.7 2.1 virginica
126 7.2 3.2 6.0 1.8 virginica
127 6.2 2.8 4.8 1.8 virginica
128 6.1 3.0 4.9 1.8 virginica
129 6.4 2.8 5.6 2.1 virginica
130 7.2 3.0 5.8 1.6 virginica
131 7.4 2.8 6.1 1.9 virginica
132 7.9 3.8 6.4 2.0 virginica
133 6.4 2.8 5.6 2.2 virginica
134 6.3 2.8 5.1 1.5 virginica
135 6.1 2.6 5.6 1.4 virginica
136 7.7 3.0 6.1 2.3 virginica
137 6.3 3.4 5.6 2.4 virginica
138 6.4 3.1 5.5 1.8 virginica
139 6.0 3.0 4.8 1.8 virginica
140 6.9 3.1 5.4 2.1 virginica
141 6.7 3.1 5.6 2.4 virginica
142 6.9 3.1 5.1 2.3 virginica
143 5.8 2.7 5.1 1.9 virginica
144 6.8 3.2 5.9 2.3 virginica
145 6.7 3.3 5.7 2.5 virginica
146 6.7 3.0 5.2 2.3 virginica
147 6.3 2.5 5.0 1.9 virginica
148 6.5 3.0 5.2 2.0 virginica
149 6.2 3.4 5.4 2.3 virginica
150 5.9 3.0 5.1 1.8 virginica

R 源代碼：

library( ”randomForest” )
data(iris)
set.seed(100)
ind=sample(2,nrow(iris),replace=TRUE，prob=c(0.8,0.2))
iris.rf=randomForest(Species~.,iris[ind==1,],ntree=50,nPerm=10,mtry=3,proximity=TRUE,importance=TRUE)
print(iris.rf)
iris.pred=predict( iris.rf,iris[ind==2,] )
table(observed=iris[ind==2,'Species'],predicted=iris.pred )

3.4 一些重要參數(shù)說明

randomForest()對訓(xùn)練集的數(shù)據(jù)進(jìn)行處理，生成決策樹

iris.rf=randomForest(Species~.,iris[ind==1,],ntree=50,nPerm=10,mtry=3,proximity=TRUE,importance=TRUE)

Species~.:代表需要預(yù)測的列，species是列的名稱。

iris[ind==1,]：生成決策樹的訓(xùn)練集

ntree：生成決策樹的數(shù)目

nperm：計算importance時的重復(fù)次數(shù)

mtry：選擇的分裂屬性的個數(shù)

proximity=TRUE：表示生成臨近矩陣

importance=TRUE：輸出分裂屬性的重要性

predict（）

iris.pred=predict( iris.rf,iris[ind==2,] )