1、1模式識(shí)別主講：主講： 蔡宣平蔡宣平 教授教授 電話：電話： 7344173441（O O）,73442,73442（H H）E-mailE-mail：?jiǎn)挝粏挝? : 電子科學(xué)與工程學(xué)院信息工程系電子科學(xué)與工程學(xué)院信息工程系2第七章第七章 特征提取與選擇特征提取與選擇n 類別可分性判據(jù)類別可分性判據(jù)n 離散離散K-LK-L變換及其在特征提取變換及其在特征提取 與選擇中的應(yīng)用與選擇中的應(yīng)用n 特征選擇中的直接挑選法特征選擇中的直接挑選法3第七章第七章 特征提取與選擇特征提取與選擇 7.1 7.1 概概 述述4 模式識(shí)別的三大核心問(wèn)題模式識(shí)別的三大核心問(wèn)題: :第七章第七章 特征提取與選擇特征提取

2、與選擇7.1概述概述特征數(shù)據(jù)采集特征數(shù)據(jù)采集分類識(shí)別分類識(shí)別特征提取與選擇特征提取與選擇 分類識(shí)別的正確率取決于對(duì)象的表示、訓(xùn)練學(xué)分類識(shí)別的正確率取決于對(duì)象的表示、訓(xùn)練學(xué)習(xí)和分類識(shí)別算法，我們?cè)谇懊娓髡碌慕榻B中詳細(xì)習(xí)和分類識(shí)別算法，我們?cè)谇懊娓髡碌慕榻B中詳細(xì)討論了后兩方面的內(nèi)容。本章介紹的特征提取與選討論了后兩方面的內(nèi)容。本章介紹的特征提取與選擇問(wèn)題則是對(duì)象表示的一個(gè)關(guān)鍵問(wèn)題。擇問(wèn)題則是對(duì)象表示的一個(gè)關(guān)鍵問(wèn)題。5 通常在得到實(shí)際對(duì)象的若干具體特征之通常在得到實(shí)際對(duì)象的若干具體特征之后，再由這些原始特征產(chǎn)生出對(duì)分類識(shí)別最后，再由這些原始特征產(chǎn)生出對(duì)分類識(shí)別最有效、數(shù)目最少的特征，這就是特征提取與

3、有效、數(shù)目最少的特征，這就是特征提取與選擇的任務(wù)。從本質(zhì)上講，我們的目的是使選擇的任務(wù)。從本質(zhì)上講，我們的目的是使在最小維數(shù)特征空間中異類模式點(diǎn)相距較遠(yuǎn)在最小維數(shù)特征空間中異類模式點(diǎn)相距較遠(yuǎn)（類間距離較大），而同類模式點(diǎn)相距較近（類間距離較大），而同類模式點(diǎn)相距較近（類內(nèi)距離較小）。（類內(nèi)距離較?。?。 第七章第七章 特征提取與選擇特征提取與選擇7.1概述概述67.1概述概述特征提取與選擇的兩個(gè)基本途特征提取與選擇的兩個(gè)基本途徑徑主要方法有：主要方法有：分支定界法分支定界法、用回歸建模技術(shù)確定相用回歸建模技術(shù)確定相關(guān)特征關(guān)特征等方法。等方法。（1 1）直接選擇法：）直接選擇法：當(dāng)實(shí)際用于分類識(shí)別

4、的特征數(shù)目當(dāng)實(shí)際用于分類識(shí)別的特征數(shù)目d d 確定后，直接從已獲得的確定后，直接從已獲得的n n 個(gè)原始特征中選出個(gè)原始特征中選出d d 個(gè)特征個(gè)特征 ，使可分性判據(jù)，使可分性判據(jù)J J 的值滿足下的值滿足下式：式：dxxx,21J x xxJ xxxdiiid1212,max,式中式中 是是n 個(gè)原始特征中的任意個(gè)原始特征中的任意d 個(gè)特征，個(gè)特征，上式表示直接尋找上式表示直接尋找n 維特征空間中的維特征空間中的d 維子空間。維子空間。idiixxx,217（2 2）變換法）變換法，在使判據(jù)，在使判據(jù)J J 取最大的目標(biāo)下，對(duì)取最大的目標(biāo)下，對(duì)n n 個(gè)原始特征進(jìn)行變換降維，即對(duì)原個(gè)原始特征

5、進(jìn)行變換降維，即對(duì)原n n 維特征空間維特征空間進(jìn)行坐標(biāo)變換，然后再取子空間。進(jìn)行坐標(biāo)變換，然后再取子空間。7.1概述概述特征提取與選擇的兩個(gè)基本途特征提取與選擇的兩個(gè)基本途徑徑主要方法有：主要方法有：基于可分性判據(jù)的特征選擇基于可分性判據(jù)的特征選擇、基于基于誤判概率的特征選擇誤判概率的特征選擇、離散離散K-LK-L變換法變換法(DKLT)(DKLT)、基于決策界的特征選擇基于決策界的特征選擇等方法。等方法。87.2 7.2 類別可分性判據(jù)類別可分性判據(jù)第七章第七章 特征提取與選擇特征提取與選擇97.2 類別可分性判據(jù)類別可分性判據(jù) 為確立特征提取和選擇的準(zhǔn)則：引入類別可分性為確立特征提取和選

6、擇的準(zhǔn)則：引入類別可分性判據(jù)，來(lái)刻劃特征對(duì)分類的貢獻(xiàn)。為此希望所構(gòu)造判據(jù)，來(lái)刻劃特征對(duì)分類的貢獻(xiàn)。為此希望所構(gòu)造的可分性判據(jù)滿足下列要求：的可分性判據(jù)滿足下列要求：構(gòu)造可分性判據(jù)構(gòu)造可分性判據(jù)(1) (1) 與誤判概率與誤判概率( (或誤分概率的上界、下界或誤分概率的上界、下界) )有單調(diào)關(guān)系。有單調(diào)關(guān)系。 (2) (2) 當(dāng)特征相互獨(dú)立時(shí)，判據(jù)有可加性，即當(dāng)特征相互獨(dú)立時(shí)，判據(jù)有可加性，即 ： Jx xxJxi jdi jkdk(,)()121式中，式中，x xxd12,是對(duì)不同種類特征的測(cè)量值，是對(duì)不同種類特征的測(cè)量值，Ji j( ) 表示使用括號(hào)中特征時(shí)第表示使用括號(hào)中特征時(shí)第i 類與第

