譯者 | 趙青窕

審校 | 孫淑娟

前言

在機(jī)器學(xué)習(xí)中，分類具有兩個階段，分別是學(xué)習(xí)階段和預(yù)測階段。在學(xué)習(xí)階段，基于給定的訓(xùn)練數(shù)據(jù)建立模型；在預(yù)測階段，該模型用于預(yù)測給定數(shù)據(jù)的響應(yīng)。決策樹是最容易理解和解釋的分類算法之一。

在機(jī)器學(xué)習(xí)中，分類具有兩個階段，分別是學(xué)習(xí)階段和預(yù)測階段。在學(xué)習(xí)階段，基于給定的訓(xùn)練數(shù)據(jù)建立模型；在預(yù)測階段，該模型用于預(yù)測給定數(shù)據(jù)的響應(yīng)。決策樹是最容易理解和解釋的分類算法之一。

決策樹算法

決策樹算法屬于監(jiān)督學(xué)習(xí)算法中的一種。與其他監(jiān)督學(xué)習(xí)算法不同，決策樹算法可以用于解決回歸和分類問題。

使用決策樹的目的是創(chuàng)建一個訓(xùn)練模型，通過學(xué)習(xí)從之前的數(shù)據(jù)（訓(xùn)練數(shù)據(jù)）推斷出的簡單決策規(guī)則來預(yù)測目標(biāo)變量的類或值。

在決策樹中，我們從樹的根開始來預(yù)測一個記錄的類標(biāo)簽。我們將根屬性的值與記錄的屬性進(jìn)行比較，在比較的基礎(chǔ)上，我們跟隨該值對應(yīng)的分支并跳轉(zhuǎn)到下一個節(jié)點(diǎn)。

決策樹的類型

基于我們所擁有的目標(biāo)變量的類型，我們可以把樹分為兩種類型:

1.分類變量決策樹：有一個分類目標(biāo)變量的決策樹，稱為分類變量決策樹。

2.連續(xù)變量決策樹：決策樹的目標(biāo)變量是連續(xù)的，因此稱為連續(xù)變量決策樹。

例子：假設(shè)我們有一個預(yù)測客戶是否會向保險公司支付續(xù)期保費(fèi)的問題。這里客戶的收入是一個重要的變量，但保險公司沒有所有客戶的收入細(xì)節(jié)?，F(xiàn)在，我們知道這是一個重要的變量，然后我們可以建立一個決策樹，基于職業(yè)，產(chǎn)品和其他各種變量來預(yù)測客戶的收入。在這種情況下，我們預(yù)測目標(biāo)變量是連續(xù)的。

與決策樹相關(guān)的重要術(shù)語

1.根節(jié)點(diǎn)(root node)：它代表整個成員或樣本，這些成員或樣本會進(jìn)一步被分成兩個或多個同類型的集合。

2.分離Splitting)：將一個節(jié)點(diǎn)拆分為兩個或多個子節(jié)點(diǎn)的過程。

3.決策節(jié)點(diǎn)(Decision Node)：當(dāng)一個子節(jié)點(diǎn)分裂成更多的子節(jié)點(diǎn)時，它被稱為決策節(jié)點(diǎn)。

4.葉子/終端節(jié)點(diǎn)(Leaf / Terminal Node)：不可拆分的節(jié)點(diǎn)稱為葉子或終端節(jié)點(diǎn)。

5.修剪(Pruning)：我們刪除一個決策節(jié)點(diǎn)的子節(jié)點(diǎn)的過程被稱為修剪。也可以把修建看作是分離的反過程。

6.分支/子樹(Branch / Sub-Tree)：整個樹的一個子部分稱為分支或子樹。

7.父節(jié)點(diǎn)和子節(jié)點(diǎn)(Parent and Child Node)：節(jié)點(diǎn)可以拆分出子節(jié)點(diǎn)的節(jié)點(diǎn)稱為父節(jié)點(diǎn)，子節(jié)點(diǎn)是父節(jié)點(diǎn)的子節(jié)點(diǎn)。

