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

模式试卷总结模式试卷总结 一、一、 模式模式 1.什么是模式：广义地说，存在于时间和空间中可观察的物体，如果我们可以区 别它们是否相同或是否相似，都可以称之为模式。 模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有 时间和空间分布的信息。 2.模式的直观特性：可观察性、可区分性、相似性 3.模式识别的分类：监督学习、概念驱动或归纳假说；非监督学习、数据驱动或 演绎假说。 4.模式分类的主要方法：数据聚类、统计分类、结构模式识别、神经网络。 二二、人工神经网络人工神经网络 1. 1.定义定义 所谓人工神经网络就是基于模仿生物大脑的结构和功能而构成的一种信息 处理系统（计算机） 。这种网络依靠系统的复杂程度，通过调整内部大量节点之 间相互连接的关系，从而达到处理信息的目的。由于我们建立的信息处理系统实 际上是模仿生理神经网络，因此称它为人工神经网络。 2. 2.特点特点 固有的并行结构和并行处理；知识的分布存储；容错性；自适应性；人工神 经网络也有其局限性（不适于高精度的计算、不适于类似顺序计数的工作、学习 和训练是一个艰难的过程、必须克服时间域顺序处理方面的困难、硬件限制、正 确的训练数据的收集） 。 3. 3.考虑因素考虑因素 要基于应用的要求和人工神经网络模型的能力间的匹配，主要考虑因素包括： 网络大小、所需输出类型、联想记忆类型、训练方法、时间的限定。 4. 4.BPBP 算法算法 是有指导训练的前馈多层网络训练算法，是靠调节各层的加权，使网络学会由输 入输出对组成的训练组。类似于感知器中线性单元和非线性单元的训练算法，执 行优化的基本方法仍是梯度下降法。BP 算法是使用非常广泛的一种算法，最常 用的转移函数是 Sigmoid 函数。 推算过程推算过程 当加入第 k 个输入时，隐蔽层 h 结点的输入加权和为： i k iih k h xws 相应点的输出： )xw(F)s (Fy i k iih k h k h 同样，输出层 j 结点的输入加权和为： hi k iihhj h k hhj k j )xw(Fwyws 相应点的输出： )xw(FwF)yw(F)s (Fy hi k iihhj h k hhj k j k j 这里，各结点的阈值等效为一个连接的加权= w0h或 w0j,这些连 接由各结点连到具有固定值-1 的偏置结点，其连接加权也是可调 的，同其它加权一样参与调节过程。 误差函数为： jkhi k iihhj k j jk k j k j xwFwFTyTWE , 2 , 2 )( 2 1 )( 2 1 )( 为了使误差函数最小，用梯度下降法求得最优的加权，权值先从 输出层开始修正，然后依次修正前层权值，因此含有反传的含义。 根据梯度下降法，由隐蔽层到输出层的连接的加权调节量为： k k h k j k k h k j k j k j hj hj yy)s (F)yT( w E w 其中 k j 为输出结点的误差信号： k j k j k j k j k j k j )s (F)yT)(s (F (1) k j k j k j yT 对于输入层到隐蔽层结点连接的加权修正量wih，必须考虑将 E(W)对 wih求导，因此利用分层链路法，有： k k i k h j ,k k i k hhj k j j ,k k i k hhj k j k j k j ih k h k k hih ih xx)s (Fw x)s (Fw)s (F)yT( w y y E w E w 其中： k h k h j k jhj k h k h )s (Fw)s (F (2) j k jhj k h w 可以看出，式(1)和(2)具有相同的形式，所不同的是其误差值的 定义，所以可定义 BP 算法对任意层的加权修正量的一般形式： P_no_vector inopq yw 若每加入一个训练对所有加权调节一次，则可写成： inopq yw 其中，下标 o 和 in 指相关连接的输出端点和输入端点，yin代表输入 端点的实际输入，o表示输出端点的误差，具体的含义由具体层决 定，对于输出层由式(1)给出，对隐蔽层则由式(2)给出。 输出层 k j k j k j yT 可直接计算，于是误差值 k j 很容易得到。对前 一隐蔽层没有直接给出目标值，不能直接计算 k h ，而需利用输出层 的 k j 来计算： j k jhj k h w 因此，算出 k h 后， k h 也就求出了。 如果前面还有隐蔽层，用 k h 再按上述方法计算 k l 和 k l ，以此类 推，一直将输出误差一层一层推算到第一隐蔽层为止。各层的 求得后，各层的加权调节量即可按上述公式求得。由于误差 k j 相当 于由输出向输入反向传播，所以这种训练算法成为误差反传算法 （BP 算法） 。 BP 训练算法实现步骤训练算法实现步骤准备：训练数据组。设网络具有 m 层， m j y 表示第 m 层中第 j 个结点的输出， 0 j y（零层输出）等于 xj，即第 j 个 输入。 m ij w表示从 1m i y 到 m j y的连接加权。这里，m 代表层号，而不是 向量的类号。 1. 将各加权随机置为小的随机数。可用均匀分布的随机数，以 保证网络不被大的加权值所饱和。 2. 从训练数据组中选一数据对(xk, Tk)，将输入向量加到输入层 （m=0） ，使得对所有端点 i： k i 0 i xy ，k 表示向量类号 3. 信号通过网络向前传播，即利用关系式： )yw(F)s (Fy i 1m i m ij m j m j 计算从第一层开始的各层内每个结点 i 的输出 m j y，直到输出 层的每个结点的输出计算完为止。 4. 计算输出层每个结点的误差值（利用公式(1)） )yT)(y1 (y)yT)(s (F m j k j m j m j m j k j m j m j （对 Sigmod 函 数） 它是由实际输出和要求目标值之差获得。 5. 计算前面各层各结点的误差值（利用公式(2)） i m iji 1m j 1m j w)s (F 这里逐层计算反传误差，直到将每层内每个结点的误差值算出为 止。 6. 利用加权修正公式 1m i m j m ij yw 和关系 ij old ij new ij www 修正所有连接权。一般= 0.011，称为训练速率系数。 7. 返回第 2 步，为下一个输入向量重复上述步骤，直至网络收 敛。 三三、聚类、聚类 1. 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. 2.最大最小距离算法最大最小距离算法 10 个模式样本点：x1(0 0), x2(3 8), x3(2 2), x4(1 1), x5(5 3), x6(4 8), x7(6 3), x8(5 4), x9(6 4), x10(7 5) 第一步：选任意一个模式样本作为第一个聚类中心，如 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，即 若 maxmin(Di1, Di2), i = 1,2,N |z1 - z2 |，则 z3 = xi 否则， 若找不到适合要求的样本作为新的聚类中心， 则 找聚类中心的过程结束。 这里，可用试探法取一固定分数，如 1/2。 在此例中，当 i=7 时，符合上述条件，故 z3 = x7 第五步： 若有 z3存在，则计算 maxmin(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 3. .系统聚类法系统聚类法 第一步：设初始模式样本共有 N 个，每个样本自成一类，即建立 N 类， )0()0( 2 )0( 1 , N GGG 。计算各类之间的距离（初始时 即为各样本间的距离） ， 得到一个N*N维的距离矩阵D(0)。 这里，标号(0)表示聚类开始运算前的状态。 第二步：假设前一步聚类运算中已求得距离矩阵 D(n)，n 为逐次聚 类合并的次数，则求 D(n)中的最小元素。如果它是 Gi(n)和 Gj(n)两类之间的距离，则将 Gi(n)和 Gj(n)两类合并为一类 )1n( ij G ，由此建立新的分类：,G,G )1n( 2 )1n( 1 。 第三步：计算合并后新类别之间的距离，得 D(n+1)。 计算 )1n( ij G 与其它没有发生合并的,G,G )1n( 2 )1n( 1 之间 的距离，可采用多种不同的距离计算准则进行计算。 第四步：返回第二步，重复计算及合并，直到得到满意的分类结 果。 （如：达到所需的聚类数目，或 D(n)中的最小分量超过给定阈值 D 等。 ） 聚类准则函数聚类准则函数 （1） 最短距离法：设 H 和 K 是两个聚类，则两类间的最短距离定义 为： Kv,Hu,dminD v,uK,H 其中， du,v表示 H 类中的样本 xu和 K 类中的样本 xv之间的距离， DH,K表示 H 类中的所有样本和 K 类中的所有样本之间的最小距 离。 递推运算：假若 K 类是由 I 和 J 两类合并而成，则 ,min ,min ,min , , , JHIHKH nmJH nmIH DDD JnHmdD InHmdD （2） 最长距离法：设 H 和 K 是两个聚类，则两类间的最长距离定义 为： Kv,Hu,dmaxD v,uK,H 其中 du,v的含义与上面相同。 递推运算：假若 K 类是由 I 和 J 两类合并而成，则 ,max ,max ,max , , , JHIHKH nmJH nmIH DDD JnHmdD InHmdD （3） 中间距离法：设 K 类是由 I 和 J 两类合并而成，则 H 和 K 类之 间的距离为： 2 J , I 2 J ,H 2 I ,HK,H D 4 1 D 2 1 D 2 1 D 它介于最长距离和最短距离之间。 （4） 重心法：假设 I 类中有 nI个样本，J 类中有 nJ个样本，则 I 和 J 合并后共有 nI+nJ个样本。用 nI/(nI+nJ)和 nJ/(nI+nJ)代替中间距离 法中的系数，得到重心法的类间距离计算公式： 2 J , I 2 JI JI 2 J ,H JI J 2 I ,H JI I K,H D )nn( nn D nn n D nn n D （5） 类平均距离法：若采用样本间所有距离的平均距离，则有： Kj Hi 2 ij KH K,H d nn 1 D 递推运算公式： 2 J ,H JI J 2 I ,H JI I K,H D nn n D nn n D 系统聚类法实例系统聚类法实例 给出 6 个五维模式样本，按最小距离准则进行系统聚类分析（直 到分为三类为止） 。 x1: 0, 3, 1, 2, 0 x2: 1, 3, 0, 1, 0 x3: 3, 3, 0, 0, 1 x4: 1, 1, 0, 2, 0 x5: 3, 2, 1, 2, 1 x6: 4, 1, 1, 1, 0 1. 将每个样本单独看成一类，得 1 )0( 1 xG， 2 )0( 2 xG， 3 )0( 3 xG， 4 )0( 4 xG， 5 )0( 5 xG， 6 )0( 6 xG 计算各类之间的距离，得距离矩阵 D(0) )0( 1 G )0( 2 G )0( 3 G )0( 4 G )0( 5 G )0( 6 G )0( 1 G 0 )0( 2 G 3 0 )0( 3 G 15 6 0 )0( 4 G 6 5 13 0 )0( 5 G 11 8 6 7 0 )0( 6 G 21 14 8 11 4 0 2. 矩阵 D(0)中最小距离元素为3，它是 )0( 1 G和 )0( 2 G之间的距离， 将它们合并为一类，得新的分类为 , )0( 2 )0( 1 )1( 1 GGG， )0( 3 )1( 2 GG， )0( 4 )1( 3 GG， )0( 5 )1( 4 GG， )0( 6 )1( 5 GG， 计算聚类后的距离矩阵 D(1)。 因 )1( 1 G为 )0( 1 G和 )0( 2 G两类合并而成， 按最小距离准则，可分别计算 )0( 1 G与 )1( 2 G )1( 5 G之间以及 )0( 2 G与 )1( 2 G )1( 5 G 之间的两两距离，并选用其最小者。 )1( 1 G )1( 2 G )1( 3 G )1( 4 G )1( 5 G )1( 1 G 0 )1( 2 G 6 0 )1( 3 G 5 13 0 )1( 4 G 8 6 7 0 )1( 5 G 14 8 11 4 0 3. 矩阵 D(1)中最小距离元素为4， 它是 )1( 4 G和 )1( 5 G之间的距离， 将 它们合并为一类，得新的分类为 )1( 1 )2( 1 GG， )1( 2 )2( 2 GG， )1( 3 )2( 3 GG，, )1( 5 )1( 4 )2( 4 GGG 同样，按最小距离准则计算距离矩阵 D(2) )2( 1 G )2( 2 G )2( 3 G )2( 4 G )2( 1 G 0 )2( 2 G 6 0 )2( 3 G 5 13 0 )2( 4 G 8 6 7 0 4. 同理，得 , )2( 3 )2( 1 )3( 1 GGG， )2( 2 )3( 2 GG， )2( 4 )3( 3 GG 求得距离矩阵 D(3) )3( 1 G )3( 2 G )3( 3 G )3( 1 G 0 )3( 2 G 6 0 )3( 3 G 7 6 0 此时得到最终分类结果：x1, x2, x4、x3、x5, x6 4. 4.动态聚类算法动态聚类算法 相似性测度相似性测度 欧氏距离 设 x 和 z 为两个模式样本，其欧氏距离定义为：D = | x - z | 例：x = (x1, x2)，z = (z1, z2)，则 2 22 2 11 )zx()zx(D 显然，模式 x 和 z 之间的距离越小，它们越相似。欧氏距离的概 念和习惯上距离的概念是一致的。 马氏距离 设 x 是模式向量，m 是均值向量，C 为模式总体的协方差矩阵， 则马氏距离的表达式： )mx(C)mx(D 1T2 一般化的明氏距离 模式样本向量 xi和 xj之间的明氏距离表示为： m/1 k m jkikjim )xx()x,x(D 其中 xik和 xjk分别表示 xi和 xj的第 k 各分量。 显然，当 m=2 时，明氏距离即为欧氏距离。 特例：当 m=1 时，|xx |)x,x(D jkik k ji1 ，亦称为街坊距离。 角度相似性函数 表达式： zx zx )z, x(S T ，它表示模式向量 x 和 z 之间夹角的余弦， 也称为 x 的单位向量与 z 的单位向量之间的点积。 特例：当特征的取值仅为(0, 1)两个值时，夹角余弦度量具有特别 的含义， 即当模式的第 i 个分量为 1 时， 认为该模式具有第 i 个特征； 当模式的第 i 个分量为 0 时，认为该模式无此特征。这时，xTz 的值就 等于 x 和 z 这两个向量共同具有的特征数目。同时， )zz)(xx(zx TT = x 中具有的特征数目和 z 中具有的特征数目 的几何平均 因此，在特征取值为 0 和 1 的二值情况下，S(x, z)等于 x 和 z 中具有 的共同特征数目的相似性测度。 K-均值算法均值算法 第一步：选 K 个初始聚类中心，z1(1)，z2(1)，zK(1)，其中括号 内的序号为寻找聚类中心的迭代运算的次序号。聚类中 心的向量值可任意设定，例如可选开始的 K 个模式样本 的向量值作为初始聚类中心。 第二步：逐个将需分类的模式样本x按最小距离准则分配给 K 个 聚类中心中的某一个 zj(1)。 假设 i=j 时，K, 2 , 1i ,)k(zxmin)k(D ij ，则 )k(Sx j ， 其中k为迭代运算的次序号， 第一次迭代k=1， Sj表示第 j 个聚类，其聚类中心为 zj。 第三步：计算各个聚类中心的新的向量值，zj(k+1)，j=1,2,K 求各聚类域中所包含样本的均值向量： K, 2 , 1j, x N 1 ) 1k(z )k(Sx j j j 其中 Nj为第 j 个聚类域 Sj中所包含的样本个数。以均值 向量作为新的聚类中心，可使如下聚类准则函数最小： K, 2 , 1j,) 1k(zxJ )k(Sx 2 jj j 在这一步中要分别计算 K 个聚类中的样本均值向量，所 以称之为 K-均值算法。 第四步：若 )k(z) 1k(z jj ，j=1,2,K，则返回第二步，将模式样 本逐个重新分类，重复迭代运算； 若 )k(z) 1k(z jj ，j=1,2,K，则算法收敛，计算结束。 K-均值分类算法实例均值分类算法实例 第一步：取 K=2，并选 z1(1)=x1=(0 0)T z2(1)=x2=(1 0)T 第二步：因) 1 () 1 ( 2111 zxzx，故 ) 1 ( 11 Sx 因) 1 () 1 ( 2212 zxzx，故) 1 ( 22 Sx 因) 1 () 1 ( 2313 zxzx，故) 1 ( 13 Sx 得到： S1(1)=x1, x3 S2(1)=x2, x4, x5, , x20 第三步：计算新的聚类中心 )1( 31 1 1 1 5 . 0 0 . 0 )( 2 11 )2( Sx xxx N z )1( 2042 2 2 2 33. 5 67. 5 )( 18 11 )2( Sx xxxx N z 第四步：因 ) 1 ()2( jj zz ，j=1,2，返回第二步； 第二步（返回 1） ：由新的聚类中心，得到： 8 , 2 , 1,)2()2( 21 lzxzx ll 20,10, 9,)2()2( 21 lzxzx ll 因此 S1(2)=x1, x2, , x8 S2(2)=x9, x10, , x20 第三步（返回 1） ：计算聚类中心 )2( 821 1 1 1 13. 1 25. 1 )( 8 11 )3( Sx xxxx N z )2( 20109 2 2 2 33. 7 67. 7 )( 12 11 )3( Sx xxxx N z 第四步（返回 1） ：因 )2()3( jj zz ，j=1,2，返回第二步； 第二步 （返回 2） ： 分类结果与前一次迭代的结果相同， 即 S1(4)=S1(3)， S2(4)= S2(3)； 第三步（返回 2） ：聚类中心与前一次迭代的结果相同； 第四步（返回 2） ：因 )3()4( jj zz ，j=1,2，算法收敛，得到最终的聚 类中心。 13. 1 25. 1 1 z 33. 7 67. 7 2 z ISODATA 算法算法 第一步：输入 N 个模式样本xi, i = 1, 2, , N 预选 Nc个初始聚类中心 z,z,z c N21 ，它可以不等于 所要求的聚类中心的数目，其初始位置可以从样本中任 意选取。 预选：K = 预期的聚类中心数目； N = 每一聚类域中最少的样本数目，若少于此 数即不作为一个独立的聚类； S = 一个聚类域中样本距离分布的标准差； c = 两个聚类中心间的最小距离，若小于此数， 两个聚类需进行合并； L = 在一次迭代运算中可以合并的聚类中心的 最多对数； I = 迭代运算的次数。 第 二 步 ： 将 N 个 模 式 样 本 分 给 最 近 的 聚 类 Sj， 假 若 N, 2 , 1i ,zxm i n D cij ， 即|x-zj|的距离最小， 则 j Sx 。 第三步：如果 Sj中的样本数目 Sj S ，同时又满足如下两个条件之一： 1. DDj和 Nj 2(N + 1)，即 Sj中样本总数超过规定 值一倍以上， 2. 2 K Nc 则将 zj 分裂为两个新的聚类中心 j z和 j z，且 Nc加 1。 j z中对应于jmax的分量加上 kjmax，其中1k0； j z 中对应于jmax的分量减去 kjmax。 如果本步骤完成了分裂运算， 则转至第二步， 否则继续。 （以上对应基本步骤（4）进行分裂处理） 第十一步：计算全部聚类中心的距离 Dij = | zi - zj |，i = 1, 2, , Nc-1 ，j =i+1, , Nc。 第十二步：比较 Dij 与c 的值，将 Dij N ，无子集可抛。 第四步：修改聚类中心 1 75. 2 38. 3 1 1 1 Sx x N z 第五步：计算模式样本与聚类中心间的平均距离 j D 26. 2 1 1 1 1 1 Sx zx N D 第六步：计算全部模式样本和其对应聚类中心的总平均距离D 26. 2 1 DD 第七步：因不是最后一次迭代，且 Nc=K/2，进入第八步 第八步：计算 S1中的标准差向量 56. 1 99. 1 1 第九步：1中的最大分量是 1.99，因此1max = 1.99。 第十步：因1maxS 且 Nc=K/2，可将 z1分裂成两个新的聚类。 设0 . 15 . 0 max1 j r，则 75. 2 38. 4 1 z 75. 2 38. 2 1 z 为方便起见，将 1 z 和 1 z 表示为 z1和 z2，Nc加 1，返回第二步。 第二步（返回 1） ：新的样本集为 S1=x4, x5, , x8，N1=5 S2=x1, x2, x3，N2=3 第三步（返回 1） ：因 N1N 且 N2N，无子集可抛。 第四步（返回 1） ：修改聚类中心 1 80. 3 80. 4 1 1 1 Sx x N z 2 00. 1 00. 1 1 2 2 Sx x N z 第五步 （返回 1） ： 计算模式样本与聚类中心间的平均距离 j D， j=1,2 80. 0 1 1 1 1 1 Sx zx N D 94. 0 1 2 2 2 2 Sx zx N D 第六步（返回 1） ：计算全部模式样本和其对应聚类中心的总平均 距离D 2 11 85. 0 8 11 j jj N j jj DNDN N D 第七步（返回 1） ：因是偶数次迭代，满足第七步的条件 3，进入第 十一步 第十一步：计算聚类对之间的距离 72. 4 2112 zzD 第十二步：比较 D12 与c ，D12c 第十三步：从上一步结果看出，聚类中心不发生合并。 第十四步：因不是最后一次迭代运算，判断是否需要修改给定的 参数。 （1） 已获得所要求的聚类数目； （2） 聚类之间的分离度大于类内样本分离的标准差； （3） 每一聚类子集的样本数目都具有样本总数中足够大的比例。 因此，可认为聚类中心具有代表性，返回第二步。 第二六步（返回 2） ：与上一次迭代计算结果相同。 第七步（返回 2） ：没有一种情况可满足，进入第八步。 第八步（返回 2） ：计算 S1=x4, x5, , x8和 S2=x1, x2, x3的标准差 75. 0 75. 0 1 82. 0 82. 0 2 第九步（返回 2） ：1max=0.75，2max=0.82 第十步（返回 2） ：分裂条件不满足，进入第十一步。 第十一步（返回 2） ：与上一次迭代的结果相同，计算得到 72. 4 2112 zzD 第十二、十三步（返回 2） ：与上一次迭代的结果相同。 第十四步（返回 2） ：无新的内容加入本次迭代中，返回第二步。 第二六步（返回 3） ：与上一次迭代计算结果相同。 第七步（返回 3） ：因是最后一次迭代，置c=0，转至第十一步。 第十一步（返回 3） ：同上一次迭代，72. 4 2112 zzD 第十二步（返回 3） ：与上一次迭代的结果相同。 第十三步（返回 3） ：无合并发生。 第十四步（返回 3） ：最后一次迭代，算法结束。 四四、判别函数、判别函数 1. 1.概念概念 两类问题的判别函数（以二维模式样本为例） 若 x 是二维模式样本 x = (x1 x2)T，用 x1和 x2作为坐标分量，得到 模式的平面图： 这时，若这些分属于1和2两类的模式可用一个直线方程 d(x)=0 来划分 d(x) = w1x1 + w2x2 + w3 = 0 其中 x1、x2为坐标变量，w1、w2、w3为参数方程，则将一个不知 类别的模式代入 d(x)，有 - 若 d(x) 0，则 1 x - 若 d(x) n 则分类界面在 x*空间是线性的， 在 x 空间是非线性的， 这里称 d(x*)=0 为广义的线性判别函数。 2. 2.为什么需要非线性判别函数？为什么需要非线性判别函数？ 实际工作中常靠已知类别的训练模式样本来确定判别函数，用该 判别函数构成的分类器对未知的模式进行分类。显然，训练用模式的 数目不可能太多，但待分类的未知模式却往往无穷无尽。若训练模式 的数目低于 Ck， 则由它确定的判别函数函数却被用来判别数目远远超 过 Ck的模式，这样，线性二分能力就迅速下降，发生错分的情况亦就 大为增加。 由于样本在特征空间分布的复杂性，许多情况下采用线性判别函 数不能取得满意的分类效果。 另外在数情况下样本分布及合适子类划 分并不知道，则往往需要采用一种聚类的方法，设法样本划分成相对 密集的子类，然后用各种方法设计各种线性判别函数。 例题：例题：两类模式，每类包括两类模式，每类包括 5 5 个个 3 3 维不同的模式，且良好分布。维不同的模式，且良好分布。 如果它们是线性可分的， 问权向量至少需要几个系数分量？假如要建如果它们是线性可分的， 问权向量至少需要几个系数分量？假如要建 立二次的多项式判别函数， 又至少需要几个系数分量？ （设模式的良立二次的多项式判别函数， 又至少需要几个系数分量？ （设模式的良 好分布不因模式变化而改变。 ）好分布不因模式变化而改变。 ） 根据线性判别函数的一般形式 11221nnn dxw xw xw xw 由于该模式为两类模式，分布良好，维数为 3，且它们是线性可分的，则权 向量至少需要 4 个系数分量。 根据 r 次多项式判别函数的一般形式以及仍在上述条件下，若要建立二次的 多项式判别函数，则至少需要 2 3 2 10 r n r CC 个系数分量。 222 11 1222333 121213132323 1 122334 d xw xw xw x w x xw x xw x x w xw xw xw 3. 3.势函数势函数 用下列势函数求解以下模式的分类问题 K(x,) = x 1: (0 1)T, (0 -1)T 2: (1 0)T, (-1 0)T 选择指数型势函数，取=1，在二维情况下势函数为 )()( 2 2 2 2 1 1 2 ),( kk k xxxxxx k eexxK 这里：1类为 x=(0 0) T, x =(2 0) T 2类为 x=(1 1) T, x =(1 -1) T 可以看出，这两类模式是线性不可分的。算法步骤如下： 第一步：取 x=(0 0) T 1，则 K1(x)=K(x,x)= )()0()0( 2 2 2 1 2 2 2 1 xxxx ee 第二步：取 x=(2 0) T 1 因 K1(x)=e -(4+0)=e-40， 故 K2(x)=K1(x)= )( 2 2 2 1 xx e 第三步：取 x=(1 1) T 2 因 K2(x)=e -(1+1)=e-20， 故 K3(x)=K2(x)-K(x,x)= )1()1()( 2 2 2 1 2 2 2 1 xxxx ee 第四步：取 x=(1 -1) T 2 因 K3(x) =e -