基于貝葉斯決策理論的分類器

1、第二章基于貝葉斯決策理論的分類器Classifiers Based on Bayes Decision Theory1 引言2 Bayes決策理論 最小錯誤率的貝葉斯決策 最小風險的貝葉斯決策3 Bayes分類器和判別函數(shù)4 正態(tài)分布的Bayes決策 1 引言 模式識別是根據(jù)對象特征值將其分類。 d個特征組成特征向量x=x1,xdT，生成d 維特征空間，在特征空間一個 x 稱為一個模式樣本。 Bayes決策理論是用概率統(tǒng)計方法研究決策問題。 為什么可用Bayes決策理論分類？ 樣本的不確定性： 樣本從總體中抽取，特征值都是隨機變量，在相同條件下重復觀測取值不同，故x為隨機向量。 特征選擇的不完

2、善引起的不確定性； 測量中有隨機噪聲存在。 另一方面從樣本的可分性來看： 當各類模式特征之間有明顯的可分性時，可用直線或曲線(面)設(shè)計分類器，有較好的效果。 當各類別之間出現(xiàn)混淆現(xiàn)象時，則分類困難。 這時需要采用統(tǒng)計方法，對模式樣本的統(tǒng)計特性進行觀測，分析屬于哪一類的概率最大。此時要按照某種判據(jù)分類，如，分類錯誤發(fā)生的概率最小，或在最小風險下進行分類決策等。 三個重要的概率和概率密度 先驗概率、類條件概率密度函數(shù)、后驗概率。先驗概率 P(wi) 由樣本的先驗知識得到先驗概率，可從訓練集樣本中估算出來。 例如，兩類10個訓練樣本，屬于w1為2個，屬于w2為8個，則先驗概率P(w1) = 0.2，

3、P(w2) = 0.8。 類條件概率密度函數(shù) p(x|wi) 模式樣本x在wi類條件下，出現(xiàn)的 概率密度分布函數(shù)。也稱 p(x|wi) 為wi 關(guān)于x 的似然函數(shù)。 在本章中均假設(shè)已知上述概率和概率密度函數(shù)。后驗概率P(wi|x) 定義為某個樣本 x, 屬于wi 類的概率, i=1,c 。 如果用先驗概率P(wi) 來確定待分樣本x的類別, 依據(jù)顯然是非常不充分的，須用類條件概率密度p(x|wi)來修正。 根據(jù)樣本 x 的先驗概率和類條件概率密度函數(shù)p(x|wi) 用Bayes公式重新修正 模式樣本所屬類的概率，稱 后驗概率P(wi|x)。3.用Bayes決策理論分類時要求：各類總體的概率分布

