统计模式识别简介

1、统计模式识别简介,0937009 0937028 0937036 0937041,关于统计学的一个笑话：,有一个从没带过小孩的统计学家，因为妻子出门勉强答应照看三个年幼好动的孩子。妻子回家时，他交出一张纸条，写的是： “擦眼泪11次；系鞋带15次；给每个孩子吹玩具气球各5次,累计15次；每个气球的平均寿命10秒钟；警告孩子不要横穿马路26次；孩子坚持要穿马路26次；我还要再过这样的星期六0次”。 统计学真的这样呆板吗？仅仅收集数据，整理分析，累加平均,统计理论要解决的是从数据中做出一些 推断、它为解决随机观测事件的决策过程 提供了理论基础。 PR中的分类问题是根据识别对象特征的观测值，将其分到

2、相应的类别中去。 而统计决策理论是模式分类的主要理论和工具之一。 下面我们介绍统计模式识别，以及几种最常用、也是最基本的统计决策方法。,统计模式识别,统计模式识别方法就是用给定的有限数量样本集，在已知研究对象统计模型或已知判别函数类条件下根据一定的准则通过学习算法把d 维特征空间划分为c个区域,每一个区域与每一类别相对应。,属于同一类别的各个模式之间的差异，部分是由环境噪声和传感器的性质所引起的，部分是模式本身所具有的随机性质。前者如纸的质量、墨水、污点对书写字符的影响；后者表现为同一个人书写同一字符时，虽形状相似，但不可能完全一样。因此当用特征向量来表示这些在形状上稍有差异的字符时，同这些特

3、征向量对应的特征空间中的点便不同一，而是分布在特征空间的某个区域中。这个区域就可以用来表示该随机向量实现的集合。,假使在特征空间中规定某种距离度量，从直观上看，两点之间的距离越小，它们所对应的模式就越相似。在理想的情况下，不同类的两个模式之间的距离要大于同一类的两个模式之间的距离，同一类的两点间连接线上各点所对应的模式应属于同一类。一个畸变不大的模式所对应的点应紧邻没有畸变时该模式所对应的点。在这些条件下，可以准确地把特征空间划分为同各个类别相对应的区域。在不满足上述条件时，可以对每个特征向量估计其属于某一类的概率，而把有最大概率值的那一类作为该点所属的类别。,模式识别系统在进行工作时只要判断

4、被识别的对象落入哪一个区域，就能确定出它所属的类别。由噪声和传感器所引起的变异性，可通过预处理而部分消除；而模式本身固有的变异性则可通过特征抽取和特征选择得到控制，尽可能地使模式在该特征空间中的分布满足上述理想条件。因此一个统计模式识别系统应包含预处理、特征抽取、分类器等部分（见图）。,统计模式识别模型,该模型主要包括两种操作模型:训练和分类 ,其中训练主要利用已有样本完成对决策边界的划分 ,并采取了一定的学习机制以保证基于样本的划分是最优的;而分类主要对输入的模式利用其特征和训练得来的决策函数而把模式划分到相应模式类中。,基本原理,统计模式识别(statistic pattern recog

5、nition)的基本原理是：有相似性的样本在模式空间中互相接近，并形成“集团”，即“物以类聚”。其分析方法是根据模式所测得的特征向量Xi=(xi1,xi2,xid)T(i=1,2,N)，将一个给定的模式归入C个类1,2, c中，然后根据模式之间的距离函数来判别分类。其中，T表示转置；N为样本点数；d为样本特征数。,统计模式识别的方法有： 贝叶斯决策方法 （1）最小错误概率贝叶斯判别准则 （2）最小风险贝叶斯判别 （3）聂曼皮尔逊判别准则准则 判别函数法 （1）线性可分的几何分类法 （2）非线性可分的几何分类法,监督参数统计法 （1）KNN法（K最近邻法） （2）Fisher判别分析法 非监督参

