經(jīng)典算法：決策樹(shù)（Decision Tree）

一、模型介紹

決策樹(shù)是一類(lèi)常見(jiàn)的機(jī)器學(xué)習(xí)方法。既可以作為分類(lèi)算法，也可以作為回歸算法。同時(shí)也非常適合集成學(xué)習(xí)。決策樹(shù)是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法，它易于實(shí)現(xiàn)，可解釋性強(qiáng)，完全符合人類(lèi)的直觀思維，有著廣泛的應(yīng)用。本文將對(duì)最基礎(chǔ)的決策樹(shù)算法原理進(jìn)行介紹，后續(xù)再介紹關(guān)于決策樹(shù)相關(guān)算法的變體。

二、模型原理

image.png

決策樹(shù)算法采用樹(shù)形結(jié)構(gòu)，使用層層推理來(lái)實(shí)現(xiàn)最終的分類(lèi)。一顆完整的決策樹(shù)包括：

  • 根節(jié)點(diǎn)：包含樣本的全集。
  • 內(nèi)部節(jié)點(diǎn)：對(duì)應(yīng)特征屬性測(cè)試。
  • 葉節(jié)點(diǎn)：代表決策結(jié)果。

預(yù)測(cè)時(shí)，在樹(shù)的內(nèi)部節(jié)點(diǎn)處用某一屬性值進(jìn)行判斷，根據(jù)判斷結(jié)果決定進(jìn)入哪個(gè)分支節(jié)點(diǎn)，直到到達(dá)葉節(jié)點(diǎn)處，得到分類(lèi)結(jié)果。

決策樹(shù)的學(xué)習(xí)關(guān)鍵是如何選擇最優(yōu)劃分屬性？
通俗理解，我們希望隨著劃分過(guò)程不斷進(jìn)行，決策樹(shù)的分支節(jié)點(diǎn)所包含的樣本盡可能屬于同一類(lèi)別，即節(jié)點(diǎn)的‘純度’越來(lái)越高。所以我們需要有一個(gè)可量化的指標(biāo)來(lái)表示‘純度’，以作為決策樹(shù)選擇最優(yōu)劃分屬性的依據(jù)。
下面主要介紹三種常見(jiàn)的指標(biāo)：信息增益（ID3）、信息增益率（C4.5)、基尼指數(shù)（CART）。

信息增益

‘信息熵’是度量樣本集合純度最常用的一種指標(biāo)。熵度量了事物的不確定性，越不確定的事物，它的熵就越大。假定當(dāng)前樣本集合 D 中第 k 類(lèi)樣本所占的比例為p_k(k=1,2,……m) 則 D 的信息熵定義為：Ent(D) = -\sum_{i=1}^{m}p_k\log_{2}{p_k} Ent(D)越小，則 D 的純度越高。
假設(shè)離散屬性 a 有 n 個(gè)可能的取值\{a^1,a^2,……,a^n\}, 若使用 a 來(lái)對(duì)樣本集 D 進(jìn)行劃分，則會(huì)產(chǎn)生 V 個(gè)分支結(jié)點(diǎn)，其中第 n 個(gè)分支包含了 D 中所有在屬性 a 上取值為 a^n 的樣本，記作 D^n。同時(shí)考慮到樣本越多的分支節(jié)點(diǎn)的影響越大，于是可以計(jì)算出用 a 屬性對(duì)樣本集 D 進(jìn)行劃分所得的‘信息增益’ (information gain): Gain(D,a) = Ent(D) - \sum_{i=1}^{n}\frac{|D^n|} {|D|} Ent(D^n)
一般而言，信息增益越大，則意味這使用屬性 a 來(lái)進(jìn)行劃分所獲得的‘純度提升’越大。 ID3 決策樹(shù)學(xué)習(xí)算法就是以信息增益為準(zhǔn)則來(lái)選擇劃分屬性。

增益率

在信息增益中，如果以每個(gè)對(duì)像的 ID 為屬性劃分，這樣的分支節(jié)純度已經(jīng)到達(dá)最大，但是，這樣的決策樹(shù)明顯不具有泛化能力，無(wú)法對(duì)新樣本進(jìn)行有效預(yù)測(cè)。
實(shí)際上，信息增益在計(jì)算的時(shí)候會(huì)對(duì)取值數(shù)目較多的屬性有所偏好，為了減少這種偏好可能帶來(lái)的不利影響。C4.5 決策樹(shù)算法不直接使用信息增益，而是使用‘增益率’ (gain ratio) 來(lái)選擇最優(yōu)劃分屬性。增益率定義為：Gain_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}
其中IV(a) = - \sum_{i=1}^{n}\frac{|D^n|}{|D|}log_{2}{\frac{|D|^n}{|D|}}
稱為屬性 a 的‘固有值’。屬性 a 的可能取值數(shù)目越多(即 n 越大)，則 IV(a) 的值通常會(huì)越大。不過(guò)，增益率準(zhǔn)則會(huì)對(duì)取值數(shù)目較少的屬性有所偏好。因此，C4.5 算法并不是直接選擇增益率最大的候選劃分屬性，而是使用了一個(gè)啟發(fā)式：先從候選劃分屬性中找出信息增益高于平均水平的屬性，再?gòu)闹羞x擇增益率高的。

