模式識別導(dǎo)論

PatternRecognition第六章特征的選擇與提取王文偉WangWenwei,Dr.-Ing.Tel:687-78652Email:ang@Web:/sites/ced/pr/電子信息學(xué)院IPL特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第1頁!TableofContents6.1引言6.2類別可分離性判據(jù)6.3特征提取與K-L變換6.4特征的選擇6.5討論

電子信息學(xué)院特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第2頁!6.1

基本概念特征的選擇與提取是模式識別中重要而困難的一個環(huán)節(jié)：分析各種特征的有效性并選出最有代表性的特征是模式識別的關(guān)鍵一步。降低特征維數(shù)在很多情況下是有效設(shè)計分類器的重要課題。三大類特征：物理、結(jié)構(gòu)和數(shù)學(xué)特征物理和結(jié)構(gòu)特征：易于為人的直覺感知，但有時難于定量描述，因而不易用于機(jī)器判別。數(shù)學(xué)特征：易于用機(jī)器定量描述和判別，如基于統(tǒng)計的特征。引言特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第3頁!特征的形成特征形成

(acquisition)：信號獲取或測量→原始測量原始特征實(shí)例：數(shù)字圖象中的各像素灰度值人體的各種生理指標(biāo)原始特征分析：原始測量不能反映對象本質(zhì)高維原始特征不利于分類器設(shè)計：計算量大，冗余，樣本分布十分稀疏。引言特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第4頁!特征的選擇與提取舉例細(xì)胞自動識別：原始測量：（正常與異常）細(xì)胞的數(shù)字圖像原始特征（特征的形成，找到一組代表細(xì)胞性質(zhì)的特征）：細(xì)胞面積，胞核面積，形狀系數(shù)，光密度，核內(nèi)紋理，核漿比壓縮特征：原始特征的維數(shù)仍很高，需壓縮以便于分類特征選擇：挑選最有分類信息的特征特征提?。簲?shù)學(xué)變換傅立葉變換或小波變換用PCA方法作特征壓縮引言特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第5頁!基于距離的可分性判據(jù)類間可分性:=所有樣本間的平均距離：(8-1)squaredEuclidian(8-5)類內(nèi)平均距離類間

距離(8-6)可分性判據(jù)特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第6頁!基于概率的可分性判據(jù)基于概率的可分性判據(jù)：用概率密度函數(shù)間的距離來度量散度：正態(tài)分布：Mahalanobis可分性判據(jù)特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第7頁!類別可分離性判據(jù)應(yīng)用舉例圖像分割：Otsu灰度圖像閾值算法

(Otsuthresholding)圖像有L階灰度，ni是灰度為i的像素數(shù)，圖像總像素數(shù)N=n1+n2+…+nL灰度為i的像素概率：pi=ni/N類間方差：可分性判據(jù)特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第8頁!6.3特征提取與K-L變換特征提取：用映射（或變換）的方法把原始特征變換為較少的新特征PCA(PrincipleComponentAnalysis)方法：

進(jìn)行特征降維變換，不能完全地表示原有的對象，能量總會有損失。希望找到一種能量最為集中的的變換方法使損失最小。K-L(Karhunen-Loeve)變換：最優(yōu)正交線性變換，相應(yīng)的特征提取方法被稱為PCA方法特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第9頁!離散K-L變換的均方誤差用有限項(xiàng)估計x

：該估計的均方誤差：特征

提取特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第10頁!K-L變換的表示K-L變換的向量展開表示：K-L變換的矩陣表示：特征

提取特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第11頁!K-L變換的性質(zhì)K-L坐標(biāo)系把矩陣R對角化，即通過K-L變換消除原有向量x的各分量間的相關(guān)性，從而有可能去掉那些帶有較少信息的分量以達(dá)到降低特征維數(shù)的目的特征

提取特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第12頁!K-L變換的數(shù)據(jù)壓縮圖解取2x1變換矩陣U=[u1]，則x的K-L變換y為：

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

提取特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第13頁!未知類別樣本的K-L變換用總體樣本的協(xié)方差矩陣C=E[(x-μ)(x-μ)T]

進(jìn)行K-L變換，K-L坐標(biāo)系U=[u1,u2,...,ud]按照C的本征值的下降次序選擇例：設(shè)一樣本集的協(xié)方差矩陣是：

