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

模式識(shí)別線性判別函數(shù)第1頁(yè)，共75頁(yè)，2023年，2月20日，星期五第六章:線性判別函數(shù)第2頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)原理利用判別函數(shù)將特征空間劃分為若干個(gè)決策區(qū)域，然后根據(jù)待識(shí)別樣本位于的決策區(qū)域來(lái)進(jìn)行判類是模式識(shí)別的重要方法之一3第3頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)判別函數(shù)的概念判別函數(shù)即是直接用來(lái)進(jìn)行模式分類的準(zhǔn)則函數(shù)例如在Bayes決策方法中，對(duì)c類模式有：這里的即可視為模式分類的準(zhǔn)則函數(shù)判別函數(shù)4第4頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)在特征空間中，判別函數(shù)還具有特殊的幾何意義和性質(zhì)5第5頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)對(duì)圖（a）所示的兩類模式，可以用一條直線（界面）將其分開(kāi)，設(shè)直線方程為：

則可令判別函數(shù)

則對(duì)類模式有對(duì)類模式有6第6頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)可用判別函數(shù)進(jìn)行模式分類，即當(dāng)待識(shí)樣本X到來(lái)時(shí)若，則判X屬于類若，則判X屬于類7第7頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)對(duì)圖（b）所示的兩類模式，用直線已不能將兩類模式分開(kāi)，分界線為二次曲線，判別函數(shù)為此時(shí)分界面仍具有如下性質(zhì)：若，則判X屬于類若，則判X屬于類8第8頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)判界面由所決定的界面稱為判別面，對(duì)判別面上（決策面）任一點(diǎn)均有判別面正面、反面的區(qū)域稱為判別面的正面，的區(qū)域稱為判別界的反面9第9頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)問(wèn)題判別函數(shù)的形式（線性、非線性）？根據(jù)先驗(yàn)知識(shí)決定判別函數(shù)中的系數(shù)？由已知類別的學(xué)習(xí)樣本確定多類問(wèn)題？化解為多個(gè)二類問(wèn)題10第10頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)

定義

d維特征空間中，若判別函數(shù)具有如下形式：其中：權(quán)向量閥值11第11頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)則稱滿足上述定義的函數(shù)為線性判別函數(shù)由線性判別函數(shù)決定的判別面（決策面）方程為：12第12頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)若令則線性判別函數(shù)可寫為，此時(shí)決策面為過(guò)原點(diǎn)的超平面

13第13頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)線性可分d維空間中的模式類如果能用線性判別函數(shù)將其分開(kāi)，則稱模式類為線性可分的線性可分線性不可分14第14頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)線性判別函數(shù)的幾何性質(zhì)15第15頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)下面以二維二類情況為例，分析線性判別函數(shù)的幾何性質(zhì)設(shè)、為判別面上的任意兩點(diǎn)，則有即：

g(X)=0WX1X216第16頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)性質(zhì)一：權(quán)向量w與判別面上任一向量正交，即w決定了判別界的方向17第17頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)設(shè)x為特征空間中的任一向量，則有：其中：18第18頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)將其代入中有：

由于為判別界上的點(diǎn),故19第19頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)因此有：性質(zhì)二：是以為單位的X到判決面的距離。若Ｘ在判別面的正面，則g(x)>0,若Ｘ在判別面的反面，則g(x)<0，判別界上g(x)=0。20第20頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)及其幾何性質(zhì)對(duì)于原點(diǎn)x=0，則性質(zhì)三：線性判別函數(shù)中的閥值W0表征了原點(diǎn)到判別界的距離。若W0>0，則原點(diǎn)位于判別界的正面；反之原點(diǎn)位于判別界反面。21第21頁(yè)，共75頁(yè)，2023年，2月20日，星期五多類情況下的線性判別函數(shù)問(wèn)題：多類情況下，如何用線性判別函數(shù)進(jìn)行分類？解決方案：化為多個(gè)二類問(wèn)題來(lái)解決！分三種情況來(lái)討論22第22頁(yè)，共75頁(yè)，2023年，2月20日，星期五多類情況下的線性判別函數(shù)情況一每個(gè)模式類均可用一個(gè)單獨(dú)的線性判別界與其余模式類分開(kāi)

23第23頁(yè)，共75頁(yè)，2023年，2月20日，星期五多類情況下的線性判別函數(shù)共需c個(gè)判別函數(shù)，且具有如下性質(zhì)：

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

