決策樹(完整)公共課

決策樹(完整)公共課第4章決策樹根據(jù)訓(xùn)練數(shù)據(jù)是否擁有標記信息學(xué)習(xí)任務(wù)決策樹（decisiontree）模型常常用來解決分類和回歸問題。常見的算法包括CART(ClassificationAndRegressionTree)、ID3、C4.5等。半監(jiān)督學(xué)習(xí)：輸入數(shù)據(jù)部分被標識，部分沒有被標識，介于監(jiān)督學(xué)習(xí)與非監(jiān)督學(xué)習(xí)之間。分類、回歸聚類監(jiān)督學(xué)習(xí)(supervisedlearning)無監(jiān)督學(xué)習(xí)(unsupervisedlearning)半監(jiān)督學(xué)習(xí)(semi-supervisedlearning)(reinforcementlearning)二分類學(xué)習(xí)任務(wù)屬性屬性值根結(jié)點：包含全部樣本葉結(jié)點：對應(yīng)決策結(jié)果“好瓜”“壞瓜”內(nèi)部結(jié)點：對應(yīng)屬性測試決策樹學(xué)習(xí)的目的：為了產(chǎn)生一顆泛化能力強的決策樹，即處理未見示例能力強。無需劃分無法劃分不能劃分無需劃分無法劃分不能劃分Hunt算法：1,2,3,4,5,6,8,10,151,2,3,4,56,8,151068,15815第（2）種情形：設(shè)定為該結(jié)點所含樣本最多的類別利用當前結(jié)點的后驗分布第（3）種情形：設(shè)定為其父結(jié)點所含樣本最多的類別把父結(jié)點的樣本分布作為當前結(jié)點的先驗分布決策樹學(xué)習(xí)的關(guān)鍵是算法的第8行：選擇最優(yōu)劃分屬性什么樣的劃分屬性是最優(yōu)的？我們希望決策樹的分支結(jié)點所包含的樣本盡可能屬于同一類別，即結(jié)點的“純度”越來越高，可以高效地從根結(jié)點到達葉結(jié)點，得到?jīng)Q策結(jié)果。三種度量結(jié)點“純度”的指標：信息增益增益率基尼指數(shù)1.信息增益香農(nóng)提出了“信息熵”的概念，解決了對信息的量化度量問題。香農(nóng)用“信息熵”的概念來描述信源的不確定性。信息熵對于二分類任務(wù)一個事件的信息量就是這個事件發(fā)生的概率的負對數(shù)。信息熵是跟所有事件的可能性有關(guān)的，是平均而言發(fā)生一個事件得到的信息量大小。所以信息熵其實是信息量的期望。假設(shè)我們已經(jīng)知道衡量不確定性大小的這個量已經(jīng)存在了，不妨就叫做“信息量”不會是負數(shù)不確定性函數(shù)

是概率

的單調(diào)遞減函數(shù)；可加性：兩個獨立符號所產(chǎn)生的不確定性應(yīng)等于各自不確定性之和，即同時滿足這三個條件的函數(shù)

是負的對數(shù)函數(shù)，即信息增益一般而言，信息增益越大，則意味著使用屬性a來進行劃分所獲得的“純度提升”越大。決策樹算法第8行選擇屬性著名的ID3決策樹算法舉例：求解劃分根結(jié)點的最優(yōu)劃分屬性根結(jié)點的信息熵：以屬性“色澤”為例計算其信息增益數(shù)據(jù)集包含17個訓(xùn)練樣例：8個正例（好瓜）占9個反例（壞瓜）占對于二分類任務(wù)用“色澤”將根結(jié)點劃分后獲得3個分支結(jié)點的信息熵分別為：屬性“色澤”的信息增益為：若把“編號”也作為一個候選劃分屬性，則屬性“編號”的信息增益為：根結(jié)點的信息熵仍為：用“編號”將根結(jié)點劃分后獲得17個分支結(jié)點的信息熵均為：則“編號”的信息增益為：遠大于其他候選屬性信息增益準則對可取值數(shù)目較多的屬性有所偏好2.增益率增益率準則對可取值數(shù)目較少的屬性有所偏好著名的C4.5決策樹算法綜合了信息增益準則和信息率準則的特點：先從候選劃分屬性中找出信息增益高于平均水平的屬性，再從中選擇增益率最高的。3.基尼指數(shù)基尼值基尼指數(shù)著名的CART決策樹算法過擬合：學(xué)習(xí)器學(xué)習(xí)能力過于強大，把訓(xùn)練樣本自身的一些特點當作了所有潛在樣本都會具有的一般性質(zhì)，導(dǎo)致泛化性能下降。欠擬合：學(xué)習(xí)器學(xué)習(xí)能力低下，對訓(xùn)練樣本的一般性質(zhì)尚未學(xué)好。過擬合無法徹底避免，只能做到“緩解”。剪枝，即通過主動去掉一些分支來降低過擬合的風(fēng)險。

預(yù)剪枝決策樹的剪枝策略

后剪枝預(yù)剪枝：在決策樹生成過程中，對每個結(jié)點在劃分前先進行估計，若當前結(jié)點的劃分不能帶來決策樹泛化性能提升，則停止劃分并將當前結(jié)點標記為葉結(jié)點后剪枝：先從訓(xùn)練集生成一棵完整的決策樹，然后自底向上地對非葉結(jié)點進行考察，若將該結(jié)點對應(yīng)的子樹替換為葉結(jié)點能帶來決策樹泛化性能提升，則將該子樹替換為葉結(jié)點。留出法：將數(shù)據(jù)集D劃分為兩個互斥的集合：訓(xùn)練集S和測試集T且預(yù)剪枝1,2,3,14訓(xùn)練集：好瓜

