判别函数及几何分类法.ppt

第3章 判别函数及几何分类法,第3章 判别函数及几何分类法,3.1 判别函数3.2 线性判别函数3.3 广义线性判别函数3.4 线性判别函数的几何性质3.5 感知器算法3.6 梯度法3.7 最小平方误差算法3.8 非线性判别函数,3.1 判别函数,聚类分析法（第七章）,判决函数法,几何分类法确定性事件分类（第三章）,概率分类法随机事件分类（第二章）,线性判决函数法,统 计 决 策 方 法,非线性判决函数法,复习与引申：,若分属于1，2的两类模式可用一方程d(X)=0来划分，那么称d(X)为判别函数，或称判决函数、决策函数。,3.1 判别函数(discriminant function),直接用来对模式进行分类的准则函数。,例：一个二维的两类判别问题，模式分布如图示，这些分属于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)的系数。用所给的模式样本确定。,3.2 线性判别函数,3.2.1 线性判别函数的一般形式,将二维模式推广到n维，线性判别函数的一般形式为：,(3-2),式中：,增广向量的形式：,式中：,为增广权向量，,为增广模式向量。,权向量,3.2.2 线性判别函数的性质,1.两类情况,对M个线性可分模式类，1，2，M，有三种划分方式：,2.多类情况,两分法,两分法,两分法特例,用线性判别函数将属于i类的模式与其余不属于i类的模式分开。,识别分类时：,对某一模式区，di(X)0的条件超过一个，或全部的di(X)0，分类失效。相当于不确定区(indefiniteregion，IR)。,此法将 M 个多类问题分成M个两类问题，识别每一类均需M个判别函数。识别出所有的M类仍是这M个函数。,例3.1 设有一个三类问题，其判别式为：,现有一模式，X=7,5T，试判定应属于哪类？并画出三类模式的分布区域。,解：将X=7,5T代入上三式，有：,三个判别界面分别为：,图示如下：,步骤：,a)画出界面直线。,b)判别界面正负侧：找特殊点带入。,c)找交集。,例3.2 已知di(X)的位置和正负侧，分析三类模式的分布区域。,一个判别界面只能分开两个类别，不能把其余所有的类别都分开。判决函数为：。这里。,则 类，而 在判别 类模式时不起作用。,如：对一个三类问题，如果，,识别分类时：,判别函数性质：,与 值无关。,例3.3 一个三类问题，三个判决函数为：,解：计算得,可写成：,x2,x1,d23(X)=0,d12(X)=0,d13(X)=0,5,5,3,0,分类时：每分离出一类，需要与I 有关的M-1个判决函数；要分开M类模式，共需M(M-1)/2个判决函数。对三类问题需要3(3-1)/2=3个判决函数。即：每次从M类中取出两类的组合：,例3.4 已知dij(X)的位置和正负侧，分析三类模式的分布区域。,当i/j两分法中的判别函数dij(X)，可以定义为,时，那么di(X)dj(X)就相当于多类情况2中的dij(X)0。,因此对具有判别函数,的M类情况，判别函数性质为：,或：,识别分类时：,判别界面需要做差值。对i类，应满足：di其他所有dj,除边界区外，没有不确定区域。,特点：,是第二种情况的特例。由于dij(X)=di(X)dj(X)，若在第三种情况下可分，则在第二种情况下也可分，但反过来不一定。,把 M 类情况分成了(M-1)个两类问题。并且 类的判别界面全部与 类的判别界面相邻（向无穷远处延伸的区域除外）。,特别的定义,例3.5 一个三类模式（M=3）分类器，其判决函数为：,试判断X0=1,1T属于哪一类，且分别给出三类的判决界面。,解：,判决界面如图所示。,类的判决函数：,类的判决函数：,例3.6 已知判决界面的位置和正负侧，分析三类模式的分布 区域。,(1)明确概念：线性可分。,一旦线性判别函数的系数Wk被确定以后，这些函数就可以作为模式分类的基础。,3.小结,(2)分法的比较：,对于M类模式的分类，两分法共需要M个判别函数，但 两分法需要M(M-1)/2个。当时M3时，后者需要更多个判别式（缺点），但对模式的线性可分的可能性要更大一些（优点）。,原因：,一种类别模式的分布要比M-1类模式的分布更为聚集，分法受到的限制条件少，故线性可分的可能性大。,两分法,若只有di(X)0，其他d(X)均0，则判为i 类,两分法:,定义,1非线性多项式函数 非线性判别函数的形式之一是非线性多项式函数。,3.3 广义线性判别函数,目的：对非线性边界：通过某映射，把模式空间X变成X*，以便将X空间中非线性可分的模式集，变成在X*空间中线性可分的模式集。,设一训练用模式集，X在模式空间X中线性不可分，非线性判别函数形式如下：,(3-9),式中 是模式X的单值实函数，。,fi(X)取什么形式及d(X)取多少项，取决于非线性边界的复杂程度。,广义形式的模式向量定义为：,(3-10),这里X*空间的维数k高于X空间的维数n，(3-9)式可写为,上式是线性的。讨论线性判别函数并不会失去一般性的意义。,(3-11),随着小样本学习理论和支持向量机的迅速发展，广义线性判别函数的“维数灾难”问题在一定程度上找到了解决的办法。,非线性变换可能非常复杂。,问题：,维数大大增加：维数灾难。,例3.7 假设X为二维模式向量，fi(X)选用二次多项式函数，原判别函数为,定义：,d(X)线性化为：,即：,广义线性判别函数：,3.4 线性判别函数的几何性质,3.4.1 模式空间与超平面,模式空间：以n维模式向量X的n个分量为坐标变量的欧氏空间。,模式向量的表示：点、有向线段。,线性分类：用d(X)进行分类，相当于用超平面d(X)=0把模式空 间分成不同的决策区域。,2.讨论,1.概念,式中，。,设判别函数：,超平面：,(1)模式向量X1和X2在超平面上,W0是超平面的法向量，方向由超平面的负侧指向正侧。,设超平面的单位法向量为U：,(2)X不在超平面上,将X向超平面投影得向量Xp，构造向量R：,r：X到超平面的垂直距离。有,(r),判别函数d(X)正比于点X到超平面的代数距离。,X到超平面的距离：,点X到超平面的代数距离（带正负号）正比于d(X)函数值。,(3)X在原点,得,超平面的位置由阈值权wn+1决定：,wn+1 0时，原点在超平面的正侧；,wn+1 0时，原点在超平面负侧；,wn+1=0 时，超平面通过原点。,3.4.2 权空间与权向量解,1.概念,权空间：以 的权系数为 坐标变量的（n+1）维欧氏空间,增广权向量的表示：点、有向线段。,2.线性分类,判别函数形式已定，只需确定权向量。,类：X11，X12，X1p,类：X21，X22，X2q,设增广样本向量：,使d(X)=0将1和 2分开，需满足,给2的q个增广模式乘以（1），统一为,其中,样本的规范化过程。,对每个已知的X，d(X)=0在权空间确定一个超平面，共(p+q)个。,在权空间中寻找向量W使判别函数d(X)能把1类和2类分开，就是寻找一个权向量，使得上式中的（p+q）个不等式同时成立,因此满足条件的权向量必然在（p+q）个超平面的正侧的交迭区域里(即W的解区)。,X：规范化增广样本向量。,例：二维权空间，超平面的方程为：,超平面：过原点的直线；,阴影部分：解区。,3.4.3 二分法,二分法（Dichotomies）：用判别函数d(X)将给定的N个模式 分成两类的方法。是一种基本的分类方法。,判别函数的不同分类能力可以通过二分法总数衡量。,若不限制判别函数的形式，N个n维模式用判别函数分成两类的二分法总数为2N。,若限定用线性判别函数，并且样本在模式空间是良好分布的，即在n维模式空间中没有(n+1)个模式位于(n1)维子空间中，可以证明，N个n维模式用线性判别函数分成两类的方法总数，即线性二分法总数为,或线性二分法概率：,只要模式的个数N小于或等于增广模式的维数（n+1），模式类总是线性可分的，,例：4个良好分布的2维模式，若用线性判别函数分类,线性二分法总数：,线性二分法概率：,图3.14 线性二分法的概率,将=2时的N值定义为阈值N0，称为二分法能力，即,通过N0，可以对任意N个样本的线性可分性进行粗略估计。,3.5 感知器算法,1.概念理解,训练：用已知类别的模式样本指导机器对分类规则进行反复修 改，最终使分类结果与已知类别信息完全相同的过程。,1）训练与学习,只要求出权向量，分类器的设计即告完成。本节开始介绍如何通过各种算法，利用已知类别的模式样本训练出权向量W。,对线性判别函数，当模式维数已知时，判别函数的形式实际上已经确定，如：三维时,3）感知器 对一种分类学习机模型的称呼，属于有关机器学习的仿生学领域中的问题，由于无法实现非线性分类而下马。但“赏罚概念（reward-punishment concept）”得到广泛应用。,2）确定性分类器,处理确定可分情况的分类器。通过几何方法将特征空间分解为对应不同类的子空间，又称为几何分类器。,2.感器算法（perception approach）,两类线性可分的模式类：，设,其中，,应具有性质,对样本进行规范化处理，即2类样本全部乘以(1)，则有：,感知器算法通过对已知类别的训练样本集的学习，寻找一个满足上式的权向量。,感知器算法步骤：,（1）选择N个分属于1和 2类的模式样本构成训练样本集 X1,XN 构成增广向量形式，并进行规范化处理。任取权向量初始 值W(1)，开始迭代。迭代次数k=1。,（2）用全部训练样本进行一轮迭代，计算WT(k)Xi 的值，并修 正权向量。,分两种情况，更新权向量的值：,c：正的校正增量。,分类器对第i个模式做了错误分类，,权向量校正为：,统一写为：,（3）分析分类结果：只要有一个错误分类，回到（2），直至 对所有样本正确分类。,分类正确时，对权向量“赏”这里用“不罚”，即权向量不变；分类错误时，对权向量“罚”对其修改，向正确的方向转换。,感知器算法是一种赏罚过程：,3.收敛性,收敛性：经过算法的有限次迭代运算后，求出了一个使所有样本都能正确分类的W，则称算法是收敛的。,可以证明感知器算法是收敛的。收敛条件：模式类别线性可分。,例3.8 已知两类训练样本,解：所有样本写成增广向量形式；进行规范化处理，属于2的样本乘以(1)。,用感知器算法求出将模式分为两类的权向量解和判别函数。,任取W(1)=0，取c=1，迭代过程为：,第一轮：,有两个WT(k)Xi 0的情况（错判），进行第二轮迭代。,第二轮：,第三轮：,第四轮：,该轮迭代的分类结果全部正确，故解向量,相应的判别函数为：,当c、W(1)取其他值时，结果可能不一样，所以感知器算法的解不是单值的。,判别界面d(X)=0如图示。,采用多类情况3的方法时，应有：,4.感知器算法用于多类情况,对于M类模式应存在M个判决函数：,算法主要内容：,设有 M 种模式类别：,设其权向量初值为：,第k次迭代时，一个属于i类的模式样本 X 被送入分类器，计算所有判别函数,训练样本为增广向量形式，但不需要规范化处理。,分二种情况修改权向量：,若第l个权向量使，则相应的权向量作调整，即：,可以证明：只要模式类在情况3判别函数时是可分的，则经过有限次迭代后算法收敛。,，c为正的校正增量,例3.9 设有三个线性可分的模式类，三类的训练样本分别为,若 则权向量不变；,现采用多类情况3的方式分类，试用感知器算法求出判别函数。,解：增广向量形式：,注意，这里任一类的样本都不能乘以（1）。,任取初始权向量,；c=1,第一次迭代：,三个权向量都需要修改：,第二次迭代：,第三次迭代：,修改为权向量。,以上进行的一轮迭代运算中，三个样本都未正确分类，进行下一轮迭代。,第四次迭代：,在第五、六、七迭代中，对所有三个样本都已正确分类。,权向量的解：,判别函数：,设函数f(Y)是向量 的函数，则f(Y)的梯度定义为：,3.6 梯度法,梯度的方向是函数 f(Y)在Y点增长最快的方向，梯度的模是f(Y)在增长最快的方向上的增长率(增长率最大值)。,1.梯度概念,梯度向量的最重要性质之一：指出函数 f 在其自变量增加时，增长最快的方向。,3.6.1 梯度法基本原理,显然：负梯度指出了最陡下降方向。梯度算法的依据。,即：,2.梯度算法,设两个线性可分的模式类1和2的样本共N个，2类样本乘(-1)。将两类样本分开的判决函数d(X)应满足：,梯度算法的目的仍然是求一个满足上述条件的权向量，主导思想是将联立不等式求解W的问题，转换成求准则函数极小值的问题。,N个不等式,准则函数的选取原则：具有唯一的最小值，并且这个最小值发生在W TXi0时。,用负梯度向量的值对权向量W进行修正，实现使准则函数达到极小值的目的。,定义一个对错误分类敏感的准则函数J(W,X)，在J的梯度方向上对权向量进行修改。一般关系表示成从W(k)导出W(k+1)：,其中c是正的比例因子。,（1）将样本写成规范化增广向量形式，选择准则函数，设置初始权向量W(1)，括号内为迭代次数k=1。,权向量修正为：,迭代次数k加1，输入下一个训练样本，计算新的权向量，直至对全部训练样本完成一轮迭代。,（3）在一轮迭代中，如果有一个样本使，回到(2)进行下 一轮迭代。否则，W不再变化，算法收敛。,（2）依次输入训练样本X。设第k次迭代时输入样本为Xi，此时 已有权向量W(k)，求：,例3.10 选择准则函数，简单地考虑X为一维增广模式的情况X=1，此时W=w，两者均为标量，,错误分类时：,，对权向量校正。,正确分类时：,，对权向量不做修正。,随着权向量W向理想值接近，准则函数关于W的导数()越来越趋近于零，这意味着准则函数J 越来越接近最小值。当 最终 时，J达到最小值，此时W不再改变，算法收敛。,将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题。,c)梯度算法是求解权向量的一般解法，算法的具体计算形式取决于准则函数J(W,X)的选择，J(W,X)的形式不同，得到的具体算法不同。,a),b)c值的选择很重要，如c值太小，收敛太慢；但若太大，搜索又可能过头，甚至引起发散。,3.6.2 固定增量法,准则函数：,求W(k)的递推公式：,1.求J的梯度,方法：函数对向量求导=函数对向量的分量求导，即,该准则函数有唯一最小值“0”，且发生在 的时候。,设，,部分：,首先求,另：矩阵论中有,其中,由的结论 有：,将 代入,得：,由此可以看出，感知器算法是梯度法的特例。即：梯度法是将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题，将原来有多个解的情况，变成求最优解的情况。,上式即为固定增量算法，与感知器算法形式完全相同。,即：,只要模式类是线性可分的，算法就会给出解。,线性分类器设计步骤,线性分类器设计任务：给定样本集K，确定线性判别函数g(x)=wTx的各项系数w。步骤：抽取类别标志明确的样本集合 K=x1,x2,xN作为训练样本集。确定一准则函数J(K,w)，其值反映分类器的性能，其极值解对应于“最好”决策。用最优化技术求准则函数J的极值解w*，从而确定判别函数，完成分类器设计。,对于未知样本x，计算g(x)，判断其类别。,4.2 Fisher线性判别,线性判别函数y=g(x)=wTx:样本向量x各分量的线性加权样本向量x与权向量w的向量点积如果|w|=1，则视作向量x在向量w上的投影 Fisher准则的基本原理：找到一个最合适的投影方向，使两类样本在该方向上投影之间的距离尽可能远，而每一类样本的投影尽可能紧凑，从而使分类效果为最佳。,Fisher线性判别图例,Fisher判别,x1,x2,w1,H:g=0,w2,Fisher准则的描述：用投影后数据的统计性质均值和离散度的函数作为判别优劣的标准。,d维空间样本分布的描述量,Fisher判别,各类样本均值向量mi,样本类内离散度矩阵Si与总类内离散度矩阵Sw,样本类间离散度矩阵Sb：,离散度矩阵在形式上与协方差矩阵很相似，但协方差矩阵是一种期望值，而离散矩阵只是表示有限个样本在空间分布的离散程度,一维Y空间样本分布的描述量,Fisher判别,各类样本均值,样本类内离散度和总类内离散度,样本类间离散度,以上定义描述d维空间样本点到一向量投影的分散情况，因此也就是对某向量w的投影在w上的分布。样本离散度的定义与随机变量方差相类似,Fisher准则函数定义的原则为，希望投影后，在一维空间中样本类别区分清晰，即两类距离越大越好，也就是类间离散度越大越好；各类样本内部密集，即类内离散度越小越好，根据上述准则，构造Fisher准则函数。,样本与其投影统计量间的关系,Fisher判别,类内离散度,Fisher准则函数,Fisher判别,评价投影方向w的原则，使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内尽可能密集的要求Fisher准则函数的定义：,Fisher最佳投影方向的求解,Fisher最佳投影方向的求解,Fisher判别,采用拉格朗日乘子算法解决,m1-m2是一向量，对与(m1-m2)平行的向量投影可使两均值点的距离最远。但是如从使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对m1-m2 向量按Sw-1作一线性变换，从而使Fisher准则函数达到极值点,判别函数的确定,前面讨论了使Fisher准则函数极大的d维向量w*的计算方法，判别函数中的另一项w0（阈值）可采用以下几种方法确定：,分类规则:,Fisher判别,Fisher公式的推导,Fisher判别,3.7 最小平方误差算法,（least mean square error,LMSE；亦称Ho-Kashyap算法）,上述的感知器算法、梯度算法、固定增量算法或其他类似方法，只有当模式类可分离时才收敛，在不可分的情况下，算法会来回摆动，始终不收敛。当一次次迭代而又不见收敛时，造成不收敛现象的原因分不清，有两种可能：,a)迭代过程本身收敛缓慢b)模式本身不可分,对可分模式收敛。对于类别不可分的情况也能指出来。,LMSE算法特点：,1.分类器的不等式方程,上式分开写为：,写成矩阵形式为：,令N(n+1)的长方矩阵为X，则,变为：,式中：,0为零向量,感知器算法是通过解不等式组，求出W。,2.LMSE算法,1)原理,的求解。式中：,两式等价。,为各分量均为较小正值的矢量。,LMSE算法把对满足 XW 0 的求解，改为满足,准则函数定义为：,“最小二乘”：最小：使方程组两边误差最小，也即使J最小。二乘：次数为2，乘了两次,考察向量(XWB)有：,可以看出：当函数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)求W(k+1)的迭代式,将(3-50)代入(3-47)式W=X#B 有：,总结：设初值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)求伪逆矩阵,求逆矩阵：,划去aij所在的行和列的元素，余下元素构成的行列式做aij的余子式，记作Mij，将 叫做元素aij的代数余子式。例：,代数余子式定义：,行列式:,(3)取 和 c=1 开始迭代：,解为 W(1)，判断函数为：,图示如下：,例3.12 已知模式训练样本：，,(2)求：,解：(1)规范化增广样本矩阵：,(3)取 和c=1，迭代：,用LMSE算法求解权向量。,e(1)全部分量为负，无解，停止迭代。为线性不可分模式。,小结：,(1)感知器法、梯度法、最小平方误差算法讨论的分类算法都是通过模式样本来确定判别函数的系数，所以要使一个分类器设计完善，必须采用有代表性的数据，训练判别函数的权系数。它们能合理反映模式数据的总体。,(2)要获得一个有较好判别性能的线性分类器，所需要的训练样本的数目的确定。,用指标二分法能力N0来确定训练样本的数目：,通常训练样本的数目不能低于N0，选为 N0的510倍左右。,二维：不能低于6个样本，最好选在3060个样本之间。三维：不能低于8个样本，最好选在4080个样本之间。,n为模式维数,如,3.8 非线性判别函数,3.8.1 分段线性判别函数,线性判别函数的特点：形式简单，容易学习；用于线性可分的模式类。非线性判别函数：用于线性不可分情况。分段线性、超曲面。,特点,基本组成为超平面。,*相对简单；*能逼近各种形状的超曲面。,1一般分段线性判别函数,设有M类模式，将i类（i=1,2,M）划分为li个子类：,其中第n个子类的判别函数：,i类的判别函数定义为：,M类的判决规则：,用各类判别函数进行分类判决实际是用各类选出的子类判别函数进行判决,判别面由各子类的判别函数决定,若i类的第n个子类和j类的第m个子类相邻，判别界面方程为：,子类之间的判别界面组成各类之间的判别界面,类间判别界面分段线性,2基于距离的分段线性判别函数,设 1类均值向量：,2类均值向量：,N1，N2：两类样本数。,任一模式X到M1和M2的欧氏距离平方：,判决规则：,判别界面方程：,1）最小距离分类器,化简得：,X的线性方程，确定一个超平面。,最小距离分类器,2）分段线性距离分类器,设：M类模式，其中i类划分为li个子类，第n个子类的均值向量为。每个子类的判别函数：,每类的判别函数：,判决规则：,若,则,3.8.2 分段线性判别函数的学习方法,1已知子类划分时的学习方法,*每个子类看成独立的类；*在一类范围内根据多类情况3，学习各子类判别函数；*继而得到各类判别函数。,2已知子类数目时的学习方法,用类似于固定增量算法的错误修正算法学习分段线性判别函数,3未知子类数目时的学习方法,树状分段线性分类器,树状分段线性分类器判别函数的学习及分类过程,暂停点,：,，,；,：,，,3.8.3 势函数法,1.势函数概念,划分属于1和2类模式样本：样本是模式空间中的点，将每个点比拟为点能源，在点上势能达到峰值，随着与该点距离的增大，势能分布迅速减小。1类样本势能为正势能积累形成“高地”；2类样本势能(-1)势能积累形成“凹地”；在两类电势分布之间，选择合适的等势面（如零等势面），即可认为是判别界面了。,借用点能源的势能概念解决模式分类问题。,一维情况示例,2.势函数法判别函数的产生,依次输入样本，利用势函数逐步积累势能的过程。,判别函数由模式空间中样本向量 的势函数K(X,Xk)累加产生，分类器计算积累势K(X)，最后取d(X)=K(X)。,设初始积累势函函数，下标为迭代次数。,势函数法：,第一步：加入训练样本 X1，,K1(X)描述了加入第一个样本后的边界划分。,第二步：加第二个训练样本X2，分三种情况：,分类正确，势函数不变：,，错误分类，修改势函数：,第k步：设Kk(X)为加入训练样本X1，X2，Xk后的积累势函数，则加入第k+1个样本，有：,以上决定积累位势的迭代算法可写为：,其中rk+1 为校正项系数，定义为：,(3-57),(3-58),从所给的训练样本集 中略去不使积累势发生变化的那些样本，可得一简化样本序列（校正错误的样本），算法可规纳为：,即：由(k+1)个训练样本产生的积累势，等于两类中校正错误 的样本的总势能之差。,式中，,(3-59),(3-60),从势函数算法可看出，积累势函数起着判别函数的作用，因此可直接用作判别函数，故取 d(X)=K(X)。由(3-57)式得：,式中rk+1按(3-58)式取值：,也可简写成：,式中 取值同(3-60)：,(3-61),两个n维向量 X 和 Xk 的函数K(X,Xk)，如同时满足下列三个条件，都可做为势函数：,3.势函数的选择,当向量 X 与 Xk 的距离趋于无穷时，K(X,Xk)趋于零。,K(X,Xk)是光滑函数，且是X与Xk之间距离的单调下降函数。,1）势函数应具备的条件,2）构成势函数的两种方法,式中，在模式定义域内应为正交函数集。,型势函数：用对称的有限项多项式展开，即：,a)内积：定义为，是一个实数。,“正交函数”概念：已知函数y(x)和z(x)，,b)正交：满足(y,z)=0。,例：,将这类势函数代入(3-61)式，有判别函数：,型势函数：直接选择双变量 X 和 Xk 的对称函数作为势函数，即，如：,(3-67),(3-68),曲线 c 含有正弦函数，具有振荡特点，只有第一个振荡周期可用。,式中 为正常数。,(3-66),图3.25 一维型势函数举例,例3.14 设两类训练样本集,样本分布如图所示。用型势函数进行分类，求判别函数。,解：两类模式不是线性可分的，这里选择指数型的势函，。二维情况下势函数为：,开始迭代：,式中，,第一步：,第二步：,分类正确,不修正。,第三步：,，分类错误，修正。,第四步：,分类错误，修正。,第五步：,，不修正。,第六步：,，修正。,第七步：,不修正。,第八步：,不修正。,第九步：,不修正。,第十步：,不修正。,从X7至X10的四次迭代中，所有训练样本皆被正确分类，故算法已收敛于判别函数，分类器设计完毕。,判别函数：,判别界面：d(X)=0,第七步：,第八步：,当训练样本的维数和数目较高时，需要计算和存储更多的指数项，但正因为判别函数由许多新项组成，故有很强的分类能力。,用型势函数构成判别函数的特点：,结束,