特征選擇綜述

1、特征選擇常用算法綜述特征選擇常用算法綜述一.什么是特征選擇什么是特征選擇(Featureion(Featureion)特征選擇也叫特征子集選擇(FSSFeatureSubsetion)。是指從已有的M個特征(Feature)中選擇N個特征使得系統(tǒng)的特定指標(biāo)最優(yōu)化。需要區(qū)分特征選擇與特征提取。特征提取(Featureextraction)是指利用已有的特征計(jì)算出一個抽象程度更高的特征集，也指計(jì)算得到某個特征的算法。特征提取與特征選擇都能降

2、低特征集的維度。評價(jià)函數(shù)評價(jià)函數(shù)(ObjectiveObjectiveFunctionFunction)，用于評價(jià)一個特征子集的好壞的指標(biāo)。這里用符號J(Y)來表示評價(jià)函數(shù)，其中Y是一個特征集，J(Y)越大表示特征集Y越好。評價(jià)函數(shù)根據(jù)其實(shí)現(xiàn)原理又分為2類，所謂的Filter和Wrapper。FilterFilter（篩選器）（篩選器）：通過分析特征子集內(nèi)部的信息來衡量特征子集的好壞，比如特征間相互依賴的程度等。Filter實(shí)質(zhì)上屬于一

3、種無導(dǎo)師學(xué)習(xí)算法。WrapperWrapper（封裝器）（封裝器）：這類評價(jià)函數(shù)是一個分類器，采用特定特征子集對樣本集進(jìn)行分類，根據(jù)分類的結(jié)果來衡量該特征子集的好壞。Wrapper實(shí)質(zhì)上是一種有導(dǎo)師學(xué)習(xí)算法。二.為什么要進(jìn)行特征選擇？為什么要進(jìn)行特征選擇？獲取某些特征所需的計(jì)算量可能很大，因此傾向于選擇較小的特征集特征間的相關(guān)性，比如特征A完全依賴于特征B，如果我們已經(jīng)將特征B選入特征集，那么特征A是否還有必要選入特征集？我認(rèn)為是不必的

4、。特征集越大，分類器就越復(fù)雜，其后果就是推廣能力（generalizationcapability）下降。選擇較小的特征集會降低復(fù)雜度，可能會提高系統(tǒng)的推廣能力。LessisMe!三.特征選擇算法分類特征選擇算法分類精確的解決特征子集選擇問題是一個指數(shù)級的問題。常見特征選擇算法可以歸為下面3類：第一類：指數(shù)算法(Exponentialalgithms)這類算法對特征空間進(jìn)行窮舉搜索（當(dāng)然也會采用剪枝等優(yōu)化），搜索出來的特征集對于樣本集是

5、最優(yōu)的。這類算法的時(shí)間復(fù)雜度是指數(shù)級的。1，2，3，4，5這3類，特征C只能將其分為1，2，3，4，5這2類。那么顯然最優(yōu)特征是A，然后是B，最后是C，樸素序列特征選擇算法會選擇特征A和B，但是特征A和B并不能區(qū)分4和5類。其實(shí)最優(yōu)選擇應(yīng)該是A和C，只有特征A和C能將5類區(qū)分開來。2.2.序列前向選擇序列前向選擇(SFSSFSSequentialSequentialFwardFwardionion)算法描述：每次選擇一個特征x加入特征子

6、集Y，使得特征函數(shù)J(Yx)最大。簡單說就是，每次都選擇一個使得特征函數(shù)的取值達(dá)到最優(yōu)的特征加入，其實(shí)就是一種簡單的貪心算法。“前向”的意思就是這個算法只能加入特征而不能去除特征。算法評價(jià)：缺點(diǎn)是只能加入不能去除，例如：特征A完全依賴于特征B與C，可以認(rèn)為如果加入了特征B與C則A就是多余的。假設(shè)序列前向選擇算法首先將A加入特征集，然后又將B與C加入，那么特征子集中就包含了多余的特征A。3.3.序列后向選擇序列后向選擇(SBSSBSSeq

7、uentialSequentialBackwardBackwardionion)算法描述：首先將全部特征加入特征集合Y，然后每次從特征集Y中去除一個特征x，使得J(Yx)最優(yōu)?！昂笙颉钡囊馑季褪翘卣髦荒苋コ荒芗尤?。算法評價(jià)：序列后向選擇與序列前向選擇正好相反，它的缺點(diǎn)是特征只能去除不能加入。4.4.增L去R選擇算法選擇算法(LRSLRSPlusLPlusLMinusRionMinusRion)算法描述：該算法有兩種形式。當(dāng)LR，算法

8、從空集開始，每輪先加入L個特征，然后從中去除R個特征，使得J(Y)最大。當(dāng)LR，算法從全集開始，每輪先去除R個特征，然后加入L個特征，使得J(Y)最大。算法評價(jià)：增L去R選擇算法結(jié)合了序列前向選擇與序列后向選擇思想，L與R的選擇是算法的關(guān)鍵。5.5.雙向搜索雙向搜索(BDSBDSBidirectionalBidirectionalSearchSearch)算法描述：使用序列前向選擇(SFS)與序列后向選擇(SBS)分別從兩端開始搜索，兩