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

1、第第2章章模式识别的基本理论与方法模式识别的基本理论与方法主要内容 1、贝叶斯决策理论。 主要讲授两种常用的决策规则：贝叶斯准则和最小风险准 则；两类及多类决策，分类器的设计、分类器的错误率计算。 2、非参数判别分类方法。 包括线性判别函数及线性分类器的设计、非线性判别函数、分段线性判别函数、局部训练法等。 3、近邻法。 包括近邻法及其改进算法(剪辑近邻、压缩近邻法)。 4、特征选择与提取方法。 概述特征提取与选择的基本概念、常用判据、基于欧氏距离度量的特征提取方法以及次优搜索算法等。 5、非监督学习方法。主要讲授C均值算法、分级聚类算法等2.1贝叶斯决策理论 模式识别是一种分类问题，即根据识

2、别对象所呈现的观察值，将其分到某个类别中去。 统计决策理论是处理模式分类问题的基本理论之一，对模式分析和分类器的设计起指导作用。 贝叶斯决策理论是统计模式识别中的一个基本方法。 几个重要概念几个重要概念 先验概率先验概率 P(1)及及P(2) 条件概率密度函数条件概率密度函数 p(x|i) 后验概率后验概率 P(i|X) iixiip xe()( |)22212贝叶斯决策理论 贝叶斯决策理论前提 各类别总体的概率分布是已知的; 要决策分类的概率分布是已知的。 贝叶斯决策理论方法所讨论的问题是： 已知:总共有c类物体，以及先验概率P(i)及类条件概率密度函数p(x|i) 问题: 如何对某一样本按

3、其特征向量分类的问题。几种常用的决策规则几种常用的决策规则 不同的决策规则反映了分类器设计者的不同考虑，对决策结果有不同的影响。最有代表性的是：1.基于最小错误率的贝叶斯决策基于最小错误率的贝叶斯决策2.基于最小风险的贝叶斯决策基于最小风险的贝叶斯决策 3.在限定一类错误率条件下使另一类错误率为最小的两类别决策(Neyman-pearson准则)4.最小最大决策2.2.1 基于最小错误率的贝叶斯决策 分类识别中为什么会有错分类？分类识别中为什么会有错分类？ 当某一特征向量值X只为某一类物体所特有，即 对其作出决策是容易的，也不会出什么差错 问题在于出现模棱两可的情况，任何决策都存在判错的可能性

4、。 分类准则：使错误率为最小 (基于最小错误率的贝叶斯决策 ) 基于最大后验概率的贝叶斯决策 例例：癌细胞的识别 假设每个要识别的细胞已作过预处理，并抽取出了d个特征描述量，用一个d维的特征向量X表示， 识别的目的是要依据该X向量将细胞划分为正常细胞或者异常细胞。 这里我们用1表示是正常细胞，而2则属于异常细先验概率先验概率 P(1)和P(2) ：每种细胞占全部细胞的比例 P(1)+P(2)=1 根据先验概率决定 这种分类决策没有意义，表明由先验概率所提供的信息太少 121122()(),()(),PPxPPx 概率密度函数概率密度函数 利用对细胞作病理分析所观测到的信息，也就是所抽取到的d维

5、观测向量，得到两类的类条件概率密度函数分布 p(x|1)是正常细胞的属性分布 p(x|2)是异常细胞的属性分布 我们的问题: 当观测向量为X值时,应该把该细胞分为哪个类别呢？基于最大后验概率的贝叶斯决策 后验概率： 该细胞属于正常细胞的概率P(1|x) 该细胞属于异常细胞的概率P(2|x) 这是考虑了X属于哪类的概率，可以作为分类的准则。-最大后验概率准则。 具体规则如下： 若： 则： 对于多类： 若： 则：ijjPXPX,(|)max (|)1 2iXijjcPXPX,.,(|)max(|)1最大后验概率决策的其他形式iiiiP Xp XPPX p X(,)(|) ()(|) ()iiiii

6、ciiip XPp XPPXp Xp XP(|) ()(|) ()(|)()(|) ()1先验概率，后验概率，概率密度函数之间关系 (1) 用先验概率及类条件概率密度函数表示iip XPp XP,(|) ()max (|) ()jjj 12若：iX则： (2)用比值的方式表示-似然比 p XPl xp XP(|)()( )(|)()1221如果则：X1 (3) 对数似然比（似然比处理器） h xl xPp Xp XP ( )ln ( )()ln (|)ln (|)ln()1122则：X1 例2.1假设在某地区切片细胞中正常(1)和异常(2)两类的先验概率分别为P(1)=0.9，P(2)=0.1

