模式识别导论(二)

§2-1判别函数§2-2线性判别函数§2-3线性判别函数的性质§2-4广义线性判别函数§2-5非线性判别函数第二章

判别函数2023/2/4湖南大学电气与信息工程学院*假设对一模式X已抽取n个特征，表示为：模式识别问题就是根据模式X的n个特征来判别模式属于ω1,ω2,

…,

ωm

类中的那一类。§2-1判别函数

2023/2/4湖南大学电气与信息工程学院*例如下图：三类的分类问题，它们的边界线就是一个判别函数§2.1判别函数（续)2023/2/4湖南大学电气与信息工程学院*判别函数包含两类：一类是线性判别函数：线性判别函数广义线性判别函数所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数分段线性判别函数另一类是非线性判别函数§2.1判别函数（续）2023/2/4湖南大学电气与信息工程学院*§2-2线性判别函数我们现在对两类问题和多类问题分别进行讨论。(一)两类问题即:

1.二维情况：取两个特征向量这种情况下判别函数:2023/2/4湖南大学电气与信息工程学院*在两类别情况，判别函数g

(x)

具有以下性质：这是二维情况下判别由判别边界分类.情况如图：1.二维情况2023/2/4湖南大学电气与信息工程学院*2.n维情况现抽取n个特征为：判别函数：

另外一种表示方法：2023/2/4湖南大学电气与信息工程学院*模式分类：当g1(x)=WTX=0为判别边界。当n=2时，二维情况的判别边界为一直线。当n=3时，判别边界为一平面，n>3时，则判别边界为一超平面。2.n维情况2023/2/4湖南大学电气与信息工程学院*(二)

多类问题对于多类问题，模式有ω1,ω2,

…,

ωm

个类别。可分三种情况：1.第一种情况：每一模式类与其它模式类间可用单个判别平面把一个类分开。这种情况，M类可有M个判别函数，且具有以下性质：2023/2/4湖南大学电气与信息工程学院*右图所示，每一类别可用单个判别边界与其它类别相分开。如果一模式X属于ω1，则由图可清楚看出:这时g1(x)>0而g2(x)<0

，g3(x)<0

。ω1

类与其它类之间的边界由g1(x)=0确定.1.第一种情况2023/2/4湖南大学电气与信息工程学院*例：已知三类ω1,ω2,ω3的判别函数分别为：因此三个判别边界为：1.第一种情况（续）2023/2/4湖南大学电气与信息工程学院*作图如下：1.第一种情况（续）2023/2/4湖南大学电气与信息工程学院*对于任一模式X如果它的g1(x)>0，g2(x)<0，g3(x)<0则该模式属于ω1类。相应ω1类的区域由直线-x2+1=0

的正边、直线-x1+x2-5=0

和直线-x1+x2=0的负边来确定。1.第一种情况（续）2023/2/4湖南大学电气与信息工程学院*必须指出，如果某个X使二个以上的判别函数gi(x)>0。则此模式X就无法作出确切的判决。如图中

IR1,IR3，IR4区域。另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确定区域。1.第一种情况（续）2023/2/4湖南大学电气与信息工程学院*问当x=(x1,x2)T=(6,5)T时属于那一类结论：g1(x)<0，g2(x)>0，g3(x)<0所以它属于ω2类1.第一种情况（续）2023/2/4湖南大学电气与信息工程学院*这样有M(M_1)/2个判别平面。对于两类问题，M=2，则有一个判别平面。同理，三类问题则有三个判别平面。

判别函数：判别边界：判别条件：2.第二种情况每个模式类和其它模式类间可分别用判别平面分开。2023/2/4湖南大学电气与信息工程学院*判别函数性质：假设判别函数为：判别边界为：2.第二种情况（续）用方程式作图：2023/2/4湖南大学电气与信息工程学院*问:未知模式X=(x1,x2)T=(4,3)T属于那一类代入判别函数可得:把下标对换可得:因为结论：所以X属于ω3类结论：判别区间增大，不确定区间减小，比第一种情况小的多.2.第二种情况（续）2023/2/4湖南大学电气与信息工程学院*3.第三种情况判别函数：

判别规则：判别边界：gi(x)=gj(x)

或gi(x)-gj(x)

