模式識(shí)別第4章.ppt

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

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

3、單個(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。第一種情況,例：已知三類(lèi)1,2,3的判別函數(shù)分別為：,因此三個(gè)判別邊界為：,1。第一種情況（續(xù)）,作圖如下：,1。第一種情況（續(xù)）,對(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ù)）,必須指出，如果某個(gè)X使二個(gè)以上的判別函數(shù) gi(x)

4、0 。則此模式X就無(wú)法作出確切的判決。如圖中 IR1,IR3，IR4區(qū)域。 另一種情況是IR2區(qū)域，判別函數(shù)都為負(fù)值。IR1，IR2，IR3，IR4。都為不確 定區(qū)域。,1。第一種情況（續(xù)）,問(wèn)當(dāng)x=(x1,x2)T=(6,5)T時(shí)屬于那一類(lèi) 結(jié)論： g1(x) 0 ， g3(x) 0所以它屬于2類(lèi),1。第一種情況（續(xù)）,這樣 有 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)。,判別函數(shù)性質(zhì)： 假設(shè)判別函數(shù)為：,判別邊界為：,2。第

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

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

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

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

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

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

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

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