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

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

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

決策樹分類的主要任務(wù)是要確定各個類別的決策區(qū)域，或者說，確定不同類別之間的邊界。在決策樹分類模型中，不同類別之間的邊界通過一個樹狀結(jié)構(gòu)來表示。

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

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

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

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

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

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

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

信息 用來消除不確定性

實際上，給定訓(xùn)練集S，信息增益代表的是在不考慮任何輸入變量的情況下確定S中任一樣本所屬類別需要的信息（以消除不確定性）與考慮了某一輸入變量X后確定S中任一樣本所屬類別需要的信息之間的差。差越大，說明引入輸入變量X后，消除的不確定性，該變量對分類所起的作用就越大，因此被稱為是好的分裂變量。換句話說，要確定S中任一樣本所屬類別，我們希望所需要的信息越少越好，而引入輸入變量X能夠減少分類所需要的信息，因此說輸入變量X為分類這個數(shù)據(jù)挖掘任務(wù)帶來了信息增益。信息增益越大，說明輸入變量X越重要，因此應(yīng)該被認為是好的分裂變量而優(yōu)先選擇。

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

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

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

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

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

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

我們還以上面的一組數(shù)據(jù)來分析，信息增益具體應(yīng)該怎么算

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

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

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

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

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

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

finally，我們可以得出屬性age的信息增益最大，所以，應(yīng)該用屬性age作為樹根。

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

雖然決策樹分類算法可以快速的預(yù)測分類，但是也會有過度擬合（Overfitting）的問題。

有些生成的決策樹完全服從于訓(xùn)練集，太循規(guī)蹈矩，以至于生成了太多的分支，某些分支可能是一些特殊情況，出現(xiàn)的次數(shù)很少，不具有代表性，更有甚者僅在訓(xùn)練集中出現(xiàn)，導(dǎo)致模型的準確性很低。

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

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

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