《模式識別》課件 第五章 特征選擇

第五章特征選擇2特征選擇5.1引言5.2類別可分離性判據5.3特征子集的搜索策略3特征選擇5.1引言5.2類別可分離性判據5.3特征子集的搜索策略4尺寸重量顏色5對分類器設計來說，使用什么樣的特征描述事物，也就是說使用什么樣的特征空間是個很重要的問題。這個問題稱之為描述量的選擇問題，意思是指保留哪些描述量，刪除哪些描述量的問題。本章研究對特征空間進行改造,目的在于提高其某方面的性能，因此又稱特征的優化問題。

基本概念5.1引言65.1引言75.1引言8對特征空間的改造、優化,主要的目的是降維，即把維數高的特征空間改成維數低的特征空間，降維主要有兩種途徑。一種是篩選掉一些次要的特征，問題在于如何確定特征的重要性，以及如何篩選。另一種方法是使用變換的手段，限定在線性變換的方法上，通過變換來實現降維。

5.1引言9特征的選擇與提取：分析各種特征的有效性并選出最有代表性的特征是模式識別系統設計的關鍵步驟。降低特征維數在很多情況下是有效設計分類器的重要課題。數據獲取預處理特征提取

與選擇分類決策分類器

設計信號空間特征空間5.1引言基本概念10三大類特征三大類特征：物理、結構和數字的■物理和結構特征：易于為人的直覺感知，但有時難于定量描述，因而不易用于機器判別?！鰯底痔卣鳎阂子谟脵C器定量描述和判別，如基于統計的特征。5.1引言11假設有D維特征向量空間，y={y1,y2,…yD}：

特征選擇是指從原有的D維特征空間，刪去一些特征描述量，從而得到精簡后的特征空間。在這個特征空間中，樣本由降維后的d維的特征向量描述：x={x1,x2,…xd}，d＜D。由于x只是y的一個子集，因此每個分量xi必然能在原特征集中找到其對應的描述量xi=yj。

特征提取則是找到一個映射關系：A:Y→X，使新樣本特征描述維數比原維數降低。其中每個分量xi是原特征向量各分量的函數，即xi=WTyi。特征優化兩種方法5.1引言

特征選擇在概念上十分簡單，即對原有特征進行刪選優化.一般人常想，只要逐個分析每個特征，判斷它對分類的價值，然后根據其價值刪去或保留，這是人們常采用的方法，但是這種方法并不能保證特征空間的最優組合優化，因此本節僅討論一些原理上更好的方法。1213特征選擇:從原始特征中挑選出一些最有代表性、分類性能最好的特征進行分類。（可解釋性好）要解決兩個問題：選擇的標準，如可分離性判據快速特征子集搜索算法從D個特征中選取d個,共

種組合。若不限定特征選擇個數，則共2D種組合

