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

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

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

Ⅲ

§

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

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

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

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

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

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

一般來(lái)說(shuō)點(diǎn)積值比較大則表示這兩個(gè)向量在方向上比較一致，換句話說(shuō)向量間的夾角較小。

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

因此這種算法就是要用錯(cuò)誤提供的信息進(jìn)行疊代修正。

是ai向量與y向量的點(diǎn)積

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

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

5.3錯(cuò)誤修正算法第十一頁(yè)，共三十頁(yè)，2022年，8月28日

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

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

§

5.3錯(cuò)誤修正算法第十二頁(yè)，共三十頁(yè)，2022年，8月28日

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

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

5.3錯(cuò)誤修正算法第十三頁(yè)，共三十頁(yè)，2022年，8月28日§

5.3錯(cuò)誤修正算法第十四頁(yè)，共三十頁(yè)，2022年，8月28日§

5.3錯(cuò)誤修正算法第十五頁(yè)，共三十頁(yè)，2022年，8月28日§

5.3錯(cuò)誤修正算法第十六頁(yè)，共三十頁(yè)，2022年，8月28日§

5.3錯(cuò)誤修正算法第十七頁(yè)，共三十頁(yè)，2022年，8月28日§

5.3錯(cuò)誤修正算法第十八頁(yè)，共三十頁(yè)，2022年，8月28日§

5.3錯(cuò)誤修正算法第十九頁(yè)，共三十頁(yè)，2022年，8月28日§

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

二維

y空間決策方程：

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