1、中國礦業(yè)大學 計算機科學與技術(shù)學院 2013-2014學年第二學期 模式識別大作業(yè) 任課教師：陳偉教師評價優(yōu)+良+中+及格+不及格+教師簽名日期2014.優(yōu)良中及格不及格優(yōu)-良-中-及格-不及格-模式識別特征選擇與提取中國礦業(yè)大學 計算機科學與技術(shù)學院 電子信息科學系班級：信科11-1班，學號：08113545，姓名：褚鈺博聯(lián)系方法（QQ或手機）：390345438，e-mail:390345438日期：2014 年 06月 10日摘要實際問題中常常需要維數(shù)約簡，如人臉識別、圖像檢索等。而特征選擇和特征提取是兩種最常用的維數(shù)約簡方法。特征選擇是從某些事物中提取出本質(zhì)性的功能、應(yīng)用、優(yōu)勢等，而特

2、征提取是對特征空間進行變換，將原始特征空間映射到低維空間中。本文是對主成分分析和線性判別分析。關(guān)鍵詞：特征選擇，特征提取，主成分分析，線性判別分析1.引言 模式識別的主要任務(wù)是利用從樣本中提取的特征，并將樣本劃分為相應(yīng)的模式類別，獲得好的分類性能。而分類方法與分類器設(shè)計，都是在d（變量統(tǒng)一用斜體）維特征空間已經(jīng)確定的前提下進行的。因此討論的分類器設(shè)計問題是一個選擇什么準則、使用什么方法,將已確定的d維特征空間劃分成決策域的問題。對分類器設(shè)計方法的研究固然重要，但如何確定合適的特征空間是設(shè)計模式識別系統(tǒng)另一個十分重要，甚至更為關(guān)鍵的問題。如果所選用的特征空間能使同類物體分布具有緊致性，即各類樣本

3、能分布在該特征空間中彼此分割開的區(qū)域內(nèi)，這就為分類器設(shè)計成功提供良好的基礎(chǔ)。反之，如果不同類別的樣本在該特征空間中混雜在一起，再好的設(shè)計方法也無法提高分類器的準確性。本文要討論的問題就是特征空間如何設(shè)計的問題。 基于主成分分析的特征選擇算法的思想是建立在這樣的基礎(chǔ)上的：主成分分析方法將原始特征通過線性變換映射到新的低維空間時，獲得的主成分是去了新的物理意義，難以理解，并且主成分是所有原始特征的線性組合。所以將主成分分析與特征選擇相結(jié)合，設(shè)計多種相似性度量準則，通過找到與主成分相關(guān)的關(guān)鍵特征或者刪除冗余、不相關(guān)以及沒有意義的特征，將主成分又重新映射到原始空間，來理解成主成分的實際意義。 基于線性

4、判別分析的高維特征選擇將單個特征的Fisher準則與其他特征選擇算法相結(jié)合，分層消除不相關(guān)特征與冗余特征。不相關(guān)特征濾波器按照每個特征的Fisher評價值進行特征排序，來去除噪音和不相關(guān)特征。通過對高維數(shù)據(jù)特征關(guān)聯(lián)性的分析，冗余特征濾波器選用冗余度量方法和基于相關(guān)性的快速過濾器算法。分別在不同情境下進行數(shù)據(jù)分類實驗，驗證其性能。 2.原理分析對一原始特征來說，特征選擇的方案很多，從維特征種選擇出個特征共有中選法，其中哪一種方案最佳，則需要有一個原則來進行指導(dǎo)。我們進行特征選擇和特征提取的最終目的還是要進行識別，因此應(yīng)該是以對識別最有利原則，這樣的原則我們稱為是類別的可分性判據(jù)。用這樣的可分性判

5、據(jù)可以度量當前特征維數(shù)下類別樣本的可分性。可分性越大，對識別越有利，可分性越小，對識別越不利。人們對的特征的可分性判據(jù)研究很多下面幾種常用的判據(jù)，我們需要根據(jù)實際問題，從中選擇出一種。一般來說，我們希望可分性判據(jù)滿足以下幾個條件：1. 與識別的錯誤率由直接的聯(lián)系，當判據(jù)取最大值時，識別的錯誤率最小；2. 當特征獨立時有可加性，即：是第類和第類的可分性判據(jù)，越大，兩類的可分程度越大，為維特征；3. 應(yīng)具有某種距離的特點：，當時；，當時；4. 單調(diào)性，加入新的特征后，判據(jù)不減小：。但是遺憾的是現(xiàn)在所經(jīng)常使用的各種判據(jù)很難滿足上述全部條件，只能滿足一個或幾個條件。特征提取又稱為特征變換，最常采用的特

