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

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

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

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

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

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

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

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

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

9、用映射xY，使廣義線性判別函數(shù) n廣義線性判別函數(shù)n則判別函數(shù)g(x)又可表示成n此時g(x)被稱為廣義線性判別函數(shù)，a稱為廣義權(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ù)來處理。n這

10、種處理非線性分類器的方法，在支持向量機中得到充分的研究。n產(chǎn)生問題: 維數(shù)會增加很多 廣義線性判別函數(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ù)的一個特例 被稱為增廣樣本向量，稱為增廣權(quán)向量。 廣義線性判別函數(shù)n一種特殊的映射方法n這樣,特征空間增加了一維，但保持了樣本間的歐氏距離不變n對于分類效果也與原決策面相同n只是在Y空間中決策面是通過坐標原點的，這在分析某些問題時具有優(yōu)點 廣義

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

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

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

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

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

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

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

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