決策樹分析法解析（決策樹分析法的基本步驟詳解）

決策樹分類是數據挖掘中分類分析的一種算法。顧名思義，決策樹是基于“樹”結構來進行決策的，是人類在面臨決策問題時一種很天然的處理機制。例如下圖一個簡樸的判別買不買電腦的決策樹：

下圖是一個測試數據集，我們以此數據集為例，來看下如何生成一棵決策樹。

決策樹分類的主要使命是要確定各個類別的決策區域，或者說，確定不同類別之間的邊界。在決策樹分類模型中，不同類別之間的邊界通過一個樹狀結構來示意。

通過以上分析，我們可以得出以下幾點：

最大高度=決策屬性的個數

樹 越矮越好

要把 重要的、好的 屬性放在樹根

因此，決策樹建樹算法就是： 挑選樹根的過程

第一步，挑選屬性作為樹根

比較盛行的屬性挑選辦法： 信息增益

信息增益最大的屬性被認為是最好的樹根

在挑選屬性之前，我們先來了解一個概念： 熵 什么是熵？什么是信息？如何度量他們？

熵 用來示意不確定性的大小

信息 用來消退不確定性

實際上，給定練習集S，信息增益代表的是在不考慮任何輸入變量的情景下確定S中任一樣本所屬類別需要的信息（以消退不確定性）與考慮了某一輸入變量X后確定S中任一樣本所屬類別需要的信息之間的差。差越大，說明引入輸入變量X后，消退的不確定性，該變量對分類所起的作用就越大，因此被稱為是好的分裂變量。換句話說，要確定S中任一樣本所屬類別，我們希望所需要的信息越少越好，而引入輸入變量X能夠減少分類所需要的信息，因此說輸入變量X為分類這個數據挖掘使命帶來了信息增益。信息增益越大，說明輸入變量X越重要，因此應當被認為是好的分裂變量而優先挑選。

因此，計算信息增益的總的思路是：

1) 首先計算不考慮任何輸入變量的情景下要確定S中任一樣本所屬類別需要的熵Entropy(S)；

2) 計算引入每個輸入變量X后要確定S中任一樣本所屬類別需要的熵Entropy (X,S);

3) 計算二者的差，Entropy (S) - Entropy (X, S)，此即為變量X所能帶來的信息（增益），記為Gain(X,S)。

結合上面對于熵的解釋的文章里，我們能得出求熵的公式：

下圖很形象的解釋了熵代表的含義。

我們還以上面的一組數據來分析，信息增益詳細應當怎么算

根據上面的討論，我們先用公式計算不考慮任何輸入屬性時，要確定練習集S中任一樣本所屬類別需要的熵。

此例子中，目標屬性即buys_computer，有2個不同的取值，yes和no，因此有2個不同的類別（m=2）。設P對應buys_computer=yes的情景，N對應buys_computer=no的情景，則P有9個樣本，N有5個樣本。所以，總的熵就是：

即，E(p,n) = E(9,5) = 0.940

然后我們來求屬性age的熵，age有三個屬性，樣本個數分別為5，4，5，所以屬性age的熵就是：

最后，我們可以求出屬性age的信息增益為：

同樣的，我們可以分別求出income，student和credit_rating的信息增益

finally，我們可以得出屬性age的信息增益最大，所以，應當用屬性age作為樹根。

確定好樹根之后，下一步我們還要按照剛才的步驟來確定下一個節點的左右子樹分別用哪個屬性作為樹根，直到最后得出完整的決策樹。

雖然決策樹分類算法可以快速的猜測分類，但是也會有適度擬合（Overfitting）的問題。

有些生成的決策樹完全聽從于練習集，太安分守己，甚至于生成了太多的分支，某些分支可能是一些特別情景，出現的次數很少，不具有代表性，更有甚者僅在練習集中出現，導致模型的正確性很低。

通常采用剪枝的方式來克服 overfitting，剪枝有兩種辦法：

先剪:構造樹的過程中進行修剪。不符合條件的分支則不建。

后剪: 整個樹生成之后進行修剪