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

（1.武漢理工大學(xué)理學(xué)院，武漢 430070；2.武漢大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，武漢 430072）

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

0 引言

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

特征選擇是一個(gè)NP-hard 問(wèn)題，對(duì)于具有n個(gè)特征的特征選擇問(wèn)題有2n個(gè)可能的特征子集［8］。在分類問(wèn)題上，通過(guò)選取關(guān)鍵的特征，忽略不太重要的數(shù)據(jù)特征，構(gòu)建出一個(gè)良好的分類器，進(jìn)而提高分類預(yù)測(cè)效果［9］。選擇的特征優(yōu)劣對(duì)于構(gòu)建出一個(gè)簡(jiǎn)潔、高效的分類系統(tǒng)有著重要的影響［10］。

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

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

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

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

基于此，本文提出了改進(jìn)的基于層次距離的基因表達(dá)式編程特征選擇分類算法（imporved Feature Selection and classification algorithm for LDGEP，F(xiàn)SLDGEP），通過(guò)改進(jìn)種群的初始化方式，使得種群個(gè)體的隨機(jī)初始化具有一定的導(dǎo)向性；同時(shí)，通過(guò)定義種群的層次鄰域來(lái)改變種群個(gè)體的隨機(jī)變異方式；并在原始的分類準(zhǔn)確率評(píng)價(jià)指標(biāo)上，考慮種群個(gè)體選擇的特征數(shù)量，將其作為適應(yīng)度評(píng)價(jià)指標(biāo)之一，平衡維度縮減率與分類準(zhǔn)確率之間的關(guān)系，構(gòu)建出類別關(guān)于特征的函數(shù)，揭示出兩者之間存在的函數(shù)映射關(guān)系。

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

LDGEP 算法是由崔未基于GEP 算法改進(jìn)而來(lái)的群智能演化算法。傳統(tǒng)的GEP 算法中存在許多需要手動(dòng)設(shè)定參數(shù)的遺傳進(jìn)化算子，如選擇復(fù)制算子、轉(zhuǎn)座算子、重組算子和變異算子等，而LDGEP 算法更改了原始GEP 算法的演化模式，重新定義了個(gè)體結(jié)構(gòu)與個(gè)體相似性計(jì)算方法，將大量的進(jìn)化算子減少至三個(gè)算子，且算子的參數(shù)無(wú)需設(shè)置，提升了算法求解問(wèn)題的精度和速度。LDGEP 算法主要包括四步：種群初始化、適應(yīng)度計(jì)算、選擇操作和遺傳操作。

1.1 種群初始化與個(gè)體編碼解碼

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

其中：t表示基因尾部長(zhǎng)度；h表示基因頭部長(zhǎng)度；n表示函數(shù)集中符號(hào)的最大運(yùn)算目數(shù)。

傳統(tǒng)GEP 算法中的個(gè)體采用固定長(zhǎng)度編碼，只是在表達(dá)時(shí)部分基因不表達(dá)。為確保個(gè)體間的距離定義一致性以及表達(dá)式樹(shù)結(jié)構(gòu)的完整性，LDGEP 算法對(duì)未表達(dá)的節(jié)點(diǎn)采用TR（Null）節(jié)點(diǎn)補(bǔ)齊方法。LDGEP 算法中的個(gè)體編碼長(zhǎng)度由該個(gè)體的層數(shù)確定，其長(zhǎng)度計(jì)算公式如式（2）：

其中：len表示個(gè)體長(zhǎng)度；L表示層數(shù)。

如表達(dá)式a+sin(b)，該個(gè)體的編碼及其表達(dá)式樹(shù)結(jié)構(gòu)如圖1（a）。解碼時(shí)，根據(jù)運(yùn)算目數(shù)對(duì)未表達(dá)的基因采用TR 補(bǔ)齊，如圖1（b），虛線代表補(bǔ)齊的TR 節(jié)點(diǎn)。再根據(jù)各節(jié)點(diǎn)運(yùn)算符的性質(zhì)以及二叉樹(shù)的中序遍歷方式，將個(gè)體的樹(shù)結(jié)構(gòu)轉(zhuǎn)換成為數(shù)學(xué)表達(dá)式。

圖1 表達(dá)樹(shù)結(jié)構(gòu)及補(bǔ)齊后表達(dá)樹(shù)結(jié)構(gòu)Fig.1 Structures of expression tree and complemented expression tree

1.2 距離定義

