决策树算法

之前上机器学习课程时学过决策树的一些算法，今天简单复习一下：

• 决策树
  决策树的每个非叶节点都为一个属性，该节点的分枝为属性的不同取值，每个叶节点为一个标签。如下图所示：

  

  决策树最基本的算法为ID3算法。下面简单回顾ID3算法的基本思想。

• ID3算法
  ID3算法基于奥坎姆剃刀定律，每次选择最”好”的属性(可以使信息增益最大的属性)作为当前分类属性。用于判断属性”好坏”的标准主要是信息熵和信息增益。

  信息熵：对于一个有n个类别(标签)的问题，训练样本集合的信息熵定义为：

  

  其中pi为第i种分类(标签)所占的比例。很明显，信息熵不小于0，类别越纯净，信息熵越小，比如：两分类问题p(0)=0, p(1)=1，则信息熵为0；类别越混乱或者各类之间的比例越接近，则信息熵越大，比如：p(0)=1/2, p(1)=1/2，则信息熵为1。

  信息增益：
  信息增益为选择某个属性作为分类属性后导致信息熵的减小值。也即：

这里选择属性A作为分类属性，values(A)为属性A的所有取值，Sv为 取属性S取值为v时对应的集合，也即对每个取值v，都计算其对应的子集合的信息熵E(Sv)，然后用其占总集合的比例加权，求和即可得到将属性A作为分类属性后的信息熵，用原来的信息熵减去分类后的信息熵即为信息增益。很明显，信息增益越大越好。
因此，ID3算法每次选择剩下的属性中可以使得信息增益最大的那个属性作为分类属性。

ID3算法:
如下图所示：