1、Made in CV&PRLab of Shandong University,隨機模式的分類方法,第2章,該方法基于貝葉斯決策理論，往往以某種概率的形式給出。本章首先介紹貝葉斯分類方法中的一般性的判決規(guī)則，并且抽象出隨機模式的判決函數(shù)和決策面方程，給出2種分類器結構。,Made in CV&PRLab of Shandong University,目 錄,2.1 引言,1,2.2 最小錯誤率判決規(guī)則（最簡單的Bayes分類方法）,2,2.3 最小風險判決規(guī)則,3,2.4 最大似然比判決規(guī)則,4,2.5 Neyman-Pearsen判決規(guī)則- 有時不知道先驗概率，僅知道類概率密度,5,2.6

2、最小最大判決規(guī)則-先驗概率是變化的,6,2.7 分類器設計,6,Made in CV&PRLab of Shandong University,2.1 引言,隨機模式 在可以覺察到的客觀世界中，存在著大量的物體和事件，他們在基本條件不變時，具有某種不確定性，每一次觀測的結果沒有重復性，這種模式就是隨機模式。 雖然隨機模式樣本測量值具有不確定性，但同類抽樣實驗的大量樣本的觀測值具有某種統(tǒng)計特性，這個統(tǒng)計特性是建立各種分類方法的基本依據(jù)。 先看一下確定性模式判決函數(shù)的問題。,Made in CV&PRLab of Shandong University,2.1 引言,通過判決函數(shù)，特征空間 被區(qū)分

3、界面劃分成兩種類型的區(qū)域A和B。由于模式樣本的觀測值是確定性的，經(jīng)常被正確分配到類型區(qū)域A、B之中。 假如我們用概率的形式來表達，就是：在類型A的條件下觀測模式樣本x，則x位于區(qū)域A的概率為1，而位于區(qū)域B的概率為0。 同樣，在類型B的條件下觀測模式樣本x，情況正好相反，x位于區(qū)域A的概率為0，而位于區(qū)域B的概率為1。這實際上是將概率的方法引入到確定模式，對于大多數(shù)實際情況，這是非常理想的概率分布。,Made in CV&PRLab of Shandong University,許多實際情況，即使在類型A的條件下，模式樣本x位于區(qū)域A的概率也往往小于1，而位于區(qū)域B的概率也不為0。對于類型B的

4、條件也一樣。這種交錯分布的樣本使分類發(fā)生錯誤，是模式隨機性的一種表現(xiàn)。此時，分類方法就從確定性模式轉到隨機模式。 “如何使分類錯誤率盡可能小，是研究各種分類方法的中心議題?！?2.1 引言,Made in CV&PRLab of Shandong University,Bayes決策理論是隨機模式分類方法最重要的基礎。 其中幾個重要的概念： 先驗概率 先驗概率是預先已知的或者可以估計的模式識別系統(tǒng)位于某種類型的概率。 類（條件）概率密度 它是系統(tǒng)位于某種類型條件下，模式樣本x出現(xiàn)的概率密度分布函數(shù) 后驗概率 后驗概率可以根據(jù)貝葉斯公式計算出來，可直接用作分類判決的依據(jù)。,2.1 引言,Made

5、 in CV&PRLab of Shandong University,先驗概率 先驗概率是預先已知的或者可以估計的模式識別系統(tǒng)位于某種類型的概率。 若仍然用兩個類型A和B為例，可用 和 表示各自的先驗概率，此時滿足 。 推廣到一般的c類問題中，用 表示類型，則各自的先驗概率用 表示，且滿足： 其實，在處理實際問題時，有時不得不以先驗概率的大小作為判決的依據(jù)。如：有一批木材，其中樺木占70，松木占30，A樺木，B松木，則，如果從中任取一塊木材，而又要用先驗概率作出判決，那就判為樺木。 先驗概率不能作為判決的唯一依據(jù)， 但當先驗概率相當大時，它也能成為主要因素。,2.1 引言,Made in C

6、V&PRLab of Shandong University,2.1 引言,2類（條件）概率密度 它是系統(tǒng)位于某種類型條件下，模式樣本x出現(xiàn)的概率密度分布函數(shù)，常用 ，以及 來表示。 先驗概率密度在分類方法中起至關重要的作用，它的函數(shù)形式及主要參數(shù)或者是已知的，或者是可通過大量抽樣實驗估計出來。 3. 后驗概率 它是系統(tǒng)在某個具體的模式樣本x條件下，位于某種類型的概率，常以 ，以及 表示。 后驗概率可以根據(jù)貝葉斯公式計算出來，可直接用作分類判決的依據(jù)。 例如：一個2類問題，w1表示診斷為無癌癥，w2診斷為有癌癥。P(w1) 表示診斷正常的概率，P(w2) 表示某地區(qū)的人被診斷出患上癌癥的概率，

