模式識別線性判別函數(shù)與分類器設(shè)計

第二章線性判別函數(shù)與線性分類器設(shè)計判別函數(shù)

線性判別函數(shù)線性判別函數(shù)的性質(zhì)線性分類器設(shè)計梯度下降法—迭代法感知器法最小平方誤差準則(MSE法)---非迭代法Fisher分類準則假設(shè)對一模式X已抽取n個特征，表示為：模式識別問題就是根據(jù)模式X的n個特征來判別模式屬于ω1,ω2,

…,

ωm類中的那一類?！?.1判別函數(shù)

例如右上圖：三類的分類問題，它們的邊界線就是一個判別函數(shù)用判別函數(shù)進行模式分類，取決兩個因素：判別函數(shù)的幾何性質(zhì)：線性與非線性判別函數(shù)的參數(shù)確定：判別函數(shù)形式+參數(shù)判別函數(shù)包含兩類一類是線性判別函數(shù)線性判別函數(shù)：線性判別函數(shù)是統(tǒng)計模式識別的基本方法之一，簡單且容易實現(xiàn)廣義線性判別函數(shù)所謂廣義線性判別函數(shù)就是把非線性判別函數(shù)映射到另外一個空間（高維）變成線性判別函數(shù)分段線性判別函數(shù)另一類是非線性判別函數(shù)§2.2

線性判別函數(shù)現(xiàn)在對兩類問題和多類問題分別進行討論：一、兩類問題：即:

1.二維情況：取兩個特征向量這種情況下判別函數(shù):在兩類別情況，判別函數(shù)g

(x)

具有以下性質(zhì)：這是二維情況下判別由判別邊界分類。情況如圖：2.n維情況：現(xiàn)抽取n個特征為：判別函數(shù)：

另外一種表示方法：模式分類：當g1(x)=WTX=0為判別邊界。當n=2時，二維情況的判別邊界為一直線。當n=3時，判別邊界為一平面。當n>3時，則判別邊界為一超平面。1.第一種情況：每一模式類與其它模式類間可用單個判別平面把一個類分開。這種情況，M類可有M個判別函數(shù)，且具有以下性質(zhì)：二、對于多類問題模式有ω1,ω2,…,ωm

個類別，可分三種情況：此情況可理解為兩分法。

下圖所示，每一類別可用單個判別邊界與其它類別相分開。如果一模式X屬于ω1，則由圖可清楚看出：這時g1(x)>0而g2(x)<0

，g3(x)<0

。ω1

類與其它類之間的邊界由g1(x)=0確定。例：已知三類ω1,ω2,ω3的判別函數(shù)分別為：因此，三個判別邊界為：作圖如下：

對于任一模式X如果它的g1(x)>0，g2(x)<0，g3(x)<0，則該模式屬于ω1類。相應ω1類的區(qū)域由直線-x2+1=0

的正邊、直線-x1+x2-5=0

和直線-x1+x2=0的負邊來確定。必須指出，如果某個X使二個以上的判別函數(shù)gi(x)>0。則此模式X就無法作出確切的判決。如圖中IR1,IR3，IR4區(qū)域。另一種情況是IR2區(qū)域，判別函數(shù)都為負值。IR1，IR2，IR3，IR4。都為不確定區(qū)域。問當x=(x1,x2)T=(6,5)T時屬于那一類結(jié)論：

g1(x)<0，g2(x)>0，g3(x)<0所以它屬于ω2類這樣有M(M_1)/2個判別平面。對于兩類問題，M=2，則有一個判別平面。同理，三類問題則有三個判別平面。判別函數(shù)：判別邊界：判別條件：第二種情況：每個模式類和其它模式類間可分別用判別平面分開，一個判別界面只能分開兩個類別，不一定能把其余所有的類別分開；這種情況可理解為二分法。判別函數(shù)性質(zhì)：假設(shè)判別函數(shù)為：判別邊界為：用方程式作圖：問:未知模式X=(x1,x2)T=(4,3)T屬于那一類？代入判別函數(shù)可得:把下標對換可得:因為結(jié)論：所以X屬于ω3類結(jié)論：判別區(qū)間增大，不確定區(qū)間減小，比第一種情況小的多。第三種情況：判別函數(shù)：

