模式識(shí)別原理精品課件

1、模式識(shí)別原理第1頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四第三章 判別函數(shù)3.1 線性判別函數(shù)3.2 廣義線性判別函數(shù)3.3 分段線性判別函數(shù)3.4 模式空間和權(quán)空間3.5 感知器算法3.6 采用感知器算法的多類模式的分類3.7 勢函數(shù)法 一種確定性的非線性分類算法第2頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.1 線性判別函數(shù)3.1.1 用判別函數(shù)分類的概念模式識(shí)別系統(tǒng)的主要作用判別各個(gè)模式所屬的類別對(duì)一個(gè)兩類問題的判別，就是將模式x劃分成1和2兩類。第3頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.1 線性判別函數(shù)3.1.1 用判別函數(shù)分類的概念

2、描述：兩類問題的判別函數(shù)第4頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.1 線性判別函數(shù)3.1.1 用判別函數(shù)分類的概念用判別函數(shù)進(jìn)行模式分類依賴的兩個(gè)因素（1）判別函數(shù)的幾何性質(zhì)：線性的和非線性的函數(shù)。線性的是一條直線；非線性的可以是曲線、折線等；線性判別函數(shù)建立起來比較簡單（實(shí)際應(yīng)用較多）；非線性判別函數(shù)建立起來比較復(fù)雜。（2）判別函數(shù)的系數(shù)：判別函數(shù)的形式確定后，主要就是確定判別函數(shù)的系數(shù)問題。只要被研究的模式是可分的，就能用給定的模式樣本集來確定判別函數(shù)的系數(shù)。第5頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.1 線性判別函數(shù)3.1.2 線性判別函數(shù)n維線

3、性判別函數(shù)的一般形式權(quán)向量增廣模式向量增廣權(quán)向量分類問題兩類情況：判別函數(shù)d(x)多類情況：設(shè)模式可分成1, 2, M共M類，則有三種劃分方法多類情況1多類情況2多類情況3第6頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.1 線性判別函數(shù)3.1.2 線性判別函數(shù)分類問題多類情況1判別函數(shù)圖例例子第7頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.1 線性判別函數(shù)3.1.2 線性判別函數(shù)分類問題多類情況2判別函數(shù)圖例例子第8頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.1 線性判別函數(shù)3.1.2 線性判別函數(shù)分類問題多類情況3判別函數(shù)圖例例子第9頁，共47

4、頁，2022年，5月20日，6點(diǎn)26分，星期四3.1 線性判別函數(shù)3.1.2 線性判別函數(shù)線性可分模式分類如可用任一個(gè)線性函數(shù)來劃分，則這些模式就稱為線性可分的，否則就是非線性可分的。一旦線性函數(shù)的系數(shù)wk被確定，這些函數(shù)就可用作模式分類的基礎(chǔ)。第10頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.1 線性判別函數(shù)3.1.2 線性判別函數(shù)多類情況1和多類情況2的比較對(duì)于M類模式的分類，多類情況1需要M個(gè)判別函數(shù)，而多類情況2需要M*(M-1)/2個(gè)判別函數(shù)，當(dāng)M較大時(shí)，后者需要更多的判別式（這是多類情況2的一個(gè)缺點(diǎn)）。采用多類情況1時(shí)，每一個(gè)判別函數(shù)都要把一種類別的模式與其余M-1

5、種類別的模式分開，而不是將一種類別的模式僅于另一種類別的模式分開。由于一種模式的分布要比M-1種模式的分布更為聚集，因此多類情況2對(duì)模式是線性可分的可能性比多類情況1更大一些（這是多類情況2的一個(gè)優(yōu)點(diǎn)）。第11頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四作業(yè)（1）在一個(gè)10類的模式識(shí)別問題中，有3類單獨(dú)滿足多類情況1，其余的類別滿足多類情況2。問該模式識(shí)別問題所需判別函數(shù)的最少數(shù)目是多少？第12頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四作業(yè)（2）一個(gè)三類問題，其判別函數(shù)如下：d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-1設(shè)這些函數(shù)是在多

6、類情況1條件下確定的，繪出其判別界面和每一個(gè)模式類別的區(qū)域。設(shè)為多類情況2，并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。繪出其判別界面和多類情況2的區(qū)域。設(shè)d1(x), d2(x)和d3(x)是在多類情況3的條件下確定的，繪出其判別界面和每類的區(qū)域。第13頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.2 廣義線性判別函數(shù)出發(fā)點(diǎn)線性判別函數(shù)簡單，容易實(shí)現(xiàn)；非線性判別函數(shù)復(fù)雜，不容易實(shí)現(xiàn)；若能將非線性判別函數(shù)轉(zhuǎn)換為線性判別函數(shù)，則有利于模式分類的實(shí)現(xiàn)。第14頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.2 廣義線性判別函

