第7章特征提取與選擇7.1特征提取與選擇的基本概念7.2基于距離的特征提取7.3基于離散K-L變換的特征提取7.4特征選擇方法前面幾章討論傳統(tǒng)模式識別方法時，一直假定給定的數(shù)據(jù)集的特征都是對識別問題非常重要的。然而在很多實際問題中，數(shù)據(jù)的某些特征可能和識別任務(wù)是不相關(guān)的或者特征之間存在冗余。特征提取與選擇的主要任務(wù)是研究如何從眾多的特征中求出那些對分類識別任務(wù)最有效的特征。

為使特征能夠代表對象，且便于實際操作和算法實現(xiàn)，并使分類結(jié)果真實可靠，要求所選用的特征應(yīng)滿足以下五個條件：

(1)真實性，特征應(yīng)能準(zhǔn)確地包含分類對象的物理信息。(2)有效性，所選用的特征和特征組合對分類是有效的，盡量使得對象易于分類識別。

(3)簡約性，信息充分且數(shù)據(jù)冗余量少。

(4)魯棒性，當(dāng)所選用的特征受到測量誤差較大影響時，盡量使得算法的有效性不被破壞。

(5)提取特征方便經(jīng)濟，便于實際操作。

本章不涉及具體的應(yīng)用背景，因此不對(1)、(4)和(5)進(jìn)行討論，主要針對(2)和(3)的一些重要理論和技術(shù)進(jìn)行詳細(xì)介紹。

本章主要討論特征提取與選擇的基本概念、基于距離的特征提取、基于離散K-L變換的特征提取以及特征選擇方法。

7.1特征提取與選擇的基本概念

7.1.1特征的種類

特征是描述待分析對象性質(zhì)的一種量，是對對象的一種抽象。從形式上看，特征可以分為以下三類：

1.物理特征

物理特征是根據(jù)對象的外在表現(xiàn)抽取的特征。例如為了描述某個人，通常采用性別、身高、胖瘦、膚色等特征，這些特征都屬于物理特征。物理特征是比較直接、容易感知的特征，一般在設(shè)計模式識別系統(tǒng)時被選用。

2.結(jié)構(gòu)特征

結(jié)構(gòu)特征是能表征觀察對象結(jié)構(gòu)信息的特征。例如人的指紋具有小橋、環(huán)、分叉點、三角點和端點等特征，這些特征都屬于結(jié)構(gòu)特征。結(jié)構(gòu)特征的獲取是先將觀察對象分割成若干基本構(gòu)成要素，然后確定基本要素間的相互連接關(guān)系，通過各個要素和相互的連接關(guān)系表達(dá)對象。結(jié)構(gòu)特征比物理特征要抽象一些，但仍屬比較容易感知的特征，其表達(dá)能力一般要高于物理特征。結(jié)構(gòu)特征在實際模式識別問題中已經(jīng)有較多的成功應(yīng)用，例如指紋識別和人臉識別等。

3.數(shù)學(xué)特征

數(shù)學(xué)特征是為了表征觀察對象而人為設(shè)定的特征。例如每個學(xué)生的學(xué)號就是一種數(shù)學(xué)特征。數(shù)學(xué)特征有時和觀察對象的固有屬性沒有關(guān)系，有時則是觀察對象的物理或結(jié)構(gòu)特征的計算結(jié)果。需要指出，數(shù)學(xué)特征是人為設(shè)定的，可以保證唯一性，但這種特征是抽象的，不容易被人感知。由于物理和結(jié)構(gòu)特征很容易被視覺、觸覺以及其他感覺器官所發(fā)現(xiàn)，因此人們通常利用這些特征來識別對象，但是這些特征對于計算機而言有時比較復(fù)雜。計算機在抽取和處理數(shù)學(xué)特征的能力方面要比人強得多。在本章中，計算機使用的數(shù)學(xué)特征包括統(tǒng)計平均值、相關(guān)矩陣和協(xié)方差矩陣的特征值及特征向量等。7.1.2特征提取與選擇

