第三章線性和非線性判別分析第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準(zhǔn)則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準(zhǔn)則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹4貝葉斯估計(jì)：先驗(yàn)概率和類條件概率密度已知，通過貝葉斯公式，來(lái)求解后驗(yàn)概率的問題。實(shí)際問題中，類條件概率密度可能并不知道，這種情況下，可以采用非參數(shù)估計(jì)——當(dāng)樣本比較充足的時(shí)候，估計(jì)類條件概率密度的方法。但實(shí)際中，有時(shí)候并沒有充分的樣本，同時(shí)存在樣本維數(shù)比較高，這種情況下，可能會(huì)使類條件概率密度估計(jì)不準(zhǔn)確，我們就采用另一種方法。線性判別函數(shù)：我們直接假設(shè)判別函數(shù)，我們用樣本估計(jì)判別函數(shù)的參數(shù)，這樣就省去了估計(jì)類條件概率。在這一章之后，都采用這種方式。我們直接估計(jì)決策面或判別函數(shù)。這種情況下，最簡(jiǎn)單的是假設(shè)判別函數(shù)是線性函數(shù)。決策面是超平面。3.1Fisher線性判別5假設(shè)判別函數(shù)是線性的時(shí)候，利用樣本用什么準(zhǔn)則來(lái)求解這個(gè)判別函數(shù)的參數(shù)？當(dāng)判別函數(shù)的參數(shù)有了，這個(gè)判別函數(shù)就確定了，這樣決策面也就確定了。如果假設(shè)判別函數(shù)為線性函數(shù)，包含參數(shù)w和w0。當(dāng)準(zhǔn)則函數(shù)不同，求解出的參數(shù)就存在不同。貝葉斯決策中，最小錯(cuò)誤率和最小風(fēng)險(xiǎn)就是準(zhǔn)則函數(shù)，不同的準(zhǔn)則最終判別函數(shù)存在不同。貝葉斯分類器，它使得錯(cuò)誤率或風(fēng)險(xiǎn)達(dá)到最小，是所有分類器中的最優(yōu)分類器。而其他準(zhǔn)則函數(shù)下得到的分類器稱為次優(yōu)分類器。后續(xù)章節(jié)中介紹的準(zhǔn)則函數(shù)，求出的是給定準(zhǔn)則下的最優(yōu)解。求得的最優(yōu)解并不是這個(gè)問題的最優(yōu)解。既然是次優(yōu)解，為什么去研究？因?yàn)樵跇颖居邢耷闆r下，簡(jiǎn)單容易實(shí)現(xiàn)，計(jì)算代價(jià)，存儲(chǔ)量，求解速度快。所以，線性判別函數(shù)方法廣泛使用。3.1Fisher線性判別63.1Fisher線性判別7方程g(x)=0定義了一個(gè)決策面，把歸于不同類的點(diǎn)分割開來(lái)，當(dāng)g(x)為線性函數(shù)時(shí)，這個(gè)決策面便是超平面。3.1Fisher線性判別8設(shè)計(jì)線性分類器的步驟3.1Fisher線性判別9Fisher線性判別出發(fā)點(diǎn)：—應(yīng)用統(tǒng)計(jì)方法解決模式識(shí)別問題時(shí)，一再碰到的問題之一就是維數(shù)問題。—在低維空間里解析上或計(jì)算上行得通的方法，在高維空間里往往行不通?！档途S數(shù)有時(shí)就會(huì)成為處理實(shí)際問題的關(guān)鍵。問題描述：對(duì)兩分類問題，考慮把d維空間的樣本投影到一條直線上，形成一維空間，即把維數(shù)壓縮到一維，同時(shí)保持較好的分類性能。3.1Fisher線性判別引言10如何根據(jù)實(shí)際數(shù)據(jù)找到一條最好的、最易于分類的投影方向，這就是Fisher判別方法所要解決的基本問題。（1）降低維數(shù)，降低計(jì)算復(fù)雜度；（2）易于分類的；3.1Fisher線性判別11假設(shè)有一集合D包含m個(gè)n維樣本{x1,x2,…,xm}

第一類樣本集合記為D1，規(guī)模為N1第二類樣本集合記為D2，規(guī)模為N2若對(duì)xi的分量做線性組合可得標(biāo)量：yi

