ID3算法实验
08级第一小组介绍：
ID3算法可分为主算法和建树算法两种。

（1）ID3主算法。

主算法流程如图所示。

其中PE、NE分别表示正例和反例集，它们共同组成训练集。

PE'、PE''和NE'、NE''分别表示正例集和反例集的子集。

ID3主算法流程
（2）建树算法。

采用建树算法建立决策树。

首先，对当前子例进行同类归集。

其次，计算各集合属性的互信息，选择互信息最大的属性Ak。

再次，将在Ak处取值相同的子例归于同一子集，Ak取几个值就几个子集。

最后,对既含正例又含反例的子集递归调用建树算法。

若子集仅含正例或反例，对应分支标上P或N，返回调用处。

ID3算法采用自顶向下不回溯的策略搜索全部属性空间并建立决策树，算法简单、深度小、分类速度快。

但是，ID3算法对于大的属性集执行效率下降快、准确性降低，并且学习能力低下。

考虑到本文所涉及到的数据量并很小，下文分类分析采用了该算法。

决策树学习是把实例从根结点排列到某个叶子结点来分类实例，叶子结点即为实例所属的分类。

学习到的决策树能再被表示成多个if-then的规则。

ID3算法是一种决策树算法。

对下载的ID3算法程序进行阅读和调试后，做了相关实验，以下是相关记录。

1、试验数据
该算法的试验数据有两个：data.dat和data.tag，分别存放训练样例和各个属性列表：
data.dat:
data.tag:
其中，训练样例集合的试验数据由课本第3.4。

2节给出，分别将其属性使用离散值数据表示，在data.tag文件中可以看到离散值其表示的属性分别对应。

2、运行结果
试验结果，是以if-then形式输出决策树，其运行界面如图：
可以将结果整理为：
if { humidity = 2.00 then
if { outlook = 3.00 then
if{ w indy = 2.00 then ON
else OFF }
else ON }
else if { outlook = 2.00 then
if { outlook = 3.00 then
if { windy = 2.00 then ON
else OFF }
else ON }
else OFF }
}
该结果与给定的训练样例是一致的。

可以看出，对于给定的这个训练样例集合，目标函数的取值与temperature这个属性没有太大关系，但是，对于未见实例，则不一定。

所以训练样例的分布是很重要的。