決策樹通過從根到葉/終端節(jié)點(diǎn)的降序方式來對樣本進(jìn)行分類，葉/終端節(jié)點(diǎn)提供樣品的分類方式。樹中的每個節(jié)點(diǎn)都充當(dāng)某個屬性的測試用例，從節(jié)點(diǎn)的每個降序方向都對應(yīng)著測試用例的可能答案。這個過程本質(zhì)上是遞歸的過程，并且對每個在新節(jié)點(diǎn)上扎根的子樹采用相同的處理方式。

創(chuàng)建決策樹時所進(jìn)行的假設(shè)

以下是我們在使用決策樹時所做的一些假設(shè):

●首先，將整個訓(xùn)練集作為根。

●特征值最好是可以分類的。如果這些值是連續(xù)的，那么在建立模型之前可以對它們進(jìn)行離散化處理。

●記錄是基于屬性值遞歸分布的。

●通過使用一些統(tǒng)計方法來把相應(yīng)屬性按順序放置在樹的根節(jié)點(diǎn)或者樹的內(nèi)部節(jié)點(diǎn)。

決策樹遵循乘積和表述形式。乘積和(SOP)也被稱為析取范式。對于一個類，從樹根到具有相同類的葉節(jié)點(diǎn)的每個分支都是值的合取，在該類中結(jié)束的不同分支構(gòu)成了析取。

決策樹實(shí)現(xiàn)過程中的主要挑戰(zhàn)是確定根節(jié)點(diǎn)及每一級節(jié)點(diǎn)的屬性，這個問題就是屬性選擇問題。目前有不同的屬性選擇方法來選擇每一級節(jié)點(diǎn)的屬性。

決策樹是如何工作的?

決策的分離特性嚴(yán)重影響樹的準(zhǔn)確性，分類樹和回歸樹的決策標(biāo)準(zhǔn)不同。

決策樹使用多種算法來決定將一個節(jié)點(diǎn)分成兩個或多個子節(jié)點(diǎn)。子節(jié)點(diǎn)的創(chuàng)建增加了子節(jié)點(diǎn)的同質(zhì)性。換句話說，相對于目標(biāo)變量來說，節(jié)點(diǎn)的純度增加了。決策樹將所有可用變量上的節(jié)點(diǎn)進(jìn)行分離，然后選擇可以產(chǎn)生很多同構(gòu)子節(jié)點(diǎn)的節(jié)點(diǎn)進(jìn)行拆分。

算法是基于目標(biāo)變量的類型進(jìn)行選擇的。接下來，讓我們看一看決策樹中會使用到的一些算法:

ID3→(D3的延伸)

C4.5→(ID3的繼承者)

CART→(分類與回歸樹)

CHAID→(卡方自動交互檢測(Chi-square automatic interaction detection)在計算分類樹時進(jìn)行多級分離)

MARS→(多元自適應(yīng)回歸樣條)

ID3算法使用自頂向下的貪婪搜索方法，在不回溯的情況下，通過可能的分支空間構(gòu)建決策樹。貪婪算法，顧名思義，總是某一時刻做出似乎是最好的選擇。

ID3算法步驟:

1.它以原始集合S作為根節(jié)點(diǎn)。

2.在算法的每次迭代過程中，對集合S中未使用的屬性進(jìn)行迭代，計算該屬性的熵(H)和信息增益(IG)。

3.然后選擇熵最小或信息增益最大的屬性。

4.緊接著用所選的屬性分離集合S以產(chǎn)生數(shù)據(jù)的子集。

5.該算法繼續(xù)在每個子集上迭代，每次迭代時只考慮以前從未選擇過的屬性。

屬性選擇方法

如果數(shù)據(jù)集包含N個屬性，那么決定將哪個屬性放在根節(jié)點(diǎn)或放在樹的不同級別作為內(nèi)部節(jié)點(diǎn)是一個復(fù)雜的步驟。通過隨機(jī)選擇任意節(jié)點(diǎn)作為根結(jié)點(diǎn)并不能解決問題。如果我們采用隨機(jī)的方法，可能會得到比較糟糕的結(jié)果。

為了解決這一屬性選擇問題，研究人員設(shè)計了一些解決方案。他們建議使用如下標(biāo)準(zhǔn):