特征提取是指通過映射或變換獲取有效特征的過程。提取后的特征稱為二次特征，它們是原始特征的某種組合，最常見的是線性組合。需要強調(diào)的是，特征提取一定要進(jìn)行數(shù)學(xué)變換。特征選擇是指從一組特征中挑選出對分類最有效的特征，實現(xiàn)特征選擇的前提是確定特征是否有效的標(biāo)準(zhǔn)，在這種標(biāo)準(zhǔn)下方可尋找最有效的特征子集。用于特征選擇的特征既可以是原始特征，也可以是經(jīng)特征提取后得到的二次特征。在實現(xiàn)特征提取和選擇的目標(biāo)之前，需要首先制定特征提取和選擇的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)應(yīng)該能夠反映各類在特征空間的分布情況或刻畫出特征對分類識別的重要性。在具體實施特征提取和選擇時可以遵循如下兩個基本的途徑：

(1)已知可分性判據(jù)J，在使得該判據(jù)取得最大值的目標(biāo)下，對原始特征進(jìn)行變換降維，即對原始特征空間進(jìn)行坐標(biāo)變換，再取子空間。該類變換方法主要有基于距離可分性測度的特征提取方法和基于離散K-L變換的特征提取方法等。

(2)直接尋找原始特征空間中的低維子空間，即直接選擇法。在選擇的過程中，尋找能夠使得可分性判據(jù)最大化的那組低維特征空間組合。直接特征選擇方法包括最優(yōu)搜索法和次優(yōu)搜索法等。特征提取和特征選擇都是在不降低或較少降低分類性能的情況下，降低特征空間的維數(shù)。其主要作用在于：

(1)簡化計算。特征空間的維數(shù)越高，需要占用的計算機資源越多，計算的復(fù)雜度也就越高。

(2)簡化特征空間結(jié)構(gòu)。特征提取和選擇是去除類間差別小的特征，保留類間差別大的特征，使得每類所占據(jù)的子空間結(jié)構(gòu)可分離性更強，從而也可以簡化類間分界面形狀的復(fù)雜度。

需要指出，特征提取和選擇并不是截然分開的。例如，可以先將原始特征空間映射到維數(shù)較低的空間，然后在這個空間中進(jìn)行特征選擇來進(jìn)一步降低維數(shù)。

7.2基于距離的特征提取

特征提取與選擇的目的是獲得一組對于分類識別最有效的特征，從而實現(xiàn)特征空間維數(shù)的約簡。然而，把一個高維特征變?yōu)榈途S特征的方法是很多的，需要一個標(biāo)準(zhǔn)來衡量哪種方法最有效，這種標(biāo)準(zhǔn)即為類別可分性測度。一般希望所構(gòu)造的可分性判據(jù)應(yīng)滿足下列幾個要求：

(1)與錯誤率(或錯誤率的上界及下界)有單調(diào)關(guān)系，即使得可分性測度取最大(或最小)值時，錯誤率也最小。

(2)當(dāng)特征相互獨立時，可分性測度具有可加性,即

這里，x1，x2，…，xd是對象不同種類特征的測量值;Jij(·)是第i類和第j類之間的可分性測度函數(shù)，Jij越大，表示兩類的分離程度就越大。

(3)度量特性，主要包括非負(fù)性和對稱性：

Jij>0，當(dāng)i≠j時

Jij=0，當(dāng)i=j時(7-2)

Jij=Jji

(7-1)

(4)單調(diào)性，即加入新的特征后，該可分性測度的值不會減?。?/p>

Jij(x1，x2，…，xd)≤Jij(x1，x2，…，xd，xd+1)

(7-3)

很多人在這方面做了不少工作，提出了各種可分性測度，本節(jié)主要介紹基于距離的類別可分性測度，以及基于這些可分性測度的特征提取方法。7.2.1基于距離的類別可分性測度

