模式識別5第五章線性分類器(幾何分類器)專題課件

1、模式識別5第五章線性分類器(幾何分類器)專題課件模式識別5第五章線性分類器(幾何分類器)專題課件5.1 幾何分類器的基本概念5.2 線性判別函數(shù)5.3 線性判別函數(shù)的實現(xiàn)5.4 感知器算法5.5 最小平方誤差算法(LMSE)5.6 Fisher分類5.7 非線性判別函數(shù)第五章 幾何分類器專題第五章 內容綱要025.1 幾何分類器的基本概念第五章 幾何分類器專題第五章第二章到第四章在概率密度和概率函數(shù)的基礎上設計分類器。04還記得嗎？第二章到第四章在概率密度和概率函數(shù)的基礎04還記得嗎？ 直接使用Bayes決策首先需要知道有關樣品總體分布的知識，包括各類先驗概率 、 類條件概率密度函數(shù)和樣品的后

2、驗概率 ， 并以此作為產生判別函數(shù)的必要依據(jù)，設計出相應的判別函數(shù)與決策面，這種方法稱為參數(shù)判別方法。 04 直接使用Bayes決策首先需要知道有關樣品 它的前提是對特征空間中的各類樣品的分布已很清楚，一旦待測試分類樣品的特征向量X已知，就可以確定X對各類的后驗概率，也就可按相應的準則計算與分類。 所以判別函數(shù)等的確定取決于樣品統(tǒng)計分布的有關知識。 因此參數(shù)分類判別方法一般只能用1）在有統(tǒng)計知識的場合，或2）能利用訓練樣品估計出參數(shù)的場合。 05 它的前提是對特征空間中的各類樣品的分布05 多數(shù)情況下，準確地估計概率密度函數(shù)并不是一件容易的事，在特征空間維數(shù)高和樣本較少的情況下尤其如此。05

3、真的不容易！ 在不涉及訓練數(shù)據(jù)隱含的分布時，我們想到更直觀的幾何分類器（線性分類器和非線性分類）！ 怎樣才能更簡單，更具可計算性呢？ 多數(shù)情況下，準確地估計概率密度函數(shù)并不05 5.1 幾何分類器的基本概念03第五章 幾何分類器專題5.1 幾何分類器的基本概念03第五章 幾何分類器專題 一個模式通過某種變換映射成一個特征向量后，該特征向量可以理解為特征空間的一個點。 06Feature Space 一個模式通過某種變換映射成一個特征向量后，0 在特征空間中，屬于一個類的點集，在某種程度上總是與屬于另一個類的點集相分離，各個類之間是確定可分的， 因此如果能夠找到一個分離函數(shù)（線性或非線性函數(shù)），

4、把不同類的點集分開，則分類任務就解決了。 06 在特征空間中，屬于一個類的點集，在某種程06 幾何分類器不依賴于條件概率密度的知識，可以理解為通過幾何的方法，把特征空間分解為對應于不同類型的子空間，而且呈線性的分離函數(shù)將使計算簡化。07 回答了之前的問題： “怎樣才能更簡單，更具可計算性呢？”07 回答了之前的問題：假定樣品X有兩個特征，即 每一個樣品都對應二維空間中的一個點。共分兩類圖像：每一點屬于一類圖像。 那么待測X屬于哪一類？08假定樣品X有兩個特征，即 每一個樣品都對應二維空對這個問題就要看它最接近哪一類，若最接近于則為類，若最接近于則為類。在各類之間要有一個邊界，若能知道各類之間的

5、邊界，那么就知道待測樣品屬于哪一類了。所以，要進一步知道如何去找這個分界線。 那么待測X屬于哪一類？09對這個問題就要看它最接近哪一類，若最接近于則為類，若最接近于找分界線的方法就是幾何分類法！幾何分類法的結果能提供一個確定的分界線方程，這個分界線方程叫做判別函數(shù)！因此判別函數(shù)描述了各類之間的分界線是什么形式。10找分界線的方法就是幾何分類法！10幾何分類法按照分界函數(shù)的形式可以分為線性判別函數(shù)和非線性判別函數(shù) 兩大類。11幾何分類法按照分界函數(shù)的形式可以分為11線性可分情況121.若已知類的所有特征向量都可以用線性分類器正確分類，我們將研究其相應的線性函數(shù)的計算方法。線性可分情況121.若已

