機(jī)器學(xué)習(xí)非參數(shù)方法課件

非參數(shù)方法非參數(shù)方法1單擊此處添加標(biāo)題

前面的章節(jié)中，我們介紹了參數(shù)和半?yún)?shù)方法，這兩種方法在實(shí)際訓(xùn)練前都需要對(duì)數(shù)據(jù)遵從的模型進(jìn)行一個(gè)假定，這個(gè)假定可以是一個(gè)已知的概率分布或混合分布。參數(shù)方法的優(yōu)點(diǎn)是把估計(jì)概率密度、判別式或回歸函數(shù)問題歸結(jié)為估計(jì)少量參數(shù)值，缺點(diǎn)則是模型假定并非總成立，當(dāng)不成立時(shí)就會(huì)出現(xiàn)很大的誤差。這時(shí)我們就需要使用非參數(shù)方法，其中我們只需要假定一個(gè)事實(shí)：即相似的輸入具有相似的輸出。因?yàn)槲覀円话愣颊J(rèn)為世界的變化時(shí)平穩(wěn)、量變到質(zhì)變的，因此無論是密度、判別式還是回歸函數(shù)都應(yīng)當(dāng)緩慢地變化。在這樣的非參數(shù)估計(jì)（nonparamitricestimation）中，局部實(shí)例對(duì)于密度的影響就顯得頗為重要，而較遠(yuǎn)的實(shí)例影響則較小。本節(jié)要點(diǎn)如下：

k-近鄰估計(jì) Pazen窗單擊此處添加標(biāo)題前面的章節(jié)中，我們介紹了參數(shù)2K近鄰K近鄰3最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心作為類別代表點(diǎn)，考查新樣本到各代表點(diǎn)的距離并將它分到最近的代表點(diǎn)所代表的類。極端情況，將所有樣本都作為代表點(diǎn)－－－－近鄰法最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心作為4問題描述:

特征向量類別X=(0.1,0.1)?特征向量類別(0.1,0.2)W1(0.2,0.1)W1(0.4,0.5)W2(0.5,0.4)W2問題描述:特征向量類別特5最小距離分類器：將各類訓(xùn)練樣本劃分成若干子類，并在每個(gè)子類中確定代表點(diǎn)，一般用子類的質(zhì)心或鄰近質(zhì)心的某一樣本為代表點(diǎn)。測試樣本的類別則以其與這些代表點(diǎn)距離最近作決策。該法的缺點(diǎn)是所選擇的代表點(diǎn)并不一定能很好地代表各類，其后果將使錯(cuò)誤率增加。最近鄰法的基本思想：以全部訓(xùn)練樣本作為“代表點(diǎn)”，計(jì)算測試樣本與這些“代表點(diǎn)”，即所有樣本的距離，并以最近鄰者的類別作為決策。近鄰法是由Cover和Hart于1968年提出的，隨后得到理論上深入的分析與研究，是非參數(shù)法中最重要的方法之一。最小距離分類器：將各類訓(xùn)練樣本劃分成若干子類，并在每個(gè)子類中6機(jī)器學(xué)習(xí)非參數(shù)方法課件7機(jī)器學(xué)習(xí)非參數(shù)方法課件8在二維情況下，最近鄰規(guī)則算法使得二維空間被分割成了許多Voronoi網(wǎng)格，每一個(gè)網(wǎng)格代表的類別就是它所包含的訓(xùn)練樣本點(diǎn)所屬的類別。在二維情況下，最近鄰規(guī)則算法使得二維空間被分割成了許多Vor9

最近鄰法的錯(cuò)誤率是比較難計(jì)算的，這是因?yàn)橛?xùn)練樣本集的數(shù)量總是有限的，有時(shí)多一個(gè)少一個(gè)訓(xùn)練樣本對(duì)測試樣本分類的結(jié)果影響很大。紅點(diǎn)表示A類訓(xùn)練樣本，藍(lán)點(diǎn)表示B類訓(xùn)練樣本，而綠點(diǎn)O表示待測樣本。假設(shè)以歐氏距離來衡量，O的最近鄰是A3，其次是B1，因此O應(yīng)該屬于A類；但若A3被拿開，O就會(huì)被判為B類。最近鄰法的錯(cuò)誤率是比較難計(jì)算的，這是因?yàn)橛?xùn)練樣本集的數(shù)量總10這說明計(jì)算最近鄰法的錯(cuò)誤率會(huì)有偶然性，也就是指與具體的訓(xùn)練樣本集有關(guān)。同時(shí)還可看到，計(jì)算錯(cuò)誤率的偶然性會(huì)因訓(xùn)練樣本數(shù)量的增大而減小。因此我們就利用訓(xùn)練樣本數(shù)量增至極大，來對(duì)其性能進(jìn)行評(píng)價(jià)。這要使用漸近概念，以下都是在漸近概念下來分析錯(cuò)誤率的。

機(jī)器學(xué)習(xí)非參數(shù)方法課件11當(dāng)最近鄰法所使用的訓(xùn)練樣本數(shù)量N不是很大時(shí)，其錯(cuò)誤率是帶有偶然性的。

下圖所示為一個(gè)在一維特征空間的兩類別情況：

X表示一待測試樣本，而X'是所用訓(xùn)練樣本集中X的最鄰近者，則錯(cuò)誤是由X與X'分屬不同的類別所引起的。當(dāng)最近鄰法所使用的訓(xùn)練樣本數(shù)量N不是很大時(shí)，其錯(cuò)誤率是帶有偶12由于X‘與所用訓(xùn)練樣本集有關(guān)，因此錯(cuò)誤率有較大偶然性。但是如果所用訓(xùn)練樣本集的樣本數(shù)量N極大，即N→∞時(shí)，可以想像X‘將趨向于X，或者說處于以X為中心的極小鄰域內(nèi)，此時(shí)分析錯(cuò)誤率問題就簡化為在X樣本條件下X與一個(gè)X(X’的極限條件)分屬不同類別的問題。如果樣本X的兩類別后驗(yàn)概率分別為P(ω1|X)與P(ω2|X)，那么對(duì)X值，在N→∞條件下，發(fā)生錯(cuò)誤決策的概率為：由于X‘與所用訓(xùn)練樣本集有關(guān)，因此錯(cuò)誤率有較大偶然性。13而在這條件下的平均錯(cuò)誤率

P稱為漸近平均錯(cuò)誤率，是PN(e)在N→∞的極限。為了與基于最小錯(cuò)誤率的貝葉斯決策方法對(duì)比，下面寫出貝葉斯錯(cuò)誤率的計(jì)算式：

其中而在這條件下的平均錯(cuò)誤率14

若是兩類問題，則

貝葉斯錯(cuò)誤率：最近鄰法錯(cuò)誤率：可見在一般情況下△P是大于零的值，只要P(ω1|X)＞P(ω2|X)＞0。若是兩類問題，則15有以下兩種例外情況△P＝0：P(ω1|X)＝1P(ω1|X)＝P(ω2|X)＝1/2。有以下兩種例外情況△P＝0：16請想一下，什么情況下P(ω1|X)＝1或P(ω2|X)=1?P(ω1|X)=P(ω2|X)會(huì)出現(xiàn)什么什么情況？

一般來說，在某一類樣本分布密集區(qū)，某一類的后驗(yàn)概率接近或等于1。此時(shí)，基于最小錯(cuò)誤率貝葉斯決策基本沒錯(cuò)，而近鄰法出錯(cuò)可能也很小。而后驗(yàn)概率近似相等一般出現(xiàn)在兩類分布的交界處，此時(shí)分類沒有依據(jù)，因此基于最小錯(cuò)誤率的貝葉斯決策也無能為力了，近鄰法也就與貝葉斯決策平起平坐了。從以上討論可以看出，當(dāng)N→∞時(shí)，最近鄰法的漸近平均錯(cuò)誤率的下界是貝葉斯錯(cuò)誤率，這發(fā)生在樣本對(duì)某類別后驗(yàn)概率處處為1的情況或各類后驗(yàn)概率相等的情況。

請想一下，什么情況下P(ω1|X)＝1或P(ω2|X)=1?17機(jī)器學(xué)習(xí)非參數(shù)方法課件18最近鄰法的錯(cuò)誤率高于貝葉斯錯(cuò)誤率，可以證明以下關(guān)系式成立：由于一般情況下P*很小，因此又可粗略表示成：可粗略說最近鄰法的漸近平均錯(cuò)誤率在貝葉斯錯(cuò)誤率的兩倍之內(nèi)。

最近鄰法的錯(cuò)誤率高于貝葉斯錯(cuò)誤率，可以證明以下關(guān)系式成立：由19小結(jié)

模式識(shí)別（機(jī)器自動(dòng)分類）的基本方法有兩大類：一類是將特征空間劃分成決策域，這就要確定判別函數(shù)或確定分界面方程。另一種方法則稱為模板匹配，即將待分類樣本與標(biāo)準(zhǔn)模板進(jìn)行比較，看跟哪個(gè)模板匹配度更好些，從而確定待測試樣本的分類。前面討論的方法可以說都是將特征空間劃分為決策域，并用判別函數(shù)或決策面方程表示決策域的方法。近鄰法則在原理上屬于模板匹配。它將訓(xùn)練樣本集中的每個(gè)樣本都作為模板，用測試樣本與每個(gè)模板做比較，看與哪個(gè)模板最相似(即為近鄰)，就按最近似的模板的類別作為自己的類別。小結(jié)模式識(shí)別（機(jī)器自動(dòng)分類）的基本方法有兩大類：前面討論的206k-近鄰法:

最近鄰法的擴(kuò)展，其基本規(guī)則是，在所有N個(gè)樣本中找到與測試樣本的k個(gè)最近鄰者，其中各類別所占個(gè)數(shù)表示成ki,i＝1，…，c。定義判別函數(shù)為：

gi(x)=ki,i=1,2,…,c。

決策規(guī)則為：

k-近鄰一般采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策。6k-近鄰法:最近鄰法的擴(kuò)展，其基本規(guī)則是，在所有N個(gè)樣本21

從樣本點(diǎn)x開始生長，不斷擴(kuò)大區(qū)域，直到包含進(jìn)k個(gè)訓(xùn)練樣本點(diǎn)為止，并且把測試樣本點(diǎn)x的類別歸為這最近的k個(gè)訓(xùn)練樣本點(diǎn)中出現(xiàn)頻率最大的類別。從樣本點(diǎn)x開始生長，不斷擴(kuò)大區(qū)域，直到包含進(jìn)k個(gè)訓(xùn)練22對(duì)于兩類問題，有以下兩種例外情況△P＝0：PN(e|x,x’)＝P(ω1|x)P(ω2|x’)+P(ω2|x)P(ω1|x’)當(dāng)N->∞時(shí)，P(ωi|x’)近似等于P(ωi|x)PN->∞(e|x,x’)＝P(ω1|x)P(ω2|x)+P(ω2|x)P(ω1|x)對(duì)于K近鄰法

