決策樹 —— 最符合人類思維的機器學習方法

機器學習基礎演算法python程式碼實現可參考：zlxy9892/ml_code

1 決策樹的基本模型

在很多初學者開始學習機器學習或者資料探勘時，大多數教程都會從決策樹（decision tree）開始，決策樹是一類常見的機器學習方法，可以幫助我們解決分類與迴歸兩類問題。以決策樹的作為學習的起點原因很簡單，因為它非常符合人類處理問題的方式，所以決策方式顯得極為自然，且模型的解釋性很好，能夠讓使用者知道為什麼這個決策結果是我所希望的那樣（樹形結構簡單易懂）。

分類決策數模型是一種描述對例項進行分類的樹形結構。決策樹由結點（node）和有向邊（directed edge）組成。結點包含了一個根結點（root node）、若干個內部結點（internal node）和若干個葉結點（leaf node）。內部結點表示一個特徵或屬性，葉結點表示一個類別。

那麼，最為關鍵的問題就是，如何根據已知的資料集，來進行決策樹的學習，構造一顆泛化能力強，即處理未見示例能力強的決策樹。為此，決策樹學習通常包括 3 個步驟：

特徵選擇

、

決策樹的生成

、

決策樹的修剪

。現有的關於決策樹學習的主要思想主要包含以下 3 個研究成果：

由

Quinlan

在 1986 年提出的

ID3

演算法

由

Quinlan

在 1993 年提出的

C4.5

演算法

由

Breiman

等人在 1984 年提出的

CART

演算法

2 劃分選擇

決策樹學習的過程中，最為關鍵的就是如何

選擇最優劃分屬性

。一般而言，隨著劃分過程不斷進行，我們希望決策樹的分支結點所包含的樣本儘可能屬於同一類別，即

結點的 “純度” (purity)

越來越高。

2.1 資訊增益

“資訊熵” （information entropy）是度量樣本集合純度最常用的一種指標。假定當前樣本集合

中第

類樣本所佔的比例為

$p_k\;(k=1,2,\dots, \mid \mathcal{Y} \mid)$

，則

的資訊熵定義為：

$\displaystyle{ Ent(D) = -\sum_{k=1}^{\mid \mathcal{Y} \mid} p_k\log_2{p_k} }$

的值越小，則

的純度越高。資訊熵表達一個數據所包含的資訊量，或者說是資訊的複雜程度、不確定性程度。例如當某一隨機變數只取 0， 1 兩個值時，當取 0 的機率 = 取 1 的機率 = 0。5 時，資訊熵達到最大值，值為 1，可以看做此時系統的不確定性最高；當某一取值的機率為 0，另一取值機率為 1 時，此時可以認為系統是完全確定的，因為只能取到 0 或 1，相應的，資訊熵取值為 0。

假設樣本集

中某一離散屬性

有

個可能的取值

${a^1, a^2, \dots, a^V}$

，若使用

來對樣本集

進行劃分，則會產生

個分支結點（注意：這裡是預設把離散屬性的每個可能的取值都進行劃分），其中第

個分支結點包含了

中所有在屬性

上取值為

的樣本，記為

。我們可根據資訊熵的定義計算出

的資訊熵。再考慮到不同分支結點所包含的樣本數不同，給分支結點賦予權重

$\frac{\mid D^v \mid}{\mid D \mid}$

，即樣本數越多的分支結點的影響越大，於是可以計算出用屬性

對樣本集

進行劃分所獲得的

“資訊增益“

（information gain）：

$\displaystyle{ Gain(D,a) = Ent(D) - \sum_{v=1}^{V} \frac{\mid D^v \mid}{\mid D \mid} Ent(D^v) }$

一般而言，資訊增益越大，則意味著使用屬性

來進行劃分所獲得的 “純度提升” 越大。因此，我們可以用資訊增益來進行決策樹的劃分屬性選擇。

著名的 ID3 決策樹學習演算法就是以資訊增益為準則來選擇劃分屬性。

2.2 資訊增益率

使用上述的資訊增益來作為劃分準則是否就一定是最優策略呢？我們試想這樣的情況，若我們獲取的樣本集資料中包含了一條屬性是每個樣本的 ID 號，那麼根據資訊增益的計算公式可以得到，當使用 ID 號作為劃分屬性時，它的資訊增益率極高，這很容易理解：“ID 號” 代表了對每個樣本的唯一標識，透過它來劃分樣本集，那麼每個分支結點僅包含一個樣本，這些分支結點的純度達到了最大。然而，這樣的決策樹顯然並非我們所希望得到的，因為它不具備泛化能力，無法對新樣本進行有效預測。

仔細分析來看，資訊增益準則對可取值數目較多的屬性有所偏好，為減少這種可能帶來的不利影響，

著名的 C4.5 決策樹演算法不直接使用資訊增益，而是使用 “增益率” (gain ratio) 來選擇最優劃分屬性

。在資訊增益計算公式的基礎上，增益率定義為：

$\displaystyle{ Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)} }$

其中，

$\displaystyle{ IV(a) = - \sum_{v=1}^{V} \frac{\mid D^v \mid}{\mid D \mid} \log_2{\frac{\mid D^v \mid}{\mid D \mid}} }$

稱為屬性

的 “固定值” （intrinsic value），對比資訊熵公式可以發現，其實

就是等同於特徵

的資訊熵（有些書籍將其記為

），其中的

$\frac{\mid D^v \mid}{\mid D \mid}$

正是對屬性

取值為

的機率的極大似然估計。那麼，若屬性

的可能取值數目越多（即

越大），則

的值通常會越大。

需要注意的是，增益率準則對可能取值數目較少的屬性有所偏好，因此，C4.5 演算法並不是直接選擇增益率最大的候選劃分屬性，而是使用了一個啟發式策略：先從候選劃分屬性中找出資訊增益高於平均水平的屬性，再從中選擇增益率最高的。

2.3 基尼指數

分類與迴歸樹（classification and regression tree， CART）模型，是應用很廣泛的決策樹學習方法，從其命名可以看出，它可以解決分類和迴歸兩類問題。與 ID3 和 C4。5 不同之處在於，CART 使用 “基尼指數” （Gini index）來選擇劃分屬性。資料集的純度可用基尼值來度量：

$\displaystyle{ \begin{align*} Gini(D) &= \sum_{k=1}^{\mid \mathcal{Y} \mid} \sum_{k$