模式識別非參數(shù)估計

非參數(shù)估計

--模式識別課程

Non-ParametricClassification提綱概率密度估計Parzen窗估計Kn-近鄰估計最近鄰規(guī)則

Non-ParametricClassification模式分類的途徑途徑1：估計類條件概率密度p(x|ωi)

?通過p(x|ωi)和p(ωi)，利用貝葉斯規(guī)則計算后驗概率p(ωi|x)，然后通過最大后驗概率做出決策?方法1a：概率密度參數(shù)估計,基于對p(x|ωi)的含參數(shù)的描述?方法1b：概率密度非參數(shù)估計,基于對p(x|ωi)的非參數(shù)的描述途徑2：直接估計后驗概率p(ωi|x)

?不需要先估計p(x|ωi)途徑3：直接計算判別函數(shù)不需要估計p(x|ωi)或者p(ωi|x)

Non-ParametricClassification為什么？對復(fù)雜的問題，我們常常得不到解析化的描述是，比如對于概率密度的多高斯描述。Bayesian學(xué)派的核心就是概率密度，而現(xiàn)實世界中的概率分布是復(fù)雜的。在一些部分上可能符合了人腦的推理規(guī)則。

Non-ParametricClassification非參數(shù)估計方法的分類非參數(shù)估計:直接用已知類別樣本去估計總體密度分布，方法有：①

用樣本直接去估計類概率密度p(x|ωi)以此來設(shè)計分類器,如窗口估計.②

用學(xué)習(xí)樣本直接估計后驗概率p(ωi|x)作為分類準(zhǔn)則來設(shè)計分類器,如k近鄰法.概率密度估計-核心思想投硬幣實驗-當(dāng)獨(dú)立進(jìn)行的實驗次數(shù)足夠多的時候，統(tǒng)計數(shù)據(jù)接近實際的概率密度。但是，問題本身是離散的，簡單的（服從伯努利分布），采樣實驗是容易的。對實際的問題呢？概率密度估計一個隨機(jī)變量X落在區(qū)域R的概率為PRp(x)p1是樣本x落入R內(nèi)的概率pk是k個樣本落入R內(nèi)的概率概率密度估計數(shù)學(xué)期望:E(k)=k=NP∴對概率P的估計:。是P的一個比較好的估計.

設(shè)p(x’)在R內(nèi)連續(xù)變化,當(dāng)R逐漸減小的時候,小到使p(x)在其上幾乎沒有變化時，則其中是R包圍的體積概率密度估計

概率密度的估計：(V足夠小)(1)當(dāng)V固定的時候N增加,k也增加,當(dāng)時(2)當(dāng)N固定,體積V變小

當(dāng)時,

時當(dāng)時,時

p(x)起伏比較大,噪聲比較大,需要對V進(jìn)行改進(jìn).概率密度估計對體積V進(jìn)行改進(jìn)：為了估計X點(diǎn)的密度,我們構(gòu)造一串包括X的區(qū)域序列R1,R2,..RN.對R1采用一個樣本進(jìn)行估計，對R2采用二個樣本進(jìn)行估計.。設(shè)VN是RN的體積，KN是N個樣本落入RN的樣本數(shù)則密度的第N次估計：

其中,VN是RN的體積,

KN是N個樣本落入RN的樣本數(shù)∴pN(x)是p(x)的第N次估計非參數(shù)概率密度估計的關(guān)鍵-VV很大：估計的概率密度過于平滑，失去準(zhǔn)確性V很?。盒枰臉颖竞芏?且估計結(jié)果起伏不定pN(x)收斂于p(x)的三個條件：Parzen窗和Kn-近鄰區(qū)別：選擇V的策略不同。首先給定一個初始V值，然后使區(qū)域序列的體積Vn按照某個函數(shù)隨N的增大不斷地縮小，如Parzen窗方法確定kn為n的某個函數(shù)，隨N的增大而變大，如kn-近鄰方法132023/1/17概率密度的估計方法直方圖方法用直方圖逼近概率密度函數(shù)?用直方圖來模擬p(x)?假設(shè)k個樣本落入以x為中點(diǎn)的小條（寬度為h）中，如果n足夠大，則有?根據(jù)以上兩種近似，得到高維空間由于數(shù)據(jù)稀疏，很難應(yīng)用142023/1/17概率密度的估計方法核方法定義窗函數(shù)（核函數(shù)、勢函數(shù)）?落入寬度為h，中點(diǎn)為x的小條中的樣本個數(shù)?對p(x)的非參數(shù)化模擬xj的某個函數(shù)的均值Parzen窗口估計假設(shè)RN為一個d維的超立方體，hN為超立方體的長度超立方體體積為：，

d=1，窗口為一線段d=2，窗口為一平面

d=3，窗口為一立方體d>3，窗口為一超立方體窗口的選擇：

