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

第二章

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

Classifiers

BasedonBayesDecisionTheory目前一頁\總數(shù)五十九頁\編于十六點§1引言§2

Bayes決策理論最小錯誤率的貝葉斯決策最小風險的貝葉斯決策§3

Bayes分類器和判別函數(shù)§4

正態(tài)分布的Bayes決策

目前二頁\總數(shù)五十九頁\編于十六點§1引言模式識別是根據(jù)對象特征值將其分類。

d個特征組成特征向量x=[x1,···,xd]T，生成d維特征空間，在特征空間一個

x稱為一個模式樣本。Bayes決策理論是用概率統(tǒng)計方法研究決策問題。⒈為什么可用Bayes決策理論分類？⑴樣本的不確定性：①樣本從總體中抽取，特征值都是隨機變量，在相同條件下重復觀測取值不同，故x為隨機向量。②特征選擇的不完善引起的不確定性；③測量中有隨機噪聲存在。目前三頁\總數(shù)五十九頁\編于十六點⑵另一方面從樣本的可分性來看：當各類模式特征之間有明顯的可分性時，可用直線或曲線(面)設計分類器，有較好的效果。當各類別之間出現(xiàn)混淆現(xiàn)象時，則分類困難。

這時需要采用統(tǒng)計方法，對模式樣本的統(tǒng)計特性進行觀測，分析屬于哪一類的概率最大。此時要按照某種判據(jù)分類，如，分類錯誤發(fā)生的概率最小，或在最小風險下進行分類決策等。目前四頁\總數(shù)五十九頁\編于十六點⒉三個重要的概率和概率密度先驗概率、類條件概率密度函數(shù)、后驗概率。⑴先驗概率P(wi)

由樣本的先驗知識得到先驗概率，可從訓練集樣本中估算出來。例如，兩類10個訓練樣本，屬于w1為2個，屬于w2為8個，則先驗概率P(w1)=0.2，P(w2)=0.8。⑵類條件概率密度函數(shù)p(x|wi)

模式樣本x在wi類條件下，出現(xiàn)的概率密度分布函數(shù)。也稱p(x|wi)為wi

關于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決策理論分類時要求：①各類總體的概率分布是已知的。②要決策的類別數(shù)c是一定的。目前六頁\總數(shù)五十九頁\編于十六點§2

Bayes

決策理論1.Bayes公式，也稱Bayes法則

2.Bayes分類規(guī)則：用后驗概率分類目前七頁\總數(shù)五十九頁\編于十六點類條件概率密度后驗概率上圖目前八頁\總數(shù)五十九頁\編于十六點目前九頁\總數(shù)五十九頁\編于十六點3.最小錯誤率的Bayes

決策⑴為什么這樣分類的結果平均錯誤率最小？在一維特征空間中，t為兩類的分界面分成兩個區(qū)域R1和R2，R1為(－∞,t)；R2為(t,∞)。

R1區(qū)域所有x值：分類器判定屬于w1類；

R2區(qū)域所有x值：分類器判定屬于w2類。判斷錯誤的區(qū)域為陰影包圍的面積。x0目前十頁\總數(shù)五十九頁\編于十六點判定錯誤區(qū)域及錯誤率真實狀態(tài)w2，而把模式x判定屬于w1類真實狀態(tài)w1，而把模式x判定屬于w2類平均錯誤率P(e)決策規(guī)則實際上對每個x都使

p(e|x)取小者，移動決策面t

都會使錯誤區(qū)域增大，因此平均錯誤率最小。目前十一頁\總數(shù)五十九頁\編于十六點⑵錯誤率計算：多類時，特征空間分割成R1,···Rc

，P(e)由c×(c-1)項組成，計算量大。用平均正確分類率P(c)計算只有c項：目前十二頁\總數(shù)五十九頁\編于十六點

例1：細胞識別已知：正常類P(w1)＝0.9;異常類P(w2)＝0.1

待識別細胞x,從類條件概率密度曲線上查得

p(x|w1)＝0.2;p(x|w2)＝0.4

這種規(guī)則先驗概率起決定作用。這里沒有考慮錯誤分類帶來的損失。目前十三頁\總數(shù)五十九頁\編于十六點4.最小風險的Bayes決策⑴把分類錯誤引起的“損失”加入到決策中去。決策論中：采取的決策稱為動作，用ai表示；每個動作帶來的損失，用l表示。歸納數(shù)學符號：目前十四頁\總數(shù)五十九頁\編于十六點

