模式識別-特征選擇

1、提綱n圖像的特征提取圖像的特征提取n模式類別可分性度量模式類別可分性度量n基于類可分性度量的特征提取與選擇基于類可分性度量的特征提取與選擇n離散離散K-LK-L變換及其在特征提取與選擇中變換及其在特征提取與選擇中的應(yīng)用的應(yīng)用n特征選擇中的直接挑選法特征選擇中的直接挑選法一、圖像的特征提取一、圖像的特征提取特征提取與選擇特征提取與選擇 模式識別的三大核心問題模式識別的三大核心問題: :特征提取與選擇特征提取與選擇圖像的特征提取圖像的特征提取特征數(shù)據(jù)采集特征數(shù)據(jù)采集分類識別分類識別特征提取與選擇特征提取與選擇 分類識別的正確率取決于對象的表示、訓(xùn)練學(xué)習(xí)和分類識別算法，我們在前面的學(xué)習(xí)中詳細(xì)討論了后

2、兩方面的內(nèi)容。本章介紹的特征提取與選擇問題則是對象表示的一個(gè)關(guān)鍵問題。 通常在得到實(shí)際對象的若干具體特征之后，通常在得到實(shí)際對象的若干具體特征之后，再再由由這些這些原始特征產(chǎn)生原始特征產(chǎn)生出對分類識別出對分類識別最有效、數(shù)最有效、數(shù)目最少的特征目最少的特征，這就是特征提取與選擇的任務(wù)。，這就是特征提取與選擇的任務(wù)。從本質(zhì)上講，我們的目的是使從本質(zhì)上講，我們的目的是使在最小維數(shù)特征空在最小維數(shù)特征空間間中異類模式點(diǎn)相距較遠(yuǎn)（中異類模式點(diǎn)相距較遠(yuǎn)（類間距離較大類間距離較大），而），而同類模式點(diǎn)相距較近（同類模式點(diǎn)相距較近（類內(nèi)距離較小類內(nèi)距離較小）。）。 特征提取與選擇特征提取與選擇圖像的特征提取

3、圖像的特征提取圖像的特征提取圖像的特征提取兩個(gè)基本途徑兩個(gè)基本途徑主要方法有：分支定界法、用回歸建模技術(shù)確定相關(guān)特征等方法。（1 1）直接選擇法：）直接選擇法：當(dāng)實(shí)際用于分類識別的特征數(shù)目d 確定后，直接從已獲得的n 個(gè)原始特征中選出d 個(gè)特征 ，使可分性判據(jù)J 的值滿足下式：dxxx,21J x xxJ xxxdiiid1212,max,式中 是n 個(gè)原始特征中的任意d 個(gè)特征，上式表示直接尋找n 維特征空間中的d 維子空間。idiixxx,21(max)121212( ,)(,) ,Jndinxx xxyy yydn yx xx（2 2）變換法：）變換法：在使判據(jù)J 取最大的目標(biāo)下，對n

4、個(gè)原始特征進(jìn)行變換降維，即對原n 維特征空間進(jìn)行坐標(biāo)變換，然后再取子空間。主要方法有：基于可分性判據(jù)的特征選擇、基于誤判概率的特征選擇、離散K-L變換法(DKLT)、基于決策界的特征選擇等方法。圖像的特征提取圖像的特征提取兩個(gè)基本途徑兩個(gè)基本途徑(max)1212( ,)( )(,), Jndxx xxyh xy yydn(c)是具有分類能力的特征，故選(c)，扔掉(a) 、 (b) 。BA解：法1 特征選擇：測量三個(gè)結(jié)構(gòu)特征 (a) 周長 (b) 面積 (c)兩個(gè)互相垂直的內(nèi)徑比 特征選擇：一般根據(jù)物理特征或結(jié)構(gòu)特征進(jìn)行壓縮。 分析：例：特征選擇與特征提取的區(qū)別：對一個(gè)條形和圓進(jìn)行識別。 當(dāng)

5、”模式”在空間中發(fā)生移動、旋轉(zhuǎn)、縮放時(shí)，特征值應(yīng)保持不變，保證仍可得到同樣的識別效果。法2： 特征抽?。簻y量物體向兩個(gè)坐標(biāo)軸的投影值，則A、B各有2個(gè)值域區(qū)間?？梢钥闯觯瑑蓚€(gè)物體的投影有重疊，直接使用投影值無法將兩者區(qū)分開。 分析：將坐標(biāo)系按逆時(shí)針方向做一旋轉(zhuǎn)變化，或物體按順時(shí)針方向變，并適當(dāng)平移等。根據(jù)物體在 軸上投影的坐標(biāo)值的正負(fù)可區(qū)分兩個(gè)物體。2x特征提取，一般用數(shù)學(xué)的方法進(jìn)行壓縮。 BA2x1x22Bx22Ax12Bx12Ax11Bx11Ax21Bx21AxA2x1x2x1x二、模式類別可分性度量二、模式類別可分性度量特征提取與選擇特征提取與選擇模式類別可分性度量模式類別可分性度量 為

6、確立特征提取和選擇的準(zhǔn)則：引入類別可分性為確立特征提取和選擇的準(zhǔn)則：引入類別可分性判據(jù)，來表征特征對分類的貢獻(xiàn)。為此希望所構(gòu)造判據(jù)，來表征特征對分類的貢獻(xiàn)。為此希望所構(gòu)造的可分性判據(jù)的可分性判據(jù)J滿足下列要求：滿足下列要求：構(gòu)造可分性判據(jù)構(gòu)造可分性判據(jù)(1)可分性判據(jù)J與誤判概率P(e) (或誤分概率的上界、下界)有單調(diào)關(guān)系，J最大時(shí)，P(e)最小。(2)當(dāng)特征相互獨(dú)立時(shí)，判據(jù)有可加性 Jx xxJxi jdi jkdk(,)()121式中，x xxd12,是對不同種類特征的測量值，Ji j( ) 表示使用括號中特征(組)時(shí)第i 類與第j類可分性判據(jù)函數(shù)。(3) 判據(jù)具有“距離”的某些特性Ji

