3模式识别与机器学习期末考查

模式识别与机器学习期末考查试卷研究生姓名：王晓薇学号：20110777入学年份：2011导师姓名：吴庆祥试题1（15%）：列出你所知道的模式识别与机器学习中的常用算法,并给出其优缺点。答：1.k-近邻法近邻法是一种最简单的非参数模式识别方法中的模式匹配法,它主要依据样本间的多维空间距离来实现分类.其基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki,i＝1，…，c。定义判别函数为：gi(x)=ki,i=1,2,…,c。决策规则为：cixgjii,,1;)(maxarg优点：算法简单，易于理解和分析，分类效果好,在训练样本趋于无穷大时接近最优。缺点：可以明显看出它需要的计算量大，存储容量大；没有考虑到决策的风险；对于近邻法错误率的分析都是建立在样本数趋向于无穷大的假定上的，而这在实际应用时是很难实现的。而对有限样本集的情况，又缺乏理论上的分析。2.贝叶斯决策理论贝叶斯决策理论是主观贝叶斯派归纳理论的重要组成部分，是基于概率统计的基本的判别函数分类理论。贝叶斯决策就是在不完全情报下，对部分未知的状态用主观概率估计，然后用贝叶斯公式对发生概率进行修正，最后再利用期望值和修正概率做出最优决策。贝叶斯决策理论方法是统计模型决策中的一个基本方法，其基本思想是：1.已知类条件概率密度参数表达式和先验概率2.利用贝叶斯公式转换成后验概率3.根据后验概率大小进行决策分类设D1，D2，……，Dn为样本空间S的一个划分，如果以P(Di)表示事件Di发生的概率，且P(Di)0(i=1，2，…，n)。对于任一事件x，P(x)0，得到贝叶斯公式：niiiiiiDPDxPDPDxPxDP1)()|()()|()|(优点：（1）算法简单，易于理解和分析，其基本概念被众多的先进决策算法运用，判断结果较精确；（2）能对信息的价值或是否需要采集新的信息做出科学的判断；（3）它能对调查结果的可能性加以数量化的评价，而不是像一般的决策方法那样，对调查结果或者是完全相信，或者是完全不相信。（4）如果说任何调查结果都不可能完全准确，先验知识或主观概率也不是完全可以相信的，那么贝叶斯决策则巧妙地将这两种信息有机地结合起来了；（5）它可以在决策过程中根据具体情况下不断地使用，使决策逐步完善和更加科学。缺点：（1）它需要的数据多，分析计算比较复杂，特别在解决复杂问题时，这个矛盾就更为突出。（2）有些数据必须使用主观概率，有些人不太相信，这也妨碍了贝叶斯决策方法的推广使用。3.逆向传播神经网络逆向传播神经网络的优点：（1）每个神经元的运算功能十分简单。（2）各神经元之间是并行结构互使得其具有高速处理能力。（3）在神经网络中，知识与信息的存储表现为神经元之间分布式的物理联系，知识存储容量很大。（4）网状结构似的整个系统的工作不会因为个别的神经元的损失而大大降低系统性能。（5）它可以实现输入和输出数据之间的非线性映射.逆向传播神经网络的缺点：（1）算法的稳定性与学效率成反比。（2）还没找到某一明确的规则确定学效率的大小，尤其相对于非线性网络来说，学效率的选择更是一个难题。（3）训练过程也可能陷入局部最小，可以通过变换初始值进行多次训练来决绝这个问题，但又增加了计算的负担。（4）没有有效的方法可以确定网络层数，太多或太少都会影响系统的性能。4.遗传算法遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它在数据挖掘中被加以应用。遗传算法的优点：（1）遗传算法解决了传统优化算法容易误入局部最优解的缺点，不用单值迭代，而是从解集合进行搜索，利于全局择优。（2）遗传算法需要的参数少，容易形成通用算法程序。（3）遗传算法有极强的容错能力，遗传算法的初始串集本身就带有大量与最优解甚远的信息；该算法具有收敛性，通过选择、交叉、变异操作能迅速排除与最优解相差极大的串。（4）遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。（5）力称为隐含并行性(ImplicitParallelism)。它说明遗传算法其内在具有并行处理的特质。遗传算法的缺点：（1）选取的值范围大，变量多时，收敛速度也随之下降，甚至有时还无法给定取值范围。（2）可找到最优解附近，但无法精确确定最优解位置。（3）遗传算法的参数(n,Pm,Pc)选择还没准确的定数，还需要进一步研究其数学基础理论。5.决策树算法决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中找到一些有价值的，潜在的信息。优点：由于决策树具有易构造、结构简单、易于理解、分类精度高，且易于转化成SQL语句有效地存取数据库，易于算法实现等优点，决策树尤其适于数据挖掘。描述简单，分类速度快，特别适合大规模的数据处理。缺点：在学习过程中不能有很多背景知识。是非递增学习算法；ID3决策树是单变量决策树，复杂概念的表达困难；同性间的相互关系强调不够；抗噪性差。决策树的这种明确性可能带来误导。试题2（15%）：你认为可从几个方面来评价模式识别与机器学习算法？什么叫十组交叉验证法？它可被用来评价模式识别与机器学习算法的什么属性？答：评价模式识别与机器学习算法1.正确性说一个算法是正确的，是指对于一切合法的输入数据，该算法经过有限时间（算法意义上的有限）的执行都能产生正确（或者说满足规格说明要求）的结果。2.时间复杂性应该怎样计算一个算法的执行时间呢？首先想到的是，我们应选择一种度量，对解决同一个问题的诸多算法用该度量可有效地进行比较。：（1）它能告诉我们算法所用方法（包括数据结构）的时间效率；（2）它与算法描述语言（或程序设计语言）及设计风格无关；（3）它与算法实现过程中的许多细节：诸如增加循环下标、计算数组下标、设置数据结构指针等簿记运算无关；（4）它应该是足够精确和具有一般性的。一个算法的时间复杂性是指该算法的基本运算次数。3.空间复杂度空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。4.占用空间算法执行需要存储空间来存放算法本身包含的语句、常数、变量、输入数据和实现其运算所需的数据（如中间结果等），此外还需要一些工作空间用来对（以某种方式存储的）数据进行操作。5.可读性可读性好的算法有助于设计者和他人阅读、理解、修改和重用。与此相反，晦涩难懂的算法不但容易隐藏较多的错误，而且增加了人们在阅读、理解、调试、修改和重用算法等方面的困难。6.坚固性当输入数据非法时，算法能适当地做出合适的反应。可用多组数据交叉等方法，用标准数据集对上述指标进行实验结果比较。十组交叉验证法就是十折交叉验证。英文名叫做10-foldcross-validation，用来测试算法准确性。是常用的测试方法。将数据集分成十分，轮流将其中9份作为训练数据，1份作为测试数据，进行试验。每次试验都会得出相应的正确率（或差错率）。10次的结果的正确率（或差错率）的平均值作为对算法精度的估计，一般还需要进行多次10折交叉验证（例如10次10折交叉验证），再求其均值，作为对算法准确性的估计。之所以选择将数据集分为10份，是因为通过利用大量数据集、使用不同学习技术进行的大量试验，表明10折是获得最好误差估计的恰当选择，而且也有一些理论根据可以证明这一点。但这并非最终诊断，争议仍然存在。而且似乎5折或者20折与10折所得出的结果也相差无几。它可被用来评价模式识别与机器学习算法的算法准确性属性试题3（15%）：简述在模式识别与机器学习中解决问题的主要步骤。指出那些步骤涉及到学习？是如何进行学习？答：一、在模式识别与机器学习中解决问题的主要步骤：(1)数据采集数据采集是指利用各种传感器把被研究对象的各种信息转换为计算机可以接受的数值或符号(串)集合。这一步的关键是传感器的选取。(2)数据预处理为了从这些数字或符号(串)中抽取出对模式识别与机器学习有效的信息，必须进行数据预处理，包括数字滤波和特征提取。数据预处理是一个非常重要的步骤，它影响着整个模式识别与机器学习的成败。(3)选择或设计模型对同一个问题或许有许多不同的模型可以描述，不同的模型会导致识别和学习结果的不同，因此需要利用已有的经验和知识来选择或设计适当的模型。在确定了所建立的模型后，就可以估计模型的参数，需要注意的时，应该使得模型对未知数据有良好的适应性。(4)训练所建立的模型用前面所得的数据分成两组，一组作为训练数据，一组作为测试数据。设定目标误差，用训练数据对所建立的模型进行训练，达到目标误差，就停止训练，这样就确定了所建立模型的参数。(5)测试、验证模型测试模型的目的是为了确定所建立模型是否满足实际应用的要求。测试数据应该和训练用的样本数据不一致，否则，测试所得的结果永远都是满意的。用测试数据对所建立模型进行测试，观察测试结果是否与实际情况是相符合。若与实际情况相符合，所建立模型就可对未知数据做预测，从而得到进一步的验证。二、在这些步骤中，步骤(4)训练所建立的模型，涉及到学习。三特征选取（也称作属性选择）是简化数据表达形式，是在模式识别中根据一定的原则，选取反映被识别模式本质的那些特征的方法或过程。模式识别和机器学习方法首先要解决的一个问题就是特征选择。在数据的前处理中，特征选择是一个非常重要的步骤，特征选择不合理，会影响识别和学习效果。通过特征选择和提取，我们才可得到所采集数据中最有效的信息，最有效的特征，选择出有利于分类或聚类建立模型的变量，从而实现特征空间维数的压缩，以降低后续处理过程的难度，才能基于这些特征对所建立模型进行训练和测试。同时特征选取也是降低存储要求，提高分类精度和效率的重要途径。试题4（15%）：在使用模式识别与机器学习算法时，常常要进行数据的前处理，请指出在数据的前处理中，应完成些什么工作？什么叫特征选择？特征选择起什么作用？答：1数据的前处理中，应完成数字滤波和特征提取等工作。数字滤波是为了消除输入数据或信息中的噪声，排除不相干的信号，只留下与被研究对象的性质和采用的识别方法密切相关的特征（如表征物体的形状、周长、面积等等）。特征提取是指从滤波数据中衍生出有用的信息，从许多特征中寻找出最有效的特征，以降低后续处理过程的难度。比如，图像识别时，提取的特征有灰度变化、纹理、形状等。我们对滤波后的这些特征进行必要的计算（比如进行快速傅里叶变换以得到信号功率谱）后，通过特征选择和提取或基元选择形成模式识别与机器学习的特征空间。2特征提取是指从滤波数据中衍生出有用的信息，从许多特征中寻找出最有效的特征，以降低后续处理过程的难度。3在数据的前处理中，特征选择是一个非常重要的步骤，是模式识别和机器学习的关键，特征选择不合理，会影响识别和学习效果。通过特征选择和提取，我们才可得到所采集数据中最有效的信息，最有效的特征，以降低后续处理过程的难度，才能基于这些特征对所建立模型进行训练和测试。（1）简化计算特征空间的维数越高，需占用的计算资源越多，设计和计算也就月复杂（2）简化特征空间结构由于特征提取和选择是去除类间差别小的特征，保留类间差别大的特征，因此，在特征空间中，每类所占据的子空间结构可分离性更强，从而也简化了类间分界面形状的复杂度。试题5（15%）：根据下列的数据集，请利用一种机器学习的算法，设计一个程序，当输入三个数值作为Age,Tall，Weight时，马上就能给出答案，这应该是何种动物？（Sheep,Ox，或Pig）。例如（0,30,8）=Sheep。AgeTallWeightAnimal0308sheep13510sheep23716sheep34020sheep44525sheep55035sheep65540sheep76045sheep86550sheep96550sheep106550sheep04515ox