4非線性判別函數(shù)課件

4.7

非線性判別函數(shù)

前面討論的用線性判別函數(shù)設(shè)計(jì)分類器，在多類情況下可以用樹分類器進(jìn)行多級(jí)分類。若在樹分類器的各節(jié)點(diǎn)上采用線性判別規(guī)則，就構(gòu)成了一個(gè)分段線性分類器。

當(dāng)兩類樣本分布具有多峰性質(zhì)并互相交錯(cuò)時(shí)，簡單的線性判別函數(shù)往往會(huì)帶來較大的分類錯(cuò)誤。采用分段線性分類器，常常能有效地應(yīng)用于這種情況。

4.7.1分段線性判別函數(shù)的基本概念分段線性判別函數(shù)是一種特殊的非線性判別函數(shù)。它確定的決策面是由若干超平面段組成的。由于它的基本組成仍然是超平面，因此，與一般超曲面(例如貝葉斯決策面)相比，仍然是簡單的；又由于它是由多段超平面組成的，所以它能逼近各種形狀的超曲面，具有很強(qiáng)的適應(yīng)能力。

圖4.7.1中分別給出了采用線性判別函數(shù)，分段線性判別函數(shù)和二次判別函數(shù)所得到的分界面。ω1ω1ω2ⅠⅡⅢⅠ：線性判別Ⅱ：分段線性判別Ⅲ：二次判別圖4.7.1μ1μ2x1x2xg(x)=00圖4.7.2這一判別函數(shù)雖然是在十分特殊的條件下推出來的，但它卻給了我們一個(gè)相當(dāng)重要的啟示，這就是可以把均值作為各類的代表點(diǎn)，用距離作為判別函數(shù)進(jìn)行分類。

ω11ω12ω21ω22ω32Ⅰ：線性距離判別m1m2Ⅰ現(xiàn)在考慮圖4.7.3所示的兩類分布情況。ω1類和ω2類都是多峰分布。如果利用上面方法，把各類均值仍作為代表點(diǎn)，設(shè)計(jì)最小距離分類器，則得到分界面Ⅰ。缺點(diǎn)是錯(cuò)誤率較大。Ⅱ：分段線性距離判別圖4.7.3ω11ω12ω21ω22ω32Ⅱ如果每類不是只取一個(gè)代表點(diǎn)，而是取多個(gè)代表點(diǎn)，例如，ω1類取兩個(gè)代表點(diǎn)，ω2類取三個(gè)代表點(diǎn)，仍利用上面定義的距離判別函數(shù)，它是由多段超平面組成的，其中每一段都是最小距離分類器。這樣的結(jié)果是令人滿意的。

