决策树详解，从熵说起
熵，一个神奇的工具，用来衡量数据集信息量的不确定性。
首先，我们先来了解一个指标，信息量。对于任意一个随机变量X，样本空间为{X1,X2，…,Xn},对于任意的样本Xi，样本Xi的信息量也就是l(Xi) = -log(p(Xi))。由于p(Xi)是为样本Xi的概率，也可以说是类Xi的概率，那么l(Xi)的取值范围为(+∞，0]。也就是X的的概率越小，其含有的信息量越大，反之亦然。这也不难理解，Xi的发生的概率越大，我们对他的了解越深，那么他所含有的信息量就越小。如果随机变量X是常量，那么我们从任意一个Xi都可以获取样本空间的值，那么我们可以认为X没有任何信息量，他的信息量为0。如果说，我们要把随机变量X样本空间都了解完，才能获得X的信息，那么我们可以认为X的信息量“无穷大”，其取值为log（2，n)。
紧接着，我们就提出了随机变量X的信息熵，也就是信息量的期望，H(X) = -∑ni=1p(Xi)log2(p(Xi))，从离散的角度得出的公式。他有三个特性：
- 单调性，即发生概率越高的事件，其所携带的信息熵越低。极端案例就是“太阳从东方升起”，因为为确定事件，所以不携带任何信息量。从信息论的角度，认为这句话没有消除任何不确定性。也就是样本空间的p(Xi)均为1。
- 非负性，即信息熵不能为负。这个很好理解，因为负的信息，即你得知了某个信息后，却增加了不确定性是不合逻辑的。
- 累加性，即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和。
有了熵这个基础，那么我们就要考虑决策树是怎么生成的了。对于随机变量X的样本个数为n的空间，每个样本都有若干个相同的特征，假设有k个。对于任意一个特征，我们可以对其进行划分，假设含有性别变量，那么切分后，性别特征消失，变为确定的值，那么随机变量X信息的不确定性减少。以此类推，直到达到我们想要的结果结束，这样就生成了若干棵树，每棵树的不确定性降低。如果我们在此过程中进行限制，每次减少的不确定性最大，那么这样一步一步下来，我们得到的树，会最快的把不确定性降低到最小。每颗树的分支，都可以确定一个类别，包含的信息量极少，确定性极大，这种类别，是可以进行预测的，不确定性小，稳定，可以用于预测。
有了以上的知识储备，那么我们要想生成一颗决策树，只需要每次把特征的信息量最大的那个找出来进行划分即可。也就是不确定性最大的那个分支，我们要优先划分。这就会得出另外一个定义，条件信息熵。也就是我的