對(duì)于兩類問題，23對(duì)所有的x，有：

PN->∞(e|x)≤Ck[P*(e|x)]根據(jù)Jensen不等式,P=E[PNk(e|x)≤E{Ck[P*(e|x)]}≤CkE{[P*(e|x)]}=Ck(P*)不等式關(guān)系P*≤P≤Ck(P*)≤Ck-1(P*)≤…≤C1(P*)≤2P*(1-P*)

對(duì)所有的x，有：24最近鄰法和k-近鄰法的錯(cuò)誤率上下界都是在一倍到兩倍貝葉斯決策方法的錯(cuò)誤率范圍內(nèi)。在k→∞的條件下，k-近鄰法的錯(cuò)誤率要低于最近鄰法。在k→∞的條件下，k-近鄰法的錯(cuò)誤率等于貝葉斯誤差率。最近鄰法和k-近鄰法的錯(cuò)誤率上下界都是在一倍到兩倍貝葉斯決策25§6.3改進(jìn)的近鄰法

盡管近鄰法有其優(yōu)良品質(zhì)，但是它的一個(gè)嚴(yán)重弱點(diǎn)與問題是需要存儲(chǔ)全部訓(xùn)練樣本，以及繁重的距離計(jì)算量。

但以簡單的方式降低樣本數(shù)量，只能使其性能降低，這也是不希望的。為此要研究既能減少近鄰法計(jì)算量與存儲(chǔ)量，同時(shí)又不明顯降低其性能的一些改進(jìn)算法。改進(jìn)的方法大致分為兩種原理。一種是對(duì)樣本集進(jìn)行組織與整理，分群分層，盡可能將計(jì)算壓縮到在接近測試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個(gè)樣本進(jìn)行距離計(jì)算。

另一種原理則是在原有樣本集中挑選出對(duì)分類計(jì)算有效的樣本，使樣本總數(shù)合理地減少，以同時(shí)達(dá)到既減少計(jì)算量，又減少存儲(chǔ)量的雙重效果?！?.3改進(jìn)的近鄰法盡管近鄰法有其優(yōu)良品質(zhì)，但是它的一個(gè)26快速搜索近鄰法

這種方法著眼于只解決減少計(jì)算量，但沒有達(dá)到減少存儲(chǔ)量的要求。

基本思想：將樣本集按鄰近關(guān)系分解成組，給出每組的質(zhì)心所在，以及組內(nèi)樣本至該質(zhì)心的最大距離。這些組又可形成層次結(jié)構(gòu)，即組又分子組。因而待識(shí)別樣本可將搜索近鄰的范圍從某一大組，逐漸深入到其中的子組，直至樹的葉結(jié)點(diǎn)所代表的組，確定其相鄰關(guān)系?？焖偎阉鹘彿ㄟ@種方法著眼于只解決減少計(jì)算量，但沒有達(dá)到減27（1）樣本集的分級(jí)分解首先將整個(gè)樣本分成l個(gè)子集，每個(gè)子集又分為它的l個(gè)子集，如此進(jìn)行若干次就能建立起一個(gè)樣本集的樹形結(jié)構(gòu)。分成子集的原則是該子集內(nèi)的樣本盡可能聚成堆，這可用聚類方法實(shí)現(xiàn)。

結(jié)點(diǎn)參數(shù)：樹形結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)表示一樣本子集，描述該子集的參數(shù)是：

（1）樣本集的分級(jí)分解28用樹結(jié)構(gòu)表示樣本分級(jí):p:樹中的一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)一個(gè)樣本子集KpNp:Kp中的樣本數(shù)Mp:Kp中的樣本均值rp:從Kp中任一樣本到Mp的最大距離用樹結(jié)構(gòu)表示樣本分級(jí):29（2）快速搜索算法

要實(shí)現(xiàn)快速搜索近鄰，需要有方法快速判斷某個(gè)樣本子集是否是該待識(shí)樣本的可能近鄰樣本集，從而可將無關(guān)的樣本子集盡快排除。另一方面在某樣本子集內(nèi)尋找哪個(gè)樣本是近鄰時(shí)，需快速排除不可能為近鄰的樣本。

這兩個(gè)快速判別算法可用以下兩個(gè)規(guī)則表示。（2）快速搜索算法30

規(guī)則1：如果存在則不可能是X的近鄰。其中B是待識(shí)別樣本在搜索近鄰過程中的當(dāng)前近鄰距離，B在搜索過程中不斷改變與縮小。算法開始可將B設(shè)為無窮大。表示待識(shí)樣本X到結(jié)點(diǎn)的均值點(diǎn)距離。

機(jī)器學(xué)習(xí)非參數(shù)方法課件31

規(guī)則2：如果其中Xi∈，則Xi不可能是X的近鄰。由此可見，只要將每個(gè)樣本子集中的每個(gè)樣本Xi到其均值Mp的距離D(Xi,Mp)存入存儲(chǔ)器中，就可利用上式將許多不可能成為測試樣本近鄰的訓(xùn)練樣本排除。

機(jī)器學(xué)習(xí)非參數(shù)方法課件32（3）搜索算法

搜索算法的大體過程是這樣的：當(dāng)搜索樹形樣本集結(jié)構(gòu)由高層次向低層次深入時(shí)，對(duì)同一層次的所有結(jié)點(diǎn)，可以利用規(guī)則1排除掉一些不可能包含待識(shí)別樣本的近鄰的結(jié)點(diǎn)(樣本子集)。但是這往往不能做到只留下唯一的待搜索結(jié)點(diǎn)，因此必須選擇其中某一結(jié)點(diǎn)先深入搜索，以類似于深度優(yōu)先的方法確定搜索路徑直至葉結(jié)點(diǎn)。然而在該葉結(jié)點(diǎn)中找到的近鄰并不能保證確實(shí)是全樣本集中的最近鄰者，所找到的該近鄰樣本需要在那些有可能包含最近鄰的樣本子集中核對(duì)與修正，直至找到真正的最近鄰樣本為止。（3）搜索算法33置B=∞，L=0，p=0將當(dāng)前結(jié)點(diǎn)的所有直接后繼結(jié)點(diǎn)放入一個(gè)目錄表中，并對(duì)這些結(jié)點(diǎn)計(jì)算D(x,Mp)根據(jù)規(guī)則1從目錄表中去掉step2中的某些結(jié)點(diǎn)如果目錄表已無結(jié)點(diǎn)則置L=L-1，如果L=0則停止，否則轉(zhuǎn)Step3。如果目錄表有一個(gè)以上的結(jié)點(diǎn)，則轉(zhuǎn)step5在目錄表中選出最近結(jié)點(diǎn)p’為當(dāng)前執(zhí)行結(jié)點(diǎn)。如果當(dāng)前的水平L是最終水平，則轉(zhuǎn)Step6，否則置L=L+1，轉(zhuǎn)Step2對(duì)當(dāng)前執(zhí)行結(jié)點(diǎn)p’中的每個(gè)xi，根據(jù)規(guī)則2決定是否計(jì)算D(x,xi)。若D(x,xi)<B，則置NN=i和B=D(x,xi)，處理完當(dāng)前執(zhí)行結(jié)點(diǎn)中的每個(gè)xi后轉(zhuǎn)Step3當(dāng)算法結(jié)束時(shí)，輸出x的最近鄰xNN和x與xNN的距離B置B=∞，L=0，p=034剪輯近鄰法目的：去掉靠近兩類中心的樣本？基本思想：當(dāng)不同類別的樣本在分布上有交迭部分的，分類的錯(cuò)誤率主要來自處于交迭區(qū)中的樣本。當(dāng)我們得到一個(gè)作為識(shí)別用的參考樣本集時(shí)，由于不同類別交迭區(qū)域中不同類別的樣本彼此穿插，導(dǎo)致用近鄰法分類出錯(cuò)。因此如果能將不同類別交界處的樣本以適當(dāng)方式篩選，可以實(shí)現(xiàn)既減少樣本數(shù)又提高正確識(shí)別率的雙重目的。為此可以利用現(xiàn)有樣本集對(duì)其自身進(jìn)行剪輯。剪輯近鄰法目的：去掉靠近兩類中心的樣本？35剪輯的過程是：將樣本集KN分成兩個(gè)互相獨(dú)立的子集：考試（test）集KT和參考（reference）集KR。首先對(duì)KT中每一個(gè)Xi在參考集KR中找到其最近鄰的樣本Yi(Xi)

。如果Yi與Xi不屬于同一類別，則將Xi從考試集KT中刪除，最后得到一個(gè)剪輯的樣本集KTE（剪輯樣本集），以取代原樣本集，對(duì)待識(shí)別樣本進(jìn)行分類。剪輯的結(jié)果是去掉兩類邊界附近的樣本。剪輯的過程是：將樣本集KN分成兩個(gè)互相獨(dú)立的子集：考試（te36壓縮近鄰法：利用現(xiàn)有樣本集，逐漸生成一個(gè)新的樣本集，使該樣本集在保留最少量樣本的條件下，仍能對(duì)原有樣本的全部用最近鄰法正確分類，那末該樣本集也就能對(duì)待識(shí)別樣本進(jìn)行分類，并保持正常識(shí)別率。壓縮近鄰法：利用現(xiàn)有樣本集，逐漸生成一個(gè)新的樣本集，使該樣本37定義兩個(gè)存儲(chǔ)器，一個(gè)用來存放即將生成的樣本集，稱為Store；另一存儲(chǔ)器則存放原樣本集，稱為Grabbag。其算法是：初始化。Store是空集，原樣本集存入Grabbag；從Grabbag中任意選擇一樣本放入Store中作為新樣本集的第一個(gè)樣本。樣本集生成。在Grabbag中取出第i個(gè)樣本用Store中的當(dāng)前樣本集按最近鄰法分類。若分類錯(cuò)誤，則將該樣本從Grabbag轉(zhuǎn)入Store中，若分類正確，則將該樣本放回Grabbag中。結(jié)束過程。若Grabbag中所有樣本在執(zhí)行第二步時(shí)沒有發(fā)生轉(zhuǎn)入Store的現(xiàn)象，或Grabbag已成空集，則算法終止，否則轉(zhuǎn)入第二步。定義兩個(gè)存儲(chǔ)器，一個(gè)用來存放即將生成的樣本集，稱為Store38最佳距離度量近鄰法定義新的距離函數(shù)

