模式识别课件(总顺序No6)(第三章NO1)(张凤)(071030)(线性判别函数)

第三章线性判别函数3.1引言(1)问题：第二章所述的分类器设计方法是在已知类条件概率密度p(X|Wi)和先验概率p(Wi)，再利用Bayes公式将其转化成后验概率。然后依据不同规则进行分类－－相对最优。但实际中，p(X|Wi)很难确定，而Parzen窗等估计方法有需大量样本，且随着特征空间Ω维数的增加所需样本数急增，导致计算量增加，存储量增加。(2)应对与局限性：因此，提出了利用样本集直接设计分类器。这种方法是：若能找到一个分离函数，特别若是不依赖于条件分布密度的，且呈线性或非线性的分离函数。它可理解为通过几何的方法，将Ω分解为对应于不同类别的子空间。这种方法所能处理的只是确定可分(线性/非线性可分)的问题，当样本集聚的空间发生重叠现象时，寻找分离函数的迭代过程将加长，甚至振荡。这就是这种方法的局限性。另外，相对Bayes方法该方法得到的是“次优解”。(3)这种方法的基本思想是：

如果根据以往大量的观察：

①知道模式类别的分布；②能找出d维空间(Ω)中模式类之间的分界。

这就能解决模式的分类问题。这实际上是运用已知类别的训练样本进行学习的过程。通过学习产生若干个代数界面g(X)=0，这个表示界面的函数g(X)称为判别函数。(4)这种方法的处理思路是：分类特征空间的分划

寻求子区域的界面判别函数g(X)

判别函数g(X)的结构与参数的确定待识别样本特征向量带入判别函数后取值与归类。

注意：这种方法要求以后的待分类样本/模式基本上不超过学习样本的分布范围，也就是说利用这些已知样本得出的分类边界是无误差的。为了找出这些模式类之间的分界面，可以利用判别函数来进行。(5)处理方法是：先给定(某个)判别函数类g(X)=0，再利用样本集确定出g(X)中的未知参数，然后对于样本根据其特征值带入g(X)后的取值正负而确定样本的类别(即其所属的子区域)。即：g(X)=W1X1+W2X2+W3=0

若g(X)<0,则XW2

若g(X)>0,则XW1 x1一线性判别函数对于d维特征空间中的不同模式类别分别给出一个由d个特征组成的单值函数，这称为判别函数。其一般表达式为：g(X)=WTX+W0其中：X是d维特征向量(亦称样本向量)。

X=[x1,…,xd]TW称权向量。W=[w1,…,wd]TW0是个常数，称为阀值权。说明：⑴使用g(X)来进行模式分类，依赖于两个因素。

①g(X)的形状(即几何性质)。它可是线性的或非线性的函数。在g(X)是线性判别函数下，它是所有模式特性的线性组合。

g(X)=w1x1+…+wdxd

+w0

式中，每个特征对于判别函数g(X)作出不同的贡献，贡献的大小就是它的权wi(i=1,…,d)。

②g(X)的参数：只要被研究的模式是可分的，就可确定g(X)的参数。(2)使用g(X)进行模式分类的方法。首先利用样本去计算各wi和w0(i=1,…,d)，再将未知(待识别)样本X归到具有最大判别函数值的类别中去。(3)对于C类模式问题，(一般)需要定义C个判别函数。

gi(X)(i=1,…,c)

它们分别对应于C个模式类w1,…,wc。(4)g(X)的基本性质：设一个模式X属于第i类，则有：

gi(X)>gj(X)

(i,j=1,…,c,i≠j)

而如果此模式在第i类和第j类的分界面上，则有：

gi(X)=gj(X)

例如：对于两类问题的线性判别函数及其分类问题。

⑴决策规则问题：在只有两类模式的情况下，可得到两个线性判别函数，即

g1(X)=w1Tx+w10 g2(X)=w2Tx+w20

①如果X属于W1类，则根据上述性质，有：

g1(X)>g2(X)或g1(X)-g2(X)>0；

反之，即如果X属于W2类，则上式小于0。

②

如果令g(X)=g1(X)-g2(X)，则得两类模式的线性分类器的决策规则为：如果g(X)>0,则决策X∈W1，即将X归到W1类。

