《模式識別》.ppt

1、模式識別 Pattern Recognition概率密度函數估計,佘勇 課件密碼 ： kys2006 TelEmail: 辦公室：科教樓110,貝葉斯分類器設計的關鍵要求,貝葉斯分類器是基于樣本的概率分布的分類器，設計貝葉斯分類器的關鍵是： 決策類別數已知（c類） 先驗概率P(i)已知 類條件概率密度p(x|i)已知,設計貝葉斯分類器時可能的已知條件,關于樣本 1、已知類別的訓練樣本 2、樣本類別未知，但有其它可用信息 關于類別的概率分布 1、已知先驗概率P(i)，類條件概率密度p(x|i)的形式已知，但部分分布參數未知 2、已知先驗概率P(i)，類條件概率密度p(x

2、|i)完全未知 3、先驗概率P(i)，類條件概率密度p(x|i)完全未知,貝葉斯分類器設計步驟,1、利用已知或未知類別的樣本信息估計先驗概率P(i)，類條件概率密度p(x|i)（分別表示為 ） 2、利用估計量 設計決策函數，完成分類器設計 我們希望：當樣本數目N時， 收斂于P(i)， p(x|i),利用樣本集估計,已知概率密度函數形式，未知其某些參數,概率密度函數形式未知,樣本類別已知,樣本類別未知,估計參數確定而未知,估計參數是隨機量，其先驗分布已知,最大似然估計,最大似然估計基于以下假設： 待估參數是確定的未知量 按類別把樣本分成c類X1，X2，X3， XC，其中第i類Xi的樣本共N個 X

3、i =(x1,x2,，xN)T，并且是從概率密度為p(x|i)總體中獨立抽取的 Xi中的樣本不包含j(ij)的信息，所以可以對每一類樣本獨立進行處理 條件概率密度p(x|i)具有確定的函數形式，其參數i未知，可以表示為p(x|i) 根據假定，可以只利用第i類訓練樣本來估計第i類的概率密度函數的參數，設i =(1,2,，P)T 。,似然函數,設第i類樣本集Xi的樣本共N個 Xi =(x1,x2,，xN)T，是從概率密度為p(x|i)總體中獨立抽取的，則聯合密度： 我們把N個隨機變量的聯合密度稱為似然函數l(i),求i的最大似然估計,如果參數空間中的某個 能夠使l(i)極大化，則 即為i的最大似然

4、估計量 如果i僅有一個分量（i為標量），則i的最大似然估計量為下列方程的解： 有時為了計算方便，可對似然函數取對數：,如果i =(1,2,，P)T ，則定義梯度算子 ： 對于對數似然函數H(i)=lnl(i)，下述方程其中的一個解為i的最大似然估計：,對i求導,并令它為0： 有時上式是多解的, 上圖有5個解,只有一個解最大即.,P(Xi/i),一維正態(tài)分布的最大似然估計,設Xi =(x1,x2,，xN)T，為N個一維樣本，是從一維正態(tài)分布概率密度函數p(x|i)總體中獨立抽取的， i =(1,2)T ，1=，2=2則： i最大似然估計量 為下述方程的解,由上述方程組解得1=，2=2的最大似然估

5、計量：,多維正態(tài)分布的最大似然估計,設Xi =(x1,x2,，xN)T，為N個d維樣本，是從d維正態(tài)分布概率密度函數p(x|i)總體中獨立抽取的， i =(1,2)T ，1=，2=則： i最大似然估計量 為下述方程的解,由上述方程組解得1=，2=的最大似然估計量： 結論： 正態(tài)總體均值的最大似然估計即為訓練樣本的算術平均 協方差的最大似然估計是N個矩陣的算術平均,最小風險率貝葉斯決策,設： 待識別樣本： x =(x1,x2,，xd)T 類別狀態(tài)空間：=w1，w2，wC 決策空間：=a1, a2,，aa (ai,wj)表示樣本x為類別wj而采取決策ai所造成損失 則，樣本x采取決策ai造成的條件

6、期望損失（條件風險）：,對特征空間Ed中的任意樣本x采取決策ai造成的條件風險的期望： 使R最小的決策ak稱為最小風險貝葉斯決策,貝葉斯估計,設第i類樣本集Xi的樣本共N個 Xi =(x1,x2,，xN)T，是從概率密度為p(x |i )總體中獨立抽取的，i為隨機量，其先驗分布p(i)已知，試通過樣本集Xi估計i（找出估計量 ）使貝葉斯風險最小,與最大似然估計的區(qū)別,最大似然估計是把待估的參數看作固定的未知量 貝葉斯估計則是把待估的參數作為具有某種先驗分布的隨機變量 通過對第i類學習樣本Xi的觀察，使概率密度分布P(Xi|)轉化為后驗P(|Xi) ，再求貝葉斯估計,參數估計的貝葉斯風險計算,參