－典型的組合優化問題14特征選擇的方法：是否直接考慮分類器性能Filter方法：根據獨立于分類器的指標J來評價所選擇的特征子集S，在所有可能的特征子集中搜索出使得J最大的特征子集作為最優特征子集。不考慮所使用的學習算法。Wrapper方法：將特征選擇和分類器結合在一起，在分類過程中表現優異的的特征子集會被選中。選擇特征的順序：自下而上：特征數從零逐步增加到d。自上而下：特征數從D開始逐步減少到d。15特征選擇5.1引言5.2類別可分離性判據5.3特征子集的搜索策略16特征選擇任務是從n個特征中求出對分類最有效的m個特征(m＜n)。對于特征選擇來講，從n個特征中選擇出m個特征，有種組合方式。哪一種特征組的分類效果最好？這需要有一個比較標準，即需要一個定量的準則來衡量選擇結果的好壞。5.2類別可分性判據17很自然地會想到，既然模式識別的目的是設計分類器，那么用分類器的錯誤概率作為準則就行了，也就是說，使分類器錯誤概率最小的那組特征，就應當是一組最有效的特征。從理論上講，這是完全正確的，但在實際使用中卻有很大困難。從錯誤概率的計算公式就會發現，即使在類條件概率密度已知的情況下錯誤概率的計算就很復雜，何況實際問題中概率分布常常不知道，這使得直接用錯誤概率作為準則來評價特征的有效性比較困難。5.2類別可分性判據18用以定量檢驗分類性能的準則稱為類別可分性準則Jij,需要滿足以下幾點：5.2類別可分性判據19用以定量檢驗分類性能的準則稱為類別可分性準則Jij,需要滿足以下幾點：5.2類別可分性判據20（1）與錯誤概率有單調關系（2）當特征獨立時有可加性（3）度量特性（4）單調性設計分類器錯誤概率最小新的標準目的理論最理想×5.2類別可分性判據215.2類別可分性判據1.基于距離的可分性判據2.基于概率分布的可分性判據3.基于熵函數的可分性判據221.基于距離的可分性判據基于距離的可分性判據的實質是Fisher準則的延伸，即綜合考慮不同類樣本的類內聚集程度與類間的離散程度這兩個因素。判據的優化體現出降維特征空間較好地體現類內密集。一些不能體現類間分隔開的特征很可能被排除掉了。掌握利用離散矩陣來描述數據離散程度的方法。5.2類別可分性判據23基于距離度量是常用來進行分類的重要依據，因為一般情況下同類物體在特征空間呈聚類狀態，即從總體上說同類物體內各樣本由于具有共性，因此類內樣本間距離應比跨類樣本間距離小。Fisher準則是以使類間距離盡可能大同時又保持類內距離較小這一種原理為基礎的。同樣在特征選擇中也可以使用類似的原理，這一類被稱為基于距離的可分性判據。為了度量類內、類間的距離，可用其他方法描述方法，即描述樣本的離散程度的方法。5.2類別可分性判據1.基于距離的可分性判據24各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離的平均值作為可分性準則5.2類別可分性判據1.基于距離的可分性判據25各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離的平均值作為可分性準則5.2類別可分性判據1.基于距離的可分性判據26各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離的平均值作為可分性準則5.2類別可分性判據1.基于距離的可分性判據均值向量總平均向量27各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離的平均值作為可分性準則5.2類別可分性判據1.基于距離的可分性判據均值向量總平均向量樣本到質心的平方距離某類均值向量到總體樣本向量之間的平方距離28各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離的平均值作為可分性準則5.2類別可分性判據1.基于距離的可分性判據均值向量總平均向量各類均值向量的平均平方距離29樣本類間

離散度矩陣樣本類內

離散度矩陣類間可分離性判據5.2類別可分性判據1.基于距離的可分性判據30樣本類間

離散度矩陣樣本類內

離散度矩陣類間可分離性判據5.2類別可分性判據1.基于距離的可分性判據31基于距離的準則概念直觀，計算方便，但與錯誤率沒有直接聯系樣本類間

離散度矩陣樣本類內

