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

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

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

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

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

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

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

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

9、wxwxg1、模式空間與加權空間Txxx),(1211123422411332231100wxwxwwxwxw13222211312211100wxwxwwxwxw243121,xxxx設：最終形成圖多面錐210)(xxxg32211)(wxwxwxg信息工程學院*v這是一個不等式方程組，它的解 處于由1類所有模式決定的平面的正邊和由2類所有模式決定的平面的負邊，它的解區即為凸多面錐。v如圖所示：(b)為加權空間，（c）為正規化后的加權空間。v由上可以得到結論：加權空間的所有分界面都通過坐標原點。這是加權空間的性質。v為了更清楚，下面用二維權空間來表示解向量和解區。1、模式空間與加權空間（續）

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

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

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

13、g(x)的函數值。r信息工程學院*WWqqrHxxqWWWxgrxwwxWxgnnnnT11110)()0()(的投影為到時因因原點因為成正比的距離與原點到11nnWH,WWqv性質：3、超平面的幾何性質（續）q2X1X0H信息工程學院*v性質：通過原點。，說明超平面則若在原點負側。則在原點正側，若則若HxWxgWHWHWTnnn)(, 0, 0, 0111否則，反之。的正側，在代數距離。到正比于來決定。的位置由超平面決定正交，方向由的平面與）超平面（結論：, 0)()()()(1xgHxHxxgcWHbWWHan3、超平面的幾何性質（續）信息工程學院*v一組模式樣本不一定是線性可分的，所以需

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

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

16、把上式用曲線表示成下圖：圖中橫坐標用=N/n+1表示。v由圖討論：4。二分法能力（續）信息工程學院*.2),1(2: )(,),1(22: )(0是最好情況即二分能力）的估計：個樣本的線性可分性（對多線性可分能力越差。說明樣品越線性可分概率急劇下降范圍，即在nNNenNd),(nNP0 . 15 .00543211n5n15nn1nNv結論：在實際工作中，分類的訓練非常重要，由已知樣本來訓練。因為已知樣本有限，而未知樣本無限。選擇已知類別的訓練樣本數方法如下：4。二分法能力（續）信息工程學院*v：如果訓練樣本N N0，設計分類器的分類能力太差，因為訓練樣本太少。v：如果訓練樣本N太多時，則樣本

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

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

19、aaWaaaxT空間判別平面：即：空間它的判別邊界：設討論在推出2-4、廣義線性判別函數（續）v從圖可以看出：在陰影上面是1類，在陰影下面是2類，v結論：在X空間的非線性判別函數通過變換到Y空間成為線性的，但X變為高維空間05.011y3y2yW平面oYWT212x信息工程學院*v1.分段線性判別函數分段線性判別函數（用線性無法分開,可用分段線性判別函數） 、基于距離的分段線性判別函數基于距離的分段線性判別函數。（用均值代表一類，通過均值連線中點的垂直線分開） 把i類可以分成li個子類: 分成l個子類。現在定義子類判別函數：在同類的子類中找最近的均值。判別規則：這是在M類中找最近均值。則把x歸

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

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

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