模式識別:特征的選擇和提取第6章特征的選擇和提取目錄6.1引言6.2類別可分離性判據6.3特征選擇(重點)6.1

引言特征的選擇與提取是模式識別中重要而困難的一個環節：分析各種特征的有效性并選出最有代表性的特征是模式識別的關鍵一步降低特征維數在很多情況下是有效設計分類器的重要課題特征的選擇與提取簡述兩類提取有效信息、壓縮特征空間的方法：特征提取和特征選擇特征提取

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

：從原始特征中挑選出一些最有代表性，分類性能最好的特征目的：降維特征的選擇與提取舉例細胞自動識別：原始測量：細胞的數字圖像原始特征：細胞面積，胞核面積，形狀系數，光密度，核內紋理，和漿比壓縮特征：原始特征的維數很高，需壓縮以便于分類特征選擇：挑選最具分類信息的特征挑選兩個好的特征：胞核面積、光密度特征提取：坐標變換產生兩個新的特征，它們由原始特征的變換得到特征選擇？特征提取？哪種方法更適用于我們專業？生物相關的問題，往往需要真實的特征。例如：基因芯片中的特征為基因：特征選擇將得到有代表性的重要基因，這些特征基因是真實的。特征提取將從原始特征得到新的特征，這些特征不能稱為特征基因。特征選擇特征選擇？特征提取？哪種方法更適用于我們專業？提取選擇目錄6.1引言6.2類別可分離性判據6.3特征選擇(重點)6.2類別可分離性判據類別可分離性判據：衡量不同特征及其組合對分類是否有效的定量準則理想準則：某組特征使分類器錯誤概率最小實際的類別可分離性判據應滿足的條件：度量特性：與錯誤率有單調關系當特征獨立時有可加性：單調性：常見類別可分離性判據：基于距離、概率分布、熵函數準則函數例子準則函數例子其它可分性判據基于概率的可分性判據：用概率密度函數間的距離來度量正態分布的散度Mahalanobis基于熵函數的可分性判據Shannon熵：平方熵：目錄6.1引言6.2類別可分離性判據6.3特征選擇(重點)目錄6.1引言6.2類別可分離性判據6.3特征提取6.4特征選擇(重點)經典特征選擇算法許多特征選擇算法力求解決搜索問題，經典算法有單獨最優特征組合法、后退法、前進法(重點)分支定界法模擬退火法(重點)Tabu禁忌搜索法遺傳算法(重點)窮舉法由原始的D維空間降到d維空間問題。一共有q=CDd種特征組合結果。D=20，d=10時，q=D=100，d=10時，q=

窮舉法（最優方法）：一定能找到最優解如果計算每組特征組合的J值，然后選擇J值最優的特征組合，往往非常耗時。計算量上無法承受。耗時!1847561013怎樣減少計算時間？使用一些次優方法，以大大減少計算時間。為什么有如此多的特征選擇算法？沒有哪個算法能夠保證兼顧運算時間又能得到更優的解。單獨最優特征組合計算各特征單獨使用時的可分性判據J并加以排隊，取前d個作為選擇結果特征選擇結果（取前d個）不一定是最優結果當可分性判據對各特征具有可加性（各特征獨立），該方法可以選出一組最優的特征來，例：順序前進法（SequentialForwardSelection，SFS）順序前進法是一種自下而上的搜索方法，它從0個特征開始每次增加一個特征，所增加的特征應使它與已入選的特征組合在一起所得J值為最大，直到特征數增加到d為止。設已選入了k個特征構成了一個大小為k的特征組Xk，把未入選的D-K個特征xj，j=1,2,…,D-k,按與已入選特征組合后的J值大小排列：若則下一步的特征組選為Xk+1=Xk+x1順序前進法考慮了所選特征與已入選特征之間的相關性，一般來說比單獨方法好。主要缺點是一旦某特征已選入，即使由于后加入的特征使它變為多余，也無法再把它剔除。廣義順序前進法（GeneralizedSequentialForwardSelection,GSFS）把SFS法推廣為每次不止增加一個特征而是增加L個特征，就成為廣義順序前進法（GeneralizedSequentialForwardSelection,GSFS）。即每次從未入選的特征中選擇出L個特征，使得這r個特征加入后J值達最大。GSFS法計算量大（每步有CLD-k

個候選特征組需要逐個計算）。另外它也無法剔除已入選的特征。順序后退法（SequentialBackwardSelection,SBS）順序后退法是一種自上而下的方法，它從全體特征開始每次剔除一個，所剔除的特征應使仍然保留的特征組的J值最大，直到特征數減少到d為止。設已剔除了k個特征，剩下的特征組為，將中的各特征xj按上述J值大小排序，j=1,2,…,D-k。若則順序后退法的優點在計算過程中可以估計每去掉一個特征所造成可分性的降低，缺點是由于順序后退法的計算是在高維空間進行，所以計算量比順序前進法要大。同樣，該方法也可推廣為廣義順序后退法（GeneralizedSequentialBackwardSelection,GSBS).增L減r法（L-r法）為了避免前面方法一旦被選入（或剔除）就不能再剔除（或選入）的缺點，可在選擇過程中加入局部回溯過程。例如，在第k步可先用SFS法一個個加入特征到k+L個，然后再用SBS法一個個剔除r個特征，我們把這樣一種算法叫增L減r法。增L減r法（L-r法）步驟一：用SFS法在未入選特征組中逐個選入L個特征，形成新特征組Xk+L，設置k=k+L，步驟二：用SBS法從特征組Xk中逐個剔除r個最差的特征，形成新特征組Xk-r，設置k=k-r，若k=d，則終止算法，否則設置xk=xk-r，轉向第一步。（1）當L>r時，L-r法是一種自下而上的算法，先執行第一步，然后執行第二步，開始時，設置k=0，x0=空（2）當L<r時，L-r法是一種自上而下的算法，此時先執行第二步，然后執行第一步，開始時設置k=0，x0={x1，…,xD}

