ID3 C4.5/C5.0 CHAID CART與QUEST

目錄

概要

決策樹模型

特徵選擇

決策樹學習

決策樹剪枝

決策樹演算法

ID3

C4.5/C5.0

CHAID

CART

QUEST

概要

決策樹作為一種基本的分類與回歸方法（更多時候指分類），是學習數據挖掘與機器學習的首要演算法。決策樹之所以排在各類機器學習演算法首位更多是因為其概念簡單且容易理解，在入門以前，不需要學習者有多少演算法基礎。對於決策樹，可以把它理解為一組 if-then 規則的集合，也可以認為是定義在特徵空間（自變數）與類空間（因變數）的條件概率分布。通常對於分類問題決策樹處理速度較快，其演算法也有較強的可讀性。決策樹的學習策略是基於損失函數最小化原則，生成決策樹後可對決策樹進行剪枝以防止決策樹過於複雜而產生過度擬合。

決策樹生成的過程就是不斷進行特徵選擇的過程，因而熵和基尼指數等概念被引入進來。通過遍歷計算每類特徵的信息貢獻，一個最優的決策樹得以被構造出來。如果說決策樹是一個if-then 規則的集合，其本質在於由決策樹的根結點到葉節點的每一條路徑構建了一條規則的條件，而葉節點的類對應著規則的結論。如果說決策樹還表示給定特徵空間下類的條件概率分布，這一條件概率分布定義在特徵空間的一個劃分上。而決策樹所表示的條件概率分布由各個單元給定條件下類的條件概率分布組成。

決策樹模型

一棵決策樹通常由結點和有向邊組成，結點包括根結點、內部結點和葉節點，根結點和內部節點表示一個特徵或者屬性，而葉節點表示一個具體分類，一顆常見的決策樹如下：

特徵選擇

所謂特徵選擇，即在於選取可以對訓練數據進行較好分類的特徵。在統計與機器學習里叫特徵選擇，在數據挖掘里又叫屬性測試條件。通常特徵選擇的準則是信息增益、信息增益比或者基尼指數等。

說到信息增益那就不得不引入熵的概念了。在資訊理論中，熵表示對隨機變數不確定度的度量（偷偷說一句，小編的研究生論文做的就是最大熵貝葉斯），當 X 為一個離散隨機變數時，其熵 H（X）定義為

而條件熵 H（YX）表示在已知隨機變數 X 的條件下隨機變數 Y 的不確定性。隨機變數 X 給定的條件下隨機變數 Y 的條件熵H（YX）定義為

所謂的信息增益表示在已知特徵 X 的信息而使得類 Y 的信息的不確定性減少的程度。若特徵 A 對訓練數據集 D 的信息增益為 g(D,A) ，則g(D,A) 定義為集合 D 的經驗熵 H(D) 與特徵 A 給定條件下 D 的經驗條件熵 H（DA）之差

為選擇最好的特徵進行分類，需對訓練數據集計算每個特徵的信息增益，通常信息增益值最大的特徵被選為最優分類特徵。而信息增益比定義為信息增益 g(D,A) 與訓練數據集 D 關於特徵 A 的值的熵 HA(D) 之比

決策樹學習

決策樹學習本質上是從訓練集中歸納出一種分類規則。能對訓練數據集進行完美分類的決策樹可能有許多個也可能一個也沒有，而我們需要的一個能對訓練集進行最大程度分類的決策樹，即分類規則出現錯誤最小的決策樹，同時該決策樹還能對未知數據集具有很好的泛化能力。從概率模型的角度看，決策樹學習是由訓練數據集估計條件概率模型，基於特徵空間劃分的類的條件概率模型有無窮多個，而我們選擇的條件概率模型應該不僅對訓練數據有很好的擬合能力，且對未知數據有很好的預測。

決策樹學慣用損失函數來表示對未知數據進行很好的預測能力的目標。決策樹學習的損失函數通常是正則化的極大似然函數，學習策略則是以損失函數為目標函數的最小化。

決策樹剪枝

按照決策樹學習方法生成的決策樹可能對訓練數據集有很好的分類能力，但對未知的測試數據集卻未必有很好的分類能力，即有可能產生擬合過度的情況，這時就需要對決策樹自下而上的進行剪枝，將複雜的樹進行簡化，使其具有較好的泛化能力。決策樹剪枝演算法可描述為：計算每個結點的經驗熵，然後遞歸地從樹的葉節點向上回縮，如果對應葉節點的損失函數值要大於父節點的損失函數值，則進行剪枝，即將父節點變為新的葉節點。不斷的遞歸回縮，直至不能繼續剪枝為止，以此便可得到損失函數最小的決策子樹。

由上我們可以看出，決策樹學習方法包括特徵選擇、決策樹的生成與決策樹的剪枝這三個過程。下面就結合具體的決策樹演算法進行介紹。

決策樹演算法

下表是由15個樣本組成的貸款申請訓練數據集，包括四個特徵（年齡、有無工作、有無房子、信貸情況）和一個類別（是否同意貸款），以此訓練數據進行決策樹演算法 的分析。（表格來自李航. 統計學習方法）

ID3

