模式识别第二章(线性判别函数法)

第二章线性判别函数2023/2/1模式识别导论2实例：统计模式识别19名男女同学进行体检，测量了身高和体重，但事后发现其中有4人忘记填写性别，试问（在最小错误的条件下）这4人是男是女？体检数值如下：2023/2/1模式识别导论3实例：统计模式识别（续）待识别的模式：性别（男或女）测量的特征：身高和体重训练样本：15名已知性别的样本特征目标：希望借助于训练样本的特征建立判别函数（即数学模型）2023/2/1模式识别导论4实例：统计模式识别（续）从图中训练样本的分布情况，找出男、女两类特征各自的聚类特点，从而求取一个判别函数（直线或曲线）。只要给出待分类的模式特征的数值，看它在特征平面上落在判别函数的哪一侧，就可以判别是男还是女了。2023/2/1模式识别导论5有关模式识别的3个问题学习人们在日常生活中几乎时时刻刻在进行模式识别的活动，从小时候起就开始学习与增强这种能力。如小孩学习认字、认识事物都有一个从不会到会的过程。确定分类决策的具体数学公式是通过分类器设计这个过程确定的。在模式识别学科中一般把这个过程称为训练与学习的过程。一般来说，决定使用什么类型的分类函数往往是人为决定的。但数学式子中的参数则往往通过学习来确定2023/2/1模式识别导论6有关模式识别的3个问题模式的紧致性分类器设计难易程度与模式在特征空间的分布方式有密切关系，例如图(a)、(b)与(c)分别表示了两类在空间分布的三种状况。两类事物分布的区域不要有相互混迭的情况，事物尽管没有混迭，但交界线很复杂。2023/2/1模式识别导论71有关模式识别的3个问题相似性度量同类物体之所以属于同一类，在于它们的某些属性相似，因此可选择适当的度量方法检测出它们之间的相似性。在特征空间中用特征向量描述样本的属性，用距离来表示相似性度量。合适的特征空间情况下，同类样本应具有聚类性，或紧致性好，而不同类别样本应在特征空间中显示出具有较大的距离。2023/2/1模式识别导论84.1引言分类器设计方法，是根据训练样本集提供的信息，直接进行分类器设计。这种方法省去了统计分布状况分析，直接对特征空间进行划分，也是当前的主要方法之一。2023/2/1模式识别导论92.1引言决策域的分界面是用数学表达式来描述的，如线性函数和各种非线性函数等，所以分界面的方程主要包括函数类型选择与最佳参数确定。一般来说，函数类型由设计者选择，其参数的确定则是依据一定的准则函数，通过一个学习过程来实现优化。2023/2/1模式识别导论102.1引言将模式识别的设计过程，主要是判别函数、决策面方程的确定过程改成2023/2/1模式识别导论112.1引言线性分类器以及作为设计依据的一些准则函数，准则函数包括：感知准则，最小平方误差准则，最小错分样本数准则，Fisher准则。2023/2/1模式识别导论122.2.1线性判别函数的基本概念在一个d维的特征空间中，线性判别函数的一般表达式如下2023/2/1模式识别导论132.2.1线性判别函数的基本概念如果采用增广模式，可以表达如下若分属于ω1，ω2的两类模式可用一方程d(X)=0来划分，那么称d(X)为判别函数，或称判决函数、决策函数。2.1判别函数(discriminantfunction)

直接用来对模式进行分类的准则函数。例：一个二维的两类判别问题，模式分布如图示，这些分属于ω1，ω2两类的模式可用一直线方程d(X)=0来划分。为坐标变量，为方程参数。式中：图3.2两类二维模式的分布1．判别函数的定义若，则若，则类；若，则类；

或拒绝将某一未知模式

X

代入：维数=3时：判别边界为一平面。维数>3时：判别边界为一超平面。d(X)表示的是一种分类的标准，它可以是1、2、3维的，也可以是更高维的。

判别界面的正负侧，是在训练判别函数的权值时确定的。2．判别函数正负值的确定图3.3判别函数正负的确定1）判决函数d(X)的几何性质。它可以是线性的或非线性的函数，维数在特征提取时已经确定。如：已知三维线性分类——判决函数的性质就确定了判决函数的形式：3.确定判别函数的两个因素例：非线性判决函数2）判决函数d(X)的系数。用所给的模式样本确定。181920多类问题图例（第一种情况）?不确定区域211、第一种情况（续）判别规则为：如果则判比如对图的三类问题,如果对于任一模式如果它的则该模式属于ω1类。221、第一种情况（续）如果某个X使二个以上的判别函数di>0

