特征選擇算法綜述20160702

1、特征選擇方法綜述控制與決策2012.2問(wèn)題的提出特征選擇框架基于搜索策略劃分特征選擇方法基于評(píng)價(jià)準(zhǔn)則劃分特征選擇方法結(jié)論一、問(wèn)題的提出特征選擇是從一組特征中挑選出一些最有效的特征以降低特征空間維數(shù)的 過(guò)程，是模式識(shí)別的關(guān)鍵問(wèn)題之一。對(duì)于模式識(shí)別系統(tǒng)，一個(gè)好的學(xué)習(xí)樣本是訓(xùn) 練分類器的關(guān)鍵，樣本中是否含有不相關(guān)或冗余信息直接影響著分類器的性能。 因此研究有效的特征選擇方法至關(guān)重要。特征選擇算法的目的在于選擇全體特征的一個(gè)較少特征集合，用以對(duì)原始數(shù) 據(jù)進(jìn)行有效表達(dá)按照特征關(guān)系度量劃分，可分為依賴基尼指數(shù)、歐氏距離、信息 熵。二特征選擇框架圖1特征選擇的基本框架由于子集搜索是一個(gè)比較費(fèi)時(shí)的步驟，一些學(xué)

2、者基于相關(guān)和冗余分析，給 出了下面一種特征選擇框架，避免了子集搜索，可以高效快速地尋找最優(yōu)子集。原始數(shù)據(jù)相關(guān)分析冗余分析最終選擇的子匕圖2改進(jìn)的特征選擇框架從特征選擇的基本框架看出，特征選擇方法中有4個(gè)基本步驟:候選特征子集的生成（搜 索策略）、評(píng)價(jià)準(zhǔn)則、停止準(zhǔn)則和驗(yàn)證方法。目前對(duì)特征選擇方法的研究主要集中于搜索策 略和評(píng)價(jià)準(zhǔn)則。因而，本文從搜索策略和評(píng)價(jià)準(zhǔn)則兩個(gè)角度對(duì)特征選擇方法進(jìn)行分類。三、基于搜索策略劃分特征選擇方法基本的搜索策略按照特征子集的形成過(guò)程，形成的特征選擇方法如下:圖3基于搜索策略劃分特征選擇方法其中，全局搜索如分支定界法，存在問(wèn)題：1）很難確定優(yōu)化特征子集的數(shù)目；2）滿足單

3、調(diào)性的可分性判據(jù)難以設(shè)計(jì)；3）處理高維多類問(wèn)題時(shí)，算法的時(shí)間復(fù)雜度較高。隨機(jī)搜索法如模擬退火、遺傳算法、禁忌搜索算法等，存在問(wèn)題：1）具有較高的不確定性，只有當(dāng)總循環(huán)次數(shù)較大時(shí)，才可能找到較好的結(jié)果。2）在隨機(jī)搜索策略中，可能需對(duì)一些參數(shù)進(jìn)行設(shè)置，參數(shù)選擇的合適與否對(duì)最終結(jié)果 的好壞起著很大的作用。啟發(fā)式搜索如SFS、SBS、SFFS、SFBS等，存在問(wèn)題：1）雖然效率高，但是它以犧牲全局最優(yōu)為代價(jià)。每種搜索策略都有各自的優(yōu)缺點(diǎn)，在實(shí)際應(yīng)用過(guò)程中，根據(jù)具體環(huán)境和準(zhǔn)則函數(shù)來(lái)尋找 一個(gè)最佳的平衡點(diǎn)。例如，特征數(shù)較少，可采用全局最優(yōu)搜索策略；若不要求全局最優(yōu)，但 要求計(jì)算速度快，可采用啟發(fā)式策略；若

4、需要高性能的子集，而不介意計(jì)算時(shí)間，則可采用 隨機(jī)搜索策略。四、基于評(píng)價(jià)準(zhǔn)則劃分特征選擇方法圖4基于評(píng)價(jià)準(zhǔn)則劃分特征選擇方法（一）考慮單個(gè)特征對(duì)分類的貢獻(xiàn)，特征選擇方法依據(jù)其與分類器的關(guān)系分為： Filter方法、Wrapper方法和Embedded方法3類。封裝式算法作為一種經(jīng)典的特征選擇算法類型采用學(xué)習(xí)算法進(jìn)行特征選擇， 其選擇過(guò)程復(fù)雜耗時(shí)，目前多與過(guò)濾式特征選擇算法結(jié)合，輔助特征選擇；嵌入 式算法則分多步驟采用不同選擇方式，算法繁瑣，其代表算法是基于稀疏多項(xiàng)式 邏輯回歸模型理論的SBMLR算法等；過(guò)濾式算法不需其他學(xué)習(xí)算法，主要考察特 征間計(jì)量關(guān)系，方法簡(jiǎn)單，時(shí)間復(fù)雜度相對(duì)較低，代表算法