一般地講，各類中的樣本可以被分開是因為它們位于特征空間中的不同區(qū)域，我們總是希望不同類的樣本之間的距離大一些，而同類的樣本較集中。不同類區(qū)域之間距離越大或者重疊的部分越小，類別可分性就越好，因此，利用距離準(zhǔn)則來構(gòu)造類別可分性判據(jù)是可行的。我們在第6章的6.2節(jié)給出了多類情況下總的類內(nèi)離散度矩陣SW、類間離散度矩陣SB和總的離散度矩陣ST的定義，并給出了利用它們構(gòu)造的聚類準(zhǔn)則函數(shù)J1~J6。實際上，這些聚類準(zhǔn)則函數(shù)可以作為類別可分性判據(jù)來進(jìn)行特征提取，這里，把它們稱之為基于距離的類別可分性測度。除了第6章給出的J1~J6這六個類別可分性測度，下面給出另外三個類別可分性測度；(7-4)(7-5)(7-6)為了使所使用的特征能夠有效地進(jìn)行分類，我們希望類間離散度盡量大，同時類內(nèi)離散度盡量小。所以，J4、J5和J6這三個測度越小越好，剩余六個測度則是越大越好。這些類別可分性測度之間存在關(guān)聯(lián)，有的可分性測度之間幾乎等

價，但性能上略有不同。7.2.2基于距離可分性測度的特征提取

設(shè)原始樣本為x=(x1，x2，…，xq)T，其中，q為特征的維數(shù)。對x作線性變換，產(chǎn)生d維特征向量y=(y1，y2，…，yd)T，d≤q，即

y=WTx

(7-7)

其中，q×d矩陣W為特征提取矩陣或者變換矩陣。本小

節(jié)我們討論在基于距離的類別可分性測度準(zhǔn)則下，如何求得最優(yōu)變換矩陣W。采用基于距離的類別可分性測度J1~J9進(jìn)行特征提取時，需要求矩陣的跡最大(最小)或者行列式值最大(最小)。下面我們先以J1測度為例說明如何求矩陣跡最大化，再以J9測度為例說明如何求行列式值最大，其他類別可分性測度可類似處理。J1的定義如下；

其中，SW和SB分別為原始樣本的類內(nèi)和類間離散度矩陣。在新的變換特征空間中，新樣本的類內(nèi)和類間離散度矩陣S*W和S*B可定義為；(7-8)(7-9)

在新的變換特征空間中

若W為非奇異矩陣，可以等價為，這表明在非奇異變換條件下，原特征空間的類可分判據(jù)與新空間的判據(jù)是相同的。設(shè)WT是標(biāo)準(zhǔn)正交矩陣，利用該矩陣對進(jìn)行對角化，得到(7-10)(7-11)(7-12)其中，λi(i=1，2，…，q)為的特征值，WT的列向量wi是對應(yīng)于特征值λi的特征向量。由于一個方陣的跡等于它的所有特征值之和，因此可得

當(dāng)新特征空間的維數(shù)d確定之后，取出的d個較大特征值對應(yīng)的特征向量wi構(gòu)造特征提取矩陣W，即

W=(w1，w2，…，wd)

(7-14)

此時采用W對x作變換，可分性測度J1達(dá)到了最大值,即(7-13)(7-15)其中，λ1≥λ2≥…≥λd≥…≥λq。

下面以J9為例，介紹如何運用以行列式形式出現(xiàn)的可分性測度求最優(yōu)變換矩陣W。

易知SW是對稱正定矩陣，存在非奇異矩陣A，使得

ATSWA=I

(7-16)

其中，I為單位矩陣。有標(biāo)準(zhǔn)正交矩陣V，可使V-1ATSTAV

=，為對角陣，而

令U=AV，則存在非奇異矩陣U，使得(7-17)且

UTSWU=I

(7-18)

對上式兩邊同時取逆，有

對上式兩邊左乘(7-16)式兩邊，得

再對上式左乘U，則有

從上式可知，U和分別為的特征向量構(gòu)成的矩陣及特征值構(gòu)成的對角陣。由于(7-19)(7-20)(7-21)

所以

即

如果設(shè)的特征值矩陣Λ=diag(λ1，λ2，…，λq)，則

