C4.5決策樹的生成

1、 CHANGSHA UNIVERSITY OF SCIENCE & TECHNOLOGY 題目： C4.5決策樹的生成 學(xué)生姓名： 曹水根 學(xué) 號(hào)：專 業(yè)： 軟件工程 年 級(jí)： 2014級(jí) 指導(dǎo)老師： 李平 完成時(shí)間： 2015年7月10號(hào) 一、介紹決策樹（Decision tree），是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。它從一組無次序、無規(guī)則的元組中推理出決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比較，并根據(jù)不同的屬性值從該結(jié)點(diǎn)向下分支，葉結(jié)點(diǎn)是要學(xué)習(xí)劃分的類。從根到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條合取規(guī)則，整個(gè)決策樹就對(duì)應(yīng)著一

2、組析取表達(dá)式規(guī)則。1986年Quinlan提出了著名的ID3算法。在ID3算法的基礎(chǔ)上，1993年Quinlan又提出了C4.5算法。2、 核心思想采用從信息論知識(shí)中我們直到，期望信息越小，信息增益越大，從而純度越高。所以ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進(jìn)行分裂。下面先定義幾個(gè)要用到的概念。設(shè)D為用類別對(duì)訓(xùn)練元組進(jìn)行的劃分，則D的熵（entropy）表示為：其中pi表示第i個(gè)類別在整個(gè)訓(xùn)練元組中出現(xiàn)的概率，可以用屬于此類別元素的數(shù)量除以訓(xùn)練元組元素總數(shù)量作為估計(jì)。熵的實(shí)際意義表示是D中元組的類標(biāo)號(hào)所需要的平均信息量。現(xiàn)在我們假設(shè)將訓(xùn)練元組D按屬性A進(jìn)

3、行劃分，則A對(duì)D劃分的期望信息為：而信息增益即為兩者的差值： C4.5算法首先定義了“分裂信息”，其定義可以表示成：其中各符號(hào)意義與ID3算法相同，然后，增益率被定義為：算法：3、 ID3算法和C4.5的比較    (1) ID3算法ID3算法的核心是：在決策樹各級(jí)結(jié)點(diǎn)上選擇屬性時(shí)，用信息增益（information gain）作為屬性的選擇標(biāo)準(zhǔn)，以使得在每一個(gè)非葉結(jié)點(diǎn)進(jìn)行測(cè)試時(shí)，能獲得關(guān)于被測(cè)試記錄最大的類別信息。其具體方法是：檢測(cè)所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn)，由該屬性的不同取值建立分支，再對(duì)各分支的子集遞歸調(diào)用該方法建立

4、決策樹結(jié)點(diǎn)的分支，直到所有子集僅包含同一類別的數(shù)據(jù)為止。最后得到一棵決策樹，它可以用來對(duì)新的樣本進(jìn)行分類。  某屬性的信息增益按下列方法計(jì)算。通過計(jì)算每個(gè)屬性的信息增益，并比較它們的大小，就不難獲得具有最大信息增益的屬性。  設(shè)S是s個(gè)數(shù)據(jù)樣本的集合。假定類標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類Ci(i=1,m)。設(shè)si是類Ci中的樣本數(shù)。對(duì)一個(gè)給定的樣本分類所需的期望信息由下式給出：  其中pi=si/s是任意樣本屬于Ci的概率。注意，對(duì)數(shù)函數(shù)以2為底，其原因是信息用二進(jìn)制編碼。  設(shè)屬性A具有v個(gè)不同值a1,a

5、2,av?？梢杂脤傩訟將S劃分為v個(gè)子集S1,S2,Sv，其中Sj中的樣本在屬性A上具有相同的值aj（j=1,2,v）。設(shè)sij是子集Sj中類Ci的樣本數(shù)。由A劃分成子集的熵或信息期望由下式給出：  熵值越小，子集劃分的純度越高。對(duì)于給定的子集Sj，其信息期望為  其中pij=sij/sj 是Sj中樣本屬于Ci的概率。在屬性A上分枝將獲得的信息增益是    Gain(A)= I(s1, s2, ,sm)-E(A)  ID3算法的優(yōu)點(diǎn)是：算法的理論清晰，方法簡單，學(xué)習(xí)能力較強(qiáng)。其缺點(diǎn)是：只對(duì)比較小