。则此模式X就无法作出确切的判决。如图另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确定区域。231、第一种情况（续）解：三个判别边界分别为：241、第一种情况（续）结论：因为所以它属于ω2类。251、第一种情况（续）26272、第二种情况（续）多类问题图例（第二种情况）2829d12(x)=-d21(x)=–x1–x2+5=0d12(x)为正两分法例题图示0123456789987654321d21(x)为正30d12(x)为正两分法例题图示0123456789987654321d21(x)为正d23(x)=-d32(x)=–x1+x2=0d32(x)为正d23(x)为正31d12(x)为正两分法例题图示0123456789987654321d21(x)为正d32(x)为正d23(x)为正d13(x)=-d31(x)=–x1+3=0d31(x)为正d13(x)为正321类判别区域

d12(x)>0d13(x)>02类判别区域

d21(x)>0d23(x)>0d12(x)为正两分法例题图示0123456789987654321d21(x)为正d32(x)为正d23(x)为正d31(x)为正d13(x)为正3类判别区域

d31(x)>0d32(x)>0IR33343、第三种情况（续）多类问题图例（第三种情况）35。36上述三种方法小结:方法⑶判别函数的数目和方法⑴相同，但没有不确定区，分析简单，是最常用的一种方法。时，法比法需要更多当的判别函数式，这是一个缺点。类与其余的开，而法是将类和类分开，显然法是将但是类区分法使模式更容易线性可分，这是它的优点。(1)明确概念：线性可分。

一旦线性判别函数的系数Wk被确定以后，这些函数就可以作为模式分类的基础。3.小结(2)分法的比较：

对于M类模式的分类，两分法共需要M个判别函数，但两分法需要M(M-1)/2个。当时M>3时，后者需要更多个判别式（缺点），但对模式的线性可分的可能性要更大一些（优点）。原因：

一种类别模式的分布要比M-1类模式的分布更为聚集，分法受到的限制条件少，故线性可分的可能性大。2023/2/1模式识别导论38.2.1线性判别函数的基本概念线性分类器的设计就是利用训练样本集建立线性判别函数式，也就是寻找最优的权向量w的过程。其主要步骤如下采集训练样本，构成训练样本集。样本应该具有典型性确定一个准则J=J(w,x)，能反映分类器性能，且存在权值w*使得分类器性能最优设计求解w的最优算法，得到解向量w*2023/2/1模式识别导论392.2.2感知器概念及其训练方法感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。402.3感知器算法(PerceptronApproach)任选一初始增广权矢量用训练样本检验分类是否正确对所有训练样本都正确分类？YesENDYesNo对权值进行校正No感知器算法流程图流程:2023/2/1模式识别导论412.2感知器概念及其训练方法设训练样本集X={x1,x2,…,xn}，其中xk属于wi或者wj，且xk的类别是已知的。为了确定加权向量w*，执行下面的训练算法给定初始值：置k=0，权向量w(k)为任意值，可选常数0＜c≤1输入样本xm∈{x1,x2,…,xn}，计算判决函数值g(xm)=wT(k)xm按如下规则修改权向量若xm∈wi，且g(xm)≤0，则w(k+1)=w(k)+cxm若xm∈wj，且g(xm)＞0，则w(k+1)=w(k)-cxm令k=k+1，返回第二步，直到w对所有样本稳定不变，结束42二、收敛定理：

如果训练模式是线性可分的，感知器训练算法在有限次迭代后便可以收敛到正确的解矢量。。证明思路：

