哈工大模式识别课件

1、模式识别模式识别模式识别模式识别第一章第一章 绪论绪论模式识别 绪论一、模式识别的概念一、模式识别的概念p什么是模式识别？什么是模式识别？p模式识别研究的内容？模式识别研究的内容？模式识别 绪论二、模式识别的应用二、模式识别的应用p工业用途：产品质量检验，设备故障检测，智工业用途：产品质量检验，设备故障检测，智能机器人的感知系统；能机器人的感知系统；p商业用途：钱币的自动识伪，信函的自动分拣，商业用途：钱币的自动识伪，信函的自动分拣，电话信息查询，声控拨号；电话信息查询，声控拨号；p医学用途：对心电、脑电、医学用途：对心电、脑电、CT等信号进行处等信号进行处理和识别，自动进行疾病的诊断；理和识

2、别，自动进行疾病的诊断；p安全领域：生理特征鉴别安全领域：生理特征鉴别(Biometrics)，网，网上电子商务的身份确认，对公安对象的刑侦和上电子商务的身份确认，对公安对象的刑侦和鉴别；鉴别； 模式识别 绪论二、模式识别的应用二、模式识别的应用p军事领域：巡航导弹的景物识别，战斗单元的军事领域：巡航导弹的景物识别，战斗单元的敌我识别；敌我识别； p办公自动化：文字识别技术和声音识别技术；办公自动化：文字识别技术和声音识别技术； p数据挖掘：数据分析；数据挖掘：数据分析； p网络应用：文本分类。网络应用：文本分类。 模式识别 绪论三、相关领域三、相关领域p人工智能：人工智能：Artificia

3、l Intelligence (AI)p模式识别：模式识别：Pattern Recognition (PR)p机器学习：机器学习：Machine Learningp人工神经网络：人工神经网络：Neural Network (NN)p计算机视觉：计算机视觉：Computer Vision (CV)模式识别 绪论四、模式识别的过程四、模式识别的过程模式识别 绪论什么是特征？什么是特征？模式识别 绪论什么是特征？什么是特征？模式识别 绪论什么是特征？什么是特征？模式识别 绪论特征抽取特征抽取模式识别 绪论特征抽取特征抽取模式识别 绪论特征的分布特征的分布模式识别 绪论特征的分布特征的分布模式识别 绪

4、论五、模式识别系统五、模式识别系统 分类分类训练训练模式识别 绪论六、模式识别问题的描述六、模式识别问题的描述给定一个训练样本的特征矢量集合：给定一个训练样本的特征矢量集合：分别属于分别属于c个类别：个类别：设计出一个分类器，能够对未知类别样本设计出一个分类器，能够对未知类别样本x进行分类进行分类2,dniDR1x xxx12,c ,1,dygRcx模式识别 绪论分类方法分类方法模式识别 绪论模式识别方法的分类模式识别方法的分类p有监督学习（有教师学习）：预先已知训有监督学习（有教师学习）：预先已知训练样本集中每个样本的类别标号；练样本集中每个样本的类别标号；p无监督学习（无教师学习）：预先不

5、知道无监督学习（无教师学习）：预先不知道训练样本集中每个样本的类别标号；训练样本集中每个样本的类别标号；模式识别 绪论七、参考书目七、参考书目pRichard Duda, Peter Hart, David Stork, Pattern Classification, 2nd edition, John Wiley, 2001p模式分类模式分类，机械工业出版社，机械工业出版社，Richard O. Dudap模式识别模式识别（第二版），清华大学出版社，边（第二版），清华大学出版社，边肇祺，张学工；肇祺，张学工；模式识别 绪论期刊期刊pIEEE Transaction on Pattern An

6、alysis and Machine Intelligence，PAMI；pPattern Recognition；pPattern Recognition Letter；p模式识别与人工智能；模式识别与人工智能；p讲义下载讲义下载:22用户名用户名: prai 密码密码: prai模式识别第二章第二章 贝叶斯决策理论贝叶斯决策理论模式识别 绪论2.1 最小错误率准则最小错误率准则模式识别 绪论各种概率及其关系各种概率及其关系p先验概率：先验概率：p后验概率：后验概率：p类条件概率：类条件概率：p贝叶斯公式：贝叶斯公式：iPiPxiPx iiiPPPPxxx

7、模式识别 绪论两个类别，一维特征两个类别，一维特征模式识别 绪论两类问题的错误率两类问题的错误率p观察到特征观察到特征x时作出判别的错误率：时作出判别的错误率：1221,PP errorPxxx判定判定 两类问题最小错误率判别准则：两类问题最小错误率判别准则：121122,PPPPxxxxxx如果如果模式识别 绪论多类问题最小错误率多类问题最小错误率p判别判别x属于属于i i的错误率：的错误率：1jij iP errorPP xxx 判别准则为：判别准则为：1argmax,jj ciP xix则：则：模式识别 绪论贝叶斯最小错误率准则贝叶斯最小错误率准则 jjjpPPpxxx jjjgpPxx

8、 1argmaxjj cig xixBayes判别准则：判别准则：，则模式识别 绪论贝叶斯分类器的错误率估计贝叶斯分类器的错误率估计11iciiRP errorpdxx1px2px模式识别 绪论例例2.1p 对一大批人进行癌症普查，设对一大批人进行癌症普查，设1 1类代表患癌类代表患癌症，症，2 2类代表正常人。已知先验概率：类代表正常人。已知先验概率：120.005,0.995PP以一个化验结果作为特征以一个化验结果作为特征x: 阳性，阴性阳性，阴性，患癌症，患癌症的人和正常人化验结果为阳性的概率分别为：的人和正常人化验结果为阳性的概率分别为：现有一人化验结果为阳性，问此人是否患癌症？现有一

