決策樹算法

轉(zhuǎn)自：Alrange公眾號

你可能做過這樣的選擇：

選擇考研學(xué)校時，如果這是一個普通學(xué)校，你不會選擇該學(xué)校。

但如果這是一個好的一本學(xué)校，你選擇繼續(xù)了解它。

并且如果它地理位置不錯，在你喜歡的城市，你選擇繼續(xù)了解它。

并且如果你選擇的專業(yè)在該校很出名，你選擇繼續(xù)了解它。

接下來你發(fā)現(xiàn)你的能力水平也可以到達(dá)這個目標(biāo)，那么你直接選擇報考它。

相反，如果你的能力水平不能達(dá)到，那么你不會選擇該學(xué)校。

把你上面的一系列決策分支畫下來，就形成了一顆下面的決策樹。

這樣的決策思路可以用到我們的機(jī)器學(xué)習(xí)中的分類來，這個算法就叫作決策樹。

本文涉及到的內(nèi)容：
1、什么是決策樹
2、決策樹的三種算法
3、決策樹的實例應(yīng)用
4、決策樹的算法補(bǔ)充

決策樹（Decision Tree）

什么是決策樹

原理

假設(shè)現(xiàn)在有兩類物體，他們各有兩種特征，投影到二維空間上后，如下圖所示：

我們想要在幾次操作后把兩種種類分開來，于是就有了下面的劃分方法。

可以看到，這樣的劃分方法實質(zhì)是利用訓(xùn)練集構(gòu)造了這樣的決策樹，之后這個決策樹可以用于分類測試的樣例。

概念

決策樹是最經(jīng)常被使用于分類問題的監(jiān)督學(xué)習(xí)算法，并且可以用于類別型特征和連續(xù)型特征。

一個決策樹它的每個分支節(jié)點都代表在一些不同選擇中的一個選擇，并且每一個葉子都代表最終的一個決策。

構(gòu)造這個決策樹會用到許多不同的算法，將會從這些歷史數(shù)據(jù)中建立一個決策樹，并且這個生成的決策樹可以分類未來遇到的樣例。

那么樹的構(gòu)造算法有哪些呢？結(jié)點是如何分裂的呢？

算法介紹

ID3

它的基本思想是采用從頂向下的貪心算法，以信息增益為準(zhǔn)則來產(chǎn)生結(jié)點。

我們先來了解兩個公式：

①熵

熵在機(jī)器學(xué)習(xí)中的意義和在熱力學(xué)中的意義相同，是測量隨機(jī)性的方法。

在這里我們用它來表示樣本集合的純度，公式如下。

其中，pk是第k類樣本在樣本集合D中所占的比例。|y|是樣本的類別個數(shù)。

②信息增益

為屬性a對樣本集D進(jìn)行劃分后所獲得的“信息增益”。信息增益表示得知屬性A的信息而使得樣本集合不確定度減少的程度，公式如下。

V是離散屬性a可能取值的個數(shù)。帶標(biāo)號v的D是D中屬性值a=v的樣本集合。

選擇最優(yōu)屬性就是是它可以給出最大的信息增益。

明白了這兩個概念之后，我們就可以來看構(gòu)造樹的步驟。

③步驟

1、計算數(shù)據(jù)集的熵。（即根節(jié)點的信息熵）
2、對每一個屬性/特征：
①計算所有分類值的熵。②對該屬性取一個平均信息熵。③計算該屬性的信息增益。
3、選擇具有最高的信息增益的屬性作為下一個樹節(jié)點。
4、重復(fù)以上操作直到我們得到期望的樹。

C4.5

可以發(fā)現(xiàn)，如果一個屬性的取值數(shù)目較多的話，它信息增益也會相應(yīng)的變大，那么就會每次分裂使偏向選擇取值數(shù)目多的屬性，為了避免這種情況，接下來講到的C4.5算法，對ID3做了改進(jìn)。

此算法的思想是用信息增益除以一個屬性的固有值，可以一定程度地避免選擇分類多的屬性，漏掉了一些好的特征。

首先看信息增益率的公式：

IV(a)的公式，即屬性a的一個固有值：

由公式可以反映出，當(dāng)選取該屬性，該屬性的可取值數(shù)越大，IV(a)就越大。

但是C4.5算法不直接選擇增益率最大的候選劃分屬性，它會在候選劃分屬性中找出信息增益高于平均水平的屬性，再從中選擇增益率最高的，原因是避免選擇屬性取值數(shù)目小的屬性。

CART算法

CART是一顆二叉樹，它可以是分類樹也可以是回歸樹。

采用GINI值作為節(jié)點分裂的依據(jù).。

GINI值的計算公式：

我們在候選屬性集合A中，選擇那個使得劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性。

實例

我們調(diào)用sklearn里面的決策樹方法來預(yù)測用戶是否購買汽車的意愿。

數(shù)據(jù)的預(yù)處理在之前的文章內(nèi)容提到過，沒看過的同學(xué)可以戳文末的鏈接~

那么直接調(diào)用決策樹分類器：

1from?sklearn.tree?import?DecisionTreeClassifier
2classifier?=?DecisionTreeClassifier(criterion?=?'gini',max_depth=3)#這里設(shè)置劃分準(zhǔn)則為gini,樹的最大深度是3.
3classifier.fit(X_train,?y_train)
4y_pred?=?classifier1.predict(X_test)

接下來用混淆矩陣查看預(yù)測結(jié)果：

1from?sklearn.metrics?import?confusion_matrix
2cm?=?confusion_matrix(y_test,?y_pred)
3cm

我們還可以可視化結(jié)果，來查看決策樹的決策邊界：

 1from?matplotlib.colors?import?ListedColormap
 2X_set,?y_set?=?X_test,?y_test
 3X1,?X2?=?np.meshgrid(np.arange(start?=?X_set[:,?0].min()?-?1,?stop?=?X_set[:,?0].max()?+?1,?step?=?0.01),
 4?????????????????????np.arange(start?=?X_set[:,?1].min()?-?1,?stop?=?X_set[:,?1].max()?+?1,?step?=?0.01))
 5plt.contourf(X1,?X2,?classifier.predict(np.array([X1.ravel(),?X2.ravel()]).T).reshape(X1.shape),
 6?????????????alpha?=?0.75,?cmap?=?ListedColormap(('red',?'green')))#畫出決策樹的決策邊界
 7plt.xlim(X1.min(),?X1.max())#設(shè)置坐標(biāo)范圍
 8plt.ylim(X2.min(),?X2.max())
 9for?i,?j?in?enumerate(np.unique(y_set)):#將測試集以散點形式畫出
10????plt.scatter(X_set[y_set?==?j,?0],?X_set[y_set?==?j,?1],
11????????????????c?=?ListedColormap(('red',?'green'))(i),?label?=?j)
12plt.title('Decision?Tree?Classification?(Test?set)')#設(shè)置標(biāo)題
13plt.xlabel('Age')
14plt.ylabel('Estimated?Salary')
15plt.legend()
16plt.show()

決策樹算法步驟

這里補(bǔ)充了一個內(nèi)容，是較為詳細(xì)的決策樹的基本算法，它采用遞歸調(diào)用的方法，算法中共有三次返回(Return)的情況。

感興趣的同學(xué)可以閱讀。

參考資料：

https://github.com/Avik-Jain/100-Days-Of-ML-Code

機(jī)器學(xué)習(xí)——周志華