为了演示ID3 算法的详细操作,训练例子入下图。这里,目标属性PlayTennis 对于不同的星期六上午具有yes 和no两个值,我们将依据其它属性来预測这个目标属性值。
先考虑这个算法的第一步,创建决策树的最顶端结点。
哪一个属性该在树上第一个被測试呢?
ID3算法计算每个候选属性(也就是Outlook,Temperature,Humidity,和Wind)的信息增益,然后选择信息增益最高的一个。全部四个属性的信息增益为:
Gain(S,Outlook)=0.246
Gain(S,Humidity)=0.151
Gain(S,Wind)=0.048
Gain(S,Temperature)=0.029
当中S 表示来自下图的训练例子的集合。
依据信息增益标准,属性Outlook 在训练例子上提供了对目标属性PlayTennis 的最好预測。
所以,Outlook 被选作根结点的决策属性,并为它的每个可能值(也就是Sunny,Overcast 和Rain)在根结点下创建分支。
同一时候画出的还有被排列到每个新的后继结点的训练例子。注意到每个Outlook=Overcast 的例子也都是PlayTennis 的正例。所以,树的这个结点成为一个叶子结点,它对目标属性的分类是PlayTennis=Yes。相反,相应Outlook=Sunny 和Outlook=Rain 的后继结点还有非0的熵,所以决策树会在这些结点下进一步展开。
对于非终端的后继结点,再反复前面的过程选择一个新的属性来切割训练例子,这一次仅使用与这个结点关联的训练例子。已经被收编入树的较高结点的属性被排除在外,以便不论什么给定的属性在树的随意路径上最多仅出现一次。对于每个新的叶子结点继续这个过程,直到满足下面两个条件中的任一个:
1) 全部的属性已经被这条路径包括
2) 与这个结点关联的全部训练例子都具有相同的目标属性值(也就是它们的熵为0)
下图演示了算法的求解过程:
与其它的归纳学习算法一样,ID3算法能够被描写叙述为从一个如果空间中搜索一个拟合训练例子的如果。
被ID3 算法搜索的如果空间就是可能的决策树的集合。
ID3算法以一种从简单到复杂的爬山算法遍历这个如果空间。
从空的树開始,然后逐步考虑更加复杂的如果,目的是搜索到一个正确分类训练数据的决策树。
引导这样的爬山搜索的评估函数是信息增益度量。下图描写叙述了这样的搜索: