模式識別-第4章-線性判別函數(shù)

1、模式識別:線性判別函數(shù)第4章 線性判別函數(shù)目錄4.1引言4.2Fisher（重點）4.3感知準則函數(shù)（重點）4.4最小平方誤差準則函數(shù)4.5分類器錯誤率估計（重點）4.6多類問題（重點）4.7分段線性判別函數(shù)（難點）4.1 引言MAXg1.g2gc.x1x2xna(x)訓練樣本集樣本類條件概率密度分布決策規(guī)則：判別函數(shù)決策面方程分類器功能結構貝葉斯分類器：實際問題中貝葉斯分類器的缺陷實際問題中并不一定具備獲取準確統(tǒng)計分布的條件！#樣本不足#樣本分布未知能否基于樣本直接確定判別函數(shù)和決策面?訓練樣本集樣本類條件概率密度分布決策規(guī)則：判別函數(shù)決策面方程？直接確定判別函數(shù)方法基于樣本的直接確定判別函

2、數(shù)方法：針對各種不同的情況，使用不同的準則函數(shù)，設計出滿足這些不同準則要求的分類器。這些準則的“最優(yōu)”并不一定與錯誤率最小相一致：次優(yōu)分類器。 訓練樣本集決策規(guī)則：判別函數(shù)決策面方程選擇最佳準則最簡單的判別函數(shù)：線性判別函數(shù)x是樣本向量，即樣本在d維特征空間中的描述， w是權向量，w0是一個常數(shù)(閾值權)。兩類問題的分類決策規(guī)則:線性判別函數(shù)的幾何意義決策面(decision boundary)H方程：g(x)=0向量w是決策面H的法向量g(x)是點x到?jīng)Q策面H的距離的一種代數(shù)度量x1x2wxxprH: g=0廣義線性判別函數(shù)例：設計一個一維分類器的判別函數(shù)， 使其功能為： 它是線性判別函數(shù)嗎

3、？否廣義線性判別函數(shù)沒有任何一個線性判別函數(shù)能解決上述問題。線性判別函數(shù)是形式最為簡單的判別函數(shù)，但是它不能用于復雜情況（線性不可分問題）。那么復雜的情況怎么辦？（1）非線性判別函數(shù)（2）線性判別函數(shù)（廣義）廣義線性判別函數(shù)二次函數(shù)的一般形式：g(x)又可表示成： 空間映射XY原理：空間映射XY稱為廣義線性判別函數(shù)按照上述原理，任何非線性函數(shù)g(x)用級數(shù)展開成高次多項式后，都可轉化成線性判別函數(shù)來處理。廣義線性判別函數(shù)的性能優(yōu)點：解決了普通線性判別函數(shù)不能解決的問題，把高次判別函數(shù)化為線性判別函數(shù)。缺點：維數(shù)增加，可能導致維數(shù)災難。廣義線性判別函數(shù)的一個特例（重點）一種特殊映射方法：增廣樣本

4、向量y與增廣權向量a線性判別函數(shù)的簡化： 在Y空間中決策面H通過坐標原點，這在分析某些問題時具有優(yōu)點，因此經(jīng)常用到。 增廣樣本向量使特征空間增加了一維，但保持了樣本間的歐氏距離不變，對于分類效果也與原決策面相同。 線性分類器設計步驟（重點）主要步驟：收集訓練數(shù)據(jù)集D=x1,x2,xN按需要確定一個準則函數(shù)J(D,w,w0)或J(D,a)，其值反映分類器的性能，其極值解對應于“最好”決策。用最優(yōu)化技術求準則函數(shù)J的極值解w*，w*或a*。最終，得到線性判別函數(shù)，完成分類器設計習題：已知兩類問題的樣本集中，有兩個樣本。 屬于類， 屬于類，對它們進行增廣后，這兩個樣本的增廣樣本分別為 =_, =_。

5、廣義線性判別函數(shù)主要是利用_原理解決_問題，利用廣義線性判別函數(shù)設計分類器可能導致_。線性分類器設計步驟？線性判別函數(shù)g(x)的幾何表示是：點x到?jīng)Q策面H的_。增廣樣本向量使特征空間增加了_（一、二、三、大于三）維，但樣本在新的空間中保持了樣本間的_不變，對于分類效果也與原決策面相同。 在新的空間中決策面H通過坐標_。目錄4.1引言4.2Fisher（重點）4.3感知準則函數(shù)（重點）4.4最小平方誤差準則函數(shù)4.5分類器錯誤率估計（重點）4.6多類問題（重點）4.7分段線性判別函數(shù)（難點）費希爾（Fisher, Ronald Aylmer）是英國統(tǒng)計學家、遺傳學家.1890年生于倫敦；1962