9、人化验结果为阳性，问此人是否患癌症？120.95,0.01P xP x阳性阳性模式识别 绪论2.2 最小平均风险准则贝叶斯分最小平均风险准则贝叶斯分 类器类器p问题的提出问题的提出 有有c个类别个类别1, 2 ,. , c, 将将i i类的样本判类的样本判别为别为j j类的代价为类的代价为ij。p将未知模式将未知模式x判别为判别为j j类类的平均风险为：的平均风险为： 1cjijiiPxx模式识别 绪论最小平均风险判别准则最小平均风险判别准则p利用利用Bayes公式，构造判别函数：公式，构造判别函数： jjg xx 1cjijiiiPPxx模式识别 绪论贝叶斯分类器贝叶斯分类器模式识别 绪论例

10、例2.2p 对一大批人进行癌症普查，设对一大批人进行癌症普查，设1类代表患癌症，类代表患癌症，2类代表正常人。已知先验概率：类代表正常人。已知先验概率：120.005,0.995PP以一个化验结果作为特征以一个化验结果作为特征x: 阳性，阴性阳性，阴性，患癌症，患癌症的人和正常人化验结果为阳性的概率分别为：的人和正常人化验结果为阳性的概率分别为：判别代价：判别代价： 11 = 0, 22 = 0, 12 = 100, 21 = 25现有一人化验结果为阳性，问此人是否患癌症？现有一人化验结果为阳性，问此人是否患癌症？120.95,0.01PxPx阳 性阳 性模式识别 绪论2.3 贝叶斯分类器的其

11、它版本贝叶斯分类器的其它版本p先验概率先验概率P(i i)未知：极小化极大准则；未知：极小化极大准则；p约束一定错误率（风险）：约束一定错误率（风险）：Neyman-Pearson准则；准则；p某些特征缺失的决策：某些特征缺失的决策：p连续出现的模式之间统计相关的决策：连续出现的模式之间统计相关的决策：模式识别 绪论2.4 正态分布的贝叶斯分类器正态分布的贝叶斯分类器p单变量正态分布密度函数（高斯分布）：单变量正态分布密度函数（高斯分布）： 211e x p22xpx 模式识别 绪论11 2211exp22tiiiidipxxx多元正态分布函数多元正态分布函数模式识别 绪论正态分布的判别函数正

12、态分布的判别函数p贝叶斯判别函数可以写成对数形式：贝叶斯判别函数可以写成对数形式： lnlniiigpPxx 类条件概率密度函数为正态分布时：类条件概率密度函数为正态分布时： 111ln2lnln222tiiiiiidgP xxx模式识别 绪论情况一情况一：21,iiPcI 2tiiiigxx x x 判别函数可以写成：判别函数可以写成： 此分类器称为距离分类器，判别函数可以用此分类器称为距离分类器，判别函数可以用待识模式待识模式x与类别均值与类别均值i i之间的距离表示：之间的距离表示： ,iigdxx 模式识别 绪论情况二：情况二：i 11ln2tiiiigPxx x 1101ln2ttt

13、iiiiiiigPwx x w x 判别函数可以写成：判别函数可以写成： 可以简化为：可以简化为：称为线性分类器称为线性分类器模式识别 绪论线性分类器线性分类器 两类问题，两类问题，1维特征，先验概率相同时：维特征，先验概率相同时：模式识别 绪论线性分类器线性分类器 两类问题，高维特征，先验概率相同时：两类问题，高维特征，先验概率相同时：模式识别 绪论线性分类器线性分类器 两类问题，两类问题，1维特征，先验概率不同时：维特征，先验概率不同时：模式识别 绪论线性分类器线性分类器 两类问题，高维特征，先验概率不同时：两类问题，高维特征，先验概率不同时：模式识别 绪论情况三：情况三： 任意任意i 判

14、别函数可以写成：判别函数可以写成： 分类界面为分类界面为2次曲线（面）次曲线（面） 111111lnln222tttiiiiiiiiigP xx x x 模式识别 绪论二次分类曲线二次分类曲线模式识别 绪论二次分类曲面二次分类曲面模式识别第三章第三章 概率密度函数的概率密度函数的参数估计参数估计模式识别 绪论3.0 引言引言p贝叶斯分类器中最主要的问题是类条件概率密贝叶斯分类器中最主要的问题是类条件概率密度函数的估计。度函数的估计。p问题可以表示为：已有问题可以表示为：已有c个类别的训练样本集个类别的训练样本集合合D1，D2，Dc，求取每个类别的类条件，求取每个类别的类条件概率密度概率密度 。

