隨機森林完整版本

大連大學(xué)DALIANUNIVERSITY決策樹與隨機森林決策樹簡介C4.5算法總結(jié)舉例1243內(nèi)容提要決策樹(DecisionTree）是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過構(gòu)成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率，評價項目風(fēng)險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。決策樹的構(gòu)成：1)內(nèi)部節(jié)點：對應(yīng)于一個屬性測試2)葉節(jié)點：對應(yīng)于決策結(jié)果3)根節(jié)點包含樣本全集；4)每個節(jié)點包括的樣本集合根據(jù)屬性測試的結(jié)果被劃分到子節(jié)點中；5)根節(jié)點到每個葉節(jié)點的路徑對應(yīng)對應(yīng)了一個判定測試路徑；決策樹決策樹示意圖決策樹生成算法建立決策樹的關(guān)鍵，即在當(dāng)前狀態(tài)下選擇哪個屬性作為分類依據(jù)。根據(jù)不同的目標(biāo)函數(shù)，建立決策樹。ID3C4.5CARTC4.5算法1.熵熵是信息論中的概念，假設(shè)數(shù)據(jù)集合D，熵的計算公式為:式中Pr(cj)表示cj類在數(shù)據(jù)集D中的概率，當(dāng)熵越小，數(shù)據(jù)越純凈。可以這么理解，熵是隨機變量不確定性的度量，不確定性越大，熵值越大；若隨機變量退化成定值，熵為0。若P為連續(xù)隨機變量，則概率分布變成概率密度函數(shù)，求和符號變成積分符號。注：1)熵其實定義了一個函數(shù)(概率分布函數(shù))到一個值(信息熵)的映射2)若X為離散隨機變量，則該名稱為概率分布函數(shù)；

若X為連續(xù)隨機變量，則該名稱為概率密度函數(shù)C4.5算法聯(lián)合熵和條件熵兩個隨機變量X，Y的聯(lián)合分布，可以形成聯(lián)合熵JointEntropy，用H(X,Y)表示H(X,Y)–H(Y)含義：(X,Y)發(fā)生所包含的信息熵，減去Y單獨發(fā)生包含的信息熵——在Y發(fā)生的前提下，X發(fā)生“新”帶來的信息熵。該式子定義為Y發(fā)生前提下，X的熵：條件熵H(X|Y)=H(X,Y)–H(Y)C4.5算法2.信息增益信息增益可以衡量混雜度或混亂度的減少量。假設(shè)Ai是D的屬性，可取v個值，則D可劃分成v個不相交的子集D1，D2，…，Dv，劃分后D的熵為:則屬性Ai的信息增益計算為:3.信息增益率信息增益偏向選擇取值較多的屬性，為了修正這種偏袒性，利用數(shù)據(jù)集的相對于屬性值分布的熵歸一化信息增益，使得熵都是相對于累屬性的，稱為信息增益率，計算為式中:s表示屬性Ai的可能取值數(shù)目，Dj表示D中具有Ai屬性第j個值的子集。4.C4.5算法描述C4.5是ID3的改進和優(yōu)化，它用信息增益率代替信息增益來選擇測試屬性，支持離散屬性和連續(xù)屬性，還對決策樹進行了必要的剪枝。流程如下：算法:Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)集產(chǎn)生一棵決策樹輸入:數(shù)據(jù)集D，候選屬性集A輸出:一棵決策樹TGenerate_decision_tree(D，A)創(chuàng)建節(jié)點T;ifD都在同一個類Cthen返回T作為葉節(jié)點，以類C標(biāo)記;elseifA為空or沒有剩余屬性進一步劃分樣本then

返回T為葉節(jié)點，標(biāo)記為D中最普通的類;//多數(shù)表決foreachD中的屬性

