决策树：ID3算法与实现
信道模型和信息的含义
信息论是关于信息的本质和传输规律的理论。
信道模型：信源（发送端）-> 信道 -> 信宿（接收端）
1. 通信过程是在随机干扰的环境汇中传递信息的过程
2. 信宿对于信源的先验不确定性：在通信前，信宿不能确切的了解信源的状态；
3. 信宿对于信源的后验不确定性：在通信后，由于存在干扰，信宿对于接收到的信息仍然具有不确定性
4. 后验不确定性总是要小于先验不确定性的。
信息：是消除不确定性的度量。
信息量的大小：由所消除的不确定性的大小来计量。
信息的定量描述
直观理解：
若消息发生的概率很大，受信者事先已经有所估计，则该消息的信息量就很小。
若消息发生的概率很小，受信者感觉到很突然，该消息所含有的信息量就很大。
所以信息量和概率联系在了一起，信息量可以表示为概率的函数。那么怎样的函数可以用来描述信息量呢？函数f(p)应该满足以下条件：
1. f(p)应该是概率p的严格单调递减函数，
2. 当p=1时，f(p)=0
3. 当p=0时，f(p)=∞
4. 两个独立事件的联合信息量应该等于它们信息量之和。
以下是f(p)=−log(p)的图像，满足以上的所有的要求。
自信息和熵的定义
若一个消息x出现的概率为p，那么这个消息所含有的信息量为
上式称为消息x的自信息，自信息有两种含义：
1. 当该消息发生之前，表示发生该消息的不确定性，
2. 当该消息发生之后，表示消息所含有的信息量。
信源含有的信息量是信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量称为熵，是指每个符号所含有的信息量（自信息）的统计平均。若X是一个离散随机变量，概率分布为p(x)=P(X=x)，x∈X，那么X的熵为
一个随机变量的熵越大，其不确定性就越大，（不管是先验熵，后验熵，还是条件熵都是这样的）正确的估计其值的可能性就越小，越是不确定的随机变量越是需要更大的信息量来确定其值。
结合信道模型，H(X)是信源发出前的平均不确定性，是先验熵。其中，p(xi)越接近，H(X)越大。p(xi)相差越大，H(X)越小。在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi|yj)，定义它的条件自信息量为条件概率对数的负值。如下：
在给定yj的条件下，（xi的条件自信息量为I（xi|yj）），此时关于X的不确定性定义为后验熵，（接收到一个输出信号后对于信源的不确定性）。如下：
在给定Y（即各个yj）的条件下，X集合的条件熵（接收到了所有的输出信号后对于信源的不确定性）为H(X|Y)
条件熵表示知道Y之后， 对X的不确定性。（知道了天气状态之后是否要出去活动的不确定性，其值越小，不确定性越小，说明天气情况带来的信息越大）。在通信后总能消除一定的关于信源端的不确定性，所以存在关系：H(U|V)<H(U)，那么定义互信息
例子
已知，垒球活动进行和取消的概率分别为914和514。
那么是否进行活动的熵的计算方法如下：（先验熵）
又，已知天气情况对活动进行的影响如下:
| 活动 | 活动进行 | 活动取消 |
|---|---|---|
| 晴天 | 2/5 | 3/5 |
| 阴天 | 1 | 0 |
| 雨天 | 3/5 | 2/5 |
计算已知户外的天气情况下活动的条件熵
(总的步骤是计算先验熵，在计算后验熵，在计算条件熵。现在先验熵已知)
计算后验墒：分别计算晴天对于活动的后验熵，阴天对于活动的后验熵，雨天对于活动的后验熵如下。
又已知天气的状况为p(晴天)=514，p(阴天)=414，p(雨天)=514
所以已知户外的天气的时候，活动的条件熵为：
平均互信息为
1. ID3算法
引入了信息论中的互信息（信息增益）作为选择判别因素的度量，即：以信息增益的下降速度作为选取分类属性的标准，所选的测试属性是从根节点到当前节点的路径上从没有被考虑过的具有最高的信息增益的属性。这就需要计算各个属性的信息增益的值，找出最大的作为判别的属性：
1. 计算先验熵，没有接收到其他的属性值时的平均不确定性，
2. 计算后验墒，在接收到输出符号yi时关于信源的不确定性，
3. 条件熵，对后验熵在输出符号集Y中求期望，接收到全部的付好后对信源的不确定性，
4. 互信息，先验熵和条件熵的差，
实例
是否适合打垒球的决策表如下
| 天气 | 温度 | 湿度 | 风速 | 活动 |
|---|---|---|---|---|
| 晴 | 炎热 | 高 | 弱 | 取消 |
| 晴 | 炎热 | 高 | 强 | 取消 |
| 阴 | 炎热 | 高 | 弱 | 进行 |
| 雨 | 适中 | 高 | 弱 | 进行 |
| 雨 | 寒冷 | 正常 | 弱 | 进行 |
| 雨 | 寒冷 | 正常 | 强 | 取消 |
| 阴 | 寒冷 | 正常 | 强 | 进行 |
| 晴 | 适中 | 高 | 弱 | 取消 |
| 晴 | 寒冷 | 正常 | 弱 | 进行 |
| 雨 | 适中 | 正常 | 弱 | 进行 |
| 晴 | 适中 | 正常 | 强 | 进行 |
| 阴 | 适中 | 高 | 强 | 进行 |
| 阴 | 炎热 | 正常 | 弱 | 进行 |
| 雨 | 适中 | 高 | 强 | 取消 |
1.计算先验熵：在没有接收到其他的任何的属性值时候，活动进行与否的熵根据下表进行计算。
2.分别将各个属性作为决策属性时的条件熵（先计算后验墒，在计算条件熵）
(1) 计算已知天气情况下活动是否进行的条件熵（已知天气情况下对于活动的不确定性）
先计算后验墒：
再计算条件熵：（知道了Y之后，对X的不确定性：知道了天气之后，对活动的不确定性，越小是越好的）
(2)计算已知温度情况时对活动的条件熵(不确定性)
(3)已知湿度情况下对于活动是否进行的条件熵（不确定性）
(4)已知风速情况下对于活动是否进行的条件熵（不确定性）
3.计算信息增益
所以选择天气作为第一个判别因素
在选择了天气作为第一个判别因素之后，我们很容易看出（计算的方法和上面提到的一样），针对上图的中间的三张子表来说，第一张子表在选择湿度作为划分数据的feature的时候，分类问题可以完全解决：湿度正常的情况下进行活动，湿度高的时候取消（在天气状态为晴的条件下）；第二个子表不需要划分，即，天气晴的情况下不管其他的因素是什么，活动都要进行；第三张子表当选择风速作为划分的feature时，分类问题也完全解决：风速弱的时候进行，风速强的时候取消（在天气状况为雨的条件下）。
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------