6、知類的所有特征向量都可以用線性分類器線性不可分情況132.對于不能將所有向量正確分類的線性分類器，我們將通過采用相應的優(yōu)化規(guī)則來尋找設計最優(yōu)線性分類器的方法。線性不可分情況132.對于不能將所有向量正確分類的線性分類器線性分類器由于涉及的數(shù)學方法較為簡單，在計算機上容易實現(xiàn)，故在模式識別中被廣泛應用。但是這并不意味著，在模式識別中只有線性分類器就足夠了。11線性分類器由于涉及的數(shù)學方法較為簡單，在計11在模式識別的許多問題中，由于線性分類器固有的局限性，它并不能提供理想的識別效果，必須求助于非線性分類器。而且有些較為簡單的非線性分類器對某些模式識別問題的解決，既簡單，效果又好。1414本章將介

7、紹線性判別函數(shù)和非線性判別函數(shù)，并介紹它們的實現(xiàn)方法，其中實現(xiàn)線性判別函數(shù)分類的方法有感知器算法、LMSE分類算法和Fisher分類。15155.2 線性判別函數(shù)16第五章 幾何分類器專題5.2 線性判別函數(shù)16第五章 幾何分類器專題判別函數(shù)分為線性判別函數(shù)和非線性判別函數(shù)。最簡單的判別函數(shù)是線性判別函數(shù)，它是由所有特征量的線性組合構成的。17判別函數(shù)分為線性判別函數(shù)和非線性判別函數(shù)。17兩類別分類器框圖如圖所示，根據(jù)計算結果的符號將X分類。1. 兩類別情況18兩類別分類器框圖如圖所示，根據(jù)計算結果1. 兩類別情況18兩個特征 19兩個特征 202021212) 三個特征 每類模式有三個特征，

8、樣品是三維的，判別邊界為一平面。222) 三個特征 3) 三個以上特征 23每類模式有三個以上特征，判別邊界為一超平面。對于 維空間，用矢量 來表示模式， 一般的線性判別函數(shù)形式為：式中 稱為權矢量或參數(shù)矢量。 3) 三個以上特征 在兩類別情況下，判別函數(shù) 有下述性質，即 滿足 的點為兩類的判別邊界。 24在兩類別情況下，判別函數(shù) 有下述性質，即 滿足 的點為兩類的2. 多類別情況對于多類別問題，假設有M類模式 。對于 維空間中的M個類別，就要 給出M個判別函數(shù)： 。分類器基本形式如圖所示 若X屬于第 類，則有 252. 多類別情況對于多類別問題，假設有M類模式 。對于 維1) 第一種情況每一

9、個類別可用單個判別平面分割，因此M類有M個判別函數(shù)，具有下面的性質261) 第一種情況每一個類別可用單個判別平面分割，因此M類有M27如圖所示，有3個模式類，每一類別可用單個判別邊界與其余的類別劃分開。27如圖所示，有3個模式類，每一類別可用單個判別邊界與282) 第二種情況每兩個類別之間可用判別平面分開，有 個判別函數(shù)，判別函數(shù)形式為且 若對于 ，有 ，則X屬于 類。 282) 第二種情況每兩個類別之間可用判別平面分開，有 個判沒有一個類別可以用一個判別平面與其他類分開，如圖所示，每一個邊界只能分割兩類。 29沒有一個類別可以用一個判別平面與其他類分開，如圖所示，29303) 第三種情況存在

