決策樹與隨機森林

1、1目標任務(wù)與主要內(nèi)容o復(fù)習(xí)信息熵n熵、聯(lián)合熵、條件熵、互信息o決策樹學(xué)習(xí)算法n信息增益nID3、C4.5、CARToBagging與隨機森林的思想n投票機制o分類算法的評價指標nROC曲線和AUC值2決策樹與隨機森林 鄒博 北京10月機器學(xué)習(xí)班 & ML在線公開課第1期 2015年1月11日3決策樹的實例(Weka自帶測試數(shù)據(jù))注：Weka的全名是懷卡托智能分析環(huán)境(Waikato Environment for Knowledge Analysis)，是一款免費的，非商業(yè)化(與之對應(yīng)的是SPSS公司商業(yè)數(shù)據(jù)挖掘產(chǎn)品-Clementine )的，基于JAVA環(huán)境下開源的機器學(xué)習(xí)(mac

2、hine learning)以及數(shù)據(jù)挖掘(data minining)軟件。它和它的源代碼可在其官方網(wǎng)站下載。4復(fù)習(xí)：熵o將離散隨機變量X的概率分布為P(X=xi)，則定義熵為：o若P為連續(xù)隨機變量，則概率分布變成概率密度函數(shù)，求和符號變成積分符號。o在不引起混淆的情況下，下面談到的“概率分布函數(shù)”，其含義是：n1、若X為離散隨機變量，則該名稱為概率分布函數(shù)；n2、若X為連續(xù)隨機變量，則該名稱為概率密度函數(shù)。 XxxpxpXH1log5對熵的理解o熵是隨機變量不確定性的度量，不確定性越大，熵值越大；若隨機變量退化成定值，熵為0n均勻分布是“最不確定”的分布o熵其實定義了一個函數(shù)(概率分布函數(shù))