7、 j 0，當(dāng)，當(dāng)ij時(shí)；時(shí)；Ji j 0，當(dāng)，當(dāng)ij時(shí)；時(shí)；JJi jji(4) 對特征數(shù)目是單調(diào)不減，即加入新的特征后，判據(jù)值不減。 Jx xxJx xxxi jdi jdd(,)(,)12121模式類別可分性度量模式類別可分性度量構(gòu)造可分性判據(jù)構(gòu)造可分性判據(jù)值得注意的是：對構(gòu)造可分性判據(jù)J的要求，“單調(diào)性”、“疊加性”、“距離性”、“單調(diào)不減性”。在實(shí)際應(yīng)用并不一定能同時(shí)具備，但并不影響它在實(shí)際使用中的價(jià)值。 模式類別可分性度量模式類別可分性度量構(gòu)造可分性判據(jù)構(gòu)造可分性判據(jù)基于幾何距離的可分性判據(jù)基于幾何距離的可分性判據(jù)基于距離的可分性度量 一般來講，不同類的模式可以被區(qū)分是由于它們所屬類

8、別在特征空間中的類域是不同的區(qū)域。顯然，區(qū)域重疊的部分越小或完全沒有重疊，類別的可分性就越好。因此可以用距離或離差測度（散度）來構(gòu)造類別的可分性判據(jù)J。 模式類別可分性度量模式類別可分性度量(一) 點(diǎn)與點(diǎn)的距離 d a babababkkkn( , )() ()()/T1 2211 2(二) 點(diǎn)到點(diǎn)集的距離),(1) ,()(12)(2ikNkiikaxdNaxdi用均方歐氏距離表示基于距離的可分性度量i表示點(diǎn)集的序號,一共有Ni個(gè)點(diǎn)點(diǎn)X到點(diǎn)集中所有點(diǎn)的距離平方和求平均(三) 類內(nèi)及總體的均值矢量 ciiimPm1)(各類模式的總體均值矢量 iNkikiixNm1)()(1類的均值矢量： ci

9、, 2 , 1 Pi為相應(yīng)類的先驗(yàn)概率，當(dāng)用統(tǒng)計(jì)量代替先驗(yàn)概率時(shí)，總體均值矢量可表示為：NllciNkikiciiiciixNxNmNNmPmi111)()(1)(111基于距離的可分性度量某一類的樣本集的中心(重心)全體樣本的中心(重心)(四) 類內(nèi)距離 )()(1)()()(T)()(12iikiikNkiimxmxNdi類內(nèi)均方歐氏距離 類內(nèi)均方距離也可定義為： iiNkNlilikiiicxxdNNd11)()(22),() 1(1)(五) 類內(nèi)離差矩陣 T)()()()(1)(1iikiikNkimxmxNSii)(2iSTrdi顯然顯然12121 122.nnnnaaaaaa aa

10、 aa aa11 12112122221212nnnnnnnnaa aa aa aaa aa aa aaaaaa aa aa a其中其中“Tr”表示矩陣的跡（對角線元素的和）表示矩陣的跡（對角線元素的和）基于距離的可分性度量一類樣本每一點(diǎn)到類中心的距離的平方和求平均(五) 類內(nèi)離差矩陣(續(xù)) T)()()()(1)(1iikiikNkimxmxNSii( )( )iiE xm( )( )( )( )( )T( )( )( )( )( )( )11121( )( )( )( )( )( )21222( )( )( )( )( )( )12()()(,)(,)(,)(,)(,)(,)(,)(,)(

11、,)iiiiiiiiiiiiniiiiiiniiiiiinnnnSExE xxE xCov xxCov xxCov xxCov xxCov xxCov xxCov xxCov xxCov xx222212()()()()iiinid顯然顯然類內(nèi)離差矩陣表類內(nèi)離差矩陣表示各類模式在類示各類模式在類的均值矢量周圍的均值矢量周圍的散布情況。的散布情況。 基于距離的可分性度量協(xié)方差(六) 兩類之間的距離 ( )( )111(,)(,)jiNNijijklklijdd xxN N 基于距離的可分性度量兩類樣本之間任意連線的平均值兩類樣本之間任意連線的平均平方和2( )( )T( )( )11()() (

12、)iNiiiiikkkidxmxmN類內(nèi)均方歐氏距離2( )( )T( )( )111(,)() ()jiNNijijijklklklijdxxxxN N (六) 兩類之間的距離 ( )( )111(,)(,)jiNNijijklklijdd xxN N (七) 各類模式之間的總的均方距離 基于距離的可分性度量兩類樣本之間任意連線的平均值兩類樣本之間任意連線的平均平方和多類之間,兩兩求類間距離的加權(quán)和2( )( )T( )( )111(,)() ()jiNNijijijklklklijdxxxxN N 22( )( )111111( )(,)2jiNNccijijklijklijdxPPdxx

13、N N (六) 兩類之間的距離 ( )( )111(,)(,)jiNNijijklklijdd xxN N 2( )( )T( )( )111(,)() ()jiNNijijijklklklijdxxxxN N (七) 各類模式之間的總的均方距離 22( )( )111111( )(,)2jiNNccijijklijklijdxPPdxxN N 當(dāng)取歐氏距離時(shí)，總的均方距離為)()(121)()()(11T)()(112jlikNkNljlikjicjjciixxxxNNPPxdij基于距離的可分性度量兩類樣本之間任意連線的平均值兩類樣本之間任意連線的平均平方和多類之間,兩兩求類間距離的加權(quán)和

14、(八) 多類情況下總的類內(nèi)、類間及總體離差矩陣 iiNkiikiikiciiciiWmxmxNPSPS1T)()()()(11)(1總的類內(nèi)離差矩陣總的類內(nèi)離差矩陣ciiiiBmmmmPS1T)()()(總的類間離差矩陣總的類間離差矩陣T)()()()(1)(1iikiikNkimxmxNSii類內(nèi)離類內(nèi)離差矩陣差矩陣 基于距離的可分性度量類協(xié)方差協(xié)方差加權(quán)和(八) 多類情況下總的類內(nèi)、類間及總體離差矩陣（續(xù)） 總體離差矩陣總體離差矩陣 BWNlllTSSmxmxNS1T)(1( )( )( )( )T111()()iNciiiiWikkikiSPxmxmNciiiiBmmmmPS1T)()(

15、)(基于距離的可分性度量不分類的樣本協(xié)方差( )( )( )( )T( )( )T111( )( )( )( )T( )( )T111()()()()1()()()()iiNcciiiiiiWBikkiikiiNciiiiiiikkikiSSPxmxmP mm mmNPxmxmmm mmNTTTTTTT()()()()ABABABABAAABBABB( )( )T( )( )T( )( )T( )( )T11( )( )T( )T( )TT11iNciiiiiiiiWBikkkkikiciiiiiiSSPxxxmm xm mNP m mm mmmmm (八) 多類情況下總的類內(nèi)、類間及總體離差

16、矩陣（續(xù)） 總體離差矩陣總體離差矩陣 BWNlllTSSmxmxNS1T)(1基于距離的可分性度量不分類的樣本協(xié)方差( )( )T( )( )T( )( )T( )( )T11( )( )T( )T( )TT11iNciiiiiiiiWBikkkkikiciiiiiiSSPxxxmm xm mNP m mm mmmmm T( )( )T( )( )T( )( )T( )( )T( )( )( )( )T1111( )( )T( )( )T11111,1iiiiiNNNNiiiiiiiiiiiikkkkkkkkiiiiNiiiikixmxmm mm xmxm mNNNNm mm mN( )( )

17、T( )T( )TT11( )( )T( )T( )TT1111iiNciiiiWBikkikiNciiiiikkkkikiSSPxxm mmmmmNPxxxmmxmmN (八) 多類情況下總的類內(nèi)、類間及總體離差矩陣（續(xù)） 總體離差矩陣總體離差矩陣 BWNlllTSSmxmxNS1T)(1基于距離的可分性度量不分類的樣本協(xié)方差TTTTTTT()()()()ABABABABAAABBABB( )( )TT11111()()()()iNcNiiWBikkllTikliSSPxm xmxm xmSNN( )( )T( )T( )TT11( )( )T( )T( )TT1111iiNciiiiWBi

18、kkikiNciiiiikkkkikiSSPxxm mmmmmNPxxxmmxmmN (八) 多類情況下總的類內(nèi)、類間及總體離差矩陣（續(xù)） 總體離差矩陣總體離差矩陣 BWNlllTSSmxmxNS1T)(1基于距離的可分性度量222212( )WBTndxTr SSTr ST111212122212( )( )( ,)( ,)( ,)(,)(,)(,)(,)(,)(,)TnnnnnnSExE xxE xCov x xCov x xCov x xCov x xCov x xCov x xCov xxCov xxCov xx不分類的樣本協(xié)方差JTr SSWB11JSSBW2lnJTr STr SB

19、W3JSSSSSWBWTW4SW、SBST構(gòu)造不同的可分性判據(jù)：可以用、和J1、J2J4J3可以證明在任何非奇異線性變換下與坐標(biāo)系有關(guān)。是不變的，基于距離的可分性度量類間類間類內(nèi)類內(nèi)類間類間類內(nèi)類內(nèi)類間類間類內(nèi)類內(nèi)總體總體類內(nèi)類內(nèi)標(biāo)準(zhǔn)差基于類的概率密度函數(shù)的可分性判據(jù)考慮兩類問題。上圖是一維的兩類概率分布密度。 (a) 表示兩類是完全可分的。(b)是完全不可分的。 可用兩類概密函數(shù)的重疊程度來度量可分性，可用兩類概密函數(shù)的重疊程度來度量可分性，構(gòu)造基于類概密的可分性判據(jù)。此處的所謂重疊構(gòu)造基于類概密的可分性判據(jù)。此處的所謂重疊程度是指兩個(gè)概密函數(shù)相似的程度。程度是指兩個(gè)概密函數(shù)相似的程度。 由

20、類概密構(gòu)造的可分性判據(jù)由類概密構(gòu)造的可分性判據(jù)Jp應(yīng)滿足應(yīng)滿足: : (1)(1)Jp 0； (2)(2)當(dāng)兩類概密函數(shù)完全不重疊時(shí)，當(dāng)兩類概密函數(shù)完全不重疊時(shí)，Jp max； (3)(3)當(dāng)兩類概密函數(shù)完全重合時(shí)，當(dāng)兩類概密函數(shù)完全重合時(shí)，Jp 0； (4)(4)相對于兩個(gè)概密具有相對于兩個(gè)概密具有 “對稱性對稱性”?；陬惖母怕拭芏群瘮?shù)的可分性判據(jù)( (一一) ) BhattacharyyaBhattacharyya 判據(jù)判據(jù)( (J JB B) )受相關(guān)概念與應(yīng)用的啟發(fā)，我們可以構(gòu)造B- -判據(jù)，它的計(jì)算式為基于類的概率密度函數(shù)的可分性判據(jù)1/212ln() ()BJp xp xdx 滿

