决策树的原理与构建围绕一个实例展开

1. 什么是决策树&＃xff1a;

    决策树是一种预测模型&＃xff0c;用来进行分类&＃xff0c;是一种有监督学习。树中每个节点表示某个对象&＃xff0c;而每个分叉路径则代表的某个可能的属性值&＃xff0c;而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值

2 决策树实例(围绕一个例子)

    问题1. 基于表1中给出的训练集&＃xff0c;给出分别使用极小熵和极大熵选择扩展属性所生成的两棵决策树。然后给出你对树的“大小”的理解&＃xff0c;并按你的理解比较两种方法生成的决策树大小。

  问题1. 基于表1中给出的训练集&＃xff0c;给出分别使用极小熵和极大熵选择扩展属性所生成的两棵决策树。然后给出你对树的“大小”的理解&＃xff0c;并按你的理解比较两种方法生成的决策树大小。

&＃xff08;1&＃xff09; 极小熵生成决策树,设表1给的数据集为D&＃xff0c;根据最大信息增益选择最优特征生成极小熵决策树,计算各特征A1、A2、A3、A4、A5对数据D的信息增益&＃xff0c;统计结果为

上表中的D1和D2&＃xff0c;D3分别表示在各个特征中取值为1、2和3的样本子集&＃xff0c;根据计算后统计在表格中的数据可得&＃xff1a;

H(D)&＃61;-8/15*log2(8/15)—7/15*log2(7/15)&＃61;0.9968

g(D,A1)&＃61;H(D)-[8/15*H(D1)&＃43;7/15*H(D2)]&＃61;0.2880

g(D,A2)&＃61;H(D)-[5/15*H(D1)&＃43;4/15*H(D2)&＃43;6/15*H(D3)]&＃61;0.1398

g(D,A3)&＃61;H(D)-[3/15*H(D1)&＃43;12/15*H(D2)]&＃61;0.0292

g(D,A4)&＃61;H(D)-[7/15*H(D1)&＃43;8/15*H(D2)]&＃61;0.2880

g(D,A5)&＃61;H(D)-[6/15*H(D1)&＃43;4/15*H(D2)&＃43;5/15*H(D3)]&＃61;0.4131

根据上面的计算结果&＃xff0c;特征A5的信息增益最大&＃xff0c;所以选择A5为根节点。根据A5的取值将样本分成3个结合&＃xff0c;S1&＃61;{2,3,6,8,12,13}&＃xff0c;S2&＃61;{1,5,7,14}&＃xff0c;S3&＃61;{4,9,10,11,15}其中集合S2已全部属于同一个类&＃xff0c;不需要再分&＃xff0c;已成为叶子节点。对于集合S1&＃xff0c;计算统计结果为&＃xff1a;

H(D)&＃61;0.6500 g(D,A1)&＃61; 0.0484 g(D,A2)&＃61; 0.1909 g(D,A3)&＃61; 0.0484 g(D,A4)&＃61;0.6500

     根据计算结果&＃xff0c;集合S1选择A4为根结点。根据A4的取值&＃xff0c;将S1集合划分为S11&＃61;{3,6,8,12,13}  S12&＃61;{2}&＃xff0c;集合S11和集合S12已成为叶节点。对于集合S3&＃xff0c;计算统计结果为&＃xff1a;

H(D)&＃61;0.9710 g(D,A1)&＃61;0.4200 g(D,A2)&＃61;0.5710  g(D,A3)&＃61;0 g(D,A4)&＃61;0.0200

根据计算结果&＃xff0c;所以集合S3选择A2作为根结点&＃xff0c;根据A2的取值将S3分成集合S31&＃61;{4,11}集合S32&＃61;{9}集合S33&＃61;{10,15} 集合S32和集合S32已为叶子节点。对于集合S33&＃xff0c;计算统计结果为

H(D)&＃61;1  g(D,A1)&＃61;1 g(D,A3)&＃61;0  g(D,A4)&＃61;0

     所以选择A1作为集合S33的根节点。根据A1的取值划分后的集合也都为叶子节点&＃xff0c;至此极小熵决策树就建立起来了&＃xff0c;如下图所示。

(2) 极大熵生成决策树,同上面的极小熵建立决策树类似&＃xff0c;设表1中数据集为D。根据信息增益最小选择特征建立决策树。计算各特征A1、A2、A3、A4、A5对数据D的信息增益&＃xff0c;统计结果为

  H(D)&＃61;0.9968g(D,A1)&＃61;0.2880 g(D,A2)&＃61;0.1398 g(D,A3)&＃61;0.0292 g(D,A4)&＃61;0.2880  g(D,A5)&＃61;0.4131

  根据上面计算结果&＃xff0c;选择最小增益A3作为根结果。根据A3的取值&＃xff0c;将集合划分S1&＃61;{5,8,14},S2&＃61;{1,2,3,4,6,7,9,10,11,12,13,15}.对于集合S1&＃xff0c;计算统计结果为