計算信息增益率gainRatio選擇A中具有最高信息增益率的屬性test_A為測試屬性;標(biāo)記節(jié)點T為test_A;if測試屬性為連續(xù)型then找到該屬性的分割閾值;foreachtest_A中的已知值A(chǔ)i//劃分D由節(jié)點T生出一個條件為test_A=Ai的分枝;設(shè)Dj是D中test_A=Ai的樣本集合; //一個劃分ifDj為空then加上一個樹葉，標(biāo)記為D中最普通的類;else

加上一個由Generate_decision_tree(Dj，D－test_A)返回的節(jié)點;進行剪枝;舉例C4.5算法舉例上面的訓(xùn)練集有4個屬性，即屬性集合A={OUTLOOK,TEMPERATURE,HUMIDITY,WINDY}；而類標(biāo)簽有2個，即類標(biāo)簽集合C={Yes,No}，分別表示適合戶外運動和不適合戶外運動，其實是一個二分類問題。

數(shù)據(jù)集D包含14個訓(xùn)練樣本，其中屬于類別“Yes”的有9個，屬于類別“No”的有5個，則計算其信息熵：Info(D)=-9/14*log2(9/14)-5/14*log2(5/14)=0.940下面對屬性集中每個屬性分別計算信息熵，如下所示：

C4.5算法舉例根據(jù)上面的數(shù)據(jù)，我們可以計算選擇第一個根結(jié)點所依賴的信息增益值，計算如下所示：接下來，我們計算分裂信息度量H(V)：OUTLOOK屬性屬性O(shè)UTLOOK有3個取值，其中Sunny有5個樣本、Rainy有5個樣本、Overcast有4個樣本，則C4.5算法舉例TEMPERATURE屬性屬性TEMPERATURE有3個取值，其中Hot有4個樣本、Mild有6個樣本、Cool有4個樣本，則HUMIDITY屬性屬性HUMIDITY有2個取值，其中Normal有7個樣本、High有7個樣本，則WINDY屬性屬性WINDY有2個取值，其中True有6個樣本、False有8個樣本，則C4.5算法舉例根據(jù)上面計算結(jié)果，我們可以計算信息增益率，如下所示：根據(jù)計算得到的信息增益率進行選擇屬性集中的屬性作為決策樹結(jié)點，對該結(jié)點進行分裂。C4.5算法的優(yōu)點是：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。

C4.5算法的缺點是：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。討論考察基尼指數(shù)的圖像、熵、分類誤差率三者之間的關(guān)系將f(x)=-lnx在x0=1處一階展開，忽略高階無窮小，得到f(x)≈1-x決策樹算法總結(jié)適應(yīng)信息增益來進行特征選擇的決策樹學(xué)習(xí)過程，即為ID3決策。所以如果是取值更多的屬性，更容易使得數(shù)據(jù)更“純”，其信息增益更大，決策樹會首先挑選這個屬性作為樹的頂點。結(jié)果訓(xùn)練出來的形狀是一棵龐大且深度很淺的樹，這樣的劃分是極為不合理的。C4.5：信息增益率gr(D,A)=g(D,A)/H(A)CART：基尼指數(shù)總結(jié)：一個屬性的信息增益越大，表明屬性對樣本的熵減少的能力更強，這個屬性使得數(shù)據(jù)由不確定性變成確定性的能力越強。BoostingDecisionTree：提升樹算法提升樹是迭代多棵回歸樹來共同決策。當(dāng)采用平方誤差損失函數(shù)時，每一棵回歸樹學(xué)習(xí)的是之前所有樹的結(jié)論和殘差，擬合得到一個當(dāng)前的殘差回歸樹，殘差的意義如公式：殘差=真實值-預(yù)測值。提升樹即是整個迭代過程生成的回歸樹的累加。訓(xùn)練一個提升樹模型來預(yù)測年齡：