21、足Jij=0滿足對稱性Jij=Jji1/212121() ()()()12p xp xdxp xp xdx( (一一) ) BhattacharyyaBhattacharyya 判據(jù)判據(jù)( (J JB B) )受相關(guān)概念與應(yīng)用的啟發(fā)，我們可以構(gòu)造B- -判據(jù)，它的計(jì)算式為 式中表示特征空間。在最小誤判概率準(zhǔn)則下，誤判概率有 基于類的概率密度函數(shù)的可分性判據(jù)1/212ln() ()BJp xp xdx 1/2012( )() ()expBP ePPJ滿足對稱性Jij=Jji12()()ln10Bp xp xJ 1212+()(), () ()1,ln0Bp xp xp xp xJ 與基本不重疊證

22、明：設(shè)P e( )為誤分概率，則最小誤分概率為：基于類的概率密度函數(shù)的可分性判據(jù)210112211221/211221/21/212121/212( )min( )min()()()()min() (), () ()() () () ()() ()() ()() ()expBP eP ePp xdxPp xdxPp xPp xdxPp xPp xdxPPp xp xdxPPJ（二）（二） Chernoff 判據(jù)判據(jù) ( () )我們可以構(gòu)造比我們可以構(gòu)造比更一般的判據(jù)，稱其為更一般的判據(jù)，稱其為其定義式為其定義式為判據(jù)，判據(jù)，1121212ln()()( ;,)(,; )( ) 0s0)因?yàn)椋?/p>

