第4章：決策樹內容決策樹的概念決策樹學習算法的基本框架屬性選擇屬性測試剪枝處理應用案例

1決策樹的定義和工作原理

定義：

工作原理：決策樹通過建立一個樹形結構來揭示屬性集與類標簽之間的關系。決策樹能夠將復雜的分類問題分解成一系列簡單的決策問題，從而實現對實例的有效分類。

決策樹概念2決策樹是一種監(jiān)督學習模型，主要用于分類任務。它通過構建一棵樹形結構來對數據進行分類。決策樹包含一個稱為“根”的結點，這個結點沒有輸入邊。沒有輸出邊的結點為葉子結點，其他結點為內部結點，根結點和內部結點都是測試結點。每個測試結點對一個屬性執(zhí)行一個測試，測試結點的輸出邊被標記為屬性的不同取值，以便根據這些值將數據劃分到不同的子結點。每個葉子結點指定了分類標簽，代表決策樹對數據進行分類的最終結果。決策樹的例子

決策樹概念4決策樹的數據分類行為2決策樹的例子

決策樹概念決策樹包含葉結點和非終端結點（包括根結點和其他內部結點）。每個葉結點都有一個類別標簽。非終端結點包含屬性測試條件，用于區(qū)分具有不同屬性的記錄。從根結點開始，對記錄應用測試條件，然后根據測試結果選擇合適的分支，這將導致分支要么進入另一個內部結點，應用新的測試條件，要么進入葉結點。每個葉子結點指定了分類標簽，代表決策樹對數據進行分類的最終結果。目標：根據給定的訓練數據集構建一個決策樹模型，使它能夠對新的實例進行正確的分類。基本數據集：Jeeves訓練數據集合問題：Bertie喜歡打網球，讓Jeeves為預訂場地。Jeeves需要預測Bertie是否打網球，因此記錄了Bertie的一些相關信息（Jeeves訓練數據集合）

決策樹學習算法的基本框架6DayOutlookTempHumidityWindTennis?1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNoJeeves訓練數據集合共有14個實例，包括9個正例和5個反例；涵蓋了4個屬性Outlook，Temp，Humidity和Wind。決策樹的停止條件

決策樹學習算法的基本框架7停止條件基本情況1：所有實例都屬于同一類別

基本情況2：沒有剩余的屬性可以測試

基本情況3：沒有剩余的實例停止條件（基本情況1：所有實例都屬于同一類別）例題1給定屬性測試順序，構建決策樹

屬性Outlook的測試

決策樹——決策樹學習算法的基本框架8為了使用指定的測試屬性順序為Jeeves數據集構建完整的決策樹，將遵循以下步驟：1、從根結點開始，并測試Outlook屬性。2、如果Outlook=Sunny，測試溫度（Temp）

屬性。如果Outlook=Rain，測試風速

（Wind）屬性。3、對于所有其他分支，先測試濕度Humidity）

屬性，

然后再測試風速（Wind）。數據集根據給定測試順序，首先測試Outlook。Outlook有三個值：Sunny、Overcast和Rain。將實例分為三個分支。實例1的Outlook等于Sunny，所以它進入左分支。實例3的Outlook等于Overcast，所以它進入中間分支，等等。停止條件（基本情況1：所有實例都屬于同一類別）例題1給定屬性測試順序，構建決策樹

屬性Outlook的測試及其葉子結點生成

決策樹——決策樹學習算法的基本框架9為了使用指定的測試屬性順序為Jeeves數據集構建完整的決策樹，將遵循以下步驟：1、從根結點開始，并測試Outlook屬性。2、如果Outlook=Sunny，測試溫度（Temp）

屬性。如果Outlook=Rain，測試風速

（Wind）屬性。3、對于所有其他分支，先測試濕度Humidity）

屬性，

然后再測試風速（Wind）。數據集在中間分支中，所有實例都是正例。沒有必要測試另一個屬性，因此可以做出決定，然后創(chuàng)建一個帶有標簽Yes的葉子結點，并且完成了這個分支。停止條件（基本情況1：所有實例都屬于同一類別）例題1給定屬性測試順序，構建決策樹

屬性Temp的測試