C4.5 算法的不足與思考

C4.5 雖然改進(jìn)或者改善了 ID3 算法的幾個(gè)主要的問(wèn)題，仍然有優(yōu)化的空間。

  • 1、由于決策樹(shù)算法非常容易過(guò)擬合，因此對(duì)于生成的決策樹(shù)必須要進(jìn)行剪枝。剪枝的算法有非常多，C4.5 的剪枝方法有優(yōu)化的空間。思路主要是兩種，一種是預(yù)剪枝，即在生成決策樹(shù)的時(shí)候就決定是否剪枝。另一個(gè)是后剪枝，即先生成決策樹(shù)，再通過(guò)交叉驗(yàn)證來(lái)剪枝。
  • 2、C4.5 生成的是多叉樹(shù)，即一個(gè)父節(jié)點(diǎn)可以有多個(gè)節(jié)點(diǎn)。很多時(shí)候，在計(jì)算機(jī)中二叉樹(shù)模型會(huì)比多叉樹(shù)運(yùn)算效率高。如果采用二叉樹(shù)，可以提高效率。
  • 3、C4.5 只能用于分類(lèi)，如果能將決策樹(shù)用于回歸的話可以擴(kuò)大它的使用范圍。
  • 4、C4.5 由于使用了熵模型，里面有大量的耗時(shí)的對(duì)數(shù)運(yùn)算,如果是連續(xù)值還有大量的排序運(yùn)算。

基尼指數(shù)

CART 決策樹(shù)使用‘基尼指數(shù)’來(lái)選擇劃分屬性，數(shù)據(jù)集 D 的純度可用基尼值來(lái)度量：
計(jì)算公式：Gini(D) = \sum_{i=1}^{k}\sum_{i'\neq i} p_k p_{k'} = 1 - \sum_{i=1}^{k}p_k^2
對(duì)于樣本 D :
Gini(D) = 1 - \sum_{i=1}^{k}(\frac{C_k}{D})^2
對(duì)于特征 A 將 D 劃分：
Gini(D, A) = \frac{D_1}{D}Gini(D_1) + \frac{D_2}{D}Gini(D_2)
直觀來(lái)說(shuō)，Gini(D) 反映了從數(shù)據(jù)集 D 中隨機(jī)抽取兩個(gè)樣本，其類(lèi)別標(biāo)記不一致的概率。 所以，Gini(D) 越小，則數(shù)據(jù)集 D 的純度越高。同時(shí)有，屬性 a 的基尼指數(shù)定義為：Gini\_index(D,a) = \sum_{i=1}^{k}\frac{|D^k|}{|D|}Gini(D^k)
于是，我們?cè)诤蜻x屬性集合中，選擇那個(gè)是的劃分后基尼指數(shù)最小的那個(gè)屬性作為最優(yōu)劃分屬性。

CART 分類(lèi)樹(shù)算法對(duì)于連續(xù)特征和離散特征處理的改進(jìn)

對(duì)于 CART 分類(lèi)樹(shù)連續(xù)值的處理問(wèn)題，其思想和 C4.5 是相同的，都是將連續(xù)的特征離散化。唯一的區(qū)別在于在選擇劃分點(diǎn)時(shí)的度量方式不同，C4.5使用的是信息增益比，則CART分類(lèi)樹(shù)使用的是基尼系數(shù)。具體的思路如下：
比如 m 個(gè)樣本的連續(xù)特征 A 有 m 個(gè)，從小到大排列為 ??1,??2,...,???? 則 CART 算法取相鄰兩樣本值的平均數(shù)，一共取得 m-1 個(gè)劃分點(diǎn)，其中第 i 個(gè)劃分點(diǎn) ???? 表示為：????=(????+????+1)/2。對(duì)于這 m-1 個(gè)點(diǎn)，分別計(jì)算以該點(diǎn)作為二元分類(lèi)點(diǎn)時(shí)的基尼系數(shù)。選擇基尼系數(shù)最小的點(diǎn)作為該連續(xù)特征的二元離散分類(lèi)點(diǎn)。比如取到的基尼系數(shù)最小的點(diǎn)為 ????，則小于 ???? 的值為類(lèi)別 1，大于 ???? 的值為類(lèi)別 2，這樣我們就做到了連續(xù)特征的離散化。