=wTxi,i=1,2,…,m這樣便得到m個(gè)一維樣本yi組成的集合，并可分為兩個(gè)子集D'1和D'2。從d維空間到一維空間的一般數(shù)學(xué)變換方法—w的值是無(wú)關(guān)緊要的，它僅使x乘上一個(gè)比例因子，重要的是選擇w的方向。它將影響樣本投影后的可分離程度?！鲜鰧ふ易罴淹队胺较虻膯栴}，在數(shù)學(xué)上就是尋找最好的變換向量w*的問題。3.1Fisher線性判別Fisher準(zhǔn)則函數(shù)基本思想12最佳投影方向的評(píng)價(jià)依據(jù)：

使兩類樣本在該軸上投影之間的距離盡可能遠(yuǎn)，而每一類樣本的投影盡可能緊湊。如何度量？評(píng)價(jià)標(biāo)準(zhǔn)—類內(nèi)離散度矩陣，類間離散度矩陣x1x2w1H:g=0w23.1Fisher線性判別13

在n維X空間(1)各類樣本的均值向量：(2)樣本類內(nèi)離散度矩陣Si和總樣本類內(nèi)離散度矩陣SwFisher準(zhǔn)則函數(shù)中的基本參量其中Sw是對(duì)稱半正定矩陣，而且當(dāng)m>n時(shí)通常是非奇異的。(3)樣本類間離散度矩陣Sb其中Sb是對(duì)稱半正定矩陣。3.1Fisher線性判別14

在一維Y空間(1)各類樣本的均值:

(2)樣本類內(nèi)離散度

和總樣本類內(nèi)離散度Fisher準(zhǔn)則函數(shù)中的基本參量(3)樣本類間離散度3.1Fisher線性判別15

目標(biāo)：投影后，在一維Y空間中各類樣本盡可能分得開些，即使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開，類內(nèi)樣本投影盡可能密集的要求.Fisher準(zhǔn)則函數(shù)3.1Fisher線性判別16

目標(biāo)：投影后，在一維Y空間中各類樣本盡可能分得開些，即使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開，類內(nèi)樣本投影盡可能密集的要求.Fisher準(zhǔn)則函數(shù)：Fisher最佳投影方向的求解:不同類的投影點(diǎn)盡量分開同一類的投影點(diǎn)盡量靠近Fisher準(zhǔn)則函數(shù)3.1Fisher線性判別17Fisher準(zhǔn)則函數(shù)由各類樣本均值可推出：投影樣本均值之差可以展開為：將J(w)變成w的顯函數(shù)3.1Fisher線性判別18由類內(nèi)散布矩陣可推出：于是有：Fisher準(zhǔn)則函數(shù)準(zhǔn)則函數(shù)可以寫為：3.1Fisher線性判別19要求使J(w)最大的w，可以采用Lagrange乘子法求解。假設(shè)分母等于非零常數(shù)，即：定義Lagrange函數(shù)為：最佳變換向量w*的求取

矩陣/向量求導(dǎo)法則3.1Fisher線性判別20要求使J(w)最大的w，可以采用Lagrange乘子法求解。假設(shè)分母等于非零常數(shù)，即：定義Lagrange函數(shù)為：對(duì)w求偏導(dǎo)數(shù)，令偏導(dǎo)數(shù)為0：即：標(biāo)量R最佳變換向量w*的求取

3.1Fisher線性判別21由于w的模對(duì)問題本身無(wú)關(guān)緊要，因此降維：對(duì)樣本集合作線性變換w*Tx，得到n個(gè)樣本投影后

的樣本值y1，y2，……，ynFisher線性判別分析3.1Fisher線性判別22一維空間的分類面是一個(gè)點(diǎn)將兩類分開即是確定一個(gè)閾值分類規(guī)則:Fisher線性分類3.1Fisher線性判別23例：兩組訓(xùn)練數(shù)據(jù)D1和D2D1=[-0.4,0.58,0.089;-0.31,0.27,-0.04;-0.38,0.055,-0.035;-0.15,0.53,0.011;-0.35,0.47,0.034;0.17,0.69,0.1;-0.011,0.55,-0.18;-0.27,0.61,0.12;-0.065,0.49,0.0012;-0.12,0.054,-0.063]D2=[0.83,1.6,-0.014;1.1,1.6,0.48;-0.44,-0.41,0.32;0.047,-0.45,1.4;0.28,0.35,3.1;-0.39,-0.48,0.11;0.34,-0.079,0.14;-0.3,-0.22,2.2;1.1,1.2,-0.46;0.18,-0.11,-0.49]例題3.1Fisher線性判別（1）求取兩組訓(xùn)練數(shù)據(jù)D1和D2的均值向量

和由公式：得:例題3.1Fisher線性判別（2）然后求取兩組訓(xùn)練數(shù)據(jù)D1和D2的類內(nèi)散度矩陣Si和總樣本類內(nèi)離散度矩陣Sw。由公式：得:例題3.1Fisher線性判別（3）求取最佳變換向量w*

由公式：得投影方向（4）求閾值由公式：得例題3.1Fisher線性判別（5）將兩組訓(xùn)練數(shù)據(jù)D1和D2作線性變換，得到20個(gè)樣本投影后的樣本值兩組數(shù)據(jù)投影后的樣本值分別為：例題3.1Fisher線性判別28訓(xùn)練效果圖：例題3.1Fisher線性判別測(cè)試數(shù)據(jù)和

：計(jì)算投影變換和：由：得：判別準(zhǔn)則：例題3.1Fisher線性判別301.Fisher辨別分析要求：在UCI數(shù)據(jù)集上的Iris和sonar數(shù)據(jù)上驗(yàn)證算法的有效性；Iris數(shù)據(jù)3類，4維，150個(gè)數(shù)據(jù)；Sonar數(shù)據(jù)2類，60維，208個(gè)樣本；訓(xùn)練和測(cè)試樣本有三種方式進(jìn)行劃分：（三選一）1）將數(shù)據(jù)隨機(jī)分訓(xùn)練和測(cè)試，多次平均求結(jié)果2）k折交叉驗(yàn)證3）留1法仿真結(jié)果+報(bào)告。第一次大作業(yè)3.1Fisher線性判別第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準(zhǔn)則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹幾個(gè)基本概念線性可分樣本的規(guī)范化解向量和解區(qū)對(duì)解區(qū)的限制3.2感知準(zhǔn)則函數(shù)線性可分性假設(shè)樣本集，為樣本個(gè)數(shù)m，為n維向量，其中包含兩類和。如果存在一個(gè)向量，滿足如下條件，則稱樣本集是線性可分的，反之是線性不可分的。33幾個(gè)基本概念3.2感知準(zhǔn)則函數(shù)樣本的規(guī)范化對(duì)于線性可分的樣本集，若令則樣本集線性可分的條件可改寫為。上述過程就被稱為樣本的規(guī)范化。被稱為規(guī)范化增廣樣本向量，后續(xù)介紹中，我們簡(jiǎn)化記為。34幾個(gè)基本概念3.2感知準(zhǔn)則函數(shù)解向量和解區(qū)對(duì)于線性可分的一組樣本(規(guī)范化增廣樣本向量)，若存在一個(gè)權(quán)向量滿足則稱為一個(gè)解向量，在權(quán)值空間中所有解向量組成的區(qū)域稱作為解區(qū)。35幾個(gè)基本概念3.2感知準(zhǔn)則函數(shù)對(duì)解區(qū)的限制由于解向量不唯一，我們可以通過加入額外的限制得到更好的選擇。一般認(rèn)為，越靠近解區(qū)中間的解向量，似乎越能對(duì)新的樣本正確分類。因此，我們可以選找一個(gè)單位長(zhǎng)度的解向量使之最大化樣本到分界面的距離，也可以引用一個(gè)余量

