决策树--信息论必备知识
-------------------------------------------------------------------------------------------------------------------------
在学习决策树的时候，最先遇到的一个与数学有关的的问题就是信息增益，在机器学习实战这本书中，构造ID3决策树的时候，使用信息论度量信息来组织杂乱无章的数据。
一、先来理解什么是信息增益：
信息增益：熵 - 条件熵
熵：表示随机变量的不确定性。
条件熵：在一个条件下，随机变量的不确定性。
信息增益的意义：在一个条件下，信息不确定性减少的程度！
通俗地讲，X(明天下雨)是一个随机变量，X的熵可以算出来， Y(明天阴天)也是随机变量，在阴天情况下下雨的信息熵我们如果也知道的话（此处需要知道其联合概率分布或是通过数据估计）即是条件熵。两者相减就是信息增益！原来明天下雨例如信息熵是2，条件熵是0.01（因为如果是阴天就下雨的概率很大，信息就少了），这样相减后为1.99，在获得阴天这个信息后，下雨信息不确定性减少了1.99！是很多的！所以信息增益大！也就是说，阴天这个信息对下雨来说是很重要的！所以在特征选择的时候常常用信息增益，如果IG（信息增益大）的话那么这个特征对于分类来说很关键~~决策树就是这样来找特征的！
作者：Kay Zhou
链接：https://www.zhihu.com/question/22104055/answer/67014456
来源：知乎
-------------------------------------------------------------------------------------------------------------------------
这个例子讲解的已经是十分通俗易懂了，接下来，什么是熵呢？
二、什么是熵：
熵的概念首先在热力学中引入，信息熵的定义与上述这个热力学的熵，虽然不是一个东西，但是有一定的联系。
熵在信息论中代表随机变量不确定度的度量。一个离散型随机变量
的熵
定义为：
这个定义的特点是，有明确定义的科学名词且与内容无关，而且不随信息的具体表达式的变化而变化。是独立于形式，反映了信息表达式中统计方面的性质。是统计学上的抽象概念。所以这个定义如题主提到的可能有点抽象和晦涩，不易理解。那么下面让我们从直觉出发，以生活中的一些例子来阐述信息熵是什么，以及有什么用处。
直觉上，信息量等于传输该信息所用的代价，这个也是通信中考虑最多的问题。比如说：赌马比赛里，有4匹马
,获胜概率分别为
. 接下来，让我们将哪一匹马获胜视为一个随机变量
. 假定我们需要用尽可能少的二元问题来确定随机变量
的取值。
例如：问题1：A获胜了吗？问题2：B获胜了吗？问题3：C获胜了吗？最后我们可以通过最多3个二元问题，来确定X取值，即哪一匹马赢了比赛。
如果X=A，那么需要问1次（问题1：是不是A？），概率为1/2 ；
如果X=B，那么需要问2次（问题1：是不是A？问题2：是不是B？），概率为1/4 ；
如果X=C，那么需要问3次（问题1，问题2，问题3），概率为1/8 ;
如果X=D，那么同样需要问3次（问题1，问题2，问题3），概率为1/8 ；
那么很容易计算，在这种问法下，为确定
取值的二元问题数量为：
那么我们回到信息熵的定义，会发现通过之前的信息熵公式，神奇地得到了：
--------------------------------------------------------------------------------------------------------------------------------
关于熵就介绍到这里，如果还想要深入学习的话就看看知乎上的讲解吧，做决策树（ID3）的话只我们通过上面的这个例子了解认识到公式、香农熵： 
就够了。 此处的负号仅仅是用来保证熵（即信息量）是正数或者为零。而
函数基的选择是任意的（信息论中基常常选择为2，因此信息的单位为比特bits；而机器学习中基常常选择为自然常数，因此单位常常被称为nats）。得到熵之后我们就可以按照获取最大信息增益的方法划分数据集了。
作者：韩迪
链接：https://www.zhihu.com/question/22178202/answer/223017546
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
-------------------------------------------------------------------------------------------------------------------------
三、信息增益率：
熵最初是一个物理学概念，后来在数学中用来描述“一个系统的混乱程度”，因此一个系统的信息熵越高就越无序，信息熵越低就越有序，信息熵越高，使其有序所要消耗的信息量就越大。我们的目的就是将系统变得有序并找出确定的信息。
信息增益（Info-Gain）就是指划分前后信息熵的变化：
若某一列数据没有重复，ID3算法倾向于把每个数据自成一类，此时
对于这个为什么概率是1，可以这样理解，这里的概率P（x)=P(S|A),而当feature A的值没有重复的时候，每个值A，都对应于唯一的一条数据，那么S的值也就必然是一定的了。这样E(A)为最小，IGain(S,A)最大，程序会倾向于选择这种划分，这样划分效果极差。
为了解决这个问题，引入了信息增益率（Gain-ratio）的概念，计算方式如下：
，
这里Info为划分行为带来的信息，信息增益率如下计算：
这样就减轻了划分行为本身的影响。
（后续还需要什么知识，遇到了再补起来。）
文章知识点与官方知识档案匹配，可进一步学习相关知识
AIEarth是一个由众多领域内专家博主共同打造的学术平台，旨在建设一个拥抱智慧未来的学术殿堂！【平台地址：https://devpress.csdn.net/aiearth】 很高兴认识你！加入我们共同进步！