ID3演算法的全稱叫 Iterative Dichotomiser 3（迭代二叉樹三代），是由 Ross Quinlan於1986年提出的決策樹思想方法，當然 C4.5/C5.0 演算法也是他提出的。ID3 演算法的核心就是在決策樹各個結點上應用信息增益準則進行特徵選擇，以此遞歸地構建決策樹。對於上表中的貸款數據集應用 ID3 演算法構建決策樹。

首先計算每個特徵的信息增益，以此來選擇最優特徵進行分類。分別以 A1，A2，A3，A4表示年齡、有工作，有房子和信貸情況這4個特徵，則各特徵的信息增益可計算為

同理可計算A2，A3，A4 的信息增益值為 0.324，0.420和0.363，可見特徵A3的信息增益值最大，首選A3作為最優特徵進行決策樹構造。

特徵A3將訓練數據集劃分為兩個子集D1（A3取值為是，有房）D2（A3取值為否，無房），然後繼續按照信息增益條件選擇餘下的特徵，計算A1，A2和A4的信息增益值。

根據計算結果選擇信息增益最大的 A2（有無工作）作為結點特徵，該結點可引出兩個子節點：一個是有工作的子節點，一個是無工作的子節點，分屬於兩個子節點的樣本均屬各自同一類別，因此該決策樹只用了兩個特徵即可構造完成。

以上便是 ID3演算法構造決策樹的過程。

C4.5/C5.0

C4.5演算法與 ID3 演算法極為相似，只是在特徵選擇上有所不同，算是一種對 ID3 演算法的改進了。C4.5演算法在決策樹生成過程中，用信息增益比來選擇特徵。信息增益比的定義如前文所述。而 C5.0 演算法作為 C4.5的改進版，其演算法原理都是一致的，都是採用信息增益比來進行特徵選擇，但C5.0適用於處理大數據集，採用 Boosting 方式來提高模型準確率，計算速度較高，對計算內存佔用也較少。關於 C4.5和C5.0的實際計算可參考R語言實現方式。

CHAID

CHAID演算法全稱叫做卡方自動交叉檢驗法（Chi-squaredAutomatic Interaction Detector），是 Kass於1974年提出來一種決策樹演算法。這裡涉及到卡方檢驗，故在此對此進行簡單解釋。首先需要明確的一點是，卡方檢驗針對的是分類變數，是統計樣本的實際觀察值與理論觀察值之間偏離程度的量，這個偏離程度決定了卡方值的大小，偏離程度越大，卡方值也就越大，若二者無差異，卡方值就為零。

CHAID演算法通過計算類別變數與特徵變數之間的相關性檢驗統計量的 p 值，即卡方統計量對應的 p值，p 值越小，說明特徵變數與類別變數之間的關係越密切，應當被選為最佳分組特徵變數。然後繼續按此準則選擇後續特徵變數，直至所有樣本被分類完畢。CHAID演算法在構建決策樹時具有一定的優勢，它是從統計顯著性的角度來確定特徵變數和分割數值，對決策樹的分枝過程優化明顯。

CART

CART（classification and regression tree）分類與回歸樹演算法是由 Breiman等人在1984年提出的一種決策樹演算法，CART 演算法既可用於分類也可用於回歸，是一種應用廣泛的決策樹學習方法。

CART是在給定輸入隨機變數X條件下輸出變數Y的條件概率分布的學習方法。CART假設決策樹是二叉樹，內部結點特徵的取值為「是」和「否」。這樣的決策樹等價於遞歸地二分每個特徵，將輸入空間即特徵空間劃分為有限個單元，並在這些單元上確定預測的概率分布，也就是在輸入給定的條件下輸出條件概率分布。

與ID3 C4.5/C5.0不同的是，CART演算法構造決策樹是通過基尼指數來選擇最優特徵的，同時也決定該特徵的最優二值切分點。在特徵 A 的條件下，集合 D 的基尼指數定義為

根據基尼指數最小原則選取最優結點，不斷遞歸調用該準則直至滿足停止條件生成CART 決策樹。依照前面貸款情況的例子分別計算 A1 A2 A3 A4 特徵的基尼指數，例如特徵 A1 的基尼指數

A1=1和A1=3相等且最小，所以二者都可以作為A1的最優切分點。

同理可計算A2 A3 的基尼指數為0.32,0.27，以此可繼續計算A4 的基尼指數。

依照CART演算法生成的決策樹和ID3演算法生成的決策樹完全一致。

QUEST

QUEST全稱為 Quick Unbiased Efficient Statistical Tree，是Loh&Shih提出的一種二元分類的決策樹演算法。QUEST會以不同的策略處理特徵變數和切分點的選擇問題，其演算法運行過程要比CART更加快速有效。

QUEST演算法在選擇特徵變數時，對於定類屬性採用卡方檢驗方法，這點和CHAID類似，對於定矩屬性則採用 F 檢驗方法，選擇對應 p 值最小且小於顯著性水平的特徵變數作為最佳分類變數。

小結

對於各類決策樹演算法，R語言中都有相應的實現方式，對於CART演算法有rpart包，對於 C5.0演算法有C50包，而對於CHAID演算法也有CHAID包，此外還有 party 包等決策樹實現方法。決策樹演算法總體而言並不難懂，關鍵的是在掌握機器學習原理的基礎上會使用R或者Python進行實際的分析。

參考資料

李航 統計學習方法

一個數據科學踐行者的學習日記

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！