模式识别详细PPT.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,模式识别,主讲：蔡宣平 教授 电话：,73441,（,O,）,73442,（,H,）,E-mail,：,xpcai,单位,:,电子科学与工程学院信息工程系,2,课程对象,相关学科,教学方法,教学目标,基本要求,教材,/,参考文献,关于本课程的有关说明,3,课程对象,信息工程专业本科生的专业课,学院硕士研究生的学位课,学院博士研究生的必修课之一,4,相关学科,统计学,概率论,线性代数（矩阵计算）,形式语言,人工智能,图像处理,计算机视觉,等等,5,教学方法,着重讲述模式识别的基本概念，基本方法和算法原理。,注重理论与实践紧密结合,实例教学：通过实例讲述如何将所学知识运用到实际应用之中,避免引用过多的、繁琐的数学推导,6,教学目标,掌握模式识别的基本概念和方法,有效地运用所学知识和方法解决实际问题,为研究新的模式识别的理论和方法打下基础,7,基本要求,基本,：完成课程学习，通过考试，获得学分。,提高,：能够将所学知识和内容用于课题研究，解决实际问题。,飞跃：,通过模式识别的学习，改进思维方式，为将来的工作打好基础，终身受益。,8,教材,/,参考文献,孙即祥，现代模式识别，国防科技大学出版社，,2003,年。,吴逸飞译，模式识别原理、方法及应用，清华大学出版社，,2003,年。,李晶皎等译，模式识别（第三版），电子工业出版社，,2006,年。,9,讲授课程内容及安排,第一章 引论,第二章 聚类分析,第三章 判别域代数界面方程法,第四章 统计判决,第五章 学习、训练与错误率估计,第六章 最近邻方法,第七章 特征提取和选择,上机实习,10,第一章 引论,1.1,概述,1.2,特征矢量和特征空间,1.3,随机矢量的描述,1.4,正态分布,概念,模式识别,(Pattern Recognition),：,确定一个样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。,样本（,Sample),：,一个具体的研究（客观）对象。如患者，某人写的一个汉字，一幅图片等。,模式,(Pattern),：,对客体（研究对象）特征的描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。,11,特征,(Features),：,能描述模式特性的量（测量值）。在统计模式识别方法中，通常用一个矢量 表示，称之为特征矢量，记为,模式类,(Class),：,具有某些共同特性的模式的集合。,概念,12,模式识别的例子,计算机自动诊断疾病,:,获取情况,(,信息采集,),测量体温、血压、心率、血液化验、,X,光透射、,B,超、心电图、,CT,等尽可能多的信息，并将这些信息数字化后输入电脑。当然在实际应用中要考虑采集的成本，这就是说,特征要进行选择,的。,运行在电脑中的,专家系统,或专用程序可以分析这些数据并进行,分类,，得出正常或不正常的判断，不正常情况还要指出是什么问题。,13,14,对象空间,模式空间,特征空间,类型空间,各类空间（,Space),的概念,模式采集：,从客观世界（对象空间）到模式空间的过程称为模式采集。,特征提取和特征选择：,由模式空间到特征空间的变换和选择。,类型判别：,特征空间到类型空间所作的操作。,模,式,识,别,三大,任务,15,1.1,概述模式识别系统,数据采集,特征提取,二次特征,提取与选择,分类,识别,待识,对象,识别结果,通常在采集信息过程中，还要去除所获取信息中的噪声，增强有用的信息等工作。这种使信息纯化的处理过程叫做信息的,预处理,。,分类识别是根据事先确定的,分类规则,对前面选取的特征进行,分类,（即识别）。,通常能描述对象的元素很多，为节约资源和提高处理速度，有时更为了可行性，在满足分类识别正确率要求的条件下，按某种准则尽量选用对正确分类识别作用较大的特征。使得用较少的特征就能完成分类识别任务。,预处理,这个环节的内容很广泛，与要解决的具体问题有关，例如，从,图象,中将,汽车车牌,的号码,识别,出来，就需要先将,车牌,从,图像,中找出来，再对,车牌,进行,划分,，将每个,数字,分别,划分,开。做到这一步以后，才能对每个,数字,进行,识别,。以上工作都应该在预处理阶段完成。,数字化,比特流,16,1.1,概述模式识别系统,数据采集,特征提取,二次特征,提取与选择,分类,识别,待识,对象,识别结果,数据采集,特征提取,改进分类识别规则,二次特征提取与选择,训练,样本,改进采集,提取方法,改进特征提取与选择,制定改进分类识别规则,人工,干预,正确率,测试,17,1.1,概述模式识别系统,模式识别系统的主要环节：,特征提取：,符号表示，如长度、波形、。,特征选择：,选择有代表性的特征，能够正确分类,学习和训练：,利用已知样本建立分类和识别规则,分类识别：,对所获得样本按建立的分类规则进行分类识别,18,纸币识别器对纸币按面额进行分类,面额,1.1,概述系统实例,5,元,10,元,20,元,50,元,100,元,19,1.1,概述系统实例,长度,(mm),宽度,(mm),5,元,13663,10,元,14170,20,元,14670,50,元,15170,100,元,15677,20,1.1,概述系统实例,磁性金属条位置,(,大约,),5,元有,54/82,10,元有,54/87,20,元有,57/89,50,元有,60/91,100,元有,63/93,5,元,10,元,20,元,50,元,100,元,1,2,3,4,5,6,7,8,反射光波形,21,22,1.1,概述系统实例,数据采集、特征提取：,长度、宽度、磁性、磁性的位置，光反射亮度、光透射亮度等等,特征选择：,长度、磁性及位置、反射亮度,分类识别：,确定纸币的面额及真伪,23,1.1,概述系统实例,训练集：,是一个已知样本集，在监督学习方法中，用它来开发出模式分类器。,测试集：,在设计识别和分类系统时没有用过的独立样本集。,系统评价原则：,为了更好地对模式识别系统性能进行评价，必须使用一组独立于训练集的测试集对系统进行测试。,24,例,:,汽车车牌识别,从摄像头获取包含车牌的彩色图象,车牌定位和获取,字符分割和识别,输入图象,特征提取,粗略定位,分割字符,确定类型,精细定位,识别、输出,25,26,27,1.1,概述模式识别的基本方法,一、统计模式识别,二、句法模式识别,三、模糊模式识别,四、人工神经网络法,五、人工智能方法,28,1.1,概述模式识别的基本方法,一、统计模式识别,模式描述方法：,特征向量,模式判定：,模式类用条件概率分布,P(X/,i,),表示,m,类就有,m,个分布，然后判定未知模式属于哪一个分布。,29,1.1,概述模式识别的基本方法,一、统计模式识别,理论基础：,概率论，数理统计,主要方法：,线性、非线性分类、,Bayes,决策、聚类分析,主要优点：,1,）比较成熟,2,）能考虑干扰噪声等影响,3,）识别模式基元能力强,主要缺点：,1,）对结构复杂的模式抽取特征困难,2,）不能反映模式的结构特征，难以描述模式的性质,3,）难以从整体角度考虑识别问题,30,1.1,概述模式识别的基本方法,二、句法模式识别,模式描述方法：,符号串，树，图,模式判定：,是一种语言，用一个文法表示一个类，,m,类就有,m,个文法，然后判定未知模式遵循哪一个文法。,31,例,2,：如下图中一幅图形，要识别图中的物体，选用句法模式识别方法,.,1.1,概述模式识别的基本方法,32,解：,图形结构复杂，首先应分解为简单的子图（背景、物体）。构成一个多级树结构：,1.1,概述模式识别的基本方法,33,在学习过程中，确定基元与基元之间的关系，推断出生成景物的方法。,判决过程中，首先提取基元，识别基元之间的连接关系，使用推断的文法规则做句法分析。若分析成立，则判断输入的景物属于相应的类型。,1.1,概述模式识别的基本方法,34,理论基础：,形式语言，自动机技术,主要方法：,自动机技术、,CYK,剖析算法、,Early,算法、转移图法,主要优点,：,1,）识别方便，可以从简单的基元开始，由简至繁。,2,）能反映模式的结构特征，能描述模式的性质。,3,）对图象畸变的抗干扰能力较强。,主要缺点：,当存在干扰及噪声时，抽取特征基元困难，且易失误。,1.1,概述模式识别的基本方法,35,1.1,概述模式识别的基本方法,三、模糊模式识别,模式描述方法：,模糊集合,A=(,a,a),(,b,b),.(,n,n),模式判定：,是一种集合运算。用隶属度将模糊集合划分为若干子集，,m,类就有,m,个子集，然后根据择近原则分类。,36,理论基础：,模糊数学,主要方法：,模糊统计法、二元对比排序法、推理法、模糊集运算规则、模糊矩阵,主要优点,：由于隶属度函数作为样本与模板间相似程度的度量，故往往能反映整体的与主体的特征，从而允许样本有相当程度的干扰与畸变。,主要缺点：,准确合理的隶属度函数往往难以建立，故限制了它的应用。,1.1,概述模式识别的基本方法,37,1.1,概述模式识别的基本方法,四、人工神经网络法,模式描述方法：,以不同活跃度表示的输入节点集（神经元）,模式判定：,是一个非线性动态系统。通过对样本的学习建立起记忆，然后将未知模式判决为其最接近的记忆。,38,理论基础：,神经生理学，心理学,主要方法：,BP,模型、,HOP,模型、高阶网,主要优点,：可处理一些环境信息十分复杂，背景知识不清楚，推理规则不明确的问题。允许样本有较大的缺损、畸变。,主要缺点：,模型在不断丰富与完善中，目前能识别的模式类还不够多。,1.1,概述模式识别的基本方法,39,1.1,概述模式识别的基本方法,五、逻辑推理法（人工智能法）,模式描述方法：,字符串表示的事实,模式判定：,是一种布尔运算。从事实出发运用一系列规则，推理得到不同结果，,m,个类就有,m,个结果。,40,理论基础：,演绎逻辑，布尔代数,主要方法：,产生式推理、语义网推理、框架推理,主要优点,：已建立了关于知识表示及组织，目标搜索及匹配的完整体系。对需要众多规则的推理达到识别目标确认的问题，有很好的效果。,主要缺点：,当样本有缺损，背景不清晰，规则不明确甚至有歧义时，效果不好。,1.1,概述模式识别的基本方法,41,1.1,概述模式识别的发展简史,1929,年,G.Tauschek,发明阅读机，能够阅读,0-9,的数字。,30,年代,Fisher,提出统计分类理论，奠定了统计模式识别的基础。,50,年代,Noam Chemsky,提出形式语言理论,傅京荪提出句法,/,结构模式识别。,60,年代,L.A.Zadeh,提出了模糊集理论，模糊模式识别方法得以发展和应用。,42,1.1,概述模式识别的发展简史,80,年代,以,Hopfield,网、,BP,网为代表的神经网络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。,90,年代,小样本学习理论，支持向量机也受到了很大的重视。,43,1.1,概述模式识别的应用,(,举例,),生物学,自动细胞学、染色体特性研究、遗传研究,天文学,天文望远镜图像分析、自动光谱学,经济学,股票交易预测、企业行为分析,医学,心电图分析、脑电图分析、医学图像分析,44,1.1,概述主要实用系统举例,文字识别（,Character Recognition,）,OCR,（,Optical Character Recognition,）,智能交通（,Intelligent Traffic,）,车牌、车型。,语音识别（,Speech recognition,）,翻译机，身份识别等,目标识别,ATR,（,Automaic Target Recognition,）,45,46,1.2,特征矢量和特征空间,47,1.3,随机矢量的描述,随机矢量：,在模式识别过程中，要对许多具体对象进行测量，以获得许多次观测值。,每次观测值不一定相同，所以对许多对象而言，各个特征分量都是随机变量，即许多对象的特征向量在,n,维空间中呈随机性分布，称为随机矢量。,48,1.3,随机矢量的描述,(,一,),随机矢量的分布函数：,设 为随机矢量，,为确定性矢量。,随机矢量的联合概率分布函数定义为：,式中 表示括号中事件同时发生的概率。,49,1.3,随机矢量的描述,(,一,),随机矢量的分布函数：,随机矢量 的联合概率密度函数定义为：,50,1.3,随机矢量的描述,51,1.3,随机矢量的描述,x,p(x),),(,1,w,x,p,),(,2,w,x,p,52,1.3,随机矢量的描述,53,1.3,随机矢量的描述,(,二,),随机矢量的数字特征：,其中，的分量：,式中，是 的第 个分量的边缘密度。随机矢量 的均值矢量 的各分量是相应的各随机分量的均值。,54,1.3,随机矢量的描述,(,二,),随机矢量的数字特征：,条件期望,在模式识别中，经常以类别 作为条件，在这种情况下随机矢量 的条件期望矢量定义为,55,1.3,随机矢量的描述,随机矢量 的自协方差矩阵表征各分量围绕其均值的散布情况及各分量间的相关关系，其定义为：,(,二,),随机矢量的数字特征：,协方差矩阵,56,1.3,随机矢量的描述,57,1.3,随机矢量的描述,58,1.3,随机矢量的描述,(,二,),随机矢量的数字特征：,相关系数,由布尼亚科夫斯基不等式知,:,相关系数矩阵定义为,:,59,1.3,随机矢量的描述,60,1.3,随机矢量的描述,61,1.3,随机矢量的描述,62,1.3,随机矢量的描述,63,1.4,正态分布,64,1.4,正态分布,（,1,）一维随机变量的正态分布,65,1.4,正态分布,66,1.4,正态分布,（,2,）随机矢量的正态分布,正态分布随机矢量,的概率密度函数定义为：,67,1.4,正态分布,68,1.4,正态分布,（,2,）二维随机变量的正态分布,69,1.4,正态分布,范例,木板,图象,512512,d=3,长度,纹理,亮度,c=2,松木,桦木,维数,无限,有限,/,很大,R,有限,d,不大,c,总结：模式识别过程,dR,无限,模式采集,模式空间,特征提取,/,选择,类型空间,分类,特征空间,客观世界,待识别对,象,识别过程,错误概率检测,制定分类的,判决规则,特征提取,/,选择方法校正,学习过程,采集方法校正,已知对象,预处理,70,71,试证明，对于正态分布，不相关与独立是等价的。,试证明，多元正态随机矢量的线性变换仍为多元正态随机矢量。,试证明，多元正态随机矢量,X,的分量的线性组合是一正态随机变量。,习题,72,模式识别,主讲：蔡宣平 教授 电话：,73441,（,O,）,73442,（,H,）,E-mail,：,xpcai,单位,:,电子科学与工程学院信息工程系,73,第二章 聚类分析,(Clustering Analysis),2.1,聚类分析的概念,2.2,模式相似性测度,2.3,类的定义与类间距离,2.4,聚类的算法,74,2.1,聚类分析的概念,一、聚类分析的基本思想,相似的归为一类。,模式相似性的度量和聚类算法。,无监督分类,（,Unsupervised,）,。,二、特征量的类型,物理量,-(,重量、长度、速度,),次序量,-(,等级、技能、学识,),名义量,-(,性别、状态、种类,),第二章 聚类分析,75,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,2,w,2,W,1,w,1,W,2,x,1,x,b,分类无效时的情况,1.,特征选取,不当,使分类无效。,第二章 聚类分析,76,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,分类无效时的情况,2.,特征选取,不足,可能使不同类别的模式判为一类。,2,w,2,W,1,w,1,W,2,x,1,x,3,w,3,W,第二章 聚类分析,77,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,分类无效时的情况,3.,特征选取,过多,可能无益反而有害,增加分析负担并使分析效果变差。,2,w,2,W,1,w,1,W,2,x,1,x,b,第二章 聚类分析,78,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,分类无效时的情况,4.,量纲选取不当。,第二章 聚类分析,79,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,分类无效时的情况,4.,量纲选取不当。,第二章 聚类分析,80,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,分类无效时的情况,4.,量纲选取不当。,第二章 聚类分析,81,下列是一些动物的名称：,羊 （,sheep,）狗 （,dog,）,蓝鲨（,blue shark,）蜥蜴 （,lizard,）,毒蛇（,viper,）猫 （,cat,）,麻雀（,sparrow,）海鸥 （,seagull,）,金鱼（,gold fish,）绯鲵鲣（,red-mullet,）蛙 （,frog,）,要对这些动物进行分类，则不同的特征有不同的分法：,特征选取不同对聚类结果的影响,第二章 聚类分析,82,特征选取不同对聚类结果的影响,羊,狗,猫,蓝鲨,蜥蜴,毒蛇,麻雀,海鸥,金鱼,绯鲵鲣,青蛙,(a),按繁衍后代的方式分,哺乳动物,非哺乳动物,第二章 聚类分析,83,金鱼绯鲵鲣蓝鲨,羊,狗,猫,蜥蜴,毒蛇麻雀,海鸥 青蛙,(b),按肺是否存在分,无肺,有肺,特征选取不同对聚类结果的影响,第二章 聚类分析,84,青蛙,羊,狗,猫 蜥蜴,毒蛇麻雀,海鸥,金鱼绯鲵鲣 蓝鲨,(c),按生活环境分,陆地,水里,两栖,特征选取不同对聚类结果的影响,第二章 聚类分析,85,蓝鲨,金鱼绯鲵鲣,蜥蜴,毒蛇麻雀,海鸥 青蛙,羊,狗,猫,(d),按繁衍后代方式和肺是否存在分,非哺乳且有肺,哺乳且无肺,哺乳且有肺,非哺乳且无肺,特征选取不同对聚类结果的影响,第二章 聚类分析,86,距离测度不同,聚类结果也不同,数据的粗聚类是两类,细聚类为,4,类,第二章 聚类分析,87,综上可见,:,选择什么特征？,选择多少个特征？,选择什么样的量纲？,选择什么样的距离测度？,这些对分类结果都会产生极大影响。,第二章 聚类分析,88,聚类过程遵循的基本步骤,一、特征选择,(feature selection),尽可能多地包含任务关心的信息,二、近邻测度,(proximity measure),定量测定两特征如何,“,相似,”,或,“,不相似,”,三、聚类准则（,clustering criterion,）,以蕴涵在数据集中类的类型为基础,四、聚类算法（,clustering algorithm,）,按近邻测度和聚类准则揭示数据集的聚类结构,五、结果验证（,validation of the results,）,常用逼近检验验证聚类结果的正确性,六、结果判定（,interpretation of the results,）,由专家用其他方法判定结果的正确性,89,聚类应用的四个基本方向,一、减少数据,许多时候，当数据量,N,很大时，会使数据处理变得很费力。因此可使用聚类分析的方法将数据分成几组可判断的聚类,m,（,mN,）来处理，每一个类可当作独立实体来对待。从这个角度看，数据被压缩了。,第二章 聚类分析,90,二、假说生成,在这种情况下，为了推导出数据性质的一些假说，对数据集进行聚类分析。因此，这里使用聚类作为建立假说的方法，然后用其他数据集验证这些假说。,聚类应用的四个基本方向,第二章 聚类分析,91,聚类应用的四个基本方向,三、假说检验,用聚类分析来验证指定假说的有效性。,例如：考虑这样的假说,“,大公司在海外投资,”,。,要验证这个假说是否正确，就要对大公司和有代表性的公司按规模、海外活跃度、成功完成项目的能力等进行聚类分析。从而来支持这个假说。,第二章 聚类分析,92,四、基于分组的预测,对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，对于一个未知模式，就可以用前面的聚类来确定是哪一类？,聚类应用的四个基本方向,例如：考虑被同种疾病感染的病人数据集。,先按聚类分析进行分类，然后对新的病人确定他适合的聚类，从而判断他病情。,第二章 聚类分析,93,2.2,模式相似性测度,用于描述各模式之间特征的相似程度,距 离 测 度,相 似 测 度,匹 配 测 度,第二章 聚类分析,94,2.2,模式相似性测度,一、距离测度,(,差值测度,),测度基础：,两个矢量矢端的距离,测度数值：,两矢量各相应分量之差的函数,。,时，等号成立；,，当且仅当,第二章 聚类分析,95,2.2,模式相似性测度,常用的距离测度有：,1.,欧氏,(Euclidean),距离,第二章 聚类分析,96,2.2,模式相似性测度,4.,明氏,(Minkowski),距离,(2-2-4),2.,绝对值距离,(,街坊距离或,Manhattan,距离,)(2-2-2),3.,切氏,(Chebyshev),距离,(2-2-3),第二章 聚类分析,97,2.2,模式相似性测度,第二章 聚类分析,98,2.2,模式相似性测度,5.,马氏,(Mahalanobis),距离,注意！,马氏距离对一切非奇异线性变换都是不变的，这说明它不受特征量纲选择的影响，并且是平移不变的。,上面的,V,的含义是这个矢量集的协方差阵的统计量，故马氏距离加入了对特征的相关性的考虑。,第二章 聚类分析,99,2.2,模式相似性测度,第二章 聚类分析,100,101,现金识别例子,(,欧氏平均距离,),数据样本介绍：,10,个文本文件,文件名：,rmb00.txt,rmb09.txt,每个文件有,4,个币种的数据，分别是：,100,圆、,50,圆、,20,圆、,10,圆,每个币种有新旧两种版本，,4,个方向，故有,8,个数据块：,如,100,圆的,8,个数据块：,data100a,data100b,data100c,data100d,老版,data100e,data100f,data100g,data100h,新版,每个数据块有,8,个传感器数据：,传感器,1,，传感器,2,，,，传感器,8,每个传感器有,60,个采样数据：,数据,1,，数据,2,，,，数据,60,102,现金识别例子,Eucliden=15.000000,Manhattan=33.000000,Chebyshev=11.000000,Minkowski=11.039449,m=8,100,元,A,面第,1,个样本第,10,点和,20,点的距离,X:,(75,76,101,83,102,96,91,82),Y:,(70,74,90,76,99,96,90,86),X-Y:,5,2,11,7,3,0,1,-4,距离测度,rmbdis,103,现金识别例子,欧式平均距离,100a-100a:(2.65,49.66)24.41,100a-100b:(16.37,55.87)33.97,100a-100c:(3.87,58.34)29.41,100a-100d:(6.86,53.74)33.04,100a-100e:(3.87,62.12)27.51,100a-100f:(13.60,67.61)34.67,100a-100g:(11.40,68.56)32.27,100a-100h:(11.27,68.61)34.43,100a-50a:(18.76,76.20)40.72,100a-20a:(13.23,81.28)42.87,100a-10a:(12.45,90.91)54.99,104,现金识别例子,100,圆,A,面的马式矩阵,SW,为,:,43.5 53.9 64.8 52.7 52.7 52.3 46.8 37.9,53.9 132.0 137.5 107.8 59.6 74.0 52.1 31.5,64.8 137.5 165.9 124.1 74.6 84.1 67.6 37.1,52.7 107.8 124.1 105.5 57.5 67.2 54.5 35.2,52.7 59.6 74.6 57.5 76.2 71.7 65.8 57.9,52.3 74.0 84.1 67.2 71.7 73.1 62.8 55.0,46.8 52.1 67.6 54.5 65.8 62.8 59.6 51.9,37.9 31.5 37.1 35.2 57.9 55.0 51.9 54.7,105,现金识别例子,SW,的逆矩阵为,:,0.3 -0.0 0.1 -0.1 -0.1 -0.1 -0.2 0.2,-0.0 0.3 -0.1 -0.1 0.1 -0.6 0.3 0.2,0.1 -0.1 0.3 -0.1 -0.0 -0.2 -0.3 0.4,-0.1 -0.1 -0.1 0.2 0.1 0.3 -0.1 -0.2,-0.1 0.1 -0.0 0.1 0.7 -0.7 -0.4 0.2,-0.1 -0.6 -0.2 0.3 -0.7 2.2 -0.0 -1.0,-0.2 0.3 -0.3 -0.1 -0.4 -0.0 1.2 -0.5,0.2 0.2 0.4 -0.2 0.2 -1.0 -0.5 1.0,106,现金识别例子,马式平均距离,100a:(7.46,80.05)39.73,100b:(26.75,179.86)91.89,100c:(14.50,231.44)103.76,100d:(11.69,155.28)78.58,100e:(5.65,2968.84)247.42,100f:(39.19,2191.91)108.10,100g:(10.68,2875.99)265.16,100h:(9.41,2673.54)107.56,50a:(22.78,221.07)101.41,20a:(22.51,343.26)162.90,10a:(20.93,975.67)256.38,107,现金识别例子,马式平均距离,a:39.73 101.41 162.90 256.38,b:91.89 230.25 288.69 659.47,c:103.76 135.94 257.57 724.96,d:78.58 171.10 330.97 675.90,e:247.42 443.46 333.93 218.71,f:108.10 328.11 305.19 607.51,g:265.16 956.58 818.83 348.42,h:107.56 339.64 387.10 628.88,100,圆,50,圆,20,圆,10,圆,其中马式矩阵为,100,圆,A,面的，上面是各面到,100,圆,A,面的均值点的平均马式距离。,108,现金识别例子,100,圆,A,面的传感器,1,到其它各面传感器,1,的街坊距离,109,2.2,模式相似性测度,二、相似测度,测度基础：,以两矢量的方向是否相近作为考虑的基础,矢量长度并不不重要。设,1.,角度相似系数,(,夹角余弦,),(2-2-11),注意：坐标系的旋转和尺度的缩放是不变的,但对一般的线形变换和坐标系的平移不具有不变性。,110,现金识别例子,100,圆,A,面传感器,1,与其它各面的相似系数,111,2.2,模式相似性测度,二、相似测度,2.,相关系数,它实际上是数据中心化后的矢量夹角余弦。,(2-2-12),112,现金识别例子,100,圆,A,面传感器,1,与其它各面的相关系数,113,2.2,模式相似性测度,二、相似测度,3.,指数相似系数,(2-2-13),式中 为相应分量的协方差，为矢量维数。它不受量纲变化的影响。,114,现金识别例子,100,圆,A,面传感器,1,与其它各面的相关系数,115,2.2,模式相似性测度,当特征只有两个状态（,0,，,1,）时，常用匹配测度。,0,表示无此特征,1,表示有此特征。故称之为,二值特征,。,对于给定的,x,和,y,中的某两个相应分量,x,i,与,y,j,若,x,i,=1,y,j,=1,，则称,x,i,与,y,j,是,(1-1),匹配,；,若,x,i,=1,y,j,=0,，则称,x,i,与,y,j,是,(1-0),匹配；若,x,i,=0,y,j,=1,，则称,x,i,与,y,j,是,(0-1),匹配；若,x,i,=0,y,j,=0,，则称,x,i,与,y,j,是,(0-0),匹配。,二、匹配测度,116,2.2,模式相似性测度,117,2.2,模式相似性测度,三、匹配测度,(1)Tanimoto,测度,118,例,2.2.2,可以看出，它等于,共同具有的特征数目,与分别具有的特征种类总数之比。这里只考虑,(1-1),匹配而不考虑,(0-0),匹配。,设,则,2.2,模式相似性测度,119,现金识别例子,100,圆,A,面与其它各面的匹配系数,Tanimoto,120,2.2,模式相似性测度,三、匹配测度,(2),Rao,测度,注：,(1-1),匹配特征数目和所选用的特征数目之比。,121,现金识别例子,100,圆,A,面与其它各面的匹配系数,Rao,122,2.2,模式相似性测度,三、匹配测度,(3),简单匹配系数,注：上式分子为,(1-1),匹配特征数目与,(0-0),匹配特征数目之和，分母为所考虑的特征数目。,123,现金识别例子,100,圆,A,面与其它各面的匹配系数,Simple,124,2.2,模式相似性测度,三、匹配测度,(4)Dice,系数,(5)Kulzinsky,系数,125,现金识别例子,100,圆,A,面与其它各面的匹配系数,dice,126,现金识别例子,100,圆,A,面与其它各面的匹配系数,Kulzinsky,127,作业,P44:2.1,2.3,128,2,3,类的定义与类间距离,2.3.1,类的定义,定义之,1,设集合,S,中任意元素,x,i,与,y,j,间的距离,d,ij,有,d,ij,h,其中,h,为给定的阀值，称,S,对于阀值,h,组成一类。,类的定义有很多种，类的划分具有人为规定性，这反,映在定义的选取及参数的选择上。一个分类结果的优劣最后只能根据实际来评价。,书中的其它定义方法请大家自行参考学习,129,2,3,类的定义与类间距离,2.3.2,类间距离测度方法,最近距离法,最远距离法,中间距离法,重心距离法,平均距离法,离差平方和法,130,2,3,类的定义与类间距离,2.3.2,类间距离测度方法,最近距离法,最远距离法,中间距离法,重心距离法,平均距离法,离差平方和法,式中 表示 和 之间的距离。,131,现金识别例子,100,圆,A,面与其它各面的最小距离,132,2,3,类的定义与类间距离,2.3.2,类间距离测度方法,最近距离法,最远距离法,中间距离法,重心距离法,平均距离法,离差平方和法,式中 表示 和,之间的距离。,133,现金识别例子,100,圆,A,面与其它各面的最大距离,134,2,3,类的定义与类间距离,2.3.2,类间距离测度方法,最近距离法,最远距离法,中间距离法,重心距离法,平均距离法,离差平方和法,p,w,q,w,k,w,p,q,k,pq,D,kq,D,kl,D,kp,D,l,w,135,2,3,类的定义与类间距离,2.3.2,类间距离测度方法,最近距离法,最远距离法,中间距离法,重心距离法,平均距离法,离差平方和法,n,p,n,q,分别为类,w,p,和,w,q,的样本个数,136,2,3,类的定义与类间距离,2.3.2,类间距离测度方法,最近距离法,最远距离法,中间距离法,重心距离法,平均距离法,离差平方和法,137,现金识别例子,100,圆,A,面与其它各面的平均距离,138,2,3,类的定义与类间距离,2.3.2,类间距离测度方法,最近距离法,最远距离法,中间距离法,重心距离法,平均距离法,离差平方和法,分别为对应类的重心,类内离差平方和,递推公式为,:,139,最近距离法,1/2,1/2,0,-1/2,最远距离法,1/2,1/2,0,1/2,中间距离法,1/2,1/2,-1/4,0,重心距离法,0,平均距离法,0,0,可变平均法,0,可变法,0,离差平方和法,0,140,2,3,类的定义与类间距离,2.3.3,聚类的准则函数,判别分类结果好坏的一般标准：,类内距离小，类间距离大。,某些算法需要一个能对分类过程或分类结果,的优劣进行评估的准则函数。如果聚类准则函数,选择得好，聚类质量就会高。聚类准则往往是和,类的定义有关的，是类的定义的某种体现。,141,2.3.3,聚类的准则函数,一、类内距离准则,设有待分类的模式集 在某种相似性测度基础上被划分为 类，,类内距离准则函数 定义为,:(,表示 类的模式均值矢量。,),(2-3-20),2,3,类的定义与类间距离,142,2,3,类的定义与类间距离,143,加权类内距离准则,:,(2-3-22),(2-3-23),式中，,表示,类内任两个模式距离,个组合数，所以,表示类内,表示,类先验概率的估计频率。,平方和，共有,两模式间的均方距离。,N,为待分类模式总数，,144,2,3,类的定义与类间距离,145,加权类间距离准则,:,对于两类问题，类间距离有时取,(2-3-26),和,的关系是,(2-3-27),(2-3-25),146,2,3,类的定义与类间距离,147,的类内离差阵定义为,(2-3-28),2,3,类的定义与类间距离,式中 为类 的模式均值矢量,(2-3-29),148,149,例,2.3.1,证明：,2,3,类的定义与类间距离,150,聚类的基本目的是使 或,。利用线形代数有关矩阵的迹和行列式的性质,可以定义如下,4,个聚类的准则函数,:,2,3,类的定义与类间距离,151,2,3,类的定义与类间距离,由它们的构造可以看出，为得到好的聚类结果，应该使它们尽量的大。这类准则也大量用在特征提取和选择中。,152,2,3,类的定义与类间距离,J1=7.60886 J2=0.0010397,J3=15.6089 J4=62.9116,用纸币数据计算获得的结果：,153,作业,P44:2.4,2.5,2.6,154,2,4,聚类的算法,2.4.1,聚类的技术方案,聚类分析有很多具体的算法,有的比较简单,有的相对复杂和完善,但归纳起来就是三大类,:,1,、按最小距离原则简单聚类方法,2,、按最小距离原则进行两类合并的方法,3,、依据准则函数动态聚类方法,155,2,4,聚类的算法,(1),简单聚类方法,针对具体问题确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，当大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离原则将其分划到某一类中。,这类算法运行中模式的类别及类的中心一旦确定将不会改变。,156,2,4,聚类的算法,首先视各模式自成一类,然后将距离最小的两类合并成一类,不断地重复这个过程，直到成为两类为止。,(2),按最小距离原则进行两类合并的方法,这类算法运行中，类心不断地修正，但模式类别一旦指定后就不再改变，就是模式一旦划为一类后就不再被分划开，这类算法也称为谱系聚类法。,157,2,4,聚类的算法,(3),依据准则函数动态聚类法,设定一些分类的控制参数，定义一个能表征聚类结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。,算法运行中，类心不断地修正，各模式的类别的指定也不断地更改。这类方法有,C,均值法、,ISODATA,法等。,158,2,4,聚类的算法,-,简单聚类方法,159,2,4,聚类的算法,-,简单聚类方法,160,2,4,聚类的算法,-,简单聚类方法,161,2,4,聚类的算法,-,简单聚类方法,这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。,算法特点,:,从算法的过程可以看出，该算法结果很大程度上依赖于距离门限,T,的选取及模式参与分类的次序。如果能有先验知识指导门限,T,的选取，通常可获得较合理的效果。也可考虑设置不同的,T,和选择不同的次序，最后选择较好的结果进行比较。,162,2,4