《模式识别课件总顺序No8第五章NO1杨雅双071120非线性判别.ppt》由会员分享，可在线阅读，更多相关《模式识别课件总顺序No8第五章NO1杨雅双071120非线性判别.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章 非线性判别函数非线性判别函数5.1 分段线性判别函数的基本概念分段线性判别函数的基本概念 n特殊的非线性判别函数特殊的非线性判别函数，其确定的决策面是由若干超平面若干超平面段段组成的。n它的基本组成仍是超平面仍是超平面，在超平面段较多段较多时，能逼近能逼近各种形状的超曲面超曲面。n图图5.1含线性判别函数、分段线性判别函数及二次判别函数。一、基于与类心距离的分段线性判别函数一、基于与类心距离的分段线性判别函数n根据前述可知。当类条件概率密度函数类条件概率密度函数为正态分布，各特征特征统计独立统计独立且方差相同方差相同时，Bayes决策规则具体为一个线性距线性距离判别函数离判别函数
2、，特别是当 时，决策规则为决策规则为：n注：X到到1的距离小于的距离小于(或大于或大于)X到到2的距离时的距离时,n为随机变量为随机变量X的数学期望的数学期望n决策面是两类期望（两类期望（“中心点中心点”）连线的垂直平分面）连线的垂直平分面。见图图5.2，称最小距离分类器最小距离分类器。n将均值（均值（“重心重心”或或“中心点中心点”）作为各类的代表点各类的代表点，用距距离作为判别函数进行分类离作为判别函数进行分类。n但是在一些情况下一些情况下，当类域是非单连通的或者一个类域有若干类域是非单连通的或者一个类域有若干个模式相对密集的区域个模式相对密集的区域。此时，若仍用每一类只取一个点代表若仍用
3、每一类只取一个点代表就不恰当了就不恰当了(因为这时若应用简单线性判别函数分类，则结果结果将会有很多错分将会有很多错分。)，而应用那些样本较密集的子区的中心样本较密集的子区的中心“联合联合”代表该类代表该类。n例如：例如：图图5.3，两类分布，类都是多峰分布。n方法方法1：若把 类的均值m1和m2作为代表类，得到分界面，则错分率较高错分率较高。n方法方法2：如果每类取多个代表点，如 类取两个代表点，m11，m12；类取三个代表点，m21，m22，m23。则得到分段线性分界面(其中每一段都是最小距离分类器每一段都是最小距离分类器)。n总之：总之：如果对于类取取li个代表点个代表点。也就是说，把属于
4、属于类的样本区域类的样本区域Ri分为分为li个子区域个子区域，即n其中Ril表示第表示第i类的第类的第l个子区域个子区域，用mil表示该子区域中样本表示该子区域中样本的的均值向量均值向量，且以此作为该子区域的代表点该子区域的代表点。则可定义如下可定义如下判别函数判别函数：n若有 则将X归到 类。分段线形距离分类器分段线形距离分类器二、分段线性判别函数二、分段线性判别函数1 引言：引言：前述的以每类（或分为若干子区域）的均值向量作为均值向量作为代表点代表点以设计最小距离分类器，在一些情况下不适用在一些情况下不适用。n例如。例如。图图5.4。各类样本服从正正态但非等协差分布态但非等协差分布，其概率
5、密度面为超椭球面，以Bayes决策规则对样本进行分类时，应为应为 类类，但若以以i作为作为代表点，并按代表点，并按i的欧式距离进的欧式距离进行分类行分类，则则 类类。2 将每一类分为若干个子类将每一类分为若干个子类，即令然后，对每一个子类定义一个线性判别函数每一个子类定义一个线性判别函数，式中 分别称为对子类对子类 的权向量和阈值权的权向量和阈值权。如果定义定义 类的线性判别函数为类的线性判别函数为：则对于c类问题，可以定义c个判别函数gi()(i=1,.,c)，并得到决策规则，即：n说明：说明：先找到具有最大判别函数值的子类最大判别函数值的子类（设为gin()），则把样本归到子类归到子类 所
6、属的类所属的类，即 类。这样得到的决策面也是分段线性的分段线性的，其决策面方程决策面方程是由各各子类的判别函数确定的子类的判别函数确定的。如果第i类的第第n个子类个子类和第第m个子类个子类相邻相邻，则该段决策面决策面方程是：方程是：三、分段线性分类器设计的一般考虑三、分段线性分类器设计的一般考虑 1 利用多类线性判别函数算法设计分段线性分类器利用多类线性判别函数算法设计分段线性分类器 在已知样本的子类划分已知样本的子类划分情况下，则可把子类看作独立的把子类看作独立的类类，然后利用不同方法不同方法/算法把各个子类分开算法把各个子类分开。2 已知子类数目时的分段线性判别函数已知子类数目时的分段线性
7、判别函数在已知子类数目，而不知子类划分已知子类数目，而不知子类划分情况下，有一种称为错误修正算法错误修正算法来设计分段线性分类器，其步骤如下步骤如下：Step1：任意给定各子类的初始权向量：任意给定各子类的初始权向量。设 类中有li个子类，则任意给定 Step2：利用训练样本集进行迭代，并按下列规则修改权向量。：利用训练样本集进行迭代，并按下列规则修改权向量。若在第k次迭代时，类中的样本j与 类的某个权向量 的內积值为最大內积值为最大。即 而且满足：，其中i=1,2,c；ij；l=1,2,li。则说明权向量组 不影响i正确分类，则各权向量保持不变各权向量保持不变。但如果存在某个或几个子类不满足
8、上述条件子类不满足上述条件，即存在 ，使得：则说明j被错误分类被错误分类，这时需要对权向量进行修正需要对权向量进行修正。设 则修正算法为：则修正算法为：Step3：重复第二步，直到算法收敛收敛，或达到规定的时限规定的时限，或达到规定的迭代次数次数为止。3 未知子类数目时的分段线性判别函数未知子类数目时的分段线性判别函数方法很多，以树状树状分段线性分离器为例。见图5.5（两类）先用两类线性判别函数算法找一个权向量找一个权向量a1，其所对应的超平面H1将整个样本集分成两部分分成两部分（即样本子集样本子集）。因为每一部分仍含两类样本每一部分仍含两类样本，所以接着找出第二、三、找出第二、三、四个权向量
9、四个权向量a2、a3、a4，对应的超平面H2、H3、H4分别把相应的样本子集分成两部分样本子集分成两部分。这时把两类样本完全分开。这样得到的分类器显然是分段线性的分段线性的，其决策面如图5.5所示。这种情况下的识别过程是一个树状结构。见图5.6。图中用虚线显示了对未知样本未知样本的决策过程，经过经过3步，步，判得判得说明：说明：此方法对初始权向量的选择很敏感初始权向量的选择很敏感，其结果随初始权向量的不同而大不相同。在每个节点上所用的寻找权向量寻找权向量ai的方法不同，结的方法不同，结果也将各异果也将各异。图5.6 与图5.5对应的树状决策过程5.2 用凹函数的并表示分段线性判别函数用凹函数的
10、并表示分段线性判别函数 一、分段线性判别函数的表示一、分段线性判别函数的表示1.凹函数的定义凹函数的定义 设Li是线性函数是线性函数（i=1，2，.，r），则分段线性函数可分段线性函数可定义定义如下：L1,L2,.,Lr都是分段线性函数。和 也是分段线性函数，式中 表示取取小小；表示取大取大。分段线性函数只有上述只有上述和和形式形式。(2)分段线性函数的一般表达式分段线性函数的一般表达式n析取范式析取范式n合取范式合取范式n对于析取范式P中的每个中的每个称为一个凹函数凹函数。所以P是是q个凹函数的并个凹函数的并，即在q个凹函数中求最大的凹最大的凹函数函数（因为 是求最大）2.使用凹函数的并完成
11、分类使用凹函数的并完成分类 n对于多峰分布的两类问题多峰分布的两类问题，设P中的每个凹函数每个凹函数（粗略的）确定了某个类的一个峰一个峰。若此类呈现呈现q个峰的分布个峰的分布，则P由由q个凹函数个凹函数Pi的的并并并并构成构成，记为:而每个凹函数Pi又是由mi个线性判别函数个线性判别函数Lij的的交交交交构成。即 再设对于设对于 每个都设计成使每个都设计成使 则r个权向量个权向量a1,ar就能对样本集正确分类就能对样本集正确分类，n决策决策(判别判别)规则为：规则为：n说明：说明：分段线性判别函数P是样本集和权向量的函数。n例如：例如：参照图5.7。两类问题。o表示表示 类，类，x表示表示 类
12、，类，对于对于 类类，有3个子类（即q=3），对于每个子类分别有5、4、4个分段线性函数（即m1=5，m2=4，m3=4）。即共有13个线性判别函数。则分段线性判别函数分段线性判别函数P为：为：或写成取大取小取大取小形式。二、算法描述n见书P1265.3 用交遇区的样本设计分段线性分类器用交遇区的样本设计分段线性分类器一、引言一、引言n实际中，有时类域的形状比较复杂，凹凸交替凹凸交替，并且两类靠两类靠的较近的较近，甚至还可能部分重叠部分重叠。我们将两类模式十分靠近十分靠近或重叠混杂的区域重叠混杂的区域称为交遇区交遇区交遇区交遇区，如图5.10中的a，c交迭区，b靠近区。对此情况不能简单的使用全
13、部训练样本全部训练样本进行训练来产生线性判别函数，应对那些交遇区十分“精细精细”地对待，取出取出交遇区中的训练样本交遇区中的训练样本，用这些局部训练样本局部训练样本产生“局部局部”的的线性判别函数线性判别函数，再由这些线性判别函数构成构成分段线性判别函分段线性判别函数数。n这种方法使组成分段线性函数的线性函数最少线性函数最少。n这种方法涉及以下几个基本问题几个基本问题：找出交遇区找出交遇区 由交遇区中的样本产生线性判别函数由交遇区中的样本产生线性判别函数 分类决策分类决策二、寻找交遇区和紧互对原型对二、寻找交遇区和紧互对原型对1.何为交遇区和紧互对原型对何为交遇区和紧互对原型对n设两类两类下，
14、有对应的两个样本集两个样本集1和和2（即1对应对应 1类，类，2对应对应 2类类）。n先用聚类分析先用聚类分析方法将每类分成若干个子聚类每类分成若干个子聚类。每个子聚类每个子聚类在在中占据一定区域中占据一定区域，称为“原型区原型区原型区原型区”；每个子聚类的每个子聚类的“重重心心”或或“类心类心”，或最靠近类心的，或最靠近类心的一个样本一个样本称为该子聚类该子聚类的的“原型原型”.n这时，每个每个子聚类子聚类可用它的可用它的原型原型表示表示，而每一类每一类则可由这类的全部原型全部原型来表示。n而交遇区的表示就是用这些原型来实现的交遇区的表示就是用这些原型来实现的。n令Vi表示表示 i类的原型集
15、合类的原型集合 式中：vij（j=1，li）为 i类的类的第第j个个原型原型，li为为 i类中的类中的原型原型个数个数。n我们用 表示一个互对的原型对一个互对的原型对。n用 表示两个互对的原型之间的欧式距离两个互对的原型之间的欧式距离，而当且当且仅当仅当满足满足 时，称为紧互对原型对紧互对原型对（必须是不同类的原型不同类的原型）。其意义参见图图5.11。2.寻找紧互对原型对集合寻找紧互对原型对集合R的算法步骤的算法步骤Step1：对于每一个原型 ，在在 中找出离它最近的原型中找出离它最近的原型v2n（v1m）。记作集合（m=1，2，l1）Step2：对于每一个原型 ，在在 中找出离它最近的原中
16、找出离它最近的原型型v1m（v2n）。记作集合：（n=1，2，l2）Step3：找出的交集，即为交集，即为R，n显然，中的紧互对原型对都位于两类样本的交遇区交遇区，所以用紧互对原型对集合表示交遇区是可行的用紧互对原型对集合表示交遇区是可行的。n可将紧互对原型对的概念扩展概念扩展。对于一类中的一个原型一类中的一个原型用类似的方法可找出可找出另一类另一类原型中的原型中的最近的最近的k个原型个原型，产生的结果称为k-紧互对原型对集合紧互对原型对集合，记为 。三、用局部训练样本产生分段线性判别函数三、用局部训练样本产生分段线性判别函数n找出找出k-紧互对原型对集合紧互对原型对集合后，则就可据此确定局部
17、超平面局部超平面，方法如下：Step1：在k-紧互对原型对集合中紧互对原型对集合中找出最近的一对最近的一对 ，可选择 连线的垂直平分面连线的垂直平分面作为初始化分界面初始化分界面H1，H1的方程为：Step2：以H1作为初始超平面，找出找出H1正确分类的紧互对正确分类的紧互对原型对原型对，用这些原型所代表的聚类中的所有样本所有样本作为局部训局部训练样本集练样本集，并由此产生第一个超平面段H1*，如果用用H1*正正确分类的紧互对原型对确分类的紧互对原型对与与H1正确分类的紧互对原型对相同正确分类的紧互对原型对相同，则H1*就是所求的第一段超平面就是所求的第一段超平面H1；若不完全相同，再以H1*
18、作为初始超平面，重复上述过程，直至得到H1。Step3：将被：将被H1正确分类的紧互对原型对除外正确分类的紧互对原型对除外，对剩下的紧互对原型对重复Step1和Step2，以得到新的超平面H2。Step4：重复上述步骤，直至所有的紧互对原型对被处理完为所有的紧互对原型对被处理完为止止，则得到一组超平面得到一组超平面H1，H2，Hm。四、决策规则四、决策规则n假设分段线性判别函数是由m个超平面个超平面Hi(i=1,m)组成组成。对于每个样本每个样本X，若设 则由由m个超平面可以产生一个个超平面可以产生一个m维分量取维分量取0，1的向量的向量Z(X).对于原始的全部全部n个样本个样本，可得到n个向量个向量 m维二值向量，最多有2m种可能的选择。每个Z(Xk)（k=1,n）只能是只能是2m种向量之一种向量之一。n对于这2m种可能的向量种可能的向量，统计其在两类样本集在两类样本集1和和2中出现中出现的次数的次数，并分别记为 n对于待分样本待分样本Xj，当 都很小很小，则令n当 都很大且二者差别较小很大且二者差别较小时，则令 n不是上述两种情况时，则令则得到决策规则为：