7、該值可以通過大量的統(tǒng)計得到，x表示“試驗反應呈陽性”。那么，P(x|w1)表示診斷為無癌癥且試驗反應為陽性，P(w1|x)表示試驗為陽性，而且沒有癌癥。同樣，可以有w2的類概率密度和后驗概率。,Made in CV&PRLab of Shandong University,2.2 最小錯誤率判決規(guī)則（最簡單的Bayes分類方法）,分析一個“兩類問題”。 以上一個例子為例，用w1和w2表示兩種不同的類型，如w1表示診斷正常，w2表示診斷出患有癌癥。 用 和 分別表示先驗概率。如： 診斷正常的概率， 表示某地人患癌癥的概率，可通過大量的統(tǒng)計得到。 用 和 表示兩個類概率密度。 樣本x表示“試驗反應

8、陽性”，則 診斷為無癌癥且試驗反應為陽性， 試驗為陽性且沒有癌癥。 根據(jù)全概率公式，模式樣本x出現(xiàn)的全概率密度為：,（2.21）,根據(jù)Bayes公式，在模式樣本x出現(xiàn)的條件下，兩個類型的后驗概率為：,（2.22）,Made in CV&PRLab of Shandong University,此時，樣本歸屬于“后驗概率較高”的那種類型。 也就是：,，則偶然決定,，或,（2.23）,，則,，則,根據(jù)（2.22）式，上述判決規(guī)則等價于：,，則,，則,（2.24）,，則偶然決定,，或,上面只是給出了最小錯誤率貝葉斯決策規(guī)則，但沒有證明按這種規(guī)則進行分類確實使錯誤率最小。,2.2 最小錯誤率判決規(guī)則,

9、Made in CV&PRLab of Shandong University,下面用一維情況來證明最小錯誤率貝葉斯決策規(guī)則，其結果不難推廣到多維。,如下圖所示，在一維特征空間里，判決門限t把空間劃分為兩個類型區(qū)域R1，R2,在R1中，,，則,在R2中，,，則,；,；,陰影區(qū)域是兩類樣本的交錯分配區(qū)域，陰影面積就是這種分類方法的錯誤概率。,2.2 最小錯誤率判決規(guī)則,Made in CV&PRLab of Shandong University,總錯誤率有兩種情況：,，而判為,，斜線區(qū)域。,，而判為,所以，總錯誤率：,，紋線區(qū)域。,其中，,表示在整個d維特征空間上的積分。,對上述兩類問題：當,

10、時，則,顯然作出決策w2時，x的條件錯誤概率為,，反之為,。,。,也就是：,=,2.2 最小錯誤率判決規(guī)則,Made in CV&PRLab of Shandong University,若令t為兩類分界面，特征向量x為一維時，t為x軸上的一個點，如上圖所示：,也可寫為：,2.2 最小錯誤率判決規(guī)則,Made in CV&PRLab of Shandong University,所以要使 最小，判決門限應如上圖所示，否則就會有多余的陰影面。 而（2.2-3）、（2.2-4）表達的判決規(guī)則，判決門限正好如上圖所示，所以稱 之為“最小錯誤概率判決規(guī)則”。,2.2 最小錯誤率判決規(guī)則,Made in

11、 CV&PRLab of Shandong University,可以把上述兩類問題導出的最小錯誤率判決規(guī)則一般化，推廣到c類問題中，表達為：,若：,，則,等價于：,，則,2.2 最小錯誤率判決規(guī)則,例1：為了對癌癥進行診斷，對一批人進行一次普查，各每個人打試驗針， 觀察反應，然后進行統(tǒng)計，規(guī)律如下： 這一批人中，每1000個人中有5個癌癥病人； 這一批人中，每100個正常人中有一個試驗呈陽性反應； 這一批人中，每100個癌癥病人中有95人試驗呈陽性反應。 問：若某人（甲）呈陽性反應，甲是否正常？,Made in CV&PRLab of Shandong University,2.2 最小錯誤

