第4章非參數(shù)判別分類(lèi)方法(線性判別函數(shù))

1、 模 式 識(shí) 別 徐蔚然北京郵電大學(xué)信息工程學(xué)院北京郵電大學(xué)信息工程學(xué)院非參數(shù)判別分類(lèi)方法 n包括內(nèi)容n第4章 線性判別函數(shù)n第5章 非線性判別函數(shù)n第6章 近鄰法n第11章 人工神經(jīng)網(wǎng)絡(luò)n第13章 統(tǒng)計(jì)學(xué)習(xí)理論和支持向量機(jī)學(xué)習(xí)目的學(xué)習(xí)目的 n(1) 掌握非參數(shù)判別分類(lèi)法的原理n(2) 掌握機(jī)器自學(xué)習(xí)的原理n(3) 學(xué)習(xí)線性分類(lèi)器的典型算法n(4) 用近鄰法進(jìn)行分類(lèi)(第六章)n(5) 通過(guò)相應(yīng)數(shù)學(xué)工具的運(yùn)用進(jìn)一步提高運(yùn)用數(shù)學(xué)的本領(lǐng)重點(diǎn)重點(diǎn) n(1) 非參數(shù)判別分類(lèi)器的基本原理n(2) 線性分類(lèi)器的典型方法n以Fisher準(zhǔn)則為代表的傳統(tǒng)模式識(shí)別方法n以感知準(zhǔn)則函數(shù)為代表的機(jī)器自學(xué)習(xí)方法n(3)

2、 線性分類(lèi)器擴(kuò)展到非線性分類(lèi)器n(4) 近鄰法的工作原理及其改進(jìn) 難點(diǎn)難點(diǎn) n(1) Fisher準(zhǔn)則函數(shù)，其中用到向量點(diǎn)積，帶約束條件的拉格朗日乘子法以及矩陣的特征值、特征向量等數(shù)學(xué)工具。要求對(duì)這些數(shù)學(xué)工具較深理解。n(2) 感知器準(zhǔn)則函數(shù)提出利用錯(cuò)誤提供信息實(shí)現(xiàn)疊代修正的學(xué)習(xí)原理(3) 近鄰法的改進(jìn)知知識(shí)識(shí)點(diǎn)點(diǎn) 貝葉斯決策理論和統(tǒng)計(jì)判別方法 n采用統(tǒng)計(jì)分布來(lái)描述來(lái)描述d維特征空間中的樣本分布n采用分類(lèi)器中最重要的指標(biāo)錯(cuò)誤率作為產(chǎn)生判別函數(shù)和決策面的依據(jù)n給出了最一般情況下適用的“最優(yōu)”分類(lèi)器設(shè)計(jì)方法n對(duì)各種不同的分類(lèi)器設(shè)計(jì)技術(shù)在理論上都有指導(dǎo)意義。 n貝葉斯決策理論設(shè)計(jì)分類(lèi)器的步驟n過(guò)程n

3、首先得到有關(guān)樣本總體分布的知識(shí)n先驗(yàn)概率n類(lèi)條件概率密度函數(shù)n計(jì)算出后驗(yàn)概率貝葉斯決策理論和統(tǒng)計(jì)判別方法n問(wèn)題n獲取統(tǒng)計(jì)分布及其參數(shù)這部分是很困難 n實(shí)際問(wèn)題中并不一定具備獲取準(zhǔn)確統(tǒng)計(jì)分布的條件 貝葉斯決策理論和統(tǒng)計(jì)判別方法非參數(shù)判別分類(lèi)方法n模式識(shí)別的設(shè)計(jì)過(guò)程n主要關(guān)鍵部分: 是設(shè)計(jì)判別函數(shù)、決策面方程的確定過(guò)程n模式識(shí)別的設(shè)計(jì)過(guò)程改成： 由于這種方法跳過(guò)了統(tǒng)計(jì)分布的參數(shù)估計(jì)，沒(méi)有使用統(tǒng)計(jì)參數(shù)作為依據(jù)，因此也是非參數(shù)判別分類(lèi)方法。非參數(shù)判別分類(lèi)方法。 而以貝葉斯決策方法為基礎(chǔ)的方法則稱(chēng)為參數(shù)判別方參數(shù)判別方法法。 非參數(shù)判別分類(lèi)方法n主要的方法n線性分類(lèi)器 (第4章)n非線性判別函數(shù) (第5

4、章)n近鄰法 (第6章)n人工神經(jīng)網(wǎng)絡(luò)(第11章)n支持向量機(jī)(第13章)通常的模式識(shí)別方法都屬于該類(lèi)別方法非參數(shù)判別分類(lèi)方法n回顧正態(tài)分布概率模型的最小錯(cuò)誤率貝葉斯分類(lèi)器n在特殊情況下，判別函數(shù)與決策面方程會(huì)呈現(xiàn)某些典型的形式 n當(dāng)各類(lèi)協(xié)方差矩陣都相等時(shí)，可得到線性分類(lèi)器n如果各類(lèi)樣本的分布為等半徑的超球體形式，且先驗(yàn)概率相等，則又可得到最小距離分類(lèi)器n而在正態(tài)分布的一般情況下，決策面為超二次曲面形式，屬非線性分類(lèi)器非參數(shù)判別分類(lèi)方法n線性分類(lèi)器計(jì)算最簡(jiǎn)單，得到廣泛重視與深入研究，并在設(shè)計(jì)分類(lèi)器時(shí)作為優(yōu)先考慮的類(lèi)型n對(duì)非線性分類(lèi)器則著重討論分段線性判別函數(shù)的基本概念與基本做法n近鄰法是分段線

