非參數(shù)判別分類方法課件

3.3感知準(zhǔn)則函數(shù)感知準(zhǔn)則函數(shù)是五十年代由Rosenblatt提出的一種自學(xué)習(xí)判別函數(shù)生成方法，由于Rosenblatt企圖將其用于腦模型感知器，因此被稱為感知準(zhǔn)則函數(shù)。其特點(diǎn)是隨意確定的判別函數(shù)初始值，在對(duì)樣本分類訓(xùn)練過程中逐步修正直至最終確定。用感知準(zhǔn)則函數(shù)設(shè)計(jì)線性分類器是一種十分重要的方法。4/2/202312.樣本的規(guī)范化決策面方程：

令結(jié)論：規(guī)范化后合適的a能使所有的Y'滿足aTY'

>0。3.3.1幾個(gè)基本概念1.線性可分性如果對(duì)一個(gè)樣本集N，總能找到一個(gè)增廣權(quán)向量a，對(duì)該樣本集所有樣本實(shí)現(xiàn)正確分類，則這種情況稱為具有線性可分性。4/2/20232中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.解向量和解區(qū)解向量：在線性可分的前提下，滿足aTYn>0，n=1,2,…,N的權(quán)向量稱為解向量。解區(qū)：N個(gè)樣本所對(duì)應(yīng)的解向量a所在區(qū)域之交迭空間。在解區(qū)內(nèi)的任一向量a能使所有樣本得到正確劃分。4/2/20233中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院梯度下降算法定義一個(gè)準(zhǔn)則函數(shù)J(a)，當(dāng)a是解向量時(shí)，J(a)最小。隨機(jī)確定初始解向量a(1)，計(jì)算其對(duì)準(zhǔn)則函數(shù)的梯度下降，下一個(gè)a(2)由自a(1)向下降最陡的方向移動(dòng)一段距離而得到，即沿梯度的負(fù)方向移動(dòng)。其中，

