模式识别概览

转载：https://blog.csdn.net/dznlong/article/details/5409784

模式识别技术漫谈（1）

                                                                                  ------引言

    在人工智能技术(Artificial Intelligence)领域中，模式识别(Pattern Recognition)技术也许是最具有挑战性的一门技术了，模式识别有时又被称为分类技术，因为模式识别说到底就是对数据进行分类。说到识别，最为常用的便是模仿人的视觉的图像识别（当然还有语音识别），也许你会想当然地认为那还不简单，觉得我们用我们的眼睛可以轻而易举地识别出各种事物，但是当你想用计算机中的程序来实现它时，于是你便会觉得很沮丧，甚至于有无从下手的感觉，至此你再也不会觉得电脑有多聪明，你会觉得电脑是多么的低能。是的，现在的电脑智能，即人工智能还远不如蟑螂的智能，这其中最为根本的原因是模式识别技术还是处于较为低层次的发展阶段，很多的识别技术还无法突破，甚至有人还断言，再过30年也不会有本质的飞跃。当然，世事总是让人难以预料，我们也用不着这么地悲观，科学技术总是向前发展的，没有人可以阻档得了的。在这里，我把我对模式识别技术的学习和研究心得拿出来与大家分享一下，我唯一的目的是想让模式识别技术走下技术的神坛，让每个人都能够去了解它，更是想让更多的人有兴趣去研究它，我的知识和能力有限，这样也许还能够帮助我改正我的错误认识。

    模式识别具有较长的历史，在20世纪60年代以前，模式识别主要是限于统计学领域中的理论研究，还无法有较强的数学理论支持，20世纪80年代神经网络等识别技术得到了突破，计算机硬件技术更是有了长足的发展，模式识别技术便得到了较为广泛的应用，光学字符识别(OCR)是模式识别技术最早得到成功应用的技术，之后的应用还有如DNA序列分析、化学气味识别、图像理解力、人脸检测、表情识别、手势识别、语音识别、图像信息检索、数据挖掘等。

    模式识别是一门与数学结合非常紧密的科学，所应用到的数学知识非常多，最基本的便是概率论和数理统计了，模式识别技术到处都充满了概率和统计的思想，我们经常所说的识别率，其实就是概率的表达：在大数据量（严格地说应当是数据量无穷大）测试中识别成功的概率，还有常用的贝叶斯决策分类器便是运用了概率公式。模式识别还用到了线性代数，因为运用线性代数可以较为方便表达具有多特征的事物，我们一般会用向量来表达一个事物的特征，对于向量的计算是一定会用到线性代数的知识的。还有一个较为高层次的数学知识是泛函分析，泛函分析是研究无限维线性空间上的泛函数和算子理论，SVM（支持向量机）便是以泛函分析中的理论为基础的，SVM技术还运用到了最优化理论数学知识，最近中科院王守觉院士提出的多维空间仿生模式识别技术是以拓扑学为理论基础的。所以说模式识别科学是应用到数学知识最多的一门学科之一，在我们研究模式识别技术过程中会碰到一个又一个的数学知识，有时需要我们重新拿起读大学时的数学书来学习，有时还需要我们去寻找和学习我们也许从未学习过的数学知识，这时你会感觉到你真的是在做研究，仿佛又回到了大学学习时光，你更会感觉到要学好模式识别技术需要多年的积累，浮躁不得，当然，如果你越是坚持下来，你的价值就会越大，因为这是个可以不断得到积累的技术，不象研究上层应用，研究多年并不意味着你就会有多厉害，一下子没有跟进便会被淘汰掉，而后面进来研究的人很容易超越前面研究的人，所以说，模式识别技术是一个喜欢做研究的人的一个很好的选择

