非參數(shù)估計(jì)課件

1、非參數(shù)估計(jì)劉芳，戚玉濤qi_1PPT課件引言參數(shù)化估計(jì)：ML方法和Bayesian估計(jì)。假設(shè)概率密度形式已知。實(shí)際中概率密度形式往往未知。實(shí)際中概率密度往往是多模的，即有多個(gè)局部極大值 。實(shí)際中樣本維數(shù)較高，且關(guān)于高維密度函數(shù)可以表示成一些低維密度函數(shù)乘積的假設(shè)通常也不成立。本章介紹非參數(shù)密度估計(jì)方法：能處理任意的概率分布，而不必假設(shè)密度函數(shù)的形式已知。2PPT課件主要內(nèi)容概率密度估計(jì)Parzen窗估計(jì)k-NN估計(jì)最近鄰分類器（NN）k-近鄰分類器（k-NN）3PPT課件概率密度估計(jì)概率密度估計(jì)問(wèn)題：給定i.i.d.樣本集：估計(jì)概率分布：4PPT課件概率密度估計(jì)直方圖方法：非參數(shù)概率密度估計(jì)的

2、最簡(jiǎn)單方法 1. 把x的每個(gè)分量分成k 個(gè)等間隔小窗， （ xEd ，則形成kd 個(gè)小艙） 2. 統(tǒng)計(jì)落入各個(gè)小艙內(nèi)的樣本數(shù)qi 3. 相應(yīng)小艙的概率密度為： qi /(NV ) （ N ：樣本 總數(shù)，V ：小艙體積）5PPT課件概率密度估計(jì)直方圖的例子6PPT課件概率密度估計(jì)非參數(shù)概率密度估計(jì)的核心思路：一個(gè)向量x落在區(qū)域R中的概率P為：因此，可以通過(guò)統(tǒng)計(jì)概率P來(lái)估計(jì)概率密度函數(shù)p(x)7PPT課件概率密度估計(jì)假設(shè)N個(gè)樣本的集合是根據(jù)概率密度函數(shù)為p(x)的分布獨(dú)立抽取得到的。那么，有k個(gè)樣本落在區(qū)域R中的概率服從二項(xiàng)式定理：k 的期望值為：對(duì)P的估計(jì)：當(dāng) 時(shí)， 估計(jì)是非常精確的8PPT課件

3、概率密度估計(jì)假設(shè)p(x)是連續(xù)的，且R足夠小使得p(x)在R內(nèi)幾乎沒(méi)有變化。令R是包含樣本點(diǎn)x的一個(gè)區(qū)域，其體積為V，設(shè)有N個(gè)訓(xùn)練樣本，其中有k落在區(qū)域R中，則可對(duì)概率密度作出一個(gè)估計(jì)：對(duì)p(x) 在小區(qū)域內(nèi)的平均值的估計(jì)9PPT課件概率密度估計(jì)當(dāng)樣本數(shù)量N固定時(shí)，體積V的大小對(duì)估計(jì)的效果影響很大。 過(guò)大則平滑過(guò)多，不夠精確； 過(guò)小則可能導(dǎo)致在此區(qū)域內(nèi)無(wú)樣本點(diǎn)，k=0。此方法的有效性取決于樣本數(shù)量的多少，以及區(qū)域體積選擇的合適。10PPT課件概率密度估計(jì)收斂性問(wèn)題：樣本數(shù)量N無(wú)窮大是，估計(jì)的概率函數(shù)是否收斂到真實(shí)值？實(shí)際中，越精確，要求：實(shí)際中，N是有限的：當(dāng)時(shí)，絕大部分區(qū)間沒(méi)有樣本：如果僥幸

