模式识别详细ppt课件.ppt

《模式识别详细ppt课件.ppt》由会员分享，可在线阅读，更多相关《模式识别详细ppt课件.ppt（711页珍藏版）》请在三一办公上搜索。

1、 课程对象 相关学科 教学方法 教学目标 基本要求 教材/参考文献,关于本课程的有关说明,课程对象,信息工程专业本科生的专业课学院硕士研究生的学位课 学院博士研究生的必修课之一,相关学科,统计学概率论线性代数（矩阵计算）形式语言人工智能图像处理计算机视觉 等等,教学方法,着重讲述模式识别的基本概念，基本方法和算法原理。注重理论与实践紧密结合 实例教学：通过实例讲述如何将所学知识运用到实际应用之中避免引用过多的、繁琐的数学推导,教学目标,掌握模式识别的基本概念和方法有效地运用所学知识和方法解决实际问题为研究新的模式识别的理论和方法打下基础,基本要求,基本：完成课程学习，通过考试，获得学分。提高：

2、能够将所学知识和内容用于课题研究，解决实际问题。飞跃：通过模式识别的学习，改进思维方式，为将来的工作打好基础，终身受益。,教材/参考文献,孙即祥，现代模式识别，国防科技大学出版社，2003年。吴逸飞译，模式识别原理、方法及应用，清华大学出版社，2003年。李晶皎等译，模式识别（第三版），电子工业出版社，2006年。,讲授课程内容及安排,第一章 引论 第二章 聚类分析第三章 判别域代数界面方程法 第四章 统计判决 第五章 学习、训练与错误率估计 第六章 最近邻方法第七章 特征提取和选择 上机实习,第一章 引论,1.1 概述1.2 特征矢量和特征空间1.3 随机矢量的描述1.4 正态分布,概念,模

3、式识别(Pattern Recognition)：确定一个样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。,样本（Sample)：一个具体的研究（客观）对象。如患者，某人写的一个汉字，一幅图片等。,模式(Pattern)：对客体（研究对象）特征的描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。,特征(Features)：能描述模式特性的量（测量值）。在统计模式识别方法中，通常用一个矢量 表示，称之为特征矢量，记为,模式类(Class)：具有某些共同特性的模式的集合。,概念,要对这些动物进行分类，则不同的特征有不同的分法：有效地运用所学知识和

4、方法解决实际问题次序量-(等级、技能、学识)的损失函数，各种判决的平均损失4、停止回溯再向下搜索d32(x)0设两类样本的类内离差矩阵分别为:由于 是标量，于是有：因为d3(x3)=-2d1(x3)=0，d3(x3)=d2(x3)=0，错分，第五章 统计决策中的训练、学习 与错误率测试、估计以上工作都应该在预处理阶段完成。在信息论中，熵(Entropy)表示不确定性，熵越大不确定性越大。（4）后验概率的最大值的类别（09）就是手写数字的所属类别。提高：能够将所学知识和内容用于课题研究，解决实际问题。例：已知有20个样本，每个样本有2个特征，数据分布如下图,使用C均值法实现样本分类（C=2）。式

5、中 表示括号中事件同时发生的概率。（2）适用于非线性和线性可分的情况解：图形结构复杂，首先应分解为简单的子图（背景、物体）。d3(x)=-2x1-2基于类的概率密度函数的可分性判据,模式识别的例子,计算机自动诊断疾病:,获取情况(信息采集)测量体温、血压、心率、血液化验、X光透射、B超、心电图、CT等尽可能多的信息，并将这些信息数字化后输入电脑。当然在实际应用中要考虑采集的成本，这就是说特征要进行选择的。运行在电脑中的专家系统或专用程序可以分析这些数据并进行分类，得出正常或不正常的判断，不正常情况还要指出是什么问题。,各类空间（Space)的概念,模式采集：从客观世界（对象空间）到模式空间的过

6、程称为模式采集。,特征提取和特征选择：由模式空间到特征空间的变换和选择。,类型判别：特征空间到类型空间所作的操作。,模式识别三大任务,1.1 概述模式识别系统,通常在采集信息过程中，还要去除所获取信息中的噪声，增强有用的信息等工作。这种使信息纯化的处理过程叫做信息的预处理。,分类识别是根据事先确定的分类规则对前面选取的特征进行分类（即识别）。,通常能描述对象的元素很多，为节约资源和提高处理速度，有时更为了可行性，在满足分类识别正确率要求的条件下，按某种准则尽量选用对正确分类识别作用较大的特征。使得用较少的特征就能完成分类识别任务。,预处理这个环节的内容很广泛，与要解决的具体问题有关，例如，从图