模式识别技术漫谈(2)

                                                                       -------大量应用了概率和统计分析方法

    模式识别大体上可以分为统计模式识别和句法模式识别，统计模式识别是对大量的样本进行统计或学习而最后得到一个分类器，如贝叶斯分类器、神经网络、SVM、K近邻法则等都是属于统计模式识别的方法，句法模式识别则是依据一定的逻辑规则进行判别，如图像形状判断、语法类型判断、地址细分等，句法模式识别也可以称为结构模式识别，一般是应用于逻辑清楚、不易混淆的识别应用中，识别方法也比较简单，所以现在研究的大部分都是统计模式识别的方法，而且在这其中研究比较集中的是机器学习，因为人们相信：象人类辨别新事物一样，都需要一个学习过程，对于计算机也可以象人类那样地去学习而具有辨识能力。神经网络技术便是基于模仿人类的学习而产生的。说了这么多，其实我想表达的是统计方法在模式识别中的重要性，在这一节我们主要就来讨论一下概率论和统计在模式识别中的应用。

    说到概率和统计就不得不提贝叶斯决策理论，它是解决模式分类问题的一种基本统计途径，贝叶斯决策理论的基本公式可做如下描述：

某个特征被判断为某类的概率 =

该类中出现这个特征的概率 * 该类存在的概率 / 这个特征出现的概率

    上面这个公式是一个条件概率公式的推导，这里用文字来描述，以便更好理解，要想了解更多这方面的知识可以查找有关模式识别的理论书，几乎每种理论书的第一个部分就是描述这方面的内容。我以前看过郎咸平的讲座，他有一句话上我印象很深，大体意思是这样的：成功的商业人士总是在选择做大成功概率的事，而不会冒风险去投机做小概率的事。贝叶斯的基本原则是选择大概率的判断，在某个特征的条件下，哪种类别出现的概率大，则判断为那种类别，这样可以达到错误率最小。实际的运用情形会复杂很多，在多种特征和多种类别的应用中，公式也会演变得很复杂，有很多的参数需要去统计分析，运用贝叶斯决策理论的过程基本上都是一个计算概率和统计分析的过程，在这里有个基本出发点要注意：所有统计必须是在大数据量的情况下，因为概率有个前提条件，即是在大数据量的情况下，所以统计模式识别方法都离不开大数据量的前提条件，应用于分析的样本量必须充分大，否则很有可能做到最后是前功尽弃。

    概率上的应用还有较为常用的理论是马尔可夫模型（Markov model）和稳马尔可夫模型(HMM)，这个是分词技术和语音识别中的基本理论工具之一，其中词频统计是其基本统计需要。马尔可夫模型和稳马尔可夫模型都是多条件概率的应用，追求的也是大概率结果。马尔可夫模型又可以分为一阶马夫可夫模型（Bigram模型）、二阶马尔可夫模型(Trigram模型)、n阶马尔可夫模型（n-gram模型），阶数越大，则需要统计的数据越多，计算的复杂度也会猛增。HMM运用了前向计算法（Viterbi算法），计算复杂度大大降低了下来，所以得到了较为广泛的应用，当今的语音识别算法就是采用HMM理论模型实现的。

    统计分析中有个协方差矩阵，它可以应用于PCA（主成分分析）降维方法中。可以很容易理解，当特征越多时，计算则越复杂，而且计算结果准确性则越低，所以我们总是要想方设法把特征维数降下来，较为常用的方法则是用PCA降维方法（另一个方法VQ也是个很好的降维方法），这个方法是通过大量的样本统计，统计出方差最小的特征，方差越小，则说明这种特征越易混淆，越无助于分类，于是就可以把这些特征去掉，以此降低了特征维数。

    类似于神经网络的机器学习方法也是属于统计模式识别一种，机器学习方法大大简化了我们对样本数据的统计工作量，采用了自动化的方法根据大量样本生成一个分类器，在这其中，统计分析的应用较为稳性，以至于让你无法承认它是属于统计模式识别的方法，但是对于大量样本的学习也可以算是统计方法的范畴，如神经网络中的每个神经节点的系数的形成是依据一定算法（如LMS算法）通过大量样本修正出来的，这个修正的过程也可以算是统计分析的过程。

    既然模式识别技术与概率和统计分析密不可分，所以在设计分类器之前，首先要准备好大量的、周全的、能够覆盖各种情况的训练样本和测试样本，然后对训练样本进行统计分析，分析样本的特点，分析样本的特征值分布规律，得到各种统计数据，最后再来确定模式识别的方法，测试样本用来检验分类器的合理性问题，根据测试样本测试出来的问题，需要返回去修改分类器，这是一个反复的过程，直至最后达到分类器的性能目标。

