模式識(shí)別特征選擇與提取

1、教師評(píng)價(jià)優(yōu)+良+中+及格+不及格+教師簽名日期2014.優(yōu)良中及格不及格優(yōu)-良-中-及格-不及格-模式識(shí)別特征選擇與提取中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 電子信息科學(xué)系班級(jí)：信科11-1班，學(xué)號(hào)：08113545，姓名：褚鈺博聯(lián)系方法（QQ或手機(jī)）：390345438，e-mail:日期：2014 年 06月 10日摘要實(shí)際問(wèn)題中常常需要維數(shù)約簡(jiǎn)，如人臉識(shí)別、圖像檢索等。而特征選擇和特征提取是兩種最常用的維數(shù)約簡(jiǎn)方法。特征選擇是從某些事物中提取出本質(zhì)性的功能、應(yīng)用、優(yōu)勢(shì)等，而特征提取是對(duì)特征空間進(jìn)行變換，將原始特征空間映射到低維空間中。本文是對(duì)主成分分析和線性判別分析。關(guān)鍵詞：特征選擇，特征

2、提取，主成分分析，線性判別分析1.引言 模式識(shí)別的主要任務(wù)是利用從樣本中提取的特征，并將樣本劃分為相應(yīng)的模式類別，獲得好的分類性能。而分類方法與分類器設(shè)計(jì)，都是在d（變量統(tǒng)一用斜體）維特征空間已經(jīng)確定的前提下進(jìn)行的。因此討論的分類器設(shè)計(jì)問(wèn)題是一個(gè)選擇什么準(zhǔn)則、使用什么方法,將已確定的d維特征空間劃分成決策域的問(wèn)題。對(duì)分類器設(shè)計(jì)方法的研究固然重要，但如何確定合適的特征空間是設(shè)計(jì)模式識(shí)別系統(tǒng)另一個(gè)十分重要，甚至更為關(guān)鍵的問(wèn)題。如果所選用的特征空間能使同類物體分布具有緊致性，即各類樣本能分布在該特征空間中彼此分割開(kāi)的區(qū)域內(nèi)，這就為分類器設(shè)計(jì)成功提供良好的基礎(chǔ)。反之，如果不同類別的樣本在該特征空間中混

3、雜在一起，再好的設(shè)計(jì)方法也無(wú)法提高分類器的準(zhǔn)確性。本文要討論的問(wèn)題就是特征空間如何設(shè)計(jì)的問(wèn)題。 基于主成分分析的特征選擇算法的思想是建立在這樣的基礎(chǔ)上的：主成分分析方法將原始特征通過(guò)線性變換映射到新的低維空間時(shí)，獲得的主成分是去了新的物理意義，難以理解，并且主成分是所有原始特征的線性組合。所以將主成分分析與特征選擇相結(jié)合，設(shè)計(jì)多種相似性度量準(zhǔn)則，通過(guò)找到與主成分相關(guān)的關(guān)鍵特征或者刪除冗余、不相關(guān)以及沒(méi)有意義的特征，將主成分又重新映射到原始空間，來(lái)理解成主成分的實(shí)際意義。 基于線性判別分析的高維特征選擇將單個(gè)特征的Fisher準(zhǔn)則與其他特征選擇算法相結(jié)合，分層消除不相關(guān)特征與冗余特征。不相關(guān)特征

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

5、據(jù)研究很多下面幾種常用的判據(jù)，我們需要根據(jù)實(shí)際問(wèn)題，從中選擇出一種。一般來(lái)說(shuō)，我們希望可分性判據(jù)滿足以下幾個(gè)條件：1. 與識(shí)別的錯(cuò)誤率由直接的聯(lián)系，當(dāng)判據(jù)取最大值時(shí)，識(shí)別的錯(cuò)誤率最小；2. 當(dāng)特征獨(dú)立時(shí)有可加性，即：是第類和第類的可分性判據(jù)，越大，兩類的可分程度越大，為維特征；3. 應(yīng)具有某種距離的特點(diǎn)：，當(dāng)時(shí)；，當(dāng)時(shí)；4. 單調(diào)性，加入新的特征后，判據(jù)不減?。?。但是遺憾的是現(xiàn)在所經(jīng)常使用的各種判據(jù)很難滿足上述全部條件，只能滿足一個(gè)或幾個(gè)條件。特征提取又稱為特征變換，最常采用的特征變換是線性變換，即若是D維原始特征，變換后的d維新特征為 ， 其中，W是維矩陣，稱作變換陣。特征提取就是根據(jù)訓(xùn)練樣

