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

是概率

的單調遞減函數；可加性：兩個獨立符號所產生的不確定性應等于各自不確定性之和，即同時滿足這三個條件的函數

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

預剪枝決策樹的剪枝策略

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

壞瓜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不足：基于“貪心”本質禁止某些分支展開，帶來了欠擬合的風險預剪枝使得決策樹的很多分支都沒有“展開”優點：降低過擬合的風險減少了訓練時間開銷和測試時間開銷后剪枝先從訓練集生成一棵完整的決策樹，然后自底向上地對非葉結點進行考察，若將該結點對應的子樹替換為葉結點能帶來決策樹泛化性能提升，則將該子樹替換為葉結點。驗證集：4,5,8,9,11,124,13(T,F)5(F)9(F)8(F)11,12(T,T)驗證集精度：考察結點順序：⑥⑤②③①6,7,15,176,7,151767,157158,9(T,F)減去結點⑥驗證集變為：訓練集：好瓜

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

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

劃分為兩個子集

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

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

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

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

劃入與其取值對應的子結點，且樣本權值在子結點中保持為若樣本

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

同時劃入所有子結點，且樣本權值在子結點中調整為

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

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