- ID3决策树学习算法是以信息增益为准则来划分的属性的。对于一个属性的信息增益越大,一般而言,使用这个属性来进行划分所获得的“纯度提升”越大。
- ID3中的ID是Iterative Dichotomiser(迭代二分器)的简称。
数据表如下图:
1.首先计算结果选项出现的频率:
类1(p1) | 类2(p2) |
0.6429 | 0.3571 |
2.计算因变量的期望信息:
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’ 划分之后所获得的三个枝节点的信息熵为:
(2)对于以‘属性 2’ 划分得到子集,同理可求出:
(3)对于以‘属性 3’ 划分得到子集,同理可求出:
-
若不加处理直接对属性2进行划分,这样的决策树很明显不具有泛化能力,无法对新样本进行有效预测。所以考虑对属性2划分为3个子集: D1(60<x<=72) ; D2(72<x<=84) ; D1(84<x<=96)。
由此以‘属性 2’ 可求出:
4. 自变量的期望信息、信息增益的计算
显然,‘属性1’的信息增益最大,所以把它选为划分属性。下图给出了基于‘属性1’对根节点进行划分的结果,各分支结点的样例子集显示在结点中:
5. 进一步划分
- 对于分支结点C的样例集合,显然可知,下一分支再用属性3判别即可。
- 对于分支结点A的样例集合H1{1,2,3,4,5}的5个样例。用属性2的判别即可到达最大信息增益。
6. 决策树
所以综上分析决策树如下图所示: