几种统计模式识别方案的比较

1、摘 要：模式识别是对表征事物或现象的各种形式的（数值的，文字的和逻辑关系的）信息进行处理和分析，以达到对事物或现象进行描述、辨认、分类和解释的目的，是信息科学和人工智能的重要组成部分。而统计决策理论是处理模式分类问题的基本理论之一，它对模式分析和分类器的设计有着实际的指导意义。本文归纳总结了统计模式识别的不同方案的详细性能，比较了它们的原理、算法、属性、应用场合、错误率等。 关键词：统计模式识别 贝叶斯决策方法 几何分类法 监督参数统计法 非监督参数统计法 聚类分析法 Comparison of Several Kinds of Statistical Pattern Recognition

2、Schemes Abstract: Pattern recognition deals with and analyses the information which signify all kinds of things and phenomena (number values, Characters and logic relation), in order to describe, recognize, classify and interpret them. It is one of the important parts of information science and arti

3、ficial intelligence. While statistical pattern recognition is one of the basics theory of classifying and is real directive significance in analyzing and classifying of pattern. We sum up the detailed performance of summarizing different schemes which counts the pattern recognition in this text, Com

4、pare their principle, algorithm, attribute, using occasion, etc. 1引 言 模式识别诞生于20世纪20年代，随着40年代计算机的出现，50年代人工智能的兴起，模式识别在60年代初迅速发展成为一门学科。它所研究的理论和方法在很多科学和技术领域中得到了广泛的重视，推动了人工智能系统的发展，扩大了计算机应用的可能性。 模式识别方法大致可以分为四类，即统计决策法、句法结构法、模糊判决法和人工智能法。 其中，统计决策论发展较早，理论也较成熟。其要点是提取待识别模式的一组统计特征，然后按照一定准则所确定的决策函数进行分类判决。统计模式识别方法

5、是建立在概率论与数理统计的基础上，它用特征向量来描述模式。不同的模式用不同条件概率分布表示，然后判别未知模式属于哪一种分布。分类方法主要有贝叶斯决策方法、线性可分的几何分类法、非线性可分的几何分类法、监督参数统计法、非监督参数统计法及聚类分析法。下文将对它们的性能进行详细地介绍。 2 几点统计识别方法介绍及比较 2.1 贝叶斯决策方法 运用统计决策理论设计的分类系统又称为分类器。贝叶斯决策是一种统计模式识别决策法，它有如下基本假定： 1.各类别总体的概率分布是已知的 2.被决策的分类数是一定的 3.被识别的事物或对象有多个特征观测值 当被识对象用n随机向量X表示，二我们已知分类的先验概率的条件

6、概率密度函数，便可根据贝叶斯公式，求解后验概率，并按后验概率的大小来判别分类，这就是贝叶斯决策方法。下面介绍三种判别准则。 （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,j=1,2, ,R,

7、且存在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 贝叶斯判别准则实质上是最小错误概率的贝叶斯判别准则。 （2）最小风险贝叶斯判别准则 在决策理论中，称所采取的决定为决策或行动。每个决策或行动都会带来一定的损失。该损失用表示，它是与本该属于

8、wi但采取的决策为j所造成的损失有关。由此定义损失函数为（j| wi）=ij(i,j=1,2, ,R)。对样本X属于wi,有贝叶斯公式已知后验概率为P(wi|X)，而采取决策j时，它的条件损失为： （2） i=1,2,R 在决策论中,把采取决策j的条件损失称为条件风险。对随机向量X取不同观察值时，同样采取j时，其条件风险是不同的。因此又是X的函数，写成(X)。由此，总的风险为： （3） 总的风险反应对整个特征空间上所有X采取决策(X)所带来的平均风险，而条件风险只反映对某一X值采取决策j所带来的风险。若每个条件风险都是最小，则总风险也最小。由此得到最小风险贝叶斯决策准则为： （4） 于是,k就

9、是最小风险贝叶斯决策。 对于两类模式集( )来说，由判别区域R1和R2。则总风险为 其中: 为 X ，且被分为 R1的“损失”； 为 X ，且被分为 R1的“损失”； 为 X ，且被分为 R2的“损失”； 为 X ，且被分为 R2的“损失”。 有全概率等于1可推出： 代入上式，经整理，得 若要总风险R最小，必须是积分号内有 便可判别 X 或 X 若用似然比表示 则有准则 （3）聂曼皮尔逊判别准则 由最小风险贝叶斯准则可见，设计该分类器时，必须预知先验概率P(i) ，并预先给定ij，特别是要有足够的经验，以给定ij，因为该准则和损失函数ij有很大关系，需要足够的先验知识。 聂曼皮尔逊(Neyma

10、n-Pearson)准则提供另一种方案，即设法限制某一错误概率，而同时使另一错误概率为最小。 取式1中 得到 当先验概率P（1）和P（2）已知时，1和2分别表示两类的错误率。在1 ，2两个错误率中取定一个（例如取定2）并使1为最小，这就使聂曼皮尔孙判别准则，也称为在限定一类错误率条件下是另一类错误率为最小的两类决策准则。在某些场合下，有它的实际意义。 2.2 几何分类法（判别函数法） 一个模式经某种数学变换后，映射为一特征向量，并表示为特征空间的一个点。同一类的点构成点集，表示一类i。不同类的点集（i ,i=1,2, ,n）总是互相有不同程度的分离。若能几何的方法，找出一种不依赖于条件概率密度

11、的分离函数，把特征空间划分为对应于不同类别的子空间，便可实现模式分类。因此，把这种分类方法称为几何分类法，把这种分离函数成为判别函数。从而，几何分类法也通常称为判别函数法。 判别函数可以是线性的或非线性的。利用已知类别的训练集，通过统计方法，可以求的判别函数的具体形式和参数，然后用来判别未知样本属何类别。这种方法虽属统计分类方法，但无需依赖于条件分布密度的知识，因此在一些场合下，比基于贝叶斯公式的概率分类法简单。 2.2.1 线性可分的几何分类法 与后面的聚类分类的不同这里是要算出确定的判别函数，而聚类是根据相似度先进行分类在修正对特征向量X在二维平面上，存在一直线方程形式的线性判别函数： 式

12、中x1、x2 分别为二维平面坐标变量，1、2 、3 为方程函数。则在二维坐标中构成两个模式集（1 ，2）。 将某一未知类别的样本X代入g（X），如为正值，则它属于1类；如为负值，则属于2 类。即 当X是三维的，判别函数为一平面方程。当n维（n3）时判别函数为一超平面，要进行模式分类，就要确定判别函数的形式及其参数。 基于线性判别函数的模式分类器称为线性分类器。设计线性分类器的主要步骤是：首先已知一组有类别的样本训练集。第二，选择一个准则函数，该函数既与样本集X与W有函数关系，又能反映分类器性能。第三，用最优化技术求出准则函数的极值解W，从而得到线性判别函数优化解。 线性分类器的准则函数及其最优

13、化解有多种成熟的技术。这里只介绍一种具有代表性的方法感知器方法。 模式识别是对人的思维的一种模拟。由苏联学者罗森布拉特提出的感知器的概念。感知器主要是一种人脑的模型，而不仅仅是模式识别装置。它实现了人工神经网络的工程模型。它用权函数连接网络的各个元素，构成一种非线性网络，对输入信号作出某种响应，并通过一定方式传达到其它元素，并能产生输出信号，这就使感知器的简单物理概念。若把感知器的R个输出元素，看作是R类模式，当某个被识样本由输入元素输入网络，使输出元素中第i个元素输出最大，则可判定被识样本属第i个模式。这样就把感知器构造成一个线性分类器。 利用感知器原则，构造一个准则函数J： 式中A为常数，

14、常取A0.5。当g(X)=WTX0,J(W,X)=0。当g(X)=WTX0。因此，这个准则函数的极小值为0，即 minJ(W,X)=0 这时，准则函数J的最优化解为： 求最优解的常用算法是梯度下降法，即一出初值W(1)常数，通过下式迭代： （5） 式中，k迭代次数； C有助于收敛的校正系数。 把 其中符号函数： 代入式(5)，得 这就使感知器准则的梯度下降算法。当 ，表示分类正确，则W(k+1)=W(k),对此给与“赏”或“不罚”，权向量不变。当 ，表示分类错误，对此给与“罚”，使W(k)加一个正比于X(k)的分量。常称此为“赏罚”概念。 用全部模式训练一轮后，只要有一个样本判错，则需进行下一