把未知樣本x歸到離它最近的代表點(diǎn)所屬的類別，則可得到如圖中折線(即分界面Ⅱ所示的分段線性分界面，4.7.2分段線性判別函數(shù)

把上述基于距離的分段線性判別函數(shù)概念加以推廣。在前面，把每一類都分為若干子區(qū)域，并選擇各子區(qū)域的均值向量作為代表點(diǎn)以設(shè)計(jì)最小距離分類器。但這種方法只在某些特殊情況下才能得到較好的分類結(jié)果，在很多情況下往往不適用。例如圖4.4所示的樣本分布情況。圖中各類樣本服從正態(tài)但非等協(xié)方差分布，其等概率密度面為超橢球面，用虛線表示。利用貝葉斯決策規(guī)則對(duì)樣本x進(jìn)行分類，應(yīng)決策x∈ω2類；但若以μi作為代表點(diǎn)，按到μi的歐氏距離進(jìn)行分類，則應(yīng)決策x∈ω1類。這與貝葉斯決策相矛盾。μ1μ2x1x20x圖4.7.4只考慮作為各類或各子區(qū)域代表點(diǎn)所提供的信息是很不夠的。如何利用整個(gè)樣本集所提供的全部信息是需要考慮的問題。把每一類分為若干個(gè)子類，即令不是選擇各子類的均值作為代表點(diǎn)設(shè)計(jì)最小距離分類器，而是對(duì)于每個(gè)子類定義一個(gè)線性判別函數(shù)得到的決策面也是分段線性的，其決策面方程是由各子類的判別函數(shù)確定的，如果第i類的第n個(gè)子類和第j類的第m個(gè)子類相鄰，則該決策面方程是關(guān)鍵問題是如何利用樣本集確定子類數(shù)目以及如何求各子類的權(quán)向量和閾值權(quán)。

假如具有最大值的判別函數(shù)是，則把x歸到子類所屬的類，即類。4.7.3分段線性分類器設(shè)計(jì)的一般考慮

分類器設(shè)計(jì)的基本問題是，在一定判別函數(shù)類內(nèi)利用訓(xùn)練樣本集確定分類器的參數(shù)，即確定判別函數(shù)中的系數(shù)。設(shè)計(jì)線性分類器，就是確定權(quán)向量w和閾值權(quán)w0或廣義權(quán)向量a。而設(shè)計(jì)分段線性分類器，則是利用樣本集確定一組和。㈠利用多類線性判別函數(shù)算法設(shè)計(jì)分段線性分類器若已知樣本的子類劃分情況，可把子類看作獨(dú)立的類，然后利用多類線性判別函數(shù)算法把各個(gè)子類分開，自然也就把各類分開了。這種方法必須以已知子類劃分為前提。劃分子類的一種方法是根據(jù)先驗(yàn)知識(shí)直觀判定，如字符識(shí)別中，可把同一字符看作一類，而把其中不同的字體看作它的不同子類。另一種方法則借助于聚類分析方法來解決。步驟2利用訓(xùn)練樣本集進(jìn)行迭代，并按下列規(guī)則修改權(quán)向量：若在第k次迭代時(shí)，ωj類(j=1,2，…，c)中的樣本yi與ωj類的某個(gè)權(quán)向量的內(nèi)積值為最大，即而且滿足其中i=1，2，…，c，i≠j，l=1，2，…，li，則說明權(quán)向量組,,…,不影響yi正確分類，因此各權(quán)向量保持不變。則說明yj被錯(cuò)誤分類，需要對(duì)權(quán)向量進(jìn)行修正。設(shè)如果存在某個(gè)或幾個(gè)子類不滿足上述條件，即存在，使得則修正算法為步驟3重復(fù)上面的迭代過程，直到算法收斂或達(dá)到規(guī)定的迭代次數(shù)為止。當(dāng)樣本集對(duì)于給定的子類數(shù)目能用分段線性判別函數(shù)完全正確分類時(shí)，算法將在有限步內(nèi)收斂，否則算法將不收斂，這時(shí)可以考慮用遞減的ρk序列令算法收斂，但不可避免地會(huì)增大分類錯(cuò)誤率。ω1ω1ω2ω2圖4.7.5H1H4H2H3該分類器是分段線性的?！啊北硎緳?quán)向量ai

的方向，它指向超平面Hi的正側(cè)。它的識(shí)別過程是一個(gè)樹狀結(jié)構(gòu)，如圖4.7.6所示。圖中用虛線顯示了對(duì)未知樣本y的決策過程，經(jīng)過三步，判斷y∈ω1。ω1ω1ω2ω1ω2圖4.7.6YYYYNNNNaT1y≥0aT2y≥0aT3y≥0aT4y≥0通?？梢赃x擇分屬兩類的歐氏距離最小的一對(duì)樣本，取其垂直平分面的法向量ai

作為初始值，然后求得局部最優(yōu)解ai*作為第一段超平面的法向量。這種方法對(duì)初始權(quán)向量的選擇很敏感，其結(jié)果隨初始權(quán)向量ai

