模式識別-第4章概率密度函數(shù)的非參數(shù)估計(jì)

1、模式識別 概率密度函數(shù)的非參數(shù)估計(jì)第四章第四章 概率密度函數(shù)的概率密度函數(shù)的非參數(shù)估計(jì)非參數(shù)估計(jì)模式識別 概率密度函數(shù)的非參數(shù)估計(jì)4.1 基本思想基本思想模式識別 概率密度函數(shù)的非參數(shù)估計(jì)4.1 基本思想基本思想p令令R是包含樣本點(diǎn)是包含樣本點(diǎn)x的一個區(qū)域，其體積為的一個區(qū)域，其體積為V，設(shè)有設(shè)有n個訓(xùn)練樣本，其中有個訓(xùn)練樣本，其中有k個落在區(qū)域個落在區(qū)域R中，則中，則可對概率密度作出一個估計(jì)：可對概率密度作出一個估計(jì)： k npVxp相當(dāng)于用相當(dāng)于用R區(qū)域內(nèi)的平均性質(zhì)來作為一點(diǎn)區(qū)域內(nèi)的平均性質(zhì)來作為一點(diǎn)x的估的估計(jì)，是一種數(shù)據(jù)的平滑。計(jì)，是一種數(shù)據(jù)的平滑。模式識別 概率密度函數(shù)的非參數(shù)估計(jì)有

2、效性有效性p當(dāng)當(dāng)n固定時，固定時，V的大小對估計(jì)的效果影響很的大小對估計(jì)的效果影響很大，過大則平滑過多，不夠精確；過小則大，過大則平滑過多，不夠精確；過小則可能導(dǎo)致在此區(qū)域內(nèi)無樣本點(diǎn)，可能導(dǎo)致在此區(qū)域內(nèi)無樣本點(diǎn)，k=0。p此方法的有效性取決于樣本數(shù)量的多少，此方法的有效性取決于樣本數(shù)量的多少，以及區(qū)域體積選擇的合適。以及區(qū)域體積選擇的合適。模式識別 概率密度函數(shù)的非參數(shù)估計(jì)收斂性收斂性p 構(gòu)造一系列包含構(gòu)造一系列包含x的區(qū)域的區(qū)域R1, R2, ，對應(yīng)，對應(yīng)n=1,2,，則對，則對p(x)有一系列的估計(jì)：有一系列的估計(jì)： nnnknpVxp 當(dāng)滿足下列條件時，當(dāng)滿足下列條件時，pn(x)收斂于

3、收斂于p (x)：lim0nnVlimnnk lim0nnkn模式識別 概率密度函數(shù)的非參數(shù)估計(jì)區(qū)域選定的兩個途徑區(qū)域選定的兩個途徑pParzen窗法窗法：區(qū)域體積：區(qū)域體積V是樣本數(shù)是樣本數(shù)n的函數(shù)，如：的函數(shù)，如：1nVnpK-近鄰法近鄰法：落在區(qū)域內(nèi)的樣本數(shù)：落在區(qū)域內(nèi)的樣本數(shù)k是總樣本數(shù)是總樣本數(shù)n的的函數(shù)，如：函數(shù)，如：nkn模式識別 概率密度函數(shù)的非參數(shù)估計(jì)Parzen窗法和窗法和K-近鄰法近鄰法模式識別 概率密度函數(shù)的非參數(shù)估計(jì)4.2 Parzen窗方法窗方法p定義定義窗函數(shù)窗函數(shù) 1,1 20,juu其它1,20,jijnnxxhhix-x其它dnnVh1,jd模式識別 概率密