6、征變換是線性變換，即若是D維原始特征，變換后的d維新特征為 ， 其中，W是維矩陣，稱作變換陣。特征提取就是根據(jù)訓練樣本求適當?shù)腤，使得某種特征變換準則最優(yōu)。主成分分析方法的出發(fā)點是從一組特征中計算出一組按重要性從大到小排序的新特征，他們是原有特征的線性組合，并且相互之間是不相關(guān)的。記為p個原始特征，設(shè)新特征，i=1,，p是這些原始特征的線性組合 ， 為了統(tǒng)一的尺度，要求線性組合的模為1，即 ， 寫成矩陣形式是 ， 其中，是由新特征組成的向量，A是特征變換矩陣。要求解的是最優(yōu)的正交變換A，它使新特征的方差達到極值。3.理論證明或說明特征選擇的基本框圖為:子集產(chǎn)生子集產(chǎn)生原始特征集子集 終止條件否

7、子集產(chǎn)生是一個典型的特征選擇算法通常包括四個人基本步驟:1. 子集產(chǎn)生，這是一個搜索過程，通過一定的搜索策略產(chǎn)生候選的特征子集。2. 子集評價，每一個候選的特征子集都根據(jù)一定的評價準則得到，并與先前的最優(yōu)特征子集進行比較。3. 終止條件，算法結(jié)束所需要滿足的條件，它與子集的產(chǎn)生過程和評價準則的選用有關(guān)。4. 結(jié)果驗證，就是根據(jù)一定的先驗知識或通過合成現(xiàn)實數(shù)據(jù)集的測試來證明所選擇的特征子集的性能。基于特征提取主成分分析變換矩陣的一般過程： 訓練數(shù)據(jù)全集PCA處理變換矩陣分析 生成變換矩陣輸出特征子集4.實現(xiàn)方法或步驟流程特征選擇順序前進法每次從未入選的特征中選擇一個特征，使得它與已入選的特征組合

8、到一起所得到的可分性判據(jù)最大，直到特征數(shù)增加到為止。用表示在第步時的特征集合，搜索算法如下：1) 開始時，從個特征中選擇一個最大的特征，加入已選特征集，；2) 在第步，中包含已經(jīng)選擇的個特征，對未入選的個特征計算，其中，并且按照由大到小排序，將可分性判據(jù)最大的特征加入，；3) 直到所選的特征數(shù)等于為止。特征抽取的方法基于離散K-L變換(DKLT)的特征抽取：設(shè)原始特征為為矢量，均值矢量，相關(guān)矩陣，協(xié)方差矩陣。我們可以對作如下的標準正交變換，將其變?yōu)槭噶?的每個分量：，其中為一個的標準正交矩陣，為其第個列矢量，。也就是說的每個分量是每一個分量的線性組合。同樣可以表示為：我們要進行特征提取，也就是

9、要用的項來代替，這種代替必然帶來誤差，下面我們來對這個誤差進行估計：令：，引入的均方誤差為：這又變成一個優(yōu)化問題，我們希望尋找到一個標準正交矩陣，使得最小，因此可以去這樣的準則函數(shù)：第一項保證均方誤差最小，第二項保證為標準正交矩陣，為一待定常數(shù)。，即：，很明顯為相關(guān)矩陣的特征值，為對應(yīng)于的特征矢量，由于是一個實對稱矩陣，所以相互正交，為一個正交矩陣。均方無差：根據(jù)矩陣論，有這樣的結(jié)論：一個的正定實對稱矩陣有個特征值和特征矢量，這些特征矢量之間是正交的。相關(guān)矩陣就是一個實對稱矩陣，當訓練樣本足夠多時，也可以滿足正定性，根據(jù)上式我們知道，當要從維特征中提取出維特征時，我們只需要統(tǒng)計出特征相關(guān)矩陣，

10、然后計算其特征值和特征矢量，選擇對應(yīng)特征值最大的前個特征矢量作成一個特征變換矩陣，就可以完成特征提取。步驟如下：1、 利用訓練樣本集合估計出相關(guān)矩陣；2、 計算的特征值，并由大到小排序：，以及相應(yīng)的特征矢量：；3、 選擇前個特征矢量作成一個變換矩陣；4、 在訓練和識別時，每一個輸入的維特征矢量可以轉(zhuǎn)換為維的新特征矢量：。這種方法是利用相關(guān)矩陣進行變換，同樣也可以利用協(xié)方差矩陣進行變換，還可以利用樣本的散度矩陣，或者進行變換。過程都是一樣的，需要計算特征值和特征向量，選擇最大的個特征值對應(yīng)的特征矢量作出變換矩陣。5.實驗設(shè)計和結(jié)果分析 基于特征相關(guān)性的特征選擇算法選擇c均值聚類算法來去除冗余。