23、當(dāng) 0 s 1 時(shí) f(s) = -asb1-s(ln(a)-ln(b)2 0)因?yàn)?，?dāng) 0 s 1 時(shí) f(s) = -asb1-s(ln(a)-ln(b)2 0, 0 s 1 )由該不等式有：xdxpxpsJssc12121)|()|(ln),(1212ln ( |)(1) ( |)ln( |)+(1)( |)=ln(1)0sp xs p xdxs p xdxsp xdxss 01,0CSJ對于一切Jc Jc 性質(zhì)（性質(zhì)（2 2）證明：）證明：只考慮連續(xù)的情況：由前面的證明可知:要Jc=0,必須有實(shí)際上也就是前面的 sa+(1-s)b = asb1-s因?yàn)閒(s)=0 ，使f(s)=0的充

24、要條件是a=b 1201,=0(|)(|)CSJp Xp X對于一切11212( |)( |)=( |)(1) ( |)ssp xp xsp xs p x111( )(1)lnlnssssssf ssas ba babaa babb求f(s)極值點(diǎn)1( )lnln0ssf saba bab111,0lnlnlnlnln0sssssbka kaba babakaa kaaka設(shè)11ln01ln11ln1ln1lnsssssakaakkakakkkkkkkkkkkk Jc Jc 性質(zhì)（性質(zhì)（2 2）證明：）證明：只考慮連續(xù)的情況：由前面的證明可知:要Jc=0,必須有實(shí)際上也就是前面的 sa+(1-

25、s)b = asb1-s因?yàn)閒(s)=0 ，使f(s)=0的充要條件是a=b )|()|(21xpxpJC=0 1201,=0(|)(|)CSJp Xp X對于一切11212( |)( |)=( |)(1) ( |)ssp xp xsp xs p x,1ln,0sbkakkkk k設(shè)有1,10,ln0skkkkk如果,1,( )0,( )=0kabf sf s所以 有且只有即時(shí)有最小值 absa+(1-s)b = asb1-sJc Jc 性質(zhì)（性質(zhì)（6 6）證明：）證明：設(shè)P(e)為最小誤分概率，則：P eP ePp xdxPp xdxPp xPp xdx01122112221( )min(

26、)min()()()()min() (),() ()利用不等式 ，由上式進(jìn)一步可得： 1min,0,0,01ssa ba babsP ePPp xp xdxPPJssssssC0121121121( )()()()()()()exp 101212()()exp,;(01)SSCP ePPJss 由JB和JC的定義知：JB=JC(1/2)對兩類都是正態(tài)分布正態(tài)分布情況: p xN mC() (,)( )111p xN mC() (,)( )222112(1)(2) T(1)(2)12112(1)11(1)()(1)()ln22Csss CsCJss mms CsCmmCC112(1)(2)T(1

27、)(2)121/21/2121()1112()()()ln2822BCCCCCJJsmmmmCC基于類的概率密度函數(shù)的可分性判據(jù)112ln()()ssCJp xp xdx 11/2/211( |)exp()()22Tiiiidip xxmCxmC當(dāng)12CCC時(shí)，)()(81)()(1 (21)2()1(1T)2()1()2()1(1T)2()1(mmCmmJmmCmmssJBC基于類的概率密度函數(shù)的可分性判據(jù)Jp xp xp xdxCs ln()()()122實(shí)際上 這就啟發(fā)我們運(yùn)用兩個(gè)概密的比或差來描述兩個(gè)概密重迭或相似的程度。 xdxpxpJssC121)()(ln可以寫成： 基于類的概率

28、密度函數(shù)的可分性判據(jù)( (三三) )散度散度J JD D (Divergence) (Divergence)i類對j類的平均可分性信息為： ( |)( |)( )ln( |)ln( |)( |)iiijijjp xp xIxEp xdxp xp x( |)( |)( )ln( |)ln( |)( |)jjjijiip xp xIxEp xdxp xp xj 對i 類的平均可分性信息為：基于類的概率密度函數(shù)的可分性判據(jù)似然比( (三三) )散度散度J JD D (Divergence) (Divergence)i類對j類的平均可分性信息為： 基于類的概率密度函數(shù)的可分性判據(jù)11/2/211( |

29、)exp()()22Tiiiidip xxCxC11( |)111ln( |)222TTjiiiijjjjiCp xTr CxxTr Cxxp xC( |)( )( |)ln( |)iijijp xIxp xdxp x1111111( )( |)ln22211ln( |)221( |)2TTjijiiiijjjiTjiiiiiTjjjiCIxp xTr CxxTr CxxdxCCTr Cxxp xdxCTr Cxxp xdx( (三三) )散度散度J JD D (Divergence) (Divergence)i類對j類的平均可分性信息為： 基于類的概率密度函數(shù)的可分性判據(jù)11/2/211(

30、|)exp()()22Tiiiidip xxCxC( |)( )( |)ln( |)iijijp xIxp xdxp x111111111( )ln( |)221( |)2111ln( |)222111ln222TjijiiiiiTjjjiTjiijiijiijiiTjijijijijiCIxTr Cxxp xdxCTr Cxxp xdxCTr C CTr Cxxp xdxCCTr CCCTr CC1( )( )( |) ( |)( |)ln( |)(,)( ,)Di jjiiijjdefdefDijDnJIxIxp xp xp xd xp xJJxx 對于i和j兩類總的平均可分性信息稱為散度

31、，其定義為兩類平均可分性信息之和，即 ( (三三) )散度散度JD (Divergence)JD (Divergence)基于類的概率密度函數(shù)的可分性判據(jù)當(dāng)兩類都是正態(tài)分布正態(tài)分布時(shí)： 11T11112() ()()22DijjiijijijJTr C CCCICC當(dāng)C Ci i=C=Cj j=C=C時(shí)T1()()8DijijBJCJ基于類的概率密度函數(shù)的可分性判據(jù)111111( )ln222TjijijijijijiCIxTr CCCTr CC1111( )( )1122Di jjiTijjiijijijJIxIxTrCCCCTrCC,TTTr BAA B AB皆向量散度具有如下性質(zhì)： Jx

32、xxJxxxxknDkDkk(,),121121() (1) JD 0；(2) 對稱性: JD(1 , 2)= JD(2 , 1); Jp xp xD012()()(3) Jx xxJxknDkDjjk(,)()121 (4) 當(dāng)x 各分量x1,x2,xn相互獨(dú)立時(shí)，(具有可加性) (5) 當(dāng)x各分量x1,x2,xn相互獨(dú)立時(shí)，(對特征數(shù)目單調(diào)不減)基于類的概率密度函數(shù)的可分性判據(jù)一般情況下，散度與誤分概率(或其上下界)之間的直接解析關(guān)系很難得到，但實(shí)驗(yàn)可以證明它們之間存在著單調(diào)關(guān)系。例如兩類都是正態(tài)分布，且有相同的協(xié)方差陣時(shí)， 是 的單調(diào)減函數(shù)。P e0( )JDJDP eydyJD0212

33、122( )exp當(dāng)兩類先驗(yàn)概率相等且為具有相同協(xié)方差的正態(tài)分布時(shí)，則最小誤分概率與 的關(guān)系為：基于類的概率密度函數(shù)的可分性判據(jù)對于c類問題類問題，可采用平均B-判據(jù)、C-判據(jù)、D-判據(jù)： cicijjiBjiBJPPJ11),()()( cicijjiCjiCJPPJ11),()()( cicijjiDjiDJPPJ11),()()(由JB、JC、JD的定義式結(jié)構(gòu)以及它們與誤分概率的關(guān)系可以知道，所選取的特征矢量應(yīng)使所對應(yīng)的JB、JC 、JD盡量大，這樣可分性就較好?；陬惖母怕拭芏群瘮?shù)的可分性判據(jù)大蓋小問題大蓋小問題 在特征空間中，若有某兩類間的在特征空間中，若有某兩類間的JB、JC或或J

34、D很大很大，可使平均判據(jù)變大，這樣就掩蓋了某些類對的判據(jù)，可使平均判據(jù)變大，這樣就掩蓋了某些類對的判據(jù)值較小的情況存在，從而可能降低總的分類正確率，值較小的情況存在，從而可能降低總的分類正確率，即所謂的即所謂的大蓋小問題大蓋小問題。為改善這種情況，可對每個(gè)類。為改善這種情況，可對每個(gè)類對的判據(jù)采用變換的方法，使對小的判據(jù)較敏感。例對的判據(jù)采用變換的方法，使對小的判據(jù)較敏感。例如，對如，對JD ，可采用變換，可采用變換8),(exp1),(jiDjiDJJ8),(exp1),(jiDjiDJJ這樣，當(dāng)i和j兩類模式相距很遠(yuǎn)時(shí)，JD(i,j)變得很大，但 也只能接近于1。但對于散度JD(i,j)

35、小的情況， 又變得較敏感。于是，總的平均(變換)判據(jù)為 ),(jiDJ),(jiDJ),()()(11jicicijDjiDJPPJ 基于類的概率密度函數(shù)的可分性判據(jù) cicijjiDjiDJPPJ11),()()(同樣對于JB，兩類問題與多類問題的平均判據(jù)分別為：1 2(,)22exp(,)BijBijJJ 兩類：11() ()(,)ccBijBijij iJPPJ C類平均判據(jù)：基于類的概率密度函數(shù)的可分性判據(jù)1/212ln() ()BJp xp xdx 1/21/212(,)22() ()BijJp xp xdx 0(,)2BijJ 基于后驗(yàn)概率的可分性判據(jù)在信息論中，熵(Entropy

36、)表示不確定性，熵越大不確定性越大。可以借用熵的概念來描述各類的可分性。pxi()對于c類問題，給定各類的后驗(yàn)概率 可以寫成如下形式：12121212()()()defccccpxpxpxppp熵的定義：11( )( )log()log()ccdefiiiiiiH xH ppppxpx 由洛必達(dá)法則知：當(dāng) 時(shí)pi 00logiipp熵的主要性質(zhì)：熵的主要性質(zhì)：(1) ，即 是有下界的非負(fù)數(shù)。當(dāng)且僅當(dāng)某個(gè)i 有pi =1而其余的 時(shí)等號成立，即確定場熵最小。H p( ) 0H p( )pjij0()例如：顯然這時(shí)能完全正確的分類識別 pxi()1pxjij(), 0基于后驗(yàn)概率的可分性判據(jù)熵的主

37、要性質(zhì)：熵的主要性質(zhì)：(2) (2) ，即，即 有上界。當(dāng)且僅當(dāng)有上界。當(dāng)且僅當(dāng) 時(shí)等號成立，即時(shí)等號成立，即等概率場熵最大，等概率場熵最大，識別最困難。識別最困難。12(,)logcH ppcH p( )1(1,2, )ipicC(3) (3) 是是 的連續(xù)上凸函數(shù)。的連續(xù)上凸函數(shù)。H p( )p基于后驗(yàn)概率的可分性判據(jù)(4)(4)2122112132121,)(),(),(ppppppHppppppHpppHcc121231212121122121212312121212121212123121211(,)(),()loglogloglog()logloglogloglogcciiicii

38、ippH pppppp Hpppppppppppppppppppppppppppppppppppppppp 12221212311212logloglog(,)cciiiiciippppppppppH p pppppp 熵的主要性質(zhì)：熵的主要性質(zhì)：(2) (2) ，即，即 有上界。當(dāng)且僅當(dāng)有上界。當(dāng)且僅當(dāng) 時(shí)等號成立，即時(shí)等號成立，即等概率場熵最大，等概率場熵最大，識別最困難。識別最困難。12(,)logcH ppcH p( )1(1,2, )ipicC(3) (3) 是是 的連續(xù)上凸函數(shù)。的連續(xù)上凸函數(shù)。H p( )p基于后驗(yàn)概率的可分性判據(jù)(4)(4)2122112132121,)(),(

39、),(ppppppHppppppHpppHcc其中021 pp說明說明當(dāng)類別較少時(shí)，分類識別的不確定性變小當(dāng)類別較少時(shí)，分類識別的不確定性變小。 從特征選擇角度看，我們從特征選擇角度看，我們應(yīng)選擇使熵最小的那些特征用于應(yīng)選擇使熵最小的那些特征用于分類分類即選用具有最小不確定性的特征進(jìn)行分類是有益的。即選用具有最小不確定性的特征進(jìn)行分類是有益的。 12123(,)(,)ccH p ppH pppp使熵最小的特征利于分類，取熵的期望：使熵最小的特征利于分類，取熵的期望：min)|(log)|(1xPxPEJiciixH廣義熵廣義熵（具有熵的性質(zhì)，利于計(jì)算）定義為定義為:()11121(,)(21)

40、 (1)cciiHp ppp式中0， 1。不同的值可得不同的可分性度量。ciiipppH1)1(log)(當(dāng)當(dāng)1時(shí)，由洛必達(dá)法則可得時(shí)，由洛必達(dá)法則可得Shannon熵熵ciippH12)2(1 2)(當(dāng)當(dāng) =2時(shí)，可得平方熵時(shí)，可得平方熵使用使用 或或 判據(jù)進(jìn)行特征提取與選擇時(shí)，目標(biāo)是使判據(jù)進(jìn)行特征提取與選擇時(shí)，目標(biāo)是使HJ()minHHJJ或同理，我們亦可用點(diǎn)熵在整個(gè)特征空間的概率平均同理，我們亦可用點(diǎn)熵在整個(gè)特征空間的概率平均()12(), (), ()HxcJEHpxpxpx作為可分性判據(jù)。作為可分性判據(jù)?；诤篁?yàn)概率的可分性判據(jù)()HJ三、基于類可分性度量的三、基于類可分性度量的特征