決策樹——決策樹學習算法的基本框架10為了使用指定的測試屬性順序為Jeeves數據集構建完整的決策樹，將遵循以下步驟：1、從根結點開始，并測試Outlook屬性。2、如果Outlook=Sunny，測試溫度（Temp）

屬性。如果Outlook=Rain，測試風速

（Wind）屬性。3、對于所有其他分支，先測試濕度Humidity）

屬性，

然后再測試風速（Wind）。數據集首先查看左分支，其中有2個正例和3個負例。因此，根據給定的順序，測試下一個屬性，即溫度（Temp）。Temp有三個值：Hot（熱）、Mild（溫和）和Cool（涼爽）。然后再次創(chuàng)建三個分支。這五個實例被這些分支分割。每個結點將重復這個過程。首先，檢查所有實例是否屬于同一類別。如果是，則創(chuàng)建一個帶有類別標簽的葉子結點并停止。否則，選擇下一個屬性進行測試，并根據選擇的屬性分割實例。停止條件（基本情況1：所有實例都屬于同一類別）

最終的決策樹

決策樹——決策樹學習算法的基本框架11停止條件（基本情況2：沒有剩余的屬性可以測試）例題2使用和例1相同的屬性測試順序構建決策樹

決策樹——決策樹學習算法的基本框架12DayOutlookTempHumidityWindTennis?1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo15SunnyMildHighWeakNo16SunnyMildHighWeakYes17SunnyMildHighStrongYes修正的Jeeves訓練數據集合（17個實例）數據集在原來Jeeves訓練集中添加了3個實例（紅色），建立了一個修正Jeeves訓練集停止條件（基本情況2：沒有剩余的屬性可以測試）例題2使用和例1相同的屬性測試順序構建決策樹

決策樹——決策樹學習算法的基本框架13為了使用指定的測試屬性順序為Jeeves數據集構建完整的決策樹，將遵循以下步驟：1、從根結點開始，并測試Outlook屬性。2、如果Outlook=Sunny，測試溫度（Temp）

屬性。如果Outlook=Rain，測試風速

（Wind）屬性。3、對于所有其他分支，先測試濕度Humidity）

屬性，

然后再測試風速（Wind）。數據集Jeeves訓練集的決策樹停止條件（基本情況2：沒有剩余的屬性可以測試）例題2使用和例1相同的屬性測試順序構建決策樹

決策樹——決策樹學習算法的基本框架14為了使用指定的測試屬性順序為Jeeves數據集構建完整的決策樹，將遵循以下步驟：1、從根結點開始，并測試Outlook屬性。2、如果Outlook=Sunny，測試溫度（Temp）

屬性。如果Outlook=Rain，測試風速

（Wind）屬性。3、對于所有其他分支，先測試濕度Humidity）

屬性，

然后再測試風速（Wind）。數據集由測試條件（Outlook是Sunny，Temperature是Mild，Humidity是High）構成的測試分支停止條件（基本情況2：沒有剩余的屬性可以測試）例題2使用和例1相同順序的屬性測試構建決策樹

決策樹——決策樹學習算法的基本框架15為了使用指定的測試屬性順序為Jeeves數據集構建完整的決策樹，將遵循以下步驟：1、從根結點開始，并測試Outlook屬性。2、如果Outlook=Sunny，測試溫度（Temp）

屬性。如果Outlook=Rain，測試風速

（Wind）屬性。3、對于所有其他分支，先測試濕度Humidity）

屬性，

然后再測試風速（Wind）。注意：當我們沒有屬性可以測試時，通常使用多數類別作為最終的決策經過Outlook，Temperature和Humidity屬性測試后，屬性Wind的測試結果停止條件（基本情況3：如果沒有剩下任何實例）例題3使用和例1相同的屬性測試順序構建決策樹

決策樹——決策樹學習算法的基本框架16DayOutlookTempHumidityWindTennis?1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo15SunnyHotHighWeakNo修正的Jeeves訓練數據集合（15個實例）數據集停止條件（基本情況3：如果沒有剩下任何實例）例題3使用和例1相同的屬性測試順序構建決策樹

經過三個屬性測試（Temp，Wind和Humidity）后，屬性Outlook的測試結果

決策樹——決策樹學習算法的基本框架17數據集決策樹學習算法的基本框架

決策樹——決策樹學習算法的基本框架屬性選擇

