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

模式識別導論

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

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

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

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

離散度矩陣樣本類內

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

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

提取求解最小均方誤差正交基用Lagrange乘子法：結論：以相關矩陣R的d個本征向量為基向量來展開x時，其均方誤差為：K-L變換：當取矩陣R的d個最大本征值對應的本征向量來展開x時，其截斷均方誤差最小。這d個本征向量組成的正交坐標系稱作x所在的D維空間的d維K-L變換坐標系，x在K-L坐標系上的展開系數向量y稱作x的K-L變換特征

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

提取K-L變換的性質y的相關矩陣是對角矩陣：特征

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

曲線方程標準二次

曲線方程特征

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

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

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

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

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

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

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

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

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

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

選擇模擬退火法(V)經過有限次轉換，在溫度Ti下的平衡態(tài)xi的分布為：當溫度T降為0時，xi的分布為：特征

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

選擇遺傳算法從生物進化論得到啟迪。遺傳，變異，自然選擇?；蜴湸a：待解問題的解的編碼，每個基因鏈碼也稱為一個個體。對于特征選擇，可用一個D位的0/1構成的串表示一種特征組合。群體：若干個個體的集合，即問題的一些解的集合。交叉：由當前兩個個體的鏈碼交叉產生新一代的個體。變異：由一個鏈碼隨機某基因使其翻轉。特征

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

選擇6.5

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