5、性判別函數(shù)的一種典型方法n主要依據(jù): 同類(lèi)物體在特征空間具有聚類(lèi)特性的原理n注意: 這些準(zhǔn)則的“最優(yōu)”并不一定與錯(cuò)誤率最小相一致非參數(shù)判別分類(lèi)方法n參數(shù)與非參數(shù)判別方法的重要不同點(diǎn)n參數(shù)分類(lèi)方法: 判別函數(shù)及決策面方程的類(lèi)別確定是由樣本分布規(guī)律決定的n非參數(shù)判別方法: 使用什么典型的分類(lèi)決策方法要預(yù)先由設(shè)計(jì)者確定，然后利用訓(xùn)練樣本集提供的信息確定這些函數(shù)中的參數(shù)n非參數(shù)判別分類(lèi)方法的兩個(gè)過(guò)程n選擇函數(shù)類(lèi)型n確定參數(shù)第4章 線性分類(lèi)器 線性判別函數(shù)的基本概念n線性判別函數(shù)模式識(shí)別方法的基本思想n設(shè)計(jì)分類(lèi)器的關(guān)鍵問(wèn)題是設(shè)計(jì)判別函數(shù)n假設(shè)判別函數(shù)是線性函數(shù)n用訓(xùn)練樣本去估計(jì)線性判別函數(shù)的參數(shù)線性判別

6、函數(shù)的基本概念n線性判別函數(shù)的表示n設(shè)樣本d維特征空間中描述，則兩類(lèi)別問(wèn)題中線性判別函數(shù)的一般形式可表示成 n其中 而0是一個(gè)常數(shù)，稱(chēng)為閾值權(quán)。 線性判別函數(shù)的基本概念n決策規(guī)則 ng(X)0就是相應(yīng)的決策面方程n在線性判別函數(shù)條件下它對(duì)應(yīng)d維空間的一個(gè)超平面線性判別函數(shù)的基本概念線性判別函數(shù)的基本概念n向量W的意義n假設(shè)在該決策平面上有兩個(gè)特征向量X1與X2，則應(yīng)有 n向量W與該平面上任兩點(diǎn)組成的向量(X1-X2)正交，因此W就是該超平面的法線向量。線性判別函數(shù)的基本概念n向量W的意義n而g(X)也就是d維空間中任一點(diǎn)X到該決策面距離的代數(shù)度量n該決策平面將這兩類(lèi)樣本按其到該面距離的正負(fù)號(hào)確

7、定其類(lèi)別。 線性判別函數(shù)的基本概念nw0則體現(xiàn)該決策面在特征空間中的位置 n當(dāng)w0=0時(shí)，該決策面過(guò)特征空間坐標(biāo)系原點(diǎn)n而w00時(shí)，則w0/|W|表示了坐標(biāo)原點(diǎn)到該決策面的距離。 線性判別函數(shù)的基本概念線性判別函數(shù)的基本概念n線性方程向量表示形式的補(bǔ)充說(shuō)明n二維空間直線方程: w2X2+w1X1+w0=0 nw2X2+w1X1是向量(w1,w2)和(X1,X2)的點(diǎn)集n注意:一條直線可以對(duì)應(yīng)無(wú)窮多個(gè)直線方程線性判別函數(shù)的基本概念n線性方程的規(guī)一化表示方法n我們定義 n則直線方程也可表示為:但參數(shù)向量模|W|為1 而WTX就是直線上任一點(diǎn)到W向量的投影 廣義線性判別函數(shù) n線性判別函數(shù)不能用于稍