7、類與第j類可分性判據(jù)函數(shù)。類可分性判據(jù)函數(shù)。107.2 類別可分性判據(jù)類別可分性判據(jù)構(gòu)造可分性判據(jù)構(gòu)造可分性判據(jù)(3) (3) 判據(jù)具有判據(jù)具有“距離距離”的某些特性，即的某些特性，即 ：Ji j 0，當(dāng)，當(dāng)ij時(shí)；時(shí)；Ji j 0，當(dāng)，當(dāng)ij時(shí)；時(shí)；JJi jji(4) (4) 對(duì)特征數(shù)目是單調(diào)不減，即加入新的特征后，對(duì)特征數(shù)目是單調(diào)不減，即加入新的特征后，判據(jù)值不減。判據(jù)值不減。 Jx xxJx xxxi jdi jdd(,)(,)12121117.2 類別可分性判據(jù)類別可分性判據(jù)構(gòu)造可分性判據(jù)構(gòu)造可分性判據(jù)值得注意的是值得注意的是：上述的構(gòu)造可分性判據(jù)的要求，即：上述的構(gòu)造可分性判據(jù)的要

8、求，即“單調(diào)性單調(diào)性”、“疊加性疊加性”、“距離性距離性”、“單調(diào)不單調(diào)不減性減性”。在實(shí)際應(yīng)用并不一定能同時(shí)具備，但并不。在實(shí)際應(yīng)用并不一定能同時(shí)具備，但并不影響它在實(shí)際使用中的價(jià)值。影響它在實(shí)際使用中的價(jià)值。 127.2 類別可分性判據(jù)類別可分性判據(jù).1基于幾何距離的可分性判據(jù)基于幾何距離的可分性判據(jù)一般來(lái)講，不同類的模式可以被區(qū)分是由于它們一般來(lái)講，不同類的模式可以被區(qū)分是由于它們所屬類別在特征空間中的類域是不同的區(qū)域。所屬類別在特征空間中的類域是不同的區(qū)域。顯然，區(qū)域重疊的部分越小或完全沒有重疊，類顯然，區(qū)域重疊的部分越小或完全沒有重疊，類別的可分性就越好。別的可分性就

9、越好。因此可以用距離或離差測(cè)度（散度）來(lái)構(gòu)造類別因此可以用距離或離差測(cè)度（散度）來(lái)構(gòu)造類別的可分性判據(jù)。的可分性判據(jù)。 13( (一一) ) 點(diǎn)與點(diǎn)的距離點(diǎn)與點(diǎn)的距離 d a babababkkkn( , )() ()()/T1 2211 2( (二二) ) 點(diǎn)到點(diǎn)集的距離點(diǎn)到點(diǎn)集的距離),(1) ,()(12)(2ikNkiikaxdNaxdi用用均方歐氏距離均方歐氏距離表示表示.1基于幾何距離的可分性判據(jù)基于幾何距離的可分性判據(jù)14( (三三) ) 類內(nèi)及總體的均值矢量類內(nèi)及總體的均值矢量 ciiimPm1)(各類模式的總體均值矢量各類模式的總體均值矢量 iNkikiixN

10、m1)()(1類的均值矢量：類的均值矢量： ci, 2 , 1 Pi為相應(yīng)類的先驗(yàn)概率，為相應(yīng)類的先驗(yàn)概率，當(dāng)用統(tǒng)計(jì)量代替先驗(yàn)概當(dāng)用統(tǒng)計(jì)量代替先驗(yàn)概率時(shí)，總體均值矢量可表示為：率時(shí)，總體均值矢量可表示為：NllciNkikiciiiciixNxNmNNmPmi111)()(1)(1.1基于幾何距離的可分性判據(jù)基于幾何距離的可分性判據(jù)15( (四四) ) 類內(nèi)距離類內(nèi)距離 )()(1)()()(T)()(12iikiikNkiimxmxNdi類內(nèi)均方歐氏距離類內(nèi)均方歐氏距離 類內(nèi)均方距離也可定義為：類內(nèi)均方距離也可定義為： iiNkNlilikiiicxxdNNd11)()(

11、22),() 1(1)(.1基于幾何距離的可分性判據(jù)基于幾何距離的可分性判據(jù)16( (五五) ) 類內(nèi)離差矩陣類內(nèi)離差矩陣 T)()()()(1)(1iikiikNkimxmxNSii)(2iSTrdi顯然顯然( (六六) ) 兩類之間的距離兩類之間的距離 ),(1),()(11)(22jlNkNlikjijixxdNNdij)()(1),()()(T)(11)(2jlikjlNkNlikjijixxxxNNdij.1基于幾何距離的可分性判據(jù)基于幾何距離的可分性判據(jù)17( (七七) )各類模式之間的總的均方距各類模式之間的總的均方距離離 ijNkNljlikji

12、cjjciixxdNNPPxd11)()(2112),(121)(當(dāng)取歐氏距離時(shí)，總的均方距離為當(dāng)取歐氏距離時(shí)，總的均方距離為)()(121)()()(11T)()(112jlikNkNljlikjicjjciixxxxNNPPxdij.1基于幾何距離的可分性判據(jù)基于幾何距離的可分性判據(jù)18( (八八) ) 多類情況下總的類內(nèi)、類間及總體離差矩陣多類情況下總的類內(nèi)、類間及總體離差矩陣 iiNkiikiikiciiciiWmxmxNPSPS1T)()()()(11)(1類內(nèi)離差類內(nèi)離差ciiiiBmmmmPS1T)()()(類間離差類間離差總體離差總體離差 BWNlllTSSmx

13、mxNS1T)(1易導(dǎo)出易導(dǎo)出dxTr SSTr SWBT2( ).1基于幾何距離的可分性判據(jù)基于幾何距離的可分性判據(jù).1基于幾何距離的可分性判據(jù)基于幾何距離的可分性判據(jù)JTr SSWB11JSSBW2lnJTr STr SBW3JSSSSSWBWTW4.1基于幾何距離的可分性判據(jù)基于幾何距離的可分性判據(jù)在特征空間中，當(dāng)類內(nèi)模式較密聚，而不同類的在特征空間中，當(dāng)類內(nèi)模式較密聚，而不同類的模式相距較遠(yuǎn)時(shí)，從直覺上我們知道分類就較容模式相距較遠(yuǎn)時(shí)，從直覺上我們知道分類就較容易，由各判據(jù)的構(gòu)造可知，這種情況下所算得的易，由各判據(jù)的構(gòu)造可知，這種

14、情況下所算得的判據(jù)值也較大。由判據(jù)的構(gòu)造我們還可以初步了判據(jù)值也較大。由判據(jù)的構(gòu)造我們還可以初步了解運(yùn)用這類判據(jù)的原則和方法。解運(yùn)用這類判據(jù)的原則和方法。217.2 7.2 類別可分性判據(jù)類別可分性判據(jù).2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)考慮兩類問(wèn)題。上圖是一維的兩類概率分布密度。考慮兩類問(wèn)題。上圖是一維的兩類概率分布密度。 (a) (a) 表示兩類是完全可分的。表示兩類是完全可分的。(b)(b)是完全不可分的。是完全不可分的。 22可用兩類概密函數(shù)的重疊程度來(lái)度量可分性，可用兩類概密函數(shù)的重疊程度來(lái)度量可分性，構(gòu)造基于類概密的可分性判據(jù)。此處的