10、M個判別函數(shù)，判別函數(shù)形式為 把X代入M個判別函數(shù)中，判別函數(shù)最大的那個類就是X所屬類別。與第一種情況的區(qū)別在于此種情況下可以有多個判別函數(shù)的值大于0，第一種情況下只有一個判別函數(shù)的值大于0。 303) 第三種情況存在M個判別函數(shù)，判別函數(shù)形式為 把X代3131若可用以上幾種情況中的任一種線性判別函數(shù)來進行分類，則這些模式類稱為線性可分的?？偨Y如表所示。32若可用以上幾種情況中的任一種線性判別函數(shù)來進行分類，325.3 線性判別函數(shù)的實現(xiàn)33第五章 幾何分類器專題5.3 線性判別函數(shù)的實現(xiàn)33第五章 幾何分類器專題 前面介紹了判別函數(shù)的形式，對于判別函數(shù)來說，應該確定兩個內容，一個是方程的形式

11、，另一個是方程的系數(shù)。 對于線性判別函數(shù)來說，方程的形式固定為線性，維數(shù)和形式已定，則對判別函數(shù)的設計就是確定函數(shù)的各系數(shù)，即線性方程的各個權值。 34 前面介紹了判別函數(shù)的形式，對于判別函數(shù)來34 1）首先按需要確定一準則函數(shù)J，如Fisher準則、感知器算法、LMSE算法。及 3）確定判別函數(shù)，完成分類器設計。 的具體數(shù)值；下面將討論如何確定線性判別函數(shù)的系數(shù)。 2）確定準則函數(shù)J達到極值時35 1）首先按需要確定一準則函數(shù)J，如Fishe 線性分類器設計任務是在給定樣品集條件下，確定線性判別函數(shù)的各項系數(shù)，36 對待測樣品進行分類時，能滿足相應的準則函數(shù)J為最優(yōu)。 線性分類器設計任務是在

12、給定樣品集條件下，36 在計算機上確定各權值時采用的是“訓練”或“學習”的方法，就是挑選一批已分類的樣品，把這批樣品輸入到計算機的“訓練”程度中去。38 通過多次迭代后，準則函數(shù)J達到極值，得到正確的線性判別函數(shù)。Classifiers based on Cost Function Optimization!請思考：以下代表性線性分類器基于什么最佳準則？ 在計算機上確定各權值時采用的是“訓練”385.4 感知器算法39第五章 幾何分類器專題5.4 感知器算法39第五章 幾何分類器專題1理論基礎既然判別函數(shù)分類器的訓練過程就是確定該函數(shù)的權集，為敘述方便起見，從判別函數(shù)的一般形式著手。 對于兩類

13、問題，設有判別函數(shù) 并已知訓練集 且 對它們來說， 則對它們來說， 401理論基礎1理論基礎既然判別函數(shù)分類器的訓練過程就是確定該函數(shù)的權集對于兩類問題，設有判別函數(shù) 401理論基礎判別函數(shù)可寫成一般方程形式其中 為權矢量 ，X為各樣品特征值的增1矩陣。 對于兩類問題，設有判別函數(shù) 401理論基礎判別函數(shù)可寫成一 判別函數(shù)可寫成一般方程形式其中 為權矢量 ，X為各樣品特征值的增1矩陣。 訓練過程就是對判斷好的樣品集求解權矢量W，即根據(jù)已知類別的樣品求出權系數(shù)，形成判別界線（面），再對未知類別的樣品求出其類別。41 判別函數(shù)可寫成一般方程形式其中 為權矢量 ，X401）將其作為典型的優(yōu)化問題來討

14、論，因此需要采用一個適當?shù)拇鷥r函數(shù)和一個優(yōu)化算法。 2）感知器代價（perceptron cost）： 1理論基礎感知器代價函數(shù)？401）將其作為典型的優(yōu)化問題來討論，因此需要采用一個適當2一般求解方法梯度下降法求解不等式組采用的最優(yōu)化的方法：定義一個準則函數(shù)J(a)，當a是解向量時，J(a)為最?。徊捎米顑?yōu)化方法求解標量函數(shù)J(a)的極小值。最優(yōu)化方法采用最多的是梯度下降法，設定初始權值矢量a(1)，然后沿梯度的負方向迭代計算：其中(k)稱為學習率，或稱步長。42詳細可以參考第二版書本第331頁附錄A.1梯度法，亦可參考希臘版參考書。以使錯分類樣本到分界面距離之和最小為原則。 一般求解方法梯

