梁伍七，王榮華，劉克禮，李 斌

(安徽廣播電視大學(xué) 信息與工程學(xué)院，合肥 230022)

一、引言

特征選擇在文本分類、文本檢索、基因分析和藥物診斷等場合有廣泛應(yīng)用，是模式識別領(lǐng)域的研究熱點之一。例如，自動文本分類是指按照給定的分類體系，依據(jù)文本的內(nèi)容自動進行文本所屬類別判別的過程，是一種有監(jiān)督的學(xué)習(xí)過程。自動文本分類在信息過濾、信息檢索、搜索引擎和數(shù)字圖書館等領(lǐng)域有廣泛應(yīng)用。分類系統(tǒng)主要包括數(shù)據(jù)預(yù)處理、文檔分詞、特征表示、特征選擇、文本表示、分類器選擇和訓(xùn)練以及分類結(jié)果評價等過程。1975年,文獻[1]提出向量空間模型(Vector Space Model，VSM),文檔被表示成特征空間中的一個向量。文本分類中文本表示方法通常使用向量空間模型，采用詞干抽取和去停用詞處理后，特征詞向量空間的維數(shù)雖有所降低，但特征空間的維數(shù)仍然是不可接受的。對于分類器來說，高維特征空間既增加了分類的時間復(fù)雜度和空間復(fù)雜度，也影響分類精度。

文本分類系統(tǒng)中高維特征空間的降維通常有兩種方法，即特征選擇(feature selection)和特征抽取(feature extraction)。二者都是在分類之前，針對原始特征的不足，降低特征維數(shù)，提高分類器的分類性能。特征抽取也稱作特征重參數(shù)化(feature re-parameterization)，通過對原始特征進行組合或者變換，新的低維空間是原來特征的一個映射。特征選擇作為文本分類預(yù)處理模塊的關(guān)鍵步驟，任務(wù)是從原始特征空間中選擇最重要的特征組成特征子集，從而實現(xiàn)特征空間降維。

二、特征選擇分類

特征選擇的過程包括四個主要環(huán)節(jié)[2-3]，包括子集生成(subset generation)、子集評估(subset evaluation)、停止準測(stopping criterion)和結(jié)果驗證(result validation)，如圖1所示。生成子集的過程是一個搜索過程，根據(jù)特定的搜索策略得到候選特征子集。對每個候選子集，根據(jù)評價準則進行評價。若新子集的評價結(jié)果優(yōu)于以前最好的子集，則將其更新為當前最優(yōu)子集。子集生成和子集評價不斷循環(huán)，直至滿足給定的停止準測，最后對最優(yōu)特征子集進行結(jié)果驗證。特征選擇在數(shù)據(jù)挖掘、模式識別和機器學(xué)習(xí)等多個領(lǐng)域內(nèi)均得到了廣泛的研究。根據(jù)不同的標準，特征選擇分類方法也有所不同，典型的分類標準及其分類方法如下。

圖1 特征選擇的四個主要環(huán)節(jié)

(一)基于搜索策略進行分類

搜索過程需要考慮兩個基本問題[3-4]：一是確定搜索起點?？梢詮囊粋€空的集合開始，然后不斷添加特征，也可以從一個完整的集合開始，然后不斷移除特征，或者從兩端開始，然后同時加入和移除特征；二是確定搜索策略。根據(jù)搜索策略的不同，特征選擇可分為完全搜索(complete search)、隨機搜索(random search)和啟發(fā)式搜索(heuristic search)等。

完全搜索方法：完全搜索需要遍歷特征空間中所有可能的特征組合，它能夠找到性能最好的子集。對于具有n個特征的數(shù)據(jù)集，存在2n個候選子集，這個搜索空間是指數(shù)級的，可以使用分支定界(branch and bound)算法[5]等啟發(fā)式方法來縮小搜索空間。

隨機搜索方法：該方法首先隨機選擇特征子集，后續(xù)采用兩種方式進行：第一種在傳統(tǒng)的序列搜索中注入隨機因素，稱為概率隨機方法，例如，隨機開始爬山算法(random-start-hill-climbing)和模擬退火算法(simulated annealing)[6]等；另一種稱為完全隨機方法，候選子集的產(chǎn)生方式是完全隨機的，例如，Las Vegas算法[7]等。這些方法中，隨機過程有助于避免在搜索空間中陷入局部最優(yōu)，但其能否搜索到最優(yōu)結(jié)果取決于可用的資源。

