识别的基础是认知
认知Cognition：获取某种事物的特征——概念抽象
识别Re-cognition：根据特征决定某个具体的事物是不是某种事物——概念归类
模式：一类事物的共同特征
识别：对事物进行概念归类
模式识别：依据事物的特征进行概念归类

特征
相似性
类
特征空间
向量空间
集合空间

通过训练（学习）得到分类器模型参数

分类器如何学习分类决策规则？

两种模式：有监督学习和无监督学习——从训练集中学习

对于每一个类别都给定一些样本——形成一个具有类别标签的训练样本集——分类器通过分析每一个样本去寻找属于同一类样本具有哪些共同特征——从训练集中学习到具体分类决策规则——有监督的学习

分类器通过有监督学习模式学习到的每个类别样本的特征就是关于某个类别概念的知识—— 学习过程就是认知过程

样本标签如何得到？——人来给定

有监督学习——从人的经验中学习分类知识——智能水平有上限

给定训练样本集但没有给每一个样本贴上类别标签——属于同一个类别的样本之间的相似程度会大于属于不同类别的样本之间的相似程度——根据相似程度的大小，按照一些规则把相似程度高的一些样本作为同一类——将训练样本集的一些样本划分成不同的类别——再从每一个类别的样本中去寻找共同特征，形成分类决策规则——无监督学习

无监督学习——自主地从数据所代表的自然规律中学习关于类别划分的知识——分类器能达到更高的分类水平——未来模式识别发展的主要方向

2.1.3

属于同一个类别的样本之间的相似程度会大于属于不同类别的样本之间的相似程度——不同类样本之间的相似度越小，分类决策规则的裕量也就越大

这样可以作为评判用于监督学习的带标签训练样本集以及作为无监督学习结果的样本集，它的优劣程度的一个指标，称为“紧致性”准则，即：紧致性好的样本集样本的类内相似度远大于类间相似度。

紧致性——定性准则

若要进行定量评判——确定如何度量相似性——可以设置多种指标——如：距离指标（最常用，距离可以定义在任意集合上，只要去计算满足三条标准：1.正定性：距离是个大于等于0的正实数，当且仅当自己和自己计算距离时才为0；2.对称性：样本之间的距离值计算与计算顺序无关；3.传递性：满足三角关系——两个样本之间的距离一定小于等于分别于第三个样本之间的距离之和。||在向量空间中可以定义欧氏距离、曼哈顿距离、切比雪夫距离等|| 非向量空间也可以定义距离，如：两个字符串之间的编辑距离也是一种合法的距离定义）非距离的相似度量标准（如：余弦相似度——使用向量空间中两个向量之间的夹角来表达相似程度：cosθ=x^Ty/||x||·||y|| ;皮尔逊相关系数Pxy=cov(x,y)/∆x∆y;Jaccard相似系数）

如果我们希望有紧致性好的样本集——那么就希望能有有效的信息能够将不同类的样本很好地区分开——增加特征的种类==增加特征的维度——特征的维度越多，用于识别的信息就越丰富，就有越多的细节信息可以将不同的样本之间的相似度降低，提高样本集的紧致性

特征的维度可以无限制地增加吗？——

不需要无限制地增加，只要不断地增加模式识别问题中地特征维数会产生维数灾难（cruse of dimensionality)——当一个问题描述地维度不断增加时会带来计算量剧增与解法性能下降等严重问题——模式识别中的维数灾难：随着特征维度的增加分类器的性能将在一段快速增加的区域后急速地下降并且最终无法使用

导致维数灾难的根本原因：在于训练集样本的数量不不足

当特征空间以同样密度能够容纳的样本总数呈指数增长时，而如果给定样本集中的样本数量没有同步按照指数规律增加的话，那么问题越往高维度特征空间映射时样本集中的样本就越稀疏，从而使得样本集的紧致性越来越差，因此分类器的性能越来越差。

要解决维数灾难问题或者要同步地大量增加样本集样本的数量，难以实现，或者尽可能减少问题所使用的特征维度。

在降低维度的同时尽可能地提升每一个维度在分类中的效能，从而使模式识别问题在较低的维度下解决。

特征生成+特征降维 重点领域——其结果直接影响分类器性能的好坏

2.1.4泛化能力与过拟合

我们期望分类器能够从训练集样本中发现所要分类的各个类别的普遍特点即找到最优的分类器，使分类器在经过训练后不仅能将训练集中的样本正确分类，而且对于不在训练集中的新样本也能够正确地分类

