決策樹和決策規(guī)則概述課件

1、第七章 決策樹和決策規(guī)則本章目標(biāo)分析解決分類問題的基于邏輯的方法的特性.描述決策樹和決策規(guī)則在最終分類模型中的表述之間的區(qū)別.介紹C4.5算法.了解采用修剪方法降低決策樹和決策規(guī)則的復(fù)雜度.決策樹和決策規(guī)則是解決實(shí)際應(yīng)用中分類問題的數(shù)據(jù)挖掘方法。一般來說，分類是把數(shù)據(jù)項(xiàng)映射到其中一個(gè)事先定義的類中的這樣一個(gè)學(xué)習(xí)函數(shù)的過程。由一組輸入的屬性值向量(也叫屬性向量)和相應(yīng)的類，用基于歸納學(xué)習(xí)算法得出分類。學(xué)習(xí)的目標(biāo)是構(gòu)建一個(gè)分類模型，通常也叫分類器。它可以根據(jù)有效的屬性輸入值預(yù)測一些實(shí)體(所給樣本)的類。是一個(gè)在樣本其他屬性已知的情況下預(yù)測另外一個(gè)屬性(樣本的類)的模型(分類的結(jié)果)。7.1 決策樹

2、從數(shù)據(jù)中生成分類器的一個(gè)特別有效的方法是生成一個(gè)決策樹。它是一種基于邏輯的方法，通過一組輸入-輸出樣本構(gòu)建決策樹的有指導(dǎo)學(xué)習(xí)方法。決策樹包含屬性已被檢驗(yàn)的節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)的輸出分枝和該節(jié)點(diǎn)的所有可能的檢驗(yàn)結(jié)果相對應(yīng)。圖7-2是一個(gè)簡單的決策樹。該問題有兩個(gè)屬性X,Y。所有屬性值X1和YB的樣本屬于類2。不論屬性Y的值是多少，值X 1的樣本都屬于類1。對于樹中的非葉節(jié)點(diǎn)，可以沿著分枝繼續(xù)分區(qū)樣本，每一個(gè)節(jié)點(diǎn)得到它相應(yīng)的樣本子集。生成決策樹的一個(gè)著名的算法是Quinlan的ID3算法，C4.5是它改進(jìn)版。ID3算法的基本思路：從樹的根節(jié)點(diǎn)處的所有訓(xùn)練樣本開始，選取一個(gè)屬性來劃分這些樣本。對屬性的每一

3、個(gè)值產(chǎn)生一分枝。分枝屬性值的相應(yīng)樣本子集被移到新生成的子節(jié)點(diǎn)上。這個(gè)算法遞歸地應(yīng)用于每個(gè)子節(jié)點(diǎn)，直到一個(gè)節(jié)點(diǎn)上的所有樣本都分區(qū)到某個(gè)類中。到達(dá)決策樹的葉節(jié)點(diǎn)的每條路徑表示一個(gè)分類規(guī)則。該算法的關(guān)鍵性決策是對節(jié)點(diǎn)屬性值的選擇。ID3和C4.5算法的屬性選擇的基礎(chǔ)是基于使節(jié)點(diǎn)所含的信息熵最小化?；谛畔⒄摰姆椒▓?jiān)持對數(shù)據(jù)庫中一個(gè)樣本進(jìn)行分類時(shí)所做檢驗(yàn)的數(shù)量最小。ID3的屬性選擇是根據(jù)一個(gè)假設(shè)，即：決策樹的復(fù)雜度和所給屬性值表達(dá)的信息量是密切相關(guān)的?；谛畔⒌脑囂椒ㄟx擇的是可以給出最高信息的屬性，即這個(gè)屬性是使樣本分類的結(jié)果子樹所需的信息最小。7.2 C4.5算法：生成一個(gè)決策樹C4.5算法最重要的

