決策樹（Decision Tree莱衩，簡稱DT）是最經(jīng)典的機器學習模型之一爵嗅，它的預(yù)測結(jié)果容易理解，易于向業(yè)務(wù)部門解釋笨蚁，預(yù)測速度快睹晒，可以處理離散型數(shù)據(jù)和連續(xù)型數(shù)據(jù)趟庄。

1.決策樹算法原理

決策樹是一個類似于流程圖的樹結(jié)構(gòu)，分支節(jié)點表示對一個特征進行預(yù)測伪很，根據(jù)預(yù)測結(jié)果進行分類戚啥，葉子節(jié)點代表一個類別。如下圖所示锉试，我們用決策樹來決定下班后的安排：

figure7_1.png

我們分別對精力指數(shù)和情緒指數(shù)兩個特征進行測試猫十，并根據(jù)測試結(jié)果決定行為的類別。每選擇一個特征進行測試呆盖，數(shù)據(jù)集就被劃分成多個子數(shù)據(jù)集拖云。接著繼續(xù)在子數(shù)據(jù)集上選擇特征，并進行數(shù)據(jù)集劃分应又，直到創(chuàng)建出一個完整的決策樹宙项。創(chuàng)建好決策樹模型后，只要根據(jù)下班后的精力和情緒情況株扛，從根節(jié)點一路往下即可預(yù)測出下班后的行為尤筐。

問題來了，在創(chuàng)建決策樹的過程中洞就，要先對哪個特征進行分裂盆繁？比如上圖中的例子，先判斷精力指數(shù)進行分裂還是先判斷情緒指數(shù)進行分裂旬蟋？要回答這個問題油昂，我們需要從信息的量化談起。

1.信息增益

我們天天在談?wù)撔畔⒖敲葱畔⒁趺礃觼砹炕兀?948年秕狰，香農(nóng)在他著名的《通信的數(shù)學原理》中提出了信息熵（Entropy）的概念，從而解決了信息的量化問題躁染。香農(nóng)認為鸣哀，一條信息的信息量和它的不確定性有直接關(guān)系。一個問題不確定性越大吞彤，要搞清楚這個問題我衬，需要了解的信息就越多，其信息熵就越大饰恕。信息熵的計算公式如下：

其中挠羔，P(x)表示事件x出現(xiàn)的概率。例如埋嵌，一個盒子里分別有5個白球和5個紅球破加，隨機取出一個球。問：這個球是紅色的還是白色的雹嗦？這個問題的信息量多大呢范舀？由于紅球和白球出現(xiàn)的概率都是1/2合是，代入信息熵公式，可以得到其信息熵為：

即锭环，這個問題的信息量就是1bit聪全。對，你沒有看錯辅辩，信息量的單位就是比特难礼。我們要確定這個球是紅色的還是白色的，只需要1bit的信息就夠了玫锋。再舉一個極端的例子蛾茉，一個盒子里有10個白球，隨機取出一個球景醇，這個球是什么顏色的臀稚？這個問題的信息量是多少呢？答案是0三痰，因為這是一個確定事件，其概率P(x)=1窜管，代入信息熵公式散劫，即可得到其信息熵為0。即我們不需要再獲取任何新的信息幕帆，就可知道這個球一定是白色的获搏。

回到?jīng)Q策樹的構(gòu)建問題上，當我們要構(gòu)建一個決策樹時失乾，應(yīng)該優(yōu)先選擇哪個特征來劃分數(shù)據(jù)集呢常熙？答案是：遍歷所有的特征，分別計算碱茁，使用這個特征劃分數(shù)據(jù)集前后信息熵的變化值裸卫，然后選擇信息熵變化幅度最大的那個特征，來優(yōu)先作為數(shù)據(jù)集劃分依據(jù)纽竣。即選擇信息增益最大的特征作為分裂節(jié)點墓贿。

比如，一個盒子里共有紅蜓氨、白聋袋、黑、藍4種顏色的球共有16個穴吹，其中紅球2個幽勒，白球2個，黑球4個港令，藍球8個啥容。紅球和黑球的體積一樣棘钞，都為1個單位；白球和藍球的體積一樣干毅，都為2個單位宜猜。紅球、白球和黑球的質(zhì)量一樣硝逢，都是1個單位姨拥，藍球的質(zhì)量為2個單位。

我們應(yīng)該優(yōu)先選擇體積這個特征還是優(yōu)先選擇質(zhì)量這個特征來作為數(shù)據(jù)集劃分的依據(jù)呢渠鸽？根據(jù)前面介紹的結(jié)論叫乌，我們先計算基礎(chǔ)信息熵，即劃分數(shù)據(jù)集前的信息熵徽缚。從已知信息容易知道憨奸，紅球、白球凿试、黑球排宰、藍球出現(xiàn)的概率分別為2/16，2/16那婉，4/16板甘，8/16，因此基礎(chǔ)信息熵為：

接著使用體積來劃分數(shù)據(jù)集详炬，此時會劃分出兩個數(shù)據(jù)集盐类，第一個子數(shù)據(jù)集里是紅球和黑球，第二個子數(shù)據(jù)集里是白球和藍球呛谜，我們計算這種劃分方式的信息熵在跳。其中，第一個子數(shù)據(jù)集里隐岛，紅球2個猫妙，黑球4個，其概率分別為2/6礼仗，4/6吐咳，因此第一個子數(shù)據(jù)集的信息熵為：