12、率判決規(guī)則,解：假定x表示實驗反應為陽性， (1)人分為兩類：w1正常人，w2癌癥患者， (2)由已知條件計算概率值： 先驗概率： 類條件概率密度： (3)決策過程,由最小錯誤判決規(guī)則，可知： 由于 比 大很多， 所以先驗概率起了較大作用。,Made in CV&PRLab of Shandong University,2.3 最小風險判決規(guī)則,最小風險判決規(guī)則也是一種Bayes分類方法。最小錯誤率判決規(guī)則沒有考慮 錯誤判決帶來的“風險”，或者說沒有考慮某種判決帶來的損失。 同一問題中，某種判決總會有一定的損失，特別是錯誤判決有風險。不同的 錯誤判決有不同的風險，如上一節(jié)的例子中，判斷細胞是否

13、為癌細胞，可能有兩 種錯誤判決： 正常細胞錯判為癌細胞； 癌細胞錯判為正常細胞。 兩種錯誤帶來的風險不同。在中，會給健康人帶來不必要的精神負擔， 在中，會使患者失去進一步檢查、治療的機會，造成嚴重后果。顯然，第種 錯誤判決的風險大于第種。 判決風險也可以理解為判決損失，即使在正確判決的情況下，一般也會付出 某種代價，也會有損失。正是由于有判決風險的存在，最小錯誤率判決就不夠了， 必須引入最小風險判決規(guī)則。,Made in CV&PRLab of Shandong University,假定有c類問題，用,表示類型，用,表示可能作出的判決。實際應用中，判決數(shù)a和類型數(shù)c可能相等，,也可能不等，即

14、允許除c類的c個決策之外，可以采用其它決策， 如“拒絕”決策，此時,。,；,對于給定的模式樣本x，令,表示,而判決為,的風險。若判決,一定，對c個不同類型的,，有c個不同的,。,2.3 最小風險判決規(guī)則,Made in CV&PRLab of Shandong University,維風險矩陣。,的c個離散值隨類型的性質變化，具有很大的隨機性，可看成是隨機變量。 另外，由于判決數(shù)目有a個，這樣對于不同的判決和不同類型就有一個,一般風險矩陣,2.3 最小風險判決規(guī)則,Made in CV&PRLab of Shandong University,假定某樣本x的后驗概率,已經(jīng)確定，則有：,對于每一

15、種判決,，可求出隨機變量,的條件平均風險，也叫“條件平均損失”：,（2.3-1）,最小風險判決規(guī)則就是把樣本x歸屬于“條件平均風險最小”的那一種判決。也就是：,若,，則,(2.3-2),2.3 最小風險判決規(guī)則,Made in CV&PRLab of Shandong University,實施最小風險判決規(guī)則的步驟如下：,(1) 在給定樣本x條件下，計算各類后驗概率,，,。,(2) 按照(2.3-1)式求各種判決的條件平均風險,，,為此，需要知道風險矩陣。,按照(2.3-2）式，比較各種判決的條件平均風險，把樣本x歸屬于 條件平均風險最小的那一種判決。,2.3 最小風險判決規(guī)則,Made i

16、n CV&PRLab of Shandong University,2.3 最小風險判決規(guī)則,和,。,解：從風險矩陣中得到：,將例1中計算出的后驗概率：,代入2.3-1式：,根據(jù)最小風險判決規(guī)則，,即試驗人屬于癌癥病人，與例1 的 結論相反。,例2：在例1的癌癥診斷問題中，所有的化驗結果可分為兩類。 w1正常，w2癌癥。 得到的判決也有兩種,Made in CV&PRLab of Shandong University,2.3 最小風險判決規(guī)則,注意：實際工作中，列出合適的風險矩陣很不容易，要根據(jù)研究的具問題， 分析錯誤決策造成損失的嚴重程度，與有關專家共同商討決定。,上面分析了兩種決策規(guī)則，

17、下面討論它們之間的關系：,判決風險又叫判決損失，,又叫損失函數(shù)。,現(xiàn)假設正確判決損失為0，錯誤判決損失為1，且判決數(shù)目與類型數(shù)目相等。 即有01損失函數(shù)：,Made in CV&PRLab of Shandong University,2.3 最小風險判決規(guī)則,代入式(2.3-1)，有：,結果代入式(2.3-2)中，得到：,若,，則,這就是最小錯誤率判決規(guī)則。 結論：在01損失函數(shù)情況下，最小風險判決規(guī)則退化為最小錯誤率判決規(guī)則。 也就是說，最小錯誤率判決規(guī)則是最小風險判決規(guī)則的一個特例。,Made in CV&PRLab of Shandong University,2.4 最大似然比判決規(guī)

18、則,0,類概率密度,又稱為“似然函數(shù)”，兩個類概率密度之比稱為“似然比函數(shù)”。,最大似然比判決規(guī)則也是一種Bayes分類方法。描述：,類型,分別與其它類型,的似然比均大于相應的門限值，,分別與,的似然比均小于相應的門限值，則樣本,。,而其它類型,（1）由最小錯誤率判決規(guī)則引出最大似然比判決規(guī)則,（2）由最小風險判決規(guī)則引出最大似然比判決規(guī)則,Made in CV&PRLab of Shandong University,2.4 最大似然比判決規(guī)則,0,（1）由最小錯誤率判決規(guī)則引出最大似然比判決規(guī)則,若,，最小錯誤率判決規(guī)則：,兩邊同時除以,有：,定義類型,與,的似然比為：,(2.4-1),則

19、判決門限為：,(2.4-2),一般先驗概率已知，,也就已知了。,Made in CV&PRLab of Shandong University,2.4 最大似然比判決規(guī)則,0,，則,，則,(2.4-3),，則偶然決定,或,（2）由最小風險判決規(guī)則引出最大似然比判決規(guī)則,若,，有,代入，,，有：,即：,所以“最小錯誤率判決規(guī)則”就變?yōu)椋?若：,Made in CV&PRLab of Shandong University,2.4 最大似然比判決規(guī)則,0,又由Bayes公式：,代入上式：,即：,式中：,(2.4-4),為判決門限。,總結：最小風險判決引出的最大似然比判決與最小錯誤率判決引出的 最大

