第4讲线性分类器资料下载.pdf

第4讲线性分类器资料下载.pdf

《第4讲线性分类器资料下载.pdf》由会员分享，可在线阅读，更多相关《第4讲线性分类器资料下载.pdf（78页珍藏版）》请在冰点文库上搜索。

在线性可分情况下，它是一个区分超平面。

若把来自于类型的样本模式的各个分量均乘以（-1），则两类样本的模式均应满足。

因此，只要加权向量是确定的，对于来自或的任何样本，很容易确定他们的类别。

但怎样确定呢？

这是下面几节要讲到的内容。

xwxgT=）（00TwxxwTwiwjww线性分类器先介绍几个概念先介绍几个概念：

样本集：

特征向量集。

训练样本集：

用于训练分类器的样本集合（或由训练样本构成的集）。

测试样本集：

用于检测分类器性能的样本集合。

一般来说，要确定加权向量w，必须首先采集一些样本，并把它们变换为特征空间里的模式向量。

这样的模式样本就是训练样本。

为此而作的实验就是训练实验。

训练实验一般是在各个类型中独立进行。

如果训练样本的类别属性是预先已知的，这样的训练实验就是预分类的训练实验，又叫监督试验监督试验。

线性分类器训练样本集常用x=x1,x2,xn表示，由训练样本集x所确定的加权向量称为解向量w*。

假定通过独立的试验在类型中采集了三个训练样本,。

在类型中采集了两个训练样本和。

把训练样本变为增广型模式向量，且、,的各分量乘以（-1），则有：

，。

对应的决策面方程。

iw1x2x3xjw4x5x4x5x0kTxw5,4,3,2,1=k0=kTxw线性分类器当样本线性可分时，确定了5个区分超平面，各自以为法线向量。

每个区分超平面都把权空间分为两个半空间，指向的一侧为正的半空间，5个正的半空间共同确定的区域一般是顶点为权空间原点的凸五面锥，锥体内的每一个点都满足，也就是均可作为解向量。

所以，并不唯一。

0=kTxwkxkx0kTxw*w*w线性分类器解向量特性：

（1）一般不唯一。

落入权空间的一个凸多面锥围成的区域内的每一个点都可作为。

该区域称为解区。

（2）每个训练样本都对解区提供一个限制。

样本越多，限制越严，越可靠，越是靠近解区的中心。

越可靠，意味着分类错误越小。

*w*w*w*w线性分类器例：

一个红外图像，目标为亮点，如下图。

50个点（bi,bi），i=1,2,.,5020个点（oj,oj），j=1,2,.,20128128，每个象素8bit线性分类器样本集：

实际要分类的样本数：

12812870。

训练样本Z的分布图如下：

.,.,7052515021xxxxxxX=,.,.,6052513021xxxxxxZ=,.,.,/706261503231xxxxxxZXY=（均值）（标准差）线性分类器假定判别函数为：

分类规则：

若点满足，则对应的象素点为目标。

对上述讨论作一个总结，得出确定线性分类器的主要步骤：

第一步第一步：

采集训练样本，构成训练样本集。

其中每个样本的属性是预知的，而且样本已经经过变换/选择，得到对分类最有效的d个特征。

cbaf+=）,（ff=）,（0）,（f线性分类器第二第二步步：

确定一个准则，满足：

（1）

（2）能反映分类器的性能，且对于的权值，所得分类器最优。

第三第三步步：

求的权值，得到解向量，同时设计求解w的最优算法。

一旦得到，训练实验的任务就完成了。

在下面研究各种训练算法时，假定第一步已经完成。

J）,（xwJJ=）,（xwJJ*w）,（xwJ*w*w梯度法2w0xwT*w0xwT前面已经讨论了在两类情况下，当样本可分时，将属于的样本的各分量乘

（1），则所有满足的样本所求出的解，即可确定判决函数。

这是一线性联立不等式的求解问题，只对线性可分问题，方程才有解。

对这样的问题来说，如果有解，其解也不一定是单值的，因而就有一个按不同条件取得最优解的问题。

这样就出现了多种不同的算法，下面介绍梯度法。

因为求某一函数的数值解，通常只能求出在某种意义下的最优解，即先定义一个准则函数，然后在使此准则函数最大或最小的情况下，求出的解。

梯度法就是先确定一准则函数，然后选一初值，然后通过迭代的方法找到的数值解。

梯度法梯度法在数学分析中，函数在某点的梯度是一个向量，其方向是增长最快的方向。

显然，负梯度方向是减少最快的方向。

）（wf）（wf）（wJ）1（ww）（wJkw）（kwJ）（wJ）（wJ梯度法所以，在求某函数极大值时，沿梯度方向走，则可以最快到达极大点；

反之，沿负梯度方向走，则可以最快到达极小点。

定义一个准则函数，它的最小值对应着最优解。

为此，我们可以得到梯度法的迭代公式：

（清华教材）上式使在函数的负梯度方向上迅速收敛于最优解。

其中，是一个正的比例因子，这就是梯度法。

）,（xwJ*w331Pw（k）wJkwkw=+）（）（）1（wJ*w梯度法感知器感知器感知器（perceptron）是一个具有单层计算单元的人工神经网络。

感知器训练算法就是由这种神经网络演变来的。

感知感知器的概念器的概念美国学者F.Rosenblatt年提出了感知器的模型，如下图。

感知器感知感知器器实质上是一种神经元模型，是一个多输入/单输出的非线性器件。

用一个数学表达式表示，就是：

这种神经元没有内部状态的转变，而且函数为一个阶跃函数，即为阈值型。

因此，它实质上是一种线性阈值计算单元，如下图：

1（）diiiyfwx=f感知器输出表达式：

也可以写成：

其中：

如果令：

则：

=11Y=diiidiiixwxw1100）sgn（0=xwYT）,.,（210dTwwww=Tdxxxx）,.,（21=）,.,（21=dTwwwwTdxxxx）1,.,（21=sgn（）Tywx=10sgn（）10xxx=感知器与其他神经元模型相比，感知器模型的一个重要特点是神经元之间的耦合程度可变，各个权值可以通过训练/学习来调整，从而实现线性可分函数。

当感知器用于两类模式的分类时，相当于在高维样本的特征空间中，用一个超平面把两类区分开。

Rosenblatt已证明，如果两类模式是线性可分的，算法一定收敛。

这就确定了一种自组织、自学习的思想。

由此引导出的感知器算法至今仍是最有效的算法之一。

iw感知器感知感知器训练算法器训练算法已知感知器输出函数：

令：

，又令：

，分别表示两种类型，则感知器输出函数变为：

若：

，则：

111,01,0diiidiiiwxywx=+1dw）,.,（210dTwwww=10）（+=dTwxwxg1=y1=y0（）0gxijwxw感知器通过上面的定义，感知器问题变成两类问题。

因此，感知器的自组织、自学习思想可以用于确定性分类器的训练。

这就是感知器训练方法。

针对两类问题，利用增广型模式向量和增广型加权向量及判决规则：

，则。

说明感知器算法。

jiww/jiww/00Twxckx,.,21nkxxxx（）（）Tkkgxwkx=）（kwkixw0）（kxgkcxkwkw+=+）（）1（kjxw0）（kxgkcxkwkw=+）（）1（如果类型的训练样本的各分量均乘以

（1），则修正规则统一为：

，则令，返回。

直到对所有训练样本均稳定不变，则结束。

一般情况，。

值太小会影响收敛速度和稳定性，太小收敛速度慢，太大，会使的值不稳定。

jw0）（kxgkcxkwkw+=+）（）1（1+=kkw10）（kxkwkw+=+）（）1（nxk,.,2,1=1+=kk感知器从算法中不难看出：

两边乘以解向量：

，（由算法的知道）由于：

归一化，为非解向量时，因此：

1100（）（0）kkiiiiwkwxx=+=*w1*00（）（）kiiwwkwxkT=2222111|（）|

（1）|

（1）|2

（1）|Tkkkwkwkxwkwkxx=+=+1|21=kx）（kw11（）

（1）TkkgxwkxT=222|（）|

（1）|21|

（1）|1wkwkTwk+感知器分别计算出，代入上式得：

表示两个向量与之间的夹角余弦，则又，令，则有：

也就是，是一个有限的值，步骤仅需有限次数就可以得到。

换句话说，在线性可分的情况下，感知器训练算法一定收敛。

正数越小，则收敛越慢（值越大）。

2|

（1）|wk2|

