隨機(jī)森林

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

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

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

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

5、對(duì)偶式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)有些文獻(xiàn)將該式作為互信息的定義式,決策樹(shù)示意圖,11,12,決策樹(shù) (Decision Tree),決策樹(shù)是一種樹(shù)型結(jié)構(gòu)，其中每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉結(jié)點(diǎn)代表一種類別。決策樹(shù)學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)。決策樹(shù)學(xué)習(xí)采用的是自頂向下的遞歸方

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

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

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

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

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

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

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