=0就是说，要判别模式X属于那一类，先把X代入M个判别函数中，判别函数最大的那个类别就是X所属类别。类与类之间的边界可由gi(x)=gj(x)

或gi(x)-gj(x)

=0来确定。每类都有一个判别函数,存在M个判别函数2023/2/4湖南大学电气与信息工程学院*右图所示是M=3的例子。对于ω1类模式，必然满足g1(x)>g2(x)

和g1(x)>g3(x)

。假设判别函数为：则判别边界为：3.第三种情况（续）2023/2/4湖南大学电气与信息工程学院*结论：不确定区间没有了，所以这种是最好情况。用上列方程组作图如下：3.第三种情况（续）2023/2/4湖南大学电气与信息工程学院*问假设未知模式x=(x1,x2)T=(1,1)T

，则x属于那一类。把它代入判别函数：得判别函数为：因为所以模式x=(1,1)T属于类。3.第三种情况（续）2023/2/4湖南大学电气与信息工程学院*§2-3线性判别函数的性质1.模式空间与加权空间模式空间：由构成的n维欧氏空间。W是此空间的加权向量，它决定模式的分界面H，W与H正交。加权空间：以为变量构成的欧氏空间模式空间与加权空间的几何表示如下图：2023/2/4湖南大学电气与信息工程学院*模式空间2023/2/4湖南大学电气与信息工程学院*2023/2/4湖南大学电气与信息工程学院*1.模式空间与加权空间（续）2023/2/4湖南大学电气与信息工程学院*该式表示一个通过加权空间原点的平面，此平面就是加权空间图中的平面①,同样令g

(x2)=g

(x3)=g

(x4)=0，分别作出通过加权空间原点的平面②③④图中用阴影表示的部分是各平面的正侧。加权空间的构造：设是加权空间分界面上的一点，代入上式得：1.模式空间与加权空间2023/2/4湖南大学电气与信息工程学院*这是一个不等式方程组，它的解处于由ω1类所有模式决定的平面的正边和由ω2类所有模式决定的平面的负边，它的解区即为凸多面锥。如图所示：(b)为加权空间，（c）为正规化后的加权空间。由上可以得到结论：加权空间的所有分界面都通过坐标原点。这是加权空间的性质。为了更清楚，下面用二维权空间来表示解向量和解区。1.模式空间与加权空间（续）2023/2/4湖南大学电气与信息工程学院*在三维空间里，令w3

=0

则为二维权空间。如图：给定一个模式X，就决定一条直线：即分界面H，W与H正交，W称为解向量。解向量的变动范围称为解区。因x1,x2∈ω1，x3,x4∈ω2由图可见x1,x3离的最近，所以分界面H可以是x1,x3之间的任一直线，由垂直于这些直线的W就构成解区，解区为一扇形平面，即阴影区域。如右图:2.解向量和解区2023/2/4湖南大学电气与信息工程学院*把不等式方程正规化：正规化：2.解向量的解区（续）2023/2/4湖南大学电气与信息工程学院*g(x)=WTX=0决定一个决策界面，当g(x)为线性时，这个决策界面便是一个超平面H，并有以下性质：性质①：W与H正交（如图所示）假设x1,x2是H上的两个向量所以W

与(x1-x2)

垂直，即W与H正交。一般说，超平面H把特征空间分成两个半空间。即Ω1,Ω2空间，当x在Ω1空间时g(x)>0,W指向Ω1，为H的正侧，反之为H的负侧.3.超平面的几何性质2023/2/4湖南大学电气与信息工程学院*Ω1Ω2g(x)>0g(x)<03.超平面的几何性质2023/2/4湖南大学电气与信息工程学院*矢量到H的正交投影与值成正比其中：x

p：x在H

的投影向量，r是x

到H

的垂直距离。是W方向的单位向量。3.超平面的几何性质（续）性质②：2023/2/4湖南大学电气与信息工程学院*另一方面:3.超平面的几何性质（续）这是超平面的第二个性质，矢量x到超平面的正交投影正比与g(x)的函数值。2023/2/4湖南大学电气与信息工程学院*性质③：3.超平面的几何性质（续）2023/2/4湖南大学电气与信息工程学院*性质④：3.超平面的几何性质（续）2023/2/4湖南大学电气与信息工程学院*一组模式样本不一定是线性可分的，所以需要研究线性分类能力的方法，对任何容量为N的样本集，线性可分的概率多大呢？（如下图（a），线性不可分）例：4个样本有几种分法。图（b）①直线把x1分开，每条直线可把4个样本分成ω1

