概率密度函數(shù)的非參數(shù)估計(jì).ppt

第四章 概率密度函數(shù)的非參數(shù)估計(jì),4.1 基本思想,4.1 基本思想,令R是包含樣本點(diǎn)x的一個(gè)區(qū)域，其體積為V，設(shè)有n個(gè)訓(xùn)練樣本，其中有k個(gè)落在區(qū)域R中，則可對(duì)概率密度作出一個(gè)估計(jì)：,相當(dāng)于用R區(qū)域內(nèi)的平均性質(zhì)來(lái)作為一點(diǎn)x的估計(jì)，是一種數(shù)據(jù)的平滑。,有效性,當(dāng)n固定時(shí)，V的大小對(duì)估計(jì)的效果影響很大，過(guò)大則平滑過(guò)多，不夠精確；過(guò)小則可能導(dǎo)致在此區(qū)域內(nèi)無(wú)樣本點(diǎn)，k=0。 此方法的有效性取決于樣本數(shù)量的多少，以及區(qū)域體積選擇的合適。,收斂性,構(gòu)造一系列包含x的區(qū)域R1, R2, ，對(duì)應(yīng)n=1,2,，則對(duì)p(x)有一系列的估計(jì)：,當(dāng)滿足下列條件時(shí)，pn(x)收斂于p (x)：,區(qū)域選定的兩個(gè)途徑,Parzen窗法：區(qū)域體積V是樣本數(shù)n的函數(shù)，如：,K-近鄰法：落在區(qū)域內(nèi)的樣本數(shù)k是總樣本數(shù)n的函數(shù)，如：,Parzen窗法和K-近鄰法,4.2 Parzen窗方法,定義窗函數(shù),1維數(shù)據(jù)的窗函數(shù),概率密度函數(shù)的估計(jì),超立方體中的樣本數(shù)： 概率密度估計(jì)：,窗函數(shù)的要求,上述過(guò)程是一個(gè)內(nèi)插過(guò)程，樣本xi距離x越近，對(duì)概率密度估計(jì)的貢獻(xiàn)越大，越遠(yuǎn)貢獻(xiàn)越小。 只要滿足如下條件，就可以作為窗函數(shù)：,窗函數(shù)的形式,窗函數(shù)的寬度對(duì)估計(jì)的影響,hn稱為窗的寬度,窗函數(shù)的寬度對(duì)估計(jì)的影響,識(shí)別方法,保存每個(gè)類別所有的訓(xùn)練樣本； 選擇窗函數(shù)的形式，根據(jù)訓(xùn)練樣本數(shù)n選擇窗函數(shù)的h寬度； 識(shí)別時(shí)，利用每個(gè)類別的訓(xùn)練樣本計(jì)算待識(shí)別樣本x的類條件概率密度： 采用Bayes判別準(zhǔn)則進(jìn)行分類。,Parzen窗的神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn),神經(jīng)元模型,簡(jiǎn)化神經(jīng)元模型,Parzen窗函數(shù)的神經(jīng)元表示,窗函數(shù)取Gauss函數(shù)，所有的樣本歸一化，令神經(jīng)元的權(quán)值等于訓(xùn)練樣本，即：,則有：,概率神經(jīng)網(wǎng)絡(luò)(PNN, Probabilistic Neural Network),PNN的訓(xùn)練算法,begin initialize j = 0; n =訓(xùn)練樣本數(shù)，aji=0 do j j + 1 normalize : train : wjxj if then aji1 until j = n,PNN分類算法,begin initialize k = 0; x 待識(shí)模式 do k k + 1 if aki = 1 then until k = n return end,徑向基函數(shù)網(wǎng)絡(luò)(RBF, Radial Basis Function),RBF與PNN的差異 神經(jīng)元數(shù)量：PNN模式層神經(jīng)元數(shù)等于訓(xùn)練樣本數(shù)，而RBF小于等于訓(xùn)練樣本數(shù)； 權(quán)重：PNN模式層到類別層的連接權(quán)值恒為1，而RBF的需要訓(xùn)練； 學(xué)習(xí)方法：PNN的訓(xùn)練過(guò)程簡(jiǎn)單，只需一步設(shè)置即可，而RBF一般需要反復(fù)迭代訓(xùn)練；,徑向基函數(shù)網(wǎng)絡(luò)的訓(xùn)練,RBF的訓(xùn)練的三種方法： 根據(jù)經(jīng)驗(yàn)選擇每個(gè)模式層神經(jīng)元的權(quán)值wi以及映射函數(shù)的寬度，用最小二乘法計(jì)算模式層到類別層的權(quán)值； 用聚類的方法設(shè)置模式層每個(gè)神經(jīng)元的權(quán)值wi以及映射函數(shù)的寬度，用最小二乘法計(jì)算模式層到類別層的權(quán)值； 通過(guò)訓(xùn)練樣本用誤差糾正算法迭代計(jì)算各層神經(jīng)元的權(quán)值，以及模式層神經(jīng)元的寬度；,4.3 近鄰分類器,后驗(yàn)概率的估計(jì) Parzen窗法估計(jì)的是每個(gè)類別的類條件概率密度 ，而k-近鄰法是直接估計(jì)每個(gè)類別的后驗(yàn)概率 。 將一個(gè)體積為V的區(qū)域放到待識(shí)樣本點(diǎn)x周圍，包含k個(gè)訓(xùn)練樣本點(diǎn)，其中ki個(gè)屬于i類，總的訓(xùn)練樣本數(shù)為n，則有：,k-近鄰分類器,k-近鄰分類算法 設(shè)置參數(shù)k，輸入待識(shí)別樣本x； 計(jì)算x與每個(gè)訓(xùn)練樣本的距離； 選取距離最小的前k個(gè)樣本，統(tǒng)計(jì)其中包含各個(gè)類別的樣本數(shù)ki；,k-近鄰分類，k=13,最近鄰規(guī)則,分類規(guī)則：在訓(xùn)練樣本集中尋找與待識(shí)別樣本x距離最近的樣本x，將x分類到x所屬的類別。 最近鄰規(guī)則相當(dāng)于k=1的k-近鄰分類，其分類界面可以用Voronoi網(wǎng)格表示。,Voronoi網(wǎng)格,距離度量,距離度量應(yīng)滿足如下四個(gè)性質(zhì)： 非負(fù)性： 自反性： 當(dāng)且僅當(dāng) 對(duì)稱性： 三角不等式：,常用的距離函數(shù),歐幾里德距離：(Eucidean Distance),常用的距離函數(shù),街市距離：(Manhattan Distance),常用的距離函數(shù),明氏距離：(Minkowski Distance),常用的距離函數(shù),馬氏距離：(Mahalanobis Distance),常用的距離函數(shù),角度相似函數(shù)：(Angle Distance),常用的距離函數(shù),海明距離：(Hamming Distance) x和y為2值特征矢量：,D(x,y)定義為x,y中使得不等式 成立的i的個(gè)數(shù)。,最近鄰分類器的簡(jiǎn)化,最近鄰分類器計(jì)算的時(shí)間復(fù)雜度和空間復(fù)雜度都為O(dn)，d為特征維數(shù)，通常只有當(dāng)樣本數(shù)n非常大時(shí)，分類效果才會(huì)好。 簡(jiǎn)化方法可以分為三種： 部分距離法； 預(yù)分類法； 剪輯近鄰法。,部分距離法,定義：,Dr(x,y)是r的單調(diào)不減函數(shù)。令Dmin為當(dāng)前搜索到的最近鄰距離，當(dāng)待識(shí)別樣本x與某個(gè)訓(xùn)練樣本xi的部分距離Dr(x,xi)大于 Dmin時(shí)， Dd(x,xi)一定要大于Dmin ，所以xi一定不是最近鄰，不需要繼續(xù)計(jì)算Dd(x,xi) 。,預(yù)分類（搜索樹）,預(yù)分類（搜索樹）,在特征空間中首先找到m個(gè)有代表性的樣本點(diǎn)，用這些點(diǎn)代表一部分訓(xùn)練樣本； 待識(shí)別模式x首先與這些代表點(diǎn)計(jì)算距離，找到一個(gè)最近鄰，然后在這個(gè)最近鄰代表的樣本點(diǎn)中尋找實(shí)際的最近鄰點(diǎn)。 這種方法是一個(gè)次優(yōu)的搜索算法。,剪輯近鄰法,最近鄰剪輯算法 begin initialize j = 0;D = data set; n = number of training samples construct the full Voronoi diagram of D do j j + 1; Find the Voronoi neighbors of Xj if any neighbor is not from the same class as Xj then mark Xj until j = n Discard all points that are not marked Construct the Voronoi diagram of the remaining samples end,剪輯近鄰法,剪輯近鄰法,RCE網(wǎng)絡(luò),RCE網(wǎng)絡(luò)的訓(xùn)練算法,begin initialize j=0, n=#patterns, =small pattern, m=max radius，aij=0 do jj+1 train weight: wj=xj if then aji = 1 find nearest point not in i: set radius: until j = n