模式识别(国家级精品课程)

1、1模式识别主讲：主讲： 蔡宣平蔡宣平 教授教授 电话：电话： 7344173441（O O）,73442,73442（H H）E-mailE-mail：单位单位: : 电子科学与工程学院信息工程系电子科学与工程学院信息工程系2 课程对象课程对象 相关学科相关学科 教学方法教学方法 教学目标教学目标 基本要求基本要求 教材教材/ /参考文献参考文献关于本课程的有关说明3 课程对象信息工程专业本科生的专业课信息工程专业本科生的专业课学院硕士研究生的学位课学院硕士研究生的学位课 学院博士研究生的必修课之一学院博士研究生的必修课之一4 相关学科统计学统计学概率论概率论线性代数（矩阵计算）线性代数（矩阵

2、计算）形式语言形式语言人工智能人工智能图像处理图像处理计算机视觉计算机视觉 等等等等5 教学方法着重讲述模式识别的基本概念，基本着重讲述模式识别的基本概念，基本方法和算法原理。方法和算法原理。注重理论与实践紧密结合注重理论与实践紧密结合 实例教学：通过实例讲述如何将所学实例教学：通过实例讲述如何将所学知识运用到实际应用之中知识运用到实际应用之中避免引用过多的、繁琐的数学推导避免引用过多的、繁琐的数学推导6 教学目标掌握模式识别的基本概念和方法掌握模式识别的基本概念和方法有效地运用所学知识和方法解决实际问题有效地运用所学知识和方法解决实际问题为研究新的模式识别的理论和方法打下基础为研究新的模式识

3、别的理论和方法打下基础 7 基本要求基本基本：完成课程学习，通过考试，获得学分。：完成课程学习，通过考试，获得学分。提高提高：能够将所学知识和内容用于课题研究，：能够将所学知识和内容用于课题研究，解决实际问题。解决实际问题。飞跃：飞跃：通过模式识别的学习，改进思维方式，通过模式识别的学习，改进思维方式，为将来的工作打好基础，终身受益。为将来的工作打好基础，终身受益。8教材教材/ /参考文献参考文献孙即祥，现代模式识别，国防科技大学孙即祥，现代模式识别，国防科技大学出版社，出版社，20032003年。年。吴逸飞译，模式识别原理、方法及应吴逸飞译，模式识别原理、方法及应用，清华大学出版社，用，清华

4、大学出版社，20032003年。年。李晶皎等译，模式识别（第三版），电李晶皎等译，模式识别（第三版），电子工业出版社，子工业出版社，20062006年。年。9讲授课程内容及安排第一章第一章 引论引论 第二章第二章 聚类分析聚类分析第三章第三章 判别域代数界面方程法判别域代数界面方程法 第四章第四章 统计判决统计判决 第五章第五章 学习、训练与错误率估计学习、训练与错误率估计 第六章第六章 最近邻方法最近邻方法第七章第七章 特征提取和选择特征提取和选择 上机实习上机实习10第一章 引论1.1 1.1 概述概述1.2 1.2 特征矢量和特征空间特征矢量和特征空间1.3 1.3 随机矢量的描述随机矢

5、量的描述1.4 1.4 正态分布正态分布概念概念n模式识别模式识别(Pattern Recognition)(Pattern Recognition)：确定一个确定一个样本的类别属性（模式类）的过程，即把某一样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。样本归属于多个类型中的某个类型。n样本（样本（Sample)Sample)：一个具体的研究（客观）对象。一个具体的研究（客观）对象。如患者，某人写的一个汉字，一幅图片等。如患者，某人写的一个汉字，一幅图片等。n模式模式(Pattern)(Pattern)：对客体（研究对象）特征的对客体（研究对象）特征的描述（定量的或结

6、构的描述），是取自客观世描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。界的某一样本的测量值的集合（或综合）。x),(21nxxxxn特征特征(Features)(Features)：能描述模式特性的量（测能描述模式特性的量（测量值）。在统计模式识别方法中，通常用一量值）。在统计模式识别方法中，通常用一个矢量个矢量 表示，称之为特征矢量，记为表示，称之为特征矢量，记为 n模式类模式类(Class)(Class)：具有某些共同特性的模式具有某些共同特性的模式的集合。的集合。概念概念模式识别的例子模式识别的例子计算机自动诊断疾病计算机自动诊断疾病:获取情况获取情况(

7、(信息采集信息采集) ) 测量体温、血压、心率、测量体温、血压、心率、血液化验、血液化验、X X光透射、光透射、B B超、心电图、超、心电图、CTCT等尽可等尽可能多的信息，并将这些信息数字化后输入电脑。能多的信息，并将这些信息数字化后输入电脑。当然在实际应用中要考虑采集的成本，这就是当然在实际应用中要考虑采集的成本，这就是说说特征要进行选择特征要进行选择的。的。运行在电脑中的运行在电脑中的专家系统专家系统或专用程序可以分析或专用程序可以分析这些数据并进行这些数据并进行分类分类，得出正常或不正常的判，得出正常或不正常的判断，不正常情况还要指出是什么问题。断，不正常情况还要指出是什么问题。14对

8、象空间对象空间模式空间模式空间特征空间特征空间类型空间类型空间各类空间（各类空间（Space)Space)的概念的概念模式采集：模式采集：从客观世界（对象从客观世界（对象空间）到模式空间的过程称为空间）到模式空间的过程称为模式采集。模式采集。特征提取和特征选择：特征提取和特征选择：由模式由模式空间到特征空间的变换和选择。空间到特征空间的变换和选择。类型判别：类型判别：特征空间到类型空特征空间到类型空间所作的操作。间所作的操作。模模式式识识别别三三大大任任务务151.1 概述模式识别系统数据采集数据采集特征提取特征提取二次特征二次特征提取与选择提取与选择分类分类识别识别待识待识对象对象识别结果识

