基于樹（Tree based）的學(xué)習(xí)算法在數(shù)據(jù)科學(xué)競賽中是相當(dāng)常見的。這些算法給預(yù)測模型賦予了準(zhǔn)確性、穩(wěn)定性以及易解釋性共苛。和線性模型不同琼富，它們對非線性關(guān)系也能進(jìn)行很好的映射仪吧。常見的基于樹的模型有：決策樹（decision trees），隨機(jī)森林（random forest）和提升樹（boosted trees）鞠眉。

在本篇文章中薯鼠，我們將會介紹決策樹的數(shù)學(xué)細(xì)節(jié)（以及各種 Python 示例）及其優(yōu)缺點(diǎn)。你們將會發(fā)現(xiàn)它們是很簡單的械蹋，并且這些內(nèi)容是有助于理解的出皇。然而，與最好的監(jiān)督學(xué)習(xí)方法相比哗戈，它們通常是沒有競爭力的郊艘。為了克服決策樹的各種缺點(diǎn)，我們將會聚焦于各種概念（附有 Python 實(shí)例）谱醇，比如自助聚集或袋裝（Bootstrap Aggregating or Bagging）暇仲，還有隨機(jī)森林（Random Forests）。另一種廣泛使用的提升方法會在以后進(jìn)行單獨(dú)討論副渴。每種方法都包括生成多種樹奈附，這些樹被聯(lián)合起來，生成一個單一的一致性預(yù)測結(jié)果煮剧，并且經(jīng)常帶來預(yù)測精度的顯著提升斥滤。

決策樹

決策樹是一種監(jiān)督學(xué)習(xí)算法将鸵。它適用于類別和連續(xù)輸入（特征）和輸出（預(yù)測）變量∮悠模基于樹的方法把特征空間劃分成一系列矩形顶掉，然后給每一個矩形安置一個簡單的模型（像一個常數(shù)）。從概念上來講挑胸，它們是簡單且有效的痒筒。首先我們通過一個例子來理解決策樹。然后用一種正規(guī)分析方法來分析創(chuàng)建決策樹的過程茬贵〔就福考慮一個簡單的借貸公司顧客的數(shù)據(jù)集合。我們給定了所有客戶的查詢賬戶余額解藻、信用記錄老充、任職年限和先前貸款狀況。相關(guān)任務(wù)是預(yù)測顧客的風(fēng)險(xiǎn)等級是否可信螟左。該問題可以使用下列決策樹來解決：

分類和回歸樹（簡稱 CART）是 Leo Breiman 引入的術(shù)語啡浊，指用來解決分類或回歸預(yù)測建模問題的決策樹算法。它常使用 scikit 生成并實(shí)現(xiàn)決策樹： sklearn.tree.DecisionTreeClassifier 和 sklearn.tree.DecisionTreeRegressor 分別構(gòu)建分類和回歸樹胶背。

CART 模型

CART 模型包括選擇輸入變量和那些變量上的分割點(diǎn)巷嚣，直到創(chuàng)建出適當(dāng)?shù)臉洹Ｊ褂秘澙匪惴ǎ╣reedy algorithm）選擇使用哪個輸入變量和分割點(diǎn)钳吟，以使成本函數(shù)（cost function）最小化涂籽。

樹建造的結(jié)尾使用了一個預(yù)定義的停止準(zhǔn)則，比如分配到樹上每一個葉結(jié)點(diǎn)的訓(xùn)練樣本達(dá)到最小數(shù)量砸抛。

其他決策樹算法：

• ID3：Iterative Dichotomiser 3

• C4.5：ID3 算法的改進(jìn)

• CHAID：Chi-squared Automatic Interaction Detector

• MARS：決策樹的擴(kuò)展式评雌，以更好地解決數(shù)值型預(yù)測。

• 條件推斷樹

回歸樹

我們現(xiàn)在關(guān)注一下回歸樹的 CART 算法的細(xì)節(jié)直焙。簡要來說景东，創(chuàng)建一個決策樹包含兩步：

1. 把預(yù)測器空間，即一系列可能值 X_1奔誓，X_2斤吐，...，X_p 分成 J 個不同的且非重疊的區(qū)域 R_1厨喂，R_2和措，...，R_J蜕煌。

2. 對進(jìn)入?yún)^(qū)域 R_J 的每一個樣本觀測值都進(jìn)行相同的預(yù)測派阱，該預(yù)測就是 R_J 中訓(xùn)練樣本預(yù)測值的均值。

為了創(chuàng)建 J 個區(qū)域 R_1斜纪，R_2贫母，...文兑，R_J，預(yù)測器區(qū)域被分為高維度的矩形或盒形腺劣。其目的在于通過下列式子找到能夠使 RSS 最小化的盒形區(qū)域 R_1绿贞，R_2，...橘原，R_J籍铁，

其中，yhat_Rj 即是第 j 個盒形中訓(xùn)練觀測的平均預(yù)測值趾断。

鑒于這種空間分割在計(jì)算上是不可行的寨辩，因此我們常使用貪婪方法（greedy approach）來劃分區(qū)域，叫做遞歸二元分割（recursive binary splitting）歼冰。