7、象中将汽车车牌的号码识别出来，就需要先将车牌从图像中找出来，再对车牌进行划分，将每个数字分别划分开。做到这一步以后，才能对每个数字进行识别。以上工作都应该在预处理阶段完成。,数字化比特流,1.1 概述模式识别系统,1.1 概述模式识别系统,模式识别系统的主要环节：特征提取：符号表示，如长度、波形、。特征选择：选择有代表性的特征，能够正确分类学习和训练：利用已知样本建立分类和识别规则分类识别：对所获得样本按建立的分类规则进行分类识别,纸币识别器对纸币按面额进行分类 面额,1.1 概述系统实例,5元10元20元50元100元,1.1 概述系统实例,长度(mm)宽度(mm)5元1366310元141

8、7020元1467050元15170100元15677,1.1 概述系统实例,磁性金属条位置(大约)5元有 54/8210元有 54/8720元有 57/8950元有 60/91100元有 63/93,5元 10元 20元 50元 100元,12345678,反射光波形,1.1 概述系统实例,数据采集、特征提取：长度、宽度、磁性、磁性的位置，光反射亮度、光透射亮度等等,特征选择：长度、磁性及位置、反射亮度,分类识别：确定纸币的面额及真伪,1.1 概述系统实例,训练集：是一个已知样本集，在监督学习方法中，用它来开发出模式分类器。测试集：在设计识别和分类系统时没有用过的独立样本集。系统评价原则：为

9、了更好地对模式识别系统性能进行评价，必须使用一组独立于训练集的测试集对系统进行测试。,要对这些动物进行分类，则不同的特征有不同的分法：如果训练模式是线性可分的，则存在权矢量 使不等式组构成一个多级树结构：为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。这类算法运行中模式的类别及类的中心一旦确定将不会改变。计算J(y1)与J(y2)：第七章 特征提取与选择f(s)=-asb1-s(ln a-ln b)2 0(ab)针对具体问题确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，当大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离原则

10、将其分划到某一类中。权空间、解矢量与解空间1、按最小距离原则简单聚类方法求矩阵的广义逆计算量较大，引入的误差也可能很大，在实际中多采用下面的梯度法。基于类的概率密度函数的可分性判据模糊集合 A=(a,a),(b,b),.该方法也称为顺序后退法(SBS)。试用K-L变换做一维特征提取。ISODATA算法举例即 等于 的整数部分；（1）最佳的bi可通过 求得多类问题图例（第一种情况）,例:汽车车牌识别,从摄像头获取包含车牌的彩色图象车牌定位和获取字符分割和识别,1.1 概述模式识别的基本方法,一、统计模式识别二、句法模式识别三、模糊模式识别四、人工神经网络法五、人工智能方法,1.1 概述模式识别的

11、基本方法,一、统计模式识别,模式描述方法：特征向量 模式判定：模式类用条件概率分布P(X/i)表示,m类就有m个分布，然后判定未知模式属于哪一个分布。,1.1 概述模式识别的基本方法,一、统计模式识别,理论基础：概率论，数理统计主要方法：线性、非线性分类、Bayes决策、聚类分析主要优点：1）比较成熟 2）能考虑干扰噪声等影响 3）识别模式基元能力强主要缺点：1）对结构复杂的模式抽取特征困难2）不能反映模式的结构特征，难以描述模式的性质3）难以从整体角度考虑识别问题,1.1 概述模式识别的基本方法,二、句法模式识别,模式描述方法：符号串，树，图模式判定：是一种语言，用一个文法表示一个类，m类就

12、有m个文法，然后判定未知模式遵循哪一个文法。,例2：如下图中一幅图形，要识别图中的物体，选用句法模式识别方法.,1.1 概述模式识别的基本方法,解：图形结构复杂，首先应分解为简单的子图（背景、物体）。构成一个多级树结构：,1.1 概述模式识别的基本方法,在学习过程中，确定基元与基元之间的关系，推断出生成景物的方法。判决过程中，首先提取基元，识别基元之间的连接关系，使用推断的文法规则做句法分析。若分析成立，则判断输入的景物属于相应的类型。,1.1 概述模式识别的基本方法,理论基础：形式语言，自动机技术主要方法：自动机技术、CYK剖析算法、Early算法、转移图法主要优点：1）识别方便，可以从简单

