模式識別-線性判別函數(shù)

1、模式識別-線性判別函數(shù)第1頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四第六章:線性判別函數(shù)第2頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)原理利用判別函數(shù)將特征空間劃分為若干個(gè)決策區(qū)域，然后根據(jù)待識別樣本位于的決策區(qū)域來進(jìn)行判類是模式識別的重要方法之一第3頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)判別函數(shù)的概念判別函數(shù)即是直接用來進(jìn)行模式分類的準(zhǔn)則函數(shù)例如在Bayes決策方法中，對c類模式有：這里的 即可視為模式分類的準(zhǔn)則函數(shù)判別函數(shù)第4頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)在特征空間中，判別函數(shù)還具有

2、特殊的幾何意義和性質(zhì)第5頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)對圖（a）所示的兩類模式，可以用一條直線（界面）將其分開，設(shè)直線方程為： 則可令判別函數(shù) 則對 類模式有 對 類模式有第6頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)可用判別函數(shù)進(jìn)行模式分類，即當(dāng)待識樣本X到來時(shí) 若 ，則判X屬于 類 若 ，則判X屬于 類第7頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)對圖（b）所示的兩類模式，用直線已不能將兩類模式分開，分界線為二次曲線，判別函數(shù)為 此時(shí)分界面仍具有如下性質(zhì)： 若 ，則判X屬于 類 若 ，則判X屬于 類第

3、8頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)判界面由 所決定的界面稱為判別面，對判別面上（決策面）任一點(diǎn)均有判別面正面、反面 的區(qū)域稱為判別面的正面， 的區(qū)域稱為判別界的反面 第9頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)問題判別函數(shù)的形式（線性、非線性）？根據(jù)先驗(yàn)知識決定判別函數(shù)中的系數(shù)？由已知類別的學(xué)習(xí)樣本確定多類問題？化解為多個(gè)二類問題第10頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)及其幾何性質(zhì) 定義 d維特征空間中，若判別函數(shù)具有如下形式：其中：權(quán)向量閥值第11頁，共75頁，2022年，5月20日，6點(diǎn)25分

4、，星期四線性判別函數(shù)及其幾何性質(zhì)則稱滿足上述定義的函數(shù) 為線性判別函數(shù)由線性判別函數(shù)決定的判別面（決策面）方程為：第12頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)及其幾何性質(zhì)若令 則線性判別函數(shù)可寫為 ，此時(shí)決策面為過原點(diǎn)的超平面 第13頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)及其幾何性質(zhì)線性可分d維空間中的模式類如果能用線性判別函數(shù)將其分開，則稱模式類為線性可分的線性可分線性不可分第14頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)及其幾何性質(zhì)線性判別函數(shù)的幾何性質(zhì) 第15頁，共75頁，2022年，5月20日，6點(diǎn)2

5、5分，星期四線性判別函數(shù)及其幾何性質(zhì)下面以二維二類情況為例，分析線性判別函數(shù)的幾何性質(zhì) 設(shè) 、 為判別面上的任意兩點(diǎn)，則有 即： g(X)=0WX1X2第16頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)及其幾何性質(zhì)性質(zhì)一：權(quán)向量w與判別面上任一向量正交，即w決定了判別界的方向第17頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)及其幾何性質(zhì)設(shè)x為特征空間中的任一向量，則有： 其中：第18頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)及其幾何性質(zhì)將其代入 中有： 由于 為判別界上的點(diǎn),故第19頁，共75頁，2022年，5月20日，

6、6點(diǎn)25分，星期四線性判別函數(shù)及其幾何性質(zhì)因此有：性質(zhì)二： 是以 為單位的X到判決面的距離。若在判別面的正面，則g(x)0, 若在判別面的反面，則g(x)0，則原點(diǎn)位于判別界的正面；反之原點(diǎn)位于判別界反面。 第21頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四多類情況下的線性判別函數(shù)問題：多類情況下，如何用線性判別函數(shù)進(jìn)行分類？解決方案：化為多個(gè)二類問題來解決！分三種情況來討論第22頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四多類情況下的線性判別函數(shù)情況一每個(gè)模式類均可用一個(gè)單獨(dú)的線性判別界與其余模式類分開 第23頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四多

7、類情況下的線性判別函數(shù)共需c個(gè)判別函數(shù)，且具有如下性質(zhì)：第24頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四多類情況下的線性判別函數(shù)當(dāng)待識樣本到來時(shí)，若 ，且 對所有的 j， ，則判 該方法實(shí)質(zhì)上是在特征空間中劃分出c個(gè)區(qū)域，并根據(jù)待識樣本落入的區(qū)域來決定屬于哪一類模式。 但該方法存在失效區(qū)或不定區(qū)，如圖中陰影部分，即存在多于一個(gè)的判別函數(shù)大于，或所有的判別函數(shù)都小于。第25頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四多類情況下的線性判別函數(shù)情況二線性判別界只能將模式類兩兩分開 第26頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四多類情況下的線性判別函數(shù)則需 個(gè)