4、存在一個(gè)樣本，則：11PPT課件概率密度估計(jì)理論結(jié)果：設(shè)有一系列包含x 的區(qū)域R1，R2，,Rn,，對(duì)R1采用1個(gè)樣本進(jìn)行估計(jì)，對(duì)R2用2 個(gè)， Rn包含kn個(gè)樣本。Vn為Rn的體積。為p(x)的第n次估計(jì)12PPT課件概率密度估計(jì)如果要求能夠收斂到p(x)，那么必須滿足：選擇Vn選擇kn13PPT課件概率密度估計(jì)兩種選擇方法：14PPT課件主要內(nèi)容概率密度估計(jì)Parzen窗估計(jì)k-NN估計(jì)最近鄰分類器（NN）k-近鄰分類器（k-NN）15PPT課件Parzen窗估計(jì)定義窗函數(shù)：假設(shè)Rn是一個(gè)d維的超立方體。令hn為超立方體一條邊的長(zhǎng)度，則體積：立方體窗函數(shù)為：中心在原點(diǎn)的單位超立方體16PP

5、T課件Parzen窗估計(jì)X處的密度估計(jì)為：落入以X為中心的立方體區(qū)域的樣本數(shù)為：可以驗(yàn)證：17PPT課件窗函數(shù)的要求Parzen窗估計(jì)過(guò)程是一個(gè)內(nèi)插過(guò)程，樣本xi距離x越近，對(duì)概率密度估計(jì)的貢獻(xiàn)越大，越遠(yuǎn)貢獻(xiàn)越小。只要滿足如下條件，就可以作為窗函數(shù)：18PPT課件窗函數(shù)的形式 方窗函數(shù)指數(shù)窗函數(shù)正態(tài)窗函數(shù)其中：19PPT課件窗口寬度的影響Parzen估計(jì)的性能與窗寬參數(shù)hn緊密相關(guān)當(dāng)hn較大時(shí)，x和中心xi距離大小的影響程度變?nèi)?，估?jì)的p(x)較為平滑，分辨率較差。當(dāng)hn較小時(shí)，x和中心xi距離大小的影響程度變強(qiáng)，估計(jì)的p(x)較為尖銳，分辨率較好。20PPT課件窗口寬度的影響21PPT課件窗

6、函數(shù)密度估計(jì)值5個(gè)樣本的Parzen窗估計(jì)：22PPT課件漸近收斂性Parzen窗密度估計(jì)的漸近收斂性： 無(wú)偏性： 一致性：當(dāng) 時(shí)，23PPT課件0123456x6x5x3x1x2x4x 例：對(duì)于一個(gè)二類（ 1 ，2 ）識(shí)別問(wèn)題，隨機(jī)抽取1類的6個(gè)樣本X=(x1，x2，. x6) 1=(x1，x2，. x6) =(x1=3.2，x2=3.6，x3=3，x4=6，x5=2.5，x6=1.1) 估計(jì)P(x|1)即PN(x) 解：選正態(tài)窗函數(shù)24PPT課件 x是一維的上式用圖形表示是6個(gè)分別以3.2，3.6，3，6，2.5，1.1為中心的正態(tài)曲線，而PN(x)則是這些曲線之和。代入：由圖看出，每個(gè)樣

7、本對(duì)估計(jì)的貢獻(xiàn)與樣本間的距離有關(guān)，樣本越多，PN(x)越準(zhǔn)確。25PPT課件例：設(shè)待估計(jì)的P(x)是個(gè)均值為0，方差為1的正態(tài)密度函數(shù)。若隨機(jī)地抽取X樣本中的1個(gè)、 16個(gè)、 256個(gè)作為學(xué)習(xí)樣本xi,試用窗口法估計(jì)PN(x)。解：設(shè)窗口函數(shù)為正態(tài)的， 1，0hN:窗長(zhǎng)度，N為樣本數(shù)，h1為選定可調(diào)節(jié)的參數(shù)。26PPT課件用 窗法估計(jì)單一正態(tài)分布的實(shí)驗(yàn)N=N=256N=16N=127PPT課件由圖看出, PN(x)隨N, h1的變化情況 當(dāng)N1時(shí)， PN(x)是一個(gè)以第一個(gè)樣本為中心的正態(tài)曲線，與窗函數(shù)差不多。 當(dāng)N16及N=256時(shí) h10.25 曲線起伏很大，噪聲大 h11 起伏減小 h1

