模式識別判別函數(shù)

模式識別判別函數(shù)第1頁，共53頁，2023年，2月20日，星期五假設對一模式X已抽取n個特征，表示為：模式識別問題就是根據(jù)模式X的n個特征來判別模式屬于ω1,ω2,

…,

ωm類中的那一類。§2-1判別函數(shù)

第2頁，共53頁，2023年，2月20日，星期五例如下圖：三類的分類問題，它們的邊界線就是一個判別函數(shù)§2.1判別函數(shù)（續(xù)）第3頁，共53頁，2023年，2月20日，星期五判別函數(shù)包含兩類：一類是線性判別函數(shù)：線性判別函數(shù)廣義線性判別函數(shù)（所謂廣義線性判別函數(shù)就是把非線性判別函數(shù)映射到另外一個空間變成線性判別函數(shù)）分段線性判別函數(shù)另一類是非線性判別函數(shù)§2.1判別函數(shù)（續(xù)）第4頁，共53頁，2023年，2月20日，星期五§2-2線性判別函數(shù)我們現(xiàn)在對兩類問題和多類問題分別進行討論。(一)兩類問題即:

1.二維情況：取兩個特征向量這種情況下判別函數(shù):第5頁，共53頁，2023年，2月20日，星期五在兩類別情況，判別函數(shù)g

(x)

具有以下性質(zhì)：這是二維情況下判別由判別邊界分類.情況如圖：1.二維情況第6頁，共53頁，2023年，2月20日，星期五2.n維情況現(xiàn)抽取n個特征為：判別函數(shù)：

另外一種表示方法：第7頁，共53頁，2023年，2月20日，星期五模式分類：當g1(x)=WTX=0為判別邊界。當n=2時，二維情況的判別邊界為一直線。當n=3時，判別邊界為一平面，n>3時，則判別邊界為一超平面。2.n維情況第8頁，共53頁，2023年，2月20日，星期五(二)

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

…,

ωm個類別?？煞秩N情況：1。第一種情況：每一模式類與其它模式類間可用單個判別平面把一個類分開。這種情況，M類可有M個判別函數(shù)，且具有以下性質(zhì)：第9頁，共53頁，2023年，2月20日，星期五右圖所示，每一類別可用單個判別邊界與其它類別相分開。如果一模式X屬于ω1，則由圖可清楚看出:這時g1(x)>0而g2(x)<0，g3(x)<0。ω1類與其它類之間的邊界由g1(x)=0確定.1。第一種情況第10頁，共53頁，2023年，2月20日，星期五例：已知三類ω1,ω2,ω3的判別函數(shù)分別為：因此三個判別邊界為：1。第一種情況（續(xù)）第11頁，共53頁，2023年，2月20日，星期五作圖如下：1。第一種情況（續(xù)）第12頁，共53頁，2023年，2月20日，星期五對于任一模式X如果它的g1(x)>0，g2(x)<0，g3(x)<0則該模式屬于ω1類。相應ω1類的區(qū)域由直線-x2+1=0

的正邊、直線-x1+x2-5=0和直線-x1+x2=0的負邊來確定。1。第一種情況（續(xù)）第13頁，共53頁，2023年，2月20日，星期五必須指出，如果某個X使二個以上的判別函數(shù)gi(x)>0。則此模式X就無法作出確切的判決。如圖中

IR1,IR3，IR4區(qū)域。另一種情況是IR2區(qū)域，判別函數(shù)都為負值。IR1，IR2，IR3，IR4。都為不確定區(qū)域。1。第一種情況（續(xù)）第14頁，共53頁，2023年，2月20日，星期五問當x=(x1,x2)T=(6,5)T時屬于那一類結論：g1(x)<0，g2(x)>0，g3(x)<0所以它屬于ω2類1。第一種情況（續(xù)）第15頁，共53頁，2023年，2月20日，星期五這樣有M(M_1)/2個判別平面。對于兩類問題，M=2，則有一個判別平面。同理，三類問題則有三個判別平面。

