1、會(huì)計(jì)學(xué)1判別函數(shù)線性判別函數(shù)線性判別函數(shù)的判別函數(shù)線性判別函數(shù)線性判別函數(shù)的第一頁(yè)，共57頁(yè)。v假設(shè)對(duì)一模式X已抽取n個(gè)特征(tzhng)，表示為：v模式識(shí)別問題就是根據(jù)模式X的n個(gè)特征(tzhng)來(lái)判別模式屬于1 ,2 , , m 類中的那一類。 2-1 判別函數(shù) 維空間的一個(gè)向量是n),.,(321XxxxxXTn第1頁(yè)/共56頁(yè)第二頁(yè)，共57頁(yè)。v例如下圖：三類的分類問題，它們的邊界線就是(jish)一個(gè)判別函數(shù)123邊界2x1x2.1 判別函數(shù)（續(xù)）第2頁(yè)/共56頁(yè)第三頁(yè)，共57頁(yè)。v判別函數(shù)包含兩類：v一類 是線性判別函數(shù)：v線性判別函數(shù)v廣義線性判別函數(shù)v （所謂廣義線性判別函數(shù)

2、就是把非線性判別函數(shù)映射到另外一個(gè)空間(kngjin)變成線性判別函數(shù)）v分段線性判別函數(shù)v另一類是非線性判別函數(shù)2.1 判別函數(shù)（續(xù)）第3頁(yè)/共56頁(yè)第四頁(yè)，共57頁(yè)。2,),(21MTi2,)(2,1nxxXT32211wxwxw)x(g為坐標(biāo)向量為參數(shù)，21, xxw第4頁(yè)/共56頁(yè)第五頁(yè)，共57頁(yè)。v在兩類別(libi)情況，判別函數(shù) g (x) 具有以下性質(zhì)：v這是二維情況下判別由判別邊界分類.v情況如圖：1. 二維情況(qngkung)21, 0, 0)(XXxgi不定Xxg,0)(32211)(wxwxwxg211x2x第5頁(yè)/共56頁(yè)第六頁(yè)，共57頁(yè)。TnxxxxX),.,(3

3、2112211.)(nnnwxwxwxwxg10nwXW為增值模式向量。，為增值權(quán)向量，TnnTnnxxxxXwwwwW) 1,.,(),.,(21121XWxgT)(為模式向量。為權(quán)向量，TnTnxxxXwwwW),.,(),.,(21210第6頁(yè)/共56頁(yè)第七頁(yè)，共57頁(yè)。v模式(msh)分類：v當(dāng) g1(x) =WTX=0 為判別邊界 。當(dāng)n=2時(shí)，二維情況的判別邊界為一直線。當(dāng)n=3時(shí)，判別邊界為一平面，n3時(shí)，則判別邊界為一超平面。21,0,0)(xxXWxgT2. n維情況(qngkung)第7頁(yè)/共56頁(yè)第八頁(yè)，共57頁(yè)。其它MiXXWxgiTii,.,2 , 1, 0, 0)(

4、v對(duì)于多類問題，模式有 1 ,2 , , m 個(gè)類別(libi)。可分三種情況：v1。第一種情況：每一模式類與其它模式類間可用單個(gè)判別平面把一個(gè)類分開。這種情況，M類可有M個(gè)判別函數(shù)，且具有以下性質(zhì)：權(quán)向量。個(gè)判別函數(shù)的為第式中iwwwwWTininiii) ,.,(121第8頁(yè)/共56頁(yè)第九頁(yè)，共57頁(yè)。v右圖所示，每一類別可用單個(gè)判別邊界與其它類別相分開 。v如果一模式X屬于(shy)1，則由圖可清楚看出:這時(shí)g1(x) 0而g2(x) 0 ， g3(x) 0 ， g2(x) 0 ， g3(x) 0 。則此模式X就無(wú)法作出確切的判決。如圖中 IR1,IR3，IR4區(qū)域。v另一種情況是IR2

5、區(qū)域，判別函數(shù)都為負(fù)值。IR1，IR2，IR3，IR4。都為不確 定區(qū)域。1。第一種情況(qngkung)（續(xù)）30)(0)(0)(321xgxgxg12000321)x(g)x(g)x(g0)(0)(0)(321xgxgxg 4IR3IR1IR2IR1x2x0)(1xg0)(2xg0)(3xg551第13頁(yè)/共56頁(yè)第十四頁(yè)，共57頁(yè)。:代入判別函數(shù)方程組1)(5)()(23212211xxgxxxgxxxg.4)(,6)(, 1)(321xgxgxg得：1。第一種情況(qngkung)（續(xù)）第14頁(yè)/共56頁(yè)第十五頁(yè)，共57頁(yè)。v這樣 有 M(M _ 1)/2個(gè)判別平面。v對(duì)于兩類問題(w

6、nt)，M=2，則有一個(gè)判別平面。v同理，三類問題(wnt)則有三個(gè)判別平面。jixgijjix0 x0)(當(dāng)當(dāng)2。第二種情況(qngkung)：XW)x(gTijijo)x(gij每個(gè)模式類和其它模式類間可分別用判別平面分開。20)(12xg0)(23xg0)(13xg 3 1第15頁(yè)/共56頁(yè)第十六頁(yè)，共57頁(yè)。0)(03)(05)(21231132112xxxgxxgxxxg21231132112)(3)(5)(xxxgxxgxxxgv判別函數(shù)性質(zhì)(xngzh)：v假設(shè)判別函數(shù)為：v判別(pnbi)邊界為：2。第二種情況(qngkung)（續(xù)）v用方程式作圖：)()(xgxgjiij0,

7、023122gg判別區(qū)012)x(g 023)x(g013)x(g 5531x0032313gg判別區(qū)0012121gg判別區(qū)2x第16頁(yè)/共56頁(yè)第十七頁(yè)，共57頁(yè)。v結(jié)論：判別區(qū)間增大(zn d)，不確定 區(qū)間減小，比第一種情況小的多.1)(, 1)(,2)(231312xgxgxg1)(, 1)(, 2)(323121xgxgxg0)(3xgj2。第二種情況（續(xù)）0023122gg判別區(qū)0012121gg判別區(qū)0)(12xg 0)(23xg0)(13xg 5530032313gg判別區(qū)1x2x第17頁(yè)/共56頁(yè)第十八頁(yè)，共57頁(yè)。XWxgKk)(MK,.,2 , 1小，其它最大，當(dāng)iTk

8、ixXWxg)(v每類都有一個(gè)(y )判別函數(shù),存在M個(gè)判別函數(shù)第18頁(yè)/共56頁(yè)第十九頁(yè)，共57頁(yè)。v右圖所示是M=3 的例子(l zi)。對(duì)于1類模式，v必然滿足g1(x) g2(x) 和 g1(x) g3(x) 。v假設(shè)判別函數(shù)為：v則判別邊界為：23212211)(1)()(xxgxxxgxxxg012)()(02)()(012)()(21322131121xxxgxgxxxgxgxxgxg2)()(21xgxg)()(32xgxg)()(31xgxg133。第三種情況(qngkung)（續(xù)）第19頁(yè)/共56頁(yè)第二十頁(yè)，共57頁(yè)。v用上列(shngli)方程組作圖如下：1)()()()

