《模式識別導(dǎo)論》課件第2章

第2章線性判別函數(shù)法2.1判別函數(shù)的基本概念2.2線性判別函數(shù)2.3感知器學(xué)習(xí)算法2.4最小均方誤差算法2.5Fisher線性判別法2.6線性二分能力在模式識別與分類中，可以根據(jù)訓(xùn)練樣本集提供的信息，直接進行分類器的設(shè)計。我們面臨的最簡單的是兩類樣本的分類問題，這時人們自然會想到能否在特征空間(決策域)中做一條直線(平面或超平面)將兩類樣本分開，需要解決的問題是這條直線(平面或超平面)如何去做，這就是基本的線性判別問題。至于更深一步的理論研究，例如,當(dāng)樣本集擴充后該分類判決是否還有效(也就是泛化性能)？分類界面是否還會是直線(平面或超平面)？樣本的分布與統(tǒng)計特征的關(guān)系如何?等等,也是要探討的問題。由于特征空間(決策域)的分界面是由數(shù)學(xué)表達式來描述的，如線性函數(shù)或各種非線性函數(shù)等，所以分界面方程的確定主要包括函數(shù)類型的選擇以及參數(shù)的確定。其中函數(shù)類型是由設(shè)計者選擇的，而參數(shù)的確定則是依據(jù)一定的準則函數(shù)并通過學(xué)習(xí)過程來實現(xiàn)的。線性分類器的優(yōu)點是簡單，在計算機上容易實現(xiàn)，因此在模式識別中被廣泛使用。

本章主要討論判別函數(shù)法和線性判別函數(shù)的基本概念，線性分類器的設(shè)計。

2.1判別函數(shù)的基本概念

模式識別系統(tǒng)的主要作用是判別各個模式的類別屬性。例如，一個兩類問題就是將模式x劃分為ω1和ω2兩類。對于一個二維的兩類問題，模式樣本可表示為x=(x1，x2)T，其中x1、x2為坐標變量(即模式的特征值)。所有的樣本分布在一個二維平面上，如圖2.1所示。如果在兩類之間能找到一條分界線將分屬于ω1和ω2的樣本分開，這樣就可以知道每個樣本的類別。設(shè)分界線的方程為

(2-1)

這里w1、w2、w0是方程的參數(shù)或權(quán)值。圖2.1兩類二維樣本的分布示意圖可以假設(shè)屬于ω1類的模式位于g(x)>0的一側(cè)，屬于ω2類的模式位于g(x)<0的一側(cè)。反之，如果將一個未知類別的模式x帶入g(x)，則應(yīng)該有下面的結(jié)果：若g(x)>0，則x屬于ω1類；若g(x)<0，則x屬于ω2類；若g(x)=0，則x落在分界線上，此時不能判定x的類別。因此，g(x)可以用來判斷某一未知模式所屬的類別，鑒于此我們稱g(x)為判別函數(shù)。

判別函數(shù)是直接用來對模式樣本進行分類的準則函數(shù)，也稱為判決函數(shù)或決策函數(shù)。尋找類別之間分界線的方法稱為判別函數(shù)法，判別函數(shù)法的結(jié)果提供了一個確定的分界線方程，這個分界線方程就是判別函數(shù)。因此，判別函數(shù)描述了各類之間的分界線的具體形式。判別函數(shù)可以是線性函數(shù)，也可以是非線性函數(shù)，這取決于模式類在空間中的分布情況，以及我們對分布的先驗信息的了解程度。由于線性分類器涉及到的數(shù)學(xué)方法比較簡單，在計算機上容易實現(xiàn)，因此得到廣泛的應(yīng)用。但是在模式識別的許多具體問題中，線性分類器固有的局限性使得它并不能提供理想的識別效果，必須求助于非線性分類器。這里需要強調(diào)指出的是，有些簡單的非線性分類器對模式識別問題的解決顯得既簡單效果又好。

2.2線性判別函數(shù)

線性判別函數(shù)是一種最簡單的判別函數(shù)，它是由所有特征向量的

線性組合構(gòu)成的。