種群個(gè)體的層次示意圖如圖2 所示，每層個(gè)體的數(shù)量為2l-1，其中l(wèi)表示當(dāng)前的層數(shù)。

圖2 個(gè)體層次示意圖Fig.2 Schematic diagram of individual layer

LDGEP 算法對(duì)每個(gè)個(gè)體的每一層給定一個(gè)權(quán)值，用以區(qū)分不同層對(duì)于個(gè)體的影響。種群個(gè)體的層次距離為基于加權(quán)的漢明距離，計(jì)算公式所示：

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

其中：l表示層數(shù)。隨著層次的遞增，層次重要性越低，從而對(duì)解碼后的個(gè)體的表達(dá)影響越低。

1.3 遺傳操作

1.3.1 遺傳位點(diǎn)選擇

由于每一層對(duì)于種群個(gè)體的表達(dá)有不同的影響，通過(guò)對(duì)層次距離不同的層采用遺傳操作，使種群個(gè)體向更優(yōu)秀的個(gè)體靠近。通過(guò)計(jì)算每一層個(gè)體間的層次距離確定遺傳位點(diǎn)。遺傳位點(diǎn)的確定規(guī)則如下所示：

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

1.3.2 基因重組

根據(jù)式（5），確定遺傳選擇層，其操作機(jī)制如圖3 所示，兩個(gè)個(gè)體第一層的層次距離大于0.5，確定遺傳位點(diǎn)為第二層，基因重組算子對(duì)兩個(gè)個(gè)體剩余部分執(zhí)行重組。

圖3 基因重組Fig.3 Gene recombination

1.3.3 層間重組

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

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

1.3.4 層次變異

為避免無(wú)用個(gè)體的產(chǎn)生，執(zhí)行層次變異時(shí)，第一層符號(hào)從函數(shù)集選擇，最后一層符號(hào)從終止集選擇，而其他層則從函數(shù)集與終止集中選擇。根據(jù)式（5），確定遺傳選擇層，其操作機(jī)制如圖5 所示，第一層距離大于0.5，層次變異算子從第二層開(kāi)始執(zhí)行變異，于是該個(gè)體隨機(jī)從函數(shù)集和終止集中選擇了一個(gè)符號(hào)，使得第二層的一個(gè)基因由雙目運(yùn)算符變成單目運(yùn)算符，同時(shí)為保證個(gè)體正確表達(dá)，對(duì)其子節(jié)點(diǎn)進(jìn)行TR補(bǔ)齊。

圖5 層次變異Fig.5 Layer mutation

2 改進(jìn)的LDGEP特征選擇分類算法

由于LDGEP 算法的種群個(gè)體有著特殊的基因編碼、解碼方式，因此，當(dāng)個(gè)體的頭部基因有較多終止符時(shí)，容易產(chǎn)生一些無(wú)用個(gè)體。同時(shí)，種群個(gè)體隨機(jī)地從函數(shù)集和終止集中選擇符號(hào)來(lái)執(zhí)行層次變異操作，這種隨機(jī)性減緩了種群的進(jìn)化速度。針對(duì)上述LDGEP 算法的不足，本文提出了一種依概率種群初始化方式和基于鄰域的層次變異策略，同時(shí)，為減少特征的選擇數(shù)量，將個(gè)體選擇的特征維度縮減率作為判斷最優(yōu)個(gè)體的指標(biāo)之一。該算法流程如圖6所示。

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

2.1 依概率種群個(gè)體初始化

在LDGEP 算法中，每層符號(hào)的選擇隨著層次的不同而不同。但是，個(gè)體編碼中過(guò)多的終止集符號(hào)使得個(gè)體的表達(dá)提前結(jié)束，容易產(chǎn)生無(wú)用的表達(dá)式。本文提出了依概率種群個(gè)體初始化方法，通過(guò)概率約束，使個(gè)體基因頭部更側(cè)重于選擇函數(shù)符號(hào)，增加產(chǎn)生有效表達(dá)式個(gè)體的數(shù)量，提高種群的進(jìn)化速度。選擇概率的計(jì)算方式如式（6）：

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

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

2.2 基于鄰域的層次變異

LDGEP 算法針對(duì)不同層產(chǎn)生的層次變異，其變異選擇符號(hào)集不同。而變異的隨機(jī)性使得種群個(gè)體在進(jìn)化過(guò)程中容易產(chǎn)生低質(zhì)量的解，影響算法的尋優(yōu)速度。本文提出了層次鄰域的概念，層次鄰域是由種群中優(yōu)秀個(gè)體的各層次符號(hào)組成，當(dāng)種群個(gè)體發(fā)生層次變異時(shí)，個(gè)體基因從當(dāng)前層次鄰域中選取變異符號(hào)，使變異個(gè)體的基因向著優(yōu)秀個(gè)體基因的方向靠近，提升算法的尋優(yōu)能力。層次鄰域定義如下。

