2.1.2 模式分类

模式分类是模式识别的核心，现已提出了多种模式分类器的设计方法，总体上可以分为基于贝叶斯决策的分类器设计方法、线性分类器设计方法和非线性分类的设计方法。其中贝叶斯分类器是其他方法的基础。本节将简要介绍贝叶斯决策中的最小错误率的贝叶斯决策方法、线性分类中的感知器分类器和非线性分类器中的近邻法（即常用的模板匹配法）。

模式分类是模式识别的主要内容。基于已知类别的若干个样本的特征，对待测模式进行分类判别是最常用的模式识别的决策方法。这种方法要建立已知类别的样本库，根据这些样本库建立分类判别函数，这一过程称为学习或训练过程，然后对未知类别的新的模式分析它的特征，决定它属于哪一类。这是一种监督分类的方法。

1.最小错误率的贝叶斯决策

贝叶斯分类器在统计模式识别中被称为最优分类器。采用贝叶斯分类器必须满足下列两个先决条件：

·要决策的类别数是一定的。假设要研究的分类问题有c个模式类。

·各类别总体的概率分布是已知的。假设待识别客体的特征向量值 x 所对应的状态后验概率P(ωi|x)是已知的；或者，对应于各个类别出现的先验概率和类条件概率密度函数是已知的。

对于两类分类问题，最小错误率贝叶斯分类的指导思想是：对于模式x，如果它属于模式类ω1的概率大于属于模式类ω2的概率，则决策模式x属于模式类ω1；反之，决策模式x属于模式类ω2。用数学语言描述为

式中，条件概率P(ωi|x)称为状态的后验概率。

由贝叶斯公式得

同时考虑到P(x)>0，则上面的决策规则可改写为

式中，p(x|ω1)、p(x|ω2)分别是ω1类和ω2类下模式x的类条件概率密度。

这样，最小错误率贝叶斯分类有两种形式，一种是后验概率形式：

另一种是类条件概率密度形式：

将两种情况推广到c类情况，最小错误率贝叶斯分类规则如下：

·后验概率形式：

·类条件概率密度形式：

应用贝叶斯决策规则对模式x进行分类的分类器称为贝叶斯分类器。

对于c类分类问题，按照决策规则可以把特征向量空间（或称模式空间）分成c个决策域，各决策域的边界称为决策边界。

贝叶斯决策规则可通过判别函数来表达。对于c类分类问题，定义c个判别函数di(x)(i=1,2,⋅⋅⋅,c)。对照两种形式下的最小错误率贝叶斯决策规则，判别函数可定义为

di(x)=P(ωi|x) (i=1,2,⋅⋅⋅,c)

及

di (x)= p(x|ωi)P(ωi) (i=1,2,⋅⋅⋅,c)

这样，决策规则可写为

决策边界由判别函数确定，相邻的两个决策域在决策边界上其判别函数值是相等的。如果决策域Ri与R j是相邻的，则分割这两个决策域的决策边界方程应满足

一般来说，当模式x为一维时，决策边界为一个分界点；当x为二维时，决策边界为一条曲线；当x为n维(n>3)时，决策边界为一个超曲面。

2.感知器分类器

使用贝叶斯分类器，必须已知样本的分布，但这一点难以做到。为此必须利用样本集估计各模式类的类条件概率密度，进而由此设计贝叶斯判别函数，因此，设计出的判别函数可能是线性函数，也可能是各种各样的非线性函数。

线性分类器指的是判别函数为线性的分类器，其形式简单，可以根据实际问题，利用已有样本集，选择合适的算法估计判别函数中的未知参数。感知器是线性分类器中最经典的方法，本节将在简单介绍线性判别函数的基础上，介绍感知器算法。

（1）线性判别函数的基本概念

对于一本样本集，若存在一个线性分类器能把每个样本都正确分类，则称这组样本集为线性可分的；否则称为线性不可分的。反过来，若样本集是线性可分的，则必然存在一个分类器能把每个样本正确分类。

假设模式向量x是n维的，线性判别函数的一般形式为

式中，w0 =(w称为增广模式向量。1,w2,…,w n)称为权向量；w n+1称为阈值；w称为增广权向量；X =(x1,x2,…,xn,1)

在两种情况下，可以仅定义一个判别函数：

决策规则为

决策边界方程为d(x)=0。当d(x)为线性函数时，这个决策边界便是超平面，超平面的方向和位置分别由w0和wn+1确定。这个超平面将模式空间分割成两个决策域。

在多类情况下，例如c类，通常有两种方案实现分类：一对一和一对多。实际上，这两种方案也适用于非线性分类情况。

在一对一中，要设计c(c-1)/2个分类函数，每个分类函数对两类进行决策，最后通过投票的方式决定分类结果。