方窗函數(shù)指數(shù)窗函數(shù)Φ(u)Φ(u)Φ(u)正態(tài)窗函數(shù)Parzen窗口估計φ(u)是以原點(diǎn)x為中心的超立方體。在xi落入方窗時，則有在VN內(nèi)為1

不在VN內(nèi)為0落入VN的樣本數(shù)為所有為1者之和概率密度估計Parzen窗口估計討論：①每個樣本對估計所起的作用依賴于它到x的距離，即

|x-xi|≤hN/2時，xi在VN內(nèi)為1，否則為0。

②稱為的窗函數(shù)，取0，1兩種值，但有

時可以取0,0.1,0.2……多種數(shù)值，例如隨xi離x接近的程度，取值由0,0.1,0.2……到1。Parzen窗口估計③要求估計的pN(x)應(yīng)滿足：為滿足這兩個條件，要求窗函數(shù)滿足：④窗長度hN對pN(x)的影響若hN太大,pN(x)是p(x)的一個平坦,分辨率低的估計,有平均誤差若hN太小,pN(x)是p(x)的一個不穩(wěn)定的起伏大的估計,有噪聲誤差為了使這些誤差不嚴(yán)重，hN應(yīng)仔細(xì)選擇下面進(jìn)一步討論窗寬對估計的影響:定義:于是估計式表示成:影響的幅度和寬度。注意到:可看出Parzen窗口估計若Nh較大，則)(jNxxrr-d幅度將較小，而寬度增大是N個低幅緩變的尺度較寬的函數(shù)迭加,較平滑，不能跟上的變化，分辨率較低。Parzen窗口估計當(dāng)hN很小時，δN（X-Xj）幅度很大，寬度很小，近似于以X為中心的δ-函數(shù)，此時pN（x）是N個以學(xué)習(xí)樣本xj為中心的尖脈沖在X點(diǎn)處疊加，這會使pN（x）波動，不穩(wěn)定，可能失去連續(xù)性，所以hN的選取對概率密度估計值pN（x）的影響很大。估計量是一隨機(jī)變量，它依賴于隨機(jī)的訓(xùn)練樣本，所以估計量的性能只能用統(tǒng)計性質(zhì)表示。在滿足下列條件下是漸近無偏估計、均方收斂、均方逼近、且是漸近正態(tài)分布。⑴

概密)(xp在x處連續(xù)⑵

窗函數(shù)滿足下列條件①0)(3ju②

ò=j1)(udu③

￥<j)(supuu④

0)(lim1=j?=￥?diiuuuParzen窗口估計證明pN(x)是p(x)的漸近無偏估計：Parzen窗口估計例1：對于一個二類（ω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)?0123456x6x5x3x1x2x4X軸Parzen窗口估計Parzen窗口估計選正態(tài)窗函數(shù)∵x是一維的上式用圖形表示是6個分別以3.2，3.6，3，6，2.5，1.1為中心的正態(tài)曲線，而PN(x)則是這些曲線之和。Parzen窗口估計Parzen窗口估計例2：設(shè)待估計的概率密度p(x)是個均值為0，方差為1的正態(tài)分布。若隨機(jī)地抽取X樣本中的1個、16個、256個作為學(xué)習(xí)樣本xi,試用窗口法估計PN(x)。解：設(shè)窗口函數(shù)為正態(tài)的，σ＝1，μ＝0hN:窗長度，N為樣本數(shù)，h1為選定可調(diào)節(jié)的參數(shù)。用窗法估計單一正態(tài)分布的實驗N=∞N=256N=16N=1例3,待估的密度函數(shù)為采用正態(tài)窗函數(shù)x-2.5-210.2502p(x)-2.5<x<-20<x<2x為其它Parzen窗口估計N=∞N=256N=16N=1用窗法估計兩個均勻分布的實驗Parzen窗分類直接估計后驗概率密度進(jìn)行判決Parzen窗分類器判決邊界的劃分與窗寬相關(guān)Parzen窗分類直接估計后驗概率密度存在維數(shù)災(zāi)難-非參數(shù)方法的致命弱點(diǎn)322023/1/17Parzen窗分類332023/1/17Parzen窗分類概率神經(jīng)網(wǎng)絡(luò)（PNN）-一種Parzen窗的實現(xiàn)a1a2ad...p1p2pn...InputunitPatternsunits....WdnWd2W111c.Categoryunits...2....Xi訓(xùn)練PNN1.規(guī)范化訓(xùn)練數(shù)據(jù)Xi={a1i,a2i,…,adi|c(類別)}使||Xi||=1;2.修改Xi和模式層單元Pi個之間的權(quán)值(w1i,w2i,…,wdi)為(a1i,a2i,…,adi);3.在pi和類別單元c之間增加連接4.直到所有訓(xùn)練數(shù)據(jù)用完并每個數(shù)據(jù)只用一次，宣告訓(xùn)練完成。用PNN分類1.歸一化待分類實例x;2.對每個模式計算內(nèi)積3.在有連接的輸出層上累加最大的響應(yīng)類別做為最后分類結(jié)果結(jié)論：