設(shè)種群中的個(gè)體數(shù)為N，層數(shù)為L(zhǎng)，計(jì)算個(gè)體的適應(yīng)度值，并從大到小排列，取前N/2 個(gè)個(gè)體作為優(yōu)秀個(gè)體，設(shè)前N/2 個(gè)個(gè)體及其基因編碼為：

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

其中：m1、m2、…、mk分別表示去重后每一層的符號(hào)總個(gè)數(shù)，即該層次鄰域的大小。種群個(gè)體從每一層的層次鄰域中選擇符號(hào)進(jìn)行層次變異。基于層次鄰域的變異策略如下所示：

2.3 改進(jìn)的適應(yīng)度值計(jì)算

LDGEP 算法僅將分類準(zhǔn)確率CA（Classification Accuracy）作為判斷當(dāng)前個(gè)體是否最優(yōu)的指標(biāo)，而忽視特征維度縮減問(wèn)題，導(dǎo)致算法得到的函數(shù)表達(dá)式變得復(fù)雜的同時(shí)也讓表達(dá)式對(duì)特征數(shù)據(jù)較為依賴和敏感。為了提高算法對(duì)于數(shù)據(jù)特征選擇的性能，本文引入特征的維度縮減率DR（Dimension Reduction）作為新的適應(yīng)度評(píng)價(jià)指標(biāo)之一，將其與CA加權(quán)求和后的值作為優(yōu)化目標(biāo)，改變種群?jiǎn)我粌?yōu)化目標(biāo)的局限性，平衡了分類函數(shù)分類準(zhǔn)確率和維度縮減率。適應(yīng)度值計(jì)算方式如下：

其中：fitness表示個(gè)體的適應(yīng)度值；λ1表示準(zhǔn)確率的權(quán)重；λ2表示維度縮減率的權(quán)重。為保證分類準(zhǔn)確率在適應(yīng)度值中的主導(dǎo)地位，避免維度縮減率的影響，λ1與λ2滿足λ1?λ2>0。

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

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

特征選擇數(shù)量與DR之間滿足關(guān)系式（11）：

其中：SelectFeature表示個(gè)體選擇的特征個(gè)數(shù)；AllFeature表示數(shù)據(jù)集的總特征數(shù)。故DR可替代特征選擇數(shù)量來(lái)描述算法在特征選擇上的優(yōu)劣。

CA描述的是通過(guò)選擇的特征構(gòu)造的分類函數(shù)對(duì)數(shù)據(jù)分類正確的概率；DR描述的是維度縮減率，即未選擇的特征在總體特征中的占比。特征選擇的數(shù)量越小越好，而CA越大越好，兩者共同用來(lái)描述算法性能優(yōu)劣時(shí)評(píng)價(jià)不統(tǒng)一，又DR由選擇特征的數(shù)量決定，且DR的大小變化與描述算法性能優(yōu)劣一致，故采用DR替代特征選擇數(shù)量來(lái)側(cè)面描述算法在特征選擇上的優(yōu)劣。CA與DR共同構(gòu)成本文算法適應(yīng)度值計(jì)算的相關(guān)指標(biāo)。

2.4 算法步驟

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

第2 步 依概率種群初始化。根據(jù)式（6）計(jì)算選擇概率，根據(jù)依概率種群初始化算子從FUNC_SYMBLE和END_SYMBLE中選擇2L個(gè)符號(hào)作為個(gè)體X，構(gòu)造初始種群。

第3 步 種群適應(yīng)度計(jì)算。將種群個(gè)體的編碼轉(zhuǎn)換成對(duì)應(yīng)的分類函數(shù)，通過(guò)計(jì)算函數(shù)中特征數(shù)據(jù)變量的個(gè)數(shù)以及利用分類函數(shù)對(duì)數(shù)據(jù)進(jìn)行分類，得到維度縮減率及分類準(zhǔn)確率，再根據(jù)式（9）計(jì)算每個(gè)個(gè)體的適應(yīng)度值。

第4 步 個(gè)體更新。對(duì)個(gè)體執(zhí)行精英策略輪盤(pán)選擇復(fù)制算子、基因重組、層間重組算子以及基于鄰域的層次變異等遺傳操作，得到更新后的個(gè)體NewX。

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