它是貪婪的（greedy），這是因?yàn)樵趧?chuàng)建樹過程中的每一步驟耻警，最佳分割都會在每個特定步驟選定隔嫡，而不是對未來進(jìn)行預(yù)測，并選取一個將會在未來步驟中出現(xiàn)且有助于創(chuàng)建更好的樹的分隔甘穿。注意所有的劃分區(qū)域 R_j 都是矩形腮恩。為了進(jìn)行遞歸二元分割，首先選取預(yù)測器 X_j 和切割點(diǎn) s

其中 yhat_R1 為區(qū)域 R_1(j,s) 中觀察樣本的平均預(yù)測值温兼，yhat_R2 為區(qū)域 R_2(j,s) 的觀察樣本預(yù)測均值秸滴。這一過程不斷重復(fù)以搜尋最好的預(yù)測器和切分點(diǎn)，并進(jìn)一步分隔數(shù)據(jù)以使每一個子區(qū)域內(nèi)的 RSS 最小化募判。然而荡含，我們不會分割整個預(yù)測器空間，我們只會分割一個或兩個前面已經(jīng)認(rèn)定的區(qū)域届垫。這一過程會一直持續(xù)释液，直到達(dá)到停止準(zhǔn)則，例如我們可以設(shè)定停止準(zhǔn)則為每一個區(qū)域最多包含 m 個觀察樣本装处。一旦我們創(chuàng)建了區(qū)域 R_1误债、R_2、...妄迁、R_J寝蹈，給定一個測試樣本，我們就可以用該區(qū)域所有訓(xùn)練樣本的平均預(yù)測值來預(yù)測該測試樣本的值登淘。

分類樹

分類樹和回歸樹十分相似箫老，只不過它是定性地預(yù)測響應(yīng)值而非定量預(yù)測。從上文可知黔州，回歸樹對一個觀察值所預(yù)測的連續(xù)型數(shù)值就是屬于同一葉結(jié)點(diǎn)訓(xùn)練樣本觀察值的均值槽惫。但是對于分類樹來說周叮，我們所預(yù)測的類別是訓(xùn)練樣本觀察值在某區(qū)域下最常見的類別，即訓(xùn)練觀察值的模式響應(yīng)（mode response）界斜。為了達(dá)到分類目的仿耽，很多時候系統(tǒng)并不會只預(yù)測一個類別，它常常預(yù)測一組類別及其出現(xiàn)的概率各薇。

分類樹的生成和回歸樹的生成十分相似项贺。正如在回歸樹中那樣，我們一般使用遞歸性的二元分割來生成分類樹峭判。然而在分類樹中开缎，RSS 不能作為二元分割的標(biāo)準(zhǔn)。我們需要定義葉結(jié)點(diǎn)的不純度量 Q_m 來替代 RSS林螃，即一種可以在子集區(qū)域 R_1,R_2,...,R_j 度量目標(biāo)變量同質(zhì)性的方法奕删。在結(jié)點(diǎn) m 中，我們可以通過 N_m 個樣本觀察值表示一個區(qū)域 R_m 所出現(xiàn)類別的頻率疗认，第 k 個類別在第 m 個區(qū)域下訓(xùn)練所出現(xiàn)的頻率可表示為：

其中完残，I(y_i=k) 為指示函數(shù)，即如果 y_i = k横漏，則取 1谨设，否則取零。

不純性度量 Q_m 一個比較自然的方法是分類誤差率缎浇。分類誤差率描述的是訓(xùn)練觀察值在某個區(qū)域內(nèi)不屬于最常見類別的概率：

考慮到該函數(shù)不可微扎拣，因此它不能實(shí)現(xiàn)數(shù)值優(yōu)化。此外素跺，該函數(shù)在結(jié)點(diǎn)概率改變上并不敏感二蓝，因此這種分類誤差率對于生成樹十分低效。我們一般使用 Gini 指數(shù)和交叉熵函數(shù)來衡量結(jié)點(diǎn)的誤差度量指厌。

Gini 指數(shù)可以衡量 k 個類別的總方差侣夷，它一般定義為：

較小的 Gini 指數(shù)值表示結(jié)點(diǎn)包含了某個類別大多數(shù)樣本觀察值。

在信息論里面仑乌，交叉熵函數(shù)用來衡量系統(tǒng)的混亂度百拓。對于二元系統(tǒng)來說，如果系統(tǒng)包含了一個類別的所有內(nèi)容晰甚，那么它的值為零衙传，而如果兩個類別的數(shù)量一樣多，那么交叉熵達(dá)到最大為 1厕九。因此蓖捶，和 Gini 指數(shù)一樣，交叉熵函數(shù)同樣能用于度量結(jié)點(diǎn)的不純度：

和 G 一樣扁远，較小的 S 值表示區(qū)域內(nèi)結(jié)點(diǎn)包含了單個類別中的大多數(shù)觀察值俊鱼。

決策樹常見參數(shù)和概念

如果我們希望以數(shù)學(xué)的方式理解決策樹刻像，我們首先需要了解決策樹和樹型學(xué)習(xí)算法的一般概念。理解以下的術(shù)語同樣能幫助我們調(diào)整模型并闲。

• 根結(jié)點(diǎn)：表示所有數(shù)據(jù)樣本并可以進(jìn)一步劃分為兩個或多個子結(jié)點(diǎn)的父結(jié)點(diǎn)细睡。

• 分裂（Splitting）：將一個結(jié)點(diǎn)劃分為兩個或多個子結(jié)點(diǎn)的過程。

• 決策結(jié)點(diǎn)：當(dāng)一個子結(jié)點(diǎn)可進(jìn)一步分裂為多個子結(jié)點(diǎn)帝火，那么該結(jié)點(diǎn)就稱之為決策結(jié)點(diǎn)溜徙。

• 葉/終止結(jié)點(diǎn)：不會往下進(jìn)一步分裂的結(jié)點(diǎn)，在分類樹中代表類別犀填。

• 分枝/子樹：整棵決策樹的一部分蠢壹。

• 父結(jié)點(diǎn)和子結(jié)點(diǎn)：如果一個結(jié)點(diǎn)往下分裂，該結(jié)點(diǎn)稱之為父結(jié)點(diǎn)而父結(jié)點(diǎn)所分裂出來的結(jié)點(diǎn)稱之為子結(jié)點(diǎn)九巡。

• 結(jié)點(diǎn)分裂的最小樣本數(shù)：在結(jié)點(diǎn)分裂中所要求的最小樣本數(shù)量（或觀察值數(shù)量）图贸。這種方法通常可以用來防止過擬合冕广，較大的最小樣本數(shù)可以防止模型對特定的樣本學(xué)習(xí)過于具體的關(guān)系疏日，該超參數(shù)應(yīng)該需要使用驗(yàn)證集來調(diào)整。

• 葉結(jié)點(diǎn)最小樣本數(shù)：葉結(jié)點(diǎn)所要求的最小樣本數(shù)佳窑。和結(jié)點(diǎn)分裂的最小樣本數(shù)一樣，該超參數(shù)同樣也可以用來控制過擬合父能。對于不平衡類別問題來說神凑，我們應(yīng)該取較小的值，因?yàn)閷儆谳^少類別的樣本可能數(shù)量上非常少何吝。

• 樹的最大深度（垂直深度）：該超參數(shù)同樣可以用來控制過擬合問題溉委，較小的深度可以防止模型對特定的樣本學(xué)習(xí)過于具體的關(guān)系，該超參數(shù)同樣需要在驗(yàn)證集中調(diào)整爱榕。

• 葉結(jié)點(diǎn)的最大數(shù)量：葉結(jié)點(diǎn)的最大個數(shù)可以替代數(shù)的最大深度這一設(shè)定瓣喊。因?yàn)樯梢豢蒙疃葹?n 的二叉樹，它所能產(chǎn)生的最大葉結(jié)點(diǎn)個數(shù)為 2^n黔酥。

• 分裂所需要考慮的最大特征數(shù)：即當(dāng)我們搜索更好分離方案時所需要考慮的特征數(shù)量藻三，我們常用的方法是取可用特征總數(shù)的平方根為最大特征數(shù)。

分類樹的實(shí)現(xiàn)

為了展示不同的前文所述的決策樹模型跪者，我們將使用 Kaggle 上的美國收入數(shù)據(jù)集棵帽，我們都可以在 Kaggle.com 上下載該數(shù)據(jù)集。下面的代碼可以展示該數(shù)據(jù)集的導(dǎo)入過程和部分內(nèi)容：

import pandas as pd
import numpy as np
from plotnine import *
import matplotlib.pyplot as plt
from sklearn.preprocessing import LabelEncoder
from sklearn_pandas import DataFrameMapper
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier

training_data = './adult-training.csv'
test_data = './adult-test.csv'

columns = ['Age','Workclass','fnlgwt','Education','EdNum','MaritalStatus','Occupation','Relationship','Race','Sex','CapitalGain','CapitalLoss','HoursPerWeek','Country','Income']

df_train_set = pd.read_csv(training_data, names=columns)
df_test_set = pd.read_csv(test_data, names=columns, skiprows=1)
df_train_set.drop('fnlgwt', axis=1, inplace=True)
df_test_set.drop('fnlgwt', axis=1, inplace=True)

在上面的代碼中渣玲，我們首先需要導(dǎo)入所有需要的庫和模塊逗概，然后再讀取數(shù)據(jù)和結(jié)構(gòu)到訓(xùn)練數(shù)據(jù)和驗(yàn)證數(shù)據(jù)中。我們同樣去除 fnlgwt 列忘衍，因?yàn)樵摂?shù)據(jù)行對于模型的訓(xùn)練并不重要逾苫。

輸入以下語句可以看到訓(xùn)練數(shù)據(jù)的前五行：

df_train_set.head()

如下所示卿城，我們還需要做一些數(shù)據(jù)清洗。我們需要將所有列的的特殊字符移除铅搓，此外任何空格或者「.」都需要移除瑟押。

#replace the special character to "Unknown"for i in df_train_set.columns:
    df_train_set[i].replace(' ?', 'Unknown', inplace=True)
    df_test_set[i].replace(' ?', 'Unknown', inplace=True)for col in df_train_set.columns:if df_train_set[col].dtype != 'int64':
        df_train_set[col] = df_train_set[col].apply(lambda val: val.replace(" ", ""))
        df_train_set[col] = df_train_set[col].apply(lambda val: val.replace(".", ""))
        df_test_set[col] = df_test_set[col].apply(lambda val: val.replace(" ", ""))
        df_test_set[col] = df_test_set[col].apply(lambda val: val.replace(".", ""))

正如上圖所示，有兩行描述了個人的教育：Eduction 和 EdNum狸吞。我們假設(shè)這兩個特征十分相關(guān)勉耀，因此我們可以移除 Education 列。Country 列對預(yù)測收入并不會起到什么作用蹋偏，所以我們需要移除它便斥。

df_train_set.drop(["Country", "Education"], axis=1, inplace=True)
df_test_set.drop(["Country", "Education"], axis=1, inplace=True)

Age 和 EdNum 列是數(shù)值型的，我們可以將連續(xù)數(shù)值型轉(zhuǎn)化為更高效的方式威始，例如將年齡換為 10 年的整數(shù)倍枢纠，教育年限換為 5 年的整數(shù)倍，實(shí)現(xiàn)的代碼如下：

colnames = list(df_train_set.columns)
colnames.remove('Age')
colnames.remove('EdNum')
colnames = ['AgeGroup', 'Education'] + colnames

labels = ["{0}-{1}".format(i, i + 9) for i in range(0, 100, 10)]
df_train_set['AgeGroup'] = pd.cut(df_train_set.Age, range(0, 101, 10), right=False, labels=labels)
df_test_set['AgeGroup'] = pd.cut(df_test_set.Age, range(0, 101, 10), right=False, labels=labels)

labels = ["{0}-{1}".format(i, i + 4) for i in range(0, 20, 5)]
df_train_set['Education'] = pd.cut(df_train_set.EdNum, range(0, 21, 5), right=False, labels=labels)
df_test_set['Education'] = pd.cut(df_test_set.EdNum, range(0, 21, 5), right=False, labels=labels)

df_train_set = df_train_set[colnames]
df_test_set = df_test_set[colnames]

現(xiàn)在我們已經(jīng)清理了數(shù)據(jù)黎棠，下面語句可以展示我們數(shù)據(jù)的概況：

df_train_set.Income.value_counts()

在訓(xùn)練集和測試集中晋渺，我們發(fā)現(xiàn) <=50K 的類別要比>50K 的多 3 倍。從這里我們就可以看出來樣本數(shù)據(jù)并不是均衡的數(shù)據(jù)脓斩，但是在這里為了簡化問題木西，我們在這里將該數(shù)據(jù)集看作常規(guī)問題。

EDA

現(xiàn)在随静，讓我們以圖像的形式看一下訓(xùn)練數(shù)據(jù)中的不同特征的分布和相互依存（inter-dependence）關(guān)系八千。首先看一下關(guān)系（Relationships）和婚姻狀況（MaritalStatus）特征是如何相互關(guān)聯(lián)的。

(ggplot(df_train_set, aes(x = "Relationship", fill = "MaritalStatus"))+ geom_bar(position="fill")+ theme(axis_text_x = element_text(angle = 60, hjust = 1)))

讓我們首先看一下不同年齡組中燎猛，教育對收入的影響（用受教育的年數(shù)進(jìn)行衡量）恋捆。

(ggplot(df_train_set, aes(x = "Education", fill = "Income"))+ geom_bar(position="fill")+ theme(axis_text_x = element_text(angle = 60, hjust = 1))+ facet_wrap('~AgeGroup'))

最近，有很多關(guān)于性別對收入差距的影響的相關(guān)說法重绷。我們可以分別看見男性和女性的教育程度和種族間的影響沸停。

(ggplot(df_train_set, aes(x = "Education", fill = "Income"))+ geom_bar(position="fill")+ theme(axis_text_x = element_text(angle = -90, hjust = 1))+ facet_wrap('~Sex'))

(ggplot(df_train_set, aes(x = "Race", fill = "Income"))+ geom_bar(position="fill")+ theme(axis_text_x = element_text(angle = -90, hjust = 1))+ facet_wrap('~Sex'))

直到現(xiàn)在，我們僅關(guān)注了非數(shù)值特征（non-numeric）的相互關(guān)系≌炎浚現(xiàn)在我們看一下資本收益（CapitalGain）和資本損失（CapitalLoss）對收入的影響愤钾。

(ggplot(df_train_set, aes(x="Income", y="CapitalGain"))+ geom_jitter(position=position_jitter(0.1)))

(ggplot(df_train_set, aes(x="Income", y="CapitalLoss"))+ geom_jitter(position=position_jitter(0.1)))

樹分類器

現(xiàn)在我們理解了我們數(shù)據(jù)中的一些關(guān)系，所以就可以使用 sklearn.tree.DecisionTreeClassifier 創(chuàng)建一個簡單的樹分類器模型候醒。然而绰垂，為了使用這一模型，我們需要把所有我們的非數(shù)值數(shù)據(jù)轉(zhuǎn)化成數(shù)值型數(shù)據(jù)火焰。我們可以直接在 Pandas 數(shù)據(jù)框架中使用 sklearn.preprocessing.LabeEncoder 模塊和 sklearn_pandas 模塊就可以輕松地完成這一步驟劲装。

