第2章-线性判别函数法

第2章判别函数及几何分类法2.1判别函数2.2线性判别函数2.3广义线性判别函数2.4线性判别函数的几何性质2.5感知器算法2.6梯度法2.7最小平方误差算法2.8非线性判别函数2.1判别函数聚类分析法（第6章）判决函数法几何分类法[确定性事件分类]（第2章）概率分类法[随机事件分类]（第3章）线性判决函数法统计决策方法非线性判决函数法复习与引申：模式识别统计若分属于ω1，ω2的两类模式可用一方程d(X)=0来划分，那么称d(X)为判别函数，或称判决函数、决策函数。2.1判别函数(discriminantfunction)直接用来对模式进行分类的准则函数。例：一个二维的两类判别问题，模式分布如图示，这些分属于ω1，ω2两类的模式可用一直线方程d(X)=0来划分。0)(32211wxwxwdX21,xx为坐标变量，321,,为方程参数。式中：图2.2两类二维模式的分布1．判别函数的定义0)(Xd2x1xO12＋－若，则若，则类；若，则类；0)(Xd1X0)(Xd2X0)(Xd21ωωXX或或拒绝将某一未知模式X代入：维数=3时：判别边界为一平面。维数3时：判别边界为一超平面。32211)(wxwxwdX0)(Xd2x1xO12＋－d(X)表示的是一种分类的标准，它可以是1、2、3维的，也可以是更高维的。判别界面的正负侧，是在训练判别函数的权值时确定的。2．判别函数正负值的确定122x1xO0)(Xd－＋图2.3判别函数正负的确定1）判决函数d(X)的几何性质。它可以是线性的或非线性的函数，维数在特征提取时已经确定。如：已知三维线性分类——判决函数的性质就确定了判决函数的形式：4332211)(wxwxwxwdX3.确定判别函数的两个因素例：非线性判决函数2）判决函数d(X)的系数。用所给的模式样本确定。2x1xO2x1xO2.2线性判别函数2.2.1线性判别函数的一般形式将二维模式推广到n维，线性判别函数的一般形式为：T1122nn00dwxwxwxwwXWX(2-2)T21,....,,nxxxX式中：1122nn012T12011nndwxwxwxwxxLLMXWXT120,,....,,nWT211,,....,,nxxxX增广向量的形式：式中：为增广权向量，为增广模式向量。T12,,...,nW权向量2.2.2线性判别函数的性质21T,0,0)(XXXWX若若d1.两类情况d(X)=0：不可判别情况，可以或拒绝或21XX）对M个线性可分模式类，ω1，ω2，…ωM，有三种划分方式：2.多类情况ii两分法ji两分法ji两分法特例ii两分法(1)多类情况1：用线性判别函数将属于ωi类的模式与其余不属于ωi类的模式分开。将某个待分类模式X分别代入M个类的d(X)中，若只有di(X)0，其他d(X)均0，则判为ωi类。识别分类时：Midiiii，，若若1,0,0)(TXXXWX全部＜０不属任何类IR，可能属于1或31230)(2Xd0)(3XdIR，可能属于3或2---0)(1Xd0,,0312ddd0,,0321ddd0,0,321dddIR，可能属于1或20,,0213ddd2x1x对某一模式区，di(X)0的条件超过一个，或全部的di(X)0，分类失效。相当于不确定区(indefiniteregion，IR)。此法将M个多类问题分成M个两类问题，识别每一类均需M个判别函数。识别出所有的M类仍是这M个函数。例2.1设有一个三类问题，其判别式为：1)(211-xxXd4)(212-xxdX1)(23-xdX现有一模式，X=[7,5]T，试判定应属于哪类？并画出三类模式的分布区域。01157)(1--Xd08457)(2-Xd0415)(3--Xd解：将X=[7,5]T代入上三式，有：23120)(),(,0)(XXXXddd0121-xx0421-xx012-x三个判别界面分别为：图示如下：10-112x1x0)(2Xd0)(3Xd(10)Xd44---0022其他：d0033其他：d0011其他：d)5,7(步骤：a)画出界面直线。b)判别界面正负侧：找特殊点带入。c)找交集。1)(211-xxdX4)(212-xxdX1)(23-xdX0)(3Xd+—例2.2已知di(X)的位置和正负侧，分析三类模式的分布区域。—0)(1Xd+0)(2Xd+—231ji两分法(2)多类情况2：一个判别界面只能分开两个类别，不能把其余所有的类别都分开。判决函数为：。这里。XWXT)(ijijdijjidd-在M类模式中，与i有关的M-1个判决函数全为正时，X∈ωi。其中若有一个为负，则为IR区。则类，而在判别类模式时不起作用。1X)(23Xd1如：对一个三类问题，如果，0)(12Xd0)(13Xd识别分类时：iijMjiijdXX若,,,2,1,;,0判别函数性质：122x1x--003231dd001312dd002321dd3-d23(X)=0d12(X)=0d13(X)=0IR000231312ddd5)(2112--xxdX3)(113-xdX2123)(xxd-X3T32313,40)(0)(XXXdd与值无关。)(12Xd例2.3一个三类问题，三个判决函数为：T]3,4[X问模式属于哪类？1)(,1)(2313--XXdd解：计算得,2)(12-Xd1)(,1)(3231XXdd可写成：,2)(21Xd(4,3)x2x1d23(X)=0d12(X)=0d13(X)=05530方法一：图示法方法二5)(2112--xxdX3)(113-xdX2123)(xxd-X122x1x--003231dd001312dd002321dd3-d23(X)=0d12(X)=0d13(X)=0IR000231312ddd55302x1x0)(12Xd0)(13Xd---O0)(23Xd3!212-MMCM分类时：每分离出一类，需要与I有关的M-1个判决函数；要分开M类模式，共需M(M-1)/2个判决函数。对三类问题需要3(3-1)/2=3个判决函数。即：每次从M类中取出两类的组合：例2.4已知dij(X)的位置和正负侧，分析三类模式的分布区域。21当ωi/ωj两分法中的判别函数dij(X)，可以定义为XXXjiijddd-)(时，那么di(X)dj(X)就相当于多类情况2中的dij(X)0。ji两分法特例(3)多类情况3：因此对具有判别函数Midii,,1,)(TXWX的M类情况，判别函数性质为：ijiMjiijddXXX若,,,2,1,;,)(或：ikiMkddXXX若,,,1,max)(识别分类时：判别界面需要做差值。对ωi类，应满足：di其他所有dj2313dddd0122x1x0)(21-XdXd---0)(31-XdXd0)(32-XdXd3212dddd3121dddd3②除边界区外，没有不确定区域。特点：①是第二种情况的特例。由于dij(X)=di(X)－dj(X)，若在第三种情况下可分，则在第二种情况下也可分，但反过来不一定。2313dddd0122x1x0)(21-XdXd---0)(31-XdXd0)(32-XdXd3212dddd3121dddd3③把M类情况分成了(M-1)个两类问题。并且类的判别界面全部与类的判别界面相邻（向无穷远处延伸的区域除外）。iijj特别的定义23212211)(1)()(xdxxdxxd---XXX例2.5一个三类模式（M=3）分类器，其判决函数为：试判断X0=[1,1]T属于哪一类，且分别给出三类的判决界面。解：①2003020102030201)()()()(1)(1111)(011)(---XXXXXXXXddddddd012)()(121--xddXX02)()(2131--xxddXX012)()(112--xddXX012)()(2132--xxddXX)()(1331XXdd-)()(2332XXdd-类的判决函数：1②判决界面如图所示。类的判决函数：2类的判决函数：3-0)(21-XdXd2313dddd0.5x2--0)(31-XdXd0)(32-XdXd3212dddd3121dddd110.5123x1-O2x1x0)(21-XXdd--0)(31-XXdd0)(32-XXdd例2.6已知判决界面的位置和正负侧，分析三类模式的分布区域。132(1)明确概念：线性可分。一旦线性判别函数的系数Wk被确定以后，这些函数就可以作为模式分类的基础。3.小结(2)分法的比较：jiii与对于M类模式的分类，两分法共需要M个判别函数，但两分法需要M(M-1)/2个。当时M3时，后者需要更多个判别式（缺点），但对模式的线性可分的可能性要更大一些（优点）。jiii原因：一种类别模式的分布要比M-1类模式的分布更为聚集，分法受到的限制条件少，故线性可分的可能性大。jiii两分法全部＜０不属任何类IR，可能属于1或31230)(2Xd0)(3XdIR，可能属于3或2---0)(1Xd0,,0312ddd0,,0321ddd0,0,321dddIR，可能属于1或20,,0213ddd2x1x若只有di(X)0，其他d(X)均0，则判为ωi类ji两分法:iijMjiijdXX若,,,2,1,;,0122x1x--003231dd001312dd002321dd3-d23(X)=0d12(X)=0d13(X)=0IR000231312dddji两分法特例XXXjiijddd-)(定义()max,1,,,ikiddkML若XXX2313dddd0122x1x0)(21-XdXd---0)(31-XdXd0)(32-XdXd3212dddd3121dddd3除边界之外不存在不确定区域1．非线性多项式函数非线性判别函数的形式之一是非线性多项式函数。2.3广义线性判别函数目的：对非线性边界：通过某映射，把模式空间X变成X*，以便将X空间中非线性可分的模式集，变成在X*空间中线性可分的模式集。设一训练用模式集，{X}在模式空间X中线性不可分，非线性判别函数形式如下：1nnn2211wxwxwxwdX(2-9)12211kkkwfwfwfwdXXXX11kiiifwX式中是模式X的单值实函数，。kifi,,2,1,X11Xkffi(X)取什么形式及d(X)取多少项，取决于非线性边界的复杂程度。广义形式的模式向量定义为：(2-10)T21T**2*11,,,,]1,,,,[XXXXkkfffxxx这里X*空间的维数k高于X空间的维数n，(2-9)式可写为上式