全面總結機器學習項目和面試中幾乎繞不開的決策樹

定義

決策樹是一種常見的機器學習演算法，它的思想十分樸素，類似於我們平時利用選擇做決策的過程。

例如有人給我們介紹新的對象的時候，我們就要一個個特點去判斷，於是這種判斷的過程就可以畫成一棵樹，例如根據特點依次判斷：

如上，決策的形式以樹的形式進行示意和編碼，就形成了決策樹。

結構

顯然，決策樹在邏輯上以樹的形式存在，包含根節點、內部結點和葉節點。

根節點：包含數據集中的所有數據的集合

內部節點：每個內部節點為一個判斷條件，並且包含數據集中滿足從根節點到該節點所有條件的數據的集合。根據內部結點的判斷條件測試結果，內部節點對應的數據的集合別分到兩個或多個子節點中。

葉節點：葉節點為最終的類別，被包含在該葉節點的數據屬於該類別。

簡而言之，決策樹是一個利用樹的模型進行決策的多分類模型，簡單有效，易於理解。

偽代碼

決策樹演算法的偽代碼（參照了python語法）如下圖所示：

劃分選擇

可以看到，在偽代碼中，大部分步驟都是簡單而明確的，而最重要的步驟在於從A中選取最優的屬性a，可以說，屬性選擇的質量，決定了決策樹的預測準確度。這很容易理解，例如我們看一個學生聰明與否可以看他的成績，但是如果依靠他的身高預測他是否聰明，顯然得不到好的結果。

一般的原則是，希望通過不斷劃分節點，使得一個分支節點包含的數據儘可能的屬於同一個類別，即「純度「越來越高。

這裡列出三種常用的準則。

信息增益準則

我們先對一個節點的純度進行定義，我們將其稱之為信息熵：

其中代表當前節點D的數據中第k類樣本所佔的比例。

觀察該信息熵的定義，有以下幾個特點：

由都屬於[0,1]，Ent(D)必定為正值，值越大說明純度越低

Ent(D)在k=1=1時取值最小值0，時取值最大值

信息熵是一個節點的固有性質，和該節點選取什麼屬性進行下一步的劃分無關

在定義了信息熵之後，對信息增益進行定義，假設選取屬性a有V個取值，

，按照決策樹的規則，D將被劃分為V個不同的節點數據集，

代表其中第v個節點：

觀察該式，有以下幾點說明：

Ent(D)是確定的，和選取的屬性a無關，我們可以將之看為定值

表示分支節點所佔的比例大小，顯然數據集越大的分支節點權重越高

分支節點整體純度越大，則後一項越小，信息增益Gain變得越大，所以我們的目標是如何最大化信息增益

由此，我們得到了一種選擇劃分屬性的方法，計算以每個屬性進行劃分子節點得到的信息增益，選擇其中最大的作為選擇的屬性。

信息增益率準則

信息增益原則對於每個分支節點，都會乘以其權重，也就是說，由於權重之和為1，所以分支節點分的越多，即每個節點數據越小，純度可能越高。這樣會導致信息熵準則偏愛那些取值數目較多的屬性。

為了解決該問題，這裡引入了信息增益率，定義如下：

相當於引入了修正項IV(a)，它是對於屬性a的固有值。

需要注意的是，信息增益率原則可能對取值數目較少的屬性更加偏愛,為了解決這個問題，可以先找出信息增益在平均值以上的屬性，在從中選擇信息增益率最高的。

基尼指數準則

在CART決策樹中，使用基尼指數來選擇屬性，首先定義數據集D的基尼值：

形象的說，基尼值代表了從D中隨機選擇兩個樣本，其類別不一致的概率。

有了基尼值後，可以在此基礎上定義基尼指數：

其的含義和之前相同，可以看出基尼指數越小，說明純度越高，我們可以通過選擇基尼指數小的屬性來劃分子節點。

剪枝

剪枝是應該決策樹過擬合的一種重要方法，主要分為以下兩種：

預剪枝：該策略就是在對一個節點進行劃分前進行估計，如果不能提升決策樹泛化精度，就停止劃分，將當前節點設置為葉節點。那麼怎麼測量泛化精度，就是留出一部分訓練數據當做測試集，每次劃分前比較劃分前後的測試集預測精度。

優點：降低了過擬合風險，降低了訓練所需的時間。

缺點：預剪枝是一種貪心操作，可能有些劃分暫時無法提升精度，但是後續劃分可以提升精度。故產生了欠擬合的風險。

後剪枝：該策略是首先正常建立一個決策樹，然後對整個決策樹進行剪枝。按照決策樹的廣度優先搜索的反序，依次對內部節點進行剪枝，如果將某以內部節點為根的子樹換成一個葉節點，可以提高泛化性能，就進行剪枝。

優先：降低過擬合風險，降低欠擬合風險，決策樹效果提升比預剪枝強

缺點：時間開銷大得多

特殊值處理

連續值處理

在之前進行選擇屬性的時候，我們僅僅討論了屬性值為離散值的情況，例如身高分為「極高、高、較高、中等、較矮」五個選項，但是如果數據集中身高為連續值，例如140-210cm，我們該如何處理呢？

這裡可以採用二分的思想，將連續值化為離散值。由於我們的數據集是有限的，即使是連續值，屬性a在數據集中也只出現了有限個確定的值，記為，且。

取n個值的中點，令

我們得到了n-1個中點，,任取一個值可以將數據集D分為兩個，表示D中大的數據，表示D中小的數據集合，這樣，我們便可以同離散值一樣進行處理了。

接下來的問題是，選取哪一個t呢？顯然在信息增益準則下，應該選擇使得信息增益最大的t:

經過稍加改造的信息增益公式就可以選擇最好的t來進行劃分。

缺失值處理

缺失值處理較為複雜，設計到較多的公式，在這裡給出鏈接，讀者可以參考閱讀

其主要思想是

在選擇屬性時，僅使用不缺失該屬性的數據來計算信息增益，最後乘以一個代表缺失數據比例的比例係數

在對某個屬性進行劃分子節點時，對於不缺失該屬性的數據正常劃分，對於缺失該屬性的數據，按不同的權重劃分進行每個子節點

多變數決策樹

實際上大部分機器學習的分類演算法，都是將一個具有n個屬性的數據，看成一個在n維空間的一個點，分類的過程就是在n維空間或者更高維度空間中找到超平面，將這些點進行劃分。

而普通的決策樹演算法有一個特點，由於它每個節點的劃分條件都是單獨的，明確的，所以決策樹的決策邊界是平行於空間的坐標軸的。如下圖所示：

這對其擬合特性有一定的影響，當數據比較複雜時，需要較多的屬性才能得到較好的劃分，而多變數決策樹就可以解決該問題。

在多變數決策樹的學習過程中，不是為每個非葉結點尋找一個最優劃分屬性，而是試圖建立一個合適的線性分類器。 如下圖所示：

多變數決策樹較複雜，如果想進一步了解，可以閱讀這個領域的論文。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！