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

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

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

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

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

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

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

比較流行的屬性選擇方法： 信息增益

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

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

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

信息 用來消除不確定性

實際上，給定訓練集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，剪枝有兩種方法：

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

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