??訓(xùn)練集是4個人，A，B，C，D年齡分別是14，16，24，26。樣本中有購物金額、上網(wǎng)時長、經(jīng)常到百度知道提問等特征。提升樹的過程如下：并行投票決策樹與傳統(tǒng)決策樹算法的主要不同之處在于:決策樹的生長方式和尋找最佳分割點的方法.并行投票決策樹應(yīng)用Leaf-wise方法,每次從當(dāng)前所有葉子中,找到分裂增益最大的一個葉子,然后分裂,如此循環(huán).與此同時增加了一個最大深度的限制,在保證高效率的同時防止過擬合.而傳統(tǒng)決策樹應(yīng)用Level-wise方法,所有葉子都是按層生長、分裂。在分裂次數(shù)相同的情況下,Leaf-wise可以降低更多的誤差,得到更好的精度。并行投票決策樹的核心是PV-Tree_FindBestSplit算法，該算法下次講解。投票決策樹表決感知器(VotedPerceptron，VP)算法是基于感知器算法的在線錯誤驅(qū)動二分類算法，訓(xùn)練算法和感知器算法的訓(xùn)練算法基本一樣，與感知器訓(xùn)練算法不同的是表決感知器存儲和使用了所有的預(yù)測向量，這些向量是在每次預(yù)測錯誤后產(chǎn)生的。對于這樣的向量，計算出在下次錯誤發(fā)生前的迭代數(shù)目，把迭代的數(shù)目作為預(yù)測向量的權(quán)值。通過計算每個向量的二類預(yù)測的權(quán)值，然后通過表決權(quán)值聯(lián)合所有的預(yù)測向量來得到最終的判別準(zhǔn)則。在樣本的預(yù)測上采用以下準(zhǔn)則：表決感知器能克服訓(xùn)練過程中出現(xiàn)的震蕩現(xiàn)象；盡管不能保證收斂性，但在訓(xùn)練時間上比SVM優(yōu)越，而且它可以有效的對高維數(shù)據(jù)實現(xiàn)分類。