如果第k+1次迭代生成的权矢量比第k次迭代生成的权矢量更接近解矢量，则收敛，即：2023/2/1模式识别导论43例子1已知两类训练样本，(0,0),(0,1)属于w1，(1,0),(1,1)属于w2，试用感知器算法求解w*训练样本分量增广化以及符号规范化。将训练样本增加一个分量1，且把来自w2的样本各分量乘以-1，得到训练模式集x1=(0,0,1),x2=(0,1,1),x3=(-1,0,-1),x4=(-1,-1,-1)运用训练算法，给权向量赋初值w(1)=(1,1,1)T，取增量c=1，置迭代步数k=1，下面是迭代过程2023/2/1模式识别导论44例子1K=1,xm=x1,w(k)Txm=1>0,w(2)=w(1)K=2,xm=x2,w(k)Txm=2>0,w(3)=w(2)K=3,xm=x3,w(k)Txm=-2<0,w(4)=w(3)+x3=(0,1,0)TK=4,xm=x4,w(k)Txm=-1<0,w(5)=w(4)+x4=(-1,0,-1)TK=5,xm=x1,w(k)Txm=-1<0,w(6)=w(5)+x1=(-1,0,0)TK=6,xm=x2,w(k)Txm=0,w(7)=w(6)+x2=(-1,1,1)TK=7,xm=x3,w(k)Txm=0,w(8)=w(7)+x3=(-2,1,0)TK=8,xm=x4,w(k)Txm=1>0,w(9)=w(8)2023/2/1模式识别导论45例子1K=9,xm=x1,w(k)Txm=0,w(10)=w(9)+x1=(-2,1,1)TK=10,xm=x2,w(k)Txm=2>0,w(11)=w(10)K=11,xm=x3,w(k)Txm=1>0,w(12)=w(11)K=12,xm=x4,w(k)Txm=0,w(13)=w(12)+x4=(-3,0,0)TK=13,xm=x1,w(k)Txm=0,w(14)=w(13)+x1=(-3,0,1)TK=14,xm=x2,w(k)Txm=1>0,w(15)=w(14)K=15,xm=x3,w(k)Txm=2>0,w(16)=w(15)K=16,xm=x4,w(k)Txm=2>0,w(17)=w(16)K=17,xm=x1,w(k)Txm=1>0,w(18)=w(17)2023/2/1模式识别导论46例子1通过上面的结果可以看出，经过对x1,x2,x3,x4一轮迭代后，使用w(14)已经能够对所有训练样本正确分类，增广权矢量的值不再发生变化，所以算法收敛于w(14)，w(14)就是所求的解向量，即w*=(-3,0,1)T。由此可以得到区分界面为：-3x1+1=0采用多类情况3的方法时，应有：2.感知器算法用于多类情况若，则对于M类模式应存在M个判决函数：算法主要内容：设有M种模式类别：设其权向量初值为：

第k次迭代时，一个属于ωi类的模式样本X

被送入分类器，计算所有判别函数训练样本为增广向量形式，但不需要规范化处理。分二种情况修改权向量：②若第l个权向量使，则相应的权向量作调整，即：

可以证明：只要模式类在情况3判别函数时是可分的，则经过有限次迭代后算法收敛。，c为正的校正增量例3.9

设有三个线性可分的模式类，三类的训练样本分别为①若则权向量不变；现采用多类情况3的方式分类，试用感知器算法求出判别函数。解：增广向量形式：注意，这里任一类的样本都不能乘以（－1）。任取初始权向量；c=1第一次迭代：三个权向量都需要修改：，但且不成立，第二次迭代：，但且不成立，修改权向量：第三次迭代：修改为权向量。，但且不成立，

以上进行的一轮迭代运算中，三个样本都未正确分类，进行下一轮迭代。第四次迭代：……在第五、六、七迭代中，对所有三个样本都已正确分类。权向量的解：判别函数：2023/2/1模式识别导论522.2.3感知器准则函数及其梯度法在两类样本线性可分的情况下，通过上面的例子可知，如果将属于wj的样本各分量同时乘以-1，则可以由所有满足wTx>0的样本求出解w*，即可确定决策函数。但是，对于求解问题，可能存在多个可行解，因此问题进一步转化成如何按一定条件利用优化算法求得最优解的问题。感知器准则函数与梯度法。2023/2/1模式识别导论532.2.3感知器准则函数及其梯度法梯度法采用最优化技术求线性判别函数中的增广权向量，首先需要构造准则函数。其次再通过优化算法求得最优解，这里选用梯度法求解。一个可微函数某点的梯度给出函数在该点的变化率最大的方向；负梯度给出下降最快的方向。那么对于有极小值的函数而言，可以沿着负梯度的方向选择适当的步长进行搜索，求解函数的极小值点。2023/2/1模式识别导论54梯度法如果我们定义一个准则函数J(w,x)，它的最小值对应着最优解w*，那么完全可以运用数学分析中这种求极值的方法来进行求解，这便是梯度法的基本思想。由于是迭代算法，所以它有一个迭代公式，并且可以找到数值解。迭代公式如下：2.2.3感知器准则函数及其梯度法2023/2/1模式识别导论55感知器准则函数构造准则函数如下：当|wTx|-wTx=0，该准则函数可以达到最小值，此时有wTx>0，所以可以得到最优解，也就是最优权向量w*。2.2.3感知器准则函数及其梯度法2023/2/1模式识别导论56感知器准则函数当p=c时，梯度下降法与感知器训练算法的修正公式一致，因此感知器训练算法是梯度下降法的一种特例，一般将p为常数的梯度法称为固定增量法。当p在迭代运算时随k变化，称为可变增量法。2.2.3感知器准则函数及其梯度法2.7最小平方误差算法（leastmeansquareerror,LMSE；亦称Ho-Kashyap算法）