屬性選擇：在每一步子集劃分時，選擇一個對分類貢獻最大的屬性

決策樹——屬性選擇191、在決策樹算法中，希望選擇一個屬性，能夠幫助更快地做出決策，即最大程度地減少對目標變量的不確定性。2、為了衡量這種不確定性的減少，我們需要計算考慮一個

屬性前后的不確定性的變化。3、用集合的熵來表示不確定性，刻畫不確定性的變化程度的常用的方法：

信息增益、增益率和基尼指數的方法。4、ID3算法采用信息增益ID3的改進版C4.5算法采用信息增益率

決策樹——屬性選擇20自信息和熵

決策樹——屬性選擇21

決策樹——屬性選擇22互信息是信息論中的概念，用來衡量兩個隨機變量之間的相互依賴性，它表示知道一個變量后，另一個變量的不確定性減少的程度

決策樹——屬性選擇23

決策樹——屬性選擇24例題4

決策樹——屬性選擇25DayOutlookTempHumidityWindTennis?1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNoJeeves訓練數據集合1、Jeeves訓練數據集

屬性：

OutlookTempHumidity

Wind2、14個實例：9個正例5個反例例題4

決策樹——屬性選擇26

例題4

決策樹——屬性選擇27

決策樹的根結點的數據分布情況解

集合的熵

關于屬性Wind的信息增益及信息增益率：

決策樹——屬性選擇解

關于屬性Humidity的信息增益及信息增益率：

決策樹——屬性選擇29解

關于屬性Outlook的信息增益及信息增益率：

決策樹——屬性選擇30解

關于屬性Temp的信息增益及信息增益率：

決策樹——屬性選擇例5對于Jeeves訓練數據集合，利用ID3算法建立決策樹。對于根結點，根據上面例題的結果，Outlook屬性具有最大的信息增益

決策樹——屬性選擇

決策樹的根結點劃分例5對于Jeeves訓練數據集合，利用ID3算法建立決策樹。1）對于Outlook=Sunny情況

決策樹——屬性選擇

當前結點（Outlook=Sunny）的數據分布例5對于Jeeves訓練數據集合，利用ID3算法建立決策樹。

1）對于Outlook=Sunny情況

計算屬性Temp的信息增益

決策樹——屬性選擇例5對于Jeeves訓練數據集合，利用ID3算法建立決策樹。1）對于Outlook=Sunny情況

計算屬性Humidity的信息增益

決策樹——屬性選擇例5對于Jeeves訓練數據集合，利用ID3算法建立決策樹。

1）對于Outlook=Sunny情況

計算屬性Wind的信息增益

決策樹——屬性選擇Humidity具有最大的信息增益，因此選擇作為劃分屬性例5對于Jeeves訓練數據集合，利用ID3算法建立決策樹。

2）對于Outlook=Rain情況

決策樹——屬性選擇當前結點（Outlook=Rain）數據分布例5對于Jeeves訓練數據集合，利用ID3算法建立決策樹。

2）對于Outlook=Rain情況

計算屬性Temp的信息增益

決策樹——屬性選擇例5對于Jeeves訓練數據集合，利用ID3算法建立決策樹。

2）對于Outlook=Rain情況

計算屬性Humidity的信息增益

決策樹——屬性選擇例5對于Jeeves訓練數據集合，利用ID3算法建立決策樹。

2）對于Outlook=Rain情況

計算屬性Wind的信息增益

決策樹——屬性選擇

我們選擇Wind，因為它的預期信息增益最大例5對于Jeeves訓練數據集合，利用ID3算法建立決策樹。

最終的生成樹

由Jeeves訓練數據集合生成的決策樹

決策樹——屬性選擇連續(xù)值的屬性

決策樹——屬性測試42二元屬性測試條件到目前為止，所涉及的屬性都是離散屬性。在處理離散屬性時，決策樹算法可以選擇允許多元分割或限制為二元分割。允許多元分割的決策樹可以捕捉到更復雜的數據結構，但可能會導致樹變得更深，計算成本更高。限制為二元分割的決策樹更簡單，計算效率更高，但可能無法捕捉到某些復雜的模式。二元屬性

測試條件生成兩個潛在的結果:連續(xù)值的屬性

決策樹——屬性測試43多元屬性測試條件

連續(xù)值的屬性

