第三章 判别函数分类器
矢量
矢量 X可以看作是 N维欧氏空间中的一个
点，用一个列矢量表示：
1
2
N
x
x
x
??
??
???
??
??
????
X
M
矩阵
矩阵可以看作是由若干个矢量构成的：
1
2
T
T
T
M
??
??
??
?
??
??
????
X
X
A
X
M
矩阵的秩
? 矩阵所有行向量的最大无关组个数称为
行秩；
? 矩阵所有列向量的最大无关组个数称为
列秩；
? 一个矩阵的行秩等于列秩，称为矩阵的
秩。
转置
? 列矢量 W的转置 WT为一个行矢量；
? N*M的矩阵 A的转置 AT为一个 M*N的矩
阵。
矢量与矢量的乘法 (1)
? 设 W和 X为 N维列矢量
1
N
T
ii
i
wx
?
? ?WX
结果是一个数。
矢量与矢量的乘法 (2)
? 设 W和 X为 N维列矢量
结果是一个 N*N维的矩阵。
1 1 1 2 1
2 1 2 2 2
12
N
NT
N N N N
w x w x w x
w x w x w x
w x w x w x
??
??
?
??
????
WX
L
L
M M O M
L
矢量与矩阵的乘法
? 设 W为 N维列矢量,A为一个 N*M的矩
阵：
1
1
2
1
1
N
ii
i
N
iiT
i
N
i iN
i
wa
wa
wa
?
?
?
??
??
??
??
??
?
??
??
??
??
????
?
?
?
WA
M
结果是一个 N维列矢量。
正交
? 设 W和 X为 N维列矢量，如果 W与 X的内
积等于零：
0T ?WX
则称 W与 X正交，也称 W垂直于 X。
逆矩阵
? A为一个 N*N的方阵,A的逆阵用 A-1表
示，满足：
11????A A A A I
其中 I为单位阵。
一个矩阵的逆阵存在条件,1)是一个方阵，
2)是一个满秩矩阵，矩阵的秩为 N
矩阵的特征值和特征向量
? A为一个 N*N的方阵，如果有：
??A ξξ
数 ?称为 A的特征值，矢量 ξ 称为 A的特
征矢量。
矩阵的迹和行列式值
? A为一个 N*N的方阵,A的迹为主对角线
元素之和：
? ?
1
N
ij
i
tr a
?
? ?A
? A为一个 N*N的方阵,A的迹为主对角线
元素之和：
? ?d et A
矩阵的迹、行列式值与特征值
之间的关系
? 矩阵 A有 N个特征值 ?1,?2,…, ?N，
则有如下关系：
? ?
1
N
i
i
tr ?
?
? ?A
1
d e t( )
N
i
i
?
?
? ?A
矩阵对数值变量微分
? 矩阵 A(t)=[aij(t)]M*N，元素 aij(t)是变量 t
的函数，矩阵 A(t)对 t的微分：
()() ij
MN
d a tdt
d t d t
?
??
? ??
??
A
矩阵函数对矩阵的微分
? 矩阵 X=(xij)M*N,M*N元函数 f(X)，定义
f(X)对矩阵 X的导数：
1 1 1
1
N
ij
MN
M M N
ff
xx
d f f
dx
ff
xx
?
????
??
??
????
?
?? ????
???
????
??
??
????
??
X
L
MM
L
常用矢量微分的性质
? X和 W为 N维矢量,A为 M*N的矩阵：
? ? Tf ?X X W ? ?df d ?X WX
? ? Tf ?X W X ? ?df d ?X WX
? ? Tf ?X X A X ? ? () Tdf d ??X A A XX
3.1 线性判别函数
? 一, 两类问题
? 二, 多类问题
两类问题的线性判别函数
? X0=(x1,x2,…,x N)T为待识模式的特征矢
量；
? W0=(w1,w2,…,w N)T称为权矢量。
? ?0 1 1 2 2 1 0 0 1Tn n n nd w x w x w x w w??? ? ? ? ? ? ?X W XL
线性判别函数的增广形式
? X=(x1,x2,…,x N,1) T称为增广的特征矢
量；
? W=(w1,w2,…,w N,1)T称为增广的权矢
量。
? ? Td ?X W X
两类问题线性判别准则
? ?
1
2
0,
0,
0,
T
d
? ? ??
?
? ? ? ??
? ?
?
X
X W X X
拒识
多类问题（情况一）
? 每一类模式可以用一个超平面与其它类
别分开；
? 这种情况可以把 M个类别的多类问题分
解为 M个两类问题解决；
多类问题（情况一）
? ?1 1 2d x x? ? ?X ? ?2 1 2 5d x x? ? ?X ? ?32 1dx? ? ?X
类别一
类别二
x
1
x
2
类别三
IR
IR
IR
IR
d
3
(X)=0
d
2 (
X
)
=
0
d 1
(
X
)
=
0
多类问题（情况一）判别规则
? 当 d1(X)≥0，而 d2(X)<0且 d3(X)<0时，判
别 X属于 Ω1；
? 当 d2(X)≥0，而 d1(X)<0且 d3(X)<0时，判
别 X属于 Ω2；
? 当 d3(X)≥0，而 d1(X)<0且 d2(X)<0时，判
别 X属于 Ω3；
? 其它情况，拒识。
多类问题（情况二）
? 每两类之间可以用一个超平面分开，但
是不能用来把其余类别分开；
? 需要将 M个类别的多类问题转化为
M(M-1)/2个两类问题。
? 第 i类与第 j类之间的判别函数的为：
? ? Tij ijd ?X W X ij?
多类问题（情况二）判别准则
? 如果对任意 j≠i，有 dij(X) )≥0,则决策 X
属于 ?i。
? 其它情况，则拒识。
多类问题（情况二）
类别二
类别三
类别一
d
12
(X)
=0
d
13
( X
) =
0
d
23 (
X
)
=
0
+ -
+
-
+
-
? ?1 2 1 3 5d x x? ? ? ?X ? ?1 3 1 3dx? ? ?X ? ?2 3 1 2d x x? ? ?X
多类问题（情况三）
? 情况三是情况二的特例，不存在拒识区
域。
类别二
类别三
类别一
d
12
(
X
)
=0
d
13
( X
) =
0
d
23 (
X
)
=
0
多类问题（情况三）判别函数
? M个类别需要 M个线性函数：
? ? 1 1 2 2 ( 1 )Ti i i i i N N i Nd w x w x w x w ?? ? ? ? ? ?X W X L
? 判别准则：
? ? ? ?? ?1m a xijjMdd ???XX i??X
3.2 两类别线性判别函数的学习
? 一, 问题的表达
? 二, 感知器算法
? 三、最小均方误差算法 (LMSE)
问题的表达
? 已知两个类别的训练样本集合：
? ?1 1 2:,,,L? X X XL
? ?2 1 2:,,,L L M??? X X XL
? 求向量 W，使得 d(X)=WTX，能够区分
?1类和 ?2类。
问题的表达
12 0,0,,0
T T T
L? ? ?X W X W X WL
12 0,0,,0
T T T
L L M??? ? ? ? ? ?X W X W X WL
矩阵形式描述 11 12 1 11
12
( 1 ) 1 ( 1 ) 2 ( 1 ) 11
12
1 0
1 0
1 0
1 0
T
N
T
L L LN LL
T
L L L N LL
T
M M M N MM
x x x w
x x x w
x x x w
x x x w
? ? ? ??
?? ?? ?? ??
?? ?? ?? ??
?? ?? ??
?? ?? ?? ??
???? ?? ??
? ? ? ??
?? ?? ?? ??
?? ?? ??
?? ?? ?? ??
? ? ? ?? ?????? ??????
??
X
X
W
X
X
L
M M O M M M MM
L
L
M M O M M M MM
L
?X W 0
X称为增广矩阵。
权矢量的解
? 只有当样本集线性可分的条件下，解才
存在；
? 线性不等式组的解是不唯一；
感知器算法的思想
W(k)
Y
W(k+1)
+
-
+
-
感知器算法
1,初始化，置 W(1)中的元素为一个小的
随机数；
2,在第 k步学习训练样本 Xk，按照如下公
式修正权值 W：
? ? ? ? ? ?? ? ? ?,01,0
T
k
T
kk
kkk
k C k
? ????
? ???
?
W W XW
W X W X
3,重复第 2步，直到所有训练样本被正确
识别。
LMSE算法的思想
此方法也称为 Ho-Kashyap算法 (H-K算法 )
? 将线性不等式组 XW≥0的问题，转化为
解线性方程组 XW=B的问题。
? 其中,B=(b1,b2,…,b N)T,bi≥0
问题求解
? 已知：增广矩阵 X(可由训练样本集得
到 )；
? 求,W和 B。
? X一般不是方阵，所以问题实际上无解，
只能求近似解。
优化的准则函数
? 定义误差矢量 e：
??e X W B
? 定义准则函数 J(W,B)：
? ? ? ? ? ?221 1 1,2 2 2 TJ ? ? ? ? ? ?W B e X W B X W B X W B
梯度法求解
? 上面两个公式成立的 W即为所求。
0J? ??W 0J? ??B
? 定义伪逆矩阵 X*：
? ? 1TT?? ?X X X X
? ? 1* TT ???W X B X X X B
H-K算法
1,由训练样本集计算 X,X*=(XTX)-1XT；
2,初始化 B(0)，每个分量是一个小的正
值，选常数 C，置 k=0；
3,计算 W(k)=X*B(k),e(k)=XW(k)-B(k)；
4,若 e(k)=0，停止迭代，输出 W=W(k)；
若 e(k)≤0，停止迭代，线性不可分；
其它情况，继续第 5步；
H-K算法
5,迭代计算：
? ? ? ? ? ?? ? ? ? ? ?,01,0kkk k C k k ????? ? ??
??
Be
B
B e e
6,k=k+1，返回第 3步，继续。
3.3 多类别线性判别函数的学习
? 情况一, M类问题转化为 M个两类问题：
?i样本作为一类，其它样本作为另一类
进行训练；
? 情况二, M类问题问题转化为 M(M-1)/2
个两类问题,?i样本作为一类,?j样
本作为另一类，训练 Wij；
多类问题情况三
? 采用扩展的感知器算法
1,初始化 L个权向量 Wi(1)，选择常数 C，
置步数 k=1；
2,输入增广特征矢量 Xk，计算 L各判别函
数的输出：
? ? ? ?Ti k i kdk?X W X
扩展的感知器算法
3,修改权矢量，规则为：
若 Xk属于 ?i，并且 di(Xk)>dj(Xk)，对任
意的 j≠i，则：
W i(k+1)=W i(k),i=1,…,L
若 Xk属于 ?i，而 dl(Xk)<dj(Xk)，则：
W i(k+1)=Wi(k)+CXk；
W l(k+1)=Wl(k)+CXk
W j(k+1)=Wj(k),j≠I,l
扩展的感知器算法
4,重复 2,3步，当 k=M时，检测 L个判别
函数是否能够对全部训练样本正确分
类，如正确分类，则结束，否则 k=1，
转 2，继续。
3.4 非线性判别函数的学习
? 一, 二次判别函数
? 二, 分段线性函数
? 三, 其它非线性判别函数方法
XOR问题
二次判别函数
? 增加特征的高次项，降低维特征转化为高维
特征；
? 2维特征的二次判别函数。
? ? 221 1 2 2 3 1 4 2 5 1 2 6d a x a x a x a x a x x a? ? ? ? ? ?X
XOR问题的二次函数解
? ? 221 2 1 2 1 20, 6 6 3 6 1, 0 0 5 6 0, 4 1 8 9 0, 8 5 7 8 3, 3 9 0 8 0, 6 2 0 7d x x x x x x? ? ? ? ? ?X
分段线性函数 — 聚类的方法
类别1
类别1
类别2
子类1
子类2
子类1
子类2
子类3
分段线性函数 — 逐块二分法
类别1
类别1
类别2
类别2
其它的非线性判别函数
? 函数逼近法：多项式函数，指数函数等；
? 多层感知器
矢量
矢量 X可以看作是 N维欧氏空间中的一个
点，用一个列矢量表示：
1
2
N
x
x
x
??
??
???
??
??
????
X
M
矩阵
矩阵可以看作是由若干个矢量构成的：
1
2
T
T
T
M
??
??
??
?
??
??
????
X
X
A
X
M
矩阵的秩
? 矩阵所有行向量的最大无关组个数称为
行秩；
? 矩阵所有列向量的最大无关组个数称为
列秩；
? 一个矩阵的行秩等于列秩，称为矩阵的
秩。
转置
? 列矢量 W的转置 WT为一个行矢量；
? N*M的矩阵 A的转置 AT为一个 M*N的矩
阵。
矢量与矢量的乘法 (1)
? 设 W和 X为 N维列矢量
1
N
T
ii
i
wx
?
? ?WX
结果是一个数。
矢量与矢量的乘法 (2)
? 设 W和 X为 N维列矢量
结果是一个 N*N维的矩阵。
1 1 1 2 1
2 1 2 2 2
12
N
NT
N N N N
w x w x w x
w x w x w x
w x w x w x
??
??
?
??
????
WX
L
L
M M O M
L
矢量与矩阵的乘法
? 设 W为 N维列矢量,A为一个 N*M的矩
阵：
1
1
2
1
1
N
ii
i
N
iiT
i
N
i iN
i
wa
wa
wa
?
?
?
??
??
??
??
??
?
??
??
??
??
????
?
?
?
WA
M
结果是一个 N维列矢量。
正交
? 设 W和 X为 N维列矢量，如果 W与 X的内
积等于零：
0T ?WX
则称 W与 X正交，也称 W垂直于 X。
逆矩阵
? A为一个 N*N的方阵,A的逆阵用 A-1表
示，满足：
11????A A A A I
其中 I为单位阵。
一个矩阵的逆阵存在条件,1)是一个方阵，
2)是一个满秩矩阵，矩阵的秩为 N
矩阵的特征值和特征向量
? A为一个 N*N的方阵，如果有：
??A ξξ
数 ?称为 A的特征值，矢量 ξ 称为 A的特
征矢量。
矩阵的迹和行列式值
? A为一个 N*N的方阵,A的迹为主对角线
元素之和：
? ?
1
N
ij
i
tr a
?
? ?A
? A为一个 N*N的方阵,A的迹为主对角线
元素之和：
? ?d et A
矩阵的迹、行列式值与特征值
之间的关系
? 矩阵 A有 N个特征值 ?1,?2,…, ?N，
则有如下关系：
? ?
1
N
i
i
tr ?
?
? ?A
1
d e t( )
N
i
i
?
?
? ?A
矩阵对数值变量微分
? 矩阵 A(t)=[aij(t)]M*N，元素 aij(t)是变量 t
的函数，矩阵 A(t)对 t的微分：
()() ij
MN
d a tdt
d t d t
?
??
? ??
??
A
矩阵函数对矩阵的微分
? 矩阵 X=(xij)M*N,M*N元函数 f(X)，定义
f(X)对矩阵 X的导数：
1 1 1
1
N
ij
MN
M M N
ff
xx
d f f
dx
ff
xx
?
????
??
??
????
?
?? ????
???
????
??
??
????
??
X
L
MM
L
常用矢量微分的性质
? X和 W为 N维矢量,A为 M*N的矩阵：
? ? Tf ?X X W ? ?df d ?X WX
? ? Tf ?X W X ? ?df d ?X WX
? ? Tf ?X X A X ? ? () Tdf d ??X A A XX
3.1 线性判别函数
? 一, 两类问题
? 二, 多类问题
两类问题的线性判别函数
? X0=(x1,x2,…,x N)T为待识模式的特征矢
量；
? W0=(w1,w2,…,w N)T称为权矢量。
? ?0 1 1 2 2 1 0 0 1Tn n n nd w x w x w x w w??? ? ? ? ? ? ?X W XL
线性判别函数的增广形式
? X=(x1,x2,…,x N,1) T称为增广的特征矢
量；
? W=(w1,w2,…,w N,1)T称为增广的权矢
量。
? ? Td ?X W X
两类问题线性判别准则
? ?
1
2
0,
0,
0,
T
d
? ? ??
?
? ? ? ??
? ?
?
X
X W X X
拒识
多类问题（情况一）
? 每一类模式可以用一个超平面与其它类
别分开；
? 这种情况可以把 M个类别的多类问题分
解为 M个两类问题解决；
多类问题（情况一）
? ?1 1 2d x x? ? ?X ? ?2 1 2 5d x x? ? ?X ? ?32 1dx? ? ?X
类别一
类别二
x
1
x
2
类别三
IR
IR
IR
IR
d
3
(X)=0
d
2 (
X
)
=
0
d 1
(
X
)
=
0
多类问题（情况一）判别规则
? 当 d1(X)≥0，而 d2(X)<0且 d3(X)<0时，判
别 X属于 Ω1；
? 当 d2(X)≥0，而 d1(X)<0且 d3(X)<0时，判
别 X属于 Ω2；
? 当 d3(X)≥0，而 d1(X)<0且 d2(X)<0时，判
别 X属于 Ω3；
? 其它情况，拒识。
多类问题（情况二）
? 每两类之间可以用一个超平面分开，但
是不能用来把其余类别分开；
? 需要将 M个类别的多类问题转化为
M(M-1)/2个两类问题。
? 第 i类与第 j类之间的判别函数的为：
? ? Tij ijd ?X W X ij?
多类问题（情况二）判别准则
? 如果对任意 j≠i，有 dij(X) )≥0,则决策 X
属于 ?i。
? 其它情况，则拒识。
多类问题（情况二）
类别二
类别三
类别一
d
12
(X)
=0
d
13
( X
) =
0
d
23 (
X
)
=
0
+ -
+
-
+
-
? ?1 2 1 3 5d x x? ? ? ?X ? ?1 3 1 3dx? ? ?X ? ?2 3 1 2d x x? ? ?X
多类问题（情况三）
? 情况三是情况二的特例，不存在拒识区
域。
类别二
类别三
类别一
d
12
(
X
)
=0
d
13
( X
) =
0
d
23 (
X
)
=
0
多类问题（情况三）判别函数
? M个类别需要 M个线性函数：
? ? 1 1 2 2 ( 1 )Ti i i i i N N i Nd w x w x w x w ?? ? ? ? ? ?X W X L
? 判别准则：
? ? ? ?? ?1m a xijjMdd ???XX i??X
3.2 两类别线性判别函数的学习
? 一, 问题的表达
? 二, 感知器算法
? 三、最小均方误差算法 (LMSE)
问题的表达
? 已知两个类别的训练样本集合：
? ?1 1 2:,,,L? X X XL
? ?2 1 2:,,,L L M??? X X XL
? 求向量 W，使得 d(X)=WTX，能够区分
?1类和 ?2类。
问题的表达
12 0,0,,0
T T T
L? ? ?X W X W X WL
12 0,0,,0
T T T
L L M??? ? ? ? ? ?X W X W X WL
矩阵形式描述 11 12 1 11
12
( 1 ) 1 ( 1 ) 2 ( 1 ) 11
12
1 0
1 0
1 0
1 0
T
N
T
L L LN LL
T
L L L N LL
T
M M M N MM
x x x w
x x x w
x x x w
x x x w
? ? ? ??
?? ?? ?? ??
?? ?? ?? ??
?? ?? ??
?? ?? ?? ??
???? ?? ??
? ? ? ??
?? ?? ?? ??
?? ?? ??
?? ?? ?? ??
? ? ? ?? ?????? ??????
??
X
X
W
X
X
L
M M O M M M MM
L
L
M M O M M M MM
L
?X W 0
X称为增广矩阵。
权矢量的解
? 只有当样本集线性可分的条件下，解才
存在；
? 线性不等式组的解是不唯一；
感知器算法的思想
W(k)
Y
W(k+1)
+
-
+
-
感知器算法
1,初始化，置 W(1)中的元素为一个小的
随机数；
2,在第 k步学习训练样本 Xk，按照如下公
式修正权值 W：
? ? ? ? ? ?? ? ? ?,01,0
T
k
T
kk
kkk
k C k
? ????
? ???
?
W W XW
W X W X
3,重复第 2步，直到所有训练样本被正确
识别。
LMSE算法的思想
此方法也称为 Ho-Kashyap算法 (H-K算法 )
? 将线性不等式组 XW≥0的问题，转化为
解线性方程组 XW=B的问题。
? 其中,B=(b1,b2,…,b N)T,bi≥0
问题求解
? 已知：增广矩阵 X(可由训练样本集得
到 )；
? 求,W和 B。
? X一般不是方阵，所以问题实际上无解，
只能求近似解。
优化的准则函数
? 定义误差矢量 e：
??e X W B
? 定义准则函数 J(W,B)：
? ? ? ? ? ?221 1 1,2 2 2 TJ ? ? ? ? ? ?W B e X W B X W B X W B
梯度法求解
? 上面两个公式成立的 W即为所求。
0J? ??W 0J? ??B
? 定义伪逆矩阵 X*：
? ? 1TT?? ?X X X X
? ? 1* TT ???W X B X X X B
H-K算法
1,由训练样本集计算 X,X*=(XTX)-1XT；
2,初始化 B(0)，每个分量是一个小的正
值，选常数 C，置 k=0；
3,计算 W(k)=X*B(k),e(k)=XW(k)-B(k)；
4,若 e(k)=0，停止迭代，输出 W=W(k)；
若 e(k)≤0，停止迭代，线性不可分；
其它情况，继续第 5步；
H-K算法
5,迭代计算：
? ? ? ? ? ?? ? ? ? ? ?,01,0kkk k C k k ????? ? ??
??
Be
B
B e e
6,k=k+1，返回第 3步，继续。
3.3 多类别线性判别函数的学习
? 情况一, M类问题转化为 M个两类问题：
?i样本作为一类，其它样本作为另一类
进行训练；
? 情况二, M类问题问题转化为 M(M-1)/2
个两类问题,?i样本作为一类,?j样
本作为另一类，训练 Wij；
多类问题情况三
? 采用扩展的感知器算法
1,初始化 L个权向量 Wi(1)，选择常数 C，
置步数 k=1；
2,输入增广特征矢量 Xk，计算 L各判别函
数的输出：
? ? ? ?Ti k i kdk?X W X
扩展的感知器算法
3,修改权矢量，规则为：
若 Xk属于 ?i，并且 di(Xk)>dj(Xk)，对任
意的 j≠i，则：
W i(k+1)=W i(k),i=1,…,L
若 Xk属于 ?i，而 dl(Xk)<dj(Xk)，则：
W i(k+1)=Wi(k)+CXk；
W l(k+1)=Wl(k)+CXk
W j(k+1)=Wj(k),j≠I,l
扩展的感知器算法
4,重复 2,3步，当 k=M时，检测 L个判别
函数是否能够对全部训练样本正确分
类，如正确分类，则结束，否则 k=1，
转 2，继续。
3.4 非线性判别函数的学习
? 一, 二次判别函数
? 二, 分段线性函数
? 三, 其它非线性判别函数方法
XOR问题
二次判别函数
? 增加特征的高次项，降低维特征转化为高维
特征；
? 2维特征的二次判别函数。
? ? 221 1 2 2 3 1 4 2 5 1 2 6d a x a x a x a x a x x a? ? ? ? ? ?X
XOR问题的二次函数解
? ? 221 2 1 2 1 20, 6 6 3 6 1, 0 0 5 6 0, 4 1 8 9 0, 8 5 7 8 3, 3 9 0 8 0, 6 2 0 7d x x x x x x? ? ? ? ? ?X
分段线性函数 — 聚类的方法
类别1
类别1
类别2
子类1
子类2
子类1
子类2
子类3
分段线性函数 — 逐块二分法
类别1
类别1
类别2
类别2
其它的非线性判别函数
? 函数逼近法：多项式函数，指数函数等；
? 多层感知器