15、所謂重疊構(gòu)造基于類概密的可分性判據(jù)。此處的所謂重疊程度是指兩個(gè)概密函數(shù)相似的程度。程度是指兩個(gè)概密函數(shù)相似的程度。.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù).2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)( (一一) ) BhattacharyyaBhattacharyya 判據(jù)判據(jù)( (J JB B) )受相關(guān)概念與應(yīng)用的啟發(fā)，我們可以構(gòu)造受相關(guān)概念與應(yīng)用的啟發(fā)，我們可以構(gòu)造B- -判判據(jù)，它的計(jì)算式為據(jù)，它的計(jì)算式為 W W xdxpxpJB 2121)()(ln 式中式中W W表示特征空間。在最小誤判概率準(zhǔn)

16、則下，誤判表示特征空間。在最小誤判概率準(zhǔn)則下，誤判概率有概率有 BJPPeP exp)()()(21210 .2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù) P eP ePp xdxPp xdx0112212( )min( )min()()()() W WW W Pp xPp xdx1122min() (),() () W W Pp xPp xdx11221 2() () () ()/ W W PPp xp x121 212() ()() ()/ W W1 2/dx 121 2/() ()expPPJB 證明：設(shè)證明：設(shè)P e( )為誤分概率，則最小誤分

17、概率為：為誤分概率，則最小誤分概率為：2.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)（二）（二） Chernoff 判據(jù)判據(jù) ( (JC) )WxdxpxpJssC121)()(ln1s0 )(),;( 21sJxxxsJCnC);,(21sJC2.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)JC 具有如下性質(zhì)：具有如下性質(zhì)： (1)(1)對(duì)一切對(duì)一切01 s，0 CJ； (2)(2)對(duì)一切對(duì)一切01 s，Jp xp xC 012()() ； (3)(3)當(dāng)參數(shù)當(dāng)參數(shù)s和和 1 s互調(diào)時(shí)，有對(duì)稱性互調(diào)時(shí)，有對(duì)稱性

18、, ,)1 ;,();,(1221sJsJCC (4)(4)當(dāng)當(dāng) x的各分量的各分量nxxx,21相互獨(dú)立時(shí)，相互獨(dú)立時(shí)， nllCnCxsJxxxsJ121);(),;(2.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)(5)(5)當(dāng)當(dāng) x的各分量的各分量nxxx,21相互獨(dú)立時(shí)，有相互獨(dú)立時(shí)，有 )( ),;(),;(121121nkxxxxsJxxxsJkkCkC (6)(6)最小誤判概率最小誤判概率 ) 10( );,(exp)()()(211210 0) (a,b0)因?yàn)?，?dāng)因?yàn)椋?dāng) 0 0 s s 1 1 時(shí)時(shí) f (s) = -af (s)

19、= -as sb b1-s1-s(ln a - ln b)(ln a - ln b)2 2 0 0 (a(a b)b)且且 f(0)=f(1) = 0f(0)=f(1) = 0，從而有從而有 f(s)f(s) 0 0。由該不等式有：。由該不等式有：證畢。證畢。WxdxpxpsJssc12121)|()|(ln),(0)1ln()|()1 ()|(ln21Wssxdxpsxsp29Jc Jc 性質(zhì)（性質(zhì)（2 2）證明：）證明：只考慮連續(xù)的情況：只考慮連續(xù)的情況：因?yàn)橐驗(yàn)閒(0)=f(1) = 0f(0)=f(1) = 0 ，當(dāng)，當(dāng) 0 0 s s 1 1 時(shí)時(shí)f (s) = a-b-asb1-s

20、 (ln a - ln b)=0 a=b 從而有從而有 f(s)=0 f(s)=0 a=b a=b ，由此有：由此有：)|()|(21xpxpJC=0 30Jc Jc 性質(zhì)（性質(zhì)（5 5）證明：）證明：設(shè)設(shè)P(e)P(e)為最小誤分概率，則：為最小誤分概率，則：P eP ePp xdxPp xdxPp xPp xdx01122112221( )min( )min()()()()min() (),() ()WWW利用不等式利用不等式 ，由上式進(jìn)一步可得：由上式進(jìn)一步可得： min ,a ba bab10001P ePPp xp xdxPPJssssssC0121121121( )()()()()

21、()()expW3.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)由由JB和和JC的定義知：的定義知：JB=JC(1/2)對(duì)兩類都是正態(tài)分布情況對(duì)兩類都是正態(tài)分布情況: p xN mC() (,)( )111p xN mC() (,)( )222Jss mms CsCmms CsCCCCss1211121121211212112()() ()()ln()( )( )( )( )TJmmCCmmCCCCB182121212121121211 221 2()()ln()( )( )( )( )/T3.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的

22、概率密度函數(shù)的可分性判據(jù)Jss mms CsCmms CsCCCCss1211121121211212112()() ()()ln()( )( )( )( )TJmmCCmmCCCCB182121212121121211 221 2()()ln()( )( )( )( )/T當(dāng)CCC12時(shí)，)()(81)()(1 (21)2()1(1T)2()1()2()1(1T)2()1(mmCmmJmmCmmssJBC3.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)Jp xp xp xdxCs ln()()()122W實(shí)際上實(shí)際上 這就啟發(fā)我們運(yùn)用這就啟發(fā)我們運(yùn)用兩

23、個(gè)概密的比或差兩個(gè)概密的比或差來(lái)描述來(lái)描述兩個(gè)概密兩個(gè)概密重迭重迭或相似的程度。或相似的程度。 WxdxpxpJssC121)()(ln可以寫成：可以寫成： 34( (三三) )散度散度J JD D (Divergence) (Divergence) i i類對(duì)類對(duì) j j類的平均可分性信息為：類的平均可分性信息為： IxEp xp xp xp xp xdxi jiijiij( )ln()()()ln()()WIxEp xp xp xp xp xdxjijjijji( )ln()()()ln()()W.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù) j j

