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

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

第八頁，共三十二頁，編輯于2023年，星期六說明：①

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

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

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

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

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

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

則修正算法為：

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

第十二頁，共三十二頁，編輯于2023年，星期六

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

說明：

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

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

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

①

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

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

分段線性函數(shù)的一般表達式析取范式合取范式對于析取范式P中的每個稱為一個凹函數(shù)。所以P是q個凹函數(shù)的并，即在q個凹函數(shù)中求最大的凹函數(shù)（因為是求最大）

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

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

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

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

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

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

表示一個互對的原型對。第二十七頁，共三十二頁，編輯于2023年，星期六用表示兩個互對的原型之間的歐式距離，而當且僅當

滿足

時，稱為緊互對原型對（必須是不同類的原型）。其意義參見圖5.11

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

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

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

。

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