第二個子數(shù)據(jù)集里，白球2個元践，藍球8個韭脊，其概率分別是2/10，8/10单旁，因此第二個子數(shù)據(jù)集的信息熵為：

因此沪羔，使用體積來劃分數(shù)據(jù)集后，其信息熵為，其信息增益為蔫饰，如下圖(a)所示：

figure7_2.png

下面來討論信息增益的物理意義。我們以概率P(x)為橫坐標良瞧，以信息熵Entropy為縱坐標陪汽，把信息熵和概率的函數(shù)關(guān)系，在二維坐標軸上畫出來褥蚯，如下圖所示：

figure7_3.png

熵是熱力學中表征物質(zhì)狀態(tài)的參量之一窥浪，其物理意義是體系混亂程度的度量，被香農(nóng)借用過來累盗，作為信息量的度量寒矿。著名的信息熵增原理是這樣描述的：熵增原理就是孤立熱力學系統(tǒng)的熵不減少，總是增大或者不變若债。一個孤立的系統(tǒng)不可能朝低熵的狀態(tài)發(fā)展符相，即不會變的有序。

用白話講就是蠢琳，如果沒有外力的作用啊终，這個世界將是越來越無序的。人活著傲须，在于盡量讓熵變低蓝牲，即讓世界變得更有序，降低不確定性泰讽。當我們在消費資源時例衍，是一個增熵的過程。我們把有序的事物變成了無序的垃圾已卸。例如我們在寫書或者看書的過程佛玄，可以理解為減熵的過程。我們通過寫作和閱讀累澡，減少了不確定的信息梦抢，從而實現(xiàn)了減熵的過程。人生價值的實現(xiàn)愧哟，在于消費資源（增熵過程）來獲取能量奥吩，經(jīng)過自己的勞動付出（減熵過程），讓世界變得更加純凈有序蕊梧，信息增益（減熵量 - 增熵量）即是衡量人生價值的尺度霞赫。希望我們每個人在暮年之時，回首往事望几，能自信地說绩脆，我給這個世界帶來的信息增益是正數(shù)，且已經(jīng)盡力做到最大了。

2.決策樹的創(chuàng)建

決策樹的構(gòu)建過程靴迫，就是從訓練數(shù)據(jù)集中歸納出一組分類規(guī)則惕味，使它與訓練數(shù)據(jù)矛盾較小的同時具有較強的泛化能力。有了信息增益來量化地選擇數(shù)據(jù)集的劃分特征玉锌，使決策樹的創(chuàng)建過程變得容易了名挥。決策樹的創(chuàng)建基本上分為以下幾個步驟：
（1）計算數(shù)據(jù)集劃分前的信息熵。
（2）遍歷所有未作為劃分條件的特征主守，分別計算根據(jù)每個特征劃分數(shù)據(jù)集后的信息熵禀倔。
（3）選擇信息增益最大的特征，并使用這個特征作為數(shù)據(jù)劃分節(jié)點來劃分數(shù)據(jù)参淫。
（4）遞歸地處理被劃分后的所有子數(shù)據(jù)集救湖，從未被選擇的特征里繼續(xù)選擇最優(yōu)數(shù)據(jù)劃分特征來劃分子數(shù)據(jù)集。

問題來了涎才，遞歸過程什么時候結(jié)束呢鞋既？一般來講，有兩個終止條件：一是所有的特征都用完了耍铜，即沒有新的特征可以用來進一步劃分數(shù)據(jù)集邑闺。二是劃分后的信息增益足夠小了，這個時候就可以停止遞歸劃分了棕兼。針對這個停止條件楼肪，需要事先選擇信息增益的閾值來作為結(jié)束遞歸地條件叮阅。

使用信息增益作為特征選擇指標的決策樹構(gòu)建算法踩窖，稱為ID3算法挠蛉。

1.離散化
如果一個特征是連續(xù)值怎么辦呢？就像開頭我們舉過的例子，假如我們有個精力測試儀器掏缎，測出來的是一個0到100的數(shù)字，這是個連續(xù)值沪哺，這個時候怎么用決策樹來建模呢酌儒？答案是：離散化。我們需要對數(shù)據(jù)進行離散化處理。例如：當精力指數(shù)小于等于40時標識為低籍滴，當大于40且小于等于70時標識為中酪夷，當大于70時標識為高。經(jīng)過離散處理后孽惰，就可以用來構(gòu)建決策樹了晚岭。要離散化成幾個類別，這個往往和具體的業(yè)務(wù)相關(guān)勋功。

2.正則項
最大化信息增益來選擇特征坦报，在決策樹的構(gòu)建過程中，容易造成優(yōu)先選擇類別最多的特征來進行分類狂鞋。舉一個極端的例子片择，我們把某個產(chǎn)品的唯一標識符ID作為特征之一加入到數(shù)據(jù)集中，那么構(gòu)建決策樹時骚揍，就會優(yōu)先選擇產(chǎn)品ID來作為劃分特征字管，因為這樣劃分出來的數(shù)據(jù)，每個葉子節(jié)點只有一個樣本疏咐，劃分后的子數(shù)據(jù)集最“純凈”纤掸，其信息增益最大。

這不是我們希望看到的結(jié)果浑塞。解決辦法是計算劃分后的子數(shù)據(jù)集的信息熵時借跪，加上一個與類別個數(shù)成正比的正則項來作為最后的信息熵。這樣當算法選擇的某個類別較多的特征酌壕，使信息熵較小時掏愁，由于受到類別個數(shù)的正則項懲罰，導致最終的信息熵也比較大。這樣通過合適的參數(shù)辛掠，可以使算法訓練得到某種程度的平衡。
另外一個解決辦法是使用信息增益比來作為特征選擇的標準猩谊。具體可以參考擴展部分的內(nèi)容墙牌。

