1、模式識別 第五講北京工業(yè)大學(xué)計算機(jī)學(xué)院1第1頁，共90頁，2022年，5月20日，6點25分，星期四這一節(jié)的目的（概念）有兩個： 在一定的分布和條件下（如正態(tài)、等協(xié)方差矩陣），貝葉斯決策可以導(dǎo)致二次或線性分類器。雖然貝葉斯決策（似然比檢驗）在錯誤率或風(fēng)險上是最優(yōu)的，但必須知道類條件密度。在大多數(shù)應(yīng)用場合，類條件密度函數(shù)是從有限的樣本中估計的。后面我們將講一些密度函數(shù)估計的方法。但密度函數(shù)的估計本身是一件復(fù)雜工作（其難度不低于分類）并且需要大量樣本。 第2頁，共90頁，2022年，5月20日，6點25分，星期四即使我們得到了密度函數(shù)，有時用似然比檢驗的方法也很難計算，需要大量的時間和空間。因此我

2、們有時考慮更簡便易行的分類器設(shè)計方法。用二次、線性、分段線性分類器。即先規(guī)定分類器的數(shù)學(xué)形式，然后在適當(dāng)?shù)臏?zhǔn)則下，來確定這些參數(shù)。這一節(jié)先分析在什么條件下貝葉斯分類器變成二次和線性分類器，然后討論當(dāng)這些條件不滿足時，如何設(shè)計“性能好”的參數(shù)分類器。 第3頁，共90頁，2022年，5月20日，6點25分，星期四一. 兩類問題的二次和線性分類器對于似然比檢驗的決策規(guī)則：第4頁，共90頁，2022年，5月20日，6點25分，星期四當(dāng)各類的類條件密度是高斯分布時， mi和Ki為均值向量和協(xié)方差矩陣。 第5頁，共90頁，2022年，5月20日，6點25分，星期四這時似然比為 定義 ，-2倍自然對數(shù),則:

3、第6頁，共90頁，2022年，5月20日，6點25分，星期四上式是二次分類器。計算x到各類均值mi的Mahalanobis距離，然后和閾值 相比較，決定x屬于第一或第二類。 第7頁，共90頁，2022年，5月20日，6點25分，星期四在一維時，馬氏距離 ，即比較用方差標(biāo)準(zhǔn)化的一般距離。 展開（）式，有 （） 式中 第8頁，共90頁，2022年，5月20日，6點25分，星期四決策邊界h(x)=T是二次曲面（超曲面）：超橢球面、超雙曲面、超拋物面、超平面等，或它們組合的形式。（為了確定二次曲面的形狀，首先要消掉x的各分量相乘的項，可采用旋轉(zhuǎn)坐標(biāo)系的方法，把坐標(biāo)軸旋轉(zhuǎn)到A（）的特征向量的方向。曲面的

4、幾何形狀由A的特征值決定。如果A的特征值全部是正的，則是超橢球面；如果特征值有些正，有些負(fù)，則是超雙曲面；如果有些特征值是0，則是超拋物面。） 第9頁，共90頁，2022年，5月20日，6點25分，星期四當(dāng)x落到?jīng)Q策邊界的某一側(cè)時，就把它分到相應(yīng)的類。也可以把上述二次分類器用到非高斯分布的密度函數(shù)，但這時不能保證錯誤率最小。（但所確定的邊界是和二階統(tǒng)計矩（均值、方差）最相匹配的。） 任何具有（）式的分類器都叫作二次分類器。只有A、b、c是由高斯密度函數(shù)確定時，才叫高斯分類器。 第10頁，共90頁，2022年，5月20日，6點25分，星期四例1：兩維時的二次分類器的決策邊界 假定兩類模式都是高斯