13、的基元开始，由简至繁。2）能反映模式的结构特征，能描述模式的性质。3）对图象畸变的抗干扰能力较强。主要缺点：当存在干扰及噪声时，抽取特征基元困难，且易失误。,1.1 概述模式识别的基本方法,1.1 概述模式识别的基本方法,三、模糊模式识别,模式描述方法：模糊集合 A=(a,a),(b,b),.(n,n)模式判定：是一种集合运算。用隶属度将模糊集合划分为若干子集，m类就有m个子集，然后根据择近原则分类。,理论基础：模糊数学主要方法：模糊统计法、二元对比排序法、推理法、模糊集运算规则、模糊矩阵主要优点：由于隶属度函数作为样本与模板间相似程度的度量，故往往能反映整体的与主体的特征，从而允许样本有相当

14、程度的干扰与畸变。主要缺点：准确合理的隶属度函数往往难以建立，故限制了它的应用。,1.1 概述模式识别的基本方法,1.1 概述模式识别的基本方法,四、人工神经网络法,模式描述方法：以不同活跃度表示的输入节点集（神经元）模式判定：是一个非线性动态系统。通过对样本的学习建立起记忆，然后将未知模式判决为其最接近的记忆。,第三章 判别域代数界面方程法为了减少计算量和存储量，可以仿照单样本修正法:6 二次准则函数及其解法自动细胞学、染色体特性研究、遗传研究例：在军事目标识别中，假定有灌木丛和坦克两种类型，它们的先验概率分别是0.if(xki)and(di(xk)dl(xk)(li)then wi(k+1

15、)=wi(k)+xk wl(k+1)=wl(k)-xkwj(k+1)=wj(k)(ji,l)最大似然估计(MLE)1 概述模式识别的发展简史且通常有 cre数据样本介绍：10个文本文件np,nq分别为类wp和wq的样本个数3 类的定义与类间距离主要优点：可处理一些环境信息十分复杂，背景知识不清楚，推理规则不明确的问题。因为cre，故0 t 1。这种具有上述特点的快速搜索方法，称为分支定界算法。随机矢量 的均值矢量 的各分量是相应的各随机分量的均值。显然，区域重叠的部分越小或完全没有重叠，类别的可分性就越好。离散K-L变换（DKLT）为改善这种情况，可对每个类对的判据采用变换的方法，使对小的判据

16、较敏感。选取密度最大的特征点作为第一个初始类心Z1，然后在与Z1大于某个距离d的那些特征点中选取具有“最大”密度的特征点作为第二个初始类心Z2，如此进行，选取C个初始聚类中心。,理论基础：神经生理学，心理学主要方法：BP模型、HOP模型、高阶网主要优点：可处理一些环境信息十分复杂，背景知识不清楚，推理规则不明确的问题。允许样本有较大的缺损、畸变。主要缺点：模型在不断丰富与完善中，目前能识别的模式类还不够多。,1.1 概述模式识别的基本方法,1.1 概述模式识别的基本方法,五、逻辑推理法（人工智能法）,模式描述方法：字符串表示的事实模式判定：是一种布尔运算。从事实出发运用一系列规则，推理得到不同

17、结果，m个类就有m个结果。,理论基础：演绎逻辑，布尔代数主要方法：产生式推理、语义网推理、框架推理主要优点：已建立了关于知识表示及组织，目标搜索及匹配的完整体系。对需要众多规则的推理达到识别目标确认的问题，有很好的效果。主要缺点：当样本有缺损，背景不清晰，规则不明确甚至有歧义时，效果不好。,1.1 概述模式识别的基本方法,1.1 概述模式识别的发展简史,1929年 G.Tauschek发明阅读机，能够阅读0-9的数字。30年代 Fisher提出统计分类理论，奠定了统计模式识别的基础。50年代 Noam Chemsky 提出形式语言理论傅京荪提出句法/结构模式识别。60年代 提出了模糊集理论，模

18、糊模式识别方法得以发展和应用。,1.1 概述模式识别的发展简史,80年代 以Hopfield网、BP网为代表的神经网络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。90年代 小样本学习理论，支持向量机也受到了很大的重视。,1.1 概述模式识别的应用(举例),生物学自动细胞学、染色体特性研究、遗传研究天文学天文望远镜图像分析、自动光谱学经济学股票交易预测、企业行为分析医学心电图分析、脑电图分析、医学图像分析,1.1 概述主要实用系统举例,文字识别（Character Recognition）OCR（Optical Character Recognition）智能交通（Intellig

19、ent Traffic）车牌、车型。语音识别（Speech recognition）翻译机，身份识别等目标识别ATR（Automaic Target Recognition）,1.2 特征矢量和特征空间,1.3 随机矢量的描述,随机矢量：在模式识别过程中，要对许多具体对象进行测量，以获得许多次观测值。每次观测值不一定相同，所以对许多对象而言，各个特征分量都是随机变量，即许多对象的特征向量在n维空间中呈随机性分布，称为随机矢量。,先看一个简单的情况。60886 J2=0.如患者，某人写的一个汉字，一幅图片等。该方法也称为顺序后退法(SBS)。t=-(1/2)ln 麻雀（sparrow）海鸥（se

20、agull）由于变换后的模式是一维的，因此判别界面实际上是各类模式所在轴上的一个点，所以可以根据训练模式确定一个阈值 yt，于是Fisher判别规则为:=类内各分量分布的距离标准差上界，(分裂用)利用二次型关于矢量求导的公式可得：因为cre，故0 t 1。100圆 50圆 20圆 10圆80年代 以Hopfield网、BP网为代表的神经网络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。适用于各类模式的类域在某些分量轴上的投影不重迭或较少重迭的情况。(5)分裂判决：Nc2*c当N 增大时，估计结果与真实分布较为接近。对于c类问题，给定各类的后验概率 可以写成如下形式：该算法的高效性能

21、原因在于如下三个方面：在实际应用并不一定能同时具备，但并不影响它在实际使用中的价值。离散K-L变换（DKLT）的优劣进行评估的准则函数。由洛必达法则知：当 时令U=AV，因此存在非奇异矩阵U，使,1.3 随机矢量的描述,(一)随机矢量的分布函数：,设 为随机矢量，,为确定性矢量。,随机矢量的联合概率分布函数定义为：,式中 表示括号中事件同时发生的概率。,1.3 随机矢量的描述,(一)随机矢量的分布函数：,随机矢量 的联合概率密度函数定义为：,1.3 随机矢量的描述,1.3 随机矢量的描述,x,p(x),1.3 随机矢量的描述,1.3 随机矢量的描述,(二)随机矢量的数字特征：其中，的分量：,式

22、中，是 的第 个分量的边缘密度。随机矢量 的均值矢量 的各分量是相应的各随机分量的均值。,1.3 随机矢量的描述,(二)随机矢量的数字特征：条件期望在模式识别中，经常以类别 作为条件，在这种情况下随机矢量 的条件期望矢量定义为,1.3 随机矢量的描述,随机矢量 的自协方差矩阵表征各分量围绕其均值的散布情况及各分量间的相关关系，其定义为：,(二)随机矢量的数字特征：协方差矩阵,1.3 随机矢量的描述,1.3 随机矢量的描述,运用最小损失准则，判决规则为：当特征只有两个状态（0，1）时，常用匹配测度。使熵最小的特征利于分类，取熵的期望：24 聚类的算法为求最佳的s*，使上界取最小值Ch(称为Che

23、rnoff界限)s*应满足例：设两类问题中，二维模式均为正态分布，(三)类内及总体的均值矢量均值矢量和协方差阵的矩法估计=每一类中允许的最少模式数目，例如：考虑这样的假说“大公司在海外投资”。设一3类问题有如下判决函数d1(x)=-x1d2(x)=x1+x2-1d3(x)=x1-x2-1试画出下列各种情况的判决边界及各类的区域：（1）满足节中的第一种情况；若，则判的最小值，有如下的定理：离散K-L变换及其在特征提取为表述简洁，我们将随机矢量X及它的某个取值x都用同一个符号x表示，在以后各节中出现的是表示随机矢量还是它的一个实现根据内容是可以清楚知道的。模式识别(Pattern Recognit

24、ion)：确定一个样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。学院博士研究生的必修课之一基于总的类内、类间离差矩阵、进行特征提取选择且 f(0)=f(1)=0，从而有 f(s)0。蜥蜴,毒蛇麻雀,海鸥 青蛙通常能描述对象的元素很多，为节约资源和提高处理速度，有时更为了可行性，在满足分类识别正确率要求的条件下，按某种准则尽量选用对正确分类识别作用较大的特征。的优劣进行评估的准则函数。,1.3 随机矢量的描述,(二)随机矢量的数字特征：相关系数,由布尼亚科夫斯基不等式知:,相关系数矩阵定义为:,1.3 随机矢量的描述,1.3 随机矢量的描述,1.3 随机矢量的描述,1.

25、3 随机矢量的描述,1.4 正态分布,1.4 正态分布,（1）一维随机变量的正态分布,1.4 正态分布,1.4 正态分布,（2）随机矢量的正态分布,正态分布随机矢量 的概率密度函数定义为：,1.4 正态分布,1.4 正态分布,（2）二维随机变量的正态分布,1.4 正态分布,范例木板图象512512d=3长度纹理亮度 c=2松木 桦木,维数无限有限/很大R有限d不大c,总结：模式识别过程,dR无限,第五章 学习、训练与错误率估计1 2 3 4 5(4)计算分类后的参数：类心 zj;类内平均距离dj;总类内平均距离d例：已知有20个样本，每个样本有2个特征，数据分布如下图,使用C均值法实现样本分类

26、（C=2）。散度具有如下性质：首先视各模式自成一类,然后将距离最小的两类合并成一类,不断地重复这个过程，直到成为两类为止。则在这轮中x1应该剔除。选取密度最大的特征点作为第一个初始类心Z1，然后在与Z1大于某个距离d的那些特征点中选取具有“最大”密度的特征点作为第二个初始类心Z2，如此进行，选取C个初始聚类中心。许多时候，当数据量N很大时，会使数据处理变得很费力。对于两类问题1，2，认为 如果x1，则x 带正电荷 如果x2，则x 带负电荷文字识别（Character Recognition）用训练样本检验分类是否正确（a）令 试给出负对数似然比判决规则-如果 和，(Maximum Likeli

27、hood Estimate)第五章 统计决策中的训练、学习 与错误率测试、估计有效地运用所学知识和方法解决实际问题24 聚类的算法最大最小距离法均值矢量和协方差阵的矩法估计类内距离小，类间距离大。,试证明，对于正态分布，不相关与独立是等价的。试证明，多元正态随机矢量的线性变换仍为多元正态随机矢量。试证明，多元正态随机矢量X的分量的线性组合是一正态随机变量。,习题,模式识别,主讲：蔡宣平 教授 电话：73441（O）,73442（H）E-mail：单位:电子科学与工程学院信息工程系,第二章 聚类分析(Clustering Analysis),2.1 聚类分析的概念2.2 模式相似性测度2.3 类

28、的定义与类间距离2.4 聚类的算法,2.1 聚类分析的概念,一、聚类分析的基本思想 相似的归为一类。模式相似性的度量和聚类算法。无监督分类（Unsupervised）。,二、特征量的类型 物理量-(重量、长度、速度)次序量-(等级、技能、学识)名义量-(性别、状态、种类),第二章 聚类分析,三、方法的有效性 取决于分类算法和特征点分布情况的匹配。,2.1 聚类分析的概念,分类无效时的情况1.特征选取不当使分类无效。,第二章 聚类分析,三、方法的有效性 取决于分类算法和特征点分布情况的匹配。,2.1 聚类分析的概念,分类无效时的情况2.特征选取不足可能使不同类别的模式判为一类。,第二章 聚类分析

29、,三、方法的有效性 取决于分类算法和特征点分布情况的匹配。,2.1 聚类分析的概念,分类无效时的情况3.特征选取过多可能无益反而有害,增加分析负担并使分析效果变差。,第二章 聚类分析,三、方法的有效性 取决于分类算法和特征点分布情况的匹配。,2.1 聚类分析的概念,分类无效时的情况4.量纲选取不当。,第二章 聚类分析,三、方法的有效性 取决于分类算法和特征点分布情况的匹配。,2.1 聚类分析的概念,分类无效时的情况4.量纲选取不当。,第二章 聚类分析,三、方法的有效性 取决于分类算法和特征点分布情况的匹配。,2.1 聚类分析的概念,分类无效时的情况4.量纲选取不当。,第二章 聚类分析,下列是一

30、些动物的名称：羊（sheep）狗（dog）蓝鲨（blue shark）蜥蜴（lizard）毒蛇（viper）猫（cat）麻雀（sparrow）海鸥（seagull）金鱼（gold fish）绯鲵鲣（red-mullet）蛙（frog）要对这些动物进行分类，则不同的特征有不同的分法：,特征选取不同对聚类结果的影响,第二章 聚类分析,特征选取不同对聚类结果的影响,羊,狗,猫蓝鲨,蜥蜴,毒蛇,麻雀,海鸥,金鱼,绯鲵鲣,青蛙,(a)按繁衍后代的方式分,哺乳动物,非哺乳动物,第二章 聚类分析,金鱼绯鲵鲣蓝鲨,羊,狗,猫蜥蜴,毒蛇麻雀,海鸥 青蛙,(b)按肺是否存在分,无肺,有肺,特征选取不同对聚类结果的

31、影响,第二章 聚类分析,青蛙,羊,狗,猫 蜥蜴,毒蛇麻雀,海鸥,金鱼绯鲵鲣 蓝鲨,(c)按生活环境分,陆地,水里,两栖,特征选取不同对聚类结果的影响,第二章 聚类分析,蓝鲨,金鱼绯鲵鲣,蜥蜴,毒蛇麻雀,海鸥 青蛙,羊,狗,猫,(d)按繁衍后代方式和肺是否存在分,非哺乳且有肺,哺乳且无肺,哺乳且有肺,非哺乳且无肺,特征选取不同对聚类结果的影响,第二章 聚类分析,距离测度不同,聚类结果也不同,数据的粗聚类是两类,细聚类为4类,第二章 聚类分析,综上可见:,选择什么特征？选择多少个特征？选择什么样的量纲？选择什么样的距离测度？这些对分类结果都会产生极大影响。,第二章 聚类分析,聚类过程遵循的基本步骤

32、,一、特征选择(feature selection)尽可能多地包含任务关心的信息,二、近邻测度(proximity measure)定量测定两特征如何“相似”或“不相似”,三、聚类准则（clustering criterion）以蕴涵在数据集中类的类型为基础,四、聚类算法（clustering algorithm）按近邻测度和聚类准则揭示数据集的聚类结构,五、结果验证（validation of the results）常用逼近检验验证聚类结果的正确性,六、结果判定（interpretation of the results）由专家用其他方法判定结果的正确性,聚类应用的四个基本方向,一、减少数

33、据 许多时候，当数据量N很大时，会使数据处理变得很费力。因此可使用聚类分析的方法将数据分成几组可判断的聚类m（mN）来处理，每一个类可当作独立实体来对待。从这个角度看，数据被压缩了。,第二章 聚类分析,二、假说生成 在这种情况下，为了推导出数据性质的一些假说，对数据集进行聚类分析。因此，这里使用聚类作为建立假说的方法，然后用其他数据集验证这些假说。,聚类应用的四个基本方向,第二章 聚类分析,（3）把拒绝判决考虑在内，重新考核四次试验的结果。值得注意的是：上述的构造可分性判据的要求，即“单调性”、“叠加性”、“距离性”、“单调不减性”。（1)求解Fish准则函数许多时候，当数据量N很大时，会使数

