信息工程学院
§ 2-1、判别函数
§ 2-2、线性判别函数
§ 2-3、线性判别函数的性质
§ 2-4、广义线性判别函数
§ 2-5、非线性判别函数第二章 判别函数信息工程学院
假设对一模式 X已抽取 n个特征，表示为：
模式识别问题就是根据模式 X的 n个特征来判别模式属于 ω1,ω2,…,ωm 类中的那一类。
§ 2-1 判别函数维空间的一个向量是 n
),..,,,,( 321
X
xxxxX Tn?
信息工程学院
例如下图：三类的分类问题，它们的边界线就是一个判别函数
1?
2?
3?边界
2x
1x
§ 2.1 判别函数（续
）
信息工程学院
判别函数包含两类：
一类 是线性判别函数：
线性判别函数
广义线性判别函数
（所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数）
分段线性判别函数
另一类是非线性判别函数
§ 2.1 判别函数（续
）
信息工程学院
§ 2-2 线性判别函数
我们现在对两类问题和多类问题分别进行讨论。
(一 )两类问题 即,
1,二维情况,取两个特征向量
这种情况下 判别函数,
2,),( 21 MTi
2,)( 2,1 nxxX T
32211 wxwxw)x(g
为坐标向量为参数,21,xxw
信息工程学院
在两类别情况，判别函数 g (x) 具有以下性质,
这是二维情况下判别由判别边界分类,
情况如图：
1,二维情况
2
1
,0
,0)(
X
Xxg
i
不定Xxg,0)(?
32211)( wxwxwxg
2?
1?
1x
2x
信息工程学院
2,n维情况
现抽取 n个特征为：
判别函数：
另外一种表示方法：
TnxxxxX ),...,,( 321?
12211,,,,,,)( nnn wxwxwxwxg
10 nwXW
为增值模式向量。，＝
为增值权向量，
T
nn
T
nn
xxxxX
wwwwW
)1,.,,,,(
),,.,,,,(
21
121
XWxg T?)(
为模式向量。＝
为权向量，
T
n
T
n
xxxX
wwwW
),.,,,,(
),.,,,,(
21
210?
信息工程学院
模式分类：
当 g1(x) =WTX=0 为判别边界 。当 n=2时，二维情况的判别边界为一直线。当 n=3时，判别边界为一平面,n>3时，则判别边界为一超平面。
2
1
,0
,0)(
x
xXWxg T
2,n维情况信息工程学院
(二 ) 多类问题
。其它 Mi
X
XWxg iTii
,.,,,2,1,,0
,0
)(
对于多类问题，模式有 ω1,ω2,…,ωm 个类别。可分三种情况：
1。 第一种情况：每一模式类与其它模式类间可用单个判别平面把一个类分开。 这种情况,M类可有 M个判别函数，且具有以下性质：
权向量。
个判别函数的为第式中 iwwwwW Tininiii ),,,.,,,,( 121
信息工程学院
右图所示，每一类别可用单个判别边界与其它类别相分开 。
如果一模式 X属于 ω1,则由图可清楚看出,这时 g1(x) >0而
g2(x) <0,g3(x) <0 。 ω1 类与其它类之间的边界由
g1(x)=0确定,
2?
1x
0)(2?xg
0)(3?xg
2x 0)(
1?xg
1?
3?
1。 第一种情况信息工程学院
1)(
5)(
)(
23
212
211
xxg
xxxg
xxxg
例：已知三类 ω1,ω2,ω3的判别函数分别为：
因此三个判别边界为：
01)(
05)(
0)(
23
212
211
xxg
xxxg
xxxg
1。 第一种情况（续）
信息工程学院
作图如下：
1。 第一种情况（续）
3?
0)(
0)(
0)(
3
2
1
xg
xg
xg
1?
2?
0)(
0)(
0)(
3
2
1
xg
xg
xg
0)(
0)(
0)(
3
2
1
xg
xg
xg
4IR 3IR
1IR
2IR
1x
2x
0)(1?xg
0)(2?xg
0)(3?xg
5
5
1
信息工程学院
对于任一模式 X如果它的 g1(x) >0,g2(x) <0,g3(x) <0
则该模式属于 ω1类。相应 ω1类的区域由直线 -x2+1=0
的正边、直线 -x1+x2-5=0 和直线 -x1+x2=0的负边来确定。
1。 第一种情况（续）
3?
0)(
0)(
0)(
3
2
1
xg
xg
xg
1?
2
0
0
0
3
2
1
)x(g
)x(g
)x(g
0)(
0)(
0)(
3
2
1
xg
xg
xg
4IR 3IR
1IR
2IR
1x
2x
0)(1?xg
0)(2?xg
0)(3?xg
5
5
1
信息工程学院
必须指出，如果某个 X使二个以上的判别函数 gi(x) >0 。
则此模式 X就无法作出确切的判决。如图中 IR1,IR3，
IR4区域。
另一种情况是 IR2区域，判别函数都为负值。 IR1,IR2，
IR3,IR4。 都为不确 定区域。
1。 第一种情况（续）
3?
0)(
0)(
0)(
3
2
1
xg
xg
xg
1?
2
0
0
0
3
2
1
)x(g
)x(g
)x(g
0)(
0)(
0)(
3
2
1
xg
xg
xg
4IR 3IR
1IR
2IR
1x
2x
0)(1?xg
0)(2?xg
0)(3?xg
5
5
1
信息工程学院
问当 x=(x1,x2)T=(6,5)T时属于那一类
结论,g1(x) <0,g2(x) >0,g3(x) <0所以它属于 ω 2
类
:代入判别函数方程组
1)(
5)(
)(
23
212
211
xxg
xxxg
xxxg
.4)(,6)(,1)( 321 xgxgxg
得：
1。 第一种情况（续）
信息工程学院
这样 有 M(M _ 1)/2个判别平面。
对于两类问题,M=2,则有一个判别平面。
同理，三类问题则有三个判别平面。
判别函数：
判别边界：
判别条件：
jixg ij?
j
i
x0
x0
)( 当当
2。 第二种情况：
XW)x(g Tijij?
o)x(g ij?
每个模式类和其它模式类间可分别用判别平面分开。
2?
0)(12?xg 0)(23?xg
0)(13?xg
3?
1?
信息工程学院
0)(
03)(
05)(
2123
113
2112
xxxg
xxg
xxxg
2123
113
2112
)(
3)(
5)(
xxxg
xxg
xxxg
判别函数性质：
假设判别函数为：
判别边界为：
2。 第二种情况（续）
用方程式作图：
)()( xgxg jiij
0,0 23122 gg 判别区?
012?)x(g
023?)x(g
013?)x(g
5
5
3
1x
0
0
32
31
3
g
g
判别区?
0
0
12
12
1
g
g
判别区?
2x
信息工程学院
问,未知模式 X=(x1,x2)T=(4,3)T属于那一类
代入判别函数可得,
把下标对换可得,
因为
结论：所以 X 属于 ω 3类
结论：判别区间增大，不确定区间减小，比第一种情况小的多,
1)(,1)(,2)( 231312 xgxgxg
1)(,1)(,2)( 323121 xgxgxg
0)(3?xg j
2。 第二种情况（续）
0
0
23
12
2
g
g
判别区?
0
0
12
12
1
g
g
判别区?
0)(12?xg
0)(23?xg
0)(13?xg
5
5
3
0
0
32
31
3
g
g
判别区?
1x
2x
信息工程学院
3。第三种情况
判别函数：
判别规则：
判别边界,gi(x) =gj(x) 或 gi(x) -gj(x) =0
就是说，要判别模式 X属于那一类，先把 X代入 M个判别函数中，判别函数最大的那个类别就是 X所属类别。
类与 类之间的边界可由 gi(x) =gj(x) 或 gi(x) -gj(x) =0来确定。
XWxg Kk?)( MK,.,.,2,1?
小，其它最大，当 iT
ki
xXWxg?)(
每类都有一个判别函数,存在 M个判别函数信息工程学院
右图所示是 M=3 的例子。对于 ω 1类模式，
必然满足 g1(x) >g2(x) 和 g1(x) >g3(x) 。
假设判别函数为：
则判别边界为：
23
212
211
)(
1)(
)(
xxg
xxxg
xxxg
012)()(
02)()(
012)()(
2132
2131
121
xxxgxg
xxxgxg
xxgxg
2?
)()( 21 xgxg?
)()( 32 xgxg?
)()( 31 xgxg?
1?
3?
3。第三种情况（续）
信息工程学院
结论：不确定区间没有了，所以这种是最好情况。
用上列方程组作图如下：
3。第三种情况（续）
1?
)()(
)()(
31
21
xgxg
xgxg
2?
)()(
)()(
32
12
xgxg
xgxg
)()(
)()(
13
23
xgxg
xgxg3
0)()( 32 xgxg
0)()( 21 xgxg
0)()( 31 xgxg
0.1
5.0
5.0
信息工程学院
问假设未知模式 x= (x1,x2)T= (1,1)T,则 x属于那一类。
把它代入判别函数：
得判别函数为：
因为
所以模式 x= (1,1)T属于 类。
3。第三种情况（续）
2?
)()(),()( 1232 xgxgxgxg
1)(,1)(,0)( 321 xgxgxg
).(),(),( 321 xgxgxg
1?
)()(
)()(
31
21 xgxg xgxg
2?
)()(
)()(
32
12 xgxg xgxg
)()( )()(
13
23 xgxg xgxg
3?
0)()( 32 xgxg
0)()( 21 xgxg
0)()( 31 xgxg
0.1
5.0
5.0
信息工程学院
§ 2-3、线性判别函数的性质
1、模式空间与加权空间
模式空间：由 构成的 n
维欧氏空间。
W是此空间的加权向量，它决定模式的分界面 H,W
与 H正交。
加权空间：以 为变量构成的欧氏空间
模式空间与加权空间的几何表示如下图：
XWxg Ti?)(
TnxxxxX ),...,,( 321?
121,.,,,,?nwww
模式空间
2X
1X
1?
2?
1x
3x
4x
0)(?xg边界
2x
HW
信息工程学院
模式空间信息工程学院加权空间判别界面信息工程学院
1、模式空间与加权空间 （续）
信息工程学院
该式表示一个通过加权空间原点的平面，此平面就是加权空间图中的平面①,同样令 g (x2) =g (x3) =g (x4)=0,分别作出通过加权空间原点的平面②③④图中用阴影表示的部分是各平面的正侧。
加权空间的构造：
设 是加权空间分界面上的一点，代入上式得,这是加权空间的边界,0)(
31221111 wxwxwxg
1、模式空间与加权空间
Txxx ),( 12111?
2
3422411
3322311
0
0?
wxwxw
wxwxw
1
3222211
3122111
0
0?
wxwxw
wxwxw
243
121
,
,
xx
xx设：
最终形成图多面锥
2
10)(
x
xxg?
32211)( wxwxwxg
信息工程学院
这是一个不等式方程组，它的解 处于由 ω 1类所有模式决定的平面的正边和由 ω 2类所有模式决定的平面的负边，它的解区即为凸多面锥。
如图所示,(b)为加权空间，（ c） 为正规化后的加权空间。
由上可以得到结论：加权空间的所有分界面都通过坐标原点。这是加权空间的性质。
为了更清楚，下面用二维权空间来表示解向量和解区。
1、模式空间与加权空间 （续）
TwwwW ),,( 321?
信息工程学院
在三维空间里，令 w3 = 0 则为二维权空间。如图：
给定一个模式 X,就决定一条直线：
即分界面 H,W与 H正交,W称为解向量。
解向量的变动范围称为解区。
因 x1,x2∈ ω1,x3,x4∈ ω2由图可见 x1,x3离的最近，所以 分界面 H可以是 x1,x3之间的任一直线，由垂直于这些直线的 W就构成解区，解区为一扇形平面，即阴影区域。
如右图,
2、解向量和解区
0)( XWxg T
1w
2w
1x
4x
3x
2x
解区
W解向量分界面H
解向量与解区信息工程学院
把不等式方程正规化：
正规化：
0
0
0
0
3422411
3322311
3222211
3122111
wxwxw
wxwxw
wxwxw
wxwxw
),,,...,,(
0)(
121
nn
T
i
wwwwW
XWxg
2、解向量的解区（续）
1w
2w
1x
4x
3x
2x
解区解向量分界面H
3x?
4x?
正规化信息工程学院
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的负侧,
上矢量一定在 HxxxxW
wxWwxW
T
n
T
n
T
)(,0)(
0
2121
1211
3、超平面的几何性质信息工程学院
1x
2X
1X
2x
W
H
Ω1
Ω2
g(x)>0
g(x)<0
3、超平面的几何性质信息工程学院
矢量到 H的正交投影 与 值成正比
其中,xp,x在 H 的投影向量,
r是 x 到 H 的垂直距离。
是 W方向的单位向量。
3、超平面的几何性质（续）
W
)x(gr性质 ②：
W
Wrxrxx
pp
)(xgx r
W
W
q
2X
1Xpx
W
x
H
p
r
信息工程学院
另一方面,
11 )()( npTnT wrxWwxWxg
1 nTpT wrWxW
)(,
)(
)()(
0
2
1
WWWr
W
xg
r
Wr
W
WW
r
W
W
rWrWxg
wxWHp
T
T
TT
np
T
是投影的绝对值上。在因为
3、超平面的几何性质（续）
这是超平面的第二个性质，矢量 x到超平面的正交投影正比与 g(x)的函数值。
r
信息工程学院
W
W
q
qrHxx
q
W
W
W
xg
r
xwwxWxg
n
n
nn
T
1
1
11
0
)(
)0()(
的投影为到时因因原点因为成正比的距离与原点到 11 nn WH,WWq
性质③：
3、超平面的几何性质（续）
q
2X
1X0
H
信息工程学院
性质④：
通过原点。，说明超平面则若在原点负侧。则在原点正侧，若则若
HxWxgW
HWHW
T
n
nn
)(,0
,0,0
1
11
否则，反之。的正侧，在代数距离。到正比于来决定。的位置由超平面决定正交，方向由的平面与）超平面（
结论：
,0)(
)()(
)(
1
xgHx
Hxxgc
WHb
WWHa
n
3、超平面的几何性质（续）
信息工程学院
一组模式样本不一定是线性可分的，所以需要研究线性分类能力的方法，对任何容量为 N的样本集，线性可分的概率多大呢？
（如下图（ a）,线性不可分）
例,4个样本有几种分法。
图（ b）① 直线把 x1分开，每条直线可把 4个样本分成
ω 1 ω 2 类,4个样本分成二类的总的可能的分法为
24=16类，其中有二种是不能用线性分类实现的线性可分的是 14。即概率为 14/16。
4。二分法能力
（ a）
x1
x2
x3
x4
①
⑥
③
②
④
⑤
⑦
（ b）
信息工程学院
结论,N个样品线性可分数目 (条件：样本分布良好）：
4。二分法能力（续）
为特征数为样本数其中 nNkNk NC kN,,])!1(![ )!1(1
n
k
k
N
N
nNC
nN
nND
0
1 1,2
1,2
),(
若若
对 N和 n各种组合的 D(N,n)值，表示在下表中，从表中可看出，当 N,n缓慢增加时 D(N,n)却增加很快。
信息工程学院
1 2 3 4 5 6
1 2 2 2 2 2 2
2 4 4 4 4 4 4
3 6 8 8 8 8 8
4 8 14 16 16 16 16
5 10 22 30 32 32 32
4。二分法能力（续）
n
),( nNDN
n
k
k
N
NN nNC
nN
nND
nNP
0
1
1 1,2
1,1
2
),(
),(
若若
线性可分概率：
信息工程学院
),( nNP
0.1
5.0
0
54321
1?n
5?n
15?n
n
1 n
N?
强。说明样本少时二分能力范围，即在
。时，线性可分概率为时，即值，对于任意
。处出现明显的门限效应时，曲线急剧下降，在由当
,1),(),1(22:)(
2
1
),()1(22:)(
21:)(
nNPnNc
nNPnNnb
na
把上式用曲线表示成下图：图中横坐标用 λ=N/n+1表示。
由图讨论：
4。二分法能力（续）
信息工程学院
.2
),1(2:)(
,),1(22:)(
0
是最好情况即二分能力）的估计：个样本的线性可分性（对多线性可分能力越差。
说明样品越线性可分概率急剧下降范围，即在
nNNe
nNd
),( nNP
0.1
5.0
0
54321
1?n
5?n
15?n
n
1 n
N?
结论：在实际工作中，分类的训练非常重要，由已知样本来训练。因为已知样本有限，而未知样本无限。选择已知类别的训练样本数方法如下：
4。二分法能力（续）
信息工程学院
①：如果 训练样本 N < N0，设计分类器的分类能力太差，因为训练样本太少。
②：如果训练样本 N太多时,则样本太多，运算量、
存储量太大。
③：因此实际工作中应该取：
②
)1)(20~10(),20~10( nN训练样品?
4。二分法能力（续）
信息工程学院
§ 2-4、广义线性判别函数
kixfw
wxfwxfwxfwxg
k
i
ii
kkk
,.,,,2,1,)(
)(.,,)()()(
1
1
12211
这样一个非线性判别函数通过映射，变换成线性判别函数。
1)(,)( 1 xfxf ki 是单值函数式中
判别函数的一般形式：
2
1
1
1
,0
,0
)(
)()(
x
x
YgYW
xfwxg
T
yx
k
i
ii
空间变换空间信息工程学院
0?YW T判别平面：
)(,
)(
..,
)(
)(
)(,
..,
,0
,0
)()()(
2
1
2
1
2
1
1
1
增广模式向量。广义权向量其中：
空间变换空间
xf
xf
xf
Y
w
w
w
W
x
x
YgYWxfwxg
kk
Tyx
k
i
ii
§ 2-4、广义线性判别函数（续）
2
1
,
,,,
xaxb
xbxorax
则则
例：如右图。
0 ba
x
二次判别函数
2? 1? 2?
信息工程学院
2
3
2
1
2
1
2
12
321
1
,
,0
,0
)()(
,0
,0
)(
x
xY
a
a
a
W
x
x
YgYWxg
x
x
xaxaaxg
T
映射：
§ 2-4、广义线性判别函数（续）
要用二次判别函数才可把二类分开：
)1,1,1(
)25.0,5.0,1(),0,0,1(
3
21
y
yy
0 5.01?
1y
3y
2y
W
平面oYW T?
ω2ω1ω
2
x
信息工程学院
0
1
5.0
12)(
1
,
2
1
1
2,1,1
2
12
3
2
1
2
3
2
1
321
YWY
x
x
xxxg
y
y
y
x
xY
a
a
a
W
aaax
T
空间判别平面：
即：
空间它的判别边界：设讨论在推出
§ 2-4、广义线性判别函数（续）
从图可以看出：在阴影上面是 ω1类,在阴影下面是 ω2
类，
结论：在 X空间的非线性判别函数通过变换到 Y空间成为线性的，但 X变为高维空间
0 5.01?
1y
3y
2y
W
平面oYW T?
ω2 ω1 ω2 x
信息工程学院
1.分段线性判别函数 （用线性无法分开,可用分段线性判别函数 ）
①,基于距离的分段线性判别函数 。 （用均值代表一类，
通过均值连线中点的垂直线分开）
把 ω i类可以分成 li个子类,
∴ 分成 l个子类。
现在定义子类判别函数：
在同类的子类中找最近的均值。
判别规则：
这是在 M类中找最近均值。则把 x归于 ωj类完成分类。
),...,,( 21 liiii
§ 2-5、非线性判别函数
Ⅱ
2?
Ⅰ
Ⅲ
Ⅰ,线性判别
Ⅱ：分段线性判别
Ⅲ：二次判别
1? 1?
li
lli xxg,.,,,2,1m in)(
Mixgxg ij,...,2,1),(m in)(
信息工程学院
§ 2-5、非线性判别函数（续）
例：未知 x,如图：
先与 ω1类各子类的均值比较，即,找一个最近的 与 ω2各子类均值比较取最近的 因 g2(x)< g1(x),所以
x∈ ω2类 。
211 )( xxg
lx 1
322 )( xxg
22?
12?
32?
21?
11?
11?
12?
32?
22?
21?
x
信息工程学院
设 ω＝ ω1,ω2,…… ωm
而每一类又可以分为 子类。
对每个子类定义一个线性判别函数为：
则定义 ωi类的线性判别函数为：
②,基于函数的分段线性判别函数利用均值代表一类有时有局限性，如图所示。若用线性判别函数代表一类，就会克服上述情况。
1?
2?
1x
2x
x
1、分段线性判别函数
),......,( 21 liiii
子类的权向量。为其中 lililili wxwxg?,)(?
)(m a x)(,.....,2,1 xgxg lilli
信息工程学院
在各子类中找最大的判别函数作为此类的代表，
则对于 M类，可定义 M个判别函数 gi(x),i=1,2,…..M,
因此，决策规则：
对未知模式 x,把 x先代入每类的各子类的判别函数中，找出一个最大的子类判别函数,M类有 M个最大子类判别函数，在 M个子类最大判别函数中，
再找一个最大的，则 x就属于最大的子类判别函数所属的那一类。
jiMij xxgxg 则),(m a x)(,.....,2,1
1、分段线性判别函数（续）
信息工程学院
③,基于凹函数的并分段线性判别函数（针对多峰情况）
设 li子类判别函数,i=1,2,…..r 则分段线性判别函数有如下特性：
1、分段线性判别函数（续）
(a),l1,l2,…… lr都是分段线性判别函数
(b),若 A,B都是分段线性判别函数，则,A∧ B,A∨ B
也是分段线性判别函数。 A∧ B取最小,A∨ B取最大。
(c),对任何分段线性函数都可以表示成如下二种形式：
1)、析取范式 (这是经常采用的形式 )
P=(L11∧ L12∧ … ∧ L1m)∨ … ∨ (Lq1∧ Lq2∧ … ∧ Lqm)
2),合取范式
Q= (L11 ∨ L12 ∨ … ∨ L1m) ∧ … ∧ (Lq1 ∨ Lq2 ∨ … ∨ Lqm)
每个 (L11 ∨ L12 ∨ … ∨ L1m) 都称为凹函数。
信息工程学院
。每个子类的判别函数数子类。
mjx
qixxwL
ijij,.,,,2,1,,0
,.,,,2,1,,0
2
1
1、分段线性判别函数（续）
对于多峰二类问题：设第一类有 q个峰，则有 q个凹函数。
即 P=P1∨ P2∨ …… ∨ Pq
每个凹函数 Pi由 m 个线性判别函数来构成。
∴ Pi=Li1∧ Li2∧ … ∧ Lim
假设对于每个子类线性判别函数 Lij都设计成：
2
1
,0
,0
xP
xP
则则判别规则：
信息工程学院
例、设如图个分段判别函数有判别函数个数：
这样它有三个子类。分三个峰，
13
4
4
5
3
3
2
1
1
m
m
m
q?
。则。若则若 21
34312421151211
,0,0
),.,.,m i n (),,.,.,m i n (),,.,.,,m i n (m a x
xPxP
lllllllP
15l
11l
12l13l
14l
22l
24l
23l
21l
34l
33l
32l
31l
11?
21?31?
2?
1、分段线性判别函数（续）
∴ P=(L11∧ L12∧ L13 ∧ L14 ∧ L15) ∨ (L21∧ L22∧ L23 ∧ L24)
∨ (L31∧ L32∧ L33 ∧ L34)
信息工程学院
2、二次判别函数计算量很大）非常复杂的系数一共有维权向量为维的权向量。是其中：
,(1)3(
2
1
)(
n
2
)(
1
1 1 1
0
1
2
0
nnlxg
W
nnW
Wxwxxwxw
WXWXWXxg
n
j ji
n
j
jjijji
n
i
iii
TT
分布分散。如下图：峰，分布比较集中，形成单若已知样本超球面，超双曲面等）面。二次决策面为超二次曲
21)1(
(
协方差为均值，为其中：
大小。的大小，决定超平面的判别函数定义
1111
1
1
11
2
1
,)()()(
:
kxxkxg T
二次判别函数一般可表示成：
信息工程学院控制大小由是个超球面判别平面：
判别规则：
k
0)(
,0)(
,0)(
1
2
1
xg
xxg
xxg
协方差，为均值，，为其中：
，
两个判别函数：都比较集中，那么定义，）如果（
2121
12
21
2,1)()()(
2
ii
ii
T
iii ixxkxg
1?
2?
类比较集中1?
2、二次判别函数 (续 )
信息工程学院
。可用来调整二类错误率判别规则：
判别平面方程：
21
2
1
2
2
2
12
1
221
1
11
1
22
1
11
1
2
1
1
2
21
,
,0
,0
)(
0)()(
)(2)(
)()()(
kk
x
x
xg
kk
xxx
xgxgxg
TT
TT
1x
2x
1?
2?
二次分界面
2、二次判别函数 (续 )
关于二次判别函数，我们将在贝叶斯分类器中详细论述。
§ 2-1、判别函数
§ 2-2、线性判别函数
§ 2-3、线性判别函数的性质
§ 2-4、广义线性判别函数
§ 2-5、非线性判别函数第二章 判别函数信息工程学院
假设对一模式 X已抽取 n个特征，表示为：
模式识别问题就是根据模式 X的 n个特征来判别模式属于 ω1,ω2,…,ωm 类中的那一类。
§ 2-1 判别函数维空间的一个向量是 n
),..,,,,( 321
X
xxxxX Tn?
信息工程学院
例如下图：三类的分类问题，它们的边界线就是一个判别函数
1?
2?
3?边界
2x
1x
§ 2.1 判别函数（续
）
信息工程学院
判别函数包含两类：
一类 是线性判别函数：
线性判别函数
广义线性判别函数
（所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数）
分段线性判别函数
另一类是非线性判别函数
§ 2.1 判别函数（续
）
信息工程学院
§ 2-2 线性判别函数
我们现在对两类问题和多类问题分别进行讨论。
(一 )两类问题 即,
1,二维情况,取两个特征向量
这种情况下 判别函数,
2,),( 21 MTi
2,)( 2,1 nxxX T
32211 wxwxw)x(g
为坐标向量为参数,21,xxw
信息工程学院
在两类别情况，判别函数 g (x) 具有以下性质,
这是二维情况下判别由判别边界分类,
情况如图：
1,二维情况
2
1
,0
,0)(
X
Xxg
i
不定Xxg,0)(?
32211)( wxwxwxg
2?
1?
1x
2x
信息工程学院
2,n维情况
现抽取 n个特征为：
判别函数：
另外一种表示方法：
TnxxxxX ),...,,( 321?
12211,,,,,,)( nnn wxwxwxwxg
10 nwXW
为增值模式向量。，＝
为增值权向量，
T
nn
T
nn
xxxxX
wwwwW
)1,.,,,,(
),,.,,,,(
21
121
XWxg T?)(
为模式向量。＝
为权向量，
T
n
T
n
xxxX
wwwW
),.,,,,(
),.,,,,(
21
210?
信息工程学院
模式分类：
当 g1(x) =WTX=0 为判别边界 。当 n=2时，二维情况的判别边界为一直线。当 n=3时，判别边界为一平面,n>3时，则判别边界为一超平面。
2
1
,0
,0)(
x
xXWxg T
2,n维情况信息工程学院
(二 ) 多类问题
。其它 Mi
X
XWxg iTii
,.,,,2,1,,0
,0
)(
对于多类问题，模式有 ω1,ω2,…,ωm 个类别。可分三种情况：
1。 第一种情况：每一模式类与其它模式类间可用单个判别平面把一个类分开。 这种情况,M类可有 M个判别函数，且具有以下性质：
权向量。
个判别函数的为第式中 iwwwwW Tininiii ),,,.,,,,( 121
信息工程学院
右图所示，每一类别可用单个判别边界与其它类别相分开 。
如果一模式 X属于 ω1,则由图可清楚看出,这时 g1(x) >0而
g2(x) <0,g3(x) <0 。 ω1 类与其它类之间的边界由
g1(x)=0确定,
2?
1x
0)(2?xg
0)(3?xg
2x 0)(
1?xg
1?
3?
1。 第一种情况信息工程学院
1)(
5)(
)(
23
212
211
xxg
xxxg
xxxg
例：已知三类 ω1,ω2,ω3的判别函数分别为：
因此三个判别边界为：
01)(
05)(
0)(
23
212
211
xxg
xxxg
xxxg
1。 第一种情况（续）
信息工程学院
作图如下：
1。 第一种情况（续）
3?
0)(
0)(
0)(
3
2
1
xg
xg
xg
1?
2?
0)(
0)(
0)(
3
2
1
xg
xg
xg
0)(
0)(
0)(
3
2
1
xg
xg
xg
4IR 3IR
1IR
2IR
1x
2x
0)(1?xg
0)(2?xg
0)(3?xg
5
5
1
信息工程学院
对于任一模式 X如果它的 g1(x) >0,g2(x) <0,g3(x) <0
则该模式属于 ω1类。相应 ω1类的区域由直线 -x2+1=0
的正边、直线 -x1+x2-5=0 和直线 -x1+x2=0的负边来确定。
1。 第一种情况（续）
3?
0)(
0)(
0)(
3
2
1
xg
xg
xg
1?
2
0
0
0
3
2
1
)x(g
)x(g
)x(g
0)(
0)(
0)(
3
2
1
xg
xg
xg
4IR 3IR
1IR
2IR
1x
2x
0)(1?xg
0)(2?xg
0)(3?xg
5
5
1
信息工程学院
必须指出，如果某个 X使二个以上的判别函数 gi(x) >0 。
则此模式 X就无法作出确切的判决。如图中 IR1,IR3，
IR4区域。
另一种情况是 IR2区域，判别函数都为负值。 IR1,IR2，
IR3,IR4。 都为不确 定区域。
1。 第一种情况（续）
3?
0)(
0)(
0)(
3
2
1
xg
xg
xg
1?
2
0
0
0
3
2
1
)x(g
)x(g
)x(g
0)(
0)(
0)(
3
2
1
xg
xg
xg
4IR 3IR
1IR
2IR
1x
2x
0)(1?xg
0)(2?xg
0)(3?xg
5
5
1
信息工程学院
问当 x=(x1,x2)T=(6,5)T时属于那一类
结论,g1(x) <0,g2(x) >0,g3(x) <0所以它属于 ω 2
类
:代入判别函数方程组
1)(
5)(
)(
23
212
211
xxg
xxxg
xxxg
.4)(,6)(,1)( 321 xgxgxg
得：
1。 第一种情况（续）
信息工程学院
这样 有 M(M _ 1)/2个判别平面。
对于两类问题,M=2,则有一个判别平面。
同理，三类问题则有三个判别平面。
判别函数：
判别边界：
判别条件：
jixg ij?
j
i
x0
x0
)( 当当
2。 第二种情况：
XW)x(g Tijij?
o)x(g ij?
每个模式类和其它模式类间可分别用判别平面分开。
2?
0)(12?xg 0)(23?xg
0)(13?xg
3?
1?
信息工程学院
0)(
03)(
05)(
2123
113
2112
xxxg
xxg
xxxg
2123
113
2112
)(
3)(
5)(
xxxg
xxg
xxxg
判别函数性质：
假设判别函数为：
判别边界为：
2。 第二种情况（续）
用方程式作图：
)()( xgxg jiij
0,0 23122 gg 判别区?
012?)x(g
023?)x(g
013?)x(g
5
5
3
1x
0
0
32
31
3
g
g
判别区?
0
0
12
12
1
g
g
判别区?
2x
信息工程学院
问,未知模式 X=(x1,x2)T=(4,3)T属于那一类
代入判别函数可得,
把下标对换可得,
因为
结论：所以 X 属于 ω 3类
结论：判别区间增大，不确定区间减小，比第一种情况小的多,
1)(,1)(,2)( 231312 xgxgxg
1)(,1)(,2)( 323121 xgxgxg
0)(3?xg j
2。 第二种情况（续）
0
0
23
12
2
g
g
判别区?
0
0
12
12
1
g
g
判别区?
0)(12?xg
0)(23?xg
0)(13?xg
5
5
3
0
0
32
31
3
g
g
判别区?
1x
2x
信息工程学院
3。第三种情况
判别函数：
判别规则：
判别边界,gi(x) =gj(x) 或 gi(x) -gj(x) =0
就是说，要判别模式 X属于那一类，先把 X代入 M个判别函数中，判别函数最大的那个类别就是 X所属类别。
类与 类之间的边界可由 gi(x) =gj(x) 或 gi(x) -gj(x) =0来确定。
XWxg Kk?)( MK,.,.,2,1?
小，其它最大，当 iT
ki
xXWxg?)(
每类都有一个判别函数,存在 M个判别函数信息工程学院
右图所示是 M=3 的例子。对于 ω 1类模式，
必然满足 g1(x) >g2(x) 和 g1(x) >g3(x) 。
假设判别函数为：
则判别边界为：
23
212
211
)(
1)(
)(
xxg
xxxg
xxxg
012)()(
02)()(
012)()(
2132
2131
121
xxxgxg
xxxgxg
xxgxg
2?
)()( 21 xgxg?
)()( 32 xgxg?
)()( 31 xgxg?
1?
3?
3。第三种情况（续）
信息工程学院
结论：不确定区间没有了，所以这种是最好情况。
用上列方程组作图如下：
3。第三种情况（续）
1?
)()(
)()(
31
21
xgxg
xgxg
2?
)()(
)()(
32
12
xgxg
xgxg
)()(
)()(
13
23
xgxg
xgxg3
0)()( 32 xgxg
0)()( 21 xgxg
0)()( 31 xgxg
0.1
5.0
5.0
信息工程学院
问假设未知模式 x= (x1,x2)T= (1,1)T,则 x属于那一类。
把它代入判别函数：
得判别函数为：
因为
所以模式 x= (1,1)T属于 类。
3。第三种情况（续）
2?
)()(),()( 1232 xgxgxgxg
1)(,1)(,0)( 321 xgxgxg
).(),(),( 321 xgxgxg
1?
)()(
)()(
31
21 xgxg xgxg
2?
)()(
)()(
32
12 xgxg xgxg
)()( )()(
13
23 xgxg xgxg
3?
0)()( 32 xgxg
0)()( 21 xgxg
0)()( 31 xgxg
0.1
5.0
5.0
信息工程学院
§ 2-3、线性判别函数的性质
1、模式空间与加权空间
模式空间：由 构成的 n
维欧氏空间。
W是此空间的加权向量，它决定模式的分界面 H,W
与 H正交。
加权空间：以 为变量构成的欧氏空间
模式空间与加权空间的几何表示如下图：
XWxg Ti?)(
TnxxxxX ),...,,( 321?
121,.,,,,?nwww
模式空间
2X
1X
1?
2?
1x
3x
4x
0)(?xg边界
2x
HW
信息工程学院
模式空间信息工程学院加权空间判别界面信息工程学院
1、模式空间与加权空间 （续）
信息工程学院
该式表示一个通过加权空间原点的平面，此平面就是加权空间图中的平面①,同样令 g (x2) =g (x3) =g (x4)=0,分别作出通过加权空间原点的平面②③④图中用阴影表示的部分是各平面的正侧。
加权空间的构造：
设 是加权空间分界面上的一点，代入上式得,这是加权空间的边界,0)(
31221111 wxwxwxg
1、模式空间与加权空间
Txxx ),( 12111?
2
3422411
3322311
0
0?
wxwxw
wxwxw
1
3222211
3122111
0
0?
wxwxw
wxwxw
243
121
,
,
xx
xx设：
最终形成图多面锥
2
10)(
x
xxg?
32211)( wxwxwxg
信息工程学院
这是一个不等式方程组，它的解 处于由 ω 1类所有模式决定的平面的正边和由 ω 2类所有模式决定的平面的负边，它的解区即为凸多面锥。
如图所示,(b)为加权空间，（ c） 为正规化后的加权空间。
由上可以得到结论：加权空间的所有分界面都通过坐标原点。这是加权空间的性质。
为了更清楚，下面用二维权空间来表示解向量和解区。
1、模式空间与加权空间 （续）
TwwwW ),,( 321?
信息工程学院
在三维空间里，令 w3 = 0 则为二维权空间。如图：
给定一个模式 X,就决定一条直线：
即分界面 H,W与 H正交,W称为解向量。
解向量的变动范围称为解区。
因 x1,x2∈ ω1,x3,x4∈ ω2由图可见 x1,x3离的最近，所以 分界面 H可以是 x1,x3之间的任一直线，由垂直于这些直线的 W就构成解区，解区为一扇形平面，即阴影区域。
如右图,
2、解向量和解区
0)( XWxg T
1w
2w
1x
4x
3x
2x
解区
W解向量分界面H
解向量与解区信息工程学院
把不等式方程正规化：
正规化：
0
0
0
0
3422411
3322311
3222211
3122111
wxwxw
wxwxw
wxwxw
wxwxw
),,,...,,(
0)(
121
nn
T
i
wwwwW
XWxg
2、解向量的解区（续）
1w
2w
1x
4x
3x
2x
解区解向量分界面H
3x?
4x?
正规化信息工程学院
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的负侧,
上矢量一定在 HxxxxW
wxWwxW
T
n
T
n
T
)(,0)(
0
2121
1211
3、超平面的几何性质信息工程学院
1x
2X
1X
2x
W
H
Ω1
Ω2
g(x)>0
g(x)<0
3、超平面的几何性质信息工程学院
矢量到 H的正交投影 与 值成正比
其中,xp,x在 H 的投影向量,
r是 x 到 H 的垂直距离。
是 W方向的单位向量。
3、超平面的几何性质（续）
W
)x(gr性质 ②：
W
Wrxrxx
pp
)(xgx r
W
W
q
2X
1Xpx
W
x
H
p
r
信息工程学院
另一方面,
11 )()( npTnT wrxWwxWxg
1 nTpT wrWxW
)(,
)(
)()(
0
2
1
WWWr
W
xg
r
Wr
W
WW
r
W
W
rWrWxg
wxWHp
T
T
TT
np
T
是投影的绝对值上。在因为
3、超平面的几何性质（续）
这是超平面的第二个性质，矢量 x到超平面的正交投影正比与 g(x)的函数值。
r
信息工程学院
W
W
q
qrHxx
q
W
W
W
xg
r
xwwxWxg
n
n
nn
T
1
1
11
0
)(
)0()(
的投影为到时因因原点因为成正比的距离与原点到 11 nn WH,WWq
性质③：
3、超平面的几何性质（续）
q
2X
1X0
H
信息工程学院
性质④：
通过原点。，说明超平面则若在原点负侧。则在原点正侧，若则若
HxWxgW
HWHW
T
n
nn
)(,0
,0,0
1
11
否则，反之。的正侧，在代数距离。到正比于来决定。的位置由超平面决定正交，方向由的平面与）超平面（
结论：
,0)(
)()(
)(
1
xgHx
Hxxgc
WHb
WWHa
n
3、超平面的几何性质（续）
信息工程学院
一组模式样本不一定是线性可分的，所以需要研究线性分类能力的方法，对任何容量为 N的样本集，线性可分的概率多大呢？
（如下图（ a）,线性不可分）
例,4个样本有几种分法。
图（ b）① 直线把 x1分开，每条直线可把 4个样本分成
ω 1 ω 2 类,4个样本分成二类的总的可能的分法为
24=16类，其中有二种是不能用线性分类实现的线性可分的是 14。即概率为 14/16。
4。二分法能力
（ a）
x1
x2
x3
x4
①
⑥
③
②
④
⑤
⑦
（ b）
信息工程学院
结论,N个样品线性可分数目 (条件：样本分布良好）：
4。二分法能力（续）
为特征数为样本数其中 nNkNk NC kN,,])!1(
