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

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

則可令判別函數(shù)

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

定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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