张素文-第3章线性判别函数

第三章线性判别函数第三章线性判别函数§3.1引言§3.2线性判别函数§3.3广义线性判别函数§3.4感知器算法§3.5梯度学习算法§3.6最小均方误差算法（LMSE）§3.7Fisher线性判别§3.1引言聚类分析法（第二章）判决函数法几何分类法[可训练的确定性分类器迭代算法]概率分类法[可训练的模式分类器迭代算法]线性判决函数法（第三章）统计决策方法非线性判决函数法复习与引申：模式识别统计若分属于和的两类模式可用一方程来划分，那么称为决策函数，或称判决函数、判别函数。一、判决函数(discriminantfunction)

直接用来对模式进行分类的准则函数。例：一个二维的两类判别问题，模式分布如图示，这些分属于、两类的模式可用一直线方程来划分。（3-1）为坐标变量，为方程参数。式中：一、判决函数(discriminantfunction)

颜色（绿/红）似圆度判别函数(DiscriminantFunction)将某一未知模式X代入：若，则类；若，则类；若，则维数=3时：判别边界为一平面。维数>3时：判别边界为一超平面。b)注意：对判别线正负的理解和确定。判别界面正负侧的确定，是在训练判别函数的权值时确定的，不要和几何上的概念混淆。表示的是一种分类的标准，它可以是1、2、3维的，也可以是更高维的。说明：1、判决函数的几何性质。它可以是线性的或非线性的函数，维数在特征提取时已经确定。如：已知三维线性分类——判决函数的性质就确定了判决函数的形式：二、确定判别函数的两个因素例：非线性判决函数2.判决函数的系数。用所给的模式样本确定。§3.2线性判别函数一、一般形式将二维模式推广到n维，线性判别函数的一般形式为：(3-2)式中：：权向量，即参数向量。上式也可写为增广向量的形式：式中：为增广权向量，为增广模式向量。二、线性判决函数的性质识别时：若1、两类情况：训练时：（=0是不可判别情况，可以）模式可为M类，、、……、，有三种划分方式：2、多类情况：两分法两分法两分法特例两分法(1)用线性判别函数将属于ωi类的模式与其余不属于ωi类的模式分开。从而训练出第i类判决函数的权向量将某个待分类模式X分别代入M个类的d

(X)中，若只有di(X)>0，其他d(X)均<0，则判为ωi类。判别方法判决函数的训练方法：对每一类的判决函数di(X)，分别将所有已知类别模式依次代入，有：

全部＜０不属任何类

IR，可能

属于1w或3w

