ID3决策树

深藏阁楼爱情的钟 2022-06-08 08:28 241阅读 0赞

#### 知识准备：信息熵 ####

**熵**是无序性（或不确定性）的度量指标。加入事件A的全概率划分是（A1,A2,…An），每部分发生的概率是（p1,p2,…pn），那信息熵定义为：

entropy(p1,p2,…,pn)=−p1log2p1−p2log2p2−⋯−pnlog2pn

通常以2为底数，单位为比特（bit）,在数学证明上通常采用e为底数，单位为奈特（Nat）  
更详细的介绍请参考 [百度百科][Link 1]

#### 核心思想及举例说明  ####

ID3构造树的基本想法是**随着树深度的增加，节点的熵迅速地降低**。熵降低的速度越快越好，这样我们有望得到一棵高度最矮的决策树。在决策树各级结点上选择属性时，用**信息增益（information gain）**作为属性的选择标准，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。这是理想情况，当决策树的高度为属性（决策变量）的个数，叶子节点不纯，这意味着要根据概率来做出决策，即选择大概率分类作为分类结果。

**信息增益计算：**  
设S是n个数据样本的集合，共分m个不同类Ci(i=1,…,m)。设ni是类Ci中的样本数。则该样本分类所需的期望信息由下式给出：

I(n1,n2,…,nm)=−∑i=1mpilog2(pi)

其中,  pi=ni/n ，是样本属于类  Ci 的概率。  
设属性A具有v个不同值  a1,a2,…,av 。可以用属性A将S划分为v个子集  \{ S1,S2,…,Sv\} ，设  nij 是子集  Sj 中属于类  Ci 的样本数。由A划分子集的熵或信息期望由如下式给出：

E(A)=∑j=1v(n1j\+n2j\+⋯\+nmj)/n∗I(n1j,n2j,\+…,nmj)

其中，  
 I(n1j,n2j,\+…,nmj)=−∑mi=1pijlog2(pij)  
 pij=nij/(n1j\+n2j\+⋯\+nmj) ，是  Sj 中属于类  Ci 的概率。  
那么，在属性A上分支将获得的信息增益是：

Gain(A)=I(n1,n2,…,nm)−E(A)

**ID3算法的优点：**算法的理论清晰，方法简单，学习能力较强。  
**ID3算法的缺点：**只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。

**实例说明：**  
参考文章-[归纳决策树ID3（Java实现）][ID3_Java]

<table> 
 <thead> 
  <tr> 
   <th>outlook</th> 
   <th>temperature</th> 
   <th>humidity</th> 
   <th>windy</th> 
   <th>play</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>sunny</td> 
   <td>hot</td> 
   <td>high</td> 
   <td>FALSE</td> 
   <td>no</td> 
  </tr> 
  <tr> 
   <td>sunny</td> 
   <td>hot</td> 
   <td>high</td> 
   <td>TRUE</td> 
   <td>no</td> 
  </tr> 
  <tr> 
   <td>overcast</td> 
   <td>hot</td> 
   <td>high</td> 
   <td>FALSE</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>rainy</td> 
   <td>mild</td> 
   <td>high</td> 
   <td>FALSE</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>rainy</td> 
   <td>cool</td> 
   <td>normal</td> 
   <td>FALSE</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>rainy</td> 
   <td>cool</td> 
   <td>normal</td> 
   <td>TRUE</td> 
   <td>no</td> 
  </tr> 
  <tr> 
   <td>overcast</td> 
   <td>cool</td> 
   <td>normal</td> 
   <td>TRUE</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>sunny</td> 
   <td>mild</td> 
   <td>high</td> 
   <td>FALSE</td> 
   <td>no</td> 
  </tr> 
  <tr> 
   <td>sunny</td> 
   <td>cool</td> 
   <td>normal</td> 
   <td>FALSE</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>rainy</td> 
   <td>mild</td> 
   <td>normal</td> 
   <td>FALSE</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>sunny</td> 
   <td>mild</td> 
   <td>normal</td> 
   <td>TRUE</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>overcast</td> 
   <td>mild</td> 
   <td>high</td> 
   <td>TRUE</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>overcast</td> 
   <td>hot</td> 
   <td>normal</td> 
   <td>FALSE</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>rainy</td> 
   <td>mild</td> 
   <td>high</td> 
   <td>TRUE</td> 
   <td>no</td> 
  </tr> 
 </tbody> 
</table>

以上是14天的气象数据（指标包括outlook,temperature,humidity,windy），并已知这些天气是否打球（play），训练决策树以对新数据进行预测。  
在无天气信息时，根据历史数据，打球的概率是9/14，不打球的概率是5/14，此时的熵为：

−914log2914−514log2514=0.940

属性有4个：outlook,temperature,humidity,windy。首先确定根节点。  
outlook=sunny时，2/5的概率打球，3/5的概率不打球。entropy=0.971  
outlook=overcast时，entropy=0  
outlook=rainy时，entropy=0.971  
而根据历史统计数据，outlook取值为sunny、overcast、rainy的概率分别是5/14、4/14、5/14，所以当已知变量outlook的值时，信息熵为：

5/14×0.971\+4/14×0\+5/14×0.971=0.693

因此，信息增益gain(outlook)=0.940-0.693=0.247  
同理可以计算得到gain(temperature)=0.029, gain(humidity)=0.152, gain(windy)=0.048  
可以看出gain(outlook)最大（即outlook在第一步使系统的信息熵下降得最快），因此选择outlook作为根节点。

![这里写图片描述][SouthEast]

同理可以计算之后的节点，最终结果如下：  
![这里写图片描述][SouthEast 1]

#### 附录 ####

1.Java实现  
[ID3决策树（Java实现）][ID3_Java 1]

[Link 1]: https://baike.baidu.com/item/%E4%BF%A1%E6%81%AF%E7%86%B5/7302318?fr=aladdin
[ID3_Java]: http://www.cnblogs.com/zhangchaoyang/articles/2196631.html
[SouthEast]: /images/20220608/41f8957e6cfb4e17b138922fbddcdd46.png
[SouthEast 1]: /images/20220608/db49aa74b4964ed7bf27ce4740f10c22.png
[ID3_Java 1]: http://blog.csdn.net/xiaohukun/article/details/78041676