的不同而大不相同。在每個(gè)節(jié)點(diǎn)上所用的尋找權(quán)向量的方法不同，結(jié)果也將各異。對(duì)包含兩類樣本的各子類的劃分也可以采用同樣的方法。任何分段線性函數(shù)都可以表示為如下兩種一般形式：①分段線性函數(shù)的析取范式P=(L11∧L12∧…∧L1,m1)∨…∨(Lq1∧Lq2∧…∧Lq,mq)②分段線性函數(shù)的合取范式Q=(L11∨L12∨…∨L1,m1)∧…∧(Lq1∨Lq2∨…∨Lq,mq)用析取范式P表示一個(gè)分段線性函數(shù)，其中每個(gè)(L11∧L12∧…∧Li,mi)稱為一個(gè)凹函數(shù)，P是q個(gè)凹函數(shù)的并，即在q個(gè)凹函數(shù)中求最大凹函數(shù)。對(duì)于多峰分布的兩類問題，可以用分段線性判別函數(shù)P把其分開，P中的每個(gè)凹函數(shù)粗略地規(guī)定了某個(gè)類的一個(gè)峰，假設(shè)第一類呈現(xiàn)q個(gè)峰的分布，則P由q個(gè)凹函數(shù)Pi的并構(gòu)成，記為P=(P1∨P2∨…∨Pq)其中每個(gè)凹函數(shù)Pi又是mi個(gè)線性判別函數(shù)Lij的交構(gòu)成的，記為Pi

=(Li1∧Li2∧…∧Li,mi)例如，對(duì)于圖4.7所示的分布，q=3，m1=5，m2=4，m3=4。因此分段線性判別函數(shù)L11L12L13L14L15L21L22L23L24L31L32L33L34圖4.7P=(L11∧L12∧L13∧L14∧L15)

∨(L21∧L22∧L23∧L24)

∨(L31∧L32∧L33∧L34)P=max{min(L11，L12，L13，L14，L15)min(L21，L22，L23，L24)min(L31，L32，L33，L34)}在這兒，共有r=m1+m2+m3=13個(gè)線性判別函數(shù)。對(duì)于任意x∈ωi1，即x落入第一類的第i個(gè)子類中，所有的Lij

