决策树之ID3

        一组含n个实例的数据集，每一个实例长为m，其中包括m-1个特征(属性)，最后一个为该特征的类别标签。

        在此种数据集的基础上，有一棵树，这棵树上的非叶子节点均为某特征，叶子节点均为其父节点特征的特征值。

那么这棵树是怎么来的？

       我们 1.首先要在当前数据集中找到最适合分组的一个特征，2. 然后根据这个特征值的不同将数据分为几组，3.接着在分组完成后的子数据集中，判断当前实例的是否都属于同一类，若是，则结束，若不是，那么在当前数据集中从第一步循环。4.数据集的所有特征都遍历完了，结束。

       容易知道建树时会用到递归，递归结束的两种情况：1.所有分支下的叶子节点均有同一标签  2.数据集的所有特征都遍历完了。

其中，寻找划分数据集的最好特征

       为了确定哪一个特征是划分数据的最好特征，我们需要判断用哪个特征划分后的子数据集信息增益最高，也就是说划分后更加有序了，划分后的子数据集越有序，越说明我们用这个特征划分是合理的。

       因此，我们要对当前数据集中的每个特征计算依据其划分后的信息增益。

       1.取数据集的前m-1列，每列为一个特征下的一组值，去重后长为N，

       2.依据此N个特征值将数据分为N组，计算每一组的熵，并对该N组的熵求和，

       3.将2所得结果与划分前初始数据的熵比较得出信息增益，

       4.对m-1个特征下的一组值均作以上操作，

       5.最后求m-1个特征中信息增益最高的，此时特征变为当前的最好划分特征。