決策樹(Decision Tree)
決策樹是機器學習演算法中一種依靠對條件進行判斷來進行分類和回歸的演算法。決策樹的思想主要來源於Quinlan在1986年提出的ID3演算法和1993年提出的C4.5演算法，以及有Breiman等人在1984年提出的CART演算法。
本文將就決策樹的基本數學原理、基本演算法模型、三類演算法介紹、決策樹剪枝等幾個方面來詳細介紹決策樹。如有錯誤，還請留言指出。
什麼是Decision Tree？
引用網上一個很火的相親的例子：在相親的時候想看對方是否年齡是否過大？超過30：不見；未超過30：繼續判斷長相，丑：不見；不醜：繼續判斷收入：收入過低：不見；收入較高：見；收入中等：繼續判斷是否為公務員：是公務員：見；不是公務員：不見。
也就是說，這個女孩會根據自己的一系列規則來判斷是否見面。這在機器學習中就是一個二分類問題。
下面給出決策樹的定義。
定義： 決策樹是一個屬性結構的預測模型，代表對象屬性和對象值之間的一種映射關係。它又節點（node）和有向邊（directed edge）組成，其節點有兩種類型：內節點（internal node）和葉節點（leaf node），內部節點表示一個特徵或屬性，葉節點表示一個類。
如上圖所示的相親例子，藍色的橢圓內節點表示的是對象的屬性，橘黃色的矩形葉節點表示分類結果（是否相親），有向邊上的值則表示對象每個屬性或特徵中可能取的值。
Decision Tree的數學原理
信息熵：信息熵是一個很抽象的概念，表示信息的不確定性。先給出公式。
X，表示該事件中有限個值的離散隨機變數， 表示每個隨機變數在整個事件中發生的概率。我信息熵計算中我們定義當
=0時，H(X)=0，這是表示信息的不確定性最小，即事件是不發生的。
信息增益：假設離散屬性a有V個可能的取值，使用a來對樣本集D進行劃分，則會產生V個分支節點，其中第v個分支結點包含了X中所有在屬性a上取值相同的向本，記為 。我們算出信息熵，在考慮不同分支結點說包含的樣本總數不同，給每個分支結點賦予的權重
也不相同，即樣本數越多的分子節點的影響越大，於是可以計算出用屬性a對樣本X進行劃分得到的信息增益。其公式如下：
一般而言，信息增益越大，意味著屬性a劃分獲得的準確率提升越大，因此ID3演算法就是以信息增益來選擇劃分屬性的。
但是這種演算法一個很大的弊端就是在屬性a有很多個取值的時候算出的信息增益會很大（具體參考習慣書上的例子進行計算），這時得到的樹是一個分支極多但是深度極淺的樹。所以引入增益率的概念。
增益率：
其中
C4.5演算法就是先選出信息增益高於平均水平的屬性，然後在選出增益率較高的屬性。
剪枝處理：
剪枝是為了防止決策樹演算法過擬合。決策樹剪枝分為預剪枝和後剪枝。無論是預剪枝還是後剪枝都需要預留一部分數據作為驗證集用於剪枝的評估。（類似於cross validation）
預剪枝：
預剪枝是在決策樹生成的時候對每一個節點進行評估。在節點未生成之前根據定義該節點是一個葉節點，此時可以算出這個葉節點的準確率a，在劃分節點之後再進行評估，劃分後的準確率為b。如果劃分前的準確率a大於劃分後的準確率，則不產生這個節點。如果劃分前的準確率a小於劃分後的準確率b，則可以進行劃分。
後剪枝：
後剪枝是在訓練出一個完整的決策樹之後再從最末端的節點開始往根節點依次判斷是否進行剪枝。原理與預剪枝一樣，根據剪枝前後驗證集的準確率來判斷是否需要進行剪枝。
後剪枝決策樹通常比預剪枝決策樹保留了更多的分支。一般情況下，後剪枝決策樹過擬合風險較小，泛化能力往往優於預剪枝決策樹。
推薦閱讀：
