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

模式識(shí)別

PatternClassification

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

則可令判別函數(shù)

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

定義

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

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

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

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

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

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

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

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

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

42AppliedPatternRecognitionCSE616感知準(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)＝０的最佳解向量A43AppliedPatternRecognitionCSE616感知準(zhǔn)則梯降法如何用迭代方法求J(A,Y)極值點(diǎn)？如何定義標(biāo)量函數(shù)？44AppliedPatternRecognitionCSE616感知準(zhǔn)則梯降法迭代方法求J(A,Y)極值點(diǎn)k=1，任意選取初始解向量計(jì)算準(zhǔn)則函數(shù)在Ak處的梯度

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

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

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

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

即平方誤差函數(shù)

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