决策树分类算法

决策树分类算法通常分为两个步骤：决策树生成和决策树修剪。

决策树生成算法的输入参数是一组带有类别标记的样本，输出是构造一颗决策树，该树可以是一棵二叉树或多叉树。二叉树的内部结点（非叶子结点）一般表示为一个逻辑判断，构造决策树的方法是采用自上而下的递归方法。

首先要先知道熵和信息增益怎么求。
案例：
四种不同的影响因素，一个结果（yes/no）

下面式子为训练样本集的熵

分割线----------------------------------------------------------------------------

考虑第一种因素：outlook
（当outlook都是overcast时，4个都是yes）

（当outlook为rainy时，5个中有3个yes，2个no）

（当outlook为sunny时，5个中有3个no，2个yes）

第一种因素outlook对应的信息增益为：


第二、三、四种因素对应的信息增益为：

样本的概率分布越均衡，它的信息量（熵）就越大，样本集的混杂程度也越高。
信息增益越大，说明属性对分类提供的信息越多。

分割线----------------------------------------------------------------------------

ID3算法
案例：

熵

分割线----------------------------------------------------------------------------

第一种因素的熵

分割线----------------------------------------------------------------------------

第二种因素的熵

分割线----------------------------------------------------------------------------

第三种因素的熵：

分割线----------------------------------------------------------------------------

第四种因素的熵：

分割线----------------------------------------------------------------------------

最后选择信息增益最大的作为根节点：outlook
接着对outlook下的三种因素计算重复以上的运算：
Entropy(outlook),Entropy(outlook,overcast),Entropy(outlook,rainy),Entropy(outlook,sunny)
接着求信息增益：
发现在overcast时，humidity的信息增益最大，所以选择humidity作为叶节点。
发现在rain时，windy的信息增益最大，选择windy作为叶节点。
最后得到下面的结果。

下面的这个案例更加清楚：

求得age的信息增益最大，然后作为根节点，得到下图

然后对age分类下的三种情况，分别求对应的信息增益：
因为在30-40之间只有yes，所以不需要计算
在<30情况下，计算信息增益，发现student的信息增益最大，则将student设为节点；
在>40情况下，发现credit rating的信息增益最大，则设它为节点。