5、分布的，參數(shù)為： 求 的分類邊界，并畫出其曲線。 第11頁，共90頁，2022年，5月20日，6點25分，星期四解： 第12頁，共90頁，2022年，5月20日，6點25分，星期四假定T=0，h(x)=T=0化為： ，是一雙曲線。 第13頁，共90頁，2022年，5月20日，6點25分，星期四第14頁，共90頁，2022年，5月20日，6點25分，星期四當(dāng)先驗概率相等時，最小錯誤率決策規(guī)則選擇密度函數(shù)大的。由于第二類在x2方向上的方差大于類1的，這樣密度函數(shù)p(x|2)在x2方向上將有較廣的延伸。使得在左邊R2區(qū)域內(nèi)有p(x|2) p(x|1)，盡管這些點比較靠近類1的均值點。在前面的h(x)

6、= xTAx+bTx+c中，如果兩類的協(xié)方差矩陣相等，K1= K1= K2，則矩陣A=0，這時決策規(guī)則為： 第15頁，共90頁，2022年，5月20日，6點25分，星期四這時的決策邊界就退化為線性決策邊界（超平面），相應(yīng)的分類器為線性分類器。 式中 第16頁，共90頁，2022年，5月20日，6點25分，星期四二. 判別函數(shù)和多類分類器 判別函數(shù) 當(dāng)模式有 類，這時的最小錯誤率的決策規(guī)則可以表示為： 若 （） 式中 稱為判別函數(shù)（discriminant function）。它表示決策規(guī)則。 第17頁，共90頁，2022年，5月20日，6點25分，星期四由貝葉斯公式， 和 等價。即把 用（）式

7、中時，決策規(guī)則是一樣的。當(dāng)先驗概率相等時，p(x|k)也是一組等價的判別函數(shù)。一般地，若 是任意一組判別函數(shù)，則下面定義的 也是一組等價的判別函數(shù)：a0,b是常數(shù)。（也可以是x的函數(shù)，但不能是k的函數(shù)。） 第18頁，共90頁，2022年，5月20日，6點25分，星期四同樣，若 ，f是單調(diào)增函數(shù)，它和 也是等價的。這些性質(zhì)可以使我們從一組判別函數(shù)推導(dǎo)出另外的判別函數(shù)，以便計算上更加簡單，或者意義更清楚，便于理解。 第19頁，共90頁，2022年，5月20日，6點25分，星期四當(dāng)每類都是正態(tài)分布，其均值和協(xié)方差分別為mk和Kk時，這時的最小錯誤率決策規(guī)則的判別函數(shù)為： 多類的二次和線性分類器 由于

8、自然對數(shù)是單調(diào)增的，所以可以定義下面等價的判別函數(shù)： 第20頁，共90頁，2022年，5月20日，6點25分，星期四（）這是二次判別函數(shù)。當(dāng)所有類的先驗概率相等時，可以省略 。 前面已經(jīng)證明，當(dāng)兩類的協(xié)方差矩陣相等時，二次分類器退化為線性分類器。多類時也是如此。 第21頁，共90頁，2022年，5月20日，6點25分，星期四當(dāng) 時，（）式化為： 上式中，由于第一項和第四項對所有的類都是相同的，所以等價的一組判別函數(shù)為： （） 上式是x的線性函數(shù)。下面考慮一些特定情況，說明二次和線性分類器的應(yīng)用。以下假定各類的先驗概率都相等。 第22頁，共90頁，2022年，5月20日，6點25分，星期四例2：

9、最小距離分類器。假定各類的先驗概率相等，而且各類 。即x的各個分量不相關(guān)，且各類等方差。 解：這時的判別函數(shù)化為： 后兩項對所有類是共同的，可以省略。分母中的 也可以去掉，因而有等價的判別函數(shù)： 這時的決策規(guī)則的含義是：x離哪類的均值最近，就把它分到哪類。 第23頁，共90頁，2022年，5月20日，6點25分，星期四例3 ：內(nèi)積分類器（相關(guān)分類器） 有 假定 。利用線性判別函數(shù) 若進(jìn)一步假定每類的均值的模相等，即|mk|相等，它們分布在半徑為|mk|的一個超球面上，且由于假定先驗概率也相等，因此，等價的判別函數(shù)為： 第24頁，共90頁，2022年，5月20日，6點25分，星期四即將測量向量x

