线性判别函数.ppt

线性判别函数.ppt

《线性判别函数.ppt》由会员分享，可在线阅读，更多相关《线性判别函数.ppt（68页珍藏版）》请在冰点文库上搜索。

第四章线性判别函数,主要内容：

非参数判别分类器的基本原理，与参数判别分类方法的比较线性分类器三种典型的线性分类器:

fisher准则，感知器，SVM两类与多类判别方法非线性判别方法,4.1引言,参数判别方法：

非参数判别方法：

缺陷：

获取统计分布及参数非常困难,4.1引言,4.2线性判别函数和判定面,最简单的判别函数是线性函数，相应的分类面是超平面,线性判别函数：

由x的各个分量的线性组合构成的函数,

（1）,w：

权向量，w0：

阀值权或偏置,4.2线性判别函数和判定面,两类情况：

4.2线性判别函数和判定面,将x表示为：

xp：

是x在H上的投影向量，r是x到H的算术距离,4.2线性判别函数和判定面,结论：

1.g（x）正比于点x到超平面的算术距离（带符号）2.点x属于w1时，r为正3.点x属于w2时，r为负,4.2线性判别函数和判定面,4.2线性判别函数和判定面,多类情况：

对c类问题：

，且c3法一（c个二分法）：

通过唯一一个线性判别函数，将属于i类的模式与其余不属于i类的模式分开。

对于c类问题，需要c个判别函数。

即：

，,，,且,C个判别函数把特征空间分成C个问题。

特点：

有不确定区域及模糊区域，类型越多，不确定区域越多。

不能直接根据判断：

4.2线性判别函数和判定面,4.2线性判别函数和判定面,判决准则：

若：

则：

且,，,，,有一个模式样本，试判断该样本的类别。

解：

把样本X分别代入上面的判别函数得：

，,，,根据判别规则,因此，判决结果为：

例如：

对三类问题，分别建立三个判别函数,4.2线性判别函数和判定面,法二（个二分法）：

对c个类型中的任意两个类型wi和wj建立一个判别函数，决策面方程，能把这两个类型区分开，但对其他类型则不提供任何信息。

判别函数具有性质：

把c类问题转变为两类问题，与第一种情况不同的是，两类问题的数目不是c个，而是个，并且每个两类问题不是而是,4.2线性判别函数和判定面,判决准则：

若：

则,例如：

对一个三类问题c=3，需要建立3个判决函数和和。

为了确定，必须考察和，且要0，0。

同样对于w2，必须满足和，对于w3必须满足：

和,4.2线性判别函数和判定面,例：

设一个三类问题，有如下判决函数，,，,，现有模式样本,试判断该样本类别：

解：

把样本代入判决函数：

，,，,因此,及,所以：

4.2线性判别函数和判定面,法三：

对c种类型中的每一种类型，均建立一个判决函数，即：

，为了区分出其中的某一个类型wi需要k个判决函数，如果满足：

，,，,则：

对不同的wi，k的取值可能不同。

判决规则也可以写成：

若满足,则，即最大值判决规则。

关于k值的选取：

有5个不同类型，决策面是分段线性的区分超平面。

类型w1与其余4个类型均相邻w2与2个类型相邻（w1,w3），w5与3个类型相邻（w1,w3,w4）。

k的选取取决于所考察的类型与几个类型相邻。

如w1,k=4;w2,k=2;w5,k=3。

4.2线性判别函数和判定面,假定c个类型在特征空间里均相邻，即k=c。

由于：

（1）,

（2）,且：

（3）,上两式与第二种情况中的两个表达式完全一致。

但是，这里的

（2）式来源于

（1）式，对于c个类型来说，独立方程式为c-1个，而非c（c-1）/2个。

尽管有此差别，第三种情况的判别式与第二种情况的判别式相同。

因此，第三种情况此时也被转变成二分法问题。

例如，假定c=3，且已有3个判决函数，满足最大值判决规则。

已知：

4.2线性判别函数和判定面,三个类型区域均相邻。

有：

由：

所以是和的线性组合。

即和是独立的，是不独立的，且在二维空间理，三个判决函数必须相交于一点。

由三个类别的分布情况来看，它们满足第二种情况的判决规则，且无不确定区。

4.2线性判别函数和判定面,例：

设一个三类问题，按最大值规则建立了3个判决函数。

今有模式样本x=（0,2）T，试判别该模式属于哪一类?

解：

将x=（0,2）T代入3个判决函数,按最大值规则，。

