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

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

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

k-近鄰估計 Pazen窗單擊此處添加標題前面的章節(jié)中，我們介紹了參數(shù)2K近鄰K近鄰3最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心作為類別代表點，考查新樣本到各代表點的距離并將它分到最近的代表點所代表的類。極端情況，將所有樣本都作為代表點－－－－近鄰法最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心作為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)練樣本劃分成若干子類，并在每個子類中確定代表點，一般用子類的質(zhì)心或鄰近質(zhì)心的某一樣本為代表點。測試樣本的類別則以其與這些代表點距離最近作決策。該法的缺點是所選擇的代表點并不一定能很好地代表各類，其后果將使錯誤率增加。最近鄰法的基本思想：以全部訓(xùn)練樣本作為“代表點”，計算測試樣本與這些“代表點”，即所有樣本的距離，并以最近鄰者的類別作為決策。近鄰法是由Cover和Hart于1968年提出的，隨后得到理論上深入的分析與研究，是非參數(shù)法中最重要的方法之一。最小距離分類器：將各類訓(xùn)練樣本劃分成若干子類，并在每個子類中6機器學(xué)習(xí)非參數(shù)方法課件7機器學(xué)習(xí)非參數(shù)方法課件8在二維情況下，最近鄰規(guī)則算法使得二維空間被分割成了許多Voronoi網(wǎng)格，每一個網(wǎng)格代表的類別就是它所包含的訓(xùn)練樣本點所屬的類別。在二維情況下，最近鄰規(guī)則算法使得二維空間被分割成了許多Vor9

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

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

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

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

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

其中而在這條件下的平均錯誤率14

若是兩類問題，則

貝葉斯錯誤率：最近鄰法錯誤率：可見在一般情況下△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)會出現(xiàn)什么什么情況？

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

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

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

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

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

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

決策規(guī)則為：

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

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

對于兩類問題，23對所有的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*)

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

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

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

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

這種方法著眼于只解決減少計算量，但沒有達到減少存儲量的要求。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

尋找x最近鄰的程序步驟

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

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

＝x’

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

1、Parzen窗方法綜述、發(fā)展歷史及現(xiàn)狀42Parzen窗（Parzenwindow）又稱為核密度估計（kerneldensityestimation），是概率論中用來估計未知概率密度函數(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ù)聚類算法提出了修訂的核密度估計方法，對Parzen窗做了一些改進。Parzen窗方法雖然是在上個世紀60年代提出來的，已經(jīng)過去了45年的時間，看上去是一種很“古老”的技術(shù)，但是現(xiàn)在依然有很多基于Parzen窗方法的論文發(fā)表。這說明Parzen窗方法的確有很強的生命力和實用價值，雖然它也存在很多缺點。Parzen窗（Parzenwindow432、Parzen窗方法和概率神經(jīng)網(wǎng)絡(luò)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

k-近鄰估計 Pazen窗單擊此處添加標題前面的章節(jié)中，我們介紹了參數(shù)74K近鄰K近鄰75最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心作為類別代表點，考查新樣本到各代表點的距離并將它分到最近的代表點所代表的類。極端情況，將所有樣本都作為代表點－－－－近鄰法最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心作為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)練樣本劃分成若干子類，并在每個子類中確定代表點，一般用子類的質(zhì)心或鄰近質(zhì)心的某一樣本為代表點。測試樣本的類別則以其與這些代表點距離最近作決策。該法的缺點是所選擇的代表點并不一定能很好地代表各類，其后果將使錯誤率增加。最近鄰法的基本思想：以全部訓(xùn)練樣本作為“代表點”，計算測試樣本與這些“代表點”，即所有樣本的距離，并以最近鄰者的類別作為決策。近鄰法是由Cover和Hart于1968年提出的，隨后得到理論上深入的分析與研究，是非參數(shù)法中最重要的方法之一。最小距離分類器：將各類訓(xùn)練樣本劃分成若干子類，并在每個子類中78機器學(xué)習(xí)非參數(shù)方法課件79機器學(xué)習(xí)非參數(shù)方法課件80在二維情況下，最近鄰規(guī)則算法使得二維空間被分割成了許多Voronoi網(wǎng)格，每一個網(wǎng)格代表的類別就是它所包含的訓(xùn)練樣本點所屬的類別。在二維情況下，最近鄰規(guī)則算法使得二維空間被分割成了許多Vor81

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

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

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

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

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

其中而在這條件下的平均錯誤率86

若是兩類問題，則

貝葉斯錯誤率：最近鄰法錯誤率：可見在一般情況下△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)會出現(xiàn)什么什么情況？

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

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

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

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

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

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

決策規(guī)則為：

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

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

對于兩類問題，95對所有的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*)

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

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

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

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

這種方法著眼于只解決減少計算量，但沒有達到減少存儲量的要求。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

尋找x最近鄰的程序步驟

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

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

＝x’

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

1、Parzen窗方法綜述、發(fā)展歷史及現(xiàn)狀114Parzen窗（Parzenwindow）又稱為核密度估計（kerneldensityestimation），是概率論中用來估計未知概率密度函數(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ù)聚類算法提出了修訂的核密度估計方法，對Parzen窗做了一些改進。Parzen窗方法雖然是在上個世紀60年代提出來的，已經(jīng)過去了45年的時間，看上去是一種很“古老”的技術(shù)，但是現(xiàn)在依然有很多基于Parzen窗方法的論文發(fā)表。這說明Parzen窗方法的確有很強的生命力和實用價值，雖然它也存在很多缺點。Parzen窗（Parzenwindow1152、Parzen窗方法和概率神經(jīng)網(wǎng)絡(luò)

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

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

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

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

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

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

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

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

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

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

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

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

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

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