1、,模式識(shí)別 第五章非線性判別函數(shù),信息工程學(xué)院 袁立,5.1 引言,對(duì)實(shí)際的模式識(shí)別問(wèn)題來(lái)說(shuō)，各類在特征空間中的分布往往比較復(fù)雜，因此無(wú)法用線性分類函數(shù)得到好的效果。這就必須使用非線性的分類方法。,第五章 非線性判別函數(shù),由于樣本在特征空間分布的復(fù)雜性，許多情況下采用線性判別函數(shù)不能取得滿意的分類效果。非線性判別函數(shù) 例如右圖所示兩類物體在二維特征空間的分布，采用線性判別函數(shù)就無(wú)法取得滿意的分類效果。在這種情況下，可以采用分段線性判別或二次函數(shù)判別等方法，效果就會(huì)好得多。, 5.1 引言,在對(duì)待非線性判別分類問(wèn)題，有三種不同的方法： 第一：傳統(tǒng)的模式識(shí)別技術(shù)，側(cè)重于使用分段線性判別函數(shù)。 第二

2、：對(duì)基于錯(cuò)誤修正法的感知準(zhǔn)則函數(shù)進(jìn)行擴(kuò)展，人工神經(jīng)元網(wǎng)絡(luò)（多層感知器等網(wǎng)絡(luò)）能夠?qū)崿F(xiàn)復(fù)雜的非線性分類，以及非線性函數(shù)擬和，非線性映射等。 第三：支持向量機(jī)則提出了一種基于特征映射的方法，也就是使用某種映射，使本來(lái)在原特征空間必須使用非線性分類技術(shù)才能解決的問(wèn)題映射到一個(gè)新的空間以后, 使線性分類技術(shù)能繼續(xù)使用。,一種特殊的非線性判別函數(shù)分段線性判別函數(shù) 決策面由若干超平面段組成，計(jì)算比較簡(jiǎn)單 能逼近各種形狀的超曲面，適應(yīng)能力強(qiáng), 5.1 引言,5.2基于距離的分段線性判別函數(shù),出發(fā)點(diǎn)：如果兩類樣本可以劃分為線性可分的若干子類，則可以設(shè)計(jì)多個(gè)線性分類器，實(shí)現(xiàn)分段線性分類器。 基本思想：用均值作為

3、各類的代表點(diǎn)，用通過(guò)均值連線中點(diǎn)的垂直線對(duì)樣本集進(jìn)行分類,第五章 非線性判別函數(shù),把i類可以分成li個(gè)子類，或者說(shuō)，把屬于i 類的樣本區(qū)域Ri分為li個(gè)子區(qū)域。 現(xiàn)在定義mil表示第i類第j個(gè)子區(qū)域中樣本的均值向量，并以此作為該子區(qū)域的代表點(diǎn)。定義判別函數(shù)如下： （在同類的子類中找最近的均值。） 判別規(guī)則： 這是在M類中找最近均值。則把x歸于j類完成分類。,基于與類心距離的分段線性判別函數(shù), 5.2 基于距離的分段線性判別函數(shù),例：未知x,如圖： 先與1類各子類的均值比較，即 ，找一個(gè)最近的 與2各子類均值比較取最近的 因g2(x) g1(x) ，所以x2類 。, 5.2 基于距離的分段線性判

4、別函數(shù),利用均值代表一類有時(shí)有局限性，如下圖所示。若用線性判別函數(shù)代表一類，就會(huì)克服上述情況。, 5.2 基于距離的分段線性判別函數(shù),設(shè) 1, 2 ,m。而每一類又可以分為 子類。 對(duì)每個(gè)子類定義一個(gè)線性判別函數(shù)：,定義i類的線性判別函數(shù)為：,在各子類中找最大的判別函數(shù)作為此類的代表，則對(duì)于M類，可定義M個(gè)判別函數(shù)gi(x),i=1,2,.M,因此，決策規(guī)則為：, 5.2 基于距離的分段線性判別函數(shù),基于與分界面距離的分段線性判別函數(shù),對(duì)未知模式x， 把x先代入每類的各子類的判別函數(shù)中； 找出一個(gè)最大的子類判別函數(shù)，M類有M個(gè)最大子類判別函數(shù)； 在M個(gè)子類最大判別函數(shù)中，再找一個(gè)最大的； 則x

5、就屬于最大的子類判別函數(shù)所屬的那一類。,5.3 每類的子類數(shù)目已知錯(cuò)誤修正算法,在感知準(zhǔn)則函數(shù)中定義過(guò)：ai與aj代表兩類增廣權(quán)向量，y則代表增廣權(quán)向量。,一般來(lái)說(shuō)點(diǎn)積值比較大則表示這兩個(gè)向量在方向上比較一致，換句話說(shuō)向量間的夾角較小。,如果某一類樣本比較分散，但是能用若干個(gè)增廣權(quán)向量表示，使同一類增廣樣本向量能夠做到與代表自己一類的增廣權(quán)向量的點(diǎn)積的最大值，比與其它類增廣權(quán)向量的點(diǎn)積值要大，就可以做到正確分類。,因此這種算法就是要用錯(cuò)誤提供的信息進(jìn)行疊代修正。,第五章 非線性判別函數(shù),當(dāng)每類的子類數(shù)目已知時(shí)，可以采用假設(shè)初始權(quán)向量，然后由樣本提供的錯(cuò)誤率信息進(jìn)行迭代修正，直至收斂。,該算法的