7、。现有一待识别细胞呈现出状态x，由其类条件概率密度分布曲线查得p(x|1)=0.2，p(x|2)=0.4。 试对细胞x进行分类。解：利用贝叶斯公式，分别计算出状态为x时1与2的后验概率 iiip XPPXp XP(|) ().(|).(|) ()111210 2 0 90 8180 2 0 90 4 0 1PXPX (|)-(|).2111 0 8180 182PXPX(|).(|).120 8180 182因此判定该细胞为正常细胞1比较合理 最大后验概率决策即是最小错误率决策的证明 平均错误率，以P(e)表示 P(e,x)：错误决策为e,观测值为x的联合概率密度p(e|x)：观测值为x时的条

8、件错误概率密度函数P(x)：x值出现的概率 P eP e x dxp e x P x dx( )( , )( | ) ( )以两类别为例证明 当p(2|x)p(1|x)时决策为2 ，对观测值x有P(1|x)概率的错误率 则：RRRRP ePx p x dxPx p x dxp xPdxp xPdx( )(| ) ( )(| ) ( )( |) ()( |) ()2112221112如果我们把作出1决策的所有观测值区域称为R1，则在R1区内的每个x值，条件错误概率为p(2|x)。另一个区R2中的x,条件错误概率为p(1|x)。X1RRRRRRP ePx p x dxPx p x dxp xPdx

9、p xPdxPp xdxPp xdxPP ePP e( )(| ) ( )(| ) ( )( |) ()( |) ()()( |)()( |)()( )() ( )21122211122211221112在R1区内任一个x值都有P(2|x)P(1|x)，或P(2)p(x|2)P(1|x) ，或P(2)p(x|2)P(1)p(x|1)错误率在每个x值处都取小者，因而平均错误率P(e)也必然达到最小因而，按最大后验概率作出的决策，其平均错误率为最小按最大后验概率作出的决策，其平均错误率为最小p XPl xp XP(|)()( ),(|)()1221如果2.1.2 基于最小风险的贝叶斯决策 基本思想

10、 使错误率最小并不一定是一个普遍适用的最佳选择。 癌细胞分类 两种错误: 癌细胞正常细胞；正常细胞癌细胞 两种错误的代价(损失)不同 宁可扩大一些总的错误率，但也要使总的损失减少。 引进一个与损失有关联的，更为广泛的概念风险。 在作出决策时，要考虑所承担的风险。 基于最小风险的贝叶斯决策规则正是为了体现这一点而产生的。基于最小风险的贝叶斯决策基于最小风险的贝叶斯决策 最小错误率贝叶斯决策规则 改为对该观测值X条件下各状态后验概率求加权和的方式: 加权平均-风险(X决策为i类的风险) j (i) X:表示X确实是j，却被判定为i的损失(风险) 分类准则是使风险最小：ijjcR XRX,.,:()

11、min()1如果iX则：ciijjjR XPX( )()(|)1ijjcPXPX,.,(|)max(,)1两类情况：以病理切片为例 X确实是癌细胞(2)，但被判正常(1)的代价( 损失 ) X确实是正常(1) ，但被判癌细胞(2)的代价(损失) R XPXPX( )( )()(|)(|)1111122RXPXPX( )( )()(|)(|)2221122作出哪一种决策就要看是R1(X)小还是R2(X)小这就是基于最小风险的贝叶斯决策的基本出发点 多类情况 (1)自然状态与状态空间。 自然状态：指待识别对象的自然类别: i 状态空间：由所有自然状态所组成的空间=1，2，c (2)决策与决策空间。

