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

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

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

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

通過(guò)以上分析，我們可以得出以下幾點(diǎn)：

因此，決策樹(shù)建樹(shù)算法就是： 選擇樹(shù)根的過(guò)程

第一步，選擇屬性作為樹(shù)根

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

信息增益最大的屬性被認(rèn)為是最好的樹(shù)根

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

熵 用來(lái)表示不確定性的大小

信息 用來(lái)消除不確定性

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

因此，計(jì)算信息增益的總的思路是：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

雖然決策樹(shù)分類(lèi)算法可以快速的預(yù)測(cè)分類(lèi)，但是也會(huì)有過(guò)度擬合（Overfitting）的問(wèn)題。

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

通常采用剪枝的方式來(lái)克服 overfitting，剪枝有兩種方法：

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

后剪: 整個(gè)樹(shù)生成之后進(jìn)行修剪