41、提取與選擇特征提取與選擇特征提取與選擇特征提取與選擇對某類模式：壓縮模式向量的維數(shù)。 對多類分類：壓縮維數(shù)；保留類別間的鑒別信息，突出可分性。 特征提取的目的：特征提取操作方法：m1 mn n1 (m n)注意：維數(shù)降低后，在新的m維空間里各模式類之間的分布 規(guī)律應(yīng)至少保持不變或更優(yōu)化?；陬惪煞中远攘康奶卣魈崛∨c選擇YW X12(,)mYy yy12( ,)nXx xx原始特征二次特征特征提取矩陣變換矩陣設(shè)和分別為原始特征空間中的類內(nèi)和類間離差矩陣， 和分別為變換特征空間中的類內(nèi)和類間離差矩陣，可知 基于類可分性度量的特征提取與選擇WSBS*WS*BS*TWWTBBSW S WSW S W(

42、 )( )( )( )T111()()iNciiiiWikkikiSPxmxmNciiiiBmmmmPS1T)()()( )( )( )( )T11( )( )( )( )T11( )( )( )T( )T111()()1()()1()()iiiNcTTiiiiWikkikiNcTiiiiikkikiNcTiTiiiikkikiW S WWPxmxmWNPWxmxmWNPW xW mxWmWN設(shè)和分別為原始特征空間中的類內(nèi)和類間離差矩陣， 和分別為變換特征空間中的類內(nèi)和類間離差矩陣，可知 基于類可分性度量的特征提取與選擇WSBS*WS*BS*TWWTBBSW S WSW S W( )( )(

43、)T( )T111()()iNcTTiTiiiWikkikiW S WPW xW mxWmWNTYW XTTYX WTYXmW m TTYXmmW ( )( )T( )( )T*111()() =iNciiTiiWiWkyyikiW S WPymymSN ( )( )( )( )T111()()iNciiiiWikkikiSPxmxmNciiiiBmmmmPS1T)()()(設(shè)和分別為原始特征空間中的類內(nèi)和類間離差矩陣， 和分別為變換特征空間中的類內(nèi)和類間離差矩陣，可知 根據(jù) J1=TrSW-1SBmax或 J4=|SW+SB|/|SB|=|ST|/|SB| max求變換矩陣 W?；陬惪煞中?/p>

44、度量的特征提取與選擇WSBS*WS*BS*TWWTBBSW S WSW S W協(xié)方差加權(quán)和nn對稱陣mmnn對稱陣( )( )( )( )T111()()iNciiiiWikkikiSPxmxmNciiiiBmmmmPS1T)()()( 在變換域中J1為 由線性代數(shù)可知，對矩陣作相似變換其跡不變，一個(gè)方陣的跡等于它的所有特征值之和。設(shè) 為正交陣，用 對對稱陣 作相似變換使其成為對角陣 12111120(,)0eWBeeWBennWSS WW SS Wdiag niieBWeBWWSSWTrSSTrJ1111矩陣跡形式的判據(jù)11*1TTWBWBJWTrSSTrW S WW S WeWeW1WBS

45、 S其中，i (i=1,2,n)為 的特征值， 的列矢量 為相應(yīng)于i的特征矢量。由上式可得。eW1WBS SiW1WBS SJTr SSWB111eeWW作變換 ，這時(shí)對于給定的d所得到的 達(dá)最大值。此方法對J3 =TrSB/TrSW也適用。 轉(zhuǎn)換步驟：轉(zhuǎn)換步驟：使使We的列矢量的排列已作適當(dāng)調(diào)整，使的列矢量的排列已作適當(dāng)調(diào)整，使S SW W-1-1S SB B的的特征值特征值 1 1 2 2 n n 。由此可得，在。由此可得，在d d 給定后，取給定后，取前前d d 個(gè)較大的特征值所對應(yīng)的特征矢量個(gè)較大的特征值所對應(yīng)的特征矢量wi( (i=1,2,=1,2,d,d) )構(gòu)造構(gòu)造特征提取矩陣特

46、征提取矩陣W，即:)(21dwwwWxWydiiWJ1*1)(矩陣跡形式的判據(jù)1 2 dn nd陣以J4為例，由于SW是對稱正定矩陣，設(shè)有非奇異陣A，使IASAW1AVSAVTIIVVAVSAVW11設(shè)有標(biāo)準(zhǔn)正交矩陣V，使這里 為對角陣，從而行列式形式的判據(jù)120=0TnUS U令U=AV ，因此存在非奇異矩陣U ，使 IUSUW4TWSJS上面右式兩邊同時(shí)取逆，有IUSUw111) (這里U及 分別是特征矢量組成的矩陣(特征矢量矩陣)及特征值對角陣。 120=0TnUS UIUSUWSS UUWT1再與左式相乘，并左乘U ，有: 行列式形式的判據(jù)因?yàn)镾SSSSISSWTWWBWB111()