1w2w3w0)(2=Xd0)(3=Xd++IR，可能

属于3w或2w

+---0)(1=Xd0,,0312<>ddd0,,0321<>ddd0,0,321<>dddIR，可能属于1w或2w

0,,0213<>ddd2x1x+对某一模式区，的条件超过一个，或全部的，分类失效。相当于不确定区（IndefiniteRegion，IR）。此法将M个多类问题分成M个两类问题，识别每一类均需M个判别函数。在识别分类时：例1：设有一个三类问题，其判别式为：现有一模式，试判定应属于哪类？解：将代入上三式，有：三个判别界面分别为：图示如下：步骤：a)画出界面直线。b)判别界面正负侧：找特殊点带入。c)找交集。例2：已知的位置和正负侧，找区域。—0)(1=Xd+0)(2=Xd+—0)(3=Xd+—2w3w1w两分法(2)一个判别界面只能分开两个类别，不能把其余所有的类别都分开。判决函数为：。这里在M类模式中，与i有关的M-1个判决函数全为正时，X∈ωi。其中若有一个为负，则为IR区。则类，而在判别类模式时不起作用。如：对一个三类问题，如果、判别方法训练方法：与值无关。例3：一个三类问题，三个判决函数为：问模式属于哪类？解：计算得可写成：(4,3)分类时：每分离出一类，需要与I有关的M-1个判决函数；要分开M类模式，共需M(M-1)/2个判决函数。对三类问题需要3(3-1)/2=3个判决函数。即：每次从M类中取出两类的组合：例4：已知的位置和正负侧，找区域。两分法特例(3)对某类问题有M个判决函数：即：训练方法：判别方法

判别界面需要做差值。对ωi类，应满足di>其他所有d。最大判别准则特点：①是第二种情况的特例。因为可以定义：可证明：即：若各类别在第三种情况下可分，则在第二种情况下也可分，但反之不一定。③把M类情况分成了M-1个两类问题。并且类的判别界面全部与类的判别界面相邻(向无穷远处延伸的区域除外)。②除边界区外，没有不确定区域。例5：一个三类模式（M=3）分类器，其判决函数为：且分别给出三类的判决界面。试判断属于哪一类，解：①类的判决函数：②判决界面如图所示。类的判决函数：类的判决函数：例六：已知判决界面的位置和正负侧，找区域。1、明确概念：线性可分。一旦线性判别函数的系数被确定以后，这些函数就可作为模式分类的基础。三、小结2、分法的比较：对于M类模式的分类，两分法共需要M个判别函数，但两分法需要M(M-1)/2个。当时M>3时，后者需要更多个判别式（缺点），但对模式的线性可分的可能性要更大一些（优点）。原因：一种类别模式的分布要比M-1类模式的分布更为聚集，分法受到的限制条件少，故线性可分的可能性大。§3.3广义线性判别函数1、目的：对非线性边界面：通过某映射，把模式空间X变成X*，以便将X空间中非线性可分的模式集，变成在X*空间中线性可分的模式集。2、定义：设一训练用模式集，在模式空间X中线性不可分，非线性判别函数形式如下：(3.3-1)式中是模式X的单值实函数，广义形式的模式向量定义为：(3.3-2)的形式是多种多样的。以X为二维时，选用二次多项式函数为例，如原判别的函数为：这里X*空间的维数k高于X空间的维数n，则(3.3-1)式写成简化的向量形式：上式是线性的。讨论线性判别函数并不会失去一般性的意义。(3.3-3)定义：则可将线性化为即：。§3.4感知器算法一种设计线性分类器的算法感知器的概念感知器线性阈值单元在（2）式中，令并且令：Y＝1和Y＝－1，分别表示两种类型，则（2）式演变为：问题：已知训练样本集，求加权向量W*。§3.4感知器算法一、概念理解只要求出权向量，分类器的设计即告完成。本节开始介绍如何通过各种算法，利用已知类别的模式样本训练出权向量W。（2）“感知器”：对一种分类学习机模型的称呼，属于有关机器学习的仿生学领域中的问题，由于无法实现非线性分类而下马。但“赏罚概念（TheReward-PunishmentConcept）”今天仍在模式识别中起着很大的作用。（1）“训练”：对于线性判别函数，当模式的维数知道时，判别函数的形式实际上也就定了下来，如：三维时已知两个训练模式集，分属于和，任取权向量初始值W(1)，开始迭代。二、感器学习算法（“赏——罚”过程）1、用全部训练模式集进行一轮迭代，计算的值。2、分三种情况，更新权向量的值：c为正的校正增量。（3.4-1）则分类器对第i个模式做了①错误分类，权向量校正为：为错误分类，有：若对的样本乘以（-1），则（3.4-2）改写为：（3.4-2）（3.4-3）②③若不是以上两种情况，表明分类正确，权向量不变，即统一写为：式中c为正的校正增量。（3.4-4）3、只要有一个样本判别错误，则进行第二轮迭代，直至用全部模式进行训练都获得正确分类结果，迭代结束。感知器算法是一种赏罚过程：分类正确时，对权向量“赏”——这里用“不罚”，即权向量不变；分类错误时，对权向量“罚”——对其修改，向正确的方向转换。三、收敛性收敛性：经过算法的有限次迭代运算后，求出了一个使所有样本都能正确分类的W，则称算法是收敛的。可以证明感知器算法是收敛的。收敛条件：模式类别线性可分。例：用感知器算法求出将图示模式分为两类的权向量解。解：将模式特征向量写成增广向量形式，将属于的训练样本乘以（-1）：取c=1，。则迭代过程为：第一轮：第一轮迭代中有两个≤0的情况（判别错误的情况），进行第二轮迭代。第二轮：第三轮：第四轮：该轮迭代的分类全部正确，故解向量相应的判别函数为：判别界面d(X)=0如图示。当c、W(1)取其他值时，结果可能不一样，所以感知器算法的解不是单值的。将两个模式的分类推广到多个模式分类的情况，采用3.2节中介绍的多类情况中的第三种方法，即：四、感知器算法用于多类情况若，则对于M类模式应存在M个判决函数：算法推导：设有M种模式类别：设其权向量初值为：一个属于类的模式样本X被送入分类器，则：1.计算出M个判决函数：②若第l个权向量使，则相应的权向量作调整，即：可以证明：只要该模式类别用情况三判别函数时是可分的，则该算法经过有限次迭代后收敛。，c为一正常数。①若则权向量不变；2.判别：采用多类情况3的方法时，应有：4.感知器算法用于多类情况若，则对于M类模式应存在M个判决函数：算法主要内容：设有M种模式类别：设其权向量初值为：第k次迭代时，一个属于ωi类的模式样本X

被送入分类器，计算所有判别函数训练样本为增广向量形式，但不需要规范化处理。分二种情况修改权向量：②若第l个权向量使，则相应的权向量作调整，即：可以证明：只要模式类在情况3判别函数时是可分的，则经过有限次迭代后算法收敛。，c为正的校正增量例3.9设有三个线性可分的模式类，三类的训练样本分别为①若则权向量不变；现采用多类情况3的方式分类，试用感知器算法求出判别函数。解：增广向量形式：注意，这里任一类的样本都不能乘以（－1）。任取初始权向量；c=1第一次迭代：三个权向量都需要修改：，但且不成立，第二次迭代：，但且不成立，修改权向量：第三次迭代：修改为权向量。，但且不成立，以上进行的一轮迭代运算中，三个样本都未正确分类，进行下一轮迭代。第四次迭代：……在第五、六、七迭代中，对所有三个样本都已正确分类。权向量的解：判别函数：设函数f(Y)是向量的函数，则f(Y)的梯度定义为：§3.5梯度学习算法即：

梯度的方向是函数f(Y)在Y点增长最快的方向，梯度的模是f(Y)在增长最快的方向上的增长率。（增长率的最大值）、梯度概念(3.5-1)

梯度向量的最重要性质之一：指出函数f在其自变量增加时，最大增大率的方向。例：对一个二维向量，令，则在几何上表示一个曲面，这个曲面被（常数）所截得的等高线，在平面上的投影是一条曲线L，不同的C值得到不同的等高线。由、平面所截的等高线在平面的投影为L1、L2。L1上A点的梯度方向与函数f(X)在点A的法线方向一致，是函数f(X)在点A增长最快的方向。若从高度C1到达C2，显然，若以同样的速率增长，沿梯度方向肯定是最快到达的。显然：负梯度指出了最陡下降方向。——梯度算法的依据。二、梯度法设两个线性可分的模式类ω1和ω2的样本共N个，ω2类样本乘(-1)。将两类样本分开的判决函数d(X)应满足：梯度算法的目的仍然是求一个满足上述条件的权向量，主导思想是将联立不等式求解W的问题，转换成求准则函数极小值的问题。——N个不等式准则函数的选取原则：具有唯一的最小值，并且这个最小值发生在W

tXi>0时。因此：寻找满足WtXi>0的W的问题，变为寻找使J(W,X)达到极小值的W的问题。即通过求准则函数极小值求符合要求的权向量。基本思路：定义一个对错误分类敏感的准则函数J(W,X)，在J的梯度方向上对权向量进行修改。一般关系表示成从W(k)导出W(k+1)：其中c是正的比例因子。 (3.5-2)梯度法求解步骤：b)依次将所有样本X代入准则函数J，对某个特定的X，J是W的函数，即J(W，X)=J(W)。求J对W的导数，代入当时的W(k)的值，求出。a)选择初始权向量W(1)。c)按(3.5-2)式修改权向量。若对所有样本均有，则W不再变化，算法收敛。例：选择准则函数解：不妨简单地设X=1（标量）。此时错误分类时：，对权向量校正。正确分类时：，对权向量不做修正。说明：随着权向量W向理想值接近，准则函数关于W的导数(即这里的梯度）会越来越趋近于零，这意味着准则函数J越来越接近最小值。当最终时，J达到最小值，此时W不再改变，算法收敛。——将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题。b)梯度算法是求解权向量的一般解法，算法的具体计算形式取决于准则函数J(W,X)的选择，J(W,X)的形式不同，得到的具体算法不同。a)c)c值的选择很重要，如c值太小，收敛太慢；但若太大，搜索又可能过头，甚至引起发散。§3.6最小均（平）方误差算法（LeastMeanSquareError,LMSE；亦称Ho-Kashyap算法）上述的感知器算法和由梯度导出的固定增量算法或其他类似方法，只是当被分模式可分离时才收敛，在不可分的情况下，算法会来回摆动，始终不收敛。当一次次迭代而又不见收敛时，造成不收敛现象的原因分不清，有两种可能：a)迭代过程本身收敛缓慢b)模式本身不可分对可分模式收敛。对于类别不可分的情况也能指出来。LMSE算法特点：、分类器的不等式方程两类分类问题的解相当于求一组线性不等式的解。如果给出分别属于、两个模式的训练样本集，应满足：若将的模式乘以（-1），则对全部模式都有：(3.6-1)设模式样本为n维，两类模式的训练样本总数为N个，将上式分开写有：写成矩阵形式为：令N×(n+1)维的长方矩阵为X（正体），则(3.6-1)式变为：(3.6-2)显然式中：为零向量。感知器算法实际就是通过(3.6-2)不等式组求出W的。(3.6-2)二、LMSE算法（H-K算法）1、原理LMSE算法把对满足的求解，改为满足的求解。(3.6-3)∴两式等价。定义准则函数：(3.6-4)为各分量均为正值的矢量。式中：①在方程组中，当行数>>列数时，通常无解，称为矛盾方程组，一般求近似解。在模式识别中，通常训练样本数N总是大于模式的维数n，因此方程的个数（行数）>>模式向量的维数（列数），即方程组为矛盾方程组，通常无精确解存在，但可求最小二乘解W*，即，W*为近似解。说明：②LMSE算法的出发点：选择一个准则函数，使得当J达到最小值时，可得到近似解（最小二乘解）。③LMSE算法的思路：转化为转化为④使J达到最小值的解W，就是矛盾方程组的最小二乘近似解，也称最优近似解。“最小二乘”——最小:：使方程组两边误差最小，也即使J最小。——二乘：括号的次数为2，乘了两次；也即“最小平方（误差算法）“最优近似解”——使方程组两边所有误差之和最小（即最优）的解。矢量：准则函数的推导：从(3.6-3)和(3.6-4)式可看出：①当函数J达到最小值，等式有最优解。即又将问题转化为求准则函数极小值的问题。②因为J有两个变量W和B，有更多的自由度供选择求解，故可望改善算法的收敛速率。(3.6-3)(3.6-4)2、推导LMSE算法递推公式与问题相关的两个梯度：

