第八章-特征選擇與特征提取課件

模式識(shí)別

PatternClassification

模式識(shí)別

PatternClassification

第八章:特征選擇與特征提取第八章:特征選擇與特征提取引言特征是決定樣本之間的相似性和分類器設(shè)計(jì)的關(guān)鍵如何找到合適的特征是模式識(shí)別的核心問題在實(shí)際問題中,常常不容易找到那些最重要的特征

或者受條件限制不能對(duì)它們進(jìn)行測(cè)量,這使得特征選擇和提取的任務(wù)復(fù)雜化

特征選擇成為構(gòu)造模式識(shí)別系統(tǒng)、提高決策精度的最困難的任務(wù)之一.3引言特征是決定樣本之間的相似性和分類器設(shè)計(jì)的關(guān)鍵.3引言模式三大基本特征：物理、結(jié)構(gòu)和數(shù)字特征物理和結(jié)構(gòu)特征：易于為人的直覺感知，但有時(shí)難于定量描述，因而不易用于機(jī)器判別數(shù)字特征：易于用機(jī)器定量描述和判別，如基于統(tǒng)計(jì)的特征.4引言模式三大基本特征：物理、結(jié)構(gòu)和數(shù)字特征.4引言一般情況下普遍認(rèn)為，增加特征向量的維數(shù)（增加特征數(shù)）將有助于提高分類器的質(zhì)量但實(shí)際應(yīng)用中特征維數(shù)卻收到多方面因素的約束和限制用較多的特征進(jìn)行分類器設(shè)計(jì)，無論從計(jì)算的復(fù)雜程度還是就分類器性能來看都是不適宜的

.5引言一般情況下普遍認(rèn)為，增加特征向量的維數(shù)（增加特征數(shù)）將有特征的形成特征形成(acquisition)：信號(hào)采集→原始測(cè)量→原始特征實(shí)例數(shù)字圖像中的各像素灰度值人體的各種生理指標(biāo)語音的音調(diào)周期、共振峰、聲道參數(shù)、頻譜.6特征的形成特征形成(acquisition)：.6特征的形成高維原始特征不利于分類器設(shè)計(jì)計(jì)算量大信息冗余.7特征的形成高維原始特征不利于分類器設(shè)計(jì).7特征選擇與提取分析原始特征的有效性，選出最有代表性的特征是模式識(shí)別的關(guān)鍵一步降低特征維數(shù)在很多情況下是有效設(shè)計(jì)分類器的重要課題.8特征選擇與提取分析原始特征的有效性，選出最有代表性的特征是模特征選擇與提取兩類獲取有效特征信息、壓縮特征空間的方法：特征提取和特征選擇基本任務(wù)是如何從原始特征中獲取最有效的信息.9特征選擇與提取兩類獲取有效特征信息、壓縮特征空間的方法：特征特征選擇與提取特征選擇(selection)

從原始特征中挑選出一些最有代表性，分類性能最好的特征特征提取(extraction)通過映射或變換的方法把高維的原始特征變換為低維的新特征，新的特征包含了原有特征的有用信息.10特征選擇與提取特征選擇(selection).10特征選擇與提取目前，還沒有特征選擇和提取的一般方法，這是由于特征選擇一般是面向問題的，很難對(duì)這些方法去作評(píng)價(jià)和比較