• 熵
• 信息增益
• 基尼指數(shù)
• 增益率
• 方差削減
• 卡方

使用這些標(biāo)準(zhǔn)計算每個屬性的值，然后對這些值進(jìn)行排序，并將屬性按照順序放置在樹中，也就是說，高值的屬性放置在根位置。

在使用信息增益作為標(biāo)準(zhǔn)時，我們假設(shè)屬性是分類的，而對于基尼指數(shù)，我們假設(shè)屬性是連續(xù)的。

1. 熵

熵是對被處理信息的隨機(jī)性的度量。熵值越高，就越難從信息中得出任何結(jié)論。拋硬幣就是提供隨機(jī)信息的行為的一個例子。

由上圖可知，當(dāng)概率為0或1時，熵H(X)為零。當(dāng)概率為0.5時，熵是最大的，因?yàn)樗跀?shù)據(jù)中投射出完全的隨機(jī)性。

ID3遵循的規(guī)則是：一個熵為0的分支是一個葉節(jié)點(diǎn)，一個熵大于0的分支需要進(jìn)一步分離。

單個屬性的數(shù)學(xué)熵表示如下:

其中S表示當(dāng)前狀態(tài)，Pi表示狀態(tài)S中事件i的概率或狀態(tài)S節(jié)點(diǎn)中i類的百分比。

多個屬性的數(shù)學(xué)熵表示如下:

其中T表示當(dāng)前狀態(tài)，X表示選定屬性

2.信息增益

信息增益(Information gain, IG)是一種統(tǒng)計屬性，用來衡量給定屬性根據(jù)目標(biāo)類分離訓(xùn)練的效果。構(gòu)建決策樹就是尋找一個返回最高信息增益和最小熵的屬性的過程。

信息的增加就是熵的減少。它根據(jù)給定的屬性值計算數(shù)據(jù)集分離前的熵差和分離后的平均熵差。ID3決策樹算法使用的就是信息增益的方法。

IG在數(shù)學(xué)上表示如下:

用一種更簡單的方法，我們可以得出這樣的結(jié)論:

其中before為拆分前的數(shù)據(jù)集，K為拆分產(chǎn)生的子集數(shù)量，(j, after)為拆分后的子集j。

3.基尼指數(shù)

您可以將基尼指數(shù)理解為用于評估數(shù)據(jù)集中分離的成本函數(shù)。它的計算方法是用1減去每個類的概率平方和。它傾向于較大的分區(qū)并且易于實(shí)現(xiàn)的情形，而信息增益則傾向于具有不同值的較小分區(qū)的情形。

基尼指數(shù)離不開分類目標(biāo)變量“成功”或“失敗”。它只執(zhí)行二進(jìn)制分離。基尼系數(shù)越高，不平等程度越高，異質(zhì)性越強(qiáng)。

計算基尼指數(shù)分離的步驟如下：

• 計算子節(jié)點(diǎn)的基尼系數(shù)，使用上面的成功(p)和失敗(q)的公式(p2+q2)。
• 使用分離的每個節(jié)點(diǎn)的加權(quán)基尼得分計算分離的基尼系數(shù)指數(shù)。

CART(Classification and Regression Tree)就是使用基尼指數(shù)方法來創(chuàng)建分離點(diǎn)。

4.增益率

信息增益傾向于選擇具有大量值的屬性作為根節(jié)點(diǎn)。這意味著它更喜歡具有大量不同值的屬性。

C4.5是ID3的改進(jìn)方法，它使用增益比，這是對信息增益的一種修正，以減少其偏置，通常是最好的選擇方法。增益率克服了信息增益的問題，在進(jìn)行拆分之前考慮了分支的數(shù)量。它通過考慮分離的內(nèi)在信息來糾正信息增益。

假如我們有一個數(shù)據(jù)集，其中包含用戶和他們的電影類型偏好，這些偏好基于性別、年齡組、等級等變量。在信息增益的幫助下，你將在“性別”中進(jìn)行分離(假設(shè)它擁有最高的信息增益)，現(xiàn)在變量“年齡組”和“評級”可能同樣重要，在增益比的幫助下，我們可以選擇在下一層中進(jìn)行分離的屬性。