由于3个类相邻，也可用第三种情况的推导出的方法求。

4.3设计线性分类器的步骤,线性可分对于一个已知容量为N的样本集，如果有一个线性分类器能把每一个样本正确分类，则称这组样本集是线性可分的。

在一个d维的特征空间中,，线性判别函数的一般表示为：

其中：

称为加权量，则：

称为增广模式。

称为增广加权向量。

则有：

对于两类问题：

若,则,两类之间的判定面方程为：

。

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

训练样本集：

x=x1,x2,xn，由训练样本集x所确定的加权向量称为解向量w*。

解向量特性

（1）一般不唯一。

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

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

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

4.3设计线性分类器的步骤,确定线性分类器的步骤第一步：

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

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

第二步：

确定一个准则,满足

（1），

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

第三步：

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

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

4.3设计线性分类器的步骤,4.4感知器,感知器（perceptron）是一个具有单层计算单元的人工神经网络。

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

4.4感知器,输出函数：

也可表示为：

其中：

模型特点：

神经元之间的耦合程度可变，各个权值wi可以通过训练/学习来调整，从而实现线性可分函数。

4.4感知器,感知器训练算法,则：

感知器训练算法实现：

设训练样本集，每个样本，分别属于类型wi或wj，且xk类别属性已知。

为了确定加权向量w*，执行：

给定初始值：

置k=0，分别给每个权向量赋任意值，可选常数。

输入训练样本计算判决函数值：

4.4感知器,修正权向量w（k）,修正规则如下：

若：

若：

如果类型wj的训练样本的各分量均乘以

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

若：

令k=k+1，返回。

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

一般情况，。

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

4.4感知器,例：

一个两类问题，4个训练样本。

W1：

（0,0）T,（0,1）TW2：

（1,0）T,（1,1）T用感知器求权向量。

解：

将训练样本变为增广型的，W2样本乘以（-1），得到4个样本：

增广向量：

令：

4.4感知器,4.4感知器,从k=1316的结果可以看出，使用w（13）已经能对所有训练样本正确分类，也就是算法收敛于w（13）。

w（13）即为解向量。

分界面：

即：

，如上图所示。

W*是不唯一的，W*属于解集空间。

感知器训练算法的收敛性若训练样本是线性可分的，则感知器训练算法在有限次迭代后，可以收敛到正确的解向量。

证明：

假定：

（1）对每个样本进行归一化处理，变为单位向量。

（2）取常数c=0，取初值。

（3）对来自的训练样本的各个分量均乘以（-1）。

对感知器算法修改为：

置k=0，选初值w（0）=0，c=1，给较小正数T。

输入训练样本xk,计算：

判断：

若,返回，否则继续。

令若所有样本均不进入，则算法结束。

从算法中可以看出：

返回,两边乘以解向量w*:

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

归一化：

4.4感知器,4.4感知器,因此：

分别计算出,代入上式得：

令：

c（k）表示两个向量w*与w（k）之间的夹角余弦，则：

又因为：

，令：

则有：

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

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

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

4.4感知器,感知器训练算法在多类问题中的应用（推广）在前面介绍的多类问题中的第三种情况是没有不确定区域的，对于c种类型中的某一种类型wi，存在k个判决函数，如果样本，则，其中k取决于在特征空间中与wi类型相邻的类型数目，。

采用感知器训练算法求解上面这种情况的权向量的解向量w*，实现步骤为：

赋给初始值：

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

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

修正权向量。

修正规则为：

若：

4.4感知器,若：

令k=k+1，返回。

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

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

例：

已知三类训练样本：

w1=（0,0）T，w2=（1,1）T，w3=（-1,1）T试求解，。

解：

训练样本变成增广型模式向量：

x的下标就是它所属类型，且没有一个样本乘以（-1）。

置K=0,c=1。

赋初值：

开始迭代：

4.4感知器,所以：

所以：

4.4感知器,所以：

所以：

4.4感知器,所以：

所以：

因此，可得到3个解向量：

对应的三个判决函数,练习：

根据上面的判决函数结果，求出各个分界面方程，并在坐标图上表示出来。

4.5最小平方误差准则函数与H-K算法,最小平方误差准则任意给定一个小的正数b，则可在线性判别方程的解区里寻找一个解向量w，使之满足：

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

其中：

上式方程组可化简为：

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

n1+n2=n，则x为N（d+1）维矩正，一般n（d+1），b为n维列向量，w为d+1维列向量。

