改進的基于層次距離的基因表達式編程特征選擇分類算法

湛 航，何 朗*，黃樟燦，李華峰，張 薔，談 慶

（1.武漢理工大學理學院，武漢 430070；2.武漢大學數學與統計學院，武漢 430072）

（*通信作者電子郵箱helang@whut.edu.cn）

0 引言

特征選擇（Feature Selection，FS）是數據挖掘中一項特別重要的數據預處理步驟，常用于去除數據中冗余和不相關的特征數據，降低計算復雜度，提升模型的效果［1-2］。特征選擇在數字圖像處理、文本分類、生物信息學、基因序列分析、金融時間序列分析以及醫學數據分析等方面應用較為廣泛［3-6］。常見的特征選擇方法有：過濾式（filter）、嵌入式（embedding）和包裹式（wrpper）［7］。過濾式獨立于學習器，在訓練學習器之前完成特征的選擇；嵌入式則將特征選擇與學習器的訓練結合，在一個優化過程中完成；包裹式則依據學習器的性能作為特征選擇優劣的評價［7］。

特征選擇是一個NP-hard 問題，對于具有n個特征的特征選擇問題有2n個可能的特征子集［8］。在分類問題上，通過選取關鍵的特征，忽略不太重要的數據特征，構建出一個良好的分類器，進而提高分類預測效果［9］。選擇的特征優劣對于構建出一個簡潔、高效的分類系統有著重要的影響［10］。

國內外許多學者一直致力于研究這個問題。一些簡單方法如窮舉搜索算法、分支定界算法等［11］，這些方法可以挑選出最優的特征子集，但是這些方法的時間復雜度對于高維數據并不友好，在應用過程中也存在一些局限性?；谠搯栴}，一些傳統的機器學習方法被應用到這個方面，如決策樹算法［12］給出了一種基于信息增益大小的特征選擇分類方法；李占山等［7］提出了一種基于XGBoost 的特征選擇算法；Moustakidis等［13］提出了一種基于支持向量機（Support Vector Machine，SVM）的模糊互補準則的特征選取方法。雖然機器學習方法擁有較快的求解速度，模型容易解釋，但是它沒有考慮特征與特征之間、特征與類別之間相關性。Sun 等［14］結合類別相關度，將最大相關性和最小冗余準則（max-Relevance and min-Redundancy，mRMR）擴展到了多標簽學習，借助凸優化來優化特征初始分配的權重，從而獲取特征排序；Sheikhi 等［15］將特征的冗余性替換為多樣性，以量化候選特征相較于已選擇子集的互補性，提出了正秩最大相關性及多樣性的特征選擇算法。盡管這些方法的原理較為簡單，在小規模數據上擁有不錯的表現，但對于大規模數據而言，在求解速度與求解精度上略顯不足。

由于演化算法在NP-hard 問題上擁有著不錯的表現，其計算復雜度相較于其他機器學習等方法更低，對于整個問題的解給出一種編碼方案，而不是直接對問題的具體參數進行處理，它不用考慮問題本身的特殊知識背景，僅依靠種群個體內部的進化就能尋找到一個全局的較優解［7］，因而被大量用于特征選擇問題上。Ghaemi 等［16］將求解連續變量優化問題的森林優化算法應用于離散的特征選擇問題，有效地提高了分類器的分類精度；張翠軍等［1］提出了一種平衡特征子集個數與分類精度策略的多目標骨架粒子群優化的特征選取算法；張夢林等［17］提出一種采用新的初始化策略和評估函數，以特征子集的準確率指導采樣的基于離散域采樣分類優化（Sampling-And-Classification optimization，SAC）特征選擇算法，實驗結果表明該方法可提高分類準確率，有好的泛化能力；李光華等［18］將隨機森林的重要度評分作為蟻群的啟發式信息，提出了一種融合蟻群算法和隨機森林的特征選擇算法；Tabakhi等［19］提出一種不依賴于其他學習算法，通過多次迭代尋優尋找最優子集的基于蟻群優化的無監督特征選擇算法。

演化算法在特征選擇領域的應用，使得人們不再關注數據領域內的具體知識，通過控制演化算法中種群的規模和搜索策略，采取合適的分類器，使得演化算法取得了不錯的效果［11］。但是，上述演化算法往往還需要結合其他分類器才能在特征選擇問題上使用，演化算法僅僅只是選擇了特征，當前特征選擇的優劣與否還需要借助分類器分類效果進行判斷。并且，選擇的特征與分類器僅僅只能反映出當前特征與該數據所屬類別之間存在關系，無法直觀說明關鍵特征與數據類別之間的一種可解釋的映射關系。

