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

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

返回T為葉節點，標記為D中最普通的類;//多數表決foreachD中的屬性

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

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

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

C4.5算法舉例根據上面的數據，我們可以計算選擇第一個根結點所依賴的信息增益值，計算如下所示：接下來，我們計算分裂信息度量H(V)：OUTLOOK屬性屬性OUTLOOK有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算法舉例根據上面計算結果，我們可以計算信息增益率，如下所示：根據計算得到的信息增益率進行選擇屬性集中的屬性作為決策樹結點，對該結點進行分裂。C4.5算法的優點是：產生的分類規則易于理解，準確率較高。

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

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

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