7、數(shù)基本思想設(shè)有一個(gè)訓(xùn)練用的模式集x，在模式空間x中線性不可分，但在模式空間x*中線性可分，其中x*的各個(gè)分量是x的單值實(shí)函數(shù)，x*的維數(shù)k高于x的維數(shù)n，即若取x* = (f1(x), f2(x), ., fk(x), kn則分類界面在x*中是線性的，在x中是非線性的，此時(shí)只要將模式x進(jìn)行非線性變換，使之變換后得到維數(shù)更高的模式x*，就可以用線性判別函數(shù)來進(jìn)行分類。描述第15頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.2 廣義線性判別函數(shù)廣義線性判別函數(shù)的意義線性的判別函數(shù)fi(x)選用二次多項(xiàng)式函數(shù)x是二維的情況x是n維的情況fi(x)選用r次多項(xiàng)式函數(shù)， x是n維的情況例子

8、d(x)的總項(xiàng)數(shù)說明d(x)的項(xiàng)數(shù)隨r和n的增加會(huì)迅速增大，即使原來模式x的維數(shù)不高，若采用次數(shù)r較高的多項(xiàng)式來變換，也會(huì)使變換后的模式x*的維數(shù)很高，給分類帶來很大困難。實(shí)際情況可只取r=2，或只選多項(xiàng)式的一部分，例如r=2時(shí)只取二次項(xiàng)，略去一次項(xiàng)，以減少x*的維數(shù)。第16頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.2 廣義線性判別函數(shù)例子：一維樣本空間 -二維樣本空間第17頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.3 分段線性判別函數(shù)出發(fā)點(diǎn)線性判別函數(shù)在進(jìn)行分類決策時(shí)是最簡單有效的，但在實(shí)際應(yīng)用中，常常會(huì)出現(xiàn)不能用線性判別函數(shù)直接進(jìn)行分類的情況。采用廣義線

9、性判別函數(shù)的概念，可以通過增加維數(shù)來得到線性判別，但維數(shù)的大量增加會(huì)使在低維空間里在解析和計(jì)算上行得通的方法在高維空間遇到困難，增加計(jì)算的復(fù)雜性。引入分段線性判別函數(shù)的判別過程，它比一般的線性判別函數(shù)的錯(cuò)誤率小，但又比非線性判別函數(shù)簡單。第18頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.3 分段線性判別函數(shù)圖例：用判別函數(shù)分類可用一個(gè)二次判別函數(shù)來分類也可用一個(gè)分段線性判別函數(shù)來逼近這個(gè)二次曲線第19頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.3 分段線性判別函數(shù)分段線性判別函數(shù)的設(shè)計(jì)采用最小距離分類的方法最小距離分類第20頁，共47頁，2022年，5月20日，

10、6點(diǎn)26分，星期四3.3 分段線性判別函數(shù)圖例：分段線性分類設(shè)計(jì)第21頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.4 模式空間和權(quán)空間分類描述模式空間對(duì)一個(gè)線性方程w1x1+w2x2+w3x3=0，它在三維空間(x1 x2 x3)中是一個(gè)平面方程式，w=(w1 w2 w3)T是方程的系數(shù)。把w向量作為該平面的法線向量，則該線性方程決定的平面通過原點(diǎn)且與w垂直。第22頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.4 模式空間和權(quán)空間模式空間若x是二維的增廣向量，此時(shí)x3=1，則在非增廣的模式空間中即為x1, x2 二維坐標(biāo)，判別函數(shù)是下列聯(lián)立方程的解 w1x1+w2

11、x2+w3=0 x3=1即為這兩個(gè)平面相交的直線AB此時(shí)，w =(w1 w2)T為非增廣的權(quán)向量，它與直線AB垂直；AB將平面分為正、負(fù)兩側(cè)，w離開直線的一側(cè)為正， w射向直線的一側(cè)為負(fù)。第23頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.4 模式空間和權(quán)空間模式空間增廣向量決定的平面非增廣向量決定的直線第24頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.4 模式空間和權(quán)空間權(quán)空間若將方程x1w1+x2w2+w3=0繪在權(quán)向量w=(w1 w2 w3)T的三維空間中，則x=(x1 x2 1)T為方程的系數(shù)。若以x向量作為法線向量，則該線性方程所決定的平面為通過原點(diǎn)且與

12、法線向量垂直的平面，它同樣將權(quán)空間劃分為正、負(fù)兩邊。在系數(shù)x不變的條件下，若w值落在法線向量離開平面的一邊，則wTx0，若w值落在法線向量射向平面的一邊，則wTx 0，或當(dāng)xk+1屬于2時(shí)，Kk(xk+1)0，則積累位勢不做任何修改就可用作判別函數(shù)。由于一個(gè)模式樣本的錯(cuò)誤分類可造成積累位勢在訓(xùn)練時(shí)的變化，因此勢函數(shù)算法提供了確定1和2兩類判別函數(shù)的迭代過程。判別函數(shù)表達(dá)式第40頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.7 勢函數(shù)法 一種確定性的非線性分類方法3.7.2 勢函數(shù)的選擇選擇勢函數(shù)的條件：一般來說，若兩個(gè)n維向量x和xk的函數(shù)K(x, xk)同時(shí)滿足下列三個(gè)條件，則

13、可作為勢函數(shù)。K(x, xk)= K(xk, x)，并且當(dāng)且僅當(dāng)x=xk時(shí)達(dá)到最大值；當(dāng)向量x與xk的距離趨于無窮時(shí)，K(x, xk)趨于零；K(x, xk)是光滑函數(shù)，且是x與xk之間距離的單調(diào)下降函數(shù)。第41頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.7 勢函數(shù)法 一種確定性的非線性分類方法3.7.2 勢函數(shù)的選擇構(gòu)成勢函數(shù)的兩種方式第一類勢函數(shù)第二類勢函數(shù)第42頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.7 勢函數(shù)法 一種確定性的非線性分類方法3.7.2 勢函數(shù)的選擇例1第43頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.7 勢函數(shù)法 一種確定性的非線性分類方法3.7.2 勢函數(shù)的選擇例2第44頁，共47頁，2022年，5月20日，6點(diǎn)26分，星期四3.7 勢函數(shù)法 一種確定性的非線性分類方法3.7.2 勢函數(shù)的選擇討論用第二類勢函數(shù)，當(dāng)訓(xùn)練樣本維數(shù)和數(shù)目都較高時(shí)，需要計(jì)算和存儲(chǔ)的指數(shù)項(xiàng)較多。正因?yàn)閯莺瘮?shù)由許多新項(xiàng)組成，因此有很強(qiáng)的分類能力。第45頁，共