武漢大學(xué)電子信息學(xué)院

1、IPL第四章 線性判別函數(shù) 模式識別 Pattern Recognition內(nèi)容目錄IPL第四章 線性判別函數(shù)67 4.2 Fisher線性判別34.3 感知器準(zhǔn)則4.5 多類問題4.6 分段線性判別函數(shù) 5 4.1 引言144.4 最小平方誤差準(zhǔn)則模式識別與神經(jīng)網(wǎng)絡(luò)4.7 討論24.1 引言基于樣本的Bayes分類器：通過估計類條件概率密度函數(shù)，設(shè)計相應(yīng)的判別函數(shù)MAXg1.g2gc.x1x2xna(x)最一般情況下適用的“最優(yōu)”分類器：錯誤率最小，對分類器設(shè)計在理論上有指導(dǎo)意義。獲取統(tǒng)計分布及其參數(shù)很困難，實際問題中并不一定具備獲取準(zhǔn)確統(tǒng)計分布的條件。 訓(xùn)練樣本集樣本分布的統(tǒng)計特征：概率密

2、度函數(shù)決策規(guī)則：判別函數(shù)決策面方程分類器功能結(jié)構(gòu)3 Classification is viewed as “l(fā)earning good decision boundaries” that separate the examples belonging to different classes in a data set.決策邊界的估計4決策邊界的估計Specify a parametric form of the decision boundary (e.g., linear or quadratic) .Find the “best” decision boundary of the sp

3、ecified form using a set of training examples. This is done by minimizing a criterion functione.g., “training error” (or “sample risk”)5直接確定判別函數(shù)基于樣本的直接確定判別函數(shù)方法：設(shè)定判別函數(shù)形式，用樣本集確定參數(shù)。使用準(zhǔn)則函數(shù)，表達(dá)分類器應(yīng)滿足的要求。這些準(zhǔn)則的“最優(yōu)”并不一定與錯誤率最小相一致：次優(yōu)分類器。 實例：正態(tài)分布最小錯誤率貝葉斯分類器在特殊情況下，是線性判別函數(shù)g(x)=wTx（決策面是超平面），能否基于樣本直接確定w?引言訓(xùn)練樣本集決策規(guī)則

4、：判別函數(shù)決策面方程選擇最佳準(zhǔn)則6線性判別函數(shù)d維空間中的線性判別函數(shù)的一般形式：x是樣本向量，即樣本在d維特征空間中的描述， w是權(quán)向量，w0是一個常數(shù)(閾值權(quán))。引言7兩類問題的分類決策規(guī)則引言8If g(x) is linear, the decision boundary is a hyperplane. The orientation of the hyperplane is determined by w and its location by w0.w is the normal to the hyperplane.If w0=0, the hyperplane passes t

5、hrough the origin.線性判別函數(shù)的幾何意義9線性判別函數(shù)的幾何意義g(x) provides an algebraic measure of the distance of x from the hyperplane.specifiesdirectionof r10線性判別函數(shù)的幾何意義Substitute the above expression in g(x):This gives the distance of x from the hyperplane:w0 determines the distance of the hyperplane from the origi

6、n:11線性判別函數(shù)的幾何意義決策面(decision boundary)H方程：g(x)=0向量w是決策面H的法向量g(x)是點(diǎn)x到?jīng)Q策面H的距離的一種代數(shù)度量引言x1x2wxxprH: g=0R1: g0R2: g d )16廣義線性判別函數(shù)The resulting discriminant function is not linear in x but it is linear in y. The generalized discriminant separates points in the transformed space by a hyperplane passing thro

7、ugh the origin.17廣義線性判別函數(shù) Example:Maps a line in x-space to a parabola in y-space.The plane aty=0 divides the y-space in two decision regions The corresponding decision regions R1,R2 in the x-space are not simply connected! functions18廣義線性判別函數(shù)19廣義線性判別函數(shù)Practical issues.Computationally intensive.Lots

