線性判別函數(shù)

線性判別函數(shù)第1頁，共62頁，2023年，2月20日，星期二

在上一章中我們討論了貝葉斯決策理論和統(tǒng)計(jì)判別方法。從原理上說貝葉斯決策理論采用了在d維特征空間中樣本分布的最一般描述方式，即統(tǒng)計(jì)分布來描述，并且采用分類器中最重要的指標(biāo)——錯誤率作為產(chǎn)生判別函數(shù)和決策面的依據(jù)，因此它給出了最一般情況下適用的“最優(yōu)”分類器設(shè)計(jì)方法，對各種不同的分類器設(shè)計(jì)技術(shù)在理論上都有指導(dǎo)意義。但是直接使用貝葉斯決策理論需要首先得到有關(guān)樣本總體分布的知識，具體說來包括各類先驗(yàn)概率P(ω1)及類條件概率密度函數(shù)，從而可以計(jì)算出樣本的后驗(yàn)概率P(ω1|X)，并以此作為產(chǎn)生判別函數(shù)的必要數(shù)據(jù)，設(shè)計(jì)出相應(yīng)的判別函數(shù)與決策面。

第2頁，共62頁，2023年，2月20日，星期二3.1.1線形判別函數(shù)的基本概念

在一個d維的特征空間中,線性判別函數(shù)的一般表達(dá)式如下：其中，，稱為權(quán)向量是個常數(shù)，稱為閾值權(quán)。（3-1）第3頁，共62頁，2023年，2月20日，星期二在兩類情況下，僅用一個判別函數(shù)：判別規(guī)則：若,則,,則,,則可將x分到任一類,

或拒絕（3-2）第4頁，共62頁，2023年，2月20日，星期二方程g(x)=0定義了一個決策面。當(dāng)g(x)為線性函數(shù)時(shí)，這個決策面便是超平面。假設(shè)和都在決策面H上，則有或這表明，w和超平面H上任一向量正叫交，即w是H的法向量。（3-3）（3-4）第5頁，共62頁，2023年，2月20日，星期二判別函數(shù)g(x)可以看成是特征空間中某點(diǎn)x到超平面的距離的一種代數(shù)度量，見圖4.1。若把x表示成式中：是x在H上的投影向量；

r:是x到H的垂直距離；：是w方向上的單位向量。（3-5）第6頁，共62頁，2023年，2月20日，星期二

圖3.1線性判別函數(shù)第7頁，共62頁，2023年，2月20日，星期二將式（3-5）代入（3-1），可得

或?qū)懽魅魓為原點(diǎn)，則從原點(diǎn)到超平面的距離（3-6）（3-7）（3-8）第8頁，共62頁，2023年，2月20日，星期二3.1.2廣義線性判別函數(shù)圖3.2二次判別函數(shù)舉例第9頁，共62頁，2023年，2月20日，星期二線性判別函數(shù)是形式最為簡單的判別函數(shù)，但是它不能用于稍復(fù)雜一些的情況，例如，建立一個二次判別函數(shù)決策規(guī)則是二次判別函數(shù)可寫成適當(dāng)選擇從x到y(tǒng)的影射，則可把函數(shù)化成y的線性函數(shù)（3-9）（3-10）（3-11）第10頁，共62頁，2023年，2月20日，星期二

式中稱為廣義判別函數(shù)，叫做廣義權(quán)向量（3-12）第11頁，共62頁，2023年，2月20日，星期二

在Y空間定義了一通過原點(diǎn)的超平面Y空間中任意一點(diǎn)y到超平面的距離為其中Y叫做增廣樣本向量，a叫做增廣權(quán)向量。第12頁，共62頁，2023年，2月20日，星期二

將非線性函數(shù)用映射的方法變成線性函數(shù)的形式，如(3-11)，(3-12)式所示，但一個重要問題是維數(shù)會增加很多。用傳統(tǒng)方法處理模式識別問題是希望降低維數(shù)，而不希望增加維數(shù)，因此不提倡使用，但支持向量機(jī)卻注重它能將非線性分類問題轉(zhuǎn)化為線性分類問題，因而主張采用。第13頁，共62頁，2023年，2月20日，星期二3.1.3設(shè)計(jì)線性分類器的主要步驟

