模式識別導(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è)對一模式X已抽取n個特征，表示為：模式識別問題就是根據(jù)模式X的n個特征來判別模式屬于ω1,ω2,

…,

ωm

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

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

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

(x)

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

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

多類問題對于多類問題，模式有ω1,ω2,

…,

ωm

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

，g3(x)<0

。ω1

類與其它類之間的邊界由g1(x)=0確定.1.第一種情況2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*例：已知三類ω1,ω2,ω3的判別函數(shù)分別為：因此三個判別邊界為：1.第一種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*作圖如下：1.第一種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*對于任一模式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的負邊來確定。1.第一種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*必須指出，如果某個X使二個以上的判別函數(shù)gi(x)>0。則此模式X就無法作出確切的判決。如圖中

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

判別函數(shù)：判別邊界：判別條件：2.第二種情況每個模式類和其它模式類間可分別用判別平面分開。2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*判別函數(shù)性質(zhì)：假設(shè)判別函數(shù)為：判別邊界為：2.第二種情況（續(xù)）用方程式作圖：2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*問:未知模式X=(x1,x2)T=(4,3)T屬于那一類代入判別函數(shù)可得:把下標(biāo)對換可得:因為結(jié)論：所以X屬于ω3類結(jié)論：判別區(qū)間增大，不確定區(qū)間減小，比第一種情況小的多.2.第二種情況（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*3.第三種情況判別函數(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ù)2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*右圖所示是M=3的例子。對于ω1類模式，必然滿足g1(x)>g2(x)

和g1(x)>g3(x)

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

，則x屬于那一類。把它代入判別函數(shù)：得判別函數(shù)為：因為所以模式x=(1,1)T屬于類。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é)院*該式表示一個通過加權(quán)空間原點的平面，此平面就是加權(quán)空間圖中的平面①,同樣令g

(x2)=g

(x3)=g

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

與(x1-x2)

垂直，即W與H正交。一般說，超平面H把特征空間分成兩個半空間。即Ω1,Ω2空間，當(dāng)x在Ω1空間時g(x)>0,W指向Ω1，為H的正側(cè)，反之為H的負側(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ù)）這是超平面的第二個性質(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é)院*一組模式樣本不一定是線性可分的，所以需要研究線性分類能力的方法，對任何容量為N的樣本集，線性可分的概率多大呢？（如下圖（a），線性不可分）例：4個樣本有幾種分法。圖（b）①直線把x1分開，每條直線可把4個樣本分成ω1

ω2

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

③

②

④

⑤

⑦

（b）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*結(jié)論：N個樣品線性可分數(shù)目(條件：樣本分布良好）：4.二分法能力（續(xù)）對N和n各種組合的D(N,n)值，表示在下表中，從表中可看出，當(dāng)N，n緩慢增加時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é)論：在實際工作中，分類的訓(xùn)練非常重要，由已知樣本來訓(xùn)練。因為已知樣本有限，而未知樣本無限。選擇已知類別的訓(xùn)練樣本數(shù)方法如下：4.二分法能力（續(xù)）2023/2/4湖南大學(xué)電氣與信息工程學(xué)院*①：如果訓(xùn)練樣本N

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

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

Ⅲ

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

ω2

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