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

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

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

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

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

5、樹也是一個葉，但和該葉關(guān)聯(lián)的類由不同于T的信息決定，如T中的絕大多數(shù)類。3. T包含屬于不同類的樣本。這種情況下，是把T精化成朝向一個單類樣本集的樣本子集。根據(jù)某一屬性，選擇具有一個或更多互斥的輸出O1,O2,On的合適檢驗。T被分區(qū)成子集T1,T2,Tn。T的決策樹包含標識檢驗的一個決策點和每個可能輸出的一個分枝(如圖7-3a中的A,B和C節(jié)點)假設(shè)選擇有n個輸出(所給屬性的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、選擇的檢驗方法采用增益標準，它基于信息論中熵的概念。集合S的期望信息(熵)如下：T被分區(qū)之后的一個相似度標準，T按照一個屬性檢驗X的幾個輸出進行分區(qū)。所需信息為子集的熵的加權(quán)和:分區(qū)所對應(yīng)的信息增益:上式度量了按照檢驗X進行分區(qū)的T所得到的信息。該增益標準選擇了使Gain(X)最大化的檢驗X，即此標準選擇的具有最高增益的那個屬性。例如：給定訓(xùn)練樣本如表7-1，14個樣本，3個屬性，分為兩個類。9個樣本屬于類1，5個屬于類2，因此分區(qū)前的熵為（基于類的熵計算） 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ù)，不能簡單按上面方式計算

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

9、5,70,75,78,80,85,90,95,96 可能的閾值Z的集合是: 65,70,75,78,80,85,90,95。 從這8個值里選擇最優(yōu)的閾值(最高信息增益)，最優(yōu)的Z=80。(如果計算?)對應(yīng)屬性2的檢驗3(屬性280和屬性280)的信息增益計算： 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的增益最高，選擇該屬性進行首次分區(qū)。每個屬性值具有一個分枝，產(chǎn)生3個分枝，如圖7-4所示.對每個分枝重復(fù)

10、上述步驟選擇檢驗和最優(yōu)化過程。對于子節(jié)點T2子集，4個樣本都是類1，該節(jié)點是葉節(jié)點。對于余下的節(jié)點，在T1中有5個樣本，最優(yōu)檢驗有兩個選擇：屬性270和屬性270的檢驗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)生兩個分枝為最終葉節(jié)點，分枝中的數(shù)據(jù)子集屬于同一類。對根節(jié)點下的T3子集進行同樣的計算，按屬性3=真和屬性3=假檢驗，產(chǎn)生兩個葉節(jié)點。圖7-5表示

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

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

13、看作分區(qū)的一個附加組可以修改Split-info(x) 。如果檢驗x有n個輸出， Split-info(x)按照檢驗把數(shù)據(jù)集分區(qū)成n+1個子集計算。例如：一個改進了的C4.5決策樹的方法。數(shù)據(jù)集見表7-2。該例有14個樣本，屬性1有一個丟失值，用“?”表示。只有13個樣本數(shù)據(jù)完整。分區(qū)前的熵是：Info(T)=-8/13log2(8/13)-5/13log2(5/13) =0.961屬性1檢驗的信息： 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該檢驗所獲得的信息系數(shù)F(F=13/14)修正：Gain(x1)=13/14(0.961-0.747)=0.199該值比上個例子的值0.216小。然后，該分區(qū)信息仍是根據(jù)整個訓(xùn)練集來確定的，而且更大，因為對未知值有一個額外的類別。 Split-info(xi) =-(5/14log(5/14)+3/14log(3/14) +5/14log(5/14)+1/14log(1/14)=1.876另外，每個樣本都有一個相關(guān)的新參數(shù),即概率。顯然，當一個值已知的樣本從T分配給Ti時，它屬于Ti的概率是1，屬于其他所有子集的概率是0。當一值是未知時，只能得出不穩(wěn)定的概率描

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

16、不明確性，每個決策都以形式(|Ti|/E)和兩個參數(shù)關(guān)聯(lián)。|Ti|是到葉節(jié)點的部分樣本和，E是屬于除了指定類以外的類的樣本的數(shù)量。2.4/0.4例如，(3.4/0.4)的意思是：3.4(3+5/13)個訓(xùn)練樣本到達葉節(jié)點，其中0.4(5/13)并不屬于分配給葉的類?？梢杂冒俜謹?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不入虎穴,焉得虎子？沒有人富有得可以不要別人的幫助，也沒有人窮得不能在某方面給他人幫助。07:33:5507:33:5507:33Sunday, July 24, 2022沒本事的男人才會要死要活。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ì)