2.2.1線性判別函數(shù)的一般形式

在一般的d維特征空間中，線性判別函數(shù)的表達式為

g(x)=wTx+w0

(2-2)

式中:x是d維特征向量，又稱為樣本向量；w0是常數(shù)且非零，也稱為閾值權(quán)；w是d維加權(quán)向量。x和w分別表示為

x=(x1，x2，…,xd)T，w=(w1，w2，…,wd)T

在二維歐氏空間中，由線性判別函數(shù)所確定的判別邊界為一條直線；在三維空間中,為一個平面；當(dāng)維數(shù)超過三時,判別邊界稱為超平面。通常由線性判別函數(shù)確定的判別界面通稱為超平面。

在式(2-2)表示的一般的線性判別函數(shù)中，由于w0非零，決策超平面不通過空間原點，因此可以使用廣義線性函數(shù)的擴維方法實現(xiàn)齊次化問題。式(2-2)也可以寫成增廣向量的形式：(2-3)式中:y=(x1，x2，…,xd，1)T稱為增廣樣本向量，a=(w1，w2，…,wd，w0)T稱為增廣權(quán)向量。g[(x)]=aTy稱為廣義線性判別函數(shù)。在這個新的特征空間中，決策超平面通過原點，且特征空間的維數(shù)由d維擴張為d+1維。2.2.2線性判別函數(shù)的基本性質(zhì)

下面在模式類線性可分的情況下，討論線性判別函數(shù)的性質(zhì)。

1.兩類情況

已知兩個模式類ω1、ω2，待識別樣本x，則線性判別函數(shù)具有如下性質(zhì)；(2-4)此時g(x)=0為d維空間的一個分類超平面。

2.多類情況

對于m個線性可分的模式類ω1，ω2，…，ωm，有以下三種劃分方式。

1)ωi

/兩分法

ωi

/兩分法的基本原理是將每一個模式類用一個單獨的判別界面與其他模式類分開。ωi類的判別函數(shù)gi(x)可以將屬于ωi類的樣本與不屬于ωi類的樣本分開。決策準則為，i=1，…，m(2-5)若僅存在gk(x)>0，k∈{1，2，…，m}，而其余gj(x)<0(j≠k，j∈{1，2，…，m})，則判定x∈ωk類。

圖2.2是一個二維三類問題的ωi/兩分法分類示意圖。圖2.2ωi/兩分法示意圖

圖2.2中每一類都可用一個簡單的直線判別界面將該類與其他類分開。例如樣本x∈ω1，從圖中的幾何表示可知，需同時滿足下面三個條件：g1(x)>0，g2(x)<0，g3(x)<0。這時不能只用g1(x)>0這一個條件判定x所屬的類別，因為在模式空間中還存在不確定的區(qū)域，它們不屬于三類中的任何一類，如圖中g(shù)1(x)<0，g2(x)<0，g3(x)<0所確定的區(qū)域。因此對m類問題，需要同時有m個判別函數(shù)。例2.1對于一個三類問題，假定三個判別函數(shù)分別為

g1(x)=－x1+x2－1，g2(x)=x1+x2－9，g3(x)=－x2+1

請畫出各類判別區(qū)域，并判斷x=(7，5)T屬于哪一類。

解將x=(7，5)T代入三個判別函數(shù)中，有

g1(x)=－7+5－1=－3<0

g2(x)=7+5－9=3>0

g3(x)=－5+1=－4<0

因為g1(x)<0，g2(x)>0，g3(x)<0，所以x∈ω2。各類的判別區(qū)域如圖2.3所示，其中ω1的判別區(qū)域位于g1(x)>0，g2(x)<0，g3(x)<0的區(qū)域；ω2的判別區(qū)域位于g1(x)<0，g2(x)>0，g3(x)<0的區(qū)域；ω3的判別區(qū)域位于g1(x)<0，g2(x)<0，g3(x)>0的區(qū)域。圖中的IR1、IR2、IR3區(qū)域是兩個判別函數(shù)大于0的區(qū)域，IR4區(qū)域是三個判別函數(shù)都小于0的區(qū)域，這些不確定區(qū)域的樣本是無法分類的。圖2.3各類判別區(qū)域示意圖

