模式识别(配套教材《现代模式识别》)课件

模式识别主讲：蔡宣平教授

电话：73441（O）,73442（H）

E-mail：xpcai@

单位:电子科学与工程学院信息工程系1a★课程对象

★相关学科

★教学方法

★教学目标

★基本要求

★教材/参考文献关于本课程的有关说明2a★课程对象●信息工程专业本科生的专业课●学院硕士研究生的学位课●学院博士研究生的必修课之一3a★相关学科●统计学●概率论●线性代数（矩阵计算）●形式语言●人工智能●图像处理●计算机视觉等等4a★教学方法●着重讲述模式识别的基本概念，基本方法和算法原理。●注重理论与实践紧密结合实例教学：通过实例讲述如何将所学知识运用到实际应用之中●避免引用过多的、繁琐的数学推导5a★教学目标●掌握模式识别的基本概念和方法●有效地运用所学知识和方法解决实际问题●为研究新的模式识别的理论和方法打下基础6a★基本要求●基本：完成课程学习，通过考试，获得学分。●提高：能够将所学知识和内容用于课题研究，解决实际问题。●飞跃：通过模式识别的学习，改进思维方式，为将来的工作打好基础，终身受益。7a★教材/参考文献●孙即祥，现代模式识别，国防科技大学出版社，2003年。●吴逸飞译，模式识别－原理、方法及应用，清华大学出版社，2003年。●李晶皎等译，模式识别（第三版），电子工业出版社，2006年。8a讲授课程内容及安排第一章引论 第二章聚类分析第三章判别域代数界面方程法 第四章统计判决 第五章学习、训练与错误率估计 第六章最近邻方法第七章特征提取和选择 上机实习 9a第一章引论1.1概述1.2特征矢量和特征空间1.3随机矢量的描述1.4正态分布10a概念模式识别(PatternRecognition)：确定一个样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。样本（Sample)：一个具体的研究（客观）对象。如患者，某人写的一个汉字，一幅图片等。模式(Pattern)：对客体（研究对象）特征的描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。11a特征(Features)：能描述模式特性的量（测量值）。在统计模式识别方法中，通常用一个矢量表示，称之为特征矢量，记为

模式类(Class)：具有某些共同特性的模式的集合。概念12a模式识别的例子计算机自动诊断疾病:获取情况(信息采集)

测量体温、血压、心率、血液化验、X光透射、B超、心电图、CT等尽可能多的信息，并将这些信息数字化后输入电脑。当然在实际应用中要考虑采集的成本，这就是说特征要进行选择的。运行在电脑中的专家系统或专用程序可以分析这些数据并进行分类，得出正常或不正常的判断，不正常情况还要指出是什么问题。13a对象空间模式空间特征空间类型空间各类空间（Space)的概念模式采集：从客观世界（对象空间）到模式空间的过程称为模式采集。特征提取和特征选择：由模式空间到特征空间的变换和选择。类型判别：特征空间到类型空间所作的操作。模式识别三大任务14a1.1概述－模式识别系统数据采集特征提取二次特征提取与选择分类识别待识对象识别结果通常在采集信息过程中，还要去除所获取信息中的噪声，增强有用的信息等工作。这种使信息纯化的处理过程叫做信息的预处理。分类识别是根据事先确定的分类规则对前面选取的特征进行分类（即识别）。通常能描述对象的元素很多，为节约资源和提高处理速度，有时更为了可行性，在满足分类识别正确率要求的条件下，按某种准则尽量选用对正确分类识别作用较大的特征。使得用较少的特征就能完成分类识别任务。预处理这个环节的内容很广泛，与要解决的具体问题有关，例如，从图象中将汽车车牌的号码识别出来，就需要先将车牌从图像中找出来，再对车牌进行划分，将每个数字分别划分开。做到这一步以后，才能对每个数字进行识别。以上工作都应该在预处理阶段完成。数字化——比特流15a1.1概述－模式识别系统数据采集特征提取二次特征提取与选择分类识别待识对象识别结果数据采集特征提取改进分类识别规则二次特征提取与选择训练样本改进采集提取方法改进特征提取与选择制定改进分类识别规则人工干预正确率测试16a1.1概述－模式识别系统模式识别系统的主要环节：特征提取： 符号表示，如长度、波形、。。。特征选择： 选择有代表性的特征，能够正确分类学习和训练：利用已知样本建立分类和识别规则分类识别： 对所获得样本按建立的分类规则进行分类识别17a纸币识别器对纸币按面额进行分类

面额

1.1概述－系统实例5元10元20元50元100元18a1.1概述－系统实例 长度(mm)宽度(mm) 5元 136 63 10元 141 70 20元 146 70 50元 151 70 100元 156 7719a1.1概述－系统实例 磁性 金属条位置(大约) 5元 有 54/82 10元 有 54/87 20元 有 57/89 50元 有 60/91 100元 有 63/9320a5元10元20元50元100元12345678反射光波形21a1.1概述－系统实例数据采集、特征提取：

长度、宽度、磁性、磁性的位置，光反射亮度、光透射亮度等等

特征选择：

