模式識(shí)別1-2判別函數(shù)

1、信息工程學(xué)院* 2-1、判別函數(shù) 2-2、線性判別函數(shù) 2-3、線性判別函數(shù)的性質(zhì) 2-4、廣義線性判別函數(shù) 2-5、非線性判別函數(shù)第二章 判別函數(shù)信息工程學(xué)院*v假設(shè)對(duì)一模式X已抽取n個(gè)特征，表示為：v模式識(shí)別問(wèn)題就是根據(jù)模式X X的n n個(gè)特征來(lái)判別模式屬于1 ,2 , , m 類中的那一類。 2-1 判別函數(shù) 維空間的一個(gè)向量是n),.,(321XxxxxXTn信息工程學(xué)院*v例如下圖：三類的分類問(wèn)題，它們的邊界線就是一個(gè)判別函數(shù)123邊界2x1x2.1 判別函數(shù)（續(xù)）信息工程學(xué)院*v判別函數(shù)包含兩類：v一類 是線性判別函數(shù)：線性判別函數(shù)廣義線性判別函數(shù) （所謂廣義線性判別函數(shù)就是把非線

2、性判別函數(shù)映射到另外一個(gè)空間變成線性判別函數(shù)）分段線性判別函數(shù)v另一類是非線性判別函數(shù)2.1 判別函數(shù)（續(xù)）信息工程學(xué)院* 2-2 線性判別函數(shù)v我們現(xiàn)在對(duì)兩類問(wèn)題和多類問(wèn)題分別進(jìn)行討論。v(一)兩類問(wèn)題 即: v v1. 二維情況 ：取兩個(gè)特征向量v 這種情況下 判別函數(shù):2,),(21MTi2,)(2,1nxxXT32211wxwxw)x(g為坐標(biāo)向量為參數(shù)，21, xxw信息工程學(xué)院*v在兩類別情況，判別函數(shù) g (x) 具有以下性質(zhì)：v這是二維情況下判別由判別邊界分類.v情況如圖：1. 二維情況21, 0, 0)(XXxgi不定Xxg,0)(32211)(wxwxwxg211x2x信息

3、工程學(xué)院*2. n維情況v現(xiàn)抽取n個(gè)特征為：v判別函數(shù)： v另外一種表示方法：TnxxxxX),.,(32112211.)(nnnwxwxwxwxg10nwXW為增值模式向量。，為增值權(quán)向量，TnnTnnxxxxXwwwwW) 1,.,(),.,(21121XWxgT)(為模式向量。為權(quán)向量，TnTnxxxXwwwW),.,(),.,(21210信息工程學(xué)院*v模式分類：v當(dāng) g1(x) =WTX=0 為判別邊界 。當(dāng)n=2時(shí)，二維情況的判別邊界為一直線。當(dāng)n=3時(shí)，判別邊界為一平面，n3時(shí)，則判別邊界為一超平面。21,0,0)(xxXWxgT2. n維情況信息工程學(xué)院*(二) 多類問(wèn)題。其它

4、MiXXWxgiTii,.,2 , 1, 0, 0)(v對(duì)于多類問(wèn)題，模式有 1 ,2 , , m 個(gè)類別?？煞秩N情況：1。第一種情況：每一模式類與其它模式類間可用單第一種情況：每一模式類與其它模式類間可用單個(gè)判別平面把一個(gè)類分開(kāi)。個(gè)判別平面把一個(gè)類分開(kāi)。這種情況，M類可有M個(gè)判別函數(shù)，且具有以下性質(zhì)：權(quán)向量。個(gè)判別函數(shù)的為第式中iwwwwWTininiii) ,.,(121信息工程學(xué)院*v右圖所示，每一類別可用單個(gè)判別邊界與其它類別相分開(kāi) 。v如果一模式X屬于1，則由圖可清楚看出:這時(shí)g1(x) 0而g2(x) 0 ， g3(x) 0 ， g2(x) 0 ， g3(x) 0 。則此模式X就

5、無(wú)法作出確切的判決。如圖中 IR1,IR3，IR4區(qū)域。v另一種情況是IR2區(qū)域，判別函數(shù)都為負(fù)值。IR1，IR2，IR3，IR4。都為不確 定區(qū)域。1 1。第一種情況（續(xù)）第一種情況（續(xù)）30)(0)(0)(321xgxgxg12000321)x(g)x(g)x(g0)(0)(0)(321xgxgxg 4IR3IR1IR2IR1x2x0)(1xg0)(2xg0)(3xg551信息工程學(xué)院*v問(wèn)當(dāng)x=(x1,x2)T=(6,5)T時(shí)屬于那一類v結(jié)論： g1(x) 0 ， g3(x) g2(x) 和 g1(x) g3(x) 。v假設(shè)判別函數(shù)為：v則判別邊界為：23212211)(1)()(xxg

6、xxxgxxxg012)()(02)()(012)()(21322131121xxxgxgxxxgxgxxgxg2)()(21xgxg)()(32xgxg)()(31xgxg133。第三種情況（續(xù)）信息工程學(xué)院*v結(jié)論：不確定區(qū)間沒(méi)有了，所以這種是最好情況。v用上列方程組作圖如下：3。第三種情況（續(xù)）1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05.0信息工程學(xué)院*v問(wèn)假設(shè)未知模式x= (x1,x2)T= (1,1)T ，則x屬于那一類。

7、v把它代入判別函數(shù)：v得判別函數(shù)為：v因?yàn)関所以模式x= (1,1)T屬于 類。3。第三種情況（續(xù)）2)()(),()(1232xgxgxgxg1)(, 1)(, 0)(321xgxgxg).(),(),(321xgxgxg1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05 . 0信息工程學(xué)院*2-3、線性判別函數(shù)的性質(zhì)v1、模式空間與加權(quán)空間v模式空間：由 構(gòu)成的n維歐氏空間。vW是此空間的加權(quán)向量，它決定模式的分界面H，W與H正交。v加

8、權(quán)空間：以 為變量構(gòu)成的歐氏空間v模式空間與加權(quán)空間的幾何表示如下圖：XWxgTi)(TnxxxxX),.,(321121,.,nwww模式空間 2X1X121x3x4x0)(xg邊界2xHW信息工程學(xué)院*模式空間信息工程學(xué)院*加權(quán)空間判別界面信息工程學(xué)院*1、模式空間與加權(quán)空間（續(xù)）信息工程學(xué)院*v該式表示一個(gè)通過(guò)加權(quán)空間原點(diǎn)的平面，此平面就是加權(quán)空間圖中的平面,同樣令g (x2) =g (x3) =g (x4)=0，分別作出通過(guò)加權(quán)空間原點(diǎn)的平面圖中用陰影表示的部分是各平面的正側(cè)。v加權(quán)空間的構(gòu)造：v設(shè) 是加權(quán)空間分界面上的一點(diǎn)，代入上式得：這是加權(quán)空間的邊界, 0)(31221111wx

9、wxwxg1、模式空間與加權(quán)空間Txxx),(1211123422411332231100wxwxwwxwxw13222211312211100wxwxwwxwxw243121,xxxx設(shè)：最終形成圖多面錐210)(xxxg32211)(wxwxwxg信息工程學(xué)院*v這是一個(gè)不等式方程組，它的解 處于由1類所有模式?jīng)Q定的平面的正邊和由2類所有模式?jīng)Q定的平面的負(fù)邊，它的解區(qū)即為凸多面錐。v如圖所示：(b)為加權(quán)空間，（c）為正規(guī)化后的加權(quán)空間。v由上可以得到結(jié)論：加權(quán)空間的所有分界面都通過(guò)坐標(biāo)原點(diǎn)。這是加權(quán)空間的性質(zhì)。v為了更清楚，下面用二維權(quán)空間來(lái)表示解向量和解區(qū)。1、模式空間與加權(quán)空間（續(xù)）