判別規(guī)則：判別邊界：gi(x)=gj(x)或gi(x)-gj(x)=0說明：就是說，要判別模式X屬于那一類，先把X代入M個判別函數(shù)中，判別函數(shù)最大的那個類別就是X所屬類別。類與類之間的邊界可由gi(x)=gj(x)或gi(x)-gj(x)=0來確定。每類都有一個判別函數(shù),存在M個判別函數(shù)，這種情況可理解為無不確定區(qū)的二分法。右圖所示是M=3的例子。對于ω1類模式，必然滿足g1(x)>g2(x)

和g1(x)>g3(x)

。假設(shè)判別函數(shù)為：則判別邊界為：結(jié)論：不確定區(qū)間沒有了，所以這種是最好情況。用上列方程組作圖如下：問假設(shè)未知模式x=(x1,x2)T=(1,1)T

，則x屬于那一類。把它代入判別函數(shù)：得判別函數(shù)為：因為所以模式x=(1,1)T屬于類。關(guān)于線性判別函數(shù)的結(jié)論：模式類別若可用任一線性判別函數(shù)來劃分，這些模式就稱為線性可分；一旦線性判別函數(shù)的參數(shù)確定，這些函數(shù)即可作為模式分類的基礎(chǔ)。對于M（M≥2）類模式分類，第一、三種情況需要M個判別函數(shù)，第二種情況需要M(M-1)/2個判別函數(shù)。對于第一種情況，每個判別函數(shù)都要把一種類別（比如i類）的模式與其余M-1種類別的模式劃分開，而不是僅將一類與另一類劃分開。實際上，一個類的模式分布要比M-1類模式分布更聚集，因此后兩種情況實現(xiàn)模式線性可分的可能性要更大一些?！?.3廣義線性判別函數(shù)研究動機線性判別函數(shù)簡單，容易實現(xiàn)；非線性判別函數(shù)復雜，不容易實現(xiàn)；若能將非線性判別函數(shù)轉(zhuǎn)換為線性判別函數(shù)，則有利于模式分類的實現(xiàn)。基本思想設(shè)一模式集{x}，在模式空間x中線性不可分，但在模式空間x*中線性可分，其中x*的各個分量是x的單值實函數(shù)，x*的維數(shù)k高于x的維數(shù)n，即

x*=(f1(x),f2(x),….,fk(x)),k>n

則分類界面在x*空間是線性的，在x空間是非線性的，此時只要將模式x進行非線性變換，使之變換后得到維數(shù)更高的模式x*，就可用線性判別函數(shù)進行分類。廣義線性判別函數(shù)若將非線性判別函數(shù)表示為：式中是模式x的單值函數(shù)，若定義成廣義形式：其中，，且于是，有由此可知，非線性判別函數(shù)已變換成線性，稱為廣義線性判別函數(shù)。廣義線性判別函數(shù)的意義線性的判別函數(shù)：若fi(x)=ax+b是一次函數(shù)，這相當于把x空間進行了尺度放縮和平移。fi(x)選用二次多項式函數(shù)：對于二維情況：模式空間為，原判別函數(shù)為：可線性化為：其中對于n維情況，則有式中各項的組成包括x各個分量的二次項、一次項和wn+1項，其總項數(shù)為顯然，x*的維數(shù)比x高，w分量的數(shù)目亦與x*的維數(shù)相同。x*的各分量的一般式為fi(x)為r次多項式函數(shù)，x是n維的情況，則于是，判別函數(shù)g(x)可按如下遞推：討論：(1)g(x)的總項數(shù)為：

顯然，Nw隨r和n的增加會迅速增大，即使原來模式x的維數(shù)不高，若采用次數(shù)r較高的多項式來變換，也會使變換后的模式x*的維數(shù)很高，給分類帶來很大困難（稱為維數(shù)災難）。實際上，一般r只取2。(2)采用二次多項式函數(shù)fi(x)的判別函數(shù)也可用矩陣形式表示：式中，A為實對稱矩陣。判別界面的幾何形狀由矩陣A決定：若A=I，則判別函數(shù)為超球面；若A為正定，則判別函數(shù)為超橢球面，軸方向為A的本征向量方向；A為半正定，判別函數(shù)為超橢圓柱面；A為不定，判別函數(shù)為超雙曲面體。§2.3線性判別函數(shù)的性質(zhì)一、模式空間與加權(quán)空間：模式空間：由構(gòu)成的n維歐氏空間，增廣形式為。W是此空間的加權(quán)向量，它決定模式的分界面H，W與H正交。加權(quán)空間：以為變量構(gòu)成的歐氏空間模式空間與加權(quán)空間的幾何表示如下圖：加權(quán)空間構(gòu)造為：設(shè)是加權(quán)空間分界面上的一點，代入上式得：對于一兩類問題：對于樣本x1、x2、x3、x4，可知g(x1)=g

