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

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

1.把x的每個分量分成k個等間隔小窗，（x∈Ed

，則形成kd

個小艙）

2.統(tǒng)計落入各個小艙內(nèi)的樣本數(shù)qi3.相應(yīng)小艙的概率密度為：qi/(NV)

（N：樣本總數(shù)，V：小艙體積）52021/5/9概率密度估計直方圖的例子62021/5/9概率密度估計非參數(shù)概率密度估計的核心思路：一個向量x落在區(qū)域R中的概率P為：因此，可以通過統(tǒng)計概率P來估計概率密度函數(shù)p(x)72021/5/9概率密度估計假設(shè)N個樣本的集合是根據(jù)概率密度函數(shù)為p(x)的分布獨立抽取得到的。那么，有k個樣本落在區(qū)域R中的概率服從二項式定理：k的期望值為：對P的估計：當(dāng)時，估計是非常精確的82021/5/9概率密度估計假設(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)的平均值的估計92021/5/9概率密度估計當(dāng)樣本數(shù)量N固定時，體積V的大小對估計的效果影響很大。過大則平滑過多，不夠精確；過小則可能導(dǎo)致在此區(qū)域內(nèi)無樣本點，k=0。此方法的有效性取決于樣本數(shù)量的多少，以及區(qū)域體積選擇的合適。102021/5/9概率密度估計收斂性問題：樣本數(shù)量N無窮大是，估計的概率函數(shù)是否收斂到真實值？實際中，越精確，要求：實際中，N是有限的：當(dāng)時，絕大部分區(qū)間沒有樣本：如果僥幸存在一個樣本，則：112021/5/9概率密度估計理論結(jié)果：設(shè)有一系列包含x的區(qū)域R1，R2，…,Rn,…，對R1采用1個樣本進(jìn)行估計，對R2用2個，…，Rn包含kn個樣本。Vn為Rn的體積。為p(x)的第n次估計122021/5/9概率密度估計如果要求能夠收斂到p(x)，那么必須滿足：選擇Vn選擇kn132021/5/9概率密度估計兩種選擇方法：142021/5/9主要內(nèi)容概率密度估計Parzen窗估計k-NN估計最近鄰分類器（NN）k-近鄰分類器（k-NN）152021/5/9Parzen窗估計定義窗函數(shù)：假設(shè)Rn是一個d維的超立方體。令hn為超立方體一條邊的長度，則體積：立方體窗函數(shù)為：中心在原點的單位超立方體162021/5/9Parzen窗估計X處的密度估計為：落入以X為中心的立方體區(qū)域的樣本數(shù)為：可以驗證：172021/5/9窗函數(shù)的要求Parzen窗估計過程是一個內(nèi)插過程，樣本xi距離x越近，對概率密度估計的貢獻(xiàn)越大，越遠(yuǎn)貢獻(xiàn)越小。只要滿足如下條件，就可以作為窗函數(shù)：182021/5/9窗函數(shù)的形式

方窗函數(shù)指數(shù)窗函數(shù)正態(tài)窗函數(shù)其中：192021/5/9窗口寬度的影響Parzen估計的性能與窗寬參數(shù)hn緊密相關(guān)當(dāng)hn較大時，x和中心xi距離大小的影響程度變?nèi)酰烙嫷膒(x)較為平滑，分辨率較差。當(dāng)hn較小時，x和中心xi距離大小的影響程度變強，估計的p(x)較為尖銳，分辨率較好。202021/5/9窗口寬度的影響212021/5/9窗函數(shù)密度估計值5個樣本的Parzen窗估計：222021/5/9漸近收斂性Parzen窗密度估計的漸近收斂性：無偏性：一致性：當(dāng)時，232021/5/90123456x6x5x3x1x2x4x

例：對于一個二類（ω1

，ω2

）識別問題，隨機(jī)抽取ω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ù)242021/5/9∵x是一維的上式用圖形表示是6個分別以3.2，3.6，3，6，2.5，1.1為中心的正態(tài)曲線，而PN(x)則是這些曲線之和。代入：由圖看出，每個樣本對估計的貢獻(xiàn)與樣本間的距離有關(guān)，樣本越多，PN(x)越準(zhǔn)確。252021/5/9例：設(shè)待估計的P(x)是個均值為0，方差為1的正態(tài)密度函數(shù)。若隨機(jī)地抽取X樣本中的1個、16個、256個作為學(xué)習(xí)樣本xi,試用窗口法估計PN(x)。解：設(shè)窗口函數(shù)為正態(tài)的，σ＝1，μ＝0hN:窗長度，N為樣本數(shù)，h1為選定可調(diào)節(jié)的參數(shù)。262021/5/9用窗法估計單一正態(tài)分布的實驗N=∞N=256N=16N=1272021/5/9由圖看出,PN(x)隨N,h1的變化情況①當(dāng)N＝1時，PN(x)是一個以第一個樣本為中心的正態(tài)曲線，與窗函數(shù)差不多。②當(dāng)N＝16及N=256時

