ID3(Examples, TargetAttribute, Attributes)
/*
Examples:训练样本集
TargetAttribute:需要预测的目标属性
Attributes:目标属性之外的其他供学习决策树的属性列表
*/
若所有Examples的TargetAttribute值相同均为a, 则返回节点值为a的单节点树
否则说明还需要根据其他属性进一步进行判断分析
若Attributes为空，则说明没有属性可以用来判断了，此时返回单节点数，节点的值为当前所有Examples中最普遍的TargetAttribute值（这是一个合理的假定）
否则，
根据信息增益最大的原则选取最好的属性bestAttr，树节点的值为bestAttr。
对于bestAttr的每个可能值v，树枝上的值为v。
Examples_v为Examples中bestAttr值为v的子集
递归计算子树ID3(Examples_v, TargetAttribute, Attributes - {bestAttr})
附信息增益和熵：
训练样本集Examples的熵就是其关于TargetAttribute各个值的分布情况，
若分布越均匀，则熵越大，即信息量越大。若分布越单一，则熵越小，即信息量小。
如何选择最好的属性来进行决策呢？
我们选取一个属性，根据其各个值将Examples分成的子样本集，然后计算子样本集的熵之和，
信息增益=原来的Examples的熵 - 子样本集的熵之和
直观上来判断最好的属性应该是能最简单的对当前的训练样本进行分类判断，因此其熵应该是最小的决策树的根节点，即未作任何决策时，其不确定性是最大的，即熵是最大的；决策树的叶子节点，应该是确定的值，熵为0，是最小的。
决策树的决策过程其实就是降低其不确定性，减少熵的过程。所以选择属性时应该选择能够最大限度减少熵的属性，即信息增益最大的属性。
感性上来认识应该是选择能够将样本划分更加均匀的属性，当然这并不精确，均匀不能仅仅指子样本集的大小，而应该还与其值的情况有关。具体得通过计算信息增益来作判断。
所以信息增益最大的属性就是最好的属性。（注：每一个子样本的熵的计算方式和Examples的计算方式一样，
子样本集的熵之和不是简单的累加，而是要乘上起一个系数：每个子样本集的大小/Examples的大小）