15、度下降法求解不等式組采用的最優(yōu)化的方法：其中401）將其作為典型的優(yōu)化問題來討論，因此需要采用一個適當?shù)拇鷥r函數(shù)和一個優(yōu)化算法。 2）感知器代價（perceptron cost）： 1理論基礎準則函數(shù)以使錯分類樣本到分界面距離之和最小為原則。 401）將其作為典型的優(yōu)化問題來討論，因此需要采用一個適當2 判別函數(shù)可寫成一般方程形式其中 為權矢量 ，X為各樣品特征值的增1矩陣。 這是一個線性聯(lián)立不等式的求解問題，只對線性可分問題方程才有解。對這樣的問題來說，如果有解，其解也不一定是單值的，因而就有一個按不同條件取得最優(yōu)解的問題，因此出現(xiàn)了多種不同的算法，這里介紹梯度法。訓練過程就是對判斷好的樣品

16、集求解權矢量W，即根據(jù)已知類別的樣品求出權系數(shù)，形成判別界線（面），再對未知類別的樣品求出其類別。41 判別函數(shù)可寫成一般方程形式其中 為權矢量 ，X一般求解方法梯度下降法求解不等式組采用的最優(yōu)化的方法：定義一個準則函數(shù)J(a)，當a是解向量時，J(a)為最?。徊捎米顑?yōu)化方法求解標量函數(shù)J(a)的極小值。最優(yōu)化方法采用最多的是梯度下降法，設定初始權值矢量a(1)，然后沿梯度的負方向迭代計算：其中(k)稱為學習率，或稱步長。42詳細可以參考第二版書本第331頁附錄A.1梯度法，亦可參考希臘版參考書。一般求解方法梯度下降法求解不等式組采用的最優(yōu)化的方法：其中一般求解方法梯度下降法求解不等式組采用的

17、最優(yōu)化的方法：定義一個準則函數(shù)J(a)，當a是解向量時，J(a)為最??；采用最優(yōu)化方法求解標量函數(shù)J(a)的極小值。最優(yōu)化方法采用最多的是梯度下降法，設定初始權值矢量a(1)，然后沿梯度的負方向迭代計算：其中(k)稱為學習率，或稱步長。42詳細可以參考第二版書本第331頁附錄A.1梯度法，亦可參考希臘版參考書。一般求解方法梯度下降法求解不等式組采用的最優(yōu)化的方法：其中感知器算法的特點當樣本線性可分情況下，學習率 合適時，算法具有收斂性；收斂速度較慢；當樣本線性不可分情況下，算法不收斂，且無法判斷樣本是否線性可分。43感知器算法的特點當樣本線性可分情況下，學習率 合5.5 最小平方誤差算法(LM

18、SE)44第五章 幾何分類器專題5.5 最小平方誤差算法(LMSE)44第五章 幾何分類LMSE方法的基本思想是將求解線性不等式組的問題轉化為求解線性方程組：45LMSE方法的基本思想是將求解線性不等式組的問題轉化為求解線最小平方誤差的準則函數(shù)定義方程組的誤差矢量e，用e長度的平方的一半作為準則函數(shù)：46最小二乘法適當優(yōu)化的標準下計算相應的權向量！最小平方誤差的準則函數(shù)定義方程組的誤差矢量e，用e長度的平方最小平方誤差的準則函數(shù)1）對于所有已知訓練特征向量的期望輸出和實 際輸出中間的誤差進行累加；2）而不是計算均值；3）可以減少對概率密度函數(shù)信息的需求。46最小平方誤差的準則函數(shù)1）對于所有已

19、知訓練特征向量的期望輸出47 求權向量？1）偽逆法求解。2）梯度下降法求解。47 求權向量？471）偽逆法求解。471）偽逆法求解。472）梯度下降法求解。472）梯度下降法求解。47通過迭代，最終能求出解。對于一線性不可分模式，要達到誤差矢量全部為正，需要迭代很多次，往往早在誤差矢量全部分量都達到非正值以前，就能看出其中有些分量向正值變化得較慢，這時已能估計出造成線性不可分的某些樣品，及早采取對策。47通過迭代，最終能求出解。LMSE算法的特點算法的收斂依靠(k)的衰減，一般取(k)=(1)/k；算法對于線性不可分的訓練樣本也能夠收斂于一個均方誤差最小解；取b=1時，當樣本數(shù)趨于無窮多時，算