h1＝0.25曲線起伏很大，噪聲大

h1＝1起伏減小

h1＝4曲線平坦

③當(dāng)N→∞時，PN(x)收斂于一平滑的正態(tài)曲線，估計曲線較好。282021/5/9例：待估的密度函數(shù)為二項分布解：此為多峰情況的估計設(shè)窗函數(shù)為正態(tài)解：此為多峰情況的估計設(shè)窗函數(shù)為正態(tài)x-2.5-210.2502P(x)-2.5<x<-20<x<2x為其它292021/5/9N=∞N=256N=16N=1用窗法估計兩個均勻分布的實驗302021/5/9當(dāng)N=1、16、256、∞時的PN(x)估計如圖所示①當(dāng)N＝1時，PN(x)實際是窗函數(shù)。②當(dāng)N＝16及N=256時

h1＝0.25曲線起伏大

h1＝1曲線起伏減小

h1＝4曲線平坦

③當(dāng)N→∞時，曲線較好。312021/5/9Parzen窗估計優(yōu)點由前面的例子可以看出，Parzen窗估計的優(yōu)點是應(yīng)用的普遍性。對規(guī)則分布，非規(guī)則分布，單鋒或多峰分布都可用此法進(jìn)行密度估計?？梢垣@得較為光滑且分辨率較高的密度估計，實現(xiàn)了光滑性和分辨率之間的一個較好平衡。缺點要求樣本足夠多，才能有較好的估計。因此使計算量，存儲量增大。窗寬在整個樣本空間固定不變，難以獲得區(qū)域自適應(yīng)的密度估計。322021/5/9識別方法保存每個類別所有的訓(xùn)練樣本；選擇窗函數(shù)的形式，根據(jù)訓(xùn)練樣本數(shù)n選擇窗函數(shù)的h寬度；識別時，利用每個類別的訓(xùn)練樣本計算待識別樣本x的類條件概率密度：采用Bayes判別準(zhǔn)則進(jìn)行分類。332021/5/9例子：基于Parzen估計的Bayesian分類器較小較大342021/5/9主要內(nèi)容概率密度估計Parzen窗估計Kn近鄰估計最近鄰分類器（NN）k-近鄰分類器（k-NN）352021/5/9Kn近鄰估計在Parzen窗估計中，存在一個問題：對hn的選擇。若hn選太小，則大部分體積將是空的（即不包含樣本），從而使Pn(x)估計不穩(wěn)定。若hn選太大，則Pn(x)估計較平坦，反映不出總體分布的變化Kn近鄰法的思想：固定樣本數(shù)量Kn

，調(diào)整區(qū)域體積大小Vn，直至有Kn個樣本落入?yún)^(qū)域中362021/5/9Kn近鄰估計Kn近鄰密度估計：固定樣本數(shù)為，在附近選取與之最近的個樣本，計算該個樣本分布的最小體積在X處的概率密度估計值為：372021/5/9漸近收斂的條件漸近收斂的充要條件為：通常選擇：382021/5/9Kn近鄰估計例子：392021/5/9例子：

Parzenwindowskn-nearest-neighbor斜率不連續(xù)當(dāng)n值為有限值時Kn近鄰估計十分粗糙402021/5/9例子：Parzenwindowskn-nearest-neighbor412021/5/9Kn近鄰估計Kn近鄰后驗概率估計：

給定i.i.d.樣本集，共類。把一個體積V放在x周圍，能夠包含進(jìn)k個樣本，其中有ki個樣本屬于第i類。那么聯(lián)合概率密度的估計為：后驗概率：

422021/5/9Kn近鄰估計例子X屬于第i類的后驗概率就是體積中標(biāo)記為第i類的樣本個數(shù)與體積中全部樣本點個數(shù)的比值。為了達(dá)到最小誤差率，選擇比值最大的那個類別作為判決結(jié)果。如果樣本足夠多、體積足夠小，這樣的方法得到的結(jié)果是比較準(zhǔn)確的！432021/5/9主要內(nèi)容概率密度估計Parzen窗估計k-NN估計最近鄰分類器（NN）

k-近鄰分類器（k-NN）442021/5/9最近鄰分類器(NN)假設(shè)i.i.d.樣本集對于樣本，NN采用如下的決策：相當(dāng)于采用近鄰方法估計后驗概率，然后采用最大后驗概率決策。分類一個樣本的計算復(fù)雜度：（采用歐氏距離）452021/5/9最近鄰分類器樣本x=(0.10,0.25)的類別？TrainingExamplesLabelsDistance(0.15,0.35)(0.10,0.28)(0.09,0.30)(0.12,0.20)