，尋找對(duì)所有樣本滿足的最小長(zhǎng)度的向量。新的解區(qū)位于原解區(qū)之中，而且它的邊界到原解區(qū)邊界的距離為。實(shí)際上，只要解向量嚴(yán)格位于解區(qū)之中都能滿足要求，這里引入余量主要是為了避免求解權(quán)向量的算法收斂到解區(qū)邊界的某點(diǎn)上。36幾個(gè)基本概念3.2感知準(zhǔn)則函數(shù)37幾個(gè)基本概念解向量和解區(qū)的兩維示意圖解區(qū)里面的向量叫解向量；讓它線性可分的解不唯一；準(zhǔn)則不同，落在這個(gè)解區(qū)中的解不同；但準(zhǔn)則確定，解一般是唯一的。3.2感知準(zhǔn)則函數(shù)感知準(zhǔn)則出發(fā)點(diǎn)一旦判別函數(shù)的形式確定下來(lái)，不管它是線性的還是非線性的，剩下的問題就是如何確定它的系數(shù)。在模式識(shí)別中，系數(shù)確定的一個(gè)主要方法就是通過對(duì)已知樣本的訓(xùn)練和學(xué)習(xí)來(lái)得到。感知器算法就是通過訓(xùn)練樣本模式的迭代和學(xué)習(xí)，產(chǎn)生線性（或廣義線性）可分的模式判別函數(shù)。感知準(zhǔn)則函數(shù)，是人工神經(jīng)網(wǎng)絡(luò)的雛形，最早的人工神經(jīng)網(wǎng)絡(luò)就是感知器神經(jīng)網(wǎng)絡(luò)。感知器準(zhǔn)則求解過程，線性判別函數(shù)形式一但確定，通過樣本不斷試錯(cuò)糾正迭代來(lái)求解更新參數(shù)w和w0的過程。給定一個(gè)w和w0的初始值，來(lái)一個(gè)樣本，如果這個(gè)參數(shù)結(jié)果不好，就進(jìn)行修正，如果結(jié)果好，就保留，不斷這樣迭代，等所有樣本都可以正確劃分，保留這時(shí)的參數(shù)，就是最終要求解的參數(shù)。3.2感知準(zhǔn)則函數(shù)感知器算法基本思想采用感知器算法(PerceptionApproach)能通過對(duì)訓(xùn)練模式樣本集的“學(xué)習(xí)”得到判別函數(shù)的系數(shù)說明這里采用的算法不需要對(duì)各類別中模式的統(tǒng)計(jì)性質(zhì)做任何假設(shè)，因此稱為確定性的方法。3.2感知準(zhǔn)則函數(shù)對(duì)于權(quán)向量w，如果某個(gè)樣本被錯(cuò)誤分類，。我們可以用對(duì)所有錯(cuò)分樣本的求和來(lái)表示對(duì)錯(cuò)分樣本的懲罰，定義感知器準(zhǔn)則函數(shù)：當(dāng)且僅當(dāng)函數(shù)取得最小值0時(shí)，求得最優(yōu)的w。可以用梯度下降法進(jìn)行求解。3.2感知準(zhǔn)則函數(shù)樣本線性可分滿足：其中，梯度下降算法3.2感知準(zhǔn)則函數(shù)梯度下降算法梯度是一個(gè)向量，它的最重要性質(zhì)就是指出了函數(shù)f在其自變量y增加時(shí)最大增長(zhǎng)率的方向。負(fù)梯度指出f的最陡下降方向利用這個(gè)性質(zhì)，可以設(shè)計(jì)一個(gè)迭代方案來(lái)尋找函數(shù)的最小值3.2感知準(zhǔn)則函數(shù)討論若正確地選擇了準(zhǔn)則函數(shù)J(w,x)，則當(dāng)權(quán)向量w是一個(gè)解時(shí)，J達(dá)到極小值（J的梯度為零）。為了使權(quán)向量能較快地收斂于一個(gè)使函數(shù)J極小的解，C值的選擇是很重要的。若C值太小，則收斂太慢；若C值太大，則搜索可能過頭，引起發(fā)散。梯度下降算法3.2感知準(zhǔn)則函數(shù)3.2感知準(zhǔn)則函數(shù)感知器算法3.2感知準(zhǔn)則函數(shù)感知器算法感知器算法實(shí)質(zhì)上是一種賞罰過程對(duì)正確分類的模式則“賞”，實(shí)際上是“不罰”，即權(quán)向量不變。對(duì)錯(cuò)誤分類的模式則“罰”，使w(k)加上一個(gè)正比于Xk的分量。當(dāng)用全部模式樣本訓(xùn)練過一輪以后，只要有一個(gè)模式是判別錯(cuò)誤的，則需要進(jìn)行下一輪迭代，即用全部模式樣本再訓(xùn)練一次。如此不斷反復(fù)直到全部模式樣本進(jìn)行訓(xùn)練都能得到正確的分類結(jié)果為止。3.2感知準(zhǔn)則函數(shù)感知器算法的收斂性只要模式類別是線性可分的，就可以在有限的迭代步數(shù)里求出權(quán)向量。如果有一個(gè)樣本線性不可分，那么感知器算法就會(huì)一直迭代，無(wú)法收斂。這是它的局限性。3.2感知準(zhǔn)則函數(shù)感知器算法采用感知器算法的多類模式的分類討論這個(gè)分類算法都是通過訓(xùn)練樣本來(lái)確定判別函數(shù)的系數(shù)，并沒有考慮到測(cè)試樣本，但一個(gè)分類器的性能最終用未知的測(cè)試樣本來(lái)檢驗(yàn)。要使一個(gè)分類器設(shè)計(jì)完善，必須采用有代表性的正確的訓(xùn)練數(shù)據(jù)，它能夠合理反映模式數(shù)據(jù)的整體。如果訓(xùn)練樣本中有噪聲樣本，就會(huì)影響分類的性能。局限性在于對(duì)噪聲數(shù)據(jù)敏感，解不夠魯棒。3.2感知準(zhǔn)則函數(shù)采用感知器算法的多類模式的分類討論要獲得一個(gè)判別性能好的線性分類器，究竟需要多少訓(xùn)練樣本？直觀上是越多越好，但實(shí)際上能收集到的樣本數(shù)目會(huì)受到客觀條件的限制；過多的訓(xùn)練樣本在訓(xùn)練階段會(huì)使計(jì)算機(jī)需要較長(zhǎng)的運(yùn)算時(shí)間；一般來(lái)說，合適的樣本數(shù)目可如下估計(jì)： 若k是模式的維數(shù)，令C=2(k+1)，則通常選用的訓(xùn)練樣本數(shù)目約為C的10~20倍。3.2感知準(zhǔn)則函數(shù)50三種梯度下降優(yōu)化框架批量梯度下降法（BatchGradientDescent,BGD）每次使用全部的訓(xùn)練樣本來(lái)更新模型參數(shù)/學(xué)習(xí)；優(yōu)點(diǎn)：每次更新都會(huì)朝著正確的方向進(jìn)行，最后能夠保證收斂于極值點(diǎn)；缺點(diǎn)：每次學(xué)習(xí)時(shí)間過長(zhǎng)，并且如果訓(xùn)練集很大以至于需要消耗大量的內(nèi)存，不能進(jìn)行在線模型參數(shù)更新。3.2感知準(zhǔn)則函數(shù)51隨機(jī)梯度下降法（StochasticGradientDescent,SGD）隨機(jī)梯度下降算法每次從訓(xùn)練集中隨機(jī)選擇一個(gè)樣本來(lái)進(jìn)行學(xué)習(xí)；優(yōu)點(diǎn)：每次只隨機(jī)選擇一個(gè)樣本來(lái)更新模型參數(shù)，因此每次的學(xué)習(xí)是非?？焖俚模⑶铱梢赃M(jìn)行在線更新；SGD波動(dòng)帶來(lái)的好處，在類似盆地區(qū)域，即很多局部極小值點(diǎn)，那么這個(gè)波動(dòng)的特點(diǎn)可能會(huì)使得優(yōu)化的方向從當(dāng)前的局部極小值點(diǎn)調(diào)到另一個(gè)更好的局限極小值點(diǎn)，這樣便可能對(duì)于非凹函數(shù)，最終收斂于一個(gè)較好的局部極值點(diǎn)，甚至全局極值點(diǎn)。缺點(diǎn)：每次更新可能并不會(huì)按照正確的方向進(jìn)行，因此會(huì)帶來(lái)優(yōu)化波動(dòng)，使得迭代次數(shù)增多，即收斂速度變慢。3.2感知準(zhǔn)則函數(shù)52小批量梯度下降法（Mini-batchGradientDescent,SGD）小批量梯度下降綜合了batch梯度下降與stochastic梯度下降，在每次更新速度與更新次數(shù)中間一個(gè)平衡，其每次更新從訓(xùn)練集中隨機(jī)選擇k(k<m)個(gè)樣本進(jìn)行學(xué)習(xí)；優(yōu)點(diǎn)：相對(duì)于隨機(jī)梯度下降，Mini-batch梯度下降降低了收斂波動(dòng)性，即降低了參數(shù)更新的方差，使得更新更加穩(wěn)定；相對(duì)于批量梯度下降，其提高了每次學(xué)習(xí)的速度；MBGD不用擔(dān)心內(nèi)存瓶頸從而可以利用矩陣運(yùn)算進(jìn)行高效計(jì)算；3.2感知準(zhǔn)則函數(shù)第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準(zhǔn)則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹54對(duì)于非線性問題，線性判別函數(shù)難以正確分類，而且設(shè)計(jì)非線性判別函數(shù)比較復(fù)雜。此時(shí)，常用的方法是將原特征空間映射到一個(gè)高維空間，將低維空間中的非線性問題轉(zhuǎn)化為高維空間中的線性問題，從而降低模式分類的難度。3.3廣義線性判別分析例：如右圖，55對(duì)于非線性問題，線性判別函數(shù)難以正確分類，而且設(shè)計(jì)非線性判別函數(shù)比較復(fù)雜。此時(shí)，常用的方法是將原特征空間映射到一個(gè)高維空間，將低維空間中的非線性問題轉(zhuǎn)化為高維空間中的線性問題，從而降低模式分類的難度。3.3廣義線性判別分析例：如右圖，二次判別函數(shù)可以表達(dá)為563.3廣義線性判別分析廣義線性判別函數(shù)這樣一個(gè)非線性判別函數(shù)通過映射，變換成線性判別函數(shù)。原始的特征空間是非線性，但通過某種映射，在新的空間能保證是線性函數(shù)，原始空間的判別函數(shù)為廣義線性判別函數(shù)。判別函數(shù)的一般形式：3.3廣義線性判別分析第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準(zhǔn)則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹近鄰法