3.基尼不純度
我們知道喜滨，信息熵是衡量信息不確定性的指標，實際上也是衡量信息“純度”的指標焰情。除此之外，基尼不純度（Gini impurity）也是衡量信息不純度的指標验游，其計算公式是：

其中，是樣本屬于這個類別的概率。如果所有的樣本都屬于一個類別场躯，此時，則签舞，即數(shù)據(jù)不純度最低，純度最高。我們以概率作為橫坐標屹培，以這個類別的基尼不純度作為縱坐標蓄诽，在坐標軸上畫出其函數(shù)關(guān)系，如圖所示：

figure7_4.png

3.剪枝算法

使用決策樹模型擬合數(shù)據(jù)時次乓，容易造成過擬合。解決過擬合的方法是對決策樹進行剪枝處理杏慰。決策樹的剪枝有兩種思路：前剪枝（Pre-Pruning）和后剪枝（Post-Pruning）。

1.前剪枝（Pre-Pruning）
前剪枝是在構(gòu)造決策樹的同時進行剪枝朝扼。在決策樹的構(gòu)建過程中榛斯，如果無法進一步降低信息熵驮俗，就會停止創(chuàng)建分支。為了避免過擬合索烹，可以設(shè)定一個閾值，即使可以繼續(xù)降低信息熵瓣戚，也停止繼續(xù)創(chuàng)建分支。這種方法稱為前剪枝仑嗅。還有一些簡單的前剪枝方法，如限制葉子節(jié)點的樣本個數(shù)脖捻，當樣本個數(shù)小于一定的閾值時，即不再繼續(xù)創(chuàng)建分支摩疑。

2.后剪枝（Post-Pruning）
后剪枝是指決策樹構(gòu)建完成之后進行剪枝雷袋。剪枝的過程是對擁有同樣父節(jié)點的一組節(jié)點進行檢查寨腔，判斷如果將其合并倚搬，信息熵的增加量是否小于某一閾值捅僵。如果小于閾值，則這一組節(jié)點可以合并成一個節(jié)點馒闷。后剪枝是目前較普遍的做法。后剪枝的過程是刪除一些子樹疏虫，然后用子樹的根節(jié)點代替官扣，來作為新的葉子結(jié)點哼御。這個新的葉子節(jié)點所標識的類別通過大多數(shù)原則來確定，即把這個葉子節(jié)點里樣本最多的類別液肌，作為這個葉子節(jié)點的類別谤祖。

后剪枝算法有很多種，其中常用的一種稱為降低錯誤率剪枝法（Reduced-Error Pruning）。其思路是锋华，自底向上，從已經(jīng)構(gòu)建好的完全決策樹中找出一棵子樹，然后用子樹的根代替這棵子樹坊罢，作為新的葉子節(jié)點续担。葉子節(jié)點所標識的類別通過大多數(shù)原則來確定。這樣就構(gòu)建出了一個新的簡化版的決策樹活孩。然后使用交叉驗證數(shù)據(jù)集來檢測這棵簡化版的決策樹物遇，看其錯誤率是否降低了。如果錯誤率降低了憾儒，則可以使用這個簡化版的決策樹代替完全決策樹询兴。否則诗舰，還是采用原來的決策樹变姨。通過遍歷所有的子樹耕驰，直到針對交叉驗證數(shù)據(jù)集夫嗓，無法進一步降低錯誤率為止。

2.決策樹算法參數(shù)

scikit-learn使用sklearn.tree.DecisionTreeClassifier類來實現(xiàn)決策樹分類算法。其中幾個典型的參數(shù)如下：

• criterion：特征選擇算法苟耻。一種是基于信息熵，另外一種是基于基尼不純度阻课。研究表明旺上，這兩種算法的差異性不大垒棋，對模型準確性沒有太大的影響甜无。相對而言，信息熵運算效率會低一些难述，因為它有對數(shù)運算彼棍。
• splitter：創(chuàng)建決策樹分支的選項穿肄。一種是選擇最優(yōu)的分支創(chuàng)建原則屑彻。另外一種是從排名靠前的特征中熟空，隨機選擇一個特征來創(chuàng)建分支，這個方法和正則項的效果類似努潘，可以避免過擬合布卡。
• max_depth：指定決策樹的最大深度雨让。通過指定該參數(shù)，用來解決模型過擬合問題忿等。
• min_samples_split：這個參數(shù)指定能創(chuàng)建分支的數(shù)據(jù)集的大小宫患，默認是2。如果一個節(jié)點的數(shù)據(jù)樣本個數(shù)小于這個數(shù)值这弧，則不再創(chuàng)建分支。這就是上面介紹的前剪枝的一種方法虚汛。
• min_samples_leaf：葉子節(jié)點的最小樣本數(shù)量匾浪，葉子節(jié)點的樣本數(shù)量必須大于等于這個值。這也是上面介紹的另一種前剪枝的方法卷哩。
• max_leaf_nodes：最大葉子節(jié)點個數(shù)蛋辈，即數(shù)據(jù)集最多能劃分成幾個類別。
• min_impurity_split：信息增益必須大于等于這個閾值才可以繼續(xù)分支将谊，否則不創(chuàng)建分支冷溶。
  從這些參數(shù)可以看出，scikit-learn有一系列的參數(shù)用來控制決策樹的生成過程尊浓，從而解決過擬合問題逞频。其他參數(shù)請參閱scikit-learn的官方文檔。

