决策树和信息熵

有没有玩过或听过这样一个游戏：参与游戏的一方在脑海里想好某个事物，然后其他参与者向他提问的方式猜答案，回答者只能回答是还是不是。问问题的人通过答复信息的判断推理，不断缩小待猜事物的范围，最后给出答案。

其实上面的过程就类似于决策树的工作原理。这个概念真的很简单，你都不需要了解机器学习的知识，就能搞明白决策树是如何工作的，所以决策树算法非常流行，也是最经常使用的数据挖掘算法之一。

就像上面那个游戏，关键点在于如何高效的问问题，那决策树的关键，就在于如何划分数据集。

划分数据集的大原则就是：将无序的数据变得更加有序。那用什么衡量有序和无需呢？就是信息熵。

要说信息熵，先说说信息量。信息量的公式如下：

其中p(x)是事件发生的概率。从公式可以看出，发生概率越大，信息量越小。显然是这样，我如果说太阳从东边升起，基本没什么信息量。如果我说太阳从西边升起，那信息量就太大了。

下面我们正式引出信息熵。

信息量度量的是一个具体事件发生了所带来的信息，而熵则是在结果出来之前对可能产生的信息量的期望——考虑该随机变量的所有可能取值，即所有可能发生事件所带来的信息量的期望。说白了就是对所有信息量求和：

所以说，熵越大，不确定性越大，越无序；熵越小，确定性越大，越有序。

所以我们构建决策树划分数据集的时候，应该选择划分前后信息熵变化最大的那种方式。划分前后信息熵变化称为信息增益（information gain），但实际上在数据集划分后，信息熵是减少的，信息熵减少也叫信息增益，这也是经常会困扰初学者的一个地方。下篇文章，我们将用python代码构建一个决策树。

长

按

解

锁