34、据处理变得很费力。设一维数据1，2属于w1,-1，-2属于w2 求将w1和w2区分开的w0，w1。将 的具体表示代入上式得：(4)计算分类后的参数：类心 zj;类内平均距离dj;总类内平均距离d许多时候，当数据量N很大时，会使数据处理变得很费力。是概密的一个确定性的参数集,(3)使能量向某些分量相对集中，增强随机矢量总体的确定性基于类的概率密度函数的可分性判据置k=1，增量=1，赋初值：w1=(0,0,0)T,w2=(0,0,0)T,w3=(0,0,0)T,进行迭代运算：当固定 时，对 的最大似然估计，3 基于可分性判据进行变换的特征提取与选择23 类的定义与类间距离上式表明，最小最大损失判决

35、所导出的最佳分界面(6)求 的标准差矢量对于2,N2=6,系数为着重讲述模式识别的基本概念，基本方法和算法原理。,聚类应用的四个基本方向,三、假说检验 用聚类分析来验证指定假说的有效性。,例如：考虑这样的假说“大公司在海外投资”。要验证这个假说是否正确，就要对大公司和有代表性的公司按规模、海外活跃度、成功完成项目的能力等进行聚类分析。从而来支持这个假说。,第二章 聚类分析,四、基于分组的预测 对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，对于一个未知模式，就可以用前面的聚类来确定是哪一类？,聚类应用的四个基本方向,例如：考虑被同种疾病感染的病人数据集。先按聚类分析进行分类，