6、的數(shù)據(jù)集有效，且對(duì)噪聲比較敏感，當(dāng)訓(xùn)練數(shù)據(jù)集加大時(shí)，決策樹可能會(huì)隨之改變。(2) C4.5算法    C4.5算法繼承了ID3算法的優(yōu)點(diǎn)，并在以下幾方面對(duì)ID3算法進(jìn)行了改進(jìn)：    1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足；    2) 在樹構(gòu)造過程中進(jìn)行剪枝；    3) 能夠完成對(duì)連續(xù)屬性的離散化處理；    4) 能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。

7、0;   C4.5算法與其它分類算法如統(tǒng)計(jì)方法、神經(jīng)網(wǎng)絡(luò)等比較起來有如下優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。其缺點(diǎn)是：在構(gòu)造樹的過程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時(shí)程序無法運(yùn)行。4、 實(shí)例C4.5數(shù)據(jù)集的一個(gè)示例如圖4.1：圖4.1 C4.5算法數(shù)據(jù)集(1)、根節(jié)點(diǎn)的計(jì)算數(shù)據(jù)集信息的統(tǒng)計(jì)如表4.1：屬性O(shè)utlookTemperatureHumidityWindy總記錄數(shù)記錄情況屬性值得個(gè)數(shù)3322149個(gè)Yes，5個(gè)No。表4.1 數(shù)據(jù)集信息數(shù)據(jù)集詳細(xì)統(tǒng)

8、計(jì)信息如表4.2：屬性屬性值記錄數(shù)記錄的情況OutlookSunny52個(gè)Yes，3個(gè)No；Overcast44個(gè)Yes；Rain53個(gè)Yes，2個(gè)No；TemperatureHot42個(gè)Yes，2個(gè)No；Mild64個(gè)Yes，2個(gè)No；Cool44個(gè)Yes，1個(gè)No；HumidityHigh73個(gè)Yes，4個(gè)No；Normal76個(gè)Yes，1個(gè)No；WindyWeak86個(gè)Yes，2個(gè)No；Strong63個(gè)Yes，3個(gè)No；表4.2 數(shù)據(jù)集詳細(xì)統(tǒng)計(jì)信息、根據(jù)計(jì)算熵的公式，計(jì)算熵：Entropy（S）=-9/14*log(9/14)-5/14*log(5/14)=0.940286的熵同理可得

9、：Entropy(Rain)=0.9709506 Rain的熵Entropy(Overcast)=0 Overcast的熵Entropy(Sunny)=0.9709506 Sunny的熵Entropy(Hot)=1 Hot的熵Entropy(Mild)= 0.9182958 Mild的熵Entropy(Sunny)=0.8112781 Sunny的熵Entropy(High)=0.9852281 High的熵Entropy(Normal)= 0.5916728 Normal的熵Entropy(Weak) =0.8112781的熵Entropy(Strong)=1 Strong的熵Entropy

10、(Outlook)= 1.577406 #Outlook的熵Entropy(Temperature)=1.556657 #Temperature的熵Entropy(Humidity)=1 #Humidity的熵Entropy(Windy)=0.9852281 #Windy的熵、計(jì)算信息增益Gain(Windy)=Entropy(S)-(8/14)*Entropy(Weak)-(6/14)*Entropy(Strong)=0.940286-(8/14)*0.8112781-(6/14)*1.0=0.048;同理可得：Gain(Outlook)=Entropy(S)-(5/14)*Entropy(

