第4章線性分類器

第四章線性分類器

計(jì)算機(jī)與通信工程學(xué)院計(jì)算機(jī)與通信工程學(xué)院模式識(shí)別假設(shè)對(duì)一模式X已抽取n個(gè)特征，表示為：模式識(shí)別問題就是根據(jù)模式X的n個(gè)特征來判別模式屬于ω1,ω2,

…,

ωm類中的那一類。例如右上圖：三類的分類問題，它們的邊界線就是一個(gè)判別函數(shù)4.1判別函數(shù)用判別函數(shù)進(jìn)行模式分類，取決兩個(gè)因素：判別函數(shù)的幾何性質(zhì)：線性與非線性判別函數(shù)的參數(shù)確定：判別函數(shù)形式+參數(shù)判別函數(shù)包含兩類：一類是線性判別函數(shù)：線性判別函數(shù)：線性判別函數(shù)是統(tǒng)計(jì)模式識(shí)別的基本方法之一，簡(jiǎn)單且容易實(shí)現(xiàn)廣義線性判別函數(shù)所謂廣義線性判別函數(shù)就是把非線性判別函數(shù)映射到另外一個(gè)空間（高維）變成線性判別函數(shù)分段線性判別函數(shù)另一類是非線性判別函數(shù)我們現(xiàn)在對(duì)兩類問題和多類問題分別進(jìn)行討論。一、兩類問題：即:

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

(x)

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

另外一種表示方法：模式分類：當(dāng)g(x)=WTX=0為判別邊界。當(dāng)n=2時(shí)，二維情況的判別邊界為一直線。當(dāng)n=3時(shí)，判別邊界為一平面。當(dāng)n>3時(shí)，則判別邊界為一超平面。

1.第一種情況：每一模式類與其它模式類間可用單個(gè)判別平面把一個(gè)類分開。這種情況，M類可有M個(gè)判別函數(shù)，且具有以下性質(zhì)：二、對(duì)于多類問題：模式有ω1,ω2,…,ωm

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

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

，g3(x)<0

。ω1

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

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

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

和直線-x1+x2=0的負(fù)邊來確定。必須指出，如果某個(gè)X使二個(gè)以上的判別函數(shù)gi(x)>0。則此模式X就無法作出確切的判決。如圖中

IR1,IR3，IR4區(qū)域。另一種情況是IR2區(qū)域，判別函數(shù)都為負(fù)值。IR1，IR2，IR3，IR4。都為不確定區(qū)域。問當(dāng)x=(x1,x2)T=(6,5)T時(shí)屬于那一類結(jié)論：

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

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

和g1(x)>g3(x)

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

，則x屬于那一類。把它代入判別函數(shù)：得判別函數(shù)為：因?yàn)樗阅Ｊ絰=(1,1)T屬于類。關(guān)于線性判別函數(shù)的結(jié)論模式類別若可用任一線性判別函數(shù)來劃分，這些模式就稱為線性可分；一旦線性判別函數(shù)的參數(shù)確定，這些函數(shù)即可作為模式分類的基礎(chǔ)。對(duì)于M（M≥2）類模式分類，第一、三種情況需要M個(gè)判別函數(shù)，第二種情況需要M(M-1)/2個(gè)判別函數(shù)。對(duì)于第一種情況，每個(gè)判別函數(shù)都要把一種類別（比如i類）的模式與其余M-1種類別的模式劃分開，而不是僅將一類與另一類劃分開。實(shí)際上，一個(gè)類的模式分布要比M-1類模式分布更聚集，因此后兩種情況實(shí)現(xiàn)模式線性可分的可能性要更大一些。4.3線性判別函數(shù)的性質(zhì)一、模式空間與加權(quán)空間：模式空間：由構(gòu)成的n維歐氏空間。W是此空間的加權(quán)向量，它決定模式的分界面H，W與H正交。加權(quán)空間：以為變量構(gòu)成的歐氏空間模式空間與加權(quán)空間的幾何表示如下圖：2023/2/6在三維空間里，令w3=0，則為二維權(quán)空間。如圖：給定一個(gè)模式X，就決定一條直線：即分界面H，W與H正交，W稱為解向量。解向量的變動(dòng)范圍稱為解區(qū)。因x1,x2∈ω1，x3,x4∈ω2由圖可見x1,x3離的最近，所以分界面H可以是x1,x3之間的任一直線，由垂直于這些直線的W就構(gòu)成解區(qū)，解區(qū)為一扇形平面，即陰影區(qū)域。如右圖:二、解向量和解區(qū)分解面H把不等式方程正規(guī)化：正規(guī)化：H分界面樣本的正規(guī)化，令：由此可見，可以不管樣本原來的類別標(biāo)識(shí)，只要找到一個(gè)對(duì)全部樣本都滿足的權(quán)向量即可，叫做正規(guī)化增廣樣本向量。g(x)=WTX=0決定一個(gè)決策界面，當(dāng)g(x)為線性時(shí)，該決策界面便是一個(gè)超平面H，并有以下性質(zhì)：性質(zhì)①：W與H正交（如圖所示）假設(shè)x1,x2是H上的兩個(gè)向量所以W與(x1-x2)

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

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

的投影向量，r是x

到H

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

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

其中

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

W=(W1,W2…

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

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

已知x1∈ω1,通過檢測(cè)調(diào)整權(quán)向量，最終使x1∈ω1已知x2∈ω2,通過檢測(cè)調(diào)整權(quán)向量，最終使x2∈ω2這樣就可以通過有限的樣本去決定權(quán)向量。>0x∈ω1

<0x∈ω2

x1x2…….xn1

w1

w2

wn

wn+1∑

測(cè)試統(tǒng)計(jì)與訓(xùn)練準(zhǔn)則

W1X1

W2X2

WnXn

Wn+1g(x)=wTx

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

g(x)＞0

當(dāng)(Xc,Xd)∈W2時(shí)

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ù)啟迪：認(rèn)知小樣本和高維特征空間的矛盾

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

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

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

Wk+1=Wk-ρk▽J(Wk)這就是梯度下降法的迭代公式。這樣一步步迭代就可以收斂于解矢量，步長(zhǎng)ρk取值很重要。關(guān)于步長(zhǎng)ρk討論：(1)ρk太大，迭代太快，引起振蕩，甚至發(fā)散;(2)ρk太小，迭代太慢。結(jié)論：應(yīng)該選最佳ρk。最優(yōu)化理論二、感知器法感知器的原理結(jié)構(gòu)為：“感知器”是借于上世紀(jì)五六十年代人們對(duì)一種分類學(xué)習(xí)機(jī)模型的稱呼，源于對(duì)生物智能的仿生學(xué)領(lǐng)域?；舅悸罚和ㄟ^對(duì)W的調(diào)整，可實(shí)現(xiàn)判別函數(shù)：

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

由J(W)經(jīng)第K+1次迭代時(shí)，J(W)趨于0，收斂于所求的W值。

感知器算法：

1.錯(cuò)誤分類修正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)值修正示意圖例題：有兩類樣本：ω1=（x1,x2）={(1,0,1),(0,1,1)}，ω2=（x3,x4）={(1,1,0),(0,1,0)}解：先求四個(gè)樣本的增廣向量

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),再進(jìn)行第2,3,…次迭代，如下表：

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

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

訓(xùn)練樣本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三、最小平方誤差準(zhǔn)則

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

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

W的優(yōu)化就是使J(W)最小。于是，求J(W)的梯度并令其為0，即解上方程得XTXW=XT