24、對(duì)對(duì) i i 類的平均可分性信息為：類的平均可分性信息為：35),(),()|()|(ln)|()|()()(1nDjiDjijii jj iDxxJJxdxpxpxpxpxIxIJW.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)對(duì)于對(duì)于 i i和和 j j兩類總的平均可分性信息稱為散度，其兩類總的平均可分性信息稱為散度，其定義為兩類平均可分性信息之和，即定義為兩類平均可分性信息之和，即 (三三)散度散度JD (Divergence)36),(),()|()|(ln)|()|()()(1nDjiDjijii jj iDxxJJxdxpxpxpxpxIxIJ

25、W.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)當(dāng)兩類都是正態(tài)分布時(shí)：當(dāng)兩類都是正態(tài)分布時(shí)： JTr CCCCImmCCmmDijjiijijij122121111() ()()( )( )( )( )T當(dāng)當(dāng)C Ci i=C=Cj j=C=C時(shí)時(shí)JmmCmmJDijijB()()( )( )( )( )T1837散度具有如下性質(zhì)：散度具有如下性質(zhì)： JxxxJxxxxknDkDkk(,),121121() .2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)(1) JD 0；(2) 對(duì)稱性對(duì)稱性: JD( 1 , 2)= J

26、D( 2 , 1); Jp xp xD012()()(3) Jx xxJxknDkDjjk(,)()121 (4) 當(dāng)當(dāng)x 各分量各分量x1,x2,xn相互獨(dú)立時(shí)，相互獨(dú)立時(shí)，(具有可加性具有可加性) (5) 當(dāng)當(dāng)x各分量各分量x1,x2,xn相互獨(dú)立時(shí)，相互獨(dú)立時(shí)，(對(duì)特征數(shù)目單對(duì)特征數(shù)目單調(diào)不減調(diào)不減)3.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)一般情況下，散度與誤分概率一般情況下，散度與誤分概率( (或其上下界或其上下界) )之間之間的直接解析關(guān)系很難得到，但實(shí)驗(yàn)可以證明它們之間的直接解析關(guān)系很難得到，但實(shí)驗(yàn)可以證明它們之間存在著單調(diào)關(guān)系。例如

27、兩類都是正態(tài)分布，且有相同存在著單調(diào)關(guān)系。例如兩類都是正態(tài)分布，且有相同的協(xié)方差陣時(shí)，的協(xié)方差陣時(shí)， 是是 的的單調(diào)減函數(shù)單調(diào)減函數(shù)。P e0( )JDJDP eydyJD0212122( )exp當(dāng)兩類先驗(yàn)概率相等且為具有相同協(xié)方差的正態(tài)當(dāng)兩類先驗(yàn)概率相等且為具有相同協(xié)方差的正態(tài)分布時(shí)，則最小誤分概率與分布時(shí)，則最小誤分概率與 的關(guān)系為：的關(guān)系為：39對(duì)于對(duì)于JC 判據(jù)的判據(jù)的最小誤分概率的上界最小誤分概率的上界 P ePPJssssC01211201( )()()exp(,; ) Ch, , 但但Bh比較容易計(jì)算，算得比較容易計(jì)算，算得結(jié)果通常也比較接近結(jié)果通常也比較接近Ch，所以在分類器

28、設(shè)計(jì)分析中，所以在分類器設(shè)計(jì)分析中Bh、JB也是常用的。也是常用的。42對(duì)于對(duì)于c類問(wèn)題，可采用平均類問(wèn)題，可采用平均B-判據(jù)、判據(jù)、C-判據(jù)、判據(jù)、D-判據(jù)：判據(jù)： cicijjiBjiBJPPJ11),()()( cicijjiCjiCJPPJ11),()()( cicijjiDjiDJPPJ11),()()(由由JB、JC、JD的定義式結(jié)構(gòu)以及它們與誤分概率的的定義式結(jié)構(gòu)以及它們與誤分概率的關(guān)系可以知道，所選取的特征矢量應(yīng)使所對(duì)應(yīng)的關(guān)系可以知道，所選取的特征矢量應(yīng)使所對(duì)應(yīng)的JB、JC 、JD盡量大，這樣可分性就較好。盡量大，這樣可分性就較好。.2基于類的概率密度函數(shù)的可分

29、性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)43大蓋小問(wèn)題大蓋小問(wèn)題 在特征空間中，若有某兩類間的在特征空間中，若有某兩類間的JB、JC或或JD很大，很大，可使平均判據(jù)變大，這樣就掩蓋了某些類對(duì)的判據(jù)值可使平均判據(jù)變大，這樣就掩蓋了某些類對(duì)的判據(jù)值較小的情況存在，從而可能降低總的分類正確率，即較小的情況存在，從而可能降低總的分類正確率，即所謂的所謂的大蓋小問(wèn)題大蓋小問(wèn)題。為改善這種情況，可對(duì)每個(gè)類對(duì)。為改善這種情況，可對(duì)每個(gè)類對(duì)的判據(jù)采用變換的方法，使對(duì)小的判據(jù)較敏感。例如，的判據(jù)采用變換的方法，使對(duì)小的判據(jù)較敏感。例如，對(duì)對(duì)JD ，可采用變換，可采用變換8),(exp1),(jiDjiDJJ448

30、),(exp1),(jiDjiDJJ這樣，當(dāng)這樣，當(dāng) i和和 j兩類模式相距很遠(yuǎn)時(shí)，兩類模式相距很遠(yuǎn)時(shí)， JD( i, j)變變得很大，但得很大，但 也只能接近于也只能接近于1。但對(duì)于散度。但對(duì)于散度JD( i, j) 小的情況，小的情況， 又變得較敏感。于是，又變得較敏感。于是，總的平均總的平均(變換變換)判據(jù)為判據(jù)為 ),(jiDJ),(jiDJ),()()(11jicicijDjiDJPPJ .2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)45同樣對(duì)于同樣對(duì)于JB，單類與平均判據(jù)分別為：，單類與平均判據(jù)分別為：21),(exp22),(jiBjiBJJ

31、單類：?jiǎn)晤悾?,()()(11jicicijBjiBJPPJ平均判據(jù)：平均判據(jù)：.2基于類的概率密度函數(shù)的可分性判據(jù)基于類的概率密度函數(shù)的可分性判據(jù)467.2.3 7.2.3 基于后驗(yàn)概率的可分性判據(jù)基于后驗(yàn)概率的可分性判據(jù)在信息論中，在信息論中，熵熵(Entropy)(Entropy)表示不確定性表示不確定性，熵越，熵越大不確定性越大?？梢越栌渺氐母拍顏?lái)描述各類的大不確定性越大?？梢越栌渺氐母拍顏?lái)描述各類的可分性?？煞中浴xi()對(duì)于對(duì)于c c類問(wèn)題，給定各類的后驗(yàn)概率類問(wèn)題，給定各類的后驗(yàn)概率 可以寫成如下形式：可以寫成如下形式：ccccpppxpxpxp21212121

