第3章判别函数分类器设计
3.1判别函数简介
判别函数是统计模式识别中用以对模式进行分类的一种较简单的函数。在特征空间中,通过学习,不同的类别可以得到不同的判别函数,比较不同类别的判别函数值的大小,就可以进行分类。统计模式识别方法把特征空间划分为决策区对模式进行分类,一个模式类同一个或几个决策区相对应。
设有c个类别,对于每一个类别ωi(i=1,2,…,c)定义一个关于特征向量X的单值函数gi(X): ①如果X属于第i类,那么gi(X)>gj(X)(i,j=1,2,…,c,j≠i); ②如果X在第i类和第j类的分界面上,那么gi(X)=gj(X)(i,j=1,2,…,c,j≠i)。
人们已研究出多种求取决策边界的算法,线性判别函数的决策边界是一个超平面方程式,其中的系数可以从已知类别的学习样本集求得。F.罗森布拉特的错误修正训练程序是求取两类线性可分分类器决策边界的早期方法之一。在用线性判别函数不可能对所有学习样本正确分类的情况下,可以规定一个准则函数(例如对学习样本的错分数最少)并用使准则函数达到最优的算法求取决策边界。用线性判别函数的模式分类器也称为线性分类器或线性机,这种分类器计算简单,不要求估计特征向量的类条件概率密度,是一种非参数分类方法。
当用贝叶斯决策理论进行分类器设计时,在一定的假设下也可以得到线性判别函数,这无论对于线性可分或线性不可分的情况都是适用的。在问题比较复杂的情况下可以用多段线性判别函数(见近邻法分类、最小距离分类)或多项式判别函数对模式进行分类。一个二阶的多项式判别函数可以表示为与它相应的决策边界是一个超二次曲面。
本章介绍线性判别函数和非线性判别函数,用以对酒瓶的颜色进行分类,其中实现线性判别函数分类的方法有LMSE分类算法和Fisher分类,实现非线性判别函数分类的方法有基于核的Fisher分类和支持向量机。
3.2线性判别函数
判别函数分为线性判别函数和非线性判别函数。最简单的判别函数是线性判别函数,它是由所有特征量的线性组合构成的。我们现在对两类问题和多类问题分别进行讨论。
1. 两类问题
对于两类问题,也就是Wi=(ω1,ω2)T。
1) 二维情况
取二维特征向量X=(x1,x2)T,这种情况下的判别函数g(x)=ω1x1+ω2x2+ω3,其中,ωi(i=1,2,3)为参数; x1和x2为坐标值,判别函数g(x)具有以下性质: 当x∈ω1时,gi(x)>0; 当x∈ω2时,gi(x)<0; 当x不定时,gi(x)=0。这是二维情况下由判别边界分类。
2) n维情况
对于n维情况,现抽取n维特征向量: X=(x1,x2,…,xn)T,判别函数为g(x)=W0X+ωn+1。其中,W0=(ω1,ω2,…,ωn)T为权向量; X=(x1,x2,…,xn)T为模式向量。另外一种表示方法是g(x)=WTX。其中,W=(ω1,ω2,…,ωn,ωn+1)T为增值权向量; X=(x1,x2,…,xn,1)T为增值模式向量。
在这种情况下,当x∈ω1时,g(x)>0; 当x∈ω2时,g(x)<0 g1="" x="" 0="" n="2时,边界为一条直线,当n=3时,边界为一个平面,当n">3时,边界为超平面。
2. 多类问题
对于多类问题,模式有ω1,ω2,…,ωM个类别,可以分为下面三种情况。
1) 第一种情况
每个模式类与其他模式可用单个判别平面分开,这时M个类有M个判别函数,且具有性质
gi(x)=WTiX(31)
式中,Wi=(ωi1,ωi2,…,ωin+1)T为第i个判别函数的权向量。当x∈ωi时,gi(x)>0,其他情况下gi(x)<0,也就是每一个类别可以用单个判别边界与其他类别相分开。
2) 第二种情况
每个模式类和其他模式类之间可以用判别平面分开,这样就有M(M-1)2个平面,对于两类问题,M=2,则有1个判别平面,同理对于三类问题,就有3个判别平面。判别函数为
gij(x)=WTijX(32)
式中,i≠j,判别边界为gij(x)=0,条件为: 当x∈ωi时,gij(x)>0; 当x∈ωj时,gij(x)<0。
3) 第三种情况
每类都有一个判别函数,存在M个判别函数: gk(x)=WkX(k=1,2,…,M),边界为gi(x)=gj(x),条件为: 当x∈ωi时,gi(x)最大; 其他情况下gi(x)小。也就是说,要判别X属于哪一个类,先把X代入M个判别函数,判别函数最大的那个类就是X所属类别。
3.3线性判别函数的实现
对于给定的样本集X,要确定线性判别函数g(x)=WTx+ω0的各项系数W和ω0,可以通过以下步骤来实现:
① 收集一组具有类别标志的样本X={x1,x2,…,xN};
② 按照需要确定准则函数J;
③ 用最优化技术求准则函数J的极值解ω*和ω*0,从而确定判别函数,完成分类器的设计。
对于未知样本x,计算g(x),判断其类别。即对于一个线性判别函数,主要任务是确定线性方程的两个参数,一个是权向量W,另一个是阈值ω0。
在计算机中想要实现线性判别函数,可以通过“训练”和“学习”的方式,将已知样本放入到计算机的“训练”程序,经过多次迭代,从而得到准确函数。
下面具体介绍各种分类器的设计。
3.4基于LMSE的分类器设计
3.4.1LMSE分类法简介
LMSE是Least Mean Square Error的英文缩写,中文的意思是最小均方误差,常称作LMSE算法。
提到LMSE分类算法就不能不提感知器算法和自适应算法,因为LMSE算法本身就是自适应算法中最常用的方法,而感知器和自适应线性元件在历史上几乎是同时提出的,并且两者在对权值的调整的算法非常相似,它们都是基于纠错学习规则的学习算法。感知器算法存在如下问题: 不能推广到一般的前向网络中; 函数不是线性可分时,得不出任何结果。而由美国斯坦福大学的WidrowHoff在研究自适应理论时提出的LMSE算法,由于其易实现因而很快得到了广泛应用,成为自适应滤波的标准算法。下面介绍自适应过程。
自适应过程是一个不断逼近目标的过程。它所遵循的途径以数学模型表示,称为自适应算法。通常采用基于梯度的算法,其中LMSE算法尤为常用。自适应算法可以用硬件(处理电路)或软件(程序控制)两种办法实现。前者依据算法的数学模型设计电路,后者则将算法的数学模型编制成程序并用计算机实现。算法有很多种,选择算法很重要,它决定了处理系统的性能质量和可行性。
自适应均衡器的原理就是按照某种准则和算法对其系数进行调整,最终使自适应均衡器的代价(目标)函数最小化,达到最佳均衡的目的。而各种调整系数的算法就称为自适应算法,自适应算法是根据某个最优准则来设计的。最常用的自适应算法有逼零算法、最陡下降算法、LMSE算法、RLS算法以及各种盲均衡算法等。
自适应算法所采用的最优准则有最小均方误差准则、最小二乘准则、最大信噪比准则和统计检测准则等,其中最小均方误差准则和最小二乘准则是目前最为流行的自适应算法准则。LMSE算法和RLS算法由于采用的最优准则不同,因此这两种算法在性能、复杂度等方面均有许多差别。
一种算法性能的好坏可以通过几个常用的指标来衡量,例如收敛速度——通常用算法达到稳定状态(即与最优值的接近程度达到一定值)的迭代次数表示; 误调比——实际均方误差相对于算法的最小均方误差的平均偏差; 运算复杂度——完成一次完整迭代所需的运算次数; 跟踪性能——对信道时变统计特性的自适应能力。
3.4.2LMSE算法原理
LMSE算法是针对准则函数引进最小均方误差这一条件而建立起来的。这种算法的主要特点是在训练过程中判定训练集是否线性可分,从而可对结果的收敛性做出判断。
LMSE算法属于监督学习的类型,而且是“模型无关”的,它是通过最小化输出和期望目标值之间的偏差来实现的。
LMSE算法属于自适应算法中常用的算法,它不同于C均值算法和ISODATA算法,后两种属于基于距离度量的算法,直观且容易理解。LMSE算法通过调整权值函数求出判别函数,进而将待测样本代入判别函数求值,最终做出判定,得出答案。
1. 准则函数
LMSE算法以最小均方差作为准则,因均方差为
E{[ri(X)-WTiX]2}(33)
因而准则函数为
J(Wi,X)=12E{[ri(X)-WTiX]2}(34)
准则函数在ri(X)-WTiX=0时取得最小值。准则函数对Wi的偏导数为
JWi=E{-X[ri(X)-WTiX]}(35)
2. 迭代方程
将式(35)代入迭代方程,得到
Wi(k+1)=Wi(k)+αkX(k)[ri(X)-WTi(k)X(k)](36)
对于多类问题来说,M类问题应该有M个权函数方程,而对于每一个权函数方程来说,如X(k)∈ωi,则
ri[X(k)]=1,i=1,2,…,M(37)
否则
ri[X(k)]=0,i=1,2,…,M(38)
3.4.3LMSE算法步骤
(1) 设各个权向量的初始值为0,即W0(0)=W1(0)=W2(0)=…=WM(0)=0。
(2) 输入第k次样本X(k),计算di(k)=WTi(k)X(k)。
(3) 确定期望输出函数值: 若X(k)∈ωi,则ri[X(k)]=1,否则ri[X(k)]=0。
(4) 计算迭代方程: Wi(k+1)=Wi(k)+αkX(k)[ri(X)-WTi(k)X(k)],其中αk=1k。
(5) 循环执行步骤(2),直到满足条件: 属于ωi类的所有样本都满足不等式di(X)>dj(X),j≠i。
3.4.4LMSE算法的MATLAB实现
1. 首先给定四类样本,各样本的特征向量经过增1
程序如下:
pattern=struct('feature',[])
p1=[864.451647.312665.9;
877.882031.663071.18;
1418.791775.892772.9;
1449.581641.583405.12;
864.451647.312665.9;
877.882031.663071.18;
1418.791775.892772.9;
1449.581641.583405.12;
1418.791775.892772.9;
1449.581641.583405.12;]
pattern(1).feature=p1'
pattern(1).feature(4,:)=1
pattern(1).feature实际的矩阵形式如下:
p1 =
1.0e+03 *
0.86451.64732.6659
0.87792.03173.0712
1.41881.77592.7729
1.44961.64163.4051
0.86451.64732.6659
0.87792.03173.0712
1.41881.77592.7729
1.44961.64163.4051
1.41881.77592.7729
1.44961.64163.4051
之后的三类,程序如下:
p2=[2352.122557.041411.53;
2297.283340.14535.62;
2092.623177.21584.32;
2205.363243.741202.69;
2949.163244.44662.42;
2802.883017.111984.98;
2063.543199.761257.21;
2949.163244.44662.42;
2802.883017.111984.98;
2063.543199.761257.21;]
pattern(2).feature=p2'
pattern(2).feature(4,:)=1
p3=[1739.941675.152395.96;
1756.7716521514.98;
1803.581583.122163.05;
1571.171731.041735.33;
1845.591918.812226.49;
1692.621867.52108.97;
1680.671575.781725.1;
1651.521713.281570.38;
1680.671575.781725.1;
1651.521713.281570.38;]
pattern(3).feature=p3'
pattern(3).feature(4,:)=1
p4=[373.33087.052429.47;
222.853059.542002.33;
401.33259.942150.98;
363.343477.952462.86;
104.83389.832421.83;
499.853305.752196.22;
172.783084.492328.65;
341.593076.622438.63;
291.023095.682088.95;
237.633077.782251.96;]
pattern(4).feature=p4'
pattern(4).feature(4,:)=1
2. 设权值向量的初始值均为0
初始化权值程序代码如下:
w=zeros(4,4);%初始化权值
MATLAB程序运行结果如下:
w =
0000
0000
0000
0000
3. 计算di(k)
程序代码如下:
for k=1:4
m=pattern(i).feature(:,j)
m=m/norm(m)
d(k)=w(:,k)'*m %计算d
……