机器学习-决策树(ID3算法及详细计算推导过程)

发布于:2024-11-29 ⋅ 阅读:(34) ⋅ 点赞:(0)

        决策树是一种基于树结构进行决策的机器学习算法 ,以下是关于它的详细介绍:

1.基本原理

  • 决策树通过一系列的条件判断对样本进行分类或预测数值。它从根节点开始,根据不同的属性值逐步将样本划分到不同的分支,直到到达叶节点,每个叶节点代表一个类别或数值。
  • 本质是通过条件判断对样本分类,每个内部节点是一个属性上的测试,分支是测试输出,叶节点是类别或值,从根节点到叶节点的路径对应一条分类规则。

2.主要组成部分

  • 节点:包括根节点、内部节点和叶节点。根节点是决策树的起始点,内部节点表示在某个属性上的测试,叶节点则给出最终的分类结果或数值预测。
  • 分支:连接各个节点,代表根据节点测试结果的不同走向,即不同的决策路径

3.决策树举例 

        图1是一个简单的用来对鸟类进行分类的决策树。在该图中,根节点包含各种鸟类;叶节点是所能识别的各种鸟的名称;中间节点是鸟的一些属性;边是鸟的某一属性的属性值;从根节点到叶节点的每一条路径都描述了一种鸟,它包括该种鸟的一些属性及相应的属性值。

        决策树还可以表示为规则的形式。上图的决策树可表示为如下规则集:    

  • IF  鸟类会飞   AND  是家养的    THEN  可能是和平鸽    
  • IF  鸟类会飞   AND  不是家养的  THEN  可能是信天翁    
  • IF  鸟类不会飞 AND  会游泳      THEN  可能是企鹅    
  • IF  鸟类不会飞 AND  不会游泳    THEN  可能是鸵鸟    

        决策树学习过程实际上是一个构造决策树的过程。当学习完成后,就可以利用这棵决策树对未知事物进行分类。

4.重要概念

4.1信息熵

        信息熵是对信息源整体不确定性的度量。假设S为样本集,S中所有样本的类别有k种,如y1,y2,…,yk,各种类别样本在S上的概率分布分别为P(y1),P(y2),…,P(yk),则S的信息熵可定义为:

        其中,概率P(yj)(j=1,2,…,k),实际上为yj的样本在S中所站的比例;对数可以是以各种数为底的对数,在ID3算法中,我们取以2为底的对数。E(S)的值越小,S的不确定性越小,即其确定性越高。 

4.2信息增益

        信息增益(information gain)是对两个信息量之间的差的度量。其讨论涉及到样本集S中样本的结构。对S中的每一个样本,除其类别外,还有其条件属性,或简称为属性。若假设S中的样本有m个属性,其属性集为X={X1,X2,…,Xm},且每个属性均有r种不同的取值,则我们可以根据属性的不同取值将样本集S划分成r个不同的子集S1, S2, ... , Sro。此时,可得到由属性x;的不同取值对样本集S进行划分后的加权信息熵

        其中,t为条件属性x;的属性值;St为x ;= t时的样本子集;E(St)为样本子集St信息熵;IS|和|St分别为样本集S和样本子集St的大小,即样本个数。有了信息熵和加权信息熵,就可以计算信息增益。所谓信息增益就是指E(S)和E(S,x1)之间的差,即

        可见,信息增益所描述的是信息的确定性,其值越大,信息的确定性越高。后面会会给出例题,看例题就明白了。

5.ID3算法

        ID3算法的学习过程是一个以整个样本集为根节点,以信息增益最大为原则,选择条件属性进行扩展,逐步构造出决策树的过程。若假设S={s1,s2,…sn}为整个样本集,X={x1,x2,…,xm}为全体属性集,Y={y1,y2,…yk}为样本类别。则ID3算法描述如下:    

        (1) 初始化样本集S={s1,s2,…sn}和属性集X={x1,x2,…,xm},生成仅含根节点(S, X)的初始决策树。    

        (2) 如果节点样本集中的所有样本全都属于同一类别,则将该节点标记为叶节点,并标出该叶节点的类别。算法结束。 否则执行下一步。    

        (3) 如果属性集为空;或者样本集中的所有样本在属性集上都取相同值,即所有样本都具有相同的属性值,则同样将该节点标记为叶节点,并根据各个类别的样本数量,按照少数服从多数的原则,将该叶节点的类别标记为样本数最多的那个类别。算法结束。否则执行下一步。

        (4) 计算每个属性的信息增益,并选出信息增益最大的属性对当前决策树进行扩展。    

        (5) 对选定属性的每一个属性值,重复执行如下操作,直止所有属性值全部处理完为止:     ① 为每一个属性值生成一个分支;并将样本集中与该分支有关的所有样本放到一起,形成该新生分支节点的样本子集;     ② 若样本子集为空,则将此新生分支节点标记为叶节点,其节点类别为原样本集中最多的类别;     ③ 否则,若样本子集中的所有样本均属于同一类别,则将该节点标记为叶节点,并标出该叶节点的类别。  

        (6) 从属性集中删除所选定的属性,得到新的属性集。    

        (7) 转第(3)步。

5.1 ID3算法举例

  • info:信息量
  • E:信息熵(信息量的加权求和)
  • gain:信息增益

用上图来计算构建决策树

5.1.1计算总的信息量

1.在上表中先看序号,总共有9个P,5个N,则我们可以计算出总的信息量为

2.我们要在天气、气温、湿度和风中选择一个做为根节点 

(1)天气的信息增益

先看天气,天气为时,有2个P,三个N,则信息量

天气为时,有三个P,两个N,则信息量

天气为多云时,有三个P,0个N,则信息熵

天气各种情况加权求和,即天气的信息熵为:

故基于天气的信息增益为:

 

(2)气温的信息增益

 气温-热:

 气温-适中:

气温-冷:

各个气温情况加权求和:

基于气温的信息增益为: 

同理我们可以计算湿度和风的信息增益

3.天气的信息增益最大,所以我们选择天气作为根节点

 

4.天气作为根节点,则他的子树我们就用相同的方法即可计算出来 

 


网站公告

今日签到

点亮在社区的每一天
去签到