长度、磁性及位置、反射亮度分类识别：

确定纸币的面额及真伪22a1.1概述－系统实例训练集：是一个已知样本集，在监督学习方法中，用它来开发出模式分类器。测试集：在设计识别和分类系统时没有用过的独立样本集。系统评价原则：为了更好地对模式识别系统性能进行评价，必须使用一组独立于训练集的测试集对系统进行测试。23a例:汽车车牌识别从摄像头获取包含车牌的彩色图象车牌定位和获取字符分割和识别输入图象特征提取粗略定位分割字符确定类型精细定位识别、输出24a25a26a1.1概述－模式识别的基本方法一、统计模式识别二、句法模式识别三、模糊模式识别四、人工神经网络法五、人工智能方法27a1.1概述－模式识别的基本方法一、统计模式识别模式描述方法：特征向量模式判定：模式类用条件概率分布P(X/i)表示,m类就有m个分布，然后判定未知模式属于哪一个分布。28a1.1概述－模式识别的基本方法一、统计模式识别理论基础：概率论，数理统计主要方法：线性、非线性分类、Bayes决策、聚类分析主要优点：

1）比较成熟

2）能考虑干扰噪声等影响

3）识别模式基元能力强主要缺点：

1）对结构复杂的模式抽取特征困难

2）不能反映模式的结构特征，难以描述模式的性质

3）难以从整体角度考虑识别问题29a1.1概述－模式识别的基本方法二、句法模式识别模式描述方法：

符号串，树，图模式判定：

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

1）识别方便，可以从简单的基元开始，由简至繁。

2）能反映模式的结构特征，能描述模式的性质。

3）对图象畸变的抗干扰能力较强。主要缺点：

当存在干扰及噪声时，抽取特征基元困难，且易失误。1.1概述－模式识别的基本方法34a1.1概述－模式识别的基本方法三、模糊模式识别模式描述方法：

模糊集合A={(a,a),(b,b),...(n,n)}模式判定：

是一种集合运算。用隶属度将模糊集合划分为若干子集，m类就有m个子集，然后根据择近原则分类。35a理论基础：模糊数学主要方法：模糊统计法、二元对比排序法、推理法、模糊集运算规则、模糊矩阵 主要优点：

由于隶属度函数作为样本与模板间相似程度的度量，故往往能反映整体的与主体的特征，从而允许样本有相当程度的干扰与畸变。主要缺点：

准确合理的隶属度函数往往难以建立，故限制了它的应用。1.1概述－模式识别的基本方法36a1.1概述－模式识别的基本方法四、人工神经网络法模式描述方法：

以不同活跃度表示的输入节点集（神经元）模式判定：

是一个非线性动态系统。通过对样本的学习建立起记忆，然后将未知模式判决为其最接近的记忆。37a理论基础：神经生理学，心理学主要方法：BP模型、HOP模型、高阶网 主要优点：

可处理一些环境信息十分复杂，背景知识不清楚，推理规则不明确的问题。允许样本有较大的缺损、畸变。主要缺点：

模型在不断丰富与完善中，目前能识别的模式类还不够多。1.1概述－模式识别的基本方法38a1.1概述－模式识别的基本方法五、逻辑推理法（人工智能法）模式描述方法：

字符串表示的事实模式判定：是一种布尔运算。从事实出发运用一系列规则，推理得到不同结果，m个类就有m个结果。39a理论基础：演绎逻辑，布尔代数主要方法：产生式推理、语义网推理、框架推理 主要优点：

已建立了关于知识表示及组织，目标搜索及匹配的完整体系。对需要众多规则的推理达到识别目标确认的问题，有很好的效果。主要缺点：

当样本有缺损，背景不清晰，规则不明确甚至有歧义时，效果不好。1.1概述－模式识别的基本方法40a1.1概述－模式识别的发展简史1929年

G.Tauschek发明阅读机，能够阅读0-9的数字。30年代

Fisher提出统计分类理论，奠定了统计模式识别的基础。50年代

NoamChemsky提出形式语言理论——傅京荪提出句法/结构模式识别。60年代

L.A.Zadeh提出了模糊集理论，模糊模式识别方法得以发展和应用。41a1.1概述－模式识别的发展简史80年代以Hopfield网、BP网为代表的神经网络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。90年代小样本学习理论，支持向量机也受到了很大的重视。42a1.1概述－模式识别的应用(举例)生物学自动细胞学、染色体特性研究、遗传研究天文学天文望远镜图像分析、自动光谱学经济学股票交易预测、企业行为分析医学心电图分析、脑电图分析、医学图像分析43a1.1概述－主要实用系统举例文字识别（CharacterRecognition）OCR（OpticalCharacterRecognition）智能交通（IntelligentTraffic）车牌、车型。语音识别（Speechrecognition）翻译机，身份识别等目标识别ATR（AutomaicTargetRecognition）44a45a1.2特征矢量和特征空间46a1.3随机矢量的描述随机矢量：