15、轮迭代，求出新的 。 反复迭代，直到全部训练及获得正确分类，迭代才结束。这时的 就是所求的 ，从而求得线性判别函数。 2.2.2 非线性可分的几何分类法 非线性分类理论为划分样本空间提供了最通用的方法，由于样本空间往往是非常复扎杂的，此非线性鉴别器函数，可以写成如下的通用形式： 1.分段线性判别函数 把每一类分为若干个子类，即令 ;我们不是选择各个子类的均值为代表点设 计最小距离分类器，而是对于每个子类定义一个线性判别函数 式中 和 分别为对子类 的权向量和阀值权。如果我们定义 类的线性判别函数为 对于c 类问题，可以定义c个判别函数 并得到决策规则:若 则决策 从直观上看，对于任意样本向量x

16、,必有某个子类的判别函数值较其他各子类的判别函数值为最大。假如具有最大值的判别函数是 ，则把 归到子类 所属的类，即 类。这样得到的决策面也是分段线性的，其决策面方程是由各子类的判别函数确定的。如果第I类的第n个子类和第I类的第m个子类相邻，则这段决策面的方程是 2. 二次判别函数 二次判别函数的一般表达式为 其中W是 实对称矩阵，w为d维向量。为确定判别函数 ，需要确定 个不同的系数。 2.3 监督参数统计法 2.3.1 KNN法及其衍生法 KNN法，也称K最近邻法，是模式识别的标准算法之一。其基本原理是先将已经分好类别的训练样本点“记入”多维空间中，然后将待分类的未知样本也记入空间。考察未

17、知样本的K个近邻，若近邻中某一类样本最多，则可以将未知样本也判为该类。在多维空间中，各点间的距离通常规定为欧几里得空间距离。KNN法的好处是它对数据结构没有特定的要求，只要用每个未知点的近邻属性类来判别就行了；KNN法也不需要训练过程。KNN法的一个缺点就是它没有对训练点作信息压缩，因此每判断一个新的未知点都要将所有对已知点的距离全部算一遍，计算工作量较大。一种简化的算法称为类重心法，即将训练中每类样本点的重心求出，然后判别未知样本点与各类的重心的距离；未知样本与哪一类重心距离最近，即将未知样本归于哪一类；这一类方法因过分简单而使结果的可靠性降低，但因计算简易，有时仍然可以应用。ALKNN法是

18、KNN法的一种改良，在KNN法中，对所有的类取相同的K值；而ALKNN法对K值的选取是根据每类样本的数目和分散程度进行的，对不同的类可以选取不同的K值；当各类的Ki值选定后，用一定的算法对类中样本的概率进行估计，并根据概率大小对他们进行类的划分。在ALKNN法中，以xi与类gi的Ki个近邻中最远的一个样本的距离r为半径，以x为中心，计算相应的超球的体积；并认为超球体积越小，类gi在xi处的概率密度越大，这一概率密度可由下式计算: P(x/gi) = (Ki 1)/nv(x/gi) 此处v(x/gi)为类gi的超球体积。对于未知样本，哪一类计算的P(x/gi)最大，即归入哪一类。此法的错误率为

19、P*= P= P*(2 c/(c-1)P*) 上式可以粗略表示为 P*= P= 2 P* P*为贝叶斯错误率 近邻法错误率在贝叶斯错误率P*和两倍贝叶斯错误率2 P*之间。这种近邻法的缺点就是：1.须将所有的样本存入计算机中，每次决策都要计算待识别样本x与全部训练样本之间的距离并进行比较；因此使存储量和计算量都比较大。2.虽然在所有情况下，对未知样本x都可以进行决策，但当错误代价很大时，会产生较大的风险。3.我们对近邻法的分析都是近似的，就是说要求样本数趋向于无穷大，这在任何场合都是无法实现的。 2.3.2 Fisher判别分析法 Fisher判别分析法的基本原理就是将多维空间样本点分布的图象