2)ωi/ωj兩分法

我們可將任意的兩個類別用一個判別界面分開。對于m類中的任意兩類：由ωi、ωj(i≠j)可以確定一個超平面gij(x)=來把ωi、ωj兩類分開，且gij(x)=－gji(x)。決策準則為

識別ωi類時，只有下標以i開頭的m－1個判別函數(shù)全為正值時，才能判定x∈ωi。若其中有一個為負值，則為不確定區(qū)域(IR區(qū))。i，j∈{1，2，…，m}，i≠j

(2-6)

ωi/ωj兩分法每分離出一類模式，需要m－1個判別函數(shù)，要分離出所有的m類模式，共需要個判別函數(shù)。

圖2.4是一個二維三類問題的ωi/ωj兩分法分類示意圖。圖中有三個判別界面g12(x)=0，g13(x)=0，g23(x)=0，三個模式類ω1，ω2，ω3，每個判別界面都可以將兩個模式類分開，但穿過了其他模式類。以ω1類為例，只有下標以1開

頭的所有判別函數(shù)值都大于零，即g12(x)>0，g13(x)>0時，才能判定x∈ω1類，而g23(x)在識別ω1類模式時不起作用。圖2.4ωi/ωj兩分法分類示意圖例2.2對于一個三類問題，假定三個判別函數(shù)為

g12(x)=－x1－x2+6，g13(x)=－x1+4，g23(x)=－x1+x2

請畫出各類判別區(qū)域，并判斷x=(5，3)T屬于哪一類。

解將x=(5，3)T代入三個判別函數(shù)中，有g(shù)12(x)=－5－3+6=－2，g13(x)=－5+4=－1，g23(x)=－5+3=－2。也可寫成g21(x)=2，g31(x)=1，g32(x)=2。因為g31(x)>0，g32(x)>0

，所以x∈ω3。

各類的判別區(qū)域如圖2.4所示，其中ω1的判別區(qū)域位于g12(x)>0，g13(x)>0的區(qū)域；ω2的判別區(qū)域位于g21(x)>0，g23(x)>0的區(qū)域；ω3的判別區(qū)域位于g31(x)>0，g32(x)>0的區(qū)域。在三條分界線相交組成的三角形區(qū)域內(nèi)的樣本無法判斷所屬類別，該區(qū)域為不確定區(qū)域IR。

3)ωi/ωj兩分法特例

有時為了處理方便，可將ωi/ωj兩分法的約束條件放寬。對于m類的判別問題，當(dāng)確定了m個超平面時，采用下列決策準則：

則x∈ωi。

根據(jù)決策準則式(2-7)，任一個模式x總能劃分到m類中的某一個模式類中去，因此作為ωi/ωj兩分法的特例，除邊界之外不存在不確定區(qū)域。圖2.5是m=3時的判別區(qū)域劃分示意圖。(2-7)圖2.5ωi/ωj兩分法(特例)分類示意圖例2.3對于一個三類問題，假定三個判別函數(shù)為

g1(x)=－x1+x2，g2(x)=x1+x2－1，g3(x)=－x2

試用ωi/ωj兩分法特例方法判斷x=(－0.5，1)T屬于哪一類，并分別給出三類的判別界面。

解分別計算得g1(x)=1.5，g2(x)=－0.5，g3(x)=－1，因為g1(x)>g2(x)，g1(x)>g3(x)，所以x∈ω1。

ω1類的判別界面為

g1(x)－g2(x)=－2x1+1=0，g1(x)－g3(x)=－x1+2x2=0

ω2類的判別界面為

g2(x)－g1(x)=2x1－1=0，g2(x)－g3(x)=x1+2x2－1=0

ω3類的判別界面為

g3(x)－g1(x)=x1－2x2=0，g3(x)－g2(x)=－x1－2x2+1=0

三類判別界面如圖2.5所示。2.2.3線性判別函數(shù)的幾何性質(zhì)