如果g(X)<0,则决策X∈W2，即将X归到W2类。

如果g(X)=0,则决策是任意的，即将X归到W1或W2类。

其中：g(X)=0是决策面方程。

它是两类模式的分界面(即分割W1类和W2类)。对于二维空间，它是一条直线(线性下)；对于三维空间，它是一个平面；而对于高维空间，则是一个超平面。⑵决策域问题设X1和X2都在决策面H上，则有：

WTX1+W0=WTX2+W0

即WT(X1-X2)=0

由于向量X1和X2是决策面（即超平面）H上的任意两点，所以(X1-X2)是H上的任意向量。上式说明，权向量W和H上的任一向量正交。故W的方向就是H的法线方向(即法向量)。在两类下，H把特征空间分成两个半空间，即对W1类的决策域R1和对W2

类的决策域R2。由于当向量（即模式）X在R1中时，g(X)>0,所以H的法向量的方向是指向R1的。常称R1位于决策面H的正侧／面；反之，称R2位于决策面H的负／反侧。(3)几何解释：H是决策面，其方程为g(X)=0。W是权向量，其是H的法线方向。X是待识别的模式的特征向量(图中X落入R1区域中，即被分到W1类中去)。对待识模式X，若将X带入判别函数，则判别函数值g(X)是特征空间中一/某点X到超平面H的距离的度量。图中W0,g(X)

均为代数量，用于求距离,与方向无关。向量X可以表示为：式中：XpX向量是超平面H的法线方向。向量Xp是X在H上的投影向量。由于Xp是H上的一点，所以是W(权向量)方向上的单位向量，而

r是X到H的垂直距离。r是待求的距离，且r是一个代数量，r的正负反应了X位于H的正负侧（即当X在H的正侧时，r为正；反之，r为负）。据上式可得：或写成为如果g(X)>0

，则X在H的正侧；如果g(X)<0

，则X在H的负侧。若X为原点，有：则从原点到超平面H的距离r0为：如果W0>0，则原点在H的正侧；反之，原点在H的负侧；如果W0=0，则g(X)=WTX(齐次形式)说明H过原点。总之，线性判别函数进行(两类)模式分类时：用超平面H将特征空间分割成两个区域；

H的方向由权向量W确定，H的位置由阀值权W0确定。

g(X)值正比于X点到H的(代数)距离（有正负）。当X在H正侧时，g(X)>0；在负侧时,g(X)<0。二广义线性判别函数对图所示的一维特征空间的两类问题。

若希望的划分是：若X<b或X>a，则X∈W1类；若b<X<a，则X∈W2类。则无法用线性判别函数法解决（实际上，对于非凸决策区域和多连通区域的划分问题，线性判别函数法都无能为力）。对上述问题可建立一个二次判别函数

g(X)=(X-a)(X-b)对应的决策规则就是：如果g(X)>0，则决策X∈W1；如果g(X)<0，则决策X∈W2。二次判别函数的一般形式可写为：

如果适当选择X→Y的映射，则可将X的二次判别函数转化为Y的线性函数。式中：

g(X)=称为广义线性判别函数，称为广义权向量。这样变换后，就化为广义线性判别函数来处理，只不过不是X的线性函数，而是Y的线性函数；且g(X)=的超平面(即=0)在Y空间是通过原点的。注意：经此变换后,维数会大大增加,从而陷入“维数灾难”。对前所述的线性判别函数式中：

则称为线性判别函数的齐次简化；并称为增广样本向量；

称为增广权向量(也称广义权向量)。它们均是d+1维向量。Y与X相比，虽然增加了一维，但保持样本间的欧氏距离不变(只是相当于坐标系移动)。三设计线性分类器的主要步骤⑴要有一组具有类别标志的样本集；⑵据实际情况确定一个准则函数J，它需满足： ①J是样本集和W，w0或a的函数。 ②J的值能反映分类器的性能，其极值解对应于“最佳”决策。⑶用最优化技术求出J的极值解W*，w0*和a*。

从而得到线性判别函数：

g(x)=W*TX+w0*或g(X)=a*TY3.2Fisher线性判别一引言

线性判别函数易于分析，但是存在维数问题，即在低维或解析上行的通情况下适用，而对于高维却很难实现。所以降低维数是关键。现考虑将d维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。