泛化能力：训练好的分类器对未知新样本正确分类的能力

因为有误差所以不能同时满足【正确分类样本集】和【正确分类未知新样本】

采集数据时由于数据采集方法的问题或者存在噪声干扰得到的样本特征会存在误差甚至会出现“异常数据”

如果我们要求分类器必须正确分类则会在分类规则上出现“失真”，从而在面对新的未知样本进行分类时出现错误（使分类器泛化能力降低）====称为分类器训练过程中的“过拟合”

“结构风险最小化准则”

2.1.5 模式识别系统

模式识别系统

分类决策规则是从自动计算中获取的而不是人工设定的

设计模式识别系统就是设计分类器的模型、所使用的的特征和分类器参数的调整算法

第一个环节：

通过采集转换得到计算机能接受和处理的数据

模式采集：传感器、变送器、模数转换

得到的数据：待识别样本的原始信息（包含大量干扰和无用数据）

第二个环节：

通过各种滤波降噪措施降低干扰的影响，增强有用的信息，在此基础上生成在分类上具有意义的各种特征

得到的特征：可以仍然用数值来表示，也可以用拓扑关系、逻辑结构等其他形式表示

第三个环节：

经过一、二环节获得的模式特征维数都是很大的

主要方法：特征选择和特征提取

特征选择：从已有的特征中选择一些特征，抛弃其他特征

特征提取：是对原始的高维特征进行映射变换，生成一组维数更少的特征

第四环节——分类器训练过程==分类器学习的过程

分类器训练是由计算机根据样本的情况自动进行的，分类有监督学习和无监督学习

第五环节——分类决策

在分类器训练结束后，对待分类的样本按照已建立起来的分类决策规则进行分类的过程，在待分类的样本在进行分类决策之前，与训练样本一样要完成模式采集、预处理与特征生成、特征降维等环节的处理，还要持续不断地对分类决策的结果进行评估，已改进分类器的性能。

2.2模式识别的算法体系

模式识别算法

模式识别算法：统计模式识别（主流）、结构模式识别

统计模式识别：将样本转换成多维特征空间中的点，再根据样本的特征取值情况和样本集的特征值分布情况确定分类决策规则。

线性分类器：是最基本的统计分类器，它通过寻找线性分类决策边界来实现特征空间中的类别划分

贝叶斯分类器：它的决策规则是基于不同类样本在特征空间中的概率分布以逆概率推理的贝叶斯公式来得到类别划分的决策结果

最近邻分类器：把学习过程隐藏到了分类决策中，通过寻找训练集中与待分类样本最相似的子集来实现分类决策

神经网络分类器：来源于对生物神经网络系统的模拟，它的本质是高度非线性的统计分类器并且随着计算机技术的发展从浅层网络向深层网络不断演化

统计聚类分析：是无监督学习的典型代表

聚类分析：是无监督学习的典型代表，目前多采用统计学习的方法。

模糊模式识别：不是一独立的方法，而是将模糊数学引入模式识别技术后对现有算法的模糊化改造，它在更精确地描述问题和更有效地得出模式识别结果方面都有许多有价值的思路。

特征降维：也不是独立的模式识别算法，但是是完成模式识别任务的流程中不可缺少的一个步骤，特征降维通过寻找数量更少对分类更有效的特征来提升整个模式识别系统的性能。

结构模式识别：

结构聚类算法：将样本结构上某些特点作为类别和个体的特征通过结构上的相似性来完成分类任务。

句法模式识别：利用了形式语言理论中的语法规则，将样本的结构特征转化为句法类型的判定，从而实现模式识别的功能。

2.3.1问题：手写数字识别

一个典型的基于视觉的模式识别工程问题

多分类问题

2.3.2算法：从模板匹配开始

模板匹配基本原理：为每一个类别建立一个或多个标准的模板，分类决策时将待识别的样本与每个类别的模板进行比对，根据与模板的匹配程度将样本划分到最相似的类别中。

建立模板时依赖人的经验所以适应性差

2.4算法实例演示：模板匹配

3.1.1线性判别和广义线性判别

“分类决策边界”

判别函数G(x)=0

如果判别函数是线性函数则称为线性判别函数

线性判别函数+对应的分类规则=线性分类器

如果特征空间是一维的，线性分类器的分类决策边界就是一个点

如果特征空间是二维的，线性分类器的分类决策边界是一条直线

如果特征空间是三维的，线性分类器的分类决策边界是一个平面

如果维度很高，从数学上可以得到分类决策边界是一个超平面

是不是任何一个模式识别问题都可以找到线性分类决策边界呢？