（1）|w2|（）|wkk=wkkTkwwkwwkc1）（kcT|*|Tw=21,0kTTk*wTk感知器感知器训练算法在多类问题中的应用感知器训练算法在多类问题中的应用（推广推广）在上一节，介绍了多类问题的三种情况。

其中，第三种情况是没有不确定区的，对于种类型中的某一种类型，存在个判别函数，如果样本，则：

其中取决于在特征空间里与类型相邻的类型数目，。

这样就把多类问题转变成多个没有不确定区的两类问题，可使用最大值判决规则。

ciwkiwx（）（）1,2,.ijgxgxjkij=kiwckjiww/感知器假定，首先建立c个判决数：

，判决规则为：

若，则。

将本节2中介绍的感知器训练算法用到这种情况，可以建立如下的算法步骤：

赋给初始值：

分别赋给个权向量（）任意的初值，选择正常数c，把训练样本变为增广型模式向量，置。

输入训练样本，假定计算c个判决函数值：

修正权向量。

修正规则为：

ck=xwxgTii=）（ci,.,2,1=）（）（xgxgjicj,.,2,1=ijiwxciwci,.,2,1=0=kkx,.,21nkxxxxikwx（）（）1,2,.Tikikgxwkxic=感知器若，则，否则，若，则：

令，返回。

直到所有的权向量对所有训练样本都稳定不变时结束。

只要模式样本线性可分，则算法迭代有限次后收敛。

）（）（xgxgjicj,.,2,1=ij）（）1（kwkwii=+ci,.,2,1=）（）（kiklxgxg

（1）（）

（1）（）

（1）（）,iikllkjjwkwkcxwkwkcxwkwkjijl+=+=+=1+=kk感知器Fisher线性判别式前面讲过的感知器准则、最小平方和准则属于用神经网络的方法解决分类问题。

下面介绍一种新的判决函数分类方法。

由于线性判别函数易于分析，关于这方面的研究工作特别多。

历史上，这一工作是从R.A.Fisher的经典论文（1936年）开始的。

我们知道，在用统计方法进行模式识别时，许多问题涉及到维数，在低维空间行得通的方法，在高维空间往往行不通。

因此，降低维数就成为解决实际问题的关键。

Fisher的方法，实际上涉及维数压缩。

如果要把模式样本在高（）维的特征向量空间里投影到一条直线上，实际上就是把特征空间压缩到一维，这在数学上容易办到。

另外，即使样本在高维空间里聚集成容易分开的群类，把它们投影到一条任意的直线上，也可能把不同的样本混杂在一起而变得无法区分。

也就是说，直线的方向选择很重要。

在一般情况下，总可以找到某个最好的方向，使样本投影到这个方向的直线上是最容易分得开的。

如何找到最好的直线方向，如何实现向最好方向投影的变换，是Fisher法要解决的基本问题。

这个投影变换就是我们寻求的解向量。

*wdFisher线性判别式线性线性投影与投影与FisherFisher准则函数准则函数在两类问题中，假定有个训练样本其中个样本来自类型，个样本来自类型，。

两个类型的训练样本分别构成训练样本的子集和。

，（4.5-1）是向量通过变换得到的标量，它是一维的。

实际上，对于给定的，就是判决函数的值。

21/wwn）,.,2,1（nkxk=1niw2njw21nnn+=1X2XkTkxwy=nk,.,2,1=kykxwwkyFisher线性判别式由子集和的样本映射后的两个子集为和。

因为我们关心的是的方向，可以令，那么就是在方向上的投影。

使和最容易区分开的方向正是区分超平面的法线方向。

如下图：

1X2X1Y2Yw1|=wkykxw1Y2YwFisher线性判别式图中画出了直线的两种选择，图（a）中，和还无法分开，而图（b）的选择可以使和区分开来。

所以图（b）的方向是一个好的选择。

1Y2Y1Y2YFisher线性判别式下面讨论怎样得到最佳方向的解析式。

各类在维特征空间里的样本均值向量：

，（4.5-2）通过变换映射到一维特征空间后，各类的平均值为：

，（4.5-3）映射后，各类样本“类内离散度”定义为：

，（4.5-4）wd=ikXxkiixnM12,1=iw=ikYykiiynm12,1=i22（）kiikiyYSym=2,1=iFisher线性判别式显然，我们希望在映射之后，两类的平均值之间的距离越大越好，而各类的样本类内离散度越小越好。

