非參數(shù)估計(完整).ppt

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

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

3、是連續(xù)的，且R足夠小使得p(x)在R內(nèi)幾乎沒有變化。 令R是包含樣本點x的一個區(qū)域，其體積為V，設(shè)有N個訓(xùn)練樣本，其中有k落在區(qū)域R中，則可對概率密度作出一個估計：,對p(x) 在小區(qū)域內(nèi)的平均值的估計,概率密度估計,當樣本數(shù)量N固定時，體積V的大小對估計的效果影響很大。 過大則平滑過多，不夠精確； 過小則可能導(dǎo)致在此區(qū)域內(nèi)無樣本點，k=0。 此方法的有效性取決于樣本數(shù)量的多少，以及區(qū)域體積選擇的合適。,概率密度估計,收斂性問題：樣本數(shù)量N無窮大是，估計的概率函數(shù)是否收斂到真實值？,概率密度估計,理論結(jié)果：,設(shè)有一系列包含x 的區(qū)域R1，R2，,Rn,，對R1采用1個樣本進行估計，對R2用2

4、個， Rn包含kn個樣本。Vn為Rn的體積。,為p(x)的第n次估計,概率密度估計,如果要求,能夠收斂到p(x)，那么必須滿足：,選擇Vn,選擇kn,概率密度估計,兩種選擇方法：,主要內(nèi)容,概率密度估計 Parzen窗估計 k-NN估計 最近鄰分類器（NN） k-近鄰分類器（k-NN）,Parzen窗估計,定義窗函數(shù)：假設(shè)Rn是一個d維的超立方體。令hn為超立方體一條邊的長度，則體積：,立方體窗函數(shù)為：,中心在原點的單位超立方體,Parzen窗估計,X處的密度估計為：,落入以X為中心的立方體區(qū)域的樣本數(shù)為：,可以驗證：,窗函數(shù)的要求,Parzen窗估計過程是一個內(nèi)插過程，樣本xi距離x越近，對

5、概率密度估計的貢獻越大，越遠貢獻越小。 只要滿足如下條件，就可以作為窗函數(shù)：,窗函數(shù)的形式,方窗函數(shù),指數(shù)窗函數(shù),正態(tài)窗函數(shù),其中：,窗口寬度的影響,Parzen估計的性能與窗寬參數(shù)hn緊密相關(guān) 當hn較大時，x和中心xi距離大小的影響程度變?nèi)?，估計的p(x)較為平滑，分辨率較差。 當hn較小時，x和中心xi距離大小的影響程度變強，估計的p(x)較為尖銳，分辨率較好。,窗口寬度的影響,窗函數(shù),密度估計值,5個樣本的Parzen窗估計：,漸近收斂性,Parzen窗密度估計的漸近收斂性： 無偏性： 一致性：,當 時，, x是一維的,上式用圖形表示是6個分別以3.2，3.6，3，6，2.5，1.1為

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

7、N時， PN(x)收斂于一平滑的正態(tài)曲線， 估計曲線較好。,例：待估的密度函數(shù)為二項分布 解：此為多峰情況的估計 設(shè)窗函數(shù)為正態(tài) 解：此為多峰情況的估計 設(shè)窗函數(shù)為正態(tài),x,-2.5,-2,1,0.25,0,2,P(x),-2.5x-2,0x2,x為其它,當N=1、16、256、 時的PN(x)估計如圖所示 當N1時， PN(x) 實際是窗函數(shù)。 當N16及N=256時 h10.25 曲線起伏大 h11 曲線起伏減小 h14 曲線平坦 當N時，曲線較好。,Parzen窗估計,優(yōu)點 由前面的例子可以看出， Parzen窗估計的優(yōu)點是應(yīng)用的普遍性。對規(guī)則分布，非規(guī)則分布，單鋒或多峰分布都可用此法進