其中xl為x的局部鄰域中的樣本,則必有

按照上面定義的新距離，在x的局部鄰域中選擇x的最近鄰x’,則可使有限樣本與無限樣本的錯(cuò)誤率之差在均方意義下達(dá)到最小。

需要說明：上述距離度量使通過對(duì)P(wi|x)在x的局部鄰域區(qū)域中做線性近似得到的，因此，它只適合于XN中與x較為接近的那些樣本。最佳距離度量近鄰法定義新的距離函數(shù)其中xl為x的局部鄰域39根據(jù)

尋找x最近鄰的程序步驟

（1）計(jì)算||x-x1||,…,||x-xN||(2)找出與x距離是最短的NA個(gè)近鄰xl，l=1,2,…,lNa

（3）利用xl計(jì)算M1-M0(4)計(jì)算|(M1-M0)T(x-xl1)|,…,|(M1-M0)T(x-xlNA)選出其中最小者，若為xlk,則xlk為x的按照距離度量的最近鄰，即xlk

＝x’

根據(jù)40Pazen窗Pazen窗411、Parzen窗方法綜述、發(fā)展歷史及現(xiàn)狀模式識(shí)別領(lǐng)域的非參數(shù)估計(jì)方法大致可以分為兩類。第一種類型是先估計(jì)出概率密度函數(shù)的具體形式，然后再利用這個(gè)估計(jì)出來的概率密度函數(shù)對(duì)樣本進(jìn)行分類。第二種類型是，不估計(jì)具體的概率密度函數(shù)，而直接根據(jù)樣本進(jìn)行分類。Parzen窗方法就是屬于第一種類型的非參數(shù)估計(jì)方法，概率神經(jīng)網(wǎng)絡(luò)（PNN）是它的一種實(shí)現(xiàn)方式。Parzen窗方法的基本思想是利用一定范圍內(nèi)的各點(diǎn)密度的平均值對(duì)總體密度函數(shù)進(jìn)行估計(jì)。

1、Parzen窗方法綜述、發(fā)展歷史及現(xiàn)狀42Parzen窗（Parzenwindow）又稱為核密度估計(jì)（kerneldensityestimation），是概率論中用來估計(jì)未知概率密度函數(shù)的非參數(shù)方法之一。該方法由EmanuelParzen于1962年在TheAnnalsofMathematicalStatistics雜志上發(fā)表的論文“OnEstimationofaProbabilityDensityFunctionandMode”中首次提出。Nadaraya和Watson最早把這一方法用于回歸法中。Specht把這一方法用于解決模式分類的問題，并且在1990年發(fā)表的論文“Probabilisticneuralnetworks”中提出了PNN網(wǎng)絡(luò)的硬件結(jié)構(gòu)。Ruppert和Cline基于數(shù)據(jù)集密度函數(shù)聚類算法提出了修訂的核密度估計(jì)方法，對(duì)Parzen窗做了一些改進(jìn)。Parzen窗方法雖然是在上個(gè)世紀(jì)60年代提出來的，已經(jīng)過去了45年的時(shí)間，看上去是一種很“古老”的技術(shù)，但是現(xiàn)在依然有很多基于Parzen窗方法的論文發(fā)表。這說明Parzen窗方法的確有很強(qiáng)的生命力和實(shí)用價(jià)值，雖然它也存在很多缺點(diǎn)。Parzen窗（Parzenwindow432、Parzen窗方法和概率神經(jīng)網(wǎng)絡(luò)

Parzen窗方法就是基于當(dāng)樣本個(gè)數(shù)n非常大的時(shí)候，有公式成立這樣的一個(gè)事實(shí)而提出的。通過計(jì)算在一個(gè)區(qū)域R內(nèi)的頻數(shù)k/n，用這個(gè)頻數(shù)來估計(jì)這一點(diǎn)的頻率，從而得到這一點(diǎn)的概率。當(dāng)n趨于無窮大的時(shí)候，p(x)等于該點(diǎn)的實(shí)際概率。這種方法就是模式識(shí)別領(lǐng)域中的非參數(shù)估計(jì)方法。Parzen窗方法就是通過構(gòu)造一系列的區(qū)域：，在這些區(qū)域內(nèi)計(jì)算k/n。記Vn為區(qū)域Rn的體積，kn為落在區(qū)域Rn中的樣本個(gè)數(shù)，表示對(duì)的第n次估計(jì)，于是有：為了保證能夠收斂到，必須滿足以下3個(gè)條件：2、Parzen窗方法和概率神經(jīng)網(wǎng)絡(luò)Parze44

Parzen窗方法的實(shí)質(zhì)就是通過對(duì)上面的區(qū)域Rn，每次按照來構(gòu)造區(qū)域序列，使區(qū)域逐漸收縮到一個(gè)給定的初始區(qū)間。它不斷收縮區(qū)域，按照公式把區(qū)域不斷縮小，而不關(guān)心該區(qū)域?qū)嶋H上包含多少個(gè)樣本點(diǎn)。另外一種與它相對(duì)應(yīng)的非參數(shù)估計(jì)方法是Kn-近鄰法。假設(shè)區(qū)間Rn是一個(gè)d維的超立方體，hn表示超立方體的一條邊的長度，那么該超立方體的體積就是。通過定義如下的窗函數(shù)，我們能夠解析地得到落在窗中的樣本個(gè)數(shù)kn的表達(dá)式：Parzen窗方法的實(shí)質(zhì)就是通過對(duì)上面的區(qū)域R45機(jī)器學(xué)習(xí)非參數(shù)方法課件46

該方程表明一種更加一般的估計(jì)概率密度函數(shù)的方法——不必規(guī)定區(qū)間必須是超立方體，可以是某種更加一般化的形式。這個(gè)公式表示我們對(duì)p(x)的估計(jì)是對(duì)一系列關(guān)于x和xi的函數(shù)求平均。這個(gè)就是Parzen窗方法估計(jì)得到的概率密度函數(shù)。關(guān)于是否合理的問題，也就是判斷它是否保證函數(shù)值非負(fù)，而且積分的結(jié)果為1。這一點(diǎn)可以通過增加條件來保證：

增加這些條件就可以保證是一個(gè)合理的概率密度函數(shù)，函數(shù)值是非負(fù)的，積分的結(jié)果為1。該方程表明一種更加一般的估計(jì)概率密度函數(shù)的方法47

Parzen窗方法可以使用神經(jīng)網(wǎng)絡(luò)的方法來實(shí)現(xiàn)，也就是通常所說的概率神經(jīng)網(wǎng)絡(luò)（Probabilisticneuralnetwork,PNN）?，F(xiàn)在假設(shè)有n個(gè)d維的樣本，它們都是從c個(gè)類別中選取的。在這種情況下，輸入層由d個(gè)輸入單元組成，每一個(gè)輸入單元都與模式層中的n個(gè)模式單元相連。而每一個(gè)模式單元只與類別層中的c個(gè)類別單元中的其中之一相連。Parzen窗方法可以使用神經(jīng)網(wǎng)絡(luò)的方法來實(shí)現(xiàn)48

從輸入層到模式層的連線表示可修改的權(quán)系數(shù)，這些權(quán)系數(shù)可以通過訓(xùn)練得到。每一個(gè)類別單元都計(jì)算與之相連的各模式單元的輸出結(jié)果的和。每一個(gè)模式層單元能夠?qū)λ臋?quán)重向量和歸一化的樣本向量x作內(nèi)積，得到Z=WtX，然后映射為。每一個(gè)類別單元把與它相連的模式層單元的輸出結(jié)果相加。這樣的結(jié)果就保證了類別單元處得到的就是使用協(xié)方差為的圓周對(duì)稱高斯窗函數(shù)的Parzen窗的估計(jì)結(jié)果（I表示d×d的單位矩陣）。從輸入層到模式層的連線表示可修改的權(quán)系數(shù)，這些49

PNN網(wǎng)絡(luò)是用下面的方式訓(xùn)練的。首先，把訓(xùn)練樣本中的每一個(gè)樣本x都?xì)w一化為單位長度，即。第一個(gè)經(jīng)過歸一化的樣本被置于輸入層單元上。同時(shí)，連接輸入單元和第一個(gè)模式層單元的那些連接被初始化為W1=X1。然后，從模式層的第一個(gè)單元到類別層中代表x1所屬類別的那個(gè)單元之間就建立了一個(gè)連接。同樣的過程對(duì)剩下的各個(gè)模式單元都重復(fù)進(jìn)行，即Wk=Xk，其中k=1,2,…,n。這樣就得到了一個(gè)網(wǎng)絡(luò)：輸入層單元與模式層單元之間是完全連通的，而模式層單元到類別單元之間是稀疏連接的。如果把第j個(gè)樣本的第k個(gè)分量記為Xjk，把這個(gè)分量到第j個(gè)模式層單元的連接權(quán)重系數(shù)記為wjk，其中j=1,2,…,n,k=1,2,…,d。得到算法描述如下：PNN網(wǎng)絡(luò)是用下面的方式訓(xùn)練的。首先，把訓(xùn)練樣50機(jī)器學(xué)習(xí)非參數(shù)方法課件51

然后，經(jīng)過訓(xùn)練完成的網(wǎng)絡(luò)就可以用這樣的方式實(shí)現(xiàn)分類：首先把一個(gè)歸一化了的測試樣本x提供給輸入節(jié)點(diǎn)，每一個(gè)模式層單元都計(jì)算內(nèi)積，得到“凈激活”（netactivation）：并產(chǎn)生netk的一個(gè)非線性函數(shù)，其中,是由用戶設(shè)置的一個(gè)參數(shù)，表示有效的高斯窗的寬度。每一個(gè)類別層單元?jiǎng)t把與它相連接的模式層單元的結(jié)果進(jìn)行相加。為了實(shí)現(xiàn)Parzen窗算法，這里的激活函數(shù)必須是一個(gè)指數(shù)函數(shù)。對(duì)于一個(gè)中心在某一個(gè)訓(xùn)練樣本W(wǎng)k處的未經(jīng)過歸一化的高斯窗函數(shù)。從期望得到的高斯窗函數(shù)倒推出模式層應(yīng)采用的非線性活化函數(shù)的形式，即如果令有效寬度hn為常數(shù)，則窗函數(shù)為然后，經(jīng)過訓(xùn)練完成的網(wǎng)絡(luò)就可以用這樣的方式實(shí)現(xiàn)52