mapper = DataFrameMapper([('AgeGroup', LabelEncoder()),('Education', LabelEncoder()),('Workclass', LabelEncoder()),('MaritalStatus', LabelEncoder()),('Occupation', LabelEncoder()),('Relationship', LabelEncoder()),('Race', LabelEncoder()),('Sex', LabelEncoder()),('Income', LabelEncoder())], df_out=True, default=None)

cols = list(df_train_set.columns)
cols.remove("Income")
cols = cols[:-3] + ["Income"] + cols[-3:]

df_train = mapper.fit_transform(df_train_set.copy())
df_train.columns = cols

df_test = mapper.transform(df_test_set.copy())
df_test.columns = cols

cols.remove("Income")
x_train, y_train = df_train[cols].values, df_train["Income"].values
x_test, y_test = df_test[cols].values, df_test["Income"].values

現(xiàn)在我們用正確的形式對數(shù)據(jù)進(jìn)行了訓(xùn)練和測試，已創(chuàng)建了我們的第一個模型！

treeClassifier = DecisionTreeClassifier()
treeClassifier.fit(x_train, y_train)
treeClassifier.score(x_test, y_test)

最簡單的且沒有優(yōu)化的概率分類器模型可以達(dá)到 83.5% 的精度占业。在分類問題中绒怨，混淆矩陣（confusion matrix）是衡量模型精度的好方法。使用下列代碼我們可以繪制任意基于樹的模型的混淆矩陣谦疾。

import itertoolsfrom sklearn.metrics import confusion_matrixdef plot_confusion_matrix(cm, classes, normalize=False):"""
    This function prints and plots the confusion matrix.
    Normalization can be applied by setting `normalize=True`.
    """
    cmap = plt.cm.Blues
    title = "Confusion Matrix"if normalize:
        cm = cm.astype('float') / cm.sum(axis=1)[:, np.newaxis]
        cm = np.around(cm, decimals=3)

    plt.imshow(cm, interpolation='nearest', cmap=cmap)
    plt.title(title)
    plt.colorbar()
    tick_marks = np.arange(len(classes))
    plt.xticks(tick_marks, classes, rotation=45)
    plt.yticks(tick_marks, classes)

    thresh = cm.max() / 2.for i, j in itertools.product(range(cm.shape[0]), range(cm.shape[1])):
        plt.text(j, i, cm[i, j],
                 horizontalalignment="center",
                 color="white" if cm[i, j] > thresh else "black")

    plt.tight_layout()
    plt.ylabel('True label')
    plt.xlabel('Predicted label')

現(xiàn)在南蹂，我們可以看到第一個模型的混淆矩陣：

y_pred = treeClassifier.predict(x_test)
cfm = confusion_matrix(y_test, y_pred, labels=[0, 1])
plt.figure(figsize=(10,6))
plot_confusion_matrix(cfm, classes=["<=50K", ">50K"], normalize=True)

我們發(fā)現(xiàn)多數(shù)類別（<=50K）的精度為 90.5%，少數(shù)類別（>50K）的精度只有 60.8%念恍。

讓我們看一下調(diào)校此簡單分類器的方法六剥。我們能使用帶有 5 折交叉驗(yàn)證的 GridSearchCV() 來調(diào)校樹分類器的各種重要參數(shù)。

from sklearn.model_selection import GridSearchCVparameters = {'max_features':(None, 9, 6),'max_depth':(None, 24, 16),'min_samples_split': (2, 4, 8),'min_samples_leaf': (16, 4, 12)}clf = GridSearchCV(treeClassifier, parameters, cv=5, n_jobs=4)clf.fit(x_train, y_train)clf.best_score_, clf.score(x_test, y_test), clf.best_params_

經(jīng)過優(yōu)化峰伙，我們發(fā)現(xiàn)精度上升到了 85.9%疗疟。在上方，我們也可以看見最優(yōu)模型的參數(shù)⊥ィ現(xiàn)在策彤，讓我們看一下 已優(yōu)化模型的混淆矩陣（confusion matrix）：

y_pred = clf.predict(x_test)
cfm = confusion_matrix(y_test, y_pred, labels=[0, 1])
plt.figure(figsize=(10,6))
plot_confusion_matrix(cfm, classes=["<=50K", ">50K"], normalize=True)

image

經(jīng)過優(yōu)化，我們發(fā)現(xiàn)在兩種類別下匣摘，預(yù)測精度都有所提升店诗。

決策樹的局限性

決策樹有很多優(yōu)點(diǎn)，比如：

• 易于理解音榜、易于解釋

• 可視化

• 無需大量數(shù)據(jù)準(zhǔn)備庞瘸。不過要注意，sklearn.tree 模塊不支持缺失值赠叼。

• 使用決策樹（預(yù)測數(shù)據(jù)）的成本是訓(xùn)練決策時所用數(shù)據(jù)的對數(shù)量級擦囊。

但這些模型往往不直接使用，決策樹一些常見的缺陷是：

• 構(gòu)建的樹過于復(fù)雜梅割，無法很好地在數(shù)據(jù)上實(shí)現(xiàn)泛化霜第。

• 數(shù)據(jù)的微小變動可能導(dǎo)致生成的樹完全不同葛家，因此決策樹不夠穩(wěn)定户辞。

• 決策樹學(xué)習(xí)算法在實(shí)踐中通常基于啟發(fā)式算法癞谒，如貪婪算法底燎，在每一個結(jié)點(diǎn)作出局部最優(yōu)決策。此類算法無法確保返回全局最優(yōu)決策樹弹砚。