模式识别技术漫谈(3)

                   -------高维空间

    我们在表示某个事物的特征时，其特征数一般有三个以上的，甚至有好几百个特征，为了表示方便，对于特征值一般采用向量的形式来表示，所以我们在研究模式识别时会有很多的矩阵运算，对于特征值的运算我们可以把它想象成是一个高维空间中的运算，矩阵运算可以方便地表达高维空间中的运算，所以说线性代数是研究模式识别的数学基础，更高层次的数学理论是泛函分析，它是研究无限维空间的几何学和分析学。

    对于三维以下空间，我们可以较容易地想象出来，但是三维以上的空间超出了我们的感知能力，很多在三维以下空间的计算，推广到高维空间时，则不灵了，出现了所谓的“维数灾难”，这是因为高维空间中出现了稀疏性和空空间的现象，即高维空间中的数据分布会非常地稀疏，且可能出现密度会很高的空区域中点，维数灾难是Bellman首先提出来的，它泛指在数据分析中遇到的由于变量过多而引起的一系列问题，有点象“指数爆炸”，随着指数的递增，数据会迅速膨胀到难以想象的大。

       SVM模式识别技术利用核方法，在高维空间中进行变换，巧妙地解决了维数灾难的问题，所以很多实验表明SVM分类算法总是能够优于其它分类算法。虽然有如此的好办法，但是我们还是得想办法降低维数，降低了维数，不仅可以降低计算的复杂度，也可以排除不必要的干扰特征，在众多的特征中也许有些特征是没有用的，即可能存在不是特征的特征，把这些无用的特征去掉，可以改善分类器的性能，目前降低维数主要应用的办法是PCA方法，很多人在描述这个方法时总要扯上协方差矩阵，让人陷入一大堆公式的推导中，其实核心思想就是把方差最小的那些特征排除掉，如果你知道这一点，可以不用理协方差矩阵，直接通过统计样本的特征值方差来实现PCA方法。

    两组特征之间的距离可以有很多种表示方法，如欧氏距离、绝对值距离、切比雪夫距离、马氏距离、兰氏距离、相似系数、定性指标的距离等，大家比较熟悉的是欧氏距离，其实这种距离在高维空间并不常用，不仅是因为计算量大，还因为不同特征的值，其计算单位不一样，不可以把每种特征同等看待，在模式识别中采用哪种距离计算方式很重要，会关系到分类器设计的成败。计算距离的方式需要根据实际情况灵活应用，有时甚至可以自己设计距离计算方式，只要满足距离的四个条件即可：

1．当且仅当两点重合时距离才会等于0;

2．距离值必需是大于或等于0;

3．对称性：从A点到B点求得的距离等于从B点到A点求得的距离；

4．三角不等式：三个点形成的三角距离关系中，任两边的和大于第三边

模式识别技术漫谈（4）

                   ------------关于机器学习

一提到机器学习，首先大家会想到的一定是神经网络，其实机器学习方法很多，这里借用“Learning OpenCV”（Gary Bradski and Adrian Kaehler）中第十三章的关于机器学习算法总结的那个表来说明一下机器学习有哪些算法：

ML AlgorithmComment

MahalanobisA distance measure that accounts for the “stretchiness” of the data space by dividing out the covariance of the data. If the covariance is the identity matrix (identical variance), then this measure is identical to the Euclidean distance measure.

K-meansAn unsupervised clustering algorithm that represents a distribution of data usingK centers, whereK is chosen by the user. The difference between this algorithm and expectation maximization is that here the centers are not Gaussian and the resulting clusters look more like soap bubbles, since centers (in effect) compete to “own” the closest data points. These cluster regions are often used as sparse histogram bins to represent the data. Invented by Steinhaus [Steinhaus56], as used by Lloyd.