4、度函數(shù)的非參數(shù)估計(jì)1維數(shù)據(jù)的窗函數(shù)維數(shù)據(jù)的窗函數(shù)模式識別 概率密度函數(shù)的非參數(shù)估計(jì)概率密度函數(shù)的估計(jì)概率密度函數(shù)的估計(jì)p超立方體中的樣本數(shù)：超立方體中的樣本數(shù)：p概率密度估計(jì)：概率密度估計(jì)：1nninkhix-x 111nninnpnVhix-xx模式識別 概率密度函數(shù)的非參數(shù)估計(jì)窗函數(shù)的要求窗函數(shù)的要求p上述過程是一個內(nèi)插過程，樣本上述過程是一個內(nèi)插過程，樣本xi距離距離x越近，越近，對概率密度估計(jì)的貢獻(xiàn)越大，越遠(yuǎn)貢獻(xiàn)越小。對概率密度估計(jì)的貢獻(xiàn)越大，越遠(yuǎn)貢獻(xiàn)越小。p只要滿足如下條件，就可以作為窗函數(shù)：只要滿足如下條件，就可以作為窗函數(shù)： 0u 1duu模式識別 概率密度函數(shù)的非參數(shù)估計(jì)窗函數(shù)

5、的形式窗函數(shù)的形式模式識別 概率密度函數(shù)的非參數(shù)估計(jì)方形窗和高斯窗方形窗和高斯窗方形窗函數(shù)方形窗函數(shù)高斯窗函數(shù)高斯窗函數(shù)模式識別 概率密度函數(shù)的非參數(shù)估計(jì)窗函數(shù)的寬度對估計(jì)的影響窗函數(shù)的寬度對估計(jì)的影響p hn為窗的寬度為窗的寬度hn=5hn=1hn=2hn=0.5模式識別 概率密度函數(shù)的非參數(shù)估計(jì)識別方法識別方法1. 保存每個類別所有的訓(xùn)練樣本；保存每個類別所有的訓(xùn)練樣本；2. 選擇窗函數(shù)的形式，根據(jù)訓(xùn)練樣本數(shù)選擇窗函數(shù)的形式，根據(jù)訓(xùn)練樣本數(shù)n選擇窗函選擇窗函數(shù)的寬度數(shù)的寬度h；3. 識別時，利用每個類別的訓(xùn)練樣本計(jì)算待識別識別時，利用每個類別的訓(xùn)練樣本計(jì)算待識別樣本樣本x的類條件概率密度：

6、的類條件概率密度：4. 采用采用Bayes判別準(zhǔn)則進(jìn)行分類。判別準(zhǔn)則進(jìn)行分類。111iinjnijinpnVhx-xx模式識別 概率密度函數(shù)的非參數(shù)估計(jì)Parzen窗的神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)窗的神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)p神經(jīng)元模型神經(jīng)元模型1dtiiinetw xw xtyf netfw x模式識別 概率密度函數(shù)的非參數(shù)估計(jì)簡化神經(jīng)元模型簡化神經(jīng)元模型模式識別 概率密度函數(shù)的非參數(shù)估計(jì)Parzen窗函數(shù)的神經(jīng)元表示窗函數(shù)的神經(jīng)元表示p 窗函數(shù)取窗函數(shù)取Gauss函數(shù)，所有的樣本歸一化，令神經(jīng)元的權(quán)函數(shù)，所有的樣本歸一化，令神經(jīng)元的權(quán)值等于訓(xùn)練樣本，即：值等于訓(xùn)練樣本，即：,kkwx21,txx x21tkkkww

7、w 222exp2exp21exptkkknkhnettttkkkxwxwxwx x+w w -2w xp 則有：則有：模式識別 概率密度函數(shù)的非參數(shù)估計(jì)概率神經(jīng)網(wǎng)絡(luò)概率神經(jīng)網(wǎng)絡(luò)(PNN, Probabilistic Neural Network)模式識別 概率密度函數(shù)的非參數(shù)估計(jì)PNN的訓(xùn)練算法的訓(xùn)練算法1. begin initialize j = 0; n =訓(xùn)練樣本數(shù)，訓(xùn)練樣本數(shù)，aji=02. do j j + 13. normalize :4. train : wjxj5. if then aji16. until j = njjjxxxjix模式識別 概率密度函數(shù)的非參數(shù)估計(jì)PN