基于該問題，Ma 等［20-21］提出了一種基于遺傳規劃（Genetic Programming，GP）算法的特征選擇算法，利用GP 算法在函數發現上的優越性，構建出特征與類別之間的函數關系。實驗結果表明，該算法提高了分類準確度，降低了特征選擇率，還給出了顯式函數關系式，揭示了特征與類別之間存在的關系。但是GP算法存在膨脹現象，種群個體在進化的過程中容易出現無用個體，影響種群進化效率，而基因表達式編程（Gene Expression Programming，GEP）算法相較于GP 算法擁有著更加高效的函數發現能力，能更好地克服GP 中的缺陷［22］。GEP算法在演化過程中過多的遺傳算子參數設定使得算法結果容易受到干擾，而且決定演化方向的單一適應度值會使算法在解決復雜問題時容易陷入局部最優。崔未［23］提出了基于層次距離的基因表達式編程（GEP based on Layer Distance，LDGEP）算法，通過改變染色體結構，對個體的基因進行分層，定義種群個體層與層之間的距離，通過層次距離來選擇遺傳位點，使得個體有針對性地變異。實驗結果表明，LDGEP 算法相較于傳統GEP 算法有更好的發現函數的能力與速度，但在種群初始化及層次變異過程中存在一定的盲目性，影響種群進化速度。

基于此，本文提出了改進的基于層次距離的基因表達式編程特征選擇分類算法（imporved Feature Selection and classification algorithm for LDGEP，FSLDGEP），通過改進種群的初始化方式，使得種群個體的隨機初始化具有一定的導向性；同時，通過定義種群的層次鄰域來改變種群個體的隨機變異方式；并在原始的分類準確率評價指標上，考慮種群個體選擇的特征數量，將其作為適應度評價指標之一，平衡維度縮減率與分類準確率之間的關系，構建出類別關于特征的函數，揭示出兩者之間存在的函數映射關系。

1 基于層次距離的基因表達式編程算法

LDGEP 算法是由崔未基于GEP 算法改進而來的群智能演化算法。傳統的GEP 算法中存在許多需要手動設定參數的遺傳進化算子，如選擇復制算子、轉座算子、重組算子和變異算子等，而LDGEP 算法更改了原始GEP 算法的演化模式，重新定義了個體結構與個體相似性計算方法，將大量的進化算子減少至三個算子，且算子的參數無需設置，提升了算法求解問題的精度和速度。LDGEP 算法主要包括四步：種群初始化、適應度計算、選擇操作和遺傳操作。

1.1 種群初始化與個體編碼解碼

LDGEP 算法中初始種群個體的基因是隨機生成的，基因由一個頭部和尾部組成，其長度分別為h和t。頭部符號從函數集和終止集中選取，尾部符號從終止集中選取。一般的函數集包含常用的數學運算符及一些初等函數，如{+，-，*，/，sin，exp，…}，終止集則通常由變量、常數等組成，如{x1，x2，1，2，e，…}。當基因頭部與基因尾部長度滿足約束式（1）時，個體初始化完成，重復多次，即可完成種群的初始化。

其中：t表示基因尾部長度；h表示基因頭部長度；n表示函數集中符號的最大運算目數。

傳統GEP 算法中的個體采用固定長度編碼，只是在表達時部分基因不表達。為確保個體間的距離定義一致性以及表達式樹結構的完整性，LDGEP 算法對未表達的節點采用TR（Null）節點補齊方法。LDGEP 算法中的個體編碼長度由該個體的層數確定，其長度計算公式如式（2）：

其中：len表示個體長度；L表示層數。

如表達式a+sin(b)，該個體的編碼及其表達式樹結構如圖1（a）。解碼時，根據運算目數對未表達的基因采用TR 補齊，如圖1（b），虛線代表補齊的TR 節點。再根據各節點運算符的性質以及二叉樹的中序遍歷方式，將個體的樹結構轉換成為數學表達式。

圖1 表達樹結構及補齊后表達樹結構Fig.1 Structures of expression tree and complemented expression tree

1.2 距離定義

