决策树分类算法决策树分类算法通常分为决策树生成和决策树修剪两个步骤。决策树生成算法的输入参数是一组带有类别标记的样本,输出是构造一颗决策树,该树可以是一棵二叉树或多叉树。二叉树的内部结点(非叶子结点)一般表示为一个逻辑判断,构造决策树的方法是采用自上而下的递归方法。
首先需要知道如何求出熵和信息增益。
案例:
四个不同的影响因素,一个结果(是/否) )。
以下公式是训练样本集的熵
将分割线-----------------改为
考虑第一个因素: outlook
(如果outlook全部为overcast,则四个都为yes。)
(outlook为rainy时,5个中3个是,2个否)
(outlook为阳光蜜粉时,5个中3个为否,2个为是)
第一个因素outlook对应的信息增益如下。
与第二、三、四要素对应的信息增益如下。
样本概率分布越均衡,其信息量(熵)越大,样本集的拥挤度也越高。
信息增益越大,表示属性对分类提供的信息越多。
将分割线-----------------改为
ID3算法
案例:
熵
将分割线-----------------改为
第一个因素的熵
将分割线-----------------改为
第二个因素的熵
将分割线-----------------改为
第三个因素的熵:
将分割线-----------------改为
第四个因素的熵:
将分割线-----------------改为
最后,选择信息增益最大的作为根节点: outlook
然后,对outlook中的三个元素的计算重复上述计算。
entropy[outlook],entropy[outlook,overcast,entropy[outlook,阳光蜜粉]
其次,寻求信息增益:
在overcast的情况下,由于发现humidity的信息增益最大,所以选择了humidity作为叶节点。
在rain的情况下,可知windy的信息增益最大,选择了windy作为叶节点。
最后得到以下结果。
下一个案例更明确
将age的信息增益设为最大并作为根节点,可以得到以下图
然后,针对age分类下的3种情况,求出分别对应的信息增益:
30-40之间只有yes,所以不需要计算
30时,计算信息增益,发现student信息增益最大,以student为节点;
40时,在发现credit rating的信息增益最大时,将其作为节点。