②

1)求W的迭代式：使J对W求最小，有：③由③式可知：只要求出B，就可求出W。求递推公式：得：令称为X的伪逆，X为阶长方阵，式中：为阶。①2)求B的迭代式：利用梯度法中的(3.5-2)式有：②代入：令，定义#1④3)求W(k+1)的迭代式：将④代入③式有：#2式中：②=0设初值B(1)，须使其每一分量都为正值。……W(k+1)、B(k+1)互相独立，均只与有关。故迭代式中也可先算B(k+1)，然后按来计算，即：……求出B、W后，再迭代出下一个，从而计算出新的B、W。总结LMSE算法迭代式：③#2④#1三、模式类别可分性的判别及算法的特点：（一）可分性判别②如果，这时隐含，有解。如继续迭代，可使。③如果的所有分量为负数或零（但不是全部为零），停止迭代，无解。此时若继续迭代下去，数据不再发生变化。

可以证明：当模式类线性可分，且校正系数c满足时，该算法收敛，可求得解W。理论上不能证明该算法到底需要迭代多少步才能达到收敛，通常在每次迭代计算后检查一下和误差向量，从而可以判断是否收敛。①如果或（即），有解。分以下几种情况：关于③的说明：通过反证法可以证明：在线性可分情况下，算法进行过程中不会出现的分量全为负的情况；若出现的分量全为负，则说明模式类线性不可分。b)所有分量为非正，继续迭代数据无变化的情况分析：③如果的所有分量为负数或零（但不是全部为零），停止迭代，无解。此时若继续迭代下去，数据不再发生变化。或综上所述：只有当中有大于零的分量时，才需要继续迭代，一旦的全部分量只有0和负数，则立即停止。事实上，往往早在全部分量都达到非正值以前，就能看出其中有些分量向正值变化得极慢，可及早采取对策。（二）算法特点除了对可分模式是收敛的以外，对于线性不可分的模式，在算法迭代过程中就可明确的表示出来。例1：已知两类模式训练样本：解：1）写出增广矩阵：2）求伪逆矩阵求逆矩阵：若，则是的代数余子式，注意两者的行和列的标号互换。|A|——A的行列式A*——A的伴随矩阵代数余子式定义：划去aij所在的行和列的元素，余下元素构成的行列式做aij的余子式，记作Mij，将叫做元素aij的代数余子式。例：行列式:3）开始迭代：取和c=1.故W(1)就是解，即判断函数为：图示如下：例2：已知模式训练样本：2）求：解：1）增广矩阵：3）迭代：取和c=1.全部分量为负，无解，停止迭代。为线性不可分模式。

可以看出：2）算法尽管略为复杂一些，但它提供了线性可分的测试特征，并且收敛速度也比前面的梯度法（包括感知器算法）要快一些。1）LMSE算法的明显缺点是需要对矩阵求逆，好在一个分类问题，只要进行一次求逆。此外，当新的一行加入X中时（即新的模式样本加入），逆矩阵有迭代算法。小结：1、感知器法、梯度法、最小平方误差算法讨论的分类算法都是通过模式样本来确定判别函数的系数，所以要使一个分类器设计完善，必须采用有代表性的数据，训练判别函数的权系数。它们能合理反映模式数据的总体。2、要获得一个有较好判别性能的线性分类器，所需要的训练样本的数目的确定。用指标二分能力Ck来决定训练样本的数目：通常训练样本的数目不能低于Ck，选为Ck的10~20倍左右。二维：不能低于6个样本，最好选在60~120个样本之间。三维：不能低于8个样本，最好选在80~160个样本之间。k为模式维数如复习：LMSE算法1、算法过程①由已知类别的样本写出增广矩阵X，求出，设B(1)、c初值，B(1)每一分量必须全为正值