種群個體的層次示意圖如圖2 所示，每層個體的數量為2l-1，其中l表示當前的層數。

圖2 個體層次示意圖Fig.2 Schematic diagram of individual layer

LDGEP 算法對每個個體的每一層給定一個權值，用以區分不同層對于個體的影響。種群個體的層次距離為基于加權的漢明距離，計算公式所示：

其中：dij(l)表示第i個個體與第j個個體在第l層的層次距離；L表示個體的總層數；Dij(l)為第i個個體與第個j個個體在第l層的漢明距離。wl表示第l層的權重，其計算公式如下所示：

其中：l表示層數。隨著層次的遞增，層次重要性越低，從而對解碼后的個體的表達影響越低。

1.3 遺傳操作

1.3.1 遺傳位點選擇

由于每一層對于種群個體的表達有不同的影響，通過對層次距離不同的層采用遺傳操作，使種群個體向更優秀的個體靠近。通過計算每一層個體間的層次距離確定遺傳位點。遺傳位點的確定規則如下所示：

其中：dij(l)表示第i個個體與第j個個體在第l層的層次距離；layerij表示第i個個體與第j個個體遺傳位點層。若該層層次距離小于0.5，則忽略該層，轉入下一層。否則，用layerij記錄下當前所處層，并對其執行三種遺傳操作：1）對兩個個體的第l+1 層及之后剩余層進行基因重組；2）對兩個個體的第l層進行層間重組；3）對該個體的第l+1 層及之后剩余層進行層次變異。

1.3.2 基因重組

根據式（5），確定遺傳選擇層，其操作機制如圖3 所示，兩個個體第一層的層次距離大于0.5，確定遺傳位點為第二層，基因重組算子對兩個個體剩余部分執行重組。

圖3 基因重組Fig.3 Gene recombination

1.3.3 層間重組

根據式（5），確定遺傳選擇層，層間算子對該層執行層間重組。其操作機制如圖4，兩個體的第一層層次距離為0，第二層層次距離等于0.5，對兩個個體的第二層進行重組。

圖4 層間重組Fig.4 Recombination between layers

1.3.4 層次變異

為避免無用個體的產生，執行層次變異時，第一層符號從函數集選擇，最后一層符號從終止集選擇，而其他層則從函數集與終止集中選擇。根據式（5），確定遺傳選擇層，其操作機制如圖5 所示，第一層距離大于0.5，層次變異算子從第二層開始執行變異，于是該個體隨機從函數集和終止集中選擇了一個符號，使得第二層的一個基因由雙目運算符變成單目運算符，同時為保證個體正確表達，對其子節點進行TR補齊。

圖5 層次變異Fig.5 Layer mutation

2 改進的LDGEP特征選擇分類算法

由于LDGEP 算法的種群個體有著特殊的基因編碼、解碼方式，因此，當個體的頭部基因有較多終止符時，容易產生一些無用個體。同時，種群個體隨機地從函數集和終止集中選擇符號來執行層次變異操作，這種隨機性減緩了種群的進化速度。針對上述LDGEP 算法的不足，本文提出了一種依概率種群初始化方式和基于鄰域的層次變異策略，同時，為減少特征的選擇數量，將個體選擇的特征維度縮減率作為判斷最優個體的指標之一。該算法流程如圖6所示。

圖6 FSLDGEP流程Fig.6 Flowchart of FSLDGEP algorithm

2.1 依概率種群個體初始化

在LDGEP 算法中，每層符號的選擇隨著層次的不同而不同。但是，個體編碼中過多的終止集符號使得個體的表達提前結束，容易產生無用的表達式。本文提出了依概率種群個體初始化方法，通過概率約束，使個體基因頭部更側重于選擇函數符號，增加產生有效表達式個體的數量，提高種群的進化速度。選擇概率的計算方式如式（6）：

其中：Pselect表示選擇概率；End_symble表示終止集；Symble表示函數集和終止集的合集；length(·)表示取集合的長度。

依概率種群個體初始化方法如下所示：

2.2 基于鄰域的層次變異

LDGEP 算法針對不同層產生的層次變異，其變異選擇符號集不同。而變異的隨機性使得種群個體在進化過程中容易產生低質量的解，影響算法的尋優速度。本文提出了層次鄰域的概念，層次鄰域是由種群中優秀個體的各層次符號組成，當種群個體發生層次變異時，個體基因從當前層次鄰域中選取變異符號，使變異個體的基因向著優秀個體基因的方向靠近，提升算法的尋優能力。層次鄰域定義如下。