8、N分類算法分類算法1. begin initialize k = 0; x 待識模式待識模式2. do k k + 13. 4. if aki = 1 then 5. until k = n6. return 7. endTkknet w x2exp1iikyynet1argmaxii cclassy 模式識別 概率密度函數(shù)的非參數(shù)估計(jì)徑向基函數(shù)網(wǎng)絡(luò)徑向基函數(shù)網(wǎng)絡(luò)(RBF, Radial Basis Function)p RBF與與PNN的差異的差異1. 神經(jīng)元數(shù)量神經(jīng)元數(shù)量：PNN模式層神經(jīng)元數(shù)等于訓(xùn)練樣本數(shù)，模式層神經(jīng)元數(shù)等于訓(xùn)練樣本數(shù)，而而RBF小于等于訓(xùn)練樣本數(shù)；小于等于訓(xùn)練樣本數(shù)；2

9、. 權(quán)重權(quán)重：PNN模式層到類別層的連接權(quán)值恒為模式層到類別層的連接權(quán)值恒為1，而，而RBF的需要訓(xùn)練；的需要訓(xùn)練；3. 學(xué)習(xí)方法學(xué)習(xí)方法：PNN的訓(xùn)練過程簡單，只需一步設(shè)置即的訓(xùn)練過程簡單，只需一步設(shè)置即可，而可，而RBF一般需要反復(fù)迭代訓(xùn)練；一般需要反復(fù)迭代訓(xùn)練；模式識別 概率密度函數(shù)的非參數(shù)估計(jì)徑向基函數(shù)網(wǎng)絡(luò)的訓(xùn)練徑向基函數(shù)網(wǎng)絡(luò)的訓(xùn)練pRBF的訓(xùn)練的三種方法：的訓(xùn)練的三種方法：1.根據(jù)經(jīng)驗(yàn)選擇每個模式層神經(jīng)元的權(quán)值根據(jù)經(jīng)驗(yàn)選擇每個模式層神經(jīng)元的權(quán)值wi以及映射函以及映射函數(shù)的寬度數(shù)的寬度，用最小二乘法計(jì)算模式層到類別層的權(quán)，用最小二乘法計(jì)算模式層到類別層的權(quán)值值；2.用聚類的方法設(shè)置模式

10、層每個神經(jīng)元的權(quán)值用聚類的方法設(shè)置模式層每個神經(jīng)元的權(quán)值wi以及映以及映射函數(shù)的寬度射函數(shù)的寬度，用最小二乘法計(jì)算模式層到類別層，用最小二乘法計(jì)算模式層到類別層的權(quán)值的權(quán)值；3.通過訓(xùn)練樣本用誤差糾正算法迭代計(jì)算各層神經(jīng)元的通過訓(xùn)練樣本用誤差糾正算法迭代計(jì)算各層神經(jīng)元的權(quán)值，以及模式層神經(jīng)元的寬度權(quán)值，以及模式層神經(jīng)元的寬度；模式識別 概率密度函數(shù)的非參數(shù)估計(jì)4.3 近鄰分類器近鄰分類器p后驗(yàn)概率的估計(jì)后驗(yàn)概率的估計(jì)Parzen窗法窗法估計(jì)的是每個類別的類條件概率密度估計(jì)的是每個類別的類條件概率密度 ，而而k-近鄰法近鄰法是直接估計(jì)每個類別的后驗(yàn)概率是直接估計(jì)每個類別的后驗(yàn)概率 。將一個體積為