• 如果某些類別占據(jù)主導(dǎo)地位双仍，則決策樹學(xué)習(xí)器構(gòu)建的決策樹會有偏差。因此推薦做法是在數(shù)據(jù)集與決策樹擬合之前先使數(shù)據(jù)集保持均衡桌吃。

• 某些類別的函數(shù)很難使用決策樹模型來建模朱沃，如 XOR、奇偶校驗(yàn)函數(shù)（parity）和數(shù)據(jù)選擇器函數(shù)（multiplexer）。

大部分限制可以通過改善決策樹輕易解決逗物。在下面的內(nèi)容中搬卒，我們將介紹相關(guān)的幾個概念，重點(diǎn)介紹袋裝和隨機(jī)森林翎卓。

剪枝

由于決策樹容易對數(shù)據(jù)產(chǎn)生過擬合契邀，因此分支更少（即減少區(qū)域 R_1, … ,R_J）的小樹雖然偏差略微高一點(diǎn)，但其產(chǎn)生的方差更低失暴，可解釋性更強(qiáng)坯门。處理上述問題的一種方法是構(gòu)建一棵樹，每個分支超過某個（高）閾值造成葉結(jié)點(diǎn)誤差率 Qm 下降逗扒，則結(jié)束構(gòu)建古戴。但是，由于分裂算法的貪婪本質(zhì)缴阎，它其實(shí)很短視酒觅。決策樹早期看似無用的一次分裂有可能會導(dǎo)致之后一次優(yōu)秀的分裂，并使得 Qm 大幅下降澎胡。

因此晃财，更好的策略是構(gòu)建一個非常大的樹 T_0，然后再剪枝建炫，得到一棵子樹畦韭。剪枝可以使用多種策略。代價復(fù)雜度剪枝（Cost complexity pruning）肛跌，又叫最弱連接剪枝（weakest link pruning）艺配，就是其中一種行之有效的策略。除了考慮每一個可能的子樹之外衍慎，還需要考慮由非負(fù)調(diào)參（nonnegative tuning parameter）α 索引的樹序列转唉。每一個 α 值都對應(yīng)一個盡可能小的子樹 T?T_0。

image

這里∣T∣代表樹 T 中葉結(jié)點(diǎn)的數(shù)量稳捆，R_m 代表第 m 個葉結(jié)點(diǎn)對應(yīng)的矩形（預(yù)測器空間的子集）赠法，yhat_Rm 是 Rm 的預(yù)測值，即 Rm 中訓(xùn)練樣本預(yù)測值的均值（或分類樹中的模式響應(yīng)）乔夯。調(diào)整參數(shù) α 控制子樹復(fù)雜度之間的權(quán)衡砖织，對訓(xùn)練數(shù)據(jù)進(jìn)行擬合。當(dāng) α= 0 的時候末荐，子樹 T 等同于 T_0侧纯。當(dāng)α的值增長時，構(gòu)建具備多個子結(jié)點(diǎn)的樹需要付出代價甲脏，這樣眶熬，要想得到更小的子樹妹笆，上述公式將達(dá)到最小化。我們可以使用某種交叉驗(yàn)證方法選擇剪枝參數(shù) α 娜氏。

注意晾浴，目前 sklearn.tree 決策樹分類器（和回歸器）不支持剪枝。

袋裝（Bootstrap Aggregating——Bagging）

在統(tǒng)計(jì)學(xué)中牍白，Bootstrap 是依靠替換隨機(jī)采樣的任意試驗(yàn)或度量脊凰。我們從上文可以看見，決策樹會受到高方差的困擾茂腥。這意味著如果我們把訓(xùn)練數(shù)據(jù)隨機(jī)分成兩部分狸涌，并且給二者都安置一個決策樹，我們得到的結(jié)果可能就會相當(dāng)不同最岗。Bootstrap 聚集帕胆，或者叫做袋裝，是減少統(tǒng)計(jì)學(xué)習(xí)方法的方差的通用過程般渡。

給定一組 n 個獨(dú)立的樣本觀測值 Z_1懒豹，Z_2，...驯用，Z_n脸秽，每一個值的方差均為 σ^2，樣本觀測值的均值方差為 σ^2/n蝴乔。換句話說记餐，對一組觀測值取平均會減小方差。因此一種減小方差的自然方式薇正，也就是增加統(tǒng)計(jì)學(xué)習(xí)方法預(yù)測精度的方式片酝，就是從總體中取出很多訓(xùn)練集，使用每一個訓(xùn)練集創(chuàng)建一個分離的預(yù)測模型挖腰，并且對預(yù)測結(jié)果求取平均值雕沿。

image

贤姆，從而獲得一個聚集預(yù)測（aggregate prediction）榆苞。

image

這就叫做袋裝（bagging）。注意霞捡，聚集（aggregating）在回歸和分類問題中可能有不同的均值坐漏。當(dāng)平均預(yù)測值在回歸問題中的效果很好時，我們將會需要使用多數(shù)票決（majority vote）：由于分類問題中的聚集機(jī)制，整體預(yù)測就是在 B 個預(yù)測值中最常出現(xiàn)的那個主要類別赊琳。