決策樹——屬性測試44

連續(xù)屬性的離散化處理連續(xù)值的屬性

決策樹——屬性測試45DayOutlookTempHumidity%WindTennis?1SunnyHot80WeakNo2SunnyHot82StrongNo3OvercastHot84WeakYes4RainMild85WeakYes5RainCool60WeakYes6RainCool62StrongNo7OvercastCool65StrongYes8SunnyMild86WeakNo9SunnyCool63WeakYes10RainMild64WeakYes11SunnyMild65StrongYes12OvercastMild83StrongYes13OvercastHot60WeakYes14RainMild83StrongNo修正Jeeves訓練數據集合（humidity連續(xù)值取值，濕度的單位：%）連續(xù)值的屬性

決策樹——屬性測試46DayOutlookTempHumidity%WindTennis?5RainCool60WeakYes13OvercastHot60WeakYes6RainCool62StrongNo9SunnyCool63WeakYes10RainMild64WeakYes7OvercastCool65StrongYes11SunnyMild65StrongYes1SunnyHot80WeakNo2SunnyHot82StrongNo12OvercastMild83StrongYes14RainMild83StrongNo3OvercastHot84WeakYes4RainMild85WeakYes修正Jeeves訓練數據集合（按照humidity值排序）連續(xù)值的屬性

決策樹——屬性測試47

T={61.0,62.5,63.5,64.5,72.5,81.0,82.5,83.5,84.5}1、根結點包含的14個訓練樣本在Humidity屬性上有10個不同的取值，計算該屬性的分割點集合2、計算分割點的信息增益連續(xù)值的屬性

決策樹——屬性測試48

過擬合

決策樹——剪枝處理49決策樹優(yōu)點：結構相對簡單，易于解釋性強。與神經網絡形成鮮明對比，后者結構復雜，往往難以解釋其工作原理。即使是在數據量較小的情況下，決策樹也能生成一個合理的模型。相比之下，神經網絡在處理小數據集時往往效果不佳過擬合現象：神經網絡在處理小數據集時往往效果不佳，且容易過擬合。過擬合仍然是在構建決策樹時需要克服的一個主要挑戰(zhàn)。決策樹學習算法可以不斷生長樹，直到它完美地分類訓練集中的所有實例。然而，這并不一定是一種理想的行為，因為這很容易導致過擬合。過擬合

決策樹——剪枝處理50DayOutlookTempHumidityWindTennis?1SunnyMildHighStrongNo2RainHotNormalStrongNo3RainCoolHighStrongNo4OvercastHotHighStrongYes5OvercastCoolNormalWeakYes6RainHotHighWeakYes7OvercastMildNormalWeakYes8OvercastCoolHighWeakYes9RainCoolHighWeakYes10RainMildNormalStrongNo11OvercastMildHighWeakYes12SunnyMildNormalWeakYes13SunnyCoolHighStrongNo14SunnyCoolHighWeakNoJeeves測試數據集合過擬合

決策樹——剪枝處理51(a)由Jeeves訓練集生成的決策樹(b)由有噪的Jeeves訓練集生成的決策樹決策樹的過擬合現象當訓練集遭到了破壞：第三個實例的標簽從“Yes”錯誤地更改為了“No”。受損的訓練集生成的決策樹將會不同。當用同一個測試集進行評估時，原始的決策樹在測試集上的誤差率為0，而新的決策樹在測試集上的錯誤率卻上升到了1/14。訓練集中一個微小的變化，可能導致生成的決策樹發(fā)生劇烈的變化。為了適應這個錯誤數據點，新的決策樹生長出了一個額外的子樹，使得樹的結構變得更加復雜。這樣的樹可能不會很好地泛化到新的數據上。過擬合

決策樹——剪枝處理52問題：過擬合模型通常捕捉到了訓練數據中的噪聲和特異性，這些屬性并不代表數據的整體分布或結構。這樣的模型在遇到新數據時往往表現不佳，因為它學習到的模式太過于特定于訓練集，缺乏泛化到未知數據的能力。解決思想：通過限制決策樹的深度和結點數量，我們可以避免模型變得過于復雜。這種簡化有助于模型專注于數據中最顯著和最普遍的屬性，從而提高了模型在新數據上的泛化能力。簡而言之，更小和更淺的決策樹往往能夠更好地捕捉到數據的真實結構，而不是僅僅記憶訓練數據。解決方法：通過剪枝技術，不僅能夠得到一個簡潔且易于解釋的模型，還能提升模型在未知數據上的預測能力。這種簡化不僅有助于防止過擬合，還能提高模型的運算效率，使其更加適用于現實世界的應用場景?？傊糁κ菦Q策樹優(yōu)化中的一項重要技術，它對于平衡模型的復雜度和泛化能力起著至關重要的作用。剪枝主要包括兩種方法：預剪枝和后剪枝。過擬合