設種群中的個體數為N，層數為L，計算個體的適應度值，并從大到小排列，取前N/2 個個體作為優秀個體，設前N/2 個個體及其基因編碼為：

將個體x1，x2，...，xN/2中每一層的符號提取去重后構成的集合作為該層的一個層次鄰域，因此可以得到L個層次鄰域式（8）：

其中：m1、m2、…、mk分別表示去重后每一層的符號總個數，即該層次鄰域的大小。種群個體從每一層的層次鄰域中選擇符號進行層次變異?；趯哟梧徲虻淖儺惒呗匀缦滤荆?/p>

2.3 改進的適應度值計算

LDGEP 算法僅將分類準確率CA（Classification Accuracy）作為判斷當前個體是否最優的指標，而忽視特征維度縮減問題，導致算法得到的函數表達式變得復雜的同時也讓表達式對特征數據較為依賴和敏感。為了提高算法對于數據特征選擇的性能，本文引入特征的維度縮減率DR（Dimension Reduction）作為新的適應度評價指標之一，將其與CA加權求和后的值作為優化目標，改變種群單一優化目標的局限性，平衡了分類函數分類準確率和維度縮減率。適應度值計算方式如下：

其中：fitness表示個體的適應度值；λ1表示準確率的權重；λ2表示維度縮減率的權重。為保證分類準確率在適應度值中的主導地位，避免維度縮減率的影響，λ1與λ2滿足λ1?λ2>0。

CA描述的是分類器分類效果的好壞，計算公式如下：

其中：TP（True Positives）表示被模型分類為正的正樣本數；TN（True Negatives）表示被模型分類為負的負樣本數；FP（False Positives）表示被模型分類為負的正樣本數；FN（False Negatives）表示被模型分類為正的負樣本數。

特征選擇數量與DR之間滿足關系式（11）：

其中：SelectFeature表示個體選擇的特征個數；AllFeature表示數據集的總特征數。故DR可替代特征選擇數量來描述算法在特征選擇上的優劣。

CA描述的是通過選擇的特征構造的分類函數對數據分類正確的概率；DR描述的是維度縮減率，即未選擇的特征在總體特征中的占比。特征選擇的數量越小越好，而CA越大越好，兩者共同用來描述算法性能優劣時評價不統一，又DR由選擇特征的數量決定，且DR的大小變化與描述算法性能優劣一致，故采用DR替代特征選擇數量來側面描述算法在特征選擇上的優劣。CA與DR共同構成本文算法適應度值計算的相關指標。

2.4 算法步驟

第1 步 初始化參數。確定種群大小NIND，種群迭代次數MAXGEN，終止集END_SYMBLE，函數集FUNC_SYMBLE，個體編碼層數L。

第2 步 依概率種群初始化。根據式（6）計算選擇概率，根據依概率種群初始化算子從FUNC_SYMBLE和END_SYMBLE中選擇2L個符號作為個體X，構造初始種群。

第3 步 種群適應度計算。將種群個體的編碼轉換成對應的分類函數，通過計算函數中特征數據變量的個數以及利用分類函數對數據進行分類，得到維度縮減率及分類準確率，再根據式（9）計算每個個體的適應度值。

第4 步 個體更新。對個體執行精英策略輪盤選擇復制算子、基因重組、層間重組算子以及基于鄰域的層次變異等遺傳操作，得到更新后的個體NewX。

第5 步 終止條件判斷。如果gen>MAXGEN，則終止，得到分類函數、維度縮減率以及分類準確率；否則令gen=gen+1，X=NewX，返回第3步。

2.5 時間復雜度分析

設最大迭代次數為MAXGEN，種群規模為NIND，種群個體編碼長度為l，數據樣本量M，由2.4 節算法步驟可知，在一個完整的循環過程中：第1步與第5步的時間復雜度可以忽略不計；第2 步中由于需要遍歷個體X，針對長度為l的個體X，初始化過程的時間復雜度近似為O(NIND?l)；第3 步操作由于每個個體均需要計算一次樣本數據的結果，其時間復雜度近似為O(NIND?M)；第4步中均是個體自身以及個體與個體之間的遺傳操作，其最差情況下的時間復雜度為O(NIND?l)。因此本文算法的總體時間復雜度近似可表示為O(MAXGEN?NIND?(M+l) +NIND?l)。

