決策樹是一個預測模型；他代表的是對象屬性與對象值之間的一種映射關系。樹中每個節點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結點則對應從根節點到該葉節點所經曆的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有複數輸出，可以建立獨立的決策樹以處理不同輸出。資料挖掘中決策樹是一種經常要用到的技術，可以用于分析資料，同樣也可以用來作預測。 從資料産生決策樹的機器學習技術叫做決策樹學習, 通俗說就是決策樹。
例如，我們要對”是否要出去玩？“這樣的問題進行決策的時候，通常會進行一系列的判斷或者”子決策“：我們先看”OUTLOOK“，如果是天氣是sunny，則我們再看空氣濕度，如果是”humidity<70“（濕度小于70），那麼就去玩，否則就不去玩；如果天氣是overcast，那麼就去玩，其他的節點可以不用判斷；以此類推：
一般地，一顆決策樹包含一個根節點，若幹個 内部節點；葉節點對應與決策結果，其他每個節點對應于一個屬性測試；每個節點包含的樣本集合根據屬性測試的結果被劃分到子節點中；根節點包含樣本全集。從根節點到每個葉節點的路徑對應了一個判定測試序列。決策樹學習的目的是為了産生一棵泛化能力強，即處理未見示例能力強的決策樹，其基本流程遵循簡單且直覺的”分而治之“的政策，如下所示：
在建立決策樹之前，我們必須先要學習一個非常重要的概念，那就是資訊熵。
1948年，香農提出了 ”資訊熵(entropy)“的概念。 一條資訊的資訊量大小和它的不确定性有直接的關系，要搞清楚一件非常非常不确定的事情，或者是我們一無所知的事情，需要了解大量資訊==>資訊量的度量就等于不确定性的多少。
資訊熵是度量樣本集合純度最常用的一種名額。假定目前樣本集合D中第K類樣本所占的比例為[Math Processing Error]，則D的資訊熵的定義為：
變量的不确定性越大，資訊熵也就越大。
決策樹歸納算法 （ID3）
資訊擷取量(Information Gain)：Gain(A) = Info(D) - Infor_A(D)，其中 Info(D)代表沒有加入A節點的所擷取的資訊量，Infor_A(D)代表加入A節點後所擷取的資訊量。
一般而言，資訊擷取量越大，則意味着使用屬性A來進行劃分所獲得的”純度提升“越大。是以，我們可以用資訊擷取量來進行決策樹的劃分屬性的選擇，著名的ID3決策樹學習算法就是以資訊擷取量為準則來選擇劃分屬性的。
以上圖中為例，
由上可得Gain(age) = Info(D) - Infor_A(D)=0.940-0.694=0.246。
類似，Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating)=0.048；
因為Gain(age)> Gain(student)>Gain(credit_rating)>Gain(income),是以，選擇age作為第一個根節點。
重複以上步驟即可得出結論。
示例Python代碼如下：
其他算法：
1、C4.5: Quinlan
2、Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)
共同點：都是貪心算法，自上而下(Top-down approach)
差別：屬性選擇度量方法不同： C4.5 （gain ratio), CART(gini index), ID3 (Information Gain)
劃分資料集的最大原則是：使無序的資料變的有序。如果一個訓練資料中有20個特征，那麼選取哪個做劃分依據？這就必須采用量化的方法來判斷，量化劃分方法有多重，其中一項就是“資訊論度量資訊分類”。基于資訊論的決策樹算法有ID3、CART和C4.5等算法，其中C4.5和CART兩種算法從ID3算法中衍生而來。
CART和C4.5支援資料特征為連續分布時的處理，主要通過使用二進制切分來處理連續型變量，即求一個特定的值-分裂值：特征值大于分裂值就走左子樹，或者就走右子樹。這個分裂值的選取的原則是使得劃分後的子樹中的“混亂程度”降低，具體到C4.5和CART算法則有不同的定義方式。
ID3算法由Ross Quinlan發明，建立在“奧卡姆剃刀”的基礎上：越是小型的決策樹越優于大的決策樹（be simple簡單理論）。ID3算法中根據資訊論的資訊增益評估和選擇特征，每次選擇資訊增益最大的特征做判斷子產品。ID3算法可用于劃分标稱型資料集，沒有剪枝的過程，為了去除過度資料比對的問題，可通過裁剪合并相鄰的無法産生大量資訊增益的葉子節點（例如設定資訊增益閥值）。使用資訊增益的話其實是有一個缺點，那就是它偏向于具有大量值的屬性–就是說在訓練集中，某個屬性所取的不同值的個數越多，那麼越有可能拿它來作為分裂屬性，而這樣做有時候是沒有意義的，另外ID3不能處理連續分布的資料特征，于是就有了C4.5算法。CART算法也支援連續分布的資料特征。
C4.5是ID3的一個改進算法，繼承了ID3算法的優點。C4.5算法用資訊增益率來選擇屬性，克服了用資訊增益選擇屬性時偏向選擇取值多的屬性的不足在樹構造過程中進行剪枝；能夠完成對連續屬性的離散化處理；能夠對不完整資料進行處理。C4.5算法産生的分類規則易于了解、準确率較高；但效率低，因樹構造過程中，需要對資料集進行多次的順序掃描和排序。也是因為必須多次資料集掃描，C4.5隻适合于能夠駐留于記憶體的資料集。
CART算法的全稱是Classification And Regression Tree，采用的是Gini指數（選Gini指數最小的特征s）作為分裂标準,同時它也是包含後剪枝操作。ID3算法和C4.5算法雖然在對訓練樣本集的學習中可以盡可能多地挖掘資訊，但其生成的決策樹分支較大，規模較大。為了簡化決策樹的規模，提高生成決策樹的效率，就出現了根據GINI系數來選擇測試屬性的決策樹算法CART。
關于剪枝(避免過拟合（overfitting))
在實際構造決策樹時，通常要進行剪枝，這時為了處理由于資料中的噪聲和離群點導緻的過分拟合問題。剪枝有兩種：
先剪枝:在構造過程中，當某個節點滿足剪枝條件，則直接停止此分支的構造。 後剪枝:先構造完成完整的決策樹，再通過某些條件周遊樹進行剪枝。
決策樹的優缺點
優點：直覺，便于了解，小規模資料集有效
缺點：1.處理連續變量不好；
2.類别較多時，錯誤增加的比較快；
3.可規模性一般。
參考: <<統計學習方法— 李航>>