第三章判别函数分类器 经过特征抽取之后,一个模式可以用n维特征空间中的一个点X来表示,当特征选择 适当时,可以使同一类模式的特征点在特征空间中某个子区域内分布,另一类模式的特征点 在另一子区域分布(例如苹果和橙子的问题)。这样,我们就可以用空间中的一些超曲面将 特征空间划分为一些互不重叠的子区域,使不同模式的类别在不同的子区域中。这些超曲面 称为判别界面,可以用一个方程来表示:d(X)=0,其中的d(X)是一个从n维空间到 维空间的映射,称为是判别函数( Discriminant function) 在所有的函数形式中,线性函数是一种最简单的形式,下面我们就从线性判别函数入手 来研究判别函数分类器 3.0预备知识 在介绍线性判别函数之前,先来帮助大家复习一下有关于矢量和矩阵的知识 1.矢量 这里的矢量X可以看作是N维欧氏空间中的一个点,用一个列矢量表示: 矩阵 有的时候矩阵可以看作是由若干个矢量构成的: X A是一个MxN的矩阵,其中的X称为是矩阵的行矢量 3.矩阵的秩 矩阵所有行向量中的最大无关组个数称为行秩,矩阵所有列向量中的最大无关组个数称 为列秩。一个矩阵的行秩等于列秩,称为矩阵的秩 4.转置 列矢量W的转置W为一个行矢量,N×M的矩阵A的转置A为一个MxN的矩 阵 5.矢量和矩阵的乘法 设W和X为N维列矢量,A为一个N×M的矩阵。则:
17 第三章 判别函数分类器 经过特征抽取之后，一个模式可以用 n 维特征空间中的一个点 X 来表示，当特征选择 适当时，可以使同一类模式的特征点在特征空间中某个子区域内分布，另一类模式的特征点 在另一子区域分布（例如苹果和橙子的问题）。这样，我们就可以用空间中的一些超曲面将 特征空间划分为一些互不重叠的子区域，使不同模式的类别在不同的子区域中。这些超曲面 称为判别界面，可以用一个方程来表示： d (X) = 0 ，其中的 d (X) 是一个从 n 维空间到一 维空间的映射，称为是判别函数(Discriminant Function)。 在所有的函数形式中，线性函数是一种最简单的形式，下面我们就从线性判别函数入手 来研究判别函数分类器。 3.0 预备知识 在介绍线性判别函数之前，先来帮助大家复习一下有关于矢量和矩阵的知识。 1. 矢量 这里的矢量 X 可以看作是 N 维欧氏空间中的一个点，用一个列矢量表示： 1 2 N x x x = X 2. 矩阵 有的时候矩阵可以看作是由若干个矢量构成的： 1 2 T T T M = X X A X A 是一个 M N 的矩阵，其中的 T Xi 称为是矩阵的行矢量。 3. 矩阵的秩 矩阵所有行向量中的最大无关组个数称为行秩，矩阵所有列向量中的最大无关组个数称 为列秩。一个矩阵的行秩等于列秩，称为矩阵的秩。 4. 转置 列矢量 W 的转置 WT 为一个行矢量， N M 的矩阵 A 的转置 T A 为一个 M N 的矩 阵。 5. 矢量和矩阵的乘法 设 W 和 X 为 N 维列矢量， A 为一个 N M 的矩阵。则：
1)Wx=∑wx,是一个数值,称为W与X的内积 V1x1w1x2……w1xN 2)wxrw2x1w2x2…w2x ,是一个N×N的矩阵 WNY WNx2 W,u,2 ) WA= ,是一个N维的列矢量 W aiN 6.正交 设W和X为N维列矢量,如果W和X的内积等于零,WX=0,则称W和X正 交,也称W垂直于X。 7.逆矩阵 设A为一个N×N的方阵,A的逆阵用A表示,满足AA=AA=I,I为单位 阵。一个矩阵的逆阵存在条件是,首先是一个方阵,其次是一个满秩矩阵,即矩阵的秩为N 8.矩阵的特征值和特征向量 设A为一个N×N的方阵,如果存在一个数A和一个N维的非零列矢量ξ,使得 1=成立,则称λ为A的特征值,ξ为A属于A的特征向量 一般来说一个矩阵应该有N个特征值(可能相等),对应有N个特征向量 9.矩阵的迹和行列式值 设A为一个NxN的方阵,A的迹为主对角线元素之和:m(A)=∑q:A的行列 式值表示为det(A)。 如果矩阵A有N个特征值,2,…,A,则有m(A)=∑4,deA)=∏ 10.矩阵微分 1)矩阵对数值变量微分 如果矩阵A()=(()的每一个元素a()是变量t的可微函数,则称A(O 可微:
18 1) 1 N T i i i w x = W X = ，是一个数值，称为 W 与 X 的内积； 2) 1 1 1 2 1 2 1 2 2 2 1 2 N T N N N N N w x w x w x w x w x w x w x w x w x = WX ，是一个 N N 的矩阵； 3) 1 1 2 1 1 N i i i N T i i i N i iN i w a w a w a = = = = W A ，是一个 N 维的列矢量 6. 正交 设 W 和 X 为 N 维列矢量，如果 W 和 X 的内积等于零， 0 T W X = ，则称 W 和 X 正 交，也称 W 垂直于 X 。 7. 逆矩阵 设 A 为一个 N N 的方阵， A 的逆阵用 −1 A 表示，满足 − − 1 1 AA A A I = = ，I 为单位 阵。一个矩阵的逆阵存在条件是，首先是一个方阵，其次是一个满秩矩阵，即矩阵的秩为 N 。 8. 矩阵的特征值和特征向量 设 A 为一个 N N 的方阵，如果存在一个数 和一个 N 维的非零列矢量 ξ ，使得： Aξ ξ = 成立，则称 为 A 的特征值， ξ 为 A 属于 的特征向量。 一般来说一个矩阵应该有 N 个特征值（可能相等），对应有 N 个特征向量。 9. 矩阵的迹和行列式值 设 A 为一个 N N 的方阵， A 的迹为主对角线元素之和： ( ) 1 N ij i tr a = A = ； A 的行列 式值表示为 det(A) 。 如果矩阵 A 有 N 个特征值 1 2 , , , N ，则有 ( ) 1 N i i tr = A = ， 1 det( ) N i i = A = 。 10. 矩阵微分 1) 矩阵对数值变量微分 如果矩阵 ( ) ( ij ( ))M N t a t A = 的每一个元素 a (t) ij 是变量 t 的可微函数，则称 A(t) 可微：
da(o d MxN 其结果还是一个M×N的矩阵 2)矩阵函数对矩阵的微分 设X=(x)”MxN元函数f(X)=/(x1,x2…,x12x1,…,xm),定义 f(X)对矩阵X的导数为 MI 其结果是一个M×N的矩阵。 特殊的,函数对一个矢量的微分是一个矢量。 3)常用微分的性质 设X和W是N维的矢量,A是一个MxN维的矩阵 . f(X)=Xw f(x)=w'x. d(x)-w /(x)=xAX, x=(A+AX 31线性判别函数 、两类问题 n维空间中的线性判别函数可以表示为: d(X)=mx+12x2+…+1x+1m=WX0+n 其中X0=(x,x2…,x)为待识模式的特征矢量,W=(m,mn2…,w)称为权矢量 般为了处理方便,我们可以将特征矢量和权矢量改为另外一种方式表示 ⅹ=(x,x2…xn,1)称为增广的特征矢量,W=(1,m2…,n,wn)称为增广的权矢 量。则线性判别函数可以以一种简单的内积形式表示:d(X)=WX。 在二维空间中,判别界面可以用一个直线方程来表示:d(X)=Wx+2x2+y=0
19 ( ) ( ) ij M N d t d a t dt dt = A 其结果还是一个 M N 的矩阵。 2) 矩阵函数对矩阵的微分 设 ( ij)M N x X = ， M N 元函数 f f x x x x x ( ) , , , , , , X = ( 11 12 12 21 mn ) ，定义 f (X) 对矩阵 X 的导数为： 11 1 1 N ij M N M MN f f x x df f d x f f x x = = X 其结果是一个 M N 的矩阵。 特殊的，函数对一个矢量的微分是一个矢量。 3) 常用微分的性质 设 X 和 W 是 N 维的矢量， A 是一个 M N 维的矩阵， i. ( ) T f X X W = ， df ( ) d = X W X ； ii. ( ) T f X W X = ， df ( ) d = X W X ； iii. ( ) T f X X AX = ， ( ) ( ) T df d = + X A A X X 。 3.1 线性判别函数 一、两类问题 n 维空间中的线性判别函数可以表示为： ( 0 1 1 2 2 1 0 0 1 ) T n n n n d w x w x w x w w X W X = + + + + = + + + 其中 0 1 2 ( , , , ) T n X = x x x 为待识模式的特征矢量， 0 1 2 ( , , , ) T W = w w wn 称为权矢量。 一般为了处理方便，我们可以将特征矢量和权矢量改为另外一种方式表示： ( 1 2 , , , ,1) T n X = x x x 称为增广的特征矢量， ( 1 2 1 , , , , ) T W = w w w wn n+ 称为增广的权矢 量。则线性判别函数可以以一种简单的内积形式表示： ( ) T d X W X = 。 在二维空间中，判别界面可以用一个直线方程来表示： ( ) 1 1 2 2 3 d w x w x w X = + + = 0 ；
在三维空间中,判别界面为一个平面;在高维空间中,判别界面为一个超平面 当我们已知线性判别函数的权矢量W时,可以构造这样一个分类器: >0.X∈ d(x)=wX<0, XeQ =0,拒识 但模式X处在分类界面上时,d(X)=0,这是一种极端情况,可以采用两种办法来处 理,一种是认为它既不属于Ω1类,也不属于92,拒绝识别:另一种办法是认为X∈91。 对于线性判别函数来说,权向量在线性空间中是一个垂直于分类界面的矢量 、多类问题 设有M个类别Ω21,92,…1,模式X为n维空间中的矢量 情况一:每一类模式可以用一个超平面与其它类别分开,即可用线性判别函数将属于Ω,和 不属于Ω类的模式(记为Ω2.)分开。这种情况可以把M个类别的多类问题分解为M个两 类问题解决,需要M个判别函数。此时判别函数为 d, (X)=W'x==o, XEs. <0.Xg 例如在二维空间中的三类问题,判别函数分别为 d1(X)=-x+x2,d2(X)=x+x2-5,d3(X)=-x2+1 分类器可以按照如下规则设计: 当d(X)≥0,而d2(X)<0且d3(X)<0时,判别X∈92 当d2(X)20,而d1(X)<0且d3(X)<0时,判别X∈92;
20 在三维空间中，判别界面为一个平面；在高维空间中，判别界面为一个超平面。 当我们已知线性判别函数的权矢量 W 时，可以构造这样一个分类器： ( ) 1 2 0, 0, 0, T d = = X X W X X 拒识 但模式 X 处在分类界面上时， d (X) = 0 ，这是一种极端情况，可以采用两种办法来处 理，一种是认为它既不属于 1 类，也不属于 2 ，拒绝识别；另一种办法是认为 X1。 对于线性判别函数来说，权向量在线性空间中是一个垂直于分类界面的矢量。 二、多类问题 设有 M 个类别 1 2 , , , M ，模式 X 为 n 维空间中的矢量。 情况一：每一类模式可以用一个超平面与其它类别分开，即可用线性判别函数将属于 i 和 不属于 i 类的模式（记为 i ）分开。这种情况可以把 M 个类别的多类问题分解为 M 个两 类问题解决，需要 M 个判别函数。此时判别函数为： ( ) 0, 0, T i i i i d = = X X W X X 例如在二维空间中的三类问题，判别函数分别为： d x x 1 1 2 (X) = − + ， d x x 2 1 2 (X) = + −5， d x 3 2 (X) = − +1 类别一 类别二 x1 x2 类别三 IR IR IR IR d3 (X)=0 d2 (X)=0 d1 (X)=0 分类器可以按照如下规则设计： 1. 当 d1 (X) 0 ，而 d2 (X) 0 且 d3 (X) 0 时，判别 X1 ； 2. 当 d2 (X) 0 ，而 d1 (X) 0 且 d3 (X) 0 时，判别 X2 ；
3.当d3(X)20,而d1(X)<0且d2(X)<0时,判别X∈g23 4.其它情况,拒识(对应IR区域)。 情况二:每两类之间可以用一个超平面分开,但是不能用来把其余类别分开。这是需要将M 个类别的多类问题转化为CM=M(M-1)2个992两类问题。判别函数为 d4(X)=WX,,j=1,2,…,M,i≠j 其中:d(X)=-d2(X)。分类器可以采用如下规则:如果d4(X)≥0,V≠,则 决策X∈。 在这种情况下,同样存在着拒识区域,例如图中的阴影区域,d12(X)≥0,d1(X)≥0, d2(X)20,所以它不属于任何一个类别。 类别二 d 类别 例3.1:一个三类问题,有三个判别函数: d3(X)=-x1+3,d2(X) 现有模式X=(43),判别它属于哪一类? 带入三个判别函数: d12(X)=-2,得d21(X)=2>0 d13(X)=-1,得d31(X) d2(X)=-1,得d2( 可见d3(X)≥0.,=12,所以可以判别X=(4,3)∈g3。 情况三:在情况一和情况二中都存在着拒识区域。拒识区域的存在,对某些问题来说是必要
21 3. 当 d3 (X) 0 ，而 d1 (X) 0 且 d2 (X) 0 时，判别 X3 ； 4. 其它情况，拒识（对应 IR 区域）。 情况二：每两类之间可以用一个超平面分开，但是不能用来把其余类别分开。这是需要将 M 个类别的多类问题转化为 ( ) 2 1 2 C M M M = − 个 i j 两类问题。判别函数为： ( ) T ij ij d X W X = ，i j M , 1,2, , = ，i j 其中： d d ij ji (X X ) = − ( ) 。分类器可以采用如下规则：如果 ( ) 0 ij d X ， j i ，则 决策 Xi 。 在这种情况下，同样存在着拒识区域，例如图中的阴影区域， d12 (X) 0 ，d31 (X) 0 ， d23 (X) 0 ，所以它不属于任何一个类别。 类别二 类别三 类别一 d12(X)=0 d13(X)=0 d23(X)=0 + - + - + - 例 3.1：一个三类问题，有三个判别函数： d x x 12 1 3 (X) = − − +5 ， d x 13 1 (X) = − +3，d x x 23 1 2 (X) = − + 现有模式 (4,3) T X = ，判别它属于哪一类？ 带入三个判别函数： d12 (X) = −2 ，得 d21 (X) = 2 0 ； d13 (X) = −1 ，得 d31 (X) = 1 0 ； d23 (X) = −1 ，得 d32 (X) = 1 0 。 可见 3 ( ) 0, 1,2 j d j X = ，所以可以判别 ( ) 3 4,3 T X = 。 情况三：在情况一和情况二中都存在着拒识区域。拒识区域的存在，对某些问题来说是必要