模式識別 第五講

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

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

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

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

5、分布的，參數為： 求 的分類邊界，并畫出其曲線。 第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分，星期四當先驗概率相等時，最小錯誤率決策規(guī)則選擇密度函數大的。由于第二類在x2方向上的方差大于類1的，這樣密度函數p(x|2)在x2方向上將有較廣的延伸。使得在左邊R2區(qū)域內有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分，星期四這時的決策邊界就退化為線性決策邊界（超平面），相應的分類器為線性分類器。 式中 第16頁，共90頁，2022年，5月20日，6點25分，星期四二. 判別函數和多類分類器 判別函數 當模式有 類，這時的最小錯誤率的決策規(guī)則可以表示為： 若 （） 式中 稱為判別函數（discriminant function）。它表示決策規(guī)則。 第17頁，共90頁，2022年，5月20日，6點25分，星期四由貝葉斯公式， 和 等價。即把 用（）式

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

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

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

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

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

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

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

14、，5月20日，6點25分，星期四人們在線性分類器上作了許多工作。這不僅因為它形式簡單，而且用分段線性的組合可以任意逼近復雜的決策邊界。我們先介紹其中的一種：Fisher線性分類器（兩類問題）。 線性分類器的形式： 尋找分類器的參數，能夠使以下的Fisher準則函數最大：（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）和參數c無關（相減），因此c可以包括到閾值T里去。因此只要找出b就可以了。對準則函數求導并令其等于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分，星期四這樣分類器的形式就成為： 當K1=K2=K時，（3.26）式的b和（3.9 a）的成比例。這樣，當模式滿足高斯分布，且協(xié)方差矩陣

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

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

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

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

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

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

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

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

24、25分，星期四第61頁，共90頁，2022年，5月20日，6點25分，星期四若原來的兩個密度函數分的較開，則相對于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距離都滿足： 在一對一的線性變換下不變；當x的分量獨立時，這兩個量都滿足相加性（對每個成分）。

25、 第64頁，共90頁，2022年，5月20日，6點25分，星期四令 表示偏離度或Bhattacharyya距離，有： 但它們都不滿足距離的三角不等式，所以都不是真實的距離。但它們滿足下面的性質： 第65頁，共90頁，2022年，5月20日，6點25分，星期四對于高斯分布的數據，可以推導出它的偏離度的封閉形式解。 高斯分布下的偏離度和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距離，有相似的推導。 第70頁，共90頁，2022年，5月20日，6點25分，星期四其中的指數項可以化為： 可以化為第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分，星期四由上面各種關系證明（）和（）。 這是對于高斯分布的Bhattacharyya距離。 第76頁，共90頁，2022年，5月20日，6點25分，星期四由上式的B和前面的 可以看出，當兩類的協(xié)方差矩陣相等時，K1= K2= K， 此時的D 和B 是等價的度量，而且和兩類均值間的馬氏距離等價。說明D 和B 確是兩類間偏離和距離的一種度量。 第77頁，共90頁，2022年，5月20日，6點25分，星期四上一小節(jié)定義了偏離度和Bhattacharyya距離。下面分析它們和錯誤率的關系。 這一節(jié)討論似然比檢驗的錯誤率的上界。它們是基于Bhattacharyya距離及其推廣。 四. 錯誤率的Bhattacharyya和Chernoff界 最小錯誤率的上界 最小錯誤率（有時也叫貝葉斯錯誤率）eB 為：第78頁，共90頁，2022年，5月20日，6點25分，星期四利用不等式 上式可以化為： 即 這個結果稱為Bhattacharyya界。 第79頁，共90頁，2022年，5月20日，6點25分，星期四若利