內(nèi)容參考自：ML-NLP/Machine Learning/3.Desition Tree at master · NLP-LOVE/ML-NLP · GitHub，有修改

目錄

1. 什么是決策樹

1.1 決策樹的基本思想

1.2 “樹”的成長(zhǎng)過(guò)程

1.3 "樹"怎么長(zhǎng)

2. 樹形結(jié)構(gòu)為什么不需要?dú)w一化?

3. 分類決策樹和回歸決策樹的區(qū)別

4. 決策樹如何剪枝

5. 代碼實(shí)現(xiàn)

---

1. 什么是決策樹

1.1 決策樹的基本思想

其實(shí)用一下圖片能更好的理解LR模型和決策樹模型算法的根本區(qū)別，我們可以思考一下一個(gè)決策問(wèn)題：是否去相親，一個(gè)女孩的母親要給這個(gè)女海介紹對(duì)象。

大家都看得很明白了吧！LR模型是一股腦兒的把所有特征塞入學(xué)習(xí)，而決策樹更像是編程語(yǔ)言中的if-else一樣，去做條件判斷，這就是根本性的區(qū)別。

1.2 “樹”的成長(zhǎng)過(guò)程

決策樹基于“樹”結(jié)構(gòu)進(jìn)行決策的，這時(shí)我們就要面臨兩個(gè)問(wèn)題 ：

• “樹”怎么長(zhǎng)。
• 這顆“樹”長(zhǎng)到什么時(shí)候停。

弄懂了這兩個(gè)問(wèn)題，那么這個(gè)模型就已經(jīng)建立起來(lái)了，決策樹的總體流程是“分而治之”的思想，一是自根至葉的遞歸過(guò)程，一是在每個(gè)中間節(jié)點(diǎn)尋找一個(gè)“劃分”屬性，相當(dāng)于就是一個(gè)特征屬性了。接下來(lái)我們來(lái)逐個(gè)解決以上兩個(gè)問(wèn)題。

這顆“樹”長(zhǎng)到什么時(shí)候停

• 當(dāng)前結(jié)點(diǎn)包含的樣本全屬于同一類別，無(wú)需劃分；例如：樣本當(dāng)中都是決定去相親的，屬于同一類別，就是不管特征如何改變都不會(huì)影響結(jié)果，這種就不需要?jiǎng)澐至恕?/li>
• 當(dāng)前屬性集為空，或是所有樣本在所有屬性上取值相同，無(wú)法劃分；例如：所有的樣本特征都是一樣的，就造成無(wú)法劃分了，訓(xùn)練集太單一。
• 當(dāng)前結(jié)點(diǎn)包含的樣本集合為空，不能劃分。

1.3 "樹"怎么長(zhǎng)

在生活當(dāng)中，我們都會(huì)碰到很多需要做出決策的地方，例如：吃飯地點(diǎn)、數(shù)碼產(chǎn)品購(gòu)買、旅游地區(qū)等，你會(huì)發(fā)現(xiàn)在這些選擇當(dāng)中都是依賴于大部分人做出的選擇，也就是跟隨大眾的選擇。其實(shí)在決策樹當(dāng)中也是一樣的，當(dāng)大部分的樣本都是同一類的時(shí)候，那么就已經(jīng)做出了決策。

我們可以把大眾的選擇抽象化，這就引入了一個(gè)概念就是純度，想想也是如此，大眾選擇就意味著純度越高。好，在深入一點(diǎn)，就涉及到一句話：信息熵越低，純度越高。我相信大家或多或少都聽說(shuō)過(guò)“熵”這個(gè)概念，信息熵通俗來(lái)說(shuō)就是用來(lái)度量包含的“信息量”，如果樣本的屬性都是一樣的，就會(huì)讓人覺(jué)得這包含的信息很單一，沒(méi)有差異化，相反樣本的屬性都不一樣，那么包含的信息量就很多了。

一到這里就頭疼了，因?yàn)轳R上要引入信息熵的公式，其實(shí)也很簡(jiǎn)單：

Pk表示的是：當(dāng)前樣本集合D中第k類樣本所占的比例為Pk。

信息增益（information gain）

表示得知特征X的信息而使得類Y的信息不確定性減少的程度，G(D,a)表示使用屬性a對(duì)樣本集D進(jìn)行劃分帶來(lái)的信息增益，設(shè)D為數(shù)據(jù)集，為樣本數(shù)，有K個(gè)類Ck，類Ck的樣本數(shù)，有

a有v個(gè)取值{a1,a2,...av}，根據(jù)特征將D劃分為V個(gè)子集，D1,D2,...DV，為Dv的樣本個(gè)數(shù)，Dv中屬于Ck的樣本集合為Dvk