3 仿真實驗

3.1 實驗數據

實驗采用UCI［24］機器學習庫中的7 個分類數據集Hepatitis、Ionosphere、Musk1、Sonar、Heart-Statlog、WDBC（Wisconsin Diagnostic Breast Cancer）和WPBC（Wisconsin Prognostic Breast Cancer）。其中Hepatitis 數據中存在多個數據缺失的情況，本文利用其同類特征數據的平均值替代。為避免不同特征數據的量綱影響，本文對7 組數據分別進行了歸一化處理，歸一化方法如式（12）所示：

其中：表示歸一化后特征數據值；Fvalue表示未歸一化特征數據值；Fmin表示未歸一化特征數據中的最小值；Fmax表示未歸一化特征數據中的最大值。

數據集詳細信息如表1 描述。實驗仿真在Intel Core i5-4460 3.20 GHz CPU，4.0 GB 內存，64 位Windows 7 操作系統的PC上實現，軟件環境為Matlab R2017b。

表1 實驗數據集說明Tab.1 Description of experimental datasets

3.2 實驗參數

FSLDGEP 參數設置為：種群大小40，種群迭代次數300，個體層數的值如表2，常數個數10 以及函數集{+，-，*，/，sqrt，exp，sin，cos，tan，lg}，終止集由各類特征數據和常數組成。經過多組數據實驗結果比較，將式（9）中λ1的權重值設定為1，λ2權重值設定為0.01。

表2 實驗數據集參數Tab.2 Parameters of experimental datasets

為了防止產生過擬合的問題，本文采用2 折交叉、5 折交叉、10 折交叉與70%-30%這4 種驗證方式。其中，k折交叉驗證方式（k表示2、5、10）表示：將數據集分成k份，訓練時每次取k-1 份數據做訓練，剩余1 份數據做測試，使得每一份數據都能基于k-1 份數據訓練得到的結果做測試，驗證算法性能。70%-30%驗證方式表示取原始數據集中的70%的數據作為訓練集，訓練算法；30%的數據作為測試集，驗證算法性能。

對于分類問題，本文采用IF-THEN規則［23］，根據算法輸出結果與閾值比較，判斷出當前數據特征所屬類別，IF-THEN 規則如下：

其中：outValue表示輸出結果；threshold表示閾值，在本文中，閾值的大小設定為0；class表示數據類別。

評價算法的性能主要使用兩個指標［17］：DR和CA。CA越大，算法得到的映射函數的分類性能越好；DR越大，則算法選擇特征數量越少，維度縮減能力越強，特征選擇能力越強。

3.3 實驗結果

為驗證本文算法對于構建特征及其類別之間函數映射關系的可行性，本文對不同數據在不同的驗證方式下獨立重復了10 次實驗，取10 次實驗中測試集的最優分類準確率TBCA（Testset Best CA）和最優分類準確率對應的維度縮減率TBDR（Testset Best DR）及其相對應的分類函數TBF（Testset Best Function），其結果展示如表3所示。

表3的最優分類函數TBF及式（13）中的Fi分別表示數據中的第i(i=1，2，…，M，M表示數據的維度)個特征數據，該特征數據與原始數據集中的特征數據一一對應。c7表示常數。將對應的特征數據帶入表5 中的最佳分類函數中進行計算，即可判斷出當前特征數據所屬類別。

表3 最優分類準確率及維度縮減率對應函數Tab.3 Functions corresponding to optimal classification accuracy and dimension reduction rate

式（13）表示Musk1 數據集在10-fold 交叉驗證方式下，10次獨立重復實驗中，最優分類準確率對應的數據特征及其對應類別之間的映射函數。

