基于相關(guān)搜索的前向序列特征選擇算法*

李三川，吳麗麗

（中移信息技術(shù)有限公司，廣東 深圳518048）

0 引 言

特征選擇是從龐大的特征集中篩選出最有價值、最具代表的特征子集來代替原來的特征集，在機(jī)器學(xué)習(xí)中起到降維、提高模型泛化能力的作用，從而提升資源效能，確保模型的穩(wěn)定性[1]。

特征選擇一般包括產(chǎn)生、評價、停止、驗(yàn)證四個過程[2]。其中，最重要的是特征子集的產(chǎn)生過程。該過程是大部分特征選擇算法的核心，即搜索策略。目前，特征選擇算法根據(jù)搜索策略主要分為完全搜索、序列搜索和隨機(jī)搜索三類[3]。完全搜索主要是通過窮舉遍歷的方式來獲得特征子集的最優(yōu)解，準(zhǔn)確度高，但時間復(fù)雜也高，實(shí)用性不強(qiáng)，主要有定向搜索、最優(yōu)優(yōu)先搜索等算法。序列搜索主要通過貪心算法來尋找特征子集的次優(yōu)解，速度快，準(zhǔn)確度高，但容易得到局部最優(yōu)解，主要算法為前向或后向序列選擇、增L去R選擇算法以及浮動序列選擇。隨機(jī)搜索通過先隨機(jī)產(chǎn)生特征子集再進(jìn)行搜索選擇的方式獲得最優(yōu)特征子集，可有效解決局部最優(yōu)解的問題，但具有較強(qiáng)的隨機(jī)性，結(jié)果難重現(xiàn)。主要算法包括模擬退火和遺產(chǎn)算法等[4]。

本文主要針對序列選擇算法中的嵌套效應(yīng)，對傳統(tǒng)的序列選擇算法進(jìn)行改進(jìn)，提出了基于相關(guān)搜索的前向序列特征選擇算法。通過在每次選擇時剔除與已選擇特征高度相關(guān)的特征組合，從而減少特征子集內(nèi)的冗余。最后，將改進(jìn)算法在兩個不同的數(shù)據(jù)集上進(jìn)行驗(yàn)證，結(jié)果表明本文提出的算法能得到更好的特征子集，且在較小特征子集時性能更優(yōu)。

1 序列選擇算法

序列選擇算法是一種基于貪心算法的特征搜索算法，通過每次尋找當(dāng)前最優(yōu)特征子集的方式來逐步得到最終的特征子集，也是目前較常用、綜合性能較好的次優(yōu)特征搜索算法[5]。目前，最具代表性且最常用的算法為前向序列選擇算法（SFS）、浮動前向序列選擇算法（SFFS）和自適應(yīng)前向序列選擇算法（ASFFS）。

1.1 前向序列選擇算法（SFS）

前向序列選擇算法是最早的序列選擇算法，實(shí)現(xiàn)的一般過程如下：

（1）初始時，特征子集X設(shè)為空集；

（2）每次從特征全集Y中選擇一個特征xk加入到X中，使得特征評價函數(shù)J(X)取得最大值；

（3）判斷當(dāng)前特征數(shù)k是否等于所需的特征子集個數(shù)；

（4）若是，則停止；否則，重復(fù)上一步直到滿足條件。

通過以上過程能迅速得到符合期望大小的特征子集，但該算法存在明顯的缺點(diǎn)，只能加入特征而不能去除特征，導(dǎo)致算法過分依賴最初得到的特征，使得所得結(jié)果并不理想。

1.2 浮動前向序列選擇算法（SFFS）

浮動前向序列選擇算法是對序列選擇算法的一次重要改進(jìn)。它在前向序列算法的基礎(chǔ)上增加了特征回溯，提供了去除較差特征的功能，改進(jìn)了SFS算法每次只能添加特征、之后遇到更好的特征卻不能替換的弊端，提高了序列選擇算法的性能[6]。算法過程如下：

（1）初始特征子集X為?，特征子集大小k為0；