3.實例：預(yù)測泰坦尼克號幸存者

眾所周知栋齿，泰坦尼克號是歷史上最嚴重的一起海難事故苗胀。我們通過決策樹模型襟诸，來預(yù)測哪些人可能成為幸存者。數(shù)據(jù)集下載https://www.kaggle.com/c/titanic基协。

數(shù)據(jù)集中總共有兩個文件歌亲，都是csv格式的數(shù)據(jù)。其中澜驮，train.csv是訓練數(shù)據(jù)集陷揪，包含已標注的訓練樣本數(shù)據(jù)。test.csv是模型進行幸存者預(yù)測的測試數(shù)據(jù)杂穷。我們的任務(wù)就是根據(jù)train.csv里的數(shù)據(jù)訓練出決策樹模型悍缠，然后使用該模型來預(yù)測test.csv里的數(shù)據(jù)，并查看模型的預(yù)測效果亭畜。

1.數(shù)據(jù)分析

train.csv是一個892行扮休、12列的數(shù)據(jù)表格。意味著我們有891個訓練樣本（扣除表頭）拴鸵，每個樣本有12個特征玷坠。我們需要先分析這些特征，以便決定哪些特征可以用來進行模型訓練劲藐。

• PassengerId：乘客的ID號八堡，這個是順序編號，用來唯一地標識一名乘客聘芜。這個特征和幸存與否無關(guān)兄渺，丟棄這個特征。
• Survived：1表示幸存汰现，0表示遇難挂谍。這是標注數(shù)據(jù)。
• Pclass：倉位等級瞎饲。這是個很重要的特征口叙，高倉位的乘客能更快的到達甲板，從而更容易獲救嗅战。
• Name：乘客的名字妄田，這個特征和幸存與否無關(guān)，丟棄這個特征驮捍。
• Sex：乘客性別疟呐。由于救生艇數(shù)量不夠，船長讓婦女和兒童先上救生艇东且。所以這也是個很重要的特征启具。
• Age：乘客的年齡。兒童會優(yōu)先上救生艇珊泳，身強力壯者幸存概率也會高一些富纸。所以這也是個很重要的特征囤踩。
• SibSp：兄弟姐妹同在船上的數(shù)量。
• Parch：同船的父輩人員的數(shù)量晓褪。
• Ticket：乘客的票號堵漱。這個特征和幸存與否無關(guān)，丟棄這個特征涣仿。
• Fare：乘客的體熱指標勤庐。
• Cabin：乘客所在的船艙號。實際上這個特征和幸存與否有一定的關(guān)系好港，比如最早被水淹沒的船艙位置愉镰，其乘客的幸存概率要低一些。但由于這個特征有大量的丟失數(shù)據(jù)钧汹，而且沒有更多的數(shù)據(jù)來對船艙進行歸類丈探，因此我們丟棄這個特征的數(shù)據(jù)。
• Embarked：乘客登船的港口拔莱。我們需要把港口數(shù)據(jù)轉(zhuǎn)換為數(shù)值類型的數(shù)據(jù)碗降。

我們需要加載csv數(shù)據(jù)。并做一些預(yù)處理塘秦，包括：

• 提取Survived列的數(shù)據(jù)作為模型的標注數(shù)據(jù)讼渊。
• 丟棄不需要的特征數(shù)據(jù)。
• 對數(shù)據(jù)進行轉(zhuǎn)換尊剔，以便模型處理爪幻。比如把性別數(shù)據(jù)轉(zhuǎn)換為0和1.
• 處理缺失的數(shù)據(jù)。比如年齡這個特征须误，有很多缺失的數(shù)據(jù)挨稿。

Pandas是完成這些任務(wù)的理想軟件包，我們先把數(shù)據(jù)從文件里讀取出來：

import pandas as pd
def read_dataset(fname):
    # 指定第一列作為行索引
    data = pd.read_csv(fname,index_col=0)
    # 丟棄無用的數(shù)據(jù)
    data.drop(['Name','Ticket','Cabin'],axis=1,inplace=True)
    # 處理性別數(shù)據(jù)
    data['Sex'] = (data['Sex']=='male').astype('int')
    # 處理登船港口數(shù)據(jù)
    labels = data['Embarked'].unique().tolist()
    data['Embarked'] = data['Embarked'].apply(lambda n:labels.index(n))
    # 處理缺失數(shù)據(jù)
    data = data.fillna(0)
    return data

train = read_dataset('../titanic/train.csv')
train.head()

處理完的數(shù)據(jù)如下：

figure7_5.png

2.模型訓練

首先需要把Survived列提取出來作為標簽京痢，并在原數(shù)據(jù)集中刪除這一列奶甘。然后把數(shù)據(jù)集劃分成訓練數(shù)據(jù)集和交叉驗證數(shù)據(jù)集。

from sklearn.model_selection import train_test_split
y = train['Survived'].values
X = train.drop(['Survived'],axis=1).values
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2)
print('train dataset: {0}; test dataset: {1}'.format(X_train.shape,X_test.shape))

輸出如下：

train dataset: (712, 7); test dataset: (179, 7)

接著历造，使用scikit-learn的決策樹模型對數(shù)據(jù)集進行擬合，并觀察模型的性能：

from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier()
clf.fit(X_train,y_train)
train_score = clf.score(X_train,y_train)
test_score = clf.score(X_test,y_test)
print('train score: {0}; test score: {1}'.format(train_score,test_score))