其中：

,

好了，有了前面的知識(shí)，我們就可以開始“樹”的生長(zhǎng)了。

1.3.1 ID3算法

ID3算法的核心就是在決策樹的各個(gè)節(jié)點(diǎn)處使用信息增益為準(zhǔn)則選擇屬性，遞歸的構(gòu)造決策樹。具體方法，在根節(jié)點(diǎn)處計(jì)算信息熵，然后根據(jù)屬性依次劃分并計(jì)算其節(jié)點(diǎn)的信息熵，用根節(jié)點(diǎn)信息熵減去屬性節(jié)點(diǎn)的信息熵=信息增益，根據(jù)信息增益進(jìn)行降序排列，排在前面的就是第一個(gè)劃分屬性，其后依次類推，這就得到了決策樹的形狀，也就是怎么“長(zhǎng)”了。

不過(guò)，信息增益有一個(gè)問(wèn)題：對(duì)可取值數(shù)目較多的屬性有所偏好，例如：考慮將“編號(hào)”作為一個(gè)屬性。為了解決這個(gè)問(wèn)題，引出了另一個(gè) 算法C4.5。

1.3.2 C4.5

為了解決信息增益的問(wèn)題，引入一個(gè)信息增益率：

其中：

屬性a的可能取值數(shù)目越多(即V越大)，則IV(a)的值通常就越大。**信息增益比本質(zhì)： 是在信息增益的基礎(chǔ)之上乘上一個(gè)懲罰參數(shù)。特征個(gè)數(shù)較多時(shí)，懲罰參數(shù)較小；特征個(gè)數(shù)較少時(shí)，懲罰參數(shù)較大。**不過(guò)有一個(gè)缺點(diǎn)：

• 缺點(diǎn)：信息增益率偏向取值較少的特征。

使用信息增益率：基于以上缺點(diǎn)，并不是直接選擇信息增益率最大的特征，而是現(xiàn)在候選特征中找出信息增益高于平均水平的特征，然后在這些特征中再選擇信息增益率最高的特征。

1.3.3 CART(Classification And Regression Tree)算法

CART假設(shè)決策樹是二叉樹（即特征取值為是和否），左分支為取值為“是”的分支，右分支為取值為“否”的分支。這樣的決策樹等價(jià)于遞歸的二分每個(gè)特征。

數(shù)學(xué)家真實(shí)聰明，想到了另外一個(gè)表示純度的方法，叫做基尼指數(shù)(討厭的公式)：

表示在樣本集合中一個(gè)隨機(jī)選中的樣本被分錯(cuò)的概率。舉例來(lái)說(shuō)，現(xiàn)在一個(gè)袋子里有3種顏色的球若干個(gè)，伸手進(jìn)去掏出2個(gè)球，顏色不一樣的概率，這下明白了吧。Gini(D)越小，數(shù)據(jù)集D的純度越高。

舉個(gè)例子

假設(shè)現(xiàn)在有特征 “學(xué)歷”，此特征有三個(gè)特征取值： “本科”，“碩士”， “博士”，

當(dāng)使用“學(xué)歷”這個(gè)特征對(duì)樣本集合D進(jìn)行劃分時(shí)，劃分值分別有三個(gè)，因而有三種劃分的可能集合，劃分后的子集如下：

1.劃分點(diǎn)： “本科”，劃分后的子集合 ： {本科}，{碩士，博士}

2.劃分點(diǎn)： “碩士”，劃分后的子集合 ： {碩士}，{本科，博士}

3.劃分點(diǎn)： “博士”，劃分后的子集合 ： {博士}，{本科，碩士}}

對(duì)于上述的每一種劃分，都可以計(jì)算出基于?劃分特征= 某個(gè)特征值?將樣本集合D劃分為兩個(gè)子集的純度：

因而對(duì)于一個(gè)具有多個(gè)取值（超過(guò)2個(gè)）的特征，需要計(jì)算以每一個(gè)取值作為劃分點(diǎn)，對(duì)樣本D劃分之后子集的純度Gini(D,Ai)，(其中Ai 表示特征A的可能取值)

然后從所有的可能劃分的Gini(D,Ai)中找出Gini指數(shù)最小的劃分，這個(gè)劃分的劃分點(diǎn)，便是使用特征A對(duì)樣本集合D進(jìn)行劃分的最佳劃分點(diǎn)。到此就可以長(zhǎng)成一棵“大樹”了。

1.3.4 三種不同的決策樹