在一对多中，只要设计c个分类器，第i个分类器就会将第i类与其他c-1类分开。

（2）感知器准则函数

对一两类线性可分问题，训练样本集S={X1,X 2,…,X N}。现欲通过感知器准则函数求出判别函数d(x)=wT X 中的权向量w。为便于推导，先对样本进行规范化处理：

式中，X(i)称为规范化样本。规范化后，当Xi∈ω1时，若w将Xi正确分类，则wTX (i)>0；若w将Xi错误分类，则wTX (i)<0。当Xi∈ω2时，若w将Xi正解分类，则wTXi<0,wTX (i)>0；若w将Xi错误分类，则wTXi>0，wTX (i)<0。

这样，不管Xi属于哪一类，若正确分类，则wTX(i) >0；若错误分类，则wTX(i) <0。感知器准则函数定义为

式中，Se是被w错误分类的样本集合。对错误分类样本X i，有wT i)( <0，即-wT X(i)>0。因此，上式中的 J(w)总是大于0，而且仅当不存在错分样本，即 Se为空集时，J(w)才为0。这时准则函数达到极小值，对应的w就是我们要寻找的权向量w*。

下面采用梯度下降法求解使J(w)达到极小值时的权向量w*。

对J(w)关于w求梯度：

为使J(w)尽快减小，w的变化方向必须与∇J(w)的方向一致。由此建立w的迭代公式：

式中，c(k)为步长。从任意给定初始权向量w(1)出发，反复使用上式，就可得到序列

对于感知器准则函数而言，梯度下降法的迭代公式为

感知器准则函数梯度下降法可归纳成如下步骤：

（a）给定初始权向量w(1)和步长c(k)。

（b）找出被权向量w(k)错分类的样本，执行第（c）步；如果无错分类样本，算法结束。

（c）按式（2-61）的迭代公式求新的权向量w(k+1)，然后转到第（b）步。

可以证明，采用梯度下降法对于线性可分的样本集，经过有限步修正，一定能找到一个使准则函数达到极小值的权向量 w*，即算法在有限步内收敛。其收敛速度取决于初始权向量 w(1)和步长c(k)。

获得权值向量后，就可对待识模式 Xi进行分类，计算di =wTX(i)的值。若 di>0，则将 Xi分到w1类中；若di<0，则将Xi分到w2类中。

感知器分类算法只适用于线性可分的情况，对于线性不可分的情形，其不会收敛。上面给出的算法在迭代的每一步中将样本集中全体错分样本一次性找出，并予以修正。实际上，改进的算法可以处理线性不可分和一次输入一个样本的情况。

3.近邻分类器

如果样本集线性可分，使用线性分类器就能够很好地完成分类任务。但是，如果样本集线性不可分，使用线性分类器的分类，误差往往偏大。因此，对于线性不可分的样本集应该采用非线性分类器。

近邻法是一种典型的非线性分类器，也是一种非参数模式识别方法，与感知器算法一样，也不需要事先给出先验概率和类条件概率密度函数等知识，而是直接对样本进行操作。近邻法将全部样本作为标准样本，根据所使用在待识样本周围的近邻样本个数，又分为最近邻法和K-近邻法。

（1）最近邻法

最近邻法的基本思想很简单：如果待识样本X与样本X k之间的距离最小，而X k∈ωi，则决策X属于ωi类。

也可以用判别函数来说明最近邻法。设有 c 类模式样本ω1，ω2，…，ωc，每类有样本ni个，i=1,2,…,c，则最近邻法的判别函数为

于是决策法则就是：若有di (X ) < dj (X), i ≠ j，则把X分到第i类中。

最近邻法在应用中又称模板匹配法。在模板匹配法中，已知的样本称模板，将待识模式与模板逐一进行比对，最相近的模板所属的类别就是待识模式的类别。在实际应用中，模板匹配法，通常并不采用最近邻法中使用的距离度量进行相似性比对，而是采用角度相似性函数进行相似性比对，当待识模式与模板的相似性函数值小于指定的阈值时，判定待识模式属于相应模板所属的类别。

（2）K-近邻法

对最近邻法的一个明显的改进是K-近邻法。这个法则就是在X的K个近邻中，按出现最多的样本类别来作为X的类别。换句话说，就是先对X的K个近邻一一找出他们的类别，然后对X的类别作出一次表决。

设有一组样本，共N个：S={X1,X 2,…,X N}，首先在这N个样本中找出X的K个近邻。若k1,k2,…,kc分别是K个近邻中属于ω1,ω2,…,ωc类中的样本数，则可以定义判别函数为

决策规则为：若，则决策x∈ωj。

近邻法是一种次优方法，其优点是算法简单，且错误率能得到保证，因而得到较为广泛的应用。其不足是存储量和计算量都较大。