6、基本要點(diǎn)是：,對(duì)每個(gè)類別的子類賦予一初始增廣權(quán)向量,然后對(duì)每次迭代所得增廣權(quán)向量用樣本去檢測(cè)，如發(fā)生錯(cuò)誤分類，則利用錯(cuò)誤分類的信息進(jìn)行修正。其做法是：,1）在第k次迭代時(shí)，將第j類的某個(gè)增廣樣本向量yj，與該類所有增廣權(quán)向量 求內(nèi)積，找到其中的最大值, 5.3 錯(cuò)誤修正算法,求內(nèi)積，并將這些內(nèi)積值與 作比較，,2)另一方面將該yj與其它類(如i類)的權(quán)向量,3）但是如果存在某個(gè)或幾個(gè)子類不滿足上述條件，譬如某個(gè)子類 的現(xiàn)有權(quán)向量 使得 這表明yj將錯(cuò)分類，而有關(guān)權(quán)向量需要修正。 如何修正呢？, 5.3 錯(cuò)誤修正算法,首先找到導(dǎo)致yj錯(cuò)分類的所有權(quán)向量中具有與yj內(nèi)積最大值的權(quán)向量 接著對(duì) 和

7、作相應(yīng)修正。 然后利用權(quán)向量的新值重復(fù)以上過(guò)程，直到收斂或迫使其收斂。 這種算法在樣本確實(shí)能被分段線性判別函數(shù)正確劃分的條件下是收斂的。, 5.3 錯(cuò)誤修正算法, 5.3 錯(cuò)誤修正算法, 5.3 錯(cuò)誤修正算法, 5.3 錯(cuò)誤修正算法, 5.3 錯(cuò)誤修正算法, 5.3 錯(cuò)誤修正算法, 5.3 錯(cuò)誤修正算法, 5.3 錯(cuò)誤修正算法,5.4 非線性可分條件下的支持向量機(jī),1維空間,作非線性變換：,通過(guò)非線性變換，非線性判決函數(shù)轉(zhuǎn)變成了線性判決函數(shù)；特征空間也由一維x空間映射成二維y空間。執(zhí)行非線性變換，特征空間維數(shù)的增長(zhǎng)往往不可避免。,此時(shí)g(x)被稱為廣義線性判別函數(shù)，a稱為廣義權(quán)向量。,廣義線性

8、判別函數(shù),二維 y 空間決策方程：,判決函數(shù)的正負(fù)側(cè)：,正側(cè)區(qū),g(y) = 0,二維 y 空間中廣義性判決函數(shù),廣義線性判決規(guī)則,變量代換,廣義線性判別函數(shù)的一般式：,因此，在 y 特征空間可線性表示一個(gè)非常復(fù)雜的 x 空間的決策函數(shù)，廣義線性函數(shù).,按照上述原理，任何非線性函數(shù)g(x)用級(jí)數(shù)展開成高次多項(xiàng)式后，都可轉(zhuǎn)化成廣義線性判別函數(shù)來(lái)處理。 wTy=0在Y空間確定了一個(gè)通過(guò)原點(diǎn)的超平面。這樣我們就可以利用線性判別函數(shù)的簡(jiǎn)單性來(lái)解決復(fù)雜的問(wèn)題。 這樣一來(lái)，線性分類方法就可以直接采用。這條路子在傳統(tǒng)的模式識(shí)別技術(shù)中并沒有持續(xù)研究下去，因?yàn)橐粋€(gè)突出的問(wèn)題是維數(shù)會(huì)急劇增加，在高維的空間中進(jìn)行計(jì)

9、算是傳統(tǒng)方法所忌諱的。但支持向量機(jī)方法的提出者們對(duì)這個(gè)問(wèn)題進(jìn)行了更深入一步的研究，他們堅(jiān)持了利用特征映射的方法，從而保留了線性劃分的計(jì)算框架。,通過(guò)特征映射，非線性可分的數(shù)據(jù)樣本在高維空間有可能轉(zhuǎn)化為線性可分。,SVM問(wèn)題求解,對(duì)非線性問(wèn)題, 可以通過(guò)非線性變換轉(zhuǎn)化為某個(gè)高維空間中的線性問(wèn)題, 在變換空間求最優(yōu)分類面. 這種變換可能比較復(fù)雜, 因此這種思路在一般情況下不易實(shí)現(xiàn)。.,核:,例如,2維向量x=x1 x2; 非線性映射(x) = 1 x12 2 x1x2 x22 2x1 2x2 設(shè) K(xi,xj)=(1 + xiTxj)2,；我們看看是否K(xi,xj)= (xi) T(xj)？ K(xi,xj)=(1 + xiTxj)2,= 1+ xi12xj12 + 2 xi1xj1 xi2xj2+ xi22xj22 + 2xi1xj1 + 2xi2xj2 = 1 xi12 2 xi1xi2 xi22 2xi1 2xi2T 1 xj12 2 xj1xj2 xj22 2xj1 2xj2 = (xi) T(xj),