7、照最小風險貝葉斯決策公式，參數估計的貝葉斯風險R： 根據貝葉斯公式： 為給定x條件下估計量的期望損失，即條件風險,貝葉斯估計的本質,使條件風險 極小的估計量 一定使貝葉斯風險最小 如果i的估計量 使條件風險 最小，則稱 是關于i的貝葉斯估計量,二次損失函數下的貝葉斯估計量,如果損失函數為二次函數： 則i的貝葉斯估計量 是給定x時的條件期望： 可以證明上式得到的i的貝葉斯估計量 可使條件風險最小,貝葉斯估計步驟, 確定i的先驗分布P(i),待估參數為隨機變量。 用第i類Xi的樣本集 Xi =(x1, x2,，xN)T，求出樣本的聯合概率密度分布P(Xi|i)，它是i的函數。 利用貝葉斯公式,求i

8、的后驗概率 求貝葉斯估計量,一維正態(tài)分布下的貝葉斯估計,設一維正態(tài)分布且總體方差已知（未知）： 總體分布密度p(x|)N(,2) 的先驗概率P()已知P()N(0,02) 樣本集 Xi =(x1,x2,，xN)T是取自N(,2)的樣本集 求：的貝葉斯估計量,在二次損失函數下: 利用貝葉斯公式，得：,由于： p(x|)N(,2) P()N(0,02) 所以,P(|X)為正態(tài)分布： 比較上述2個公式，利用待定系數法，得：,解上式得： 代入估計量公式：,如果令P()為標準正態(tài)分布 P()N(0,02)=N(0,1) 則： 與最大似然估計相似，只是分母不同,貝葉斯學習,在貝葉斯估計中，當求出的后驗概率

9、之后，直接去推導總體分布即 根據貝葉斯公式： 設用XN表示N個樣本的樣本集： XN =(x1,x2,，xN)T，有：,綜合上述兩式得： 參數估計的遞推貝葉斯方法：設p()已知，利用上式，可以得到一個密度函數系列： p()，p(|x1)， p(|x1，x2)，。 如果此密度系列收斂于一個真實參數為中心的函數，此種性質稱為貝葉斯學習,一維正態(tài)分布下的貝葉斯學習,在貝葉斯估計中，當求出的后驗概率之后，直接去推導總體分布即 當觀察一個樣本時，N=1就會有一個的估計值的修正值 當觀察N=4時，對進行修正，向真正的靠近 當觀察N=9時，對進行修正，向真正的靠的更近 當N,N就反映了觀察到N個樣本后對的最好

10、推測，而N2反映了這種推測的不確定性 N,N2,N2 隨觀察樣本增加而單調減小，且當N, N2 0 當N，P(|xi)越來越尖峰突起N, P(|xi)函數，這個過程成為貝葉斯學習,類概率密度的估計 在求出u的后驗概率P(|X)后，可以直接利用式 推斷類條件概率密度。 即P(x|X) P(x|i ，X) 一維正態(tài)：已知2，未知 的后驗概率為,結論： 把第i類的先驗概率P(i)與第i類概率密度P(x|xi)相乘可以 得到第i類的后驗概率P(i/x) ，根據后驗概率可以分類。 對于正態(tài)分布P(x|xi)，用樣本估計出來的N代替原來的 用 代替原來的方差 即可。 把估計值N作為的實際值，那么使方差由原

11、來的 變 為 ,使方差增大,參數估計的缺點,參數估計要求密度函數的形式已知，但這種假定有時并不成立，我們不知道總體分布的函數形式 經典的密度函數都是單峰的，而在許多實際情況中卻是多峰的，很難擬合實際的概率密度 上述2種情況下，將不能使用參數估計，因此用非參數估計,非參數估計,直接用已知類別樣本去估計總體密度分布，方法有： 用樣本直接去估計類概率密度p(x/i)以此來設計分類器,如窗口估計 用學習樣本直接估計后驗概率p(i/x)作為分類準則來設計分類器，如k近鄰法.,非參數估計原理,設樣本x落入區(qū)域R的概率P p(x)為x的總體概率密度函數，若從概率密度函數為p(x)的總體中獨立抽取N個樣本x1