啟發(fā)式搜索方法：啟發(fā)式搜索可以消除組合爆炸，根據(jù)特定的啟發(fā)式規(guī)則設(shè)計次優(yōu)搜索策略，利用啟發(fā)信息來引導(dǎo)搜索，可以得到近似最優(yōu)解。常用的算法包括[3,8]序列前向選擇(SFS，sequential forward selection)、序列后向選擇(SBS，sequential backward selection)和雙向選擇(BDSS，bidirectional selection)等。該方法運算速度較快，對于包含n個特征的集合，搜索時間往往低于O(n2)。

(二)根據(jù)評價準則進行分類

每一個生成的候選子集都必須使用一個評價準則來進行評價。根據(jù)評價準則是否獨立于學(xué)習(xí)算法，可以分為過濾式(Filter)、封裝式(Wrapper)和混合式(Hybrid)三種類型。

(1)過濾式[4]：過濾式特征選擇作為一種數(shù)據(jù)預(yù)處理過程，評價準則和學(xué)習(xí)算法無關(guān)，可以快速排除不相關(guān)的噪聲特征，計算效率高。基于過濾式的評價函數(shù)包括距離度量(distance measure)[9-10]、信息度量(information measure)[11]、相關(guān)性度量(correlation measure)[12]和一致性度量(consistency measure)[8]等，評價準則不同得到的結(jié)果子集也不同。

(2)封裝式[13]：封裝式和所使用的學(xué)習(xí)算法有關(guān)，特征選擇算法作為學(xué)習(xí)算法的組成部分，將學(xué)習(xí)算法的性能作為衡量特征優(yōu)劣的標準。在特征選擇過程中直接用所選特征來訓(xùn)練分類器，根據(jù)分類器在驗證集上的性能作為特征重要程度的評價標準，封裝式能選出更適合特定學(xué)習(xí)算法的特征。對每個候選子集，分類器都需要重新訓(xùn)練，故該方法在速度上比過濾式要慢，優(yōu)點是所選的優(yōu)化特征子集的規(guī)模相對要小很多?；趩l(fā)式搜索策略的封裝器方法是目前較實用的特征選擇研究熱點。

(3)混合式[14]：綜合利用過濾式與封裝式的優(yōu)勢，提出混合式方法來處理大規(guī)模的數(shù)據(jù)集。最理想的情況是和過濾式的時間復(fù)雜度相近，和封裝式的算法性能相似。混合式方法的處理過程是，先使用過濾式基于數(shù)據(jù)集本身固有的特性快速進行特征選擇，保留少量特征，減少進一步搜索的特征規(guī)模，然后再用封裝式方法進一步優(yōu)化，得到分類性能最優(yōu)的特征子集。

(三)根據(jù)不同的監(jiān)督信息進行分類

監(jiān)督信息是文本內(nèi)容的重要組成部分，文本分類系統(tǒng)中，通常將類別信息作為監(jiān)督信息。特征選擇過程中，監(jiān)督信息起著重要的指導(dǎo)作用?？梢曰诓煌谋O(jiān)督信息，對特征選擇方法進行分類。

(1)根據(jù)訓(xùn)練集中給定類別標簽樣本和未給定類別標簽樣本的相對數(shù)量，可分為有監(jiān)督特征選擇(supervised feature selection)、半監(jiān)督特征選擇(semi-supervised feature selection)和無監(jiān)督特征選擇(unsupervised feature selection)[3-4]，反映了選擇特征過程中對類別信息的依賴程度。

監(jiān)督式特征選擇：利用類別信息進行指導(dǎo)，通過計算特征與類別之間的關(guān)系，選擇最具類別區(qū)分力的特征子集[2]131-156。關(guān)于特征選擇的研究最初大多聚焦于監(jiān)督式特征選擇，通過度量特征之間和特征與類別之間的相互關(guān)系來確定特征子集。

半監(jiān)督式特征選擇：半監(jiān)督式學(xué)習(xí)主要考慮如何利用少量的具有類別信息的樣本和大量的不帶類別信息的樣本進行分類學(xué)習(xí)的問題。Miller等人提出了一種分類器架構(gòu)和學(xué)習(xí)算法，算法可以有效利用未標記數(shù)據(jù)提高學(xué)習(xí)算法的性能[15]。隨著半監(jiān)督學(xué)習(xí)的發(fā)展，半監(jiān)督式特征選擇的研究也越來越受到重視。