判別函數(shù)：判別邊界：判別條件：2。第二種情況：每個模式類和其它模式類間可分別用判別平面分開。第16頁，共53頁，2023年，2月20日，星期五判別函數(shù)性質(zhì)：假設判別函數(shù)為：判別邊界為：2。第二種情況（續(xù)）用方程式作圖：第17頁，共53頁，2023年，2月20日，星期五問:未知模式X=(x1,x2)T=(4,3)T屬于那一類代入判別函數(shù)可得:把下標對換可得:因為結論：所以X屬于ω3類結論：判別區(qū)間增大，不確定區(qū)間減小，比第一種情況小的多.2。第二種情況（續(xù)）第18頁，共53頁，2023年，2月20日，星期五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ù)第19頁，共53頁，2023年，2月20日，星期五右圖所示是M=3的例子。對于ω1類模式，必然滿足g1(x)>g2(x)

和g1(x)>g3(x)

。假設判別函數(shù)為：則判別邊界為：3。第三種情況（續(xù)）第20頁，共53頁，2023年，2月20日，星期五結論：不確定區(qū)間沒有了，所以這種是最好情況。用上列方程組作圖如下：3。第三種情況（續(xù)）第21頁，共53頁，2023年，2月20日，星期五問假設未知模式x=(x1,x2)T=(1,1)T

，則x屬于那一類。把它代入判別函數(shù)：得判別函數(shù)為：因為所以模式x=(1,1)T屬于類。3。第三種情況（續(xù)）第22頁，共53頁，2023年，2月20日，星期五§2-3、線性判別函數(shù)的性質(zhì)1、模式空間與加權空間模式空間：由構成的n維歐氏空間。W是此空間的加權向量，它決定模式的分界面H，W與H正交。加權空間：以為變量構成的歐氏空間模式空間與加權空間的幾何表示如下圖：第23頁，共53頁，2023年，2月20日，星期五模式空間第24頁，共53頁，2023年，2月20日，星期五第25頁，共53頁，2023年，2月20日，星期五1、模式空間與加權空間（續(xù)）第26頁，共53頁，2023年，2月20日，星期五該式表示一個通過加權空間原點的平面，此平面就是加權空間圖中的平面①,同樣令g

(x2)=g

(x3)=g

(x4)=0，分別作出通過加權空間原點的平面②③④圖中用陰影表示的部分是各平面的正側。加權空間的構造：設是加權空間分界面上的一點，代入上式得：1、模式空間與加權空間第27頁，共53頁，2023年，2月20日，星期五這是一個不等式方程組，它的解處于由ω1類所有模式?jīng)Q定的平面的正邊和由ω2類所有模式?jīng)Q定的平面的負邊，它的解區(qū)即為凸多面錐。如圖所示：(b)為加權空間，（c）為正規(guī)化后的加權空間。由上可以得到結論：加權空間的所有分界面都通過坐標原點。這是加權空間的性質(zhì)。為了更清楚，下面用二維權空間來表示解向量和解區(qū)。1、模式空間與加權空間（續(xù)）第28頁，共53頁，2023年，2月20日，星期五在三維空間里，令w3

=0

則為二維權空間。如圖：給定一個模式X，就決定一條直線：即分界面H，W與H正交，W稱為解向量。解向量的變動范圍稱為解區(qū)。因x1,x2∈ω1，x3,x4∈ω2由圖可見x1,x3離的最近，所以分界面H可以是x1,x3之間的任一直線，由垂直于這些直線的W就構成解區(qū)，解區(qū)為一扇形平面，即陰影區(qū)域。如右圖:2、解向量和解區(qū)第29頁，共53頁，2023年，2月20日，星期五把不等式方程正規(guī)化：正規(guī)化：2、解向量的解區(qū)（續(xù)）第30頁，共53頁，2023年，2月20日，星期五g(x)=WTX=0決定一個決策界面，當g(x)為線性時，這個決策界面便是一個超平面H，并有以下性質(zhì)：性質(zhì)①：W與H正交（如圖所示）假設x1,x2是H上的兩個向量所以W

與(x1-x2)

垂直，即W與H正交。一般說，超平面H把特征空間分成兩個半空間。即Ω1,Ω2空間，當x在Ω1空間時g(x)>0,W指向Ω1，為H的正側，反之為H的負側.3、超平面的幾何性質(zhì)第31頁，共53頁，2023年，2月20日，星期五Ω1Ω2g(x)>0g(x)<03、超平面的幾何性質(zhì)第32頁，共53頁，2023年，2月20日，星期五矢量到H的正交投影與值成正比其中：x

