決策樹(基于統(tǒng)計學(xué)習(xí)方法書)課件

決策樹決策樹(基于統(tǒng)計學(xué)習(xí)方法書)決策樹決策樹（DecisionTree）是一種基本的分類與回歸方法，決策樹模型呈樹形結(jié)構(gòu)，在分類問題中，表示基于特征對實例進(jìn)行分類的過程?？梢哉J(rèn)為是if-then規(guī)則的集合?？梢哉J(rèn)為是定義在特征空間與類空間上的條件概率分布。決策樹(基于統(tǒng)計學(xué)習(xí)方法書)決策樹模型：if-then規(guī)則內(nèi)部節(jié)點：特征和屬性葉節(jié)點：類樹：由節(jié)點和有向邊組成路徑互斥且完備可以認(rèn)為是if-then規(guī)則的集合。由決策樹的根結(jié)點到葉結(jié)點的每一條路徑構(gòu)建一條規(guī)則;路徑上內(nèi)部結(jié)點的特征對應(yīng)著規(guī)則的條件，而葉結(jié)點的類對應(yīng)著規(guī)則的結(jié)論。決策樹(基于統(tǒng)計學(xué)習(xí)方法書)決策樹：條件概率分布決策樹還表示給定特征條件下類的條件概率分布此處條件概率分布：定義在特征空間的一個劃分(partition)上，將特征空間劃分為互不相交的單元(cell)或區(qū)域(region)，并在每個單元定義一個類的概率分布就構(gòu)成了一個條件概率分布。決策樹(基于統(tǒng)計學(xué)習(xí)方法書)決策樹：條件概率分布決策樹(基于統(tǒng)計學(xué)習(xí)方法書)學(xué)習(xí)目的從訓(xùn)練數(shù)據(jù)集中歸納出一組分類規(guī)則?？赡苡卸鄠€，可能沒有。需要的是一個與訓(xùn)練數(shù)據(jù)矛盾較小的決策樹，同時具有很好的泛化能力。從訓(xùn)練數(shù)據(jù)集估計條件概率模型?；谔卣骺臻g劃分的類的條件概率模型有無窮多個。我們選擇的條件概率模型應(yīng)該不僅對訓(xùn)練數(shù)據(jù)有很好的擬合，而且對未知數(shù)據(jù)有很好的預(yù)測。決策樹(基于統(tǒng)計學(xué)習(xí)方法書)學(xué)習(xí)步驟特征的選擇決策樹的生成：遞歸地選擇最優(yōu)特征，并根據(jù)該特征對訓(xùn)練數(shù)據(jù)進(jìn)行分割，使得對各個子數(shù)據(jù)集有一個最好的分類的過程。剪枝：利用損失函數(shù)最小原則進(jìn)行剪枝=用正則化的極大似然估計進(jìn)行模型選擇決策樹(基于統(tǒng)計學(xué)習(xí)方法書)學(xué)習(xí)步驟一：特征的選擇如果特征數(shù)量很多，在決策樹學(xué)習(xí)開始時對特征進(jìn)行選擇，只留下對訓(xùn)練數(shù)據(jù)有足夠分類能力的特征選擇的原則：信息增益或者信息增益比設(shè)有隨機(jī)變量(X,Y)，其聯(lián)合概率分布為：熵：表示隨機(jī)變量不確定性的度量條件熵：H(Y|X)表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性，定義為X給定條件下Y的條件概率分布的嫡對X的數(shù)學(xué)期望決策樹(基于統(tǒng)計學(xué)習(xí)方法書)學(xué)習(xí)步驟一：特征的選擇當(dāng)?shù)蘸蜅l件嫡中的概率由數(shù)據(jù)估計(特別是極大似然估計)得到時，所對應(yīng)的嫡與條件嫡分別稱為經(jīng)驗熵和經(jīng)驗條件嫡極大似然估計，只是一種概率論在統(tǒng)計學(xué)的應(yīng)用，它是參數(shù)估計的方法之一。說的是已知某個隨機(jī)樣本滿足某種概率分布，但是其中具體的參數(shù)不清楚，參數(shù)估計就是通過若干次試驗，觀察其結(jié)果，利用結(jié)果推出參數(shù)的大概值。極大似然估計是建立在這樣的思想上：已知某個參數(shù)能使這個樣本出現(xiàn)的概率最大，我們當(dāng)然不會再去選擇其他小概率的樣本，所以干脆就把這個參數(shù)作為估計的真實值。決策樹(基于統(tǒng)計學(xué)習(xí)方法書)學(xué)習(xí)步驟一：特征的選擇信息增益：