上述的感知器算法、梯度算法、固定增量算法或其他类似方法，只有当模式类可分离时才收敛，在不可分的情况下，算法会来回摆动，始终不收敛。当一次次迭代而又不见收敛时，造成不收敛现象的原因分不清，有两种可能：a)迭代过程本身收敛缓慢b)模式本身不可分对可分模式收敛。对于类别不可分的情况也能指出来。LMSE算法特点：2023/2/1模式识别导论582.3最小平方误差准则在两类样本线性可分的情况下，如果将属于wj的样本各分量同时乘以-1，则应该有权向量w，对所有样本满足wTxi>0，设计分类器就是求解一组线性不等式。如果任意给定一个向量b=[b1,b2,…,bn]T>0，那么上述问题可以转化成求解w，使之满足wTxi＝bi。2023/2/1模式识别导论592.3最小平方误差准则设分别属于wi与wj的样本数为n1与n2，n=n1+n2W为d+1维列向量，通常有：n>d+1，那么方程是没有精确解存在的。定义误差向量：e=xw-b最小平方误差准则函数如下：2023/2/1模式识别导论602.3最小平方误差准则此时的w*并不是最小平方误差准则函数下的解，因为w*还依赖于b。根据平方误差准则函数，使用固定增量的梯度下降法建立b的迭代公式如下（即b的初始值可以任意给定）。1.分类器的不等式方程

两类分类问题的解相当于求一组线性不等式的解。如果给出分属于，两个模式类的训练样本集，应满足：其中，Xi是规范化增广样本向量，。上式分开写为：写成矩阵形式为：令N×(n+1)的长方矩阵为X，则变为：式中：0为零向量感知器算法是通过解不等式组，求出W。2.LMSE算法1)原理的求解。式中：∴

两式等价。为各分量均为正值的矢量。LMSE算法把对满足XW>0

的求解，改为满足①在方程组中当行数>>列数时，通常无解，称为矛盾方程组，一般求近似解。在模式识别中，通常训练样本数N总是大于模式的维数n，因此方程的个数(行数)>>模式向量的维数(列数)，是矛盾方程组，只能求近似解W*，即说明：②LMSE算法的出发点：选择一个准则函数，使得当J达到最小值时，XW=B

可得到近似解（最小二乘近似解）。③LMSE算法的思路：转化为转化为准则函数定义为：“最小二乘”：——最小：使方程组两边误差最小，也即使J最小。——二乘：次数为2，乘了两次最小平方（误差算法）考察向量(XW－B)有：可以看出：①当函数J达到最小值，等式XW=B有最优解。即又将问题转化为求准则函数极小值的问题。②因为J有两个变量W和B，有更多的自由度供选择求解，故可望改善算法的收敛速率。XW=B

的近似解也称“最优近似解”：——使方程组两边所有误差之和最小（即最优）的解。准则函数：使J对W求最小，令，得：2)推导LMSE算法递推公式与问题相关的两个梯度：(3-46)(3-47)由(3-47)式可知：只要求出B，就可求出W。求递推公式：(1)求W的递推关系X为N×(n+1)长方阵，X#为(n+1)×N长方阵。称为X的伪逆，式中：(3-45)(2)求B(k+1)的迭代式(3-46)代入，得

令，定义(3-49)(3-50)(3-46)利用梯度算法公式有：(3)求W(k+1)的迭代式将(3-50)代入(3-47)式W=X#B

有：=0(3-49)(3-50)总结：设初值B(1)，各分量均为正值，括号中数字代表迭代次数。……W(k+1)、B(k+1)互相独立，先后次序无关。……求出B，W后，再迭代出下一个e，从而计算出新的B，

W。或另一算法：先算B(k+1)，再算W(k+1)。3）模式类别可分性判别②

如果e(k)>0

，表明XW(k)>B(k)>0，隐含有解。继续迭代，可使e(k)→0

。③