對于兩類問題，設(shè)線性判別函數(shù)為g(x)=wTx+w0，其中w=(w1，w2，…，wd)T，x=(x1，x2，…，xd)T，則由g(x)確定的d維歐幾里德空間中的超平面為g(x)=wTx+w0=0。設(shè)超平面為H，則對H上的任意兩點x1，x2有

g(x1)=wTx1+w0=wTx2+w0=g(x2)

(2-8)

即

wT(x1－x2)=0

(2-9)式(2-9)表明向量w和x1－x2正交，由x1，x2的任意性可知，w垂直于超平面H上的任意向量x1－x2，也就是說w垂直于超平面H，即w是超平面H的法向量。根據(jù)決策準則式(2-7)，當(dāng)g1(x)>g2(x)時，判定x∈ω1；否則，x∈ω2。從而得出法向量w的方向由超平面的負側(cè)指向正側(cè)。設(shè)超平面的單位法向量為u，即

其中||w||為向量w的模值，||w||2=wTw。二維情況時的超平面示意圖如圖2.6所示。(2-10)圖2.6超平面示意圖當(dāng)x不在超平面H上時，設(shè)xp為x在H上的投影向量，則x可表示為

其中r為x到超平面H的距離。這時

因為xp在超平面H上，故有g(shù)(xp)=wTxp+w0=0，于是g(x)=r||w||。因此，x到超平面H的距離為(2-11)(2-12)(2-13)如圖2.7所示，這是一種代數(shù)距離(帶有正負號)。當(dāng)x在超平面正側(cè)時，g(x)>0；反之，g(x)<0。

特別的，當(dāng)x在原點時，g(x)=w0，即原點到超平面

H的距離為

若w0>0，則原點在超平面H的正側(cè)；若w0<0，則原點在超平面H的負側(cè)；若w0=0，則超平面H穿過原點。(2-14)圖2.7點到超平面的距離綜上所述，對于兩類問題，線性判別函數(shù)的幾何意義在于利用一個超平面實現(xiàn)對d維特征空間Rd的劃分，超平面方

向由法向量w確定，它的位置由閾值w0確定。判別函數(shù)正比于x點到超平面的代數(shù)距離。2.2.4設(shè)計線性分類器的主要步驟

分類器的設(shè)計是利用訓(xùn)練樣本集建立線性判別函數(shù)，找到表達式中最好的加權(quán)系數(shù)向量w和w0(或增廣權(quán)向量α)，最好的結(jié)果恰好出現(xiàn)在準則函數(shù)的極值點上。這樣，線性分類器的設(shè)計工作就轉(zhuǎn)化為尋找準則函數(shù)的極值點w*和w*0(或a*)的最優(yōu)化問題。設(shè)計線性分類器的主要步驟如下：

(1)選取一組有類別標志的樣本集合R={x1，x2，…，xn}。

(2)確定準則函數(shù)J，要求滿足以下兩個條件：①J應(yīng)為樣本集R、w和w0(或a)的函數(shù)；②J的值反映分類性能，它的極值對應(yīng)于“最好”的決策。

(3)用最優(yōu)化技術(shù)求出準則函數(shù)的極值解w*和w*0(或a*)。

2.3感知器學(xué)習(xí)算法

感知器準則函數(shù)的基本思想是尋找一個權(quán)向量，使得規(guī)范化增廣樣本向量集的錯分樣本數(shù)最少。下面先介紹幾個相關(guān)的概念。

2.3.1幾個基本概念

1.線性可分的定義

設(shè)由n個樣本構(gòu)成的樣本集合Y={y1，y2，…，yn}，其中yi為d維的來自于ω1和ω2類的增廣樣本向量。如果存在權(quán)向量a使得對于任意的y∈ω1有aTy>0，則稱樣本集Y是線性可分的，否則稱為線性不可分的。反過來，如果樣本集合Y是線性可分的，則一定存在權(quán)向量a將樣本集合Y正確分為兩類。

2.樣本規(guī)范化

