判别函数及几何分类法.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 ，分类失效。 相当于不确定区(indefinite region ，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,