title: 模式識(shí)別 第七章 特征提取和選擇
date: 2017-03-26 18:47:52
categories: ML/盧曉春 模式識(shí)別引論
mathjax: true
tags: [Machine Learning]

第七章 特征提取和選擇

特征形成

特征通常有物理的赦肋、結(jié)構(gòu)的、數(shù)學(xué)的三種類型杈帐。物理的贤壁、結(jié)構(gòu)的比較直觀巩梢，但對(duì)于計(jì)算機(jī)而言，數(shù)學(xué)的更方便處理极阅。
因此疗涉，對(duì)于一個(gè)具體問(wèn)題，往往是缸废，

• 物理量的獲取與轉(zhuǎn)換：對(duì)從傳感器中得到的信號(hào)包蓝，可以稱之為原始信息
• 描述事物方法的選擇與設(shè)計(jì)：在得到了原始信息之后，要對(duì)它進(jìn)一步加工企量，以獲取對(duì)分類最有效的信息测萎。
• 特征空間的優(yōu)化 ：已有了一個(gè)初始的特征空間后，如何對(duì)它進(jìn)行改造與優(yōu)化的問(wèn)題届巩。一般說(shuō)來(lái)要對(duì)初始的特征空間進(jìn)行優(yōu)化是為了降維硅瞧。
• 特征形成：根據(jù)被識(shí)別的對(duì)象產(chǎn)生出一組基本特征，它可以是由計(jì)算得到的恕汇，也可以是用儀表或傳感器測(cè)量出來(lái)的腕唧，這樣產(chǎn)生出來(lái)的特征稱為原始特征。在大多數(shù)情況下拇勃，不能直接對(duì)原始特征進(jìn)行分類器設(shè)計(jì)四苇。
• 特征選擇：從一組特征中挑選出一些最有效的特征以達(dá)到降低特征空間維數(shù)的目的孝凌，這個(gè)過(guò)程叫特征選擇方咆。
• 特征抽取：原始特征的數(shù)量可能很大蟀架，或者樣本處于一個(gè)高維空間中瓣赂，通過(guò)映射（或變換）的方法可以用低維空間來(lái)表示樣本，這個(gè)過(guò)程叫特征抽取片拍。映射后的特征叫二次特征煌集，它們是原始特征的某種組合（通常是線性組合）。所謂特征抽取在廣義上就是指一種變換捌省。
  注：特征抽取是通過(guò)變換的方法組合原始高維特征苫纤，獲得一組低維的新特征，而特征選擇是根據(jù)專家的經(jīng)驗(yàn)知識(shí)或根據(jù)某種評(píng)價(jià)準(zhǔn)則來(lái)挑選出那些對(duì)分類最有影響力的特征纲缓，并未形成新的特征卷拘。
  例子：
  需要處理：

比如車牌識(shí)別，數(shù)據(jù)掃描進(jìn)來(lái)后祝高，怎么來(lái)表示數(shù)字呢栗弟？

• 可以直接圖像，

• 可以是數(shù)字自上到下離y軸的距離工闺，10個(gè)數(shù)字這類信息肯定是不一樣且小于上述圖像表示的
• 可以是田字格中乍赫，數(shù)字和橫向線瓣蛀、豎向線的交點(diǎn)數(shù)量。

類別可分離性判據(jù)

對(duì)特征空間優(yōu)化是一種計(jì)算過(guò)程：
* 找到一種準(zhǔn)則（或稱判據(jù)）雷厂，通常用一種式子表示
* 計(jì)算出一種優(yōu)化方法惋增，使得這種計(jì)算準(zhǔn)則達(dá)到一個(gè)極值。

基于距離的可分性判據(jù)：使類間距離盡可能大同時(shí)又保持類內(nèi)距離較小

類的均值向量：

Paste_Image.png

Paste_Image.png

• 類內(nèi)離散度矩陣
• 兩類之間的距離
• 各類模式之間的總的均方距離
• 多類情況下總的類內(nèi)、類間及總體離差矩陣

基于概率分布的可分性判據(jù)

Paste_Image.png

滿足下述條件的任何函數(shù)都可以用作基于類概率密度的可分性判據(jù)钩杰。

• 非負(fù)性
• 當(dāng)兩類概率密度函數(shù)完全不重疊時(shí)纫塌，判據(jù)取最大值

• 當(dāng)兩類概率密度函數(shù)完全相同時(shí)，判據(jù)取最小值0

  
  
  Paste_Image.png
  
  
  Paste_Image.png

特征抽取:低維新特征

原始特征的數(shù)量可能很大讲弄，或者樣本處于一個(gè)高維空間中措左，通過(guò)映射（或變換）的方法可以用低維空間來(lái)表示樣本，這個(gè)過(guò)程叫特征抽取避除。映射后的特征叫二次特征怎披，它們是原始特征的某種組合（通常是線性組合）。所謂特征抽取在廣義上就是指一種變換瓶摆。