2.5 時(shí)間復(fù)雜度分析

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

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

數(shù)據(jù)集詳細(xì)信息如表1 描述。實(shí)驗(yàn)仿真在Intel Core i5-4460 3.20 GHz CPU，4.0 GB 內(nèi)存，64 位Windows 7 操作系統(tǒng)的PC上實(shí)現(xiàn)，軟件環(huán)境為Matlab R2017b。

表1 實(shí)驗(yàn)數(shù)據(jù)集說(shuō)明Tab.1 Description of experimental datasets

3.2 實(shí)驗(yàn)參數(shù)

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

表2 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)Tab.2 Parameters of experimental datasets

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

對(duì)于分類問(wèn)題，本文采用IF-THEN規(guī)則［23］，根據(jù)算法輸出結(jié)果與閾值比較，判斷出當(dāng)前數(shù)據(jù)特征所屬類別，IF-THEN 規(guī)則如下：

其中：outValue表示輸出結(jié)果；threshold表示閾值，在本文中，閾值的大小設(shè)定為0；class表示數(shù)據(jù)類別。

評(píng)價(jià)算法的性能主要使用兩個(gè)指標(biāo)［17］：DR和CA。CA越大，算法得到的映射函數(shù)的分類性能越好；DR越大，則算法選擇特征數(shù)量越少，維度縮減能力越強(qiáng)，特征選擇能力越強(qiáng)。

3.3 實(shí)驗(yàn)結(jié)果

為驗(yàn)證本文算法對(duì)于構(gòu)建特征及其類別之間函數(shù)映射關(guān)系的可行性，本文對(duì)不同數(shù)據(jù)在不同的驗(yàn)證方式下獨(dú)立重復(fù)了10 次實(shí)驗(yàn)，取10 次實(shí)驗(yàn)中測(cè)試集的最優(yōu)分類準(zhǔn)確率TBCA（Testset Best CA）和最優(yōu)分類準(zhǔn)確率對(duì)應(yīng)的維度縮減率TBDR（Testset Best DR）及其相對(duì)應(yīng)的分類函數(shù)TBF（Testset Best Function），其結(jié)果展示如表3所示。

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

表3 最優(yōu)分類準(zhǔn)確率及維度縮減率對(duì)應(yīng)函數(shù)Tab.3 Functions corresponding to optimal classification accuracy and dimension reduction rate

式（13）表示Musk1 數(shù)據(jù)集在10-fold 交叉驗(yàn)證方式下，10次獨(dú)立重復(fù)實(shí)驗(yàn)中，最優(yōu)分類準(zhǔn)確率對(duì)應(yīng)的數(shù)據(jù)特征及其對(duì)應(yīng)類別之間的映射函數(shù)。

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

為驗(yàn)證本文算法構(gòu)建的映射函數(shù)在數(shù)據(jù)分類上的有效性及優(yōu)越性，將FSLDGEP 和公開(kāi)發(fā)表文獻(xiàn)中的算法在相同的數(shù)據(jù)集和驗(yàn)證方式下的實(shí)驗(yàn)結(jié)果進(jìn)行比較，每一次驗(yàn)證均重復(fù)10 次，取其平均值。對(duì)比結(jié)果中：加粗?jǐn)?shù)值表示在不同驗(yàn)證方式下的最優(yōu)值；“—”表示該算法不存在該結(jié)果或無(wú)需采用該類方法策略。

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

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

表4 Hepatitis數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較Tab.4 Comparison of experimental results on Hepatatis dataset

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

表5 Ionosphere數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較Tab.5 Comparison of experimental results on Ionosphere dataset

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

表6 Musk1數(shù)據(jù)集上基于10-fold驗(yàn)證方式的實(shí)驗(yàn)結(jié)果比較Tab.6 Comparison of experimental results based on 10-fold verification on Musk1 dataset

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

表7 WPBC數(shù)據(jù)集上基于5-fold驗(yàn)證方式的實(shí)驗(yàn)結(jié)果比較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，F(xiàn)S-GD）［31］、基于鄰域粗糙集依賴性的特征選擇算法（Feature Selection algorithm based on Dependency of Neighborhood rough set，F(xiàn)S-ND）［32］、基于鄰域識(shí)別率的特征選擇算法（Feature Selection algorithm based on Neighborhood Recognition Rate，F(xiàn)S-NRR）［33］、NFSFOA、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［27］、SVM-FuzCoc、改進(jìn)的基于烏鴉搜索算法的特征選擇算法（Improved Feature Selection algorithm based on Crow Search Algorithm，IFSCrSA）［34］等在Sonar數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。