從表3 可看出：FSLDGEP 在92%的測試上TBCA超過80%，在57%的測試上TBCA超過90%。在71%的測試上TBDR超過85%。在10-fold 驗證情況下，FSLDGEP 針對Hepatitis、Ionosphere以及WDBC數據集，分別選擇了3個、5個以及4 個特征，構建出的分類器函數最優分類準確率達到100%，針對含有60 個特征的Sonar 數據集，FSLDGEP 僅保留了3 個特征，構建出了最佳分類準確度95.24%的分類函數；針對含有166 個特征的Musk1 數據集，FSLDGEP 也僅僅是選擇了使用22 個特征去構造映射函數。對于大部分特征選擇算法而言，它們僅僅反映了一種特征及其類別之間一種不明確的關系。但FSLDGEP 可以從原始特征中選擇少量的特征構造出與數據類別相關的有效映射函數關系式，其形式較為簡單，僅通過幾個初等函數組合得到，能更好地解釋特征與類別之間的關系，雖然式（13）相對其他分類函數更為復雜，但由于Musk1數據擁有較多的特征，其類別由較多的特征決定，無法通過少數特征與線性或非線性函數構造得到分類函數，本文算法在保證維度縮減率及分類準確率較好的條件下，從而得到了一個較為復雜的分類函數。盡管本文算法在其他數據集上有較好的表現，但對于Musk1 數據集仍存在一點不足。通過最佳分類準確率及維度縮減率可以發現，最佳分類準確率與維度縮減率之間相差不大，大部分相差在10%左右，說明本文算法能夠有效地平衡特征選擇數量以及分類準確率之間的關系，在提高分類正確率的同時也能減少一定的特征選擇的數量。

為驗證本文算法構建的映射函數在數據分類上的有效性及優越性，將FSLDGEP 和公開發表文獻中的算法在相同的數據集和驗證方式下的實驗結果進行比較，每一次驗證均重復10 次，取其平均值。對比結果中：加粗數值表示在不同驗證方式下的最優值；“—”表示該算法不存在該結果或無需采用該類方法策略。

各對比算法采用的分類器有J48、3 近鄰（3-Nearest Neighbor，3NN）分類算法、1 近鄰（1-Nearest Neighbor，1NN）分類算法、5近鄰（5-Nearest Neighbor，5NN）分類算法、基于徑向基核函數的支持向量機（SVM based on Radial basis kernel function，Rbf-SVM）、SVM、隨機森林算法（Random Forests，RF）、決策樹（Decision Tree，DT）等方法。

表4 為FSLDGEP 與森林優化特征選擇算法（Feature Selection based on Forest Optimization Algorithm，FSFOA）［16］、基于鄰域有效信息比的特征選擇（Feature Selection based on the Neighborhood Effective Information Ratio，FS-NEIR）算法［25］、鄰域軟邊界特征選擇（feature evaluation and selection based on Neighborhood Soft Margin，NSM）［26］算法、基于離散互信息的分步優化特征選擇算法（Step by step Optimization Feature Selection algorithm based on Discrete mutual information，SOFS-D）［5］、基于鄰域互信息的分步優化特征選擇算法（Step by step Optimization Feature Selection algorithm based on Neighborhood mutual information，SOFS-N）［5］、基于蟻群優化的無監督特征選擇算法（Unsupervised Feature Selection algorithm based on Ant Colony Optimization，UFSACO）［19］等算法在Hepatitis數據集上的實驗結果。

表4 Hepatitis數據集上的實驗結果比較Tab.4 Comparison of experimental results on Hepatatis dataset

表5 為FSLDGEP 與FSFOA、新的森林優化算法的特征選擇算法（New Feature Selection based on Forest Optimization Algorithm，NFSFOA）［2］、NSM、FS-NEIR、UFSACO、基于模糊互補準則的支持向量機特征選擇方法（novel SVM-based feature selection method using a Fuzzy Complementary criterion，SVMFuzCoc）［13］、基于離散域采樣分類優化特征選擇算法（Feature Selection algorithm using Sampling-And-Classification optimization algorithm，FSSAC）［17］、基于粒子群優化的特征選擇方法分類的新初始化和更新機制（本文記為PSO（4-2），4-2表示原文作者采用自定義的第4 種策略做種群初始化，自定義的第2種策略更新種群）［27］、基于互信息的包裹式特征選擇混合遺傳算法（Hybrid Genetic Algorithm for Feature Selection wrapper based on mutual information，HGAFS）［28］等算法在Ionosphere數據集上的實驗結果。

表5 Ionosphere數據集上的實驗結果比較Tab.5 Comparison of experimental results on Ionosphere dataset