其中使用了歸一化條件：這樣一個(gè)模式層單元向與它相連接的那個(gè)類別層單元貢獻(xiàn)了一個(gè)信號(hào)，這個(gè)信號(hào)的強(qiáng)度等于以當(dāng)前訓(xùn)練樣本為中心的高斯函數(shù)產(chǎn)生這個(gè)測試樣本點(diǎn)的概率。對(duì)這些局部估計(jì)值求和就得到判別函數(shù)gi(X)——也就是概率密度函數(shù)的Parzen窗估計(jì)結(jié)果。通過

運(yùn)算得到測試點(diǎn)的期望的類別：其中使用了歸一化條件53機(jī)器學(xué)習(xí)非參數(shù)方法課件543、Parzen窗方法的優(yōu)點(diǎn)和缺點(diǎn)

Parzen窗方法的好處是不需事先知道概率密度函數(shù)的參數(shù)形式，比較通用，可以應(yīng)對(duì)不同的概率密度分布形式。在處理有監(jiān)督學(xué)習(xí)過程的時(shí)候，現(xiàn)實(shí)世界的情況往往是我們不知道概率密度函數(shù)形式。就算能夠給出概率密度函數(shù)的形式，這些經(jīng)典的函數(shù)也很少與實(shí)際情況符合。所有經(jīng)典的概率密度函數(shù)的形式都是單模的（只有單個(gè)局部極大值），而實(shí)際情況往往是多模的。非參數(shù)方法正好能夠解決這個(gè)問題，所以從這個(gè)意義上來講，Parzen窗方法能夠更好地對(duì)應(yīng)現(xiàn)實(shí)世界的概率密度函數(shù)，而不必實(shí)現(xiàn)假設(shè)概率密度函數(shù)的形式是已知的。Parzen窗方法能處理任意的概率分布，不必假設(shè)概率密度函數(shù)的形式已知，這是非參數(shù)化方法的基本優(yōu)點(diǎn)。3、Parzen窗方法的優(yōu)點(diǎn)和缺點(diǎn)Parze55

Parzen窗方法的一個(gè)缺點(diǎn)是它需要大量的樣本。在樣本有限的情況下，很難預(yù)測它的收斂性效果如何。為了得到較精確的結(jié)果，實(shí)際需要的訓(xùn)練樣本的個(gè)數(shù)是非常驚人的。這時(shí)要求的訓(xùn)練樣本的個(gè)數(shù)比在知道分布的參數(shù)形式下進(jìn)行估計(jì)所需要的訓(xùn)練樣本的個(gè)數(shù)要多得多。而且，直到今天人們還沒有找到能夠有效的降低訓(xùn)練樣本個(gè)數(shù)的方法。這也導(dǎo)致了Parzen窗方法對(duì)時(shí)間和存儲(chǔ)空間的消耗特別大。更糟糕的是，它對(duì)訓(xùn)練樣本個(gè)數(shù)的需求，相對(duì)特征空間的維數(shù)呈指數(shù)增長。這種現(xiàn)象被稱為“維數(shù)災(zāi)難（curseofdimensionality）”，嚴(yán)重制約了這種方法的實(shí)際應(yīng)用。Parzen窗方法的另外一個(gè)缺點(diǎn)是，它在估計(jì)邊界區(qū)域的時(shí)候會(huì)出現(xiàn)邊界效應(yīng)。Parzen窗方法的一個(gè)缺點(diǎn)是它需要大量的樣56

Parzen窗方法的一個(gè)問題是，窗寬度的選擇難以把握。下圖是一個(gè)二維Parzen窗的兩類分類器的判決邊界。其中窗寬度h不相同。左邊的圖中的窗寬度h較小，右邊的圖中的窗寬度h較大。所以左側(cè)的Parzen窗分類器的分類界面比右邊復(fù)雜。這里給出的訓(xùn)練樣本的特點(diǎn)是，上半部分適合用較小的窗寬度h，而下半部分適合用較大的窗寬度h。所以，這個(gè)例子說明沒有一個(gè)理想的固定的h值能夠適應(yīng)全部區(qū)域的情況。這算是Parzen窗方法的一個(gè)不足之處。Parzen窗方法的一個(gè)問題是，窗寬度的選擇難57機(jī)器學(xué)習(xí)非參數(shù)方法課件58

PNN是Parzen窗方法的實(shí)現(xiàn)。PNN的好處之一是學(xué)習(xí)速度很快，因?yàn)閷W(xué)習(xí)規(guī)則非常簡單（Wk=Xk），并且每一個(gè)樣本點(diǎn)只需要提供一遍。這個(gè)算法的空間復(fù)雜度也很容易計(jì)算：只要查看PNN圖中的連接個(gè)數(shù)即可。而空間復(fù)雜度是O((n+1)d)?？梢?，PNN算法的缺點(diǎn)就是在硬件實(shí)現(xiàn)的時(shí)候，對(duì)存儲(chǔ)空間的要求比較高，特別是當(dāng)n和d都比較大的時(shí)候。PNN算法的時(shí)間復(fù)雜度是O(1)，因?yàn)楣街械膬?nèi)積都可以用并行的方式來完成計(jì)算。所以，PNN算法適合于對(duì)計(jì)算速度要求高而存儲(chǔ)器資源比較容易滿足的場合。PNN算法的另外一個(gè)優(yōu)點(diǎn)是新的訓(xùn)練樣本很容易被加入以前訓(xùn)練好的分類器中，這一特性對(duì)于“在線”應(yīng)用特別有意義。PNN是Parzen窗方法的實(shí)現(xiàn)。PNN的好處594、對(duì)Parzen窗法的改進(jìn)

Parzen窗/PNN算法中的一個(gè)關(guān)鍵問題就是如何選取體積序列V1,V2,…,Vn。例如，當(dāng)我們選取那么對(duì)于有限的n，估計(jì)結(jié)果將對(duì)初始體積V1非常敏感。如果V1非常小，那么大多數(shù)的體積內(nèi)都是空的，估計(jì)得到的Pn(x)將包含很大的誤差。但是如果V1非常大的話，那么平滑效應(yīng)就會(huì)非常劇烈，以至于概率密度的空間變化被掩蓋了。而且很有可能對(duì)于某一個(gè)區(qū)域適合的體積對(duì)于另一個(gè)區(qū)域就非常不適合。所以，可以考慮更加一般化的方法，例如使用交叉驗(yàn)證方法來輔助Parzen窗方法，提高算法的性能。4、對(duì)Parzen窗法的改進(jìn)Parzen窗/PN60

簡單地說，“交叉驗(yàn)證方法”使用數(shù)據(jù)集中的一小部分來形成一個(gè)“驗(yàn)證集”，而窗的寬度就是通過使驗(yàn)證集上的誤差率最小來調(diào)節(jié)得到的。我們可以通過使用“m-重交叉驗(yàn)證”（m-foldcrossvalidation）來估計(jì)Parzen窗方法得到的分類器的推廣性能。首先講訓(xùn)練樣本集D，樣本點(diǎn)的總數(shù)為n。然后把訓(xùn)練樣本隨機(jī)地劃分為m個(gè)集合，每個(gè)集合包含n/m個(gè)樣本點(diǎn)，這m個(gè)訓(xùn)練樣本子集互不相交。用這m個(gè)訓(xùn)練樣本集去訓(xùn)練Parzen窗分類器，訓(xùn)練完成之后，再選擇一個(gè)與訓(xùn)練樣本集不同的樣本集作為“驗(yàn)證集”（validationset），在驗(yàn)證的時(shí)候可以計(jì)算出這一次的推廣誤差（generalizationerror），把這個(gè)值作為Parzen分類器推廣能力的度量。上述過程重復(fù)m次，將獲得的推廣誤差取平均值，就可以估計(jì)Parzen分類器的推廣能力，從而評(píng)價(jià)它的性能如何。簡單地說，“交叉驗(yàn)證方法”使用數(shù)據(jù)集中的一小部61

利用交叉驗(yàn)證技術(shù)，我們可以對(duì)Parzen窗技術(shù)中的高斯窗函數(shù)的寬度進(jìn)行調(diào)整。通過不斷調(diào)整窗寬度h的值，使得交叉驗(yàn)證方法得到的推廣誤差最小。從而達(dá)到優(yōu)化Parzen窗方法的目的。下面的例子中，將數(shù)據(jù)集D分為2部分，第一部分占樣本點(diǎn)總數(shù)的90%，用作訓(xùn)練集；第二部分占樣本總數(shù)的10%，用作驗(yàn)證集以測試推廣性能。對(duì)Parzen窗分類器以及大多數(shù)的問題而言，訓(xùn)練誤差會(huì)隨著訓(xùn)練的進(jìn)行而單調(diào)下降。而在驗(yàn)證集上誤差典型的情況是首先單調(diào)下降，然后上升。這是因?yàn)楹竺娉霈F(xiàn)了對(duì)訓(xùn)練集“過擬合”（overfitting）的現(xiàn)象。所以，在調(diào)整窗寬度h的時(shí)候，在驗(yàn)證集誤差達(dá)到第一個(gè)局部極小值時(shí)就停止。如圖所示：利用交叉驗(yàn)證技術(shù)，我們可以對(duì)Parzen窗技術(shù)62

前面提到了Parzen窗方法存在著“維數(shù)災(zāi)難”的問題，這嚴(yán)重限制了Parzen窗方法的實(shí)際應(yīng)用。產(chǎn)生“維數(shù)災(zāi)難”的最核心的問題是，高維函數(shù)事實(shí)上遠(yuǎn)比低維函數(shù)復(fù)雜，人們對(duì)其復(fù)雜度幾乎無法進(jìn)行有效的分析和掌握。現(xiàn)在對(duì)付“維數(shù)災(zāi)難”的惟一有效的方法就是盡可能多的在處理問題時(shí)嵌入關(guān)于模式數(shù)據(jù)本身的可靠的先驗(yàn)知識(shí)。前面提到了Parzen窗方法存在著“維數(shù)災(zāi)難”63Parzen窗方法的實(shí)質(zhì)就是通過對(duì)上面的區(qū)域Rn，每次按照來構(gòu)造區(qū)域序列，使區(qū)域逐漸收縮到一個(gè)給定的初始區(qū)間。它不斷收縮區(qū)域，按照公式把區(qū)域不斷縮小，而不關(guān)心該區(qū)域?qū)嶋H上包含多少個(gè)樣本點(diǎn)。另外一種與它相對(duì)應(yīng)的非參數(shù)估計(jì)方法是Kn-近鄰法。假設(shè)區(qū)間Rn是一個(gè)d維的超立方體，hn表示超立方體的一條邊的長度，那么該超立方體的體積就是。通過定義如下的窗函數(shù)，我們能夠解析地得到落在窗中的樣本個(gè)數(shù)kn的表達(dá)式：這樣，就表示一個(gè)中心在原點(diǎn)的單位超立方體。如果xi落在超立方體Vn中，那么，否則便為0。因此，超立方體中的樣本個(gè)數(shù)就是帶入公式，就得到該方程表明一種更加一般的估計(jì)概率密度函數(shù)的方法——不必規(guī)定區(qū)間必須是超立方體，可以是某種更加一般化的形式。這個(gè)公式表示我們對(duì)p(x)的估計(jì)是對(duì)一系列關(guān)于x和xi的函數(shù)求平均。這個(gè)就是Parzen窗方法估計(jì)得到的概率密度函數(shù)。Parzen窗方法的實(shí)質(zhì)就是通過對(duì)上面的區(qū)域Rn，每次按照64模式分類方法總結(jié)一、參數(shù)判別分類方法與非參數(shù)判別分類方法的區(qū)別