12、 对分类问题所作的判决，称之为决策， i 。 由所有决策组成的空间称为决策空间。 =1, 2,., K 决策不仅包括根据观测值将样本划归哪一类别(状态)，还可包括其它决策，如“拒绝”等，因此决策空间内决策总数K可以不等于类别数c (3)损失函数(i|j) (或写成(i,j)。 它明确表示对自然状态j作出决策i时所造成的损失。是前面我们引用过的j(i) (4)观测值X条件下的期望损失R(i|X),称为条件风险 （5）期望风险R： （6）最小风险贝叶斯决策规则： 若： 则：ciijjjRXPXiK (|)(,) (|), ,.,11 2jiiKRXRX, ,.,(|)min(|)1 2jXiRRX

13、 p X dX(|) ()最小风险贝叶斯决策的步骤 （1）根据贝叶斯公式计算后验概率 （2）利用后验概率及损失函数计算条件风险 （3）按条件风险最小进行决策。 若： 则：jXciijjjRXPXiK (|)(,) (|), ,.,11 2jiiKRXRX, ,.,(|)min(|)1 2 例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) ) 按最

14、小风险贝叶斯决策进行分类。 解：已知条件为P(1)0.9, P(2)0.1p(X|1)0.2, p(X|2)0.4110, 126, 211, 220(1) 根据例2.1的计算结果可知后验概率为 P(1|X)0.818 P(2|X)0.182 (2) 再计算出条件风险(3) 作出决策由于R(1|X)R(2|X)即决策为2的条件风险小于决策为1的条件风险，因此应采取决策行动2，即判待识别的细胞X为2类异常细胞。jjjjjjRXPXPXRXPXPX(|)(|)(|).(|)(|)(|).211122122221111 0920 818两种决策方法之间的关系 基于最小错误率的决策是基于最小风险决策的

15、特例 设损失函数为 正确决策,没有损失;错误决策:损失为1. -0-1损失 此时，条件风险为 R(i|X)最小即是P(i|X)最大 可见：最小错误率贝叶斯决策就是可见：最小错误率贝叶斯决策就是0-1损失函数下损失函数下的最小风险贝叶斯决策的最小风险贝叶斯决策cciijjjijjj iR aXaPXPXPX ,(|)(|) (|)(|)(|)111ijijai jcij(|), ,.,01 21最小错误率决策与最小风险决策的最小错误率决策与最小风险决策的似然比及错误率似然比及错误率p XPl xp XP(|)()( ),(|)()1221如果X1Pp Xl xp XP()(|)( ),(|)()

16、1 222211 12121（-）如果（-）（1）似然比门限不同；（2）错误率不同2.1.3 判别函数、决策面与分类器设计 决策域：决策域：各类别在特征空间内所占的区域。 分类决策：分类决策：待识别的特征向量落在哪个决策域，该样本就被判为哪一类。决策面及决策面方程：决策面及决策面方程：决策域的边界面就是决策面，在数学上用解析形式表示成决策面方程。判别函数：判别函数：用于表达决策规则的某些函数则称为判别函数。一、判别函数及决策面例：两类别问题按最小错误率决策的判别函数及决策面 决策规则 ：若P(1|X) P(2|X)，则X 1 可设判别函数 ：gi(X)P(i|X), i=1,2 则决策面方程为

17、 ：g1(X)g2(X) 基于判别函数的决策规则如果gi(X)gj(X) ; i, j=1,2 且 ij则Xi 多类别情况 若各类判别函数为： 则决策规则为：如果 则X i 决策面及决策面方程 当i的决策域与j的决策域相邻时，相应的决策面为：gi(X)gj(X) ijjcg XgX,.,()max()1ig Xic(), ,.,1 2决策面 决策面是一种统称 特征空间是一维时，一个决策面实际上只是一个点。 二维特征空间里，决策面是一条曲线。 三维则是一曲面。 超过三维的空间，决策面是一个超曲面。 三类别问题用一维特征空间时的所有决策边界 两类别问题的二维特征空间中的决策边界 二、分类器设计 可

18、看成是硬件或软件组成的一个“机器” 其功能是计算待识别的特征向量的判别函数，然后根据判别函数的大小进行决策。两类别分类器的框图此时，可用一个判别函数：g(x)=g1(x)-g2(x)决策规则：g(x)0，则判X属于1 g(x)10）时，h(x)服从正态分布，则可计算h(x)的均值和方差：(ij, ij易统计得到）diiliilldiiiillE h xEh xE h x ( )|()| ( ) |12221负对数似然比：类条件概率密度：错误率的计算同1（正态分布且协方差阵相等）二、错误率上界Chernoff界限界限ssP esstP ess tssh p hdhdstdsPtPP ePPs ( )exp( )( )exp( )(