概率密度估計及近鄰法

1、第三章概率密度函數(shù)估計及近鄰法Estimation of Probability Density Function and The Nearest Neighbor Rule1 引言2 總體分布的參數(shù)估計 極大似然估計 貝葉斯估計參數(shù)3 總體分布的非參數(shù)估計 Parzen窗法 kN近鄰法4 近鄰法則 1 引言 基于樣本的兩步貝葉斯決策： 估計類條件概率密度 和先驗概率 ； 利用 和 完成分類器設(shè)計。(第二章) 本章討論從樣本集推斷總體概率分布p(x|wi) 。而樣本的先驗概率P(wi)的估計較易實現(xiàn)。 概率密度函數(shù)含參數(shù)和形式兩方面內(nèi)容，分別稱為參數(shù)估計和非參數(shù)估計。其估計方法：1. 監(jiān)督參數(shù)

2、估計 已知樣本類別wi及其p(x|wi)形式，而參數(shù)未知，需從訓(xùn)練樣本x估計參數(shù)q q，如一元正態(tài)分布的m、s 2等參數(shù)。)( ixpw)(iPw)( ixpw)(iPw2. 非監(jiān)督參數(shù)估計 未知樣本類別wi ，已知概率密度函數(shù)p(x|wi)的形式，但參數(shù)未知，需從樣本x估計參數(shù)。 上述兩種均可用極(最)大似然法和Bayes估計法來估計參數(shù)。3. 非參數(shù)估計即估計p(x|wi)形式 已知樣本類別，但未知概率密度函數(shù)的形式，要從樣本推斷p(x|wi)屬于哪種分布。 可用Parzen窗法和kN近鄰法。4. 近鄰法則不屬于估計內(nèi)容 直接利用樣本設(shè)計分類器。非參數(shù)(即分類中不需要估計概率密度函數(shù)) 方

3、法之一。5. 參數(shù)估計的幾個基本術(shù)語統(tǒng)計量：每個訓(xùn)練樣本都包含總體信息。根據(jù)從總體中抽取的樣本集構(gòu)造某種函數(shù), 該函數(shù)統(tǒng)計學(xué)中稱為統(tǒng)計量。參數(shù)空間：概率密度形式已知，參數(shù)q q 未知, q q 可取值的集合稱為參數(shù)空間，記為。點估計、估計量和估計值：構(gòu)造一個統(tǒng)計量f(x1,xn) 作為參數(shù)q 的估計量 。如果x1,xn屬于某類，代入統(tǒng)計量f，就可得到該類具體的估計值。本章參數(shù)估計屬于點估計。區(qū)間估計要求用區(qū)間(d1, d2)作為q 可能取值范圍的一種估計。該區(qū)間稱為置信區(qū)間。q2 總體分布的參數(shù)估計1. 極(最)大似然估計 基本原理 把參數(shù)q q 看成確定的(非隨機(jī)) 但取值未知，最好估計值是

4、在樣本x概率為最大條件下得到的。 假設(shè)： 按類別把樣本集分成c個子集 x1, x2,xc，其中xj中的樣本是從概率密度為p(x|wj)的總體中獨立抽取的。 p(x|wj)形式已知, 參數(shù)q qj未知, 可寫成p(x|wj,q qj)。 不同類的參數(shù)獨立，即xi不包含q qj信息(ij)這樣每一類可單獨處理，共處理c個獨立問題。 設(shè)某類有N個樣本組成了樣本集 xx1,x2,xN 樣本是獨立從該類抽取的，因此N個隨機(jī)變量的聯(lián)合概率密度 統(tǒng)計學(xué)中稱p(x|q)為相對于樣本集x的q 的似然函數(shù)l(q q ) 似然函數(shù)l(q q) 給出了從總體中抽取的x1,x2,xN這N個樣本的概率。 極大似然估計值定

5、義： 令l(q q) 為樣本集x的似然函數(shù)，在的參數(shù)空間中能使l(q q) 極大化的那個 值。)()()(),()(2121qqqqqNNxpxpxpxxxplNkkNxpxxxpxp121)(),()(qqqq 極大似然法的主要思想：如果在一次觀察中一個事件出現(xiàn)了，則這個事件出現(xiàn)的可能性最大。事件xx1,x2,xN在一次觀察中(即從總體中抽取N個樣本)出現(xiàn)了，就可認(rèn)為 p(x|q)達(dá)到極大值，即在參數(shù)空間中使似然函數(shù)極大化的 值。 一個簡單的例子：q為均值。對應(yīng)達(dá)極大點時在點時較小點和有不同值的概密計算自左向右取不同值時，當(dāng)。此時似然法估計用極大集已知，通過抽出的樣本，現(xiàn)方差布設(shè)一維樣本服從

6、正態(tài)分qqqqqmqmsmq,)|(,)|()|(,),()|(616212xpCBAxpxpxxxxxNxpkk 假設(shè)似然函數(shù)p(x|q q) 對未知參數(shù)q q 是連續(xù)可微的，則 可由典型的求極值的方法求得。 求極大值的必要條件 單個q q 的情況下： 若q q 是向量，有s個分量q q =q1,qs T，則多變量的梯度算子 對數(shù)似然函數(shù)H(q q)是單調(diào)的增函數(shù)，為計算方便，一般用對數(shù)似然函數(shù)。sqqq10)(qqddlq 使似然函數(shù)最大。只有個解，解，如圖中有有時上式可能沒有唯一。，就是極大似然估計值得到的解個方程的從而下個樣本獨立抽取的條件在對數(shù)似然函數(shù)qqqqqqqqqqqqqqqq

7、q50)()|(ln)()|(ln)|(ln)(),|,(ln)|(ln)(ln)()(11111sHxpHxpxpHNxxpxplHHNkkkNkNkksN 正態(tài)分布的極大似然估計 從總體中抽取N個樣本 xk，觀察下列不同情況：已知，均值向量m m未知，即q q m m。 m的極大似然估計必須滿足方程： 未知均值的極大似然估計正是樣本的算術(shù)平均。)()(21exp21)|(1212mmqxxxpTdNkkNkkxNx1111, 0) (mm)()|(ln)()(21|)2ln(21)|(ln11mqmmqmkkkTkdkxxpxxxp 一維正態(tài)情況，兩個參數(shù)均未知，設(shè)q1m，q2s 2 ,

8、q qq1,q2 T 。 2122)(212ln21)(lnqqqqkkxxp似然函數(shù)22212122)(21)(1)(lnqqqqqqqkkkxxxp兩個變量的梯度2)(21exp21)(smsqxxp分布形式NkNkkNkkxx1122212112210)(10)(1qqqqqqq需滿足下列條件、求極大似然估計2122112) (11msqmqsmNkkNkkxNxN和方差值解方程，得到一維的均多維正態(tài)密度的情況。 計算方法和形式完全類似，只是復(fù)雜些，計算結(jié)果： 均值向量的極大似然估計是樣本的均值，而協(xié)方差的極大似然估計是N個矩陣 的算術(shù)平均。這是一致估計。 協(xié)方差矩陣的無偏估計為Tkkx

9、x) )(mmNkTkkxxN1) )(11mm維向量。個抽樣，是為第其中dkxxxNxNkNkTkkNkk11)(11mmm2. Bayes估計和Bayes學(xué)習(xí) Bayes估計：根據(jù)樣本集 x 確定總體某個參數(shù)q Bayes學(xué)習(xí)：利用樣本集 x 確定概率密度函數(shù)p(x)Bayes估計 基本原理：把參數(shù)q當(dāng)作具有某種先驗分布p(q) 的隨機(jī)變量, 對樣本x觀察使先驗分布轉(zhuǎn)化為后驗分布p(q|x)，據(jù)此再修正原先的估計 。假設(shè)： 把所有的樣本按類別分成c個子集。每個子集有N個樣本 x = x1,x2,xN。每類可單獨處理。 已知樣本的分布形式p(x|q q) ，而參數(shù)q q 未知。 q為隨機(jī)變量

10、, 已知其先驗概密函數(shù)p(q) 。q貝葉斯估計和最小風(fēng)險貝葉斯決策可統(tǒng)一： Bayes估計：有一個樣本集x，用來估計所屬總體分布的某個參數(shù)，使帶來的貝葉斯風(fēng)險最小。 Bayes估計最小風(fēng)險 R為給定條件下某個估計量的期望損失，常稱為條件風(fēng)險。使條件風(fēng)險最小的估計量q q，也就是貝葉斯估計。 經(jīng)推導(dǎo)(P.52定理3.1)使用平方誤差損失函數(shù)時，得到估計量為條件期望：2)(),()(),()(qqqqqqqqq損失函數(shù)dxpxRdxpxEqqqqq)|()|( Bayes參數(shù)估計步驟： 確定q 的先驗概率密度函數(shù)p(q)； 由樣本集 x = x1,x2,xN計算樣本的聯(lián)合分布 ，它是 q 的函數(shù)

11、； 用Bayes公式求后驗分布p(q | x) 求樣本的估計量qNkkxpxp1)|()|(qqqqqqqqdxpxEx)|(|條件下的條件期望：給定是在，貝葉斯估計量損失函數(shù)為二次函數(shù)時qqqqqqdxpxpxpxpxp)|()|()|()|()|(正態(tài)分布情況的Bayes估計舉例 樣本為一維正態(tài)分布 p(x|m)N(m,s 2)，m未知 m是隨機(jī)的，其先驗概密 p(m)N(m0,s02) N個樣本構(gòu)成樣本集 x=x1, x2, xN 求m的估計量 解： 用Bayes公式求m的后驗分布：mmmmmmmmmmmdpxpapxpadpxppxpxpNkk)()|(/1)()|()()|()()|