從參數(shù)判別方法看，它的前提是對(duì)特征空間中的各類樣本的分布清楚，因此一旦要測試分類樣本的特征向量值X已知，就可以確定X對(duì)各類的后驗(yàn)概率，也就可按相應(yīng)的準(zhǔn)則計(jì)算與分類。如果這種分布可以用正態(tài)分布等描述，那么決策域的判別函數(shù)與分界面方程就可用函數(shù)的形式確定下來。所以判別函數(shù)等的確定取決于樣本統(tǒng)計(jì)分布的有關(guān)知識(shí)。因此參數(shù)分類判別方法一般只能用在有統(tǒng)計(jì)知識(shí)的場合，或能利用訓(xùn)練樣本估計(jì)出參數(shù)的場合。模式分類方法總結(jié)一、參數(shù)判別分類方法與非參數(shù)判別分類方法的區(qū)65模式分類方法總結(jié)一、參數(shù)判別分類方法與非參數(shù)判別分類方法的區(qū)別非參數(shù)分類判別方法則著眼于直接利用訓(xùn)練樣本集，省去參數(shù)估計(jì)這一環(huán)節(jié)，這樣一來，從保證最小錯(cuò)誤率的原則出發(fā)計(jì)算確定判別函數(shù)的方法就不適用了。因此非參數(shù)分類判別方法只能根據(jù)一些其它準(zhǔn)則來設(shè)計(jì)分類器。分類器的效果好壞，常指分類的錯(cuò)誤率，一般在理論上很難說明，主要靠實(shí)踐來檢驗(yàn)。所選擇的判別函數(shù)型式，所使用的訓(xùn)練樣本集，以及所用的算法對(duì)結(jié)果都會(huì)有影響。模式分類方法總結(jié)一、參數(shù)判別分類方法與非參數(shù)判別分類方法的區(qū)66模式分類方法總結(jié)二、非參數(shù)分類判別方法的基本做法

使用非參數(shù)分類判別方法進(jìn)行分類器設(shè)計(jì)主要包含兩個(gè)步驟：（1）一個(gè)是確定的使用的判別函數(shù)類型或決策面方程類型，如線性分類器，分段線性分類器，非線性分類器等或近鄰法等。如果使用人工神經(jīng)元網(wǎng)絡(luò)，則怎樣的網(wǎng)絡(luò)結(jié)構(gòu)也隱含了所使用的函數(shù)形式。（2）另一個(gè)步驟是在選定的函數(shù)類型網(wǎng)絡(luò)結(jié)構(gòu)等條件下，確定相應(yīng)的參數(shù)，從而完成整個(gè)分類器設(shè)計(jì)。模式分類方法總結(jié)二、非參數(shù)分類判別方法的基本做法67模式分類方法總結(jié)三、決策面方程的顯式表示和隱式表示

對(duì)一個(gè)分類的決策域劃分一般可采用兩種形式，一種是用函數(shù)直接表示分界面方程，如線性方程式表示的邊界等。另一種則用隱含形式，例如我們用最小距離分類器就代表了這種類型，其實(shí)這兩種形式是等價(jià)的。如二維空間的最小距離分類器用最小距離表示等價(jià)于連接m1與m2線的垂直平分線。本章學(xué)習(xí)的Fisher準(zhǔn)則、支持向量機(jī)與局部訓(xùn)練法等用的是顯式表示，而錯(cuò)誤修正法和近鄰法則可以說是隱式表示。模式分類方法總結(jié)三、決策面方程的顯式表示和隱式表示68模式分類方法總結(jié)四、基于相似度的分類判別方法

判別函數(shù)的隱式表示與使用基于相似度判別的原則有關(guān)。如近鄰法是用距離遠(yuǎn)近表示相似程度，錯(cuò)誤修正法用樣本向量與增廣權(quán)向量的點(diǎn)積運(yùn)算，也可在一定程度上看作相似度。在多類問題上，往往用計(jì)算相似度較方便。模式分類方法總結(jié)四、基于相似度的分類判別方法69模式分類方法總結(jié)五、Fisher準(zhǔn)則

Fisher準(zhǔn)則是傳統(tǒng)模式識(shí)別方法中的典型方法，它強(qiáng)調(diào)將線性方程中的法向量與樣本的乘積看作樣本向量在單位法向量上的投影，如能做到不同類的樣本在法向量上的投影呈現(xiàn)類內(nèi)聚集，類向分開的效果，則對(duì)減少錯(cuò)分類有利。所得最佳法向量計(jì)算式為模式分類方法總結(jié)五、Fisher準(zhǔn)則70模式分類方法總結(jié)六、感知準(zhǔn)則函數(shù)方法

這種方法提倡用錯(cuò)分類提供的信息修正錯(cuò)誤，這種思想對(duì)機(jī)器學(xué)習(xí)的發(fā)展以及人工神經(jīng)元網(wǎng)絡(luò)的發(fā)生發(fā)展產(chǎn)生深遠(yuǎn)影響。七、近鄰法

近鄰法訓(xùn)練樣本數(shù)量較多時(shí)，從漸近錯(cuò)誤率角度看，其錯(cuò)誤率比較小，是經(jīng)常使用的模式識(shí)別分類方法，比較適合在多類別情況下使用。模式分類方法總結(jié)六、感知準(zhǔn)則函數(shù)方法71THANKYOUFORYOURWATCHTHANKYOUFORYOURWATCH72非參數(shù)方法非參數(shù)方法73單擊此處添加標(biāo)題

前面的章節(jié)中，我們介紹了參數(shù)和半?yún)?shù)方法，這兩種方法在實(shí)際訓(xùn)練前都需要對(duì)數(shù)據(jù)遵從的模型進(jìn)行一個(gè)假定，這個(gè)假定可以是一個(gè)已知的概率分布或混合分布。參數(shù)方法的優(yōu)點(diǎn)是把估計(jì)概率密度、判別式或回歸函數(shù)問題歸結(jié)為估計(jì)少量參數(shù)值，缺點(diǎn)則是模型假定并非總成立，當(dāng)不成立時(shí)就會(huì)出現(xiàn)很大的誤差。這時(shí)我們就需要使用非參數(shù)方法，其中我們只需要假定一個(gè)事實(shí)：即相似的輸入具有相似的輸出。因?yàn)槲覀円话愣颊J(rèn)為世界的變化時(shí)平穩(wěn)、量變到質(zhì)變的，因此無論是密度、判別式還是回歸函數(shù)都應(yīng)當(dāng)緩慢地變化。在這樣的非參數(shù)估計(jì)（nonparamitricestimation）中，局部實(shí)例對(duì)于密度的影響就顯得頗為重要，而較遠(yuǎn)的實(shí)例影響則較小。本節(jié)要點(diǎn)如下：

k-近鄰估計(jì) Pazen窗單擊此處添加標(biāo)題前面的章節(jié)中，我們介紹了參數(shù)74K近鄰K近鄰75最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心作為類別代表點(diǎn)，考查新樣本到各代表點(diǎn)的距離并將它分到最近的代表點(diǎn)所代表的類。極端情況，將所有樣本都作為代表點(diǎn)－－－－近鄰法最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心作為76問題描述:

特征向量類別X=(0.1,0.1)?特征向量類別(0.1,0.2)W1(0.2,0.1)W1(0.4,0.5)W2(0.5,0.4)W2問題描述:特征向量類別特77最小距離分類器：將各類訓(xùn)練樣本劃分成若干子類，并在每個(gè)子類中確定代表點(diǎn)，一般用子類的質(zhì)心或鄰近質(zhì)心的某一樣本為代表點(diǎn)。測試樣本的類別則以其與這些代表點(diǎn)距離最近作決策。該法的缺點(diǎn)是所選擇的代表點(diǎn)并不一定能很好地代表各類，其后果將使錯(cuò)誤率增加。最近鄰法的基本思想：以全部訓(xùn)練樣本作為“代表點(diǎn)”，計(jì)算測試樣本與這些“代表點(diǎn)”，即所有樣本的距離，并以最近鄰者的類別作為決策。近鄰法是由Cover和Hart于1968年提出的，隨后得到理論上深入的分析與研究，是非參數(shù)法中最重要的方法之一。最小距離分類器：將各類訓(xùn)練樣本劃分成若干子類，并在每個(gè)子類中78機(jī)器學(xué)習(xí)非參數(shù)方法課件79機(jī)器學(xué)習(xí)非參數(shù)方法課件80在二維情況下，最近鄰規(guī)則算法使得二維空間被分割成了許多Voronoi網(wǎng)格，每一個(gè)網(wǎng)格代表的類別就是它所包含的訓(xùn)練樣本點(diǎn)所屬的類別。在二維情況下，最近鄰規(guī)則算法使得二維空間被分割成了許多Vor81

最近鄰法的錯(cuò)誤率是比較難計(jì)算的，這是因?yàn)橛?xùn)練樣本集的數(shù)量總是有限的，有時(shí)多一個(gè)少一個(gè)訓(xùn)練樣本對(duì)測試樣本分類的結(jié)果影響很大。紅點(diǎn)表示A類訓(xùn)練樣本，藍(lán)點(diǎn)表示B類訓(xùn)練樣本，而綠點(diǎn)O表示待測樣本。假設(shè)以歐氏距離來衡量，O的最近鄰是A3，其次是B1，因此O應(yīng)該屬于A類；但若A3被拿開，O就會(huì)被判為B類。最近鄰法的錯(cuò)誤率是比較難計(jì)算的，這是因?yàn)橛?xùn)練樣本集的數(shù)量總82這說明計(jì)算最近鄰法的錯(cuò)誤率會(huì)有偶然性，也就是指與具體的訓(xùn)練樣本集有關(guān)。同時(shí)還可看到，計(jì)算錯(cuò)誤率的偶然性會(huì)因訓(xùn)練樣本數(shù)量的增大而減小。因此我們就利用訓(xùn)練樣本數(shù)量增至極大，來對(duì)其性能進(jìn)行評(píng)價(jià)。這要使用漸近概念，以下都是在漸近概念下來分析錯(cuò)誤率的。