4、部分是由一組訓(xùn)練樣本生成一個(gè)初始決策樹的過程。決策樹可以用來對一個(gè)新樣本進(jìn)行分類，這種分類從該樹的根節(jié)點(diǎn)開始，然后移動(dòng)樣本直至達(dá)葉節(jié)點(diǎn)。在每個(gè)非葉決策點(diǎn)處，確定該節(jié)點(diǎn)的屬性檢驗(yàn)結(jié)果，把注意力轉(zhuǎn)移到所選擇子樹的根節(jié)點(diǎn)上。例如，如圖7-3a為決策樹分類模型，待分類有樣本如圖7-3b所示，由決策樹分類模型可得出待分類樣本為類2。(節(jié)點(diǎn)A,C,F(葉節(jié)點(diǎn))C4.5算法的構(gòu)架是基于亨特的CLS方法，其通過一組訓(xùn)練樣本T構(gòu)造一個(gè)決策樹。用C1,C2,CK來表示這些類，集合T所含的內(nèi)容信息有3種可能性：T包含一個(gè)或更多的樣本，全部屬于單個(gè)的類Cj。那么T的決策樹是由類Cj標(biāo)識(shí)的一個(gè)葉節(jié)點(diǎn)。T不包含樣本。決策

5、樹也是一個(gè)葉，但和該葉關(guān)聯(lián)的類由不同于T的信息決定，如T中的絕大多數(shù)類。3. T包含屬于不同類的樣本。這種情況下，是把T精化成朝向一個(gè)單類樣本集的樣本子集。根據(jù)某一屬性，選擇具有一個(gè)或更多互斥的輸出O1,O2,On的合適檢驗(yàn)。T被分區(qū)成子集T1,T2,Tn。T的決策樹包含標(biāo)識(shí)檢驗(yàn)的一個(gè)決策點(diǎn)和每個(gè)可能輸出的一個(gè)分枝(如圖7-3a中的A,B和C節(jié)點(diǎn))假設(shè)選擇有n個(gè)輸出(所給屬性的n個(gè)值)的檢驗(yàn)，把訓(xùn)練樣本集T分區(qū)成子集T1,T2,Tn。僅有的指導(dǎo)信息是在T和它的子集Ti中的類分布。如果S是任意樣本集，設(shè)freq(Ci,S)代表S中屬于Ci的樣本數(shù)量，|S|表示集合S中的樣本數(shù)量。ID3算法的屬性

6、選擇的檢驗(yàn)方法采用增益標(biāo)準(zhǔn)，它基于信息論中熵的概念。集合S的期望信息(熵)如下：T被分區(qū)之后的一個(gè)相似度標(biāo)準(zhǔn)，T按照一個(gè)屬性檢驗(yàn)X的幾個(gè)輸出進(jìn)行分區(qū)。所需信息為子集的熵的加權(quán)和:分區(qū)所對應(yīng)的信息增益:上式度量了按照檢驗(yàn)X進(jìn)行分區(qū)的T所得到的信息。該增益標(biāo)準(zhǔn)選擇了使Gain(X)最大化的檢驗(yàn)X，即此標(biāo)準(zhǔn)選擇的具有最高增益的那個(gè)屬性。例如：給定訓(xùn)練樣本如表7-1，14個(gè)樣本，3個(gè)屬性，分為兩個(gè)類。9個(gè)樣本屬于類1，5個(gè)屬于類2，因此分區(qū)前的熵為（基于類的熵計(jì)算） info(T)=-9/14log2(9/14)-5/14log2(5/14) =0.940按屬性1分區(qū)可得子集的熵的加權(quán)和： infox

7、1(T)=5/14(-2/5log2(2/5)-3/5log2(3/5) +4/14(-4/4log2(4/4)-0/4log2(0/4) +5/14(-3/5log2(3/5)-2/5log2(2/5) =0.694 相應(yīng)的增益: Gain(x1)=0.94-0.694=0.246按屬性3分區(qū)可得子集的熵的加權(quán)和： infox2(T)=6/14(-3/6log2(3/6)-3/6log2(3/6) +8/14(-6/8log2(6/8)-2/8log2(2/8) =0.892 相應(yīng)的增益: Gain(x2)=0.94-0.892=0.048由于屬性2是數(shù)值型的連續(xù)數(shù)據(jù)，不能簡單按上面方式計(jì)算

8、。下面先介紹一下C4.5算法中一般包含3種類型的檢驗(yàn)結(jié)構(gòu)：1.離散值的“標(biāo)準(zhǔn)”檢驗(yàn)，對屬性的每個(gè)可能值有一個(gè)分枝和輸出。2.如果屬性Y有連續(xù)的數(shù)值，通過將該值和閾值Z比較，用輸出YZ和YZ定義二元檢驗(yàn)。3.基于離散值的更復(fù)雜的檢驗(yàn)，該檢驗(yàn)中屬性的每個(gè)可能值被分配到許多易變的組中，每組都有一個(gè)輸出和分枝。數(shù)值型屬性檢驗(yàn)： 對于屬性Y，按訓(xùn)練樣本進(jìn)行分類，分類順序用v1,v2,vm表示，因此對Y僅有m-1個(gè)分區(qū)，要系統(tǒng)在檢查所有分區(qū)以求得最優(yōu)分區(qū)。通常選擇區(qū)間的中點(diǎn)為閾值。而C4.5算法選擇vi,vi+1的最小值vi為閾值。這確保出現(xiàn)結(jié)果中閾值屬于數(shù)據(jù)庫的一個(gè)值。對于上例，屬性2的值的集合是: 6

9、5,70,75,78,80,85,90,95,96 可能的閾值Z的集合是: 65,70,75,78,80,85,90,95。 從這8個(gè)值里選擇最優(yōu)的閾值(最高信息增益)，最優(yōu)的Z=80。(如果計(jì)算?)對應(yīng)屬性2的檢驗(yàn)3(屬性280和屬性280)的信息增益計(jì)算： infox3(T)=9/14(-7/9log2(7/9)-2/9log2(2/9) +5/14(-2/5log2(2/5)-3/5log2(3/5) =0.837 相應(yīng)的增益: Gain(x3)=0.94-0.837=0.103屬性1的增益最高，選擇該屬性進(jìn)行首次分區(qū)。每個(gè)屬性值具有一個(gè)分枝，產(chǎn)生3個(gè)分枝，如圖7-4所示.對每個(gè)分枝重復(fù)

10、上述步驟選擇檢驗(yàn)和最優(yōu)化過程。對于子節(jié)點(diǎn)T2子集，4個(gè)樣本都是類1，該節(jié)點(diǎn)是葉節(jié)點(diǎn)。對于余下的節(jié)點(diǎn)，在T1中有5個(gè)樣本，最優(yōu)檢驗(yàn)有兩個(gè)選擇：屬性270和屬性270的檢驗(yàn)x4。 info(T1)=-2/5log2(2/5)-3/5log2(3/5) =0.940infox4(T1)=2/5(-2/2log2(2/2)-0/2log2(0/2) +3/5(-0/3log2(0/3)-3/3log2(3/3) =0Gain(x3)=0.94-0=0.94產(chǎn)生兩個(gè)分枝為最終葉節(jié)點(diǎn)，分枝中的數(shù)據(jù)子集屬于同一類。對根節(jié)點(diǎn)下的T3子集進(jìn)行同樣的計(jì)算，按屬性3=真和屬性3=假檢驗(yàn)，產(chǎn)生兩個(gè)葉節(jié)點(diǎn)。圖7-5表示

11、數(shù)據(jù)庫T的最終決策樹。另外，決策樹可以用可執(zhí)行代碼（或偽代碼）的形式表示。圖7-6用偽代碼給出了上面例子的決策樹。 增益標(biāo)準(zhǔn)對具有許多輸出的檢驗(yàn)有嚴(yán)重的偏差，根據(jù)info(S)的定義，指定一個(gè)附加的參數(shù)：這表示通過把集T分區(qū)成n個(gè)子集Ti而生成的潛在信息?，F(xiàn)在，定義一個(gè)新的增益標(biāo)準(zhǔn)： Gain-radio(X)=gain(X)/Split-info(X) 7.3 未知屬性值C4.5算法的前一版本是基于所有屬性值都已確定這一假設(shè)。但是在一個(gè)數(shù)據(jù)庫，經(jīng)常會(huì)缺少某些樣本的一些屬性。由于該屬性值與某個(gè)樣本是不相關(guān)的，或搜集樣本時(shí)沒有對它進(jìn)行記錄，或在數(shù)據(jù)錄入時(shí)有人為的誤差，就可能出現(xiàn)屬性值丟失的情況。

12、解決丟失值問題的兩種方法： 1.拋棄數(shù)據(jù)庫中有丟失數(shù)據(jù)的樣本。 2.定義一個(gè)新的算法或改進(jìn)現(xiàn)有算法來處理丟失的數(shù)據(jù)。第一種解決方案很簡單，但當(dāng)樣本集中存在大量丟失值時(shí)不能采用這種方法。在C4.5算法中,有未知值的樣本是按照已知值的相對頻率隨機(jī)分布的,這是普遍使用的法則。除了考慮到僅有的幾個(gè)有已知屬性值的樣本，Info(T)和Infox(T)的計(jì)算和前面機(jī)相同。然后可以用系數(shù)合理地修正增益參數(shù)，該系數(shù)表示所給屬性已知的概率。數(shù)據(jù)庫中一個(gè)給出的屬性值具有已知值的樣本的數(shù)量/數(shù)據(jù)集中樣本數(shù)量總和。新的增益標(biāo)準(zhǔn)有以下形式：Gain(x)=F(Info(T)-Infox(T)同樣，通過把具有未知值的樣本

13、看作分區(qū)的一個(gè)附加組可以修改Split-info(x) 。如果檢驗(yàn)x有n個(gè)輸出， Split-info(x)按照檢驗(yàn)把數(shù)據(jù)集分區(qū)成n+1個(gè)子集計(jì)算。例如：一個(gè)改進(jìn)了的C4.5決策樹的方法。數(shù)據(jù)集見表7-2。該例有14個(gè)樣本，屬性1有一個(gè)丟失值，用“?”表示。只有13個(gè)樣本數(shù)據(jù)完整。分區(qū)前的熵是：Info(T)=-8/13log2(8/13)-5/13log2(5/13) =0.961屬性1檢驗(yàn)的信息： infox1(T)=5/13(-2/5log2(2/5)-3/5log2(3/5) +3/13(-3/3log2(3/3)-0/3log2(0/3) +5/13(-3/5log2(3/5)-2/

14、5log2(2/5) =0.747該檢驗(yàn)所獲得的信息系數(shù)F(F=13/14)修正：Gain(x1)=13/14(0.961-0.747)=0.199該值比上個(gè)例子的值0.216小。然后，該分區(qū)信息仍是根據(jù)整個(gè)訓(xùn)練集來確定的，而且更大，因?yàn)閷ξ粗涤幸粋€(gè)額外的類別。 Split-info(xi) =-(5/14log(5/14)+3/14log(3/14) +5/14log(5/14)+1/14log(1/14)=1.876另外，每個(gè)樣本都有一個(gè)相關(guān)的新參數(shù),即概率。顯然，當(dāng)一個(gè)值已知的樣本從T分配給Ti時(shí)，它屬于Ti的概率是1，屬于其他所有子集的概率是0。當(dāng)一值是未知時(shí)，只能得出不穩(wěn)定的概率描

15、述。因此C4.5和每個(gè)子集Ti中的每個(gè)樣本是用權(quán)重w聯(lián)系起來的，它表示屬于每個(gè)子集的樣本概率。為了使該解決方法更具一般性，必須認(rèn)為分區(qū)前樣本的概率并不總是等于1。因此，分區(qū)后丟失值的新參數(shù)wnew為： wnew=woldP(Ti)對于屬性1的檢驗(yàn)x1分區(qū)結(jié)果，丟失值的記錄將被表示在3個(gè)子集中。如圖7-7所示。因?yàn)樽畛醯?舊的)w值等于1，新的權(quán)值wi等于概率5/13,3/13,和5/13。在C4.5中，Ti的算式如下： |T1|=5+5/13, |T2|=3+3/13, |T3|=5+5/13對屬性2和屬性3檢驗(yàn)分區(qū)，最終決策樹如圖7-8中所示的形式。上圖與圖7-6結(jié)構(gòu)相同，但是因?yàn)樽罱K分類的

16、不明確性，每個(gè)決策都以形式(|Ti|/E)和兩個(gè)參數(shù)關(guān)聯(lián)。|Ti|是到葉節(jié)點(diǎn)的部分樣本和，E是屬于除了指定類以外的類的樣本的數(shù)量。2.4/0.4例如，(3.4/0.4)的意思是：3.4(3+5/13)個(gè)訓(xùn)練樣本到達(dá)葉節(jié)點(diǎn)，其中0.4(5/13)并不屬于分配給葉的類。可以用百分?jǐn)?shù)表示參數(shù)|Ti|和E：3/3.4100%=所給葉的88%的樣本將被分給類20.4/3.4100%=所給葉的12%的樣本將被分給類1人生只有必然，沒有偶然。7月-227月-22Sunday, July 24, 2022不知不覺中人就發(fā)霉了，所以千萬不要不知不覺。07:33:5507:33:5507:337/24/2022

17、7:33:55 AM以誠感人者，人亦誠而應(yīng)。7月-2207:33:5507:33Jul-2224-Jul-22不入虎穴,焉得虎子？沒有人富有得可以不要?jiǎng)e人的幫助，也沒有人窮得不能在某方面給他人幫助。07:33:5507:33:5507:33Sunday, July 24, 2022沒本事的男人才會(huì)要死要活。7月-227月-2207:33:5507:33:55July 24, 2022省錢就是掙錢。2022年7月24日7:33 上午7月-227月-22人在世上練，刀在石上磨。24 七月 20227:33:55 上午07:33:557月-22屬于自己的，不要放棄；別人得到的，切莫妒忌。七月 227:33 上午7月-2207:33July 24, 2022青霄有路終須到，金榜無名誓不休。2022/7/24 7:33:5507:33:5524 July 2022質(zhì)