一般用決策表或損失矩陣表示上述三者關系。

決策表表示各種狀態(tài)下的決策損失，如下表：目前十五頁\總數(shù)五十九頁\編于十六點由于引入了“損失”的概念(即在錯判時造成的損失)，不能只根據(jù)后驗概率來決策，必須考慮所采取的決策是否使損失最小。對于給定的x，決策ai，l可在c個l(ai,wj)中選一個，其相應的后驗概率為P(wj|x)。此時的條件期望損失，即后驗概率加權和在決策論中條件期望損失稱為條件風險，即x被判為i類時損失的均值。由于x是隨機向量的觀察值，不同的x采取不同決策ai，其條件風險的大小是不同的。目前十六頁\總數(shù)五十九頁\編于十六點

決策a可看成隨機向量x的函數(shù)，記為a(x)，它本身也是一個隨機變量。定義期望風險R

dx是d維特征空間的體積元，積分在整個特征空間。期望風險R反映對整個特征空間上所有x的取值都采取相應的決策a(x)所帶來的平均風險；而條件風險R(ai|x)只反映觀察到某一x的條件下采取決策ai

所帶來的風險。如果采取每個決策行動ai使條件風險R(ai|x)最小，則對所有的x作出決策時，其期望風險R也必然最小。這就是最小風險Bayes決策。目前十七頁\總數(shù)五十九頁\編于十六點⑵最小風險的Bayes決策規(guī)則：目前十八頁\總數(shù)五十九頁\編于十六點如果只有兩類的情況下這時最小風險的Bayes決策法則為：如果R(a1|x)<R(a2|x),則x的真實狀態(tài)w1,否則w2。兩類時最小風險Bayes決策規(guī)則的另兩種形式：

目前十九頁\總數(shù)五十九頁\編于十六點例2：條件同例1，利用決策表，按最小風險Bayes決策分類。

這里決策與例1結論相反為異常細胞。因損失起了主導作用。l不易確定，要與有關專家商定。

目前二十頁\總數(shù)五十九頁\編于十六點

例3：現(xiàn)有兩類問題，比較兩種Bayes決策。已知：單個特征變量x為正態(tài)分布兩類方差都為s2=1/2,均值分別為m=0,1

即求：①若先驗概率P(w1)=P(w2)=1/2，計算最小錯誤率情況下的閾值x0。②如果損失矩陣為

計算最小風險情況下的閾值x0。目前二十一頁\總數(shù)五十九頁\編于十六點①最小錯誤概率情況下閾值x0

(取對數(shù)運算)

②最小風險情況下閾值x0

如果這兩類不是等概率，

P(w1)<P(w2),閾值左移也就是說擴大最大可能類的區(qū)域。可能性大的類可產生更小的誤差。閾值左移目前二十二頁\總數(shù)五十九頁\編于十六點⑶拒絕決策在某些情況下拒絕決策比錯誤判別風險要小。樣本x在各種判別條件下的平均風險當i=c+1時，如果R(ac+1|x)<R(ai|x),i=1,2,···,c則對x作出拒絕判別。若此時各類拒絕判別風險相同，即都為lz，則則拒絕判別的條件為

lz<R(ai|x),i=1,2,···,c。目前二十三頁\總數(shù)五十九頁\編于十六點5.兩種Bayes決策關系①多類問題中，若損失函數(shù)為0—1時

目前二十四頁\總數(shù)五十九頁\編于十六點②兩類問題中，若有即所謂對稱損失函數(shù)的情況下，這時最小風險的Bayes決策和最小錯誤概率的Bayes決策方法相同。6.此外還有下列三種主要的決策方法：聶曼－皮爾遜決策：兩類模式中，一類錯誤率為常數(shù)，另一類錯誤率達到極小值時的決策。最大最小決策：考慮到先驗概率有可能改變的分類方法。選擇風險為最大時的P(w)來設計。序貫分類決策：考慮特征的獲取要付出一定的代價。先用一部分特征來分類，逐步加入特征以減少分類損失。目前二十五頁\總數(shù)五十九頁\編于十六點§3

Bayes分類器和判別函數(shù)c類的分類問題，就是按決策規(guī)則將d維特征空間劃分為c個決策區(qū)域，其邊界稱為決策面，用決策面方程表示。用于表示決策規(guī)則的函數(shù)稱為判別函數(shù)

