隨機(jī)森林

隨機(jī)森林的基本思想：通過(guò)自助法(boot-strap)重采樣技術(shù),不斷生成訓(xùn)練樣本和測(cè)試樣本,由訓(xùn)練樣本生成多個(gè)分類樹組成隨機(jī)森林,測(cè)試數(shù)據(jù)的分類結(jié)果按分類樹投票多少形成的分?jǐn)?shù)而定。

隨機(jī)森林有兩個(gè)重要參數(shù)：一是樹節(jié)點(diǎn)預(yù)選的變量個(gè)數(shù)；二是隨機(jī)森林中樹的個(gè)數(shù)。隨機(jī)森林分類器組合AdaBoosting(AdaptiveBoosting)對(duì)每個(gè)樣本賦予一個(gè)權(quán)重，代表該樣本被當(dāng)前分類器選入訓(xùn)練集的概率，并根據(jù)預(yù)測(cè)函數(shù)的輸出與期望輸出的差異調(diào)整權(quán)重：如某個(gè)樣本點(diǎn)已被正確分類，則它的權(quán)重減小，否則，它的權(quán)重增大；通過(guò)這種方式，使得學(xué)習(xí)算法能集中學(xué)習(xí)較難判別的樣本。經(jīng)過(guò)T輪訓(xùn)練，得到T個(gè)分類函數(shù){f1,f2,…,fT}及對(duì)應(yīng)的權(quán)重{1,2,…,T}，最終的分類規(guī)則為加權(quán)投票法Bagging(Breiman,1996)在訓(xùn)練的每一輪中，均從原始樣本集S中有放回地隨機(jī)抽取訓(xùn)練樣本集T（T的樣本個(gè)數(shù)同S），這樣一個(gè)初始樣本在某輪訓(xùn)練中可能出現(xiàn)多次或根本不出現(xiàn)（S中每個(gè)樣本未被抽取的概率為(1-1/|S|)|S|≈0.368，當(dāng)|S|很大時(shí)）。最終的分類規(guī)則為簡(jiǎn)單多數(shù)投票法或簡(jiǎn)單平均法隨機(jī)森林算法隨機(jī)森林算法是LeoBreiman于2001年提出的一種新型分類和預(yù)測(cè)模型,它具有需要調(diào)整的參數(shù)較少、不必?fù)?dān)心過(guò)度擬合、分類速度很快,能高效處理大樣本數(shù)據(jù)、能估計(jì)哪個(gè)特征在分類中更重要以及較強(qiáng)的抗噪音能力等特點(diǎn),因此,在基因芯片數(shù)據(jù)挖掘、代謝途徑分析及藥物篩選等生物學(xué)領(lǐng)域得到應(yīng)用并取得了較好的效果。該方法是基于決策樹（decisiontree）的分類器集成算法。自助法重采樣在統(tǒng)計(jì)量重采樣技術(shù)中，一種新方法是自助法（bootstrap）。自助法是從原始的樣本容量為N的訓(xùn)練樣本集合中隨機(jī)抽取N個(gè)樣本生成新的訓(xùn)練樣本集，抽樣方法為有放回抽樣，這樣重新采樣的數(shù)據(jù)集不可避免地存在著重復(fù)的樣本。獨(dú)立抽樣k次，生成k個(gè)相互獨(dú)立的自助樣本集。隨機(jī)森林算法基本原理隨機(jī)森林是通過(guò)一種新的自助法重采樣技術(shù)生成很多個(gè)樹分類器,其步驟如下：

1.從原始訓(xùn)練數(shù)據(jù)中生成ｋ個(gè)自助樣本集,每個(gè)自助樣本集是每棵分類樹的全部訓(xùn)練數(shù)據(jù)。