（2）使用基本的SFS算法從特征集合Y-Xk中選取使J(Xk+1)最大的特征Xk+1；

（3）遍歷Xk+1，從中依次去掉一個特征得到，若J()≤J(Xk)，則返回步驟（2），同時k=k+1，并判斷是否滿足停止條件；否則，進(jìn)行步驟（4）；

從SFFS的算法過程中可以看出，該算法兼顧前進(jìn)和后退，在前進(jìn)添加特征的同時，后退回溯判斷當(dāng)前特征集的子集是否仍為最優(yōu)，以此盡可能,使最終得到的特征子集最優(yōu)。

1.3 自適應(yīng)前向序列選擇算法（ASFFS）

自適應(yīng)前向序列選擇算法結(jié)合了SFFS算法和增L去R選擇算法的特點(diǎn)，通過自適應(yīng)方式調(diào)節(jié)每次添加和去除的特征個數(shù)。越接近期望特征維數(shù)d時，每次添加和去除的特征個數(shù)就越多[7]。算法主要過程如下：

（1）初始化k=0，單次添加或去除個數(shù)o=1。

（2）前進(jìn)過程：使用SFS算法添加o個特征，并判斷當(dāng)前J(Xk+o)是否為最大，若是，使k=k+o并判斷是否停止進(jìn)入后退過程；否則，根據(jù)k與d的差值增加o的值，繼續(xù)通過SFS添加特征。

（3）后退過程：使用后向序列選擇算法（SBS）去除o個特征，判斷當(dāng)前J(Xk-o)是否仍為最大，若是替換特征子集，使k=k-o并重復(fù)后退過程；否則，根據(jù)k與d的差值增加o的值，繼續(xù)去除特征直到o的值超過最大門限值后返回前進(jìn)過程。

從上述過程可以看出，ASFFS算法能更靈活地選取特征子集，但當(dāng)特征全集Y較大時，增大o值會陷入窮舉困境，大大增加了時間復(fù)雜度。

2 基于相關(guān)搜索的前向序列選擇算法

2.1 傳統(tǒng)序列選擇算法的問題

無論是SFS算法，還是SFFS和ASFFS算法，都存在一個明顯的缺陷——無條件前向添加特征，即在添加特征時都是無條件的，使得特征子集中存在相關(guān)的特征組合形成冗余。要解決該問題，只需在添加特征時添加條件，對特征進(jìn)行條件篩選，確保與特征子集相關(guān)的特征無法被選取即可。但是，若只是單純地直接添加條件，則很可能導(dǎo)致序列選擇算法陷入死循環(huán)?；谏鲜隹紤]，提出了基于相關(guān)搜索的前向序列選擇算法（RSFFS），實(shí)現(xiàn)在每次添加特征前剔除與特征子集高度相關(guān)的特征組合，變相增加了特征添加條件。該算法有效實(shí)現(xiàn)的關(guān)鍵是相關(guān)特征組合的搜索，找到高度相關(guān)的特征組合。

2.2 相關(guān)特征組合搜索

為尋找高度相關(guān)的特征組合，需計算特征組合{x1,x2,…,xk,k=2,…,k}與目標(biāo)變量y之間的復(fù)相關(guān)系數(shù)R。為得到R，首先用x1,x2,…,xk對y進(jìn)行線性回歸，得到：

為得到高度相關(guān)的特征組合，需對上述過程進(jìn)行窮舉，搜索出特征集所有的特征組合。這需要極高的時間成本和計算量，并不實(shí)際。而根據(jù)二元相關(guān)系數(shù)的特性，當(dāng)二元相關(guān)系數(shù)高時可以確定y與xk之間存在線性組合的關(guān)系[8]，所以可采用反向逼近的方式去搜索與y高度相關(guān)的特征組合。

在RSFFS算法中，通過預(yù)先設(shè)置相關(guān)系數(shù)閾值p和閾值步長Δ對特征組合進(jìn)行搜索，過程如下。

步驟1：計算特征集中任意特征與y的相關(guān)系數(shù)R，若R＞p，則認(rèn)為y與其高度相關(guān)，遍歷計算得到滿足高度相關(guān)的特征組合Xp。