8、行密度估計。 可以獲得較為光滑且分辨率較高的密度估計，實現(xiàn)了光滑性和分辨率之間的一個較好平衡。 缺點 要求樣本足夠多，才能有較好的估計。因此使計算量，存儲量增大。 窗寬在整個樣本空間固定不變，難以獲得區(qū)域自適應(yīng)的密度估計。,識別方法,保存每個類別所有的訓(xùn)練樣本； 選擇窗函數(shù)的形式，根據(jù)訓(xùn)練樣本數(shù)n選擇窗函數(shù)的h寬度； 識別時，利用每個類別的訓(xùn)練樣本計算待識別樣本x的類條件概率密度： 采用Bayes判別準則進行分類。,例子： 基于Parzen估計的Bayesian分類器,較小,較大,主要內(nèi)容,概率密度估計 Parzen窗估計 Kn近鄰估計 最近鄰分類器（NN） k-近鄰分類器（k-NN）,Kn近

9、鄰估計,在Parzen窗估計中，存在一個問題：對hn的選擇。 若hn選太小，則大部分體積將是空的（即不包含樣本），從而使Pn(x)估計不穩(wěn)定。 若hn選太大，則Pn(x)估計較平坦，反映不出總體分布的變化 Kn近鄰法的思想：固定樣本數(shù)量Kn ，調(diào)整區(qū)域體積大小Vn，直至有Kn個樣本落入?yún)^(qū)域中,Kn近鄰估計,Kn近鄰密度估計：,在X處的概率密度估計值為：,漸近收斂的條件,漸近收斂的充要條件為：,通常選擇：,Kn近鄰估計,例子：,例子：,Parzen windows,kn-nearest-neighbor,斜率不連續(xù),當n值為有限值時Kn近鄰估計十分粗糙,例子：,Parzen windows,kn

10、-nearest-neighbor,Kn近鄰估計,Kn近鄰后驗概率估計： 給定i.i.d.樣本集 ，共 類。把一個體積V放在x周圍，能夠包含進k個樣本，其中有 ki個樣本屬于第i類。那么聯(lián)合概率密度的估計為： 后驗概率：,Kn近鄰估計,例子,X屬于第i類的后驗概率就是體積中標記為第i類的樣本個數(shù)與體積中全部樣本點個數(shù)的比值。 為了達到最小誤差率，選擇比值最大的那個類別作為判決結(jié)果。 如果樣本足夠多、體積足夠小，這樣的方法得到的結(jié)果是比較準確的！,主要內(nèi)容,概率密度估計 Parzen窗估計 k-NN估計 最近鄰分類器（NN） k-近鄰分類器（k-NN）,最近鄰分類器(NN),假設(shè)i.i.d.樣本

11、集 對于樣本 ，NN采用如下的決策： 相當于采用 近鄰方法估計后驗概率，然后采用最大后驗概率決策。 分類一個樣本的計算復(fù)雜度： （采用歐氏距離）,最近鄰分類器,樣本 x = (0.10, 0.25) 的類別？,最近鄰分類器,決策邊界： Voronoi網(wǎng)格,NN分類規(guī)則將特征空間分成許多Voronoi網(wǎng)格 （ Voronoi網(wǎng)格：由一組由連接兩鄰點直線的垂直平分線組成的連續(xù)多邊形組成 ）,最近鄰分類器,決策邊界 在一個Voronoi網(wǎng)格中，每一個點到該 Voronoi網(wǎng)格原型的距離小于到其它所有訓(xùn)練樣本點的距離。 NN分類器將該Voronoi網(wǎng)格中的點標識為與該原型同類。,最近鄰分類器,決策邊界

12、： 在NN分類器中，分類邊界對于分類新樣本是足夠的。 但是計算或者存儲分類邊界是非常困難的 目前已經(jīng)提出許多算法來存儲簡化后的樣本集，而不是整個樣本集，使得分類邊界不變。,NN分類器的漸近誤差界,NN分類器的漸近誤差界,假設(shè)能夠得到無限多的訓(xùn)練樣本和使用任意復(fù)雜的分量規(guī)則，我們至多只能使誤差率降低一半。 也就是說，分類信息中的一半信息是由最鄰近點提供的！,最近鄰分類器,當樣本有限的情況下，最近鄰分類器的分類效果如何？ 不理想！ 隨著樣本數(shù)量的增加，分類器收斂到漸近值的速度如何？ 可能會任意慢，而且誤差未必會隨著n的增加單調(diào)遞減！,k-近鄰分類器（k-NN）,假設(shè)i.i.d.樣本集 對于樣本 ，

