基于新的森林優化算法的特征選擇算法

謝 琪，徐 旭，程耕國，陳和平

（1.武漢科技大學信息科學與工程學院，武漢430081； 2.格勒諾布爾高等商學院高等商業學院，格勒諾布爾38000，法國）

（?通信作者電子郵箱85169023@qq.com）

0 引言

特征選擇是機器學習和數據挖掘領域研究的熱點之一［1］。特征選擇是從一組特征中挑選出一些最有效的特征以降低特征空間維數的過程［2-3］。特征選擇在數據預處理的過程中會去除冗余和無關的特征，能減輕維度災難所產生的問題，同時能降低學習任務的難度，提升學習效果［4-5］。在分類問題中，特征選擇能提高分類的準確性，能生成更快和更有效的分類器，能更好地了解關鍵特征的信息［6］。特征選擇已被許多學者證明是有效的［7-9］。因此，特征選擇是機器學習過程的重要組成部分，可以為之后的學習任務保留有用的特征，同時忽略不相關和不重要的特征［10］。

在2016年，Ghaemi等［11］提出基于森林優化算法的特征選擇（Feature Selection using Forest Optimization Algorithm，FSFOA）算法［12］，該算法將森林優化算法（Forest Optimization Algorithm，FOA）用于特征選擇。FSFOA與基于混合遺傳算法的特征選擇（Hybrid Genetic Algorithm for Feature Selection，HGAFS）算 法［13］、基 于 粒 子 群 優 化（Particle Swarm Optimization，PSO）算法的特征選擇算法［14］和基于支持向量機的 特 征 選 擇 算 法［15］（a novel Support Vector Machine based feature selection method using a fuzzy Complementary criterion，SVM-FuzCoc）等算法相比取得了不錯的效果。FSFOA算法能提高特征學習的準確率，有效地除去冗余特征，并且還具備全局搜索能力。但是FSFOA算法存在一些不足：第一，FSFOA算法初始特征采用隨機生成策略，隨機初始化策略在非凸函數中可能會陷入局部最優，無法搜索到全局最優；第二，FSFOA算法遠處播種使用的是候選森林中的樹木，候選森林會產生優劣樹不完備問題，影響到全局搜索；第三，實驗發現，在最優樹更新階段會有相同適應度但是特征不同的樹木，FSFOA算法會將這些樹木淘汰，但是淘汰樹木中存在維度更小或者能產生更高精度的樹木。針對以上的問題，本文提出了基于一種新的森林優化算法的特征選擇（New Feature Selection Using Forest Optimization Algorithm，NFSFOA）算法，該算法分別從森林的初始化、候選森林的生成和森林的更新3個方面作了改進。最后將新算法與傳統算法在相同的測試數據下進行對比實驗，實驗結果表明，新的算法表現出了更準確的分類性能，并且能更有效地縮減維度。

1 特征選擇綜述

在機器學習和模式識別領域中，特征選擇的好壞會直接影響分類器的性能，因此特征選擇的方法非常重要。Dash等［16］提出了特征選擇的框架。特征選擇共分為4個部分：特征子集的搜索機制、特征子集的評價機制、停止準則和驗證方法［17-18］。當前主要研究集中在搜索機制和評價機制。