11、Sunny)-(4/14)* Entropy(Overcast)-(5/14)*Entropy(Rain)=0.2467498;Gain(Temperature)=0.02922257;Gain(Humidity)=0.1518355;、計(jì)算信息增益率GainRatio(Outlook)=Gain(Outlook)/Entropy(Outlook)=0.2467498/1.577406=0.1564679;GainRatio(Windy)=Gain(Windy)/Entropy(Windy)=0.048/0.9852281=0.04884862;GainRatio(Temperature)=G

12、ain(Temperature)/Entropy(Temperature)=0.02922257/1.556657= 0.04884862;GainRatio(Humidity)=Gain(Humidity)/Entropy(Humidity)=0.1518355;增益率中GainRatio(Outlook)最大，所以O(shè)utlook作為根節(jié)點(diǎn)。（2） 、以計(jì)算以O(shè)utlook為根節(jié)點(diǎn)，以Sunny為子樹的熵增益率的計(jì)算Sunny記錄的統(tǒng)計(jì)信息如表4.3，屬性總記錄數(shù)記錄情況屬性值得個(gè)數(shù)52個(gè)Yes，3個(gè)No。表4.3 Sunny記錄的統(tǒng)計(jì)信息Sunny詳細(xì)統(tǒng)計(jì)信息如表4.4：屬性屬性值記錄數(shù)記

13、錄的情況TemperatureHot22個(gè)Yes；Mild21個(gè)Yes，1個(gè)No；Cool11個(gè)Yes；HumidityHigh33個(gè)No；Normal22個(gè)Yes；WindyWeak31個(gè)Yes，2個(gè)No；Strong21個(gè)Yes，1個(gè)No；表4.4 Sunny詳細(xì)統(tǒng)計(jì)信息、根據(jù)計(jì)算熵的公式，計(jì)算熵：Entropy（Sunny）=0.9709506的熵Entropy(Hot)=0 Hot的熵Entropy(Mild)= 1 Mild的熵Entropy(Sunny)=0 Sunny的熵Entropy(High)=0 High的熵Entropy(Normal)= 0 Normal的熵Entrop

14、y(Weak) = 0.889975的熵Entropy(Strong)=1 Strong的熵Entropy(Temperature)=1.521928 #Temperature的熵Entropy(Humidity)=0.9709506 #Humidity的熵Entropy(Windy)=0.9709506 #Windy的熵、根據(jù)公式計(jì)算信息增益Gain(Windy)=0.03696559;Gain(Temperature)= 0.5709506;Gain(Humidity)= 0.9709506;、根據(jù)公式計(jì)算信息增益率GainRatio(Windy)=Gain(Windy)/Entropy(

15、Windy)=0.048/0.9852281=0.03807155;GainRatio(Temperature)=Gain(Temperature)/Entropy(Temperature)=0.02922257/1.556657= 0.3751495;GainRatio(Humidity)=Gain(Humidity)/Entropy(Humidity)=1;GainRatio(Humidity)的值最大，所以選擇Humidity作為Sunny的子節(jié)點(diǎn)，也是分裂節(jié)點(diǎn)。（3） 、計(jì)算以O(shè)utlook為根節(jié)點(diǎn)，以Rain為子樹的熵增益的計(jì)算Rain記錄的統(tǒng)計(jì)信息如表4.5，屬性總記錄數(shù)記錄情況屬

16、性值得個(gè)數(shù)53個(gè)Yes，2個(gè)No。表4.5 Rain記錄的統(tǒng)計(jì)信息Rain詳細(xì)統(tǒng)計(jì)信息如表4.6：屬性屬性值記錄數(shù)記錄的情況TemperatureMild32個(gè)Yes，1個(gè)No；Cool21個(gè)Yes，1個(gè)No；HumidityHigh21個(gè)Yes，1個(gè)No；Normal32個(gè)Yes，1個(gè)No；WindyWeak33個(gè)Yes；Strong22個(gè)No；表4.6 Rain詳細(xì)統(tǒng)計(jì)信息、根據(jù)計(jì)算熵的公式，計(jì)算熵：Entropy（Rain）=0.9709506的熵Entropy(Mild)= 0.9182958 Mild的熵Entropy(Sunny)=1 Sunny的熵Entropy(High)=1

