1、,第5章 特征的選擇與提取,主要內(nèi)容,1.引言 2 類別可分離性判據(jù) 3 特征選擇 4.特征提取,1.引言,【問題的提出】,【問題的提出】,【問題的提出】,【問題的提出】,方案2.強(qiáng)調(diào)分析不同截面的信號，如在框架的若干部位沿不同方向截取截面分析從背景到字，以及從字到背景轉(zhuǎn)換的情況,如AB截面切割字符三次，CD截面切割字符一次等。,【問題的提出】,例 用RGB顏色空間和HSI顏色空間,【問題的提出】,【問題的提出】,【問題的提出】,【概念】,【概念】,【概念】,2 類別可分離性判據(jù),【概念】,特征選擇與提取的任務(wù)是找出一組對分類最有效的特征，因此需一準(zhǔn)則。,概念：數(shù)學(xué)上定義的用以衡量特征對分類的

2、效果的準(zhǔn)則實(shí)際問題中需根據(jù)實(shí)際情況人為確定。,誤識率判據(jù)：理論上的目標(biāo)，實(shí)際采用困難（密度未知，形式復(fù)雜，樣本不充分，）,可分性判據(jù)：實(shí)用的可計(jì)算的判據(jù),【概念】,【用于可分性判據(jù)的類內(nèi)類間距離】,【用于可分性判據(jù)的類內(nèi)類間距離】,定義,【用于可分性判據(jù)的類內(nèi)類間距離】,常用的基于類內(nèi)類間距離的可分性判據(jù)：,特點(diǎn)： 直觀，易于實(shí)現(xiàn)（用樣本計(jì)算），較常用。 不能確切表明各類分布重疊情況，與錯(cuò)誤率無直接聯(lián)系。 當(dāng)各類協(xié)差相差不大時(shí)，用此種判據(jù)較好。,【用于可分性判據(jù)的類內(nèi)類間距離】,幾種常見的距離度量,（1）Minkovski Metric (of order s),（2）城市塊（City Blo

3、ck）,（3）歐氏距離（Euclidean）,Chobychev 距離,平方距離,非線性距離度量,【用于可分性判據(jù)的類內(nèi)類間距離】,選擇原則：,ii. 計(jì)算簡單，易于實(shí)現(xiàn)。,iii. 數(shù)學(xué)上容易處理。,準(zhǔn)則函數(shù)的遞推計(jì)算問題:每增/減一個(gè)特征，只影響向量中的一個(gè)元素，矩陣的一行和一列。,【用于可分性判據(jù)的類內(nèi)類間距離】,i. 實(shí)際分類問題需要，找與分類性能關(guān)系密切者。,【基于概率分布的可分性判據(jù)】,考查兩類分布密度之間的交疊程度,【基于概率分布的可分性判據(jù)】,定義：兩個(gè)密度函數(shù)之間的距離：,它必須滿足三個(gè)條件：,【基于概率分布的可分性判據(jù)】,具體定義有多種：,Bhattacharyya 距離,

4、Chernoff 界,散度,【基于概率分布的可分性判據(jù)】,正態(tài)分布情況下：,【基于概率分布的可分性判據(jù)】,幾種常見的概率距離準(zhǔn)則(J ) 和概率相關(guān)性準(zhǔn)則(I ),【熵可分性判據(jù)】,【熵可分性判據(jù)】,規(guī)一化,對稱性,確定性,擴(kuò)張性,連續(xù)性,分枝性,【熵可分性判據(jù)】,Shannon 熵：,平方熵：,廣義熵：,【熵可分性判據(jù)】,結(jié)論,【熵可分性判據(jù)】,舉例：圖像分割,3.特征選擇,問題： 從D維特征中選取d 維（ d D ），使分類性能最佳（ J 最大）。,【問題的提出】,一、窮舉算法： 計(jì)算每一可能的組合，逐一比較準(zhǔn)則函數(shù)。 適用于： d 或D d 很?。ńM合數(shù)較少）的情況。,基本思想： 按照一

