1、模式识别与机器学习期末考查思考题1：简述模式识别与机器学习研究的共同问题和各自的研究侧重点。机器学习是研究让机器（计算机）从经验和数据获得知识或提高自身能力的科学。机器学习和模式识别是分别从计算机科学和工程的角度发展起来的。然而近年来，由于它们关心的很多共同问题（分类、聚类、特征选择、信息融合等），这两个领域的界限越来越模糊。机器学习和模式识别的理论和方法可用来解决很多机器感知和信息处理的问题，其中包括图像/视频分析、（文本、语音、印刷、手写）文档分析、信息检索和网络搜索等。近年来，机器学习和模式识别的研究吸引了越来越多的研究者，理论和方法的进步促进了工程应用中识别性能的明显提高。机器学习：要
2、使计算机具有知识一般有两种方法；一种是由知识工程师将有关的知识归纳、整理，并且表示为计算机可以接受、处理的方式输入计算机。另一种是使计算机本身有获得知识的能力，它可以学习人类已有的知识，并且在实践过程中不总结、完善，这种方式称为机器学习。机器学习的研究，主要在以下三个方面进行：一是研究人类学习的机理、人脑思维的过程；和机器学习的方法；以及建立针对具体任务的学习系统。 机器学习的研究是在信息科学、脑科学、神经心理学、逻辑学、模糊数学等多种学科基础上的。依赖于这些学科而共同发展。目前已经取得很大的进展，但还没有能完全解决问题。 模式识别：模式识别是研究如何使机器具有感知能力，主要研究视觉模式和听觉
3、模式的识别。如识别物体、地形、图像、字体（如签字）等。在日常生活各方面以及军事上都有广大的用途。近年来迅速发展起来应用模糊数学模式、人工神经网络模式的方法逐渐取代传统的用统计模式和结构模式的识别方法。 特别神经网络方法在模式识别中取得较大进展。 理解自然语言 计算机如能“听懂”人的语言（如汉语、英语等），便可以直接用口语操作计算机，这将给人们带来极大的便利。计算机理解自然语言的研究有以下三个目标：一是计算机能正确理解人类的自然语言输入的信息，并能正确答复（或响应）输入的信息。二是计算机对输入的信息能产生相应的摘要，而且复述输入的内容。三是计算机能把输入的自然语言翻译成要求的另一种语言，如将汉语
4、译成英语或将英语译成汉语等。目前，研究计算机进行文字或语言的自动翻译，人们作了大量的尝试，还没有找到最佳的方法，有待于更进一步深入探索。机器学习今后主要的研究方向如下：1)人类学习机制的研究；2)发展和完善现有学习方法，建立实用的学习系统，特别是开展多种学习方法协同工作的集成化系统的研究；通过多个现有的具体例子进行分析，归纳为更一般的概念.机器学习所关注的一个根本问题是如何提高学习系统的泛化能力，或者说是机器在数据中发现的模式怎样才能具有良好的推广能力.机器学习的研究主旨是使用计算机模拟人类的学习活动，它是研究计算机识别现有知识、获取新知识、不断改善性能和实现自身完善的方法。模式识别(Patt
5、ern Recognition)是指对表征事物或现象的各种形式的(数值的、文字的和逻辑关系的)信息进行处理和分析,以对事物或现象进行描述、辨认、分类和解释的过程,是信息科学和人工智能的重要组成部分。模式识别的研究的内容是指利用计算机对要分析的客观事物与标准模板的通过某种模式算法，对其进行分类，在错误概率最小的条件，使识别到的结果最接近于待识别的客观事实。先用一定数量的样本，根据它们之间的相似性进行分类器设计，而后用所设计的分类器对待识别的样本进行分类决策目前模式识别的主要研究的是提取目标的运动特征，或在此基础上进行对目标的整体的运动轨迹进行研究，2：列出在模式识别与机器学习中的常用算法及其优缺
6、点。1.k-近邻法近邻法是一种最简单的非参数模式识别方法中的模式匹配法,它主要依据样本间的多维空间距离来实现分类.令 Dn=x1,x2,xn,其中,每一个样本所属的类别均已知.对于测试样本点 x,分类是，在集合 Dn 中与每个模板进行一一比较，将距离最近的点标记为 x.那么,近邻法就是把点 x 分为 x所属类别.（1）优点：算法简单，易于理解和分析，分类效果好。（2）缺点：大样本的计算量大，存储所有样本需较大容量，样本小时误差难控制。2. 贝叶斯决策法贝叶斯决策法是基于概率统计的基本的判别函数分类法。（1）贝叶斯决策优点：算法简单，易于理解和分析，其基本概念被众多的先进决策算法运用，判断结果较
7、精确。（2）贝叶斯决策的主要的缺陷：在采用贝叶斯算法之前，要事先收集一定数量的符合实际情况的样本，这样才能较精确得出先验概率和条件概率。且在实际生活中，决策表是很难确定的，计算所需要的损失差数，往往是根据多位专家根据实际具体问题，共同其错误的决策造成的损失的严重程度来大概确立的。3. 逆向传播神经网络其算法在应用中的缺点主要如下：（1） 算法的稳定性与学效率成反比。（2） 还没找到某一明确的规则确定学效率的大小，尤其相对于非线性网络来说，学效率的选择更是一个难题。（3） 训练过程也可能陷入局部最小，可以通过变换初始值进行多次训练来决绝这个问题，但又增加了计算的负担。（4） 没有有效的方法可以确
8、定网络层数，太多或太少都会影响系统的性能。（5） 收敛于局部极小的较早收敛问题尚未解决主要的优点如下：（6） 每个神经元的运算功能十分简单。（7） 各神经元之间是并行结构互使得其具有高速处理能力。（8） 在神经网络中，知识与信息的存储表现为神经元之间分布式的物理联系，知识存储容量很大。（9） 网状结构似的整个系统的工作不会因为个别的神经元的损失而大大降低系统性能。（10） 它可以实现输入和输出数据之间的非线性映射.4. 遗传算法遗传算法的优点 遗传算法解决了传统优化算法容易误入局部最优解的缺点，不用单值迭代，而是从解集合进行搜索，利于全局择优。遗传算法需要的参数少，容易形成通用算法程序。 遗传
9、算法有极强的容错能力，遗传算法的初始串集本身就带有大量与最优解甚远的信息；该算法具有收敛性，通过选择、交叉、变异操作能迅速排除与最优解相差极大的串。 遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。 力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。 遗传算法的缺点遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；遗传算法还有大量的问题需要研究，目前也还有各种不足。选取的值范围大，变量多时，收敛速度也随之下降，甚至有时还无法给定取值范围时。可找到最优解附近，
10、但无法精确确定最优解位置。遗传算法的参数(n,Pm,Pc)选择还没准确的定数，还需要进一步研究其数学基础理论。5. 决策树算法优点：由于决策树具有易构造、结构简单、易于理解、分类精度高，且易于转化成SQI语句有效地存取数据库，易于算法实现等优点，决策树尤其适于数据挖掘。描述简单，分类速度快，特别适合大规模的数据处理缺点：在学习过程中不能有很多背景知识。是非递增学习算法；ID3 决策树是单变量决策树，复杂概念的表达困难；同性间的相互关系强调不够；抗噪性差。决策树的这种明确性可能带来误导.神经网络方法神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和高度容错等特性非常适合解决数据挖
11、掘的问题，因此近年来越来越受到人们的关注。典型的神经网络模型主要分 3 大类：以感知机、BP 反向传播模型、函数型网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以 Hopfield 的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网络模型；以 ART 模型、Koholon 模型为代表的，用于聚类的自组织映射方法。神经网络方法的缺点是“黑箱“性，人们难以理解网络的学习和决策过程。遗传算法遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它在数据挖掘中被加以应用。Sunil 已成功
12、地开发了一个基于遗传算法的数据挖掘工具，利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。遗传算法的应用还体现在与神经网络、粗集等技术的结合上。如利用遗传算法优化神经网络结构，在不增加错误率的前提下，删除多余的连接和隐层单元；用遗传算法和 BP 算法结合训练神经网络，然后从网络提取规则等。但遗传算法的算法较复杂，收敛于局部极小的较早收敛问题尚未解决。决策树方法决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。最有影响和最早的决策树方法是
13、由 Quinlan 提出的著名的基于信息熵的 ID3 算法。它的主要问题是：ID3 是非递增学习算法；ID3 决策树是单变量决策树，复杂概念的表达困难；同性间的相互关系强调不够；抗噪性差。针对上述问题，出现了许多较好的改进算法，如 Schlimmer 和 Fisher 设计了 ID4递增式学习算法;钟鸣，陈文伟等提出了 IBLE 算法等。 粗集方法粗集理论是一种研究不精确、不确定知识的数学工具。粗集方法有几个优点：不需要给出额外信息；简化输入信息的表达空间；算法简单，易于操作。粗集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统，为粗集的数据挖掘奠
14、定了坚实的基础。但粗集的数学基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是普遍存在的。因此连续属性的离散化是制约粗集理论实用化的难点。现在国际上已经研制出来了一些基于粗集的工具应用软件，如加拿大 Regina 大学开发的 KDD-R;美国Kansas 大学开发的 LERS 等。覆盖正例排斥反例方法它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去，相反则保留。按此思想循环所有正例种子，将得到正例的规则(选择子的合取式)。比较典型的算法有 Michalski 的 AQ11 方法、洪家荣改进的 A
15、Q15 方法以及他的AE5 方法。统计分析方法在数据库字段项之间存在两种关系：函数关系(能用函数公式表示的确定性关系)和相关关系(不能用函数公式表示，但仍是相关确定性关系)，对它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行常用统计(求大量数据中的最大值、最小值、总和、平均值等)、回归分析(用回归方程来表示变量间的数量关系)、相关分析(用相关系数来度量变量间的相关程度)、差异分析(从样本统计量的值得出差异来确定总体参数之间是否存在差异)等。模糊集方法即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。系统的复杂性越高，模糊性越强，一般模糊
16、集合理论是用隶属度来刻画模糊事物的亦此亦彼性的。李德毅等人在传统模糊理论和概率统计的基础上，提出了定性定量不确定性转换模型-云模型，并形成了云理论。3：请应用一种具体的模式识别与机器学习算法，简述解决问题的主要步骤。反向传播网络训练设计步骤及算法设置初始值（初始化训练的样本集、学习速率lr，赋给每个连接权值wij和节点数的阈值）。输入一个随机样本X和期望输出T。计算实际输出Y,计算公式见公式（5）（6）。iijjuwy（5）k-1ikj kk-1ij i jw uy其 中 表 示 前 一 层 的 第 个 节 点 到 层 的 第 个 节 点 的 权 值 ， 为 层 的 输 出 ， 为层 的 输
17、出 ， 可 层 的 输 入 。 1iiuye（6） iy为 最 后 层 的 输 出 。从输出层向第一隐层，逐层反向调整权值，调整公式见公式（7）（8）（9）。()()ijijiwnewold（7）为 学 习 速 率 ， 是 常 数 。21()2iEyt（8） ti表 示 期 望 输 出 的 值 。iiiEyt（9）转 ，重复执行，直到误差满足要求为止。遗传算法步骤：（1） 初始化群体；（2） 计算群体上每个个体的适应度值；（3） 按由个体适应度值 所决定的某个规则选择将 进入下一代的个体；（4） 按概率 Pc 进行交叉操作；（5） 按概率 Pc 进行突变操作；（6） 没有满足某种停止条件，则转
18、第(2)步，否则进入(7)。（7） 输出种群中适应度值最优的 染色体作为问题 的满意解或最优解。说明：算法停止条件最简单的有如下两种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度若干代基本没有改进时停止。4：在模式识别与机器学习中，常常需要用已知的数据集来训练所建立的模型。如果所建立的模型被说成是overfit，请解释这是什么意思？请陈述一些避免overfit的方法。是“过拟合“现象，过拟合主要指训练后的网络对训练样本（Train sample）具有极高的拟合精度，但是对工作样本（Work sample）的预测误差却非常大。过拟合着重于网络的推广能力（Gen
19、eralization Ability）问题，即网络学习能力与推广能力之间满足一般测不准关系.1. 测不准关系式中的过拟合参数 P 的确定将有助于避免出现“过拟合“现象. 2. 过拟合的解决方法是设置满足问题求解精度要求的上限，不要将目标误差设置太小。个人认为过拟合还与样本过于冗余有关，采用删除冗余样本信息的特征样本，不仅可以加快训练速度，还可以改善过拟合问题。3. 1.使用初期终止的方法来提高泛化能力。用训练集来训练网络，同时考察网络在校验集上的误差，一旦校验集上的误差的误差不再下降（或者累计 n 次不再下降），那么就停止训练，这样可以减轻网络过拟合的程度。4. 防止过拟合（overfitt
20、ing）的方法：（1）按照一定比例在 TRAIN 函数导入校验和测试的 VV 和 VT 参数；（2）采用 TRAINGDX 和 LEARNGDM 组合训练；（3）采用 TRAINBR 函数训练等等，发现没有一个的泛化（GENERALIZATION)效果能很理想的。5. 通过加入拟合函数的先验知识,加上正则项。或是加惩罚项。决策树对此历史数据可能非常准确,一旦应用到新的数据时准确性却急剧下降,我们称这种情况为训练过度.为了使得到的决策树所蕴含的规则具有普遍意义,必须防止训练过度,同时也减少了训练的时间.因此我们需要有一种方法能让我们在适当的时候停止树的生长.常用的方法是设定决策树的最大高度(层数
21、)来限制树的生长.还有一种方法是设定每个节点必须包含的最少记录数,当节点中记录的个数小于这个数值时就停止分割.5：在模式识别与机器学习的研究中，还不断有人提出新的算法。请问有那些方法可以用来判定他们的优劣？1. 正确性说一个算法是正确的，是指对于一切合法的输入数据，该算法经过有限时间（算法意义上的有限）的执行都能产生正确（或者说满足规格说明要求）的结果。2. 时间复杂性应该怎样计算一个算法的执行时间呢？首先想到的是，我们应选择一种度量，对解决同一个问题的诸多算法用该度量可有效地进行比较。：（1）它能告诉我们算法所用方法（包括数据结构）的时间效率；（2）它与算法描述语言（或程序设计语言）及设计风
22、格无关；（3）它与算法实现过程中的许多细节：诸如增加循环下标、计算数组下标、设置数据结构指针等簿记运算无关；（4）它应该是足够精确和具有一般性的。一个算法的时间复杂性是指该算法的基本运算次数。 3. 占用空间算法执行需要存储空间来存放算法本身包含的语句、常数、变量、输入数据和实现其运算所需的数据（如中间结果等），此外还需要一些工作空间用来对（以某种方式存储的）数据进行操作。4. 可读性可读性好的算法有助于设计者和他人阅读、理解、修改和重用。与此相反，晦涩难懂的算法不但容易隐藏较多的错误，而且增加了人们在阅读、理解、调试、修改和重用算法等方面的困难。5. 坚固性 当输入数据非法时，算法能适当地作
23、出合适的反应。时间复杂度算法分析同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。1、时间复杂度（1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。（2）时间复杂度在刚才提到的时间频
24、度中，n 称为问题的规模，当 n 不断变化时，时间频度 T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数，用 T(n)表示，若有某个辅助函数 f(n),使得当 n 趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作 T(n)=O(f(n),称O(f(n) 为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为 O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如 T(n)=n
25、2+3n+4 与 T(n)=4n2+2n+1 它们的频度不同，但时间复杂度相同，都为 O(n2)。按数量级递增排列，常见的时间复杂度有：常数阶 O(1),对数阶 O(log2n),线性阶 O(n),线性对数阶 O(nlog2n),平方阶 O(n2)，立方阶 O(n3),.，k 次方阶 O(nk),指数阶 O(2n)。随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。2、空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:S(n)=O(f(n)我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。6：如果你所遇到的数据集是纯数值型数据，你会采用那些模式识别与机器学习算法？若是包含大量非数值数据你会采用那些模式识别与机器学习算法？为什么？纯数值型数据：贝叶斯决策法，神经网络非纯数值型数据：决策树/1. k-近邻法，是一种最简单的模式识别方法中的模式匹配法,它主要依据样本间的多维空间距离来实现分类.
