模式识别理论基础_规范化增广向量

由word文档导入，有些信息可能遗漏

一．绪论

1. 定义
   研究如何使机器具有 识别、分类能力的学科。
   具体说就是利用计算机自动地（或者少人为干预地）把待识别的模式分配到各自类中。
2. 模式识别系统
   2.1基本构成：
    数据获取
    预处理
    特征选择/提取
    分类规则训练
    分类决策

2.2“处理”与“识别”两个概念的区别：
处理：输入与输出是同样的对象，性质不变。
识别：输入的是事物，输出的是对它的分类、理解和描述。

2.3模式识别系统分类
从实现方法来分：
监督（有人管理）分类：利用判别函数进行分类判别。需要有足够的先验知识。
非监督（无人管理）分类：用于没有先验知识的情况下，通常采用聚类分析的方法。

二．聚类分析

1.概念：
非监督分类，距离在聚类中很关键，由模式样本的特征值变成数量再变成特征向量。
2.模式相似性的测度：距离
1）欧式距离

2）马氏距离

3）明氏距离

4）汉明距离

5）角度相似性函数

k均值算法

1.前提：
模式特征矢量集为{x1,x2,…,xN}；类的数目K是事先取定的。
2.基本思想：
任意选取K个聚类中心，按最小距离原则将各模式分配到K类的某一类。不断计算聚类中心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方之和最小。
Sj：第j个聚类集（域），Zj ；聚类中心，Nj： Sj中所含的样本个数
聚类中心的选择应使准则函数J极小，Sj类的聚类中心应选为该类样本的均值。
3.步骤：
(1)任选K个模式特征矢量作为初始聚类中心： z1(1) ,z2(1) ,…zK(1)。括号内的序号表示迭代次数。
(2)将待分类的模式特征矢量集{x}中的模式逐个按最小距离原则分划给K类中的某一类。
(3)计算重新分类后的各聚类中心zj(k+1)，即求各聚类域中所包含样本的均值向量： ，以均值向量作新的聚类中心。可得新的准则函数：
(4)如果zj(k+1)=zj(k)(j=1,2,…K),则结束；否则，k=k+1,转(2)。
注意：多次运行K均值算法，例如50~1000次，每次随机选取不同的初始聚类中心。聚类结束后计算准则函数值，选取准则函数值最小的聚类结果为最后的结果。该方法一般适用于聚类数目小于10的情况。

三．线性判别函数

一． 1.判别函数
统计模式识别分为聚类分析法和判决函数法，其中判决函数法又包括几何分类法（确定性时间分类，线性，非线性）以及概率分类法（随机事件分类）。
判别函数即用来对模式进行分类的准则函数。

2．线性判别函数
n维线性判别函数的一般形式为：

其中X，W不包含最后一项常数项

：权向量，解向量，即参数向量
增广向量就把最后一项加进去，

W加一个Wn+1,X加一个1
这里有一个多类情况：
1）
：
用线性判别函数将属于ωi类的模式与其余不属于ωi类的模式分开。将某个待分类模式 X 分别代入 M 个类的d (X)中，若只有di(X)>0，其他d(X)均<0，则判为ωi类。对某一模式区，di(X)>0的条件超过一个，或全部
的di(X)<0 ，分类失效。相当于不确定区(indefiniteregion ，IR)。

2）
：
在 M 类模式中，与i 有关的M-1个判决函数全为正时，X∈ωi。其中若有一个为负，则为IR区。d xy（X）=-d yx(X)

3.广义线性判别函数
通过某映射，把模式空间X变成X*，以便将X空间中非线性可分的模式集，变成在X*空间中线性可分的模式集。

4.线性判别函数的几何性质
模式空间：以n维模式向量X的n个分量为坐标变量的欧氏空间。
模式向量的表示：点、有向线段。
线性分类：用d(X)进行分类，相当于用超平面d(X)=0把模式空间分成不同的决策区域。

感知器算法