1

2

5

20.1180.0300.0510.054462021/5/9最近鄰分類器決策邊界：Voronoi網(wǎng)格NN分類規(guī)則將特征空間分成許多Voronoi網(wǎng)格（Voronoi網(wǎng)格：由一組由連接兩鄰點直線的垂直平分線組成的連續(xù)多邊形組成）472021/5/9最近鄰分類器決策邊界在一個Voronoi網(wǎng)格中，每一個點到該Voronoi網(wǎng)格原型的距離小于到其它所有訓(xùn)練樣本點的距離。

NN分類器將該Voronoi網(wǎng)格中的點標(biāo)識為與該原型同類。482021/5/9最近鄰分類器決策邊界：在NN分類器中，分類邊界對于分類新樣本是足夠的。但是計算或者存儲分類邊界是非常困難的目前已經(jīng)提出許多算法來存儲簡化后的樣本集，而不是整個樣本集，使得分類邊界不變。492021/5/9NN分類器的漸近誤差界若是n個樣本時的誤差率，并且：為最小Bayesian錯誤率，c為類別數(shù)?？梢宰C明：502021/5/9NN分類器的漸近誤差界假設(shè)能夠得到無限多的訓(xùn)練樣本和使用任意復(fù)雜的分量規(guī)則，我們至多只能使誤差率降低一半。也就是說，分類信息中的一半信息是由最鄰近點提供的！512021/5/9最近鄰分類器當(dāng)樣本有限的情況下，最近鄰分類器的分類效果如何？不理想！隨著樣本數(shù)量的增加，分類器收斂到漸近值的速度如何？可能會任意慢，而且誤差未必會隨著n的增加單調(diào)遞減！522021/5/9k-近鄰分類器（k-NN）假設(shè)i.i.d.樣本集對于樣本，k-NN采用如下的決策：搜索與最近的個近鄰，如果個近鄰中屬于類的樣本最多，則判決屬于原理：相當(dāng)于采用近鄰方法估計后驗概率，然后采用最大后驗概率決策。分類一個樣本的計算復(fù)雜度：（采用歐氏距離）532021/5/9k-近鄰分類器從測試樣本x開始生長，不斷擴(kuò)大區(qū)域，直至包含進(jìn)k個訓(xùn)練樣本；把測試樣本x的類別歸為與之最近的k個訓(xùn)練樣本中出現(xiàn)頻率最大的類別。542021/5/9例：k=3

(oddvalue)

andx=(0.10,0.25)t選擇k-NNtox

{(0.10,0.28,

2);(0.12,0.20,2);

(0.09,0.30,5)}X屬于

2。PrototypesLabels(0.15,0.35)(0.10,0.28)(0.09,0.30)(0.12,0.20)

1

2

5

2552021/5/9k-近鄰分類器決策面：

分段線性超平面每一個超平面對應(yīng)著最近兩點的中垂面。562021/5/9k-近鄰分類器k-NN分類器的誤差率在樣本數(shù)無窮大時趨向于Bayesian最小錯誤率！572021/5/9k-NN分類器

近鄰分類器

假設(shè)i.i.d.樣本集對于樣本，-NN采用如下的決策：搜索與最近的個近鄰，如果個近鄰中屬于類的樣本最多，為個，則判決屬于，否則拒識。582021/5/9k-NN分類器k-NN分類器的優(yōu)點：原理和實現(xiàn)簡單，特別適用于大類別問題。當(dāng)訓(xùn)練樣本數(shù)較多時，誤差界小于2倍的Bayesian最小錯誤率。592021/5/9k-NN分類器k-NN分類器的缺點：由于訓(xùn)練樣本數(shù)有限，k-NN估計的后驗概率往往并不精確，從而導(dǎo)致分類錯誤率遠(yuǎn)遠(yuǎn)大于Bayesian最小錯誤率。搜索近鄰需要遍歷每一個樣本，計算復(fù)雜度較大。需要存儲所有樣本。受噪聲和距離測度的選擇影響較大。602021/5/9距離度量距離度量應(yīng)滿足如下三個性質(zhì)：非負(fù)性：自反性：當(dāng)且僅當(dāng)對稱性：三角不等式：距離測度的選取原則：需要精心選擇類內(nèi)變化平緩，類間變化劇烈的距離測度！612021/5/9常用的距離函數(shù)歐幾里德距離：(EucideanDistance)

曼哈頓距離：(ManhattanDistance)622021/5/9常用的距離函數(shù)明氏距離：(MinkowskiDistance)馬氏距離：(MahalanobisDistance)632021/5/9常用的距離函數(shù)角度相似函數(shù)：(AngleDistance)

海明距離：(HammingDistance)

x和y為2值特征矢量：D(x,y)定義為x,y中使得不等式