g(x)

。c個類就有c個由d個特征組成的單值函數(shù)，即判別函數(shù)g(x)

。1.Bayes決策中的判別函數(shù)

gi(x)=P(wi|x)最小錯誤概率的決策規(guī)則

gi(x)=-R(ai|x)最小風險的決策規(guī)則

決策規(guī)則：

gi(x)>gj(x)所有i≠j

則x∈wi

目前二十六頁\總數(shù)五十九頁\編于十六點兩類情況下，設最小錯誤率的Bayes決策規(guī)則的四種等價形式后驗概率類條件概率密度函數(shù)與先驗概率似然比似然比取對數(shù)目前二十七頁\總數(shù)五十九頁\編于十六點多類情況下，設最小錯誤率的Bayes決策規(guī)則的四種等價形式目前二十八頁\總數(shù)五十九頁\編于十六點2.決策面方程各決策域R被決策面所分割，這些決策面是特征空間中的點、直線、超曲面，相鄰的兩個決策域在決策面上其判別函數(shù)相等。決策面方程應滿足

gi(x)=gj(x)gij(x)=gi(x)－gj(x)=0i≠j

且i與j為相鄰的兩類。一維、三類二維、二類目前二十九頁\總數(shù)五十九頁\編于十六點只有兩類的分界面：

x為一維，決策面為一分界點；如圖(a)

x為二維，決策面為一曲線；如圖(b)

x為三維，決策面為一曲面；

x為d維，決策面為一超曲面(b)目前三十頁\總數(shù)五十九頁\編于十六點3.分類器設計在d維特征空間內，劃分為c個決策區(qū)域。⑴多類：根據(jù)各類訓練集樣本x計算得到c個判別函數(shù)gi，將待分樣本計算gi，從中選擇最大值作為類決策。分類器可看成由硬件或軟件組成的一個“機器”。目前三十一頁\總數(shù)五十九頁\編于十六點⑵兩類：兩類分類器可看作只是對x計算判別函數(shù)的一個“機器”，根據(jù)計算結果的符號將x分類。目前三十二頁\總數(shù)五十九頁\編于十六點例4對例1和例2分別列出判別函數(shù)和決策面方程例1.判別函數(shù)

決策面方程

例2.判別函數(shù)

決策面方程：目前三十三頁\總數(shù)五十九頁\編于十六點§4正態(tài)分布的Bayes決策

大量隨機變量服從正態(tài)分布,而且數(shù)學上容易處理,因此以正態(tài)分布為例來說明。1.正態(tài)分布函數(shù)和性質⑴單變量的正態(tài)分布概率密度函數(shù)

性質：p(x)由m,s2確定。隨機變量

x集中在均值m附近,其分散度正比于標準差s,95%樣本落入|x-m|<2s范圍內。目前三十四頁\總數(shù)五十九頁\編于十六點⑵多元(維)正態(tài)分布的概率密度函數(shù)

目前三十五頁\總數(shù)五十九頁\編于十六點⑶多元正態(tài)分布的性質：①參數(shù)m和S決定分布形狀概率密度函數(shù)由d+d(d+1)/2個數(shù)目的參數(shù)唯一確定，其中d為均值數(shù)，d(d+1)/2為協(xié)方差數(shù)。通常記為。②等概率密度點的軌跡為一超橢球面

x大部分落在以均值向量m為中心，大小由協(xié)方差矩陣S確定的區(qū)域。指數(shù)項為常數(shù)的x點即為等概率密度。因此超橢球的方程應是目前三十六頁\總數(shù)五十九頁\編于十六點超橢球主軸方向由S的本征向量確定，其長度與協(xié)方差矩陣的本征值l平方根成正比。證明：中心移到坐標原點m=0，，可用這約束條件構造Lagrange函數(shù)，求極值得到。目前三十七頁\總數(shù)五十九頁\編于十六點

在數(shù)理統(tǒng)計中，定義稱x到m的Mahalanobis(馬氏)距離平方。所以等概率密度點的軌跡是x到μ的馬氏距離為常數(shù)的超橢球面。③在正態(tài)分布中不相關性等價于獨立性。若兩個隨機變量xi和xj間

