模式識別第4章.ppt

1、第四章 線性判別函數(shù),2010.11,第四章 線性判別函數(shù),4.1引言 4.2 Fisher線性判別 4.3 感知準則函數(shù) 4.4 最小錯分樣本數(shù)準則 4.5 最小平方誤差準則函數(shù) 4.6 隨機最小錯誤率線性判別準則函數(shù) 4.7 多類問題,引言,設(shè)計貝葉斯分類器的方法：即已知先驗概率P(i)和類條件概率密度p(x/i)的情況下，按一定的決策規(guī)則確定判別函數(shù)和決策面。 類條件概率密度的形式常常難以確定，利用非參數(shù)估計分布需要大量樣本，且所需樣本數(shù)隨維數(shù)升高急劇增加。 線性判別函數(shù)法,線性判別函數(shù),我們現(xiàn)在對兩類問題和多類問題分別進行討論。 (一)兩類問題 即: 1. 二維情況 ：取兩個特征向量

2、這種情況下 判別函數(shù):,在兩類別情況，判別函數(shù) g (x) 具有以下性質(zhì)： 這是二維情況下判別由判別邊界分類. 情況如圖：,1. 二維情況,2. n維情況,現(xiàn)抽取n個特征為： 判別函數(shù)： 另外一種表示方法：,模式分類： 當 g1(x) =WTX=0 為判別邊界 。當n=2時，二維情況的判別邊界為一直線。當n=3時，判別邊界為一平面，n3時，則判別邊界為一超平面。,2. n維情況,(二) 多類問題,對于多類問題，模式有 1 ,2 , , c 個類別?？煞秩N情況： 1。第一種情況：每一模式類與其它模式類間可用單個判別平面把一個類分開。這種情況，M類可有M個判別函數(shù)，且具有以下性質(zhì)：,每一類別可用

3、單個判別邊界與其它類別相分開 。 如果一模式X屬于1，則由圖可清楚看出:這時g1(x) 0而g2(x) 0 ， g3(x) 0 。 1 類與其它類之間的邊界由 g1(x)=0確定.,1。第一種情況,例：已知三類1,2,3的判別函數(shù)分別為：,因此三個判別邊界為：,1。第一種情況（續(xù)）,作圖如下：,1。第一種情況（續(xù)）,對于任一模式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ù)）,必須指出，如果某個X使二個以上的判別函數(shù) gi(x)

4、0 。則此模式X就無法作出確切的判決。如圖中 IR1,IR3，IR4區(qū)域。 另一種情況是IR2區(qū)域，判別函數(shù)都為負值。IR1，IR2，IR3，IR4。都為不確 定區(qū)域。,1。第一種情況（續(xù)）,問當x=(x1,x2)T=(6,5)T時屬于那一類 結(jié)論： g1(x) 0 ， g3(x) 0所以它屬于2類,1。第一種情況（續(xù)）,這樣 有 M(M _ 1)/2個判別平面。 對于兩類問題，M=2，則有一個判別平面。 同理，三類問題則有三個判別平面。,判別函數(shù)： 判別邊界： 判別條件：,2。第二種情況：,每個模式類和其它模式類間可分別用判別平面分開。,判別函數(shù)性質(zhì)： 假設(shè)判別函數(shù)為：,判別邊界為：,2。第

5、二種情況（續(xù)）,用方程式作圖：,問:未知模式X=(x1,x2)T=(4,3)T屬于那一類,代入判別函數(shù)可得: 把下標對換可得: 因為 結(jié)論：所以X 屬于3類,結(jié)論：判別區(qū)間增大，不確定 區(qū)間減小，比第一種情況小的多.,2。第二種情況（續(xù)）,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ù),右圖所示是M=3

6、的例子。對于1類模式， 必然滿足g1(x) g2(x) 和 g1(x) g3(x) 。 假設(shè)判別函數(shù)為： 則判別邊界為：,3。第三種情況（續(xù)）,結(jié)論：不確定區(qū)間沒有了，所以這種是最好情況。,用上列方程組作圖如下：,3。第三種情況（續(xù)）,問假設(shè)未知模式x= (x1,x2)T= (1,1)T ，則x屬于那一類。 把它代入判別函數(shù)： 得判別函數(shù)為： 因為 所以模式x= (1,1)T屬于 類。,3。第三種情況（續(xù)）,廣義線性判別函數(shù),這樣一個非線性判別函數(shù)通過映射，變換成線性判別函數(shù)。,判別函數(shù)的一般形式：,廣義線性判別函數(shù)（續(xù)）,例：如右圖。,廣義線性判別函數(shù)（續(xù)）,要用二次判別函數(shù)才可把二類分開：