其中before為分離前的數(shù)據(jù)集，K為分離產(chǎn)生的子集數(shù)量，(j, after)為分離后的子集j。

5.方差削減

方差削減是一種用于連續(xù)目標(biāo)變量(回歸問題)的算法。該算法使用標(biāo)準(zhǔn)方差公式來選擇最佳分離方式。選擇方差較低的分離作為分離總體的標(biāo)準(zhǔn):

是均值，X是實(shí)際值，n是值的個數(shù)。

計算方差的步驟:

• 計算每個節(jié)點(diǎn)的方差。
• 計算每一次分離的方差并作為每個節(jié)點(diǎn)方差的加權(quán)平均。

6.卡方

CHAID是Chi-squared Automatic Interaction Detector的縮寫。這是比較老的樹的分類方法之一。找出子節(jié)點(diǎn)與父節(jié)點(diǎn)之間的差異具有統(tǒng)計學(xué)意義。我們通過對目標(biāo)變量的觀測頻率和期望頻率之間的標(biāo)準(zhǔn)化差的平方和來衡量它。

它與分類目標(biāo)變量“成功”或“失敗”一起工作。它可以執(zhí)行兩次或多次分離?？ǚ街翟礁?，子節(jié)點(diǎn)與父節(jié)點(diǎn)之間的差異統(tǒng)計意義就越高。它生成一個名為CHAID的樹。

在數(shù)學(xué)上，Chi-squared表示為:

計算卡方的步驟如下:

• 通過計算成功和失敗的偏差來計算單個節(jié)點(diǎn)的卡方
• 使用分離的各節(jié)點(diǎn)的成功和失敗的所有卡方之和計算分離的卡方

如何避免/對抗決策樹的過擬合(Overfitting)?

決策樹存在一個常見問題，特別是對于一個滿列的樹。有時它看起來像是樹記住了訓(xùn)練數(shù)據(jù)集。如果一個決策樹沒有限制，它會給你100%的訓(xùn)練數(shù)據(jù)集的準(zhǔn)確性，因?yàn)樵谧钤愀獾那闆r下，它最終會為每個觀察產(chǎn)生一個葉子。因此，當(dāng)預(yù)測不屬于訓(xùn)練集的樣本時，這就會影響準(zhǔn)確性。

在此我介紹兩種方法來消除過擬合，分別是修剪決策樹和隨機(jī)森林。

1.修剪決策樹

分離過程會產(chǎn)生完全長成的樹，直到達(dá)到停止標(biāo)準(zhǔn)。但是，成熟的樹很可能會過度擬合數(shù)據(jù)，導(dǎo)致對未見數(shù)據(jù)的準(zhǔn)確性較差。

在修剪中，你剪掉樹的分支，也就是說，刪除從葉子節(jié)點(diǎn)開始的決策節(jié)點(diǎn)，這樣整體的準(zhǔn)確性就不會受到干擾。這是通過將實(shí)際的訓(xùn)練集分離為兩個集：訓(xùn)練數(shù)據(jù)集D和驗(yàn)證數(shù)據(jù)集V，用分離的訓(xùn)練數(shù)據(jù)集D準(zhǔn)備決策樹，然后繼續(xù)對樹進(jìn)行相應(yīng)的修剪，以優(yōu)化驗(yàn)證數(shù)據(jù)集V的精度。

在上圖中，樹左側(cè)的“Age”屬性已經(jīng)被修剪，因?yàn)樗跇涞挠覀?cè)更重要，因此消除了過擬合。

2.隨機(jī)森林

隨機(jī)森林是集成學(xué)習(xí)(Ensemble Learning)的一個例子，我們結(jié)合多種機(jī)器學(xué)習(xí)算法來獲得更好的預(yù)測性能。因?yàn)闃?gòu)建樹時訓(xùn)練數(shù)據(jù)集是隨機(jī)抽樣的，且分離節(jié)點(diǎn)時考慮特征的隨機(jī)子集，所以我們把這種方法稱之為隨機(jī)。

一種被稱為bagging的技術(shù)被用來創(chuàng)建一個樹的集合，其中多個訓(xùn)練集通過替換生成。

