第八章特征選擇與特征提取[2014]

1、模模式識別式識別Pattern Classification第八章第八章:特征選擇與特征提取特征選擇與特征提取模式識別，第八章3引言引言特征是決定樣本之間的相似性和分類器設(shè)計的關(guān)鍵如何找到合適的特征是模式識別的核心問題在實際問題中, 常常不容易找到那些最重要的特征 或者受條件限制不能對它們進(jìn)行測量, 這使得特征選擇和提取的任務(wù)復(fù)雜化 特征選擇成為構(gòu)造模式識別系統(tǒng)、提高決策精度的最困難的任務(wù)之一模式識別，第八章4引言引言模式三大基本特征：物理、結(jié)構(gòu)和數(shù)字特征物理和結(jié)構(gòu)特征：易于為人的直覺感知，但有時難于定量描述，因而不易用于機(jī)器判別數(shù)字特征：易于用機(jī)器定量描述和判別，如基于統(tǒng)計的特征模式識別，第

2、八章5引言引言一般情況下普遍認(rèn)為，增加特征向量的維數(shù)（增加特征數(shù)）將有助于提高分類器的質(zhì)量但實際應(yīng)用中特征維數(shù)卻收到多方面因素的約束和限制用較多的特征進(jìn)行分類器設(shè)計，無論從計算的復(fù)雜程度還是就分類器性能來看都是不適宜的 模式識別，第八章6特征的形成特征形成特征形成 (acquisition)：信號采集信號采集原始測量原始測量原始特征原始特征實例實例數(shù)字圖像中的各像素灰度值數(shù)字圖像中的各像素灰度值人體的各種生理指標(biāo)人體的各種生理指標(biāo)語音的音調(diào)周期、共振峰、聲道參數(shù)、頻譜語音的音調(diào)周期、共振峰、聲道參數(shù)、頻譜模式識別，第八章7特征的形成高維原始特征不利于分類器設(shè)計高維原始特征不利于分類器設(shè)計計算量

3、大計算量大信息冗余信息冗余模式識別，第八章8特征選擇與提取分析原始特征的有效性，選出最有代表性的特征是模式識別的關(guān)鍵一步降低特征維數(shù)在很多情況下是有效設(shè)計分類器的重要課題模式識別，第八章9特征選擇與提取兩類獲取有效特征信息、壓縮特征空間的方法：特征提取和特征選擇基本任務(wù)是如何從原始特征中獲取最有效的信息模式識別，第八章10特征選擇與提取特征選擇(selection) 從原始特征中挑選出一些最有代表性，分類性能最好的特征特征提取(extraction)通過映射或變換的方法把高維的原始特征變換為低維的新特征，新的特征包含了原有特征的有用信息模式識別，第八章11特征選擇與提取目前，還沒有特征選擇和提

4、取的一般方法，這是由于特征選擇一般是面向問題的，很難對這些方法去作評價和比較 特征選擇與提取是模式識別中重要而困難的一個環(huán)節(jié)模式識別，第八章12特征選擇與提取細(xì)胞自動識別原始測量 正常或異常細(xì)胞的數(shù)字圖像原始特征 找到一組代表細(xì)胞性質(zhì)的特征：細(xì)胞面積，胞核面積，形狀系數(shù)，光密度，核內(nèi)紋理，和漿比 原始特征的維數(shù)仍很高，需壓縮以便于分類！模式識別，第八章13特征選擇與提取細(xì)胞自動識別特征選擇 挑選最有分類信息的特征特征提取 數(shù)學(xué)變換：傅立葉變換或小波變換、特征壓縮模式識別，第八章14特征選擇特征選擇特征選擇的任務(wù)是從一組數(shù)量為D的特征中選擇出數(shù)量為d(D d)的一組最優(yōu)特征各個特征之間存在復(fù)雜的

