2.2 统计模式识别
2.2.1 统计模式识别原理与工作流程
1.统计模式识别原理
统计模式识别是最先提出的一种模式识别方法，是受数学中决策理论的启发而产生的。它一般假定被识别的对象或经过提取的特征向量是符合一定分布规律的随机变量。首先通过测量与计算，提取待识别模式的一组统计特征，并将其表示为一个量化的特征向量；再将特征提取阶段得到的特征向量定义在一个特征空间中，这个空间包含了所有的特征向量，不同的特征向量或者说不同类别的对象都对应于空间中的一点；在分类阶段，则利用统计决策的原理，按某种决策函数设计的分类器，对特征空间进行划分，从而达到识别不同特征的对象的目的。若将具有m个特征参量的m维特征空间进行划分，使之形成不同区域，则每一区域均对应一类模式，根据参量所分配的具体区域可对事物的模式予以确定。分类方法有定界分类和不定界分类两种。定界分类是指在分类之前已知界限定义和各类别的样本，只需设计鉴别函数并用判决函数对模式特征进行判决，将其划入到所属类别中去；不定界分类是事前不知道有哪些类别，根据物以类聚的原则进行划分，如聚类分类法。
在统计模式识别中，贝叶斯决策系统从理论上解决了最优分类器的设计问题，但其实施却必须首先解决更困难的概率密度估计问题。反向传播（BP）神经网络直接从观测数据（训练样本）学习，是更简便、有效的方法，因而获得了广泛的应用，但它是一种启发式技术，缺乏指导工程实践的坚实理论基础。统计推断理论研究所取得的突破性成果导致现代统计学习理论——VC（Vapnik Chervonenkis）理论的建立；该理论不仅在严格的数学基础上圆满地回答了ANN中出现的理论问题，且导出了支持向量机（support vector machine，SVM）学习方法。
2.统计模式识别工作流程
一个完整的统计模式识别系统由数据获取，数据处理，特征提取和选择，分类决策四部分组成，如图2.2所示。
图2.2 统计模式识别系统构成
（1）数据获取
数据获取就是对待识别对象的能够观测的一些特征数据进行统计，是指利用各种传感器把被研究对象的各种信息转换为计算机可以接收的数字或符号（串）集合。习惯上，称这种数字或符号（串）所组成的空间为模式空间，这一步的关键是传感器的选取。为了从这些数字或符号（串）中抽取出对识别有效的信息，必须进行数据处理，包括数字滤波和特征提取。
（2）数据处理
预处理是指消除输入数据或信息中的噪声，排除不相干的信号，只留下与被研究对象的性质和采用的识别方法密切相关的特征（如表征物体的形状、周长、面积等）。例如，在进行指纹识别时，指纹扫描设备每次输出的指纹图像会随着图像对比度、亮度或背景等不同而不同，有时可能还会产生变形，而人们感兴趣的仅仅是图像中的指纹线、指纹分叉点、端点等，不需要指纹的其他部分或背景。因此，需要采用合适的滤波算法，如基于块方图的方向滤波、二值滤波等，过滤掉指纹图像中不必要的部分。
（3）特征提取和选择
常见的特征有几何大小、灰度统计特征、边缘形状特征、纹理特征、视觉感知特征、灰度梯度特征、分形特征、颜色、对象特征、方向、梯度、密度、特征点、变换域纹理、局部特征等。对数据进行一定的预先处理后，当待识别对象原始特征的数量在预处理后有很多，或者处于一个高维空间中时，为了更好地用计算机进行分类，往往对这些高维的数据进行降维处理。通过一定变换将多个特征用少数几个特征的线性组合来进行替换，从滤波数据中衍生出有用的信息，从许多特征中寻找出最有效的特征，从而起到一定的降维作用，这个过程就是特征提取。
特征选择通常是指从待识别对象的众多特征中选择若干个能够有效反映该类对象的特征组，用来表示该类所具有的模式特征向量；该过程去除掉一些无用或冗余的特征，如在曲线识别中对曲线特征的提取就要选择有代表性的点集。对滤波后的这些特征进行必要的计算后，通过特征选择和提取形成模式的特征空间。
特征选择和提取是模式识别的一个关键问题。一般情况下，候选特征种类越多，得到的结果越难以求解。因此，数据处理阶段的关键是滤波算法和特征提取方法的选取。不同的应用场合，采用的滤波算法和特征提取方法以及提取出来的特征也会不同。
（4）分类决策
基于数据处理生成的模式特征空间，用于进行模式识别的最后一步：模式分类或模型匹配。模式分类（即分类决策）就是运用分类器把待识别对象按照前面确定的类别特征进行分类识别的过程。该阶段最后输出的可能是对象所属的类型，也可能是模型数据库中与对象最相似的模式编号。模式分类或描述通常是基于已得到分类或描述的模式集合而进行的。人们称这个模式集合为训练集，由此产生的学习策略称为监督学习。在有监督模式识别过程中，选择好特征集和分类器之后，再用已知类别样本集对分类器进行训练，最后再用该分类器对未知类别样本进行识别。学习也可以是非监督性学习，在此意义下产生的系统不需要提供模式类的先验知识，而是基于模式的统计规律或模式的相似性学习来判断模式的类别。在非监督模式识别过程中，选择好特征向量后根据一定的聚类方法对待识别的样本进行分类识别，聚类的过程是一个自学习过程，不用进行样本集的训练。
2.2.2 模板匹配分类法
在模式识别中，最原始的分类方法是模板匹配分类法（template matching method）.在这种方法中，首先对每一个模式建立一个标准模板，再把待识别的样品与模板进行匹配比较，若样品上的大多数单元与作为标准的模板上的大多数单元均相匹配，则称二者匹配得好；反之，匹配得不好，取匹配最好的样品作为识别的结果。模板匹配分类法又分光学模板匹配、电子模板匹配等。
光学模板匹配法如图2.3所示，将待识别模式的正像（样品）依次与各模板（负模）相匹配，输出光通量转换为电流量作为匹配不一致性的度量。若输出电流为零，则匹配最好。实际应用中若检测到的电流小于某个预先设定的阈值，则表示待识别的样品为模板的识别类型，否则不被识别。
图2.3 光学模版匹配法
模板匹配原理是选择已知对象作为模板，与图像中选择的区域进行比较，从而识别目标。模板匹配依据模板选择的不同，可以分为两类：一是，以某一已知目标为模板，在一幅图像中进行模板匹配，找出与模板相近的区域，从而识别图像中的物体，如点、线、几何图形、文字以及其他物体；二是，以一幅图像为模板，与待处理的图像进行比较，识别物体的存在和运动情况。模板匹配的计算量很大，相应的数据的存储量也很大，且随着图像模板的增大，运算量和存储量以几何级数增长。若图像和模板大到一定程度，就会导致计算机无法处理，随之也就失去了图像识别的意义。模板匹配的另一个缺点是由于匹配的点很多，理论上最终可以达到最优解，但实际却很难做到。
2.2.3 最小距离分类法
最小距离分类法是指把模式经数学变换表示成n维特征空间向量X=（x1，x2，…，xn），每一个模式对应空间一个点。两个点的距离越小，则相应的两个模式越相似，于是距离最小的模式划为同一类，如图2.4所示。矩形块表示标准样本，圆圈表示待识样品，距离标准样本最近的样品为一类，较远的样品为另一类。
图2.4 最小距离分类法
最小距离分类法根据样本的分散性还可以细分为平均样本法、平均距离法、最近邻法等。在实际使用中，根据不同的应用目的可以采用不同的距离函数，如明氏（Minkowsk）、曼哈顿（Manhattan）、欧几里得（Euclid）、Camberra、切比雪夫（Chebyshev）、哈拉诺比斯（Mahalanobis）、Dice及Yule等距离函数。
最小距离分类法的优点是概念直观、方法简单，有利于建立多维空间分类方法的几何概念，也为其他分类提供了理论基础，适用于低维、小样本数、样本分布小的情况。
2.2.4 几何分类法
如前所述，每一个模式对应空间一个点。若空间不同类别的点很多，则可以用若干条直线或曲线将这些点按不同的类别区分，这就是几何分类法的基本思想。这些直线（或曲线）称为线性的（或非线性的）分类器，也称为几何分类器。通过几何分类方法，将特征空间分解为对应于不同类别的子空间。
二类问题是模式分类的基础，多类问题可以递归地用二类问题来解决。假设样本X是二维的，设计一个判决函数g（X）=a1x1+a2x2，其中x1，x2为坐标变量，a1，a2为系数。将某一不知类别的模式求得X，代入g（X），如为正值，则属于一类；如为负值，则属于另一类；如为零，则不可判别，如图2.5所示。
图2.5 二类模式的线性判别
几何分类法的缺点是只能处理确定可分问题，当样本空间相互重叠时，寻找判决函数非常困难，有时甚至是不可能的。
2.2.5 概率分类法
为了克服几何分类法的缺点，可以采用概率分类法。概率分类法在已知样本集ωi的先验概率P（ωi）和条件概率P（X|ωi）的条件下，通过计算模式，属于ωi类的后验条件概率来判断模式的类别。这是因为后验概率是一种客观概率；它表明随机实验中事件发生的相对频率，值越大，事件发生的相对频率越高，模式属于ωi类的可能性越大。
在概率分类法中，需要用到贝叶斯决策理论，通过贝叶斯公式计算后验概率，建立相应的判决函数和分类器来实现模式识别。
设有m个模式类，待识模式为X，根据贝叶斯公式，后验概率为
贝叶斯判决法则是：若存在i∈{1，2，…，m}，使得对所有的j（j=1，2，…，i-1，i+1，…，m）均有P（ωi |X）>P（ωj |X），则X∈ωi.
根据贝叶斯判决法则，可得到相应的判决函数Gi（X）>Gj（X）（i≠j）。判决函数把特征空间划分为m个决策区域，凡落入该区域的X都判决它属于ωi类。相应的分类器如图2.6所示。
2.2.6 聚类分类法
聚类分析法是一种不定界分类法，其前提条件是已知所属类别的样品，用判别函数比较未知样品和已知样品，从而进行分类。这是一种有教师分类法，已知样品起教师作用，作为训练集，对未知样品按训练集分类。若没有训练集，即没有教师，则按物以类聚，人以群分的原则，根据样品间的相似程度自动分类；这是一种无教师分类法。
图2.6 贝叶斯分类器
聚类是基于物以类聚的朴素思想，目的是使得同一类别个体之间的距离尽可能地小，而不同类别个体间的距离尽可能地大。聚类又被称为非监督分类。和分类学习相比，分类学习的例子或对象有一类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自动确定，即把所有一类样本作为未知样本进行聚类。随着科学技术的发展，对分类的要求越来越高，以致有时仅凭经验和专业知识难以确切分类，于是人们逐渐地把数学工具引用到分类学中，形成数值分类学；之后又将多元分析的技术引入到数值分类学，形成了聚类分析。因此，分类问题和聚类问题根本的不同点为：在分类问题中，知道训练样本例的分类属性值，而在聚类问题中，需要在训练样例中找到这个分类属性值。
聚类分析的算法主要有划分法（partitioning method）、层次法（hierarchical method）、基于密度的方法（density-based method）、基于网格的方法（grid-based method）以及基于模型的方法（model-based method）等。
1.划分法
划分法给定一个由N个元素组成或者记录的数据集，构造K个分组，每一个分组就代表一个聚类，K<N，且这K个分组满足下列条件：（1） 每一个分组至少包含一个数据记录；（2） 每一个数据记录属于且仅属于一个分组。对于给定的K，算法首先给出一种初始的分组方法，然后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好。这样，所谓好的标准就是同一分组中的记录越近越好，而不同分组中的记录越远越好。使用这个基本思想的算法有K-MEANS算法、K-MEDOIDS算法、基于随机搜索的聚类算法（clustering algorithm based on randomized search，CLARANS）算法等。
2.层次法
层次法对给定的数据集进行层次上的分解，直到某种条件满足为止；具体又可分为“自下而上”和“自上而下”两种方案。例如，在“自下而上”方案中，初始时每一个数据记录都组成一个单独的组；在接下来的迭代中，把相互邻近的组合并成一个组，直到所有的记录组成一个分组或某个条件满足为止。代表算法有利用层次方法的平衡迭代规约和聚类（balanced iterative reducing and clustering using hierarchies，BIRCH）算法、利用代表点聚类（clustering using representatives，CURE）算法、CHAMELEON算法等。
3.基于密度的方法
基于密度的方法与其他方法的一个根本区别是：它不是基于距离的，而是基于密度的。这样，就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。这个方法的指导思想是只要一个区域中点的密度大过某个阀值，就把它加到与之相近的聚类中去。代表算法有基于密度的有噪声应用的空间聚类（densitybased spatial clustering of applications with noise，DBSCAN）算法、排序点以识别集群结构（ordering points to identify the clustering structure，OPTICS）算法、基于密度的聚类（density-based clustering，DENCLUE）算法等。
4.基于网格的方法
基于网格的方法是首先将数据空间划分成为有限个单元的网格结构，所有的处理都是以单个单元为对象的。这样处理的一个突出优点就是处理速度很快，通常与目标数据库中记录的个数无关，只与把数据空间分为多少个单元有关。代表算法有统计信息网络（statistical information grid，STING）算法、聚类高维空间（clustering in QUEST，CLIQUE）算法、小波变换（WAVE-CLUSTER）算法等。
5.基于模型的方法
基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好满足这个模型的数据集。例如，此模型可以是数据点在空间中的密度分布函数。该方法的前提是目标数据集由一系列概率分布所决定的。
在采用聚类分类法时，首先需要确定聚类准则。确定聚类准则的方法有两类：一类是凭经验；另一类是使用准则函数。一种最简单而又广泛应用的准则函数是误差平方和准则：设有n个样本，分属于ω1，ω2，…，ωi类，设有ni个样品的ωi类，其均值为
则误差平方和为
式中，C为聚类数目。
由于聚类算法很多，这里只介绍最大最小距离法，其具体算法步骤如下：
（1）任选某样品为第一个聚类中心Z1，如x1=Z1；
（2）求出离x1距离最大的样品x2，作为第二个聚类中心Z2.
（3）求出所有n个样品与这两个聚类中心Z1和Z2的欧氏距离Di1和Di2，其中i=1，2，…，n.
（4）求第三个聚类中心Z3，若存在max{min（Di1，Di2），i=1，2，…，n}>
，则xi=Z3，转（5），否则转（6）.
（5）重复（3）和（4）的计算过程，计算n个样品与Z1，Z2，Z3的距离Di1，Di2，Di3，求第四个聚类中心Z4.
（6）将全部样品按最近距离分到最近的聚类中心。若第一类为{x1，x2，x3}，其聚类中心是Z1=x1；若第二类是{x2，x6}，其聚类中心是Z2=x6；若第三类为{x3，x7}，其聚类中心是Z3=x7.