決策樹(Decision Tree）是在已知各種情況發生機率的基礎上，通過構成決策樹來判斷其可行性的決策分析方法，是直覺運用機率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝幹，故稱決策樹。在機器學習中，決策樹是一個預測模型，他代表的是對象屬性與對象值之間的一種映射關系。
決策樹是對資料進行分類，以此達到預測的目的。決策樹方法先根據訓練集資料形成決策樹，如果該樹不能對所有對象給出正确的分類，那麼選擇一些例外加入到訓練集資料中，重複該過程一直到形成正确的決策集。決策樹代表着決策集的樹形結構。
決策樹由決策結點、分支和葉子組成。決策樹中最上面的結點為根結點，每個分支是一個新的決策結點，或者是樹的葉子。每個決策結點代表一個問題或決策，通常對應于待分類對象的屬性。每一個葉子結點代表一種可能的分類結果。沿決策樹從上到下周遊的過程中，在每個結點都會遇到一個測試，對每個結點上問題的不同的測試輸出導緻不同的分支，最後會到達一個葉子結點，這個過程就是利用決策樹進行分類的過程，利用若幹個變量來判斷所屬的類别。
一、決策樹構造及其運用
1、樹的定義
樹是由節點和邊兩種元素組成的結構。了解樹，就需要了解幾個關鍵詞：根節點、父節點、子節點和葉子節點。
父節點和子節點是相對的，說白了子節點由父節點根據某一規則分裂而來，然後子節點作為新的父親節點繼續分裂，直至不能分裂為止。而根節點是沒有父節點的節點，即初始分裂節點，葉子節點是沒有子節點的節點，如下圖所示：
決策樹利用如上圖所示的樹結構進行決策，每一個非葉子節點是一個判斷條件，每一個葉子節點是結論。從跟節點開始，經過多次判斷得出結論。
2、如何利用樹進行決策
銀行希望能夠通過一個人的資訊（包括職業、年齡、收入、學曆）去判斷他是否有貸款的意向，進而更有針對性地完成工作。下表是銀行現在能夠掌握的資訊，我們的目标是通過對下面的資料進行分析建立一個預測使用者貸款一下的模型。
| 職業 | 年齡 | 收入 | 學曆 | 是否貸款 |
| 自由職業 | 28 | 5000 | 高中 | 是 |
| 勞工 | 36 | 5500 | 高中 | 否 |
| 勞工 | 42 | 2800 | 國中 | 是 |
| 白領 | 45 | 3300 | 國小 | 是 |
| 白領 | 25 | 10000 | 大學 | 是 |
| 白領 | 32 | 8000 | 碩士 | 否 |
| 白領 | 28 | 13000 | 博士 | 是 |
| 自由職業 | 21 | 4000 | 大學 | 否 |
| 自由職業 | 22 | 3200 | 國小 | 否 |
| 勞工 | 33 | 3000 | 高中 | 否 |
| 勞工 | 48 | 4200 | 國小 | 否 |
上邊中有4個客戶的屬性，如何綜合利用這些屬性去判斷使用者的貸款意向？
決策樹的做法是每次選擇一個屬性進行判斷，如果不能得出結論，繼續選擇其他屬性進行判斷，直到能夠“肯定地”判斷出使用者的類型或者是上述屬性都已經使用完畢。比如說我們要判斷一個客戶的貸款意向，我們可以先根據客戶的職業進行判斷，如果不能得出結論，再根據年齡作判斷，這樣以此類推，直到可以得出結論為止。
決策樹用樹結構實作上述的判斷流程，如下圖所示：
上圖所示的是通過輸入使用者的資訊，輸出使用者的貸款意向。如果要判斷某一客戶是否有貸款的意向，直接根據使用者的職業、收入、年齡以及學曆就可以分析得出使用者的類型。如某客戶的資訊為：{職業、年齡，收入，學曆}={勞工、39， 1800，國小}，将資訊輸入上述決策樹，可以得到下列的分析步驟和結論。
第一步：根據該客戶的職業進行判斷，選擇“勞工”分支
第二步：根據客戶的年齡進行選擇，選擇年齡”<=40”這一分支
第三步：根據客戶的學曆進行選擇，選擇”國小”這一分支，得出該客戶無貸款意向的結論
3、決策樹的建構
從上述步驟可以看出，決策生成過程中有幾個個重要的問題：
- 資料如何分割
- 如何選擇分裂的屬性
- 什麼時候停止分裂
假如我們已經選擇了一個分裂的屬性，那怎樣對資料進行分裂呢？
I、資料分割
分裂屬性的資料類型分為離散型和連續性兩種情況，對于離散型的資料，按照屬性值進行分裂，每個屬性值對應一個分裂節點；對于連續性屬性，一般性的做法是對資料按照該屬性進行排序，再将資料分成若幹區間，如[0,10]、[10,20]、[20,30]、…，一個區間對應一個節點，若資料的屬性值落入某一區間則該資料就屬于其對應的節點。
設有資料表如下：
| 職業 | 年齡 | 是否貸款 |
| 白領 | 30 | 否 |
| 勞工 | 40 | 否 |
| 勞工 | 20 | 否 |
| 學生 | 15 | 否 |
| 學生 | 18 | 是 |
| 白領 | 42 | 是 |
屬性“職業”是離散型變量，有三個取值，分别為白領、勞工和學生，根據三個取值對原始的資料進行分割，如下表所示:
| 取值 | 貸款人數 | 不貸款人數 |
| 白領 | 1 | 1 |
| 勞工 | 2 | |
| 學生 | 1 | 1 |
上表可以表示成如下的決策樹結構：
屬性“年齡”是連續性變量，這裡将資料分成三個區間，分别是[0，20]、(20,40]、(40,*]，則每一個區間的分裂結果如下：
| 年齡分組 | 貸款人數 | 不貸款人數 |
| [0 ,20] | 1 | 2 |
| (20,40] | 2 | |
| (40,* ] | 1 |
上表可以表示成如下的決策樹結構：
II、分裂屬性的選擇
前面介紹了分裂屬性是如何對資料進行分割的，那麼怎樣選擇分裂的屬性呢？
決策樹采用貪婪思想進行分裂，即選擇可以得到最優分裂結果的屬性進行分裂。那麼怎樣才算是最優的分裂結果？最理想的情況當然是能找到一個屬性剛好能夠将不同類别分開，但是大多數情況下分裂很難一步到位，我們希望每一次分裂之後孩子節點的資料盡量”純”，以下圖為例：
從圖例1和圖例2可以明顯看出，屬性2分裂後的子節點比屬性1分裂後的子節點更純：屬性1分裂後每個節點的兩類的數量還是相同，跟根節點的分類結果相比完全沒有提高；按照屬性2分裂後每個節點各類的數量相差比較大，可以很大機率認為第一個子節點的輸出結果為類1，第2個子節點的輸出結果為2。
選擇分裂屬性是要找出能夠使所有子節點資料最純的屬性，決策樹使用資訊增益、資訊增益率或者基尼值作為選擇屬性的依據（相關概念及算法在ID3和C4.5中解釋）。
III、停止分裂的條件
決策樹不可能無限制地生長，總有停止分裂的時候，最極端的情況是當節點分裂到隻剩下一個資料點時自動結束分裂，但這種情況下樹過于複雜，而且預測的精度不高。一般情況下為了降低決策樹複雜度和提高預測的精度，會适當提前終止節點的分裂
以下是決策樹節點停止分裂的一般性條件：
- 最小節點數：當節點的資料量小于一個指定的數量時，不繼續分裂。兩個原因：一是資料量較少時，再做分裂容易強化噪聲資料的作用；二是降低樹生長的複雜性。提前結束分裂一定程度上有利于降低過拟合的影響
- 熵或者基尼值小于閥值：熵和基尼值的大小表示資料的複雜程度，當熵或者基尼值過小時，表示資料的純度比較大，如果熵或者基尼值小于一定程度數，節點停止分裂
- 決策樹的深度達到指定的條件：節點的深度可以了解為節點與決策樹跟節點的距離，如根節點的子節點的深度為1，因為這些節點與跟節點的距離為1，子節點的深度要比父節點的深度大1。決策樹的深度是所有葉子節點的最大深度，當深度到達指定的上限大小時，停止分裂
- 所有特征已經使用完畢，不能繼續進行分裂：被動式停止分裂的條件，當已經沒有可分的屬性時，直接将目前節點設定為葉子節點
IV、決策樹的建構方法
根據決策樹的輸出結果，決策樹可以分為分類樹和回歸樹，分類樹輸出的結果為具體的類别，而回歸樹輸出的結果為一個确定的數值。
決策樹的建構算法主要有ID3、C4.5、CART三種，其中ID3和C4.5是分類樹，CART是分類回歸樹。本文介紹ID3和C4.5技術，其中ID3是決策樹最基本的建構算法，而C4.5和CART是在ID3的基礎上進行優化的算法。
根據決策樹的輸出結果，決策樹可以分為分類樹和回歸樹，分類樹輸出的結果為具體的類别，而回歸樹輸出的結果為一個确定的數值。
決策樹的建構算法主要有ID3、C4.5、CART三種，其中ID3和C4.5是分類樹，CART是分類回歸樹。本文介紹ID3和C4.5技術，其中ID3是決策樹最基本的建構算法，而C4.5和CART是在ID3的基礎上進行優化的算法。
二、ID3算法
ID3算法最早是由羅斯昆（J.Ross Quinlan）于1975年在悉尼大學提出的一種分類預測算法，算法的核心是“資訊熵（Information entropy）”。ID3算法通過計算每個屬性的資訊增益，認為資訊增益高的是好屬性，每次劃分選取資訊增益最高的屬性為劃分标準，重複這個過程，直至生成一個能完美分類訓練樣例的決策樹。
1、資訊熵
資訊論之父 C. E. Shannon 在1948年發表的論文“通信的數學理論（A Mathematical Theory of Communication）”中，Shannon指出，任何資訊都存在備援，備援大小與資訊中每個符号（數字、字母或單詞）的出現機率或者說不确定性有關。Shannon借鑒了熱力學的概念，把資訊中排除了備援後的平均資訊量稱為“資訊熵”，并給出了計算資訊熵的數學表達式。
事件ai 的資訊量I(ai)可如下度量：
其中p(ai)表示事件ai發生的機率。
假設有n個互不相容的事件
它們中有且僅有一個發生，則其平均的資訊量可如下度量：
資訊熵是消除不确定性所需資訊量的度量，也即未知事件可能含有的資訊量。
例如，投擲一枚分币，正面和反面朝上的機率相對，為1/2，這一随機試驗所有可能結果的發生機率所包含的資訊量的大小，即資訊熵值為，
假設這枚分币正反面不均勻，一面朝上的機率為0.3，另一面為0.7，資訊熵值為，
對于極端情況，一面朝上的機率為0，另一面為1，資訊熵值為，
式中，對數底數可以為任何數，不同的取值對應了熵的不同機關。通常對數的底數取2，并規定當p(ai) = 0時，
當正反面朝上機率相等時，結果最難猜，資訊熵最大；正面朝上機率為0.7、反面朝上機率為0.3時，應該猜正面朝上，會有70%勝算，但資訊熵減小；正面朝上機率為1、反面朝上機率為0時，正面一定朝上，這時資訊熵為0。
2、ID3算法中資訊量大小的度量
在運用ID3算法進行決策樹分類過程中，假設D是訓練樣本集合，則D的熵（entropy）表示為：
其中pipi表示第i個類别在整個訓練元組中出現的機率，可以用屬于此類别元素的數量除以訓練元組元素總數量作為估計。熵的實際意義表示是D中元組的類标号所需要的平均資訊量。
現對訓練樣本集合D按屬性A進行劃分，則A對D劃分的期望資訊為：
式中|D|為練樣本量，Dj 為屬性A的不同水準樣本數，info(Dj)為屬性A的不同水準的熵。
而資訊增益為，
3、ID3算法案例
學習資料挖掘技術的最好方法是找到詳細案例和看懂計算過程。有時算法雖然不難，但公式表達很難了解。
案例：SNS社群中不真實賬号檢測，使用ID3算法構造決策樹。
| 日志密度/L | 好友密度/F | 真實頭像/H | 真實賬戶/R |
| S | S | NO | NO |
| S | L | YES | YES |
| L | M | YES | YES |
| M | M | YES | YES |
| L | M | YES | YES |
| M | L | NO | YES |
| M | S | NO | NO |
| L | M | NO | YES |
| M | S | NO | YES |
| S | S | YES | NO |
注：表中S、M和L分别表示小、中和大。設L、F、H和R表示日志密度、好友密度、是否使用真實頭像和賬号是否真實，試用ID3算法構造決策樹
解：設D為10個樣本集，其中決策屬性（真實賬戶/R）有7個YES、3個NO。決策屬性資訊熵為，
日志密度屬性期望資訊熵為：
好友密度屬性期望資訊熵為：
真實頭像屬性期望資訊熵為：
日志密度資訊增益: gain(L) = info(D)−infoL(D) = 0.8813–0.6 = 0.2813
好友密度資訊增益: gain(F) = info(D)−infoF(D) = 0.8813–0.3245 = 0.5568
真實頭像資訊增益: gain(H) = info(D)−infoH(D) = 0.8813–0.8464 = 0.0349
因為好友密度（F）具有最大的資訊增益（好友密度資訊熵最小，最易分割），是以第一次分裂選擇好友密度F為分裂屬性，分裂後的結果如下：
圖中按好友密度（F）分割樹，水準M和L為單一水準決策屬性分支（樹葉），沒有必要繼續分割。水準S包含決策屬性的不同水準，應該繼續分割。待分割決策資訊表為，
| 日志密度/L | 真實頭像/H | 真實賬戶/R |
| S | NO | NO |
| M | NO | NO |
| M | NO | YES |
| S | YES | NO |
此時，設D為4個樣本集，其中決策屬性（真實賬戶/R）有1個YES、3個NO。決策屬性資訊熵為：
日志密度屬性期望資訊熵為：
真實頭像屬性期望資訊熵為：
日志密度資訊增益: gain(L) = info(D)−infoL(D)=0.8113–0.5=0.2813
真實頭像資訊增益: gain(H)=info(D)−infoH(D)=0.8113–0.8464=0.6887
因為日志密度（L）具有最大的資訊增益，是以第二次分裂選擇日志密度（L）為分裂屬性，分裂後的結果如下圖表示：
圖中，日志密度為M時，無法做出判斷、也無法繼續進行分裂。至此，決策樹建構完畢。
設某人在SNS社群中的好友密度為L或M，無論其它屬性水準取值如何，均可判定為是真實賬戶；如果某人在SNS社群中的好友密度為S、日志密度也為S，可判定為是虛假賬戶；如果某人在SNS社群中的好友密度為S、日志密度為M，應根據真實頭像資訊做出判斷，由于樣本過少，無法繼續進行。
三、C4.5算法
ID3算法是決策樹的一個經典的構造算法，但ID3算法也存在一些問題，比較突出的缺陷是資訊增益的計算依賴于特征水準較多的特征，而屬性取值最多的屬性并不一定最優。例如，投擲一枚分币和一個色子這兩個随機試驗，所有可能的期望資訊熵為，
通過資訊熵的定義可知，在給定特征水準數條件下，各水準發生機率相等（如擲篩子6個數字發生的機率都為1616），期望資訊熵最大。是以，當決策資訊中某個變量特征水準較多時，ID3算法按資訊增益名額往往會選擇該變量或屬性做為分割節點。
1、C4.5算法的兩個基本公式
I、“分裂資訊”公式
C4.5算法首先定義了“分裂資訊”，其定義可以表示成：
式中，各符号意義與ID3算法相同，符号|D|為訓練樣本數、|Dj|為屬性A各水準樣本數。
II、增益率
III、分裂資訊和增益率計算執行個體
在ID3算法案例中（SNS社群中不真實賬号檢測），決策屬性資訊熵為：
把決策屬性替換成其它屬性，即為各屬性分裂資訊熵。
日志密度分裂資訊：
好友密度分裂資訊：
真實頭像分裂資訊：
由前面ID3算法已知，
日志密度資訊增益: gain(L) = info(D)−infoL(D) = 0.8813–0.6 = 0.2813
好友密度資訊增益: gain(F) = info(D)−infoF(D) = 0.8813–0.3245 = 0.5568
真實頭像資訊增益: gain(H) = info(D)−infoH(D) = 0.8813–0.8464 = 0.0349
各屬性增益率為，
日志密度資訊增益率：
好友密度資訊增益率:
真實頭像資訊增益率:
由上述計算結果可知“好友密度”在屬性中具有最大的資訊增益比，取“好友密度”為分割屬性，引出一個分枝，樣本按此劃分。對引出的每一個分枝再用此分類法進行分類，再引出分枝。
某屬性的資訊增益除以分裂資訊，消除了屬性水準數量多少的影響，使得分裂屬性的選擇更加合理。