表8 Sonar數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較Tab.8 Comparison of experimental results on Sonar dataset

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

表9 Heart-Statlog數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較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、相關(guān)性冗余特征選擇（Relevance-Redundancy Feature Selection，RRFS）算法［19］、融合蟻群算法和隨機(jī)森林的特征選擇方法（feature selection method based on Ant Colony Optimization and Random Forest，ACORF）［18］等在WDBC 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。

表10 WDBC數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較Tab.10 Comparison of experimental results on WDBC dataset

從表4～10 中分類準(zhǔn)確率的實(shí)驗(yàn)結(jié)果可以看出，關(guān)于Hepatitis、Ionosphere、Musk1、WPBC、Heart-Statlog 和WDBC 數(shù)據(jù)集在10-fold條件驗(yàn)證下以及關(guān)于WPBC和WDBC數(shù)據(jù)集在5-fold 條件驗(yàn)證下，本文算法均達(dá)到最好；但FSLDGEP 在Ionospherre、Sonar 和Heart-Statlog 這三個(gè)數(shù)據(jù)集中，存在部分交叉驗(yàn)證的情況下，其分類準(zhǔn)確率分別低于NFSFOA、PSO 算法和IFSCrSA 算法。雖然FSLDGEP 不能保證在每一種驗(yàn)證條件下的分類準(zhǔn)確率最高，但是FSLDGEP 的分類準(zhǔn)確率與數(shù)據(jù)集的當(dāng)前最優(yōu)分類準(zhǔn)確率之間相差不大，并且在10-fold 驗(yàn)證條件下，F(xiàn)SLDGEP 在大部分?jǐn)?shù)據(jù)集上能夠取得最好的分類準(zhǔn)確率。

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

綜合表4～10 中的CA與DR的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，F(xiàn)SLDGEP 在Musk1、WPBC、WDBC 這3 個(gè)數(shù)據(jù)集上均取得了最好結(jié)果。盡管在有些數(shù)據(jù)集的不同驗(yàn)證條件下，F(xiàn)SLDGEP不能使得CA與DR同時(shí)取得最優(yōu)值，但是，F(xiàn)SLDGEP 在大部分情況下能夠使得CA與DR形成一種互補(bǔ)的情況。在Ionosphere 數(shù)據(jù)集上，基于10-fold 驗(yàn)證條件下，F(xiàn)SLDGEP 與NSM 算法相比，在DR上低4.11 個(gè)百分點(diǎn)，但CA上高2.87 個(gè)百分點(diǎn)；基于70%-30%與2-fold 驗(yàn)證條件下，F(xiàn)SLDGEP 與NFSFOA 算法相比，在CA上分別低4.4 與4.85 個(gè)百分點(diǎn)，但在DR上高23.53與30.89個(gè)百分點(diǎn)。在Sonar數(shù)據(jù)集上，基于10-fold與2-fold驗(yàn)證條件下，F(xiàn)SLDGEP 與NFSFOA 相比，在CA上低3.01與0.94個(gè)百分點(diǎn)，但在DR上高26.83與13.34個(gè)百分點(diǎn)；基于70%-30%驗(yàn)證條件下，F(xiàn)SLDGEP 與PSO算法相比，在CA上低2.19 個(gè)百分點(diǎn)，但DR上高68.96 個(gè)百分點(diǎn)；從CA與DR的結(jié)果也可以反映出，F(xiàn)SLDGEP 相較于其他算法來(lái)說(shuō)占有一定的優(yōu)勢(shì)。

綜合表3～10 的結(jié)果可以看出，無(wú)論是低維度特征數(shù)據(jù)Heart-Statlog，還是高緯度特征數(shù)據(jù)Musk1，F(xiàn)SLDGEP 都能夠很好地發(fā)現(xiàn)數(shù)據(jù)特征及其所屬類別之間的一個(gè)函數(shù)映射關(guān)系，且發(fā)現(xiàn)的函數(shù)能很好地平衡CA與DR。說(shuō)明了本文算法生成的映射函數(shù)在數(shù)據(jù)特征提取分類上的可行性與有效性，同時(shí)說(shuō)明了本文算法在數(shù)據(jù)特征選擇分類上的優(yōu)越性。

4 結(jié)語(yǔ)

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