學(xué)習(xí)打卡內(nèi)容：
閱讀《李航統(tǒng)計學(xué)習(xí)方法》的65-74頁
學(xué)習(xí)Gini指數(shù)
學(xué)習(xí)回歸樹
剪枝
根據(jù)自己閱讀仑濒，先寫出自己所認(rèn)為的筆記捆愁。
前面學(xué)習(xí)了決策樹的建立方法。
這樣產(chǎn)生的樹往往對訓(xùn)練數(shù)據(jù)的分類很準(zhǔn)確氓奈， 但對未知的測試數(shù)據(jù)的分類卻沒有那么準(zhǔn)確瞬欧， 即出現(xiàn)過擬合現(xiàn)象。過擬合的原因在于學(xué)習(xí)時過多地考慮如何提高對訓(xùn)練數(shù)據(jù)的正確分類晦鞋， 從而構(gòu)建出過于復(fù)雜的決策樹蹲缠。 解決這個問題的辦法是考慮決策樹的復(fù)雜度棺克， 對已生成的決策樹進行簡化。
如何簡化线定？
剪枝
從已生成的樹上裁掉一些子樹或葉結(jié)點娜谊， 并將其根結(jié)點或父結(jié)點作為新的葉結(jié)點， 從而簡化分類樹模型斤讥。
決策樹的剪枝往往通過極小化決策樹整體的損失函數(shù)（loss function） 或代價函數(shù)（cost function） 來實現(xiàn)纱皆。
C(T)表示模型對訓(xùn)練數(shù)據(jù)的預(yù)測誤差， 即模型與訓(xùn)練數(shù)據(jù)的擬合程度芭商， |T|表示模型復(fù)雜度派草， 參數(shù)a≥0控制兩者之間的影響。 較大的a促使選擇較簡單的模型（樹） 铛楣，較小的a促使選擇較復(fù)雜的模型（樹） 近迁。 a＝0意味著只考慮模型與訓(xùn)練數(shù)據(jù)的擬合程度，不考慮模型的復(fù)雜度簸州。
決策樹生成只考慮了通過提高信息增益（或信息增益比） 對訓(xùn)練數(shù)據(jù)進行更好的擬合鉴竭。 而決策樹剪枝通過優(yōu)化損失函數(shù)還考慮了減小模型復(fù)雜度。 決策樹生成學(xué)習(xí)局部的模型岸浑， 而決策樹剪枝學(xué)習(xí)整體的模型搏存。
算法5.4（樹的剪枝算法）
輸入： 生成算法產(chǎn)生的整個樹T， 參數(shù)a矢洲；
輸出： 修剪后的子樹Ta璧眠。
（1） 計算每個結(jié)點的經(jīng)驗熵。
（2） 遞歸地從樹的葉結(jié)點向上回縮读虏。設(shè)一組葉結(jié)點回縮到其父結(jié)點之前與之后的整體樹分別為TB與TA蛆橡， 其對應(yīng)的損失函數(shù)值分別是Ca(TB)與Ca(TA)， 如果則進行剪枝掘譬， 即將父結(jié)點變?yōu)樾碌娜~結(jié)點。
（3） 返回（2） 呻拌， 直至不能繼續(xù)為止葱轩， 得到損失函數(shù)最小的子樹Ta。
CART算法
分類與回歸樹（classification and regression tree藐握， CART）
CART是在給定輸入隨機變量X條件下輸出隨機變量Y的條件概率分布的學(xué)習(xí)方法靴拱。CART假設(shè)決策樹是二叉樹， 內(nèi)部結(jié)點特征的取值為“是”和“否”猾普， 左分支是取值為“是”的分支袜炕， 右分支是取值為“否”的分支。 這樣的決策樹等價于遞歸地二分每個特征初家， 將輸入空間即特征空間劃分為有限個單元偎窘， 并在這些單元上確定預(yù)測的概率分布乌助， 也就是在輸入給定的條件下輸出的條件概率分布。
CART算法由以下兩步組成：
（1） 決策樹生成： 基于訓(xùn)練數(shù)據(jù)集生成決策樹陌知， 生成的決策樹要盡量大他托；
（2） 決策樹剪枝： 用驗證數(shù)據(jù)集對已生成的樹進行剪枝并選擇最優(yōu)子樹， 這時用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)仆葡。
決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程赏参。 對回歸樹用平方誤差最小化準(zhǔn)則，對分類樹用基尼指數(shù)（Gini index） 最小化準(zhǔn)則沿盅， 進行特征選擇把篓， 生成二叉樹。
基尼指數(shù)（Gini index）?
分類問題中腰涧， 假設(shè)有K個類韧掩， 樣本點屬于第k類的概率為pk，則概率分布的基尼指數(shù)定義為：
基尼指數(shù)Gini(D)表示集合D的不確定性南窗， 基尼指數(shù)Gini(D,A)表示經(jīng)A＝a分割后集合D的不確定性揍很。 基尼指數(shù)值越大， 樣本集合的不確定性也就越大万伤， 這一點與熵相似窒悔。
CART剪枝算法從“完全生長”的決策樹的底端剪去一些子樹， 使決策樹變械新颉（模型變簡單） 简珠， 從而能夠?qū)ξ粗獢?shù)據(jù)有更準(zhǔn)確的預(yù)測。CART剪枝算法由兩步組成： 首先從生成算法產(chǎn)生的決策樹
T0底端開始不斷剪枝虹钮， 直到T0的根結(jié)點聋庵， 形成一個子樹序列{T0， T1,…,Tn}芙粱； 然后通過交叉驗證法在獨立的驗證數(shù)據(jù)集上對子樹序列進行測試祭玉， 從中選擇最優(yōu)子樹。
1． 剪枝春畔， 形成一個子樹序列
對固定的a脱货， 一定存在使損失函數(shù)Ca(T)最小的子樹， 將其表示為Ta律姨。 Ta在損失函數(shù)Ca(T)最小的意義下是最優(yōu)的振峻。 容易驗證這樣的最優(yōu)子樹是唯一的。 當(dāng)a大的時候择份， 最優(yōu)子樹Ta偏锌勖稀； 當(dāng)a小的時候荣赶， 最優(yōu)子樹Ta偏大凤价。 極端情況鸽斟， 當(dāng)a＝0時， 整體樹是最優(yōu)的料仗。 當(dāng)a→ 時湾盗， 根結(jié)點組成的單結(jié)點樹是最優(yōu)的。
它表示剪枝后整體損失函數(shù)減少的程度立轧。 在T0中剪去g(t)最小的Tt格粪， 將得到的子樹作為T1， 同時將最小的g(t)設(shè)為a1氛改。 T1為區(qū)間[a1,a2)的最優(yōu)子樹帐萎。如此剪枝下去， 直至得到根結(jié)點胜卤。 在這一過程中疆导， 不斷地增加a的值， 產(chǎn)生新的區(qū)間葛躏。
2． 在剪枝得到的子樹序列T0,T1,…,Tn中通過交叉驗證選取最優(yōu)子樹Ta
利用獨立的驗證數(shù)據(jù)集澈段， 測試子樹序列T0,T1,…,Tn中各棵子樹的平方誤差或基尼指數(shù)。 平方誤差或基尼指數(shù)最小的決策樹被認(rèn)為是最優(yōu)的決策樹舰攒。 在子樹序列中败富， 每棵子樹T1,T2,…,Tn都對應(yīng)于一個參數(shù)a1,a2,…,an。 所以摩窃， 當(dāng)最優(yōu)子樹Tk確定時兽叮， 對應(yīng)的ak也確定了， 即得到最優(yōu)決策樹Ta猾愿。
