模式識(shí)別導(dǎo)論(二)

§2-1判別函數(shù)§2-2線性判別函數(shù)§2-3線性判別函數(shù)的性質(zhì)§2-4廣義線性判別函數(shù)§2-5非線性判別函數(shù)第二章

判別函數(shù)2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*假設(shè)對(duì)一模式X已抽取n個(gè)特征，表示為：模式識(shí)別問(wèn)題就是根據(jù)模式X的n個(gè)特征來(lái)判別模式屬于ω1,ω2,

…,

ωm

類(lèi)中的那一類(lèi)?！?-1判別函數(shù)

2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*例如下圖：三類(lèi)的分類(lèi)問(wèn)題，它們的邊界線就是一個(gè)判別函數(shù)§2.1判別函數(shù)（續(xù))2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*判別函數(shù)包含兩類(lèi)：一類(lèi)是線性判別函數(shù)：線性判別函數(shù)廣義線性判別函數(shù)所謂廣義線性判別函數(shù)就是把非線性判別函數(shù)映射到另外一個(gè)空間變成線性判別函數(shù)分段線性判別函數(shù)另一類(lèi)是非線性判別函數(shù)§2.1判別函數(shù)（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*§2-2線性判別函數(shù)我們現(xiàn)在對(duì)兩類(lèi)問(wèn)題和多類(lèi)問(wèn)題分別進(jìn)行討論。(一)兩類(lèi)問(wèn)題即:

1.二維情況：取兩個(gè)特征向量這種情況下判別函數(shù):2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*在兩類(lèi)別情況，判別函數(shù)g

(x)

具有以下性質(zhì)：這是二維情況下判別由判別邊界分類(lèi).情況如圖：1.二維情況2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*2.n維情況現(xiàn)抽取n個(gè)特征為：判別函數(shù)：

另外一種表示方法：2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*模式分類(lèi)：當(dāng)g1(x)=WTX=0為判別邊界。當(dāng)n=2時(shí)，二維情況的判別邊界為一直線。當(dāng)n=3時(shí)，判別邊界為一平面，n>3時(shí)，則判別邊界為一超平面。2.n維情況2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*(二)

多類(lèi)問(wèn)題對(duì)于多類(lèi)問(wèn)題，模式有ω1,ω2,

…,

ωm

個(gè)類(lèi)別。可分三種情況：1.第一種情況：每一模式類(lèi)與其它模式類(lèi)間可用單個(gè)判別平面把一個(gè)類(lèi)分開(kāi)。這種情況，M類(lèi)可有M個(gè)判別函數(shù)，且具有以下性質(zhì)：2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*右圖所示，每一類(lèi)別可用單個(gè)判別邊界與其它類(lèi)別相分開(kāi)。如果一模式X屬于ω1，則由圖可清楚看出:這時(shí)g1(x)>0而g2(x)<0

，g3(x)<0

。ω1

類(lèi)與其它類(lèi)之間的邊界由g1(x)=0確定.1.第一種情況2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*例：已知三類(lèi)ω1,ω2,ω3的判別函數(shù)分別為：因此三個(gè)判別邊界為：1.第一種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*作圖如下：1.第一種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*對(duì)于任一模式X如果它的g1(x)>0，g2(x)<0，g3(x)<0則該模式屬于ω1類(lèi)。相應(yīng)ω1類(lèi)的區(qū)域由直線-x2+1=0

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

和直線-x1+x2=0的負(fù)邊來(lái)確定。1.第一種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*必須指出，如果某個(gè)X使二個(gè)以上的判別函數(shù)gi(x)>0。則此模式X就無(wú)法作出確切的判決。如圖中