11、將一個體積為V的區(qū)域放到待識樣本點(diǎn)的區(qū)域放到待識樣本點(diǎn)x周圍，包含周圍，包含k個訓(xùn)個訓(xùn)練樣本點(diǎn)，其中練樣本點(diǎn)，其中ki個屬于個屬于i類，總的訓(xùn)練樣本數(shù)為類，總的訓(xùn)練樣本數(shù)為n，則，則有：有：ipxipx,inik npVx 1,niniiicnnjjppkppkpxxxxx模式識別 概率密度函數(shù)的非參數(shù)估計(jì)k-近鄰分類器近鄰分類器p k-近鄰分類算法近鄰分類算法1. 設(shè)置參數(shù)設(shè)置參數(shù)k，輸入待識別樣本，輸入待識別樣本x；2. 計(jì)算計(jì)算x與每個訓(xùn)練樣本的與每個訓(xùn)練樣本的距離距離；3. 選取距離最小的前選取距離最小的前k個樣本，統(tǒng)計(jì)其中包含個樣本，統(tǒng)計(jì)其中包含各個類別的樣本數(shù)各個類別的樣本數(shù)ki；

12、4. 1argmaxii cclassk 模式識別 概率密度函數(shù)的非參數(shù)估計(jì)k-近鄰分類，近鄰分類，k=13模式識別 概率密度函數(shù)的非參數(shù)估計(jì)最近鄰規(guī)則最近鄰規(guī)則p分類規(guī)則分類規(guī)則：在訓(xùn)練樣本集中尋找與待識別樣本：在訓(xùn)練樣本集中尋找與待識別樣本x距距離最近的樣本離最近的樣本x，將，將x分類到分類到x所屬的類別。所屬的類別。p最近鄰規(guī)則最近鄰規(guī)則相當(dāng)于相當(dāng)于k=1的的k-近鄰分類，其分類界面近鄰分類，其分類界面可以用可以用Voronoi網(wǎng)格表示。網(wǎng)格表示。模式識別 概率密度函數(shù)的非參數(shù)估計(jì)Voronoi網(wǎng)格網(wǎng)格模式識別 概率密度函數(shù)的非參數(shù)估計(jì)距離度量距離度量p 距離度量應(yīng)滿足如下四個性質(zhì)：距離

13、度量應(yīng)滿足如下四個性質(zhì)：1. 非負(fù)性非負(fù)性：2. 自反性自反性： 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)3. 對稱性對稱性：4. 三角不等式三角不等式：0Da,b0Da,babDDa,bb,aDDDa,bb,ca,c模式識別 概率密度函數(shù)的非參數(shù)估計(jì)常用的距離函數(shù)常用的距離函數(shù) 121221,dtiiiDxyx yx-yx-yp歐幾里德距離歐幾里德距離：(Eucidean Distance) 模式識別 概率密度函數(shù)的非參數(shù)估計(jì)常用的距離函數(shù)常用的距離函數(shù)p街市距離街市距離：(Manhattan Distance)1,diiiDxyx y模式識別 概率密度函數(shù)的非參數(shù)估計(jì)常用的距離函數(shù)常用的距離函數(shù)p明氏距離明氏距離

14、：(Minkowski Distance)11,mdmiiiDxyx y模式識別 概率密度函數(shù)的非參數(shù)估計(jì)常用的距離函數(shù)常用的距離函數(shù) 1,tDx yx-y x-yp馬氏距離馬氏距離：(Mahalanobis Distance) 模式識別 概率密度函數(shù)的非參數(shù)估計(jì)常用的距離函數(shù)常用的距離函數(shù)p角度相似函數(shù)角度相似函數(shù)：(Angle Distance),tDx yx yx y模式識別 概率密度函數(shù)的非參數(shù)估計(jì)常用的距離函數(shù)常用的距離函數(shù)1,tdxxx1,tdyyy,0,1iix y p海明距離海明距離：(Hamming Distance) x和和y為為2值特征矢量：值特征矢量： D(x,y)定義