無監(jiān)督式特征選擇：沒有類別信息指導(dǎo)，通過對特征空間的樣本進行聚類或無監(jiān)督學(xué)習(xí)對特征進行分組，并對特征重要性進行評估，根據(jù)特征的重要性程度進行特征選擇。文獻[16]考慮了無監(jiān)督學(xué)習(xí)的特征選擇問題，提出了一種新的算法，能夠識別嵌入在高維空間中支持復(fù)雜結(jié)構(gòu)的信息特征，算法通過一個目標函數(shù)將其表示為一個優(yōu)化問題，并用迭代法求解。

(2)根據(jù)類別數(shù)目，可分為二元特征選擇(binary feature selection)和多類特征選擇(multi-class feature selection)[3]。當某個樣本數(shù)據(jù)可以同時屬于多個類別，稱為多類特征選擇，也稱為多標簽特征選擇(multi-label feature selection)。根據(jù)類別的組織方式，多類問題可以分為平鋪結(jié)構(gòu)和層次化結(jié)構(gòu)。平鋪結(jié)構(gòu)的各個類別間關(guān)系是平等的，若類別間的關(guān)系不是獨立的，而是具有某種復(fù)雜的關(guān)系，可利用層次化特征選擇進行處理[17]。

三、基于SVM的特征選擇

1963年，文獻[18]在解決模式識別問題時提出了基于支持向量機(support vector machine，SVM)方法。1995年，文獻[19]正式提出統(tǒng)計學(xué)習(xí)理論，并提出用廣義分類面來解決線性不可分問題，據(jù)此構(gòu)成了SVM的理論基礎(chǔ)。SVM已被證明是具有最小化分類誤差和最大化泛化能力的強有力的分類工具，它建立在統(tǒng)計學(xué)習(xí)理論的VC維理論和最小化經(jīng)驗風險以及結(jié)構(gòu)風險的線性組合原理基礎(chǔ)上[20-21]。但SVM是作為模式識別領(lǐng)域中逐步發(fā)展而來的分類工具，標準的SVM并不能進行特征選擇。文獻[22]基于梯度最小化泛化邊界方法來減少特征，指出當存在不相關(guān)的特征時，標準SVM分類的性能會大大降低。這一結(jié)論導(dǎo)致了眾多學(xué)者對基于SVM的特征選擇算法進行研究。

根據(jù)評價準則是否和學(xué)習(xí)算法相關(guān)，特征選擇可以分為過濾式(Filter)、封裝式(Wrapper)和混合式(hybrid)三類[3]。基于SVM的特征選擇算法，本質(zhì)就是在特征選擇過程中融入SVM學(xué)習(xí)算法，因此基于SVM的特征選擇算法也可以劃分成三類：基于SVM的Wrapper特征選擇、基于SVM的Embedded特征選擇和基于SVM的混合特征選擇。

(一)基于SVM的Wrapper特征選擇

基于SVM的Wrapper特征選擇利用SVM分類器的性能作為特征選擇的評價準則。文獻[23]提出了一種基于SVM的Wrapper特征選擇算法，即SVM-RFE(SVM recursive feature elimination)特征選擇算法。SVM-RFE的算法流程是[21]：利用當前數(shù)據(jù)集訓(xùn)練SVM分類器，得到分類器的參數(shù)；計算權(quán)重向量；根據(jù)特征排序準則，計算所有特征的排序準則得分；移除得分最小的特征；上述過程多次迭代直至特征集中剩余最后一個特征。SVM-RFE方法是一個序列后向選擇的過程，目標是在d個特征中找出大小為r的特征子集，使得SVM分類的學(xué)習(xí)性能最優(yōu)。該方法首先訓(xùn)練SVM分類器，得到分類器的參數(shù)，利用參數(shù)信息對特征進行遞歸移除，在特征選擇的過程中存在參數(shù)不確定問題。

文獻[24]針對SVM-RFE方法的不足提出了改進算法。在SVM-RFE方法的基礎(chǔ)上，由支持向量機理論的泛化誤差界推導(dǎo)出評分準則，每次迭代過程中移除最小得分的特征；文獻[25]提出了增強的SVM-RFE特征選擇算法，采用最小冗余和最大相關(guān)MRMR作為評分準則。與SVM-RFE算法相比，在多數(shù)基因數(shù)據(jù)集上，算法選擇的特征個數(shù)較少。針對SVM-RFE算法中SVM參數(shù)難以確定的問題，文獻[26]采用粒子群算法搜索SVM的參數(shù)。

和SVM算法一樣，SVM-RFE最初設(shè)計是用來解決兩類基因選擇問題的。文獻[27]針對不同的多類SVM框架，推廣了SVM-RFE算法，用來解決多類基因特征選擇問題。文獻[28]針對多類分類問題，使用標準兩類SVM-RFE算法來排序問題，該算法能夠較好地解決多類問題。