12、()|(1a比例因子與無關(guān)mmmmqqqqdxpdxp)|()|( 根據(jù)上述假設(shè)： 代入計算后驗概密 p(|x) p(|x)是的二次函數(shù)的指數(shù)函數(shù)，仍是正態(tài)密度, 寫成),()(),()|(2002smmsmmNpNxpk)1(2)1(21exp)()(21exp)(21exp21)(21exp21)|(200122202, ,20012,20200122axnaxaxaxpNkkNkkNkk無關(guān)項并入與mmsmsmsssmmsmsmmssmsm)(21exp21)|(),()|(22NNNNNxpNxpsmmsmsmm0220222020222202202022022202012002220

13、2221exp21)|(),()|(1,11mssssssmmmsmmsmmmmmsmmmsssssmssssssmsmssmsssNmNNddxpNxpNNmNNxNmmNNNNNNNNNNNNNkkNNNNN。為的后驗概密由樣本集得到解得樣本的均值比較后得到 Bayes學(xué)習(xí)求概率密度函數(shù)p(x| X) 從聯(lián)合密度求條件概密函數(shù) X由N個樣本組成，X=x1,xN 用Bayes公式計算q 的后驗分布 p(q|X)， 根據(jù)獨立性 其中 XN=x1, xN1,xN， XN1=x1,xN1 qqqqqqqqqqqqqqqdXpxpXpxpXpXpxpXpdpXppXpXpNNNNNNNN)()()(

14、)()()()()()()|()()|()(111qqqqqdXpxpdXxpXxp)|()|()|,()|( 已知q 的先驗概密 p(q|X0) = p(q)，根據(jù)樣本序列x1, xN按下式反復(fù)計算，得到概率密度的序列p(q), p(q|x1), p(q|x1,x2),，同時修改q，如果這個密度序列在估計值 附近產(chǎn)生一個陡峰, 即d 函數(shù), 這種性質(zhì)稱為Bayes學(xué)習(xí)。q)()|()|(),()|(,xpxpxxpxpxpNNqqqqq即也就是真實總體分布而，就是真實參數(shù)時當(dāng)qqqqqqdXpxpXpxpXpNNNNN)()()()()(11 Bayes學(xué)習(xí)步驟： 前三步同Bayes估計。下

15、面的步驟 讀入第一個樣本x1，計算得到得到后驗概密p(q|x1), 據(jù)此作為下一步計算的先驗概率密度； 讀入樣本x2，計算得到p(q|x1,x2) ； ； 這樣得到一個概率密度序列： 這個過程稱為參數(shù)估計的遞歸的Bayes方法。 這個序列收斂于一個q q0為中心的d 函數(shù)，則這個性質(zhì)稱 Bayes 學(xué)習(xí)。大多數(shù)密度函數(shù)有此性質(zhì)。為已知的先驗密度函數(shù)第一列)(),|(,),|(),|(),(1211qqqqqpxxpxxpxppN從前例 Bayes學(xué)習(xí)得到條件概率密度函數(shù) 非監(jiān)督參數(shù)估計方法所采用的也是這兩種方法，但計算較復(fù)雜。就極大似然估計來說，由于樣本的類別未知，因此定義c類樣本組成的混合密

16、度建立似然函數(shù)。方差修正為通過樣本估計均值為方差為為也是正態(tài)分布，其均值為，為其中2222122122222121211,),(),|(,),|()(21exp21),|(),(),|(),()|(),|()|(),|(NNNNNNNNNNNNNNNNNNxxxpxxxpxxxxpNxxpNxpdxxpxpxxxpssmssmssmssmsssmmsmmmmm3 總體分布的非參數(shù)估計 根據(jù)訓(xùn)練樣本集x=x1, x2, xN , 估計總體分布概率密度函數(shù)p(x|x1, x2, xN)形式。 基本思想： 每個樣本對總體概率密度 分布都有貢獻(xiàn) (如矩形a)， N個樣本的貢獻(xiàn)疊加起來， 得到概率密度估

17、計，如虛線。 也可認(rèn)為每個樣本在自己位 置上貢獻(xiàn)增大，離得遠(yuǎn)貢獻(xiàn) 小(如正態(tài)分布)，同樣疊加 得到概率密度估計(下圖)。直方圖方法估計一維概率密度函數(shù)近似值： 將x軸劃分為長度為h的區(qū)間，樣本x落在某個區(qū)間的概率就是這個區(qū)間的估計值。 樣本總數(shù)為N，落在某個區(qū)間的點數(shù)為kN，相應(yīng)的概率近似于頻數(shù)： P kN /N 概率密度在同一個區(qū)間為常數(shù)，近似等于 估計值收斂于真實值的條件： hN 0； kN ； kN /N0。 這三個條件表示對N的依賴型。為區(qū)間中點。00,2,1)( xhxxNkhxpNNkPPNPNmkRmkNPPPNmmkPkNkNCRxPPPCPPRkNxxxNxpxxpdxxpP

18、RxkmkkNkNkkNkkNR) 1(max) 1(,)!( !,)1 (,)()()(. 121的概率最大個落入個樣本中根據(jù)眾數(shù)定義，。即稱為眾數(shù)取最大值的知，根據(jù)二項分布的性質(zhì)可的概率落入為服從離散二項分布的概率個樣本落入?yún)^(qū)域個中有，則個樣本中獨立抽取的從的總體概率密度函數(shù)為的概率落入?yún)^(qū)域基本方法：設(shè)樣本有關(guān)。以及落入其中的樣本數(shù)的區(qū)域體積包含、的估計值。與樣本數(shù)點概率密度上式就是因此中的點，則是的體積，是區(qū)域式中，中近似不變，得到在使足夠小，連續(xù)，并且區(qū)域設(shè)為了估計kVxNxpxVNkxpVxpdxxpPNkRxRVVxpdxxpPRxpRxpxpRR)(/)( )( )( )()()

