這次打卡學(xué)習(xí)的是西瓜書的第四章決策樹。
1. 決策樹基本概念
顧名思義，決策樹是基于樹結(jié)構(gòu)來進(jìn)行決策的郊愧，它也是一種常見的機(jī)器學(xué)習(xí)分類算法。
如上圖所示（來源西瓜書）井佑，決策過程的每一次判定都是對(duì)某一屬性的“測(cè)試”属铁，決策最終結(jié)論則對(duì)應(yīng)最終的判定結(jié)果。一般一顆決策樹包含：一個(gè)根節(jié)點(diǎn)躬翁、若干個(gè)內(nèi)部節(jié)點(diǎn)和若干個(gè)葉子節(jié)點(diǎn)焦蘑，易知：
* 每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性測(cè)試。
* 每個(gè)分支代表這個(gè)特征屬性在某個(gè)值域上的輸出盒发。
* 每個(gè)葉子節(jié)點(diǎn)存放一個(gè)類別例嘱。
* 每個(gè)節(jié)點(diǎn)包含的樣本集合通過屬性測(cè)試被劃分到子節(jié)點(diǎn)中，根節(jié)點(diǎn)包含樣本全集宁舰。
2. 決策樹基本算法流程
決策樹的構(gòu)造是一個(gè)遞歸的過程拼卵，有三種情形會(huì)導(dǎo)致遞歸返回：(1) 當(dāng)前結(jié)點(diǎn)包含的樣本全屬于同一類別，這時(shí)直接將該節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)蛮艰，并設(shè)為相應(yīng)的類別腋腮；(2) 當(dāng)前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分即寡，這時(shí)將該節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)徊哑，并將其類別設(shè)為該節(jié)點(diǎn)所含樣本最多的類別；(3) 當(dāng)前結(jié)點(diǎn)包含的樣本集合為空聪富，不能劃分实柠，這時(shí)也將該節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)，并將其類別設(shè)為父節(jié)點(diǎn)中所含樣本最多的類別善涨。
可以看出：決策樹學(xué)習(xí)的關(guān)鍵在于如何選擇劃分屬性窒盐，不同的劃分屬性得出不同的分支結(jié)構(gòu)，從而影響整顆決策樹的性能钢拧。屬性劃分的目標(biāo)是讓各個(gè)劃分出來的子節(jié)點(diǎn)盡可能地“純”蟹漓，即屬于同一類別。因此下面便是介紹量化純度的具體方法源内，決策樹最常用的算法有三種：ID3葡粒，C4.5和CART。
3. 常見算法
3.1 ID3算法
ID3算法使用信息增益為準(zhǔn)則來選擇劃分屬性膜钓，“信息熵”(information entropy)是度量樣本結(jié)合純度的常用指標(biāo)嗽交，假定當(dāng)前樣本集合D中第k類樣本所占比例為pk，則樣本集合D的信息熵定義為：
假定通過屬性劃分樣本集D颂斜，產(chǎn)生了V個(gè)分支節(jié)點(diǎn)夫壁，v表示其中第v個(gè)分支節(jié)點(diǎn)，易知：分支節(jié)點(diǎn)包含的樣本數(shù)越多沃疮，表示該分支節(jié)點(diǎn)的影響力越大盒让。故可以計(jì)算出劃分后相比原始數(shù)據(jù)集D獲得的“信息增益”（information gain）
信息增益越大，表示使用該屬性劃分樣本集D的效果越好司蔬，因此ID3算法在遞歸過程中邑茄，每次選擇最大信息增益的屬性作為當(dāng)前的劃分屬性。
3.2 C4.5算法
ID3算法存在一個(gè)問題俊啼，就是偏向于取值數(shù)目較多的屬性肺缕，例如：如果存在一個(gè)唯一標(biāo)識(shí)，這樣樣本集D將會(huì)被劃分為|D|個(gè)分支授帕，每個(gè)分支只有一個(gè)樣本同木，這樣劃分后的信息熵為零，十分純凈豪墅，但是對(duì)分類毫無用處泉手。因此C4.5算法使用了“增益率”（gain ratio）來選擇劃分屬性，來避免這個(gè)問題帶來的困擾偶器。首先使用ID3算法計(jì)算出信息增益高于平均水平的候選屬性，接著C4.5計(jì)算這些候選屬性的增益率，增益率定義為：
3.3 CART算法
CART決策樹使用“基尼指數(shù)”（Gini index）來選擇劃分屬性屏轰，基尼指數(shù)反映的是從樣本集D中隨機(jī)抽取兩個(gè)樣本颊郎，其類別標(biāo)記不一致的概率，因此Gini(D)越小越好霎苗，基尼指數(shù)定義如下：
進(jìn)而姆吭，使用屬性α劃分后的基尼指數(shù)為：
4 剪枝處理
從決策樹的構(gòu)造流程中我們可以直觀地看出：不管怎么樣的訓(xùn)練集，決策樹總是能很好地將各個(gè)類別分離開來唁盏，這時(shí)就會(huì)遇到之前提到過的問題：過擬合（overfitting）内狸，即太依賴于訓(xùn)練樣本。剪枝（pruning）則是決策樹算法對(duì)付過擬合的主要手段厘擂，剪枝的策略有兩種如下：
* 預(yù)剪枝（prepruning）：在構(gòu)造的過程中先評(píng)估昆淡，再考慮是否分支。
* 后剪枝（post-pruning）：在構(gòu)造好一顆完整的決策樹后刽严，自底向上昂灵，評(píng)估分支的必要性。
評(píng)估指的是性能度量舞萄，即決策樹的泛化性能眨补。之前提到：可以使用測(cè)試集作為學(xué)習(xí)器泛化性能的近似，因此可以將數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集倒脓。預(yù)剪枝表示在構(gòu)造數(shù)的過程中撑螺，對(duì)一個(gè)節(jié)點(diǎn)考慮是否分支時(shí)，首先計(jì)算決策樹不分支時(shí)在測(cè)試集上的性能崎弃，再計(jì)算分支之后的性能实蓬，若分支對(duì)性能沒有提升，則選擇不分支（即剪枝）吊履。后剪枝則表示在構(gòu)造好一顆完整的決策樹后安皱，從最下面的節(jié)點(diǎn)開始，考慮該節(jié)點(diǎn)分支對(duì)模型的性能是否有提升艇炎，若無則剪枝酌伊，即將該節(jié)點(diǎn)標(biāo)記為葉子節(jié)點(diǎn)，類別標(biāo)記為其包含樣本最多的類別缀踪。