15、ipx模式识别 绪论概率密度函数的估计方法概率密度函数的估计方法p参数估计方法：预先假设每一个类别的概率密度参数估计方法：预先假设每一个类别的概率密度函数的形式已知，而具体的参数未知；函数的形式已知，而具体的参数未知；n最大似然估计最大似然估计(MLE, Maximum Likelihood Estimation)；n贝叶斯估计贝叶斯估计(Bayesian Estimation)。p非参数估计方法。非参数估计方法。模式识别 绪论3.1 最大似然估计最大似然估计p样本集样本集D中包含中包含n个样本：个样本：x1，x2， , xn，样，样本都是本都是独立同分布独立同分布的随机变量的随机变量(i.i

16、.d，independent identically distributed)。p对类条件概率密度函数的函数形式作出假设，参对类条件概率密度函数的函数形式作出假设，参数可以表示为参数矢量数可以表示为参数矢量：,iipx模式识别 绪论似然函数似然函数p由独立同分布假设，样本集由独立同分布假设，样本集D出现的概率为：出现的概率为：121,nniip Dppx xx x 定义对数似然函数：定义对数似然函数： 1lnlnniilp Dpx 模式识别 绪论最大似然估计最大似然估计p最大似然估计就是要寻找到一个最优矢量最大似然估计就是要寻找到一个最优矢量 ，使，使得似然函数得似然函数 最大。最大。 arg

17、maxl l 模式识别 绪论正态分布的似然估计正态分布的似然估计pGauss分布的参数由均值矢量分布的参数由均值矢量和协方差矩阵和协方差矩阵构成，最大似然估计结果为：构成，最大似然估计结果为：11ntiiinxx11niinx模式识别 绪论3.2 贝叶斯估计贝叶斯估计p已有独立同分布训练样本集已有独立同分布训练样本集D；p已知类条件概率密度函数已知类条件概率密度函数p(x|)的形式，但参数的形式，但参数未知；未知；p已知参数已知参数的先验概率密度函数的先验概率密度函数p()；p求在已有训练样本集求在已有训练样本集D的条件下，类条件概率密的条件下，类条件概率密度函数度函数p(x|D)。模式识别

18、绪论贝叶斯估计与最大似然估计的差别贝叶斯估计与最大似然估计的差别p最大似然估计认为最大似然估计认为是一个确定的未知矢量；是一个确定的未知矢量；p贝叶斯估计认为贝叶斯估计认为是一个随机变量，以一定的概是一个随机变量，以一定的概率分布取所有可能的值。率分布取所有可能的值。模式识别 绪论贝叶斯估计的一般理论贝叶斯估计的一般理论 ,pDpD dppD dxx x 由于参数矢量由于参数矢量是一个随机变量，所以类是一个随机变量，所以类条件概率可以用下式计算：条件概率可以用下式计算： 11niiniippp DppDp Dpdppdx x 根据贝叶斯公式，有：根据贝叶斯公式，有：模式识别 绪论单变量正态分布

19、的贝叶斯估计单变量正态分布的贝叶斯估计2,p xN 已知概率密度函数满足正态分布，其中方已知概率密度函数满足正态分布，其中方差差2 2已知，均值已知，均值未知，假设未知，假设的先验概的先验概率满足正态分布，即：率满足正态分布，即： 200,pN 模式识别 绪论均值的后验概率均值的后验概率 1niip DppDp xpp Dpd202222100111exp22niiNx经推导可得，在已知训练样本集合经推导可得，在已知训练样本集合D的条件的条件下，参数下，参数的分布：的分布：211exp22nnn模式识别 绪论均值的后验概率均值的后验概率均值的后验概率仍满足正态分布，其中：均值的后验概率仍满足正

20、态分布，其中：2200222200nnnnn11nniixn2220220nn 模式识别 绪论均值分布的变化均值分布的变化模式识别 绪论类条件概率密度的计算类条件概率密度的计算 p x Dp xpD d221111expexp2222nnnxd222,1exp22nnnnfx 2222222221,exp2nnnnnnxfdu 模式识别 绪论3.3期望最大化算法期望最大化算法(EM算法算法)pEM算法的应用可以分为两个方面：算法的应用可以分为两个方面：1.训练样本中某些特征丢失情况下，分布参数的最大训练样本中某些特征丢失情况下，分布参数的最大似然估计；似然估计；2.对某些复杂分布模型假设，最大

21、似然估计很难得到对某些复杂分布模型假设，最大似然估计很难得到解析解时的迭代算法。解析解时的迭代算法。模式识别 绪论基本基本EM算法算法p令令X是观察到的样本数据集合，是观察到的样本数据集合，Y为丢失的数为丢失的数据集合，完整的样本集合据集合，完整的样本集合D=X Y。p DpX,Y lnllDlp X,YX,Y 由于由于Y未知，在给定参数未知，在给定参数时，时，似然函数可以似然函数可以看作看作Y的函数：的函数：模式识别 绪论基本基本EM算法算法p由于由于Y未知，因此我们需要寻找到一个在未知，因此我们需要寻找到一个在Y的的所有可能情况下，平均意义下的似然函数最所有可能情况下，平均意义下的似然函数

22、最大值，即似然函数对大值，即似然函数对Y的期望的最大值：的期望的最大值：11,iiQElY X,YX 1argmaxiiQ 1ln,iEpYX,Y X 模式识别 绪论基本基本EM算法算法1.begin initialize ，T，i0；2. do ii+13. E步：计算步：计算 ; ;4. M步：步：5. until 6.return 01iQ 11iiiiQQT 1i1argmaxiiQ 模式识别 绪论混合密度模型混合密度模型p一个复杂的概率密度分布函数可以由多个简一个复杂的概率密度分布函数可以由多个简单的密度函数混合构成：单的密度函数混合构成：1,Miiiipa px x 最常用的是高斯