10、和每類的均值mk作內(nèi)積（或稱相關(guān)），然后選擇值最大的，作為它的類。 上述例子是通信理論中信號檢測的一個經(jīng)典例子。 假定有Nc種已知信號要檢測。令x(t)表示接收到的信號，mk(t)是已知的信號，k=1，2，Nc 。當(dāng)mk(t)發(fā)送時，加入了白噪聲w(t)， 第25頁，共90頁，2022年，5月20日，6點25分，星期四白噪聲w(t)是零均值、等方差、不相關(guān)的信號（隨機(jī)過程）。即在任意時刻ti，w(ti)的均值為0，方差為 ，且當(dāng) 時， 。 即： 如果隨機(jī)向量x和mk是由相應(yīng)的時間函數(shù)取樣而成，即第26頁，共90頁，2022年，5月20日，6點25分，星期四第27頁，共90頁，2022年，5月2

11、0日，6點25分，星期四這是一個相關(guān)分類器（內(nèi)積分類器）的模式識別問題。假定|mk|2相等，即要求所有的信號具有相等的能量。 第28頁，共90頁，2022年，5月20日，6點25分，星期四把接收到的信號和已知信號作相關(guān)mkTx，然后選擇相關(guān)最大的。作相關(guān)時通常通過一個“匹配濾波器”來實現(xiàn)。 選擇最大的輸出 匹配濾波器1 匹配濾波器2 匹配濾波器Nc 第29頁，共90頁，2022年，5月20日，6點25分，星期四在連續(xù)時，判別函數(shù)： 另外，mk和x間的相關(guān)也可以通過一個線性濾波器的輸出來實現(xiàn)。 構(gòu)造一個函數(shù)gk(t)，使?jié)M足 gk(Tt)=mk(t)，則 （線性系統(tǒng)的杜哈美爾積分） 第30頁，共

12、90頁，2022年，5月20日，6點25分，星期四即濾波器的輸出是相關(guān)值，而濾波器的脈沖響應(yīng)是gk(t)，匹配濾波器可由專門的儀器來作。 * 可以把上面的線性分類器的討論再進(jìn)一步。在線性分類器 中，如果把向量在K的特征向量的坐標(biāo)系下表示（作變換），并作比例變換使所有分量的方差變?yōu)?，這時。線性分類器將作mkTx相關(guān)運(yùn)算。在通信問題中，如果噪聲信號是相關(guān)的，而且方差是變化的，那么最優(yōu)的信號檢測是使噪聲變?yōu)椴幌嚓P(guān)的，然后作相關(guān)或匹配濾波器運(yùn)算。 第31頁，共90頁，2022年，5月20日，6點25分，星期四三. Fisher線性分類器另一種 決策準(zhǔn)則 在前面一節(jié)中，我們討論了兩種形式的分類器，在n

13、維空間內(nèi)分析了它的判別邊界。其中分類的參數(shù)如A、b、c和T都是確定的，如果模式滿足高斯分布，那么分類器可以使錯誤率、最小風(fēng)險或者NeymanPearson準(zhǔn)則最小。 第32頁，共90頁，2022年，5月20日，6點25分，星期四但在某些情況下，不知道類條件密度函數(shù)，因此不可能找出最佳分類器。在另些情況下，雖然可以對類條件密度進(jìn)行估計，但推導(dǎo)最優(yōu)分類器的計算量太大。 因此，實際工作中，更需要先假定一種分類器的數(shù)學(xué)形式，如線性或二次分類器，然后確定它的參數(shù)，使它能最優(yōu)某種適當(dāng)?shù)臏?zhǔn)則函數(shù)，如分離性等。在一般情況下，這種準(zhǔn)則函數(shù)不一定是錯誤率，而是更加簡單和易于分析的。 第33頁，共90頁，2022年

