模式識別與智能計算第七章

決策樹分類器設計

楊淑瑩第七章決策樹分類器設計7.1

決策樹的基本概念1.決策樹的基本原理2.決策樹分類3.決策樹方法的特點

7.2決策樹理論的分類方法1.理論基礎3.編程代碼

2.實現(xiàn)步驟4.效果圖

7.3總結(jié)

7.1決策樹的基本概念1.決策樹的基本原理決策樹（DecisionTree)：又稱為判定樹，是用于分類和預測的一種樹結(jié)構(gòu)。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部節(jié)點進行屬性值的比較并根據(jù)不同屬性判斷從該節(jié)點向下的分支，在決策樹的葉節(jié)點得到結(jié)論。例1

圖1所示為買車問題的決策樹，從中可以看出一位客戶是否會買汽車，用它可以預測某個人的購買意向。決策樹的基本概念年齡月薪買健康狀況不買買不買買<3030~60>60<3000≥3000不好好圖1

買車問題的決策樹決策樹的基本概念自然樹對應決策樹中的意義分類問題中的表示意義樹根根節(jié)點訓練實例整個數(shù)據(jù)集空間杈內(nèi)部節(jié)點、決策節(jié)點待分類對象的屬性樹枝分支屬性的一個可能取值葉子葉子結(jié)點、狀態(tài)節(jié)點數(shù)據(jù)分割（分類結(jié)果）表1決策樹與自然樹的對應關(guān)系及代表含義

構(gòu)造決策樹通常采用自上而下的遞歸構(gòu)造方法。如果訓練集中所有數(shù)據(jù)都是同類的，則將之作為葉節(jié)點，節(jié)點內(nèi)容即該類標記，否則根據(jù)某種策略選擇一個屬性，按照屬性的各個取值，把數(shù)據(jù)集合劃分若干個子集，使得每個子集上的所有數(shù)據(jù)在該屬性上具有同樣的屬性值。2.決策樹分類

決策樹分類算法起源于概念學習系統(tǒng)，然后發(fā)展到ID3方法，最后又演化為能處理連續(xù)屬性的C4.5。此外，還有CART、SLIQ、SPRINT等方法。使用決策樹進行分類可分為兩步：步驟1：建立決策樹模型：利用訓練集建立并精化一棵決策樹。（建樹、剪枝）步驟2：利用生成的決策樹對數(shù)據(jù)進行分類。決策樹的基本概念3.決策樹方法的特點與其他分類方法相比，決策樹分類有如下優(yōu)點：分類速度快，計算量相對較小，容易轉(zhuǎn)化成分類規(guī)則。分類準確性高，從決策樹中挖掘出的規(guī)則準確性高且便于理解。決策樹的基本概念7.2決策樹理論的分類方法1.理論基礎Quinlan提出的ID3算法是決策樹算法的代表，具有描述簡單、分類速度快的優(yōu)點，大多數(shù)決策樹算法都是在它的基礎上加以改進而實現(xiàn)的。（1）ID3算法基本思想決策樹理論的分類方法年齡月薪買健康狀況不買買不買買<3030~60>60<3000≥3000不好好圖1

買車問題的決策樹（2）屬性選擇度量期望信息量：設訓練集為

，樣品總數(shù)為N，其中包含M個不同的類ωi(i=1,2，…，M)的樣品的個數(shù)。設Ni是

中屬于類ωi的樣品個數(shù)。對一個給定樣品分類所需的期望信息為

其中，pi是樣品屬于ωi的概率。決策樹理論的分類方法熵：熵是一個衡量系統(tǒng)混亂程度的統(tǒng)計量，熵越大，表示系統(tǒng)越混亂。對于給定子集Sj，有決策樹理論的分類方法決策樹理論的分類方法信息增益：Gain（A）是指由于知道屬性A的值而導致的熵的期望壓縮。在屬性A上分支獲得的信息增益表示為例2

