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

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

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

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

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

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

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

（ZL，Zr）法：廣義L-r法模擬退火算法1982年，Kirkpatrick(譯名：科克派特瑞克)等人將退火思想引入組合優(yōu)化領(lǐng)域，提出一種解大規(guī)模組合優(yōu)化問題，特別是NP完全組合優(yōu)化問題的有效近似算法——模擬退火算法（simulatedannealingalgorithm)。他源于對固體退火過程的模擬；采用Metropolis接受準(zhǔn)則；并用一組稱為冷卻進(jìn)度表的參數(shù)控制算法進(jìn)程，使算法在多項(xiàng)式時間里給出一個近似最優(yōu)解。模擬退火來自冶金學(xué)的專有名詞退火。退火是將材料加熱后再經(jīng)特定速率冷卻，目的是增大晶粒的體積，并且減少晶格中的缺陷。材料中的原子原來會停留在使內(nèi)能有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機(jī)在其他位置中移動。退火冷卻時速度較慢，使得原子有較多可能可以找到內(nèi)能比原先更低的位置。模擬退火的原理也和金屬退火的原理近似：我們將熱力學(xué)的理論套用到統(tǒng)計(jì)學(xué)上，將搜尋空間內(nèi)每一點(diǎn)想像成空氣內(nèi)的分子；分子的能量，就是它本身的動能；而搜尋空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有“能量”，以表示該點(diǎn)對命題的合適程度。算法先以搜尋空間內(nèi)一個任意點(diǎn)作起始：每一步先選擇一個“鄰居”，然后再計(jì)算從現(xiàn)有位置到達(dá)“鄰居”的概率。模擬退火算法應(yīng)用的一般形式從選定的初始解開始，借助于控制溫度t遞減時產(chǎn)生的一系列Mapkob（馬爾科夫）鏈，利用一個新解產(chǎn)生裝置和接受準(zhǔn)則,重復(fù)進(jìn)行包括“產(chǎn)生新解-——計(jì)算目標(biāo)函數(shù)——判斷是否接受新解（或舍棄）新解”這三個階段，不斷對當(dāng)前解迭代，從而達(dá)到使目標(biāo)函數(shù)最優(yōu)（最大或最小）的執(zhí)行過程。書中用于特征選擇的模擬退火算法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接受準(zhǔn)則對應(yīng)的轉(zhuǎn)移概率冷卻進(jìn)度表參數(shù)選擇方案冷卻進(jìn)度表是一組控制算法進(jìn)程的參數(shù)。溫度T的初值；控制參數(shù)T的衰減函數(shù)；Mapkob鏈的長度；停止準(zhǔn)則；冷卻進(jìn)度表是影響模擬退火算法試驗(yàn)性能的重要因素，其合理選取是算法應(yīng)用的關(guān)鍵。溫度T的初值T0的選取原則

T0值的選取基于“Tk值只要選的充分大，就會立即達(dá)到準(zhǔn)平衡”的論證，為使算法進(jìn)程一開始就達(dá)到準(zhǔn)平衡，應(yīng)讓初始接受率為

Metropolis準(zhǔn)則，可推知T0值很大。例如取，則在時T0

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

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