习题及参考答案 下载本文

取对数:d(p,q)??log(s(p,q))

第3章分类与回归

3.1 简述决策树分类的主要步骤。

答:决策树生成的过程如下:

(1)对数据源进行数据预处理, 得到训练集和测试集;

(2)对训练集进行训练;

(3)对初始决策树进行树剪枝;

(4)由所得到的决策树提取分类规则;

(5)使用测试数据集进行预测,评估决策树模型;

3.2 给定决策树,选项有:(1)将决策树转换成规则,然后对结果规则剪枝,或(2)对决策树剪

枝,然后将剪枝后的树转换成规则。相对于(2),(1)的优点是什么? 答:相对于(2),(1)的优点是:由于第一种方法已经将决策树转换成规则,通过规则,可以

很快速的评估决策树以及其子树紧凑程度,不能提高规则的估计准确率的任何条件都可以减掉,从而泛化规则;

3.3 计算决策树算法在最坏情况下的时间复杂度是重要的。给定数据集D,具有m个属性和

|D|个训练记录,证明决策树生长的计算时间最多为m?D?log(D)。

答:假设训练集拥有|D|实例以及m个属性。我们需要对树的尺寸做一个假设,假设树的深

度是由log |D| 决定,即O(log |D|)。考虑一个属性在树的所有节点上所要做的工作量。

当然不必在每一个节点上考虑所有的实例。但在树的每一层,必须考虑含有|D|个实例的整个数据集。由于树有log |D|个不同的层,处理一个属性需要的工作量是D?log(D)。在每个节点上所有属性都要被考虑,因此总的工作量为m?D?log(D)。

3.4 考虑表3-23所示二元分类问题的数据集。

表3-23 习题3.4数据集 A B 类标号 T T T T T F F F T T F T T F T F F F T F + + + - + - - - - - (1) 计算按照属性A和B划分时的信息增益。决策树归纳算法将会选择那个属性? (2) 计算按照属性A和B划分时Gini系数。决策树归纳算法将会选择那个属性?

第 9 页 共 27 页

答:

按照属性A和B划分时,数据集可分为如下两种情况: A=T A=F 0 3 B=T B=F 1 5 + 4 - 3 + 3 - 1 (1)

划分前样本集的信息熵为 E=-0.4log20.4-0.6log20.6=0.9710

按照属性A划分样本集分别得到的两个子集(A取值T和A取值F)的信息熵分别为:

EA?T??EA?F??4733log2log24733?3703log2log23703?0.9852

??0

?E?710EA?T?310EA?F?0.2813 按照属性A划分样本集得到的信息增益为:?

按照属性B划分样本集分别得到的两个子集(B取值T和B取值F)的信息熵分别为:

EB?T??EB?F??3416log2log23416?1456log2log21456?0.8113

?E?410EB?T?610EB?F?0.2565??0.6500 按照属性B划分样本集得到的信息增益为:?因此,决策树归纳算法将会选择属性A。 (2)

划分前的Gini值为G=1-0.42-0.62=0.48 按照属性A划分时Gini指标:

GA?T?4??3??1???????0.4898?7??7??3??0??1???????0

?3??3?2222

GA?FGini增益??G?710GA?T?310GA?F?0.1371

按照属性B划分时Gini指标:

GB?T?1??3??1???????0.3750?4??4??1??5??1???????0.2778?6??6?2222

GB?FGini增益??G?410GB?T?610GB?F?0.1633因此,决策树归纳算法将会选择属性B。

3.5 证明:将结点划分为更小的后续结点之后,结点熵不会增加。

证明:根据定义可知,熵值越大,类分布越均匀;熵值越小,类分布越不平衡。假设原有的

结点属于各个类的概率都相等,熵值为1,则分出来的后续结点在各个类上均匀分布,

此时熵值为1,即熵值不变。假设原有的结点属于个各类的概率不等,因而分出来的

第 10 页 共 27 页

后续结点不均匀地分布在各个类上,则此时的分类比原有的分类更不均匀,故熵值减少。