近鄰法則是一種根據(jù)樣本提供的信息，繞開概率的估計(jì)而直接決策的技術(shù)，所以它也屬于非參數(shù)判別方法的一種。（沒有訓(xùn)練過程）模式識(shí)別的基本方法有兩大類，一類是將特征空間劃分成決策域，這就要確定判別函數(shù)和分界面方程（線性判別函數(shù)）。而另一種方法則稱為模板匹配，即將待分類樣本與標(biāo)準(zhǔn)模板進(jìn)行比較，看跟哪個(gè)模板匹配度更好些，從而確定待測(cè)試樣本的分類。近鄰法

線性判別函數(shù)是將特征空間劃分為決策域，并用判別函數(shù)或決策面方程表示決策域的方法。近鄰法則在原理上屬于模板匹配。它將訓(xùn)練樣本集中的每個(gè)樣本都作為模板，用測(cè)試樣本與每個(gè)模板做比較，看與哪個(gè)模板最相似(即為近鄰)，就按最近似的模板的類別作為自己的類別。譬如A類有10個(gè)訓(xùn)練樣本，因此有10個(gè)模板，B類有8個(gè)訓(xùn)練樣本，就有8個(gè)模板。任何一個(gè)待測(cè)試樣本在分類時(shí)與這18個(gè)模板都算一算相似度，如最相似的那個(gè)近鄰是B類中的一個(gè)，就確定待測(cè)試樣本為B類，否則為A類。因此原理上說近鄰法是最簡(jiǎn)單的。近鄰法

但是近鄰法有一個(gè)明顯的缺點(diǎn):就是計(jì)算量大，存儲(chǔ)量大，要存儲(chǔ)的模板很多，每個(gè)測(cè)試樣本要對(duì)每個(gè)模板計(jì)算一次相似度，因此在模板數(shù)量很大時(shí)，計(jì)算量也很大的。

思想簡(jiǎn)單，有一個(gè)如此明顯缺點(diǎn)的方法還有沒有存在的必要性呢？?jī)?yōu)點(diǎn):在模板數(shù)量很大時(shí)其錯(cuò)誤率指標(biāo)還是相當(dāng)不錯(cuò)的。該方法普適性比較好。常用來(lái)作為一個(gè)基準(zhǔn)算法。

結(jié)論:這就是說近鄰法有存在的必要。最近鄰法則最近鄰法:將與測(cè)試樣本最近鄰樣本的類別作為決策的方法。對(duì)一個(gè)C類別問題，每類有Ni個(gè)樣本，i＝1，…，C，則第i類ωi的判別函數(shù)

其中表示是ωi類的第k個(gè)樣本。對(duì)于C類：決策規(guī)則為：如果則決策X∈ωj。

最近鄰法則

最近鄰法在原理上最直觀，方法上也十分簡(jiǎn)單，只要對(duì)所有樣本(共N＝∑Ni)進(jìn)行N次距離運(yùn)算，然后以最小距離者的類別作決策。

公式中用‖·‖表示距離，其實(shí)這是一個(gè)象征性的表示，可以采用任何一種相似性的度量，一般采用歐氏距離為相似性度量的較多。但由于特征向量各個(gè)分量之間對(duì)應(yīng)的物理意義很可能不一致，因此究竟采用何種相似性度量要看問題而定。

近鄰法則的錯(cuò)誤率實(shí)際問題中，近鄰法的錯(cuò)誤率是比較難算的，因?yàn)橛?xùn)練樣本集的數(shù)量總是有限的，有時(shí)多一個(gè)少一個(gè)訓(xùn)練樣本對(duì)測(cè)試樣本分類的結(jié)果影響很大。譬如圖中:(A3)

