第5章-非線性判別函數分析課件

模式識別 徐蔚然北京郵電大學信息工程學院非線性判別函數非線性判別函數傳統(tǒng)的模式識別技術，則側重于使用分段線性判別函數人工神經元網絡如多層感知器等網絡能夠實用非常復雜的非線性分類，以及非線性函數擬和，非線性映射等支持向量機則提出了一種基于特征映射的方法，也就是使用某種映射，使本來在原特征空間必須使用非線性分類技術才能解決的問題,映射到一個新的空間以后,使線性分類技術能繼續(xù)使用。5.1非線性判別函數與分段線性判別函數線性辨別函數以下只討論有關分段線性判別函數設計中的一些基本問題。分段線性判別二次函數判別分段段數問題分段段數問題分段段數過少，分類效果必然要差但段數又要盡可能少，以免分類判別函數過于復雜，增加分類決策的計算量同一類樣本可以用若干個子類來描述合適的子類劃分不知道，需要采用聚類方法分段線性判別函數的一般形式分段線性判別函數的一般形式表示第i類第l段線性判別函數li為i類所具有的判別函數個數，分別是第l段的權向量與閾值權。分段線性判別函數的一般形式相應的判別規(guī)則是：

如果其中則決策則稱為第i類的判別函數。分類的決策面方程:取決于相鄰的決策域，如第i類的第n個子類與第j類的第m個子類相鄰，則由它們共同決定的決策面方程為分段線性判別的主要問題分段線性判別的主要問題每一類的樣本數據在特征空間中的分布呈復雜修正時，使用線性判別函數就會產生很差的效果，如果能將它們分割成子集，而每個子集在空間聚集成團，那么子集與子集的線性劃分就可以取得比較好的效果。因此分段線性判別的主要問題是如何對數據劃分成子集的問題。5.2基于距離的分段線性判別函數正態(tài)分布條件下，兩類別問題在各特征統(tǒng)計獨立、同方差、且先驗概率相等情況下，最小錯誤率決策可按最小距離決策，即基于距離的分段線性判別函數分段線性距離分類器原理按距離分類的原理推廣把各類別樣本特征向量的均值作為各類的代表點，而樣本的類別按它到各類別代表點的最小距離劃分在這種判別函數中，決策面是兩類別均值連線的垂直平分面基于距離的分段線性判別函數基于距離的分段線性判別函數基于距離的分段線性判別函數分段線性距離分類器原理顯然這種判別方法只有在各類別密集地分布在其均值附近時才有效。對于上圖所示情況，若企圖再用每類一個均值代表點產生最小距離分類器，就會產生很明顯的錯誤率。在這種情況下，可以將各類別劃分成相對密集的子類，每個子類以它們的均值作為代表點，然后按最小距離分類基于距離的分段線性判別函數分段線性距離分類器原理歸納起來，如果對于ωi有l(wèi)i個子類，則有l(wèi)i個代表點，或者說把屬于ωi的決策域Ri分成li個子域，即對每個子區(qū)域Ril均值用mil表示，并以此作為該子區(qū)域的代表點，則判別函數定義為：相應的判別規(guī)則是：如果

，則X∈ωi

基于距離的分段線性判別函數

基于距離的分段線性判別函數對樣本進行子類的合適劃分是分段線性距離分類器性能好壞的一個關鍵問題

5.3錯誤修正算法錯誤修正法是對感知準則函數的擴展aiTy與ajTy相比較的含義:ai與aj代表兩類增廣權向量y則代表規(guī)范化的增廣權向量一般來說點積值比較大則表示這兩個向量在方向上比較一致， 換句話說向量間的夾角較小。錯誤修正算法思路如果某一類樣本比較分散能用若干個增廣權向量表示使同一類規(guī)范化增廣樣本向量能夠做到與代表自己一類的增廣權向量的點積的最大值比與其它類增廣權向量的點積值要大就可以做到正確分類。錯誤修正算法思路這種算法就是要用錯誤提供的信息進行疊代修正它對每類樣本集進行具體劃分希望能知道每類所需的增廣權向量數目實際上，該數目也可以在計算過程中按分類效果調整錯誤修正算法的基本要點當每類的子類數目已知時可以采用假設初始權向量然后由樣本提供的錯誤率信息進行迭代修正，直至收斂(1)對每個類別的子類賦予一初始增廣權向量，其中括號中的數目表示迭代次數。