17、High的熵Entropy(Normal)= 0.9293715 Normal的熵Entropy(Weak) = 0的熵Entropy(Strong)=0 Strong的熵Entropy(Temperature)=1.521928 #Temperature的熵Entropy(Humidity)= 0.9931569 #Humidity的熵Entropy(Windy)=0.9709506 #Windy的熵、根據(jù)公式計(jì)算信息增益Gain(Windy)=0.4709506;Gain(Temperature)= 0.4036323;Gain(Humidity)= -0.0007980202;、根據(jù)公式

18、計(jì)算信息增益率GainRatio(Windy)=Gain(Windy)/Entropy(Windy)=0.048/0.9852281=0.4850407;GainRatio(Temperature)=Gain(Temperature)/Entropy(Temperature)=0.02922257/1.556657= 0.4064134;GainRatio(Humidity)=Gain(Humidity)/Entropy(Humidity)=-0.0008218958;GainRatio(Windy)的值最大，所以選擇Windy作為Sunny的子節(jié)點(diǎn)，也是分裂節(jié)點(diǎn)。因此：可以構(gòu)建決策樹如圖4.

19、2，5、 代碼R語言實(shí)現(xiàn)，計(jì)算熵，熵增益，熵增益率。1、 計(jì)算根節(jié)點(diǎn)的代碼：#總共14條記錄，9個(gè)yes,5個(gè)NoS1 <-9/14 #總的記錄的劃分S2 <-5/14#Outlook中Sunny總共5條記錄，其中2個(gè)Yes，3個(gè)No；Overcast總共4條記錄，4個(gè)Yes；Rain總共%5條記錄，3個(gè)Yes，2個(gè)No。Sunny <-5Overcast <- 4Rain <-5Sunny1 <- 2/5Sunny2 <- 3/5Overcast1 <-4/4Rain1 <-3/5Rain2 <-2/5#Temperature中Ho

20、t總共4條記錄，其中2個(gè)Yes，2個(gè)No；Mild有6條記錄，4個(gè)Yes，2個(gè)No；Cool有4條記錄，3個(gè)yes，一個(gè)No。Hot <-4Mild <-6Cool <-4Hot1 <-2/4Hot2 <- 2/4Mild1 <-4/6Mild2 <-2/6Cool1 <-3/4Cool2 <-1/4#Humidity中High中共有7條記錄，其中3個(gè)Yes，4個(gè)No;Normal有7條記錄，6個(gè)Yes，1個(gè)No。High <-7Normal <- 7High1 <- 3/7High2 <- 4/7Normal1 &

21、lt;- 6/7Normal2 <-1/7#Wind中Weak有8條記錄，6個(gè)Yes，2個(gè)No；Strong有6條記錄，3個(gè)Yes，3個(gè)No。Weak <- 8Strong <- 6Weak1 <- 6/8Weak2 <- 2/8Strong1 <-3/6Strong2 <-3/6#計(jì)算熵entropy1 <- function(a) #一個(gè)參數(shù)計(jì)算熵的方式return(-a * logb(a,2)entropy2 <- function(a,b) #兩個(gè)參數(shù)計(jì)算熵的方式return(-a * logb(a,2)- b* logb(b,2)

22、entropy3 <- function(a,b,c)#三個(gè)參數(shù)計(jì)算熵的方式return(-a * logb(a,2)- b* logb(b,2)- c* logb(c,2)entropy2(S1,S2) #Entropy（S）的熵entropy2(Rain1 ,Rain2) #Entropy(Rain) Rain的熵entropy1(Overcast1) #Entropy(Overcast) Overcast的熵entropy2(Sunny1,Sunny2) #Entropy(Sunny) Sunny的熵entropy2(Hot1 ,Hot2) #Entropy(Hot) Hot的熵e