6、本求適當(dāng)?shù)腤，使得某種特征變換準(zhǔn)則最優(yōu)。主成分分析方法的出發(fā)點(diǎn)是從一組特征中計(jì)算出一組按重要性從大到小排序的新特征，他們是原有特征的線性組合，并且相互之間是不相關(guān)的。記為p個(gè)原始特征，設(shè)新特征，i=1,，p是這些原始特征的線性組合 ， 為了統(tǒng)一的尺度，要求線性組合的模為1，即 ， 寫(xiě)成矩陣形式是 ， 其中，是由新特征組成的向量，A是特征變換矩陣。要求解的是最優(yōu)的正交變換A，它使新特征的方差達(dá)到極值。3.理論證明或說(shuō)明特征選擇的基本框圖為:子集產(chǎn)生子集產(chǎn)生原始特征集子集 終止條件否子集產(chǎn)生是一個(gè)典型的特征選擇算法通常包括四個(gè)人基本步驟:1. 子集產(chǎn)生，這是一個(gè)搜索過(guò)程，通過(guò)一定的搜索策略產(chǎn)生候選

7、的特征子集。2. 子集評(píng)價(jià)，每一個(gè)候選的特征子集都根據(jù)一定的評(píng)價(jià)準(zhǔn)則得到，并與先前的最優(yōu)特征子集進(jìn)行比較。3. 終止條件，算法結(jié)束所需要滿足的條件，它與子集的產(chǎn)生過(guò)程和評(píng)價(jià)準(zhǔn)則的選用有關(guān)。4. 結(jié)果驗(yàn)證，就是根據(jù)一定的先驗(yàn)知識(shí)或通過(guò)合成現(xiàn)實(shí)數(shù)據(jù)集的測(cè)試來(lái)證明所選擇的特征子集的性能?；谔卣魈崛≈鞒煞址治鲎儞Q矩陣的一般過(guò)程： 訓(xùn)練數(shù)據(jù)全集PCA處理變換矩陣分析 生成變換矩陣輸出特征子集4.實(shí)現(xiàn)方法或步驟流程特征選擇順序前進(jìn)法每次從未入選的特征中選擇一個(gè)特征，使得它與已入選的特征組合到一起所得到的可分性判據(jù)最大，直到特征數(shù)增加到為止。用表示在第步時(shí)的特征集合，搜索算法如下：1) 開(kāi)始時(shí)，從個(gè)特征中

8、選擇一個(gè)最大的特征，加入已選特征集，；2) 在第步，中包含已經(jīng)選擇的個(gè)特征，對(duì)未入選的個(gè)特征計(jì)算，其中，并且按照由大到小排序，將可分性判據(jù)最大的特征加入，；3) 直到所選的特征數(shù)等于為止。特征抽取的方法基于離散K-L變換(DKLT)的特征抽?。涸O(shè)原始特征為為矢量，均值矢量，相關(guān)矩陣，協(xié)方差矩陣。我們可以對(duì)作如下的標(biāo)準(zhǔn)正交變換，將其變?yōu)槭噶?的每個(gè)分量：，其中為一個(gè)的標(biāo)準(zhǔn)正交矩陣，為其第個(gè)列矢量，。也就是說(shuō)的每個(gè)分量是每一個(gè)分量的線性組合。同樣可以表示為：我們要進(jìn)行特征提取，也就是要用的項(xiàng)來(lái)代替，這種代替必然帶來(lái)誤差，下面我們來(lái)對(duì)這個(gè)誤差進(jìn)行估計(jì)：令：，引入的均方誤差為：這又變成一個(gè)優(yōu)化問(wèn)題，我