>0，j=1，2，…，mi，故Pi>0，因而P>0。而對(duì)于任意x∈ω2，因?yàn)樗械腜i≤0，i=1，2，3,因而P≤0。對(duì)于未知的樣本x，如果某個(gè)Pi>0，則x∈ωi1，因而x∈ω1。如果Pi≤0，i=1，2，3，x∈ω2。例4.1設(shè)有兩個(gè)未知樣本x1和x2，其分段線性判別函數(shù)的值分別為x1:L11=8L12=4L13=6L14=10L15=17L21=9L22=15L23=17L24=－3L31=－8L32=－7L33=9L34=－25x2:L11=26L12=－50L13=25L14=80L15=73L21=18L22=－4L23=－96L24=14L31=17L32=－6L33=－1L34=8∵P=max{min(L11，L12，L13，L14，L15)min(L21，L22，L23，L24)min(L31，L32，L33，L34)∴Px1=max{min(8,4,6,10,17),min(9,15,17,－3),min(－8,－7,9,－25)}=max{4,－3,－25}=4>0決策x1∈ω1Px2=max{min(26,－50,25,80,73),min(18,－4,－9,14),min(17,－6,－1,8)=max{－50,－9,－6}=－6<0決策x2∈ω2有了分段線性判別函數(shù)的定義，如何利用樣本集，求出r個(gè)權(quán)向量，，…，使之滿足。4.2.2算法步驟令X1和X2分別表示來自ω1和ω2類的樣本集。要找出若干個(gè)分段線性判別函數(shù)Pi組成的分段線性分類器，有效地對(duì)ω1和ω2進(jìn)行分類。假設(shè)用線性判別函數(shù)，i=1，2，…，r找出，，…，的迭代算法如下：

⑴檢驗(yàn)k是否為0，并選擇Ai1(k)和Ai2(k)。若k=0，則令A(yù)i1(0)，Ai2(0)，i=1，2，…，r分別是從X1和X2中任意選出的第一類和第二類樣本的非空子集。步驟1任意給定初始權(quán)向量a1(0)，a2(0)，…，a1(0)步驟2令a1(k)，a2(k)，…，ar(k)表示第k次迭代時(shí)得到的權(quán)向量，可按下述方式得到第k+1次迭代時(shí)的權(quán)向量a1(k+1)，a2(k+1)，…，ar(k+1)若k≠0。則令A(yù)i1(k)和Ai2(k)分別是X1和X2中所有滿足下式的樣本x組成的樣本子集，aiT(k)=P(x;a1(k),a2(k),…,ar(k))或?qū)懽魇街衖=1，2，…，r，很明顯，這樣的x一定最接近由ai(k)所決定的超平面⑵以Ai1和Ai2為樣本集，求第k+1次最優(yōu)權(quán)向量即找r個(gè)線性判別函數(shù)將Ai1和Ai2有效地分開。,i=1，2，…，r，這可用前面介紹的各種線性判別函數(shù)算法來解決，也可以作為初始權(quán)向量，經(jīng)過反復(fù)迭代找出最優(yōu)的權(quán)向量。步驟3檢驗(yàn)由構(gòu)成的分段線性判別函數(shù)P是否能正確分類樣本集X1和X2，若能，則就是所求的最優(yōu)權(quán)向量；若不能，則令k=k+1，重復(fù)上面的過程。直到算法收斂，或令k達(dá)到一個(gè)預(yù)先規(guī)定的上界為止。用圖4.8給出這種算法的框圖。其中：INUM表示以作初始權(quán)向量，為求最優(yōu)而限定的迭代次數(shù)。IPLS表示求分段線性判別函數(shù)中的a1*,a2*,…,a3*)的迭代次數(shù)的上限。IREP表示重新選擇初始權(quán)向量a1(0),a2(0),…,ar(0)以及Ai1(0)和Ai2(0)的次數(shù)。在圖4.8中，選擇IREP=10。I=1I>IREP?任意選擇初始權(quán)向量k=0k=0?按(4-19)式選擇Ai1(k)和Ai2(k)正確分X1和X2嗎？P(·)停機(jī)：輸出解向量集停機(jī)：將10次迭代中樣本錯(cuò)誤率最小的分段線性判別函數(shù)作為最終結(jié)果隨機(jī)選擇Ai1(0)和Ai2(0),i=1,2,…,rk=k+1k=IRLS?I=I+1YYYYNNNN圖4.8以為初始權(quán)向量以Ai1(k)和Ai2(k)為樣本集，求線性判別函數(shù)權(quán)向量限制迭代次數(shù)為INUM這種算法存在的主要問題是：⑴在算法執(zhí)行前，要首先判斷每類分布有多少個(gè)峰，從而決定選擇哪一類作設(shè)計(jì)，并確定設(shè)計(jì)幾個(gè)分段線性判別函數(shù)才符合要求。這就需要對(duì)樣本集有一定的先驗(yàn)知識(shí)。如果沒有足夠的先驗(yàn)知識(shí)，實(shí)驗(yàn)結(jié)果表明，只要選擇多于峰數(shù)的分段線性判別函數(shù)，結(jié)果也將是令人滿意的。這種算法存在的主要問題是(續(xù))：⑵在算法執(zhí)行前，要給出每個(gè)分段線性判別函數(shù)中分段的數(shù)目。⑶理論上沒有證明算法的收斂性。但大量實(shí)驗(yàn)結(jié)果表明，算法一般都能收斂到較好的結(jié)果。多設(shè)幾次權(quán)向量初值，并重新選擇Ai1(0)和Ai2(0)。4.7.2用交遇區(qū)的樣本設(shè)計(jì)分段線性分類器算法基本思想