10、TwwwW),(321信息工程學(xué)院*v在三維空間里，令w3 = 0 則為二維權(quán)空間。如圖：v給定一個(gè)模式X，就決定一條直線：v即分界面H，W與H正交，W稱為解向量。v解向量的變動(dòng)范圍稱為解區(qū)。v因x1,x21， x3,x42由圖可見(jiàn)x1,x3離的最近，所以分界面H可以是x1,x3之間的任一直線，由垂直于這些直線的W就構(gòu)成解區(qū)，解區(qū)為一扇形平面，即陰影區(qū)域。v如右圖:2、解向量和解區(qū)0)(XWxgT1w2w1x4x3x2x解區(qū)W解向量分界面H解向量與解區(qū)信息工程學(xué)院*v把不等式方程正規(guī)化：v正規(guī)化：00003422411332231132222113122111wxwxwwxwxwwxwxwwx

11、wxw) ,.,(0)(121nnTiwwwwWXWxg2、解向量的解區(qū)（續(xù)）1w2w1x4x3x2x解區(qū)解向量分界面H3x4x正規(guī)化信息工程學(xué)院*vg(x)=WTX=0決定一個(gè)決策界面，當(dāng)g(x)為線性時(shí)，這個(gè)決策界面便是一個(gè)超平面H，并有以下性質(zhì)：v性質(zhì)：W與H正交（如圖所示）v假設(shè)x1,x2是H上的兩個(gè)向量v所以 vW 與(x1-x2) 垂直，即W與H正交。v一般說(shuō)，超平面H把特征空間分成兩個(gè)半空間。即1,2空間，當(dāng)x在1空間時(shí)g(x)0,W指向1，為H的正側(cè)，反之為H的負(fù)側(cè).上矢量一定在HxxxxWwxWwxWTnTnT)( , 0)(0212112113、超平面的幾何性質(zhì)信息工程學(xué)院

12、*1x2X1X2xWH12g(x)0g(x)03、超平面的幾何性質(zhì)信息工程學(xué)院*v 矢量到H的正交投影 與 值成正比v其中： x p： x在H 的投影向量，vr是x 到H 的垂直距離。v 是W方向的單位向量。3、超平面的幾何性質(zhì)（續(xù)）W)x(grv性質(zhì) ：WWrxrxxpp)(xgxrWWq2X1XpxWxHpr信息工程學(xué)院*v另一方面:11)()(npTnTwrxWwxWxg1nTpTwrWxW)(,)()()(021WWWrWxgrWrWWWrWWrWrWxgwxWHpTTTTnpT是投影的絕對(duì)值上。在因?yàn)?、超平面的幾何性質(zhì)（續(xù)）v這是超平面的第二個(gè)性質(zhì)，矢量x到超平面的正交投影 正比與

