数据词典：ID3算法（ID3 Algorithm）

赵老师

1986年，J. Ross Quinlan在概念学习系统研究的基础上提出了ID3算法。ID3算法采用自顶向下的贪婪搜索遍历可能的决策树空间，在每个结点选取能最好分类样例的属性。这个过程一直重复，直到这棵树能完美分类训练样例，或所有的属性都已被使用过为止。

用ID3算法构造决策树的过程从“哪一个属性将在树的根结点被测试”这个问题开始。为了回答这个问题，我们使用统计测试来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作树的根结点。然后，为根结点属性的每个可能值产生一个分枝，并把训练样例分配到适当的分枝（即样例属性值所对应的分枝）之下。重复整个过程，用每个分枝结点关联的训练样例来选取在该点被测试的最佳属性。这样，就形成了对合格决策树的贪婪搜索，所以ID3算法不回溯，不重新考虑以前做过的选择。

ID3算法的核心问题是选取每个结点上要测试的属性。我们当然希望选择的是最有利于分类实例的属性。但是，如何衡量一个属性价值的高低呢？这个问题没有统一的答案，在机器学习中有不同的度量方法。ID3算法根据信息增益来度量给定属性区分训练样例的能力。实际上，ID3算法选择信息增益最大的属性作为决策树结点。

【出处】鲍军鹏,张选平.人工智能导论（第2版）,机械工业出版社,2021年1月.