5、相互關(guān)系 如果僅對每個單獨的特征按照一定的統(tǒng)計進(jìn)行排隊, 取排在前面的d個特征 所得結(jié)果在大多數(shù)情況下不是最優(yōu)特征組模式識別，第八章15特征選擇特征選擇從D個特征中選擇出d個最優(yōu)的特征, 在這兩個參數(shù)都已知的狀況下, 所有可能的組合數(shù)為如果D=100， d=10， 則的Q數(shù)量級是1013模式識別，第八章16特征選擇特征選擇在實際問題的研究過程當(dāng)中，D的維數(shù)往往遠(yuǎn)遠(yuǎn)高于100例如, 在利用生物芯片來進(jìn)行藥物設(shè)計和癌癥診斷時, 其產(chǎn)生的有效特征維數(shù)往往在10000左右實際需要選取的優(yōu)化特征組的特征數(shù)量是未知的尋找可行的特征選擇算法已逐漸成為國際上研究的熱點模式識別，第八章17特征選擇特征選擇一般來

6、看，特征選擇（確定優(yōu)化的特征子集）需要兩個主要步驟確定評價準(zhǔn)則來評價所選擇的特征子集的性能確定進(jìn)行特征搜索所需要的策略模式識別，第八章18特征選擇特征選擇按搜索策略劃分的特征選擇算法全局最優(yōu)搜索策略 “分支定界” 算法：該方法能保證在事先確定優(yōu)化特征子集中特征數(shù)目的情況下, 找到相對于所設(shè)計的可分性判據(jù)而言的最優(yōu)特征子集。 如何事先確定優(yōu)化特征子集當(dāng)中特征的數(shù)目？ 當(dāng)處理高維度多類問題時，算法運算效率低下模式識別，第八章19特征選擇特征選擇按搜索策略劃分的特征選擇算法隨機(jī)搜索策略 將特征選擇視為組合優(yōu)化問題，采用非全局最優(yōu)搜索方法 把特征選擇問題和模擬退火算法、禁忌搜索算法、遺傳算法、或隨機(jī)重

7、采樣過程結(jié)合, 以概率推理和采樣過程作為算法基礎(chǔ) 遺傳算法在這一領(lǐng)域的應(yīng)用最為廣泛模式識別，第八章20特征選擇特征選擇按搜索策略劃分的特征選擇算法啟發(fā)式搜索策略 單獨最優(yōu)特征組合算法 序列前向選擇算法 序列后向選擇算法 浮動搜索算法模式識別，第八章21特征選擇特征選擇特征選擇的原則選擇反映模式本質(zhì)特性的參數(shù)作為特征使樣本類間距離較大、類內(nèi)距離較小與類別信息不相關(guān)的變換（平移、旋轉(zhuǎn)、尺度變換）具有不變性盡量選擇相關(guān)性小的特征盡可能不受噪聲的干擾模式識別，第八章22基于主成份的特征提取：K-L變換K-L變換(Karhunen-Loeve Transform,卡洛南-洛伊變換)是將高維特征向量映射為