关键：寻找满足上述目标的投影轴的方向和在一维空间中确定判别函数规则的问题——这就是Fisher所要解决的问题。

二Fisher法的基本思想和基本方法⒈Fisher方法的基本思想

把d维空间的所有模式投影到一条过原点的直线上，就能把维数压缩到1。这就是说，要求一个投影向量W，使各样本投影后同类模式相距较近，同类模式密集；不同类模式相距较远，即类心相距较远。这就是相当于找到某个方向，使在这个方向的直线上，样本的投影能分开得最好。⒉Fisher的基本方法

指从d维空间到一维空间的一般变换方法。设有一集合æ包含N个d维样本X1,…,XN，其中N1个属于W1类的样本,记为子集æ1，N2(=N-N1)个属于W2类的样本,记为æ2。目的是找到一条直线，使得样本在此直线上的投影最有利于分类。设W为此直线正方向的单位向量。即‖W‖=1。

(实际上W的绝对值大小在此是无关紧要的，而重要的是确定W的方向。W的方向不同，将使样本投影后的可分离程度不同，从而影响识别效果.)若设由X1和X2对直线的投影相应地得到集合Y1和Y2。则每个yj∈Yi就是xj∈Xi(j=1,…,N;i=1,2)在单位向量W上的投影。即yj

=WTxj(j=1,…,N)注意：yj代表一维样本（即yj为标量）。说明：对xj的分量作线性组合后，共得到N个一维样本yj组成的集合Y，它们归属于两个子集Y1和Y2中。这从几何上讲，每个yj就是相对应的Xj到方向为W的直线上的投影。这样上式可写成：Y=WTX

式中：Y=[y1,…,yN]T；

WT

=[w1,…,wd]并且‖w‖=1；

X

=[xj1,…,yjd]T(j=1,…,N)为了找到最有利于分类的方向W，需建立一个准则函数，它能反映不同类别模式在此直线上投影分离程度的好坏。三Fisher准则函数所涉及的基本参量⒈在d维x空间⑴各类样本均值向量mi

：

(i=1,2)

注意：Ni为标量(个数)，x为向量，所以mi为向量。⑵样本类类内离散度矩阵Si和总类类内离散度矩阵Sw

(1=1,2)

Sw

=S1+

S2说明：Si表示类中各点到类的中心点距离之和(的平方)。其中Sw是对称半正定矩阵，且当N>d时，通常是非奇异的。⑶样本类类间离散度矩阵Sb

Sb=(m1-m2)(m1-m2)T

说明：Sb也是对称半正定矩阵，在两类条件下，它的秩最大等于1，且(Sb)d*d

。⒉在一维Y空间 即作变换后，使d维向量x在以向量W为方向的轴上进行投影

Y=WTX

变换后在一维Y空间中。⑴各类样本均值

(i=1,2)说明：①因为y是标量，所以也是标量。mi是第i类d维样本的均值，而这些样本在直线W上的投影的均值就是，再根据Y=WTX

③

为了使类别分离地好，应使各类样本投影均值彼此间相距尽可能大，而投影均值间的距离就是：因为m1和m2对于给定的两类样本集是不变的。所以改变W的方向，就可改变投影均值间的距离。⑵样本类类内离散度和总类类内离散度

说明：①因为y,均为标量，所以和也为标量。②为了使类别分离得好，还应使同类样本的投影比较密集，这由来度量；而表示整个样本集合中各类样本投影的密集程度。③为了得到更好的分类结果，应选择直线W使得尽可能小。⑶样本类类间离散度说明：因为为标量，所以也为标量。四Fisher线性判别

构造Fisher判别函数（y为一维，X为d维）

(注意：“判别函数”指的是任一X的函数)

希望投影后，在一维Y空间里，各类样本尽可能分得开些，即希望类间离散度越大越好；而希望各类样本内部尽量密集，即希望类内离散度越小越好。据此定义Fisher准则函数

式中JF(w)为标量(因为,,均是标量)

现在的问题就是选择合适的W(方向)使尽可能的达到极大。将变成W的显函数，即将，，的式子代入式得:

这是广义Rayleigh商/比，其