模式識別分類器的設計第一頁，共四十八頁，編輯于2023年，星期六

§3-1線性分類器的設計

上一章我們討論了線性判別函數(shù)形式為:g(x)=WTX

其中

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

W=(W1,W2…

Wn,Wn+1)n維權向量

通常通過特征抽取可以獲得n維特征向量，因此n維權向量是要求解的。求解權向量的過程就是分類器的訓練過程，使用已知類別的有限的學習樣本來獲得分類器的權向量被稱為有監(jiān)督的分類。第二頁，共四十八頁，編輯于2023年，星期六利用已知類別學習樣本來獲得權向量的訓練過程如下已知x1∈ω1,通過檢測調整權向量，最終使x1∈ω1已知x2∈ω2,通過檢測調整權向量，最終使x2∈ω2這樣就可以通過有限的樣本去決定權向量

x1

x2…….

xn

1

w1

w2

wn

wn+1∑

>0x∈ω1

檢測(已知類別)

W1X1

W2X2

WnXn

Wn+1<0x∈ω2g(x)=wTx

第三頁，共四十八頁，編輯于2023年，星期六利用方程組來求解權向量對二類判別函數(shù)g(x)=W1X1+W2X2+W3已知訓練集：Xa,Xb,Xc,Xd且當(Xa,Xb)∈W1時

g(x)＞0

當(Xc,Xd)∈W2時

g(x)＜0設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

第四頁，共四十八頁，編輯于2023年，星期六將③④式正規(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ù)第五頁，共四十八頁，編輯于2023年，星期六訓練過程就是對已知類別的樣本集求解權向量w，這是一個線性聯(lián)立不等式方程組求解的過程。求解時：①

只有對線性可分的問題，g(x)=WTX才有解②

聯(lián)立方程的解是非單值，在不同條件下，有不同的解，所以就產(chǎn)生了求最優(yōu)解的問題③求解W的過程就是訓練的過程。訓練方法的共同點是，先給出準則函數(shù)，再尋找使準則函數(shù)趨于極值的優(yōu)化算法，不同的算法有不同的準則函數(shù)。算法可以分為迭代法和非迭代法。

第六頁，共四十八頁，編輯于2023年，星期六一梯度下降法—迭代法欲對不等式方程組WTX>0求解，首先定義準則函數(shù)(目標函數(shù))J(W)，再求J(W)的極值使W優(yōu)化。因此求解權向量的問題就轉化為對一標量函數(shù)求極值的問題。解決此類問題的方法是梯度下降法。方法就是從起始值W1開始，算出W1處目標函數(shù)的梯度矢量▽J(W1)，則下一步的w值為：W2=W1-ρ1▽J(W1)W1為起始權向量ρ1為迭代步長J(W1)為目標函數(shù)▽J(W1)為W1處的目標函數(shù)的梯度矢量第七頁，共四十八頁，編輯于2023年，星期六在第K步的時候Wk+1=Wk-ρk▽J(Wk)ρk為正比例因子這就是梯度下降法的迭代公式。這樣一步步迭代就可以收斂于解矢量，ρk取值很重要

ρk太大，迭代太快，引起振蕩，甚至發(fā)散。

ρk太小，迭代太慢。應該選最佳ρk。第八頁，共四十八頁，編輯于2023年，星期六選最佳ρk

目標函數(shù)J(W)二階臺勞級數(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這就是最佳ρk的計算公式，但因二階偏導數(shù)矩陣D的計算量太大，因此此公式很少用。

第九頁，共四十八頁，編輯于2023年，星期六若令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為奇異時，無法用牛頓法。第十頁，共四十八頁，編輯于2023年，星期六二感知器法感知器的原理結構為：第十一頁，共四十八頁，編輯于2023年，星期六通過對W的調整，可實現(xiàn)判別函數(shù)g(x)=WTX>RT

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

由J(W)經(jīng)第K+1次迭代的時候，J(W)趨于0，收斂于所求的W值第十三頁，共四十八頁，編輯于2023年，星期六+感知器算法：

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權值修正過程第十四頁，共四十八頁，編輯于2023年，星期六ρk選擇準則

①

固定增量原則

ρk固定非負數(shù)

②

絕對修正規(guī)則

ρk>

③

部分修正規(guī)則

ρk=λ0＜λ≤2第十五頁，共四十八頁，編輯于2023年，星期六例題：有兩類樣本

ω1=（x1,x2）={(1,0,1),(0,1,1)}ω2=（x3,x4）={(1,1,0),(0,1,0)}解：先求四個樣本的增1模式

x1=(1,0,1,1)x2=(0,1,1,1)x3=(1,1,0,1)x4=(0,1,0,1)假設初始權向量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)第一次迭代后,權向量w3=(0,-1,1,-1),再進行第2,3,…次迭代如下表第十六頁，共四十八頁，編輯于2023年，星期六直到在一個迭代過程中權向量相同，訓練結束。w6=w=(0,1,3,0)判別函數(shù)g(x)=-x2+3x3感知器算法只對線性可分樣本有收斂的解,對非線性可分樣本集會造成訓練過程的振蕩,這是它的缺點.

