中科院_黄庆明_模式识别_考试试卷总结_国科大

模式试卷 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 一、模式1.什么是模式：广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 现为具有时间和空间分布的信息。2.模式的直观特性：可观察性、可区分性、相似性3.模式识别的分类：监督学习、概念驱动或归纳假说；非监督学习、数据驱动或演绎假说。4.模式分类的主要方法：数据聚类、统计分类、结构模式识别、神经网络。二、人工神经网络1.定义所谓人工神经网络就是基于模仿生物大脑的结构和功能而构成的一种信息处理系统（计算机）。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。由于我们建立的信息处理系统实际上是模仿生理神经网络，因此称它为人工神经网络。2.特点固有的并行结构和并行处理；知识的分布存储；容错性；自适应性；人工神经网络也有其局限性（不适于高精度的计算、不适于类似顺序计数的工作、学习和训练是一个艰难的过程、必须克服时间域顺序处理方面的困难、硬件限制、正确的训练数据的收集）。3.考虑因素要基于应用的要求和人工神经网络模型的能力间的匹配，主要考虑因素包括：网络大小、所需输出类型、联想记忆类型、训练方法、时间的限定。4.BP算法是有指导训练的前馈多层网络训练算法，是靠调节各层的加权，使网络学会由输入输出对组成的训练组。类似于感知器中线性单元和非线性单元的训练算法，执行优化的基本方法仍是梯度下降法。BP算法是使用非常广泛的一种算法，最常用的转移函数是Sigmoid函数。推算过程当加入第k个输入时，隐蔽层h结点的输入加权和为：kkshwihxii相应点的输出：kkkyhF(sh)F(wihxi)i同样，输出层j结点的输入加权和为：kkksjwhjyhwhjF(wihxi)hhi相应点的输出：kkkkyjF(sj)F(whjyh)F[whjF(wihxi)]hhi这里，各结点的阈值等效为一个连接的加权θ=w0h或w0j,这些连接由各结点连到具有固定值-1的偏置结点，其连接加权也是可调的，同其它加权一样参与调节过程。误差函数为：1kk21kk2E(W)(Tjyj){TjF[whjF(wihxi)]}2k,j2k,jhi为了使误差函数最小，用梯度下降法求得最优的加权，权值先从输出层开始修正，然后依次修正前层权值，因此含有反传的含义。根据梯度下降法，由隐蔽层到输出层的连接的加权调节量为：Ekkkkkkwhj(Tjyj)F(sj)yhjyhwhjkkk其中j为输出结点的误差信号：kkkkkkjF(sj)(Tjyj)F(sj)j(1)kkkjTjyj对于输入层到隐蔽层结点连接的加权修正量Δwih，必须考虑将E(W)对wih求导，因此利用分层链路法，有：EEykwh{(Tkyk)F(sk)wF(sk)xk}ihkjjjhjhiwihkyhwihk,jkkkkkjwhjF(sh)xihxik,jk其中：kkkkkhF(sh)whjjF(sh)h(2)jkkhwhjjj可以看出，式(1)和(2)具有相同的形式，所不同的是其误差值的定义，所以可定义BP算法对任意层的加权修正量的一般形式：wpqoyinvector_no_P若每加入一个训练对所有加权调节一次，则可写成：wpqoyin其中，下标o和in指相关连接的输出端点和输入端点，yin代表输入端点的实际输入，δo表示输出端点的误差，具体的含义由具体层决定，对于输出层由式(1)给出，对隐蔽层则由式(2)给出。kkkk输出层jTjyj可直接计算，于是误差值j很容易得到。对前k一隐蔽层没有直接给出目标值，不能直接计算h，而需利用输出层的来计算：kkhwhjjjk因此，算出后，h也就求出了。kkk如果前面还有隐蔽层，用h再按上述方法计算l和l，以此类推，一直将输出误差δ一层一层推算到第一隐蔽层为止。各层的δ求得后，各层的加权调节量即可按上述公式求得。由于误差相当于由输出向输入反向传播，所以这种训练算法成为误差反传算法（BP算法）。mBP训练算法实现步骤准备：训练数据组。设网络具有m层，yj0表示第m层中第j个结点的输出，yj（零层输出）等于xj，即第j个mm1m输入。wij表示从yi到yj的连接加权。这里，m代表层号，而不是向量的类号。1.将各加权随机置为小的随机数。可用均匀分布的随机数，以保证网络不被大的加权值所饱和。2.从训练数据组中选一数据对(xk,Tk)，将输入向量加到输入层（m=0），使得对所有端点i：0kyixi，k表示向量类号3.信号通过网络向前传播，即利用关系式：mmmm1yjF(sj)F(wijyi)im计算从第一层开始的各层内每个结点i的输出yj，直到输出层的每个结点的输出计算完为止。4.计算输出层每个结点的误差值（利用公式(1)）mmkmmmkmjF(sj)(Tjyj)yj(1yj)(Tjyj)（对Sigmod函数）它是由实际输出和要求目标值之差获得。5.计算前面各层各结点的误差值（利用公式(2)）m1m1mjF(sj)wjiii这里逐层计算反传误差，直到将每层内每个结点的误差值算出为止。6.利用加权修正公式mmm1wijjyi和关系newoldwijwijwij修正所有连接权。一般η=0.01~1，称为训练速率系数。7.返回第2步，为下一个输入向量重复上述步骤，直至网络收敛。三、聚类1.最近邻规则给定N个待分类的模式样本{x1,x2,…,xN}，要求按距离阈值T，将它们分类到聚类中心z1,z2,…。第一步：任取一样本xi作为一个聚类中心的初始值，例如令z1=x1计算D21=||x2-z1||若D21>T，则确定一个新的聚类中心z2=x2否则x2属于以z1为中心的聚类第二步：假设已有聚类中心z1、z2计算D31=||x3-z1||D32=||x3-z2||若D31>T且D32>T，则得一个新的聚类中心z3=x3否则x3属于离z1和z2中的最近者······如此重复下去，直至将N个模式样本分类完毕。2.最大最小距离算法10个模式样本点：{x1(00),x2(38),x3(22),x4(11),x5(53),x6(48),x7(63),x8(54),x9(64),x10(75)}第一步：选任意一个模式样本作为第一个聚类中心，如z1=x1第二步：选距离z1最远的样本作为第二个聚类中心。经计算，||x6-z1||最大，所以z2=x6第三步：逐个计算各模式样本{xi,i=1,2,…,N}与{z1,z2}之间的距离，即Di1=||xi-z1||Di2=||xi–z2||并选出其中的最小距离min(Di1,Di2)，i=1,2,…,N第四步：在所有模式样本的最小值中选出最大距离，若该最大值达到||z1-z2||的一定比例以上，则相应的样本点取为第三个聚类中心z3，即若max{min(Di1,Di2),i=1,2,…,N}>θ||z1-z2||，则z3=xi否则，若找不到适合要求的样本作为新的聚类中心，则找聚类中心的过程结束。这里，θ可用试探法取一固定分数，如1/2。在此例中，当i=7时，符合上述条件，故z3=x7第五步：若有z3存在，则计算max{min(Di1,Di2,Di3),i=1,2,…,N}。若该值超过||z1-z2||的一定比例，则存在z4，否则找聚类中心的过程结束。在此例中，无z4满足条件。第六步：将模式样本{xi,i=1,2,…,N}按最近距离分到最近的聚类中心：z1=x1：{x1,x3,x4}为第一类z2=x6：{x2,x6}为第二类z3=x7：{x5,x7,x8,x9,x10}为第三类最后，还可在每一类中计算各样本的均值，得到更具代表性的聚类中心。3.系统聚类法第一步：设初始模式样本共有N个，每个样本自成一类，即建立(0)(0)(0)N类，G1,G2,,GN。计算各类之间的距离（初始时即为各样本间的距离），得到一个N*N维的距离矩阵D(0)。这里，标号(0)表示聚类开始运算前的状态。第二步：假设前一步聚类运算中已求得距离矩阵D(n)，n为逐次聚(n)(n)类合并的次数，则求D中的最小元素。如果它是Gi和(n)(n)(n)Gj两类之间的距离，则将Gi和Gj两类合并为一类(n1)(n1)(n1)Gij，由此建立新的分类：G1,G2,。第三步：计算合并后新类别之间的距离，得D(n+1)。计算与其它没有发生合并的之间的距离，可采用多种不同的距离计算准则进行计算。第四步：返回第二步，重复计算及合并，直到得到满意的分类结果。（如：达到所需的聚类数目，或D(n)中的最小分量超过给定阈值D等。）聚类准则函数（1）最短距离法：设H和K是两个聚类，则两类间的最短距离定义为：DH,Kmin{du,v},uH,vK其中，du,v表示H类中的样本xu和K类中的样本xv之间的距离，DH,K表示H类中的所有样本和K类中的所有样本之间的最小距离。递推运算：假若K类是由I和J两类合并而成，则DH,Imin{dm,n},mH,nIDH,Kmin{DH,I,DH,J}DH,Jmin{dm,n},mH,nJ（2）最长距离法：设H和K是两个聚类，则两类间的最长距离定义为：DH,Kmax{du,v},uH,vK其中du,v的含义与上面相同。递推运算：假若K类是由I和J两类合并而成，则DH,Imax{dm,n},mH,nIDH,Kmax{DH,I,DH,J}DH,Jmax{dm,n},mH,nJ（3）中间距离法：设K类是由I和J两类合并而成，则H和K类之间的距离为：121212DH,KDH,IDH,JDI,J224它介于最长距离和最短距离之间。（4）重心法：假设I类中有nI个样本，J类中有nJ个样本，则I和J合并后共有nI+nJ个样本。用nI/(nI+nJ)和nJ/(nI+nJ)代替中间距离法中的系数，得到重心法的类间距离计算公式：nI2nJ2nInJ2DH,KDH,IDH,J2DI,JnInJnInJ(nInJ)（5）类平均距离法：若采用样本间所有距离的平均距离，则有：1Dd2H,KijnHnKiHjK递推运算公式：nI2nJ2DH,KDH,IDH,JnInJnInJ系统聚类法实例给出6个五维模式样本，按最小距离准则进行系统聚类 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 （直到分为三类为止）。x1:0,3,1,2,0x2:1,3,0,1,0x3:3,3,0,0,1x4:1,1,0,2,0x5:3,2,1,2,1x6:4,1,1,1,01.将每个样本单独看成一类，得(0)(0)(0)G1{x1}，G2{x2}，G3{x3}，(0)(0)(0)G4{x4}，G5{x5}，G6{x6}计算各类之间的距离，得距离矩阵D(0)(0)(0)(0)(0)(0)(0)G1G2G3G4G5G60(0)G230(0)G31560(0)G465130118670(0)G62114402.矩阵D(0)中最小距离元素为，它是和之间的距离，将它们合并为一类，得新的分类为(1)(0)(0)(1)(0)(1)(0)G1{G1,G2}，G2{G3}，G3{G4}，(1)(0)(1)(0)G4{G5}，G5{G6}，(1)(1)(0)(0)计算聚类后的距离矩阵D。因G1为G1和G2两类合并而成，(1)(1)按最小距离准则，可分别计算与G2~G5之间以及与~之间的两两距离，并选用其最小者。(1)(1)G3G4(1)G10(1)G260(1)G35130(1)G486701411403.矩阵D(1)中最小距离元素为，它是和之间的距离，将它们合并为一类，得新的分类为(2)(1)(2)(1)(2)(1)(2)(1)(1)G1{G1}，G2{G2}，G3{G3}，G4{G4,G5}同样，按最小距离准则计算距离矩阵D(2)(2)(2)(2)(2)G1G2G3G4(2)G10(2)G20(2)G30(2)G404.同理，得(3)(2)(2)(3)(2)(3)(2)G1{G1,G3}，G2{G2}，G3{G4}求得距离矩阵D(3)(3)(3)(3)G1G2G3(3)G10(3)G260(3)G370此时得到最终分类结果：{x1,x2,x4}、{x3}、{x5,x6}4.动态聚类算法相似性测度欧氏距离设x和z为两个模式样本，其欧氏距离定义为：D=||x-z||22例：x=(x1,x2)，z=(z1,z2)，则D(x1z1)(x2z2)显然，模式x和z之间的距离越小，它们越相似。欧氏距离的概念和习惯上距离的概念是一致的。马氏距离设x是模式向量，m是均值向量，C为模式总体的协方差矩阵，则马氏距离的表达式：D2(xm)TC1(xm)一般化的明氏距离模式样本向量xi和xj之间的明氏距离表示为：1/mmDm(xi,xj)(xikxjk)k其中xik和xjk分别表示xi和xj的第k各分量。显然，当m=2时，明氏距离即为欧氏距离。特例：当时，，亦称为街坊距离。m=1D1(xi,xj)|xikxjk|k角度相似性函数xTz表达式：S(x,z)，它表示模式向量x和z之间夹角的余弦，xz也称为x的单位向量与z的单位向量之间的点积。特例：当特征的取值仅为(0,1)两个值时，夹角余弦度量具有特别的含义，即当模式的第i个分量为1时，认为该模式具有第i个特征；当模式的第i个分量为0时，认为该模式无此特征。这时，xTz的值就等于x和z这两个向量共同具有的特征数目。同时，xz(xTx)(zTz)={x中具有的特征数目和z中具有的特征数目的几何平均}因此，在特征取值为0和1的二值情况下，S(x,z)等于x和z中具有的共同特征数目的相似性测度。K-均值算法第一步：选K个初始聚类中心，z1(1)，z2(1)，…，zK(1)，其中括号内的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。第二步：逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个zj(1)。假设i=j时，Dj(k)min{xzi(k),i1,2,K}，则xSj(k)，其中k为迭代运算的次序号，第一次迭代k=1，Sj表示第j个聚类，其聚类中心为zj。第三步：计算各个聚类中心的新的向量值，zj(k+1)，j=1,2,…,K求各聚类域中所包含样本的均值向量：1zj(k1)x,j1,2,,KNjxSj(k)其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：2Jjxzj(k1),j1,2,,KxSj(k)在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。z(k1)z(k)第四步：若jj，j=1,2,…,K，则返回第二步，将模式样本逐个重新分类，重复迭代运算；z(k1)z(k)若jj，j=1,2,…,K，则算法收敛，计算结束。K-均值分类算法实例第一步：取K=2，并选Tz1(1)=x1=(00)Tz2(1)=x2=(10)第二步：因x1z1(1)x1z2(1)，故x1S1(1)因x2z1(1)x2z2(1)，故x2S2(1)因x3z1(1)x3z2(1)，故x3S1(1)……得到：S1(1)={x1,x3}S2(1)={x2,x4,x5,…,x20}第三步：计算新的聚类中心110.0z(2)x(xx)1N2130.51xS1(1)115.67z(2)x(xxx)2N1824205.332xS2(1)z(2)z(1)第四步：因jj，j=1,2，返回第二步；第二步（返回1）：由新的聚类中心，得到：xz(2)xz(2),l1,2,,8l1l2xz(2)xz(2),l9,10,,20l1l2因此S1(2)={x1,x2,…,x8}S2(2)={x9,x10,…,x20}第三步（返回1）：计算聚类中心111.25z(3)x(xxx)1N81281.131xS1(2)117.67z(3)x(xxx)2N12910207.332xS2(2)z(3)z(2)第四步（返回1）：因jj，j=1,2，返回第二步；第二步（返回2）：分类结果与前一次迭代的结果相同，即S1(4)=S1(3)，S2(4)=S2(3)；第三步（返回2）：聚类中心与前一次迭代的结果相同；z(4)z(3)第四步（返回2）：因jj，j=1,2，算法收敛，得到最终的聚类中心。1.257.67z1z21.137.33ISODATA算法第一步：输入N个模式样本{xi,i=1,2,…,N}预选个初始聚类中心{z,z,z}，它可以不等于Nc12Nc所要求的聚类中心的数目，其初始位置可以从样本中任意选取。预选：K=预期的聚类中心数目；θN=每一聚类域中最少的样本数目，若少于此数即不作为一个独立的聚类；θS=一个聚类域中样本距离分布的标准差；θc=两个聚类中心间的最小距离，若小于此数，两个聚类需进行合并；L=在一次迭代运算中可以合并的聚类中心的最多对数；I=迭代运算的次数。第二步：将N个模式样本分给最近的聚类Sj，假若Djmin{xzi,i1,2,Nc}，即||x-zj||的距离最小，则xSj。第三步：如果Sj中的样本数目Sj<θN，则取消该样本子集，此时Nc减去1。（以上各步对应基本步骤（1））第四步：修正各聚类中心1zjx,j1,2,,NcNjxSj第五步：计算各聚类域Sj中模式样本与各聚类中心间的平均距离1Djxzj,j1,2,,NcNjxSj第六步：计算全部模式样本和其对应聚类中心的总平均距离1NDNjDjNj1（以上各步对应基本步骤（2））第七步：判别分裂、合并及迭代运算1.若迭代运算次数已达到I次，即最后一次迭代，则置θc=0，转至第十一步。K2.若N，即聚类中心的数目小于或等于规定值的一半，则转c2至第八步，对已有聚类进行分裂处理。3.若迭代运算的次数是偶数次，或Nc2K，不进行分裂处理，转至第十一步；否则（即既不是偶数次迭代，又不满足），转至第八步，进行分裂处理。（以上对应基本步骤（3））第八步：计算每个聚类中样本距离的标准差向量Tj(1j,2j,,nj)其中向量的各个分量为Nj12ij(xikzij)Njk1式中，i=1,2,…,n为样本特征向量的维数，j=1,2,…,Nc为聚类数，Nj为Sj中的样本个数。第九步：求每一标准差向量{σj,j=1,2,…,Nc}中的最大分量，以{σjmax,j=1,2,…,Nc}代表。第十步：在任一最大分量集{σjmax,j=1,2,…,Nc}中，若有σjmax>θS，同时又满足如下两个条件之一：1.DjD和Nj>2(θN+1)，即Sj中样本总数超过规定值一倍以上，K2.Nc2则将zj分裂为两个新的聚类中心zj和zj，且Nc加1。zj中对应于σjmax的分量加上kσjmax，其中0k1；中对应于σjmax的分量减去kσjmax。如果本步骤完成了分裂运算，则转至第二步，否则继续。（以上对应基本步骤（4）进行分裂处理）第十一步：计算全部聚类中心的距离Dij=||zi-zj||，i=1,2,…,Nc-1，j=i+1,…,Nc。第十二步：比较Dij与θc的值，将Dij<θc的值按最小距离次序递增排列，即{D,D,,D}i1j1i2j2iLjL式中，DDD。i1j1i2j2iLjL第十三步：将距离为D的两个聚类中心z和z合并，得新的ikjkikjk中心为：*1zk[NiziNjzj]，k=1,2,…,LNNkkkkikjk式中，被合并的两个聚类中心向量分别以其聚类域内*的样本数加权，使zk为真正的平均向量。（以上对应基本步骤（5）进行合并处理）第十四步：如果是最后一次迭代运算（即第I次），则算法结束；否则，若需要操作者改变输入参数，转至第一步；若输入参数不变，转至第二步。在本步运算中，迭代运算的次数每次应加1。ISODATA算法实例此例中N=8，n=2。假设取初始值TNc=1，z1(1)=x1=(00)，则运算步骤如下：第一步：取K=2，θN=1，θS=1，θc=4，L=1，I=4预选：K=预期的聚类中心数目；θN=每一聚类域中最少的样本数目，若少于此数即不作为一个独立的聚类；θS=一个聚类域中样本距离分布的标准差；θc=两个聚类中心间的最小距离，若小于此数，两个聚类需进行合并；L=在一次迭代运算中可以合并的聚类中心的最多对数；I=迭代运算的次数。第二步：因只有一个聚类中心，因此S1={x1,x2,…,x8}，N1=8。第三步：因N1>θN，无子集可抛。第四步：修改聚类中心13.38z1xN2.751xS1第五步：计算模式样本与聚类中心间的平均距离Dj1D1xz12.26N1xS1第六步：计算全部模式样本和其对应聚类中心的总平均距离DDD12.26第七步：因不是最后一次迭代，且Nc=K/2，进入第八步第八步：计算S1中的标准差向量1.9911.56第九步：σ1中的最大分量是1.99，因此σ1max=1.99。第十步：因σ1max>θS且Nc=K/2，可将z1分裂成两个新的聚类。设rj0.51max1.0，则4.38z12.752.38z12.75zz为方便起见，将1和1表示为z1和z2，Nc加1，返回第二步。第二步（返回1）：新的样本集为S1={x4,x5,…,x8}，N1=5S2={x1,x2,x3}，N2=3第三步（返回1）：因N1>θN且N2>θN，无子集可抛。第四步（返回1）：修改聚类中心14.80z1xN3.801xS111.00z2xN1.002xS2第五步（返回1）：计算模式样本与聚类中心间的平均距离Dj，j=1,21D1xz10.80N1xS11D2xz20.94N2xS2第六步（返回1）：计算全部模式样本和其对应聚类中心的总平均距离D1N12DNjDjNjDj0.85Nj18j1第七步（返回1）：因是偶数次迭代，满足第七步的条件3，进入第十一步第十一步：计算聚类对之间的距离D12z1z24.72第十二步：比较D12与θc，D12>θc第十三步：从上一步结果看出，聚类中心不发生合并。第十四步：因不是最后一次迭代运算，判断是否需要修改给定的参数。（1）已获得所要求的聚类数目；（2）聚类之间的分离度大于类内样本分离的标准差；（3）每一聚类子集的样本数目都具有样本总数中足够大的比例。因此，可认为聚类中心具有代表性，返回第二步。第二~六步（返回2）：与上一次迭代计算结果相同。第七步（返回2）：没有一种情况可满足，进入第八步。第八步（返回2）：计算S1={x4,x5,…,x8}和S2={x1,x2,x3}的标准差0.7510.750.8220.82第九步（返回2）：σ1max=0.75，σ2max=0.82第十步（返回2）：分裂条件不满足，进入第十一步。第十一步（返回2）：与上一次迭代的结果相同，计算得到D12z1z24.72第十二、十三步（返回2）：与上一次迭代的结果相同。第十四步（返回2）：无新的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 加入本次迭代中，返回第二步。第二~六步（返回3）：与上一次迭代计算结果相同。第七步（返回3）：因是最后一次迭代，置θc=0，转至第十一步。第十一步（返回3）：同上一次迭代，D12z1z24.72第十二步（返回3）：与上一次迭代的结果相同。第十三步（返回3）：无合并发生。第十四步（返回3）：最后一次迭代，算法结束。四、判别函数1.概念两类问题的判别函数（以二维模式样本为例）T若x是二维模式样本x=(x1x2)，用x1和x2作为坐标分量，得到模式的平面图：这时，若这些分属于ω1和ω2两类的模式可用一个直线方程d(x)=0来划分d(x)=w1x1+w2x2+w3=0其中x1、x2为坐标变量，w1、w2、w3为参数方程，则将一个不知类别的模式代入d(x)，有-若d(x)>0，则x1-若d(x)<0，则x2此时，d(x)=0称为判别函数。推广到n维模式，线性判别函数的一般形式则为tD(x)=w1x1+w2x2+…wnxn+wn+1=w0x+wn+1其中，xi为一次。如果一训练用模式集｛x｝，在模式空间x中线性不可分，而在x*空间中才线性可分，且x*的各个分量是x的单值函数，它的维数k高于x的维数n，即*tx=(f1(x)f2(x)…fn(x))，k>n则分类界面在x*空间是线性的，在x空间是非线性的，这里称d(x*)=0为广义的线性判别函数。2.为什么需要非线性判别函数？实际工作中常靠已知类别的训练模式样本来确定判别函数，用该判别函数构成的分类器对未知的模式进行分类。显然，训练用模式的数目不可能太多，但待分类的未知模式却往往无穷无尽。若训练模式的数目低于Ck，则由它确定的判别函数函数却被用来判别数目远远超过Ck的模式，这样，线性二分能力就迅速下降，发生错分的情况亦就大为增加。由于样本在特征空间分布的复杂性，许多情况下采用线性判别函数不能取得满意的分类效果。另外在数情况下样本分布及合适子类划分并不知道，则往往需要采用一种聚类的方法，设法样本划分成相对密集的子类，然后用各种方法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 各种线性判别函数。例题：两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。）根据线性判别函数的一般形式dxw11xw221xwxnnwn由于该模式为两类模式，分布良好，维数为3，且它们是线性可分的，则权向量至少需要4个系数分量。根据r次多项式判别函数的一般形式以及仍在上述条件下，若要建立二次的r2多项式判别函数，则至少需要CCnr3210个系数分量。222dxw11x1w22x2w33x3wxxwxxwxx121213132323w1x1w2x2w3x3w43.势函数用下列势函数求解以下模式的分类问题−α‖푥−x푘‖K(x,푥푘)=푒TTTTω1:{(01),(0-1)}ω2:{(10),(-10)}选择指数型势函数，取α=1，在二维情况下势函数为2[(xx)2(xx)2]xxk1k12k2K(x,xk)eeTT这里：ω1类为x①=(00),x②=(20)TTω2类为x③=(11),x④=(1-1)可以看出，这两类模式是线性不可分的。算法步骤如下：T第一步：取x①=(00)∈ω1，则2222[(x10)(x20)](x1x2)K1(x)=K(x,x①)=eeT第二步：取x②=(20)∈ω1-(4+0)-4因K1(x②)=e=e>0，22(x1x2)故K2(x)=K1(x)=eT第三步：取x③=(11)∈ω2-(1+1)-2因K2(x③)=e=e>0，2222(x1x2)[(x11)(x21)]故K3(x)=K2(x)-K(x,x③)=eeT第四步：取x④=(1-1)∈ω2-(1+1)-(0+4)-2-4因K3(x④)=e-e=e-e>0，故K4(x)=K3(x)-K(x,x④)222222=e(x1x2)e[(x11)(x21)]e[(x11)(x21)]需对全部训练样本重复迭代一次T0-2-2-2第五步：取x⑤=x①=(00)∈ω1，K4(x⑤)=e-e-e=1-2e>0故K5(x)=K4(x)T-4-2-2-4-2第六步：取x⑥=x②=(20)∈ω1，K5(x⑥)=e-e-e=e-2e<0故K6(x)=K5(x)+K(x,x⑥)22222222=e(x1x2)e[(x11)(x21)]e[(x11)(x21)]e[(x12)x2]T-20-4-2-2-4第七步：取x⑦=x③=(11)∈ω2，K6(x⑦)=e-e-e+e=2e-e-1<0故K7(x)=K6(x)T-2-40-2-2-4第八步：取x⑧=x④=(1-1)∈ω2，K7(x⑧)=e-e-e+e=2e-e-1<0故K8(x)=K7(x)T0-2-2-4-4-2第九步：取x⑨=x①=(00)∈ω1，K8(x⑨)=e-e-e+e=1+e-2e>0故K9(x)=K8(x)T-4-2-20-4-2第十步：取x⑩=x②=(20)∈ω1，K9(x⑩)=e-e-e+e=1+e-2e>0故K10(x)=K9(x)经过上述迭代，全部模式都已正确分类，因此算法收敛于判别函数22222222(x1x2)[(x11)(x21)][(x11)(x21)][(x12)x2]d(x)eeee五、贝叶斯1.最小错误概率判别根据一个事物后验概率最大作为分类依据的决策。p(x|1)P(2)若l12(x)，则x1p(x|2)P(1)p(x|1)P(2)若l12(x)，则x2p(x|2)P(1)其中，l12称为似然比，P(ω2)/P(ω1)=θ21称为似然比的判决阈值，此判别称为贝叶斯判别。2.最小风险判别按贝叶斯公式，最小平均条件风险可写成：1Mrj(x)Lijp(x|i)P(i)p(x)i1因1/p(x)为公共项，可舍去，因此可简化为：Mrj(x)Lijp(x|i)P(i)i1这也是贝叶斯分类器，只是它的判别方法不是按错误概率最小作为标准，而是按平均条件风险作为标准。选M=2，即全部的模式样本只有ω1和ω2两类，要求分类器将模式样本分到ω1和ω2两类中，则平均风险可写成：当分类器将x判别为ω1时：r1(x)L11p(x|1)P(1)L21p(x|2)P(2)当分类器将x判别为ω2时：r2(x)L12p(x|1)P(1)L22p(x|2)P(2)若r1(x)Lii，有：p(x|1)P(2)L21L22当时，x1p(x|2)P(1)L12L11p(x|1)该式左边为似然比：l12p(x|2)P(2)L21L22右边为阈值：21P(1)L12L11故得两类模式的贝叶斯判别条件为：（1）若l12(x)>θ21，则x1（2）若l12(x)<θ21，则x2（3）若l12(x)=θ21，则可做任意判别。通常，当判别正确时，不失分，可选常数L11=L22=0；判别错误P(2)时，可选L12=L21=1，此时21。P(1)六、K－L变换1Ni1Nimx1jx2j05j15j1255T11T11T25.425.0RP(i)E{xx}x1jx1jx2jx2ji125j125j125.025.4解特征值方程|R-λI|=0，求R的特征值。22由(25.4-λ)-25.0=0，得特征值λ1=50.4，λ2=0.4其对应的特征向量可由RФi=λiФi求得：1111，122121T选λ1对应的变换向量作为变换矩阵，由y=Фx得变换后的一维模式特征为：10991111101111991:,,,,2:,,,,2222222222七、句法模式识别1.框图2.原理统计模式识别是基于模式特征的一组测量值来组成特征向量，用决策理论划分特征空间的方法进行分类。基于描述模式的结构信息，用形式语言中的规则进行分类，可以更典型地应用于景物图片的分析。因为在这类问题中，所研究的模式通常十分复杂，需要的特征也很多，仅用数值上的特征不足以反映它们的类别。3.有限态自动机确定正则文法举例设一有限态自动机A=({0,1},{q0,q1,q2},δ,q0,{q2})，δ定义如下：δ(q0,0)=q2，δ(q1,0)=q2，δ(q2,0)=q2，δ(q0,1)=q1，δ(q1,1)=q0，δ(q2,1)=q1试求等价的正则文法，使得L(G)=T(A)设由A得一正则文法G=(VN,VT,P,S)，则VN={S,x1,x2}，VT={0,1}，S=q0由δ(q0,1)=q1，得生成式S->1x1由δ(q1,1)=q0，得生成式x1->1S由δ(q2,1)=q1，得生成式x2->1x1由δ(q0,0)=q2，得生成式S->0，S->0x2由δ(q1,0)=q2，得生成式x1->0，x1->0x2由δ(q2,0)=q2，得生成式x2->0，x2->0x2对比实例：当扫描字符串1110时，A按以下状态序列接受该字符串1110q0q1q0q1q2用对应的正则文法G推导，得：S=>1x1=>11S=>111x1=>1110