決策樹(完整)ppt課件

1、機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)第4章 決策樹第5章 神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)第6章 支持向量機(jī)第8章 集成學(xué)習(xí)第9關(guān)聯(lián)規(guī)則學(xué)習(xí)1;.第第4章章 決策樹決策樹根據(jù)訓(xùn)練數(shù)據(jù)是否擁有標(biāo)記信息學(xué)習(xí)任務(wù)決策樹決策樹（decision tree）模型常常用來解決分類和回歸問題。常見的算法包括 CART (Classification And Regression Tree)、ID3、C4.5等。半監(jiān)督學(xué)習(xí)：輸入數(shù)據(jù)部分被標(biāo)識，部分沒有被標(biāo)識，介于監(jiān)督學(xué)習(xí)與非監(jiān)督學(xué)習(xí)之間。分類、回歸聚類( ,)iix y監(jiān)督學(xué)習(xí)(supervised learning)無監(jiān)督學(xué)習(xí)(unsupervised learning)半監(jiān)督學(xué)習(xí)(sem

2、i-supervised learning)強(qiáng)化學(xué)習(xí)(reinforcement learning)2;.二分類學(xué)習(xí)任務(wù)屬性屬性值根結(jié)點(diǎn)：包含全部樣本葉結(jié)點(diǎn)：對應(yīng)決策結(jié)果 “好瓜” “壞瓜”內(nèi)部結(jié)點(diǎn)：對應(yīng)屬性測試決策樹學(xué)習(xí)的目的：為了產(chǎn)生一顆泛化能力強(qiáng)的決策樹，即處理未見示例能力強(qiáng)。3;.無需劃分無法劃分不能劃分無需劃分無法劃分不能劃分Hunt算法：4;.1,2,3,4,5,6,8,10,151,2,3,4,56,8,151068,15815第（2）種情形：設(shè)定為該結(jié)點(diǎn)所含樣本最多的類別利用當(dāng)前結(jié)點(diǎn)的后驗(yàn)分布第（3）種情形：設(shè)定為其父結(jié)點(diǎn)所含樣本最多的類別把父結(jié)點(diǎn)的樣本分布作為當(dāng)前結(jié)點(diǎn)的先驗(yàn)分

3、布5;.決策樹學(xué)習(xí)的關(guān)鍵是算法的第8行：選擇最優(yōu)劃分屬性什么樣的劃分屬性是最優(yōu)的？我們希望決策樹的分支結(jié)點(diǎn)所包含的樣本盡可能屬于同一類別，即結(jié)點(diǎn)的“純度”越來越高，可以高效地從根結(jié)點(diǎn)到達(dá)葉結(jié)點(diǎn)，得到?jīng)Q策結(jié)果。三種度量結(jié)點(diǎn)“純度”的指標(biāo)：1.信息增益2.增益率3.基尼指數(shù)6;.1. 信息增益信息增益香農(nóng)提出了“信息熵”的概念，解決了對信息的量化度量問題。香農(nóng)用“信息熵”的概念來描述信源的不確定性。信息熵信息熵對于二分類任務(wù)2y 7;.一個事件的信息量信息量就是這個事件發(fā)生的概率的負(fù)對數(shù)。信息熵信息熵是跟所有事件的可能性有關(guān)的，是平均而言發(fā)生一個事件得到的信息量大小。所以信息熵其實(shí)是信息量的期望。

4、假設(shè)我們已經(jīng)知道衡量不確定性大小的這個量已經(jīng)存在了，不妨就叫做“信息量信息量”不會是負(fù)數(shù)不確定性函數(shù) 是概率的單調(diào)遞減函數(shù)；可加性：兩個獨(dú)立符號所產(chǎn)生的不確定性應(yīng)等于各自不確定性之和，即同時滿足這三個條件的函數(shù)是負(fù)的對數(shù)函數(shù)，即fp1212()()()f ppf pf pf1()loglogiiif ppp 1 loglogniiiiEppp 8;.信息增益信息增益一般而言，信息增益越大，則意味著使用屬性a來進(jìn)行劃分所獲得的“純度提升”越大。決策樹算法第8行選擇屬性著名的ID3決策樹算法9;.舉例：求解劃分根結(jié)點(diǎn)的最優(yōu)劃分屬性根結(jié)點(diǎn)的信息熵：以屬性“色澤”為例計算其信息增益1817p 2917

5、p 數(shù)據(jù)集包含17個訓(xùn)練樣例：8個正例（好瓜）占9個反例（壞瓜）占對于二分類任務(wù)2y 10;.用“色澤”將根結(jié)點(diǎn)劃分后獲得3個分支結(jié)點(diǎn)的信息熵分別為：屬性“色澤”的信息增益為：11;.12;.13;.若把“編號”也作為一個候選劃分屬性，則屬性“編號”的信息增益為：根結(jié)點(diǎn)的信息熵仍為：()0.998Ent D 用“編號”將根結(jié)點(diǎn)劃分后獲得17個分支結(jié)點(diǎn)的信息熵均為：117221100()()( loglog)01111Ent DEnt D 則“編號”的信息增益為：1711( ,)()()0.99817vvGain DEnt DEnt D編號遠(yuǎn)大于其他候選屬性信息增益準(zhǔn)則對可取值數(shù)目較多的屬性有所