23、混合模型最常用的是高斯混合模型(GMM，Gauss Mixture Model)： 1;Miiiipa Nxx ,11Miia模式识别 绪论GMM模型产生的模型产生的2维样本数据维样本数据模式识别 绪论两个高斯函数的混合两个高斯函数的混合 0.710,20.3 (5,3)p xNN模式识别 绪论混合密度模型的参数估计混合密度模型的参数估计p混合密度模型的参数可以表示为：混合密度模型的参数可以表示为：1212,MMa aa 参数的估计方法：参数的估计方法：1. 利用最优化方法直接对似然函数进行优化，如利用最优化方法直接对似然函数进行优化，如梯度下降法；梯度下降法；2. 引入未知隐变量引入未知隐变

24、量Y对问题进行简化，将对问题进行简化，将Y看作丢看作丢失的数据，使用失的数据，使用EM算法进行优化。算法进行优化。模式识别 绪论GMM模型的参数估计模型的参数估计p首先引入隐含数据集合首先引入隐含数据集合:12,nYy yy 其中：其中： 代表第代表第i个训练样本是个训练样本是由第由第 个高斯函数产生的，将个高斯函数产生的，将Y作为丢失作为丢失数据集合，采用数据集合，采用EM算法进行迭代估计。算法进行迭代估计。1,iyMiy模式识别 绪论GMM参数的参数的EM估计算法估计算法1.设定混合模型数设定混合模型数M，初始化模型参数，初始化模型参数 ，阈值，阈值T，i0；2.用下列公式迭代计算模型参数

25、，直到似然函数变化用下列公式迭代计算模型参数，直到似然函数变化小于小于T为止：为止：01,iimmtmitMiijjtjja pp ma px x x 111,niimttap mnx 111,nittitmnittp mp mxx x 11111,ntiiittmtmitmnittp mp mx xxx 模式识别 绪论EM算法的性质算法的性质pEM算法具有收敛性；算法具有收敛性；pEM算法只能保证收敛于似然函数的局部最大值算法只能保证收敛于似然函数的局部最大值点（极值点），而不能保证收敛于全局最优点。点（极值点），而不能保证收敛于全局最优点。模式识别 绪论隐含隐含Markov模型模型 (Hi

26、dden Markov Model, HMM)p有一些模式识别系统处理的是与时间相关的问有一些模式识别系统处理的是与时间相关的问题，如语音识别，手势识别，唇读系统等；题，如语音识别，手势识别，唇读系统等；p对这类问题采用一个特征矢量序列描述比较方对这类问题采用一个特征矢量序列描述比较方便，这类问题的识别便，这类问题的识别HMM取得了很好的效果。取得了很好的效果。模式识别 绪论输入语音波形输入语音波形模式识别 绪论观察序列观察序列p信号的特征需要用一个特征矢量的序列来表示：信号的特征需要用一个特征矢量的序列来表示：12,TTVv vv 其中的其中的vi为一个特征矢量，称为一个观察值。为一个特征矢

27、量，称为一个观察值。模式识别 绪论一阶一阶Markov模型模型p一阶一阶Markov模型由模型由M个状态构成，在每个时刻个状态构成，在每个时刻t，模型处于某个状态模型处于某个状态w(t)，经过，经过T个时刻，产生出一个个时刻，产生出一个长度为长度为T的状态序列的状态序列WT=w(1),w(T)。模式识别 绪论一阶一阶Markov模型的状态转移模型的状态转移p模型在时刻模型在时刻t处于状态处于状态wj的概率完全由的概率完全由t-1时刻时刻的状态的状态wi决定，而且与时刻决定，而且与时刻t无关，即：无关，即： 1TP w t WP w t w t 1jiijP w tw ta模式识别 绪论Mark

28、ov模型的初始状态概率模型的初始状态概率p模型初始于状态模型初始于状态wi的概率用的概率用 表示。表示。p完整的一阶完整的一阶Markov模型可以用参数模型可以用参数 表示，其中：表示，其中： i,A1,M111212122212MMMMMMaaaaaaAaaa模式识别 绪论一阶一阶Markov模型输出状态序列的模型输出状态序列的概率概率p模型输出状态序列的概率可以由初始状态概率模型输出状态序列的概率可以由初始状态概率与各次状态转移概率相乘得到。与各次状态转移概率相乘得到。p例如：例如：W5=w1, w1, w3, w1, w2，则模型，则模型输出该序列的概率为：输出该序列的概率为：51111

29、33112P Wa a a a模式识别 绪论一阶隐含一阶隐含Markov模型模型p隐含隐含Markov模型中，状态是不可见的，在每一模型中，状态是不可见的，在每一个时刻个时刻t，模型当前的隐状态可以输出一个观察值。，模型当前的隐状态可以输出一个观察值。p隐状态输出的观察值可以是离散值，连续值，也隐状态输出的观察值可以是离散值，连续值，也可以是一个矢量。可以是一个矢量。模式识别 绪论HMM的工作原理的工作原理pHMM的内部状态转移过程同的内部状态转移过程同Markov模型相同，在模型相同，在每次状态转移之后，由该状态输出一个观察值，只是每次状态转移之后，由该状态输出一个观察值，只是状态转移过程无

