?一文讀懂決策樹

1. 不確定性的理解

下圖為事件A是否發(fā)生的概率分布，事件發(fā)生記為1，討論事件A的不確定性。

(1) 我們考慮一種極端的情況，若 p=1或 p=0，表示為事件A必定發(fā)生或事件A不可能發(fā)生，即不確定性為0。

(2) 若 p>1/2，即事件A發(fā)生的概率大于事件A不發(fā)生的概率，我們傾向于預(yù)測事件A是發(fā)生的；若 p<1/2，即事件A不發(fā)生的概率小于事件A發(fā)生的概率，我們傾向于預(yù)測事件A是不發(fā)生的。若 p=1/2，即事件A發(fā)生的概率等于事件A不發(fā)生的概率，我們無法作出預(yù)測，即事件A的不確定性達(dá)到最大，以致于我們無從預(yù)測，或者可以理解成事件A太復(fù)雜了，復(fù)雜的我們只能靠運(yùn)氣去猜測事件A是否發(fā)生。

2. 決策樹不確定性的度量方法

本文用熵和基尼指數(shù)去衡量數(shù)據(jù)集的不確定性，假設(shè)數(shù)據(jù)集包含了K類，每個(gè)類的大小和比例分別為 Di 和 pi，i = 1,2,...K。

（1）熵的不確定性度量方法

在信息論和概率論統(tǒng)計(jì)中，熵是表示隨機(jī)變量不確定性的度量，令熵為H(p)，則：

熵越大，數(shù)據(jù)集的不確定性就越大。

（2）基尼指數(shù)的不確定度量方法

數(shù)據(jù)集的基尼指數(shù)定義為：

基尼指數(shù)越大，數(shù)據(jù)集的不確定性越大。

假設(shè)數(shù)據(jù)集A共有K個(gè)特征，記為xi，i=1,2,...K。數(shù)據(jù)集A的不確定性越大，則數(shù)據(jù)集A包含的信息也越多。假設(shè)數(shù)據(jù)集A的信息為H（A），經(jīng)過特征xi篩選后的信息為H(A|xi)，定義信息增益g(A,xi)為兩者的差值，即：

g(A,xi) = H(A) - H(A|xi)

選擇使數(shù)據(jù)集A信息增益最大的特征作為篩選特征，數(shù)學(xué)表示為：

x = max( g(A,xi) ) = max( H(A) - H(A|xi) )

令決策樹的葉節(jié)點(diǎn)數(shù)為T，損失函數(shù)為：

其中C(T)為決策樹的訓(xùn)練誤差，決策樹模型用不確定性表示，不確定性越大，則訓(xùn)練誤差亦越大。T表示決策樹的復(fù)雜度懲罰，α參數(shù)權(quán)衡訓(xùn)練數(shù)據(jù)的訓(xùn)練誤差與模型復(fù)雜度的關(guān)系，意義相當(dāng)于正則化參數(shù)。

考慮極端情況：當(dāng)α趨于0的時(shí)候，最優(yōu)決策樹模型的訓(xùn)練誤差接近 0，模型處于過擬合；當(dāng)α趨于無窮大的時(shí)候，最優(yōu)決策樹模型是由根節(jié)點(diǎn)組成的單節(jié)點(diǎn)樹。

將數(shù)據(jù)集A通過一定的比例劃分為訓(xùn)練集和測試集。

決策樹的損失函數(shù)：

決策樹最優(yōu)模型的構(gòu)建步驟包括訓(xùn)練階段和測試階段：

訓(xùn)練階段：

（1）最小化決策樹的不確定性值得到的生成模型，即決策樹生成；

（2）通過決策樹剪枝，得到不同的正則化參數(shù)α下的最優(yōu)決策樹模型，即決策樹剪枝。

下面重點(diǎn)討論訓(xùn)練階段的決策樹生成步驟和決策樹剪枝步驟。

決策樹生成步驟：

（1） 根據(jù)決策樹的特征篩選準(zhǔn)則，選擇數(shù)據(jù)集信息增益最大的特征；

 （2） 重復(fù)第一個(gè)步驟，直到所有葉節(jié)點(diǎn)的不確定性為0 。

決策樹剪枝步驟：

（1） 將正則化參數(shù)α從小到大分成不同的區(qū)間，對(duì)決策樹的非葉節(jié)點(diǎn)進(jìn)行剪枝，令該節(jié)點(diǎn)為T，以該節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹為Tt。

（2） 當(dāng)α滿足如下條件時(shí)：

即節(jié)點(diǎn)為單節(jié)點(diǎn)樹的損失函數(shù)與子樹Tt的損失函數(shù)相等，而剪枝后的復(fù)雜度降低了，泛化性能較好，因此，對(duì)該節(jié)點(diǎn)進(jìn)行剪枝。

（3）遍歷所有非葉節(jié)點(diǎn)，得到每個(gè)剪枝后的最優(yōu)子樹與對(duì)應(yīng)的α參數(shù) 。

備注：決策樹生成和剪枝步驟只給出大致框架，具體請(qǐng)參考李航《統(tǒng)計(jì)學(xué)習(xí)方法》

測試階段：

通過測試集評(píng)估不同α參數(shù)下的最優(yōu)決策樹模型，選擇測試誤差最小的最優(yōu)決策樹模型和相應(yīng)的正則化參數(shù)α。

優(yōu)點(diǎn)：

算法簡單，模型具有很強(qiáng)的解釋性

可以用于分類和回歸問題

缺點(diǎn)：

決策樹模型很容易出現(xiàn)過擬合現(xiàn)象，即訓(xùn)練數(shù)據(jù)集的訓(xùn)練誤差很小，測試數(shù)據(jù)集的測試誤差很大，且不同的訓(xùn)練數(shù)據(jù)集構(gòu)建的模型相差也很大。實(shí)際項(xiàng)目中，我們往往不是單獨(dú)使用決策樹模型，為了避免決策樹的過擬合，需對(duì)決策樹結(jié)合集成算法使用，如bagging算法和boosting算法。