求解w:

（1）如果w是非奇异的，则：

。

（2）寻找w，使xw-b的差值最小。

误差向量定义：

平方误差准则函数：

约束条件：

要使得到的解w就是解向量w*，必须保证,求解误差平方和最小的解：

令：

，得到,用,代入，得到：

为x的“伪逆矩正”，如果x是方正且非奇异的，这个“伪逆矩正”就是x的逆矩正。

W*是伪逆解。

使用梯度下降法建立b的迭代式：

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

由,得：

令：

这就是最小的条件。

求解b:

对b的前后两次迭代来说，b为正值，又，则b的增量应该是：

即：

引入误差向量：

，则有：

将,代入,则有：

这就是LMSE（LeastMeanSquareError）算法，即最小平方误差算法，也被简称为HK（Ho-Kashyap）算法。

其主要内容为：

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

由训练样本集构成增广矩阵X，求伪逆赋初值b

（1），应使其各分量为正值。

选常数c，置k=1。

计算：

判断：

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

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

否则算法继续。

计算：

令k=k+1，返回,注意：

第步中，可以先计算b（k+1），然后再由公式,求,该算法没有给出精确的迭代次数，通常在每次迭代后均对xw（k）和ek进行检查，当xw（k）0或ek=0，则有解。

反之，若ek变为非正，则迭代停止，表明模式样本线性不可分。

H-K算法与感知器算法的比较：

H-K算法能够监视迭代过程，能发现线性不可分的情况，从而可以及早退出迭代，或删除造成线性不可分的样本。

而感知器算法对线性不可分的情况将会来回摆动，只要计算过程不中止，就始终不收敛，从而造成时间上的浪费。

例4-5.1：

已知两类的训练样本：

w1:

（0,0）T（0,1）T,w2:

（1,0）T（1,1）T,试用H-K算法求解权向量w*。

解：

训练样本的增广矩阵：

求x的伪逆矩阵得：

令c=1,则,误差向量：

由于ek的各分量都为0，则w

（1）就是权解向量，所以判定面方程：

例4-5.2已知两类的训练样本w1:

（0,0）T（1,1）T,w2:

（0,1）T（1,0）T试用H-K算法求解向量w*。

解：

训练样本的增广矩阵：

求x的伪逆矩阵得：

令c=1，,则,误差向量：

e1的各分量都为负，则样本线性不可分。

中止迭代。

H-K算法的多类推广由于多类问题可以简化为多个两类问题，在这儿我们可以利用多类问题的第一种情况，将c类问题简化为c个两类问题，分别对c个两类问题进行训练，得到c个权向量解w*，从而得到c个判决函数。

注意在训练过程中样本的选择，在除类wi之外的训练样本中适当抽取足够的样本，与wi类的样本一起共同构成训练样本集Xi。

多类问题的H-K算法：

由训练样本集Xi的样本建立增广矩阵xi,并求伪逆：

赋给初值。

选常数c,置k=1计算：

判断：

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

否则若ek的各分量均接近于0，即则迭代过程结束，得到解向量，否则：

计算：

令k=k+1，返回,说明：

算法中，令分别进行c次训练，得到c个解向量和c个判决函数。

4.6Fisher线性判别函数,Fisher线性判别函数的提出：

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

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

Fisher的方法，就是解决维数压缩问题。

考虑把d维空间中的数据点投影到一条直线上去的问题，需要解决的两个问题：

（1）怎样找到最好的投影直线方向；

（2）怎样向这个方向实现投影，这个投影变换就是要寻求的解向量w*。

这两个问题就是Fisher方法要解决的基本问题。

图（a）所选的投影直线不能区分样本，而（b）可以。

w1,w2,Fisher准则函数,Fisher准则函数的基本思路：

向量W的方向选择应能使两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小。

基本参量定义：

1.样本在d维特征空间的一些描述量

（1）各类样本均值向量mi,

（2）样本类内离散度矩阵Si与总类内离散度矩阵Sw,（4.6-1）,（4.6-2）,（4.6-3）,（3）样本类间离散度矩阵Sb,（4.6-4）,2在一维投影Y空间

（1）各类样本均值,

（2）样本类内离散度和总类内离散度,（4.6-5）,（4.6-6）,（4.6-7）,根据Fisher选择投影方向W的原则，使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内样本投影尽可能密集的要求，用来评价投影方向W的函数为：

（4.6-8）,将上式化为w的显函数形式：

（4.6-9）,所以的分子项为：