如果e(k)<0（所有分量为负数或零，但不全为零），停止迭代，无解。此时若继续迭代，数据不再发生变化。

可以证明：当模式类线性可分，且校正系数c满足时，该算法收敛，可求得解W。

理论上不能证明该算法到底需要迭代多少步才能达到收敛，通常在每次迭代计算后检查一下XW(k)和误差向量e(k)，从而可以判断是否收敛。①

如果e(k)=0

，表明XW(k)=B(k)>0，有解。分以下几种情况：情况③分析：e(k)<0

综上所述：只有当e(k)中有大于零的分量时，才需要继续迭代，一旦e(k)的全部分量只有0和负数，则立即停止。事实上，往往早在e(k)全部分量都达到非正值以前，就能看出其中有些分量向正值变化得极慢，可及早采取对策。

通过反证法可以证明：在线性可分情况下，算法进行过程中不会出现e(k)的分量全为负的情况；若出现e(k)的分量全为负，则说明模式类线性不可分。4)LMSE算法描述(1)根据N个分属于两类的样本，写出规范化增广样本矩阵X。(2)求X的伪逆矩阵。……(3)设置初值c和B(1)，c为正的校正增量，B(1)的各分量大于零，迭代次数k=1。开始迭代：计算(4)计算，进行可分性判别。如果e(k)>0，线性可分，若进入(5)可使e(k)→0

，得最优解。如果e(k)<0，线性不可分，停止迭代，无解，算法结束。如果e(k)=0，线性可分，解为W(k)，算法结束。否则，说明e(k)的各分量值有正有负，进入(5)。(5)计算W(k+1)和B(k+1)。方法1：分别计算方法2：先计算再计算迭代次数k加1，返回(4)。3.算法特点(1)算法尽管略为复杂一些，但提供了线性可分的测试特征。(2)同时利用N个训练样本，同时修改W和B，故收敛速度快。(3)计算矩阵复杂，但可用迭代算法计算。例3.11已知两类模式训练样本：试用LMSE算法求解权向量。解：(1)写出规范化增广样本矩阵：

Aij是aij的代数余子式，注意两者的行和列的标号互换。(2)求伪逆矩阵求逆矩阵：若，则|A|——A的行列式A*——A的伴随矩阵

划去aij所在的行和列的元素，余下元素构成的行列式做aij的余子式，记作Mij，将叫做元素aij的代数余子式。例：代数余子式定义：行列式:(3)取和c=1开始迭代：.解为W(1)，判断函数为：图示如下：例3.12已知模式训练样本：，(2)求：解：(1)规范化增广样本矩阵：(3)取和c=1，迭代：用LMSE算法求解权向量。

e(1)全部分量为负，无解，停止迭代。为线性不可分模式。

小结：(1)感知器法、梯度法、最小平方误差算法讨论的分类算法都是通过模式样本来确定判别函数的系数，所以要使一个分类器设计完善，必须采用有代表性的数据，训练判别函数的权系数。它们能合理反映模式数据的总体。(2)要获得一个有较好判别性能的线性分类器，所需要的训练样本的数目的确定。用指标二分法能力N0来确定训练样本的数目：通常训练样本的数目不能低于N0

，选为

N0的5~10倍左右。二维：不能低于6个样本，最好选在30~60个样本之间。三维：不能低于8个样本，最好选在40~80个样本之间。n为模式维数如2023/2/1模式识别导论852.4

Fisher线性判别准则2023/2/1模式识别导论862023/2/1模式识别导论872023/2/1模式识别导论882023/2/1模式识别导论892.4

Fisher线性判别准则是将d维空间的样本映射到了一维样本集，这个一维空间的方向是相对于Fisher准则为最好的。我们还需要解决分类问题。将d维分类问题转化为一维分类问题后，只需要确定一个阈值点，将投影点与阈值点比较，就可以做出决策。902.4Fisher线性判别91二维模式向一维空间投影示意图uroxy92二维模式向一维空间投影示意图uroxy93二维模式向一维空间投影示意图oxyoxy94（1)求解Fish准则函数9596类间离差度为：97并使其最大,上式称为Fisher准则函数。98利用二次型关于矢量求导的公式可得：（2)求解Fisher最佳鉴别矢量令可得：99100上式右边后两项因子的乘积为一标量，令其为，于是可得式中为一标量因子，其不改变轴的方向，可以取为1,于是有101此时的可使Fisher准则函数取最大值，即是n

维空间到一维空间投影轴