8、復(fù)雜的情況n例如:欲設(shè)計(jì)這樣一個(gè)一維樣本的分類(lèi)器，使其性能為：用線性判別函數(shù)顯然就無(wú)能為力了 圖像表示圖像表示返回廣義線性判別函數(shù)n設(shè)計(jì)新判別函數(shù)n辨別函數(shù):g(x)(x-a)(x-b) n相應(yīng)的決策規(guī)則:能達(dá)到所要求的分類(lèi)效果，不再是x的線性函數(shù)，而是一個(gè)二次函數(shù) 辨別函數(shù)圖像表示廣義線性判別函數(shù) n線性判別函數(shù)優(yōu)點(diǎn)n具有形式簡(jiǎn)單n計(jì)算方便的優(yōu)點(diǎn)n已被充分研究 n希望能將其用適當(dāng)方式擴(kuò)展至原本適宜非線性判別函數(shù)的領(lǐng)域 廣義線性判別函數(shù) n廣義線性判別函數(shù)n選擇一種映射XY，即將原樣本特征向量X映射成另一向量Y，從而可以采用線性判別函數(shù)的方法。例如對(duì)于二次函數(shù)情況，其一般式可表示成 如果我們采

9、用映射xY，使廣義線性判別函數(shù) n廣義線性判別函數(shù)n則判別函數(shù)g(x)又可表示成n此時(shí)g(x)被稱(chēng)為廣義線性判別函數(shù)，a稱(chēng)為廣義權(quán)向量。 _廣義線性判別函數(shù)The mapping y = (1,x,x2)t takes a line and transforms it to a parabola in three dimensions.A plane splits the resulting y-space into regions corresponding to2 categories廣義線性判別函數(shù)n廣義線性判別函數(shù)n按照這種原理，任何形式的高次判別函數(shù)都可轉(zhuǎn)化成線性判別函數(shù)來(lái)處理。n這

10、種處理非線性分類(lèi)器的方法，在支持向量機(jī)中得到充分的研究。n產(chǎn)生問(wèn)題: 維數(shù)會(huì)增加很多 廣義線性判別函數(shù) n一種特殊的映射方法 n將X增廣至 廣義線性判別函數(shù) n一種特殊的映射方法 n并將g(x)中的W向量與w0統(tǒng)一表示成其中w1，w2，w3.wd為向量w各分量 廣義線性判別函數(shù) n一種特殊的映射方法n則線性判別函數(shù)g(X)可以表示成 這是廣義線性判別函數(shù)的一個(gè)特例 被稱(chēng)為增廣樣本向量，稱(chēng)為增廣權(quán)向量。 廣義線性判別函數(shù)n一種特殊的映射方法n這樣,特征空間增加了一維，但保持了樣本間的歐氏距離不變n對(duì)于分類(lèi)效果也與原決策面相同n只是在Y空間中決策面是通過(guò)坐標(biāo)原點(diǎn)的，這在分析某些問(wèn)題時(shí)具有優(yōu)點(diǎn) 廣義

11、線性判別函數(shù)n例 一維特征空間的分類(lèi)器 n其決策面方程為： x-c=0 n經(jīng)齊次簡(jiǎn)化后可得： 一維空間中為一個(gè)點(diǎn) 此時(shí)在二維空間中決策面為一過(guò)原點(diǎn)的直線 廣義線性判別函數(shù)線性分類(lèi)器設(shè)計(jì)步驟 n線性分類(lèi)器設(shè)計(jì)任務(wù)n在給定樣本集 條件下，確定線性判別函數(shù)的各項(xiàng)系數(shù):n關(guān)鍵問(wèn)題:n確定所需的準(zhǔn)則函數(shù)，n用最優(yōu)化技術(shù)確定準(zhǔn)則函數(shù)的極值解W*及W*0 ，或增廣權(quán)向量a*。_線性分類(lèi)器設(shè)計(jì)步驟 n線性分類(lèi)器設(shè)計(jì)步驟n1 按需要確定一準(zhǔn)則函數(shù)J。 n2 確定準(zhǔn)則函數(shù)J達(dá)到極值時(shí)W*及W*0的具體數(shù)值，從而確定判別函數(shù)，完成分類(lèi)器設(shè)計(jì)。Fisher線性判別函數(shù)n簡(jiǎn)介nFisher線性判別函數(shù)是研究這類(lèi)判別函數(shù)