12、,x2,xN，其中k個樣本落入區(qū)域R的概率符合二項分布： 可以證明，下式是P的一個較好的估計,設區(qū)域R足夠小，其體積為V， 為概率密度函數p(x)的估計,p(x)連續(xù)且在R上無變化，則： 與樣本數N、區(qū)域R的體積V、落入V中的樣本數k有關，它是的一個空間平均估計, 當V固定的時候N增加, k也增加,當N時，N，此時P=k/N1， 只反映了P(x)的空間平均估計，而反映不出空間的變化 N固定,體積變小，當V0時 k0時： k0時： 所以起伏比較大,噪聲比較大,需要對V進行改進.,對體積V的改進,為了估計x點的密度,我們構造一串包括X的區(qū)域序列R1,R2,. RN，對R1采用一個樣本進行估計，對R

13、2采用二個樣本進行估計。 設VN是RN的體積，KN是N個樣本落入VN的樣本數則密度的第N次估計：,若pN(x)收斂于p(x)應滿足三個條件： ，當N時，VN，N，VN0 這時雖然樣本數多，但由于VN，落入VN內的樣本KN 也減小，所以空間變化才反映出來 ，N ，kN ，N與KN同相變化 ，KN的變化遠小于N的變化。 因此盡管在R內落入了很多的樣本，但同總數N比較, 仍然是很小的一部分。,兩種非參數估計方法,如何選擇VN滿足以上條件： Parzen窗口法：使體積VN以N的某個函數減小， (h為常數) KN近鄰法：使KN作為N的某個函數，例 VN的選擇使RN正好包含KN個近鄰,Parzen窗口估計

14、,假設RN為一個d維的超立方體，hN為超立方體的長度 超立方體體積為： ， d=1，窗口為一線段 d=2，窗口為一平面 d=3，窗口為一立方體 d3，窗口為一超立方體 窗口的選擇：,方窗函數,指數窗函數,正態(tài)窗函數,(u),(u),(u),hN,正態(tài)窗函數, (u) 是以原點x為中心的超立方體。 在xi落入方窗時，則有 在VN內為1 不在VN內為0 落入VN的樣本數為所有為1者之和 密度估計,討論： 每個樣本對估計所起的作用依賴于它到x的距離，即 | x-xi|hN/2時， xi在VN內為1，否則為0。 稱為 的窗函數，取0，1兩種值，但有 時可以取0, 0.1, 0.2多種數值，例如隨xi離

15、x接近的程 度， 取值由0, 0.1, 0.2到1。, 要求估計的PN(x)應滿足： 為滿足這兩個條件，要求窗函數滿足： 窗長度hN對PN(x)的影響 若hN太大, PN(x)是P(x)的一個平坦, 分辨率低的估計, 有平均誤差 若hN太小, PN(x)是P(x)的一個不穩(wěn)定的起伏大的估計,有噪聲誤差 為了使這些誤差不嚴重， hN應很好選擇,例1：對于一個二類（ 1 ，2 ）識別問題，隨機抽取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)窗函數,

16、0,1,2,3,4,5,6,x6,x5,x3,x1,x2,x4,x,x是一維的 上式用圖形表示是6個分別以3.2，3.6，3，6，2.5，1.1為中 心的丘形曲線(正態(tài)曲線)，而PN(x)則是這些曲線之和。,由圖看出，每個樣本對估計的貢獻與樣本間 的距離有關，樣本越多， PN(x)越準確。,例2：設待估計的P(x)是個均值為0，方差為1的一維正態(tài)密度函數。若隨機地抽取X樣本中的1個、 16個、 256個作為學習樣本xi,試用窗口法估計PN(x)。 解：設窗口函數為正態(tài)的， 1，0 hN:窗長度，N為樣本數，h1為選定可調節(jié)的參數。,討論：由圖看出, PN(x)隨N, h1的變化情況 當N1時，

17、 PN(x)是一個以第一個樣本為中心的正態(tài)形狀的小丘，與窗函數差不多。 當N16及N=256時 h10.25 曲線起伏很大，噪聲大 h11 起伏減小 h14 曲線平坦，平均誤差 當N時， PN(x)收斂于一平滑的正態(tài)曲線， 估計曲線較好。,關于Parzen窗口法的結論,結論： 由上例知窗口法的優(yōu)點是應用的普遍性。對規(guī)則分布，非規(guī)則分布，單鋒或多峰分布都可用此法進行密度估計。 要求樣本足夠多，才能有較好的估計。因此使計算量，存儲量增大。 在窗口法中存在一個問題是對hN的選擇問題。若hN選太小，則大部分體積將是空的（即不包含樣本），從而使PN(x)估計不穩(wěn)定。若hN選太大，則PN(x)估計較平坦，反映不出總體分布的變化,kN-近鄰估計,KN近鄰法的思想是以x為中心建立空胞，使v，直到捕捉到KN個樣本為止，稱KN-近鄰估計 v的改進，樣本密度大，VN