隨機森林

1、決策樹與隨機森林,李寧,2,目標任務與主要內容,信息熵熵、聯(lián)合熵、條件熵、互信息決策樹學習算法信息增益ID3、C4.5、CARTBagging與隨機森林的思想,3,熵,將離散隨機變量X的概率分布為P(X=xi)，則定義熵為：若P為連續(xù)隨機變量，則概率分布變成概率密度函數(shù)，求和符號變成積分符號。在不引起混淆的情況下，下面談到的“概率分布函數(shù)”，其含義是：1、若X為離散隨機變量，則該名稱為概率分布函數(shù)；2、若X為連續(xù)隨

2、機變量，則該名稱為概率密度函數(shù)。,4,對熵的理解,熵是隨機變量不確定性的度量，不確定性越大，熵值越大；若隨機變量退化成定值，熵為0均勻分布是“最不確定”的分布熵其實定義了一個函數(shù)(概率分布函數(shù))到一個值(信息熵)的映射。P(x)?H (函數(shù)?數(shù)值),5,聯(lián)合熵和條件熵,兩個隨機變量X，Y的聯(lián)合分布，可以形成聯(lián)合熵Joint Entropy，用H(X,Y)表示H(X,Y) – H(Y)(X,Y)發(fā)生所包含的信息熵，減去Y單獨

3、發(fā)生包含的信息熵——在Y發(fā)生的前提下，X發(fā)生“新”帶來的信息熵該式子定義為Y發(fā)生前提下，X的熵：條件熵H(X|Y) = H(X,Y) – H(Y),6,推導條件熵的定義式,7,相對熵,相對熵，又稱互熵，交叉熵，鑒別信息，Kullback熵，Kullback-Leible散度等設p(x)、q(x)是X中取值的兩個概率分布，則p對q的相對熵是說明：相對熵可以度量兩個隨機變量的“距離”在“貝葉斯網(wǎng)絡”、“變分推導”章節(jié)使用過

4、一般的，D(p||q) ≠D(q||p),8,互信息,兩個隨機變量X，Y的互信息，定義為X，Y的聯(lián)合分布和獨立分布乘積的相對熵。I(X,Y)=D(P(X,Y) || P(X)P(Y)),9,計算H(X)-I(X,Y),10,整理得到的等式,H(X|Y) = H(X,Y) - H(Y)條件熵定義H(X|Y) = H(X) - I(X,Y)根據(jù)互信息定義展開得到有些文獻將I(X,Y)=H(Y) – H(Y|X)作為互信息的定義式

5、對偶式H(Y|X)= H(X,Y) - H(X)H(Y|X)= H(Y) - I(X,Y)I(X,Y)= H(X) + H(Y) - H(X,Y)有些文獻將該式作為互信息的定義式,決策樹示意圖,11,12,決策樹 (Decision Tree),決策樹是一種樹型結構，其中每個內部結點表示在一個屬性上的測試，每個分支代表一個測試輸出，每個葉結點代表一種類別。決策樹學習是以實例為基礎的歸納學習。決策樹學習采用的是自頂向下的遞歸方

6、法，其基本思想是以信息熵為度量構造一棵熵值下降最快的樹，到葉子節(jié)點處的熵值為零，此時每個葉節(jié)點中的實例都屬于同一類。,13,決策樹學習算法的特點,決策樹學習算法的最大優(yōu)點是，它可以自學習。在學習的過程中，不需要使用者了解過多背景知識，只需要對訓練實例進行較好的標注，就能夠進行學習。顯然，屬于有監(jiān)督學習。從一類無序、無規(guī)則的事物(概念)中推理出決策樹表示的分類規(guī)則。,14,決策樹學習的生成算法,建立決策樹的關鍵，即在當前狀態(tài)下選擇哪個

7、屬性作為分類依據(jù)。根據(jù)不同的目標函數(shù)，建立決策樹主要有一下三種算法。ID3C4.5CART,15,信息增益,概念：當熵和條件熵中的概率由數(shù)據(jù)估計(特別是極大似然估計)得到時，所對應的熵和條件熵分別稱為經(jīng)驗熵和經(jīng)驗條件熵。信息增益表示得知特征A的信息而使得類X的信息的不確定性減少的程度。定義：特征A對訓練數(shù)據(jù)集D的信息增益g(D,A)，定義為集合D的經(jīng)驗熵H(D)與特征A給定條件下D的經(jīng)驗條件熵H(D|A)之差，即：g(D,A

8、)=H(D) – H(D|A)顯然，這即為訓練數(shù)據(jù)集D和特征A的互信息。,16,基本記號,設訓練數(shù)據(jù)集為D，|D|表示其容量，即樣本個數(shù)。設有K個類Ck，k=1,2,…,K，|Ck|為屬于類Ck的樣本個數(shù)。Σk|Ck|=|D|。設特征A有n個不同的取值{a1,a2…an}，根據(jù)特征A的取值將D劃分為n個子集D1,D2,…Dn,|Di|為Di的樣本個數(shù)，Σi|Di|=D。記子集Di中屬于類Ck的樣本的集合為Dik，|Dik|為Dik的樣

9、本個數(shù)。,17,信息增益的計算方法,計算數(shù)據(jù)集D的經(jīng)驗熵計算特征A對數(shù)據(jù)集D的經(jīng)驗條件熵H(D|A)計算信息增益：g(D,A)=H(D) – H(D|A),18,經(jīng)驗條件熵H(D|A),19,其他目標,信息增益率：gr(D,A) = g(D,A) / H(A)基尼指數(shù)：,20,三種決策樹學習算法,適應信息增益來進行特征選擇的決策樹學習過程，即為ID3決策。所以如果是取值更多的屬性，更容易使得數(shù)據(jù)更“純” ，其信息增益更大，決

10、策樹會首先挑選這個屬性作為樹的頂點。結果訓練出來的形狀是一棵龐大且深度很淺的樹，這樣的劃分是極為不合理的。 C4.5：信息增益率 gr(D,A) = g(D,A) / H(A)CART：基尼指數(shù)總結：一個屬性的信息增益越大，表明屬性對樣本的熵減少的能力更強，這個屬性使得數(shù)據(jù)由不確定性變成確定性的能力越強。,21,決策樹的過擬合,決策樹對訓練屬于有很好的分類能力，但對未知的測試數(shù)據(jù)未必有好的分類能力，泛化能力弱，即可能發(fā)生過擬合現(xiàn)

11、象。剪枝隨機森林,22,剪枝,預剪枝在構造決策樹的同時進行剪枝。(為了避免過擬合，可以設定一個閾值)后剪枝決策樹構造完成后進行剪枝Reduced-Error Pruning (REP,錯誤率降低剪枝）Pessimistic Error Pruning (PEP，悲觀剪枝）,23,Bagging的策略,bootstrap aggregation 從樣本集中重采樣(有重復的)選出n個樣本在所有屬性上，對這n個樣本建立分類器

12、(ID3、C4.5、CART、SVM、Logistic回歸等)重復以上兩步m次，即獲得了m個分類器將數(shù)據(jù)放在這m個分類器上，最后根據(jù)這m個分類器的投票結果，決定數(shù)據(jù)屬于哪一類,24,Bagging,25,隨機森林,隨機森林在bagging基礎上做了修改。從樣本集中用Bootstrap采樣選出n個樣本；從所有屬性中隨機選擇k個屬性，選擇最佳分割屬性作為節(jié)點建立CART決策樹；重復以上兩步m次，即建立了m棵CART決策樹這m個C