特征選擇與提取是模式識(shí)別中重要而困難的一個(gè)環(huán)節(jié).11特征選擇與提取目前，還沒有特征選擇和提取的一般方法，這是由于特征選擇與提取細(xì)胞自動(dòng)識(shí)別原始測(cè)量正?；虍惓＜?xì)胞的數(shù)字圖像原始特征找到一組代表細(xì)胞性質(zhì)的特征：細(xì)胞面積，胞核面積，形狀系數(shù)，光密度，核內(nèi)紋理，和漿比原始特征的維數(shù)仍很高，需壓縮以便于分類！.12特征選擇與提取細(xì)胞自動(dòng)識(shí)別.12特征選擇與提取細(xì)胞自動(dòng)識(shí)別特征選擇挑選最有分類信息的特征特征提取數(shù)學(xué)變換：傅立葉變換或小波變換、特征壓縮.13特征選擇與提取細(xì)胞自動(dòng)識(shí)別.13特征選擇特征選擇的任務(wù)是從一組數(shù)量為D的特征中選擇出數(shù)量為d(D>d)的一組最優(yōu)特征各個(gè)特征之間存在復(fù)雜的相互關(guān)系如果僅對(duì)每個(gè)單獨(dú)的特征按照一定的統(tǒng)計(jì)進(jìn)行排隊(duì),取排在前面的d個(gè)特征所得結(jié)果在大多數(shù)情況下不是最優(yōu)特征組.14特征選擇特征選擇的任務(wù)是從一組數(shù)量為D的特征中選擇出數(shù)量為d特征選擇從D個(gè)特征中選擇出d個(gè)最優(yōu)的特征,在這兩個(gè)參數(shù)都已知的狀況下,所有可能的組合數(shù)為如果D=100，d=10，則的Q數(shù)量級(jí)是1013.15特征選擇從D個(gè)特征中選擇出d個(gè)最優(yōu)的特征,在這兩個(gè)參數(shù)都已特征選擇在實(shí)際問題的研究過程當(dāng)中，D的維數(shù)往往遠(yuǎn)遠(yuǎn)高于100例如,在利用生物芯片來進(jìn)行藥物設(shè)計(jì)和癌癥診斷時(shí),其產(chǎn)生的有效特征維數(shù)往往在10000左右實(shí)際需要選取的優(yōu)化特征組的特征數(shù)量是未知的尋找可行的特征選擇算法已逐漸成為國際上研究的熱點(diǎn).16特征選擇在實(shí)際問題的研究過程當(dāng)中，D的維數(shù)往往遠(yuǎn)遠(yuǎn)高于100特征選擇一般來看，特征選擇（確定優(yōu)化的特征子集）需要兩個(gè)主要步驟確定評(píng)價(jià)準(zhǔn)則來評(píng)價(jià)所選擇的特征子集的性能確定進(jìn)行特征搜索所需要的策略.17特征選擇一般來看，特征選擇（確定優(yōu)化的特征子集）需要兩個(gè)主要特征選擇按搜索策略劃分的特征選擇算法全局最優(yōu)搜索策略

“分支定界”算法：該方法能保證在事先確定優(yōu)化特征子集中特征數(shù)目的情況下,找到相對(duì)于所設(shè)計(jì)的可分性判據(jù)而言的最優(yōu)特征子集。如何事先確定優(yōu)化特征子集當(dāng)中特征的數(shù)目？當(dāng)處理高維度多類問題時(shí)，算法運(yùn)算效率低下.18特征選擇按搜索策略劃分的特征選擇算法.18特征選擇按搜索策略劃分的特征選擇算法隨機(jī)搜索策略將特征選擇視為組合優(yōu)化問題，采用非全局最優(yōu)搜索方法把特征選擇問題和模擬退火算法、禁忌搜索算法、遺傳算法、或隨機(jī)重采樣過程結(jié)合,以概率推理和采樣過程作為算法基礎(chǔ)遺傳算法在這一領(lǐng)域的應(yīng)用最為廣泛.19特征選擇按搜索策略劃分的特征選擇算法.19特征選擇按搜索策略劃分的特征選擇算法啟發(fā)式搜索策略單獨(dú)最優(yōu)特征組合算法序列前向選擇算法序列后向選擇算法浮動(dòng)搜索算法.20特征選擇按搜索策略劃分的特征選擇算法.20特征選擇特征選擇的原則選擇反映模式本質(zhì)特性的參數(shù)作為特征使樣本類間距離較大、類內(nèi)距離較小與類別信息不相關(guān)的變換（平移、旋轉(zhuǎn)、尺度變換）具有不變性盡量選擇相關(guān)性小的特征盡可能不受噪聲的干擾.21特征選擇特征選擇的原則.21基于主成份的特征提?。篕-L變換K-L變換(Karhunen-LoeveTransform,卡洛南-洛伊變換)是將高維特征向量映射為低維特征向量的有效方法目的：