由上例知窗口法的優(yōu)點(diǎn)是應(yīng)用的普遍性。對規(guī)則分布，非規(guī)則分布，單鋒或多峰分布都可用此法進(jìn)行密度估計。要求樣本足夠多，才能有較好的估計。因此使計算量，存儲量增大。窗函數(shù)選取得當(dāng)有利于提高估計的精度和減少樣本的數(shù)量。Parzen窗口估計KN近鄰估計

在窗口法中存在一個問題是對hN的選擇問題。若hN選太小，則大部分體積將是空的（即不包含樣本），從而使pN(x)估計不穩(wěn)定。若hN選太大，則pN(x)估計較平坦，反映不出總體分布的變化，而KN近鄰法的思想是以x為中心建立空胞，使v↑，直到捕捉到KN個樣本為止?！喾QKN-近鄰估計。

v的改進(jìn)，樣本密度大，VN↓;

樣本密度小，VN↑;

∴p(x)的估計為：KN近鄰估計

使PN(x)收斂于P(x)的充分必要條件：①，N與KN同相變化②，KN的變化遠(yuǎn)小于N的變化

③V1為N=1時的VN值KN近鄰估計KN近鄰法作后驗概率的估計由KN近鄰估計知N個已知類別樣本落入VN內(nèi)為KN個樣本的概率密度估計為：

N個樣本落入VN內(nèi)有KN個，KN個樣本內(nèi)有ki個樣本屬于ωi類則聯(lián)合概率密度：

KN近鄰估計根據(jù)Bayes公式可求出后驗概率：類別為ωi的后驗概率就是落在VN內(nèi)屬于ωi的樣本ki與VN內(nèi)總樣本數(shù)KN的比值∴

∵K近鄰準(zhǔn)則K近鄰分類準(zhǔn)則：對于待分樣本x，找出它的k個近鄰，檢查它的類別，把x歸于樣本最多的那個類別。K近鄰分類的錯誤率隨K↑，Pk↓,最低的錯誤率為Bayes分類。P*PK

最近鄰分類準(zhǔn)則：待分樣本x，找一個離它最近的樣本，把x歸于最近的樣本一類。錯誤率：

M為類別數(shù)P(e)為Bayes估計的錯誤率最近鄰分類法則的錯誤率P比K近鄰錯誤率還大，但最大不會超過貝葉斯分類器錯誤率的二倍。PP(e)BayesK近鄰最近鄰最近鄰法將與測試樣本最近鄰樣本的類別作為決策的方法稱為最近鄰法。

最近鄰法的錯誤率是比較難計算的，這是因為訓(xùn)練樣本集的數(shù)量總是有限的，有時多一個少一個訓(xùn)練樣本對測試樣本分類的結(jié)果影響很大。紅點(diǎn)表示A類訓(xùn)練樣本，藍(lán)點(diǎn)表示B類訓(xùn)練樣本，而綠點(diǎn)O表示待測樣本。假設(shè)以歐氏距離來衡量，O的最近鄰是A3，其次是B1，因此O應(yīng)該屬于A類；但若A3被拿開，O就會被判為B類。最近鄰法的錯誤率這說明計算最近鄰法的錯誤率會有偶然性，也就是指與具體的訓(xùn)練樣本集有關(guān)。同時還可看到，計算錯誤率的偶然性會因訓(xùn)練樣本數(shù)量的增大而減小。因此我們就利用訓(xùn)練樣本數(shù)量增至極大，來對其性能進(jìn)行評價。這要使用漸近概念，以下都是在漸近概念下來分析錯誤率的。

最近鄰法的錯誤率當(dāng)最近鄰法所使用的訓(xùn)練樣本數(shù)量N不是很大時，其錯誤率是帶有偶然性的。

下圖所示為一個在一維特征空間的兩類別情況：

X表示一待測試樣本，而X'是所用訓(xùn)練樣本集中X的最鄰近者，則錯誤是由X與X'分屬不同的類別所引起的。最近鄰法的錯誤率由于X‘與所用訓(xùn)練樣本集有關(guān)，因此錯誤率有較大偶然性。但是如果所用訓(xùn)練樣本集的樣本數(shù)量N極大，即N→∞時，可以想像X‘將趨向于X，或者說處于以X為中心的極小鄰域內(nèi)，此時分析錯誤率問題就簡化為在X樣本條件下X與一個X(X’的極限條件)分屬不同類別的問題。如果樣本X的兩類別后驗概率分別為P(ω1|X)與P(ω2|X)，那么對X值，在N→∞條件下，發(fā)生錯誤決策的概率為：最近鄰法的錯誤率而在這條件下的平均錯誤率

P稱為漸近平均錯誤率，是PN(e)在N→∞的極限。為了與基于最小錯誤率的貝葉斯決策方法對比，下面寫出貝葉斯錯誤率的計算式：

其中最近鄰法的錯誤率

若是兩類問題，則

貝葉斯錯誤率：