Normal/Naїve Bayes classifier

A generative classifier in which features are assumed to be Gaussian distributed and statistically independent from each other, a strong assumption that is generally not true. For this reason, it’s often called a “naїve Bayes” classifier. However, this method often works surprisingly well. Original mention.

Decision trees

A discriminative classifier. The tree finds one data feature and a threshold at the current node that best divides the data into separate classes. The data is split and we recursively repeat the procedure down the left and right branches of the tree. Though not often the top performer, it’s often the first thing you should try because it is fast and has high functionality.

BoostingA discriminative group of classifiers. The overall classification decision is made from the combined weighted classification decisions of the group of classifiers. In training, we learn the group of classifiers one at a time. Each classifier in the group is a “weak”classifier (only just above chance performance). These weak classifiers are typically composed of single-variable decision trees called “stumps”. In training, the decision stump learns its classification decisions from the data and also learns a weight for its “vote” from its accuracy on the data. Between training each classifier one by one, the data points are re-weighted so that more attention is paid to data points where errors were made. This process continues until the total error over the data set, arising from the combined weighted vote of the decision trees, falls below a set threshold. This algorithm is often effective when a large amount of training data is available.

Random trees

A discriminative forest of many decision trees, each built down to a large or maximal splitting depth. During learning, each node of each tree is allowed to choose splitting variables only from a random subset of the data features. This helps ensure that each tree becomes a statistically independent decision maker. In run mode, each tree gets an unweighted vote. This algorithm is often very effective and can also perform regression by averaging the output numbers from each tree.

Face detector /

Haar classifier

An object detection application based on a clever use of boosting. The OpenCV distribution comes with a trained frontal face detector that works remarkably well. You may train the algorithm on other objects with the software provided. It works well for rigid objects and characteristic views.

Expectation maximization (EM)A generative unsupervised algorithm that is used for clustering. It will fitN multidimensional Gaussians to the data, whereN is chosen by the user. This can be an effective way to represent a more complex distribution with only a few parameters (means and variances). Often used in segmentation. Compare with K-means listed previously.

K-nearest neighborsThe simplest possible discriminative classifier. Training data are simply stored with labels. Thereafter, a test data point is classified according to the majority vote of its K nearest other data points (in a Euclidean sense of nearness). This is probably the simplest thing you can do. It is often effective but it is slow and requires lots of memory.

Neural networks /

Multilayer perceptron (MLP)

A discriminative algorithm that (almost always) has “hidden units” between output and input nodes to better represent the input signal. It can be slow to train but is very fast to run. Still the top performer for things like letter recognition.

Support vector machine (SVM)

A discriminative classifier that can also do regression. A distance function between any two data points in a higher-dimensional space is defined. (Projecting data into higher dimensions makes the data more likely to be linearly separable.) The algorithm learns separating hyperplanes that maximally separate the classes in the higher dimension. It tends to be among the best with limited data, losing out to boosting or random trees only when large data sets are available.

    对于这么多的算法，如果想很好地学习它，运用OpenCV开源程序确实是一个很不错的选择，当然，在学习某个算法之前，还是得应该认真研究一下相关理论知识，否则不一定能够看懂其实现代码。

    这里有个“没有免费的午餐”的理论，提出没有最好的算法，每种算法总有它的优势和缺陷，即让我们不要太迷信某一个算法的绝对优势，在采用某一个算法时要明白“得”与“失”，所以单一的算法总不能满足实际需要，往往需要采用多个算法来提高识别性能。还有一个“剃刀原理”，就是尽量不要把问题复杂化，要尽力把没用的、会引起问题复杂化的因素剔除掉，对于识别算法也一样，并不是越复杂的算法越有用，有时简单的算法也能够达到较好的性能。

    机器学习中大部分的算法是为了寻找（或者拟合）一个分隔曲线，如果是线性可分，则这条分隔线即是一条直线（如果是高维空间中则是一个超平面），如果是非线性可分，则这要分隔线是一条曲线（如果是高维空间中则是一个超曲面），如果理解了这一点，你可能就会很好理解神经网络中为什么每个结点采用函数大都是正余弦函数：通过傅立叶变换原理我们可以知道用正余弦函数来拟合一条曲线是最好的选择。

    对于模式识别算法的研发，我个人觉得创新思维和扎实的技术积累最为重要，对于某个识别技术的开发，也许会有很多的识别方法让你选择，也许会没有一种方法可以适合你，这时就需要你创新地应用某个识别方法，甚至由此产生新的独特的识别方法，有了既定的算法方向，剩下的就是长期的技术积累，要把一个好的识别算法应用到能用的产品中，一般都需要有一个长期的完善过程，任何浮躁、短视的心态都无法成功。

