基于ID3算法实现的离散决策树生成。

ID3算法的基本思想是贪心算法，采用自上而下的分而治之的方法构造决策树。首先检测训练数据集的所有特征，选择信息增益最大的特征A建立决策树根节点，由该特征的不同取值建立分枝，对各分枝的实例子集递归，用该方法建立树的节点和分枝，直到某一子集中的数据都属于同一类别，或者没有特征可以在用于对数据进行分割。ID3算法总是选择具有最高信息增益(或最大熵压缩)的属性作为当前结点的测试属性。该属性使得结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。这种信息理论方法使得对一个对象分类所需的期望测试数目达到最小，并尽量确保一棵简单的(但不必是最简单的)树来刻画相关的信息。

在ID3算法中，计算信息增益时，由于信息增益存在一个内在偏置，它偏袒具有较多值的属性，太多的属性值把训练样例分割成非常小的空间。因此，这个属性可能会有非常高的信息增益，而且被选作树的根结点的决策属性，并形成一棵深度只为一级但却非常宽的树，这棵树可以理想地分类训练数据。但是这个决策树对于测试数据的分类性能可能会相当差，因为它过分地完美地分割了训练数据，不是一个好的分类器。

在J.Mingers关于ID3算法的研究中，通过对五种包含噪音的学习样例的实验发现，多数情况下过度拟合导致决策树的精度降低了10%一25%。过度拟合不仅影响决策树对未知实例的分类精度，而且还会导致决策树的规模增大。一方面，叶子节点随分割不断增多。在极端的情况下，在一棵完成分割的决策树中，每个叶子节点中只包含一个实例。此时决策树在学习样例上的分类精度达到100%，而其叶子节点的数目等于学习样例中实例的数目。但是显然这棵决策树对任何未见的实例都是毫无意义的。另一方面，决策树不断向下生长，导致树的深度增加。因为每一条自根节点到叶子节点的路径都对应一条规则，所以树的深度越大，其对应的规则越长。作为一种蕴含于学习样例中的知识，这样一组过长的规则集合是很难被人理解的。过度拟合现象的存在，无论是对决策树的分类精度，还是对其规模以及可理解性都产生了不利的影响。因此对与决策树的剪枝是非常有必要的。