那么(7-22)(7-23)(7-24)(7-25)(7-26)對于給定的d，取的前d個較大特征值對應(yīng)的特征向量構(gòu)成變換矩陣W，可使可分性測度J9達(dá)到最大值,即

其中，λ1≥λ2≥…≥λd≥…≥λq。(7-27)例7.1給定具有兩個模式類的樣本集X={x1，x2，…，x7}，其中，ω1：x1=(1，1)T，x2=(1，2)T，x3=(3，1)T，x4=(3，3)T；ω2：x5=(－2，－2)T，x6=(－2，－3)T，

x7=(－3，－2)T。利用類別可分性測度J9將樣本特征維數(shù)變?yōu)橐痪S。

解(1)計算矩陣。首先分別計算各類樣本均值向量mi(i=1，2)和樣本總體均值向量m。

然后計算每一類的類內(nèi)離散度矩陣，i=1，2,即接著計算總的類內(nèi)離散度矩陣SW；然后計算總的離散度矩陣ST；

最后計算

(2)計算D的特征值和特征向量。根據(jù)|D-λI|=0，可得

λ1=14.09，λ2=1.00

根據(jù)，可得λ1和λ2對應(yīng)的特征向量分別為；

w1=(0.60，0.80)T

w2=(-0.69，0.73)T

(3)選擇w1構(gòu)成變換矩陣W，即

W=w1

(4)利用W對樣本集X中的每一個樣本進(jìn)行特征提取，即

yi=WTxi

最終結(jié)果為

y1=1.40，y2=2.20，y3=2.60，y4=4.20

y5=－2.80，y6=－3.60，y7=－3.40

特征提取結(jié)果如圖7.1所示。圖7.1基于類別可分性測度J9的特征提取結(jié)果

7.3基于離散K-L變換的特征提取

離散K-L變換又稱為霍特林變換或主成分分析，是一種基于目標(biāo)統(tǒng)計特性的正交變換。該變換具有如下重要性質(zhì)：(1)變換后產(chǎn)生的新分量是正交或者不相關(guān)的；(2)變換后各分量的非零平方期望或方差更趨于不均；(3)采用部分新分量表示原向量時均方誤差最小，即具有最佳逼近性；(4)變換后向量能量更加集中，即變換使能量向某些分量相對集中；(5)變換后向量在總體上更趨確定性。鑒于離散K-L變換具有上述諸多性質(zhì)，它已經(jīng)在特征提取方面得到了極為重要的應(yīng)用。7.3.1離散K-L變換(DKLT)

設(shè)q維隨機向量x=(x1，x2，…，xq)T，其均值向量為，相關(guān)矩陣為Rx=E［xxT］，協(xié)方差矩陣為

。x經(jīng)過標(biāo)準(zhǔn)正交矩陣WT正交變換后變成向量y=(y1，y2，…，yq)T，即(7-28)明顯可以看出，y的各個分量為

而且由于WT為正交矩陣，因此，i=1，2，…，q

(7-29)(7-30)選擇x關(guān)于yi的展開式的l項在最小均方誤差準(zhǔn)則下來線性估計x，此時，x的估計式為，1≤l≤q

(7-31)該估計式與x的均方誤差為

為了使得均方誤差ε2(l)在W為標(biāo)準(zhǔn)正交矩陣的約束下(即

)取得最小值，可以采用下式作為準(zhǔn)則函數(shù)：

由可得(7-32)(7-33)

即

Rxwi=λiwi，i=l+1，…，q

(7-35)

式中，λi為x的相關(guān)矩陣Rx的特征值；wi為Rx的對應(yīng)于λi的特征向量。將上式代入均方誤差ε2(l)表達(dá)式(7-32)中，可得

如果在x的估計式中保留l個yi，而余下的q-l個分量yi(i=l+1，…，q)分別由預(yù)選的q-l個常數(shù)bi代替，此時的估計式可以表示為i=l+1，…，q

(7-34)(7-36)

估計的均方誤差為

最佳的bi可以通過ε2/bi=0求得，即

可得(7-37)(7-38)(7-39)(7-40)于是