對于任意一個樣本yi，如果滿足aTyi>0，則屬于ω1類；如果滿足aTyi<0，則屬于ω2類。對樣本進行規(guī)范化處理，即對ω2類的全部樣本都乘以-1，有

則對全部樣本yn′∈ω1∪ω2，需尋找滿足aTyn′>0的權(quán)向量。(2-15)

3.解向量和解區(qū)

對于規(guī)范化增廣樣本向量而言，滿足aTyi>0

(i=1，2，…，n)的權(quán)向量稱為解向量，記為a*。權(quán)向量a可看成權(quán)空間中的一點，對于任一yi，要求aTyi>0。方程aTyi=0在權(quán)向量空間確定了一個超平面Hi，這個超平面的法向量為a，超平面正側(cè)的向量滿足aTyi>0。n個樣本將確定n個超平面，每個超平面把權(quán)空間分為兩個半空間。所以，滿足aTyi>0(i=1，2，…，n)的權(quán)向量必在這n個超平面正側(cè)的交疊區(qū)內(nèi)，這個區(qū)域就是a的解區(qū)，解區(qū)中的任意向量都是解向量a*，如圖2.8所示。為了使解向量a*更加可靠，需要對解區(qū)加以限制。一

般來講，解向量越靠近解區(qū)中間,越能對新的樣本進行正確分類。因此引入余量b>0，使解向量滿足aTyi>b(i=1，2，

…，n)。顯然,由此確定的正半空間的交疊區(qū)(新解區(qū))位于原解區(qū)中，而且它的邊界離原來解區(qū)邊界的距離為b/||yi||，如圖2.9所示。

以上關(guān)于兩類問題的解區(qū)和解向量的概念也可以推廣到線性可分的多類問題中。圖2.8權(quán)向量的解區(qū)和解向量圖2.9解區(qū)和解向量示意圖2.3.2感知器算法

對于線性可分的兩類問題ω1，ω2，設(shè)規(guī)范化增廣樣本集合Y={y1，y2，…，yn}，n為樣本容量，尋找解向量a使其滿足

aTyi>0，i=1，2，…，n

(2-16)

為此構(gòu)造感知器準則函數(shù)

其中yk為錯分樣本集合，當(dāng)y∈yk時，有

-aTy≥0

(2-18)(2-17)顯然Jp(a)≥0。當(dāng)且僅當(dāng)全部樣本分類正確且沒有錯分樣本時才會有Jp(a*)=minJp(a)=0，此時a*就是要尋找的最優(yōu)解向量。下面給出幾個求解a*的算法。

1)梯度下降算法

在數(shù)學(xué)分析中，函數(shù)J(a)的梯度方向J(ak)是這樣一個方向：在點wk處，它指向J(a)增加最快的方向,而J(a)的負梯度方向－J(ak)則指向J(a)下降最快的方向。設(shè)準則函數(shù)為Jp(a)，使得Jp(a)達到最小時的最優(yōu)解向量為a*。下面我們采用感知器的梯度下降算法求解最優(yōu)解a*。

感知器準則函數(shù)的梯度函數(shù)為(2-19)梯度下降法的迭代公式為

其中yk是被權(quán)向量a(k)錯分的樣本集，ρk為第k次迭代時的步長因子。ρk的取值大小是有理論依據(jù)的，為了簡化分析取步長因子ρk=1，得迭代式為

可以證明，對于線性可分的樣本集，經(jīng)過有限次修正，一定可以找到一個解向量a*，使得算法在有限次迭代后收斂。收斂速度取決于初始值a(0)與系數(shù)ρk。

(2-20)(2-21)式(2-21)在迭代時，每次計算需要用到所有的錯分樣本。既然從原理上已經(jīng)確定了錯分樣本對于迭代解的修正方向，為了減少計算量，每次迭代只由一個錯分樣本完成，表示為a(k+1)=a(k)+yk

(2-22)

式中yk為第k次迭代使用的單個錯分樣本。式(2-22)稱為單錯分樣本迭代式。感知收斂定理如果樣本集合是線性可分的，那么由式(2-22)所得到的序列必定終止于某個解向量。