47、diagn(,)12設(shè)SW-1SB 的特征值矩陣11()()WBWBISSUUSS UUI 所以I 則行列式形式的判據(jù)SS UUWT111112101()=01WBnU SS UU UII eUW因?yàn)镾SSSSISSWTWWBWB111() diagn(,)12設(shè)SW-1SB 的特征值矩陣11()()WBWBISSUUSS UUI 所以I 則于是WTSSJ 4USSUTW11TWSS1TWSS1)1 (1iniini1行列式形式的判據(jù)SS UUWT1此處的U 就是前述的We。轉(zhuǎn)換步驟：轉(zhuǎn)換步驟：設(shè)設(shè)U 的各列已作適當(dāng)調(diào)整，的各列已作適當(dāng)調(diào)整，使使S SW W-1-1S SB B 的特征值的特征

48、值 1 2 n ，對于給定的，對于給定的d，取前，取前d個(gè)較大的特征值對應(yīng)的個(gè)較大的特征值對應(yīng)的特征矢量構(gòu)造變換矩陣可使特征矢量構(gòu)造變換矩陣可使J4 取最大值，此時(shí)取最大值，此時(shí)*41()(1)diiJW )1 (1111114iniiniTWTWTWWTUSSUSSSSSSJ行列式形式的判據(jù)四、離散四、離散K-LK-L變換及其變換及其在特征提取與選擇中的應(yīng)用在特征提取與選擇中的應(yīng)用特征提取與選擇特征提取與選擇特征提取與K-L變換u特征提取特征提?。河糜成洌ɑ蜃儞Q）的方法把原始特征變換為較少的新特征uPCA (Principle Component Analysis)方法方法：進(jìn)行特征降維變換

49、，不能完全地表示原有的對象，能量總會有損失。希望找到一種能量最為集中的變換方法,使損失最小。uK-L (Karhunen-Loeve)變換變換：最優(yōu)正交線性變換，相應(yīng)的特征提取方法被稱為PCA方法離散K-L變換（DKLT）DKLT的性質(zhì)： 使變換后產(chǎn)生的新的分量正交或不相關(guān); 以部分新分量表示原矢量均方誤差最小;1. 使變換矢量更趨確定、能量更趨集中。有限離散K-L變換（DKLT）,又稱霍特林(Hotelling)變換或主分量分解,它是一種基于目標(biāo)統(tǒng)計(jì)特性的最佳正交變換。 變換是一種工具，它的用途歸根結(jié)底是用來描述事物，特別是描述信號用的。例如我們看到一個(gè)復(fù)雜的時(shí)序信號，希望能夠?qū)λM(jìn)行描述。