23、ntropy2(Mild1 ,Mild2) #Entropy(Mild) Mild的熵entropy2(Cool1 ,Cool2) #Entropy(Sunny) Sunny的熵entropy2(High1 ,High2) #Entropy(High) High的熵entropy2(Normal1 ,Normal2) #Entropy(Normal) Normal的熵entropy2(Weak1 ,Weak2) #Entropy(Weak) Weak的熵entropy2(Strong1 ,Strong2) #Entropy(Strong) Strong的熵entropy3(Sunny/14 ,

24、Rain/14,Overcast/14)#Entropy(Outlook) #Outlook的熵entropy3(Hot/14 ,Mild/14,Cool/14)#Entropy(Temperature) #Temperature的熵entropy2(High/14 ,Normal/14)#Entropy(Humidity) #Humidity的熵entropy2(Weak/14 ,Strong/14)#Entropy(Humidity) #Humidity的熵#print(entropy2(S1,S2),entropy2(Rain1 ,Rain2),entropy1(Overcast1),e

25、ntropy2(Sunny1,Sunny2),entropy2(Hot1 ,Hot2),entropy2(Mild1 ,Mild2),entropy2(Cool1 ,Cool2),entropy2(High1 ,High2) ,entropy2(Normal1 ,Normal2),entropy2(Weak1 ,Weak2),entropy2(Strong1 ,Strong2),entropy3(Sunny/14 ,Rain/14,Overcast/14),)#計(jì)算信息增益gain_outlook <- entropy2(S1,S2)-Sunny/14*entropy2(Sunny1,S

26、unny2)-Rain/14*entropy2(Rain1 ,Rain2)-Overcast/14*entropy1(Overcast1)#Outlook的信息增益gain_temperature <- entropy2(S1,S2)-Hot/14*entropy2(Hot1,Hot2)-Mild/14*entropy2(Mild1 ,Mild2)-Cool/14*entropy2(Cool1,Cool2)#Temperature的信息增益gain_humidity <- entropy2(S1,S2)-High/14*entropy2(High1,High2)-Normal/14

27、*entropy2(Normal1 ,Normal2)#Humidity的信息增益gain_Wind <- entropy2(S1,S2)-Weak/14*entropy2(Weak1,Weak2)-Strong/14*entropy2(Strong1 ,Strong2)#Windy的信息增益print(gain_outlook)print(gain_temperature )print(gain_humidity)print(gain_Wind)#計(jì)算信息增益率gain_outlook/entropy3(Sunny/14 ,Rain/14,Overcast/14)#GainRatio(

28、Outlook)gain_temperature/entropy3(Hot/14 ,Mild/14,Cool/14)#GainRatio(Temperature)gain_humidity /entropy2(High/14 ,Normal/14)#GainRatio(Humidity)gain_Wind/entropy2(Weak/14 ,Strong/14)#GainRatio(Windy) 2、 以Sunny為子節(jié)點(diǎn)的計(jì)算#計(jì)算以O(shè)utlook為根節(jié)點(diǎn)，以Sunny為子樹的熵增益的計(jì)算#總共5條記錄，2個(gè)yes,3個(gè)NoSum <- 5 #記錄的總數(shù)目S1 <-2/5 #總的

29、記錄的劃分S2 <-3/5#Temperature中Hot總共2條記錄，其中2個(gè)Yes；Mild有2條記錄，1個(gè)Yes，1個(gè)No；Cool有1條記錄，1個(gè)yes。Hot <-2Mild <-2Cool <-1Hot1 <-2/2Mild1 <-1/2Mild2 <-1/2Cool1 <-1/1#Humidity中High中共有3條記錄，其中3個(gè)No;Normal有2條記錄，2個(gè)Yes。High <-3Normal <- 2High1 <- 3/3Normal1 <- 3/3#Wind中Weak有3條記錄，1個(gè)Yes，2個(gè)N