只要求出权向量，分类器的设计即告完成。利用已知类别的模式样本训练出权向量W。
训练：用已知类别的模式样本指导机器对分类规则进行反复修改，最终使分类结果与已知类别信息完全相同的过程。
感知器：对一种分类学习机模型的称呼，属于有关机器学习的仿生学领域中的问题，由于无法实现非线性分类而下马。但“赏罚概念（ reward-punishment concept）” 得到广泛应用。

对样本进行规范化处理，即ω2类样本全部乘以(－1)，则有：
感知器算法通过对已知类别的训练样本集的学习，寻找一个满足上式的权向量。

两类感知器算法步骤：
（1） 选择N个分属于ω1和 ω2类的模式样本构成训练样本集{ X1, …, XN }构成增广向量形式，并进行规范化处理，每个向量变成增广向量后面加1，二类需要每个再乘以-1。任取权向量初始值W(1)（如w=（0，0，0）），c=1开始迭代。迭代次数k=1。
（2） 用全部训练样本进行一轮迭代，计算WT(k)Xi 的值，并修正权向量分两种情况，更新权向量的值：

分类器对第i个模式做了错误分类，权向量校正为
，其中c：正的校正增量，取1。

分类正确，权向量不变

统一为：

（3） 分析分类结果：只要有一个错误分类，回到（2），直至对所有样本正确分类

感知器算法是一种赏罚过程：
分类正确时，对权向量“赏”——这里用“不罚”，即权向量不变；
分类错误时，对权向量“罚”——对其修改，向正确的方向转换。
收敛性：经过算法的有限次迭代运算后，求出了一个使所有样本都能正确分类的W，则称算法是收敛的。
当c、W(1)取其他值时，结果可能不一样，所以感知器算法的解不是单值的。

多类：
训练样本为增广向量形式，但不需要规范化处理。
第k次迭代时，一个属于ωi类的模式样本 X 被送入分类器，计算所有判别函数 分二种情况修改权向量：
1） 则权向量不变；
2）若第l个权向量使 ，则相应的权向量作调整，即：

四．贝叶斯判别准则

1.基础概率公式

先验、后验、条件概率

2.最小错误率贝叶斯决策
规则：

几种等价形式：
将后验概率转化为类概率密度函数和先验概率的表示。由：

两类问题：上式等于

3.最小风险贝叶斯决策

决策规则为：

推导与判别步骤：

例：
方法一 最小错误率

方法二：最小风险

正态分布贝叶斯决策：

正态最小错误率求分界面：
令
u为先验概率值比p(w1)/p(w2)

贝叶斯分类器错误概率与模式样本的马氏距离的关系：

五．特征提取

1.特征选择与特征提取
特征选择，就是从n个度量值集合{x1, x2,…, xn}中，按某一准则选取出m维（m<n）供分类用的子集，作为降维的分类特征
特征提取，就是使(x1, x2,…, xn)通过某种变换，产生m个特征(y1, y2,…, ym) (m<n) ，作为新的分类特征（或称为二次特征）

2．K-L变换
k-l变换是在最小方误差的意义下获得数据压缩的最佳变换。
基本过程/步骤：
1） 计算总体自相关矩阵R=E[XXT]
2） 求R的特征值|R-入I|=0，从大到小排列
3） 选前几个大特征值，计算对应的特征向量Ru=入u
4） 归一化得到变换矩阵U
5）
得到kl变换结果

六．神经网络
1．感知器分类问题
Xor分类——两层前馈神经网络：

2.BP神经网络——采用BP算法的多层感知器
BP算法（误差反向传播算法）

步骤：
1、 对权值和阈值初始化为0-1内的随机数
2、 输入样本，指定输出层各神经元的期望输出值
3、 正向计算每层的实际输出
4、 从输出层反向修正权值直到第一隐层，
5、 从2开始循环直到权值稳定

3.神经网络结构分类
分层结构—有明显层次，信息流向由输入层到输出层—前馈网络，
相互连接—没有明显层次，任意两个神经元之间可达，具有输出单元到隐层单元或输入单元的反馈连接—反馈网络