第2章 線性判別函數(shù)

第2章線性判別函數(shù)

2.1線性判別函數(shù)和決策面2.2感知準則函數(shù)2.3最小平方誤差準則函數(shù)2.4

Fisher線性判別函數(shù)2.5多類情況下的線性判別函數(shù)2.6分段線性判別函數(shù)2.1線性判別函數(shù)和決策面線性判別函數(shù)是決策論模式識別方法中的一種重要的基本方法，是形式最簡單的判別函數(shù)，由于它具有計算簡單，在一定條件下能夠?qū)崿F(xiàn)最優(yōu)分類的性質(zhì)，因此在實際中得到了廣泛的應用。此外，許多其它決策論識別方法也可用判別函數(shù)來研究（非線性判別函數(shù)），它也是研究神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)?，F(xiàn)在我們就從線性判別函數(shù)開始介紹統(tǒng)計模式識別的各種方法。返回本章首頁在統(tǒng)計模式識別方法中，首先應把能代表模式的那些特征抽取出來，構(gòu)成一個代表這個模式的特征向量，表示為當我們觀察待分類模式時，每次觀察到的樣本都是不同的，他們可以看成是隨機產(chǎn)生的。所以每次抽取到的模式特征都應看成是隨機變量，從而代表這些模式的n維向量也應是隨機向量。下面看一個三類模式例子，如圖所示。三類模式可用邊界線AD、BD和CD分開。返回本章首頁返回本章首頁所以，如果根據(jù)以往大量的觀察，知道模式類別的分布，從而能找出n維空間中模式類之間的分界，就能解決模式的分類問題。這在實際上是一個通過給定樣本的學習過程。簡便起見，在本章中我們假定抽取到的模式樣本的邊界是“整齊”而不混雜的，而且以后遇到的待分類模式基本上不超過學習樣本的分布范圍，從而利用這些樣本得出的分類邊界是無誤差的。為找出這些模式之間的分界面，可以利用判別函數(shù)來進行。對于n維空間中的c個模式類別各給出一個由n

個特征組成的單值函數(shù)，這叫做判別函數(shù)。在c

類的情況下，我們共有c個判別函數(shù)，記為返回本章首頁判別函數(shù)的性質(zhì)假如一個模式X

屬于第i

類，則有而如果這個模式在第i

類和第j

類的分界面上，則有事實上，這是由n

維模式降為1維或1個數(shù)的一種變換。線性判別函數(shù)是所有模式特征的線性組合，表示為返回本章首頁二類情況下的線性判別函數(shù)令用其可以構(gòu)造一個二類模式的線性分類器，如圖所示。返回本章首頁可將其任意分類，或拒絕返回本章首頁二類情況下，決策面與模式向量的幾何關(guān)系是決策面方程，它是兩類模式的分界，對于二維空間的情況，它是一條直線。下面，對一些關(guān)系作幾何解釋，如圖所示。返回本章首頁返回本章首頁2.2

感知準則函數(shù)2.2.1幾個基本概念2.2.2感知準則函數(shù)及其梯度下降算法返回本章首頁1線性可分性討論如下的兩個問題①對于4個二維樣本，其在平面上的分布如圖所示。若把每個樣本任意分到兩種類別之一或，舉出其中的兩種線性不可分情況。②驗證

N

個d維樣本線性可分的概率閥值是返回本章首頁2.2.1幾個節(jié)本概念2樣本的規(guī)范化二類模式的線性分類器的決策規(guī)則為引入增廣模式向量和廣義權(quán)向量返回本章首頁可將其任意分類，或拒絕代入，決策規(guī)則可變?yōu)槿】傻媒凶鲆?guī)范化增廣樣本向量，為方便起見仍用表示3解向量和解區(qū)返回本章首頁返回本章首頁返回本章首頁返回本章首頁對解區(qū)的限制對解區(qū)加以限制的目的在于使解向量更可靠。因為越靠近解區(qū)中間的解向量越能對新的樣本正確分類。同時也可避免求解向量的算法不致收斂到解區(qū)邊界的某點上。為了解線性不等式（

已規(guī)范化

）需要構(gòu)造一個準則函數(shù)。這里我們介紹一種常用的準則函數(shù)即所謂的感知準則函數(shù)，定義為如下的形式：

是由于使用權(quán)向量而被誤分類的樣本集合。返回本章首頁2.2.2感知準則函數(shù)及其梯度下降算法也就是說，當對于某個向量，準則函數(shù)達到極小值的話，就是解權(quán)向量，這時沒有樣本被錯分類?，F(xiàn)在用最優(yōu)化方法——梯度下降算法尋找使達到極小值的解權(quán)向量。梯度下降算法基本思想函數(shù)在某點的梯度是一個向量，它的方向與過點的等量面的法線方向重合，指向增加的一方，是準則函數(shù)變化率最大的方向。反之，負梯度的方向則是函數(shù)減少得最快的方向。所以在求準則函數(shù)的極小值時，沿負梯度方向搜索有可能最快地找到極小值。返回本章首頁梯度下降算法的實現(xiàn)先任意選擇一個初始的權(quán)向量，計算上的梯度，從出發(fā)在最陡方向（負梯度）上移動一個距離以得到下一個權(quán)向量值，用迭代公式表示為請簡述梯度下降算法？

返回本章首頁梯度下降算法應用舉例——單樣本修正法參考教材P94，把樣本看作一個不斷重復出現(xiàn)的序列而逐個加以考慮，樣本組成的樣本序列為：返回本章首頁返回本章首頁返回本章首頁2.3最小平方誤差準則函數(shù)

2.2.1平方誤差準則函數(shù)及其偽逆解2.2.2MSE準則函數(shù)的梯度下降算法返回本章首頁前面我們介紹的感知器準則函數(shù)是在誤分類樣本的基礎(chǔ)上建立的，它要求對于所有樣本都能滿足不等式本節(jié)介紹的最小平方誤差準則函數(shù)，它是一個基于全體樣本的準則函數(shù)，要求滿足等式這樣就可以將原來解一組線性不等式的問題轉(zhuǎn)化為解一組線性方程組的問題。返回本章首頁2.3.1平方誤差準則函數(shù)及其偽逆解引入其中是規(guī)范化增廣樣本向量將寫成聯(lián)立方程組得形式①若是非奇異方陣，則可以得到解；②若是長方陣（一般為列滿秩），則是矛盾方程組，沒有精確解。定義誤差向量返回本章首頁引入其中是規(guī)范化增廣樣本向量將寫成聯(lián)立方程組得形式①若是非奇異方陣，則可以得到解；②若是長方陣（一般為列滿秩），則是矛盾方程組，沒有精確解存在。返回本章首頁定義誤差向量定義平方和準則函數(shù)為使廣義權(quán)向量為最優(yōu)，只需使平方和準則函數(shù)極小化，然后把相應的作為問題的解，稱其為矛盾方程組的最小二乘解（MSE解）。

返回本章首頁

返回本章首頁這里是一個維方陣，且常為非奇異；方陣稱為的偽逆（矩陣論里稱其為廣義逆），且具有以下性質(zhì)：①當為非奇異方陣時，的偽逆和它的逆相等②③一般來說返回本章首頁從上述推倒過程可以看出，MSE解依賴于向量，的不同選擇可以給予解以不同的性質(zhì)（參考教材P102）。返回本章首頁從前面的推導過程我們可以看到，用MSE方法按式的計算工作量很大，首先要求證明是非奇異的，然后計算，為維矩陣的逆。這樣，我們引入梯度下降算法以避免這種問題。誤差平方和準則函數(shù)的梯度返回本章首頁2.3.2MSE準則函數(shù)的梯度下降算法梯度下降算法為：（1）首先任意指定初始權(quán)向量；（2）如第

k步不能滿足要求

則按下式求第(k+1)步的權(quán)向量對于任意的正常數(shù)，算法得到的權(quán)向量序列收斂于使返回本章首頁2.4Fisher線性判別函數(shù)在以后的統(tǒng)計模式識別方法中，維數(shù)或特征數(shù)是一個很大的問題，因此，降低維數(shù)有時就成為處理實際問題的關(guān)鍵。Fisher線性判別函數(shù)法就是其中一種，是R.A.Fisher（1936）在他的一篇論文中提出來的，其基本思想是把d

維模式投影到一條通過原點的直線上，把維數(shù)壓縮到1。參照如圖所示的例子，進行分析。返回本章首頁返回本章首頁基于這個例子可以看到，投影線的方向起著至關(guān)重要的作用。下面著重討論如何從數(shù)學上尋求最優(yōu)的投影線方向。首先討論從d

維空間到1維空間的數(shù)學變換，從幾何上看，就是相對應的到方向為的直線上的投影。尋找最好的投影方向即是尋找最好的變換向量的問題。返回本章首頁為了使類別分離的好，應使各類模式投影均值彼此間相距盡可能大。第i類d

