本文筆者將用具體例子講述決策樹的構建過程，分析：決策樹生成過程中有什麼樣的問題？
一、基本概念
決策樹的定義：
首先，決策樹是一種有監督的分類算法——即給定X，Y值，構建X，Y的映射關係。
不同於線性回歸等是多項式，決策樹是一種樹形的結構，一般由根節點、父節點、子節點、葉子節點構成如圖所示。
父節點和子節點是相對的，子節點可以由父節點分裂而來，而子節點還能作為新的父節點繼續分裂；根節點是沒有父節點，即初始分裂節點，葉子節點是沒有子節點的節點，為終節點。
每一個分支代表著一個判斷，每個葉子節點代表一種結果。
這是在已知各種情況的發生的概率的基礎上，通過構建決策樹來進行分析的一種方式。
預測方式：
根據輸入的樣本X的特徵屬性和決策樹的取值，將輸入的X樣本分配到某一個葉子節點中。將葉子節點中出現最多的Y值，作為輸入的X樣本的預測類別。目的：
最優的模型應該是：葉子節點中只包含一個類別的數據。
但是，事實是不可能將數據分的那麼的純，因此，需要「貪心」策略，力爭在每次分割時都比上一次好一些，分的更純一些。
二、決策樹構建過程
步驟一：將所有的特徵看成一個一個的節點，eg（擁有房產、婚姻狀態、年收入這些特徵，我們可以看成一個一個的節點。）
步驟二：遍歷當前特徵的每一種分割方式，找到最好的分割點eg（婚姻狀態這個特徵，我們可以按照單身、已婚、離婚進行劃分；也可以按照結過婚、沒有結過婚進行劃分）；將數據劃分為不同的子節點，eg： N1、 N2….Nm；計算劃分之後所有子節點的「純度」信息
步驟三：使用第二步遍歷所有特徵，選擇出最優的特徵，以及該特徵的最優的劃分方式，得出最終的子節點N1、 N2….Nm
步驟四：對子節點N1、N2….Nm分別繼續執行2-3步，直到每個最終的子節點都足夠「純」。
從上述步驟可以看出，決策生成過程中有兩個重要的問題：
對數據進行分割。選擇分裂特徵。什麼時候停止分裂。
1. 對數據進行分割
根據屬性值的類型進行劃分：
如果值為離散型，且不生成二叉決策樹，則此時一個屬性就是可以一個分支，比如：上圖數據顯示，婚姻狀態為一個屬性，而下面有三個值，單身、已婚、離婚，則這三個值都可以作為一個分類。
如果值為離散型，且生成二叉決策樹，可以按照 「屬於此子集」和「不屬於此子集」分成兩個分支。還是像上面的婚姻狀態，這可以按照已婚，和非婚，形成兩個分支。
如果值為連續性，可以確定一個值作為分裂點，按照大於分割點，小於或等於分割點生成兩個分支，如上圖數據，我可以按照6千元的點劃分成：大於6千元和小於6千元。
2. 找到最好的分裂特徵
決策樹算法是一種「貪心」算法策略——只考慮在當前數據特徵情況下的最好分割方式。
在某種意義上的局部最優解，也就是說我只保證在當分裂的時候，能夠保證數據最純就好。
對於整體的數據集而言：按照所有的特徵屬性進行劃分操作，對所有劃分操作的結果集的「純度」進行比較，選擇「純度」越高的特徵屬性作為當前需要分割的數據集進行分割操作。
決策樹使用信息增益作為選擇特徵的依據，公式如下：
H（D）為：分割前的純度。
H（D｜A）為：在給定條件A下的純度，兩者之差為信息增益度。如果信息增益度越大，則H（D｜A）越小，則代表結果集的數據越純。
計算純度的度量方式：Gini、信息熵、錯誤率。
一般情況下，選擇信息熵和Gini係數，這三者的值越大，表示越「不純」。
Gini：
信息熵：
錯誤率：
3. 什麼時候停止分裂
一般情況有兩種停止條件：
當每個子節點只有一種類型的時候停止構建。當前節點中記錄數小於某個閾值，同時迭代次數達到給定值時，停止構建過程。此時，使用 max(p(i))作為節點的對應類型。方式一可能會使樹的節點過多，導致過擬合(Overfiting)等問題。所以，比較常用的方式是使用方式二作為停止條件。
三、舉例
數據集如下：
1. 對數據特徵進行分割
擁有房產（是、否）婚姻狀態（單身、已婚、離婚）年收入（80、97.5）
2. 通過信息增益找到分割特徵
首先，計算按照擁有房產這個特徵進行劃分的信息增益，使用錯誤率進行純度的計算：
計算原始數據的純度：
計算按擁有房產劃分後的結果集數據純度H（D｜A）：
H(D| X=有房產) 的計算方式：
H(D| X=無房產) 的計算方式：
計算信息增益度Gain(房產)：
同理，可以計算：婚姻狀態 年收入=97.5
Gain(婚姻) = 0.205
Gain(婚姻) =0.395
按照Gain越大，分割後的純度越高，因此第一個分割屬性為收入，並按照97.5進行劃分。
左子樹的結果集夠純，因此不需要繼續劃分。
接下來，對右子樹年收入大於97.5的數據，繼續選擇特徵進行劃分，且不再考慮收入這個特徵，方法如上，可以得到如圖：
四、常見算法
ID3：
優點：決策樹構建速度快；實現簡單
缺點：
計算依賴於特徵數目較多的特徵，而屬性值最多的屬性並不一定最優 。ID3算法不是遞增算法，ID3算法是單變量決策樹，對於特徵屬性之間的關係不會考慮。抗噪性差。只適合小規模數據集，需要將數據放到內存中。C4.5：
在ID3算法的基礎上，進行算法優化提出的一種算法(C4.5)，使用信息增益率來取代ID3中的信息增益。
CART（Classification And Regression Tree）：
五、總結
ID3和5算法均只適合在小規模數據集上使用。ID3和5算法都是單變量決策樹當屬性值取值比較多的時候，最好考慮C4.5算法，ID3得出的效果會比較差 決策樹分類一般情況只適合小數據量的情況(數據可以放內存) CART算法是三種算法中最常用的一種決策樹構建算法(sklearn中僅支持CART)。三種算法的區別僅僅只是對於當前樹的評價標準不同而已，ID3使用信息增益、 5使用信息增益率、CART使用基尼係數。CART算法構建的一定是二叉樹，ID3和5構建的不一定是二叉樹。本文由 @SincerityY 原創發布於人人都是產品經理。未經許可，禁止轉載
題圖來自Unsplash，基於CC0協議