2.每個(gè)自助樣本集生長(zhǎng)為單棵分類樹。在樹的每個(gè)節(jié)點(diǎn)處從Ｍ個(gè)特征中隨機(jī)挑選ｍ個(gè)特征（ｍ《Ｍ）,按照節(jié)點(diǎn)不純度最小的原則從這個(gè)ｍ特征中選出一個(gè)特征進(jìn)行分支生長(zhǎng)。這棵分類樹進(jìn)行充分生長(zhǎng),使每個(gè)節(jié)點(diǎn)的不純度達(dá)到最小,不進(jìn)行通常的剪枝操作。根據(jù)生成的多個(gè)樹分類器對(duì)新的數(shù)據(jù)進(jìn)行預(yù)測(cè),分類結(jié)果按每個(gè)樹分類器的投票多少而定。隨機(jī)森林通過(guò)在每個(gè)節(jié)點(diǎn)處隨機(jī)選擇特征進(jìn)行分支，最小化了各棵分類樹之間的相關(guān)性，提高了分類精確度。因?yàn)槊靠脴涞纳L(zhǎng)很快，所以隨機(jī)森林的分類速度很快，并且很容易實(shí)現(xiàn)并行化。隨機(jī)森林分類性能的主要因素森林中單顆樹的分類強(qiáng)度（Strength）：每顆樹的分類強(qiáng)度越大，則隨機(jī)森林的分類性能越好。森林中樹之間的相關(guān)度（Correlation）：樹之間的相關(guān)度越大，則隨機(jī)森林的分類性能越差。ID3和cart的算法區(qū)別CART是L.Breiman等人在1984年提出的決策樹算法，其原理與ID3相似，在CART中提出了雜度削減的概念，按雜度削減最大分裂節(jié)點(diǎn)生長(zhǎng)決策樹，與ID3不同的是，CART最終生成二叉樹，然后利用重采技術(shù)進(jìn)行誤差估計(jì)和樹剪枝，然后選擇最優(yōu)作為最終構(gòu)建的決策樹。這些算法均要求訓(xùn)練集全部或一部分在分類的過(guò)程中一直駐留在內(nèi)存中。12ID3方法基本思想首先找出最有判別力的屬性，把樣例分成多個(gè)子集，每個(gè)子集又選擇最有判別力的屬性進(jìn)行劃分，一直進(jìn)行到所有子集僅包含同一類型的數(shù)據(jù)為止。最后得到一棵決策樹。J.R.Quinlan的工作主要是引進(jìn)了信息論中的信息增益，他將其稱為信息增益（informationgain），作為屬性判別能力的度量，設(shè)計(jì)了構(gòu)造決策樹的遞歸算法。13二、ID3算法⒈對(duì)當(dāng)前例子集合，計(jì)算各屬性的信息增益；⒉選擇信息增益最大的屬性Ak；⒊把在Ak處取值相同的例子歸于同一子集，Ak取幾個(gè)值就得幾個(gè)子集；⒋對(duì)既含正例又含反例的子集，遞歸調(diào)用建樹算法；⒌若子集僅含正例或反例，對(duì)應(yīng)分枝標(biāo)上P或N，返回調(diào)用處。ID3在建樹時(shí)，每個(gè)節(jié)點(diǎn)僅含一個(gè)屬性，是一種單變?cè)乃惴?，屬性間的相關(guān)性強(qiáng)調(diào)不夠。雖然它將多個(gè)屬性用一棵樹連在一起，但聯(lián)系還是松散的。14（4）ID3對(duì)噪聲較為敏感。關(guān)于什么是噪聲，Quinlan的定義是訓(xùn)練例子中的錯(cuò)誤就是噪聲。它包含兩方面，一是屬性值取錯(cuò)，二是類別給錯(cuò)。當(dāng)訓(xùn)練集增加時(shí)，ID3的決策樹會(huì)隨之變化。在建樹過(guò)程中，各屬性的信息增益會(huì)隨例子的增加而改變，從而使決策樹也變化。這對(duì)漸近學(xué)習(xí)（即訓(xùn)練例子不斷增加）是不方便的。

