第7章決策樹和決策規(guī)則

1、決策樹和決策規(guī)則決策樹和決策規(guī)則第第7章章本章目標本章目標n分析解決分類問題的基于邏輯的方法的特性分析解決分類問題的基于邏輯的方法的特性n信息論基礎信息論基礎nID3算法算法n了解何時以及怎樣用修剪方法降低決策樹和復雜度了解何時以及怎樣用修剪方法降低決策樹和復雜度n總結用決策樹和決策規(guī)則表示一個分類模型的局限性總結用決策樹和決策規(guī)則表示一個分類模型的局限性n什么是分類？n數(shù)據(jù)分類（data classfication）是數(shù)據(jù)挖掘的主要內(nèi)容之一，主要是通過分析訓練數(shù)據(jù)樣本，產(chǎn)生關于類別的精確描述。這種類別通常由分類規(guī)則組成，可以用來對未來的數(shù)據(jù)進行分類和預測。n數(shù)據(jù)分類的兩個步驟：n第1步：建立

2、一個模型，描述給定的數(shù)據(jù)類集或概念集（簡稱訓練集）n第2步：使用模型對數(shù)據(jù)進行分類。包括評估模型的分類準確性以及對類標號未知的元組按模型進行分類訓練數(shù)據(jù)分類算法分類規(guī)則學習測試數(shù)據(jù)待分類數(shù)據(jù)分類規(guī)則模型評估新數(shù)據(jù)分類7.1 信息論基礎n信息論是C.E.Shannon四十年代末期，以客觀概率信息為研究對象，從通信的信息傳輸問題中總結和開拓出來的理論。主要研究的問題 ：n信源的描述，信息的定量度量、分析與計算 n信道的描述，信道傳輸?shù)亩慷攘?、分析與計算。 n信源、信道與通信系統(tǒng)之間的統(tǒng)計匹配，以及通信系統(tǒng)的優(yōu)化 Shannon的三個編碼定理。 n信息論誕生五十年來，至今，仍然是指導通信技術發(fā)展的

3、理論基礎，是創(chuàng)新通信體制的源泉 。香農(nóng)信息(概率信息)n信息是事物運動狀態(tài)或存在方式的不確定性的描述。n在通信系統(tǒng)中形式上傳輸?shù)氖窍ⅲ珜嵸|(zhì)上傳輸?shù)氖切畔⑿旁葱潘扌诺老⒏蓴_或噪聲（發(fā)信者）（收信者）通信系統(tǒng)框圖n樣本空間：某事物各種可能出現(xiàn)的不同狀態(tài)，即所有可能選擇的消息的集合。n對于離散消息的集合，概率測度是對每一個可能選擇的消息指定一個概率。一個樣本空間和它的概率測度稱為一個概率空間。表示：X，Pn在離散情況下： 其中，P(ui)為選擇符號 ui作為消息的概率，稱為先驗概率先驗概率)(,),(),(,)(2121qquPuPuPuuuuPU信源數(shù)學模型n后驗概率后驗概率：條件概率 接收

4、端收到消息（符號） 后而發(fā)送端發(fā)的是 的概率。n自信息：消息 發(fā)生后所含有的信息量，反映了消息 發(fā)生前的不確定性：)|(jivuPjviuiuiu)(log)(1log)(iiiuPuPuIn信源熵n定義：信源各個離散消息的自信息量的數(shù)學期望（即概率加權的統(tǒng)計平均值）為信源的平均信息量，一般稱為信源的信息熵，也叫信源熵或香農(nóng)熵，有時也稱為無條件熵或熵函數(shù)，簡稱熵。n公式：n熵函數(shù)的自變量是X,表示信源整體，實質(zhì)上是無記憶信源平均不確定性的度量。n單位：以2為底，比特/符號)(log)()(1log)()(212iniiiixpxpxpExIEXH互信息n后驗熵：當接收到輸出符號V=vj后，信源

5、的平均不確定性，即輸入符號U的信息度量n條件熵：對后驗熵在輸出符號集V中求期望稱為信道疑義度。表示在輸出端收到全部輸出符號V后，對于輸入端的符號集U尚存有不確定性（有疑義），這是由于存在干擾（噪聲）引起的。H(U|V)H(U)，表明接收到符號集V的所有符號后，關于輸入符號U的平均不確定性減少了。)|(log)|()|(1log)|()|(212jinijijijijvupvupvupEvuIEvUH)|(log)|()()|()|(211jinijinjjjvupvupvpvUHEVUHn互信息互信息：先驗的不確定性減去收到輸出符號集V后尚存在的不確定性，表示收信者獲得的信息量,也稱信息增益)

6、|()(),(VUHUHVUI7.2 ID3算法n決策樹（Decision Tree）方法：n決策樹方法的起源是概念學習系統(tǒng)CLS，然后發(fā)展到由Quiulan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一個優(yōu)點是它能夠處理連續(xù)屬性。n決策樹又稱為判定樹，是運用于分類的一種樹結構。其中的每個內(nèi)部結點代表對某個屬性的一次測試，每條邊代表一個測試結果，葉結點代表某個類或者類的分布，最上面的結點是根結點。7.2 ID3算法（續(xù)）nID3算法思想：n任意選取一個屬性作為決策樹的根結點，然后就這個屬性所有的取值創(chuàng)建樹的分支；n用這棵樹來對訓練數(shù)據(jù)集進行分類，如果一個葉結點的所有實例都屬于同一類

7、，則以該類為標記標識此葉結點；如果所有的葉結點都有類標記，則算法終止；n否則，選取一個從該結點到根路徑中沒有出現(xiàn)過的屬性為標記標識該結點，然后就這個屬性所有的取值繼續(xù)創(chuàng)建樹的分支；重復算法步驟step 21.顯然，不同的屬性選取順序?qū)⑸刹煌臎Q策樹。因此，適當?shù)剡x取屬性將生成一棵簡單的決策樹。在ID3算法中，采用了一種基于信息的啟發(fā)式的方法來決定如何選取屬性。啟發(fā)式方法選取具有最高信息增益的屬性，也就是說，生成最少分支決策樹的那個屬性。7.2 ID3算法（續(xù)）屬性1屬性2A7079類18089屬性3類2假9099類2屬性26069屬性3類1真7079屬性3類1假9099屬性3類1真B屬性27