36、然后对新的病人确定他适合的聚类，从而判断他病情。,第二章 聚类分析,2.2 模式相似性测度,用于描述各模式之间特征的相似程度 距 离 测 度 相 似 测 度 匹 配 测 度,第二章 聚类分析,2.2 模式相似性测度,一、距离测度(差值测度)测度基础：两个矢量矢端的距离测度数值：两矢量各相应分量之差的函数。,第二章 聚类分析,2.2 模式相似性测度,常用的距离测度有：1.欧氏(Euclidean)距离,第二章 聚类分析,2.2 模式相似性测度,4.明氏(Minkowski)距离(2-2-4),2.绝对值距离(街坊距离或Manhattan距离)(2-2-2)3.切氏(Chebyshev)距离(2-

37、2-3),第二章 聚类分析,2.2 模式相似性测度,第二章 聚类分析,2.2 模式相似性测度,5.马氏(Mahalanobis)距离,注意！马氏距离对一切非奇异线性变换都是不变的，这说明它不受特征量纲选择的影响，并且是平移不变的。上面的V的含义是这个矢量集的协方差阵的统计量，故马氏距离加入了对特征的相关性的考虑。,第二章 聚类分析,2.2 模式相似性测度,第二章 聚类分析,现金识别例子(欧氏平均距离),数据样本介绍：10个文本文件文件名：rmb00.txt rmb09.txt每个文件有4个币种的数据，分别是：100圆、50圆、20圆、10圆每个币种有新旧两种版本，4个方向，故有8个数据块：如1