(x2)=g

(x3)=g

(x4)=0，可分別作出通過加權(quán)空間原點的其他平面。這是一個不等式方程組，它的解處于由ω1類所有模式?jīng)Q定的平面的正邊和由ω2類所有模式?jīng)Q定的平面的負邊，它的解區(qū)即為凸多面錐。加權(quán)空間的性質(zhì)：加權(quán)空間的所有分界面都通過坐標原點。在三維空間里，令w3=0，則為二維權(quán)空間。如圖：給定一個模式X，就決定一條直線：即分界面H，W與H正交，W稱為解向量。解向量的變動范圍稱為解區(qū)。因x1,x2∈ω1，x3,x4∈ω2由圖可見x1,x3離的最近，所以分界面H可以是x1,x3之間的任一直線，由垂直于這些直線的W就構(gòu)成解區(qū)，解區(qū)為一扇形平面，即陰影區(qū)域。如右圖:二、解向量和解區(qū)分界面H把不等式方程正規(guī)化：正規(guī)化：H分界面樣本的正規(guī)化，令：由此可見，可以不管樣本原來的類別標識，只要找到一個對全部樣本都滿足的權(quán)向量即可，叫做正規(guī)化增廣樣本向量。g(x)=WTX=0決定一個決策界面，當g(x)為線性時，該決策界面是一超平面H，有以下性質(zhì)：性質(zhì)①：W與H正交（如圖所示）假設(shè)x1,x2是H上的兩個向量所以W與(x1-x2)

垂直，即W與H正交。

三、超平面的幾何性質(zhì)Ω1Ω2g(x)>0g(x)<0說明：一般說，超平面H把特征空間分成兩個半空間。即Ω1,Ω2空間，當x在Ω1空間時g(x)>0,W指向Ω1，為H的正側(cè)，反之為H的負側(cè)。

矢量到H的正交投影與值成正比其中：xp是x在H

的投影向量，r是x

到H

的垂直向量。是W方向的單位向量。性質(zhì)②：另一方面:這是超平面的第二個性質(zhì)：矢量x到超平面的正交投影正比與g(x)的函數(shù)值。性質(zhì)③：性質(zhì)④：

§2.4線性分類器的設(shè)計

上面我們討論的線性判別函數(shù)形式為：g(x)=WTX

其中：X=(X1,X2…Xn)n維特征向量

W=(W1,W2…

Wn,Wn+1)n維權(quán)向量

通常通過特征抽取可以獲得n維特征向量，而n維權(quán)向量是要按某種準則（準則函數(shù)）求解的。求解權(quán)向量的過程就是分類器的訓練過程，使用已知類別的有限學習樣本來獲得分類器的權(quán)向量被稱為有監(jiān)督的分類。設(shè)計線性分類器的主要步驟：(1)收集一組具有類別標識的樣本。若把每個樣本看成確定的觀測值，則這組樣本稱為確定性樣本集；若把每個樣本看成隨機變量，則這組樣本稱為隨機樣本集。(2)根據(jù)實際情況確定一個準則函數(shù)J。J必須滿足：a)J是樣本集X和、的函數(shù)；b)J的值反映分類器的性能，其極值解對應于“最好”的決策。(3)用最優(yōu)化技術(shù)求出準則函數(shù)的極值解，。權(quán)向量的訓練過程：利用已知類別學習樣本來獲得權(quán)向量的訓練過程如下：已知x1∈ω1,通過檢測調(diào)整權(quán)向量，最終使x1∈ω1已知x2∈ω2,通過檢測調(diào)整權(quán)向量，最終使x2∈ω2這樣就可以通過有限的樣本去決定權(quán)向量。>0x∈ω1

<0x∈ω2

x1x2…….xn1

w1

w2

wn

wn+1∑

測試統(tǒng)計與訓練準則

W1X1

W2X2

WnXn

Wn+1g(x)=wTx

已知類別利用方程組來求解權(quán)向量對二類判別函數(shù)g(x)=w1x1+w2x2+w3已知訓練集：Xa,Xb,Xc,Xd且當(Xa,Xb)∈W1時

g(x)＞0

當(Xc,Xd)∈W2時

g(x)＜0設(shè)Xa=(X1a,X2a)TXb=(X1b,X2b)TXc=(X1c,X2c)TXd=(X1d,X2d)T判別函數(shù)可聯(lián)立成：