20、似然比判決的公式相同，只是判決門限 的計算公式不同。,Made in CV&PRLab of Shandong University,2.4 最大似然比判決規(guī)則,0,同樣：在(2.4-4)中取01損失函數(shù)，即：,則(2.4-4)退化為(2.4-2)。 在01損失函數(shù)情況下，最小風險判決退化為最小錯誤率判決。 將上述討論進一步推廣，假定有c個類型，分別用,表示，定義：,，且,(2.4-5),由最小錯誤率判決規(guī)則導出：,0,若,，則,其中，,(2.4-7),（2.4-6）,Made in CV&PRLab of Shandong University,2.4 最大似然比判決規(guī)則,由最小風險判決規(guī)則

21、導出，對于2.4-6式，,定義為：,同樣在01損失函數(shù)的情況下，(2.4-8)退化為(2.4-7)。,(2.4-8),似然函數(shù)的性質：,，因此，在c類問題中，若有一個,則不可能再有另外的類型,例3：對于前面的例1、2可以用上述辦法求出。,滿足式(2.4-6)式。,滿足(2.4-6)式，,Made in CV&PRLab of Shandong University,2.5 Neyman-Pearsen判決規(guī)則,0,在兩類別決策問題中，有犯兩種錯誤分類的可能性， 一種是在采取決策時 ，其實際自然狀態(tài)為 ； 另一種是在采取決策時 ，其實際自然狀態(tài)為 。,在實際應用中，有時不知道先驗概率，僅知道類概

22、率密度，應如何確定判決 門限呢?假定在處理過程中，先驗概率保證不變，這時可以使用聶曼皮爾遜 (NeymanPearson)判決規(guī)則。,兩種錯誤的概率分別為： 和 ， 最小錯誤率Bayes決策是使這兩種錯誤之和 最小。,Made in CV&PRLab of Shandong University,2.5 Neyman-Pearsen判決規(guī)則,0,在兩類問題中，兩類的類概率密度曲線如下圖所示，假定判決門限選為t， 可能發(fā)生的兩類分類錯誤與陰影區(qū)面積 和 成正比。,聶曼皮爾遜判決規(guī)則的基本思想是：在一種錯誤率不變的條件下， 使另一種錯誤率最小。,Made in CV&PRLab of Shando

23、ng University,2.5 Neyman-Pearsen判決規(guī)則,0,這是具有實際意義的，例如，在細胞的化驗中，由于把異常細胞錯判為正 常細胞的風險較大，可以要求這種錯判的錯誤率不大于某個指定的常數(shù)作為前 提條件，使正常細胞錯判為異常細胞的錯誤率盡可能小，以此為原則來選擇判 決門限t，這就是聶曼皮爾遜判決規(guī)則的基本思想。,從上圖可以看出：,假定 不變，為某個給定的正數(shù)，令：,（2.5-3）,Made in CV&PRLab of Shandong University,2.5 Neyman-Pearsen判決規(guī)則,0,為了使 最小化，就要通過適當?shù)剡x擇某個正數(shù) 使 最小。,把（2.5-4）式