表6 為FSLDGEP 與聯合互信息特征選擇算法（Joint Mutual Information feature selection algorithm，JMI）［29］、基于動態變化類的特征選擇算法（Dynamic Change of Selected Feature algorithm with the class，DCSF）［29］、最小化冗余信息的動態特征選擇方法（Dynamic Feature Selection method with Minimize Redundancy Information，MRIDFS）［29］、最小冗余與最大相關的特征選擇算法（Minimal-Redundancy-Maximal-Relevance feature selection，MRMR）［30］、最大相關性和最大獨立性特征選擇算法（Max-Relevance and max-Independence feature selection algorithm，MRI）［30］等在Musk1 數據集上的實驗結果。

表6 Musk1數據集上基于10-fold驗證方式的實驗結果比較Tab.6 Comparison of experimental results based on 10-fold verification on Musk1 dataset

表7 為FSLDGEP 與基于特征子集區分度的順序前向搜索特征選擇算法（feature selection algorithm of Discernibility of Feature Subset based on Sequential Forward Search，DFSSFS）［10］、基于特征相關性的順序前向搜索特征選擇算法（feature selection algorithm of Correlation of Feature Selector based on Sequential Forward Search，CFS-SFS）［10］、基于皮爾遜相關系數絕對值的順序前向搜索相關特征選擇（Correlation based Feature Selector based on the absolute of Pearson’s correlation coefficient on Sequential Forward Search，CFSPabs-SFS）［10］、基于特征子集區分度的順序后向搜索特征選擇算法（feature selection algorithm of Discernibility of Feature Subset based on Sequential Backward Search，DFS-SBS）［10］、基于特征相關性的順序后向搜索特征選擇算法（feature selection algorithm of Correlation of Feature Selector based on Sequential Backward Search，CFS-SBS）［10］、基于皮爾遜相關系數絕對值的順序后向搜索相關特征選擇（Correlation based Feature Selector based on the absolute of Pearson’s correlation coefficient on Sequential Backward Search，CFSPabs-SBS）［10］等算法在WPBC數據集上的實驗結果。

表7 WPBC數據集上基于5-fold驗證方式的實驗結果比較Tab.7 Comparison of experimental results based on 5-fold verification on WPBC dataset

表8 為FSLDGEP 與FSFOA、FS-NEIR、基于高斯核粗糙集依賴性的特征選擇算法（Feature Selection algorithm based on Dependency of Gaussian kernel rough set，FS-GD）［31］、基于鄰域粗糙集依賴性的特征選擇算法（Feature Selection algorithm based on Dependency of Neighborhood rough set，FS-ND）［32］、基于鄰域識別率的特征選擇算法（Feature Selection algorithm based on Neighborhood Recognition Rate，FS-NRR）［33］、NFSFOA、粒子群優化（Particle Swarm Optimization，PSO）算法［27］、SVM-FuzCoc、改進的基于烏鴉搜索算法的特征選擇算法（Improved Feature Selection algorithm based on Crow Search Algorithm，IFSCrSA）［34］等在Sonar數據集上的實驗結果。

表8 Sonar數據集上的實驗結果比較Tab.8 Comparison of experimental results on Sonar dataset

如表9 為FSLDGEP 與FSFOA、NSM、NFSFOA、FS-NEIR、UFSACO、IFSCrSA、融合Shapley 值和粒子群優化算法的混合特征選擇算法（Shapley Value and Particle Swarm Optimization，SVPSO）［35］、新的Shapely 值嵌入遺傳算法（novel Shapely Value Embedded Genetic Algorithm，SVEGA）［36］等在Heart-Statlog 數據集上的實驗結果。

表9 Heart-Statlog數據集上的實驗結果比較Tab.9 Comparison of experimental results on Heart-Statlog dataset

如表10 為FSLDGEP 與SOFS-D、SOFS-N、DFA-SFS、CFSSFS、CFSPaBS-SFS、DFS-SBS、CFS-SBS、CFSPaBS-SBS、UFSACO、相關性冗余特征選擇（Relevance-Redundancy Feature Selection，RRFS）算法［19］、融合蟻群算法和隨機森林的特征選擇方法（feature selection method based on Ant Colony Optimization and Random Forest，ACORF）［18］等在WDBC 數據集上的實驗結果。

表10 WDBC數據集上的實驗結果比較Tab.10 Comparison of experimental results on WDBC dataset