根據特征子集評價機制的不同，可將特征選擇方法分為三 類 ：過 濾 式（Filter）、包 裹 式（Wrapper）和 嵌 入 式（Embeding）［4］。過濾式方法［10，19］是先對數據進行特征選擇，然后再訓練學習器，特征選擇過程與后續學習器無關。過濾式特征選擇方法一般使用評價函數來增加特征與類別之間的相關性，削減特征之間的相關性［1，16］。典型的過濾式特征選擇是Relief。Kira等［20］提出 Relief方法是一種特征權重法，計算每個特征和類別之間的相關性，選擇相關性大于一定閾值的特征作為特征子集或者指定要選擇的特征個數K，然后選擇相關性最大的K個特征作為特征子集。Relief方法只能處理二分類問題不能處理多分類問題。Kononenko［21］提出Relief-F方法，該方法用于處理多分類問題。過濾式方法的關鍵是選取評價函數，評價函數可分為四類：距離度量、信息度量、依賴性度量和一致性度量［16］。包裹式特征選擇直接把最終將要使用的學習器的性能作為特征子集的評價準則［4］。典型的包裹式特征選擇是拉斯維加斯包裹式特征選擇（Las Vegas Wrapper，LVW）。Liu等［22］提出LVW方法在拉斯維加斯方法框架下，使用隨機策略來進行子集搜索，并以最終分類器的誤差作為特征子集的評價標準［4］。學者們使用不同機器學習算法用于包裹式特征選擇，如決策樹算法［23］、遺傳算法（Genetic Algorithm，GA）［24］和 支 持 向 量 機（Support Vector Machine，SVM）［25］等。嵌入式特征選擇是將特征選擇過程與學習器訓練過程融為一體，兩者在同一個優化過程中完成，即在學習器訓練過程中自動地進行了特征選擇［4］。正則化是典型的嵌入式特征的方法。Tikhonov等［26］提出嶺回歸算法在平方誤差損失函數中引入L2范數正則化。Tibshirani等［27］提出套索算法（Least Absolute Shrinkage and Selection Operator，LASSO），與嶺回歸算法類似該算法使用平方誤差函數作為損失函數，區別在于該算法使用范數正則化替代L2范數正則化。使用正則化求解得到的非零權重對應的特征就是最終求解的特征。正則化將特征選擇和學習器訓練同時完成，學習器訓練完成則特征選擇完成。

進化算法是通過模擬自然界生物不斷進化的過程以實現隨機搜索的一類算法［28］。進化算法具有高魯棒性和自適應性，能有效處理傳統優化算法難以解決的復雜問題，可用于求解全局最優解問題［29］?；谶M化算法具備的上述優點，學者們使用進化算法用于特征選擇［5］。遺傳算法是進化算法的一種，Yang等［30］提出使用遺傳算法進行特征選擇。Dong等［31］提出一種顆粒信息與遺傳算法相結合的特征算法，該方法使用改進的特征粒度遺傳算法用于特征選擇。Dorigo等［32-33］提出蟻群算法（Ant Colony Optimization，ACO），該算法是啟發式算法，并用于求解組合優化問題。Kabir等［34］提出一種混合蟻群優化算法用于特征選擇，該算法結合了過濾式特征選擇和包裹式特征選擇的優點。Wan等［35］提出一種改進的二進制編碼蟻群算法用于特征選擇，該算法使用遺傳算法初始化蟻群算法的信息素的初始信息。Kenned等［36-37］提出粒子群優化（PSO）算法，該算法利用個體信息共享使整個群體的運動在問題求解空間中產生從無序到有序的演化過程。Xue等［14］提出了分類問題中基于粒子群算法的特征選擇算法，該算法提出了三種新的初始化策略和三種新的個體最佳和全局最佳的更新機制。Zhang等［38］提出基于裸骨粒子群算法，該算法設計了一種增強記憶策略來更新粒子的局部領導者，避免了粒子中優秀基因的退化。Tran等［39］總結了粒子群優化算法在特征選擇中的運用。最近幾年進化算法產生了一個新的分支，Ghaemi等［11］根據森林中樹木優勝劣汰的生長過程提出了森林優化算法（Forest Optimization Algorithm，FOA）。森林優化算法是一種仿生類智能優化算法，它模擬森林中種子傳播的過程進行搜索最優解，用于解決非線性連續型優化問題［40］。

2 基于森林優化算法的特征選擇

FSFOA算法共分為5個步驟：初始化森林（Initialize Trees）、本地播種（Local Seeding）、規模限制（Population Limiting）、遠處播種（Global Seeding）和更新最優樹（Update the Best Tree）。

步驟1 初始化森林。隨機產生一些樹木初始化生成一個森林，每棵樹木由特征值、樹齡（Age）和適應度（Fitness）值組成。特征值是一個隨機產生的“0”或“1”的一維向量，“0”代表了對應的特征被刪除，“1”代表了對應的特征被選擇。Age設置為0。適應度是評價這棵樹選擇的特征在數據集上的學習能力，FSFOA算法使用的適應度函數為：鄰近算法（K-Nearest Neighbor，KNN）［41］、支持向量機算法［42］和C4.5算法［43］。

步驟2 本地播種。在本地播種階段，將森林中樹齡為0的樹參與本地播種，其余樹木不參與本地播種。將樹齡為0的樹依據參數本地播種變換（Local Seeding Change，LSC）值復制生成若干個相同特征值的樹木。每棵新生成的樹特征值隨機選擇一位取反，如果值為“0”則變成“1”，反之亦然。最后森林中所有樹木的Age值加1，新樹Age值置0，并將新樹加入森林之中。本地播種的過程用于算法的局部搜索。

步驟3 規模限制。FSFOA算法把控制樹木數量的過程稱為規模限制（Population Limiting）。規模限制的方式有兩種：第一種，將樹齡大于年齡上限（Life Time）值的樹木淘汰，這種方式模擬樹木正常死亡的過程；第二種，在淘汰掉樹齡大于“Life Time”值的樹木之后，森林數量的規模如果還大于規模上限（Area Limit）值，將所有樹木的適應度（Fitness）做降序排列，淘汰掉適應度小的樹木，將森林的規?？刂圃凇癆rea Limit”值以內，這種方式模擬自然界適者生存法則。

步驟4 遠處播種。FSFOA算法通過模擬遠處播種的過程為算法提供全局搜索方法。算法依據轉移率（Transfer Rate）的值隨機選擇候選森林中一定比例的樹木用于遠處播種。每棵遠處播種的樹木依據遠處播種變化（Global Seeding Change，GSC）值隨機選擇若干個特征值取反。

步驟5 更新最優樹。在更新最優樹階段，選擇森林中適應度最大的樹，將這些樹的年齡值置為0，重新放入森林中。

3 基于改進的森林優化算法的特征選擇

3.1 FSFOA算法的不足

FSFOA算法在以下3個方面存在不足：

1）FSFOA算法在初始化森林階段，初始化的樹木采用完全隨機方式，完全隨機策略在非凸函數問題中容易陷入局部最優解。

2）FSFOA算法在規模限制階段通過兩種策略限制森林的規模，并將淘汰的樹木生成候選森林，并按一定比例數量用于遠處播種。這種會產生“優劣”樹不完備問題，影響全局搜索。

規模限制的第一種方式是模擬優質樹的自然死亡，將樹齡達到“Life Time”值淘汰進入候選森林，樹齡能達到“Life Time”值的樹以前沒有被淘汰說明這類樹的fitness會大于一般的樹，否則之前就會被淘汰，這樣的樹是一種“優質樹”。規模限制的第二種方式是如果森林的規模超過了“Area Limit”值，淘汰fitness最小的樹。這種方式是模擬森林中優勝劣汰的過程，有的樹由于基因或者環境的問題還沒有長大就死亡了，說明這種樹是一種“劣質樹”。將優質樹和劣質樹混在一起形成候選森林，按一定比例進行遠處播種，由于優質樹和劣質樹混在一起選擇，有可能選擇到的都是優質樹或者都是劣質樹，最終影響到全局搜索。

3）在最優樹更新階段會有相同適應度但是特征不同的樹木，FSFOA算法是將這些樹木淘汰，但是淘汰樹木中存在維度更小或者能產生更高精度的樹木。

3.2 FSFOA算法的改進

針對FSFOA算法以上的不足，本文相應提出了3點改進：

1）初始化策略的改進。初始化策略共分為兩步：第一步，計算數據所有特征與標簽之間的皮爾森相關系數，取相關系數為正的特征作為備選特征集；第二步，將備選特征集使用L1正則化特征選擇法選出權重為非0的特征。

通過使用皮爾森相關系數和L1正則化兩次選擇之后產生的特征集合與標簽之間具有很高的關聯性。與隨機初始化策略相比，新的初始化策略選擇的特征集合能夠快速地收斂到極值，并有助于搜索到最優的特征子集。