證明設(shè)為目標解向量，如果樣本集合線性可分，則有Tyi>0。設(shè)比例因子α>0，由式(2-22)得到

(2-23)

其平方范數(shù)為

由于yk為錯分樣本，有a(k)Tyk≤0，因此

(2-24)

設(shè)樣本向量最大長度

(2-25)和解向量與樣本向量的最小內(nèi)積

(2-26)

不等式可化為

(2-27)

選擇比例因子

(2-28)得到

(2-29)每次校正，從a(k+1)到的平方距離則減少τ2，經(jīng)過k次校正后有

(2-30)

由于平方距離非負，因而經(jīng)過不超過

次校正迭代終止。(2-31)

2)獎懲算法

將感知器梯度下降算法進一步具體化就是“獎懲”算法；當(dāng)分類器發(fā)生分類錯誤時，通過修正權(quán)向量對分類器進行“懲罰”，使其向正確的方向轉(zhuǎn)換；當(dāng)分類正確時，保持權(quán)向量不變對其進行“獎勵”，表現(xiàn)為不罰。以兩類分類情況為例，算法具體步驟為：

(1)設(shè)規(guī)范化增廣樣本集合Y={y1，y2，…，yn}，初始化權(quán)向量，置k=0。

(2)輸入n個訓(xùn)練樣本，計算判別函數(shù)g(yk)=a(k)Tyk，其中a(k)為第k次迭代的權(quán)向量。

(3)按照如下公式修正權(quán)向量：

其中c為正的校正增量。如果a(k)Tyi>0，則表明分類器對樣本yi的分類正確，權(quán)向量保持不變。如果a(k)Tyi≤0，則表明分類器對樣本yi的分類發(fā)生了錯誤，需要修正權(quán)向量。

(4)令k=k+1，返回(2)，直到權(quán)向量a對所有的訓(xùn)練樣本

均穩(wěn)定不變，此時所有的訓(xùn)練樣本被正確分類。(2-32)例2.4已知兩類訓(xùn)練樣本；

ω1：x1=(0，0)T，x2=(0，1)T

ω2：x3=(1，0)T，x4=(1，－1)T

用感知器獎懲算法求解判別函數(shù)，并繪出判別界面。

解將訓(xùn)練樣本寫成增廣向量的形式，并進行規(guī)范化處理，將ω2類的樣本乘以－1，得

x1=(0，0，1)T，x2=(0，1，1)T，x3=(－1，0，－1)T，x4=(－1，1，－1)T取初始權(quán)向量w(1)=［0，0，0］T，取校正增量c=1,則迭代過程如下；

第一次迭代：，故權(quán)向量修改為w(2)=w(1)+x1=(0，0，0)T+(0，0，1)T=(0，0，1)T，故權(quán)向量修改為

w(3)=w(2)=(0，0，1)T

，故權(quán)向量修改為w(4)=w(3)+x3=(0，0，1)T+(－1，0，－1)T=(－1，0，0)T

，故權(quán)向量修改為

w(5)=w(4)=(－1，0，0)T

在第一次迭代中有兩次w(k)Txi≤0，說明發(fā)生了兩次錯判，進行第二次迭代。第二次迭代：

w(5)Tx1=0≤0，故w(6)=w(5)+x1=(－1，0，0)T+(0，0，1)T=(－1，0，1)T;

w(6)Tx2=1>0，故w(7)=w(6)=(－1，0，1)T;

w(7)Tx3=0≤0，故w(8)=w(7)+x＋=(－2，0，0)T;

w(8)Tx4=2>0，故w(9)=w(8)=(－2，0，0)T。

第三次迭代：

w(9)Tx1=0≤0，故w(10)=w(9)+x1=(－2，0，0)T+(0，0，1)T=(－2，0，1)T;

w(10)Tx2=1>0，故w(11)=w(10);

w(11)Tx3=1>0，故w(12)=w(11);

w(12)Tx4=1>0，故w(13)=w(12)。第四次迭代：

w(13)Tx1=1>0，故w(14)=w(13)；

w(14)Tx2=1>0，故w(15)=w(14)；