bagging技術(shù)采用隨機(jī)抽樣的方法將數(shù)據(jù)集劃分為N個樣本。然后，使用單一學(xué)習(xí)算法在所有樣本上建立模型。之后通過并行投票或平均的方式將預(yù)測結(jié)果結(jié)合起來。

線性模型和基于樹的模型哪個更好?

該問題取決于你要解決的問題類型。

1.如果因變量和自變量之間的關(guān)系可以被一個線性模型很好地模擬，線性回歸將優(yōu)于基于樹的模型。

2.如果因變量和自變量之間存在高度的非線性且復(fù)雜的關(guān)系，樹模型將優(yōu)于經(jīng)典回歸方法。

3.如果你需要建立一個容易理解的模型，決策樹模型總是比線性模型更好。決策樹模型比線性回歸更容易理解!

使用Scikit-learn進(jìn)行決策樹分類器構(gòu)建

我采用的數(shù)據(jù)是從https://drive.google.com/open?id=1x1KglkvJxNn8C8kzeV96YePFnCUzXhBS下載的超市相關(guān)數(shù)據(jù)，首先使用下面的代碼加載所有基本庫：

import numpy as np
import matplotlib.pyplot as plt 
import pandas as pd

之后，我們采用下面的方式加載數(shù)據(jù)集。它包括5個屬性，用戶id，性別，年齡，預(yù)估工資和購買情況。

data = pd.read_csv('/Users/ML/DecisionTree/Social.csv')
data.head()

圖1數(shù)據(jù)集

我們只將年齡和預(yù)估工資作為我們的自變量X，因?yàn)樾詣e和用戶ID等其他特征是不相關(guān)的，對一個人的購買能力沒有影響，y是因變量。

feature_cols = ['Age','EstimatedSalary' ]X = data.iloc[:,[2,3]].values
y = data.iloc[:,4].values

下一步是將數(shù)據(jù)集分離為訓(xùn)練集和測試集。

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test =  train_test_split(X,y,test_size = 0.25, random_state= 0)

接下來執(zhí)行特征縮放

#feature scaling
from sklearn.preprocessing import StandardScaler
sc_X = StandardScaler()
X_train = sc_X.fit_transform(X_train)
X_test = sc_X.transform(X_test)

將模型擬合到?jīng)Q策樹分類器中。

from sklearn.tree import DecisionTreeClassifier
classifier = DecisionTreeClassifier()
classifier = classifier.fit(X_train,y_train)

進(jìn)行預(yù)測并檢查準(zhǔn)確性。

#prediction
y_pred = classifier.predict(X_test)#Accuracy
from sklearn import metricsprint('Accuracy Score:', metrics.accuracy_score(y_test,y_pred))

決策樹分類器的準(zhǔn)確率達(dá)到91%。

混淆矩陣

from sklearn.metrics import confusion_matrix
cm = confusion_matrix(y_test, y_pred)Output:
array([[64,  4],
       [ 2, 30]])

這意味著有6個觀測結(jié)果被列為錯誤。

首先，讓我們將模型預(yù)測結(jié)果可視化

from matplotlib.colors import ListedColormap
X_set, y_set = X_test, y_test
X1, X2 = np.meshgrid(np.arange(start = X_set[:,0].min()-1, stop= X_set[:,0].max()+1, step = 0.01),np.arange(start = X_set[:,1].min()-1, stop= X_set[:,1].max()+1, step = 0.01))
plt.contourf(X1,X2, classifier.predict(np.array([X1.ravel(), X2.ravel()]).T).reshape(X1.shape), alpha=0.75, cmap = ListedColormap(("red","green")))plt.xlim(X1.min(), X1.max())
plt.ylim(X2.min(), X2.max())for i,j in enumerate(np.unique(y_set)):
    plt.scatter(X_set[y_set==j,0],X_set[y_set==j,1], c = ListedColormap(("red","green"))(i),label = j)
plt.title("Decision Tree(Test set)")
plt.xlabel("Age")
plt.ylabel("Estimated Salary")
plt.legend()
plt.show()

接下來，想象一下這棵樹

