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

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

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

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

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

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

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

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

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

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

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

12、第26頁/共56頁第二十七頁，共57頁。v這是一個不等式方程組，它的解 處于由1類所有模式決定的平面的正邊和由2類所有模式決定的平面的負邊，它的解區即為凸多面錐。v如圖所示：(b)為加權空間，（c）為正規化后的加權空間。v由上可以得到結論：加權空間的所有分界面都通過坐標原點。這是加權空間的性質。v為了更清楚(qng chu)，下面用二維權空間來表示解向量和解區。1、模式(msh)空間與加權空間（續）TwwwW),(321第27頁/共56頁第二十八頁，共57頁。2、解向量(xingling)和解區0)(XWxgT1w2w1x4x3x2x解區W解向量分界面H解向量與解區第28頁/共56頁第二十九頁

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

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

15、投影 正比(zhngb)與g(x)的函數值。r第33頁/共56頁第三十四頁，共57頁。WWqqrHxxqWWWxgrxwwxWxgnnnnT11110)()0()(的投影為到時因因原點因為成正比的距離與原點到11nnWH,WWqv性質(xngzh)：3、超平面的幾何(j h)性質（續）q2X1X0H第34頁/共56頁第三十五頁，共57頁。v性質(xngzh)：通過原點。，說明超平面則若在原點負側。則在原點正側，若則若HxWxgWHWHWTnnn)(, 0, 0, 0111否則，反之。的正側，在代數距離。到正比于來決定。的位置由超平面決定正交，方向由的平面與）超平面（結論：, 0)()()()(

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

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

18、6頁第三十九頁，共57頁。),(nNP0 .15 .00543211n5n15nn1nN強。說明樣本少時二分能力范圍，即在。時，線性可分概率為時，即值，對于任意。處出現明顯的門限效應時，曲線急劇下降，在由當, 1),(),1(22: )(21),() 1(22: )(21: )(nNPnNcnNPnNnbnav把上式用曲線表示(biosh)成下圖：圖中橫坐標用=N/n+1表示(biosh)。v由圖討論：4。二分法能力(nngl)（續）第39頁/共56頁第四十頁，共57頁。.2),1(2: )(,),1(22: )(0是最好情況即二分能力）的估計：個樣本的線性可分性（對多線性可分能力越差。說明樣

19、品越線性可分概率急劇下降范圍，即在nNNenNd),(nNP0 . 15 . 00543211n5n15nn1nNv結論：在實際工作中，分類的訓練(xnlin)非常重要，由已知樣本來訓練(xnlin)。因為已知樣本有限，而未知樣本無限。選擇已知類別的訓練(xnlin)樣本數方法如下：4。二分法能力(nngl)（續）第40頁/共56頁第四十一頁，共57頁。v：如果訓練樣本N N0，設計分類器的分類能力(nngl)太差，因為訓練樣本太少。v：如果訓練樣本N太多時，則樣本太多，運算量、存儲量太大。v：因此實際工作中應該取：v)1)(2010(),2010(nN訓練樣品4。二分法能力(nngl)（續）

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

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

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

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

24、lilli第48頁/共56頁第四十九頁，共57頁。v在各子類中找最大的判別函數作為此類的代表，則對于M類，可定義M個判別函數gi(x),i=1,2,.M,因此，決策規則：v對未知模式x，把x先代入每類的各子類的判別函數中，找出一個最大的子類判別函數，M類有M個最大子類判別函數，在M個子(g zi)類最大判別函數中，再找一個最大的，則x就屬于最大的子類判別函數所屬的那一類。jiMijxxgxg則),(max)(,.,2, 11、分段(fn dun)線性判別函數（續）第49頁/共56頁第五十頁，共57頁。1、分段(fn dun)線性判別函數（續）v(a)：l1,l2,lr都是分段線性判別函數v(b

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

26、q個峰，則有q個凹函數。v即P=P1P2Pqv每個凹函數Pi由m 個線性判別函數來構成。vPi=Li1Li2Limv假設對于每個子類線性判別函數Lij都設計成：21, 0, 0 xPxP則則判別規則：第51頁/共56頁第五十二頁，共57頁。個分段判別函數有判別函數個數：這樣它有三個子類。分三個峰，1344533211mmmq。則。若則若2134312421151211, 0, 0),.,min(),.,min(),.,min(maxxPxPlllllllP15l11l12l13l14l22l24l23l21l34l33l32l31l11213121、分段(fn dun)線性判別函數（續）P=(L11