g(D,A)：特征A對訓(xùn)練數(shù)據(jù)集D的信息增益H(D)：集合D的經(jīng)驗嫡H(D|A)：特征A給定條件下D的經(jīng)驗條件嫡改進(jìn)：信息增益值的大小是相對于訓(xùn)練數(shù)據(jù)集而言的，并沒有絕對意義。在分類問題困難時，也就是說在訓(xùn)練數(shù)據(jù)集的經(jīng)驗嫡大的時候，信息增益值會偏大，反之，信息增益值會偏小。信息增益比：決策樹(基于統(tǒng)計學(xué)習(xí)方法書)學(xué)習(xí)步驟二：決策樹的生成ID3算法：基于信息增益選擇特征C4.5算法：基于信息增益比選擇特征（C4.5并不一個算法，而是一組算法—C4.5，非剪枝C4.5和C4.5規(guī)則）決策樹(基于統(tǒng)計學(xué)習(xí)方法書)ID3算法例子：1.特征的選擇,計算信息增益，并選擇結(jié)果最大時所對應(yīng)的特征決策樹(基于統(tǒng)計學(xué)習(xí)方法書)ID3算法例子：2.樹的生成決策樹(基于統(tǒng)計學(xué)習(xí)方法書)學(xué)習(xí)步驟三：剪枝決策樹的生成算法容易構(gòu)建過于復(fù)雜的決策樹，可能只是對已知數(shù)據(jù)很好分類，對未知數(shù)據(jù)分類效果不清楚，產(chǎn)生過擬合在決策樹學(xué)習(xí)中將已生成的樹進(jìn)行簡化的過程稱為剪枝。具體地，剪枝從下而上，從已生成的樹上裁掉一些子樹或葉結(jié)點，并將其根結(jié)點或父結(jié)點作為新的葉結(jié)點，從而簡化分類樹模型.此處介紹一種簡單的算法實現(xiàn)：極小化決策樹整體的損失函數(shù)(lossfimction)或代價函數(shù)(costfunction)。損失函數(shù)(lossfimction)：對于單個訓(xùn)練樣本的誤差代價函數(shù)(costfunction)：對于整個訓(xùn)練集，所有樣本誤差總和的平均決策樹(基于統(tǒng)計學(xué)習(xí)方法書)學(xué)習(xí)步驟三：剪枝設(shè)樹T的葉結(jié)點個數(shù)為|T|,t是樹T的葉結(jié)點，該葉結(jié)點有Nt個樣本點，其中k類的樣本點有Ntk個，k=1,2,...,K，Ht(T)為葉結(jié)點t上的經(jīng)驗嫡，決策樹的損失函數(shù)：C(T)：模型對訓(xùn)練數(shù)據(jù)的預(yù)測誤差，即模型與訓(xùn)練數(shù)據(jù)的擬合程度|T|：模型復(fù)雜度正則化參數(shù)a>=0控制兩者之間的影響。剪枝實質(zhì)上是當(dāng)a確定時，選擇損失函數(shù)最小的模型，即損失函數(shù)最小的子樹。此時，損失函數(shù)正好表示了對模型的復(fù)雜度和訓(xùn)練數(shù)據(jù)的擬合兩者的平衡。決策樹(基于統(tǒng)計學(xué)習(xí)方法書)學(xué)習(xí)步驟三：剪枝決策樹生成只考慮了通過提高信息增益(或信息增益比)對訓(xùn)練數(shù)據(jù)進(jìn)行更好的擬合，學(xué)習(xí)局部的模型；決策樹剪枝通過優(yōu)化損失函數(shù)還考慮了減小模型復(fù)雜度，學(xué)習(xí)整體的模型。決策樹(基于統(tǒng)計學(xué)習(xí)方法書)CART算法CART（classificationandregressiontree）:分類回歸樹1.生成樹回歸樹：用平方誤差最小化準(zhǔn)則分類樹：基尼指數(shù)(Giniindex)最小化準(zhǔn)則，進(jìn)行特征選擇ps:基尼指數(shù)Gini(D)表示集合D的不確定性，基尼指數(shù)Gini(D,A)表示經(jīng)A=a分割后集合D的不確定性?；嶂笖?shù)值越大，樣本集合不確定性就越大，因此不同于之前選信息增益和信息增益比最大，此算法選基尼指數(shù)最小的特征2.剪枝決策樹(基于統(tǒng)計學(xué)習(xí)方法書)CART算法剪枝:(1)剪枝。形成一個子樹序列在剪枝過程中，計算子樹的損失函數(shù):可以用遞歸的方法對樹進(jìn)行剪枝，將a從小增大，a0<a1<...<an<+無窮，產(chǎn)生一系列的區(qū)間[ai，ai+1)，i=0,1,...,n；剪枝得到的子樹序列對應(yīng)著區(qū)間[ai，ai+1)，i=0,1,...,n的最優(yōu)子樹序列{T0,T1,...,Tn}，序列中的子樹是嵌套的。對T0中每一內(nèi)部結(jié)點t，計算表示剪枝后整體損失函數(shù)減少的程度，在T0中剪去g(t)最小的Tt，將得到的子樹作為T1，同時將最小的g(t)設(shè)為a1，T1為區(qū)間[a1，a2)的最優(yōu)子樹。如此剪枝下去，直至得到根結(jié)點。在這一過程中，不斷地增加a的值，產(chǎn)生新的區(qū)間。決策樹(基于統(tǒng)計學(xué)習(xí)方法書)CART算法剪枝:(2)在剪枝得到的子樹序列T0,T1,...,Tn中通過交叉驗證選取最優(yōu)子樹Ta具體地，利用獨立的驗證數(shù)據(jù)集，測試子樹序列T0,T1,...,Tn中各棵子樹的平方