14、，5月20日，6點25分，星期四人們在線性分類器上作了許多工作。這不僅因為它形式簡單，而且用分段線性的組合可以任意逼近復(fù)雜的決策邊界。我們先介紹其中的一種：Fisher線性分類器（兩類問題）。 線性分類器的形式： 尋找分類器的參數(shù)，能夠使以下的Fisher準(zhǔn)則函數(shù)最大：（3.21） 第34頁，共90頁，2022年，5月20日，6點25分，星期四（3.22a ） 式中 （3.22b） 希望使兩類的均值離得越開越好，而方差盡可能的小?；叵胍幌拢粲?即 第35頁，共90頁，2022年，5月20日，6點25分，星期四（3.23a ） 這時h(x)（分類器的輸出）的均值和方差為 （3.23b） 方程（

15、3.21）和參數(shù)c無關(guān)（相減），因此c可以包括到閾值T里去。因此只要找出b就可以了。對準(zhǔn)則函數(shù)求導(dǎo)并令其等于0，有 變換后的均值和方差 第36頁，共90頁，2022年，5月20日，6點25分，星期四（3.24） （3.25） 第37頁，共90頁，2022年，5月20日，6點25分，星期四利用（3.23）式可以求出 、 、 、 ，然后代入上式，但為了簡單，有時就把b定為 （3.26） 而把項 放到閾值里去。 第38頁，共90頁，2022年，5月20日，6點25分，星期四這樣分類器的形式就成為： 當(dāng)K1=K2=K時，（3.26）式的b和（3.9 a）的成比例。這樣，當(dāng)模式滿足高斯分布，且協(xié)方差矩陣

16、相等時，使Fisher準(zhǔn)則最優(yōu)等價于最小錯誤率最優(yōu)。第39頁，共90頁，2022年，5月20日，6點25分，星期四小結(jié) 這一章首先討論了一些簡單的決策理論。 最小錯誤率、風(fēng)險、NeymanPearson 似然比檢驗，只是閾值不同。 最小最大決策，當(dāng)先驗概率變化時，使最大的錯誤率最小。序貫決策：測量的維數(shù)可變時，分析了閾值和錯誤率間的關(guān)系。在獨(dú)立同分布的假定下分析了維數(shù)的期望值。 第40頁，共90頁，2022年，5月20日，6點25分，星期四這一章還介紹了線性和二次分類器。 對于多類模式識別問題的判別函數(shù)。討論了最近距離分類和相關(guān)分類。討論了兩類問題的一種線性分類器Fisher分類器。在高斯分布

17、、等協(xié)方差矩陣的情況下，F(xiàn)isher分類器等價于最小錯誤率分類器。 第41頁，共90頁，2022年，5月20日，6點25分，星期四 * 這類線性分類器的更一般解法 線性分類器是最容易實現(xiàn)的。然而，只在正態(tài)分布和等協(xié)方差的情況下，線性判別函數(shù)才是貝葉斯意義上最優(yōu)的。在通信系統(tǒng)的信號檢測中，等協(xié)方差矩陣是合理的。但在不少應(yīng)用場合，并不滿足協(xié)方差矩陣相等。在設(shè)計正態(tài)分布、不等協(xié)方差的線性分類器，在設(shè)計非正態(tài)分布的線性分類器上有不少研究成果。當(dāng)然，它們不是最優(yōu)的。但簡單易行，可以補(bǔ)償性能上的損失。下面我們更一般地討論這一問題。 第42頁，共90頁，2022年，5月20日，6點25分，星期四令 任務(wù)是要

18、確定 和 。 表示X在V方向上的投影。投影后的均值 和方差 是衡量類可分性的一個準(zhǔn)則。 第43頁，共90頁，2022年，5月20日，6點25分，星期四投影 比 要好。投影后的均值 和方差 是衡量類可分性的一個準(zhǔn)則。 第44頁，共90頁，2022年，5月20日，6點25分，星期四令 是任一準(zhǔn)則函數(shù)（要最大或最小的），要確定使f最大（小）的v和v0。 第45頁，共90頁，2022年，5月20日，6點25分，星期四由于 代入，有： 第46頁，共90頁，2022年，5月20日，6點25分，星期四由以上兩式可以計算出v，但由于錯誤率只依賴v的方向，而不是它的大小。因而可以消去v的常數(shù)系數(shù)（不是mi和ki