離散度矩陣類間可分離性判據5.2類別可分性判據1.基于距離的可分性判據32基于距離的可分性判據的其他表達形式：5.2類別可分性判據1.基于距離的可分性判據33優缺點：優點：定義直觀、易于實現，因此比較常用。缺點：沒有直接考慮樣本的分布情況，很難在理論上建立起它們與分類錯誤率的聯系，而且當兩類樣本的分布有重疊時，這些判據不能反映重疊的情況。5.2類別可分性判據1.基于距離的可分性判據34基于距離的可分性判據原理直觀，計算簡便。但是這種原理沒有考慮概率分布，因此當不同類樣本中有部分在特征空間中交迭分布時，簡單地按距離劃分，無法表明與錯誤概率之間的聯系?；诟怕史植嫉目煞中耘袚t依據如下觀察到的現象。如果不考慮各類的先驗概率，或假設兩類樣本的先驗概率相等，那么從兩類條件概率分布可以看出，如果兩類條件概率分布互不交迭，即對p(X|ω2)≠0處都有p(X|ω1)＝0，則這兩類就完全可分；另一種極端情況是對所有X都有p(X|ω1)＝p(X|ω2)，則兩類就完全不可分。5.2類別可分性判據2.基于概率分布的可分性判據35完全可分對p(X|ω2)≠0處都有p(X|ω1)＝0完全不可分對所有X都有p(X|ω1)＝p(X|ω2)5.2類別可分性判據2.基于概率分布的可分性判據36顯然不同類別在特征空間x中的分布要盡可能不一樣，則分類就比較容易，通俗的講，則不同類別在特征空間的不同區域聚集，則分類就容易，它們重迭的程度越低，越有別于分類。為了考查在不同特征下兩類樣本概率分布的情況，定義了基于概率分布的可分性判據。5.2類別可分性判據2.基于概率分布的可分性判據37顯然不同類別在特征空間x中的分布要盡可能不一樣，則分類就比較容易，通俗的講，則不同類別在特征空間的不同區域聚集，則分類就容易，它們重迭的程度越低，越有別于分類。為了考查在不同特征下兩類樣本概率分布的情況，定義了基于概率分布的可分性判據。分布密度的交疊程度可用p(X|ω1)及p(X|ω2)這兩個分布密度函數之間的距離Jp來度量，距離Jp有以下幾個共同點：1.Jp是非負，即Jp≥0；2.當兩類完全不交迭時Jp達到其最大值；3.當兩類分布密度相同時，Jp＝05.2類別可分性判據2.基于概率分布的可分性判據381.Bhattacharyya距離（巴氏距離）：顯然，當p(X|ω1)＝p(X|ω2)對所有X值成立時JB＝0，而當兩者完全不交迭時JB無窮大。巴氏距離與錯誤率的上界有直接關系，因此JB不僅用來對特征空間進行降維優化，而且也用來對分類器的錯誤率作出估計。2.Chernoff（切諾夫）界限：其中S取[0，1]區間的一個參數，顯然在S＝0.5時就變為JB式，因此JB是JC的一個特例。5.2類別可分性判據2.基于概率分布的可分性判據393.散度：區分i，j兩類總的平均信息對wi類的平均可分信息對wj類的平均可分信息散度Jd為兩類平均可分信息之和wi，wj對數似然比5.2類別可分性判據2.基于概率分布的可分性判據40當兩類樣本都服從正態分布，且協方差矩陣相等的情況下Mahalanobis距離5.2類別可分性判據散度為：這也等于兩類均值之間的Mahalanobis距離。2.基于概率分布的可分性判據41特征對分類的有效性也可以從后驗概率角度來考慮。已知最佳分類器是由后驗概率決定的，如果對某些特征，各類后驗概率都相等，即：P(ωi|x)=1/c，其中c為類別數，則樣本的類屬就無法確定，或者只能任意指定樣本所屬類別。此時錯誤率為(c-1)/c。5.2類別可分性判據3.基于熵的可分性判據42如果考慮另一極端，假設能有一組特征使得：P(ωi|x)=1,且P(ωj|x)=0,對任意j≠i。則此時樣本x肯定屬于ωi類，錯誤率為0。由此可看出，后驗概率越集中，錯誤概率就越小，反之后驗概率分布越平緩，即接近均勻分布，則分類錯誤概率就越大。為了衡量后驗概率分布的集中程度，借用信息論中熵的概念，定義了基于熵的類別可分性判據。5.2類別可分性判據3.基于熵的可分性判據43

把類別ωi,i=1,2,…,c看作一系列隨機事件，它的發生依賴于隨機向量x，給定x后ωi的后驗概率是P(ωi|x)。

如果根據x能完全確定ω，則ω就沒有不確定性，對ω本身的觀察就不會再提供信息量，此時熵為0，特征最有利于分類；熵來度量均一性。

如果x完全不能確定ω，則ω不確定性最大，對ω本身的觀察所提供信息量最大，此時熵為最大，特征最不利于分類。5.2類別可分性判據3.基于熵的可分性判據44

■熵函數：衡量后驗概率分布的集中程度■