因此，定义Fisher准则函数：

（4.5-5）使最大的解就是最佳解向量，也就是Fisher的线性判别式。

2122212|（）FmmJwss=+FJ*wFisher线性判别式求解求解从的表达式可知，它并非的显函数，必须进一步变换。

已知：

，,依次代入（4.5-1）和（4.5-2），有：

，（4.5-6）所以：

（4.5-7）其中：

（4.5-8）*w）（wJFw=ikYykiiynm12,1=iiTXxkiTkXxTiiMwxnwxwnmikik=）1（12,1=i221221221|）（|MMwMwMwmmTTT=wSwwMMMMwbTTT=）（2121TbMMMMS）（2121=Fisher线性判别式是原维特征空间里的样本类间离散度矩阵，表示两类均值向量之间的离散度大小，因此，越大越容易区分。

将（4.5-6）和（4.5-2）代入（4.5-4）式中：

（4.5-9）bSdbSiTiMwm=ikXxkiixnM12iS=ikXxiTkTiMwxwS22）（=ikXxTikikTwMxMxw）（wSwiT=Fisher线性判别式其中：

，（4.5-10）因此：

（4.5-11）显然：

（4.5-12）称为原维特征空间里，样本“类内离散度”矩阵。

是样本“类内总离散度”矩阵。

为了便于分类，显然越小越好，也就是越小越好。

TiXxkikiMxMxSik）（=2,1=iwSwwSSwSSwTT=+=+）（21222121SSSw+=iSdwSiSwSFisher线性判别式将上述的所有推导结果代入表达式：

广义Rayleigh商（4.5-13）式中和皆可由样本集计算出。

用lagrange乘子法求解的极大值点。

令分母等于非零常数，也就是：

定义lagrange函数：

（4.5-14）（wJFwSwwSwwJwTbTF=）（bSwSX）（wJF0=cwSwcwT）（）,（cwSwwSwwLwTbT=Fisher线性判别式对求偏导数：

令得到：

（4.5-15）从上述推导（4.5-10）（4.5-12）可知，是维特征的样本协方差矩阵，它是对称的和半正定的。

当样本数目时，是非奇异的，也就是可求逆。

Lw）

（2）,（wSwSwwLwb=0）,（=wwL*wSwSwb=wSddnwS*1*wSSwbw=Fisher线性判别式（4.5-16）问题转化为求一般矩阵的特征值和特征向量。

令，则是的特征根，是的特征向量。

（4.5-17）式中：

是一个标量。

所以总是在方向上。

将（4.5-17）代入到（4.5-15），可以得到：

bwSS1ASSbw=1A*wA*2121*）（wMMMMwSTb=）（*2121wMMMMT=）（21MM*21）（wMMT=*wSb）（21MM）（211*MMSww=Fisher线性判别式其中，是一个比例因子，不影响的方向，可以删除，从而得到最后解：

（4.5-18）就使取得最大值，可使样本由维空间向一维空间映射，其投影方向最好。

是一个Fisher线性判断式。

讨论：

如果，则样本线性不可分。

，未必线性可分。

不可逆，未必不可分。

*w）（211*MMSww=*w）（wJF*wd）（211*MMSww=21MM=0*=w21MMwSFisher线性判别式FisherFisher算法步骤算法步骤由Fisher线性判别式求解向量的步骤：

把来自两类的训练样本集分成和两个子集和。

由，计算。

由计算各类的类内离散度矩阵，。

计算类内总离散度矩阵。

）（211*MMSww=*w21/wwX1w2w1X2X=ikXxkiixnM12,1=iiMTiXxkikiMxMxSik）（=iS2,1=i21SSSw+=Fisher线性判别式计算的逆矩阵。

由求解。

这一节所研究的问题针对确定性模式分类器的训练，实际上，Fisher的线性判别式对于随机模式也是适用的。

Fisher算法注释:

（1）Fisher方法可直接求解权向量；

（2）对线性不可分的情况，Fisher方法无法确定分类，Fisher可以进一步推广到多类问题中去。

wS1wS）（211*MMSww=*w*wFisher线性判别式最小平方和准则函数与H-K算法最小平方和准则最小平方和准则针对二类问题，利用增广型加权向量和增广型模式向量，并把所有来自的训练样本的各分量均乘以

