模式識(shí)別課件(總順序No6)(第三章NO1)(張鳳)(071030)(線性判別函數(shù))

第三章線性判別函數(shù)3.1引言(1)問題：第二章所述的分類器設(shè)計(jì)方法是在已知類條件概率密度p(X|Wi)和先驗(yàn)概率p(Wi)，再利用Bayes公式將其轉(zhuǎn)化成后驗(yàn)概率。然后依據(jù)不同規(guī)則進(jìn)行分類－－相對(duì)最優(yōu)。但實(shí)際中，p(X|Wi)很難確定，而Parzen窗等估計(jì)方法有需大量樣本，且隨著特征空間Ω維數(shù)的增加所需樣本數(shù)急增，導(dǎo)致計(jì)算量增加，存儲(chǔ)量增加。(2)應(yīng)對(duì)與局限性：因此，提出了利用樣本集直接設(shè)計(jì)分類器。這種方法是：若能找到一個(gè)分離函數(shù)，特別若是不依賴于條件分布密度的，且呈線性或非線性的分離函數(shù)。它可理解為通過幾何的方法，將Ω分解為對(duì)應(yīng)于不同類別的子空間。這種方法所能處理的只是確定可分(線性/非線性可分)的問題，當(dāng)樣本集聚的空間發(fā)生重疊現(xiàn)象時(shí)，尋找分離函數(shù)的迭代過程將加長(zhǎng)，甚至振蕩。這就是這種方法的局限性。另外，相對(duì)Bayes方法該方法得到的是“次優(yōu)解”。(3)這種方法的基本思想是：

如果根據(jù)以往大量的觀察：

①知道模式類別的分布；②能找出d維空間(Ω)中模式類之間的分界。

這就能解決模式的分類問題。這實(shí)際上是運(yùn)用已知類別的訓(xùn)練樣本進(jìn)行學(xué)習(xí)的過程。通過學(xué)習(xí)產(chǎn)生若干個(gè)代數(shù)界面g(X)=0，這個(gè)表示界面的函數(shù)g(X)稱為判別函數(shù)。(4)這種方法的處理思路是：分類特征空間的分劃

尋求子區(qū)域的界面判別函數(shù)g(X)

判別函數(shù)g(X)的結(jié)構(gòu)與參數(shù)的確定待識(shí)別樣本特征向量帶入判別函數(shù)后取值與歸類。

注意：這種方法要求以后的待分類樣本/模式基本上不超過學(xué)習(xí)樣本的分布范圍，也就是說利用這些已知樣本得出的分類邊界是無誤差的。為了找出這些模式類之間的分界面，可以利用判別函數(shù)來進(jìn)行。(5)處理方法是：先給定(某個(gè))判別函數(shù)類g(X)=0，再利用樣本集確定出g(X)中的未知參數(shù)，然后對(duì)于樣本根據(jù)其特征值帶入g(X)后的取值正負(fù)而確定樣本的類別(即其所屬的子區(qū)域)。即：g(X)=W1X1+W2X2+W3=0

若g(X)<0,則XW2

若g(X)>0,則XW1 x1一線性判別函數(shù)對(duì)于d維特征空間中的不同模式類別分別給出一個(gè)由d個(gè)特征組成的單值函數(shù)，這稱為判別函數(shù)。其一般表達(dá)式為：g(X)=WTX+W0其中：X是d維特征向量(亦稱樣本向量)。

X=[x1,…,xd]TW稱權(quán)向量。W=[w1,…,wd]TW0是個(gè)常數(shù)，稱為閥值權(quán)。說明：⑴使用g(X)來進(jìn)行模式分類，依賴于兩個(gè)因素。

①g(X)的形狀(即幾何性質(zhì))。它可是線性的或非線性的函數(shù)。在g(X)是線性判別函數(shù)下，它是所有模式特性的線性組合。

g(X)=w1x1+…+wdxd

+w0

式中，每個(gè)特征對(duì)于判別函數(shù)g(X)作出不同的貢獻(xiàn)，貢獻(xiàn)的大小就是它的權(quán)wi(i=1,…,d)。