32、 )()()(熵的定義：熵的定義：)(log)(log)()(11xpxppppHxHiciiicii由洛必達(dá)法則知：當(dāng)由洛必達(dá)法則知：當(dāng) 時(shí)時(shí)pi 00logiipp477.2.3 7.2.3 基于后驗(yàn)概率的可分性判據(jù)基于后驗(yàn)概率的可分性判據(jù)例如：例如：顯然這時(shí)能實(shí)現(xiàn)完全正確的分類識(shí)別顯然這時(shí)能實(shí)現(xiàn)完全正確的分類識(shí)別 pxi()1pxjij(), 0487.2.3 7.2.3 基于后驗(yàn)概率的可分性判據(jù)基于后驗(yàn)概率的可分性判據(jù)497.2.3 7.2.3 基于后驗(yàn)概率的可分性判據(jù)基于后驗(yàn)概率的可分性判據(jù)熵的主要性質(zhì)：熵的主要性質(zhì)：(4)(4)2122112132121,)(),(),(ppppp

33、pHppppppHpppHcc其中其中021 pp說(shuō)明當(dāng)類別較少時(shí)，分類識(shí)別的不確定性變小。說(shuō)明當(dāng)類別較少時(shí)，分類識(shí)別的不確定性變小。 從特征選擇角度看，我們從特征選擇角度看，我們應(yīng)選擇使熵最小的那些特應(yīng)選擇使熵最小的那些特征用于分類征用于分類即選用具有最小不確定性的特征進(jìn)行分即選用具有最小不確定性的特征進(jìn)行分類是有益的。類是有益的。 50使熵最小的特征利于分類，取熵的期望：使熵最小的特征利于分類，取熵的期望：min)|(log)|(1xPxPEJiciixH廣義熵廣義熵（具有熵的性質(zhì)，利于計(jì)算）定義定義為為:) 1() 12(),(11121)(ciicppppH式中0， 1。不同的值可得不

34、同的可分性度量。ciiipppH1)1(log)(當(dāng)當(dāng)1時(shí)，由洛必達(dá)法則可得時(shí)，由洛必達(dá)法則可得Shannon熵熵ciippH12)2(1 2)(當(dāng)當(dāng) =2時(shí)，可得平方熵時(shí)，可得平方熵51JH使用使用 判據(jù)進(jìn)行特征提取與選擇時(shí)，我們的目標(biāo)是使判據(jù)進(jìn)行特征提取與選擇時(shí)，我們的目標(biāo)是使JH min。 同理，我們亦可用點(diǎn)熵在整個(gè)特征空間的概率平均同理，我們亦可用點(diǎn)熵在整個(gè)特征空間的概率平均)(,),(),(21)(xpxpxpJEJcxH作為可分性判據(jù)。作為可分性判據(jù)。7.2.3 7.2.3 基于后驗(yàn)概率的可分性判據(jù)基于后驗(yàn)概率的可分性判據(jù)52第七章第七章 特征提取與選擇特征提取與選擇7.3 7.3

35、 基于可分性判據(jù)進(jìn)行變換的基于可分性判據(jù)進(jìn)行變換的 特征提取與選擇特征提取與選擇537.3 7.3 基于可分性判據(jù)進(jìn)行變換的特征提取與選擇基于可分性判據(jù)進(jìn)行變換的特征提取與選擇變換變換xWy為特征提取矩陣或變換矩陣為特征提取矩陣或變換矩陣WWn d),(21nxxxxndyyyyd, ),(21原始特征原始特征 二次特征二次特征547.3.1 7.3.1 基于離差陣判據(jù)的變換法基于離差陣判據(jù)的變換法 設(shè)設(shè)SW和和SB分別為原始特征空間中的類內(nèi)和類分別為原始特征空間中的類內(nèi)和類間離差矩陣，間離差矩陣，SW*和和SB*分別為變換特征空間中的類分別為變換特征空間中的類內(nèi)和類間離差矩陣，可知內(nèi)和類間離

36、差矩陣，可知 SW S WWW* T SW S WBB* T根據(jù)根據(jù) J1 1=TrS=TrSW W-1-1S SB Bmaxmax或或 J4 4=|S=|SW W+S+SB B|/|S|/|SB B|=|S|=|ST T|/|S|/|SB B| max| max求變換矩陣求變換矩陣 W W。55 在變換域中在變換域中J1為為 )()(Tr)(Tr)(T1T*1*1WSWWSWSSWJBWBW 由線性代數(shù)可知，對(duì)矩陣作相似變換其跡不變，由線性代數(shù)可知，對(duì)矩陣作相似變換其跡不變，一個(gè)方陣的跡等于它的所有特征值之和。設(shè)一個(gè)方陣的跡等于它的所有特征值之和。設(shè)We為正為正交陣，用交陣，用We對(duì)對(duì)稱陣對(duì)

37、對(duì)稱陣SSWB 1作相似變換使其成為對(duì)角陣作相似變換使其成為對(duì)角陣,其中其中, i ni, 2 , 1 為為SSWB 1的特征值，的特征值，We的列矢量的列矢量 Wi為為SSWB 1相應(yīng)于相應(yīng)于 i的特征矢量。由上式可得的特征矢量。由上式可得 ),(002121111nneBWeeBWediagWSSWWSSWniieBWeBWWSSWTrSSTrJ1111（一）對(duì)于矩陣跡形式的判據(jù)（一）對(duì)于矩陣跡形式的判據(jù)56假設(shè)假設(shè)We的列矢量的排列已作適當(dāng)調(diào)整，使的列矢量的排列已作適當(dāng)調(diào)整，使S SW W-1-1S SB B的的特征值特征值 1 1 2 2 n n 。由此可得，在。由此可得，在d d 給

38、給定后，取前定后，取前d d 個(gè)較大的特征值所對(duì)應(yīng)的特征矢量個(gè)較大的特征值所對(duì)應(yīng)的特征矢量wi( (i=1,2,=1,2,d d) )構(gòu)造特征提取矩陣構(gòu)造特征提取矩陣W，即，即: :)(21dwwwWxWydiiWJ1*1)(7.3.1 7.3.1 基于離差陣判據(jù)的變換法基于離差陣判據(jù)的變換法作變換作變換 ，這時(shí)對(duì)于給定的，這時(shí)對(duì)于給定的d d所得到的所得到的 達(dá)最大值。此方法對(duì)達(dá)最大值。此方法對(duì)J3 3 =TrS=TrSB B/TrS/TrSW W 也適用。也適用。 57（二）對(duì)于行列式形式的判據(jù)（二）對(duì)于行列式形式的判據(jù)以以J4為例，由于為例，由于SW是對(duì)稱正定矩陣，設(shè)有非奇異是對(duì)稱正定矩

39、陣，設(shè)有非奇異陣陣A，使，使IASAW1AVSAVTIIVVAVSAVW11但一般但一般AST A不是對(duì)角陣，設(shè)有標(biāo)準(zhǔn)正交矩陣不是對(duì)角陣，設(shè)有標(biāo)準(zhǔn)正交矩陣V，使，使這里這里 為對(duì)角陣，從而為對(duì)角陣，從而7.3.1 7.3.1 基于離差陣判據(jù)的變換法基于離差陣判據(jù)的變換法0021nTUSU令令U=AV ，因此存在非奇異矩陣因此存在非奇異矩陣U ，使，使 IUSUW58上面右式兩邊同時(shí)取逆，有上面右式兩邊同時(shí)取逆，有IUSUw111) (這里這里U及及 分別是特征矢量組成的矩陣分別是特征矢量組成的矩陣(特征矢量矩特征矢量矩陣陣)及特征值對(duì)角陣。及特征值對(duì)角陣。 7.3.1 7.3.1 基于離差陣判

40、據(jù)的變換法基于離差陣判據(jù)的變換法0021nTUSUIUSUWSS UUWT1再與左式相乘，并左乘再與左式相乘，并左乘U ，有，有: 59因?yàn)橐驗(yàn)镾SSSSISSWTWWBWB111() diagn(,)12設(shè)設(shè)SW-1SB 的特征值矩陣的特征值矩陣)()(11IUUSSUUSSIBWBW所以所以I 則則于是于是7.3.1 7.3.1 基于離差陣判據(jù)的變換法基于離差陣判據(jù)的變換法WTSSJ 4USSUTW11TWSS1TWSS1)1 (1iniini160此處的此處的U 就是前述的就是前述的We。設(shè)。設(shè)U 的各列已作適當(dāng)調(diào)的各列已作適當(dāng)調(diào)整，使整，使 1 2 n ，對(duì)于給定的，對(duì)于給定的d，取前

41、，取前d個(gè)較大的個(gè)較大的特征值對(duì)應(yīng)的特征矢量構(gòu)造變換矩陣可使特征值對(duì)應(yīng)的特征矢量構(gòu)造變換矩陣可使J4 取最大值，取最大值，此時(shí)此時(shí)J Widi411()()1 (1111114iniiniTWTWTWWTUSSUSSSSSSJ7.3.1 7.3.1 基于離差陣判據(jù)的變換法基于離差陣判據(jù)的變換法從從J4的構(gòu)造可知，用的構(gòu)造可知，用J4作判據(jù)作判據(jù) ，不至于選用那些，不至于選用那些只對(duì)兩類有很好的可分性而對(duì)其他各類分類效果不好只對(duì)兩類有很好的可分性而對(duì)其他各類分類效果不好的特征。而對(duì)于的特征。而對(duì)于J1 =TrSW-1SB，只要一個(gè)，只要一個(gè) i很大就會(huì)很大就會(huì)發(fā)生這種情況。發(fā)生這種情況。61例例

42、7.1 給定兩類模式，其先驗(yàn)概率給定兩類模式，其先驗(yàn)概率P( 1)= P( 2) ，均均值矢量分別為值矢量分別為 和和 ，離差陣分別，離差陣分別為為 求基于判據(jù)求基于判據(jù)J4的最優(yōu)特征提取。的最優(yōu)特征提取。 ) 1, 3 , 1 (1m ) 1 , 1, 1(2mC1410140001C2210120001mmm()( , , )1220 1 0TSCCW1231013000112()SW118310130008解：解： TiTiiBmmmmmmmmS)(41)(2121212162S S vvWB1為求該特征值應(yīng)解方程：為求該特征值應(yīng)解方程：這就是所要求的最優(yōu)特征提取矩陣。這就是所要求的最優(yōu)

43、特征提取矩陣。 即即TWmmmmS)(2121141由于由于 是標(biāo)量，于是有：是標(biāo)量，于是有：Tmm)(2141TWmmS)16,10, 2(81)(21163第七章第七章 特征提取與選擇特征提取與選擇7.5 7.5 離散離散K-LK-L變換及其在變換及其在 特征提取與選擇中的應(yīng)用特征提取與選擇中的應(yīng)用647.5.1 離散離散K-L變換（變換（DKLT）DKLT的性質(zhì)：的性質(zhì)： 使變換后產(chǎn)生的新的分量正交或不相關(guān)使變換后產(chǎn)生的新的分量正交或不相關(guān); 以部分新分量表示原矢量均方誤差最小以部分新分量表示原矢量均方誤差最小;1. 使變換矢量更趨確定、能量更趨集中。使變換矢量更趨確定、能量更趨集中。有

44、限離散有限離散K-LK-L變換（變換（DKLTDKLT）, ,又稱霍特林又稱霍特林(Hotelling)(Hotelling)變換或主分量分解變換或主分量分解, ,它是一種基于目標(biāo)它是一種基于目標(biāo)統(tǒng)計(jì)特性的最佳正交變換。統(tǒng)計(jì)特性的最佳正交變換。657.5.1 離散離散K-L變換（變換（DKLT）設(shè)設(shè)n維隨機(jī)矢量維隨機(jī)矢量 xx xxn ( ,)12T，其均，其均值矢量值矢量 xE x ，相關(guān)陣，相關(guān)陣 RE xxx T，協(xié)方，協(xié)方差陣差陣 CE xx xxx ()()T， x經(jīng)正交變換后經(jīng)正交變換后產(chǎn)生矢量產(chǎn)生矢量 yy yyn (,)12T，66設(shè)有標(biāo)準(zhǔn)正交變換矩陣設(shè)有標(biāo)準(zhǔn)正交變換矩陣T，（

45、即，（即 TT=I）),( )(2121nnyyyxtttxTyniiityyTyTx11) (xtyii),2 , 1(ni取前取前m項(xiàng)為項(xiàng)為 的估計(jì)值的估計(jì)值xxy tiiim1nm J(y2),所以選最佳變換矩陣為所以選最佳變換矩陣為)707. 0 ,707. 0(1W下面依據(jù)下面依據(jù)S SW W和和S SB B作作DKLTDKLT進(jìn)行最優(yōu)特征提取。進(jìn)行最優(yōu)特征提取。此時(shí)此時(shí)447. 02/11707. 02/125 . 0316. 05 . 0316. 0707. 000447. 0707. 0707. 0707. 0707. 02/1UB對(duì)對(duì)S SB B進(jìn)行白化變換：進(jìn)行白化變換：1

46、896. 1896. 16 . 3BSBSBB861896. 1896. 16 . 3BSBSBB的非零特征值只有一個(gè)，的非零特征值只有一個(gè)， 6 . 41BS對(duì)應(yīng)的特征矢量為對(duì)應(yīng)的特征矢量為)466. 0 ,884. 0(1)046. 0 ,512. 0(1BW總的最優(yōu)變換為：總的最優(yōu)變換為：作業(yè)：作業(yè)：7.1187第七章第七章 特征提取與選擇特征提取與選擇7.5 7.5 離散離散K-LK-L變換及其在變換及其在 特征提取與選擇中的應(yīng)用特征提取與選擇中的應(yīng)用88第七章第七章 特征提取與選擇特征提取與選擇7.7 7.7 特征選擇中的直接挑選法特征選擇中的直接挑選法特征的選擇除了我們前面學(xué)習(xí)的變

47、換法外特征的選擇除了我們前面學(xué)習(xí)的變換法外, , 也可以也可以在原坐標(biāo)系中依據(jù)某些原則直接選擇特征在原坐標(biāo)系中依據(jù)某些原則直接選擇特征, , 即我們即我們這節(jié)課要學(xué)的直接挑選法。這節(jié)課要學(xué)的直接挑選法。7.7.1 7.7.1 次優(yōu)搜索法次優(yōu)搜索法7.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法897.7.1 7.7.1 次優(yōu)搜索法次優(yōu)搜索法( (一一) )單獨(dú)最優(yōu)的特征選擇單獨(dú)最優(yōu)的特征選擇單獨(dú)選優(yōu)法的基本思路是：?jiǎn)为?dú)選優(yōu)法的基本思路是：計(jì)算各特征單獨(dú)使用時(shí)的判計(jì)算各特征單獨(dú)使用時(shí)的判據(jù)值并以遞減排序，選取前據(jù)值并以遞減排序，選取前d d個(gè)分類效果最好的特征。個(gè)分類效果最好的特征。 這種方法才能選