4、是已知的。要決策的類別數(shù)c是一定的。 2 Bayes 決策理論1. Bayes公式，也稱Bayes法則 2. Bayes分類規(guī)則：用后驗概率分類)()|()()()()|()|()|(),(1iciiiiiiiPxpxpxpPxpxPxpPwwwwwww其中，全概率密度后驗概率為則類條件概率密度函數(shù)已知：先驗概率類屬于則如果類屬于則如果情況下兩類221121，)()( ，)()()2(wwwwwwxxPxPxxPxPc類條件概率密度后驗概率上圖上圖cjixxPxPPPxpxpxlxhPPxlPPxpxpxlPxpPxpxPxPxxijcji, 2 , 1,),|(max)|(Bayes)()(

5、ln)|(ln)|(ln)(ln)()()(,)()()()()()()()|()()|()|()|(Bayes, 1212112122122112121wwwwwwwwwwwwwwwwwwwww則決策：多類問題的稱為似然比閾值稱為似然比統(tǒng)計學中后驗概率，否則策：下述四種等價規(guī)則的決式分類規(guī)則的幾種等價形兩類情況下的)(ln)(xlxh取)()()|()|(BayesxpPxpxPiiiwww公式3. 最小錯誤率的 Bayes 決策為什么這樣分類的結(jié)果平均錯誤率最?。?在一維特征空間中，t 為兩類的分界面分成兩個區(qū)域R1和R2 ， R1為(, t)； R2為(t,)。 R1區(qū)域所有x值： 分類

6、器判定屬于w1類； R2區(qū)域所有x值： 分類器判定屬于w2類。 判斷錯誤的區(qū)域為陰影包圍的面積。cjixPerrorPxxPxPiijcji, 2 , 1,)|(min)(),|(max)|(, 2, 1wwww誤差概率則決策規(guī)則x0 判定錯誤區(qū)域及錯誤率 真實狀態(tài)w2，而把模式x判定屬于w1類 真實狀態(tài)w1，而把模式x判定屬于w2類 平均錯誤率P(e) 決策規(guī)則實際上對每個x都使 p(e|x)取小者，移動決策面 t 都會使錯誤區(qū)域增大，因此 平均錯誤率最小。)|()|()|()|()|()|()|(212121xPxPxPxPxPxPxePwwwwww，當，當)()()()()()()()(

7、)()(1122112221ePPePPePdxxpPdxxpPePRRwwwwww錯誤率計算： 多類時，特征空間分割成 R1, Rc ，P(e) 由c(c-1)項組成，計算量大。 用平均正確分類率P(c)計算只有c 項：)(1)()()|()()|()(11cPePdxPxpPRxPcPjcjRjjcjjji wwww 例1：細胞識別 已知：正常類P(w1)0.9; 異常類P(w2)0.1 待識別細胞 x, 從類條件概率密度曲線上查得 p(x|w1)0.2; p(x|w2)0.4 這種規(guī)則先驗概率起決定作用。這里沒有考慮錯誤分類帶來的損失。121122111121182. 0)|(818.

8、0)|(182. 0)|(1)|(818. 0)()|()()|()|(BayeswwwwwwwwwwwwxxPxPxPxPPxpPxpxPjjj因此的后驗概率和公式分別計算解：利用4. 最小風險的Bayes決策 把分類錯誤引起的“損失”加入到?jīng)Q策中去。 決策論中： 采取的決策稱為動作，用ai表示； 每個動作帶來的損失，用l表示。 歸納數(shù)學符號： 的損失。時，采取的決策為當真實狀態(tài)為表示損失函數(shù)拒絕決策下標組成個決策由決策空間組成類個自然狀態(tài)由狀態(tài)空間，維隨機向量是ijjiacicTdacjaiacaaaaaAaciaaAccxxxxdxwlwlwww, 2 , 1, 2 , 1),()( 1

9、, 2 , 1,)(,212121 一般用決策表或損失矩陣表示上述三者關(guān)系。 決策表表示各種狀態(tài)下的決策損失，如下表：ai xPaaEx a Rcjjjijii, , 2 , 1)( ) , (), ( ) (1wwlwl 由于引入了“損失”的概念 (即在錯判時造成的損失)，不能只根據(jù)后驗概率來決策，必須考慮所采取的決策是否使損失最小。 對于給定的x，決策ai ，l可在c個l(ai,wj)中選一個，其相應的后驗概率為P(wj|x)。 此時的條件期望損失，即后驗概率加權(quán)和 在決策論中條件期望損失稱為條件風險，即x被判為i類時損失的均值。 由于x是隨機向量的觀察值，不同的x采取不同決策ai ，其條

10、件風險的大小是不同的。dxxpxxaRR)()( 決策a可看成隨機向量x的函數(shù)，記為a(x)，它本身也是一個隨機變量。 定義期望風險R dx是d維特征空間的體積元，積分在整個特征空間。 期望風險R反映對整個特征空間上所有x的取值都采取相應的決策a(x)所帶來的平均風險；而條件風險R(ai|x)只反映觀察到某一x的條件下采取決策ai 所帶來的風險。 如果采取每個決策行動ai使條件風險R(ai|x)最小，則對所有的x作出決策時，其期望風險R也必然最小。這就是最小風險Bayes決策。決策。就是最小風險則即決策找出使條件風險最小的進行比較，個條件風險值上式得到的決策的條件風險采取利用決策表，計算出；計

11、算后驗概率公式，由根據(jù)待識別的已知：決策可按下列步驟進行最小風險則對應的決策如果Bayes),|(min)|(,2,1),|(,2,1),|()|()|()|()|(Bayes,),|(),(Bayes),|(min)|(,2,11,2,1kiaikkijcijiiiijjjkiaikaxaRxaRaaixaRaaixPaxaRxaRaxPxxpPaaxaRxaRwwlwww最小風險的Bayes決策規(guī)則：21121121221221212221211121)()()()()()|()()|()(wwwwllllwwwwwllwll；否則則決策，如果；否則則決策，如果PPxpxpxlxPxP 如

12、果只有兩類的情況下 這時最小風險的Bayes決策法則為： 如果R(a1|x) R(a2|x), 則x的真實狀態(tài)w1, 否則w2。 兩類時最小風險Bayes決策規(guī)則的另兩種形式： )|()|()|()|()|()|(22212122121111xPxPxaRxPxPxaRwlwlwlwl182.0)|(,818.0)|(101604.0)|(,2.0)|(1.0)(,9.0)(21222112112121xPxPxpxpPPwwllllwwww得到后驗概率：例已知：例2：條件同例1，利用決策表， 按最小風險Bayes決策分類。 這里決策與例1結(jié)論相反為異常細胞。因損失起了主導作用。l不易確定，要

13、與有關(guān)專家商定。 22112122122111),|() |(818. 0) |() |(092. 1) |() |() |(wwlwlwlxxaRxaRxPxaRxPxPxaRjjj所以由于條件風險)1(exp(1)()exp(1)(2221xxPxxpww類條件概率密度函數(shù) 例3： 現(xiàn)有兩類問題，比較兩種Bayes決策。 已知：單個特征變量x為正態(tài)分布 兩類方差都為s 2=1/2, 均值分別為m = 0,1 即 求： 若先驗概率 P(w1) = P(w2) = 1/2，計算最小錯誤率情況下的閾值 x0。 如果損失矩陣為 015.00l )(21exp21) (2smsxxp計算最小風險情況

14、下的閾值 x0。21)1(exp()exp(022xxx 最小錯誤概率情況下閾值x0 (取對數(shù)運算) 最小風險情況下閾值x0 如果這兩類不是等概率， P(w1) gj(x) 所有ij 則xwi 兩類情況下，設(shè) 最小錯誤率的Bayes決策規(guī)則的四種等價形式后驗概率類條件概率密度函數(shù)與先驗概率似然比似然比取對數(shù) 多類情況下，設(shè) 最小錯誤率的Bayes決策規(guī)則的四種等價形式2. 決策面方程 各決策域R被決策面所分割，這些決策面是特征空間中的點、直線、超曲面，相鄰的兩個決策域在決策面上其判別函數(shù)相等。 決策面方程應滿足 gi (x) = gj (x) gij(x) = gi(x)gj(x)=0 ij

15、且i與j為相鄰的兩類。一維、三類二維、二類 只有兩類的分界面： x為一維，決策面為一分界點；如圖(a) x為二維，決策面為一曲線；如圖(b) x為三維，決策面為一曲面； x為d維，決策面為一超曲面ijiiiiiiiiiixijxgxgPxpxgPxpxgxPxgxgwwwwww屬于，則，對一切如果：三種形式的判別函數(shù)。每個類有一個判別函數(shù))()()(ln)|(ln)()()|()()|()()(b)3. 分類器設(shè)計 在d維特征空間內(nèi)，劃分為c個決策區(qū)域。 多類： 根據(jù)各類訓練集樣本x計算得到c個判別函數(shù)gi，將待分樣本計算gi，從中選擇最大值作為類決策。 分類器可看成由硬件或軟件組成的一個“機

16、器”。）（設(shè)；否則設(shè)屬于，則如果決策規(guī)則同樣有三種形式：判別函數(shù)1)1(0)()()(ln)|()|(ln)()()|()()|()()|()|()()()()()(21212122112121wwwwwwwwwwwwxxgPPxpxpxgPxpPxpxgxPxPxgxgxgxgxg兩類： 兩類分類器可看作只是對x計算判別函數(shù)的一個“機器”，根據(jù)計算結(jié)果的符號將x分類。)| ( 1 . 0)| ( 9 . 0) ()( )| ()( )| () (212211wwwwwwxpxpxgPxpPxpxg0 ) | ( ) | ( 9 ) ( , 0 ) (21wwx px px gx g例4 對例

17、1和例2分別列出判別函數(shù)和決策面方程 例1. 判別函數(shù) 決策面方程 例2. 判別函數(shù) 決策面方程：)|(6.0)|(9.0)()()|()()|()|()|()|()|()(212222112121212112wwwwlwwlwlwlxpxpxgPxpPxpxPxPxaRxaRxg0)|(6)|(9)(21wwxpxpxgdxxpxdxxxpxExxp)()()()(21exp21)(222msmsms方差均值),()(2smNxp記為非對角線上的元素協(xié)方差方差，對角線上的元素對稱矩陣，并且正定的行列式是的逆矩陣，是,)(222222122222212212122111jjiiijiidddd

18、ddxxEmmsssssssssss4 正態(tài)分布的Bayes決策 大量隨機變量服從正態(tài)分布, 而且數(shù)學上容易處理, 因此以正態(tài)分布為例來說明。1.正態(tài)分布函數(shù)和性質(zhì)單變量的正態(tài)分布概率密度函數(shù) 性質(zhì)：p(x)由m, s 2確定。隨機變量 x 集中在均值m附近, 其分散度正比于標準差s, 95%樣本落入|x -m| 2s范圍內(nèi)。維的協(xié)方差矩陣維均值向量維隨機變量式中ddxxEdxEdxxxxxxpTTdTdTd)(,)()(21exp)2 (1)(1112 / 12 /mmmmmmm多元(維)正態(tài)分布的概率密度函數(shù) ), ()(mNxpkxxT)()(1mm多元正態(tài)分布的性質(zhì)： 參數(shù) m m 和

19、 S 決定分布形狀 概率密度函數(shù)由d+d(d+1)/2個數(shù)目的參數(shù)唯一確定，其中d為均值數(shù)，d(d+1)/2為協(xié)方差數(shù)。 通常記為 。 等概率密度點的軌跡為一超橢球面 x大部分落在以均值向量m m為中心，大小由協(xié)方差矩陣S確定的區(qū)域。 指數(shù)項為常數(shù)的x點即為 等概率密度。因此超橢 球的方程應是成比例。矩陣的本征值長度與兩邊矩陣的本征向量方向。主軸方向是，兩邊即超球體主軸的必要條件lllllllllkxxxxxxxxxxxxxLkxxxxxLTTTTT11111,00)(,0022)(),(kxxT 1 超橢球主軸方向由S的本征向量確定，其長度與協(xié)方差矩陣的本征值l平方根成正比。 證明：中心移到

20、坐標原點m=0， ，可用這約束條件構(gòu)造Lagrange函數(shù)，求極值得到。) ( ) (12mmxxrT獨立性條件更強獨立性定義：不相關(guān)性定義：) ( ) () , ( jij ijij ix px px x px Ex Ex x E)(ln|ln212ln221212121)(g)(ln|ln212ln2)()(21)()(ln)|(ln)()|(ln)(11111iiiTiiiTiiiTiTiiiTiiiiiiiiiPdxxxxxPdxxxgPxpPxpxgwmmmmwmmwwww 在數(shù)理統(tǒng)計中，定義 稱x到m 的Mahalanobis(馬氏)距離平方。 所以等概率密度點的軌跡是x到的馬氏

21、距離為常數(shù)的超橢球面。在正態(tài)分布中不相關(guān)性等價于獨立性。 若兩個隨機變量xi和xj間 對多元正態(tài)的任意兩個分量xi和xj來說兩者等價。 如果xi和xj是統(tǒng)計獨立， 中xi 的方差sii2, xi和xj 的協(xié)方差sij2, 則sij20, 為對角矩陣。則 x= (x1,xd)T各分量是相互獨立的正態(tài)分布隨機變量。cixxExExxxpTiiiiiiTiidi1)()()()(21exp21)|(12/12/mmmmmw0)()(ln|ln21)()()()(21,0)()()()(11jijijjTjiiTijijiPPxxxxjixgxgxgxgwwmmmm即相鄰或得到多元正態(tài)分布的邊緣分布和

22、條件分布具有正態(tài)性線性變換的正態(tài)性： x為多元正態(tài)分布的隨機向量，其均值向量為 m m，協(xié)方差矩陣為S。對x作線性變換，即 y = Ax A為線性變換矩陣，且非奇異，變換后服從均值向量為Am，協(xié)方差矩陣為AAT的多元正態(tài)分布。 p(y) N(Am, AAT) 線性組合的正態(tài)性 x為多元分布的正態(tài)隨機向量，則線性組合y=aTx 是一維的正態(tài)隨機變量, a是與x同維向量 p(y)N(aTm, aTA) 2. 正態(tài)分布的最小錯誤率的Bayes分類 條件概密函數(shù) 判別函數(shù) 2200ss)(ln2|)(22iiiPxxgwsm 決策面方程 根據(jù)相鄰的決策域在決策面上的判別函數(shù)相等， 下面討論幾種不同的情

23、況： Si=s 2I, i =1, 2,c SiS SiSj , i, j =1, 2,c 212)()()(|ijdjjiTiixxxxmmmm Si=s2I 各類模式分布的協(xié)方差矩陣相等，各xi統(tǒng)計獨立且方差相同，協(xié)方差均為0。幾何上相當于各類樣本落在以mi為中心同樣大小的一些超球體中。判別函數(shù)中第二和第三項與類別i無關(guān) 若c類先驗概率相等，則gi(x)可忽略最后一項。) ( ln| | ln212 ln2) ) ( )(21) (1iiTii iiPdxxx gwmm 212/ I,ssidi2,1minicixm)(ln)2(21)(2iiTiTiTiPxxxxgwmmms02)(ln

24、)2(21)(iTiiiTiTiiwxWPxxgwmmms歐氏距離平方： Bayes 決策： P(wi)= P(wj) 先驗概率相等 測量從待分類向量x到每一類均值向量的歐氏距離，把x分到距離最近的類， mi是從訓練樣本集中得到的。也稱最小距離分類器。 若把每個均值向量m mi看作一個典型的樣本(模板)，則這種分類方法也稱為模板匹配技術(shù)。 P(wi)P(wj) 歐氏距離的平方必須用方差s2規(guī)范化后減去lnP(wi)再用于分類。因此，如果待分類的向量x 同兩類均值向量的歐氏距離相等，則最小錯誤概率Bayes決策把這模式歸入先驗概率大的那類。 )(ln21,1)(2020iiTiiiiiTiiPw

25、WwxWxgwmmsms其中 實際使用中不必計算歐氏距離，把gi(x)展開可得 這是x的二次函數(shù)， 其中xT x與分類無關(guān) 這是與均值有關(guān)的線性判別函數(shù)，組成線性分類器。 對待分類的樣本x,分別計算 gi(x),i=1,2,c gk(x)max gi(x) 則決策 xwk)()()(ln|)(210)(0)()(200jijijijijiTjiPPxWxxWxgxgmmwwmmsmmmm其中Ii2si 決策面方程 相鄰決策面方程是由上述線性方程所確定的一個超平面，且討論的是方差相等，協(xié)方差為0這樣一種特殊情況，即 。 這個方程確定了決策面是通過x0并正交于向量W的一個超平面。由于W=m mim

26、 mj 所以超平面正交于均值向量m mi與m mj之間的聯(lián)線。)(21)()(0jijixPPmmww)(ln)()(21) (1iiTiiPxxxgwmm)()() (12iTiixxrxgmm 若先驗概率相等 超平面通過mi與mj聯(lián)線的中點，且與聯(lián)線正交。 若先驗概率不相等，則 x0 不在中點，超平面向先驗概率小的方向移動。 若s2 |mi-mj|2,則先驗概率對決策面的影響就比較小。 d 維特征空間，交界面呈球狀分布，其判別邊界為d-1維的平面，垂直于中心線。)(0)(0)()(10jiTjiWxxWxgxgmm其中)(ln21,) (1010iiTiiiiiTiiPwWwxWxgwmm

27、m其中一維 二維 三維)(ln21,) (1010iiTiiiiiTiiPwWwxWxgwmmm其中)(ln21,) (1010iiTiiiiiTiiPwWwxWxgwmmm其中)(ln21,) (1010iiTiiiiiTiiPwWwxWxgwmmm其中 SiS S與i無關(guān)。 各類的協(xié)方差矩陣相等S1S2Sc=S。幾何上相當于各類樣本集中于以該類均值mi點為中心的同樣大小和形狀的超橢球體中。 判別函數(shù)： 若c類先驗概率相等，則 Bayes決策： 計算x到每類均值點m mi的馬氏距離平方r2, 將x分到距離最近的類中去，或歸于r2最小的類。)()()()(/ )(ln)(2110jijiTjijijippxmmmmmmwwmm 展開后, 忽略與i無關(guān)項xTS-1x，則判別函數(shù) 線性判別函數(shù)，因此決策面仍是一個超平面。 相鄰決策面方程 W不在(mi-mj)方向上，超平面通過x0點但不與均值向量連線正交。 TT33009 . 13 . 03 . 01 . 121mm672.38.00.255.015.015.095.08.00.2)()(),(955.015.015.095.02.20.1)()(),(2122211112mmmmmmxxxrxxxrTT0)()(x