②g(X)的參數(shù)：只要被研究的模式是可分的，就可確定g(X)的參數(shù)。(2)使用g(X)進(jìn)行模式分類的方法。首先利用樣本去計(jì)算各wi和w0(i=1,…,d)，再將未知(待識(shí)別)樣本X歸到具有最大判別函數(shù)值的類別中去。(3)對(duì)于C類模式問題，(一般)需要定義C個(gè)判別函數(shù)。

gi(X)(i=1,…,c)

它們分別對(duì)應(yīng)于C個(gè)模式類w1,…,wc。(4)g(X)的基本性質(zhì)：設(shè)一個(gè)模式X屬于第i類，則有：

gi(X)>gj(X)

(i,j=1,…,c,i≠j)

而如果此模式在第i類和第j類的分界面上，則有：

gi(X)=gj(X)

例如：對(duì)于兩類問題的線性判別函數(shù)及其分類問題。

⑴決策規(guī)則問題：在只有兩類模式的情況下，可得到兩個(gè)線性判別函數(shù)，即

g1(X)=w1Tx+w10 g2(X)=w2Tx+w20

①如果X屬于W1類，則根據(jù)上述性質(zhì)，有：

g1(X)>g2(X)或g1(X)-g2(X)>0；

反之，即如果X屬于W2類，則上式小于0。

②

如果令g(X)=g1(X)-g2(X)，則得兩類模式的線性分類器的決策規(guī)則為：如果g(X)>0,則決策X∈W1，即將X歸到W1類。

如果g(X)<0,則決策X∈W2，即將X歸到W2類。

如果g(X)=0,則決策是任意的，即將X歸到W1或W2類。

其中：g(X)=0是決策面方程。

它是兩類模式的分界面(即分割W1類和W2類)。對(duì)于二維空間，它是一條直線(線性下)；對(duì)于三維空間，它是一個(gè)平面；而對(duì)于高維空間，則是一個(gè)超平面。⑵決策域問題設(shè)X1和X2都在決策面H上，則有：

WTX1+W0=WTX2+W0

即WT(X1-X2)=0

由于向量X1和X2是決策面（即超平面）H上的任意兩點(diǎn)，所以(X1-X2)是H上的任意向量。上式說明，權(quán)向量W和H上的任一向量正交。故W的方向就是H的法線方向(即法向量)。在兩類下，H把特征空間分成兩個(gè)半空間，即對(duì)W1類的決策域R1和對(duì)W2

類的決策域R2。由于當(dāng)向量（即模式）X在R1中時(shí)，g(X)>0,所以H的法向量的方向是指向R1的。常稱R1位于決策面H的正側(cè)／面；反之，稱R2位于決策面H的負(fù)／反側(cè)。(3)幾何解釋：H是決策面，其方程為g(X)=0。W是權(quán)向量，其是H的法線方向。X是待識(shí)別的模式的特征向量(圖中X落入R1區(qū)域中，即被分到W1類中去)。對(duì)待識(shí)模式X，若將X帶入判別函數(shù)，則判別函數(shù)值g(X)是特征空間中一/某點(diǎn)X到超平面H的距離的度量。圖中W0,g(X)

均為代數(shù)量，用于求距離,與方向無關(guān)。向量X可以表示為：式中：XpX向量是超平面H的法線方向。向量Xp是X在H上的投影向量。由于Xp是H上的一點(diǎn)，所以是W(權(quán)向量)方向上的單位向量，而

r是X到H的垂直距離。r是待求的距離，且r是一個(gè)代數(shù)量，r的正負(fù)反應(yīng)了X位于H的正負(fù)側(cè)（即當(dāng)X在H的正側(cè)時(shí)，r為正；反之，r為負(fù)）。據(jù)上式可得：或?qū)懗蔀槿绻鹓(X)>0

，則X在H的正側(cè)；如果g(X)<0

，則X在H的負(fù)側(cè)。若X為原點(diǎn)，有：則從原點(diǎn)到超平面H的距離r0為：如果W0>0，則原點(diǎn)在H的正側(cè)；反之，原點(diǎn)在H的負(fù)側(cè)；如果W0=0，則g(X)=WTX(齊次形式)說明H過原點(diǎn)。總之，線性判別函數(shù)進(jìn)行(兩類)模式分類時(shí)：用超平面H將特征空間分割成兩個(gè)區(qū)域；

H的方向由權(quán)向量W確定，H的位置由閥值權(quán)W0確定。

g(X)值正比于X點(diǎn)到H的(代數(shù))距離（有正負(fù)）。當(dāng)X在H正側(cè)時(shí)，g(X)>0；在負(fù)側(cè)時(shí),g(X)<0。二廣義線性判別函數(shù)對(duì)圖所示的一維特征空間的兩類問題。

若希望的劃分是：若X<b或X>a，則X∈W1類；若b<X<a，則X∈W2類。則無法用線性判別函數(shù)法解決（實(shí)際上，對(duì)于非凸決策區(qū)域和多連通區(qū)域的劃分問題，線性判別函數(shù)法都無能為力）。對(duì)上述問題可建立一個(gè)二次判別函數(shù)

g(X)=(X-a)(X-b)對(duì)應(yīng)的決策規(guī)則就是：如果g(X)>0，則決策X∈W1；如果g(X)<0，則決策X∈W2。二次判別函數(shù)的一般形式可寫為：

如果適當(dāng)選擇X→Y的映射，則可將X的二次判別函數(shù)轉(zhuǎn)化為Y的線性函數(shù)。式中：

g(X)=稱為廣義線性判別函數(shù)，稱為廣義權(quán)向量。這樣變換后，就化為廣義線性判別函數(shù)來處理，只不過不是X的線性函數(shù)，而是Y的線性函數(shù)；且g(X)=的超平面(即=0)在Y空間是通過原點(diǎn)的。注意：經(jīng)此變換后,維數(shù)會(huì)大大增加,從而陷入“維數(shù)災(zāi)難”。對(duì)前所述的線性判別函數(shù)式中：

則稱為線性判別函數(shù)的齊次簡(jiǎn)化；并稱為增廣樣本向量；

稱為增廣權(quán)向量(也稱廣義權(quán)向量)。它們均是d+1維向量。Y與X相比，雖然增加了一維，但保持樣本間的歐氏距離不變(只是相當(dāng)于坐標(biāo)系移動(dòng))。三設(shè)計(jì)線性分類器的主要步驟⑴要有一組具有類別標(biāo)志的樣本集；⑵據(jù)實(shí)際情況確定一個(gè)準(zhǔn)則函數(shù)J，它需滿足： ①J是樣本集和W，w0或a的函數(shù)。 ②J的值能反映分類器的性能，其極值解對(duì)應(yīng)于“最佳”決策。⑶用最優(yōu)化技術(shù)求出J的極值解W*，w0*和a*。

從而得到線性判別函數(shù)：

g(x)=W*TX+w0*或g(X)=a*TY3.2Fisher線性判別一引言

線性判別函數(shù)易于分析，但是存在維數(shù)問題，即在低維或解析上行的通情況下適用，而對(duì)于高維卻很難實(shí)現(xiàn)。所以降低維數(shù)是關(guān)鍵?，F(xiàn)考慮將d維空間的樣本投影到一條直線上，形成一維空間，即把維數(shù)壓縮到一維。

關(guān)鍵：尋找滿足上述目標(biāo)的投影軸的方向和在一維空間中確定判別函數(shù)規(guī)則的問題——這就是Fisher所要解決的問題。

二Fisher法的基本思想和基本方法⒈Fisher方法的基本思想

把d維空間的所有模式投影到一條過原點(diǎn)的直線上，就能把維數(shù)壓縮到1。這就是說，要求一個(gè)投影向量W，使各樣本投影后同類模式相距較近，同類模式密集；不同類模式相距較遠(yuǎn)，即類心相距較遠(yuǎn)。這就是相當(dāng)于找到某個(gè)方向，使在這個(gè)方向的直線上，樣本的投影能分開得最好。⒉Fisher的基本方法

指從d維空間到一維空間的一般變換方法。設(shè)有一集合?包含N個(gè)d維樣本X1,…,XN，其中N1個(gè)屬于W1類的樣本,記為子集?1，N2(=N-N1)個(gè)屬于W2類的樣本,記為?2。目的是找到一條直線，使得樣本在此直線上的投影最有利于分類。設(shè)W為此直線正方向的單位向量。即‖W‖=1。

(實(shí)際上W的絕對(duì)值大小在此是無關(guān)緊要的，而重要的是確定W的方向。W的方向不同，將使樣本投影后的可分離程度不同，從而影響識(shí)別效果.)若設(shè)由X1和X2對(duì)直線的投影相應(yīng)地得到集合Y1和Y2。則每個(gè)yj∈Yi就是xj∈Xi(j=1,…,N;i=1,2)在單位向量W上的投影。即yj

=WTxj(j=1,…,N)注意：yj代表一維樣本（即yj為標(biāo)量）。說明：對(duì)xj的分量作線性組合后，共得到N個(gè)一維樣本yj組成的集合Y，它們歸屬于兩個(gè)子集Y1和Y2中。這從幾何上講，每個(gè)yj就是相對(duì)應(yīng)的Xj到方向?yàn)閃的直線上的投影。這樣上式可寫成：Y=WTX

式中：Y=[y1,…,yN]T；

WT

=[w1,…,wd]并且‖w‖=1；

X

=[xj1,…,yjd]T(j=1,…,N)為了找到最有利于分類的方向W，需建立一個(gè)準(zhǔn)則函數(shù)，它能反映不同類別模式在此直線上投影分離程度的好壞。三Fisher準(zhǔn)則函數(shù)所涉及的基本參量⒈在d維x空間⑴各類樣本均值向量mi

：

(i=1,2)

注意：Ni為標(biāo)量(個(gè)數(shù))，x為向量，所以mi為向量。⑵樣本類類內(nèi)離散度矩陣Si和總類類內(nèi)離散度矩陣Sw

(1=1,2)

Sw

=S1+

S2說明：Si表示類中各點(diǎn)到類的中心點(diǎn)距離之和(的平方)。其中Sw是對(duì)稱半正定矩陣，且當(dāng)N>d時(shí)，通常是非奇異的。⑶樣本類類間離散度矩陣Sb

Sb=(m1-m2)(m1-m2)T

說明：Sb也是對(duì)稱半正定矩陣，在兩類條件下，它的秩最大等于1，且(Sb)d*d

。⒉在一維Y空間 即作變換后，使d維向量x在以向量W為方向的軸上進(jìn)行投影

Y=WTX

變換后在一維Y空間中。⑴各類樣本均值

(i=1,2)說明：①因?yàn)閥是標(biāo)量，所以也是標(biāo)量。mi是第i類d維樣本的均值，而這些樣本在直線W上的投影的均值就是，再根據(jù)Y=WTX

③

為了使類別分離地好，應(yīng)使各類樣本投影均值彼此間相距盡可能大，而投影均值間的距離就是：因?yàn)閙1和m2對(duì)于給定的兩類樣本集是不變的。所以改變W的方向，就可改變投影均值間的距離。⑵樣本類類內(nèi)離散度和總類類內(nèi)離散度

說明：①因?yàn)閥,均為標(biāo)量，所以和也為標(biāo)量。②為了使類別分離得好，還應(yīng)使同類樣本的投影比較密集，這由來度量；而表示整個(gè)樣本集合中各類樣本投影的密集程度。③為了得到更好的分類結(jié)果，應(yīng)選擇直線W使得盡可能小。⑶樣本類類間離散度說明：因?yàn)闉闃?biāo)量，所以也為標(biāo)量。四Fisher線性判別

構(gòu)造Fisher判別函數(shù)（y為一維，X為d維）

(注意：“判別函數(shù)”指的是任一X的函數(shù))

希望投影后，在一維Y空間里，各類樣本盡可能分得開些，即希望類間離散度越大越好；而希望各類樣本內(nèi)部盡量密集，即希望類內(nèi)離散度越小越好。據(jù)此定義Fisher準(zhǔn)則函數(shù)

式中JF(w)為標(biāo)量(因?yàn)?,均是標(biāo)量)

現(xiàn)在的問題就是選擇合適的W(方向)使盡可能的達(dá)到極大。將變成W的顯函數(shù)，即將，，的式子代入式得:

這是廣義Rayleigh商/比，其