12、中最有影響的方法之一。n對(duì)線性判別函數(shù)的研究就是從R.A.Fisher在1936年發(fā)表的論文開(kāi)始的。Fisher線性判別函數(shù)nFisher線性判別函數(shù)基本原理n設(shè)計(jì)線性分類(lèi)器首先要確定準(zhǔn)則函數(shù)準(zhǔn)則函數(shù)，然后再利用訓(xùn)練樣本集確定該分類(lèi)器的參數(shù)，以求使所確定的準(zhǔn)則達(dá)到最佳。 n維數(shù)問(wèn)題: 降低維數(shù)n線性判別函數(shù)把d維空間映射到1維空間Fisher線性判別函數(shù)nFisher線性判別函數(shù)基本原理n如果我們只考慮各分量的線性加權(quán)和，則它是各樣本向量與向量W的向量點(diǎn)積。 n如果向量W的幅度為單位長(zhǎng)度，則線性加權(quán)和又可看作各樣本向量在向量W上的投影。 nFisher的基本問(wèn)題n在1維直線上不一定能夠分開(kāi)樣本

13、n希望在1維直線上不同類(lèi)別的樣本分得越開(kāi)越好n如何找到這條最好的、最易于分類(lèi)的投影線Fisher線性判別函數(shù)nFisher線性判別函數(shù)基本原理Fisher線性判別函數(shù)基本原理例nFisher準(zhǔn)則就是要找到一個(gè)最合適的投影軸，使兩類(lèi)樣本在該軸上投影的交迭部分最少，從而使分類(lèi)效果為最佳。n分析w1方向之所以比w2方向優(yōu)越，可以歸納出這樣一個(gè)準(zhǔn)則 n向量W的方向選擇應(yīng)能使兩類(lèi)樣本投影的均值之差盡可能大些 n而使類(lèi)內(nèi)樣本的離散程度盡可能小這就是Fisher準(zhǔn)則函數(shù)的基本思路。 Fisher線性判別函數(shù)n基本參量n樣本在d維特征空間的一些描述量。(1) 各類(lèi)樣本均值向量mi (2) 樣本類(lèi)內(nèi)離散度矩陣S

14、i與總類(lèi)內(nèi)離散度矩陣Sw Fisher線性判別函數(shù)n基本參量n樣本在d維特征空間的一些描述量。(3) 樣本類(lèi)間離散度矩陣Sb Fisher線性判別函數(shù)n基本參量n在一維Y空間(1) 各類(lèi)樣本均值(2) 樣本類(lèi)內(nèi)離散度 和總類(lèi)內(nèi)離散度 Fisher線性判別函數(shù)nFisher準(zhǔn)則函數(shù)但是上式并不是W的顯函數(shù)，需進(jìn)一步化為W的顯函數(shù)。 需要進(jìn)一步演化 Fisher線性判別函數(shù)nFisher準(zhǔn)則函數(shù)式中的 為:因而 Fisher線性判別函數(shù)nFisher準(zhǔn)則函數(shù)同樣 也可推出與W的關(guān)系 因此 Fisher線性判別函數(shù)nFisher準(zhǔn)則函數(shù)代入 ，得Fisher線性判別函數(shù)n最佳W值的確定n最佳W值的確

15、定實(shí)際上就是對(duì)JF(W)求取其達(dá)極大值時(shí)的W* n對(duì)于這個(gè)問(wèn)題可以采用拉格朗日乘子算法解決 n為此可設(shè)計(jì)一拉格朗日函數(shù)Fisher線性判別函數(shù)n最佳W值的確定n向量W*就是使Fisher準(zhǔn)則函數(shù)JF(W)達(dá)極大值的解，n也就是按Fisher準(zhǔn)則將d維X空間投影到一維Y空間的最佳投影方向， n該向量W*的各分量值是對(duì)原d維特征向量求加權(quán)和的權(quán)值 圖例Fisher線性判別函數(shù)n判別函數(shù)的確定n目前的問(wèn)題討論了線性判別函數(shù)加權(quán)向量W的確定方法討論了使Fisher準(zhǔn)則函數(shù)極大的W*的計(jì)算方法判別函數(shù)中的另一項(xiàng)w0尚未確定Fisher線性判別函數(shù)n判別函數(shù)的確定n確定w0有以下幾種方法或 或當(dāng)P(w1)