是正的比例因子，即用于設(shè)定步長(zhǎng)的學(xué)習(xí)率。4/2/20235中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院用梯度下降算法求感知準(zhǔn)則函數(shù)極小值感知準(zhǔn)則函數(shù)Jp(a)其中，Yk是被權(quán)向量a錯(cuò)分類的樣本集合。感知準(zhǔn)則函數(shù)Jp(a)對(duì)a求梯度：可以證明，對(duì)于線性可分的樣本集，經(jīng)過有限次修正，一定可以找到一個(gè)解向量a，即算法能在有限步內(nèi)收斂。其收斂速度的快慢取決于初始權(quán)向量a(1)和系數(shù)。4/2/20236中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院例：三個(gè)樣本的分類問題解向量的修正過程4/2/20237中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.4多類問題在兩類別問題中使用的線性判別函數(shù)方法可以推廣到多類別問題中。（1）將C類別問題化為(C-1)個(gè)兩類問題，即將第i類與所有非i類樣本，按兩類問題確定其判別函數(shù)與決策面方程。因此對(duì)于C類，則總共有(C-1)個(gè)兩類別問題。（2）將C類中的每?jī)深悇e單獨(dú)設(shè)計(jì)其線性判別函數(shù)，因此總共有C(C-1)/2個(gè)線性判別函數(shù)。4/2/20239中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院判別邊界示意圖存在的問題：出現(xiàn)一些不定區(qū)域用線性判別函數(shù)對(duì)i類及所有非i類進(jìn)行劃分并不能保證獲得性能良好的劃分，硬性使用線性分類器可能會(huì)產(chǎn)生很不好的效果。4/2/202310中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院線性機(jī)器將特征空間確實(shí)劃分為C個(gè)決策域，共有C個(gè)判別函數(shù)。每個(gè)決策域Ri按以下規(guī)則劃分：如果則線性機(jī)器中決策域的邊界由相鄰決策域的判別函數(shù)共同決定。4/2/202311中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.5非線性判別函數(shù)由于樣本在特征空間分布的復(fù)雜性，許多情況下采用線性判別函數(shù)不能取得滿意的分類效果。傳統(tǒng)的模式識(shí)別技術(shù)，則側(cè)重于使用分段線性判別函數(shù)。人工神經(jīng)元網(wǎng)絡(luò)如多層感知器等網(wǎng)絡(luò)能夠適用非常復(fù)雜的非線性分類，以及非線性函數(shù)擬和，非線性映射等，這將在人工神經(jīng)元網(wǎng)絡(luò)這一章討論。支持向量機(jī)則提出了一種基于特征映射的方法，也就是使用某種映射，使本來在原特征空間必須使用非線性分類技術(shù)才能解決的問題,映射到一個(gè)新的空間以后,使線性分類技術(shù)能繼續(xù)使用。4/2/202313中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.5.1分段線性判別函數(shù)線性判別函數(shù)分段線性判別函數(shù)二次判別函數(shù)圖5.1分段線性判別函數(shù)示意圖4/2/202314中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院分段線性判別函數(shù)分段線性判別函數(shù)設(shè)計(jì)中首先要解決的問題是分段線性判別函數(shù)的分段段數(shù)問題。主要討論在樣本分布及子類劃分大體已定的情況下，設(shè)計(jì)分段線性判別函數(shù)的問題，著重討論幾種典型的設(shè)計(jì)原理。4/2/202315中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.5.2基于距離的分段線性判別函數(shù)圖5.2最小距離分類器圖5.3用多個(gè)最小距離分類器組成分段線性分類面4/2/202317中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院如果對(duì)于ωi有l(wèi)i個(gè)子類，則有l(wèi)i個(gè)代表點(diǎn)，或者說把屬于ωi的決策域Ri分成li個(gè)子域，即Ri={Ri1,Ri2,…,Rili}對(duì)每個(gè)子區(qū)域Ril均值用mil表示，并以此作為該子區(qū)域的代表點(diǎn)，則判別函數(shù)定義為：如果相應(yīng)的判別規(guī)則是：4/2/202318中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院分段線性距離分類器性能好壞的一個(gè)關(guān)鍵問題：對(duì)樣本進(jìn)行子類的合適劃分。圖5.4最小距離分類器不適用的情況4/2/202319中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院錯(cuò)誤修正算法的基本步驟當(dāng)每類的子類數(shù)目已知時(shí)，可以采用假設(shè)初始權(quán)向量，然后由樣本提供的錯(cuò)誤率信息進(jìn)行迭代修正，直至收斂。（1）對(duì)每個(gè)類別的子類賦予一初始增廣權(quán)向量。ai1(1),ai2(1),…,aili(1),i=1,2,…,cail(k)表示第k次迭代時(shí),第i類第l個(gè)子類的增廣權(quán)向量。4/2/202321中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院ajm(k)T

yj≤ain(k)T

yj,

ij若存在某個(gè)或某幾個(gè)子類ωin不滿足上述條件，即則說明yj被錯(cuò)誤分類，需要對(duì)權(quán)向量進(jìn)行修正。ai’n’(k)T

yj=max{ain(k)T

yj},修正算法為：ai’n’(k+1)T=ai’n’(k)T-ρk

yj

ajm(k+1)T=ajm(k)T+ρk

yj

（2）利用訓(xùn)練樣本集進(jìn)行迭代，并按下列規(guī)則修正增廣權(quán)向量。ajm(k)T

yj=max{ajl(k)T

yj},l=1,2,…,ljajm(k)T

yj>ail(k)T