步驟2：將閾值p更新為p+Δ，并對步驟1中所得到的Xp再次遍歷，找到相關(guān)系數(shù)大于p的特征構(gòu)成新的Xp。重復(fù)該過程并逐步增加閾值步長，直到無法找到新的Xp。其中，原理在于高二元相關(guān)系數(shù)所得到的特征集是由與y相關(guān)的特征組合中的部分特征及剩余特征的線性回歸解兩部分組成，而不斷提高閾值再次搜索即可逐漸反向逼近回歸解所表示的特征線性組合。

2.3 算法的主要過程

利用鏈?zhǔn)较嚓P(guān)特征搜索方式為核心，結(jié)合傳統(tǒng)前向序列選擇算法SFFS，即可實(shí)現(xiàn)RSFFS算法，算法流程如圖1所示。

圖1 RSFFS算法流程

通過圖1的流程可總結(jié)算法的主要過程如下：

（1）初始化：設(shè)置k=0，p和Δ為合適的值，Xk為?，期望的特征子集大小d；

（2）按照傳統(tǒng)SFS算法，從特征集合Y-Xk中選取使J(Xk+1)最大的特征xk+1；

（3）遍歷Xk+1，從中依次去掉一個特征xr得到， 若J(≤J(Xk)， 則 進(jìn) 行 第（4） 步， 同時k=k+1并判斷是否滿足停止條件；否則，跳到第（5）步；

（4）從xk+1出發(fā)，采用鏈?zhǔn)较嚓P(guān)搜索，在Y-Xk中找出與xk+1構(gòu)成特征組合的集Xp，并將Xp從特征全集中去掉Y=Y-Xp；

同時，將與xs相關(guān)的特征組合Xsp回復(fù)到特征總集Y=Y+Xsp。

（6）判斷k是否為2，若是，則更新Xk=Xk′，并返回第（2）步；否則，重復(fù)執(zhí)行第（5）步。

3 結(jié)果與分析

為驗(yàn)證算法的有效性，選擇了musk和snoar兩個不同維度的二分類數(shù)據(jù)集對算法進(jìn)行測試。musk數(shù)據(jù)集樣本個數(shù)分別為476、248，特征個數(shù)D分別為166、60。測試時，以knn算法的分類精度作為特征選擇的評價函數(shù)，最終得到各算法的分類精度。圖2和圖3分別為SFS、SFFS、ASFFS以及RSFFS算法在musk和sonar數(shù)據(jù)集特征選擇上的分類結(jié)果。

從圖2可以看出，整體上分類結(jié)果的精度是隨著特征子集個數(shù)的增大而提高，并最后趨于穩(wěn)定。此外，在相同個數(shù)的特征子集個數(shù)時，RSFFS算法得到的特征子集在分類時的精度明顯高于SFS、SFFS和ASFFS，尤其是在特征子集個數(shù)為10～16時優(yōu)勢明顯。

從圖3中可以看出，RSFFS算法在數(shù)據(jù)集sonar的效果亦均好于其余三種算法。

綜上，RSFFS算法可以有效提高序列選擇算法的性能，篩選的特征子集比傳統(tǒng)的序列選擇算法所得的結(jié)果更優(yōu)，且當(dāng)期特征子集數(shù)較小時，效果更明顯。

圖2 四種算法在musk數(shù)據(jù)集上的分類結(jié)果

圖3 四種算法在sonar數(shù)據(jù)集上的分類結(jié)果

4 結(jié) 語

本文提出了基于相關(guān)搜索的前向序列特征選擇算法，針對傳統(tǒng)序列選擇算法存在的嵌套冗余問題，在向前添加特征時剔除與之相關(guān)的特征組合，避免了特征子集的過度冗余。試驗(yàn)表明，該算法能夠有效篩選出更好的低維度特征，使得最終分類效果更好，且在具有高度相關(guān)特征的數(shù)據(jù)上，RSFFS算法的效果尤為明顯。