8、 of training examples are required to determine a if is very large (i.e.,curse of dimensionality).Example: A Full quadratics, the dimension of Y space is: 20廣義線性判別函數(shù)一種特殊映射方法：增廣樣本向量y與增廣權(quán)向量a21廣義線性判別函數(shù)(4)增廣樣本向量使特征空間增加了一維，但保持了樣本間的歐氏距離不變，對于分類效果也與原決策面相同，只是在Y空間中決策面是通過坐標(biāo)原點(diǎn)的，這在分析某些問題時具有優(yōu)點(diǎn)，因此經(jīng)常用到。 引言線性判別函數(shù)的齊次

9、簡化：22線性分類器設(shè)計步驟線性分類器設(shè)計任務(wù)：給定樣本集K，確定線性判別函數(shù)g(x)=wTx的各項系數(shù)w。步驟：收集一組樣本K=x1,x2,xN按需要確定一準(zhǔn)則函數(shù)J(K,w)，其值反映分類器的性能，其極值解對應(yīng)于“最好”決策。用最優(yōu)化技術(shù)求準(zhǔn)則函數(shù)J的極值解w*，從而確定判別函數(shù)，完成分類器設(shè)計。對于未知樣本x，計算g(x)，判斷其類別。引言234.2 Fisher線性判別線性判別函數(shù)y=g(x)=wTx:樣本向量x各分量的線性加權(quán)樣本向量x與權(quán)向量w的向量點(diǎn)積如果| w |=1，則視作向量x在向量w上的投影 Fisher準(zhǔn)則的基本原理：找到一個最合適的投影軸，使兩類樣本在該軸上投影之間的

10、距離盡可能遠(yuǎn)，而每一類樣本的投影盡可能緊湊，從而使分類效果為最佳。24Fisher線性判別圖例Fisher判別x1x2w1H: g=0w2Fisher準(zhǔn)則的描述：用投影后數(shù)據(jù)的統(tǒng)計性質(zhì)均值和離散度的函數(shù)作為判別優(yōu)劣的標(biāo)準(zhǔn)。25d維空間樣本分布的描述量Fisher判別各類樣本均值向量mi樣本類內(nèi)離散度矩陣Si與總類內(nèi)離散度矩陣Sw 樣本類間離散度矩陣Sb：離散度矩陣在形式上與協(xié)方差矩陣很相似，但協(xié)方差矩陣是一種期望值，而離散矩陣只是表示有限個樣本在空間分布的離散程度26一維Y空間樣本分布的描述量Fisher判別各類樣本均值樣本類內(nèi)離散度和總類內(nèi)離散度樣本類間離散度 以上定義描述d維空間樣本點(diǎn)到一

11、向量投影的分散情況，因此也就是對某向量w的投影在w上的分布。樣本離散度的定義與隨機(jī)變量方差相類似 27樣本與其投影統(tǒng)計量間的關(guān)系Fisher判別樣本x與其投影y的統(tǒng)計量之間的關(guān)系：28樣本與其投影統(tǒng)計量間的關(guān)系Fisher判別29Fisher準(zhǔn)則函數(shù)Fisher判別評價投影方向w的原則，使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開，類內(nèi)盡可能密集的要求Fisher準(zhǔn)則函數(shù)的定義：Fisher最佳投影方向的求解30Fisher最佳投影方向的求解Fisher判別采用拉格朗日乘子算法解決 m1-m2是一向量，對與(m1-m2)平行的向量投影可使兩均值點(diǎn)的距離最遠(yuǎn)。但是如從使類間分得較開，同時