（ZL，Zr）法：廣義L-r法Li,i=1,2,…,ZLrj,j=1,2,…,Zr

（ZL，Zr）法：廣義L-r法模擬退火算法1982年，Kirkpatrick(譯名：科克派特瑞克)等人將退火思想引入組合優化領域，提出一種解大規模組合優化問題，特別是NP完全組合優化問題的有效近似算法——模擬退火算法（simulatedannealingalgorithm)。他源于對固體退火過程的模擬；采用Metropolis接受準則；并用一組稱為冷卻進度表的參數控制算法進程，使算法在多項式時間里給出一個近似最優解。模擬退火來自冶金學的專有名詞退火。退火是將材料加熱后再經特定速率冷卻，目的是增大晶粒的體積，并且減少晶格中的缺陷。材料中的原子原來會停留在使內能有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機在其他位置中移動。退火冷卻時速度較慢，使得原子有較多可能可以找到內能比原先更低的位置。模擬退火的原理也和金屬退火的原理近似：我們將熱力學的理論套用到統計學上，將搜尋空間內每一點想像成空氣內的分子；分子的能量，就是它本身的動能；而搜尋空間內的每一點，也像空氣分子一樣帶有“能量”，以表示該點對命題的合適程度。算法先以搜尋空間內一個任意點作起始：每一步先選擇一個“鄰居”，然后再計算從現有位置到達“鄰居”的概率。模擬退火算法應用的一般形式從選定的初始解開始，借助于控制溫度t遞減時產生的一系列Mapkob（馬爾科夫）鏈，利用一個新解產生裝置和接受準則,重復進行包括“產生新解-——計算目標函數——判斷是否接受新解（或舍棄）新解”這三個階段，不斷對當前解迭代，從而達到使目標函數最優（最大或最小）的執行過程。書中用于特征選擇的模擬退火算法initilaize(i0,T0,L0)k:=0;i:=i0repeatforL:=1toLkdobegin

generate(jfromSi);iff(i)<f(j)i:=jelseiftheni:=j;endk:=k+1calculate-length(Lk)calculate-control(Tk)untilstopcriterionMetropolis接受準則對應的轉移概率冷卻進度表參數選擇方案冷卻進度表是一組控制算法進程的參數。溫度T的初值；控制參數T的衰減函數；Mapkob鏈的長度；停止準則；冷卻進度表是影響模擬退火算法試驗性能的重要因素，其合理選取是算法應用的關鍵。溫度T的初值T0的選取原則

T0值的選取基于“Tk值只要選的充分大，就會立即達到準平衡”的論證，為使算法進程一開始就達到準平衡，應讓初始接受率為

Metropolis準則，可推知T0值很大。例如取，則在時T0

>949。經驗法則要求算法進程在合理時間里搜索盡可能大的空間范圍，只有足夠大的值才能滿足這個要求。溫度T的衰減函數衰減函數(k＝0，1，2，...)。其中是一個接近1的常數。這個衰減函數是Kirkpatrick等人首先提出來的，他們取。Bonomi以及Lutton等許多研究者研究，認為值一般在0.5-0.99范圍內取值為宜。Mapkob鏈的長度直接指定方式n為循環次數此外，Skiscim和Nahar等人提出用單個Mapkob鏈的終止準則去產生Lk，Lk的值與Tk值相關。這類方法便于控制最終解的質量，卻難以把握算法進程的時間。在Mapkob鏈的終止準準則選擇不當時，甚至可能危及模擬退火算法的收斂性。而用限定Lk的方法和他相反，它便于直接控制算法進程的CPU時間。停止準則停止準則1:循環n次停止。停止準則2:在若干個相繼的Mapkob鏈無任何優化就停止算法。這種停止準則（準則2）兼顧了最終解的質量和CPU時間。在T，L等參數的配合下，可得到高質量最終解。模擬退火算法與初始值無關，算法求得的解與初始解狀態無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l收斂于全局最優解的全局優化算法

。習題：敘述用于特征選擇的增l減r搜索算法的算法步驟。并考慮l值大于（或小于）r值時，增l減r算法步驟應做出怎樣的修改，以及該情況下，增l減r搜索算法的特點？為什么分類器設計中的最近鄰法可以適用于線性不可分的樣本集？為什么最近鄰法又稱為分類器設計的非參數方法？它與fisher等參數方法在訓練和預測階段效率上有什么不同？遺傳算法的運算過程主要分四個階段，包括編碼階段、___________、交叉階段、___________。敘述怎樣利用模擬退火算法是進行特征選擇。模擬退火算法采用___________準則，并用一組稱為冷卻進度表的參數控制算法進程，使算法在多項式時間里給出一個近