50、描述事物的基本方法之一是將復(fù)雜的事物化成簡單事物的組合, 或?qū)ζ溥M(jìn)行分解，分析其組成的成分。 例如對一波形，我們希望知道它是快速變化的(高頻)，還是緩慢變化的(低頻)，或是一成不變的(常量)。如果它既有快速變化的成分，又有緩慢變化的成分，又有常量部分，那么我們往往希望將它的成分分析出來。這時(shí)我們就要用到上式中要求titi=1，是考慮到ti是作為度量事物的單位應(yīng)用的，它本身的模應(yīng)該為1，ti又稱為。而被分解后的任何事物(在此指信號)可等成各種成分之和。故任一信號X可表示成： 其中yi是基ti的相應(yīng)成分。 綜合以上分析，我們可以將對這種變換的定義總結(jié)為：如果將這種變換中的每一成分，用一個(gè)向量ti表

51、示，i是其下標(biāo)，原理上可以到，則我們要求的正交變換可表示成：10i jijt tij1i iiXy tn基于Karhunen-Loeve變換的特征提取方法是以在特征空間分布的樣本特征向量為原始數(shù)據(jù)，通過實(shí)行K-L變換，找到維數(shù)較少的組合特征，達(dá)到降維的目的樣本都是離散的向量的情況下，只需討論K-L變換的離散情況。離散K-L變換（DKLT）nK-L變換：對給定一個(gè)n維訓(xùn)練樣本集（原始特征空間），進(jìn)行特征空間的降維，降到m維，m2 2c c, ,選取前選取前d d個(gè)較大的特征個(gè)較大的特征值對應(yīng)的特征矢量構(gòu)成變換矩陣，可實(shí)現(xiàn)特征的選取。值對應(yīng)的特征矢量構(gòu)成變換矩陣，可實(shí)現(xiàn)特征的選取。BSBSBSSB

