非參數(shù)估計課件

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

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

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

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

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

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

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

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

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

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

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

12、判決結(jié)果。如果樣本足夠多、體積足夠小，這樣的方法得到的結(jié)果是比較準確的！43PPT課件主要內(nèi)容概率密度估計Parzen窗估計k-NN估計最近鄰分類器（NN） k-近鄰分類器（k-NN）44PPT課件最近鄰分類器(NN)假設(shè)i.i.d.樣本集對于樣本 ，NN采用如下的決策：相當(dāng)于采用 近鄰方法估計后驗概率，然后采用最大后驗概率決策。分類一個樣本的計算復(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)格：由一組由連接兩鄰點直線的垂直平分線組成的連續(xù)多邊形組成 ） 47PPT課件最近鄰分類器決策邊界 在一個Voronoi網(wǎng)格中，每一個點到該 Voronoi網(wǎng)格原型的距離小于到其它所有訓(xùn)練樣本點的距離。 NN分類器將該Voronoi網(wǎng)格中的點標(biāo)識為與該原型同類。48PPT課件最近鄰分類器決策邊界：在NN分類器中，分類邊界對于分類新樣本是足夠的。但是計算或者存儲分類邊界是非常困難的目前已經(jīng)提出許多算法來存儲簡化后的樣本

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

15、下的決策：搜索與 最近的 個近鄰，如果 個近鄰中屬于 類的樣本最多，則判決 屬于 原理：相當(dāng)于采用 近鄰方法估計后驗概率，然后采用最大后驗概率決策。分類一個樣本的計算復(fù)雜度： （采用歐氏距離）53PPT課件k-近鄰分類器從測試樣本x開始生長，不斷擴大區(qū)域，直至包含進k個訓(xùn)練樣本；把測試樣本x的類別歸為與之最近的k個訓(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-近鄰分類器決策面： 分段線性超平面 每一個超平面對應(yīng)著最近兩點的中垂面。56PPT課件k-近鄰分類器k-NN分類器的誤差率在樣本數(shù)無窮大時趨向于Bayesian最小錯誤率！57PPT課件k-NN分類器 近鄰分類器 假設(shè)i.i.d.樣本集 對于樣本 ， -NN采用如下的決策： 搜索與 最近的 個近鄰，如果 個近鄰中屬于 類的樣本最多，為 個，則判決 屬于 ，否則拒識。 58PPT課件k-NN分類器k-NN分類器的優(yōu)點： 原理和實現(xiàn)簡單，特別適用于大類別問題。 當(dāng)訓(xùn)練

17、樣本數(shù)較多時，誤差界小于2倍的Bayesian最小錯誤率。59PPT課件k-NN分類器k-NN分類器的缺點：由于訓(xùn)練樣本數(shù)有限，k-NN估計的后驗概率往往并不精確，從而導(dǎo)致分類錯誤率遠遠大于Bayesian最小錯誤率。搜索近鄰需要遍歷每一個樣本，計算復(fù)雜度較大。需要存儲所有樣本。受噪聲和距離測度的選擇影響較大。60PPT課件距離度量距離度量應(yīng)滿足如下三個性質(zhì)：非負性：自反性： 當(dāng)且僅當(dāng)對稱性：三角不等式：距離測度的選取原則：需要精心選擇類內(nèi)變化平緩，類間變化劇烈的距離測度！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的個數(shù)。64PPT課件最近鄰分類器的簡化最近鄰分類器的簡化方法可以分為三種： 部分距離法； 預(yù)分類法； 需要存儲所有樣本問題：濃縮、剪枝。65PPT課件部分距離法定義：Dr(x,y)是r的單調(diào)不減函數(shù)。令Dmin為當(dāng)前搜索到的最近鄰距離，當(dāng)待識別樣本x與某個訓(xùn)練樣本xi的部分距離Dr(x,xi)大于 Dmin時， Dd(x,xi)一定要大于Dmin ，所以xi一定不是最近鄰，不需要繼續(xù)計算Dd(x,xi) 。66PPT課件預(yù)分類（搜索樹）67PPT課件預(yù)分類（搜索樹）在特征空間中首先找到m個有代表性的樣本點，用這些點代表一部分訓(xùn)練樣本；待識別模式x首先與這些代表點計算距離，找到一個最近鄰，然后在這個最近鄰代表的樣本點中尋找實際的最近鄰點。這種方法是一個次優(yōu)的