對多元正態(tài)的任意兩個分量xi和xj來說兩者等價。如果xi和xj是統(tǒng)計獨立，∑中xi

的方差sii2,xi和xj的協(xié)方差sij2,則sij2＝0,∑為對角矩陣。則x=(x1,···,xd)T各分量是相互獨立的正態(tài)分布隨機變量。目前三十八頁\總數(shù)五十九頁\編于十六點④多元正態(tài)分布的邊緣分布和條件分布具有正態(tài)性⑤線性變換的正態(tài)性：

x為多元正態(tài)分布的隨機向量，其均值向量為m，協(xié)方差矩陣為S。對x作線性變換，即

y=AxA為線性變換矩陣，且非奇異，變換后服從均值向量為Am，協(xié)方差矩陣為A∑AT的多元正態(tài)分布。

p(y)~N(Am,A∑AT)

⑥線性組合的正態(tài)性

x為多元分布的正態(tài)隨機向量，則線性組合y=aTx

是一維的正態(tài)隨機變量,a是與x同維向量

p(y)~N(aTm,

aT∑A)目前三十九頁\總數(shù)五十九頁\編于十六點2.正態(tài)分布的最小錯誤率的Bayes分類

條件概密函數(shù)

判別函數(shù)

目前四十頁\總數(shù)五十九頁\編于十六點

決策面方程根據(jù)相鄰的決策域在決策面上的判別函數(shù)相等，下面討論幾種不同的情況：

⑴Si=s2I,i=1,2,···,c⑵Si＝S

⑶Si≠Sj,

i,j=1,2,···,c

目前四十一頁\總數(shù)五十九頁\編于十六點⑴Si=s2I各類模式分布的協(xié)方差矩陣相等，各xi統(tǒng)計獨立且方差相同，協(xié)方差均為0。幾何上相當于各類樣本落在以mi為中心同樣大小的一些超球體中。判別函數(shù)中第二和第三項與類別i無關

若c類先驗概率相等，則gi(x)可忽略最后一項。歐氏距離平方：目前四十二頁\總數(shù)五十九頁\編于十六點Bayes決策：①P(wi)=P(wj)先驗概率相等測量從待分類向量x到每一類均值向量的歐氏距離，把x分到距離最近的類，mi是從訓練樣本集中得到的。也稱最小距離分類器。若把每個均值向量mi看作一個典型的樣本(模板)，則這種分類方法也稱為模板匹配技術。②P(wi)≠P(wj)

歐氏距離的平方必須用方差s2規(guī)范化后減去lnP(wi)再用于分類。因此，如果待分類的向量x

同兩類均值向量的歐氏距離相等，則最小錯誤概率Bayes決策把這模式歸入先驗概率大的那類。目前四十三頁\總數(shù)五十九頁\編于十六點實際使用中不必計算歐氏距離，把gi(x)展開可得這是x的二次函數(shù)，其中xT

x與分類無關

這是與均值有關的線性判別函數(shù)，組成線性分類器。對待分類的樣本x,分別計算gi(x),i=1,2,···,c

gk(x)＝maxgi(x)則決策x∈wki目前四十四頁\總數(shù)五十九頁\編于十六點

決策面方程相鄰決策面方程是由上述線性方程所確定的一個超平面，且討論的是方差相等，協(xié)方差為0這樣一種特殊情況，即。

這個方程確定了決策面是通過x0并正交于向量W的一個超平面。由于W=mi－mj

所以超平面正交于均值向量mi與mj之間的聯(lián)線。目前四十五頁\總數(shù)五十九頁\編于十六點

若先驗概率相等

超平面通過mi與mj聯(lián)線的中點，且與聯(lián)線正交。若先驗概率不相等，則

x0不在中點，超平面向先驗概率小的方向移動。若s2<<||mi-mj||2,則先驗概率對決策面的影響就比較小。d維特征空間，交界面呈球狀分布，其判別邊界為d-1維的平面，垂直于中心線。目前四十六頁\總數(shù)五十九頁\編于十六點一維二維三維目前四十七頁\總數(shù)五十九頁\編于十六點⑵Si＝SS與i無關。各類的協(xié)方差矩陣相等S1＝S2＝···＝Sc=S。幾何上相當于各類樣本集中于以該類均值mi點為中心的同樣大小和形狀的超橢球體中。判別函數(shù)：

若c類先驗概率相等，則

Bayes決策：計算x