3.6　決策樹學(xué)習(xí)

如果關(guān)心可解釋性，那么決策樹分類器就是有吸引力的模型。正如其名稱所暗示的那樣，我們可以認(rèn)為該模型是根據(jù)一系列要回答的問題做出決定來完成數(shù)據(jù)分類。

在下面的例子中，讓我們考慮用決策樹來決定某一天的活動安排，如圖3-17所示。

基于訓(xùn)練數(shù)據(jù)集的特征，決策樹模型通過對一系列問題的學(xué)習(xí)來推斷樣本的分類標(biāo)簽。雖然圖3-17說明了基于分類變量的決策樹概念，但是如果特征是像鳶尾花數(shù)據(jù)集這樣的實數(shù)，這些概念也同樣適用。例如，我們可以簡單地定義萼片寬度特征軸的臨界值，并且問一個二元問題：“萼片的寬度≥2.8厘米嗎？”

使用決策樹算法，我們從樹根開始，在信息增益（IG）最大的特征上分裂數(shù)據(jù)，后續(xù)章節(jié)會更加詳細(xì)地解釋。各子節(jié)點在迭代過程中重復(fù)該分裂過程，直至只剩下葉子節(jié)點為止。這意味著所有節(jié)點上的樣本都屬于同一類。在實踐中，這可能會出現(xiàn)根深葉茂的樹，這樣容易導(dǎo)致過擬合。因此，我們通常希望通過限制樹的最大深度來對樹進(jìn)行修剪（prune）。

3.6.1　最大化信息增益——獲得最大收益

為保證在特征信息增益最大的情況下分裂節(jié)點，我們需要先定義目標(biāo)函數(shù)，然后進(jìn)行決策樹學(xué)習(xí)和算法優(yōu)化。該目標(biāo)函數(shù)可以在每次分裂的時候最大化信息增益，定義如下：

這里f是分裂數(shù)據(jù)的特征依據(jù)，Dp和Dj為父節(jié)點和第j個子節(jié)點，I為雜質(zhì)含量，Np為父節(jié)點的樣本數(shù)，Nj是第j個子節(jié)點的樣本數(shù)。正如我們所看到的那樣，父節(jié)點和子節(jié)點之間的信息增益僅在雜質(zhì)含量方面存在著差異，即子節(jié)點雜質(zhì)含量越低信息增益越大。然而，為簡便起見，同時考慮到減少組合搜索空間，大多數(shù)軟件庫（包括scikit-learn）只實現(xiàn)二元決策樹。這意味著每個父節(jié)點只有Dleft和Dright兩個子節(jié)點：

在二元決策樹中，度量雜質(zhì)含量或者分裂標(biāo)準(zhǔn)的三個常用指標(biāo)分別為基尼雜質(zhì)度（IG）、熵（IH）和分類誤差（IE）。我們從非空類（p（i|t）≠0）熵的定義開始：

其中p（i|t）≠0為某節(jié)點t屬于i類樣本的概率。如果節(jié)點上的所有樣本都屬于同一個類，則熵為0，如果類的分布均勻，則熵值最大。例如，對二元分類，如果p（i＝1|t）＝1或p（i=0|t）=0，則熵為0。如果類分布均勻，p（i＝1|t）＝0.5，p（i＝0|t）＝0.5，則熵為1。所以，我們可以說熵準(zhǔn)則試圖最大化決策樹中的互信息。

直觀地說，可以把基尼雜質(zhì)理解為盡量減少錯誤分類概率的判斷標(biāo)準(zhǔn)：

與熵類似，如果類是完全混合的，那么基尼雜質(zhì)最大，例如在二元分類中（c=2）：

然而，基尼雜質(zhì)和熵在實踐中經(jīng)常會產(chǎn)生非常相似的結(jié)果，而且通常并不值得花很多時間用不同的雜質(zhì)標(biāo)準(zhǔn)來評估樹，更好的選擇是嘗試不同的修剪方法。

另外一種雜質(zhì)度量的方法是分類誤差：

IE（t）=1-max{p（i|t）}

這對修剪樹枝是個有用的判斷標(biāo)準(zhǔn)，但我們并不推薦把它用于決策樹，因為它對節(jié)點的分類概率變化不太敏感?？梢酝ㄟ^圖3-18所示的兩種可能的分裂場景來說明。

從數(shù)據(jù)集的父節(jié)點Dp開始，它包含40個分類標(biāo)簽為1的樣本和40個分類標(biāo)簽為2的樣本，要分裂成Dleft和Dright兩個數(shù)據(jù)集。在A和B兩種場景下，用分類誤差作為分裂標(biāo)準(zhǔn)得到的信息增益（IGE=0.25）相同：

然而，與場景A（IGG=0.125）相比，基尼雜質(zhì)有利于分裂場景B（IGG=0.16），該場景確實是純度更高：

同樣，與場景A（IGH=0.19）相比，熵準(zhǔn)則對場景B（IGH=0.31）更為有利：