19、的函數(shù)）。 解出： 式中， 第47頁，共90頁，2022年，5月20日，6點25分，星期四注意，上面得出的v和f無關(guān)，f只是出現(xiàn)在s中。 回想在正態(tài)、等協(xié)方差的情況下，有 這里是用s和(1s)對K1和K2作加權(quán)平均。當(dāng)f的具體形式給出后，v0是 的解。第48頁，共90頁，2022年，5月20日，6點25分，星期四例1：Fisher線性分類器。 因此s0.5 Fisher準(zhǔn)則不依賴于v0。因為v0從 和 相減中消失了。 最佳的第49頁，共90頁，2022年，5月20日，6點25分，星期四例2：另種準(zhǔn)則是 解出后有 Fisher準(zhǔn)則不能確定v0。 第50頁，共90頁，2022年，5月20日，6點2

20、5分，星期四2.5 分類器的錯誤率問題 對樣本進(jìn)行分類是PR的任務(wù)之一。在分類過程中總會有錯誤率，當(dāng)先驗概率和類條件密度函數(shù)已知，采用的決策規(guī)則也確定后，錯誤率也就固定了。 錯誤率反映了模式分類問題本身的固有復(fù)雜程度。也是衡量分類器性能的重要指標(biāo)。分類器是否和要解決的問題相匹配。一. 錯誤率的計算和估計 第51頁，共90頁，2022年，5月20日，6點25分，星期四從上式可以看出，在x是多維時，P(e)的計算要進(jìn)行多重積分。當(dāng)類條件密度函數(shù)的解析形式比較復(fù)雜時，P(e)的計算相當(dāng)困難。錯誤率的計算公式前面已經(jīng)分析，對兩類問題：第52頁，共90頁，2022年，5月20日，6點25分，星期四由于錯

21、誤率的重要性和復(fù)雜性，人們對錯誤率的計算和估算方法進(jìn)行了大量的研究。方法主要有以下幾類： 按公式計算錯誤率；估算錯誤率的上限；從實驗中估計錯誤率。 這一小節(jié)先討論前兩種方法。 第53頁，共90頁，2022年，5月20日，6點25分，星期四正態(tài)分布且等協(xié)方差矩陣時； 當(dāng)x的各分量間相互獨(dú)立時； （參考清華的書，略）。下面討論估計錯誤率上限的方法 二. 在一些特殊情況下錯誤率的計算 第54頁，共90頁，2022年，5月20日，6點25分，星期四模式可分性度量反映了模式分類的困難程度，和錯誤率有密切關(guān)系。既有理論上的意義，也用在特征抽取和選擇上。這一節(jié)介紹模式可分性的兩種重要度量：偏離度（diver

22、gence）和Bhattacharyya距離。 （涇渭分明西瓜） 先對一般的概率密度函數(shù)定義這兩個量。然后在多元高斯情況下，看看會有什么結(jié)果。 三. 模式可分性的度量 第55頁，共90頁，2022年，5月20日，6點25分，星期四對于對數(shù)的似然比檢驗 ， 也是一個隨機(jī)變量。它可以用兩個密度函數(shù) 和 來描述。如下圖所示，當(dāng)兩個密度函數(shù)偏離較大時，錯誤率一定低，反之，會大。 偏離度和Bhattacharyya距離 第56頁，共90頁，2022年，5月20日，6點25分，星期四兩類模式可分性的一種度量是它們均值的差 ，稱為偏離度D 。第57頁，共90頁，2022年，5月20日，6點25分，星期四偏離