8、低維特征向量的有效方法目的： 提取出空間原始數(shù)據(jù)的主要特征(主元或主成份)，減少數(shù)據(jù)冗余，使得數(shù)據(jù)在一個低維的特征空間被處理，同時保持原始數(shù)據(jù)的絕大部份有用信息，從而解決數(shù)據(jù)維度過高的瓶頸問題。方法：將 維特征向量 ，通過特征變換得到另一 維特征向量特征向量 ，使得 與原向量 的均方誤差最小 模式識別，第八章23nXm)(nmYYX模式識別，第八章24K-L變換設(shè) 為 維特征向量，即： 現(xiàn)在 維特征空間中選取一組新的正交基底向量 即： XnTnxxxX, 21nn,21 ji 0ji 1jTi模式識別，第八章25K-L變換將 在該基底向量上進(jìn)行投影得到新向量 ，即 則向量 可表示為：XYXyy

9、yyYTiiTn： ,21其中niiiYyX1 X1模式識別，第八章26K-L變換X原空間原空間Y新空間新空間y1y2x1x2TyyY21,TxxX21,2211yyX2模式識別，第八章27K-L變換可見不同的基底向量 ，將 投影后可產(chǎn)生不同的向量現(xiàn)要尋求一組有效的基底向量，實現(xiàn)特征壓縮的目的 Yn,21X模式識別，第八章28K-L變換考慮： TnmmTnyyyyyyyyY, ,12121模式識別，第八章29K-L變換 將 中 以后各項用常數(shù) 代替得：Y)(mnibTnmmbbyyyY,121模式識別，第八章30K-L變換 定義誤差向量nmiiimiiibyX11nmiiiibyXXX1)(模

10、式識別，第八章31K-L變換X原空間原空間y新空間新空間yX模式識別，第八章32K-L變換則平方誤差為nmjjjjnmiTiiiTbybyXXX112)()(模式識別，第八章33K-L變換由于則有 ji 0ji 1jTinmiiibyX122)(模式識別，第八章34K-L變換若現(xiàn)有一批樣本，則均方誤差為： 可見，均方誤差與基底向量 和 有關(guān) 211222)()(inmiTinmiiibXEbyEXE iib模式識別，第八章35K-L變換如何選擇 和 ，使得均方誤差 最??？為什么要這樣做？ iib2模式識別，第八章36K-L變換首先考慮若 確定，如何選擇 ？ 令 即 iib0)(212inmiT

11、iiibXEbbnmiiTibXE102模式識別，第八章37K-L變換則有 XEbbXETiiiTi 0模式識別，第八章38K-L變換再考慮當(dāng) 用最佳值 代替后， 如何確定？ XETiib i模式識別，第八章39K-L變換 確定后，均方誤差 nmiTiTiXEXE12)(ibnmiiTibXE122)(模式識別，第八章40K-L變換即：nmiiTi12 nmiiTTiXEXXEXE12 )(協(xié)方差矩陣協(xié)方差矩陣經(jīng)典數(shù)學(xué)問題經(jīng)典數(shù)學(xué)問題模式識別，第八章41K-L變換結(jié)論：使均方誤差 最小的基底向量 ，即是協(xié)方差矩陣 的本征向量 如何求本征向量？2 i模式識別，第八章42K-L變換本征值協(xié)方差矩陣

12、 的本征值，即滿足 的 值共有i 個本征值0I單位矩陣單位矩陣n,321模式識別，第八章43K-L變換本征向量滿足方程 的向量共有i 個本征向量iiiin,321模式識別，第八章44K-L變換當(dāng) 為協(xié)方差矩陣 的本征向量時，均方誤差可見應(yīng)保留本征值較大的本征向量為基底向量！為什么？nmii12i模式識別，第八章45K-L變換總結(jié)：將 壓縮到 將產(chǎn)生誤差 壓縮維數(shù)越多 將越大，即丟失的信息越多。 TnyyyY,21TmyyyY,21nmii122模式識別，第八章46K-L變換為了有效減少 ，應(yīng)在壓縮時，保留本征較大的本征向量為基底向量，即排序而選擇本征值較大的m個本征向量為基底向量壓縮后的特征向

13、量為 2n321TmyyyY,21模式識別，第八章47K-L變換而稱為X的m個主成份XyTii模式識別，第八章48K-L變換K-L變換進(jìn)行特征維數(shù)壓縮的過程：獲取一批學(xué)習(xí)樣本 計算其均值 計算其協(xié)方差矩陣計算協(xié)方差矩陣的n個本征值 XE TXEXXEXE)(i模式識別，第八章49K-L變換將 由大到小排序值為 計算本征值對應(yīng)的本征向量 ，即 根據(jù)具體要求將特征向量降為m維向量 in321iiiini, 2 , 1TmyyyY,21XyTii模式識別，第八章50K-L變換例：設(shè)已知樣本的特征向量為：試用K-L變換將X壓縮為一維的4個樣本，并求出均方誤差 22,11,22,114321XXXX2模式識別，第八章51K-L變換X2X3X4X1模式識別，第八章52K-L變換解： 求出樣本均值 （期望值） 04141iiXXE模式識別，第八章53K-L變換求協(xié)方差矩陣 TXEXXEXE)(4141iTiiXX2.5 2.52.5 2.5