模式识别基础复习资料.docx
- 文档编号:4705970
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:14
- 大小:221.63KB
模式识别基础复习资料.docx
《模式识别基础复习资料.docx》由会员分享,可在线阅读,更多相关《模式识别基础复习资料.docx(14页珍藏版)》请在冰点文库上搜索。
[模式识别基础]
2009秋季
模式识别基础
复习资料
教师:
张学工
2009秋季
Xinbenlv@zzxy.org
清华大学自动化系
2009秋季
Contents
卷一、模式识别机经 3
卷二、2008~2009秋_模式识别_张学工_期末B 4
卷三、2007~2008秋_模式识别_张学工_期末B 6
卷四、2007~2008秋_模式识别_张学工_期末A 8
卷五、2006~2007秋_模式识别_张学工_期末B 9
卷六、2005~2006秋_模式识别_张学工_期末 10
卷七、2004~2005秋_模式识别_张学工_期末 11
卷八、2003~2004秋_模式识别_张学工_期末 12
卷九、1999~2000春_模式识别_张学工_期末 13
附录、名词以及原理 15
卷一、模式识别机经
1.(16分)正态分布N(0,9)与均匀分布[5,10],先验概率1/2
最小错误率分类器,并画图.最小错误率分类器缺点
答:
1.设计最小错误率分类器:
如果则为反之则为(特别的,当,可以接受为任何一类也可以拒绝。
在连续情况下这种情况几乎完全不出现。
,
2.画图如下,红色表示([5,10]均匀分布的后验概率),蓝色表示(N(0,9)的后验概率)(注意!
!
!
图是错的——作者)
(图是错的)
3.最小错误分类器有许多局限性。
其一,其只考虑到错误率的限制,并未考虑到实际情况中不同错误的代价等等,为了克服这类局限性,学者们在最小错误率之外又设计了最小风险分类器、限定一类错误率令另一类错误率最小的分类器等;其二,其只能用于监督学习,要求已知分类情况,并且要满足I.I.D条件即样本与总体分布相符;其三,其要求必须知道先验概率,许多实际问题的先验概率是难以得到的。
2.(22分)8个样品w1 3个...,w2 5个.....
1)最近邻分类,画图 2)给两个点..,问怎么分
3)最近邻分类器线性分类器?
4)设计二次曲面分之
5)压缩近邻法压缩过程及结果 6)压缩近邻法分界面并比较1)
答:
(题目不完整)最近邻法(k=1),k近邻(k个最近的点投票),可以考虑加权
3.(5分)证明两个样品构成得协方差矩阵一般是奇异的(不可逆的)
答:
设,从而其第i行j列元素为,表示第m个样本第n个维度的值。
从而这是一个行列式为零的矩阵(第一行除以(),第二行除以之后想减得零,故该协方差阵是奇异的。
4.(26分)"距离"不同会有不同结果
1)给出两种你认为重要的距离,如何定义及物理意义
2)贝叶斯分类器,近邻法,fisher投影法,c均值法是否受距离度量影响,不受则说明理由,
受,距离说明
答:
距离可以是任意一种范数,设对点
欧几里得距离(2范数):
每个坐标的绝对值差之和(1范数):
贝叶斯分类器不受、fisher投影法不受:
都属于判别函数与距离度量无关的,故不受影响,近邻法,c均值法与受到距离度量的
5.(15分)AB玩游戏,A问是非问题,B回答是或非.
问
1)游戏与模式识别什么内容有关系?
用模式识别语言描述
2)B应如何调整问题
3)如果做成计算机游戏,写出设计思路,方法,难点,解决方案.游戏受欢迎吗?
为什么?
答:
?
?
?
这是一类决策树问题。
可以将每一个是非问题看做一个决策树节点,是非答案决定了分支的方向(左或右)。
调整问题应该使得在有效分类的情况下树深度最浅,就能在单次游戏最坏情况下最快猜出。
(我觉得挺2的,应该不会受欢迎。
。
不过可以用作公安局犯罪嫌疑人指认的软件)
6.(6分)自己设计模糊数学用于模式识别的其他理论方法(除去聚类).写出思路必要细节
.分析可能结果.
答:
例如k-近邻法的模糊性质。
定义隶属函数表示属于类的程度,值域上界为1,表示完全属于,下界为0,表示完全不属于,将对任意一个待判定的样本,选取某个距离度量(如欧几里得距离)最近的k个已知类别的训练样本,从而令得到x对于类的隶属函数。
7.(10分)专家经常根据特殊笔迹或特殊长相分类.问如何在一个人脸自动识别系统或笔迹
自动识别系统中实现人的这一经验.从数据预处理,特征提取,选择分类器设计等角度描述
实现这一经验的方法与可能性.优点?
缺点?
答:
这是一类特殊的图像识别问题,可以采用K-L分类
卷二、2008~2009秋_模式识别_张学工_期末B
1.(30') 简要介绍下列概念
·ROC曲线、交叉验证、似然函数、特征选择与提取、推广能力、随机森林
答:
1.ROC曲线(ReceiverOperationalCharacteristicCurve)是以FalsePositiveRate为横坐标,TruePositiveRate为纵坐标的绘制的曲线,通过改变分点给出对应的FP和TP绘成。
曲线的点表示了在敏感度和特殊性之间的平衡,例如越往左,也就是假阳性越小,则真阳性也越小。
曲线下方的面积越大,则表示该方法越有利于区分两种类别。
2.交叉验证是指交叉验证(Cross-validation)主要用于建模应用中,在给定的建模样本中,拿出大部分样本进行建模型,留小部分样本用刚建立的模型进行预报,并求这小部分样本的预报误差,记录它们的平方加和。
这个过程一直进行,直到所有的样本都被预报了一次而且仅被预报一次。
把每个样本的预报误差平方加和,这个数越小,表示该方法越好
3.特征选择与提取:
特征是指对事物的观测或者某种运算,用于分类。
特征提取是指直接观测到或者经过初步运算的特征——原始特征。
特征选择是指从m个特征中选择m1个,m1 特征提取(特征压缩、变换)将m个特征变为m2个新特征。 4.推广能力: 在有限的样本上建立的学习机器对未来样本的表现。 5.随机森林是指通过bootstrapping样本来生成许多决策树,对于决策树上的每一个节点,选择m个变量来进行决策。 计算训练集基于这m个变量的最佳分划。 (Wiki: 在机器学习中,随机森林是一个包含多个决策树的分类器,并且其输出的类别是由个别树输出的类别的众数而定。 LeoBreiman和AdeleCutler发展出推论出随机森林的算法。 而"RandomForests"是他们的商标。 这个术语是1995年由贝尔实验室的TinKamHo所提出的随机决策森林(randomdecisionforests)而来的。 这个方法则是结合Breimans的"Bootstrapaggregating"想法和Ho的"randomsubspacemethod""以建造决策树的集合。 ) 2.(30’)简述Fisher线性判别方法的基本原理并讨论如何在Fisher线性判别中实现最小风险的分类决策。 答: 1.Fisher线性判别法是指: 将多维判别决策问题通过线性组合降低为1维的时候,选择一个最优的一维线性判别函数的方法。 该方法考虑了不同类别样本的协方差和均值之差。 决策面法向量为。 2.考虑最小风险分类决策的时候,需要甄选分界阈值点。 从而可以根据贝叶斯决策规获得一种一维内的最小风险分类器。 例如,经过投影后的分别服从的分布规律…P14页下方 3.(20’)简述C-均值方法的基本原理,并讨论在什么情况下此方法比较适用。 答: C均值法是一种动态聚类法,通过多次迭代,逐步调整类别划分,最终使某准则达到最优。 C均值法的目标是最小化——最小方差划分。 用另一个角度来看,就是用C个码本来代表整个样本集,使这种表示带来的总体误差最小——向量量化。 误差平方和聚类准则: 见课件9.3(p14) 适用条件: 课件9.3(p22) 4.(20’)SVM与多层感知器都可以实现非线性分类,试讨论它们在原理上的联系与区别。 答: 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.联系与差异: 都属于非线性分类器,但是其中一种是通过特征空间的非线性变换来实现最优决策面的,而多层感知器则是通过多层感知器(逻辑单元)的逻辑组合(输入-中间-输出)以及每层之间各数据的线性组合来实现非线性决策面的 5.(没有分)给课程提建设性建议。 1.通过《模式识别基础》课程的学习。 。 。 卷三、2007~2008秋_模式识别_张学工_期末B 1 .写出英文全称,中文,100字简述 5*6=30 a)Hierachical Clustering; b)MLP;c)Nonparametric Estimation; d)SVM e)Fisher's Linear Discriminant Analysis;f)PCA;g)Random Forest 1.HierachicalClustering,分级聚类(课件9.4P45): 从各类只有一个样本点开始,逐级合并,每级只合并两类,直到最后所有样本都归到一类。 聚类过程中考察类间相似度,依次决定类别数。 2.MLP,Multi-LayerPerception,多层感知器原理: 课件5.4P10。 是一种前馈人工神经网络。 它利用三层或者三层以上多个感知器来讲输入数据映射为复杂输出数据,使得分类器可以产生非线性的或者超平面的决策面,从而成为分线性分类器。 (Wiki: Amultilayerperceptronisafeedforwardartificialneuralnetworkmodelthatmapssetsofinputdataontoasetofappropriateoutput.Itisamodificationofthestandardlinearperceptroninthatitusesthreeormorelayersofneurons(nodes)withnonlinearactivationfunctions,andismorepowerfulthantheperceptroninthatitcandistinguishdatathatisnotlinearlyseparable,orseparablebyahyperplane.[1]) 3.Nonparametric Estimation: 非参数估计(课件3.5.1,P36) 不假设概率模型,通过样本落在区域的概率来估计出一个概率密度函数。 常用的有窗函数法(如近邻估计、Parzen窗估计)。 4.SVM,SupportingVectorMechine,支持向量机: 课件5.5P6(特点是: P13),课本P301。 支持向量机的基本思想可以概括为: 首先通过非线性变化将输入空间变换到一个高维空间,然后在这个新空间中求取最优先行分类面,而这种非线性变换是通过定义适当的内积函数K(X,Y)实现的。 5.Fisher's Linear Discriminant Analysis,Fisher线性判别分析: Fisher线性判别法是指: 将多维判别决策问题通过线性组合降低为1维的时候,选择一个最优的一维线性判别函数的方法。 该方法考虑了不同类别样本的协方差和均值之差。 决策面法向量为。 6.PCA,PrincipalComponentAnalysis,主成分分析: 课件8.2P21,目的: 在统计学中,主成分分析(principalcomponentsanalysis(PCA))是一种简化数据集的技术。 它是一个线性变换。 这个变换把数据变换到一个新的坐标系统中,使得任何数据投影的第一大方差在第一个坐标(称为第一主成分)上,第二大方差在第二个坐标(第二主成分)上,依次类推。 主成分分析经常用减少数据集的维数,同时保持数据集的对方差贡献最大的特征。 这是通过保留低阶主成分,忽略高阶主成分做到的。 这样低阶成分往往能够保留住数据的最重要方面。 但是,这也不是一定的,要视具体应用而定。 6.RandomForest,随机森林: 随机森林是指通过bootstrapping样本来生成许多决策树,对于决策树上的每一个节点,选择m个变量来进行决策。 计算训练集基于这m个变量的最佳分划。 (Wiki: 在机器学习中,随机森林是一个包含多个决策树的分类器,并且其输出的类别是由个别树输出的类别的众数而定。 LeoBreiman和AdeleCutler发展出推论出随机森林的算法。 而"RandomForests"是他们的商标。 这个术语是1995年由贝尔实验室的TinKamHo所提出的随机决策森林(randomdecisionforests)而来的。 这个方法则是结合Breimans的"Bootstrapaggregating"想法和Ho的"randomsubspacemethod""以建造决策树的集合。 ) 2. 200字简述 4*5=20 a)最小距离分类器何时是最优分类器? b)写出最小距离分类器,分段线性判别,最近邻法的关系 c)写出决策树和随机森林的关系,以及为什么要有随机森林 记不太清了,貌似有个SVM的原理? d)写出K-L变换和PCA的关系 写出特征提取和fisher线性判别的关系 答: 1.最小距离分类器: (课本P120页)最小距离分类器是指在贝叶斯决策规则当类条件概率密度为正态分布且各特征统计独立同方差时,利用贝叶斯决策规则在可以得到线性距离判别函数,特别是当时,决策规则式可以写成 这时的最小距离分类器是满足贝叶斯决策规则的最优分类器。 2.最小距离分类器是一种分段线性的判别方法。 每个样本点的类别由最近的代表点的类别决定。 最近邻法是这种分类器的一种应用,特殊之处在于(课本P120页)最近邻法是将每一个样本都当做类别的代表点 3.随机森林由多个决策树组成。 随机森林的优缺点: Wiki: Theadvantagesofrandomforestare: ·Formanydatasets,itproducesahighlyaccurateclassifier ·Ithandlesaverylargenumberofinputvariables ·Itestimatestheimportanceofvariablesindeterminingclassification ·Itgeneratesaninternalunbiasedestimateofthegeneralizationerrorastheforestbuildingprogresses ·Itincludesagoodmethodforestimatingmissingdataandmaintainsaccuracywhenalargeproportionofthedataaremissing ·Itprovidesanexperimentalwaytodetectvariableinteractions ·Itcanbalanceerrorinclasspopulationunbalanceddatasets ·Itcomputesproximitiesbetweencases,usefulforclustering,detectingoutliers,and(byscaling)visualizingthedata ·Usingtheabove,itcanbeextendedtounlabeleddata,leadingtounsupervisedclustering,outlierdetectionanddataviews ·Learningisfast Thedisadvantagesofrandomforestare: ·Randomforestarepronetooverfittingforsomedatasets.Thisisevenmorepronouncedinnoisyclassification/regressiontasks.[6] ·RandomForestdoesnothandlelargenumbersofirrelevantfeaturesaswellasensemblesofentropy-reducingdecisiontrees.[7] ·Itismoreefficienttoselectarandomdecisionboundarythananentropy-reducingdecisionboundary,thusmakinglargerensemblesmorefeasible.Althoughthismayseemtobeanadvantageatfirst,ithastheeffectofshiftingthecomputationfromtrainingtimetoevaluationtime,whichisactuallyadisadvantageformostapplications. 3.写出K-L变换和PCA的关系: PCA和K-L变换目的都是从高维的原始数据中提取低维度相关性低的特征数据。 (白云飞: PCA针对样本协方差矩阵,找出特征值较大的,K-L变换针对产生矩阵,可以根据不同准则挑选特征值和特征向量,二者本质相同) 3.构造两类分类器,100个训练数据,使用K近邻法,如何选择K,给出一个合适的K,说明理由(1*5=5) 答: K值不宜太大,太大则太多干扰样本点被纳入,太小则无法适应小规模错误情况,对于100个训练数据,一般来说选择5、7、9比较合适。 去奇数是为了避免出现两种类别数相同无法判决的情况。 4.SOM若没有邻域作用,则变成什么算法? 写出该算法的目标函数,算法基本步骤(1*15=15) 答: SOM思路类似先作向量量化(聚类),用较少的点(子类)代表原样本空间,把这些代表点进行分类。 (Wiki: Aself-organizingmap(SOM)orself-organizingfeaturemap(SOFM)isatypeofartificialneuralnetworkthatistrainedusingunsupervisedlearningtoproducealow-dimensional(typicallytwo-dimensional),discretizedrepresentationoftheinputspaceofthetrainingsamples,calledamap.Self-organizingmapsaredifferentfromotherartificialneuralnetworksinthesensethattheyuseaneighborhoodfunctiontopreservethetopologicalpropertiesoftheinputspace.) 如果没有邻域作用,就退化一个典型的C均值法。 该算法计算步骤(课件9.3,P17) 5.综合题。 文本自动分类的原理性设计,按内容分类为军事,体育,娱乐等。 例举本科所学内容和概念能在这个设计上怎么体现。 1*30=30 答: 因为是按已知内容分类,是一个监督学习的模式识别问题。 考虑如下监督学习模式 1.随机获取已经定义好类别的样本 1.特征提取: 每个样本进行词频统计,词汇来自《辞海》。 假设辞海有80000个词,则对每一个样本,得到一个80000维的特征数据。 显然,这是一个高维数据。 2.特征处理: (1)首先去所有样本出现频度都小于一定阈值的词汇,比方说出现5次。 剩下10000维。 (2)对这10000维进行主成分分析,得到一个低维度的特征数据,比如4维。 (3)对于这三维,可以进行一下分类: k近邻法、支撑向量机法(广义支撑向量机)、Fisher判别法等。 其中Fisher判别再次降维后还可以运用基于最小错误率的贝叶斯决策 3.对于以上监督学习模式的样本可以进行同一个方法的交叉验证,去除一定的干扰。 附加题.说明两类错误率。 在SVM线性不可分的情况下,如何把最小风险的概念引入SVM,对目标函数应该怎样修正。 (最多10分,全卷不会超过100分) 答: (1)两类错误率为“拒真纳伪”。 (2)(课本P298)如果线性不可分,就是某些样本不能满足条件时,引入松弛因子,使得条件变成,对于足够小的,只要使最小就能使错分样本数最小。 对应线性可分情况下的使分类间隔最大,在线性不可分的时候引入约束,最终得到目标函数,C为某个指定常数,起着控制对错分样本惩罚的程度(风险)的作用。 关于风险的讨论在课本P299页 卷四、2007~2008秋_模式识别_张学工_期末A(略) 卷五、2006~2007秋_模式识别_张学工_期末B 1. 写出英文全称并解释相应的概念或者方法的原理30% a)非参数估计 b)非监督模式识别 c)最大似然估计 d)MDS e)推广能力 f)kNN 答: 其他见前文卷子。 1.MDS: Multi-DimensionalScaling, Multidimensionalscaling(MDS)isasetofrelatedstatisticaltechniquesoftenused
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模式识别 基础 复习资料