模式識(shí)別課件第4章

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

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

討論4.1

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

樣本集樣本分布的

統(tǒng)計(jì)特征：

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

判別函數(shù)

決策面方程分類器

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

判別函數(shù)

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

曲面廣義

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

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

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

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

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

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

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

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

感知器解向量與解區(qū)感知器31感知器準(zhǔn)則函數(shù)對(duì)于任何一個(gè)增廣權(quán)向量a

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

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

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

正確分類得到合理的a

完成

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

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

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

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

問(wèn)題多類線性決策面圖例R1R3R2g1>g2g1>g3g3>g1g3>g2g2>g3g2>g1R1R3R2R5R4多類

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

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

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

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

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

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

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

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