ω2

类，4个样本分成二类的总的可能的分法为24=16类，其中有二种是不能用线性分类实现的线性可分的是14。即概率为14/16。4.二分法能力（a）x1x2x3x4⑥

③

②

④

⑤

⑦

（b）2023/2/4湖南大学电气与信息工程学院*结论：N个样品线性可分数目(条件：样本分布良好）：4.二分法能力（续）对N和n各种组合的D(N,n)值，表示在下表中，从表中可看出，当N，n缓慢增加时D(N,n)却增加很快。2023/2/4湖南大学电气与信息工程学院*12345612222222444444368888848141616161651022303232324.二分法能力（续）线性可分概率：2023/2/4湖南大学电气与信息工程学院*把上式用曲线表示成下图：图中横坐标用λ=N/n+1表示。由图讨论：4.二分法能力（续）2023/2/4湖南大学电气与信息工程学院*结论：在实际工作中，分类的训练非常重要，由已知样本来训练。因为已知样本有限，而未知样本无限。选择已知类别的训练样本数方法如下：4.二分法能力（续）2023/2/4湖南大学电气与信息工程学院*①：如果训练样本N

<N0，设计分类器的分类能力太差，因为训练样本太少。②：如果训练样本N太多时，则样本太多，运算量、存储量太大。③：因此实际工作中应该取：②4.二分法能力（续）2023/2/4湖南大学电气与信息工程学院*§2-4广义线性判别函数这样一个非线性判别函数通过映射，变换成线性判别函数。判别函数的一般形式：2023/2/4湖南大学电气与信息工程学院*§2-4广义线性判别函数（续）例：如右图。2023/2/4湖南大学电气与信息工程学院*§2-4广义线性判别函数（续）要用二次判别函数才可把二类分开：ω2ω1ω22023/2/4湖南大学电气与信息工程学院*§2-4广义线性判别函数（续）从图可以看出：在阴影上面是ω1类，在阴影下面是ω2类，结论：在X空间的非线性判别函数通过变换到Y空间成为线性的，但X变为高维空间ω2ω1ω22023/2/4湖南大学电气与信息工程学院*1.分段线性判别函数（用线性无法分开,可用分段线性判别函数）

①、基于距离的分段线性判别函数。（用均值代表一类，通过均值连线中点的垂直线分开）把ωi类可以分成li个子类:∴分成l个子类。现在定义子类判别函数：在同类的子类中找最近的均值。判别规则：这是在M类中找最近均值。则把x归于ωj类完成分类。§2-5非线性判别函数Ⅱ

Ⅲ

2023/2/4湖南大学电气与信息工程学院*§2-5非线性判别函数（续）例：未知x,如图：先与ω1类各子类的均值比较，即，找一个最近的与ω2各子类均值比较取最近的因g2(x)<g1(x)，所以x∈ω2类。2023/2/4湖南大学电气与信息工程学院*设ω＝ω1,

ω2

,……ωm而每一类又可以分为子类。对每个子类定义一个线性判别函数为：则定义ωi类的线性判别函数为：②、基于函数的分段线性判别函数利用均值代表一类有时有局限性，如图所示。若用线性判别函数代表一类，就会克服上述情况。1.分段线性判别函数2023/2/4湖南大学电气与信息工程学院*在各子类中找最大的判别函数作为此类的代表，则对于M类，可定义M个判别函数gi(x),i=1,2,…..M,因此，决策规则：对未知模式x，把x先代入每类的各子类的判别函数中，找出一个最大的子类判别函数，M类有M个最大子类判别函数，在M个子类最大判别函数中，再找一个最大的，则x就属于最大的子类判别函数所属的那一类。1.分段线性判别函数（续）2023/2/4湖南大学电气与信息工程学院*③、基于凹函数的并分段线性判别函数（针对多峰情况）设li子类判别函数，i=1,2,…..r则分段线性判别函数有如下特性：1.分段线性判别函数（续）(a)：l1,l2,……lr都是分段线性判别函数(b)：