9、們希望尋找到一個(gè)標(biāo)準(zhǔn)正交矩陣，使得最小，因此可以去這樣的準(zhǔn)則函數(shù)：第一項(xiàng)保證均方誤差最小，第二項(xiàng)保證為標(biāo)準(zhǔn)正交矩陣，為一待定常數(shù)。，即：，很明顯為相關(guān)矩陣的特征值，為對(duì)應(yīng)于的特征矢量，由于是一個(gè)實(shí)對(duì)稱矩陣，所以相互正交，為一個(gè)正交矩陣。均方無(wú)差：根據(jù)矩陣論，有這樣的結(jié)論：一個(gè)的正定實(shí)對(duì)稱矩陣有個(gè)特征值和特征矢量，這些特征矢量之間是正交的。相關(guān)矩陣就是一個(gè)實(shí)對(duì)稱矩陣，當(dāng)訓(xùn)練樣本足夠多時(shí)，也可以滿足正定性，根據(jù)上式我們知道，當(dāng)要從維特征中提取出維特征時(shí)，我們只需要統(tǒng)計(jì)出特征相關(guān)矩陣，然后計(jì)算其特征值和特征矢量，選擇對(duì)應(yīng)特征值最大的前個(gè)特征矢量作成一個(gè)特征變換矩陣，就可以完成特征提取。步驟如下：1、

10、 利用訓(xùn)練樣本集合估計(jì)出相關(guān)矩陣；2、 計(jì)算的特征值，并由大到小排序：，以及相應(yīng)的特征矢量：；3、 選擇前個(gè)特征矢量作成一個(gè)變換矩陣；4、 在訓(xùn)練和識(shí)別時(shí)，每一個(gè)輸入的維特征矢量可以轉(zhuǎn)換為維的新特征矢量：。這種方法是利用相關(guān)矩陣進(jìn)行變換，同樣也可以利用協(xié)方差矩陣進(jìn)行變換，還可以利用樣本的散度矩陣，或者進(jìn)行變換。過(guò)程都是一樣的，需要計(jì)算特征值和特征向量，選擇最大的個(gè)特征值對(duì)應(yīng)的特征矢量作出變換矩陣。5.實(shí)驗(yàn)設(shè)計(jì)和結(jié)果分析 基于特征相關(guān)性的特征選擇算法選擇c均值聚類算法來(lái)去除冗余。 C均值算法的基本思想即是通過(guò)迭代尋找c個(gè)聚類的一種劃分方案，使得用這c個(gè)聚類的均值來(lái)代表相應(yīng)各類樣本時(shí)所得到的總體誤

11、差最小。 C均值算法的基礎(chǔ)是最小誤差平方和準(zhǔn)則。若是第i聚類中的樣本數(shù)目，是這些樣本的均值，即 把中的各樣本y與均值間的誤差平方和對(duì)所有類相加后為是誤差平方和聚類準(zhǔn)則，它是樣本集和類別集的函數(shù)。 C均值算法的步驟：1.選擇初始劃分，并計(jì)算每個(gè)聚類的均值以及誤差平方和；2.選擇一個(gè)備選樣本y，設(shè)y； 3.若樣本數(shù)目為1，則轉(zhuǎn)2，否則繼續(xù)； 4.計(jì)算：ji時(shí)，； j=i時(shí)， ；5. 考查中的最小者，若，則把y從移到中； 6.重新計(jì)算聚類i和k的均值，并修改誤差平方和；7.若多次迭代后誤差平方和不變，則停止，否則轉(zhuǎn)到步驟2。1.無(wú)論在聚類時(shí)，初始均值如何選取，在程序結(jié)果中總能得到相同的分類結(jié)果，同時(shí)