5、包括：基于特征權(quán)重 的Relief F、Fisher、SPEC以及基于互信息的MRMR算法等。(1) Filter方法：通過(guò)分析特征子集內(nèi)部的信息來(lái)衡量特征子集的好壞，不依 賴于分類器。Filter實(shí)質(zhì)上屬于一種無(wú)導(dǎo)師學(xué)習(xí)算法。常用：基于特征權(quán)重的Relief F、Fisher、SPEC以及基于互信息的MRMR算法Filter特征選擇方法一般使用評(píng)價(jià)準(zhǔn)則來(lái)增強(qiáng)特征與類的相關(guān)性，削減特 征之間的相關(guān)性。將評(píng)價(jià)函數(shù)分成4類：1)距離度量。距離度量通常也認(rèn)為是分離性、差異性或者辨識(shí)能力的度量。 最為常用的一些重要距離測(cè)度：歐氏距離、S階Minkowski測(cè)度、Chebychev距 離、平方距離等。2

6、)信息度量。信息度量通常采用信息增益(IG)或互信息(MI)衡量。信息增益：有無(wú)這個(gè)特征對(duì)分類問(wèn)題的影響的大小?；バ畔ⅲ好枋鰞蓚€(gè)隨機(jī)變量之間相互依存關(guān)系的強(qiáng)弱。泛化的信息度量函數(shù)標(biāo)準(zhǔn)：j(f) = a - 力 S) R其中，C：類別；f：候選特征；5：已選特征；g(C,f,S)： C，f，S之間的信息量；。：調(diào)控系數(shù)；6：懲罰因子BIF (best individual feature)是一種最簡(jiǎn)單最直接的特征選擇方法。 評(píng)價(jià)函數(shù)：I()：互信息降序排序前k個(gè)優(yōu)缺點(diǎn)：這種方法簡(jiǎn)單快速，適合于高維數(shù)據(jù)。沒(méi)有考慮到所選特征間的相關(guān)性，會(huì)帶來(lái) 較大的冗余。 MIFS (mutual informat

7、ion feature selection)：互信息特征選擇。使用候選特征f與單 個(gè)已選特征s相關(guān)性對(duì)f進(jìn)行懲罰的方法。B：調(diào)節(jié)系數(shù)。B在0.5，時(shí)，算法性能較好。 mRMR (minimal-redundancy and maximal-relevance)方法。思想：最大化特征子集和 類別的相關(guān)性，最小化特征之間的冗余。J=/)白 1(8 ，&esJ(/) = 1*FCBF (fast correlation-based filter)。基于相互關(guān)系度量給出的一種算法。對(duì)于線性隨 機(jī)變量，用相關(guān)系數(shù)分析特征與類別、特征間的相互關(guān)系。對(duì)于非線性隨機(jī)變量，采用對(duì)稱 不確定性(SU)來(lái)度量，對(duì)于

8、兩個(gè)非線性隨機(jī)變量X和Y，它們的相互關(guān)系表示為：SU(X, F) = 2IG(XY)H()：信息熵基本思想：根據(jù)所定義的C-相關(guān)(特征與類別的相互關(guān)系)和F-相關(guān)(特征之間的相 互關(guān)系)，從原始特征集合中去除C-相關(guān)值小于給定閾值的特征，再對(duì)剩余的特征進(jìn) 行冗余分析。 CMIM (conditional mutual information maximization)。利用條件互信息來(lái)評(píng)價(jià)特征 的重要性程度，即在已知已選特征集S的情況下通過(guò)候選特征f與類別C的依賴程度來(lái)確定f的重要性，其中條件互信息I(C IS)值越大，f能提供的新信息越多。J=arg minI(C;/|S3)依賴性度量。有許

9、多統(tǒng)計(jì)相關(guān)系數(shù)被用來(lái)表達(dá)特征相對(duì)于類別可分離性 間的重要性程度。如：Pearson相關(guān)系數(shù)、概率誤差、Fisher分?jǐn)?shù)、先行可判定 分析、最小平方回歸誤差、平方關(guān)聯(lián)系數(shù)、t-test、F-Statistic等。Hilbert-Schmidt依賴性準(zhǔn)則(HSIC)可作為一個(gè)評(píng)價(jià)準(zhǔn)則度量特征與類別 的相關(guān)性。核心思想是一個(gè)好的特征應(yīng)該最大化這個(gè)相關(guān)性。To = argmaxJfS), s+t+ S W 九SUFt:所選特征個(gè)數(shù)上限；F：特征集合；5：已選特征集合；J(S)：評(píng)價(jià)準(zhǔn)則 從式中可知需要解決兩個(gè)問(wèn)題：一是評(píng)價(jià)準(zhǔn)則J(S)的選擇；二是算法的選擇。4)一致性度量給定兩個(gè)樣本,若他們特征值均相