輸出如下：

train score: 0.9845505617977528; test score: 0.7877094972067039

從輸出結(jié)果可以看出船庇，針對訓練樣本評分很高吭产，但是針對交叉驗證數(shù)據(jù)集評分較低，兩者差距較大鸭轮。沒錯臣淤，這是過擬合現(xiàn)象。解決決策樹過擬合的方法是剪枝窃爷，包括前剪枝和后剪枝邑蒋。不幸的是scikit-learn不支持后剪枝姓蜂，但是提供了一系列模型參數(shù)進行前剪枝。例如医吊，可以通過max_depth參數(shù)限定決策樹的深度钱慢，當決策樹達到限定的深度時，就不再進行分裂了卿堂。這樣就可以在一定程度上避免過擬合束莫。

3.優(yōu)化模型參數(shù)

我們可以選擇一系列的參數(shù)值，然后分別計算指定參數(shù)訓練出來的模型的評分草描。還可以把參數(shù)值和模型評分通過圖形畫出來览绿，以便直觀地發(fā)現(xiàn)兩者之間的關(guān)系。

這里以限制決策樹深度max_depth為了來介紹模型參數(shù)的優(yōu)化過程穗慕。我們先創(chuàng)建一個函數(shù)饿敲，它使用不同的max_depth來訓練模型，并計算模型評分逛绵。

# 參數(shù)選擇 max_depth
def cv_score(d):
    clf = DecisionTreeClassifier(max_depth=d)
    clf.fit(X_train,y_train)
    tr_score = clf.score(X_train,y_train)
    cv_score = clf.score(X_test,y_test)
    return (tr_score,cv_score)

接著構(gòu)造參數(shù)范圍怀各，在這個范圍內(nèi)分別計算模型評分，并找出評分最高的模型所對應(yīng)的參數(shù)暑脆。

import numpy as np
depths = range(2,15)
scores = [cv_score(d) for d in depths]
tr_scores = [s[0] for s in scores]
cv_scores = [s[1] for s in scores]
best_score_index = np.argmax(cv_scores)
best_score = cv_scores[best_score_index]
best_param = depths[best_score_index]
print(scores)
print('best param: {0}渠啤； best score： {1}'.format(best_param,best_score))

輸出如下：

best param: 3； best score： 0.8435754189944135

可以看到添吗，針對模型深度這個參數(shù)沥曹，最優(yōu)的值是3，其對應(yīng)的交叉驗證數(shù)據(jù)集評分為0.84碟联。（你的結(jié)果可能跟我不一樣妓美，因為每次劃分數(shù)據(jù)集都是隨機的）我們還可以把模型參數(shù)和對應(yīng)的模型評分畫出來，更直觀地觀察其變化規(guī)律鲤孵。

import matplotlib.pyplot as plt
plt.figure(figsize=(6,4),dpi=144)
plt.grid()
plt.xlabel('max depth of decision tree')
plt.ylabel('score')
plt.plot(depths,cv_scores,'.g-',label='cross-validation score')
plt.plot(depths,tr_scores,'.r--',label='training score')
plt.legend()

輸出如下：

figure7_6.png

使用同樣的方式壶栋，我們可以考察參數(shù)min_impurity_split。這個參數(shù)用來指定信息熵或基尼不純度的閾值普监。當決策樹分裂后贵试，其信息增益低于這個閾值，則不再分裂凯正。

# 訓練模型毙玻，并計算評分
def cv_score(val):
    clf = DecisionTreeClassifier(criterion='gini', min_impurity_decrease=val)
    clf.fit(X_train, y_train)
    tr_score = clf.score(X_train, y_train)
    cv_score = clf.score(X_test, y_test)
    return (tr_score, cv_score)

# 指定參數(shù)范圍，分別訓練模型廊散，并計算評分
values = np.linspace(0, 0.005, 50)
scores = [cv_score(v) for v in values]
tr_scores = [s[0] for s in scores]
cv_scores = [s[1] for s in scores]

# 找出評分最高的模型參數(shù)
best_score_index = np.argmax(cv_scores)
best_score = cv_scores[best_score_index]
best_param = values[best_score_index]
print('best param: {0}; best score: {1}'.format(best_param, best_score))

# 畫出模型參數(shù)與模型評分的關(guān)系
plt.figure(figsize=(10, 6), dpi=144)
plt.grid()
plt.xlabel('threshold of entropy')
plt.ylabel('score')
plt.plot(values, cv_scores, '.g-', label='cross-validation score')
plt.plot(values, tr_scores, '.r--', label='training score')
plt.legend()

輸出如下：

best param: 0.002653061224489796; best score: 0.8324022346368715

figure7_7.png

這里把[0,0.005]等分50份桑滩，以每個等分點作為信息增益閾值來訓練一次模型≡识茫可以看到运准，訓練數(shù)據(jù)集的評分急速下降幌氮，且訓練評分和測試評分都保持較低水平，說明模型欠擬合胁澳。我們可以把決策樹特征選擇的基尼不純度改為信息熵该互，即把參數(shù)criterion的值改為'entropy'觀察圖形的變化。

...
clf = DecisionTreeClassifier(criterion='entropy', min_impurity_decrease=val)
...

figure7_7_2.png

4.模型參數(shù)選擇工具包