SVM-RFE是一種簡單有效的特征選擇算法，已在許多領(lǐng)域得到應(yīng)用，基于SVM-RFE理論框架的特征選擇方法得到眾多研究者的關(guān)注，算法以SVM分類器的性能作為特征重要性的評價準則，優(yōu)點是所選的特征子集的規(guī)模相對較小，缺點是算法的時間復(fù)雜度較高。文獻[29]提出了一種基于SVM的Wrapper特征選擇算法，算法采用序列后向選擇，特征排序準則使用驗證子集的錯分樣本個數(shù)，每一輪迭代過程中，將特征所引起的錯分樣本個數(shù)最少的那個特征移除，最后得到最優(yōu)的特征子集。

(二)基于SVM的Embedded特征選擇

與一般的Embedded方法類似，基于SVM的Embedded特征選擇，特征選擇過程融于學(xué)習(xí)過程中，但該類方法的學(xué)習(xí)算法依據(jù)SVM理論[21]。

文獻[30]通過構(gòu)造非線性SVM，提出了一種新的特征選擇算法RFSVM。該算法的基本思想：在SVM思想的基礎(chǔ)上，通過一個正的參數(shù)σ來加權(quán)特征抑制項eTEe，該問題可以轉(zhuǎn)化為一個混合整數(shù)規(guī)劃求解問題。算法的目標函數(shù)為：

(1)

其中，A表示數(shù)據(jù)集矩陣，K表示核函數(shù)，v為正常數(shù)，u、s和γ為分類器的待求量，e表示全1的矢量，y表示正的變量，E表示對角元素為0或1的對角矩陣。(1)式是一個混合整數(shù)規(guī)劃問題，混合整數(shù)規(guī)劃問題是一個NP難問題?？梢酝ㄟ^固定E，將(1)式變?yōu)橐粋€線性規(guī)劃問題，通過求解得到(u,γ,y,s)的解，計算目標函數(shù)，上述過程多次迭代，直到函數(shù)值小于某一設(shè)定的閾值。該算法收斂于局部最小值，最終選擇的特征個數(shù)最少。

針對多類別分類特征選擇的問題，文獻[31]提出了一種基于SVM的Embedded方法L1MSVM，該算法通過加入l1范數(shù)，修改標準SVM的目標函數(shù)，為自適應(yīng)特征選擇計算整個正則化解決方案路徑。該算法的目標函數(shù)為：

(2)

l1范數(shù)SVM是標準l2范數(shù)SVM的變體，在處理高維問題和冗余噪聲特征時，l1范數(shù)SVM比l2范數(shù)SVM有一些優(yōu)勢，但l1范數(shù)SVM不適合處理存在強相關(guān)特征組合的場合。為了較好地解決這一問題，文獻[32]提出特征選擇算法DrSVM(doubly regularized support vector machine)。該算法混合了l2范數(shù)和l1范數(shù)，在標準SVM的目標函數(shù)加人l1范數(shù)，算法的優(yōu)點是能夠同時移除或選擇一組強相關(guān)的重要特征。DrSVM算法等價于解決下面的問題：

(3)

其中，λ1和λ2均是調(diào)整參數(shù)，[1-z]+=max(1-z,0)，(xi,yi)表示訓(xùn)練數(shù)據(jù)，yi表示第i個樣本的類別，yi∈{+1,-1}。l1范數(shù)的作用是來進行特征選擇，而l2范數(shù)的作用是同時選擇一組強相關(guān)的特征。文獻[32]研究表明，l2范數(shù)傾向于產(chǎn)生強相關(guān)的特征，且這些特征對應(yīng)的系數(shù)幾乎相等，稱這種現(xiàn)象為分組效應(yīng)。

DrSVM算法是基于SVM的Embedded特征選擇算法，和基于SVM的Embedded特征選擇算法l1-SVM相比，二者相同點是特征選擇過程和學(xué)習(xí)過程融于一體，在學(xué)習(xí)過程中自動地進行特征選擇；不同點是DrSVM算法能夠同時選擇或舍棄一組強相關(guān)的特征，而l1-SVM不考慮特征間的相關(guān)性，只能從強相關(guān)的特征中選擇一個[21]。DrSVM算法適用于維數(shù)高于訓(xùn)練樣本數(shù)的場合，而l1-SVM選擇的特征數(shù)目不超過訓(xùn)練樣本數(shù)。

