3.决策树ID3算法原理

1.决策树的作用

主要用于解决分类问题的一种算法

2.建立决策树的3中常用算法

1).ID3---》信息增益

2).c4.5--> 信息增益率

4).CART Gini系数

3.提出问题：

ID3算法中，选择根节点时为什么要使得信息增益最大的特征呢？

***************************后续内容均为更好的理解3中所提出的的问题展开****************************

4.ID3算法的理解

如何更好的理解决策树的建立原理呢：我想从下图的层次去理解决策树的原理

首先用倒序的方式来将问题细化如下图：

1).什么是自信息？

香农（shannon）给出的定义：信息是事务运动状态后存在方式不确定性的描述

对上述定义的理解：

引入图片（左图来源：西安电子科技大学老师信号论课程讲义图）

左图：

第一列：x1-x8表示的是发送端（信源）即将发送的信息的内容；

第二列：用3位的二进制数所唯一表征上述x1-x8

第三列：发送端随机发送任意一个信息内容的概率

通过右图我们可以发现，在信号传递过程中所体现出来的不确定性我们是可以通过概率的方式去量化表征的；

这样我们就可以预先假设不确定性和概率之前存在着一种量化的关系，可以做出如下的定义：在如下图所示的集合中，每一个事件x发生的不确定性可以定义为

下面我们分析一下信息的不确定性的特点：

a.确定事件的不确定性为0，即f(1) = 0

b.是单调减函数，即随着p(xi)的增大，f的值减小

c.可加性，即a发生的不确定性为i,b发生的不确定性为j 那么a和b同时发生的不确定性为i + j

通过上述的假设的不确定性与概率之间的量化关系，以及信号传递（或者说事件发生）过程中不确定性的特点，发现此种形式的函数满足如上假设以及特点

由此便有了信息的数学表达式为：

表达式1：事件xi的自信息-------------------------->

为什么称作自信息，暂且理解为只考虑自身的不确定性，后边的内容了解之后，大家就知道为甚这么叫了。

表达式2：事件xi的条件自信息------------------->

含义：事件yi发生的情况下，事件xi发生的不确定性的大小

表达式3：事件x的非平均互信息：------------->

含义：观测某一事件后所得到的关于信源事件不确定性的大小；

分步骤理解：

第一步：y事件发生前x事件发生的可能性为I(x)

第二步：y事件发生后x事件发生的可能性为I(x|y)

第三步：两者的差值即就是观测y事件发生后所得到的关于x事件不确定性的大小

通过上图，我们可以更直观得到自信息，条件自信息，非平均互信息三者之间的关系；

******************************************************************************************

2).什么是信息熵？

在理解什么是信息的过程中，我们引入的都是单一事件，表征的均为单一事件的不确定性，那如何表征x1-x8这个集合的不确定性呢？这便引入了信息熵，来度量集合的平均不确定性，表达式如下：

如何理解熵的与信息之间的关系：信息用来表征单一事件发生的不确定性，而熵是表征一个事件集合发射的平均不确定性，此处的平均实为加权平均

下面是几种熵的表达式：

表达式1：条件平均子信息（注意此时的x是一个集合）

表达式2：条件熵

表达式3：平均互信息

定义1：特定事件y属于Y w(y)>0出现时所给出的关于集合{X,p(x)}中格式件的平均互信息的表达式：

含义：观测某一事件后所得到的信源事件整体平均不确定性的大小

定义2:集合{XY,p(xy)}中随机变量I(x;y)的数学期望：

含义：观测集合整体后所得到的信源事件整体平均不确定性的大小

关系如下图：

我们发现:

下面给出上述关系的证明：(此时就是信息增益的关系时)

5.结论：

下面解决我们最初提出的问题即：ID3算法中，选择根节点时为什么要使得信息增益最大的特征呢？

首先明确我们在决策树中所提出的信息增益即就是平均互信息I(X;Y),含义如上文中蓝色字体所示，也可以理解为是Y事件集发生后，使得x发生的不确定性的减少程度

为什么要信息增益大呢？如下图所示当信息增益越大时，时件y发生后时间x的不确定性（即条件互信息）越来越小，这个正是我们所想要的；