上面的模型參數(shù)優(yōu)化過程存在兩個問題听哭。其一慢洋，數(shù)據(jù)不穩(wěn)定，即數(shù)據(jù)集每次都是隨機劃分的陆盘，選擇出來的最優(yōu)參數(shù)在下一次運行時就不是最優(yōu)的了普筹。其二，不能一次選擇多個參數(shù)隘马，例如太防，想要考察max_depth和min_samples_leaf兩個結(jié)合起來的最優(yōu)參數(shù)就無法實現(xiàn)。

問題一的原因是酸员，每次把數(shù)據(jù)集劃分為訓練樣本和交叉驗證樣本時蜒车，是隨機劃分的，這樣導致每次的訓練數(shù)據(jù)集是有差異的幔嗦，訓練出來的模型也有差異酿愧。解決這個問題的方法是多次計算，求平均值邀泉。具體來講嬉挡，就是針對模型的某個特定的參數(shù)，多次劃分數(shù)據(jù)集汇恤，多次訓練模型庞钢，計算出這個參數(shù)對應(yīng)的模型的最低評分、最高評分以及評價評分因谎。問題二的解決辦法比較簡單基括，把代碼再優(yōu)化一下，能處理多個參數(shù)組合即可财岔。

所幸风皿，我們不需要從頭實現(xiàn)這些代碼。scikit-learn在sklearn.model_selection包里提供了大量模型選擇和評估工具供我們使用匠璧。針對以上問題桐款，可以使用GridSearchCV類來解決。下面先看一下使用GridSearchCV選擇一個參數(shù)的最優(yōu)值患朱。

from sklearn.model_selection import GridSearchCV
thresholds = np.linspace(0,0.5,50)
param_grid = {'min_impurity_split':thresholds}
clf = GridSearchCV(DecisionTreeClassifier(),param_grid,cv=5)
clf.fit(X,y)
print("best param: {0}\nbest score: {1}".format(clf.best_params_,clf.best_score_))
plot_curve(thresholds,clf.cv_results_,xlabel='gini thresholds')

輸出如下：

best param: {'min_impurity_split': 0.21428571428571427}
best score: 0.8215488215488216

其中關(guān)鍵的參數(shù)是param_grid鲁僚，它是一個字典炊苫，鍵對應(yīng)的值是一個列表裁厅。GridSearchCV會枚舉列表里的所有值來構(gòu)建模型冰沙，最終得出指定參數(shù)值的平均評分及標準差。另外一個關(guān)鍵參數(shù)是cv执虹，它用來指定交叉驗證數(shù)據(jù)集的生成規(guī)則拓挥，代碼中的cv=5，表示每次計算都把數(shù)據(jù)集分成5份袋励，拿其中一份作為交叉驗證數(shù)據(jù)集侥啤，其他的作為訓練數(shù)據(jù)集。最終得出的最優(yōu)參數(shù)及最優(yōu)評分保存在clf.best_params_和clf.best_score_里茬故。此外盖灸，clf.cv_results_保存了計算過程的所有中間結(jié)果。我們可以拿這個數(shù)據(jù)來畫出模型參數(shù)與模型評分的關(guān)系圖磺芭，如下所示赁炎。

def plot_curve(train_sizes,cv_results,xlabel):
    train_scores_mean = cv_results['mean_train_score']
    train_scores_std = cv_results['std_train_score']
    test_scores_mean = cv_results['mean_test_score']
    test_scores_std = cv_results['std_test_score']
    plt.figure(figsize=(6,4),dpi=144)
    plt.title('parameters turning')
    plt.grid()
    plt.xlabel(xlabel)
    plt.ylabel('score')
    plt.fill_between(train_sizes,
                     train_scores_mean-train_scores_std,
                     train_scores_mean+train_scores_std,
                     alpha=0.1,color='r')
    plt.fill_between(train_sizes,
                     test_scores_mean-test_scores_std,
                     test_scores_mean+test_scores_std,
                     alpha=0.1,color='g')
    plt.plot(train_sizes,train_scores_mean,'.--',color='r',label='Training score')
    plt.plot(train_sizes,test_scores_mean,'.-',color='g',label='Cross-validation score')
    plt.legend(loc='best')

figure7_8.png

接下來看一下如何在多組參數(shù)之間選擇最優(yōu)的參數(shù)組合：

from sklearn.model_selection import GridSearchCV
entropy_thresholds = np.linspace(0,1,50)
gini_thresholds = np.linspace(0,0.5,50)
param_grid = [{'criterion':['entropy'],'min_impurity_split':entropy_thresholds},
              {'criterion':['gini'],'min_impurity_split':gini_thresholds},
              {'max_depth':range(2,10)},
              {'min_samples_split':range(2,30,2)}]
clf=GridSearchCV(DecisionTreeClassifier(),param_grid,cv=5)
clf.fit(X,y)
print('best param: {0}\nbest score: {1}'.format(clf.best_params_,clf.best_score_))

輸出如下：

best param: {'criterion': 'entropy', 'min_impurity_split': 0.5306122448979591}
best score: 0.8260381593714927

代碼關(guān)鍵部分還是param_grid參數(shù)，它是一個列表钾腺，列表中的每個元素都是字典徙垫。例如：針對列表中的第一個字典，選擇信息熵作為決策樹特征選擇的判斷標準放棒，同時其閾值范圍是[0,1]之間分了50等份姻报。GridSearchCV會針對列表中的每個字典進行迭代，最終比較列表中每個字典所對應(yīng)的參數(shù)組合间螟，選擇出最優(yōu)的參數(shù)吴旋。關(guān)于GridSearchCV的更多詳情可參考官方文檔。