9、(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05.0第20頁(yè)/共56頁(yè)第二十一頁(yè)，共57頁(yè)。v問假設(shè)未知模式(msh)x= (x1,x2)T= (1,1)T ，則x屬于那一類。v把它代入判別函數(shù)：v得判別函數(shù)為：v因?yàn)関所以模式(msh)x= (1,1)T屬于 類。3。第三種情況(qngkung)（續(xù)）2)()(),()(1232xgxgxgxg1)(, 1)(, 0)(321xgxgxg).(),(),(321xgxgxg1)()()()(3121xg

10、xgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32xgxg0)()(21xgxg0)()(31xgxg0.15.05 . 0第21頁(yè)/共56頁(yè)第二十二頁(yè)，共57頁(yè)。XWxgTi)(TnxxxxX),.,(321121,.,nwww模式空間 2X1X121x3x4x0)(xg邊界2xHW第22頁(yè)/共56頁(yè)第二十三頁(yè)，共57頁(yè)。模式(msh)空間第23頁(yè)/共56頁(yè)第二十四頁(yè)，共57頁(yè)。加權(quán)空間判別界面第24頁(yè)/共56頁(yè)第二十五頁(yè)，共57頁(yè)。1、模式(msh)空間與加權(quán)空間（續(xù)）第25頁(yè)/共56頁(yè)第二十六頁(yè)，共57頁(yè)。v該式表示(biosh

11、)一個(gè)通過加權(quán)空間原點(diǎn)的平面，此平面就是加權(quán)空間圖中的平面,同樣令g (x2) =g (x3) =g (x4)=0，分別作出通過加權(quán)空間原點(diǎn)的平面圖中用陰影表示(biosh)的部分是各平面的正側(cè)。v加權(quán)空間(kngjin)的構(gòu)造：v設(shè) 是加權(quán)空間(kngjin)分界面上的一點(diǎn)，代入上式得：這是加權(quán)空間的邊界, 0)(31221111wxwxwxg1、模式(msh)空間與加權(quán)空間Txxx),(1211123422411332231100wxwxwwxwxw13222211312211100wxwxwwxwxw243121,xxxx設(shè)：最終形成圖多面錐210)(xxxg32211)(wxwxwxg

12、第26頁(yè)/共56頁(yè)第二十七頁(yè)，共57頁(yè)。v這是一個(gè)不等式方程組，它的解 處于由1類所有模式?jīng)Q定的平面的正邊和由2類所有模式?jīng)Q定的平面的負(fù)邊，它的解區(qū)即為凸多面錐。v如圖所示：(b)為加權(quán)空間，（c）為正規(guī)化后的加權(quán)空間。v由上可以得到結(jié)論：加權(quán)空間的所有分界面都通過坐標(biāo)原點(diǎn)。這是加權(quán)空間的性質(zhì)。v為了更清楚(qng chu)，下面用二維權(quán)空間來(lái)表示解向量和解區(qū)。1、模式(msh)空間與加權(quán)空間（續(xù)）TwwwW),(321第27頁(yè)/共56頁(yè)第二十八頁(yè)，共57頁(yè)。2、解向量(xingling)和解區(qū)0)(XWxgT1w2w1x4x3x2x解區(qū)W解向量分界面H解向量與解區(qū)第28頁(yè)/共56頁(yè)第二十九頁(yè)

13、，共57頁(yè)。v把不等式方程(fngchng)正規(guī)化：v正規(guī)化：00003422411332231132222113122111wxwxwwxwxwwxwxwwxwxw) ,.,(0)(121nnTiwwwwWXWxg2、解向量(xingling)的解區(qū)（續(xù)）1w2w1x4x3x2x解區(qū)解向量分界面H3x4x正規(guī)化第29頁(yè)/共56頁(yè)第三十頁(yè)，共57頁(yè)。上矢量一定在HxxxxWwxWwxWTnTnT)( , 0)(0212112113、超平面的幾何(j h)性質(zhì)第30頁(yè)/共56頁(yè)第三十一頁(yè)，共57頁(yè)。1x2X1X2xWH12g(x)0g(x)03、超平面的幾何(j h)性質(zhì)第31頁(yè)/共56頁(yè)第三十

14、二頁(yè)，共57頁(yè)。v 矢量(shling)到H的正交投影 與 值成正比v其中： x p： x在H 的投影(tuyng)向量，vr是x 到H 的垂直距離。v 是W方向的單位向量。3、超平面的幾何(j h)性質(zhì)（續(xù)）W)x(grv性質(zhì) ：WWrxrxxpp)(xgxrWWq2X1XpxWxHpr第32頁(yè)/共56頁(yè)第三十三頁(yè)，共57頁(yè)。v另一方面:11)()(npTnTwrxWwxWxg1nTpTwrWxW)(,)()()(021WWWrWxgrWrWWWrWWrWrWxgwxWHpTTTTnpT是投影的絕對(duì)值上。在因?yàn)?、超平面的幾何(j h)性質(zhì)（續(xù)）v這是超平面的第二個(gè)性質(zhì)，矢量x到超平面的正交