23、度的定義為： 定義量： 稱為有（單）向偏離度，或第i類相對第j類的相對信息。有些作者稱它為Kullbackliebler數(shù)。 第58頁，共90頁，2022年，5月20日，6點25分，星期四由上兩式可知 這樣，當(dāng)相對信息H(1，2)和H(2，1)大時，D也大，可分性好。 可分性的另一種度量是Bhattacharyya距離： 而量 ，有時稱為Bhattacharyya系數(shù)。 第59頁，共90頁，2022年，5月20日，6點25分，星期四這兩個量比起偏離度來，直觀上更難解釋。但 若寫為： 我們可以給出Bhattacharyya距離的一種解釋，如下圖： 第60頁，共90頁，2022年，5月20日，6點

24、25分，星期四第61頁，共90頁，2022年，5月20日，6點25分，星期四若原來的兩個密度函數(shù)分的較開，則相對于2的期望將較?。?）。 這時的ln值將會大，Bhattacharyya距離將會大。 第62頁，共90頁，2022年，5月20日，6點25分，星期四反之，若p1 (x)和p2 (x)近似重疊，則期望值將較大，ln將較小。即Bhattacharyya距離小。如下圖： 第63頁，共90頁，2022年，5月20日，6點25分，星期四偏離度和B距離是真的距離度量嗎？偏離度和Bhattacharyya距離都滿足： 在一對一的線性變換下不變；當(dāng)x的分量獨(dú)立時，這兩個量都滿足相加性（對每個成分）。

25、 第64頁，共90頁，2022年，5月20日，6點25分，星期四令 表示偏離度或Bhattacharyya距離，有： 但它們都不滿足距離的三角不等式，所以都不是真實的距離。但它們滿足下面的性質(zhì)： 第65頁，共90頁，2022年，5月20日，6點25分，星期四對于高斯分布的數(shù)據(jù)，可以推導(dǎo)出它的偏離度的封閉形式解。 高斯分布下的偏離度和Bhattacharyya距離 而 第66頁，共90頁，2022年，5月20日，6點25分，星期四由于 而且由 有 第67頁，共90頁，2022年，5月20日，6點25分，星期四和 第68頁，共90頁，2022年，5月20日，6點25分，星期四同樣，有： 這就是高斯

26、分布的偏離度。 第69頁，共90頁，2022年，5月20日，6點25分，星期四對于高斯分布的Bhattacharyya距離，有相似的推導(dǎo)。 第70頁，共90頁，2022年，5月20日，6點25分，星期四其中的指數(shù)項可以化為： 可以化為第71頁，共90頁，2022年，5月20日，6點25分，星期四其中第72頁，共90頁，2022年，5月20日，6點25分，星期四 第73頁，共90頁，2022年，5月20日，6點25分，星期四可以證明 （） 以及 （） 第74頁，共90頁，2022年，5月20日，6點25分，星期四證明的思路和技巧：定義量 先證明 由此再證： 以及 第75頁，共90頁，2022年，

27、5月20日，6點25分，星期四由上面各種關(guān)系證明（）和（）。 這是對于高斯分布的Bhattacharyya距離。 第76頁，共90頁，2022年，5月20日，6點25分，星期四由上式的B和前面的 可以看出，當(dāng)兩類的協(xié)方差矩陣相等時，K1= K2= K， 此時的D 和B 是等價的度量，而且和兩類均值間的馬氏距離等價。說明D 和B 確是兩類間偏離和距離的一種度量。 第77頁，共90頁，2022年，5月20日，6點25分，星期四上一小節(jié)定義了偏離度和Bhattacharyya距離。下面分析它們和錯誤率的關(guān)系。 這一節(jié)討論似然比檢驗的錯誤率的上界。它們是基于Bhattacharyya距離及其推廣。 四. 錯誤率的Bhattacharyya和Chernoff界 最小錯誤率的上界 最小錯誤率（有時也叫貝葉斯錯誤率）eB 為：第78頁，共90頁，2022年，5月20日，6點25分，星期四利用不等式 上式可以化為： 即 這個結(jié)果稱為Bhattacharyya界。 第79頁，共90頁，2022年，5月20日，6點25分，星期四若利