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

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

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

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

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

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

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

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

8、079屬性38089屬性39099屬性3類(lèi)2真類(lèi)1假類(lèi)2真類(lèi)1假7.2 ID3算法（續(xù)）屬性2屬性1A8089屬性3類(lèi)1真屬性16069屬性3類(lèi)1真7079屬性3類(lèi)1屬性1類(lèi)2B屬性1屬性3屬性3屬性3類(lèi)2類(lèi)1A類(lèi)2真類(lèi)2假BCC假9099A真B類(lèi)1真屬性3C類(lèi)1假7.2 ID3算法（續(xù)）n表7-1的ID3算法實(shí)例計(jì)算：1)計(jì)算信息熵H(C)類(lèi)別Ci出現(xiàn)概率P(Ci)=|Ci|/|X|,|Ci|為類(lèi)別Ci的樣本數(shù),|X|為總的樣本數(shù)|C1|=9,|C2|=5,|X|=14，代入上式算得H(C)=0.940bit2)計(jì)算屬性1的條件熵H(C|V)屬性1取值vj時(shí)，類(lèi)別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個(gè)例子中有2個(gè)類(lèi)1，3個(gè)類(lèi)2，所以: P(C1|v1)=2/5 P(C2|v1)=3/5 )(log)()(21iniiCpCpCH)|(log)|()()|(211jinijinjjvCpvCpvpVCH7.2 ID3算法（續(xù)）n表7-1的ID3算法實(shí)例計(jì)算：同理有： 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)計(jì)算信息增益Gain(屬性1)

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

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

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

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