特征的選擇與提取武漢大學(xué),王文偉老師課件

模式識(shí)別導(dǎo)論

PatternRecognition第六章特征的選擇與提取WangWenwei,Dr.-Ing.Tel:687-78652Email:Web:IPLTableofContents電子信息學(xué)院6.1

基本概念特征的選擇與提取是模式識(shí)別中重要而困難的一個(gè)環(huán)節(jié)：分析各種特征的有效性并選出最有代表性的特征是模式識(shí)別的關(guān)鍵一步。降低特征維數(shù)在很多情況下是有效設(shè)計(jì)分類器的重要課題。三大類特征：物理、結(jié)構(gòu)和數(shù)學(xué)特征物理和結(jié)構(gòu)特征：易于為人的直覺(jué)感知，但有時(shí)難于定量描述，因而不易用于機(jī)器判別。數(shù)學(xué)特征：易于用機(jī)器定量描述和判別，如基于統(tǒng)計(jì)的特征。引言特征的選擇與提取兩類提取有效信息、壓縮特征空間的方法：特征提取和特征選擇特征提取

(extraction)：用映射（或變換）的方法把原始特征變換為較少的新特征。特征選擇(selection)

：從原始特征中挑選出一些最有代表性，分類性能最好的特征。特征的選擇與提取與具體問(wèn)題有很大關(guān)系，目前沒(méi)有理論能給出對(duì)任何問(wèn)題都有效的特征選擇與提取方法。引言特征的選擇與提取舉例細(xì)胞自動(dòng)識(shí)別：原始測(cè)量：（正常與異常）細(xì)胞的數(shù)字圖像原始特征（特征的形成，找到一組代表細(xì)胞性質(zhì)的特征）：細(xì)胞面積，胞核面積，形狀系數(shù)，光密度，核內(nèi)紋理，核漿比壓縮特征：原始特征的維數(shù)仍很高，需壓縮以便于分類特征選擇：挑選最有分類信息的特征特征提?。簲?shù)學(xué)變換傅立葉變換或小波變換用PCA方法作特征壓縮引言6.2類別可分離性判據(jù)類別可分離性判據(jù)：衡量不同特征及其組合對(duì)分類是否有效的定量準(zhǔn)則理想準(zhǔn)則：某組特征使分類器錯(cuò)誤概率最小實(shí)際的類別可分離性判據(jù)應(yīng)滿足的條件：度量特性：與錯(cuò)誤率有單調(diào)關(guān)系當(dāng)特征獨(dú)立時(shí)有可加性：?jiǎn)握{(diào)性：常見(jiàn)類別可分離性判據(jù)：基于距離、概率分布、熵函數(shù)基于距離的可分性判據(jù)矩陣形式基于距離的準(zhǔn)則概念直觀，計(jì)算方便，但與錯(cuò)誤率沒(méi)有直接聯(lián)系樣本類間

離散度矩陣樣本類內(nèi)

離散度矩陣類間可分離性判據(jù)可分性判據(jù)基于概率的可分性判據(jù)基于概率的可分性判據(jù)：用概率密度函數(shù)間的距離來(lái)度量散度：正態(tài)分布：Mahalanobis可分性判據(jù)基于熵函數(shù)的可分性判據(jù)熵函數(shù)：Shannon熵：平方熵：熵函數(shù)期望表征類別的分離程度：可分性判據(jù)Otsuthresholding灰度圖像閾值:Otsu灰度圖像二值化算法演示及程序分析:可分性判據(jù)6.3特征提取與K-L變換特征提?。河糜成洌ɑ蜃儞Q）的方法把原始特征變換為較少的新特征PCA(PrincipleComponentAnalysis)方法：

進(jìn)行特征降維變換，不能完全地表示原有的對(duì)象，能量總會(huì)有損失。希望找到一種能量最為集中的的變換方法使損失最小。K-L(Karhunen-Loeve)變換：最優(yōu)正交線性變換，相應(yīng)的特征提取方法被稱為PCA方法K-L變換離散K-L變換：對(duì)向量x用確定的完備正交歸一向量系uj展開特征

提取求解最小均方誤差正交基用Lagrange乘子法：結(jié)論：以相關(guān)矩陣R的d個(gè)本征向量為基向量來(lái)展開x時(shí)，其均方誤差為：K-L變換：當(dāng)取矩陣R的d個(gè)最大本征值對(duì)應(yīng)的本征向量來(lái)展開x時(shí)，其截?cái)嗑秸`差最小。這d個(gè)本征向量組成的正交坐標(biāo)系稱作x所在的D維空間的d維K-L變換坐標(biāo)系，x在K-L坐標(biāo)系上的展開系數(shù)向量y稱作x的K-L變換特征

提取K-L變換的表示K-L變換的向量展開表示：K-L變換的矩陣表示：特征

提取K-L變換的性質(zhì)y的相關(guān)矩陣是對(duì)角矩陣：特征

提取K-L變換圖解x1x2u2u1二次

曲線方程標(biāo)準(zhǔn)二次

曲線方程特征

提取K-L變換的數(shù)據(jù)壓縮圖解取2x1變換矩陣U=[u1]，則x的K-L變換y為：

y=UTx=u1Tx=y1變換的能量損失為特征

提取K-L變換的產(chǎn)生矩陣數(shù)據(jù)集KN={xi}的K-L變換的產(chǎn)生矩陣由數(shù)據(jù)的二階統(tǒng)計(jì)量決定，即K-L坐標(biāo)系的基向量為某種基于數(shù)據(jù)x的二階統(tǒng)計(jì)量的產(chǎn)生矩陣的本征向量K-L變換的產(chǎn)生矩陣可以有多種選擇：x的相關(guān)函數(shù)矩陣R=E[xxT]x的協(xié)方差矩陣C=E[(x-μ)(x-μ)T]樣本總類內(nèi)離散度矩陣：特征

提取特征選擇:=從原始特征中挑選出一些最有代表性、分類性能最好的特征進(jìn)行分類。從D個(gè)特征中選取d個(gè),共CdD種組合。若不限定特征選擇個(gè)數(shù)，則共2D種組合

－典型的組合優(yōu)化問(wèn)題特征選擇的方法大體可分兩大類：Filter方法：根據(jù)獨(dú)立于分類器的指標(biāo)J來(lái)評(píng)價(jià)所選擇的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作為最優(yōu)特征子集。不考慮所使用的學(xué)習(xí)算法。Wrapper方法：將特征選擇和分類器結(jié)合在一起，在學(xué)習(xí)過(guò)程中表現(xiàn)優(yōu)異的的特征子集會(huì)被選中。6.4特征的選擇經(jīng)典特征選擇算法許多特征選擇算法力求解決搜索問(wèn)題，經(jīng)典算法有：分支定界法:最優(yōu)搜索，效率比盲目窮舉法高。單獨(dú)最優(yōu)特征組合法：次優(yōu)搜索。順序后退法順序前進(jìn)法模擬退火法Tabu搜索法遺傳算法特征

選擇順序后退法該方法根據(jù)特征子集的分類表現(xiàn)來(lái)選擇特征搜索特征子集：從全體特征開始，每次剔除一個(gè)特征，使得所保留的特征集合有最大的分類識(shí)別率依次迭代，直至識(shí)別率開始下降為止用“l(fā)eave-one-out”方法估計(jì)平均識(shí)別率：用N-1個(gè)樣本判斷余下一個(gè)的類別，N次取平均特征

選擇模擬退火法來(lái)源于統(tǒng)計(jì)力學(xué)。材料粒子從高溫開始，非常緩慢地降溫(退火)，粒子就可在每個(gè)溫度下達(dá)到熱平衡。假設(shè)材料在狀態(tài)i的能量為E(i)，那么材料在溫度T時(shí)從狀態(tài)i進(jìn)入狀態(tài)j遵循如下規(guī)律：如果E(j)≤E(i)，接受該狀態(tài)被轉(zhuǎn)換。如果E(j)>E(i)，則狀態(tài)轉(zhuǎn)換以如下概率被接受：特征

選擇模擬退火法(II)在某一溫度下，進(jìn)行了充分轉(zhuǎn)換后，材料達(dá)到熱平衡，這時(shí)材料處于狀態(tài)i的概率滿足：所有狀態(tài)在高溫下具有相同概率。特征

選擇模擬退火法(III)當(dāng)溫度降至很低時(shí)，材料會(huì)以很大概率進(jìn)入最小能量狀態(tài)。模擬退火優(yōu)化法：f:x→R+，其中x∈S，表示優(yōu)化問(wèn)題的一個(gè)可行解。N(x)≤S表示x的一個(gè)鄰域集合。特征

選擇模擬退火法(IV)首先給定初始溫度T0和初始解x(0)，以概率P生成下一個(gè)新解x’：對(duì)于溫度Ti和該優(yōu)化問(wèn)題的解x(k)，可以生成新解x’。經(jīng)過(guò)多次轉(zhuǎn)換，降低溫度得到Ti+1<Ti。在Ti+1下重復(fù)上述過(guò)程，最終的解是對(duì)該問(wèn)題尋優(yōu)的結(jié)果。特征

選擇模擬退火法(V)經(jīng)過(guò)有限次轉(zhuǎn)換，在溫度Ti下的平衡態(tài)xi的分布為：當(dāng)溫度T降為0時(shí)，xi的分布為：特征

選擇特征選擇的模擬退火法Step1:令i=0,k=0,給出初始溫度T0和初始特征組合x(0)。Step2:在x(k)的鄰域N(x(k))中選擇一個(gè)狀態(tài)x’，即新特征組合。計(jì)算其可分性判據(jù)J(x’)，并按概率P接受x(k+1)=x’。Step3:如果在Ti下還未達(dá)到平衡，則轉(zhuǎn)到Step2。Step4:如果Ti已經(jīng)足夠低，則結(jié)束，當(dāng)時(shí)的特征組合即為算法的結(jié)果。否則繼續(xù)。Step5:根據(jù)溫度下降方法計(jì)算新的溫度Ti+1。轉(zhuǎn)到Step2。特征

選擇遺傳算法從生物進(jìn)化論得到啟迪。遺傳，變異，自然選擇。基因鏈碼：待解問(wèn)題的解的編碼，每個(gè)基因鏈碼也稱為一個(gè)個(gè)體。對(duì)于特征選擇，可用一個(gè)D位的0/1構(gòu)成的串表示一種特征組合。群體：若干個(gè)個(gè)體的集合，即問(wèn)題的一些解的集合。交叉：由當(dāng)前兩個(gè)個(gè)體的鏈碼交叉產(chǎn)生新一代的個(gè)體。變異：由一個(gè)鏈碼隨機(jī)某基因使其翻轉(zhuǎn)。特征

選擇遺傳算法適應(yīng)度：每個(gè)個(gè)體xi的函數(shù)值fi，個(gè)體xi越好，fi越大。新一代群體對(duì)環(huán)境的平均適應(yīng)度比父代高。遺傳算法的基本框架：Step1:令進(jìn)化代數(shù)t=0。Step2:給出初始化群體P(t)，令xg為任一個(gè)體。Step3:對(duì)P(t)中每個(gè)個(gè)體估值，并將群體中最優(yōu)解x’與xg比較，如果x’的性能優(yōu)于xg，則xg=x’Step4:如果終止條件滿足，則算法結(jié)束，xg為算法的結(jié)果。否則繼續(xù)。Step5:從P(t)中選擇個(gè)體并進(jìn)行交叉和變異操作，得到新一代群體P(t+1)。令t=t+1,轉(zhuǎn)到Step3。特征

選擇6.5

討論特征的選擇與提取是模式識(shí)別中重要而困難的一