機(jī)器學(xué)習(xí)非參數(shù)方法課件83當(dāng)最近鄰法所使用的訓(xùn)練樣本數(shù)量N不是很大時(shí)，其錯(cuò)誤率是帶有偶然性的。

下圖所示為一個(gè)在一維特征空間的兩類別情況：

X表示一待測試樣本，而X'是所用訓(xùn)練樣本集中X的最鄰近者，則錯(cuò)誤是由X與X'分屬不同的類別所引起的。當(dāng)最近鄰法所使用的訓(xùn)練樣本數(shù)量N不是很大時(shí)，其錯(cuò)誤率是帶有偶84由于X‘與所用訓(xùn)練樣本集有關(guān)，因此錯(cuò)誤率有較大偶然性。但是如果所用訓(xùn)練樣本集的樣本數(shù)量N極大，即N→∞時(shí)，可以想像X‘將趨向于X，或者說處于以X為中心的極小鄰域內(nèi)，此時(shí)分析錯(cuò)誤率問題就簡化為在X樣本條件下X與一個(gè)X(X’的極限條件)分屬不同類別的問題。如果樣本X的兩類別后驗(yàn)概率分別為P(ω1|X)與P(ω2|X)，那么對(duì)X值，在N→∞條件下，發(fā)生錯(cuò)誤決策的概率為：由于X‘與所用訓(xùn)練樣本集有關(guān)，因此錯(cuò)誤率有較大偶然性。85而在這條件下的平均錯(cuò)誤率

P稱為漸近平均錯(cuò)誤率，是PN(e)在N→∞的極限。為了與基于最小錯(cuò)誤率的貝葉斯決策方法對(duì)比，下面寫出貝葉斯錯(cuò)誤率的計(jì)算式：

其中而在這條件下的平均錯(cuò)誤率86

若是兩類問題，則

貝葉斯錯(cuò)誤率：最近鄰法錯(cuò)誤率：可見在一般情況下△P是大于零的值，只要P(ω1|X)＞P(ω2|X)＞0。若是兩類問題，則87有以下兩種例外情況△P＝0：P(ω1|X)＝1P(ω1|X)＝P(ω2|X)＝1/2。有以下兩種例外情況△P＝0：88請想一下，什么情況下P(ω1|X)＝1或P(ω2|X)=1?P(ω1|X)=P(ω2|X)會(huì)出現(xiàn)什么什么情況？

一般來說，在某一類樣本分布密集區(qū)，某一類的后驗(yàn)概率接近或等于1。此時(shí)，基于最小錯(cuò)誤率貝葉斯決策基本沒錯(cuò)，而近鄰法出錯(cuò)可能也很小。而后驗(yàn)概率近似相等一般出現(xiàn)在兩類分布的交界處，此時(shí)分類沒有依據(jù)，因此基于最小錯(cuò)誤率的貝葉斯決策也無能為力了，近鄰法也就與貝葉斯決策平起平坐了。從以上討論可以看出，當(dāng)N→∞時(shí)，最近鄰法的漸近平均錯(cuò)誤率的下界是貝葉斯錯(cuò)誤率，這發(fā)生在樣本對(duì)某類別后驗(yàn)概率處處為1的情況或各類后驗(yàn)概率相等的情況。

請想一下，什么情況下P(ω1|X)＝1或P(ω2|X)=1?89機(jī)器學(xué)習(xí)非參數(shù)方法課件90最近鄰法的錯(cuò)誤率高于貝葉斯錯(cuò)誤率，可以證明以下關(guān)系式成立：由于一般情況下P*很小，因此又可粗略表示成：可粗略說最近鄰法的漸近平均錯(cuò)誤率在貝葉斯錯(cuò)誤率的兩倍之內(nèi)。

最近鄰法的錯(cuò)誤率高于貝葉斯錯(cuò)誤率，可以證明以下關(guān)系式成立：由91小結(jié)

模式識(shí)別（機(jī)器自動(dòng)分類）的基本方法有兩大類：一類是將特征空間劃分成決策域，這就要確定判別函數(shù)或確定分界面方程。另一種方法則稱為模板匹配，即將待分類樣本與標(biāo)準(zhǔn)模板進(jìn)行比較，看跟哪個(gè)模板匹配度更好些，從而確定待測試樣本的分類。前面討論的方法可以說都是將特征空間劃分為決策域，并用判別函數(shù)或決策面方程表示決策域的方法。近鄰法則在原理上屬于模板匹配。它將訓(xùn)練樣本集中的每個(gè)樣本都作為模板，用測試樣本與每個(gè)模板做比較，看與哪個(gè)模板最相似(即為近鄰)，就按最近似的模板的類別作為自己的類別。小結(jié)模式識(shí)別（機(jī)器自動(dòng)分類）的基本方法有兩大類：前面討論的926k-近鄰法:

最近鄰法的擴(kuò)展，其基本規(guī)則是，在所有N個(gè)樣本中找到與測試樣本的k個(gè)最近鄰者，其中各類別所占個(gè)數(shù)表示成ki,i＝1，…，c。定義判別函數(shù)為：

gi(x)=ki,i=1,2,…,c。

決策規(guī)則為：

k-近鄰一般采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策。6k-近鄰法:最近鄰法的擴(kuò)展，其基本規(guī)則是，在所有N個(gè)樣本93

從樣本點(diǎn)x開始生長，不斷擴(kuò)大區(qū)域，直到包含進(jìn)k個(gè)訓(xùn)練樣本點(diǎn)為止，并且把測試樣本點(diǎn)x的類別歸為這最近的k個(gè)訓(xùn)練樣本點(diǎn)中出現(xiàn)頻率最大的類別。從樣本點(diǎn)x開始生長，不斷擴(kuò)大區(qū)域，直到包含進(jìn)k個(gè)訓(xùn)練94對(duì)于兩類問題，有以下兩種例外情況△P＝0：PN(e|x,x’)＝P(ω1|x)P(ω2|x’)+P(ω2|x)P(ω1|x’)當(dāng)N->∞時(shí)，P(ωi|x’)近似等于P(ωi|x)PN->∞(e|x,x’)＝P(ω1|x)P(ω2|x)+P(ω2|x)P(ω1|x)對(duì)于K近鄰法

對(duì)于兩類問題，95對(duì)所有的x，有：

PN->∞(e|x)≤Ck[P*(e|x)]根據(jù)Jensen不等式,P=E[PNk(e|x)≤E{Ck[P*(e|x)]}≤CkE{[P*(e|x)]}=Ck(P*)不等式關(guān)系P*≤P≤Ck(P*)≤Ck-1(P*)≤…≤C1(P*)≤2P*(1-P*)

對(duì)所有的x，有：96最近鄰法和k-近鄰法的錯(cuò)誤率上下界都是在一倍到兩倍貝葉斯決策方法的錯(cuò)誤率范圍內(nèi)。在k→∞的條件下，k-近鄰法的錯(cuò)誤率要低于最近鄰法。在k→∞的條件下，k-近鄰法的錯(cuò)誤率等于貝葉斯誤差率。最近鄰法和k-近鄰法的錯(cuò)誤率上下界都是在一倍到兩倍貝葉斯決策97§6.3改進(jìn)的近鄰法

盡管近鄰法有其優(yōu)良品質(zhì)，但是它的一個(gè)嚴(yán)重弱點(diǎn)與問題是需要存儲(chǔ)全部訓(xùn)練樣本，以及繁重的距離計(jì)算量。

但以簡單的方式降低樣本數(shù)量，只能使其性能降低，這也是不希望的。為此要研究既能減少近鄰法計(jì)算量與存儲(chǔ)量，同時(shí)又不明顯降低其性能的一些改進(jìn)算法。改進(jìn)的方法大致分為兩種原理。一種是對(duì)樣本集進(jìn)行組織與整理，分群分層，盡可能將計(jì)算壓縮到在接近測試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個(gè)樣本進(jìn)行距離計(jì)算。

另一種原理則是在原有樣本集中挑選出對(duì)分類計(jì)算有效的樣本，使樣本總數(shù)合理地減少，以同時(shí)達(dá)到既減少計(jì)算量，又減少存儲(chǔ)量的雙重效果。§6.3改進(jìn)的近鄰法盡管近鄰法有其優(yōu)良品質(zhì)，但是它的一個(gè)98快速搜索近鄰法

這種方法著眼于只解決減少計(jì)算量，但沒有達(dá)到減少存儲(chǔ)量的要求。

基本思想：將樣本集按鄰近關(guān)系分解成組，給出每組的質(zhì)心所在，以及組內(nèi)樣本至該質(zhì)心的最大距離。這些組又可形成層次結(jié)構(gòu)，即組又分子組。因而待識(shí)別樣本可將搜索近鄰的范圍從某一大組，逐漸深入到其中的子組，直至樹的葉結(jié)點(diǎn)所代表的組，確定其相鄰關(guān)系?？焖偎阉鹘彿ㄟ@種方法著眼于只解決減少計(jì)算量，但沒有達(dá)到減99（1）樣本集的分級(jí)分解首先將整個(gè)樣本分成l個(gè)子集，每個(gè)子集又分為它的l個(gè)子集，如此進(jìn)行若干次就能建立起一個(gè)樣本集的樹形結(jié)構(gòu)。分成子集的原則是該子集內(nèi)的樣本盡可能聚成堆，這可用聚類方法實(shí)現(xiàn)。

結(jié)點(diǎn)參數(shù)：樹形結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)表示一樣本子集，描述該子集的參數(shù)是：

（1）樣本集的分級(jí)分解100用樹結(jié)構(gòu)表示樣本分級(jí):p:樹中的一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)一個(gè)樣本子集KpNp:Kp中的樣本數(shù)Mp:Kp中的樣本均值rp:從Kp中任一樣本到Mp的最大距離用樹結(jié)構(gòu)表示樣本分級(jí):101（2）快速搜索算法

要實(shí)現(xiàn)快速搜索近鄰，需要有方法快速判斷某個(gè)樣本子集是否是該待識(shí)樣本的可能近鄰樣本集，從而可將無關(guān)的樣本子集盡快排除。另一方面在某樣本子集內(nèi)尋找哪個(gè)樣本是近鄰時(shí)，需快速排除不可能為近鄰的樣本。

這兩個(gè)快速判別算法可用以下兩個(gè)規(guī)則表示。（2）快速搜索算法102