神经网络基本原理

学习模式识别我个人觉得从神经网络入手可能是个较好的选择，一方面可以避免一下子就陷入复杂的公式推导中，另一方面可以让我们较快就能体验到模式识别是个什么样的技术，因为我们可以利用matlat或openCV非常方便地进行实践(学习一种技术，多去实践非常有助于对理论知识的理解)。神经网络技术是从仿生的角度来思考模式识别技术，探寻模仿人类的智能一直以来是科学界所研究的目标，神经网络技术就是基于此而产生的，但是神经网络能够得到应用还是因为数学问题方面得到了解决，最优化理论中的梯度下降法便是神经网络实现原理的核心，梯度下降算法是一个循环的计算过程：

1． 为算法模型参数值选择初始值，或随机选择些初始值；

2． 计算每个参数对应的损失函数的变化梯度；

3． 根据梯度值改变参数值，使得错误值变得更小；

4． 重复第二和第三步骤直至梯度值接近于0。

神经网络方法就是通过训练样本进行学习来拟合出一条分割线（对于维数是三维的识别，则是个平面或曲面，三维以上则是超平面或超曲面），如果这条分割线是一条直线（或平面，或超平面），则称为线性神经网络，否则为非线性神经网络，线性神经网络较好理解，理解了线性神经网络，对于非线性神经网络则能够更易理解，所以这里先以线性神经网络为例来解释神经网络的原理，下图是一个二维特征分布图，中间的一条直线是分割线，我们现在要关心的问题是这条分割线是如何计算出来，如果学过数学，我们知道可以用最小二乘法把它计算出来，但这里我们将要用神经网络的学习方法来把它学习出来：

从上图我们可以知道，只要我们能够得到w1,w2,b的值，则这条直线我们就可以求出来了，据此我们构造出如下所示的神经网络拓扑图：

从上图中的w1,w2，我们把它们称为权值，b称为阈值，神经网络的学习过程便是不断地调整权值和阈值，直至最后达到最小的错误率，对于线性神经网络，我们可以采用LMS算法，即最小均方差算法来求出权值和阈值，如下是LMS算法的描述：

原理：通过调整线性神经网络的权值(w)和阈值(b)，使得均方差最小。

已知有样本集：{p1,t1},{p2,t2},{p3,t3}……{pn,tn}.（如果样本特征值是多维的，则p是个向量表达式）

求出均方差：mse = sum( e( i )2 ) / n = sum(t(i) – a(i))2/ n, 其中i = 1~n，a(i) = pi * w + b

假设第k步已分别求出权值梯度（Gw）和阈值梯度（Gb），则第k+1步权值和阈值分别为：

w(k+1) = w(k) – Gw* α ;

b(k+1) = b(k) – Gb*α ;    α为学习率

下一步就是要怎么算出梯度，如果权值和阈值的变化能够使得均方差趋向最小，则便可以达到我们的目标，依此我们可以对均方差公式求对权值和阈值的偏导，这个偏导值便是我们所要的梯度值，它反应了权值或阈值变化与均方差的关系，偏导公式的演变（推导）如下：