IR1,IR3，IR4區(qū)域。另一種情況是IR2區(qū)域，判別函數(shù)都為負(fù)值。IR1，IR2，IR3，IR4。都為不確定區(qū)域。1.第一種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*問(wèn)當(dāng)x=(x1,x2)T=(6,5)T時(shí)屬于那一類(lèi)結(jié)論：g1(x)<0，g2(x)>0，g3(x)<0所以它屬于ω2類(lèi)1.第一種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*這樣有M(M_1)/2個(gè)判別平面。對(duì)于兩類(lèi)問(wèn)題，M=2，則有一個(gè)判別平面。同理，三類(lèi)問(wèn)題則有三個(gè)判別平面。

判別函數(shù)：判別邊界：判別條件：2.第二種情況每個(gè)模式類(lèi)和其它模式類(lèi)間可分別用判別平面分開(kāi)。2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*判別函數(shù)性質(zhì)：假設(shè)判別函數(shù)為：判別邊界為：2.第二種情況（續(xù)）用方程式作圖：2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*問(wèn):未知模式X=(x1,x2)T=(4,3)T屬于那一類(lèi)代入判別函數(shù)可得:把下標(biāo)對(duì)換可得:因?yàn)榻Y(jié)論：所以X屬于ω3類(lèi)結(jié)論：判別區(qū)間增大，不確定區(qū)間減小，比第一種情況小的多.2.第二種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*3.第三種情況判別函數(shù)：

判別規(guī)則：判別邊界：gi(x)=gj(x)

或gi(x)-gj(x)

=0就是說(shuō)，要判別模式X屬于那一類(lèi)，先把X代入M個(gè)判別函數(shù)中，判別函數(shù)最大的那個(gè)類(lèi)別就是X所屬類(lèi)別。類(lèi)與類(lèi)之間的邊界可由gi(x)=gj(x)

或gi(x)-gj(x)

=0來(lái)確定。每類(lèi)都有一個(gè)判別函數(shù),存在M個(gè)判別函數(shù)2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*右圖所示是M=3的例子。對(duì)于ω1類(lèi)模式，必然滿(mǎn)足g1(x)>g2(x)

和g1(x)>g3(x)

。假設(shè)判別函數(shù)為：則判別邊界為：3.第三種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*結(jié)論：不確定區(qū)間沒(méi)有了，所以這種是最好情況。用上列方程組作圖如下：3.第三種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*問(wèn)假設(shè)未知模式x=(x1,x2)T=(1,1)T

，則x屬于那一類(lèi)。把它代入判別函數(shù)：得判別函數(shù)為：因?yàn)樗阅Ｊ絰=(1,1)T屬于類(lèi)。3.第三種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*§2-3線性判別函數(shù)的性質(zhì)1.模式空間與加權(quán)空間模式空間：由構(gòu)成的n維歐氏空間。W是此空間的加權(quán)向量，它決定模式的分界面H，W與H正交。加權(quán)空間：以為變量構(gòu)成的歐氏空間模式空間與加權(quán)空間的幾何表示如下圖：2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*模式空間2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*1.模式空間與加權(quán)空間（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*該式表示一個(gè)通過(guò)加權(quán)空間原點(diǎn)的平面，此平面就是加權(quán)空間圖中的平面①,同樣令g

(x2)=g

(x3)=g

(x4)=0，分別作出通過(guò)加權(quán)空間原點(diǎn)的平面②③④圖中用陰影表示的部分是各平面的正側(cè)。加權(quán)空間的構(gòu)造：設(shè)是加權(quán)空間分界面上的一點(diǎn)，代入上式得：1.模式空間與加權(quán)空間2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*這是一個(gè)不等式方程組，它的解處于由ω1類(lèi)所有模式?jīng)Q定的平面的正邊和由ω2類(lèi)所有模式?jīng)Q定的平面的負(fù)邊，它的解區(qū)即為凸多面錐。如圖所示：(b)為加權(quán)空間，（c）為正規(guī)化后的加權(quán)空間。由上可以得到結(jié)論：加權(quán)空間的所有分界面都通過(guò)坐標(biāo)原點(diǎn)。這是加權(quán)空間的性質(zhì)。為了更清楚，下面用二維權(quán)空間來(lái)表示解向量和解區(qū)。1.模式空間與加權(quán)空間（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*在三維空間里，令w3