規(guī)則1：如果存在則不可能是X的近鄰。其中B是待識(shí)別樣本在搜索近鄰過程中的當(dāng)前近鄰距離，B在搜索過程中不斷改變與縮小。算法開始可將B設(shè)為無窮大。表示待識(shí)樣本X到結(jié)點(diǎn)的均值點(diǎn)距離。

機(jī)器學(xué)習(xí)非參數(shù)方法課件103

規(guī)則2：如果其中Xi∈，則Xi不可能是X的近鄰。由此可見，只要將每個(gè)樣本子集中的每個(gè)樣本Xi到其均值Mp的距離D(Xi,Mp)存入存儲(chǔ)器中，就可利用上式將許多不可能成為測試樣本近鄰的訓(xùn)練樣本排除。

機(jī)器學(xué)習(xí)非參數(shù)方法課件104（3）搜索算法

搜索算法的大體過程是這樣的：當(dāng)搜索樹形樣本集結(jié)構(gòu)由高層次向低層次深入時(shí)，對(duì)同一層次的所有結(jié)點(diǎn)，可以利用規(guī)則1排除掉一些不可能包含待識(shí)別樣本的近鄰的結(jié)點(diǎn)(樣本子集)。但是這往往不能做到只留下唯一的待搜索結(jié)點(diǎn)，因此必須選擇其中某一結(jié)點(diǎn)先深入搜索，以類似于深度優(yōu)先的方法確定搜索路徑直至葉結(jié)點(diǎn)。然而在該葉結(jié)點(diǎn)中找到的近鄰并不能保證確實(shí)是全樣本集中的最近鄰者，所找到的該近鄰樣本需要在那些有可能包含最近鄰的樣本子集中核對(duì)與修正，直至找到真正的最近鄰樣本為止。（3）搜索算法105置B=∞，L=0，p=0將當(dāng)前結(jié)點(diǎn)的所有直接后繼結(jié)點(diǎn)放入一個(gè)目錄表中，并對(duì)這些結(jié)點(diǎn)計(jì)算D(x,Mp)根據(jù)規(guī)則1從目錄表中去掉step2中的某些結(jié)點(diǎn)如果目錄表已無結(jié)點(diǎn)則置L=L-1，如果L=0則停止，否則轉(zhuǎn)Step3。如果目錄表有一個(gè)以上的結(jié)點(diǎn)，則轉(zhuǎn)step5在目錄表中選出最近結(jié)點(diǎn)p’為當(dāng)前執(zhí)行結(jié)點(diǎn)。如果當(dāng)前的水平L是最終水平，則轉(zhuǎn)Step6，否則置L=L+1，轉(zhuǎn)Step2對(duì)當(dāng)前執(zhí)行結(jié)點(diǎn)p’中的每個(gè)xi，根據(jù)規(guī)則2決定是否計(jì)算D(x,xi)。若D(x,xi)<B，則置NN=i和B=D(x,xi)，處理完當(dāng)前執(zhí)行結(jié)點(diǎn)中的每個(gè)xi后轉(zhuǎn)Step3當(dāng)算法結(jié)束時(shí)，輸出x的最近鄰xNN和x與xNN的距離B置B=∞，L=0，p=0106剪輯近鄰法目的：去掉靠近兩類中心的樣本？基本思想：當(dāng)不同類別的樣本在分布上有交迭部分的，分類的錯(cuò)誤率主要來自處于交迭區(qū)中的樣本。當(dāng)我們得到一個(gè)作為識(shí)別用的參考樣本集時(shí)，由于不同類別交迭區(qū)域中不同類別的樣本彼此穿插，導(dǎo)致用近鄰法分類出錯(cuò)。因此如果能將不同類別交界處的樣本以適當(dāng)方式篩選，可以實(shí)現(xiàn)既減少樣本數(shù)又提高正確識(shí)別率的雙重目的。為此可以利用現(xiàn)有樣本集對(duì)其自身進(jìn)行剪輯。剪輯近鄰法目的：去掉靠近兩類中心的樣本？107剪輯的過程是：將樣本集KN分成兩個(gè)互相獨(dú)立的子集：考試（test）集KT和參考（reference）集KR。首先對(duì)KT中每一個(gè)Xi在參考集KR中找到其最近鄰的樣本Yi(Xi)

。如果Yi與Xi不屬于同一類別，則將Xi從考試集KT中刪除，最后得到一個(gè)剪輯的樣本集KTE（剪輯樣本集），以取代原樣本集，對(duì)待識(shí)別樣本進(jìn)行分類。剪輯的結(jié)果是去掉兩類邊界附近的樣本。剪輯的過程是：將樣本集KN分成兩個(gè)互相獨(dú)立的子集：考試（te108壓縮近鄰法：利用現(xiàn)有樣本集，逐漸生成一個(gè)新的樣本集，使該樣本集在保留最少量樣本的條件下，仍能對(duì)原有樣本的全部用最近鄰法正確分類，那末該樣本集也就能對(duì)待識(shí)別樣本進(jìn)行分類，并保持正常識(shí)別率。壓縮近鄰法：利用現(xiàn)有樣本集，逐漸生成一個(gè)新的樣本集，使該樣本109定義兩個(gè)存儲(chǔ)器，一個(gè)用來存放即將生成的樣本集，稱為Store；另一存儲(chǔ)器則存放原樣本集，稱為Grabbag。其算法是：初始化。Store是空集，原樣本集存入Grabbag；從Grabbag中任意選擇一樣本放入Store中作為新樣本集的第一個(gè)樣本。樣本集生成。在Grabbag中取出第i個(gè)樣本用Store中的當(dāng)前樣本集按最近鄰法分類。若分類錯(cuò)誤，則將該樣本從Grabbag轉(zhuǎn)入Store中，若分類正確，則將該樣本放回Grabbag中。結(jié)束過程。若Grabbag中所有樣本在執(zhí)行第二步時(shí)沒有發(fā)生轉(zhuǎn)入Store的現(xiàn)象，或Grabbag已成空集，則算法終止，否則轉(zhuǎn)入第二步。定義兩個(gè)存儲(chǔ)器，一個(gè)用來存放即將生成的樣本集，稱為Store110最佳距離度量近鄰法定義新的距離函數(shù)

其中xl為x的局部鄰域中的樣本,則必有

按照上面定義的新距離，在x的局部鄰域中選擇x的最近鄰x’,則可使有限樣本與無限樣本的錯(cuò)誤率之差在均方意義下達(dá)到最小。

需要說明：上述距離度量使通過對(duì)P(wi|x)在x的局部鄰域區(qū)域中做線性近似得到的，因此，它只適合于XN中與x較為接近的那些樣本。最佳距離度量近鄰法定義新的距離函數(shù)其中xl為x的局部鄰域111根據(jù)

尋找x最近鄰的程序步驟

（1）計(jì)算||x-x1||,…,||x-xN||(2)找出與x距離是最短的NA個(gè)近鄰xl，l=1,2,…,lNa

（3）利用xl計(jì)算M1-M0(4)計(jì)算|(M1-M0)T(x-xl1)|,…,|(M1-M0)T(x-xlNA)選出其中最小者，若為xlk,則xlk為x的按照距離度量的最近鄰，即xlk

＝x’

根據(jù)112Pazen窗Pazen窗1131、Parzen窗方法綜述、發(fā)展歷史及現(xiàn)狀模式識(shí)別領(lǐng)域的非參數(shù)估計(jì)方法大致可以分為兩類。第一種類型是先估計(jì)出概率密度函數(shù)的具體形式，然后再利用這個(gè)估計(jì)出來的概率密度函數(shù)對(duì)樣本進(jìn)行分類。第二種類型是，不估計(jì)具體的概率密度函數(shù)，而直接根據(jù)樣本進(jìn)行分類。Parzen窗方法就是屬于第一種類型的非參數(shù)估計(jì)方法，概率神經(jīng)網(wǎng)絡(luò)（PNN）是它的一種實(shí)現(xiàn)方式。Parzen窗方法的基本思想是利用一定范圍內(nèi)的各點(diǎn)密度的平均值對(duì)總體密度函數(shù)進(jìn)行估計(jì)。

1、Parzen窗方法綜述、發(fā)展歷史及現(xiàn)狀114Parzen窗（Parzenwindow）又稱為核密度估計(jì)（kerneldensityestimation），是概率論中用來估計(jì)未知概率密度函數(shù)的非參數(shù)方法之一。該方法由EmanuelParzen于1962年在TheAnnalsofMathematicalStatistics雜志上發(fā)表的論文“OnEstimationofaProbabilityDensityFunctionandMode”中首次提出。Nadaraya和Watson最早把這一方法用于回歸法中。Specht把這一方法用于解決模式分類的問題，并且在1990年發(fā)表的論文“Probabilisticneuralnetworks”中提出了PNN網(wǎng)絡(luò)的硬件結(jié)構(gòu)。Ruppert和Cline基于數(shù)據(jù)集密度函數(shù)聚類算法提出了修訂的核密度估計(jì)方法，對(duì)Parzen窗做了一些改進(jìn)。Parzen窗方法雖然是在上個(gè)世紀(jì)60年代提出來的，已經(jīng)過去了45年的時(shí)間，看上去是一種很“古老”的技術(shù)，但是現(xiàn)在依然有很多基于Parzen窗方法的論文發(fā)表。這說明Parzen窗方法的確有很強(qiáng)的生命力和實(shí)用價(jià)值，雖然它也存在很多缺點(diǎn)。Parzen窗（Parzenwindow1152、Parzen窗方法和概率神經(jīng)網(wǎng)絡(luò)

Parzen窗方法就是基于當(dāng)樣本個(gè)數(shù)n非常大的時(shí)候，有公式成立這樣的一個(gè)事實(shí)而提出的。通過計(jì)算在一個(gè)區(qū)域R內(nèi)的頻數(shù)k/n，用這個(gè)頻數(shù)來估計(jì)這一點(diǎn)的頻率，從而得到這一點(diǎn)的概率。當(dāng)n趨于無窮大的時(shí)候，p(x)等于該點(diǎn)的實(shí)際概率。這種方法就是模式識(shí)別領(lǐng)域中的非參數(shù)估計(jì)方法。Parzen窗方法就是通過構(gòu)造一系列的區(qū)域：，在這些區(qū)域內(nèi)計(jì)算k/n。記Vn為區(qū)域Rn的體積，kn為落在區(qū)域Rn中的樣本個(gè)數(shù)，表示對(duì)的第n次估計(jì)，于是有：為了保證能夠收斂到，必須滿足以下3個(gè)條件：2、Parzen窗方法和概率神經(jīng)網(wǎng)絡(luò)Parze116