Shannon熵：■平方熵：■熵函數期望表征類別的分離程度：5.2類別可分性判據3.基于熵的可分性判據45特征選擇5.1引言5.2類別可分離性判據5.3特征子集的搜索策略46許多特征選擇算法力求解決搜索問題，經典算法有：5.3特征子集的搜索策略471.單獨最優特征組合計算各特征單獨使用時的可分性判據J并加以排隊，取前d個作為選擇結果組合起來不一定是最優結果當可分性判據對各特征具有(廣義)可加性，該方法可以選出一組最優的特征來，例：各類具有正態分布各特征統計獨立可分性判據基于Mahalanobis距離5.3特征子集的搜索策略482.順序前進法（SFS）:最簡單的自下而上搜索算法自下而上搜索方法。每次從未入選的特征中選擇一個特征，使得它與已入選的特征組合在一起時所得的可分性或分類識別率為最大，直至特征數增加到d為止。該方法考慮了所選特征與已入選特征之間的相關性。比單獨最優特征組合效果好。缺點：一旦某特征已入選，即使由于后加入的特征使它變為多也無法再把它剔除。5.3特征子集的搜索策略49推廣：3.廣義順序前進法（GSFS），每次從未入選的特征中選擇出r個特征，使得這r個特征加入后J值達最大。SFS每次只增加一個特征，它未考慮未入選特征之間的統計相關性；GSFS法可以克服這個缺點，計算量增大，它比SFS更可靠，但仍然無法拿出已入選的特征。5.3特征子集的搜索策略504.順序后退法（SBS）：自上而下的方法該方法根據特征子集的分類表現來選擇特征搜索特征子集：從全體特征開始，每次剔除一個特征，使得所保留的特征集合有最大的可分性或分類識別率。依次迭代，直至可分性或識別率開始下降為止。和順序前進法比較，順序后退法有兩個特點：計算過程中可以估計每此去掉一個特征所造可分性的降低；由于順序后退法的計算是在高位空間進行的，所以計算量比順序前進法要大推廣：廣義順序后退法5.3特征子集的搜索策略515.增l減r法（l-r）避免上述方法的一旦被選入（或剔除）就不能再剔除（或選入）的缺點，可在選擇過程中加入局部回溯過程。在第k步可先用SFS法一個個加入特征到k+l個，然后再用SBS法一個個剔除r個特征。5.3特征子集的搜索策略52步驟：假設已經選了k個特征，得出特征組Xk1.用SFS法在未入選特征組XD-Xk中逐個選入特征l個，形成新特征組Xk+l，置k=k+l,

Xk=Xk+l2.用SBS法從Xk中逐個剔除r個最差的特征，形成新特征組Xk-r，置k=k-r,

若k=d則終止算法，否則，置Xk=Xk-r,轉向第一步。5.增l減r法（l-r）5.3特征子集的搜索策略53說明：當l>r時，l-r法是自下而上的算法，先執行第一步，然后執行第二步，起始時應置k=0,X0從空開始。當l<r時，l-r法是自上而下的算法，先執行第二步，然后執行第一步，起始時應置k=D,X0從全部特征開始。推廣：6.廣義l-r法，上述方法是逐個增加和逐個刪除的5.增l減r法（l-r）5.3特征子集的搜索策略546.遺傳算法從生物進化論得到啟迪。遺傳，變異，自然選擇?；谠撍枷氚l展了遺傳優化算法?；蜴湸a：待解問題的解的編碼，每個基因鏈碼也稱為一個個體。對于特征選擇，可用一個D位的0/1構成的串表示一種特征組合。群體：若干個個體的集合，即問題的一些解的集合。交叉：由當前兩個個體的鏈碼交叉產生新一代的兩個個體。變異：由一個鏈碼隨機選取某基因使其翻轉。5.3特征子集的搜索策略555.3特征子集的搜索策略56適應度：每個個體xi的函數值fi，個體xi越好，適應度fi越大。新一代群體對環境的平均適應度比父代高。遺傳算法的基本框架：Step1:令進化代數t=0。Step2:給出初始化群體P(t)，令xg為任一個體。Step3:對P(t)中每個個體估值，并將群體中最優解x’與xg比較，如