p：x在H

的投影向量，r是x

到H

的垂直距離。是W方向的單位向量。3、超平面的幾何性質(zhì)（續(xù)）性質(zhì)②：第33頁，共53頁，2023年，2月20日，星期五另一方面:3、超平面的幾何性質(zhì)（續(xù)）這是超平面的第二個性質(zhì)，矢量x到超平面的正交投影正比與g(x)的函數(shù)值。第34頁，共53頁，2023年，2月20日，星期五性質(zhì)③：3、超平面的幾何性質(zhì)（續(xù)）第35頁，共53頁，2023年，2月20日，星期五性質(zhì)④：3、超平面的幾何性質(zhì)（續(xù)）第36頁，共53頁，2023年，2月20日，星期五一組模式樣本不一定是線性可分的，所以需要研究線性分類能力的方法，對任何容量為N的樣本集，線性可分的概率多大呢？（如下圖（a），線性不可分）例：4個樣本有幾種分法。圖（b）①直線把x1分開，每條直線可把4個樣本分成ω1

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

③

②

④

⑤

⑦

（b）第37頁，共53頁，2023年，2月20日，星期五結論：N個樣品線性可分數(shù)目(條件：樣本分布良好）：4。二分法能力（續(xù)）對N和n各種組合的D(N,n)值，表示在下表中，從表中可看出，當N，n緩慢增加時D(N,n)卻增加很快。第38頁，共53頁，2023年，2月20日，星期五12345612222222444444368888848141616161651022303232324。二分法能力（續(xù)）線性可分概率：第39頁，共53頁，2023年，2月20日，星期五把上式用曲線表示成下圖：圖中橫坐標用λ=N/n+1表示。由圖討論：4。二分法能力（續(xù)）第40頁，共53頁，2023年，2月20日，星期五結論：在實際工作中，分類的訓練非常重要，由已知樣本來訓練。因為已知樣本有限，而未知樣本無限。選擇已知類別的訓練樣本數(shù)方法如下：4。二分法能力（續(xù)）第41頁，共53頁，2023年，2月20日，星期五①：如果訓練樣本N<N0，設計分類器的分類能力太差，因為訓練樣本太少。②：如果訓練樣本N太多時，則樣本太多，運算量、存儲量太大。③：因此實際工作中應該?。孩?。二分法能力（續(xù)）第42頁，共53頁，2023年，2月20日，星期五§2-4、廣義線性判別函數(shù)這樣一個非線性判別函數(shù)通過映射，變換成線性判別函數(shù)。判別函數(shù)的一般形式：第43頁，共53頁，2023年，2月20日，星期五§2-4、廣義線性判別函數(shù)（續(xù)）例：如右圖。第44頁，共53頁，2023年，2月20日，星期五§2-4、廣義線性判別函數(shù)（續(xù)）要用二次判別函數(shù)才可把二類分開：ω2ω1ω2第45頁，共53頁，2023年，2月20日，星期五§2-4、廣義線性判別函數(shù)（續(xù)）從圖可以看出：在陰影上面是ω1類，在陰影下面是ω2類，結論：在X空間的非線性判別函數(shù)通過變換到Y空間成為線性的，但X變?yōu)楦呔S空間ω2ω1ω2第46頁，共53頁，2023年，2月20日，星期五1.分段線性判別函數(shù)（用線性無法分開,可用分段線性判別函數(shù)）

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

Ⅲ

第47頁，共53頁，2023年，2月20日，星期五§2-5、非線性判別函數(shù)（續(xù)）例：未知x,如圖：先與ω1類各子類的均值比較，即，找一個最近的與ω2各子類均值比較取最近的因g2(x)<g1(x)，所以x∈ω2類。第48頁，共53頁，2023年，2月20日，星期五設ω＝ω1,

ω2

,……ωm而每一類又可以分為子類。對每個子類定義一個線性判別函數(shù)為：則定義ωi類的線性判別函數(shù)為：②、基于函數(shù)的分段線性判別函數(shù)利用均值代表一類有時有局限性，如圖所示。若用線性判別函數(shù)代表一類，就會克服上述情況。1、分段線性判別函數(shù)第49頁，共53頁，2023年，2月20日，星期五在各子類中找最大的判別函數(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ù)）第50頁，共53頁，2023年，2月20日，星期五③