顯然，應(yīng)有：27第27頁(yè)，共75頁(yè)，2023年，2月20日，星期五多類情況下的線性判別函數(shù)識(shí)別過(guò)程為：當(dāng)待識(shí)樣本Ｘ到來(lái)時(shí)，若對(duì)所有的j均有則判該方法仍然存在不定區(qū)，對(duì)不定區(qū)待識(shí)樣本，采用拒識(shí)策略28第28頁(yè)，共75頁(yè)，2023年，2月20日，星期五多類情況下的線性判別函數(shù)情況三不考慮二類問(wèn)題的線性判別函數(shù)，采用Ｃ個(gè)線性判別函數(shù)將Ｃ個(gè)模式分開(kāi)。判別函數(shù)為：識(shí)別準(zhǔn)則為：對(duì)所有的，若則判29第29頁(yè)，共75頁(yè)，2023年，2月20日，星期五多類情況下的線性判別函數(shù)該方法實(shí)際上是將特征空間劃分為R1,……，Rc

共C個(gè)判別區(qū)域，當(dāng)模式在Ri中時(shí),具有最大的函數(shù)值如果Ri與Rj相鄰，則決策面是方程的一部分該方法不存在不定區(qū)30第30頁(yè)，共75頁(yè)，2023年，2月20日，星期五多類情況下的線性判別函數(shù)R1R2R3R4g1(X)g4(X)g3(X)g2(X)31第31頁(yè)，共75頁(yè)，2023年，2月20日，星期五小結(jié)由上述分析可得，應(yīng)用線性判別函數(shù)的方法實(shí)際上是如何應(yīng)用學(xué)習(xí)樣本來(lái)確定線性判別函數(shù)參數(shù)的方法由于多類問(wèn)題可化為多個(gè)二類問(wèn)題來(lái)處理，故以下介紹二類問(wèn)題的線性判別函數(shù)學(xué)習(xí)算法32第32頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)的學(xué)習(xí)算法線性判別函數(shù)一般具有如下一般形式：現(xiàn)將其擴(kuò)展到增廣特征空間，即：33第33頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)的學(xué)習(xí)算法則線性判別函數(shù)可寫為：判別面為過(guò)原點(diǎn)的超平面根據(jù)判別函數(shù)的性質(zhì)，對(duì)于二類問(wèn)題有：若，則類若，則類34第34頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)的學(xué)習(xí)算法現(xiàn)對(duì)類樣本進(jìn)行歸一化處理，即令所有類樣本則二類分類問(wèn)題變?yōu)椋河桑蝹€(gè)學(xué)習(xí)樣本，找到權(quán)向量Ａ，使得對(duì)所有的學(xué)習(xí)樣本有：35第35頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)的學(xué)習(xí)算法滿足上述條件的向量A稱為解向量可見(jiàn)每個(gè)學(xué)習(xí)樣本都對(duì)解向量進(jìn)行了限制，解向量并不唯一。顯然，若存在解向量A使得二類樣本分類正確，則樣本是線性可分的36第36頁(yè)，共75頁(yè)，2023年，2月20日，星期五線性判別函數(shù)的學(xué)習(xí)算法解向量并不唯一：解區(qū)域

37第37頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法欲求解向量Ａ，即是根據(jù)學(xué)習(xí)樣本求解不等式組直接求解不等式是困難的！38第38頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法可將求Ａ的問(wèn)題轉(zhuǎn)化為標(biāo)量準(zhǔn)則函數(shù)求極值的問(wèn)題，即定義一個(gè)標(biāo)量函數(shù)J(A)，它具有如下的性質(zhì)：J(A)的值越小，判別面的分割質(zhì)量越高39第39頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法求標(biāo)題函數(shù)對(duì)矢量的極值問(wèn)題，可用優(yōu)化方法中的梯度下降法來(lái)解決標(biāo)量函數(shù)J(A)關(guān)于矢量Ａ的的梯度是一個(gè)向量，即：40第40頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法的方向是J(A)在向量Ａ處增加最快的方向反之，負(fù)梯度是J(A)在向量Ａ處減小得最快的方向的值的大小表示J(A)在Ａ處變化率的大小梯度等于０的點(diǎn)即是函數(shù)J(A)的極值點(diǎn)41第41頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法標(biāo)量函數(shù)關(guān)于向量的梯度

42第42頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法梯降法求解向量的一般思路：定義一個(gè)標(biāo)量準(zhǔn)則函數(shù)J(A,Y)，該函數(shù)不僅與解向量A有關(guān)，還與學(xué)習(xí)樣本Y有關(guān)當(dāng)準(zhǔn)則函數(shù)達(dá)到極值時(shí)，判別界的質(zhì)量最高通過(guò)迭代的方法找到函數(shù)J(A,Y)的極值點(diǎn)，即找到使得

J(A,Y)＝０的最佳解向量A43第43頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法如何用迭代方法求J(A,Y)極值點(diǎn)？如何定義標(biāo)量函數(shù)？44第44頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法迭代方法求J(A,Y)極值點(diǎn)k=1，任意選取初始解向量計(jì)算準(zhǔn)則函數(shù)在Ak處的梯度

向負(fù)梯度方向跨一步，令若，則顯然，停止。否則，令k=k+1，重復(fù)第二步，直到結(jié)束。45第45頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法感知準(zhǔn)則函數(shù)定義為：其含義是選擇了解向量Ａ后，被錯(cuò)分類的樣本到判別面的距離之和可見(jiàn)滿足，其存在極小值０，此時(shí)無(wú)錯(cuò)分類樣本

達(dá)到極小值時(shí)的解向量Ａ即是欲求的解向量！46第46頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法如何求感知準(zhǔn)則函數(shù)的梯度？即感知準(zhǔn)則函數(shù)的梯度為選取解向量Ａ后，所有被錯(cuò)分類的樣本之和的負(fù)值47第47頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法則迭代公式為：48第48頁(yè)，共75頁(yè)，2023年，2月20日，星期五感知準(zhǔn)則梯降法迭代方法求感知準(zhǔn)則函數(shù)極值點(diǎn)k=1，任意選取初始解向量遍歷所有樣本，計(jì)算找出選擇后被錯(cuò)分類的樣本（即的樣本）令：若，則停止。否則，令k=k+1，重復(fù)第三步，直到結(jié)束49第49頁(yè)，共75頁(yè)，2023年，2月20日，星期五固定增量算法感知準(zhǔn)則算法需一次獲取所有學(xué)習(xí)樣本，并在迭代算法中一次遍歷所有樣本在實(shí)際應(yīng)用中，有時(shí)樣本是分批獲取固定增量算法即是針對(duì)上述情況的改進(jìn)感知準(zhǔn)則算法基本思想是：每次修改解向量時(shí)，不需遍歷所有的樣本，而是將學(xué)習(xí)樣本序貫輸入，每考察一個(gè)樣本就對(duì)修改一次。50第50頁(yè)，共75頁(yè)，2023年，2月20日，星期五固定增量算法固定增量迭代算法任意選取初始解向量順序取出學(xué)習(xí)樣本，計(jì)算若，則不變?nèi)簦瑒t遍歷所有樣本，即，完成一次迭代令k=k+1，重復(fù)上述迭代，直至51第51頁(yè)，共75頁(yè)，2023年，2月20日，星期五固定增量算法存在的問(wèn)題初始解向量的選擇問(wèn)題？步長(zhǎng)的選取問(wèn)題？收斂性問(wèn)題？（感知收斂定理）結(jié)論：只要二類樣本是線性可分的，則固定增量算法一定收斂52第52頁(yè)，共75頁(yè)，2023年，2月20日，星期五最小平方誤差算法原理將求線性判別函數(shù)的不等式問(wèn)題轉(zhuǎn)化為求解等式的問(wèn)題，即令：其中為任意指定的正常數(shù)53第53頁(yè)，共75頁(yè)，2023年，2月20日，星期五最小平方誤差算法方法定義矩陣，其第i行是學(xué)習(xí)樣本Ｙi的各元素，即：54第54頁(yè)，共75頁(yè)，2023年，2月20日，星期五最小平方誤差算法令：

n為學(xué)習(xí)樣本總數(shù)

則等價(jià)于55第55頁(yè)，共75頁(yè)，2023年，2月20日，星期五最小平方誤差算法假如是非奇異矩陣，則可直接計(jì)算解向量但通常情況下，的行數(shù)常大于列數(shù)，即是方程式數(shù)目大于未知數(shù)數(shù)目的矛盾方程，一般無(wú)精確解56第56頁(yè)，共75頁(yè)，2023年，2月20日，星期五最小平方誤差算法此時(shí)可考慮尋找解向量Ａ，它使與b之間的誤差極小化定義誤差向量將平方誤差定義為準(zhǔn)則函數(shù)即平方誤差函數(shù)

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