=0

則為二維權(quán)空間。如圖：給定一個(gè)模式X，就決定一條直線：即分界面H，W與H正交，W稱(chēng)為解向量。解向量的變動(dòng)范圍稱(chēng)為解區(qū)。因x1,x2∈ω1，x3,x4∈ω2由圖可見(jiàn)x1,x3離的最近，所以分界面H可以是x1,x3之間的任一直線，由垂直于這些直線的W就構(gòu)成解區(qū)，解區(qū)為一扇形平面，即陰影區(qū)域。如右圖:2.解向量和解區(qū)2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*把不等式方程正規(guī)化：正規(guī)化：2.解向量的解區(qū)（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*g(x)=WTX=0決定一個(gè)決策界面，當(dāng)g(x)為線性時(shí)，這個(gè)決策界面便是一個(gè)超平面H，并有以下性質(zhì)：性質(zhì)①：W與H正交（如圖所示）假設(shè)x1,x2是H上的兩個(gè)向量所以W

與(x1-x2)

垂直，即W與H正交。一般說(shuō)，超平面H把特征空間分成兩個(gè)半空間。即Ω1,Ω2空間，當(dāng)x在Ω1空間時(shí)g(x)>0,W指向Ω1，為H的正側(cè)，反之為H的負(fù)側(cè).3.超平面的幾何性質(zhì)2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*Ω1Ω2g(x)>0g(x)<03.超平面的幾何性質(zhì)2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*矢量到H的正交投影與值成正比其中：x

p：x在H

的投影向量，r是x

到H

的垂直距離。是W方向的單位向量。3.超平面的幾何性質(zhì)（續(xù)）性質(zhì)②：2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*另一方面:3.超平面的幾何性質(zhì)（續(xù)）這是超平面的第二個(gè)性質(zhì)，矢量x到超平面的正交投影正比與g(x)的函數(shù)值。2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*性質(zhì)③：3.超平面的幾何性質(zhì)（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*性質(zhì)④：3.超平面的幾何性質(zhì)（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*一組模式樣本不一定是線性可分的，所以需要研究線性分類(lèi)能力的方法，對(duì)任何容量為N的樣本集，線性可分的概率多大呢？（如下圖（a），線性不可分）例：4個(gè)樣本有幾種分法。圖（b）①直線把x1分開(kāi)，每條直線可把4個(gè)樣本分成ω1

ω2

類(lèi)，4個(gè)樣本分成二類(lèi)的總的可能的分法為24=16類(lèi)，其中有二種是不能用線性分類(lèi)實(shí)現(xiàn)的線性可分的是14。即概率為14/16。4.二分法能力（a）x1x2x3x4⑥

③

②

④

⑤

⑦

（b）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*結(jié)論：N個(gè)樣品線性可分?jǐn)?shù)目(條件：樣本分布良好）：4.二分法能力（續(xù)）對(duì)N和n各種組合的D(N,n)值，表示在下表中，從表中可看出，當(dāng)N，n緩慢增加時(shí)D(N,n)卻增加很快。2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*12345612222222444444368888848141616161651022303232324.二分法能力（續(xù)）線性可分概率：2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*把上式用曲線表示成下圖：圖中橫坐標(biāo)用λ=N/n+1表示。由圖討論：4.二分法能力（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*結(jié)論：在實(shí)際工作中，分類(lèi)的訓(xùn)練非常重要，由已知樣本來(lái)訓(xùn)練。因?yàn)橐阎獦颖居邢?，而未知樣本無(wú)限。選擇已知類(lèi)別的訓(xùn)練樣本數(shù)方法如下：4.二分法能力（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*①：如果訓(xùn)練樣本N

