模式識別課件第4章

第四章線性判別函數(shù)孔萬增KongWanzeng,Ph.DTelmail:kongwanzeng@計算機學院IPLTableofContents4.1引言4.2Fisher線性判別4.3

感知器準則4.4最小平方誤差準則4.5多類問題4.6分段線性判別函數(shù)4.7

討論4.1

引言基于樣本的Bayes分類器：通過估計類條件概率密度函數(shù)，設計相應的判別函數(shù)最一般情況下適用的“最優(yōu)”分類器：錯誤率最小，對分類器設計在理論上有指導意義。獲取統(tǒng)計分布及其參數(shù)很困難，實際問題中并不一定具備獲取準確統(tǒng)計分布的條件。訓練

樣本集樣本分布的

統(tǒng)計特征：

概率密度函數(shù)決策規(guī)則：

判別函數(shù)

決策面方程分類器

功能結(jié)構(gòu)ARGMAXg1...g2gc...x1x2xna(x)直接確定判別函數(shù)基于樣本的直接確定判別函數(shù)方法：設定判別函數(shù)形式，用樣本集確定判別函數(shù)的參數(shù)。定義準則函數(shù)，表達分類器應滿足的要求。這些準則的“最優(yōu)”并不一定與錯誤率最小相一致：次優(yōu)分類器。實例：正態(tài)分布最小錯誤率貝葉斯分類器在特殊情況下，是線性判別函數(shù)g(x)=wTx（決策面是超平面）。那么我們能否基于樣本直接確定w?引言訓練樣本集決策規(guī)則：

判別函數(shù)

決策面方程選擇最佳準則線性分類器設計步驟線性分類器設計任務：給定樣本集K，確定線性判別函數(shù)g(x)=wTx的各項系數(shù)w。步驟：收集一組已知類別的樣本K={x1,x2,…,xN}按需要確定一準則函數(shù)J(K,w)，其值反映分類器的性能，其極值解對應于“最好”分類。用最優(yōu)化技術求準則函數(shù)J的極值解w*，從而確定判別函數(shù)，完成分類器設計。對于未知樣本x，計算g(x)，判斷其類別。引言設計應用線性判別函數(shù)d維空間中的線性判別函數(shù)的一般形式：x是樣本向量，即樣本在d維特征空間中的描述，w是權向量，w0是一個常數(shù)(閾值權)。引言兩類問題的分類決策規(guī)則引言規(guī)則表達1規(guī)則表達2線性判別函數(shù)的幾何意義決策面(decisionboundary)方程：g(x)=0決策面將特征空間分成決策區(qū)域。向量w是決策面H的法向量g(x)是點x到?jīng)Q策面H的距離的一種代數(shù)度量x1x2wxxprH:g=0R1:g>0R2:g<0引言廣義線性判別函數(shù)線性判別函數(shù)是形式最為簡單的判別函數(shù)，但是它不能用于復雜情況。例：設計一個一維分類器，使其功能為：判別函數(shù)：引言廣義線性判別函數(shù)(2)二次函數(shù)的一般形式：g(x)又可表示成：映射X→Y引言廣義線性判別函數(shù)(3)按照上述方法，任何非線性函數(shù)g(x)用級數(shù)展開成高次多項式后，都可轉(zhuǎn)化成線性來處理。一種特殊映射方法：增廣樣本向量y與增廣權向量a引言廣義線性判別函數(shù)(4)增廣樣本向量使特征空間增加了一維，但保持了樣本間的歐氏距離不變，對于分類效果也與原決策面相同，只是在Y空間中決策面是通過坐標原點的，這在分析某些問題時具有優(yōu)點，因此經(jīng)常用到。線性判別函數(shù)的齊次簡化：引言廣義線性判別函數(shù)舉例例1：設五維空間的線性方程為55x1+68x2+32x3+16x4+26x5+10=0，試求出其權向量與樣本向量點積的表達式wTx+w0=0中的w，x以及增廣權向量與增廣樣本向量形式aTy中的a與y。引言答：樣本向量：x=(x1,x2,x3,x4,x5)T權向量：w=(55,68,32,16,26)T,w0=10增廣樣本向量：y=(1,x1,x2,x3,x4,x5)T增廣權向量：a=(10,55,68,32,16,26)T廣義線性判別函數(shù)舉例(2)例2：有一個三次判別函數(shù)：z=g(x)=x3+2x2+3x+4。試建立一映射x→y，使得z轉(zhuǎn)化為y的線性判別函數(shù)。引言答：映射X→Y如下：廣義線性判別函數(shù)舉例(3)例3：設在三維空間中一個類別分類問題擬采用二次曲面。如欲采用廣義線性方程求解，試問其廣義樣本向量與廣義權向量的表達式，其維數(shù)是多少？引言答：設次二次曲面為:二次

曲面廣義

權向量廣義樣本向量維數(shù)為10廣義線性