為了能更直觀地比較前面討論過的三種不同的雜質(zhì)標(biāo)準(zhǔn)，我們將把分類標(biāo)簽為1、概率在［0,1］之間的雜質(zhì)情況畫在圖上。注意，我們還將添加一個小比例樣本的熵（熵/2）來觀察介于熵和分類誤差中間的度量標(biāo)準(zhǔn)——基尼雜質(zhì)，具體的示例代碼如下：

執(zhí)行前面的示例代碼得到圖3-19。

3.6.2　構(gòu)建決策樹

通過將特征空間劃分成不同的矩形，決策樹可以構(gòu)建復(fù)雜的決策邊界。然而，我們必須小心，因為決策樹越深，決策邊界就越復(fù)雜，越容易導(dǎo)致過擬合。假設(shè)最大深度為4，以熵作為雜質(zhì)度量標(biāo)準(zhǔn)，用scikit-learn來訓(xùn)練決策樹模型。雖然為了可視化，我們可能需要進(jìn)行特征縮放，但請注意該特征縮放并非決策樹算法的要求。代碼如下：

執(zhí)行代碼后，通常我們會得到?jīng)Q策樹與坐標(biāo)軸平行的決策邊界，如圖3-20所示。

scikit-learn有一個不錯的功能，它允許我們在訓(xùn)練完成后輕松地通過下述代碼可視化決策樹模型（如圖3-21所示）：

然而，作為繪制決策樹的后端，用Graphviz程序可以更好地完成可視化。讀者可以從http://www.graphviz.org免費(fèi)下載該程序，它支持Linux、Window和macOS。除了Graphviz以外，我們還將采用被稱為PyDotPlus的Python庫，其功能與Graphviz類似，它允許把.dot數(shù)據(jù)文件轉(zhuǎn)換成決策樹的圖像。在安裝Graphviz后，我們可以直接調(diào)用pip程序安裝PyDotPlus（http://www.graphviz.org/download上有詳細(xì)的指令），例如，在你自己的計算機(jī)上可以執(zhí)行下面的命令：

安裝PyDotPlus的先決條件

注意到在某些系統(tǒng)中，在安裝PyDotPlus之前，你可能要先執(zhí)行下述命令以安裝其所依賴的軟件包：

執(zhí)行下述代碼將在本地目錄以PNG格創(chuàng)建決策樹的圖像文件：

通過設(shè)置out_file=None，可以直接把數(shù)據(jù)賦予dot_data變量，而不是在磁盤上產(chǎn)生中間文件tree.dot。參數(shù)filled、rounded、class_names和feature_names為可選項，但是要使圖像的視覺效果更好，就需要添加顏色、邊框的邊緣圓角，并在每個節(jié)點上顯示大多數(shù)分類標(biāo)簽，以及分裂標(biāo)準(zhǔn)的特征。這些設(shè)置完成后將得到圖3-22所示的決策樹圖像。

現(xiàn)在，我們可以在決策樹圖上很好地追溯訓(xùn)練數(shù)據(jù)集的分裂過程。從105個樣本的根節(jié)點開始，以花瓣寬度0.75厘米作為截止條件，先把樣本數(shù)據(jù)分裂成大小分別為35和70的兩個子節(jié)點。我們可以看到左面子節(jié)點的純度已經(jīng)很高，它只包含Iris-setosa類（基尼雜質(zhì)度=0）。而右面子節(jié)點則進(jìn)一步分裂成Iris-versicolor和Iris-virginica兩類。

在樹以及決策區(qū)域圖上，我們可以看到?jīng)Q策樹在花朵分類上的表現(xiàn)不錯。不幸的是scikit-learn目前還不提供手工修剪決策樹的函數(shù)。然而，我們可以返回到前面的代碼示例，把決策樹的參數(shù)max_depth修改為3，然后與當(dāng)前的模型進(jìn)行比較，但是我們將把這作為練習(xí)題留給感興趣的讀者。

3.6.3　多個決策樹的隨機(jī)森林組合

在過去十年里，由于集成方法具有良好的分類性能和對過擬合的魯棒性，該算法在機(jī)器學(xué)習(xí)的應(yīng)用中廣受歡迎。雖然在第7章中，我們將討論包括裝袋（bagging）和boosting在內(nèi)的不同集成方法，但是在這里我們將先討論基于決策樹的隨機(jī)森林算法，該算法以其良好的可擴(kuò)展性和易用性而聞名。可以把隨機(jī)森林視為決策樹的集成。隨機(jī)森林的原理是對受較大方差影響的多個決策樹分別求平均值，然后構(gòu)建一個具有更好泛化性能和不易過擬合的強(qiáng)大模型。隨機(jī)森林算法可以概括為以下四個簡單的步驟：

1）隨機(jī)提取一個規(guī)模為n的bootstrap樣本（從訓(xùn)練數(shù)據(jù)集中有放回地隨機(jī)選擇n個樣本）。

2）基于bootstrap樣本生成決策樹。在每個節(jié)點上完成以下的任務(wù)：

a. 不放回地隨機(jī)選擇d個特征。

b. 根據(jù)目標(biāo)函數(shù)的要求，例如信息增益最大化，使用選定的最佳特征來分裂節(jié)點。

3）把步驟1和2重復(fù)k次。