48、出一組最優(yōu)特征。這種方法才能選出一組最優(yōu)特征。一般地講，即使各特征是統(tǒng)計(jì)獨(dú)立的，這種方法選一般地講，即使各特征是統(tǒng)計(jì)獨(dú)立的，這種方法選出的出的d d個(gè)特征也不一定是最優(yōu)的特征組合，只有可分性個(gè)特征也不一定是最優(yōu)的特征組合，只有可分性判據(jù)判據(jù)J J是可分的時(shí)候，即是可分的時(shí)候，即10( )() ( )()nniiiiJ xJ xJ xJ x或 90( (二二) )增添特征法增添特征法該該方方法法也也稱稱為為順順序序前前進(jìn)進(jìn)法法( (SFS) )。這這是是最最簡(jiǎn)簡(jiǎn)單單的的自自下下而而上上搜搜索索方方法法， 每每次次從從未未選選入入的的特特征征中中選選擇擇一一個(gè)個(gè)特特征征， 使使它它與與已已選選入入

49、的的特特征征組組合合在在一一起起時(shí)時(shí)J值值最最大大，直直到到選選入入特特征征數(shù)數(shù)目目達(dá)達(dá)到到指指定定的的維維數(shù)數(shù)d為為止止。7.7.1 7.7.1 次優(yōu)搜索法次優(yōu)搜索法91( (二二) )增添特征法增添特征法7.7.1 7.7.1 次優(yōu)搜索法次優(yōu)搜索法設(shè)已選入了設(shè)已選入了k個(gè)特征，它們記為個(gè)特征，它們記為Xk，把未選入的，把未選入的n-k個(gè)特征個(gè)特征xj（j=1,2,n-k)逐個(gè)與已選入的特征逐個(gè)與已選入的特征Xk組合計(jì)算組合計(jì)算J 值，若：值，若：則則x1選入，下一步的特征組合為選入，下一步的特征組合為Xk+1=Xk+x1。開。開始時(shí)，始時(shí)，k=0，X0=F F， 該過(guò)程一直進(jìn)行到該過(guò)程一直