13、k-NN采用如下的決策： 搜索與 最近的 個近鄰，如果 個近鄰中屬于 類的樣本最多，則判決 屬于 原理：相當于采用 近鄰方法估計后驗概率，然后采用最大后驗概率決策。 分類一個樣本的計算復(fù)雜度： （采用歐氏距離）,k-近鄰分類器,從測試樣本x開始生長，不斷擴大區(qū)域，直至包含進k個訓(xùn)練樣本； 把測試樣本x的類別歸為與之最近的k個訓(xùn)練樣本中出現(xiàn)頻率最大的類別。,例： 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。,k-近鄰分類器,決

14、策面： 分段線性超平面 每一個超平面對應(yīng)著最近兩點的中垂面。,k-近鄰分類器,k-NN分類器的誤差率在樣本數(shù)無窮大時趨向于Bayesian最小錯誤率！,k-NN分類器,近鄰分類器 假設(shè)i.i.d.樣本集 對于樣本 ， -NN采用如下的決策： 搜索與 最近的 個近鄰，如果 個近鄰中屬于 類的樣本最多，為 個，則判決 屬于 ，否則拒識。,k-NN分類器,k-NN分類器的優(yōu)點： 原理和實現(xiàn)簡單，特別適用于大類別問題。 當訓(xùn)練樣本數(shù)較多時，誤差界小于2倍的Bayesian最小錯誤率。,k-NN分類器,k-NN分類器的缺點： 由于訓(xùn)練樣本數(shù)有限，k-NN估計的后驗概率往往并不精確，從而導(dǎo)致分類錯誤率遠遠

15、大于Bayesian最小錯誤率。 搜索近鄰需要遍歷每一個樣本，計算復(fù)雜度較大。 需要存儲所有樣本。 受噪聲和距離測度的選擇影響較大。,距離度量,距離度量應(yīng)滿足如下三個性質(zhì)： 非負性： 自反性： 當且僅當 對稱性： 三角不等式：,距離測度的選取原則：需要精心選擇類內(nèi)變化平緩，類間變化劇烈的距離測度！,常用的距離函數(shù),歐幾里德距離：(Eucidean Distance),曼哈頓距離：(Manhattan Distance),常用的距離函數(shù),明氏距離：(Minkowski Distance),馬氏距離：(Mahalanobis Distance),常用的距離函數(shù),角度相似函數(shù)：(Angle Dist

16、ance),海明距離：(Hamming Distance),x和y為2值特征矢量：,D(x,y)定義為x,y中使得不等式 成立的i的個數(shù)。,最近鄰分類器的簡化,最近鄰分類器的簡化方法可以分為三種： 部分距離法； 預(yù)分類法； 需要存儲所有樣本問題：濃縮、剪枝。,部分距離法,定義：,Dr(x,y)是r的單調(diào)不減函數(shù)。令Dmin為當前搜索到的最近鄰距離，當待識別樣本x與某個訓(xùn)練樣本xi的部分距離Dr(x,xi)大于 Dmin時， Dd(x,xi)一定要大于Dmin ，所以xi一定不是最近鄰，不需要繼續(xù)計算Dd(x,xi) 。,預(yù)分類（搜索樹）,預(yù)分類（搜索樹）,在特征空間中首先找到m個有代表性的樣本點，用這些點代表一部分訓(xùn)練樣本； 待識別模式x首先與這些代表點計算距離，找到一個最近鄰，然后在這個最近鄰代表的樣本點中尋找實際的最近鄰點。 這種方法是一個次優(yōu)的搜索算法。,濃縮、剪枝,濃縮(C