（1），则所有模式都应该满足：

现在任意给定一个小的正数，则可在解区里寻找一个解向量，使之满足：

假定有n个训练样本，则上式可以写成n个联立方程组：

jiww/jw0xwTbwbxwT=式中上述方程组可简写为：

（是一个超定方程组）。

其中，为训练样本的增广矩阵：

1122TTTnnwxbwxbwxb=nibi,.,2,1,0=bwx=x最小平方和准则函数与H-K算法1111112221112111122

（1）1

（1）2

（1）2121111dTiTnnndnnndTjnnnndxxxxnwxxxxxxxxnwxxxx+=最小平方和准则函数与H-K算法注意：

假定来自和的样本数目分别为和，且，为维矩阵，一般。

为维列向量。

如果样本是线性可分的，则的任意子阵的秩均等于。

这时可以通过最小二乘法求解。

12Tnbbbb=，.，iwjw1n2n21nnn+=x）1（+dn1+dnbnw1+dx）1（）1（+dd1+d最小平方和准则函数与H-K算法定义：

误差向量又定义平方误差准则函数：

约束条件：

要使得到的解就是解向量，必须保证。

下面求的极小值：

bxwe=2221（,）|（）nTsiiiJwxbexwbwxb=sJw*w0iiTbxwsJ*2（）TsJxxwbw=最小平方和准则函数与H-K算法令，得到所以有：

上式中：

用代入，得到其中，称为的伪逆，是伪逆解。

注意：

此时还不是最小平方误差准则函数下的伪逆解。

因为还依赖于b，还要进一步确定b。

0sJw=*2（）0Txxwb=*0TTxxwxb=bxxxwTT1*）（=TTxxxx1#）（=bxw#*=#xx*w*w*w最小平方和准则函数与H-K算法根据平方误差准则函数的定义：

要使最小，使用梯度下降法建立的迭代式：

这里使用固定增量法，为大于0的常数。

对定义求导，令，这就是最小的条件。

）,（bxwJssJb（）

（1）（）（）sbbkJbkbkcb=+=csJ2（）sJxwbb=0sJb=0=bxwsJ最小平方和准则函数与H-K算法对的前后两次迭代来说，又为正值，又考虑到，则的增量应该是：

上式也可以改写为：

）（）（）1（kbkbkb+=+b0=bxwbb）（kb0,（）0（）2（）（）,（）0xwkbbkcxwkbkxwkb=（）（）（）|（）（）|bkcxwkbkxwkbk=+最小平方和准则函数与H-K算法引入误差向量：

，则有：

将代入，则有：

至此，我们就建立了一种算法，通常称为LMSE算法，即最小均方误差算法。

LMSE：

LeastMeanSquareError。

也简称H-K算法。

其主要内容为：

）（）（kbkxwek=|）|（）（kkeeckb+=）（）（）1（kbkbkb+=+bxw#*=*#*#

（1）（）（）（）（）wkxbkxbkwkxbk+=+=+最小平方和准则函数与H-K算法下面看一下H-K算法的迭代式。

H-KH-K算法算法该算法的步骤如下：

*#*#

（1）（）（|）

（1）

（1）

（1）0kkwkwkcxeewxbb+=+=最小平方和准则函数与H-K算法由训练样本集构成增广矩阵，求伪逆。

赋初值，应使其各分量为正值。

选常数，置。

计算：

xTTxxxx1#）（=）1（bc1=k）（）（#kbxkw=）（）（kbkxwek=最小平方和准则函数与H-K算法判断：

若的各分量停止变为正值或者不是全部0，则线性不可分，中止迭代。

否则，若的各分量均接近于0，即，则迭代过程完成，结束。

否则算法继续。

keke0ke#

（1）（）|（）|kkkwkwkcxeewkcxe+=+=+

（1）（）|kkbkbkcee+=+最小平方和准则函数与H-K算法注意推导：

，）（）（）（1#kbkxwxxxexTTk=）

（1）（#1kbxxxxxTT=0）（）（）（1=kbxxxxTTT）（）（#kbxkw=TTTTTxxxxxxxxx=1#）（最小平方和准则函数与H-K算法令，返回注意：

第步中，可以先计算，然后再由公式求。

可以证明：

当模式类型可分，且时，H-K算法收敛。

证明收敛