给定一个样本集，它是线性可分的吗？

涉及问题：样本集的线性可分性

如果一个样本集，它的各个类别样本的分布区域是相交的，那么肯定是线性不可分的；如果各个类别样本的分布区域是互不相交的，并且都是凸集，那么它一定是线性可分的；如果互不相交但有的是凹集，也不一定是线性可分的，需要找出凹集区域最小的凸集包络线称为凸包，如果凸包都不想交，那么样本集才是可分的，否则不可分。

线性可分性——异或问题

非线性分类问题转化为线性分类问题：

当我们将一个模式识别问题从低维特征空间映射到高维特征空间时，就将一个非线性分类问题转化为一个线性分类问题。======》这种方法被称为“广义线性化”

3.1.2多分类线性判别

需要多个线性判别函数——用二分类问题的组合来确定多分类的分类决策规则

根据一定的逻辑关系构成多分类的线性分类器

绝对可分：对于样本集中的每一个类都有一个线性判别函数，可以把属于这一类和不属于这一类的样本分开。——带来的不可识别区域很多，整体分类器的性能不好。

两两可分：判别函数并不是用于判别属于某一个或者不属于某一个类的样本，而是在两个特定的类别中选边站。减少了不可识别区域，提升了线性分类器的性能。

如果有k个分类，两两可分的线性判别一共需要C2k个判别函数，绝对可分的线性判别需要k个判别函数

最大值可分：样本集中每一个类别对应有一个判别函数，而一个样本将被划分到取值最大的那个判别函数所对应的类别中。——不可识别区域消失，判别函数的数量也仅仅与样本集中的类别数量一样。

如何求最大值可分的判别函数？——工作量大

3.1.3线性判别函数的几何意义

判别函数是样本到决策超平面距离远近的一种度量

样本x到决策边界的距离r正比于判别函数G(x)的值，判别函数的符号代表了距离r的符号，表示该模式位于决策边界的正侧还是负侧

权向量w仅代表决策超平面的法向方向，长度不会影响决策边界在特征空间中的位置，可以取w为1，此时判别函数的值就是样本到决策边界的距离。

3.2.1线性分类器训练的一般思路

线性分类器——由线性判别函数及相应道德分类决策规则构成的

线性判别函数如何得到？——如何设计线性分类器？——训练问题

线性分类器学习/训练的一般思路：

G_ij(x)=w^Tx+w₀

w^T 权向量

w₀ 偏置量

解区域中寻找最优解

1.设定一个标量的准则函数J(w,w₀),使其值能够代表解的优劣程度，准则函数值越小，说明解越符合要求，越好。

2.通过寻找准则函数J(w,w₀)的极小值，就能找到最优的一个解，是准则函数取得极小值的增广权向量w，这就是最优解。 （w,w₀）^*

训练集数据的规范化

3.2.2感知器算法的原理

1.了解感知器模型

感知器（perception）模型是一种神经元模型

多路输入+单路输出

将所有输入信号加权求和后于一个阈值相比较，如果大于阈值，则神经元输出为1；小于等于阈值，则神经元输出为0

没有反馈与内部状态

只能依靠输入信号是否超过阈值来决定是否激活神经元的输出

如果把感知器的输入信号看作是一个待识别样本的特征向量，感知器的数学模型就构成了一个典型的线性分类器，可以做出非常明确的二分类决策

通过样本集使感知器能够学习到输入权重值和输出的阈值

感知器是一个通过输入加权和与阈值的比较来决定是否激活输出的神经元模型，这是一个线性分类器，输入的权构成了线性分类决策边界的权向量，激活输出的阈值\theta就是分类决策边界的偏置量w₀

求解目标：对所有样本，都有w^Tx > 0

感知器算法设定准则函数的依据：最终分类器要能正确分类所有的样本

所以J设定为所有错分样本的判别函数值之和

X₀是所有错分样本的集合

只要存在错分样本，准则函数一定大于0，只有当所有样本正确分类了，准则函数值才能取得极小值0

梯度下降法

w(k+1)=w(k)-p(k+1)∆J(w(k))

3.3算法实例演示：线性分类器

3.4.1线性分类器的松弛求解

3.4.2H-K算法

3.5.1支持向量机的原理

对于线性可分的两类问题其分类决策边界为一n维特征空间中的超平面H