38、00圆的8个数据块：data100a,data100b,data100c,data100d老版 data100e,data100f,data100g,data100h新版每个数据块有8个传感器数据：传感器1，传感器2，传感器8每个传感器有60个采样数据：数据1，数据2，数据60,现金识别例子,Eucliden=15.000000Manhattan=33.000000Chebyshev=11.000000Minkowski=11.039449m=8,100元A面第1个样本第10点和20点的距离X:(75,76,101,83,102,96,91,82)Y:(70,74,90,76,99,96,90

39、,86),X-Y:5,2,11,7,3,0,1,-4,距离测度rmbdis,现金识别例子欧式平均距离,100a-100a:(2.65,49.66)24.41100a-100b:(16.37,55.87)33.97100a-100c:(3.87,58.34)29.41100a-100d:(6.86,53.74)33.04100a-100e:(3.87,62.12)27.51100a-100f:(13.60,67.61)34.67100a-100g:(11.40,68.56)32.27100a-100h:(11.27,68.61)34.43100a-50a:(18.76,76.20)40.7210

40、0a-20a:(13.23,81.28)42.87100a-10a:(12.45,90.91)54.99,现金识别例子,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

41、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,现金识别例子,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

42、 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,现金识别例子马式平均距离,100a:(7.46,80.05)39.73100b:(26.75,179.86)91.89100c:(14.50,231.44)103.76100d:(11.69,155.28)78.58100e:(5.65,2968.84)247.42100f:(39.19,2191.91)108.10100g:(10.68,2875.99)265.16100h:(9.41,2673.54)107.56 50a:(22.78,2

43、21.07)101.41 20a:(22.51,343.26)162.90 10a:(20.93,975.67)256.38,现金识别例子马式平均距离,a:39.73 101.41 162.90 256.38b:91.89 230.25 288.69 659.47c:103.76 135.94 257.57 724.96d:78.58 171.10 330.97 675.90e:247.42 443.46 333.93 218.71f:108.10 328.11 305.19 607.51g:265.16 956.58 818.83 348.42h:107.56 339.64 387.10 6