訓練樣本wkTx修正式修正后的權值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第十七頁，共四十八頁，編輯于2023年，星期六線性不可分樣本集的分類解(取近似解)

對于線性可分的樣本集，可以用上述方法解到正確分類的權向量。當樣本集線性不可分時，用上述方法求權值時算法不收斂。如果我們把循環(huán)的權向量取平均值作為待求的權向量，或就取其中之一為權向量，一般可以解到較滿意的近似結果。例：在樣本ω1:

X1=（0,2）X3=（2,0）

X5=（-1,-1）ω2:

X2=（1,1）X4=（0,-2）

X6=（-2,0）求權向量的近似解x2x1x6x1x3－2x5－2x4x211H第十八頁，共四十八頁，編輯于2023年，星期六解：此為線性不可分問題，利用感知器法求權向量權向量產(chǎn)生循環(huán)(-1,2,0),(0,2,2),(-1,1,1),(-1,1,1)(-1,1,1),(0,0,0),(-1,2,0)因此算法不收斂，我們可以取循環(huán)中任一權值，例如取W=(0,2,2)T則判別函數(shù)為：g(x)=2x1+2x2判別面方程為：g(x)=2x1+2x2＝0所以x1+x2＝0由圖看出判別面H把二類分開，但其中x2錯分到ω1類，而x1錯分到ω2類，但大部分分類還是正確的。第十九頁，共四十八頁，編輯于2023年，星期六作業(yè)：已知四個訓練樣本

w1={(0,0),(0,1)}w2={(1,0),(1,1)}

使用感知器固定增量法求判別函數(shù)設w1=(1,1,1,1)ρk=1

要求編寫程序上機運行，寫出判別函數(shù)，并打出圖表。第二十頁，共四十八頁，編輯于2023年，星期六三最小平方誤差準則(MSE法)---非迭代法

前面我們研究了線性不等式方程組g(x)=WTX>0的解法。它們共同點是企圖找一個權向量W，使錯分樣本最小?，F(xiàn)在我們把不等式組變成如下形式：WTXi=bi>0

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

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

MSE準則函數(shù)第二十二頁，共四十八頁，編輯于2023年，星期六只要計算出X+就可以得到W?。?/p>

最小平方誤差法同F(xiàn)isher法是一致的。（MSE解）其中N/N1有N1個，N/N2有N2個第二十三頁，共四十八頁，編輯于2023年，星期六

四韋—霍氏法（LMS法）迭代法上節(jié)得到MSE法的W解為：W=X+b在計算X+時，

1．

要求XTX矩陣為非奇異

2．

由于計算量太大而引入比較大誤差所以要用迭代法來求求J(W)的梯度▽J(W)=2XT(XW-b)代入迭代公式W1任意設定

Wk+1=Wk-ρkXT(XWk-b)

此法可收斂于W值。W滿足:XT(XW-b)=0計算量很大第二十四頁，共四十八頁，編輯于2023年，星期六因此下降算法不論XTX是否奇異，總能產(chǎn)生一個解。若訓練樣本無限的重復出現(xiàn)，則簡化為

W1任意

Wk+1=Wk+ρk(bk-WkTXk)Xk

ρk隨迭代次數(shù)k而減少，以保證算法收斂于滿意的W值第二十五頁，共四十八頁，編輯于2023年，星期六五何—卡氏法

（判斷迭代過程中是否線性可分）

若訓練樣本線性可分時，感知器法可求出界面，但對不可分問題不收斂只能取平均。最小平方誤差法不論樣本是否線性可分都能給出一加權矢量，但不能保證此矢量就是分界矢量，下面介紹一種方法可以檢測迭代過程中是否線性可分。因最小平方誤差法的J(W)的解為因為XW=bb應為正值c為矯正系數(shù)當（XWk-bk）≤0時

當（XWk-bk）＞

0時第二十六頁，共四十八頁，編輯于2023年，星期六引入誤差矢量ekek=XWk-bk判斷是否線性可分所以J(W)的解為初始條件