6、偏好14;.2. 增益率增益率增益率準(zhǔn)則對可取值數(shù)目較少的屬性有所偏好著名的C4.5決策樹算法綜合了信息增益準(zhǔn)則信息增益準(zhǔn)則和信息率準(zhǔn)則信息率準(zhǔn)則的特點(diǎn)：先從候選劃分屬性中找出信息增益高于平均水平的屬性，再從中選擇增益率最高的。15;.3. 基尼指數(shù)基尼指數(shù)基尼值基尼值基尼指數(shù)基尼指數(shù)著名的CART決策樹算法16;.過擬合過擬合：學(xué)習(xí)器學(xué)習(xí)能力過于強(qiáng)大，把訓(xùn)練樣本自身的一些特點(diǎn)當(dāng)作了所有潛在樣本都會具有的一般性質(zhì)，導(dǎo)致泛化性能下降。欠擬合欠擬合：學(xué)習(xí)器學(xué)習(xí)能力低下，對訓(xùn)練樣本的一般性質(zhì)尚未學(xué)好。過擬合無法徹底避免，只能做到“緩解”。17;.剪枝，即通過主動去掉一些分支來降低過擬合的風(fēng)險。預(yù)剪枝

7、預(yù)剪枝決策樹的剪枝策略后剪枝后剪枝預(yù)剪枝預(yù)剪枝：在決策樹生成過程中，對每個結(jié)點(diǎn)在劃分前先進(jìn)行估計，若當(dāng)前結(jié)點(diǎn)的劃分不能帶來決策樹泛化性能提升，則停止劃分并將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)后剪枝后剪枝：先從訓(xùn)練集生成一棵完整的決策樹，然后自底向上地對非葉結(jié)點(diǎn)進(jìn)行考察，若將該結(jié)點(diǎn)對應(yīng)的子樹替換為葉結(jié)點(diǎn)能帶來決策樹泛化性能提升，則將該子樹替換為葉結(jié)點(diǎn)。留出法：將數(shù)據(jù)集D劃分為兩個互斥的集合：訓(xùn)練集S和測試集TDSTST 且18;.19;.預(yù)剪枝預(yù)剪枝1,2,3,14訓(xùn)練集訓(xùn)練集：好瓜好瓜 壞瓜壞瓜1,2,3,6,7,10,14,15,16,176,7,15,1710,16精度：正確分類的樣本占所有樣本的比例4

8、,5,13(T,T,F)8,9(T,F)11,12(T,T)驗(yàn)證集驗(yàn)證集：4,5,8,9,11,12,133=75=720;.不足不足：基于“貪心”本質(zhì)禁止某些分支展開，帶來了欠擬合的風(fēng)險預(yù)剪枝使得決策樹的很多分支都沒有“展開”優(yōu)點(diǎn)優(yōu)點(diǎn)：降低過擬合的風(fēng)險減少了訓(xùn)練時間開銷和測試時間開銷21;.后剪枝后剪枝先從訓(xùn)練集生成一棵完整的決策樹，然后自底向上地對非葉結(jié)點(diǎn)進(jìn)行考察，若將該結(jié)點(diǎn)對應(yīng)的子樹替換為葉結(jié)點(diǎn)能帶來決策樹泛化性能提升，則將該子樹替換為葉結(jié)點(diǎn)。驗(yàn)證集驗(yàn)證集：4,5,8,9,11,124,13(T,F)5(F)9(F)8(F)11,12(T,T)驗(yàn)證集精度：37考察結(jié)點(diǎn)順序：6,7,15,

9、176,7,151767,157158,9(T,F)減去結(jié)點(diǎn)驗(yàn)證集變?yōu)椋?7訓(xùn)練集訓(xùn)練集：好瓜好瓜 壞瓜壞瓜1,2,3,6,7,10,14,15,16,1722;.后剪枝后剪枝決策樹預(yù)剪枝預(yù)剪枝決策樹保留了更多的分支欠擬合風(fēng)險很小泛化能力優(yōu)于預(yù)剪枝決策樹訓(xùn)練時間開銷比未減枝和預(yù)剪枝決策樹大得多1. 生產(chǎn)完全決策樹2. 所有非葉節(jié)點(diǎn)逐一考察23;.知識回顧：知識回顧：1.四類學(xué)習(xí)任務(wù)2.Hunt算法3種遞歸返回情形、第8行3.3種度量結(jié)點(diǎn)“純度”的指標(biāo)：4.信息增益ID35.增益率C4.56.基尼指數(shù)CART7.過擬合、欠擬合8.決策樹剪枝9.預(yù)剪枝10. 后剪枝24;.離散屬性：臍部 根蒂 色