w(15)Tx3=1>0，故w(16)=w(15)；

w(16)Tx4=1>0，故w(17)=w(16)。

由于第四次迭代的分類結(jié)果全部正確，因此解向量為w=(－2，0，1)T，相應(yīng)的判別函數(shù)為g(x)=－2x+1，判別界面為g(x)=0。

這里需要指出的是，當(dāng)初始值w(1)和c取其他值時，結(jié)果可能不一樣。因此，感知器獎懲算法的解不是單值的。

2.4最小均方誤差算法

感知器算法是針對線性可分的情形設(shè)計的。對于線性不可分的情況，它具有不收斂的缺點。最小均方誤差(LeastMeanSquareError，LMSE)算法是對準則函數(shù)引進最小均方誤差這一條件而建立起來的，算法的主要特點是在訓(xùn)練過程中判定訓(xùn)練集是否線性可分，從而對結(jié)果的收斂性做出判斷。

針對兩類問題，設(shè)規(guī)范化增廣樣本集合Y={y1，y2，…，yN}，尋找權(quán)向量a滿足

aTyi>0，i=1，2，…，N

(2-33)任意給定一個N維向量b=(b1，b2，…，bN)T，其中bi為小的正數(shù)且滿足

aTyi=bi，i=1，2，…，N

(2-34)

于是可以得到一個超定方程組

Ya=b

(2-35)

其中Y為訓(xùn)練樣本的增廣矩陣,即，通常情況下N>d,一般為列滿秩矩陣。方程個數(shù)多于未知數(shù)

的個數(shù)，一般為矛盾方程組，通常不存在精確解。定義誤差向量為

e=Ya－b

(2-36)定義均方誤差準則函數(shù)為

使Js(a)最小的解a*稱為最小二乘解，又稱為偽逆解或MSE解。由式(2-37)定義的準則函數(shù)也稱為MSE準則函數(shù)。

(2-37)為了求解，首先計算Js(a)的梯度并令其為零

即

YTYa*=YTb

(2-39)

由于矩陣YTY是d×d維的方陣，而且一般是非奇異的，兩邊左乘(YTY)－1，得到

a*=(YTY)－1YTb

(2-40)

令，則。其中稱為Y的偽逆，a*為偽逆解。

(2-38)按照式(2-40)求解a*時，需要計算矩陣YTY及其逆矩陣(YTY)－1，計算量大，通常可以使用梯度下降法以迭代的方式求解。由最小均方誤差準則的梯度公式使用梯度下降法作迭代式

ak+1=ak－ρkYT(Ya－b)

(2-41)

其中a0為任意的迭代初始值，經(jīng)過有限次迭代可得到最優(yōu)解。為了進一步減少計算量和存儲空間，可以使用單個樣本修正算法，則迭代式(2-41)可修改為

ak+1=ak+ρk(bk-aTkyk)yk

(2-42)其中迭代初始向量a0為任意向量，單個樣本yk為滿足

aTkyk≠bk

(2-43)

的樣本。

由于bk是任意給定的正常數(shù)，因此，理想的逼近條件aTkyk=bk幾乎是永遠不可能滿足的，修正過程永遠都不可能結(jié)束。為了保證算法的收斂性，選取

使得步長因子ρk隨著迭代步數(shù)的增加而逐漸減小，保證算法收斂于滿意的解a*。(2-44)

2.5Fisher線性判別法

2.5.1類內(nèi)離散度矩陣和類間離散度矩陣

Fisher準則是由R.A.Fisher在1936年首次提出的。對于d維空間中的樣本，投影到某一條直線上，樣本極有可能混在一起無法識別，如果能夠找到一個投影方向，使得樣本集合在該投影方向上最易區(qū)分，這就是Fisher準則的基本原理。如圖2.10所示，在原空間中不易區(qū)分的兩類樣本，如果選擇投影方向w1，則兩類樣本混雜在一起無法區(qū)分；如果選擇投影方向w2，則兩類樣本極易區(qū)分。圖2.10Fisher投影原理已知兩類問題的n個d維樣本x1，x2，…，xn，其中類別為ωi(i=1，2)且樣本容量為ni，其子集為X1、X2。對xi(i=1，2，…，n)做如下變換可實現(xiàn)d維空間到一維空間的映射：yi=wTxi，i=1，2，…，n