H(D)&＃61;0.9183 g(D,A1)&＃61;0.9183 g(D,A2)&＃61;0.9183 g(D,A4)&＃61;0.9183 g(D,A5)&＃61;0.9183

根据计算结果&＃xff0c;选择A1或A2或A4或A5都可以作为集合S1的根节点&＃xff0c;这里不妨选择A1作为根节点&＃xff0c;根据A1的取值将S1划分成S11&＃61;{5,14} &＃xff0c;S12&＃61;{8}&＃xff0c;此时S11和S12已经为叶节点不需要在划分。

对于集合S2,计算统计结果为

H(D)&＃61;0.9799 g(D,A1)&＃61;0.1957 g(D,A2)&＃61;0.0753 g(D,A4)&＃61;0.1957 g(D,A5)&＃61;0.2745

根据计算结果&＃xff0c;选择A2作为集合S2的根节点&＃xff0c;根据A2的取值将集合S2划分为S21&＃61;{2,4,6,11},S22&＃61;{7,9,12},S23&＃61;{1,3,10,13,15}&＃xff0c;对于集合S21&＃xff0c;计算统计结果为

H(D)&＃61;0.8113  g(D,A1)&＃61;0.1226  g(D,A4)&＃61;0.1226  g(D,A5)&＃61;0.3113

根据计算结果&＃xff0c;选择A1和A4作为S21的根节点都可以&＃xff0c;这里不妨选A1为S21的根节点。根据A1的取值将S21划分为S211&＃61;{11}&＃xff0c;S212&＃61;{2,4,6}&＃xff0c;其中S211已为叶节点。对于集合S212&＃xff0c;计算统计结果为

H(D)&＃61;0.9183  g(D,A4)&＃61;0.2516  g(D,A5)&＃61;0.2516

根据计算结果&＃xff0c;选择A4和A5作为S212的根节点都可以&＃xff0c;这里不妨选A4作为根节点。根据A4的取值将集合S212划分为S2121&＃61;{6}  S2122&＃61;{2,4}&＃xff1b;对于集合S2122选择A5作为根节点&＃xff0c;根据A5的取值将集合S2122划分为S21221&＃61;{2}  S21223&＃61;{4}&＃xff1b;此时集合S2121和集合S21221&＃xff0c;S21223都为叶节点&＃xff0c;对于集合S22&＃xff0c;计算统计结果为

H(D)&＃61;0.9183  g(D,A1)&＃61;0.9183  g(D,A4)&＃61;0.9183  g(D,A5)&＃61;0.9183

根据计算结果&＃xff0c;选择A1或A4或A5作为根节点都可以&＃xff0c;这里选择A1作为根节点。根据A1的取值将集合S22划分为S221&＃61;{12}&＃xff0c;S222&＃61;{7,9} 此时&＃xff0c;S221和S222已为叶节点。对于集合S23&＃xff0c;计算统计结果为

H(D)&＃61;0.9710  g(D,A1)&＃61;0.4200  g(D,A4)&＃61;0.3220  g(D,A5)&＃61;0.5710

根据计算结果&＃xff0c;选择A4作为根节点。根据A4的取值将S23划分为S231&＃61;{3,10,13,15},S232&＃61;{1}.对集合S231&＃xff0c;计算统计结果为

H(D)&＃61;0.8113  g(D,A1)&＃61;0.3113  g(D,A5)&＃61;0.3113

根据计算结果&＃xff0c;选择A1或A5作为S231的根节点都可以&＃xff0c;这里选择A1作为其根节点&＃xff0c;根据A1的取值将集合S231划分为S2311&＃61;{3,10},S2312&＃61;{13,15}。集合S2311选择A5作为根节点&＃xff0c;将集合S2311划分为S23111&＃61;{3} , S23113&＃61;{10}。至此极大熵决策树就可以建立起来了&＃xff0c;如下图所示

3.  拓展

     利用极小熵生成的决策树不一定是“最小决策树”。因为用极小熵生成的决策树可能存在过拟合&＃xff0c;对训练数据分类很好&＃xff0c;但对测试数据不一定好。一般需要对生成的决策树做剪枝处理&＃xff0c;减掉过于细分的叶节点。使其退回到父节点&＃xff0c;然后将父节点改为新的叶节点。