淺入淺出：決策樹

1 一個例子說明決策樹

決策樹是有監督學習，即根據訓練集的『屬性和標籤』，生成決策樹，之後根據新數據的 『屬性』，採用樹結構進行決策的方法。先來舉個例子，現在有丈母娘進行的選婿活動，發生了以下對話：

「青年 A」

青年 A ：沒有，但是……

「青年 B」

青年 B ：有。

「青年 C」

准丈母娘 ： 有房嗎？

上述過程就是採用樹進行決策的過程，該過程的樹結構如下圖。

決策樹的決策過程直白易理解，上面的例子也說明了這一點。但是，決策樹中很關鍵的內容在例子中沒有提及，該部分內容就是決策樹的生成，也就是建模過程。

2 決策樹的生成

在上面的例子中看得出來，重要的問題要先問，比如是否有房。也就是說，我們需要找到一個描述屬性重要性的數值，該數值可以反映其對決策結果的重要性程度，如『是否有房』更影響決策結果，還是『是否有車』更影響決策結果。

在這之前，先介紹一個概念： 信息熵 ， 信息熵 是指信息的不確定程度，熵越大越不確定。比如現在有一群准女婿，准丈母娘不確定其中誰適合結婚，誰不適合結婚，是否適合結婚的不確定程度就是 信息熵 。現在，按照是否有房將這群准女婿分成兩組，我們知道，有房組中將很有可能適合結婚，沒房組不適合結婚，也就是說：在是否有房的條件下，是否適合結婚的不確定程度大大降低。我們將某條件下的信息不確定度稱為 條件熵 。

信息熵 - 條件熵 = 信息增益 ， 信息增益 就是我們尋找的數值。 某屬性的 信息增益 大，則其對決策結果的重要性大。

實際上，採用 信息增益 作為準則來選擇最優劃分屬性 (最重要屬性) 的演算法是 ID3 ，該演算法會偏好哪些取值數目較多的屬性 (是否有房是屬性，該屬性的取值有 「有、沒有」)，為了減少偏好， C4.5 採用 增益率 作為劃分準則， 增益率 大體上可以理解為信息增益除以取值數目。上述的兩種準則都是基於熵模型的，需要進行大量對數計算。有沒有一個準則不需要對數計算，又能近似等價於熵模型呢？答案就是 基尼係數 。採用 基尼係數 作為準則的演算法是 CART ，也是目前大部分決策樹實現所採用的演算法。當然，這是淺入淺出，實際上考慮和改進的地方更大，如果需要深入的學習，請參考其他相關資料。