壞瓜1,2,3,6,7,10,14,15,16,176,7,15,1710,16精度：正確分類的樣本占所有樣本的比例4,5,13(T,T,F)8,9(T,F)11,12(T,T)驗證集：4,5,8,9,11,12,13不足：基于“貪心”本質(zhì)禁止某些分支展開，帶來了欠擬合的風(fēng)險預(yù)剪枝使得決策樹的很多分支都沒有“展開”優(yōu)點：降低過擬合的風(fēng)險減少了訓(xùn)練時間開銷和測試時間開銷后剪枝先從訓(xùn)練集生成一棵完整的決策樹，然后自底向上地對非葉結(jié)點進行考察，若將該結(jié)點對應(yīng)的子樹替換為葉結(jié)點能帶來決策樹泛化性能提升，則將該子樹替換為葉結(jié)點。驗證集：4,5,8,9,11,124,13(T,F)5(F)9(F)8(F)11,12(T,T)驗證集精度：考察結(jié)點順序：⑥⑤②③①6,7,15,176,7,151767,157158,9(T,F)減去結(jié)點⑥驗證集變?yōu)椋河?xùn)練集：好瓜

壞瓜1,2,3,6,7,10,14,15,16,17后剪枝決策樹預(yù)剪枝決策樹保留了更多的分支欠擬合風(fēng)險很小泛化能力優(yōu)于預(yù)剪枝決策樹訓(xùn)練時間開銷比未減枝和預(yù)剪枝決策樹大得多生產(chǎn)完全決策樹所有非葉節(jié)點逐一考察知識回顧：四類學(xué)習(xí)任務(wù)Hunt算法3種遞歸返回情形、第8行3種度量結(jié)點“純度”的指標：信息增益 ID3增益率 C4.5基尼指數(shù) CART過擬合、欠擬合決策樹剪枝預(yù)剪枝后剪枝離散屬性：臍部根蒂色澤···連續(xù)屬性：密度含糖率···連續(xù)屬性離散化技術(shù)：二分法 C4.5決策樹算法樣本集連續(xù)屬性

，有n個不同的取值，將n個取值從小到大排序：劃分點t（數(shù)值）將

劃分為兩個子集

和顯然，對相鄰的屬性取值

來說，t在區(qū)間中取任意值所產(chǎn)生的劃分結(jié)果都相同根結(jié)點的信息熵仍為：根結(jié)點包含17個訓(xùn)練樣本，密度有17個不同取值候選劃分點集合包含16個候選值每一個劃分點能得到一個對應(yīng)的信息增益選擇“紋理”作為根結(jié)點劃分屬性與離散屬性不同，若當前結(jié)點劃分屬性為連續(xù)屬性，該連續(xù)屬性還可被再次選作后代結(jié)點的最優(yōu)劃分屬性?，F(xiàn)實任務(wù)中，尤其在屬性數(shù)目較多時，存在大量樣本出現(xiàn)缺失值。出于成本和隱私的考慮屬性值缺失時，如何進行劃分屬性選擇？（如何計算信息增益）給定劃分屬性，若樣本在該屬性上的值缺失，如何對樣本進行劃分？（對于缺失屬性值的樣本如何將它從父結(jié)點劃分到子結(jié)點中）訓(xùn)練集訓(xùn)練集中在屬性a上沒有缺失值的樣本子集被屬性a劃分后的樣本子集中屬于第k類的樣本子集無缺失值樣本中在屬性 上取值 的樣本所占比例無缺失值樣本所占比例無缺失值樣本中第k類所占比例無缺失值的樣本子集

上的信息增益對于問題2：對于有缺失值的樣本如何將它從父結(jié)點劃分到子結(jié)點中若樣本

在劃分屬性a上的取值已知，則將

劃入與其取值對應(yīng)的子結(jié)點，且樣本權(quán)值在子結(jié)點中保持為若樣本

在劃分屬性a上的取值未知，則將

同時劃入所有子結(jié)點，且樣本權(quán)值在子結(jié)點中調(diào)整為

，就是讓同一個樣本以不同的概率劃入不同的子結(jié)點中。其中， 是為每個樣本 賦予的一個權(quán)重運用：問題1 屬性值缺失時，如何進行劃分屬性選擇？ =屬性值缺失時，如何計算缺失屬性的信息增益？無缺失值樣本中在屬性 上取值 的樣本所占比例無缺失值樣本中第k類所占比例根結(jié)點包含樣本集 中全部17個樣本屬性“色澤”無缺失值的樣例子集包含14個樣例：好瓜(6個)壞瓜(8個)無缺失值樣本所占比例無缺失值樣本中在屬性 上取值 的樣本所占比例無缺失值樣本所占比例“紋理”被用于對根結(jié)點進行劃分問題2 給定劃分屬性，若樣本在該屬性上的值缺失，如何對樣本進行劃分？樣本劃分原則：屬性值已知，劃入與其取值對應(yīng)的子結(jié)點，樣本權(quán)值不變，仍為屬性值未知，劃入所有子結(jié)點，樣本權(quán)值調(diào)整為

，讓同一個樣本以不同的概率劃入不同的子結(jié)點中無缺失值樣本中在屬性 上取值 的樣本所占比例“紋理”屬性值缺失的樣本編號為：8,10 權(quán)值為：{8}和{10}同時進入三個分支中，權(quán)值分別為：0.3