x1aw1+x2aw2+w3＞0①

x1bw1+x2bw2+w3＞0②

x1cw1+x2cw2+w3＜0③

x1dw1+x2dw2+w3＜0④

求出w1,w2,w3

將③④式正規(guī)化，得

-X1cW1-X2cW2-W3>0-X1dW1-X2dW2-W3>0所以g(x)=WTX>0

其中W=(W1,W2,W3)T

為各模式增1矩陣

為N*(n+1）矩陣N為樣本數(shù)，n為特征數(shù)啟迪：認知小樣本和高維特征空間的矛盾

由此可見：訓練過程就是對已知類別的樣本集求解權(quán)向量Ｗ，這是一個線性聯(lián)立不等式方程組求解的過程。求解時：①只有對線性可分的問題，g(x)=WTX才有解②聯(lián)立方程的解是非單值，在不同條件下，有不同的解，所以就產(chǎn)生了求最優(yōu)解的問題③求解W的過程就是訓練的過程。訓練方法的共同點是：先給出準則函數(shù)，再尋找使準則函數(shù)趨于極值的優(yōu)化算法。不同的算法有不同的準則函數(shù)。同時，算法可以分為迭代法和非迭代法。

一、梯度下降法—迭代法基本思路：欲對不等式方程組WTX>0求解，首先定義準則函數(shù)(目標函數(shù))J(W)，再求J(W)的極值使W優(yōu)化。因此，求解權(quán)向量的問題就轉(zhuǎn)化為對一標量函數(shù)求極值的問題。解決此類問題的方法是梯度下降法。基本方法：就是從起始值W1開始，算出W1處目標函數(shù)的梯度矢量▽J(W1)，則下一步的W2值為：

W2=W1-ρ1▽J(W1)W1為起始權(quán)向量，ρ1為迭代步長J(W)為目標函數(shù)▽J(W1)為W1處的目標函數(shù)的梯度矢量在第K步的時候：

Wk+1=Wk-ρk▽J(Wk)這就是梯度下降法的迭代公式。這樣一步步迭代就可以收斂于解矢量，步長ρk取值很重要。關(guān)于步長ρk討論：(1)ρk太大，迭代太快，引起振蕩，甚至發(fā)散;(2)ρk太小，迭代太慢。結(jié)論：應該選最佳ρk。選最佳ρk：目標函數(shù)J(W)二階Taylor級數(shù)展開式為J(W)≈J(Wk)+▽JT(W-Wk)+(W-Wk)TD(W-Wk)T/2①其中D為當W=Wk時J(W)的二階偏導數(shù)矩陣

將W=Wk+1=Wk-ρk▽J(Wk)代入①式得：

J(Wk+1)≈J(Wk)-ρk||▽J||2+ρk2▽JTD▽J

其中▽J=▽J(Wk)

對ρk求導數(shù)，并令導數(shù)為零，則最佳步長為

ρk=||▽J||2/▽JTD▽J稱為Hessian矩陣若令W=Wk+1上式為J(Wk+1)=J(Wk)+▽JT(Wk+1-Wk)+(Wk+1-Wk)TD(Wk+1-Wk)T/2對Wk+1求導，并令導數(shù)為零可得：最佳迭代公式：Wk+1=Wk-D-1▽J—牛頓法的迭代公式

D-1是D的逆陣討論：牛頓法比梯度法收斂的更快，但是D的計算量大并且要計算D-1。當D為奇異時，無法用牛頓法。二、感知器法感知器的原理結(jié)構(gòu)為：“感知器”是借于上世紀五六十年代人們對一種分類學習機模型的稱呼，源于對生物智能的仿生學領(lǐng)域?；舅悸罚和ㄟ^對W的調(diào)整，可實現(xiàn)判別函數(shù)：

g(x)=WTX>RT其中RT為響應閾值定義感知準則函數(shù)準則：只考慮錯分樣本定義：，其中X0為錯分樣本當分類發(fā)生錯誤時就有WTX<0，或－WTX>0,所以J(W)總是正值，錯誤分類愈少，J(W)就愈小。理想情況為，即求最小值的問題。求最小值，對W求梯度代入迭代公式中Wk+1=Wk-ρk▽J

由J(W)經(jīng)第K+1次迭代時，J(W)趨于0，收斂于所求的W值。W的訓練過程：例如:x1,x2,x3∈ω1作

x1,x3的垂直線可得解區(qū)(如圖)

。假設(shè)起始權(quán)向量w1=0，步長ρk=1：1.x1,x2,x3三個矢量相加得矢量2,垂直于矢量2的超平面H將x3錯分；2.x3與矢量2相加得矢量3,垂直于矢量3的超平面H1,將x1錯分；3.依上法得矢量4,垂直于矢量4做超平面,H2將x3錯分；4.x3與矢量4相加得矢量5,矢量5在解區(qū)內(nèi),垂直于矢量5的超平面可以把x1,x2,x3分成一類。x1x2x32H3H14H25W區(qū)間如果樣本進行正則化處理，情況為何？感知器算法：

1.錯誤分類修正wk

如wkTx≤0并且x∈ω1wk+1=wk+ρkx

如wkTx≥0并且x∈ω2

wk+1=wk-ρkx2.正確分類

，wk不修正如wkTx＞0并且x∈ω1

如wkTx＜0并且x∈ω2

wk+1=wk

+-Hwk+1ρkxwk權(quán)值修正過程賞罰概念：感知器算法顯然是一種賞罰過程。對正確分類的模式則“賞”（此處用“不罰”，即權(quán)向量W不變）；對錯誤分類的模式則“罰”，使W加上一個正比于錯誤模式樣本X的分量。ρk選擇準則：①

固定增量原則ρk固定非負數(shù)

②

絕對修正規(guī)則ρk>

③部分修正規(guī)則ρk=λ0＜λ≤2例題：有兩類樣本：ω1=（x1,x2）={(1,0,1),(0,1,1)}，ω2=（x3,x4）={(1,1,0),(0,1,0)}

解：先求四個樣本的增值模式

x1=(1,0,1,1)x2=(0,1,1,1)x3=(1,1,0,1)x4=(0,1,0,1)

假設(shè)初始權(quán)向量w1=(1,1,1,1)ρk=1

第一次迭代：

w1Tx1=(1,1,1,1)(1,0,1,1)T=3>0所以不修正

w1Tx2=(1,1,1,1)(0,1,1,1)T=3>0所以不修正

w1Tx3=(1,1,1,1)(1,1,0,1)T=3>0所以修正w1w2=w1-x3=(0,0,1,0)w2Tx4=(0,0,1,0)T(0,1,0,1)=0所以修正w2w3=w2-x4=(0,-1,1,-1)

第一次迭代后,權(quán)向量w3=(0,-1,1,-1),再進行第2,3,…次迭代，如下表：

直到在一個迭代過程中權(quán)向量相同，訓練結(jié)束。

w6=w=(0,1,3,0)，判別函數(shù)g(x)=-x2+3x3感知器算法只對線性可分樣本有收斂的解,對非線性可分樣本集會造成訓練過程的振蕩,這是它的缺點。

訓練樣本wkTx修正式修正后的權(quán)值wk＋1迭代次數(shù)x11011x20111x31101x40101+++0w1w1w1-x3w2-x41111111100100–11-1

1x11011x20111x31101x401010+0-w3+x1w4w4-x3w51–1201–1200–22–10–22-1

2x11011x20111x31101x40101+---w5w5+x2w6w60–22–10–1300–1300–130

3x11011x20111x31101x40101++--w6w6w6w60–1300–1300–1300–130

4三、最小平方誤差準則-非迭代法

前面我們討論的線性分類器訓練方法，其共同點是企圖找一個權(quán)向量W，使錯分樣本最小?，F(xiàn)在我們把不等式組變成如下形式：WTXi=bi>0

則有聯(lián)立方程XW=b這是矛盾方程組，方程數(shù)大于未知數(shù)，所以沒有精確解的存在。每個樣本有n個特征定義誤差向量：e=XW-b≠0把平方誤差作為目標函數(shù)

W的優(yōu)化就是使J(W)最小。于是，求J(W)的梯度并令其為0，即解上方程得XTXW=XTb這樣把求解XW=b的問題，轉(zhuǎn)化為對XTXW=XTb求解，這樣最大好處是：因XTX是方陣且通常是非奇異的，所以可以得到W的唯一解。

MSE準則函數(shù)

選取合適的b，只要計算出X+就可以得到W。若取b：

此時，最小平方誤差法同F(xiàn)isher法是一致（見邊肇祺書102頁）。（MSE解）其中N/N1有N1個，N/N2有N2個四、Fisher分類準則

現(xiàn)在討論通過映射投影來降低維數(shù)的方法。

X空間

映射Y空間：把X空間各點投影到Y(jié)空間的一直線上，維數(shù)由2