錯誤修正算法的基本要點(2)然后對每次迭代所得增廣權向量用樣本去檢測，如發(fā)生錯誤分類，則利用錯誤分類的信息進行修正。其做法是：a)先將某一j類的增廣樣本向量yj，與該類所有增廣權向量aj-l(k)求內積aj-l(k)Tyj

，找到其中的最大值aj-m(k)Tyj

aj-m(k)Tyj=maxaj-l(k)Tyj錯誤修正算法的基本要點b)將該yj與其它類(如i類)的權向量求內積，并將這些內積值與作比較，若

aj-m(k)Tyj

≤ai-l(k)Tyj

i=1,…,c,i≠j,l=1,…,li

則表明權向量組，不影響yj的正確分類，因此不需要修改這些權向量錯誤修正算法的基本要點b)

但是如果存在某個或幾個子類不滿足上述條件，譬如某個子類的現(xiàn)有權向量使得

aj-m(k)Tyj

≤ai-n(k)Tyj

i≠j

這表明yj將錯分類，而有關權向量需要修正錯誤修正算法的基本要點c)此時首先找到導致yj錯分類的所有權向量中具有與yj內積最大值的權向量ai-n’(k)T

ai-n’(k)T=max(ai-n(k)Tyj

)

接著對aj-m(k)Tyj

與ai-n’(k)T作相應修正:錯誤修正算法的基本要點c)

然后利用權向量的新值重復以上過程，直到收斂或迫使其收斂。

收斂條件(訓練集錯誤率為零)這種算法在樣本確實能被分段線性判別函數正確劃分的條件下是收斂的但當該條件不滿足時，則需逐步減小ρk的數值，迫使其“收斂”會有相應的錯誤率存在5.4局部訓練法局部訓練法的思路出發(fā)點是類間的分界面必然處在兩類樣本的交界處因此只需找出這些交界處的樣本，然后對這些鄰近的不同類樣本,按需要確定分界面即可學習這一段主要能明白它的思路即可局部訓練法

局部訓練法局部訓練法的思路實際上決策面都處在不同類別樣本分布的交界處或鄰接處所在的區(qū)域內用這些區(qū)域中的樣本來決定判別函數，就可以代替用整個樣本集進行訓練?；谶@種思想的樣本訓練法稱為“局部訓練法”。局部訓練法局部訓練法的思路參加訓練的局部樣本集由兩類樣本組成。這些區(qū)域稱之為“交遇區(qū)”局部訓練法就是基于交遇區(qū)內的樣本進行設計的局部訓練法要解決的幾個問題(1)如何從樣本集中找到“交遇區(qū)”；(2)如何利用“交遇區(qū)”中的樣本設計線性分類器以及;(3)如何進行分類決策5.4.1緊互對原型與交遇區(qū)

尋找“交遇區(qū)”的一種思路其實質是先在每類樣本集內進行分片劃分，所使用的方法是聚類方法也可以采用別的方法。劃分的目的是使每類樣本劃分成小片后，找到處在本類樣本占領區(qū)域邊界上的小片原型。找到邊界子集的方法是通過與另一類樣本子集中找近鄰的方法實現(xiàn)的。5.4.1緊互對原型與交遇區(qū)