接下來您可以使用Scikit-learn的export_graphviz函數(shù)在Jupyter筆記本中顯示樹。為了繪制樹，我們需要采用下面的命令安裝Graphviz和pydotplus：

conda install python-graphviz
pip install pydotplus

export_graphviz函數(shù)將決策樹分類器轉(zhuǎn)換為點(diǎn)文件，pydotplus將該點(diǎn)文件轉(zhuǎn)換為png或在Jupyter上顯示的形式，具體實(shí)現(xiàn)方式如下：

from sklearn.tree import export_graphviz
from sklearn.externals.six import StringIO  
from IPython.display import Image  
import pydotplusdot_data = StringIO()
export_graphviz(classifier, out_file=dot_data,  
                filled=True, rounded=True,
                special_characters=True,feature_names = feature_cols,class_names=['0','1'])
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())  
Image(graph.create_png())

在決策樹形圖中，每個內(nèi)部節(jié)點(diǎn)都有一個分離數(shù)據(jù)的決策規(guī)則。Gini代表基尼系數(shù)，它代表了節(jié)點(diǎn)的純度。當(dāng)一個節(jié)點(diǎn)的所有記錄都屬于同一個類時，您可以說它是純節(jié)點(diǎn)，這種節(jié)點(diǎn)稱為葉節(jié)點(diǎn)。

在這里，生成的樹是未修剪的。這棵未經(jīng)修剪的樹不容易理解。在下一節(jié)中，我會通過修剪的方式來優(yōu)化樹。

隨后優(yōu)化決策樹分類器

criteria: 該選項(xiàng)默認(rèn)配置是Gini，我們可以通過該項(xiàng)選擇合適的屬性選擇方法，該參數(shù)允許我們使用different-different屬性選擇方式。支持的標(biāo)準(zhǔn)包含基尼指數(shù)的“基尼”和信息增益的“熵”。

splitter: 該選項(xiàng)默認(rèn)配置是" best "，我們可以通過該參數(shù)選擇合適的分離策略。支持的策略包含“best”(最佳分離)和“random”(最佳隨機(jī)分離)。

max_depth：默認(rèn)配置是None，我們可以通過該參數(shù)設(shè)置樹的最大深度。若設(shè)置為None，則節(jié)點(diǎn)將展開，直到所有葉子包含的樣本小于min_samples_split。最大深度值越高，過擬合越嚴(yán)重，反之，過擬合將不嚴(yán)重。

在Scikit-learn中，只有通過預(yù)剪枝來優(yōu)化決策樹分類器。樹的最大深度可以用作預(yù)剪枝的控制變量。

# Create Decision Tree classifer object
classifier = DecisionTreeClassifier(criterion="entropy", max_depth=3)# Train Decision Tree Classifer
classifier = classifier.fit(X_train,y_train)#Predict the response for test dataset
y_pred = classifier.predict(X_test)# Model Accuracy, how often is the classifier correct?
print("Accuracy:",metrics.accuracy_score(y_test, y_pred))

至此分類率提高到94%，相對之前的模型來說，其準(zhǔn)確率更高。現(xiàn)在讓我們再次可視化優(yōu)化后的修剪后的決策樹。

dot_data = StringIO()
export_graphviz(classifier, out_file=dot_data,  
                filled=True, rounded=True,
                special_characters=True, feature_names = feature_cols,class_names=['0','1'])
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())  
Image(graph.create_png())

上圖是經(jīng)過修剪后的模型，相對之前的決策樹模型圖來說，其更簡單、更容易解釋和理解。

總結(jié)

在本文中，我們討論了很多關(guān)于決策樹的細(xì)節(jié)，它的工作方式，屬性選擇措施，如信息增益，增益比和基尼指數(shù)，決策樹模型的建立，可視化，并使用Python Scikit-learn包評估和優(yōu)化決策樹性能，這就是這篇文章的全部內(nèi)容，希望你們能喜歡它。

譯者介紹

趙青窕，51CTO社區(qū)編輯，從事多年驅(qū)動開發(fā)。

原文標(biāo)題：??Decision Tree Algorithm, Explained??，作者：Nagesh Singh Chauhan