8、4 曲線平坦 當(dāng)N時(shí)， PN(x)收斂于一平滑的正態(tài)曲線， 估計(jì)曲線較好。28PPT課件例：待估的密度函數(shù)為二項(xiàng)分布解：此為多峰情況的估計(jì)設(shè)窗函數(shù)為正態(tài)解：此為多峰情況的估計(jì)設(shè)窗函數(shù)為正態(tài)x-2.5-210.2502P(x)-2.5x-20 x2x為其它29PPT課件N=N=256N=16N=1用 窗法估計(jì)兩個(gè)均勻分布的實(shí)驗(yàn)30PPT課件當(dāng)N=1、16、256、 時(shí)的PN(x)估計(jì)如圖所示 當(dāng)N1時(shí)， PN(x) 實(shí)際是窗函數(shù)。 當(dāng)N16及N=256時(shí) h10.25 曲線起伏大 h11 曲線起伏減小 h14 曲線平坦 當(dāng)N時(shí)，曲線較好。31PPT課件Parzen窗估計(jì)優(yōu)點(diǎn)由前面的例子可以看出，

9、 Parzen窗估計(jì)的優(yōu)點(diǎn)是應(yīng)用的普遍性。對(duì)規(guī)則分布，非規(guī)則分布，單鋒或多峰分布都可用此法進(jìn)行密度估計(jì)。可以獲得較為光滑且分辨率較高的密度估計(jì)，實(shí)現(xiàn)了光滑性和分辨率之間的一個(gè)較好平衡。缺點(diǎn)要求樣本足夠多，才能有較好的估計(jì)。因此使計(jì)算量，存儲(chǔ)量增大。窗寬在整個(gè)樣本空間固定不變，難以獲得區(qū)域自適應(yīng)的密度估計(jì)。32PPT課件識(shí)別方法保存每個(gè)類別所有的訓(xùn)練樣本；選擇窗函數(shù)的形式，根據(jù)訓(xùn)練樣本數(shù)n選擇窗函數(shù)的h寬度；識(shí)別時(shí)，利用每個(gè)類別的訓(xùn)練樣本計(jì)算待識(shí)別樣本x的類條件概率密度：采用Bayes判別準(zhǔn)則進(jìn)行分類。33PPT課件例子： 基于Parzen估計(jì)的Bayesian分類器較小較大34PPT課件主要內(nèi)

10、容概率密度估計(jì)Parzen窗估計(jì)Kn近鄰估計(jì)最近鄰分類器（NN）k-近鄰分類器（k-NN）35PPT課件Kn近鄰估計(jì)在Parzen窗估計(jì)中，存在一個(gè)問(wèn)題：對(duì)hn的選擇。若hn選太小，則大部分體積將是空的（即不包含樣本），從而使Pn(x)估計(jì)不穩(wěn)定。若hn選太大，則Pn(x)估計(jì)較平坦，反映不出總體分布的變化Kn近鄰法的思想：固定樣本數(shù)量Kn ，調(diào)整區(qū)域體積大小Vn，直至有Kn個(gè)樣本落入?yún)^(qū)域中36PPT課件Kn近鄰估計(jì)Kn近鄰密度估計(jì)：固定樣本數(shù)為，在附近選取與之最近的個(gè)樣本，計(jì)算該個(gè)樣本分布的最小體積在X處的概率密度估計(jì)值為：37PPT課件漸近收斂的條件漸近收斂的充要條件為：通常選擇：38PP

11、T課件Kn近鄰估計(jì)例子：39PPT課件例子： Parzen windowskn-nearest-neighbor斜率不連續(xù)當(dāng)n值為有限值時(shí)Kn近鄰估計(jì)十分粗糙40PPT課件例子：Parzen windowskn-nearest-neighbor41PPT課件Kn近鄰估計(jì)Kn近鄰后驗(yàn)概率估計(jì)： 給定i.i.d.樣本集 ，共 類。把一個(gè)體積V放在x周圍，能夠包含進(jìn)k個(gè)樣本，其中有 ki個(gè)樣本屬于第i類。那么聯(lián)合概率密度的估計(jì)為：后驗(yàn)概率： 42PPT課件Kn近鄰估計(jì)例子X(jué)屬于第i類的后驗(yàn)概率就是體積中標(biāo)記為第i類的樣本個(gè)數(shù)與體積中全部樣本點(diǎn)個(gè)數(shù)的比值。為了達(dá)到最小誤差率，選擇比值最大的那個(gè)類別作為

