本篇部落客要講解決策樹是如何分類的。
概念
決策樹也稱判定樹，基于樹結構進行決策，決策樹是一個預測模型，代表的是對象屬性與對象值之間的一種映射關系。
一般的，一棵決策樹包含一個根節點、若幹個内部節點和若幹個葉節點。葉節點對應于決策結果，其他每個節點對應于一個屬性測試；每個節點包含的樣本根據屬性測試的結果被劃分到子節點中；根節點包含樣本全集。
決策樹學習目的：為了産生一個泛化能力強，即處理未見示例能力強的決策樹。
一樣通過一個簡單的例子先來了解一下什麼是決策樹
女兒：多大年紀了？
母親：26。
女兒：長的帥不帥？
母親：挺帥的。
女兒：收入高不？
母親：不算很高，中等情況。
女兒：是公務員不？
母親：是，在稅務局上班呢。
女兒：那好，我去見見。
那我們可以用一個決策樹去表達母親和女兒的對話：
那下面我們就可以先引入決策樹的算法流程了：
算法流程
輸入: 訓練集D={(x1,y1),(x2,y2),……,(xm,ym)} ;
屬性集A= {a1,a2,……ad}.
過程: 函數TreeGenerate(D,A)
l: 生成結點node;
2: if D 中樣本全屬于同一類别 C then
3: 将node 标記為C類葉結點; return
4: end if
5: if A= Ø OR D 中樣本在A 上取值相同then
6: 将node 标記為葉結點，其類别标記為D中樣本數最多的類; return
7:end if
8: 從A 中選擇最優劃分屬性;
9: for 的每一個值 do
10: 為node 生成一個分支; 令 表示D中在 上取值為 的樣本子集;
11: if 為空then
12: 将分支結點标記為葉結點，其類别标記為D 中樣本最多的類; return
13: else
14: 以TreeGenerate( ,A{ })為分支結點
15: end if
16: end for
輸出: 以node 為根結點的一棵決策樹
分析一下算法中三個傳回情況
(1)目前結點包含的樣本全部屬于同一類别，無需劃分。
(2)目前屬性集為空，或者是所有樣本在所有屬性上的取值相同，無法劃分。(目前結點标為葉子結點，其類别也是該節點所含樣本最多的類别)
(3)目前結點包含的樣本集合為空，不能劃分。(目前結點标為葉子結點，其類别為父結點所含樣本最多的類别)
(2)和(3)是不一樣的，(2)是在利用目前結點的後驗分布，(3)是把父結點的樣本分布作為目前結點的先驗分布。
算法的核心思想在于劃分選擇，下面對劃分選擇進行介紹
劃分準則：随着劃分過程的不斷進行，我們希望決策樹的分支結點所包含的樣本盡可能屬于同一類别，即結點的“純度”(purity)越來越高。
方法：資訊增益（ID3）
優化方法：增益率（C4.5）
相關概念
“資訊熵”information entropy：是度量樣本集合純度最常用的一種名額，假定目前樣本集合D中第k類樣本所占比例為pk（k=1,2,…,|y|）,則D的資訊熵定義為：
End(D)的值越小，則D的純度越高。
資訊增益”information gain:用離散屬性a有V個可能取值{a1,a2,…,aV}對樣本集D進行劃分,其中第v個分支結點包含了D在屬性a上取值為av的樣本，記為
。所獲得的“資訊增益”：
一般而言，資訊增益越大，使用屬性a來進行劃分所獲得的“純度提升”越大。ID3決策樹學習算法就是以資訊增益為準則來選擇劃分屬性。
接下來用西瓜資料集來詳細解釋這些概念
以屬性“色澤”為例：有3個可能取值{青綠、烏黑、淺白}，用該屬性對D進行劃分，可以得到3個子集D1(色澤=青綠),D2(色澤=烏黑)，D3(色澤=淺白)。
D1包含編号{1,4,6,10,13,17}六個樣例，正例占p1=3/6，反例占p2=3/6；
D2包含編号{2,3,7,8,9,15}六個樣例，正例占p1=4/6，反例占p2=2/6；
D3包含編号{5,11,12,14,16}五個樣例，正例占p1=1/5，反例占p2=4/5；
三個分支的資訊熵分别為：
Ent(D1)=-(3/6log23/6+3/6log23/6)=1.000
Ent(D2)=-(4/6log24/6+2/6log22/6)=0.918
Ent(D3)=-(1/5log21/5+4/5log24/5)=0.772
屬性“色澤”的資訊增益為：
其他屬性資訊屬性增益為：
Gain(D,根蒂)=0.143; Gain(D,敲聲)=0.141;
Gain(D,紋理)=0.381; Gain(D,臍部)=0.289;
Gain(D,觸感)=0.006;
屬性“紋理”的資訊增益最大，于是被選為劃分屬性。劃分結果如下：
決策樹學習算法将對每個分支結點做進一步劃分
當然ID3算法是有問題的：
如果使得每個樣例的編号作為屬性，每個分支有一個樣本，這些分支結點的純度已達到最大，但是這樣的決策樹不具有泛化能力，無法對新樣本進行有效預測，資訊增益準則對可取值數目較多的屬性有所偏好。
著名的C4.5決策樹算法使用“增益率”gain ratio來選擇最優劃分屬性。下面來簡單介紹C4.5算法
相關概念
“增益率”gain ratio：
其中
稱為屬性a的“固有值”。屬性a的可能取值越多（V越大），IV(a)的值通常越大，IV(觸感)=0.874(v=2);IV(色澤)=1.580(v=3)；IV(編号)=4.008(v=17)。
增益率準則對可取值數目較少的屬性有所偏好，是以，C4.5算法并不是直接選取增益率最大的候選劃分屬性，而是使用了一個啟發式：先從候選劃分屬性中找出資訊增益高于平均水準的屬性，再從中選擇增益率最高的。
接下來對我們的這棵樹進行剪枝處理
“剪枝”是決策樹學習算法對付“過拟合”的主要手段。
在決策樹學習中，為了盡可能正确分類訓練樣本，結點劃分過程将不斷重複，造成決策樹分支過多，這時就可能因訓練樣本學的“太好”了，以緻于把訓練集自身的一些特點當做所有資料都具有的一般性質而導緻的過拟合。
決策樹剪枝的基本政策有“預剪枝”和“後剪枝”
同樣，對喜瓜資料集進行讨論，紅色的作為驗證集，黑色作為測試集：
未剪枝決策樹
該決策樹的驗證集精度為：42.9%
預剪枝：
預剪枝是指在決策樹生成過程中，對每個結點在劃分前先進行估計，若目前結點的劃分不能帶來決策樹泛化性能提升，則停止劃分并将目前結點标記為葉結點。
假設在臍部不劃分：直接把其标記成葉節點，那麼{4,5,8}是劃分對的，驗證集精度：3/7
劃分後：将凹陷、稍凹記為好瓜，平坦記為壞瓜{4,5,8,11,12}劃分正确，驗證集精度：5/7
故，劃分得以确定，預剪枝決策：劃分
然後，決策樹算法對結點2進行劃分，基于資訊增益準則，挑選“色澤”屬性。劃分後發現{5}由正确轉換為錯誤，驗證集精度下降為57.1%。
故，預剪枝決策：禁止被劃分。
後剪枝：
後剪枝則是先從訓練集生成一顆完整的決策樹，然後自底向上地對非葉結點進行考察，若将該結點對應的子樹替換為葉結點能帶來決策樹泛化性能的提升，則将該子樹替換為葉結點。
先考察結點6，若把結點6當做葉節點，葉節點類别标為“好瓜”，替換後葉節點包含{7，,1}，此時決策樹的驗證精度提升至57.1%，故，後剪枝決策決定：剪枝。
再考察結點5，，将其作為葉子結點，替換後葉節點包含編号{6,7,15}，葉節點類别标記為“好瓜”，此時決策樹驗證集精度仍未：57.1%，故，後剪枝決策決定：不剪枝。
兩種剪枝的優缺點：
優點：
後剪枝決策樹通常比預剪枝決策樹保留了更多分支。一般情況下，後剪枝決策樹的欠拟合風險很小，泛化性能往往優于與剪枝決策樹。
缺點：
但是後剪枝序是在生成完全決策樹之後進行的，并且要自底向上地對樹中所有非葉結點進行逐一考察，是以訓練時間開銷比未剪枝決策樹和預剪枝決策樹都要大得多。
python代碼實作可參考
https://www.cnblogs.com/MrLJC/p/4099404.html
決策樹内容就先告一段落了，謝謝浏覽。