從表4～10 中分類準確率的實驗結果可以看出，關于Hepatitis、Ionosphere、Musk1、WPBC、Heart-Statlog 和WDBC 數據集在10-fold條件驗證下以及關于WPBC和WDBC數據集在5-fold 條件驗證下，本文算法均達到最好；但FSLDGEP 在Ionospherre、Sonar 和Heart-Statlog 這三個數據集中，存在部分交叉驗證的情況下，其分類準確率分別低于NFSFOA、PSO 算法和IFSCrSA 算法。雖然FSLDGEP 不能保證在每一種驗證條件下的分類準確率最高，但是FSLDGEP 的分類準確率與數據集的當前最優分類準確率之間相差不大，并且在10-fold 驗證條件下，FSLDGEP 在大部分數據集上能夠取得最好的分類準確率。

從表4～10 中維度縮減率的實驗結果可以看出，關于Hepatitis、WPBC、Sonar 和WDBC 數據集在幾種不同驗證條件下，本文算法均達到最優。但在Ionosphere 數據集上基于10-fold 與70%-30% 驗證條件下分別低于NSM 算法與PSO（4-2）算法；在Heart-Statlog 數據集上基于10-fold 與2-fold驗證條件下分別低于NSM算法與NFSFOA算法。盡管維度縮減率相較于上述算法略有不足，但FSLDGEP 在大部分數據集上的不同驗證方法下的維度縮減率超過了80%，只有Hepatitis 和Heart-Statlog 數據集基于10-fold 驗證條件下的維度縮減率分別為77.89%和65.38%。出現這樣的情況并不能說明本文算法在10-fold 驗證條件下不適用于Hepatitis 和Heart-Statlog 數據集；相反地，利用本文算法對這兩個數據集進行特征選擇分類后，均能達到該數據集在10-fold 驗證條件下的最高分類準確率。

綜合表4～10 中的CA與DR的實驗結果可以發現，FSLDGEP 在Musk1、WPBC、WDBC 這3 個數據集上均取得了最好結果。盡管在有些數據集的不同驗證條件下，FSLDGEP不能使得CA與DR同時取得最優值，但是，FSLDGEP 在大部分情況下能夠使得CA與DR形成一種互補的情況。在Ionosphere 數據集上，基于10-fold 驗證條件下，FSLDGEP 與NSM 算法相比，在DR上低4.11 個百分點，但CA上高2.87 個百分點；基于70%-30%與2-fold 驗證條件下，FSLDGEP 與NFSFOA 算法相比，在CA上分別低4.4 與4.85 個百分點，但在DR上高23.53與30.89個百分點。在Sonar數據集上，基于10-fold與2-fold驗證條件下，FSLDGEP 與NFSFOA 相比，在CA上低3.01與0.94個百分點，但在DR上高26.83與13.34個百分點；基于70%-30%驗證條件下，FSLDGEP 與PSO算法相比，在CA上低2.19 個百分點，但DR上高68.96 個百分點；從CA與DR的結果也可以反映出，FSLDGEP 相較于其他算法來說占有一定的優勢。

綜合表3～10 的結果可以看出，無論是低維度特征數據Heart-Statlog，還是高緯度特征數據Musk1，FSLDGEP 都能夠很好地發現數據特征及其所屬類別之間的一個函數映射關系，且發現的函數能很好地平衡CA與DR。說明了本文算法生成的映射函數在數據特征提取分類上的可行性與有效性，同時說明了本文算法在數據特征選擇分類上的優越性。

4 結語

本文針對特征選擇算法無法揭示特征與其類別之間存在的具體關系的問題，提出了一種改進的層次距離基因表達式編程特征選擇分類算法。該方法首先依概率對種群個體進行初始化，使個體頭部側重于函數符號的選擇，減少無效基因的表達，提高了種群進化的速度；其次，通過層次距離確定遺傳位點，并對其進行遺傳操作，利用定義的層次鄰域，使得種群個體的層次變異具有導向性，提升了算法尋優的精度；最后，引入新的適應度評價指標，綜合考量了分類準確率和維度縮減率，改變了種群更新機制的局限性，使得算法能夠更有效地建立特征與類別之間的函數關系，為特征的選擇提供了一種新的思路。在7 個數據集上進行仿真實驗，與SVM、NN 等分類器相比，FSLDGEP 在能夠有效構建特征及其類別之間函數關系式，減少特征選取的數量，提升分類效果。針對高維特征數據，如何保證高分類率和低特征選擇率的同時，仍能得到一個較為簡單的函數表達式，將是進一步的研究工作。