ID3决策树算法是基于信息增益来构建的，信息增益可以由训练集的信息熵算得，这里举一个简单的例子
data=[心情好天气好出门
心情好天气不好出门
心情不好天气好出门
心情不好天气不好不出门]
前面两列是分类属性，最后一列是分类
分类的信息熵可以计算得到：出门=3，不出门=1，总行数=4分类信息熵=-(3/4)*log2(3/4)-(1/4)*log2(1/4)
第一列属性有两类，心情好，心情不好
心情好,出门=2，不出门=0，行数=2
心情好信息熵=-(2/2)*log2(2/2)+(0/2)*log2(0/2)
同理
心情不好信息熵=-(1/2)*log2(1/2)-(1/2)*log2(1/2)
心情的信息增益=分类信息熵-心情好的概率*心情好的信息熵-心情不好的概率*心情不好的信息熵
由此可以得到每个属性对应的信息熵，信息熵最大的即为最优划分属性。
还是这个例子，加入最优划分属性为心情
然后分别在心情属性的每个具体情况下的分类是否全部为同一种，若为同一种则该节点标记为此类别，
这里我们在心情好的情况下不管什么天气结果都是出门所以，有了
心情不好的情况下有不同的分类结果，继续计算在心情不好的情况下，其它属性的信息增益，
把信息增益最大的属性作为这个分支节点，这个我们只有天气这个属性，那么这个节点就是天气了，
天气属性有两种情况，如下图
在心情不好并且天气好的情况下，若分类全为同一种，则改节点标记为此类别
有训练集可以，心情不好并且天气好为出门，心情不好并且天气不好为不出门，结果入下图
对于分支节点下的属性很有可能没有数据，比如，我们假设训练集变成
data=[心情好晴天出门
心情好阴天出门
心情好雨天出门
心情好雾天出门
心情不好晴天出门
心情不好雨天不出门
心情不好阴天不出门]
如下图：
在心情不好的情况下，天气中并没有雾天，我们如何判断雾天到底是否出门呢？我们可以采用该样本最多的分类作为该分类，这里天气不好的情况下，我们出门=1，不出门=2，那么这里将不出门，作为雾天的分类结果
在此我们所有属性都划分了，结束递归，我们得到了一颗非常简单的决策树。
下面附上我的实现ID3决策树算法代码：（octave/matlab，该程序本人已经验证过可以执行且结果正确，这里属性集我偷了一个懒，
没有标识出具体属性名，我是使用矩阵中的列号）
著名的还有C4.5决策树算法，它是ID3的改进，作者都是同一个人，罗斯昆兰