取对数：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 页