决策树：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)的图像，知足以上的全部的要求。api

自信息和熵的定义

若一个消息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) ，那么定义互信息 表示在接收到 Y 后得到的关于 X 的信息量。

---

例子

已知，垒球活动进行和取消的几率分别为914和514。 
那么是否进行活动的熵的计算方法以下：（先验熵） 
测试

又，已知天气状况对活动进行的影响以下:

活动	活动进行	活动取消
晴天	2/5	3/5
阴天	1	0
雨天	3/5	2/5

计算已知户外的天气状况下活动的条件熵 
(总的步骤是计算先验熵，在计算后验熵，在计算条件熵。如今先验熵已知) 
计算后验墒：分别计算晴天对于活动的后验熵，阴天对于活动的后验熵，雨天对于活动的后验熵以下。 
ui

又已知天气的情况为 p(晴天)=514，p(阴天)=414，p(雨天)=514  
因此已知户外的天气的时候，活动的 条件熵 为： 

平均互信息为

---

1. ID3算法

引入了信息论中的互信息（信息增益）做为选择判别因素的度量，即：以信息增益的降低速度做为选取分类属性的标准，所选的测试属性是从根节点到当前节点的路径上从没有被考虑过的具备最高的信息增益的属性。这就须要计算各个属性的信息增益的值，找出最大的做为判别的属性： 
1. 计算先验熵，没有接收到其余的属性值时的平均不肯定性， 
2. 计算后验墒，在接收到输出符号yi时关于信源的不肯定性， 
3. 条件熵，对后验熵在输出符号集Y中求指望，接收到所有的付好后对信源的不肯定性， 
4. 互信息，先验熵和条件熵的差，atom

实例

是否适合打垒球的决策表以下spa

天气	温度	湿度	风速	活动
晴	炎热	高	弱	取消
晴	炎热	高	强	取消
阴	炎热	高	弱	进行
雨	适中	高	弱	进行
雨	寒冷	正常	弱	进行
雨	寒冷	正常	强	取消
阴	寒冷	正常	强	进行
晴	适中	高	弱	取消
晴	寒冷	正常	弱	进行
雨	适中	正常	弱	进行
晴	适中	正常	强	进行
阴	适中	高	强	进行
阴	炎热	正常	弱	进行
雨	适中	高	强	取消

1.计算先验熵：在没有接收到其余的任何的属性值时候，活动进行与否的熵根据下表进行计算。 
.net

2.分别将各个属性做为决策属性时的条件熵（先计算后验墒，在计算条件熵）code

(1) 计算已知天气状况下活动是否进行的条件熵（已知天气状况下对于活动的不肯定性） 
 
先计算后验墒： 
blog

再计算 条件熵 ：（知道了Y以后，对X的不肯定性：知道了天气以后，对活动的不肯定性，越小是越好的） 

(2)计算已知 温度状况 时对活动的条件熵(不肯定性) 
 

(3)已知 湿度状况 下对于活动是否进行的条件熵（不肯定性） 
 

(4)已知 风速状况 下对于活动是否进行的条件熵（不肯定性） 
 

3.计算信息增益 




因此选择天气做为第一个判别因素  

在选择了天气做为第一个判别因素以后，咱们很容易看出（计算的方法和上面提到的同样），针对上图的中间的三张子表来讲，第一张子表在选择湿度做为划分数据的feature的时候，分类问题能够彻底解决：湿度正常的状况下进行活动，湿度高的时候取消（在天气状态为晴的条件下）；第二个子表不须要划分，即，天气晴的状况下无论其余的因素是什么，活动都要进行；第三张子表当选择风速做为划分的feature时，分类问题也彻底解决：风速弱的时候进行，风速强的时候取消（在天气情况为雨的条件下）。

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------