6、数统计法 （1）基于概率密度函数估计的直接方法 （2）与样本空间相似性度量的间接聚类方法 聚类分析法 近邻函数法 （1）基于最邻近规范的试探法 （2）最大最小距离法,主要方法,贝叶斯决策法 线性判别函数 邻近法分类（KNN) 最小距离分类 聚类分析法,贝叶斯决策方法,运用统计决策理论设计的分类系统又称为分类器。 贝叶斯决策是一种统计模式识别决策法，它有如下基本假定： 1.各类别总体的概率分布是已知的 2.被决策的分类数是一定的 3.被识别的事物或对象有多个特征观测值,当被识对象用n随机向量X表示，二我们已知分类的先验概率的条件概率密度函数，便可根据贝叶斯公式，求解后验概率，并按后验概率的大小来

7、判别分类，这就是贝叶斯决策方法。下面介绍三种判别准则： （1）最小错误概率贝叶斯判别准则 （2）最小风险贝叶斯判别 （3）聂曼皮尔逊判别准则准则,（1）最小错误概率贝叶斯判别准则,设有R类样本，分别为w1,w2,wR, 已知每类的先验概率为P(wi), 其中i=1,2, ,R。对于待识别的随机向量X,已知每类的条件概率密度为P(X|wi),则根据贝叶斯公式有后验概率： P(wi|X)=(P(X| wi)*P(wi)/(P(Xwi)*P(wi) （1） 根据计算得出得后验概率，取最大得后验概率P(wi|X)所属的wi类，判决X属于wi类。表示为： P(wi|X)P(wj|X)则X属于wi 其中i

8、,j=1,2, ,R,且存在ji，这就是贝叶斯判别准则。 若按统计理论定义“似然比”为： l(X) = P(X| wi)/ P(x| wi) 取判别阀值： ji= P(wj)/ P(wi) 则有贝叶斯判别准则的似然比表示形式： l(X) P(wj)/ P(wi) 则X属于wi 对于两类模式集（w1,w2）的分类，贝叶斯判别准则简单表示为： 若 P(w1|X)P(w2|X)则X属于w1 若 P(w2|X)P(w1|X)则X属于w2 贝叶斯判别准则实质上是最小错误概率的贝叶斯判别准则。,最小风险贝叶斯判别准则,在实际工作中，有时仅考虑错误率最小是不够的。要引入比错误率更广泛的概念风险、损失。 如果

9、在采取每一决策时，其条件风险都最小，则对所有的x作决策时，其平均（期望风险）也最小。称为最小风险的贝叶斯决策。,在决策理论中，称所采取的决定为决策或行动。每个决策或行动都会带来一定的损失。该损失用表示，它是与本该属于wi但采取的决策为j所造成的损失有关。由此定义损失函数为（j| wi）=ij(i,j=1,2, ,R)。对样本X属于wi,有贝叶斯公式已知后验概率为P(wi|X),几何分类法（判别函数法）,一个模式经某种数学变换后，映射为一特征向量，并表示为特征空间的一个点。同一类的点构成点集，表示一类i。不同类的点集（i ,i=1,2, ,n）总是互相有不同程度的分离。若能几何的方法，找出一种不

10、依赖于条件概率密度的分离函数，把特征空间划分为对应于不同类别的子空间，便可实现模式分类。因此，把这种分类方法称为几何分类法，把这种分离函数成为判别函数。从而，几何分类法也通常称为判别函数法。,判别函数可以是线性的或非线性的。利用已知类别的训练集，通过统计方法，可以求的判别函数的具体形式和参数，然后用来判别未知样本属何类别。这种方法虽属统计分类方法，但无需依赖于条件分布密度的知识，因此在一些场合下，比基于贝叶斯公式的概率分类法简单。,线性判别函数,基于线性判别函数的模式分类器称为线性分类器。设计线性分类器的主要步骤是：首先已知一组有类别的样本训练集。第二，选择一个准则函数，该函数既与样本集X与W

11、有函数关系，又能反映分类器性能。第三，用最优化技术求出准则函数的极值解W，从而得到线性判别函数优化解。,监督参数统计法,KNN法（ K最近邻法） Fisher判别分析法,K最近邻法,KNN法，也称K最近邻法，是模式识别的标准算法之一。 其基本原理是先将已经分好类别的训练样本点“记入”多维空间中，然后将待分类的未知样本也记入空间。考察未知样本的K个近邻，若近邻中某一类样本最多，则可以将未知样本也判为该类。在多维空间中，各点间的距离通常规定为欧几里得空间距离。KNN法的好处是它对数据结构没有特定的要求，只要用每个未知点的近邻属性类来判别就行了；KNN法也不需要训练过程。KNN法的一个缺点就是它没有

12、对训练点作信息压缩，因此每判断一个新的未知点都要将所有对已知点的距离全部算一遍，计算工作量较大。一种简化的算法称为类重心法，即将训练中每类样本点的重心求出，然后判别未知样本点与各类的重心的距离；未知样本与哪一类重心距离最近，,非监督参数统计法,基于概率密度函数估计的直接方法 于样本空间相似性度量的间接聚类方法,聚类分析法,在没有训练集的情况下，对一批没有类别的被识别样本进行自动分类，要按照样本之间的相似程度分类，即俗语讲的“物以类聚，人以群分”，这种分类方法称为聚类分析，它是一种无教师的非监督的分类方法。 若有未知类别的n个样本，要把它们分到C类中，可以有不同的聚类方法，如何评价聚类的好坏，需

13、要决定一个聚类准则。聚类准则的确定有两种方法，一是凭经验，根据分类问题，选择一种准则（例如以距离函数作相似性度量），用不断修改阀值，来达到某种最佳分类。另一种方法是确定一种函数，当该函数取最小值时，仍未达到最佳分类。,近邻函数法,基于最邻近规范的试探法 最大最小距离法,基于最邻近规范的试探法,设有n个样本：X1,X2, ，Xn。取任一样本（例如取X1）为聚类中心Z1，则有X1=Z1。选取一非负的阀值T1。然后计算X2到Z1的距离D21,距离函数可以选择上述任一种，通常选用欧氏距离。计算距离结果，如果D21T1，则建立一个新的聚类中心Z2，且X2=Z2。 下一步，取第三个样本X3，分别按距离函数

14、计算X3到Z1、Z2的距离D31、D32。若D31T1且D32T1，则X3与X1、X2都不同类。并需建立第三个聚类中心Z3=X3。 用上述方法对全部样本计算距离，比较阀值，决定聚类。这种方法计算简单。当具有一些模式分布先验知识，以指导阀值选取及初始点选择，便可较快获得结果。,最大最小距离法,这种方法以欧氏距离为度量，先选择相距最远的两点为中心，分别计算各种本到这两中心的距离Di1和Di2,i=1,2, ，n。对每个i点取两个距离Di1和Di2中的最小：min（Di1，Di2），检测全部min（Di1，Di2）中的最大者是否大于|Z1-Z2|/2来判决聚类。故称最大最小距离法。以下图十点为例，具

15、体步骤如下： 第一步：任意取X1为第一个聚类中心，即X1Z1。 第二步：确定离X1最远的标本，令X6Z2。 第三步：逐个计算各样本X1,X2, ,Xn与Z1及Z2的距离Di1，Di2。 Di1X iZ1，Di2X iZ2 若存在max min（Di1，Di2）,i=1,2, ，nZ 1Z2/2,则令X iZ3（X 7Z3），转下一步。否则，转最后一步。 第四步：计算Di1，Di2，Di3若存在max min（Di1，Di2，Di3）,i=1,2, ，nZ 1Z2/2，则令XiZ4，转下一步。否则，转最后一步。 最后一步：将全部样本按最小距离分别到最近的聚类中心。本例为三个中心，得分类结果： X

16、1X3X4为第一类，Z 1X 1 X2X6为第二类，Z 2X 6 X5X7X8X9X10为第三类，Z 3X 7,统计模式识别的研究进展,类条件概率分布的估计线性判别法贝叶斯分类器误差界,类条件概率分布的估计,考虑将待识样本XRd判别为C个不同类1,2, c中的某一类。由贝叶斯定理，X应判为具最大后验概率的那一类。由于类条件概率分布未知，故通常假定分布为某一带参数的模型如多维正态分布(当多维正态分布中均值向量和协方差矩阵已知时，由此分布得到的二次判别函数是最优的），而表示分布的参数则由训练样本进行估计。当训练样本不充足时，分布参数包含估计误差影响识别精度。为了提高分类精度，Ujiie H等人提出

17、了这样一个方法。首先，将给定数据进行变换(带指数函数的变换），使得变换后的数据更近似于正态分布，不论原数据所服从的分布如何，而且在理论上找到了最优变换；然后，为了处理这些变换后的数据，对传统的二次判别函数进行了修改；最后，提出了变换的一些性质并通过实验表明了该方法的有效性。为了避免分类精度的降低，通过研究特征值的估计误差，提出了各种方法，但对特征向量的估计误差却考虑得不多。Iwamura M等人经过研究得出特征向量的估计误差是造成分类精度降低的另一个因素，因而提出了通过修改特征值以弥补特征向量的估计误差的方法。,线性判别法,20世纪90年代中期，统计学习理论和支撑向量机算法的成功引起了广大研究

18、人员的重视。支撑向量机算法具有较扎实的理论基础和良好的推广能力，并在手写数字识别、文本分类等领域取得了良好的效果，它的一个引人注目的特点是利用满足Mercer条件的核函数实现非线性分类器的设计，而不需要知道非线性变换的具体形式10。Fisher判别法和主分量分析法是在模式分类与特征抽取中已经获得广泛应用的传统线性方法。近年出现的基于核函数的Fisher判别法1112与基于核函数的主分量分析法13是它们的线性推广，其性能更好，适用范围更广，灵活性更高，是值得关注的应用前景看好的新方法。在考虑两类问题且每类中的训练样本数大于样本的维数的情况下，参考文献14提出了基于训练样本来划分一个多维空间的两种

19、方法，它们是Fisher线性判别法的两点改进。第一种方法一维参数搜索；第二种方法递归Fisher方法。这两种方法对模式检测问题比起标准的Fisher判别法来训练效果更好。利用Mercer核，可以将这两个方法推广到非线性决策面。,贝叶斯分类器,模式识别的目的就是要将一个物体(由它的特征表示）判别为它所属的某一类。考虑两类的情况。采用贝叶斯分类器时，物体是按最大后验概率进行分类的，这由一个判别函数来完成。多数情况下，该判别函数是线性的或二次的。当类服从正态分布时，要找到最优线性分类器总是不可能的。就目前所知，都是协方差矩阵相等的情况。 与最优线性分类器相对，研究人员尝试各种方法来得到线性分类器，尽

20、管这些方法找到了线性判别函数，但分类器却不是最优的。存在正态分布和不等协方差矩阵的其它情况判别函数是线性的且分类器是最优的。与前面研究的线性分类器相比，这里介绍的新方法得到两个正态分布类间的最优分类器是对偶的和线性的。文中确定了均值向量和协方差矩阵必须满足的条件以得到最优对偶线性分类器，解决了感知器的Minsky悖论。 一种改进的Nave贝叶斯分类器(INBC）技术且探索了在分类问题中选择输入特征子集时遗传算法的应用。NBC是在观察独立的假定下贝叶斯规则的简化形式。 具最优决策的贝叶斯分类器可以由概率神经网络来实现。,可以用非线性动态系统(Nonlinear Dynamical System，

21、简记为NDS)的集合来对模式进行分类，其中每个NDS将输入值分类为IN或OUT类型。输入值通过每一个NDS进行迭代并沿着一个轨道收敛到一个全局稳定吸引子(attractor)，它是该NDS所代表的类的原型。先前提出了一种“Race to The Attractor”神经网络(RTANN）模型方法，与传统的神经网络方法相比，这一方法受益于与人的大脑联系更广的几个有利条件。然而，该方法缺乏详细的数学分析。研究了RTANN方法的数学结构，确定了该方法得到最优贝叶斯分类的条件。要从杂乱的背景图像中检测出诸如人、脸和汽车等是一个广泛应用的方法。许多应用系统需要准确而快速的检测。换句话说，降低检测错误和减少计算复杂性是两个主要的问题。很多目标检测的工作集中在性能改善上，而对复杂性问题注意很少。这两个问题同时进行了研究。通过在贝叶斯决策规则下的误差分析，减少检测时系数的数量来降低计算开销。作者采用隐式Markov树(HMT）模型来描述模式分布，引入概念errorboundtree(EBT)建立特征选择与误差降低的联系。,误差界,最小分类错误(MCE）训练准则，与其它判别训练准则如极大交互信息(MMI）准