第五章 非線性判別函數(shù)

第五章非線性判別函數(shù)第一頁，共三十頁，2022年，8月28日§5.1引言對實際的模式識別問題來說，各類在特征空間中的分布往往比較復(fù)雜，因此無法用線性分類函數(shù)得到好的效果。這就必須使用非線性的分類方法。第五章非線性判別函數(shù)由于樣本在特征空間分布的復(fù)雜性，許多情況下采用線性判別函數(shù)不能取得滿意的分類效果。－非線性判別函數(shù)例如右圖所示兩類物體在二維特征空間的分布，采用線性判別函數(shù)就無法取得滿意的分類效果。在這種情況下，可以采用分段線性判別或二次函數(shù)判別等方法，效果就會好得多。第二頁，共三十頁，2022年，8月28日§

5.1引言在對待非線性判別分類問題，有三種不同的方法：第一：傳統(tǒng)的模式識別技術(shù)，側(cè)重于使用分段線性判別函數(shù)。第二：對基于錯誤修正法的感知準(zhǔn)則函數(shù)進行擴展，人工神經(jīng)元網(wǎng)絡(luò)（多層感知器等網(wǎng)絡(luò)）能夠?qū)崿F(xiàn)復(fù)雜的非線性分類，以及非線性函數(shù)擬和，非線性映射等。第三：支持向量機則提出了一種基于特征映射的方法，也就是使用某種映射，使本來在原特征空間必須使用非線性分類技術(shù)才能解決的問題映射到一個新的空間以后,使線性分類技術(shù)能繼續(xù)使用。第三頁，共三十頁，2022年，8月28日一種特殊的非線性判別函數(shù)－分段線性判別函數(shù)決策面由若干超平面段組成，計算比較簡單能逼近各種形狀的超曲面，適應(yīng)能力強Ⅱ

Ⅲ

§

5.1引言第四頁，共三十頁，2022年，8月28日§5.2基于距離的分段線性判別函數(shù)出發(fā)點：如果兩類樣本可以劃分為線性可分的若干子類，則可以設(shè)計多個線性分類器，實現(xiàn)分段線性分類器?；舅枷耄河镁底鳛楦黝惖拇睃c，用通過均值連線中點的垂直線對樣本集進行分類第五章非線性判別函數(shù)第五頁，共三十頁，2022年，8月28日把ωi類可以分成li個子類，或者說，把屬于ωi類的樣本區(qū)域Ri分為li個子區(qū)域。現(xiàn)在定義mil表示第i類第j個子區(qū)域中樣本的均值向量，并以此作為該子區(qū)域的代表點。定義判別函數(shù)如下：（在同類的子類中找最近的均值。）判別規(guī)則：這是在M類中找最近均值。則把x歸于ωj類完成分類。基于與類心距離的分段線性判別函數(shù)§

5.2基于距離的分段線性判別函數(shù)第六頁，共三十頁，2022年，8月28日例：未知x,如圖：先與ω1類各子類的均值比較，即，找一個最近的與ω2各子類均值比較取最近的因g2(x)<g1(x)，所以x∈ω2類?！?/p>

5.2基于距離的分段線性判別函數(shù)第七頁，共三十頁，2022年，8月28日利用均值代表一類有時有局限性，如下圖所示。若用線性判別函數(shù)代表一類，就會克服上述情況?！?/p>

5.2基于距離的分段線性判別函數(shù)第八頁，共三十頁，2022年，8月28日設(shè)ω＝ω1,ω2,……ωm。而每一類又可以分為子類。對每個子類定義一個線性判別函數(shù)：定義ωi類的線性判別函數(shù)為：在各子類中找最大的判別函數(shù)作為此類的代表，則對于M類，可定義M個判別函數(shù)gi(x),i=1,2,…..M,因此，決策規(guī)則為：§

5.2基于距離的分段線性判別函數(shù)基于與分界面距離的分段線性判別函數(shù)對未知模式x，把x先代入每類的各子類的判別函數(shù)中；找出一個最大的子類判別函數(shù)，M類有M個最大子類判別函數(shù)；在M個子類最大判別函數(shù)中，再找一個最大的；則x就屬于最大的子類判別函數(shù)所屬的那一類。第九頁，共三十頁，2022年，8月28日§5.3每類的子類數(shù)目已知—錯誤修正算法

在感知準(zhǔn)則函數(shù)中定義過：ai與aj代表兩類增廣權(quán)向量，y則代表增廣權(quán)向量。

一般來說點積值比較大則表示這兩個向量在方向上比較一致，換句話說向量間的夾角較小。

如果某一類樣本比較分散，但是能用若干個增廣權(quán)向量表示，使同一類增廣樣本向量能夠做到與代表自己一類的增廣權(quán)向量的點積的最大值，比與其它類增廣權(quán)向量的點積值要大，就可以做到正確分類。

因此這種算法就是要用錯誤提供的信息進行疊代修正。

是ai向量與y向量的點積

是aj向量與y向量的點積第五章非線性判別函數(shù)第十頁，共三十頁，2022年，8月28日