30、法观察到，只能观察到输出的观察值状态转移过程无法观察到，只能观察到输出的观察值序列。序列。p以离散的以离散的HMM为例，隐状态可能输出的观察值集合为为例，隐状态可能输出的观察值集合为v1, v2, , vK，第，第i个隐状态输出第个隐状态输出第k个观察值的个观察值的概率为概率为bik。p例如：例如：T=5时，可能的观察序列时，可能的观察序列V5=v3v2v3v4v1模式识别 绪论HMM的工作过程的工作过程模式识别 绪论HMM的参数表示的参数表示p状态转移矩阵：状态转移矩阵：A，M*M的方阵；的方阵；p状态输出概率：状态输出概率：B，M*K的矩阵；的矩阵；p初始概率：初始概率：，包括，包括M个元

31、素。个元素。M个状态，个状态，K个可能的输出值。个可能的输出值。, A B模式识别 绪论HMM的三个核心问题的三个核心问题p估值问题：已有一个：已有一个HMM模型，其参数已知，模型，其参数已知，计算这个模型输出特定的观察序列计算这个模型输出特定的观察序列VT的概率；的概率；p解码问题：已有一个：已有一个HMM模型，其参数已知，模型，其参数已知，计算最有可能输出特定的观察序列计算最有可能输出特定的观察序列VT的隐状态的隐状态转移序列转移序列WT；p学习问题：已知一个：已知一个HMM模型的结构，其参数模型的结构，其参数未知，根据一组训练序列对参数进行训练；未知，根据一组训练序列对参数进行训练；模式

32、识别 绪论估值问题估值问题p一个一个HMM模型产生观察序列模型产生观察序列VT可以由下式计算：可以由下式计算： max1rTTTTrrrP VP VWP Wrmax=MT为为HMM所有可能的状态转移序列数；所有可能的状态转移序列数； 为状态转移序列为状态转移序列 输出观察序列输出观察序列 的概的概率；率； 为为 状态转移序列状态转移序列 发生的概率。发生的概率。 TTrP VWTrP WTrWTVTrW模式识别 绪论估值问题的计算估值问题的计算 112231rrrrrrrTrwwwwww Tw TP Waaa 1212rrrTTrwwwTP VWbvbvbv T max11122112rrrr

33、rrTwwwwwrP Vbvabv 1rrrwTwTwTabv Tp计算复杂度：计算复杂度：TO M T模式识别 绪论HMM估值算法的简化估值算法的简化模式识别 绪论HMM的前向算法的前向算法1.初始化：初始化：2.迭代计算：迭代计算：3.结束输出：结束输出： 11,1,iiib viM 111 ,1,Mijjiijtt ab v tiM 1MTiiP VT计算复杂度：计算复杂度：2O M T模式识别 绪论解码问题解码问题p解码问题的计算同估值问题的计算类似，最直观的解码问题的计算同估值问题的计算类似，最直观的思路是遍历所有的可能状态转移序列，取出最大值，思路是遍历所有的可能状态转移序列，取出

34、最大值，计算复杂度为：计算复杂度为：O(MTT)。p同样存在着优化算法：同样存在着优化算法：Viterbi算法。算法。模式识别 绪论Viterbi算法算法1.因为需要回朔最优路径，所以建立一个矩阵因为需要回朔最优路径，所以建立一个矩阵，其元，其元素素 保存第保存第t t步，第步，第i i个状态在第个状态在第t-1t-1步的最优状态。步的最优状态。 ti2.2. 初始化：初始化：3.3. 迭代计算：迭代计算：4.4. 结束：结束：5.5. 路径回朔：路径回朔： 11,1,iiibviM 10i 11max1 ,1,ijjiij Mtt ab v tiM 11argmaxijjij Mtt a *

35、1max,Tjj MPVT *1argmaxjj MwTT *11wtwtt模式识别 绪论Viterbi算法图示算法图示模式识别 绪论学习问题学习问题pHMM的学习问题：的学习问题：已知一组观察序列已知一组观察序列(训练样本集合训练样本集合)：1212,nTTTnVVVV如何确定最优的模型参数如何确定最优的模型参数，使得模型产生训，使得模型产生训练集合练集合V V的联合概率最大的联合概率最大max P V这同样是一个最大似然估计问题，需要采用这同样是一个最大似然估计问题，需要采用EMEM算算法。法。模式识别 绪论图示图示模式识别 绪论变量说明变量说明p ：表示在：表示在t-1时刻时刻HMM处于

36、状态处于状态i，并且，并且从从1t-1时刻之间产生观察序列时刻之间产生观察序列V1t-1的概率；的概率；p ：表示在：表示在t时刻时刻HMM处于状态处于状态j，并且从，并且从t+1T时刻之间产生观察序列时刻之间产生观察序列Vt+1T的概率；的概率；1it jt 11iiib v1121Mijjiijttab v t 1jT 111Mjjiijitatbv t模式识别 绪论变量说明变量说明p输出观察序列输出观察序列VT时，在时，在t-1时刻时刻HMM处于处于i状态，在时刻状态，在时刻t处于处于j状态的概率：状态的概率： 1iijjjijTta bv tttP V模式识别 绪论前向前向-后向算法后

37、向算法(Baum-Welch算法算法)p迭代公式：迭代公式：初始概率：初始概率：状态转移概率：状态转移概率：输出概率：输出概率： 11Miijj 111TijtijTMiktktat 1,111kTMiltv tvlikTMiltltb vt 模式识别 绪论HMM的其它问题的其它问题p连续连续HMM模型：在观察序列中每个观察值是一个特征模型：在观察序列中每个观察值是一个特征矢量，相应的模型中输出概率矢量，相应的模型中输出概率b就需要用一个概率密度就需要用一个概率密度函数描述，其函数形式需要假设，通常使用函数描述，其函数形式需要假设，通常使用GMM。p训练问题：通常可以用每个训练样本分别计算训练