這是一種實(shí)現(xiàn)最少分段線性分類器的方法。當(dāng)兩類樣本非線性可分時(shí)，貝葉斯分界面一般通過兩類樣本十分靠近或相互交迭的區(qū)域，稱之為"交遇區(qū)"。acbω1ω2圖4.10把這些區(qū)域找出來，利用這些區(qū)域中的樣本作為新的樣本集設(shè)計(jì)線性判別函數(shù)，然后把它們連在一起，就構(gòu)成了一個(gè)分段線性判別函數(shù)，這種方法稱為“局部訓(xùn)練法”，所得的分界面是分段線性分界面，它可以很好地逼近貝葉斯分界面。

如圖4.10所示，其中(a)(c)是交迭區(qū)，(b)是靠近區(qū)。綜上所述，這種方法大體需要解決以下幾個(gè)問題：

⑴如何從樣本集中找出“交遇區(qū)”；⑵如何利用“交遇區(qū)”中的樣本設(shè)計(jì)線性分類器；⑶如何進(jìn)行分類決策。

(一)緊互對(duì)原型對(duì)與交遇區(qū)

假設(shè)有兩類樣本集X1和X2。為找出交遇區(qū)，可先將每一類樣本用聚類分析方法分為若干個(gè)聚類。每個(gè)聚類在特征空間中占據(jù)一定區(qū)域，稱為“原型區(qū)”，每個(gè)聚類的重心，或最靠近重心的一個(gè)樣本，稱該聚類的“原型”。這樣，每個(gè)聚類可簡化為用它的原型來表示，每一類則由若干個(gè)原型來表示。用原型表示交遇區(qū)。令Vi表示ωi類的原型集合式中l(wèi)i為ωi類中的原型個(gè)數(shù)，用表示一個(gè)原型對(duì)，其中i,j=1,2，m=1,2,…,li,n=1,2…,lj。如果用表示兩個(gè)互對(duì)原型之間的歐氏距離，則當(dāng)且僅當(dāng)和之間的歐氏距離滿足當(dāng)i≠j時(shí)，原型對(duì)稱為互對(duì)的。時(shí)，稱為"緊互對(duì)原型對(duì)"，參見圖4.11所示的例子，圖中ω1ω2v11v21v31v12v22v32圖4.11原型對(duì)是一個(gè)緊互對(duì)原型對(duì)。不是緊互對(duì)原型對(duì)。用Φ表示兩類緊互對(duì)原型對(duì)集合，尋找Φ的方法可由下列步驟來完成：步驟1對(duì)于ω1類的每一個(gè)原型，在V2中找出離它最近的原型，并記集合步驟2用同樣的方法，對(duì)于每個(gè),在V1中找出離它最近的原型，并記集合步驟3找出L12和L21的交集Φ，Φ=L12∩L21

顯然，Φ中的緊互對(duì)原型對(duì)部位于兩類樣本的交遇區(qū)，因此，用緊互對(duì)原型對(duì)表示交遇區(qū)是合理的?？蓪颖镜木o互對(duì)原型對(duì)集合Φ擴(kuò)展到k——緊互對(duì)原型對(duì)集合Φ(k)。尋找Φ(k)的方法與尋找Φ的方法相似，所不同的是在第一、二步不是只找一個(gè)最近的原型，而是找出k個(gè)。k的選擇往往借助于經(jīng)驗(yàn)，有時(shí)取k=d=維數(shù)。4.3.3局部訓(xùn)練法

利用緊互對(duì)原型對(duì)集設(shè)計(jì)局部超平面的方法如下：

步驟l首先在k一緊互對(duì)原型對(duì)集合中找出最近的一對(duì)，用表示。