4）聚合每棵樹的預(yù)測結(jié)果，并以多數(shù)票機(jī)制確定標(biāo)簽的分類。在第7章中，我們將更詳細(xì)地討論多數(shù)票機(jī)制。

應(yīng)該注意，在步驟2中訓(xùn)練單個決策樹時，并不需要評估所有的特征來確定節(jié)點的最佳分裂方案，而是僅僅考慮其中的一個隨機(jī)子集。

有放回抽樣和不放回抽樣

如果你對有放回抽樣的概念不熟悉，那么可以通過一個簡單的思考實驗來說明。假設(shè)我們玩抽獎游戲，從一個罐中隨機(jī)抽取數(shù)字。罐中有0、1、2、3和4五個獨(dú)立的數(shù)字，每次抽一個。第一輪從罐中抽出某個數(shù)字的概率是1/5。如果不放回抽樣，每輪抽獎后抽出的數(shù)字將不再放回罐中。因此，下一輪從剩余的數(shù)字中抽到某個數(shù)字的概率就取決于前一輪。例如，如果剩下的數(shù)字是0、1、2和4，那么在下一輪抽到0的概率將變成1/4。

然而，有放回抽樣會把每次抽到的數(shù)字放回罐中，以確保在下一輪抽獎時，抽到某個數(shù)字的概率保持不變。換句話說，在有放回抽樣時，樣本（數(shù)字）是獨(dú)立的，并且協(xié)方差為零。例如五輪隨機(jī)數(shù)的抽樣結(jié)果如下所示：

• 不放回隨機(jī)抽樣：2、1、3、4、0
• 有放回隨機(jī)抽樣：1、3、3、4、1

盡管隨機(jī)森林的可解釋性不如決策樹好，但是其顯著優(yōu)勢在于不必?fù)?dān)心超參數(shù)值的選擇。通常不需要修剪隨機(jī)森林，因為集成模型對來自單個決策樹的噪聲有較強(qiáng)的抵抗力。實際上，唯一需要關(guān)心的參數(shù)是在步驟3中如何選擇隨機(jī)森林中樹的數(shù)量k。通常，樹越多，隨機(jī)森林分類器的性能就越好，當(dāng)然計算成本的增加也就越大。

雖然在實踐中并不常見，但是隨機(jī)森林分類器的其他超參數(shù)也可以被優(yōu)化，我們可以用在第6章中將要討論的技術(shù)進(jìn)行優(yōu)化。這些超參數(shù)分別包括步驟1 bootstrap樣本的規(guī)模n和步驟2.a中每次分裂隨機(jī)選擇的特征數(shù)d。通過bootstrap樣本規(guī)模n來控制隨機(jī)森林的偏差-方差權(quán)衡。

因為特定訓(xùn)練數(shù)據(jù)被包含在bootstrap樣本中的概率較低，所以減小bootstrap樣本的規(guī)模會增加在單個樹之間的多樣性。因此，縮小bootstrap樣本的規(guī)?？赡軙黾与S機(jī)森林的隨機(jī)性，這有助于降低過擬合。然而，較小規(guī)模的bootstrap樣本通常會導(dǎo)致隨機(jī)森林的總體性能較差，訓(xùn)練樣本和測試樣本之間的性能差別很小，但總體測試性能較低。相反，擴(kuò)大bootstrap樣本的規(guī)?？赡軙黾舆^擬合。由于bootstrap樣本的存在，各個決策樹之間會變得更相似，它們能通過學(xué)習(xí)更加緊密地擬合原始的訓(xùn)練數(shù)據(jù)集。

包括scikit-learn中的RandomForestClassifier實現(xiàn)在內(nèi)，在大多數(shù)的隨機(jī)森林實現(xiàn)中，bootstrap樣本的規(guī)模一般與原始訓(xùn)練數(shù)據(jù)集樣本的規(guī)模保持一致，這通常會有一個好的偏置-方差權(quán)衡。對于每輪分裂的特征數(shù)d，我們希望選擇的值小于訓(xùn)練數(shù)據(jù)集的特征總數(shù)。在scikit-learn以及其他實現(xiàn)中，合理的默認(rèn)值為，這里m為訓(xùn)練數(shù)據(jù)集的特征總數(shù)。

為了方便起見，我們并未從決策樹本身開始構(gòu)建隨機(jī)森林分類器，因為scikit-learn已經(jīng)實現(xiàn)了一個分類器可供我們使用：

執(zhí)行前面的代碼可以看到由隨機(jī)森林中樹的集成產(chǎn)生的決策區(qū)域，如圖3-23所示。

通過設(shè)置參數(shù)n_estimators并用基尼雜質(zhì)度作為準(zhǔn)則來分裂節(jié)點，我們利用前面的代碼訓(xùn)練了由25個決策樹組成的隨機(jī)森林。雖然在非常小的訓(xùn)練數(shù)據(jù)集上生長出來小規(guī)模隨機(jī)森林，但是為了演示我們設(shè)置參數(shù)n_jobs，它使我們可以用多核計算機(jī)（這里是雙核）來并行訓(xùn)練模型。