20、投影到二维或者一维，投影方向选择的原则是使两类样本点尽可能分开。求投影方向，得到两类点分开的最佳的方向和次佳方向，由这两个方向张成二维平面，可使投影形成二维分类图；垂直于分界线的法线代表使样本向一类或者二类转化的方向。Fisher方法在工业优化计算中常用，当工业生产实际作业区偏在优化区一侧时，生产上的“优类”工况和“劣类”工况就可以用Fisher方法分开；相反，如果优化区在生产实际作业区的中心区，用Fisher方法就不能将“优、劣”样本分开这时就得用其他的模式识别算法。 2.4 非监督参数统计法 1. 基于概率密度函数估计的直接方法 单峰子集（类）的分离方法：投影方法和基于对称集性质的单峰子集

21、分离法。 在没有任何类条件概率分布的先验知识情况下，我们只能把特征空间分为若干个区域 在每个区域的混合密度应该是单峰的。以后我们把这些区域叫做单峰区域。每一个单峰区域 和一个类别 相对应。 2.于样本空间相似性度量的间接聚类方法 动态聚类方法是一种普遍采用的方法，它具有3个要点： (1) 选定某种距离度量作为样本间的相似性度量。 (2) 确定某个评价聚类结果质量的准则函数。 （3）给定某个初始分类，然后用迭代算法找出使准则函数取极值的最好聚类结果。主要有以下方法：C-均值算法、基于样本和核的相似性度量的动态聚类算法、近邻函数准则算法和分级聚类方法。 2.5 聚类分析法 在没有训练集的情况下，对

22、一批没有类别的被识别样本进行自动分类，要按照样本之间的相似程度分与K最近邻法的区别，k邻近是已经分类好的类，即俗语讲的“物以类聚，人以群分”，这种分类方法称为聚类分析，它是一种无教师的非监督的分类方法。 （1）模式相似性与距离度量 模式相似性可以用相似性函数表示。常用的相似性函数有距离函数和夹角函数。 距离函数是用特征空间中，两特征点的距离作为相似性度量。对于特征空间中的点X和Y的距离，用d（X,Y）表示。它应满足下列条件： 根据不同应用，距离函数可采用不同定义，常用的距离函数有以下几种。 1）明氏（Minkowsky）距离 (6) 2）欧氏（Euclidean）距离 当明氏距离的2时， (7

23、) 3）曼氏（Manhattan）距离 当明氏距离的1时， (8) 4）类块（City block）距离 (9) 这是引入权值 i，对式（8）的修正。 距离函数还有很多其他的定义方法，在此不再一一列举。具体应用上述距离函数时，要注意特征分量（检测的物理量）的量纲。例如测量长度时，用密或毫米作量纲，其计算结果差异很大，因此常使特征数据归一化。 相似性的夹角函数使用特征向量X,Y的矢量夹角的余弦来表示，即 式中 两向量的夹角； |X| X的幅值。 则有 显然 12 ，即 ，故认为X与Z1更相似些也就是X与Z1同一类（i）。 （2）聚类分析的基本方法 若有未知类别的n个样本，要把它们分到C类中，可以

24、有不同的聚类方法，如何评价聚类的好坏，需要决定一个聚类准则。聚类准则的确定有两种方法，一是凭经验，根据分类问题，选择一种准则（例如以距离函数作相似性度量），用不断修改阀值，来达到某种最佳分类。另一种方法是确定一种函数，当该函数取最小值时，人未达到最佳分类。 下面介绍聚类分析中的近邻函数法。 近邻函数法 a基于最邻近规范的试探法 设有n个样本：X1,X2, ，Xn。取任一样本（例如取X1）为聚类中心Z1，则有X1=Z1。选取一非负的阀值T1。然后计算X2到Z1的距离D21,距离函数可以选择上述任一种，通常选用欧氏距离。计算距离结果，如果D21T1，则建立一个新的聚类中心Z2，且X2=Z2。 下一步，取第三个样本X3，分别按距离函数计算X3到Z1、Z2的距离D31、D32。若D31T1且D32T1，则X3与X1、X2都不同类。并需建立第三个聚类中心Z3=X3。 用上述方法对全部样本计算距离，比较阀值，决定聚类。这种方法计算简单。当具有一些模式分布先验知识，以指导阀值选取及初始点选择，便可较快获得结果。 b最大最小距离法 这种方法以欧氏距离为度量，先选择相距最远的两点为中心，分别计算各种本到这两中心的距离