W1=X+b1并且b1>0迭代時檢測如果ek≥0時，XW

>b，系統(tǒng)線性可分，迭代收斂如果ek<0時，XW

<b，系統(tǒng)線性不可分，迭代不收斂我們用下面的例子來說明ek的作用因此上式可以寫成第二十七頁，共四十八頁，編輯于2023年，星期六例題：

ω1={(0,0)T,(0,1)T}ω2={(1,0)T,(1,1)T}解：正規(guī)化對ω2取負，有

X的規(guī)范矩陣為x2x1x1x2x3x4第二十八頁，共四十八頁，編輯于2023年，星期六取b1=(1,1,1,1)Tc=1W1=X+b1=(-2,0,1)T

所以W1為所求解e1=XW1-b1=0系統(tǒng)線性可分因為第二十九頁，共四十八頁，編輯于2023年，星期六若四個樣本變成：ω1={(0,0)T,(1,1)T}ω2={(0,1)T,(1,0)T}解：

取b1=(1,1,1,1)Tc=1W1=X+b1=(0,0,0)Te1=XW1-b1=(-1,-1,-1,-1)T<0

系統(tǒng)線性不可分

C為校正系數(shù),取0＜C≤1在算法進行過程中，應在每一次迭代時，檢測ek的值。只要出現(xiàn)ek<0，迭代就應立即停止。

x2x1

1

1第三十頁，共四十八頁，編輯于2023年，星期六六Fisher分類準則

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

X空間

X=-WTX-W0>0X∈ω1

X=-WTX-W0<0X∈ω2

映射Y空間

Y=WTX-W0>0X∈ω1

Y=WTX-W0<0X∈ω2把X空間各點投影到Y空間得一直線上，維數(shù)由2維降為一維。若適當選擇W的方向，可以使二類分開。下面我們從數(shù)學上尋找最好的投影方向，即尋找最好的變換向量W的問題。w(y)wy1y2x2x1ω1ω2第三十一頁，共四十八頁，編輯于2023年，星期六

投影樣本之間的分離性用投影樣本之差表示

投影樣本類內(nèi)離散度:

i=1,2i=1,2第三十二頁，共四十八頁，編輯于2023年，星期六

類間散布矩陣第三十三頁，共四十八頁，編輯于2023年，星期六上式就是n維x空間向一維y空間的最好投影方向，它實際是多維空間向一維空間的一種映射。其中Sw為類內(nèi)散布矩陣,Sb為類間散布矩陣第三十四頁，共四十八頁，編輯于2023年，星期六現(xiàn)在我們已把一個n維的問題轉化為一維的問題。現(xiàn)在一維空間設計Fisher分類器:W0的選擇

第三十五頁，共四十八頁，編輯于2023年，星期六

Yki表示第i類中第k個樣本的投影值

N1為ω1樣本數(shù)

N2為ω2樣本數(shù)

當W0選定后，對任一樣本X，只要判斷Y=WTX>0則X∈ω1;Y=WTX<0則X∈ω2。分類問題就解決了第三十六頁，共四十八頁，編輯于2023年，星期六

§3-2分段線形分類器的設計先求子類的權向量Wil，再求總的權向量Wi

1.

已知子類劃分時的設計方法把每一個子類作為獨立類，利用每個子類的訓練樣本，求每個子類的線性判別函數(shù)，總的判別函數(shù)就可獲得。

子類的劃分可用以下方法：①

用先驗知識直接劃分②

用聚類分析，聚成多個子類

2.

已知子類的數(shù)目的設計方法①

設各個子類的初始權向量：Wi1,Wi2…Wili

i=1,2,…MWi中有Li個子類②

若第K步迭代時ωj

類樣本Xj同ωj類某個子類的權向量Wj

n(k)的內(nèi)積值最大，即Wj

n(k)lxj=

max{Wj

n(k)lxj}n=1,2,…lj第三十七頁，共四十八頁，編輯于2023年，星期六

并且滿足條件Wjn(k)xj>Win(k)lxji=1,2,…M類

j=1,2,…li子類i≠j

則權向量Wi1(k)，Wi2(k)，…,Wili

(k)不影響分類，

所以權向量不需要修正。若有某個或某幾個子類不滿足條件即：存在Win(k)使Wjn(k)xj

≤Win(k)lxji≠j所以xj錯分類，要修改權向量。

設Win(k)lxj=

max{Win(k)lxj}n=1,2,…lii≠j則修改權向量Wjn(k+1)=Wjn(k)±ρkxj③