尋找“交遇區(qū)”的一種思路如果發(fā)現(xiàn)分屬兩類的兩個原型互為最近鄰，那么這兩個原型就被認定為處在兩類樣本決策域的交界處，它們所在區(qū)域就成為交遇區(qū)。交遇區(qū)就是有這些處在邊界上的原型集組成。為了簡便計算，每個小片(原型)都找出一質心，用它代表這個小片(也稱原型)。通過計算每個原型與其它原型的歐氏距離來計算近鄰關系。緊互對原型與交遇區(qū)尋找“交遇區(qū)”的具體方法(1)為了找到兩類樣本的交遇區(qū)，首先對這兩類樣本進行聚類分析，從而找出它們各自的一些相對密集的子區(qū)域，稱為“原型區(qū)”。(2)在每個原型區(qū)中找到一個質心或距質心很近的樣本作為各原型區(qū)的代表點，稱為“原型”。緊互對原型與交遇區(qū)緊互對原型與交遇區(qū)尋找“交遇區(qū)”的具體方法(3)然后在兩個類別的原型集合中，分別計算不同類原型對之間的歐氏距離，并找出各原型在對方類型中相距最近的原型對(4)從這些最小距離原型關系中找到互為最小距離的原型對(5)緊互對原型對的集合組成“交遇區(qū)”。有時可將緊互對原型對擴展成k-緊互對原型對5.4.2局部訓練法

局部訓練法利用“交遇區(qū)”來設計分界面的基本思想邊界由若干個交遇區(qū)確定，在每個交遇區(qū)中只有兩種不同類型的樣本由這些樣本產生一個合適的分界面，一般使用分段線性分界面具體做法是利用處于最緊貼邊界的緊互對原型對產生一初始分界面，然后利用交遇區(qū)進行調整，這種調整屬于局部性的調整局部訓練法具體做法步驟一：產生初始超平面首先由緊互對原型對集合中最近的一對，產生一個初始決策面的方程例如可由兩個原型的垂直平分平面作為初始界面，表示成H1局部訓練法具體做法步驟二：初始決策面最佳化確定H1能正確分類的所有緊互對原型對，并由這些原型對中的樣本組成局部訓練的樣本集按所使用的準則設計出線性決策面H1*

，該決策面對現(xiàn)有局部樣本集來說是最佳的局部訓練法具體做法步驟二：初始決策面最佳化對該H1決策面又可找出它能正確分類的所有緊互對原型對。如果H1*與H1’的分類效果相同，則不需再調整否則由作為初始決策面重復上述過程，直到所包羅的局部訓練樣本集不再發(fā)生變化為止局部訓練法具體做法步驟三：新決策面的產生與最佳化在找到一個最佳的決策面段后，將相應的局部訓練樣本從原緊互對原型對集合中撤走然后在剩下的緊互對原型對集合重復上述步驟，產生另一個超平面分界面如此重復下去直到所有緊互對原型對都被處理完畢，得到一系列超平面，組成分段線性分類器。5.4.3決策規(guī)則的確定

在使用上述方法得到一組超平面作為分段線性分類器的分界面僅對交遇區(qū)的樣本集進行性能檢測有時不能發(fā)現(xiàn)存在的問題需要使用全體樣本對其進行性能檢驗，觀察其能否對全體樣本作出合理的劃分決策規(guī)則的確定

決策規(guī)則的確定用向量表示樣本yj的所屬區(qū)域如果現(xiàn)有的決策界面數為m，需要表示出樣本yj的所屬區(qū)域每個決策超平面的增廣權向量為那么每一個樣本yj處在哪個區(qū)域，可用它們與這些增廣權向量的內積符號表示決策規(guī)則的確定用向量表示樣本yj的所屬區(qū)域可定義一個由樣本Xj(用增廣樣本向量yj表示)決策的m維向量來表示 其中因此處在同一區(qū)域的所有樣本都有同樣的向量值。決策規(guī)則的確定決策規(guī)則的確定全體樣本將被劃分若干子集，最大可能的子集數為2m個。每個子集都可能包含兩個類別的訓練樣本但在每個子集中兩類樣本分布的不同，將作為劃分與改進決策域的依據決策規(guī)則的確定計算比值函數

決策規(guī)則的確定根據L值及N1(ZK)與N2(ZK)這三個數據，可對各個區(qū)域作相應決定：1如果L>>1/2，則ZK區(qū)域為ω1的