求最優(yōu)2x1特征提取器U

解答：計算特征值及特征向量[V,D]=eig(C);

特征值D=[24.736,2.263]T,特征向量:

由于λ1>λ2，故最優(yōu)2x1特征提取器

此時的K-L變換式為：特征

提取特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第14頁!經(jīng)典特征選擇算法許多特征選擇算法力求解決搜索問題，經(jīng)典算法有：分支定界法:最優(yōu)搜索，效率比盲目窮舉法高。單獨(dú)最優(yōu)特征組合法：次優(yōu)搜索。順序后退法順序前進(jìn)法模擬退火法Tabu搜索法遺傳算法特征

選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第15頁!順序前進(jìn)法自下而上搜索方法。每次從未入選的特征中選擇一個特征，使得它與已入選的特征組合在一起時所得的J值為最大，直至特征數(shù)增加到d為止。該方法考慮了所選特征與已入選特征之間的相關(guān)性。特征

選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第16頁!模擬退火法來源于統(tǒng)計力學(xué)。材料粒子從高溫開始，非常緩慢地降溫(退火)，粒子就可在每個溫度下達(dá)到熱平衡。假設(shè)材料在狀態(tài)i的能量為E(i)，那么材料在溫度T時從狀態(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)換以如下概率被接受：特征

選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第17頁!模擬退火法(III)當(dāng)溫度降至很低時，材料會以很大概率進(jìn)入最小能量狀態(tài)。模擬退火優(yōu)化法：f:x→R+，其中x∈S，表示優(yōu)化問題的一個可行解。N(x)≤S表示x的一個鄰域集合。特征

選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第18頁!模擬退火法(V)經(jīng)過有限次轉(zhuǎn)換，在溫度Ti下的平衡態(tài)xi的分布為：當(dāng)溫度T降為0時，xi的分布為：特征

選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第19頁!遺傳算法從生物進(jìn)化論得到啟迪。遺傳，變異，自然選擇?；蜴湸a：待解問題的解的編碼，每個基因鏈碼也稱為一個個體。對于特征選擇，可用一個D位的0/1構(gòu)成的串表示一種特征組合。群體：若干個個體的集合，即問題的一些解的集合。交叉：由當(dāng)前兩個個體的鏈碼交叉產(chǎn)生新一代的個體。變異：由一個鏈碼隨機(jī)某基因使其翻轉(zhuǎn)。特征

選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第20頁!6.5

討論特征的選擇與提取是模式識別中重要而困難的一步模式識別的步：分析各種特征的有效性并選出最有代表性的特征降低特征維數(shù)在很多情況下是有效設(shè)計分類器的重要課題三大類特征：物理、結(jié)構(gòu)和數(shù)學(xué)特征物理和結(jié)構(gòu)特征：易于為人的直覺感知，但難于定量描述，因而不易用機(jī)器判別數(shù)學(xué)特征：易于用機(jī)器定量描述和判別特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第21頁!特征的選擇與提取兩類提取有效信息、壓縮特征空間的方法：特征提取和特征選擇特征提取

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

：從原始特征中挑選出一些最有代表性，分類性能最好的特征。特征的選擇與提取與具體問題有很大關(guān)系，目前沒有理論能給出對任何問題都有效的特征選擇與提取方法。引言特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第22頁!6.2類別可分離性判據(jù)類別可分離性判據(jù)：衡量不同特征及其組合對分類是否有效的定量準(zhǔn)則理想準(zhǔn)則：某組特征使分類器錯誤概率最小實(shí)際的類別可分離性判據(jù)應(yīng)滿足的條件：度量特性：與錯誤率有單調(diào)關(guān)系當(dāng)特征獨(dú)立時有可加性：單調(diào)性：常見類別可分離性判據(jù)：基于距離、概率分布、熵函數(shù)特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第23頁!基于距離的可分性判據(jù)矩陣形式基于距離的準(zhǔn)則概念直觀，計算方便，但與錯誤率沒有直接聯(lián)系樣本類間

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

離散度矩陣類間可分離性判據(jù)可分性判據(jù)特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第24頁!基于熵函數(shù)的可分性判據(jù)熵函數(shù)：Shannon熵：平方熵：熵函數(shù)期望表征類別的分離程度：可分性判據(jù)特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第25頁!Otsuthresholding灰度圖像閾值:Otsu灰度圖像二值化算法演示及程序分析:可分性判據(jù)特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第26頁!K-L變換離散K-L變換：對向量x用確定的完備正交歸一向量系uj展開特征