決策樹——剪枝處理53預剪枝在決策樹生成的過程中，通過設定準則來提前終止樹的生長，以避免過度擬合訓練數據。預剪枝的優(yōu)點在于其高效性，因為它減少了不必要的樹生長。然而，這種方法可能會過于保守，導致剪掉一些可能對模型泛化有益的分支，從而造成欠擬合。后剪枝則是在決策樹完全生長之后進行的。它允許樹生長到最大深度，然后從下到上逐層考慮是否剪枝。后剪枝的決策通?；诩糁η昂蟮腻e誤率來決定。后剪枝的缺點是計算成本較高，因為它需要先生成一棵完整的樹，然后再進行剪枝。盡管如此，后剪枝通常能夠得到一個更精確的模型，因為它考慮了所有可能的分支。這里只是介紹了預剪枝技術。預剪枝的基本思想：用訓練集進行屬性選擇，找到當前信息增益或者增益率最大的屬性進行數據劃分，利用測試集來評估所做劃分的有效性。如果劃分后的測試精度有所下降，這表明該結點的劃分并沒有提高模型的泛化能力，反而可能導致了過擬合。在這種情況下，認為該結點的劃分是無效的，并采取減枝操作，即撤銷這一劃分。剪枝處理

例4（利用C4.5算法建立決策樹）

有噪的Jeeves訓練數據集合所示，它將原Jeeves訓練數據集的第9個數據的humidity屬性值由Normal改為High，記作：有噪的Jeeves訓練數據集。以信息增益率為準則進行屬性選擇，利用Jeeves測試集，采用預剪枝技術，構建決策樹。

決策樹——剪枝處理54剪枝處理

例4（利用C4.5算法建立決策樹）

決策樹——剪枝處理55DayOutlookTempHumidityWindTennis?1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolHighWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo有噪的Jeeves訓練數據集合剪枝處理解：步驟1以根結點作為當前結點進行預減枝處理首先對根結點進行測試,D共有14個實例，根結點包含9個正例和5個反例。屬性集合：{Outlook、Temp、Humidity、Wind}。正例多于反例，根據多數原則，根結點的標簽為“Yes”以Jeeves測試數據集合對根結點進行測試，測試結果為{1,2,3,4,5,6,7,8,9,10,11,12,13,14}，紅色表示錯分的實例。

決策樹——剪枝處理56剪枝處理步驟1以根結點作為當前結點進行預減枝處理

接下來考慮不同屬性下的劃分結果

決策樹——剪枝處理

下面只給出Outlook屬性下的信息增益率的計算過程，其他屬性下的具體的計算過程省略。注：用訓練集進行屬性選擇，找到當前增益率最大的屬性進行集合劃分，用測試集進行測試根據前后測試精度的改變，決定該結點的劃分是否保留，如果精度下降，該結點劃分無效，需要減枝。剪枝處理步驟1以根結點作為當前結點進行預減枝處理

決策樹——剪枝處理58

對于根結點數據分布剪枝處理步驟1以根結點作為當前結點進行預減枝處理

決策樹——剪枝處理計算屬性Outlook的信息增益和信息增益率。剪枝處理

決策樹——剪枝處理根結點的預剪枝Outlook增益率最大，因此選擇Outlook為分割屬性對于Outlook=Sunny，Outlook=Overcast和Outlook=Rain，根據多數原則，對應的三個訓練子集所的標簽分別為“No”，和“Yes”和“Yes”用測試集驗證，精度由原來的8/14提高到10/14，因此按照Outlook劃分測試集正確分類的記錄個數：8剪枝處理步驟2分別以Outlook=Sunny，Outlook=Overcast和Outlook=Rain三個分支結點作為當前結點，進行預減