模式識(shí)別 課件 第8章 特征選擇

第8章特征選擇主要內(nèi)容8.1概述8.2特征的評價(jià)準(zhǔn)則8.3特征選擇的優(yōu)化算法8.4過濾式特征選擇方法8.5包裹式特征選擇方法8.6嵌入式特征選擇方法8.1概述特征選擇從已有特征中挑選出比較重要的、有代表性的、對分類有利的特征，以便降低樣本的維數(shù)，降低分類器設(shè)計(jì)的難度。三個(gè)關(guān)鍵問題對特征的要求，即選擇什么樣的特征具有充分的識(shí)別信息量，即應(yīng)具有充分的可分性。盡可能的獨(dú)立性，重復(fù)的、相關(guān)性強(qiáng)的特征不能提供更多信息，只選一個(gè)。數(shù)量盡量少，同時(shí)損失的信息量小。8.1概述特征選擇的標(biāo)準(zhǔn)：即評價(jià)準(zhǔn)則，衡量特征的可分性、獨(dú)立性、信息量等，簡言之，選出的特征是否有利于分類三個(gè)關(guān)鍵問題特征選擇的方法：即如何進(jìn)行特征選擇利用待識(shí)別對象的特點(diǎn)從特征和分類的角度出發(fā)8.2特征的評價(jià)準(zhǔn)則希望選出的特征最有利于分類，因此利用分類器的性能度量作為特征的評價(jià)準(zhǔn)則，例如，錯(cuò)誤率等。做法：利用不同的特征組合設(shè)計(jì)分類器，計(jì)算分類器的性能度量值，并從中選出分類器性能最好的一組特征。優(yōu)點(diǎn)：選出的特征對于分類器而言針對性較強(qiáng)，性能更好。存在的問題：錯(cuò)誤率的計(jì)算復(fù)雜；計(jì)算量很大。定義便于計(jì)算的類別可分性準(zhǔn)則，以衡量一組特征下類之間的可分程度，也稱為可分性判據(jù)8.2特征的評價(jià)準(zhǔn)則評價(jià)準(zhǔn)則要求與誤判概率有單調(diào)關(guān)系：J最大時(shí)，錯(cuò)誤率最小當(dāng)特征相互獨(dú)立時(shí)，判據(jù)有可加性判據(jù)具有度量特性：具有距離的某些特性對特征數(shù)目是單調(diào)不減的：加入新的特征，不會(huì)使判據(jù)減小8.2特征的評價(jià)準(zhǔn)則（1）基于類內(nèi)類間距離的可分性判據(jù)若樣本可分，必然位于特征空間的不同區(qū)域，這些不同的區(qū)域之間必定有一定的距離，距離越大，分得越開。所以，可以用距離作為模式分布狀態(tài)的測度。距離有多種定義方式，均可以作為類別可分性判據(jù)，常采用歐氏距離。概述8.2特征的評價(jià)準(zhǔn)則相關(guān)散布矩陣定義類內(nèi)散布矩陣：類間散布矩陣：總體類內(nèi)散布矩陣：

混合散布矩陣

8.2特征的評價(jià)準(zhǔn)則可分性判據(jù)

8.2特征的評價(jià)準(zhǔn)則例題

8.2特征的評價(jià)準(zhǔn)則

8.2特征的評價(jià)準(zhǔn)則判據(jù)優(yōu)缺點(diǎn)計(jì)算方便直觀概念清楚沒有考慮各類的概率分布，不能確切表明各類重疊情況，與錯(cuò)誤概率沒有直接聯(lián)系8.2特征的評價(jià)準(zhǔn)則（2）基于概率分布的可分性判據(jù)

概述8.2特征的評價(jià)準(zhǔn)則

散度8.2特征的評價(jià)準(zhǔn)則常用的概率距離度量

散度

對數(shù)似然比

8.2特征的評價(jià)準(zhǔn)則Chernoff界限s∈[0,1]Bhattacharyya距離

這些量表達(dá)了兩類模式的差異性，并且具有距離函數(shù)的性質(zhì)，稱為概率距離度量。8.2特征的評價(jià)準(zhǔn)則例題

8.2特征的評價(jià)準(zhǔn)則

8.2特征的評價(jià)準(zhǔn)則（3）基于熵函數(shù)的可分性判據(jù)概述

用具有最小不確定性的特征進(jìn)行分類最為有利。8.2特征的評價(jià)準(zhǔn)則熵在信息論中，熵表示不確定性，熵越大不確定性越大。Shannon熵：廣義熵：基于熵的可分性判據(jù)

JE越小，可分性越好。8.2特征的評價(jià)準(zhǔn)則相對熵：交叉熵：

8.2特征的評價(jià)準(zhǔn)則（4）基于統(tǒng)計(jì)檢驗(yàn)的可分性判據(jù)采用統(tǒng)計(jì)檢驗(yàn)的方法可以檢驗(yàn)?zāi)骋蛔兞吭趦深悩颖鹃g是否存在顯著差異，給出統(tǒng)計(jì)量反映這種差別，在兩類間有顯著差異的特征有利于分類。u-檢驗(yàn)t-檢驗(yàn)秩和檢驗(yàn)8.2特征的評價(jià)準(zhǔn)則（5）特征的相關(guān)性評價(jià)Pearson相關(guān)系數(shù)

Spearman秩相關(guān)系數(shù)

相關(guān)系數(shù)8.2特征的評價(jià)準(zhǔn)則互信息

8.3特征選擇的優(yōu)化算法（1）概述窮舉法（全局最優(yōu)搜索）從n個(gè)特征中挑出m個(gè)，列舉所有可能的組合，計(jì)算每個(gè)J，以選擇最優(yōu)特征組計(jì)算量太大采用某些搜索技術(shù)使計(jì)算量有所降低非窮舉法不能保證結(jié)果最優(yōu)8.3特征選擇的優(yōu)化算法（2）分支定界算法（BranchAndBound）一種自上而下方法，從包含所有候選特征開始，逐步去掉不被選中的特征，具有回溯功能通過合理地組織搜索過程，使得有可能避免計(jì)算某些特征組合而不影響結(jié)果為最優(yōu)主要利用可分離性判據(jù)的單調(diào)性整個(gè)搜索過程可用樹表示出來，稱為搜索樹或解樹基本思想8.3特征選擇的優(yōu)化算法例題

8.3特征選擇的優(yōu)化算法

8.3特征選擇的優(yōu)化算法

0

確定后繼節(jié)點(diǎn)要舍棄的特征8.3特征選擇的優(yōu)化算法

0

8.3特征選擇的優(yōu)化算法

0

8.3特征選擇的優(yōu)化算法

0

8.3特征選擇的優(yōu)化算法最終搜索樹完整的搜索樹8.3特征選擇的優(yōu)化算法避免了部分m個(gè)特征組合的判據(jù)計(jì)算，與窮舉相比節(jié)約了時(shí)間由于搜索過程中要計(jì)算中間的判據(jù)，在m很小或很接近n時(shí)，不如使用窮舉法必須采用具有單調(diào)性的判據(jù)理論上具有單調(diào)性的判據(jù)，在實(shí)際運(yùn)用樣本計(jì)算時(shí)，可能不再具備單調(diào)性算法分析對每一個(gè)特征單獨(dú)計(jì)算類別可分性判據(jù)，根據(jù)單個(gè)特征的判據(jù)值排隊(duì)，選擇其中前m個(gè)特征前提假設(shè)是單獨(dú)作用時(shí)性能最優(yōu)的特征，組合起來也是性能最優(yōu)的與很多實(shí)際情況不相符單獨(dú)最優(yōu)特征的組合（3）特征選擇的次優(yōu)算法8.3特征選擇的優(yōu)化算法順序前進(jìn)法Sequentialforwardselection，SFS從底向上的方法，第一個(gè)特征選擇單獨(dú)最優(yōu)的特征，第二個(gè)特征從其余特征中選擇與第一個(gè)特征組合在一起后準(zhǔn)則最優(yōu)的特征，后面每一個(gè)特征都選擇與已經(jīng)入選的特征組合起來最優(yōu)的特征第一個(gè)特征僅靠單個(gè)特征的準(zhǔn)則選擇特征一旦入選無法剔除，即使它與后面選擇的特征并不是最優(yōu)的組合廣義順序前進(jìn)法，每一次不是選擇一個(gè)新特征，而是選擇l個(gè)新特征8.3特征選擇的優(yōu)化算法順序后退法Sequentialbackwardselection，SBS從頂向下的方法，從所有特征開始注意剔除不被選中的特征，每次剔除的特征都是使得剩余的特征的準(zhǔn)則函數(shù)值最優(yōu)的特征因?yàn)閺捻斚蛳?，很多?jì)算在高維空間進(jìn)行，計(jì)算量比順序前進(jìn)法大特征一旦剔除無法再選入廣義順序后退法，每一次不是剔除一個(gè)特征，而是剔除r個(gè)新特征8.3特征選擇的優(yōu)化算法結(jié)合SFS和SBS方法，在選擇或剔除過程引入一個(gè)回溯的步驟，使得依據(jù)局部準(zhǔn)則選擇或剔除的特征因?yàn)榕c其他特征間的組合而重新被考慮從底向上時(shí)，l>r，首先逐步增選l個(gè)特征，然后再逐步剔除r個(gè)與其他特征組合起來準(zhǔn)則最差的特征，依此類推，直到選擇到所需要數(shù)目的特征從頂向下時(shí)，l<r，首先逐步剔除r個(gè)特征，然后再從已經(jīng)被剔除的特征中逐步選擇l個(gè)與其他特征組合起來準(zhǔn)則最優(yōu)的特征，直到剩余的特征數(shù)目達(dá)到所需的數(shù)目增l減r法8.3特征選擇的優(yōu)化算法（4）特征選擇的啟發(fā)算法模仿自然界退火現(xiàn)象而得，利用了物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性，從某一初始溫度開始，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找全局最優(yōu)解啟發(fā)式算法（HeuristicAlgorithm），一類得到近似最優(yōu)解的優(yōu)化算法，基于直觀或經(jīng)驗(yàn)構(gòu)造，在可接受的計(jì)算代價(jià)下，給出優(yōu)化問題每個(gè)實(shí)例的一個(gè)可行解，但多數(shù)情況下不能得到最優(yōu)解，也無法描述解與最優(yōu)解的近似程度。8.3特征選擇的優(yōu)化算法模擬退火（SimulatedAnnealingAlgorithm）起源于生物進(jìn)化的思想，物競天擇，適者生存。應(yīng)用于數(shù)學(xué)上的優(yōu)化問題：將每一個(gè)可能的解看作群體中的一個(gè)個(gè)體，生成群體根據(jù)預(yù)定的目標(biāo)函數(shù)對群體中每個(gè)個(gè)體進(jìn)行評價(jià)，給出一個(gè)適應(yīng)度值通過遺傳算子對個(gè)體進(jìn)行選擇、交叉和變異操作，得到一個(gè)新群體不斷重復(fù)遺傳、變異過程，一代比一代適應(yīng)度更高經(jīng)過若干代，找出最優(yōu)的個(gè)體作為優(yōu)化問題的解8.3特征選擇的優(yōu)化算法遺傳算法（GeneticAlgorithm，GA）模擬系統(tǒng)利用局部信息從而可以產(chǎn)生不可預(yù)測的群行為。蟻群算法：模擬自然界螞蟻的覓食過程，基于信息正反饋原理尋找最優(yōu)解粒子群優(yōu)化算法：源于對鳥群捕食行為的研究，通過群體中個(gè)體之間的協(xié)作和信息共享來尋找最優(yōu)解8.3特征選擇的優(yōu)化算法群智能算法（SwarmIntelligence）8.4過濾式特征選擇方法先進(jìn)行特征選擇，再訓(xùn)練分類器，特征選擇過程和后續(xù)分類器設(shè)計(jì)無關(guān)。特征選擇時(shí)，需要先選定特征的評價(jià)準(zhǔn)則，在特征集合中進(jìn)行尋優(yōu)，找到最優(yōu)的特征組合。8.4過濾式特征選擇方法利用互信息實(shí)現(xiàn)冗余度和關(guān)聯(lián)度的量化度量，找出與類別標(biāo)簽之間關(guān)聯(lián)最大、特征之間冗余最小的特征組合典型方法最小冗余最大相關(guān)（MinimumRedundancyMaximumRelevance，MRMR）算法根據(jù)各個(gè)特征和類別的相關(guān)性賦予特征不同的權(quán)重，再根據(jù)要選擇的特征個(gè)數(shù)或者權(quán)重閾值選擇若干個(gè)權(quán)重大的特征。Relief和ReliefF算法8.5包