模式识别国家级精品课程讲义

《模式识别国家级精品课程讲义》由会员分享，可在线阅读，更多相关《模式识别国家级精品课程讲义（712页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、合概率密度函数定义为：的联合概率密度函数定义为： 491.3 随机矢量的描述501.3 随机矢量的描述x xp(x)p(x)(1xp)(2xp511.3 随机矢量的描述521.3 随机矢量的描述( (二二) )随机矢量的数字特征：随机矢量的数字特征：其中，其中， 的分量：的分量： 式中，式中， 是是 的第的第 个分量的边缘个分量的边缘密度。随机矢量密度。随机矢量 的均值矢量的均值矢量 的各分的各分量是相应的各随机分量的均值。量是相应的各随机分量的均值。531.3 随机矢量的描述( (二二) )随机矢量的数字特征：随机矢量的数字特征： 条件期望条件期望在模式识别中，经常以类别在模式识别中，经常以

30、类别 作为条件，在这作为条件，在这种情况下随机矢量种情况下随机矢量 的条件期望矢量定义为的条件期望矢量定义为541.3 随机矢量的描述随机矢量随机矢量 的自协方差矩阵表征各分量围绕的自协方差矩阵表征各分量围绕其均值的散布情况及各分量间的相关关系，其均值的散布情况及各分量间的相关关系，其定义为：其定义为：(二二)随机矢量的数字特征：随机矢量的数字特征： 协方差矩阵协方差矩阵 551.3 随机矢量的描述561.3 随机矢量的描述571.3 随机矢量的描述( (二二) )随机矢量的数字特征：随机矢量的数字特征： 相关系数相关系数 由布尼亚科夫斯基不等式知由布尼亚科夫斯基不等式知: : 相关系数矩阵定

31、义为相关系数矩阵定义为 : :581.3 随机矢量的描述591.3 随机矢量的描述601.3 随机矢量的描述611.3 随机矢量的描述621.4 正态分布631.4 正态分布（1 1）一维随机变量的正态分布）一维随机变量的正态分布641.4 正态分布651.4 正态分布（2 2）随机矢量的正态分布）随机矢量的正态分布 正态分布随机矢量正态分布随机矢量 的概率密度函数定义为：的概率密度函数定义为：661.4 正态分布671.4 正态分布（2 2）二维随机变量的正态分布）二维随机变量的正态分布681.4 1.4 正态分布正态分布69范例范例木板木板图象图象512512d=3长度长度纹理纹理亮度亮度

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

33、多元正态随机矢量。变换仍为多元正态随机矢量。3.试证明，多元正态随机矢量试证明，多元正态随机矢量X的分量的分量的线性组合是一正态随机变量。的线性组合是一正态随机变量。 习题习题71模式识别主讲主讲： 蔡宣平蔡宣平 教授教授 电话电话： 7344173441（O O）,73442,73442（H H）E-mailE-mail：单位单位: : 电子科学与工程学院信息工程系电子科学与工程学院信息工程系72第二章第二章 聚类分析聚类分析 (Clustering Analysis) 2.1 2.1 聚类分析的概念聚类分析的概念2.2 2.2 模式相似性测度模式相似性测度2.3 2.3 类的定义与类间距离

34、类的定义与类间距离2.4 2.4 聚类的算法聚类的算法732.1 2.1 聚类分析的概念聚类分析的概念一、聚类分析的基本思想一、聚类分析的基本思想 相似的归为一类。相似的归为一类。 模式相似性的度量和聚类算法。模式相似性的度量和聚类算法。 无监督分类无监督分类（Unsupervised） 。二、特征量的类型二、特征量的类型 物理量物理量-(-(重量、长度、速度重量、长度、速度) ) 次序量次序量-(-(等级、技能、学识等级、技能、学识) ) 名义量名义量-(-(性别、状态、种类性别、状态、种类) )第二章第二章 聚类分析聚类分析74三、方法的有效性三、方法的有效性 取决于分类算法和特征点取决于

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

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

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

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

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

40、章 聚类分析聚类分析84蓝鲨蓝鲨金鱼金鱼绯鲵鲣绯鲵鲣蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鸥海鸥 青蛙青蛙羊羊, ,狗狗, ,猫猫(d) 按按繁衍后代方式和肺是否存在繁衍后代方式和肺是否存在分分非哺乳且有肺非哺乳且有肺哺乳且无肺哺乳且无肺哺乳且有肺哺乳且有肺非哺乳且无肺非哺乳且无肺特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响第二章第二章 聚类分析聚类分析85距离测度不同距离测度不同,聚类结果也不同聚类结果也不同数据的粗聚类是两类数据的粗聚类是两类,细聚类为细聚类为4类类第二章第二章 聚类分析聚类分析86综上可见综上可见:选择什么特征？选择什么特征？选择多少个特征？选择多少个特征？选

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

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

43、 聚类分析聚类分析90聚类应用的四个基本方向三、假说检验 用聚类分析来验证指定假说的有效性。例如：考虑这样的假说例如：考虑这样的假说“大公司在海外投资大公司在海外投资”。要验证这个假说是否正确，就要对大公司和有要验证这个假说是否正确，就要对大公司和有代表性的公司按规模、海外活跃度、成功完成代表性的公司按规模、海外活跃度、成功完成项目的能力等进行聚类分析。从而来支持这个项目的能力等进行聚类分析。从而来支持这个假说。假说。第二章第二章 聚类分析聚类分析91四、基于分组的预测 对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，对于一个未知模式，就可以用前面的聚类来确定是哪一类？聚类应

44、用的四个基本方向例如：考虑被同种疾病感染的病人数据集。例如：考虑被同种疾病感染的病人数据集。先按聚类分析进行分类，然后对新的病人确定他先按聚类分析进行分类，然后对新的病人确定他适合的聚类，从而判断他病情。适合的聚类，从而判断他病情。第二章第二章 聚类分析聚类分析922.2 2.2 模式相似性测度模式相似性测度 用于描述各模式之间特征的相似程度用于描述各模式之间特征的相似程度 距距 离离 测测 度度 相相 似似 测测 度度 匹匹 配配 测测 度度第二章第二章 聚类分析聚类分析932.2 2.2 模式相似性测度模式相似性测度一、距离测度一、距离测度( (差值测度差值测度) )测度基础：测度基础：两

45、个矢量矢端的距离两个矢量矢端的距离测度数值：测度数值：两矢量各相应分量之差的函数两矢量各相应分量之差的函数。时，等号成立；时，等号成立；，当且仅当，当且仅当第二章第二章 聚类分析聚类分析942.2 2.2 模式相似性测度模式相似性测度常用的距离测度有：常用的距离测度有：1.1.欧氏欧氏(Euclidean)(Euclidean)距离距离 第二章第二章 聚类分析聚类分析952.2 模式相似性测度4.明氏(Minkowski)距离 (2-2-4)2.绝对值距离(街坊距离或Manhattan距离) (2-2-2) 3.切氏(Chebyshev)距离 (2-2-3) 第二章第二章 聚类分析聚类分析96

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

47、分别是：个币种的数据，分别是： 100圆、圆、50圆、圆、20圆、圆、10圆圆每个币种有新旧两种版本，每个币种有新旧两种版本，4个方向，故有个方向，故有8个数据块：个数据块：如如100圆的圆的8个数据块：个数据块： data100a,data100b,data100c,data100ddata100a,data100b,data100c,data100d老版老版 data100e,data100f,data100g,data100hdata100e,data100f,data100g,data100h新版新版每个数据块有每个数据块有8个传感器数据：个传感器数据： 传感器传感器1，传感器，传感器

48、2，传感器传感器8每个传感器有每个传感器有60个采样数据：个采样数据： 数据数据1，数据，数据2，数据，数据60101现金识别例子现金识别例子Eucliden=15.000000Eucliden=15.000000Manhattan=33.000000Manhattan=33.000000Chebyshev=11.000000Chebyshev=11.000000Minkowski=11.039449Minkowski=11.039449m=8m=8100100元元A A面第面第1 1个样本第个样本第1010点和点和2020点的距离点的距离X:X: (75, 76,101, 83,102, 9

49、6, 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距离测度距离测度rmbdis102现金识别例子现金识别例子欧式平均距离欧式平均距离100a-100a:( 2.65,49.66) 24.41100a-100a:( 2.65,49.66) 24.41100a-100b:(16.37,55.87) 33.971

50、00a-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,62.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:(

51、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.87100a- 10a:(12.45,90.91) 54.99100a- 10a:(12.45,90.91) 54.99103现金识别例子现金识别例子100100圆圆A A面的马式矩阵面的马式矩阵SWSW为为: : 43

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

53、.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 55.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

54、55.0 51.9 54.7 37.9 31.5 37.1 35.2 57.9 55.0 51.9 54.7104现金识别例子现金识别例子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 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.

55、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 -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 -

56、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.0105现金识别例子现金识别例子马式平均距离马式平均距离100a: ( 7.46, 80.05) 39.73100a: ( 7.46, 80.05) 39.73100b: (26.75, 179.86) 91.89100b: (26.75, 179.86) 91.89100c: (14.50, 231.44) 103.76100c: (14.50, 231.44) 103.76100d: (11.69, 155.28) 78.58100d: (11.6

57、9, 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: ( 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

58、: (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.38106现金识别例子现金识别例子马式平均距离马式平均距离a: 39.73 101.41 162.90 256.38a: 39.73 101.41 162.90 256.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 25

59、7.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: 265.16 956.58 818.83 348.42g: 265.16 956.58 818.83 348.42h: 107.56 339.64 387.10 628.88h: 107.56 339.64 387.

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

61、09现金识别例子现金识别例子100100圆圆A A面传感器面传感器1 1与其它各面的相似系数与其它各面的相似系数1102.2 模式相似性测度二、相似测度2.相关系数它实际上是数据中心化后的矢量夹角余弦。 (2-2-12)111现金识别例子现金识别例子100100圆圆A A面传感器面传感器1 1与其它各面的相关系数与其它各面的相关系数1122.2 模式相似性测度二、相似测度3.指数相似系数 (2-2-13)式中式中 为相应分量的协方差，为相应分量的协方差， 为矢量维数。为矢量维数。它不受量纲变化的影响。它不受量纲变化的影响。 113现金识别例子现金识别例子100100圆圆A A面传感器面传感器1

62、 1与其它各面的相关系数与其它各面的相关系数1142.2 模式相似性测度当特征只有两个状态（当特征只有两个状态（0 0，1 1）时，常用匹配测度。）时，常用匹配测度。0 0表示无此特征表示无此特征 1 1表示有此特征。故称之为表示有此特征。故称之为二值特征二值特征。 对于给定的对于给定的x x和和y y中的某两个相应分量中的某两个相应分量x xi i与与y yj j若若x xi i=1,y=1,yj j=1 =1 ，则称，则称 x xi i与与y yj j是是 (1-1)(1-1)匹配匹配；若若x xi i=1,y=1,yj j=0 =0 ，则称，则称 x xi i与与y yj j是是 (1-

63、0)(1-0)匹配；匹配；若若x xi i=0,y=0,yj j=1 =1 ，则称，则称 x xi i与与y yj j是是 (0-1)(0-1)匹配；匹配；若若x xi i=0,y=0,yj j=0 =0 ，则称，则称 x xi i与与y yj j是是 (0-0)(0-0)匹配。匹配。二、匹配测度二、匹配测度1152.2 模式相似性测度1162.2 模式相似性测度 三、匹配测度(1)Tanimoto测度测度117例例2.2.22.2.2 可以看出，它等于可以看出，它等于共同具有的特征数目共同具有的特征数目与分别与分别具有的特征种类总数之比。这里只考虑具有的特征种类总数之比。这里只考虑(1-1)

64、(1-1)匹配而匹配而不考虑不考虑(0-0)(0-0)匹配。匹配。设设则则2.2 模式相似性测度118现金识别例子现金识别例子100100圆圆A A面面与其它各面的匹配系数与其它各面的匹配系数TanimotoTanimoto1192.2 模式相似性测度 三、匹配测度(2) RaoRao测度测度注：注：(1-1)匹配特征数目和所选用的特征数目之比。匹配特征数目和所选用的特征数目之比。120现金识别例子现金识别例子100100圆圆A A面面与其它各面的匹配系数与其它各面的匹配系数RaoRao1212.2 模式相似性测度 三、匹配测度(3) (3) 简单匹配系数简单匹配系数注：上式分子为注：上式分子

65、为(1-1)匹配特征数目与匹配特征数目与(0-0)匹配特征匹配特征数目之和，分母为所考虑的特征数目。数目之和，分母为所考虑的特征数目。122现金识别例子现金识别例子100100圆圆A A面面与其它各面的匹配系数与其它各面的匹配系数SimpleSimple1232.2 模式相似性测度 三、匹配测度(4) Dice系数系数(5) Kulzinsky系数系数124现金识别例子现金识别例子100100圆圆A A面面与其它各面的匹配系数与其它各面的匹配系数dicedice125现金识别例子现金识别例子100100圆圆A A面面与其它各面的匹配系数与其它各面的匹配系数KulzinskyKulzinsky1

66、26作业作业P44: 2.1, 2.312723 类的定义与类间距离2.3.1 2.3.1 类的定义类的定义定义之定义之1 1 设集合设集合S S中任意元素中任意元素x xi i与与y yj j间的距离间的距离d dijij有有 d dijij h h其中其中h h为给定的阀值，称为给定的阀值，称S S对于阀值对于阀值h h组成一类。组成一类。 类的定义有很多种，类的划分具有人为规定性，这反类的定义有很多种，类的划分具有人为规定性，这反映在定义的选取及参数的选择上。一个分类结果的优劣最映在定义的选取及参数的选择上。一个分类结果的优劣最后只能根据实际来评价。后只能根据实际来评价。书中的其它定义方

67、法请大家自行参考学习书中的其它定义方法请大家自行参考学习12823 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法12923 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法式中式中 表示表示 和和 之间的距离。之间的距离。130现金识别例子现金识别例子100100圆圆A

68、A面面与其它各面的最小距离与其它各面的最小距离13123 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法式中式中 表示表示 和和 之间的距离。之间的距离。132现金识别例子现金识别例子100100圆圆A A面面与其它各面的最大距离与其它各面的最大距离13323 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法

69、平均距离法 离差平方和法离差平方和法p q k pqkpqDkqDklDkpDl 13423 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法np,nq分别为类分别为类 p和和 q的的样本个数样本个数13523 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法136现金识别例

70、子现金识别例子100100圆圆A A面面与其它各面的平均距离与其它各面的平均距离13723 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法分别为对应类的重心分别为对应类的重心类内离差平方和类内离差平方和 递推公式为递推公式为:138 最近距离法最近距离法 1/2 1/2 0 -1/2 最远距离法最远距离法 1/2 1/2 0 1/2 中间距离法中间距离法 1/2 1/2 -1/4 0 重心距离法重心距离法 0 平均距离法平均距离法

71、0 0 可变平均法可变平均法 0 可变法可变法 0 离差平方和法离差平方和法 013923 类的定义与类间距离2.3.3 2.3.3 聚类的准则函数聚类的准则函数判别分类结果好坏的一般标准：判别分类结果好坏的一般标准：类内距离小，类间距离大。类内距离小，类间距离大。 某些算法需要一个能对分类过程或分类结果某些算法需要一个能对分类过程或分类结果的优劣进行评估的准则函数。如果聚类准则函数的优劣进行评估的准则函数。如果聚类准则函数选择得好，聚类质量就会高。聚类准则往往是和选择得好，聚类质量就会高。聚类准则往往是和类的定义有关的，是类的定义的某种体现。类的定义有关的，是类的定义的某种体现。1402.3

72、.3 2.3.3 聚类的准则函数聚类的准则函数一、类内距离准则一、类内距离准则 设有待分类的模式集设有待分类的模式集 在某种相似性测在某种相似性测度基础上被划分为度基础上被划分为 类，类，类内距离准则函数类内距离准则函数 定义为定义为:( 表示表示 类的模式均类的模式均值矢量。值矢量。)(2-3-20)23 类的定义与类间距离14123 类的定义与类间距离142加权类内距离准则加权类内距离准则 : :(2-3-22)(2-3-23)式中，表示类内任两个模式距离 个组合数，所以表示类内表示类先验概率的估计频率。平方和，共有两模式间的均方距离。N为待分类模式总数，14323 类的定义与类间距离14

73、4加权类间距离准则加权类间距离准则: :对于两类问题，类间距离有时取(2-3-26)和的关系是(2-3-27)(2-3-25)14523 类的定义与类间距离146 的类内离差阵定义为的类内离差阵定义为 (2-3-28)(2-3-28)23 类的定义与类间距离式中式中 为类为类 的模式均值矢量的模式均值矢量 (2-3-29)(2-3-29)147148例例2.3 .1 证明：证明：23 类的定义与类间距离149 聚类的基本目的是使聚类的基本目的是使 或或 。利用线形代数有关矩阵的迹和行列式的性质。利用线形代数有关矩阵的迹和行列式的性质, ,可以可以定义如下定义如下4 4个聚类的准则函数个聚类的准

74、则函数: : 23 类的定义与类间距离15023 类的定义与类间距离 由它们的构造可以看出，为得到好的聚类由它们的构造可以看出，为得到好的聚类结果，应该使它们尽量的大。这类准则也大量结果，应该使它们尽量的大。这类准则也大量用在特征提取和选择中。用在特征提取和选择中。 15123 类的定义与类间距离J1= 7.60886 J2= 0.0010397J1= 7.60886 J2= 0.0010397J3= 15.6089 J4= 62.9116J3= 15.6089 J4= 62.9116用纸币数据计算获得的结果：用纸币数据计算获得的结果：152作业作业P44: 2.4, 2.5, 2.61532

75、4 聚类的算法 2.4.1 聚类的技术方案聚类的技术方案聚类分析有很多具体的算法聚类分析有很多具体的算法,有的比较简单有的比较简单,有的相对复杂和完善有的相对复杂和完善,但归纳起来就是三大类但归纳起来就是三大类:1、按最小距离原则简单聚类方法、按最小距离原则简单聚类方法2、按最小距离原则进行两类合并的方法、按最小距离原则进行两类合并的方法3、依据准则函数动态聚类方法、依据准则函数动态聚类方法15424 聚类的算法 (1) 简单聚类方法简单聚类方法 针对具体问题确定相似性阈值，将模式到各聚针对具体问题确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，当大于阈值时该模式类中心间的距离与阈值比较

76、，当大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离原则就作为另一类的类心，小于阈值时按最小距离原则将其分划到某一类中。将其分划到某一类中。这类算法运行中模式的类别及类的中心一旦确这类算法运行中模式的类别及类的中心一旦确定将不会改变。定将不会改变。15524 聚类的算法 首先视各模式自成一类首先视各模式自成一类, ,然后将距离最小的两然后将距离最小的两类合并成一类类合并成一类, ,不断地重复这个过程，直到成为不断地重复这个过程，直到成为两类为止。两类为止。(2) 按最小距离原则进行两类合并的方法按最小距离原则进行两类合并的方法这类算法运行中，类心不断地修正，但模式这类算法运行中，类心不

77、断地修正，但模式类别一旦指定后就不再改变，就是模式一旦划为类别一旦指定后就不再改变，就是模式一旦划为一类后就不再被分划开，这类算法也称为谱系聚一类后就不再被分划开，这类算法也称为谱系聚类法。类法。15624 聚类的算法 (3) 依据准则函数动态聚类法依据准则函数动态聚类法设定一些分类的控制参数，定义一个能表征聚设定一些分类的控制参数，定义一个能表征聚类结果优劣的准则函数，聚类过程就是使准则函类结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。数取极值的优化过程。算法运行中，类心不断地修正，各模式的类别算法运行中，类心不断地修正，各模式的类别的指定也不断地更改。这类方法有的指定也不断地

78、更改。这类方法有CC均值法、均值法、ISODATAISODATA法等。法等。15724 聚类的算法-简单聚类方简单聚类方法法 15824 聚类的算法-简单聚类方简单聚类方法法 15924 聚类的算法-简单聚类方法简单聚类方法 16024 聚类的算法-简单聚类方简单聚类方法法 这类算法的突出优点是算法简单。但聚类过程这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。类后也不再改变。算法特点算法特点:从算法的过程可以看出，该算法结果很大程度从算法的过程可以看出，该算法结果很大程度上依赖于距离门限上依赖于距

79、离门限T的选取及模式参与分类的次序。的选取及模式参与分类的次序。如果能有先验知识指导门限如果能有先验知识指导门限T的选取，通常可获得的选取，通常可获得较合理的效果。也可考虑设置不同的较合理的效果。也可考虑设置不同的T和选择不同和选择不同的次序，最后选择较好的结果进行比较。的次序，最后选择较好的结果进行比较。16124 聚类的算法-简单聚类方简单聚类方法法 简单聚类图简单聚类图例例162例例2.4.12.4.1：初始条件不同的简单聚类结果：初始条件不同的简单聚类结果初始中心不同门限不同样本顺序不同 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 10 9 8 10

80、 9 8 8 7 6 8 7 6 11 6 7 11 6 7 9 10 11 9 10 1116324 聚类的算法简单聚类法程简单聚类法程序序 simpleclusteringsimpleclustering16424 聚类的算法最大最小距离最大最小距离法法 16524 聚类的算法-最大最小距离最大最小距离法法 算法原理步骤算法原理步骤 选任一模式特征矢量作为第一个聚类中心例如，。作为第二个聚类中心。 从待分类矢量集中选距离最远的特征矢量166 计算未被作为聚类中心的各模式特征矢量与、之间的距离，并求出它们之中的最小值， 为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写

81、出来，因这并不影响算法的正确性。即167则相应的特征矢量作为第三个聚类中心，然后转至；否则，转至最后一步。 若 设存在个聚类中心，计算未被作为聚类中心,并算出如果，则否则，转至最后一步。的各特征矢量到各聚类中心的距离并转至；168 当判断出不再有新的聚类中心之后，将模式特中去，即计算当，则判。征矢量按最小距离原则分到各类这种算法的聚类结果与参数心的选取有关。如果没有先验知识指导和取，可适当调整和选取最合理的一种聚类。以及第一个聚类中的选，比较多次试探分类结果，16924 聚类的算法最大最小距离法最大最小距离法程程序序 maxminclusteringmaxminclustering17024

82、聚类的算法层次聚类法层次聚类法 (Hierarchical Clustering Method)(系统系统聚类法、聚类法、 谱系聚类法）谱系聚类法）按最小距离原则不断进行两类合并按最小距离原则不断进行两类合并 2.4.3 谱系聚类法谱系聚类法17124 聚类的算法层次聚类法层次聚类法 (Hierarchical Clustering Method)(系统系统聚类法、聚类法、 谱系聚类法）谱系聚类法）按最小距离原则不断进行两类合并按最小距离原则不断进行两类合并 算法思想算法思想 首先将首先将 N N 个模式视作各自成为一类，然后计算个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的

83、一对合并成一类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离，个新类，计算在新的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类再将距离最近的两类合并，直至所有模式聚成两类为止。为止。 2.4.3 谱系聚类法谱系聚类法17224 聚类的算法 2.4.3 谱系聚类法谱系聚类法17324 聚类的算法 2.4.3 谱系聚类法谱系聚类法174例2.4.3：如下图所示 1、设全部样本分为6类，2、作距离矩阵D(0)3、求最小元素：4、把1,3合并7=(1,3)4,6合并8=(4,6)5、作距离矩阵D(1)12345233144748552626

84、85913D(0)175例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)728238745522176n6 6、若合并的类数没有达到要求，转、若合并的类数没有达到要求，转3 3。否则停止。否则停止。n3 3、求最小元素：、求最小元素： n4 4、8,5,28,5,2合并合并, 9=, 9=（2,5,4,62,5,4,6）17717824 聚类的算法谱系聚类法谱系聚类法程序程序 Hierarchical clusteringclustering17924 聚类的算法最大距离

85、和层次聚类算法的一个共同特点是某最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后继的算法过程个模式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了。因此，这些方法在后继算法过程中也不再改变了。因此，这些方法效果一般不会太理想。效果一般不会太理想。 1802. 确定评估聚类质量的准则函数。1. 确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢为，协方差阵为，则模式和该类的与该类均矢的

86、马氏距离：距离平方为3. 确定模式分划及聚类合并或分裂的规则。24 聚类的算法动态聚类算法要动态聚类算法要点点18124 聚类的算法动态聚类的基本步动态聚类的基本步骤骤1.建立初始聚类中心，进行初始聚类；2.计算模式和类的距离，调整模式的类别；3.计算各聚类的参数，删除、合并或分裂一些聚类；4.从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止。18224 聚类的算法动态聚类的框图动态聚类的框图产生初始产生初始聚类中心聚类中心聚类聚类检验聚类检验聚类合理性合理性待分类模式待分类模式 分类结分类结果果合理合理再迭代再迭代/修改参数修改参数

87、不合理不合理183 条件及约定条件及约定 设待分类的模式特征矢量集为：设待分类的模式特征矢量集为：类的数目类的数目C C是事先取定的。是事先取定的。24 聚类的算法 2.4.3 动态聚类法动态聚类法C-均值法均值法 算法思想算法思想 该方法该方法取定取定 C C个类别个类别和选取和选取 C C个初始聚类中个初始聚类中心心，按最小距离原则将各模式分配到按最小距离原则将各模式分配到 C C类中的某类中的某一类，之后不断地一类，之后不断地计算类心和调整各模式计算类心和调整各模式的类别，的类别，最终使各模式到其判属类别中心的距离平方之和最终使各模式到其判属类别中心的距离平方之和最小。最小。18424

88、聚类的算法 2.4.3 动态聚类法动态聚类法C-均值法均值法18524 聚类的算法 2.4.3 动态聚类法动态聚类法C-均值法均值法186选代表点选代表点初始分类初始分类分类合理否分类合理否4.4.动态聚类框图动态聚类框图24 聚类的算法 2.4.3 动态聚类法动态聚类法C-均值法均值法最终分类最终分类Y修改分类修改分类N187例例2.4.2 2.4.2 使用聚类算法实现图像分割使用聚类算法实现图像分割在散射图上形成了两个聚类，利用模式识别的在散射图上形成了两个聚类，利用模式识别的方法将其分开，就实现了图象的分割。方法将其分开，就实现了图象的分割。188 例例2.4.32.4.3：已知有已知有

89、2020个样本，每个样本有个样本，每个样本有2 2个特征，数据个特征，数据分布分布如下图如下图, ,使用使用C C均值法实现样本分类（均值法实现样本分类（C=2C=2）。）。第一步第一步：令：令C=2C=2，选初始聚类中心为，选初始聚类中心为样本序号样本序号x x1 1x x2 2x x3 3x x4 4x x5 5x x6 6x x7 7x x8 8x x9 9x x1010特征特征x x1 10 01 10 01 12 21 12 23 36 67 7特征特征x x2 20 00 01 11 11 12 22 22 26 66 6x11x12x13x14x15x16x17x18x19x20

90、8678978989677778889918919000第二步第二步：000）（-10100）（-10001）（-所以因为-所以因为同理, 12,21=-=-.20652065都属于、离计算出来，判断与第二个聚类中心的距、同样把所有因此分为两类：),.,()1(),()1(205422311=18,221=NNGG二、一、192193194n第三步：第三步：更新聚类中心更新聚类中心195196n第四步：第四步：n第二步：第二步：n第三步第三步：更新聚类中心：更新聚类中心197198clusteringclustering24 聚类的算法 2.4.3 动态聚类法动态聚类法C-均值法程序均值法程序

91、199作业作业P45: 2.7, 2.820024 聚类的算法 2.4.3 动态聚类法动态聚类法C-均值法均值法关于关于C-C-均值法收敛性的分析均值法收敛性的分析20124 聚类的算法 2.4.3 动态聚类法动态聚类法C-均值法均值法当模式分布呈现类内团聚状，当模式分布呈现类内团聚状，C-C-均值算法是能均值算法是能达到很好的聚类结果，故应用较多。从算法的迭代达到很好的聚类结果，故应用较多。从算法的迭代过程看，过程看，C-C-均值算法均值算法是能使各模式到其所判属的类是能使各模式到其所判属的类别中心别中心距离距离( (平方平方) )之和为最小之和为最小的最佳聚类。的最佳聚类。20224 聚类

92、的算法 2.4.3 动态聚类法动态聚类法C-C-均值法的改进均值法的改进 在类别数未知的情况下，可使类数在类别数未知的情况下，可使类数C C由较小值逐步由较小值逐步增加，对于每个选定的增加，对于每个选定的C C分别使用该算法。显然准则函分别使用该算法。显然准则函数数J J是随是随C C的增加而单调减少。的增加而单调减少。 C C的调整的调整 作一条作一条C C一一J J曲线，其曲率变化的最大点对应的类曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。数是比较接近最优的类数。 在增加过程中，总会出现使本来较密集的类再拆在增加过程中，总会出现使本来较密集的类再拆开的情况，此时开的情况，此时J

93、 J虽减小，但减小速度将变缓。如果作虽减小，但减小速度将变缓。如果作一条一条C C一一J J曲线，其曲率变化的最大点对应的类数是比曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。然而在许多情况下，曲线并无明较接近最优的类数。然而在许多情况下，曲线并无明显的这样的点。显的这样的点。20324 聚类的算法 2.4.3 动态聚类法动态聚类法C-C-均值法的改进均值法的改进 初始聚类中心的选取初始聚类中心的选取 凭经验选择初始类心。凭经验选择初始类心。 将模式随机地分成将模式随机地分成C C类，计算每类中心，以其类，计算每类中心，以其作为初始类心。作为初始类心。 （最大密度最大密度），求以每个

94、特征点为球心、某一），求以每个特征点为球心、某一正数正数d d0 0为半径的球形域中特征点个数，这个数称为半径的球形域中特征点个数，这个数称为该点的为该点的密度密度。选取密度最大的特征点作为第一。选取密度最大的特征点作为第一个初始类心个初始类心Z Z1 1，然后在与，然后在与Z Z1 1大于某个距离大于某个距离d d的那些的那些特征点中选取具有特征点中选取具有“最大最大”密度密度的特征点作为第的特征点作为第二个初始类心二个初始类心Z Z2 2 ，如此进行，选取，如此进行，选取C C个初始聚类个初始聚类中心。中心。20424 聚类的算法 2.4.3 动态聚类法动态聚类法C-C-均值法的改进均值法

95、的改进 初始聚类中心的选取初始聚类中心的选取 用相距最远的用相距最远的C C个特征点作为初始类心。具体个特征点作为初始类心。具体地讲，是按前述的最大最小距离算法求取地讲，是按前述的最大最小距离算法求取C C个初始个初始聚类中心。聚类中心。 当当N N较大时，先随机地从较大时，先随机地从N N个模式中取出一部分个模式中取出一部分模式用谱系聚类法聚成模式用谱系聚类法聚成C C类，以每类的重心作为初类，以每类的重心作为初始类心。始类心。 设已标准化的待分类模式集为设已标准化的待分类模式集为 希望将它们分为希望将它们分为C C类。类。 205 设已标准化的待分类模式集为设已标准化的待分类模式集为 希望

96、将它们分为希望将它们分为C C类。类。 设设: :计算计算: :显然显然0 iC，若，若 i最接近整数最接近整数j，则把，则把xi分划至中分划至中 j。对所有样本都实行上述处理，就可实现初始分类，对所有样本都实行上述处理，就可实现初始分类，从而产生初始聚类中心。从而产生初始聚类中心。20624 聚类的算法 2.4.3 动态聚类法动态聚类法C-C-均值法的改进均值法的改进 用类核代替类心用类核代替类心 前面的算法存在一个不足，即只用一个聚类前面的算法存在一个不足，即只用一个聚类中心点作为一类的代表，但一个点往往不能充分中心点作为一类的代表，但一个点往往不能充分地反映该类的模式分布结构，从而损失了

97、很多有地反映该类的模式分布结构，从而损失了很多有用的信息。用的信息。当类的分布不是球状或近似球状时，当类的分布不是球状或近似球状时，这种算法很难有较好的效果。这种算法很难有较好的效果。此时，可用类核代替类心，类核此时，可用类核代替类心，类核可以是一个可以是一个函数、一个点集或其他适当的模型。函数、一个点集或其他适当的模型。比如前面我比如前面我们讲过的们讲过的马式距离马式距离。207(3) (3) 动态聚类法动态聚类法ISODATA算法算法(Iterative Self-Organizing Data Analysis Techniques Algorithm 迭代自组织数据分析迭代自组织数据分

98、析) 特点：特点：启发性推理、分析监督、控制聚类结构及人机启发性推理、分析监督、控制聚类结构及人机交互。交互。算法思想：算法思想：在每轮迭代过程中，样本重新调整类别之后计在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地是两类合并为一类还是一类分裂为两类，不断地“自自组织组织”，以达到在各参数满足设计要求条件下，使各，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。模式到其类心的距离平方和最小。208ISODATA算法原理步骤算法原理步骤 预置预置 设

99、定聚类分析控制参数：设定聚类分析控制参数：= =预期的类数，预期的类数，= =每一类中允许的最少模式数目，每一类中允许的最少模式数目，= =初始聚类中心个数初始聚类中心个数( (可以不等于可以不等于c)c)，= =类内各分量分布的距离标准差上界，类内各分量分布的距离标准差上界，( (分裂用分裂用) )= =两类中心间的最小距离下界，两类中心间的最小距离下界，( (合并用合并用) )= =在每次迭代中可以合并的类的最多对数，在每次迭代中可以合并的类的最多对数，= =允许的最多迭代次数。允许的最多迭代次数。209ISODATA算法原理步骤算法原理步骤 210ISODATA算法原理步骤算法原理步骤

100、211ISODATA算法原理步骤算法原理步骤 计算各类的中心计算各类的中心 计算分类后的参数计算分类后的参数: :各类中心、类内平均距离及总各类中心、类内平均距离及总体平均距离。体平均距离。 计算各类中模式到类心的平均距离计算各类中模式到类心的平均距离 计算各个模式到其类内中心的总体平均距离计算各个模式到其类内中心的总体平均距离212ISODATA算法原理步骤算法原理步骤 213ISODATA算法原理步骤算法原理步骤 计算各类类内距离的标准差矢量计算各类类内距离的标准差矢量式中，式中， 为分量编号，为分量编号， 为类的编号，为类的编号， 为矢量维数，为矢量维数， 是是 的第的第 个分量，个分量

101、， 是是 的第的第 个分量。个分量。214ISODATA算法原理步骤算法原理步骤 215ISODATA算法原理步骤算法原理步骤 216ISODATA算法原理步骤算法原理步骤 217ISODATA算法原理步骤算法原理步骤 218219ISODATA算法举例算法举例( (二维二维) )(1)初始值设定初始值设定:类间距离类间距离上限上限距离标准距离标准差上界差上界最少模最少模式数目式数目合并的合并的类的最类的最多对数多对数220ISODATA算法举例算法举例(2)聚类聚类(只有一个中心只有一个中心):221ISODATA算法举例算法举例(3)(3) 因因 , 无合并无合并:(4) 计算聚类中心、计

102、算聚类中心、类内平均距离和总类内平均距离和总的平均距离。的平均距离。 222ISODATA算法举例算法举例(5)(5)因不是最后一步迭因不是最后一步迭代，且代，且 ，转至，转至 (6)求求 的标准差矢量的标准差矢量 223ISODATA算法举例算法举例(7)(7) 算得算得 (6) 因因 且且 将将 分裂成分裂成两类，取两类，取 ，则则 且且 转转(2)224ISODATA算法举例算法举例(2)聚类聚类(两个中心两个中心):(3)(3) 因因 , 无合并无合并:225ISODATA算法举例算法举例(4) 计算聚类中心、计算聚类中心、类内平均距离和总类内平均距离和总的平均距离。的平均距离。 (5

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

104、算结果与前一次迭代结果相同。(7)(8) ,分裂条件不满足，转至分裂条件不满足，转至。(11) ，无新的变化，无新的变化， ，转至，转至。 (6) 计算计算 和和 的标准差矢量的标准差矢量(5) 没有任一种情况被满足，到没有任一种情况被满足，到。(9) 与前一次迭代结果相同，与前一次迭代结果相同，(10) 无合并发生。无合并发生。228 与前一次迭代结果相同。与前一次迭代结果相同。 因是最后一次迭代，令因是最后一次迭代，令 ，转至，转至。 ，同前。，同前。 因因 ，无合并发生。，无合并发生。 因是最后一次迭代因是最后一次迭代, 结束。结束。229StartStart输入样本数据，置输入样本数据

105、，置c; Nc; Nc c ; ; 选初始类心选初始类心z zj j ，j=1,2,.Nj=1,2,.Nc c(1)(1)置控制参数：置控制参数： n n , , s s , , D D, , , L , I , L , I(3)(3)合并判决：合并判决： n nj j s s) ) (d(dj jd)d) (n(nj j2(2( n n+1)+1) NNc cc/2c/2(6)(6)计算各类类内距离的标准差矢量计算各类类内距离的标准差矢量(7)(7)找出最大分量找出最大分量(10)(10)合并处理合并处理(11)(11)结束判决：结束判决：I Ip p I I(9)(9)计算各类对类间距离计

106、算各类对类间距离N NEndY YNc = Nc + 1I Ip p = I = Ip p + 1 + 1(8)(8)分裂处理分裂处理Y YN NY Y转转修修改改参参数数修改参数否转转重重新新聚聚类类N N232StartStart输入样本数据，置输入样本数据，置c; Nc; Nc c ; ; 选初始类心选初始类心z zj j ，j=1,2,.Nj=1,2,.Nc c(1)(1)置控制参数：置控制参数： n n , , s s , , D D, , , L , I , L , I(2)(2)聚类：聚类：if dif dil il = minD(x= minD(xi i, z, z1 1),

107、), D(xD(xi i, z, z2 2),), D(x, D(xi i, z, zNcNc) then x) then xi il l(3)(3)合并判决：合并判决： n nj j 00 。则此。则此模式模式X X就无法作出确切的判决。如图就无法作出确切的判决。如图另一种情况是另一种情况是IR2IR2区域，区域，判别函数都为负值。判别函数都为负值。IR1IR1，IR2IR2，IR3IR3，IR4IR4。都为。都为不确定区域。不确定区域。2471 1、第一种情况（续）第一种情况（续）解：解： 三个判别边界分别为：三个判别边界分别为：2481、第一种情况（续）第一种情况（续）结论：结论： 因为

108、因为所以它属于所以它属于2 2类。类。2491 1、第一种情况（续）第一种情况（续）2502512、第二种情况（续）第二种情况（续）多类问题图例多类问题图例（第二种情况）（第二种情况）252253d12(x) = - d21(x) = x1 x2 + 5 = 0d d1212(x)(x)为正为正两分法例题图示两分法例题图示0 1 2 3 4 5 6 7 8 9987654321d d2121(x)(x)为正为正254d d1212(x)(x)为正为正两分法例题图示两分法例题图示0 1 2 3 4 5 6 7 8 9987654321d d2121(x)(x)为正为正d d2323(x)= -(

109、x)= -d d3232(x)= (x)= x x1 1+ +x x2 2= 0= 0d d3232(x)(x)为正为正d d2323(x)(x)为正为正255d d1212(x)(x)为正为正两分法例题图示两分法例题图示0 1 2 3 4 5 6 7 8 9987654321d d2121(x)(x)为正为正d d3232(x)(x)为正为正d d2323(x)(x)为正为正d d1313(x)= -(x)= -d d3131(x)= (x)= x x1 1+3 = 0+3 = 0d d3131(x)(x)为正为正d d1313(x)(x)为正为正256 1 1类判别区域类判别区域 d d1

110、212(x)0(x)0 d d1313(x)0(x)0 2 2类判别区域类判别区域 d d2121(x)0(x)0 d d2323(x)0(x)0d d1212(x)(x)为正为正两分法例题图示两分法例题图示0 1 2 3 4 5 6 7 8 9987654321d d2121(x)(x)为正为正d d3232(x)(x)为正为正d d2323(x)(x)为正为正d d3131(x)(x)为正为正d d1313(x)(x)为正为正 3 3类判别区域类判别区域 d d3131(x)0(x)0 d d3232(x)0(x)0IR2572583、第三种情况（续）第三种情况（续）多类问题图例多类问题图

111、例（第三种情况）（第三种情况）259。260上述三种方法小结上述三种方法小结: 方法方法判别函数的数目和方法判别函数的数目和方法相同，但没有不相同，但没有不确定区，分析简单，是最常用的一种方法。确定区，分析简单，是最常用的一种方法。时，时，法比法比法需要更多法需要更多当当的判别函数式，这是一个缺点。的判别函数式，这是一个缺点。类与其余的类与其余的开，而开，而法是将法是将类和类和类分开，显然类分开，显然法是将法是将但是但是类区分类区分法使模式更容易线性可分，这是它的优点。法使模式更容易线性可分，这是它的优点。2613.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及

112、解空间 第三章第三章 判别域代数界面方程法判别域代数界面方程法262此方程表示一超平面此方程表示一超平面 。它有以下。它有以下三个性质三个性质: :n(1)(1)系数矢量系数矢量 ，是该平面的法矢量。是该平面的法矢量。n(2)(2)判别函数判别函数 的绝对值正比于的绝对值正比于 到超到超平面平面 的距离。的距离。n(3)(3)判别函数值的正负表示出特征点位于哪个判别函数值的正负表示出特征点位于哪个半空间中。半空间中。3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 第三章第三章 判别域代数界面方程法判别域代数界面方程法263图图3.3.1 3.3.1 点

113、面距离及界面的正负侧示意图点面距离及界面的正负侧示意图2x1xo+-0)(=xdrnrprpxrr-264265266267证明：判别函数值的正负表示出特征点位于哪个证明：判别函数值的正负表示出特征点位于哪个半空间中。半空间中。268背向的半空间中时，背向的半空间中时，当当在在这说明判别函数值的正负表示出特征点位于这说明判别函数值的正负表示出特征点位于哪个半空间中，或者换句话说，表示特征点位于哪个半空间中，或者换句话说，表示特征点位于界面的哪一侧。界面的哪一侧。和和，故，故同号。同号。由于由于在在指向的半空间中时，指向的半空间中时，即即269例例3.3.13.3.1：利用判别函数的鉴别意义，试

114、分析：利用判别函数的鉴别意义，试分析d(xd(x1 1,x,x2 2) )x x1 1+x+x2 2+1+1。d(x1,x2)d(x1,x2)0 0 -1-12703.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间271(2) (2) 解矢量解矢量3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间272(2) (2) 解矢量解矢量3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴

115、别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间2733.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间274(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0 ，w1。w0w1275(3) (3) 解空间解空间3.3.2权空间、

116、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0 ，w1。w0w1276(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开

117、的区分开的w0 ，w1。w0w1277(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0 ，w1。w0w1278(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一

118、维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0 ，w1。w0w1279(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间 先看一个简先看一个简单的情况。设一单的情况。设一维数据维数据1，2属于属于 1, -1，-2属属于于 2 求将求将 1和和 2区分开的区分开的w0 ，w1。w0w1280(3) (3) 解空间解空间3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判

119、别函数值的鉴别意义、权空间及解空间2813.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间每一个训练模式都对解区提供一个约束，训练每一个训练模式都对解区提供一个约束，训练模式越多，解区的限制就越多，解区就越小，就越模式越多，解区的限制就越多，解区就越小，就越靠近解区的中心，解矢量靠近解区的中心，解矢量 就越可靠，由它构就越可靠，由它构造的判别函数错分的可能性就越小。造的判别函数错分的可能性就越小。282(4) (4) 余量余量3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数

120、值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间283(4) (4) 余量余量3.3.2权空间、解矢量与解空间权空间、解矢量与解空间3.3 3.3 判别函数值的鉴别意义、权空间及解空间判别函数值的鉴别意义、权空间及解空间引入了余量可有效地避免量测的误差、引入引入了余量可有效地避免量测的误差、引入的误差以及某些算法求得的解矢量收敛于解区的的误差以及某些算法求得的解矢量收敛于解区的边界上，从而提高了解的可靠性。边界上，从而提高了解的可靠性。284设一设一3 3类问题有如下判决函数类问题有如下判决函数d d1 1(x) = - x(x) = - x1 1d d2 2(x) = x(x

121、) = x1 1 + x + x2 2 -1 -1d d3 3(x) = x(x) = x1 1 - x - x2 2 -1 -1试画出下列各种情况的判决边界及各类的区域：试画出下列各种情况的判决边界及各类的区域：（1 1）满足）满足3.4.23.4.2节中的第一种情况；节中的第一种情况；（2 2）满足）满足3.4.23.4.2节中的第二种情况节中的第二种情况, , 且令且令 d d1212(x)=d(x)=d1 1(x)(x)，d d1313(x)=d(x)=d2 2(x)(x)，d d2323(x)=d(x)=d3 3(x)(x)；（3 3）满足）满足3.4.23.4.2节中的第三种情况。

122、节中的第三种情况。作业作业2853.4 Fisher3.4 Fisher线性判别线性判别 第三章第三章 判别域代数界面方程法判别域代数界面方程法286二维模式向一维空间投影示意图二维模式向一维空间投影示意图uroxy287二维模式向一维空间投影示意图二维模式向一维空间投影示意图uroxy288二维模式向一维空间投影示意图二维模式向一维空间投影示意图oxyoxy289（1)1)求解求解FishFish准则函数准则函数290291类间离差度为：类间离差度为：292并使其最大并使其最大, ,上式称为上式称为FisherFisher准则函数准则函数。293利用二次型关于矢量求导的公式可得：利用二次型关

123、于矢量求导的公式可得：（2) 2) 求解求解FisherFisher最佳鉴别矢量最佳鉴别矢量令令可得：可得：294295n上式右边后两项因子的乘积为一标量，上式右边后两项因子的乘积为一标量，令其为令其为 ，于是可得，于是可得n式式中中 为为一一标标量量因因子子，其其不不改改变变轴轴的的方方向，可以取为向，可以取为1,于是有于是有296此时的此时的 可使可使Fisher准则函数取最大值，即是准则函数取最大值，即是n 维维空间到一维空间投影轴的最佳方向，由空间到一维空间投影轴的最佳方向，由和和JF 最大值为最大值为:297即即称称为为Fisher变换函数变换函数J JF F=298 由于变换后的模

124、式是一维的，因此判别界面实际由于变换后的模式是一维的，因此判别界面实际上是各类模式所在轴上的一个点，所以可以根据训练上是各类模式所在轴上的一个点，所以可以根据训练模式确定一个阈值模式确定一个阈值 y yt t，于是，于是FisherFisher判别规则判别规则为为: : （3) 3) 求解求解FisherFisher判别函数判别函数判别阈值可取两个类心在判别阈值可取两个类心在u u方向上轴的投影连线的方向上轴的投影连线的中点作为阈值，即中点作为阈值，即: :299300（7 7） 计算计算 。（8 8） 计算计算yt 。（9 9） 对未知模式对未知模式x判定模式类。判定模式类。301以以100

125、100元元A A面数据和面数据和5050元元A A面数据为例面数据为例100100元元A A面面:(64,76,99,84,98,95,88,83),:(64,76,99,84,98,95,88,83),5050元元A A面面:(65,67,82,80,89,94,86,92),:(65,67,82,80,89,94,86,92),N N1 1=N=N2 2=60=60算得算得: :m m1 1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m m2 2=(59.2,55.5

126、,81.9,63.9,95.1,91.0,91.1,86.5)=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)302m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91.0, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91.0, 91.1, 86.5) )303m m1 1=(=(6

127、9.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5) )304m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4

128、) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5) )305m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91,

129、91.1, 86.5) )306307308 利用给定的一个样本数据编写利用给定的一个样本数据编写100100元元B B面与面与5050元元A A面的面的FisherFisher判别门限的程序，并用另一个样本数据判别门限的程序，并用另一个样本数据验证之。验证之。上机练习上机练习3093.5 一次准则函数及梯度下降法一次准则函数及梯度下降法3.5.1 感知感知器算法器算法(Perceptron Approach)任选一初始增广权矢量任选一初始增广权矢量用训练样本检验分类是否正确用训练样本检验分类是否正确对所有训练样本都正确分类？对所有训练样本都正确分类？YesYesENDENDYesYesNoN