44、28.88,100圆 50圆 20圆 10圆,其中马式矩阵为100圆A面的，上面是各面到100圆A面的均值点的平均马式距离。,现金识别例子100圆A面的传感器1到其它各面传感器1的街坊距离,2.2 模式相似性测度,二、相似测度测度基础：以两矢量的方向是否相近作为考虑的基础,矢量长度并不不重要。设,1.角度相似系数(夹角余弦)(2-2-11),注意：坐标系的旋转和尺度的缩放是不变的,但对一般的线形变换和坐标系的平移不具有不变性。,现金识别例子100圆A面传感器1与其它各面的相似系数,2.2 模式相似性测度,二、相似测度2.相关系数它实际上是数据中心化后的矢量夹角余弦。(2-2-12),现金识别例

45、子100圆A面传感器1与其它各面的相关系数,2.2 模式相似性测度,二、相似测度3.指数相似系数(2-2-13),式中 为相应分量的协方差，为矢量维数。它不受量纲变化的影响。,现金识别例子100圆A面传感器1与其它各面的相关系数,2.2 模式相似性测度,当特征只有两个状态（0，1）时，常用匹配测度。0表示无此特征 1表示有此特征。故称之为二值特征。对于给定的x和y中的某两个相应分量xi与yj若xi=1,yj=1，则称 xi与yj是(1-1)匹配；若xi=1,yj=0，则称 xi与yj是(1-0)匹配；若xi=0,yj=1，则称 xi与yj是(0-1)匹配；若xi=0,yj=0，则称 xi与yj