20、法的解以最小均方誤差逼近貝葉斯判別函數(shù)；當訓練樣本線性可分的情況下，算法未必收斂于一個分類超平面。49LMSE算法的特點算法的收斂依靠(k)的衰減，一般取(k5.6 Fisher分類50第五章 幾何分類器專題更直觀的線性判別分析！5.6 Fisher分類50第五章 幾何分類器專題更直觀Fisher線性判別函數(shù) Fisher線性判別函數(shù)是研究這類判別函數(shù)中最有影響的方法之一。 對線性判別函數(shù)的研究就是從R.A.Fisher在1936年發(fā)表的論文開始的。51Fisher線性判別函數(shù) 51理論基礎 1）在應用統(tǒng)計方法解決模式識別問題時，經(jīng)常會遇到所謂的“維數(shù)災難”的問題，在低維空間里適用的方法在高維

21、空間里可能完全不適用。 2）因此，壓縮特征空間的維數(shù)有時是很重要的。 3）Fisher方法實際上涉及維數(shù)壓縮的問題。52理論基礎 1）在應用統(tǒng)計方法解決模式識別問題時，經(jīng)常會遇5353 如何找到這個最好的直線方向以及如何實現(xiàn)向最好方向投影的變換，這正是Fisher算法要解決的基本問題，這個投影變換恰是我們所尋求的解向量 。54 如何找到這個最好的直線方向以及如何實現(xiàn)向 1)最好的投影方向：使投影以后兩類盡可能分開，而各類內部又盡可能聚集。建立Fisher準則函數(shù)：54樣品類間離散度矩陣總類內離散度矩陣 類內離散度矩陣（投影以后的空間） 1)最好的投影方向：使投影以后兩類盡可能分開，而各類內54

22、（投影以后的空間）（Fisher準則下的 最優(yōu)投影方向）54（投影以后的空間）（Fisher準則下的 具體方法如下： 1）計算各類樣品均值向量。 2）計算樣品類內離散度矩陣和總類間離散度矩陣。 3）計算樣品類間離散度矩陣。 4）求向量 。 5）將訓練集內所有樣品進行投影。 6）計算在投影空間上的分割閾值。 7）對于給定的X，計算出它在 上的投影點。而后根據(jù)決策規(guī)則進行分類。56 具體方法如下：56 要實現(xiàn)Fisher分類，首先要實現(xiàn)兩類Fisher算法，兩類Fisher算法能夠返回最接近待測樣品的類別，然后用返回的類別和新的類別作兩類Fisher運算，又能夠得到比較接近的類別，以此類推，直至所

23、有的類別，最后得出未知樣品的類別。實現(xiàn)步驟57 要實現(xiàn)Fisher分類，首先要實現(xiàn)兩類Fi 兩類Fisher算法實現(xiàn)步驟如下： 1）求兩類樣品均值向量。 2）求兩類樣品類內離散度矩陣。 3）求總類間離散度矩陣。 4）求向量 。 5）對于兩類已知樣品，求出它們在 上的投影點 6）求各類樣品在投影空間上的均值。 7）選取閾值。 8）對于未知樣品X，計算它在 上的投影點。 9）根據(jù)決策規(guī)則分類。58 兩類Fisher算法實現(xiàn)步驟如下：585.7 非線性判別函數(shù)59第五章 幾何分類器專題5.7 非線性判別函數(shù)59第五章 幾何分類器專題 線性判別函數(shù)簡單方便，經(jīng)常用來對進行一些簡單的模式分類，但在實際應用中模式往往比較復雜，不是線性可分的。如圖所示，就不能用一個線性函數(shù)來分割。60 線性判別函數(shù)簡單方便，經(jīng)常用來對進行一些 但是只要各類模式的特征值不相同，判別函數(shù)的邊界總是存在的，只不過判別邊界不是線性的而已。這時，可以通過某種映射將非線性空