• ID3：取值多的屬性，更容易使數(shù)據(jù)更純，其信息增益更大。

  訓(xùn)練得到的是一棵龐大且深度淺的樹：不合理。

• C4.5：采用信息增益率替代信息增益。

• CART：以基尼系數(shù)替代熵，最小化不純度，而不是最大化信息增益。

2. 樹形結(jié)構(gòu)為什么不需要?dú)w一化?

因?yàn)閿?shù)值縮放不影響分裂點(diǎn)位置，對(duì)樹模型的結(jié)構(gòu)不造成影響。 按照特征值進(jìn)行排序的，排序的順序不變，那么所屬的分支以及分裂點(diǎn)就不會(huì)有不同。而且，樹模型是不能進(jìn)行梯度下降的，因?yàn)闃?gòu)建樹模型（回歸樹）尋找最優(yōu)點(diǎn)時(shí)是通過(guò)尋找最優(yōu)分裂點(diǎn)完成的，因此樹模型是階躍的，階躍點(diǎn)是不可導(dǎo)的，并且求導(dǎo)沒(méi)意義，也就不需要?dú)w一化。

既然樹形結(jié)構(gòu)（如決策樹、RF）不需要?dú)w一化，那為何非樹形結(jié)構(gòu)比如Adaboost、SVM、LR、Knn、KMeans之類則需要?dú)w一化。

對(duì)于線性模型，特征值差別很大時(shí)，運(yùn)用梯度下降的時(shí)候，損失等高線是橢圓形，需要進(jìn)行多次迭代才能到達(dá)最優(yōu)點(diǎn)。 但是如果進(jìn)行了歸一化，那么等高線就是圓形的，促使SGD往原點(diǎn)迭代，從而導(dǎo)致需要的迭代次數(shù)較少。

3. 分類決策樹和回歸決策樹的區(qū)別

Classification And Regression Tree(CART)是決策樹的一種，CART算法既可以用于創(chuàng)建分類樹（Classification Tree），也可以用于創(chuàng)建回歸樹（Regression Tree），兩者在建樹的過(guò)程稍有差異。

回歸樹：

CART回歸樹是假設(shè)樹為二叉樹，通過(guò)不斷將特征進(jìn)行分裂。比如當(dāng)前樹結(jié)點(diǎn)是基于第j個(gè)特征值進(jìn)行分裂的，設(shè)該特征值小于s的樣本劃分為左子樹，大于s的樣本劃分為右子樹。

而CART回歸樹實(shí)質(zhì)上就是在該特征維度對(duì)樣本空間進(jìn)行劃分，而這種空間劃分的優(yōu)化是一種NP難問(wèn)題，因此，在決策樹模型中是使用啟發(fā)式方法解決。典型CART回歸樹產(chǎn)生的目標(biāo)函數(shù)為：

因此，當(dāng)我們?yōu)榱饲蠼庾顑?yōu)的切分特征j和最優(yōu)的切分點(diǎn)s，就轉(zhuǎn)化為求解這么一個(gè)目標(biāo)函數(shù)：

所以我們只要遍歷所有特征的的所有切分點(diǎn)，就能找到最優(yōu)的切分特征和切分點(diǎn)。最終得到一棵回歸樹。

參考文章：經(jīng)典算法詳解--CART分類決策樹、回歸樹和模型樹

4. 決策樹如何剪枝

決策樹的剪枝基本策略有 預(yù)剪枝 (Pre-Pruning) 和 后剪枝 (Post-Pruning)。

• 預(yù)剪枝：其中的核心思想就是，在每一次實(shí)際對(duì)結(jié)點(diǎn)進(jìn)行進(jìn)一步劃分之前，先采用驗(yàn)證集的數(shù)據(jù)來(lái)驗(yàn)證如果劃分是否能提高劃分的準(zhǔn)確性。如果不能，就把結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)并退出進(jìn)一步劃分；如果可以就繼續(xù)遞歸生成節(jié)點(diǎn)。
• 后剪枝：后剪枝則是先從訓(xùn)練集生成一顆完整的決策樹，然后自底向上地對(duì)非葉結(jié)點(diǎn)進(jìn)行考察，若將該結(jié)點(diǎn)對(duì)應(yīng)的子樹替換為葉結(jié)點(diǎn)能帶來(lái)泛化性能提升，則將該子樹替換為葉結(jié)點(diǎn)。

參考文章：決策樹及決策樹生成與剪枝

5. 代碼實(shí)現(xiàn)

Jupyter Notebook Viewer

總結(jié)

以上是生活随笔為你收集整理的机器学习-决策树（Decision Tree）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。