6、年卒于澳大利亞阿德雷德. 1909年靠一筆助學金進入劍橋大學 1919年到加拿大務農(nóng)。農(nóng)業(yè)試驗站作統(tǒng)計工作費希爾還是一位遺傳學家、優(yōu)生學家，他是統(tǒng)計遺傳學的創(chuàng)始人之一，他用統(tǒng)計方法研究生物學，研究突變、連鎖、自然淘汰、近親婚姻、移居等因素對總體遺傳特性的影響. 費希爾是使統(tǒng)計學成為一門有堅實理論基礎并獲得廣泛應用的主要統(tǒng)計學家之一 。4.2 Fisher線性判別線性判別函數(shù)y=g(x)=wTx:樣本向量x各分量的線性加權樣本向量x與權向量w的向量點積如果| w |=1，則視作向量x在向量w上的投影 Fisher準則的基本原理：找到一個最合適的投影軸，使兩類樣本在該軸上投影之間的距離盡可能遠，而

7、每一類樣本的投影盡可能緊湊，從而使分類效果為最佳。x1w1決策面w2x2Fisher線性判別圖例W1，W2哪個向量好？類間離散度類內(nèi)離散度類間離散度類內(nèi)離散度一維Y空間樣本分布的描述量各類樣本均值樣本類內(nèi)離散度和總類內(nèi)離散度樣本類間離散度 以上定義描述d維空間樣本點到一維向量投影的分散情況，因此也就是對某向量w的投影在w上的分布。樣本離散度的定義與隨機變量方差相類似 d維空間樣本分布的描述量各類樣本均值向量mi樣本類內(nèi)離散度矩陣Si與總類內(nèi)離散度矩陣Sw 樣本類間離散度矩陣Sb：離散矩陣在形式上與協(xié)方差矩陣很相似，但協(xié)方差矩陣是一種期望值，而離散矩陣只是表示有限個樣本在空間分布的離散程度樣本與

8、其投影統(tǒng)計量間的關系：均值向量樣本x與其投影y的統(tǒng)計量之間的關系：樣本與其投影統(tǒng)計量間的關系：類間離散度矩陣樣本x與其投影y的統(tǒng)計量之間的關系：樣本與其投影統(tǒng)計量間的關系：樣本類內(nèi)離散度矩陣Fisher準則函數(shù)評價投影方向w的原則，使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開，類內(nèi)樣本投影盡可能密集的要求Fisher準則函數(shù)的定義：Fisher最佳投影方向的求解Fisher最佳投影方向的求解采用拉格朗日乘子算法解決 m1-m2是一向量，對與(m1-m2)平行的向量投影可使兩均值點的距離最遠。但是如從使類間分得較開，同時又使類內(nèi)密集程度較高這樣一個綜合指標來看，則需根據(jù)兩類樣本的分布離散

9、程度對投影方向作相應的調(diào)整，這就體現(xiàn)在對m1-m2 向量按Sw-1作一線性變換，從而使Fisher準則函數(shù)達到極值點判別函數(shù)的確定前面討論了使Fisher準則函數(shù)極大的d維向量w*的計算方法，判別函數(shù)中的另一項w0（閾值）可采用以下幾種方法確定： 分類規(guī)則:Fisher公式的推導習題Fisher準則的基本原理為：找到一個最合適的投影軸，使_在該軸上投影之間的距離盡可能遠，而_的投影盡可能緊湊，從而使分類效果為最佳。Fisher準則函數(shù)的定義為 =_。Fisher方法中，樣本類內(nèi)離散度矩陣Si與總類內(nèi)離散度矩陣Sw 分別為_和_。Fisher方法主要利用投影向量w，將所有d維樣本x投影的一維樣本

10、y（即，y=wTx）來實現(xiàn)對樣本的有效分類。已知一維樣本類間離散度 ，d維樣本類間離散度矩陣為 ，證明它們之間的關系為利用Lagrange乘子法使Fisher線性判別的準則函數(shù)極大化，最終可以得到的判別函數(shù)權向量 = _。 敘述Fisher算法的基本原理。 Fisher準則函數(shù)的定義為 。試利用Lagrange乘子法使Fisher線性判別的準則函數(shù)極大化來得到的判別函數(shù)權向量。描述獲得這個權向量的推導過程。目錄4.1引言4.2Fisher（重點）4.3感知準則函數(shù)（重點）4.4最小平方誤差準則函數(shù)4.5分類器錯誤率估計（重點）4.6多類問題（重點）4.7分段線性判別函數(shù)（難點）4.3 感知準則

