习题3(第三章-分类技术)

1、习题3（第三章 分类技术）1. 在决策树归纳中，选项有：(a)将决策树转化为规则，然后对结果规则剪枝，或(b)对决策树剪枝，然后将剪枝后的树转化为规则。相对于(b)，(a)的优点是什么？解答：如果剪掉子树，我们可以用(b)将全部子树移除掉，但是用方法(a)的话，我们可以将子树的任何前提都移除掉。方法(a)约束更少。2. 在决策树归纳中，为什么树剪枝是有用的？使用分离的元组集评估剪枝有什么缺点？解答：决策树的建立可能过度拟合训练数据，这样就会产生过多分支，有些分支就是因为训练数据中的噪声或者离群点造成的。剪枝通过移除最不可能的分支(通过统计学方法)，来排除这些过度拟合的数据。这样得到的决策树就会

2、变得更加简单跟可靠，用它来对未知数据分类时也会变得更快、更精确。使用分离的元组集评估剪枝的缺点是，它可能不能代表那些构建原始决策树的训练元组。如果分离的元组集不能很好地代表，用它们来评估剪枝树的分类精确度将不是一个很好的指示器。而且，用分离的元组集来评估剪枝意味着将使用更少的元组来构建和测试树。3. 画出包含4个布尔属性A,B,C,D的奇偶函数的决策树。该树有可能被简化吗？ABCDClassTTTTTTTTFFTTFTFTTFFTTFTTFTFTFTTFFTTTFFFFFTTTFFTTFTFTFTTFTFFFFFTTTFFTFFFFFTFFFFFT解答：决策树如下，该树不可能被简化。4. X是

3、一个具有期望Np、方差Np(1-p)的二项随机变量，证明X/N同样具有二项分布且期望为p方差为p(1-p)/N。解答：令r=X/N，因为是二项分布，同样具有二项分布。期望，Er = EX/N = EX/N = (Np)/N = p;方差，E = E= E/ = Np(1-p)/ = p(1-p)/N5. 当一个数据对象同时属于多个类时，很难评估分类的准确率。评述在这种情况下，你将使用何种标准比较对相同数据建立的不同分类器。解答：一个数据对象可能同时属于多个类，然而，该数据对象可能属于某个类的概率更高。因此，一个评估标准就是选择正确预测出该数据对象通常属于哪个类的分类器。受此启发，一个分类预测如

4、果满足第一或第二最可能的类，那么就被认为是正确的。其他的评估标准包括速度、鲁棒性、可伸缩性和可解释性。通常，我们选择的分类器一般趋向于含有这样的特征：最小化计算开销，即使给予噪声数据或不完整数据也能准确预测，在大规模数据下仍然有效工作，提供简明易懂的结果。6. 证明准确率是灵敏性和特效性的函数，即证明式accuracy = sensitivity+specificity解答：accuracy = = + = + = sensitivity+specificity7. 支持向量机是一种具有高准确率的分类方法。然而，在使用大型数据元组集进行训练时，该方法的处理速度很慢。讨论如何克服这一困难，并未大

5、型数据集有效的SVM分类开发一种可伸缩的SVM算法。解答：我们可以使用micro-clustering技术(Classifying large data sets using SVM with hierarchical clusters by Yu, Yang, and Han, in Proc. 2003 ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD03), pages 306-315, Aug. 2003 YYH03)来克服这一困难。一种基于簇的SVM方法如下描述：(1) 使用CF树构建微簇；(2) 在微簇的中

6、心训练SVM；(3) 打散边界附近的条目；(4) 用其他的条目重复SVM训练；(5) 重复上面的步骤直到收敛。8. 通过对预测器变量变换，有些非线性回归模型可以转化成线性模型。指出如何将非线性回归方程y=转换成可以用最小二乘方求解的线性回归方程。解答：运用替换：,=,，可以获得线性模型：。9. 什么是提升（Boosting）？陈述它为何能够提决策树归纳的准确性？解答：提升(Boosting)是一种用来提高分类准确度的技术。现有一个包含s个元组的元组集S，训练集(t=1,2,T)，给中的元组赋予一定的权值。在中创建一个分类器。当创建好以后，更新中元组的权重，这样如果元组造成分类错误的话，在接下来的分类器创建时，容易被发现。这样就可以提高接下来的分类器的准确性。运用这种技术，就可以保证每一个分类器都比之前的分类器具有更高的准确度。最终的分类器组合每个个体分类器，其中每个分类器投票的权重是其准确率的函数。10. 下表汇总了具有三个属性A、B、C，以及两个分类标号+、-的数据集，请根据此建立一棵两层的决策树ABC实例数+-TTT50FTT020TFT200FFT05TTF00FTF250TFF00FFF025解答：ABCclass1