决策树的简单实现

熵

我第一次接触这个字是在高中的化学课堂上，这里的熵是用来衡量一个系统混乱程度的度量。信息熵是信息论创始人香农提出的，它和上面提到的熵其实是正相关的。当我们面对一件非常不确定的事件时，我们需要大量的信息才能掌控此事件，也就是说信息量的大小和事件的不确定性有着直接的关系。 设X是一个有限状态的离散型随机变量,熵与概率之间的关系：

决策树

最近同学说食堂饭很难吃，我常去食堂，发现其实并不是经常性的难吃，只是偶尔有几次吃得想吐，由于宿舍楼里就这么一个食堂，大家都很懒，还是有很多人去排队吃食堂，下面以此作为一个例子简单实现一下，来简单预测一下明天的情况：

信息增益:得知特征A的信息而使得数据集D的信息的不确定性减少的程度

通过信息增益生成决策树: 计算一下Gain(天气):

同理算出 Gain(菜) = 0.252 bit，根据计算结果，Gain最大的作为起始开始生成决策树：

代码实现：