12、判決結(jié)果。如果樣本足夠多、體積足夠小，這樣的方法得到的結(jié)果是比較準(zhǔn)確的！43PPT課件主要內(nèi)容概率密度估計(jì)Parzen窗估計(jì)k-NN估計(jì)最近鄰分類器（NN） k-近鄰分類器（k-NN）44PPT課件最近鄰分類器(NN)假設(shè)i.i.d.樣本集對(duì)于樣本 ，NN采用如下的決策：相當(dāng)于采用 近鄰方法估計(jì)后驗(yàn)概率，然后采用最大后驗(yàn)概率決策。分類一個(gè)樣本的計(jì)算復(fù)雜度： （采用歐氏距離）45PPT課件最近鄰分類器樣本 x = (0.10, 0.25) 的類別？Training ExamplesLabelsDistance(0.15, 0.35)(0.10, 0.28)(0.09, 0.30)(0.12, 0

13、.20)12520.1180.0300.0510.05446PPT課件最近鄰分類器決策邊界： Voronoi網(wǎng)格NN分類規(guī)則將特征空間分成許多Voronoi網(wǎng)格（ Voronoi網(wǎng)格：由一組由連接兩鄰點(diǎn)直線的垂直平分線組成的連續(xù)多邊形組成 ） 47PPT課件最近鄰分類器決策邊界 在一個(gè)Voronoi網(wǎng)格中，每一個(gè)點(diǎn)到該 Voronoi網(wǎng)格原型的距離小于到其它所有訓(xùn)練樣本點(diǎn)的距離。 NN分類器將該Voronoi網(wǎng)格中的點(diǎn)標(biāo)識(shí)為與該原型同類。48PPT課件最近鄰分類器決策邊界：在NN分類器中，分類邊界對(duì)于分類新樣本是足夠的。但是計(jì)算或者存儲(chǔ)分類邊界是非常困難的目前已經(jīng)提出許多算法來(lái)存儲(chǔ)簡(jiǎn)化后的樣本

14、集，而不是整個(gè)樣本集，使得分類邊界不變。49PPT課件NN分類器的漸近誤差界若是n個(gè)樣本時(shí)的誤差率，并且：為最小Bayesian錯(cuò)誤率，c為類別數(shù)?？梢宰C明：50PPT課件NN分類器的漸近誤差界假設(shè)能夠得到無(wú)限多的訓(xùn)練樣本和使用任意復(fù)雜的分量規(guī)則，我們至多只能使誤差率降低一半。也就是說(shuō)，分類信息中的一半信息是由最鄰近點(diǎn)提供的！51PPT課件最近鄰分類器當(dāng)樣本有限的情況下，最近鄰分類器的分類效果如何？ 不理想！隨著樣本數(shù)量的增加，分類器收斂到漸近值的速度如何？可能會(huì)任意慢，而且誤差未必會(huì)隨著n的增加單調(diào)遞減！52PPT課件k-近鄰分類器（k-NN）假設(shè)i.i.d.樣本集對(duì)于樣本 ，k-NN采用如

15、下的決策：搜索與 最近的 個(gè)近鄰，如果 個(gè)近鄰中屬于 類的樣本最多，則判決 屬于 原理：相當(dāng)于采用 近鄰方法估計(jì)后驗(yàn)概率，然后采用最大后驗(yàn)概率決策。分類一個(gè)樣本的計(jì)算復(fù)雜度： （采用歐氏距離）53PPT課件k-近鄰分類器從測(cè)試樣本x開始生長(zhǎng)，不斷擴(kuò)大區(qū)域，直至包含進(jìn)k個(gè)訓(xùn)練樣本；把測(cè)試樣本x的類別歸為與之最近的k個(gè)訓(xùn)練樣本中出現(xiàn)頻率最大的類別。54PPT課件例：k = 3 (odd value) and x = (0.10, 0.25)t選擇 k-NN to x (0.10, 0.28, 2); (0.12, 0.20, 2); (0.09, 0.30,5) X屬于 2。PrototypesL