所謂設(shè)計(jì)線性分類器，就是利用訓(xùn)練樣本建立線性判別函數(shù)式（3-1）或廣義線性判別函數(shù)式（3-12）。設(shè)計(jì)線性分類器的過程實(shí)際就是找最好的w和w0的過程。第14頁，共62頁，2023年，2月20日，星期二設(shè)計(jì)線性分類器的主要步驟：1.訓(xùn)練樣本集常用x={x1,x2,…xn}表示，由訓(xùn)練樣本集x所確定的加權(quán)向量稱為解向量w*。2.確定一個準(zhǔn)則函數(shù)J,它必須滿足：

(1)J是樣本集和、或a的函數(shù)

(2)J的值能反映分類器的性能3.求出準(zhǔn)則函數(shù)的極值解和或。這樣就得到線性判別函數(shù)第15頁，共62頁，2023年，2月20日，星期二換一個方式說，設(shè)計(jì)線性分類器，是指所用的判別函數(shù)、分界面方程的類型已選定為線性類型，因此主要的設(shè)計(jì)任務(wù)是確定線性方程的兩個參數(shù)，一個是權(quán)向量W，另一個是閾值w0。為了使所設(shè)計(jì)的線性分類器在性能上要滿足一定的要求，這種要求通過一種準(zhǔn)則來體現(xiàn)，并且要表示成一種準(zhǔn)則函數(shù)，以便能通過將準(zhǔn)則函數(shù)值優(yōu)化的方法確定W與w0。第16頁，共62頁，2023年，2月20日，星期二3.2Fisher線性判別

由于線性判別函數(shù)易于分析，關(guān)于這方面的研究工作特別多。歷史上，這一工作是從R.A.Fisher的經(jīng)典論文（1936年）開始的。我們知道，在用統(tǒng)計(jì)方法進(jìn)行模式識別時(shí)，許多問題涉及到維數(shù)，在低維空間行得通的方法，在高維空間往往行不通。因此，降低維數(shù)就成為解決實(shí)際問題的關(guān)鍵。Fisher的方法，實(shí)際上涉及維數(shù)壓縮。第17頁，共62頁，2023年，2月20日，星期二

如果要把模式樣本在高(d)維的特征向量空間里投影到一條直線上，實(shí)際上就是把特征空間壓縮到一維，這在數(shù)學(xué)上容易辦到。另外，即使樣本在高維空間里聚集成容易分開的群類，把它們投影到一條任意的直線上，也可能把不同的樣本混雜在一起而變得無法區(qū)分。也就是說，直線的方向選擇很重要。

如上所述，設(shè)計(jì)線性分類器首先要確定準(zhǔn)則函數(shù)，然后再利用訓(xùn)練樣本集確定該分類器的參數(shù)，以求使所確定的準(zhǔn)則達(dá)到最佳。該分類器的參數(shù)決定后，在使用線性分類器時(shí)，未知樣本的分類由其判別函數(shù)值決定，而每個樣本的判別函數(shù)值是其各分量的線性加權(quán)和再加上一閾值w0。第18頁，共62頁，2023年，2月20日，星期二

在一般情況下，總可以找到某個最好的方向，使樣本投影到這個方向的直線上是最容易分得開的。如何找到最好的直線方向，如何實(shí)現(xiàn)向最好方向投影的變換，是Fisher法要解決的基本問題。這個投影變換就是我們尋求的解向量。

換句話說，F(xiàn)isher準(zhǔn)則的基本原理，就是要找到一個最合適的投影軸，使兩類樣本在該軸上投影的交迭部分最少，從而使分類效果為最佳。第19頁，共62頁，2023年，2月20日，星期二圖3.3第20頁，共62頁，2023年，2月20日，星期二從d維空間到一維空間的方法設(shè)有d維樣本，其中個屬于類的樣本集X1，個屬于類的樣本集X2，若對的分量做線性組合可得標(biāo)量這樣就得到N個一維樣本組成的集合，并可分為兩個子集。因此，前述尋找最好投影方向的問題，在數(shù)學(xué)上就是尋找最好的變換向量的問題。第21頁，共62頁，2023年，2月20日，星期二

在圖3.3中，分析w1方向之所以比w2方向優(yōu)越，可以歸納出這樣一個準(zhǔn)則，即向量W的方向選擇應(yīng)能使兩類樣本投影的均值之差盡可能大些，而使類內(nèi)樣本的離散程度盡可能小。這就是Fisher準(zhǔn)則函數(shù)的基本思路。為了將這個思路變?yōu)榭捎?jì)算的函數(shù)值，我們先對一些基本參量下定義。

第22頁，共62頁，2023年，2月20日，星期二基本參量在d維X空間

(1)各類樣本均值向量(2)樣本類內(nèi)離散度矩陣和總類內(nèi)離散度矩陣第23頁，共62頁，2023年，2月20日，星期二

(3)樣本類間離散度矩陣其中是對稱半正定矩陣，而且當(dāng)N>d時(shí)通常是非奇異的。2.在一維Y空間(1)各類樣本均值第24頁，共62頁，2023年，2月20日，星期二(2)樣本類內(nèi)離散度和總類內(nèi)離散度第25頁，共62頁，2023年，2月20日，星期二定義準(zhǔn)則函數(shù)

顯然，我們希望在映射之后，兩類的平均值之間的距離越大越好，而各類的樣本類內(nèi)離散度越小越好。因此，定義Fisher準(zhǔn)則函數(shù)

第26頁，共62頁，2023年，2月20日，星期二第27頁，共62頁，2023年，2月20日，星期二——廣義Rayleigh商第28頁，共62頁，2023年，2月20日，星期二下面求使取極大值時(shí)的令分母等于非零常數(shù)，也就是：定義lagrange函數(shù)：

對w求偏導(dǎo)數(shù)：

令偏倒數(shù)為零，得第29頁，共62頁，2023年，2月20日，星期二因?yàn)榉瞧娈?，可得式中從而可得忽略比例因?3-32)第30頁，共62頁，2023年，2月20日，星期二

向量就是使Fisher準(zhǔn)則函數(shù)達(dá)極大值的解，也就是按Fisher準(zhǔn)則將d維X空間投影到一維Y空間的最佳投影方向。

由(3-32)表示的最佳投影方向是容易理解的，因?yàn)槠渲幸豁?xiàng)(m1-m2)是一向量，顯然從兩類均值在變換后距離最遠(yuǎn)這一點(diǎn)看，對與(m1-m2)平行的向量投影可使兩均值點(diǎn)的距離最遠(yuǎn)。但是如從使類間分得較開，同時(shí)又使類內(nèi)密集程度較高這樣一個綜合指標(biāo)來看，則需根據(jù)兩類樣本的分布離散程度對投影方向作相應(yīng)的調(diào)整，這就體現(xiàn)在對(m1-m2)

向量按

作一線性變換，從而使Fisher準(zhǔn)則函數(shù)達(dá)到極值點(diǎn)。第31頁，共62頁，2023年，2月20日，星期二3.Fisher算法步驟由Fisher線性判別式求解向量的步驟：①把來自兩類的訓(xùn)練樣本集X分成和兩個子集和。②由，計(jì)算。③由計(jì)算各類的類內(nèi)離散度矩陣。④計(jì)算類內(nèi)總離散度矩陣。第32頁，共62頁，2023年，2月20日，星期二⑤計(jì)算的逆矩陣。⑥由求解。第33頁，共62頁，2023年，2月20日，星期二分類問題：

只要確定一個閥值，將投影點(diǎn)與相比較，便可做出決策。一維分類問題的基本原則：

(1)當(dāng)維數(shù)d和樣本數(shù)N都比較大時(shí)，可采用貝葉斯決策規(guī)則，從而獲得一種在一維空間的“最優(yōu)”分類器。

(2)上述條件不滿足，可利用先驗(yàn)知識選定分界閥值點(diǎn)，如選擇第34頁，共62頁，2023年，2月20日，星期二

對于任意給定的未知樣本x,只要計(jì)算它的投影點(diǎn)y，再根據(jù)決策規(guī)則就可以判斷x屬于什么類別。第35頁，共62頁，2023年，2月20日，星期二作業(yè)：一、設(shè)五維空間的線性方程為：

55X1＋68X2＋32X3＋16X4＋26X5+10=0試求出其權(quán)向量與樣本向量點(diǎn)積的表達(dá)式WTX+w0=0中的W、X以及增廣權(quán)向量與增廣樣本向量形式aTY中的a和Y。同時(shí)求出該五維空間超平面到坐標(biāo)原點(diǎn)的法向距離。二、設(shè)兩類樣本的類內(nèi)離散矩陣分別為：m1=(2,0)T,m2=(2,2)T,試用fisher準(zhǔn)則求其決策面方程。第36頁，共62頁，2023年，2月20日，星期二3.3感知準(zhǔn)則函數(shù)1、線性可分性如果存在一個權(quán)向量a，使得對于任何y∈w1，都有aTy>0，而對于任何y∈w2，都有aTy<0，則稱這組樣本集是線性可分的；反過來，如果樣本集是線性可分的，則必然存在一個權(quán)向量a，能將每個樣本正確的分類。第37頁，共62頁，2023年，2月20日，星期二2、樣本的規(guī)范化感知準(zhǔn)則函數(shù)使用增廣樣本向量與增廣權(quán)向量，即用(3-11)中的d+1維向量y表示樣本的齊次化增廣向量，用判別函數(shù)中的權(quán)向量W與閾值權(quán)組合成增廣權(quán)向量a。而判別函數(shù)則表示成(3-12)，即

在兩類別情況下，判別準(zhǔn)則是：

第38頁，共62頁，2023年，2月20日，星期二為了計(jì)算方便起見，我們可將第二類樣本都取其反向向量，即令

那么，對于能將所有樣本正確分類的決策面來說，應(yīng)有

上述過程稱為樣本的規(guī)范化，叫做規(guī)范化增廣樣本向量第39頁，共62頁，2023年，2月20日，星期二

權(quán)向量a可理解為權(quán)空間中的一點(diǎn)，每個樣本yn對a的位置都起限制，即要求aTyn>0。方程aTyn＝0確定了一個經(jīng)過權(quán)空間原點(diǎn)的超平面，解向量必存在于超平面的正側(cè)；N個樣本將產(chǎn)生N個超平面，所以解向量必存在于N個正半空間的重合區(qū)，該重合區(qū)中的任意向量都是解向量a。第40頁，共62頁，2023年，2月20日，星期二討論完了問題的提法后，下一步要解決如何找到這樣一個合適的a。感知準(zhǔn)則函數(shù)方法的思路是：先隨意找一個初始向量a，寫作a(0)，然后用訓(xùn)練樣本集中的每個樣本來計(jì)算。一旦發(fā)現(xiàn)有的Y‘使aTY’<0，則說明當(dāng)前的廣義權(quán)向量a不適合還需要進(jìn)一步修正。修正的原理也很簡單，設(shè)當(dāng)前經(jīng)k次疊代修正的廣義權(quán)向量為a(k)，若有發(fā)現(xiàn)一個Y'出現(xiàn)aTY'<0，則只要a(k+1)=a(k)+pkY',

pk(步長系數(shù))為正，則必有a(k+1)TY‘=a(k)TY’+pkY‘TY’>a(k)TY‘，

就有趨勢做到使a(k+1)TY’>0。

當(dāng)然，修改后的a(k+1)還可以使某些Y‘出現(xiàn)a(k+1)TY’<0的情況，理論證明，只要訓(xùn)練樣本集線性可分，無論a(0)的初值是什么，經(jīng)過有限次疊代，都可得到滿意的a。

第41頁，共62頁，2023年，2月20日，星期二3.4多類問題

以上討論的都是兩類別問題，但是實(shí)際問題中常遇到的是多類別問題。在兩類別問題中使用的線性判別函數(shù)方法可以推廣到多類別問題中，但可有不同做法。一種最簡單作法是將C類別問題化為(C-1)個兩類問題，即將第i類與所有非i類樣本，按兩類問題確定其判別函數(shù)與決策面方程。因此對于C類，則總共有(C-1)個兩類別問題第42頁，共62頁，2023年，2月20日，星期二

這種做法存在兩個問題，一是可能會出現(xiàn)一些不定區(qū)域，如圖中綠色陰影所示，在這些區(qū)域中的樣本無法確定其類別。另一方面用線性判別函數(shù)對i類及所有非i類進(jìn)行劃分并不能保證獲得性能良好的劃分，硬性使用線性分類器可能會產(chǎn)生很不好的效果。第43頁，共62頁，2023年，2月20日，星期二另一種相對麻煩些的做法是將C類中的每兩類別單獨(dú)設(shè)計(jì)其線性判別函數(shù)，因此總共有C(C-1)/2個線性判別函數(shù)。這種方法如圖所示。這種方法由于每個判別函數(shù)針對每兩類別樣本設(shè)計(jì)，預(yù)期可有好效果，但仍有不定區(qū)域，在該區(qū)域內(nèi)樣本類別無法確定。

第44頁，共62頁，2023年，2月20日，星期二因此一個比較合適的作法是將特征空間確實(shí)劃分為C個決策域，共有C個判別函數(shù)

，每個決策域Ri按以下規(guī)則劃分

如果

因此落在Ri區(qū)域內(nèi)的樣本被劃分成ωi類，如果發(fā)生gi(X)＝gj(X)，即處于決策域的邊界上，則作出拒絕決策。這種分類器被稱為線性機(jī)器。線性機(jī)器中決策域的邊界由相鄰決策域的判別函數(shù)共同決定，此時(shí)應(yīng)有

第45頁，共62頁，2023年，2月20日，星期二第46頁，共62頁，2023年，2月20日，星期二3.3非線性判別函數(shù)

對實(shí)際的模式識別問題來說，各類在特征空間中的分布往往比較復(fù)雜，因此無法用線性分類函數(shù)得到好的效果。這就必須使用非線性的分類方法。在對待非線性判別分類問題，，提到的三種不同的方法。傳統(tǒng)的模式識別技術(shù)，側(cè)重于使用分段線性判別函數(shù)，因此基本上是沿用了線性判別函數(shù)的方法。錯誤修正法是對感知準(zhǔn)則函數(shù)的擴(kuò)展，但人工神經(jīng)元網(wǎng)絡(luò)如多層感知器等網(wǎng)絡(luò)能夠使用非常復(fù)雜的非線性分類，以及非線性函數(shù)擬和，非線性映射等，這將在人工神經(jīng)元網(wǎng)絡(luò)這一章討論。支持向量機(jī)則提出了一種基于特征映射的方法，也就是使用某種映射，使本來在原特征空間必須使用非線性分類技術(shù)才能解決的問題,映射到一個新的空間以后,使線性分類技術(shù)能繼續(xù)使用

第47頁，共62頁，2023年，2月20日，星期二3.3.1

非線性判別函數(shù)與分段線性判別函數(shù)

1第48頁，共62頁，2023年，2月20日，星期二

由于樣本在特征空間分布的復(fù)雜性，許多情況下采用線性判別函數(shù)不能取得滿意的分類效果。例如對上圖所示兩類物體在二維特征空間的分布，采用線性判別函數(shù)就無法取得滿意的分類效果。在這種情況下，可以采用分段線性判別或二次函數(shù)判別等方法，效果就會好得多。與一般超曲面相比，分段線性判別函數(shù)是最為簡單的形式，是非線性判別函數(shù)情況下最為常用的形式。除此之外二次判別函數(shù)是除線性及分段線性外最簡單的形式。以下只討論有關(guān)分段線性判別函數(shù)設(shè)計(jì)中的一些基本問題。第49頁，共62頁，2023年，2月20日，星期二與線性判別函數(shù)相比，分段線性判別函數(shù)設(shè)計(jì)中首先要解決的問題是分段線性判別函數(shù)的分段段數(shù)問題，顯然這是一個與樣本集分布有關(guān)的問題。分段段數(shù)過少，其分類效果必然要差；但段數(shù)又要盡可能少，以免分類判別函數(shù)過于復(fù)雜，增加分類決策的計(jì)算量。在有些實(shí)際的分類問題中，同一類樣本可以用若干個子類來描述，這些子類的數(shù)目就可作為確定分段段數(shù)的依據(jù)。但多數(shù)情況下樣本分布及合適子類劃分并不知道，則往往需要采用一種聚類的方法(在以后討論),設(shè)法將樣本劃分成相對密集的子類，然后用各種方法設(shè)計(jì)各段判別函數(shù)。由于在后面章節(jié)要討論聚類問題，這一章主要討論在樣本分布及子類劃分大體已定的情況下，設(shè)計(jì)分段線性判別函數(shù)的問題，著重討論幾種典型的設(shè)計(jì)原理。第50頁，共62頁，2023年，2月20日，星期二則分段線性判別函數(shù)的一般形式可定義為：

若把每一類分為若干個子類，即令其中

表示第i類第l段線性判別函數(shù)，li為i類所具有的判別函數(shù)個數(shù)，

與

分別是第l段的權(quán)向量與閾值權(quán)。相應(yīng)的判別規(guī)則是：

第51頁，共62頁，2023年，2月20日，星期二

至于分類的決策面方程取決于相鄰的決策域，如第i類的第n個子類與第j類的第m個子類相鄰，則由它們共同決定的決策面方程為：

結(jié)論：當(dāng)每一類的樣本數(shù)據(jù)在特征空間中的分布呈復(fù)雜修正時(shí)，使用線性判別函數(shù)就會產(chǎn)生很差的效果，如果能將它們分割成子集，而每個子集在空間聚集成團(tuán)，那么子集與子集的線性劃分就可以取得比較好的效果。因此分段線性判別的主要問題是如何對數(shù)據(jù)劃分成子集的問題，或者說如何利用樣本集確定子類數(shù)目以及如何求解各子類的權(quán)向量和閾值權(quán)。第52頁，共62頁，2023年，2月20日，星期二3.3.2基于距離的分段線性判別函數(shù)在正態(tài)分布條件下，兩類別問題在各特征統(tǒng)計(jì)獨(dú)立、同方差、且先驗(yàn)概率相等情況下，最小錯誤率決策可按最小距離決策，即：其中

與

為各類的均值。這樣的分類器叫最小距離分類器

第53頁，共62頁，2023年，2月20日，星期二最小距離分類器用多個最小距離分類器組成分段線性分類面。第54頁，共62頁，2023年，2月20日，星期二

盡管這是在一種很特殊的情況下得到的，但是按距離分類的原理是可以推廣的，即把各類別樣本特征向量的均值作為各類的代表點(diǎn)，而樣本的類別按它到各類別代表點(diǎn)的最小距離劃分。在這種判別函數(shù)中，決策面是兩類別均值連線的垂直平分面。對于上圖所示情況，若企圖再用每類一個均值代表點(diǎn)產(chǎn)生最小距離分類器，就會產(chǎn)生很明顯的錯誤率。在這種情況下，可以將各類別劃分成相對密集的子類，每個子類以它們的均值作為代表點(diǎn)，然后按最小距離分類，把未知樣本x歸到離它最近的代表點(diǎn)所屬的類，則可以有比較滿意的效果。

第55頁，共62頁，2023年，2月20日，星期二例：未知x,如圖：先與ω1類各子類的均值比較，即，找一個最近的與ω2各子類均值比較取最近的因g2(x)<g1(x)，所以x∈ω2類。第56頁，共62頁，2023年，2月20日，星期二

歸納起來，分