特征選擇提取

特征選擇與提取特征的選取是模式識別的基礎(chǔ)、關(guān)鍵。特征選擇的好壞將直接影響到分類器設(shè)計的好壞。故從原特征的形成，到特征提取和特征選擇，每一步驟都顯得尤為重要。同時特征的選取它也是模式識別的難點，如何獲取如何獲得在追求最優(yōu)解的同時代價（計算量或時間）卻最小的方法。一、原特征選擇的依據(jù)在運用模式識別進行分類器設(shè)計之前，毫無疑問，首先要進行廣泛采集能夠反映研究對象的狀態(tài)、本質(zhì)及性質(zhì)等特征。比如，就如大家平時的講話當中，充斥著許多描述性情節(jié)，就需從怎樣描述其對象才能讓大家認知，找出一大堆的描述詞來對能反映的特征進行修飾。就像兩個同學(xué)在分開多年以后再次遇到，其中的一個人想向另一個人打聽一個不在場的同學(xué)現(xiàn)況，但是可能由于心奮突然一時之間想不起他的名字，這是他就會向?qū)Ψ教峁┮欢研畔ⅲ热缭眠^的綽號、相貌、體型、走路的體態(tài)及說話的方式等等。這些就是泛泛的原特征，可能描述者稍加思索就可以從中找出幾個甚至一個關(guān)鍵特征能夠讓對方明白他講的是誰。比如當聽者收到“當時班里男生里面?zhèn)€子最高的（班里最高的比其他人高都的很明顯，）”或“班里最漂亮的女生（班里其他女生都慘不忍睹）”這樣的話時，他就知道說的是誰了。而其它的許多特征也在描述中起到了一定的作用，一定數(shù)量的特征也可能是對方判定。故原特征選定的好壞對于整個分類器的設(shè)計過程起到了第一個瓶頸。原特征的選定應(yīng)分兩種情況：一種是特征之間主次很明顯。向上面例子中講的那樣設(shè)計（描述）對象的特征對于設(shè)計者來說，已經(jīng)比較清楚，哪個特征是最主要特征，最能反映事物的，哪個次之，哪個再次之，排序很明顯，沒有犯難的。這時原特征選定就比較簡單，只需根據(jù)“專家知識”就能定特征。一種是特征之間的主次不明顯，哪個重要哪個不重要讓人猶豫不決，這時的原特征不能依賴于“專家知識”來定特征，而應(yīng)該對猶豫不決的特征都收集起來，交給下個環(huán)節(jié)運用數(shù)學(xué)方法進行海選。同樣，上例當中的聽者收到“當時班里男生里面?zhèn)€子最高的（但是那時班里個子高的有好幾個，而且都差不多）”或“班里最漂亮的女生（班里其他女生都個個漂亮）”的話時卻因滿足條件的太多了，難以產(chǎn)生聯(lián)想。同時在原特征選定這一環(huán)節(jié)中要注意：首先，要根據(jù)需求找原特征。同樣一部電臺，外形設(shè)計師只獲取電臺的材料質(zhì)地、顏色形狀，而通信工程人員則會關(guān)心其頻率、噪聲等性能參數(shù)，而不在乎其電臺是圓的還是方的，這就是需求不一樣，找特征也不一樣。其次，從實際情況出發(fā)找原特征。要鑒于實際，若當前的人員設(shè)備不能支撐你來獲取或處理此特征，就應(yīng)該拋棄或用其它可獲取和處理的特征來代替。二、特征提取特征選擇與提取是為了求出一組對分類最有效的特征，這就需要一個定量的準則（判據(jù)）來衡量特征對分類的有效性。把一個高維空間變換為低維空間的映射有很多，那種映射對分類最有利，需要一個比較標準。設(shè)計分類器，首先會想到有其錯誤率來作為標準即可。但是，基于類分布常常未知和錯誤概率的計算復(fù)雜，直接用錯誤概率作為標準來分析特征的有效性就比較困難。人們就開始找一些實用的標準來衡量各類建的可分性，但是還未有取得滿意的方法。特征提取就是把維數(shù)比較多的空間最終壓縮到維數(shù)比較少的空間，為下一步的特征篩選而服務(wù)的過程，是把原特征空間眾多特征進行某種組合（通常是線性組合）而減少特征，降低維數(shù)的。三、特征選擇特征選擇就是從一組特征里挑出一些最有效的特征以降低特征空間的維數(shù)的過程。選擇有兩種途徑：首先是從原始特征中去挑選出一些最有代表性的特征（通常在特征提取針對特征進行的映射變換之前完成，這時的特征不單單是只是數(shù)學(xué)歸一，同時還具有現(xiàn)實意義）；再者就是用變換的方法把原始特征變換為較少的新特征。下面針對上述內(nèi)容進行闡述：由原有特征空間中選出若干個特征，組成描述樣本的新特征空間，即從原有的D維空間選取一個d維子空間(d＜D)，在該子空間中進行模式識別。這時就要對前面提到過的兩個問題要進行解決，一個是選擇特性的標準的問題，也就是選擇可分離性判據(jù)，以這些判據(jù)為準則，使所選擇的d維子空間具有最大的可分離性。另一個問題是找出比較好的特征選擇方法，以在允許的時間為主的代價內(nèi)選擇出一組最優(yōu)的特征。所謂最優(yōu)的特征組，就是要找到合適的特征的組合。如果從逐個特征配組進行性能比較的話，即窮舉的算法，特征配組的數(shù)量可能極大，組合配置的數(shù)目按下式計算如果D＝100，d＝10，則q的數(shù)量級就是1013，即使D＝20，d＝10，q也會達到184756種。如果將所有可能的特征配組列舉出來，按某選定的可分離性判據(jù)進行計算，從中擇優(yōu)，其計算量之大是可想而知的。那末如何解決這個問題呢?曾有人以為如果將每維特征單獨計算可分離性判據(jù)，并按其大小排隊，如直接選用前d個特征構(gòu)成新的特征空間，也許可以得到最優(yōu)的可分離性。這樣做的話，就把特征選擇的問題過于簡單化了。因為即使所有特征都互相獨立（而且通過變換，仍保持相互獨立的就不多了），除了極少特殊情況外，直接用前d個最有效的特征組合成的特征組并非是最優(yōu)的d維特征組。因此采用這種方法并不能保證得到最優(yōu)的特征組合，而需要尋找搜索最優(yōu)特征組的合適方法。由于任何非窮舉的算法都不能確保所得結(jié)果是最優(yōu)的，因此要得最優(yōu)解，就必需采用窮舉法，只是在搜索技術(shù)上采用一些技巧，使計算量有可能降低。下面對一種最優(yōu)特征搜索法討論。能得到最優(yōu)解的快速算法有“分支定界”算法——“自上而下”，具有回溯功能，可使所有可能的特征組合都被考慮到。其核心問題是通過合理組合搜索過程，避免一些計算而仍能得到最優(yōu)的結(jié)果。其關(guān)鍵是利用了判據(jù)的單調(diào)性。結(jié)合一個從D＝6特征空間選擇d＝2的最優(yōu)子空間的例子，說明該算法的原理以及如何利用判據(jù)的單調(diào)性減少計算量。設(shè)原D維空間有六個特征表示成{x1,x2,x3,x4,x5,x6}上圖的搜索樹形結(jié)構(gòu)表示搜索過程，根結(jié)點為原特征空間，包含全部特征，在這里是六個特征。除了根結(jié)點外，其它結(jié)點每刪除一個特征，結(jié)點上的號表示被刪特征序號。葉結(jié)點本身也刪除一個特征，而剩下的特征組的特征數(shù)為d，在此為2。葉結(jié)點的個數(shù)由不同的d個特征配置的個數(shù)決定。由于每個結(jié)點只刪除一個結(jié)點，因而從根結(jié)點到葉結(jié)點所在的層數(shù)由D-d決定，在此為4層(不算根結(jié)點所在的第零層)。該樹的結(jié)構(gòu)有一特點，即每一層結(jié)點的直接后繼結(jié)點數(shù)各不相同，但是卻有規(guī)律性。譬如第一層中三個結(jié)點各自的直接后繼結(jié)點數(shù)從左到右分別是3、2與1個，而第一層的最左結(jié)點的三個直接后繼結(jié)點的后繼結(jié)點數(shù)也是如此。實際上整個樹結(jié)構(gòu)是在搜索過程中展開的。在每個當前計算結(jié)點要執(zhí)行的計算按是否處于回溯過程而不同。如處在非回溯過程，則執(zhí)行以下幾個計算：(1)確定直接后繼結(jié)點數(shù)，以根結(jié)點為例。在該結(jié)點上共有六個特征。該結(jié)點層數(shù)為i＝0，因此到達其下屬某一葉結(jié)點需經(jīng)(D-d-i)層(此處為4)，因而需有相應(yīng)數(shù)目的特征備刪除用，并且只有r-(D-d-i)個特征可用作另外的回溯支路入口，因而一結(jié)點的直接后繼點數(shù)在根結(jié)點處r＝6，故q＝3，有三個直接后繼結(jié)點。(2)確定直接后繼結(jié)點要刪除的特征為了使每一當前計算結(jié)點盡可能早地接觸到判據(jù)值較大的葉結(jié)點，在確定直接后繼點待刪除特征時，先計算現(xiàn)有ψ中刪去其中一特征的相應(yīng)判據(jù)值，并將相應(yīng)的特征Xj按判據(jù)值由小到大的順序分別賦予相應(yīng)直接后繼結(jié)點，第一層的三個結(jié)點的待刪除特征分別為與，也就是說有顯然如此安排含有這樣一種假設(shè)，即認為刪除對分類較有效的特征，會使判據(jù)值有明顯減小。為了說明以上兩步我們再舉a點為例，此時a點的為,所以，無分支結(jié)點。在d點，,達到葉結(jié)點，剩下特征組為。至于回溯過程中要執(zhí)行的任務(wù)是將第i層的ψ加上第i-1層被刪除的特征，并檢查其分支路數(shù)q，待發(fā)現(xiàn)到時，就到達回溯轉(zhuǎn)折點，轉(zhuǎn)入其相鄰左邊第i層結(jié)點。從最右端首先回溯至根結(jié)點，由根結(jié)點轉(zhuǎn)至中間枝的第一級點，此時再轉(zhuǎn)入非回溯階段。“分支定界”的最優(yōu)搜索算法的缺點：該算法避免了部分d個特征組合的判據(jù)計算，與窮舉相比節(jié)約了時間。但是由于在搜索過程中要計算中間的判據(jù)值，因此在d很小或d很接近D時，還不如使用窮舉法。另外該算法必須使用具有單調(diào)