紅點(diǎn)表示A類訓(xùn)練樣本，藍(lán)點(diǎn)表示B類訓(xùn)練樣本綠點(diǎn)O表示待測(cè)樣本。假設(shè)以歐氏距離來(lái)衡量，O的最近鄰是A3，其次是B1，因此O應(yīng)該屬于A類，但若A3被拿開，O就會(huì)被判為B類。這說明計(jì)算最近鄰法的錯(cuò)誤率會(huì)有偶然性，也就是指與具體的訓(xùn)練樣本集有關(guān)。計(jì)算錯(cuò)誤率的偶然性會(huì)因訓(xùn)練樣本數(shù)量的增大而減小。隨著訓(xùn)練樣本的增加，準(zhǔn)確率會(huì)有所提高。因此人們就利用訓(xùn)練樣本數(shù)量增至極大，來(lái)對(duì)其性能進(jìn)行評(píng)價(jià)。

近鄰法則的錯(cuò)誤率最近鄰法則

最近鄰規(guī)則是次優(yōu)的方法，通常的錯(cuò)誤率比最小可能錯(cuò)誤率（即最小貝葉斯法則的錯(cuò)誤率）要大。但在無(wú)限訓(xùn)練樣本的情況下，這個(gè)錯(cuò)誤率不會(huì)超過貝葉斯錯(cuò)誤率的一倍。小于等于兩倍，錯(cuò)誤率有上限的。當(dāng)訓(xùn)練樣本足夠多時(shí)：最近鄰法的錯(cuò)誤率要高于貝葉斯錯(cuò)誤率，可以證明以下關(guān)系式成立：

最近鄰法的漸近平均錯(cuò)誤率的下、上界分別為貝葉斯錯(cuò)誤率及

由于一般情況下

很小，因此上式又可粗略表示成

近鄰法則的錯(cuò)誤率

因此可以說最近鄰法的漸近平均錯(cuò)誤率在貝葉斯錯(cuò)誤率的兩倍之內(nèi)。從這點(diǎn)說最近鄰法是優(yōu)良的，因此它是模式識(shí)別重要方法之一。近鄰法則的錯(cuò)誤率

最近鄰方法最近的樣本可能受噪聲影響。最近鄰法可以擴(kuò)展成找測(cè)試樣本的k個(gè)最近樣本作決策依據(jù)的方法。k近鄰基本規(guī)則是，在所有N個(gè)樣本中找到與測(cè)試樣本的k個(gè)最近鄰者，其中第i個(gè)類別所占個(gè)數(shù)為gi(X),i＝1，…，c，決策規(guī)則：如果

則決策X∈ωj

。K-近鄰法則k近鄰一般采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策?？梢赃@樣理解:K近鄰算法從測(cè)試樣本點(diǎn)開始生長(zhǎng)，不斷擴(kuò)大區(qū)域，直到包含進(jìn)k個(gè)訓(xùn)練樣本點(diǎn)為止，并且把X歸為這最近的k個(gè)訓(xùn)練樣本點(diǎn)中出現(xiàn)頻率最大的類別中。如圖為k=5的情況。K-近鄰法則

在N→∞的條件下，k-近鄰法的錯(cuò)誤率要低于最近鄰法。從圖中也可看出，無(wú)論是最近鄰法，還是k-近鄰法，其錯(cuò)誤率的上下界都是在一倍到兩倍貝葉斯決策方法的錯(cuò)誤率范圍內(nèi)。不同k值時(shí)的錯(cuò)誤率情況K-近鄰法則的錯(cuò)誤率：K-近鄰法則最近鄰法和K近鄰法的共同優(yōu)點(diǎn)是簡(jiǎn)單，而且結(jié)果比較好，但仍存在不少缺點(diǎn)：

(1)要求的計(jì)算機(jī)存儲(chǔ)容量和計(jì)算量相當(dāng)大。

(2)沒有考慮到?jīng)Q策風(fēng)險(xiǎn)。

(3)以上的分析是建立在無(wú)窮多樣本的基礎(chǔ)上的，對(duì)于有限樣本的情況，缺乏理論上的分析。K-近鄰法則732.近鄰法數(shù)據(jù)：1）USPS手寫體2）UCI數(shù)據(jù)庫(kù)中sonar數(shù)據(jù)源3）UCI數(shù)據(jù)庫(kù)中Iris數(shù)據(jù)驗(yàn)證算法：不進(jìn)行降維，1）K近鄰方法分類；2）最近鄰方法分類；對(duì)比算法：fisher+K近鄰（最近鄰）作業(yè)形式：程序+大報(bào)告+上機(jī)課演示第二次大作業(yè)第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準(zhǔn)則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹3.5.1決策樹分類介紹3.5.2ID33.5.3C4.5決策樹簡(jiǎn)介決策樹：（適合離散屬性的分類問題）一種多級(jí)分類器，它采用分級(jí)的形式，綜合用多個(gè)決策規(guī)則，逐步把復(fù)雜的多類別分類問題轉(zhuǎn)化為若干個(gè)簡(jiǎn)單的分類問題來(lái)解決n1n2n3n4n5t1t2t3t4t5t6t7多類