13、g(x)的函數(shù)值。r信息工程學(xué)院*WWqqrHxxqWWWxgrxwwxWxgnnnnT11110)()0()(的投影為到時(shí)因因原點(diǎn)因?yàn)槌烧鹊木嚯x與原點(diǎn)到11nnWH,WWqv性質(zhì)：3、超平面的幾何性質(zhì)（續(xù)）q2X1X0H信息工程學(xué)院*v性質(zhì)：通過(guò)原點(diǎn)。，說(shuō)明超平面則若在原點(diǎn)負(fù)側(cè)。則在原點(diǎn)正側(cè)，若則若HxWxgWHWHWTnnn)(, 0, 0, 0111否則，反之。的正側(cè)，在代數(shù)距離。到正比于來(lái)決定。的位置由超平面決定正交，方向由的平面與）超平面（結(jié)論：, 0)()()()(1xgHxHxxgcWHbWWHan3、超平面的幾何性質(zhì)（續(xù)）信息工程學(xué)院*v一組模式樣本不一定是線性可分的，所以需

14、要研究線性分類能力的方法，對(duì)任何容量為N的樣本集，線性可分的概率多大呢？v（如下圖（a），線性不可分）v例：4個(gè)樣本有幾種分法。v圖（b）直線把x1分開(kāi)，每條直線可把4個(gè)樣本分成1 2 類，4個(gè)樣本分成二類的總的可能的分法為24=16類，其中有二種是不能用線性分類實(shí)現(xiàn)的線性可分的是14。即概率為14/16。4。二分法能力（a）x1x2x3x4 （b）信息工程學(xué)院*v結(jié)論：N個(gè)樣品線性可分?jǐn)?shù)目(條件：樣本分布良好）：4。二分法能力（續(xù)）為特征數(shù)為樣本數(shù)其中nNkNkNCkN,)!1( !)!1(1nkkNNnNCnNnND011,21,2),(若若v對(duì)N和n各種組合的D(N,n)值，表示在下表中

15、，從表中可看出，當(dāng)N，n緩慢增加時(shí)D(N,n)卻增加很快。信息工程學(xué)院*12345612222222444444368888848141616161651022303232324。二分法能力（續(xù)）n),(nNDNnkkNNNnNCnNnNDnNP0111,21, 12),(),(若若v線性可分概率：信息工程學(xué)院*),(nNP0 .15 .00543211n5n15nn1nN強(qiáng)。說(shuō)明樣本少時(shí)二分能力范圍，即在。時(shí)，線性可分概率為時(shí)，即值，對(duì)于任意。處出現(xiàn)明顯的門限效應(yīng)時(shí)，曲線急劇下降，在由當(dāng), 1),(),1(22: )(21),() 1(22: )(21: )(nNPnNcnNPnNnbnav

16、把上式用曲線表示成下圖：圖中橫坐標(biāo)用=N/n+1表示。v由圖討論：4。二分法能力（續(xù)）信息工程學(xué)院*.2),1(2: )(,),1(22: )(0是最好情況即二分能力）的估計(jì)：個(gè)樣本的線性可分性（對(duì)多線性可分能力越差。說(shuō)明樣品越線性可分概率急劇下降范圍，即在nNNenNd),(nNP0 . 15 .00543211n5n15nn1nNv結(jié)論：在實(shí)際工作中，分類的訓(xùn)練非常重要，由已知樣本來(lái)訓(xùn)練。因?yàn)橐阎獦颖居邢?，而未知樣本無(wú)限。選擇已知類別的訓(xùn)練樣本數(shù)方法如下：4。二分法能力（續(xù)）信息工程學(xué)院*v：如果訓(xùn)練樣本N N0，設(shè)計(jì)分類器的分類能力太差，因?yàn)橛?xùn)練樣本太少。v：如果訓(xùn)練樣本N太多時(shí)，則樣本

