第2章 模式识别的基本理论(1)

第2章模式识别的基本理论与方法1主要内容1、贝叶斯决策理论。主要讲授两种常用的决策规则：贝叶斯准则和最小风险准则；两类及多类决策，分类器的设计、分类器的错误率计算。2、非参数判别分类方法。包括线性判别函数及线性分类器的设计、非线性判别函数、分段线性判别函数、局部训练法等。3、近邻法。包括近邻法及其改进算法(剪辑近邻、压缩近邻法)。4、特征选择与提取方法。概述特征提取与选择的基本概念、常用判据、基于欧氏距离度量的特征提取方法以及次优搜索算法等。5、非监督学习方法。主要讲授C均值算法、分级聚类算法等。2§2.1贝叶斯决策理论模式识别是一种分类问题，即根据识别对象所呈现的观察值，将其分到某个类别中去。统计决策理论是处理模式分类问题的基本理论之一，对模式分析和分类器的设计起指导作用。贝叶斯决策理论是统计模式识别中的一个基本方法。3几个重要概念先验概率–P(ω1)及P(ω2)条件概率密度函数–p(x|ωi)后验概率–P(ωi|X)4贝叶斯决策理论贝叶斯决策理论前提–各类别总体的概率分布是已知的;–要决策分类的概率分布是已知的。贝叶斯决策理论方法所讨论的问题是：–已知:总共有c类物体，以及先验概率P(ωi)及类条件概率密度函数p(x|ωi)–问题:如何对某一样本按其特征向量分类的问题。5几种常用的决策规则不同的决策规则反映了分类器设计者的不同考虑，对决策结果有不同的影响。最有代表性的是：1.基于最小错误率的贝叶斯决策2.基于最小风险的贝叶斯决策3.在限定一类错误率条件下使另一类错误率为最小的两类别决策(Neyman-pearson准则)4.最小最大决策62.2.1基于最小错误率的贝叶斯决策分类识别中为什么会有错分类？–当某一特征向量值X只为某一类物体所特有，即对其作出决策是容易的，也不会出什么差错–问题在于出现模棱两可的情况，任何决策都存在判错的可能性。–分类准则：使错误率为最小(基于最小错误率的贝叶斯决策)7基于最大后验概率的贝叶斯决策例：癌细胞的识别–假设每个要识别的细胞已作过预处理，并抽取出了d个特征描述量，用一个d维的特征向量X表示，–识别的目的是要依据该X向量将细胞划分为正常细胞或者异常细胞。–这里我们用ω1表示是正常细胞，而ω2则属于异常细8先验概率–P(ω1)和P(ω2)：每种细胞占全部细胞的比例P(ω1)+P(ω2)=1–根据先验概率决定–这种分类决策没有意义，表明由先验概率所提供的信息太少121122()(),()(),PPxPPx9概率密度函数–利用对细胞作病理分析所观测到的信息，也就是所抽取到的d维观测向量，得到两类的类条件概率密度函数分布p(x|ω1)是正常细胞的属性分布p(x|ω2)是异常细胞的属性分布–我们的问题:当观测向量为X值时,应该把该细胞分为哪个类别呢？10基于最大后验概率的贝叶斯决策–后验概率：该细胞属于正常细胞的概率P(ω1|x)该细胞属于异常细胞的概率P(ω2|x)这是考虑了X属于哪类的概率，可以作为分类的准则。----最大后验概率准则。具体规则如下：若：则：对于多类：若：则：ijjPXPX,(|)max(|)12iX11ijjcPXPX,...,(|)max(|)1最大后验概率决策的其他形式iiiiPXpXPPXpX(,)(|)()(|)()iiiiiciiipXPpXPPXpXpXP(|)()(|)()(|)()(|)()1先验概率，后验概率，概率密度函数之间关系(1)用先验概率及类条件概率密度函数表示iipXPpXP,(|)()max(|)()jjj12若：iX则：12(2)用比值的方式表示-----似然比pXPlxpXP(|)()()(|)()1221如果则：X1(3)对数似然比（似然比处理器）hxlxPpXpXP()ln[()]()ln(|)ln(|)ln()1122则：X113例2.1假设在某地区切片细胞中正常(ω1)和异常(ω2)两类的先验概率分别为P(ω1)=0.9，P(ω2)=0.1。现有一待识别细胞呈现出状态x，由其类条件概率密度分布曲线查得p(x|ω1)=0.2，p(x|ω2)=0.4。试对细胞x进行分类。解：利用贝叶斯公式，分别计算出状态为x时ω1与ω2的后验概率14iiipXPPXpXP(|)()..(|).....(|)()111210209081802090401PXPX(|)-(|)..211108180182PXPX(|).(|).1208180182因此判定该细胞为正常细胞ω1比较合理15最大后验概率决策即是最小错误率决策的证明平均错误率，以P(e)表示P(e,x)：错误决策为e,观测值为x的联合概率密度p(e|x)：观测值为x时的条件错误概率密度函数P(x)：x值出现的概率16PePexdxpexPxdx()(,)(|)()以两类别为例证明当p(ω2|x)＞p(ω1|x)时决策为ω2，对观测值x有P(ω1|x)概率的错误率则：RRRRPePxpxdxPxpxdxpxPdxpxPdx()(|)()(|)()(|)()(|)()2112221112如果我们把作出ω1决策的所有观测值区域称为R1，则在R1区内的每个x值，条件错误概率为p(ω2|x)。另一个区R2中的x,条件错误概率为p(ω1|x)。17X1RRRRRRPePxpxdxPxpxdxpxPdxpxPdxPpxdxPpxdxPPePPe()(|)()(|)()(|)()(|)()()(|)()(|)()()()()21122211122211221112在R1区内任一个x值都有P(ω2|x)＜P(ω1|x)，或P(ω2)p(x|ω2)P(ω1)p(x|ω1)在R2区内任一个x值都有P(ω2|x)P(ω1|x)，或P(ω2)p(x|ω2)P(ω1)p(x|ω1)错误率在每个x值处都取小者，因而平均错误率P(e)也必然达到最小因而，按最大后验概率作出的决策，其平均错误率为最小pXPlxpXP(|)()(),(|)()1221如果182.1.2基于最小风险的贝叶斯决策基本思想–使错误率最小并不一定是一个普遍适用的最佳选择。–癌细胞分类两种错误:癌细胞→正常细胞；正常细胞→癌细胞两种错误的代价(损失)不同–宁可扩大一些总的错误率，但也要使总的损失减少。–引进一个与损失有关联的，更为广泛的概念——风险。–在作出决策时，要考虑所承担的风险。–基于最小风险的贝叶斯决策规则正是为了体现这一点而产生的。19基于最小风险的贝叶斯决策最小错误率贝叶斯决策规则改为对该观测值X条件下各状态后验概率求加权和的方式:加权平均-----风险(X决策为i类的风险)λj(i)X:表示X确实是ωj，却被判定为ωi的损失(风险)分类准则是使风险最小：ijjcRXRX,...,:()min()1如果iX则：ciijjjRXPX()()(|)120ijjcPXPX,...,(|)max(,)1两类情况：以病理切片为例X确实是癌细胞(ω2)，但被判正常(ω1)的代价(损失)X确实是正常(ω1)，但被判癌细胞(ω2)的代价(损失)RXPXPX()()()(|)(|)1111122RXPXPX()()()(|)(|)2221122作出哪一种决策就要看是R1(X)小还是R2(X)小这就是基于最小风险的贝叶斯决策的基本出发点21多类情况(1)自然状态与状态空间。自然状态：指待识别对象的自然类别:ωi状态空间Ω：由所有自然状态所组成的空间Ω={ω1，ω2，…，ωc}(2)决策与决策空间。对分类问题所作的判决，称之为决策，αi。由所有决策组成的空间称为决策空间。Α={α1,α2,…..,αK}决策不仅包括根据观测值将样本划归哪一类别(状态)，还可包括其它决策，如“拒绝”等，因此决策空间内决策总数K可以不等于类别数c22(3)损失函数λ(αi|ωj)(或写成λ(αi,ωj))。它明确表示对自然状态ωj作出决策αi时所造成的损失。是前面我们引用过的λj(i)(4)观测值X条件下的期望损失R(αi|X),称为条件风险（5）期望风险R：（6）最小风险贝叶斯决策规则：若：则：23ciijjjRXPXiK(|)(,)(|),,...,112jiiKRXRX,,...,(|)min(|)12jXiRRXpXdX(|)()最小风险贝叶斯决策的步骤（1）根据贝叶斯公式计算后验概率（2）利用后验概率及损失函数计算条件风险（3）按条件风险最小进行决策。若：则：jX24ciijjjRXPXiK(|)(,)(|),,...,112jiiKRXRX,,...,(|)min(|)12例2.2在例2.1条件的基础上–假设在某地区切片细胞中正常(ω1)和异常(ω2)两类的先验概率分别为P(ω1)=0.9，P(ω2)=0.1。现有一待识别细胞呈现出状态x，由其类条件概率密度分布曲线查得p(x|ω1)=0.2，p(x|ω2)=0.4–λ11=0，λ12=6,λ21=1，λ22=0(λij表示λ(αi|ωj))–按最小风险贝叶斯决策进行分类。25–解：已知条件为P(ω1)＝0.9,P(ω2)＝0.1p(X|ω1)＝0.2,p(X|ω2)＝0.4λ11＝0,λ12＝6,λ21＝1,λ22＝0(1)根据例2.1的计算结果可知后验概率为P(ω1|X)＝0.818P(ω2|X)＝0.18226(2)再计算出条件风险(3)作出决策由于R(α1|X)＞R(α2|X)即决策为α2的条件风险小于决策为α1的条件风险，因此应采取决策行动α2，即判待识别的细胞X为ω2类——异常细胞。27jjjjjjRXPXPXRXPXPX(|)(|)(|).(|)(|)(|).2111221222211110920818两种决策方法之间的关系基于最小错误率的决策是基于最小风险决策的特例设损失函数为正确决策,没有损失;错误决策:损失为1.----0-1损失此时，条件风险为R(αi|X)最小即是P(ωi|X)最大可见：最小错误率贝叶斯决策就是0-1损失函数下的最小风险贝叶斯决策cciijjjijjjiRaXaPXPXPX,(|)(|)(|)(|)(|)11128ijijaijcij(|),,,,...,0121最小错误率决策与最小风险决策的似然比及错误率pXPlxpXP(|)()(),(|)()1221如果X1PpXlxpXP()(|)(),(|)()122221112121（-）如果（-）（1）似然比门限不同；（2）错误率不同292.1.3判别函数、决策面与分类器设计决策域：各类别在特征空间内所占的区域。分类决策：待识别的特征向量落在哪个决策域，该样本就被判为哪一类。决策面及决策面方程：决策域的边界面就是决策面，在数学上用解析形式表示成决策面方程。判别函数：用于表达决策规则的某些函数则称为判别函数。一、判别函数及决策面30例：两类别问题按最小错误率决策的判别函数及决策面决策规则：若P(ω1|X)P(ω2|X)，则X∈ω1可设判别函数：gi(X)＝P(ωi|X),i=1,2则决策面方程为：g1(X)＝g2(X)基于判别函数的决策规则如果gi(X)＞gj(X);i,j=1,2且i≠j则X∈ωi31多类别情况若各类判别函数为：则决策规则为：如果则X∈ωi决策面及决策面方程当ωi的决策域与ωj的决策域相邻时，相应的决策面为：gi(X)＝gj