CART二元?jiǎng)澐侄鏄洳灰桩a(chǎn)生數(shù)據(jù)碎片，精確度往往也會(huì)高于多叉樹，所以在CART算法中，采用了二元?jiǎng)澐植患冃远攘糠诸惸繕?biāo)：Gini指標(biāo)、Towing、orderTowing連續(xù)目標(biāo)：最小平方殘差、最小絕對(duì)殘差剪枝：用獨(dú)立的驗(yàn)證數(shù)據(jù)集對(duì)訓(xùn)練集生長(zhǎng)的樹進(jìn)行剪枝CART-回歸樹樣本：(X,y)y為分類=>分類樹y為實(shí)數(shù)=>回歸樹設(shè)t代表樹的某個(gè)節(jié)點(diǎn)，t中的樣本集合為：{(X1,y1),(X2,y2)…}，應(yīng)變量為實(shí)數(shù)，N(t)是節(jié)點(diǎn)t中的樣本個(gè)數(shù)。節(jié)點(diǎn)t的應(yīng)變量的均值：節(jié)點(diǎn)t內(nèi)的平方殘差最小化(squaredresidualsminimizationalgorithm)：CART_regression(DataSet,featureList,alpha,delta)：創(chuàng)建根節(jié)點(diǎn)R如果當(dāng)前DataSet中的數(shù)據(jù)的值都相同，則標(biāo)記R的值為該值如果最大的phi值小于設(shè)定閾值delta，則標(biāo)記R的值為DataSet應(yīng)變量均值如果其中一個(gè)要產(chǎn)生的節(jié)點(diǎn)的樣本數(shù)量小于alpha，則不再分解，標(biāo)記R的值為DataSet應(yīng)變量均值CART-回歸樹算法步驟示意CART方法是由Breiman

等人在1984年提出的一種決策樹分類方法[2]。其采用基于最小距離的基尼指數(shù)估計(jì)函數(shù),這是因?yàn)榛嶂笖?shù)可以單獨(dú)考慮子數(shù)據(jù)集中類屬性的分布情況,用來(lái)決定由該子數(shù)據(jù)集生成的決策樹的拓展形狀。CART創(chuàng)建簡(jiǎn)單二叉樹結(jié)構(gòu)對(duì)新事例進(jìn)行分類,這樣可以有效地處理缺失數(shù)據(jù),尤其對(duì)于分類與預(yù)測(cè)時(shí)更好。并且CART方法中有貝葉斯分類的特征,使用者可以提供主觀的分類先驗(yàn)概率作為選擇分類的權(quán)重,則CART在獲得最終選擇樹前使用交叉檢驗(yàn)來(lái)評(píng)估候選樹的誤分類率,這對(duì)分析復(fù)雜樣本數(shù)據(jù)非常有用。CART處理離散變量與連續(xù)變量同樣容易,這是由于它使用了或形狀的幾乎不依靠無(wú)關(guān)變量的分支。而且,被CART考慮到的分支在任何單調(diào)轉(zhuǎn)換下是不變的,如對(duì)一個(gè)或更多的特征取對(duì)數(shù)、平方根等都是不變的。CART(ClassificationandRegressionTree,CART)二叉樹由根結(jié)點(diǎn),中間結(jié)點(diǎn)和葉(終)結(jié)點(diǎn)組成。每個(gè)CART有良好的優(yōu)越性,但是,并不是說(shuō)在任何情況下CART方法都好。對(duì)于許多數(shù)據(jù)集,CART方法產(chǎn)生的樹并不穩(wěn)定。訓(xùn)練樣本集的一點(diǎn)輕微改變都可能完全改變樹的結(jié)構(gòu),這些特點(diǎn)存在于具有顯著相關(guān)特征的數(shù)據(jù)集中。在CART中,問(wèn)題就轉(zhuǎn)換為在單個(gè)結(jié)點(diǎn)處存在幾個(gè)分支,而這幾個(gè)分支在減少子結(jié)點(diǎn)的所有復(fù)雜度方面幾乎是等價(jià)的。從而一個(gè)特定的分支選擇是比較隨意的,但是它將導(dǎo)致更多可能不同的樹。這種不穩(wěn)定性意味著使用者必須十分清楚由CART產(chǎn)生的樹中特定特征的充分解釋。另一方面,這一特點(diǎn)暗含著具有相似判別能力的不同樹的有用性,它允許通過(guò)樹的使用改變特征的選擇。CART的全稱是分類和回歸樹，既可以做分類算法，也可以做回歸。