əe2(i)/əw = 2e(i) * əe(i)/əw = 2e(i) * ə(t(i) – a(i))/əw = 2e(i) * ə[t(i) – (w*p + b)]/əw

        = –2e(i) * p;

əe2(i)/əb = 2e(i) * əe(i)/əb = 2e(i) * ə(t(i) – a(i))/əb = 2e(i) * ə[t(i) – (w*p + b)]/əb

        = – 2e(i);

第k步的平均差值表示为：e(k) = sum(e(i))/n;

于是最后我们就可以得到权值和阈值的变化方程式：

w(k+1) = w(k) – Gw* α = w(k) + 2 * e(k) * p * α;

b(k+1) = b(k) – Gb* α  = b(k) + 2 * e(k) * α;

    其实，上面所描述的神经网络是一种单层的神经网络，早在1969年，M.Minsky和S.Papert所著的《感知机》书中对单层神经网络进行了深入分析，并且从数学上证明了这种网络功能有限，甚至不能解决象"异或"这样的简单逻辑运算问题。同时，他们还发现有许多模式是不能用单层网络训练的，真正让神经网络得到广泛应用的是1985年发展了BP网络学习算法，实现了Minsky的多层网络设想，BP网络是一种多层前馈型神经网络，其神经元的传递函数是S型函数（非线性函数），它可以实现从输入到输出的任意非线性映射，由于权值的调整采用反向传播（Back Propagation）学习算法，因此被称为BP网络，目前，在人工神经网络应用中，大部分是采用BP网络及其变化形式，它也是前向网络的核心部分，体现了人工神经网络的精华。BP神经网络不仅可用于模式识别，还可用于函数逼近、数据压缩应用中。

     BP算法跟上面介绍的算法非常相似，也是根据均方差求权值和阈值的调整方向，也是通过对权值变量和阈值变量分别求偏导得到权值和阈值的修正梯度方向，差别在于BP神经网络有好几层，要从输出层开始，一层一层地计算出每层的权值变化和阈值变化（所以称为反向传播学习算法），另一个差别是有些网络层的神经元的传递函数采用log-sigmoid型非线性函数，对于这类函数需要对其进行求导。

     BP算法的主要缺点是：收敛速度慢、存在多个局部极值、难以确定稳层个数和稳层节点的个数。所以在实际应用中，BP算法很难胜任，需要进行改进，主要有两种途径进行改进：一种是启发式学习算法（对表现函数梯度加以分析以改进算法），另一种是更有效的优化算法（基于数值最优化理论的训练算法）。启发式学习算法有这些：有动量的梯度下降法、有自适应lr的梯度下降法、有动量和自适应的梯度下降法、能复位的BP训练法等，基于最优化理论的算法有这些：共轭梯度法、高斯-牛顿法、Levenberg-Marquardt方法，这些改进的算法在matlab中都可以找得到，matlab提供了丰富的神经网络算法，除了BP神经网络，还有基于径向基函数的神经网络（如广义回归神经网络、概率神经网络）、反馈型神经网络（如Hopfield网络、Elman神经网络）、竞争型神经网络（如自组织特征映射神经网络、学习向量量化神经网络），所以学习神经网络，matlab是个非常好的工具，如果想看具体的实现方法，openCV提供了BP算法的实现，可惜目前openCV只实现BP算法，很希望有更多的神经网络算法能够在openCV中被实现。

     对于神经网络，万不可过于迷信它的厉害，对于样本种类多、神经网络节点多，神经网络的收敛速度会很慢，导致学习要花费很长时间，由于存在多个局部极值点，导致初值不同和学习样本不同时，学习效果也不同，所以经常要多次学习才能够得到较好的效果，根据问题的复杂度，设计合适的神经网络的网络拓扑结构也是一个非常难的问题。神经网络是人类模仿生物神经网络原理的一个成果，但是还远远无法达到生物的神经网络功能，现在的人工智能技术甚至连蟑螂都不如，也比不上小小的蚂蚁，人工智能技术的研究还有非常漫长的路要走