52、iui) 1, 2 , 1(ci121cdui12( ,.,)dUu uu 排序：，取前個(gè)構(gòu)成變換矩陣，有yU x3 基于總的類內(nèi)離差矩陣 的DKLT進(jìn)行特征提取選擇WST(1,2, )WiiiiWiSuinu S u構(gòu)造準(zhǔn)則函數(shù)J yu S uu S uu S uiiBiiWiiBii() TTT 適用于各類模式的類域在某些分量軸上的投影不重迭或較少重迭的情況。離散K-L變換在特征提取與選擇中的應(yīng)用排序：J yJ yJ yn()()()12，取前面d個(gè)較大的J( ) 值對應(yīng)的ui(, , )id 1 2 組成變換矩陣 ，有WTYW XJTr STr SBW34. 依據(jù) 、 作DKLT以降低特

53、征維數(shù)的最優(yōu)壓縮方法WSBS離散K-L變換在特征提取與選擇中的應(yīng)用設(shè)和U是對稱正定陣WS的特征值對角陣和特征矢量矩陣，作如下的白化變換 I2121TUSUW易知，存在正交陣V可使 2121TTVUSUVB式中是白化變換后的總的類間離差陣的特征值對角陣。2121TUSUSBBTBBSB S B由于BS的秩不大于1c，所以SB最多只有1c個(gè)非零特征值，設(shè)非零特征值共有d個(gè)，用這d個(gè)非零特征值所對應(yīng)的特征矢量), 2, 1(djvj作變換矩陣，所得的d個(gè)分量含有原來n維模式的全部信息。12YW XVU X)(21dvvvV離散K-L變換在特征提取與選擇中的應(yīng)用不損失信息而又達(dá)到最小維數(shù)的變換矩陣為：

54、12WVUSW特征值對角陣SW特征矢量陣SB特征矢量陣?yán)齼深悩颖镜木凳噶糠謩e為m1=(4,2)和m2=(-4,-2),協(xié)方差矩陣分別為：31131C42242C兩類的先驗(yàn)概率相等，試求一維特征提取矩陣。解解總的類內(nèi)離差陣可以算得：5 . 35 . 15 . 15 . 3221121CCSw1icWiiSPS(1)依據(jù)SW進(jìn)行DKLT，得到特征值2, 521對應(yīng)的特征向量分別為：)707. 0,707. 0(, )707. 0 ,707. 0(21因?yàn)榭偟木凳噶繛椋?0 , 0(221121mmm故類間離差陣SB為：4881622211121mmmmSB計(jì)算J(y1)與J(y2)：1)(,

55、 7 . 3)(22221111BBSyJSyJ因?yàn)镴(y1)J(y2),所以選最佳變換矩陣為)707. 0 ,707. 0(1WciiiiBmmmmPS1T)()()(2)依據(jù)SW和SB作DKLT進(jìn)行最優(yōu)特征提取。此時(shí)447. 02/11707. 02/125 . 0316. 05 . 0316. 0707. 000447. 0707. 0707. 0707. 0707. 02/1UB對SB進(jìn)行白化變換：1896. 1896. 16 . 3BSBSBB的非零特征值只有一個(gè)， 6 . 41BS對應(yīng)的特征矢量為)466. 0 ,884. 0(1)046. 0 ,512. 0(1BW總的最優(yōu)變換為

56、：12WVU5. 基于總體離差陣 的DKLT選擇特征 適用于各類模式類間距離較大的情況。ST在未知屬別信息時(shí)，即沒有訓(xùn)練樣本，從而無法得到 和 ，此時(shí)，可依據(jù)總體離差陣 作DKLT，設(shè)對應(yīng)該總體離差陣的特征值依下面次序排列：SWSBST12 n對于給定的 ，選擇前面較大的本征值對應(yīng)的本征矢量作變換矩陣以實(shí)現(xiàn)特征選擇、降低特征空間維數(shù)的目的。d離散K-L變換在特征提取與選擇中的應(yīng)用T11()()NTlllSxm xmN五、特征選擇中的直接挑選法五、特征選擇中的直接挑選法特征提取與選擇特征提取與選擇 特征的提取與選擇除了我們前面學(xué)習(xí)的變換法外, 也可以在原坐標(biāo)系中依據(jù)某些原則直接選擇特征, 即直接

57、挑選法。n次優(yōu)搜索法n最優(yōu)搜索法特征提取與選擇特征提取與選擇次優(yōu)搜索法( (一一) )單獨(dú)最優(yōu)的特征選擇單獨(dú)最優(yōu)的特征選擇 單獨(dú)選優(yōu)法的基本思路是：計(jì)算各特征單獨(dú)使用時(shí)的判據(jù)值并以遞減排序，選取前d個(gè)分類效果最好的特征。 這種方法才能選出一組最優(yōu)特征。一般地講，即使各特征是統(tǒng)計(jì)獨(dú)立的，這種方法選出的d個(gè)特征也不一定是最優(yōu)的特征組合，只有可分性判據(jù)J是可分的時(shí)候，即10( )( ) ( )( )nniiiiJ xJ xJ xJ x或 ( (二二) )增添特征法增添特征法次優(yōu)搜索法( (二二) )增添特征法增添特征法設(shè)已選入了k個(gè)特征，它們記為Xk，把未選入的n-k個(gè)特征xj（j=1,2,n-k)

58、逐個(gè)與已選入的特征Xk組合計(jì)算J 值，若：則x1選入，下一步的特征組合為Xk+1=Xk+x1。開始時(shí)，k=0，X0=F， 該過程一直進(jìn)行到k=d為止。)()()(21knkkkxXJxXJxXJ次優(yōu)搜索法( (二二) )增添特征法增添特征法該方法比該方法比“單獨(dú)最優(yōu)的特征選擇法單獨(dú)最優(yōu)的特征選擇法”要好，但要好，但其缺點(diǎn)也是明顯的：即某特征一旦選入，即使后邊其缺點(diǎn)也是明顯的：即某特征一旦選入，即使后邊的的n-k特征中的某個(gè)從組合講比它好，也無法把它特征中的某個(gè)從組合講比它好，也無法把它剔除。剔除。次優(yōu)搜索法( (三三) )剔減特征法剔減特征法該方法也稱為順序后退法(SBS)。這是一種自上而下的

59、搜索方法，從全部特征開始每次剔除一個(gè)特征，所剔除的特征應(yīng)使尚保留的特征組合的J值最大。次優(yōu)搜索法( (三三) )剔減特征法剔減特征法)()()(21knkkkxXJxXJxXJ設(shè)已剔除了k個(gè)特征，剩下的特征組記為 ，將 中的各特征xj（j=1,2,n-k)分別逐個(gè)剔除，并同時(shí)計(jì)算 值，若：kXkX)(jkxXJ則在這輪中x1應(yīng)該剔除。這里初值 ，過程直到k=n-d為止。11xXXkk, 0210nxxxXk次優(yōu)搜索法(四四) 增增l 減減r 法（法（l-r 法）法） 為了克服前面方法（二） 、（三）中的一旦某特征選入或剔除就不能再剔除或選入的缺點(diǎn)，可在選擇過程中加入局部回溯，例如在第k步可先用

60、方法（二） ，對已選入的k個(gè)特征再一個(gè)個(gè)地加入新的特征到k+l個(gè)特征，然后用方法（三）一個(gè)個(gè)地剔除r個(gè)特征，稱這種方法為增l減r 法（ l-r法）次優(yōu)搜索法次優(yōu)搜索法最優(yōu)搜索法最優(yōu)搜索法分支定界法分支定界法(BAB(BAB算法算法) ) 尋求全局最優(yōu)的特征選擇的搜索過程可用一個(gè)尋求全局最優(yōu)的特征選擇的搜索過程可用一個(gè)樹結(jié)構(gòu)來描述，稱其為搜索樹或解樹。樹結(jié)構(gòu)來描述，稱其為搜索樹或解樹?？偟乃阉鞣桨甘茄刂鴺淇偟乃阉鞣桨甘茄刂鴺渥陨隙伦陨隙?、從右至左從右至左進(jìn)進(jìn)行，由于樹的每個(gè)節(jié)點(diǎn)代表一種特征組合，于是所行，由于樹的每個(gè)節(jié)點(diǎn)代表一種特征組合，于是所有可能的組合都可以被考慮。有可能的組合都可以被考