38、问题：通常可以用每个训练样本分别计算值，然值，然后分子和分母部分分别进行累加，最后统一进行参数修后分子和分母部分分别进行累加，最后统一进行参数修正；正；p模型的拓扑结构：模型结构可以根据实际问题的需要来模型的拓扑结构：模型结构可以根据实际问题的需要来设计，在初始化状态转移矩阵设计，在初始化状态转移矩阵A时，将某些元素设为时，将某些元素设为0即可。即可。模式识别 绪论“左左-右右”模型结构模型结构123模式识别 绪论带跨越的带跨越的“左左-右右”结构结构HMM模模型型1234模式识别第四章第四章 概率密度函数的概率密度函数的非参数估计非参数估计模式识别 绪论4.1 基本思想基本思想模式识别 绪论

39、4.1 基本思想基本思想p令令R是包含样本点是包含样本点x的一个区域，其体积为的一个区域，其体积为V，设有设有n个训练样本，其中有个训练样本，其中有k个落在区域个落在区域R中，中，则可对概率密度作出一个估计：则可对概率密度作出一个估计： k npVxp相当于用相当于用R区域内的平均性质来作为一点区域内的平均性质来作为一点x的估的估计，是一种数据的平滑。计，是一种数据的平滑。模式识别 绪论有效性有效性p当当n固定时，固定时，V的大小对估计的效果影响很的大小对估计的效果影响很大，过大则平滑过多，不够精确；过小则大，过大则平滑过多，不够精确；过小则可能导致在此区域内无样本点，可能导致在此区域内无样本

40、点，k=0。p此方法的有效性取决于样本数量的多少，此方法的有效性取决于样本数量的多少，以及区域体积选择的合适。以及区域体积选择的合适。模式识别 绪论收敛性收敛性p构造一系列包含构造一系列包含x的区域的区域R1, R2, ，对应，对应n=1,2,，则，则对对p(x)有一系列的估计：有一系列的估计： nnnk npVxp 当满足下列条件时，当满足下列条件时，pn(x)收敛于收敛于p (x)：lim0nnVlimnnk lim0nnkn模式识别 绪论区域选定的两个途径区域选定的两个途径pParzen窗法：区域体积窗法：区域体积V是样本数是样本数n的函数，如：的函数，如：1nVnpK-近邻法：落在区域

41、内的样本数近邻法：落在区域内的样本数k是总样本数是总样本数n的的函数，如：函数，如：nkn模式识别 绪论Parzen窗法和窗法和K-近邻法近邻法模式识别 绪论4.2 Parzen窗方法窗方法p定义窗函数定义窗函数 1,1 20,juu其它1,20,jijnnxxhhix-x其它dnnVh1,jd 模式识别 绪论1维数据的窗函数维数据的窗函数模式识别 绪论概率密度函数的估计概率密度函数的估计p超立方体中的样本数：超立方体中的样本数：p概率密度估计：概率密度估计：1nninkhix-x 111nninnpnVhix-xx模式识别 绪论窗函数的要求窗函数的要求p上述过程是一个内插过程，样本上述过程是

42、一个内插过程，样本xi距离距离x越近，越近，对概率密度估计的贡献越大，越远贡献越小。对概率密度估计的贡献越大，越远贡献越小。p只要满足如下条件，就可以作为窗函数：只要满足如下条件，就可以作为窗函数： 0u 1duu模式识别 绪论窗函数的形式窗函数的形式模式识别 绪论窗函数的宽度对估计的影响窗函数的宽度对估计的影响phn称为窗的宽度称为窗的宽度模式识别 绪论窗函数的宽度对估计的影响窗函数的宽度对估计的影响模式识别 绪论识别方法识别方法1.保存每个类别所有的训练样本；保存每个类别所有的训练样本；2.选择窗函数的形式，根据训练样本数选择窗函数的形式，根据训练样本数n选择窗函选择窗函数的数的h宽度；宽

43、度；3.识别时，利用每个类别的训练样本计算待识别识别时，利用每个类别的训练样本计算待识别样本样本x的类条件概率密度：的类条件概率密度：4.采用采用Bayes判别准则进行分类。判别准则进行分类。111iinjnijinpnVhx-xx模式识别 绪论Parzen窗的神经网络实现窗的神经网络实现p神经元模型神经元模型1dtiiinetw xw xtyf netfw x模式识别 绪论简化神经元模型简化神经元模型模式识别 绪论Parzen窗函数的神经元表示窗函数的神经元表示p窗函数取窗函数取Gauss函数，所有的样本归一化，令神经元的函数，所有的样本归一化，令神经元的权值等于训练样本，即：权值等于训练样

44、本，即：,kkwx21,txx x21tkkkww w 2exp2tkkknhxwxwxw221expexp2knettttkkkx x+w w -2w xp 则有：则有：模式识别 绪论概率神经网络概率神经网络(PNN, Probabilistic Neural Network)模式识别 绪论PNN的训练算法的训练算法1.begin initialize j = 0; n =训练样本数，训练样本数，aij=02.do j j + 13. normalize :4. train : wjxj5. if then aji16.until j = njjjxxxjix模式识别 绪论PNN分类算法分类

