[工學(xué)]第5章 線性判別函數(shù).ppt

第五章 線性判別函數(shù),線性判別函數(shù) Fisher線性判別 最小平方誤差準(zhǔn)則 多類(lèi)問(wèn)題 分段線性判別函數(shù),5.1 問(wèn)題的提出 GenerativeDiscriminative,基于樣本的Bayes分類(lèi)器：通過(guò)估計(jì)類(lèi)條件概率密度函數(shù)，設(shè)計(jì)相應(yīng)的判別函數(shù),“最優(yōu)”分類(lèi)器：錯(cuò)誤率最小，風(fēng)險(xiǎn)最小等對(duì)分類(lèi)器設(shè)計(jì)在理論上有指導(dǎo)意義 獲取統(tǒng)計(jì)分布及其參數(shù)很困難，實(shí)際問(wèn)題中并不一定具備獲取統(tǒng)計(jì)分布的條件,訓(xùn)練 樣本集,樣本分布的 統(tǒng)計(jì)特征： 概率密度函數(shù),決策規(guī)則： 判別函數(shù) 決策面方程,判別函數(shù),基于訓(xùn)練樣本確定判別函數(shù),例：正態(tài)分布最小錯(cuò)誤率貝葉斯分類(lèi)器在特殊情況下，是線性判別函數(shù) g(x)=wTx（決策面是超平面），能否基于樣本直接確定w? 設(shè)定判別函數(shù)形式，用樣本集確定參數(shù) 使用準(zhǔn)則函數(shù)，表達(dá)分類(lèi)器應(yīng)滿足的要求 這些準(zhǔn)則的“最優(yōu)”并不一定與錯(cuò)誤率最小相一致：次優(yōu)分類(lèi)器,該樣本集中的每個(gè)樣本的類(lèi)別已知,線性分類(lèi)器設(shè)計(jì)步驟,線性分類(lèi)器設(shè)計(jì)任務(wù)：給定樣本集K，確定線性判別函數(shù) g(x)=wTx 的各項(xiàng)系數(shù)w： 收集一組樣本K=x1,x2,xN 按需要確定一準(zhǔn)則函數(shù)J(K,w)，其值反映分類(lèi)器的性能，其極值解對(duì)應(yīng)于“最優(yōu)”決策 用最優(yōu)化技術(shù)求準(zhǔn)則函數(shù)J的極值解w*，從而確定判別函數(shù)，完成分類(lèi)器設(shè)計(jì),對(duì)于未知樣本x，計(jì)算g(x)，判斷其類(lèi)別,設(shè)計(jì),應(yīng)用,線性判別函數(shù),d維空間中的線性判別函數(shù)的一般形式：,x是樣本向量，即樣本在d維特征空間中的描述， w是權(quán)向量，w0是一個(gè)常數(shù)(閾值權(quán)),為了說(shuō)明向量W的意義，我們假設(shè)在決策平面上有兩個(gè)特征向量X1與X2，則應(yīng)有 其中(X1-X2)也是一個(gè)向量，上式表明向量W與該平面上任兩點(diǎn)組成的向量(X1-X2)正交，因此W的方向就是決策面的法線方向,兩類(lèi)問(wèn)題的分類(lèi)決策規(guī)則,是決策面方程，它是兩類(lèi)模式的分界，對(duì)于二維空間情況，它是一條直線；對(duì)于三維情況，它是一個(gè)平面；而對(duì)于高維空間的情況，則是一個(gè)超平面,構(gòu)造一個(gè)二類(lèi)模式的線性分類(lèi)器，如下圖所示：,線性判別函數(shù)的幾何意義,決策面(decision boundary) H 方程：g(x)=0 決策面將特征空間分成決策區(qū)域 向量w是決策面H的法向量 g(x)是點(diǎn)x到?jīng)Q策面H的距離的一種代數(shù)度量,線性判別函數(shù)的幾何意義,結(jié)論：利用線性判別函數(shù)進(jìn)行決策，就是用一個(gè)超平面把特征空間分割成兩個(gè)決策區(qū)域，超平面方向由權(quán)向量W決定，它的位置由閾值權(quán)w0確定,=0,廣義線性判別函數(shù),線性判別函數(shù)是形式最為簡(jiǎn)單的判別函數(shù)，但是它不能用于復(fù)雜情況 例：設(shè)計(jì)一個(gè)一維分類(lèi)器，使其功能為：,判別函數(shù)：,廣義線性判別函數(shù),二次函數(shù)的一般形式：,g(x)又可表示成：,映射XY,廣義線性判別函數(shù),按照上述原理，任何非線性函數(shù)g(x)用級(jí)數(shù)展開(kāi)成高次多項(xiàng)式后，都可轉(zhuǎn)化成線性來(lái)處理 一種特殊映射方法：增廣樣本向量y與增廣權(quán)向量a,廣義線性判別函數(shù),增廣樣本向量使特征空間增加了一維，但保持了樣本間的歐氏距離不變，對(duì)于分類(lèi)效果也與原決策面相同，只是在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：有一個(gè)三次判別函數(shù)：z=g(x)=x3+2x2+3x+4。試建立一映射xy，使得z轉(zhuǎn)化為y的線性判別函數(shù)。,答：映射XY如下：,廣義線性判別函數(shù),例3：設(shè)在三維空間中一個(gè)兩類(lèi)別分類(lèi)問(wèn)題擬采用二次曲面。如欲采用廣義線性方程求解，試問(wèn)其廣義樣本向量與廣義權(quán)向量的表達(dá)式，其維數(shù)是多少？,答：設(shè)該二次曲面方程為:,二次 曲面,廣義 權(quán)向量,廣義樣本向量,維數(shù)為10,廣義線性 判別函數(shù),5.2 Fisher線性判別 降維/兩類(lèi),線性判別函數(shù) y = g(x) = wTx : 樣本向量x各分量的線性加權(quán) 樣本向量x與權(quán)向量w的向量點(diǎn)積 如果| w |=1，則視作向量x在w上的投影 Fisher準(zhǔn)則的基本原理：找到一個(gè)最理想的投影軸，使兩類(lèi)樣本在該軸上投影之間的距離盡可能遠(yuǎn)，而每一類(lèi)樣本的投影盡可能緊湊，從而使分類(lèi)效果為最佳,Fisher線性判別圖例,Fisher準(zhǔn)則的描述：用投影后數(shù)據(jù)的統(tǒng)計(jì)性質(zhì) 均值和離散度的函數(shù)作為判別優(yōu)劣的標(biāo)準(zhǔn),d維X空間樣本分布的描述量,各類(lèi)樣本均值向量mi,樣本類(lèi)內(nèi)離散度矩陣Si與總類(lèi)內(nèi)離散度矩陣Sw,樣本類(lèi)間離散度矩陣Sb：,離散度矩陣在形式上與協(xié)方差矩陣很相似,一維Y空間樣本分布的描述量,各類(lèi)樣本均值,樣本類(lèi)內(nèi)離散度和總類(lèi)內(nèi)離散度,樣本類(lèi)間離散度,以上定義描述d維空間樣本點(diǎn)到一向量投影后的分散情況,原樣本與其投影統(tǒng)計(jì)量間的關(guān)系,樣本x與其投影 y 的統(tǒng)計(jì)量之間的關(guān)系：,樣本與其投影統(tǒng)計(jì)量間的關(guān)系,Fisher準(zhǔn)則函數(shù),評(píng)價(jià)投影方向w的原則，使原樣本向量在該方向上的投影能兼顧類(lèi)間分布盡可能分開(kāi)，類(lèi)內(nèi)盡可能密集的要求 Fisher準(zhǔn)則函數(shù)的定義：,Fisher最佳投影方向的求解,Fisher最佳投影方向的求解,采用拉格朗日乘子算法解決,m1-m2是一向量，對(duì)與(m1-m2)平行的向量投影可使兩均值點(diǎn)的距離最遠(yuǎn)。但是如果從使類(lèi)間分得較開(kāi)，同時(shí)又使類(lèi)內(nèi)密集程度較高這樣一個(gè)綜合指標(biāo)來(lái)看，則需根據(jù)兩類(lèi)樣本的分布離散程度對(duì)投影方向作相應(yīng)的調(diào)整，這就體現(xiàn)在對(duì)m1-m2 向量按Sw-1作一線性變換，從而使Fisher準(zhǔn)則函數(shù)達(dá)到極值點(diǎn),判別函數(shù)的確定,前面討論了使Fisher準(zhǔn)則函數(shù)極大的d維向量w*的計(jì)算方法，判別函數(shù)中的另一項(xiàng)w0（閾值）可采用以下幾種方法確定：,分類(lèi)規(guī)則:,Fisher準(zhǔn)則舉例,例1：設(shè)兩類(lèi)樣本的類(lèi)內(nèi)離散矩陣分別為S1，S2，各類(lèi)樣本均值分別為m1=(2, 0)T, m2=(2, 2)T, 試用Fisher準(zhǔn)則求其決策面方程,解,由于兩類(lèi)樣本分布形狀是相同的（只是方向不同），因此w0應(yīng)為（投影后）兩類(lèi)均值的中點(diǎn),Fisher準(zhǔn)則最佳投影,Fisher準(zhǔn)則最佳分界面,Fisher最佳線性分界面,R1,R2,圖中綠線為最佳分界面,x1,x2,5.3 最小平方誤差準(zhǔn)則 MSE,對(duì)于增廣樣本向量，線性判別函數(shù)為 g(x)=aTy 規(guī)范化增廣樣本向量yi，增廣權(quán)向量a，yi被正確分類(lèi)，要求： aTyi0, i=1,N 線性分類(lèi)器設(shè)計(jì) 求一組N個(gè)線性不等式的解 樣本集增廣矩陣Y及一組N個(gè)線性不等式的的矩陣表示：,引入余量(目標(biāo)向量) b=b1, b2, , bNT， bi任意給定正常數(shù)， aTyi = bi 0 N個(gè)線性方程的的矩陣表示：,平方誤差準(zhǔn)則函數(shù),定義誤差向量 e =Ya - b： 定義平方誤差準(zhǔn)則函數(shù) Js(a):,最小二乘解（MSE解）：,MSE方法的思想：對(duì)每個(gè)樣本，設(shè)定一個(gè)“理想”的判別函數(shù)輸出值，以最小平方誤差為準(zhǔn)則求最優(yōu)權(quán)向量,MSE準(zhǔn)則函數(shù)的偽逆解,Y的 偽逆矩陣,MSE方法的迭代解,a*=Y+b, Y+=(YTY)-1YT，計(jì)算量大 實(shí)際中常用梯度下降法：,批量樣本修正法,單樣本修正法,梯度下降算法：對(duì)(迭代)向量沿某函數(shù)的負(fù)梯度方向修正，可較快到達(dá)該函數(shù)極小值,MSE方法與 Fisher方法的關(guān)系,與Fisher方法的關(guān)系：可證明當(dāng),MSE解等價(jià)于Fisher解,MSE方法與Bayes方法的關(guān)系,可證明當(dāng)N，b=uN= 1,1, , 1T 時(shí)，則它以最小均方誤差逼近Bayes判別函數(shù)：,5.4 多類(lèi)問(wèn)題,兩類(lèi)別問(wèn)題可以推廣到多類(lèi)別問(wèn)題 i/i 法：將C類(lèi)別問(wèn)題化為(C-1)個(gè)兩類(lèi)（第i類(lèi)與所有非i類(lèi)）問(wèn)題，按兩類(lèi)問(wèn)題確定其判別函數(shù)與決策面方程 i/j 法：將C類(lèi)中的每?jī)深?lèi)別單獨(dú)設(shè)計(jì)其線性判別函數(shù)，因此總共有C(C-1)/2個(gè)線性判別函數(shù),多類(lèi)線性判別函數(shù),將特征空間確實(shí)劃分為c個(gè)決策域，共有c個(gè)判別函數(shù),決策規(guī)則：,決策域的邊界由相鄰決策域的判別函數(shù)共同決定，此時(shí)應(yīng)有g(shù)i(x)=gj(x) 線性分類(lèi)器的決策面是凸的，決策區(qū)域是單連通的 多類(lèi)分類(lèi)器的分界面是分段線性的,多類(lèi)線性決策面圖例,決策樹(shù),決策樹(shù)：一種多極分類(lèi)器，它采用分級(jí)的形式，綜合用多個(gè)決策規(guī)則，逐步把復(fù)雜的多類(lèi)別分類(lèi)問(wèn)題轉(zhuǎn)化為若干個(gè)簡(jiǎn)單的分類(lèi)問(wèn)題來(lái)解決,二叉決策樹(shù),二叉決策樹(shù)把復(fù)雜的多類(lèi)別分類(lèi)問(wèn)題轉(zhuǎn)化為多級(jí)兩類(lèi)分類(lèi)問(wèn)題來(lái)解決,5.5 分段線性判別函數(shù),有些復(fù)雜模式識(shí)別問(wèn)題不是線性可分的，需使用非線性的分類(lèi)方法 分段線性判別函數(shù)：一種特殊的非線性判別函數(shù)，它的決策面是若干超平面,分段線性距離分類(lèi)器,最小距離分類(lèi)器：把各類(lèi)別樣本的均值向量作為各類(lèi)的代表點(diǎn)(prototype) ，根據(jù)待識(shí)樣本到各類(lèi)別代表點(diǎn)的最小距離判別其類(lèi)別。決策面是兩類(lèi)別均值連線的垂直平分面,分段線性距離分類(lèi)器,分段線性距離分類(lèi)器：將各類(lèi)別劃分成相對(duì)密集的子類(lèi)，每個(gè)子類(lèi)以它們的均值作為代表點(diǎn)，然后按最小距離分類(lèi),基于距離的分段線性判別函數(shù),判別函數(shù)定義：i有l(wèi)i個(gè)子類(lèi)，即屬于i 的決策域Ri分成li個(gè)子域Ri1, Ri2, Rili)，每個(gè)子區(qū)域用均值mik作為代表點(diǎn),判別規(guī)則：,分段線性判別函數(shù),分段線性判別函數(shù)的形式: gik(x)表示第i類(lèi)第k段線性判別函數(shù)，li為i類(lèi)所具有的判別函數(shù)個(gè)數(shù)，wik與wi0k分別是第k段的權(quán)向量與閾值,第i類(lèi)的判別函數(shù):,分段線性判別函數(shù),判別規(guī)則: