C4.5决策树的生成

1、 CHANGSHA UNIVERSITY OF SCIENCE & TECHNOLOGY 题目： C4.5决策树的生成 学生姓名： 曹水根 学 号：专 业： 软件工程 年 级： 2014级 指导老师： 李平 完成时间： 2015年7月10号 一、介绍决策树（Decision tree），是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，并根据不同的属性值从该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一

2、组析取表达式规则。1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上，1993年Quinlan又提出了C4.5算法。2、 核心思想采用从信息论知识中我们直到，期望信息越小，信息增益越大，从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。设D为用类别对训练元组进行的划分，则D的熵（entropy）表示为：其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。现在我们假设将训练元组D按属性A进

3、行划分，则A对D划分的期望信息为：而信息增益即为两者的差值： C4.5算法首先定义了“分裂信息”，其定义可以表示成：其中各符号意义与ID3算法相同，然后，增益率被定义为：算法：3、 ID3算法和C4.5的比较    (1) ID3算法ID3算法的核心是：在决策树各级结点上选择属性时，用信息增益（information gain）作为属性的选择标准，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立

4、决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。  某属性的信息增益按下列方法计算。通过计算每个属性的信息增益，并比较它们的大小，就不难获得具有最大信息增益的属性。  设S是s个数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类Ci(i=1,m)。设si是类Ci中的样本数。对一个给定的样本分类所需的期望信息由下式给出：  其中pi=si/s是任意样本属于Ci的概率。注意，对数函数以2为底，其原因是信息用二进制编码。  设属性A具有v个不同值a1,a

5、2,av。可以用属性A将S划分为v个子集S1,S2,Sv，其中Sj中的样本在属性A上具有相同的值aj（j=1,2,v）。设sij是子集Sj中类Ci的样本数。由A划分成子集的熵或信息期望由下式给出：  熵值越小，子集划分的纯度越高。对于给定的子集Sj，其信息期望为  其中pij=sij/sj 是Sj中样本属于Ci的概率。在属性A上分枝将获得的信息增益是    Gain(A)= I(s1, s2, ,sm)-E(A)  ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。其缺点是：只对比较小

6、的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。(2) C4.5算法    C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：    1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；    2) 在树构造过程中进行剪枝；    3) 能够完成对连续属性的离散化处理；    4) 能够对不完整数据进行处理。

7、0;   C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。4、 实例C4.5数据集的一个示例如图4.1：图4.1 C4.5算法数据集(1)、根节点的计算数据集信息的统计如表4.1：属性OutlookTemperatureHumidityWindy总记录数记录情况属性值得个数3322149个Yes，5个No。表4.1 数据集信息数据集详细统

8、计信息如表4.2：属性属性值记录数记录的情况OutlookSunny52个Yes，3个No；Overcast44个Yes；Rain53个Yes，2个No；TemperatureHot42个Yes，2个No；Mild64个Yes，2个No；Cool44个Yes，1个No；HumidityHigh73个Yes，4个No；Normal76个Yes，1个No；WindyWeak86个Yes，2个No；Strong63个Yes，3个No；表4.2 数据集详细统计信息、根据计算熵的公式，计算熵：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的熵、计算信息增益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;、计算信息增益率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)最大，所以Outlook作为根节点。（2） 、以计算以Outlook为根节点，以Sunny为子树的熵增益率的计算Sunny记录的统计信息如表4.3，属性总记录数记录情况属性值得个数52个Yes，3个No。表4.3 Sunny记录的统计信息Sunny详细统计信息如表4.4：属性属性值记录数记

13、录的情况TemperatureHot22个Yes；Mild21个Yes，1个No；Cool11个Yes；HumidityHigh33个No；Normal22个Yes；WindyWeak31个Yes，2个No；Strong21个Yes，1个No；表4.4 Sunny详细统计信息、根据计算熵的公式，计算熵：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的熵、根据公式计算信息增益Gain(Windy)=0.03696559;Gain(Temperature)= 0.5709506;Gain(Humidity)= 0.9709506;、根据公式计算信息增益率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的子节点，也是分裂节点。（3） 、计算以Outlook为根节点，以Rain为子树的熵增益的计算Rain记录的统计信息如表4.5，属性总记录数记录情况属

16、性值得个数53个Yes，2个No。表4.5 Rain记录的统计信息Rain详细统计信息如表4.6：属性属性值记录数记录的情况TemperatureMild32个Yes，1个No；Cool21个Yes，1个No；HumidityHigh21个Yes，1个No；Normal32个Yes，1个No；WindyWeak33个Yes；Strong22个No；表4.6 Rain详细统计信息、根据计算熵的公式，计算熵：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的熵、根据公式计算信息增益Gain(Windy)=0.4709506;Gain(Temperature)= 0.4036323;Gain(Humidity)= -0.0007980202;、根据公式