5、定的順序?qū)⑺锌赡艿慕M合排成一棵樹，沿樹進(jìn)行搜索，避免一些不必要的計(jì)算，使找到最優(yōu)解的機(jī)會(huì)最早。,【最優(yōu)搜索方法】,算法要點(diǎn)：, 根結(jié)點(diǎn)為全體特征（第0 級） 每個(gè)結(jié)點(diǎn)上舍棄一個(gè)特征，各個(gè)葉結(jié)點(diǎn)代表選擇的各種組合,避免在整個(gè)樹中出現(xiàn)相同組合的樹枝和葉結(jié)點(diǎn) 記錄當(dāng)前搜索到的葉結(jié)點(diǎn)的最大準(zhǔn)則函數(shù)值（界限B），初值置0,每級中將最不可能被舍棄（舍棄后J 值最?。┑奶卣鞣旁谧钭髠?cè) 從右側(cè)開始搜索,【最優(yōu)搜索方法】,從左側(cè)同級中將舍棄的特征不在本結(jié)點(diǎn)以下各級中舍棄 搜索到葉結(jié)點(diǎn)后，更新B 值，然后回溯到上一分支處,如果結(jié)點(diǎn)上J B ，則不向下搜索，向上回溯 每次回溯將已舍棄的特征放回（放回待舍棄之列）

6、如已回溯到頂（根）而不能再向下搜索，則J = B 的葉結(jié)點(diǎn)即為解。,【最優(yōu)搜索方法】,算法要點(diǎn)：,特征總數(shù)D以及選擇特征數(shù)d增加時(shí)，窮舉法計(jì)算量迅速上升。,【最優(yōu)搜索方法】,窮舉法存在的問題：,非最優(yōu)，但某些情況下最優(yōu)，實(shí)現(xiàn)簡單,（1）單獨(dú)最優(yōu)組合選前d 個(gè)單獨(dú)最佳的特征,（2）SFS 法（Sequential Forward Selection：順序前進(jìn)）：從底向上每加入一個(gè)特征尋優(yōu)一次，使加入該特征后所得組合最大 特點(diǎn)：考慮了特征間的相關(guān)性，但某特下一經(jīng)入選，即無法淘汰,（3）廣義SFS 法（GSFS）從底向上，每次增加l 個(gè)特征。 考慮了新增特征中的相關(guān)性計(jì)算量比SFS 大，若l = d

7、 ，（一步加滿），則就是窮舉法,【非最優(yōu)搜索方法】,（4）SBS 法（順序后退，后向貫序）從頂向下，每次減一個(gè)特征 與SFS 相對，一旦失去，無法換回。,（5）廣義SBS 法（GSBS）從頂向下，每次減r 個(gè)特征,模擬退火算法 遺傳算法,【特征選擇的幾種新方法】,模擬退火算法起源于物理退火 物理退火過程： （1）加溫過程 （2）等溫過程 （3）冷卻過程,【模擬退火算法】,1953年，Metropolis提出重要的采樣法，即以概率接受新狀態(tài)，稱Metropolis準(zhǔn)則，計(jì)算量相對Monte Carlo方法顯著減少。 1983年，Kirkpatrick等提出模擬退火算法，并將其應(yīng)用于組合優(yōu)化問題的

8、求解。,【模擬退火算法】,Metropolis準(zhǔn)則,1）Metropolis準(zhǔn)則提出 固體在恒定溫度下達(dá)到熱平衡的過程可以用MorteCarol算法方法加以模擬，雖然該方法簡單，但必須大量采樣才能得到比較精確的結(jié)果，因而計(jì)算量很大。鑒于物理系統(tǒng)傾向于能量較低的狀態(tài)，而熱運(yùn)動(dòng)又妨礙它準(zhǔn)確落到最低態(tài)。,采樣時(shí)著重選取那些有重要貢獻(xiàn)的狀態(tài)則可較快達(dá)到較好的結(jié)果。因此，Metropolis等在1953年提出了重要的采樣法，即以概率接受新狀態(tài)。,假設(shè)在狀態(tài)xold時(shí)，系統(tǒng)受到某種擾動(dòng)而使其狀態(tài)變?yōu)閤new。與此相對應(yīng)，系統(tǒng)的能量也從E(xold)變成E(xnew)，系統(tǒng)由狀態(tài)xold變?yōu)闋顟B(tài)xnew的接

9、受概率p。,1) 隨機(jī)產(chǎn)生一個(gè)初始解x0，令xbest x0 ，并計(jì)算目標(biāo)函數(shù)值E(x0); 2) 設(shè)置初始溫度T(0)=To，迭代次數(shù)i = 1; 3) Do while T(i) Tmin 1) for j = 1k 2) 對當(dāng)前最優(yōu)解xbest按照某一鄰域函數(shù)，產(chǎn)生一新的解xnew。計(jì)算新的目 標(biāo)函數(shù)值E(xnew) ，并計(jì)算目標(biāo)函數(shù)值的增量E = E(xnew) - E(xbest) 。 3) 如果E 0，則xbest = xnew； 4) 如果E 0，則p = exp(- E /T(i); 1) 如果c = random0,1 p， xbest = xnew; 否則xbest = x

10、best。 5) End for 4) i = i 1； 5) End Do 6) 輸出當(dāng)前最優(yōu)點(diǎn)，計(jì)算結(jié)束,【模擬退火算法】,3.特征選擇(續(xù)),【復(fù)習(xí)】,問題： 從D維特征中選取d 維（ d D ），使分類性能最佳（ J 最大）。,【復(fù)習(xí)】,基本遺傳算法（Simple Genetic Algorithms，簡稱SGA），其遺傳進(jìn)化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。,【基本遺傳算法】,基本遺傳算法的組成 （1）編碼（產(chǎn)生初始種群） （2）適應(yīng)度函數(shù) （3）遺傳算子（選擇、交叉、變異） （4）運(yùn)行參數(shù),編碼,GA是通過某種編碼機(jī)制把對象抽象為由特定符號按一定順序排成的串。

11、正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進(jìn)制串進(jìn)行編碼。,【基本遺傳算法】,幾個(gè)術(shù)語,基因型：10101000111,表現(xiàn)型：0.637197,編碼,解碼,個(gè)體（染色體）,基因,【基本遺傳算法】,初始種群 ：,SGA采用隨機(jī)方法生成若干個(gè)個(gè)體的集合，該集合稱為初始種群。初始種群中個(gè)體的數(shù)量稱為種群規(guī)模。,適應(yīng)度函數(shù) ：,遺傳算法對一個(gè)個(gè)體（解）的好壞用適應(yīng)度函數(shù)值來評價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問題本身的要求而定。,【基本遺傳算法】,遺傳算法使用選擇運(yùn)算來實(shí)現(xiàn)對群體中的個(gè)

12、體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個(gè)體，遺傳到下一代群體。,【基本遺傳算法】,選擇算子 ：,交叉算子 ：,所謂交叉運(yùn)算，是指對兩個(gè)相互配對的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。 SGA中交叉算子采用單點(diǎn)交叉算子。,交叉前： 00000|010000 11100|000101 交叉后： 00000|000101 11100|010000

13、,交叉點(diǎn),【基本遺傳算法】,交叉算子示意圖,所謂變異運(yùn)算，是指依據(jù)變異概率 Pm 將個(gè)體編碼串中的某些基因值用其它基因值來替換，從而形成一個(gè)新的個(gè)體。遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力，同時(shí)保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。 SGA中變異算子采用基本位變異算子。,【基本遺傳算法】,變異算子,基本位變異算子的執(zhí)行過程,變異前： 0000010000 變異后： 1000010000,變異點(diǎn),【基本遺傳算法】,SGA的框圖,【基本遺傳算法】,4 特征提取,特征提?。喊袲個(gè)特征變?yōu)閐 個(gè)新特征,目的：更好分類和/或減少計(jì)算量,【概念】,【概念】,【概念】,準(zhǔn)則函數(shù)J (w) ：,【歐氏距離準(zhǔn)則下的特征提取】,【歐氏距離準(zhǔn)則下的特征提取】,【歐氏距離準(zhǔn)則下的特征提取】,【歐氏距離準(zhǔn)則下的特征提取】,【歐氏距