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

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

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