8、判別函數(shù) 具有如下性質(zhì)： 顯然，應(yīng)有：第27頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四多類情況下的線性判別函數(shù)識別過程為：當(dāng)待識樣本到來時(shí)，若對所有的j均有 則判該方法仍然存在不定區(qū)，對不定區(qū)待識樣本，采用拒識策略第28頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四多類情況下的線性判別函數(shù)情況三不考慮二類問題的線性判別函數(shù)，采用個(gè)線性判別函數(shù)將個(gè)模式分開。判別函數(shù)為：識別準(zhǔn)則為：對所有的 ，若 則判第29頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四多類情況下的線性判別函數(shù)該方法實(shí)際上是將特征空間劃分為R1,， Rc 共C個(gè)判別區(qū)域，當(dāng)模式在Ri中時(shí), 具有最

9、大的函數(shù)值如果Ri與Rj相鄰，則決策面是方程 的一部分該方法不存在不定區(qū) 第30頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四多類情況下的線性判別函數(shù)R1R2R3R4g1(X)g4(X)g3(X)g2(X)第31頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四小結(jié)由上述分析可得，應(yīng)用線性判別函數(shù)的方法實(shí)際上是如何應(yīng)用學(xué)習(xí)樣本來確定線性判別函數(shù)參數(shù)的方法由于多類問題可化為多個(gè)二類問題來處理，故以下介紹二類問題的線性判別函數(shù)學(xué)習(xí)算法第32頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)的學(xué)習(xí)算法 線性判別函數(shù)一般具有如下一般形式：現(xiàn)將其擴(kuò)展到增廣特征空間，即：

10、第33頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)的學(xué)習(xí)算法 則線性判別函數(shù)可寫為：判別面 為過原點(diǎn)的超平面根據(jù)判別函數(shù)的性質(zhì)，對于二類問題有： 若 ，則 類 若 ，則 類第34頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)的學(xué)習(xí)算法 現(xiàn)對 類樣本進(jìn)行歸一化處理，即令所有 類樣本則二類分類問題變?yōu)椋河蓚€(gè)學(xué)習(xí)樣本，找到權(quán)向量，使得對所有的學(xué)習(xí)樣本有：第35頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)的學(xué)習(xí)算法 滿足上述條件的向量A稱為解向量可見每個(gè)學(xué)習(xí)樣本都對解向量進(jìn)行了限制，解向量并不唯一。顯然，若存在解向量A使得二類樣本分

11、類正確，則樣本是線性可分的第36頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四線性判別函數(shù)的學(xué)習(xí)算法 解向量并不唯一：解區(qū)域 第37頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法 欲求解向量，即是根據(jù)學(xué)習(xí)樣本求解不等式組直接求解不等式是困難的！第38頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法可將求的問題轉(zhuǎn)化為標(biāo)量準(zhǔn)則函數(shù)求極值的問題，即定義一個(gè)標(biāo)量函數(shù)J(A)，它具有如下的性質(zhì)：J(A)的值越小，判別面的分割質(zhì)量越高第39頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法求標(biāo)題函數(shù)對矢量的極值問題，可用優(yōu)化方法中

12、的梯度下降法來解決標(biāo)量函數(shù)J(A)關(guān)于矢量的的梯度是一個(gè)向量，即 ：第40頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法 的方向是J(A)在向量處增加最快的方向反之，負(fù)梯度 是J(A)在向量處減小得最快的方向 的值的大小 表示J(A)在處變化率的大小梯度等于的點(diǎn)即是函數(shù)J(A)的極值點(diǎn) 第41頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法標(biāo)量函數(shù)關(guān)于向量的梯度 第42頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法梯降法求解向量的一般思路：定義一個(gè)標(biāo)量準(zhǔn)則函數(shù)J(A,Y)，該函數(shù)不僅與解向量A有關(guān)，還與學(xué)習(xí)樣本Y有關(guān)當(dāng)準(zhǔn)則函

13、數(shù)達(dá)到極值時(shí)，判別界的質(zhì)量最高通過迭代的方法找到函數(shù)J(A,Y)的極值點(diǎn)，即找到使得J(A,Y)的最佳解向量A第43頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法如何用迭代方法求J(A,Y)極值點(diǎn)？如何定義標(biāo)量函數(shù)？第44頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法迭代方法求J(A,Y)極值點(diǎn)k=1，任意選取初始解向量計(jì)算準(zhǔn)則函數(shù)在Ak處的梯度 向負(fù)梯度方向跨一步，令 若 ，則顯然 ，停止。 否則，令k=k+1，重復(fù)第二步，直到結(jié)束。第45頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法感知準(zhǔn)則函數(shù)定義為：其含義是選擇了解

