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

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

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

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

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

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

屬于第i

類(lèi)，則有而如果這個(gè)模式在第i

類(lèi)和第j

類(lèi)的分界面上，則有事實(shí)上，這是由n

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

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

N

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

已規(guī)范化

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

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

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

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

返回本章首頁(yè)

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

k步不能滿足要求

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

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

維空間到1維空間的數(shù)學(xué)變換，從幾何上看，就是相對(duì)應(yīng)的到方向?yàn)榈闹本€上的投影。尋找最好的投影方向即是尋找最好的變換向量的問(wèn)題。返回本章首頁(yè)為了使類(lèi)別分離的好，應(yīng)使各類(lèi)模式投影均值彼此間相距盡可能大。第i類(lèi)d

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

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

類(lèi)去而如果這個(gè)模式在第i

類(lèi)和第j

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