12、又使類內(nèi)密集程度較高這樣一個綜合指標(biāo)來看，則需根據(jù)兩類樣本的分布離散程度對投影方向作相應(yīng)的調(diào)整，這就體現(xiàn)在對m1-m2 向量按Sw-1作一線性變換，從而使Fisher準(zhǔn)則函數(shù)達(dá)到極值點(diǎn)31判別函數(shù)的確定前面討論了使Fisher準(zhǔn)則函數(shù)極大的d維向量w*的計算方法，判別函數(shù)中的另一項w0（閾值）可采用以下幾種方法確定： 分類規(guī)則:Fisher判別32Fisher公式的推導(dǎo)Fisher判別334.3 感知器準(zhǔn)則感知準(zhǔn)則函數(shù)是五十年代由Rosenblatt提出的一種自學(xué)習(xí)判別函數(shù)生成方法，由于Rosenblatt企圖將其用于腦模型感知器(Perceptron)，因此被稱為感知準(zhǔn)則函數(shù)。其特點(diǎn)是隨意確

13、定的判別函數(shù)初始值，在對樣本分類訓(xùn)練過程中逐步修正直至最終確定。34基本概念感知器：Perceptron，Rosenblatt，50d/20thc線性可分性：訓(xùn)練樣本集中的兩類樣本在特征空間可以用一個線性分界面正確無誤地分開。在線性可分條件下，對合適的(廣義)權(quán)向量a應(yīng)有：規(guī)范化樣本向量 ：將第二類樣本取其反向向量 感知器準(zhǔn)則35Every training sample yi places a constraint on the weight vector a.Given n examples, the solution must lie on the intersection of n h

14、alf-spaces.a1a2g(x)=aty基本概念36解向量與解區(qū)感知器準(zhǔn)則37解向量與解區(qū)Constrain margin: find min-length a withMove solution to the center of the feasible region 38感知器準(zhǔn)則函數(shù)對于任何一個增廣權(quán)向量a ，對樣本y正確分類，則有：aTy0 對樣本y錯誤分類，則有：aTy0定義一準(zhǔn)則函數(shù)JP(a) (感知準(zhǔn)則函數(shù))： 感知器準(zhǔn)則被錯分類的規(guī)范化增廣樣本集恒有JP(a)0，且僅當(dāng)a為解向量，Yk為空集（不存在錯分樣本）時， JP(a)=0，即達(dá)到極小值。確定向量a的問題變?yōu)閷P(

15、a)求極小值的問題。39梯度下降算法梯度下降算法：對(迭代)向量沿某函數(shù)的負(fù)梯度方向修正，可較快到達(dá)該函數(shù)極小值。 感知器準(zhǔn)則40算法(step by step)感知器準(zhǔn)則1. 初值: 任意給定一向量初始值a(1)2. 迭代: 第k+1次迭代時的權(quán)向量a(k+1)等于第k次的權(quán)向量a(k)加上被錯分類的所有樣本之和與rk的乘積3. 終止: 對所有樣本正確分類任意給定一向量初始值a(1)a(k+1)=a(k)+ rkSum(被錯分類的所有樣本)所有樣本正確分類得到合理的a完成分類器設(shè)計NY41感知器方法例解 固定增量法與可變增量法批量樣本修正法與單樣本修正法單樣本修正法：樣本集視為不斷重復(fù)出現(xiàn)的

16、序列，逐個樣本檢查，修正權(quán)向量批量樣本修正法：樣本成批或全部檢查后，修正權(quán)向量感知器準(zhǔn)則42Gradient Descent43Gradient Descenttoo large learning rate!44感知器方法小結(jié)感知準(zhǔn)則函數(shù)方法的思路是：先隨意找一個初始向量a(1)，然后用訓(xùn)練樣本集中的每個樣本來計算。若發(fā)現(xiàn)一個y出現(xiàn)aTy0。當(dāng)然，修改后的a(k+1)還可以使某些y出現(xiàn)a(k+1)Ty 0, i=1,N線性分類器設(shè)計求一組N個線性不等式的解樣本集增廣矩陣Y及一組N個線性不等式的的矩陣表示：引入余量(目標(biāo)向量) b=b1, b2, , bNT， bi任意給定正常數(shù)， aTyi =

