常見(jiàn)特征選擇算法20160711

1、我們畢業(yè)啦 其實(shí)是答辯的標(biāo)題地方 常見(jiàn)特征選擇算法 什么是特征選擇？ 模式識(shí)別系統(tǒng)的輸入時(shí)傳感器對(duì)實(shí)物或過(guò)程進(jìn)行測(cè)量所得到 的數(shù)據(jù)，其中有些數(shù)據(jù)可以直接作為特征，有一些需要經(jīng)過(guò) 處理之后作為特征，這樣的一組特征一般為原始特征原始特征。 在原始特征中，并不一定每個(gè)特征都有用，從原始特征集合 中選擇對(duì)分類(lèi)結(jié)果有用的特征的過(guò)程稱(chēng)為特征選擇。 比如在識(shí)別蘋(píng)果和橙子的系統(tǒng)中，我們可以抽取的特征很多 （體積、重量、顏色、高度、寬度、最寬處高度），在這些特 征中有用的是（顏色、高度、最寬處高度），其它特征對(duì)識(shí)別 意義不大，所以去掉。 為什么進(jìn)行特征選擇？ 在機(jī)器學(xué)習(xí)的實(shí)際應(yīng)用中，特征數(shù)量往往較多，其中可能

2、存在不相關(guān)的特征，特征之間也可能存在相互依賴(lài)，容易 導(dǎo)致如下的后果： 特征個(gè)數(shù)越多，分析特征、訓(xùn)練模型所需的時(shí)間就越長(zhǎng)。 特征個(gè)數(shù)越多，容易引起“維度災(zāi)難”，模型也會(huì)越復(fù) 雜，其推廣能力會(huì)下降。 特征選擇能剔除不相關(guān)(irrelevant)或亢余(redundant )的特 征，從而達(dá)到減少特征個(gè)數(shù)，提高模型精確度，減少運(yùn)行 時(shí)間的目的。另一方面，選取出真正相關(guān)的特征簡(jiǎn)化了模 型，使研究人員易于理解數(shù)據(jù)產(chǎn)生的過(guò)程。 特征選擇和特征抽取區(qū)別？ 模式識(shí)別中特征降維方法有兩種：特征抽取特征抽取和特征選擇特征選擇 特征提取 ( Feature extraction ) 是指利用已有的特征計(jì)算出一個(gè)抽

3、象程度更高的特征集。對(duì)已有特征 集合進(jìn)行映射變換得到。 PCA、LDA 特征選擇也叫特征子集選擇 ( FSS , Feature Subset Selection ) 或?qū)?性選擇( Attribute Selection )。 特征選擇實(shí)質(zhì)是從原始數(shù)據(jù)集中選 取最優(yōu)子集的過(guò)程。 特征選擇一般流程 A. 產(chǎn)生過(guò)程( Generation Procedure )：按一定的搜索策略搜索策略產(chǎn)生候選特征 子集。 B. 評(píng)價(jià)函數(shù)( Evaluation Function ) ：通過(guò)某個(gè)評(píng)價(jià)函數(shù)評(píng)價(jià)函數(shù)來(lái)評(píng)估特征子集 的優(yōu)劣。 C. 停止準(zhǔn)則( Stopping Criterion )：停止準(zhǔn)則是與評(píng)價(jià)

4、函數(shù)相關(guān)的，一般是 一個(gè)閾值，當(dāng)評(píng)價(jià)函數(shù)值達(dá)到這個(gè)閾值后就可停止搜索。 D. 子集驗(yàn)證：用來(lái)驗(yàn)證最終所選子集的有效性。 評(píng)價(jià)函數(shù) 評(píng)價(jià)函數(shù)通常用來(lái)評(píng)估某個(gè)特征或特征子集分類(lèi)的能力。 最優(yōu)特征子集產(chǎn)生和評(píng)價(jià)函數(shù)是相關(guān)的，不同評(píng)價(jià)函數(shù) 可能產(chǎn)生不同的最優(yōu)特征子集。 將評(píng)價(jià)函數(shù)分為兩類(lèi)：filter和wrapper。 用符號(hào)J ( Y )來(lái)表示評(píng)價(jià)函數(shù)，其中Y是一個(gè)特征集，J( Y ) 越大表示特征集Y越好 Filter：通過(guò)分析特 征子集內(nèi)部的信息來(lái) 衡量特征子集的好壞。 評(píng)價(jià)準(zhǔn)則 Wrapper：評(píng)價(jià)函數(shù)是一個(gè)分 類(lèi)器，采用特定特征子集對(duì)樣 本集進(jìn)行分類(lèi)，根據(jù)分類(lèi)的結(jié) 果來(lái)衡量該特征子集的好壞

5、評(píng)價(jià)函數(shù)-Filter 距離或可分性度量距離或可分性度量：距離度量有時(shí)候也稱(chēng)作類(lèi)別可分離 判據(jù)、離散度準(zhǔn)則,在統(tǒng)計(jì)模式識(shí)別中對(duì)類(lèi)別的可分離性 研究的比較深入。 -歐幾里得距離、馬氏距離、巴氏距離等 相關(guān)性度量：相關(guān)性度量：用來(lái)度量特征和類(lèi)別之間的相關(guān)性。 -相關(guān)系數(shù) 信息論度量：信息論度量： -信息增益、最小描述長(zhǎng)度、互信息 Filter-距離度量 距離度量，是基于這樣的假設(shè)：好的特征子集應(yīng)該使得 屬于同一類(lèi)的樣本距離盡可能小，屬于不同類(lèi)的樣本之 間的距離盡可能遠(yuǎn)。 常見(jiàn)的有歐氏距離、馬氏距離、巴 氏距離等等。 Filter-相關(guān)系數(shù) 運(yùn)用相關(guān)性來(lái)度量特征子集的好壞是基于這樣一個(gè)假設(shè)： 好的特

6、征子集所包含的特征應(yīng)該是與分類(lèi)的相關(guān)度較高 （相關(guān)度高），而特征之間相關(guān)度較低的（亢余度低）。 可以使用線(xiàn)性相關(guān)系數(shù)(correlation coefficient) 來(lái)衡量向 量之間線(xiàn)性相關(guān)度。 Filter-信息增益（1） 通過(guò)計(jì)算特征的信息增益來(lái)對(duì)特征進(jìn)行評(píng)價(jià)。 信息熵：假設(shè)存在離散變量Y，Y中可能的取值包括y1， y2，.，ym ，yi出現(xiàn)的概率為Pi。則Y的信息熵定義為： 條件信息熵：附加條件X=Xi后，Y的條件信息熵變?yōu)椋?信息增益：加入條件X前后的信息熵之差。 Filter-信息增益（2） 對(duì)于分類(lèi)系統(tǒng)來(lái)說(shuō)，類(lèi)別C是變量，他可能的取值為 C1,C2,Cn,而每個(gè)類(lèi)別出現(xiàn)的概率是P

7、(Ci),分類(lèi)系統(tǒng)的 信息熵為： 當(dāng)新加入一個(gè)特征Fj后，系統(tǒng)的信息熵變?yōu)椋?增加F特征前后的信息增益為： 假設(shè)存在特征子集A和特征子集B，分類(lèi)變量為C，若 IG( C|A ) IG( C|B ) ，則認(rèn)為選用特征子集A的分類(lèi)結(jié)果 比B好，因此傾向于選用特征子集A。 Filter和Wrapper優(yōu)缺點(diǎn) 評(píng)價(jià)準(zhǔn)則優(yōu)點(diǎn)缺點(diǎn) filter 快速執(zhí)行； 易于推廣； 準(zhǔn)確率方面通常低于 Wrapper方法； wrapper準(zhǔn)確率高； 計(jì)算代價(jià)大； 不易于推廣； 搜索策略 窮舉算法：窮舉算法：對(duì)特征空間進(jìn)行窮舉搜索（當(dāng)然也會(huì)采用剪 枝等優(yōu)化），搜索出來(lái)的特征集對(duì)于樣本集是最優(yōu)的。 這類(lèi)算法的時(shí)間復(fù)雜度是指

8、數(shù)級(jí)的。 序列算法：序列算法：這類(lèi)算法實(shí)際上是一種貪心算法，算法時(shí)間 復(fù)雜度較低，但是可能會(huì)陷入局部最優(yōu)值，不一定能找 到全局最優(yōu)解。 隨機(jī)算法：隨機(jī)算法：隨機(jī)算法屬于一種近似算法，能找出問(wèn)題的 近似最優(yōu)解。每個(gè)隨機(jī)算法都需要設(shè)置一定的參數(shù)，這 些參數(shù)的選擇很重要。 搜索策略 窮舉算法：窮舉搜索 Exhaustive Search (ES) 分支限界法 Branch and Bound (Bk=k+1 go to Step 3 else go to Step 2 三種搜索算法對(duì)比 搜索策略?xún)?yōu)點(diǎn)缺點(diǎn) 窮舉算法 能夠得到全局最 優(yōu)解； 算法復(fù)雜，耗費(fèi) 時(shí)間； 序列算法 實(shí)現(xiàn)簡(jiǎn)單，執(zhí)行 效率高； 不

9、能回溯 隨機(jī)算法 避免陷入局部最 優(yōu)解 模型參數(shù)選擇比 較難 參考文獻(xiàn) 1 Doak J, Doak J. An evaluation of feature selection methods and their application to computer securityJ. Uc Davis Dept of Computer Science Tech Reports, 1992. Dash M, Liu H. Feature selection for classificationJ. Intelligent Data Analysis, 2010, 1(s 14):131-156. 毛勇, 周曉波, 夏錚,等. 特征選擇算法研究綜述J. 模式識(shí) 別與人工智能, 2007, 20(2):211-218. Ricardo Gutierrez-Osuna, Introduction to Pattern Analysis ( L11: Sequential Feature Selection and L12: randomized fe