10、同，但所屬類別不同,則稱它們是不一致 的;否則，是一致的。試圖保留原始特征的辨識(shí)能力,找到與全集有同樣區(qū)分類別 能力的最小子集。典型算法有Focus、LVF等。Filter方法選擇合適的準(zhǔn)則函數(shù)將會(huì)得到較好的分類結(jié)果。優(yōu)點(diǎn)：可以很快地排除很大數(shù)量的非關(guān)鍵性的噪聲特征,縮小優(yōu)化特征子集 搜索的規(guī)模,計(jì)算效率高,通用性好,可用作特征的預(yù)篩選器。缺點(diǎn)：它并不能保證選擇出一個(gè)優(yōu)化特征子集,尤其是當(dāng)特征和分類器息息 相關(guān)時(shí)。因而，即使能找到一個(gè)滿足條件的優(yōu)化子集,它的規(guī)模也會(huì)比較龐大,會(huì) 包含一些明顯的噪聲特征。2）Wrapper法：評(píng)價(jià)函數(shù)是一個(gè)分類器，采用特定特征子集對(duì)樣本集進(jìn)行分類， 根據(jù)分類的結(jié)

11、果來(lái)衡量該特征子集的好壞。Wrapper實(shí)質(zhì)上是一種有導(dǎo)師學(xué)習(xí)算法。訓(xùn)練集測(cè)試集優(yōu)點(diǎn)：準(zhǔn)確率高缺點(diǎn)：1）為選擇出性能最好的特征子集，Wrapper算法需要的計(jì)算量巨大；2）該方法所選擇的特征子集依賴于具體學(xué)習(xí)機(jī)；3）容易產(chǎn)生“過(guò)適應(yīng)”問(wèn)題，推廣性能較差（3）Embedded方法。將特征選擇集成在學(xué)習(xí)機(jī)訓(xùn)練過(guò)程中，通過(guò)優(yōu)化一個(gè) 目標(biāo)函數(shù)在訓(xùn)練分類器的過(guò)程中實(shí)現(xiàn)特征選擇。優(yōu)點(diǎn)：相對(duì)于Wrapper方法，不用將訓(xùn)練數(shù)據(jù)集分成訓(xùn)練集和測(cè)試集兩部分， 避免了為評(píng)估每一個(gè)特征子集對(duì)學(xué)習(xí)機(jī)所進(jìn)行的從頭開(kāi)始的訓(xùn)練，可以快速地得 到最佳特征子集，是一種高效的特征選擇方法。缺點(diǎn)：構(gòu)造一個(gè)合適的函數(shù)優(yōu)化模型是該方法

12、的難點(diǎn)。通常，將Filter方法的高效與Wrapper方法的高準(zhǔn)確率進(jìn)行結(jié)合，可得到 更優(yōu)的特征子集?；旌咸卣鬟x擇過(guò)程一般由兩個(gè)階段組成：1）使用Filter方法初步剔除大部分無(wú)關(guān)或噪聲特征,只保留少量特征,從而 有效地減小后續(xù)搜索過(guò)程的規(guī)模。2）將剩余的特征連同樣本數(shù)據(jù)作為輸入?yún)?shù)傳遞給Wrapper選擇方法，以進(jìn) 一步優(yōu)化選擇重要的特征。（二）依據(jù)特征之間的聯(lián)合作用對(duì)分類的貢獻(xiàn)，分為：CFS（Correltion based Feature Selector）、CFSPabs（CFS based on the absolute of Perons s correlation coeffic

13、ient）、 DFS（Discernibility of Feature Subsets）。（1）CFS：基于關(guān)聯(lián)特征的特征選擇。CFS計(jì)算整個(gè)特征子集的類間區(qū)分 能力實(shí)現(xiàn)特征選擇，使得被選特征子集中的特征之間盡可能不相關(guān)，而與類標(biāo)高 度相關(guān)。Jk + k（k Ms：度量了包含k個(gè)特征的特征子集S的類別辨識(shí)能力。:特征f （f ）與類別C的相關(guān)系數(shù)的均值:特征之間相關(guān)系數(shù)的均值分子：特征子集S的類預(yù)測(cè)能力分母：特征子集S中特征的冗余程度適合于二分類（2）CFSPabs：基于皮爾森相關(guān)系數(shù)的絕對(duì)值的相關(guān)特征選擇。J _-N 乙V（3）DFS：特征子集區(qū)分度量。工：當(dāng)前i個(gè)特征的特征子集在整個(gè)數(shù)據(jù)集上的均值向量K :當(dāng)前i個(gè)特征的特征子集在第j類數(shù)據(jù)集上的均值向量.:第j類中第k個(gè)樣本對(duì)應(yīng)當(dāng)前i個(gè)特征的特征值向量分子：1個(gè)類別中各類別對(duì)