15、為定義為x,y中使得不等式中使得不等式 成立的成立的i的個的個數(shù)。數(shù)。iixy模式識別 概率密度函數(shù)的非參數(shù)估計(jì)最近鄰分類器的簡化最近鄰分類器的簡化p 最近鄰分類器計(jì)算的時間復(fù)雜度和空間復(fù)雜度都最近鄰分類器計(jì)算的時間復(fù)雜度和空間復(fù)雜度都為為O(dn)，d為特征維數(shù)，通常只有當(dāng)樣本數(shù)為特征維數(shù)，通常只有當(dāng)樣本數(shù)n非非常大時，分類效果才會好。常大時，分類效果才會好。p 簡化方法可以分為三種：簡化方法可以分為三種：1. 部分距離法；部分距離法；2. 預(yù)分類法；預(yù)分類法；3. 剪輯近鄰法。剪輯近鄰法。模式識別 概率密度函數(shù)的非參數(shù)估計(jì)部分距離法部分距離法p 定義：定義：1221rriiiDxyx,yD

16、r(x,y)是是r的單調(diào)不減函數(shù)。令的單調(diào)不減函數(shù)。令Dmin為當(dāng)前搜索到的最近鄰為當(dāng)前搜索到的最近鄰距離，當(dāng)待識別樣本距離，當(dāng)待識別樣本x與某個訓(xùn)練樣本與某個訓(xùn)練樣本xi的部分距離的部分距離Dr(x,xi)大于大于 Dmin時，時， Dd(x,xi)一定要大于一定要大于Dmin ，所以，所以xi一定不是最一定不是最近鄰，不需要繼續(xù)計(jì)算近鄰，不需要繼續(xù)計(jì)算Dd(x,xi) 。模式識別 概率密度函數(shù)的非參數(shù)估計(jì)預(yù)分類（搜索樹）預(yù)分類（搜索樹）模式識別 概率密度函數(shù)的非參數(shù)估計(jì)預(yù)分類（搜索樹）預(yù)分類（搜索樹）p在特征空間中首先找到在特征空間中首先找到m個有代表性的樣本點(diǎn)，個有代表性的樣本點(diǎn)，用這些

17、點(diǎn)代表一部分訓(xùn)練樣本；用這些點(diǎn)代表一部分訓(xùn)練樣本；p待識別模式待識別模式x首先與這些代表點(diǎn)計(jì)算距離，找到一首先與這些代表點(diǎn)計(jì)算距離，找到一個最近鄰，然后在這個最近鄰代表的樣本點(diǎn)中尋個最近鄰，然后在這個最近鄰代表的樣本點(diǎn)中尋找實(shí)際的最近鄰點(diǎn)。找實(shí)際的最近鄰點(diǎn)。p這種方法是一個這種方法是一個次優(yōu)次優(yōu)的搜索算法。的搜索算法。模式識別 概率密度函數(shù)的非參數(shù)估計(jì)剪輯近鄰法剪輯近鄰法p 最近鄰剪輯算法最近鄰剪輯算法1. begin initialize j = 0;D = data set; n = number of training samples2. construct the full Voron

18、oi diagram of D3. do j j + 1; 4. Find the Voronoi neighbors of Xj5. if any neighbor is not from the same class as Xj then mark Xj6. until j = n7. Discard all points that are not marked8. Construct the Voronoi diagram of the remaining samples9. end模式識別 概率密度函數(shù)的非參數(shù)估計(jì)剪輯近鄰法剪輯近鄰法剪輯前剪輯前剪輯后剪輯后模式識別 概率密度函數(shù)的非參數(shù)估計(jì)RCE網(wǎng)絡(luò)網(wǎng)絡(luò)模式識別 概率密度函數(shù)的非參數(shù)估計(jì)RCE網(wǎng)絡(luò)的訓(xùn)練算法網(wǎng)絡(luò)的訓(xùn)練算法1. begin initialize j=0, n=#patterns, =small pattern, m=max radius，aij=02. do jj+13. train weight: wj=xj4. if then aji = 15. find nearest poin