1、決策樹
決策樹是基于樹的結(jié)構(gòu)來進(jìn)行決策的靶橱，通常在經(jīng)過一系列的判斷或“子決策”之后，得出最終的決策路捧，也即是我們最終所希望獲得的結(jié)論关霸。
決策樹學(xué)習(xí)的目的：得到一顆泛化能力強，即處理未見示例能力強的決策樹
2杰扫、決策樹的構(gòu)成
3队寇、決策樹生成的基本算法
決策樹生成是一個遞歸過程，有三種情形導(dǎo)致遞歸返回
當(dāng)前結(jié)點包含的樣本全屬于同一類章姓，無需分類佳遣。此處直接將當(dāng)前結(jié)點標(biāo)記為C類（C類為樣本類別）葉子結(jié)點识埋。
當(dāng)前屬性集為空，或者所有樣本在所有屬性上取值相同零渐，無法劃分窒舟。
當(dāng)前結(jié)點包含的樣本集合為空，不能劃分相恃，分支結(jié)點標(biāo)記為葉子結(jié)點辜纲，類別標(biāo)記為當(dāng)前樣本集合中同類樣本最多的類。
在第2種情形下拦耐，把當(dāng)前結(jié)點標(biāo)記為葉結(jié)點耕腾，但類別設(shè)定為該結(jié)點所含樣本最多的類別。在第3種情形下杀糯，把當(dāng)前結(jié)點標(biāo)記為葉節(jié)點扫俺，但類別設(shè)定為其父結(jié)點所含樣本最多的類別。它們的不同點是 固翰，第2種是利用當(dāng)前結(jié)點的后驗分布狼纬，第3種則是把父結(jié)點的樣本分布作為當(dāng)前結(jié)點的先驗分布。
4骂际、劃分選擇
問題：如何選擇最優(yōu)化分屬性疗琉，我們希望結(jié)點的“純度”越來越高
信息增益
信息熵：度量樣本集合純度最常用的一種指標(biāo)。其公式如下：
的值越小歉铝，則
的純度越高盈简，
代表的是當(dāng)前樣本集合
信息增益：對于同一屬性的不同取值計算出其信息熵后賦予權(quán)重，樣本數(shù)越多的分枝其影響越大太示，由此可以計算出信息增益柠贤。
一般而言，信息增益越大类缤，則意味著使用該屬性來進(jìn)行劃分所獲得的“純度提升”越大偷办。因此囚企，我們可用信息增益來進(jìn)行決策樹的劃分屬性選擇。
增益率
在C4.5決策樹算法中，不直接使用信息增益拯欧，而是使用“增益率”來選擇最優(yōu)劃分屬性箱季。
增益率定義：
其中
C4.5是使用一個啟發(fā)式：先從候選劃分屬性中找出信息增益高于平均水平的屬性玄柏，再從中選擇增益率最高的旷偿。
基尼指數(shù)
CART決策樹常用基尼指數(shù)來選擇劃分屬性
基尼值：數(shù)據(jù)集的純度度量
基尼指數(shù)：
基尼指數(shù)小的屬性作為最優(yōu)化分屬性。
5降允、剪枝
剪枝是解決策樹學(xué)習(xí)算法“過擬合”的主要手段恩闻，基本策略有“預(yù)剪枝”和“后剪枝”
6、連續(xù)值與缺失值
連續(xù)值處理
問題：連續(xù)屬性的可取值數(shù)目不再有限
處理方法：使用二分法對連續(xù)值進(jìn)行處理剧董，即是以某一個值為分界幢尚，對父結(jié)點進(jìn)行劃分破停，則正是C4.5決策樹算法中采用的機制。
缺失值處理
問題一：如何在屬性值缺失的情況下進(jìn)行劃分屬性選擇尉剩？（相應(yīng)最優(yōu)劃分屬性如何確定）
為樣本賦予權(quán)重真慢，再計算信息增益以確定最優(yōu)劃分屬性。
問題二：給定劃分屬性理茎，若樣本在該屬性上的值缺失黑界，如何對樣本進(jìn)行劃分？（即樣本缺失該屬性應(yīng)如何劃分）
樣本x取值已知皂林，則劃入相應(yīng)的子結(jié)點朗鸠，并保持其權(quán)值w。
樣本x取值未知础倍，則劃入全部子結(jié)點中烛占，并調(diào)整其權(quán)值，即是以不同的概率劃入到不同的子結(jié)點去沟启。
7忆家、多變量決策樹
在面對復(fù)雜的決策樹時，由于要進(jìn)行大量的屬性測試德迹，使用平行于軸的分類邊界芽卿，預(yù)測時間開銷會很大，而多變量決策樹就是一種實現(xiàn)斜劃分甚至更復(fù)雜劃分的決策樹胳搞，它不是尋找一個最優(yōu)化分屬性卸例，而是試圖建立一個合適的線性分類器。