提取特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第27頁!求解最小均方誤差正交基用Lagrange乘子法：結(jié)論：以相關(guān)矩陣R的d個本征向量為基向量來展開x時，其均方誤差為：K-L變換：當(dāng)取矩陣R的d個最大本征值對應(yīng)的本征向量來展開x時，其截斷均方誤差最小。這d個本征向量組成的正交坐標(biāo)系稱作x所在的D維空間的d維K-L變換坐標(biāo)系，x在K-L坐標(biāo)系上的展開系數(shù)向量y稱作x的K-L變換特征

提取特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第28頁!K-L變換的性質(zhì)y的相關(guān)矩陣是對角矩陣：特征

提取特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第29頁!K-L變換圖解x1x2u2u1二次

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

曲線方程特征

提取特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第30頁!K-L變換的產(chǎn)生矩陣數(shù)據(jù)集KN={xi}的K-L變換的產(chǎn)生矩陣由數(shù)據(jù)的二階統(tǒng)計量決定，即K-L坐標(biāo)系的基向量為某種基于數(shù)據(jù)x的二階統(tǒng)計量的產(chǎn)生矩陣的本征向量K-L變換的產(chǎn)生矩陣可以有多種選擇：x的相關(guān)函數(shù)矩陣R=E[xxT]x的協(xié)方差矩陣C=E[(x-μ)(x-μ)T]樣本總類內(nèi)離散度矩陣：特征

提取特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第31頁!特征選擇:=從原始特征中挑選出一些最有代表性、分類性能最好的特征進(jìn)行分類。從D個特征中選取d個,共CdD種組合。若不限定特征選擇個數(shù)，則共2D種組合

－典型的組合優(yōu)化問題特征選擇的方法大體可分兩大類：Filter方法：根據(jù)獨(dú)立于分類器的指標(biāo)J來評價所選擇的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作為最優(yōu)特征子集。不考慮所使用的學(xué)習(xí)算法。Wrapper方法：將特征選擇和分類器結(jié)合在一起，在學(xué)習(xí)過程中表現(xiàn)優(yōu)異的的特征子集會被選中。6.4特征的選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第32頁!單獨(dú)最優(yōu)特征組合計算各特征單獨(dú)使用時的可分性判據(jù)J并加以排隊(duì)，取前d個作為選擇結(jié)果不一定是最優(yōu)結(jié)果當(dāng)可分性判據(jù)對各特征具有(廣義)可加性，該方法可以選出一組最優(yōu)的特征來，例：各類具有正態(tài)分布各特征統(tǒng)計獨(dú)立可分性判據(jù)基于Mahalanobis距離特征

選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第33頁!順序后退法該方法根據(jù)特征子集的分類表現(xiàn)來選擇特征搜索特征子集：從全體特征開始，每次剔除一個特征，使得所保留的特征集合有最大的分類識別率依次迭代，直至識別率開始下降為止用“l(fā)eave-one-out”方法估計平均識別率：用N-1個樣本判斷余下一個的類別，N次取平均特征

選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第34頁!模擬退火法(II)在某一溫度下，進(jìn)行了充分轉(zhuǎn)換后，材料達(dá)到熱平衡，這時材料處于狀態(tài)i的概率滿足：所有狀態(tài)在高溫下具有相同概率。特征

選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第35頁!模擬退火法(IV)首先給定初始溫度T0和初始解x(0)，以概率P生成下一個新解x’：對于溫度Ti和該優(yōu)化問題的解x(k)，可以生成新解x’。經(jīng)過多次轉(zhuǎn)換，降低溫度得到Ti+1<Ti。在Ti+1下重復(fù)上述過程，最終的解是對該問題尋優(yōu)的結(jié)果。特征

選擇特征的選擇與提取武漢大學(xué),王文偉老師共39頁，您現(xiàn)在瀏覽的是第36頁!特征選擇的模擬退火法Step1:令i=0,k=0,給出初始溫度T0和初始特征組合x(0)。Step2:在x(k)的鄰域N(x(k))中選擇一個狀態(tài)x’，即新特征組合。計算其可分性判據(jù)J