3.6 为什么朴素贝叶斯称为“朴素”?简述朴素贝叶斯分类的主要思想。 答:朴素贝叶斯之所以称之为朴素是因为,它假设属性之间是相互独立的。

朴素贝叶斯分类的主要思想为:利用贝叶斯定理,计算未知样本属于某个类标号值的概率,根据概率值的大小来决定未知样本的分类结果。

(通过某对象的先验概率,利用贝叶斯公式计算出其后验概率,即该对象属于某一类的概率,选择具有最大后验概率的类作为该对象所属的类。)

3.7 考虑表3-24数据集,请完成以下问题:

表3-24 习题3.7数据集

记录号 1 2 3 4 5 6 7 8 9 A 0 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 0 0 1 C 0 1 1 1 1 1 1 1 1 类 + - - - + + - - + |?)10 1 0 1 + (1) 估计条件概率P(A|?),P(B|?),P(C|?),P(A|?),P(B|?),P(C。

(2) 根据(1)中的条件概率,使用朴素贝叶斯方法预测测试样本(A=0,B=1,C=0)的类

标号;

(3) 使用Laplace估计方法,其中p=1/2,l=4,估计条件概率P(A|?),P(B|?),P(C|?),

P(A|?),P(B|?),P(C|?)。 (4) 同(2),使用(3)中的条件概率

(5) 比较估计概率的两种方法,哪一种更好,为什么? 答:(1) P(A|?)=3/5

P(B|?)=1/5

=2/5

P(B|?)=2/5

P(A|?)P(C|?)=1

(2) 假设P(A=0,B=1,C=0)=K

则K属于两个类的概率为:

P(+|A=0,B=1,C=0)=P(A=0,B=1,C=0)×P(+)/K

=P(A=0|+)P(B|+)P(C=0|+)×P(+)/K=0.4×0.2×0.2×0.5/K=0.008/K P(-|A=0,B=1,C=0)=P(A=0,B=1,C=0)×P(-)/K

=P(A=0|-)P(B|-)P(C=0|-)×P(-)/K=0.4×0.2×0×0.5/K=0/K 则得到,此样本的类标号是+。

第 11 页 共 27 页

(3) P(A|+)=(3+2)/(5+4)=5/9

P(A|-)=(2+2)/(5+4)=4/9 P(B|+)=(1+2)/(5+4)=1/3 P(B|-)=(2+2)/(5+4)=4/9 P(C|-)=(0+2)/(5+4)=2/9 (4) 假设P(A=0,B=1,C=0)=K

则K属于两个类的概率为:

P(+|A=0,B=1,C=0)=P(A=0,B=1,C=0)×P(+)/K =P(A=0|+)P(B|+)P(C=0|+)×P(+)/K =(4/9) ×(1/3) ×(1/3) ×0.5/K=0.0247/K P(-|A=0,B=1,C=0)=P(A=0,B=1,C=0)×P(-)/K =P(A=0|-)P(B|-)P(C=0|-)×P(-)/K =(5/9) ×(4/9) ×(2/9) ×0.5/K=0.0274/K 则得到,此样本的类标号是-。

(5) 当条件概率为0的时候,条件概率的预测用Laplace估计方法比较好,因为我们不想整个条件概率计算结果为0.

3.8 考虑表3-25中的一维数据集。

表3-25 习题3.8数据集

X 0.5 3.0 4.5 4.6 4.9 5.2 5.3 5.5 7.0 9.5 Y - - + + + - - + - - 根据1-最近邻、3-最近邻、5-最近邻、9-最近邻,对数据点x=5.0分类,使用多数表决。 答: 1-最近邻:+ 3-最近邻:-

5-最近邻:+ 9-最近邻:-

3.9 表3-26的数据集包含两个属性X与Y,两个类标号“+”和“-”。每个属性取三个不同

值策略:0,1或2。“+”类的概念是Y=1,“-”类的概念是X=0 and X=2。

表3-26 习题3.9数据集 X 0 1 2 1 2 0 1 2 Y 0 0 0 1 1 2 2 2 实例数 + 0 0 0 10 10 0 0 0 - 100 0 100 0 100 100 0 100 第 12 页 共 27 页