19、()(),( 上的一個很好估計。在這是總體密度，RxpNkP)( 理論上講，要使 ，就必須使體積V趨于零，同時N和k 趨于無窮大。 若體積V固定, 樣本取得越來越多, 則k/N收斂，只能得到p(x)的空間平均估計 若樣本數(shù)N固定，使R不斷縮小，V趨于零，會發(fā)生兩種無意義情況：一是區(qū)域內(nèi)不包含任何樣本，p(x)=0；二是碰巧有一個樣本，p(x) = 。 實際上樣本是有限的，V也不能任意縮小。若用這種方法估計，頻數(shù)k/N和估計的p(x)將存在隨機(jī)性，都有一定的方差。RRdxdxxpVP)( )()(xpxpN收斂于 假設(shè)有無限多的樣本可利用，在特征空間構(gòu)造包含x點的區(qū)域序列R1, R2, RN,

20、對R1用一個樣本進(jìn)行估計，對R2用二個樣本，。設(shè)落在RN的 x點數(shù)為kN，則第N次估計的概率密度函數(shù)為 要使 NNNVNkxp/)(收斂，這是必要條件。忽略不計。要使比仍可，但與內(nèi)落入大量樣本盡管。收斂于可使頻數(shù)比的點對。收斂于可使空間平均區(qū)域平滑縮小)(, 0lim,0)(,lim)(, 0limxpNkRNkPNkxpkxpVPVNNNNNNNNNN的三個條件：收斂于)()(xpxpN 滿足這三個條件的區(qū)域序列通常有兩種方法： Parzen窗法： 把包含x點的區(qū)域序列VN選為樣本數(shù)目N的函數(shù)，并使其空間體積VN隨N的增大而減小，例如 VN =N-1/2 。 但對kN和kN /N都要加些限制

21、條件以使估計值收斂于p(x) 。 kN近鄰法： 把KN選為樣本數(shù)目的函數(shù)。 讓kN為N的某個函數(shù) (例如kN =N1/2) ，并調(diào)整體積VN大小，使區(qū)域正好包含x的kN個近鄰，則該區(qū)域體積可用作x點的密度估計。2. Parzen窗法 窗估計的概念 多維情況下，圍繞x點的區(qū)域RN為一個超立方體， ，邊長為hN, d為特征空間維數(shù)。 訓(xùn)練樣本xi是否落入這個超立方體內(nèi)，檢查x-xi的每個分量值，若小于hN/2，則在RN內(nèi)，其中x為數(shù)軸(特征空間坐標(biāo)軸)上的點。 為了用函數(shù)描述落入VN 中訓(xùn)練樣本的數(shù)目kN，定義窗函數(shù) 對u的特征空間來說，f(u)是圍繞原點的1個單位超立方體。dNNhV其他，當(dāng)，,

22、 0,2 , 12/1|1)(djuujf 若u=(x-xi)/hN，則窗函數(shù) 當(dāng)某個樣本xi落入以x為中心、體積為VN的立方體內(nèi)時計為1，否則為0。 落入VN內(nèi)的樣本數(shù)： x點的密度估計 Parzen窗的密度估計 NiNiNNhxxVNxp111)(f其他當(dāng)，, 0, 121| )( |1djhxxhxxNjiNifNNNVNkxp/)(NiNiNhxxk1f在以x為中心的立方體內(nèi)的樣本應(yīng)相加 用方窗的直觀解釋一維概率密度函數(shù)的估計： 樣本集xx1,x2,x5有五個樣本。 每個樣本xi在以 xxi為中心，寬為h的范圍內(nèi)對概率密度函數(shù)貢獻(xiàn)為1，數(shù)軸x上任一點的概密函數(shù)是樣本集中全部樣本對概密函

23、數(shù)之和。 對所有的點求和，得到p(x)的分布虛線所示。 如果樣本數(shù)很多，并選擇適當(dāng)?shù)拇昂瘮?shù)，估計的概率密度函數(shù)的性質(zhì)有可能接近真實的概率密度函數(shù)p(x)。估計量 為密度函數(shù)的條件 為使 是一個估計合理的概率密度函數(shù)，必須滿足對概率密度函數(shù)的基本要求，即它應(yīng)該非負(fù)且在特征空間積分為1。 為此窗函數(shù)須滿足兩個條件： )(xpN。概率的估計的密度函數(shù)利用第二個條件可證明非負(fù)。限制條件下，保證在第一個數(shù)的形式窗函數(shù)本身具有密度函即積分為非負(fù)1)()()( 11)(0)(xpPxpxpduuuNNff)(xpN 窗函數(shù)的選擇： 方窗函數(shù) 正態(tài)窗函數(shù) 指數(shù)窗函數(shù) 只要所選擇的函數(shù)滿足前述的兩個條件式，都可

24、作為窗函數(shù)。 221exp21)(uuf|)|exp(21)(uuf02/1|, 1)(uuf估計量的統(tǒng)計性質(zhì)NVNVVuuuduuuxxpxpNNNNNdiiuuN/1,lim0lim0)(lim)(sup1)(0)()()(1縮減的速率要低于窗寬受下列條件約束；窗函數(shù)滿足下列條件點連續(xù)；在限制條件：和平方誤差一致性。是漸近無偏性計量在一些限制條件下，估ffff 產(chǎn)生隨機(jī)變量的補(bǔ)充材料（共四頁，三個問題）產(chǎn)生 0,1之間均勻分布的隨機(jī)數(shù)ui方法為正整數(shù)為計算機(jī)字長的位數(shù)，參數(shù)選擇：例：。之間均勻分布的隨機(jī)數(shù)量之間均勻分布的隨機(jī)變?yōu)榉N子。為模數(shù)為增量為乘子其中：個隨機(jī)數(shù)是第kzkacpmuzu