在W為標(biāo)準(zhǔn)正交矩陣的約束下，求使得ε2(l)→min的wi的方法和前面類似，構(gòu)造準(zhǔn)則函數(shù)為

由可得

Cxwi=λiwi，i=l+1，…，q

(7-43)(7-41)(7-42)從上式可以看出，λi和wi分別為x的協(xié)方差矩陣Cx的特征值和相應(yīng)的特征向量。將上式代入均方誤差ε2(l)表達(dá)式(7-41)中，可得

當(dāng)采用式(7-31)估計x時，使均方誤差最小的正交變換矩陣是隨機向量x的相關(guān)矩陣Rx的特征向量矩陣的轉(zhuǎn)置；而當(dāng)采用式(7-37)估計x時，使均方誤差最小的正交變換矩陣是x的協(xié)方差矩陣Cx的特征向量矩陣的轉(zhuǎn)置。無論上述哪種情況，為使ε2(l)最小化，都是采用前l(fā)個較大特征值對應(yīng)的特征向量構(gòu)造l×q的變換矩陣?？偨Y(jié)上面的內(nèi)容，我們給出下面的定理。(7-44)定理7.1在一切標(biāo)準(zhǔn)正交變換z=VTx=(v1v2…vq)Tx中，用隨機向量x的協(xié)方差矩陣Cx的特征向量矩陣(w1w2…wq)對其進(jìn)行變換所得的向量y可使

式中，(w1

w2…wq)的各列對應(yīng)的特征值滿足λ1≥λ2≥…≥λq，。

這種采用x的相關(guān)矩陣Rx或者協(xié)方差矩陣Cx的特征向量矩陣作為變換矩陣的變換稱為離散K-L變換，此時，式(7-30)稱為x的K-L展開。

(7-45)7.3.2離散K-L變換在特征提取中的應(yīng)用

設(shè)X={x1，x2，…，xn}表示一個具有c個模式類的樣本集合，其中，每個樣本xi是一個q維向量。下面介紹如何采用離散K-L變換對樣本集進(jìn)行特征提取，將樣本的特征維數(shù)從q維降到d維。

(1)求c類樣本集X的總體自相關(guān)矩陣R。

(2)求R的特征值λi和對應(yīng)的特征向量wi，i=1，2，…，q，并將特征值按照從大到小的順序進(jìn)行排列。(7-46)

(3)將R的前d個較大特征值對應(yīng)的特征向量wi構(gòu)成變換矩陣W，即

W=［w1，w2，…，wd]

(7-47)

(4)對樣本集X={x1，x2，…，xn}中的每一個樣本xi進(jìn)行K-L變換，得到相應(yīng)的d維向量yi，即

yi=WTxi

(7-48)上面我們介紹了利用樣本集的自相關(guān)矩陣R進(jìn)行特征提取，同理可以先獲得樣本集的協(xié)方差矩陣C，形式如下：

然后利用C進(jìn)行特征提取，該過程與上述過程類似，這里就不再贅述。(7-49)例7.2利用K-L變換將例7.1中樣本集的特征維數(shù)由兩維降為一維。

解(1)計算X的總體自相關(guān)矩陣R。

(2)計算R的特征值和特征向量。根據(jù)|]R-λI|=0，可得

λ1=9.37，λ2=0.49

根據(jù)Rwi=λiwi，可得λ1和λ2對應(yīng)的特征向量分別為；

w1=［0.74，0.68］T

w2=［-0.68，0.74］T

(3)選擇w1構(gòu)成變換矩陣W，即

W=w1

(4)利用W對樣本集X中的每一個樣本進(jìn)行K-L變換，即

yi=WTxi

變換結(jié)果為

y1=1.42，y2=2.10，y3=2.90，y4=4.26

y5=－2.84，y6=－3.52，y7=－3.58

7.4特征選擇方法