45、算法1.begin initialize k = 0; x 待识模式待识模式2. do k k + 13. 4. if aki = 1 then 5. until k = n6. return 7.endTkknet w x2exp1iikyynet1argmaxii cclassy 模式识别 绪论径向基函数网络径向基函数网络(RBF, Radial Basis Function)pRBF与与PNN的差异的差异1.PNN模式层神经元数等于训练样本数，而模式层神经元数等于训练样本数，而RBF小于小于等于训练样本数；等于训练样本数；2.PNN模式层到类别层的连接权值恒为模式层到类别层的连接权值恒为

46、1，而，而RBF的的需要训练；需要训练；3.PNN的训练过程简单，只需一步设置即可，而的训练过程简单，只需一步设置即可，而RBF一般需要反复迭代训练；一般需要反复迭代训练；模式识别 绪论径向基函数网络的训练径向基函数网络的训练pRBF的训练的三种方法：的训练的三种方法：1.根据经验选择每个模式层神经元的权值根据经验选择每个模式层神经元的权值wi以及映射函以及映射函数的宽度数的宽度，用最小二乘法计算模式层到类别层的权，用最小二乘法计算模式层到类别层的权值值；2.用聚类的方法设置模式层每个神经元的权值用聚类的方法设置模式层每个神经元的权值wi以及映以及映射函数的宽度射函数的宽度，用最小二乘法计算模

47、式层到类别层，用最小二乘法计算模式层到类别层的权值的权值；3.通过训练样本用误差纠正算法迭代计算各层神经元的通过训练样本用误差纠正算法迭代计算各层神经元的权值，以及模式层神经元的宽度权值，以及模式层神经元的宽度；模式识别 绪论4.3 近邻分类器近邻分类器p后验概率的估计后验概率的估计Parzen窗法估计的是每个类别的类条件概率密窗法估计的是每个类别的类条件概率密度度 ，而，而k-近邻法是直接估计每个类别的后验概近邻法是直接估计每个类别的后验概率率 。将一个体积为将一个体积为V的区域放到待识样本点的区域放到待识样本点x周围，包含周围，包含k个训个训练样本点，其中练样本点，其中ki个属于个属于i类

48、，总的训练样本数为类，总的训练样本数为n，则，则有：有：ipxipx,inik npVx 1,niniiicnnjjppkppkpxxxxx模式识别 绪论k-近邻分类器近邻分类器pk-近邻分类算法近邻分类算法1.设置参数设置参数k，输入待识别样本，输入待识别样本x；2.计算计算x与每个训练样本的与每个训练样本的距离距离；3.选取距离最小的前选取距离最小的前k个样本，统计其中包含个样本，统计其中包含各个类别的样本数各个类别的样本数ki；4. 1argmaxii cclassk 模式识别 绪论k-近邻分类，近邻分类，k=13模式识别 绪论最近邻规则最近邻规则p分类规则：在训练样本集中寻找与待识别样

49、本分类规则：在训练样本集中寻找与待识别样本x距离最近的样本距离最近的样本x，将，将x分类到分类到x所属的类别。所属的类别。p最近邻规则相当于最近邻规则相当于k=1的的k-近邻分类，其分类界近邻分类，其分类界面可以用面可以用Voronoi网格表示。网格表示。模式识别 绪论Voronoi网格网格模式识别 绪论距离度量距离度量p距离度量应满足如下四个性质：距离度量应满足如下四个性质：1.非负性：非负性：2.自反性：自反性： 当且仅当当且仅当3.对称性：对称性：4.三角不等式：三角不等式：0Da,b0Da,babDDa,bb,aDDDa,bb,ca,c模式识别 绪论常用的距离函数常用的距离函数 121

50、221,dtiiiDxyx yx-yx-yp欧几里德距离：欧几里德距离：(Eucidean Distance) 模式识别 绪论常用的距离函数常用的距离函数p街市距离：街市距离：(Manhattan Distance)1,diiiDxyx y模式识别 绪论常用的距离函数常用的距离函数p明氏距离：明氏距离：(Minkowski Distance)11,mdmiiiDxyx y模式识别 绪论常用的距离函数常用的距离函数 1,tDx yx-y x-yp马氏距离：马氏距离：(Mahalanobis Distance) 模式识别 绪论常用的距离函数常用的距离函数p角度相似函数：角度相似函数：(Angle

51、Distance),tDx yx yx y模式识别 绪论常用的距离函数常用的距离函数1,tdxxx1,tdyyy ,0,1iix y p海明距离：海明距离：(Hamming Distance) x和和y为为2值特征矢量：值特征矢量： D(x,y)定义为定义为x,y中使得不等式中使得不等式 成立的成立的i的个的个数。数。iixy模式识别 绪论最近邻分类器的简化最近邻分类器的简化p最近邻分类器计算的时间复杂度和空间复杂度都最近邻分类器计算的时间复杂度和空间复杂度都为为O(dn)，d为特征维数，通常只有当样本数为特征维数，通常只有当样本数n非常大时，分类效果才会好。非常大时，分类效果才会好。p简化方

52、法可以分为三种：简化方法可以分为三种：1.部分距离法；部分距离法；2.预分类法；预分类法；3.剪辑近邻法。剪辑近邻法。模式识别 绪论部分距离法部分距离法p定义：定义：1221rriiiDxyx,yDr(x,y)是是r的单调不减函数。令的单调不减函数。令Dmin为当前搜索到的最近邻为当前搜索到的最近邻距离，当待识别样本距离，当待识别样本x与某个训练样本与某个训练样本xi的部分距离的部分距离Dr(x,xi)大于大于 Dmin时，时， Dd(x,xi)一定要大于一定要大于Dmin ，所以，所以xi一定不是最一定不是最近邻，不需要继续计算近邻，不需要继续计算Dd(x,xi) 。模式识别 绪论预分类（搜