當(dāng)每類的子類數(shù)目已知時，可以采用假設(shè)初始權(quán)向量，然后由樣本提供的錯誤率信息進行迭代修正，直至收斂。該算法的基本要點是：對每個類別的子類賦予一初始增廣權(quán)向量然后對每次迭代所得增廣權(quán)向量用樣本去檢測，如發(fā)生錯誤分類，則利用錯誤分類的信息進行修正。其做法是：1）在第k次迭代時，將第j類的某個增廣樣本向量yj，與該類所有增廣權(quán)向量求內(nèi)積，找到其中的最大值§

5.3錯誤修正算法第十一頁，共三十頁，2022年，8月28日

求內(nèi)積，并將這些內(nèi)積值與作比較，2)另一方面將該yj與其它類(如i類)的權(quán)向量

3）但是如果存在某個或幾個子類不滿足上述條件，譬如某個子類的現(xiàn)有權(quán)向量使得這表明yj將錯分類，而有關(guān)權(quán)向量需要修正。如何修正呢？

§

5.3錯誤修正算法第十二頁，共三十頁，2022年，8月28日

首先找到導(dǎo)致yj錯分類的所有權(quán)向量中具有與yj內(nèi)積最大值的權(quán)向量接著對和作相應(yīng)修正。

然后利用權(quán)向量的新值重復(fù)以上過程，直到收斂或迫使其收斂。這種算法在樣本確實能被分段線性判別函數(shù)正確劃分的條件下是收斂的。§

5.3錯誤修正算法第十三頁，共三十頁，2022年，8月28日§

5.3錯誤修正算法第十四頁，共三十頁，2022年，8月28日§

5.3錯誤修正算法第十五頁，共三十頁，2022年，8月28日§

5.3錯誤修正算法第十六頁，共三十頁，2022年，8月28日§

5.3錯誤修正算法第十七頁，共三十頁，2022年，8月28日§

5.3錯誤修正算法第十八頁，共三十頁，2022年，8月28日§

5.3錯誤修正算法第十九頁，共三十頁，2022年，8月28日§

5.3錯誤修正算法第二十頁，共三十頁，2022年，8月28日5.4非線性可分條件下的支持向量機1維空間第二十一頁，共三十頁，2022年，8月28日一維x空間中非線性判別函數(shù)例作非線性變換：通過非線性變換，非線性判決函數(shù)轉(zhuǎn)變成了線性判決函數(shù)；特征空間也由一維x空間映射成二維y空間。執(zhí)行非線性變換，特征空間維數(shù)的增長往往不可避免。此時g(x)被稱為廣義線性判別函數(shù)，a稱為廣義權(quán)向量。廣義線性判別函數(shù)第二十二頁，共三十頁，2022年，8月28日

二維

y空間決策方程：

判決函數(shù)的正負側(cè)：正側(cè)區(qū)g(y)=0二維y空間中廣義性判決函數(shù)廣義線性判決規(guī)則變量代換第二十三頁，共三十頁，2022年，8月28日廣義線性判別函數(shù)的一般式：因此，在y特征空間可線性表示一個非常復(fù)雜的x空間的決策函數(shù)，廣義線性函數(shù).按照上述原理，任何非線性函數(shù)g(x)用級數(shù)展開成高次多項式后，都可轉(zhuǎn)化成廣義線性判別函數(shù)來處理。wTy=0在Y空間確定了一個通過原點的超平面。這樣我們就可以利用線性判別函數(shù)的簡單性來解決復(fù)雜的問題。這樣一來，線性分類方法就可以直接采用。這條路子在傳統(tǒng)的模式識別技術(shù)中并沒有持續(xù)研究下去，因為一個突出的問題是維數(shù)會急劇增加，在高維的空間中進行計算是傳統(tǒng)方法所忌諱的。但支持向量機方法的提出者們對這個問題進行了更深入一步的研究，他們堅持了利用特征映射的方法，從而保留了線性劃分的計算框架。第二十四頁，共三十頁，2022年，8月28日通過特征映射，非線性可分的數(shù)據(jù)樣本在高維空間有可能轉(zhuǎn)化為線性可分。第二十五頁，共三十頁，2022年，8月28日SVM問題求解對非線性問題,可以通過非線性變換轉(zhuǎn)化為某個高維空間中的線性問題,在變換空間求最優(yōu)分類面.這種變換可能比較復(fù)雜,因此這種思路在一般情況下不易實現(xiàn)。.核:例如2維向量x=[x1x2];非線性映射φ(x)=

[1x12√2x1x2x22√2x1√2x2]設(shè)

K(xi,xj)=(1+xiTxj)2,；我們看看是否K(xi,xj)=φ(xi)

Tφ(xj)？K(xi,xj)=(1+xiTxj)2,=1+xi12xj12+2xi1xj1

xi2xj2+xi22xj22+2xi1xj1+2xi2xj2=[1xi12√2xi1xi2xi22√2xi1√2xi2]T[1xj12√2xj1xj2xj22√2xj1√2xj2]=φ(xi)

Tφ(xj),第二十六頁，共三十頁，2022年，8月28日這樣，我們通過核函數(shù)將原始空間的樣本映射到