（4.2.5-8）,（4.6-10）,同样也可推出与W的关系,所以：

（4.6-11）,所以可以表示为：

（4.6-12）,求解最佳,求最佳就是对（4.6-12）求取其达极大值时的。

可以采用拉格朗日乘子算法解决，保持（4.6-12）式分母为一非零常数c的条件下,求其分子项的极大值。

设计拉格朗日函数为：

（4.2.5-13）,按拉格朗日算法对（4.6-13）式求对W的偏导数，且令其在时为零，得：

则有：

（4.6-14）,由于Sw非奇异，将（4.6-14）两边乘以Sw-1得,（4.6-15）,又因为：

其中是一个数量，可用数值R表示，则（4.6-16）式可写成,（4.6-16）,代入到（4.6-15）得：

（4.6-17）,我们关心的只是向量的方向，其数值大小对分类器没有影响。

因此在忽略了数值因子后，可得,向量就是使Fisher准则函数达极大值的解，也就是按Fisher准则将d维X空间投影到一维Y空间的最佳投影方向，该向量的各分量值是对原d维特征向量求加权和的权值。

（4.6-18）,Fisher算法实现步骤,由Fisher判别式：

求解的步骤：

把来自两类的训练样本集X分成分别属于类w1和w2两个子集X1和X2,由,计算,由,计算各类的类内离散度矩阵,计算类内总离散度矩阵,计算的逆矩阵,由,求解,判别函数的确定,确定,的方法：

（1）：

（2）：

（3）：

当与已知时可用,（4.6-19）,（4.6-20）,（4.6-22）,当W0确定之后，则可按以下规则分类,（4.6-21）,例题：

设两类样本的类内离散矩阵分别为,使用Fisher准则求决策面方程。

解：

4.7广义线性判别函数,将非线性判别函数转化成广义线性判别函数,a、b为两类的分界点。

其中：

判决规则为：

若xb，g（x）0，则若axb，g（x）0，则,将g（x）进行线性化变换：

令,则g（x）可改写为：

其中：

在y的特征空间里，区分直线为：

，如下图：

区分直线把y空间线性地划分为两个类型区域w1和w2，判决规则为：

若：

对样本x的测量值：

先进行非线性变换，计算g（x）之值，判决类别,总结：

通过线性变换，非线性函数g（x）转化成了线性函数g（y），同时，特征空间也由一维的x空间变成二维的y特征空间，线性变换常常会增加特征空间的维数。

当非判决函数为线性判决之后，其中权向量w可以用感知器、HK、Fisher等算法来求解。

4.8非线性判别函数,非线性判别函数与分段线性判别函数,分段线性判别函数设计中首先要解决的问题：

分段线性判别函数的分段段数问题，这是一个与样本集分布有关的问题。

分段段数过少，就如上图中用一个线性判别函数（段数为1）的情况，其分类效果必然要差；但段数又要尽可能少，以免分类判别函数过于复杂，增加分类决策的计算量。

在有些实际的分类问题中，同一类样本可以用若干个子类来描述，这些子类的数目就可作为确定分段段数的依据。

但多数情况下样本分布及合适子类划分并不知道，则往往需要采用一种聚类的方法将样本划分成相对密集的子类，然后用各种方法设计各段线性判别函数。

分段线性判别函数的一般形式可定义为：

（4.8-1）,其中表示第i类第l段线性判别函数，li为i类所具有的判别函数个数，与分别是第l段的权向量与阈值权。

相应的判别规则是：

其中：

（4.8-2）,则决策：

则称为第i类的判别函数。

决策面方程取决于相邻的决策域，如第i类的第n个子类与第j类的第m个子类相邻，则由它们共同决定的决策面方程为:

（4.8-3）,基于距离的分段线性判别函数,前面讨论过正态分布条件下，两类别问题在各特征统计独立、同方差、且先验概率相等情况下，最小错误率决策可按最小距离决策，即,（4.8-4）,其中与为各类的均值。

基于距离的线性判别,（a）,（b）,图（a）用每个类的特征向量的均值作为各类的代表点图（b）先把各类分成分布相对集中的几个子类，每个子类用子类的特征向量的均值作为各类的代表点。

即：

如果对于i有li个子类，则有li个代表点，或者说把属于i的决策域Ri分成li个子域，即,对每个子区域Ril均值用mil表示，并以此作为该子区域的代表点，则判别函数定义为：

判别规则是：

这种分类器就称为分段线性距离分类器。