第四章? 決策樹
4.1 決策樹基本概念
顧名思義术唬，決策樹是基于樹結(jié)構(gòu)來進行決策的送讲。
決策樹中奸笤，決策過程的每一次判定都是對某一屬性的“測試”惋啃，決策最終結(jié)論則對應(yīng)最終的判定結(jié)果。一般一顆決策樹包含：一個根節(jié)點监右、若干個內(nèi)部節(jié)點和若干個葉子節(jié)點边灭，易知：
* 每個非葉節(jié)點表示一個特征屬性測試。?
* 每個分支代表這個特征屬性在某個值域上的輸出健盒。?
* 每個葉子節(jié)點存放一個類別绒瘦。?
* 每個節(jié)點包含的樣本集合通過屬性測試被劃分到子節(jié)點中，根節(jié)點包含樣本全集扣癣。
決策樹的基本流程體現(xiàn)了簡單且直觀的“分而治之”（divide-and-conquer）策略惰帽。
4.2 決策樹的構(gòu)造
決策樹的構(gòu)造是一個遞歸的過程，有三種情形會導(dǎo)致遞歸返回：(1) 當(dāng)前結(jié)點包含的樣本全屬于同一類別父虑，這時直接將該節(jié)點標(biāo)記為葉節(jié)點该酗，并設(shè)為相應(yīng)的類別；(2) 當(dāng)前屬性集為空士嚎，或是所有樣本在所有屬性上取值相同呜魄，無法劃分，這時將該節(jié)點標(biāo)記為葉節(jié)點莱衩，并將其類別設(shè)為該節(jié)點所含樣本最多的類別爵嗅；(3) 當(dāng)前結(jié)點包含的樣本集合為空，不能劃分笨蚁，這時也將該節(jié)點標(biāo)記為葉節(jié)點睹晒，并將其類別設(shè)為父節(jié)點中所含樣本最多的類別。算法的基本流程如下圖所示：
可以看出：決策樹學(xué)習(xí)的關(guān)鍵在于如何選擇劃分屬性括细，不同的劃分屬性得出不同的分支結(jié)構(gòu)伪很，從而影響整棵決策樹的性能。屬性劃分的目標(biāo)是讓各個劃分出來的子節(jié)點盡可能地“純”奋单，即屬于同一類別是掰。因此下面便是介紹量化純度的具體方法，決策樹最常用的算法有三種：ID3辱匿，C4.5和CART键痛。
4.2.1 ID3算法
ID3算法使用信息增益為準(zhǔn)則來選擇劃分屬性，“信息熵”(information entropy)是度量樣本結(jié)合純度的常用指標(biāo)匾七，假定當(dāng)前樣本集合D中第k類樣本所占比例為pk絮短，則樣本集合D的信息熵定義為：
假定通過屬性劃分樣本集D，產(chǎn)生了V個分支節(jié)點昨忆，v表示其中第v個分支節(jié)點丁频，易知：分支節(jié)點包含的樣本數(shù)越多，表示該分支節(jié)點的影響力越大。故可以計算出劃分后相比原始數(shù)據(jù)集D獲得的“信息增益”（information gain）席里。
信息增益越大叔磷，表示使用該屬性劃分樣本集D的效果越好，因此ID3算法在遞歸過程中奖磁，每次選擇最大信息增益的屬性作為當(dāng)前的劃分屬性改基。
4.2.2? C4.5算法
ID3算法存在一個問題，就是偏向于取值數(shù)目較多的屬性咖为，例如：如果存在一個唯一標(biāo)識秕狰，這樣樣本集D將會被劃分為|D|個分支，每個分支只有一個樣本躁染，這樣劃分后的信息熵為零鸣哀，十分純凈，但是對分類毫無用處吞彤。因此C4.5算法使用了“增益率”（gain ratio）來選擇劃分屬性我衬，來避免這個問題帶來的困擾。首先使用ID3算法計算出信息增益高于平均水平的候選屬性饰恕，接著C4.5算法計算這些候選屬性的增益率低飒，增益率定義為：
4.2.3 CART算法
CART決策樹使用“基尼指數(shù)”（Gini index）來選擇劃分屬性，基尼指數(shù)反映的是從樣本集D中隨機抽取兩個樣本懂盐，其類別標(biāo)記不一致的概率，因此Gini(D)越小越好糕档，基尼指數(shù)定義如下：
進而莉恼，使用屬性α劃分后的基尼指數(shù)為：
4.3 剪枝處理
從決策樹的構(gòu)造流程中我們可以直觀地看出：不管怎么樣的訓(xùn)練集，決策樹總是能很好地將各個類別分離開來速那，這時就會遇到之前提到過的問題：過擬合（overfitting）俐银，即太依賴于訓(xùn)練樣本。剪枝（pruning）則是決策樹算法對付過擬合的主要手段端仰，剪枝的策略有兩種如下：
* 預(yù)剪枝（prepruning）：在構(gòu)造的過程中先評估捶惜，再考慮是否分支。?
* 后剪枝（post-pruning）：在構(gòu)造好一顆完整的決策樹后荔烧，自底向上吱七，評估分支的必要性。?
評估指的是性能度量鹤竭，即決策樹的泛化性能踊餐。之前提到：可以使用測試集作為學(xué)習(xí)器泛化性能的近似，因此可以將數(shù)據(jù)集劃分為訓(xùn)練集和測試集臀稚。預(yù)剪枝表示在構(gòu)造樹的過程中吝岭，對一個節(jié)點考慮是否分支時，首先計算決策樹不分支時在測試集上的性能，再計算分支之后的性能窜管，若分支對性能沒有提升散劫，則選擇不分支（即剪枝）。后剪枝則表示在構(gòu)造好一顆完整的決策樹后幕帆，從最下面的節(jié)點開始获搏，考慮該節(jié)點分支對模型的性能是否有提升，若無則剪枝蜓肆，即將該節(jié)點標(biāo)記為葉子節(jié)點颜凯，類別標(biāo)記為其包含樣本最多的類別。
上圖分別表示不剪枝處理的決策樹仗扬、預(yù)剪枝決策樹和后剪枝決策樹症概。預(yù)剪枝處理使得決策樹的很多分支被剪掉，因此大大降低了訓(xùn)練時間開銷早芭，同時降低了過擬合的風(fēng)險彼城，但另一方面由于剪枝同時剪掉了當(dāng)前節(jié)點后續(xù)子節(jié)點的分支，因此預(yù)剪枝“貪心”的本質(zhì)阻止了分支的展開退个，在一定程度上帶來了欠擬合的風(fēng)險募壕。而后剪枝則通常保留了更多的分支，因此采用后剪枝策略的決策樹性能往往優(yōu)于預(yù)剪枝语盈，但其自底向上遍歷了所有節(jié)點舱馅，并計算性能，訓(xùn)練時間開銷相比預(yù)剪枝大大提升刀荒。
預(yù)剪枝VS后剪枝 總結(jié)如下：
（1）時間開銷
預(yù)剪枝：測試時間開銷降低代嗤，訓(xùn)練時間開銷降低
后剪枝：測試時間開銷降低，訓(xùn)練時間開銷增加
（2）過/欠擬合風(fēng)險：
預(yù)剪枝：過擬合風(fēng)險降低缠借，欠擬合風(fēng)險增加
后剪枝：過擬合風(fēng)險降低，欠擬合風(fēng)險基本不變
（3）泛化性能：后剪枝通常優(yōu)于預(yù)剪枝
4.4 連續(xù)值與缺失值處理
對于連續(xù)值的屬性硝逢，若每個取值作為一個分支則顯得不可行柴罐，因此需要進行離散化處理猎拨，常用的方法為二分法，基本思想為：給定樣本集D與連續(xù)屬性α虾啦，二分法試圖找到一個劃分點t將樣本集D在屬性α上分為≤t與＞t呻率。
* 首先將α的所有取值按升序排列，所有相鄰屬性的均值作為候選劃分點（n-1個，n為α所有的取值數(shù)目）。?
* 計算每一個劃分點劃分集合D（即劃分為兩個分支）后的信息增益。?
* 選擇最大信息增益的劃分點作為最優(yōu)劃分點粒氧。?
現(xiàn)實中常會遇到不完整的樣本饱苟，即某些屬性值缺失城须。有時若簡單采取剔除，則會造成大量的信息浪費，因此在屬性值缺失的情況下需要解決兩個問題：（1）如何選擇劃分屬性。（2）給定劃分屬性你辣，若某樣本在該屬性上缺失值，如何劃分到具體的分支上尘执。假定為樣本集中的每一個樣本都賦予一個權(quán)重舍哄，根節(jié)點中的權(quán)重初始化為1，則定義：
對于（1）：通過在樣本集D中選取在屬性α上沒有缺失值的樣本子集誊锭，計算在該樣本子集上的信息增益表悬，最終的信息增益等于該樣本子集劃分后信息增益乘以樣本子集占樣本集的比重。即：
對于（2）：若該樣本子集在屬性α上的值缺失丧靡，則將該樣本以不同的權(quán)重（即每個分支所含樣本比例）劃入到所有分支節(jié)點中蟆沫。該樣本在分支節(jié)點中的權(quán)重變?yōu)椋?/p>
4.5 多變量決策樹
單變量決策樹
（在每個非葉結(jié)點）每次只針對一個屬性進行劃分，其他屬性保持不變温治，會出現(xiàn)“軸平行”平面饭庞，每個空間的劃分區(qū)域都對應(yīng)著一個葉節(jié)點（分類）。
多變量決策樹
當(dāng)學(xué)習(xí)任務(wù)多對應(yīng)的分類邊界很復(fù)雜時熬荆，需要非常多段劃分能得到較好的近似舟山，于是想用非軸平行的直線進行劃分。多變量決策樹：每個非葉結(jié)點不僅考慮一個屬性卤恳，考慮多個屬性的組合累盗。如“斜決策樹”（oblique decision tree）不是為每一個非葉結(jié)點尋找最優(yōu)劃分屬性，而是建立一個線性分類器突琳，可以同時看多個變量若债。
混合決策樹
多變量決策樹相當(dāng)于是對單變量決策樹的拓展，每次劃分可以看多個屬性拆融，多個屬性可以進行線性組合蠢琳，也可以進行更復(fù)雜的模型啊终，甚至神經(jīng)網(wǎng)絡(luò)或其他非線性模型。