判別函數(shù)4.2Fisher線性判別線性判別函數(shù)y=g(x)=wTx:樣本向量x各分量的線性加權樣本向量x與權向量w的向量點積如果||w||=1，則視作向量x在w上的投影Fisher準則的基本原理：找到一個最合適的投影軸，使兩類樣本在該軸上投影之間的距離盡可能遠，而每一類樣本的投影盡可能緊湊，從而使分類效果為最佳。Fisher線性判別圖例x1x2w1H:g=0w2Fisher準則的描述：用投影后數(shù)據(jù)的統(tǒng)計性質(zhì)

(均值和離散度的函數(shù))作為判別優(yōu)劣的標準。Fisherd維空間樣本分布的描述量各類樣本均值向量mi樣本類內(nèi)離散度矩陣Si與總類內(nèi)離散度矩陣Sw

樣本類間離散度矩陣Sb：Fisher離散度矩陣在形式上與協(xié)方差矩陣很相似，但協(xié)方差矩陣是一種總體期望值，而離散矩陣只是表示有限個樣本在空間分布的離散程度一維Y空間樣本分布的描述量各類樣本均值樣本類內(nèi)離散度和總類內(nèi)離散度樣本類間離散度

以上定義描述d維空間樣本點到一向量投影后的分散情況。樣本離散度的定義與隨機變量方差相類似Fisher樣本與其投影統(tǒng)計量間的關系樣本x與其投影y的統(tǒng)計量之間的關系：Fisher樣本與其投影統(tǒng)計量間的關系(2)FisherFisher準則函數(shù)評價投影方向w的原則，使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開，類內(nèi)盡可能密集的要求Fisher準則函數(shù)的定義：Fisher最佳投影方向的求解FisherFisher最佳投影方向的求解采用拉格朗日乘子算法解決m1-m2是一向量，對與(m1-m2)平行的向量投影可使兩均值點的距離最遠。但是如果從使類間分得較開，同時又使類內(nèi)密集程度較高這樣一個綜合指標來看，則需根據(jù)兩類樣本的分布離散程度對投影方向作相應的調(diào)整，這就體現(xiàn)在對m1-m2

向量按Sw-1作一線性變換，從而使Fisher準則函數(shù)達到極值點Fisher判別函數(shù)的確定前面討論了使Fisher準則函數(shù)極大的d維向量w*的計算方法，判別函數(shù)中的另一項w0（閾值）可采用以下幾種方法確定：分類規(guī)則:FisherFisher公式的推導FisherFisher準則舉例Fisher例1：設兩類樣本的類內(nèi)離散矩陣分別為S1,S2,各類樣本均值分別為m1=(2,0)t,m2=(2,2)t,試用Fisher準則求其決策面方程。答：由于兩類樣本分布形狀是相同的（只是方向不同），因此-w0應為（投影后）兩類均值的中點Fisher準則最佳投影Fisher準則最佳分界面Fisher最佳線性分界面FisherR1R2圖中綠線為最佳分界面4.3

感知器準則感知器準則是五十年代由Rosenblatt提出的一種自學習判別函數(shù)生成方法，由于Rosenblatt企圖將其用于腦模型感知器(Perceptron)，因此被稱為感知準則函數(shù)。其特點是隨意確定的判別函數(shù)初始值，在對樣本分類訓練過程中逐步修正直至最終確定?；靖拍罡兄鳎篜erceptron，Rosenblatt，50d/20thc線性可分性：訓練樣本集中的兩類樣本在特征空間可以用一個線性分界面正確無誤地分開。在線性可分條件下，對合適的(廣義)權向量a應有：規(guī)范化樣本向量

：將第二類樣本取其反向向量

感知器解向量與解區(qū)感知器31感知器準則函數(shù)對于任何一個增廣權向量a

，對樣本y正確分類，則有：aTy>0對樣本y錯誤分類，則有：aTy<0定義一準則函數(shù)JP(a)(感知準則函數(shù))：被錯分類的規(guī)范化增廣樣本集恒有JP(a)≥0，且僅當a為解向量，Yk為空集（不存在錯分樣本）時，JP(a)=0，即達到極小值。確定向量a的問題變?yōu)閷P(a)求極小值的問題。感知器梯度下降算法梯度下降算法：對(迭代)向量沿某函數(shù)的負梯度方向修正，可較快到達該函數(shù)極小值。感知器算法(stepbystep)1.初值:任意給定一向量初始值a12.迭代:第k+1次迭代時的權向量ak+1等于第k次的權向量ak加上被錯分類的所有樣本之和與rk的乘積3.終止:對所有樣本正確分類任意給定一向量

初始值a1ak+1=ak+rk×Sum

(被錯分類的所有樣本)所有樣本

正確分類得到合理的a

完成

