1. 隨機(jī)森林使用背景 1.1 隨機(jī)森林定義 隨機(jī)森林是一種比較新的機(jī)器學(xué)習(xí)模型。經(jīng)典的機(jī)器學(xué)習(xí)模型是神經(jīng)網(wǎng)絡(luò),有半個(gè)多世紀(jì)的歷史了。神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)精確,但是計(jì)算量很大。上世紀(jì)八十年代Breiman等人發(fā)明分類樹的算法(Breiman et al. 1984),通過(guò)反復(fù)二分?jǐn)?shù)據(jù)進(jìn)行分類或回歸,計(jì)算量大大降低。2001年Breiman把分類樹組合成隨機(jī)森林(Breiman 2001a),即在變量(列)的使用和數(shù)據(jù)(行)的使用上進(jìn)行隨機(jī)化,生成很多分類樹,再匯總分類樹的結(jié)果。隨機(jī)森林在運(yùn)算量沒(méi)有顯著提高的前提下提高了預(yù)測(cè)精度。隨機(jī)森林對(duì)多元公線性不敏感,結(jié)果對(duì)缺失數(shù)據(jù)和非平衡的數(shù)據(jù)比較穩(wěn)健,可以很好地預(yù)測(cè)多達(dá)幾千個(gè)解釋變量的作用(Breiman 2001b),被譽(yù)為當(dāng)前最好的算法之一(Iverson et al. 2008)。 隨機(jī)森林顧名思義,是用隨機(jī)的方式建立一個(gè)森林,森林里面有很多的決策樹組成,隨機(jī)森林的每一棵決策樹之間是沒(méi)有關(guān)聯(lián)的。在得到森林之后,當(dāng)有一個(gè)新的輸入樣本進(jìn)入的時(shí)候,就讓森林中的每一棵決策樹分別進(jìn)行一下判斷,看看這個(gè)樣本應(yīng)該屬于哪一類(對(duì)于分類算法),然后看看哪一類被選擇最多,就預(yù)測(cè)這個(gè)樣本為那一類。 1.2 隨機(jī)森林優(yōu)點(diǎn) 隨機(jī)森林是一個(gè)最近比較火的算法,它有很多的優(yōu)點(diǎn): a. 在數(shù)據(jù)集上表現(xiàn)良好,兩個(gè)隨機(jī)性的引入,使得隨機(jī)森林不容易陷入過(guò)擬合 b. 在當(dāng)前的很多數(shù)據(jù)集上,相對(duì)其他算法有著很大的優(yōu)勢(shì),兩個(gè)隨機(jī)性的引入,使得隨機(jī)森林具有很好的抗噪聲能力 c. 它能夠處理很高維度(feature很多)的數(shù)據(jù),并且不用做特征選擇,對(duì)數(shù)據(jù)集的適應(yīng)能力強(qiáng):既能處理離散型數(shù)據(jù),也能處理連續(xù)型數(shù)據(jù),數(shù)據(jù)集無(wú)需規(guī)范化 d. 可生成一個(gè)Proximities=(pij)矩陣,用于度量樣本之間的相似性: pij=aij/N, aij表示樣本i和j出現(xiàn)在隨機(jī)森林中同一個(gè)葉子結(jié)點(diǎn)的次數(shù),N隨機(jī)森林中樹的顆數(shù) e. 在創(chuàng)建隨機(jī)森林的時(shí)候,對(duì)generlization error使用的是無(wú)偏估計(jì) f. 訓(xùn)練速度快,可以得到變量重要性排序(兩種:基于OOB誤分率的增加量和基于分裂時(shí)的GINI下降量 g. 在訓(xùn)練過(guò)程中,能夠檢測(cè)到feature間的互相影響 h. 容易做成并行化方法 i. 實(shí)現(xiàn)比較簡(jiǎn)單 1.3 隨機(jī)森林應(yīng)用范圍 隨機(jī)森林主要應(yīng)用于回歸和分類。本文主要探討基于隨機(jī)森林的分類問(wèn)題。隨機(jī)森林和使用決策樹作為基本分類器的(bagging)有些類似。以決策樹為基本模型的bagging在每次bootstrap放回抽樣之后,產(chǎn)生一棵決策樹,抽多少樣本就生成多少棵樹,在生成這些樹的時(shí)候沒(méi)有進(jìn)行更多的干預(yù)。而隨機(jī)森林也是進(jìn)行bootstrap抽樣,但它與bagging的區(qū)別是:在生成每棵樹的時(shí)候,每個(gè)節(jié)點(diǎn)變量都僅僅在隨機(jī)選出的少數(shù)變量中產(chǎn)生。因此,不但樣本是隨機(jī)的,連每個(gè)節(jié)點(diǎn)變量(Features)的產(chǎn)生都是隨機(jī)的。 許多研究表明, 組合分類器比單一分類器的分類效果好,隨機(jī)森林(random forest)是一種利用多個(gè)分類樹對(duì)數(shù)據(jù)進(jìn)行判別與分類的方法,它在對(duì)數(shù)據(jù)進(jìn)行分類的同時(shí),還可以給出各個(gè)變量(基因)的重要性評(píng)分,評(píng)估各個(gè)變量在分類中所起的作用。 2. 隨機(jī)森林方法理論介紹 2.1 隨機(jī)森林基本原理 隨機(jī)森林由LeoBreiman(2001)提出,它通過(guò)自助法(bootstrap)重采樣技術(shù),從原始訓(xùn)練樣本集N中有放回地重復(fù)隨機(jī)抽取k個(gè)樣本生成新的訓(xùn)練樣本集合,然后根據(jù)自助樣本集生成k個(gè)分類樹組成隨機(jī)森林,新數(shù)據(jù)的分類結(jié)果按分類樹投票多少形成的分?jǐn)?shù)而定。其實(shí)質(zhì)是對(duì)決策樹算法的一種改進(jìn),將多個(gè)決策樹合并在一起,每棵樹的建立依賴于一個(gè)獨(dú)立抽取的樣品,森林中的每棵樹具有相同的分布,分類誤差取決于每一棵樹的分類能力和它們之間的相關(guān)性。特征選擇采用隨機(jī)的方法去分裂每一個(gè)節(jié)點(diǎn),然后比較不同情況下產(chǎn)生的誤差。能夠檢測(cè)到的內(nèi)在估計(jì)誤差、分類能力和相關(guān)性決定選擇特征的數(shù)目。單棵樹的分 類能力可能很小,但在隨機(jī)產(chǎn)生大量的決策樹后,一個(gè)測(cè)試樣品可以通過(guò)每一棵樹的分類結(jié)果經(jīng)統(tǒng)計(jì)后選擇最可能的分類。 2.2 隨機(jī)森林算法 2.2.1 決策樹 決策樹(decision tree)是一個(gè)樹結(jié)構(gòu)(可以是二叉樹或非二叉樹)。其每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的測(cè)試,每個(gè)分支代表這個(gè)特征屬性在某個(gè)值域上的輸出,而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別。使用決策樹進(jìn)行決策的過(guò)程就是從根節(jié)點(diǎn)開始,測(cè)試待分類項(xiàng)中相應(yīng)的特征屬性,并按照其值選擇輸出分支,直到到達(dá)葉子節(jié)點(diǎn),將葉子節(jié)點(diǎn)存放的類別作為決策結(jié)果。 隨機(jī)森林是用隨機(jī)的方式建立一個(gè)森林,森林里面有很多的決策樹組成,隨機(jī)森林的每一棵決策樹之間是沒(méi)有關(guān)聯(lián)的。在得到森林之后,當(dāng)有一個(gè)新的輸入樣本進(jìn)入的時(shí)候,就讓森林中的每一棵決策樹分別進(jìn)行一下判斷,看看這個(gè)樣本應(yīng)該屬于哪一類,然后看看哪一類被選擇最多,就預(yù)測(cè)這個(gè)樣本為那一類。 在建立每一棵決策樹的過(guò)程中,有兩點(diǎn)需要注意采樣與完全分裂。首先是兩個(gè)隨機(jī)采樣的過(guò)程,random forest對(duì)輸入的數(shù)據(jù)要進(jìn)行行、列的采樣。對(duì)于行采樣,采用有放回的方式,也就是在采樣得到的樣本集合中,可能有重復(fù)的樣本。假設(shè)輸入樣本為N個(gè),那么采樣的樣本也為N個(gè)。這樣使得在訓(xùn)練的時(shí)候,每一棵樹的輸入樣本都不是全部的樣本,使得相對(duì)不容易出現(xiàn)over-fitting。然后進(jìn)行列采樣,從M個(gè)feature中,選擇m個(gè)(m << M)。之后就是對(duì)采樣之后的數(shù)據(jù)使用完全分裂的方式建立出決策樹,這樣決策樹的某一個(gè)葉子節(jié)點(diǎn)要么是無(wú)法繼續(xù)分裂的,要么里面的所有樣本的都是指向的同一個(gè)分類。一般很多的決策樹算法都一個(gè)重要的步驟——剪枝,但是這里不這樣干,由于之前的兩個(gè)隨機(jī)采樣的過(guò)程保證了隨機(jī)性,所以就算不剪枝,也不會(huì)出現(xiàn)over-fitting。 決策樹中分裂屬性的兩個(gè)選擇度量: 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)號(hào),Pi為任意樣本屬于Ci的概率,si為分類Ci上的樣本數(shù) b) I(s1,s2,……,sm)越小,s1,s2,……,sm就越有序(越純),分類效果就越好。 c) 由屬性A劃分為子集的熵: A為屬性,具有V個(gè)不同的取值, S被A 劃分為V 個(gè)子集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個(gè)類別的記錄,那么其Gini指標(biāo)就是pj 類別j出現(xiàn)的頻率 b) 如果集合T分成m部分 N1 , N2 ,…, Nm 。那么這個(gè)分割的Gini就是 c)分裂屬性選擇規(guī)則:選擇具有最小Ginisplit的屬性為分裂屬性(對(duì)于每個(gè)屬性都要遍歷所有可能的分割方法)。 2.2.3 隨機(jī)森林模型的注意點(diǎn) 設(shè)有N個(gè)樣本,每個(gè)樣本有M個(gè)features,決策樹們其實(shí)都是隨機(jī)地接受n個(gè)樣本(對(duì)行隨機(jī)取樣)的m個(gè)feature(對(duì)列進(jìn)行隨機(jī)取樣),每顆決策樹的m個(gè)feature相同。每顆決策樹其實(shí)都是對(duì)特定的數(shù)據(jù)進(jìn)行學(xué)習(xí)歸納出分類方法,而隨機(jī)取樣可以保證有重復(fù)樣本被不同決策樹分類,這樣就可以對(duì)不同決策樹的分類能力做個(gè)評(píng)價(jià)。 2.2.4隨機(jī)森林實(shí)現(xiàn)過(guò)程 隨機(jī)森林中的每一棵分類樹為二叉樹,其生成遵循自頂向下的遞歸分裂原則,即從根節(jié)點(diǎn)開始依次對(duì)訓(xùn)練集進(jìn)行劃分;在二叉樹中,根節(jié)點(diǎn)包含全部訓(xùn)練數(shù)據(jù), 按照節(jié)點(diǎn) 純度最小原則,分裂為左節(jié)點(diǎn)和右節(jié)點(diǎn),它們分別包含訓(xùn)練數(shù)據(jù)的一個(gè)子集,按照同樣的規(guī)則節(jié)點(diǎn)繼續(xù)分裂,直到滿足分支停止規(guī)則而停止生長(zhǎng)。若節(jié)點(diǎn)n上的分類數(shù)據(jù)全部來(lái)自于同一類別,則此節(jié)點(diǎn)的 純度I(n)=0, 純度度量方法是Gini準(zhǔn)則,即假設(shè)P(Xj)是節(jié)點(diǎn)n上屬于Xj 類樣本個(gè)數(shù)占訓(xùn)練。 具體實(shí)現(xiàn)過(guò)程如下: (1)原始訓(xùn)練集為N,應(yīng)用bootstrap法有放回地隨機(jī)抽取k個(gè)新的自助樣本集,并由此構(gòu)建k棵分類樹,每次未被抽到的樣本組成了k個(gè)袋外數(shù)據(jù); (2)設(shè)有mall個(gè)變量,則在每一棵樹的每個(gè)節(jié)點(diǎn)處隨機(jī)抽取mtry個(gè)變量(mtry n mall),然后在mtry中選擇一個(gè)最具有分類能力的變量,變量分類的閾值通過(guò)檢查每一個(gè)分類點(diǎn)確定; (3)每棵樹最大限度地生長(zhǎng), 不做任何修剪; (4)將生成的多棵分類樹組成隨機(jī)森林,用隨機(jī)森林分類器對(duì)新的數(shù)據(jù)進(jìn)行判別與分類,分類結(jié)果按樹分類器的投票多少而定。 3. 隨機(jī)森林應(yīng)用 由于R中早就出現(xiàn)randomForest包了,本文主要討論R中隨機(jī)森林的應(yīng)用。兩個(gè)主要函數(shù)比較重要:randomForest用來(lái)構(gòu)建隨機(jī)森林模型,predict()使用訓(xùn)練后的隨機(jī)森林對(duì)新數(shù)據(jù)進(jìn)行預(yù)測(cè)。 3.1目標(biāo) 通過(guò)隨機(jī)森林的算法,根據(jù)一些特征,例如花瓣的長(zhǎng),寬,花萼的長(zhǎng)寬。來(lái)預(yù)測(cè)植株的種類。 3.2 準(zhǔn)備的數(shù)據(jù)集 iris數(shù)據(jù)集,是R語(yǔ)言自帶的數(shù)據(jù)集。
R 源代碼:
3.4 一些重要參數(shù)說(shuō)明 randomForest()對(duì)訓(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ù)測(cè)的列,species是列的名稱。 iris[ind==1,]:生成決策樹的訓(xùn)練集 ntree:生成決策樹的數(shù)目 nperm:計(jì)算importance時(shí)的重復(fù)次數(shù) mtry:選擇的分裂屬性的個(gè)數(shù) proximity=TRUE:表示生成臨近矩陣 importance=TRUE:輸出分裂屬性的重要性 predict() iris.pred=predict( iris.rf,iris[ind==2,] ) iris.rf:表示生成的隨機(jī)森林模型 iris[ind==2,] :進(jìn)行預(yù)測(cè)的測(cè)試集 3.5預(yù)測(cè)結(jié)果
|
|
來(lái)自: 甯靜1 > 《數(shù)據(jù)分析算法及模型》