yj,i=1,2,…,c,l=1,2,…,ljij若滿足則權(quán)向量組ai1(k),ai2(k),…,aili(k),i=1,2,…,c不影響yj正確分類，因此各權(quán)向量保持不變。（3）重復(fù)上述迭代過程，直到收斂或達(dá)到最大迭代次數(shù)。4/2/202322中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.5.4用交遇區(qū)的樣本設(shè)計(jì)分段線性分類器（局部訓(xùn)練法）算法思想圖5.10交遇區(qū)類間的分界面必然處在兩類樣本的交界處，因此只需找出這些交界處的樣本，然后對(duì)這些鄰近的不同類樣本,按需要確定分界面?；谶@種思想的樣本訓(xùn)練法稱為“局部訓(xùn)練法”。4/2/202323中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院緊互對(duì)原型對(duì)與交遇區(qū)先在每類樣本集內(nèi)進(jìn)行分片劃分，所使用的方法是聚類方法。找到處在本類樣本占領(lǐng)區(qū)域邊界上的小片原型。如果發(fā)現(xiàn)分屬兩類的兩個(gè)原型互為最近鄰，那么這兩個(gè)原型就被認(rèn)定為處在兩類樣本決策域的交界處，它們所在區(qū)域就成為交遇區(qū)。圖5.10緊互對(duì)原型對(duì)4/2/202325中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院找出“原型區(qū)”。圖中V11,V12,V13等是ω1的若干個(gè)原型區(qū),而V21,V22,V23等是ω2的原型區(qū)。在每個(gè)原型區(qū)中找到一個(gè)質(zhì)心或距質(zhì)心很近的樣本作為各原型區(qū)的代表點(diǎn)，稱為“原型”。找出各原型在對(duì)方類型中相距最近的原型對(duì)，如V21的最近原型是V11，而V11的最近原型是V22等?！熬o互對(duì)原型對(duì)”：從這些最小距離原型關(guān)系中找到互為最小距離的原型對(duì)，如V12與V23

。緊互對(duì)原型對(duì)的集合組成“交遇區(qū)”。4/2/202326中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院步驟三：新決策面的產(chǎn)生與最佳化在找到一個(gè)最佳的決策面段后，將相應(yīng)的局部訓(xùn)練樣本從原緊互對(duì)原型對(duì)集合中撤走，然后在剩下的緊互對(duì)原型對(duì)集合重復(fù)上述步驟，產(chǎn)生另一個(gè)超平面分界面。步驟四：重復(fù)上述步驟，直到所有緊互對(duì)原型對(duì)都被處理完畢，得到一系列超平面，組成分段線性分類器。4/2/202329中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院分段線性分類器檢驗(yàn)一個(gè)決策規(guī)則的確定

在使用上述方法得到一組超平面作為分段線性分類器的分界面后，僅對(duì)交遇區(qū)的樣本集進(jìn)行性能檢測(cè)有時(shí)不能發(fā)現(xiàn)存在的問題，需要使用全體樣本對(duì)其進(jìn)行性能檢驗(yàn)，觀察其能否對(duì)全體樣本作出合理的劃分。4/2/202330中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院如果現(xiàn)有的決策界面數(shù)為m，每個(gè)決策超平面的增廣權(quán)向量為aiT

，i=1,2,…,c。定義向量在z(X),記錄X屬于決策界面的正測(cè)還是負(fù)側(cè)。處在同一區(qū)域的所有樣本都有同樣的向量值，將被劃分若干子集，最大可能的子集數(shù)為2m個(gè)。每個(gè)子集中兩類樣本的分布，作為劃分與改進(jìn)決策域的依據(jù)。4/2/202331中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院用NT(Zk)表示在第k個(gè)子集中第l類訓(xùn)練樣本的個(gè)數(shù)，k＝1,2,…,2m,l＝1,2。定義一個(gè)比值函數(shù)L表示每個(gè)子集中ω1類樣本所占比例。根據(jù)L值及N1(Zk)與N2(Zk)這三個(gè)數(shù)據(jù)，可對(duì)各個(gè)區(qū)域作相應(yīng)決定：

1如果L>1/2，則Zk區(qū)域?yàn)棣?的決策域；

2如果L<1/2，則Zk區(qū)域?yàn)棣?的決策域；

3如果L≈1/2，以及N1(Zk),N2(Zk)很小，則對(duì)Zk內(nèi)樣本可作拒絕決策；

4如果L≈1/2，但N1(Zk)與N2(Zk)數(shù)量不可忽略，則對(duì)此區(qū)域，用該子集的樣本再次進(jìn)行局部訓(xùn)練法訓(xùn)練，以獲得其