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

05-25

來自專欄機器學習知識點

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) 是度量樣本集合純度最常用的一種指標。假定當前樣本集合 $D$ ? 中第 $k$ ? 類樣本所佔的比例為 $p_k;(k=1,2,dots, mid mathcal{Y} mid)$ ?，則 ? $D$ 的信息熵定義為：

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

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

? 假設樣本集 $D$ 中某一離散屬性 $a$ 有 $V$ 個可能的取值 ${a^1, a^2, dots, a^V}$ ，若使用 $a$ 來對樣本集 $D$ 進行劃分，則會產生 $V$ 個分支結點 (注意：這裡是默認把離散屬性的每個可能的取值都進行劃分)，其中第 $v$ 個分支結點包含了 $D$ 中所有在屬性 $a$ 上取值為 $a^v$ 的樣本，記為 $D^v$ 。我們可根據信息熵的定義計算出 $D^v$ 的信息熵。再考慮到不同分支結點所包含的樣本數不同，給分支結點賦予權重 $frac{mid D^v mid}{mid D mid}$ ，即樣本數越多的分支結點的影響越大，於是可以計算出用屬性 $a$ 對樣本集 $D$ 進行劃分所獲得的 「信息增益「 (information gain)：

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

? 一般而言，信息增益越大，則意味著使用屬性 $a$ 來進行劃分所獲得的 "純度提升" 越大。因此，我們可以用信息增益來進行決策樹的劃分屬性選擇。

? 著名的 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}} }$

$IV(a)$ 稱為屬性 $a$ 的「固定值」 (intrinsic value)，對比信息熵公式可以發現，其實 $IV(a)$ 就是等同於特徵 $a$ 的信息熵 (有些書籍將其記為 $H_a(D)$ )，其中的 $frac{mid D^v mid}{mid D mid}$ 正是對屬性 $a$ 取值為 $a^v$ 的概率的極大似然估計。那麼，若屬性 $a$ 的可能取值數目越多 (即 $V$ 越大)，則 $IV(a)$ 的值通常會越大。

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

2.3 基尼指數

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

? $displaystyle{ egin{align*} Gini(D) &= sum_{k=1}^{mid mathcal{Y} mid} sum_{k eq k} p_k p_{k} \ &= 1 - sum_{k=1}^{mid mathcal{Y} mid} p_k^2 end{align*} }$

也可以寫成：

? $displaystyle{ Gini(D) = sum_{k=1}^{mid mathcal{Y} mid} p_k (1-p_k) = 1 - sum_{k=1}^{mid mathcal{Y} mid} p_k^2 }$

其中， $p_k$ 為數據集 $D$ 中輸出值為 $k$ 的概率，根據實際數據，可採用 $frac{mid D^k mid}{mid D mid}$ 來進行估計。

? 直觀來說， $Gini(D)$ 反映了從數據集 $D$ 中隨機抽取兩個樣本，其類別標記不一致的概率。因此， $Gini(D)$ 越小，則數據集 $D$ 的純度越高。

? 基於此，對於屬性 $a$ 的基尼指數定義為：

? $displaystyle{ Gini\_index(D,a) = sum_{v=1}^{V} frac{mid D^v mid}{mid D mid} Gini(D^v) }$

? 於是，我們在候選屬性集合 $A$ 中，選擇那個使得劃分後基尼指數最小的屬性作為最優劃分屬性，即：

? $displaystyle{ a_* = arg min_{a in A} Gini\_index(D,a) }$

2.4 連續值處理

? 到目前為止，我們僅討論了基於離散屬性來生成決策樹。現實學習任務中常會遇到連續屬性，因此，有必要討論如何在決策樹學習中使用連續屬性。

? 藉助連續屬性離散化技術，最簡單的策略是採用二分法 (bi-partition) 對連續屬性進行處理，這正是 C4.5 決策樹演算法中採用的機制，CART 也採用該策略。

? 給定樣本集 $D$ 和連續屬性 $a$ ，假定 $a$ 在 $D$ 上出現了 $n$ 個不同的取值，將這些取值從小到大進行排序，記為 ${ a^1, a^2, dots, a^n }$ 。基於劃分點 $t$ 可將 $D$ 分為兩個子集，記為 ${-, +}$ 。顯然，對於屬性取值 $a^{i}$ 與 $a^{i+1}$ 來說，在區間 $[a^i, a^{i+1})$ 中取任意值所產生的劃分結果相同。因此，對連續屬性 $a$ ，我們可考察包含 $n-1$ 個元素的候選劃分點集合：

? $displaystyle{ T_a = { frac{a^i + a^{i+1}}{2} mid 1 leqslant i leqslant n-1 } }$

即把每個區間的中位點作為候選劃分點。然後，我們就可像離散屬性值一樣來考察這些劃分點，選取最優的劃分點進行樣本集合的劃分。

? 在 CART 應用於回歸問題時，同樣也是採用了二分法，將劃分的兩個子集分別求得輸出量 $y$ 的均值，以此作為輸出值的估計，記為 $hat{y}$ 。在尋找最優切分點時，通過計算兩個子區域的估計值與每個輸出的真值之間的平方誤差，選取使得平方誤差總和最小的作為最優切分點。具體的，求解：

? ? $displaystyle{ arg min_t left[ sum_{i in -}(y_i - hat{y_i})^2 + sum_{i in +}(y_i - hat{y_i})^2 ight]}$

? 使用該方法構建的回歸樹也稱為最小二乘回歸樹。

3 關於剪枝處理

? 剪枝 (pruning) 是決策樹學習演算法對付「過擬合」的主要手段。在決策樹學習中，為了儘可能正確分類訓練樣本，結點劃分過程將不斷重複，有時會造成決策樹分支過多，這時就可能因針對訓練樣本學得「太好」了，以至於把訓練集自身的一些特點當作所有數據都具有的一般性質而導致過擬合。因此，可通過主動去掉一些分支來降低過擬合的風險。

? 決策樹剪枝的基本策略有「預剪枝」 (prepruning) 和「後剪枝」 (postpruning)。

預剪枝 是指在決策樹生成過程中，對每個結點在劃分前先進行估計，若當前節點的劃分不能帶來決策樹泛化性能的提升，則停止劃分並將當前結點標記為葉結點；
後剪枝 則是先從訓練集生成一顆完整的決策樹，然後自底向上地對非葉結點進行考察，若將該結點的子樹替換為葉結點能帶來決策樹泛化性能的提升，則將該子樹替換為葉結點。

4 參考文獻與相關資料

Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1 (1), 81-106.
Quinlan, J. R. (1992). C4.5: programs for machine learning. ,1.
Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and regression trees.