11、函數(shù)感知準則函數(shù)是五十年代由羅森勃拉特(Rosenblatt) 提出的一種自學習判別函數(shù)生成方法由于Rosenblatt企圖將其用于腦模型感知機（perceptron），因此被稱為感知準則函數(shù)。其特點是隨意確定權向量初始值，在對樣本分類訓練過程中逐步修正權向量直至最終確定。1958年美國心理學家羅森勃拉特（Rosenblatt）發(fā)表著名的論文：感知器：腦的組織與信息存儲的概率模型。首次把人工神經(jīng)網(wǎng)絡的研究用于工程實踐。提出了著名的感知器模型，成為20世紀80年代影響巨大的多層感知器的基礎。1961年，明斯基證明了羅森勃拉特的感知器的缺陷：只能完成線性可分的模式分類，不能完成諸如“異或”，或者非

12、線性的分類。神經(jīng)網(wǎng)絡的研究從此走了一段彎路，研究經(jīng)費幾乎沒有。1986年，多層感知器的反向傳播方法，克服了感知器的主要缺陷?；靖拍睿阂?guī)范化增廣樣本（重點）線性可分性：訓練樣本集中的兩類樣本可以用一個線性分界面正確分開。在線性可分條件下，對合適的(廣義)權向量a應有：規(guī)范化樣本向量 ：Y 是規(guī)范化增廣樣本將第二類樣本取其反向向量 解向量與解區(qū)滿足 的權向量稱為解向量，記為解區(qū):解向量不止一個，而是由無窮多個解向量組成的解，稱這樣的區(qū)域為解區(qū)。通常為了使解向量更可靠，需要對解區(qū)進行限制。（引入余量b0，尋找 的解向量）解向量與解區(qū)感知機準則函數(shù)及其梯度下降算法對于任何一個增廣權向量a ，對樣本y

13、正確分類，則有：aTy0 對樣本y錯誤分類，則有：aTy0引入余量、不等式轉化為等式引入余量(目標向量) b=b1, b2, , bNT， bi任意給定正常數(shù) aTyi = bi 0N個線性方程的的矩陣表示：平方誤差準則函數(shù)定義誤差向量 e=Ya-b定義平方誤差準則函數(shù)Js(a):平方誤差準則函數(shù)最小二乘近似解（MSE解）：MSE方法的思想：以最小平方誤差為準則求最優(yōu)權向量MSE準則函數(shù)的偽逆解Y的偽逆矩陣MSE方法與Fisher方法的關系與Fisher方法的關系：N1個N2個MSE解等價于Fisher解MSE方法與Bayes方法的關系當N，b=uN= 1,1, , 1T 時，則它以最小均方誤

14、差逼近Bayes判別函數(shù)：MSE方法偽逆解帶來的問題a*=Y+b Y+=(YTY)-1YT 問題1：計算量大 問題2：YTY有時非奇異實際中常用梯度下降法來降低計算復雜度MSE方法的迭代解實際中常用梯度下降法：批量樣本修正法單樣本修正法目錄4.1引言4.2Fisher（重點）4.3感知準則函數(shù)（重點）4.4最小平方誤差準則函數(shù)4.5分類器錯誤率估計（重點）4.6多類問題（重點）4.7分段線性判別函數(shù)（難點）分類器錯誤率估計categoricalcategoricalcontinuousclassTestSetTraining SetModelLearn Classifier錯誤率估計第一種情況

15、已設計好分類器時，錯誤率的估計即用錯分測試樣本數(shù)與總測試樣本數(shù)的比值來估計分類器的錯誤率。錯誤率估計第二種情況未設計好分類器時，錯誤率的估計。這種情況在設計分類器階段和檢驗分類器階段的樣本使用上會存在問題。樣本競爭設計分類器階段和檢驗分類器階段都要用到帶有類別標號的樣本（訓練樣本）。categoricalcategoricalcontinuousclassTestSetTraining SetModelLearn Classifier粗糙的錯誤率估計方案粗糙的錯誤率估計方案：樣本重復使用：N樣本既用于設計分類器，又用于估計分類器錯誤率缺點：樣本相交度高。訓練分類器的樣本用于檢驗會使分類效果偏好

16、，導致錯誤率估計不準確！樣本分為不相交的兩個部分：一部分樣本用于設計分類器，另一部分用于估計分類器錯誤率缺點：樣本利用率低，較少的樣本參與分類器設計和檢驗，導致錯誤率估計不準確！留一法留一法：N個樣本取N-1個樣本為訓練集，設計分類器。剩下的一個樣本作為測試集，輸入到分類器中，檢驗是否錯分。然后放回樣本，重復上述的過程，直到N次，即每個樣本都做了一次測試。統(tǒng)計被錯分的樣本總數(shù)k， 作為錯誤率的估計率。TestSetTraining SetModelLearn Classifier10個樣本的留一法例子第1次第2次第10次。判斷結果：留一法性能留一法有效的利用了訓練樣本，而且很大程度上降低了樣本