提取出空間原始數(shù)據(jù)的主要特征(主元或主成份)，減少數(shù)據(jù)冗余，使得數(shù)據(jù)在一個(gè)低維的特征空間被處理，同時(shí)保持原始數(shù)據(jù)的絕大部份有用信息，從而解決數(shù)據(jù)維度過高的瓶頸問題。.22基于主成份的特征提取：K-L變換K-L變換(Karhunen方法：將維特征向量，通過特征變換得到另一維特征向量特征向量，使得與原向量的均方誤差最小

.23方法：.23K-L變換設(shè)為維特征向量，即：現(xiàn)在維特征空間中選取一組新的正交基底向量即：

.24K-L變換設(shè)為維特征向量，即：.24K-L變換將在該基底向量上進(jìn)行投影得到新向量，即則向量可表示為：.25K-L變換將在該基底向量上進(jìn)行投影得到新向量，即K-L變換X原空間Y新空間y1y2x1x2.26K-L變換X原空間Y新空間y1y2x1x2.26K-L變換可見不同的基底向量，將投影后可產(chǎn)生不同的向量現(xiàn)要尋求一組有效的基底向量，實(shí)現(xiàn)特征壓縮的目的

.27K-L變換可見不同的基底向量，將K-L變換考慮：

.28K-L變換考慮：.28K-L變換

將中以后各項(xiàng)用常數(shù)代替得：.29K-L變換將中以后各項(xiàng)用常數(shù)代K-L變換定義誤差向量.30K-L變換.30K-L變換X原空間y新空間yX.31K-L變換X原空間y新空間yX.31K-L變換則平方誤差為.32K-L變換則平方誤差為.32K-L變換由于則有.33K-L變換由于.33K-L變換若現(xiàn)有一批樣本，則均方誤差為：可見，均方誤差與基底向量和有關(guān)

.34K-L變換若現(xiàn)有一批樣本，則均方誤差為：.34K-L變換如何選擇和，使得均方誤差最??？為什么要這樣做？.35K-L變換如何選擇和，使得均方誤差K-L變換首先考慮若確定，如何選擇？令即.36K-L變換首先考慮若確定，如何選擇？.36K-L變換則有.37K-L變換則有.37K-L變換再考慮當(dāng)用最佳值代替后，如何確定？

.38K-L變換再考慮當(dāng)用最佳值代替后，K-L變換確定后，均方誤差.39K-L變換確定后，均方誤差.39K-L變換即：協(xié)方差矩陣經(jīng)典數(shù)學(xué)問題.40K-L變換即：協(xié)方差矩陣經(jīng)典數(shù)學(xué)問題.40K-L變換結(jié)論：使均方誤差最小的基底向量，即是協(xié)方差矩陣的本征向量

如何求本征向量？.41K-L變換結(jié)論：.41K-L變換本征值協(xié)方差矩陣的本征值，即滿足的值共有i

個(gè)本征值單位矩陣.42K-L變換本征值單位矩陣.42K-L變換本征向量滿足方程的向量共有i

個(gè)本征向量.43K-L變換本征向量.43K-L變換當(dāng)為協(xié)方差矩陣的本征向量時(shí)，均方誤差可見應(yīng)保留本征值較大的本征向量為基底向量！為什么？ .44K-L變換當(dāng)為協(xié)方差矩陣的本征向K-L變換總結(jié)：將

壓縮到將產(chǎn)生誤差壓縮維數(shù)越多將越大，即丟失的信息越多。

.45K-L變換總結(jié)：.45K-L變換為了有效減少，應(yīng)在壓縮時(shí)，保留本征較大的本征向量為基底向量，即排序而選擇本征值較大的m個(gè)本征向量為基底向量壓縮后的特征向量為

.46K-L變換為了有效減少，應(yīng)在壓縮時(shí)，保留本征較大的本K-L變換而 稱為X的m個(gè)主成份.47K-L變換而.47K-L變換K-L變換進(jìn)行特征維數(shù)壓縮的過程：獲取一批學(xué)習(xí)樣本

計(jì)算其均值

計(jì)算其協(xié)方差矩陣計(jì)算協(xié)方差矩陣的n個(gè)本征值

.48K-L變換K-L變換進(jìn)行特征維數(shù)壓縮的過程：.48K-L變換將由大到小排序值為

計(jì)算本征值對(duì)應(yīng)的本征向量，即

根據(jù)具體要求將特征向量降為m維向量

.49K-L變換將由大到小排序值為.49K-L變換例：設(shè)已知樣本的特征向量為：試用K-L變換將X壓縮為一維的4個(gè)樣本，并求出均方誤差

.50K-L變換例：設(shè)已知樣本的特征向量為：.50K-L變換X2X3X4X1.51K-L變換X2X3X4X1.51K-L變換解：

求出樣本均值

（期望值）.52K-L變換解：.52K-L變換求協(xié)方差