11、C均值算法的基本思想即是通過迭代尋找c個聚類的一種劃分方案，使得用這c個聚類的均值來代表相應(yīng)各類樣本時所得到的總體誤差最小。 C均值算法的基礎(chǔ)是最小誤差平方和準則。若是第i聚類中的樣本數(shù)目，是這些樣本的均值，即 把中的各樣本y與均值間的誤差平方和對所有類相加后為是誤差平方和聚類準則，它是樣本集和類別集的函數(shù)。 C均值算法的步驟：1.選擇初始劃分，并計算每個聚類的均值以及誤差平方和；2.選擇一個備選樣本y，設(shè)y； 3.若樣本數(shù)目為1，則轉(zhuǎn)2，否則繼續(xù)； 4.計算：ji時，； j=i時， ；5. 考查中的最小者，若，則把y從移到中； 6.重新計算聚類i和k的均值，并修改誤差平方和；7.若多次迭代后

12、誤差平方和不變，則停止，否則轉(zhuǎn)到步驟2。1.無論在聚類時，初始均值如何選取，在程序結(jié)果中總能得到相同的分類結(jié)果，同時的結(jié)果相差很小。 2當各聚類設(shè)定的初始均值不同時，程序結(jié)果經(jīng)過的步驟不同。3.是隨著聚類數(shù)目的增加而單調(diào)的減少的，當聚類數(shù)目等于樣本數(shù)時=0，即每個樣本自己成一類。4.此算法是個局部搜索算法，并不能保證收斂到全局最優(yōu)解，即不能保證找到所有可能的聚類劃分中誤差平方和最小的解。算法的結(jié)果受到初始劃分和樣本調(diào)整順序的影響。6. 結(jié)論模式識別技術(shù)是人工智能的基礎(chǔ)技術(shù)，21世紀是智能化、信息化、計算花、網(wǎng)絡(luò)化的世紀，在這個以數(shù)字計算為特征的世紀里，模式識別技術(shù)將會獲得巨大的發(fā)展空

13、間。特征選擇作為數(shù)據(jù)預(yù)處理的一個必要步驟，是模式識別中的一個關(guān)鍵問題。一個模式識別系統(tǒng)的成敗，首先取決于所利用的特征是否較好的反映了將要研究的分類問題。而且高維數(shù)據(jù)是特征選擇的一個挑戰(zhàn)，研究人員總是努力的尋找著各種方法來盡量提高特征選擇的性能。對于特征選擇與特征提取，還有許多問題期待解決：高維數(shù)據(jù)的特征選擇，特別是訓練樣本較少而特征維數(shù)極高的數(shù)據(jù)集；在樣本的類別數(shù)未知的情況下，設(shè)計時間復(fù)雜度較低的非監(jiān)督的特征選擇；如何在進行特征選擇時，選擇有意義的訓練樣本；將維數(shù)約簡與距離度量學習相結(jié)合；隨著特征選擇的應(yīng)用領(lǐng)域不斷擴大，當出現(xiàn)新的非線性相關(guān)的數(shù)據(jù)類型時，如何設(shè)計新的特征選擇算法；將特征選擇算法

14、應(yīng)用于人臉識別與人臉檢測中，消除傳統(tǒng)人臉識別方法如PCA和LDA固有的局限性。模式識別是一門理論與實踐緊密結(jié)合的學科，教與學的方式值得我們研究和探索。還可以看出模式識別具有相當大的前景，而且模式識別的應(yīng)用得到越來越多的人的支持，而且它的成效也十分顯著。因此它也得到各國的重視，正因各個單位集體對人工智能的模式識別給予相關(guān)的重視，模式識別技術(shù)在現(xiàn)今社會也能快速發(fā)展。當然，現(xiàn)在的模式識別還不算真正完整，不過人類科技的技術(shù)是不斷發(fā)展的，相信總有一天人工智能中的模式識別會真正融入我們的社會，成為我們?nèi)祟惒豢苫蛉钡囊徊糠帧６O(shè)計具體的、專業(yè)的、高效的特征選擇算法是一個值得重視值得探索的研究方向。7.參考文獻：1 張學工.模式識別（第三版).北京：清華大學出版社，20102 朱明，王俊普，蔡慶生.一種最優(yōu)特征集的選擇算法，計算機研究與發(fā)展.vol.35(9),pp.803-805,19983L.Yu,H.Lu,Efficient feature selection via analysis of relevance and redundancy,Machine Learning Research,vol.5,pp.1205-1224,20044 M.Dash,K.Choi,P.Scheuermann and H.Liu,Fea