最后基于好奇寒亥，使用最優(yōu)參數(shù)的決策樹到底是什么樣呢邮府？我們可以使用sklearn.tree.export_graphviz()函數(shù)把決策樹模型導出到文件中，然后使用graphviz工具包生成決策樹示意圖溉奕。

from sklearn.tree import export_graphviz
clf = DecisionTreeClassifier(criterion='entropy', min_impurity_split=0.5306122448979591)
clf.fit(X_train, y_train)
train_score = clf.score(X_train, y_train)
test_score = clf.score(X_test, y_test)
print('train score: {0}; test score: {1}'.format(train_score, test_score))

columns = train.columns[1:]
# 導出 titanic.dot 文件
with open("E:/titanic.dot", 'w') as f:
    f = export_graphviz(clf, out_file=f,feature_names=columns)

# 1. conda安裝 graphviz ：conda install python-graphviz 
# 2. 運行 `dot -Tpng titanic.dot -o titanic.png` 
# 3. 在當前目錄查看生成的決策樹 titanic.png

我們最優(yōu)參數(shù)的決策樹就長這個樣子：

titanic.png

4.拓展閱讀

1.熵和條件熵

在決策樹創(chuàng)建過程中褂傀，我們會計算以某個特征創(chuàng)建分支后的子數(shù)據(jù)集的信息熵。用數(shù)學語言描述實際上是計算條件熵加勤，即滿足某個條件的信息熵仙辟。

關(guān)于信息熵和條件熵的相關(guān)概念，可以閱讀吳軍老師的《數(shù)學之美》里"信息的度量和作用"一文鳄梅〉《數(shù)學之美》這本書，吳軍老師用平實的語言戴尸，把復(fù)雜的數(shù)學概念解釋的入木三分粟焊，即使你只有高中的數(shù)學水平，也可以領(lǐng)略到數(shù)學的“優(yōu)雅”和“威力”。

2.決策樹的構(gòu)建算法

本文重點介紹的決策樹構(gòu)建算法是ID3算法项棠，它是1986年由Ross Quinlan提出的悲雳。1993年，該算法作者發(fā)布了新的決策樹構(gòu)建算法C4.5香追，作為ID3算法的改進合瓢，主要體現(xiàn)在：

• 增加了對連續(xù)值的處理，方法是使用一個閾值作為連續(xù)值的劃分條件透典，從而把數(shù)據(jù)離散化晴楔。
• 自動處理特征值缺失問題，處理方法是直接把這個特征拋棄峭咒，不參與計算信息增益比税弃。
• 使用信息增益比作為特征選擇標準。
• 采用后剪枝算法處理過擬合凑队，即在決策樹創(chuàng)建完成之后钙皮，再通過合并葉子節(jié)點的方式進行剪枝。

此后顽决，該算法作者又發(fā)布了改進的商業(yè)版本C5.0短条，它運算效率更高，使用內(nèi)存更小才菠，創(chuàng)建出來的決策樹更小茸时，并且準確性更高，適合大數(shù)據(jù)集的決策樹構(gòu)建赋访。

除了前面介紹的使用基尼不純度來構(gòu)建決策樹的CART算法之外可都，還有其他知名的決策樹構(gòu)建算法，如CHAID算法蚓耽、MARS算法等渠牲。這里不再詳述。

5.集合算法

集合算法（Ensemble）是一種元算法（Meta-algorithm）步悠，它利用統(tǒng)計學采樣原理签杈，訓練出成百上千個不同的算法模型。當需要預(yù)測一個新樣本時鼎兽，使用這些模型分別對這個樣本進行預(yù)測答姥，然后采樣少數(shù)服從多數(shù)的原則，決定新樣本的類別谚咬。集合算法可以有效地解決過擬合問題鹦付。在scikit-learn里，所有的集合算法都實現(xiàn)在sklearn.ensemble包里择卦。

1.自助聚合算法Bagging

自助聚合（Bagging敲长，Bootstrap Aggregating的縮寫）的核心思想是郎嫁，采用有放回的采樣規(guī)則，從m個樣本的原數(shù)據(jù)集里進行n次采樣（n<=m）祈噪，構(gòu)成一個包含n個樣本的新訓練數(shù)據(jù)集行剂。重復(fù)這個過程B次，得到B個模型钳降，當有新樣本需要預(yù)測時，拿這B個模型分別對這個樣本進行預(yù)測腌巾，然后采用投票方式（回歸問題）得到新樣本的預(yù)測值遂填。

所謂的有放回采樣規(guī)則是指，在m個數(shù)據(jù)集里澈蝙，隨機取出一個樣本放到新數(shù)據(jù)集里吓坚，然后把這個樣本放回到原數(shù)據(jù)集里，繼續(xù)隨機采樣灯荧，直到到達采樣次數(shù)n為止礁击。由此可見，隨機采樣出的數(shù)據(jù)集里可能有重復(fù)數(shù)據(jù)逗载，并且原數(shù)據(jù)集的每一個數(shù)據(jù)不一定都出現(xiàn)在新數(shù)據(jù)集里哆窿。

單一模型往往容易對數(shù)據(jù)噪聲敏感，從而造成高方差（High Variance）厉斟。自助聚合算法可以降低對數(shù)據(jù)噪聲的敏感性挚躯，從而提高模型準確性和穩(wěn)定性。這種方法不需要額外的輸入擦秽，只是簡單地對同一個數(shù)據(jù)集訓練出多個模型即可實現(xiàn)码荔。當然這并不是說沒有代價，自助聚合算法一般會增加模型訓練的計算量感挥。

