模式识别-总结

模式识别-总结PatternRecognition余莉电话：73478（O）,75420（H）E-mail：[e-mail]课程内容第一章引论(2学时)第二章聚类分析(4学时)第三章判别域代数界面方程法(4学时)第四章统计判决与估计(4学时)第五章统计学习与估计(4学时)第六章最近邻方法(2学时)第七章特征提取与选择(2学时)复习(2学时)实验上机实验(8学时)作业每次课后布置习题考核笔试(70%)+实验(20%)+作业(10%)概念模式识别：确定一个样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。模式分类的过程。样本（Sample)：一个具体的研究（客观）对象。如患者，某人写的一个汉字，一幅图片等。模式（Pattern）：对客体（研究对象）特征的描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。特征（Features）：能描述模式特性的量（测量值）。在统计模式识别方法中，通常用一个矢量表示，称之为特征矢量，记为模式类（Class）：具有某些共同特性的模式的集合。12(,,,)'nxxxx1.1.3模式识别系统图1.2模式识别系统框图判决过程学习过程分类器训练分类器特征提取选择预处理模式采集1.1.4模式识别方法统计判决句法结构模糊判决逻辑推理神经网络第二章聚类分析内容：聚类的基本概念；相似性测度、类间距离、聚类准则；简单聚类、层次聚类；动态聚类。要求：重点:相似性测度、K均值聚类和层次聚类算法。难点:聚类准则函数。小结一、影响分类的因数（1）分类准则；（2）特征量的选择；（3）量纲。二、模式相似性测度（一）距离测度(1)欧氏距离(2)马氏距离对坐标系平移、旋转、比例不变。（二）相似测度相关系数（特征矢量的方向）对坐标系平移、旋转、比例不变。21(,)()'()ijijijdxxxxVxx1/2()'()(,)[()'()()'()]xxyyrxyxxxxyyyy三、类间距离递推公式（其中l=pq）222222klpkpqkqpqkpkqDDDDDDpq最近距离1/21/20-1/2最远距离1/21/201/2中间距离1/21/2-1/40重心距离np/(np+nq)nq/(np+nq)-pq0平均距离np/(np+nq)nq/(np+nq)00可变平均距离(1-)np/(np+nq)(1-)nq/(np+nq)10可变距离(1-)/2(1-)/210离差平方和(nk+np)/(nk+nl)(nk+nq)/(nk+nl)-nk/(nk+nl)0222222221/21/2||||min[,][],max[,][]2222abababababab四、聚类准则函数评估分类过程或分类结果优劣的准则函数（一）类内距离准则（误差平方和准则）2()()()1111()'()minjjnnccjjjWijijijjijiJxmxmxm()11(1,2,,)jnjjiijmxjcn()1,(1,2,,),cjijjjxjcnN式中，nj是j中的样本个数，加权类内距离准则21cjWWjjnJdN＝()()22()()2(1)jkjjijjjjikxjjxdxxnn式中，是j内样本间的均方距离。适用于各类模式呈团状分布的情况。四、聚类准则函数（二）类间距离准则1()'()maxcBjjjJmmmm()11(1,2,,)jnjjiijmxjcn式中，是总的样本均值矢量，加权类间距离准则11NiimxN1()'()maxcjWBjjjnJmmmmN对于两类问题，可以定义21212()'()BJmmmm1222WBBnnJJN（三）基于类内类间距离的准则函数构造能同时使Jwmin和JBmax的准则函数类内离差矩阵（ScatterMatrix）()()()()()1111()(),,,(1,2,,)jjnnjjjjjWijijijjiiijjSxmxmxmxjcnn总的类内离差矩阵()1cjjWWjnSSN总的离差矩阵11()()NTiiiSxmxmN13452m1m类间离差矩阵1()()cjBjjjnSmmmmN11NiimxN（三）基于类内类间距离的准则函数聚类的基本目标是使JWB=Tr[SB]max和JWW=Tr[SW]min因此可定义如下聚类准则函数11WBJTrSS12WBJSS13WTJTrSS14WTJSSJimax，(i=1,2,3,4)即，类内越“紧”，类间越“开”，聚类效果越好。2.3聚类算法（一）简单聚类最邻近规则试探法给定阀值T，聚类到zl（二）层次聚类初始每个样本点为一类（N类），将类间距离最小者合并为一类，逐级进行。类间距离可用：最小、最大、中间、重心、平均距离等。（三）动态聚类算法C-均值算法（适用于团状分布的情况）重新聚类ISODATA算法c（预期类数），Nc（初始类心个数），N（各类最小样本数），s（类中样本特征分量标准差上限），jmax，D（聚合中心最小间距），L，I1c()()jj1j10,(1),1,2,...,;1(),NN,jiiNjjjiiijczxiczkxxNC-均值算法性能算法简单，收敛。如模式呈现类内团状分布，效果很好，故应用较多。能使各模式到其所判属类别中心距离平方之和为最小。第三章类域界面方程法总结分类特征空间的分划子空间的界面：判别函数求解3·2线性判别函数式中,称为权矢量或系数矢量。写成矢量形式这里，，，称为增广特征矢量和增广权矢量。增广特征矢量的全体称为增广特征空间。()0dx()dxwx121(,,,,)nn1122101()nnnndxwxwxwxwwxw012(,,,)n()dxwx12(,,,,1)nxxxx121(,,,,)nn判别规则：解多类问题的两分法:⑴两分法有不确定区域⑵两分法⑶没有不确定区的两分法令120()00ixdxwxxx或拒判ii()0()0,iijdxifthenxdxjiijij()0,,ijiifdxjithenx()()()()ijijijdxdxdxwwx()(),()max[()]ijiijijifdxdxjithenxorifdxdxthenx3·3判别函数值的鉴别意义、权空间及解空间（1）系数矢量是超平面的法矢量；（2）的绝对值正比于到超平面的距离；（3）的正（负）反映在超平面的正（负）侧。0w()0dx()dx()dxx()dxx()0dx3·4Fisher线性判别多维Fisher变换利于分类的一维（1）Fisher准则函数对两类问题作变换，n维矢量在矢量方向轴上的投影Fisher准则函数()()()(),1,2iiiWjijijSxmxmi121212()()BSmmmmxu()()iijjyux122212222()()maxBBF（2）Fisher变换对于两类问题,它所对应的本征矢量称为Fisher最佳鉴别矢量。Fisher变换函数：（3）Fisher判别规则1WBSSuu1WBSSu112()WuSmm112()WymmSx12tuxyyx1212()22tumumyummum()dxuxum12()0uxmx1112122()()02WmmmmSxx3.5一次准则函数及梯度下降法如果训练模式已经符号规范化，即已乘以－1（包括增广分量1），则()(1)()kwkwkwkx()0()()0()kkwkxwkx若正确分类若错误分类2kx收敛定理解多类问题3·6二次准则函数及其算法221(,,)()minNiiiJXwbXwbwxb0Xwb式中是矩阵。将上面的不等式组写成矩阵方程形式，并引入N维余量矢量，于是不等式方程组变为b0XwbX(1)Nn121211121(1)21222(1)12(1)(1)(,,,)NNnnNNNnNnxxXxxxxxxxxxxxxx最小方差准则及W-H算法针对方程组,构造方差准则函数对于,此时的,而对于,此时的。如果方程组有唯一解,说明训练模式集是线性可分的,如果方程组无解,极小点值是最小二乘解。一般情况下使极小等价于误分模式数目最少。Xwb()()()JwXwbXwb21()minNiiiwxb(1,2,,)iiwxbiNmin()0JJwiiwxb()0JwJ⑴伪逆法求对的梯度并令其为零，有可得(3-6-12)当(X’X)-1存在时，X+=(X’X)-1X’称为X的伪逆(也称广义逆或M-P逆)，称为的伪逆解。X’X是(n+1)×(n+1)矩阵，一般是非奇异的。当(X’X)-1不存在时，可用广义逆法解这里(X’X)+为X’X的广义逆矩阵。()Jw()2()0JwXXwbwwXXwXb1()wXXXbXbwXb()wXXXb求解最佳权矢量的方法：⑵梯度法()Jw()2()JwXXwb(0)w(1)()(())kwkwkXXwkb由前述知，的梯度为梯度下降算法迭代公式为Step1.任取Step2.(3-6-13)可以证明，当为任意正的常数，则该算法使权矢量序列收敛于;满足，也称为MSE解。()wkw()0Jww11/,kkStep1.任取Step2.此算法通常称为W－H(Widrow－Hoff)算法仿前采用单样本修正法，则式(3-6-13)可以修改为1()()NkkkkXXwbwxbx(0)w(1)()(())kkkkwkwkbwkxx为了减少计算量和存储量，由于(3-6-14)3·12势函数分类法概念：1：q+；2：q-定义点处的位势函数，它应满足：⑴；⑵是连续光滑函数；⑶是与间距离的单值单调下降函数;当且仅当时，达其最大值;jx(,)jKxx(,)(,)jjKxxKxx(,)jKxx(,)jKxxxjxjxx,(,)0jjxxKxx第一类位势函数设是定义域中的完备正交函数集，位势函数取为第二类位势函数取关于和的距离的对称函数作位势函数，例如(),1,2,ixix1(,)()()mjiijiKxxxx2(,)expjjKxxxx21(,)1jjKxxxxxjx两类位势函数第四章统计判决总结概念:后验概率：类概密：先验概率：()iPx()ipx()iP4·1最小误判概率准则判决总的误判概率2121()pxdx1212()pxdx112221()()()PePP211212()()()()PpxdxPpxdxt12xp(x|1)P(1)p(x|2)P(2)21P(2)12P(1)多类问题，最小误判概率准则有如下几种等价的判决规则(1)if()(),thenijiPxPxjixif()max[()]thenijijPxPxxif(|)()(|)(),theniijjipxPpxPjixif(|)()max[(|)()