17、 bi 0N個線性方程的的矩陣表示：46平方誤差準(zhǔn)則函數(shù)定義誤差向量 e=Ya-b：定義平方誤差準(zhǔn)則函數(shù)Js(a):MSE準(zhǔn)則最小二乘近似解（MSE解）：MSE方法的思想：對每個樣本，設(shè)定一個“理想”的判別函數(shù)輸出值，以最小平方誤差為準(zhǔn)則求最優(yōu)權(quán)向量47MSE準(zhǔn)則函數(shù)的偽逆解MSE準(zhǔn)則Y的偽逆矩陣48MSE方法與Fisher方法的關(guān)系與Fisher方法的關(guān)系：當(dāng)MSE準(zhǔn)則N1個N2個MSE解等價于Fisher解49MSE方法與Bayes方法的關(guān)系MSE準(zhǔn)則當(dāng)N，b=uN= 1,1, , 1T 時，則它以最小均方誤差逼近Bayes判別函數(shù)：50MSE方法的迭代解a*=Y+b, Y+=(YTY)-

18、1YT，計算量大實際中常用梯度下降法：MSE準(zhǔn)則批量樣本修正法單樣本修正法rk是遞減的序列514.5 多類問題兩類別問題可以推廣到多類別問題i/i 法：將C類別問題化為(C-1)個兩類（第i類與所有非i類）問題，按兩類問題確定其判別函數(shù)與決策面方程 i/j 法：將C類中的每兩類別單獨(dú)設(shè)計其線性判別函數(shù)，因此總共有C(C-1)/2個線性判別函數(shù) R1R3R21非12非2R1R3R212133252多類線性判別函數(shù)將特征空間確實劃分為c個決策域，共有c個判別函數(shù)多類問題決策規(guī)則：決策域的邊界由相鄰決策域的判別函數(shù)共同決定，此時應(yīng)有g(shù)i(x)=gj(x) 線性分類器的決策面是凸的，決策區(qū)域是單連通的

19、多類分類器的分界面是分段線性的53多類線性決策面圖例R1R3R2g1g2g1g3g3g1g3g2g2g3g2g1R1R3R2R5R4多類問題54決策樹簡介決策樹：一種多極分類器，它采用分級的形式，綜合用多個決策規(guī)則，逐步把復(fù)雜的多類別分類問題轉(zhuǎn)化為若干個簡單的分類問題來解決多類問題n1n2n3n4n5t1t2t3t4t5t6t755二叉決策樹二叉決策樹：除葉節(jié)點(diǎn)外，決策樹的每個節(jié)點(diǎn)ni都有且只有兩個子節(jié)點(diǎn)nil和nir。二叉決策樹把復(fù)雜的多類別分類問題轉(zhuǎn)化為多級兩類分類問題來解決。在每個節(jié)點(diǎn)ni ，都把樣本集分成兩個子集。每個子集可能仍包含多類別的樣本，繼續(xù)分直至僅包含單類別樣本的葉節(jié)點(diǎn)多類問

20、題n1n2n3n4t1t2t5x25x12x34x2212323t3t4564.6 分段線性判別函數(shù) 有些復(fù)雜模式識別問題不是線性可分的，需使用非線性的分類方法分段線性判別函數(shù)：一種特殊的非線性判別函數(shù)，它的決策面是若干超平面樹分類器的各節(jié)點(diǎn)上采用線性判別規(guī)則，即構(gòu)成分段線性分類器R1R3R2IIIIIII: 線性判別II：分段線性判別III: 二次判別57分段線性距離分類器最小距離分類器：把各類別樣本特征的均值向量作為各類的代表點(diǎn)(prototype) ，根據(jù)待識樣本到各類別代表點(diǎn)的最小距離判別其類別。決策面是兩類別均值連線的垂直平分面分段線性距離分類器：將各類別劃分成相對密集的子類，每個子類以它們的均值作為代表點(diǎn)，然后按最小距離分類 分段線性判別58分段線性距離分類器圖例分段線性判別m1m2xg(x)=0m1m2x59基于距離的