46、是(0-0)匹配。,二、匹配测度,2.2 模式相似性测度,2.2 模式相似性测度,三、匹配测度,(1)Tanimoto测度,例,可以看出，它等于共同具有的特征数目与分别具有的特征种类总数之比。这里只考虑(1-1)匹配而不考虑(0-0)匹配。,设,则,2.2 模式相似性测度,现金识别例子100圆A面与其它各面的匹配系数Tanimoto,2.2 模式相似性测度,三、匹配测度,(2)Rao测度,注：(1-1)匹配特征数目和所选用的特征数目之比。,现金识别例子100圆A面与其它各面的匹配系数Rao,2.2 模式相似性测度,三、匹配测度,(3)简单匹配系数,注：上式分子为(1-1)匹配特征数目与(0-0

47、)匹配特征数目之和，分母为所考虑的特征数目。,现金识别例子100圆A面与其它各面的匹配系数Simple,2.2 模式相似性测度,三、匹配测度,(4)Dice系数,(5)Kulzinsky系数,现金识别例子100圆A面与其它各面的匹配系数dice,现金识别例子100圆A面与其它各面的匹配系数Kulzinsky,作业,P44:2.1,2.3,23 类的定义与类间距离,类的定义,定义之1 设集合S中任意元素xi与yj间的距离dij有 dij h其中h为给定的阀值，称S对于阀值h组成一类。,类的定义有很多种，类的划分具有人为规定性，这反映在定义的选取及参数的选择上。一个分类结果的优劣最后只能根据实际来

48、评价。,书中的其它定义方法请大家自行参考学习,23 类的定义与类间距离,类间距离测度方法,最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法,23 类的定义与类间距离,类间距离测度方法,最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法,现金识别例子100圆A面与其它各面的最小距离,23 类的定义与类间距离,类间距离测度方法,最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法,现金识别例子100圆A面与其它各面的最大距离,23 类的定义与类间距离,类间距离测度方法,最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差

49、平方和法,p,q,k,23 类的定义与类间距离,类间距离测度方法,最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法,np,nq分别为类wp和wq的样本个数,23 类的定义与类间距离,类间距离测度方法,最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法,现金识别例子100圆A面与其它各面的平均距离,23 类的定义与类间距离,类间距离测度方法,最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法,分别为对应类的重心,类内离差平方和,递推公式为:,23 类的定义与类间距离,聚类的准则函数,判别分类结果好坏的一般标准：类内距离小，类间距

50、离大。,某些算法需要一个能对分类过程或分类结果的优劣进行评估的准则函数。如果聚类准则函数选择得好，聚类质量就会高。聚类准则往往是和类的定义有关的，是类的定义的某种体现。,聚类的准则函数,一、类内距离准则 设有待分类的模式集 在某种相似性测度基础上被划分为 类，类内距离准则函数 定义为:(表示 类的模式均值矢量。),(2-3-20),23 类的定义与类间距离,23 类的定义与类间距离,加权类内距离准则:,(2-3-22),(2-3-23),23 类的定义与类间距离,加权类间距离准则:,(2-3-25),23 类的定义与类间距离,的类内离差阵定义为(2-3-28),23 类的定义与类间距离,式中