<N0，設(shè)計(jì)分類(lèi)器的分類(lèi)能力太差，因?yàn)橛?xùn)練樣本太少。②：如果訓(xùn)練樣本N太多時(shí)，則樣本太多，運(yùn)算量、存儲(chǔ)量太大。③：因此實(shí)際工作中應(yīng)該?。孩?.二分法能力（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*§2-4廣義線性判別函數(shù)這樣一個(gè)非線性判別函數(shù)通過(guò)映射，變換成線性判別函數(shù)。判別函數(shù)的一般形式：2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*§2-4廣義線性判別函數(shù)（續(xù)）例：如右圖。2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*§2-4廣義線性判別函數(shù)（續(xù)）要用二次判別函數(shù)才可把二類(lèi)分開(kāi)：ω2ω1ω22023/2/4湖南大學(xué)電氣與信息工程學(xué)院*§2-4廣義線性判別函數(shù)（續(xù)）從圖可以看出：在陰影上面是ω1類(lèi)，在陰影下面是ω2類(lèi)，結(jié)論：在X空間的非線性判別函數(shù)通過(guò)變換到Y(jié)空間成為線性的，但X變?yōu)楦呔S空間ω2ω1ω22023/2/4湖南大學(xué)電氣與信息工程學(xué)院*1.分段線性判別函數(shù)（用線性無(wú)法分開(kāi),可用分段線性判別函數(shù)）

①、基于距離的分段線性判別函數(shù)。（用均值代表一類(lèi)，通過(guò)均值連線中點(diǎn)的垂直線分開(kāi)）把ωi類(lèi)可以分成li個(gè)子類(lèi):∴分成l個(gè)子類(lèi)?，F(xiàn)在定義子類(lèi)判別函數(shù)：在同類(lèi)的子類(lèi)中找最近的均值。判別規(guī)則：這是在M類(lèi)中找最近均值。則把x歸于ωj類(lèi)完成分類(lèi)?！?-5非線性判別函數(shù)Ⅱ

Ⅲ

2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*§2-5非線性判別函數(shù)（續(xù)）例：未知x,如圖：先與ω1類(lèi)各子類(lèi)的均值比較，即，找一個(gè)最近的與ω2各子類(lèi)均值比較取最近的因g2(x)<g1(x)，所以x∈ω2類(lèi)。2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*設(shè)ω＝ω1,

ω2

,……ωm而每一類(lèi)又可以分為子類(lèi)。對(duì)每個(gè)子類(lèi)定義一個(gè)線性判別函數(shù)為：則定義ωi類(lèi)的線性判別函數(shù)為：②、基于函數(shù)的分段線性判別函數(shù)利用均值代表一類(lèi)有時(shí)有局限性，如圖所示。若用線性判別函數(shù)代表一類(lèi)，就會(huì)克服上述情況。1.分段線性判別函數(shù)2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*在各子類(lèi)中找最大的判別函數(shù)作為此類(lèi)的代表，則對(duì)于M類(lèi)，可定義M個(gè)判別函數(shù)gi(x),i=1,2,…..M,因此，決策規(guī)則：對(duì)未知模式x，把x先代入每類(lèi)的各子類(lèi)的判別函數(shù)中，找出一個(gè)最大的子類(lèi)判別函數(shù)，M類(lèi)有M個(gè)最大子類(lèi)判別函數(shù)，在M個(gè)子類(lèi)最大判別函數(shù)中，再找一個(gè)最大的，則x就屬于最大的子類(lèi)判別函數(shù)所屬的那一類(lèi)。1.分段線性判別函數(shù)（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*③、基于凹函數(shù)的并分段線性判別函數(shù)（針對(duì)多峰情況）設(shè)li子類(lèi)判別函數(shù)，i=1,2,…..r則分段線性判別函數(shù)有如下特性：1.分段線性判別函數(shù)（續(xù)）(a)：l1,l2,……lr都是分段線性判別函數(shù)(b)：