15、投影 正比(zhngb)與g(x)的函數(shù)值。r第33頁(yè)/共56頁(yè)第三十四頁(yè)，共57頁(yè)。WWqqrHxxqWWWxgrxwwxWxgnnnnT11110)()0()(的投影為到時(shí)因因原點(diǎn)因?yàn)槌烧鹊木嚯x與原點(diǎn)到11nnWH,WWqv性質(zhì)(xngzh)：3、超平面的幾何(j h)性質(zhì)（續(xù)）q2X1X0H第34頁(yè)/共56頁(yè)第三十五頁(yè)，共57頁(yè)。v性質(zhì)(xngzh)：通過原點(diǎn)。，說(shuō)明超平面則若在原點(diǎn)負(fù)側(cè)。則在原點(diǎn)正側(cè)，若則若HxWxgWHWHWTnnn)(, 0, 0, 0111否則，反之。的正側(cè)，在代數(shù)距離。到正比于來(lái)決定。的位置由超平面決定正交，方向由的平面與）超平面（結(jié)論：, 0)()()()(

16、1xgHxHxxgcWHbWWHan3、超平面的幾何(j h)性質(zhì)（續(xù)）第35頁(yè)/共56頁(yè)第三十六頁(yè)，共57頁(yè)。v一組模式樣本不一定是線性可分的，所以需要(xyo)研究線性分類能力的方法，對(duì)任何容量為N的樣本集，線性可分的概率多大呢？v（如下圖（a），線性不可分）v例：4個(gè)樣本有幾種分法。v圖（b）直線把x1分開，每條直線可把4個(gè)樣本分成1 2 類，4個(gè)樣本分成二類的總的可能的分法為24=16類，其中有二種是不能用線性分類實(shí)現(xiàn)的線性可分的是14。即概率為14/16。4。二分法能力(nngl)（a）x1x2x3x4 （b）第36頁(yè)/共56頁(yè)第三十七頁(yè)，共57頁(yè)。v結(jié)論(jiln)：N個(gè)樣品線性可

17、分?jǐn)?shù)目(條件：樣本分布良好）：4。二分法能力(nngl)（續(xù)）為特征數(shù)為樣本數(shù)其中nNkNkNCkN,)!1( !)!1(1nkkNNnNCnNnND011,21,2),(若若v對(duì)N和n各種組合的D(N,n)值，表示在下表中，從表中可看出，當(dāng)N，n緩慢(hunmn)增加時(shí)D(N,n)卻增加很快。第37頁(yè)/共56頁(yè)第三十八頁(yè)，共57頁(yè)。12345612222222444444368888848141616161651022303232324。二分法能力(nngl)（續(xù)）n),(nNDNnkkNNNnNCnNnNDnNP0111,21, 12),(),(若若v線性可分概率(gil)：第38頁(yè)/共5

18、6頁(yè)第三十九頁(yè)，共57頁(yè)。),(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把上式用曲線表示(biosh)成下圖：圖中橫坐標(biāo)用=N/n+1表示(biosh)。v由圖討論：4。二分法能力(nngl)（續(xù)）第39頁(yè)/共56頁(yè)第四十頁(yè)，共57頁(yè)。.2),1(2: )(,),1(22: )(0是最好情況即二分能力）的估計(jì)：個(gè)樣本的線性可分性（對(duì)多線性可分能力越差。說(shuō)明樣

19、品越線性可分概率急劇下降范圍，即在nNNenNd),(nNP0 . 15 . 00543211n5n15nn1nNv結(jié)論：在實(shí)際工作中，分類的訓(xùn)練(xnlin)非常重要，由已知樣本來(lái)訓(xùn)練(xnlin)。因?yàn)橐阎獦颖居邢蓿粗獦颖緹o(wú)限。選擇已知類別的訓(xùn)練(xnlin)樣本數(shù)方法如下：4。二分法能力(nngl)（續(xù)）第40頁(yè)/共56頁(yè)第四十一頁(yè)，共57頁(yè)。v：如果訓(xùn)練樣本N N0，設(shè)計(jì)分類器的分類能力(nngl)太差，因?yàn)橛?xùn)練樣本太少。v：如果訓(xùn)練樣本N太多時(shí)，則樣本太多，運(yùn)算量、存儲(chǔ)量太大。v：因此實(shí)際工作中應(yīng)該取：v)1)(2010(),2010(nN訓(xùn)練樣品4。二分法能力(nngl)（續(xù)）

20、第41頁(yè)/共56頁(yè)第四十二頁(yè)，共57頁(yè)。kixfwwxfwxfwxfwxgkiiikkk,.,2 , 1, )()(.)()()(1112211v這樣一個(gè)非線性判別函數(shù)通過映射(yngsh)，變換成線性判別函數(shù)。1)(,)(1xfxfki是單值函數(shù)式中v判別函數(shù)的一般(ybn)形式：2111,0,0)()()(xxYgYWxfwxgTyxkiii空間變換空間第42頁(yè)/共56頁(yè)第四十三頁(yè)，共57頁(yè)。0YWT判別平面：)( ,)(.)()()( ,., 0, 0)()()(21212111增廣模式向量。廣義權(quán)向量其中：空間變換空間xfxfxfYwwwWxxYgYWxfwxgkkTyxkiii2-4

21、、廣義(gungy)線性判別函數(shù)（續(xù)）21,xaxbxbxorax則則v例：如右圖。0bax二次判別函數(shù)212第43頁(yè)/共56頁(yè)第四十四頁(yè)，共57頁(yè)。2321212123211,0,0)()(,0,0)(xxYaaaWxxYgYWxgxxxaxaaxgT映射：2-4、廣義(gungy)線性判別函數(shù)（續(xù)）v要用二次判別函數(shù)才可把二類(r li)分開：)1 , 1, 1()25.0 ,5 .0 , 1(),0 ,0 , 1(321yyy05.011y3y2yW平面oYWT212x第44頁(yè)/共56頁(yè)第四十五頁(yè)，共57頁(yè)。015 . 012)(1,2112, 1, 12123212321321YWYx

22、xxxxgyyyxxYaaaWaaaxT空間判別平面：即：空間它的判別邊界：設(shè)討論在推出2-4、廣義(gungy)線性判別函數(shù)（續(xù)）v從圖可以看出(kn ch)：在陰影上面是1類，在陰影下面是2類，v結(jié)論：在X空間的非線性判別函數(shù)通過變換到Y(jié)空間成為線性的，但X變?yōu)楦呔S空間05.011y3y2yW平面oYWT212x第45頁(yè)/共56頁(yè)第四十六頁(yè)，共57頁(yè)。),.,(21liiii2-5、非線性判別函數(shù) 2 :線性判別 ：分段線性判別 ：二次判別 11lillixxg,.,2,1min)(Mixgxgij,.,2 , 1),(min)(第46頁(yè)/共56頁(yè)第四十七頁(yè)，共57頁(yè)。2-5、非線性判別函

23、數(shù)（續(xù)）v例：未知x,如圖：v先與1類各子類的均值(jn zh)比較，即 ，找一個(gè)最近的 與2各子類均值(jn zh)比較取最近的 因g2(x) g1(x) ，所以x2類 。 211)( xxglx1322)( xxg22123221111112322221x第47頁(yè)/共56頁(yè)第四十八頁(yè)，共57頁(yè)。v設(shè) 1, 2 ,mv而每一類又可以分為 子類。v對(duì)每個(gè)子類定義(dngy)一個(gè)線性判別函數(shù)為：v則定義(dngy)i類的線性判別函數(shù)為：121x2xx1、分段(fn dun)線性判別函數(shù)),.,(21liiii子類的權(quán)向量。為其中l(wèi)ilililiwxwxg,)()(max)(,.,2, 1xgxg

24、lilli第48頁(yè)/共56頁(yè)第四十九頁(yè)，共57頁(yè)。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è)子(g zi)類最大判別函數(shù)中，再找一個(gè)最大的，則x就屬于最大的子類判別函數(shù)所屬的那一類。jiMijxxgxg則),(max)(,.,2, 11、分段(fn dun)線性判別函數(shù)（續(xù)）第49頁(yè)/共56頁(yè)第五十頁(yè)，共57頁(yè)。1、分段(fn dun)線性判別函數(shù)（續(xù)）v(a)：l1,l2,lr都是分段線性判別函數(shù)v(b

25、)：若A,B都是分段線性判別函數(shù)，則： AB ，AB也是分段線性判別函數(shù)。 AB取最小 ，AB取最大。v(c)：對(duì)任何分段線性函數(shù)都可以表示成如下(rxi)二種形式：v1)、析取范式(這是經(jīng)常采用的形式)P=(L11L12L1m)(Lq1Lq2Lqm)v2)、合取范式Q= (L11 L12 L1m) (Lq1 Lq2 Lqm)v每個(gè)(L11 L12 L1m) 都稱為凹函數(shù)。第50頁(yè)/共56頁(yè)第五十一頁(yè)，共57頁(yè)。每個(gè)子類的判別函數(shù)數(shù)子類。mjxqixxwLijij,.,2 , 1, 0,.,2 , 1, 0211、分段(fn dun)線性判別函數(shù)（續(xù)）v對(duì)于多峰二類(r li)問題：設(shè)第一類有

26、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ī)則：第51頁(yè)/共56頁(yè)第五十二頁(yè)，共57頁(yè)。個(gè)分段判別函數(shù)有判別函數(shù)個(gè)數(shù)：這樣它有三個(gè)子類。分三個(gè)峰，1344533211mmmq。則。若則若2134312421151211, 0, 0),.,min(),.,min(),.,min(maxxPxPlllllllP15l11l12l13l14l22l24l23l21l34l33l32l31l11213121、分段(fn dun)線性判別函數(shù)（續(xù)）P=(L11