(2-45)

則由X1、X2可以得到兩個相應(yīng)的集合Y1、Y2。由于我們特別關(guān)注的是w的方向，因此可以令||w||=1，則yi就是xi在w方向上的投影。Fisher準則的目的就是尋找最好的投影方向，使得w為最好的投影向量w*。

在定義Fisher準則函數(shù)之前，首先定義幾個必要的基本參數(shù)。

1.在d維空間中

(1)各類樣本的均值向量mi；

(2)樣本類內(nèi)離散度矩陣Si和總類內(nèi)離散度矩陣Sw；

Sw=S1+S2(2-48)

(3)樣本類間離散度矩陣Sb；

Sb=(m1－m2)(m1－m2)T(2-49)

其中Sw是對稱半正定矩陣，且當(dāng)n>d時通常是非奇異的。Sb也是對稱半正定矩陣，在兩類條件下，它的秩最大等于1。

(2-46)(2-47)

2.在一維空間中

(1)各類樣本的均值；

(2)類內(nèi)離散度和總類內(nèi)離散度；(2-50)(2-51)(2-52)2.5.2Fisher線性判別法

下面定義Fisher準則函數(shù)。希望投影后，在一維空間中各類樣本分得越開越好，即希望均值之差越大越好；同時希望各類樣本內(nèi)部密集，即類內(nèi)離散度

越小越好。根據(jù)上述兩條規(guī)則，構(gòu)造Fisher準則函數(shù)如下；

使JF(w)達到最大值的w即為最佳投影方向w*。

為了求出JF(w)的極大值點，需要將JF(w)轉(zhuǎn)化為w的顯式函數(shù),即(2-53)(2-56)(2-54)則(2-55)再由類內(nèi)離散度得到

故Fisher準則函數(shù)關(guān)于的顯式為

下面求使JF(w)取最大值時的w*。上式中的JF(w)是著名的廣義瑞利(Rayleigh)商，可以用Lagrange乘子法求解。令分母等于非零常數(shù)，即

wTSww=C≠0

(2-59)

構(gòu)造Lagrange函數(shù)

L(w，λ)=wTSbw－λ(wTSww－C)

(2-60)(2-57)(2-58)其中λ為Lagrange乘子，對上式求關(guān)于w的偏導(dǎo)，并令其為零,即

得

Sbw*－λSww*=0

(2-62)

由于Sw是非奇異的，兩邊左乘S-1w，得到

S-1wSbw*=λw*

(2-63)

其中λ為矩陣S-1wSb的特征值，w*為對應(yīng)特征值λ的特征向量，即最佳投影的坐標向量。(2-61)另外，我們還可以不通過求特征值，直接給出最優(yōu)解w*的求解方法。由

Sb=[(m1－m2)][(m1－m2)]T

得到

Sbw*=[(m1－m2)][(m1－m2)]Tw*

=[(m1－m2)][(m1－m2)]Tw*]

=R[(m1－m2)]

(2-64)

其中

R=[(m1－m2)]Tw*

(2-65)為一標量，所以Sbw*總在[(m1－m2)]方向上。由(2-63)式知

λw*=S－1wSbw*=S－1w(m1－m2)R

(2-66)

于是

忽略比例因子得最優(yōu)解為

w＝為使得Fisher準則函數(shù)取極大值時的解，即d維空間的樣本在一維空間中的最佳投影方向。利用w*，將樣本xi往該方向上投影，可得(2-67)(2-68)

yi=(w*)Txi

(2-69)

利用Fisher準則函數(shù)獲得最佳一維投影后，需要確定一個閾值點y0。根據(jù)決策規(guī)則；若y>y0，則x∈ω1，否則x∈ω2。

閾值y0的確定可以采用以下幾種方法來實現(xiàn)；(2-70)(2-71)(2-72