7.2和7.3節(jié)介紹了對原始特征空間進(jìn)行變換來獲得有效特征的方法。我們也可以采用特征選擇的方法，依據(jù)某種準(zhǔn)則或者策略從原始特征中挑選出一些最有代表性的，分類性能最好的特征出來。因此，特征選擇方法需要解決以下兩個問題：(1)如何評價特征組合的有效性；(2)尋找有效特征組合的方法和策略。一般情況下，原始特征空間的維數(shù)是已知的，為保證選擇出的特征具有一定的分類性能，可以通過7.2節(jié)介紹的各種可分性判據(jù)對特征組合的有效性進(jìn)行度量。此外，由于選擇后的特征維數(shù)d一般是未知的，假設(shè)原始特征空間維數(shù)為q，則d的選擇范圍是1~q之間的任何一個自然數(shù)，因此，所有可能的特征組合數(shù)目為。顯而易見，這是一個典型的組合優(yōu)化問題，如果q值很大，選擇的特征數(shù)目也很多，則特征選擇的復(fù)雜度是非常高的。為此，人們提出了一系列特征選擇的策略。本節(jié)介紹兩種特征選擇方法：最優(yōu)搜索法和次優(yōu)搜索法。7.4.1最優(yōu)搜索法

分支定界法是一種經(jīng)典的最優(yōu)搜索方法。在該算法中，尋找全局最優(yōu)特征組合的搜索過程可以用一個樹形結(jié)構(gòu)來描述，稱其為搜索樹。搜索方案是沿著搜索樹從上而下、從右向左進(jìn)行，由于該樹的每個節(jié)點代表一種特征組合，因此所有的特征組合都被考慮到了。分支定界法的關(guān)鍵是利用了特征選擇可分性判據(jù)J的單調(diào)性，即對于兩個特征子集X和Y,有