18、计算信息增益率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的子节点，也是分裂节点。因此：可以构建决策树如图4.

19、2，5、 代码R语言实现，计算熵，熵增益，熵增益率。1、 计算根节点的代码：#总共14条记录，9个yes,5个NoS1 <-9/14 #总的记录的划分S2 <-5/14#Outlook中Sunny总共5条记录，其中2个Yes，3个No；Overcast总共4条记录，4个Yes；Rain总共%5条记录，3个Yes，2个No。Sunny <-5Overcast <- 4Rain <-5Sunny1 <- 2/5Sunny2 <- 3/5Overcast1 <-4/4Rain1 <-3/5Rain2 <-2/5#Temperature中Ho

20、t总共4条记录，其中2个Yes，2个No；Mild有6条记录，4个Yes，2个No；Cool有4条记录，3个yes，一个No。Hot <-4Mild <-6Cool <-4Hot1 <-2/4Hot2 <- 2/4Mild1 <-4/6Mild2 <-2/6Cool1 <-3/4Cool2 <-1/4#Humidity中High中共有7条记录，其中3个Yes，4个No;Normal有7条记录，6个Yes，1个No。High <-7Normal <- 7High1 <- 3/7High2 <- 4/7Normal1 &

21、lt;- 6/7Normal2 <-1/7#Wind中Weak有8条记录，6个Yes，2个No；Strong有6条记录，3个Yes，3个No。Weak <- 8Strong <- 6Weak1 <- 6/8Weak2 <- 2/8Strong1 <-3/6Strong2 <-3/6#计算熵entropy1 <- function(a) #一个参数计算熵的方式return(-a * logb(a,2)entropy2 <- function(a,b) #两个参数计算熵的方式return(-a * logb(a,2)- b* logb(b,2)

22、entropy3 <- function(a,b,c)#三个参数计算熵的方式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),)#计算信息增益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)#计算信息增益率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为子节点的计算#计算以Outlook为根节点，以Sunny为子树的熵增益的计算#总共5条记录，2个yes,3个NoSum <- 5 #记录的总数目S1 <-2/5 #总的

29、记录的划分S2 <-3/5#Temperature中Hot总共2条记录，其中2个Yes；Mild有2条记录，1个Yes，1个No；Cool有1条记录，1个yes。Hot <-2Mild <-2Cool <-1Hot1 <-2/2Mild1 <-1/2Mild2 <-1/2Cool1 <-1/1#Humidity中High中共有3条记录，其中3个No;Normal有2条记录，2个Yes。High <-3Normal <- 2High1 <- 3/3Normal1 <- 3/3#Wind中Weak有3条记录，1个Yes，2个N

30、o；Strong有2条记录，1个Yes，1个No。Weak <- 3Strong <-2Weak1 <- 2/3Weak2 <- 1/2Strong1 <-1/2Strong2 <-1/2#计算熵entropy1 <- function(a) #一个参数计算熵的方式return(-a * logb(a,2)entropy2 <- function(a,b) #两个参数计算熵的方式return(-a * logb(a,2)- b* logb(b,2)entropy3 <- function(a,b,c)#三个参数计算熵的方式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的熵#计算信息增益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)#计算信息增益率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为子节

35、点的计算#计算以Outlook为根节点，以Rain为子树的熵增益的计算#总共5条记录，3个yes,2个NoSum <- 5 #记录的总数目S1 <-3/5 #总的记录的划分S2 <-2/5#Temperature中Mild有3条记录，2个Yes，1个No；Cool有2条记录，1个yes，1个No。Hot <-2Mild <-2Cool <-1Mild1 <-2/3Mild2 <-1/3Cool1 <-1/2Cool2 <-1/2#Humidity中High中共有2条记录，其中1个yes，1个No;Normal有3条记录，2个Yes，1

36、个No。High <-3Normal <- 2High1 <- 1/2High2 <- 1/2Normal1 <- 2/3Normal1 <- 1/3#Wind中Weak有3条记录，3个Yes；Strong有2条记录，2个No。Weak <- 3Strong <-2Weak1 <- 3/3Strong1 <-2/2#计算熵entropy1 <- function(a) #一个参数计算熵的方式return(-a * logb(a,2)entropy2 <- function(a,b) #两个参数计算熵的方式return(-a * logb(a,2)- b* lo