Out-of-Bag（OOB）誤差

Bagging 方法最大的優(yōu)勢是我們可以不通過交叉驗(yàn)證而求得測試誤差街夭。回想一下躏筏，Bagging 方法的精髓是多棵樹可以重復(fù)地?cái)M合觀察樣本的自助子集板丽。平均而言，每一個袋裝樹可以利用 2/3 的觀察樣本趁尼。而剩下的 1/3 觀察樣本就可以稱為 out-of-bag (OOB) 觀察樣本埃碱，它們并不會擬合一一棵給定袋裝樹。我們可以使用每一棵樹的 OOB 觀察樣本而計(jì)算第 i 個觀察樣本的預(yù)測值酥泞，這將會導(dǎo)致大約有 B/3 的預(yù)測值可以預(yù)測第 i 個觀察樣本⊙獾睿現(xiàn)在我們可以使用和 Bagging（平均回歸和大多數(shù)投票分類）類似的聚集技術(shù)，我們能獲得第 i 個觀察樣本的單一預(yù)測值芝囤。我們可以用這種方式獲得 n 個觀察樣本的 OOB 預(yù)測似炎，因此總體的 OOB MSE（回歸問題）和分類誤差率（分類問題）就能計(jì)算出來。OOB 誤差結(jié)果是 Bagging 模型測試誤差的有效估計(jì)悯姊，因?yàn)槊恳粋€樣本的預(yù)測值都是僅僅使用不會進(jìn)行擬合訓(xùn)練模型的樣本羡藐。

特征重要性度量

通過使用單一樹，Bagging 通常會提升預(yù)測的精確度悯许。但是传睹，解釋最終的模型可能很困難。當(dāng)我們袋裝大量的樹時岸晦，就不再可能使用單一的樹表征最終的統(tǒng)計(jì)學(xué)習(xí)流程欧啤，因此，Bagging 是以犧牲闡釋性能力為代價來提升預(yù)測精確度的启上。有趣的是邢隧，一個人可使用 RSS（用于 bagging 回歸樹）或者基尼指數(shù)（用于 bagging 分類樹）得到每一個預(yù)測器的整體總結(jié)。在 bagging 回歸樹的情況中冈在，我們可以記錄由于所有的 B 樹上平均的給定預(yù)測分子分裂而造成的 RSS 減少的所有數(shù)量倒慧。一個大的值表示一個重要的預(yù)測器。相似地包券，在 bagging 分類樹的情況下纫谅，我們可以添加由于所有的 B 樹上平均的給定預(yù)測分子分裂而造成的基尼系數(shù)降低的所有數(shù)量。一旦訓(xùn)練完成溅固，sklearn 模塊的不同袋裝樹（bagged tree）學(xué)習(xí)方法可直接訪問特征的重要性數(shù)據(jù)作為屬性付秕。

隨機(jī)森林模型

雖然袋裝技術(shù)（Bagging）通過降低方差而提高了一般決策樹的預(yù)測性能，但它還遇到了其他缺點(diǎn)：Bagging 要求我們在自助樣本上生成整棵樹侍郭，這就增加了 B 倍計(jì)算復(fù)雜度询吴。此外掠河，因?yàn)榛?Bagging 的樹是相關(guān)聯(lián)的，預(yù)測精度會根據(jù) B 而飽和猛计。

隨機(jī)森林通過隨機(jī)擾動而令所有的樹去相關(guān)唠摹，因此隨機(jī)森林要比 Bagging 性能更好。隨機(jī)森林不像 Bagging奉瘤，在構(gòu)建每一棵樹時勾拉，每一個結(jié)點(diǎn)分割前都是采用隨機(jī)樣本預(yù)測器。因?yàn)樵诤诵乃枷肷系廖拢S機(jī)森林還是和 Bagging 樹一樣望艺，因此其在方差上有所減少。此外肌访，隨機(jī)森林可以考慮使用大量預(yù)測器找默，不僅因?yàn)檫@種方法減少了偏差，同時局部特征預(yù)測器在樹型結(jié)構(gòu)中充當(dāng)重要的決策吼驶。

隨機(jī)森林可以使用巨量的預(yù)測器惩激，甚至預(yù)測器的數(shù)量比觀察樣本的數(shù)量還多。采用隨機(jī)森林方法最顯著的優(yōu)勢是它能獲得更多的信息以減少擬合數(shù)值和估計(jì)分割的偏差蟹演。

通常我們會有一些預(yù)測器能主導(dǎo)決策樹的擬合過程风钻，因?yàn)樗鼈兊钠骄阅苁冀K要比其他一些競爭預(yù)測器更好。因此酒请，其它許多對局部數(shù)據(jù)特征有用的預(yù)測器并不會選定作為分割變量骡技。隨著隨機(jī)森林計(jì)算了足夠多的決策樹模型，每一個預(yù)測器都至少有幾次機(jī)會能成為定義分割的預(yù)測器羞反。大多數(shù)情況下布朦，我們不僅僅只有主導(dǎo)預(yù)測器，特征預(yù)測器也有機(jī)會定義數(shù)據(jù)集的分割昼窗。

隨機(jī)森林有三個主要的超參數(shù)調(diào)整：