要注意的是，與 ID3 或者 C4.5 處理離散屬性不同的是，如果當(dāng)前節(jié)點(diǎn)為離散屬性，則該屬性后面還可以參與子節(jié)點(diǎn)的產(chǎn)生選擇過(guò)程。
對(duì)于 CART 分類(lèi)樹(shù)離散值的處理問(wèn)題，采用的思路是不停的二分離散特征。
回憶下 ID3 或者 C4.5，如果某個(gè)特征 A 被選取建立決策樹(shù)節(jié)點(diǎn)，如果它有A1, A2, A3 三種類(lèi)別，我們會(huì)在決策樹(shù)上一下建立一個(gè)三叉的節(jié)點(diǎn)。這樣導(dǎo)致決策樹(shù)是多叉樹(shù)。但是 CART 分類(lèi)樹(shù)使用的方法不同，他采用的是不停的二分，還是這個(gè)例子，CART 分類(lèi)樹(shù)會(huì)考慮把 A 分成 {??1} 和 {??2,??3}, {??2} 和 {??1,??3}, {??3}和 {??1,??2}三種情況，找到基尼系數(shù)最小的組合，比如 {??2} 和 {??1,??3},然后建立二叉樹(shù)節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)是 A2 對(duì)應(yīng)的樣本，另一個(gè)節(jié)點(diǎn)是 {A1,A3} 對(duì)應(yīng)的節(jié)點(diǎn)。同時(shí)，由于這次沒(méi)有把特征 A 的取值完全分開(kāi)，后面我們還有機(jī)會(huì)在子節(jié)點(diǎn)繼續(xù)選擇到特征 A 來(lái)劃分 A1 和 A3。這和 ID3 或者 C4.5 不同，在 ID3 或者 C4.5 的一棵子樹(shù)中，離散特征只會(huì)參與一次節(jié)點(diǎn)的建立。

三、模型細(xì)節(jié)

剪枝處理

剪枝(pruning) 是決策樹(shù)學(xué)習(xí)算法處理過(guò)擬合的主要手段。通過(guò)主動(dòng)去掉一些分支來(lái)降低過(guò)擬合的風(fēng)險(xiǎn)。決策樹(shù)剪枝的基本策略有：預(yù)剪枝(prepruning) 和 后剪枝(postpruning)。

  • 預(yù)剪枝：在決策樹(shù)生成過(guò)程中，對(duì)每個(gè)節(jié)點(diǎn)在劃分前先進(jìn)行估計(jì)，若當(dāng)前節(jié)點(diǎn)不能帶來(lái)決策樹(shù)泛化性能提升，則停止劃分并將當(dāng)前節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)。
  • 后剪枝：先從訓(xùn)練集生成一棵完整的決策樹(shù)，然后自底向上的對(duì)非節(jié)點(diǎn)進(jìn)行考察，若該節(jié)點(diǎn)對(duì)應(yīng)的子樹(shù)替換為葉節(jié)點(diǎn)能帶來(lái)決策樹(shù)泛化性能提升，則將該子樹(shù)替換為葉節(jié)點(diǎn)。
  • 預(yù)剪枝是的決策樹(shù)的很多分支都沒(méi)有展開(kāi)，這不僅降低了過(guò)擬合的風(fēng)險(xiǎn)，還顯著減少了決策樹(shù)的訓(xùn)練時(shí)間。但另一方面，有些分支的當(dāng)前劃分雖不能提升泛化性能、甚至可能導(dǎo)致泛化性能暫時(shí)下降，但在其基礎(chǔ)上進(jìn)行的后續(xù)劃分卻有可能導(dǎo)致性能顯著提高，預(yù)剪枝禁止這些分支展開(kāi)，也同時(shí)帶來(lái)了欠擬合的風(fēng)險(xiǎn)。
  • 后剪枝通常比預(yù)剪枝保留了更多的分支，一般情況下，后剪枝決策樹(shù)的欠擬合風(fēng)險(xiǎn)更小，泛化性能往往優(yōu)于預(yù)剪枝決策樹(shù)。但后剪枝過(guò)程是在完全生成決策樹(shù)之后進(jìn)行的，而且需要自底向上的對(duì)樹(shù)種所有非葉節(jié)點(diǎn)進(jìn)行一一考察，因此其訓(xùn)練時(shí)間開(kāi)銷(xiāo)要比預(yù)剪枝決策樹(shù)大得多。

四、模型優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

  • 決策樹(shù)易于理解和解釋，可以可視化分析，容易提取出規(guī)則。
  • 不需要預(yù)處理，不需要提前歸一化，處理缺失值。
  • 既可以處理離散值也可以處理連續(xù)值。

缺點(diǎn)：

  • 決策樹(shù)算法非常容易過(guò)擬合，導(dǎo)致泛化能力不強(qiáng)?？梢酝ㄟ^(guò)設(shè)置節(jié)點(diǎn)最少樣本數(shù)量和限制決策樹(shù)深度來(lái)改進(jìn)。
  • 尋找最優(yōu)的決策樹(shù)是一個(gè)難題，我們一般是通過(guò)啟發(fā)式方法，容易陷入局部最優(yōu)。可以通過(guò)集成學(xué)習(xí)之類(lèi)的方法來(lái)改善。

五、模型使用

sklearn 中的 Decision Tree（CART算法）：

from sklearn.tree import DecisionTreeClassifier
tree = DecisionTreeClassifier(max_depth=7）

決策樹(shù) 在 sklearn 中的使用也相對(duì)簡(jiǎn)單，具體參數(shù)可參考 sklearn 相關(guān)文檔，這里不再贅述。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容