50、進(jìn)行到k=d為止。為止。)()()(21knkkkxXJxXJxXJ92( (二二) )增添特征法增添特征法7.7.1 7.7.1 次優(yōu)搜索法次優(yōu)搜索法該方法比該方法比“單獨(dú)最優(yōu)的特征選擇法單獨(dú)最優(yōu)的特征選擇法”要好，但要好，但其缺點(diǎn)也是明顯的：即某特征一旦選入，即使后邊其缺點(diǎn)也是明顯的：即某特征一旦選入，即使后邊的的n-k特征中的某個(gè)從組合講比它好，也無(wú)法把它特征中的某個(gè)從組合講比它好，也無(wú)法把它剔除。剔除。93( (三三) )剔減特征法剔減特征法7.7.1 7.7.1 次優(yōu)搜索法次優(yōu)搜索法該方法也稱為順序后退法該方法也稱為順序后退法(SBS)。這是一種。這是一種自上而下的搜索方法，從全部特

51、征開始每次剔除自上而下的搜索方法，從全部特征開始每次剔除一個(gè)特征，所剔除的特征應(yīng)使尚保留的特征組合一個(gè)特征，所剔除的特征應(yīng)使尚保留的特征組合的值最大的值最大。94( (三三) )剔減特征法剔減特征法7.7.1 7.7.1 次優(yōu)搜索法次優(yōu)搜索法)()()(21knkkkxXJxXJxXJ則在這輪中則在這輪中x1應(yīng)該剔除。應(yīng)該剔除。這里初值這里初值 ，過(guò)程直到，過(guò)程直到k=n-d為為止。止。11xXXkk, 0210nxxxXk957.7.1 7.7.1 次優(yōu)搜索法次優(yōu)搜索法(四四) 增增l 減減r 法（法（l-r 法）法）為了克服前面方法為了克服前面方法 ( (二二) )、( (三三) )中的一

52、旦某特征中的一旦某特征選入或剔除就不能再剔除或選入的缺點(diǎn)，可在選擇選入或剔除就不能再剔除或選入的缺點(diǎn)，可在選擇過(guò)程中加入局部回溯，例如在第過(guò)程中加入局部回溯，例如在第k步可先用方法步可先用方法( (二二) )，對(duì)已選入的，對(duì)已選入的k個(gè)特征再一個(gè)個(gè)地加入新的特征個(gè)特征再一個(gè)個(gè)地加入新的特征到到kl 個(gè)特征，然后用方法個(gè)特征，然后用方法( (三三) )一個(gè)個(gè)地剔除一個(gè)個(gè)地剔除r個(gè)特個(gè)特征，稱這種方法為增征，稱這種方法為增l減減r法法( (lr 法法) )。967.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法( (一一) )分支定界法分支定界法(BAB(BAB算法算法) ) 尋求全局最優(yōu)的特征選擇的搜

53、索過(guò)程可用一個(gè)尋求全局最優(yōu)的特征選擇的搜索過(guò)程可用一個(gè)樹結(jié)構(gòu)來(lái)描述，稱其為搜索樹或解樹。樹結(jié)構(gòu)來(lái)描述，稱其為搜索樹或解樹?？偟乃阉鞣桨甘茄刂鴺渥陨隙?、從右至左進(jìn)總的搜索方案是沿著樹自上而下、從右至左進(jìn)行，由于樹的每個(gè)節(jié)點(diǎn)代表一種特征組合，于是所行，由于樹的每個(gè)節(jié)點(diǎn)代表一種特征組合，于是所有可能的組合都可以被考慮。有可能的組合都可以被考慮。利用可分性判據(jù)的單調(diào)性采用利用可分性判據(jù)的單調(diào)性采用分支定界策略分支定界策略和和值值左小右大左小右大的樹結(jié)構(gòu)，使得在實(shí)際上并不計(jì)算某些的樹結(jié)構(gòu)，使得在實(shí)際上并不計(jì)算某些特征組合而又不影響全局尋優(yōu)。這種具有上述特點(diǎn)特征組合而又不影響全局尋優(yōu)。這種具有上述特點(diǎn)的

54、快速搜索方法，稱為的快速搜索方法，稱為分支定界算法分支定界算法。976 6選選2 2的特征選擇問(wèn)題的特征選擇問(wèn)題 (a)(a)搜索樹搜索樹 (b)(b)搜索回溯示意圖搜索回溯示意圖7.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法BAB算法算法1232344 43A34545 545 5 54 5 6 5 6 6 5 6 6 6 5 6 6 6 6nXX000i1i2i4i3i0X( ) a( ) bs=0s=1s=2s=3s=498樹的每個(gè)節(jié)點(diǎn)表示一種特征組合，樹的每樹的每個(gè)節(jié)點(diǎn)表示一種特征組合，樹的每一級(jí)一級(jí)各節(jié)點(diǎn)表示從其父節(jié)點(diǎn)的特征組合中再去掉一個(gè)特各節(jié)點(diǎn)表示從其父節(jié)點(diǎn)的特征組合中再去掉一個(gè)特

55、征后的特征組合，其標(biāo)號(hào)征后的特征組合，其標(biāo)號(hào)k表示去掉的特征是表示去掉的特征是xk 。7.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法BAB算法算法由于每一級(jí)只舍棄一個(gè)特征，因此整個(gè)搜索樹除由于每一級(jí)只舍棄一個(gè)特征，因此整個(gè)搜索樹除根節(jié)點(diǎn)的根節(jié)點(diǎn)的0 0級(jí)外，還需要級(jí)外，還需要n-d 級(jí)，即全樹有級(jí)，即全樹有n-d 級(jí)。在級(jí)。在6 6個(gè)特征中選個(gè)特征中選2 2個(gè)，故整個(gè)搜索樹需要個(gè)，故整個(gè)搜索樹需要4 4級(jí)，第級(jí)，第n-d 級(jí)級(jí)是葉節(jié)點(diǎn)，有個(gè)葉節(jié)點(diǎn)是葉節(jié)點(diǎn)，有個(gè)葉節(jié)點(diǎn) 。dnC99BAB算法算法7.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法表示特征數(shù)目為表示特征數(shù)目為l 的的特征集合。特征集合。lX

56、表示舍棄表示舍棄s 個(gè)特征后余下的特征集合。個(gè)特征后余下的特征集合。sX表示當(dāng)前節(jié)點(diǎn)的表示當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)。子節(jié)點(diǎn)數(shù)。sq表示表示集合中元素的數(shù)目。集合中元素的數(shù)目。sr表示第表示第s 級(jí)當(dāng)前節(jié)點(diǎn)上用來(lái)作為下一級(jí)可舍級(jí)當(dāng)前節(jié)點(diǎn)上用來(lái)作為下一級(jí)可舍棄特征的特征集合。棄特征的特征集合。s100由于從根節(jié)點(diǎn)要經(jīng)歷由于從根節(jié)點(diǎn)要經(jīng)歷n-dn-d級(jí)才能到達(dá)葉節(jié)點(diǎn)，級(jí)才能到達(dá)葉節(jié)點(diǎn)，s級(jí)某節(jié)點(diǎn)后繼的每一個(gè)子節(jié)點(diǎn)分別舍棄級(jí)某節(jié)點(diǎn)后繼的每一個(gè)子節(jié)點(diǎn)分別舍棄 中互不中互不相同的一個(gè)特征，從而考慮在相同的一個(gè)特征，從而考慮在s+1級(jí)可以舍棄的特級(jí)可以舍棄的特征方案數(shù)征方案數(shù)( (即其子節(jié)點(diǎn)數(shù)即其子節(jié)點(diǎn)數(shù)) )q