問題根節(jié)點(diǎn)：所有樣本集合葉子節(jié)點(diǎn)：分完類的樣本集合，每個(gè)集合屬于同一類別二叉決策樹二叉決策樹：除葉節(jié)點(diǎn)外，決策樹的每個(gè)節(jié)點(diǎn)ni都有且只有兩個(gè)子節(jié)點(diǎn)nil和nir。二叉決策樹把復(fù)雜的多類別分類問題轉(zhuǎn)化為多級(jí)兩類分類問題來(lái)解決。在每個(gè)節(jié)點(diǎn)ni，都把樣本集分成兩個(gè)子集。每個(gè)子集可能仍包含多類別的樣本，繼續(xù)分直至僅包含單類別樣本的葉節(jié)點(diǎn)n1n2n3n4t1t2t5x2≤5x1≤2x3≤4x2≤2ω1ω2ω3ω2ω3t3t4多類

問題簡(jiǎn)介決策樹方法的起源是概念學(xué)習(xí)系統(tǒng)，然后發(fā)展到ID3（處理離散屬性）方法而為高潮，最后又演化為能處理連續(xù)屬性的C4.5。有名的決策樹方法還有CART和Assistant（處理缺失屬性的數(shù)據(jù)，比如互聯(lián)網(wǎng)數(shù)據(jù)）。是應(yīng)用最廣的歸納推理算法之一一種逼近離散值目標(biāo)函數(shù)的方法對(duì)噪聲數(shù)據(jù)有很好的健壯性且能學(xué)習(xí)析取表達(dá)式，之前的線性判別函數(shù)中的感知器函數(shù)對(duì)噪聲特別敏感，決策樹對(duì)噪聲魯棒性較好決策樹舉例決策樹樹的基礎(chǔ)知識(shí)樹的結(jié)構(gòu)示意圖決策樹的表示法決策樹通過把實(shí)例（樣本）從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例，葉子節(jié)點(diǎn)即為實(shí)例所屬的分類。樹上的每一個(gè)節(jié)點(diǎn)說明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試，并且該節(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值（二叉決策樹：是或否）例子類標(biāo)示例天氣溫度濕度風(fēng)力打網(wǎng)球1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo圖離散屬性：若干個(gè)確定的特征值14個(gè)訓(xùn)練樣本，2分類問題，4個(gè)屬性表達(dá)式?jīng)Q策樹代表實(shí)例屬性值約束的合取的析取式。屬性之間的合?。ㄇ业年P(guān)系），多種情況下的析取（或的關(guān)系）。從樹根到樹葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取，樹本身對(duì)應(yīng)這些合取的析取。（基于規(guī)則的分類）決策樹學(xué)習(xí)的適用問題實(shí)例是由‘屬性-值’對(duì)表示的:如實(shí)例是用一系列固定的屬性（例如，Temperature）和它們的值（離散的值）（例如，Hot）來(lái)描述的目標(biāo)函數(shù)具有離散的輸出值:決策樹給每個(gè)實(shí)例賦予一個(gè)布爾型的分類（例如，yes或no），如果是多分類，就是多個(gè)離散輸出。決策樹方法很容易擴(kuò)展到學(xué)習(xí)有兩個(gè)以上輸出值的函數(shù)。一種更強(qiáng)有力的擴(kuò)展算法允許學(xué)習(xí)具有實(shí)數(shù)值輸出的函數(shù)，比如C4.5.可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤：決策樹學(xué)習(xí)對(duì)錯(cuò)誤有很好的魯棒性，無(wú)論是訓(xùn)練樣例所屬的分類錯(cuò)誤還是描述這些樣例的屬性值錯(cuò)誤。單個(gè)樣本存在錯(cuò)誤，對(duì)整個(gè)決策樹的構(gòu)造影響并不明顯。訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例:決策樹學(xué)習(xí)甚至可以在有未知屬性值的訓(xùn)練樣例中使用（例如，僅有一部分訓(xùn)練樣