清华大学模式识别往年考题2.doc

模式识别 张长水 2007.7.1 14:00-16:00 1 （15分）两类分类问题，P(w1)=1/4，P(w2)=3/4。样本有两个特征，分别是x和y。两类?的概率密度函数：w1，在0=x=3、0=y=3中均匀分布，其余为0；w2，在2=x=5、1=y=7中均匀分布，其余为0。请设计做小错误率贝叶斯分类器，并计算误分率。 2 （20分）支持向量机通过二次最优化得到支持向量。现在有一个两类分类问题，共有N个样本，样本有d维特征空间，样本集合是线性可分的。试使用遗传算法求解支持向量，说明算法步骤和使用的遗传算子。使用遗传算法求解支持向量有什么优缺点？ 3 （20分）两类分类问题，有3个特征x,y,z，共有N个样本。通过经验知道将3个特征进行加权相加得到的特征将具有更好的分类性能，但是不知道如何得到各个特征的权重。试回答?如何得到各个特征的权重。给出必要的计算和推导过程。 4 （15分）使用多级聚类算法对下面的样本进行聚类，使用最近距离量度。给出计算过程，多级聚类树。问应该分成几类，为什么？举例说明使用最近距离量度聚类和使用最远距离量度聚类各自的优缺点。(1,0) (2,0) (0,2) (1,3) (0,5)5 （20分）距离是模式识别中的重要概念，试说明贝叶斯分类器、近邻法、Fisher投影法、C均值算法是否受不同距离量度选择的影响。如果不是，说明原因；如果是，举例说明受什么影响。 6 （10分）一个袋子中装有红、绿、蓝三种颜色的球，采用有放回的取球方法，取出N个球，其中有n1个红色球、n2个绿色球和n3个蓝色球的概率为p(n1,n2,n3)=(N!/(n1!n2!n3!)*p1n1*p2n2*p3n3其中n1+n2+n3=N，p1+p2+p3=1已知概率模型如下：p1=1/4 p2=1/4+p/4 p3=1/2-p/4如果一个人是红绿色盲，分不清红色球和绿色球，那么他只能知道他取了m1=n1+n2个红/绿球，和m2=n3个蓝色球。试通过这些数据估计概率模型中的p，并估计红色球和绿色球的数?。 - 不出意外的话应该是在清华最后一门考试了，复习的时候又极其痛苦，500+张ppt，很多公式要理解要背，所以得纪念一下，粗略回忆一下今天考的内容，给后面的同学留点参考吧 （这里研究生的考试题实在有点稀少） 模式识别 林行刚（电子系） 期末 闭卷 2008.6.27 一、判断对错 40*0.5 = 20分1m 0;37m考的题很细，涉及了各个方面，比如 m 1m 0;37m简单模式匹配、K-L变换（2题）、最小欧氏距离、权向量定义、近邻函数定义、 m 单个神经元分类是否是线性的、子空间（1题）、 “最小马氏距离分类器的错误概率一定不会比最小欧氏距离分类器的错误率大”。 二、对现有算法的理解 5*5=251、s个类，可以用s(s-1)/2个线性分类器分开，称为这个样本集成对线性可分。举例二、对现有算法的理解 5*5=251、s个类，可以用s(s-1)/2个线性分类器分开，称为这个样本集成对线性可分。举例 说明，成对线性可分不一定线性可分。 2、定义相似度为20-min (dXi,Xj)(Xi属于类wi,Xj属于类wj)，其中dXi,Xj表示 两个样本之间的欧氏距离，给了一组样本10个数据， -2.2,-2.0,-0.3,0.1,0.2,0.4,1.6,1.7,1.9,2.0（好像是这样），请画出层次 聚类算法的分类树，并说明最终聚为几个类比较好。 3、KMP算法，对于在字符串text1,2,.,n中查找字串pat1,2,.,m，当匹配到 pat中的pj发现不匹配时， 1）应该怎样确定下一个pat开始查找的位置nextj； 2）给出4个pat形式，写出对于所有j值写出nextj的值。四个形式大概是abcd,abca aaad,abcadbab（最后一个不确定） 3）什么情况是最坏情况，最坏要进行多少次比较 4、给定字符串abbc和abcbc，给出求解编辑距离的步骤图并给节点标上最小费用，求编 辑距离，画出最小路径，简要说明寻找最小费用路径的步骤。4、给定字符串abbc和abcbc，给出求解编辑距离的步骤图并给节点标上最小费用，求编 辑距离，画出最小路径，简要说明寻找最小费用路径的步骤。 5、（似作业题）设有符合正态分布的两类样本，p(w1)=p(w2)=0.5， w1=(3,4),(3,8),(2,6),(4,6),w2=(3,0),(3,-4),(1,-2),(5,-2)，求： 1)识别函数 2）识别界面，画出示意图 3）如果p(w1)=0.1,p(w2)=0.9，请问识别界面会有什么变化？ 4）如果要使识别界面成为双曲线，那么样本应该做怎样的调整？ 三、实验设计 15 各省都有简称，比如京、津、鄂、鲁、豫等，共达三十余个类，需要用楷、行等6 种字体进行印刷，请设计分类器识别省市简称。印刷中，字体不同，质量不同，有 粗细差别甚至缺失。 1）为了设计分类器，你将怎样搜集和准备数据 2）你将怎样对对象进行描述，即怎样进行特征抽取和选择 3）你怎样设计分类器和确定参数 4）怎样测试数据和评估精度 三、实验设计 15 各省都有简称，比如京、津、鄂、鲁、豫等，共达三十余个类，需要用楷、行等6 种字体进行印刷，请设计分类器识别省市简称。印刷中，字体不同，质量不同，有 粗细差别甚至缺失。 1）为了设计分类器，你将怎样搜集和准备数据 2）你将怎样对对象进行描述，即怎样进行特征抽取和选择 3）你怎样设计分类器和确定参数 4）怎样测试数据和评估精度 结语：时间很紧，得快，另外概念的东西考的很细，需要确实的理解。期末占60%，平?小作业20%，大实验20%，号称成绩是以82为期望的正态分布。 总的来说林行刚老师还是比自动化的张长水的模式识别正常一点，如果要上模式识别?话建议选他的。-07模式识别 林行刚 2007.6bow to: zhouguangyipfree,在此基础上修改完善的:)另外，这门课的给分：平均分80，正态分布，90以上和70以下的各占10%. 一,判断对错题(40*0.5=20)考得很细课件要仔细看，不过感觉有好多都是老师上课时讲解的,课件上并没写,可惜没仔细听课? 二.问答计算(4*6=24)1.一个二次判决函数d(x)=7+3x+15x2 (1)将它化成一个广义齐次线性判决函数； (2)简述对于一般的高次判决函数怎样化成广义齐次线性判决函数。2.s个类，可以用s(s-1)/2个线性分类器分开，称为这s个类成对线性可分。 举例说明，成对线性可分不一定线性可分。3.模糊数学问题： 依据经验定义“凌晨”“白天”“夜晚”在X属于0，24时间内的模糊隶属度函数。 以此例说明一下隶属度函数和概率的区别。4.关于Bayes分类器 (1)为什么Bayes分类器得到的是最小错误概率分类。4.关于Bayes分类器 (1)为什么Bayes分类器得到的是最小错误概率分类。 (2)写出A.P(w1)=P(w2)；N.P(X|w1)=P(X|w2)两种情况下的Bayes分类函数。 (3)什么情况下Bayes分类器与最小欧氏距离分类器错误概率相同。 (4)什么情况下最小马氏举例分类器比最小欧氏距离分类器错误概率小。5.SVM,给了两类六个点：w1:(0,0)(1,0)(0,1)；w2:(1,1)(2,0)(2,2) (1)画图给出最优界面的权向量 (2)标出支持向量6.有穷状态机问题 (1)给出有穷状态机的5个元素 (2)说明为什么有穷状态机能解决“无穷个对象”的问题。 (3)给3个字符串的例子，并画出相应的有穷状态机 (4)给2个不能用有穷状态机解决的