25、zuzzcammzummzzmcaizmcazzpiiiiii, 14, 122438. 016/7, 716mod)345(063. 016/1, 116mod)365(375. 016/6, 616mod)375(7, 3, 5,16 1 , 0/ 1, 010,)(mod(016162211001mm 產(chǎn)生隨機(jī)變量方法(非0,1均勻分布的隨機(jī)數(shù)) 基本方法反變換法 以概率積分變換定理為基礎(chǔ)的一種常用的抽樣方法。其基礎(chǔ)是0,1之間均勻分布的隨機(jī)數(shù)。 若隨機(jī)變量x的分布函數(shù)為F(x)，其反函數(shù)F -1?？捎?,1之間均勻分布的隨機(jī)數(shù)來產(chǎn)生要求分布的隨機(jī)變量。 具體方法 U為0,1均勻分布隨機(jī)

26、數(shù) 令 U=F(x) x = F-1(U) x即為所要求分布的隨機(jī)變量。變量區(qū)間上均勻分布的隨機(jī)即為則有，令隨機(jī)數(shù)使用的分布函數(shù)可得到由其他其概率密度函數(shù)為變量區(qū)間上均勻分布的隨機(jī)例：產(chǎn)生,)()()() 1 , 0()(1)()(,0,1)(,0baxuabaxbxabxaxxFuuUbxabxaxdtabxFxxfbxaabxfbaxx產(chǎn)生一維正態(tài)分布隨機(jī)變量的近似方法xyNuxnnunnnuUxxNNuuunnnxxxniiniiniixxnxxnxxsmsmsmsmsmsm則分布，若要若取的隨機(jī)變量分布，可得到服從標(biāo)準(zhǔn)正態(tài)當(dāng)。其均勻分布的隨機(jī)數(shù)個的近似正態(tài)分布。和方差為之和，服從均值為

27、量的獨立同分布的隨機(jī)變，方差為個均值為概率中心極限定理：),(612212122) 1 , 0(12/1, 2/1, 1 , 0,121112212212舉例 根據(jù)已知概率密度函數(shù)p(x)產(chǎn)生一系列隨機(jī)變量，作為樣本。用正態(tài)窗函數(shù)估計樣本的總體分布，并與真實的概率密度函數(shù)作比較。 采用下列兩種樣本： p(x)是均值為0方差為1的正態(tài)分布，生成樣本xi p(x)是兩個均勻分布的混合密度生成樣本xi02025. 025 . 21)(xxxp其他 統(tǒng)計落入正態(tài)窗的隨機(jī)樣本數(shù)，計算p(x)的估計值，在計算中要注意公式中變量和參數(shù)的意義。 這種方法具有普遍性，即不管是規(guī)則或不規(guī)則、單峰或多峰分布都可用，

28、但需要的樣本數(shù)量很大。需要一定的經(jīng)驗。很敏感的選擇對估計量對有限時，選擇問題。在窗估計中有個體積系列為可調(diào)整的參數(shù)，概率密度函數(shù)使用正態(tài)窗,)( 4, 1,4111)(21exp21)(111112xphNhhNhhhxxhNxpuuNNiNiNNff從圖中可看出N256，h11時，接近真實分布，而h14時，噪聲小。當(dāng)樣本數(shù)很多時， h1影響不大。均值為0方差為1的正態(tài)分布二個均勻分布的混合密度 基本步驟：產(chǎn)生訓(xùn)練集樣本，有兩種方法： 在問題域中搜集樣本； 根據(jù)題意按已知的概率密度產(chǎn)生隨機(jī)樣本。設(shè)x為d維的數(shù)軸，以體積 在數(shù)軸上向前推進(jìn)，即N=1,2,3,，這樣就可統(tǒng)計落入各體積的樣本數(shù)KN。

29、選擇窗函數(shù)f(u)，利用概率密度函數(shù)公式進(jìn)行統(tǒng)計 計算數(shù)軸上各點的密度。對所有的點求和，用圖形表示概率密度曲面(一維為曲線)。 如果自行按某種概率密度產(chǎn)生的隨機(jī)數(shù)，則可將計算得到的曲面(線)與其進(jìn)行比較，以驗證Parzen窗法的正確性。dNNhVNiNiNNhxxVNxp111)(f3. kN近鄰法 Parzen 窗存在問題：體積V的選擇 V1的選擇很敏感，太小大部分是空的噪聲大；太大估計值平坦，不能反映總體分布變化。kN近鄰法：體積不是樣本的函數(shù)，而是kN的函數(shù)。先確定kN，然后以x點為中心，讓體積不斷擴(kuò)大，直到捕獲到kN個樣本為止，這些樣本稱為x的kN個近鄰。如果點x附近密度愈高, 則體積

30、愈小, 分辨率高，反之體積愈大。 kN近鄰估計公式： NNNVNkxp/)(NVVN/1估計的pN (x)收斂于真實概率密度p(x)的充分必要條件： kN 可取為N的某個函數(shù)，如 k1 0 選擇k1，使kN 1。 這種方法同樣要求樣本數(shù)量要大。一維要幾百個樣本；二維要幾千個樣本。不為樣本的體積獲的增長不要太快，使捕可限制的概率。估計落入這樣可較好地用00/lim/lim0limNNNNNNNNNNkkNkVNkkV，NkkN1例：條件同上例，用kN近鄰法。 p(x)是均值為0方差為1的正態(tài)分布，生成樣本xi p(x)是二個均勻分布的混合密度生成樣本xi 設(shè) N=1,16,256, ；kN =1

31、,4,16, 估計結(jié)果為左圖所示。 計算步驟與Parzen窗法類似。 02025. 025 . 21)(xxxp其他NNNVNkxp/)(估計公式4 近鄰法 kN近鄰法是利用樣本進(jìn)行概率密度函數(shù)的估計。 現(xiàn)在討論的是直接利用樣本，根據(jù)距離分類。 近鄰法： 在設(shè)計階段已根據(jù)訓(xùn)練集樣本在特征空間劃分了邊界。計算待識別樣本點x到周圍近鄰的距離， 將x歸入最近鄰中樣本所屬的那個類。 最近鄰法 k-近鄰法 此法屬非參數(shù)法(無需估計概率密度)有近鄰法，線性判別函數(shù)和聚類(非監(jiān)督學(xué)習(xí)法)。 兩種近鄰法1.最近鄰法 決策規(guī)則 設(shè)有c個類別 ，每類有標(biāo)明類別的Ni個樣本，i =1, 2 , c。 wi類的判別函

32、數(shù)和決策規(guī)則： 比較未知樣本x與 個已知類別樣本xik 間的歐氏距離，將 x 歸入離它最近的那個樣本類。()cixxxxxxxxijdjjiTii, 2 , 1)()()(|212121歐氏距離：jiijxcixgxgw則決策若決策規(guī)則：, 2 , 1),(min)(為待分類的樣本是樣本的類別，其中判別函數(shù)：xiNkxxxgikiki, 2 , 1,|min)(ciiNN1cwww,21最近鄰法錯誤率的分析 訓(xùn)練集樣本數(shù)有限，有時多一個或少一個對分類結(jié)果影響較大。 例如圖中有 A類和 B類， O 代表待分樣本,用歐氏距離測量，O的近鄰為A3，分在A類；若將A3拿開，O就分在B類。 說明最近鄰法

33、錯誤率有偶然性。樣本越多偶然性減少。 因此用訓(xùn)練樣本數(shù)增到 極大來評價性能，用到 漸近概念分析錯誤率。 設(shè)N個樣本下的平均錯誤概率為PN(e)，且樣本x的最近鄰為x ，則 可證明下述關(guān)系 根據(jù)第二章，貝葉斯錯誤率P*)(lim)()()| () ,|()(ePPePNPdxxpdxxxpxxePePNNNNN的極限時為當(dāng)定義漸近平均錯誤率為類數(shù)。為貝葉斯錯誤率，其中cPPccPPP12dxxpxPdxxpxePPm)()|(1 )()|(w 最近鄰法漸近平均錯誤率P的范圍(上下界) ：PccPPPPccPdxxpxPPPPcccPcicxPPPPxPPPdxxpxPdxxpxePePPciii

34、mciiNNNN1212)( )|(1 ,111), 2 , 1(/1)|(, 01)|()( )|(1 )()|(lim)(lim1212所以上界可以證明息情況。密度函數(shù)相等，即無信相當(dāng)于各類的條件概率，時，各類后驗概率相等，當(dāng)時，當(dāng)特定情況下，存在下界wwww 根據(jù)最近鄰法錯誤率的公式 圖中標(biāo)明最近鄰法錯誤率的上下界。 Bayes錯誤率在0和(c-1)/c 之間。 當(dāng)Bayes錯誤率較小時， 最近鄰法的錯誤率最大為Bayes兩倍。 一般情況下，近鄰法錯誤率在陰影區(qū)域中。 近鄰法是一種次優(yōu)法，它的錯誤率比Bayes決策大。當(dāng)樣本數(shù)目無限大時，它的錯誤率P不會超過Bayes錯誤率P*的2倍。)12(PccPPPP=2P*P=P*2. k-近鄰法，最近鄰法的改進(jìn) 在待分樣本x的k個近鄰中，按出現(xiàn)最多的樣本類別來作為x的類別，即在x的近鄰中一一找出它們的類別進(jìn)行判別。方法：首先規(guī)定k的大小，找出待分樣本x的k個近鄰，看這k個近鄰中多數(shù)屬于哪一類，就將x歸為這一類。 x附近的n個樣本中來自w1類的有n1個，設(shè)近鄰 有k1 ；來自w2類的有n2個, 近鄰有k2個； ；來自wc 類的有nc個, 近鄰有kc個。 判別函數(shù)： gi(x) ki, i = 1,2,c 決策規(guī)則：jicijxkxgw則決策若,