決策樹1.原理1.1模型簡介決策樹是一種基本的回歸和分類算法。在分類問題中，可以認(rèn)為是一系列if-then規(guī)則的幾何。決策樹學(xué)通常包括三個步驟：特征選擇，決策樹的生成，決策樹的修剪。定義：決策樹由結(jié)點(diǎn)和有向邊組成，內(nèi)部節(jié)點(diǎn)表示一個特征和屬性，葉子結(jié)點(diǎn)表示一個類。性質(zhì)：決策樹路徑（或者對應(yīng)的if-then規(guī)則）具有互斥且完備性：每一個實(shí)例都被一條路徑或規(guī)則所覆蓋，而且只被這條路徑或規(guī)則所覆蓋。決策樹學(xué)習(xí)：能夠正確對數(shù)據(jù)集進(jìn)行分類的決策樹可能有多個，也可能一個也沒有，我們的目的是找到一個與訓(xùn)練數(shù)據(jù)集矛盾較小的，同時具有很好泛化能力的決策樹。特征選擇：一種是在決策樹學(xué)習(xí)開始的時候，對特征進(jìn)行選擇，只留下對訓(xùn)練數(shù)據(jù)有足夠分類能力的特征，一種是在學(xué)習(xí)過程中對訓(xùn)練數(shù)據(jù)分割成自己的時候，選擇最優(yōu)的特征進(jìn)行分割。決策樹生成：一般這是一個遞歸的規(guī)程。決策樹的剪枝：提高決策樹的泛化能力。1.2特征選擇特征選擇的準(zhǔn)則一般是：信息增益和信息增益比1.2.1信息增益a?信息增益：信息增益大的特征具有更強(qiáng)的分類能力，即選擇信息增益值大的特征作為最優(yōu)特征。b?信息熵：表示變量的不確定性（在得知特征X的信息時，使得Y的信息不確定性減少的程度），熵越大，變量的不確定性越大。設(shè)X是一個取有限值的離散型隨機(jī)變量，其概率分布為：p（X=x）=pii則隨機(jī)變量X的熵定義為:

H(X)=-工plogp注：若pi=0,定義OlogO二0。其中若對數(shù)以2為底，熵的單位稱為比特，若以e為底，單位稱為納特。c.條件熵：隨機(jī)變量X在給定條件下隨機(jī)變量Y的條件熵H(Y|X)表示：X給定條件下Y的條件概率分布的熵關(guān)于X的數(shù)學(xué)期望：iiH(YIX)二工pH(YIX二x)ii其中，P(X=x)=p當(dāng)熵和條件熵有數(shù)據(jù)估計(jì)(特別是極大似然估計(jì))得到時，被分別稱為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵。信息增益：特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g(D|A)定義為：g(D,A)=H(D)-H(DIA)其中，H(D)為集合D的經(jīng)驗(yàn)熵，H(DIA)為特征A給定條件下D的經(jīng)驗(yàn)條件熵。d.信息增益的計(jì)算方法。設(shè)：訓(xùn)練數(shù)據(jù)集D,個數(shù)為|D|。K個類，分別為Ck.每個類內(nèi)個數(shù)|Ck|根據(jù)特征A,能夠?qū)⒂?xùn)練集劃分為n個子集：D],D2，…Dn。|D」為該子集的樣本個數(shù)。子集Di中屬于類Ck的個數(shù)|Dik|o則計(jì)算信息增益的公式為：數(shù)據(jù)集D的信息熵：lOg(!CK-lOg(!CK-IDIH(DIA)H(DIA)=工凹H(D)=工也藝 log(^￡iH(D)= i iklOg( ikIDIiIDIIDIIDI注：此公式意義：在特征A作用下，將數(shù)據(jù)集D分為多個q。這時關(guān)于D的熵等于關(guān)于Di熵的均值。計(jì)算信息增益。1.2.2信息增益比gRgR(D,A)g(D,A)H(D)其中HP）表示特征集D關(guān)于特征A的值得熵。1.3決策樹的生成1.3.1ID3算法a.選取特征：信息增益準(zhǔn)則b?算法終止條件：所有特征的信息增益均很小或者沒有特征可以選擇。c.算法過程：Algorithm1ID3輸入訓(xùn)練數(shù)據(jù)集D,特征集A,閾值E輸出1：決策樹T若D中所有實(shí)例屬于同一類Ck,則T為單節(jié)點(diǎn)樹，將Ck作為該結(jié)點(diǎn)類標(biāo)記,返回T。2若A=0,則T為單節(jié)點(diǎn)樹，將D中實(shí)例數(shù)最多的類作為該結(jié)點(diǎn)類標(biāo)記,返回T。3:否則，計(jì)算A中各特征對D的信息增益，選取信息增益最大的特征Ag。4：如果特征A的信息增益小于E,則T為單結(jié)點(diǎn)樹，將實(shí)例數(shù)最多g的類作為該結(jié)點(diǎn)的類標(biāo)記，返回T。5：否則，對Ag將訓(xùn)練集劃分為多個Di，創(chuàng)建子結(jié)點(diǎn)。每個Di中實(shí)例數(shù)最多的類作為該子結(jié)點(diǎn)的類標(biāo)記。返回此時構(gòu)建的樹To6：對每一個子結(jié)點(diǎn)，以Di為訓(xùn)練集，｛AAg｝為特征集，遞歸調(diào)用上述5個步驟，得到字?jǐn)?shù)已，返回Ti.1.3.2C4.5算法算法過程與ID3算法類似。不同的是該算法將信息增益比作為特征選擇的準(zhǔn)則。1.4決策樹剪枝原理：極小化決策樹整體的損失函數(shù)。方法：設(shè)：樹T的葉結(jié)點(diǎn)個數(shù)為|T|，T是樹T的一個葉結(jié)點(diǎn)，并且包含Nt個樣本點(diǎn)。其中k類的樣本點(diǎn)個數(shù)為Ntk。則，決策樹的損失函數(shù)定義為：C(T)二藝NH(T)+aITIattt=1KNN其中’H(T)=一芳 iog(~N^)k=1t t上式中，Nt的意義：假設(shè)我們最后的分類結(jié)果是為每個樣本都分配了一個葉子節(jié)點(diǎn)，則此時的經(jīng)驗(yàn)熵為0(llogl=0)。然而極端情況基本是不存在的。我們一般都會有類別數(shù)量的限制。想像這樣的一個情況，對于前i個類我們?yōu)槠涿總€分配一個樣本，后面所有的樣本歸為一個類，此時損失可能比較小.但是這樣的分類完全沒有意義(單葉子節(jié)點(diǎn)過擬合，后面的欠擬合)。所以在每個葉子節(jié)點(diǎn)的經(jīng)驗(yàn)熵前面乘以一個系數(shù)Nt。放大欠擬合部分的損失，以平衡損失函數(shù)。當(dāng)然如果僅僅這樣做，并不能防止過擬合，還應(yīng)該加上正則項(xiàng)來防止過擬合。對于上式般令C(T)等于左邊項(xiàng)，表示模型對訓(xùn)練數(shù)據(jù)的預(yù)測誤差。第二項(xiàng)為正則項(xiàng)，避免過擬合，|T|可以看做是對模型復(fù)雜度的度量。樹的剪枝算法：Algorithm2樹的剪枝算法輸入樹T，參數(shù)a輸出1：修剪后的決策樹T計(jì)算每個結(jié)點(diǎn)的經(jīng)驗(yàn)熵2遞歸的從樹的葉結(jié)點(diǎn)向上回縮，計(jì)算前后整體樹的損失函數(shù)值，如果減小或相等則剪枝。3:返回2，直至不能繼續(xù)為止1.4.1REP(錯誤率降低剪枝)上面所講的方法叫做錯誤率降低剪枝該算法以bottom-up的方式遍歷所有的子樹，對于完全決策樹中的每一個非葉子節(jié)點(diǎn)的子樹，我們嘗試著把它替換成一個葉子節(jié)點(diǎn)，該葉子節(jié)點(diǎn)的類別我們用子樹所覆蓋訓(xùn)練樣本中存在最多的那個類來代替，這樣就產(chǎn)生了一個簡化決策樹，然后比較這兩個決策樹在測試數(shù)據(jù)集中的表現(xiàn)，如果簡化決策樹在測試數(shù)據(jù)集中的錯誤比較少，那么該子樹就可以替換成葉子節(jié)點(diǎn)。直至沒有任何子樹可以替換使得測試數(shù)據(jù)集的表現(xiàn)得以改進(jìn)時，算法就可以終止。

1.4.2PEP悲觀錯誤剪枝該方法基于訓(xùn)練數(shù)據(jù)的誤差評估，因此不用單獨(dú)找剪枝數(shù)據(jù)集。但訓(xùn)練數(shù)據(jù)也帶來錯分誤差偏向于訓(xùn)練集，因此需要加入修正1/2。是自上而下的修剪。具有T個節(jié)點(diǎn)的樹的誤差率衡量為:煩巧一乙刃啲其中，e(t)表示節(jié)點(diǎn)t之下的訓(xùn)練集的誤判的個數(shù)。N(t)表示節(jié)點(diǎn)t之下的訓(xùn)練集的總個數(shù)。PEP算法流程:INOUT:TREEOUTPUT:PRUNINGTREEPROCESS:Forallnodes:自頂向下逐層遍歷:If剪枝前子樹的錯誤數(shù)-刪除該節(jié)點(diǎn)所在分支剪枝后葉子錯誤數(shù)〉剪枝前分類錯誤個數(shù)的標(biāo)準(zhǔn)差ENDFOR其中標(biāo)準(zhǔn)差的計(jì)算：子樹的錯誤個數(shù)經(jīng)過驗(yàn)證可以近似看成是二項(xiàng)分布，就可以根據(jù)二項(xiàng)分布的標(biāo)準(zhǔn)差公式算出標(biāo)準(zhǔn)差。B(N,e)的二項(xiàng)分布，根據(jù)公式，均值為Ne,方差為Ne(1e。N為子樹樣本總個數(shù)。子樹中有N的實(shí)例，就是進(jìn)行N次試驗(yàn)，每次實(shí)驗(yàn)的錯誤的概率為e。118T9__匚TOI例子：TOI那么根據(jù)e的公式e=(7+0.5X3)/16=8.5/16=0.53根據(jù)二項(xiàng)分布的標(biāo)準(zhǔn)差公式，標(biāo)準(zhǔn)差為(16X0.53X(1-0.53))八0.5=2.00子樹的錯誤數(shù)為“所有葉子實(shí)際錯誤數(shù)+0.5調(diào)整值”=7+0.5X3=8.5把子樹剪枝后，只剩下T4,T4的錯誤數(shù)為7+0.5=7.5這樣，8.5-2<7.5，因此不滿足剪枝標(biāo)準(zhǔn)，不能用T4替換整個子樹。http://www.jianshu.eom/p/794d08199e5e1.5CART算法1.5.1CART生成CART樹假設(shè)決策樹是二叉樹。剪枝標(biāo)準(zhǔn)同樣是損失函數(shù)最小。使用基尼系數(shù)選

擇最優(yōu)特征，選擇基尼系數(shù)小得特征作為最優(yōu)特征。假設(shè)有k個類，則概率分布的基尼系數(shù)定義為：G(p)二芳p(1一p)kkk=1二分類問題的概率分布基尼系數(shù)為：G(p)二2p(l—p) (j)在決策樹問題中，利用基尼系數(shù)進(jìn)行特征選擇的原理是：G(D,A)G(D,A)=DG(UHDG(D2)其中G(D]),G(D2)的計(jì)算方法利用式(j)：來計(jì)算的。Algorithm3CART生成算法輸入 訓(xùn)練數(shù)據(jù)集D,算法終止條件輸出CART決策樹T在每個結(jié)點(diǎn)處，計(jì)算現(xiàn)有特征A對該數(shù)據(jù)集的基尼系數(shù)。因?yàn)?： CART是二叉樹，然而有的特征卻有多個值，根據(jù)A=a可以將訓(xùn)練數(shù)據(jù)集分成兩個不同的子集，應(yīng)分別計(jì)算A=a時的基尼系數(shù)在所有特征A以及A所有可能的切分點(diǎn)中，選擇基尼系數(shù)最小的2 特征及此時A的取值a為最優(yōu)的切分點(diǎn)，從此結(jié)點(diǎn)生成兩個子結(jié)點(diǎn)，將數(shù)據(jù)集分到不同的子結(jié)點(diǎn)中去3: 遞歸調(diào)用上述兩個步驟，直到滿足終止條件，返回決策樹T算法終止條件是樣本個數(shù)小于預(yù)定閾值或只有同一類，樣本集的基尼系數(shù)小于預(yù)定閾值，沒有更多特征。1.5.2CART剪枝(代價復(fù)雜度剪枝ccp)剪枝的前提是剪枝后損失函數(shù)不增大：根據(jù)子樹的損失函數(shù)公式：Ca(T)=甲)+叩|其中，T為任意子樹，C(T)為對訓(xùn)練數(shù)據(jù)的預(yù)測誤差(如基尼系數(shù))，|T|為樹的葉結(jié)點(diǎn)個數(shù)，a>=0為參數(shù)，Ca(T)為參數(shù)是a時的子樹T的整體損失。a的意義在于權(quán)衡對訓(xùn)練數(shù)據(jù)的擬合程度與模型的復(fù)雜度。cpp主要思想，不同的a，可剪枝的情況也不一樣，所以該方法就是計(jì)算出所有不同的情況，然后利用交叉驗(yàn)證的方法來選擇最優(yōu)的模型。對整體樹T的任意內(nèi)部節(jié)點(diǎn)t,設(shè)以t為單節(jié)點(diǎn)樹的子樹損失函數(shù)為：Ca(t);且由損失函數(shù)公式得：Ca(t)=C(t)+a;以t為根節(jié)點(diǎn)的子樹7；的損失函數(shù)為：Ca(Tt)=C(Tt)+a\Tt\易知：C(Tf)與0(t)的大小關(guān)系關(guān)于a的形式為：當(dāng)a等于0或者充分小時，Ca(Tt)<Ca(t);當(dāng)a增大到等于g(t)=c(t)-c(rt)時，Ca(Tt)=Ca(t);\Tt\-1當(dāng)a繼續(xù)增大，則有：Cn(Tt)>Cn(t);Lv1/ Lv關(guān)于統(tǒng)計(jì)學(xué)習(xí)方法這本書中P73頁，g(t)表示剪枝后整體損失的減小程度，而我們每次剪枝反而是剪去g(t)最小的，解釋：我們知道要想使剪枝后的損失減小，a的取值應(yīng)該大于等于g(t)，而我們剪枝的過程是需要滿足a逐漸增大(一方面模擬下面算法中a逐漸增大的過程，以得到所有情況下的最有剪枝策略；隨著a的不斷增大，總會有一顆子樹該剪枝，而其他子樹不需要剪枝，這樣隨著a的增大，才會不斷的剪枝，最后回溯到整棵樹的根節(jié)點(diǎn)。另一方面,a逐漸增大，后面剪枝選取的a仍然能夠保證前面的剪枝操作是正確的。，從而得到n顆剪枝后的子樹，最后通過交叉驗(yàn)證得到最優(yōu)子樹。算法策略：初始化參數(shù)：令a=+8,k=0(計(jì)數(shù)器)，T=T0O對該樹的所有內(nèi)部節(jié)點(diǎn)t，計(jì)算它的g(t)和a=min(a,g(t))。對g(t)=a的節(jié)點(diǎn)進(jìn)行剪枝，并通過多數(shù)表決的方法決定葉子節(jié)點(diǎn)t的類。4?令k++,Tk=T,ak=a,(Tk為％-ak+］的最優(yōu)子樹)5?如果,q不是一根節(jié)點(diǎn)和兩個葉子結(jié)點(diǎn)組成的樹，則回到2.6?采用交叉驗(yàn)證法在子樹序列中選取最優(yōu)子樹T?a說明：實(shí)際上2,3的過程是根據(jù)g(t)從小到大的順序依次剪去非葉子節(jié)點(diǎn)，并是此時的玉=g(t)。此方法巧妙的地方在于：如果我們要不斷增大a,這是一個連續(xù)過程，并不能夠進(jìn)行下去。而此方法通過剪枝的過程模擬a的不斷增大。1.6幾種剪枝方法比較REPPEPCCP剪枝方式自底向上自頂向下自底向上訐算農(nóng)雜魔0(nJo(n)o(n^)誤差估計(jì)剪■枝案上誤差使用連鑽糾正標(biāo)準(zhǔn)誤;差1.7優(yōu)缺點(diǎn)比較ID3:算法一般會優(yōu)先選擇有較多屬性值的特征（信息增益反映的給定一個條件以后不確定性減少的程度,必然是分得越細(xì)的數(shù)據(jù)集確定性更高,也就是條件熵越小,信息增益越大），因?yàn)閷傩灾刀嗟奶卣鲿邢鄬^大的信息增益.ID3只能對離散屬性的數(shù)據(jù)集構(gòu)造決策樹。C4.5采用信息增益率的方式去選擇變量，避免了ID3優(yōu)先選擇有較多屬性