7、,廣義線性判別函數(shù)（續(xù)）,從圖可以看出：在陰影上面是1類，在陰影下面是2類， 結(jié)論：在X空間的非線性判別函數(shù)通過變換到Y(jié)空間成為線性的，但X變?yōu)楦呔S空間,Fisher線性判別,出發(fā)點 應(yīng)用統(tǒng)計方法解決模式識別問題時，一再碰到的問題之一就是維數(shù)問題。 在低維空間里解析上或計算上行得通的方法，在高維空間里往往行不通。 因此，降低維數(shù)有時就會成為處理實際問題的關(guān)鍵。,Fisher線性判別,問題描述 考慮把d維空間的樣本投影到一條直線上，形成一維空間，即把維數(shù)壓縮到一維。 然而，即使樣本在d維空間里形成若干緊湊的互相分得開的集群，當把它們投影到一條直線上時，也可能會是幾類樣本混在一起而變得無法識別。

8、但是，在一般情況下，總可以找到某個方向，使在這個方向的直線上，樣本的投影能分得開。,Fisher線性判別,問題描述 問題：如何根據(jù)實際情況找到一條最好的、最易于分類的投影線，這就是Fisher判別方法所要解決的基本問題。,Fisher線性判別,從d維空間到一維空間的一般數(shù)學變換方法 假設(shè)有一集合包含N個d維樣本x1, x2, , xN，其中N1個屬于1類的樣本記為子集1， N2個屬于2類的樣本記為子集2 。若對xn的分量做線性組合可得標量： yn = wTxn, n=1,2,N 這樣便得到N個一維樣本yn組成的集合，并可分為兩個子集1和2 。,Fisher線性判別,從d維空間到一維空間的一般數(shù)

9、學變換方法 實際上，w的值是無關(guān)緊要的，它僅是yn乘上一個比例因子，重要的是選擇w的方向。w的方向不同，將使樣本投影后的可分離程度不同，從而直接影響的分類效果。 因此，上述尋找最佳投影方向的問題，在數(shù)學上就是尋找最好的變換向量w*的問題。,Fisher線性判別,Fisher線性判別,我們希望投影后，在一維Y空間中各類樣本盡可能分得開些，即希望兩類均值之差越大越好，同時希望各類樣本內(nèi)部盡量密集，即希望類內(nèi)離散度越小越好。,Fisher線性判別,Fisher線性判別,基于最佳變換向量w*的投影 w*是使Fisher準則函數(shù)JF(w)取極大值時的解，也就是d維X空間到一維Y空間的最佳投影方向。有了w

10、*，就可以把d維樣本x投影到一維，這實際上是多維空間到一維空間的一種映射，這個一維空間的方向w*相對于Fisher準則函數(shù)JF(w)是最好的。 利用Fisher準則，就可以將d維分類問題轉(zhuǎn)化為一維分類問題，然后，只要確定一個閾值T，將投影點yn與T相比較，即可進行分類判別。,感知器算法,出發(fā)點 一旦判別函數(shù)的形式確定下來，不管它是線性的還是非線性的，剩下的問題就是如何確定它的系數(shù)。 在模式識別中，系數(shù)確定的一個主要方法就是通過對已知樣本的訓(xùn)練和學習來得到。 感知器算法就是通過訓(xùn)練樣本模式的迭代和學習，產(chǎn)生線性（或廣義線性）可分的模式判別函數(shù)。,感知器算法,基本思想 采用感知器算法(Percep

11、tion Approach)能通過對訓(xùn)練模式樣本集的“學習”得到判別函數(shù)的系數(shù) 說明 這里采用的算法不需要對各類別中模式的統(tǒng)計性質(zhì)做任何假設(shè)，因此稱為確定性的方法。,感知器算法,感知器的訓(xùn)練算法 感知器算法實質(zhì)上是一種賞罰過程 對正確分類的模式則“賞”，實際上是“不罰”，即權(quán)向量不變。 對錯誤分類的模式則“罰”，使w(k)加上一個正比于Xk的分量。 當用全部模式樣本訓(xùn)練過一輪以后，只要有一個模式是判別錯誤的，則需要進行下一輪迭代，即用全部模式樣本再訓(xùn)練一次。 如此不斷反復(fù)直到全部模式樣本進行訓(xùn)練都能得到正確的分類結(jié)果為止。,感知器算法,感知器算法的收斂性 只要模式類別是線性可分的，就可以在有限

12、的迭代步數(shù)里求出權(quán)向量。,采用感知器算法的多類模式的分類,采用多類情況3，將感知器算法推廣到多類模式。 感知器算法判別函數(shù)的推導(dǎo),采用感知器算法的多類模式的分類,討論 這里的分類算法都是通過模式樣本來確定判別函數(shù)的系數(shù)，但一個分類器的判斷性能最終要受并未用于訓(xùn)練的那些未知樣本來檢驗。 要使一個分類器設(shè)計完善，必須采用有代表性的訓(xùn)練數(shù)據(jù)，它能夠合理反映模式數(shù)據(jù)的整體。,采用感知器算法的多類模式的分類,討論 要獲得一個判別性能好的線性分類器，究竟需要多少訓(xùn)練樣本？ 直觀上是越多越好，但實際上能收集到的樣本數(shù)目會受到客觀條件的限制； 過多的訓(xùn)練樣本在訓(xùn)練階段會使計算機需要較長的運算時間； 一般來說，合適的樣本數(shù)目可如下估計： 若k是模式的維數(shù)，