准备工作

学习决策树，要先了解信息熵和信息增益等概念。
参考：
https://blog.csdn.net/zhengudaoer/article/details/80240529
【例如】
买西瓜，假设我们要根据西瓜的味道，颜色来判断它是好瓜还是坏瓜：

image.png

信息量

信息量

关于信息量，下面有一些不太严谨但比较生动的描述：
我们公司说过年要上班。这信息量太大了，简直是爆炸性的新闻。
如果全国有10000家公司，已知有9999家公司春节放假，只有我们一家公司春节上班。也就是1/10000的概率春节上班，这概率很小了。
公司成功的“鸡立鹤群”，区别于其他9999家公司，坐实敲定了一个很小概率的事件（1/10000的概率春节上班）。本来过年上班是非常不确定的一件事（因为大多数时候过年都是放假的），没想到公司把这个“非常不确定”给解除了，直接敲定过年上班了。
这意味着，信息量越大，概率越小，解除的不确定程度越大，信息的可划分性越大。

如果我们公司说春节正常放假。那这就没什么信息量了。
全国有10000家公司，已知有9999家公司春节放假。我们公司也放假，相当于这10000家公司全都放假。也就是10000/10000的概率春节放假，很大的概率。
公司的信息量几乎为零。因为大家都放假，你也放假。
我们公司成功的"泯然于众"，没法区别于其他公司了。本来过年就应该放假（因为大多数时候过年都是放假的），公司确定了一件“本身就很确定”的事情，没有解除掉什么“不确定”。
这意味着，信息量越小，概率越大，解除的不确定程度越小，信息的可划分性越小。

信息熵：

今天下午公司要宣布过年是否放假。
公司还没宣布（事情还没发生），大家只能靠以往的经验考虑到所有可能性，来预期公司即将发布的通知里有多少信息量。
信息量度量的是一个具体事件发生所带来的信息，而熵则是在结果出来之前对可能产生的信息量的期望——考虑该随机变量的所有可能取值，即所有可能发生事件所带来的信息量的期望。
信息熵的本质是：事件的平均信息量（即期望）。

条件信息熵：

①这里有一个公式：
书面描述：给定条件X的情况下，所有不同X值情况下Y的信息熵的平均值。
②还有另外一个公式：（好理解，但不常用）
书面描述：H(Y|X)=H(X,Y)-H(X)，事件(X,Y)发生所包含的熵，减去事件X单独发生的熵，即为在事件X发生的前提下，Y发生“新”带来的熵。

信息增益：

Gain(X,Y)=H(X)-H(X|Y)
H(X)：X的信息熵
H(X|Y)：条件信息熵，前提条件是Y。
信息增益表明信息源和条件信息源之间的信息交互量（在Y这个前提，X的不确定性的降低程度），
这个交互量越大说明信息（X）在该条件（Y）下越容易划分。
缺点：偏爱取值较多的特征（Y）。

信息增益率：

Gain_radio(X,Y)=(H(X)-H(X|Y)) / H(Y)
因为信息增益的缺点，所以有了信息增益率。
不过它也有缺点：计算复杂度高。

决策树：

做分类。
想用什么特征来画这棵树？
Kd-tree是用方差选特征，再用特征值的中位数画树。
决策树呢，就是用前面说的信息增益和信息增益率来选特征，从而画树。
比如算出Gain(瓜,味道)，在算出Gain(瓜,颜色)，
Gain(瓜,味道)值大，就用特征味道来划分样本。
Gain(瓜,颜色)值大，就用特征颜色来划分样本。
ID3：用信息增益分类
C4.5：用信息增益率分类