机器学习第四章【决策树】学习记录:ID3练习题:给定如下一个训练集,计算并画出ID3决策树。

时间:2022-03-11 11:40:45

  • ID3决策树学习算法是以信息增益为准则来划分的属性的。对于一个属性的信息增益越大,一般而言,使用这个属性来进行划分所获得的“纯度提升”越大。
  • ID3中的ID是Iterative Dichotomiser(迭代二分器)的简称。

数据表如下图:

机器学习第四章【决策树】学习记录:ID3练习题:给定如下一个训练集,计算并画出ID3决策树。 

    1.首先计算结果选项出现的频率:

类1(p1) 类2(p2)
0.6429 0.3571

     2.计算因变量的期望信息:

               机器学习第四章【决策树】学习记录:ID3练习题:给定如下一个训练集,计算并画出ID3决策树。

     3.  自变量的期望信息、信息增益的计算

属性2 65 70 70 70 75 78 80 80 80 85 90 90 95 96
类别 1 1 1 2 1 1 2 1 1 2 2 1 2 1
属性3
类别 1 2 1 1 2 2 2 2 1 1 1 1 1 1
(1)以‘属性 1’ 划分得到三个子集:D1(属性1=A);D2(属性1=B);D3(属性1=C)
         以‘属性 1’ 划分之后所获得的三个枝节点的信息熵为:

               

机器学习第四章【决策树】学习记录:ID3练习题:给定如下一个训练集,计算并画出ID3决策树。

 (2)对于以‘属性 2’ 划分得到子集,同理可求出:

            

机器学习第四章【决策树】学习记录:ID3练习题:给定如下一个训练集,计算并画出ID3决策树。


 (3)对于以‘属性 3’ 划分得到子集,同理可求出:             

机器学习第四章【决策树】学习记录:ID3练习题:给定如下一个训练集,计算并画出ID3决策树。


  • 若不加处理直接对属性2进行划分,这样的决策树很明显不具有泛化能力,无法对新样本进行有效预测。所以考虑对属性2划分为3个子集: D1(60<x<=72) ; D2(72<x<=84) ; D1(84<x<=96)。

                

    由此以‘属性 2’ 可求出:             

    机器学习第四章【决策树】学习记录:ID3练习题:给定如下一个训练集,计算并画出ID3决策树。

     4.  自变量的期望信息、信息增益的计算


显然,‘属性1’的信息增益最大,所以把它选为划分属性。下图给出了基于‘属性1’对根节点进行划分的结果,各分支结点的样例子集显示在结点中:

机器学习第四章【决策树】学习记录:ID3练习题:给定如下一个训练集,计算并画出ID3决策树。

      5.  进一步划分

  1. 对于分支结点C的样例集合,显然可知,下一分支再用属性3判别即可。
  2. 对于分支结点A的样例集合H1{1,2,3,4,5}的5个样例。用属性2的判别即可到达最大信息增益。

      6.  决策树

所以综上分析决策树如下图所示:

机器学习第四章【决策树】学习记录:ID3练习题:给定如下一个训练集,计算并画出ID3决策树。