• 結(jié)點(diǎn)規(guī)模：隨機(jī)森林不像決策樹是趴，每一棵樹葉結(jié)點(diǎn)所包含的觀察樣本數(shù)量可能十分少。該超參數(shù)的目標(biāo)是生成樹的時候盡可能保持小偏差澄惊。

• 樹的數(shù)量：在實(shí)踐中選擇數(shù)百棵樹一般是比較好的選擇唆途。

• 預(yù)測器采樣的數(shù)量：一般來說，如果我們一共有 D 個預(yù)測器掸驱，那么我們可以在回歸任務(wù)中使用 D/3 個預(yù)測器數(shù)作為采樣數(shù)肛搬，在分類任務(wù)中使用 D^(1/2) 個預(yù)測器作為抽樣。

隨機(jī)森林模型案例

使用和上文一樣的收入數(shù)據(jù)毕贼，現(xiàn)在我們構(gòu)建一個包含 500 棵樹的簡單隨機(jī)森林分類器模型：

rclf = RandomForestClassifier(n_estimators=500)
rclf.fit(x_train, y_train)
rclf.score(x_test, y_test)

即使沒有任何優(yōu)化温赔，我們?nèi)匀话l(fā)現(xiàn)模型性能可以和已優(yōu)化決策樹分類器相媲美，并且測試分達(dá)到了 85.1%帅刀。按照下面的混淆矩陣让腹，我們發(fā)現(xiàn)簡單的隨機(jī)森林和經(jīng)過優(yōu)化的樹型分類器表現(xiàn)差不多，其在主要類別（<=50K 收入）的預(yù)測精度達(dá)到了 92.1%扣溺，而在少數(shù)類別（>50K 收入）上達(dá)到了 62.6%骇窍。

rclf = RandomForestClassifier(n_estimators=500)
rclf.fit(x_train, y_train)
rclf.score(x_test, y_test)

image

正如前面所探討的，隨機(jī)森林模型還提供了特征重要性的度量方法锥余。我們可以在下圖中看到目前模型不同特征的重要性：

importances = rclf.feature_importances_
indices = np.argsort(importances)
cols = [cols[x] for x in indices]
plt.figure(figsize=(10,6))
plt.title('Feature Importances')
plt.barh(range(len(indices)), importances[indices], color='b', align='center')
plt.yticks(range(len(indices)), cols)
plt.xlabel('Relative Importance')

image

現(xiàn)在我們可以嘗試優(yōu)化我們的隨機(jī)森林模型腹纳，如下我們可以使用帶 5-折交叉驗(yàn)證的 GridSearchCV() 操作來優(yōu)化隨機(jī)森林：

parameters = {'n_estimators':(100, 500, 1000),'max_depth':(None, 24, 16),'min_samples_split': (2, 4, 8),'min_samples_leaf': (16, 4, 12)}

clf = GridSearchCV(RandomForestClassifier(), parameters, cv=5, n_jobs=8)
clf.fit(x_train, y_train)
clf.best_score_, clf.best_params_
0.86606676699118579
{'max_depth': 24,
 'min_samples_leaf': 4,
 'min_samples_split': 4,
 'n_estimators': 1000}

我們可以看到現(xiàn)在的模型要顯著地比前面的更好一些，并且預(yù)測率達(dá)到了 86.6%驱犹。按照下面的混淆矩陣嘲恍，新模型在主要類別的預(yù)測精度上有顯著的提升，并且在少數(shù)類別的預(yù)測上精度只稍微降低了一點(diǎn)雄驹。這是非平衡數(shù)據(jù)普遍存在的問題佃牛。

rclf2 = RandomForestClassifier(n_estimators=1000,max_depth=24,min_samples_leaf=4,min_samples_split=8)
rclf2.fit(x_train, y_train)

y_pred = rclf2.predict(x_test)
cfm = confusion_matrix(y_test, y_pred, labels=[0, 1])
plt.figure(figsize=(10,6))
plot_confusion_matrix(cfm, classes=["<=50K", ">50K"], normalize=True)

image

最后，下面展示了對優(yōu)化后模型比較重要的特征医舆。

importances = rclf2.feature_importances_
indices = np.argsort(importances)
cols = [cols[x] for x in indices]
plt.figure(figsize=(10,6))
plt.title('Feature Importances')
plt.barh(range(len(indices)), importances[indices], color='b', align='center')
plt.yticks(range(len(indices)), cols)
plt.xlabel('Relative Importance')

image

隨機(jī)森林的局限性

除了 Bagging 樹模型的一般局限性外俘侠，隨機(jī)森林還有一些局限性：

• 當(dāng)我們需要推斷超出范圍的獨(dú)立變量或非獨(dú)立變量，隨機(jī)森林做得并不好蔬将，我們最好使用如 MARS 那樣的算法爷速。

• 隨機(jī)森林算法在訓(xùn)練和預(yù)測時都比較慢。

• 如果需要區(qū)分的類別十分多霞怀，隨機(jī)森林的表現(xiàn)并不會很好惫东。

總的來說，隨機(jī)森林在很多任務(wù)上一般要比提升方法的精度差毙石，并且運(yùn)行時間也更長廉沮。所有在 Kaggle 競賽上，有很多模型都是使用的梯度提升樹算法或其他優(yōu)秀的提升方法徐矩。