很容易找到一個(gè)超平面把這一對(duì)原型分開，為簡單起見，可以選擇和連線的垂直平分面，這個(gè)超平面的方程是稱這一超平面為。設(shè)計(jì)時(shí)可利用前面介紹的各種線性判別函數(shù)算法。步驟2以作為初始超平面，找出正確分類的緊互對(duì)原型對(duì)，用這些原型所代表的聚類中的所有樣本作為局部訓(xùn)練樣本集，并利用它設(shè)計(jì)第一個(gè)超平面段。假定是用某種方法找到的一個(gè)最佳超平面。這時(shí)，檢驗(yàn)所能正確分類的緊互對(duì)原型對(duì)。如果正確分類的緊互對(duì)原型對(duì)與正確分類的緊互對(duì)原型對(duì)相同，則就是所要求的第一段超平面H1；若不完全相同，則以作為初始超平面，重復(fù)上面過程，直至兩者完全相同為止，并記最后得到的超平面為H1。步驟3將被H1正確分類的緊互對(duì)原型對(duì)拿走，對(duì)剩下的緊互對(duì)原型對(duì)重復(fù)1、2兩個(gè)步驟，以得到第二個(gè)超平面段H2。步驟4重復(fù)上述步驟，直到所有的緊互對(duì)原型對(duì)都被處理完畢為止。這樣，就可以序貫地得到一組(比如說共有m個(gè))超平面H1，H2，…，Hm，它們構(gòu)成一個(gè)分段線性分類器。4.3.4決策規(guī)則

假設(shè)分段線性分類器是由m個(gè)超平面段組成的。其中每段超平面都可以表示為式中是超平面Hi的法向量。對(duì)于每段超平面Hi，它可能把樣本x分到它的正側(cè)，也可能分到它的負(fù)側(cè)。設(shè)時(shí)，即x在Hi正側(cè)時(shí)記為1，而時(shí)記為0。這樣，對(duì)于每個(gè)樣本x，由m個(gè)超平面可以產(chǎn)生一個(gè)m維、取值為0或1的向量。記這一向量為z(x)，則其元素zi(x)為這樣就得到z(x)=[z1(x)，z2(x)，…，zm(x)]對(duì)于訓(xùn)練集中的全部N個(gè)樣本，我們可以得到N個(gè)向量，記為z(x1)，z(x2)，…，z(xN)，其中每個(gè)z(xk)，k=1，2，…，N，都是一個(gè)m維由0或l組成的向量。因?yàn)閷?duì)于m維二值向量，最多有2m種可能的選擇，因此，每個(gè)z(xk)只能是2m種向量之一。對(duì)于這2m種可能的向量，統(tǒng)計(jì)其在兩類樣本集X1和X2中出現(xiàn)的次數(shù)，并分別記為N1(zj(x))和N2(zj(x))，j=1，2，…，2m。再定義一個(gè)開關(guān)函數(shù)Ω(zj)。如果N1(zj)和N2(zj)都很小，則記Ω(zj)=δ，否則這樣決策規(guī)則可寫作：如果N1(zj)和N2(zj)都較大，但二者差別較小，即，則說明可能還缺少超平面段，應(yīng)對(duì)這部分樣本重復(fù)上面的算法。

若

<舉例假設(shè)最終的分段線性分類器由三個(gè)超平面段組成，那么z(x)最多有23=8種可能的取值如下表所示，表中同時(shí)給出了決策規(guī)則。對(duì)于未知樣本x，如果z(x)=001或z(x)=111，則x∈ω1；如果z(x)=011或z(x)=100，則x∈ω2；否則拒絕。z(x)取值及決策規(guī)則表z(x)LΩ(z)決策000

δ拒絕001>1/21ω1010

δ拒絕011<1/20ω2100<1/20ω2101

δ拒絕110

δ拒絕111>1/21ω1這一決策過程可用4.12所示的框圖表示。序貫選擇Hi{Hi}Ω(z)ω1ω2拒絕xzj(x)圖4.12例4.3假設(shè)兩類樣本分布如圖4.13(a)所示，其中“×”表示第一類，“?！北硎镜诙?。說明分段線性分類器的設(shè)計(jì)過程。(a)解：

⑵從這些原型中找出2-緊互對(duì)原型對(duì)集合和，它們的交組成2-緊互對(duì)原型對(duì)集合Φ(2)。⑶利用局部訓(xùn)練法得到兩個(gè)超平面H1和H2，它們將樣本空間分為三個(gè)區(qū)域R1，R2和R3。R1