概率密度估計(jì)及近鄰法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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