一般情况下会有无穷多个解，当我们确定一个解所对应的权向量w，超平面的斜率和朝向就是确定的了，可以在一定范围内平移超平面H，只要不达到或者越过两类中距离H最近的样本，分类决策边界都可以正确地实现线性分类，所以任何一个求解得到的权向量w都会带来一系列平行的分类决策边界，其可平移的范围具有一定的宽度，称为分类间隔（Marigin of Classification）。

当我们改变w，使分类决策边界的斜率和朝向随之变化时，我们得到的分类间隔是不同的。

分类间隔越大，两类样本做决策时的裕量也就越大

找到可以使分类间隔最大的最优权向量 w*——支持向量机的出发点

分类间隔是由距离分类决策边界最近的少量样本决定的，这些样本被称为“支持向量 support vector”_支撑起了线性分类器在最大分类间隔意义下的最优解

支持向量机的优化求解目标是求取能带来最大分类间隔的权向量w

分类间隔是支持向量到分类决策边界的2倍

Max d = max 2|G_ij(x)|/||w|| 支持向量机采用令|G_ij(x)|=1 =>min ||w|| 将求取最大的d的问题转化为求取权向量的长度最短的问题——为了方便进行二次优化——=>min 1/2 ||w||²

求取优化目标要求两类中的所有样本到分类决策边界的距离都应该比支持向量更大，其他样本的判别函数绝对值都需要大于1，即不等式约束条件为：图

支持向量机采用拉格朗日乘子法将其转化为无约束优化问题来求解，即通过将所有约束条件与拉格朗日乘子相乘后添加到优化目标中，在求取拉格朗日乘子最大值的条件下，求取最短的权向量w——凸规划问题——存在唯一解——其充要条件可以通过拉格朗日函数分别对权向量w和偏置值w0求偏导来得到，即满足这样的条件——得到权向量的表达公式

KKT条件

3.5.2结构风险最小化准则

经验风险:训练之后的分类器的错误分类样本比例

经验风险最小化 R_emp==o

只有当训练集的样本数趋近于无穷，训练集中样本的分布趋近于样本的真实分布时，经验风险才会趋近于真实样本分类的风险

为了从根本上解决“过拟合”问题——提出“结构风险最小化SRM”min(R(w))

结构风险：在一个训练好的分类器面对未知样本时分类错误的概率

泛化误差界：R(w)<=Remp(w)+φ(h/l) 置信风险 l是训练集中的样本数，h为分类器形式的vc维，而φ置信风险的具体计算公式：图

如果分类器函数形式已经确定，则样本数越大，置信风险也就越小；如果训练集中的样本数量不够多，那么结构风险的大小就受置信风险大小的很大影响，而此时置信风险的大小取决于分类器函数形式本身具有的VC维，函数的VC维h越大，则置信风险也就越大，则相应的结构风险也就越大，分类器的泛化能力越差。

什么是VC维？一类函数所具有的分类能力

它的值是一类函数能打散两类样本集中最大样本数量

分类器函数形式的阶次越低，其VC维也就越小，在样本集数量有限的情况下，训练后的分类器结构风险就越小，泛化能力越强。

（支持向量机是阶次最低的线性函数）——是支持向量机在不需要大量训练样本的情况下也能取得泛化能力特别强的分类器训练结果的主要原因

所以支持向量机是应用结构风险最小化准则的一个结果

3.5.3线性不可分时的SVM之一——软间隔支持向量机

线性不可分问题：1.异常点干扰 2.非线性分类

线性支持向量机是把具有最大分类间隔的最优线性判别函数的求解转化为求解最短权向量的二次规划问题

1. 异常点干扰

异常点的判别函数值距离一定小于1

可以在约束条件中减去一项正数kesei，使判别函数的绝对值允许小于1，kesei就称为松弛变量

把kesei也作为优化目标，希望kesei越少越好，越小越好。

最理想的情况：绝大多数支持向量外侧的样本包括支持向量对应的松弛变量都该为0.只有少数支持向量内侧才有一个尽可能小的松弛变量。

因此，可以把所有松弛变量的和值也作为优化目标的一个分项，即在原来的最短权向量的二次优化目标基础上再加上一项C乘以所有松弛变量的和。C为惩罚因子，表示对分类器中存在异常点的容忍程度。C越小，松弛变量的存在对整体优化过程的影响越小，对异常点的容忍度越高。如果C取0，约束条件被破坏。

软间隔的支持向量机：使用松弛变量和惩罚因子的支持向量机

3.5.4线性不可分时的SVM之二——非线性支持向量机

2. 非线性分类——本质上不可分

采用——广义线性化（把低维空间中的非线性问题往高维映射，从而转化为一个线性分类问题）