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

模式識別

PatternClassification

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

則可令判別函數(shù)

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

定義

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

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

g(X)=0WX1X216AppliedPatternRecognitionCSE616線性判別函數(shù)及其幾何性質(zhì)性質(zhì)一：權(quán)向量w與判別面上任一向量正交，即w決定了判別界的方向17AppliedPatternRecognitionCSE616線性判別函數(shù)及其幾何性質(zhì)設(shè)x為特征空間中的任一向量，則有：其中：18AppliedPatternRecognitionCSE616線性判別函數(shù)及其幾何性質(zhì)將其代入中有：

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

23AppliedPatternRecognitionCSE616多類情況下的線性判別函數(shù)共需c個判別函數(shù)，且具有如下性質(zhì)：

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

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

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

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

42AppliedPatternRecognitionCSE616感知準則梯降法梯降法求解向量的一般思路：定義一個標量準則函數(shù)J(A,Y)，該函數(shù)不僅與解向量A有關(guān)，還與學習樣本Y有關(guān)當準則函數(shù)達到極值時，判別界的質(zhì)量最高通過迭代的方法找到函數(shù)J(A,Y)的極值點，即找到使得

J(A,Y)＝０的最佳解向量A43AppliedPatternRecognitionCSE616感知準則梯降法如何用迭代方法求J(A,Y)極值點？如何定義標量函數(shù)？44AppliedPatternRecognitionCSE616感知準則梯降法迭代方法求J(A,Y)極值點k=1，任意選取初始解向量計算準則函數(shù)在Ak處的梯度

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

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

n為學習樣本總數(shù)

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

即平方誤差函數(shù)

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