3、到一個值(信息熵)的映射。nP(x)H (函數(shù)數(shù)值)n泛函o回憶一下關(guān)于“變分推導(dǎo)”章節(jié)中對于泛函的內(nèi)容。6聯(lián)合熵和條件熵o兩個隨機變量X，Y的聯(lián)合分布，可以形成聯(lián)合熵Joint Entropy，用H(X,Y)表示oH(X,Y) H(Y)n(X,Y)發(fā)生所包含的信息熵，減去Y單獨發(fā)生包含的信息熵在Y發(fā)生的前提下，X發(fā)生“新”帶來的信息熵n該式子定義為Y發(fā)生前提下，X的熵：o條件熵H(X|Y) = H(X,Y) H(Y)7推導(dǎo)條件熵的定義式 yxyxyxyxyxyxyyxyxpyxpypyxpyxpypyxpyxpyxpypyxpyxpyxpypypyxpyxpYHYXH,)|(log),()(

4、),(log),()(log),(),(log),()(log),(),(log),()(log)(),(log),()(),(8相對熵o相對熵，又稱互熵，交叉熵，鑒別信息，Kullback熵，Kullback-Leible散度等o設(shè)p(x)、q(x)是X中取值的兩個概率分布，則p對q的相對熵是o說明：n相對熵可以度量兩個隨機變量的“距離”o在“貝葉斯網(wǎng)絡(luò)”、“變分推導(dǎo)”章節(jié)使用過n一般的，D(p|q) D(q|p)nD(p|q)0、 D(q|p) 0 提示：凸函數(shù)中的Jensen不等式9互信息o兩個隨機變量X，Y的互信息，定義為X，Y的聯(lián)合分布和獨立分布乘積的相對熵。oI(X,Y)=D(P(

5、X,Y) | P(X)P(Y)yxypxpyxpyxpYXI,)()(),(log),(),(10計算H(X)-I(X,Y)|()|(log),()(),(log),()()(),(log),()(log),()()(),(log),()(log),()()(),(log),()(log)(),()(,YXHyxpyxpypyxpyxpypxpyxpyxpxpyxpypxpyxpyxpxpyxpypxpyxpyxpxpxpYXIXHyxyxyxyxyxxyyxx 11整理得到的等式oH(X|Y) = H(X,Y) - H(Y)n條件熵定義oH(X|Y) = H(X) - I(X,Y)n根據(jù)互信

6、息定義展開得到n有些文獻將I(X,Y)=H(Y) H(Y|X)作為互信息的定義式o對偶式nH(Y|X)= H(X,Y) - H(X)nH(Y|X)= H(Y) - I(X,Y)oI(X,Y)= H(X) + H(Y) - H(X,Y)n有些文獻將該式作為互信息的定義式o試證明：H(X|Y) H(X) ，H(Y|X) H(Y)12強大的Venn圖：幫助記憶13決策樹示意圖14決策樹 (Decision Tree) o決策樹是一種樹型結(jié)構(gòu)，其中每個內(nèi)部結(jié)點表示在一個屬性上的測試，每個分支代表一個測試輸出，每個葉結(jié)點代表一種類別。o決策樹學(xué)習(xí)是以實例為基礎(chǔ)的歸納學(xué)習(xí)。o決策樹學(xué)習(xí)采用的是自頂向下的遞

7、歸方法，其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子節(jié)點處的熵值為零，此時每個葉節(jié)點中的實例都屬于同一類。15決策樹學(xué)習(xí)算法的特點o決策樹學(xué)習(xí)算法的最大優(yōu)點是，它可以自學(xué)習(xí)。在學(xué)習(xí)的過程中，不需要使用者了解過多背景知識，只需要對訓(xùn)練實例進行較好的標注，就能夠進行學(xué)習(xí)。n顯然，屬于有監(jiān)督學(xué)習(xí)。n從一類無序、無規(guī)則的事物(概念)中推理出決策樹表示的分類規(guī)則。16決策樹學(xué)習(xí)的生成算法o建立決策樹的關(guān)鍵，即在當前狀態(tài)下選擇哪個屬性作為分類依據(jù)。根據(jù)不同的目標函數(shù)，建立決策樹主要有一下三種算法。nID3nC4.5nCART17信息增益o概念：當熵和條件熵中的概率由數(shù)據(jù)估計(特別是極大似然估

8、計)得到時，所對應(yīng)的熵和條件熵分別稱為經(jīng)驗熵和經(jīng)驗條件熵。o信息增益表示得知特征A的信息而使得類X的信息的不確定性減少的程度。o定義：特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)，定義為集合D的經(jīng)驗熵H(D)與特征A給定條件下D的經(jīng)驗條件熵H(D|A)之差，即：ng(D,A)=H(D) H(D|A)n顯然，這即為訓(xùn)練數(shù)據(jù)集D和特征A的互信息。18基本記號o設(shè)訓(xùn)練數(shù)據(jù)集為D，|D|表示其容量，即樣本個數(shù)。設(shè)有K個類Ck，k=1,2,K，|Ck|為屬于類Ck的樣本個數(shù)。k|Ck|=|D|。設(shè)特征A有n個不同的取值a1,a2an，根據(jù)特征A的取值將D劃分為n個子集D1,D2,Dn,|Di|為Di的樣本

9、個數(shù)，i|Di|=D。記子集Di中屬于類Ck的樣本的集合為Dik，|Dik|為Dik的樣本個數(shù)。19信息增益的計算方法o計算數(shù)據(jù)集D的經(jīng)驗熵o計算特征A對數(shù)據(jù)集D的經(jīng)驗條件熵H(D|A)o計算信息增益：g(D,A)=H(D) H(D|A) KkkkDCDCDH1log20經(jīng)驗條件熵H(D|A) niiikiikKkiniikikKkiniikikiKkkiikikikiikikDDDDDDADpADpApADpADpApADpADpApADpADpADH111111,log|log|log|log|log,|21其他目標o信息增益率：gr(D,A) = g(D,A) / H(A)o基尼指數(shù)：

10、21121111KkkKkkKkkkDCppppGini22討論(一家之言)o考察基尼指數(shù)的圖像、熵、分類誤差率三者之間的關(guān)系n將f(x)=-lnx在x0=1處一階展開，忽略高階無窮小，得到f(x)1-x KkkkKkkkppppXH111ln23三種決策樹學(xué)習(xí)算法o適應(yīng)信息增益來進行特征選擇的決策樹學(xué)習(xí)過程，即為ID3決策。o所以如果是取值更多的屬性，更容易使得數(shù)據(jù)更“純” ，其信息增益更大，決策樹會首先挑選這個屬性作為樹的頂點。結(jié)果訓(xùn)練出來的形狀是一棵龐大且深度很淺的樹，這樣的劃分是極為不合理的。 oC4.5：信息增益率 gr(D,A) = g(D,A) / H(A)oCART：基尼指數(shù)o

11、總結(jié)：一個屬性的信息增益越大，表明屬性對樣本的熵減少的能力更強，這個屬性使得數(shù)據(jù)由不確定性變成確定性的能力越強。24決策樹的例子o對于下面的數(shù)據(jù)，希望分割成紅色和綠色兩個類25決策樹的生成過程26決策樹的生成過程27決策樹的生成過程28決策樹的生成過程29決策樹的生成過程30決策樹的生成過程31決策樹的生成過程32決策樹的生成過程33決策樹的生成過程34決策樹的過擬合o決策樹對訓(xùn)練屬于有很好的分類能力，但對未知的測試數(shù)據(jù)未必有好的分類能力，泛化能力弱，即可能發(fā)生過擬合現(xiàn)象。n剪枝n隨機森林35BootstrapingoBootstraping的名稱來自成語“pull up by your ow

12、n bootstraps”，意思是依靠你自己的資源，稱為自助法，它是一種有放回的抽樣方法。n注：Bootstrap本義是指高靴子口后面的懸掛物、小環(huán)、帶子，是穿靴子時用手向上拉的工具?！皃ull up by your own bootstraps”即“通過拉靴子讓自己上升”，意思是“不可能發(fā)生的事情”。后來意思發(fā)生了轉(zhuǎn)變，隱喻“不需要外界幫助，僅依靠自身力量讓自己變得更好”。36Bagging的策略obootstrap aggregationo 從樣本集中重采樣(有重復(fù)的)選出n個樣本o在所有屬性上，對這n個樣本建立分類器(ID3、C4.5、CART、SVM、Logistic回歸等)o重復(fù)以上

13、兩步m次，即獲得了m個分類器o將數(shù)據(jù)放在這m個分類器上，最后根據(jù)這m個分類器的投票結(jié)果，決定數(shù)據(jù)屬于哪一類37Another description of Bagging38Bagging39Bagging的結(jié)果40隨機森林o隨機森林在bagging基礎(chǔ)上做了修改。n從樣本集中用Bootstrap采樣選出n個樣本；n從所有屬性中隨機選擇k個屬性，選擇最佳分割屬性作為節(jié)點建立CART決策樹；n重復(fù)以上兩步m次，即建立了m棵CART決策樹n這m個CART形成隨機森林，通過投票表決結(jié)果，決定數(shù)據(jù)屬于哪一類41應(yīng)用實例：KinectReal-Time Human Pose Recognition in

14、 Parts from Single Depth Images, Jamie Shotton etc,2001,42隨機森林/Bagging和決策樹的關(guān)系o當然可以使用決策樹作為基本分類器o但也可以使用SVM、Logistic回歸等其他分類器，習(xí)慣上，這些分類器組成的“總分類器”，仍然叫做隨機森林。o舉例43回歸問題o離散點是樣本集合，描述了臭氧(橫軸)和溫度(縱軸)的關(guān)系o試擬合二者的變化曲線44使用Baggingo算法過程n做100次bootstrap，每次得到的數(shù)據(jù)Di，Di的長度為Nn對于每一個Di，使用局部回歸(LOESS)擬合一條曲線(圖中灰色線是其中的10條曲線)n將這些曲線取平

15、均，即得到紅色的最終擬合曲線n顯然，紅色的曲線更加穩(wěn)定，并且沒有過擬合明顯減弱記原始數(shù)據(jù)為D，長度為N(即圖中有N個離散點)45附：局部加權(quán)線性回歸oLWR：Locally Weighted linear RegressionoLOESS : LOcal regrESSion46附：線性回歸與局部加權(quán)回歸o黑色是樣本點o紅色是線性回歸曲線o綠色是局部加權(quán)回歸曲線47投票機制o簡單投票機制n一票否決(一致表決)n少數(shù)服從多數(shù)o有效多數(shù)(加權(quán))n閾值表決o貝葉斯投票機制48貝葉斯投票機制o簡單投票法假設(shè)每個分類器都是平等的。o在實際生活中，我們聽取一個人的意見，會考慮這個人過去的意見是否有用，從而

16、加大或者減少權(quán)值。o貝葉斯投票機制基于每個基本分類器在過去的分類表現(xiàn)設(shè)定一個權(quán)值，然后按照這個權(quán)值進行投票。49投票機制舉例o假定有N個用戶可以為X個電影投票(假定投票者不能給同一電影重復(fù)投票)，投票有1、2、3、4、5星共5檔。o如何根據(jù)用戶投票，對電影排序？n本質(zhì)仍然是分類問題：對于某個電影，有N個決策樹，每個決策樹對該電影有1個分類(1、2、3、4、5類)，求這個電影應(yīng)該屬于哪一類(可以是小數(shù)：分類問題變成了回歸問題)50一種可能的方案oWR：加權(quán)得分(weighted rating)oR：該電影的用戶投票的平均得分(Rating)oC：所有電影的平均得分ov：該電影的投票人數(shù)(vote

17、s)om：排名前250名的電影的最低投票數(shù)n根據(jù)總投票人數(shù)，250可能有所調(diào)整n按照v=0和m=0分別分析51評價指標o以下近考慮二分類問題，即將實例分成正類(positive)或負類(negative)。o對一個二分問題來說，會出現(xiàn)四種情況。如果一個實例是正類并且也被 預(yù)測成正類，即為真正類(True positive),如果實例是負類被預(yù)測成正類，稱之為假正類(False positive)。相應(yīng)地，如果實例是負類被預(yù)測成負類，稱之為真負類(True negative),正類被預(yù)測成負類則為假負類(false negative)。52混淆矩陣(Confusion Matrix)oTP：正確

18、肯定實例是正例，劃分為正例oFN：漏報實際是正例，卻劃分成了負例oFP：誤報實際是負例，卻劃分成了正例oTN：正確拒絕實例是負例，劃分為負例53o誤分率Error Rate：(FN+FP) / Co準確度Accuracy ：(TP+TN) / Co查準率Precision：TP / (TP + FP)o真正類率(true positive rate ,TPR)：TP/(TP+FN)n查全率Recall、擊中概率，收益(benefits)o假正類率(False Positive Rate, FPR)：FP/ (FP + TN)n虛報概率，代價(costs)o思考：可否按此模式，定義“真負類率TN

19、R”？54使用TPR和FPR分析二分類模型o對于一個二分類模型，假設(shè)已確定一個閥值，比如說 0.6，大于這個值的實例劃歸為正類，小于這個值則劃到負類中。如果減小閥值，比如減到0.5，一方面，能識別出更多的正類，即提高TPR(樣本集合的正例總數(shù)沒變)；另一方面，也將更多的負實例當作了正實例，即提高了FPR。o根據(jù)不同的閾值，將離散點(TPR,FPR)繪制成曲線，就得到ROC曲線，可以用于評價一個分類器。nReceiver Operating Characteristic，接受者操作特性曲線55ROC曲線o以假正類率FPR為橫軸，真正類率TPR為縱軸，得到ROC曲線n虛報概率 (代價)為橫軸，擊中概率 (收益)為縱軸56ROC曲線的分析o對于一個分類器，n每個閾值對應(yīng)一個(TPR，F(xiàn)PR)；