表2所示的是一個顧客買車意向的訓練集，通過此例來說明屬性選擇方法。決策樹理論的分類方法樣品編號年齡月薪健康狀況買車意向1<30<3000好不買2<30<3000不好不買3<30≥3000不好買4<30≥3000好買530~60<3000好買630~60≥3000好買730~60≥3000不好買8>60<3000好買9>60<3000不好不買10>60≥3000不好不買表2決策樹理論的分類方法從表2中可以看出，類屬性“買車意向”有兩個不同的值｛買，不買｝，因此一共有兩個類M＝2。設ω1對應于“買”，ω2對應于“不買”，則ω1有6個樣本，N1＝6，ω2有4個樣本，N2＝4。首先計算期望信息I（N1，N2）。然后計算每個屬性的熵。對于屬性“年齡”，有三種取值，即三個子集，分別計算三個子集的期望信息。決策樹理論的分類方法計算樣本按“年齡”劃分成子集的熵為信息增益為同理，我們可以得到其余兩個屬性的信息增益：決策樹理論的分類方法圖2對屬性“年齡”進行劃分對屬性“年齡”劃分后得到圖2所示樹，年齡30~60的樣本都是同一類，故可作為葉子結(jié)點，因此對年齡<30以及>60的需要繼續(xù)操作.決策樹理論的分類方法(3)決策樹剪枝剪枝

就是指將決策樹的某些內(nèi)部節(jié)點下面的節(jié)點都刪掉，留下來的內(nèi)部決策節(jié)點作為葉子節(jié)點。為什么需要剪枝？決策樹是充分考慮了所有的數(shù)據(jù)點而生成的復雜樹，它在學習的過程中為了盡可能的正確的分類訓練樣本，不停地對結(jié)點進行劃分，因此這會導致整棵樹的分支過多，造成決策樹很龐大。決策樹過于龐大，有可能出現(xiàn)過擬合的情況，決策樹越復雜，過擬合的程度會越高。所以，為了避免過擬合，咱們需要對決策樹進行剪枝。決策樹理論的分類方法(3)決策樹剪枝先剪枝：建樹過程中進行判斷，若滿足一定條件節(jié)點不再分裂。后剪枝：建樹完成，從葉子到根的方向修剪，若某個葉子剪去后測試集的準確率不降低，則剪去該葉子。決策樹理論的分類方法(4)從決策樹提取分類規(guī)則從根結(jié)點到葉結(jié)點的每一條路徑創(chuàng)建一條分類規(guī)則，路徑上的每一對“屬性-值”對應規(guī)則的前件的一個合取項，葉結(jié)點為規(guī)則的后件。表三所示為例2構(gòu)造決策樹后的分類規(guī)則。年齡月薪健康狀況買車意向<30<3000不買<30≥3000買30~60買>60不好不買>60好買表3決策樹理論的分類方法(5)ID3算法的改進ID3算法的缺點：最優(yōu)屬性選取不準確，信息增益的計算依賴于屬性取值數(shù)目較多的特征，而取值較多的屬性不一定是最優(yōu)屬性；抗噪性差，訓練集中正例和反例較難控制。因此，眾多學者針對ID3算法的不足，提出了許多改進策略。離散化空缺值處理屬性選擇度量可伸縮性碎片、重復和復制處理7.2決策樹理論的分類方法2.實現(xiàn)步驟構(gòu)建訓練樣本集構(gòu)建分類決策樹利用決策樹分類顯示決策樹決策樹理論的分類方法習題73.對于一個訓練集，如表4所示，利用ID3算法構(gòu)造一棵決策樹。表4決策樹理論的分類方法構(gòu)建訓練樣本集圖3通過創(chuàng)建CSV文件構(gòu)建樣本集決策樹理論的分類方法構(gòu)建分類決策樹圖4導入要使用的庫并讀取數(shù)據(jù)集決策樹理論的分類方法構(gòu)建分類決策樹圖5創(chuàng)建決策樹對數(shù)據(jù)集進行訓練決策樹理論的分類方法顯示決策樹圖6顯示決策樹決策樹理論的分類方法顯示決策樹運行以上代碼將在左側(cè)項目區(qū)下生成pdf文件。如圖7為文件內(nèi)顯示的決策樹。0：否

1：是2：體溫正常

3：體溫高4：體溫非常高圖7顯示決策樹決策樹理論的分類方法利用決策樹分類圖8驗證決策樹構(gòu)造的正確性，并預測一組數(shù)據(jù)進行分類決策樹理論的分類方法利用決策樹分類圖9驗證結(jié)果與預測結(jié)果7.3總結(jié)