基于SVM的Embedded特征選擇算法，特征選擇過程作為組成部分嵌入到學(xué)習(xí)算法里，這類算法效率較高，得到的學(xué)習(xí)算法有較好的性能。但如何基于標準SVM算法，來構(gòu)造算法的目標函數(shù)是目前算法研究的熱點。

(三)基于SVM的混合特征選擇算法

基于SVM的混合特征選擇先使用Filter算法快速進行特征選擇，然后利用Wrapper特征選擇算法進一步細化，得到更為有效的特征子集。

文獻[33]提出基于SVM的混合特征選擇算法FS_SFS(Filtered and Supported Sequential forward search)，和傳統(tǒng)的采用序列前向選擇的Wrapper方法比較，該算法有兩個重要的特性來減少計算時間。該算法首先使用Filter算法對原始特征進行預(yù)處理，然后對預(yù)處理后的特征子集，利用Wrapper算法進一步細化。該算法提出了一種新的評分準則，該準則既考慮了單個特征的區(qū)分能力，又考慮了特征之間的相關(guān)性，從而有效地過濾非本質(zhì)特征。

文獻[34]提出的基于SVM的混合特征選擇算法F_SSFS(F-score and Supported Sequential Forward Search)，該算法結(jié)合了F-score和序列前向選擇，結(jié)合了Filter方法和Wrapper方法各自的優(yōu)勢來選擇最優(yōu)特征子集，該算法可應(yīng)用于股票市場預(yù)測?？紤]到Filter算法和Wrapper算法各自的優(yōu)缺點，即Filter方法的計算成本低，但分類可靠性不足，而Wrapper方法具有較高的分類精度，但需要很大的計算能力，文獻[35]將二者整合成一個序列搜索算法，用以提高所選擇特征對于分類算法的性能。該算法添加預(yù)選擇步驟，以提高特征選擇的效率，利用ROC(receiver operating characteristic) 曲線作為搜索策略，利用SVM作為分類器，算法在生物數(shù)據(jù)分類上得到了很好的應(yīng)用。

文獻[36]提出了一種新的基于隊列智能算法的特征選擇與支持向量機(SVM)模型選擇混合方法SVM_SACI。方法將自適應(yīng)隊列智能(SACI)算法與SVM集成，形成了一種新的混合方法，用于同時進行特征選擇和SVM模型選擇，在多個數(shù)據(jù)集上的檢驗結(jié)果表明，SACI在支持向量機分類精度和降維方面優(yōu)于其他啟發(fā)式方法。針對樣本量遠小于數(shù)據(jù)集特征個數(shù)的小樣本可能帶來的奇異性問題，文獻[37]提出了一種0

文獻[38]提出了一種基于蝗蟲優(yōu)化算法(GOA)和SVM的混合方法，該方法對支持向量機模型的參數(shù)進行優(yōu)化，同時找到最佳特征子集。在多個低維和高維數(shù)據(jù)集上實驗結(jié)果表明，該方法在分類精度上優(yōu)于其他方法，同時最小化了所選特征的數(shù)目。文獻[39]提出了一種基于SVM方法的特征選擇分類問題的MILP模型，利用精確算法和啟發(fā)式算法，分析了該模型的不同求解方法。通過在多個數(shù)據(jù)集的檢驗和經(jīng)典分類方法的比較，對模型進行了驗證。文獻[40]提出了一種新穎的進化算法(lion算法)和SVM的混合方法，利用lion算法選擇高維數(shù)據(jù)集的特征子集，解決分類問題。特征選擇過程識別并刪除無關(guān)/冗余特征，以減少特征維數(shù)，從而提高分類的效率和準確性。

四、結(jié)語

本文闡述了自動文本分類中特征選擇的算法框架，探討了特征選擇的分類方法，介紹了SVM用于特征選擇的意義，對基于SVM的特征選擇算法進行了歸納總結(jié)，重點總結(jié)了基于SVM的Wrapper特征選擇、Embedded特征選擇以及混合特征選擇算法，分析對比了基于SVM的三類特征選擇的優(yōu)缺點。SVM算法的效率和性能主要取決于內(nèi)核類型及其參數(shù)，在處理高維數(shù)據(jù)集時，用于SVM模型的特征子集選擇是影響分類精度的另一個重要因素。如何利用已有的算法或提出新穎的算法用于高維數(shù)據(jù)集的特征選擇并訓(xùn)練SVM模型的參數(shù)，是基于SVM特征選擇的研究熱點和分類應(yīng)用發(fā)展方向。