30、o；Strong有2條記錄，1個(gè)Yes，1個(gè)No。Weak <- 3Strong <-2Weak1 <- 2/3Weak2 <- 1/2Strong1 <-1/2Strong2 <-1/2#計(jì)算熵entropy1 <- function(a) #一個(gè)參數(shù)計(jì)算熵的方式return(-a * logb(a,2)entropy2 <- function(a,b) #兩個(gè)參數(shù)計(jì)算熵的方式return(-a * logb(a,2)- b* logb(b,2)entropy3 <- function(a,b,c)#三個(gè)參數(shù)計(jì)算熵的方式return(-a

31、 * logb(a,2)- b* logb(b,2)- c* logb(c,2)entropy2(S1,S2) #Entropy（S）的熵entropy1(Hot1 ) #Entropy(Hot) Hot的熵entropy2(Mild1 ,Mild2) #Entropy(Mild) Mild的熵entropy1(Cool1 ) #Entropy(Sunny) Sunny的熵entropy1(High1 ) #Entropy(High) High的熵entropy1(Normal1 ) #Entropy(Normal) Normal的熵entropy2(Weak1 ,Weak2) #Entrop

32、y(Weak) Weak的熵entropy2(Strong1 ,Strong2) #Entropy(Strong) Strong的熵entropy3(Hot/Sum ,Mild/Sum,Cool/Sum)#Entropy(Temperature) #Temperature的熵entropy2(High/Sum ,Normal/Sum)#Entropy(Humidity) #Humidity的熵entropy2(Weak/Sum ,Strong/Sum)#Entropy(Windy) #Windy的熵#計(jì)算信息增益gain_temperature <- entropy2(S1,S2)-Ho

33、t/Sum*entropy1(Hot1)-Mild/Sum*entropy2(Mild1 ,Mild2)-Cool/Sum*entropy1(Cool1)#Temperature的信息增益gain_humidity <- entropy2(S1,S2)-High/Sum*entropy1(High1)-Normal/Sum*entropy1(Normal1 )#Humidity的信息增益gain_Wind <- entropy2(S1,S2)-Weak/Sum*entropy2(Weak1,Weak2)-Strong/Sum*entropy2(Strong1 ,Strong2)#W

34、indy的信息增益print(gain_outlook)print(gain_temperature )print(gain_humidity)print(gain_Wind)#計(jì)算信息增益率gain_temperature/entropy3(Hot/Sum ,Mild/Sum,Cool/Sum)#Entropy(Temperature)gain_humidity /entropy2(High/Sum ,Normal/Sum)#Entropy(Humidity)gain_Wind/entropy2(Weak/Sum ,Strong/Sum)#Entropy(Windy) 3、 以Rain為子節(jié)

35、點(diǎn)的計(jì)算#計(jì)算以O(shè)utlook為根節(jié)點(diǎn)，以Rain為子樹的熵增益的計(jì)算#總共5條記錄，3個(gè)yes,2個(gè)NoSum <- 5 #記錄的總數(shù)目S1 <-3/5 #總的記錄的劃分S2 <-2/5#Temperature中Mild有3條記錄，2個(gè)Yes，1個(gè)No；Cool有2條記錄，1個(gè)yes，1個(gè)No。Hot <-2Mild <-2Cool <-1Mild1 <-2/3Mild2 <-1/3Cool1 <-1/2Cool2 <-1/2#Humidity中High中共有2條記錄，其中1個(gè)yes，1個(gè)No;Normal有3條記錄，2個(gè)Yes，1

36、個(gè)No。High <-3Normal <- 2High1 <- 1/2High2 <- 1/2Normal1 <- 2/3Normal1 <- 1/3#Wind中Weak有3條記錄，3個(gè)Yes；Strong有2條記錄，2個(gè)No。Weak <- 3Strong <-2Weak1 <- 3/3Strong1 <-2/2#計(jì)算熵entropy1 <- function(a) #一個(gè)參數(shù)計(jì)算熵的方式return(-a * logb(a,2)entropy2 <- function(a,b) #兩個(gè)參數(shù)計(jì)算熵的方式return(-a * logb(a,2)- b* lo