表決感知器概述隨機性機制模型評估存在問題隨機森林目錄為什么提出隨機森林在回答上述問題前，必須要提到?jīng)Q策樹。決策樹(DecisionTree）是分類算法中最基本的算法，因其操作簡單，容易理解和有較好的分類效果，被廣泛應(yīng)用。隨著大數(shù)據(jù)的不斷發(fā)展，單一使用決策樹已經(jīng)遠遠解決不了問題。特別是處理連續(xù)的數(shù)據(jù)，容易導(dǎo)致過擬合等一系列問題。在這樣背景下，以決策樹為基分類器的多分類器隨機森林出現(xiàn)了。概念隨機森林由一系列單株分類器組成，其中是獨立同分布的隨機變量。當(dāng)輸入X后，進行如下步驟。Step1：每棵決策樹僅投一票給它認為最合適的分類標(biāo)簽；Step2：選擇投票最多的為X的分類標(biāo)簽。隨機森林生成規(guī)則隨機森林就是用CART決策樹作為Bagging算法中的弱學(xué)習(xí)器的實現(xiàn)，同時在每棵樹的特征選擇也用到了隨機且有放回抽樣，所以隨機森林的生成規(guī)則如下：1從原始訓(xùn)練集中隨機有放回采樣N個訓(xùn)練樣本，共進行T次采樣，生成T個訓(xùn)練集2用T個訓(xùn)練集，分別訓(xùn)練T個CART樹模型3如果特征維度為M，指定一個常數(shù)m4將生成的T棵決策樹組成隨機森林5對于分類問題，由T個CART樹投票表決產(chǎn)生分類結(jié)果。對于回歸問題，由T棵樹預(yù)測結(jié)果的均值作為最終的預(yù)測結(jié)果所以隨機森林歸的隨機歸納為一句話，即數(shù)據(jù)隨機采樣，特征隨機采樣。線性回歸與局部加權(quán)回歸黑色是樣本點紅色是線性回歸曲線綠色是局部加權(quán)回歸曲線使用Bagging記原始數(shù)據(jù)為D，長度為N(即圖中有N個離散點)算法過程做100次bootstrap，每次得到的數(shù)據(jù)Di，Di的長度為N對于每一個Di，使用局部回歸(LOESS)擬合一條曲線(圖中灰色線是其中的10條曲線)將這些曲線取平均，即得到紅色的最終擬合曲線顯然，紅色的曲線更加穩(wěn)定，并且沒有過擬合明顯減弱隨機性定量分析給一系列單株分類器，隨機選擇一些訓(xùn)練樣本，其中X是輸入向量，Y是正確分類的標(biāo)簽向量。定義如下邊際函數(shù)：其中I(.)是示性函數(shù)，av(.)表示取平均值。邊際函數(shù)表示了正確分類Y下，X得票數(shù)目超過其它錯誤分類最大得票數(shù)目的程度。該值越大，表明分類的置信度越高。隨機性分析泛函誤差公式定義：，其中X、Y表示概率空間。根據(jù)大數(shù)定律中的辛欽定理，當(dāng)決策樹的數(shù)量增加時，對所有的序列和PE都會收斂到：大數(shù)定理中的頻率收斂于概率。綜上所述，解釋了為什么隨機森林不會產(chǎn)生過度擬合，并且有一個泛化誤差值。簡單投票機制一票否決(一致表決)少數(shù)服從多數(shù)有效多數(shù)(加權(quán))閾值表決貝葉斯投票機制投票機制貝葉斯投票機制簡單投票法假設(shè)每個分類器都是平等的。在實際生活中，我們聽取一個人的意見，會考慮這個人過去的意見是否有用，從而加大或者減少權(quán)值。貝葉斯投票機制基于每個基本分類器在過去的分類表現(xiàn)設(shè)定一個權(quán)值，然后按照這個權(quán)值進行投票。投票機制舉例假定有N個用戶可以為X個電影投票(假定投票者不能給同一電影重復(fù)投票)，投票有1、2、3、4、5星共5檔。如何根據(jù)用戶投票，對電影排序？本質(zhì)仍然是分類問題：對于某個電影，有N個決策樹，每個決策樹對該電影有1個分類(1、2、3、4、5類)，求這個電影應(yīng)該屬于哪一類(可以是小數(shù)：分類問題變成了回歸問題)一種可能的方案WR：加權(quán)得分(weightedrating)R：該電影的用戶投票的平均得分(Rating)C：所有電影的平均得分v：該電影的投票人數(shù)(votes)m：排名前250名的電影的最低投票數(shù)根據(jù)總投票人數(shù)，250可能有所調(diào)整按照v=0和m=0分別分析模型評估可以在這里寫結(jié)論要得到一個相對正確的結(jié)論，首先要進行大量的調(diào)查。以二分類問題為例：其中：P(PositiveSample):正例數(shù)量N(NegativeSample):負例數(shù)量TP(TruePositive):正確預(yù)測正例數(shù)量FP(FalsePositive):把負例預(yù)測成正例數(shù)量FN(FalseNegative):把正例預(yù)測成負例數(shù)量TN(TrueNegative):正確預(yù)測負例數(shù)量分類準(zhǔn)確度，就是正負樣本正確分類，計算公式：召回率，就是正樣本被識別出的概率，計算公式：虛警率，負樣本誤分為正樣本概率，計算公式：精確率，分類結(jié)果為正樣本真實性程度，計算公式：模型評估使用TPR和FPR分析二分類模型對于一個二分類模型，假設(shè)已確定一個閥值，比如說0.6，大于這個值的實例劃歸為正類，小于這個值則劃到負類中。如果減小閥值，比如減到0.5，一方面，能識別出更多的正類，即提高TPR(樣本集合的正例總數(shù)沒變)；另一方面，也將更多的負實例當(dāng)作了正實例，即提高了FPR。根據(jù)不同的閾值，將離散點(TPR,FPR)繪制成曲線，就得到ROC曲線，可以用于評價一個分類器。ReceiverOperatingCharacteristic，接受者操作特性曲線ROC曲線以假正類率FPR為橫軸，真正類率TPR為縱軸，得到ROC曲