8、079屬性38089屬性39099屬性3類2真類1假類2真類1假7.2 ID3算法（續(xù)）屬性2屬性1A8089屬性3類1真屬性16069屬性3類1真7079屬性3類1屬性1類2B屬性1屬性3屬性3屬性3類2類1A類2真類2假BCC假9099A真B類1真屬性3C類1假7.2 ID3算法（續(xù)）n表7-1的ID3算法實例計算：1)計算信息熵H(C)類別Ci出現(xiàn)概率P(Ci)=|Ci|/|X|,|Ci|為類別Ci的樣本數(shù),|X|為總的樣本數(shù)|C1|=9,|C2|=5,|X|=14，代入上式算得H(C)=0.940bit2)計算屬性1的條件熵H(C|V)屬性1取值vj時，類別Ci的條件概率：P(Ci|v

9、j)=|Ci|/|vj|屬性1取值v1=A, v2=B, v3=CP(v1)=5/14, P(v2)=4/14, P(v3)=5/14取值為A的5個例子中有2個類1，3個類2，所以: P(C1|v1)=2/5 P(C2|v1)=3/5 )(log)()(21iniiCpCpCH)|(log)|()()|(211jinijinjjvCpvCpvpVCH7.2 ID3算法（續(xù)）n表7-1的ID3算法實例計算：同理有： P(C1|v2)=4/4 P(C2|v2)=0/4 P(C1|v3)=3/5 P(C2|v1)=2/5 代入上式得： H(C|V)=0.694bit3)計算信息增益Gain(屬性1)

10、=H(C)- H(C|V)=0.246bit同理可求得Gain(屬性3)=0.048bitn根據(jù)增益準則，ID3算法將選擇屬性1做為根節(jié)點，因為該屬性的信息增益最大。為了求得最優(yōu)解，還應該分析屬性2的信息增益，但因它是連續(xù)型數(shù)值，不能直接求，而要先進行離散化轉換成分類型的數(shù)據(jù)。7.3 修剪決策樹n決策樹修剪的主要任務是拋棄一個或更多的子樹，并用葉子替換這些子樹，使決策樹簡單化。在替換這些子樹時，我們期望算法降低預測誤差率來提高分類模型的質(zhì)量n剪枝操作有兩種策略:n預剪枝：在樹生成過程中判斷是否還繼續(xù)擴展決策樹。若停止擴展，相當于剪去該結點以下的分枝n后剪枝：對于生成好的樹剪去某些結點和分枝nC

11、4.5算法遵循基于誤差的后剪枝，也叫悲觀修剪，即如果使用葉子或樹枝代替原來的子樹后，誤差率能夠下降，則就使用此葉子或樹枝代替原來的子樹。7.3 修剪決策樹（續(xù)）n準備知識：二項式分布n在醫(yī)學領域中，有一些隨機事件是只具有兩種互斥結果的離散型隨機事件，稱為二項分類變量（dichotomous variable），如對病人治療結果的有效與無效，某種化驗結果的陽性與陰性，接觸某傳染源的感染與未感染等。二項分布（binomial distribution）就是對這類只具有兩種互斥結果的離散型隨機事件的規(guī)律性進行描述的一種概率分布。n考慮只有兩種可能結果的隨機試驗，當成功的概率（）是恒定的，且各次試驗相

12、互獨立，這種試驗在統(tǒng)計學上稱為貝努里試驗（Bernoulli trial）。如果進行n次貝努里試驗，取得成功次數(shù)為X（X=0,1,n）的概率可用下面的二項分布概率公式來描述：其中 表示在n次實驗中出現(xiàn)X的各種組合情況XnXXnXP)1 ()()()(Xn7.3 修剪決策樹（續(xù)）n決策樹的子樹如圖所示，這里根節(jié)點是關于屬性A的3個可能值1，2，3的檢驗。根節(jié)點的子節(jié)點是用相應的類和參數(shù)(|Ti|,E)表示的葉。問題是估計修剪子樹并用它的替換根結點作為一個新的歸納根節(jié)點的概率類1(16,1)7.3 修剪決策樹（續(xù)）n如一個葉結點覆蓋N個實例，其中E個為錯誤的，對于具有信任度CF的實例，計算一個2項

13、式分布UCF(E,N)，即是實例誤判的概率，那么N個實例誤判的數(shù)目為N* UCF(E,N)。子樹的錯誤數(shù)目為所有葉結點的總和。n設CF為25%，從統(tǒng)計表中可查出E的上限置信極限：U25%(0,6)=0.206,U25%(0,9)=0.143,U25%(0,1)=0.750, U25%(1,16)=0.157則子樹的實例誤判數(shù)目為：6* U25%(0,6)+9* U25%(0,9)+1* U25%(0,1)=3.257若以一個葉子“類1(16,1)”代替子樹，則誤判數(shù)目為：16* U25%(1,16)=16*0.157=2.5126FTI64TSH=tT4U=tTHY=t then calss A。該規(guī)則覆蓋3個實例，其中2個判斷正確，1個誤判。則誤判概率為UCF(1, 3)=69%。設刪除其中各個條