16、abels(0.15, 0.35)(0.10, 0.28)(0.09, 0.30)(0.12, 0.20)125255PPT課件k-近鄰分類器決策面： 分段線性超平面 每一個(gè)超平面對(duì)應(yīng)著最近兩點(diǎn)的中垂面。56PPT課件k-近鄰分類器k-NN分類器的誤差率在樣本數(shù)無(wú)窮大時(shí)趨向于Bayesian最小錯(cuò)誤率！57PPT課件k-NN分類器 近鄰分類器 假設(shè)i.i.d.樣本集 對(duì)于樣本 ， -NN采用如下的決策： 搜索與 最近的 個(gè)近鄰，如果 個(gè)近鄰中屬于 類的樣本最多，為 個(gè)，則判決 屬于 ，否則拒識(shí)。 58PPT課件k-NN分類器k-NN分類器的優(yōu)點(diǎn)： 原理和實(shí)現(xiàn)簡(jiǎn)單，特別適用于大類別問(wèn)題。 當(dāng)訓(xùn)練

17、樣本數(shù)較多時(shí)，誤差界小于2倍的Bayesian最小錯(cuò)誤率。59PPT課件k-NN分類器k-NN分類器的缺點(diǎn)：由于訓(xùn)練樣本數(shù)有限，k-NN估計(jì)的后驗(yàn)概率往往并不精確，從而導(dǎo)致分類錯(cuò)誤率遠(yuǎn)遠(yuǎn)大于Bayesian最小錯(cuò)誤率。搜索近鄰需要遍歷每一個(gè)樣本，計(jì)算復(fù)雜度較大。需要存儲(chǔ)所有樣本。受噪聲和距離測(cè)度的選擇影響較大。60PPT課件距離度量距離度量應(yīng)滿足如下三個(gè)性質(zhì)：非負(fù)性：自反性： 當(dāng)且僅當(dāng)對(duì)稱性：三角不等式：距離測(cè)度的選取原則：需要精心選擇類內(nèi)變化平緩，類間變化劇烈的距離測(cè)度！61PPT課件常用的距離函數(shù)歐幾里德距離：(Eucidean Distance) 曼哈頓距離：(Manhattan Dis

18、tance)62PPT課件常用的距離函數(shù)明氏距離：(Minkowski Distance)馬氏距離：(Mahalanobis Distance)63PPT課件常用的距離函數(shù)角度相似函數(shù)：(Angle Distance) 海明距離：(Hamming Distance) x和y為2值特征矢量： D(x,y)定義為x,y中使得不等式 成立的i的個(gè)數(shù)。64PPT課件最近鄰分類器的簡(jiǎn)化最近鄰分類器的簡(jiǎn)化方法可以分為三種： 部分距離法； 預(yù)分類法； 需要存儲(chǔ)所有樣本問(wèn)題：濃縮、剪枝。65PPT課件部分距離法定義：Dr(x,y)是r的單調(diào)不減函數(shù)。令Dmin為當(dāng)前搜索到的最近鄰距離，當(dāng)待識(shí)別樣本x與某個(gè)訓(xùn)練樣本xi的部分距離Dr(x,xi)大于 Dmin時(shí)， Dd(x,xi)一定要大于Dmin ，所以xi一定不是最近鄰，不需要繼續(xù)計(jì)算Dd(x,xi) 。66PPT課件預(yù)分類（搜索樹）67PPT課件預(yù)分類（搜索樹）在特征空間中首先找到m個(gè)有代表性的樣本點(diǎn)，用這些點(diǎn)代表一部分訓(xùn)練樣本；待識(shí)別模式x首先與這些代表點(diǎn)計(jì)算距離，找到一個(gè)最近鄰，然后在這個(gè)最近鄰代表的樣本點(diǎn)中尋找實(shí)際的最近鄰點(diǎn)。這種方法是一個(gè)次優(yōu)的