53、索树）预分类（搜索树）模式识别 绪论预分类（搜索树）预分类（搜索树）p在特征空间中首先找到在特征空间中首先找到m个有代表性的样本点，个有代表性的样本点，用这些点代表一部分训练样本；用这些点代表一部分训练样本；p待识别模式待识别模式x首先与这些代表点计算距离，找到首先与这些代表点计算距离，找到一个最近邻，然后在这个最近邻代表的样本点中一个最近邻，然后在这个最近邻代表的样本点中寻找实际的最近邻点。寻找实际的最近邻点。p这种方法是一个次优的搜索算法。这种方法是一个次优的搜索算法。模式识别 绪论剪辑近邻法剪辑近邻法p最近邻剪辑算法最近邻剪辑算法1.begin initialize j = 0;D =

54、data set; n = number of training samples2.construct the full Voronoi diagram of D3.do j j + 1; 4. Find the Voronoi neighbors of Xj5. if any neighbor is not from the same class as Xj then mark Xj6.until j = n7.Discard all points that are not marked8.Construct the Voronoi diagram of the remaining samp

55、les9.end模式识别 绪论剪辑近邻法剪辑近邻法模式识别 绪论剪辑近邻法剪辑近邻法模式识别 绪论RCE网络网络模式识别 绪论RCE网络的训练算法网络的训练算法1.begin initialize j=0, n=#patterns, =small pattern, m=max radius，aij=02.do jj+13. train weight: wj=xj4. if then aji = 15. find nearest point not in i:6. set radius: 7.until j = nargminijDxxx ,xmin,jjmD x ,xjix模式识别 绪论模式识

56、别 绪论RCE网络的分类算法网络的分类算法1.begin initialize j=0, k=0, x, 2. do jj+13. if then4. until j = n5. if category of all is the same 6. then return the label7. else “ambiguous” labeltD ttjDDx,jjD x xjtD x模式识别 线性判别函数第五章第五章 线性判别函数线性判别函数模式识别 绪论5.1 线性判别函数和判别界面线性判别函数和判别界面模式识别 绪论线性不可分情况线性不可分情况模式识别 绪论线性判别函数线性判别函数px=(x

57、1, x2, xd)t: 特征矢量；特征矢量；pw=(w1, w2, , wd)t: 权矢量；权矢量；pw0：偏置：偏置(bias)。 0tgwxw x模式识别 绪论线性判别函数的增广形式线性判别函数的增广形式py=(1, x1, x2, xd)t: 增广的特征矢量；增广的特征矢量；pa=(w0, w1, w2, , wd)t: 增广的权矢量；增广的权矢量； tgya y模式识别 绪论两类问题线性判别准则两类问题线性判别准则 1020,0,0,tgwxxw xx拒识模式识别 绪论线性分类器的分类界面线性分类器的分类界面模式识别 绪论分类界面的几何解释分类界面的几何解释1.线性分类界面线性分类界

58、面H是是d维空间中的一个超平面；维空间中的一个超平面；2.分类界面将分类界面将d维空间分成两部分，维空间分成两部分，R1，R2分分别属于两个类别；别属于两个类别；3.判别函数的权矢量判别函数的权矢量w是一个垂直于分类界面是一个垂直于分类界面H的矢量，其方向指向区域的矢量，其方向指向区域R1 ；4.偏置偏置w0与原点到分类界面与原点到分类界面H的距离有关：的距离有关：00wr w模式识别 绪论多类问题（情况一）多类问题（情况一）p每一类模式可以用一个超平面与其它类别分开；每一类模式可以用一个超平面与其它类别分开；p这种情况可以把这种情况可以把c个类别的多类问题分解为个类别的多类问题分解为c个两个

59、两类问题解决，需要类问题解决，需要c个线性分类界面；个线性分类界面；p第第i类与其它类别之间的判别函数：类与其它类别之间的判别函数： tiigya y模式识别 绪论多类问题（情况一）分类界面多类问题（情况一）分类界面模式识别 绪论多类问题（情况一）判别规则多类问题（情况一）判别规则p若存在若存在i，使得，使得gi(x)0， gj(x)0，ji，则，则判别判别x属于属于i i类类；p其它情况，拒识。其它情况，拒识。模式识别 绪论多类问题（情况二）多类问题（情况二）p每两个类别之间可以用一个超平面分开；每两个类别之间可以用一个超平面分开；pc个类别的问题需要个类别的问题需要c(c-1)/2个线性分

60、类界面；个线性分类界面；p第第i类与第类与第j类之间的判别函数为：类之间的判别函数为： ,tijijgya yij模式识别 绪论多类问题（情况二）分类界面多类问题（情况二）分类界面模式识别 绪论多类问题（情况二）判别准则多类问题（情况二）判别准则p如果对任意如果对任意ji ，有，有gij(x)0 ，则决策，则决策x属于属于i。 p其它情况，则拒识。其它情况，则拒识。模式识别 绪论多类问题（情况三）多类问题（情况三）p情况三是情况二的特例，不存在拒识区域。情况三是情况二的特例，不存在拒识区域。 模式识别 绪论多类问题（情况三）判别函数多类问题（情况三）判别函数pc个类别需要个类别需要c个线性函数