在scikit-learn里缩搅，由BaggingClassifier類和BaggingRegressor類分別實現(xiàn)了分類和回歸的Bagging算法。

2.正向激勵算法Boosting

正向激勵算法（Boosting）的基本原理是触幼，初始化時硼瓣，針對有m個訓練樣本的數(shù)據(jù)集，給每個樣本都分配一個初始權(quán)重置谦，然后使用這個帶有權(quán)重的數(shù)據(jù)集來訓練模型巨双。訓練出模型之后，針對這個模型預(yù)測錯誤的那些樣本霉祸，增加其權(quán)重筑累，然后拿這個更新過權(quán)重的數(shù)據(jù)集來訓練出一個新的模型。重復(fù)這個過程B次丝蹭，就可以訓練出B個模型慢宗。

Boosting算法和Bagging算法的區(qū)別如下：

• 采樣規(guī)則不同：Bagging算法是采樣有放回的隨機采樣規(guī)則。而Boosting算法是使用增加預(yù)測錯誤樣本權(quán)重的方法，相當于加強了對預(yù)測錯誤的樣本的學習力度镜沽，從而提高模型的準確性敏晤。
• 訓練方式不同：Bagging算法可以并行訓練多個模型。而Boosting算法只能串行訓練缅茉，因為下一個模型依賴上一個模型的預(yù)測結(jié)果嘴脾。
• 模型權(quán)重不同：Bagging算法訓練出來的B個模型的權(quán)重是一樣的。而Boosting算法訓練出來的B個模型本身帶有權(quán)重信息蔬墩，在對新樣本進行預(yù)測時译打，每個模型的權(quán)重是不一樣的席函。單個模型的權(quán)重由模型訓練的效果來決定浸策，即準確性高的模型權(quán)重更高。

Boosting算法有很多種實現(xiàn)谎砾，其中最著名的是AdaBoosting算法樟插。在scikit-learn里由AdaBoostingClassifier類和AdaBoostingRegression類分別實現(xiàn)Boosting分類和Boosting回歸韵洋。

3.隨機森林

隨機森林（RF，Random Forest）在自助聚合算法（Bagging）的基礎(chǔ)上更進一步黄锤，對特征應(yīng)用自助聚合算法搪缨。即，每次訓練時鸵熟，不拿所有的特征來訓練勉吻，而是隨機選擇一個特征的子集來進行訓練。隨機森林算法有兩個關(guān)鍵參數(shù)旅赢，一是構(gòu)建的決策樹的個數(shù)t齿桃，二是構(gòu)建單棵決策樹特征的個數(shù)f。

假設(shè)煮盼，針對一個有m個樣本短纵、n個特征的數(shù)據(jù)集，則其算法原理如下：
（1）單棵決策樹的構(gòu)建

• 采用有放回采樣僵控，從原數(shù)據(jù)集中經(jīng)過m次采樣香到，獲取到一個m個樣本的數(shù)據(jù)集（這個數(shù)據(jù)集里可能有重復(fù)的樣本）
• 從n個特征里，采用無放回采樣規(guī)則报破，從中取出f個特征作為輸入特征悠就。
• 重復(fù)上述過程t次，構(gòu)建出t棵決策樹充易。

（2）隨機森林的分類結(jié)果
生成t棵決策樹之后梗脾，對于每個新的測試樣例，集合多棵決策樹的預(yù)測結(jié)果來作為隨機森林的預(yù)測結(jié)果盹靴。具體為炸茧，如果是回歸問題瑞妇，取t棵決策樹的預(yù)測值的平均值作為隨機森林的預(yù)測結(jié)果；如果是分類問題梭冠，采取少數(shù)服從多數(shù)的原則辕狰，取單棵決策樹預(yù)測最多的那個類別作為隨機森林的分類結(jié)果。

思考：為什么隨機森林要選取特征的子集來構(gòu)建決策樹控漠？
假如某個輸入特征對預(yù)測結(jié)果是強關(guān)聯(lián)的蔓倍，那么如果選擇全部的特征來構(gòu)建決策樹，這個特征都會體現(xiàn)在所有的決策樹里面盐捷。由于這個特征和預(yù)測結(jié)果強關(guān)聯(lián)偶翅，會造成所有的決策樹都強烈地反映這個特征的“傾向性”，從而導致無法很好地解決過擬合問題毙驯。我們在討論線性回歸算法時，通過增加正則項來解決過擬合灾测，它的原理就是確保每個特征都對預(yù)測結(jié)果有少量的貢獻爆价，從而避免單個特征對預(yù)測結(jié)果有過大貢獻導致的過擬合問題。這里的原理是一樣的媳搪。

在scikit-learn里由RandomForestClassifier類和RandomForestRegression類分別實現(xiàn)隨機森林的分類算法和隨機森林的回歸算法铭段。

4.ExtraTrees算法

ExtraTrees，叫做極限樹或者極端隨機樹秦爆。隨機森林在構(gòu)建決策樹的過程中序愚，會使用信息熵或者基尼不純度，然后選擇信息增益最大的特征來進行分裂等限。而ExtraTrees是直接從所有特征里隨機選擇一個特征來分裂爸吮，從而避免了過擬合問題。

在scikit-learn里望门，由ExtraTreesClassifier類和ExtraTreesRegression類分別實現(xiàn)ExtraTrees的分類算法和ExtraTrees的回歸算法形娇。