分類器設計NY感知器感知器方法例解固定增量法與可變增量法批量樣本修正法與單樣本修正法單樣本修正法：樣本集視為不斷重復出現(xiàn)的序列，逐個樣本檢查，修正權向量批量樣本修正法：樣本成批或全部檢查后，修正權向量感知器感知器方法小結(jié)感知準則函數(shù)方法的思路是：先隨意找一個初始向量a1，然后用訓練樣本集中的每個樣本來計算。若發(fā)現(xiàn)一個y出現(xiàn)aTy<0，則只要ak+1=ak+rky，rk為正(步長系數(shù))，則必有ak+1Ty=akTy+rkyTy，就有趨勢做到使ak+1Ty>0。當然，修改后的ak+1還可以使某些y出現(xiàn)ak+1Ty<0的情況，理論證明，只要訓練樣本集線性可分，無論a1的初值是什么，經(jīng)過有限次疊代，都可收斂。感知器4.4最小平方誤差準則規(guī)范化增廣樣本向量yi，增廣權向量a，正確分類要求：aTyi>0,i=1,…,N線性分類器設計求一組N個線性不等式的解a*樣本集增廣矩陣Y及一組N個線性不等式的的矩陣表示：引入余量(目標向量)b=[b1,b2,…,bN]T，bi為任意給定正常數(shù)，aTyi=bi>0N個線性方程的的矩陣表示：矛盾方程組，沒有精確解平方誤差準則函數(shù)定義誤差向量

e=Ya-b：定義平方誤差準則函數(shù)Js(a):最小二乘近似解（MSE解）：MSE方法的思想：對每個樣本，設定一個“理想”的判別函數(shù)輸出值，以最小平方誤差為準則求最優(yōu)權向量MSEMSE準則函數(shù)的偽逆解Y的

偽逆矩陣MSEMSE方法的迭代解a*=Y+b,Y+=(YTY)-1YT，計算量大實際中常用梯度下降法：批量樣本修正法單樣本修正法MSEWidrow-HoffMSE方法與Fisher方法的關系與Fisher方法的關系：當N1個N2個MSE解等價于Fisher解MSEMSE方法與Bayes方法的關系當N→∞，b=uN=[1,1,…,1]T時，則它以最小均方誤差逼近Bayes判別函數(shù)：MSEMSE方法應用舉例MSE4.5多類問題兩類別問題可以推廣到多類別問題ωi/~ωi法：將C類別問題化為(C-1)個兩類（第i類與所有非i類）問題，按兩類問題確定其判別函數(shù)與決策面方程。ωi/ωj法：將C類中的每兩類別單獨設計其線性判別函數(shù)，因此總共有C(C-1)/2個線性判別函數(shù)。R1R3R2ω1非ω1ω2非ω2R1R3R2ω1ω2ω1ω3ω3ω2多類線性判別函數(shù)將特征空間確實劃分為c個決策域，共有c個判別函數(shù)決策規(guī)則：決策域的邊界由相鄰決策域的判別函數(shù)共同決定，此時應有gi(x)=gj(x)

線性分類器的決策面是凸的，決策區(qū)域是單連通的多類分類器的分界面是分段線性的多類

問題多類線性決策面圖例R1R3R2g1>g2g1>g3g3>g1g3>g2g2>g3g2>g1R1R3R2R5R4多類

問題決策樹簡介決策樹：一種多級分類器，它采用分級的形式，綜合用多個決策規(guī)則，逐步把復雜的多類別分類問題轉(zhuǎn)化為若干個簡單的分類問題來解決n1n2n3n4n5t1t2t3t4t5t6t7多類

問題二叉決策樹二叉決策樹：除葉節(jié)點外，決策樹的每個節(jié)點ni都有且只有兩個子節(jié)點nil和nir。二叉決策樹把復雜的多類別分類問題轉(zhuǎn)化為多級兩類分類問題來解決。在每個節(jié)點ni

，都把樣本集分成兩個子集。每個子集可能仍包含多類別的樣本，繼續(xù)分直至僅包含單類別樣本的葉節(jié)點n1n2n3n4t1t2t5x2≤5x1≤2x3≤4x2≤2ω1ω2ω3ω2ω3t3t4多類

問題4.6分段線性判別函數(shù)有些復雜模式識別問題不是線性可分的，需使用非線性的分類方法分段線性判別函數(shù)：一種特殊的非線性判別函數(shù)，它的決策面是若干超平面樹分類器的各節(jié)點上采用線性判別規(guī)則，即構(gòu)成分段線性分類器R1R3R2IIIIIII:線性判別II：分段線性判別III:二次判別分段線性距離分類器最小距離分類器：把各類別樣本的均值向量作為各類的代表點(prototype)

，根據(jù)待識樣本到各類別代表點的最小距離判別其類別。決策面是兩類別均值連線的垂直平分面。分段

線性m1m2xg(x)=0m1m2x分段線性距離分類器(2)分段線性距離分類器：將各類別劃分成相對密集的子類，每個子類以它們的均值作為代表點，然后按最小距離分類。分段

線性基于距離的分段線性判別函數(shù)判別函數(shù)定義：ωi有l(wèi)i個子類，即屬于ωi

的決策域Ri分成li個子域Ri1,Ri2,…,Rili)，每個子區(qū)域用均值mik代表點判別規(guī)則：