16、與P(w2)已知時(shí)可用Fisher線性判別函數(shù)n判別函數(shù)的確定當(dāng)W0確定之后，則可按以下規(guī)則分類(lèi)， 感知準(zhǔn)則函數(shù)n簡(jiǎn)介n感知準(zhǔn)則函數(shù)是五十年代由Rosenblatt提出的一種自學(xué)習(xí)判別函數(shù)生成方法，n由于Rosenblatt企圖將其用于腦模型感知器，因此被稱(chēng)為感知準(zhǔn)則函數(shù)。n其特點(diǎn)是隨意確定的判別函數(shù)初始值，在對(duì)樣本分類(lèi)訓(xùn)練過(guò)程中逐步修正直至最終確定。感知準(zhǔn)則函數(shù)設(shè)計(jì)線性分類(lèi)器是一種十分重要的方法，是學(xué)習(xí)的重點(diǎn)。 感知準(zhǔn)則函數(shù)n線性決策面方程另外的形式n感知準(zhǔn)則函數(shù)使用增廣樣本向量與增廣權(quán)向量 nWT+w0=0 改成 aTY=0 感知準(zhǔn)則函數(shù)在兩類(lèi)別情況下，判別準(zhǔn)則是： 為簡(jiǎn)單起見(jiàn)，我們不考慮

17、g(X)0的情況。 為了討論原理方便，這一節(jié)在線性可分條件下討論問(wèn)題，并且只談兩類(lèi)識(shí)別問(wèn)題。 感知準(zhǔn)則函數(shù)n線性可分 n線性可分是說(shuō)該訓(xùn)練樣本集中的兩類(lèi)樣本可以用一個(gè)線性分界面正確無(wú)誤的分開(kāi)。n在線性可分條件下，廣義權(quán)向量a合適的話應(yīng)有： 感知準(zhǔn)則函數(shù)為了方便起見(jiàn)，如果我們令 則合適的a能使所有的Y滿足需要解決的問(wèn)題: 找到滿足上式的aT_例感知準(zhǔn)則函數(shù)返回感知準(zhǔn)則函數(shù)返回感知準(zhǔn)則函數(shù)n分析n根據(jù)訓(xùn)練樣本確定增廣權(quán)向量 an在給定一個(gè)規(guī)范化增廣樣本集Y1,YN的條件下，對(duì)于任何一個(gè)增廣權(quán)向量a ，可計(jì)算n顯然如果該向量是一個(gè)能將此樣本集正確分類(lèi)的增廣權(quán)向量，則應(yīng)有 _感知準(zhǔn)則函數(shù)n分析n而對(duì)可

18、導(dǎo)致錯(cuò)分類(lèi)的增廣權(quán)向量，則必有若干個(gè)yi ,使 n我們令被錯(cuò)分類(lèi)的規(guī)范化增廣樣本組成的集用yk表示，并定義一準(zhǔn)則函數(shù) 感知準(zhǔn)則函數(shù)n分析n則能將該樣本集正確分類(lèi)的增廣權(quán)向量a 使得n即達(dá)到a極小值。 n因此確定向量的問(wèn)題變?yōu)榍髽O小值的問(wèn)題 n這個(gè)準(zhǔn)則函數(shù) 就是感知準(zhǔn)則函數(shù) _感知準(zhǔn)則函數(shù)n求準(zhǔn)則函數(shù)的極小值n可以采用迭代法進(jìn)行n一個(gè)常用的方法是梯度下降算法n即對(duì)第k次迭代值，求其梯度向量，n并令迭代向量沿此負(fù)梯度向量方向修正，可以較快速度到達(dá)其極小值 感知準(zhǔn)則函數(shù)n求準(zhǔn)則函數(shù)的極小值n將準(zhǔn)則函數(shù)對(duì)a求偏導(dǎo)數(shù)，得 n可見(jiàn)感知準(zhǔn)則函數(shù)的梯度向量是所有被錯(cuò)分類(lèi)的規(guī)范化增廣樣本向量之和n將迭代公式寫(xiě)成_步長(zhǎng)系數(shù) 感知準(zhǔn)則