模式識別

PatternClassification

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

則可令判別函數

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

定義

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

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

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

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

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

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

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

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

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

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

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

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

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

n為學習樣本總數

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

即平方誤差函數

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