10、澤連續(xù)屬性：密度 含糖率25;.連續(xù)屬性離散化技術(shù)：二分法 C4.5決策樹算法樣本集連續(xù)屬性 ，有n個不同的取值，將n個取值從小到大排序：劃分點(diǎn)t（數(shù)值）（數(shù)值）將 劃分為兩個子集和12,.,na aaDaDtDtD121,.,.,iina aa aatDtDtt顯然，對相鄰的屬性取值來說，t在區(qū)間中取任意值所產(chǎn)生的劃分結(jié)果都相同ia1ia1,iia a26;.27;.根結(jié)點(diǎn)的信息熵仍為：()0.998Ent D 220044()( loglog)04444tEnt D +228855()(loglog)0.96113131313tEnt D (,)413()()()17170.263ttGa

11、in DEnt DEnt DEnt D密度,0.381根結(jié)點(diǎn)包含17個訓(xùn)練樣本，密度有17個不同取值候選劃分點(diǎn)集合包含16個候選值每一個劃分點(diǎn)能得到一個對應(yīng)的信息增益密度密度好瓜好瓜0.243否0.245否0.343否0.360否0.403是10.437是20.481是30.556是40.593否0.680是50.634是60.639否0.657否0.666否0.697是70.719否0.774是80.381t tDtD28;.選擇“紋理”作為根結(jié)點(diǎn)劃分屬性與離散屬性不同，若當(dāng)前結(jié)點(diǎn)劃分屬性為連續(xù)屬性，該連續(xù)屬性還可被再次選作后代結(jié)點(diǎn)的最優(yōu)劃分屬性。29;.現(xiàn)實(shí)任務(wù)中，尤其在屬性數(shù)目較多時，存

12、在大量樣本出現(xiàn)缺失值。出于成本和隱私的考慮30;.1.屬性值缺失時，如何進(jìn)行劃分屬性選擇？（如何計算信息增益）2.給定劃分屬性，若樣本在該屬性上的值缺失，如何對樣本進(jìn)行劃分？（對于缺失屬性值的樣本如何將它從父結(jié)點(diǎn)劃分到子結(jié)點(diǎn)中）:D訓(xùn)練集:D訓(xùn)練集中在屬性a上沒有缺失值的樣本子集:vD被屬性a劃分后的樣本子集D:kDD中屬于第k類的樣本子集無缺失值樣本中在屬性上取值的樣本所占比例:無缺失值樣本所占比例:kp 無缺失值樣本中第k類所占比例:vr vaa31;.無缺失值的樣本子集上的信息增益D32;.對于問題2：對于有缺失值的樣本如何將它從父結(jié)點(diǎn)劃分到子結(jié)點(diǎn)中若樣本在劃分屬性a上的取值已知，則將劃

13、入與其取值對應(yīng)的子結(jié)點(diǎn)與其取值對應(yīng)的子結(jié)點(diǎn)，且樣本權(quán)值在子結(jié)點(diǎn)中保持為若樣本在劃分屬性a上的取值未知，則將同時劃入所有子結(jié)點(diǎn)所有子結(jié)點(diǎn)，且樣本權(quán)值在子結(jié)點(diǎn)中調(diào)整為，就是讓同一個樣本以不同的概率劃入不同的子結(jié)點(diǎn)中。xxxwvxr wxxxw其中，是為每個樣本賦予的一個權(quán)重x運(yùn)用運(yùn)用：問題1屬性值缺失時，如何進(jìn)行劃分屬性選擇？=屬性值缺失時，如何計算缺失屬性的信息增益？:vr 無缺失值樣本中在屬性上取值的樣本所占比例vaa33;.:kp 無缺失值樣本中第k類所占比例根結(jié)點(diǎn)包含樣本集中全部17個樣本屬性“色澤”無缺失值的樣例子集包含14個樣例：D=2,3,4,6,7,8,9,10,11,12,14,

14、15,16,17D好瓜好瓜(6個)壞瓜壞瓜(8個)1417無缺失值樣本所占比例34;.:vr 無缺失值樣本中在屬性上取值的樣本所占比例vaa:無缺失值樣本所占比例“紋理”被用于對根結(jié)點(diǎn)進(jìn)行劃分問題2給定劃分屬性，若樣本在該屬性上的值缺失，如何對樣本進(jìn)行劃分？35;.樣本劃分原則：屬性值已知，劃入與其取值對應(yīng)的子結(jié)點(diǎn)，樣本權(quán)值不變，仍為屬性值未知，劃入所有子結(jié)點(diǎn)，樣本權(quán)值調(diào)整為，讓同一個樣本以不同的概率劃入不同的子結(jié)點(diǎn)中xwvxr w:vr 無缺失值樣本中在屬性上取值的樣本所占比例vaa753,15 15 15“紋理”屬性值缺失的樣本編號為：8,10權(quán)值為：8和10同時進(jìn)入三個分支中，權(quán)值分別為： 8 ,1 0D=1xw36;.0.3810.205每個屬性d個屬性描述的樣本對樣本分類坐標(biāo)空間中的一個坐標(biāo)軸d維空間中的一個數(shù)據(jù)點(diǎn)在坐標(biāo)空間中