維樣本的均值樣本在直線上的投影的均值是投影的均值間的距離是返回本章首頁為了使類別分離得好，還應使同類模式的投影比較密集。用類內(nèi)離散度來度量。定義為總的類內(nèi)離散度為：它代表整個樣本集合中各類樣本投影的密集程度返回本章首頁這里建立一個準則函數(shù)，它能反映不同類別模式在直線上投影分離程度的好壞。綜合上述考慮，希望兩類模式投影均值之差越大越好；同時希望同類模式的投影內(nèi)部盡量密集。定義Fisher準則函數(shù)尋找使分子盡可能大，而分母盡可能小，也就是使盡可能大的作為投影方向。返回本章首頁將變?yōu)榈娘@函數(shù)返回本章首頁返回本章首頁稱為Rayleigh比,其具有以下性質(zhì)：①，a是一個實數(shù)；②的極值與的大小無關(guān)，只與的方向有關(guān)。下面求準則函數(shù)的極大值。將標量對向量求導并令其為零向量，注意到的分子分母均為標量，利用二次型關(guān)于向量求導的公式可得：返回本章首頁上式表明：是矩陣相應于特征值

的特征向量（本特值）。返回本章首頁由于我們的目的是尋求最好的投影方向，的比例因子對此并無影響，因此，可得返回本章首頁MSE最小平方誤差方法與Fisher線性判別的關(guān)系在此，我們將通過適當選擇b來說明MSE判別函數(shù)是和Fisher線性判別有直接聯(lián)系的。我們假設(shè)一組d維樣本集，其中個屬于類的樣本記為子集，其中個屬于類的樣本記為子集。進一步，得到增廣模式向量，并進行規(guī)范化。不失一般性，可以假設(shè)前個樣本屬于類，后個樣本屬于。這樣矩陣就可以寫成分塊矩陣返回本章首頁是個1的列向量，是一個矩陣，它的行是屬于。接下來，我們將證明MSE解和Fisher線性判別關(guān)系。返回本章首頁返回本章首頁返回本章首頁返回本章首頁對于任意的，向量都是在的方向上，則就有代入2.5多類情況下的線性判別函數(shù)前面我們重點討論了二類模式情況下的線性判別方法，不難把它們推廣到多類別的情況。可以把多類問題化為二類問題來解決，也可以直接按多類問題來解。1、按二類問題解①是把c類問題轉(zhuǎn)化為個二類模式的分類問題。其中第i個問題就是用線性判別函數(shù)把屬于類的模式同不屬于的模式分開。②是用次二類模式線性判別，每次只從樣本集中判別指定的二類的決策面。兩種方法都會產(chǎn)生模糊區(qū)域，結(jié)合下圖進行分析。返回本章首頁返回本章首頁返回本章首頁2按多類問題解（結(jié)合第一節(jié)內(nèi)容）如果不用區(qū)別二類問題的線性判別函數(shù)，可采用一般的c類線性判別函數(shù)：如果對于所有的，有則把模式歸到

類去而如果這個模式在第i

類和第j

類的分界面上，則有返回本章首頁返回本章首頁返回本章首頁線性機器的決策區(qū)域的特點（1）所有決策區(qū)域是凸的；（2）每個決策區(qū)域都是單連通的；（3）不存在拒絕分類的死區(qū)；返回本章首頁2.6分段線性判別函數(shù)以上我們介紹了線性判別函數(shù)，它的一個顯著的優(yōu)點是：算法簡單和具有“學習”的能力，就是說，給定分好類的樣本集后，能夠根據(jù)樣本“學習”，自動找到線性分界面。它的另一個優(yōu)點是：如果給定的分好類的n維模式樣本集是線性可分的，則基于感知準則函數(shù)的算法一定收斂。不足是：必須線性可分，得到的分界面是一個超平面，應用有限，對于比較復雜的問題，如果樣本不是線性可分時，就會導致較大的分類錯誤率。返回本章首頁返回本章首頁為了解決比較復雜的線性不可分樣本分類問題，提出了非線性判別函數(shù)，如圖的分界面Ⅱ所示，為超曲面，非線性判別函數(shù)計算復雜，實際應用上受到較大的限制。解決問題比較簡便的方法是采用多個線性分界面，將它們分段連接，用分段線性判別劃分去逼近分界的超曲面，如圖Ⅲ。其優(yōu)點是：由于它的各段都是超平面，有可能利用已知的線性判別函數(shù)來解決分類問題；