重復以上迭代,直到收斂,此法類似于固定增量法.第三十八頁，共四十八頁，編輯于2023年，星期六

3.未知子類數(shù)目時的設計方法當每類應分成的子類數(shù)也不知時，這是最一般情況，方法很多，舉例如下。樹狀分段線性分類器:

設兩類情況ω1，ω2。如圖所示①

先用兩類線性判別函數(shù)求出W1,超平面H1分成兩個區(qū)間,每個區(qū)間包含兩類。②再利用二類分類求出W2(H2),W3(H3)。③

如果每個部分仍包含兩類,

繼續(xù)上面的過程。第三十九頁，共四十八頁，編輯于2023年，星期六關鍵是初始權向量W1的選擇:一般先選兩類中距離最近的兩個子類的均值連線做垂直線作為H1(w1)初始值再求最優(yōu)解。w1Tx>0w4Tx≥0w3Tx≥0w2Tx≥0YNYYNNω1

ω1

ω2ω2

NYω1

樹狀決策框圖第四十頁，共四十八頁，編輯于2023年，星期六§3-3非線性分類器的設計電位函數(shù)分類器,用非線性判別函數(shù)區(qū)分線性不可分的類別電位函數(shù)分類器:每個特征作為一個點電荷,把特征空間作為能量場.電位分布函數(shù)有下面三種形式。

α為系數(shù)xk為某一特定點上圖是這些函數(shù)在一維時的圖形，第三條是振蕩曲線，只有第一周期才是可用范圍。xK(x)x321第四十一頁，共四十八頁，編輯于2023年，星期六電位函數(shù)算法的訓練過程是在逐個樣本輸入時，逐漸積累電位的過程，對于二類問題，經(jīng)過若干循環(huán)后，如積累電位方程的運算結果能以正、負來區(qū)分二類樣本，則訓練就可結束。算法:

設初始電位為K0(x)=01.輸入樣本x1計算積累電位K1(x)

若x∈ω1K1(x)=K0(x)+K(xx1)

若x∈ω2K1(x)=K0(x)-K(xx1)

設ω1為正電荷,ω2為負電荷在K0(x)=0時

若x1∈ω1K1(x)=K(xx1)

若x1∈ω2K1(x)=-K(xx1)

第四十二頁，共四十八頁，編輯于2023年，星期六2.輸入樣本x2計算積累電荷有以下幾種情況

a.若x2∈ω1并且K1(x2)>0

若x2∈ω2并且K1(x2)<0K1(x)=K2(x)不修正

b.若x2∈ω1并且K1(x2)≤0

若x2∈ω2并且K1(x2)≥0K2(x)=K1(x)±K(xx2)=±K1(xx1)±K(xx2)修正直到第k+1步,已輸入x1,x2,….xk個樣本

第四十三頁，共四十八頁，編輯于2023年，星期六積累電荷Kk+1(x)有三種情況:1.若xk+1∈ω1并且Kk(xk+1)>0或xk+1∈ω2并且Kk(xk+1)<0

則Kk+1(x)=Kk(x)不修正2.若xk+1∈ω1并且Kk(xk+1)≤0

則Kk+1(x)=Kk(x)+K(xxk)3.若xk+1∈ω2并且Kk(xk+1)≥0

則Kk+1(x)=Kk(x)-K(xxk)綜合式：Kk+1(x)=Kk(x)+rk+1K(x,xk)

其中：xk+1∈ω1并且Kk(xk+1)>0時rk+1=0xk+1∈ω1并且Kk(xk+1)≤0時rk+1=1xk+1∈ω2并且Kk(xk+1)<0時rk+1=0xk+1∈ω2并且Kk(xk+1)≥0時rk+1=-1第四十四頁，共四十八頁，編輯于2023年，星期六例題.設有兩類樣本ω1={(0,0)T,(2,0)T}ω2={(1,1)T,(1,-1)

T}如下圖線性不可分特征為二維的，所以電位函數(shù)為：K(xx2)=exp{-[(x1-xk1)2+(x2-xk2)2]}①輸入x1=(xk1,xk2)T=(0,0)Tx1∈ω1K1(x)=K1(xx1)=exp{-(x12+x22)}②輸入x2=(2,0)Tx2∈ω1代入

K1(x2)=exp{-(02+22)}>0不修正

K2(x)=K1(x)=exp{-(x12+x22)}③輸入x3=(1,1)Tx3∈ω2代入

K2(x3)=exp{-(12+12)}>0所以需要修正

K3(x)=K