9、别结果通常在采集信息过程中，还要去除所获取信息通常在采集信息过程中，还要去除所获取信息中的噪声，增强有用的信息等工作。这种使信息中的噪声，增强有用的信息等工作。这种使信息纯化的处理过程叫做信息的纯化的处理过程叫做信息的预处理预处理。分类识别是根据事先确定的分类识别是根据事先确定的分类规则分类规则对前面选对前面选取的特征进行取的特征进行分类分类（即识别）。（即识别）。通常能描述对象的元素很多，为节约资源和提通常能描述对象的元素很多，为节约资源和提高处理速度，有时更为了可行性，在满足分类识高处理速度，有时更为了可行性，在满足分类识别正确率要求的条件下，按某种准则尽量选用对别正确率要求的条件下，按某

10、种准则尽量选用对正确分类识别作用较大的特征。使得用较少的特正确分类识别作用较大的特征。使得用较少的特征就能完成分类识别任务。征就能完成分类识别任务。预处理预处理这个环节的内容很广泛，与要解决的具这个环节的内容很广泛，与要解决的具体问题有关，例如，从体问题有关，例如，从图象图象中将中将汽车车牌汽车车牌的号码的号码识别识别出来，就需要先将出来，就需要先将车牌车牌从从图像图像中找出来，再中找出来，再对对车牌车牌进行进行划分划分，将每个，将每个数字数字分别分别划分划分开。做到开。做到这一步以后，才能对每个这一步以后，才能对每个数字数字进行进行识别识别。以上工。以上工作都应该在预处理阶段完成。作都应该在

11、预处理阶段完成。数字化数字化比特流比特流161.1 概述模式识别系统数据采集数据采集特征提取特征提取二次特征二次特征提取与选择提取与选择分类分类识别识别待识待识对象对象识别结果识别结果数据采集数据采集特征提取特征提取改进分类改进分类识别规则识别规则二次特征提二次特征提取与选择取与选择训练训练样本样本改进采集改进采集提取方法提取方法改进特征提改进特征提取与选择取与选择制定改进分制定改进分类识别规则类识别规则人工人工干预干预正确率正确率测试测试171.1 概述模式识别系统模式识别系统的主要环节：模式识别系统的主要环节：特征提取：特征提取：符号表示，如长度、波形、。符号表示，如长度、波形、。特征选择

12、：特征选择：选择有代表性的特征，能够正确分类选择有代表性的特征，能够正确分类学习和训练：学习和训练：利用已知样本建立分类和识别规则利用已知样本建立分类和识别规则分类识别：分类识别：对所获得样本按建立的分类规则进行对所获得样本按建立的分类规则进行分类识别分类识别18纸币识别器对纸币按面额进行分类纸币识别器对纸币按面额进行分类 面额面额1.1 概述系统实例5元10元20元50元100元191.1 概述系统实例 长度长度(mm) (mm) 宽度宽度(mm)(mm)5 5元元13613663631010元元14114170702020元元14614670705050元元1511517070100100

13、元元1561567777201.1 概述系统实例磁性磁性金属条位置金属条位置( (大约大约) )5 5元元有有 54/8254/821010元元有有 54/8754/872020元元有有 57/8957/895050元元有有 60/9160/91100100元元有有 63/9363/935元 10元 20元 50元 100元12345678反反射射光光波波形形221.1 概述系统实例数据采集、特征提取：数据采集、特征提取： 长度、宽度、磁性、磁性的位置，光反射亮度、光长度、宽度、磁性、磁性的位置，光反射亮度、光透射亮度等等透射亮度等等 特征选择：特征选择： 长度、磁性及位置、反射亮度长度、磁性