17、相關性。對錯誤率的估計更準確。但為了估計分類器錯誤率需訓練N次分類器，計算量大。 參與設計的樣本 參與錯誤率估計的樣本（N-1）（N）M-重交叉驗證m-重交叉驗證：N個樣本被劃分成m個不相交集合，每組有N/m個樣本在m個組中取m-1個組的樣本作為訓練集，設計分類器。剩下的一組樣本作測試集，輸入到分類器中檢驗，統(tǒng)計錯分數(shù)k。然后放回，重復上述的過程，直到m次。設ki（i=1,m)是第i次測試的錯分數(shù)，則TestSetTraining SetModelLearn Classifier10個樣本的m-重交叉驗證例子（m=5）第1次第2次第5次。判斷結果：分組方法性能留一法有效的利用了訓練樣本，而且很

18、大程度上降低了樣本相關性。對錯誤率的估計更準確。但為了估計分類器錯誤率需訓練N次分類器，計算量大。 參與設計的樣本 參與錯誤率估計的樣本m-重交叉驗證與留一法相比減少了大量的計算量。隨著m值減少，訓練分類器時的樣本減少，導致設計的分類器模型質量下降，將降低錯誤率的估計準確率。總體上看，錯誤率的估計相對較好。 參與設計的樣本 參與錯誤率估計的樣本（N-1）（N）（N）（N-N/m）Weka進行分類器錯誤率估計目錄4.1引言4.2Fisher（重點）4.3感知準則函數(shù)（重點）4.4最小平方誤差準則函數(shù)4.5分類器錯誤率估計（重點）4.6多類問題（重點）4.7分段線性判別函數(shù)（難點）4.6 多類問題

19、兩類別問題可以推廣到多類別問題i/i 法：將C類別問題化為(C-1)個兩類（第i類與所有非i類）問題，按兩類問題確定其判別函數(shù)與決策面方程 i/j 法：將C類中的每兩類別單獨設計其線性判別函數(shù)，因此總共有C(C-1)/2個線性判別函數(shù) R1R3R21非12非2R1R3R21213324.6 多類問題兩類別問題可以推廣到多類別問題i/i 法：將C類別問題化為(C-1)個兩類（第i類與所有非i類）問題，按兩類問題確定其判別函數(shù)與決策面方程 R1R3R21非12非2121非2非12非2非1123組合后的分類結果：4.6 多類問題兩類別問題可以推廣到多類別問題i/j 法：將C類中的每兩類別單獨設計其線

20、性判別函數(shù)，因此總共有C(C-1)/2個線性判別函數(shù) R1R3R2121332111組合后的分類結果：211131321333212221323222333兩類問題分類器解決多類問題方法的性能優(yōu)點：設計思想簡單，容易實現(xiàn)。缺點： （1）需要訓練的子分類器或參數(shù)多，效率低。 （2）無法確定類別的區(qū)域多。造成該問題的根本原因是將多類問題看成了多個兩類問題來解決。這樣，必然造成陰影區(qū)域的出現(xiàn)。如果想根本解決這種問題，需要使用多類問題的分類器而不是兩類問題的分類器。目錄4.1引言4.2Fisher（重點）4.3感知準則函數(shù)（重點）4.4最小平方誤差準則函數(shù)4.5分類器錯誤率估計（重點）4.6多類問題（

21、重點）4.7分段線性判別函數(shù)（難點）4.7 分段線性判別函數(shù) 有些復雜模式識別問題不是線性可分的，需使用非線性的分類方法分段線性判別函數(shù)：一種特殊的非線性判別函數(shù)，它的決策面是若干超平面R1R3R2IIIIIII: 線性判別II：分段線性判別III: 二次判別基于距離的分段線性判別函數(shù) 最小距離分類器： 把各類別樣本特征的均值向量作為各類的代表點(prototype) ，根據(jù)待識別樣本到各類別代表點的最小距離判別其類別。決策面是兩類別均值連線的垂直平分面m1m2xg(x)=0基于距離的分段線性判別函數(shù) 分段線性距離分類器： 將各類別劃分成相對密集的子類，每個子類以它們的均值作為代表點，然后按最小距離分類 基于距離的分段線性判別函數(shù) 判別函數(shù)定義：i有l(wèi)i個子類，即屬于i 的決策域Ri分成li個子域Ri1, Ri2, Rili)，每個子區(qū)域用均值mik代表點判別規(guī)則：性能優(yōu)點： （1）可以解決線性不可分問題。 （2）比二次判別函數(shù)簡單。缺點： （1）確定子集數(shù)目難。 （2）對一些情況不適用 （3）兩類問題變?yōu)槎囝悊栴}，使得分類問題