皮爾森相關系數（Pearson Correlation Coefficient）也稱皮爾森積矩相關系數（Pearson Product-moment Correlation Coefficient），是一種線性相關系數。皮爾森相關系數是用來反映兩個變量線性相關程度的統計量。相關系數描述的是兩個變量間線性相關強弱的程度，相關系數的絕對值越大表明相關性越強。皮爾森相關系數等于兩個向量的協方差除以各自的標準差，如式（1）所示：其中：Cov(X，Y)代表向量X和向量Y的協方差，σx代表向量X的標準差，σy代表向量Y的標準差，E代表期望，ρxy代表向量X和向量Y的皮爾森相關系數。

皮爾森相關系數的取值范圍在-1到1之間：相關系數為0，說明兩個向量不是線性相關；如果相關系數大于0，說明兩個向量正相關；如果相關系數小于0，說明兩個向量負相關。皮爾森相關系數特征選擇法是過濾式特征選擇的一種。

2）候選森林的改進。根據規模限制的兩個策略將候選森林分為“優質森林”和“劣質森林”，將“優質森林”和“劣質森林”分別按“Transfer Rate”的值隨機選擇樹木進行遠處播種。由于規模限制的策略不同，“優質森林”和“劣質森林”會產生“類別不平衡”問題，即“優質森林”的數量會遠大于“劣質森林”的數量或者相反。為了解決“類別不平衡”問題，當“優質森林”數量大于“劣質森林”數量時，在森林中選擇fitness最小的若干個樹木補足“優質森林”和“劣質森林”之間數量的差額；反之則在森林中選擇fitness最大的若干個樹木補足差額。

3）最優樹更新和選擇的改進。在FSFOA算法中，當遠處播種生成的新樹的最大fitness與森林中最大fitness相同時，新樹被淘汰。在新的更新機制中，如果新樹的最大fitness等于森林中最大的fitness時，則將這些新樹Age置0后添加到森林中。這是因為當新樹和舊樹fitness相同時，存在維度更小的新樹，因此將新樹添加到森林之中有利于維度的縮??；如果fitness相同但新樹的維度大于等于舊樹，將這樣的新樹也添加到森林中，因為這樣的新樹再通過傳播存在產生性能更好的樹，以提高了搜索全局最優解的可能。最后，在最優樹選擇階段，選擇fitness最大的樹，如果有多個fitness最大的樹則選擇特征數量最少的樹。

3.3 算法的流程

改進算法的流程如圖1所示。

圖1 NFSFOA算法流程Fig.1 Flowchart of NFSFOA algorithm

4 實驗

為了證明新算法的有效性，實驗采用與FSFOA算法相同的數據集和參數，實驗從UCI機器學習庫［44］中獲得10個數據集。實驗程序用python3編寫，使用scikit-learn工具包編寫L1嵌入式特征選擇、皮爾森相關系數過濾式特征選擇以及其他機器學習的算法。所有實驗都在MacBook Pro 3.5 GHz Intel Core i7處理器下執行。

4.1 實驗數據

實驗數據一共包含了10個數據集合，分別是：Wine、Ionosphere、Vehicle、Glass、Segmentation、SRBCT、Heart-statlog、Cleveland、Sonar和Dermatology。FSFOA算法將實驗數據集根據特征數量的個數分為“小維度”“中維度”和“大維度”數據集，分別對應的特征數量的范圍是［0，19］、［20，49］、［50，∞］［12］。根據以上劃分的依據，數據集中包含6個小維數據集、2個中維數據集和2個大維數據集。實驗數據集合的相關說明如表1所示。

表1 實驗數據集說明表Tab.1 Descriptions of experimental data

4.2 實驗參數

新算法的參數與FSFOA算法的參數一致，FSFOA算法共有5個參數：樹的年齡上限（Life Time）、樹的規模上限（Area Limit）、遠處播種的比例（Transfer Rate）、本地播種變化個數（LSC）和遠處播種變化個數（GSC）。FOA指出參數“Life Time”“Area Limit”和“Transfer Rate”與數據集的數量無關［11］。FSFOA算法將這3個參數設定為固定值，“Life Time”為15、“Area Limit”為 50、“Transfer Rate”為5%［12］。FOA指出LSC 和GSC與特征的個數相關［11］。FSFOA算法設定了10個數據集的LSC和GSC值，如表2所示。