17、太多，運(yùn)算量、存儲(chǔ)量太大。v：因此實(shí)際工作中應(yīng)該?。簄)1)(2010(),2010(nN訓(xùn)練樣品4。二分法能力（續(xù)）信息工程學(xué)院*2-4、廣義線性判別函數(shù)kixfwwxfwxfwxfwxgkiiikkk,.,2 , 1, )()(.)()()(1112211v這樣一個(gè)非線性判別函數(shù)通過(guò)映射，變換成線性判別函數(shù)。1)(,)(1xfxfki是單值函數(shù)式中v判別函數(shù)的一般形式：2111,0,0)()()(xxYgYWxfwxgTyxkiii空間變換空間信息工程學(xué)院*0YWT判別平面：)( ,)(.)()()( ,., 0, 0)()()(21212111增廣模式向量。廣義權(quán)向量其中：空間變換空間x

18、fxfxfYwwwWxxYgYWxfwxgkkTyxkiii2-4、廣義線性判別函數(shù)（續(xù)）21,xaxbxbxorax則則v例：如右圖。0bax二次判別函數(shù)212信息工程學(xué)院*2321212123211,0,0)()(,0,0)(xxYaaaWxxYgYWxgxxxaxaaxgT映射：2-4、廣義線性判別函數(shù)（續(xù)）v要用二次判別函數(shù)才可把二類分開(kāi)：)1 , 1, 1()25.0 ,5 .0 , 1(),0 ,0 , 1(321yyy05 .011y3y2yW平面oYWT212x信息工程學(xué)院*015 . 012)(1,2112, 1, 12123212321321YWYxxxxxgyyyxxYa

19、aaWaaaxT空間判別平面：即：空間它的判別邊界：設(shè)討論在推出2-4、廣義線性判別函數(shù)（續(xù)）v從圖可以看出：在陰影上面是1類，在陰影下面是2類，v結(jié)論：在X空間的非線性判別函數(shù)通過(guò)變換到Y(jié)空間成為線性的，但X變?yōu)楦呔S空間05.011y3y2yW平面oYWT212x信息工程學(xué)院*v1.分段線性判別函數(shù)分段線性判別函數(shù)（用線性無(wú)法分開(kāi),可用分段線性判別函數(shù)） 、基于距離的分段線性判別函數(shù)基于距離的分段線性判別函數(shù)。（用均值代表一類，通過(guò)均值連線中點(diǎn)的垂直線分開(kāi)） 把i類可以分成li個(gè)子類: 分成l個(gè)子類?，F(xiàn)在定義子類判別函數(shù)：在同類的子類中找最近的均值。判別規(guī)則：這是在M類中找最近均值。則把x歸

20、于j類完成分類。),.,(21liiii2-5、非線性判別函數(shù) 2 :線性判別 ：分段線性判別 ：二次判別 11lillixxg,.,2,1min)(Mixgxgij,.,2 , 1),(min)(信息工程學(xué)院*2-5、非線性判別函數(shù)（續(xù)）v例：未知x,如圖：v先與1類各子類的均值比較，即 ，找一個(gè)最近的 與2各子類均值比較取最近的 因g2(x) g1(x) ，所以x2類 。 211)( xxglx1322)( xxg22123221111112322221x信息工程學(xué)院*v設(shè) 1, 2 ,mv而每一類又可以分為 子類。v對(duì)每個(gè)子類定義一個(gè)線性判別函數(shù)為：v則定義i類的線性判別函數(shù)為：、基于函

21、數(shù)的分段線性判別函數(shù) 利用均值代表一類有時(shí)有局限性，如圖所示。若用 線性判別函數(shù)代表一類，就會(huì)克服上述情況。121x2xx1、分段線性判別函數(shù)),.,(21liiii子類的權(quán)向量。為其中l(wèi)ilililiwxwxg,)()(max)(,.,2, 1xgxglilli信息工程學(xué)院*v在各子類中找最大的判別函數(shù)作為此類的代表，則對(duì)于M類，可定義M個(gè)判別函數(shù)gi(x),i=1,2,.M,因此，決策規(guī)則：v對(duì)未知模式x，把x先代入每類的各子類的判別函數(shù)中，找出一個(gè)最大的子類判別函數(shù)，M類有M個(gè)最大子類判別函數(shù)，在M個(gè)子類最大判別函數(shù)中，再找一個(gè)最大的，則x就屬于最大的子類判別函數(shù)所屬的那一類。jiMij

22、xxgxg則),(max)(,.,2, 11、分段線性判別函數(shù)（續(xù)）信息工程學(xué)院*、基于凹函數(shù)的并分段線性判別函數(shù)（針對(duì)多峰情況） 設(shè)li子類判別函數(shù)，i=1,2,.r則分段線性判別函數(shù)有如下特性：1、分段線性判別函數(shù)（續(xù)）v(a)：l1,l2,lr都是分段線性判別函數(shù)v(b)：若A,B都是分段線性判別函數(shù)，則： AB ，AB也是分段線性判別函數(shù)。 AB取最小 ，AB取最大。v(c)：對(duì)任何分段線性函數(shù)都可以表示成如下二種形式：v1)、析取范式(這是經(jīng)常采用的形式)P=(L11L12L1m)(Lq1Lq2Lqm)v2)、合取范式Q= (L11 L12 L1m) (Lq1 Lq2 Lqm)v每個(gè)(L11 L12 L1m) 都稱為凹函數(shù)。信息工程學(xué)院*。每個(gè)子類的判別函數(shù)數(shù)子類。mjxqixxwLijij,.,2 , 1, 0,.,2 , 1, 0211、分段線性判別函數(shù)（續(xù)）v對(duì)于多峰二類問(wèn)題：設(shè)第一類有q個(gè)峰，則有q個(gè)凹函數(shù)。v即P=P1P2Pqv每個(gè)凹函數(shù)Pi由m 個(gè)線性判別函數(shù)來(lái)構(gòu)成。vPi=Li1Li2Limv假設(shè)對(duì)于每個(gè)子類線性判別函數(shù)Lij都設(shè)計(jì)成：21, 0, 0 xPxP則則判別規(guī)則：信息工程學(xué)院*v例、設(shè)