Parzen窗方法的實(shí)質(zhì)就是通過對(duì)上面的區(qū)域Rn，每次按照來構(gòu)造區(qū)域序列，使區(qū)域逐漸收縮到一個(gè)給定的初始區(qū)間。它不斷收縮區(qū)域，按照公式把區(qū)域不斷縮小，而不關(guān)心該區(qū)域?qū)嶋H上包含多少個(gè)樣本點(diǎn)。另外一種與它相對(duì)應(yīng)的非參數(shù)估計(jì)方法是Kn-近鄰法。假設(shè)區(qū)間Rn是一個(gè)d維的超立方體，hn表示超立方體的一條邊的長度，那么該超立方體的體積就是。通過定義如下的窗函數(shù)，我們能夠解析地得到落在窗中的樣本個(gè)數(shù)kn的表達(dá)式：Parzen窗方法的實(shí)質(zhì)就是通過對(duì)上面的區(qū)域R117機(jī)器學(xué)習(xí)非參數(shù)方法課件118

該方程表明一種更加一般的估計(jì)概率密度函數(shù)的方法——不必規(guī)定區(qū)間必須是超立方體，可以是某種更加一般化的形式。這個(gè)公式表示我們對(duì)p(x)的估計(jì)是對(duì)一系列關(guān)于x和xi的函數(shù)求平均。這個(gè)就是Parzen窗方法估計(jì)得到的概率密度函數(shù)。關(guān)于是否合理的問題，也就是判斷它是否保證函數(shù)值非負(fù)，而且積分的結(jié)果為1。這一點(diǎn)可以通過增加條件來保證：

增加這些條件就可以保證是一個(gè)合理的概率密度函數(shù)，函數(shù)值是非負(fù)的，積分的結(jié)果為1。該方程表明一種更加一般的估計(jì)概率密度函數(shù)的方法119

Parzen窗方法可以使用神經(jīng)網(wǎng)絡(luò)的方法來實(shí)現(xiàn)，也就是通常所說的概率神經(jīng)網(wǎng)絡(luò)（Probabilisticneuralnetwork,PNN）?，F(xiàn)在假設(shè)有n個(gè)d維的樣本，它們都是從c個(gè)類別中選取的。在這種情況下，輸入層由d個(gè)輸入單元組成，每一個(gè)輸入單元都與模式層中的n個(gè)模式單元相連。而每一個(gè)模式單元只與類別層中的c個(gè)類別單元中的其中之一相連。Parzen窗方法可以使用神經(jīng)網(wǎng)絡(luò)的方法來實(shí)現(xiàn)120

從輸入層到模式層的連線表示可修改的權(quán)系數(shù)，這些權(quán)系數(shù)可以通過訓(xùn)練得到。每一個(gè)類別單元都計(jì)算與之相連的各模式單元的輸出結(jié)果的和。每一個(gè)模式層單元能夠?qū)λ臋?quán)重向量和歸一化的樣本向量x作內(nèi)積，得到Z=WtX，然后映射為。每一個(gè)類別單元把與它相連的模式層單元的輸出結(jié)果相加。這樣的結(jié)果就保證了類別單元處得到的就是使用協(xié)方差為的圓周對(duì)稱高斯窗函數(shù)的Parzen窗的估計(jì)結(jié)果（I表示d×d的單位矩陣）。從輸入層到模式層的連線表示可修改的權(quán)系數(shù)，這些121

PNN網(wǎng)絡(luò)是用下面的方式訓(xùn)練的。首先，把訓(xùn)練樣本中的每一個(gè)樣本x都?xì)w一化為單位長度，即。第一個(gè)經(jīng)過歸一化的樣本被置于輸入層單元上。同時(shí)，連接輸入單元和第一個(gè)模式層單元的那些連接被初始化為W1=X1。然后，從模式層的第一個(gè)單元到類別層中代表x1所屬類別的那個(gè)單元之間就建立了一個(gè)連接。同樣的過程對(duì)剩下的各個(gè)模式單元都重復(fù)進(jìn)行，即Wk=Xk，其中k=1,2,…,n。這樣就得到了一個(gè)網(wǎng)絡(luò)：輸入層單元與模式層單元之間是完全連通的，而模式層單元到類別單元之間是稀疏連接的。如果把第j個(gè)樣本的第k個(gè)分量記為Xjk，把這個(gè)分量到第j個(gè)模式層單元的連接權(quán)重系數(shù)記為wjk，其中j=1,2,…,n,k=1,2,…,d。得到算法描述如下：PNN網(wǎng)絡(luò)是用下面的方式訓(xùn)練的。首先，把訓(xùn)練樣122機(jī)器學(xué)習(xí)非參數(shù)方法課件123

然后，經(jīng)過訓(xùn)練完成的網(wǎng)絡(luò)就可以用這樣的方式實(shí)現(xiàn)分類：首先把一個(gè)歸一化了的測試樣本x提供給輸入節(jié)點(diǎn)，每一個(gè)模式層單元都計(jì)算內(nèi)積，得到“凈激活”（netactivation）：并產(chǎn)生netk的一個(gè)非線性函數(shù)，其中,是由用戶設(shè)置的一個(gè)參數(shù)，表示有效的高斯窗的寬度。每一個(gè)類別層單元?jiǎng)t把與它相連接的模式層單元的結(jié)果進(jìn)行相加。為了實(shí)現(xiàn)Parzen窗算法，這里的激活函數(shù)必須是一個(gè)指數(shù)函數(shù)。對(duì)于一個(gè)中心在某一個(gè)訓(xùn)練樣本W(wǎng)k處的未經(jīng)過歸一化的高斯窗函數(shù)。從期望得到的高斯窗函數(shù)倒推出模式層應(yīng)采用的非線性活化函數(shù)的形式，即如果令有效寬度hn為常數(shù)，則窗函數(shù)為然后，經(jīng)過訓(xùn)練完成的網(wǎng)絡(luò)就可以用這樣的方式實(shí)現(xiàn)124

其中使用了歸一化條件：這樣一個(gè)模式層單元向與它相連接的那個(gè)類別層單元貢獻(xiàn)了一個(gè)信號(hào)，這個(gè)信號(hào)的強(qiáng)度等于以當(dāng)前訓(xùn)練樣本為中心的高斯函數(shù)產(chǎn)生這個(gè)測試樣本點(diǎn)的概率。對(duì)這些局部估計(jì)值求和就得到判別函數(shù)gi(X)——也就是概率密度函數(shù)的Parzen窗估計(jì)結(jié)果。通過

運(yùn)算得到測試點(diǎn)的期望的類別：其中使用了歸一化條件125機(jī)器學(xué)習(xí)非參數(shù)方法課件1263、Parzen窗方法的優(yōu)點(diǎn)和缺點(diǎn)

Parzen窗方法的好處是不需事先知道概率密度函數(shù)的參數(shù)形式，比較通用，可以應(yīng)對(duì)不同的概率密度分布形式。在處理有監(jiān)督學(xué)習(xí)過程的時(shí)候，現(xiàn)實(shí)世界的情況往往是我們不知道概率密度函數(shù)形式。就算能夠給出概率密度函數(shù)的形式，這些經(jīng)典的函數(shù)也很少與實(shí)際情況符合。所有經(jīng)典的概率密度函數(shù)的形式都是單模的（只有單個(gè)局部極大值），而實(shí)際情況往往是多模的。非參數(shù)方法正好能夠解決這個(gè)問題，所以從這個(gè)意義上來講，Parzen窗方法能夠更好地對(duì)應(yīng)現(xiàn)實(shí)世界的概率密度函數(shù)，而不必實(shí)現(xiàn)假設(shè)概率密度函數(shù)的形式是已知的。Parzen窗方法能處理任意的概率分布，不必假設(shè)概率密度函數(shù)的形式已知，這是非參數(shù)化方法的基本優(yōu)點(diǎn)。3、Parzen窗方法的優(yōu)點(diǎn)和缺點(diǎn)Parze127

Parzen窗方法的一個(gè)缺點(diǎn)是它需要大量的樣本。在樣本有限的情況下，很難預(yù)測它的收斂性效果如何。為了得到較精確的結(jié)果，實(shí)際需要的訓(xùn)練樣本的個(gè)數(shù)是非常驚人的。這時(shí)要求的訓(xùn)練樣本的個(gè)數(shù)比在知道分布的參數(shù)形式下進(jìn)行估計(jì)所需要的訓(xùn)練樣本的個(gè)數(shù)要多得多。而且，直到今天人們還沒有找到能夠有效的降低訓(xùn)練樣本個(gè)數(shù)的方法。這也導(dǎo)致了Parzen窗方法對(duì)時(shí)間和存儲(chǔ)空間的消耗特別大。更糟糕的是，它對(duì)訓(xùn)練樣本個(gè)數(shù)的需求，相對(duì)特征空間的維數(shù)呈指數(shù)增長。這種現(xiàn)象被稱為“維數(shù)災(zāi)難（curseofdimensionality）”，嚴(yán)重制約了這種方法的實(shí)際應(yīng)用。Parzen窗方法的另外一個(gè)缺點(diǎn)是，它在估計(jì)邊界區(qū)域的時(shí)候會(huì)出現(xiàn)邊界效應(yīng)。Parzen窗方法的一個(gè)缺點(diǎn)是它需要大量的樣128

Parzen窗方法的一個(gè)問題是，窗寬度的選擇難以把握。下圖是一個(gè)二維Parzen窗的兩類分類器的判決邊界。其中窗寬度h不相同。左邊的圖中的窗寬度h較小，右邊的圖中的窗寬度h較大。所以左側(cè)的Parzen窗分類器的分類界面比右邊復(fù)雜。這里給出的訓(xùn)練樣本的特點(diǎn)是，上半部分適合用較小的窗寬度h，而下半部分適合用較大的窗寬度h。所以，這個(gè)例子說明沒有一個(gè)理想的固定的h值能夠適應(yīng)全部區(qū)域的情況。這算是Parzen窗方法的一個(gè)不足之處。Parzen窗方法的一個(gè)問題是，窗寬度的選擇難129機(jī)器學(xué)習(xí)非參數(shù)方法課件130

PNN是Parzen窗方法的實(shí)現(xiàn)。PNN的好處之一是學(xué)習(xí)速度很快，因?yàn)閷W(xué)習(xí)規(guī)則非常簡單（Wk=Xk），并且每一個(gè)樣本點(diǎn)只需要提供一遍。這個(gè)算法的空間復(fù)雜度也很容易計(jì)算：只要查看PNN圖中的連接個(gè)數(shù)即