模式识别.PPT

模 式 识 别2022-10-52课程对象计算机学院（软件学院）本科生的专业选修课研究生的专业课2022-10-53与模式识别相关的学科统计学概率论线性代数（矩阵计算）信号处理机器学习人工智能图像处理计算机视觉2022-10-54教学方法着重讲述模式识别的基本概念，基本方法和算法原理。注重理论与实践紧密结合实例教学：主要通过实例讲述如何将所学知识运用到实际应用之中避免陷入过多的、繁琐的数学推导。2022-10-55教学目标了解模式识别的基本概念和方法能够运用所学知识和方法解决部分实际问题为深入研究模式识别的理论和方法打下基础 2022-10-56教材/参考文献钟珞，模式识别，武汉大学出版社边肇祺，模式识别（第二版），清华大学出版社蔡元龙，模式识别，西北电讯工程学院出版社第一章 绪 论2022-10-581.1 模式识别和模式的概念什么是模式识别：模式识别是研究用计算机来实现人类模式识别能力的一门学科。模式识别 直观，无所不在，“物以类聚”周围物体的认知：桌子、椅子人的识别：张三、李四声音的辨别：汽车、火车，狗叫、人语人和动物的模式识别能力是极其平常的，但对计算机来说却是非常困难的。2022-10-59什么是模式广义地说，模式是一些供模仿用的、完美无缺的标本。本课程把所见到的具体事物称为模式，而将它们归属的类别称为模式类。模式的直观特性:可观察性可区分性相似性2022-10-510模式识别简史1929年 G.Tauschek发明阅读机，能够阅读0-9的数字。30年代 Fisher提出统计分类理论，奠定了统计模式识别的基础。50年代 Noam Chemsky 提出形式语言理论傅京荪 提出句法结构模式识别。60年代 L.A.Zadeh提出了模糊集理论，模糊模式识别方法得以发展和应用。80年代以Hopfield网、BP网为代表的神经网络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。90年代小样本学习理论，支持向量机也受到了很大的重视。2022-10-5111.2 模式识别的研究方法模式识别系统识别方法2022-10-5121.2.1 模式识别系统信息获取预处理特征提取和选取分类器设计分类决策2022-10-5131 信息获取二维图象 如文字、指纹、地图、照片一维波形 如脑电图、心电图、机械震动波形物理参数和逻辑值2022-10-5142 预处理目的：去除噪声，加强有用信息，复原信息预处理：包括AD,二值化，图象的平滑，变换，增强，恢复，滤波等,主要指图象处理。2022-10-5153 特征提取和选取特征提取和选择：对原始数据进行变换，得到最能反映分类本质的特征测量空间：原始数据组成的空间特征空间：分类识别赖以进行的空间模式表示：维数较高的测量空间-维数较低的特征空间例如，一幅64x64的图象可以得到4096个数据，这种在测量空间的原始数据通过变换获得在特征空间最能反映分类本质的特征。2022-10-5164 分类器设计是一种分类判别规则。用一定数量的样本确定出一套分类判别规则，使得按这套分类判别规则对待识别模式进行分类造成的错误识别率最小或引起的损失最小。2022-10-5175 分类决策分类器按已确定的分类判别规则对待识别模式进行分类判别，输出分类结果，这就是分类器的使用过程，又称为分类决策。2022-10-5181.2.2 识别方法描述模式有两种方法：定量描述和结构性描述。定量描述就是用一组数据来描述模式；结构性描述就是用一组基元来描述模式。两种基本的模式识别方法：统计模式识别方法和结构模式识别方法。2022-10-519统计模式识别被研究的模式用特征向量来描述，特征向量中的每一个元素代表模式的一个特征或属性，特征向量构成的空间叫做特征空间。研究统计模式识别方法的任务就是用不同的方法划分特征空间，从而达到识别的目的。2022-10-520结构模式识别该方法通过考虑识别对象的各部分之间的联系来达到识别分类的目的。模式是由一些模式基元按一定的结构规则组合而成，结构分析的内容就是分析模式如何由基元构成的规则。比较成功的是句法结构模式识别。通过检查代表这个模式的句子是否符合事先给定的某一类文法规则，如果符合，那么这个模式就属于这个文法所代表的那个模式类。2022-10-521模糊模式识别利用模糊数学的理论和方法分析和解决模式识别问题。具有数学基础，又更接近人的思维。代表方法：模糊K均值、模糊ISODATA算法。2022-10-522神经网络神经网络是受人脑组织的生理学启发而创立的。由一系列互相联系的、相同的单元（神经元）组成。相互间的联系可以在不同的神经元之间传递增强或抑制信号。增强或抑制是通过调整神经元相互间联系的权重系数来（weight）实现。神经网络可以实现监督和非监督学习条件下的分类。2022-10-5231.3 模式识别的应用（举例）生物学自动细胞学、染色体特性研究、遗传研究天文学天文望远镜图像分析、自动光谱学经济学股票交易预测、企业行为分析医学心电图分析、脑电图分析、医学图像分析2022-10-524工程产品缺陷检测、特征识别、语音识别、自动导航系统、污染分析、字符识别军事航空摄像分析、雷达和声纳信号检测和分类、自动目标识别安全指纹识别、人脸识别、监视和报警系统模式识别的应用（举例）2022-10-525模式分类器的获取和评测过程数据采集特征选取模型选择训练和测试计算结果和复杂度分析，反馈2022-10-526训练和测试训练集：是一个已知样本集，在监督学习方法中，用它来开发出模式分类器。测试集：在设计识别和分类系统时没有用过的独立样本集。系统评价原则：为了更好地对模式识别系统性能进行评价，必须使用一组独立于训练集的测试集对系统进行测试。2022-10-527实例：统计模式识别19名男女同学进行体检，测量了身高和体重，但事后发现其中有4人忘记填写性别，试问（在最小错误的条件下）这4人是男是女？体检数值如下：2022-10-528实例：统计模式识别（续）待识别的模式：性别（男或女）测量的特征：身高和体重训练样本：15名已知性别的样本特征目标：希望借助于训练样本的特征建立判别函数（即数学模型）2022-10-529实例：统计模式识别（续）从图中训练样本的分布情况，找出男、女两类特征各自的聚类特点，从而求取一个判别函数（直线或曲线）。只要给出待分类的模式特征的数值，看它在特征平面上落在判别函数的哪一侧，就可以判别是男还是女了。2022-10-5302022-10-5312022-10-5322022-10-533本门课程的主要内容1、模式识别概述2、Bayes决策理论3、线性判别函数与非线性判别函数4、近邻法则5、特征提取和选择6、非监督学习方法（数据聚类）7、统计学习理论8、模式识别应用实例第二章 贝叶斯决策理论2022-10-5352.1 贝叶斯决策的基本概念随机模式与统计特性贝叶斯决策理论就是用概率统计的方法研究随机模式的决策问题各类别总体的概率分布是已知的要决策分类的类别是一定的如何使分类错误率尽可能小是研究各种分类方法的中心问题有关概念：先验概率、类条件概率密度、后验概率、贝叶斯公式2022-10-536作为统计判别问题的模式分类模式识别的目的就是要确定某一个给定的模式样本属于哪一类。可以通过对被识别对象的多次观察和测量，构成特征向量，并将其作为某一个判决规则的输入，按此规则来对样本进行分类。2022-10-537作为统计判别问题的模式分类在获取模式的观测值时，有些事务具有确定的因果关系，即在一定的条件下，它必然会发生或必然不发生。例如识别一块模板是不是直角三角形，只要凭“三条直线边闭合连线和一个直角”这个特征，测量它是否有三条直线边的闭合连线并有一个直角，就完全可以确定它是不是直角三角形。这种现象是确定性的现象。2022-10-538作为统计判别问题的模式分类但在现实世界中，由于许多客观现象的发生，就每一次观察和测量来说，即使在基本条件保持不变的情况下也具有不确定性。只有在大量重复的观察下，其结果才能呈现出某种规律性，即对它们观察到的特征具有统计特性。特征值不再是一个确定的向量，而是一个随机向量。此时，只能利用模式集的统计特性来分类，以使分类器发生错误的概率最小。2022-10-539先验概率预先已知的或者可以估计的模式识别系统位于某种类型的概率。1)()()(21 cPPP表示类型),2,1(cii 2022-10-540类条件概率密度函数系统位于某种类型条件下模式样本X出现的概率密度分布函数。同一类事物的各个属性的变化范围，用一种函数来表示其分布密度。之间201)|()|(21XPXP2022-10-541后验概率系统在某个具体的模式样本X条件下位于某种类型的概率。后验概率可以根据贝叶斯公式计算，直接用做分类判决的依据。1)|()|()|(21 XPXPXPc2022-10-542贝叶斯公式两个事物X与w联合出现的概率称为联合概率。利用该公式可以计算后验概率。)()|()()|(),(XPXPPXPXP2022-10-5432.2 几种常用的决策规则研究在统计意义下的分类判决。用分类决策规则对模式进行分类。都存在判错的可能；不同的决策规则可能有不同的判决结果。最小错误率决策与最小风险决策。限定错误率的两类判别决策。最小最大决策。2022-10-5442.2.1 最小错误率的贝叶斯决策在模式分类问题中，往往希望尽量减少分类错误的概率，因此需要建立一种能使错误率为最小的决策规则。从这样的要求出发，利用概率论中的贝叶斯公式得出使错误率为最小得分类规则，称之为基于最小错误率得贝叶斯决策。基于最小错误概率的贝叶斯决策理论就是按后验概率的大小作判决的。2022-10-545例子1癌细胞识别：只有两类情况，是与否。用d维向量X表示细胞测量数据，1代表正常细胞，2代表异常细胞。目的是要根据X把测量细胞判别为正常细胞或者异常细胞。2022-10-546例子1根据大量统计资料，可以对正常细胞与异常出现的比例作出估计。这就是通常所说的先验概率：P(1)与P(2)1)()(21PP)()(21PP2022-10-547例子1下图是正常细胞的属性分布与异常细胞的属性分布。即类条件概率密度函数。得到样本的观测值x之后，可以根据先验概率和类概率密度得到后验概率。通过后验概率则可以作出分类判断。X)|(1xp)|(2xp2.04.0 x2022-10-548例子1利用贝叶斯公式计算两类的后验概率)|(xPi)()()|()|(xPPxPxPiii21)()|()(jjjPxPxP2022-10-549例子1基于最小错误概率的贝叶斯决策理论就是按后验概率的大小作判据，其规则为21)|2()|1(xxxPxP，否则，则如果2022-10-550例子2假设某个地区正常细胞1与异常细胞2的先验概率分别为9.0)(1P1.0)(2P对于某个待识别细胞，其观察值为x，根据类条件概率密度分布曲线上可知2.0)|(1xP4.0)|(2xP请对该细胞进行分类2022-10-551例子2利用贝叶斯公式，分别计算1与2的后验概率如下818.01.04.09.02.09.02.021)()|()1()1|()|1(iiPixPPxPxP182.0)|(1)|(12xPxP2022-10-552例子2根据最小错误率的贝叶斯决策规则，合理的决策是把x归类于正常状态。尽管类别2出现状态x的条件概率高于1出现此状态的概率，但是根据最小错误原则，该细胞被判断为正常。182.0)|(818.0)|(21xPxP2022-10-553证明（最小错误率）假设模式特征x是一个连续的随机变量，显然观察到的x不同，后验概率不同，分类错误率也不同。分类错误概率P(e|x)是随机变量x的函数。观察到大量模式，对它们作出决策的平均错误率P(e)是P(e|x)的数学期望。则可以计算这个随机变量x的函数P(e|x)的数学期望：dxxPxePeP)()|()(P(x)为x出现的概率，P(e|x)是观测值为x时的条件错误概率，积分表示整个d维空间上的总和。在一维情况下，x取整个范围。2022-10-554证明（最小错误率）对两类问题，从决策规则可知，如果那么决策为第2类，这时x的条件错误概率为所以有如下的公式：)|()|(12xPxP)|(2xP)|()|(),|()|()|(),|()|(212121xPxPxPxPxPxPxeP2022-10-555证明（最小错误率）在例子2的决策中，实际包含了0.182的错误概率。所以如果把作出1决策的区域记为R1，作出2决策的区域记为R2，则在R1内的每个x，条件错误概率为P(2|x)，所以有下面的公式。1212)()|()()|()()|()()|()|(221121RRRRdxPxPdxPxPdxxPxPdxxPxPxeP2022-10-556证明（最小错误率）下图表示一维模式时的情况。H为R1与R2的分界。H的位置不同，错误率也不同。阴影部分为总的错误率。改变H的位置，可以改变错误率。选取决策面使得：则可消除小面积A，得到最小分类错误概率。这正是贝叶斯决策规则。)()|()()|(2211PxPPxP2022-10-5572.2.2 最小风险的贝叶斯决策在一些实际问题中，错误率最小并不是一个最佳选择。有时候宁可扩大一些总的错误，也要使总的损失减少。对前面的例子可以看到，我们不仅要考虑到尽可能作出正确的判断，而且还要考虑万一作出了错误的判断后带来的后果，要比较哪一种的风险更小，或者损失更大。2022-10-5582.2.2 最小风险的贝叶斯决策这里引入一个与损失有关联的，更为广泛的概念：风险。在进行分类决策的时候，要考虑决策所承担的风险。最小风险的贝叶斯决策就是把各种分类错误引起的损失考虑进去的贝叶斯决策法则。期望风险与条件风险。2022-10-5592.2.2 最小风险的贝叶斯决策决策论中称采取的决定为决策或行动。所有可能采取的各种决策组成的集合称决策空间或行动空间。每个决策都会带来一定的损失，通常是决策和自然状态的函数，用决策表来表示这种关系。决策表的形成是困难的，需要大量的领域知识。2022-10-5602.2.2 最小风险的贝叶斯决策其基本思想是：在观测值X条件下，对各状态的后验概率求加权和，并根据加权和的大小来进行分类决策。而这个加权和就是所谓的风险。)|()(1XPxRjcjjii时所造成的损失而被判为状态，实属类别表示ijXji2022-10-5612.2.2 最小风险的贝叶斯决策如果希望尽可能避免将状态(j)错判为(i)，则可以将相应的(j,i)的值选择得大一些。那么可以知道最小风险的判别方法就是根据下面的公式来实现的。找出条件风险最下的。kicikxRxR则),|(min)|(,.,12022-10-562例子3在例子2的基础上进一步讨论。如X是2但被判断为1，会有损失用21来表示；如X是1但被判断为2，会有损失用12来表示；将X判断为1与2的风险分别为：)|()|()(2211111XPXPXR)|()|()(2221122XPXPXR2022-10-563例子3如果已知11=0，21=6，12=1，22=0，按最小风险贝叶斯该如何分类。092.1)|(6)|(0)(211XPXPXR818.0)|(0)|(1)(212XPXPXR221)()(XXRXR2022-10-5642.2.2最小风险的贝叶斯决策关于最小风险贝叶斯决策规则的一些相关术语。自然状态与状态空间：样本与类别决策与决策空间：决策总数可能大于类别数损失函数与决策表：决策表是一种先验知识期望损失：期望损失的最小值，就是最小风险的贝叶斯决策2022-10-5652.2.2最小风险的贝叶斯决策最小错误率与最小风险之间的关系定义决策表的损失函数为0-1损失函数根据前面的公式可以知道，最小错误率贝叶斯决策就是在0-1损失函数条件下的最小风险贝叶斯决策。即前者是后者的一个特例。2022-10-5662.2.3 限定错误率的两类判别决策在两类判别决策问题中，有两种错误分类的可能。这两种错误的概率为P(2)P2(e)和P(1)P1(e)最小错误率贝叶斯决策是使这两种错误率之和最小。实际中，有时要求限制某一类错误率不大于某个常数而使另一类错误率尽可能地小，即令：的极小值求)()(102ePeP2022-10-5672.2.3 限定错误率的两类判别决策这样的决策，就是一个典型的条件极值问题，可以用Lagrange乘子法解决。按此方法建立数学模型：)()(021ePeP1)|()(22RdxxPeP12)|(1)|()(111RRdxxPdxxPeP2022-10-5682.2.3 限定错误率的两类判别决策112)|()|()1()|()|(120021RRRdxxPxPdxxPdxxP有：令0,0 x)|()|(21xPxP102)|(RdxxP2022-10-5692.2.3 限定错误率的两类判别决策满足上面公式的边界面以及最佳，就可以让极小。此时，决策规则可以写为：2121,)|()|(xorxxPxP2022-10-5702.2.4 最小最大决策在实际中，各类先验概率P(i)往往不能精确知道，或者在分析过程中是变化的。那么此时的判决不是最佳的，实际平均损失会变大。如何解决这种平均损失变大的问题，按决策论的思想，应该立足在最差情况下争取最好的结果。根据这种原则，可以知道最小最大决策是一种稳健的设计方法，也是一种保守的设计方法。2022-10-5712.2.4 最小最大决策对于两类问题，假设一种分类识别决策将特征空间分为两个区域，平均损失为：)()|()()|()()()|()(12221211121221112221222121bPadxxPdxxPPdxxPRRRR2022-10-5722.2.4 最小最大决策2022-10-5732.2.4 最小最大决策根据图和公式进行分析，在（0，1）区间内，对先验概率P(1)取若干个不同的值，按最小风险决策确定相应的决策域，从而计算相应的最小风险R，可以得出最小贝叶斯风险与先验概率的关系曲线，如图的曲线部分。图a曲线上A点的纵坐标是对应于先验概率为P*(1)时的最小风险。过A的切线CD，表示在判决面不作调整的情况下，当P(1)变化时，R的变化，是一个线性函数，在（a，a+b）之间变化。2022-10-5742.2.4 最小最大决策由于没有针对P(1)的变化重新求最佳判决面，所以平均损失要比最佳的判决面大，直线CD在曲线上方说明了此点。可以总结，在作最小决策时，考虑先验概率可能改变，则应选择使最小贝叶斯风险为最大值时的P*(1)来设计分类器，即对应图b中的B点。此时直线平行P(1)，能保证在不调整判决面的情况下，不管P(1)如何变化，最大风险都为最小。2022-10-5752.2.4 最小最大决策具体的设计过程是：按最小损失准则找出对应于（0，1）中的各个不同值的P(1)的最佳决策面，计算相应的最小平均损失，得到曲线函数。找出使R最大的P*(1)，最后运用最小损失的决策规则构造似然比函数：211*11211*221221,)()()(1)()|()|(xorxPPxPxP2022-10-5762.2.5 序贯分类方法前面的方法都没有考虑获取特征所花费的代价。有的问题需要考虑其余特征的获取代价是否大于分类错误的代价。解决这个问题的方法是序贯分类方法。先用一部分特征来分类，逐步加入分类特征减少分类损失；并且比较加入特征的花费代价与所降低分类损失的大小。2022-10-5772.2.6 分类器设计根据所学习的贝叶斯决策规则，可以进行分类器的设计。分类器设计就是在描述待识别对象的d维特征所组成的特征空间内，将其划分为c个决策域。决策域的边界称为决策面；用于表达决策规则的函数称为判别函数；判别函数决定了决策面。分类器，就是一个计算c个类别的判别函数并选取与最大判别值对应的类别为决策结果的一种机器。2022-10-5782.2.3 分类器设计两类情况判别函数：g(x)=g1(x)g2(x)决策规则表示为g(x)0，则决策1；反之决策2决策面方程：g(x)=02022-10-5792.2.3 分类器设计多类情况判别函数：gi(x)决策决策规则表示为如果gi(x)gj(x)，则x决策为i；反之决策j。决策面方程：gi(x)=gj(x)2022-10-5802.3 正态分布的统计决策正态分布在数学上比较简单，有物理上的合理性正态分布概率模型有很多好的性质，有利于作数学分析。对于许多实际的数据集，正态假设通常是一种合理的近似。观测值较多地分布在均值附近，远离均值的样本比较少。2022-10-5812.3.1 正态分布概率密度函数的定义与性质单变量正态分布与多元正态分布单变量正态分布概率密度函数由两个参数完全确定，分别为均值与方差。正态分布的样本主要集中在均值附近，其分散程度用标准差来表征。标准差越大，分散程度也越大。约有95%的样本都落在2倍标准差范围之内。2022-10-5822.4 关于分类器的错误率问题在分类过程中任何一种决策规则都有对应的错误率。错误率反映了分类问题固有的复杂程度。对错误率的计算主要有3种方法。按理论公式计算(补充贝叶斯等协方差错误率计算)计算错误率上界（参照分别计算两类错误率上界）实验估计第三章 概率密度函数的估计2022-10-5843.1 引言在实际中先验概率和类条件概率密度函数常常是未知的。设计分类器的过程一般分为两步，称为基于样本的两步贝叶斯决策。利用样本集估计类条件概率密度与先验概率将估计量代入贝叶斯决策规则，完成分类器设计2022-10-5853.1 引言主要有3个问题需要讨论如何利用样本集估计估计量的性质如何利用样本集估计错误率的方法)()|(iipxp和2022-10-5863.1 引言从样本集推断总体概率分布的方法可以归纳为2种参数估计 监督参数估计：样本所属类别及类条件总体概率密度函数的形式已知，某些参数未知 非监督参数估计：已知总体概率密度函数形式但未知样本类别，要推断某些参数非参数估计：已知样本类别，未知总体概率密度函数形式，要求直接推断概率密度函数本身。2022-10-5873.2 参数估计的基本概念统计量：针对不同要求构造出样本的某种函数，这种函数在统计学种称为统计量。构造描述未知参数的数学模型是关键性步骤。参数空间：在统计学中，把未知参数的可取值集合称为参数空间，记为 2022-10-5883.2 参数估计的基本概念点估计、估计量和估计值：针对某未知参数构造一个统计量作为的估计*，这种估计称为点估计；*称为的估计量；代入自变量的值得到*的值称为的估计值。区间估计：用一个区间作为的取值范围的一种估计。这个区间称为置信区间，这类问题称为区间估计。2022-10-5893.2 参数估计的基本概念我们要求估计总体分布的具体参数，这是点估计问题。两种主要的点估计方法：最大似然估计、贝叶斯估计。评价估计的好坏，不能按一次抽样结果得到估计值与参数真实值的偏差大小来确定，必须从平均和方差的角度来分析。2022-10-5903.2.1 最大似然估计似然函数的定义：N个随机变量x1，x2，xN的似然函数是N个随机变量的联合密度 这个密度可以看成是的函数。具体的说，若 是独立地抽取自密度 ，那么似然函数就是)|,.,()|()(21NxxxpplNxxx,.,21)|(xp)|().|()|()|,.,()(2121NNxpxpxpxxxpl2022-10-5913.2.1 最大似然估计为了解释最大似然估计，我们有如下假定，就可以分别处理c个独立的问题。待估参数是确定的未知量。按类别把样本分成M类X1，X2，X3，XM，其中第i类的样本共N个，Xi =(X1,X2,XN)T，并且是独立从总体中抽取的。类条件概率密度具有某种确定的函数形式。Xi中的样本不包含j(ij)的信息。2022-10-5923.2.1 最大似然估计最大似然估计量：令 为样本集的似然函数，如果 是参数空间中能使似然函数 极大化的值，那么 就是的最大似然估计量。一般来说似然函数满足连续、可微的条件，对似然函数求导即可解出。为了便于分析，使用似然函数的对数往往比使用似然函数本身更容易些。)(l,.,21Nxxx),.,()(21Nxxxdd)(l2022-10-5933.2.2 贝叶斯估计贝叶斯估计和最大似然估计的结果近似相等，但从概念上来说他们的处理方法完全不同。最大似然估计把参数看作是确定而未知的，最好的估计值是在获得实际观察样本的概率为最大的条件下得到的。而贝叶斯估计则把未知的参数当作具有某种分布的随机变量，样本的观察结果使先验分布转化为后验分布，再根据后验分布修正原先对参数的估计。2022-10-5943.2.2 贝叶斯估计最小风险贝叶斯决策中的期望风险与条件风险。贝叶斯决策与贝叶斯估计两者都是立足于使贝叶斯风险最小，只是要解决的问题不同，前者是要决策x的真实状态，而后者则是要估计X所属总体分布的参数。2022-10-5953.2.2 贝叶斯估计决策问题估计问题样本x决策真实状态状态空间是离散空间先验概率样本集估计量真实参数参数空间是连续空间参数的先验分布2022-10-5963.2.2 贝叶斯估计如果损失函数为平方误差损失函数，则贝叶斯估计量是给定x时的条件期望。求解贝叶斯估计量的步骤如下确定的先验分布P()求出样本的联合分布P(xi|)，它是的函数利用贝叶斯公式,求的后验概率求出估计量2)(),(dPXPPXPXPiii)()|()().|()|(dXPi)|(2022-10-5973.2.3 贝叶斯学习贝叶斯学习是利用的先验分布及样本提供的信息求出的后验分布，然后直接求总体分布。当观察一个样本时，N=1就会有一个的估计值的修正值；当观察N=9时，对进行修正，向真正的靠的更近；当N,N就反映了观察到N个样本后对的最好推测，而N反映了这种推测的不确定性，N，N，N 随观察样本增加而单调减小，且当N，N 0；当N，P(|xi)越来越尖峰突起；这个过程成为贝叶斯学习。2022-10-5983.2.3 贝叶斯学习2022-10-5993.3 正态分布的监督参数估计正态分布是最通常的随机变量的分布方式，主要以单变量正态分布为例来对最大似然估计和贝叶斯估计进行学习。正态分布的参数主要是均值与方差。2022-10-51003.3.1 最大似然估计示例利用最大似然估计方法对单变量正态分布函数来估计其均值和方差2。221exp21)|(xxp12221exp21)(iixLT21221,2022-10-51013.3.1 最大似然估计示例niixnnL122221ln22ln2ln01ln1121niinxLniixnL12122220212ln2022-10-51023.3.1 最大似然估计示例niix11201niix12210niixn111niixn122212022-10-51033.3.2 贝叶斯估计示例其问题可以概括为：设 是取自正态分布 的样本集，其中为未知参数，且假定未知参数是随机参数，它有先验分布 ，要求我们用贝叶斯方法求出的估计量。关键问题在于先验分布的存在与否。,.,21Nxxx),(2N),(200N第四章 线性判别函数2022-10-51054.1 引言我们讨论了贝叶斯决策理论和统计判别方法。从原理上说贝叶斯决策理论采用了在d维特征空间中样本分布的最一般描述方式，即统计分布来描述。但是直接使用贝叶斯决策理论需要首先得到有关样本总体分布的知识，具体说来包括各类先验概率P(1)及类条件概率密度函数，从而可以计算出样本的后验概率P(1|X)，并以此作为产生判别函数的必要数据，设计出相应的判别函数与决策面。2022-10-51064.1 引言其中获取统计分布及其参数这部分是很困难的，实际问题中并不一定具备获取准确统计分布的条件。另一种分类器设计方法，是根据训练样本集提供的信息，直接进行分类器设计。这种方法省去了统计分布状况分析，直接对特征空间进行划分，也是当前的主要方法之一。2022-10-51074.1 引言决策域的分界面是用数学表达式来描述的，如线性函数和各种非线性函数等，所以分界面的方程主要包括函数类型选择与最佳参数确定。一般来说，函数类型由设计者选择，其参数的确定则是依据一定的准则函数，通过一个学习过程来实现优化。2022-10-51084.1 引言线性分类器以及作为设计依据的一些准则函数，准则函数包括：感知准则，最小平方误差准则，最小错分样本数准则，Fisher准则。贝叶斯分类器使错误率或风险达到最小，通常称为最优分类器；采用线性判别函数所产生的错误率或风险可能比贝叶斯分类器大，但是它简单，容易实现。2022-10-51094.2 感知准则函数线性判别函数的基本概念感知器概念及其训练算法感知器准则函数及其梯度法2022-10-51104.2.1 线性判别函数的基本概念 在一个d维的特征空间中，线性判别函数的一般表达式如下12211)(dddwxwxwxwxg为加权向量wwxwxgdT1)(2022-10-51114.2.1 线性判别函数的基本概念如果采用增广模式，可以表达如下xwxgT)(Tdxxxx)1,(21 增广加权向量Tdwdwwww)1,2,1(2022-10-51124.2.1 线性判别函数的基本概念在两类情况下，仅用一个判别函数g(x)来表示，对应的分界面就是g(x)=0。如果绝任意分到某一类，或拒可将则决策则决策xxgwxxgwxxg,0)(2,0)(1,0)(2022-10-51134.2.1 线性判别函数的基本概念当g(x)为线性函数的时候，这个决策面便是超平面。假设X1和X2都在决策面H上，则有1211dTdTwXwwXw0)(21 XXwTv这表明w与H上任一向量正交，即w是H的法向量，并且指向g(x)0的决策域。2022-10-51144.2.1 线性判别函数的基本概念线性分类器的设计就是利用训练样本集建立线性判别函数式，也就是寻找最优的权向量w的过程。其主要步骤如下采集训练样本，构成训练样本集。样本应该具有典型性确定一个准则J=J(w,x)，能反映分类器性能，且存在权值w*使得分类器性能最优设计求解w的最优算法，得到解向量w*2022-10-51154.2.2 感知器概念及其训练方法感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。2022-10-51164.2.2 感知器概念及其训练方法感知器是一个具有单层计算单元的神经元模型，是一个多输入单输出的非线性器件。diTiixwxwfy1)sgn()(v各个权值可以通过样本的训练学习来调整，从而实现线性可分函数。2022-10-51174.2.2 感知器概念及其训练方法针对两类问题，利用增广模式向量与增广加权向量以及判决规则来介绍感知器训练算法。Tdxxxx)1,(21 Tdwwww),(21 jTiTwxxwwxxw,0,02022-10-51184.2.2 感知器概念及其训练方法设训练样本集X=x1,x2,xn，其中xk属于wi或者wj，且xk的类别是已知的。为了确定加权向量w*，执行下面的训练算法给定初始值：置k=0，权向量w(k)为任意值，可选常数0c1输入样本xm x1,x2,xn，计算判决函数值g(xm)=wT(k)xm按如下规则修改权向量 若xm wi，且g(xm)0，则w(k+1)=w(k)+cxm 若xm wj，且g(xm)0，则w(k+1)=w(k)-cxm令k=k+1，返回第二步，直到w对所有样本稳定不变，结束2022-10-5119例子1已知两类训练样本，(0,0),(0,1)属于w1，(1,0),(1,1)属于w2，试用感知器算法求解w*训练样本分量增广化以及符号规范化。将训练样本增加一个分量1，且把来自w2的样本各分量乘以-1，得到训练模式集x1=(0,0,1),x2=(0,1,1),x3=(-1,0,-1),x4=(-1,-1,-1)运用训练算法，给权向量赋初值w(1)=(1,1,1)T，取增量c=1，置迭代步数k=1，下面是迭代过程2022-10-5120例子1K=1,xm=x1,w(k)Txm=10,w(2)=w(1)K=2,xm=x2,w(k)Txm=20,w(3)=w(2)K=3,xm=x3,w(k)Txm=-20,w(4)=w(3)+x3=(0,1,0)TK=4,xm=x4,w(k)Txm=-10,w(5)=w(4)+x4=(-1,0,-1)TK=5,xm=x1,w(k)Txm=-10,w(9)=w(8)2022-10-5121例子1K=9,xm=x1,w(k)Txm=0,w(10)=w(9)+x1=(-2,1,1)TK=10,xm=x2,w(k)Txm=20,w(11)=w(10)K=11,xm=x3,w(k)Txm=10,w(12)=w(11)K=12,xm=x4,w(k)Txm=0,w(13)=w(12)+x4=(-3,0,0)TK=13,xm=x1,w(k)Txm=0,w(14)=w(13)+x1=(-3,0,1)TK=14,xm=x2,w(k)Txm=10,w(15)=w(14)K=15,xm=x3,w(k)Txm=20,w(16)=w(15)K=16,xm=x4,w(k)Txm=20,w(17)=w(16)K=17,xm=x1,w(k)Txm=10,w(18)=w(17)2022-10-5122例子1通过上面的结果可以看出，经过对x1,x2,x3,x4一轮迭代后，使用w(14)已经能够对所有训练样本正确分类，增广权矢量的值不再发生变化，所以算法收敛于w(14)，w(14)就是所求的解向量，即w*=(-3,0,1)T。由此可以得到区分界面为：-3x1+1=02022-10-51234.2.3 感知器准则函数及其梯度法在两类样本线性可分的情况下，通过上面的例子可知，如果将属于wj的样本各分量同时乘以-1，则可以由所有满足wTx0的样本求出解w*，即可确定决策函数。但是，对于求解问题，可能存在多个可行解，因此问题进一步转化成如何按一定条件利用优化算法求得最优解的问题。感知器准则函数与梯度法。2022-10-51244.2.3 感知器准则函数及其梯度法梯度法采用最优化技术求线性判别函数中的增广权向量，首先需要构造准则函数。其次再通过优化算法求得最优解，这里选用梯度法求解。一个可微函数某点的梯度给出函数在该点的变化率最大的方向；负梯度给出下降最快的方向。那么对于有极小值的函数而言，可以沿着负梯度的方向选择适当的步长进行搜索，求解函数的极小值点。2022-10-5125梯度法如果我们定义一个准则函数J(w,x)，它的最小值对应着最优解w*，那么完全可以运用数学分析中这种求极值的方法来进行求解，这便是梯度法的基本思想。由于是迭代算法，所以它有一个迭代公式，并且可以找到数值解。迭代公式如下：4.2.3 感知器准则函数及其梯度法)()()()1(kwwJkwkw2022-10-5126感知器准则函数构造准则函数如下：当|wTx|-wTx=0，该准则函数可以达到最小值，此时有wTx0，所以可以得到最优解，也就是最优权向量w*。4.2.3 感知器准则函数及其梯度法0),|(|),(kxwxwkxwJTT2022-10-5127感知器准则函数令k=1/2，可以对J(w,x)求导得到：4.2.3 感知器准则函数及其梯度法)sgn(21xxTwxwJJ其他)()(0)()()()()()(sgn()(2)()1(kxkwkxkTwkwkxkxTkwkxkwkw2022-10-5128v感知器准则函数 当p=c时，梯度下降法与感知器训练算法的修正公式一致，因此感知器训练算法是梯度下降法的一种特例，一般将p为常数的梯度法称为固定增量法。当p在迭代运算时随k变化，称为可变增量法。4.2.3 感知器准则函数及其梯度法2022-10-51294.3 最小平方误差准则感知准则函数及其梯度下降法只适用于样本线性可分的情况，对于线性不可分情况，迭代过程永远不会终结，即算法不收敛。在实际问题中常常无法事先知道样本集是否线性可分，因此希望找到一种既适用于线性可分又适用于线性不可分的算法。通过这种算法得到的解都统一称为最优解。2022-10-51304.3 最小平方误差准则在两类样本线性可分的情况下，如果将属于wj的样本各分量同时乘以-1，则应该有权向量w，对所有样本满足wTxi 0，设计分类器就是求解一组线性不等式。如果任意给定一个向量b=b1,b2,bnT0，那么上述问题可以转化成求解w，使之满足wTxibi。2022-10-51314.3 最小平方误差准则bwxTnbbbb,21 1222121)11(2)11(1)11(11211111121121dnxnxnxdnxnxnxdnxnxnxdxxxTnxTxTxx2022-10-51324.3 最小平方误差准则设分别属于wi与wj的样本数为n1与n2，n=n1+n2W为d+1维列向量，通常有：nd+1，那么方程是没有精确解存在的。定义误差向量：e=xw-b最小平方误差准则函数如下：niiiTsbxwbxwebxwJ1222)(|),(2022-10-51334.3 最小平方误差准则约束条件：要解w为最优，必须保证wTxibi0为最小极值条件0)*(2bxwTxwsJbxxxwTT1*)(的伪逆称为xTxxTxx1)(#2022-10-51344.3 最小平方误差准则此时的w*并不是最小平方误差准则函数下的解，因为w*还依赖于b。根据平方误差准则函数，使用固定增量的梯度下降法建立b的迭代公式如下（即b的初始值可以任意给定）。)()()()1(kbbsbJckbkb2022-10-51354.3 最小平方误差准则)()()1(kbkbkb|)|(|)()(|)()()(kekeckbkxwkbkxwckb)(#)(*)(#)(#)1(#)1(*kbxkwkbxkbxkbxkw2022-10-51364.3 最小平方误差准则从这个迭代表达式可以看出w*依赖于b与c的选择。令b=(1,1,1)T，在样本数无穷大时，最小均方误差解逼近贝叶斯判决。|)1|1()1()()()(|)|(#)(*)1(*)1(#)1(*)1(0)1(kekeckbkxwkbkxwkekekecxkwkwbxwbb可任意给定2022-10-5137例子2已知两类训练样本，(0,0),(0,1)属于w1，(1,0),(1,1)属于w2，试用最小均方误差算法求解w*111101110100 x训练样本的增广矩阵：2/12/12/12/31111111121)(1#TTxxxxx的伪逆矩阵：2022-10-5138例子2TTwbc)1,0,2()1(,)1,1,1,1()1(,1则令0000)1()1(1bwxe误差向量：)1,0,2()1(0*1 wwe，的各分量为0121 x决策面方程：2022-10-51394.3 最小平方误差准则可以重新设置b(1)的初始值，得到不同的决策面方程。与例子1的解对比，可以知道两种方法的差异。2022-10-51404.4 最小错分样本数准则对于不等式wTxi 0，如果有解，可以得到解向量w*，如果无解，那么对于任何向量w，必然有某些样本被错分，那么我们可以寻找使最多数目的不等式得到满足的权向量，将它作为最优解向量w*。上述准则便是最小错分样本数准则的基本思想。2022-10-51414.4 最小错分样本数准则最小错分样本数准则如下：|)(|)(|)(bxwbxwwJqTb 111 v对于最小错分样本数准则函数，一般用共轭梯度法进行求解。2022-10-51424.5 Fisher线性判别准则在应用统计方法进行识别时，在低维空间可行的方法，往往在高维空间行不通。因此，降维是解决实际问题的关键。在一般情况下，总可以找到某个最好的方向，使样本投影到该方向所对应的直线上最容易分开。如何找到最好的直线方向，如何实现向最好方向投影的变换，就是Fisher法要解决的问题。2022-10-51434.5 Fisher线性判别准则在两类问题中，设分别属于wi与wj的样本数为n1与n2，n=n1+n2令yk=wTxk(k=1,2,n)，由子集X1与X2映射后的两个子集为Y1与Y2。使Y1与Y2最容易区分开的w方向正好是分类超平面的法线方向。（见书）2022-10-51444.5 Fisher线性判别准则定义Fisher准则函数如下所示。使得JF最大的解w*就是最佳解向量。2221221|)(SSmmwJF2,1,1iynmikyykii2,1,)(22imysikyyiki2022-10-51454.5 Fisher线性判别准则由Fisher判别式求解向量w*的步骤如下211XX 与把两类样本分为iXkxikxniM2,1,12iXkxiTiMkxiMkxiS2,1,)(3214SSwS)21(1*5MMwSw第五章 非线性判别函数2022-10-5147引言由于样本在特征空间分布的复杂性，很多情况下采用线性判别函数不能取得满意的效果。采用分段线性判别或二次函数判别等非线性方法效果会好得多。分段线性判别函数是最简单的形式，二次判别函数是除分段线性外最简单的形式。2022-10-51485.1 分段线性判别函数的基本概念分段线性判别函数是一种特殊的非线性判别函数，它确定的决策面是由若干超平面段组成。与一般超曲面相比是简单的，又可以逼近各种形状的超曲面。2022-10-5149基于距离的分段线性判别函数样本为等协差的单峰分布样本为等协差的多峰分布分段线性距离分类器5.1 分段线性判别函数的基本概念2022-10-51505.2 二次判别函数二次判别函数也是一种常用的非线性判别函数，它所确定的分界面较为复杂。二次判别函数一般可以表示成：0)(wxwxWxxgTT第六章 近邻法则和集群2022-10-5152引言在分段线性判别函数中，利用每一类的代表点设计分类器，这是最简单和直观的设计方法。但是这个代表点有时候不一定能很好地代表各个类。作为一种分段线性判别函数的极端情况，将各类中全部样本都作为代表点，这样的决策方法就是近邻法的基本思想。2022-10-5153引言近邻法是非参数法中最重要的方法之一。主要介绍最近邻法，k近邻法，快速近邻法算法，集群的基本知识。2022-10-51546.1 最近邻法以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。这种方法就是近邻法的基本思想。将与测试样本最近邻样本的类别作为决策的方法称为最近邻法。2022-10-51556.1 最近邻法最近邻法的决策规则如下ikikiNkxxxg,2,1|,|min)(jiijxxgxg那么：如果)(min)(2022-10-5156最近邻法存在计算量大，存储量大等明显缺点。训练样本集的数量总是有限的，有时候多一个或者少一个训练样本将会对测试样本分类的结果产生较大的影响，因此近邻法的错误率是比较难以计算的。6.1 最近邻法2022-10-51576.1 最近邻法计算错误率的偶然性会随着训练样本数量的增大而减少，就利用训练样本数量增至极大，来对其性能进行评价。也就是在渐进概念下分析错误率。)12(*PccPPP2022-10-51586.2 k近邻法最近邻法的一个明显的推广是K近邻法。取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。cikxgii,2,1,)(jiiixkxg则若,max)(2022-10-51596.2 k近邻法k近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。下面给出两类问题的k近邻错误率分析。)1(2*PPPP2022-10-5160模糊k近邻法只按照前K个近邻样本的顺序而不考虑其距离差别来判断测试样本的类别也是有局限的，远离测试样本的样本点会产生很大干扰。可以采用模糊分类的思想，引入隶属度函数的概念，对K个近邻的样本点的贡献加权，来进行分类判决。2022-10-51616.3 关于近邻法则的讨论实例：在二维空间中，A类有3个样本点，B类有4个样本点。按近邻法，对任意两个由不同类别的样本构成的样本对，如果它们有可能成为测试样本的近邻，则它们之间的中垂面就是类别的分界面。2022-10-51626.3 关于近邻法则的讨论近邻法是典型的非参数法，其优点是实现简单分类结果比较好近邻法的主要缺点是对计算机的存储量和计算量的要求很大，耗费大量测试时间没有考虑决策的风险。对其错误率的分析都是建立在渐进理论基础上的。2022-10-51636.4 改进的近邻法通过优缺点的分析，可以看出，对于近邻法的改进主要有两种方法对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免对每个样本进行距离计算在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，达到既减少计算量又减少存储量的效果2022-10-51646.4.1 快速搜索近邻法这种方法着眼于只解决减少计算量，但没有达到减少存储量的要求。将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组，因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。2022-10-51656.4.1 快速搜索近邻法快速搜索近邻法包括两个阶段样本集的分级分解搜索 要实现快速搜索近邻，需要快速判断某个样本子集是否是测试样本的可能近邻集，从而可将无关的样本子集尽快排除 在某个样本子集内寻找哪个样本是近邻时，需要快速排除不可能为近邻的样本2022-10-51666.4.1 快速搜索近邻法搜索中的两个判别规则如果存在BrpD(X,Mp)，则Xip不可能是X的近邻。其中B是待识别样本在搜索近邻过程中的当前近邻距离，B在搜索过程中不断改变与缩小。算法开始可将B设为无穷大。如果B+D(Xi,Mp)D(X,Mp)，其中Xip，则Xi不可能是X的近邻。2022-10-51676.4.2 快速近邻算法由于近邻法的优点，不断研究算法来加速搜索待分类的模式的最近邻。其共同特点是如何尽快找出最近邻可能存在的小的空间，减少搜索的范围。分量邻域法：将样本划分成一些不相交的子集，通过动态调整搜索半径进行局部搜索。列表法：分为预处理阶段和搜索阶段。2022-10-51686.4.3 剪辑近邻法假如使用全部样本设计分类器和估计错误率，将由于设计和估计样本之间缺乏独立性而总是产生偏于乐观的估计。将样本集分成两个独立的检验集和预测集，用检验集设计分类器，用预测集估计错误率，在两集合独立的条件下，对错误率的估计将是较为准确的。这就是剪辑近邻法的来源。2022-10-51696.4.3 剪辑近邻法利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。两分剪辑近邻法重复剪辑近邻法2022-10-5170两分剪辑近邻法将原始样本随机分为两个集合：预测集T和参考集R，来自预测集和参考集的样本分别完成考试和参考任务，相互独立。对预测集T中的所有样本，利用参考集采用近邻法对其进行分类决策，如果决策结果与实际类别不同，则从预测集中删除该样本，最后得到经过剪辑的考试样本集TE。利用考试样本集TE，采用最近邻法对测试样本进行分类决策。2022-10-5171重复剪辑近邻法K=1，将原始样本随机划分为s个集合以Ti+1作为参考集，采用近邻法对预测集Ti中所有样本进行分类，删除其不相容样本将所有经过剪辑后留下样本组成新的总样本集TNEWK=2,3,，重复步骤2至3，直到再没有样本被剪辑出去则停止，否则转12022-10-51726.4.4 压缩近邻法剪辑近邻的结果只是去掉了两类边界附近的样本，而靠近两类中心的样本几乎没有被去掉。在剪辑的基础上，再去掉一部分这样的样本，有助于进一步缩短计算时间和降低存储要求。这类方法叫作压缩近邻法。压缩近邻法中定义了两个存储器，一个用来存放即将生成的样本集，Store；