因此某些特征組合并不需要計算且又不影響全局最優(yōu)特征組合的搜索。此外，該算法先從結(jié)構(gòu)簡單的部分開始搜索，所以效率很高。(7-50)下面采用一個從5個特征中選擇2個特征的例子來說明分支定界法的原理。設(shè)原空間中的5個特征為{x1，x2，x3，x4，x5}，整個搜索過程的樹形結(jié)構(gòu)如圖7.2所示。在該圖中，根節(jié)點代表全部特征，節(jié)點上的數(shù)字表示所選特征的編號，因此其上的數(shù)字為(1，2，3，4，5)。每個節(jié)點表示一個特征組合，子節(jié)點所代表的特征比其父節(jié)點代表的特征少一個，同父的各子節(jié)點分別代表從父節(jié)點的特征組合中舍棄不同的一個特征后余下的特征。由于每個節(jié)點只刪除一個特征，如果是從q個特征中選擇d個，那么根節(jié)點到葉節(jié)點的層數(shù)由q-d決定，因此本例中為3層(根節(jié)點在第0層)。為使各個特征子集不重復(fù)，從父節(jié)點到子節(jié)點的特征刪除過程中，要按照特征編號的順序依次刪除一個不同的特征。例如在第1層中，從左往右各個子節(jié)點刪除的特征分別為1、2和3。只有三個子節(jié)點的原因是由于對某個子節(jié)點來講，其左邊同父節(jié)點已丟棄的特征以后不能在要丟棄的特征組合里，這樣可以防止得到重復(fù)的特征組合。另外，從圖中可以看出，每個分支最右邊的節(jié)點總是只有一個子節(jié)點。圖7.2分支定界法搜索樹示例分支定界法的基本原理是先找到一個d維組合，期望該特征組合的判據(jù)值盡可能的大，并以此為界，然后將后續(xù)搜索到的節(jié)點的判據(jù)值與該界值進(jìn)行比較。如果某節(jié)點的特征組合的判據(jù)值小于界值，則由判據(jù)的單調(diào)性，該節(jié)點的所有子節(jié)點不可能是最優(yōu)特征組合，也就不需要再進(jìn)行搜索。在已獲得樹結(jié)構(gòu)的條件下，特征組合搜索過程總體上是從分支數(shù)量不密集的部分到分支數(shù)最密集的部分，也就是從上到下、從右到左進(jìn)行。在這個過程中包含幾個可能的子過程：向下搜索、更新界值、向上回溯、停止回溯再向下搜索。在搜索之前先將界值B初始化為0，然后從樹的根節(jié)點沿最右邊的一支自上而下搜索。在搜索樹中，一個節(jié)點的子樹最右邊一支總是無分支的，因此從根節(jié)點開始可以直接到達(dá)葉節(jié)點，得到特征集(1，2)。假設(shè)該葉節(jié)點的特征組合的可分性判據(jù)值為J(1，2)=75，此時更新界值B=75，然后向上回溯。一旦遇到有分支的節(jié)點就停止回溯，轉(zhuǎn)而向下搜索。因此，從特征集為(1，2)的節(jié)點向上回溯遇到根節(jié)點停止，轉(zhuǎn)而向特征集為(1，3，4，5)的節(jié)點分支進(jìn)行搜索。由于J(1，3，4，5=82>J(1，2)，繼續(xù)往右邊分支進(jìn)行搜索，從圖7.3中可知，一直可以搜索到葉子節(jié)點并計算特征組合(1，3)的判據(jù)值J(1，3)=79

>B，因此更新界值B=79，然后再向上回溯。依此類推，可以搜索到特征組合(1，5)的判據(jù)值J(1，5)=81>B，因此更新界值B=81。從特征集為(1，5)的節(jié)點向上回溯遇到根節(jié)點停止，轉(zhuǎn)而向特征集為(2，3，4，5)的節(jié)點分支進(jìn)行搜索。由于J(2，3，4，5)=78<B，根據(jù)單調(diào)性，該特征集合的所有子集的可分性判據(jù)都低于其自身的可分性判據(jù)。此時分支定界法停止搜索，得到最優(yōu)特征組合(1，5)。圖7.3分支定界法搜索回溯示意圖分支定界法的高效性在于：(1)利用了可分性判據(jù)的單調(diào)性，從而避免了有相當(dāng)多的特征組合的判據(jù)計算。如果樹上某個節(jié)點a的可分性判據(jù)值滿足Ja≤B，可知a的子樹上各節(jié)點的可分性判據(jù)值都不會大于B，因此節(jié)點A的子樹節(jié)點都不用去搜索，這就是所謂的分支定界；(2)分支定界法的搜索過程是從右至左進(jìn)行的，由于樹的右邊分支要比左邊分支結(jié)構(gòu)簡單，因此分支定界法具有高效的性能。7.4.2次優(yōu)搜索法

1.單獨最優(yōu)的特征選擇法

單獨最優(yōu)特征選擇法是最簡單的一種特征選擇算法。該算法首先計算每個特征單獨使用時的可分性判據(jù)值，然后根據(jù)得到的判據(jù)值對各個特征進(jìn)行排序，最后選擇前d個分類效果最好的特征作為最終的特征組合。

一般情況下，即使各個特征之間是統(tǒng)計獨立的，單獨最優(yōu)特征選擇算法選出的d個特征也不一定是最優(yōu)的特征組合。只有當(dāng)可分性判據(jù)J寫為如下形式時：或(7-51)這種算法才能獲得最優(yōu)的特征組合。例如在正態(tài)分布情況下，當(dāng)各個特征是相互獨立時，用馬氏距離作為判據(jù)選出的d個特征就是最優(yōu)的特征組合。

2.順序前進(jìn)法

順序前進(jìn)法(SequentialForwardSelection，SFS)也稱為增添特征法，是一種最簡單的自下而上的搜索算法。該算法的基本思路是,每次從未選入的特征中選擇一個特征，使它與已選入的特征組合在一起的可分性判據(jù)最大，直到特征數(shù)目達(dá)到指定的數(shù)目d為止。假設(shè)已經(jīng)選擇了k個特征，記為Xk，把未選擇的q-k個特征xj(j=1，2，…，q-k)逐個與Xk組合后計算可分性判據(jù)值J，若

則選擇x*與Xk構(gòu)成新的特征組合，該過程一直進(jìn)行到選入的特征數(shù)目達(dá)到指定維數(shù)d為止。

順序前進(jìn)法考慮了所選特征與已選入