模式识别基础复习资料

模式识别基础复习资料教师：张学工2009秋季[e-mail]清华大学自动化系2009秋季2009秋季[模式识别基础]2卷一、模式识别机经|清华大学自动化系Contents卷一、模式识别机经..................................................................................3卷二、2008~2009秋_模式识别_张学工_期末B.......................................5卷三、2007~2008秋_模式识别_张学工_期末B.......................................7卷四、2007~2008秋_模式识别_张学工_期末A.....................................10卷五、2006~2007秋_模式识别_张学工_期末B.....................................11卷六、2005~2006秋_模式识别_张学工_期末.........................................12卷七、2004~2005秋_模式识别_张学工_期末.........................................13卷八、2003~2004秋_模式识别_张学工_期末.........................................14卷九、1999~2000春_模式识别_张学工_期末.........................................14附录、名词以及原理...................................................错误!未定义书签。[模式识别基础]2009秋季清华大学自动化系|卷一、模式识别机经3卷一、模式识别机经答：１．设计最小错误率分类器：如果12(|)(|)PxPx则x为1反之12(|)(|)PxPx则x为2（特别的，当12(|)(|)PxPx，可以接受x为任何一类也可以拒绝。在连续情况下这种情况几乎完全不出现。1122(|)()(|)(|)()(|)()iiipxPPxpxPpxP，112212,(|)(|),(|)(|)whenPxPxxwhenPxPx2．画图如下，红色表示1(|)Px（[5,10]均匀分布的后验概率），蓝色表示2(|)Px（N(0,9)的后验概率）（注意！！！图是错的——作者）（图是错的）3．最小错误分类器有许多局限性。其一，其只考虑到错误率的限制，并未考虑到实际情况中不同错误的代价等等，为了克服这类局限性，学者们在最小错误率之外又设计了最小风险分类器、限定一类错误率令另一类错误率最小的分类器等；其二，其只能用于监督学习，要求已知分类情况，并且要满足I.I.D条件即样本与总体分布相符；其三，其要求必须知道先验概率，许多实际问题的先验概率是难以得到的。答：（题目不完整）最近邻法（k=1），k近邻（k个最近的点投票），可以考虑加权1.(16分)正态分布N(0,9)与均匀分布[5,10],先验概率1/2最小错误率分类器,并画图.最小错误率分类器缺点2.(22分)8个样品w13个...,w25个.....1)最近邻分类,画图2)给两个点..,问怎么分3)最近邻分类器线性分类器?4)设计二次曲面分之5)压缩近邻法压缩过程及结果6)压缩近邻法分界面并比较1)3.(5分)证明两个样品构成得协方差矩阵一般是奇异的（不可逆的）2009秋季[模式识别基础]4卷一、模式识别机经|清华大学自动化系答：设1212,,2XXXXM,从而21121212cov(,)()()()()22TTXXXXXXXMXM其第i行j列元素为1,2,1,2,{()()}iijjxxxx，,mnx表示第m个样本第n个维度的值。从而这是一个行列式为零的矩阵（第一行除以(1,12,1xx）,第二行除以1,22,2)xx（之后想减得零，故该协方差阵是奇异的。答：距离可以是任意一种范数，设对点12,XX欧几里得距离（2范数）：T1/21221212||||[()()]XXXXXX每个坐标的绝对值差之和（1范数）：121(1)(2)1|||||()|niiiXXxx贝叶斯分类器不受、fisher投影法不受：都属于判别函数与距离度量无关的，故不受影响，近邻法，c均值法与受到距离度量的答：???这是一类决策树问题。可以将每一个是非问题看做一个决策树节点，是非答案决定了分支的方向（左或右）。调整问题应该使得在有效分类的情况下树深度最浅，就能在单次游戏最坏情况下最快猜出。（我觉得挺2的，应该不会受欢迎。。不过可以用作公安局犯罪嫌疑人指认的软件）答：例如k-近邻法的模糊性质。定义隶属函数()ix表示x属于i类的程度，值域上界为1，表示完全属于i，下界为0，表示完全不属于i，将对任意一个待判定的样本,选取某个距离度量（如欧几里得距离）最近的k个已知类别的训练样本,1,2,...,ixik，从而令4.(26分)距离不同会有不同结果1)给出两种你认为重要的距离,如何定义及物理意义2)贝叶斯分类器,近邻法,fisher投影法,c均值法是否受距离度量影响,不受则说明理由,5.(15分)AB玩游戏,A问是非问题,B回答是或非.问1)游戏与模式识别什么内容有关系?用模式识别语言描述2)B应如何调整问题3)如果做成计算机游戏,写出设计思路,方法,难点,解决方案.游戏受欢迎吗?为什么?6.(6分)自己设计模糊数学用于模式识别的其他理论方法(除去聚类).写出思路必要细节.分析可能结果.[模式识别基础]2009秋季清华大学自动化系|卷二、2008~2009秋_模式识别_张学工_期末B51()()/ikjijxsigxk得到x对于类i的隶属函数。答：这是一类特殊的图像识别问题，可以采用K-L分类卷二、2008~2009秋_模式识别_张学工_期末B答：1．ROC曲线（ReceiverOperationalCharacteristicCurve）是以FalsePositiveRate为横坐标，TruePositiveRate为纵坐标的绘制的曲线，通过改变分点给出对应的FP和TP绘成。曲线的点表示了在敏感度和特殊性之间的平衡，例如越往左，也就是假阳性越小，则真阳性也越小。曲线下方的面积越大，则表示该方法越有利于区分两种类别。2．交叉验证是指交叉验证(Cross-validation)主要用于建模应用中，在给定的建模样本中，拿出大部分样本进行建模型，留小部分样本用刚建立的模型进行预报，并求这小部分样本的预报误差，记录它们的平方加和。这个过程一直进行，直到所有的样本都被预报了一次而且仅被预报一次。把每个样本的预报误差平方加和，这个数越小，表示该方法越好3．特征选择与提取：特征是指对事物的观测或者某种运算，用于分类。特征提取是指直接观测到或者经过初步运算的特征——原始特征。特征选择是指从m个特征中选择m1个，m1m。特征提取（特征压缩、变换）将m个特征变为m2个新特征。4．推广能力：在有限的样本上建立的学习机器对未来样本的表现。5．随机森林是指通过bootstrapping样本来生成许多决策树，对于决策树上的每一个节点，选择m个变量来进行决策。计算训练集基于这m个变量的最佳分划。（Wiki:在机器学习中，随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。LeoBreiman和AdeleCutler发展出推论出随机森林的算法。而RandomForests是他们的商标。这个术语是1995年由贝尔实验室的TinKamHo所提出的随机决策森林（randomdecisionforests）而来的。这个方法则是结合Breimans的Bootstrapaggregating想法和Ho的randomsubspacemethod以建造决策树的集合。）答：7.(10分)专家经常根据特殊笔迹或特殊长相分类.问如何在一个人脸自动识别系统或笔迹自动识别系统中实现人的这一经验.从数据预处理,特征提取,选择分类器设计等角度描述实现这一经验的方法与可能性.优点?缺点?1.（30'）简要介绍下列概念·ROC曲线、交叉验证、似然函数、特征选择与提取、推广能力、随机森林2.（30’）简述Fisher线性判别方法的基本原理并讨论如何在Fisher线性判别中实现最小风险的分类决策。2009秋季[模式识别基础]6卷二、2008~2009秋_模式识别_张学工_期末B|清华大学自动化系1.Fisher线性判别法是指：将多维判别决策问题通过线性组合降低为1维的时候，选择一个最优的一维线性判别函数的方法。该方法考虑了不同类别样本的协方差和均值之差。决策面法向量为*112()wwSmm。2.考虑最小风险分类决策的时候，需要甄选分界阈值点。从而可以根据贝叶斯决策规获得一种一维内的最小风险分类器。例如，经过投影后的12,分别服从12(|),(|)pxpx的分布规律…P14页下方答：C均值法是一种动态聚类法，通过多次迭代，逐步调整类别划分，最终使某准则达到最优。C均值法的目标是最小化eJ——最小方差划分。用另一个角度来看，就是用C个码本来代表整个样本集，使这种表示带来的总体误差最小——向量量化。误差平方和聚类准则：见课件9.3(p14)适用条件：课件9.3(p22)答：1.支持向量机（SVM：SupportingVectorMechine)原理：课件5.5P6（特点是：P13），课本P301。支持向量机的基本思想可以概括为：首先通过非线性变化将输入空间变换到一个高维空间，然后在这个新空间中求取最优先行分类面，而这种非线性变换是通过定义适当的内积函数K(X,Y)实现的。2.多层感知器（MLP:Multi-LayerPerception）原理：课件5.4P10。是一种前馈人工神经网络。它利用三层或者三层以上多个感知器来讲输入数据映射为复杂输出数据，使得分类器可以产生非线性的或者超平面的决策面，从而成为分线性分类器。(Wiki:Amultilayerperceptronisafeedforwardartificialneuralnetworkmodelthatmapssetsofinputdataontoasetofappropriateoutput.Itisamodificationofthestandardlinearperceptroninthatitusesthreeormorelayersofneurons(nodes)withnonlinearactivationfunctions,andismorepowerfulthantheperceptroninthatitcandistinguishdatathatisnotlinearlyseparable,orseparablebyahyperplane.[1])3.联系与差异：都属于非线性分类器，但是其中一种是通过特征空间的非线性变换来实现最优决策面的，而多层感知器则是通过多层感知器（逻辑单元）的逻辑组合（输入-中间-输出）以及每层之间各数据的线性组合来实现非线性决策面的3.（20’）简述C-均值方法的基本原理，并讨论在什么情况下此方法比较适用。4.（20’）SVM与多层感知器都可以实现非线性分类，试讨论它们在原理上的联系与区别。5.（没有分）给课程提建设性建议。[模式识别基础]2009秋季清华大学自动化系|卷三、2007~2008秋_模式识别_张学工_期末B71.通过《模式识别基础》课程的学习。。。卷三、2007~2008秋_模式识别_张学工_期末B1.HierachicalClustering，分级聚类（课件9.4P45）：从各类只有一个样本点开始，逐级合并，每级只合并两类，