14、及位置、反射亮度分类识别：分类识别： 确定纸币的面额及真伪确定纸币的面额及真伪231.1 概述系统实例训练集：训练集：是一个已知样本集，在监督学习方法是一个已知样本集，在监督学习方法中，用它来开发出模式分类器。中，用它来开发出模式分类器。测试集：测试集：在设计识别和分类系统时没有用过的在设计识别和分类系统时没有用过的独立样本集。独立样本集。系统评价原则：系统评价原则：为了更好地对模式识别系统性为了更好地对模式识别系统性能进行评价，必须使用一组独立于训练集的测能进行评价，必须使用一组独立于训练集的测试集对系统进行测试。试集对系统进行测试。24例:汽车车牌识别n从摄像头获取包含车牌的彩色图象从摄像

15、头获取包含车牌的彩色图象n车牌定位和获取车牌定位和获取n字符分割和识别字符分割和识别输入图象输入图象特征提取特征提取粗略定位粗略定位分割字符分割字符确定类型确定类型精细定位精细定位识别、输出识别、输出2526271.1 概述模式识别的基本方法一、统计模式识别一、统计模式识别二、句法模式识别二、句法模式识别三、模糊模式识别三、模糊模式识别四、人工神经网络法四、人工神经网络法五、人工智能方法五、人工智能方法281.1 概述模式识别的基本方法一、统计模式识别一、统计模式识别模式描述方法：模式描述方法： 特征向量特征向量 模式判定：模式判定： 模式类用条件概率分布模式类用条件概率分布P(X/P(X/

16、i i) )表示表示,m,m类就有类就有m m个分布，然后判定未知模式属于哪一个分布。个分布，然后判定未知模式属于哪一个分布。),(21nxxxx291.1 概述模式识别的基本方法一、统计模式识别一、统计模式识别理论基础：理论基础：概率论，数理统计概率论，数理统计主要方法：主要方法：线性、非线性分类、线性、非线性分类、BayesBayes决策、聚类分析决策、聚类分析主要优点：主要优点： 1 1）比较成熟）比较成熟 2 2）能考虑干扰噪声等影响）能考虑干扰噪声等影响 3 3）识别模式基元能力强）识别模式基元能力强主要缺点：主要缺点： 1 1）对结构复杂的模式抽取特征困难）对结构复杂的模式抽取特征

17、困难2 2）不能反映模式的结构特征，难以描述模式的性质）不能反映模式的结构特征，难以描述模式的性质3 3）难以从整体角度考虑识别问题）难以从整体角度考虑识别问题301.1 概述模式识别的基本方法二、句法模式识别二、句法模式识别模式描述方法：模式描述方法： 符号串，树，图符号串，树，图模式判定：模式判定： 是一种语言，用一个文法表示一个类，是一种语言，用一个文法表示一个类，m m类就类就有有m m个文法，然后判定未知模式遵循哪一个文法。个文法，然后判定未知模式遵循哪一个文法。31例例2 2：如下图中一幅图形，要识别图中的物体，：如下图中一幅图形，要识别图中的物体，选用句法模式识别方法选用句法模式

18、识别方法. .1.1 概述模式识别的基本方法32解：解：图形结构复杂，首先应分解为简单的子图图形结构复杂，首先应分解为简单的子图（背景、物体）。（背景、物体）。构成一个多级树结构：构成一个多级树结构：1.1 概述模式识别的基本方法33n在学习过程中，确定基元与基元之间的在学习过程中，确定基元与基元之间的关系，推断出生成景物的方法。关系，推断出生成景物的方法。n判决过程中，首先提取基元，识别基元判决过程中，首先提取基元，识别基元之间的连接关系，使用推断的文法规则之间的连接关系，使用推断的文法规则做句法分析。若分析成立，则判断输入做句法分析。若分析成立，则判断输入的景物属于相应的类型。的景物属于相

19、应的类型。1.1 概述模式识别的基本方法34理论基础：理论基础：形式语言，自动机技术形式语言，自动机技术主要方法：主要方法：自动机技术、自动机技术、CYKCYK剖析算法、剖析算法、EarlyEarly算法、算法、转移图法转移图法主要优点主要优点：1 1）识别方便，可以从简单的基元开始，由简至繁。）识别方便，可以从简单的基元开始，由简至繁。2 2）能反映模式的结构特征，能描述模式的性质。）能反映模式的结构特征，能描述模式的性质。3 3）对图象畸变的抗干扰能力较强。）对图象畸变的抗干扰能力较强。主要缺点：主要缺点：当存在干扰及噪声时，抽取特征基元困难，且易失误。当存在干扰及噪声时，抽取特征基元困难

20、，且易失误。1.1 概述模式识别的基本方法351.1 概述模式识别的基本方法三、模糊模式识别三、模糊模式识别模式描述方法：模式描述方法： 模糊集合模糊集合 A=(A=( a a,a), (,a), ( b b,b),. (,b),. ( n n,n),n)模式判定：模式判定： 是一种集合运算。用隶属度将模糊集合划分是一种集合运算。用隶属度将模糊集合划分为若干子集，为若干子集， m m类就有类就有m m个子集，然后根据择近原个子集，然后根据择近原则分类。则分类。36理论基础：理论基础：模糊数学模糊数学主要方法：主要方法：模糊统计法、二元对比排序法、推理法、模糊统计法、二元对比排序法、推理法、模糊

21、集运算规则、模糊矩阵模糊集运算规则、模糊矩阵主要优点主要优点：由于隶属度函数作为样本与模板间相似程度的度量，由于隶属度函数作为样本与模板间相似程度的度量，故往往能反映整体的与主体的特征，从而允许样本有故往往能反映整体的与主体的特征，从而允许样本有相当程度的干扰与畸变。相当程度的干扰与畸变。主要缺点：主要缺点：准确合理的隶属度函数往往难以建立，故限制了它的准确合理的隶属度函数往往难以建立，故限制了它的应用。应用。1.1 概述模式识别的基本方法371.1 概述模式识别的基本方法四、人工神经网络法四、人工神经网络法模式描述方法：模式描述方法： 以不同活跃度表示的输入节点集（神经元）以不同活跃度表示的

22、输入节点集（神经元）模式判定：模式判定： 是一个非线性动态系统。通过对样本的学习是一个非线性动态系统。通过对样本的学习建立起记忆，然后将未知模式判决为其最接近的建立起记忆，然后将未知模式判决为其最接近的记忆。记忆。38理论基础：理论基础：神经生理学，心理学神经生理学，心理学主要方法：主要方法：BPBP模型、模型、HOPHOP模型、高阶网模型、高阶网主要优点主要优点：可处理一些环境信息十分复杂，背景知识不清楚，推可处理一些环境信息十分复杂，背景知识不清楚，推理规则不明确的问题。允许样本有较大的缺损、畸变。理规则不明确的问题。允许样本有较大的缺损、畸变。主要缺点：主要缺点：模型在不断丰富与完善中，

23、目前能识别的模式类还不模型在不断丰富与完善中，目前能识别的模式类还不够多。够多。1.1 概述模式识别的基本方法391.1 概述模式识别的基本方法五、逻辑推理法（人工智能法）五、逻辑推理法（人工智能法）模式描述方法：模式描述方法： 字符串表示的事实字符串表示的事实模式判定：模式判定： 是一种布尔运算。从事实出发运用一系列规是一种布尔运算。从事实出发运用一系列规则，推理得到不同结果，则，推理得到不同结果，m m个类就有个类就有m m个结果。个结果。40理论基础：理论基础：演绎逻辑，布尔代数演绎逻辑，布尔代数主要方法：主要方法：产生式推理、语义网推理、框架推理产生式推理、语义网推理、框架推理主要优点

24、主要优点：已建立了关于知识表示及组织，目标搜索及匹配的完已建立了关于知识表示及组织，目标搜索及匹配的完整体系。对需要众多规则的推理达到识别目标确认的整体系。对需要众多规则的推理达到识别目标确认的问题，有很好的效果。问题，有很好的效果。主要缺点：主要缺点：当样本有缺损，背景不清晰，规则不明确甚至有歧义当样本有缺损，背景不清晰，规则不明确甚至有歧义时，效果不好。时，效果不好。1.1 概述模式识别的基本方法411.1 概述模式识别的发展简史19291929年年 G. TauschekG. Tauschek发明阅读机发明阅读机 ，能够阅，能够阅读读0-90-9的数字。的数字。3030年代年代 Fish

25、erFisher提出统计分类理论，奠定了提出统计分类理论，奠定了统计模式识别的基础。统计模式识别的基础。5050年代年代 Noam Chemsky Noam Chemsky 提出形式语言理论提出形式语言理论傅京荪提出句法傅京荪提出句法/ /结构模式识别。结构模式识别。6060年代年代 L.A.ZadehL.A.Zadeh提出了模糊集理论，模糊提出了模糊集理论，模糊模式识别方法得以发展和应用。模式识别方法得以发展和应用。421.1 概述模式识别的发展简史8080年代年代 以以HopfieldHopfield网、网、BPBP网为代表的神经网为代表的神经网络模型导致人工神经元网络复活，网络模型导致人

26、工神经元网络复活，并在模式识别得到较广泛的应用。并在模式识别得到较广泛的应用。9090年代年代 小样本学习理论，支持向量机也受小样本学习理论，支持向量机也受到了很大的重视。到了很大的重视。431.1 概述模式识别的应用(举例)n生物学生物学自动细胞学、染色体特性研究、遗传研究自动细胞学、染色体特性研究、遗传研究n天文学天文学天文望远镜图像分析、自动光谱学天文望远镜图像分析、自动光谱学n经济学经济学股票交易预测、企业行为分析股票交易预测、企业行为分析n医学医学心电图分析、脑电图分析、医学图像分析心电图分析、脑电图分析、医学图像分析441.1 概述主要实用系统举例n文字识别（文字识别（Charac

27、ter Recognition）OCR（Optical Character Recognition）n智能交通（智能交通（Intelligent Traffic）车牌、车型。车牌、车型。n语音识别（语音识别（Speech recognition）翻译机，身份识别等翻译机，身份识别等n目标识别目标识别ATR（Automaic Target Recognition）45461.2 特征矢量和特征空间471.3 随机矢量的描述随机矢量：随机矢量： 在模式识别过程中，要对许多具体对在模式识别过程中，要对许多具体对象进行测量，以获得许多次观测值。象进行测量，以获得许多次观测值。 每次观测值不一定相同，所

28、以对许多每次观测值不一定相同，所以对许多对象而言，各个特征分量都是随机变量，对象而言，各个特征分量都是随机变量，即许多对象的特征向量在即许多对象的特征向量在n n维空间中呈随维空间中呈随机性分布，称为随机矢量。机性分布，称为随机矢量。481.3 随机矢量的描述P),(21nXXXX),(21nxxxx),(),(221121nnnxXxXxXPxxxF)()(xXPxF(一一)随机矢量的分布函数：随机矢量的分布函数：设设 为随机矢量，为随机矢量， 为确定性矢量。为确定性矢量。 随机矢量的联合概率分布函数定义为：随机矢量的联合概率分布函数定义为： 式中式中 表示括号中事件同时发生的概率。表示括号

29、中事件同时发生的概率。 491.3 随机矢量的描述( (一一) )随机矢量的分布函数：随机矢量的分布函数：)(),(21xpxxxpnnnnxxxxxxF2121),(X随机矢量随机矢量 的联合概率密度函数定义为：的联合概率密度函数定义为： 501.3 随机矢量的描述5112X1X121.3 随机矢量的描述x xp(x)p(x)(1xp)(2xp2521.3 随机矢量的描述531.3 随机矢量的描述( (二二) )随机矢量的数字特征：随机矢量的数字特征：其中，其中， 的分量：的分量： 1212E()d.(,.,)d d.diiiiiinniXx p xxx p x xxx xxX)(ixpXi

30、X式中，式中， 是是 的第的第 个分量的边缘个分量的边缘密度。随机矢量密度。随机矢量 的均值矢量的均值矢量 的各的各分量是相应的各随机分量的均值。分量是相应的各随机分量的均值。541.3 随机矢量的描述( (二二) )随机矢量的数字特征：随机矢量的数字特征： 条件期望条件期望在模式识别中，经常以类别在模式识别中，经常以类别 作为条件，在这作为条件，在这种情况下随机矢量种情况下随机矢量 的条件期望矢量定义为的条件期望矢量定义为iE|(|)dniiiXXxp xxX551.3 随机矢量的描述随机矢量随机矢量 的自协方差矩阵表征各分量围绕的自协方差矩阵表征各分量围绕其均值的散布情况及各分量间的相关关

31、系，其均值的散布情况及各分量间的相关关系，其定义为：其定义为：XE()() XXXX2()() ( )d()nijn nXxxp xx (二二)随机矢量的数字特征：随机矢量的数字特征： 协方差矩阵协方差矩阵 561.3 随机矢量的描述571.3 随机矢量的描述581.3 随机矢量的描述( (二二) )随机矢量的数字特征：随机矢量的数字特征： 相关系数相关系数 )(2jjiiijijrjjiiij2由布尼亚科夫斯基不等式知由布尼亚科夫斯基不等式知: : 11ijrnnijrr)(相关系数矩阵定义为相关系数矩阵定义为 : :591.3 随机矢量的描述601.3 随机矢量的描述611.3 随机矢量的

32、描述621.3 随机矢量的描述631.4 正态分布641.4 正态分布（1 1）一维随机变量的正态分布）一维随机变量的正态分布kk651.4 正态分布661.4 正态分布（2 2）随机矢量的正态分布）随机矢量的正态分布 正态分布随机矢量正态分布随机矢量 的概率密度函数定义为：的概率密度函数定义为：),(21nXXXX)()(21exp|)2(1)(),(12/ 12/21xxxpxxxpnn)()(21exp|)2(1)(),(12/ 12/21xxxpxxxpnn671.4 正态分布222212222222121212211)(nnnnnnXXE681.4 正态分布（2 2）二维随机变量的正

33、态分布）二维随机变量的正态分布691.4 1.4 正态分布正态分布范例范例木板木板图象图象512512d=3长度长度纹理纹理亮度亮度 c=2松木松木 桦木桦木维数维数无限无限有限有限/很大很大R有限有限d不大不大c总结：模式识别过程dR无限模式采集模式采集模式空间模式空间特征提取特征提取/ /选择选择类型空间类型空间分类分类特征空间特征空间客观世界客观世界待识别对待识别对象象识别过程识别过程错误概率检测错误概率检测制定分类的制定分类的判决规则判决规则特征提取特征提取/选择选择方法校正方法校正学习过程学习过程采集方法校正采集方法校正已知对象已知对象预处理预处理71 试证明，对于正态分布，不相关与

34、试证明，对于正态分布，不相关与独立是等价的。独立是等价的。 试证明，多元正态随机矢量的线性试证明，多元正态随机矢量的线性变换仍为多元正态随机矢量。变换仍为多元正态随机矢量。1. 试证明，多元正态随机矢量试证明，多元正态随机矢量X的分量的分量的线性组合是一正态随机变量。的线性组合是一正态随机变量。 习题习题72模式识别主讲：主讲： 蔡宣平蔡宣平 教授教授 电话：电话： 7344173441（O O）,73442,73442（H H）E-mailE-mail：单位单位: : 电子科学与工程学院信息工程系电子科学与工程学院信息工程系73第二章第二章 聚类分析聚类分析 (Clustering Anal

35、ysis) 2.1 2.1 聚类分析的概念聚类分析的概念2.2 2.2 模式相似性测度模式相似性测度2.3 2.3 类的定义与类间距离类的定义与类间距离2.4 2.4 聚类的算法聚类的算法742.1 2.1 聚类分析的概念聚类分析的概念一、聚类分析的基本思想一、聚类分析的基本思想 相似的归为一类。相似的归为一类。 模式相似性的度量和聚类算法。模式相似性的度量和聚类算法。 无监督分类无监督分类（Unsupervised） 。二、特征量的类型二、特征量的类型 物理量物理量-(-(重量、长度、速度重量、长度、速度) ) 次序量次序量-(-(等级、技能、学识等级、技能、学识) ) 名义量名义量-(-(

36、性别、状态、种类性别、状态、种类) )第二章第二章 聚类分析聚类分析75三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。2.1 聚类分析的概念22112x1xb分类无效时的情况分类无效时的情况1.1.特征选取特征选取不当不当使分类无效。使分类无效。第二章第二章 聚类分析聚类分析76三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况分类无效时的情况2.2.特征选取特征选取不足不足可能使不同可能使不同类别的模式判为一类。类别的模式判为一类。

37、22112x1x33第二章第二章 聚类分析聚类分析77三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况分类无效时的情况3.3.特征选取特征选取过多过多可能无益反可能无益反而有害而有害, ,增加分析负担并使增加分析负担并使分析效果变差。分析效果变差。22112x1xb第二章第二章 聚类分析聚类分析78三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况分类无效时的情况4.4.量纲选取不当。量纲选取不当。

38、第二章第二章 聚类分析聚类分析79三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况分类无效时的情况4.4.量纲选取不当。量纲选取不当。第二章第二章 聚类分析聚类分析80三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况分类无效时的情况4.4.量纲选取不当。量纲选取不当。第二章第二章 聚类分析聚类分析81下列是一些动物的名称：下列是一些动物的名称：羊羊 （sheepsheep）狗狗 （dogdog）蓝

39、鲨（蓝鲨（blue sharkblue shark） 蜥蜴蜥蜴 （lizardlizard）毒蛇（毒蛇（viperviper）猫猫 （catcat）麻雀（麻雀（sparrowsparrow）海鸥海鸥 （seagullseagull）金鱼（金鱼（gold fishgold fish）绯鲵鲣（绯鲵鲣（red-mulletred-mullet）蛙蛙 （frogfrog）要对这些动物进行分类，则不同的特征有不同的分法：要对这些动物进行分类，则不同的特征有不同的分法：特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响第二章第二章 聚类分析聚类分析82特征选取不同对聚类结果的影响特征选取不同对聚类结

40、果的影响羊羊, , 狗狗, , 猫猫蓝鲨蓝鲨蜥蜴蜥蜴, ,毒蛇毒蛇, ,麻雀麻雀, ,海鸥海鸥, ,金鱼金鱼, ,绯鲵鲣绯鲵鲣, , 青蛙青蛙(a) 按繁衍后代的方式分按繁衍后代的方式分哺乳动物哺乳动物非哺乳动物非哺乳动物第二章第二章 聚类分析聚类分析83金鱼金鱼绯鲵鲣绯鲵鲣蓝鲨蓝鲨羊羊, ,狗狗, ,猫猫蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鸥海鸥 青蛙青蛙(b) 按肺是否存在分按肺是否存在分无肺无肺有肺有肺特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响第二章第二章 聚类分析聚类分析84青蛙青蛙羊羊, ,狗狗, ,猫猫 蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鸥海鸥 金鱼金鱼绯鲵鲣绯

41、鲵鲣 蓝鲨蓝鲨(c) 按生活环境分按生活环境分陆地陆地水里水里两栖两栖特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响第二章第二章 聚类分析聚类分析85蓝鲨蓝鲨金鱼金鱼绯鲵鲣绯鲵鲣蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鸥海鸥 青蛙青蛙羊羊, ,狗狗, ,猫猫(d) 按繁衍后代方式和肺是否存在分按繁衍后代方式和肺是否存在分非哺乳且有肺非哺乳且有肺哺乳且无肺哺乳且无肺哺乳且有肺哺乳且有肺非哺乳且无肺非哺乳且无肺特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响第二章第二章 聚类分析聚类分析86距离测度不同距离测度不同,聚类结果也不同聚类结果也不同数据的粗聚类是两类数据的粗聚类是两类,

42、细聚类为细聚类为4类类第二章第二章 聚类分析聚类分析87综上可见综上可见:选择什么特征？选择什么特征？选择多少个特征？选择多少个特征？选择什么样的量纲？选择什么样的量纲？选择什么样的距离测度？选择什么样的距离测度？ 这些对分类结果都会产生极大影响。这些对分类结果都会产生极大影响。第二章第二章 聚类分析聚类分析88聚类过程遵循的基本步骤 一、特征选择(feature selection) 尽可能多地包含任务关心的信息二、近邻测度(proximity measure) 定量测定两特征如何“相似”或“不相似”三、聚类准则（clustering criterion） 以蕴涵在数据集中类的类型为基础四、

43、聚类算法（clustering algorithm） 按近邻测度和聚类准则揭示数据集的聚类结构五、结果验证（validation of the results） 常用逼近检验验证聚类结果的正确性六、结果判定（interpretation of the results） 由专家用其他方法判定结果的正确性89聚类应用的四个基本方向一、减少数据 许多时候，当数据量N很大时，会使数据处理变得很费力。因此可使用聚类分析的方法将数据分成几组可判断的聚类m（mN）来处理，每一个类可当作独立实体来对待。从这个角度看，数据被压缩了。第二章第二章 聚类分析聚类分析90二、假说生成 在这种情况下，为了推导出数据性质

44、的一些假说，对数据集进行聚类分析。因此，这里使用聚类作为建立假说的方法，然后用其他数据集验证这些假说。聚类应用的四个基本方向第二章第二章 聚类分析聚类分析91聚类应用的四个基本方向三、假说检验 用聚类分析来验证指定假说的有效性。例如：考虑这样的假说例如：考虑这样的假说“大公司在海外投资大公司在海外投资”。要验证这个假说是否正确，就要对大公司和有要验证这个假说是否正确，就要对大公司和有代表性的公司按规模、海外活跃度、成功完成代表性的公司按规模、海外活跃度、成功完成项目的能力等进行聚类分析。从而来支持这个项目的能力等进行聚类分析。从而来支持这个假说。假说。第二章第二章 聚类分析聚类分析92四、基于

45、分组的预测 对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，对于一个未知模式，就可以用前面的聚类来确定是哪一类？聚类应用的四个基本方向例如：考虑被同种疾病感染的病人数据集。例如：考虑被同种疾病感染的病人数据集。先按聚类分析进行分类，然后对新的病人确定他先按聚类分析进行分类，然后对新的病人确定他适合的聚类，从而判断他病情。适合的聚类，从而判断他病情。第二章第二章 聚类分析聚类分析932.2 2.2 模式相似性测度模式相似性测度 用于描述各模式之间特征的相似程度用于描述各模式之间特征的相似程度 距距 离离 测测 度度 相相 似似 测测 度度 匹匹 配配 测测 度度第二章第二章 聚

46、类分析聚类分析942.2 2.2 模式相似性测度模式相似性测度一、距离测度一、距离测度( (差值测度差值测度) )测度基础：测度基础：两个矢量矢端的距离两个矢量矢端的距离测度数值：测度数值：两矢量各相应分量之差的函数两矢量各相应分量之差的函数。时，等号成立；时，等号成立；0),(yxd，当且仅当，当且仅当xy),(),(xydyxd),(),(),(yzdzxdyxd第二章第二章 聚类分析聚类分析952.2 2.2 模式相似性测度模式相似性测度常用的距离测度有：常用的距离测度有：1.1.欧氏欧氏(Euclidean)(Euclidean)距离距离 第二章第二章 聚类分析聚类分析962.2 模式

47、相似性测度4.明氏(Minkowski)距离 (2-2-4)2.绝对值距离(街坊距离或Manhattan距离) (2-2-2) 3.切氏(Chebyshev)距离 (2-2-3) 第二章第二章 聚类分析聚类分析972.2 模式相似性测度第二章第二章 聚类分析聚类分析982.2 模式相似性测度5.马氏(Mahalanobis)距离注意！马氏距离对一切非奇异线性变换都是不变的，这说明它不受特征量纲选择的影响，并且是平移不变的。 上面的V V的含义是这个矢量集的协方差阵的统计量，故马氏距离加入了对特征的相关性的考虑。第二章第二章 聚类分析聚类分析992.2 模式相似性测度第二章第二章 聚类分析聚类分

48、析100101现金识别例子现金识别例子( (欧氏平均距离欧氏平均距离) )数据样本介绍：数据样本介绍：10个文本文件个文本文件文件名：文件名：rmb00.txt rmb09.txt每个文件有每个文件有4个币种的数据，分别是：个币种的数据，分别是： 100圆、圆、50圆、圆、20圆、圆、10圆圆每个币种有新旧两种版本，每个币种有新旧两种版本，4个方向，故有个方向，故有8个数据块：个数据块：如如100圆的圆的8个数据块：个数据块： data100a,data100b,data100c,data100ddata100a,data100b,data100c,data100d老版老版 data100e,

49、data100f,data100g,data100hdata100e,data100f,data100g,data100h新版新版每个数据块有每个数据块有8个传感器数据：个传感器数据： 传感器传感器1，传感器，传感器2，传感器，传感器8每个传感器有每个传感器有60个采样数据：个采样数据： 数据数据1，数据，数据2，数据，数据60102现金识别例子现金识别例子Eucliden=15.000000Eucliden=15.000000Manhattan=33.000000Manhattan=33.000000Chebyshev=11.000000Chebyshev=11.000000Minkowsk

50、i=11.039449m=8Minkowski=11.039449m=8100100元元A A面第面第1 1个样本第个样本第1010点和点和2020点的距离点的距离X:X: (75, 76,101, 83,102, 96, 91, 82) (75, 76,101, 83,102, 96, 91, 82)Y:Y: (70, 74, 90, 76, 99, 96, 90, 86) (70, 74, 90, 76, 99, 96, 90, 86)X-Y: X-Y: 5, 2, 11, 7, 3, 0, 1, -45, 2, 11, 7, 3, 0, 1, -4距离测度距离测度rmbdis103现金识

51、别例子现金识别例子欧式平均距离欧式平均距离100a-100a:( 2.65,49.66) 24.41100a-100a:( 2.65,49.66) 24.41100a-100b:(16.37,55.87) 33.97100a-100b:(16.37,55.87) 33.97100a-100c:( 3.87,58.34) 29.41100a-100c:( 3.87,58.34) 29.41100a-100d:( 6.86,53.74) 33.04100a-100d:( 6.86,53.74) 33.04100a-100e:( 3.87,62.12) 27.51100a-100e:( 3.87,6

52、2.12) 27.51100a-100f:(13.60,67.61) 34.67100a-100f:(13.60,67.61) 34.67100a-100g:(11.40,68.56) 32.27100a-100g:(11.40,68.56) 32.27100a-100h:(11.27,68.61) 34.43100a-100h:(11.27,68.61) 34.43100a- 50a:(18.76,76.20) 40.72100a- 50a:(18.76,76.20) 40.72100a- 20a:(13.23,81.28) 42.87100a- 20a:(13.23,81.28) 42.8

53、7100a- 10a:(12.45,90.91) 54.99100a- 10a:(12.45,90.91) 54.99104现金识别例子现金识别例子100100圆圆A A面的马式矩阵面的马式矩阵SWSW为为: : 43.5 53.9 64.8 52.7 52.7 52.3 46.8 37.943.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 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

54、84.1 67.6 37.1 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 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.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 52.3 74.0 84.1 67.2 71.7 73.1 62.8 5

55、5.0 46.8 52.1 67.6 54.5 65.8 62.8 59.6 51.9 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 37.9 31.5 37.1 35.2 57.9 55.0 51.9 54.7105现金识别例子现金识别例子SWSW的逆矩阵为的逆矩阵为: : 0.3 -0.0 0.1 -0.1 -0.1 -0.1 -0.2 0.20.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

56、 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.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.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.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 -

57、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.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 0.2 0.2 0.4 -0.2 0.2 -1.0 -0.5 1.0106现金识别例子现金识别例子马式平均距离马式平均距离100a: ( 7.46, 80.05) 39.73100a: ( 7.46, 80.05) 39.73100b: (26.75, 179.86) 91.89100b: (26.75

58、, 179.86) 91.89100c: (14.50, 231.44) 103.76100c: (14.50, 231.44) 103.76100d: (11.69, 155.28) 78.58100d: (11.69, 155.28) 78.58100e: ( 5.65,2968.84) 247.42100e: ( 5.65,2968.84) 247.42100f: (39.19,2191.91) 108.10100f: (39.19,2191.91) 108.10100g: (10.68,2875.99) 265.16100g: (10.68,2875.99) 265.16100h: (

59、 9.41,2673.54) 107.56100h: ( 9.41,2673.54) 107.56 50a: (22.78, 221.07) 101.41 50a: (22.78, 221.07) 101.41 20a: (22.51, 343.26) 162.90 20a: (22.51, 343.26) 162.90 10a: (20.93, 975.67) 256.38 10a: (20.93, 975.67) 256.38107现金识别例子现金识别例子马式平均距离马式平均距离a: 39.73 101.41 162.90 256.38a: 39.73 101.41 162.90 256.

60、38b: 91.89 230.25 288.69 659.47b: 91.89 230.25 288.69 659.47c: 103.76 135.94 257.57 724.96c: 103.76 135.94 257.57 724.96d: 78.58 171.10 330.97 675.90d: 78.58 171.10 330.97 675.90e: 247.42 443.46 333.93 218.71e: 247.42 443.46 333.93 218.71f: 108.10 328.11 305.19 607.51f: 108.10 328.11 305.19 607.51g: