模式識(shí)別課件第五章非線性判別第一頁(yè)，共三十二頁(yè)，編輯于2023年，星期六第二頁(yè)，共三十二頁(yè)，編輯于2023年，星期六一、基于與類心距離的分段線性判別函數(shù)根據(jù)前述可知。當(dāng)類條件概率密度函數(shù)為正態(tài)分布，各特征統(tǒng)計(jì)獨(dú)立且方差相同時(shí)，Bayes決策規(guī)則具體為一個(gè)線性距離判別函數(shù)，特別是當(dāng)時(shí)，決策規(guī)則為：注：X到μ1的距離小于(或大于)X到μ2的距離時(shí),μ為隨機(jī)變量X的數(shù)學(xué)期望第三頁(yè)，共三十二頁(yè)，編輯于2023年，星期六決策面是兩類期望（“中心點(diǎn)”）連線的垂直平分面。見(jiàn)圖5.2，稱最小距離分類器。將均值（“重心”或“中心點(diǎn)”）作為各類的代表點(diǎn)，用距離作為判別函數(shù)進(jìn)行分類。第四頁(yè)，共三十二頁(yè)，編輯于2023年，星期六但是在一些情況下，當(dāng)類域是非單連通的或者一個(gè)類域有若干個(gè)模式相對(duì)密集的區(qū)域。此時(shí)，若仍用每一類只取一個(gè)點(diǎn)代表就不恰當(dāng)了(因?yàn)檫@時(shí)若應(yīng)用簡(jiǎn)單線性判別函數(shù)分類，則結(jié)果將會(huì)有很多錯(cuò)分。)，而應(yīng)用那些樣本較密集的子區(qū)的中心“聯(lián)合”代表該類。例如：圖5.3，兩類分布，類都是多峰分布。方法1：若把類的均值m1和m2作為代表類，得到分界面Ⅰ，則錯(cuò)分率較高。方法2：如果每類取多個(gè)代表點(diǎn)，如類取兩個(gè)代表點(diǎn)，m11，m12；類取三個(gè)代表點(diǎn)，m21，m22，m23。則得到分段線性分界面Ⅱ(其中每一段都是最小距離分類器)。第五頁(yè)，共三十二頁(yè)，編輯于2023年，星期六總之：如果對(duì)于類取li個(gè)代表點(diǎn)。也就是說(shuō)，把屬于類的樣本區(qū)域Ri分為li個(gè)子區(qū)域，即其中Ril表示第i類的第l個(gè)子區(qū)域，用mil表示該子區(qū)域中樣本的均值向量，且以此作為該子區(qū)域的代表點(diǎn)。則可定義如下判別函數(shù)：若有則將X歸到類。－－－－分段線形距離分類器第六頁(yè)，共三十二頁(yè)，編輯于2023年，星期六二、分段線性判別函數(shù)1引言：前述的以每類（或分為若干子區(qū)域）的均值向量作為代表點(diǎn)以設(shè)計(jì)最小距離分類器，在一些情況下不適用。例如。圖5.4。各類樣本服從正態(tài)但非等協(xié)差分布，其概率密度面為超橢球面，以Bayes決策規(guī)則對(duì)樣本Ｘ進(jìn)行分類時(shí)，應(yīng)為類，但若以μi作為代表點(diǎn)，并按μi的歐式距離進(jìn)行分類，則類。

第七頁(yè)，共三十二頁(yè)，編輯于2023年，星期六2將每一類分為若干個(gè)子類，即令然后，對(duì)每一個(gè)子類定義一個(gè)線性判別函數(shù)，式中分別稱為對(duì)子類的權(quán)向量和閾值權(quán)。如果定義類的線性判別函數(shù)為：則對(duì)于c類問(wèn)題，可以定義c個(gè)判別函數(shù)gi(Ｘ)(i=1,….,c)，并得到?jīng)Q策規(guī)則，即：

第八頁(yè)，共三十二頁(yè)，編輯于2023年，星期六說(shuō)明：①

先找到具有最大判別函數(shù)值的子類（設(shè)為gin(Ｘ)），則把樣本Ｘ歸到子類所屬的類，即類。②這樣得到的決策面也是分段線性的，其決策面方程是由各子類的判別函數(shù)確定的。③如果第i類的第n個(gè)子類和第m個(gè)子類相鄰，則該段決策面方程是：

第九頁(yè)，共三十二頁(yè)，編輯于2023年，星期六三、分段線性分類器設(shè)計(jì)的一般考慮

1利用多類線性判別函數(shù)算法設(shè)計(jì)分段線性分類器在已知樣本的子類劃分情況下，則可把子類看作獨(dú)立的類，然后利用不同方法/算法把各個(gè)子類分開。2已知子類數(shù)目時(shí)的分段線性判別函數(shù)在已知子類數(shù)目，而不知子類劃分情況下，有一種稱為錯(cuò)誤修正算法來(lái)設(shè)計(jì)分段線性分類器，其步驟如下：第十頁(yè)，共三十二頁(yè)，編輯于2023年，星期六

Step1：任意給定各子類的初始權(quán)向量。設(shè)類中有l(wèi)i個(gè)子類，則任意給定Step2：利用訓(xùn)練樣本集進(jìn)行迭代，并按下列規(guī)則修改權(quán)向量。若在第k次迭代時(shí)，類中的樣本Ｙj與類的某個(gè)權(quán)向量的內(nèi)積值為最大。即而且滿足：，其中i=1,2,…,c；i≠j；l=1,2,…,li。第十一頁(yè)，共三十二頁(yè)，編輯于2023年，星期六

則說(shuō)明權(quán)向量組

不影響Ｙi正確分類，則各權(quán)向量保持不變。但如果存在某個(gè)或幾個(gè)子類不滿足上述條件，即存在，使得：則說(shuō)明Ｙj被錯(cuò)誤分類，這時(shí)需要對(duì)權(quán)向量進(jìn)行修正。設(shè)

則修正算法為：

Step3：重復(fù)第二步，直到算法收斂，或達(dá)到規(guī)定的時(shí)限，或達(dá)到規(guī)定的迭代次數(shù)為止。

第十二頁(yè)，共三十二頁(yè)，編輯于2023年，星期六

3未知子類數(shù)目時(shí)的分段線性判別函數(shù)方法很多，以樹狀分段線性分離器為例。見(jiàn)圖5.5（兩類）先用兩類線性判別函數(shù)算法找一個(gè)權(quán)向量a1，其所對(duì)應(yīng)的超平面H1將整個(gè)樣本集分成兩部分（即樣本子集）。因?yàn)槊恳徊糠秩院瑑深悩颖?，所以接著找出第二、三、四個(gè)權(quán)向量a2、a3、a4，對(duì)應(yīng)的超平面H2、H3、H4分別把相應(yīng)的樣本子集分成兩部分。這時(shí)把兩類樣本完全分開。這樣得到的分類器顯然是分段線性的，其決策面如圖5.5所示。第十三頁(yè)，共三十二頁(yè)，編輯于2023年，星期六第十四頁(yè)，共三十二頁(yè)，編輯于2023年，星期六這種情況下的識(shí)別過(guò)程是一個(gè)樹狀結(jié)構(gòu)。見(jiàn)圖5.6。圖中用虛線顯示了對(duì)未知樣本Ｙ的決策過(guò)程，經(jīng)過(guò)3步，判得

說(shuō)明：

①此方法對(duì)初始權(quán)向量的選擇很敏感，其結(jié)果隨初始權(quán)向量的不同而大不相同。②在每個(gè)節(jié)點(diǎn)上所用的尋找權(quán)向量ai的方法不同，結(jié)果也將各異。第十五頁(yè)，共三十二頁(yè)，編輯于2023年，星期六圖5.6與圖5.5對(duì)應(yīng)的樹狀決策過(guò)程第十六頁(yè)，共三十二頁(yè)，編輯于2023年，星期六5.2用凹函數(shù)的并表示分段線性判別函數(shù)

一、分段線性判別函數(shù)的表示1.凹函數(shù)的定義

⑴設(shè)Li是線性函數(shù)（i=1，2，….，r），則分段線性函數(shù)可定義如下：

①

L1,L2,.......,Lr都是分段線性函數(shù)。②和也是分段線性函數(shù)，式中表示取??；表示取大。

③分段線性函數(shù)只有上述①和②形式。第十七頁(yè)，共三十二頁(yè)，編輯于2023年，星期六(2)

分段線性函數(shù)的一般表達(dá)式析取范式合取范式對(duì)于析取范式P中的每個(gè)稱為一個(gè)凹函數(shù)。所以P是q個(gè)凹函數(shù)的并，即在q個(gè)凹函數(shù)中求最大的凹函數(shù)（因?yàn)槭乔笞畲螅?/p>

第十八頁(yè)，共三十二頁(yè)，編輯于2023年，星期六2.使用凹函數(shù)的并完成分類

對(duì)于多峰分布的兩類問(wèn)題，設(shè)P中的每個(gè)凹函數(shù)（粗略的）確定了某個(gè)類的一個(gè)峰。若此類呈現(xiàn)q個(gè)峰的分布，則P由q個(gè)凹函數(shù)Pi的并構(gòu)成，記為:

而每個(gè)凹函數(shù)Pi又是由mi個(gè)線性判別函數(shù)Lij的交構(gòu)成。即再設(shè)對(duì)于每個(gè)都設(shè)計(jì)成使則r個(gè)權(quán)向量a1,…,ar就能對(duì)樣本集正確分類，第十九頁(yè)，共三十二頁(yè)，編輯于2023年，星期六決策(判別)規(guī)則為：說(shuō)明：分段線性判別函數(shù)P是樣本集?和權(quán)向量的函數(shù)。例如：參照?qǐng)D5.7。兩類問(wèn)題。o表示類，x表示類，對(duì)于

類，有3個(gè)子類（即q=3），對(duì)于每個(gè)子類分別有5、4、4個(gè)分段線性函數(shù)（即m1=5，m2=4，m3=4）。即共有13個(gè)線性判別函數(shù)。則分段線性判別函數(shù)P為：或?qū)懗扇〈笕⌒⌒问健?/p>

第二十頁(yè)，共三十二頁(yè)，編輯于2023年，星期六第二十一頁(yè)，共三十二頁(yè)，編輯于2023年，星期六二、算法描述見(jiàn)書P126第二十二頁(yè)，共三十二頁(yè)，編輯于2023年，星期六5.3用交遇區(qū)的樣本設(shè)計(jì)分段線性分類器一、引言實(shí)際中，有時(shí)類域的形狀比較復(fù)雜，凹凸交替，并且兩類靠的較近，甚至還可能部分重疊。我們將兩類模式十分靠近或重疊混雜的區(qū)域稱為交遇區(qū)，如圖5.10中的a，c交迭區(qū)，b靠近區(qū)。對(duì)此情況不能簡(jiǎn)單的使用全部訓(xùn)練樣本進(jìn)行訓(xùn)練來(lái)產(chǎn)生線性判別函數(shù)，應(yīng)對(duì)那些交遇區(qū)十分“精細(xì)”地對(duì)待，取出交遇區(qū)中的訓(xùn)練樣本，用這些局部訓(xùn)練樣本產(chǎn)生“局部”的線性判別函數(shù)，再由這些線性判別函數(shù)構(gòu)成分段線性判別函數(shù)。第二十三頁(yè)，共三十二頁(yè)，編輯于2023年，星期六第二十四頁(yè)，共三十二頁(yè)，編輯于2023年，星期六這種方法使組成分段線性函數(shù)的線性函數(shù)最少。這種方法涉及以下幾個(gè)基本問(wèn)題：

①找出交遇區(qū) ②由交遇區(qū)中的樣本產(chǎn)生線性判別函數(shù) ③分類決策第二十五頁(yè)，共三十二頁(yè)，編輯于2023年，星期六二、尋找交遇區(qū)和緊互對(duì)原型對(duì)1.何為交遇區(qū)和緊互對(duì)原型對(duì)設(shè)兩類下，有對(duì)應(yīng)的兩個(gè)樣本集?1和?2（即?1對(duì)應(yīng)1類，?2對(duì)應(yīng)2類）。先用聚類分析方法將每類分成若干個(gè)子聚類。每個(gè)子聚類在Ω中占據(jù)一定區(qū)域，稱為“原型區(qū)”；每個(gè)子聚類的“重心”或“類心”，或最靠近類心的一個(gè)樣本稱為該子聚類的“原型”.這時(shí)，每個(gè)子聚類可用它的原型表示，而每一類則可由這類的全部原型來(lái)表示。而交遇區(qū)的表示就是用這些原型來(lái)實(shí)現(xiàn)的。第二十六頁(yè)，共三十二頁(yè)，編輯于2023年，星期六令Vi表示i類的原型集合式中：vij（j=1，…，li）為i類的第j個(gè)原型，li為i類中的原型個(gè)數(shù)。我們用

表示一個(gè)互對(duì)的原型對(duì)。第二十七頁(yè)，共三十二頁(yè)，編輯于2023年，星期六用表示兩個(gè)互對(duì)的原型之間的歐式距離，而當(dāng)且僅當(dāng)

滿足

時(shí)，稱為緊互對(duì)原型對(duì)（必須是不同類的原型）。其意義參見(jiàn)圖5.11

。第二十八頁(yè)，共三十二頁(yè)，編輯于2023年，星期六

2.尋找緊互對(duì)原型對(duì)集合R的算法步驟Step1：對(duì)于每一個(gè)原型，在中找出離它最近的原型v2n（v1m）。記作集合（m=1，2，…，l1）Step2：對(duì)于每一個(gè)原型，在中找出離它最近的原型v1m（v2n）。記作集合：（n=1，2，…，l2）Step3：找出

的交集，即為R，第二十九頁(yè)，共三十二頁(yè)，編輯于2023年，星期六顯然，中的緊互對(duì)原型對(duì)都位于兩類樣本的交遇區(qū)，所以用緊互對(duì)原型對(duì)集合表示交遇區(qū)是可行的。可將緊互對(duì)原型對(duì)的概念擴(kuò)展。對(duì)于一類中的一個(gè)原型用類似的方法可找出另一類原型中的最近的k個(gè)原型，產(chǎn)生的結(jié)果稱為k-緊互對(duì)原型對(duì)集合，記為

。

第三十頁(yè)，共三十二頁(yè)，編輯于2023年，星期六三、用局部訓(xùn)練樣本產(chǎn)生分段線性判別函數(shù)找出k-緊互對(duì)原型對(duì)集合后，則就可據(jù)此確定局部超平面，方法如下：Step1：在k-緊互對(duì)原型對(duì)集合中找出最近的一對(duì)，可選擇連線的垂直平分面作為初始化分界面H1’，H1’的方程為：第三十一頁(yè)，共三十二頁(yè)，編輯于2023年，星期六Step2：以H1’作為初始超平面，找出H1’正確分類的緊互對(duì)原型對(duì)，用這些原型所代表的聚類中的所有樣本作為局部訓(xùn)練樣本集