1、1,第5章 非線性判別函數(shù),實(shí)際問題經(jīng)常不是線性可分的，即決策面是非線性函數(shù)。,常用方法：, 分段線性函數(shù)，見P83 圖5-3，采用距離為分類標(biāo)準(zhǔn)，一般要求對(duì)樣本的分布有所了解。,關(guān)鍵是子類數(shù)目，權(quán)值確定也比較復(fù)雜。,直接使用非線性判別函數(shù)，如神經(jīng)網(wǎng)絡(luò)方法。,非線性支持向量機(jī)，公認(rèn)是比較好的分類器設(shè)計(jì)方法。,異或(XOR)問題,不存在決策線將兩類分開.,2,而與和或問題是線性可分的,兩層感知器,對(duì)于問題, 可以劃兩條線，而不是一條線。見下頁圖形,3,B類位于陰影區(qū)域之外，而A類位于陰影區(qū)域之內(nèi)。,分類器可以采用兩階段的設(shè)計(jì)方法。,階段1 劃兩條線（超平面）,每條線由一個(gè)感知器實(shí)現(xiàn),階段2 根據(jù)

2、 y1, y2 的值確定 x 相對(duì)兩條線的位置,等價(jià)地: 階段1 實(shí)現(xiàn)如下影射,4,決策在變換后的數(shù)據(jù) y 域進(jìn)行:,可以再劃一條線，將兩類分開，該線用一個(gè)感知器實(shí)現(xiàn)。,階段1實(shí)現(xiàn)了一個(gè)映射，將線性不可分問題轉(zhuǎn)化為線性可分問題。,神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)如下圖所示。,5,這是一個(gè)兩層感知機(jī)，包含一個(gè)隱層和一個(gè)輸出層。激活函數(shù)為,圖中的神經(jīng)元實(shí)現(xiàn)以下直線（超平面）,誤差反向傳播算法,迭代計(jì)算連接權(quán)值的算法程序，使代價(jià)函數(shù)最小化,6,優(yōu)化過程需要計(jì)算導(dǎo)數(shù)，不連續(xù)的激活函數(shù)存在問題,可以采用下面的連續(xù)函數(shù)近似，也可以采用其他函數(shù),函數(shù)中的 a 決定了函數(shù)的近似程度。,有兩種訓(xùn)練方法,批量訓(xùn)練方法：所有樣本一起

3、計(jì)算誤差，統(tǒng)一調(diào)節(jié)權(quán)值,單樣本訓(xùn)練方法：每個(gè)樣本誤差調(diào)節(jié)一次權(quán)值,7,8,主要問題: 算法可能收斂到局部極小值,9,過擬合問題網(wǎng)絡(luò)把噪聲的信息也學(xué)來了，推廣能力差,10,廣義線性判別函數(shù),回憶異或問題，映射,激活函數(shù)把非線性問題變換成線性問題。,一般情況，是否存在函數(shù)與合適的 k，通過映射,把分類問題轉(zhuǎn)換為線性的？,如果是這樣，得到 則存在超平面 wRk，得到如下分類器,因此，可以把判別函數(shù)近似表示為,11,徑向基函數(shù)網(wǎng)絡(luò) Radial Basis Function Networks (RBF),選擇非線性函數(shù)為徑向基函數(shù),徑向基函數(shù)示意圖,12,等價(jià)于激活函數(shù)為RBF函數(shù)的單層神經(jīng)網(wǎng)絡(luò),13

4、,例:用RBF網(wǎng)絡(luò)解決異或(XOR)問題,定義RBF函數(shù)的中心和寬度為,隱層神經(jīng)元輸出為,14,RBF網(wǎng)絡(luò)的分類結(jié)果,15,RBF 網(wǎng)絡(luò)訓(xùn)練,固定中心: 在數(shù)據(jù)點(diǎn)中間隨機(jī)選擇中心，寬度i心也是固定的，那么,變成典型的線性分類器設(shè)計(jì)問題,中心訓(xùn)練是非線性優(yōu)化問題，可以采用監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)相結(jié)合的方法進(jìn)行分類器設(shè)計(jì)。,RBF 網(wǎng)絡(luò)具有局部性質(zhì)，收斂速度快但推廣能力弱。,多層感知器與RBF 網(wǎng)絡(luò)比較,采用聚類分析方法確定中心，再用監(jiān)督學(xué)習(xí)方法進(jìn)行線性分類器設(shè)計(jì)。,多層感知器具有全局性質(zhì)，收斂速度慢但推廣能力強(qiáng)。,16,非線性支持向量機(jī),特征向量的維數(shù)增加可以增大樣本線性可分的概率。,采用下面的非

5、線性映射,在Rk空間采用支持向量機(jī)分類,需要在高維空間計(jì)算內(nèi)積，計(jì)算復(fù)雜性增加,解決方法：高維空間內(nèi)積表示成低維空間內(nèi)積的函數(shù),17,Mercer 定理,則對(duì)任意函數(shù),H空間內(nèi)積定義為,下式成立,（5-50）,反之若（5-50）式成立，則 K(x , x) 一定對(duì)應(yīng)某個(gè)空間H的內(nèi)積,K(x , x) 是對(duì)稱的，稱為核函數(shù)。,常用的核函數(shù),多項(xiàng)式核函數(shù),RBF核函數(shù),Sigmoid 核函數(shù),18,非線性支持向量機(jī)分類步驟,Step 1: 選擇核函數(shù)。隱含著一個(gè)到高維空間的映射，雖然不知道具體形式。,Step 2: 求解優(yōu)化問題,s. t. C ai 0，i=1,2,N,(5-48）,結(jié)果得到隱式

6、組合,Step 3： 對(duì)給定樣本 x 進(jìn)行分類,19,非線性支持向量機(jī)結(jié)構(gòu),20,21,決策樹Decision Trees,This is a family of non-linear classifiers. They are multistage decision systems, in which classes are sequentially rejected, until a finally accepted class is reached.,決策樹屬于非線性分類器。它是多階段的決策系統(tǒng)，決策過程順序拒絕一些類，一直達(dá)到最終接受的類為止。,The feature space is

7、 split into unique regions in a sequential manner.,通過順序劃分方法將特征空間分解為唯一的區(qū)域（屬于唯一的一個(gè)類）。,Upon the arrival of a feature vector, sequential decisions, assigning features to specific regions, are performed along a path of nodes of an appropriately constructed tree.,對(duì)于未知類別的特征向量，通過順序決策，將其分派到特定的區(qū)域，該過程通過對(duì)事先構(gòu)造樹的

8、節(jié)點(diǎn)路徑搜索來實(shí)現(xiàn)。,The sequence of decisions is applied to individual features, and the queries performed in each node are of the type:,對(duì)每個(gè)特征順序決策，每個(gè)節(jié)點(diǎn)進(jìn)行下面類型的判定：,is feature,a是預(yù)先選擇的閾值參數(shù),The figures below are such examples.,This type of trees is known as Ordinary Binary Classification.,The decision hyperplanes, splitting