在模式识别过程中，要对许多具体对象进行测量，以获得许多次观测值。每次观测值不一定相同，所以对许多对象而言，各个特征分量都是随机变量，即许多对象的特征向量在n维空间中呈随机性分布，称为随机矢量。47a1.3随机矢量的描述(一)随机矢量的分布函数：设为随机矢量，

为确定性矢量。

随机矢量的联合概率分布函数定义为：

式中表示括号中事件同时发生的概率。

48a1.3随机矢量的描述(一)随机矢量的分布函数：随机矢量的联合概率密度函数定义为：49a1.3随机矢量的描述50a1.3随机矢量的描述xp(x))(1wxp)(2wxp51a1.3随机矢量的描述52a1.3随机矢量的描述(二)随机矢量的数字特征：其中，的分量：式中，是的第个分量的边缘密度。随机矢量的均值矢量的各分量是相应的各随机分量的均值。53a1.3随机矢量的描述(二)随机矢量的数字特征：

⑵条件期望在模式识别中，经常以类别作为条件，在这种情况下随机矢量的条件期望矢量定义为54a1.3随机矢量的描述随机矢量的自协方差矩阵表征各分量围绕其均值的散布情况及各分量间的相关关系，其定义为：(二)随机矢量的数字特征：

⑶协方差矩阵

55a1.3随机矢量的描述56a1.3随机矢量的描述57a1.3随机矢量的描述(二)随机矢量的数字特征：⑷相关系数

由布尼亚科夫斯基不等式知:相关系数矩阵定义为:58a1.3随机矢量的描述59a1.3随机矢量的描述60a1.3随机矢量的描述61a1.3随机矢量的描述62a1.4正态分布63a1.4正态分布（1）一维随机变量的正态分布64a1.4正态分布65a1.4正态分布（2）随机矢量的正态分布正态分布随机矢量的概率密度函数定义为：66a1.4正态分布67a1.4正态分布（2）二维随机变量的正态分布68a1.4正态分布69a范例木板图象512×512d=3长度纹理亮度

c=2松木\桦木维数无限有限/很大R有限d不大c总结：模式识别过程d<<R<无限模式采集模式空间特征提取/选择类型空间分类特征空间客观世界待识别对象识别过程错误概率检测制定分类的判决规则特征提取/选择方法校正学习过程采集方法校正已知对象预处理70a试证明，对于正态分布，不相关与独立是等价的。试证明，多元正态随机矢量的线性变换仍为多元正态随机矢量。试证明，多元正态随机矢量X的分量的线性组合是一正态随机变量。习题71a模式识别主讲：蔡宣平教授

电话：73441（O）,73442（H）

E-mail：xpcai@

单位:电子科学与工程学院信息工程系72a第二章聚类分析

(ClusteringAnalysis)2.1聚类分析的概念2.2模式相似性测度2.3类的定义与类间距离2.4聚类的算法73a2.1聚类分析的概念一、聚类分析的基本思想★相似的归为一类。★模式相似性的度量和聚类算法。

★无监督分类（Unsupervised）

。二、特征量的类型★物理量----(重量、长度、速度)★次序量----(等级、技能、学识)

★名义量----(性别、状态、种类)第二章聚类分析74a三、方法的有效性

取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念2w2W1w1W2x1xb分类无效时的情况1.特征选取不当使分类无效。第二章聚类分析75a三、方法的有效性

取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念分类无效时的情况2.特征选取不足可能使不同类别的模式判为一类。2w2W1w1W2x1x3w3W第二章聚类分析76a三、方法的有效性

取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念分类无效时的情况3.特征选取过多可能无益反而有害,增加分析负担并使分析效果变差。2w2W1w1W2x1xb第二章聚类分析77a三、方法的有效性

取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念分类无效时的情况4.量纲选取不当。第二章聚类分析78a三、方法的有效性

取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念分类无效时的情况4.量纲选取不当。第二章聚类分析79a三、方法的有效性

取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念分类无效时的情况4.量纲选取不当。第二章聚类分析80a下列是一些动物的名称：羊（sheep） 狗（dog）蓝鲨（blueshark） 蜥蜴（lizard）毒蛇（viper） 猫（cat）麻雀（sparrow） 海鸥（seagull）金鱼（goldfish） 绯鲵鲣（red-mullet）

蛙（frog）要对这些动物进行分类，则不同的特征有不同的分法：特征选取不同对聚类结果的影响第二章聚类分析81a特征选取不同对聚类结果的影响羊,狗,猫蓝鲨蜥蜴,毒蛇,

麻雀,海鸥,金鱼,

绯鲵鲣,青蛙(a)按繁衍后代的方式分哺乳动物非哺乳动物第二章聚类分析82a金鱼

绯鲵鲣

蓝鲨羊,狗,猫蜥蜴,毒蛇

麻雀,海鸥

青蛙(b)按肺是否存在分无肺有肺特征选取不同对聚类结果的影响第二章聚类分析83a青蛙羊,狗,猫蜥蜴,毒蛇

麻雀,海鸥金鱼

绯鲵鲣

蓝鲨(c)按生活环境分陆地水里两栖特征选取不同对聚类结果的影响第二章聚类分析84a蓝鲨金鱼

绯鲵鲣蜥蜴,毒蛇

麻雀,海鸥

青蛙羊,狗,猫(d)按繁衍后代方式和肺是否存在分非哺乳且有肺哺乳且无肺哺乳且有肺非哺乳且无肺特征选取不同对聚类结果的影响第二章聚类分析85a距离测度不同,聚类结果也不同数据的粗聚类是两类,细聚类为4类第二章聚类分析86a综上可见:选择什么特征？选择多少个特征？选择什么样的量纲？选择什么样的距离测度？这些对分类结果都会产生极大影响。第二章聚类分析87a聚类过程遵循的基本步骤

一、特征选择(featureselection)

尽可能多地包含任务关心的信息二、近邻测度(proximitymeasure)

定量测定两特征如何“相似”或“不相似”三、聚类准则（clusteringcriterion）以蕴涵在数据集中类的类型为基础四、聚类算法（clusteringalgorithm）按近邻测度和聚类准则揭示数据集的聚类结构五、结果验证（validationoftheresults）常用逼近检验验证聚类结果的正确性六、结果判定（interpretationoftheresults）由专家用其他方法判定结果的正确性88a聚类应用的四个基本方向一、减少数据

许多时候，当数据量N很大时，会使数据处理变得很费力。因此可使用聚类分析的方法将数据分成几组可判断的聚类m（m<<N）来处理，每一个类可当作独立实体来对待。从这个角度看，数据被压缩了。第二章聚类分析89a二、假说生成在这种情况下，为了推导出数据性质的一些假说，对数据集进行聚类分析。因此，这里使用聚类作为建立假说的方法，然后用其他数据集验证这些假说。聚类应用的四个基本方向第二章聚类分析90a聚类应用的四个基本方向三、假说检验用聚类分析来验证指定假说的有效性。例如：考虑这样的假说“大公司在海外投资”。要验证这个假说是否正确，就要对大公司和有代表性的公司按规模、海外活跃度、成功完成项目的能力等进行聚类分析。从而来支持这个假说。第二章聚类分析91a四、基于分组的预测对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，对于一个未知模式，就可以用前面的聚类来确定是哪一类？聚类应用的四个基本方向例如：考虑被同种疾病感染的病人数据集。先按聚类分析进行分类，然后对新的病人确定他适合的聚类，从而判断他病情。第二章聚类分析92a2.2模式相似性测度

用于描述各模式之间特征的相似程度

●距离测度●相似测度●匹配测度第二章聚类分析93a2.2模式相似性测度一、距离测度(差值测度)测度基础：两个矢量矢端的距离测度数值：两矢量各相应分量之差的函数。时，等号成立；⑴，当且仅当⑵⑶第二章聚类分析94a2.2模式相似性测度常用的距离测度有：1.欧氏(Euclidean)距离

第二章聚类分析95a2.2模式相似性测度4.明氏(Minkowski)距离

(2-2-4)2.绝对值距离(街坊距离或Manhattan距离)(2-2-2)3.切氏(Chebyshev)距离

(2-2-3)

第二章聚类分析96a2.2模式相似性测度第二章聚类分析97a2.2模式相似性测度5.马氏(Mahalanobis)距离注意！马氏距离对一切非奇异线性变换都是不变的，这说明它不受特征量纲选择的影响，并且是平移不变的。上面的V的含义是这个矢量集的协方差阵的统计量，故马氏距离加入了对特征的相关性的考虑。第二章聚类分析98a2.2模式相似性测度第二章聚类分析99a100a现金识别例子(欧氏平均距离)数据样本介绍：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，……，数据60101a现金识别例子Eucliden=15.000000Manhattan=33.000000Chebyshev=11.000000Minkowski=11.039449——m=8100元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距离测度rmbdis102a现金识别例子—欧式平均距离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.72100a--20a:(13.23,81.28)42.87100a--10a:(12.45,90.91)54.99103a现金识别例子100圆A面的马式矩阵SW为:

43.553.964.852.752.752.346.837.953.9132.0137.5107.859.674.052.131.564.8137.5165.9124.174.684.167.637.152.7107.8124.1105.557.567.254.535.252.759.674.657.576.271.765.857.952.374.084.167.271.773.162.855.046.852.167.654.565.862.859.651.937.931.537.135.257.955.051.954.7104a现金识别例子SW的逆矩阵为:

0.3-0.00.1-0.1-0.1-0.1-0.20.2-0.00.3-0.1-0.10.1-0.60.30.20.1-0.10.3-0.1-0.0-0.2-0.30.4-0.1-0.1-0.10.20.10.3-0.1-0.2-0.10.1-0.00.10.7-0.7-0.40.2-0.1-0.6-0.20.3-0.72.2-0.0-1.0-0.20.3-0.3-0.1-0.4-0.01.2-0.50.20.20.4-0.20.2-1.0-0.51.0105a现金识别例子—马式平均距离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.5650a:(22.78,221.07)101.4120a:(22.51,343.26)162.9010a:(20.93,975.67)256.38106a现金识别例子—马式平均距离a:39.73101.41162.90256.38b:91.89230.25288.69659.47c:103.76135.94257.57724.96d:78.58171.10330.97675.90e:247.42443.46333.93218.71f:108.10328.11305.19607.51g:265.16956.58818.83348.42h:107.56339.64387.10628.88100圆50圆20圆10圆其中马式矩阵为100圆A面的，上面是各面到100圆A面的均值点的平均马式距离。107a现金识别例子——100圆A面的传感器1到其它各面传感器1的街坊距离108a2.2模式相似性测度二、相似测度测度基础：以两矢量的方向是否相近作为考虑的基础,矢量长度并不不重要。设1.角度相似系数(夹角余弦)(2-2-11)注意：坐标系的旋转和尺度的缩放是不变的,但对一般的线形变换和坐标系的平移不具有不变性。

109a现金识别例子——100圆A面传感器1

与其它各面的相似系数110a2.2模式相似性测度二、相似测度2.相关系数它实际上是数据中心化后的矢量夹角余弦。

(2-2-12)111a现金识别例子——100圆A面传感器1

与其它各面的相关系数112a2.2模式相似性测度二、相似测度3.指数相似系数

(2-2-13)式中为相应分量的协方差，为矢量维数。它不受量纲变化的影响。113a现金识别例子——100圆A面传感器1

与其它各面的相关系数114a2.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是

(0-0)匹配。二、匹配测度115a2.2模式相似性测度116a2.2模式相似性测度三、匹配测度(1)Tanimoto测度117a例2.2.2可以看出，它等于共同具有的特征数目与分别具有的特征种类总数之比。这里只考虑(1-1)匹配而不考虑(0-0)匹配。设则2.2模式相似性测度118a现金识别例子——100圆A面

与其它各面的匹配系数Tanimoto119a2.2模式相似性测度三、匹配测度(2)Rao测度注：(1-1)匹配特征数目和所选用的特征数目之比。120a现金识别例子——100圆A面

与其它各面的匹配系数Rao121a2.2模式相似性测度三、匹配测度(3)简单匹配系数注：上式分子为(1-1)匹配特征数目与(0-0)匹配特征数目之和，分母为所考虑的特征数目。122a现金识别例子——100圆A面

与其它各面的匹配系数Simple123a2.2模式相似性测度三、匹配测度(4)Dice系数(5)Kulzinsky系数124a现金识别例子——100圆A面

与其它各面的匹配系数dice125a现金识别例子——100圆A面

与其它各面的匹配系数Kulzinsky126a作业P44:2.1,2.3127a2·3类的定义与类间距离2.3.1类的定义定义之1

设集合S中任意元素xi与yj间的距离dij有

dij

h其中h为给定的阀值，称S对于阀值h组成一类。

类的定义有很多种，类的划分具有人为规定性，这反映在定义的选取及参数的选择上。一个分类结果的优劣最后只能根据实际来评价。书中的其它定义方法请大家自行参考学习128a2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法129a2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法式中表示和之间的距离。130a现金识别例子——100圆A面

与其它各面的最小距离131a2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法式中表示和之间的距离。132a现金识别例子——100圆A面

与其它各面的最大距离133a2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法pwqwkwpqkpqDkqDklDkpDlw134a2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法np,nq分别为类wp和wq的样本个数135a2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法136a现金识别例子——100圆A面

与其它各面的平均距离137a2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法分别为对应类的重心类内离差平方和递推公式为:138a

最近距离法

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离差平方和法

0139a2·3类的定义与类间距离2.3.3聚类的准则函数判别分类结果好坏的一般标准：类内距离小，类间距离大。

某些算法需要一个能对分类过程或分类结果的优劣进行评估的准则函数。如果聚类准则函数选择得好，聚类质量就会高。聚类准则往往是和类的定义有关的，是类的定义的某种体现。140a2.3.3聚类的准则函数一、类内距离准则

设有待分类的模式集在某种相似性测度基础上被划分为类，类内距离准则函数定义为:(表示类的模式均值矢量。)(2-3-20)2·3类的定义与类间距离141a2·3类的定义与类间距离142a加权类内距离准则:(2-3-22)(2-3-23)式中，表示类内任两个模式距离个组合数，所以表示类内表示类先验概率的估计──频率。平方和，共有两模式间的均方距离。N为待分类模式总数，143a2·3类的定义与类间距离144a加权类间距离准则:对于两类问题，类间距离有时取(2-3-26)和的关系是(2-3-27)(2-3-25)145a2·3类的定义与类间距离146a

的类内离差阵定义为

(2-3-28)2·3类的定义与类间距离式中为类的模式均值矢量

(2-3-29)147a148a例2.3.1证明：

2·3类的定义与类间距离149a

聚类的基本目的是使或。利用线形代数有关矩阵的迹和行列式的性质,可以定义如下4个聚类的准则函数:

2·3类的定义与类间距离150a2·3类的定义与类间距离由它们的构造可以看出，为得到好的聚类结果，应该使它们尽量的大。这类准则也大量用在特征提取和选择中。151a2·3类的定义与类间距离J1=7.60886J2=0.0010397J3=15.6089J4=62.9116用纸币数据计算获得的结果：152a作业P44:2.4,2.5,2.6153a2·4聚类的算法2.4.1聚类的技术方案聚类分析有很多具体的算法,有的比较简单,有的相对复杂和完善,但归纳起来就是三大类:1、按最小距离原则简单聚类方法2、按最小距离原则进行两类合并的方法3、依据准则函数动态聚类方法154a2·4聚类的算法(1)简单聚类方法

针对具体问题确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，当大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离原则将其分划到某一类中。这类算法运行中模式的类别及类的中心一旦确定将不会改变。155a2·4聚类的算法首先视各模式自成一类,然后将距离最小的两类合并成一类,不断地重复这个过程，直到成为两类为止。(2)按最小距离原则进行两类合并的方法这类算法运行中，类心不断地修正，但模式类别一旦指定后就不再改变，就是模式一旦划为一类后就不再被分划开，这类算法也称为谱系聚类法。156a2·4聚类的算法(3)依据准则函数动态聚类法设定一些分类的控制参数，定义一个能表征聚类结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。算法运行中，类心不断地修正，各模式的类别的指定也不断地更改。这类方法有—C均值法、ISODATA法等。157a2·4聚类的算法--简单聚类方法

158a2·4聚类的算法--简单聚类方法

159a2·4聚类的算法--简单聚类方法

160a2·4聚类的算法--简单聚类方法

这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。算法特点:从算法的过程可以看出，该算法结果很大程度上依赖于距离门限T的选取及模式参与分类的次序。如果能有先验知识指导门限T的选取，通常可获得较合理的效果。也可考虑设置不同的T和选择不同的次序，最后选择较好的结果进行比较。161a2·4聚类的算法--简单聚类方法

简单聚类图例162a例2.4.1：初始条件不同的简单聚类结果初始中心不同门限不同样本顺序不同

12345

12345

12345

12345

1098

1098

876

876

1167

1167

91011

91011163a2·4聚类的算法—简单聚类法程序

simpleclustering164a2·4聚类的算法—最大最小距离法

165a2·4聚类的算法--最大最小距离法

⒊算法原理步骤⑴选任一模式特征矢量作为第一个聚类中心例如，。作为第二个聚类中心。⑵从待分类矢量集中选距离最远的特征矢量166a⑶计算未被作为聚类中心的各模式特征矢量与、之间的距离，并求出它们之中的最小值，

为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。即167a则相应的特征矢量作为第三个聚类中心，然后转至⑸；否则，转至最后一步⑹。⑷若⑸设存在个聚类中心，计算未被作为聚类中心,并算出如果，则否则，转至最后一步⑹。的各特征矢量到各聚类中心的距离并转至⑸；168a⑹当判断出不再有新的聚类中心之后，将模式特中去，即计算当，则判。征矢量按最小距离原则分到各类这种算法的聚类结果与参数心的选取有关。如果没有先验知识指导和取，可适当调整和选取最合理的一种聚类。以及第一个聚类中的选，比较多次试探分类结果，169a2·4聚类的算法—最大最小距离法程序

maxminclustering170a2·4聚类的算法层次聚类法(HierarchicalClusteringMethod)(系统聚类法、谱系聚类法）按最小距离原则不断进行两类合并

2.4.3谱系聚类法171a2·4聚类的算法层次聚类法(HierarchicalClusteringMethod)(系统聚类法、谱系聚类法）按最小距离原则不断进行两类合并⒉算法思想

首先将N个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。

2.4.3谱系聚类法172a2·4聚类的算法

2.4.3谱系聚类法173a2·4聚类的算法

2.4.3谱系聚类法174a例2.4.3：如下图所示1、设全部样本分为6类，2、作距离矩阵D(0)3、求最小元素：4、把ω1,ω3合并ω7=(1,3)ω4,ω6合并ω8=(4,6)5、作距离矩阵D(1)ω1ω2ω3ω4ω5ω23ω314ω4748ω55262ω685913D(0)175a例2.4.3：如下图所示1、设全部样本分为6类，2、作距离矩阵D(0)3、求最小元素：4、把ω1,ω3合并ω7=(1,3)ω4,ω6合并ω8=(4,6)5、作距离矩阵D(1)D(1)ω7ω2ω8ω23ω874ω5522176a6、若合并的类数没有达到要求，转3。否则停止。3、求最小元素：4、ω8,ω5,ω2合并,ω9=（2,5,4,6）177a178a2·4聚类的算法—谱系聚类法程序

Hierarchicalclustering179a2·4聚类的算法最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了。因此，这些方法效果一般不会太理想。180a2.确定评估聚类质量的准则函数。确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢为，协方差阵为，则模式和该类的与该类均矢的马氏距离：距离平方为3.确定模式分划及聚类合并或分裂的规则。2·4聚类的算法——动态聚类算法要点181a2·4聚类的算法——动态聚类的基本步骤建立初始聚类中心，进行初始聚类；计算模式和类的距离，调整模式的类别；计算各聚类的参数，删除、合并或分裂一些聚类；从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止。182a2·4聚类的算法——动态聚类的框图产生初始聚类中心聚类检验聚类合理性待分类模式分类结果合理再迭代/修改参数不合理183a⒈条件及约定

设待分类的模式特征矢量集为：类的数目C是事先取定的。2·4聚类的算法

2.4.3动态聚类法——C-均值法⒉算法思想

该方法取定C个类别和选取

C个初始聚类中心，按最小距离原则将各模式分配到C类中的某一类，之后不断地计算类心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方之和最小。184a2·4聚类的算法

2.4.3动态聚类法——C-均值法185a2·4聚类的算法

2.4.3动态聚类法——C-均值法186a选代表点初始分类分类合理否4.动态聚类框图2·4聚类的算法

2.4.3动态聚类法——C-均值法最终分类Y修改分类N187a例2.4.2使用聚类算法实现图像分割在散射图上形成了两个聚类，利用模式识别的方法将其分开，就实现了图象的分割。188a

例2.4.3：已知有20个样本，每个样本有2个特征，数据分布如下图,使用C－均值法实现样本分类（C=2）。第一步：令C=2，选初始聚类中心为样本序号x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x2086789789896777788899189a190a00第二步：000＝））－（（＝-10100＝））－（（＝-10001＝））－（（＝-所以因为Î-<-191a0)01()01(=-=-,Î->-所以因为同理,12,21Î\=->-Î\=-<-＝＝......20652065都属于、、离计算出来，判断与第二个聚类中心的距、、同样把所有因此分为两类：),...,,()1(),,()1(205422311==18,221==NNGG二、一、192a193a194a第三步：更新聚类中心195a196a第四步：第二步：第三步：更新聚类中心197a198aclustering2·4聚类的算法

2.4.3动态聚类法——C-均值法程序199a作业P45:2.7,2.8200a2·4聚类的算法

2.4.3动态聚类法——C-均值法关于C-均值法收敛性的分析201a2·4聚类的算法

2.4.3动态聚类法——C-均值法当模式分布呈现类内团聚状，C-均值算法是能达到很好的聚类结果，故应用较多。从算法的迭代过程看，C-均值算法是能使各模式到其所判属的类别中心距离(平方)之和为最小的最佳聚类。202a2·4聚类的算法

2.4.3动态聚类法——C-均值法的改进在类别数未知的情况下，可使类数C由较小值逐步增加，对于每个选定的C分别使用该算法。显然准则函数J是随C的增加而单调减少。⑴C的调整作一条C一J曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。在增加过程中，总会出现使本来较密集的类再拆开的情况，此时J虽减小，但减小速度将变缓。如果作一条C一J曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。然而在许多情况下，曲线并无明显的这样的点。203a2·4聚类的算法

2.4.3动态聚类法——C-均值法的改进⑵初始聚类中心的选取①凭经验选择初始类心。②将模式随机地分成C类，计算每类中心，以其作为初始类心。③（最大密度），求以每个特征点为球心、某一正数d0为半径的球形域中特征点个数，这个数称为该点的密度。选取密度最大的特征点作为第一个初始类心Z1，然后在与Z1大于某个距离d的那些特征点中选取具有“最大”密度的特征点作为第二个初始类心Z2

，如此进行，选取C个初始聚类中心。204a2·4聚类的算法

2.4.3动态聚类法——C-均值法的改进⑵初始聚类中心的选取④用相距最远的C个特征点作为初始类心。具体地讲，是按前述的最大最小距离算法求取C个初始聚类中心。⑤当N较大时，先随机地从N个模式中取出一部分模式用谱系聚类法聚成C类，以每类的重心作为初始类心。⑥设已标准化的待分类模式集为希望将它们分为C类。205a⑥设已标准化的待分类模式集为希望将它们分为C类。设:计算:显然0≤ai≤C，若ai最接近整数j，则把xi分划至中wj。对所有样本都实行上述处理，就可实现初始分类，从而产生初始聚类中心。206a2·4聚类的算法

2.4.3动态聚类法——C-均值法的改进⑶用类核代替类心前面的算法存在一个不足，即只用一个聚类中心点作为一类的代表，但一个点往往不能充分地反映该类的模式分布结构，从而损失了很多有用的信息。当类的分布不是球状或近似球状时，这种算法很难有较好的效果。此时，可用类核代替类心，类核可以是一个函数、一个点集或其他适当的模型。比如前面我们讲过的马式距离。207a(3)动态聚类法——ISODATA算法(IterativeSelf-OrganizingDataAnalysisTechniquesAlgorithm迭代自组织数据分析)特点：启发性推理、分析监督、控制聚类结构及人机交互。算法思想： 在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。208aISODATA算法原理步骤⑴预置①设定聚类分析控制参数：=预期的类数，=每一类中允许的最少模式数目，=初始聚类中心个数(可以不等于c)，=类内各分量分布的距离标准差上界，(分裂用)=两类中心间的最小距离下界，(合并用)=在每次迭代中可以合并的类的最多对数，=允许的最多迭代次数。209aISODATA算法原理步骤210aISODATA算法原理步骤211aISODATA算法原理步骤 ①计算各类的中心⑷计算分类后的参数:各类中心、类内平均距离及总体平均距离。②计算各类中模式到类心的平均距离 ③计算各个模式到其类内中心的总体平均距离212aISODATA算法原理步骤213aISODATA算法原理步骤⑹计算各类类内距离的标准差矢量式中，为分量编号，为类的编号，为矢量维数，是的第个分量，是的第个分量。214aISODATA算法原理步骤215aISODATA算法原理步骤216aISODATA算法原理步骤217aISODATA算法原理步骤218a219aISODATA算法举例(二维)(1)初始值设定:类间距离上限距离标准差上界最少模式数目合并的类的最多对数220aISODATA算法举例(2)聚类(只有一个中心):221aISODATA算法举例(3)

因,无合并:(4)计算聚类中心、类内平均距离和总的平均距离。222aISODATA算法举例(5)因不是最后一步迭代，且，转至⑹(6)求的标准差矢量223aISODATA算法举例(7)

算得(6)因且将分裂成两类，取，则且转(2)224aISODATA算法举例(2)聚类(两个中心):(3)

因,无合并:225aISODATA算法举例(4)计算聚类中心、类内平均距离和总的平均距离。(5)因这是偶次迭代，满足算法原理步骤⑸中④的条件，故转⑼226aISODATA算法举例(9)计算类间距离由，类不能合并。(11)因不是最后一次迭代(，题设)，，判断是否修改参数。由上面结果可知，已获得所要求类别数目，类间距离大于类内距离，每类样本数都有样本总数的足够大的百分比，因此不改变参数。227a(2)～(4)计算结果与前一次迭代结果相同。(7)

,分裂条件不满足，转至⑼。，无新的变化，，转至⑵。(6)计算和的标准差矢量(5)没有任一种情况被满足，到⑹。与前一次迭代结果相同，无合并发生。228a⑵～⑷与前一次迭代结果相同。⑸因是最后一次迭代，令，转至⑼。⑼，同前。⑽因，无合并发生。⑾因是最后一次迭代,

结束。229aStart输入样本数据，置c;Nc;选初始类心zj

，j=1,2,..Nc(1)置控制参数：n,s,D,,L,I(3)合并判决：

nj<n

YNc=Nc-1(2)聚类：ifdil=min{D(xi,z1),D(xi,z2),…,D(xi,zNc)}thenxilN(4)计算分类后的参数：

①类心zj;②类内平均距离dj;③总类内平均距离dISODATA流程:230a(5)①结束判决：Ip≧IN(4)计算分类后的参数：

①类心zj;②类内平均距离dj;③总类内平均距离dN(5)④Ip为偶数N(5)②按类个数分裂判决：Nc≦c/2N(5)③分裂判决：Nc≧2*cNYYYD=0Y转(9)231aN(5)④Ip为偶数NY转(9)⑻(jmax>s){[(dj>d)(nj>2(n+1))][Nc≦c/2]}(6)计算各类类内距离的标准差矢量(7)找出最大分量(10)合并处理(11)结束判决：Ip≧I(9)计算各类对类间距离NEndYNc=Nc+1Ip=Ip+1(8)分裂处理YNY转修改参数修改参数否转重新聚类N232aStart输入样本数据，置c;Nc;选初始类心zj

，j=1,2,..Nc(1)置控制参数：n,s,D,,L,I(2)聚类：ifdil=min{D(xi,z1),D(xi,z2),…,D(xi,zNc)}thenxil(3)合并判决：

nj<n

NYNc=Nc-1(4)计算分类后的参数：

①类心zj;②类内平均距离dj;③总类内平均距离d修改参数入口重新聚类入口233a作业P45:2.9,2.10234a模式识别主讲：蔡宣平教授

电话：73441（O）,73442（H）

E-mail：xpcai@

单位:电子科学与工程学院信息工程系235a

第三章判别域代数界面方程法3.1用判别域界面方程分类的概念3.2线性判别函数3.3判别函数值的鉴别意义、权空间及解空间3.4Fisher线性判别3.5一次准则函数及梯度下降法3.6二次准则函数及其解法3.9广义线性判别函数3.10二次判别函数3.12位势函数分类法有监督分类236a

3.1用判别域界面方程分类的概念237a两类的分类问题，它们的边界线就是一个判别函数238a两类问题中线性不可分的实例239a三类的分类问题，它们的边界线也是一个判别函数240a3.1用判别域界面方程分类的概念

第三章判别域代数界面方程法241a

3.2线性判别函数

第三章判别域代数界面方程法242a243a244a多类问题图例（第一种情况）?不确定区域245a1、第一种情况（续）判别规则为：如果则判比如对图的三类问题,如果对于任一模式如果它的则该模式属于ω1类。246a1、第一种情况（续）如果某个X使二个以上的判别函数di>0

。则此模式X就无法作出确切的判决。如图另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确定区域。247a1、第一种情况（续）解：三个判别边界分别为：248a1、第一种情况（续）结论：因为所以它属于ω2类。249a1、第一种情况（续）250a251a2、第二种情况（续）多类问题图例（第二种情况）252a253ad12(x)=-d21(x)=–x