130、o对权值进行校正对权值进行校正NoNo感知器算法流程图感知器算法流程图流程:3103.5 一次准则函数及梯度下降法一次准则函数及梯度下降法3.5.1 感知感知器算法器算法(Perceptron Approach)311 (3)调整增广权矢量，规则是调整增广权矢量，规则是 - 如果如果 和和 ，则，则 - 如果如果 和和 ，则，则 - 如果如果 和和 ， 或或 和和 ，则，则 (4)如果如果k wx wj jx (x ( j j i)i)因此判别规则是因此判别规则是 若若 d di i(x) d(x) dj j(x) (x) j j i i 则判则判x xi i 第三章第三章 判别域代数界面方程

131、法判别域代数界面方程法326(1) (1) 赋初值赋初值, ,分别给分别给c c个权矢量个权矢量w wi i(i=1,2,c)(i=1,2,c)赋任意的赋任意的初值，选择正常数初值，选择正常数 ，置步数，置步数k=1k=1。算法步骤：算法步骤：(2) (2) 输入已知类别的增广训练模式输入已知类别的增广训练模式x xk k，计算，计算c c个判别函数个判别函数 d di i(x(xk k) = w) = wi ix xk k (i=1,2,c) (i=1,2,c)(3) (3) 修正权矢量，修正规则是：修正权矢量，修正规则是：if (xif (xk ki i) and (d) and (di

132、i(x(xk k)d)dj j(x(xk k) () ( j j i) theni) then w wi i(k+1) = w(k+1) = wi i(k) (i=1,2,c) (k) (i=1,2,c) (正确分类正确分类) ) if (xif (xk ki i) and (d) and (di i(x(xk k) ) d dl l(x(xk k) (l) (l i) theni) then w wi i(k+1) = w(k+1) = wi i(k)+ (k)+ x xk k w wl l(k+1) = w(k+1) = wl l(k)- (k)- x xk kw wj j(k+1) =

133、w(k+1) = wj j(k) (k) ( j j i,l) i,l) 327(1) (1) 赋初值赋初值, ,分别给分别给c c个权矢量个权矢量w wi i(i=1,2,c)(i=1,2,c)赋任意的赋任意的初值，选择正常数初值，选择正常数 ，置步数，置步数k=1k=1。算法步骤：算法步骤：(2) (2) 输入已知类别的增广训练模式输入已知类别的增广训练模式x xk k，计算，计算c c个判别函数个判别函数 d di i(x(xk k) = w) = wi ix xk k (i=1,2,c) (i=1,2,c)(4) if kN ,(4) if kN ,令令k=k+1,k=k+1,返至返至

134、；if k=Nif k=N，检验判别函数是否对都能正确分类，若是，检验判别函数是否对都能正确分类，若是，结束；否则，令结束；否则，令k=1k=1，返至，返至。(3) (3) 修正权矢量。修正权矢量。328例例题题:已已知知训训练练样样本本(0,0)T1，(1,1)T2 ，(-1,1)T3, 试求解向量试求解向量w1、w2和和w3。 （2 2）运运用用感感知知器器训训练练算算法法。置置k=1k=1，增增量量 =1=1，赋赋初初值值：w1 1=(0,0,0)=(0,0,0)T T, , w2 2=(0,0,0)=(0,0,0)T T, , w3 3=(0,0,0)=(0,0,0)T T, ,进行迭

135、代运算：进行迭代运算：解解:（1 1）训练样本分量增广化。将训练样本变成增广训）训练样本分量增广化。将训练样本变成增广训练模式：练模式：x1 1=(0,0,1)=(0,0,1)T T, , x2 2=(1,1,1)=(1,1,1)T T, , x3 3=(-1,1,1)=(-1,1,1)T T, , 这里的下标恰是所属类别，各类样本不需符号规这里的下标恰是所属类别，各类样本不需符号规范化。范化。329例例题题:已已知知训训练练样样本本(0,0)T1，(1,1)T2 ，(-1,1)T3, 试求解向量试求解向量w1、w2和和w3。 k=1,k=1,xk k= =x1 11 1, ,因为因为d d1

136、 1( (x1 1)=d)=d2 2( (x1 1)=0)=0，d d1 1( (x1 1)=d)=d3 3( (x1 1)=0)=0，错错分，所以分，所以: : w1 1(2)=(2)=w1 1(1)+ (1)+ x1 1=(0,0,1)=(0,0,1)T T w2 2(2)=(2)=w2 2(1)- (1)- x1 1=(0,0,-1)=(0,0,-1)T T w3 3(2)=(2)=w3 3(1)- (1)- x1 1=(0,0,-1)=(0,0,-1)T Tk=2,xk=2,xk k=x=x2 22 2, ,因为因为d d2 2(x(x2 2)=-1d)=-1d1 1(x(x2 2)=

137、1)=1，d d2 2(x(x2 2)=d)=d3 3(x(x2 2)=-1)=-1，错分，错分，所以所以 w w1 1(3)=w(3)=w1 1(2)- x(2)- x2 2=(-1,-1, 0)=(-1,-1, 0)T T w w2 2(3)=w(3)=w2 2(2)+ x(2)+ x2 2=( 1, 1, 0)=( 1, 1, 0)T T w w3 3(3)=w(3)=w3 3(2)- x(2)- x2 2=(-1,-1,-2)=(-1,-1,-2)T T330例例题题:已已知知训训练练样样本本(0,0)T1，(1,1)T2 ，(-1,1)T3, 试求解向量试求解向量w1、w2和和w3。

138、 k=3,xk=3,xk k=x=x3 33 3, ,因为因为d d3 3(x(x3 3)=-2d)=-2d)=0d1 1(x(x2 2)=-2)=-2，d d2 2(x(x2 2)=0d)=0d3 3(x(x2 2)=-4)=-4，正确，正确，所以所以 w w1 1(6)=w(6)=w1 1(5)=( 0,-2, 0)(5)=( 0,-2, 0)T T w w2 2(6)=w(6)=w2 2(5)=( 2, 0,-2)(5)=( 2, 0,-2)T T w w3 3(6)=w(6)=w3 3(5)=(-2, 0,-2)(5)=(-2, 0,-2)T Tk=6,xk=6,xk k=x=x3 3

139、3 3, ,因为因为d d3 3(x(x3 3)=0d)=0d1 1(x(x3 3)=-2)=-2，d d3 3(x(x3 3)=0d)=0d2 2(x(x3 3)=-4)=-4，正确，正确，所以所以 w w1 1(7)=w(7)=w1 1(6)=( 0,-2, 0)(6)=( 0,-2, 0)T T w w2 2(7)=w(7)=w2 2(6)=( 2, 0,-2)(6)=( 2, 0,-2)T T w w3 3(7)=w(7)=w3 3(6)=(-2, 0,-2)(6)=(-2, 0,-2)T T332例例题题:已已知知训训练练样样本本(0,0)T1，(1,1)T2 ，(-1,1)T3,

140、试求解向量试求解向量w1、w2和和w3。 k=7,xk=7,xk k=x=x1 11 1, ,因为因为d d1 1(x(x1 1)=0d)=0d2 2(x(x1 1)=-2)=-2，d d1 1(x(x1 1)=0d)=0d3 3(x(x1 1)=-2)=-2，正确，正确，三个权矢量不再变化，因此可以确定所有训练样本均已三个权矢量不再变化，因此可以确定所有训练样本均已被正确分类，被正确分类，由此得到三个解矢量：由此得到三个解矢量：w1 1* *= =w1 1(5)(5)，w2 2* *= =w2 2(5)(5)，w3 3* *= =w3 3(5) (5) 同时可得三个判别函数同时可得三个判别函

141、数: :d d1 1( (x) = -2) = -2x x2 2d d2 2( (x) = 2) = 2x x1 1-2-2d d3 3( (x) = -2) = -2x x1 1-2-2333 3.6 二次准则函数及其解法二次准则函数及其解法 问题：问题： 一次准则函数及其算法（如感知器算法）一次准则函数及其算法（如感知器算法）只适用于线性可分的情况，如果是线性不可分只适用于线性可分的情况，如果是线性不可分的，分类过程将不收敛的，分类过程将不收敛! ! 能否找到一种算法，使之能够测试出模能否找到一种算法，使之能够测试出模式样本集是否线性可分，并且对线性不可分式样本集是否线性可分，并且对线性不

142、可分的情况也能给出的情况也能给出“次最优次最优”的解？的解？ 第三章第三章 判别域代数界面方程法判别域代数界面方程法334 如果训练模式是线性不可分如果训练模式是线性不可分不等式组是不等式组是不一致不一致的，不等式组没解。此时，目标的，不等式组没解。此时，目标最少的训练模式被最少的训练模式被错分。错分。（一）最小错分模式数目准则：（一）最小错分模式数目准则： 如果训练模式是线性可分的，则存在权矢量如果训练模式是线性可分的，则存在权矢量 使不等式组使不等式组成立。成立。对线性不可分样本集，求一解矢量使得错分的对线性不可分样本集，求一解矢量使得错分的模式数目最少。模式数目最少。 335336 如果

143、方程组有唯一解如果方程组有唯一解, ,说明训练模式集是线性说明训练模式集是线性可分的可分的, ,如果方程组无解如果方程组无解, ,极小点值是最小二乘解。极小点值是最小二乘解。一般情况下使一般情况下使 极小等价于误分模式数目最少。极小等价于误分模式数目最少。337338 求矩阵的广义逆计算量较大，引入的误差求矩阵的广义逆计算量较大，引入的误差也可能很大，在实际中多采用下面的梯度法。也可能很大，在实际中多采用下面的梯度法。339340为了减少计算量和存储量，可以仿照单样本修正法为了减少计算量和存储量，可以仿照单样本修正法: :由于：由于：此算法通常称为此算法通常称为W WH(WidrowH(Wid

144、rowHoff)Hoff)算法算法 341W-HW-H算法有两个性质算法有两个性质342343H-KH-K算法算法求解最佳权矢量的方法求解最佳权矢量的方法H-KH-K算法的迭代公式为：算法的迭代公式为：其中其中344345H-K算法步骤Step2.Step2.置初值置初值Step1.Step1.将训练样本符号规范化，得将训练样本符号规范化，得X X求伪逆求伪逆Step3.Step3.计算计算346H-K算法步骤Step6. Step6. k=k+1; goto Step3; goto Step3;Step5.Step5.347348349作业1 1 以下列两类模式为样本，用以下列两类模式为样本

145、，用LMSELMSE( (梯度法梯度法) )算法求解算法求解判决函数。（令判决函数。（令 w(1) = (-1,-2,-2)w(1) = (-1,-2,-2) ） 1 1：(0,0,0(0,0,0), (1,0,0) (1,0,0), (1,0,1, (1,0,1), , (1,1,0)(1,1,0), 2 2：(0,0,1)(0,0,1), (0,1,1), (0,1,1), (0,1,0), (0,1,0), , (1,1,1)(1,1,1),2 2 用用LMSELMSE( (梯度法梯度法) )算法检验下列模式的线性可分性。算法检验下列模式的线性可分性。 1 1：(0,1)(0,1)，(0

146、,-1)(0,-1) ， 2 2：(1,0)(1,0)，(-(-1,0)1,0) 。3 3 已知已知 1 1：(0,0)(0,0), 2 2：(1,1)(1,1), 3 3：(-1,1)(-1,1) 。用感知器算法求该三类问题的判别函数，并画出解区用感知器算法求该三类问题的判别函数，并画出解区域。域。350 设一维两类模式设一维两类模式 x x 在一维空间在一维空间坐标轴上分坐标轴上分布如图布如图3-9-13-9-1所示，两类的类域为所示，两类的类域为 和和 3.9 3.9 广义线性判别函数广义线性判别函数图图3.9.1 3.9.1 一维特征空间中非线性可分的图示一维特征空间中非线性可分的图示

147、351显然，这两类不是线显然，这两类不是线性可分的，因不能用性可分的，因不能用一个分界点将两类分一个分界点将两类分开。但是，对于一条开。但是，对于一条穿过穿过a a、b b两点的二次两点的二次曲线，曲线，当当即即或或时时, ,当当即即时时, ,352原来的一维非线性可分的模式在所映射的二维特征空原来的一维非线性可分的模式在所映射的二维特征空间中是线性可分的，即间中是线性可分的，即: :353使使在特征空间是线性可在特征空间是线性可分的分的, , 称其为称其为广义线性判别函数广义线性判别函数。354下图所示两类模式是线性不可分的。下图所示两类模式是线性不可分的。355经过非线性变换，两类模式是线

148、性可分的。经过非线性变换，两类模式是线性可分的。356式中式中是是 的单值实函数。的单值实函数。357358上式右边前两项是上式右边前两项是x x各分量的二次项求和式，各分量的二次项求和式，显然它们的项数分别为显然它们的项数分别为n n和和 n(n-1)/2n(n-1)/2。第三项是第三项是x x的各分量一次项求和式，项数为的各分量一次项求和式，项数为n n。所以所以d(x)d(x)的项数为的项数为: : n+n(n-1)/2+n+1=(n+1)(n+2)/2n+n(n-1)/2+n+1=(n+1)(n+2)/2由于有一个常数项，变换后的特征空间维数为由于有一个常数项，变换后的特征空间维数为:

149、 : (n+1)(n+2)/2-1=n(n+3)/2(n+1)(n+2)/2-1=n(n+3)/23591360的项数为：的项数为： 361 的维数的维数 令令其中其中362 3.10 3.10 二次判别函数二次判别函数 二次判别函数是一种常用的非线性判别函数，函二次判别函数是一种常用的非线性判别函数，函数构造比较简单，适用面比线性判别函数要广。数构造比较简单，适用面比线性判别函数要广。在在 n n 维特征空间中，二次判别函数的一般表示式为：维特征空间中，二次判别函数的一般表示式为：363 二次判别函数图例二次判别函数图例364一般的判别规则是：一般的判别规则是：计算训练模式计算训练模式构造判

150、别函数：构造判别函数：对未知模式：对未知模式：365特点：特点：（ 1 1）可直接确定判决函数）可直接确定判决函数 （ 2 2）适用于非线性和线性可分的情况）适用于非线性和线性可分的情况3.12 3.12 位势函数分类法位势函数分类法位势函数的概念：位势函数的概念： 位势为位势为0 0的等位线的等位线判决界面（判别函数）判决界面（判别函数）对于两类问题对于两类问题 1 1， 2 2，认为，认为 如果如果x x1 1，则，则x x 带正电荷带正电荷 如果如果x x2 2，则，则x x 带负电荷带负电荷366367 位势函数图例位势函数图例368369位势函数图例位势函数图例370371372 与

151、感知器算法类似，位势函数训练算法也可以用于多类问题，与感知器算法类似，位势函数训练算法也可以用于多类问题，其其技术要点技术要点是：是： 设初始积累位势函数设初始积累位势函数 ,这里这里 i 表示类别表示类别, i = 1,2,c。 当当 时，迭代规则是时，迭代规则是 如果如果 则则 如果如果 则则373374例：例：已知如图(3-12-1)所示两类训练样本： 试用势函数法进行分类器训练。 解：选用第二类势函数，令解：选用第二类势函数，令 =1=1，在二维情况下，在二维情况下，为积累位势函数为积累位势函数)(exp) 0() 0( (exp ),()(, 1222122211111xxxxxxK

152、xKxj+-=-+-=rrrr375376377令令判别界面判别界面378判别界面判别界面x2=x1-1x2=1-x1379已知两类训练样本：已知两类训练样本：试用势函数法设计分类器。试用势函数法设计分类器。 作业：380模式识别主讲主讲： 蔡宣平蔡宣平 教授教授 电话电话： 7344173441（O O）,73442,73442（H H）E-mailE-mail：单位单位: : 电子科学与工程学院信息工程系电子科学与工程学院信息工程系381382随机模式分类识别，通常称为随机模式分类识别，通常称为BayesBayes( (贝叶斯贝叶斯) )判决判决。（基础复习）（基础复习）第四章第四章 统计

153、判决统计判决主要依据类的概率、概密，按照主要依据类的概率、概密，按照某种准则某种准则使分使分类结果从统计上讲是最佳的。准则函数不同，所导类结果从统计上讲是最佳的。准则函数不同，所导出的出的判决规则判决规则就不同，分类结果也不同。就不同，分类结果也不同。本章主要论述分类识别的一般原理、几种重要本章主要论述分类识别的一般原理、几种重要的的准则准则和相应的和相应的判决规则判决规则，正态分布模式类的判决，正态分布模式类的判决函数以及它们的性能。函数以及它们的性能。383384BayesBayes公式：公式：设实验设实验E E的样本空间为的样本空间为S S，A A为为E E的事件，的事件，B B1 1,

154、B,B2 2, , ,B Bn n为为S S的一个划分，且的一个划分，且P P(A)0(A)0，P P(B(Bi i)0)0，(i=1,2,(i=1,2,n),n)，则，则: :“概率论概率论”有关概念复习有关概念复习385B1SB2B3B4A划分示意图“概率论概率论”有关概念复习有关概念复习386条件概率条件概率“概率论概率论”有关概念复习有关概念复习先验概率：先验概率：P( i)表示类表示类 i出现的先验概率，简称类出现的先验概率，简称类 i的概率。的概率。后验概率：后验概率：P P( ( i i|x|x) )表示表示x x出现条件下类出现条件下类 i i出现的概率出现的概率, ,称其为称

155、其为类别的类别的后验概率后验概率，对于模式识别来讲可理解为，对于模式识别来讲可理解为x x来自类来自类 i i的的概率。概率。类概密：类概密： p(x|(x| i i) )表示在类表示在类 i i条件下的概率密度，即类条件下的概率密度，即类 i i模模式式x x 的概率分布密度，简称为的概率分布密度，简称为类概密类概密。387 为表述简洁，我们将随机矢量为表述简洁，我们将随机矢量X X及它的某个取值及它的某个取值x x都都用同一个符号用同一个符号x x表示，在以后各节中出现的是表示随机表示，在以后各节中出现的是表示随机矢量还是它的一个实现根据内容是可以清楚知道的。矢量还是它的一个实现根据内容是

156、可以清楚知道的。“概率论概率论”有关概念复习有关概念复习条件期望条件期望( (某个特征某个特征) )因不涉及因不涉及x的维数的维数,可将可将Xn改写为特征空间改写为特征空间W W。388对于两类对于两类 1 1， 2 2问题，直观地，可以根据后验概率做判决：问题，直观地，可以根据后验概率做判决：式中，式中，p p(x|(x| i i) )又称又称似然函数似然函数(likelihood function of (likelihood function of class class i i) )，可由已知样本求得。，可由已知样本求得。 Bayes法则最大后验概率准则法则最大后验概率准则根据根据Ba

157、yes公式，后验概率公式，后验概率 可由类可由类 i的先验概率的先验概率P( i)和条件概率密度和条件概率密度 来表示，即来表示，即389将将P( i|x)代入判别式，判别规则可表示为代入判别式，判别规则可表示为或改写为或改写为l12称为称为似然比似然比（likelihood ratio），）， 12称为似然比的判决阀值。称为似然比的判决阀值。原则：要确定原则：要确定x x是属于是属于11类还是类还是22类，要看类，要看x x是来自于是来自于11类的概率大还是来自类的概率大还是来自22类的概率大。类的概率大。390已知：已知：（统计结果）（统计结果）先验概率：先验概率：P( ( 1 1)=1/

158、3)=1/3（鲈鱼出现的概率）（鲈鱼出现的概率） P( ( 2 2)=1-)=1-P( ( 1 1)=2/3 )=2/3 （鲑鱼出现的概率鲑鱼出现的概率）条件概率条件概率：p(x| 1 1) 见图示见图示（鲈鱼的长度特征分布概率）（鲈鱼的长度特征分布概率）p(x| 2 2)见图示见图示（鲑鱼的长度特征分布概率）（鲑鱼的长度特征分布概率）求：后验概率求：后验概率：P( |x=10)=?（如果一条鱼如果一条鱼x x1010，是什么类别？），是什么类别？）391解法解法1 1：利用利用Bayes公式公式392写成似然比形式写成似然比形式解法解法2：393例题1图示鲈鱼鲈鱼鲑鱼鲑鱼100.050.55

159、.58.5394例题1图示10395n 最小误判概率准则判决最小误判概率准则判决n 最小损失准则判决最小损失准则判决n 最小最大损失准则最小最大损失准则n N-P(NeymanPearson)N-P(NeymanPearson)判决判决第四章第四章 统计判决统计判决39641 41 最小误判概率准则判决最小误判概率准则判决第四章第四章 统计判决统计判决397398图例：最小误判概率准则399400最小误判概率准则下的判决规则：最小误判概率准则下的判决规则： 如果，如果， 则判则判或等价地，或等价地， 如果，如果， 则判则判401另一个等价形式是：另一个等价形式是： 如果如果 则判则判由贝叶斯定

160、理由贝叶斯定理402对于多类问题，对于多类问题，最小误判概率准则最小误判概率准则有如下有如下几种等价的判决规则几种等价的判决规则:若若 ，则判，则判 若若 ， ，则判，则判 （后验概率形式）（后验概率形式）若若 ， ，则判，则判 若若 ，则判，则判 （条件概率形式）（条件概率形式）若若 ， , 则判则判 （似然比形式）（似然比形式）如果如果 ， ，则判则判 （条件概率的对数形式）（条件概率的对数形式）403例：对一批人进行癌症普查，患癌症者定为属例：对一批人进行癌症普查，患癌症者定为属 1类，类，正常者定为属正常者定为属 2类。统计资料表明人们患癌的概率类。统计资料表明人们患癌的概率 ，从而，

161、从而 。设有一种诊断此病的。设有一种诊断此病的试验，其结果有阳性反应和阴性反应之分，依其作诊试验，其结果有阳性反应和阴性反应之分，依其作诊断。化验结果是一维离散模式特征。统计资料表明：断。化验结果是一维离散模式特征。统计资料表明：癌症者有阳性反映的概率为癌症者有阳性反映的概率为0.95即即 ，从而可知从而可知 ，正常人阳性反映的概率，正常人阳性反映的概率为为0.01即即 , 可知可知 。问有阳性反映的人患癌症的概率有多大？问有阳性反映的人患癌症的概率有多大？404解：解：说明有阳性反应的人其患癌的概率有说明有阳性反应的人其患癌的概率有32.3% 32.3% 405写成似然比形式：写成似然比形式

162、： 406407上式中去掉与类别无关的项并不影响分类判决结果：上式中去掉与类别无关的项并不影响分类判决结果：或对数形式或对数形式 类的判决函数可以表示为：类的判决函数可以表示为：408(1) 当当 时时当当 和和 相邻相邻 时时409当当 和和 相邻相邻 时时式中：式中：显显然，然，该该判判别别界面界面为为一超平面。此决策超平面一超平面。此决策超平面过过点点 ， 是该超平面的法矢量。是该超平面的法矢量。 410若各类的概率相等，由判别式若各类的概率相等，由判别式 可简化为马氏距离的平方，即：可简化为马氏距离的平方，即： 因此因此 的类别就由的类别就由 到各类的均矢的马氏距离决定，到各类的均矢的

163、马氏距离决定，应判应判 属于马氏距离最小的那一类。属于马氏距离最小的那一类。 411x1x2 决策超平面过决策超平面过点，矢量点，矢量是该超平面的法矢量。是该超平面的法矢量。通常不与通常不与方向相同，所以决策界面不与方向相同，所以决策界面不与正交。正交。412x1x2 为单位阵，为单位阵，为分量的方差，显然有矢量为分量的方差，显然有矢量和矢量和矢量方向相同，此时决策平面垂直于两类中心的连线方向相同，此时决策平面垂直于两类中心的连线 若若此时决策界面还过此时决策界面还过和和连线的中点连线的中点 413(2)这是一般的情况。这是一般的情况。 i i类模式的判决函数为类模式的判决函数为: :其中其中

164、相邻两类的决策界面为相邻两类的决策界面为: :414415二维模式，二维模式， 1 12 2的几种情况的几种情况12(a) 圆，圆， 2 2类的方差小类的方差小12(b) 椭圆，椭圆， 2 2类的方差小类的方差小12(c) 抛物线，抛物线， 2 2类的方差小类的方差小12(d) 双曲线双曲线(e) 直线，两类的分布关于一直线是对称直线，两类的分布关于一直线是对称12416例：模式分布如图所示，两类的均矢和协方差阵例：模式分布如图所示，两类的均矢和协方差阵可用下式估计。可用下式估计。(0,1,1)(1,1,1)(1,0,0)(1,0,1)(0,0,1)(0,0,0)12x2x1x321417(0

165、,1,1)(1,1,1)(1,0,0)(1,0,1)(0,0,1)(0,0,0)12x2x1x321418两类均作为正态分布，并假设两类均作为正态分布，并假设 ，故判决式为故判决式为419 考虑两类问题，设两类模式为协方差阵相考虑两类问题，设两类模式为协方差阵相等的多变量正态分布，它们的密度等的多变量正态分布，它们的密度函函数分别为数分别为: : 4.1.3 4.1.3 正态模式分类的误判概率正态模式分类的误判概率对数似然比对数似然比420令令是是 的线性函数，而的线性函数，而 的各分量是正态分布的，的各分量是正态分布的，故故 是正态分布的随机变量。是正态分布的随机变量。 421xi0rij2

166、/2xj-rij2/2p(Lij|i)Lijp(Lij|j)422将属于将属于类的模式误判为属于类的模式误判为属于类的错误概率为类的错误概率为将属于将属于类的模式误判为属于类的模式误判为属于类的错误概率为类的错误概率为式中式中423于是，总的误判概率为于是，总的误判概率为: :424特取特取 ，此时，此时 =0=0 上式表明了误判概率与两类的马氏距离的关系上式表明了误判概率与两类的马氏距离的关系： 随随 的增大而单调递减，只要两类马氏距的增大而单调递减，只要两类马氏距离足够大，其误判概率可足够小。离足够大，其误判概率可足够小。 4254.1 4.1 设以下两类模式均为正态分布设以下两类模式均为

167、正态分布 1 1：(0,0)(0,0)T T，(2,0)(2,0)T T，(2,2)(2,2)T T，(0,2)(0,2)T T 2 2：(4,4)(4,4)T T，(6,4)(6,4)T T，(6,6)(6,6)T T，(4,6)(4,6)T T 设设P(P( 1 1)= P()= P( 2 2)=1/2)=1/2，求该两类模式之间的，求该两类模式之间的BayesBayes 判别界面的方程。判别界面的方程。作业作业4.2 4.2 设两类二维正态分布参数为设两类二维正态分布参数为u u1 1=(-1,0)=(-1,0)T T，u u2 2=(1,0)=(1,0)T T先验概率相等。先验概率相等

168、。（a a） 令令 试给出负对数似然比判决规则试给出负对数似然比判决规则（b b） 令令试给出负对数似然比判决规则。试给出负对数似然比判决规则。4264.2 4.2 最小损失准则判决最小损失准则判决第四章第四章 统计判决统计判决4274.2.1 4.2.1 损失概念、损失函数与平均损失损失概念、损失函数与平均损失设模式空间中存在设模式空间中存在c c个类别个类别: :决策空间由决策空间由a a个决策个决策: :决策决策 j j常指将模式常指将模式x x指判为某一类指判为某一类w wj j或者是拒判。或者是拒判。对一个实属对一个实属 i i 类的模式采用了决策类的模式采用了决策 j j 所造成的

169、损失所造成的损失记为：记为：于是就有于是就有 空间中的二元函数，称其为空间中的二元函数，称其为损失函数损失函数。428决策决策- -损失表损失表 n决策决策 j j指将模式指将模式x x指判为指判为w wj j或者是拒判。或者是拒判。0-10-1损失函数损失函数429 令决策的数目令决策的数目a a等于类数等于类数c c，如果决策，如果决策 j j 定义为判定义为判 属属于于 j j 类，那么对于给定的模式类，那么对于给定的模式 在采取决策在采取决策 j j 的条件下的条件下损失的期望为损失的期望为条件平均风险条件平均风险 条件期望损失条件期望损失 刻划了在模式为刻划了在模式为 、决策为、决策

170、为 j j条条件下的平均损失，故也称件下的平均损失，故也称 为为条件平均损失或条条件平均损失或条件平均风险（件平均风险（RiskRisk）。由贝叶斯公式，上式可以写为。由贝叶斯公式，上式可以写为430求上式求上式Rj(x)关于关于x的数学期望的数学期望:平平均均损损失失431n可以将最小条件平均损失判决规则表示为可以将最小条件平均损失判决规则表示为如果如果 则判则判 4.2.2 4.2.2 最小损失准则判决最小损失准则判决定理：定理：使条件平均损失最小的判决也必然使总的平均使条件平均损失最小的判决也必然使总的平均损失最小。损失最小。 所以最小条件平均损失准则也称为最小平均损失所以最小条件平均损

171、失准则也称为最小平均损失准则或最小平均风险准则，简称为准则或最小平均风险准则，简称为最小损失准则最小损失准则。432 对于两类问题，对于两类问题，如果如果则：则：这时最小损失判决规则这时最小损失判决规则可以表为：可以表为： 433经整理可得：经整理可得： 两类问题的最小损失准则的似然比形式的判两类问题的最小损失准则的似然比形式的判决规则为：决规则为：如果如果 则判则判 434若记似然比阈值若记似然比阈值注意，若注意，若我们规定任判或拒判。我们规定任判或拒判。则两类问题的判决规则为：则两类问题的判决规则为：如果如果则判：则判： 435如果如果则判：则判： 损失函数如何确定依赖于实际问题和经验，有

172、时损失函数如何确定依赖于实际问题和经验，有时为了方便，对于一般的为了方便，对于一般的类问题，令类问题，令 （0-10-1损失函数）损失函数）此时：此时：此即为最小误判概此即为最小误判概率准则的判决规则率准则的判决规则 436取取0-10-1损失函数时，最小损失准则等价于最小损失函数时，最小损失准则等价于最小误判概率准则，此时的平均损失就是误判概率，误判概率准则，此时的平均损失就是误判概率，使平均损失最小即使误判概率最小。这也表明，使平均损失最小即使误判概率最小。这也表明，最小误判概率准则是最小损失准则的特例。最小误判概率准则是最小损失准则的特例。 4.2.2 最小损失准则判决最小损失准则判决4

173、37438似然比为：似然比为：439运用最小损失准则，判决规则为：运用最小损失准则，判决规则为：判判即信号为即信号为“0 0”。时时两边取对数：两边取对数： 当当 时时4404414424.2.3 4.2.3 含拒绝判决的最小损失判决含拒绝判决的最小损失判决拒绝判决可以作为最小损失判决中的一个可能判决，拒绝判决可以作为最小损失判决中的一个可能判决，“拒绝判决拒绝判决”。443如果如果j j=1,2,=1,2, ,c c则作出拒绝判决。则作出拒绝判决。设设 ( ( c+1c+1( ( ) )| | i i)=)= r r，( (i i=1,2,=1,2,c),c)，（即各类的拒判损失相同）（即各

174、类的拒判损失相同） 则则 又设又设 ( ( j j( ( ) )| | i i)=)= e e，( (j j i i，i i，j j =1,2, =1,2,c),c)，（即各误判损失相同）（即各误判损失相同）（即各正确判决损失相同）（即各正确判决损失相同） ( ( i i( ( ) )| | i i)=)= c c，( (i i=1,2,=1,2,c),c)， 且通常有且通常有 c c r r e e444445如果如果，(j=1,2,c)，则对则对做拒绝判决。做拒绝判决。 = 1-t 这里这里 称之称之为为拒判拒判门门限。限。 因因为为 c r 1-1/c时时,1-t1/c,上式恒成立上式恒

175、成立,不存在拒判问题不存在拒判问题,即存在拒判决策的条件应该是即存在拒判决策的条件应该是:t1-1/c447判决规则判决规则如下：如下：4.2.3 4.2.3 含拒绝判决的最小损失判决含拒绝判决的最小损失判决如果如果 则判则判如果如果则判则判4484.34.3最小最大损失准则最小最大损失准则第四章第四章 统计判决统计判决449最小误判概率准则最小误判概率准则最小损失准则最小损失准则拒判拒判拒拒绝绝判判决决的的最最小小损损失失450拒判拒判拒拒绝绝判判决决的的最最小小损损失失拒判损失拒判损失误判损失误判损失正确判决损失正确判决损失451最小最大损失准则最小最大损失准则的基本思想：的基本思想： 实

176、际中，类先验概率实际中，类先验概率 P P( ( i i) ) 往往不能精确往往不能精确知道或在分析过程中是变动的，从而导致判决知道或在分析过程中是变动的，从而导致判决域不是最佳的。所以应考虑如何解决在域不是最佳的。所以应考虑如何解决在 P P( ( i i) ) 不确知或变动的情况下使平均损失变大的问题。不确知或变动的情况下使平均损失变大的问题。 应该立足最差的情况争取最好的结果。应该立足最差的情况争取最好的结果。452对于两类问题，设一种分类识别决策将特征空对于两类问题，设一种分类识别决策将特征空间间分划为两个子空间分划为两个子空间1和和2，记，记ij为将实属为将实属i类的模式判为类的模式

177、判为j的损失函数，各种判决的平均损失的损失函数，各种判决的平均损失为为xdxpxxRRrrrr=)()(xdxpxxRxdxpxxRrrrrrrrr+=21)()()()(21xdPxpxdPxpiiiiiiiirrrr)()()()(21212211+=+=11)()()()(22211111xdxpPxdxpPrrrr+22)()()()(22221112xdxpPxdxpPrrrr453利用利用)(1)(12-=PP则平均损失可写成则平均损失可写成-+=1)()(2222122xdxpRrr-+-+-+12)()()()()()(221221111222111xdxpxdxpPrrrr)

178、(1+DbPa由于由于)(1P在在 0 0 和和 1 1 之间取值，所以平均损失值有之间取值，所以平均损失值有baRa+-=21)(1)(xdxpxdxpiirrrr和和454n由上式可见，当类概密、损失函数ij 、类域i 取定后，R是P(1)的线性函数。n考虑P(1)的各种可能取值情况，为此在区间(0,1)中取若干个不同的P(1)值，并分别按最小损失准则确定相应的最佳决策类域1 、 2 ，然后计算出其相应的最小平均损失R*，从而可得最小平均损失R*与先验概率P(1)的关系曲线。455PA(1)1 P(1)ACDR*BR*B0DCPB(1)456 如果能求出某个如果能求出某个)()(11DBP

179、P，相对于相对于)(1BP的最佳判决的最佳判决类域类域1和和2能使该式中的能使该式中的0=b，即，即0)()()()()(1222122111122211=-+-+-=xdxpxdxpbrrrr在此决策类域下，无论在此决策类域下，无论)(1P如何变化，因如何变化，因0=b而使而使R与与)(1P无关，从而使得平均损失无关，从而使得平均损失R恒等于常数恒等于常数a，即即aRxdxpR=D-+=*1)()(2222122rr求使求使0=b的的)(1P等价于在最小平均损失等价于在最小平均损失*R)(1P关系关系中求使中求使0)(1=*dPdR的的)(1P，显然，此时的，显然，此时的)(1P使使*R取所

180、有最小损失的最大取所有最小损失的最大值值*mR。所以所以*mR是最大的最小损失。是最大的最小损失。457具体的设计过程是具体的设计过程是: :(1)(1) 按最小损失准则找出对应于按最小损失准则找出对应于(0,1)(0,1) 中的各个不同值的中的各个不同值的)(1P的最佳决策类域的最佳决策类域1、2， (2)(2) 计算相应各个计算相应各个)(1P及最佳决策类域的最小平均损失，得及最佳决策类域的最小平均损失，得*R)(1P曲线，找出使曲线，找出使*R取最大值的取最大值的)(1*P， (3)(3) 运用运用)(1*P、)(11-*P及及ij构造似然比阈值并运用最小构造似然比阈值并运用最小损失准则

181、下的决策规则对具体的模式分类识别。损失准则下的决策规则对具体的模式分类识别。 )()()()()()()()()(12121221122lllPxpxpxpPxpxpxpxRjjjjrrrrrrr-+-+=458最小最大损失判决规则最小最大损失判决规则 为：为：如果如果 )()()(1)()()(111121222121-*PPxpxprr则判则判21xr当采用当采用 0-10-1 损失函数时，由损失函数时，由0=b可得可得xdxpxdxprrrr)()(2112=上式表明，最小最大损失判决所导出的最佳分界面上式表明，最小最大损失判决所导出的最佳分界面应使两类错误概率相等应使两类错误概率相等

182、, ,可知此时的平均损失可知此时的平均损失=1)(2xdxpRrr459作业作业P125 4.1 4.2 4.7P125 4.1 4.2 4.746044 N-P(NeymanPearson)44 N-P(NeymanPearson)判决判决第四章第四章 统计判决统计判决461在某些实际问题中，可能存在以下几种情况：在某些实际问题中，可能存在以下几种情况： 不知道各类的先验概率不知道各类的先验概率)(iP ； 难于确定误判的代价难于确定误判的代价ij； 某一种错误较另一种错误更为重要。某一种错误较另一种错误更为重要。针对针对，可以采用最小最大损失准则或令各类概可以采用最小最大损失准则或令各类概

183、率相等的办法克服；率相等的办法克服；针对针对(3)(3)，可以采用最小损失准则判决。针对上，可以采用最小损失准则判决。针对上面的三个问题，更主要的是针对面的三个问题，更主要的是针对，我们采用，我们采用N-PN-P准则准则。针对针对，如果允许的话，可，如果允许的话，可以避开使用损失函数以避开使用损失函数 而采用最小误判概率准则而采用最小误判概率准则；462所谓所谓N-PN-P准则，是严格限制较重要的一类错误概准则，是严格限制较重要的一类错误概率令其等于某常数而使另一类误判概率最小。率令其等于某常数而使另一类误判概率最小。 对两类问题，对两类问题，0)(= =xdr r将特征空间将特征空间W W分

184、成两分成两 个子空间个子空间1W W和和2W W，其中，其中W W= =W WW W21U U，F F= =W WW W21I I。 当一模式特征点当一模式特征点1W W xr r时，指判时，指判1 xr r；当当2W W xr r 时，指判时，指判2 xr r。463将实属将实属类的模式类的模式判属判属类的误判概率为类的误判概率为将实属将实属类的模式判属类的模式判属类的误判概率为类的误判概率为 N-PN-P准则是在使某一类误判概率等于常数的约准则是在使某一类误判概率等于常数的约束下使另一类误判概率最小。束下使另一类误判概率最小。 464令令=021常数，求常数，求使使12最小。运用最小。运用

185、拉格朗日拉格朗日乘乘数法求条件极值，为此作辅助函数数法求条件极值，为此作辅助函数:465郎格朗日乘数法郎格朗日乘数法: : 在条件极值问题中在条件极值问题中, , 满足条件满足条件 g(x, y) = 0 g(x, y) = 0 下，下，去寻求函数去寻求函数 f(x, y) f(x, y) 的极值。的极值。 对三变量函数对三变量函数 F(x, y, ) = f(x, y) + g(x, y) F(x, y, ) = f(x, y) + g(x, y) 分别求分别求F F对三变量的偏导对三变量的偏导, ,并联立方程式并联立方程式 F F = g(x, y) = 0 = g(x, y) = 0 F

186、 Fx x = f = fx x (x, y) + g (x, y) + gx x (x, y) = 0 (x, y) = 0 F Fy y = f = fy y (x, y) + g (x, y) + gy y (x, y) = 0 (x, y) = 0 求得的解求得的解 (x, y) (x, y) 就成为极值的候补。就成为极值的候补。 这样求极值的方法就叫做拉格朗日乘数法、这样求极值的方法就叫做拉格朗日乘数法、叫叫做拉格朗日乘数。做拉格朗日乘数。 466求求使使取极小值。取极小值。无法直接用解析的办法求得。无法直接用解析的办法求得。 一般地讲，一般地讲，但注意到但注意到在式子中是确定的，在

187、式子中是确定的，、在在空间中也是确定的，如果选择满足条件空间中也是确定的，如果选择满足条件的的的全体作为的全体作为这时所求得的这时所求得的值值比比的其它取法时的的其它取法时的值要小。值要小。 就能保证就能保证因为这种取法下因为这种取法下, , 是使被积函数取正数的最大的域。是使被积函数取正数的最大的域。467，如前定义如前定义这时的这时的值为值为 上有上有于是在于是在在在上有上有上式中第二项的积分为正值，第三项的积分为负值。上式中第二项的积分为正值，第三项的积分为负值。显然显然468同理同理, , 由由因此选择满足条件因此选择满足条件的全体的全体 作为作为选择满足条件选择满足条件的全体的全体

188、作为作为在在中中 在在中中 综上，即：综上，即：469于是将其中一类错误概率作为控制量而使另一类于是将其中一类错误概率作为控制量而使另一类错误概率最小错误概率最小的的N-N-P P判决规则为：判决规则为：上式中上式中，是判决阈值是判决阈值。如果如果，则判则判 可以看出，可以看出，N-PN-P判决规则的形式和最小误判判决规则的形式和最小误判概率准则及最小损失准则的形式相同，只是似然概率准则及最小损失准则的形式相同，只是似然比阈值不同。比阈值不同。 470这里这里是由下列关系式确定：是由下列关系式确定：即适当地选取即适当地选取以保证使以保证使，因此，因此的值决定着类域的值决定着类域、。这里这里为似

189、然比为似然比的条件概密。的条件概密。，令，令为求为求因当因当时就判时就判，所以当，所以当给定后，给定后，可由式可由式确定。确定。拉格朗日乘子拉格朗日乘子4711221xp(l|2)p(l|1) 的值决定着类域的值决定着类域1、2，这里的，这里的 是由是由0e所所确定的，即适当地选取确定的，即适当地选取使使021=。为求。为求 ，令，令)(2lp为似然比为似然比)(xlr在在2xr的条件下的概密，因当的条件下的概密，因当l时就时就判判1xr，所以当，所以当0给定后，拉格朗日乘子给定后，拉格朗日乘子可由式可由式 确定。确定。 W W1W W2l472在具体运用在具体运用N-PN-P准则时，首先根据

190、给定的控制准则时，首先根据给定的控制量量e e0计算门限计算门限 ，然后运用判决规则进行判决分类。，然后运用判决规则进行判决分类。473例：例：设两类问题中，二维模式均为正态分布，设两类问题中，二维模式均为正态分布，其均值矢量和协方差阵分别为：其均值矢量和协方差阵分别为： ，取定，取定试求试求N-P判决阈值。判决阈值。解解：由公式和给定的条件可算得两类的概密分别为：由公式和给定的条件可算得两类的概密分别为: :由上面二式可以算得由上面二式可以算得 : :474其为判决界面，上式两边取对数，于是可得判决规其为判决界面，上式两边取对数，于是可得判决规则则: : 由于界面只是由于界面只是的函数，需求

191、的函数，需求的边缘密度的边缘密度475由上面的判决规则，有由上面的判决规则，有: :476有数学手册可查得有数学手册可查得:可算得可算得与与的关系如下表所示：的关系如下表所示： 4211/21/4210.0460.0890.01590.2580.378477x1x221-1 1 1 221t=-(1/2)ln 由设定的由设定的，查上表可得，查上表可得，对应的，对应的，从而得此问题的判决规则为，从而得此问题的判决规则为: ，则判，则判 若若478本章主要介绍了贝叶斯统计决策理论为基础的贝本章主要介绍了贝叶斯统计决策理论为基础的贝叶斯分类方法叶斯分类方法, ,其中包括了其中包括了最小误判概率最小误

192、判概率、最小损失最小损失准则准则等，依据这些准则设计的分类器，从理论上讲是等，依据这些准则设计的分类器，从理论上讲是最优的性能，即分类的错误率或风险在所有可能的分最优的性能，即分类的错误率或风险在所有可能的分类器中为最小，因此经常被用来作为衡量其他分类器类器中为最小，因此经常被用来作为衡量其他分类器设计方法优劣的标准。设计方法优劣的标准。由于正态分布在由于正态分布在物理上物理上的合理性和的合理性和数学上数学上的计算的计算简便性，我们详细介绍了贝叶斯分类方法在正态分布简便性，我们详细介绍了贝叶斯分类方法在正态分布下的几种特殊情形，导出了其对应的判决函数、决策下的几种特殊情形，导出了其对应的判决函

193、数、决策面方程及相应的几何描述。面方程及相应的几何描述。479下面我们简单回顾一下本章所学的几种贝叶斯下面我们简单回顾一下本章所学的几种贝叶斯决策准则决策准则: :1 1、最小误判概率准则、最小误判概率准则如果如果则判则判两类时两类时: :多类时多类时: : 如果如果判判4802 2、最小损失准则、最小损失准则则判则判如果如果 两类时两类时: :多类时多类时: :计算计算若若则判则判4813 3、含拒绝判决的最小损失准则、含拒绝判决的最小损失准则拒判拒判其中：其中：拒判损失拒判损失误判损失误判损失正确判决损失正确判决损失两类时两类时: :4823 3、含拒绝判决的最小损失准则、含拒绝判决的最小

194、损失准则多类时多类时: :计算计算若若则判则判其中其中 为拒绝判决。为拒绝判决。4834 4、最小最大损失准则、最小最大损失准则如果如果 则判则判 是如何获得的？是如何获得的？ 让让 从从0 逐渐变化到逐渐变化到1，按最小损失准则算出最，按最小损失准则算出最小平均损失，即取各类条件平均损失的最小者。小平均损失，即取各类条件平均损失的最小者。由此可得出由此可得出RP(RP( 1 1) )曲线，最大的曲线，最大的R R对应的对应的P(P( 1 1) )就就是是4845 5、N-PN-P准则准则如果如果，则判则判 是如何获得的？是如何获得的？由由固定固定e e0 0反求反求 485例：在军事目标识别

195、中，假定有灌木丛和坦克两种例：在军事目标识别中，假定有灌木丛和坦克两种类型，它们的先验概率分别是类型，它们的先验概率分别是0.7和和0.3，损失函数如，损失函数如下表所示，其中，类型下表所示，其中，类型 1和和 2分别表示灌木和坦克，分别表示灌木和坦克，判决判决 1= 1， 2= 2， 3表示拒绝判决。现在做了四表示拒绝判决。现在做了四次试验，获得四个样本的类概率密度如下：次试验，获得四个样本的类概率密度如下： P(x| 1):0.1, 0.15, 0.3, 0.6, P(x| 2):0.8, 0.7, 0.55, 0.3 1 2 12.52.0 24.01.0 31.51.5（1 1）用最小

196、误判概率准则，判）用最小误判概率准则，判断四个样本各属哪一个类型。断四个样本各属哪一个类型。问：问：（3） 把拒绝判决考虑在内，重新考核四次试验的结把拒绝判决考虑在内，重新考核四次试验的结果。果。（2 2）假定只考虑前两种情况，）假定只考虑前两种情况，试用最小损失准则判断四个试用最小损失准则判断四个样本各属于哪一个类型。样本各属于哪一个类型。类型判决判决损损 失失486答答: : 求出四个样本两类的似然比。求出四个样本两类的似然比。最小误判概率准则时的阈值：最小误判概率准则时的阈值：（1） 因此按最小误判概率准则判决时，第一、第因此按最小误判概率准则判决时，第一、第二样本属于第二类即坦克，第三

197、、第四属于第一二样本属于第二类即坦克，第三、第四属于第一类即灌木丛。类即灌木丛。487（2） 按最小损失准则判决按最小损失准则判决因此按最小损失准则判决时，第一、第二样本属于因此按最小损失准则判决时，第一、第二样本属于第二类即坦克，第三、第四属于第一类即灌木丛。第二类即坦克，第三、第四属于第一类即灌木丛。最小损失准则时的阈值：最小损失准则时的阈值：488（3） 带拒绝的最小损失准则判决带拒绝的最小损失准则判决由于是比较大小由于是比较大小, ,可忽略可忽略p(x),p(x),即只需计算即只需计算489（3） 带拒绝的最小损失准则判决带拒绝的最小损失准则判决因此第一、因此第一、 第二、第三、第四样

198、本均拒判。第二、第三、第四样本均拒判。=2.5*0.7*(0.1,0.15,0.3,0.6)+2.0*0.3*(0.8,0.7,0.55,0.3)=(0.655, 0.683, 0.855, 1.23)=4.0*0.7*(0.1,0.15,0.3,0.6)+1.0*0.3*(0.8,0.7,0.55,0.3)=(0.52, 0.63, 1.005, 1.77)=1.5*0.7*(0.1,0.15,0.3,0.6)+1.5*0.3*(0.8,0.7,0.55,0.3)=(0.465, 0.473, 0.563, 0.765)490利用贝叶斯分类器实现手写数字识别的例子利用贝叶斯分类器实现手写数字

199、识别的例子对每个手写的数字样品对每个手写的数字样品, , 按按NxNNxN方式划分方式划分, ,共有共有2525份，份，如图所示。如图所示。对每一份内的象素个数进行累对每一份内的象素个数进行累加统计加统计,除以每一份内的象素总除以每一份内的象素总数数,设定阈值设定阈值T=0.05,若每一份若每一份内的象素占有率大于内的象素占有率大于T则对应则对应的特征值为的特征值为1,否则为否则为0.1 1、理论基础、理论基础（1）先计算先验概率）先计算先验概率2 2、实现步骤、实现步骤P( i)类别为数字类别为数字i的先验概率的先验概率Ni数字数字i的样品数的样品数N为样品总数为样品总数491利用贝叶斯分类

200、器实现手写数字识别的例子利用贝叶斯分类器实现手写数字识别的例子2 2、实现步骤、实现步骤（2）计算）计算 ，再计算类条件概率，再计算类条件概率 表示样品表示样品X属于属于 i类条件下，类条件下，X的第的第j个分量为个分量为1的概率估计值。的概率估计值。492利用贝叶斯分类器实现手写数字识别的例子利用贝叶斯分类器实现手写数字识别的例子2 2、实现步骤、实现步骤其中其中 =0=0或或1 1（3 3）利用贝叶斯公式求后验概率）利用贝叶斯公式求后验概率493利用贝叶斯分类器实现手写数字识别的例子利用贝叶斯分类器实现手写数字识别的例子2 2、实现步骤、实现步骤（4 4）后验概率的最大值的类别（）后验概率

201、的最大值的类别（0909）就是手写）就是手写数字的所属类别。数字的所属类别。494利用贝叶斯分类器实现手写数字识别的例子利用贝叶斯分类器实现手写数字识别的例子2 2、实现步骤、实现步骤（4 4）后验概率的最大值的类别（）后验概率的最大值的类别（0909）就是手写）就是手写数字的所属类别。数字的所属类别。（1）先计算先验概率）先计算先验概率（2）计算）计算 ，再计算类条件概率，再计算类条件概率（3 3）利用贝叶斯公式求后验概率）利用贝叶斯公式求后验概率495已知两个一维模式类别的类概率密度函数为已知两个一维模式类别的类概率密度函数为先验概率先验概率P P( ( 1 1)=)= P P( ( 2

202、2)=0.5 )=0.5 。(1) (1) 求求BayesBayes判决函数（用判决函数（用0-10-1损失函数）；损失函数）；(2) (2) 求总误判概率求总误判概率P P(e)(e)。P126: 4.8 作业作业496模式识别主讲主讲： 蔡宣平蔡宣平 教授教授 电话电话： 7344173441（O O）,73442,73442（H H）E-mailE-mail：单位单位: : 电子科学与工程学院信息工程系电子科学与工程学院信息工程系497第五章第五章 统计决策中的训练、学习统计决策中的训练、学习 与错误率测试、估计与错误率测试、估计n 统计推断概述统计推断概述n 参数估计参数估计n 概密的

203、窗函数估计法概密的窗函数估计法n 有限项正交函数级数逼近有限项正交函数级数逼近法法49851 51 统计推断概述统计推断概述第五章第五章 统计决策中的训练、学习统计决策中的训练、学习 与错误率测试、估计与错误率测试、估计499本章目的：已知类别的样本（训练样本）本章目的：已知类别的样本（训练样本） 学习或训练学习或训练获得类概密获得类概密在上一章的学习中在上一章的学习中, ,我们一直假设类的条件概我们一直假设类的条件概率密度函数是已知的率密度函数是已知的, ,然后去设计贝叶斯分类器。然后去设计贝叶斯分类器。但在实际中，这些知识往往是不知道的，这就需但在实际中，这些知识往往是不知道的，这就需要用

204、已知的样本进行学习或训练。也就是说利用要用已知的样本进行学习或训练。也就是说利用统计推断理论中的估计方法，从样本集数据中估统计推断理论中的估计方法，从样本集数据中估计这些参数。计这些参数。5.1 统计推断概述统计推断概述500如果已知如果已知i 类的概密类的概密)(ixp r的函数类型，即知道的函数类型，即知道i 类的类的概型，但不知道其中的参数或参数集概型，但不知道其中的参数或参数集，可采用参数估计的方法可采用参数估计的方法，当解得这些参数，当解得这些参数 后后)(ixp r也就确定了。也就确定了。 ),(21qqq=qD qmiLr确定未知参数确定未知参数参数估计参数估计参数估计有两类方法

205、参数估计有两类方法: :1.1.将参数作为非随机量处理，如将参数作为非随机量处理，如矩法估计矩法估计、最大似然估计最大似然估计；2.2.将参数作为随机变量，将参数作为随机变量，贝叶斯估计贝叶斯估计就属此就属此类。类。5.1 统计推断概述统计推断概述501非参数估计非参数估计5.1 统计推断概述统计推断概述当不知道类的概型时，就要采用非参数估计的当不知道类的概型时，就要采用非参数估计的方法，这种方法也称为总体推断，这类方法有：方法，这种方法也称为总体推断，这类方法有：1. p-1. p-窗法窗法2. 2. 有限项正交函数级数逼近法有限项正交函数级数逼近法3. 3. 随机逼近法随机逼近法502基本

206、概念基本概念母体（总体）：母体（总体）：一个模式类称为一个一个模式类称为一个总体总体或或母体母体5.1 统计推断概述统计推断概述母体的母体的子样子样：一个模式类中某些模式：一个模式类中某些模式( (即母体中的即母体中的 一些元素一些元素) )的集合称为这个的集合称为这个母体的子样母体的子样。母体的。母体的子样含有母体的某些信息，可以通过构造子样含有母体的某些信息，可以通过构造样本样本的函数的函数来获得。来获得。统计量：统计量：一般来说，每一个样本都包含着母体的某一般来说，每一个样本都包含着母体的某些信息，为了估计未知参数就要把有用的信息些信息，为了估计未知参数就要把有用的信息从样本中抽取出来。

207、为此，要构造训练样本的从样本中抽取出来。为此，要构造训练样本的某种函数，这种函数在统计学中称为统计量。某种函数，这种函数在统计学中称为统计量。503基本概念基本概念经验分布：经验分布：由样本推断的分布称为经验分布。由样本推断的分布称为经验分布。5.1 统计推断概述统计推断概述数学期望、方差等数学期望、方差等理论量（或理论分布）：理论量（或理论分布）：参数空间：参数空间：在统计学中，把未知参数在统计学中，把未知参数 的可能值的的可能值的集合称为参数空间，记为集合称为参数空间，记为Q Q。点估计、估计量：点估计、估计量：针对某未知参数针对某未知参数 构造一个统计构造一个统计量作为量作为 的估计的估

208、计 ，这种估计称为点估计。，这种估计称为点估计。 称为称为 的估计量。的估计量。504基本概念基本概念5.1 统计推断概述统计推断概述 为了准确地对某一类的分布进行参数估计或总为了准确地对某一类的分布进行参数估计或总体推断，应只使用该类的样本。体推断，应只使用该类的样本。就是说在进行参数估计时，应对各类进行独立就是说在进行参数估计时，应对各类进行独立的参数估计或总体推断。因此在以后的论述中，如的参数估计或总体推断。因此在以后的论述中，如无必要，不特别言明类别。无必要，不特别言明类别。 区间估计：区间估计：在一定置信度条件下估计某一未知参数在一定置信度条件下估计某一未知参数 的取值范围，称之为置

209、信区间，这类估计成为的取值范围，称之为置信区间，这类估计成为区间估计。区间估计。505506基本概念基本概念5.1 统计推断概述统计推断概述渐近无偏估计渐近无偏估计：即即 。当不能对所当不能对所有有 的都有的都有 时，希望估计量时，希望估计量 是渐是渐近无偏估计。近无偏估计。 507基本概念基本概念5.1 统计推断概述统计推断概述均方收敛均方收敛:均方逼近均方逼近: :均方收敛均方收敛:又称相合估计又称相合估计一致估计一致估计: : 当样本无限增多时，估计量当样本无限增多时，估计量 依概依概率收敛于率收敛于 ，508 52 52 参数估计参数估计第五章第五章 统计决策中的训练、学习统计决策中的

210、训练、学习 与错误率测试、估计与错误率测试、估计5095.2 参数估计参数估计5.2.1 5.2.1 均值矢量和协方差阵的矩法估计均值矢量和协方差阵的矩法估计5.2.2 5.2.2 最大似然估计最大似然估计(MLE)(MLE)5.2.3 5.2.3 贝叶斯估计贝叶斯估计(BE)(BE)5105.2 参数估计参数估计均值矢量和协方差阵的矩法估计均值矢量和协方差阵的矩法估计矩法估计矩法估计是用样本是用样本( (的统计的统计) )矩作为总体矩作为总体( (理论理论) )矩的估矩的估值。若类的概型为正态分布，我们用矩法估计出类的值。若类的概型为正态分布，我们用矩法估计出类的均值矢量和协方差阵后，类的概

211、密也就完全确定了。均值矢量和协方差阵后，类的概密也就完全确定了。均值矢量均值矢量: 均值无偏估计均值无偏估计: 5115.2 参数估计参数估计均值矢量和协方差阵的矩法估计均值矢量和协方差阵的矩法估计协方差阵协方差阵 :5125.2 参数估计参数估计均值矢量和协方差阵的矩法估计均值矢量和协方差阵的矩法估计协方差阵协方差阵 :协方差阵无偏估计协方差阵无偏估计 :或或5135.2 参数估计参数估计设设和和是由是由个样本算得的均矢和协方差阵，个样本算得的均矢和协方差阵，则可采用则可采用递推公式递推公式进行估算进行估算若再加入一个新的样本若再加入一个新的样本初始值初始值:)(11)(1NmxNNmNr

212、rr rr r- -+ + += =+ +均值矢量和协方差阵的矩法估计均值矢量和协方差阵的矩法估计5145.2 参数估计参数估计协方差矩阵的递推估计式协方差矩阵的递推估计式: 均值矢量和协方差阵的矩法估计均值矢量和协方差阵的矩法估计+=+-=11)1() 1(11NjjjNmNmNNxxNrrrr11)(12)()(111111+=+-+-=NNNjNjjxxNxNmNNmNmNNxxNrrrrrrrr)()(11)(111NmxNmxNNCNNNNrrrr-+-=+F=-=-=)1 () 1 () 1 (111111xxxxmmxxCrrrrrrrr初始值初始值:5155.2 参数估计参数估

213、计均值矢量和协方差阵的矩法估计均值矢量和协方差阵的矩法估计5165.2 参数估计参数估计最大似然估计最大似然估计(MLE)(Maximum Likelihood Estimate) 如同如同矩法估计矩法估计一样，一样，最大似然估计最大似然估计要求要求已知已知总体的概型总体的概型，即概密的具体函数形式，它也将被，即概密的具体函数形式，它也将被估计量作为确定性的变量对待。但最大似然估计估计量作为确定性的变量对待。但最大似然估计适用范围比矩法估计更宽一些，可以用于不是正适用范围比矩法估计更宽一些，可以用于不是正态分布的情况。态分布的情况。最大似然估计最大似然估计是参数估计中最重要的方法。是参数估计中

214、最重要的方法。5175.2 参数估计参数估计最大似然估计最大似然估计(MLE)(Maximum Likelihood Estimate) 似然函数似然函数: :当当个随机样本取定值个随机样本取定值时，时，称为相对于称为相对于的的的的似然函数似然函数。 联合概密联合概密 设一个总体设一个总体的概密为的概密为，其中，其中是一个是一个未知参数集，未知参数集，5185.2 5.2 参数估计参数估计最大似然估计最大似然估计(MLE)(Maximum Likelihood Estimate) 由于由于是概密的一个确定性的参数集是概密的一个确定性的参数集, , 因此因此实际上就是条件概密实际上就是条件概密

215、上式中不同的上式中不同的 , ,将不同。将不同。 如果各个如果各个是独立抽取的，则进是独立抽取的，则进一步有：一步有：5195.2 5.2 参数估计参数估计最大似然估计最大似然估计(MLE)(MLE)(Maximum Likelihood Estimate) (Maximum Likelihood Estimate) 最大似然估计：最大似然估计：5205.2 5.2 参数估计参数估计最大似然估计最大似然估计(MLE)(MLE)(Maximum Likelihood Estimate) (Maximum Likelihood Estimate) 在实际中多是独立取样和经常处理正态变量，而在实际中

216、多是独立取样和经常处理正态变量，而且对数函数是单值单调函数，对数似然函数与似然且对数函数是单值单调函数，对数似然函数与似然函数在相同的函数在相同的 处取得最大值。处取得最大值。5215.2 参数估计参数估计最大似然估计最大似然估计(MLE)(Maximum Likelihood Estimate) 在似然函数可微的条件下，在似然函数可微的条件下，求下面微分方程组的解：求下面微分方程组的解：或等价地求或等价地求作为极值的必要条件。作为极值的必要条件。 对数似然方程组对数似然方程组 5225.2 参数估计参数估计最大似然估计最大似然估计(MLE)(Maximum Likelihood Estima

217、te) 需要指出的是：需要指出的是：对于具体问题，有时用上述对于具体问题，有时用上述方法不一定可行，原因之一是似然函数在最大值方法不一定可行，原因之一是似然函数在最大值点处没有零斜率。点处没有零斜率。 求出上面方程组中的一切解及边界值，计算使求出上面方程组中的一切解及边界值，计算使最大的最大的作为作为的最大似然估计。的最大似然估计。 因此，最大似然的关键是必须知道概型。因此，最大似然的关键是必须知道概型。5235.2 参数估计参数估计最大似然估计最大似然估计(MLE)(Maximum Likelihood Estimate) 下面我们以多维正态分布为例进行说明。下面我们以多维正态分布为例进行说

218、明。（1 1）假设）假设是已知的，未知的只是均值是已知的，未知的只是均值，则：，则：5245.2 参数估计参数估计最大似然估计最大似然估计(MLE)(Maximum Likelihood Estimate) 这说明，样本总体的未知均值的最大似然估计这说明，样本总体的未知均值的最大似然估计就是训练样本的平均值。它的几何解释就是：若把就是训练样本的平均值。它的几何解释就是：若把N N个样本看成是一群质点，则样本均值便是它们的个样本看成是一群质点，则样本均值便是它们的质心。质心。525526可见，正态分布中的协方差阵可见，正态分布中的协方差阵的最大似然估的最大似然估计量等于计量等于N N个矩阵的算术

219、平均值。个矩阵的算术平均值。527（3 3）对于一般的多维正态密度的情况，计算方法）对于一般的多维正态密度的情况，计算方法完全是类似的。最后的结果是：完全是类似的。最后的结果是：可以证明上式的均值是无偏估计，但协方差阵可以证明上式的均值是无偏估计，但协方差阵并不是无偏估计，无偏估计是：并不是无偏估计，无偏估计是：5285.2 参数估计参数估计贝叶斯估计贝叶斯估计(BE)考考虑虑到到的各种取的各种取值值，我，我们应们应求求在在空空间间中的期望，即平均中的期望，即平均损损失：失： 5295.2 参数估计参数估计贝叶斯估计贝叶斯估计(BE)5305.2 参数估计参数估计贝叶斯估计贝叶斯估计(BE)

220、不同的具体定义，可得到不同不同的具体定义，可得到不同的最佳贝叶斯估计。比如，可以用平方误差作为的最佳贝叶斯估计。比如，可以用平方误差作为代价，此时：代价，此时：上式中，对于上式中，对于于是：于是： 5315.2 参数估计参数估计贝叶斯估计贝叶斯估计(BE)由于由于是非负的，是非负的，只出现在内层积分中，关于只出现在内层积分中，关于使使最小等价于：最小等价于：为求为求极小，令极小，令5325.2 参数估计参数估计贝叶斯估计贝叶斯估计(BE)从而可得：从而可得：5335.2 参数估计参数估计贝叶斯估计贝叶斯估计(BE)下面介绍估计下面介绍估计 所涉及的其它公式或近似算式：所涉及的其它公式或近似算式

221、：由于各样本是独立抽取的，故它们条件独立，即有由于各样本是独立抽取的，故它们条件独立，即有由贝叶斯定理知：由贝叶斯定理知：5345.2 参数估计参数估计贝叶斯估计贝叶斯估计(BE)5355.2 参数估计参数估计贝叶斯估计贝叶斯估计(BE)536作业：作业：P170 5.1, 5.2, 5.353754 概密的窗函数估计法 第五章第五章 统计决策中的训练、学习统计决策中的训练、学习 与错误率测试、估计与错误率测试、估计538设设 个样本个样本 是从上述概密为是从上述概密为 的总的总体中独立抽取的，体中独立抽取的， 个样本中有个样本中有 个样本落入区域个样本落入区域 中的概率中的概率 服从离散随机

222、变量的二项分布服从离散随机变量的二项分布539令令 为众数，如果为众数，如果 不是整数，则不是整数，则: 即即 等于等于 的整数部分；的整数部分；如果如果 是整数，则是整数，则: 和和540由于：由于：所以：所以：这这里里 是是 的估计，当的估计，当 较大较大 较小时上式的近似较小时上式的近似程度是足够的。程度是足够的。 5415.4 概密的窗函数估计法概密的窗函数估计法概率密度的基本估计式概率密度的基本估计式 当固定当固定 时，对时，对 的最大似然估计的最大似然估计 ，由概率论知，由概率论知， 的数学期望的数学期望 。5425.4 概密的窗函数估计法概密的窗函数估计法概率密度的基本估计式概率

223、密度的基本估计式设区域设区域R的体积为的体积为V，我们取，我们取R足够小，使足够小，使=RVxpxdxpP)()(rrr设设)( xpr是是)(xpr的估计，由上面二式有的估计，由上面二式有VxpxdxpPNkR)()(rrr=于是可得于是可得5435.4 概密的窗函数估计法概密的窗函数估计法概率密度的基本估计式概率密度的基本估计式显然显然是是的基本估的基本估计计式，它与式，它与有关，有关，显显然然和和有一定的有一定的误误差。差。 理理论论上，要使上，要使 R0 V0，同，同时时k，N。 而而实际实际估估计时计时体体积积不是任意的小，且不是任意的小，且样样本本总总数数总总是存在是存在误误差。差

224、。 也是有限的，所以也是有限的，所以5445.4 概密的窗函数估计法概密的窗函数估计法概率密度的基本估计式概率密度的基本估计式为了提高为了提高处的概密处的概密)(xpr的估计精度，我们根据的估计精度，我们根据理论，可以采用如下步骤以尽量满足理论要求：理论，可以采用如下步骤以尽量满足理论要求：极限极限 构造一包含构造一包含的区域序列的区域序列各区域各区域的体积的体积满足满足 相对区域相对区域作估计实验，对作估计实验，对取取N个样本个样本进行估计，设有进行估计，设有个样本落入个样本落入样本数目应满足样本数目应满足中，中，5455465475485.4 概密的窗函数估计法概密的窗函数估计法Parze

225、n窗法窗法为能用函数描述区域为能用函数描述区域NR和对落入和对落入NR的样本计的样本计数，数，定义窗函数定义窗函数),(21=nuuuuLr=j其它当,0, 2 , 1,21,1)(niuuiLr 这样，这样，)(ur rj j以函数值以函数值1界定了一个以原点为中界定了一个以原点为中心、棱长为心、棱长为1的的n维超立方体。维超立方体。5495.4 概密的窗函数估计法概密的窗函数估计法Parzen窗法窗法 如果一个样本如果一个样本jxr落入以落入以 xr为为中心以中心以Nh为棱长的超立方体为棱长的超立方体NR内时则计数为内时则计数为1 ，否则计数为，否则计数为 0，我们可以利用窗函数我们可以利

226、用窗函数)(xrj实现实现这个约定，即这个约定，即落入该立方体落入该立方体NR的样本数的样本数5505515.4 概密的窗函数估计法概密的窗函数估计法Parzen窗法窗法上面所讲的是从构造上导出了估计式，所取的窗函上面所讲的是从构造上导出了估计式，所取的窗函数即迭加基函数为数即迭加基函数为 维方窗维方窗(柱柱)函数。事实上只要窗函数。事实上只要窗函数满足下面的两个条件函数满足下面的两个条件:由式由式 构造的估计式就是概密函数。构造的估计式就是概密函数。 5525.4 概密的窗函数估计法概密的窗函数估计法Parzen窗法窗法 按照上面的条件，除了选择方窗外，还可以选择按照上面的条件，除了选择方窗

227、外，还可以选择其它的满足上述其它的满足上述两个条件的函数作窗函数。下面列出两个条件的函数作窗函数。下面列出几个一维窗函数的例子，几个一维窗函数的例子，n维的窗函数可用乘积的方维的窗函数可用乘积的方法由一维函数构造。法由一维函数构造。 指数窗函数指数窗函数 uu-=jexp)( 方窗函数方窗函数 =j其它,021,1)(uu 正态窗函数正态窗函数 -p=j221exp21)(uu 三角窗函数三角窗函数 -=j1,01,1)(uuuu553下面进一步讨论窗宽下面进一步讨论窗宽 对估计的影响对估计的影响:5.4 概密的窗函数估计法概密的窗函数估计法Parzen窗法窗法定义定义:于是估计式表示成于是估

228、计式表示成:影响影响的幅度和宽度。的幅度和宽度。注意到注意到: 可看出可看出 5545.4 概密的窗函数估计法概密的窗函数估计法Parzen窗法窗法若若Nh较大较大，则，则)(jNxxrr-d幅度将较小，而宽幅度将较小，而宽度增大度增大)(xpNr是是N个低幅缓变个低幅缓变宽的函数迭加宽的函数迭加,)(xpNr较平较平滑，不能跟上滑，不能跟上 的变化，分辨率较低。的变化，分辨率较低。)(xpr5555565.4 概密的窗函数估计法概密的窗函数估计法Parzen窗法窗法估估计计量量 是一随机变量，它依赖于随机的训是一随机变量，它依赖于随机的训练样本，所以估计量的性能只能用统计性质表示。练样本，所

229、以估计量的性能只能用统计性质表示。在在满满足下列条件下足下列条件下 是是渐近无偏估计渐近无偏估计、均方收均方收敛敛、均方逼近均方逼近 、且是、且是渐近正态分布渐近正态分布。 概密概密)(xpr r在在xr r处连续处连续 窗函数满足下列条件窗函数满足下列条件0)(jur =j1)(udurr j)(supuurr 0)(lim1=j=niiuuurr5575.4 概密的窗函数估计法概密的窗函数估计法Parzen窗法窗法估估计计量量 是一随机变量，它依赖于随机的训是一随机变量，它依赖于随机的训练样本，所以估计量的性能只能用统计性质表示。练样本，所以估计量的性能只能用统计性质表示。在在满满足下列条

230、件下足下列条件下 是是渐近无偏估计渐近无偏估计、均方收均方收敛敛、均方逼近均方逼近 、且是、且是渐近正态分布渐近正态分布。 窗宽限制窗宽限制 对样本的要求对样本的要求558(1) (1) 是是 的的渐近无偏估计渐近无偏估计证明：559560P窗法的特点窗法的特点 适用范围广，无论概密是规则的或不规则的、单峰适用范围广，无论概密是规则的或不规则的、单峰的或多峰的。的或多峰的。但它但它要求样本分布较好且数量要大要求样本分布较好且数量要大，显然这也是一，显然这也是一个良好估计所必须的，但它的取样过程的操作个良好估计所必须的，但它的取样过程的操作增加了取样工作的复杂性。增加了取样工作的复杂性。窗函数选

231、取得当有利于提高估计的精度和减少样本窗函数选取得当有利于提高估计的精度和减少样本的数量。的数量。561（a）图中，图中，p(x)是均值为零、是均值为零、方差为方差为1的一维正态分布，的一维正态分布，窗函数选择为正态窗函数：窗函数选择为正态窗函数：h1为可调节参量。于是：为可调节参量。于是：562（a）由结果曲线可以看出，由结果曲线可以看出，样本量越大，估计越精样本量越大，估计越精确；同时，也可以看出确；同时，也可以看出窗口选择是否适当对估窗口选择是否适当对估计结果有一定影响。计结果有一定影响。 563和和 同上同上由图中曲线可以看出，由图中曲线可以看出，当当N N 较小时，窗函数较小时，窗函数

232、对估计结果影响较大，对估计结果影响较大，其估计结果与真实分其估计结果与真实分布相差较远；当布相差较远；当N N 增增大时，估计结果与真大时，估计结果与真实分布较为接近。实分布较为接近。5645.4 概密的窗函数估计法概密的窗函数估计法kN-近邻估计法近邻估计法在在P窗法中，把体积窗法中，把体积作为作为的函数导致的函数导致对估计结果影响很大。例如对估计结果影响很大。例如当当选得太小将导致大部分区域是空的，会使选得太小将导致大部分区域是空的，会使不稳定；不稳定；选得太大，则选得太大，则较平坦，将丢失较平坦，将丢失的一些重要空间变化。的一些重要空间变化。当当近邻元估计法是克服这个问题的一个可能的方法

233、。近邻元估计法是克服这个问题的一个可能的方法。5655.4 概密的窗函数估计法概密的窗函数估计法kN-近邻估计法近邻估计法基本思想：把含基本思想：把含点的序列区域的体积点的序列区域的体积作为落入作为落入中样本数中样本数的函数，而不是直接作为的函数，而不是直接作为的函数。我们可以预先确定的函数。我们可以预先确定是是的某个函数，然后在的某个函数，然后在点附近选择一点附近选择一“紧凑紧凑”区域，区域，个邻近样本。个邻近样本。实验样本数实验样本数让它只含让它只含点附近概密较大，则包含点附近概密较大，则包含个样本的区域个样本的区域如果如果体积自然就相对的小；体积自然就相对的小；点附近概密较小，则区域体积

234、就较大。点附近概密较小，则区域体积就较大。个邻近样本而扩展到高密度个邻近样本而扩展到高密度如果如果显然，当区域为含有显然，当区域为含有区时，扩展过程必然会停止。区时，扩展过程必然会停止。5665.4 概密的窗函数估计法概密的窗函数估计法kN-近邻估计法近邻估计法如果满足条件如果满足条件 5675.4 概密的窗函数估计法概密的窗函数估计法kN-近邻估计法近邻估计法5685.4 概密的窗函数估计法概密的窗函数估计法kN-近邻估计法近邻估计法-2 0 210.01.00.10.010.001N=1, KN=1-2 0 210.01.00.10.010.001-2 0 210.01.00.10.010

235、.001-2 0 210.01.00.10.010.001-2 0 210.01.00.10.010.001-2 0 210.01.00.10.010.001-2 0 210.01.00.10.010.001-2 0 210.01.00.10.010.001N=16, KN=4N=256, KN=16N= , KN= 569作业作业P170 5.7 5.857057155 55 有限项正交函数级数逼近法有限项正交函数级数逼近法第五章第五章 统计决策中的训练、学习统计决策中的训练、学习 与错误率测试、估计与错误率测试、估计57255 有限项正交函数级数逼近法有限项正交函数级数逼近法设有设有个抽自

236、同一母体个抽自同一母体 的样本的样本用于估用于估计总体概密计总体概密，我们将概密，我们将概密的估计的估计表示成表示成有限项正交级数有限项正交级数式中，式中，是某一正交函数集是某一正交函数集的基函数，的基函数，为待定系数。为待定系数。应根据应根据 的特点适当选择的特点适当选择 以期在固定的以期在固定的项数下减小误差，项数项数下减小误差，项数R取得越大近似得就越好。取得越大近似得就越好。最小积分平方逼近方法最小积分平方逼近方法57355 有限项正交函数级数逼近法有限项正交函数级数逼近法 估计估计与真值与真值之间的误差可用下式测度之间的误差可用下式测度式中，式中， 是特征空间，是特征空间，是权函数，

237、显然是权函数，显然越小，我们得到的估计从总体上讲就越精确。越小，我们得到的估计从总体上讲就越精确。将将 的具体表示代入上式得：的具体表示代入上式得： 最小积分平方逼近方法最小积分平方逼近方法574上式的上式的是是的二次函数，因此使的二次函数，因此使达到最小值的达到最小值的必要且只要满足：必要且只要满足：由此可得：由此可得：从而有：从而有：575 令令是是带权带权函数函数的正交函数集，即的正交函数集，即 576则有则有:若若是在是在下的规范化的正交函数集，即下的规范化的正交函数集，即则有则有:将所求得的最佳系数将所求得的最佳系数代入式代入式。便可以得到便可以得到577的的计计算式可写成算式可写成

238、迭代形式迭代形式。 令令，若，若表示用前表示用前个样本所求得的系数个样本所求得的系数个样本后，个样本后，当加入第当加入第初始系数初始系数:，显显然然。 578同理可得到同理可得到 的的迭代形式迭代形式。 初始值初始值:579 前面介绍的方法中被逼近的函数是概密，对于这种前面介绍的方法中被逼近的函数是概密，对于这种幅值大小变化较剧烈的函数，须用幅值大小变化较剧烈的函数，须用较多的项较多的项才可能在整才可能在整个空间中有较好的逼近。个空间中有较好的逼近。 为减少计算量为减少计算量, 在样本出现较密集的区域（即概密在样本出现较密集的区域（即概密取值较大的区域）中，应要求逼近精度高些；而在样取值较大的

239、区域）中，应要求逼近精度高些；而在样本出现稀疏的区域（即概密取值较小的区域）中，可本出现稀疏的区域（即概密取值较小的区域）中，可以让逼近精度低一些。以让逼近精度低一些。 这样分别对待会使在相同的训练样本下总的误判这样分别对待会使在相同的训练样本下总的误判概率较小。因此应考虑概率较小。因此应考虑加权的最小均方差逼近加权的最小均方差逼近。580对于对于c类问题，设类概密和类概率分别类问题，设类概密和类概率分别为为)(ixp r r和和)(iP ), 2 , 1(ciLL= =，则混合概密为，则混合概密为 = = = =ciiixpPxp1)()()(r rr r设对每类的概密设对每类的概密)(ix

240、p r r的估计的估计)(ixp r r用正交函用正交函数有限项表示为数有限项表示为 = =j j= = RjjijixCxp1)()()( r rr r581考虑以混合概密作为权值的加权均方差考虑以混合概密作为权值的加权均方差: 求求的最小值，有如下的定理：的最小值，有如下的定理：记为记为，其中，其中，若取各类的概率若取各类的概率为使上面所确定的为使上面所确定的达到最小值的达到最小值的近似满足线性方程组近似满足线性方程组:设有设有 个样本个样本，其中有，其中有个样本属于个样本属于类，类，582其中其中:583求得求得后就能构造各类的概密逼近式：后就能构造各类的概密逼近式：584解：解：用正交

241、的二维用正交的二维Hermite多项式来构成正交函数集。多项式来构成正交函数集。例：用逼近法求如下模式类别的例：用逼近法求如下模式类别的 和和 的估计。的估计。 585586对于对于 1,N1=7,系数为系数为587对于对于 2,N2=6,系数为系数为588使用最小错误判决规则使用最小错误判决规则:若只取线性项，则为若只取线性项，则为122令令则则判别界面方程为判别界面方程为589122590作业作业: 5.9591模式识别主讲主讲： 蔡宣平蔡宣平 教授教授 电话电话： 7344173441（O O）,73442,73442（H H）E-mailE-mail：单位单位: : 电子科学与工程学院

242、信息工程系电子科学与工程学院信息工程系592第六章第六章 最近邻方法最近邻方法6.1 最近邻决策规则最近邻决策规则6.2 剪辑最近邻法剪辑最近邻法6.3 实例实例593最近邻方法最近邻方法最近邻决策规则最近邻决策规则1-NN594最近邻方法最近邻方法最近邻决策规则最近邻决策规则k-NN 对于一个待识别模式对于一个待识别模式x, 分别计算它与分别计算它与个已知类别的样本个已知类别的样本 的距离的距离, 取取k个最近邻样本个最近邻样本,这这k个样本中哪一类最多个样本中哪一类最多, 就判属哪一类。即：就判属哪一类。即：如果如果则则显然显然595剪辑最近邻方法剪辑最近邻方法剪辑最近邻法剪辑最近邻法对于

243、两类问题，设将已知类别的样本集对于两类问题，设将已知类别的样本集 分成参照分成参照集集 和测试集和测试集 两部分，这两部分没有公共元素，两部分，这两部分没有公共元素，它们的样本数各为它们的样本数各为NR和和NT，NR+NT=N。利用参照集。利用参照集 中的样本中的样本 采用最近邻规则对已知类别的采用最近邻规则对已知类别的测试集测试集 中的每个样本中的每个样本 进行分类，剪进行分类，剪辑掉辑掉 中被错误分类的样本。中被错误分类的样本。若若是是的最近邻元，剪辑掉不的最近邻元，剪辑掉不与与 同类的同类的 ，余下的判决正确的样本组成剪辑样，余下的判决正确的样本组成剪辑样本集本集 ，这一操作称为剪辑。，

244、这一操作称为剪辑。596剪辑最近邻方法剪辑最近邻方法剪辑最近邻法剪辑最近邻法获得剪辑样本集获得剪辑样本集 后，对待识模式后，对待识模式 采用最近采用最近邻规则进行分类。邻规则进行分类。如果如果则则这里这里597剪辑最近邻方法剪辑最近邻方法剪辑剪辑k-NN 最近邻法最近邻法 剪辑最近邻法可以推广至剪辑最近邻法可以推广至k近邻法中，具体的近邻法中，具体的做法是：第一步用做法是：第一步用kNN 法进行剪辑，第二步用法进行剪辑，第二步用1NN 法进行分类。法进行分类。 如果样本足够多，就可以重复地执行剪辑程序，如果样本足够多，就可以重复地执行剪辑程序，以进一步提高分类性能。称为重复剪辑最近邻法。以进一

245、步提高分类性能。称为重复剪辑最近邻法。598599实例：实例：以现金识别的数据作为模式样本进行最近邻法分类。以现金识别的数据作为模式样本进行最近邻法分类。600模式识别主讲主讲： 蔡宣平蔡宣平 教授教授 电话电话： 7344173441（O O）,73442,73442（H H）E-mailE-mail：单位单位: : 电子科学与工程学院信息工程系电子科学与工程学院信息工程系601第七章第七章 特征提取与选择特征提取与选择n 类别可分性判据类别可分性判据n 离散离散K-LK-L变换及其在特征提取变换及其在特征提取 与选择中的应用与选择中的应用n 特征选择中的直接挑选法特征选择中的直接挑选法60

246、2第七章第七章 特征提取与选择特征提取与选择 7.1 7.1 概概 述述603 模式识别的三大核心问题模式识别的三大核心问题: :第七章第七章 特征提取与选择特征提取与选择7.1概述概述特征数据采集特征数据采集分类识别分类识别特征提取与选择特征提取与选择 分类识别的正确率取决于对象的表示、训练学分类识别的正确率取决于对象的表示、训练学习和分类识别算法，我们在前面各章的介绍中详细习和分类识别算法，我们在前面各章的介绍中详细讨论了后两方面的内容。本章介绍的特征提取与选讨论了后两方面的内容。本章介绍的特征提取与选择问题则是对象表示的一个关键问题。择问题则是对象表示的一个关键问题。604 通常在得到实

247、际对象的若干具体特征之通常在得到实际对象的若干具体特征之后，再由这些原始特征产生出对分类识别最后，再由这些原始特征产生出对分类识别最有效、数目最少的特征，这就是特征提取与有效、数目最少的特征，这就是特征提取与选择的任务。从本质上讲，我们的目的是使选择的任务。从本质上讲，我们的目的是使在最小维数特征空间中异类模式点相距较远在最小维数特征空间中异类模式点相距较远（类间距离较大），而同类模式点相距较近（类间距离较大），而同类模式点相距较近（类内距离较小）。（类内距离较小）。 第七章第七章 特征提取与选择特征提取与选择7.1概述概述6057.1概述概述特征提取与选择的两个基本途径特征提取与选择的两个基

248、本途径主要方法有：主要方法有：分支定界法分支定界法、用回归建模技术确定相用回归建模技术确定相关特征关特征等方法。等方法。（1 1）直接选择法：）直接选择法：当实际用于分类识别的特征数目当实际用于分类识别的特征数目d d 确定后，直接从已获得的确定后，直接从已获得的n n 个原始特征中选出个原始特征中选出d d 个个特征特征 ，使可分性判据，使可分性判据J J 的值满足下式：的值满足下式：式中式中 是是n 个原始特征中的任意个原始特征中的任意d 个特征，个特征，上式表示直接寻找上式表示直接寻找n 维特征空间中的维特征空间中的d 维子空间。维子空间。606（2 2）变换法）变换法，在使判据，在使判

249、据J J 取最大的目标下，对取最大的目标下，对n n 个个原始特征进行变换降维，即对原原始特征进行变换降维，即对原n n 维特征空间进维特征空间进行坐标变换，然后再取子空间。行坐标变换，然后再取子空间。7.1概述概述特征提取与选择的两个基本途径特征提取与选择的两个基本途径主要方法有：主要方法有：基于可分性判据的特征选择基于可分性判据的特征选择、基于基于误判概率的特征选择误判概率的特征选择、离散离散K-LK-L变换法变换法(DKLT)(DKLT)、基基于决策界的特征选择于决策界的特征选择等方法。等方法。6077.2 7.2 类别可分性判据类别可分性判据第七章第七章 特征提取与选择特征提取与选择6

250、087.2 类别可分性判据类别可分性判据 为确立特征提取和选择的准则：引入类别可分性为确立特征提取和选择的准则：引入类别可分性判据，来刻划特征对分类的贡献。为此希望所构造判据，来刻划特征对分类的贡献。为此希望所构造的可分性判据满足下列要求：的可分性判据满足下列要求：构造可分性判据构造可分性判据(1) (1) 与误判概率与误判概率( (或误分概率的上界、下界或误分概率的上界、下界) )有单调关系。有单调关系。 (2) (2) 当特征相互独立时，判据有可加性，即当特征相互独立时，判据有可加性，即 ： 式中，式中，是对不同种类特征的测量值，是对不同种类特征的测量值，表示使用括号中特征时第表示使用括号

251、中特征时第i 类与第类与第j类可分性判据函数。类可分性判据函数。6097.2 类别可分性判据类别可分性判据构造可分性判据构造可分性判据(3) (3) 判据具有判据具有“距离距离”的某些特性，即的某些特性，即 ：，当，当时；时；，当，当时；时；(4) (4) 对特征数目是单调不减，即加入新的特征后，判对特征数目是单调不减，即加入新的特征后，判据值不减。据值不减。 6107.2 类别可分性判据类别可分性判据构造可分性判据构造可分性判据值得注意的是值得注意的是：上述的构造可分性判据的要求，即：上述的构造可分性判据的要求，即“单调性单调性”、“叠加性叠加性”、“距离性距离性”、“单调不单调不减性减性”

252、。在实际应用并不一定能同时具备，但并不。在实际应用并不一定能同时具备，但并不影响它在实际使用中的价值。影响它在实际使用中的价值。 6117.2 类别可分性判据类别可分性判据7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据一般来讲，不同类的模式可以被区分是由于它们一般来讲，不同类的模式可以被区分是由于它们所属类别在特征空间中的类域是不同的区域。所属类别在特征空间中的类域是不同的区域。显然，区域重叠的部分越小或完全没有重叠，类显然，区域重叠的部分越小或完全没有重叠，类别的可分性就越好。别的可分性就越好。因此可以用距离或离差测度（散度）来构造类别因此可以用距离或离差测度（散度）来

253、构造类别的可分性判据。的可分性判据。 612( (一一) ) 点与点的距离点与点的距离 ( (二二) ) 点到点集的距离点到点集的距离用用均方欧氏距离均方欧氏距离表示表示7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据613( (三三) ) 类内及总体的均值矢量类内及总体的均值矢量 各类模式的总体均值矢量各类模式的总体均值矢量 类的均值矢量：类的均值矢量： 为相应类的先验概率，为相应类的先验概率，当用统计量代替先验概当用统计量代替先验概率时，总体均值矢量可表示为：率时，总体均值矢量可表示为：7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据614( (四四

254、) ) 类内距离类内距离 类内均方欧氏距离类内均方欧氏距离 类内均方距离也可定义为：类内均方距离也可定义为： 7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据615( (五五) ) 类内离差矩阵类内离差矩阵 显然显然( (六六) ) 两类之间的距离两类之间的距离 7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据616( (七七) )各类模式之间的总的均方距离各类模式之间的总的均方距离 当取欧氏距离时，总的均方距离为当取欧氏距离时，总的均方距离为7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据617( (八八) ) 多类情况下总的类内、

255、类间及总体离差矩阵多类情况下总的类内、类间及总体离差矩阵 类内离差类内离差类间离差类间离差总体离差总体离差 易导出易导出7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据6187.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据6197.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据在特征空间中，当类内模式较密聚，而不同类的在特征空间中，当类内模式较密聚，而不同类的模式相距较远时，从直觉上我们知道分类就较容模式相距较远时，从直觉上我们知道分类就较容易，由各判据的构造可知，这种情况下所算得的易，由各判据的构造可知，这种情况下所算得的判据值也较大

256、。由判据的构造我们还可以初步了判据值也较大。由判据的构造我们还可以初步了解运用这类判据的原则和方法。解运用这类判据的原则和方法。6207.2 7.2 类别可分性判据类别可分性判据7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据考虑两类问题。上图是一维的两类概率分布密度。考虑两类问题。上图是一维的两类概率分布密度。 (a) (a) 表示两类是完全可分的。表示两类是完全可分的。(b)(b)是完全不可分的。是完全不可分的。 621可用两类概密函数的重叠程度来度量可分性，可用两类概密函数的重叠程度来度量可分性，构造基于类概密的可分性判据。此处的所谓重叠构造基于类概密

257、的可分性判据。此处的所谓重叠程度是指两个概密函数相似的程度。程度是指两个概密函数相似的程度。7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据6227.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据( (一一) ) BhattacharyyaBhattacharyya 判据判据( (J JB B) )受相关概念与应用的启发，我们可以构造受相关概念与应用的启发，我们可以构造B- -判判据，它的计算式为据，它的计算式为 W W- -= =xdxpxpJBr rr rr r2121)()(ln 式中式中W W表示特征空间。在最小误判

258、概率准则下，误判表示特征空间。在最小误判概率准则下，误判概率有概率有 BJPPeP- - exp)()()(21210 6237.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据 P eP ePp xdxPp xdx0112212( )min( )min()()()()= = =+ + r rr rr rr rW WW W Pp xPp xdx1122min() (),() ()= = r rr rr rW W Pp xPp xdx11221 2() () () ()/ r rr rr rW W PPp xp x121 212() ()() ()/= = r r

259、r rW W1 2/dxr r 121 2/() ()expPPJB= =- - 证明：设证明：设为误分概率，则最小误分概率为：为误分概率，则最小误分概率为：6247.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据（二）（二）Chernoff判据判据 ( (JC) )6257.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据JC 具有如下性质：具有如下性质： (1)(1)对一切对一切01 s，0 CJ； (2)(2)对一切对一切01 s，Jp xp xC= = =012()()r rr r ； (3)(3)当参数当参数s和和(

260、() )1- - s互调时，有对称性互调时，有对称性, ,)1 ;,();,(1221sJsJCC- -= = (4)(4)当当r rx的各分量的各分量nxxx,21LL相互独立时，相互独立时， = = =nllCnCxsJxxxsJ121);(),;(LL6267.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据(5)(5)当当r rx的各分量的各分量nxxx,21LL相互独立时，有相互独立时，有 )( ),;(),;(121121nkxxxxsJxxxsJkkCkC - - -LLLL(6)(6)最小误判概率最小误判概率 ) 10( );,(exp)()()

261、(211210 0) (a,b0)因为，当因为，当 0 0 s s 1 1 时时 f f (s) = -a(s) = -as sb b1-s1-s(ln a - ln b)(ln a - ln b)2 2 0 Ch, , 但但Bh比较容易计算，算得比较容易计算，算得结果通常也比较接近结果通常也比较接近Ch，所以在分类器设计分析中，所以在分类器设计分析中Bh、JB也是常用的。也是常用的。641对于对于c类问题，可采用平均类问题，可采用平均B-判据、判据、C-判据、判据、D-判据：判据： 由由JB、JC、JD的定义式结构以及它们与误分概率的的定义式结构以及它们与误分概率的关系可以知道，所选取的特征

262、矢量应使所对应的关系可以知道，所选取的特征矢量应使所对应的JB、JC 、JD尽量大，这样可分性就较好。尽量大，这样可分性就较好。7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据642大盖小问题大盖小问题 在特征空间中，若有某两类间的在特征空间中，若有某两类间的JB、JC或或JD很大，很大，可使平均判据变大，这样就掩盖了某些类对的判据值可使平均判据变大，这样就掩盖了某些类对的判据值较小的情况存在，从而可能降低总的分类正确率，即较小的情况存在，从而可能降低总的分类正确率，即所谓的所谓的大盖小问题大盖小问题。为改善这种情况，可对每个类对。为改善这种情况，可对每个类

263、对的判据采用变换的方法，使对小的判据较敏感。例如，的判据采用变换的方法，使对小的判据较敏感。例如，对对JD ，可采用变换，可采用变换643这样，当这样，当 i和和 j两类模式相距很远时，两类模式相距很远时， JD( i, j)变变得很大，但得很大，但 也只能接近于也只能接近于1。但对于散度。但对于散度JD( i, j) 小的情况，小的情况， 又变得较敏感。于是，总又变得较敏感。于是，总的平均的平均(变换变换)判据为判据为 7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据644同样对于同样对于JB，单类与平均判据分别为：，单类与平均判据分别为：单类：单类：平均

264、判据：平均判据：7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据6457.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据在信息论中，在信息论中，熵熵(Entropy)(Entropy)表示不确定性表示不确定性，熵越，熵越大不确定性越大。可以借用熵的概念来描述各类的可大不确定性越大。可以借用熵的概念来描述各类的可分性。分性。对于对于c c类问题，给定各类的后验概率类问题，给定各类的后验概率 可以写成如下形式：可以写成如下形式：熵的定义：熵的定义：由洛必达法则知：当由洛必达法则知：当 时时6467.2.3 7.2.3 基于后验概率的可分性判

265、据基于后验概率的可分性判据例如：例如：显然这时能实现完全正确的分类识别显然这时能实现完全正确的分类识别 6477.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据6487.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据熵的主要性质：熵的主要性质：(4)(4)其中其中说明当类别较少时，分类识别的不确定性变小。说明当类别较少时，分类识别的不确定性变小。 从特征选择角度看，我们从特征选择角度看，我们应选择使熵最小的那些特应选择使熵最小的那些特征用于分类征用于分类即选用具有最小不确定性的特征进行分即选用具有最小不确定性的特征进行分类是有益的。类是有益的。 64

266、9使熵最小的特征利于分类，取熵的期望：使熵最小的特征利于分类，取熵的期望：广义熵广义熵（具有熵的性质，利于计算）定义定义为为:式中0， 1。不同的值可得不同的可分性度量。当当1时，由洛必达法则可得时，由洛必达法则可得Shannon熵熵当当 =2时，可得平方熵时，可得平方熵650使用使用 判据进行特征提取与选择时，我们的目标是使判据进行特征提取与选择时，我们的目标是使。 同理，我们亦可用点熵在整个特征空间的概率平均同理，我们亦可用点熵在整个特征空间的概率平均作为可分性判据。作为可分性判据。7.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据651第七章第七章 特征提取与选择特

267、征提取与选择7.3 7.3 基于可分性判据进行变换的基于可分性判据进行变换的 特征提取与选择特征提取与选择6527.3 7.3 基于可分性判据进行变换的特征提取与选择基于可分性判据进行变换的特征提取与选择变换变换为特征提取矩阵或变换矩阵为特征提取矩阵或变换矩阵原始特征原始特征 二次特征二次特征6537.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据的变换法 设设SW和和SB分别为原始特征空间中的类内和类分别为原始特征空间中的类内和类间离差矩阵，间离差矩阵，SW*和和SB*分别为变换特征空间中的类分别为变换特征空间中的类内和类间离差矩阵，可知内和类间离差矩阵，可知 SW S WWW*=

268、 =T SW S WBB*= =T根据根据 J1 1=TrS=TrSW W-1-1S SB Bmaxmax或或 J4 4=|S=|SW W+S+SB B|/|S|/|SB B|=|S|=|ST T|/|S|/|SB B| max| max求变换矩阵求变换矩阵 W W。654 在变换域中在变换域中J1为为 )()(Tr)(Tr)(T1T*1*1WSWWSWSSWJBWBW- - -= = =由线性代数可知，对矩阵作相似变换其迹不变，由线性代数可知，对矩阵作相似变换其迹不变，一个方阵的迹等于它的所有特征值之和。设一个方阵的迹等于它的所有特征值之和。设We为正为正交阵，用交阵，用We对对称阵对对称阵

269、SSWB- -1作相似变换使其成为对角阵作相似变换使其成为对角阵,其中其中, i( () )ni, 2 , 1LL= =为为SSWB- -1的特征值，的特征值，We的列矢量的列矢量r rWi为为SSWB- -1相应于相应于 i的特征矢量。由上式可得的特征矢量。由上式可得 （一）对于矩阵迹形式的判据（一）对于矩阵迹形式的判据655假设假设We的列矢量的排列已作适当调整，使的列矢量的排列已作适当调整，使S SW W-1-1S SB B的的特征值特征值 1 1 2 2 n n 。由此可得，在。由此可得，在d d 给给定后，取前定后，取前d d 个较大的特征值所对应的特征矢量个较大的特征值所对应的特征

270、矢量wi( (i=1,2,=1,2,d d) )构造特征提取矩阵构造特征提取矩阵W，即，即: :7.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据的变换法作变换作变换 ，这时对于给定的，这时对于给定的d d所得到的所得到的 达最大值。此方法对达最大值。此方法对J3 3 =TrS=TrSB B/TrS/TrSW W 也适用。也适用。 656（二）对于行列式形式的判据（二）对于行列式形式的判据以以J4为例，由于为例，由于SW是对称正定矩阵，设有非奇异是对称正定矩阵，设有非奇异阵阵A，使，使但一般但一般AST A不是对角阵，设有标准正交矩阵不是对角阵，设有标准正交矩阵V，使，使这里这里 为

271、对角阵，从而为对角阵，从而7.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据的变换法令令U=AV ，因此存在非奇异矩阵因此存在非奇异矩阵U ，使，使 657上面右式两边同时取逆，有上面右式两边同时取逆，有这里这里U及及 分别是特征矢量组成的矩阵分别是特征矢量组成的矩阵(特征矢量矩特征矢量矩阵阵)及特征值对角阵。及特征值对角阵。 7.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据的变换法再与左式相乘，并左乘再与左式相乘，并左乘U ，有，有: 658因为因为设设SW-1SB 的特征值矩阵的特征值矩阵所以所以则则于是于是7.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据

272、的变换法659此处的此处的U 就是前述的就是前述的We。设。设U 的各列已作适当调整的各列已作适当调整，使，使 1 2 n ，对于给定的，对于给定的d，取前，取前d个较大的特个较大的特征值对应的特征矢量构造变换矩阵可使征值对应的特征矢量构造变换矩阵可使J4 取最大值，取最大值，此时此时7.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据的变换法从从J4的构造可知，用的构造可知，用J4作判据作判据 ，不至于选用那些，不至于选用那些只对两类有很好的可分性而对其他各类分类效果不好只对两类有很好的可分性而对其他各类分类效果不好的特征。而对于的特征。而对于J1 =TrSW-1SB，只要一个，只要

273、一个 i很大就会很大就会发生这种情况。发生这种情况。660例例7.1 给定两类模式，其先验概率给定两类模式，其先验概率P( 1)= P( 2) ，均均值矢量分别为值矢量分别为 和和 ，离差阵分别为，离差阵分别为 求基于判据求基于判据J4的最优特征提取。的最优特征提取。解：解： 661为求该特征值应解方程：为求该特征值应解方程：这就是所要求的最优特征提取矩阵。这就是所要求的最优特征提取矩阵。 即即由于由于 是标量，于是有：是标量，于是有：662第七章第七章 特征提取与选择特征提取与选择7.5 7.5 离散离散K-LK-L变换及其在变换及其在 特征提取与选择中的应用特征提取与选择中的应用6637.

274、5.1 离散离散K-L变换（变换（DKLT）DKLT的性质：的性质：1. 使变换后产生的新的分量正交或不相关使变换后产生的新的分量正交或不相关;2. 以部分新分量表示原矢量均方误差最小以部分新分量表示原矢量均方误差最小;3. 使变换矢量更趋确定、能量更趋集中。使变换矢量更趋确定、能量更趋集中。有限离散有限离散K-LK-L变换（变换（DKLTDKLT）, ,又称霍特林又称霍特林(Hotelling)(Hotelling)变换或主分量分解变换或主分量分解, ,它是一种基于目标它是一种基于目标统计特性的最佳正交变换。统计特性的最佳正交变换。6647.5.1 离散离散K-L变换（变换（DKLT）设设n

275、维随机矢量维随机矢量r rLLxx xxn= = (,)12T，其均，其均值矢量值矢量 r rr rxE x= =，相关阵，相关阵 RE xxxr rr r r r= =T，协方，协方差阵差阵 CE xx xxxr rr rr rr rr r= =- - -()()T，r rx经正交变换后经正交变换后产生矢量产生矢量r rLLyy yyn= = (,)12T，665设有标准正交变换矩阵设有标准正交变换矩阵T，（即，（即 TT=I）取前取前m项为项为 的估计值的估计值（称为（称为 的的K-LK-L展开式）展开式）其均方误差为其均方误差为666xtyiir rr r= =在在TT=I的约束条件下的

276、约束条件下,要使均方误差要使均方误差为此作准则函数为此作准则函数由由 可得可得即即667 i是是 的特征值，而的特征值，而 是相应的特征矢量。是相应的特征矢量。由由表明表明:利用上式有利用上式有:7.5.1 离散离散K-L变换（变换（DKLT）在在上上述述的的估估计计式式中中，如如果果不不是是简简单单地地舍舍弃弃后后 (n-m)项项 ， 而而 是是 用用 预预 选选 的的 常常 数数 bi代代 替替 yi, i=m+1,n，此时的估计式为，此时的估计式为:6687.5.1 离散离散K-L变换（变换（DKLT）的均方误差为的均方误差为:（1）最佳的）最佳的bi可通过可通过 求得求得 6697.5

277、.1 离散离散K-L变换（变换（DKLT）6707.5.1 离散离散K-L变换（变换（DKLT）因为因为为非负定阵，故有为非负定阵，故有上述的讨论可归纳为上述的讨论可归纳为: : 当我们用简单的当我们用简单的“截断截断”方式产生估计式时方式产生估计式时, ,使使均方误差最小的正交变换矩阵是随机矢量均方误差最小的正交变换矩阵是随机矢量x x的相关阵的相关阵R Rx x的特征矢量矩阵的特征矢量矩阵; ; 当估计式除了选用当估计式除了选用m m个分量个分量y yi i(i=1,2,m)(i=1,2,m)之外之外, ,还用余下的各还用余下的各y yi i的均值的均值b bi i代替相应的分量时代替相应

278、的分量时, ,使均方使均方误差最小的正交变换矩阵是误差最小的正交变换矩阵是x x的协方差阵。的协方差阵。这表明对于相同的这表明对于相同的m m，第一种估计，第一种估计式比第二种估计式的均方差大。式比第二种估计式的均方差大。671DKLTDKLT的性质的性质(1) (1) 变换后各特征分量正交或不相关变换后各特征分量正交或不相关 的自相关阵和协方差阵为变换后的矢量的各分量是正交的,或不相关的(因为C=R-E(x)E(x)，当E(x)=0时，不相关即是正交)；i=E(yi2),或i=Eyi -E(yi)2 (方差)672673(2)(2)最佳逼近性最佳逼近性(3)(3)使能量向某些分量相对集中，增

279、强使能量向某些分量相对集中，增强随机矢量总体的确定性随机矢量总体的确定性DKLTDKLT的性质的性质674例例: 已知两类样本已知两类样本 试用试用K-LK-L变换做一维特征提取。变换做一维特征提取。解：解：（1 1）（3 3）求求R R的特征值、特征矢量的特征值、特征矢量（2 2）675（4）选选 1 1对应的对应的 作为变换矩阵作为变换矩阵得由由 得变换后的一维模式特征为得变换后的一维模式特征为6767.5.2 基于总的类内、类间离差矩阵、进行特征提取选择基于总的类内、类间离差矩阵、进行特征提取选择6777.5.2 7.5.2 基于总的类内、类间离差矩阵、进行特征提取选择基于总的类内、类间

280、离差矩阵、进行特征提取选择678 基于总的基于总的类内离差矩阵类内离差矩阵 的的DKLTDKLT进行特征提取选择进行特征提取选择7.5.2 基于总的类内、类间离差矩阵、进行特征提取选择基于总的类内、类间离差矩阵、进行特征提取选择，构造准则函数构造准则函数排序：排序：，取前面，取前面个较大的个较大的值对应的值对应的 适用于各类模式的类域在某些分量轴上的投影不适用于各类模式的类域在某些分量轴上的投影不重迭或较少重迭的情况。重迭或较少重迭的情况。679 依据依据 、 作作DKLTDKLT以降低特征维数的最优压缩方法以降低特征维数的最优压缩方法7.5.2 基于总的类内、类间离差矩阵、进行特征提取选择基

281、于总的类内、类间离差矩阵、进行特征提取选择设设L和和U是对称正定阵是对称正定阵WS的特征值对角阵和特征的特征值对角阵和特征矢量矩阵，作如下的白化变换矢量矩阵，作如下的白化变换 I2121T=LL-USUW易知，存在正交阵易知，存在正交阵V可使可使 L=LL-2121TTVUSUVB式中式中L是白化变换后的总的类间离差阵是白化变换后的总的类间离差阵2121T-LL=USUSBB的特征值对角阵。的特征值对角阵。680由于由于BS的秩不大于的秩不大于1- -c，所以，所以SB最多只有最多只有1- -c个非个非零特征值，设非零特征值共有零特征值，设非零特征值共有d个，用这个，用这d个非个非零特征值所对

282、应的特征矢量零特征值所对应的特征矢量), 2 , 1(djvjLLr r= =作变换作变换矩阵，所得的矩阵，所得的d个分量含有原来个分量含有原来n维模式的全部维模式的全部信息。信息。7.5.2 基于总的类内、类间离差矩阵、进行特征提取选择基于总的类内、类间离差矩阵、进行特征提取选择6817.5.2 基于总的类内、类间离差矩阵、进行特征提取选择基于总的类内、类间离差矩阵、进行特征提取选择设设)(21dvvvVr rLLr rr r= =则不损失信息而又达到最小维数的变换矩阵为：则不损失信息而又达到最小维数的变换矩阵为：WVUTTT= =- -L L1 2从而从而r rr rr ryWxVUx=

283、= =- -TTTL L1 2当类数当类数c远比特征矢量维数远比特征矢量维数n 小时，该方法的压缩小时，该方法的压缩性能是十分明显的。性能是十分明显的。682例例7.5.17.5.1两类样本的均值矢量分别为两类样本的均值矢量分别为m1=(4,2)和和m2=(-4,-2),协协方差矩阵分别为：方差矩阵分别为：两类的先验概率相等，试求一维特征提取矩阵。两类的先验概率相等，试求一维特征提取矩阵。解解总的类内离差阵可以算得：总的类内离差阵可以算得：683依据依据SW进行进行DKLT，得到特征值，得到特征值对应的特征向量分别为：对应的特征向量分别为：因为总的均值矢量为：因为总的均值矢量为：故类间离差阵故

284、类间离差阵SB为：为：计算计算J(y1)与与J(y2)：684因为因为J(y1)J(y2),所以选最佳变换矩阵为所以选最佳变换矩阵为下面依据下面依据S SW W和和S SB B作作DKLTDKLT进行最优特征提取。进行最优特征提取。此时此时对对S SB B进行白化变换：进行白化变换：685的非零特征值只有一个，的非零特征值只有一个， 对应的特征矢量为对应的特征矢量为总的最优变换为：总的最优变换为：作业：作业：7.11686第七章第七章 特征提取与选择特征提取与选择7.5 7.5 离散离散K-LK-L变换及其在变换及其在 特征提取与选择中的应用特征提取与选择中的应用687第七章第七章 特征提取与

285、选择特征提取与选择7.7 7.7 特征选择中的直接挑选法特征选择中的直接挑选法特征的选择除了我们前面学习的变换法外特征的选择除了我们前面学习的变换法外, , 也可以也可以在原坐标系中依据某些原则直接选择特征在原坐标系中依据某些原则直接选择特征, , 即我们即我们这节课要学的直接挑选法。这节课要学的直接挑选法。7.7.1 7.7.1 次优搜索法次优搜索法7.7.2 7.7.2 最优搜索法最优搜索法6887.7.1 7.7.1 次优搜索法次优搜索法( (一一) )单独最优的特征选择单独最优的特征选择单独选优法的基本思路是：单独选优法的基本思路是：计算各特征单独使用时的判计算各特征单独使用时的判据值

286、并以递减排序，选取前据值并以递减排序，选取前d d个分类效果最好的特征。个分类效果最好的特征。 这种方法才能选出一组最优特征。这种方法才能选出一组最优特征。一般地讲，即使各特征是统计独立的，这种方法选一般地讲，即使各特征是统计独立的，这种方法选出的出的d d个特征也不一定是最优的特征组合，只有可分性个特征也不一定是最优的特征组合，只有可分性判据判据J J是可分的时候，即是可分的时候，即689( (二二) )增添特征法增添特征法7.7.1 7.7.1 次优搜索法次优搜索法690( (二二) )增添特征法增添特征法7.7.1 7.7.1 次优搜索法次优搜索法设已选入了设已选入了k个特征，它们记为个

287、特征，它们记为Xk，把未选入的，把未选入的n-k个特征个特征xj（j=1,2,n-k)逐个与已选入的特征逐个与已选入的特征Xk组合计算组合计算J 值，若：值，若：则则x1选入，下一步的特征组合为选入，下一步的特征组合为Xk+1=Xk+x1。开。开始时，始时，k=0，X0=F F， 该过程一直进行到该过程一直进行到k=d为止。为止。691( (二二) )增添特征法增添特征法7.7.1 7.7.1 次优搜索法次优搜索法该方法比该方法比“单独最优的特征选择法单独最优的特征选择法”要好，但要好，但其缺点也是明显的：即某特征一旦选入，即使后边其缺点也是明显的：即某特征一旦选入，即使后边的的n-k特征中的

288、某个从组合讲比它好，也无法把它特征中的某个从组合讲比它好，也无法把它剔除。剔除。692( (三三) )剔减特征法剔减特征法7.7.1 7.7.1 次优搜索法次优搜索法该该方方法法也也称称为为顺顺序序后后退退法法(SBS)。这这是是一一种种自自上上而而下下的的搜搜索索方方法法，从从全全部部特特征征开开始始每每次次剔剔除除一一个个特特征征，所所剔剔除除的的特特征征应应使使尚尚保保留留的的特特征征组组合合的值最大的值最大。693( (三三) )剔减特征法剔减特征法7.7.1 7.7.1 次优搜索法次优搜索法则在这轮中则在这轮中x1应该剔除。应该剔除。这里初值这里初值 ，过程直到，过程直到k=n-d为

289、止。为止。6947.7.1 7.7.1 次优搜索法次优搜索法(四四) 增增l 减减r 法（法（l-r 法）法）为了克服前面方法为了克服前面方法 ( (二二) )、( (三三) )中的一旦某特征中的一旦某特征选入或剔除就不能再剔除或选入的缺点，可在选择选入或剔除就不能再剔除或选入的缺点，可在选择过程中加入局部回溯，例如在第过程中加入局部回溯，例如在第k步可先用方法步可先用方法( (二二) )，对已选入的，对已选入的k个特征再一个个地加入新的特征个特征再一个个地加入新的特征到到kl+ +个特征，然后用方法个特征，然后用方法( (三三) )一个个地剔除一个个地剔除r个特个特征，称这种方法为增征，称这

290、种方法为增l减减r法法( (lr- -法法) )。6957.7.2 7.7.2 最优搜索法最优搜索法( (一一) )分支定界法分支定界法(BAB(BAB算法算法) ) 寻寻求求全全局局最最优优的的特特征征选选择择的的搜搜索索过过程程可可用用一一个个树树结构来描述，称其为搜索树或解树。结构来描述，称其为搜索树或解树。总总的的搜搜索索方方案案是是沿沿着着树树自自上上而而下下、从从右右至至左左进进行行，由由于于树树的的每每个个节节点点代代表表一一种种特特征征组组合合，于于是是所所有有可可能的组合都可以被考虑。能的组合都可以被考虑。利利用用可可分分性性判判据据的的单单调调性性采采用用分分支支定定界界策

291、策略略和和值值左左小小右右大大的的树树结结构构，使使得得在在实实际际上上并并不不计计算算某某些些特特征征组组合合而而又又不不影影响响全全局局寻寻优优。这这种种具具有有上上述述特特点点的的快速搜索方法，称为快速搜索方法，称为分支定界算法分支定界算法。6966 6选选2 2的特征选择问题的特征选择问题 (a)(a)搜索树搜索树 (b)(b)搜索回溯示意图搜索回溯示意图7.7.2 7.7.2 最优搜索法最优搜索法BAB算法算法s=0s=1s=2s=3s=4697树的每个节点表示一种特征组合，树的每树的每个节点表示一种特征组合，树的每一级一级各节点表示从其父节点的特征组合中再去掉一个特各节点表示从其父

292、节点的特征组合中再去掉一个特征后的特征组合，其标号征后的特征组合，其标号k表示去掉的特征是表示去掉的特征是xk 。7.7.2 7.7.2 最优搜索法最优搜索法BAB算法算法由于每一级只舍弃一个特征，因此整个搜索树除由于每一级只舍弃一个特征，因此整个搜索树除根节点的根节点的0 0级外，还需要级外，还需要n-d 级，即全树有级，即全树有n-d 级。在级。在6 6个特征中选个特征中选2 2个，故整个搜索树需要个，故整个搜索树需要4 4级，第级，第n-d 级级是叶节点，有个叶节点是叶节点，有个叶节点 。698BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法表示特征数目为表示特征数目为l 的的

293、特征集合。特征集合。表示舍弃表示舍弃s 个特征后余下的特征集合。个特征后余下的特征集合。表示当前节点的表示当前节点的子节点数。子节点数。表示表示集合中元素的数目。集合中元素的数目。表示第表示第s 级当前节点上用来作为下一级可舍级当前节点上用来作为下一级可舍弃特征的特征集合。弃特征的特征集合。699由于从根节点要经历由于从根节点要经历n-dn-d级才能到达叶节点，级才能到达叶节点，s级某节点后继的每一个子节点分别舍弃级某节点后继的每一个子节点分别舍弃 中互不中互不相同的一个特征，从而考虑在相同的一个特征，从而考虑在s+1级可以舍弃的特征级可以舍弃的特征方案数方案数( (即其子节点数即其子节点数)

294、 )qs时，必须使这一级舍弃了时，必须使这一级舍弃了特征特征 后还剩后还剩(n-d)-(s+1)个特征。除了从树的纵个特征。除了从树的纵的方向上一级丢弃一个特征，实际上从树的横的方的方向上一级丢弃一个特征，实际上从树的横的方向上，一个分支也轮换丢弃一个特征。因此后继子向上，一个分支也轮换丢弃一个特征。因此后继子节点数节点数 。 BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法700BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法ss+1n-d(n-d)-(s+1)qsRs节点特征数量节点特征数量701BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法123702BA

295、B算法算法7.7.2 7.7.2 最优搜索法最优搜索法123243703BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法123243543543545445455 6656656566666(x5 , x6)(x4 , x6)(x2 , x6)(x4 , x5)(x3 , x6)(x3 , x4)(x3 , x5)(x2 , x5)(x2 , x4)(x2 , x3)(x1 , x6)(x1 , x5)(x1 , x4)(x1 , x3)(x1 , x2)704BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法123243543543545445455 66566565666

296、66(x5 , x6)(x4 , x6)(x2 , x6)(x4 , x5)(x3 , x6)(x3 , x4)(x3 , x5)(x2 , x5)(x2 , x4)(x2 , x3)(x1 , x6)(x1 , x5)(x1 , x4)(x1 , x3)(x1 , x2)我们的目的我们的目的是求出叶节是求出叶节点对应的所点对应的所有可能的有可能的d d个特征组合个特征组合使得判据使得判据J J的值最大。的值最大。705BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法注意到每个节点都注意到每个节点都可以计算相应的可以计算相应的J J值。值。由于判据由于判据J J值的单调值的单调性，使

297、得：性，使得：上面的不等式表明，任何节点的上面的不等式表明，任何节点的J J值均大于它所属值均大于它所属的各子节点的的各子节点的J J值。值。706BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法搜索过程是从上至下、搜索过程是从上至下、从右至左进行。从右至左进行。四个步骤：四个步骤：1 1、向下搜索、向下搜索2 2、更新界值、更新界值3 3、向上回溯、向上回溯4 4、停止回溯再向下搜索、停止回溯再向下搜索707BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法向下搜索：向下搜索：开始时置界值开始时置界值B=0B=0从树的根节点沿最右边从树的根节点沿最右边的一支自上而下搜索。的

298、一支自上而下搜索。对于一个节点，它的子树最右边的一支总是无分支对于一个节点，它的子树最右边的一支总是无分支的，即是的，即是1 1度节点或度节点或0 0节点（叶节点）。节点（叶节点）。此时可直接到达叶节点，计算该叶节点的此时可直接到达叶节点，计算该叶节点的J J值，并更值，并更新界值新界值B B。即图中的虚线可省略而得到最小搜索树。即图中的虚线可省略而得到最小搜索树。708BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法最小搜索树最小搜索树709BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法向上回溯和停止回溯：向上回溯和停止回溯：回溯到有分支的那个节回溯到有分支的那个节点则

299、停止回溯转入向下点则停止回溯转入向下搜索。搜索。例如回溯到例如回溯到q qs-1s-11 1 的那个节点，则转入的那个节点，则转入s s深度的左深度的左边的最近的那个节点，使该节点成为当前节点，按边的最近的那个节点，使该节点成为当前节点，按前面的方法沿它最右边的子树继续搜索。前面的方法沿它最右边的子树继续搜索。在搜索过程中先要判一下该节点的在搜索过程中先要判一下该节点的J J值是否比值是否比B B值大。值大。若不大于若不大于B B值，该节点以下的各子节点值，该节点以下的各子节点J J值均不会比值均不会比B B大，故无需对该子树继续进行搜索。大，故无需对该子树继续进行搜索。710BAB算法算法7

300、.7.2 7.7.2 最优搜索法最优搜索法如果搜索到叶节点，且如果搜索到叶节点，且该叶节点代表的特征的该叶节点代表的特征的可分性判据可分性判据J J值大于值大于B B，则更新界值，即则更新界值，即B=JB=J；否则不更新界值。否则不更新界值。显然到达叶节点后，要向上回溯。重复上述过程，显然到达叶节点后，要向上回溯。重复上述过程，一直进行到一直进行到J J值不大于当前界值值不大于当前界值B B为止。而对应的最为止。而对应的最大界值大界值B B的叶节点对应的的叶节点对应的d d个特征组合就是所求的最个特征组合就是所求的最优的选择。优的选择。711该算法的高效性能原因在于如下三个方该算法的高效性能原

301、因在于如下三个方面：面：(1)(1)在构造搜索树时，同一父节点的各子节点为根的在构造搜索树时，同一父节点的各子节点为根的各子树右边的边要比左边的少，即树的结构右边各子树右边的边要比左边的少，即树的结构右边比左边简单；比左边简单；(2)(2)在同一级中按最小的在同一级中按最小的J J值从左到右挑选舍弃的特征，值从左到右挑选舍弃的特征，即节点的即节点的J J值是左小右大，而搜索过程是从右至左值是左小右大，而搜索过程是从右至左进行的；进行的；(3)(3)因因J J的单调性，树上某节点如的单调性，树上某节点如A A的可分性判据值的可分性判据值 ，则，则A A的子树上各节点的的子树上各节点的J J值都不会大于值都不会大于B B，因此该，因此该子树各节点都可以不去搜索。子树各节点都可以不去搜索。JBA 从从(1) (1) 、(2)(2)和和(3)(3)可知，有很多的特征组合不需计可知，有很多的特征组合不需计算仍能求得全局最优解。算仍能求得全局最优解。712