表2 實驗數據集參數表Tab.2 Parametersof experimental data

為了防止產生過擬合問題，通常會將實驗數據分為訓練集、驗證集和測試集，使用驗證集來減少過擬合問題的產生。由于本次實驗的數據較少，如果增加驗證集，訓練集較少將會產生欠擬合。因此實驗不使用驗證集，而使用10折交叉驗證、2折交叉驗證和70%訓練集與30%測試集。10折交叉驗證是指將數據集合分為10份，其中9份作為訓練集，1份作為測試集，重復10次每次使用的測試集不同，最后將10次測試結果求均值。

評價算法的性能使用兩個函數：分類精確性（Classification Accuracy，CA）和 維 度 減 少 率（Dimension Reduction，DR），CA和DR如式（2）和式（3）所示：

其中：N_CC是測試數據中分類正確的數據個數，N_AC是測試數據的總數。

其中：N_SF是通過算法選擇到的特征個數，N_AF是特征的總數。

CA和DR的值域為［0，1］。CA是分類算法的準確性，CA值越大說明該算法分類性能越好；DR是特征選擇算法特征維度選擇能力，DR值越大說明算法維度縮減能力越強。

適應度函數使用KNN、C4.5、SVM，參數如表3所示。

表3 適應度函數和參數Tab.3 Fitness functions and parameters

4.3 實驗結果

如表4所示，NFSFOA算法和FSFOA算法在不同數據集、不同適應度函數和不同驗證方式下的實驗結果。通過表4可以發現，在數據集Sonar、Dermatology、Ionosphere、Segmentation和Vehicle中，NFSFOA算法的測試精度和維度縮減能力相較于FSFOA算法在相同測試條件下都有提高。在SRBCT數據集中，NFSFOA算法和FSFOA算法測試精度相同，NFSFOA算法維度縮減能力提高。在Heart-statlog和Wine數據集中，NFSFOA算法在部分條件下測試精度有提高，維度縮減能力全部有提高。在Cleveland和Glass數據集中，測試精度都有提高，部分條件下維度縮減能力下降。

4.4 實驗結果分析

第一，在SRBCT數據集中，NFSFOA算法和FSFOA算法測試精度相同是因為SRBCT數據集特征個數為2 308但數據只有63條，特征個數遠大于數據個數，這樣的數據集容易陷入過擬合。SRBCT數據集采用70%訓練30%測試的方式，一共測試數據19條，94.73%的測試準確率，19條數據中18條數據分類正確，只有1條分類錯誤。94.73%的測試準確率達到了分類器的極限，如果精確率再提高則分類正確率達到100%。

第二，在Heart-statlog和Wine數據集中，在部分情況下分類精度有下降。在Cleveland和Glass數據集中，在部分情況下維度縮減能力有下降。主要原因是與其他數據集相比，Heart-statlog、Wine、Cleveland和Glass這四個數據集的特征維度最小，分別是13個特征和9個特征。說明NFSFOA算法在維度太小的數據集上分類性能和維度縮減能力有限。

第 三 ，在 數 據 集 Sonar、Dermatology、Ionosphere、Segmentation和Vehicle中，NFSFOA算法分類性能和維度縮減能力都有提高。說明NFSFOA算法在中大維度的數據集中有不錯的性能。

表4 NFSFOA算法和FSFOA算法在不同數據上性能的對比Tab.4 Performancecomparison between NFSFOA algorithmand FSFOA algorithmon different data

5 結語

本文針對FSFOA算法存在的三個問題，提出了一種基于改進的森林優化算法的特征選擇算法。該算法提出了三個方面的改進：第一，在初始化階段使用皮爾森相關系數和L1正則化代替隨機初始化；第二，在候選森林生成階段將優質樹和劣質樹分開采用差額補足的方法解決優劣樹不平衡問題；第三，在更新解決段將精度相同但維度不同的樹添加到森林中。本文通過實驗，測試了小維度、中維度和大維度的數據集，新算法在中大維度數據上分類性能和維度縮減能力均有提高。