14、向量后，被錯(cuò)分類的樣本到判別面的距離之和可見滿足，其存在極小值，此時(shí)無錯(cuò)分類樣本達(dá)到極小值時(shí)的解向量即是欲求的解向量！第46頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法如何求感知準(zhǔn)則函數(shù)的梯度？即感知準(zhǔn)則函數(shù)的梯度為選取解向量后，所有被錯(cuò)分類的樣本之和的負(fù)值第47頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法則迭代公式為：第48頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四感知準(zhǔn)則梯降法迭代方法求感知準(zhǔn)則函數(shù)極值點(diǎn)k=1，任意選取初始解向量遍歷所有樣本，計(jì)算 找出選擇后被錯(cuò)分類的樣本（即的樣本）令： 若 ，則停止。 否則，令k=k+1

15、，重復(fù)第三步，直到結(jié)束第49頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四固定增量算法感知準(zhǔn)則算法需一次獲取所有學(xué)習(xí)樣本，并在迭代算法中一次遍歷所有樣本在實(shí)際應(yīng)用中，有時(shí)樣本是分批獲取固定增量算法即是針對上述情況的改進(jìn)感知準(zhǔn)則算法基本思想是：每次修改解向量時(shí)，不需遍歷所有的樣本，而是將學(xué)習(xí)樣本序貫輸入，每考察一個(gè)樣本就對修改一次。第50頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四固定增量算法固定增量迭代算法任意選取初始解向量順序取出學(xué)習(xí)樣本，計(jì)算若，則不變?nèi)?，則遍歷所有樣本，即，完成一次迭代令k=k+1，重復(fù)上述迭代，直至 第51頁，共75頁，2022年，5月20日，6點(diǎn)

16、25分，星期四固定增量算法存在的問題初始解向量的選擇問題？步長的選取問題？收斂性問題？（感知收斂定理）結(jié)論：只要二類樣本是線性可分的，則固定增量算法一定收斂 第52頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四最小平方誤差算法 原理將求線性判別函數(shù)的不等式問題轉(zhuǎn)化為求解等式的問題，即令：其中為任意指定的正常數(shù)第53頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四最小平方誤差算法方法定義矩陣，其第 i 行是學(xué)習(xí)樣本i 的各元素，即：第54頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四最小平方誤差算法令：n為學(xué)習(xí)樣本總數(shù)則 等價(jià)于第55頁，共75頁，2022年，5月20

17、日，6點(diǎn)25分，星期四最小平方誤差算法假如 是非奇異矩陣，則可直接計(jì)算解向量但通常情況下， 的行數(shù)常大于列數(shù)，即 是方程式數(shù)目大于未知數(shù)數(shù)目的矛盾方程，一般無精確解第56頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四最小平方誤差算法此時(shí)可考慮尋找解向量，它使 與b之間的誤差極小化定義誤差向量 將平方誤差定義為準(zhǔn)則函數(shù) 即平方誤差函數(shù) 第57頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四最小平方誤差算法 具有極小值，此時(shí)即為 的解如何求平方誤差函數(shù)的極值?求平方誤差函數(shù)極值方法偽逆法梯降法第58頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四最小平方誤差算法偽逆法則梯

18、度令即第59頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四最小平方誤差算法偽逆法可得解得最佳解向量為：稱為的偽逆矩陣第60頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四最小平方誤差算法偽逆法特點(diǎn)：偽逆法要求為非奇異矩陣，其逆才存在計(jì)算較為復(fù)雜第61頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四最小平方誤差算法梯降法由于則梯降法的迭代公式為：算法過程與感知準(zhǔn)則梯降法相同第62頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四isher 線性函數(shù)基本思想：在d維特征空間中，將所有樣本投影到一條過原點(diǎn)的直線上，將維數(shù)壓縮到維目標(biāo)：找到一個(gè)最優(yōu)的投影方向，使投影后的樣本最易于分類 第63頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四isher 線性函數(shù)WW第64頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四isher 線性函數(shù)設(shè)給定兩類學(xué)習(xí)樣本集和，共n個(gè)學(xué)習(xí)樣本，其中類樣本個(gè)，類樣本個(gè)現(xiàn)將任意學(xué)習(xí)樣本與權(quán)向量作內(nèi)積：則即是在方向上投影后的樣本第65頁，共75頁，2022年，5月20日，6點(diǎn)25分，星期四isher 線性函數(shù)是一標(biāo)量，是坐標(biāo)原點(diǎn)