12、的結(jié)果相差很小。 2當(dāng)各聚類設(shè)定的初始均值不同時(shí)，程序結(jié)果經(jīng)過(guò)的步驟不同。3.是隨著聚類數(shù)目的增加而單調(diào)的減少的，當(dāng)聚類數(shù)目等于樣本數(shù)時(shí)=0，即每個(gè)樣本自己成一類。4.此算法是個(gè)局部搜索算法，并不能保證收斂到全局最優(yōu)解，即不能保證找到所有可能的聚類劃分中誤差平方和最小的解。算法的結(jié)果受到初始劃分和樣本調(diào)整順序的影響。6. 結(jié)論模式識(shí)別技術(shù)是人工智能的基礎(chǔ)技術(shù)，21世紀(jì)是智能化、信息化、計(jì)算花、網(wǎng)絡(luò)化的世紀(jì)，在這個(gè)以數(shù)字計(jì)算為特征的世紀(jì)里，模式識(shí)別技術(shù)將會(huì)獲得巨大的發(fā)展空間。特征選擇作為數(shù)據(jù)預(yù)處理的一個(gè)必要步驟，是模式識(shí)別中的一個(gè)關(guān)鍵問(wèn)題。一個(gè)模式識(shí)別系統(tǒng)的成敗，首先取決于所利用的特征

13、是否較好的反映了將要研究的分類問(wèn)題。而且高維數(shù)據(jù)是特征選擇的一個(gè)挑戰(zhàn)，研究人員總是努力的尋找著各種方法來(lái)盡量提高特征選擇的性能。對(duì)于特征選擇與特征提取，還有許多問(wèn)題期待解決：高維數(shù)據(jù)的特征選擇，特別是訓(xùn)練樣本較少而特征維數(shù)極高的數(shù)據(jù)集；在樣本的類別數(shù)未知的情況下，設(shè)計(jì)時(shí)間復(fù)雜度較低的非監(jiān)督的特征選擇；如何在進(jìn)行特征選擇時(shí)，選擇有意義的訓(xùn)練樣本；將維數(shù)約簡(jiǎn)與距離度量學(xué)習(xí)相結(jié)合；隨著特征選擇的應(yīng)用領(lǐng)域不斷擴(kuò)大，當(dāng)出現(xiàn)新的非線性相關(guān)的數(shù)據(jù)類型時(shí)，如何設(shè)計(jì)新的特征選擇算法；將特征選擇算法應(yīng)用于人臉識(shí)別與人臉檢測(cè)中，消除傳統(tǒng)人臉識(shí)別方法如PCA和LDA固有的局限性。模式識(shí)別是一門理論與實(shí)踐緊密結(jié)合的學(xué)科

14、，教與學(xué)的方式值得我們研究和探索。還可以看出模式識(shí)別具有相當(dāng)大的前景，而且模式識(shí)別的應(yīng)用得到越來(lái)越多的人的支持，而且它的成效也十分顯著。因此它也得到各國(guó)的重視，正因各個(gè)單位集體對(duì)人工智能的模式識(shí)別給予相關(guān)的重視，模式識(shí)別技術(shù)在現(xiàn)今社會(huì)也能快速發(fā)展。當(dāng)然，現(xiàn)在的模式識(shí)別還不算真正完整，不過(guò)人類科技的技術(shù)是不斷發(fā)展的，相信總有一天人工智能中的模式識(shí)別會(huì)真正融入我們的社會(huì)，成為我們?nèi)祟惒豢苫蛉钡囊徊糠?。而設(shè)計(jì)具體的、專業(yè)的、高效的特征選擇算法是一個(gè)值得重視值得探索的研究方向。7.參考文獻(xiàn)：1 張學(xué)工.模式識(shí)別（第三版).北京：清華大學(xué)出版社，20102 朱明，王俊普，蔡慶生.一種最優(yōu)特征集的選擇算法，計(jì)算機(jī)研究與發(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,Feat