基于可分離性判據(jù)的特征抽取方法

Paste_Image.png

基于離散K-L變換的特征抽取方法 即 主成分分析

K-L變換是一種正交變換凉逛，即將一個(gè)向量X，在某一種坐標(biāo)系統(tǒng)中的描述群井，轉(zhuǎn)換成用另一種基向量組成的坐標(biāo)系統(tǒng)表示状飞。
要使得轉(zhuǎn)換坐標(biāo)系后的向量和原向量的均方誤差為最小：
\zeta = E[(X-\hat X)^T(X-\hat X)]
優(yōu)點(diǎn)：

• 可以使變換后所生成的新分量正交或不相關(guān)
• K-L變換后的協(xié)方差矩陣為對(duì)角矩陣
• 在用較少的新分量來(lái)表示原特征向量時(shí)书斜，可以達(dá)到均方誤差最小

例子：

降維與數(shù)據(jù)壓縮是緊密聯(lián)系在一起的诬辈。如原訓(xùn)練樣本集的數(shù)量為V，而現(xiàn)采用30個(gè)基(每個(gè)基是一幅圖象)荐吉，再加上每幅圖象的描述參數(shù)焙糟，數(shù)據(jù)量是大大降低。尤其是圖象數(shù)很大時(shí)样屠，壓縮量是十分明顯的穿撮。
利用K-L變換進(jìn)行人臉圖象識(shí)別是一個(gè)著名的方法。

1. 其原理十分簡(jiǎn)單痪欲，首先搜集要識(shí)別的人的人臉圖象悦穿，建立人臉圖象庫(kù)，
2. 然后利用K-L變換確定相應(yīng)的人臉基圖象勤揩，
3. 再反過(guò)來(lái)用這些基圖象對(duì)人臉圖象庫(kù)中的有人臉圖象進(jìn)行K-L變換咧党，從而得到每幅圖象的參數(shù)向量并將每幅圖的參數(shù)向量存起來(lái)。
4. 在識(shí)別時(shí)陨亡，先對(duì)一張所輸入的臉圖象進(jìn)行必要的規(guī)范化傍衡，再進(jìn)行K-L變換分析深员，得到其參數(shù)向量。
5. 將這個(gè)參數(shù)向量與庫(kù)中每幅圖的參數(shù)向量進(jìn)行比較蛙埂，找到最相似的參數(shù)向量倦畅，也就等于找到最相似的人臉，從而認(rèn)為所輸入的人臉圖象就是庫(kù)內(nèi)該人的一張人臉, 完成了識(shí)別過(guò)程

注：一個(gè)非周期性隨機(jī)過(guò)程不能用具有互不相關(guān)的隨機(jī)傅立葉系數(shù)的傅立葉級(jí)數(shù)表示绣的，但是可以用具有互不相關(guān)系數(shù)的正交函數(shù)的級(jí)數(shù)展開(kāi)叠赐。K-L展開(kāi)式就是這樣一種展開(kāi)方法。

1 離散有限K-L展開(kāi)

Paste_Image.png

2 基于K-L變換的數(shù)據(jù)壓縮

問(wèn)題：如果從n個(gè)特征向量中選取m個(gè)組成新的變換矩陣屡江，m<n芭概，那么怎么選取m個(gè)特征向量可以在最小均方誤差準(zhǔn)則下效果最優(yōu)？
方法：選擇m個(gè)最大的特征值對(duì)應(yīng)的特征向量組成新的變換矩陣惩嘉，可以讓最小均方誤差最小罢洲。因此，K-L變換又稱為主成分分析文黎。
算法：

1. 平移坐標(biāo)系惹苗，將模式的總體均值向量作為新坐標(biāo)系的原點(diǎn)
2. 求隨機(jī)向量X的自相關(guān)矩陣R=E(XX^T)
3. 求自相關(guān)矩陣的n個(gè)特征值及其對(duì)應(yīng)的特征向量
4. 將特征值從大到小排序，取前m個(gè)大的特征值所對(duì)應(yīng)的特征向量構(gòu)成新的變換矩陣
5. 將n維向量變換為m維新向量

例子：

Paste_Image.png

特征選擇：專家選擇耸峭，刪除部分特征

從一組特征中挑選出一些最有效的特征以達(dá)到降低特征空間維數(shù)的目的桩蓉，這個(gè)過(guò)程叫特征選擇。因此有兩個(gè)關(guān)鍵問(wèn)題：選擇的標(biāo)準(zhǔn)劳闹、搜索的算法

標(biāo)準(zhǔn)：

Paste_Image.png

搜索：

Paste_Image.png

最優(yōu)搜索算法

最優(yōu)搜索算法：至今能得到最優(yōu)解的唯一快速算法是“分支定界”算法院究。屬于自上而下的算法，具有回溯功能玷或。
算法核心是通過(guò)合理組合搜索過(guò)程儡首，避免一些重復(fù)計(jì)算片任。關(guān)鍵是利用了判據(jù)的單調(diào)性偏友。
如果?_i<?_j，則有J(?_i)≤J(?_j)

次優(yōu)搜索算法

順序前進(jìn)法（SFS）最簡(jiǎn)單的自下而上法对供，每次選取一個(gè)位他，使得與已經(jīng)選入的特征組合判據(jù)最大

• 一般說(shuō)來(lái)，由于考慮了特征之間的相關(guān)性产场，在選擇特征時(shí)計(jì)算與比較了組合特征的判據(jù)值鹅髓，要比前者好些。其主要缺點(diǎn)是京景，一旦某一特征被選入窿冯，即使由于后加入的特征使它變?yōu)槎嘤啵矡o(wú)法再把它剔除
• 該法可推廣至每次入選r個(gè)特征确徙，而不是一個(gè)醒串，稱為廣義順序前進(jìn)法(GSFS)执桌。

順序后退法（SBS）最簡(jiǎn)單的自上而下法

• 這是一種與SFS相反的方法，是自上而下的方法芜赌。做法也很簡(jiǎn)單仰挣，從現(xiàn)有的特征組中每次減去一個(gè)不同的特征并計(jì)算其判據(jù)，找出這些判據(jù)值中之最大值缠沈，如此重復(fù)下去直到特征數(shù)達(dá)到予定數(shù)值d為止
  與SFS相比膘壶，此法計(jì)算判據(jù)值是在高維特征空間進(jìn)行的，因此計(jì)算量比較大洲愤。
• 此法也可推廣至每次剔除r個(gè)颓芭，稱為廣義順序后退法（GSBS）

增l減r法在選擇過(guò)程中加入局部的回溯

• 前面兩種方法都有一個(gè)缺點(diǎn)，即一旦特征入選(或剔除)柬赐，過(guò)程不可逆轉(zhuǎn)畜伐。為了克服這種缺點(diǎn)，可采用將這兩種方法結(jié)合起來(lái)的方法躺率，即增l減r法玛界。
• 其原理是對(duì)特征組在增加l個(gè)特征后，轉(zhuǎn)入一個(gè)局部回溯過(guò)程悼吱，又用順序后退法慎框，剔除掉r個(gè)特征。這種方法既可能是“自上而下”方法后添，也可能是“自下而上”的笨枯，這取決于l與r的數(shù)據(jù)大小。當(dāng)l＜r時(shí)遇西，入選特征數(shù)逐漸增加馅精，屬“自下而上”型，反之屬“自上而下”型粱檀。

增 l減r法的推廣

增 l減r法也可推廣至用GSFS及GSBS代替SFS及SBS洲敢，并可在實(shí)現(xiàn)增加l特征時(shí)采用分幾步實(shí)現(xiàn)。增l特征用Z_l步茄蚯，減r則用Z_r步压彭，該種方法一般稱為（Z_l, Z_r）法。這種做法是為了既考慮入選(或剔除)特征之間的相關(guān)性渗常，又不至因此引起計(jì)算量過(guò)大壮不。合理地設(shè)置Z_l與Z_r ，可以同時(shí)對(duì)兩者皱碘，即計(jì)算復(fù)雜性及特征選擇的合理性兼顧考慮询一。

（Z_l, Z_r）算法

前面所講的各種方法都可看作是（Z_l, Z_r）法的特例，它們的關(guān)系如下所示：
Z_l=(1), Z_r=(0)：SFS（1, 0）算法
Z_l=(0), Z_r=(1)：SBS（0, 1）算法
Z_l=(d), Z_r=(0)：窮舉法
Z_l=(l), Z_r=(0)： GSPS(l)算法
Z_l=(0), Z_r=(r)： GSBS(r)算法
Z_l=(1,1,…,1), Z_r=(1,1,…,1)：(l, r)算法

新的優(yōu)化搜索算法

• 遺傳算法：建立在生物進(jìn)化基礎(chǔ)上的，是一種基于自然選擇和群體遺傳機(jī)理的搜索算法健蕊。主要有編碼缓醋、選擇、交換绊诲、變異等操作送粱。參考博客
• 模擬退火算法：從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降掂之，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解抗俄，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。
• Tabu搜索算法：隱含假定一個(gè)解的“鄰域”中往往存在性能更好的解世舰，構(gòu)建Tabu表記錄近期搜索過(guò)的性能較優(yōu)的解动雹。
• 蟻群算法 ant colony optimization, ACO 參考博客
• A*