57、s時(shí)，必須使這一級(jí)舍棄時(shí)，必須使這一級(jí)舍棄了特征了特征 后還剩后還剩(n-d)-(s+1)個(gè)特征。除了從樹的個(gè)特征。除了從樹的縱的方向上一級(jí)丟棄一個(gè)特征，實(shí)際上從樹的橫的縱的方向上一級(jí)丟棄一個(gè)特征，實(shí)際上從樹的橫的方向上，一個(gè)分支也輪換丟棄一個(gè)特征。因此后繼方向上，一個(gè)分支也輪換丟棄一個(gè)特征。因此后繼子節(jié)點(diǎn)數(shù)子節(jié)點(diǎn)數(shù) 。 BAB算法算法7.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法ssX(1)ssqrnds 101BAB算法算法7.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法ss+1n-d(n-d)-(s+1)qsRs節(jié)點(diǎn)特征數(shù)量節(jié)點(diǎn)特征數(shù)量) 1()(sdnqrss) 1(sdnrqssnr 01

58、0 dq102BAB算法算法7.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法60r310 dq,6543210 xxxxxx,654321xxxxx,65431xxxx,6541xxx123103BAB算法算法7.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法60r3) 104(60q,6543210 xxxxxx,654321xxxxx,65432xxxx,6542xxx,652xx123243104BAB算法算法7.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法60r3) 104(60q,6543210 xxxxxx,654321xxxxx123243543543545445455 6656656566666(x5 , x6)(x4 , x6)(x2 , x6)(x4 , x5)(x3 , x6)(x3 , x4)(x3 , x5)(x2 , x5)(x2 , x4)(x2 , x3)(x1 , x6)(x1 , x5)(x1 , x4)(x1 , x3)(x1 , x2)105BAB算法算法7.7.2 7.7.2 最優(yōu)搜索法最優(yōu)搜索法60r3) 104(60q,6543210 xxxxxx,654321xxxxx123243543543545445455